Method and system for determining projections in non-central catadioptric optical systems

This invention relates generally to catadioptric optical systems, and more particularly to determining a projection in non-central catadioptric optical systems.

A catadioptric optical system combines refraction and reflection principles, usually via lenses (dioptrics) and curved mirrors (catoptrics). The catadioptric system includes camera imaging reflectors or refractors enabling wide field-of-view (FOV) imaging. The catadioptric systems have been used in a wide range of applications, including panoramic imaging and visualization, wide-angle reconstruction, surveillance, and mobile robot and car navigation. The catadioptric system can be central or non-central.

Central Catadioptric System

Central catadioptric systems use a single camera-mirror pair arranged to enable an effective single viewpoint, i.e., all rays of light forming an image acquired by the camera sensor intersect at one point. Examples of the central catadioptric systems include a perspective camera placed on one of the foci of a hyperbolic or elliptical mirror, and an orthographic camera placed on an axis of a parabolic mirror.

Non-Central Catadioptric System

Non-central catadioptric systems are widely used in computer vision applications. Examples of non-central catadioptric systems include a perspective camera placed outside of a spherical mirror, and configurations wherein the camera is not placed on the foci of a hyperbolic or elliptical mirror. In contrast with the central catadioptric systems, in the non-central catadioptric systems, the rays do not generally intersect at one point. Instead, the rays intersect along a line, or the rays are tangent to a circle, or to a more complex shape.

In a number of applications, it is important to model non-central catadioptric systems, which, in turn, requires determining a three-dimensional (3D) projection of a point in a scene (PS) to a center of projection (COP) of the camera of the catadioptric system. The non-central catadioptric system does not have an effective center of projection. The COP refers to the center of projection of the physical perspective camera used in a catadioptric system.

The 3D projection maps the three-dimensional PS to a two-dimensional (2D) pixel of an image plane of the camera of the catadioptric system.

For example, if the catadioptric system includes a reflector, such as mirror, the projection of the PS onto an image plane of the camera requires computing a path of the ray of light from that point to the COP via mirror reflection. Thus, the point of reflection on a surface of the mirror needs to be determined. Similarly, if the catadioptric system includes the refractor, e.g., a refractive sphere, two points of refraction need to be determined to model the projection.

Analytical solutions of projections for central catadioptric systems are known. However, there is no analytical solution of projection for non-central catadioptric systems.

Several conventional methods approximate non-central catadioptric systems as the central catadioptric system that enables analytical solution for projection. However, those methods lead to inaccuracies such as skewed 3D estimation.

Alternative methods use iterative non-linear optimization by initializing the point of reflection or refraction using the central approximation. However, those methods are time-consuming and inappropriate initialization leads to incorrect solutions. Yet another method uses a general linear camera representation for locally approximating a non-central catadioptric camera with an affine model that allows analytical projection, but this method also introduces approximation.

Accordingly, it is desired to provide an analytical solution of the projection for non-central catadioptric systems. It is also desired to determine analytically a three-dimensional (3D) location of at least one folding point of a ray from the PS to the COP of non-central catadioptric system.

Embodiments of invention are based on a realization that a three-dimensional (3D) projection of a point in a scene (PS) for particular configurations of a non-central catadioptric optical system can be determined analytically by mapping a 3D structure of the catadioptric system on a two-dimensional (2D) plane defined by an axis of symmetry of a folding optical element of the catadioptric system and the PS.

The folding optical element is a reflector or refractor having a quadric surface rotationally symmetric around an axis of symmetry of the surface. A center of projection (COP) of a perspective camera is placed on the axis of symmetry. The problem of determining folding, e.g., reflection/refraction points in such catadioptric cameras is solved by formulating the problem on a 2D plane defined by the axis of symmetry and the 3D scene point, and using the law of reflection/refraction as the constraints on the plane.

Some embodiments determine a reflection points on the surface of the mirror by solving a 6th degree equation for a general conic mirror. For a spherical mirror, the complexity of the equation is reduced to a 4th degree equation, resulting in a closed form solution. The analytical forward projection avoids approximations as well as iterative solution and can be used for accurate and fast 3D reconstruction via bundle adjustment. Embodiments achieve a two order of magnitude speed up over conventional methods using iterative forward projection.

