Similarity-based visualization of large image collections

Abstract

Effective techniques for organizing and visualizing large image collections are in growing demand as visual search gets increasingly popular. Targeting an online astronomy archive with thousands of images, we present our solution for image search and clustering based on the evaluation of image similarity using both visual and textual information. Time-consuming image similarity computation is accelerated using graphics processing unit. To lay out images, we introduce iMap, a treemap-based representation for visualizing and navigating image search and clustering results. iMap not only makes effective use of available display area to arrange images but also maintains stable update when images are inserted or removed during the query. We also develop an embedded visualization that integrates image tags for in-place search refinement. To show the effectiveness of our approach, we demonstrate experimental results, compare our iMap layout with a force-directed layout, and conduct a comparative user study. As a potential tool for astronomy education and outreach, we deploy our iMap to a large tiled display of nearly 50 million pixels.

Keywords

Image collection astronomy archive image layout embedded search tiled display

Introduction

With the booming of digital cameras and image archiving and photo sharing websites, browsing and searching through large online image collections is becoming increasingly popular. An emerging trend is that images are now often tagged with names, keywords, hyperlinks, and so on to improve the search and understanding. In this article, we strive for innovation on the organization and interaction aspects of image search rather than the search algorithm itself. Specifically, we explore how to arrange images in a layout for better viewing and how to leverage the connection between image and text for better interaction.

Many existing applications provide overviews of image collections by presenting a set of thumbnail images arranged in a spreadsheet-like interface. We advocate a more attractive way for image browsing to enable effective sense-making of large image collections through image ranking and clustering, and intuitive presentation and interaction. We analyze image content and design measures to evaluate their similarity using both visual and textual information. We arrange similar images close to each other and leverage a treemap-based representation to visualize image search and clustering results to facilitate the understanding. This visual means brings several benefits such as effective screen utilization, occlusion minimization, and stable update. In addition, we develop an embedded visualization that integrates image tags for in-place search refinement.

We experiment with our approach using the Astronomy Picture of the Day (APOD),¹ a popular online astronomy archive. Every day, APOD features a picture of our universe, along with a brief explanation written by a professional astronomer. Since its debut in June 1995, APOD has archived thousands of handpicked pictures, which makes it the largest collection of annotated astronomical images on the Internet. This makes it perfect for us to include textual information into similarity analysis and interaction design. Our work complements the state-of-the-art image search and exploration techniques with new interface and interaction that enable effective sense-making of a large image collection. This interface guides users to sift through the collection and identify images of interest, a critical need for many applications involving with large image collections.

This article is organized as follows. We review related work in section “Related work.” In sections “Image distance measure” and “Image ranking and clustering,” we describe the distance computation between images and the ranking and clustering of images, respectively. In section “Image layout and interaction,” we discuss our iMap layout design and interaction functions. Results are given in section “Results,” followed by a comparison of our iMap layout with a force-directed layout in terms of screen utilization and overlap reduction in section “Comparison with force-directed layout.” In section “Deployment of iMap to tiled display,” we describe the deployment of iMap to a large display wall. A user study that compares iMap with existing image search functions provided by online APOD is given in section “User study.” Finally, we conclude this work in section “Conclusions and future work.”

Related work

Image similarity analysis

Content-based image analysis is at the heart of modern image searching and retrieval. Its primary goal is to organize digital image archives by their visual content. Image features capture visual properties of an image, either globally or locally. To extract image features that help perform meaningful classification and retrieval, researchers have utilized key visual contributions such as color,^2–4 texture,^3–5 shape,⁶ salient points,⁷ and landmarks.⁸ Advances have been made in both deriving new features and constructing signatures based on these features.⁹ We leverage the color and spectrum information together with the grayscale version of images for similarity analysis.

Image collection organization

The most common way to organize a large collection of images is based on a two-dimensional grid of thumbnails, but it enforces a uniform thumbnail aspect ratio. Furthermore, only parts of the data set can be seen within line of sight when the image collection is excessively large. Over the years, different new solutions have been proposed to improve the organization of image collections. Chen et al.¹⁰ leveraged the Pathfinder network scaling technique, originally developed for the analysis of proximity data in psychology, to organize a collection of images based on their color labels, texture, shape orientation, and so on. Torres et al.¹¹ introduced a focus + context approach based on spiral and concentric rings for exploring query results in an image database. Yang et al.¹² developed a scalable semantic image browser (SIB) based on the semantic content of images. The multidimensional scaling layout based on semantic similarities was used for image overview, and the value and relation layout was used for content overview. Gomi et al.¹³ presented clustered album thumbnails (CAT) for hierarchical browsing of large image collections, which show representative images when zooming out and individual images when zooming in. Brivio et al.¹⁴ proposed a dynamic image browsing mechanism in which the arrangement of the thumbnails is based on weighted anisotropic Voronoi diagrams and Lloyd relaxation. Tan et al.¹⁵ designed ImageHive that generates a summary image from an image collection. A constrained graph layout algorithm was used to preserve the relationships between images and avoid occluding their salient parts, and a constrained Voronoi tessellation algorithm was applied to locally refine the layout and tile the image plane.

Visualization and presentation modes

Common visualization schemes for image collections include relevance-ordered (e.g. Google Images), time-ordered (e.g. the timeline¹⁶ and time quilt¹⁷), clustered (e.g. the design gallery layout using multidimensional scaling¹⁸), hierarchical (e.g. Google Image Swirl), and composite (the mix of two or more of the preceding forms). In terms of user presentation, there are three modes: static (i.e. no motion is involved whatsoever), moving (i.e. constant motion even without interaction), and interactive (i.e. motion triggered only under user interaction). A recent study has shown that static presentation is better than moving presentation in terms of recognition success and user preference.¹⁹ We design a layout for organizing a large image collection using the composite visualization scheme and interactive presentation mode.

Image distance measure

Measuring the similarity or distance between two images is central to any image searching or clustering tasks. Images themselves provide direct cues to visual comparison. Textual information associated with images, whenever available, gives additional hints for us to evaluate their similarity or difference. We therefore compare images using their visual and textual information from multiple perspectives and define five partial distances ( $D_{G}$ , $D_{F}$ , $D_{H}$ , $D_{K}$ , and $D_{L}$ ). The overall distance measure is a weighted summation of all the partial distances.

Visual distance

Different images in an image collection come with different dimensions, types, and formats. For simplicity, we convert all resulting images to the same type and format and scale them down to a fixed resolution ( $256 \times 256$ ). We consider three aspects of images, namely, grayscale image distance, spectrum image distance, and color histogram distance, for calculating their visual distance. Note that our solution to visual similarity analysis is by no means ideal. Rather, we seek a cost-effective solution to serve the basic visual search need.

Grayscale image distance

