TWI385595B - Image segmentation method using image region merging algorithm - Google Patents

Description

Image segmentation method using image region merging algorithm

The invention relates to an image segmentation method, in particular to an image segmentation method using an image region merge algorithm.

The development of computer imaging technology and tools has become more and more mature, and the image of realistic appearance has once again gained the development of imaginary space. Therefore, various related technologies of image processing are born, and image segmentation is one of the important processes that cannot be lacked.

In simple terms, image segmentation can be defined as: dividing a digital image into several regions, and these regions composed of pixels must be connected by similar pixels. In addition, the purpose of image segmentation is to segment images according to the objects formed by the images, so that the computer has the ability to analyze image features like humans. To achieve this goal, the computer must have enough knowledge to recognize the content of the image. For example, the broadcaster broadcasts the news in the studio. The broadcaster is part of the foreground, and the image other than the broadcaster belongs to the background of the studio. If the image segmentation is performed by this principle, the broadcaster can be taken from the image. Split it out.

Therefore, the image segmentation technology described above can be further utilized in the image feature capture field, and the image feature capture is a feature that can be represented by the image, such as the color distribution in the image and the texture of the image. And the characteristics of the distribution of objects in the image. The easiest way to get the color distribution in an image is through the histogram of the color. For example, converting the red distribution position and intensity of an image into red The histogram of the color distribution, comparing the histograms of different image colors, can roughly see the similarity. The characteristics of the image texture can be explored by the directionality or repeatability of the texture. For example, some wood lines are horizontal and some wood lines are vertical.

Today's image segmentation can be used mainly for: (1) military purposes, such as the detection of set features, such as tanks in motion, or the search for landmarks in aerial maps.

(2) Industrial uses, such as passive component positioning and defect detection technology; (3) environmentally friendly uses, such as control measurements for environmental changes or regional disaster assessments due to natural disasters.

(4) Target search is beneficial to strengthen the target of interest and weaken irrelevant image components. For example, the police want to identify the vehicle tracking system from various objects on the road or other such as automatic building monitoring system and face recognition system. And road traffic calculations, etc.

Furthermore, the main technical means of image segmentation can be roughly divided into two stages: (1) image quantization, the purpose of which is to reduce the color used by the image. The step of image quantization can be roughly divided into two parts, the first is to obtain the main representative color in the image, and the second is to replace the original color of the image with the representative color. There are many ways to capture color, which is generally achieved by clustering. The easiest way is to use the k-mean algorithm, first determine the number of categories (that is, the value of k), then generate k seeds in random numbers, and calculate the data points themselves and each seed for each data point. The distance and classify this data point into the category with the smallest distance. Then calculate The average of each class, and the average as the new seed, repeat the above classification work until the data points of each category no longer change.

As for color replacement, the general approach is to calculate the distance between the color of the pixel and each representative color for each pixel in the image, and then replace the color of the pixel with the representative color with the smallest distance.

(2) Image area merging, the purpose of which is to merge a plurality of smaller areas formed by initial segmentation of the image into larger and more meaningful areas for subsequent applications. The general method of merging is to start with a small area and merge it into the area adjacent to it and closest to the color until all existing areas are larger than a certain area.

However, in the above existing method, when merging image regions, the conventionally used merging method starts from a small region and merges it into the region adjacent to and closest to the color until all existing regions are larger than certain. The area is up to now. Since the colors between the initial regions formed by image quantization are not too similar, the results obtained by considering only the colors to merge are often inconsistent with human perception.

Therefore, how to develop a better image area merging technology for the improvement of the above-mentioned prior art deficiencies has become a direction that the relevant industry is trying to study.

Accordingly, it is an object of the present invention to provide an image segmentation method using an image region merging algorithm.

Therefore, the image segmentation method using the image region merging algorithm of the present invention comprises the following steps: (a) inputting an original image, and performing a quantization operation on the original image to obtain a quantized image and a plurality of color regions in the quantized image.

(b) performing an importance evaluation on each color region in the quantized image by an importance indexing operation to obtain a complex importance index value corresponding to the color regions.

