Method and apparatus for high speed object location

• US 5,101,444 A
• Filed: 05/18/1990
• Issued: 03/31/1992
• Est. Priority Date: 05/18/1990
• Status: Expired due to Term

• Current Assignee: Labtec, Inc. (Logitech International SA)
• Original Assignee: Panacea, Inc. (Honyaku Center Inc.)
• Inventors: Wilson, David H., Richter, Jake
• Primary Examiner(s): Razavi, Michael
• Application Number:
  US07/525,966
• Time in Patent Office: 683 Days
• Field of Search: 382/48, 382/9, 382/18, 382/10, 382/25, 382/27, 382/57, 358/401, 358/262.1, 358/426
• US Class Current: 382/174
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image

Abstract

A method and apparatus for rapidly locating a desired object in a bit-mapped or vector display listed object space, wherein additional information is appended to or stored with the object information. This additional information relates to the relative coordinate position of that object or object element within a larger, more coarsely defined object space grid, such as an 8×8 grid. The apparatus and method of the present invention reduces the processing time necessary to locate the desired object within the object space by comparing the object and display area information relative to the grid for rapid preliminary acceptance or rejection prior to further detail search for the object or object elements. Thus, if no coincidence is found between the elements of the grid having at least a portion of the desired object and a second set of a grid elements corresponding to the desired display area, then the object is not located in the display area and further search in the corresponding grid portion of the object area is avoided. Similarly, signals relating cumulative object grid information are stored in linked memory lists, wherein comparisons between the display area grid information and the cumulative grid information contained in the linked display lists memory will eliminate the need to search that portion of memory should there be no coincidence, thereby enhancing the speed of object search.

Claims

1. A method of rapid object location within an area of interest in a multidimensional object space having a finite spatial resolution, comprising the steps of:

defining a plurality of regions in at least one dimension of said multidimensional space, said regions being larger than the spatial resolution of said object space;

providing a projection for said object in each dimension of said multidimensional object space, wherein

said projection provides an indication of the presence of at least a portion of said object in each said region;

defining said area of interest comprising at least one of said regions in each said dimension;

providing a projection of said area of interest in each said dimension, wherein

said projection provides an indication of the presence of at least a portion of said area of interest in each said region;

logically combining said projection of said object and said projection of said area of interest to provide an indication of the coincidence of the presence of at least a portion of said object in at least one of said plurality of regions, wherein

the location of said object is provided by the logical combination of said projection of said object and said projection of said area of interest.

2. The Method of claim 1, further including the steps of:

providing a display rectangle comprising at least a portion of a region in each dimension of said multidimensional object space;

determining if said display rectangle includes at least a portion of said region having said coincidence; and

displaying said object if a coincidence exists within said display rectangle.

3. The Method of claim 2, wherein

said object is described by a display list comprising a plurality of display vectors, said method further including the step of:

storing said projection for said object with said display vectors.

4. The Method of claim 3, further comprising the steps of:

providing a plurality of linked lists for providing said display list;

providing for each linked list, a cumulative logical combination of said projections for said object;

logically combining a selected one of said cumulative logical combination and a projection of an area of interest providing a list coincidence signal if at least a portion of said area of interest and said cumulative logical combination exists; and

elimination from further search said linked lists corresponding to the cumulative logical combination providing no list coincidence signal produced as a result of said logical combination.

5. The Method of claim 3, further comprising the steps of:

providing a plurality of linked lists providing said display list;

providing for each linked list, a cumulative logical combination of said projections for said objects;

providing a projection for a selected object;

comparing said projection of said selected object with said cumulative logical combination of one of said linked lists and providing a coincidence signal if at least a portion of said logical projection and said cumulative logical combination is coincident; and

eliminating from further search said one of said linked lists upon the absence of a corresponding coincidence signal.

16. The Method of claim 1, further including the steps of:

generating the projection signal of a second object;

detecting the coincidence of said projection signal of said second object and said composite projection signal; and

identifying second object constituent vectors from said projection signal of said second object.

6. Apparatus for providing rapid object location within an area of interest in a multidimension object space having a finite spatial resolution, comprising:

