JP5567448B2 - Image area dividing apparatus, image area dividing method, and image area dividing program - Google Patents

Description

  The present invention relates to an image region dividing device, an image region dividing method, and an image region dividing program, and in particular, an image is divided into a plurality of regions having similar characteristics (especially similar colors), and each image is included in an image. The present invention relates to an image region dividing device, an image region dividing method, and an image region dividing program for separating objects.

  In order to analyze the image and grasp the contents in detail, it is important to divide each object included in the image in advance and extract the regions. As a conventional technique for realizing such processing, there is an image area dividing apparatus that can divide an image into a plurality of areas by various methods and separate individual objects included in the image. As shown in FIG. 12, these are devices that divide the input image shown in (a) into three regions as shown in (b) and separate them into objects shown in (b1), (b2), and (b3), respectively. .

  In particular, the device described in the following Patent Document 1 (prior application by the present inventors: an image region dividing device, an image region dividing method, and an image region dividing program) is shown in FIG. 13 and FIG. A small area dividing unit 1 that excessively divides into a plurality of small areas based on color characteristics, and an internal area belonging to the small area in the input image and the small areas for each of the plurality of excessively divided small areas A target area selection unit 2 that outputs an external area that does not belong to the area, and an area similar in color to the corresponding internal area of the external area is integrated with the internal area and output as a small area expansion area A small region expansion unit 30 that performs the region similarity calculation unit 6 that calculates the region similarity of the pair of the small region expansion regions, and the region similarity of the corresponding small region expansion region pair among the small region pairs. The degree meets a predetermined standard A small region integration unit 7 that obtains the respective objects by determining that all the small region pairs belong to the same object and integrating them, and determining that the small region pairs that do not satisfy the predetermined standard belong to different objects; And an image area dividing device that separates and extracts each object included in the input image.

  The image region dividing device described in Patent Literature 1 is roughly divided as follows: (1) a small region dividing unit 10, (2) a target region selecting unit 2, (3) a small region expanding unit 30, and (4) a region. The five functional blocks of the similarity calculation unit 6 and (5) small region integration unit 7 realize the extraction of objects included in the image. The function outline of each part is as follows.

(1) Small area dividing unit 10
Based on the similarity of the properties of the image signal such as color and brightness, the image is actually divided into much smaller areas than the number of objects actually included in the image.

(2) Target area selection unit 2
One small region of interest is selected from the excessively divided image.

(3) Small area expansion unit 30
Statistically model the luminance and color distribution in the small area of interest, identify pixels that follow the same luminance and color distribution model as the original small area elsewhere in the image, Combine to get extended area. By combining with the target area selection unit, one extended area is obtained for each of the small areas obtained by the excessive division.

(4) Area similarity calculation unit 4
The similarity between the extended regions is measured as a ratio including matching pixels and digitized. Here, the region similarity S (R ₁ , R ₂ ) between the small region expansion regions is calculated from the following equation (Equation 1).

In Equation 1, the numerator E ₁ ∩E ₂ represents the number of pixels belonging to both the small region expansion regions E ₁ and E ₂ corresponding to the small region pair R ₁ and R ₂ , and the denominator E ₁ ∪E ₂ represents the small region expansion region. The number of pixels belonging to either region E ₁ or E ₂ is shown. In addition, 0 ≦ S (E ₁ , E ₂ ) ≦ 1, and S (E ₁ , E ₂ ) = 1 if the regions E ₁ and E ₂ completely match, and if there are no pixels that match at all S (E ₁ , E ₂ ) = 0 is shown. A larger region similarity indicates that regions (including shape and position) are more similar.

(5) Small area integration unit 5
If the calculated similarity between extended areas exceeds a preset threshold, both extended areas are determined to be similar to each other, and the original small areas of those extended areas belong to the same object And decide to integrate them into the same group.

  In the integration process as described above in the image region dividing device described in Patent Document 1, each object included in an image has a characteristic color distribution. This is based on the characteristic that the color distribution does not change significantly. Therefore, when there are many overlapping areas in the extended areas output based on the color distribution of each of the two small areas selected for a certain color distribution (including cases where the degree of coincidence of position, shape, etc. is large) The selected subregions have the same color distribution and the two selected subregions (one selected subregion pair) are likely to be part of the same object To do.

  FIG. 15 shows an outline of processing performed by the region similarity calculation unit 6 and the small region integration unit 7 of the prior art region dividing apparatus. That is, (1) From the result (a) of being excessively divided by the small area dividing unit 1, (2) (b) the small area R1 and (d) the small area R2 selected by the target area selecting unit 2 are (3) This is an example of the case where (c) the expansion region E1 and (e) the expansion region E2 are obtained by expansion by the small region expansion unit 30. (4) Since the similarity is calculated as 0.92 from the ratio of the pixels that match in the expansion region E1 and the expansion region E2 by the region similarity calculation unit 6, and exceeds a predetermined threshold value 0.90, (5) the small region integration unit 7 The original small area 1 and small area 2 are merged.

  FIG. 16 shows an example in which the (5) small area integration unit 7 obtains the area similarity for all the small area pairs of the input image and divides the small areas into groups corresponding to the respective objects as shown in FIG. As a result of (1) the small area dividing unit 1 dividing the input image into small areas, 17 small areas R1 to R17 are generated and identified by numbers. For each small region, corresponding small region expansion regions E1 to E17 are obtained by the processing of (2) the target region selection unit 2 and (3) the small region expansion unit 30. As a result of obtaining the area similarity of all pairs of the small area expansion area and determining whether it is above or below the predetermined threshold, three groups of small area expansion areas [(E14, E15, E16, E17), (E5, E6, E7, E8, E9, E10, E11, E12, E13), (E1, E2, E3, E4)] are obtained. The three groups are grouped so that all the small region extended region pairs in each group have a region similarity higher than a predetermined value, and all pairs outside each group have a predetermined value or less. Therefore, from these 3 groups, the corresponding 3 groups of the original small area [Group 1 (R14, R15, R16, R17), Group 2 (R5, R6, R7, R8, R9, R10, R11, R12, R13), Group 3 (R1, R2, R3, R4)]. Each group is regarded as a part of each object, and corresponds to (b1) to (b3) shown in FIG.

  As described above, the image area dividing device described in Patent Document 1 divides an image into an excessive number of small areas once, and then, based on the similarity between extended areas for each small area, This is an apparatus that performs integration determination and realizes extraction of objects included in an image.

