Geometric hashing method for model-based recognition of an object
First Claim
1. A method of pattern matching for recognition of objects within an image using a model defined by a set of one or more model primitives representative of large scale structures of an archetype, the method comprising steps of:
- deriving at least one target primitive representative of a large scale structure of the image;
for each target primitive;
identifying any model primitives that at least partially match the target primitive, andfor each identified model primitive, calculating a geometric figure of merit indicative of a degree of geometric correspondence between the target primitive and the model primitive; and
accumulating the geometric figures of merit;
wherein the step of deriving at least one target primitive comprises steps of;
detecting geometric features within the image;
analyzing the detected geometric features to find large scale structures of the image;
approximating each large scale structure with at least one respective primitive;
deriving a basis from at least one of the primitives; and
representing each of the primitives as invariants in the derived basis;
wherein the step of deriving a basis comprises the steps of calculating an origin of a respective local coordinate system and calculating an orientation of the respective local coordinate system;
wherein the step of deriving a basis further comprises the steps of deriving a plurality of bases and selecting at least one of the plurality of derived bases; and
wherein the step of selecting at least one of the plurality of derived bases comprises any one or more of;
selecting bases derived using relatively large primitives;
selecting at most two bases derived using any one primitive;
selecting bases having respective origins distributed substantially evenly across the image; and
selecting bases in respect of which the orientation of the respective coordinate system is parallel to at least one primitive used in the derivation of the respective basis.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of pattern matching for recognition of objects within an image, uses a model defined by a set of one or more model primitives representative of large scale structures of an archetype. The image is analyzed to derive at least one target primitive representative of a large scale structure of the image. A basis is derived from at least one of the target primitives, and each of the target primitives represented as invariants in the derived basis. For each target primitive, any model primitives that at least partially match the target primitive are identified. Each identified model primitive is then processed to calculate a figure of merit indicative of a degree of correspondence between the target primitive and the model primitive. In some embodiments, the figure of merit is an Orthogonal projection between the target and model primitives, which is and accumulated for each model basis.
14 Citations
7 Claims
-
1. A method of pattern matching for recognition of objects within an image using a model defined by a set of one or more model primitives representative of large scale structures of an archetype, the method comprising steps of:
-
deriving at least one target primitive representative of a large scale structure of the image; for each target primitive; identifying any model primitives that at least partially match the target primitive, and for each identified model primitive, calculating a geometric figure of merit indicative of a degree of geometric correspondence between the target primitive and the model primitive; and accumulating the geometric figures of merit; wherein the step of deriving at least one target primitive comprises steps of; detecting geometric features within the image; analyzing the detected geometric features to find large scale structures of the image; approximating each large scale structure with at least one respective primitive; deriving a basis from at least one of the primitives; and representing each of the primitives as invariants in the derived basis; wherein the step of deriving a basis comprises the steps of calculating an origin of a respective local coordinate system and calculating an orientation of the respective local coordinate system; wherein the step of deriving a basis further comprises the steps of deriving a plurality of bases and selecting at least one of the plurality of derived bases; and wherein the step of selecting at least one of the plurality of derived bases comprises any one or more of; selecting bases derived using relatively large primitives;
selecting at most two bases derived using any one primitive;
selecting bases having respective origins distributed substantially evenly across the image; and
selecting bases in respect of which the orientation of the respective coordinate system is parallel to at least one primitive used in the derivation of the respective basis.
-
-
2. A method of pattern matching for recognition of objects within an image using a model defined by a set of one or more model primitives representative of large scale structures of an archetype, the method comprising steps of:
-
deriving at least one target primitive representative of a large scale structure of the image; for each target primitive; identifying any model primitives that at least partially match the target primitive, and for each identified model primitive, calculating a geometric figure of merit indicative of a degree of geometric correspondence between the target primitive and the model primitive; and accumulating the geometric figures of merit; wherein the step of deriving at least one target primitive comprises steps of; detecting geometric features within the image; analyzing the detected geometric features to find large scale structures of the image; approximating each large scale structure with at least one respective primitive; deriving a basis from at least one of the primitives; and representing each of the primitives as invariants in the derived basis; wherein the step of deriving a basis comprises the steps of calculating an origin of a respective local coordinate system and calculating an orientation of the respective local coordinate system; and wherein the step of calculating the orientation of the respective local coordinate system comprises the steps of selecting one of the primitives used to calculate the origin, and setting the orientation of the coordinate system based on an orientation of the selected primitive. - View Dependent Claims (3, 4)
-
-
5. A method of pattern matching for recognition of objects within an image using a model defined by a set of one or more model primitives representative of large scale structures of an archetype, the method comprising steps of:
-
deriving at least one model primitive representative of large scale structures of an archetype; sampling each model primitive at two or more respective sample locations; mapping each sample location to a respective sample bin of a hash table; inserting a reference to the respective model primitive in the sample bin; deriving at least one target primitive representative of a large scale structure of the image; for each target primitive; identifying any model primitives that at least partially match the target primitive, and for each identified model primitive, calculating a geometric figure of merit indicative of a degree of geometric correspondence between the target primitive and the model primitive; and accumulating the geometric figures of merit. - View Dependent Claims (6)
-
-
7. A method of pattern matching for recognition of objects within an image using a model defined by a set of one or more model primitives representative of large scale structures of an archetype, the method comprising steps of:
-
deriving at least one target primitive representative of a large scale structure of the image; for each target primitive; identifying any model primitives that at least partially match the target primitive, and for each identified model primitive, calculating a geometric figure of merit indicative of a degree of geometric correspondence between the target primitive and the model primitive; and accumulating the geometric figures of merit; wherein each model primitive is associated with a respective model basis, and wherein the step of accumulating the geometric figures of merit comprises calculating a sum of the geometric figures of merit calculated for model primitives associated with the respective model basis; and further comprising the steps of; calculating a ratio indicative of a proportionality between the accumulated geometric figures of merit and an ideal accumulation of the geometric figures of merit; and selecting, as a candidate basis, the model basis having the highest ratio.
-
Specification