Intuitively, the similarity between two images can be evaluated by identifying their structural similarity. The structural similarity index proposed by Wang et al.²⁰ considers luminance, contrast, and structure information of the two images. We use the grayscale version of images for this evaluation and will consider color information separately when computing the color histogram distance. Given two grayscale images, we take a local $8 \times 8$ window, which moves pixel by pixel over the entire image, to evaluate their similarity. For two corresponding image blocks $B_{a}$ and $B_{b}$ , we compute their similarity as

S_{B} (B_{a}, B_{b}) = \frac{(2 μ_{a} μ_{b} + c_{1}) (2 σ_{a b} + c_{2})}{(μ_{a}^{2} + μ_{b}^{2} + c_{1}) (σ_{a}^{2} + σ_{b}^{2} + c_{2})}

(1)

where $μ_{a}$ and $μ_{b}$ are the means of $B_{a}$ and $B_{b}$ , respectively; $σ_{a}$ and $σ_{b}$ are the standard deviations of $B_{a}$ and $B_{b}$ , respectively; and $σ_{ab}$ is the covariance of $B_{a}$ and $B_{b}$ . Small constants $c_{1}$ and $c_{2}$ are included to avoid instability when $μ_{a}$ , $μ_{b}$ , $σ_{a}$ , and $σ_{b}$ are very close to 0. As suggested by Wang et al.,²⁰ we set $c_{1} = (0.01 \times L)^{2}$ and $c_{2} = (0.03 \times L)^{2}$ , where L is the number of levels in the grayscale images. We define the distance between two grayscale images $G_{a}$ and $G_{b}$ as

D_{G} (G_{a}, G_{b}) = 1.0 - \frac{1}{m} \sum_{i = 1}^{m} {\bar{S}}_{B} (B_{ai}, B_{bi})

(2)

Where m is the total number of image blocks considered and $\bar{S}$ denotes the normalized similarity value.

Spectrum image distance

The power spectrum of an image is a representation of the magnitude of its various frequency components that has been transformed using the Fourier transform. The power at each location in the spectrum indicates the frequency and orientation of a particular feature in the image. We use the grayscale version of the spectrum image after the $\log$ transform. In Figure 1, we compare four astronomy images using their spectrum images to demonstrate the feasibility of analyzing image similarity in terms of complexity. Given two grayscale frequency spectrum images $F_{a}$ and $F_{b}$ , we compute their similarity through evaluating their block-wise Pearson linear correlation. Again, we take a local $8 \times 8$ window, which moves pixel by pixel over the entire image. For two corresponding image blocks $B_{a}$ and $B_{b}$ , we compute their correlation as

P_{B} (B_{a}, B_{b}) = \frac{1}{n} \sum_{j = 1}^{n} (\frac{p_{aj} - μ_{a}}{σ_{a}}) (\frac{p_{bj} - μ_{b}}{σ_{b}})

(3)

where $p_{aj}$ and $p_{bj}$ are the jth pixel values of $B_{a}$ and $B_{b}$ , respectively; $μ_{a}$ and $μ_{b}$ are the means of $B_{a}$ and $B_{b}$ , respectively; $σ_{a}$ and $σ_{b}$ are the standard deviations of $B_{a}$ and $B_{b}$ , respectively; and n is the number of pixels in the block. With equation (3), we compute the distance $D_{F} (F_{a}, F_{b})$ similar to equation (2), where the absolute correlationvalues $| P_{B} (B_{ai}, B_{bi}) |$ are used instead.

Figure 1.

Four images and their respective grayscale frequency spectrum images. All four spectrum images are enhanced with the same $\log$ transform. We can observe that (a) and (b) are almost similar, followed by (a) and (e), and (a) and (g). (a) original (b) spectrum (c) original (d) spectrum (e) original (f) spectrum (g) original (h) spectrum.

Color histogram distance

Image colors provide additional information for similarity comparison. Given an image, we compute its color histogram by sampling each of the R, G, and B channels into eight levels, which leads to a color histogram of 512 entries. Given two normalized color histograms $H_{a}$ and $H_{b}$ , we can use the Kullback–Leibler divergence (KLD) to evaluate their difference

K_{H} (H_{a} | | H_{b}) = \sum_{k = 1}^{b} h_{a} (k) \log \frac{h_{a} (k)}{h_{b} (k)}

(4)

where $h_{a} (k)$ and $h_{b} (k)$ are the heights of the kth bin for $H_{a}$ and $H_{b}$ , respectively, and b is the number of bins in the color histogram. Notice that the KLD is not a true metric, that is, $K_{H} (H_{a} | | H_{b}) \neq K_{H} (H_{b} | | H_{a})$ . We thus actually use the symmetric Jensen–Shannon divergence (JSD) measure instead

D_{H} (H_{a}, H_{b}) = \frac{K_{H} (H_{a} | | H_{m}) + K_{H} (H_{b} | | H_{m})}{2}

(5)

where $H_{m} = (H_{a} + H_{b}) / 2$ .

Textual distance

To obtain textual features, we extract meta-tagged keywords in the HTML header. We also extract hyperlinks in the explanation. These hyperlinks refer to URLs, and similar hyperlinks indicate that their corresponding images may also share similarity. Then, we convert all uppercase letters to lowercase ones for extracted keywords and hyperlinks and apply the bag-of-words model²¹ for textual similarity measurement. We point out that semantic-based methods for detecting text similarity²² can classify text based on the same semantic focus such as an object or action. Nevertheless, the simple keyword extraction and similarity evaluation technique we propose performs well as all images in our case share the same theme of astronomy.

Keyword list distance

We treat two given keywords $k_{a}$ and $k_{b}$ as strings and calculate their edit distance by computing the minimum number of inserts, deletes, and substitutions required to transform one string into the other. The distance between $k_{a}$ and $k_{b}$ is calculated as

D_{k} (k_{a}, k_{b}) = \frac{c_{i} n_{i} + c_{d} n_{d} + c_{s} n_{s}}{| k_{a} | + | k_{b} |}

(6)

where $c_{i}$ , $c_{d}$ , and $c_{s}$ are the costs of insertion, deletion, and substitution operations, respectively; $n_{i}$ , $n_{d}$ , and $n_{s}$ are the numbers of times that these three operations occur, respectively; and $| k_{a} |$ and $| k_{b} |$ are the lengths of keywords $k_{a}$ and $k_{b}$ , respectively. We set $c_{i} = 2.0$ , $c_{d} = 2.0$ , and $c_{s} = 3.0$ since the cost of deletion or insertion operation must be greater than half of the cost of substitution operation. Otherwise, two strings $k_{a}$ and $k_{b}$ will be matched using the deletion and insertion operations only.

To calculate the distance between two lists of keywords, we take into account all keyword pairs from the two lists. Our solution is to calculate the average of the minimum distance values of keyword pairs, that is

D_{K} (K_{a}, K_{b}) = \frac{A_{K} (K_{a}, K_{b}) + A_{K} (K_{b}, K_{a})}{2}

(7)

where $A_{K} (K_{a}, K_{b})$ is the average of the minimum distances (equation (6)) for each keyword in list $K_{a}$ to any keyword in list $K_{b}$ . All $D_{K}$ are normalized for use.