Other embodiments of the invention disclose that an optical path from a given 3D point to a given viewpoint via a refractive sphere can be obtained by solving a 10th degree equation. Thus, similar to mirrors, refractive spheres can also be used for 3D reconstruction by combining the forward projection equation in a bundle adjustment.

For example, one embodiment discloses a method for determining a three-dimensional (3D) location of at least one folding point of a ray between a point in a scene (PS) and a center of projection (COP) of a camera of a catadioptric system, wherein the catadioptric system includes the camera arranged at a distance from a surface of a folding optical element, wherein the folding optical element is selected from a reflector or a refractor, wherein the folding point is on the surface and is caused by a reflection or a refraction of the ray on the surface such that the folding point partitions the ray into an incoming ray and an outgoing ray, and wherein the PS and the COP are identified by 3D locations, comprising the steps of: acquiring a configuration of the catadioptric system, wherein the catadioptric system is non central, the surface is a quadric surface rotationally symmetric around an axis of symmetry of the surface, and wherein the COP is arranged on the axis of symmetry; mapping the surface, and the 3D locations of the PS and the COP on a two-dimensional (2D) plane defined by the axis of symmetry and the PS to produce a conic and 2D locations of the PS and COP on the 2D plane, wherein the conic is a parameterization of the surface on the 2D plane; determining a 2D location of the folding point on the 2D plane based on the conic, the 2D locations of the PS and the COP, and at least one constraint on the incoming ray and the outgoing ray; and determining the 3D location of the folding point from the 2D location of the folding point on the 2D plane, wherein the steps of the method are performed by the processor.

Another embodiment discloses a catadioptric system configured for determining a three-dimensional (3D) location of at least one folding point of a ray between a point in a scene (PS) and a center of projection (COP) of the catadioptric system, wherein the PS and the COP are identified by 3D locations, and the catadioptric system is non central, comprising: a folding optical element, wherein the folding point is caused by folding of the ray on a surface of the folding optical element, wherein the surface is a quadric surface rotationally symmetric around an axis of symmetry; a camera arranged at a distance from the surface, wherein the COP of the catadioptric system is a COP of the camera and arranged on the axis of symmetry; means for mapping the surface, and the 3D locations of the PS and the COP on a two-dimensional (2D) plane defined by the axis of symmetry and the PS to produce a conic and 2D locations of the PS and COP on the 2D plane, wherein the conic is a parameterization of the surface on the 2D plane; a processor for determining a 2D location of the folding point on the 2D plane based on the conic, the 2D locations of the PS and the COP; and means for determining the 3D location of the folding point from the 2D location of the folding point on the 2D plane.

Yet another embodiment discloses a method for determining a three-dimensional (3D) location of at least one folding point of a ray between a point in a scene (PS) and a center of projection (COP) of a catadioptric system, wherein the PS and the COP are identified by 3D locations, and the catadioptric system is non central, comprising the steps of: providing a folding optical element, wherein the folding point is caused by folding of the ray on a surface of the folding optical element, wherein the surface is a quadric surface rotationally symmetric around an axis of symmetry; providing a camera arranged at a distance from the surface, wherein the COP of the catadioptric system is a COP of the camera and arranged on the axis of symmetry; mapping the surface, and the 3D locations of the PS and the COP on a two-dimensional (2D) plane defined by the axis of symmetry and the PS to produce a conic and 2D locations of the PS and COP on the 2D plane, wherein the conic is a parameterization of the surface on the 2D plane; determining a 2D location of the folding point on the 2D plane based on the conic, the 2D locations of the PS and the COP; and determining the 3D location of the folding point from the 2D location of the folding point on the 2D plane.

FIGS. 1A-B are a schematic and a block diagram of a method for determining a folding point on the catadioptric optical system according to embodiments of an invention;

FIG. 2 is a schematic of a method for determining refraction points in a system including a refractive sphere according to the embodiments of the invention;

FIGS. 3A-3C are schematics of light path obtained by solving a forward projection for a refractive sphere according to the embodiments of the invention;

FIG. 4 is a schematic of back projection for spherical mirror according to the embodiments of the invention; and

FIG. 5 is a graph of epipolar curves for spherical mirror according to the embodiments of the invention.

Method and System Overview

Embodiments of invention are based on a realization that a three-dimensional (3D) projection of a point in a scene (PS) for particular configurations of a non-central catadioptric optical system can be determined analytically by mapping a 3D structure of the catadioptric system on a two-dimensional (2D) plane defined by an axis of symmetry of the catadioptric system and the PS.

