Content-based visualization and user-modeling for interactive browsing and retrieval in multimedia databases

[0002] This invention relates generally to computer-based systems which provide access to multimedia databases, and more particularly to systems that visualize multimedia objects according to media characteristics.

[0003] Traditional browsing and navigating in a large multimedia database, for example, image, video, or audio databases, is often disorienting unless a user can form a mental picture of the entire database. Content-based visualization can provide an efficient approach for browsing and navigating multimedia databases.

[0004] Many browsing and retrieval systems are feature based. For example, color, texture and structure for images, color and motion for videos, ceptrum, pitch, zero crossing rate, and temporal trajectories for audio. Color is one of the most widely used features for content-based image/video analysis. It is relatively robust to background complication and independent of image size and orientation. Color histograms are the most commonly used color feature representation. While histograms are useful because they are relatively insensitive to position and orientation changes, they do not capture spatial relationship of color regions, and thus, color histograms have limited discriminating power.

[0005] One can also use color moments. There, the color distribution of an image is interpreted as a probability distribution, and the color distribution can be uniquely characterized by its moments. Characterizing a 1-D color distribution with the first three moments of color is more robust and more efficient than working with color histograms.

[0006] Texture refers to the visual pattern with properties of homogeneity that do not result from the presence of a single color or intensity. Texture contains important information about the arrangement of surfaces and the relationship of the surfaces to the surrounding environment. Texture can be represented by wavelets by processing an image into a wavelet filter bank to decompose the image into wavelet levels having a number of bands. Each band captures the feature of some scale and orientation of the original image. For each band, the standard deviation of wavelet coefficients can be extracted.

[0007] Structure is a more general feature than texture and shape. Structure captures information such as rough object size, structural complexity, loops in edges, etc. Structure does not require an uniform texture region, nor a closed shape contour. Edge-based structure features can be extracted by a so-called “water-filling algorithm,” see X. Zhou, Y. Rui and T. S. Huang, “Water-filling algorithm: A novel way for image feature extraction based on edge maps,”in Proc. IEEE Intl. Conf. On Image Proc., Japan, 1999, and X. S. Zhou and T. S. Huang, “Edge-based structural feature for content-based image retrieval,”Pattern Recognition Letters, Vol 22/5, April 2001. pp. 457-468.

[0008] The invention visualizes multimedia objects, such as multiple images, on an output devices based on media features such as color, texture, structure, audio ceptrum, textual semantics, or any combination thereof. The vizualization can use the actual objects, or visual icons representing the objects. The resulting arrangement of multimedia objects automatically clusters objects having similar features. An original high-dimensional feature space is reduced to display space, i.e., locations having coordinates x and y, by principle component analysis (PCA).

[0009] Furthermore, the invention provides a process that optimizes the display by maximizing visibility, while minimizing deviation from the original locations of the objects. Given the original PCA-based visualization, the constrained non-linear optimization process adjust the location and size of the multimedia objects in order to minimize overlap while maintaining fidelity to the original locations of the objects which are indicative of mutual similarities. Furthermore, the appearance of specific objects in the display can be enhanced using a relevancy score.

[0010] More particularly, the invention provides a method for visualizing image objects. The method assigns a feature vector to each image. The feature vector of each image is reduced to a location vector having a dimensionality of a display device. A cost function is evaluated to determine an optimal location vector for each image, and each image is displayed on a display device according to the optimal location vector. The reducing can use principle component analysis.

[0011] FIG. 1 is a block diagram of a method for visualizing multimedia objects according to the invention;

[0012] FIG. 2 is a graph of a cost function of overlap; and

[0013] FIG. 3 is a graph of a cost function of deviation:

[0014] As shown in FIG. 1, our invention provides a method and system 100 for optimally visualizing multimedia objects, e.g., digital images, videos, or audio programs 101 on a two or three dimensional output device 150. Our visualization is based on features 111 extracted from or associated with the multimedia object 101. The features can include vision, audio, and semantic features, depending on the content of the multimedia. Our invention augments a user's perception of a multitude of multimedia objects in order to provide information that cannot be perceived by traditional browsing methods, where objects are usually displayed either randomly, or as a regular pattern of tiles.