Hyperlink list distance

Given two hyperlinks, we compute their similarity by first determining whether we are comparing an internal link (i.e. an URL in the same website) to an external link (i.e. an URL in a different website). For simplicity, we only check these links not the actual content these links refer to. If the two hyperlinks are internal and external links, we define their similarity as 0. If both links are internal, the similarity is 1 if they match exactly; otherwise, the similarity is 0. If both links are external, we ignore any directories and only take into account each hyperlink’s subdomains. Each hyperlink is first split into a list, where each element in the list is a subdomain (e.g. www.nasa.gov is split into the list www, nasa, and gov). We then compare each subdomain in the first hyperlink to each subdomain in the second hyperlink starting from the end of each list and moving backwards. At any step, if two subdomains being compared do not match exactly, then we do not proceed further. Let $l_{a}$ be a hyperlink with $| l_{a} |$ subdomains, $l_{b}$ be a hyperlink with $| l_{b} |$ subdomains, and n be the number of subdomains matched. We define the similarity between two hyperlinks $l_{a}$ and $l_{b}$ as

S_{l} (l_{a}, l_{b}) = \frac{n}{\max (| l_{a} |, | l_{b} |)}

(8)

To find the similarity between two lists of hyperlinks, we use the average of the maximum similarity values

S_{L} (L_{a}, L_{b}) = \frac{A_{L} (L_{a}, L_{b}) + A_{L} (L_{b}, L_{a})}{2}

(9)

where $A_{L} (L_{a}, L_{b})$ is the average of the maximum similarity values (equation (8)) for each hyperlink in list $L_{a}$ to any hyperlink in list $L_{b}$ . We normalize all similarity values to $[0, 1]$ and define the distance between $L_{a}$ and $L_{b}$ as $D_{L} (L_{a}, L_{b}) = 1.0 - S_{L} (L_{a}, L_{b})$ .

Graphics processing unit acceleration

Our experiment shows that the bottleneck stages of image distance computation are grayscale image distance ( $D_{G}$ ) and spectrum image distance ( $D_{F}$ ) calculations. It is slow because we need to compute $S_{B}$ (equation (1)) and $P_{B}$ (equation (3)) on a local $8 \times 8$ window, which moves pixel by pixel over the entire image. To speed up the performance, we leverage the graphics processing unit (GPU) to perform distance computation in parallel. Specifically, all the thumbnail images are loaded into the GPU memory to reduce the time cost of fetching each pixel. We assign a large number of blocks and threads in the calculation for efficiency. A straightforward solution allocates N blocks and N threads within each block, where N is the number of images. In this way, each thread only needs to calculate the distance for at most one pair of images. However, this assignment has two drawbacks. First, due to the symmetry of distance matrix, we only need to calculate half of the distance matrix. This leads to an imbalanced workload for different blocks. Second, in our case, the number of images N is larger than the maximum number of threads in one block. This implies that some threads have to calculate for multiple image pairs while others are idle, which results in an imbalanced workload for different threads within a block. As a matter of fact, this straightforward solution also leads to a Compute Unified Device Architecture (CUDA) error CUDA_ERROR_LAUNCH_TIMEOUT, which occurs when a time-consuming computation runs on a graphics card that is used for both graphics rendering and CUDA computation. To avoid this problem, we evenly distribute the number of image pairs to all threads in a round-robin fashion to balance the workload and utilize a second graphics card in our personal computer (PC) for dedicated GPU computation.

Image ranking and clustering

With the overall image distance defined, we build a symmetric distance matrix recording the distance between any two images in the collection. During image search, the user selects a query image, and all other images in the collection are ranked accordingly. The user can change the weights for partial distances to update the distance matrix and search results.

For image clustering, we apply the hierarchical quality threshold algorithm due to its simplicity and efficiency. The algorithm uses a list of distance thresholds with increasing values ${δ_{0}, δ_{1}, δ_{2}, \dots, δ_{l}}$ to create a hierarchy up to $l + 1$ levels ( $δ_{0} = 0$ , $δ_{l} = 1$ ). Initially, each image in the collection is in its own cluster. At the first iteration, we build a candidate cluster for each image I by including all images that have their respective distance to I smaller than $δ_{1}$ . We save the cluster with the largest number of images as the first true cluster and remove all images in this cluster from further consideration. In the true cluster, image I is treated as its representative. We repeat with the reduced set of images until all images are classified. In the following iterations, the input is all representative images gathered from the previous iteration. We continue this process for the following iterations until we finish the lth iteration or until we have only one cluster left in the current iteration.

Image layout and interaction

Once images are ranked, image layout is important as it determines how images should be arranged for viewing. For a large image collection, it is desirable to maintain good visual overview while allowing flexible exploration and detailed examination. An appropriate image layout should fulfill the following criteria:

Stable layout: the layout should accommodate image ordering and maintain stable update when images are inserted or removed during the query.

Screen utilization: for efficiency, the layout should display as many images as users can comfortably view them.

Occlusion minimization: for effectiveness, images displayed should not occlude each other in the layout or their overlap should be minimized.

In-place interaction: the layout itself should also serve as an interface for in-place interaction to attract user attention and facilitate image identification.

iMap

Since most displays and images are in the form of rectangle, we opt to use the rectangular shape for image layout so that the available display area can be best utilized. We propose to use the treemap²³ to visualize a large image collection due to its simplicity and effectiveness. We refer to the treemap-based representation of image collections as the iMap (“i” stands for image). Each node in iMap corresponds to a rectangle that displays an image thumbnail. The sizes of these rectangles can be determined by the importance of their images, such as search rank or hit count.

Layout design

The original “slice-and-dice” treemap layout generates rectangles of arbitrary aspect ratios. Squarified treemaps²⁴ create rectangles with smaller aspect ratios but give up on node ordering. Ordered treemaps²⁵ offer a good trade-off among stable updates, order preserving, and low aspect ratios. Quantum treemaps developed for PhotoMesa²⁶ guarantee that the regions showing groups of photos have dimensions that are integer multiples of the dimensions of the photos (i.e. they must be sized to contain quantum or indivisible contents). Spiral treemaps²⁷ place nodes along the spiral pattern, which guarantees that neither the overall pattern nor the specific node ordering will change drastically as the data evolve over time.

For iMap, we propose a hybrid layout that combines the advantages of both quantum and spiral treemaps: the use of quantum with a fixed aspect ratio simplifies the layout for images of different aspect ratios, and the adoption of spiral pattern maintains stable update when we insert or remove images. The one-dimensional (1D) spiral also accommodates image ordering, such as the chronological order or rank order. Our layout results with image search and clustering are given in Figure 2. To organize clustering results, we apply a two-level layout: the quad-tree layout for different levels of hierarchy and the spiral layout for images within each level. Much as in human vision, we display the focus image at the center of display area (focal point) and arrange less important images in its surrounding (periphery). By default, we display the focus image in normal size and reduce the width and height by half for the successive layers. The user can adjust the number of repetition layers r needed to keep the current width and height. In Figure 2, we set $r = 2$ for image search and $r = 1$ for image clustering.

