1.2 Old-school image querying

Jacobs et al. propose an algorithm where sparse signatures for images in the database are first created. When a user inputs a query image, the signature of the query is computed and compared to signatures in the database.

The signatures are computed as follows:

• Compute the discrete wavelet transform of the image.
• Set all but the highest magnitude wavelet coefficients to 0.
• Of the remaining coefficients, quantize the positive coefficients to +1 and the negative ones to –1.

This matrix of mostly 0’s and a few +1’s and –1’s constitutes the signature for an image. These +1’s and –1’s correspond to the feature points in an image, and basically characterize the image structure. Jacobs et al. concluded, after some experimentation, that on their database, considering the top 60 magnitude coefficients worked well for scanned images, while the top 40 coefficients gave best results for hand-drawn images.

The signatures in our implementation were compared using the generic L1 norm of the difference between signature matrices. Jacobs et al. use the non-intuitive “Lq” norm, which somehow weights the coefficients corresponding to different scales differently. This idea definitely carries some merit, but Jacobs et al. do not provide a very good explanation of this scheme, and we don’t believe that it will improve the performance of their querying algorithm significantly.

Our implementation of their algorithm is available on Owlnet at

The m-file for generating signatures is sig_gen.m , and the metric function for comparing signatures is metric.m .