Insertion method in a high-dimensional index structure for content-based image retrieval

• US 6,389,424 B1
• Filed: 10/28/1999
• Issued: 05/14/2002
• Est. Priority Date: 10/28/1998
• Status: Expired due to Fees

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Lee, Jin Soo, Kim, June, Yoo, Jae Soo, Lee, Seok Hee, Hur, Dae Young
• Primary Examiner(s): Shah, Sanjiv
• Application Number:
  US09/429,300
• Time in Patent Office: 929 Days
• Field of Search: 707/100, 707/1, 707/2, 707/6, 707/7, 707/101, 707/102, 707/104, 707/3, 707/5, 345/589, 382/225, 382/226, 382/227
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An insertion method in a high-dimensional index structure for a content-based image retrieval is disclosed, in which a desired image can be efficiently searched when there is formed a high-dimensional image database. In the present invention, the basic properties of the CIR tree are utilized, and at the same time, a splitting algorithm having a superior search efficiency over the conventional CIR tree is employed. Further, an effective standard for choosing lower nodes is provided, and a re-insertion algorithm capable of re-inserting based on a weighted center is employed, thereby forming an ECIR (Extended CIR) as a high-dimensional index structure supporting efficient retrieval performance. That is, a splitting algorithm for the branch nodes and the terminal nodes are adopted so as to improve the efficiency when carrying out the search and insertion. The re-insertion objects are chose based on the weighted center when the nodes overflow. According to the present invention, the images can be efficiently searched when an image information containing many feature dimensions is formed into a database.

Claims

1. A method for inserting a high-dimensional index structure for a content-based image retrieval, comprising the steps of:

(a) inserting an object into a root node if a tree consists of only a root node;

(b) forming a new root node when an existing root node overflows;

(c) after inserting an object if the child nodes of the root node are branch nodes, choosing the branch node with the following sequences,

     1) the MBR that has minimum number of new pairs of overlapping MBR within the root node,

     2) the MBR that uses more dimensions for discrimination,

     3) the MBR whose center is close to a new object, and

     4) the MBR showing less increase in a size of a minimum bounding region;

(d) choosing objects based on weighted center to re-insert them into the branch node if the branch node overflows;

(e) splitting the branch node if the branch node overflows, and otherwise, adjusting the minimum bounding region (MBR);

(f) choosing a lower node as a terminal node to insert an object if a child node of the root node is a branch node;

(g) choosing objects based on a weighted center to re-insert them into the terminal node if the terminal node with an object inserted into it overflows; and

(h) splitting the terminal node, and then, carrying out the steps c to g to insert a new object into the branch node if the terminal node overflows after a re-insertion.

2. The method as claimed in claim 1, wherein a weighted center of the terminal node is obtained by dividing the result value obtained by adding object values of same dimensions by the number of entries.

3. The method as claimed in claim 1, wherein a weight center of said branch node is obtained by dividing center values of said minimum bounding regions by a number of entries.

4. The method as claimed in claim 1, wherein re-insertion objects are chosen starting from those most remotely positioned from the weighted center.

5. The method as claimed in claim 1, wherein a splitting of the branch nodes comprises the steps of:

choosing a dimension having the widest range and divisible without generating overlaps;

choosing a dimension having the widest non-overlapping range and satisfying a minimum existable number of objects during a division if there is no divisible dimension with overlap-free regions;

choosing a split having minimum overlapping regions from among many splits lying between a minimum filling and a maximum filling of objects after sorting them based on a weighted center for a chose dimension;

comparing the chose split with a reference value to extend it to a super node if the chose split is higher than the reference value; and

making chooses in a sequence of a split having small overlap regions, a split having a minimum area, a split having a small margin length, and a split divisible into same numbers, if the chose split is lower than the reference value.

6. The method as claimed in claim 1, wherein a split of the terminal nodes comprises the steps of:

choosing a dimension having the widest range and divisible without generating overlaps;

choosing a split having a minimum area from among many splits lying between minfill and maxfill of the node during splitting of number of entries in one of divided two nodes after sorting them for the chose dimension; and

making chooses in a sequence of a split having a minimum area, a split having a small margin length, and a split divisible into same numbers of entries.

7. A recording medium comprising:

a means for judging on constituent elements of a tree;

a means for inserting an object into a root node if the tree consists of a root node, and forming a new root node if the existing root node overflows;

a means for inserting an object if child nodes of the root node are branch nodes, and choosing the branch nodes in a sequence of one having less overlaps with near by nodes, one having same values in many dimensions, one showing less increase in a minimum bounding region size, and one disposed more adjacently to a center;

a means for adding a mean value of a minimum bounding region if the branch node overflows, obtaining a weighted center by dividing the result value obtained by adding the center values of MBRs by the number of entries, and choosing re-insertion objects in a sequence of remote positioning from the weighted center to re-insert them into the branch nodes;

a means for splitting the branch node if the branch node overflows with the objects, and otherwise, adjusting the minimum bounding region;

a means for choosing a terminal node if a child node of the root node is a terminal node or if a child node of the branch node is a terminal node, then inserting an object into the terminal node, then adding an object value of a same dimension, then obtaining a weighted center by dividing the result value obtained by adding object values of the same dimensions by the number of entries, and then choosing a re-insertion objects to re-insert it into said terminal node; and

a means for splitting the terminal node if the terminal node overflows, and inserting a new object into the branch node, whereby a program for activating the above means is read by a computer.