Figure 2.

iMap with the spiral layout: (a) image search results and (b) hierarchical clustering results.

iMap interaction

The interaction with image search function includes the following: left mouse click for showing the overlay full-resolution image in its original aspect ratio, middle mouse click for showing metadata information, and right mouse click for updating search with respect to the image selected. Each image comes with an ID, and we also store the number of pixels similar to a list of given representative colors. This allows us to enable “search by ID” (selecting an image ID via slider) and “search by color” (picking a representative color via radio button) functions for updating the query image besides “search by image” (directly clicking on an image displayed in iMap). The interaction with image clustering function is the same except that right mouse click on an image is for displaying its next level of images in the hierarchy.

We also implement a focus + context (F + C) function to further improve the readability of iMap as the user mouses over the images. Our F + C approach aims to apply a simple strategy to achieve an acceptable result for a single focus. As shown in Figure 3, in a general case, the expansions of the four edges of the focused image divide the entire space into eight areas. When the focus is enlarged, its edges move accordingly, so do the edges of the eight areas. However, if we simply scale each area to fit into the new layout, the four areas adjacent to the focus, that is, Areas 2, 4, 7, and 5, will suffer from more serious distortion than other areas (Figure 3(b)). Taking Areas 1 and 2 for example, when the focus grows, the horizontal edges of Area 2 will expand, while its vertical edges shrink; but for Area 1, both its horizontal and vertical edges will shrink. Thus, the aspect ratio of Area 2 changes more significantly than that of Area 1. To balance these changes, we group each area adjacent to the focus to the one at the corner, that is, Areas 1 and 2, 3 and 5, 4 and 6, and 7 and 8 will be grouped together. This strategy is similar to the solution proposed by Kustanowitz and Shneiderman²⁸ in their two-level auto-layout technique for photo browsing. Then, we apply the transformation to each group, so that the overall distortion can be reduced (Figure 3(c)). However, for the spiral layout, an image that is larger than the focus might cross three areas, as shown in Figure 3(d). Figure 3(e) shows an example where the current query image at the center crosses Areas 1, 2, and 3. In this case, Areas 1, 2, and 3 must be in one group to ensure that every image is still a rectangle. For other areas, we will group Areas 4 and 6, 5 and 8, respectively, and leave Area 7 ungrouped (since it is the smallest one).

Figure 3.

F + C visualization: (a) selection the focus (denoted as “f”) divides the entire space into eight areas. Edge expansions of the focus through (b) adjusting each area independently or (c) adjusting areas by group. In (d) and (e), one image, shown in the dashed rectangle, crosses three areas.

In our implementation, the focused image will be scaled up to the same size as the centered query image before the deformation. To better preserve the original aspect ratio for the areas out of focus, the center of the focused image might move. Taking the horizontal direction for example, the left and right boundaries of the focused image after deformation are decided in a way such that the left and right remaining areas are squeezed proportionally to their original widths. Once the boundaries of the focused image are determined, we compute the boundaries of each area and uniformly deform the context images within each area.

Integrating text into image search

Building the overall distance matrix that includes the keyword and hyperlink distances for image search implicitly utilizes the textual information. In this case, all keywords or all hyperlinks associated with images must be taken into account. Nevertheless, these keywords or hyperlinks can also be explicitly utilized to customize or refine the search. We present three different ways to explicitly integrate text into image search.

Keyword input

In this mode, the user inputs a keyword into a text widget, and we search and display images that contain such a keyword. The keyword input could be partially or exactly matched with image keywords and/or text explanations in the HTML files. Multiple keywords are allowed with logical operators (OR, AND). Images founded can be ordered by their IDs or other attributes such as hit count. They can also be arranged according to their rank order from the previous image search results.

Embedded text

Both keyword input and tag cloud display text in another widget or window separate from iMap. Another different design is to embed image tags for in-place selection and search, which obviates the need to use a list of words separately. This concept is similar to PhotoMesa,²⁶ a zoomable image browser (in terms of in-place interaction) and scented widgets²⁹ (in terms of improving navigation cues). Zoomable interfaces make navigation straightforward and avoid getting lost. Improving navigation cues lowers the cost structure of seeking and accessing information. We therefore advocate a solution that integrates tag information into iMap for further interaction and embedded search. For the APOD collection, tags are only associated with the image, not specific objects. We thus overlay a layer of tags for user selection and search refinement. Much as in tag clouds, the size, color, or order of tags for an image can be adjusted to provide additional hints such as how many images will match selected tags. The user can select multiple tags to add into the current search.

Results

We collected APOD webpages that contain meta-tagged keywords (since 26 September 1997) till a cut-off date (3 April 2010). Occasionally, APOD runs videos instead of images. In this experiment, we did not consider videos and therefore excluded those webpages from our collection. For images in the Graphics Interchange Format (GIF) though, we extract the first frame as the representative of the entire image sequence. The resulting data set consists of 4560 images with text information including keywords, hyperlinks, and explanations extracted from the HTML files. At preprocessing, we computed five distance matrices ( $D_{G}$ , $D_{F}$ , $D_{H}$ , $D_{K}$ , and $D_{L}$ ) to record the distance for all pairs of images. These distance matrices are used at run time to update the final overall distance. In the following, we present iMap results with screenshots captured from our program.

Image layout

Figure 2 shows iMap layout. For image search, the query image of the International Space Station is displayed at the center of iMap as the focus. Results based on both visual and textual distances are ranked and arranged along the spiral circling out. The effectiveness of image search can be verified by the similar images retrieved and displayed. For image clustering, the user explores the cluster hierarchy by clicking the image of interest, which will be highlighted with a yellow bounding box, and its next level of detail is displayed. By displaying all levels of hierarchy currently explored, we give the user the freedom to jump between nonconsecutive hierarchical levels during the exploration. In Figure 4, we can see that using only visual distance picks up images of similar brownish-yellow colors, while using only textual distance pulls up the ranks for grayscale images related to the Mars. A combination of both visual and textual distances finds a balance in between. In Figure 5, we show that if no other textual search is provided, clustering images with the incorporation of visual distance would be more effective for users to identify images of interest in their exploration. Our current implementation only provides the top-down exploration of the hierarchy; it would be interesting to consider the bottom-up exploration as well. For example, the user can search a leaf image via keyword, and all corresponding intermediate levels in the hierarchy are automatically extracted and displayed.

Figure 4.

iMap showing search results with the use of (a) visual distance only, (b) textual distance only, and (c) a combination of visual and textual distances.

Figure 5.

iMap showing clustering results with the use of (a) visual distance only, (b) textual distance only, and (c) a combination of visual and textual distances.

