Title of Invention

"A DEVICE FOR ADAPTIVELY SEARCHING A FEATURE VECTOR SPACE"

Abstract

The present invention provides a device for adaptively searching a feature vector space comprising (a) a similarity measurement means (101) for performing a similarity measurement on a given query vector within the feature vector space; and (b) a search applying conditions means (102) for applying search conditions limited by the result of the similar measurement obtained from a first means and performing a changed similarity measurement on the given query vector, characterized in that the search applying conditions means comprises: a) a approximation level filter (103) for obtaining candidate approximation regions by performing a approximation level filtering according to a distance measurement limited by the result of the similar measurement obtained from the first means; and b) a data level filter (104) for performing data level filtering on the candidate approximation obtained from the third means.

Full Text

Field of the Invention: The present invention relates to a device for adaptively searching a feature vector space for a feature vector which has similar features to a query vector, and more particularly, to a device for efficiently searching a vector space indexed based on an approximation for a feature vector having features similar to a query vector according to a varying distance measurement. 2. Description of the Related Art In a multimedia database related to a multimedia application multimedia contents are typically represented by feature vectors. Similarity of objects is determined by a distance measurement defined by feature distances between the query vector and feature vectors in a feature vector space. To provide further precise retrievals, a distance measurement may be iteratively performed using collected information such as user feedback. However, a conventional search method does not consider how to iteratively perform a distance measurement according to varying factors in a large database. In particular, a conventional indexing method in a feature vector space has not addressed how to quickly perform a search in an environment that a distance measurement is changing, such as on-line retrieval. Thus, there still remains a need for accelerating a search in an environment that a distance measurement is varying. SUMMARY OF THE INVENTION To solve the above problems, it is an objective of the present invention to provide a method for quickly and iteratively searching an approximated feature vector space for a feature vector having features similar to a query vector according to varying measure conditions. Accordingly, to achieve the above objective, the present invention provides a method for adaptively searching a feature vector space which includes the steps of (a) performing a similarity measurement on a given query vector within the feature vector space, and (b) applying search conditions limited by the result of the similar measurement obtained in the step (a) and performing a changed similarity measurement on the given query vector. Preferably, the step (b) includes the steps of (b-1) obtaining candidate approximation regions by performing.approximation level filtering according to a distance measurement limited by the result of the similar measurement obtained in the step (a), and (b-2) performing data level filtering on the obtained candidate approximation regions. Preferably, the step (a) includes the steps of (a-1) obtaining a predetermined number of nearest candidate approximation regions by measuring the distances between the query vector and approximation regions, and (a-2) obtaining K nearest neighbor feature vectors by measuring the distance between each of all feature vectors in the obtained candidate approximation regions and the query vector, where K is a positive integer. Preferably, the step (b-1) includes the steps of (b-1-1) calculating K'-th shortest distance for the K nearest neighbor feature vectors obtained according to the previous distance measurement according to the changed distance measurement where K' is a positive integer, and setting the calculated distance as rtu+1 and (b-1-2) calculating K'-th smallest lower bound for the predetermined number of candidate approximation regions obtained according to the previous distance measurement according to the changed distance measurement and set as Preferably, the step (b-1) includes the steps of (b-1-3a) measuring the distance L;(Wt+1) between the lower bound of an approximation region and a query vector for a new distance measurement, wherein N is a positive integer denoting the number of objects in the feature vector space and i is a variable ranging from 1 to N, (b-1-4) comparing the distance Li(Wt+1) obtained in the step (b-1-3a) with a minimum value min (Φ,rtu+1, Φtu+1) of K-th smallest upper bound Φ, rtu+1 and Φtu+1 (b-1 -5) if the distance L|(Wt+1) is less than or equal to the minimum value min (Φ,rtu+1, Φtu+1) setting the corresponding approximation region as a candidate approximation region, and (b-1-6) if the distance Li(Wt+i) is greater than the minimum value min (Φru+1,Φtu+1), excluding the corresponding approximation region. Furthermore, the step (b-1) further includes (b-l-3b) measuring the distance Ui(Wl+1) between the upper bound of the approximation region and the query vector for the new distance measurement, assuming that N is a positive integer denoting the number of objects in the feature vector space and i is a variable from 1 to N, and (b-1-7) updating the K-th smallest upper bound Φ referring to the distance U1(Wt+1) Furthermore, the steps (b-1-1) to (b-1-6) are repeated until the approximation level filtering is performed on all N approximation regions where N is a positive integer denoting the number of objects in a database. Preferably, the step (b-2) includes the -steps of (b-2-1) performing a distance measurement between each of all feature vectors in the candidate approximation regions and the query vector, and (b-2-2) determining K'nearest neighbor vectors as retrieved vectors depending on the result of the distance measurements performed in steps (b-2-1). The present invention further provides a device for adaptively searching a feature vector space, said device comprising a first means for performing a similarity measurement on a given query vector within the feature vector space and a second means for applying search conditions limited by the result of the similar measurement obtained from the first means and performing a changed similarity measurement on the given query vector In an embodiment of the present invention, the second means further comprises of a third means for obtaining candidate approximation regions by performing a approximation level filtering according to a distance measurement limited by the result of the similar measurement obtained from the first means and a fourth means for performing data level filtering on the candidate approximation obtained from the third means. In another embodiment of the present invention, the first means further comprises of a fifth means for obtaining a predetermined number of nearest candidate approximation regions by measuring the distance between the query vector and each approximation region and a sixth means for obtaining K nearest neighbor feature vectors by measuring the distances between all feature vectors in the obtained candidate approximation regions and the query vector, where K is a positive integer. In still another embodiment of the present invention, the third means further comprises of a seventh means for calculating K'-th shortest distance for the K nearest neighbor feature vectors obtained according to the previous distance measurement according to the changed distance measurement where K' is a positive integer, and setting the calculated distance as rut+1 and an eight means for calculating K'-th smallest lower bound for the predetermined number of candidate approximation regions obtained according to the previous distance measurement according to the changed distance measurement and set In yet another embodiment of the present invention, the third means further comprises of a ninth means for measuring the distance Li(Wt+1) between the lower bound of an approximation region and a query vector for a new distance measurement, wherein N is a positive integer denoting the number of objects in the feature vector space and i is a variable ranging from 1 to N, a tenth means for comparing the distance L1(Wt+1) obtained from the ninth mean with a minimum value min(Φru+1,Φtu+1) of K-th smallest upper bound Φru+1 and Φtu+1, an eleventh means for comparing the distance Li(Wt+i) with the minimum value min(Φru+1,Φtu+1) and setting the corresponding approximation region as a candidate approximation region if the distance Li(Wt^) is lesser than or equal to the minimum value min(Φru+1,Φtu+1) and a twelfth means for comparing the distance L1(Wt+1) with the minimum value min(Φru+1,Φtu+1) and excluding the corresponding approximation region. In one more embodiment of the present invention, the third means further comprises of a thirteenth means for measuring distance U1(Wt+1) between the upper bound of the approximation region and the query vector for the new distance measurement, assuming that N is a positive integer denoting the number of objects in the feature vector space and i is a variable ranging from 1 to N and a fourteenth means for updating the K-th smallest upper bound preferring to the distance U1(Wt+1). In a further embodiment of the present invention, the fourth means further comprises of a fifteenth means for performing a distance measurement between each of all feature vectors in the candidate approximation regions and the query vector and a sixteenth means for determining K' nearest neighbor vectors as retrieved vectors depending on the result of the distance measurements performed by the fifteenth means. BRIEF DESCRIPTION OF THE DRAWINGS The above objective and advantages of the present invention will become more apparent by describing in detail preferred embodiments thereof with reference to the attached drawings in which: Figs. 1A and 1B: Flowcharts showing main steps of a method for adaptively searching a feature vector space according to an embodiment of the present invention; and Fig 2: Pseudo code list for explaining approximation level filtering. Fig. 3: Block diagram showing the construction of the device of the present invention. DETAILED DESCRIPTION OF THE INVENTION The main steps of an adaptive search method according to an embodiment of the present invention will now be described with reference to Figures 1A and 1B. A database in which multimedia contents are stored is represented as a feature vector space. In this embodiment, the feature vector space is approximated with a plurality of hypercubes. Furthermore, assuming that M is a positive integer denoting the dimensionality of feature vectors used to describe an image/video object, and N is a positive integer denoting the number of objects in the database, feature vector F and feature vector Q of a query object Q are defined as F = [Fi1, Fi2,..., FiM ] and Q = [qil,qi2,...,qim] respectively. Here, the database is represented as a feature vector space and the feature vector Q of a query object Q is hereinafter called a query vector. First, a predetermined number of nearest candidate hypercubes are obtained by measuring the distance between a query vector and each of hypercubes (step 102). Then, K of nearest neighbor feature vectors are abort indicator by measuring the distance between the query vector and each of all feature vectors in the predetermined number of candidate hypercubes obtained in the step 102, where K is a positive integer (step 104). The distance between the query vector and each of the feature vectors is measured by calculating weighted Euclidean distance. The weighted Euclidean distance is calculated by Equation (1): d(Wt,Ft,Q)=(Q-F)TWt(Q-F) -d) where W, is a full symmetric function matrix at iteration t and updated at every iteration. Then, for example, the user selects a plurality of multimedia contents similar to those that he or she desires to find among calculated multimedia contents and attempts a search again. Thus, feedback for changed search conditions can be provided from the user, which is called relevance feedback. According to the present invention, features for which feedback is provided from the user are reflected in a distance measurement for the next search, thereby changing distance measurement conditions. According to the present invention, approximation level filtering is performed using information from previous iteration t. Wt,C,(Wt), and Rtdenote a distance measurement function used in the previous iteration t, approximation regions that passed the previous iteration t or hypercubes in this embodiment, and vectors retrieved using Wt, respectively. FIG. 2 shows a pseudo code list for explaining the step of approximation level filtering. The approximation level filtering is performed using the information from the previous iteration t. Referring to FIG. 2, according to the pseudo codes, during the approximation level filtering, K'-th shortest distance is calculated for the K nearest neighbor feature vectors obtained according to the previous distance measurement according to the changed distance measurement where K' is a positive integer, and the calculated distance is set as rtuj (step 106). Furthermore, K'-th smallest lower bound is calculated for the predetermined number of candidate hypercubes obtained according to the previous distance measurement according to the changed distance measurement and set as Φtu+1 (step 108). Then, assuming that N is the number of objects or approximation regions in the approximated feature vector space or a positive integer denoting the number of hypercubes in this embodiment and i is a variable ranging from 1 to N, the distance L|(Wt+1) between each of the lower bounds of hypercubes in the feature vector space and a query vector and the distance Uj(Wt+1) between each of the upper bounds of the hypercubes in the feature vector space and the query vector are measured according to the changed new distance measurement (step 110). Furthermore, the K'-th smallest upper bound (j) is calculated (step 112). Next, the distance Li(W,+1) between the lower bound of i-th hypercube in the corresponding vector space and the query vector is compared with a minimum value min (Φru+1,Φtu+1) of the K'-th smallest upper bound Φ calculated in the step 112, rtu+1 and 0},"j (step 114). If the distance L|(Wt+1) is less than or equal to the minimum value min(Φru+1,tΦtu+1), a relevant hypercube is set as a candidate hypercube (step 116) and if not, the relevant hypercube is excluded (step 118). Referring to pseudo code 202 in FIG. 2, it is determined whether or not the distance Li(Wt+1) between the lower bound of i-th hypercube in the corresponding vector space and the query vector is smaller than all of the K'-th smallest upper bound Φ,rtu+1 and Φtu+1 and relevant hypercube Pi is selected as a candidate hypercube as shown pseudo code 204. Referring to pseudo code 206, if requirements shown in the pseudo code 202 are satisfied, the relevant hypercube Pi is selected as a candidate hypercube, and the upper bound $ is updated referring to the distance Uj(Wt+1) (step 120). Next, assuming that N is a positive integer denoting the number of objects in the database or hypercubes, it is determined whether i reaches N (step 124), and if i does not reach N, the steps 114 -124 are repeated until the approximation level filtering is performed on all N hypercubes. According to the method described above, for a hypercube to be set as a candidate hypercube, the hypercube must meet new requirements determined from the previous distance measurement information such as the pseudo code 202. Thus, requirements for selecting candidate hypercubes are further limited, thereby reducing the number of selected candidate hypercubes. Then, data level filtering is performed. During the filtering, a distance measurement between each of all feature vectors in the candidate hypercubes and the query vector is performed (step 126) to determine K' nearest neighbor vectors as found feature vectors depending on the result of the distance measurements performed in the step 126 thereby completing a search (step 128). In this case, the number of candidate hypercubes is reduced, which reduces the computational complexity in measuring the distance between each of all feature vectors in the candidate cubes and the query vector. Thus, a search speed can be improved when searching for a feature vector having features similar to a query vector. That is, according to the search method as described, the number of candidate approximation regions in a varying distance measurement is reduced thereby improving the search speed, and if new approximation regions are included, database can be updated fast. Although the preferred embodiments of this invention has been described with reference to the example that the feature vector space is partitioned into hypercubes and approximated, the invention is also applicable to feature vector spaces indexed by other known index structures such as R-tree, R tree, SR-tree and X-tree. It will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims. The search method according to the present invention can be written as a program executed on a personal or server computer. The program codes and code segments constructing the program can be easily inferred by computer programmers in the industry. Furthermore, the program can be stored in a computer-readable recording medium. The recording medium includes a magnetic recording medium, an optical recording medium, and a radio medium. According to the present invention, the number of approximation regions is reduced during a varying distance measurement, which improves a search speed. With reference to figure 3, the device for adaptively searching a feature vector space is described hereafter. The device for adaptively searching a feature vector space comprises: a) a similarity measurement means (101) for performing a similarity measurement on a given query vector within the feature vector space; and b) a search applying conditions means (102) for applying search conditions limited by the result of the similar measurement obtained from a first means and performing a changed similarity measurement on the given query vector, characterized in that the search applying conditions means comprises: a) a approximation level filter (103) for obtaining candidate approximation regions by performing a approximation level filtering according to a distance measurement limited by the result of the similar measurement obtained from the first means; and b) a data level filter (104) for performing data level filtering on the candidate approximation obtained from the third means. The similarity measurement means (101) comprises a first distance measuring means (105) for obtaining a predetermined number of nearest candidate approximation regions by measuring the distance between the query vector and each approximation region; and a second distance measuring means (106) for obtaining K nearest neighbour feature vectors by measuring the distances between all feature vectors in the obtained candidate approximation regions and the query vector, where K is a positive integer. The approximation level filter (103) comprises a distance calculating means (107) for calculating K'-th shortest distance for the K nearest neighbor feature vectors obtained according to the previous distance measurement according to the changed distance measurement where K' is a positive integer, and setting the calculated distance as rut+1; and a bound calculating means (108) for calculating K'-th smallest lower bound for the predetermined number of candidate approximation regions obtained according to the previous distance measurement according to the changed distance measurement and set U as t+1 The approximation level filter (103) comprises a third distance measuring means (109) for measuring the distance Li(Wt+1) between the lower bound of an approximation region and a query vector for a new distance measurement, wherein N is a positive integer denoting the number of objects in the feature vector space and i is a variable ranging from 1 to N; a first comparator (110) for comparing the distance Li(Wt+1) obtained from the ninth means with a minimum value min(Φru+1, ut+i) of K-th smallest upper bound Φ, rtu+1 and tu+1; a second comparator (111) for comparing the distance Li(Wt+1) with the minimum value min(Φ , rut+1, ut+1) and setting the corresponding approximation region as a candidate approximation region if the distance Li(Wt+1) is lesser than or equal to the minimum value min(Φru+1, tu+1); and a third comparator (112) for comparing the distance L1(Wt+1) with the minimum value min(Φru+1 ,tu+1), and excluding the corresponding approximation region. The approximation level filter (103) comprises a fourth distance measuring means (113) for measuring distance U1(Wt+1) between the upper bound of the approximation region and the query vector for the new distance measurement, assuming that N is a positive integer denoting the number of objects in the feature vector space and i is a variable ranging from 1 to N; and an updating means (114) for updating the K-th smallest upper bound Φ referring to the distance U1(Wt+1). We Claim: 1. A device for adaptively searching a feature vector space, said device comprising: a) a similarity measurement means (101) for performing a similarity measurement on a given query vector within the feature vector space; and b) a search applying conditions means (102) for applying search conditions limited by the result of the similar measurement obtained from a first means and performing a changed similarity measurement on the given query vector, characterized in that the search applying conditions means comprises of: a) a approximation level filter (103) for obtaining candidate approximation regions by performing a approximation level filtering according to a distance measurement limited by the result of the similar measurement obtained from the first means; and b) a data level filter (104) for performing data level filtering on the candidate approximation obtained from the third means. 2. A device as claimed in claim 1, wherein the similarity measurement means (101) comprises of: a) a first distance measuring means (105) for obtaining a predetermined number of nearest candidate approximation regions by measuring the distance between the query vector and each approximation region; and b) a second distance measuring means (106) for obtaining K nearest neighbour feature vectors by measuring the distances between all feature vectors in the obtained candidate approximation regions and the query vector, where K is a positive integer. 3. A device as claimed in claim 1, wherein the approximation level filter (103) comprises of: a) a distance calculating means (107) for calculating K'-th shortest distance for the K nearest neighbor feature vectors obtained according to the previous distance measurement according to the changed distance measurement where K' is a positive integer, and setting the calculated distance as rut+i; and b) a bound calculating means (108) for calculating K'-th smallest lower bound for the predetermined number of candidate approximation regions obtained according to the previous distance measurement according to the changed distance measurement and set as Vi.- 4. A device as claimed in claim 3, wherein the approximation level filter (103) comprises of: a) a third distance measuring means (109) for measuring the distance Li(Wt+,) between the lower bound of an approximation region and a query vector for a new distance measurement, wherein N is a positive integer denoting the number of objects in the feature vector space and i is a variable ranging from 1 to N; b) a first comparator (110) for comparing the distance Li(Wt+i) obtained from the ninth means with a minimum value min(O, rut+i, Vi) of K-th smallest upper bound O, rut+i and 0 Vi! c) a second comparator (111) for comparing the distance Li(Wt+1) with the minimum value min(O , ru,+i, Vi) and setting the corresponding approximation region as a candidate approximation region if the distance Li(W,+i) is lesser than or equal to the minimum value min(O, rut+i> Vi)» and d) a third comparator (112) for comparing the distance Li(Wt+i) with the minimum value min(O, rut+i, Vi), and excluding the corresponding approximation region. 5. A device as claimed in claim 3, wherein the approximation level filter (103) comprises of: a) a fourth distance measuring means (113) for measuring distance Ui(Wt+i) between the upper bound of the approximation region and the query vector for the new distance measurement, assuming that N is a positive integer denoting the number of objects in the feature vector space and i is a variable ranging from 1 to N; and b) an updating means (114) for updating the K-th smallest upper bound O referring to the distance Ui(Wt+i). 6. A device as claimed in claim 1, wherein the fourth means (113) comprises of: a) a fifth distance measuring means (115) for performing a distance measurement between each of all feature vectors in the candidate approximation regions and the query vector; and b) a determination means (116) for determining K' nearest neighbor vectors as retrieved vectors depending on the result of the distance measurements performed by the fifteenth means. 7. A device for adaptively searching a feature vector space substantially as herein described with reference to the accompanying drawings.

Documents:

126-del-2001-abstract.pdf

126-del-2001-claims.pdf

126-del-2001-correspondence-others.pdf

126-del-2001-correspondence-po.pdf

126-del-2001-description (complete).pdf

126-del-2001-drawings.pdf

126-del-2001-form-1.pdf

126-del-2001-form-13.pdf

126-del-2001-form-19.pdf

126-del-2001-form-2.pdf

126-del-2001-form-26.pdf

126-del-2001-form-3.pdf

126-del-2001-form-5.pdf

126-del-2001-petition-137.pdf

abstract.jpg