Method of extracting and searching integral histograms of data samples

• US 20060177131A1
• Filed: 02/07/2005
• Published: 08/10/2006
• Est. Priority Date: 02/07/2005
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Porikli, Fatih M.
• Granted Patent: US 7,454,058 B2
• Time in Patent Office: Days
• US Class Current: 382/168
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/30201 Face
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• 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/758 Involving statistics of pixels or of feature values, e.g. histogram matching

Abstract

A computer implemented method extracts an integral histogram from sampled data, such as time series data, images, and volumetric data. First, a set of samples is acquired from a real-word signal. The set of samples is scanned in a predetermined order. For each current sample, an integral histogram integrating a histogram of the current sample and integral histograms of previously scanned samples is constructed.

Claims

1. A computer implemented method for extracting an integral histogram from sampled data, comprising:

acquiring a set of samples from a real-word signal;

scanning the set of samples in a predetermined order; and

constructing, for each current sample, an integral histogram, the integral histogram integrating a histogram of the current sample and the integral histograms of previously scanned samples.

2. The method of claim 1, in which the scanning is in a left to right and then a top to bottom order.

3. The method of claim 1, in which the set of samples is a d-dimensional array, and in which a range of values for each dimension is N_d with associated k-dimensional tensors.

4. The method of claim 1, in which the integral histogram includes a plurality of bins, and a size of each bin is an integer number.

5. The method of claim 4, in which the size is a power of two.

6. The method of claim 1, in which the set of samples is a one-dimensional time series.

7. The method of claim 1, in which the set of samples is a two-dimensional gray-level image.

8. The method of claim 1, in which the set of samples is a color image.

9. The method of claim 1, in which the set of samples is volumetric data.

10. The method of claim 1, in which the set of samples is a video, and further comprising:

constructing a similarity map from the integral histogram.

11. The method of claim 10, in which the similarity map is used to detect an object in the image.

12. The method of claim 7, in which the similarity map is used to detect textures in the image.

13. The method of claim 1, further comprising:

combining the integral histogram spatially.

14. The method of claim 1, further comprising:

combining the integral histogram hierarchally.

15. The method of claim 1, further comprising:

combining the integral histogram according to a model.

16. The method of claim 1, in which the set of samples is an image, and further comprising:

specifying target regions in the image according to corner points in a Cartesian space;

determining the integral histogram for the target regions; and

normalizing the integral histogram with respect to a size of the target regions in the image to obtain a normalized histogram.

19. The method of claim 1, in which the set of samples is an image, and further comprising:

constructing higher-level features by combining the integral histograms of intensity, color, texture, gradient, motion, orientation, template matching, and image filter responses of the image.

17. The method of claim 17, further comprising:

adding bin values of the integral histogram of a lower-right corner point that correspond to a largest target region in the image to bin values of the integral histogram of an upper-left corner point in the image that correspond to a smallest target region, and

subtracting the bin values of the upper-right and lower-left corner point integral histograms.

18. The method of claim 17, further comprising:

determining a distance between the normalized histogram and the integral histograms of the target regions.