Image analysis – Color image processing – Image segmentation using color
Reexamination Certificate
1999-07-22
2002-11-19
Mancuso, Joseph (Department: 2623)
Image analysis
Color image processing
Image segmentation using color
C382S170000, C382S171000, C358S515000, C358S538000
Reexamination Certificate
active
06483940
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method for dividing image by descending number of color, and more particularly, to a method for dividing image in accordance with inflection on a distribution curve of image pixel versus color coordinate.
2. Description of the Prior Art
When a traditional technology is used to divide an image, pixels of similar color are classified into a cluster region, so an image can be classified into a plurality of cluster regions. Finally, if any pixel is not classified into one of the existed cluster regions, determine the distance between the color of the pixel and that of every existed cluster region. Then joint the pixel to the existed cluster that has the shortest distance of color to the pixel, in other words, the pixel is classified into the cluster. So the color of the pixel is replaced with the color of the color of the existed cluster that has shortest distance to the pixel mentioned above. So all the pixels of the image are classified into the plurality of cluster regions.
The color histogram of an image is frequently used in dividing an image into a plurality of cluster regions, especially the color of a region having a local maximum within the color histogram is assigned as the principal color of the cluster region. When dividing an image into several cluster regions, the relation between the image mentioned above and its color histogram is shown in FIG.
1
. The image
1
includes a plurality of pixels, and the statistic for the number of pixel having a color on color coordinate acquires its color histogram
2
. Then find a first local maximum value
3
, and set up first threshold value
4
. Next, by the same way, a second local maximum value
5
, its second threshold value
6
, the third local maximum value
7
, its third threshold value
8
, the fourth local maximum value
9
, and its fourth threshold value
10
. Every local maximum value is actually a value on the color coordinate. Subsequently, assign the color of the pixel having the local maximum value to be the color of the pixels of the cluster region enclosing the pixel having the local maximum value. In other words, the principle color of a cluster region is assigned to be the color of the pixel enclosed by the cluster region, which having the local maximum value. Next, calculate the distance from the color of the pixel beyond the plurality of cluster regions to the plurality of local maximum values. So a plurality of distance is acquired, then select a minimum distance from the plurality of distance. The principle color of the cluster region having the minimum distance to the pixel beyond the plurality of cluster regions is assigned as the color of the pixel beyond the plurality of cluster regions. Then it is defined that the pixel beyond the plurality of cluster regions is joint to a cluster region which having minimum distance to the pixel. Also, it is defined that, the pixel is classified to a cluster region. Proceeding with the steps mentioned above continuously until all the pixels of the image is classified into one of the existed cluster regions. Through the steps mentioned above, thus obtain a plurality of cluster regions which including all pixels of image
1
. For example, as shown in
FIG. 1
, the first cluster region
13
in image
1
includes the pixels having the color the same as the principle color of the first local maximum value
3
illustrated in the color histogram
2
. Similarly, the second cluster region
15
in image
1
includes the pixels having the color the same as the principle color of the second local maximum value
5
illustrated in the color histogram
2
. The third cluster region
17
in image
1
includes the pixels having the color the same as the principle color of the first local maximum value
7
illustrated in the color histogram
2
. The fourth cluster region
19
in image
1
includes the pixels having the color the same as the principle color of the fourth local maximum value
9
illustrated in the color histogram
2
.
The colorful-image dividing method mentioned above is a technology utilizing a moving window to look for a local maximum value in the color histogram. Because the colorful-image dividing method mentioned above does not analysis the color histogram according to the feature of color distribution, thus the obtained principle colors does not fully match the color distribution of the image. Furthermore, the size of the moving window as well as the threshold values are the fixed values set up by the user, i.e., the window size and the threshold values are not set up according to the actual color distribution. So the exactly color distribution can not be obtained, and the resulted color division does not actually fit the color distribution of the colors on the image. Also, the division does not fit the actual color distribution, so the resulted principle color of the cluster region is not correct. In conclusion, the traditional method mentioned above can not properly reduce the number of color of the image.
SUMMARY OF THE INVENTION
According to the prior art mentioned above, the traditional method utilized to divide a pre-processed image utilize the manually determined threshold value as the criterion when dividing the image, so it is impossible to divide the image according to the characteristic of color distribution of the pre-processed image. Thus the traditional method can not divide the image correctly.
A purpose of the present invention is to avoid using the fixed threshold value to divide the image, instead, the present invention uses the convex portion of a function to obtain the plurality of cluster regions. The function mentioned above is obtained by a smoothed histogram of the image, so the cluster regions are acquired according to the characteristic of the distribution of color of the pre-processed image. The present invention is used to divide a pre-processed image into a plurality of cluster regions, such that all the pixels of the pre-processed image are classified into any one of the plurality of cluster regions. In other words, the pre-processed image is divided into a plurality of cluster regions.
According to the purpose mentioned above, the method used to divide an image is disclosed herein. The method divide an image into a plurality of cluster regions, each has its own principle color, and every pixel of the image is classified into one of the plurality of cluster regions. The method mentioned above includes the following steps.
At first, acquire a three dimensional histogram of the image by counting the number of pixels of the image based on three dimensional color coordinate. Then smooth the three dimensional histogram by a numerical diffusion method to obtain a function. The function can be a normal distribution probability function. Next, define a plurality of cluster regions on the image, thus the pixels within the plurality of cluster regions correspond to convex portion of the function. Subsequently, assign the color of each pixel of the image as a principle color of a first cluster region among the plurality of cluster regions. The principle color is equal to average of all pixels within the cluster region, the average is equal to A/B, wherein A is summation of color of pixels within the first cluster region, and B is equal to the number of pixels within the first cluster region. The color of the pixel is represented by the three color coordinate, and each of the plurality of cluster regions have a corresponding principle color. Finally, joint an unclassified pixel to a cluster region of the plurality of cluster regions according to minimum distance from the unclassified pixel to the plurality of cluster regions. The unclassified pixel is outside the plurality of cluster regions before this joint step, after all pixels of the image have being jointed to one of the plurality of cluster regions, the image is divided into the plurality of cluster regions.
REFERENCES:
patent: 5047842 (1991-09-01), Bouman, Jr. et al.
patent: 5649025 (1997-07-01), Revankar
Baker & Botts LLP
Bhatnagar Anand
Institute for Information Industry
Mancuso Joseph
LandOfFree
Method for dividing image 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 dividing image, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for dividing image will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2935097