Abstract:
A method and apparatus are provided for determining or estimating the focal length of a camera based on a series of images captured by the camera. In one embodiment, a method for determining focal length includes obtaining a plurality of images of a three-dimensional scene from the camera, matching feature points across a subset of the images, deriving a projective reconstruction from the feature point matching, and finally recovering a metric reconstruction from the projective reconstruction in accordance with semidefinite programming. Once the metric reconstruction is recovered, the camera&#39;s intrinsic parameters, including focal length, can be estimated.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
       [0001]     This application claims the benefit of U.S. Provisional Patent Application Ser. No. 60/618,689, filed Oct. 14, 2004, which is herein incorporated by reference in its entirety. 
     
    
     REFERENCE TO GOVERNMENT FUNDING  
       [0002]     This invention was made with Government support under contract number DAAD19-01-2-0012, awarded by the U.S. Army. The Government has certain rights in this invention. 
     
    
     FIELD OF THE INVENTION  
       [0003]     The present invention relates generally to computer vision and relates more specifically to determining the focal length of a moving camera.  
       BACKGROUND OF THE DISCLOSURE  
       [0004]     Reconstruction of three-dimensional (3D) scenes from a video sequence is a fundamental problem of computer vision. One way in which this objective can be advanced is advancing the state of the art in uncalibrated structure from motion.  
         [0005]     Currently, the best result achievable in the uncalibrated setting is a reconstruction of a scene up to an unknown projective transformation. This projective structure, however, is insufficient for many applications which require measurement of three-dimensional angles or distances, thereby necessitating a metric or Euclidean reconstruction (e.g., as in the case of a camera placed inside a vehicle to determine the location of a passenger). To obtain the Euclidean reconstruction, though, knowledge of the camera&#39;s calibration parameters (e.g., focal length, aspect ratio) is needed. Typically, these parameters are obtained offline using a calibration pattern. However, this approach is quite restrictive.  
         [0006]     Thus, there is a need in the art for a method and apparatus for determining camera focal length.  
       SUMMARY OF THE INVENTION  
       [0007]     A method and apparatus are provided for determining or estimating the focal length of a camera based on a series of images captured by the camera. In one embodiment, a method for determining focal length includes obtaining a plurality of images of a three-dimensional scene from the camera, matching feature points across a subset of the images, deriving a projective reconstruction from the feature point matching, and finally recovering a metric reconstruction from the projective reconstruction in accordance with semidefinite programming. Once the metric reconstruction is recovered, the camera&#39;s intrinsic parameters, including focal length, can be estimated. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0008]     The teachings of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which:  
         [0009]      FIG. 1  is a flow diagram illustrating one embodiment of a method for determining camera focal length, according to the present invention;  
         [0010]      FIG. 2  is a flow diagram illustrating one embodiment of a method for obtaining a metric reconstruction from a projective reconstruction using semidefinite programming, according to the present invention; and  
         [0011]      FIG. 3  is a high level block diagram of the present method for focal length determination that is implemented using a general purpose computing device. 
     
    
       [0012]     To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures.  
       DETAILED DESCRIPTION  
       [0013]     In one embodiment, the present invention relates to a method and apparatus for determining camera focal length through application of semidefinite programming (SDP). In one embodiment, the present invention assumes that the camera has rectangular pixels (e.g., is a skewless camera) and that the principal point of the camera is known and fixed. The present invention then estimates the aspect ratio and focal length of the camera at each frame of a video sequence in accordance with these assumptions.  
         [0014]     As used herein, the term “camera” refers to any image capturing device that is capable of capturing still and/or moving images (e.g., a photo camera, a video camera, a cell phone camera, etc.).  
         [0015]      FIG. 1  is a flow diagram illustrating one embodiment of a method  100  for determining camera focal length, according to the present invention. In this embodiment, the principal point position of the camera is assumed to be fixed at the center of an image or sequence of images.  
         [0016]     The method  100  is initialized at step  102  and proceeds to step  104 , where the method  100  obtains n images of a rigid scene. In one embodiment, n is at least three. In one embodiment, the n images are received from a camera having changing intrinsic and/or extrinsic parameters. Intrinsic parameters, denoted as K i , are those parameters that can be varied by varying the camera&#39;s focal length, while extrinsic parameters are those parameters that can be varied by moving the camera itself. In one embodiment, the camera is a skewless camera (e.g., having rectangular pixels). In further embodiments, the intrinsic parameters are assumed to be constant. In such embodiments, the camera&#39;s focal length and aspect ratio are unknown and remain to be estimated.  
         [0017]     In step  106 , the method  100  factors out frames or images having the same or similar principal points. Typically, frames or images that are close in time will have similar principal points. Hence, in some embodiments, the method  100  may be applied to each batch of N consecutive frames.  
         [0018]     In step  108 , the method  100  matches feature points across the frames that were factored out in step  104 . Feature points are distinctive points in an image, and the selection of feature points is influenced by this measure of distinctiveness. For example, corner points in a scene are distinctive and may thus function as feature points. In order to match these feature points across a number of frames, an image similarity measure is used (e.g., the feature points will look similar across all of the frames).  
         [0019]     Once feature points have been matched across the frames, the method  100  proceeds to step  110  and obtains a projective reconstruction with projection matrices P i , i=1, . . . , n. In one embodiment, the projective reconstruction is obtained in accordance with an iterative factorization algorithm, such as that described by S. Mahamud and M, Herbert in “Iterative Projective Reconstruction from Multiple Views”, Proc. IEEE Computer Vision and Pattern Recognition Conference, vol. II, 2000).  
         [0020]     In step  112 , the method  100  obtains a metric (or Euclidean) reconstruction from the projective reconstruction in accordance with semidefinite programming (e.g., an extension of linear programming in which non-negativity constraints are replaced by positive semidefinite constraints on matrix variables). Specifically, the method  100  applies a semidefinite programming framework to formulate an auto-calibration problem that recovers camera parameters (e.g., focal length, apect ratio, etc.) using rigidity constraints present in the 3D scene and certain simplifying assumptions. The metric reconstruction will yield the focal lengths (in pixels), α x   i  and α y   i , of each camera in the x and y directions, respectively. One embodiment of a method for applying semidefinite programming to obtain the metric reconstruction is discussed in further detail with respect to  FIG. 2 . The method  100  then terminates in step  114 .  
         [0021]     The application of semidefinite programming to the auto-calibration problem overcomes many drawbacks inherent in conventional techniques that attempt to solve using linear algorithms. For example, some known linear least squares (LLS) approaches do not enforce certain constraints or conditions that are necessary to ensure substantial accuracy of the solution. Experimental results have shown that the focal length estimates produced by the present invention, applying the semidefinite programming framework, are more accurate (e.g., produced lower rates of error) than those produced by applying a linear programming framework. Moreover, the present invention can, using the semidefinite programming framework, incorporate a large number of views more easily than conventional methods can.  
         [0022]      FIG. 2  is a flow diagram illustrating one embodiment of a method  200  for obtaining a metric reconstruction from a projective reconstruction using semidefinite programming, according to the present invention. In particular, the method  200  formulates an auto-calibration problem as a constrained norm minimization problem and solves in accordance with semidefinite programming to obtain a corresponding metric reconstruction.  
         [0023]     The method  200  is initialized in step  202  and proceeds to step  204 , where the method  200  obtains the DIAC, Ω* i , associated with the camera in accordance with auto-calibration techniques. The DIAC, Ω* i , is the dual of the absolute conic (IAC), which is a calibration object that is always present but can only be observed through constraints on the intrinsic parameters, K i , of the camera.  
         [0024]     The basic projection equation for a camera with a projection matrix of P i =[A i  a i ] may be given as: 
 
 x   j   −P   i   X   j   (EQN. 1) 
 
 where X j  is the homogeneous coordinate of a 3D point, x j  is the projection of the 3D point in the image of the 3D scene, and A i  and a i  contain the intrinsic and extrinsic camera parameters, respectively. The projection matrix P i  contains information about the pose of the camera and its intrinsic parameters, K i , represented by the matrix:  
               K   i     =     [           α   x         s         x   0             0         α   y           y   0             0       0       1         ]             (     EQN   .           ⁢   2     )             
 
 where, as stated above, α x  and α y  are the camera&#39;s focal lengths (in pixels) in the x and y directions, respectively; s is the camera skew; and x 0  and y 0  are the principal points of the camera. 
 
         [0025]     As discussed above, the absolute conic is an imaginary conic closely tied to the intrinsic parameters, K i , of the camera. The absolute conic&#39;s dual, Ω* i  (the DIAC), is represented by: 
 