[0015] We first extract features from the digital multimedia objects 101 stored in a multimedia database 102 using multimedia analysis 110 to produce a feature vector 111 for each object 101. For image objects, we use the HSV color space due to its de-correlated and uniform coordinates. Therefore, a nine-dimensional color feature vector, i.e., three moments for each color, is extracted from every image in the database. Texture and structure features are respectively represented by ten wavelet moments and eighteen water-filling features. As stated above, each feature vector can also be audio features, or semantic features, or any combinations of these features.

[0016] Consequently, the dimensionality of the feature vectors 111 for the multimedia can be very large, e.g., hundreds or more. Therefore, we use principle component analysis (PCA) 120 to reduce the dimensionality of the feature vectors 111. PCA is a very fast linear transformation that achieves the maximum distance preservation when projecting from high to low dimensional feature spaces. We project the feature vectors 111 to either 2D or 3D space depending on the display device 150. This projection is applied to each feature vectors 111 to produce a corresponding two or three dimensional location 121 for each multimedia object. For example, each location 121 has (x, y), (x, y, z), (ρ, θ) or (ρ, θ, φ) coordinates. The mutual distance between object locations respects their feature similarity, thus clustering displayed objects or icons representing the objects 151 according to their features, see U.S. patent application Ser. No. 09/651,002 “Multi-User Interactive Picture Presentation System and Method,” Filed by Shen et al. on Aug. 29, 2000, incorporated herein by reference.

[0017] However, if many of the objects 101 are similar in terms of their features, then it is expected that there will be a considerable amount of overlap in the visualized objects or icons because the values of the coordinates of the reduced dimensional vectors 121 will be close to each other. This will make it difficult for the user to discern all of the objects at once. It is desired to maximize visibility. This can be done by moving the objects apart, and reducing the size of the objects or icons. However, we want to maximize visibility, while minimizing deviation from the original layout, while at the same time not have the objects so small that they become indiscernible.

[0018] Optimizing Lay-Out of Display

[0019] Therefore, we provide a technique 130 that optimally displays the objects 101. We optimize 130 the location and sizes of the objects 101 using a non-linear cost function J. A number of factors are taken into consideration while minimizing the cost function J. The visibility (minimum overlap) among objects on the display device 130 is made as large as possible. The total deviation from the original location 121 on the display device 150 is at the same time made as small as possible. Furthermore, the location of each object must be on the display device, and the size of each object must be greater than a minimum size threshold. To maximize the total visibility, the objects are moved away from each other.

[0020] However, this increases the deviation of the objects from the original locations. Large deviations from the original location are undesirable when the original location of each object is important. Without increasing the total deviation, the object size can be reduced. Of course, the object size cannot be arbitrary small. Because increasing the object size will increase the amount of overlap, the initial object size is assumed to be the maximum size.

[0021] Therefore, our cost function J uses the following parameters. The number of objects that are optimized minimized is N. The original location 121 of each object i is denoted by, e.g., for a 2D display, by {x_i⁰, y_i⁰}, for i=1, . . . , N. Optimized locations 131 of the objects are denoted by {x_i, y_i}, for i=1, . . . , N. The maximum and minimum coordinates of the display device are [x_min, x_max, y_min, y_max]. For simplicity, the radius of each objects is r_i, for i=1, . . . , N. The maximum and minimum object size, in terms of radius, are r_maxand r_minin radius. The original object size is r_i=r_max, for i=1, . . . , N.

[0022] The cost function J that optimizes the visualization is a linear combination of two individual cost functions that take into account the factor mentioned above.

[0023] J=F(p)+λ·S·G(p)  (1)

[0024] where F(p) is a cost function of total visibility, and G(p) is a cost function of the total deviation from the original location of the objects. In order to maximize the total visibility, the total amount of overlap of the objects is minimized. The value S is a scaling factor which brings the range of the cost function G(p) to the same range of the cost function F(p), and λ is a weight, i.e., λ≧0. When λ is 0, the deviation of the objects is not considered in visibility maximization. When λ is 1, the cost functions of visibility and deviation are equally weighted. When 0<λ<1, the minimization maximization of visibility is more important than the minimization of deviation, and vice versa for λ>1.