Such configurations include non-central catadioptric systems having a camera arranged at a distance from a surface of a reflector or a refractor, wherein the surface is quadric and rotationally symmetric around an axis of symmetry, and a center of projection (COP) of the camera used in the catadioptric system is arranged on the axis of symmetry. The 2D plane is defined by the axis of symmetry, and the PS and 2D solution of the projection represents the 3D projection, in part, due to the rotational symmetry of the catadioptric system.

FIG. 1A shows a block diagram of a method according embodiments of the invention. The method determines a three-dimensional (3D) location 199 of at least one folding point of a ray between a PS, e.g., the PS 130 , and a COP, e.g., the COP 120 , of the catadioptric system 171 having a camera, e.g., the camera 121 , arranged at a distance from a surface, e.g., the surface 106 of the optical folding element, wherein the folding point is on the surface and is caused by folding of the ray on the surface such that the folding point partitions the ray into an incoming ray and an outgoing ray, and wherein the PS and the COP are identified by 3D locations 176 . The steps of the method are performed by a processor 101 as known in the art.

A configuration 175 of the catadioptric system is acquired 170 , wherein the catadioptric system is non central, the surface of the reflector or the refractor is a quadric surface rotationally symmetric around an axis of symmetry, e.g., the axis 110 , and wherein the COP 120 is positioned on the axis of symmetry. In one embodiment, the camera is a pinhole camera. In various embodiments the configuration 175 is configuration of existing catadioptric system or a model of the catadioptric system.

According to aforementioned realization, the surface, and the 3D locations of the PS and the COP are mapped 180 on a 2D plane, e.g., the plane 140 , defined by the axis of symmetry and the PS to produce the conic 105 ′ and 2D locations 186 of the PS and COP on the 2D plane, wherein the conic is a parameterization of the surface on the 2D plane.

A 2D location 191 of the folding point on the 2D plane is determined 190 based on the conic, the 2D locations of the PS and the COP, and at least one constraint 193 on the incoming ray and the outgoing ray defined by a law of reflection or refraction. For example, in one embodiment, the catadioptric system includes the reflector, the folding point is a point of reflection of the ray from the 3D surface, and the constraint is a law of reflection. In one variation of this embodiment, the reflector is a spherical mirror, and the axis of symmetry passes through a center of the spherical mirror and the COP.

In another embodiment, the catadioptric system includes the refractor, the folding point is a point of refraction of the ray from the 3D surface, and the constraint is a law of refraction. In one variation of this embodiment, the refractor is a refractive sphere, and the axis of symmetry passes through a center of the refractive sphere and the COP.

After, the 3D location of the folding point is determined, a 2D image projection of the PS can be computed according to

( p , q ) = ( f x ⁢ X f Z f + c x , f y ⁢ ⁢ Y f Z f + c y ) ,

wherein (p, q) are coordinates of the 2D image projection, (X f , Y f , Z f ) are coordinates of the folding point, (f x , f y ) are effective focal lengths of the camera in x and); directions, and (c x , c y ) is a 2D principal point of the camera.

Forward Projection for Quadric Mirrors

FIG. 1B shows an example of the catadioptric system according to one embodiment of the invention. The catadioptric system is non-central and includes a camera 121 , e.g., a perspective camera, arranged at the distance from the surface 106 of a folding optical element 105 selected from a reflector or a refractor. The camera is configured to image the surface. In this embodiment, catadioptric system includes the reflector, i.e., a mirror. Other embodiments include a refractor in place of the reflector, such that the catadioptric system includes at least one of the reflector and the refractor. The surface 106 is quadric and rotationally symmetric around an axis of symmetry 110 , and the COP 120 is arranged on the axis of symmetry.

The embodiments of the invention determine a 3D location of at least one folding point 160 of a ray connecting a point in a scene (PS) 130 and the COP 120 of the catadioptric system. The folding point of the ray is on the surface 106 . The folding point is caused by a reflection or a refraction of the ray on the surface such that the folding point partitions the ray into an incoming ray 131 and an outgoing ray 132 .

