KR100830949B1 - Dynamic Clustering Method for Relevance Feedback of Region-based Image Finder - Google Patents

Abstract

The present invention relates to a dynamic clustering method for conformance feedback of a region-based image retrieval, and more particularly, to a combination of region-based image retrieval and suitability feedback, which is characterized by a color histogram and a color layout representing images at the object level. Materialize the method of image representation in space, make it possible to express higher-level concepts for example images, construct hierarchical clusters to semantically segment the appropriate images, and determine and merge the number of potential clusters It is driven to search for more accurate images by expressing multiple queries with representative points of the final cluster, and by applying Hotelling's T ² _v using a diagonal matrix, the function is calculated with a small number of data. Only the value that corresponds to the diagonal line reduces the cost of calculating the inverse matrix. To achieve the same effect, to solve the high-level singularity problem of region-based cluster merging, and to provide a dynamic clustering method for conformance feedback of region-based image retrieval system that can improve the performance of content-based image retrieval system. will be. The technical configuration of the present invention for this purpose in the region-based image similarity search using the fitness feedback, the first step of generating a region-based query point with multiple representative values by inputting an example image; outputting a query result set as a k-nearest query; A third step of constructing an appropriate image set with user feedback; Generating a region-based classified set by applying region-based cluster classification; And a fifth process of calculating a representative value of the cluster by using the region-based cluster merger.

Conformance Feedback, Image Database, Clustering, Merging, Region-Based Image Retrieval

Description

Adaptive Clustering Method for Relevance Feedback in Region-Based Image Search Engine

1 is a block diagram illustrating a region based image similarity searching process using conformance feedback according to the present invention.

2 is a flow diagram schematically illustrating an algorithm of k-nearest query for region based image retrieval in accordance with the present invention.

3 is a flow diagram schematically illustrating a more detailed algorithm for cluster merging in accordance with the present invention.

4 is a scatter diagram showing the process of cluster merging in accordance with the present invention;

5 is a CPU time comparison graph of a cluster merging process when using a diagonal matrix and an inverse matrix according to the prior art according to the present invention.

Figure 6 is a comparison graph when using the color moment of precision and recall in accordance with the present invention.

7 is a graph comparing query results according to an iterative step of a diagonal matrix according to the present invention and a query point movement and a progressive clustering method according to the related art.

8 is a view showing a query result in one iteration step to a sample query according to the present invention.

9 is a view showing the results of a query in five iterations to a sample query according to the present invention.

<Explanation of symbols for the main parts of the drawings>

10: region-based query point 11: k-nearest query

20: Query result set 21: User feedback

30: Suitable image set 31: Region based cluster classification

40: zone-based classified set 41: zone-based cluster merging

50: representative value of cluster

The present invention relates to a dynamic clustering method for conformance feedback of an area-based image retrieval, in particular by combining area-based image retrieval and relevance feedback, on the feature space of color histograms and color layouts that represent images at the object level. An area-based clustering process to refine image representation methods, to enable higher-level concepts for example images, to include semantically relevant images in the same cluster with similar visual characteristics, and to output semantically related clusters. And region-based cluster merging method to construct hierarchical clusters to semantically associate the divided regions of appropriate images, determine and merge the number of potential clusters, and generate multiple queries with representative points of the final cluster. For more accurate image search By applying Hotelling's T ² _v using diagonal matrix, the function is calculated with a small number of data, so the same effect can be obtained with only the diagonal value that reduces the cost of calculating the inverse matrix of numerical analysis. In addition, the present invention relates to a dynamic clustering method for relevance feedback of a region-based image retrieval that can solve the high-level singularity problem of region-based cluster merging and improve the performance of a content-based image retrieval system.

In general, with the development of computer vision, information retrieval and database management techniques, detailed research on conformance feedback for content-based image retrieval (CBIR) has been conducted, and content-based image retrieval systems represent images as vectors in feature space. Use visual attributes of images such as color histogram, color layout, and texture to index and index them.

Here, each image can be viewed as a data point in the feature space, an example query is mapped to a query point in the same feature space, and a k-nearest query is an image corresponding to k data points close to the query point. , The closer the two vectors in the feature space, the more similar the corresponding images are.

Recent image retrieval uses content properties such as color, texture, and shape to retrieve the most similar images from the large image database to the ones you want (M. Flicker h. Sawhney, W. Niblack et al. Query By image and video content: The QBIC system.IEEE Computer Magazine, 28 (9), pp. 23-32, 1995), (XS Zhou and TS Huang, "Relevance feedback for image retrieval: a comprehensive review, "ACM Multimedia Systems Journal, 8 (6), pp. 536-544, 2003.) has become one of the most active research areas.