[0025] The cost function F(p) of total visibility is $\begin{array}{cc}F\left(p\right)=\sum _{i=1}^N\sum _{j=i+1}^{N}f\left(p\right),& \left(2\right)\\ \text{where}f\left(p\right)=\{\begin{array}{cc}1-e^{-\frac{u^2}{{\sigma }_f}}& u>0\\ 0& u\le 0\end{array},\text{and}\text{where}u=r_i+r_j-\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}.& \left(3\right)\end{array}$

[0026] When u≦0, there is no overlap between the jth object and the ith object, and the cost is 0. When u>0, there is partial overlap between the ith object and the jth object. When u=2·r_max, the ith object totally obscures the jth object.

[0027] FIG. 2 graphs the cost function a function of u. It is clear that with the increasing value of u (u>0), the cost of overlap is also increasing. The value σ_fin equation (3) can be determined by setting T=0.95 201 when u=r_max202, that is $\begin{array}{cc}{\sigma }_f=\frac{-u^2}{\ln \left(1-T\right)}{\mid }_{u=r_{\max }}.& \left(4\right)\end{array}$

[0028] The cost function of total deviation is $\begin{array}{cc}G\left(p\right)=\sum _{i=1}^{N}g\left(p\right)& \left(5\right)\\ g\left(p\right)=1-e^{-\frac{v^2}{{\sigma }_g}}& \left(6\right)\end{array}$

[0029] where ν={square root over ((x_i−x_i⁰)²+(y_i−y_i⁰)²)} is the deviation of the ith object at the optimized location (x_i, y_i) 131 from the ith object at the original locations (x_i⁰, y_i⁰) 111.

[0030] FIG. 3 graphs the cost function g(p) 300 as a function of deviation. It is clear that with the increasing value of ν, the cost of deviation is also increasing. The value σ_gin equation (6) is determined by setting T=0.95 301 when ν=maxsep. The value maxsep 302 can be set to 2·r_max. Thus, the value σ_gis $\begin{array}{cc}{\sigma }_g=\frac{-v^2}{\ln \left(1-T\right)}{\mid }_{v=2·r_{\max }}& \left(7\right)\end{array}$

[0031] The value S in equation (1) is selected chosen to be (N−1)/2.

[0032] User Preference Clustering

[0033] In an optional step 160, we can also display the objects 101 according to a preferred arrangement selected by a user of our invention. Here, the user 153 initially places a small number of objects at preferred locations 161 on the display device 151. For example, the user places four objects at four separate arbitrary locations, e.g., objects with people, buildings, seascapes, and landscapes. More objects can be placed when the objects contain a mix of features, for example, people in front of buildings, or people on a lake or sea shore.

[0034] Given the preferred locations 161 of the user selected objects, we now place additional objects 101 on the display device 150 according to the user specified clustering.

[0035] We do this by determining a relative “feature” distance between the preferred clusters of objects. As stated above, a cluster can be as small as one object, although larger clusters will give a better result. The relative distance is expressed in terms of a weighting vector α 162. The features in the weighting vector α are identical to those in the feature vectors 111, although the weighting vector can have fewer features, for example, only visual features, or only visual and semantic feature, for example. We then apply 170 the weighting vector α 162 to each feature vector 111 before the PCA. This, surprisingly, will “skew” the optimized clustering towards the.

[0036] Determining the Weighting Vector α

[0037] We describe the estimation of α for visual feature only, e.g. color, texture, and structure, although it should be understood that any of the features 111 can be factored into α.

[0038] In this case, the weighting vector 162 is α={α_c,α_t,α_s}^T, where α_cis the weight for color, α_tis the weight for texture, and α_sis the weight for structure. The number of objects in the preferred clustering is N, and X_cis a L_c×N matrix where the ith column is the color feature vector of the ith object, i=1, . . . , N, X_tis the L_t×N matrix, the ith column is the texture feature vector of the ith object, i=1, . . . , N, and X_sis the L_s×N matrix, the ith column is the structure feature vector of the ith object, i=1, . . . , N. The lengths of color, texture and structure features are L_c, L_t, and L_srespectively. The distance, for example Euclidean or Hamming, between the ith object and the jth object, for i, j=1, . . . , N, in the preferred clustering is d_ij.

