JP2004258750A - Method and device for clustering feature vector of image - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To classify feature vectors extracted from image data by clustering by specifying the level of optimal classification matching inputted image data from the image data themselves without the need of inputting any parameter to designate the level of desired classification. <P>SOLUTION: A plurality of low resolution images whose resolutions are different stepwise are derived from an original image, and the initial representative vectors of two or more clusters are derived from the lowest resolution image whose resolution is the lowest. The optimal classification of feature vectors in the respective low resolution images is successively derived while increasing the representative vectors on which information in a real image space is reflected on the basis of the correlation of the classification of image areas in the real image space and the classification in a feature vector space by using those initial representative vectors, and finally the optimal classification of the feature vectors extracted from the individual pixels of the original image is derived. <P>COPYRIGHT: (C)2004,JPO&NCIPI

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a method and apparatus for classifying a plurality of feature vectors extracted from an image, and in particular, using a clustering technique in a feature vector space for region segmentation processing and the like, from each pixel of one original image. The present invention relates to a method and apparatus for classifying extracted feature vectors into a plurality of clusters to which similar ones belong.
[0002]
[Prior art]
As a data classification method when features of observation data or image data can be expressed as feature vectors having n parameters representing the features, a plurality of feature vectors are mapped to an n-dimensional feature vector space, and the features A so-called clustering method for classifying these feature vectors into a plurality of clusters based on the distribution in the vector space is conventionally known. A cluster is literally a “lumps” of feature vectors in the feature vector space, and feature vectors that are close to each other are classified into the same cluster using Euclidean distance in the feature vector space as an index. That is, feature vectors belonging to the same cluster represent features that are similar to each other.
[0003]
In general, in the clustering process, a constant value parameter indicating how far the classification is to be performed must be specified prior to the start of the process. For example, the final number of clusters and the maximum allowable distance between the cluster center and feature vectors belonging to the clusters can be specified as such parameters. Even when using a self-converging algorithm that does not fix the number of clusters, etc., some constant value parameter that indicates how far the classification is performed, such as a parameter related to cluster expansion and a parameter related to the distance between clusters. The necessity to specify is not eliminated (for example, see Non-Patent Document 1).
[0004]
[Non-Patent Document 1]
Nagao Makoto, "Image recognition theory", first edition, Corona, February 15, 1983
, P. 120-126
[0005]
[Problems to be solved by the invention]
The degree to which classification should be performed in the clustering process strongly depends on the data contents. In particular, when image data with high diversity is targeted, the appropriate classification level varies greatly depending on the image data. For example, a region dividing process for dividing one image into regions (hereinafter referred to as “object regions”) corresponding to imaging target elements such as “sky”, “sea”, and “building” included in the image is performed. For example, when classifying the feature vector extracted from each pixel of the image by clustering processing, the number of elements to be captured included in each image is various, and how much the image should be classified It is impossible to set a single standard. That is, if an image includes only “sky” and “sea” as photographing target elements, it is only necessary to divide the image into two object areas, so that the degree of classification is sufficient, but “building” and “tree” are also sufficient. For images including many elements to be photographed such as “soil”, a finer classification is required. In this case, if the standard of the degree of uniform classification according to the former image is adopted, sufficient classification cannot be performed for the latter image, and the uniform standard according to the latter image cannot be achieved. If it is adopted, the former image in which only “sky” and “sea” are actually photographed is unnecessarily divided into many object regions.
[0006]
Therefore, in the clustering process for image data for the purpose of area division or the like, no matter what image data is input as a classification target, the optimum classification degree for the image data is specified from the image data itself, A method that realizes stable classification performance is strongly desired.
[0007]
In view of such circumstances, the present invention specifies the optimum classification level from the input image data itself representing one original image without requiring the input of a parameter for specifying the preferable classification level, and An object of the present invention is to provide a clustering method and apparatus for classifying feature vectors extracted from each pixel of an original image.
[0008]
[Means for Solving the Problems]
That is, the image feature vector clustering method according to the present invention includes a step of deriving a low-resolution image including a plurality of pixels having different resolutions in stages from an original image, and the resolution among the plurality of low-resolution images. Obtaining an initial value of each component of two or more representative vectors from the lowest resolution image having the lowest resolution, and extracting a feature vector from each pixel of the current image with the next lowest resolution image as the current image Mapping each of the feature vectors to a feature vector space; classifying the feature vectors into clusters represented by each of the representative vectors in the feature vector space; and Dividing the current image into image regions based on the distribution of pixels corresponding to the feature vector to which the image belongs in the current image; A step of specifying an image region corresponding to one selected cluster selected from the stars, and a step performed when a plurality of image regions are specified by the specification, wherein the selection is made from the plurality of image regions. One temporary representative vector is extracted from each of the plurality of selected image regions, and in the feature vector space, the feature vectors corresponding to the pixels belonging to the plurality of selected image regions are each represented by the temporary representative vector. Reclassify into clusters, identify one or more temporary cluster groups based on the correspondence between the selected image region and temporary clusters, and represent the vectors representing each of the temporary cluster groups as representative of the selected cluster A step of setting a new representative vector instead of the representative vector, a step of specifying the image area for all clusters, and the plurality of images The above feature vector until the final representative vector for classifying the feature vector extracted from each pixel of the original image is obtained, the step of repeating the steps performed when the area is specified, and the original image is the current image The method includes the step of repeating the above-described repeating step from the step of extracting.
[0009]
The image feature vector clustering apparatus according to the present invention also includes means for deriving a low-resolution image composed of a plurality of pixels having different resolutions in stages from an original image, and a resolution among the plurality of low-resolution images. Means for obtaining an initial value of each component of two or more representative vectors from the lowest resolution image having the lowest resolution, and means for extracting a feature vector from each pixel of the current image with the next lowest resolution image as the current image Means for mapping each of the feature vectors to a feature vector space; means for classifying the feature vector into a cluster represented by each of the representative vectors in the feature vector space; and Means for dividing the current image into image regions based on the distribution of pixels corresponding to the feature vector to which the vector belongs in the current image, and the above class A means for specifying an image area corresponding to one selected cluster selected from the above, and a means for operating when a plurality of image areas are specified by the specification, and is selected from the plurality of image areas. One temporary representative vector is extracted from each of the plurality of selected image regions, and each of the temporary representative vectors represents a feature vector corresponding to a pixel belonging to the plurality of selected image regions in the feature vector space. Reclassify into temporary clusters, identify one or more temporary cluster groups based on the correspondence between the selected image area and temporary clusters, and represent the vectors representing each of the temporary cluster groups as representative of the selected cluster Means for replacing the representative vector with a new representative vector, means for specifying the image area for all clusters, and the plurality of images Until the final representative vector for classifying the feature vector extracted from each pixel of the original image is obtained and the original image is the current image, and the means that operates when the area is specified is repeatedly operated. It is an apparatus characterized by comprising means for repeatedly operating the means for repeatedly operating the above-mentioned means for extracting feature vectors.
[0010]
Here, in the present invention, the “low resolution image” is an image composed of a plurality of pixels having a smaller number of pixels than the original image. Based on the original image, Gaussian pyramid, linear interpolation, spline interpolation, wavelet transform, etc. It refers to what is sequentially obtained by the image reduction processing used. Different reduction ratios may be applied to the vertical and horizontal directions of the image.
[0011]
In the present invention, a “feature vector” is a vector extracted from each pixel of an image, and a vector having a plurality of parameters (hereinafter referred to as “feature amounts”) indicating the features of the image as components. Point to. As the feature amount that is a component of the feature vector, for example, a feature amount indicating a color feature, a brightness feature, a texture feature, depth information, an edge feature included in the image, or the like can be used. Further, the “feature vector space” refers to a space having the coordinates of each component of the feature vector. For example, when the feature vector is a vector having the luminance component of each pixel and two color difference components in the YCC color system as components, the three-dimensional YCC color system space is the feature vector space.
[0012]
Further, in the present invention, the “representative vector” refers to a vector representing each cluster defined in the feature vector space, and one representative vector is assigned to each cluster.
[0013]
In the present invention, the “image region” means each island-shaped region formed by pixels corresponding to feature vectors belonging to the same cluster in the feature vector space on the real image space, that is, the low-resolution image or the original image itself. Point to. In the real image space, a plurality of regions having similar features may exist separately from each other, and thus one cluster in the feature vector space may correspond to two or more image regions. If the clustering process is performed with the optimum classification level, the image area in the original image becomes an object area corresponding to each imaging target element such as “sky”, “sea”, and “building”.
[0014]
Further, in the present invention, the “temporary representative vector” refers to one vector having the same dimension as the feature vector that represents the feature of each selected image region. For example, the feature vector corresponding to the pixel belonging to each selected image region A vector having the average value of each component as a component can be used.
[0015]
In the present invention, “specify one or a plurality of temporary cluster groups based on the correspondence between the selected image region and the temporary cluster” means that the selected image regions separated from each other in the real image space are feature vectors. This means that a group of temporary clusters corresponding to a group of selected image regions that are separated from each other also in the feature vector space is specified based on whether or not they can be separated from each other in the space. That is, according to the present invention, in view of the fact that feature vectors corresponding to pixels that form one image region by gathering together in the real image space are likely to form one cluster also in the feature vector space. When there are a plurality of image regions corresponding to the cluster separated in the real image space, it is examined in the feature vector space whether it is appropriate to distinguish a plurality of selected image regions selected from the image regions, If appropriate, the representative vector is replaced so as to distinguish them.
[0016]
Further, the specification of the one or more temporary cluster groups includes all feature vectors corresponding to the pixels in the selected image area from which the temporary representative vectors representing the temporary cluster are extracted, and other selected images. When there is a temporary cluster that does not include a feature vector corresponding to a pixel in the region, the temporary cluster is specified as one temporary cluster group, and further belongs to any of the temporary cluster groups specified as such. When there are no remaining temporary clusters, a group of the remaining temporary clusters may be specified as one temporary cluster group. Alternatively, the specification of the one or more temporary cluster groups includes all feature vectors corresponding to pixels in the selected image area from which the temporary representative vector representing the temporary cluster is extracted, and another selected image. When there is a temporary cluster that does not include a feature vector corresponding to a pixel in the region, the temporary cluster is specified as one temporary cluster group, and further, a temporary representative vector extraction source that represents the temporary cluster only between each other If there are a plurality of temporary clusters exchanging feature vectors corresponding to the pixels in the selected image area, a group of the plurality of temporary clusters is identified as one temporary cluster group, and If there remains a temporary cluster that does not belong to any of the specified temporary cluster group, the remaining temporary clusters are included. The may be one identified as one formal cluster group. In these cases, after reclassification to the temporary cluster and before specifying the temporary cluster group, for each temporary cluster, for the total number of feature vectors belonging to the temporary cluster, the corresponding feature vector belonging to the temporary cluster If there is a selected image area whose number ratio is less than a predetermined ratio, the feature vector corresponding to the selected image area may be excluded from the temporary cluster.
[0017]
Here, “a plurality of temporary clusters exchanging feature vectors corresponding to pixels in a selected image area from which a temporary representative vector representing the temporary cluster only in mutual is exchanged” refers to the plurality of temporary clusters. Each of the selected image regions has the same pattern as to which feature vector is derived from, and the feature vectors derived from those selected image regions are not included in other temporary clusters Point to.
[0018]
The clustering method or apparatus according to the present invention may further include a step or means for updating the representative vector based on the feature vector included in each of the classified clusters. Further, in addition to this, it may further include a step or means for updating the cluster based on the updated representative vector.
[0019]
Here, “updating a representative vector” means that a vector that more appropriately represents a cluster specified by classification is a new representative vector. For example, a feature vector belonging to each specified cluster In this case, the vector representing the center of gravity is replaced with the original representative vector to be a new representative vector. Further, “updating a cluster” means reclassifying by clustering based on the representative vector updated as described above. For example, each feature vector is the closest to the Euclidean distance in the feature vector space. This refers to reclassification into a cluster represented by a new representative vector.
[0020]
The clustering method or apparatus according to the present invention may further include a step or means for updating the image region by integrating the micro region into the non-micro region.
[0021]
Here, the “small area” refers to an area that is considered to be so-called noise, and is composed of a smaller number of pixels than the predetermined ratio (for example, about 1/1000) of the number of pixels forming the current image. On the other hand, the “non-micro area” refers to an image area that is not a micro area.
[0022]
In addition, the plurality of selected image areas may be obtained by sequentially selecting a plurality of constituent pixels having a large number of constituent pixels from the plurality of image areas.
[0023]
In obtaining the initial value of each component of the representative vector, one original representative vector is derived from the lowest resolution image made up of n pixels, and n extracted from each of the n pixels. The distance between the feature vector and the original representative vector in the feature vector space is determined, the feature vector indicating the maximum distance is set as the representative vector candidate, the highest candidate ranking is assigned, and each of the remaining feature vectors and the original representative Find the distance in the feature vector space between the vector and the representative vector candidate closest to the feature vector, add the feature vector indicating the maximum distance to the representative vector candidate, and give the next highest candidate ranking, The process of assigning the next highest candidate ranking is repeated, and according to the candidate ranking, the top two or more of the above representative vector candidates The value of each component of the symptom vector may be an initial value of the.
[0024]
Here, the “distance” in the feature vector space typically refers to the Euclidean distance between two vectors in the feature vector space, but any index that appropriately represents the degree of proximity of the two vectors in the feature vector space. Suppose that it is not limited to the Euclidean distance.
[0025]
The “original representative vector” is one vector representing the lowest resolution image, and for example, a vector whose component is the average value of each component of the feature vector extracted from each pixel of the lowest resolution image is used. Can be done.
[0026]
【The invention's effect】
The image feature vector clustering method and apparatus according to the present invention obtains initial values of each component of the representative vector based on the lowest resolution image derived from the input original image itself, and uses these initial values, Parameters that specify the degree of the preferred classification, since the optimal classification of feature vectors in the next lowest resolution image is sequentially obtained and finally the classification of feature vectors extracted from each pixel of the original image is obtained. The feature vector extracted from each pixel of the original image can be classified according to the optimum classification according to the content of the original image. Therefore, even if any original image is input, stable classification performance can be realized, and this is extremely effective when performing continuous segmentation on a large number of images including various elements to be photographed. is there.
[0027]
Further, as described above, the clustering method or apparatus according to the present invention, when obtaining the optimum classification of feature vectors in each low-resolution image or original image, pixels that gather together to form one image region in the real image space In view of the high possibility that a feature vector corresponding to す る will form one cluster in the feature vector space, a new one is created based on the correspondence between the selected image region in the real image space and the temporary cluster in the feature vector space. A representative vector is added. Therefore, the clustering method and apparatus according to the present invention obtains a representative vector for optimal classification while reflecting information in the real image space, so that the real image space of one original image is converted into the original image. It is particularly suitable for application to an area dividing process for dividing an object area corresponding to an imaging target element such as “sky”, “sea”, “building” and the like.
[0028]
Furthermore, the image feature vector clustering method and apparatus according to the present invention sequentially performs classification processing on an image with a reduced resolution, that is, an image with a reduced number of feature vectors. Thus, the calculation amount does not become excessive.
[0029]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the drawings.
[0030]
FIG. 1 is a flowchart showing a procedure of clustering processing according to one embodiment of the present invention. The purpose of this clustering process is to classify the feature vectors extracted from each pixel of the original image into a plurality of clusters. The original image is “sky”, “sea”, “building”. It can be used for area division processing that divides into a plurality of image areas corresponding to the elements to be imaged. In the present embodiment, the original image is a digital photographic image having 1024 × 1024 pixels, and the feature vector is a three-dimensional vector having a luminance component and two color difference components expressed in the YCC color system. Suppose there is.
[0031]
When the original image is input, first, in step 10 of FIG. 1, a plurality of low resolution images having different resolutions are derived step by step. In this embodiment, as shown in FIG. 2, starting from the original image, low resolution images with half the vertical and horizontal pixels are sequentially obtained, and finally the ninth low resolution image, that is, Assume that a low-resolution image having 2 × 2 pixels is obtained. This low resolution image having 2 × 2 pixels is the lowest resolution image in this embodiment.
[0032]
Any method of image reduction processing for obtaining each of these low resolution images may be used, but in this embodiment, reduction processing using a Gaussian pyramid is used. The reduction process using the Gaussian pyramid is the step of deriving a blurred image by applying a Gaussian filter to the image to be reduced, and picking up every other pixel in such a blurred image and calculating the number of vertical and horizontal pixels respectively. This is a process of sequentially deriving low-resolution images having different resolutions by sequentially repeating the steps of deriving an image that has been reduced to half. The Gaussian filter used is, for example, as shown in FIG. 3 if the filter size is 5 × 5. Regarding the processing of the image edge, for example, when a 5 × 5 size filter shown in FIG. 3 is used, appropriate pixel values for two rows or two columns on each side of the image to be reduced are used. For convenience, a blurred image having the same size as the original image to be reduced can be derived. As the “appropriate pixel value” of the pixel to be added, a zero value, a value obtained by repeating the pixel value at the image end, or the like can be used.
[0033]
When the derivation of the low-resolution image is completed, next, in step 12 of FIG. 1, two or more initial representative vectors, that is, initial values of the components of the representative vector are determined based on the lowest resolution image (2 × 2 pixels). Derived. The initial representative vector derivation process will be described in detail below with reference to the flowchart of FIG. 4 and the conceptual diagram of FIG.
[0034]
First, in step 40 of FIG. 4, one original representative vector is derived from the lowest resolution image. In the present embodiment, one vector having the average value of each component of the feature vector extracted from the four pixels forming the lowest resolution image as the component is defined as the original representative vector. For example, in the feature vector space shown in FIG. ₁ , OB ₂ , OB ₃ And OB ₄ Is a feature vector extracted from four pixels forming the lowest resolution image, the original representative vector is OA. Note that the feature vector OB ₁ , OB ₂ , OB ₃ And OB ₄ Each extraction source pixel is as shown in FIG.
[0035]
Next, in step 42 in FIG. 4, the distance between each of the above four feature vectors and the original representative vector is calculated. In the present embodiment, this distance is assumed to be the Euclidean distance in the feature vector space. In the example of FIG. 5A, the calculated distances are d ₁ , D ₂ , D ₃ And d ₄ It is.
[0036]
Subsequently, in step 44, the feature vector indicating the maximum distance among the distances calculated in step 42 is set as the first representative vector candidate in the candidate ranking. In the example of FIG. 5A, the distance d ₁ , D ₂ , D ₃ And d ₄ The maximum distance is d ₁ Therefore, the feature vector indicating the maximum distance is the vector OB ₂ So vector OB ₂ Is the first representative vector candidate in the candidate ranking, that is, the first representative vector candidate.
[0037]
Next, in step 46, the remaining feature vectors or three vectors OB ₁ , OB ₃ And OB ₄ , The original representative vector OA and the representative vector candidate OB ₂ The distance to the one closest to the feature vector is identified. In this example, as shown in FIG. ₄ For representative vector candidate OB ₂ Is smaller than the distance to the original representative vector OA. ₁ 'Is specified. Vector OB ₁ And OB ₃ , The distance from the original representative vector OA is the representative vector candidate OB ₂ Because the distance is smaller than ₂ 'And d ₃ 'Is specified.
[0038]
Subsequently, in step 48, the feature vector indicating the maximum distance among the distances calculated in step 46 is set as a representative vector candidate of the next highest candidate rank. In the example of FIG. 5B, the maximum distance d ₁ The feature vector indicating 'is the vector OB ₄ So vector OB ₄ Is the second representative vector candidate in the second candidate ranking.
[0039]
Next, in step 50, it is confirmed whether there is a feature vector that has not yet been assigned a candidate rank. Here, the feature vector OB is still ₁ And OB ₃ Since no candidate rank has been assigned to, the process returns to step 46. In step 46 performed again here, as shown in FIG. ₁ And OB ₃ For both, the original representative vector OA and the representative vector candidate OB ₂ And OB ₄ Since the vector having the closest distance is the original representative vector OA, the distance d to the original representative vector OA as shown in the figure. ₁ '' And d ₂ '' Is specified. In the following step 48, the distance d ₁ '' Is d ₂ Is larger than '', so the feature vector OB ₁ Is the third representative vector candidate in the third candidate ranking.
[0040]
In this way, step 46 to step 50 in FIG. 4 are repeated until all four feature vectors are given candidate ranks. ₂ , OB ₄ , OB ₁ , OB ₃ Are added to the representative vector candidates in this order, and the first to fourth candidate rankings are given.
[0041]
Subsequently, in step 52 of FIG. 4, it is confirmed whether or not the candidate rank of the feature vector having the largest change amount of the maximum distance when added to the representative vector candidate is equal to or lower than the second rank. The As described above with reference to FIG. 5, in this example, the feature vector OB ₂ Is added to the representative vector candidate as the first representative vector candidate, the maximum distance is d ₁ To d ₁ And then the feature vector OB ₄ Is added to the representative vector candidate, the maximum distance is d ₁ 'To d ₁ '' Has changed. This change in the maximum distance is illustrated in FIG. That is, in this example, the change amount of the maximum distance is the feature vector OB ranked third in the candidate ranking. ₁ 1 is the maximum when the vector is added to the representative vector candidate, the process of FIG. 1 proceeds to step 54, and the feature vectors up to the third candidate rank, that is, the vector OB ₂ , OB ₄ And OB ₁ Is the initial representative vector OR ₁ , OR ₂ And OR ₃ It is said. On the other hand, if the candidate rank confirmed in step 52 is the first candidate rank, the process of FIG. 1 proceeds to step 56, and the feature vector of the second candidate rank is the initial representative vector OR. ₁ And OR ₂ It is said.
[0042]
Here, in the present embodiment, the initial representative vector is selected on the basis of the change amount of the maximum distance in the feature vector space as described above. However, the change amount of the average distance or the like may be used as a reference. Alternatively, since the number of pixels is considerably reduced in the lowest resolution image (four pixels in this embodiment), all of the feature vectors extracted from each pixel of the lowest resolution image may be used as the initial representative vector. In short, as long as two or more initial representative vectors corresponding to the original image are obtained by a predetermined process from the lowest resolution image itself derived from the original image without requiring input of any external parameters, It belongs to the scope of the present invention.
[0043]
Returning to FIG. 1, subsequently, in step 14, an image having the next lowest resolution, that is, an eighth low-resolution image having 4 × 4 pixels is set as the current image, and the classification process in the current image is started. Hereinafter, the classification process in the current image having 4 × 4 pixels will be described in order with reference to FIGS.
[0044]
First, in step 16 of FIG. 1, feature vectors having a luminance component and two color difference components in the YCC color system are extracted from each of the 16 pixels constituting the current image, and these 16 feature vectors are extracted. Are mapped to the feature vector space, that is, the YCC color space.
[0045]
Subsequently, in step 18, the 16 feature vectors are classified into clusters represented by the representative vectors. The current representative vector is the initial representative vector OR derived from the lowest resolution image. ₁ , OR ₂ And OR ₃ Therefore, 16 feature vectors are classified into three clusters represented by these. In the present embodiment, each feature vector is classified into a cluster represented by a representative vector having the closest distance on the basis of the Euclidean distance in the feature vector space.
[0046]
Next, in step 20, the current image is divided into image regions according to the feature vector classification by the cluster. Referring to FIG. 7, (a) of FIG. 7 shows the same minimum resolution image as that shown in FIG. FIG. 7B is a current image of 4 × 4 pixels, and the feature vector extracted from each pixel is the representative vector OR in the previous step 16. ₁ , OR ₂ And OR ₃ It is shown to which of the clusters represented by. In the present embodiment, the current image is subjected to a labeling process for attaching the same label to pixels forming island-like regions separated from each other in the real image space by a method such as raster scanning or region expansion. Then, as shown in FIG. 7C, labels of 0 to 3 are attached to the respective pixels. Based on these labels, four image regions 60, 62, 64 and 66 are defined as shown in FIG. Here, the feature vector extracted from each pixel forming the image regions 60 and 66 is represented by a representative vector OR in the feature vector space. ₃ Belong to one representative cluster, but in the real image space, these pixels are separated by an image region 64 as shown, thus forming separate image regions 60 and 66.
[0047]
Subsequently, in step 22 of FIG. 1, an image region corresponding to one selected cluster selected from the three clusters is specified, and in step 24, it is confirmed whether or not there are a plurality of specified image regions. Is done. In this example, as shown in (d) of FIG. 7, the selected cluster is a representative vector OR. ₁ Or OR ₂ 1, since there is only one corresponding image region of the image region 62 or 64, the process of FIG. 1 proceeds to step 36 described later, but the selected cluster is a representative vector OR. ₃ If there are two corresponding image areas (that is, image areas 60 and 66), the process proceeds from step 26 to step 34. Hereinafter, the processing of these steps 26 to 34 will be described.
[0048]
First, in step 26, a plurality of selected image areas are selected from the plurality of image areas specified in step 22. In this embodiment, it is assumed that two image areas are selected from the descending order of the number of constituent pixels as the selected image area. Here, since the specified image areas are originally two of the image areas 60 and 66, both are selected as the selected image areas. FIG. 8A shows the distribution of feature vectors corresponding to the pixels belonging to the image regions 60 and 66 in the feature vector space, and the representative vector OR of the current selected cluster. ₃ FIG.
[0049]
Subsequently, in step 28, one temporary representative vector is extracted from each of the selected image regions 60 and 66. In the present embodiment, as a temporary representative vector, a vector whose component is an average value of each component of a feature vector corresponding to a pixel belonging to each selected image region is used. Hereinafter, temporary representative vectors extracted from the selected image regions 60 and 66 are respectively represented as vectors OT. ₁ And OT ₂ And
[0050]
Next, in step 30, the feature vectors corresponding to the pixels belonging to the selected image regions 60 and 66 are converted into the temporary representative vectors OT extracted in step 28 described above. ₁ And OT ₂ Temporary cluster C represented by ₁ And C ₂ Reclassified. In the present embodiment, similar to the classification in step 18, each feature vector is classified into a temporary cluster represented by the temporary representative vector having the closest distance on the basis of the Euclidean distance in the feature vector space. Here, the reclassification to the temporary cluster is as shown by a solid line in FIG.
[0051]
Subsequently, in step 32, the selected image regions 60 and 66 and the temporary cluster C ₁ And C ₂ The temporary cluster group is specified based on the correspondence relationship. In this embodiment, this step 32 is performed by the process shown in the flowchart of FIG.
[0052]
The process shown in FIG. 9 includes, for each temporary cluster, the temporary cluster includes all the feature vectors corresponding to the pixels in the selected image area from which the temporary representative vector representing the temporary cluster is extracted. It is checked whether or not the temporary cluster does not include the feature vector corresponding to the pixel in the selected image area (step 70). It is assumed that a cluster group is configured (step 72). If there are still temporary clusters remaining (step 74), the remaining temporary clusters are combined into another temporary cluster group (step 76). ) In the present embodiment, since two image areas are selected as the selected image areas in order from the largest number of constituent pixels in step 26, in other words, the processing shown in FIG. 9 is performed for each of the two selected image areas. If there is a complete correspondence between the pixels belonging to and the feature vectors belonging to each of the two temporary clusters, each of the two temporary clusters forms one temporary group, that is, a total of two temporary cluster groups In the case where there is no such complete correspondence, two temporary clusters collectively constitute only one temporary cluster group. Here, as shown in FIG. 8B, all the feature vectors corresponding to the pixels in the image area 60 are provisional clusters C. ₁ And the feature vectors corresponding to the pixels in the image area 66 are all temporary clusters C ₂ Belongs to. That is, since there is the above-mentioned complete correspondence, as shown by a broken line in FIG. ₁ And C ₂ Each constitute one temporary cluster group.
[0053]
Thereafter, in step 34 of FIG. 1, a representative vector OR representative of the currently selected cluster. ₃ Instead, a vector representing each temporary cluster group is set as a new representative vector. Here, temporary cluster C ₁ And C ₂ Are supposed to form one temporary cluster group, so that the temporary representative vector OT ₁ And OT ₂ As a vector representing each temporary cluster group, and the representative vector OR ₃ It is assumed that a new representative vector is substituted for.
[0054]
Here, the significance of steps 32 and 34 will be described. When the original image shown in FIG. 2 is compared with (d) of FIG. 7, each pixel belonging to the image area 60 of the current image is a pixel in which the feature of the empty part in the original image is mainly compressed. It can be seen that each pixel belonging to 66 is a pixel in which the features of the water portion in the original image are mainly compressed. The sky part and the water part are both bluish in color, and the difference in their characteristics is small compared to the difference between the sky part and the grassland part, for example. If a feature vector is extracted by collecting a large number of pixels in the portion and pixels in the water portion, it is considered that the sky portion and the water portion are gradually distinguished even in the feature vector space. On the other hand, parts corresponding to different subject elements, such as the sky part and the water part, which are relatively similar in characteristics, are blurred and connected in a low-resolution image with a small number of pixels in the real image space. Although there is a tendency to form an image area, when the image resolution is increased (that is, the number of pixels is increased) and the outline of each imaging target element gradually becomes clear, an image area separated from each other is formed. start. In the above example, the image regions 60 and 66 were separated in the real image space when proceeding from the lowest resolution image to the current image of 4 × 4 pixels. Therefore, when a temporary representative vector is extracted from each of the image regions 60 and 66 and reclassified into a temporary cluster, even in the feature vector space, the image region 60 in which the feature of the empty part is mainly compressed is used. The pixels were completely separated from the pixels in the image area 66 where the features of the water part were mainly compressed. Therefore, in order to reflect the information in the real image space in the clustering process, the temporary representative vector OT ₁ And OT ₂ The representative vector OR ₃ A new representative vector to replace
[0055]
On the other hand, although different from the above example, if the distribution of feature vectors corresponding to each pixel belonging to two selected image regions is as shown in FIG. ₁ And OT ₂ Temporary cluster C by ₁ And C ₂ The reclassification is as shown by a solid line in FIG. In this case, feature vectors derived from the two selected image regions are mixed in each temporary cluster, and between the pixels belonging to each of the two selected image regions and the feature vectors belonging to each of the two temporary clusters. Does not have a complete correspondence as described above. Such a situation occurs, for example, when there are a plurality of water portions in the original image and the two selected image regions are separated in the real image space, but both correspond to the water portions. In such a case, provisional cluster C ₁ Feature vector and temporary cluster C ₂ It is not appropriate to perform a clustering process in which feature vectors belonging to are classified. Therefore, according to the process shown in FIG. 9, as shown by the broken line in FIG. ₁ And C ₂ Collectively constitute one temporary cluster group. In this case, the representative vector OR of the original selected cluster is used as a vector representing the temporary cluster group. ₃ Shall be adopted. That is, even after step 34 in FIG. 1, the original representative vector OR ₃ Will continue to be used as the representative vector.
[0056]
When the processing of steps 26 to 34 is completed, it is confirmed in step 36 of FIG. 1 whether or not there is a cluster for which the corresponding image area has not yet been specified. The processing of steps 22 to 36 is performed for all clusters. Repeated.
[0057]
Thereafter, the process proceeds to step 38 where it is confirmed whether or not the current image is an original image. Here, since the original image at the present stage is the eighth low-resolution image of 4 × 4 pixels, the processing shown in FIG. 1 returns to step 14, the original image is made the current image, and each pixel of the original image is Steps 14 to 38 are repeated until a final representative vector for classifying the extracted feature vector is obtained.
[0058]
According to the embodiment described above, two or more initial representative vectors are obtained based on the 2 × 2 minimum resolution image derived from the input original image itself, and these initial representative vectors are used. By sequentially finding the optimum classification of feature vectors in the next lowest resolution image, the classification of feature vectors extracted from each pixel of the original image is finally obtained, so input of external parameters is required. In addition, classification can be performed according to the optimum degree of classification according to the contents of the original image. Therefore, stable classification performance can be realized no matter what original image is input.
[0059]
Further, according to the above embodiment, in each low-resolution image or original image, representative vectors for optimal classification are sequentially obtained while reflecting information in the real image space. Especially suitable for application.
[0060]
Next, a modified example of the above embodiment will be described with reference to FIGS. In the processing in this modified example, in step 26 of FIG. 1, five image areas (all image areas when the number of image areas is 2 to 4) from the descending order of the number of constituent pixels are selected image areas. Except that the processing shown in FIG. 12 is performed in place of the processing shown in FIG. 9 in step 32, and is the same as the processing in the above embodiment.
[0061]
For the purpose of explaining this modification, an image area that is connected in a certain low-resolution image is separated into five or more image areas in the real image space when proceeding to the next lower-resolution image. To V are selected as selected image areas. The distribution in the feature vector space of the feature vectors corresponding to the pixels belonging to these selected image areas I to V, and the temporary representative vector OT extracted from these selected image areas _I To OT _V Distribution, and temporary cluster C represented by these temporary representative vectors _I To C _V It is assumed that the classification by is as shown in FIG.
[0062]
Here, when the processing shown in FIG. 12 is performed, first, in step 80, the temporary cluster C _I To C _V Each of the temporary clusters includes all feature vectors corresponding to the pixels in the selected image area from which the temporary representative vectors representing the temporary clusters are extracted, and corresponds to the pixels in the other selected image areas. It is checked whether the cluster is a temporary cluster that does not include a feature vector. In the example of FIG. 11, the temporary cluster C _I 11 includes all the feature vectors corresponding to the pixels in the selected image area I as the extraction source, and does not include the feature vectors corresponding to the pixels in the other selected image areas II to V. Processing proceeds to step 82 where this temporary cluster C _I However, it is assumed that it constitutes one temporary cluster group independently.
[0063]
Subsequently, in step 84, the remaining temporary cluster C _II To C _V Only for each other, it is confirmed whether or not there are a plurality of temporary clusters exchanging feature vectors corresponding to pixels in the selected image region from which the temporary representative vectors representing the temporary clusters are extracted. In the example of FIG. 11, the temporary cluster C _II And C _III However, both include only feature vectors derived from the selected image regions II and III, and the patterns are the same. In addition, the feature vectors derived from the selected image regions II and III are stored in other temporary clusters C _I , C _IV And C _V It is not included in any of. Therefore, provisional cluster C _II And C _III Are tentative representative vectors OT that represent the tentative cluster only within each other. _II And OT _III Correspond to a plurality of temporary clusters exchanging feature vectors corresponding to the pixels in the selected image regions II and III from which extraction is performed. _II And C _III Is specified as one temporary cluster group. Temporary cluster C _IV And C _V The same can be said for this set.
[0064]
Finally, in step 88, it is confirmed whether or not there are temporary clusters that do not yet belong to any of the temporary cluster groups. If they remain, in step 90, the remaining temporary clusters are collected together. Furthermore, one temporary cluster group is specified. In the example of FIG. 11, since there are no remaining temporary clusters, the process shown in FIG. 12 ends without further specifying a temporary cluster group.
[0065]
Through the above processing, three temporary cluster groups as indicated by broken lines in FIG. 11 are specified. Such a state is, for example, among the selected image regions I to V, where two regions of grassland where region I is a mountain portion and regions II and III are separated in a real image space across a road or river portion, This occurs when the regions IV and V correspond to two tree parts separated from each other in the real image space.
[0066]
Here, in the above-described embodiment described with reference to FIGS. 8 to 10, when any one of the two temporary clusters includes a single feature vector derived from different selected image regions, 2 One temporary cluster is assumed to belong to one temporary cluster group, and the representative vector is not increased. Such processing is preferable at the initial stage where a low-resolution image of about 4 × 4 pixels, which is described in detail above, is handled as the current image. However, as the resolution of the current image gradually increases, most of the feature vectors are selected for each selected image. Even though it is classified as a temporary cluster corresponding to a region, only two feature vectors derived from different selected image regions are mixed, and two temporary clusters are not classified into different temporary cluster groups. In some cases, the number of representative vectors does not increase effectively, and clustering processing based on the optimal classification level cannot be performed. A similar situation can occur in the modification described with reference to FIGS. In order to prevent such a situation, in the above embodiment and the modified example, between step 30 and step 32 in FIG. 1, for each temporary cluster, the total number of feature vectors belonging to the temporary cluster is changed to the temporary cluster. When there is a selected image area in which the ratio of the number of corresponding feature vectors to which the image belongs is smaller than a predetermined ratio, a step of excluding the feature vector corresponding to the selected image area from the temporary cluster may be further included. As this “predetermined ratio”, for example, a value of about 5% can be adopted.
[0067]
In addition, for further optimization of the classification result, a step of updating each representative vector to a more appropriate one based on the feature vector included in each cluster is included between step 18 and step 20 in FIG. It may be. For example, a vector indicating the center of gravity of feature vectors belonging to each cluster can be adopted as a new representative vector. In addition to this, a step of reclassifying the feature vectors based on the Euclidean distance or the like based on the updated representative vector and updating the cluster may be further included.
[0068]
Further, in order to exclude an image region that is considered to be so-called noise, which is composed of pixels smaller than a predetermined ratio (for example, about 1/1000) of the number of pixels forming the current image, the steps 20 and 22 in FIG. In the meantime, a step of updating the image region defined in step 20 by integrating the micro region into the non-micro region may be further included. As a method of integration, for example, a method of specifying an adjacent image region that touches a boundary with a minute region, and performing processing for integrating the minute region into an adjacent image region having the longest border length in order from a smaller minute region. Alternatively, an adjacent image region that borders the minute region is identified, one feature vector is extracted from each of the minute region and all the neighboring image regions, and an adjacent image region having the shortest distance between feature vectors in the feature vector space And a method of performing processing for integrating the minute regions in order from the smallest minute region.
[0069]
In the above-described embodiments and modification examples, a plurality of image regions having a large number of constituent pixels are sequentially selected as a selection image region from among a plurality of image regions. However, the selection method of the selection image region is not limited thereto. A form in which all of a plurality of specified image areas are selected image areas also belongs to the scope of the present invention.
[0070]
In the above-described embodiments and modifications, the three-dimensional vector including the luminance component and the two color difference components expressed in the YCC color system is used as the feature vector. However, each component of the feature vector is not limited thereto. The dimension of the feature vector is not limited to 3.
[0071]
Furthermore, in the above-described embodiments and modifications, for convenience of explanation, the original image is a square image having 1024 × 1024 pixels, but it goes without saying that the present invention can also be applied to original images having different vertical and horizontal pixel numbers. Yes. Each low-resolution image is not limited to a square image. Further, the number of pixels of the minimum resolution image is not limited to four, and any number of pixels may be used as long as it is a plurality of pixels smaller than the number of pixels of the original image.
[0072]
In addition, the above-described embodiments and modification examples are intended to classify feature vectors extracted from each pixel of the target image using the target image itself that is a target of region division or the like as an original image. A mode in which a reduced image that has been subjected to image reduction processing in advance as an original image and classification of feature vectors extracted from each pixel of the reduced image is also within the scope of the present invention. In this case, after classifying the feature vector extracted from each pixel of the reduced image, the image is subjected to image enlargement processing again on the reduced image. It can be used for area division processing or the like.
[0073]
Note that the clustering process according to the above and other embodiments of the present invention may be executed by a computer program. In addition, the above description has been made with respect to a method for convenience of description, but an apparatus including means for performing each of the above steps is also within the scope of the present invention.
[0074]
As mentioned above, although embodiment and the modification of this invention were described in detail, these are only illustrations, The technical scope of this invention should be defined only by the claim in this specification Needless to say.
[Brief description of the drawings]
FIG. 1 is a flowchart showing a procedure of clustering processing according to an embodiment of the present invention.
FIG. 2 is a conceptual diagram showing a method for deriving each low-resolution image in the embodiment of FIG.
FIG. 3 is a diagram showing an example of a Gaussian filter used for deriving each low-resolution image.
4 is a flowchart showing in detail an initial representative vector derivation step in the embodiment of FIG. 1;
5 is a conceptual diagram showing each stage of the initial representative vector derivation process shown in FIG. 4;
6 is a bar graph showing a change in the maximum distance which is a reference for selecting an initial representative vector in the initial representative vector derivation step shown in FIG.
7 is a conceptual diagram showing a method of dividing a current image into image areas in the embodiment of FIG.
FIG. 8 is a conceptual diagram showing a method for identifying a temporary cluster group in the embodiment of FIG.
FIG. 9 is a flowchart showing a method for specifying a temporary cluster group in the embodiment of FIG. 1;
10 is a conceptual diagram showing a method for specifying a temporary cluster group in the embodiment of FIG.
11 is a conceptual diagram showing a method for specifying a temporary cluster group in a modification of the embodiment of FIG.
12 is a flowchart showing a method for identifying a temporary cluster group in the modification of FIG.