Content-based image retrieval expresses image information by points in a feature space, and based on this, the content-based image retrieval system retrieves images according to the following procedure.

(1) The user expresses the image he wants to find in query form and presents it to the system.

(2) The system retrieves an image similar to the user query. At this time, the similarity between the specific image and the query in the database is measured by calculating the distance between two corresponding points in the feature space.

(3) The k images most similar to the user query are retrieved and provided to the customer.

The content-based image retrieval system expresses images as feature vectors using visual features such as color, texture, and shape, and the closer the two vectors are in the feature space, the more similar the corresponding images become.

However, the performance of the search system is very low because the low-level features of the example images do not represent high-level user concepts, and the search system uses the Query-By-Example (QBE) interface to display the example images, features, and feature representations. The user receives input from the user through the interface and uses it for retrieval. In general, users access a content-based image retrieval with a wide range of information needs and express the request as a query.

Relevance feedback is a widely used technique to mitigate the abnormal state and uncertainty of such user information needs. Conformance feedback is a method for improving search performance by automatically regenerating new queries by supplementing incomplete queries by using the user as part of the CBIR system to interact with the system and users.

In other words, through the relevance feedback, the user provides a judgment as to whether the current search result is appropriate or inadequate, and the CBIR system learns the content property of the image that the user wants based on it and repeatedly searches until the user is satisfied. Trying colors can lead to good search results (R. Brunelli, O. Mich, "Image Retrieval by Examples," IEEE TRansactions on Mutlimedia, 2 (3), pp. 164-171,2000), ( XS Zhou and TS Huang, "Relevance feedback for image retrieval: a comprehensive review," ACM Multimedia System Journal, 8 (6), pp. 536-544, 2003).

Learning is reflected in the refinement of query and similarity functions (DH Kim, CW Chung, K. Barnard, "Relevance feedback using adaptive clustering for image similarity retrieval," Journal of Systems and Software, 78 (1), pp. 9 -23, 2005.), (K. Porkaew, K. Chakrabarti, and S. Mehrotra, "Query Refinement for Multimedia Similarity Retrieval in MARS," Proc. 7th ACM Multimedia Conference, pp. 235-238, November 1999.), (L. Wu et al., “FALCON: Feedback Adaptive Loop for Content-Based Retrieval,” Proc. 26th VLDB Conference, pp. 297-306, 2000.).

However, there are few suitability feedback methods that can process complex queries, and the similarity between images recognized by humans may not be proportional to the distance between images in the feature space. Appropriate images may be spread out in feature space, may be interspersed in multiple clusters rather than one cluster, and existing conformance feedback methods that shift the center of the query by linear combination of suitable images do not work well. .

The present invention has been made to solve the above problems, by combining region-based image retrieval and conformance feedback, to specify a method of image representation in the feature space of the color histogram and color layout representing the images at the object level, and the example image Using the region-based clustering process and the region-based cluster merging method to enable the representation of higher-level concepts for, to include semantically relevant images in the same cluster with similar visual features, and to output semantically related clusters. By constructing hierarchical clusters to semantically correlate the segmented regions of the appropriate images, and determining and merging the number of potential clusters, multiple queries are represented by representative points of the final cluster for more accurate image retrieval. Using a diagonal matrix Sterling (Hotelling) of T ² _v applied, because the function computed by a small number of data, and the same advantage as that of only the value corresponding to the angle that reduces the inverse matrix calculation cost of the numerical analysis, of high-level area-based cluster merge It is an object of the present invention to provide a dynamic clustering method for relevance feedback of a region-based image searcher that solves the singularity problem and improves the performance of a content-based image search system.

In order to achieve the above object, the present invention provides a region-based image similarity search using fitness feedback, comprising: a first step of inputting an example image to generate region-based query points with multiple representative values; outputting a query result set as a k-nearest query; A third step of constructing an appropriate image set with user feedback; Generating a region-based classified set by applying region-based cluster classification; And a fifth process of calculating a representative value of the cluster by using region-based cluster merging.
The region-based query point and region-based clustering are performed using a plurality of regions divided for each image.

The output of the query result set by the k-nearest query is output using an Earth Mover Distance (EMD) function that can be applied to a feature expression having a variable length as a distance function of the query and the image.

In addition, when the example image is included in the query result set, the third process is included in a suitable image set calculated by suitability filtering from the query result set, and is repeatedly executed.

In the fourth process, clustering is performed by hierarchical clustering of images of the appropriate image set, and the center, covariance, and weight are calculated for each cluster by applying region-based clustering.

In this case, the fifth process estimates the number of clusters composed of similar regions by applying T ² _v of Hotelling using a diagonal matrix, and merges neighboring clusters in proportion to the number of region clusters.

The second to fifth processes are repeatedly executed until the query result set reaches the significance level set by the user. When the query result set reaches the significance level, iterative execution ends. do.

