Multi-linearization data structure for image browsing6233367Abstract A method of displaying images is based on both a first linearization and a second linearization. In one embodiment, the linearizations are performed by traversing two space-filling curves. In another embodiment, the linearizations are performed by traversing a cluster data structure. More than two linearizations may be displayed. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
TABLE 1
/***********************************************************
.COPYRGT. Intel Corporation, 1998
Pseudo-code for collapsing points in a space to points in a line,
via space-filling curve traversal.
The "points" are arrays of plain old integer coordinates. These are
combined to produce a single value, indicating a position along a line.
Since we're dealing with high-dimensional spaces
(DIMENSION == .about.600), the final value will have hundreds of digits,
and we construct a special datatype to hold it.
************************************************************/
BEGIN
for each image I, BEGIN:
Compute I's n-bin color histogram, H
Normalize H to a standard number of pixels
Convert H to an n-dimensional vector, V
Call Hctol(V) to print out position of V along
a Hilbert curve traversal.
Call Pctol(V) to print out position of V along
a Peano curve traversal.
END
Sort images along Hilbert curve positions: output sorted list
Sort images along Peano curve positions: output sorted list.
/* These two orderings can then be used to generate Browser
Windows */
END
/*
* function: hilbert_cube_to_line --- Hctol
* Collapses m-dimensional coordinates to a line via
* Hilbert curve traversal
*/
function Hctol(point)
{
integer tau, /* chunk of digits of final line position */
lasttau; /* holder for previous value of tau */
integer i,j,k, /* counters */
lastbit=0,
one, zero,
r=0, b=0,
DEGREE=19; /* DEGREE == number of bits precision per
coordinate */
FOR i = DEGREE .. 1
{
/* Extract tau from all the coordinate values */
FORj = 1 .. DIMENSION
{
SET j'th bit of tau = i'th bit of point[j]
}
SWAP tau and lasttau;
XOR tau with lasttau;
ROLL tau r bits to the left;
tau->end = (tau->end + roller)%DIMENSION;
/* twiddle bits in tau */
if(lastbit == 0)
TOGGLE first bit of tau: replace 1 with 0, 0 with 1;
TOGGLE b'th bit (from the left) of tau;
/* Avalanche and send digits to the output buffer */
for(j = 1..DIMENSION){
COMPUTE k = the XOR of the first j bits of tau;
OUTPUT k;
if(k==1) one=j;
else zero=j;
}
/* compute b */
SET lastbit = k;
if(lastbit == 0)
b=DIMENSION-one;
else
b=DIMENSION-zero;
COMPUTEr = (r+DIMENSION-1-b)%DIMENSION;
}
}
/*
* function: peano_cube_to_line
* Collapses m-dimensional coordinates to a line via
* Peano curve traversal
*/
void Pctol(point)
{
int i,j, trit, flag=0, DEGREE=12;
int modulus, h=0;
int flags[2048]; /* flags are used to determine which way
the curve winds at any given point */
FOR all i, SET flags[i]=0;
FOR i = DEGREE .. 1
FOR j = DIMENSION .. 1
{
flag = flag XOR flags[j];
trit = i'th digit of point[j] /* This is in base 3, so trit
takes on values 0, 1, or 2 */
if(trit==1)INVERT flag[j];
else
if(flag is TRUE)
SET trit = 2-trit; /* Sets 2 to 0, or 0 to 2 */
OUTPUT trit;
SET flag = flag XOR flags[j];
}
}
}
/*
Source code for collapsing points in a space to points in a line,
via space-filling curve traversal.
The "points" are arrays of plain old integer coordinates. These are
combined to produce a single value, indicating a position along a line.
Since we're dealing with high-dimensional spaces
(DIMENSION == .about.600), the final value will have hundreds of digits,
and we must construct a special datatype to hold it.
*/
#include<stdio.h>
#define MAXD 700
#define DIMENSION length
#define SIDELENGTH 531441
/* */
/* Code to handle the numeral datatype */
/* */
typedef struct numeral{
char d[MAXD]; /* At most MAXD digits */
int end; /* position of highest digit */
}*numeral;
char hopper[10];
int hopsize, hopcount, hopmod;
/* Ninit --- allocates a numeral and sets its value to 0 */
numeral ninit(int length)
{
numeral done; int i;
if((done=(numeral)malloc(sizeof(struct numberal)))==NULL)
{fprintf(stderr,"Numeral allocation problem..backslash.n"); exit(1);}
for(i=0; i<MAXD;i++)done->d[i]='0';
done->end=DIMENSION-1;
return done;
}
/* Hopperhead --- initializes the "hopper." More on this below */
void hopperhead(int size, int mod)
{
hopsize=size; hopmod=mod; hopcount=0;
}
/* Hop --- pours digits into a "hopper," emptying the whole thing
* when it becomes full.
*
* The hopper is a small buffer of digits in some small base b, such
* as 2 or 3. These digits are generated by the curve-mapping functions,
* in the form of very large binary/ternary numbers. We don't want to
* store all that in a file, so the hop function conglomerates N base-b
* digits into a single digit base N*b before printing it to standard out.
*
*/
void hop(int c)
{
int i,j;
if(c!= 0)hopper[hopcount++]=(char) c;
if(hopcount>=hopsize.parallel.c==0){/* Dump hopper in base-n format */
for(i=j=0; j<hopcount; j++)
i = i*hopmod + hopper[j]-'0';
printf("%c",i+''+1);
hopcount=0;
}
}
/*
* function: hilbert_cube_to_line
* Collapses m-dimensional coordinates to a line via
* Hilbert curve traversal
*
* This function accepts an array of integers (coordinates)
* and converts it to a position along a line, sending the
* digits to an output buffer which eventually prints to
* standard output.
*/
void Hctol(int*v, int length)
{
numeral tau, lasttau;
int i,j,k, one, zero, lastbit=0, lastbyte=0, roller=0, DEGREE=19;
tau=ninit(DIMENSION); lasttau=ninit(DIMENSION);
hopperhead(6,2); /* Set up hopper: Base 2, */
/* Buffer of six digits max */
for(i=1<<(DEGREE-1); i>0; i>>=1)
{
/* Extract tau from all the coordinate values */
for(j=0; j<DIMENSION; j++)
tau->d[j]= ((v[j]&i)==0)?'0':'1';
tau->end=DIMENSION-1;
/* Perform: tau = lasttau; lasttau = tau; */
for(j=0; j<DIMENSION; j++){
k=tau->d[j];
tau->d[j] = (lasttau->d[j]&1);
lasttau->d[j]=k;
}
/* Roll the value of tau "roller" bits to the left */
tau->end = (tau->end + roller)%DIMENSION;
/* twiddle bits in tau */
if(lastbit==0)tau->d[(tau->end+1)%DIMENSION] = 1;
tau->d[(tau->end+1+lastbyte)%DIMENSION] = 1;
/* Avalanche and send digits to the output buffer */
for(j=k=0, one=zero=DIMENSION-1; j<DIMENSION; j++){
hop(tau->d[(tau->end+1+j)%DIMENSION] k);
k = (tau->d[(tau->end +1+j)%DIMENSION]&1);
if(k) one=j; else zero=j;
}
/* compute lastbyte */
if(lastbit=k) lastbyte=DIMENSION-1-zero;
else lastbyte=DIMENSION-1-one;
roller = (roller+DIMENSION-1-lastbyte)%DIMENSION;
}
hop(0); /* flush the output buffer */
free(tau); free(lasttau);
}
/*
* function: peano_cube_to_line
* Collapses m-dimensional coordinates to a line via
* Peano curve traversal
*
* This function accepts an array of integers (coordinates)
* and converts it to a position along a line, sending the
* digits to an output buffer which eventually prints to
* standard output.
*/
void Pctol(int*v, int length)
{
int i,j, trit, flag=0, DEGREE=12;
int modulus, h=0;
int flags[2048];
hopperhead(4,3); /* Set up hopper: base-3, */
/* Buffer of 4 digits max */
for(i=0; i<2048; i++)flags[i]=0;
for(modulus=SIDELENGTH/3, i=DEGREE-1; i>=0; i--, modulus/=3){
for(j=DIMENSION-1;j>=0;j--){
flag = flags[j]; /* XOR-out current flag */
trit = (v[j]/modulus)%3; /* Get current base-3 digit */
if(trit==1) flags[j] = 1; /* Invert current flag, or: */
else if(flag)trit = 2-trit; /* maybe invert the digit */
hop(trit+'0'); /* Send digit to output */
flag = flags[j]; /* XOR-in the new flag value */
}
}
hop(0); /* Flush output buffer */
}
FIG. 1 shows one embodiment of a flowchart of the process of creating dual linearizations for each image. At step 101, a histogram H(Ij) is created of image Ij. One implementation of the histogram is by using color information. Other feature information like shape and size can also be implemented, and can be in the form of histogram or other feature representation. Essentially, any image content that can be represented as a vector (a point in space) may be used. Points "close" to one another are similar in that particular kind of content. Once the set of images is converted into a set of points, the rest of the process is the same: traverse the "space" along the two curves, and output the data structure. At step 102, the histogram of k attributes is mapped as a point p(j) in k-dimensional space, where k is any positive integer. At step 103, the position of p(j) is computed in a Hilbert traversal of the k-space. In one embodiment, the position of p(j) is computed along an interval [0,1] in a Hilbert traversal of the k-space. At step 104, the position of p(j) is computed along interval [0,1] in a Peano traversal of the k-space. At step 105, p(j)'s four nearest neighbors based on the values obtained from the Hilbert and Peano curve traversals are located. Their links are updated according to the positions of the images. In one embodiment, a linked data structure is used to store each image as it is linearized. For example, a new image is placed into a first linked structure by its linearization based on the Hilbert curve traversal. The new image is linked to its nearest neighbor, i.e., the images closest to the new image in linearization. The new image is similarly placed into a second linked structure by its linearization based on the Peano curve traversal. Once all the images are added to the data structure, it is possible to follow a first set of links to traverse the linearization based on the Hilbert traversal. It is also possible to follow a second set of links to traverse the linearization based on the Peano traversal. In another embodiment, linearizations based on other methods can be employed. Additionally more than two linearizations may be used. One advantage of using the described data structure is that it does not need to be completely recalculated each time an image is added or deleted from the data structure. Instead, only a few links need to be modified for each addition or deletion of an image. A second advantage of the data structure is that it is data independent, so that two existing databases can be combined into one with little more than a simple list merge. Clustering Clustering is another method of providing a linearization to images. A cluster is a grouping of images using a tree-like structure. The nature of clusters is such that it is not unusual that like images are placed into the data structure at the same time. By performing a linearization based upon a smart traversal of the cluster, like images are more likely to be placed next to each other in the linearization. One way of linearizing a cluster is to add an entire first group of images before traversing the cluster to add another group of images. For example, if a first group of images was all added to the cluster at the same time, these images should be linked together prior to moving on to a group of images that was added to the cluster at a different time than the first group. In another embodiment, the attributes of the target image are compared with attributes of all groups of the cluster. The groups that are the closest in attributes are linearized first. Other groups are added based on their similarity in attributes. A centroid, or representative item having the average characteristics of an entire group, can be used to compare the target image with an entire group within the cluster. Another way to perform a linearization is to traverse the cluster in an orderly fashion. For example, a first linearization can traverse the cluster taking all right branches prior to taking any left branches. A second linearization can traverse the cluster taking all left branches. Alternatively, a first linearization can alterate between right and left branches, and a second linearization can alternate in the opposite manner. In another embodiment, multiple linearizations can be created by first performing a first traversal of a cluster by traversing a first random traversal of the cluster linearizing each of the images of a section before moving on to a different section. A second traversal of the entire cluster is then performed by a different random traversal of the cluster. Display of Multi-linearizations FIG. 4 shows an example of a browser interface based on a dual linearization. In this implementation, a total of 53 images are displayed at a time. The current image of focus, or the target image, is centered in the display. The images immediately to the left and right are the nearest neighbors 42a in one linearization. The images immediately to the top and bottom are the nearest neighbors 42b in a second linearization. The nearest neighbors are the images closest to the target image in linearization. In the case of the space-filling curves, the nearest neighbors correspond to the points that are closest in position in a linearization to the point corresponding to the target image. In one embodiment, the first linearization may be based on a Hilbert curve, and the second linearization may be based on a Peano curve. In a second embodiment, the first linearization is based on a first traversal of a cluster data structure, and the second lienarization is based on a second traversal of the cluster data structure. In one embodiment, the rules of displaying nearest neighbors of an image are applied recursively to all other images. Additionally, in one embodiment, images further away from the center, or target image, are displayed with a smaller size to denote greater dissimilarity from those images closer to the center. In FIG. 3, the next nearest neighbors 43 to the target image are smaller than the nearest neighbors 42a and 42b. The next-next nearest neighbors 44 of the target image are even smaller then its next nearest neighbors 43. FIG. 5 shows an example of a browser interface based on a triple linearization. In one embodiment, the images above and below an image are the nearest neighbors based on a first linearization. Two other images may correspond to nearest neighbors based on a second linearization, and the remaining two images may correspond to nearest neighbors based on a third linearization. In other embodiments, more linearizations may be added, and a mixture of linearizations based on different methods is possible. FIG. 6 shows an example of a system implemented on an SQL server that communicates with a middleware server to construct and serve web pages to an end user. The SQL server maintains the data structure of the multiple linearizations. The web server allows easy selection of the target image from any of the displayed images. When one of the images is selected, it becomes the target image, and the nearest neighbor and next-nearest neighbor images are updated correspondingly. Thus, a system and method for using multiple linearizations for image browsing is disclosed. The specific arrangements and methods described herein are merely illustrative of the principles of this invention. Numerous modifications in form and detail may be made without departing from the scope of the described invention. Although this invention has been shown in relation to a particular embodiment, it should not be considered so limited. Rather, the described invention is limited only by the scope of the appended claims. The method steps of FIG. 1 may be performed by a computer processor executing instructions organized into a program module or a custom designed state machine. Storage devices suitable for tangibly embodying computer program instructions include all forms of non-volatile memory including, but not limited to: semiconductor memory devices such as EPROM, EEPROM, and flash devices; magnetic disks (fixed, floppy, and removable); other magnetic media such as tape; and optical media such as CD-ROM disks. Further, the methods described herein may be embodied in a hardware device such as a printed circuit board comprising discrete logic, integrated circuits, or specially designed application specific integrated circuits (ASIC).
|
Same subclass Same class Consider this |
||||||||||