Japanese Patent Application No. 2010-012467

  However, in the procedure performed by the image region dividing device described in Patent Document 1 for integration in units of small regions based on the similarity between extended regions, there are cases where objects cannot be correctly extracted from the image.

  The image region dividing device described in Patent Document 1 first over-divides an image, determines similarity in units of obtained small regions, and if it is determined to be similar, it is regarded as belonging to the same object Integrate. Here, the determination of the similarity between the small areas, that is, whether or not to integrate the two small areas is determined from the similarity of the shape between the expanded areas once each small area is expanded. Accordingly, when the expansion of the small area does not work well and the extended area having a similar shape is not formed, the small areas are not integrated. Therefore, the performance of the small area expanding unit 30 is improved. Accuracy is affected.

  For example, when a small area including a small number of pixels is expanded by (3) the small area expansion unit 30, modeling of luminance and color distribution is not sufficiently performed, and the area often does not expand. Referring to FIG. 17, since the small area of R17 has a small area size, the color distribution cannot be sufficiently modeled, and the small area may not be expanded. At this time, the extended region of the small region R17 is the same as the original small region, as in E'17. In this case, as compared with the expanded region E14 to E16, the denominator of the similarity calculation formula has a large value and the numerator indicates a small value, so the similarity is extremely lowered. Therefore, R17 is regarded as a separate object from R14 to R16 and is not integrated. As shown in (b1) to (b4) of FIG. 18, the region division results at this time are 4 groups [group 1 (R14, R15, R16), group 2 (R5, R6, R7, R8, R9, R10, R11, R12, R13), group 3 (R1, R2, R3, R4), and group 4 (R17)]. Correctly, since the small area to be integrated into the same group has a low similarity between the extended area and the multiple areas, an area division result in which the small area R17 is vacant is obtained.

  This is because the region division result is a binary determination such as “whether or not to integrate these small regions”. Then, although it is a small area that should be integrated at the time of small area integration, the erroneous determination that occurred because the area was not correctly integrated because the area expansion was not performed correctly, as shown in the example of FIG. It directly affects the final region segmentation result. As described above, separation of objects included in an image is realized by the processing method “(4) Integration in small areas performed by the area similarity calculation unit and (5) small area integration unit”. However, depending on the type of input video, there was a problem.

  The present invention inherits the framework of (1) small area division and (2) small area expansion of the preceding apparatus, and enables image area division that enables separation of individual objects included in an image with higher accuracy and stability. It is an object to provide an apparatus, an image region dividing method, and an image region dividing program.

  In order to achieve the above object, the present invention is an image region dividing device for separating and extracting each object included in an input image, and a small region dividing unit that excessively divides an input image into a plurality of small regions based on color features. A target area selection unit that outputs, in an associated manner, an internal area that belongs to the small area and an external area that does not belong to the small area in the input image, for each of the plurality of subdivided small areas; For each of the small region expansion regions, a small region expansion unit that outputs a region similar in color characteristic to the corresponding internal region among the external regions and outputs the small region expansion region. A pixel on the contour is extracted by using a contour extracting unit for extracting contour information, which is information for identifying the extracted pixel on the contour, and the contour information obtained for each of the pixels. Against A contour concentration frequency measuring unit that calculates a frequency of contour concentration by measuring the frequency at which the position of the image becomes a contour, and among the pixels of the input image, a pixel that satisfies the predetermined standard for the contour concentration frequency is an inter-object boundary candidate An object boundary determination unit for determining, and a closed region is extracted from the regions constituting the object boundary candidates to obtain an object boundary, and each region of the input image separated by the object boundary is obtained as each object. It is a first feature that an area extraction unit is provided.

  A color distribution modeling unit configured to generate a color distribution model from a color distribution of pixels included in the internal region; and an external region corresponding to the internal region using the color distribution model. Determining the energy required to bisect the region based on a first color feature similarity with the inner region and a second color feature similarity within the local region within the outer region A divided energy calculation unit that generates an energy function as a variable, and obtains a divided two region that minimizes the energy using the energy function, and among the divided two regions, there is a similarity in color characteristics with the internal region. A second feature includes a two-region division / integration unit that integrates the determined region with the internal region and outputs the integrated region as the small region expansion region.

  Further, the division energy calculation unit obtains the second color feature similarity by using a pixel value in a local area in the external area, and calculates the pixel value in a local area in the entire input image. The third feature is to obtain the second color feature similarity using a value normalized based on the color feature similarity of the second color feature.

  In addition, when the two-region division / integration unit obtains a divided two region that minimizes the energy using the energy function, the energy is applied to each of the excessively divided small regions included in the outer region. The fourth feature is to obtain the area to be minimized.

  The fifth feature is that a mixed normal distribution model (GMM) is used for the color distribution model.

  The sixth feature is that a histogram is used for the color distribution model.

  Further, the small region dividing unit subtracts the input image and converts it into a reduced color image, and a region boundary likelihood calculating unit that calculates the region boundary likelihood of the reduced color image in units of pixels of a predetermined sampling density; A region number assigning unit that determines whether each pixel for which the region boundary likelihood is calculated from the region boundary likelihood distribution belongs to a region boundary or a region, and assigns a region number if the pixel belongs to a region; With respect to the remaining pixels other than the pixels determined to belong to the region boundary or the region, the region number is assigned to the pixel determined to belong to the region based on the local distribution of the pixel assigned the region number. And a region enlargement unit that obtains each of the plurality of small regions as a connected region of the pixels to which the region number is assigned in the entire input image.

  The small region dividing unit includes a similarity matrix indicating similarity of color features between pixels of the input image and an inter-pixel similarity matrix calculating unit that calculates a diagonal matrix of the similarity matrix, and the similarity An evaluation criterion creation unit for creating an evaluation criterion matrix for dividing pixels having high color feature similarity into the same small region using the matrix and the diagonal matrix, and eigenvalues in ascending order of eigenvalues of the evaluation criterion matrix A small area number matrix indicating which of the predetermined number of small areas each pixel of the input image belongs to by using the eigenvector calculation unit for obtaining a predetermined number in the eigenvector and the diagonal matrix, An eighth feature includes a small area calculation unit that obtains each of the plurality of small areas with reference to a number matrix.

  Further, the contour concentration frequency measurement unit obtains the contour concentration frequency by normalizing the measured frequency, and the object boundary determination unit determines that the contour concentration frequency is a predetermined threshold reference among the pixels of the input image. A ninth feature is that a pixel that satisfies the condition is determined as an inter-object boundary candidate.

  The contour concentration frequency measuring unit obtains the contour concentration frequency as a value obtained by dividing the measured frequency using the maximum value of the measured frequencies for each pixel of the input image, and the object boundary A tenth feature is that the determination unit determines, among the pixels of the input image, a pixel whose contour concentration frequency satisfies a predetermined threshold criterion as an inter-object boundary candidate.

  Further, the contour concentration frequency measuring unit obtains the contour concentration frequency as a value obtained by dividing the measured frequency using the number of the small regions excessively divided by the small region dividing unit, and the object boundary determination An eleventh feature is that the unit determines that a pixel satisfying a predetermined threshold criterion among the pixels of the input image is a boundary candidate between objects.

  In order to achieve the above object, the present invention provides an image region dividing method for separating and extracting each object included in an input image, wherein the input image is divided into a plurality of small regions based on color characteristics. A division step, and a target region selection step of outputting an internal region belonging to the small region and an external region not belonging to the small region in the input image in association with each of the plurality of excessively divided small regions A small area expansion step of integrating an area similar in color characteristic to the corresponding internal area in the external area with the internal area and outputting it as a small area expansion area, and for each of the small area expansion areas A contour extracting step for extracting contour information, which is information for identifying pixels on the extracted contour, and for identifying the extracted pixels on the contour; For each pixel of the image, a contour concentration frequency measuring step for determining a contour concentration frequency by measuring the frequency at which the position of the pixel becomes an outline, and among the pixels of the input image, the contour concentration frequency is determined based on a predetermined reference. An inter-object boundary determining step for determining that a pixel to be satisfied is an inter-object boundary candidate, and an input image that is separated by the inter-object boundary by extracting a closed region from the region constituting the inter-object boundary candidate And a closed region extracting step for obtaining each region as the object.

  Furthermore, in order to achieve the above object, the present invention is an image region dividing program for separating and extracting each object included in an input image, and causes the computer to excessively divide the input image into a plurality of small regions based on color features. A target area for outputting a small area dividing step and an internal area belonging to the small area and an external area not belonging to the small area in the input image for each of the plurality of excessively divided small areas For each of the selection step, a small region expansion step of integrating a region similar in color characteristic to the corresponding internal region in the external region with the internal region and outputting the integrated region as a small region expansion region, On the other hand, a contour extraction step for extracting the pixels on the contour and obtaining contour information which is information for identifying the extracted pixels on the contour; Using the contour information, for each pixel of the input image, the contour concentration frequency measuring step for determining the frequency of contour concentration by measuring the frequency at which the position of the pixel becomes the contour, and among the pixels of the input image, An inter-object boundary determining step for determining a pixel whose contour concentration frequency satisfies a predetermined criterion as an inter-object boundary candidate; and extracting a closed region from an area constituting the inter-object boundary candidate to form an inter-object boundary; A thirteenth feature is that a closed region extraction step of obtaining each region of the input image separated by the boundary as each object is executed.

  According to the first, second, or third feature, it is possible to automatically realize image segmentation without the need for human intervention. In addition, it is possible to separate individual objects included in an image with higher accuracy and stability than in the past.

  According to the fourth feature, since the calculation of the minimum energy region is performed for each small region that is narrower than the entire external region, the calculation load in the calculation can be reduced.

  According to the fifth feature, the accuracy of color distribution modeling increases, and the image can be segmented with high accuracy.

  According to the sixth feature, the color distribution can be modeled even when the number of pixels used for modeling the color distribution is small.

  According to the seventh or eighth feature, since the color features are divided into similar small regions, the small regions do not include colors of different systems, and the color features of the small regions are determined by the small region expansion unit in the subsequent stage. A small region expansion region is obtained as a region / shape reflected in detail, and it can be determined with high accuracy whether the small region integration unit belongs to the same object.

  According to the ninth, tenth, or eleventh feature, even if different images are handled, the threshold value can be set in the object environment determination unit based on a uniform standard within the same range.

  According to the twelfth feature, it is possible to automatically realize image segmentation without human intervention. In addition, it is possible to separate individual objects included in an image with higher accuracy and stability than in the past.

  According to the thirteenth feature, it is possible to automatically realize image segmentation without human intervention. In addition, it is possible to separate individual objects included in an image with higher accuracy and stability than in the past.

