Abstract:
A system provides high-speed multiple line digitization for three-dimensional imaging of a physical object. A full frame of three-dimensional data may be acquired in the same order as the frame rate of a digital camera.

Description:
PRIORITY AND CROSS REFERENCE TO RELATED APPLICATION 
   This application claims the benefit under 35 U.S.C. § 119(e) of co-pending provisional application No. 60/503,666 filed Sep. 17, 2003 for High Speed Multiple Line Three-Dimensional Digitization, which is incorporated in its entirety herein by reference. 

   BACKGROUND OF THE INVENTION 
   1. Technical Field 
   This invention generally relates to three-dimensional imaging of a physical object, and in particular to a high-speed multi-line triangulation for three-dimensional digitization of a physical object. 
   2. Related Art 
   Imaging techniques provide a three-dimensional visualization of a physical object on a video terminal or monitor. The three-dimensional visualization may illustrate surface characteristics of the physical object. Data associated with the surface characteristics are generated and processed by a processor to generate the three-dimensional visualization. 
   Data associated with the surface characteristics are generated by capturing images of the object from various perspectives. The perspectives are mapped or combined to produce a set of data points that represent the various surfaces of the object. The data points are processed to generate the three-dimensional visual display of the object. The data points also may be processed to represent the object in a dimensionally correct manner in the computer. However, the time to generate the data points is longer than the display rate for the digital camera. 
   Imaging systems that use a triangulation technique emanate a single point or a single line on the object to determine relative surface characteristics of the object. Multiple line systems are limited by the maximum number of simultaneous lines that may image the object and require a large number of images to obtain a final image of the object. 
   A Moiré technique may use multiple lines to compute a relative height map of the surface characteristics. Each point has a known or predetermined relative relationship to a neighboring point on a neighboring line. A sinusoidal variation of the lines provides a trigonometric solution to estimate the relative relationships or equivalently extracting the phase. Such technique requires either multiple images or substantial processing time to provide a three-dimensional image. 
   Accordingly, there is a need for a high-speed three dimensional imaging system that minimizes the number of images and amount of computation to provide a three-dimensional image. 
   SUMMARY 
   By way of introduction only, a high speed multiple line three-dimensional digitization may include imaging a physical object to provide a visualization or virtualization of the object that may be viewed and manipulated by using a processor. The high speed multiple line three-dimensional digitization may be achieved by one or more apparatuses, devices, systems, methods, and/or processes. 
   In an embodiment, the high-speed multiple-line digitization generates a full frame of three-dimensional data of a surface of a physical object that is acquired in substantially the same order as a frame rate of a camera used to acquire or capture the three-dimensional image. For example, a camera used to capture a three-dimensional image has a frame rate of N frames per second. A full frame of three-dimensional data is obtained in a time frame of m/N seconds where m different patterns are projected. For example, where two patterns are projected, a full frame of three-dimensional data is obtained in a time frame f 2/N seconds. The full frame of three-dimensional data includes multiple data points represented by multiple floating point numbers. 
   The foregoing summary is provided only by way of introduction. The features and advantages of the high speed multiple line three-dimensional digitization may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the claims. Nothing in this section should be taken as a limitation on the claims, which define the scope of the invention. Additional features and advantages of the present invention will be set forth in the description that follows, and in part will be obvious from the description, or may be learned by practice of the present invention. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The invention can be better understood with reference to the following drawings and description. The components in the figures are not necessarily to scale, emphasis instead being placed upon illustrating principles of the invention. Moreover, in the figures, like referenced numerals designate corresponding parts throughout the different views. 
       FIG. 1  illustrates a high-speed multi-line three-dimensional digitization system having a camera fixed relative to a line projector. 
       FIG. 2  illustrates a coordinate view of the system of  FIG. 1 . 
       FIG. 3  illustrates a line pattern incident on a surface of an object. 
       FIG. 4  illustrates an approximate line pattern estimated from a first pattern frame scan for comparison with an actual line pattern for a subsequent frame as observed by the camera of  FIG. 1 . 
       FIG. 5  illustrates non-rectangular regions of distinguishability. 
       FIG. 6  illustrates an embodiment where multiple light sources are derived from a single laser source switched with a liquid crystal cell. 
       FIG. 7  illustrates an embodiment for multiple laser sources. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   Hereinafter exemplary embodiments are discussed with reference to accompanied figures. 
     FIG. 1  illustrates a digitization system  100 . The digitization system  100  includes a camera  106  and a line pattern projector or illuminator  104 . The camera  106  is fixed relative to the line pattern projector  104 . The projector  104  illuminates a portion of a surface  108  of object  102  with a light pattern. The object may be any physical object capable of being imaged. In an embodiment, the object may be dentition or dental items including molds, castings, dentition, prepared dentition and the like. 
   Light reflected from the surface  108  is captured by the camera  106 . Based on the reflected light pattern, three-dimensional data representative of the illuminated surface  108  may be generated. The three-dimensional data may be processed to generate a three-dimensional image of the illuminated surface  108 . The camera  106  may be characterized by a local coordinate system XY, and the projector  104  characterized by a local coordinate system X′Y′. 
   Referring to  FIG. 2 , pattern projector  204  projects a pattern during a capture or read period. The pattern may be considered to be an assembly of multiple points. The number of points may be finite or substantially infinite. The size of the points may be finite or infinitesimal. An example of such a pattern is a pattern consisting of multiple lines. The pattern may be structured white light. 
   In an embodiment, camera  206  is a high-speed camera that images general patterns or multiple line patterns. The camera  206  may also capture multiple line patterns during a read period. The relationship shown in  FIG. 2  refers to a single point in such a line pattern. A triangulation axis R may be defined as passing through an intersection of an axial ray from camera  206  and an axial ray of projector  204 . The axis R may be perpendicular to an axial ray from camera  206  and an axial ray of projector  204 . The triangulation axis R also may be substantially parallel to Y and Y′. A minimum angle θ between a valid ray between the projector  204  relative to a valid axial ray of the camera  206  is non-zero. 
   A line projected by projector  204  represents a connected series of points or curvilinear segments where a normal vector n at any point along the curve obeys the following equation or rule: 
                        n   ·   R          ≥     1     2               (   1   )               