In addition, T ² _v of Hotelling, which uses a diagonal matrix for all cluster pairs, to merge the clusters of region-based cluster merging into larger clusters. And a first step of calculating c ² of the same cluster pair; Selecting a pair of clusters having a minimum value of T ² _v ; C ² of a cluster pair having the same T ² _v value of the cluster pair selected in the second step A third step of merging the cluster pairs if less than the value; And a fourth step of calculating a new cluster weight, an average vector, and a covariance matrix for the cluster pair merged in the third step. C ² of a cluster pair having the same T ² _v value By selecting the candidate pair of the cluster until the value is exceeded, it characterized in that the cyclical driving in the second step.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a block diagram illustrating a region based image similarity search process using conformance feedback according to the present invention. As shown in the figure, a region-based image similarity search mechanism is schematically shown.

Here, in the preprocessing step, all images are divided into a plurality of areas by applying an image segmentation method, and feature vectors are extracted for the plurality of areas and stored in a database.

The sample image submitted by the user is analyzed to generate an initial query multiple representative value Q = (q, d, k), and q is represented by the feature values of the regions constituting the example image. K is the number of images included in the query result output by the system, d is the distance function, and the query point is applied to the images included in the database by applying the distance function. Are compared.

A query result set (20) consisting of k images close to a query point according to the distance function,

This is provided to the user.

Since each image is composed of a plurality of regions, p _knk is the n _k th region constituting the k th image.

In the next step, the user evaluates the suitability by applying a suitability score to each image included in the query result set 20, and based on the suitability score, as a suitable set of images 30,

Where p'm _n is the nth region of the mth suitable image.

That is, the suitable image set 30 includes the newly added suitable example image and the previous suitable image set, thereby generating Relevant (Q) = Relevant _previous (Q) ∪ {p _i '}, and adding the added suitable image. The example image (p _i ') reflects the concept of the user's query more clearly, so that a larger weight is applied than the weight applied to the _previous relevant image set (Relevant _previous ).

Here, the number of regions included in the example image is rapidly increased because new suitable images are added to and included in the suitable image set 30, and the query and the Earth Mover Distance (EMD) of the image [ RA Johnson, D.W. Wichern. Applied Multivariate Statistical Analysis. Prentice-Hall, N.J., 1998.] is proportional to the number of regions included in the query.

In this case, the region-based clustering process merges similar regions included in the suitable image set 30 to shorten the searching speed of the system, and then uses a hierarchical clustering algorithm to query the next query in the region belonging to the suitable image set 30. A region based cluster merging 41 is performed to merge the cluster into a predetermined number of clusters corresponding to the regions.

After performing the region-based cluster merging 41, the number of inherent clusters is estimated, and adjacent clusters included in the same hierarchy are merged to reduce the number of clusters so that the appropriate set of images for the next iteration step. A new query point is formed using the representative of the cluster generated from the suitable image of (30), and a new multiple representative value including the new query point and the new distance function with the modified weights is calculated to perform a recursive iteration step. Is applied as input for.

In addition, the cyclic iteration step is driven to approximate the optimal multiple representative value Q _opt = (q _opt , d _opt , k). When the user is satisfied with the query result, the final result is output and the search is terminated.

Here, the dynamic clustering method for conformance feedback of the region-based image retrieval according to the present invention is a normalized cuts image segmentation method [J. Shi and J. Malik. Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22 (8), 888-905, August 2000.] divides the image into areas that distinguish objects included in the image.

That is, region based retrieval allows for constructing a multipoint query, i.e. a query with multiple objects (regions), and allows a user to select a suitable image from the appropriate image set 30 of the k-nearest query 11 result images. When selected, the areas that make up the suitable image are relevant points.

In addition, a cluster is generated using the appropriate points, the center of the cluster is adopted as a representative, a multipoint query is constructed using the representative point generated by applying the region-based cluster merger 41 by predicting the optimal number of clusters. Let's do it.

Here, the region-based clustering process is used to improve the search efficiency by constructing a hierarchical tree structure, and the suitable image added to the suitable image set 30 does not change the suitable image set of the previous step, so that the previous step Using the mean and variance computed in, we can reduce the overall running time of the system by calculating statistics for the current clusters.

In addition, the region-based cluster merger (41) is based on the Hotelling T ² [H. Hotelling. Multivariate Quality Control. In C. Eisenhart, MW Hastay, and WA Wallis, eds. Techniques of Statistical Analysis. NY, McGraw-Hill, 1947.] and to apply the modified ² T _v, by merging the pair of clusters any aspect of the thereby calculate the number of clusters for a given query.