Figure 6 shows an example of “search by color” where images are ranked according to how much percentages of brown pixels they contain. Compared to the row-and-column layout, the spiral layout effectively highlights top-ranked images while maintaining stable update when the number of image layers changes. We also show the results with different numbers of layers displayed and the effect with F + C visualization. Note that our F + C strategy might result in larger distortion when the focused image is close to the corner. In this case, some divided areas could be small, whose size will change dramatically during the deformation. A more sophisticated F + C visualization for this kind of application remains an open problem. To keep the shape of each image as a rectangle, it will be challenging to minimize the distortion while preserving their relative positions without creating voids. The variation of image size in the spiral layout makes the problem more complicated, since those large images will greatly limit the possible moves we can take. Producing a smooth animated transition of the deformation could be even more difficult.

Figure 6.

Query by color—images are ranked according to their percentages of brown pixels: (a) spiral, 5 layers, 145 images; (b) spiral, 7 layers, 289 images; and (c) row-and-column, 144 images. F + C visualization is shown in (b) where the focused image is expanded and highlighted in the yellow boundary.

Image and text

Figure 7 shows an example of interactive image filtering via keyword input. The user can choose either partial or exact keyword match in the search. Figure 8 shows the use of tag cloud in iMap. Tag clouds organize all keywords in a certain order, and the user can go over pages to identify the keyword of interest. As an option, the frequency count for each keyword may also be displayed. When the user clicks on the keyword, iMap updates the search result and displays all images containing the selected keyword. Figure 9 shows an example where the user first searches images based on the use of visual and textual distances as usual. Upon identifying the images of interest, the user can then turn on the embedded keyword list associated with the query image to refine the search by clicking on a certain keyword. All images that do not contain the selected keyword will be filtered out from the query result, while the rank order from the previous search is utilized to maintain the relative stable update. The embedded search allows users to perform in-place interaction to refine their search results without shifting their focus among different windows, which makes it easy for users to follow and take actions.

Figure 7.

Image search via keyword input. The search results corresponding to keyword(s) (a) “spiral,” (b) “galaxy,” (c) “spiral” OR “galaxy,” and (d) “spiral” AND “galaxy.” There are 222, 461, 474, and 208 images matched from (a) to (d), respectively. The first 145 images, ordered by their dates, are shown in each search.

Figure 8.

iMap and tag cloud: (a) the page of the most frequent keywords, (b) a page of keywords in the alphabetical order, and (c) all images that contain the keyword “sun” are ordered by their IDs and displayed.

Figure 9.

iMap with embedded search: (a) image search results using visual and textual distances and (b and c) the user clicks on the keyword “space shuttle”/“columbia” from the embedded list for result filtering.

Performance

For the APOD data set, the one-time computation of the five distance matrices took days to complete on a single Intel 3.2-GHz central processing unit (CPU). The dominant timing was spent on calculating $D_{G}$ and $D_{F}$ where we computed $S_{B}$ (equation (1)) and $P_{B}$ (equation (3)) on a local $8 \times 8$ window which moves pixel by pixel over the entire image. Leveraging an NVIDIA GeForce GTX 580 graphics card to perform distance computation in parallel for multiple images, we are able to reduce the computation of the three image distance matrices significantly. The configurations and timing results are shown in Table 1. We can see that GPU computation provides about 18×, 24×, and 54× speedup for grayscale image distance, spectrum image distance, and color histogram distance calculations, respectively. The reason that we only allocate 512 threads in the calculation of grayscale image distance is due to its complexity. It requires more local memory and registers than the other two, thus using more threads causes the crash of GPU.

Table 1.

Parameter values and timing results for grayscale image distance, spectrum image distance, and color histogram distance calculations.

Similarity type	Image number	Step size	CPU			GPU
Similarity type	Image number	Step size	Loading time (s)	Computing time (s)	Saving time (s)	Block number	Thread number	Loading time (s)	Computing time (s)	Saving time (s)
Grayscale	4560	$1 \times 1$	1.91	976,200	1.04	16,384	512	0.2194	53,886	0.0338
		$2 \times 2$						0.2906	12,162	0.0098
		$4 \times 4$						0.215	3,015	0.0077
		$8 \times 8$						0.214	762	0.0098
Spectrum	4560	$1 \times 1$	1.52	787,149	2.43	16,384	1024	0.2158	31,944	0.0077
		$2 \times 2$						0.222	7993	0.0071
		$4 \times 4$						0.2138	2017	0.0077
		$8 \times 8$						0.2136	515	0.0015
Histogram	4560	N/A	1.08	176.52	2.6	16,384	1024	0.0021	3.2596	0.0086

CPU: central processing unit; GPU: graphics processing unit.

CPU loading and saving are loading image data from disk and saving the distance matrix to disk. GPU loading and saving are copying the data from main memory and saving the distance matrix to main memory. For GPU computation of grayscale image distance and spectrum image distance, we also report timing with different step sizes for the local $8 \times 8$ window.

This timing performance can be further improved by taking an approximate solution: setting a step size larger than 1 pixel for moving the local window. Table 1 shows the timing with three approximate solutions (with step size of $2 \times 2$ , $4 \times 4$ , and $8 \times 8$ , respectively). The speedup is nearly linear to the reduction rate (i.e. 4×, 16×, and 64× for $2 \times 2$ , $4 \times 4$ , and $8 \times 8$ , respectively). When using the step size of $8 \times 8$ (in this case, the local sliding window does not overlap each other), the total GPU computation time for generating the three image distance matrices is reduced to less than 30 min, which is quite affordable. In Figure 10, we show that these approximate solutions do not lead to dramatic changes of image search results. All five distances (three image distances and two textual distances) take an equal weight in the final distance measure. We can see that there are changes of ranking for the similar images with respect to the query image as we adjust the step size for the local window, but compared with the ground truth, the overall approximate results are fairly good even with a large step size of $8 \times 8$ . In fact, for results with these three step sizes shown in Figure 10, 99.76% ( $2 \times 2$ ), 99.52% ( $4 \times 4$ ), and 99.04% ( $8 \times 8$ ) of images are the same as the images shown in Figure 2. At run time, only the clustering step takes a few minutes to complete. All other tasks and interactions are interactive.

Figure 10.

Comparing the search results with different step sizes for the local $8 \times 8$ window used in computing grayscale image distance and spectrum image distance. Search results with step size of (a) $2 \times 2$ , (b) $4 \times 4$ , and (c) $8 \times 8$ . The ground truth search results are shown in Figure 2.

Comparison with force-directed layout

We compare our iMap layout with a force-directed layout in terms of screen utilization and overlap reduction. We apply the Fruchterman–Reingold algorithm³⁰ to draw an initial force-directed graph layout due to its popularity and simplicity. For the initial layout, we use images retrieved from the same query using iMap as the input for nodes. As we know, iMap produces no image overlapping and could fully utilize the display area. This would not be possible for the force-directed layout. For meaningful comparisons, we have to either reduce the number of images displayed or proportionally scale down the size of each image (the images with the smallest size may remain unchanged for easy readability). To reduce image overlap while maintaining the relative positions among different images, we apply a triangulation scheme³¹ to the initial layout and use the resulting mesh to perform constrained layout adjustment. Similar to the algorithms described by Cui et al.,³² we consider four kinds of forces to reposition the nodes to reduce their overlap while maintaining the topology of the layout:

