System and method for computing rectifying homographies for stereo vision processing of three dimensional objects

[0002] 1. Field of the Invention

[0003] The present invention relates in general to object modeling, and in particular to a system and method for computing rectifying homographies for stereo vision processing of three dimensional (3D) objects.

[0004] 2. Related Art

[0005] In the stereo computer vision field, it is typically assumed that a pair of two dimensional (2D) images of a three dimensional (3D) object or environment are taken from two distinct viewpoints. For certain stereo vision computations, the epipolar geometry of the two images is usually determined first and corresponding points between the two images typically need to satisfy an epipolar constraint. Next, for a given point in one image, a search is initiated for its correspondence in the other image along an epipolar line. In general, epipolar lines are not aligned with coordinate axis and are not parallel.

[0006] However, such searches are time consuming since the pixels of each image are compared on skewed lines in image space. These types of computations can be simplified and made more efficient if epipolar lines are axis aligned and parallel. This can be realized by applying 2D projective transforms, or homographies, to each image. This process is known as image rectification. In general, image rectification involves applying a pair of two dimensional (2D) projective transforms, or homographies, to a pair of images whose epipolar geometry is known so that epipolar lines in the original images map to horizontally aligned lines in the transformed images.

[0007] The pixels corresponding to point features from a rectified image pair will lie on the same horizontal scan-line and differ only in horizontal displacement. This horizontal displacement or disparity between rectified feature points is related to the depth of the feature. As such, rectification can be used to recover 3D structure from an image pair without appealing to 3D geometry notions like cameras. Computations that find dense correspondences are based on correlating pixel colors along epipolar lines. Typically, distinct views of a scene can be morphed by linear interpolation along rectified scan-lines to produce new geometrically correct views of the scene. Thus, image rectification is an important component of stereo computer vision computations and processing.

[0008] Some previous techniques for finding image rectification homographies involve 3D constructions. These methods find the 3D line of intersection between image planes and project the two images onto a plane containing this line that is parallel to the line joining the optical centers. However, its realization in practice is difficult because it involves 3D geometric construction. Although a 2D approach exists, it does not optimally reduce distortion effects of image rectification. Instead, the distortion minimization criterion is based on a simple geometric heuristic, which may not lead to optimal solutions.

[0009] Therefore, what is needed is an efficient system and method for computing rectifying homographies of 2D images of a 3D object for stereo vision processing of the 3D objects. What is also needed is a system and method that rectifies images with optimally reduced distortion.

[0010] Whatever the merits of the above mentioned systems and methods, they do not achieve the benefits of the present invention.

[0011] To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention is embodied in a system and method for computing rectifying homographies for stereo vision processing of three dimensional (3D) objects.

[0012] In general, the system and method of the present invention computes 2D projective transforms or homographies derived from specialized projective and affine transforms or components. The affine transform is comprised of a similarity transform and an optional shearing transform for image rectification. During image rectification of the present invention, optimization techniques are used for reducing the distortion.

[0013] Namely, first, two-dimensional (2D) images of a three-dimensional (3D) object are obtained. Next, a fundamental matrix between the two images is obtained. The fundamental matrix embodies the epipolar geometry between the images. For each image, a special projective transform is then found that minimizes a well defined projective distortion criteria. Next, for each image, an affine transform is computed. The affine transform is comprised of a similarity and an optional shearing transform.

[0014] The similarity transform is found such that it satisfies the constraints for rectification. The shearing transform can be found for further reducing distortion introduced by the projective component. The similarity and optional shearing transforms are combined into a final affine component for each homography. Next, for each homography, the special projective and final affine transforms are combined into the rectifying homography. With the use of the above transforms of the present invention, rectification of each image is produced with minimum distortion.

[0015] The present invention as well as a more complete understanding thereof will be made apparent from a study of the following detailed description of the invention in connection with the accompanying drawings and appended claims.

[0016] Referring now to the drawings in which like reference numbers represent corresponding parts throughout:

[0017] FIG. 1 is a block diagram illustrating an apparatus for carrying out the invention;

[0018] FIG. 2 is an overview block diagram of the present invention;

[0019] FIG. 3 shows an operational and functional overview of the present invention;

[0020] FIGS. 4-5 illustrate the epipolar geometry of the multiple views of the present invention;

[0021] FIG. 6 illustrates the operational and functional details of one transform of the present invention;

[0022] FIG. 7 illustrates the operational and functional details of other transforms of the present invention; and

[0023] FIGS. 8-11 are pictures illustrating a working example of the present invention.

[0024] In the following description of the invention, reference is made to the accompanying drawings, which form a part hereof, and in which is shown by way of illustration a specific example in which the invention may be practiced. It is to be understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention.

