Histogram methods and systems for object recognition

• US 9,135,520 B2
• Filed: 07/01/2014
• Issued: 09/15/2015
• Est. Priority Date: 05/19/2009
• Status: Active Grant

• Current Assignee: Digimarc Corporation
• Original Assignee: Digimarc Corporation
• Inventors: Sharma, Ravi K.
• Primary Examiner(s): COUSO, JOSE L
• Application Number:
  US14/321,415
• Publication Number:
  US 20150010231A1
• Time in Patent Office: 441 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 10/56 relating to colour
• CPC Class Codes: H04M 2250/52 including functional features of a camera constructional features concerning the integration of cameras in portable phones H04M1/0264

Abstract

A multidimensional histogram is used to characterize an image (or object), and is used to identify candidate matches with one or more reference images (or objects). An exemplary implementation employs hue information for two of the dimensions, and a second derivative function based on luminance for a third dimension. The simplicity and speed of the detailed arrangements make them well suited for use with cell phones and other mobile devices, which can use the technology for image/object recognition, e.g., in visual search applications.

Claims

1. A method for matching test imagery to reference imagery, comprising the acts:

generating color histogram data that corresponds to test imagery captured by a camera-equipped mobile device;

matching said test imagery color histogram data with color histogram data that corresponds to reference imagery, said matching being performed by a hardware processor of said camera-equipped mobile device;

said test imagery histogram data and said reference imagery histogram data comprising values corresponding to a plurality of quantized bins; and

said matching including determining one or more of the following;

a. a number of occupied bins in the test and reference imagery histograms;

b. a number of occupied bins common to both the test imagery and reference imagery histograms;

c. a number of occupied bins combined between both the test imagery and reference imagery histograms;

d. a number of pixels common to both the test imagery and reference imagery histograms (histogram intersection);

e. a percentage of occupied bins of the test imagery histogram that are occupied in the reference imagery histogram;

f. a ratio of said histogram intersection to number of occupied bins of the test imagery histogram;

g. nonzero bins of test imagery histogram;

h. nonzero bins of reference imagery histogram;

i. nonzero bins of test imagery histogram that are a subset of nonzero bins of reference imagery histogram;

j. a number of nonzero bins of test imagery histogram that are a subset of nonzero bins of reference imagery histogram;

k. nonzero bins of reference imagery histogram that are a subset of nonzero bins of test imagery histogram; and

l. a number of nonzero bins of reference imagery histogram that are a subset of nonzero bins of test imagery histogram.

2. The method of claim 1 that includes combining two or more of (a)-(l) in connection with said matching.

3. The method of claim 1 that includes treating as empty any bins having less than a threshold value.

4. The method of claim 1 in which said matching includes determining a number of occupied bins in the test and reference imagery histograms.

5. The method of claim 1 in which said matching includes determining a number of occupied bins common to both the test imagery and reference imagery histograms.

6. The method of claim 1 in which said matching includes determining a number of occupied bins combined between both the test imagery and reference imagery histograms.

7. The method of claim 1 in which said matching includes determining a number of pixels common to both the test imagery and reference imagery histograms.

8. The method of claim 1 in which said matching includes determining a percentage of occupied bins of the test imagery histogram that are occupied in the reference imagery histogram.

9. The method of claim 1 in which said matching includes determining a ratio of said histogram intersection to number of occupied bins of the test imagery histogram.

10. The method of claim 1 in which said matching includes determining nonzero bins of said test imagery histogram.

11. The method of claim 1 in which said matching includes determining nonzero bins of said reference imagery histogram.

12. The method of claim 1 in which said matching includes determining nonzero bins of said test imagery histogram that are a subset of nonzero bins of reference imagery histogram.

13. The method of claim 1 in which said matching includes determining a number of nonzero bins of test imagery histogram that are a subset of nonzero bins of reference imagery histogram.

14. The method of claim 1 in which said matching includes determining nonzero bins of reference imagery histogram that are a subset of nonzero bins of test imagery histogram.

15. The method of claim 1 in which said matching includes determining a number of nonzero bins of reference imagery histogram that are a subset of nonzero bins of test imagery histogram.

16. A method for matching test imagery to reference imagery, comprising the acts:

generating color histogram data that corresponds to test imagery captured by a camera-equipped mobile device;

matching said test imagery color histogram data with color histogram data that corresponds to reference imagery, said matching being performed by a hardware processor of said camera-equipped mobile device;

said test imagery histogram data and said reference imagery histogram data comprising values corresponding to a plurality of quantized bins; and

said matching including disregarding bins of the test imagery histogram that are unoccupied in the reference imagery histogram, and performing a comparison between remaining bins of the test imagery histogram and bins of the reference imagery histogram.

17. The method of claim 16 that includes treating as unoccupied any bins having less than a threshold value.

18. A method for matching test imagery to reference imagery, comprising the acts:

generating color histogram data that corresponds to test imagery captured by a camera-equipped mobile device;

matching said test imagery color histogram data with color histogram data that corresponds to reference imagery, said matching being performed by a hardware processor of said camera-equipped mobile device;

said test imagery histogram data and said reference imagery histogram data comprising values corresponding to a plurality of quantized bins; and

said matching including (a) checking whether at least a majority of occupied bins of the test imagery histogram are a subset of the occupied bins in the reference imagery histogram, and (b) checking that counts of at least some of the bins in the test imagery histogram are larger than corresponding counts for the reference imagery histogram;

wherein test imagery can be matched to reference imagery despite zooming-in.

19. The method of claim 18 that includes treating as unoccupied any bins having less than a threshold value.

20. The method of claim 18 that further includes performing a regression analysis to determine a scale factor that represents a relationship between bin counts in the test imagery and reference imagery histograms.