means for defining a plurality of regions in at least one dimension of said multidimensional space, said regions being larger than the spatial resolution of said object space;

means for providing a projection for said object in each dimension of said multidimensional object space, wherein

said projection provides an indication of the presence of at least a portion of said object in each said region;

means for defining said area of interest comprising at least one of said regions in each said dimension;

means for providing a projection of said area of interest in each said dimension, wherein

said projection provides an indication of the presence of at least a portion of said area of interest in each said region;

means for logically combining said projection of said object and said projection of said area of interest to provide an indication of the coincidence of the presence of at least a portion of said object in at least one of said plurality of regions, wherein

the location of said object is provided by the logical combination of said projection of said object and said projection of said area of interest.

7. The Apparatus of claim 6, further including:

means for providing a display rectangle comprising at least a portion of a region in each dimension of said multidimensional object space;

means for determining if said display rectangle includes at least a portion of said region having said coincidence; and

means for displaying said object if a coincidence exists within said display rectangle.

8. The Apparatus of claim 7, wherein

said object is described by a display list comprising a plurality of display vectors, said apparatus further including:

means for storing said projection for said object with said display vectors.

9. The Apparatus of claim 8, further comprising:

means for providing a plurality of linked lists for providing said display list;

means for providing for each linked list, a cumulative logical combination of said projections for said object;

means for logically combining a selected one of said cumulative logical combination and a projection of an area of interest providing a list coincidence signal if at least a portion of said area of interest and said cumulative logical combination exists; and

means for eliminating from further search said linked lists corresponding to the cumulative logical combination providing no list coincidence signal produced as a result of said logical combination.

10. The Apparatus of claim 8, further comprising:

means for providing a plurality of linked lists providing said display list;

means for providing for each linked list, a cumulative logical combination of said projections for said objects;

means for providing a projection for a selected object;

means for comparing said projection of said selected object with said cumulative logical combination of one of said linked lists and providing a coincidence signal if at least a portion of said logical projection and said cumulative logical combination is coincident; and

means for eliminating from further search said one of said linked lists upon the absence of a corresponding coincidence signal.

11. A method for identifying component vectors of a multidimensional object elements from among a plurality of listed vectors, comprising the steps of:

generating a projection signal corresponding to a projection of regions from a logical combination of the constituent vectors of a selected object;

storing said projection signal in a display list memory in association with said selected object in multidimensional object space;

defining an area of interest including at least one region;

generating an area of interest signal corresponding to said area of interest;

logically comparing said area of interest signal with said projection signal;

eliminating from further search said selected object if no coincidence is provided by said step of logical comparing detecting the coincidence of a selected object according to a coincidence of said area of interest signal with a projection signal of a first object; and

generating a composite projections signal from the projection of a composite object.

12. The method of claim 11, wherein

a composite object is formed from a plurality of selected objects, said method further comprising the step of:

forming a composite projection signal of regions from the logical combination of projection from the constituent selected objects.

15. The Method of claim 11, further including the steps of:

detecting the coincidence of said projection signal of said first object with said composite projection signal, wherein at least one non-coincident composite object constituent vector is identified among the constituent vectors of said composite object.

13. Apparatus for identifying component vectors of a multidimensional object elements from among a plurality of listed vectors, comprising:

means for generating a projection signal corresponding to a projection from a logical combination of the constituent vectors of a selected object;

means for storing said projection signal in a display list memory in association with said selected object in multidimensional object space;

means for defining an area of interest including at least one region;

means for generating an area of interest signal corresponding to said area of interest;

means for logically comparing said area of interest signal with said projection signal;

means for eliminating from further search said selected object if no coincidence is provided by said step of logical comparing means for detecting the coincidence of said area of interest with a selected object projection;

means for detecting at least one constituent vector of said coincident selected object with constituent vectors of a composite object; and

means for identifying regions of further coincident selected vectors from said composite projection.

14. The Apparatus of claim 13, wherein

a composite object is formed from a plurality of selected objects, said apparatus further comprising:

means for forming a composite projection of regions signal logical combination of projections from the constituent selected objects.