For the purpose of this description, the z axis of the 3D coordinate system is the axis of symmetry, e.g., the axis of the mirror. The camera 121 can be a pinhole camera placed at a distance d 122 from an origin 111 on the mirror axis, and P=[X, Y, Z] T is the PS, wherein X, Y, Z are coordinates of a 3D location of the PS in the 3D coordinate system. Because the mirror is rotationally symmetric, the mirror reflection of the PS is analyzed in a two-dimensional (2D) plane π 140 defined by the axis of symmetry and the PS.

Let (z 1 , z 2 ) be axes determining a local coordinate system of the 2D plane π. In this plane, a 2D location of the PS P is P=[u,v], wherein u is a first coordinate of the 2D location of the PS, u=S sin θ, and v is a second coordinate of the 2D location of the PS, v=Z, wherein Z is a coordinate for the axis corresponding to the axis of the symmetry, and where S=√{square root over (X 2 +Y 2 +Z 2 )} is a distance from the PS to the origin 111 and an angle θ=cos −1 (Z/S) is the angle 150 between the mirror axis and a line 151 from the origin to the PS.

In the plane π, the surface is parameterized on the 2D plane as a conic section 105 ′, herein after “conic” described by a function Az 2 2 +z 1 2 +Bz 2 =C, wherein A, B, C are parameters of the function that depend on a type of the quadric surface, as described in more details below. If the folding point m has a 2D location m=[x,y] T , then x=±√{square root over (C−By−Ay 2 )}. A vector v i of the incoming ray is v i =[x,y−d] T , and a normal vector n at the folding point m is n=[x,B/2+Ay] T . Using the law of reflection, a vector of the outgoing or reflected ray is v r =v i −2n(n T v i )/(n T n).

Because the outgoing ray passes through the point P, a function of y is f(y)=v r ×(p−m)=0, where × denotes a cross product. In one embodiment, a numerator of the function f(y) is factorized as uK 1 (y)+K 2 (y)√{square root over (C−By−Ay 2 )},

where K 1 (y) and K 2 (y) are reflection polynomials in y, defined as

K 1 ( y )= K 11 y 3 +K 12 y 2 +K 13 y+K 14 , K 2 ( y )= K 21 y 2 +K 22 y+K 23   (1)

and individual terms are given by

K 11 =4 A (1− A ), K 12 =4 B− 4 A ( d+Ad+ 2B)

K 13 =8 AC− 4 Bd− 3 B 2 −4 C− 4 ABd, K 14 =−dB 2 +4 CB+ 4 Cd,

K 21 =4( A− 1)( A ( d+v )+ B ), K 22 =8 C+ 2 B 2 +4 A (−2 C+B ( d+v )+2 dv ), and

K 23 =B 2 ( d+v )+4 B (− C+dv )−4 C ( v+d ).

Because the function f(y)=0, the square root term in Equation (1) are removed as

uK 1 ( y )=− K 2 ( y )√{square root over ( C−By−Ay 2 )} u 2 K 1 2 ( y )= K 2 2 ( y )( C−By−Ay 2 ).

Accordingly, the embodiments of the invention define and use a 6 th order forward projection (FP) equation in terms of the coordinate y

u 2 K 1 2 ( y )+ K 2 2 ( y )( Ay 2 +By−C )=0.  (2)

where u is the first element of the 2D coordinate of the PS, K 1 (y) and K 2 (y) are polynomials in y defined in Equation (1), and A, B, C are parameters for the conic equation.

For a given point P, solving Equation (2) results in six solutions for the coordinate y. The final solution is determined by checking a constraint on the incoming ray and the outgoing ray, e.g., the law of reflection and/or refraction, for each solution. For example, in embodiment that includes a mirror as shown in FIG. 1A , the final solution considers a constraint of a law of reflection, i.e.,

v r T n=−v i T n,

wherein v i is a vector representing the incoming ray, v r is a vector representing the outgoing ray, T is a transpose operator, n is a vector representing a normal of the surface at the folding point

Accordingly, the embodiments determine the 2D location of the folding point on the 2D plane based on the conic, the 2D locations of the PS and the COP, and at least one constraint on the incoming ray and the outgoing ray, and than determines the 3D location of the folding point from the 2D location of the folding point on the 2D plane.

For example, in the embodiment shown in FIG. 1B , the 3D location of the folding point is determined according to

xz 1 /∥z 1 ∥+yz 2 /∥z 2 ∥, wherein

X=sign ( u )√{square root over ( C−By−Ay 2 )}.