2 is a flowchart schematically illustrating an algorithm of k-nearest query for region based image retrieval according to the present invention. As shown in the figure, when a user inputs an example image as a query for searching (S11), q is composed of a plurality of query points in a feature space using the example image, and In operation S12, an initial multiple representative value Q = (q, d, k) having a variable k as the number of images included in the query result and a distance function d are generated.

The multiple representative value Q = (q, d, k) is applied to an EMD (Q, p) representing a distance between a query and an image (S13), and a k-nearest query is performed (S14). In operation S20, a query result set 20 including k images close to the query point is provided to the user.

In addition, the user applies a suitability evaluation to each image included in the query result set 20, and calculates and applies a suitability score based on the suitability evaluation to generate a suitable image set 30.

That is, the suitable image set 30 includes newly added suitable images and a previous set of suitable images, thereby generating Relevant (Q) = Relevant _previous (Q) ∪ {p _i '}, and adding the added suitable images. Since the query and example images (p _i ') clearly reflect the concept of the user's query, apply a weight greater than the weight applied to the Relevant _previous .

Similar regions are merged in the clustering process, and the synthesized images form a multipoint query, and the signature of the Earth Mover Distance (EMD) function is a composite image having regions corresponding to the clusters. Since the Euclidean distance is used to measure the reference distance between the two regions, the total weight of each signature is 1, and the size of each region is used as the weight of the signature.

In this case, when the new example images are included in the suitable image set 30, the number of regions included in the example images is increased to be proportional to the number of regions to calculate the Earth Mover Distance (EMD) between the examples and the images. It takes time.

In addition, to retrieve similar images for the example image, an Earth Mover Distance (EMD) function is used to measure the distance between two images based on an area representation, and the Earth Mover Distance. Since the distance function can be applied to feature representations with variable length, the distance can be measured even if the number of regions of the two images are different, and if the user displays the appropriate images among the images at each stage of the conformance feedback, The system then selects the appropriate image as representative for the cluster and the center of the cluster.

Meanwhile, hierarchical clustering and cluster classification are applied to the appropriate image set 30, and center, covariance, and weight are calculated for each cluster Ci (S33, S34, S35).

Here, the hierarchical clustering method is used to compose suitable images in a hierarchical tree structure, which makes a hierarchical structure using initial clusters for all regions of the suitable images, and g clusters at the g level in the cluster hierarchy. This corresponds to drive the loop to correspond to the level of the cluster and the number of clusters.

Then, a potential cluster is searched by applying T ² _v which transforms Hotel ² 's T ² into a diagonal matrix (S41), and the suitable image set 30 reduces the time proportional to the number in the region. In order to apply a merge and hierarchical clustering algorithm, similar regions included in the suitable image set 30 are merged into a predetermined number of clusters corresponding to the next query region in the region belonging to the suitable image set 30 (S42). ).

In addition, the area-based cluster merging 41 performed in step S42 is used to calculate the number of nested clusters and merge adjacent clusters included in the same hierarchy to reduce the number of clusters. A new query point is formed using a representative of a cluster generated from a suitable image of the appropriate image set 30 for the next iteration step, and the new multiple representative value is applied as a new input to be cycled to the step S13. .

)개의 T² _v 함수값을 이용한다. 임의의 군집 합병이 발생하지 않으면 군집 개수(g)가 군집 개수(g-1)보다 최적값에 근접한다. 그렇지 않으면, 군집 개수(g-1)이 최적값에 더 근접하게 된다.Here, to begin the process of finding the number of clusters, consider the level with (g-1) clusters and the level with g clusters. You need to decide which level is more optimal. At the g cluster level, to determine which cluster pairs to join (

) T ² _v Use a function value. If no cluster merge occurs, the cluster number g is closer to the optimum than the cluster number g-1. Otherwise, the cluster number g-1 is closer to the optimum value.

At this time, the query result from the modified multiple representative value is approximated to the optimal query result set 20. If the query result set 20 is determined to be similar to the optimal value by the user, the algorithm according to the present invention is terminated. If the query result set 20 does not reach the user's significance level (S51), the multiple representative value (S50) modified by the step (S13) is repeated as an input to execute an iterative step.

3 is a flow diagram schematically illustrating a more detailed algorithm for cluster merging in accordance with the present invention. As shown in the figure, for all cluster pairs, T ² _v, which is a variation of Hotelling's T ² , and a critical distance value c ² are calculated (S60), and the minimum value among the T ² _v is calculated. (S61).

_new, S_{new )}을 산출한다(S67).And, c ² which is the minimum distance value of the selected cluster pair is the minimum value of the T ² _v (S63), and the minimum value of T ² _v is c ² which is a threshold distance value of the selected cluster pair. Below, the minimum value of T ² _v merges the selected cluster pairs (S65), and a new cluster weight, a new mean vector, and a new covariance matrix (m _new ,) according to the following equations (8, 9, 10).

