Dynamic visual registration of a 3-D object with a graphical model

• US 6,330,356 B1
• Filed: 09/29/1999
• Issued: 12/11/2001
• Est. Priority Date: 09/29/1999
• Status: Expired due to Term

• Current Assignee: Mind Fusion, LLC (Ascend Innovation Management, LLC)
• Original Assignee: Rockwell Science Center LLC
• Inventors: Sundareswaran, Venkataraman, Behringer, Reinhold Werner
• Primary Examiner(s): AHMED, SAMIR ANWAR
• Application Number:
  US09/407,928
• Time in Patent Office: 804 Days
• Field of Search: 382/103, 382/154, 382/285, 382/291, 382/294, 382/295, 345/7-9, 345/112-114, 345/139, 345/418, 345/629, 345/630, 345/648, 345/649, 345/633, 345/634, 345/672, 345/757, 345/664, 356/12, 356/373, 356/374, 356/375
• US Class Current: 382/154
• CPC Class Codes: G06T 3/00 Geometric image transformations in the plane of the image
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/73 using feature-based methods

Abstract

The invention displays computer graphics in combination with imagery of real objects, while maintaining apparent alignment notwithstanding any changes of viewpoint of an imaging device relative to the real object. A computer executed control loop recognizes features in the image and finds a corresponding position and orientation of a CAD model by projecting the CAD representation onto a “virtual camera” and “moving” the virtual camera to track the relative motion of the real imaging device, according to an efficient “visual servoing” algorithm. In an alternate embodiment of the invention, computing tasks are divided between an “image processing host” and one or more “display hosts” which communicate over a channel. Bandwidth is conserved by performing image registration locally at the display host(s) using the “visual servoing” algorithm.

Claims

1. A method for finding the relative position and orientation of an imaging device in relation to an imaged object, wherein said imaging device produces a video signal representing a two-dimensional projection of said imaged object onto an image frame, the method comprising the steps of:

recognizing a plurality of features from the video signal;

associating with each recognized feature a two-dimensional position in the image frame;

computing a disparity between the positions of the features and corresponding positions of features in a calculated projection of a stored, three-dimensional object model, said calculated projection calculated according to a virtual camera model; and

varying parameters of the virtual camera model, consistent with a projective geometric model, to reduce said disparity;

wherein said disparity is reduced by computing and applying a transformation matrix including translation sub-matrix and rotation sub-matrix, and wherein said sub-matrices are calculated from translation and rotation sub-vectors of a vector obtained by multiplying a constant with a product of an error function and a pseudo-inverse of an interaction matrix L;

wherein said interaction matrix L represents two dimensional coordinates xp, yp and a depth Z for a plurality of pre-defined points in a calculated three dimensional object model, and said two dimensional coordinates xp, yp are calculated projected positions of said pre-defined points onto a hypothetical plane of projection which corresponds to an image plane of said virtual camera model.

2. The method of claim 1, wherein said parameters are varied by rotating said virtual camera model relative to a pre-defined coordinate system.

3. The method of claim 2, wherein said parameters are varied by translating said virtual camera model relative to a predefined coordinate system.

4. The method of claim 2, further comprising the step of:

reiteratively repeating said previously recited steps in a loop, to further reduce said disparity.

5. A method of registering a two-dimensional object image of a three-dimensional object with a stored, three-dimensional model having a predetermined spatial relationship to the three-dimensional object, comprising the steps of:

identifying the positions of a plurality of features in said object image;

rendering a virtual image by projecting at least portions of said three-dimensional model onto a virtual image plane;

calculating an error function which measures a difference between positions of said plurality of features in said object image and corresponding positions of previously associated features in said virtual image;

finding a position and/or orientation of said virtual image plane which reduces said error function,

wherein said position and/or orientation are found by computing and applying a transformation matrix including a translation sub-matrix and a rotation sub-matrix, and wherein said sub-matrices are calculated from translation and rotation sub-vectors of a vector obtained by multiplying a constant with a product of an error function and a pseudo-inverse of an interaction matrix L;

wherein said interaction matrix L represents two dimensional coordinates xp, yp and a depth Z for a plurality of pre-defined points in a calculated three dimensional object model, and said two dimensional coordinates xp, yp are calculated projected positions of said pre-defined points onto the virtual image plane.

6. The method of claim 5, wherein an orientation of said virtual image plane is found by iteratively rotating said virtual image plane relative to a pre-defined coordinate system.

7. The method of claim 6, wherein said position of said virtual image plane is found by reiteratively translating said virtual image plane relative to a pre-defined coordinate system.

8. The method of claim 5, wherein said error function is represented by a vector having plural distance components, each said distance component being a distance between a feature position in the object image and a corresponding virtual feature position in said virtual image.

9. The method of claim 8, wherein said feature positions in said object image are determined by recognizing ring-shaped markers on said three dimensional object.

10. The method of claim 9, wherein said ring shaped markers are coded to identify specific markers with an associated identifier.

11. The method of claim 10, wherein said ring-shaped markers are coded according to a binary code.

12. The method of claim 9, wherein said markers are recognized by searching an image for projected bands of contrast having a predetermined ratio between their width and their diameter.