[0039] We set the sum of α_c, α_t, α_sto 1, and define the best “fit” measure to be minimized as a constraint least square optimization problem where p=2. $\begin{array}{cc}J=\sum _{i=1}^N\stackrel{N}{\sum _{j=1}}{\left(d_{\mathrm{ij}}^p-\sum _{k=1}^{L_c}{\alpha }_c^p{\left|X_{c\left(i\right)}^{\left(k\right)}-X_{c\left(j\right)}^{\left(k\right)}\right|}^p-\sum _{k=1}^{L_t}{\alpha }_t^p{\left|X_{t\left(i\right)}^{\left(k\right)}-X_{t\left(j\right)}^{\left(k\right)}\right|}^p-\sum _{k=1}^{L_s}{\alpha }_s^p{\left|X_{s\left(i\right)}^{\left(k\right)}-X_{s\left(j\right)}^{\left(k\right)}\right|}^p\right)}^2\mathrm{Let}& \left(8\right)\\ V_{\left(\mathrm{ij}\right)}^c=\sum _{k=1}^{L_c}{\left|X_{c\left(i\right)}^{\left(k\right)}-X_{t\left(j\right)}^{\left(k\right)}\right|}^p& \left(9\right)\\ V_{\left(\mathrm{ij}\right)}^t=\sum _{k=1}^{L_t}{\left|X_{t\left(i\right)}^{\left(k\right)}-X_{t\left(j\right)}^{\left(k\right)}\right|}^p& \left(10\right)\\ V_{\left(\mathrm{ij}\right)}^s=\sum _{k=1}^{L_s}{\left|X_{s\left(i\right)}^{\left(k\right)}-X_{s\left(j\right)}^{\left(k\right)}\right|}^p& \left(11\right)\end{array}$

[0040] and simplify to: $\begin{array}{cc}J=\sum _{i=1}^N\sum _{j=1}^N{\left(d_{\mathrm{ij}}^p-{\alpha }_c^p{V}_{\left(\mathrm{ij}\right)}^c-{\alpha }_t^p{V}_{\left(\mathrm{ij}\right)}^t-{\alpha }_s^p{V}_{\left(\mathrm{ij}\right)}^s\right)}^2& \left(12\right)\end{array}$

[0041] To minimize J, we take the partial derivatives of J relative to α_c^p, α_t^p, α_s^pand set the partials to zero, respectively.

[0042] We set $\begin{array}{cc}\frac{\partial J}{\partial {\alpha }_c^p}=0\frac{\partial J}{\partial {\alpha }_t^p}=0\frac{\partial J}{\partial {\alpha }_s^p}=0& \left(13\right)\end{array}$

[0043] We have: $\begin{array}{cc}\sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^{c^2}·{\alpha }_c^p+\sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^c{V}_{\left(\mathrm{ij}\right)}^t·{\alpha }_t^p+\sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^c{V}_{\left(\mathrm{ij}\right)}^s·{\alpha }_s^p=\sum _{i=1}^N\sum _{j=1}^N{d}_{\mathrm{ij}}^2{V}_{\left(\mathrm{ij}\right)}^c& \left(14\right)\\ \sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^c{V}_{\left(\mathrm{ij}\right)}^t·{\alpha }_c^p+\sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^{t^2}·{\alpha }_t^p+\sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^t{V}_{\left(\mathrm{ij}\right)}^s·{\alpha }_s^p=\sum _{i=1}^N\sum _{j=1}^N{d}_{\mathrm{ij}}^2{V}_{\left(\mathrm{ij}\right)}^t& \left(15\right)\\ \sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^c{V}_{\left(\mathrm{ij}\right)}^s·{\alpha }_c^p+\sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^t{V}_{\left(\mathrm{ij}\right)}^s·{\alpha }_t^p+\sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^{s^2}·{\alpha }_s^p=\sum _{i=1}^N\sum _{j=1}^N{d}_{\mathrm{ij}}^2{V}_{\left(\mathrm{ij}\right)}^s& \left(16\right)\end{array}$