1 is a functional block diagram of an image area dividing device according to a first embodiment of the present invention. FIG. 5 is a functional block diagram of an image area dividing device according to a second embodiment of the present invention. It is a figure which shows the flow of the object area | region extraction process by the image area division | segmentation apparatus of this invention. It is a figure explaining the color reduction process using k-means by the quantization part in 1st Embodiment. FIG. 6 is a diagram for explaining processing of a small region dividing unit in the first embodiment. It is a figure explaining the process by the object area | region selection part in 1st and 2nd embodiment, a color distribution modeling part, a division | segmentation energy calculation part, and a 2 area | region division | segmentation / integration part. It is a figure explaining an example until outline information is obtained through the process of a target area selection part, a small area expansion part, and an outline extraction part from the small area division result in the 1st and 2nd embodiments. It is a figure explaining the example of the process which determines an outline. From each small region division result in the first and second embodiments, through the processing of the target region selection unit, the small region expansion unit and the contour extraction unit, each contour information is obtained, and further, the contour concentration frequency measurement unit It is a figure explaining the example from which a contour concentration frequency is obtained as a sum of contour information through processing. A series of processes of the present invention, that is, (1) small area dividing process, (2) target area selecting process (3) small area expanding process, (4) contour extracting process, (5) contour concentration frequency measuring process, (6) It is a figure which shows the example until an area | region division result is obtained from an input image by the boundary determination process between objects, and (7) closed area extraction processing. It is a figure explaining the process of the small area division part in 2nd Embodiment. It is a figure explaining the area | region division of an image. It is a functional block diagram of the area dividing device of a prior art. It is a functional block diagram of the area dividing device of a prior art. It is a figure explaining the process by the area | region similarity calculation part and small area integration part of the area | region division apparatus of a prior art. It is a figure explaining the result of the small area expansion area | region obtained from each small area | region in the process by the area | region dividing apparatus of a prior art, and grouping of the small area based on the result. It is a figure explaining the subject of a prior art that an isolated small area | region may generate | occur | produce by the result of the small area expansion area | region obtained from each small area | region, and the small area grouping based on the result. It is a figure explaining the final area segmentation result (each object) containing the error obtained by the area segmentation device of a prior art depending on the case.

  Hereinafter, the present invention will be described in detail with reference to the drawings. FIG. 1 shows a first embodiment of an image area dividing apparatus of the present invention, and FIG. 2 shows a functional block diagram of the second embodiment. The flow common to both the embodiments of FIG. 1 and FIG. 2 is broadly divided into (1) a small region dividing unit 1, (2) a target region selecting unit 2, (3) a small region expanding unit 30, and (4). The image region dividing apparatus of the present invention includes seven functional blocks: a contour extracting unit 8, (5) contour concentration frequency measuring unit 9, (6) inter-object boundary determining unit 10, and (7) closed region extracting unit 20. Thus, the extraction of the object included in the image is realized. (1) to (3) are the same as the preceding area dividing device described in Patent Document 1.

  The image region dividing device of the present invention generally functions as described above, focusing on the similarity of the shape indicated by the extended region, like the prior art device of Patent Document 1. However, unlike the previous device that expands the small area and integrates the original small areas based on the similarity between the extended areas, the present invention has a high probability that the outline of the extended area is a boundary between objects included in the image. The boundary between objects is determined based on the position where the contour of each extended area expanded from the small area in the image is concentrated and the degree of concentration. The part of the difference corresponds to the above (4) to (7).

  Next, the outline of each process of (1) to (7) will be described.

(1) Small area dividing unit 10
Based on the similarity of the properties of the image signal, such as color and brightness, the image is divided into much smaller areas than the number of objects actually included in the image.

(2) Target area selection unit 2
One small region of interest is selected from the excessively divided image.

(3) Small area expansion part 30
Statistically model the luminance and color distribution in the small area of interest, identify pixels that follow the same luminance and color distribution model as the original small area elsewhere in the image, Combine to get extended area. By combining with the target area selection unit, one extended area is obtained for each of the small areas obtained by the excessive division.

(4) Outline extraction unit 8
A contour is extracted from the obtained extended region and output as contour information.

(5) Contour concentration frequency measurement unit 9
The frequency at which each pixel position in the image becomes the contour is measured from the contour between the two regions obtained for each extended region, and the contour concentration frequency is obtained.

(6) Inter-object boundary determination unit 10
From the obtained contour concentration frequency, whether or not the pixel is a boundary between objects at each pixel position is determined based on a set threshold value, and set as an object boundary candidate.

