Fast and efficient search method for graphical data

• US 5,159,647 A
• Filed: 03/04/1991
• Issued: 10/27/1992
• Est. Priority Date: 03/04/1991
• Status: Expired due to Term

• Current Assignee: Sarnoff Corporation (SRI International, Inc.)
• Original Assignee: David Sarnoff Research Center, Inc.
• Inventors: Burt, Peter J.
• Primary Examiner(s): Mancuso, Joseph
• Application Number:
  US07/663,513
• Time in Patent Office: 603 Days
• Field of Search: 382/37, 382/48, 382/56, 382/14, 382/2, 382/36, 382/30, 382/38, 358/209, 364/513, 395/1, 395/21, 395/51, 395/80
• US Class Current: 382/103
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

By processing the highest-resolution graphical data (e.g., image data) pertaining to relevant-objects defined by the graphical data into abstracted multiple-attribute information that is stored in a group of nodes of the lowest level of a hierarchy of data arrays (e.g., the leaf nodes of a complete data tree file), the present invention processes the data of each of these hierarchy of data arrays backward toward a single node of the highest level of the hierarchy of data arrays (e.g., the root node of a complete data tree file), to derive an attribute vector of all the abstracted multiple-attribute information at this single node. The derived attribute vector is then used to guide a search down the hierarchy of data arrays from the single node of its highest level toward at least a selected one of the group of nodes of its lowest level (which, by way of example, may correspond to the location of a likely relevant object). In this manner, a search made over a relatively large spatial domain for a relatively small relevant object can be converted into a search for the relevant object as described in the attribute domain of the hierarchy of data arrays, where such means as direct indexing may be used.

Claims

1. In a guided search method employing low-to-high resolution techniques for locating any of one or more various types of relevant objects that may be represented in relatively high-resolution graphical data that occupies a given data domain H_n, where n≧

1;

wherein each type of relevant objects exhibits a different combination of one or more of multiple predetermined attributes;

the improvement comprising the step of employing high-to-low resolution techniques to prepare a search guide comprising a hierarchy of data arrays;

wherein;

a certain level of said hierarchy of data arrays comprises respective nodes that individually correspond to each of a plurality of data domains H_k-1 into which said given data domain H_n has been divided, each data domain H_k-1 being smaller than a data domain H_k, where 1≦

k≦

n and 0≦

(k-1)<

n;

another one of said data-tree node levels comprises at least one node that individually corresponds to a data domain H_k which is comprised a group of H_k-1 data domains;

a first attribute vector is stored in the node corresponding to each H_k-1 data domain, which first attribute vector abstracts all attribute information defined by the graphical data contained in that H_k-1 data domain; and

a second attribute vector, which pools the multiple attribute information stored by said first attribute vectors in all those nodes corresponding to the group of H_k-1 data domains that comprise each H_k data domain, stores information abstracted from that group of H_k-1 data domains in the node corresponding to that H_k data domain;

whereby a low-to-high resolution guided search may be made by employing the pooled abstracted multiple attribute information stored by the second attribute vector in a node corresponding to an H_k data domain to select the attribute information stored by the first attribute vector of at least one of the nodes corresponding to the H_k-1 data domains of the group that comprises that H_k data domain.

2. The method defined in claim 1, wherein said graphical data is comprised of an array of individual high-resolution data elements, the data domain of each of said individual data elements being H₀ ;

and wherein the step of employing high-to-low resolution techniques to prepare a search guide includes the steps of;

a) dividing said given domain H_n into a plurality of said data domains H_k-1 ;

b) separately processing the data of each of said plurality of data domains H_k-1 to abstract information as to whether any and, if so, which of said predetermined attributes of said relevant objects are defined thereby, and then storing the abstracted information as a first attribute vector in that H_k-1 node of the H_k-1 level of said hierarchy of data arrays that corresponds to that H_k-1 data domain; and

(c) pooling the multiple attribute information stored by the first attribute vectors in those nodes corresponding to the individual H_k-1 data-domain group that comprises that H_k data domain, and storing information abstracted from that group of H_k-1 data domains in the node corresponding to that H_k data domain.

3. The method defined in claim 2, wherein k has an initial value equal to one, whereby (k-1) has an initial value equal to zero, wherein n has a given value greater than one;

and wherein said method further comprises the step of;

(d) cyclically repeating steps (a), (b) and (c), with the value of k during each repeated cycle being one higher than the value of k during the immediately preceding cycle, until the value of k on the last cycle is equal to n;

whereby the highest level of said hierarchy of data arrays comprises a single node corresponding to said given data domain H_n and the lowest level of said hierarchy of data arrays comprises of a group of nodes that individually correspond to each of a plurality of said data domains H₀, and a guided search may be made starting with the pooled abstracted multiple attribute information defined by the second attribute vector stored in said single node of said highest level of said hierarchy of data arrays and proceeding therefrom toward the respective abstracted information defined by the first attribute vector stored in any selected one of said group of nodes of the lowest level of said hierarchy of data arrays in accordance with the pooled abstracted information defined by the second attribute vector stored in each node of said hierarchy of data arrays antecedent to that selected one of said group of nodes.

4. The method defined in claim 3, wherein:

said hierarchy of data arrays is a complete data-tree file which includes a plurality of node levels in which the root node of said data-tree file corresponds to said node of said highest level of said hierarchy of data arrays and said leaf nodes of said data-tree file corresponds to said group of nodes of said lowest level of said hierarchy of data arrays.

5. The method defined in claim 1, wherein:

said other one of said levels of the hierarchy of data arrays comprises at least one node that individually corresponds to a data domain H_k which comprises a group of adjacent H_k-1 data domains.

6. The method defined in claim 1, wherein:

said graphical data is comprised of two-dimensional image data.

7. The method defined in claim 6, wherein:

said other one of said levels of the hierarchy of data arrays comprises at least one node that individually corresponds to an image-data domain H_k which comprises a group of adjacent H_k-1 image-data domains

8. The method defined in claim 7, wherein:

said other one of levels of the hierarchy of data arrays comprises at least one node that individually corresponds to an image-data domain H_k which is comprised of a 2×

2 group of adjacent H_k-1 image-data domains.

9. The method defined in claim 1, wherein:

each of said multiple attributes is of a different given type and exhibits a certain value.

10. The method defined in claim 1, wherein:

said first attribute vector stored in the node corresponding to each one of the H_k-1 data domains of the H_k-1 level of the hierarchy of data arrays lists the abstracted attribute information of which comprises it arranged in the same predefined order as said first attribute vector stored in the node corresponding to each other of the H_k-1 data domains of the H_k-1 level of the data-tree file lists the abstracted attribute information which comprises it.

11. The method defined in claim 10, wherein:

said second attribute vector stored in the node corresponding to each one of the H_k data domains of the H_k level of the hierarchy of data arrays lists the abstracted attribute information which comprises it arranged in the same second predefined order as said second attribute vector stored in the node corresponding to each other of the H_k-1 data domains of the H_k-1 level of the data-tree file lists the abstracted attribute information which comprises it.

12. The method defined in claim 11, wherein:

said second predefined order is different from said first-mentioned predefined order.