_new , S _{new )} is calculated (S67).

)개의 T² _v 함수값을 구한다. 상기 값들 중 T² _{v 의} 최소값이 c² 보다 크면, 합병될 군집쌍이 없다는 의미이므로, 군집의 개수는 g개가 되고, 군집 합병 알고리즘은 종료 되어, 다음 단계로 진행하게 되며, T² _v 의 최소값이 c2보다 작으면, 해당 군집쌍이 합병되므로 군집의 개수는 (g-1)개가 되며, 계속하여 합병될 군집 쌍이 있는지 검사하게 된다.Here, if the condition is not satisfied in the step (S63), to determine a certain cluster pair at the g th cluster level (

) T ² _v Get the function value. Among these values, _the minimum value of T ² _v is c ² If larger, it means that there are no cluster pairs to be merged, so the number of clusters is g, and the cluster merging algorithm is terminated and proceeds to the next step. If the minimum value of T ² _v is smaller than c2, the cluster pairs are merged. The number of will be (g-1) and will be examined to see if there are any cluster pairs to merge.

When the cluster pairs are merged in the step S65, the number of clusters decreases in proportion to the number of mergers, and is repeated until the minimum value of the T ² _v reaches the ^second c ² , which is the threshold distance value of the selected cluster pairs. S69).

Here, the hierarchical clustering method is used to construct suitable images in a hierarchical tree structure. The hierarchical clustering is made by using initial clusters of all regions of the appropriate images, and g clusters are displayed at the g level in the cluster hierarchy. Corresponding.

, 가중치 공분산 행렬 S를 산출하여, 상기 평균 벡터가 초평면 타원의 위치를 결정한다.In addition, the clustering algorithm bundles the data into hyperplane spheres, and once the initial cluster is created, the mean vector

The weighted covariance matrix S is calculated to determine the position of the hyperplane ellipse.

On the other hand, the weight covariance matrix S represents a shape and a direction. In an iterative feedback process, a user applies a score value v to each image x, and then after each region-based cluster merging 41, each image ( When x) becomes the kth point of the i th cluster (C _i ), v is v _ik Since the relative weight (m _i ) of each cluster (C _{i )} is the sum of the suitability scores of points existing in each cluster is determined by the following equation.

Here, in order to check the proximity of the two clusters, Hotelling T ² of the prior art Statistics [H. Hotelling. Multivariate Quality Control. In C. Eisenhart, MW Hastay, and WA Wallis, eds. Techniques of Statistical Analysis. NY, McGraw-Hill, 1947.], and deduces the merger of two clusters from the proximity of two mean vectors and defines them as:

points in the i th cluster x _i1 , x ₁₂ , ..., x _ini Is a probability sample of size n _i from the population of the mean vector μ _i , the covariance matrix Σ _i . The points (x _{j1 ,} x _j2 , ..., x _jnj ) of the j th cluster are called probability samples of size (n _j ) from the population of the mean vector (μ _j ) and the covariance matrix (Σ _j ). x _i1 , x ₁₂ , ..., x _ini Wow x _{j1 ,} x _j2 , ..., x _jnj Are independent of each other.

), 공분산 행렬(S_i,S_j), 군집의 원소의 개수(n_i,n_j), 군집의 가중치(m_i,m_j)를 각각 가질 때, 호텔링(Hotelling)의 T² 통계량은 다음과 같이 정의된다.Since the covariances of the populations of the two populations are assumed to be similar, the covariances of the samples are used to estimate the common variances. The two clusters that are the target are the mean vectors (

), The covariance matrix (S _i, S _j), the number (n _i, n _j of the cluster elements), when it has a weight (m _i, m _j) of the cluster, respectively, T ² statistic of hoteling (Hotelling) is It is defined as follows.

On the other hand, in a large image database, the visual characteristics of the image are expressed as a high-dimensional vector so that when the dimension of the data is larger than the number of data, T ² Since the singularity problem of covariance used in a function may occur, principal component analysis [F. Jing, M. Li, HJ Zhang, B. Zhang. Relevance feedback in region-based image retrieval. By applying IEEE Transactions on Circuits and Systems for Video Technology, 14 (5), 672-681, May 2004.], a T ² _v function using v principal components is applied to the present invention.

을 갖는다. X=(x₁,...,x_n)' 이며, S는 X의 표본 공분산 행렬일 때, G는 S의 p × p 고유 벡터 행렬, L은 S의 고유값 행렬이 되고, X_i가 R^p인 컬럼벡터이고, g_(i)가 G의 컬럼 벡터일 때 표본 주성분은

