Method and apparatus for locating multi-region objects in an image or video database

• US 6,691,126 B1
• Filed: 06/14/2000
• Issued: 02/10/2004
• Est. Priority Date: 06/14/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Syeda-Mahmood, Tanveer Fathima
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/593,465
• Time in Patent Office: 1,336 Days
• Field of Search: 707/102, 382/104
• US Class Current: 707/696
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: Y10S 707/914 Video
• CPC Class Codes: Y10S 707/915 Image
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method (and system) for specifying the region layout of objects in an affine invariant manner as a set of affine intervals between pairs of regions, includes representing database and query regions using affine intervals along with their region identity, matching query region layout to layout of database image regions using an index structure, and retrieving relevant images of the database by hashing for dominant hit regions in the index structure.

Claims

1. A method of specifying the region layout of objects in an affine invariant manner as a set of affine intervals between pairs of regions, comprising:

representing database and query regions using affine intervals along with their region identity;

matching query region layout to layout of database image regions using an index structure; and

retrieving relevant images of the database by hashing for dominant hit regions in the index structure.

2. The method of claim 1, wherein said hashing comprises color region hashing.

3. The method of claim 1, further comprising:

using a spatial layout representation to represent and localize said object in a pose-invariant manner.

4. The method of claim 1, further comprising:

extracting said regions using color for providing an illumination-invariant way of localizing colored objects.

5. The method of claim 1, further comprising:

using the index structure to consolidate affine interval information in the database.

6. The method of claim 1, further comprising:

using the index structure to avoid linearly searching through the database.

7. The method of claim 1, further comprising:

localizing 2-dimensional objects in an affine-invariant manner.

8. The method of claim 1, further comprising:

localizing 3-dimensional objects under limited pose changes in an affine-invariant manner.

9. The method of claim 1, further comprising:

extracting regions based on a feature other than color.

10. The method of claim 1, wherein said regions are extracted regardless of a presence of occlusions and noise in the region extraction based on built-in redundancy of said extracting.

11. A method of locating a multi-feature object in an image or video database, comprising:

extracting regions within the images containing a multi-feature query object;

using in combination the feature and geometric layout to localize the object in an illumination invariant and affine-invariant manner; and

retrieving an image based on said localization of said object.

12. The method of claim 11, wherein said feature comprises color.

13. The method of claim 11, wherein said feature includes texture patterns.

14. The method of claim 11, wherein said object comprises any of a two-dimensional object and a three-dimensional object in two-dimensional data, said method further comprising:

locating two-dimensional and three-dimensional objects in two-dimensional data; and

representing affine intervals using said data structure, said data structure comprising an interval hash tree.

15. The method of claim 14, further comprising:

indexing the interval hash tree; and

recording the histogram of region hits.

16. The method of claim 11, wherein said features are extracted regardless of a presence of occlusions and noise in the feature extraction.

17. The method of claim 11, wherein a linear search of the database is avoided.

18. A system for specifying the region layout of objects in an affine invariant manner as a set of affine intervals between pairs of regions, comprising:

means for representing database and query regions using affine intervals along with their region identity;

means for matching query region layout to layout of database image regions using an index structure; and

means for retrieving relevant images of the database by hashing for dominant hit regions in the index structure.

19. The system of claim 18, further comprising:

means for using a spatial layout representation to represent and localize said object in a pose-invariant manner.

20. The system of claim 18, further comprising:

means for extracting said regions using color for providing an illumination-invariant way of localizing colored objects.

21. The system of claim 18, further comprising:

means for using the index structure to consolidate affine interval information in the database.

22. The method of claim 18, further comprising:

means for using the index structure to avoid linearly searching through the database.

23. A system for locating a multi-feature object in an image or video database, comprising:

means for extracting regions within the images containing a multi-feature query object;

means for using in combination the feature and geometric layout to localize the object in an illumination invariant and affine-invariant manner; and

means for retrieving an image based on said localization of said object.

24. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of specifying the region layout of objects in an affine invariant manner as a set of affine intervals between pairs of regions, said method comprising:

representing database and query regions using affine intervals along with their region identity;

matching query region layout to layout of database image regions using an index structure; and

retrieving relevant images of the database by hashing for dominant hit regions in the index structure.

25. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of locating a multi-feature object in an image or video database, said method comprising:

extracting regions within the images containing a multi-feature query object;

using in combination the feature and geometric layout to localize the object in an illumination invariant and affine-invariant manner; and

retrieving an image based on said localization of said object.