Image analysis – Color image processing – Pattern recognition or classification using color
Reexamination Certificate
2000-01-28
2004-10-19
Boudreau, Leo (Department: 2721)
Image analysis
Color image processing
Pattern recognition or classification using color
C382S199000
Reexamination Certificate
active
06807298
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a method for generating a block-based image histogram from data compressed by JPEG, MPEG-1, and MPEG-2, or uncompressed image data. In particular, the method employs block-based linear quantization to generate histograms that include color, brightness, and edge components.
BACKGROUND OF THE INVENTION
JPEG is the international standard for still images and MPEG-1, 2 are for moving pictures. Regarding the compressed image information, feature information is necessary for applications such as extracting key frames, searching images, and browsing.
To extract such feature information, a brightness and color histogram that express relative frequency of brightness and color (red, green, blue) in an image is widely used. Methods comparing histograms have been proposed for searching digital video applications. As histograms are used for searching images and detecting motion change, it is proposed that conventional histograms be improved. That is, conventional single component histograms with discrete quantization and color have been developed, and therefore composite histograms that employs linear update and soft decision are adopted for effective and efficient image description.
U.S. Pat. No. 5,805,733 “Method and system for detecting scenes and summarizing video sequence” disclosed a method that employs color histograms and edge maps for detecting motion change. Though the method is effective in that it extracts color information in consideration of the human eye, it doesn't use brightness information. A method disclosed by a technical paper “Color Indexing” published by International Journal of Computer Vision receives color information and measures similarity of images by histogram intersection method. However, this method doesn't use brightness information and therefore accuracy is not good enough. Also, since the conventional methods generate histograms using a discrete quantization method, a relatively large number of histogram bins are needed to achieve good performance. Consequentially, these methods are not efficient in terms of storage and similarity measurement.
In addition, because the conventional methods perform feature extraction in terms of pixel in generating histograms, feature information is very restrictively generated.
SUMMARY OF THE INVENTION
A method for generating a block-based image histogram is provided.
A method for generating a block-based image histogram using a color information and a brightness information of an image data includes the following steps. The first step is to extract edge information of an image in terms of a block. The second step is to update edge histogram bins on the basis of the edge information to generate a global edge histogram.
Preferably, the step of extracting the edge information further comprises the following steps. The first step is to divide the block into a plurality of sub-blocks by dividing the block by half with respect to horizontal direction and dividing the block by half with respect to vertical direction. The second step is to obtain brightness representative values of the sub-blocks, respectively. The third step is to determine 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.
Preferably, the determining step determines that the edge exists and detects the edge type if the brightness difference is larger than the threshold or determines that the block is a monotone block if the brightness difference is not larger than the threshold.
Preferably, the brightness representative value of the sub-block is an average value of the pixels within the sub-block.
Preferably, the brightness representative value of the sub-block is a median value of the pixels within the sub-block.
Preferably, another method of extracting the edge information comprises the following steps. The first step is to divide 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. The second step is to obtain brightness representative values of the sub-blocks, respectively. The third step is to obtain an edge value of 0 degree, an edge value of 45 degree, an edge value of 90 degree, an edge value of 135 degree, and a complex edge value by convoluting the brightness representative values with filter coefficients. The fourth step is to determine 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 a complex edge value.
Preferably, the obtaining step of 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 is calculated by applying the brightness representative values and the filter coefficients to following equations.
edge90
=
&LeftBracketingBar;
∑
i
=
0
3
(
mean_sub
_block
(
i
)
×
edge90_filter
(
i
)
)
&RightBracketingBar;
edge0
=
&LeftBracketingBar;
∑
i
=
0
3
(
mean_sub
_block
(
i
)
×
edge0_filter
(
i
)
)
&RightBracketingBar;
edge45
=
&LeftBracketingBar;
∑
i
=
0
3
(
mean_sub
_block
(
i
)
×
edge45_filter
(
i
)
)
&RightBracketingBar;
edge135
=
&LeftBracketingBar;
∑
i
=
0
3
(
mean_sub
_block
(
i
)
×
edge135_filter
(
i
)
)
&RightBracketingBar;
complex_edge
=
&LeftBracketingBar;
∑
i
=
0
3
(
mean_sub
_block
(
i
)
×
complex_edge
_filter
(
i
)
)
&RightBracketingBar;
wherein the edge
90
_filter(i), the edge
45
_filter(i), the edge
135
_filter(i), and the complex_edge_filter(i) are filter coefficients, and wherein the mean_sub_block(i) is average brightness value of ith sub-block.
Preferably, the method for generating a block-based image histogram in accordance with an embodiment of the present invention further comprises the following step of grouping the blocks and thereby generating a local edge histogram using the edge information extracted from each block in terms of the local regions.
Preferably, the method for generating a block-based image histogram in accordance with an embodiment of the present invention further comprises the following step of grouping the local regions with respect to horizontal direction and 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.
Preferably, the global histogram, semi-global histogram, and the local histogram are normalized separately.
Preferably, the method for generating a block-based image histogram in accordance with an embodiment of the present invention further comprises the following steps. The first step is to initialize a variable k and determining a block size of level k by grouping the pixels of the image. The second step is to update related histogram bins by extracting a feature information of the image in terms of a block regarding all blocks of the level k. The Third step is to update related histogram bins by grouping blocks of level k to form a block of level k+1, merge the feature information of the level k, and extract the feature information of the image in terms of a block regarding all blocks of the level k+1.
Preferably, the method for generating a block-based image histogram using color information and brightness information of image data comprises the following steps. The first step is to extract the color information and the brightness information by employing a linear weight depending on a distance between histogram bins. The second step is to update values of the histogram bins to minimize a quantization error occurring at a boundary between the histogram bins.
Preferably, th
Choi Dong See
Kim Hyun Jin
Park Dong Kwon
Park Soo Jun
Won Chee Sun
Boudreau Leo
Electronics and Telecommunications Research Institute
Seed IP Law Group PLLC
Sherali Ishrat
LandOfFree
Method for generating a block-based image histogram does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for generating a block-based image histogram, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for generating a block-based image histogram will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3290889