(c) determining whether the importance index value of the color regions is lower than a threshold value, and if so, using a merge possibility operation to evaluate and merge each color region below the threshold value, and then obtain a first A combined result.

(d) Output a split image.

The invention has the effect of processing the original image through the quantization operation processing, the importance indexing operation, and the merging possibility operation to generate the segmented image, thereby achieving the purpose of improving the prior art.

The above and other technical contents, features and advantages of the present invention will be apparent from the following detailed description of the preferred embodiments.

Referring to FIG. 1 to FIG. 3 and FIG. 1 to FIG. 3, a preferred embodiment of the image segmentation method using the image region merging algorithm of the present invention comprises the following steps: First, as shown in step 11, an original image 20 is input, and A quantization operation is performed on the original image 20 to obtain a quantized image 21 and a plurality of color regions 22 in the quantized image 21.

It is worth mentioning that in the preferred embodiment, the quantization operation is The method includes the following steps: first, as shown in step 111, a mode conversion operation is performed on the original image 20 to obtain a plurality of first image values 30; and the mode conversion job actually divides the original image 20 into a plurality of color channels (ie, the first image values 30) as shown in FIG. 2; and the color channels are divided into a brightness channel 31, a U color difference channel 32, and a V color difference channel 33, which are commonly used in related fields. YUV.

Next, as shown in sub-step 112, an analysis processing operation is performed on the first image values 30 such that the first image values 30 become a plurality of second image values 40 as shown in FIG.

Then, as shown in sub-step 113, the second image values 40 are combined into a plurality of color candidates as shown in Annex 2.

Next, as shown in sub-step 114, a sort numbering operation is performed on the color candidate candidates to replace the complex original color of the original image with the color candidate to obtain the quantized image. Here, we create a color correspondence table as shown in Annex 3 for all color candidates, and combine these unordered color numbers into strings and sort and number them. And taking the original color of the original image as an index, looking up the table to obtain the corresponding color candidate, and using the binary search method to obtain the number of each color candidate, quantizing the original image, and replacing the original color with the original color A color candidate is obtained, and a quantized image 21 and a plurality of color regions 22 are obtained. Therefore, the time complexity of each pixel color replacement is changed from Cn to log ₂ Cn +1. Save a lot of computing time.

It is additionally noted that, as shown in FIGS. 2 and 3, the analysis processing operation smoothes the original histogram using a non-parametric density function. The detailed operation details are: for each level of the histogram, the density estimation core function is used to calculate the contribution of other levels to the level and summed to obtain the average value as a new histogram function value, and finally The selection of the local maximum values yields the second image values 40. However, the relationship between the aforementioned core functions, core values and other related parameters can be known by the following formula: f(x) : represents the non-parametric density function h(r) : represents a histogram of any of the three color channels r _k : represents the kth level of a color channel K _σ ( x ): represents the density estimation core Function σ: represents the bandwidth of the density estimation core function M : represents the total number of levels of a color channel

2 is an image of the individual histogram function after the original image 20 is converted by the YUV channel, and after the above-mentioned operation processing, a histogram function graph as shown in FIG. 3 is obtained. In this example, each histogram function graph can just select three local maximum values, and then obtain the second image values of the nine (as indicated by the circle in FIG. 3).

Next, as shown in step 12, the importance of each color region 22 in the quantized image 21 is evaluated by an importance indexing operation, and the complex importance index values corresponding to the color regions 22 are obtained. .

It is worth mentioning that the importance index of a certain area is obtained by dividing the number of pixels of the area by the sum of the number of pixels of all the color areas 22, and dividing by all the areas 22 of the same color as the area. The number of pixels of the largest area is obtained, and the importance index value of each color area 22 is obtained, and the obtained importance index values are sorted from small to large; and the aforementioned importance index value can use the following formula achieve: R ⁱ _j : the region where the color number is i and the region index is j . Imp(R ⁱ _j ) : The importance index of R' _j : Number of pixels of R ⁱ _j Mor ( N _R' ): the number of pixels in the region with the color number i : Image size m : number of initial areas