Various embodiments of the invention use the 6 th order FP equation described above to determine the 2D location of the folding point. However, for some types of the conics, the FP equation is simplified, as described below. The 3D location of the folding point is determined from the 2D location of the folding point on the 2D plane.

Forward Projection for Spherical Mirror

In one embodiment, the catadioptric system includes the spherical mirror, which allows for reducing the degree of the FP equation. Substituting the parameters A=1, B=0, C=r 2 in the FP equation, where r is a radius of the spherical mirror and d is a distance between the COP and a center of the sphere, results in a 4 th order forward projection equation

u 2 ( r 2 ( d+y )−2 dy 2 ) 2 −( r 2 −y 2 )( r 2 ( d+v )−2 dvy ) 2 =0.  (3)

Because the FP equation is of 4 th order, one embodiment determines a close form solution for the coordinate y in terms of radicals. Also, in this embodiment, the location of COP is not restricted. For any COP, e.g., a pinhole location, a new axis from the pinhole to a center of the spherical mirror is defined.

Degree of FP Equation for Several Quadric Reflectors

Table 1 shows the degree of FP equation for spherical (A=1, B=0, C>0), elliptical (B=0), hyperbolic (A<0, C<0) and parabolic (A=0, C=0) mirrors of non-central catadioptric system.

Forward Projection for Refractive Sphere

FIG. 2 shows a schematic of defining and using the forward projection equation for imaging via a refractive sphere according another embodiment of the invention. This embodiment uses the catadioptric systems that includes a refractive sphere 200 of radius r and a refractive index μ. For example, the refractive sphere of radius r is arranged at an origin 205 of a coordinate system, and a pinhole camera 210 is arranged at distance d from the origin. As described above the embodiments analyze the projection on a 2D plane 220 defined by the axis of symmetry 230 and the PS p 240 .

Points n 1 =[x,y] T and n 2 =[x 2 ,y 2 ] T are the folding points of the ray, i.e., a first refraction point 250 on the sphere has coordinates x, y and a second refraction point 255 on the sphere has coordinates x 2 , y 2 , and vectors v 1 , v 2 , and v 3 are vectors representing light path from the COP to the first refraction point, from the first refraction point to the second refraction point, and from the second refraction point to the PS, respectively.

Then v 1 =[x,y−d] T and n 1 T n 1 =n 2 T n 2 =r 2 .

Based on the incoming ray v i and a normal n at the surface separating mediums of refractive indexes μ 1 and μ 2 , the refracted ray v r is written in vector form according to

v r = av i + bn , where a = μ 1 μ 2 , b = - μ 1 ⁢ v i T ⁢ n ± μ 1 2 ⁡ ( v i T ⁢ n ) 2 - ( μ 1 2 - μ 2 2 ) ⁢ ( v i T ⁢ v i ) ⁢ ( n T ⁢ n ) μ 2 ⁡ ( n T ⁢ n ) . ( 15 ) Thus , v r T ⁢ n ∝ ± μ 1 2 ⁡ ( v i T ⁢ n ) 2 - ( μ 1 2 - μ 2 2 ) ⁢ ( v i T ⁢ v i ) ⁢ ( n T ⁢ n ) ,

wherein the sign is determined using another constraint, i.e., signs vectors of v r T n and v i T n are the same.

Because a tangent ray from the pinhole to the sphere is at y=r 2 /d, y≧r 2 /d for a valid refraction point. Thus, v 1 T n 1 =r 2 −dy≦0, and

The second refraction point n 2 equals n 1 +λv 2 for a constant λ, which is determined according to

r 2 =n 2 T n 2 =r 2 +λ 2 v 2 T v 2 +2λ v 2 T n 1 , λ=− 2 v 2 T n 1 /v 2 T v 2 ,  (17)

where

v 2 T n 1 =−√{square root over (( dy−r 2 ) 2 +r 2 (μ 2 −1)( d 2 −2 dy+r 2 ))}{square root over (( dy−r 2 ) 2 +r 2 (μ 2 −1)( d 2 −2 dy+r 2 ))}{square root over (( dy−r 2 ) 2 +r 2 (μ 2 −1)( d 2 −2 dy+r 2 ))}/μ

v 2 T v 2 =d 2 −2 dy+r 2 .