[0025] Rectification of 2D images of a 3D object of the present invention is produced from projective and affine components of each homography of the 2D images. The projective component of each homography is a special projective component that minimizes a well defined projective distortion criterion. The affine component of each homography is comprised of a pair of simpler transforms, one designed to satisfy the constraints for rectification, the other to further reduce the distortion introduced by the projective component. The special projective and affine components are combined for each homography to rectify the images. The image rectification system and method of the present invention is based on well defined geometric criteria, thus, image distortion due to the rectification is minimized.

[0026] FIG. 1 and the following discussion are intended to provide a brief, general description of a suitable computing environment in which the invention may be implemented. Although not required, the invention will be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Moreover, those skilled in the art will appreciate that the invention may be practiced with a variety of computer system configurations, including personal computers, server computers, hand-held devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located on both local and remote computer storage media including memory storage devices.

[0027] With reference to FIG. 1, an exemplary system for implementing the invention includes a general purpose computing device in the form of a conventional computer 100, including a processing unit 102, a system memory 104, and a system bus 106 that couples various system components including the system memory 104 to the processing unit 102. The system bus 106 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. The system memory includes computer storage media in the form of read only memory (ROM) 110 and random access memory (RAM) 112. A basic input/output system 114 (BIOS), containing the basic routines that helps to transfer information between elements within computer 100, such as during start-up, is stored in ROM 110. The computer 100 may include a hard disk drive 116 for reading from and writing to a hard disk, not shown, a magnetic disk drive 118 for reading from or writing to a removable magnetic disk 120, and an optical disk drive 122 for reading from or writing to a removable optical disk 124 such as a CD ROM or other optical media. The hard disk drive 116, magnetic disk drive 128, and optical disk drive 122 are connected to the system bus 106 by a hard disk drive interface 126, a magnetic disk drive interface 128, and an optical drive interface 130, respectively. The drives and their associated computer-readable media provide storage of computer readable instructions, data structures, program modules and other data for the computer 100. Although the exemplary environment described herein employs a hard disk, a removable magnetic disk 120 and a removable optical disk 130, it should be appreciated by those skilled in the art that other types of computer readable media can store data that is accessible by a computer. Such computer readable media can be any available media that can be accessed by computer 100. By way of example, and not limitation, such computer readable media may comprise communication media and computer storage media. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set of changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as wired network or direct wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. By way of example, and not limitation, communication media includes wired media such as a wired network or direct wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Computer storage media includes any method or technology for the storage of information such as computer readable instructions, data structures, program modules or other data. By way of example, such storage media includes RAM, ROM, EPROM, flash memory or other memory technology, CD-ROM, digital video disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computer 100. Combinations of any of the above should also be included within the scope of computer readable media.

[0028] A number of program modules may be stored on the hard disk, magnetic disk 120, optical disk 124, ROM 110 or RAM 112, including an operating system 132, one or more application programs 134, other program modules 136, and program data 138. A user may enter commands and information into the computer 100 through input devices such as a keyboard 140 and pointing device 142. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit 102 through a serial port interface 144 that is coupled to the system bus 106, but may be connected by other interfaces, such as a parallel port, game port or a universal serial bus (USB). A monitor 146 or other type of display device is also connected to the system bus 106 via an interface, such as a video adapter 148. In addition to the monitor 146, computers may also include other peripheral output devices (not shown), such as speakers and printers.

[0029] The computer 100 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 150. The remote computer 150 may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the personal computer 100, although only a memory storage device 152 has been illustrated in FIG. 1. The logical connections depicted in FIG. 1 include a local area network (LAN) 154 and a wide area network (WAN) 156. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and Internet.

[0030] When used in a LAN networking environment, the computer 100 is connected to the local network 154 through a network interface or adapter 158. When used in a WAN networking environment, the computer 100 typically includes a modem 160 or other means for establishing communications over the wide area network 156, such as the Internet. The modem 160, which may be internal or external, is connected to the system bus 106 via the serial port interface 144. In a networked environment, program modules depicted relative to the computer 100, or portions thereof, may be stored in the remote memory storage device. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

[0031] FIG. 2 is an overview block diagram of the present invention. The present invention is embodied in a system and method for computing rectifying homographies for stereo vision processing of three dimensional (3D) objects. In general, the system 200 of the present invention includes an object 210 represented by multiple 2D images 212, 214. A homography that maps the epipole to a predetermined point for each image is applied to each image. Geometrical representations or the epipolar geometry of the views are obtained as fundamental matrix (FM) 216 between the views 212, 214.

[0032] The homographies are comprised of special projective transforms (SP and SP′) 220, 222 and affine transforms (A and A′) 224, 226. These transforms can be computed based on the fundamental matrix (FM), respectively. The special projective transforms (SP and SP!) 220, 222 are computed so that they minimize a well defined projective distortion criterion. The affine transforms (A and A′) 224, 226 are comprised of simpler transforms (A1 and A1′) 228, 230 that are designed to satisfy the constraints for rectification. In addition, the affine transforms (A and A′) 224, 226 can be comprised of optional affine transforms (A2 and A2′) 232, 234 to further reduce the distortion introduced by the projective component.