Then, as shown in step 13, it is determined whether the importance index value of the color regions 22 is lower than a threshold value. If not, as shown in step 15, a first merge result is obtained; if yes, then Step 14 shows that each color region 22 below the threshold value is evaluated and merged by using a merge possibility job, and it is sequentially checked whether there is a next color region and the merge possibility operation is required, and finally, The first combined result 23 as shown in step 15 (in the preferred embodiment, 7 regions are indicated by the numbers 0 to 6 in the attached example), and then step 18 is performed.

The combination of each of the two color regions 22 mentioned in the above steps 13 to 15 replaces the merged color number with another color number, and the new color is the weighted average of the ratio of the two regions. .

In addition, in the preferred embodiment, the merge possibility operation first calculates color distance values and boundary length values between each color region 22 below the threshold value and each color region 22 adjacent thereto. And the area value of each color region 22 adjacent thereto. Then a consolidation possibility is calculated by the following combination probability formula: ML ( a, k ) merging possibility between regions a and k CD ( a, k ) color distance between regions a and k BL ( a, k ) boundary length RS ( k ) between regions a and k The area size w ₁ , w ₂ , w _{3 of the} area k is the weight of the item such as the color distance, the boundary length and the area size, respectively. The maximum value function is simply, the above expression is to represent any two colors. The closer the colors between the regions 22 are, the longer the boundary length is, and the smaller the area is, the stronger the possibility of merging between the two color regions 22, and therefore the two color regions 22 should be merged together.

Then, as shown in step 16, the first merge result 23 is subjected to a second merge using an overall similarity evaluation to obtain a second merge result 24. In the preferred embodiment, the overall similarity assessment is achieved by performing the importance indexing operation and the merge possibility job again on the first merge result 23.

Finally, as shown in step 17, a segmented image 25 labeled with a plurality of dividing lines is output.

In summary, the image segmentation method of the image region merging algorithm is mainly used to obtain the quantized image 21 and the color regions by using the mode conversion operation, the analysis processing operation, and the number sorting operation. 22. Thereafter, the first merge result 23 is obtained by the importance indexing operation and the merge possibility job (which may be collectively referred to as an image area merge algorithm), and may even be performed by using an overall similarity evaluation as needed. The second merge operation is performed to obtain the second merge result 24, and finally the split image 25 is generated.

In addition, in view of the existing improvement using only the lack of color distance combination, the above-mentioned importance indexing operation and the use of the merged possibility operation not only consider the homogeneity of color when merging, but also consider the geometry between regions. The characteristics, therefore, greatly reduce the situation of excessive segmentation caused by the conventional method, and therefore, the segmentation result obtained by the image segmentation method using the image region merging algorithm of the present invention is closer to the human perception, so It is indeed possible to achieve the object of the present invention.

However, the above is only a preferred embodiment of the present invention, and is not intended to limit the scope of the present invention, that is, the simple equivalent changes and modifications made by the scope of the present invention and the description of the invention. All remain within the scope of the invention patent.

11~17‧‧‧Steps

111~114‧‧ steps

20‧‧‧ original image

21‧‧‧Quantified images

22‧‧‧Color area

23‧‧‧ First combined results

24‧‧‧Second combined results

25‧‧‧Split image

30‧‧‧ first image value

31‧‧‧Brightness channel

32‧‧‧U color difference channel

33‧‧‧V color difference channel

40‧‧‧second image value

1 is a flow chart illustrating a process flow of a preferred embodiment of the image segmentation method of the present invention; FIG. 2 is a set of histograms illustrating the conversion of the original image into a plurality of first image values in the preferred embodiment; FIG. 3 is a set of histograms illustrating the conversion of the first image value into a plurality of second image values in the preferred embodiment.

[A brief description of the attachment]

Attachment 1 is a set of image diagrams showing an individual difference between an original image, a quantized image, a complex color region, a first merge result, a second merge result, and a split image in the preferred embodiment; 2 is a schematic diagram illustrating a color candidate sub-view formed by combining a plurality of second image values in the preferred embodiment; and Attachment 3 is a correspondence table illustrating the closest color candidate candidate correspondence tables of the color candidates from the original colors.

11~17‧‧‧Steps

111~114‧‧ steps

Claims (14)

