The difference or similarities between images in a database can be based upon measures like the L1- or L2-norm for each pair of feature vectors of images in the database. For a database of size N this distance matrix has NxN entries of which only N(N-1) have to be computed since the distance matrix is symmetric and has a zero-diagonal. The optimal way of sorting the images in time would be to divide similarity space into clusters of like images and by showing members of each cluster as frames from a coherent scene while treating the movement from cluster to cluster as scene breaks. Because clusters may well contain a single frame in our case, a bi-level set-up was used: 1 frame per cluster is considered to be an index frame; an index frame video loop is produced and for each cluster a separate video loop is produced of its internal frames. The global index loop can be shown at slow speed, while the cluster loops can be displayed at a higher speed.
The index and cluster sequences are generated from one specific path through the distance matrix using a threshold. Two possibly shortest paths were devised for a walk through the image database using the values of the distance matrix. One way to order the frames would be according to a sort on increasing average distance of each image to all the other images in the database: the average distance is obtained by summing the row- or column values in the distance matrix and averaging. We will call this the average walk. The second way to order the frames is by following the shortest distance connections (linking image pairs as consecutive frames using the lowest distance entry in a row or column) starting with the image that is closest to all other images (most representative image of the database). We call this the shortest walk. As a comparison to quantify the reduction in variance obtained by using these walks we also generated a random walk by using the order images were scanned in, which is close enough to random. We will call this sort the random walk.
Dr. D.P. Huijsmans