3D scanning using shadows

[0001] This application claims the benefit of the U.S. Provisional Applications Nos. 60/169,103, filed Dec. 6, 1999; 60/169,102, filed Dec. 6, 1999; and 60/183,172, filed on Feb. 17, 2000.

[0002] U.S. Government may have certain rights in this invention pursuant to National Science Foundation, contract Agreement No. EEC-9402726.

[0003] Three-dimensional scanning has recently become popular. However, many of the scanners used for such scanning trade-off between cost of acquisition and/or use, accuracy, ease-of-use and/or speed of acquisitions. Many commercial 3-D scanners emphasize the accuracy over all other parameters.

[0004] Scanners such as the Cyberware scanner may use an active illumination system in a fixed installation with controlled lighting. The object is transported using a motorized transport system. This can significantly increase the cost of the system. Moreover, this can make the system difficult to use in many installations, such as outdoors, where lighting may be difficult to control.

[0005] The present application teaches a system which allows scanning of 3D objects using shadow imaging.

[0006] In an embodiment, the system requires only a computer and a camera. The computer may be programmed to image shadows, and determine three dimensional information of an object from the imaged shadows.

[0024] The present application describes capturing three-dimensional surfaces using a simplified system. In one embodiment, the lighting can be “weakly structured”, i.e, any light source can be used.

[0025] The general principle is shown in FIG. 1. The scene to be imaged 100 is shown with a shadow 105 on the scene. The shadow 105 is produced by an edge, e.g. a straight edge such as a pencil or a stick, and is caused to move across the scene 100. The human operator produces the movement.

[0026] A camera 110 monitors the image of the scene including the shadows, and produces an output which is sent to a processor 120. The processor estimates the three-dimensional shape of the scene from the sequence of images of the shadow as deformed by three-dimensional elements of the scene. The processing operates to extract scene depth at least at a plurality of pixels in the image, more preferably at every pixel in the image. It should be understood, however, that the pixels could be of any size.

[0027] More detail about the acquisition, including the geometry of the acquisition, is shown in FIG. 2. A light source, shown approximated as point source 200, illuminates the scene 199. The intersection of the point source and the leading edge of the pencil define a plane Λ(t), at each time instant. Therefore, the boundary of the pencil's shadow on the scene comprises the intersection between the plane Λ(t), and the surface of the object.

[0028] In FIG. 2, the plane Π_h represents the horizontal plane, and the plane Π_v represents a vertical plane orthogonal to Π_h. This vertical plane is optional. In the FIG. 1 setup for example, the plane ΠV is removed. The position of the plane Π_h in the camera reference plane will be known from calibration as explained further herein. The position of Π_v is also inferred from a projection Λ_I at the intersection line between Π_h and Π_v.

[0029] The end goal is to obtain three-dimensional coordinates of each point P in the three-dimensional scene. This may be done one pixel at a time. The three-dimensional location of the point P in space will be estimated corresponding to every pixel p at coordinates x_c in the image obtained by the camera. Effectively, the user projects a succession of N shadows on the scene, thereby generating N shadow edges ξ_I, where I=1 . . . N. The points on this edge are estimated through triangulation, as described herein.

[0030] The shadow time t is defined as the time when the shadow boundary passes by a given pixel along a line x_c. Π_t represents the corresponding shadow plane at that time t. The leading edge of the shadow is represented by the value Λ.