Bidirectional repulsive force. This force pushes away two nodes $v_{a}$ and $v_{b}$ from each other and is effective if and only if $v_{a}$ and $v_{b}$ overlap each other. The bidirectional repulsive force is defined as $f_{1} (v_{a}, v_{b}) = k_{1} \times \min (x, y)$ , where $k_{1}$ is a given weight and x and y are the width and height of the overlapping region, respectively, as shown in Figure 11(a). This force is applied to every pair of nodes in the layout.

Unidirectional repulsive force. This force pushes away a node $v_{b}$ from a node $v_{a}$ and is effective if and only if $v_{b}$ is inside $v_{a}$ . The unidirectional repulsive force is defined as $f_{2} (v_{a}, v_{b}) = k_{2} \times \min (x, y)$ , where $k_{2}$ is a given weight and x and y are the width and height of the gap region, respectively, as shown in Figure 11(b). Once this force pushes $v_{b}$ away from $v_{a}$ and they become overlapping, the previous bidirectional repulsive force will be effective in subsequent iterations to move them further apart.

Spring force. This force is used to balance the graph by offsetting the two repulsive forces introduced. Given two nodes $v_{a}$ and $v_{b}$ , the spring force is defined as $f_{3} (v_{a}, v_{b}) = k_{3} \times l$ , where $k_{3}$ is a given weight and l is the length of the line segment connecting the centers of $v_{a}$ and $v_{b}$ that lies outside of their boundaries as shown in Figure 11(c). This force is applied to every pair of nodes in the graph.

Attractive force. This force is used to maintain the underlying triangle mesh we construct for the graph. During the layout adjustment, if a mesh triangle is flipped, as shown in Figure 11(d), then the topology of the triangle mesh changes. Our goal is to maintain a stable update of the graph by introducing an attractive force to flip the triangle back. The attractive force is defined as $f_{4} (v) = k_{4} \times t$ , where $k_{4}$ is a given weight and t is the distance from node v to edge e. We also consider virtual triangle edges connecting extreme nodes in the graph to the four corners of the drawing area. This is to ensure that all graph nodes do not go out of bound.

Figure 11.

The four different forces we consider for the force-directed layout adjustment for overlap reduction and topology maintenance: (a) bidirectional repulsive force, (b) unidirectional repulsive force, (c) spring force, and (d) attractive force.

Figures 12 and 13 show two examples of the force-directed layouts based on Figure 6(a) (five layers, 145 images) and Figure 2(a) (seven layers, 417 images), respectively. We compute the amount of image overlap (in pixels) and derive the percentage of image overlapping as follows

o = \frac{\sum_{i \in N, j \in N, i < j} A_{i} \cap A_{j}}{A}

(10)

where $A_{i} \cap A_{j}$ is the number of pixels overlapped by images i and j, N is the total number of images in the layout, and A is the number of pixels in the entire display area. The percentage of screen utilization is computed as $u = \bar{A} / A$ , where $\bar{A}$ is the number of pixels that are occupied by at least one image in the layout.

Figure 12.

Force-directed layouts based on the iMap result shown in Figure 6(a). (a) The initial force-directed layout, (b) the force-directed layout after overlap reduction, and (c) quad drawing showing the actual overlap in (b). First row: scaling down the images so that the summation of all image sizes accounts for 75% of the display area as the input ( $o = 14.00 %$ , $u = 66.39 %$ ). Second row: removing the last layer of images from the iMap result as the input ( $o = 20.46 %$ , $u = 65.00 %$ ).

Figure 13.

Force-directed layouts based on the iMap result shown in the Figure 2(a). (a) The initial force-directed layout, (b) the force-directed layout after overlap reduction, and (c) quad drawing showing the actual overlap in (b). First row: scaling down the images so that the summation of all image sizes accounts for 75% of the display area as the input ( $o = 11.08 %$ , $u = 68.46 %$ ). Second row: removing the last layer of images from the iMap result as the input ( $o = 19.84 %$ , $u = 75.45 %$ ).

In Figure 12, we either reduce the number of images from 145 to 85 images by removing the outermost layer of the iMap result or proportionally scale down the size of each image (except the last two layers) so that the summation of all image sizes accounts for 75% of the display area. After applying overlap reduction, the force-directed layout still has 14%–20% image overlap with about one-third of pixels not utilized. These numbers improve slightly with seven layers of images in Figure 13. As a comparison, the iMap layout has zero image overlap while all pixels are utilized. Besides this major advantage, we find that the iMap layout is clearer as we only consider the similarity between the query image and each of the other images in the layout. In contrast, the force-directed layout considers the similarity between all pairs of images in the layout.

Deployment of iMap to tiled display

To transform iMap into a tool for astronomy education, we deploy our system to a large tiled display at Michigan Technological University’s Immersive Visualization Studio. The tiled display consists of $6 \times 4$ thin-bezel 46-in Samsung monitors, each with $1920 \times 1080$ pixels. These 24 monitors are driven by eight computing nodes for computation and visualization, and each node connects to three monitors. In total, the tiled display can display nearly 50 million pixels simultaneously. In order to forward the iMap window from the local desktop’s monitor to the tiled display wall, we leverage the open-source libraries such as Chromium,³³ a system for interactive rendering on clusters of workstations. Chromium provides a number of key features for large tiled display wall rendering. For example, it can synchronize parallel graphics commands to implement various parallel rendering techniques. It can also aggregate the output of multiple graphics cards to form a single display with higher performance. Furthermore, since Chromium streams the graphics pipeline based on the industry standard OpenGL API, it is transparent to the programmers and allows many OpenGL programs to run without modification. By specifying the hardware configuration into the Chromium configuration file, users can easily set up Chromium and fit it into their own tiled display architecture.

Some photo results showing the running of iMap on the tiled display are shown in Figure 14. Currently, we are using this facility for showing iMap demos to visitors and teaching middle and high school students through Michigan Technological University’s Youth Programs. Initial feedback from several groups of visitor is fairly positive as they comment that running iMap on this life-size tiled display is much more expressive and fun to watch compared with on a regular desktop display. The advantage of using the display wall is that it allows more than a dozen of people to comfortably view and discuss the results together in such a collaborative environment. Nevertheless, with the dramatic expanding of display area, it takes more effort for a viewer to correlate and compare images that are on the opposite sides of the display wall, especially for those small images close to the wall’s boundary.

Figure 14.

iMap shown on the 24-monitor tiled display that can display nearly 50 million pixels simultaneously.

User study

We performed a user study to evaluate the effectiveness of iMap by comparing it with the existing image search functions (archive, index, and text search) provided by online APOD. A desktop version of iMap was used in the study, running on a 27-in monitor with $1920 \times 1080$ screen resolution. We used a design of 2 conditions (iMap vs online APOD) × 3 tasks (text, image, and image + text). We assigned a target image for each of the six combinations except for Task 1, where users were asked to identify two images with very different numbers of images retrieved. Therefore, a total of eight images were selected. These images cover different topics: astronaut, aurora, black hole, Earth, Jupiter, Mars, Moon, and Sun.