Claims (18)

Deriving from the original image a low resolution image composed of a plurality of pixels having different resolutions in stages;
Obtaining an initial value of each component of two or more representative vectors from the lowest resolution image having the lowest resolution among the plurality of low resolution images;
Extracting the feature vector from each pixel of the current image, using the next lowest resolution image as the current image;
Mapping each of the feature vectors to a feature vector space;
Classifying the feature vectors into clusters represented by each of the representative vectors in the feature vector space;
Dividing the current image into image regions based on a distribution on the current image of pixels corresponding to the feature vectors belonging to each of the clusters;
Identifying the image region corresponding to one selected cluster selected from the clusters;
A step performed when a plurality of image regions are specified by the specification, wherein one temporary representative vector is extracted from each of a plurality of selected image regions selected from the plurality of image regions, and the feature vector space The feature vectors corresponding to the pixels belonging to the plurality of selected image regions are reclassified into temporary clusters represented by the temporary representative vectors, and based on the correspondence relationship between the selected image regions and the temporary clusters. Identifying one or a plurality of temporary cluster groups, and replacing a vector representing each of the temporary cluster groups with a new representative vector instead of the representative vector representing the selected cluster;
For all the clusters, repeating the step of identifying the image region and the step of performing the steps when the plurality of image regions are identified;
The step of repeating the repeating step from the step of extracting the feature vector until the original image is the current image and a final representative vector for classifying the feature vector extracted from each pixel of the original image is obtained. A method for clustering feature vectors of an image characterized by including the image. The identification of the one or more temporary cluster groups is
Includes all the feature vectors corresponding to the pixels in the selected image region from which the temporary representative vectors representing the temporary cluster are extracted, and includes the feature vectors corresponding to the pixels in the other selected image regions If there is no temporary cluster, the first step of identifying the temporary cluster as one temporary cluster group;
When the temporary cluster that does not belong to any of the temporary cluster groups specified in the first step remains, a second group that specifies the group of the remaining temporary clusters as one temporary cluster group The clustering method according to claim 1, wherein the clustering method is performed by the following steps. The identification of the one or more temporary cluster groups is
Includes all the feature vectors corresponding to the pixels in the selected image region from which the temporary representative vectors representing the temporary cluster are extracted, and includes the feature vectors corresponding to the pixels in the other selected image regions If there is no temporary cluster, the first step of identifying the temporary cluster as one temporary cluster group;
When there are a plurality of temporary clusters exchanging the feature vectors corresponding to the pixels in the selected image area from which the temporary representative vectors representing the temporary clusters only in the mutual are extracted, A second step of identifying a group of temporary clusters as one temporary cluster group;
When the temporary cluster that does not belong to any of the temporary cluster groups specified in the first step and the second step remains, the group consisting of the remaining temporary clusters is regarded as one temporary cluster. The clustering method according to claim 1, wherein the clustering method is performed by a third step of specifying as a group. After reclassification to the temporary cluster and before identifying the one or more temporary cluster groups,
For each of the temporary clusters, if there is a selected image area in which the ratio of the number of corresponding feature vectors belonging to the temporary cluster is less than a predetermined ratio with respect to the total number of the feature vectors belonging to the temporary cluster, the selected image area 4. The clustering method according to claim 2, wherein the feature vector corresponding to is excluded from the temporary cluster. Between the step of classifying into the cluster and the step of dividing the current image into image regions,
The clustering method according to claim 1, further comprising a step of updating the representative vector based on the feature vector included in each of the clusters. Between the step of classifying into the cluster and the step of dividing the current image into image regions,
Updating the representative vector based on the feature vectors included in each of the clusters;
The clustering method according to claim 1, further comprising a step of updating the cluster based on the updated representative vector. Between the step of dividing the current image into image regions and the step of identifying the image regions,
The clustering method according to claim 1, further comprising a step of updating the image area by integrating a minute area into a non-minute area. The clustering method according to any one of claims 1 to 7, wherein the plurality of selected image regions are obtained by sequentially selecting a plurality of image pixels having a large number of constituent pixels from the plurality of image regions. Obtaining the initial value comprises:
deriving one original representative vector from the lowest resolution image consisting of n pixels;
A distance in the feature vector space between the n feature vectors extracted from each of the n pixels and the original representative vector is obtained, and a feature vector indicating the maximum distance is set as a representative vector candidate and the highest Assigning candidate ranks,
A distance in the feature vector space between each of the remaining feature vectors and the original representative vector and the representative vector candidate closest to the feature vector is obtained, and a feature vector indicating a maximum distance is determined as the representative vector candidate. And adding the next highest candidate ranking,
Repeating the step of assigning the next highest candidate ranking;
2. The method according to claim 1, further comprising: setting values of each component of the top two or more feature vectors of the representative vector candidates as the initial values of the components of the representative vector according to the candidate ranking. 9. The clustering method according to any one of 8 to 8. Means for deriving a low resolution image composed of a plurality of pixels having different resolutions in stages from the original image;
Means for obtaining an initial value of each component of two or more representative vectors from the lowest resolution image having the lowest resolution among the plurality of low resolution images;
Means for extracting a feature vector from each pixel of the current image, with the next lowest resolution image as the current image;
Means for mapping each of the feature vectors to a feature vector space;
Means for classifying the feature vectors into clusters represented by each of the representative vectors in the feature vector space;
Means for dividing the current image into image regions based on a distribution on the current image of pixels corresponding to the feature vectors belonging to each of the clusters;
Means for identifying the image region corresponding to one selected cluster selected from the clusters;
Means for operating when a plurality of image regions are specified by the specification, wherein one temporary representative vector is extracted from each of a plurality of selected image regions selected from the plurality of image regions, and the feature vector In the space, the feature vectors corresponding to the pixels belonging to the plurality of selected image areas are reclassified into temporary clusters represented by the temporary representative vectors, and the correspondence relationship between the selected image area and the temporary clusters is obtained. Means for identifying one or more temporary cluster groups based on, and replacing the vectors representing each of the temporary cluster groups with a new representative vector instead of the representative vector representing the selected cluster;
Means for repeatedly operating the means for specifying the image area and the means for operating when the plurality of image areas are specified for all the clusters;
Until the original image is the current image and a final representative vector for classifying the feature vector extracted from each pixel of the original image is obtained, the means for extracting the feature vector is repeatedly operated. An apparatus for clustering image feature vectors, characterized by comprising means for operating. Identifying the one or more provisional cluster groups,
Includes all the feature vectors corresponding to the pixels in the selected image region from which the temporary representative vectors representing the temporary cluster are extracted, and includes the feature vectors corresponding to the pixels in the other selected image regions If there is no temporary cluster, a first means for identifying the temporary cluster as one temporary cluster group;
When the temporary cluster that does not belong to any of the temporary cluster groups specified by the first means remains, a second group that specifies a group of the remaining temporary clusters as one temporary cluster group The clustering apparatus according to claim 10, wherein the clustering apparatus is performed by means. Identifying the one or more provisional cluster groups,
Includes all the feature vectors corresponding to the pixels in the selected image region from which the temporary representative vectors representing the temporary cluster are extracted, and includes the feature vectors corresponding to the pixels in the other selected image regions If there is no temporary cluster, a first means for identifying the temporary cluster as one temporary cluster group;
When there are a plurality of temporary clusters exchanging the feature vectors corresponding to the pixels in the selected image area from which the temporary representative vectors representing the temporary clusters only in the mutual are extracted, A second means for specifying a group of temporary clusters as one temporary cluster group;
When the temporary cluster that does not belong to any of the temporary cluster groups specified by the first means and the second means remains, a group of the remaining temporary clusters is regarded as one temporary cluster group. The clustering apparatus according to claim 10, wherein the clustering apparatus is performed by third means that specifies The means that operates when the plurality of image regions are specified is classified into the temporary cluster for each of the temporary clusters after the reclassification to the temporary cluster and before the one or more temporary cluster groups are specified. If there is a selected image area in which the ratio of the number of corresponding feature vectors belonging to the temporary cluster is less than a predetermined ratio with respect to the total number of the feature vectors belonging to the temporary cluster, the feature vector corresponding to the selected image area is extracted from the temporary cluster. 13. The clustering apparatus according to claim 11, wherein the clustering apparatus is excluded. 14. The clustering apparatus according to claim 10, further comprising means for updating the representative vector based on the feature vector included in each of the clusters. Means for updating the representative vector based on the feature vectors included in each of the clusters;
14. The clustering apparatus according to claim 10, further comprising means for updating the cluster based on the updated representative vector. 16. The apparatus according to claim 10, further comprising means for updating the image area defined by the means for dividing the current image into image areas by integrating a minute area into a non-minute area. A clustering device described in the section. The clustering apparatus according to any one of claims 10 to 16, wherein the plurality of selected image regions are obtained by sequentially selecting a plurality of image pixels having a large number of constituent pixels from the plurality of image regions. Means for determining the initial value;
means for deriving one original representative vector from the lowest resolution image comprising n pixels;
A distance in the feature vector space between the n feature vectors extracted from each of the n pixels and the original representative vector is obtained, and a feature vector indicating the maximum distance is set as a representative vector candidate and the highest A means to rank candidates,
A distance in the feature vector space between each of the remaining feature vectors and the original representative vector and the representative vector candidate closest to the feature vector is obtained, and a feature vector indicating a maximum distance is determined as the representative vector candidate. Means to add and rank the next highest candidate ranking,
Means for repeatedly operating the means for assigning the next highest candidate ranking;
The apparatus further comprises means for setting values of each component of the top two or more feature vectors of the representative vector candidates as the initial values of the components of the representative vector according to the candidate rank. Item 18. The clustering apparatus according to any one of Items 10 to 17.

Images