JP6587407B2 - Image processing apparatus, image processing method, and program - Google Patents

Description

  The present invention particularly relates to an image processing apparatus, an image processing method, and a program suitable for use in dividing an image into a plurality of regions having similar attributes such as coordinates.

  In recent years, a technique for dividing an image into a plurality of regions having similar attributes such as color, texture, and coordinates has attracted attention. The area divided in this way is called a super pixel, and since encoding processing, image processing, image recognition processing, and the like can be executed in units of the divided area, it can be applied to various image processing apparatuses. it can.

  Conventionally, various methods have been proposed for image segmentation. In particular, many techniques for dividing an image into a plurality of regions by clustering pixels have been proposed. In these methods, data having colors, textures, and coordinates as elements are clustered. In the clustering, representative data of each class (region) is obtained, and input data is assigned to the nearest representative data. Here, the nearest representative data is representative candidate data having a shortest distance from the input data among a plurality of representative candidate data for the input data.

  Non-Patent Document 1 proposes a method of dividing into a plurality of regions using a clustering technique called SLIC (Simple Linear Iterative Clustering). SLIC is a technique in which the search range of nearest neighbor representative data in K-means clustering is limited to a local region in an image. Patent Document 1 proposes a method of integrating a region into an adjacent class when the shape of the region is a linear small region.

  Further, in the method described in Non-Patent Document 2, in the distance calculation between input data and representative candidate data, a term is introduced in which the distance increases as different classes of input data exist in the vicinity of the input data of interest. . Thus, clustering is performed so that the shape to be divided is close to a circle.

Japanese Patent No. 5335581

Radhakrishna Achanta, et al., "SLIC Superpixels Compared to State-of-the-Art Superpixel Methods", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, No. 11, pp. 2274-2282, Nov. 2012. J. Wang, and X. Wang, "VCells: Simple and Efficient Superpixels Using Edge-Weighted Centroidal Voronoi Tessellations", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, No. 6, pp. 1241-1247, Jun. 2012. C. Cortes, and V. Vapnik, "Support-Vector Networks", Machine Learning, 20, pp.273-297, 1995. C. M.M. Bishop, “Pattern recognition and machine learning,” Maruzen Publishing, 2012.

  Clustering is a technique often used in image segmentation. However, fragmentation may occur in region division by clustering. Fragmentation is a state in which pixels in the same class are not continuous in the coordinate space. When applying the region division result, it is preferable that no fragmentation occurs.

  In the method described in Non-Patent Document 1, in order to eliminate fragmentation, first, the region size of consecutive pixels belonging to the same class is calculated. If the region size is less than the threshold, the region is integrated into a neighboring class, and if the region size is equal to or larger than the threshold, all the fragmentation is eliminated by assigning a new class. However, in order to extract the area | region of the continuous pixel which belongs to the same class, since it is necessary to compare sequentially the class information of a certain pixel and its vicinity pixel, there exists a subject that processing amount is large.

  Further, the method described in Patent Document 1 can eliminate fragmentation that is a linear small region. However, the shape of fragmentation to be eliminated is limited, and there is a problem that fragmentation of a certain size or more cannot be eliminated.

  Furthermore, in the method described in Non-Patent Document 2, the occurrence of fragmentation can be suppressed, but it is necessary to refer to class information to which neighboring input data belongs when calculating the distance between each input data and representative candidate data. For this reason, there exists a subject that processing amount is large.

  In view of the above-described problems, an object of the present invention is to suppress the generation of fragmentation by suppressing the processing amount when an image is divided into a plurality of regions having similar attributes.

An image processing apparatus according to the present invention relates to at least one of representative data setting means for setting representative data for each of a plurality of regions in an image, coordinates of the representative data, color, and texture. Based on the distance, each pixel in the image is associated with any representative data in the plurality of regions, and each representative data is updated based on the set of associated pixels, and the update An association means for associating each pixel in the image with any of the updated representative data based on the distance to the representative data, and a pixel associated with the updated representative data by the association means Whether or not an area constituted by a set of the following is a predetermined range from the representative data related to the area, whether or not the area is continuous in the coordinate space. Region comprising a determining means based on the pattern of pixels are associated, when it is determined that the state of non-contiguous by the determination unit, the representative data pertaining to the is determined not contiguous region And a correction means for correcting to a continuous state in the coordinate space.

  According to the present invention, when an image is divided into a plurality of regions having similar attributes, the amount of processing can be suppressed and occurrence of fragmentation can be suppressed.