Hypotheses

We postulated four hypotheses for the study. Since the users’ respond time varies for each task, hypotheses about response time of search under both conditions will be considered based on different tasks. Furthermore, we only considered the overall accuracy due to the high probability of finding the exact image.

Hypothesis 1. Given the keywords and description only (Task 1), iMap is faster to search than online APOD.

Hypothesis 2. Given the image only (Task 2), iMap is faster to search than online APOD.

Hypothesis 3. Given the image and keywords (Task 3), iMap is faster to search than online APOD.

Hypothesis 4. Overall, for image search, using iMap makes fewer errors than online APOD.

Interactions

Detailed interactions with iMap are described in section “Image layout and interaction.” For online APOD, three search modes are provided: archive, index, and text search. The archive mode provides the dates and titles of all images and arranges them in the reverse chronological order. The index mode offers various keywords organized by category. Clicking on any keyword shows keyword-related thumbnail images with their dates, titles, and short explanations. The text search mode provides OR or AND search for multiple keywords. Since the way to search online APOD is similar to other websites, we assume that all users are familiar with it.

Tasks and procedure

Three tasks were implemented to compare the performance of iMap and online APOD. In each task, users were asked to identify the three most related or similar images. Ideally, the exact image should be found, and if not, they were asked to find up to three most related ones.

Task 1. Text search: given a short text description and several recommended keywords, users were asked to find the three most related images. Two images will be tested for each condition, one search generated a large number of retrieved images while the other generated a small number.

Task 2. Image search: given target images without any keyword or description, users were asked to find the three most similar images. We assumed that the users could figure out the content of the images with their very basic astronomy knowledge.

Task 3. Image + text search: given target images with several keywords, users were asked to find the three most similar images.

For iMap, there was a 15-min training session and a further 5-min free exploration time (practice search) preceding the actual tasks. This was the same for online APOD, except that there was no training. A post-test survey for user preference and comments was conducted immediately after a user finished all the tests. A total of 16 users (8 graduate and 8 undergraduate students) participated in this study, and each user used both iMap and online APOD. Users were required to finish tasks in the order given. Users recorded the date of images they selected, and we helped them record the starting and ending time for completing each task. Each user was asked to perform 8 trials, and therefore, we had a total of 128 (16 × 8) trials. Each experiment was conducted individually and took approximately 40 min, including the training, practice task, experimental tasks for both conditions, and questionnaire.

Results and discussion

We present results from the study in three aspects: completion time, accuracy, and subjective preferences. A paired t-test with a standard significance level of $α = 0.05$ was performed to determine statistical significance between the two conditions.

Completion time

Figure 15(a) shows the mean response time results when comparing iMap to online APOD for each task.

For Task 1, iMap was significantly faster than online APOD with only keywords given and a large number of images retrieved (iMap: 82.39 s, online APOD: 215.36 s; $p = 0.007$ ). This is because iMap provides a good overview of the image collection to facilitate the visual search. However, no significant difference was found with only keywords given and a small number of images retrieved. Possible reasons include the following: the text descriptions were confusing to some users; users were more proficient for online search, while it took time for them to adjust to using iMap; and users needed to switch among multiple views or tabs in iMap, while there was only one view in online APOD.

For Task 2, iMap was significantly faster than online APOD with only images given (iMap: 38.86 s, online APOD: 72.29 s; $p = 0.0127$ ). Two reasons explain this. First, using online APOD, users were able to scroll up and down the result page to view about 10 images at a time, while they could view hundreds of images simultaneously using iMap. Second, neighboring images in iMap are similar, while neighboring images have no connection at online APOD.

For Task 3, no significant difference in response time was found with keywords and images given. Since the images we selected for this task got a very small number of images retrieved (10–20 images), it was easy for users to search under both conditions.

Figure 15.

Comparing iMap to online APOD: (a) mean response time by task, (b) mean error rate, (c) mean overall rating, and (d) mean rating by statement. The four statements are (S1) it was enjoyable to use, (S2) it was easy to search images with only keywords given, (S3) it was easy to search images with only images given, and (S4) it was easy to search images with keywords and images given.

Therefore, Hypothesis 1 was fully supported when the number of images retrieved is large. Hypothesis 2 was also fully supported, while Hypotheses 3 was not supported.

Accuracy

Since almost all users were able to find the exact image correctly, we compute the error as the number of failed trials (i.e. image misidentified) over the number of total trials. With online APOD, 4.69% (6 out of 128) tests failed, and with iMap, 1.56% (2 out of 128) tests failed. Figure 15(b) shows the average error results when comparing iMap and online APOD. In terms of accuracy, iMap was not distinguishable from online APOD, which contradicts Hypothesis 4. We found that almost every user could find the exact image under both conditions.

Subjective preferences

The 16 users completed a survey after their experiment. They were asked which condition they preferred overall and which interface they perceived to be more useful for each of the three tasks. Four statements were provided as follows:

Statement 1.“It was enjoyable to use.”

Statement 2.“It was easy to search images with only keywords given.”

Statement 3.“It was easy to search images with only images given.”

Statement 4.“It was easy to search images with keywords and images given.”

Each statement was answered with a 5-point scale (1 = strongly disagree, 5 = strongly agree). We ran a paired t-test with a standard significance level of $α = 0.05$ and found a significant effect for iMap.

Figure 15(c) shows the mean overall rating when comparing iMap to online APOD. The rating for iMap is significantly higher than online APOD (iMap: 3.89, online APOD: 2.89; $p = 0.039$ ), which indicates that the users prefer using iMap over online APOD.

Figure 15(d) shows the mean rating when comparing iMap to online APOD for the following four statements:

For Statement 1, iMap was judged to be more enjoyable to use (iMap: 4.19, online APOD: 2.94; $p = 0.0017$ ).

For Statement 2, iMap was not significantly easier to search images with only keywords given (iMap: 2.94, online APOD: 2.56; $p = 0.5544$ ).

For Statement 3, iMap was significantly easier to search images with only images given (iMap: 4.06, online APOD: 2.634; $p = 0.0001$ ).

For Statement 4, iMap was significantly easier to search images with keywords and images given (iMap: 4.38, online APOD: 3.44; $p = 0.0098$ ).

Conclusion and future work

We have presented iMap, an analysis and visualization framework that supports effective searching, browsing, and understanding of large image collections. iMap strikes a good balance among simplicity, intuitiveness, and effectiveness by addressing issues such as stable layout, screen utilization, and in-place interaction. Our user study confirms that iMap provides a more effective solution for image search, ranking, and identification compared with traditional archive and keyword search methods. While the layout itself will work for other image collections beyond APOD, we would improve our image distance measure by considering image aesthetics measures, high-level image features, and relationships between words so that the similarity ranking would be applicable to other image collections as well. In the future, we will also develop a web version of iMap for APOD so that any users can easily access our system online.

