Method for indexing feature vector data space

• US 20020040367A1
• Filed: 02/15/2001
• Published: 04/04/2002
• Est. Priority Date: 08/21/2000
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd., Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Wu, Peng, Choi, Yang-lim, Manjunath, B. S.
• Granted Patent: US 6,917,927 B2
• Time in Patent Office: Days
• US Class Current: 707/104.1
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951

Abstract

A method is provided for indexing feature vectors within feature vector data space which includes adaptively forming approximation of the feature vectors on the basis of statistical distribution of feature vector data within the feature vector data space. The method for indexing feature vector data space of the present invention efficiently indexes vector space having high-dimensionality in which generally feature vectors are not uniformly distributed. Also, the method for indexing feature vector data space has an advantage that indexing can be easily upgraded when new feature vector data is added.

Claims

1. A method for indexing feature vector data space comprising the step of:

(a) adaptively approximating feature vectors on the basis of statistical distribution of feature vector data in the feature vector data space.

2. The method of claim 1, wherein the step (a) further comprises the steps of:

(a-1) measuring the statistical distribution of the feature vector data in the feature vector data space;

(a-2) estimating marginal distribution of the feature vector data using the statistical distribution;

(a-3) dividing the estimated marginal distribution into a plurality of grids in which a probability of disposing the feature vector data in each grid is uniform; and

(a-4) indexing the feature vector data space using the divided grids.

3. The method of claim 2, further comprising prior to step (a-4), the step of updating the grids on the basis of a previous probability distribution function and an updated probability distribution function, when new data is received.

4. The method of claim 2, wherein step (a-4) further comprises indexing using vector approximation (VA) files.

5. The method of claim 2, wherein a number of the plurality of grids is determined by a number of bits assigned to the dimension.

6. The method of claim 2, wherein step (a-2) further comprises the steps of:

(a-2-1) defining a probability distribution function using a weighted sum of a predetermined distribution function; and

(a-2-2) obtaining an estimated probability distribution function by estimating predetermined parameters using the probability distribution function defined in the step (a-2-1).

7. The method of claim 6, wherein step (a-2-2) further comprises obtaining the estimated probability distribution function by estimating the predetermined parameters using all N predetermined data in each estimation, wherein N is a positive integer, on the basis of an expectation-maximization algorithm using the probability distribution function defined in the step (a-2-1).

8. The method of claim 6, wherein the predetermined distribution function is the Gaussian function.

9. The method of claim 6, wherein the probability distribution function of step (a-2-1) is a one-dimensional signal, p(x), wherein

10. The method of claim 6, wherein the estimated probability distribution function of step (a-2-2) is obtained by finding Φ

j, j=1, . . . , M, which maximizes

11. The method of claim 10, wherein the estimated parameters of step (a-2-2) are updated according to the following equations

12. The method of claim 11, wherein the estimated parameter set of step (a-2-2) using N data v[I] is given as {P(j)^Nμ

_j^N, (σ

_j²)^N}, and the updated parameter set for new data v[N+1], coming in, is calculating using the following equations;

13. The method of claim 11, wherein the step (a-2-2) further comprises:

measuring a change of a probability distribution function which is defined as

$\frac{\mathrm{\rho <br><br>}=\int <br><br>{\left({\hat{p}}_{\mathrm{old}}<br><br>\left(x\right)-{\hat{p}}_{\mathrm{new}}<br><br>\left(x\right)\right)}^2<br><br><br><br>x}{\int <br><br>{{\hat{p}}_{\mathrm{old}}<br><br>\left(x\right)}^2<br><br><br><br>x}$

for each dimension, wherein a previous probability distribution function is {circumflex over (P)}_old(x), and an updated probability distribution function is {circumflex over (P)}_new(x); and

updating an approximation for the dimension if ρ

is larger than a predetermined threshold value.

14. The method of claim 2, wherein step (a-3) further comprises dividing a probability distribution function into the plurality of grids to make areas covered by each grid equal, wherein the plurality of grids have boundary points defined by c[I], I=0, . . . , 2^b, where b is a number of bits allocated and wherein the boundary points satisfy a criterion,