It is a flowchart which shows an example of the process sequence of the clustering process in embodiment. It is a figure for demonstrating the block in an image, and its representative data. It is a figure which shows an example of the area division | segmentation result in which fragmentation has generate | occur | produced. It is a block diagram which shows the hardware structural example of the data processor in embodiment. It is a figure for demonstrating the procedure which determines whether fragmentation has generate | occur | produced.

  DESCRIPTION OF EXEMPLARY EMBODIMENTS Hereinafter, preferred embodiments of the invention will be described in detail with reference to the drawings. In the present embodiment, an example in which an image is divided into regions using the image region dividing method according to the present invention will be described.

<Configuration example of data processing device>
FIG. 4 is a block diagram illustrating a hardware configuration example of the data processing apparatus 400 that can implement the clustering method according to the present embodiment.
In FIG. 4, a data storage unit 401 is a storage medium that holds image data. The data storage unit 401 includes a hard disk, flexible disk, CD-ROM, CD-R, DVD, memory card, CF card, smart media, SD card, memory stick, xD picture card, USB memory, and the like. In addition to image data, the data storage unit 401 can also store programs and other data. Alternatively, a part of the RAM 406 described later may be used as the data storage unit 401. Furthermore, a storage device of a destination device connected by the communication unit 402 described later may be virtually configured to be used via the communication unit 402.

  The display unit 403 is a device that displays images before and after performing the area division processing, or displays an image such as a GUI, and generally uses a CRT, a liquid crystal display, or the like. Alternatively, it may be an external display device connected by a cable or the like.

  The CPU 404 executes main processing according to the present embodiment and controls the overall operation of the data processing device 400. The ROM 405 and the RAM 406 provide the CPU 404 with programs, data, work areas, and the like necessary for the processing. When a program necessary for processing to be described later is stored in the data storage unit 401 or stored in the ROM 405, the processing described later is executed after being once written in the RAM 406. When the data processing apparatus 400 receives a program via the communication unit 402, the program is temporarily recorded in the data storage unit 401 and then written in the RAM 406 or directly from the communication unit 402 to the RAM 406. Executed.

  The CPU 404 reads image data written in the RAM 406 or the data storage unit 401 and executes image processing (clustering processing) according to the present embodiment. Data in the middle of processing such as representative data is written into the RAM 406 by the CPU 404 and is read out when necessary. Then, the clustering processing result is written in the RAM 406. Further, the CPU 404 performs control for displaying an image on the display unit 403, and performs control for transmitting image data to an external apparatus via the communication unit 402.

  The communication unit 402 is an I / F for performing communication between devices. As the I / F, for example, a well-known local area network, USB, IEEE1284, IEEE1394, a wired communication system such as a telephone line may be used. Further, a wireless communication system such as infrared (IrDA), IEEE802.11a, IEEE802.11b, IEEE802.11g, IEEE802.11n, Bluetooth (registered trademark), or UWB (Ultra wide Band) may be used.

  In the example shown in FIG. 4, an example is shown in which the data storage unit 401 and the display unit 403 are all included in one device, but these parts are connected by a communication path using a known communication method. Therefore, the configuration as a whole may be used. Further, in the example shown in FIG. 4, the configuration has only one CPU, but a configuration in which a plurality of CPUs are provided may be employed. As for the system configuration, various components other than those described above may exist, but the description thereof is omitted because it is not the main point of the present invention.

  Hereinafter, an outline of processing performed by the data processing apparatus 400 illustrated in FIG. 4 will be described. In the present embodiment, the class to which the input data in the vicinity of the representative data of each class belongs is referred to the clustering result. Then, it is determined whether fragmentation has occurred based on the number of input data belonging to the same class as the representative data. As a result, when fragmentation has occurred, a cancellation process is performed.