[0033] The affine transforms (A1 and A2 and A1′ and A2′) are combined to produce affine combinations (AC and AC′) 236, 238. The special projective transforms (SP and SP′) 220, 222 are combined with the affine combinations (AC and AC′) 236, 238 to compute the rectifying homographies (H and H′) 240, 242 to produce rectified images (R and R′) 244, 246. The discussion below describes the details of the system and method of the present invention.

[0034] The following discussion assumes 2D projective workspace. Points and lines are represented by lower-case bold symbols, e.g. p (point) and l (line). The coordinates of points and lines are represented by 3D column vectors, e.g. p=[p_up_vp_w]^Tand l=[l_al_bl_c]^T. The individual coordinates are sometimes ordered u, v, w for points, and a, b, c for lines. Transforms on points and lines are represented by 3×3 matrices associated with bold upper case symbols, e.g. T. Unless identified to the contrary, matrix entries are given sub-scripted upper-case symbols, e.g. T₁₁,T₁₂, . . . , T₃₃. Pure scalar quantities are given lower-case Greek symbols. As projective quantities, points and lines are scale invariant, meaning p=αp(α≠0) represents the same point. Points with w-coordinates equal to zero are affine vectors, directions or points at ∞. Points with a non-zero w-coordinate are affine points when the scale has been fixed so that p=[p_up_v1]^T. The set of all affine points is the affine plane. For the following discussion, the image plane is considered to be an affine plane where points are uniquely identified by u and v, and w are presumed to be equal to one.

[0035] A. Epipolar Geometry

[0036] FIG. 3 shows an operational and functional overview of the present invention. In general, first, images such as two-dimensional (2D) images of a three-dimensional (3D) object are obtained (step 300). Second, a fundamental matrix between the two images is obtained (step 310). The fundamental matrix embodies the epipolar geometry between the images. The epipolar geometry between a pair of images can be defined by setting C and C′ as a pair of pinhole cameras in 3D space and letting m and m′ be the projections through cameras C and C′ of a 3D point M in images I and I′ respectively. The geometry of these definitions is shown in FIGS. 4 and 5.

[0037] Namely, the epipolar constraint is defined by:

[0038] m′^TFm=0,  (1)

[0039] for all pairs of images correspondences m and m′, where F is the fundamental matrix.

[0040] The fundamental matrix F is a 3×3 rank −2 matrix that maps points in I to lines in I′, and points in I′ to lines in I′. That is, if m is a point in I, then Fm=1′ is an epipolar line in I′ since from Eq. (1), m′^T1′=0. In fact, any point m′ that corresponds with m lies on the epipolar line Fm. For a fundamental matrix F, there exists a pair of unique points eεI and e′εI′ such that:

[0041] Fe=0=F^Te′  (2)

[0042] where 0=[000]^Tis the zero vector. The points e and e′ are the epipoles of images I and I′ respectively. The epipoles have the property that all epipolar lines in I pass through e, similarly all epipolar lines in I′ pass through e′.

[0043] In 3D space, e and e′ are the intersections of the line C C′ with the planes containing image I and I′. The set of planes containing the line C C′ are the epipolar planes. Any 3D point M not on line C C′ will define an epipolar plane, the intersection of this epipolar plane with the plane containing I or I′ will result in an epipolar line, as shown in FIG. 4.

[0044] In the following discussion, it is assumed that F is known. An overview of techniques to find F is described in “Determining the Epipolar Geometry and its Uncertainty: A Review,” by Z. Zhang, International Journal of Computer Vision,27(2):161-1195, 1998, which is incorporated herein by reference. If the intrinsic parameters of a camera are known, the images are calibrated, and the fundamental matrix becomes the essential matrix. The rectification system and method of the present invention is suitable for calibrated or uncalibrated images pairs, provided that F is known between them.

[0045] B. Image Rectification

[0046] After the fundamental matrix is obtained, the images can be rectified. Image rectification is the process of transforming the epipolar geometry of a pair of images into a canonical form. This is accomplished by applying a homography to each image that maps the epipole to a predetermined point. The point is defined as i=[100]^T(a point at ∞), and the fundamental matrix for a rectified image pair is defined, as discussed above, by the expression: $\stackrel{\_}{F}={\left[i\right]}_x=\left[\begin{array}{ccc}0& 0& 0\\ 0& 0& -1\\ 0& 1& 0\end{array}\right]$

[0047] The notation [x]_xis used to denote the antisymetric matrix representing the cross product with x. From the above, the rectified images have the following two properties: 1) All epipolar lines are parallel to the u-coordinate axis and 2) Corresponding points have identical v-coordinates. These properties are useful in practice since rectification maps epipolar lines to image scan-lines. Other conventions for canonical epipolar geometry can be useful under special circumstances.