Footnotes

Acknowledgements

All the images at the APOD website are credited to the owners or institutions where they originated.

Funding

This work was supported in part by the U.S. National Science Foundation [IIS-1017935, CNS-1229297].

References

Nemiroff

Bonnell

. Astronomy Picture of the Day. In: Bulletin of the American Astronomical Society, 1995, p. 1291, http://antwrp.gsfc.nasa.gov/apod/astropix.html

Swain

Ballard

. Color indexing. Int J Comput Vision 1991; 7(1): 11–32.

Rodden

Basalaj

Sinclair

. Evaluating a visualisation of image similarity as a tool for image browsing. In: Proceedings of IEEE symposium on information visualization, San Francisco, CA, 24–29 October 1999, pp. 36–43. Los Alamitos, CA: IEEE.

Rodden

Basalaj

Sinclair

. Does organisation by similarity assist image browsing? In: Proceedings of ACM SIGCHI conference, Seattle, WA, 31 March–4 April 2001, pp. 190–197. New York: ACM.

Manjunath

. Texture features for browsing and retrieval of image data. IEEE T Pattern Anal 1996; 18(8): 837–842.

Bimbo

Pala

. Visual image retrieval by elastic matching of user sketches. IEEE T Pattern Anal 1997; 19(2): 121–132.

Mikolajczyk

Schmid

. Scale and affine invariant interest point detectors. Int J Comput Vision 2004; 60(1): 63–86.

Kennedy

Naaman

. Generating diverse and representative image search results for landmarks. In: Proceedings of international conference on World Wide Web, Beijing, China, 21–25 April 2008, pp. 297–306. New York: ACM.

Datta

Joshi

. Image retrieval: ideas, influences, and trends of the new age. ACM Comput Surv 2008; 40(2): 5:1–5:60.

10.

Chen

Gagaudakis

Rosin

. Content-based image visualization. In: Proceedings of international conference on information visualisation, London, UK, 19–21 July 2000, pp. 13–18. Los Alamitos, CA: IEEE.

11.

Torres

Silva

Medeiros

. Visual structures for image browsing. In: Proceedings of international conference on information and knowledge management, New Orleans, LA, 3–8 November 2003, pp. 49–55. New York: ACM.

12.

Yang

Fan

Hubball

. Semantic image browser: bridging information visualization with automated intelligent image analysis. In: Proceedings of IEEE symposium on visual analytics science and technology, Baltimore, MD, 31 October–2 November 2006, pp. 191–198. Los Alamitos, CA: IEEE.

13.

Gomi

Miyazaki

Itoh

. CAT: a hierarchical image browser using a rectangle packing technique. In: Proceedings of international conference on information visualisation, London, UK, 9–11 July 2008, pp. 82–87. Los Alamitos, CA: IEEE.

14.

Brivio

Tarini

Cignoni

. Browsing large image datasets through Voronoi diagrams. IEEE T Vis Comput Gr 2010; 16(6): 1261–1270.

15.

Tan

Song

Liu

. ImageHive: interactive content-aware image summarization. IEEE Comput Graph 2012; 32(1): 46–55.

16.

Harada

Naaman

Song

. Lost in memories: interacting with large photo collections on PDAs. In: Proceedings of ACM/IEEE-CS joint conference on digital libraries, Tucson, AZ, 7–11 June 2004, pp. 325–333. New York: ACM.

17.

Huynh

Drucker

Baudisch

. Time quilt: scaling up zoomable photo browsers for large, unstructured photo collections. In: Proceedings of ACM CHI extended abstracts, Portland, OR, 2–7 April 2005, pp. 1937–1940. New York: ACM.

18.

Marks

Andalman

Beardsley

. Design galleries: a general approach to setting parameters for computer graphics and animation. In: Proceedings of ACM SIGGRAPH conference, Los Angeles, CA, 3–8 August 1997, pp. 389–400. New York: ACM.

19.

Cooper

De Bruijn

Spence

. A comparison of static and moving presentation modes for image collections. In: Proceedings of international working conference on advanced visual interfaces, Venezia, Italy, 23–26 May 2006, pp. 381–388. New York: ACM.

20.

Wang

Bovik

Sheikh

. Image quality assessment: from error visibility to structural similarity. IEEE T Image Process 2004; 13(4): 600–612.

21.

Lewis

. Naïve (Bayes) at forty: the independence assumption in information retrieval. In: Proceedings of European conference on machine learning, Chemnitz, Germany, 21–23 April 1998, pp. 4–15. London: Springer-Verlag.

22.

Hatzivassiloglou

Klavans

Eskin

. Detecting text similarity over short passages: exploring linguistic feature combinations via machine learning. In: Proceedings of joint SIGDAT conference on empirical methods in natural language processing and very large corpora, College Park, MD, 21-22 June 1999, pp. 203–212. New Brunswick, NJ: ACL.

23.

Shneiderman

. Tree visualization with tree-maps: a 2D space-filling approach. ACM T Graphic 1992; 11(1): 92–99.

24.

Bruls

Huizing

Van Wijk

. Squarified treemaps. In: Eurographics/IEEE TCVG symposium on visualization, Vienna, Austria, 26-28 May 1999, pp. 33–42. Oxford, UK: Blackwell.

25.

Shneiderman

Wattenberg

. Ordered treemap layouts. In: IEEE symposium on information visualization, San Diego, CA, 22–23 October 2001, pp. 73–78. Los Alamitos, CA: IEEE.

26.

Bederson

. PhotoMesa: a zoomable image browser using quantum treemaps and bubblemaps. In: Proceedings of ACM symposium on user interface and software technology, Orlando, FL, 11–14 November 2001, pp. 71–80. New York: ACM.

27.

Shen

. Visualizing changes of hierarchical data using treemaps. IEEE T Vis Comput Gr 2007; 13(6): 1286–1293.

28.

Kustanowitz

Shneiderman

. Hierarchical layouts for photo libraries. IEEE Multimedia 2006; 13(4): 62–72.

29.

Willett

Heer

Agrawala

. Scented widgets: improving navigation cues with embedded visualizations. IEEE T Vis Comput Gr 2007; 13(6): 1129–1136.

30.

Fruchterman

TMJ

Reingold

. Graph drawing by force-directed placement. Software Pract Exper 1991; 21(11): 1129–1164.

31.

Shewchuk

. Triangle: engineering a 2D quality mesh generator and Delaunay triangulator. In: Proceedings of ACM workshop on applied computational geometry, Philadelphia, PA, 27–28 May 1996, pp. 203–222. Berlin: Springer-Verlag.

32.

Cui

Liu

. Context preserving dynamic word cloud visualization. In: Proceedings of IEEE Pacific visualization symposium, Taipei, Taiwan, 2–5 March 2010, pp. 121–128. Los Alamitos, CA: IEEE.

33.

Chromium. http://chromium.sourceforge.net/