Invariant texture matching method for image retrieval

• US 6,192,150 B1
• Filed: 11/16/1998
• Issued: 02/20/2001
• Est. Priority Date: 11/16/1998
• Status: Expired due to Term

• Current Assignee: National University of Singapore
• Original Assignee: National University of Singapore
• Inventors: Lai, Seow Yong, Leow, Wee Kheng
• Primary Examiner(s): Tran, Phuoc
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/192,274
• Time in Patent Office: 827 Days
• Field of Search: 382/181, 382/190, 382/191, 382/276, 382/305, 707/2, 707/4, 707/7, 707/100
• US Class Current: 382/190
• CPC Class Codes: G06F 16/5862 using texture
• CPC Class Codes: G06T 7/44 using image operators, e.g. filters, edge density metrics or local histograms
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method and apparatus matches texture patterns in a way that is invariant to the intensities, scales, and orientations of the texture patterns. The texture matching apparatus includes a texture feature extractor, a feature transformer, and an image ranker. The texture feature extractor identifies regions in a plurality of stored images that contain homogeneous texture patterns that may vary in intensities, scales, and orientations, and extracts N-component texture feature vectors in these regions. The feature transformer maps the N-component feature vectors into a D-dimensional texture space that is invariant to texture intensity, scale, and orientation. The image ranker ranks the images according to the similarity between the texture patterns that they contain and the query texture measured in the D-dimensional invariant texture space, and the similarity between the N-component feature vectors of the texture patterns. The results of texture matching can be used by a content-based image retrieval system to display a list of images according to their similarity to the query texture.

Claims

1. An apparatus for matching a query texture with a plurality of images, each containing a plurality of textured regions, said apparatus comprising:

feature extraction means for identifying a plurality of regions in the plurality of images, each region containing a texture pattern, extracting an N-component feature vector for each region, and normalizing the extracted N-component feature vectors, where N is an even integer greater than or equal to 2;

normalization means for normalizing the extracted N-component texture feature vectors;

arranging means for arranging each N-component feature vector into a 2-dimensional representation with spatial frequency increasing along one dimension and orientation changing in another dimension;

extraction means for extracting D texture characteristics that are invariant to texture scale and orientation from each 2-dimensional representation and forming a D-dimensional feature vector, where D for said D texture characteristics and said D-dimensional is an integer greater than 1;

computing means for computing the similarity between the query texture and the plurality of images according to the similarity between a D-dimensional feature vector of the query texture and the D-dimensional feature vectors of the plurality of textured regions in the plurality of images; and

image ranking means for ranking the plurality of images according to their similarity to the query texture.

2. The apparatus of claim 1, wherein said feature extraction means includes a plurality of Gabor filters.

3. The apparatus of claim 2, wherein said plurality of Gabor filters have overlapping filter supports.

4. The apparatus of claim 1, wherein said feature extraction means performs oriented wavelet transform.

5. The apparatus of claim 1, wherein said feature extraction means normalizes an N-component feature vector by dividing the value of each feature vector component by the value of the largest component.

6. The apparatus of claim 1, wherein said means for computing D texture characteristics comprises:

means for storing a plurality of 2-dimensional masks;

means for computing a similarity value between each 2-dimensional mask and a local patch of the 2-dimensional representation of a feature vector; and

means for finding the largest similarity value over the entire 2-dimensional representation.

7. The apparatus of claim 6, wherein one mask identifies patch-shaped patterns in the 2-dimensional representation.

8. The apparatus of claim 6, wherein one mask identifies column-shaped patterns in the 2-dimensional representation.

9. The apparatus of claim 6, wherein one mask identifies row-shaped patterns in the 2-dimensional representation.

10. The apparatus of claim 1, wherein said image ranking means comprises:

means for arranging the texture patterns in a ranked list in order of similarity computed in the D-dimensional texture space;

means for computing the similarity between the N-component vector of a texture pattern and the N-component vector of P neighboring texture patterns down the ranked list where P is an integer greater than or equal to 1;

means for re-ranking neighboring texture patterns with larger similarity between the N-component vectors higher on the ranked list and patterns with smaller similarity lower on the ranked list;

means for mapping the ranked list of texture patterns into a ranked list of images by determining the images that contain the respective texture patterns of the ranked list of texture patterns; and

means for removing redundant images with smaller similarities from the ranked list of images.

11. The apparatus of claim 10, wherein said means for computing similarity in the D-dimensional texture space calculates Euclidean distances between D-dimensional vectors.

12. The apparatus of claim 10, wherein said means for computing similarity between N-component feature vectors calculates the normalized cosine between N-component feature vectors.

13. A method for matching a query texture with a plurality of images, each containing a plurality of textured regions, said method comprising:

identifying from the plurality of images a plurality of regions, each containing a texture pattern;

extracting and N-component texture feature vector for each region, where N is an even integer greater than or equal to 2;

normalizing the extracted N-component texture feature vectors;

arranging each N-component texture feature vector into a 2-dimensional representation with spatial frequency increasing along one dimension and orientation changing in another dimension;

extracting D texture characteristics that are invariant to texture scale and orientation from each 2-dimensional representation and forming a D-dimensional feature vector, where D for said D texture characteristics and said D-dimensional is an integer greater than 1;

computing the similarity between the query texture and the plurality of images according to the similarity between a D-dimensional feature vector of the query texture and the D-dimensional feature vectors of the plurality of textured regions in the plurality of images; and

ranking the plurality of images according to their similarity to the query texture.

14. The method of claim 13, wherein said N-component feature vectors are extracted using a plurality of Gabor filters.

15. The method of claim 14, wherein said plurality of Gabor filters have overlapping filter supports.

16. The method of claim 13, wherein said N-component feature vectors are extracted using oriented wavelet transformers.

17. The method of claim 13, wherein said N-component feature vectors are normalized by dividing the value of each feature vector component by the value of the largest component.

18. The method of claim 13, wherein said D texture characteristics are computed by:

retrieving a plurality of 2-dimensional masks;

computing the similarity value between a 2-dimensional mask and a local patch of a 2-dimensional representation; and

finding the largest similarity value over the entire 2-dimensional representation.

19. The method of claim 18, wherein one 2-dimensional mask identifies patch-shaped patterns in the 2-dimensional representation.

20. The method of claim 18, wherein one 2-dimensional mask identifies column-shaped patterns in the 2-dimensional representation.

21. The apparatus of claim 18, wherein one 2-dimensional mask identifies row-shaped patterns in the 2-dimensional representation.

22. The method of claim 13, wherein said ranking step is performed by:

arranging the texture patterns in a ranked list in order of similarity computed in the D-dimensional texture space;

computing the similarity between the N-component vector of a texture pattern and P neighboring texture patterns down the ranked list where P is an integer greater than or equal to 1;

moving neighboring texture patterns with larger similarity between the N-component vectors higher on the list and texture patterns with smaller similarity lower on the list;

mapping the ranked list of texture patterns into a ranked list of images by determining the images that contain the ranked texture patterns; and

removing redundant images with smaller similarities.

23. The method of claim 22, wherein similarities in the D-dimensional texture space are computed by calculating Euclidean distances between D-dimensional vectors.

24. The method of claim 22, wherein similarities between N-component feature vectors are computed by calculating the normalized cosine N-component between vectors.