<Clustering for region division>
FIG. 1A is a flowchart illustrating an example of a processing procedure of clustering processing in the present embodiment. Note that each step shown in FIG. 1A indicates the operation of the CPU 404.
First, clustering target data will be described. Equation (1) below shows the i-th input data. The input data is a five-dimensional vector corresponding to the pixel in the image, and the i-th input data is information regarding the i-th pixel read out by raster scanning the image.
X _i = (x _{i, 1} , x _{i, 2} , x _{i, 3} , x _{i, 4} , x _{i, 5} ) (1)

In formula (1), x _{i, 1} and x _{i, 2} represent positions in a two-dimensional coordinate space, and mean coordinate values in the vertical and horizontal directions of the image, respectively. X _{i, 3} , x _{i, 4} and x _{i, 5} are three-dimensional color features representing the color components of the pixels.

First, in step S101, initialized representative data is generated. Specifically, as representative data setting processing, for example, the image 201 shown in FIG. 2 is divided into blocks on the coordinate space, and one representative data 205 is set in each block 203. Then, input data in the block 203 is selected at random, and a vector having the coordinates and color features of the selected input data as elements is set as a vector of the representative data. Equation (2) below shows the j-th representative data C _j . Here, j is a class index assigned to the representative data arranged as shown in FIG. 2 in raster order.
C _j = (c _{j, 1} , c _{j, 2} , c _{j, 3} , c _{j, 4} , c _{j, 5} ) (2)

In equation (2), c _{j, 1} and c _{j, 2} represent positions in a two-dimensional coordinate space, and mean coordinate values in the vertical and horizontal directions of the image, respectively. Further, c _{j, 3} , c _{j, 4} , and c _{j, 5} are three-dimensional color features representing the color components of the pixels.

In step S102, the maximum number of iterations is set, and a loop of iteration calculation from steps S103 to S111 is started.
In step S103, an input data loop is started. The order i of the input data X _i in the image is controlled, and the processing from step S104 to step S109 is repeated to cluster all the input data.

  First, in step S104, a search range is set. Specifically, the search range for representative candidate data is set according to the coordinate position of the input data. Here, the representative candidate data of the input data is a candidate of representative data to which the corresponding input data is assigned (belongs to).

  Here, an example of representative data in which the width and height of the search range 202 are each five will be described. First, a search range of representative candidate data is set around a block including input data to be processed (hereinafter referred to as attention input data) 206. In this case, the search range is representative data in the vicinity of 5 × 5 coordinates. The search range 202 has a vertical direction of 5 to 9, and a horizontal direction of 6 to 10. In the case of the example shown in FIG. 2, since the number of representative data per line is 15, the indexes included in the search range 202 are 66 to 70, 81 to 85, 96 to 100, 111 to 115, 126 to 130. It is. Therefore, the search range 202 of all input data included in the range of the block 204 including the target input data 206 is the same. It is assumed that the relationship between the position of the input data and the representative candidate data in the search range is fixed first, and the index of the representative data does not change even if the position of the representative data is changed by iterative processing.

Steps S105 to S107 are steps for searching the nearest representative data of the input data. Here, the nearest representative data is representative data having the shortest distance from the input data, that is, representative data closest in the distance space. Before describing the processing contents in each step, a method for calculating the distance between input data and representative candidate data in the present embodiment will be described. The following formula (3) is a calculation formula representing the distance D (X _i , C _j ) between the i-th input data and the j-th representative candidate data.
D (X _i , C _j ) = W × D _s (X _i , C _j ) + D _c (X _i , C _j ) (3)

In the equation (3), D _s represents a distance on the coordinate space, and D _c represents a distance on the color space. W is a weight for the distance in the coordinate space. As shown in Expression (3), the distance D between the input data and the representative candidate data is calculated by linear combination of the distance D _s on the coordinate space and the distance D _c on the color space. Hereinafter, such a distance calculated from a plurality of partial distances is referred to as a total distance. The following formulas (4) and (5) are calculation formulas for calculating the distance D _{s in} the coordinate space and the distance D _c in the color space, respectively. In the present embodiment, the Euclidean distance is used as the distance, but the present invention is not limited to this.