According to Equation (1), the angle between a point on the curve and the triangulation axis R is greater than or equal to about 45 degrees. The line may have a cross-sectional intensity characterized by a function that is independent of Equation 1. The cross-sectional intensity may have a sinusoidal variation, a Gaussian profile, or any other function for cross-sectional intensity.
 
   The local coordinate system XY of the camera  206  may be further characterized by a coordinate system XYZ, where the XY coordinate system defined by the camera include axis Z, which is substantially perpendicular to both the X-axis and the Y-axis. The axis Z includes a range of values for Z based on optics limitations. The values for Z may be based on distances d 1  and d 2  such that d 1 ≦z≦d 2 . A single point from a projected line incident on a plane perpendicular to Z will appear to be displaced in the X direction by ΔX. Based on a triangulation angle, the following condition exists: 
   
     
       
         
           
             
               
                 
                   Δ 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   z 
                 
                 = 
                 
                   
                     Δ 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     x 
                   
                   
                     Tan 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     θ 
                   
                 
               
             
             
               
                 ( 
                 2 
                 ) 
               
             
           
         
       
     
   
   In a projected line pattern having multiple lines L 1 -L n , a given line L i  may be characterized by a unique function θ(x). For a given line L i , the location of line L i  with respect to the coordinate system XYZ of the camera  206  for various values of z where d 1 ≦z≦d 2  may be determined through calibration or similar process. 
   For an observed line L c , a closest calibrated line position may be selected, and the x and z coordinates (x c , z c ) of the calibrated line determined. The camera  206  may observe multiple lines during projected on an object  102 . For each observed point on the line, as captured or observed by the camera  206 , the XY coordinates of that surface point may be directly observed as (x observed , y observed ). A point z observed  may be determined by observing the displaced Δx (where Δx=x observed −x c ), to compute Δz. The z coordinate may then be computed as:
 
 z   observed   =z   c   +Δz.   (3)
 
