Image retrieval by syntactic characterization of appearance

• US 5,987,456 A
• Filed: 10/28/1997
• Issued: 11/16/1999
• Est. Priority Date: 10/28/1997
• Status: Expired due to Fees

• Current Assignee: University Of Massachusetts
• Original Assignee: University Of Massachusetts
• Inventors: Manmatha, Raghavan, Ravela, Srinivas, Riseman, Edward
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US08/959,500
• Time in Patent Office: 749 Days
• Field of Search: 707/5, 707/104, 707/4, 345/326
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

An image retrieval method which includes producing multiscale vectors associated with points in a set of database images, indexing the database vectors to produce a database vector index, producing query multiscale vectors associated with points in a query image, and matching the query vectors with the indexed database vectors to identify a database image which is similar to the query image. Each of the database multiscale vectors and the query multiscale vectors includes multiple single scale vectors associated with corresponding spatial scales. The method can include applying a single scale image processing procedure at each of the spatial scales to produce single scale vectors and combining single scale vectors each associate with a given point in an image to form a multiscale vector associated with that point. The single scale image processing procedure can include evaluating multiple smoothed spatial derivatives of image intensity at a point in an image and transforming the spatial derivatives to produce a single scale vector which is insensitive to rotation of the image about the point.

Claims

1. A method of image retrieval comprising:

applying a database multiscale image processing procedure to each of a plurality of database images producing a plurality of database multiscale vectors, wherein each multiscale vector characterizes a region about a different one of a corresponding plurality of points in the images;

indexing the database vectors to produce a database vector index;

applying a query multiscale image processing procedure to a query image to produce a plurality of query multiscale vectors, wherein each query multiscale vector characterizes a region about a different one of a corresponding plurality of points in the query image; and

matching the plurality of query vectors with the plurality of indexed database vectors to identify a database image which is similar to the query image;

wherein each of the database multiscale vectors and the query multiscale vectors includes a plurality of single scale vectors associated with a corresponding plurality of database spatial scales.

2. The method of claim 1 wherein the database image processing procedure and the query multiscale image processing procedure applied to an image each includes:

applying a single scale image processing procedure to the image at each of the plurality of database spatial scales to a produce a plurality of single scale vectors; and

combining single scale vectors each associated with a same point in the image to form a multiscale vector associated with that same point.

3. The method of claim 2 wherein the single scale image processing procedure applied to the image includes:

evaluating a plurality of smoothed spatial derivatives of image intensity at a point in the image; and

transforming the plurality of spatial derivatives to produce a single scale vector associated with the point such that the single scale vector is insensitive to rotation of the image about the point.

4. The method of claim 3 wherein evaluating the smoothed spatial derivatives of image intensity includes the step of filtering the image using a derivative of a Gaussian function.

5. The method of claim 1 further comprising:

accepting a specification of a salient region of the query image; and

selecting the plurality of query points within the salient region.

6. The method of claim 1 wherein matching further includes the step of comparing relative location of points associated with query vectors with relative locations of points associated with database vectors.

7. The method of claim 1 wherein each of the query vectors further includes a plurality of single scale vectors associated with a corresponding plurality of additional spatial scales, and matching includes the step of selecting a subset of the single scale vectors in each of the query vectors.

8. The method of claim 1 wherein matching further includes accessing the database vector index to find database vectors that have similar values to one of the query vectors.

9. The method of claim 1 wherein the single scale vectors included in each of the database multiscale vectors and the query multiscale vectors characterize regions about a same point in an image as that multiscale vector.

10. A computer program stored on a computer readable medium for causing a computer to perform the functions of:

applying a database multiscale image processing procedure to each of a plurality of database images producing a plurality of database multiscale vectors, wherein each multiscale vector characterizes a region about a different one of a corresponding plurality of points in the images;

indexing the database vectors to produce a database vector index;

applying a query multiscale image processing procedure to a query image to produce a plurality of query multiscale vectors, wherein each query multiscale vector characterizes a region about a different one of a corresponding plurality of points in the query image; and

matching the plurality of query vectors with the plurality of indexed database vectors to identify a database image which is similar to the query image;

wherein each of the database multiscale vectors and the query multiscale vectors includes a plurality of single scale vectors associated with a corresponding plurality of database spatial scales.

11. The computer program of claim 10 wherein the database image processing procedure and the query multiscale image processing procedure applied to an image each includes:

applying a single scale image processing procedure to the image at each of the plurality of database spatial scales to a produce a plurality of single scale vectors; and

combining single scale vectors each associate with a same point in the image to form a multiscale vector associated with that same point.

12. The computer program of claim 10 wherein the single scale image processing procedure applied to the image includes:

evaluating a plurality of smoothed spatial derivatives of image intensity at a point in the image; and

transforming the plurality of spatial derivatives to produce a single scale vector associated with the point such that the single scale vector is insensitive to rotation of the image about the point.

13. The computer program of claim 12 wherein evaluating the smoothed spatial derivatives of image intensity includes the step of filtering the image using a derivative of a Gaussian function.

14. The computer program of claim 10 for further causing the computer to perform the functions of:

accepting a specification of a salient region of the query image; and

selecting the plurality of query points within the salient region.

15. The computer program of claim 10 wherein the function of matching further includes the step of comparing relative location of points associated with query vectors with relative locations of points associated with database vectors.

16. The computer program of claim 10 wherein each of the query vectors further includes a plurality of single scale vectors associated with a corresponding plurality of additional spatial scales, and the function of matching includes selecting a subset of the single scale vectors in each of the query vectors.

17. The computer program of claim 10 wherein the function of matching further includes accessing the database vector index to find database vectors that have similar values to one of the query vectors.

18. The computer program of claim 10 wherein the single scale vectors included in each of the database multiscale vectors and the query multiscale vectors characterize regions about a same point in an image as that multiscale vector.

19. An image retrieval system for comparing a query image to a plurality of database images comprising:

a database image processor;

a plurality of database multiscale vectors produced by applying each of the plurality of database images as input to the database image processor;

a database vector index for accessing the database vectors;

a query image processor;

a plurality of query multiscale vectors produced by applying the query image as input the query image processor; and

means for matching the plurality of query vectors with the indexed database vectors to identify a database image which is similar to the query image;

wherein each of the database multiscale vectors and the query multiscale vectors includes a plurality of single scale vectors associated with a corresponding plurality of database spatial scales.

20. The system of claim 19 wherein the database image processor and the query image processor each includes:

a derivative processor used to compute a plurality of smoothed spatial derivatives of an input image for each of the database spatial scales; and

a feature processor which takes the plurality of derivatives and whose output is insensitive to rotation of the input image around a point.

21. The system of claim 19 wherein the query image processor includes a means for accepting a specification of a salient region of the query image, and the database vectors are associated with points within the salient region.

22. The system of claim 19 wherein the means for matching further includes a spatial matcher that compares relative locations of query points and relative locations of database points.

23. The system of claim 19 wherein each of the query vectors further includes a plurality of single scale vectors associated with a corresponding plurality of additional spatial scales, and the means for matching includes a means for selecting a subset of the single scale vectors in each of the query vectors.

24. The image retrieval system of claim 19 wherein the single scale vectors included in each of the database multiscale vectors and the query multiscale vectors characterize regions about a same point in an image as that multiscale vector.