In step S105, a representative candidate data loop is started. The order j of the representative candidate data C _j is sequentially updated to search for all representative candidate data. In step S106, the total distance between the i-th input data and the j-th representative candidate data is calculated according to equation (3). In step S107, it is determined whether or not the calculation of the total distance with all representative candidate data has been completed. As a result of the determination, if the total distance with all the representative candidate data is calculated, the process proceeds to step S108, and the representative candidate data loop is terminated. On the other hand, if there is representative candidate data for which the total distance has not yet been calculated, the process returns to step S106 to calculate the total distance with the next representative candidate data.

  Subsequently, in step S108, the input data is attributed (associated) to the class of representative candidate data (nearest neighbor representative data) having the shortest distance from the total distance calculated in the loop of steps S105 to S107. In step S109, it is determined whether all input data has been processed. If all the input data is processed as a result of this determination, the process proceeds to step S110, and the input data loop is terminated. On the other hand, if there is input data that has not been processed yet, the process returns to step S104 to start processing the next input data.

In step S110, an average vector of the assigned input data vectors is calculated for each representative data. Then, the average vector is set as a new vector C _j of the corresponding representative data, and the representative data is updated. In step S111, it is determined whether or not the maximum number of repetitions has been exceeded, or whether or not the clustering result has converged. If any of the conditions is satisfied as a result of this determination, the iterative calculation is terminated. On the other hand, if neither condition is satisfied, the process returns to step S103 to start the next iterative calculation. Here, the clustering result indicates the class index to which each input data belongs. In the present embodiment, it is assumed that the input data has a two-dimensional image format.

  Next, in step S112, the clustering result is analyzed, and fragmentation elimination processing is performed on the class in which fragmentation has occurred. Details of this processing will be described later. When the above processing is completed, the CPU 404 outputs the clustering result (region division result) after the fragmentation is eliminated to the display unit 403 or the like.

<Fragmentation detection &resolution>
Here, the detailed processing procedure of step S112 is demonstrated, referring FIG.1 (b). In steps S113 to S116 in FIG. 1B, it is determined whether or not fragmentation has occurred for each class, and the resolution processing is applied to the class in which fragmentation has occurred.

  Here, fragmentation is a state in which input data belonging to the same class is not continuous in the coordinate space. FIG. 3 is a diagram for explaining an example of a clustering result in which fragmentation has occurred. In FIG. 3, each area is constituted by a set of input data belonging to the representative data, and each area in FIG. 3 indicates that the class index in the area is the same. The areas 301 to 303, the areas 304 to 307, the areas 308 to 315, and the areas 316 to 317 belong to the same class, but are separated on the coordinate space.

In step S113, a representative data loop is started. The order j of the representative data C _j is sequentially updated, and the following steps S114 to S115 are executed for all the representative data.

First, in step S114, it is estimated whether fragmentation has occurred for the j-th class. In the present embodiment, it is determined that fragmentation has occurred when there is input data that does not belong to the same class in the vicinity of the representative data C _j . Details of the determination process will be described below.

First, the coordinate position (c _{j, 1} , c _{j, 2} ) of the _jth representative data is read. In addition, a counter for counting the number of input data belonging to the same class as the representative data is initialized to zero. Next, from the clustering result, the coordinate position (c _{j, 1} , within a predetermined range (in this embodiment, a 3 × 3 area) centered on the coordinate position (c _{j, 1} , c _{j, 2} ) of the representative data _{. 1} + α _{n, 1} , c _{j, 2} + α _{n, 2} ) is read. Here, α _{n, 1} = {− _1, 0 _{, 1} }, α _{n, 2} = {− _{1 ,} 0 _{, 1} }, and α _{n, 1} ² + α _{n, 2} ² ≠ 0. . When the read class index value is j, the counter is incremented. If the coordinate position to be referred to is outside the clustering result area, the class index comparison process is skipped.

After the above processing is executed for all α _{n, 1} and α _{n, 2,} if the value of the counter is 3 × 3 = 9, it is determined that no fragmentation has occurred. On the other hand, if the count value is less than 9, it is determined that fragmentation has occurred. That is, it is determined that fragmentation has occurred when at least one input data belonging to a class different from the representative data exists in a 3 × 3 area centered on the representative data. FIG. 5 shows an example of the determination result of the presence or absence of fragmentation in the present embodiment.

  When it is determined that fragmentation has occurred in the above procedure, the process proceeds to step S115, and when it is determined that fragmentation has not occurred, the process proceeds to step S116.

  In step S115, correction processing for eliminating fragmentation is performed. In the present embodiment, fragmentation is eliminated by applying the method described in Non-Patent Document 1 to a region in the vicinity of a class in which it is determined that fragmentation has occurred. Details will be described below.