The maximum displacement for any line in the volume may be determined by:
 
Δ x =( d   1 - d   2 ) Tan θ  (4)
 
   A maximum number of simultaneously distinguishable lines n max  may be determined as: 
   
     
       
         
           
             
               
                 
                   n 
                   max 
                 
                 = 
                 
                   
                     X 
                     max 
                   
                   
                     
                       ( 
                       
                         
                           d 
                           1 
                         
                         - 
                         
                           d 
                           2 
                         
                       
                       ) 
                     
                     ⁢ 
                     Tan 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       θ 
                       max 
                     
                   
                 
               
             
             
               
                 ( 
                 4 
                 ) 
               
             
           
         
       
     
   
   The maximum number of simultaneously distinguishable lines n max  increases with a decreasing depth of field d 1 -d 2 . The maximum number of simultaneously distinguishable lines n max  also increases with as θ max  decreases. The accuracy of the determination also may also decrease with smaller θ max  values. Also, decreasing a depth of field may result in a less useful volume for digitizing. 
     FIG. 3  illustrates a line pattern having multiple lines L 1 -L n  projected toward an object  302 . Each line L 1 -L n  represents a connected series of points or curvilinear segments where a normal vector n at any point along the curve obeys equation 1 above. The multiple lines L 1 -L n  are projected toward and incident onto a surface  308  of the object  302 . 
   Multiple patterns of lines L 1 -L n  may be projected toward the object  302  during a capture period. The light patterns may be referred to as A i  where I=1, 2, . . . x, where the first light pattern having L 1 -L n  lines is referred to as A 1  and subsequent line patterns are referred to as A 2  to A x . The number of lines n in pattern A i  may be selected so that n≦n max . In  FIG. 3 , a first pattern includes a number of distinguishable curvilinear lines {L 1 , L 2  and L n }, and a second, subsequent pattern includes a number of distinguishable curvilinear lines {L′ 1 , L′ 2  and L′ n }. 
   According to Equation (4), each line in pattern A 1  incident on the surface  308  may be uniquely labeled or identified. For each line pattern A 1 , the x, y and z coordinates may be determined for each point on the line using the above equations. For each line L i , data-points representative of characteristics of the surface  308  along the line L i  may be generated. From the data points, a three-dimensional representation of the surface  302  along the line L i  is formed. From all the lines of pattern A 1 , an approximation of the surface of the object being digitized may be determined. 
   For the subsequent patterns A i , where i=2, . . . x, let n i  represent the number of lines for the pattern A i . For i&lt;j the condition n i ≦n j  holds. Also, n i &gt;n max  for each i. Because equation (4) no longer holds, labeling or identifying lines for A i  may be resolved during a prior calibration step. 
   In a calibration step, each line in A i  is characterized on a flat plane for different Z values. Based on the characterization, and an approximation surface, the approximate locations of each labeled line in A i  is estimated by intersecting a known light plane corresponding with each labeled line with the approximation surface  308 . The estimation may be compared to the observed line pattern for A i  incident on the surface  302 , and observed lines accordingly labeled. 
     FIG. 4  illustrates an approximate line pattern estimated from a first pattern frame scan  410  compared with an actual line pattern  412  for a subsequent frame as observed by camera  206 . By choosing closest curves, a unique labeling of the multiple lines L 1 -L n  is obtained. A new approximation surface is thus obtained by repeated application of equation (4) on each labeled line. This may be repeated using a new and enhanced approximation surface of the surface and a higher density line pattern. 
     FIG. 5  illustrates non-rectangular regions of distinguishability. In an embodiment, non-rectangular regions of distinguishability may be defined as areas between adjacent projection lines L 1 -L n . For example, a non-rectangular region of distinguishability may be defined as the region between a first line L 1  of the multiple line pattern and a second line L 2  of the light pattern. For each line that may be projected onto a planar surface placed at z values between d 1  and d 2 , the region of distinguishability defines the smallest envelope that always includes that line as imaged by the imaging system. Other lines L i  will have separate regions of distinguishability. Therefore, in the exemplary embodiment, each line may be projected to a discrete area where substantially no overlap exists between adjacent areas. 
     FIG. 5  illustrates an example of a pattern where three lines are being projected, with non-overlapping regions of distinguishability. By allowing non-rectangular regions of distinguishability, the limitations of equation (4) may be minimized or eliminated altogether by allowing non-rectangular regions for each line, where the non-rectangular regions may be compressed without substantial overlap or ambiguity. The number of simultaneous projected lines may be increased by allowing the distinguishable regions around each line to follow a shape of the line instead of a defined rectangular area. Accordingly, the maximum number of simultaneous lines may be increased. 
   An embodiment for a projector for a high speed multiple line three-dimensional digitization system may include a modulated laser source having a two-axis orthogonal mirror scanner. The scanner may have a single two axis mirror, two orthogonally mounted single axis mirrors, or the equivalents. The scanner may project a two-dimensional light pattern having multiple lines L 1 -L n  through optics toward a surface of an object. The light pattern illuminates the surface. Light reflected from the surface may be captured by a camera. The patterns incident on the object may be viewed through additional optics, a CCD, CMOS digital camera, or similar device. The line patterns are analyzed and converted to three-dimensional coordinates representative of the illuminated surface. 
   Referring to  FIG. 6 , an embodiment having two laser sources  620 ,  622  is shown. The two laser sources  620 ,  622  each project a laser beam. The laser beams pass through a focusing lens  624  and a line lens  626  that transforms the single point from each laser source  620 ,  622  into a line. Each line then passes through two different diffraction gratings  628  that split the line into multiple substantially parallel lines. The multiple minimal patterns may be produced without substantial moving parts. 
   Referring to  FIG. 7 , an embodiment having a single laser source  720  is shown. The laser source  720  may be switched using a liquid crystal (LC) cell  734 . The laser light beam from the single laser source  720  passes through a wave plate  732  to polarize the light. The wave plate  732  may be a ½ wave plate. The laser light is polarized based on the LC cell  734 , in a particular direction and/or orientation, where the direction may be switched by switching the LC cell  734 . Two possible paths for the light may pass through the beam splitter  736  so that the single laser beam may be split to two paths. The laser point may be processed as described. 
   In an embodiment for a high speed multiple line three-dimensional digitization system, a scanner and camera may be configured as described according to co-pending U.S. patent application Ser. No. 10/749,579, entitled LASER DIGITIZER SYSTEM FOR DENTAL APPLICATIONS, filed on Dec. 30, 2003, the description of which is incorporated herein in its entirety. The scanner may be a modulated laser source, coupled to a two axis orthogonal mirror scanner. An embodiment for a high speed multiple line three-dimensional digitization system may include a modulated laser source, coupled to a two axis orthogonal mirror scanner. The scanner may have a single two axis mirror, two orthogonally mounted single axis mirrors, or the equivalents. By varying the rotation of the mirror(s), and by modulating the laser beam, a two-dimensional pattern may be traced. The pattern may be projected through optics onto the physical object, and the patterns incident on the object viewed through additional optics, a CCD, CMOS digital camera, or similar device. The line patterns are analyzed and converted to three-dimensional coordinates for the surface. 
   It is intended in the appended claims to cover all such changes and modifications which fall within the true spirit and scope of the invention. Therefore, the invention is not limited to the specific details, representative embodiments, and illustrated examples in this description. Accordingly, the invention is not to be restricted except in light as necessitated by the accompanying claims and their equivalents.