[0048] For image rectification in accordance with the present invention, H and H′ are defined as the homographies to be applied to images I and I′ respectively, and mεI and m′εI′ are a pair of points that satisfy Eq. (1). It is noted that rectified image points {overscore (m)} and {overscore (m)}′ define:

[0049] {overscore (m)}=Hmand {overscore (m)}′=H′m′.

[0050] It follows from Eq. (1) that:

[0051] {overscore (m)}′^T{overscore (F)}{overscore (m)}=0, $m^{\prime T}\underset{\underset{F}{⏟}}{\begin{array}{cc}{H}^{\prime }& \stackrel{\_}{F}Hm\end{array}}=0,$

[0052] resulting in the factorization

[0053] F=H′^T[i]_xH.

[0054] Note that the homographies H and H′ that satisfy Eq. (3) are not unique. However, in accordance with the present invention, a pair of homographies H and H′ are found to minimize image distortion.

[0055] Namely, u, v and w are lines equated to the rows of H such that: $\begin{array}{cc}H=\left[\begin{array}{c}{u}^T\\ v^T\\ w^T\end{array}\right]=\left[\begin{array}{ccc}{u}_a& u_b& u_c\\ v_a& v_b& v_c\\ w_a& w_b& w_c\end{array}\right].& \left(4\right)\end{array}$

[0056] Similarly, lines u′, v′, and w′ are equated to the rows of H′. As such, by definition:

[0057] He=[u^Te v^Te w^Te]^T=[100]^T.

[0058] This means that the lines v and w contain the epipole e. Similarly v′ and w′ contain the other epipole e′. Further, lines v and v′, and lines w and w′ are corresponding epipolar lines. This has a simple geometric interpretation as illustrated in FIG. 5. This result establishes a linkage between the homographies H and H′, which is important when minimizing distortion caused by rectification.

[0059] Namely, corresponding epipolar lines are related by a direction in one image and the second and third rows of a pair of rectifying homographies correspond to pairs of corresponding epipolar lines. In the discussion that follows, the symbol ˜ is used to indicate correspondence. First, lεI and l′εI′ are defined as a pair of epipolar lines. If l˜l′ and xεI is a direction (point at ∞) such that l=[e]_xx then

[0060] 1′=Fx.

[0061] This can be shown by letting x be the intersection of lines l and k=[001]^T(the line at ∞), found by x=[k]_xl. Similarly, let x′=[k]_xl′. As such, l=[e]_xx, since [e]_x[k]_xl=l. Since l˜l′, it follows that x′^TFx=0. By definition e′^Tl′=e′^TFx=0 and x′^Tl′=x′^TFx=0, which shows that lines l′ and Fx both contain points e′ and x′ and must be the same line. In the following, we denote the rows of H and H′ as in Eq. (4), and i=[100]^T.

[0062] Next, if H and H′ are homgraphies such that

[0063] F=H′^T[i]_xH,  (A)

[0064] then v˜v′ and w˜w′. For example, expanding H′^T[i]xH, shows that $F=\left[\begin{array}{ccc}{v}_a{w}_a^{\prime }-v_a^{\prime }{w}_a& v_b{w}_a^{\prime }-v_a^{\prime }{w}_b& v_c{w}_a^{\prime }-v_a^{\prime }{w}_c\\ v_a{w}_b^{\prime }-v_b^{\prime }{w}_a& v_b{w}_b^{\prime }-v_b^{\prime }{w}_b& v_c{w}_b^{\prime }-v_b^{\prime }{w}_c\\ v_a{w}_c^{\prime }-v_c^{\prime }{w}_a& v_b{w}_c^{\prime }-v_c^{\prime }{w}_b& v_c{w}_c^{\prime }-v_c^{\prime }{w}_c\end{array}\right].$

[0065] It should be noted that F does not depend on u or u′. Without loss of generality, the following expression u=k=u′, can be set where k=[001]^Tis the line at ∞. As such, up to a scale factor H⁻¹=[[v]_xw [w]_xu [u]_xv]. Since v and w are independent (follows from Eq. (A)) and both contain e, it can be concluded that [v]_xw=e. If y=[v]_xk and z=[w]_xk. From Eq. (A) the following expression is produced:

[0066] H′^T[i]_x=FH⁻¹

[0067] [k v′ w′][i]_x=F[e z−y]

[0068] [0 w′−v′]=[0 Fz−Fy].  (B)

[0069] It is concluded that v′=Fy and w′=Fz. Consequently, it follows that v˜v′ and w˜w′.

[0070] In general, the system and method of the present invention achieves image rectification by combining specialized projective and affine transforms. After the fundamental matrix is obtained (as shown in FIG. 3), a special projective transform is found for each image that minimizes a well defined projective distortion criteria (step 312). Next, for each image, a first affine transform is found such that it satisfies the constraints for rectification (step 314). Optionally, for each image, a second affine transform can be found for further reducing distortion introduced by the projective component (step 316).

