US4731860A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for identifying three-dimensional objects using two-dimensional images
Assignee: International Business Machines Corp
•
Filing: 1986-06-13
•
Granted: 1988-03-15
•
Expires: 2006-06-13
Abstract
Abstract For recognizing a three-dimensional object from its two-dimensional image which was produced e.g. by a TV camera, a Hough transform representation is generated of the image and specific configurations or structures of the cluster points which constitute the Hough transform representation are determined. The information about these specific configurations is compared to similar information stored for the Hough representation of known object models. By thus relating portions of the image to portions of one or several object models, vertices of the image which are present at line or edge intersections, are related to vertices of the known object model(s). This knowledge about the correspondence of model and object vertex points allows the exact fitting of vertices and thus recognition of the unknown object and its relative orientation. The models may be either primitive objects and the procedure determines of which primitives the unknown object is composed, or the models may be wire frame models each of which completely describes one more complicated object and the procedure determines to which of the models the entire unknown object fits best.
Inventors
- 👤 Friedrich M. Wahl
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 14:58
CPC Classifications
G; G06; G06V; G06V10/00; G06V10/40; G06V10/48
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
179 words
A machine method for recognizing or identifying a three-dimensional object from a two-dimensional image of the object, using a Hough space representation of said image comprising clusters each represented by its center point, comprising the steps of: (a) determining in the Hough space representation of said object image, cluster configurations having specific properties; (b) providing predetermined cluster configurations of Hough space representations which correspond to known object models identifying vertex points in three-dimensional space; (c) relating cluster configurations determined in step (a) to said predetermined cluster configurations of Hough space representations, in order to identify said object by comparison of the vertex points of said object image represented by cluster configurations determined in step (a) to corresponding vertex points of said object model representations; and (d) if further information is required for identification, fitting vertex points of the object image, the locations of which are given by the slope and intercept of respective cluster point colinearities in Hough space representation, to vertex points of at least one object model, on the basis of the relations determined in step (b).
Claim 2
Dependent Claim
179 words
A machine method for recognizing or identifying a three-dimensional object from a two-dimensional image of the object, using a Hough space representation of said image comprising clusters each represented by its center point, comprising the steps of: (a) determining in the Hough space representation of said object image, cluster configurations having specific properties; (b) providing predetermined cluster configurations of Hough space representations which correspond to known object models identifying vertex points in three-dimensional space; (c) relating cluster configurations determined in step (a) to said predetermined cluster configurations of Hough space representations, in order to identify said object by comparison of the vertex points of said object image represented by cluster configurations determined in step (a) to corresponding vertex points of said object model representations; and (d) if further information is required for identification, fitting vertex points of the object image, the locations of which are given by the slope and intercept of respective cluster point colinearities in Hough space representation, to vertex points of at least one object model, on the basis of the relations determined in step (b).
Claim 3
Dependent Claim
52 words
Method according to claim 1, wherein said known object models comprise object primitive models representing basic geometrical objects, and for each such model a Hough space representation of its image as seen from a given view angle, with data characterizing existing specific cluster configurations of the respective model, is stored for comparison.
Claim 4
Dependent Claim
53 words
Method according to claim 1, wherein said known object models comprise wire frame models each representing the respective object modeled completely by providing geometric information about all its edges and vertices, and for each such wire frame model a Hough space representation with data characterizing existing specific cluster configurations is stored for comparison.
Claim 5
Dependent Claim
53 words
Method according to claim 3, wherein a Hough space representation with data characterizing specific cluster configurations is stored for each of a plurality of images of each such wire frame model as seen from different view angles, said images not comprising the edges and vertices which are hidden for the respective view angle.
Claim 6
Dependent Claim
86 words
Method according to claim 3, further comprising the steps of: providing a graph representing the interrelation between edges and vertices of each wire frame model and information about the common slopes of edges; providing a graph representing the interrelation of viewed edges and vertices, including common slopes, from the information about colinearities in the Hough space representation of an unknown object; and in a graph matching procedure, identifying those portions of the graph of each wire frame model which fit the graph of the unknown object.
Claim 7
Dependent Claim
32 words
Method according to claim 1, wherein said specific properties of cluster configurations include colinear arrangements of clusters, cluster colinearities intersecting each other exactly at a cluster, and parallel arrangements of cluster colinearities.
Claim 8
Dependent Claim
30 words
Method according to claim 1, wherein if more than one possible solution is found in step (c), one actual solution is selected by the vertex fitting procedure of step (d).
Claim 9
Dependent Claim
192 words
A machine method for recognizing a three-dimensional object from a two-dimensional image of the object, using a Hough space representation of said image comprising clusters each repesented by its center point, comprising the steps of: (a) determining, in the Hough space representation of said object image, linear arrangements of cluster points, called cluster colinearities, each of said cluster colinearities representing a vertex in said object image; (b) preparing tables of such cluster colinearities indicating their interrelations, including common cluster points; (c) preparing tables representing specific cluster colinearity configurations identifying specific vertex point arrangements in said object image; (d) preparing a Hough space representation for each of a plurality of preselected object models; (e) determining cluster colinearities and preparing tables of cluster colinearities indicating their interrelations, for each of the preselected model Hough space representations, each of their cluster colinearities being related to a 3-D defined vertex point of the respective model; and (f) comparing the object colinearity tables prepared in step (c) to model colinearity tables prepared in step (e) for determining similar cluster colinearity configurations, thus relating vertex points of the object image to vertex points of at least one model.
Claim 10
Dependent Claim
192 words
A machine method for recognizing a three-dimensional object from a two-dimensional image of the object, using a Hough space representation of said image comprising clusters each repesented by its center point, comprising the steps of: (a) determining, in the Hough space representation of said object image, linear arrangements of cluster points, called cluster colinearities, each of said cluster colinearities representing a vertex in said object image; (b) preparing tables of such cluster colinearities indicating their interrelations, including common cluster points; (c) preparing tables representing specific cluster colinearity configurations identifying specific vertex point arrangements in said object image; (d) preparing a Hough space representation for each of a plurality of preselected object models; (e) determining cluster colinearities and preparing tables of cluster colinearities indicating their interrelations, for each of the preselected model Hough space representations, each of their cluster colinearities being related to a 3-D defined vertex point of the respective model; and (f) comparing the object colinearity tables prepared in step (c) to model colinearity tables prepared in step (e) for determining similar cluster colinearity configurations, thus relating vertex points of the object image to vertex points of at least one model.
Claim 11
Dependent Claim
71 words
Method according to claim 8, comprising the further steps of preparing additional edge slope tables for said object image as well as for the models, indicating common slopes of edges which are represented as cluster points in the Hough space representations of said object image and of each model, and additionally using in step (f) the indications of the edge slope tables for relating image vertex points to model vertex points.
Claim 12
Independent Claim
199 words
A system for recognizing or identifying a three-dimensional object from a two-dimensional image of the object, using a Hough space representation of said image comprising clusters each represented by its center point, comprising: (a) means for determining in the Hough space representation of said object image, cluster configurations having specific properties; (b) means for storing predetermined cluster configurations of Hough space representations which correspond to known object models identifying vertex points in three-dimensional space; (c) means for comparing said cluster configurations determined by said determining means to said predetermined cluster configurations of Hough space representations stored in said storage means, in order to identify said object by comparison of the vertex points of said object image represented by said determined cluster configurations to corresponding vertex points of said object model representations; and (d) means, responsive to said comparing means, for identifying said object and, if further information is required for identification, for fitting vertex points of the object image, the locations of which are given by the slope and intercept of respective cluster point colinearities in Hough space representation, to vertex points of at least one object model, on the basis of the relations determined by said comparing means.
Claim 13
Independent Claim
199 words
A system for recognizing or identifying a three-dimensional object from a two-dimensional image of the object, using a Hough space representation of said image comprising clusters each represented by its center point, comprising: (a) means for determining in the Hough space representation of said object image, cluster configurations having specific properties; (b) means for storing predetermined cluster configurations of Hough space representations which correspond to known object models identifying vertex points in three-dimensional space; (c) means for comparing said cluster configurations determined by said determining means to said predetermined cluster configurations of Hough space representations stored in said storage means, in order to identify said object by comparison of the vertex points of said object image represented by said determined cluster configurations to corresponding vertex points of said object model representations; and (d) means, responsive to said comparing means, for identifying said object and, if further information is required for identification, for fitting vertex points of the object image, the locations of which are given by the slope and intercept of respective cluster point colinearities in Hough space representation, to vertex points of at least one object model, on the basis of the relations determined by said comparing means.
Claim 14
Dependent Claim
56 words
System according to claim 10, wherein said known object models comprise object primitive models representing basic geometrical objects, and for each such model a Hough space representation of its image as seen from a given view angle, with data characterizing existing specific cluster configurations of the respective model, is stored in said storage means for comparison.
Claim 15
Dependent Claim
57 words
System according to claim 10, wherein said known object models comprise wire frame models each representing the respective object modeled completely by providing geometric information about all its edges and vertices, and for each such wire frame model a Hough space representation with data characterizing existing specific cluster configurations is stored in said storage means for comparison.
Claim 16
Dependent Claim
57 words
System according to claim 12, wherein a Hough space representation with data characterizing specific cluster configurations is stored in said storage means for each of a plurality of images of each such wire frame model as seen from different view angles, said images not comprising the edges and vertices which are hidden for the respective view angle.
Claim 17
Dependent Claim
86 words
System according to claim 12, further comprising: means for providing a graph of the interrelation between edges and vertices of each wire frame model and information about the common slopes of edges; means for providing a graph representing the interrelation of viewed edges and vertices, including common slopes, from the information about colinearities in the Hough space representation of an unknown object; and graph matching means for identifying those portions of the graph of each wire frame model which fit the graph of the unknown object.
Claim 18
Dependent Claim
32 words
System according to claim 10, wherein said specific properties of cluster configurations include colinear arrangements of clusters, cluster colinearities intersecting each other exactly at a cluster, and parallel arrangements of cluster colinearities.
Claim 19
Dependent Claim
34 words
System according to claim 10, wherein said identifying means comprises means, if more than one possible model is found by said comparing means, for selecting one actual model according to said vertex fitting procedure.
Claim 20
Independent Claim
205 words
A system for recognizing a three-dimensional object from a two-dimensional image of the object, using a Hough space representation of said image comprising clusters each represented by its center point, comprising: (a) means for determining, in the Hough space representation of said object image, linear arrangements of cluster points, called cluster colinearities, each of said cluster colinearities representing a vertex in said object image; (b) first means for preparing tables of such clusters colinearities indicating their interrelations, including common cluster points; (c) second means for preparing tables representing specific cluster colinearity configurations identifying specific vertex point arrangements in said object image; (d) means for preparing a Hough space representation for each of a plurality of preselected object models; (e) third means for determining cluster colinearities and preparing tables of cluster colinearities indicating their interrelations, for each of the preselected model Hough space representations, each of their cluster colinearities being related to a 3-D defined vertex point of the respective model; and (f) means for comparing the object colinearity tables prepared by said second means to model colinearity tables prepared by said third means for determining similar cluster colinearity configurations, thus relating vertex points of the object image to vertex points of at least one model.
Claim 21
Independent Claim
205 words
A system for recognizing a three-dimensional object from a two-dimensional image of the object, using a Hough space representation of said image comprising clusters each represented by its center point, comprising: (a) means for determining, in the Hough space representation of said object image, linear arrangements of cluster points, called cluster colinearities, each of said cluster colinearities representing a vertex in said object image; (b) first means for preparing tables of such clusters colinearities indicating their interrelations, including common cluster points; (c) second means for preparing tables representing specific cluster colinearity configurations identifying specific vertex point arrangements in said object image; (d) means for preparing a Hough space representation for each of a plurality of preselected object models; (e) third means for determining cluster colinearities and preparing tables of cluster colinearities indicating their interrelations, for each of the preselected model Hough space representations, each of their cluster colinearities being related to a 3-D defined vertex point of the respective model; and (f) means for comparing the object colinearity tables prepared by said second means to model colinearity tables prepared by said third means for determining similar cluster colinearity configurations, thus relating vertex points of the object image to vertex points of at least one model.
Claim 22
Dependent Claim
76 words
System according to claim 17, further comprising means for preparing additional edge slope tables for said object image as well as for the models, indicating common slopes of edges which are represented as cluster points in the Hough space representations of said object image and of each model, and means for providing the indications of said additional edge slope tables to said comparing means for additional use in relating image vertex points to model vertex points.
References Cited (Backward Citations)
US3069654A
Cited
US4618989A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1991-03-15 | 1991-09-14 | 1992-03-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1995-03-15 | 1995-09-14 | 1996-03-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1999-03-15 | 1999-09-14 | 2000-03-15 | $7700.00 | Window Closed / Lapsed |