The outgoing refracted ray is v 3 =μv 2 +b 3 n 2 , for some b 3 . Due to symmetry of the sphere v 3 T n 2 =−v 1 T n 1 and v 2 T n 2 =−v 2 T n 1 . Accordingly, b 3 =(−v 1 T n 1 −μv 2 T n 1 )/r 2 .

Because, the outgoing refracted ray v 3 passes through the PS p=[u, v] T , v 3 ×(p−n 2 )=0. By substituting all the terms, we obtain the following equation

0= v 3 ×( p−n 2 ) 0 =K 1 ( x,y )+ K 2 ( x,y ) √{square root over (A)}+K 3 ( x,y ) A 3/2 ,  (18)

where A=d 2 μ 2 r 2 −d 2 x 2 −2dμ 2 r 2 y+μ 2 r 4 , and K 1 , K 2 and K 3 are refractive polynomials in x and y:

K 1 =d 3 μ 2 x 5 +ud 3 μ 2 x 4 +2 d 3 μ 2 x 3 y 2 +2 vd 3 μ 2 x 3 y+d 3 μ 2 xy 4 2 vd 3 μ 2 xy 3 −ud 3 μ 2 y 4 −2 ud 3 x 4 −4 vd 3 x 3 y +2 ud 3 x 2 y 2 −2 d 2 μ 2 x 5 −vd 2 μ 2 x 5 −ud 2 μ 2 x 4 y −4 d 2 μ 2 x 3 y 3 −6 vd 2 μ 2 x 3 y 2 +2 ud 2 μ 2 x 2 y 3 −2 d 2 μ 2 xy 5 −5 vd 2 μ 2 xy 4 +3 ud 2 μ 2 y 5 +2 vd 2 x 5 −2 ud 2 x 4 y +2 vd 2 x 3 y 2 −2 ud 2 x 2 y 3 +d μ 2 x 7 +ud μ 2 x 6 +3 d μ 2 x 5 y 2 +4 vd μ 2 x 5 y− 2 ud 2 x 4 y +2 vd 2 x 3 y 2 −2 ud 2 x 2 y 3 +d μ 2 x 7 +ud μ 2 x 6 +3 d μ 2 x 5 y 2 +4 vd μ 2 x 5 y − 3 ud μ 2 y 6 −v μ 2 x 7 +u μ 2 x 6 y −3 v μ 2 x 5 y 2 +3 u μ 2 x 4 y 3 −3 v μ 2 x 3 y 4 +3 u μ 2 x 2 y 5 −v μ 2 xy 6 +u μ 2 y 7

K 2 =2 vd 2 μ 2 x 3 −2 ud 2 μ 2 x 2 y +2 vd 2 μ 2 xy 2 −2 ud 2 μ 2 y 3 −2 ud 2 x 2 y −2 vd 2 xy 2 −4 vd μ 2 x 3 y −4 ud μ 2 x 2 y 2 −4 vd μ 2 xy 3 +4 ud μ 2 y 4 +2 udx 4 +2 vdx 3 y +2 udx 2 y 2 +2 vdxy 3 +2 v μ 2 x 5 −2 u μ 2 x 4 y +4 v μ 2 x 2 −4 u μ 2 x 2 y 3 +2 v μ 2 xy 4 −2 u μ 2 y 5

K 3 =2 uy −2 vx.

In one embodiment, the square root terms in Equation (18) are removed as

0 =K 2 2 ( x,y ) A+K 3 2 ( x,y ) A 3 +2 K 2 ( x,y ) K 3 ( x,y ) A 2 −K 1 2 ( x,y ),  (19)

which after simplification is a 8 th degree polynomial equation in both x and y. Bringing the odd powered terms of x on one side, squaring and substituting x 2 =r 2 −y 2 result, after simplification, in a 10 th degree equation in y.

Obtained Light Path for Refractive Sphere

FIGS. 3A-3C show an example of solving the FP equation and determining the folding points for the refractive sphere according several embodiments of the invention. For a given PS p 240 , solving Equation (19) results in ten solutions for y. In general, when the PS is not on the axis of symmetry, only eight out of the ten solutions are real, from which the corresponding light paths are obtained as shown in FIG. 3A . A constraint y≧r 2 /d further reduces the possible solutions to four solutions shown in FIG. 3B . The final solution shown in FIG. 3C is found using another constraint, i.e., by testing the law of refraction for each possible solution.

Sparse 3D Reconstruction Using Spherical Mirrors