[0071] The first and second affine transforms can then be combined into a final affine component for each homography (step 318). Next, for each homography, the special projective and final affine transforms are combined into the rectifying homography (step 320). With the use of the above transforms of the present invention, rectification of each image is produced with minimum distortion (step 322).

[0072] C. Decomposition of the Homographies

[0073] In particular, rectifying homographies H and H′ are computed in accordance with the present invention by decomposing the homographies into simpler transforms, as shown generally in FIG. 2. Each component transform is then computed to achieve a desired effect and satisfy some conditions.

[0074] First, the scale invariant homography H is equated with a scale variant counterpart: $\begin{array}{cc}H=\left[\begin{array}{ccc}{u}_a& u_b& u_c\\ v_a& v_b& v_c\\ w_a& w_b& 1\end{array}\right],& \left(5\right)\end{array}$

[0075] by dividing out w_c. Similarly w′_ccan be divided out from H′. This will not lead to difficulties arising from the possibility that w_cor w′_cbe equal to zero since it is assumed that the image coordinate system origin is near the image. As such, the minimization procedure will tend to keep the lines w and w′ away from the images.

[0076] H is decomposed into

[0077] H=H_aH_p,

[0078] where H_pis a special projective transform and H_ais an affine transform. Thus, the following is defined: $\begin{array}{cc}{H}_p=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ w_a& w_b& 1\end{array}\right].& \left(6\right)\end{array}$

[0079] From Eqs. (5) and (6) it follows that: $H_a=H{H}_p^{-1}=\left[\begin{array}{ccc}{u}_a-u_c{w}_a& u_b-u_c{w}_b& u_c\\ v_a-v_c{w}_a& v_b-v_c{w}_b& v_c\\ 0& 0& 1\end{array}\right].$

[0080] The definitions of H′_aand H′_pfor the other homography for the second image are similar but with primed symbols.

[0081] Next, H_a(similarly H′_a) can be further decomposed into:

[0082] H_a=H_sH_r

[0083] where H_ris a first affine transform, such as a similarity transformation, and H_sis a second affine transform, such as a shearing transformation. The transform H_rwill have the form: $\begin{array}{cc}{H}_r=\left[\begin{array}{ccc}{v}_b-v_c{w}_b& v_c{w}_a-v_a& 0\\ v_a-v_c{w}_a& v_b-v_c{w}_b& v_c\\ 0& 0& 1\end{array}\right]& \left(7\right)\end{array}$

[0084] and the transform H_swill have the form: $H_s=\left[\begin{array}{ccc}{s}_a& s_b& s_c\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$

[0085] Note that H_sonly effects the u-coordinate of a point, therefore it will not effect the rectification of an image. The following discussion describes the computation of each component transform defined above.

[0086] 1. Special Projective Transform

[0087] FIG. 6 illustrates the operational and functional details of one transform of the present invention. In general, once the fundamental matrix is obtained (step 600), the special projective transform is found such that it minimizes a well defined projective distortion criteria (step 610). This includes sending the epipole to infinity so that the epipolar lines become parallel (step 612), capturing all image distortion due to projective transformation (step 614) and making the special transformation as affine as possible by minimizing the variation of assigned weights over all pixels (step 616).

[0088] Specifically, the special projective transforms H_pand H′_pcompletely characterize the projective components of H and H′. These transforms map the epipoles e and e′ to points at ∞ (points with w-coordinates equal to zero). By definition, H_pand H′_pare determined by lines w and w′ respectively. The lines w and w′ are not independent. Given a direction z=[λμ0]^Tin image I, the following is found:

[0089] w=[e]_xzand w′=Fz.  (8)

[0090] This result follows from the correspondence of w and w′ as epipolar lines (as discussed above). Any such z will define a pair of corresponding epipolar lines and the parameter z is found that minimizes distortion, to be defined below.

[0091] Let p_i=[p_i,up_i,v1]^Tbe a point in the original image. This point will be transformed by H_pto point ${\left[\frac{p_{i,u}}{w_i}\frac{p_{i,v}}{w_i}1\right]}^T$

[0092] with weight

[0093] w_i=w^Tp_i.

[0094] If the weights assigned to points are identical then there is no projective distortion and the homography is necessarily an affine transform. In order to map the epipole e from the affine (image) plane to a point at ∞, H_pis not, in general, affine. However, as the image is bounded H_pcan be made as affine as possible. This is the basis of the distortion minimization criterion.

[0095] a) Distortion Minimization Criterion