과 같이 정의되고, S=GLG' 이다.Here, the principal component transform is given by z = (x−μ) ′ Г when x is a p-dimensional probability vector whose mean (μ), variance (Σ), and Г are the eigenvectors of the variance (Σ). Г is orthogonal and the principal component on the diagonal with Г'ΣГ = Λ

Has X = (x ₁ , ..., x _n ) ', where S is the sample covariance matrix of X, G is the p × p eigenvector matrix of S, L is the eigenvalue matrix of S, and X _i is When the column vector is R ^p and g _(i) is a column vector of G, the sample principal

Is defined as S = GLG '.

가 되며, G는 (n × p)행렬을 같은 차수의 다른 행렬로 변환시키며,

이고, C는 상수이고

와

는 각각

와

대신 사용되고, COV_pooled(x,y)는 x,y의 공통 공분산을 나타내면 가 되고,

Collecting sample principal components

Where G converts the (n × p) matrix to another matrix of the same order,

Where C is a constant

Wow

Are each

Wow

COV _pooled (x, y) is used instead to represent the common covariance of x, y,

Become

The simple form of T ² _p having p main components is as follows.

T ² _p using p principal components is a quadratic form that reduces the amount of computation, and d ² using principal components is also a simple form.

The measurement function of Equation 1 uses the inverse matrix of the sample covariance matrix and the sample covariance matrix, and uses a diagonal matrix instead of the inverse matrix to solve the singularity problem.

When ε≤0.15, the first v≤p principal components are taken, and 1-ε is the ratio of the total variation covered by the first v principal components.

If Gv is a matrix (p × v) where the columns are the first v columns of G,

이고, 일때,

, And,

to be.

In this case, T ² _v of Hotelling using v principal components becomes a simple quadratic form, and after region-based clusters, the clusters can be merged into larger clusters, given a cluster of g clusters. The based cluster merging 41 algorithm searches for candidate pairs of clusters to be merged. The two clusters that are most likely to be merged should be close, and the region based cluster merger (41) algorithm compares the mean vectors to select cluster pairs to be merged repeatedly until the number of inherent clusters is retrieved. The hypothesis for checking the position difference is as follows.

가

와 분리될 때, 큰 값을 가지며 귀무 가설 H_o가 기각된다. H_o가 참이면μ _i is the unknown center of C _i ,

end

When the separation, has a larger value, the null hypothesis H _o is dismissed. If H _o is true

_o

_o

Becomes

는 자유도가 p와 m_i+m_j-p-1인 F-분포의 상위 100(1-α) 퍼센트이다.

Is the top 100 (1-α) percent of the F-distribution with degrees of freedom p and m _i + m _j -p-1.

이면 Ho가 기각된다.therefore,

If Ho is rejected.

은

를 따른다.That is, when two clusters are judged to be different from each other and the proposed cluster-merge function uses the sample covariance and the inverse of the sample covariance, when the data follow the multivariate normal distribution,

silver

Follow.

개의 함수값을 이용한다. 임의의 군집 합병이 발생하지 않으면 군집 개수(g)가 군집 개수 (g-1)보다 최적값에 하며, 반대의 경우, 군집 개수(g-1)는 군집값에 더 근접하게 된다.This statistic is known as the Mahalanobis distance between the centers of two clusters. To begin the process of finding the number of clusters, considering (g-1) the level with clusters and the level with clusters g, we need to determine which level is more optimal. At the g cluster level, to determine which cluster pairs to join

Use function values If no cluster merge occurs, the cluster number g is more optimal than the cluster number g-1 and vice versa, the cluster number g-1 is closer to the cluster value.

_i)_, 공분산 행렬(S_i), 군집의 원소의 개수(n_i), 군집의 가중치(m_i)를 갖고 있을 시, 다음과 같은 통계량을 이용하여 군집i와j를 합쳐 새로운 군집을 만들 수 있다.[R.A. Johnson, D.W. Wichern. Applied Multivariate Statistical Analysis. Prentice-Hall, N.J., 1998.]Here, for efficient cluster merging, instead of the parameters of the points in the existing clusters, the parameters of the aggregated clusters are determined from the parameters of the existing clusters. Clusters mean vector (

_i ) _, covariance matrix (S _i ), the number of elements in the cluster (n _i ), and the weight of the cluster (m _i ), you can create a new cluster by combining clusters i and j using the following statistics: RA Johnson, DW Wichern. Applied Multivariate Statistical Analysis. Prentice-Hall, NJ, 1998.]

4 is a scatter diagram illustrating the process of cluster merging in accordance with the present invention. As shown in the figure, region-based cluster merging 41 is shown for nine clusters.