[0044] We let $A=\left[\begin{array}{ccc}\sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^{c^2}& \sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^c{V}_{\left(\mathrm{ij}\right)}^t& \sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^c{V}_{\left(\mathrm{ij}\right)}^s\\ \sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^c{V}_{\left(\mathrm{ij}\right)}^t& \sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^{t^2}& \sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^t{V}_{\left(\mathrm{ij}\right)}^s\\ \sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^c{V}_{\left(\mathrm{ij}\right)}^s& \sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^t{V}_{\left(\mathrm{ij}\right)}^s& \sum _{i=1}^N\sum _{j=1}^N{V}_{\left(\mathrm{ij}\right)}^{s^2}\end{array}\right],\beta =\left[\begin{array}{c}{\alpha }_c^p\\ {\alpha }_t^p\\ {\alpha }_s^p\end{array}\right]\text{and}b=\left[\begin{array}{c}\sum _{i=1}^N\sum _{j=1}^N{d}_{\mathrm{ij}}^2{V}_{\left(\mathrm{ij}\right)}^c\\ \sum _{i=1}^N\sum _{j=1}^N{d}_{\mathrm{ij}}^2{V}_{\left(\mathrm{ij}\right)}^t\\ \sum _{i=1}^N\sum _{j=1}^N{d}_{\mathrm{ij}}^2{V}_{\left(\mathrm{ij}\right)}^s\end{array}\right]$

[0045] Equations 14-16 are simplified

[0046] A·β=b,  (17)

[0047] β is calculated as a constrained least square problem. The weighting vector α 162 is determined by the p-th root of the β.

[0048] Location Transformation

[0049] In the preferred user specified arrangement, it is desired to have the additional objects to be located relative to the objects placed by the user. However, there is no express relationship between the user arrangement and the arrangement according to the PCA. Therefore, we apply a linear affine transform 170 to the locations 121 produced by the PCA 120. The affine transformation takes care of difference in rotation, reflection, stretching, translation and shearing transformation between the PCA produced locations 121, and the preferred clustering 161.

[0050] However, due to the collinearity and ratio of distance preserving properties, the affine transformation does not align the additional objects with the user placed objects. Therefore, we also apply a non-linear transformation, e.g., a radial basis function, to the affine transformed locations to align the objects with the preferred locations.

[0051] Enhanced Visualization

[0052] As shown in FIG. 1, the system 100 according to our invention can also selectively enhance 180 a subset of the displayed objects based on relevance criteria 181. The enhancement 180 increases the visual prominence of this subset of objects according to a relevance score 182 for each displayed object 101. The enhancement can be done by increasing the size, contrast, or brightness of the objects as a function of their relevance score 182.

[0053] The relevance 132 represents a “third” dimension of visualization, the location being the other two dimensions. The purpose of the relevance 132 is to increase the information flow, and enhance the user's perception of the displayed objects based on the current context.

[0054] In a typical scenario, a user issues an object-based query, e.g., “find me similar objects,” and the system retrieves the nearest-neighboring objects, as described above, and renders the top N objects, using the alpha-weighted feature vectors 111. In this case, each object has an implicit equal “relevance,” or similarity to the query. It is desired to selectively enhance the visualization, so that displayed objects that have a greater contextual relevance become more visually prominent by, for example, proportionally increasing their sizes—in which case the relevance score becomes a constraint in the optimization 130. Alternatively, the contrast or brightness of the objects can be modified, perhaps, independent of the optimization 130, or iconic information can display the actual relevance, e.g., rank number, or symbolic graphics.

[0055] The invention is described in terms that enable any person skilled in the art to make and use the invention, and is provided in the context of particular example applications and their requirements. Various modifications to the preferred embodiments will be readily apparent to those skilled in the art, and the principles described herein may be applied to other embodiments and applications without departing from the spirit and scope of the invention. Thus, the present invention is not intended to be limited to the embodiments described herein, but is to be accorded with the broadest scope of the claims below, consistent with the principles and features disclosed herein.