A fast full-search equivalent algorithm using energy compacting transforms

A new fast algorithm is proposed for image database search which is equivalent to full search. An energy compacting transform is applied off-line to the members of the database, and the same transform is applied to the sample image. For the sample image, a low-resolution best match is then found based on the distance between the low-resolution version of sample image and low-resolution versions of the database members. For the low-resolution match, the full-resolution distance is computed, and any database member whose low-resolution distance is larger than this distance is pruned. This process is repeated for different resolutions. The proposed algorithm provides significant speed up compared to full search, and is faster than the partial sum, and nearest neighbor search algorithms