Here, in order to check the proximity of any cluster pair, when the initial value of the confidence level α is given as 0.01, the search is performed to merge the cluster pair having the minimum of T ² _v for all cluster pairs, and the predetermined confidence If c ² of the same cluster pair is calculated for level α and the T ² _v is less than or equal to c ² , the searched cluster pairs are merged, the number of clusters is reduced, and until the T ² _v is greater than c ² , cyclically To drive the repetition step.

As described above, the number of clusters adjusted in FIG. 2 is 6, and the number of clusters to be merged by adjusting the confidence level α is variable.

The following looks at the experimental example of the present invention.

In order to evaluate the performance of the present invention, a fitness feedback method implemented on a PC with a Pentium using a Windows operating system and using region-based cluster merging (41) for multipoint k-nearest queries in a region-based image database In order to evaluate, the experiment was conducted in the form of answering the following two main questions using the system.

1. How much performance does the method of the present invention improve over query point movement and gradual clustering?

2. How much does the proposed function for estimating the number of potential clusters improve over the performance of the function using principal components?

For the experiments, composite data and Corel image collections were used as test data, the collection contains 10,000 color images, classified by experts, and each category (airplane, flower, mountain, pyramid, sunset, etc.). 100 images are provided per).

In addition, the image segmentation method used in this experiment was normalized cuts (J. Shi and J. Malik. Normalized Cuts and Image Segmentation.IEEE Transactions on Pattern Analysis and Machine Intelligence, 22 (8), 888-905, August 2000.) The image segmentation divides the image into different regions, uses five main regions for each image, and extracts features from individual regions to represent the objects that each region represents.

In order to express the area, the color moment and the size of the area are used as characteristics, and the three color moment values of the mean, standard deviation, and skewness are extracted from each channel of the color space, and using principal component analysis. The dimension of the feature vector is reduced to three dimensions.

That is, as the 3D feature vector is used as the color feature, _v of the T ² _v function is determined to be 3, and the size of the region is normalized by dividing the size by the size of the entire image to determine the importance of the region. Randomly generates three initial queries and evaluates the search performance through an iterative step beginning with the initial query, performs five feedback iterations in addition to the initial query, averages the results of the 100 queries for the 100 initial queries, and compares the similarity search. The k-nearest query is used for this purpose, and k is assumed to be 100.

FIG. 5 is a graph comparing CPU time of a cluster merging process when using a diagonal matrix and an inverse matrix according to the prior art. FIG. As illustrated in the figure, and when using the color moment features (feature), the inverse matrix method using a T ² function in the region-based cluster merge with, T ² _v compare the CPU cost of the diagonal matrix using a function .

Here, the diagonal matrix method using the T ² _v function is shown to have a more time-saving effect than the inverse matrix method in terms of CPU time.

Figure 6 is a comparison graph when using the color moment of the accuracy (precision) and the correct rate (recall) according to the present invention. As shown in the figure, when using the color moment, a graph of the precision according to the recall is shown, one line for each iteration, with each line precision for 100 retrieved images. And 100 points to show the recall.

Here, the search performance is increased in each step, the search performance is increased in the first step, the increase rate decreases after passing the first step, it is shown that the convergence quickly to the user's target.

7 is a graph comparing query results according to an iterative step of a diagonal matrix according to the present invention and a query point movement and a progressive clustering method according to the related art. As shown in the figure, a diagonal matrix method (Adaptive Cluster) using a T ² _v function for each iteration step according to the present invention, a query point movement and an incremental cluster method according to the prior art Compare the recall of.

Here, the same answer rate is shown in the initial query, but the recall rate of the dynamic clustering method for conformance feedback of the region-based image searcher according to the present invention is increased step by step, so that the query point movement and gradual clustering according to the prior art are increased. Better performance than the method.

8 is a diagram showing the results of a query in a sample repetition step according to the present invention, Figure 9 is a diagram showing a result of a query in a sample repetition step 5 according to the present invention. As shown in the figure, the results of the query are shown in the first and fifth iterations of the sample query belonging to the plane category, and the example image is shown in the upper left, and the k-nearest query (11 Of the results of) (k = 100), only the example image and 10 result images are shown.

Then, it can be seen that the fifth from five suitable images in the first airplane category increases to seven in the appropriate images in the airplane category.

Second, detailed experiments were performed using the synthetic data to measure the accuracy of the cluster-merger algorithm.

이고 정규 분포 N(0,1)라 가정하면, z는 평균 0과 공분산 행렬 1을 갖는 다변량 정규 분포를 따르며, z의 데이터 형태는 구형으로 형성되며, y=Az라 가정하면, COV(y)=AA' 이고 y의 데이터 형태는 타원으로 형성된다.here,

And assume a normal distribution N (0,1), z follows a multivariate normal distribution with mean 0 and covariance matrix 1, and the data form of z is spherical, assuming y = Az, COV (y) = AA 'and the data type of y is formed into an ellipse.

