Histogram methods and systems for object recognition

• US 9,811,757 B2
• Filed: 08/01/2016
• Issued: 11/07/2017
• 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:
  US15/224,975
• Publication Number:
  US 20170032213A1
• Time in Patent Office: 463 Days
• 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 comprising the acts:

determining, for each of plural pixels in a received input image, three data, the first datum indicating a value of a first color parameter at said pixel, the second datum indicating a value of a second color parameter at said pixel, and the third datum indicating a value of a luminance parameter at said pixel;

generating a histogram for the received input image, said histogram comprising (a) first data indicating a count of pixels in the received input image having said determined first datum within each of M quantized first color parameter value ranges, (b) second data indicating a count of pixels in the received input image having said determined second datum within each of M quantized second color parameter value ranges, and (c) third data indicating a count of pixels in the received input image having said determined third datum within each of N quantized luminance parameter ranges; and

comparing the generated histogram against a collection of reference histograms to identify a reference histogram that corresponds to the generated histogram, to thereby identify the input image;

wherein at least said act of generating the histogram is performed by a cell phone that includes a programmable device that executes software instructions read from a memory, a camera, a touchscreen and a display; and

N is less than half of M.

2. The method of claim 1 wherein N is one-fourth of M.

3. The method of claim 1 in which M is 16 and N is 4.

4. The method of claim 1 wherein N is three-sixteenths of M.

5. The method of claim 1 in which the M is 16 and N is 3.

6. The method of claim 1 wherein N is one-eighth of M.

7. The method of claim 1 in which M is 16 and N is 2.

8. The method of claim 1 in which the luminance parameter for each of said pixels comprises a value of a derivative of the input image luminance at said pixel.

9. The method of claim 8 in which N is three:

one of said three quantized luminance parameter ranges counting pixels for which the derivative value has an absolute value less than a threshold value, another of said three quantized luminance parameter ranges counting pixels for which the derivative value is above said threshold value, and a third of said quantized luminance parameter ranges counting pixels for which a negative of said derivative value is above said threshold value.

10. The method of claim 8 in which N is two:

one of said two quantized luminance parameter ranges counting pixels for which the derivative value is above a threshold value, and a second of said two quantized luminance parameter ranges counting pixels for which a negative of said derivative value is above said threshold value.

11. The method of claim 1 in which the luminance parameter for each of said pixels comprises a value of a second derivative function of the input image luminance at said pixel.

12. The method of claim 11 in which the said second derivative function comprises a Laplacian of Gaussian operator.

13. The method of claim 11 in which the said second derivative function comprises a Laplacian operator.

14. The method of claim 11 in which the said second derivative function comprises a difference of Gaussians operator.

15. The method of claim 1 wherein the generated histogram is a 3D histogram.

16. The method of claim 1 wherein said M quantized first color parameter value ranges are non-uniformly quantized.

17. The method of claim 1 in which said first determined datum indicates a value of the first color parameter along a red-green color axis, and said second determined datum indicates a value of the second color parameter along a blue-yellow color axis, and the method further includes normalizing opponent color directions by a difference between the maximum of {three red/green/blue color values} at a pixel, and a minimum of said {three red/green/blue color values} at said pixel.

18. The method of claim 17 in which said first determined datum comprises a value RG′

along the red-green color axis, and said second determined datum comprises a value BY′

along the blue-yellow color axis, and the method further includes normalizing opponent color directions by a difference between the maximum of {three red/green/blue color values} at a pixel, and a minimum of said {three red/green/blue color values} at said pixel, wherein;

Max Val=Max(R,G,B);

Min Val=Min(R,G,B);

RG′

=(R−

G)/(Max Val−

Min Val); and

BY′

=(B−

0.5*(R+G))/(Max Val−

Min Val).

19. The method of claim 1 wherein the first datum indicates a value of color contrast parameter at said pixel.

20. An image processing system comprising a memory, a programmable device that executes software instructions read from said memory, a camera, a touchscreen, and a display, said software instructions causing the system to perform acts including:

determining, for each of plural pixels in a received input image, three data, the first datum indicating a value of a first color parameter at said pixel, the second datum indicating a value of a second color parameter at said pixel, and the third datum indicating a value of a luminance parameter at said pixel;

generating a histogram for the received input image, said histogram comprising (a) first data indicating a count of pixels in the received input image having said determined first datum within each of M quantized first color parameter value ranges, (b) second data indicating a count of pixels in the received input image having said determined second datum within each of M quantized second color parameter value ranges, and (c) third data indicating a count of pixels in the received input image having said determined third datum within each of N quantized luminance parameter ranges; and

comparing the generated histogram against a collection of reference histograms to identify a reference histogram that corresponds to the generated histogram, to thereby identify the input image;

wherein N is less than half of M.