[0031] The projection of Λ on the image plane λ is obtained by the camera at 305. This is done by a temporal processing operation of estimating the shadow time t_s(x_c) at each pixel x_c. This temporal processing is followed by a spatial processing, in which the projection of Λ that is seen by the camera is represented by values λ. Therefore, the two portions of the shadow projected on the two planes Π_h and Π_v are visible on the image as the lines λ_h and λ_v. After extracting these two lines, the location in space of the two corresponding lines Λ_h and Λ_v are obtained at 310. This can be done by forming a plane between the camera and the λ lines. In FIG. 2, the camera origin is shown as 0_c. A plane between 0_c and the λ is can be obtained. These planes (0_c, λ(t), and (O_c, λ(t)) are intersected with the image planes Π_h and Π_v respectively. The shadow plane Π_t is then found at 315. If the vertical plane has been used for scanning, then the shadow plane is the plane defined by the two non collinear lines Λ_h and Λ_v at 315. If the vertical plane has not been used for scanning, however, the shadow plane may still be inferred from the only available line λ_H and the position of the point light source S. in this latter case, point light source needs to be at a known and fixed location in space.

[0032] At 320, the actual point P corresponding to the pixel x_c is retrieved by triangulating Π of T with the optical ray O_c from the camera.

[0033] If the light source S is at a known location in space, then the shadow plane Π(t) may be directly inferred from the point S and the line Λ_h. Consequently, no calculation of the additional plane Π(t) is not required. Therefore, two different embodiments are contemplated: a first having two calibrated planes (Π_hand Π_v) and an uncalibrated light source, and the second having one calibrated plane and a calibrated light source.

Camera Calibration

[0034] Camera calibration can be used to recover the location of the ground plane Π_h and the intrinsic camera parameters. The intrinsic camera parameters may include focal length, principal point, and radial distortion factor. A first embodiment of the calibration technique herein uses a planar checkerboard pattern. FIGS. 4A and 4B show the setup which includes a planar checkerboard pattern 400 placed on the imaging area, e.g., the ground or table surface, in a general location of the objects to be scanned. The camera 402 is pointed at this general area. The camera 402 captures an image shown in FIG. 4B. This image is used to infer the intrinsic and extrinsic parameters of the camera.

[0035] The projections on the image planes of the known grid corners are matched to the expected projection that is directly on the image. This is described in more detail in Tsai “A Versatile Camera Calibration Technique for High Accuracy 3-D Machine Vision Metrology using off-the-shelf TV cameras and Lenses”. A first order symmetric radial distortion model is used for the lens. When this technique is used with a single image, the principal point, that is the intersection of the optical axis with the image plane, cannot be easily recovered. This principal point is therefore assumed to be identical with the image center. A full camera model may be used which integrates multiple images of the planar grid at different locations in space with different orientations, e.g., using three or four images.

[0036] It has been found that the quality of reconstruction is relatively insensitive to errors in the principal point position. Therefore, either of the calibration techniques can be used.

[0037] As described above, when a single reference plane, e.g. Π_h, is used for scanning, the location of the light source must be known in order to infer the shadow plane location Π_t. Another embodiment allows calibration in the light source using an item, e.g. a pencil or a stake of known length. The operation and geometric theory is shown in FIGS. 6A–6C. In FIG. 6A, the pencil is shown standing on the reference plane Π_h. The camera 605 observes the shadow of the pencil 610 as projected on the ground plane. The acquired image is shown in FIG. 6B. Two points: b and t_s are found in this acquired image, as shown in FIG. 6B.

[0038] FIG. 6C shows a geometrical diagram. The points b and t_s can be triangulated to obtain the position in space of pencil points B and T using the known the height of the pencil H. Effectively, the coordinates of the pencil tip T can be directly inferred from B. As shown, this is done by intersecting optical rays (0c, b) and (0c, t_s) with the Π_h that is known from camera calibration. The point light source S therefore must lie in the plane Δ=(T, T_s) in space. This by itself yields a first linear constraint on the position of the light source.

[0039] By taking a second view, with the pencil at different locations on the plane, a second independent constraint with another line Λ prime can be obtained. A closed form solution for the 3-D coordinates of S may then be derived by intersecting the two lines Λ and Λ prime using a least squared combination.

[0040] Two views may provide sufficient information. However since the problem is linear, the estimation can be made more accurate by obtaining more than two views.

[0041] Operation 305 in FIG. 3 requires determining lines of intersection between the shadow plane Π of T. and the two planes Π of h and Π of v. This may be done by the spatial processing of localizing edges of the shadow that are directly projected onto orthogonal planes at each discrete time t to form the set of all shadow planes Π of T. Temporal processing also, and also estimating the time t_s as the shadow time, where the edge of the shadow passes through any given pixel x_c=x_c, y_c in the image.

[0042] These processing tasks allow finding the edge of the shadow. However, the search domains for the spatial and temporal processing tasks may be different. The spatial task operates on the spatial coordinates or image coordinate system, while the temporal task operates on the temporal coordinates system. One aspect of the present system enables making the two search procedures more compatible so that at any time to when the shadow passes through a pixel x_c, the two searches still find the exact same point (x, y, t0) in space-time.

[0043] A technique is described herein called spatio-temporal thresholding. This thresholding is based on the observation that, as the shadow is scanned across the scene, each pixel x,y sees its brightness intensity going from an initial maximum value Imax down to a minimum value I_min. The pixel then returns to its initial value as the shadow goes away. This profile is characteristic even when there is a non-neglible amount of internal reflections in the scene.

[0044] For any given pixel {overscore (x)}_c=(x,y), define I_min(x,y) and I_max(x,y) as its minimum and maximum brightness throughout the entire sequence:

[0045] $\{\begin{array}{c}{I}_{\min }\left(x,y\right)\stackrel{.}{=}\underset{t}{\min }\left\{I\left(x,y,t\right)\right\}\\ I_{\max }\left(x,y\right)\stackrel{.}{=}\underset{t}{\max }\left\{I\left(x,y,t\right)\right\}\end{array}\hspace{1em}$

[0046] The shadow is defined as to be the locations (in space-time) where the image I(x,y,t) intersects with the threshold image I_shadow(x,y); defined as the mean value between I_max(x,y) and I_min(x,y):

[0047] $I_{\mathrm{shadow}}\left(x,y\right)\stackrel{.}{=}\frac{1}{2}\left(I_{\max }\left(x,y\right)+I_{\min }\left(x,y\right)\right)$

[0048] This may be also regarded as the zero crossings of the difference image ΔI(x,y,t) defined as follows:
ΔI(x,y,t)≐I(x,y,t)−I_shadow(x,y)

[0049] The concept of dual space may assist in certain calculations.

Shadow Plane Estimation Π(t)

[0050] Denote by {overscore (ω)}(t), {overscore (λ)}_v(t) and {overscore (λ)}_v(t) the coordinate vectors of the shadow plane Π(t) and of the shadow edges λ_h(t) and λ_v(t) at time t. Since λ_h(t) is the projection of the line of intersection Λ_h(t) between Π(t) and Π_h, then (t) lies on the line passing through {overscore (ω)}_h with direction {overscore (λ)}_h(t) in dual-space (from proposition 1 of section 2.2.2). That line, denoted Λ_h(t), is the dual image of Λ_h(t) in dual-space as described above (see section 2.2.2). Similarly, {overscore (ω)}(t) lies on the line Λ_v(t) passing through {overscore (ω)}_v with direction {overscore (λ)}_v(t) (dual image of Λ_v(t)). Therefore, in dual-space, the coordinate vector of the shadow plane {overscore (ω)}(t) is at the intersection between the two known lines Λ_h(t) and Λ_v(t). In the presence of noise, these two lines might not exactly intersect (equivalently, the 3 lines λ_i, λ_h(t) and λ_v(t) do not necessarily intersect at one point on the image plane, or their coordinate vectors {overscore (λ)}_i, {overscore (λ)}_h(t) and {overscore (λ)}_v(t) are not coplanar). However, one may still identify {overscore (ω)}(t) with the point that is closest to the lines in the least-squares sense. The complete derivations for intersecting a set of lines in space may be found in section 4.1.2. When interesting the two lines Λ_h(t) and Λ_v(t) in space, the solution reduces to:

[0051] $\stackrel{\_}{\omega }\left(t\right)=\frac{1}{2}\left(\stackrel{\_}{{\omega }_1}\left(t\right)+\stackrel{\_}{{\omega }_2}\left(t\right)\right),\mathrm{with}$ ${\varpi }_1\left(t\right)\stackrel{.}{=}{\varpi }_h+{\alpha }_h\stackrel{\_}{{\lambda }_h}\left(t\right)$ ${\varpi }_2\left(t\right)\stackrel{.}{=}{\varpi }_v+{\alpha }_v\stackrel{\_}{{\lambda }_v}\left(t\right)$ $\mathrm{where}\left[\begin{array}{c}{\alpha }_h\\ {\alpha }_v\end{array}\right]=A^{-1}b$
where A is a 2×2 matrix and b is a 2-vector defined as follows (for clarity, the variable t is omitted):

[0052] $A\stackrel{.}{=}\left[\begin{array}{cc}\text{<}{\stackrel{\_}{\lambda }}_h,{\stackrel{\_}{\lambda }}_h\text{>}& -\text{<}{\stackrel{\_}{\lambda }}_h,{\stackrel{\_}{\lambda }}_v\text{>}\\ -\text{<}{\stackrel{\_}{\lambda }}_h,{\stackrel{\_}{\lambda }}_v>& <{\stackrel{\_}{\lambda }}_v,{\stackrel{\_}{\lambda }}_v\text{>}\end{array}\right],b\stackrel{.}{=}\left[\begin{array}{c}\text{<}{\stackrel{\_}{\lambda }}_h,{\varpi }_v-{\varpi }_h\text{>}\\ \text{<}{\stackrel{\_}{\lambda }}_v,{\varpi }_h-{\varpi }_v\text{>}\end{array}\right]$

[0053] Note that the two vectors {overscore (ω)}₁(t) and {overscore (ω)}₂(2) are the orthogonal projections, in dual-space, of {overscore (ω)}(t) onto Λ_h(t) and Λ_v(t) respectively. The norm of the difference between these two vectors may be used as an estimate of the error in recovering Π(t). If the two edges λ_h(t) and λ_v(t) are estimated with different reliabilities, a weighted least square method may still be used.

[0054] Using the additional vertical plane Π_v enables extracting the shadow plane location without requiring the knowledge of the light source position. Consequently, the light source is allowed to move during the scan. This may allow use of natural light, e.g. the sun, for example.

[0055] When the light source is of fixed and known location in space, the plane Π_v is not required. Then, one may directly infer the shadow plane position from the line λ_h(t) and from the light source position S:
{overscore (ω)}(t)={overscore (ω)}_h+{overscore (λ)}_h(t)
where

[0056] $\begin{array}{cc}S\in \Pi \left(t\right)\iff \text{<}\varpi \left(t\right),{\stackrel{\_}{X}}_s\text{>}=1\iff {\alpha }_h=\frac{1-\text{<}{\varpi }_h,{\stackrel{\_}{X}}_s\text{>}}{\text{<}{\stackrel{\_}{\lambda }}_h\left(t\right),{\stackrel{\_}{X}}_s\text{>}}& \left(6.10\right)\end{array}$
where {overscore (X)}_s=[X_s Y_s Y_s]^T is the coordinate vector of the light source S in the camera reference frame. In dual-space geometry, this corresponds to the intersecting the line Λ_h(t) with plane Ŝ, dual image of the source point S. Notice that <{overscore (λ)}_h(t), {overscore (X)}_s>=0 corresponds to the case where the shadow plane contains the camera center projection O_c. This is singular configuration that may make the triangulation fail (∥{overscore (ω)}(t)∥→∞). This approach requires an additional step of estimating the position of S using light source calibration. This reconstruction method was used in experiments 2 and 3.

[0057] The quantity 1−<{overscore (ω)}_h, {overscore (X)}_s> reduces to h_s/d_h where h_s and d_h are the orthogonal distances of the light source S and the camera center O_c to the plane Π_h.

[0058] Since {overscore (ω)}_h is the coordinate vector of plane Π_h, the vector {overscore (n)}_h=d_h{overscore (ω)}_h is the normal vector of the plane Π_h in the camera reference frame. Let P be a point in Euclidean space (E) of coordinate vector {overscore (X)}. The quantity d_h−<{overscore (n)}_h, {overscore (X)}> is then the (algebraic) orthogonal distance of P to Π_h (positive quantity if the point P is on the side of the camera, negative otherwise). In particular, if P lies on Π_h, then <{overscore (n)}_h,{overscore (X)}>=d_h, which is equivalent to <{overscore (ω)}_h, {overscore (X)}>=1. The orthogonal distance of the light source S to Π_h is denoted h_s. Therefore h_s=d_h−<{overscore (n)}_h, {overscore (X)}>, or equivalently 1−<{overscore (ω)}_h, {overscore (X)}_s>=h_s/d_h.

[0059] According to that claim, the constant a_h of equation 6.10 may be written as:

[0060] ${\alpha }_h=\frac{h_s/d_h}{\text{<}{\stackrel{\_}{\lambda }}_h\left(t\right),{\stackrel{\_}{X}}_s\text{>}}=\frac{1/d_h}{\text{<}{\stackrel{\_}{\lambda }}_h\left(t\right),{\stackrel{\_}{X}}_s/h_s\text{>}}$

[0061] This expression highlights the fact that the algebra naturally generalizes to cases the light source is located at infinity (and calibrated). Indeed, in those cases, the ratio {overscore (X)}_s/h_s reduces to {overscore (d)}_s/sin φ where {overscore (d)}_s is the normalized light source direction vector (in the camera reference frame) and φ the elevation angle of the light source with respect to the Π_h. In dual-space, the construction of the shadow plane vector {overscore (ω)}(t) remains the same: it is still at the intersection of Λ_h(t) with Ŝ. The only difference is that the dual image Ŝ is a plane crossing the origin in dual-space. The surface normal of that plane is simply the vector {overscore (d)}_s.

Triangulation

[0062] Once the shadow time t_s({overscore (x)}_c) is estimated at a given pixel {overscore (x)}_c=[x_c y_c 1]^T (in homogeneous coordinates), the corresponding shadow plane Π(t_s({overscore (x)}_c)) is identified (its coordinate vector {overscore (ω)}_c≐{overscore (ω)}(t_s({overscore (x)}_c))) by triangulation at 320. The point P in space associated to {overscore (x)}_c is then retrieved by intersecting Π(t_s({overscore (x)}_c)) with the optical ray (0_c, {overscore (x)}_c):

[0063] $Z_c=\frac{1}{\text{<}{\stackrel{\_}{\omega }}_c,{\stackrel{\_}{x}}_c\text{>}}\Rightarrow {\stackrel{\_}{X}}_c=Z_c\stackrel{\_}{x_c=\frac{{\stackrel{\_}{x}}_c}{\text{<}{\stackrel{\_}{\omega }}_c,{\stackrel{\_}{x}}_c\text{>}}},$
If {overscore (X)}_c=[X_c Y_c Z_c]^T is defined as the coordinate vector of P in the camera reference frame.

[0064] Notice that the shadow time t_s({overscore (x)}_c) acts as an index to the shadow plane list Π(t). Since t_s({overscore (x)}_c) is estimate at sub-frame accuracy, the plane Π(t_s({overscore (x)}_c)) (actually it coordinate vector {overscore (ω)}_c) results from linear interpolation between the two planes Π(t₀−1) and Π(t₀) if t₀−1<t_s({overscore (x)}_c)<t₀ and t₀ integer:
{overscore (ω)}_c=Δt{overscore (ω)}(t₀−1)+(1−Δt){overscore (ω)}(t₀),
where Δt=t₀−t_s({overscore (x)}_c), 0≦Δt<1.

[0065] Pixels corresponding to occluded regions in the same cannot provide substantive information. Therefore, only pixels that have a contrast value larger than a predetermined threshold are used. In the experiments giving herein, where intensity values are encoded between zero and 255, this threshold may be 30. The threshold may also be proportional to the level of noise in the image.

[0066] Once the shadow time is estimated at any given pixel, the shadow plane can be triangulated from its coordinate vector. The point in space (P) associated to the given pixel is then retrieved by intersecting the shadow plane with this optical ray. This is shown in FIG. 2. More specifically,

[0067] $Z_c=\frac{1}{\langle {\stackrel{\_}{\omega }}_c,{\stackrel{\_}{x}}_c\rangle }\Rightarrow {\stackrel{\_}{X}}_c=Z_c{\stackrel{\_}{x}}_c=\frac{{\stackrel{\_}{x}}_c}{\langle {\stackrel{\_}{\omega }}_c,{\stackrel{\_}{x}}_c\rangle },$
the shadow time therefore ask as an index to the shadow plane list. This effectively provides range data to the actual object.

[0068] The recovered range data is used to form a mesh by connecting neighborhood points in triangles. Connectivity is directly given by the image. Two vertices become neighbors if their corresponding pixels are neighbors in the image. Moreover, since each vertex corresponds to a unique pixel, the texture mapping can be relatively easily carried out.

[0069] FIG. 7 shows the global geometrical principal of the reconstruction technique in normal Euclidean space (left) and “dual space” (right). This Figure shows the correspondence between Euclidean space and dual space for objects, e.g. lines and points on the image plane, as well as objects in 3-D which include planes, lines and points in space.

[0070] Observe that the calibration of the vertical plane Π_v is also illustrated in the dual-space diagram: its coordinate vector {overscore (ω)}_v is at the intersection of the Λ_i and the set of plane vectors orthogonal to {overscore (ω)}_h (defining a plane in dual-space). The line Λ_i is at the intersection of the two planes Π_h and Π_v, and it dual image Λ_i is uniquely defined by the horizontal plane vector {overscore (ω)}_h and the vector {overscore (λ)}_i, coordinate vector of the line λ_i observed on the image plane. This calibration process is described above.

[0071] Once {overscore (ω)}_v is known, the shadow plane vector {overscore (ω)}(t) associated to the shadow edge configuration at time t is at the intersection between the two lines Λ_h(t) and Λ_v(t), dual images of Λ_h (t) and Λ_v(t). Those two dual lines are defined by the two reference plane vectors {overscore (ω)}_h and {overscore (ω)}_v and the direction vectors {overscore (λ)}_h(t) and {overscore (λ)}_v(t) (vector coordinate of the two image lines λ_h(t) and λ_v(t)). This processing step is described in detail.

[0072] The final step consisting of identifying the point P in space by intersecting the optical ray (0_c, p) with the shadow plane Π is also illustrated on the dual-space diagram. In dual-space, that stage corresponds to finding the dual image of P that is the unique plane in dual-space containing the point {overscore (ω)}(t) (shadow plane vector) with orthogonal vector {overscore (x)}_c (homogeneous coordinate vector of the image point p).

[0073] An alternative embodiment uses a single reference plane (Π_h without Π_v) with a calibrated light source is summarized on FIG. 8. This technique uses a different procedure of estimating the shadow plane coordinate {overscore (ω)}(t). In that version, the vector {overscore (107 )}(t) is at the intersection of the dual line Λ_h(t) and the dual image of the light source Ŝ. The triangulation operation remains unchanged.

[0074] The point P in space is determined by intersecting the optical ray O_c, P with the shadow plane Π. This corresponds to finding the dual image of P that is the unique plane in dual space that contains the point including the shadow plane vector with the orthogonal vector. This is done by triangulation as described above.

[0075] The alternate setup uses a single reference plane with a calibrated light source as shown in FIG. 8. In the FIG. 8 setup, a different procedure is used to estimate the shadow plane coordinate vector.

[0076] The accuracy of this system is not necessarily increased by decreasing the scanning speed. However, the scanning speed must be sufficiently slow to allow each temporary pixel profile to be sufficiently sampled. A sharper shadow edge will require slower scanning so that the temporal profile at each pixel can be properly sampled. The reality, however, is that the speed of moving the shadow is really limited by the response speed of the image acquisition element.

[0077] In this system, range data can only be retrieved for pixels that correspond to regions in the scene that are illuminated by the light source and imaged by the camera. Better coverage of the scene may be obtained from multiple scans of the same scene keeping the light source at different locations each time and keeping the camera position fixed.

[0078] The previous system has described accurately characterizing 3-D surface based on projection of shadows on a known reference plane. Another embodiment describes operating without using a background plane as the reference plane, and instead using a calibrated light source.

[0079] A summary of the scanning scenario for a flat reference plane is shown in FIG. 9. In the first embodiment, the plane Π_d is used as a reference plane for scanning. The position of the light source S is known and the position of the plane Π_d is also known from calibration/setup.

[0080] A curved edge shadow ξ is projected on the image during scanning. All points in space P are estimated as the curved edge moves across the image, by estimating from the points p on ξ. Π denotes the corresponding shadow plane. The image 930 corresponds to that image which is seen by the camera. The corresponding points A and B in the scene may be found by intersecting Π_d with the optical rays (O_c, a) and (O_c, b) from the image. The shadow plane Π may then be inferred from the three points in space: S, A and B.

[0081] For a given position of the shadow, once the shadow plane Π is identified, the 3-D image of the entire shadow edge ξ can be determined by geometric triangulation using, among other things, the known position of the reference plane Π_d. This embodiment describes finding the 3D image, using a similar overall technique to that described above, but without knowing Π.

[0082] The extension to this embodiment takes into account a number of issues about the image. First, depth information at two distinct points on an edge propagates along the entire edge. Also, if depths Z of two distinct points a and b of this shadow edge ξ are known, then the depth at any other point in the image Z_P can also be found. Depth at two distinct points propagates over the whole image.

[0083] Let {overscore (x)}_A and {overscore (x)}_B be the homogeneous coordinate vectors of the two points α and b on the image plane {overscore (x)}_A=[x_A V_A 1]^T. Then if the two depths Z_A and Z_B are know, then so are the full coordinate vectors of the associated points A and B in the 3D scene: {overscore (X)}_A=Z_A{overscore (x)}_A and {overscore (X)}_B=Z_B{overscore (x)}_B. Therefore the associated shadow plane Π is the unique plane passing through the three points A, B and S. Once Π is recovered, any point p along the edge ε may be triangulated leading to Z_p.

[0084] The depths of two points a and b may be known if they lie on the known reference plane Π_d. Consequently, following Property 1, depth information at a and b propagate to every point p along the edge ε.

[0085] Depths can also propagate from edge to edge. This concept is used here to allow the depths to propagate over the entire image. According to the present embodiment, knowledge of the depth of three distinct points in the image can be used to recover the entire scene depth map. Hence, knowledge of these three distinct points can be used in place of knowledge of the reference plane Π_d.

[0086] A, b and c are defined as three distinct points in the scannable area of the image. For purposes of this explanation, it can be assumed their depths Z_a, Z_B and Z_c are known. By appropriate shadow scanning, the depth of any point p in the image can be obtained.

[0087] This can be demonstrated using a constructive example. A shadow edge ξ1 that goes through points a and B can be projected. A second shadow edge ξ2 can be projected through points a and c. This is shown in FIG. 10. The two points a and b on ε₁ are of known depth, and therefore the depth of every point along that edge can be similarly computed. Analogously, for ε₂, the depth of every point along that edge can be computed.

[0088] For every point p on the image, there can be an edge ξp that passes through p and intersects both ε₁ and ε₂ at distinct points P₁ and P₂ which points are each different than a. Since P₁ and P₂ each lie on the two known edges at ε₁ and ε₂, the depths of ξ1 and ξ₂ must also be known. Therefore, since two points on the shadow edge ε_p. are known, the depth of every point along ξ_p may also be computed. In particular, the depth of the point p can be computed as shown in FIG. 10. Moreover, if points between the edges intersect, then the depth information can propagate from edge to edge.

[0089] As stated above, this means that knowledge of the depth at three distinct points in the image becomes sufficient to recover the entire scene depth map. To propagate depth information from {a, b, c} to p uses intersecting points p1 and p2 of the shadow edges.

[0090] The system uses edges ξ. An edge ξ is an isolated edge if and only if it does not intersect with at least two other edges on the image. Depth information can not be propagated to any isolated edge from the rest of the edges. Isolated edges, therefore, can not be used in this system.

[0091] This embodiment follows the summary flowchart of FIG. 11, using the setup shown in more detail in FIG. 12. In FIG. 11, a number of summary operations are described, which are each described in further detail herein. The hardware of FIG. 12 shows a point source at S, and a straight edge producing element, e.g. a stick 1200 being shown in two different positions. Each different position projects a shadow onto the 3-D scene 12. A camera at 1220 receives a view of the image plane, and uses that view to reconstruct details of the 3-D image.

[0092] At 1110, a set of shadow images is obtained. The shadows are extracted, and their intersections are computed.

[0093] Let Π_i be the i^th shadow plane generated by the stick (i=1, . . . , N), with corresponding plane vector {overscore (ω)}_i=[w_xⁱ w_yⁱ w_zⁱ]^T (in dual space). For all vectors {overscore (ω)}_t to be well defined, it is required that none of the planes Π_I contain the camera center 0_c. Denote by ε_I the associated shadow edge observed on the image plane. The N vectors {overscore (ω)}_I constitute then the main unknowns in the reconstruction problem. Once those vectors are identified, all edges can be triangulated in space. Therefore, there is apparently a total of 3N unknown variables. However, given the scanning scenario, every shadow plane Π_i must contain the light source point S. Therefore, {overscore (X)}_s=[X_s Y_s Z_S]^T the light source coordinate vector in the camera reference frame (known), provides
∀i=1, . . . , N, <{overscore (ω)}_i,{overscore (X)}_S>=1
Equivalently, in dual-space, all shadow plane vectors {overscore (ω)}_i must lie on the plane Ŝ, dual-image on the light source point S. One may then explicitly use that constraint, and parameterize the vectors {overscore (ω)}_i using a two-coordinate vector ū_i=[u_xⁱ u_yⁱ]^T such that:
{overscore (ω)}_i=Wū_i+{overscore (ω)}₀=[{overscore (ω)}_s1 {overscore (ω)}_s2]ū_i+{overscore (ω)}₀
where {overscore (ω)}₀, {overscore (ω)}_s1, and {overscore (ω)}_s2 are three vectors defining the parameterization. For example, if X_S≠0, one may then keep the last two coordinates of {overscore (ω)}hd i as parameterization: ū_i=[w_yⁱ w_zⁱ]^T, picking {overscore (ω)}_s1=[−Y_S/X_S 1 0]^T, {overscore (ω)}_s2=[−Z_S/X_S 0 1]^T and {overscore (ω)}₀=[1/X_S 0 0]^T. Any other choice of linear parameterization is acceptable (there will always exist one give that is S≠0_c). In order to define a valid coordinate change, the three non-zero vectors {overscore (ω)}₀, {overscore (ω)}_s1, and {overscore (ω)}_s2 must only satisfy the three conditions (a) <{overscore (ω)}₀, {overscore (X)}_S>=1, (b) <{overscore (ω)}_s1, {overscore (X)}_S>=0, (c) {overscore (ω)}_s1≠{overscore (ω)}_s2. In dual-space, {{overscore (ω)}_s1, {overscore (ω)}_s2} (or W) may be interpreted as a basis vector of the plane Ŝ and {overscore (ω)}₀ as one particular point on that plane. FIG. 13 shows the coordinate transformation.

[0094] After that parameter reduction, the total number of unknown variables reduces to 2N: two coordinates u_xⁱ and u_yⁱ per shadow plane Π_i. Given that reduced plane vector parameterization (called ū-parameterization), global reconstruction can be carried out.

[0095] Intersecting points between the edges themselves depth information that propagates from edge to edge. These points provide geometrical constraints that may be extracted from the images. Therefore, a first operation may be carried out by studying the type of constraint provided by an elementary edge intersection.

[0096] Assume that the two edges ε_n and ε_m intersect at the point p_k on the image (n≠m), and let Π_n and Π_m be the two associated shadow planes with coordinate vectors {overscore (ω)}_n and {overscore (ω)}_m as shown in FIG. 12. Let {overscore (x)}_k be the homogeneous coordinate vector of p_k on the image plane, and Z_k the depth of the corresponding point P_k in the scene. The two edges ε_n and ε_m intersect in space at P_k if and only if the planes Π_n and Π_m and the scene surface intersect at a unique point in space (P_k). Equivalently, the depth Z_k may be computed by triangulation using either plane Π_n or Π_m. This condition translates into the two constraint equations Z_k=1/<{overscore (ω)}_n, {overscore (x)}_k>=1/<{overscore (ω)}_m, {overscore (x)}_k> in dual-space which can be rewritten as follows:
<{overscore (x)}_k,{overscore (ω)}_n−{overscore (ω)}_m>=0

[0097] This unique equation captures then all the information that is contained into an elementary edge intersection. There is a very intuitive geometrical interpretation of that equation: Let Λ_k be the line of intersection between the two planes Π_n and Π_m, in space, and let λ_k be the perspective projection of that line onto the image plane. Then, the vector {overscore (λ)}={overscore (ω)}_n−{overscore (ω)}_m is one coordinate vector of the line λ_k. Therefore, equation 7.3 is merely <{overscore (x)}_k, {overscore (λ)}_k>=0, which is equivalent to enforcing the point p_k to lie on λ_k (see FIG. 12). This equation has both advantages of (a) not explicitly involving Z_k (which may be computed afterwards from the shadow plane vectors) and (b) being linear in the plane vectors unknowns {overscore (ω)}_n and {overscore (ω)}_m. The same constraint may also be written as a function of ū_n and ū_m, the two ū-parameterization vectors of the shadow planes Π_n and Π_m:
<{overscore (y)}_K,ū_N−ū_m>=0
where {overscore (y)}_k=W^T{overscore (x)}_k (a 2-vector). Notice that this new equation remains linear and homogeneous in that reduced parameter space.

[0098] Let N_p be the total number of intersection points p_k (k=1, . . . , N_p) existing in the edge-web (the entire set of edges). Assume that a generic p_k lies at the intersection of the two edges ε_n(k) and ε_m(k) (n(k) and m(k) are the two different edge indices).

[0099] The total set of constraints associated to the N_p intersections may then be collected in the form of N_p linear equations:
∀k=1, . . . N_p, <{overscore (y)}_k,ū_m(k)−ū_n(k)>=0
which may also be written in a matrix form:
AŪ=0_Np
where 0_Np is a vector of N_p zeros, A is an N_p×2N matrix (function of the {overscore (y)}_k coordinate vectors only) and Ū is the vector of reduced plane coordinate (of length 2N):

[0100] $\stackrel{\_}{U}={[{\stackrel{\_}{u}}_1^T{\stackrel{\_}{u}}_2^T\dots ]}^T={[\begin{array}{cccc}{u}_x^1& u_y^1& u_x^2& u_y^2\dots \end{array}]}^T.$
The vector Ū={ū_i}_{i . . . N}.
According to this equation, the solution for the shadow plane vectors lies in the null space of the matrix A. The rank of that matrix or equivalently the dimension of its null space are identified at 1120, isolated edges and isolated group of edges are rejected. This forms an edge web which is fully connected, resulting in a set of an edges ξ_I and N_P intersection points p_K.

[0101] An edge-web is fully connected if and only if it cannot be partitioned into two groups of edges which have less that two (zero or one) points in common. In particular a fully connected edge-web does not contain any isolated edge. Notice that under the condition only, depth information can freely propagate though the entire web. A normal scanning scenario is then defined as a scenario where the edge-web is fully connected and the total number of intersections is larger than 2N (this last condition will be relaxed later on).

[0102] In a normal scanning scenario, the rank of the matrix A is exactly 2N-3 (or alternatively, the null space of A is of dimension 3).

[0103] This is because in a normal scanning scenario, the reconstruction problem has at most three parameters. Consequently the dimension of the null space of A is at most 3, or equivalently, A is of rank at least 2N-3 in fact, usually exactly 2N-3. At 1130, a unitary seed vector U₀ is calculated. The scene factor is calculated using singular value decomposition or SVD.

[0104] For every solution vector Ū={ū_i} to the equation, there exists three scalars α, β and λ such that:
∀i=1, . . . , N, ū_i=yū_i⁰+ū₀
which are also obtained at 1130 with ū₀=[α β]^T. Conversely, for any scalars α, β and ç, the vector Ū={ū_i} given by the equation is solution of a linear system. The vector Ū⁰ is called a “seed” solution from which all solutions of the linear system may be identified.

[0105] Any non-trivial solution vector Ū⁰={ū_i⁰} may be used as seed as long as it is one solution of the equation the solution vector (called the unitary seed vector) that satisfies the two extra normalizing conditions: (a)

[0106] $\begin{array}{cc}\sum _{i=1}^N{\stackrel{\_}{u}}_i^0=0\left(\mathrm{zero}\mathrm{mean}\right),& \end{array}$
(b)

[0107] $\sum _{i=1}^N{{\stackrel{\_}{u}}_i^0}^2=1$
(unit norm) may be used. Those conditions assure a non trivial solution meaning that all ū_I cannot be identical. The unitary seed vector Ū⁰ satisfies the linear equation BŪ⁰=o_n2-0, where b is the following augmented (N_p−2)×2N matrix:

[0108] $B=\left[\begin{array}{c}A\\ 1010\dots 10\\ 0101\dots 01\end{array}\right]$

[0109] The last two rows of B enforce the zero-mean constraint, bringing the rank of B to 2N−1 (=(2N−3)+2). Therefore, the dimension of null space of B is one, leading to Ū⁰ being the unitary eigenvector associated to the unique zero eigenvalue of B. Consequently, a standard singular value decomposition (SVD) of B allows to naturally retrieve Ū⁰. Such a decomposition leads to the following relation:
B=U S V^T
where U and V=[V₁ V₂ . . . V_2N] are two unitary matrices of respective sizes (N_p+2)×(N_p+2) and 2N×2N, and S is the (N_p+2)×2N matrix of singular values. The unitary seed vector Ū⁰ is then the column vector of V associated to the zero singular value. Without loss of generality, assume it is the last column vector: Ū⁰={ū_i⁰}=V_2N. Alternatively, one may retrieve the same V matrix by applying the same decomposition on the smaller 2N×2N symmetric matrix C=B^TB. Such a matrix substitution is advantageous because the so-defined matrix, C, has a simple block structure:

[0110] $C=\left[\begin{array}{cccc}{C}_{1,1}& C_{1,2}& \cdots & C_{1,N}\\ C_{2,1}& C_{2,2}& \cdots & C_{2,N}\\ ⋮& ⋮& ⋰& ⋮\\ C_{N,1}& C_{N,2}& \cdots & C_{N,N}\end{array}\right]$
where each matrix element C_ij is of size 2×2.

[0111] Two shadow edges can only intersect once (two shadow planes intersect along a line that can only interest the scene at a single point). All matrices C_ij have the following expressions:

[0112] $C_{\mathrm{ij}}=I_2-{\stackrel{\_}{Y}}_{k\left(\mathrm{ij}\right)}{\stackrel{\_}{Y}}_{k\left(\mathrm{ij}\right)}^T\mathrm{if}i\ne j$ $C_{i,i}=I_2-\sum _{n=1}^N{\stackrel{\_}{Y}}_{k\left(i,n\right)}{\stackrel{\_}{Y}}_{{}_{k\left(i,n\right)}}^T$
where I₂ is the 2×2 identity matrix. Observe that, every off-diagonal matrix element C_ij (i≠j) depends only on the intersection point p_k(ij) between edges ε_I and ε_j. Every diagonal block C_i,i however is function of all the intersection points of ε₁ with the rest of the edge-web (the sum is over all points p_k(i,n), for n=(1, . . . , N).

[0113] Once the C matrix is built, V is retrieved by singular value decomposition (1130; FIG. 11). This technique allows then for a direct identification of the unitary seed solution of

[0114] ${\stackrel{\_}{U}}^0=\left\{{\stackrel{\_}{u}}_i^0\right\}$
leading the set of all possible solutions of the equation. Euclidean reconstruction is thus achieved up to the three parameters α, β and λ.

[0115] Once the seed solution Ū⁰={ū_i⁰} is found (by SVD), one may identify the final “Euclidean” solution Ū={ū_I} at 1140 if the depth of (at least) three points in the scene are known. Without loss of generality, assume that these points are p_k for k=1, 2, 3 (with depths Z_k). Those points provide then three linear equations in the unknown coefficient vector {overscore (α)}=[α, β γ]^T

[0116] $\left[{\stackrel{\_}{y}}_k^T\langle {\stackrel{\_}{u}}_{n\left(k\right)}^0,\stackrel{\_}{y}\rangle \right]\stackrel{\_}{\alpha }=1/Z_k-\langle {\stackrel{\_}{\omega }}_0,{\stackrel{\_}{x}}_k\rangle$
for k=1, 2, 3 resulting into a linear system of three equations and three unknowns. This system may then be solved, yielding the three coefficients α, β and λ, and therefore the final solution vector Ū. Complete Euclidean shape reconstruction is thus achieved. If more points are used as initial depths, the system may be solved in the least squares sense (once again optimal in the inverse depth error sense). Notice that the reference depth points do not have to be intersection points as the equation contends. Any three (or more) points in the edge-web may be used.

[0117] While the above has described strict reconstruction, other clues about the scene may also be used. These clues may include planarity of portions on the scene, angles between the different planes, or mutual distances between points in space. Any of these geometric clues can help either simplify the calculations, or make the calculations more strictly Euclidean. Another embodiment, shown in FIG. 14, generalizes the above operation to use with multiple light sources. Using the notation above, two calibrated light sources may be used. In this case, the matrix A has a rank that is increased to 2N-2. To shadow planes from the two light sources S1 and S2 can intersect at least at two points in the scene. As described above, depth information at those two points can then propagate along the two edges. They also propagate to the rest of the edge web as described above.

[0118] Two shadow planes Πn and Πm are generated from the two light sources as shown in FIG. 14. Two corresponding shadow edges ξn and ξm intersect on the image plane at the two points P. Depth information at P_k and qk propagates through the shadow edges for and am. This provides further information which can be used for further detection of information in the scene.

[0119] The notation in the foregoing refers to “Dual Space” and “B-shape”. The meaning of this notation is further described herein. All definitions are given in Euclidean space as well as in projective geometry. A mathematical formalism called B-dual-space geometry is derived from projective geometry. This formalism enables us to explore and compute geometrical properties of three-dimensional scenes with simple and compact notation. This will be illustrated in the following chapter when applying that formalism to the problem of camera calibration.

[0120] Let (E) be the 3D Euclidean space. For a given position of a camera in space we define =(O_c, X_c, Y_c, Z_c) as the standard frame of reference (called “camera reference frame”) where O_c is the camera center of projection, and the three axes (O_c, X_c), (O_c, Y_c) and (O_c, Z_c) are mutually orthogonal and right-handed ((O_c, X_c) and (O_c, Y_c) are chosen parallel to the image plane).

[0121] We may then refer to a point P in space by its corresponding Euclidean coordinate vector {overscore (X)}=[X Y Z]^T in that reference frame . The Euclidean space may also be viewed as a three-dimensional projective space ³. In that representation, the point P is alternatively represented by the homogeneous 4-vector {overscore (X)}≃[X Y Z 1]^T. The sign ≃ denotes a vector equality up to a non-zero scalar. Therefore, any scaled version of [X Y Z 1]^T represents the same point in space.

[0122] A plane Π in space is defined as the set of points P of homogeneous coordinate vector {overscore (X)} that satisfy:
<{overscore (π)},{overscore (X)}>=0  (2.1)
where π≃[π_xπ_yπ_zπ_t] is the homogeneous 4-vector parameterizing the plane Π (<.> is the standard scalar product operator). Observe that if {overscore (π)} is normalized such that π_x²+π_y²+π_z²=1, then {overscore (n)}_x=[π_xπ_yπ_z]^T is the normal vector of the plane Π (in the camera reference frame ) and d_π=−π_t its orthogonal (algebraic) distance to the camera center O_c
Image Plane and Perspective Projection

[0123] Let (I) be the 2D image plane. The image reference frame is defined as (c, x_c, y_c) where c is the intersection point between (O_c, Z_c) (optical axis) and the image plane, and (c, x_c) and (c, y_c) are the two main image coordinate axes (parallel to (O_c, X_c) and (O_c, Y_c)). The point c is also called optical center or principal point.

[0124] Let p be the projection on the image plane of a given point P of coordinates {overscore (X)}=[X Y Z]^T, and denote {overscore (x)}=[x y]^T its coordinate vector on the image plane. Then, the two vectors {overscore (X)} and {overscore (x)} are related through the perspective projection equation:

[0125] $\begin{array}{cc}\stackrel{\_}{x}=\left[\begin{array}{c}x\\ y\end{array}\right]=\frac{1}{Z}\left[\begin{array}{c}X\\ Y\end{array}\right]& \left(2.2\right)\end{array}$
This projection model is also referred to as a “pinhole” camera model.

[0126] In analogy to Euclidean space, it is sometimes useful to view the image plane as a two-dimensional projective space ². In that representation, a point p on the image plane has homogeneous coordinate vector {overscore (x)}≃[x y 1]^T. Similarly to ³, any scaled version of [x y 1]^T describes the same point on the image plane.

[0127] One advantage of using projective geometry is that the projection operator defined in equation 2.2 becomes a linear operator from ³ to ².
{overscore (x)}≃P{overscore (X)} with P=[I_3×3 0_3×1]  (2.3)
where {overscore (X)} and {overscore (x)} are the homogeneous coordinates of P and p respectively, I_3×3 is the 3×3 identify matrix and 0_3×1 is the 3×1 zero-vector. Observe from equation 2.3 that {overscore (x)} is equal (up to a scale) to the Euclidean coordinate vector {overscore (X)}=[X Y Z] of P:
{overscore (x)}≃{overscore (X)}  (2.4)
Therefore {overscore (x)} is also referred to as the optical ray direction associated to P.

[0128] A line λ on the image plane is defined as the set of points p of homogeneous coordinate vectors {overscore (x)} that satisfy:
<{overscore (λ)},{overscore (x)}>=0  (2.5)
where {overscore (λ)}=[λ_x λ_y λ_z]^T is the homogeneous 3-vector defining the line λ. Observe that if {overscore (λ)} is normalized such that λ_x²+λ_y²=1, then {overscore (n)}_λ=[λ_x λ_y]^T is the normal vector of the line λ (in the image reference frame) and d_λ=−λ_z its orthogonal (algebraic) distance to the principal point c.

• [0129] Claim 1: Let p₁ and p₂ be two distinct points on the image plane with respective homogeneous coordinate vectors {overscore (x)}₁ and {overscore (x)}₂. Then, it is straightforward to show that the line λ connecting p₁ and P₂ has homogeneous coordinate vector {overscore (λ)}≃{overscore (x)}₁×{overscore (x)}₂, where x is the standard vector product operator in ³.
• [0130] Claim 2: Let λ₁ and λ₂ be two distinct lines on the image plane with respective homogeneous coordinate vectors {overscore (λ)}₁ and {overscore (λ)}₂. Then, the point of intersection p between the two lines λ₁ and λ₂ has homogeneous coordinate vector {overscore (x)}≃{overscore (λ)}₁×{overscore (λ)}₂. If the two lines are parallel then the last coordinate of {overscore (x)} is zero. In that case p is a point at infinity.

[0131] There exists useful relations between lines on the image plane and planes in space, as illustrated by the two following examples.

[0132] Consider a line λ on the image plane of coordinate vector {overscore (λ)}=[λ_x λ_y λ_z]^T. Then, the set of points P in space that project onto λ is precisely the plane Π_λ spanned by λ and the camera O_c. Let {overscore (π)}_λ be the coordinate vector of Π_λ. Let us compute {overscore (π)}_λ as a function of {overscore (λ)}. According to equations 2.3 and 2.5, a point P of homogeneous coordinate vector {overscore (X)} will lie on Π_λ if and only if:
<{overscore (λ)},P{overscore (X)}>=0  (2.6)
this relation enforces the projection of P to lie on λ. This may be alternatively written:
<P^T{overscore (λ)},{overscore (X)}>=0  (2.7)
Therefore the plane coordinates {overscore (π)}_λ has the following expression:

[0133] $\begin{array}{cc}{\stackrel{\_}{\pi }}_{\lambda }\simeq P^T\stackrel{\_}{\lambda }=\left[\begin{array}{c}\stackrel{\_}{\lambda }\\ 0\end{array}\right]=\left[\begin{array}{c}{\lambda }_x\\ {\lambda }_y\\ {\lambda }_z\\ 0\end{array}\right]& \left(2.8\right)\end{array}$

[0134] Consider two planes in space Π₁ and Π₂ of respective coordinate vectors {overscore (π)}₁≃[π_x1 π_y1 π_z1 π_t1]^T and {overscore (π)}₂≃[π_x2 π_y2 π_z2 π_t2]^T. Assume the two planes intersect along line Λ in space, and call λ the resulting image line after projection of Λ onto the image plane. Let us compute the coordinate vector {overscore (λ)} of λ as a function of {overscore (π)}₁ and {overscore (π)}₂. Consider a point P on Λ and denote p its projection on the image plane. Since P lies on Π₁ and Π₂, its homogeneous coordinate vector {overscore (X)}≃[X Y Z 1]^T must satisfy the following system:

[0135] $\begin{array}{cc}\{\begin{array}{cc}{\pi }_{x_1}X+{\pi }_{y_1}Y+{\pi }_{z_1}Z+{\pi }_{t_1}=0& \left(L_1\right)\\ {\pi }_{x_2}X+{\pi }_{y_2}Y+{\pi }_{z_2}Z+{\pi }_{t_2}=0& \left(L_2\right)\end{array}& \left(2.9\right)\end{array}$
This system yields:
(π_t2 π_x1−π_t1 π_x2)X+(π_t2 π_y1−π_t1 π_y2)Y+(π_t2 π_z1−π_t1 π_z2)Z=0.  (2.10)
Since the homogeneous coordinate vector of p is {overscore (x)}≃{overscore (X)}=[X Y Z]^T, equation 2.10 reduces to a standard image line equation:
<{overscore (λ)},{overscore (x)}>=0  (2.11)
where

[0136] $\begin{array}{cc}\stackrel{\_}{\lambda }\simeq \left[\begin{array}{c}{\pi }_{t_2}{\pi }_{x_1}-{\pi }_{t_1}{\pi }_{x_2}\\ {\pi }_{t_2}{\pi }_{y_1}-{\pi }_{t_1}{\pi }_{y_2}\\ {\pi }_{t_2}{\pi }_{z_1}-{\pi }_{t_1}{\pi }_{z_2}\end{array}\right]& \left(2.12\right)\end{array}$
that is the coordinate vector of λ, projector of Λ=Π₁∩Π₂.
Rigid Body Motion Transformation

[0137] Consider a set on N points P_i in space (i=1, . . . , N), and let {overscore (X)}_i=[X_i Y_i Z_i]^T be their respective coordinate vectors in the camera reference frame . Suppose the camera moves to a new location in space, and let {overscore (X)}_i′=[X_i′ Y_i′ Z_i′]^T be the coordinate vectors of the same points P_i in the new camera reference frame ′. Then {overscore (X)}_i and {overscore (X)}′_i are related to each other through a rigid body motion transformation:
∀i=(1, . . . N), {overscore (X)}_i′=R{overscore (X)}_i+T  (2.13)
Where RεSO(3), which is a special orthogonal 3×3 matrix, and T are respectively a 3×3 rotation matrix and a 3-vector that uniquely define the rigid motion between the two camera positions. The matrix R is defined by a rotation vector {overscore (Ω)}=[Ω_x Ω_y Ω_z]^T such that:
R=e^{{overscore (Ω)}Λ}  (2.14)
where {overscore (Ω)}Λ is the following skew-symmetric matrix:

[0138] $\begin{array}{cc}\stackrel{\_}{\Omega }\Lambda =\left[\begin{array}{ccc}0& -{\Omega }_z& {\Omega }_y\\ {\Omega }_z& 0& -{\Omega }_x\\ -{\Omega }_y& {\Omega }_x& 0\end{array}\right]& \left(2.15\right)\end{array}$
Equation 2.14 may also be written in a compact form using the Rodrigues' formula:

[0139] $\begin{array}{cc}R=I_{3\times 3}\cos \left(\theta \right)+\left[\stackrel{\_}{\Omega }\Lambda \right]\frac{\sin \left(\theta \right)}{\theta }+\left[\stackrel{\_}{\Omega }{\stackrel{\_}{\Omega }}^T\right]\frac{1-\cos \left(\theta \right)}{{\theta }^2}& \left(2.16\right)\end{array}$
where θ=∥{overscore (Ω)}∥, and {overscore (Ω)}{overscore (Ω)}^T is the following semi-positive definite matrix:

[0140] $\begin{array}{cc}\stackrel{\_}{\Omega }{\stackrel{\_}{\Omega }}^T=\left[\begin{array}{ccc}{\Omega }_x^2& {\Omega }_x{\Omega }_y& {\Omega }_x{\Omega }_z\\ {\Omega }_y{\Omega }_x& {\Omega }_y^2& {\Omega }_y{\Omega }_z\\ {\Omega }_z{\Omega }_x& {\Omega }_z{\Omega }_y& {\Omega }_z^2\end{array}\right]& \left(2.17\right)\end{array}$

[0141] The fundamental rigid body motion equation 2.13 may also be written in projective space ³. In ³, the point P_i has homogeneous coordinate vectors {overscore (X)}_i ≃[X_i Y_i Z_i 1]^T and {overscore (X)}_i′≃[X_i′ Y_i′ Z_i′ 1]^T in the first () and second (′) reference frames respectively. Then, equation 2.13 may be written:

[0142] $\begin{array}{cc}{\stackrel{\_}{X}}_i^{\prime }\simeq D{\stackrel{\_}{X}}_i\mathrm{with}D=\left[\begin{array}{cc}R& T\\ 0_{1\times 3}& 1\end{array}\right]& \left(2.18\right)\end{array}$
where 0_1×3 is a 1×3 zero row vector. Observe that the inverse relation may also be written as follows:

[0143] $\begin{array}{cc}{\stackrel{\_}{X}}_i^{\prime }\simeq D^{-1}{\stackrel{\_}{X}}_i^{\prime }\mathrm{with}{D}^{-1}=\left[\begin{array}{cc}{R}^T& -R^{T}T\\ 0_{1\times 3}& 1\end{array}\right]& \left(2.19\right)\end{array}$

[0144] Let p_i′ be the projection of P_i onto the second camera image plane, and let {overscore (x)}_i′ be the homogeneous coordinate vector. Then, following the equation 2.3, we have:
{overscore (x)}_i′≃P{overscore (X)}_i′  (2.20)
which may be also written:
{overscore (x)}_i′≃P′{overscore (X)}_i  (2.21)
where: which may be also written:
P′=PD=[RT]  (2.22)
The matrix P′ is the projection matrix associated to the second camera location.

[0145] Consider now a plane Π of homogeneous coordinate vectors {overscore (π)} and {overscore (π)}′ in both camera reference frames and ′. How do {overscore (π)} and {overscore (π)}′ relate to each other? Consider a generic point P on Π with homogeneous coordinate vectors {overscore (X)} and {overscore (X)}′ in both reference frames. According to equation 2.1, we have:
<{overscore (π)}, {overscore (X)}>=0  (2.23)
which successively implies:
<{overscore (π)},D⁻¹{overscore (X)}_i′>=0  (2.24)
<D^−T{overscore (π)},{overscore (X)}_i′>=0  (2.25)
Therefore:

[0146] $\begin{array}{cc}{\stackrel{\_}{\pi }}^{\prime }\simeq D^{-T}\stackrel{\_}{\pi }=\left[\begin{array}{cc}R& 0_{3\times 1}\\ -T^{T}R& 1\end{array}\right]\stackrel{\_}{\pi }& \left(2.26\right)\end{array}$
Similarly, the plane coordinate vector before motion {overscore (π)} may be retrieved from {overscore (π)}′ through the inverse expression:

[0147] $\begin{array}{cc}\stackrel{\_}{\pi }\simeq D^T{\stackrel{\_}{\pi }}^{\prime }=\left[\begin{array}{cc}{R}^T& 0_{3\times 1}\\ T^T& 1\end{array}\right]{\stackrel{\_}{\pi }}^{\prime }& \left(2.27\right)\end{array}$

[0148] In order to put in practice these concepts, let us go through the following example:

[0149] In the second reference frame ′ (after camera motion), consider a line λ′ on the image plane, and the plane Π that this line spans with the camera center (similarly to example 1. Let {overscore (λ)}′ and {overscore (π)}′ be the homogeneous coordinate vectors of λ′ and Π in ′. Let us compute {overscore (π)}, the coordinate vector of Π in the initial camera reference frame (before motion) as a function of {overscore (λ)}′, R and T.

[0150] According to equation 2.8, {overscore (π)}′ and {overscore (λ)}′ are related through the following expression:

[0151] $\begin{array}{cc}{\stackrel{\_}{\pi }}^{\prime }\simeq \left[\begin{array}{c}{\stackrel{\_}{\lambda }}^{\prime }\\ 0\end{array}\right]& \left(2.28\right)\end{array}$
Then, {overscore (π)} may be calculated from {overscore (π)}′ using equation 2.27:

[0152] $\begin{array}{cc}\stackrel{\_}{\pi }\simeq D^T{\stackrel{\_}{\pi }}^{\prime }=\left[\begin{array}{cc}{R}^T& 0_{3\times 1}\\ T^T& 1\end{array}\right]\left[\begin{array}{c}{\stackrel{\_}{\lambda }}^{\prime }\\ 0\end{array}\right]=\left[\begin{array}{c}{R}^T{\stackrel{\_}{\lambda }}^{\prime }\\ \langle T,{\stackrel{\_}{\lambda }}^{\prime }\rangle \end{array}\right]=P^{\prime T}{\stackrel{\_}{\lambda }}^{\prime }& \left(2.29\right)\end{array}$
where P′ is the projection matrix associated to the second camera location (eq. 2.22). Observe the similarity between equations 2.8 and 2.29.
Definition of B-Dual-Space

[0153] As presented in the previous section, a plane Π in space is represented by an homogeneous 4-vector {overscore (π)}≃[π_x π_y π_z π_t]^T in the camera reference frame =(0_c,X_c,Y_c,Z_c) (see equation 2.1). Alternatively, if Π does not contain the camera center O_c (origin of ) then it may be represented by a 3-vector {overscore (ω)}=[ω_x ω_y ω_z]^T, such that:
<{overscore (ω)}, {overscore (X)}>=1  (2.30)
for any point PεΠ of coordinate vector {overscore (X)}=[X Y Z]^T in . Notice that {overscore (ω)}={overscore (n)}_π/d_π where {overscore (n)}_π is the unitary normal vector of the plane and d_π≠0 its distance to the origin. Let (Ω)=³. Since every point {overscore (ω)}ε(Ω) corresponds to a unique plane Π in Euclidean space (E), we refer to (Ω) as the ‘plane space’ or ‘B-dual-space’. For brevity in notation, we will often refer to this space as the dual-space. There exists a simple relationship between plane coordinates in projective geometry and dual-space geometry:

[0154] $\begin{array}{cc}\stackrel{\_}{\omega }=-\frac{1}{{\pi }_t}\left[\begin{array}{c}{\pi }_x\\ {\pi }_y\\ {\pi }_z\end{array}\right]\mathrm{if}{\pi }_t\ne 0& \left(2.31\right)\end{array}$
In that sense, dual-space geometry is not a new concept in computational geometry. Originally, the dual of a given vector space (E) is defined as the set of linear forms on (E) (linear functions of (E) into the reals ). In the case where (E) is the three dimensional Euclidean space, each linear form may be interpreted as a plane Π in space that is typically parameterized by a homogeneous 4-vector {overscore (π)}≃[π_x π_y π_z π_t]^T. A point P of homogeneous coordinates {overscore (X)}=[X Y Z 1]^T lies on a generic plane Π of coordinates {overscore (π)} if and only if <{overscore (π)}, {overscore (X)}>=0 (see [13]). Our contribution is mainly the new {overscore (ω)}-parameterization. We will show that this representation exhibits useful properties allowing us to naturally relate objects in Euclidean space (planes, lines and points) to their perspective projections on the image plane (lines and points). One clear limitation of that representation is that plane crossing the camera origin cannot be parameterized using that formalism (for such planes π_t=0). However, this will be shown not to be a critical issue in all geometrical problems addressed in this thesis (as most planes of interest do not contain the camera center).
Properties of B-Dual Space

[0155] This section presents the fundamental properties attached to dual-space geometry.

[0156] The following proposition constitutes the major property associated to our choice of parameterization:

[0157] Proposition 1: Consider two planes Π_a and Π_b in space, with respective coordinate vectors {overscore (ω)}_a and ω_b({overscore (ω)}_a≠{overscore (ω)}_b) in dual-space, and let Λ=Π_a∩Π_b be the line of intersection between them. Let λ be the perspective projection of Λ on the image plane, and {overscore (λ)} its homogeneous coordinate vector. Then {overscore (λ)} is parallel to {overscore (ω)}_a−{overscore (ω)}_b. In other words, {overscore (ω)}_a−{overscore (ω)}_b is a valid coordinate vector of the line λ.

[0158] Proof: Let PεΛand let p be the projection of P on the image plane. Call {overscore (X)}=[X Y Z]^T and

[0159] $\stackrel{\_}{x}\simeq \frac{1}{z}\stackrel{\_}{X}$
the respective coordinates of P and p. We successively have:

[0160] $\begin{array}{c}P\in \Lambda \iff \{\begin{array}{ccc}P& \in & {\Pi }_a\\ P& \in & {\Pi }_b\end{array}\\ \iff \{\begin{array}{c}\langle {\stackrel{\_}{\omega }}_a,\stackrel{\_}{X}\rangle =1\\ \langle {\stackrel{\_}{\omega }}_b,\stackrel{\_}{X}\rangle =1\end{array}\\ \Rightarrow \langle {\stackrel{\_}{\omega }}_a-{\stackrel{\_}{\omega }}_b,\stackrel{\_}{X}\rangle =0\\ \Rightarrow \langle {\stackrel{\_}{\omega }}_a-{\stackrel{\_}{\omega }}_b,\stackrel{\_}{X}\rangle =0\left(\mathrm{since}Z\ne 0\right)\\ \Rightarrow \stackrel{\_}{\lambda }\simeq {\stackrel{\_}{\omega }}_a-{\omega }_b.•\end{array}$

[0161] Notice that this relation is significantly simpler than that derived using standard projective geometry (equation 2.12).

[0162] In addition, observe that the coordinate vector {overscore (ω)} of any plane Π containing the line Λ lies on the line connecting {overscore (ω)}_a and {overscore (ω)}_b in dual-space (Ω). We denote that line by {circumflex over (Λ)} and call it the dual image of Λ. The following definition generalizes that concept of dual image to other geometrical objects:

[0163] Definition: Let be a sub-manifold of (E) (e.g., a point, line, plane, surface or curve). The dual image of of is defined as the set of coordinates vectors {overscore (ω)} in dual-space (Ω) representing the tangent planes to . Following that standard definition (see [13, 14]), the dual images of points, lines and planes in (E) may be shown to be respectively planes, lines and points in dual-space (Ω). Further properties regarding non-linear sub-manifolds may be observed, such as for quadric surfaces in [15] or for general apparent contours in space in [16].

[0164] The following five propositions cover the principal properties attached to the dual-space formalism.

[0165] Proposition 2—Parallel Planes—Horizon Line: Let Π_a and Π_b be two parallel planes of coordinates {overscore (ω)}_a and {overscore (ω)}_b. Then {overscore (ω)}_a parallel to {overscore (ω)}_b.

[0166] Proof: The planes have the same surface normals {overscore (n)}_a={overscore (n)}_b. Therefore, the proposition follows from definition of {overscore (ω)}.

[0167] The horizon line H represents the “intersection” of two planes at infinity. The dual image of H is the line Ĥ connecting {overscore (ω)}_a and {overscore (ω)}_b and crossing the origin of the (Ω) space. The direction of that line is not only the normal vector of the two planes {overscore (n)}_a={overscore (n)}_b, but also the representative vector {overscore (λ)}_H of the projection λ_H of H (horizon line) on the image plane (according to proposition 1). Although H is not a well-defined line in Euclidean space (being a line at infinity), under perspective projection, it may give rise to a perfectly well defined line λ_H on the image plane (for example a picture of the ocean). Once that line is extracted, the orientation of the plane is known:
{overscore (ω)}_a≃{overscore (ω)}_b≃{overscore (λ)}_H  (2.32)
Proposition 3—Orthogonal Planes: If two planes Π_a and Π_b are two orthogonal, then so are their coordinate vectors {overscore (ω)}_a and {overscore (ω)}_b in dual-space. Consequently, once one of the plane {overscore (ω)}_a is known, then {overscore (ω)}_b is constrained to lie in the sub-space orthogonal to {overscore (ω)}_a, a plane in dual-space.

[0168] Proposition 4—Intersecting lines: Consider two lines Λ_a and Λ_b intersecting at a point P, and call Π the plane that contains them. In dual-space, the two dual lines {circumflex over (Λ)}_a and {circumflex over (Λ)}_b necessarily intersect at {overscore (ω)} the coordinate vector of Π (since {overscore (ω)} is the plane that contains both lines). Similarly, the dual image {circumflex over (P)} of P is the plane in dual-space that contains both dual lines {circumflex over (Λ)}_a and {circumflex over (Λ)}_b. Notice that {circumflex over (P)} does not cross the origin of (Ω).

[0169] Proposition 5—Parallel lines—Vanishing Point: Consider two parallel lines Λ_a and Λ_b belonging to the plane Π of coordinates {overscore (ω)}. Then {overscore (ω)} is at the intersection of the two dual lines {circumflex over (Λ)}_a and {circumflex over (Λ)}_b. In dual-space, the plane containing both dual lines {circumflex over (Λ)}_a and {circumflex over (Λ)}_b is the dual image of {circumflex over (V)} of the vanishing point V, i.e., the intersection point of Λ_a and Λ_b in Euclidean space. If H is the horizon line associated with Π, then VεH, which translates in dual-space into Ĥε{circumflex over (V)}. Since Ĥ contains the origin, so does {circumflex over (V)}. Notice that once the perspective projection v of V is observable on the image plane, the plane {circumflex over (V)} is entirely known (since its orientation is the coordinate vector of v).

[0170] Proposition 6—Orthogonal lines: Let Λ₁ and Λ₂ be two orthogonal lines contained in the plane Π of coordinates {overscore (ω)}) and let {overscore (ω)}={circumflex over (Λ)}₁∩{circumflex over (Λ)}₂. Consider the set of planes orthogonal to Π. In the dual-space, that set is represented by a plane containing the origin, and orthogonal to {overscore (ω)} (see proposition 3). Call that plane {circumflex over (V)} (it can be shown to be the dual image of a vanishing point). In that set, consider the two specific planes Π₁ and Π₂ that contain the lines Λ₁ and Λ₂. In the dual-space, the representative vectors {overscore (ω)}₁ and {overscore (ω)}₂ of those two planes are defined as the respective intersections between {circumflex over (V)} and the two lines {circumflex over (Λ)}₁ and {circumflex over (Λ)}₂. Then, since the two lines Λ₁ and Λ₂ are orthogonal, the two vectors {overscore (ω)}₁ and {overscore (ω)}₂ are also orthogonal. This implies that the images of the two vanishing points {circumflex over (V)}₁ and {circumflex over (V)}₂ associated to the lines Λ₁ and Λ₂ are orthogonal in the dual-space. Two vanishing points are enough to recover the horizon line H associated with a given plane Π in space. Therefore, observing two sets of parallel lines belonging to the same plane under perspective projection allows us to recover the horizon line, and therefore the orientation of the plane in space (from proposition 2). The horizon line H corresponding to the ground floor Π is recovered from the two vanishing points V₁ and V₂.

2.2.3 Geometrical Problems Solved in B-Dual-Space

[0171] This section presents several useful geometrical problems solved using dual-space geometry.

[0172] Let Π be a plane in space of coordinate vector {overscore (ω)}. Let P be a point on H with coordinate vector {overscore (X)}=[X Y Z]^T. Let p be the projection of P onto the image plane, and denote {overscore (x)}≃[x y 1]^T its homogeneous coordinate vector. The triangulation problem consists of finding the point P from its projection p and the plane Π, or calculating {overscore (X)} from {overscore (x)} and {overscore (ω)}. Since P lies on the optical ray (O_c, p), its coordinate vector satisfies {overscore (X)}≃{overscore (x)} or equivalently, {overscore (X)}=Z{overscore (x)}, with {overscore (x)}=[x y 1]^T. In addition, since P lies on the plane Π, we have <{overscore (ω)},{overscore (X)}>1. This implies:

[0173] $\begin{array}{cc}Z=\frac{1}{\langle \stackrel{\_}{\omega },\stackrel{\_}{x}\rangle }\Rightarrow \stackrel{\_}{X}=\frac{\stackrel{\_}{x}}{\langle \stackrel{\_}{\omega },\stackrel{\_}{x}\rangle }& \left(2.33\right)\end{array}$
This is the fundamental triangulation equation between a ray and a plane in space.

[0174] Consider two camera frames and ′ and let {R, T} be the rigid motion parameters between and ′. Let Π be a plane in space of coordinate vectors {overscore (ω)} and {overscore (ω)}′ in and ′ respectively. How do {overscore (ω)} and {overscore (ω)}′ relate to each other?

[0175] Consider a generic point P on Π of coordinate vectors {overscore (X)} and {overscore (X)}′ in and ′ respectively. Then, {overscore (X)}′=R{overscore (X)}+T. Since PεΠ, we may write:
<{overscore (ω)}′, {overscore (X)}′>=1  (2.34)
<{overscore (ω)}′, R{overscore (X)}+T>=1  (2.35)
<R^T{overscore (ω)}′, {overscore (X)}>=1−<{overscore (ω)}′, T>  (2.36)

[0176] $\begin{array}{cc}\langle \frac{R^T{\stackrel{\_}{\omega }}^{\prime }}{1-\langle {\stackrel{\_}{\omega }}^{\prime },T\rangle },\stackrel{\_}{X}\rangle =1\mathrm{if}\langle {\stackrel{\_}{\omega }}^{\prime },T\rangle \ne 1& \left(2.37\right)\end{array}$
Therefore:

[0177] $\begin{array}{cc}\stackrel{\_}{\omega }=\frac{R^T{\stackrel{\_}{\omega }}^{\prime }}{1-\langle {\stackrel{\_}{\omega }}^{\prime },T\rangle }.& \left(2.38\right)\end{array}$
This expression is the equivalent of equation 2.27 in dual-space geometry. Notice that the condition<{overscore (w)}′, T>≠1 is equivalent to enforcing the plane Π not to contain the origin of the first camera reference frame . That is a necessary condition in order to have a well defined plane vector {overscore (ω)}. The inverse expression may also be derived in a similar way:

[0178] $\begin{array}{cc}{\stackrel{\_}{\omega }}^{\prime }=\frac{R\stackrel{\_}{\omega }}{1+\langle \stackrel{\_}{\omega },R^{T}T\rangle }.& \left(2.39\right)\end{array}$
In that case, the condition <{overscore (ω)},−R^TT>≠1 constraints the plane Π not to contain the origin of the second reference frame ′ (in order to have a well defined vector {overscore (ω)}′).

[0179] In some cases, only one of the two plane vectors {overscore (ω)} or {overscore (ω)}′ is well-defined. The following example is one illustration of such a phenomenon.

[0180] Consider the geometrical scenario of example 5 where the plane Π is now spanned by a line λ′ on the image plane of the second camera reference frame ′ (after motion). In that case, the coordinate vector {overscore (ω)}′ is not well defined (since by construction, the plane Π contains the origin of ′). However, the plane vector {overscore (ω)} may very well be defined since Π does not necessarily contain the origin of the first reference frame . Indeed, according to equation 2.29, the homogeneous coordinate vector {overscore (π)} of Π in is given by:

[0181] $\begin{array}{cc}\stackrel{\_}{\pi }\simeq \left[\begin{array}{c}{R}^T{\stackrel{\_}{\lambda }}^{\prime }\\ \langle T,{\stackrel{\_}{\lambda }}^{\prime }\rangle \end{array}\right]& \left(2.40\right)\end{array}$
where {overscore (λ)}′ is homogeneous coordinate vector of the image line λ′ in ′. Then, according to expression 2.31, the corresponding dual-space vector {overscore (ω)} is given by:

[0182] $\begin{array}{cc}\stackrel{\_}{\omega }=-\frac{R^T{\stackrel{\_}{\lambda }}^{\prime }}{\langle T,{\stackrel{\_}{\lambda }}^{\prime }\rangle }& \left(2.41\right)\end{array}$
which is perfectly well-defined as long as Π does not contain O_c, or equivalently if (T, {overscore (λ)}′)≠0. This condition is equivalent to enforcing the line not to contain the epipole on the image plane attached to camera frame. The point is the projection of onto the image plane attached to the second camera reference frame.

[0183] triangulation of an optical ray (O_c,P) with the plane H spanned by the line λ′ in the other camera reference frame ′. Let {overscore (X)}=[X Y Z]^T be the coordinates of P in space and {overscore (x)}=[x y 1]^T the coordinates of its known projection p on the image plane. Equation 2.41 provides then an expression for the coordinate vector {overscore (ω)} of Π in frame :

[0184] $\begin{array}{cc}\stackrel{\_}{\omega }=-\frac{R^T{\stackrel{\_}{\lambda }}^{\prime }}{\langle T,{\stackrel{\_}{\lambda }}^{\prime }\rangle }& \left(2.42\right)\end{array}$
where {overscore (λ)}′ is the homogeneous coordinate vector of the image line λ′ in ′. The triangulation expression given by equation 2.40 returns then the final coordinate vector of P:

[0185] $\begin{array}{cc}\stackrel{\_}{X}=\frac{\stackrel{\_}{x}}{\langle \stackrel{\_}{\omega },\stackrel{\_}{x}\rangle }=\frac{\langle T,{\stackrel{\_}{\lambda }}^{\prime }\rangle \stackrel{\_}{x}}{\langle R^T{\stackrel{\_}{\lambda }}^{\prime },\stackrel{\_}{x}\rangle }& \left(2.43\right)\end{array}$
Observe that the plane Π is not allowed to cross the origin of the initial reference frame , otherwise, triangulation is impossible. Therefore the plane vector {overscore (ω)} is perfectly well defined (i.e., (T,{overscore (λ)}′)≠0).
3.1.1 Camera Calibration in B-Dual-Space Geometry

[0186] The position of a point p in a real image is originally expressed in pixel units. One can only say that a point p is at the intersection of column p_x=150 and row p_y=50 on a given digitized image. So far, we have been denoting {overscore (x)}=[x y 1]^T the homogeneous coordinate vector of a generic point p on the image plane. This vector (also called normalized coordinate vector) is directly related to the 3D coordinates {overscore (X)}=[X Y Z]^T of the corresponding point P is space through the perspective projection operator (eq. 2.2). Since in practice we only have access to pixel coordinates {overscore (p)}=[p_x p_y 1]^T, we need to establish a correspondence between {overscore (p)} and {overscore (x)} (from pixel coordinates to optical ray in space).

[0187] Since the origin of the image reference frame is at the optical center c (or principal point), it is necessary to know the location of that point in the image: {overscore (c)}=[c_x c_y]^T (in pixels). Let f_o be the focal distance (in meters) of the camera optics (distance of the lens focal point to the imaging sensor), and denote by d_x and d_y the x and y dimensions of the pixels in the imaging sensor (in meters). Let f_x=f_o/d_x and f_y=f_o/d_y (in pixels). Notice that for most imaging sensors currently manufactured, pixels may be assumed perfectly square, implying d_x=d_y or equivalently f_z=f_y. In the general case f_x and f_y may be different.

[0188] Then, the pixel coordinates {overscore (p)}=[p_x p_y 1]^T of a point on the image may be computed from its normalized homogeneous coordinates {overscore (x)}=[x y 1]^T through the following expression:

[0189] $\begin{array}{cc}\{\begin{array}{c}{p}_x=f_{x}x+c_x\\ p_y=f_{y}y+c_y\end{array}& \left(3.1\right)\end{array}$
That model assumes that the two axes of the imaging sensor are orthogonal. In the case where they are not orthogonal, the pixel mapping function may be generalized to:

[0190] $\begin{array}{cc}\{\begin{array}{c}{p}_x=f_{x}x-\alpha f_{y}y+c_x\\ p_y=f_{y}y+c_y\end{array}& \left(3.2\right)\end{array}$
where α is a scalar coefficient that controls the amount of skew between the two main sensor axes (if α=0, there is no skew). For now, let us consider the simple model without skew (equation 3.1). If p is the image projection of the point P in space (of coordinates {overscore (X)}=[X Y Z]^T), the global projection map may be written in pixel units:

[0191] $\begin{array}{cc}\{\begin{array}{c}{p}_x=f_x\left(X/Z\right)+c_x\\ p_y=f_y\left(Y/Z\right)+c_y\end{array}& \left(3.3\right)\end{array}$

[0192] This equation returns the coordinates of a point projected onto the image (in pixels) in the case of an ideal pinhole camera. Real cameras do not have pinholes, but lenses. Unfortunately a lens will introduce some amount of distortion (also called aberration) in the image. That makes the projected point to appear at a slightly different position on the image. The following expression is a simple first-order model that captures the distortions introduced by the lens:

[0193] $\begin{array}{cc}\{\begin{array}{cc}\stackrel{\_}{a}=\left[\begin{array}{c}X/Z\\ Y/Z\end{array}\right]=\left[\begin{array}{c}x\\ y\end{array}\right]& \mathrm{pinhole}\mathrm{projection}\\ \stackrel{\_}{b}=\left[\begin{array}{c}{b}_x\\ b_y\end{array}\right]=\stackrel{\_}{x}\left(1+k_c{\stackrel{\_}{a}}^2\right)& \mathrm{radial}\mathrm{distortion}\\ \stackrel{\_}{p}=\left[\begin{array}{c}{p}_x\\ p_y\end{array}\right]=\left[\begin{array}{c}{f}_x{b}_x+c_x\\ f_y{b}_y+c_y\end{array}\right]& \mathrm{pixel}\mathrm{coordinates}\end{array}& \text{(3.4)}\end{array}$
where k_c is called the radial distortion factor. This model is also called first-order symmetric radial distortion model (“symmetric” because the amount of distortion is directly related to the distance of the point to the optical center c). Observe that the systems (3.4) and (3.3) are equivalent when k_c=0 (no distortion).

[0194] Therefore, if the position of the point P is known in camera reference frame, one may calculate its projection onto the image plane given the intrinsic camera parameters f_x, f_y, c_x, c_y and k_c. That is known as the direct projection operation and may be denoted {overscore (p)}=Π({overscore (X)}). However, most 3D vision applications require to solve the “inverse problem” that is mapping pixel coordinates {overscore (p)} to 3D world coordinates [X Y Z]^T. In particular, one necessary step is to compute normalized image coordinates {overscore (x)}=[x y 1]^T (3D ray direction) from pixel coordinates {overscore (p)} (refer to equation 3.4). The only non-trivial aspect of that inverse map computation is in computing the vector ā from {overscore (b)}. This is the distortion compensation step. It may be shown that for relatively small distortions, this inverse map may be very well approximated by the following equation:

[0195] $\begin{array}{cc}\stackrel{\_}{a}\approx \frac{\stackrel{\_}{b}}{1+k_c{\frac{\stackrel{\_}{b}}{1+k_c{\stackrel{\_}{b}}^2}}^2}& \left(3.5\right)\end{array}$
Experimentally, this expression is sufficiently accurate.
Camera Calibration

[0196] The camera calibration procedure identifies the intrinsic camera parameters f_x, f_y, c_x, c_y and k_c and possibly α). A standard method is to acquire an image a known 3D object (a checker board pattern, a box with known geometry . . . ) and look for the set of parameters that best match the computed projection of the structure with the observed projection on the image. The reference object is also called calibration ring. Since the camera parameters are inferred from image measurements, this approach is also called visual calibration. This technique was originally presented by Tsai and Brown. An algorithm for estimation was proposed by Abdel-Aziz and Karara (for an overview on camera calibration, the reader may also refer to the book Klette, Schluns and Koschan).

[0197] FIGS. 4A and 4B show two examples of calibration images when using a planar rig (checker board pattern). FIG. 5 shows a 3D rig (two orthogonal checker board patterns).

[0198] Note that although the geometry of the calibration rig is known (i.e., the mutual position of the grid corners in space), its absolute location with respect to the camera is unknown. In other words, the pose of the calibration pattern in unknown. Therefore, before applying the set of equations (3.4) to compute the image projection of every corner in the structure, one needs to find their 3D coordinates in the camera reference frame. We first choose a reference frame attached to the rig (called the object frame) in which we express the known coordinates {overscore (X)}_oⁱ of all the corners P_i, (i=1. . . N). This set of vectors is known since the intrinsic rig structure is known. Then, the coordinate vector {overscore (X)}_cⁱ in the camera frame is related {overscore (X)}_oⁱ through a rigid motion transformation:
∀i=1, . . . , N, {overscore (X)}_c′=R_c{overscore (X)}_oⁱ+T_c  (3.6)
where R_c and T_c define the pose of the calibration rig with respect to the camera (similarly to equation 2.13). See FIG. 3.2.

[0199] Notice that by adding the calibration object in the scene, more unknowns have been added to the problem: R_c and T_c. Those parameters are called extrinsic camera parameters since they are dependent upon the pose of the calibration pattern with respect to the camera (unlike the intrinsic parameters that remain constant as the rig is moved in front of the camera).

[0200] Let {overscore (Ω)}_c be the rotation vector associated to the rotation matrix R_c (see equation 2.13). Then, the complete set of unknowns to solve for is:

• [0201] Focal length: f_x, f_y (2 DOF),
• [0202] Principal point coordinates: c_x, c_y (2 DOF),
• [0203] Radial distortion factor: k_c (1 DOF),
• [0204] Calibration rig pose: {overscore (Ω)}_c, T_c (6 DOF).
  Therefore, the global calibration problem consists of solving for a total of 11 scalar parameters (adding the skew coefficient α would bring the number of unknowns to 12).

[0205] Let p_i(i=1, . . . , N) be the observed image projections of the rig points P_i and let {overscore (p)}_i=[p_xⁱ p_yⁱ]^T be their respective pixel coordinates. Experimentally, the points p_i are detected using the standard Harris corner finders.

[0206] The estimation process finds the set of calibration unknowns (extrinsic and intrinsic) that minimizes the reprojection error. Therefore, the solution to that problem may be written as follows:

[0207] $\begin{array}{cc}\left\{f_x,f_y,c_x,c_y,k_c,{\stackrel{\_}{\Omega }}_c,T_c\right\}=\mathrm{Argmin}\sum _{i=1}^N{\stackrel{\_}{p}}_i-{\left(\Pi (R_c{\stackrel{\_}{X}}_o^i+T_c\right)}^2& \left(3.7\right)\end{array}$
where R_c=e^{{overscore (Ω)}Λ},Π(.) is the image projection operator defined in equation 3.4 (function of the intrinsic parameters f_x, f_y, c_x, c_y and k_c) and ∥.∥ is the standard distance norm is pixel units. This non-linear optimization problem may be solved using standard gradient descent techniques. However, it is required to have a good initial guess before starting the iterative refinement. a method to derive closed form expressions for calibration parameters that may be used for initialization is presented.

[0208] Apart from numerical implementation details, it is also important to study the observability of the model. In other words, under which conditions (type of the calibration rig and its position in space) can the full camera model (eq. 3.4) be estimated from a single image projection. For example, it is worth noticing that if the calibration rig is planar (as shown on FIG. 3.1-a) the optical center c cannot be estimated (the two coordinates c_x and c_y). Therefore, in such cases, it is necessary to reduce the camera model to fewer intrinsic parameters and fix the optical center in the center of the image. Further discussions on the camera model observability are presented.

Closed-Form Solution in B-Dual-Space Geometry

[0209] This section demonstrates how one may easily retrieve closed-form expressions for intrinsic and extrinsic camera parameters using the dual-space formalism as a fundamental mathematical tool. The method is based on using vanishing points and vanishing lines. The concept of using vanishing points for camera calibration is not new (most of the related work on this topic may probably be found in the art. Therefore, this does not to state new concepts or theories on calibration, but rather illustrate the convenience of the dual-space formalism by applying it to the problem of calibration. We show here that this formalism enables us to keep the algebra simple and compact while exploiting all the geometrical constraints present in the scene (in the calibration rig). That will also lead us to derive properties regarding the observability of several camera models under different geometrical configuration of the setup, and types of calibration rig used (2D or 3D). Most related work on that topic only deal with simple camera model (unique focal length) and extract the extrinsic parameters through complex 3D parameterization (using Euler angles). Other standard methods for deriving explicit solutions for camera calibration were presented by Abdel-Aziz and Karara and Tsai. These methods are based on estimating, in a semi-linear way, a set of parameters that is larger than the real original set of unknowns and do not explicitly make use of all geometrical properties of the calibration rig.

[0210] The method that we disclose here involves very compact algebra, uses intuitive and minimal parameterizations, and naturally allows to exploit all geometrical properties present in the observed three-dimensional scene (calibration rig). In addition, our approach may be directly applied to natural images that do not contain a special calibration grid (such as pictures of buildings, walls, furniture . . . ).

[0211] Once it is computed, the closed-form solution is then fed to the non-linear iterative optimizer as an initial guess for the calibration parameters. This final optimization algorithm is inspired from the method originally presented by Tsai including lens distortion (see equation 3.7). The purpose of that analysis is to provide a good initial guess to the non-linear optimizer, to better insure convergence, and check for the consistency of the results.

[0212] We will first consider the case of a calibration when using a planar rig (a 2D grid), and then generalize the results to 3D rigs (such as a cube). In those two cases, different camera models will be used.

3.2.1. When Using a Planar Calibration Rig

[0213] Consider the calibration image shown in FIG. 4A. Assuming no lens distortion (k_c=0) and no image noise, the grid may be summarized by its four extreme corners on the image (intuitively, one may localize all the inside grid corners from those four points by simple perspective warping). In practice, all points will be used in order to be less sensitive to image noise, however the principle remains the same. Then, the basic observed pattern is a perspective view of a rectangle of known dimensions L×W. Without loss of generality, we can also assume that this rectangle is a square. The reason for that is that through a similar perspective image warping, it is always possible to convert a perspective view of a rectangle into a perspective view of a square, given that the dimensions of the original rectangle are known (actually, only the ratio W/L is necessary).

[0214] FIG. 15 shows a perspective image of a square ABCD. The four points {overscore (x)}₁, {overscore (x)}₂, {overscore (x)}₃, and {overscore (x)}₄ are the coordinate vectors of the detected corners of the square on the image plane after normalization. This means that the {overscore (x)} vectors are computed from the pixel coordinates of the points after subtraction of the optical center coordinates (c_x, c_y) (in pixel) and scaling by the inverse of the focal length (in pixel as well). To model the aspect ration in x and y, one can assume two distinct focal lengths f_x and f_y in both image directions (to account for non-square CCD pixels).

[0215] In the case of calibration from planar rigs, it is known that the optical center position (c_x, c_y) cannot be estimated. Therefore, we will keep it fixed at the center of the image, and take it out of the set of unknowns. The resulting intrinsic parameters to be estimated are therefore f_x and f_y. Let {overscore (p)}_i≃[p_xi p_yi 1]^T (i=1, . . . , 4) be the pixel locations of the corners after subtraction of the optical center (in homogeneous coordinates). Then one can extract the {overscore (x)} vectors through a linear operation involving the focal lengths f_x and f_y: for i=1, . . . , 4,

[0216] $\begin{array}{cc}{\stackrel{\_}{x}}_i\simeq \left[\begin{array}{ccc}1/f_x& 0& 0\\ 0& 1/f_y& 0\\ 0& 0& 1\end{array}\right]{\stackrel{\_}{p}}_i=K{\stackrel{\_}{p}}_i& \left(3.8\right)\end{array}$
where K is the intrinsic camera matrix containing the intrinsic parameters (f_x and f_y). Let us now extract the set of independent constraints attached to the observation in order to estimate the focal lengths (hence the camera matrix K).

[0217] FIG. 15 shows the set of corner points {overscore (x)}_i on the image plane. Following proposition 5 of section 2.2.2, lines {overscore (λ)}_i(i=1, . . . , 4) are used to infer the two vanishing points V₁ and V₂ in order to recover the projection {overscore (λ)}_H of the horizon line H associated to the plane Π_d. The derivation is as follows:

[0218] $\begin{array}{cc}\begin{array}{c}\begin{array}{c}{\stackrel{\_}{\lambda }}_1\simeq {\stackrel{\_}{x}}_1\times {\stackrel{\_}{x}}_2\\ {\stackrel{\_}{\lambda }}_2\simeq {\stackrel{\_}{x}}_3\times {\stackrel{\_}{x}}_4\end{array}\}{V}_1\simeq {\stackrel{\_}{\lambda }}_1\times {\stackrel{\_}{\lambda }}_2\\ \begin{array}{c}{\stackrel{\_}{\lambda }}_3\simeq {\stackrel{\_}{x}}_2\times {\stackrel{\_}{x}}_3\\ {\stackrel{\_}{\lambda }}_4\simeq {\stackrel{\_}{x}}_4\times {\stackrel{\_}{x}}_1\end{array}\}{V}_2\simeq {\stackrel{\_}{\lambda }}_3\times {\stackrel{\_}{\lambda }}_4\end{array}\}{\stackrel{\_}{\lambda }}_H\simeq V_1\times V_2& \left(3.9\right)\end{array}$
where x is the standard vector product in ³. Notice that in order to keep the notation clear, we abusively used V₁ and V₂ to refer to the homogeneous coordinates of the vanishing points on the image plane (quantities similar to the {overscore (x)}_i's using homogeneous coordinates). It is important to keep in mind that all equalities are defined “up to scale.” For example, any vector proportional to {overscore (x)}₁×{overscore (x)}₁ would be a good representative for the same line {overscore (λ)}₁. The same observation holds for the coordinate vectors of the vanishing points and that of the horizon line.

[0219] Yet, the normalized coordinates {overscore (x)}_i of the corners are not directly available, only the pixel coordinates {overscore (p)}_i. However, all {overscore (x)}_i's can be retrieved from the {overscore (p)}_i's through the linear equation 3.8. We will use of the following statement whose proof may be found in [30]:

[0220] Claim 1: Let K be any 3×3 matrix, and ū and {overscore (v)} any two 3-vectors. Then the following relation holds:
(Kū)×(K{overscore (v)})=K*(ū×{overscore (v)})
where K* is the adjoint of K (or the matrix of cofactors of K). Note that if K is invertible (which is the case here), then K*=det(K)(K^T)⁻¹, and consequently K**∝K.

[0221] Using that claim, the camera matrix K (or K*) may be factored out of the successive vector products of equations 3.9, yielding:

[0222] $\begin{array}{c}\begin{array}{c}{\stackrel{\_}{\lambda }}_1\simeq K^{*}{\stackrel{\_}{\lambda }}_1^p\\ {\stackrel{\_}{\lambda }}_2\simeq K^{*}{\stackrel{\_}{\lambda }}_2^p\end{array}\}{V}_1\simeq {\mathrm{KV}}_1^p\\ \begin{array}{c}{\stackrel{\_}{\lambda }}_3\simeq K^{*}{\stackrel{\_}{\lambda }}_3^p\\ {\stackrel{\_}{\lambda }}_4\simeq K^{*}{\stackrel{\_}{\lambda }}_4^p\end{array}\}{V}_2\simeq {\mathrm{KV}}_2^p\end{array}\}{\stackrel{\_}{\lambda }}_H\simeq K^{*}{\stackrel{\_}{\lambda }}_H^p,$
where {overscore (λ)}₁^p, {overscore (λ)}₂^p, {overscore (λ)}₃^p, {overscore (λ)}₄^p, V₁^p, V₂^p and {overscore (λ)}_H^p are line and point coordinate vectors on the image plane in pixel (directly computed from the pixel coordinates {overscore (p)}₁, {overscore (p)}₂, {overscore (p)}₃ and {overscore (p)}₄):

[0223] $\begin{array}{c}\begin{array}{c}{\stackrel{\_}{\lambda }}_1^p\simeq {\stackrel{\_}{p}}_1\times {\stackrel{\_}{p}}_2\\ {\stackrel{\_}{\lambda }}_2^p\simeq {\stackrel{\_}{p}}_3\times {\stackrel{\_}{p}}_4\end{array}\}{V}_1^p\simeq {\stackrel{\_}{\lambda }}_1^p\times {\stackrel{\_}{\lambda }}_2^p\\ \begin{array}{c}{\stackrel{\_}{\lambda }}_3^p\simeq {\stackrel{\_}{p}}_2\times {\stackrel{\_}{p}}_3\\ {\stackrel{\_}{\lambda }}_4^p\simeq {\stackrel{\_}{p}}_4\times {\stackrel{\_}{p}}_1\end{array}\}{V}_2^p\simeq {\stackrel{\_}{\lambda }}_3^p\times {\stackrel{\_}{\lambda }}_4^p\end{array}\}{\stackrel{\_}{\lambda }}_H^p\simeq V_1^p\times V_2^p$
The step of inferring the vanishing points V₁ and V₂ from the pairs of lines {{overscore (λ)}₁, {overscore (λ)}₂} and {{overscore (λ)}₃, {overscore (λ)}₄} made use of the fact that ABCD is a parallelogram (proposition 5). Using proposition 6 (in section 2.2.2), one naturally enforce orthogonality of the pattern by stating that the two vanishing points V₁ and V₂ are mutually orthogonal (see FIG. 2.11):
V₁⊥V₂⇄(KV₁^p)⊥(KV₂^p)⇄(V₁^p)^T(K^TK) (V₂^p)=0  (3.10)
That provides one scalar constraint in the focal lengths f_x and f_y:

[0224] $\begin{array}{cc}\frac{a_1{a}_2}{f_x^2}+\frac{b_1{b}_2}{f_y^2}+c_1{c}_2=0& \left(3.11\right)\end{array}$
where a₁, a₂, b₁, b₂, c₁ and c₃ are the known pixel coordinates of the vanishing points V₁^p and V₂^p: V₁^p≃[a₁ b₁ c₁]^T and V₂^p≃[a₂ b₂ c₂]^T. Notice that equation 3.11 constraints the two square focals (f_x²,f_y²) to lie on a fixed hyperbola. Finally, the parallelogram ABCD is not only a rectangle, but also a square. This means that its diagonals (AC) and (BD) are also orthogonal (see FIG. 15). This constraint is exploited by enforcing the two vanishing points attached to the diagonal V₃ and V₄ to be mutually orthogonal (proposition 6). Those points are extracted from intersecting the two diagonal lines {overscore (λ)}₅ and {overscore (λ)}₆ with the horizon line {overscore (λ)}_H (see FIG. 15). Following the same process of factoring the K matrix (or K*) out of every successive vector product, one obtains:
{overscore (λ)}₅≃K*λ₅^p→V₃≃KV₃^p
{overscore (λ)}₆≃K*λ₆^p→V₄≃KV₄^p
where V₃^p and V₄^p are the two pixel coordinates of the vanishing points V₃ and V₄ (pre-computed from the pixel coordinates of the corner points):
{overscore (λ)}₅^p≃{overscore (p)}₁×{overscore (p)}₃→V₃^p≃{overscore (λ)}₅^p×{overscore (λ)}_H^p
{overscore (λ)}₆^p≃{overscore (p)}₂×{overscore (p)}₄→V₄^p≃{overscore (λ)}₆^p×{overscore (λ)}_H^p
Then, the orthogonality of V₃ and V₄ yields (V₃^p)^T (K^TK) (V₄^p)=0, or:

[0225] $\begin{array}{cc}\frac{a_3{a}_4}{f_x^2}+\frac{b_3{b}_4}{f_y^2}+c_3{c}_4=0& \left(3.12\right)\end{array}$
where a₃, a₄, b₃, b₄, C₃ and c₄ are the known pixel coordinates of V₃^p and V₄^p: V₃^p≃[a₃ b₃ c₃]^T and V₄^p≃[a₄ b₄ c₄]^T. This constitutes a second constraint on f_x and f_y (a second hyperbola in the (f_x², f_y²) plane), which can be written together with equation 3.11 in a form of a linear equation in ū=[u₁ u₂]^T=[1/f_x² 1/f_y²]^T:

[0226] $𝒜\stackrel{\_}{u}=\stackrel{\_}{b}\mathrm{with}𝒜=\left[\begin{array}{cc}{a}_1{a}_2& b_1{b}_2\\ a_3{a}_4& b_3{b}_4\end{array}\right]\mathrm{and}\stackrel{\_}{b}=-\left[\begin{array}{c}{c}_1{c}_2\\ c_3{c}_4\end{array}\right]$
If is invertible, then both focals f_x and f_y may be recovered explicitly:

[0227] $\stackrel{\_}{u}=\left[\begin{array}{c}1/f_x^2\\ 1/f_y^2\end{array}\right]={𝒜}^{-1}\stackrel{\_}{b}\Rightarrow \{\begin{array}{c}{f}_x=\sqrt{1/u_1}\\ f_y=\sqrt{1/u_2}\end{array}\text{or:}{f}_x=\sqrt{\frac{a_1{a}_2{b}_3{b}_4-a_3{a}_4{b}_1{b}_2}{b_1{b}_2{c}_3{c}_4-b_3{b}_4{c}_1{c}_2}}{f}_y=\sqrt{\frac{a_1{a}_2{b}_3{b}_4-a_3{a}_4{b}_1{b}_2}{a_3{a}_4{c}_1{c}_2-a_1{a}_2{c}_3{c}_4}}$
under the condition u₁>0 and u₂>0.

[0228] If is not invertible (or a₁a₂b₃b₄−a₃a₄b₁b₂=0), then both focals (f_x, f_y) cannot be recovered. However, if is of rank one (i.e. it is not the zero matrix), then a single focal length model f_c=f_x=f_y may be used. The following claim gives a necessary and sufficient condition for to be rank one:

[0229] Claim 2: The matrix is rank one if and only if the projection {overscore (λ)}_H of the horizon line is parallel to either the x or y axis on the image plane (its first or second coordinate is zero, not both), or crosses the origin on the image plane (its last coordinate is zero). Since the matrix K is diagonal, this condition also applies to the horizon line in pixel coordinates {overscore (λ)}_H^p.

[0230] Corollary: Since {overscore (λ)}_H is proportional to the surface normal vector {overscore (n)}_h (from proposition 2 in section 2.2.2), this degeneracy condition only depends upon the 3D orientation of the plane Π_h with respect to the camera, and not the way the calibration grid is positioned onto it (this is intrinsic to the geometry of the setup).

[0231] In such a rank-one degenerate case, the reduced focal model is acceptable. Then both constraint equations 3.11 and 3.12 may be written as a function of a unique focal f_c and follows:

[0232] $\left[\begin{array}{c}{c}_1{c}_2\\ c_3{c}_4\end{array}\right]f_c^2=-\left[\begin{array}{c}{a}_1{a}_2+b_1{b}_2\\ a_3{a}_4+b_3{b}_4\end{array}\right]$
which may be solved in a least squares fashion, yielding the following solution:

[0233] $\begin{array}{cc}{f}_c=f_x=f_y=\sqrt{-\frac{c_1{c}_2\left(a_1{a}_2+b_1{b}_2\right)+c_3{c}_4\left(a_3{a}_4+b_3{b}_4\right)}{c_1^2{c}_2^2+c_3^2{c}_4^2}}& \left(3.13\right)\end{array}$
Alternative estimates may be derived by directly solving for either one of the constraint equations (3.11 or 3.12) taking f_x=f_y=f_c. This may be more appropriate in the case where one of the four vanishing points V_k is at infinity (corresponding to c_k=0). It is then better to drop the associate constraint and only consider the remaining one (remark: having a vanishing point at infinity does not necessarily mean that the matrix is singular). Since the vector {overscore (λ)}_H is parallel to the normal vector {overscore (n)}_h of the ground plane Π_h, this rank-one degeneracy case corresponds to having one of the camera axis X_c, Y_c or Z_c parallel to the calibration plane Π_h.

[0234] Note that if two vanishing points are at infinity, then the projection of the entire horizon line, {overscore (λ)}_H is also at infinity on the image plane (its two first coordinates are zero). This occurs only when the calibration plane Π_h is strictly parallel to the image plane (or {overscore (n)}_h=[0 0 1]^T), which is known to be a degenerate case where there exists no solution for calibration.

[0235] In the case where the planar pattern is a rectangle, but not necessarily a square (or equivalently, the aspect ratio of the rectangle is not known), then the diagonal constraint is not available (equation 3.12). In that case, only equation 3.11 is available to estimate focal length. It is therefore necessary to use a reduced single focal model f_c=f_x=f_x:

[0236] $\begin{array}{cc}{f}_c=f_x=f_y=\sqrt{-\frac{a_1{a}_2+b_1{b}_2}{c_1{c}_2}}& \left(3.14\right)\end{array}$
This expression will be used in a calibration experiment illustrated in FIG. 3.5.

[0237] Once the camera matrix K is estimated, the normalized horizon vector {overscore (λ)}_H≃K*{overscore (λ)}_H^p may be recovered. From proposition 2, this vector is known to be proportional to the coordinate vector {overscore (ω)}_h of Π_h (or its normal vector {overscore (n)}_h). Therefore, this directly provides the orientation in 3D space of the ground plane. The only quantity left to estimate is then its absolute distance d_h to the camera center, or equivalently the norm ∥{overscore (ω)}_h∥=1/d_h. This step may be achieved by making use of the known area of the square ABCD and applying an inverse perspective projection on it (possible since the orientation of Π_h is known).

[0238] Implementation details: In principle, only the four extreme corners of the rectangular pattern are necessary to localize the four vanishing points V₁^p, V₂^p, V₃^p, and V₄^p. However, in order to be less sensitive to pixel noise, it is better in practice to make use of all the detected corners on the grid (points extracted using the Harris corner finder). This aspect is especially important given that vanishing point extraction is known to be very sensitive to noise in the corner point coordinates (depending on amount of depth perspective in the image). One possible approach is to fit a set of horizontal and vertical lines to the pattern points, and then recover the two vanishing points V₁^p, V₂^p by intersecting them in a least squares fashion. Once these two points are extracted, the position of the extreme corners of the rectangular pattern may be corrected by enforcing the four extreme edges of the grid to go through those vanishing points. The next step consists of warping the perspective view of the rectangle into a perspective view of a square (making use of the known aspect ration of the original rectangle). The two remaining vanishing points V₃^p and V₄^p may then be localized by intersecting the two diagonals of this square with the horizon line {overscore (λ)}_H^p connecting V₁^p and V₂^p. Once those four points are extracted, the focal length may be estimated, together with the plane coordinate vector {overscore (ω)}_h following the method described earlier (using a one or two focal model).

When Using a 3D Calibration Rig

[0239] Let us generalize the results to the case where a 3D rig of the type in FIG. 5 is used for calibration. FIG. 16 shows a perspective view of a cube in 3D. From that image, one may extract seven vanishing points V₁, V₂, . . . V₇. Similarly to the case of a planar square, this set of points must satisfy five orthogonality properties: V₁⊥V₂, V₁⊥V₃, V₂⊥V₃, V₄⊥V₅ and V₆⊥V₇. Then, similarly to equation 3.10, we can write a set of five scalar constraints on the pixel coordinates of the vanishing points:

[0240] $\begin{array}{cc}\{\begin{array}{c}{V}_1\perp V_2\Rightarrow {\left(V_1^p\right)}^T\left(K^{T}K\right)\left(V_2^p\right)=0\\ V_1\perp V_3\Rightarrow {\left(V_1^p\right)}^T\left(K^{T}K\right)\left(V_3^p\right)=0\\ V_2\perp V_3\Rightarrow {\left(V_2^p\right)}^T\left(K^{T}K\right)\left(V_3^p\right)=0\\ V_4\perp V_5\Rightarrow {\left(V_4^p\right)}^T\left(K^{T}K\right)\left(V_5^p\right)=0\\ V_6\perp V_7\Rightarrow {\left(V_6^p\right)}^T\left(K^{T}K\right)\left(V_7^p\right)=0\end{array}& \left(3.15\right)\end{array}$
Where K is the intrinsic camera matrix and V_i^p≃[a_i b_i c_i]^T (i=1, . . . ,7) are the pixel coordinate vectors of the vanishing points (see FIG. 16). Note that the first three constraints in (3.15) enforce mutual orthogonality of the faces of the cube, whereas the last two force the left and fight faces (and therefore all the others) to be squares.

[0241] Given those five independent constraints, one should be able to estimate a full 5 degrees of freedom (DOF) camera model for metric calibration including two focal lengths (f_x and f_y in pixels), the optical center coordinates (c_x and c_y in pixels) and the skew factor α (see equation 3.2). In that case, the intrinsic camera matrix K takes its most general form [31]:

[0242] $K=\left[\begin{array}{ccc}1/f_x& \alpha /f_x& -c_x/f_x\\ 0& 1/f_y& -c_y/f_y\\ 0& 0& 1\end{array}\right]$
This model matches precisely the notation introduced in equation (3.2). Then, the semi-positive definite matrix K^T K may be written as follows:

[0243] $\begin{array}{cc}{K}^{T}K=\frac{1}{f_x^2}\left[\begin{array}{ccc}1& \alpha & -c_x\\ \alpha & a^2+{\left(f_x/f_y\right)}^2& -\alpha c_x-{c_y\left(f_x/f_y\right)}^2\\ -c_x& -\alpha c_x-{c_y\left(f_x/f_y\right)}^2& f_x^2+c_x^2+{c_y^2\left(f_x/f_y\right)}^2\end{array}\right]& \left(3.16\right)\\ =\frac{1}{f_x^2}\left[\begin{array}{ccc}1& u_5& -u_3\\ u_5& u_2& -u_4\\ -u_3& -u_4& u_1\end{array}\right]& \left(3.17\right)\end{array}$
Notice that the vanishing point constraints (3.15) are homogeneous. Therefore, one can substitute K^T K by its proportional matrix f_x² K^T K. Doing so, the five constraints listed in equation 3.15 are linear in the vector ū=[u₁ . . . u₅]^T. Indeed, for (i, j)ε{(1,2), (1,3), (2,3), (4,5), (6,7)}, we have:
[−c_ic_j−b_ib_j (a_ic_j+a_jc_i) (b_ic_j+b_jc_i)−(a_ib_j+a_jb_i)]ū=a_ia_j,  (3.18)
Therefore, this set of 5 equations may be written in a form of a linear system of 5 equations in variable ū:
ū={overscore (b)}  (3.19)
where is a 5×5 matrix, and {overscore (b)} a 5-vector:

[0244] $𝒜=\left[\begin{array}{ccccc}-c_1{c}_2& b_1{b}_2& \left(a_1{c}_2+a_2{c}_1\right)& \left(b_1{c}_2+b_2{c}_1\right)& -\left(a_1{b}_2+a_2{b}_1\right)\\ -c_1{c}_3& b_1{b}_3& \left(a_1{c}_3+a_3{c}_1\right)& \left(b_1{c}_3+b_3{c}_1\right)& -\left(a_1{b}_3+a_3{b}_1\right)\\ -c_2{c}_3& b_2{b}_3& \left(a_2{c}_3+a_3{c}_2\right)& \left(b_2{c}_3+b_3{c}_2\right)& -\left(a_2{b}_3+a_3{b}_2\right)\\ -c_4{c}_5& b_4{b}_5& \left(a_4{c}_5+a_5{c}_4\right)& \left(b_4{c}_5+b_5{c}_4\right)& -\left(a_4{b}_5+a_5{b}_4\right)\\ -c_6{c}_7& b_6{b}_7& \left(a_6{c}_7+a_7{c}_6\right)& \left(b_6{c}_7+b_7{c}_6\right)& -\left(a_6{b}_7+a_7{b}_6\right)\end{array}\right],\stackrel{\_}{b}=\left[\begin{array}{c}{a}_1{a}_2\\ a_1{a}_3\\ a_2{a}_3\\ a_4{a}_5\\ a_6{a}_7\end{array}\right]$

[0245] If the matrix is invertible, this system admits a solution ū=⁻¹{overscore (b)}. Finally, the intrinsic camera parameters are retrieved from ū as follows:

[0246] $\begin{array}{cc}\{\begin{array}{c}{f}_x=\sqrt{u_1-u_3^2-\frac{{\left(u_4-u_3{u}_5\right)}^2}{u_2-u_2^5}}\\ f_y=f_x/\sqrt{u_2-u_5^2}\\ c_x=u_3\\ c_y=\frac{u_4-u_3{u}_5}{u_2-u_2^5}\\ \alpha =u_5\end{array}& \left(3.20\right)\end{array}$
This final step consisting of de-embedding the intrinsic parameters from the vector ū is equivalent to a Choleski decomposition of the matrix K^T K in order to retrieve K.