에서 합성 데이터가 생성되어 3개의 군집을 구성하고, 상기 합성 데이터로 이루어진 군집간의 거리는 0.5에서 0.25로 변화되며, 주성분 분석을 적용시켜 16차원 합성 데이터에서 12, 9, 6, 3 차원 합성 데이터로 축소시킨다.And,

Synthetic data is generated in the cluster to form three clusters, and the distance between the clusters of the composite data is changed from 0.5 to 0.25, and reduced from 12-dimensional, 9-, 6-, and 3-dimensional composite data by applying principal component analysis. Let's do it.

Next, the error rate of the T ² function using the inverse matrix and the error of the T ² _v function using the diagonal matrix to measure the accuracy of the region-based cluster merging (41) algorithm for 12, 9, 6, 3D composite data. Calculating the ratio, given a cluster of 100 pairs of size 20, a threshold distance value c ² corresponding to 100 T ² _v values is calculated.

Here, quantile-F in Table 1 and Table 2 is a threshold distance value of 95% probability when p is a dimension and n is a population, and when T ² value exceeds the corresponding c ² value, Ho is rejected and the two clusters It is determined to separate the two clusters, and the error rate increases when the two clusters are in close proximity.

Tables 1 and 2 show average values and average error rates (%) of 12, 9, 6, and 3D composite data with respect to T ² using an inverse matrix and T ² _v using a diagonal matrix.

As described above, although described with reference to a preferred embodiment of the present invention, those skilled in the art various modifications of the present invention without departing from the spirit and scope of the invention described in the claims below Or it may be modified.

As described above, the present invention combines region-based image retrieval and conformance feedback to embody a method of expressing an image in the feature space of a color histogram and a color layout representing images at an object level, and provides a high level concept for an example image. By using a region-based clustering process and a region-based cluster merging method to express a semantically appropriate image in the same cluster to have similar visual features, and to output a semantically related cluster, A hierarchical cluster is constructed to semantically segment the divided regions, and the number of potential clusters is determined and merged to express multiple queries using representative points of the final cluster for more accurate image retrieval. the use of hoteling (hotelling) T ² _v By applying a function with a small number of data, the same effect can be obtained with only a diagonal value that reduces the cost of calculating the inverse of the numerical analysis, and solves the high-level singularity problem of the region-based cluster merging. There is an effect such as improving the performance of the search system.

Claims (7)

In area-based image similarity search using relevance feedback, A first step of generating an area-based query point 10 using multiple representative values by inputting an example image; outputting a query result set 20 as a k-nearest query; A third step of constructing an appropriate image set 30 with user feedback 21; Generating a region-based classified set 40 by applying the region-based cluster classification 31; And Comprising a fifth step of calculating the representative value 50 of the cluster using the region-based cluster merge; The output of the query result set by the k-nearest query is output using the Earth Mover Distance (EMD) function which can be applied to the feature representation of the region-based image with variable length as the distance function of the query and the image. and, The region-based query point and region-based clustering are made using a plurality of regions divided for each image, In the fifth process, the number of clusters composed of similar regions is estimated by applying a Hotelling T ² _v using a diagonal matrix, and the neighboring clusters are merged in proportion to the number of region clusters. Dynamic Clustering Method for Relevance Feedback of Based Image Retrieval. delete The method of claim 1, wherein the third process includes in the suitable image set 30 calculated by suitability filtering from the query result set 20 when the example image is included in the query result set 20. And dynamic clustering method for relevance feedback of the region-based image searcher, which is repeatedly driven. 4. The method of claim 3, wherein the fourth process comprises clustering the images of the appropriate image set 30 in a hierarchical clustering method, and applies a region-based cluster classification 31 to the center, covariance, and weight for each cluster. Dynamic clustering method for conformance feedback of the region-based image searcher, characterized in that for calculating the. delete The method of claim 1, wherein the second to fifth processes are repeatedly executed until the query result set 20 reaches an optimal value approaching the significance level set by the user. And repeating execution is terminated when the significance level is reached. The method of claim 1, wherein in order to merge the cluster of region-based cluster merging into a larger cluster, Calculating a T ² _v of Hotelling using a diagonal matrix for all cluster pairs and c ² of the same cluster pair; Selecting a pair of clusters having a minimum value of T ² _v ; A third step of merging the cluster pairs when the T ² _v value of the cluster pair selected in the second step is less than the c ² value of the same cluster pair; And A fourth step of calculating a new cluster weight, an average vector, and a covariance matrix for the cluster pair merged in the third step; Conformance feedback of the region-based image searcher, wherein the feedback is performed by selecting a candidate pair of the cluster until the T ² _v value exceeds the c ² value of the same cluster pair. Dynamic clustering method for the process.

Images