Ω* i   =K   i   K   it   (EQN. 3) 
 
 where K it  is the transpose of K i . The matrix Ω* i  is symmetric and positive semidefinite (denoted as Ω* i ≧0). If the skew of the camera is zero (s=0), then the DIAC, Ω* i , can be written compactly as:  
                 ω     *   i       =       F   0     +       α   x   2     ⁢     F   1       +       α   y   2     ⁢     F   2           ⁢     
     ⁢   where           (     EQN   .           ⁢   4     )                 F   0     =     [           x   0   2             x   0     ⁢     y   0             x   0                 x   0     ⁢     y   0             y   0   2           y   0               x   0           y   0         1         ]             (     EQN   .           ⁢   5     )                   F   1     =     [         1       0       0           0       0       0           0       0       0         ]       ⁢     
     ⁢   and           (     EQN   .           ⁢   6     )                 F   2     =     [         0       0       0           0       1       0           0       0       0         ]             (     EQN   .           ⁢   7     )             
 
         [0026]     The goal of auto-calibration is to recover the DIAC, Ω* i , by exploiting the rigidity constraints present in the 3D scene depicted in the image(s).  
         [0027]     In one embodiment, the DIAC, Ω* i  may be solved for simultaneously with the plane at infinity, π∞, by equivalent formulation using the absolute quadric, Q ∞ , an imaginary degenerate quadric represented by a 4×4 matrix of rank three. Given n cameras, the unknown parameters (the DIAC, Ω* i  and the plane at infinity, π∞ may be related to the known entries of the projection matrices P i , i=1, . . . , n according to the basic equation for auto-calibration for the i th  image:  
                   κ   i     ⁢     ω     *   i         =         (       A   i     -       a   i     ⁢     π   ∞   t         )     ⁢         ω     *   1       ⁡     (       A   i     -       a   i     ⁢     π   ∞   t         )       T       =       P   i     ⁢     Q   ∞   *     ⁢     P     i   ⁢           ⁢   T             ⁢     
     ⁢       i   =   2     ,   …   ⁢           ,   n     ⁢     
     ⁢   and           (     EQN   .           ⁢   8     )                 Q   ∞   t     =     [           ω     *   i               -     ω     *   i         ⁢     π   ∞                   -     π   ∞       ⁢     ω     *   i                 π   ∞     ⁢     ω     *   1       ⁢     π   ∞             ]             (     EQN   .           ⁢   9     )             
 
 where κ i  is an unknown scale factor. Since Ω* i  is positive semidefinite (Ω* i ≧0), it is easy to ascertain that the right-hand side (RHS) of the equation is semidefinite positive and κ i ≧0. In accordance with the equation above, constraints on the scale factor, κ i , are translated into constraints on the DIAC, Ω* i , which in turn gives an equation relating Ω* i  and π∞. Given enough such constraints, it is possible to solve for the unknown parameters (the DIAC, Ω* i , and the plane at infinity, π∞). 
 
         [0028]     For example, for a skewless camera (s=0) having a known principal point (x 0 , y 0 ), the constraints become linear and can be solved for using linear least squares (LLS).  
         [0029]     Substituting the expression for Ω* i  given by EQN. 4 into the basic equation for auto-calibration for the i th  image (EQN. 8) yields: 
 
κ i ( F   0 +α x   i2   F   1 +α y   i2   F   2 )=( A   i   −a   i π ∞   t ( F   0 +α x   2   F   1 +α y   2   F   2 )( A   i   −a   i π ∞   t ) T   (EQN. 10) 
 
         [0030]     In one embodiment, π ∞   t =(n 1 , n 2 , n 3 ) and e 1 , e 2 , e 3  are the three standard basis vectors for the group of 3×3 matrices (i.e., e 1   t =(1 0 0), etc.). If γ 7   i =κ i , γ 8   i =κ i α x   i2  and γ 9   i =κ i α y   i2 , then the left-hand side (LHS) of EQN. 8 can be written as:  
               LHS   i     =       ∑     j   =   0     2     ⁢       γ     7   +   j     i     ⁢     F   j                 (     EQN   .           ⁢   11     )             
 
         [0031]     After multiplying the terms, the right-hand side (RHS) of EQN. 8 can be written as an affine combination of seven symmetric matrices, G 0   i , . . . , G 6   i , as follows: 
 
 A   i   F   0   A   iT +α x   2   A   i   F   1   A   iT +α y   2   A   i   F   2   A   iT   +RHS   i =α x   2   n   1 ( A   i   e   1   a   iT   +a   i   e   1   T   A   iT )+α y   2   n   1 ( A   i   e   2   a   iT   +a   i   e   2   T   A   iT )+ n   3 ( A   i   e   3   a   iT   +a   i   e   3   T   A   iT )+( n   3   2   +a   x   2   n   1   2   +a   y   2   n   2   2 ) a   i   a   iT   (EQN. 12) 
 
         [0032]     Let γ 1 =α x   2 , γ 2 =α y   2 , γ 3 =α x   2   n   1 , γ 4 =α y   2   n   2 , γ 5 =n 3  and γ 6 =n 3   2 +α x   2 n 1   2 +α y   2 n 2   2 . Then, the expression above (EQN. 12) becomes:  
               RHS   i     =       G   0   i     +       ∑     j   =   1     6     ⁢       γ   j     ⁢     G   j   i                   (     EQN   .           ⁢   13     )             
 
         [0033]     The auto-calibration problem can thus be cast as a minimization of the sum of the norm of n−1 matrices, subject to certain semidefinite programming constraints, as:  
             minimize   ⁢           ⁢       ∑     i   =   2     n     ⁢            LHS   i     -     RHS   i                      (     EQN   .           ⁢   14     )             
 
         [0034]     Because of the parameterization being used, the rank constraint for the absolute quadric Q* ∞  is automatically enforced. It is also relatively simple to add the constraint that the DIAC, Ω* i , is positive semidefinite, such that EQN. 14 is subject to the following: 
 
 F   0 +γ 1   F   1 +γ 2   F   2 ≧0  (EQN. 15) 
 
γ 7   i   F   0 +γ 8   i   F   1 +γ 9   i   F   2 0i=2, . . . , n  (EQN. 16) 
 
         [0035]     The expressions for γ 1 , γ 2  and γ 6  imply that these variables are non-negative. Similarly, γ 7   i , γ 8   i  and γ 9   i  are also non-negative. Thus, the constraints of EQNS. 15 and 16 can be replaced by: 
 
diag(γ 1 , γ 2 , γ 6 , γ 7   2 , . . . , γ 7   n , γ 8   2 , . . . , γ 8   2 , γ 9   n )≧0  (EQN. 17) 
 
 which is a block diagonal matrix with diagonal entries γ 1 , γ 2 , γ 6 , γ 7   2 , γ 7   n , γ 8   2 , . . . , γ 8   n , γ 9   2 , . . . , γ 9   n . 
 
         [0036]     Applying these constraints in conjunction with the norm minimization of the sum yields a constrained norm minimization problem in which the variables are γ 1 , . . . , γ 6 , γ 7 , γ 8   i , γ 9   i  for i=2, . . . , n and the semidefinite programming (SDP) constraints in the norm minimization problem correspond to the equations above (i.e., EQNS. 15, 16 and 17). Therefore, the problem becomes a standard norm minimization problem that can be solved using a standard SDP solver to obtain the variables γ 1 , . . . , γ 6 , γ 7   i , γ 8   i , γ 9   i . In one embodiment, the problem is solved in accordance with a C library of routines for semidefinite programming (CSDP).  
         [0037]     Referring back to  FIG. 2 , once the DIAC, Ω* i , has been obtained, the method  200  recovers the intrinsic parameters, K i , of the camera from the DIAC, Ω* i  in step  206 . In one embodiment, the intrinsic parameters, K i , are obtained from the DIAC by Cholesky factorization, thereby updating the projective structure to a metric structure.  
         [0038]     In step  208 , the method  200  then recovers the focal lengths α x  and α y  from the intrinsic parameters matrix, K i . The variables γ 1 , . . . , γ 6 , γ 7   i , γ 8   i , γ 9   i  are directly related to focal length (as indicated by the expressions given above for the variables), and thus the focal lengths α x  and α y  can be obtained once these variables are known. For example, α x =√{square root over (γ 1 )} and α y =√{square root over (γ 2 )}. In addition, the aspect ratio is recovered as α x /α y .  
         [0039]      FIG. 3  is a high level block diagram of the present method for focal length determination that is implemented using a general purpose computing device  300 . In one embodiment, a general purpose computing device  300  comprises a processor  302 , a memory  304 , a focal length determination module  305  and various input/output (I/O) devices  306  such as a display, a keyboard, a mouse, a modem, and the like. In one embodiment, at least one I/O device is a storage device (e.g., a disk drive, an optical disk drive, a floppy disk drive). It should be understood that the focal length determination module  305  can be implemented as a physical device or subsystem that is coupled to a processor through a communication channel.  
         [0040]     Alternatively, the focal length determination module  305  can be represented by one or more software applications (or even a combination of software and hardware, e.g., using Application Specific Integrated Circuits (ASIC)), where the software is loaded from a storage medium (e.g., I/O devices  306 ) and operated by the processor  302  in the memory  304  of the general purpose computing device  300 . Thus, in one embodiment, the focal length determination module  305  for determining camera focal length described herein with reference to the preceding Figures can be stored on a computer readable medium or carrier (e.g., RAM, magnetic or optical drive or diskette, and the like).  
         [0041]     Thus, the present invention represents a significant advancement in the field of computer vision. The present invention provides improved focal length estimates (e.g., having lower rates of error) compared to those produced by applying conventional methods for recovering focal length. Moreover, the present invention can, using the semidefinite programming framework, incorporate a large number of views more easily than conventional methods can.  
         [0042]     Although various embodiments which incorporate the teachings of the present invention have been shown and described in detail herein, those skilled in the art can readily devise many other varied embodiments that still incorporate these teachings.