An analytical forward projection (AFP) is used for sparse 3D reconstruction, i.e., determining concurrently 3D points in the scene and parameters of the catadioptric system, using bundle adjustment algorithm. In one embodiment, the catadioptric system includes a single perspective camera imaging multiple spherical mirrors. One example of such mirrors is a stainless steel ball. The internal camera calibration is done separately off-line, radius is known. The 3D locations of centers of the mirrors are determined as described below.

Bundle Adjustment Using Analytical Forward Projection

Let C(i)=[C x (i), C y (i), C z (i)] T , i=1 . . . M be the sphere centers, and P(j)=[P x (j), P y (j), P z (j)] T , j=1 . . . N be the 3D PS in the camera coordinate system when the pinhole camera is arranged at the origin. We rewrite the FP Equation (3) in terms of 3D quantities. For a given 3D point P(j) and a mirror center C(i), the orthogonal vectors z 1 and z 2 defining the 2D plane π are given by

By substituting d, v and u in (3), the FP equation is re-written as

c 1 y 4 +c 2 y 3 +c 3 y 2 +c 4 y+c 5 =0,  (21)

where each coefficient c i is a function of P(j) and C(i) only. In general, when the scene point is outside the sphere and is visible through mirror reflection, there are four possible solutions. The single correct solution is determined by checking the law of reflection for each possible solution.

Using the solution, the 3D reflection point on the sphere is determined according to

Finally, the 2D image projection pixel is determined according to

p ⁡ ( i , j ) = f x ⁢ X m ⁡ ( i , j ) Z m ⁡ ( i , j ) + c x , q ⁡ ( i , j ) = f y ⁢ Y m ⁡ ( i , j ) Z m ⁡ ( i , j ) + c y ,

where (f x , f y ) and (c x , c y ) are a focal length and a principal point of the camera, respectively.

Let [{circumflex over (p)}(i,j),{circumflex over (q)}(i,j)] T be the image projection of the j th 3D point for the i th sphere and [p(i,j),q(i,j)] T are current estimates determined from current estimates of sphere centers and 3D scene points. Each pair (i,j) gives a 2-vector error function

F ( i,j )=[ p ( i,j )− {circumflex over (p)} ( i,j ), q ( i,j )− {circumflex over (q)} ( i,j )] T ,  (23)

and an average reprojection error is

The bundle adjustment is preformed by minimizing the error E starting from an initial solution. The initial 3D points are obtained as the center of the shortest transversal of the respective back-projection rays. The initial sphere centers are obtained using the acquired images.

Jacobian Computation

Another embodiment uses AFP to analytically determine a Jacobian matrix of a reprojection error, which accelerates the bundle adjustment process. Let t denote an unknown. Then

Because X m , Y m , Z m depends on the coordinate y, the above derivatives depend on

Usually, a closed form expression for the coordinate y is required to determine

∂ y ∂ t .

However, one embodiment of the invention uses alternative approach, which takes the derivative of the FP Equation (10), and obtains

For a given 3D point P(j) and sphere center C(i), y is computed by solving the FP equation, which can be substituted in Equation (14) to determine

∂ y ∂ t .

The gradient of the reprojection error, with respect to each unknown, is determined using Equations (11), (13), and (14).

3D Reconstruction with Outlier Removal

Some embodiments consider that corresponding image points are estimated using a feature matching algorithm, such as a scale-invariant feature transform (SIFT), and invariably contain outliers and false matches. Those embodiments perform reconstruction by iterating bundle-adjustment with outlier removal. After each bundle-adjustment step, the 3D points whose reprojection error is greater than twice the average reprojection error are removed. Because AFP significantly reduces bundle-adjustment time, one embodiment is repeats such removal multiple times and is effective in handling outliers. Thus, analytical FP allows complex non-central models to be used for outlier removal without a central approximation.

Setup and Initial Estimate of Sphere Centers

One embodiment uses, e.g., four spherical mirrors of radius 0.75″ positioned with an interval of 3″, and acquires a single image using a Mamiya 645AFD camera. Each sphere image in the photo image has 1300×1300 resolution. To determine initial sphere centers, the embodiment marks several points on each sphere boundary, corresponding to the rays tangential to the sphere, and determines a central ray that makes the same angle α with all the tangential rays. The sphere center is at a distance of r/sin α along the central ray.