First, an N × N size region centered on the coordinate position (c _{j, 1} , c _{j, 2} ) of the j-th representative data is set for the clustering result. Here, the value of N is set so that the input data of the jth class index is sufficiently included in the N × N size area. In this embodiment, for example, the value of N is set so as to be the same size as the search range 202 shown in FIG.

  Then, the method described in Non-Patent Document 1 is applied to the N × N size area as follows to eliminate fragmentation. First, a region size in which the same class index continues is calculated. If the area size is smaller than the threshold value, the class index in the area is changed to a nearby class index. On the other hand, if the area size is greater than or equal to the threshold, a new class index is assigned.

  In step S116, it is determined whether or not the processing in steps S114 to S115 has been executed for all representative data. If the result of this determination is that processing has been performed for all representative data, the processing ends. On the other hand, if there is representative data that has not yet been processed, the process returns to step S114 to start processing for the next representative data.

  As described above, according to the present embodiment, it is determined that fragmentation has occurred when at least one input data belonging to a class different from the representative data exists in the vicinity of the representative data. In such a case, the fragmentation elimination process is executed only for the neighboring area. As described above, since the determination process for the presence or absence of fragmentation only refers to the class of input data in the vicinity of the representative data, the processing amount can be reduced. In addition, since the region for executing the fragmentation elimination process is limited, the processing amount is reduced as compared with the case where the fragmentation elimination process is performed on the entire image. Furthermore, by performing a process for eliminating fragmentation, the generation of fragmentation can be suppressed as an output result.

(Other embodiments)
In the embodiment described above, in step S114 of FIG. 1, a 3 × 3 size area centered on the representative data is set as the vicinity of the representative data, but the present invention is not limited to this. For example, it may be a rectangular area having an arbitrary size or a circular area having a radius r (r ≧ 1) with the representative data as the center.

  Further, in step S114 of FIG. 1, it is determined that fragmentation has occurred when at least one input data having a class index different from the representative data exists in the vicinity of the representative data. However, the present invention is not limited to this. For example, among the input data in the vicinity of the representative data, the number of input data having the same class index as the representative data is counted. Then, it may be determined that fragmentation has not occurred when the count value is equal to or greater than the threshold value, and it may be determined that fragmentation has occurred when the count value is less than the threshold value.

  In addition, among the class indexes in the vicinity of the representative data, the number of input data having a class index different from the representative data may be counted instead of the same class index as the representative data. Furthermore, a class index pattern may be designated in advance, and it may be determined that fragmentation has occurred when the class index pattern (associated pattern) in the vicinity of the representative data is similar to the pattern designated in advance.

  In addition, a class index pattern in the vicinity of representative data when fragmentation occurs and when it does not occur is used as learning data, and a two-class identification model for determining whether fragmentation has occurred is learned in advance. Also good. In this case, as the identification model, for example, SVM (Support Vector Machine) described in Non-Patent Document 3 is used.

  In step S114 of FIG. 1 of the above-described embodiment, the binary value indicating whether or not fragmentation has occurred is determined, but the probability that fragmentation has occurred may be calculated. In this case, for example, the probability is calculated according to the number of class indexes that are the same as the representative data among the class indexes in the vicinity of the representative data. Alternatively, the probabilistic identification model is learned using the pattern of the class index near the representative data as learning data. At this time, for example, logistic regression described in Non-Patent Document 4 is used as the probabilistic identification model.

  In step S115 of FIG. 1 of the above-described embodiment, the technique of Non-Patent Document 1 is applied as the fragmentation elimination process, but the present invention is not limited to this. For example, new representative data may be arranged around the representative data of the class determined to have fragmentation, and the clustering process may be executed again. By increasing the number of representative data in this way, it can be expected that fragmentation is eliminated by allocating to different representative data in each region of the class where fragmentation occurs.

