Browse Prior Art Database

ImageHive: An effective interactive visualization method for image collections

IP.com Disclosure Number: IPCOM000198080D
Publication Date: 2010-Jul-26
Document File: 4 page(s) / 334K

Publishing Venue

The IP.com Prior Art Database

Abstract

“A picture is worth a thousand words!” Just as the old adage says, image is always one of the most intuitive expressions. Interactive visualization of image collections has been an active subject in visual art, design, and human-computer interaction [MoMA exhibit][UMD photomesa][vister], these techniques can facilitate visual exploration and management of images, and foster users’ understanding and consuming of a large image collection and the complex relationships among these images. Further insights can be revealed if interactive visualization is used in combination with automatic image analysis techniques such as segmentation and recognition. Traditional image visualization methods (e.g. [1]) use node-link graphs to visualize images, where nodes represent images and edges between nodes represent the relationship between images. Users can interactively explore the relationships between images, where such interactions are supported by related graph visualization techniques. However, the traditional graph-based visualization method could not make full use of the graphical spaces because of its internal graph embedding method, whereas it is very important to make full use of graphical space to visualize more content. Beside this, it may lead to heavy overlapped of images when the graph is huge. On the contrary, some photo collage methods (e.g. [2][3]) have been proposed to make the best use of graphical spaces. As mostly these collage methods are implemented by some rule based algorithms, it may turn out to be awful in some cases because of its overlap, and can not reflect the relationships between images. Moreover, such rule based methods are hard to support for rich interaction. To address these problems, we proposed ImageHive, an interactive visualization method for images based on Voronoi diagram.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 49% of the total text.

Page 1 of 4

ImageHive: An effective interactive visualization method for image collections

In this part, we introduce the method as two parts:
Image tessellation Interaction support

3.1 Image tessellation

The method workflow is shown as follows:

Image tessellation workflow

Input:
n images
closed region G for tessellation threshold

e

           for stop criterion
Output:
the image tessellation as Voronoi diagram Description:
extract features

M

from n images (

M

is a n*m matrix, where m is length of feature)

project

M

into graphical space, and scale it into given the graphical region G with coordinates

n

{

i

X £

£

1

}

i

{ in region G, where cells in Voronoi diagram

denoted as n

i

i

X £

£

1

}

generate Voronoi diagram by coordinates n

i

{

set the center of region n

i

i

C £

£

1

}

{ be n

i

C £

£

1

}

{ , calculate the distance between n

i

X £

£

1

'}

{ and

}

i

i

X £

£

1

i

{ , as err

For example, one way to calculate the distance is described as follows

i

X £

£

1

'}

i

n

n

2

'

err

=

Xi X

i

i

=

1

e

{

}

if err <

, return n

i

i

C £

£

1

{ and go to step 3

There are a lot of methods to extract features, which can represent the characteristics in some specific aspects, e.g. global colors, textures, time, geo-region and etc. Our method is not constrained in a specific feature extracting method. Specially, in the situation that each image is tagged with some words, features could be extracted as semantic meaning.

After the features are extracted, images are then projected into graphical space by these features. Existing dimensionality reduction approaches include linear methods such as PCA[4], multi-dimensional scaling [11] (MDS), or non-linear mthods including Locally linear embedding (LLE) [6], Laplacian EigenMap[7] and ISOMAP[5]. In our implementation, we use dimensionality reduction method to project images into two dimensional graphical spaces as Figure 2(a) shows. After the projection, we scale the coordinates to fit the given region.

The relationships between images can be embodied by the distances of coordinates in the projection. Our visualization method is based on Voronoi diagram, which can be generated with O(nlgn

)

{ = n

i

X £

£

1

}

'}

set n

i

i

X £

£

1

i

time complexity

[8][9]. Figure 2(b) shows an example of Voronoi diagram generated by the coordinates. Then, the diagram is iteratively adjusted to make the cells of diagram fit the images. Finally, the images will be trimmed into cells of

1

Page 2 of 4

Voronoi diagram shown as Figure 2(c).

3.2 Interaction Support

Our method allows the user to incrementally add, delete and drag image. When users interactively add, delete or drag the image, the initial Voronoi diagram can be constructed by incremental construction algorithm [10] according to the new coordinates of images. Here, we give a solution on how to update the coordinates of other images to fit the change.

Incremental Update

Input:
the image

p

which is changed

the initial Voronoi tessellation n

i

{ with coordinate n

i

C £

£

1

}

{...