Iterative Forward Projection vs. Analytical Forward Projection

Conventional iterative forward projection (IFP) first computes the initial image projection of a 3D point using the central approximation, and then performs non-linear optimization to minimize the distance between the 3D point and the back-projected ray. For projecting 10 5 3D points with a single sphere, IFP takes 1120 seconds, while AFP takes only 13.8 seconds, i.e., ˜80 times faster. AFP, along with analytical Jacobian computation, achieves two orders of magnitude faster when compared to IFP for 3D reconstruction using bundle adjustment.

Back-Projection for Spherical Mirror

FIG. 4 shows a schematic of back projection for spherical mirror according one embodiment of the invention. The embodiment rewrites the back-projection equations in matrix-vector form. For example, a point C p =[0,0,−d] T is the COP 400 and a spherical mirror 410 of radius r is located at the origin 420 . For an image point q 430 , s=K −1 q is a direction 435 of the ray, where K 3×3 is the internal camera calibration matrix. The intersection points b with the mirror is

b = C p + s ⁢ ⁢ ds 3 ± d 2 ⁢ s 3 2 - ( d 2 - r 2 ) ⁢ ( s T ⁢ s ) s T ⁢ s , ( 26 )

where S 3 is the third element of s, b T b=r 2 and the normal at b is b/r.

Because v i =b−C p , the outgoing vector v r is

v r =( b−C p )−2 b ( b T ( b−C p ))/ r 2 =−b−C p +2 b ( b T C p )/ r 2 ,  (27)

which intersects the mirror axis at m=[0,0,k] T , where k=dr 2 /(2db 3 +r 2 ). Thus, the Plücker coordinates of the reflected 3D ray are L=(b T −m T ,(b×m) T ) T . We use L + 450 and L − 455 to represent the reflected rays corresponding to the two intersections of v i with the sphere (b + 460 and b − 465 ). We represent the two lines with a second-order line complex C, described as a symmetric 6×6 matrix

C ∼ W ⁡ ( L + T ⁢ L - + L - T ⁢ L + ) ⁢ W , W = ( 0 I I 0 ) , ( 28 )

where ˜ denotes the equality of matrices up to a scale factor. By substituting b and M, we obtain a line complex C that includes quartic monomials of s. Let v sym (C) be the column-wise vectorization of the upper-right triangular part of C (21-vector) and  denote double lifted coordinates of s in the lexicographic order (15-vector):

Then, we obtain the back-projection equation in a matrix-vector form:

v sym ( C )˜ B r,d {circumflex over (ŝ)}=B r,d {circumflex over ({circumflex over (K)} −1 {circumflex over ({circumflex over (q)},   (29)

where B r,d is a sparse 21×15 matrix depending only on r and d:

Epipolar Curve for Spherical Mirror

One embodiment considers a 3D ray defined in the sphere-centered coordinate system and represented with Plücker coordinates as L 0 . This ray intersects a line complex C if and only if

L 0 T CL 0 =0.  (30)

Because the line complex C includes quartic monomials of S, the constraint results in a 4 th order curve. The projection of L 0 , therefore, appears as a quartic curve in the image of spherical minor, which means that spherical-minor based catadioptric systems yield fourth order epipolar curves.

The embodiment uses the FP equation to validate degree and shape of the epipolar curves.

FIG. 5 is a graph that compares the epipolar curve 510 analytically determined based on Equation (19) with the curve 520 obtained by projecting 3D points on L 0 using the FP equation. The shape of curves is a continuous section of the analytical quartic curve. Also, the image point converges as the 3D point goes to ±∞ on L 0 .

Similar to perspective cameras, the quartic epipolar curve can be used to restrict the search space for dense stereo matching. Typically, approximations such as epsilon-stereo constraint are used, which assumes that the corresponding matches are arranged approximately along a line. However, the embodiments provide the analytical 2D epipolar curve for non-central spherical mirror cameras. The FP equation for general conic mirrors simplifies the correspondence search for other non-central conic catadioptric systems as well.

The embodiments of the invention advance the field of catadioptric imaging both theoretically and practically. Embodiments provide analytical equations of forward and backward projections for a broad class of non-central catadioptric systems. Furthermore, the analytical FP and Jacobian computation significantly reduce the bundle adjustment run-time. Thus, the computational complexity of using a non-central model becomes similar to that of a central approximation.

Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications can be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.