(7) Closed region extraction unit 20
The determined object boundary candidate may include a boundary line that does not constitute a closed region. A closed region is extracted from the object boundary candidates and set as an object boundary. Each area of the image divided by the boundary becomes each object extracted by the image area dividing apparatus of the present invention.

  As described above, according to the present invention, one image is excessively divided into a plurality of small regions having similar characteristics (particularly similar colors) in the process (1), and is excessively divided in the processes (2) and (3). In the processes (4) to (7), pre-processing for separating individual objects included in the image is performed by integrating the small areas estimated to be included in the same object from the small areas. It is characterized by actually separating objects using contour information.

  FIG. 3 shows an outline of the flow of area division related to the image area dividing apparatus of the present invention. A small area divided image (b) is obtained from the input image of FIG. The small area in FIG. 5B is excessively divided into objects. Therefore, by integrating the areas between the small areas that are determined to belong to the same object, and extracting the objects using the contour information, the area for the three objects is finally obtained as shown in FIG. Get the split result. The use of the contour information, which is the process between (b) and (c) in FIG. 3, is not shown in FIG. 3, but will be described later with reference to FIGS.

  As a method of obtaining an excessively divided small area from an input image, a case using JSEG described later [A1] (first embodiment showing functional blocks in FIG. 1) and a case using Normalized Cuts [A2] (FIG. 2). The second embodiment showing functional blocks) will be described, but any method that can obtain an equivalent result by, for example, excessive division by Super Pixel or the like can be applied. The integration process [B] after excessive division into small areas is common.

  In FIG. 3D, each object is painted in a different color (represented by different shades), and the area appropriately divided into objects in FIG. In addition, the input image example in Fig. 11 (a) is an image in which a goat (mainly white) eats grass (mainly green) on a ranch with a fence (mainly white gray) at the back, explaining the present invention. In each figure, it is used as an example in common. (A) in the figure shows the original color image as a black and white image, and as can be seen from the shades of black and white, the colors of the fence, goat and grass are not uniform. Color shades and shades are different.

  Hereinafter, an image region dividing device and an image region dividing method according to the first embodiment of the present invention will be described. In the first embodiment, an input image is excessively divided using JSEG, and subsequently integrated.

[A1] Over-division using JSEG First, details of JSEG, which is an existing area division method for the above-described over-division into small areas, will be described. A functional block diagram of the area division apparatus configuration is shown in FIG. 1 as described above. In the small area dividing unit 1 of FIG. 1, overdivision is performed using JSEG as one embodiment. In this case, the small region dividing unit 1 includes a quantization unit 11, a region boundary likelihood calculating unit 12, a region number assigning unit 13, and a region expanding unit 14, as shown in FIG. FIG. 5 shows an example in which an image is processed by the small area dividing unit 1 (when JSEG is used). JSEG has been proposed in the following document.

  Y. Deng, BS Manjunath, "Unsupervised Segmentation of Color-Texture Regions in Images and Video", IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI '01), vol. 23, no. 8, pp. 800-810, Agustus 2001.

  In the quantization unit 11 in FIG. 1, the input image is reduced in color. For example, if the input image is a 24-bit multi-valued color image represented by 8 bits for each RGB component, one pixel is represented by 16.67 million colors, but the quantization unit 11 uses C color (C = 10 to JSEG). 20 is used).

  The color reduction processing in the quantization unit 11 is performed using k-means of a known technique as schematically shown in FIG. That is, all the pixels of the input image are plotted on a three-dimensional RGB space as shown in FIG. 4 (each x point in FIG. 4 is a pixel). In FIG. 4, only the two-dimensional RG space of the RGB space is shown for convenience, and k-means can be applied regardless of the number of dimensions. By using k-means, the space is clustered as shown in FIG. 4, and the points of the pixels belonging to each cluster are changed to the colors indicated by the centroid of each cluster (the XX points in FIG. 4 are centroids). Reduce color. Since the number of clusters k in k-means can be arbitrarily set, a number C of colors to be reduced is set when k-means is used as the quantization unit 11 in JSEG. Thus, after color reduction, the number of colors C = k.

Specifically, k-means clustering is performed by the following procedures (1) to (4).
(1) The data is divided into k clusters, which is an arbitrary number.
(2) Calculate the center of gravity for each cluster.
(3) For all data, find a cluster that minimizes the distance from the center of gravity, and assign each data to the smallest cluster.
(4) Terminate if there is no change from the previous cluster. If there is a change, go back to (2)

  When the process of the quantization unit 11 is performed in this way, for example, an input image as shown in FIG. 5A becomes a reduced color image as shown in FIG. 5B. In addition, the value of the pixel is converted for convenience so that the pixel showing the same color can be visually recognized in the reduced color image of FIG. 5B, and the image in which it is easy to see that the input image (a) to (b) is reduced. Is FIG. 5 (b2).

  The region boundary likelihood calculating unit 12 calculates a region boundary likelihood J indicating the likelihood of an object boundary from a local region centered on a pixel of interest in the input image that has been reduced in color through the quantization unit 11 according to the following procedure. To do. The region boundary likelihood J is calculated in units of pixels, and takes a large value at the boundary between objects included in the image. (The name of JSEG is derived from the region boundary likelihood J.)

For the position coordinate (x, y) of the pixel of interest z = (x, y) in the reduced color input image, calculate the variance S _T (Equation 2) from the center of gravity m (Equation 1) as shown in the following equation: . Note that in Equations 1 and 2, the local region at the center of the target pixel is Z, and among the pixels included in Z, the one used for calculating the region boundary likelihood J (for example, within the local region Z for convenience of calculation efficiency and load) Sampling is performed every two pixels in the vertical and horizontal directions).

Also, let Z _i (i = 1, 2,..., C) be a set of pixels obtained by classifying pixels belonging to the local region Z at the center of the pixel of interest in Equations 1 and 2 for each color reduced to the number of colors C. That is, the union of each i (i = 1, 2,..., C) of Z _i becomes the local region Z, and each Z _i is also determined for each pixel of interest that is the center of Z as with the local region Z. A total sum S _W (Formula 4) of the variance S _i from the center of gravity m _i (Formula 3) of the pixel set Z _i is calculated. Note the number of pixels included the N _i to pixel set Z _i in Equation 3 and 4.

As shown in the following equation (Equation 5), calculates the area boundary likelihood J of the pixel of interest located at the center of the local area from the calculated dispersion S _T and S _W. The color boundary image of FIG. 5B is thus processed by the region boundary likelihood calculating unit 12 to calculate the region boundary likelihood J, and the region boundary likelihood J is visualized (visualized as closer to white as J is larger). The obtained image is shown in FIG.

The region number assigning unit 13 calculates the mean μ of the distribution of the region boundary likelihood J and the variance σ ² (and the square root of the variance σ ^{2 in} the local region (the same region and sampling as in the region boundary likelihood calculating unit 12). Standard deviation σ) is calculated, and the threshold value T is determined as shown in the following formula (formula 6). However, α is a parameter that needs to be adjusted, and a value that works effectively is determined in advance by conducting a preliminary experiment or the like. For example, when the value of α is set to about 0.1, it works effectively.

  A pixel having a region boundary likelihood J that is less than the set threshold T is determined not to be a region boundary and is assigned a region number. At this time, if it is determined that the adjacent pixel (the adjacent pixel in the pixel used in the calculation in the local region) is not the region boundary, the same region number is assigned.

  An image obtained by visualizing the region boundary likelihood J in FIG. 5 (c) (an image in which the region boundary likelihood J is calculated) is processed by the region number assigning unit 13, and a pixel exceeding the threshold T (if it is a boundary region) FIG. 5 (d) shows an image in which the determined pixels) are white and the pixels below the threshold value T (pixels that are determined not to be boundary regions and assigned region numbers) are displayed in black.

  In the region enlargement unit 14, for the sake of calculation efficiency, a somewhat sparse boundary region / region number determination obtained from the result of the region boundary likelihood J calculated to some extent at a predetermined sampling density is applied to all remaining pixels. Perform supplementary processing. That is, the area number of a pixel to which an area number is assigned is a pixel that has not been assigned an area number adjacent to that pixel (a pixel that has not been sampled in the local area) and is not adjacent to a pixel in the boundary area And the enlargement process is repeated until there are no pixels with no area number (excluding pixels with no area number because they are determined to be boundary areas). In addition, the area numbers assigned in each local area are adjusted as the area numbers in the entire image so that there is no contradiction (for example, if the areas to which the area numbers are assigned are connected, a common area number is used). Thus, finally, the entire pixel to which each area number is assigned is regarded as each small area, and the area division result (small area division result) shown in FIG. 5E is obtained.

  In addition, in order to obtain an object by integrating the small areas obtained by overdivision as a result of area division, each pixel in the small area is quantized with reference to the input image when processing in the target area selection unit 2 and later described later. It is assumed that the pixel value before the color reduction in the unit 11 is restored. This process may be performed in the region enlargement unit 14 or in the target region selection unit 2. Note that color reduction is not performed in small area division by [A2] Normalized Cuts, which will be described later, and therefore it is not necessary to return to the original pixel value before color reduction.

  In the foregoing, the description has been given of the execution of the small area dividing unit 1 in JSEG until the small area dividing result is obtained from the input image.

