Method for generating a block-based image histogram

• US 6,807,298 B1
• Filed: 01/28/2000
• Issued: 10/19/2004
• Est. Priority Date: 03/12/1999
• Status: Expired due to Term

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Park, Soo Jun, Kim, Hyun Jin, Yoo, Seong Joon, Choi, Dong See, Park, Dong Kwon, Won, Chee Sun
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHERALI, ISHRAT I
• Application Number:
  US09/493,841
• Time in Patent Office: 1,726 Days
• Field of Search: 382/165, 382/164, 382/162, 382/168, 382/232, 382/170-173, 382/224-225, 382/305, 382/199, 382/203, 382/209, 382/216-219, 707/1-6, 707/104.1, 358/403-404, 358/521-522
• US Class Current: 382/165
• 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/507 Summing image-intensity values; Histogram projection analysis

Abstract

A method for generating a block-based image histogram from data compressed by JPEG, MPEG-1, and MPEG-2, or uncompressed image data employing block-based linear quantization to generate histograms that include color, brightness, and edge components. The edge histogram, in particular, includes the global edge features, semi-global edge features, and local edge features. The global edge histogram is based on image blocks of the entire image space. The local edge histogram is based on a group of edge blocks. The semi-global edge histogram is based on the horizontally and the vertically grouped image blocks. A method for generating block-based image histogram with color information and brightness information of image data in accordance with an embodiment of the present invention extracts feature information of an image in terms of the block and updates global histogram bins on the basis of the feature information. The method for generating block-based image histogram with color information and brightness information of image data minimizes quantization error by employing linear weight and updates values of histogram bins. The error that occurs at a boundary between bins of the histograms and the linear weight depends on the distance between the histogram bins.

Claims

1. A method for generating a block-based image histogram using color information and brightness information of an image data, comprising:

extracting edge information of an image in terms of a blocks having a plurality of pixels in the block; and

updating edge histogram bins on the basis of the edge information to generate a global edge histogram;

wherein extracting edge information further comprises;

dividing the block into a plurality of sub-blocks by dividing the block by half with respect to a horizontal direction and dividing the block by half with respect to a vertical direction;

obtaining brightness representative values of the sub-blocks, respectively; and

determining if an edge exists in the block and determining an edge type by comparing a brightness difference between the adjacent sub-blocks with a threshold.

2. The method for generating a block-based image histogram of claim 1, wherein determining comprises determining that the edge exists and detecting the edge type if the brightness difference is larger than the threshold or determining that the block is a monotone block if the brightness difference is not larger than the threshold.

3. The method for generating a block-based image histogram according to claim 1, wherein the brightness representative value of the sub-block is an average value of the pixels within the sub-block.

4. The method for generating a block-based image histogram of claim 1, wherein the brightness representative value of the sub-block is a median value of the pixels within the sub-block.

5. The method for generating a block-based image histogram of claim 1, wherein extracting edge information further comprises:

dividing the block into four sub-blocks by dividing the block by half with respect to a horizontal direction and dividing the block by half with respect to a vertical direction;

obtaining brightness representative values of the sub-blocks, respectively;

obtaining an edge value of 0 degrees, an edge value of 45 degrees, an edge value of 90 degrees, an edge value of 135 degrees, and a complex edge value by convoluting the brightness representative values with filter coefficients; and

determining if an edge exists in the block and determining an edge type by comparing a maximum edge value with a threshold, wherein the maximum edge value is the largest value among the edge value of 0 degrees, the edge value of 45 degrees, the edge value of 90 degrees, the edge value of 135 degrees, and the complex edge value.

6. The method for generating a block-based image histogram according to claim 5, wherein obtaining the edge value of 0 degrees, the edge value of 45 degrees, the edge value of 90 degrees, the edge value of 135 degrees, and the complex edge value comprises calculating by applying the brightness representative values and the filter coefficients to the following equations;

$\begin{array}{cc}\mathrm{edge90}=<br><br>\underset{i=0}{\overset{3}{\sum <br><br>}}<br><br>\left(\mathrm{mean\_sub}<br><br>\mathrm{\_block}<br><br>\left(i\right)\times <br><br>\mathrm{edge90\_filter}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i\right)\right)<br><br><br><br><br><br>\mathrm{edge0}=<br><br>\underset{i=0}{\overset{3}{\sum <br><br>}}<br><br>\left(\mathrm{mean\_sub}<br><br>\mathrm{\_block}<br><br>\left(i\right)\times <br><br>\mathrm{edge0\_filter}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i\right)\right)<br><br><br><br><br><br>\mathrm{edge45}=<br><br>\underset{i=0}{\overset{3}{\sum <br><br>}}<br><br>\left(\mathrm{mean\_sub}<br><br>\mathrm{\_block}<br><br>\left(i\right)\times <br><br>\mathrm{edge45\_filter}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i\right)\right)<br><br><br><br><br><br>\mathrm{edge135}=<br><br>\underset{i=0}{\overset{3}{\sum <br><br>}}<br><br>\left(\mathrm{mean\_sub}<br><br>\mathrm{\_block}<br><br>\left(i\right)\times <br><br>\mathrm{edge135\_filter}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i\right)\right)<br><br><br><br><br><br>\mathrm{complex\_edge}=<br><br>\underset{i=0}{\overset{3}{\sum <br><br>}}<br><br>\left(\mathrm{mean\_sub}<br><br>\mathrm{\_block}<br><br>\left(i\right)\times <br><br>\mathrm{complex\_edge}<br><br>\mathrm{\_filter}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i\right)\right)<br><br>& \left[\mathrm{Equation}\right]\end{array}$

wherein the edge90_filter(i), the edge45_filter(i), the edge135_filter(i), and the complex_edge_filter(i) are filter coefficients, and wherein the mean_sub_block(i) is average brightness value of an ith sub-block.

7. The method for generating a block-based image histogram of claim 5, wherein determining comprises determining the maximum edge value as a representative edge of the block if the maximum edge value is larger than the threshold or determines the block as a monotone block if the maximum edge value is not larger than the threshold.

8. The method for generating a block-based image histogram of claim 1, further comprising:

grouping the blocks and generating a local edge histogram using the edge information extracted from each block in terms of the local regions.

9. The method for generating a block-based image histogram of claim 1, further comprising;

grouping the local regions with respect to a horizontal direction and a vertical direction and thereby generating a semi-global edge histogram using the edge information extracted from each block in terms of the semi-global regions.

10. The method as recited in claim 8, wherein the global edge histogram bins is normalized by being divided by the total number of blocks that exist in the global region.

11. The method as recited in claim 8, wherein the local edge histogram bins are normalized by being divided by the total number of block in the local region.

12. The method as recited in claim 9, wherein the semi edge histogram bins are normalized by being divided by the total number of block in the semi-global region.