In the embodiment described above, the position of the input data in the coordinate space is represented by two dimensions x _i1 and x _i2 , but the present invention is not limited to this, and coordinates of an arbitrary dimension may be used. In addition, although the color features of the input data are represented in three dimensions x _i3 , x _i4 , and x _i5 , they are not limited to color features, but may be texture features or a feature amount that combines texture features and color features. Good. Further, the dimension of the feature amount is not limited to three dimensions, and may be an arbitrary dimension.

  In the above-described embodiment, an example in which the search range 202 has five widths and heights of representative data has been described. However, the width of the search range is not limited to five representative data, and is arbitrary. It may be a search range.

(Other embodiments)
The present invention supplies a program that realizes one or more functions of the above-described embodiments to a system or apparatus via a network or a storage medium, and one or more processors in a computer of the system or apparatus read and execute the program It is also possible to implement this process. It can also be realized by a circuit (for example, ASIC) that realizes one or more functions.

401 Data storage unit 404 CPU

Claims (8)

Representative data setting means for setting representative data for each of a plurality of regions in the image;
Associating each pixel in the image with any representative data in the plurality of regions based on coordinates with the representative data and a distance relating to at least one of color and texture, and Updating each of the representative data based on a set of associated pixels, and, based on the distance from the updated representative data, replacing each of the pixels in the image with any of the updated representative data; An association means to associate;
Whether or not an area constituted by a set of pixels associated with the updated representative data by the associating means is continuous in the coordinate space is within a predetermined range from the representative data related to the area. Determining means for determining based on a pattern associated with the pixels;
Correction means for correcting to a state of being continuous on a coordinate space in a region including representative data relating to the region determined to be non-continuous when the determination unit determines that the state is not continuous. An image processing apparatus comprising:   The determination unit is in a state of being continuous in the coordinate space based on the number of pixels associated with the representative data related to the region among the pixels within a predetermined range from the representative data related to the region. The image processing apparatus according to claim 1, wherein the image processing apparatus determines whether or not the image processing is in progress.   The determination means is a state in which all pixels within a predetermined range from the representative data related to the area are pixels associated with the representative data related to the area and are continuous on the coordinate space. The image processing apparatus according to claim 2, wherein the determination is performed.   When the number of pixels associated with the representative data related to the region in the pixels within a predetermined range from the representative data related to the region is greater than or equal to a threshold value, the determination unit is continuous in the coordinate space The image processing apparatus according to claim 2, wherein it is determined that The image processing apparatus according to claim 1 , wherein the determination unit determines whether or not the state is continuous in a coordinate space by using an identification model learned in advance. Wherein the predetermined range from the representative data, an image processing apparatus according to any one of claim 1 to 5, characterized in that the representative data is a rectangular or circular area centering on. A representative data setting step for setting representative data for each of a plurality of regions in the image;
Associating each pixel in the image with any representative data in the plurality of regions based on coordinates with the representative data and a distance relating to at least one of color and texture, and Updating each of the representative data based on a set of associated pixels, and, based on the distance from the updated representative data, replacing each of the pixels in the image with any of the updated representative data; An association step to associate;
Whether or not an area composed of a set of pixels associated with the updated representative data in the association step is continuous in a coordinate space within a predetermined range from the representative data related to the area A determination step for determining based on a pattern associated with the pixels of
When it is determined that the state is not continuous in the determination step, a correction step for correcting the state including the representative data related to the region determined not to be continuous to a state continuous on the coordinate space; An image processing method comprising: A representative data setting step for setting representative data for each of a plurality of regions in the image;
Associating each pixel in the image with any representative data in the plurality of regions based on coordinates with the representative data and a distance relating to at least one of color and texture, and Updating each of the representative data based on a set of associated pixels, and, based on the distance from the updated representative data, replacing each of the pixels in the image with any of the updated representative data; An association step to associate;
Whether or not an area composed of a set of pixels associated with the updated representative data in the association step is continuous in a coordinate space within a predetermined range from the representative data related to the area A determination step for determining based on a pattern associated with the pixels of
When it is determined that the state is not continuous in the determination step, a correction step for correcting the state including the representative data related to the region determined not to be continuous to a state continuous on the coordinate space; A program characterized by being executed by a computer.

Images