[B] Small region integration processing Next, for the small region division result (and input image), (2) target region selection processing, (3) small region expansion processing, (4) contour extraction processing, (5) The steps until the contour division result is obtained by performing the contour concentration frequency measurement processing, (6) inter-object boundary determination processing, and (7) closed region extraction processing will be described. Among these stages, (2) target area selection unit 2 and (3) small area expansion unit 30 (color distribution model) in FIG. 1 according to the first embodiment (or in FIG. 2 according to the second embodiment described later). FIG. 6 shows an example in which an image is processed by the conversion unit 3, the division energy calculation unit 4, and the two-region division / integration unit 5). In this stage, the image is processed by (4) contour extraction processing, (5) contour concentration frequency measurement processing, (6) inter-object boundary determination processing, and (7) closed region extraction processing in FIG. 1 (or FIG. 2). An example of this is shown in FIG.

  (2) The target area selection unit 2 selects a small area from the small area division result, outputs a process number for identifying the small area for each selected small area, and simultaneously outputs it from the input image. The internal area and external area of the selected small area are extracted. The internal area of the small area is the small area itself, and is a term for distinguishing from the external area. The external area is an area obtained by removing the internal area from the entire input image. If there is a hole area (not belonging to a small area) inside the small area, the hole is not an internal area. When a small area is not connected, each part is an internal area.

  In the example shown in FIG. 6, when the green grass region on the left side is selected from the image of the small region division result shown in FIG. 6A, the internal region of the selected small region is the same as FIG. The external area of the selected small area is output as shown in FIG. In (b) and (c) of the figure, the non-applicable areas are displayed in black.

  Note that each small area is subtracted in the middle of the small area dividing unit 1 as in the case of the above-described JSEG (and after subdivision in the small area dividing unit 1 after obtaining the division result) (2) The target area selection unit 2 may refer back to the original input image and return the pixel value to the original value.

  (3) The small area expanding unit 30 includes a color distribution modeling unit 3, a divided energy calculating unit 4, and a two-region dividing / integrating unit 5 described below. Here, the color feature of the internal region is extracted, and the region (color feature similar region) that is determined to be similar to the internal region is selected from the external region, and the internal region corresponding to the color feature similar region ( = Small area) to obtain a small area expansion area. In the example shown in FIG. 6, (3) the small region expansion unit 30 outputs (b), (c) to (d).

  The color distribution modeling unit 3 models the color distribution of pixels included in the selected small area. For example, in the case of FIG. 6, since (b) in FIG. 6 is an internal region of the selected small region, the color distribution of the pixels included therein is modeled. In this case, the green distribution of grass is mainly modeled. At this time, for example, a mixed normal distribution model (GMM) or a histogram can be used for modeling the color distribution.

If the signal value of the pixel was set to F, the density function g [F] of a mixed normal distribution model of the number of mixture M (GMM) has an average mu _m, the covariance matrix sigma M number of normal distributions is determined by _m N _m It is defined as a weighted linear sum of (μ _m , Σ _m ) (Formula 7). Here, F represents a pixel signal value, and λ _m represents a weight assigned to each normal distribution.