[0096] Although identical weights usually do not exist in general (except when the epipole is already at ∞), the variation of the weights assigned to a collection of points over both images can be minimized. All the pixels from both images are preferably used as a collection, but some other subset of important image points could also be used if necessary. The variation is measured with respect to the weight associated with the image center. More formally, the following is computed: $\begin{array}{cc}\sum _{i-1}^n{\left[\frac{w_i-w_c}{w_c}\right]}^2,& \left(9\right)\end{array}$

[0097] where w_c=w^Tp_cand where $p_c=\frac{1}{n}\sum _i^n=1$

[0098] p_iis the average of the points. This measure will be zero if the weights for all the points are equal, occurring only if H_pis an affine map, and the epipole is already at ∞. By minimizing Eq. (9) it follows that H_pand H′_pare as close to affine as possible over the point set p_i.

[0099] Over one image, Eq. (9) can be written as $\sum _{i=1}^n{\left[\frac{w^T\left(p_i-p_c\right)}{w^T{p}_c}\right]}^2,$

[0100] or as a matrix equation: $\begin{array}{cc}\frac{w^T{\mathrm{PP}}^{T}w}{w^T{p}_c{p}_c^{T}w},& \left(10\right)\end{array}$

[0101] where P is the 3×n matrix $P=\left[\begin{array}{cccc}{p}_{1,u}-p_{c,u}& p_{2,u}-p_{c,u}& \dots & p_{n,u}-p_{c,u}\\ p_{1,v}-p_{c,v}& p_{2,v}-p_{c,v}& \dots & p_{n,v}-p_{c,v}\\ 0& 0& \dots & 0\end{array}\right].$

[0102] The matrices p′_cand P′ are similarly defined for the other image. Since w=[e]_z, and w′=Fz, Eq. (10) can be rewritten over both images as: $\begin{array}{cc}\frac{\begin{array}{cc}{z}^T& \stackrel{\stackrel{A}{⏞}}{{\left[e\right]}_x^{T}P{P^T\left[e\right]}_{x}z}\end{array}}{\begin{array}{cc}{z}^T& \underset{\underset{B}{⏟}}{{\left[e\right]}_x^T{P}_c{P_c^T\left[e\right]}_{x}z}\end{array}}+\frac{\begin{array}{cc}{z}^T& \stackrel{\stackrel{A^{\prime }}{⏞}}{F^T{P}^{\prime }{P^{\prime }}^{T}Fz}\end{array}}{\begin{array}{cc}{z}^T& \underset{\underset{B^{\prime }}{⏟}}{F^T{P}_c^{\prime }{P}_c^{\prime T}Fz}\end{array}}\mathrm{or}\frac{z^T\mathrm{Az}}{z^T\mathrm{Bz}}+\frac{z^T{A}^{\prime }z}{z^T{B}^{\prime }z},& \left(11\right)\end{array}$

[0103] where A, B, A′, and B′ are 3×3 matrices that depend on the point sets. p_iand p′_i. Since the w-coordinate of z is equal to zero, the upper-left 2×2 blocks of these matrices are important. In the following discussion of this section, the expression z=[λ, μ]^Tis denoted.

[0104] The specific point set corresponding to a whole image is considered below. It is assumed that an image is a collection of pixel locations denoted

[0105] p_i,j=[i j1]^T,

[0106] where i=0, . . . , w−1 and j=0, . . . , h−1, and w and h are the width and height of image I. The image center is the point $p_c={\left[\frac{w-1}{2}\frac{h-1}{2}1\right]}^T$

[0107] The primed counter-parts, I′, for image I are similarly defined. Under these assumptions, the upper-left 2×2 block of PP^Tis reduced to the following simple form: ${\mathrm{PP}}^T=\frac{\mathrm{wh}}{12}\left[\begin{array}{cc}{w}^2-1& 0\\ 0& h^2-1\end{array}\right],\mathrm{and}$ $p_c{p}_c^T=\frac{1}{4}\left[\begin{array}{cc}{\left(w-1\right)}^2& \left(w-1\right)\left(h-1\right)\\ \left(w-1\right)\left(h-1\right)& {\left(h-1\right)}^2\end{array}\right].$

[0108] Using these results, the 2×2 matrices A, B, A′, and B′ in can be computed in Eq. (11).

[0109] b) Minimization

[0110] Solving z by minimizing Eq. (11) is a nonlinear optimization problem. For example, z=[λμ]^Tis defined up to a scalar factor. Without loss of generality, the present invention can set u=1. (If μ is much smaller than λ, the system can set λ=1, but the following discussion is still applicable). Quantity (11) is minimized when the first derivative with respect to λ is equal to 0. This produces a polynomial of degree 7, because (11) is the sum of two rational functions, each the ratio of quadratic polynomials. The root can be found iteratively starting from an initial guess.

