Method and apparatus for high speed object location
First Claim
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, whereinsaid 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, whereinsaid 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, whereinthe location of said object is provided by the logical combination of said projection of said object and said projection of said area of interest.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
16 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. - View Dependent Claims (2, 3, 4, 5, 16)
-
-
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. - View Dependent Claims (7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 15)
-
-
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. - View Dependent Claims (14)
-
Specification