When modeling the color distribution using a mixed normal distribution model (GMM), the EM algorithm (expected value maximization method), which is a well-known technique, uses the signal value F of the pixels contained in the selected small region. Thus, the mean μ _m and covariance matrix Σ _m are determined simultaneously with the weight λ _m assigned to each normal distribution N _m (μ _m , Σ _m ).

  When the color distribution is modeled by a histogram, by measuring the relative frequency of the signal value F of the pixels included in the selected small area, with each section as an appropriate section of the signal value F that can be taken by the pixel. A histogram θ [F] is calculated. Since the histogram value θ [F] is the relative frequency of each section of the signal value F and is standardized, as shown in the following equation (Formula 8), if the sum is taken over the section of all signal values F, 1

  In the split energy calculation unit 4, the energy required to divide the outer area into an area determined to be similar to the inner area and an area determined not to be similar to the inner area (the smaller the energy, the lower the division based on the color characteristics. Generate an energy function that calculates (determined to be a reasonable partition). For this reason, first, the color distribution model generated by the color distribution modeling unit 3 is used to determine how small each pixel p included in the area other than the small area selected in the input image is selected. It is calculated as the likelihood L [F (p)] from the signal value F (p) of the pixel p whether it is similar to the color distribution of the pixels in the pixel p.

  When the color distribution is modeled by the density function g [F] of the mixed normal distribution model (GMM), the likelihood is L [F (p)] = g [F (p)]. When the color distribution is modeled by the histogram θ [F], the likelihood L [F (p)] = θ [F (p)] is set.

  Likelihood L [F (p)], that is, in addition to an index of the similarity of the color feature of each pixel with the inner region, the color feature similarity between adjacent pixels, other than the small region selected in the input image The energy required for dividing the image specified in the region into two regions is obtained, and an energy function E with the division method as a variable is generated according to the following equation (Equation 9).

  In Equation 9, e [l (p), l (q)] is as follows (Equation 10).

  However, q is a pixel in the vicinity of the pixel p, and l (p) is determined that the pixel p included in the region other than the selected small region is similar to the color characteristics of the pixels in the selected small region. In this case, 1 is set, otherwise 0 is set (that is, when the division method is determined, the value of l (p) is determined for all the pixels p, and the value of the energy function E is determined). η and κ are positive constants that require adjustment, and dist (p, q) is the distance between the pixels p and q.

  The constant κ may be adaptively automatically determined from the input image as in the following (Formula 11). That is, from the signal value F of the pixel p in the input image and the pixel q in the vicinity thereof,

Asking. However, in (Equation 11), the operation symbol <•> means the average value of the values of all combinations that can be taken in the image for the pixel p and its neighboring pixels q. This makes it possible to determine κ according to the content of the signal in the input image, determine κ suitable for the input image, and obtain the effect of improving the accuracy of region division.

  In addition, the use of κ by (Equation 11) is, as is clear from substituting (Equation 10), for each pixel value F (p), F (q) with the square root of (Equation 11) as a constant. This is equivalent to finding e [l (p), l (q)] in (Equation 10) after normalization by multiplication. The normalization is normalization based on the color feature similarity in the local region represented by the pixel q in the entire input image represented by the pixel p, based on the meaning of the operation symbol <•>.

  When the two-region division / integration unit 5 first determines that the pixel p included in the region other than the small region selected as the two-region division processing is similar to the color characteristics of the pixels in the selected small region. If l (p) = 1, otherwise l (p) = 0, the divided two regions that minimize the energy are determined from the generated energy function E. Each of the divided two regions may be connected, not connected, or may not have a hole. Next, as an integration process, corresponding to the regions determined to be similar to the color features of the inner region (small region) with l (p) = 1 in the divided two regions (the color feature similarity determination source and It is integrated with the internal area and output as a small area expansion area.

  As a result of the two-region division by energy minimization and the integration of the color feature similar regions obtained thereby into the inner region, an image as shown in FIG. 6D, for example, is obtained as a small region expansion region. In FIG. 6D, areas that are not determined to be similar in the external area (areas other than the small area expansion area) are shown in black.

  Note that the first term of Equation 9 is a term related to the color feature, and the value becomes smaller as the signal value F (p) of the pixel p is used inside the selected small region. It is preferable for energy minimization to determine that is similar to the color characteristics of the pixels in the selected small region.

  The second term of Equation 9 is a term related to the color feature and how to divide (based on the color feature), and a large energy is generated if the signal value between the pixels p and q is close to l ( p) and l (q) are different (i.e., p and q have different color characteristics and belong to different areas of the divided two areas), but a large amount of energy is not generated at the boundary where the difference in pixel values is large Therefore, the determination that l (p) and l (q) are different is preferred. As described above, when Expression 11 is used, the determination based on the degree of difference in color characteristics in the entire input image is performed in the determination of the distinction between the two divided areas.

  The two-region division / integration unit 5 does not determine the entire external region as a variable at the same time, but determines the external region from the energy function E generated as described above. A region with the minimum energy may be determined for each of the other small regions (other than the corresponding internal region) (small regions divided by the small region dividing unit 1) included in. Also, in this case, depending on whether or not the minimum energy area obtained from each small area exceeds a predetermined ratio of the small area (for example, half of the number of pixels included), the whole of each small area is added to the small area expansion area or You may perform the process which is not added.

  As described above, (3) the small area expansion process has a function of identifying a pixel in the image according to the same statistical information as the selected small area and extracting an area obtained by enlarging the original small area. If a small region is properly selected as a partial region belonging to an object in the image, it is considered that the small region is correctly expanded to the shape of the belonging object having the same statistical properties.

  As will be described later, when (3) the small area expansion process is applied using (1) the small areas divided in various ways by the small area dividing process, the true area included in the image is included in the obtained enlarged area. Often, several objects having the same shape as the object are included. Therefore, in the present invention, an object is extracted using the characteristic that the shapes of the enlarged regions overlap.

  That is, in the present invention, attention is paid to the outline of the extension area in order to collect the extension areas in consideration of overlap. Since the pixels where the contours of the enlarged region are concentrated are considered to be on the boundary line of the true object included in the image, multi-value region division is realized by extracting them. Thereby, the true object included in the image can be extracted probabilistically based on the overlapping degree of the enlarged regions having similar shapes.

Note that in the expansion / integration process of the above-described process (3) in the image region dividing apparatus according to the present invention, the objects included in the image each have a characteristic color distribution and are within the same object. This is based on the characteristic that the color distribution does not change significantly when viewed partially. Therefore, when there are many overlapping areas between the small area expansion areas that are output based on the color distribution of each of the two small areas selected for a certain color distribution (when the degree of coincidence of position, shape, etc. is large). The selected subregions have the same color distribution, and the two selected subregions (one selected subregion pair) are likely to be part of the same object. And integrate.
(4) Outline extraction unit 8
A contour is extracted from the obtained extension region, and is output as contour information, that is, information for identifying whether or not each pixel is a pixel constituting the contour of each extension region. As shown in FIG. 7, (1) a small area R1 selected by (2) target area selection processing from (a) small area divided image by (1) small area division processing is (3) small area By the extension process, (c) it is extended to the extension area E1. Then, by (4) contour extraction processing, a contour is extracted from the obtained extended region E1, and is output as (d) contour information C1.

  In the case of the example in FIG. 7, the region is expanded from a part of the grass that is the selected small region R <b> 1 to the grass region (mainly green) in the image, and an expanded region E <b> 1 is obtained. The contour information C1 correctly indicates the boundary portion between each object of the goat and the fence.

  Similarly, (g) contour information C2, which is the contour, is extracted from (e) the expanded region E2 expanded from the selected small region R2. The small region R2 is a part of the goat's body, and the extended region E2 shows the entire goat's body (mainly white). The contour information C2 correctly shows the boundary between the grass and fence objects.

  In order to extract contour information, that is, determine whether each pixel is a contour, for example, the following may be performed. The procedure is shown in FIG. Whether or not it is a pixel on the contour is determined by scanning the obtained extended region image in order of raster scanning from left to right and from top to bottom as shown in FIG. To go. The pixel of interest is located in the upper left. It is determined whether the pixels in the three directions of right, lower right, and lower are in the same region as the target position. If at least one different area is included, the target position is determined as a pixel on the contour.

  At the pixel position β shown in (b2) of the example of FIG. 8, four pixels near the contour of the upper left part of the goat's back were extracted. The position of interest β is a background pixel (noted as “B” in the figure) that is not included in the extended area, and the other pixels on the right, lower right, and lower are pixels (“F” in the figure) that are included in the extended area. Notation). In this case, since the region of the target position and the surrounding three pixels are different, the target position β is determined as a pixel on the contour as shown in (c2). Conversely, at the pixel position α shown in (b1) of the example of FIG. 8, since α itself and other right, lower right, and lower pixels are all background pixels, as shown in (c1), the target position α Is determined not to be a contour. In this way, pixels at the boundary between the background and the goat are extracted as contours.

(5) Contour concentration frequency measurement unit 9
The frequency at which the pixel position becomes the contour is measured at each pixel position in the image from the contour between the two regions obtained for each extended region. That is, the frequency at which each pixel position in the image becomes a contour is obtained by taking the sum of the contour information obtained for each region. Then, the contour concentration frequency is obtained by normalizing the frequency obtained as the sum.

  As shown in FIG. 9A, it is assumed that (1) a total of 17 small regions R are obtained by the small region dividing unit 10. As shown in (b), (c), and (d) in the figure, each of these small regions R is obtained by (2) selecting by the target region selecting unit 2 and (3) expanding by the small region expanding unit 30. It can be confirmed that the enlarged region E includes several overlapping objects that show the same shape as the true object included in the image.

  The numbers in the diagrams (b), (c), and (d) correspond to the small area numbers in (a). It can be confirmed that there are enlarged regions having the same shape as the true object included in the image in the extended region in FIG. For example, the extended areas E1, E2, E3, and E4 corresponding to the small area numbers R1, R2, R3, and R4 are all the fence objects, and the extended areas corresponding to the small area numbers R5, R7, R10, R12, and R13, respectively. The areas E5, E7, E10, E12, and E13 are all expanded to grass objects, and the expanded areas E14 and E16 corresponding to the small area numbers R14 and R16 are all expanded to goat objects.

  (5) In order to extract the true object from the object candidates generated by the area enlargement, the contour concentration frequency measuring unit 9 pays attention to the outline of the enlarged area, and determines the overlapping degree of the enlarged area showing a similar shape in the prior art. Instead of using, the degree of concentration of the outline of the enlarged region, which is a feature of the present invention, is used. Thus, the accuracy of object extraction is improved by replacing the degree of overlap with the degree of contour concentration and measuring.

  For example, in FIG. 9, there are overlapping extended areas with similar shapes, and therefore pixels on the outer periphery of the fence / grass / goat object are determined to be the boundary lines between the true objects included in the image. Probability increases. By counting the frequency at which the contours of the object candidates obtained by enlarging the various seeds in the image are concentrated, it is determined probabilistically whether the pixel is a pixel on the boundary line.

  The contour concentration frequency Lp is obtained by normalizing the frequency value measured as the sum of the contour information so as to have a value in the range of 0 to 1 (from 0 to 1). Specifically, the contour concentration frequency Lp is obtained by dividing the frequency of each pixel by the maximum value in the image. Alternatively, the contour concentration frequency Lp can be obtained by dividing the frequency of each pixel in the image by the small region division number (in the example of FIG. 9, the division number is 17).

  FIG. 9E shows a frequency obtained by measuring and normalizing the frequency of the contour of the enlarged region for each pixel, obtaining the contour concentration frequency, and visualizing the distribution in the image. A brighter (white) image indicates that the frequency of the outline of the enlarged region is higher.

(6) Inter-object boundary determination unit 10
From the obtained contour concentration frequency, it is determined by a set threshold value whether or not the pixel is a boundary candidate between objects at each pixel position. Pixels with a high frequency of reaching the contour of the enlarged region are determined as pixel candidates on the boundary line between true objects included in the image. Therefore, if L_p ≧ T according to the threshold T (0 ≦ T ≦ 1), the pixel is determined as a pixel candidate on the boundary line between true objects included in the image.

  Actually, the boundary line determined by setting the threshold value T from the contour concentration frequency shown in FIG. 10C is shown in FIG. It can be seen that a result close to the boundary line of the object included in the region division result by human judgment can be reproduced.

(7) Closed region extraction unit 20
The determined object boundary candidate may include a boundary line that does not constitute a closed region. A closed region is extracted from the object boundary candidates to obtain an object boundary. As an area into which an image is divided by the object boundary, an object as a result of division into multiple areas in the image area dividing apparatus of the present invention is obtained. The closed region extraction processing is known in the field of image processing. Existing closed region extraction methods can be applied.

  For example, in the object boundary line candidate shown in FIG. 10 (d), a boundary line that forms an open region that is not related to the configuration of the closed region is obtained from the goat body at the lower left of the image. In order to eliminate this, (7) the closed region extraction unit 20 examines the connectivity between adjacent pixels by searching in units of pixels and assigns region numbers, and the same region on both sides of the pixel on the boundary line candidate. Those numbered are considered to be pixels on the boundary line constituting the open area and are deleted.

  As a result, as shown in FIG. 10 (e), a region division result of three objects of goat, grass, and fence is obtained. These series of processes do not require manual operations such as the user specifying a seed. The final multi-region division result is automatically obtained from the given image.

  Next, an image region dividing device and an image region dividing method according to the second embodiment of the present invention will be described. The second embodiment is different from the first embodiment in that the input image is excessively divided using Normalized Cuts, but the integration process is common. Therefore, only the excessive division process using Normalized Cuts will be described below, and the description of the small area integration process will be omitted.

[A2] Excessive division using Normalized Cuts
The case where the small area dividing unit 1 in the image area dividing apparatus of the present invention is realized using Normalized Cuts will be described in detail. As described above, the functional block diagram of the image area dividing apparatus is shown in FIG. Further, FIG. 11 shows a flow of processing for dividing into small areas in this configuration. Normalized Cuts are known as proposed in the following document.

  Jianbo Shi and Jitendra Malik, "Normalized Cuts and Image Segmentation," IEEE Transactions on PAMI, Vol. 22, No. 8, pp.888-905, Aug. 2000.

The inter-pixel similarity matrix calculation unit 101 calculates a similarity matrix W indicating the similarity of color features between pixels for all combinations of two arbitrary pixels in the image. The pixels in the input image of vertical N _R pixels, horizontal N _C pixels, and all N _R N _C pixels are counted in raster scan order, the signal value of the i-th pixel is F (i), and the position coordinate is X (i) The signal value of the jth pixel is F (j) and the position coordinate is X (j). However, i, j = 1, 2,..., N _R N _C. The element w _ij of the i-th row and the j-th column of the similarity matrix W of N _R N _C rows and N _R N _C columns is calculated as follows (Formula 12).

In Equation 12, r is a parameter that needs to be adjusted with the distance threshold. σ _I ² and σ _x ² are obtained from the variance of the signal value F of the pixel in the input image and the variance of the position coordinate X, respectively. This means that the similarity is 0 between pixels that are separated by a distance of r or more.

From the calculated similarity matrix W, the inter-pixel similarity matrix calculation unit 101 similarly calculates a diagonal matrix D of N _R N _C rows and N _R N _C columns as follows (Formula 13). However, the element d _ij in the i-th row and j-th column of the diagonal matrix D is used.

The evaluation criterion creation unit 102 creates an evaluation criterion matrix A for dividing pixels with high color feature similarity into the same small area from the calculated similarity matrix W and its diagonal matrix D as follows: (Formula 14). The evaluation criterion matrix A is also a matrix of N _R N _C rows and N _R N _C columns.

The eigenvector calculation unit 103 calculates P eigenvectors v _p of the evaluation criterion matrix A in ascending order from the smallest eigenvalue (p = 1, 2,..., P). The eigenvector v _p is a matrix with N _R N _C rows and one column.

In the small region calculation unit 104, an eigenvector matrix V = [v ₁ , v ₂ ,..., V _P ] in which the calculated P eigenvectors v _p are sequentially arranged in the column direction from the smallest eigenvalue, and a similarity matrix W A matrix B shown in the following equation is calculated from the diagonal matrix D.

The matrix B is a matrix of N _R N _C rows and P columns. The elements of the matrix B is extracted in the row direction, N _R N _C-number of row vectors _{u r (r = 1,2, ...} , N R N C) to produce a. That row vector _{u r (r = 1,2, ...} , N R N C) is a matrix of one row P string identical to the first r rows of the matrix B, 1 row j-th column of the row vector (matrix) u _r The (j = 1, 2,..., P) component is equal to the r row j column component of the matrix B.

N _R N sets of the _C row vector u _r to clustering P-dimensional space distributed into Q by the above-described k-means clustering. However, Q sets the number of small areas to be divided. Result of the clustering, N _R N _C subregions number from 1 to each row vector u _r until Q is given. A matrix of N _R N _C rows and one column having the assigned small region number as an element is calculated as a small region number matrix h. The elements of the small area number matrix h describe the numbers of the small areas divided into Q in order corresponding to the raster scan order of the input image. That element of i rows and one column of small area matrix h (i is 1, 2, ..., N _R either N _C) is Qi (Qi is 1, ..., one of Q) if, in the input image The pixel with the order i counted up in the raster scan order belongs to the small area with the small area number Qi. In this way, by referring to each element of the small area matrix h, it is determined which small area each of the N _R N _C pixels of the input image belongs, and a small area division result is obtained.

  Note that the image region dividing apparatus (including the first and second embodiments) of the present invention stores an input unit for inputting an input image, a main storage unit for storing image data being processed, and a program. 1 and 2 are installed on a personal computer (PC) equipped with a recording unit for executing the program, a central processing unit for executing the program, and a display unit for displaying the processing results. May be.

  According to the present invention, a new image-related service can be provided. That is, the image area dividing apparatus of the present invention can separate individual objects included in an image. For this reason, the extracted individual objects can be switched and displayed separately. It is also useful for image coding and transmission services. That is, it is useful to improve the subjective image quality of an image in encoding under a limited code rate by preferentially encoding important objects with high image quality. It is also useful for image recognition services. That is, by extracting individual objects, it is possible to analyze and understand the image contents in more detail than when analyzing an image in which objects are mixed as a whole.

DESCRIPTION OF SYMBOLS 1 ... Small area division part, 2 ... Target area selection part, 30 ... Small area expansion part, 3 ... Color distribution modeling part, 4 ... Divided energy calculation part, 5 ... Two area division | segmentation / integration part, 8 ... Contour extraction part , 9 ... Contour concentration frequency measuring unit, 10 ... Inter-object boundary determining unit, 20 ... Closed region extracting unit, 11 ... Quantizing unit, 12 ... Region boundary likelihood calculating unit, 13 ... Region number assigning unit, 14 ... Region expansion 101: Inter-pixel similarity matrix calculation unit, 102 ... Evaluation criterion creation unit, 103 ... Eigen vector calculation unit, 104 ... Small region calculation unit

Claims (13)

An image region dividing device for separating and extracting each object included in an input image,
A small area dividing unit that excessively divides an input image into a plurality of small areas based on color features;
A target area selection unit that outputs, in an associated manner, an internal area that belongs to the small area and an external area that does not belong to the small area in the input image, for each of the plurality of small areas that are excessively divided;
A small area expansion unit that integrates an area similar in color characteristic to the corresponding internal area in the external area and outputs the area as a small area expansion area;
For each of the small region expansion regions, a contour extraction unit that extracts the pixels on the contour and obtains contour information that is information for identifying the extracted pixels on the contour;
Using the contour information obtained for each of the above, for each pixel of the input image, a contour concentration frequency measuring unit that determines the frequency of contour concentration by measuring the frequency at which the position of the pixel becomes the contour;
Among the pixels of the input image, an inter-object boundary determination unit that determines that a pixel satisfying a predetermined criterion for the contour concentration frequency is an inter-object boundary candidate;
A closed region extracting unit that extracts a closed region from a region constituting the candidate boundary between objects as an inter-object boundary and obtains each region of an input image separated by the inter-object boundary as the object. An image area dividing device. The small area extension is
A color distribution modeling unit that generates a color distribution model from the color distribution of pixels included in the internal region;
Using the color distribution model, an outer region corresponding to the inner region is determined based on a first color feature similarity with the inner region and a second color feature similarity with a local region in the outer region. A split energy calculation unit for obtaining an energy function using the two split regions as variables, and obtaining energy required for splitting;
The energy function is used to obtain a divided two region that minimizes the energy, and a region that is determined to have a color feature similarity with the inner region of the divided two regions is integrated with the inner region. The image region dividing apparatus according to claim 1, further comprising a two-region dividing / merging unit that outputs the region as an extended region. The split energy calculation unit
The second color feature similarity is obtained using a pixel value in the local region in the outer region, and the pixel value is normalized based on the color feature similarity in the local region in the entire input image. The image area dividing apparatus according to claim 2, wherein the second color feature similarity is obtained using the converted value. The two-region division / integration unit
When obtaining the divided two regions that minimize the energy using the energy function, a region that minimizes the energy is obtained for each of the excessively divided small regions included in the outer region. The image area dividing device according to claim 2 or 3.   5. The image area dividing apparatus according to claim 2, wherein a mixed normal distribution model (GMM) is used for the color distribution model.   5. The image area dividing apparatus according to claim 2, wherein a histogram is used for the color distribution model. The small region dividing unit is
A quantization unit that reduces the color of the input image and converts it to a reduced color image;
A region boundary likelihood calculating unit that calculates a region boundary likelihood of the color-reduced image in units of pixels of a predetermined sampling density;
A region number assigning unit that determines whether each pixel from which the region boundary likelihood is calculated from the region boundary likelihood distribution belongs to a region boundary or a region;
With respect to the remaining pixels other than the pixels determined to belong to the region boundary or the region, the region number is assigned to the pixel determined to belong to the region based on the local distribution of the pixel assigned the region number. And a region enlarging unit that obtains each of the plurality of small regions as a connected region of pixels assigned with the region number in the entire input image. Image region dividing apparatus. The small region dividing unit is
A similarity matrix indicating similarity of color features between pixels of the input image and a pixel-to-pixel similarity matrix calculating unit that calculates a diagonal matrix of the similarity matrix;
Using the similarity matrix and the diagonal matrix, an evaluation criterion creation unit that creates an evaluation criterion matrix for dividing pixels having high similarity in color features into the same small region;
An eigenvector calculation unit for obtaining a predetermined number of eigenvectors of the evaluation criterion matrix in ascending order of eigenvalues;
Using the eigenvector and the diagonal matrix, calculate a small area number matrix indicating which of the predetermined number of small areas each pixel of the input image belongs to, and refer to the small area number matrix The image area dividing device according to claim 1, further comprising a small area calculation unit that obtains each of the small areas. The contour concentration frequency measurement unit obtains the contour concentration frequency by normalizing the measured frequency,
9. The object boundary determination unit according to claim 1, wherein a pixel satisfying a predetermined threshold criterion among the pixels of the input image is determined as an inter-object boundary candidate. An image area dividing device according to claim 1. The contour concentration frequency measuring unit obtains the contour concentration frequency as a value obtained by dividing the measured frequency using the maximum value of the measured frequencies for each pixel of the input image,
9. The object boundary determination unit according to claim 1, wherein a pixel satisfying a predetermined threshold criterion among the pixels of the input image is determined as an inter-object boundary candidate. An image area dividing device according to claim 1. The contour concentration frequency measuring unit obtains the contour concentration frequency as a value obtained by dividing the measured frequency by using the number of the small regions excessively divided by the small region dividing unit,
9. The object boundary determination unit according to claim 1, wherein a pixel satisfying a predetermined threshold criterion among the pixels of the input image is determined as an inter-object boundary candidate. An image area dividing device according to claim 1. An image region dividing method for separating and extracting each object included in an input image,
A small area dividing step of excessively dividing the input image into a plurality of small areas based on color features;
A target area selecting step for outputting an associated internal area belonging to the small area and an external area not belonging to the small area in the input image for each of the plurality of subdivided small areas;
A small region expansion step of integrating a region similar in color characteristic to the corresponding internal region in the external region with the internal region and outputting as a small region expansion region;
For each of the small area expansion regions, a contour extraction step for extracting contour pixels that are information for extracting pixels on the contour and identifying the pixels on the extracted contour;
Using the contour information obtained for each of the above, for each pixel of the input image, the contour concentration frequency measuring step for measuring the frequency at which the position of the pixel becomes the contour and obtaining the contour concentration frequency;
Among the pixels of the input image, an inter-object boundary determination step for determining, as an inter-object boundary candidate, a pixel whose contour concentration frequency satisfies a predetermined criterion;
A closed region extracting step of extracting a closed region from a region constituting the inter-object boundary candidate as an inter-object boundary, and obtaining each region of the input image separated by the inter-object boundary as each object. An image region dividing method. An image region segmentation program that separates and extracts each object included in an input image.
A small area dividing step of excessively dividing the input image into a plurality of small areas based on color features;
A target area selecting step for outputting an associated internal area belonging to the small area and an external area not belonging to the small area in the input image for each of the plurality of subdivided small areas;
A small region expansion step of integrating a region similar in color characteristic to the corresponding internal region in the external region with the internal region and outputting as a small region expansion region;
For each of the small area expansion regions, a contour extraction step for extracting contour pixels that are information for extracting pixels on the contour and identifying the pixels on the extracted contour;
Using the contour information obtained for each of the above, for each pixel of the input image, the contour concentration frequency measuring step for measuring the frequency at which the position of the pixel becomes the contour and obtaining the contour concentration frequency;
Among the pixels of the input image, an inter-object boundary determination step for determining, as an inter-object boundary candidate, a pixel whose contour concentration frequency satisfies a predetermined criterion;
A closed region extraction step for extracting a closed region from regions constituting the inter-object boundary candidate to obtain an inter-object boundary, and obtaining each region of an input image separated by the inter-object boundary as each object. program.