[0111] The initial guess is obtained as follows. First, z^TAz/z^TBz and z^TA′z/z^TB′z are minimized separately (see discussion below), which produces two different estimations of z, denoted by {circumflex over (z)}₁and {circumflex over (z)}₂. Their average ({circumflex over (z)}₁/∥{circumflex over (z)}₁∥+{circumflex over (z)}₂/∥{circumflex over (z)}₂∥)/2, is used as the initial guess of z. This average is close to the optimal solution. Minimizing z^TAz/z^TBz is equivalent to maximizing z^TBz/z^TAz, denoted by f(z). As A is symmetric and positive-definite, it can be decomposed as A=D^TD. Let y=Dz . Then, f(z) becomes $\hat{f}\left(y\right)=\frac{y^T{D}^{-T}{\mathrm{BD}}^{-1}y}{y^{T}y}.$

[0112] Since y is defined up to a scale factor, ∥y∥=1 can be imposed, and {circumflex over (f)}(y) is maximized when y is equal to the eigenvector of D^−TBD⁻¹associated with the largest eigen-value. Finally, the solution for z is given by z=D⁻¹y. Exactly the same procedure can be applied to find z which minimizes z^TA′z/z^TB′z.

[0113] 2. Affine Transforms

[0114] FIG. 7 illustrates the operational and functional details of other transforms of the present invention. In general, after the special projective transform and fundamental matrix is obtained (step 700), affine components of each homography is computed (step 710). The affine components are comprised of at least a similarity transform 712 and optionally a shearing transform 714 for each image, as described in FIGS. 2 and 3.

[0115] The similarity transform 712 is preferably found by rotating and translating images such that the epipolar lines are horizontally aligned so that it satisfies the constraints for rectification (step 716). The optional shearing transform is preferably found by scaling and translating the images in a horizontal direction while preserving original image resolution as close as possible for further reducing distortion introduced by the projective component (step 718).

[0116] a. Similarity Transform

[0117] Specifically, as discussed above, the transforms H_pand H′_pwere found that map the epipoles e and e′ to points at ∞. In the discussion that follows, a pair of similarity transforms H_rand H′_rare defined that rotate these points at ∞ into alignment with the direction i=[100]^Tas required for rectification. Additionally, a translation in the v-direction on one of the images is found to exactly align the scan-lines in both images. At this stage, it is assumed that the lines w and w′ are known. Therefore, v_aand v_bcan be eliminated from Eq. (7) by making use of the following: $\begin{array}{cc}\begin{array}{c}F={H^{\prime T}\left[i\right]}_{x}H\\ =[\begin{array}{ccc}{v}_a{w}_a^{\prime }-v_a^{\prime }{w}_a& v_b{w}_a^{\prime }-v_a^{\prime }{w}_b& v_c{w}_a^{\prime }-v_a^{\prime }\\ v_a{w}_b^{\prime }-v_b^{\prime }{w}_a& v_b{w}_b^{\prime }-v_b^{\prime }{w}_b& v_c{w}_b^{\prime }-v_b^{\prime }\\ v_a-v_c^{\prime }{w}_a& v_b-v_c^{\prime }{w}_b& v_c-v_c^{\prime }\end{array}].\end{array}& \left(12\right)\end{array}$

[0118] Using the last row of this matrix equation, it can be determined that:

[0119] v_a=F₃₁+v′_cw_a,  (13)

[0120] v_b=F₃₂+v′_cw_b,  (14)

[0121] v_c=F₃₃+v′_c.  (15)

[0122] Eqs. (13-15) are substituted into Eq (7), resulting in: $\begin{array}{cc}{H}_r=\left[\begin{array}{ccc}{F}_{32}-w_b{F}_{33}& w_a{F}_{33}-F_{31}& 0\\ F_{31}-w_a{F}_{33}& F_{32}-w_b{F}_{33}& F_{33}+v_c^{\prime }\\ 0& 0& 1\end{array}\right].& \left(16\right)\end{array}$

[0123] Similarly, v′_aand v′_bcan be eliminated to get: $\begin{array}{cc}{H}_r^{\prime }=\left[\begin{array}{ccc}{F}_{23}-w_b^{\prime }{F}_{33}& w_a^{\prime }{F}_{33}-F_{13}& 0\\ F_{13}-w_a^{\prime }{F}_{33}& F_{23}-w_b^{\prime }{F}_{33}& v_c^{\prime }\\ 0& 0& 1\end{array}\right].& \left(17\right)\end{array}$

[0124] Note that there remains a translation term involving v′_cin Eqs. (17) and (16). This shows that translation in the v-direction is linked between the two images, and that an offset of F₃₃is needed to align horizontal scan-lines. As such, v′_cis found so that the minimum v-coordinate of a pixel in either image is zero. As similarity transforms, H_rand H′_rcan only rotate, translate, and uniformly scale the images I and I′. None of these operations introduce any additional distortion. The combined transforms H_rH_pand H′_rH′_pare sufficient to rectify images I and I′. However, there remains additional freedom, corresponding to u and u′ of Eq. (4). These elements take the form of shearing transforms (described below) that can be optionally used to reduce distortion and to map the images into a more practical pixel range.