An image segmentation method using an image region merging algorithm includes the following steps: (a) inputting an original image, and performing a quantization operation on the original image to obtain a quantized image and a plurality of color regions in the quantized image; (b) performing an importance evaluation on each color region in the quantized image by an importance indexing operation to obtain a complex importance index value corresponding to the color regions; (c) determining the color regions Whether the importance index value is lower than a threshold value, and if so, using a merge possibility operation to evaluate and merge each color region below the threshold value, and then obtain a first merge result, wherein the merge The possibility operation is to calculate the color distance value and the boundary length value between each color region adjacent to the threshold region and each adjacent color region, and the area value of each adjacent color region. Next, a merge possibility formula is used to calculate an adjacent region in which the region should be merged; and (d) a split image is output. The image segmentation method using an image region merging algorithm according to claim 1, wherein in the step (b), the importance indexing operation is performed by respectively squaring the number of pixels in each color region. Divide by the sum of the number of pixels in all color regions, and divide by the number of pixels in the largest region of all color regions to obtain the importance index value for each color region. The image segmentation method using the image region merging algorithm according to item 2 of the patent application scope further includes a step (e) between the step (c) and the step (d), and the first combined result is performed. An overall similarity assessment of the combined operations yields a second combined result. An image segmentation method using an image region merging algorithm according to claim 3, wherein in the step (e), the overall similarity evaluation merging operation is to perform the importance again on the first merging result Index jobs and merge possibility jobs. According to the image segmentation method of the image region merging algorithm according to the fourth aspect of the patent application, in the step (a), the quantization operation process first performs a mode conversion operation on the original image, and becomes a plural number. And performing, by the first image value, an analysis processing operation on the first image values, so that the first image values become a plurality of second image values, and then combining the second image values into a plurality of color candidates, and Performing a sort numbering operation on the color candidate to replace the complex original color of the original image with the color candidate to obtain the quantized image. An image segmentation method using an image region merging algorithm according to claim 5, wherein in the sorting number operation of the step (a), the replacement of the original colors is indexed by the original colors And querying a color candidate candidate fast matching table that is closest to the original colors to obtain a corresponding color candidate and its number. The image segmentation method using the image region merging algorithm according to the sixth aspect of the patent application, wherein, in the step (c), the merging between the two color regions replaces the color number of the merged person with another One person The color number, and the new color is the weighted average of the ratio of the two areas. An image segmentation method using an image region merging algorithm according to claim 7, wherein in the step (a), the mode conversion operation divides the original image into a plurality of color channels, and becomes the first The image processing value is obtained by smoothing the original histogram with a non-parametric density function, and finally selecting the local maximum value to obtain the second image values. The image segmentation method using the image region merging algorithm according to the eighth aspect of the patent application, wherein in the step (a), the numbers of the color candidate numbers are obtained by a binary search method. An image segmentation method using an image region merging algorithm according to claim 9, wherein in the step (c), the merging possibility formula is obtained by multiplying a first weight by 1 and subtracting each After the color distance value accounts for the ratio of the maximum color distance value, a second weight is multiplied by the ratio of the maximum boundary length value of each of the boundary length values, and a third weight is multiplied by 1 Subtracting the ratio of the maximum area value of each of the area values, and finally obtaining at least one probability value. An image segmentation method using an image region merging algorithm according to claim 10, wherein in the step (a), the non-parametric density function brings each gradation value of each color channel into its color. The histogram function of the channel, and subtracting one of the rank values from other rank values into a density estimation kernel function to obtain a complex core value, and then adding the total core value to the core value The total number of levels of the color channel. Image area merging calculation according to item 11 of the patent application scope The image segmentation method of the method, wherein in the step (b), the obtained importance index values are sorted from small to large, and in the step (c), the colors are sequentially determined. Whether the importance index value of the region is lower than the threshold value. An image segmentation method using an image region merging algorithm according to claim 12, wherein, in the step (c), when the importance index value of the color regions is determined to be not lower than the threshold When the value is obtained, the first combined result is directly obtained, and the next step is performed. An image segmentation method using an image region merging algorithm according to claim 1 or 12, wherein the importance indexing operation in the step (b) and the merging possibility operation in the (c) step It is collectively referred to as an image area merge algorithm.