[0125] b. Shearing Transform

[0126] For the shearing transform, the freedom afforded by the independence of u and u′ is exploited to reduce the distortion introduced by the projective transforms H_pand H′_p. Due to this independence, only one image is discussed for brevity since the same procedure is identically performed on both images. The effect of u is modeled as a shearing transform: $S=\left[\begin{array}{ccc}a& b& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right].$

[0127] The translation components of S are set to zero since these terms add no useful freedom at this stage. Let $a={\left[\begin{array}{ccc}\frac{w-1}{2}& 0& 1\end{array}\right]}^T,b={\left[\begin{array}{ccc}w-1& \frac{h-1}{2}& 1\end{array}\right]}^T,c={\left[\begin{array}{ccc}\frac{w-1}{2}& h-1& 1\end{array}\right]}^T,\mathrm{and}d={\left[\begin{array}{ccc}0& \frac{h-1}{2}& 1\end{array}\right]}^T$

[0128] be points corresponding to the midpoints of the edges of I. Further, let â=H_rH_pa, be a point in the affine plane by dividing through so that â_w=1. It is noted that {circumflex over (b)}, ĉ and {circumflex over (d)} are similarly defined.

[0129] In general, H_pis a projective transform, so it is not possible to undistort I completely using the affine transform S. Instead perpendicularity is preserved and aspect ratio of the lines b{overscore ( )}d and c{overscore ( )}a. Let

[0130] x={circumflex over (b)}−{circumflex over (d)},

[0131] y=ĉ−â.

[0132] As the difference of affine points, x and y are vectors in the euclidean image plane. Perpendicularity is preserved when

[0133] (Sx)^T(Sy)=0,  (18)

[0134] and aspect ratio is preserved if $\begin{array}{cc}\frac{{\left(\mathrm{Sx}\right)}^T\left(\mathrm{Sx}\right)}{{\left(\mathrm{Sy}\right)}^T\left(\mathrm{Sy}\right)}=\frac{w^2}{h^2}.& \left(19\right)\end{array}$

[0135] Eqs. (18) and (19) represent quadratic polynomials in a and b (the unknown elements of S) whose simultaneous satisfaction is required. Using the method outlined in “Algorithms for intersecting parametric and algebraic curves l: Simple intersections, by D. Manocha and J Demmel, ACM Transactions on Graphics,13(1):73-100, 1994, which is incorporated herein by reference, the real solution $a=\frac{h^2{x}_v^2+w^2{y}_v^2}{\mathrm{hw}\left(x_v{y}_u-x_u{y}_v\right)}\mathrm{and}b=\frac{h^2{x}_u{x}_v+w^2{y}_u{y}_v}{\mathrm{hw}\left(x_u{y}_v-x_v{y}_u\right)},$

[0136] is found up to sign; the solution where a is positive is preferred. H_s(and similarly H′_s) is defined to be composed with a uniform scaling and translation as described below.

[0137] The combined transform H_sH_rH_pand similarly H′_sH′_rH′_p, rectify images I and I′ with minimal distortion. However these image may not be the appropriate size, or in the most desirable coordinate system. Therefore, additional uniform scaling and translation may be applied. It is important that the same scale factor, and the same v-translation be applied to both images to preserve rectification. Translations in the u-direction have no effect on rectification. In the example below, a uniform scale factor is chosen that preserves the sum of image areas. Other criteria may work equally well. Translations are also computed in u so that the minimum pixel coordinate has a u-coordinate of zero. A similar translation is found for the v direction, but the minimum is taken over both images to preserve rectification.

[0138] The present invention is embodied in a procedure for computing rectification homographies for a pair of images taken from distinct viewpoints of a 3D scene, as discussed in detail above. FIGS. 8-11 are pictures illustrating one working example of the present invention and show the results of each stage of the working example. The present invention is based on quantifiable 2D image measures and does not require 3D constructions. Further, these measures have intuitive geometric meanings. Namely, as discussed above distortion due to the projective component of rectification is minimized, and additional degrees of freedom are used in the affine component to further reduce distortion to a well defined minimum.

[0139] Referring back to FIG. 2 along with FIGS. 8-11, in this working example FIG. 8 shows an original image pair overlaid with several epipolar lines. FIG. 9 shows the image pair transformed by the specialized projective mapping H_pand H′_p220 and 222. Note that the epipolar lines are now parallel to each other in each image. FIG. 10 shows the image pair transformed by the similarity transform H_rand H′_r228, 230. Note that the image pair is now rectified (the epipolar lines are horizontally aligned). Last, FIG. 11 shows the final image rectification after shearing transform H_sand H′_s232, 234. Note that the image pair remains rectified, but the horizontal distortion is reduced.

[0140] The foregoing description of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto.