System and method for matching curves of multiple images representing a scene

[0002] 1. Field of the Invention

[0003] The present invention relates in general to processing digital data, and in particular, to a system and method for matching curves of multiple images representing a scene for stereo vision applications.

[0004] 2. Related Art

[0005] For stereo vision applications, accurate vector or mathematical representations of objects or scenes derived from two dimensional image data are very important. Vector or mathematical representations of a scene can be comprised of curve information derived from an image. Reliable curve matching is a difficult problem but is required in many vision-based applications. Curve matching is particularly difficult when the edges in question, such as for a general scene, are not limited to be on straight lines.

[0006] Although many techniques exist for detecting the edges of a scene, these techniques, however, have difficulties when applied to more general scenes. For example, some techniques use line matching methods applied to scenes containing mainly planar surfaces. However, they are not suitable for scenes containing curves because the line model is insufficient to describe curves. In addition, they are not suitable for scenes that are taken by a camera close to the scene, where the local affinity or similarity assumption for long line segments is not valid. Further, the projection of straight lines in 3D onto images may no longer be straight due to radial lens distortion.

[0007] Some problems related to curve matching are the design of good unary and binary measurements, and the definition of appropriate similarity and compatibility functions. Previous techniques and methods for curve matching provided examples on the unary measurements and similarity function between curves. Nevertheless, these previous methods were limited when dealing with binary measurements and compatibility functions. Namely, their compatibility functions were usually computed from measurements such as disparity or disparity gradient, which are only suitable for the description of relationships between two pairs of points, and are not scale invariant.

[0008] Therefore, what is needed is a system and method that solves the problems that prior methods encounter with general scenes with a system that performs curve matching (including lines) within a probabilistic relaxation framework. What is also needed is a system the uses the relaxation framework to progressively reduce the matching.

[0009] To overcome the limitations in the prior art as described above and other limitations that will become apparent upon reading and understanding the present specification, the present invention is embodied in a system and method for matching curves of multiple images representing a scene. The curve matching produces a geometrical representation of the scene from the images, which can be used for any suitable application, such as computer and stereo vision applications.

[0010] In general, first, multiple images depicting a scene are digitally received by the system. The images are graphical images digitally received and processed. For example, the images can be two dimensional image data, such as bitmap or raster image data. Curves of the images are then matched to correlate the two images of the scene for creating three dimensional (3D) curve information, such as 3D vector or mathematical information, of the scene. This 3D vector information can then be used in any suitable manner, for example, to digitally reconstruct the scene for stereo vision applications.

[0011] The present invention performs the curve matching (including lines) preferably within a probabilistic relaxation framework. The relaxation framework is used to progressively reduce the matching ambiguity. In other words, the relaxation framework is used to handle the curves and explicitly model uncertainty in line segment measurements. Epipolar geometry can be used to reduce the matching ambiguity between the line segments. Similarity-invariant unary and binary measurements suitable for curves are developed. An additional measurement can be introduced to model the uncertainty of the binary measurements, which can then be used to compute the matching support from neighboring matches. The present invention also includes preprocessing techniques to enhance curve matching.

[0012] Other aspects and advantages of the present invention as well as a more complete understanding thereof will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention. Moreover, it is intended that the scope of the invention be limited by the claims and not by the preceding summary or the following detailed description.

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

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

[0015] FIG. 2 is a general block diagram illustrating a system processing multiple images of a scene for stereo vision applications in accordance with the present invention.

[0016] FIG. 3 is a flow diagram for curve matching multiple images of a scene in accordance with the present invention.

[0017] FIG. 4 is a working example of FIG. 3 for curve matching two images of a scene in accordance with the present invention.

[0018] FIG. 5 is a neighborhood of a seed point in the left image and its correspondence in the right image of the working example of FIG. 4.

[0019] FIG. 6 is a configuration of two pairs of line segments in both images of the working example of FIG. 4.

[0020] FIG. 7 is a computation of the high curvature and the epipolar breakpoint of the working example of FIG. 4 in accordance with the present invention.

[0021] 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.

[0022] 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 personal 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 other computer system configurations, including 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 memory storage devices.

[0023] With reference to FIG. 1, an exemplary system for implementing the invention includes a general-purpose computing device in the form of a conventional personal 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 read only memory (ROM) 110 and random access memory (RAM) 112. A basic input/output system 114 (BIOS), containing the basic routines that help to transfer information between elements within the personal computer 100, such as during start-up, is stored in ROM 110. The personal computer 100 further includes 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 nonvolatile storage of computer readable instructions, data structures, program modules and other data for the personal computer 100. Although the exemplary environment described herein employs a hard disk, a removable magnetic disk 120 and a removable optical disk 124, it should be appreciated by those skilled in the art that other types of computer readable media which can store data that is accessible by a computer, such as magnetic cassettes, flash memory cards, digital video disks, Bernoulli cartridges, random access memories (RAMs), read only memories (ROM), and the like, may also be used in the exemplary operating environment.

[0024] 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 personal 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, personal computers typically include other peripheral output devices (not shown), such as speakers and printers.

[0025] The personal 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 another 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.

[0026] When used in a LAN networking environment, the personal computer 100 is connected to the local network 154 through a network interface or adapter 158. When used in a WAN networking environment, the personal 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 personal 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, such as a direct connection via an integrated services digital network (ISDN) connection.

[0027] Reliable curve matching of images representing a scene is important and desirable in many vision-based applications, especially when the edges of the images in question are not limited to be on straight lines. The present invention provides reliable curve matching of multiple images representing scenes, including general scenes where edges are not limited to be on straight lines. Curve matching in accordance with the present invention produces a geometrical representation of the scene from the images, which can be used for any suitable application, such as computer and stereo vision applications.

[0028] In general, the present invention can be embodied in a computer hardware or software system that matches curves (including lines) within a probabilistic relaxation framework. Similarity-invariant unary and binary measurements suitable for curves are computed. Also, a measurement to model the uncertainty of the binary measurements is computed. This measurement is used for determining matching support from neighboring matches.

[0029] FIG. 2 is a general block diagram illustrating a curve matching system for processing multiple images of a scene in accordance with the present invention. The system 200 can be used for any suitable computer application, such as computer or stereo vision applications. In general, image 1, image 2, . . . , image N (210, 212, 214) depicting a scene are digitally received by the system 200. The images (210, 212, 214) can be graphical images taken by a camera and containing two dimensional image data of the scene, in any suitable format, such as bitmap or raster image data format.

[0030] A curve matching module 216 receives the images (210, 212, 214) and correlates the images to each other by matching the curves of the images (210, 212, 214). The matched curves of the images represent geometrical three dimensional (3D) curve information 218, such as 3D vector information, of the scene. This 3D vector information geometrically represents the scene and can be used in any suitable manner, for example, to digitally reconstruct the scene for stereo vision applications 220.

[0031] The present invention reliably performs curve matching for a scene given at least two images of the scene. The present invention can also reliably perform curve matching when the edges of an object of the scene in question are not limited to be on straight lines. The present invention solves the problems discussed above that prior methods encounter with general scenes by performing curve matching (including lines) within a probabilistic relaxation framework. The relaxation framework is used to progressively reduce the matching ambiguity and will be discussed in detail below.

[0032] FIG. 3 is a flow diagram for curve matching multiple images of a scene in accordance with the present invention. In general, referring to FIG. 2 along with FIG. 3, first, images (210, 212, 214) are received by the system (step 310). The images (210, 212, 214) are graphical images, such as two dimensional bitmap or raster image data. Second, curves of the images (210, 212, 214) are represented as line segments (step 312) and the line segments are matched (step 314). Optionally, epipolar geometry can be used to break curves appropriately in order to reduce the matching ambiguity. Epipolar breaking techniques of the present invention (step 316) reduce matching complexity and will be discussed in detail below.

[0033] With regard to the line segments, a piecewise linear model is used to approximate curves with the line segments. The line segments of the images (210, 212, 214) are matched by computing unary and binary measurements (steps 318, 320). The relaxation framework of the present invention deals with curves and explicitly models the uncertainty in the binary measurements. For example, a set of binary measurements for the line segments can be computed, which are similarity-invariant and measured in the same physical space. The set of binary measurements are then integrated to provide a set of binary measurements and a compatibility function for the complete curve.

[0034] Last, the uncertainty in the combined binary measurements is progressively modeled for reducing ambiguities in the combined binary measurements by integrating line matching for curve matching (step 322). Namely, criteria of the line matching is integrated into criteria of curve matching. This is accomplished by first computing an individual variance or uncertainty of combined binary measurements for matched line segments of each curve (step 324). A global minimal variance criterion is then used to compute an integrated variance for the entire curve based on the individual variance of each matched line segment (step 328), which will be discussed in detail below.

[0035] Referring back to FIG. 2 along with FIG.3, information that can be used for curve matching falls into three categories, i.e., the geometrical constraint, the similarity between the curves, and the compatibility among the neighborhood matches. One important geometric constraint between views is the epipolar constraint, which is typically used in curve-based stereo matching systems for reducing the search space. Epipolar lines can be defined as horizontal scan lines, but are not restricted to be horizontal (the fundamental matrix can be used to define the epipolar geometry).

[0036] The similarity function between two curves is usually defined in a high dimensional feature space. The features may include attributes such as the intensity in the neighborhood, orientation, and the local shape characteristics. These are the unary measurements. The compatibility function among neighboring matches is usually defined by the relationship between neighboring pairs of matches. The compatibility function is usually related to the local affinity or similarity assumption, and the binary measurements, defining the relationship, could be the angle and distance between a pair of neighboring curves.

[0037] The relaxation technique of the present invention integrates the similarity function and the compatibility function to progressively reduce the matching ambiguity. Curves include both straight and non-straight edges. Edge points can be detected in sub-pixel accuracy by finding the zero-crossing between the integer pixels on the DOG (difference of Gausian) image. Adjacent edge points are then linked together into connected edge chains (also called curves for simplicity). The linking process does not include any heuristic processing such as one-pixel gap filling or straight line fitting. An edge chain (curve) is represented as a linked list, and is parameterized by the index variable.

[0038] The present invention also considers the uncertainty in the binary measurements. It should be noted that the local affinity or similarity assumption is only valid within a limited area of the image. Binary measurements obtained from curves far away from each other have more uncertainty than those from nearby curves. In the present invention, this is reflected in the computation of the compatibility function.

[0039] FIG. 4 is a working example of FIG. 3 for curve matching two images of a scene in accordance with the present invention. In the example 400, in general, a left image 410 and a right image 412 of a scene 414 are captured by any suitable means. Edges or curves 420 of each image 410, 412 defining the objects of the scene 414 are matched with the curve matching module 216 of FIG. 2. The matched curves 425 are used to determine a geometrical representation of the scene 414 in the form of curve information 430, which can be used in stereo matching applications.

[0040] A. A Probabilistic Relaxation Framework

[0041] A probabilistic relaxation framework for structural matching is used by the present invention. For notational purposes, curve matching is modeled as a labeling problem from the object space (left image 410) to the model space (right image 412). There are curves in the left image, and in the right. The curves in the left image form the object space, denoted by ={a₁, . . . , a}. The curves in the right image form the model space, each labeled as ω_j. As discussed above, the object 410 is matched to the model 412. Thus, assigned to each object, a_iis a label θ_i, which may take as its value any of the +1 model labels that form the set Ω={ω₀, ω₁, . . . ,ω}, where ω₀is the null label used to label curves for which no match in the right image is appropriate. Four sets of indices are defined for convenience as:

[0042] ₀≡{1, . . . ,}, _i≡{j|jε₀,j≠i},

[0043] ₀≡{0, . . . ,}, and _i≡{j|jε₀,j≠i}.

[0044] The unary measurement set is defined as ={x_i|i ε₀} where x_iis the unary measurement vector for the object a_i. Unary measurements include intensity similarity, and will be addressed below. The binary measurement set for the object a_iis defined as _i={A_ij|jε_i}, where A_ijis the vector of binary measurements between objects a_iand a_j. Binary measurements include distance between two curves, and will be discussed below. A special measurement set _i={B_ij|jε_i} is also defined, where B_ijis the uncertainty measurement to be defined later. Upper-case P is used to denote the probability of an event, lower-case p is used to denote the probability density function, and _v(μ,Σ) to denote the Gaussian probability density function of a random vector v with the mean μ and the covariance matrix Σ.

[0045] 1. A Framework With Uncertainty Measurement:

[0046] With the above notation, the matching problem becomes that of finding for object a_ia model label ω_θwith the highest probability given the measurements , _i, and _i: $\begin{array}{cc}P\left({\theta }_i={\omega }_{{\theta }_i}|𝒳,{𝒜}_i,{ℬ}_i\right)=\underset{\mathrm{\omega \lambda }\in \Omega }{\max }P\left({\theta }_i={\omega }_{\lambda }|𝒳,{𝒜}_i,{ℬ}_i\right)& \left(1\right)\end{array}$

[0047] For the convenience of the discussion that follows, the notation of the event set is introduced as ^λ={θ_i=ω_λ}∪{θ_j=ω_θ|jεN_i} to indicate that object a_iis labeled with a given label ω_λwhile other objects can change their labels. For ^θ, the ith event _i^θis equivalent to event θ_i=ω_θ. Using Bayes' formula and the theorem of total probability, the result is: $\begin{array}{cc}\begin{array}{c}p\left({ℒ}_i^{{\theta }_i}|𝒳,{𝒜}_i,{ℬ}_i\right)=\frac{p\left({ℒ}_i^{{\theta }_i},𝒳,{𝒜}_i,{ℬ}_i\right)}{p\left(𝒳,{𝒜}_i,{ℬ}_i\right)}\\ =\frac{\sum _{\left\{{\omega }_{{\theta }_j}\in \Omega ,j\in N_i\right\}}p\left({ℒ}^{{\theta }_i},𝒳,{𝒜}_i,{ℬ}_i\right)}{\sum _{{\omega }_{\lambda }\in \Omega }\sum _{\left\{{\omega }_{{\theta }_j}\in \Omega ,j\in N_i\right\}}p\left({ℒ}^{\lambda },𝒳,{𝒜}_i,{ℬ}_i\right)}\end{array}& \left(2\right)\end{array}$

[0048] By applying the product rule for p(^λ,,_i,_i), the following is produced: $\begin{array}{cc}\begin{array}{c}p\left({ℒ}^{\lambda },𝒳,{𝒜}_i,{ℬ}_i\right)=p\left(𝒳|{ℒ}^{\lambda },{𝒜}_i,{ℬ}_i\right)p\left({ℒ}^{\lambda },{𝒜}_i,{ℬ}_i\right)\\ =p\left(𝒳|{ℒ}^{\lambda }\right)p\left({𝒜}_i|{ℒ}^{\lambda },{ℬ}_i\right)p\left({ℒ}^{\lambda },{ℬ}_i\right)\\ =p\left(𝒳|{ℒ}^{\lambda }\right)P\left({ℒ}^{\lambda }\right)p\left({𝒜}_i|{ℒ}^{\lambda },{ℬ}_i\right)p\left({ℬ}_i\right)\\ =P\left({ℒ}^{\lambda }|𝒳\right)p\left({𝒜}_i|{ℒ}^{\lambda },{ℬ}_i\right)p\left(𝒳\right)p\left({ℬ}_i\right)\end{array}& \left(3\right)\end{array}$

[0049] where the second equation holds because (unary measurement set) does not depend on _i(binary measurement set) and _i(uncertainty of the binary measurement set), and the third equation holds because ^λ and _iare independent. Since there is no knowledge about and _i, p() and p(_i) are constants. Substituting (3) into (2) produces: $\begin{array}{cc}p\left({ℒ}_i^{{\theta }_i}|𝒳,{𝒜}_i,{ℬ}_i\right)=\frac{\sum _{\left\{{\omega }_{{\theta }_j}\in \Omega ,j\in N_i\right\}}P\left({ℒ}^{{\theta }_i}|𝒳\right)p\left({𝒜}_i|{ℒ}^{{\theta }_i},{ℬ}_i\right)}{\sum _{{\omega }_{\lambda }\in \Omega }\sum _{\left\{{\omega }_{{\theta }_j}\in \Omega ,j\in N_i\right\}}P\left({ℒ}^{\lambda }|𝒳\right)p\left({𝒜}_i|{ℒ}^{\lambda },{ℬ}_i\right)}& \left(4\right)\end{array}$

[0050] Assuming that the events in the ^λ are independent, it follows that: $P\left({ℒ}^{\lambda }|𝒳\right)=P\left({\theta }_i={\omega }_{\lambda }|x_i\right)\prod _{j\in N_i}P\left({\theta }_j={\omega }_{{\theta }_j}|x_j\right)$

[0051] Since A_ijonly depends on the ith and jth events in ^λ and B_ij, and since A_ijs are independent from each other, the following is true: $p\left({𝒜}_i|{ℒ}^{\lambda },{ℬ}_i\right)=\prod _{j\in N_i}p\left({𝒜}_{\mathrm{ij}}|{\theta }_i={\omega }_{\lambda },{\theta }_j={\omega }_{{\theta }_j},B_{\mathrm{ij}}\right)$

[0052] With the following simple notation $P_j^{\lambda }=P\left({\theta }_j={\omega }_{{\theta }_j}|x_j\right)p\left({𝒜}_{\mathrm{ij}}|{\theta }_i={\omega }_{\lambda },{\theta }_j={\omega }_{{\theta }_j},B_{\mathrm{ij}}\right)$

[0053] it follows that: $\begin{array}{cc}\sum _{\left\{{\omega }_{{\theta }_j}\in \Omega ,j\in N_i\right\}}P\left({ℒ}^{\lambda }|𝒳\right)p\left({𝒜}_i|{ℒ}^{\lambda },{ℬ}_i\right)\begin{array}{c}=P\left({\theta }_i={\omega }_{\lambda }|x_i\right)\sum _{{\omega }_{{\theta }_i}\in \Omega }{P}_1^{\lambda }\dots \sum _{{\omega }_{{\theta }_N}\in \Omega }{P}_{𝒩}^{\lambda }\\ =P\left({\theta }_i={\omega }_{\lambda }|x_i\right)\prod _{j\in N_i}\sum _{{\omega }_{{\theta }_j}\in \Omega }{P}_j^{\lambda }\end{array}& \left(5\right)\end{array}$

[0054] Substituting (5) into (4) leads immediately to $\begin{array}{cc}P\left({\theta }_i={\omega }_{{\theta }_i}|𝒳,{𝒜}_i,{ℬ}_i\right)=\frac{P\left({\theta }_i={\omega }_{{\theta }_i}|x_i\right)𝒬\left({\theta }_i={\omega }_{{\theta }_i}\right)}{\sum _{{\omega }_{\lambda }\in \Omega }P\left({\theta }_i={\omega }_{\lambda }\right){𝒬}^{\left(n\right)}\left({\theta }_i={\omega }_{\lambda }\right)}& \left(6\right)\end{array}$

[0055] where the support function is given by $\begin{array}{cc}\begin{array}{c}𝒬\left({\theta }_i={\omega }_{\alpha }\right)=\prod _{j\in N_i}\sum _{{\omega }_{\beta }\in \Omega }{P}_j^{\beta }\\ =\prod _{j\in N_i}\sum _{{\omega }_{\beta }\in \Omega }P\left({\theta }_j={\omega }_{\beta }|x_j\right)\\ p\left({𝒜}_{\mathrm{ij}}|{\theta }_i={\omega }_{\alpha },{\theta }_j={\omega }_{\beta },B_{\mathrm{ij}}\right)\end{array}& \left(7\right)\end{array}$

[0056] where the first item in the summation is the similarity function, and the second is the compatibility function that takes into account explicitly the uncertainty measurement Bij.

[0057] Based on (6), the labeling probability is updated in a relaxation scheme according to the following iterative equation: $\begin{array}{cc}{\hspace{0.17em}}^{P\left(n+1\right)}\left({\theta }_i={\omega }_{{\theta }_i}\right)=\frac{P^{\left(n\right)}\left({\theta }_i={\omega }_{{\theta }_i}\right){𝒬}^{\left(n\right)}\left({\theta }_i={\omega }_{{\theta }_i}\right)}{\sum _{{\omega }_{\lambda }\in \Omega }{P}^{\left(n\right)}\left({\theta }_i={\omega }_{\lambda }\right){𝒬}^{\left(n\right)}\left({\theta }_i={\omega }_{\lambda }\right)}& \left(8\right)\end{array}$

[0058] Where n is the iteration number, and P⁽⁰⁾(θ_i=ω_θ)=P(θ_i=ω_θ|x_i). The iteration process terminates if the change in the probabilities is less than a predefined small value or the maximum number of iterations is reached.

[0059] As has been mentioned above, candidate curves in the right view for the current curve a_jin the left view are found by the epipolar geometry. This is equivalent to reducing the model label set for a_jfrom Ω to Ω_jin the above derivations. Since the size of Ω_jis usually much smaller than that of Ω, the computational efficiency of the relaxation process is increased considerably.

[0060] 2. Adapted Framework With Combined Measurements

[0061] In the present invention, the unary and binary measurements depend on information in both object and model space (i.e., left and right image 410, 412). Therefore, measurements for combined object-model pairs are considered. Namely, let x_i^(α)(αε₀) be the combined unary measurement defined for the pair of the ith object and the αth model. The unary measurement of object a_i, x_i, is then itself a set of combined unary measurements, i.e., {x_i^(α)|αε₀}. Let A_ij^(αβ)(αε₀,βε₀) be the combined binary measurement defined for two object-model pairs (i,α) and (j,β). Then, the binary measurement A_ijis itself a set of combined binary measurements, i.e., {A_ij^(αβ)|αε₀,βε₀}.

[0062] In order to adapt the framework for working with the combined measurements, a similarity function is first considered, as discussed in Structural matching in computer vision using probabilistic relaxation by William J. Christmas, Josef Kittler, and Maria Petrou, IEEE Trans. PAMI, 17(8):749-764, August 1995, which is incorporated herein by reference. Since the event θ_j=ω_β does not depend on the combined unary measurements other than the x_j^(β), it follows that:

[0063] P(θ_j=ω_β|{x_j^(β)|βε₀})=P(θ_j=ω_β|x_j^(β))  (9)

[0064] Similarly, _ij^(αβ)'s are independent of each other, and hence: $p\left(A_{\mathrm{ij}}|{\theta }_i={\omega }_{\alpha },{\theta }_j={\omega }_{\beta },B_{\mathrm{ij}}\right)$ $\begin{array}{c}=p\left(\left\{A_{\mathrm{ij}}^{\mathrm{kl}}\right\}|{\theta }_i={\omega }_{\alpha },{\theta }_j={\omega }_{\beta },B_{\mathrm{ij}}\right)\\ =\prod _{\begin{array}{c}k\in {ℳ}_0\\ l\in {ℳ}_0\end{array}}p\left(A_{\mathrm{ij}}^{\mathrm{kl}}|{\theta }_i={\omega }_{\alpha },{\theta }_j={\omega }_{\beta },B_{\mathrm{ij}}\right)\end{array}$

[0065] For A_ij^(kl)which are not equal to A_ij^(αβ)(i.e., k and l are not matched with i and j), there is no information about how to compute the binary measurement A_ij^(kl). Hence, it is assumed that the density function is a uniform distribution, i.e., a constant, within its domain. In consequence, it follows that: $\begin{array}{cc}p\left(A_{\mathrm{ij}}|{\theta }_i={\omega }_{\alpha },{\theta }_j={\omega }_{\beta },B_{\mathrm{ij}}\right)=ϵp\left(A_{\mathrm{ij}}^{\left(\mathrm{\alpha \beta }\right)}|{\theta }_i={\omega }_{\alpha },{\theta }_j={\omega }_{\beta },B_{\mathrm{ij}}\right)& \left(10\right)\end{array}$

[0066] where {A_ij^(kl)} is the abbreviation of {A_ij^(kl)|kε₀,lε₀} and ε=Π_{kl≠αβ}p(A_ij^(kl)|B_ij) is a constant. Thus, by substituting (10) and (9) into (7),(7) into (6), and eliminating the constant, ε, (6) can be rewritten as: $\begin{array}{cc}P\left({\theta }_i={\omega }_{{\theta }_i}|𝒳,{𝒜}_i,{ℬ}_i\right)=\frac{P\left({\theta }_i={\omega }_{{\theta }_i}|x_i^{\left({\theta }_i\right)}\right)𝒬\left({\theta }_i={\omega }_{{\theta }_i}\right)}{\sum _{{\omega }_{\gamma \in \Omega }}P\left({\theta }_i={\omega }_{\lambda }|x_i^{\left(\lambda \right)}\right)𝒬\left({\theta }_i={\omega }_{\gamma }\right)}& \left(11\right)\end{array}$

[0067] and (7) as: $\begin{array}{cc}\begin{array}{c}𝒬\left({\theta }_i={\omega }_{\alpha }\right)=\prod _{j\in {𝒩}_i}\sum _{{\omega }_{\beta }\in \Omega }{P}_j^{\beta }\\ =\prod _{j\in N_i}\sum _{{\omega }_{\beta }\in \Omega }P\left(\theta ={\omega }_{\beta }|x_j^{\left(\beta \right)}\right)\\ =p\left({𝒜}_{\mathrm{ij}}^{\left(\mathrm{\alpha \beta }\right)}|{\theta }_i={\omega }_{\alpha },{\theta }_j={\omega }_{\beta },B_{\mathrm{ij}}\right)\end{array}& \left(12\right)\end{array}$

[0068] B. The Combined Unary Measurement and the Similarity Function

[0069] A combined unary measurement invariant to similarity (scaled Euclidean) transformation is developed below and the similarity function is computed based on it. It should be noted that preferably only selected seed points on both the left and the right curves are considered; the right seed points are obtained by intersecting the epipolar lines of the left seed points with the curve in the right image; and for each seed point on the left curve and its corresponding point on the right curve, a correlation score is computed between their neighborhoods. In addition, it is ensured that the score computation is less sensitive to the image transformation.

[0070] 1. Seed Score

[0071] FIG. 5 is a neighborhood of a seed point in the left image and its correspondence in the right image of the working example of FIG. 4. For each seed point k_Lin the left image, a neighborhood (k_L) is assigned. The neighborhood (l_R) of the corresponding seed point l_Ron the right image is defined by (k_L) and a similarity transformation.

[0072] A similarity transformation can be of the following form:

[0073] x′=sR_θx+t  (23)

[0074] where s is the scale, R_θ is the rotation matrix with angle θ, and t is the translation vector. It maps a point x in one image to a point x′ in the other. If there are two pairs of matched points (p₁,p′₁) and (p₂,p′₂) the following can be obtained: $\{\begin{array}{ccc}s& =& \frac{\left|\right|p_1^{\prime }-p_2^{\prime }\left|\right|}{\left|\right|p_1-p_2\left|\right|}\\ \cos \theta & =& \stackrel{\_}{\left(p_1-p_2\right)}·\stackrel{\_}{\left(p_1^{\prime }-p_2^{\prime }\right)}\\ t& =& \left[\left(p_1^{\prime }+p_2^{\prime }\right)-s{R}_{\theta }\left(p_1+p_2\right)\right]2\end{array}$

[0075] where {overscore (v)} denotes the normalized vector of v.

[0076] The similarity transformation can be estimated from a pair of points inside the neighborhood and their corresponding points in the right image. The pair of seed points are already obtained, and another pair requires selection. The extreme point of (k_L) can be chosen along the curve, p₁, and its corresponding point p′₁can be computed by intersecting the epipolar line of p₁,_p1, with the curve in the right image. The estimation of the similarity transformation from two pairs of points was given above.

[0077] The seed score is computed as the correlation between these two corresponding neighborhoods, and is given by: $\begin{array}{cc}S\left(k_{ℒ},l_{ℛ}\right)=\sum _{\begin{array}{c}\xi \in 𝒩\left(k_{ℒ}\right)\\ \eta \in 𝒩\left(l_{ℛ}\right)\end{array}}\frac{\left[I_{ℒ}\left(\xi \right)-\stackrel{\_}{I}\left(k_{ℒ}\right)\right]\lfloor I_{ℛ}\left(\eta \right)-\stackrel{\_}{I}\left(l_{ℛ}\right)\rfloor }{{𝒩}_n\sigma \left(I_{k_{ℒ}}\right)\sigma \left(I_{l_{ℛ}}\right)}& \left(13\right)\end{array}$

[0078] where I_i(χ) is the intensity value on a point χ in the ith image, (χ) is the neighborhood for seed point χ, η is a point in the second image corresponding to point ξ in the first image according to the similarity transformation described above, and _nis the number of points in the neighborhood. The details of computing the mean ({overscore (I)}(χ)) and the standard deviation (σ(χ)) in (χ) can be found in Epipolar geometry in stereo by Gang Xu and Zhengyou Zhang. Motion and Object Recognition, Kluwer Academic Publishers, 1996, which is incorporated herein by reference. The correlation score thus computed is invariant under the similarity transformation.

[0079] 2. The Curve Score as the Combined Unary Measurement

[0080] The curve score (i,j) for the ith curve in the left image 410 and the jth curve in the right image 412, which is the combined unary measurement in the context, is the average of all possible seed scores. That is, $\begin{array}{cc}ℒ\left(i_{ℒ},j_{ℛ}\right)=\frac{1}{{𝒩}_i}\sum _{\begin{array}{c}{k}_{ℒ}\in \mathrm{Sd}\left(i_{ℒ}\right)\\ l_{ℛ}\in \mathrm{Sd}\left(j_{ℛ}\right)\end{array}}S\left(k_{ℒ},l_{ℛ}\right)& \left(14\right)\end{array}$

[0081] where , is total number of seed points on i, and Sd(i) and Sd(j) are the seed point sets of the left and right curves, respectively.

[0082] 3. Similarity Function

[0083] The similarity function can be computed as follows. The combined unary measurement x_i^(α)in (11) is a scalar, and is denoted by χ_i^α. It is equal to (θ_i,ω_α) computed above. According to Bayes' theorem, $\begin{array}{cc}P\left({\theta }_i={\omega }_{{\theta }_i}|x_i^{\left(\alpha \right)}\right)=\frac{p\left(x_i^{\left(\alpha \right)}|{\theta }_i={\omega }_{\alpha }\right)\hat{P}\left({\theta }_i={\omega }_{\alpha }\right)}{\sum _{{\omega }_{\lambda \in \Omega }}p\left(x_i^{\left(\alpha \right)}|{\theta }_i={\omega }_{\lambda }\right)\hat{P}\left({\theta }_i={\omega }_{\lambda }\right)}& \left(15\right)\end{array}$

[0084] where {circumflex over (P)}(θ_i=ω_λ) is the prior probability equal to a prefixed value ζ if λ=0(i.e., no match), and to (1−ζ)/₀otherwise. It is assumed that p(x_i^(λ)|θ_i=ω_λ)=(μ_l,σ_l). The value of μ_land σ_lcan be computed from the histogram of x_i^(λ)using the initial matches. The initial matches could be obtained by selecting only the labeling with x_i^(λ)that is the highest in both {x_i^(β)|βε₀} and {x_j^(γ)|jε₀}.

[0085] The unary measurements are used in (15) to compute P(θ_i=ω_α|x_i^(α)). It is then used to initialize the relaxation scheme, that is:

[0086] P⁽⁰⁾(θ_i=ω_α)=P(θ_i=ω_α|x_i^(α)).

[0087] It should be noted that since the unary measurement is similarity invariant, there is no need to introduce a motion related term for the computation of the similarity function.

[0088] C. The Combined Binary Measurement and the Compatibility Function

[0089] In order to efficiently compute combined binary measurements, a curve is approximated by a set of line segments connected by the seed points mentioned above. This approximation is accurate provided that an edge chain is broken at the high curvature points (to be detailed below), and that seed points are not very far from each other. A set of combined binary measurements for the line segments is developed in the present invention. These measurements are grouped together in an optimal way to form the combined binary measurements for curves. The compatibility function for curves can then be computed. The uncertainty measurements for the combined binary measurements are also provided.

[0090] 1. Combined Binary Measurements for Line Segments

[0091] As mentioned above, the similarity transformation is a reasonable mapping from a neighborhood in one image to the corresponding neighborhood in the other. FIG. 6, is a configuration of two pairs of line segments in both images of the working example of FIG. 4 wherein two pairs of line segments are shown. The similarity transformation x′=sR_θx+t can be computed from (p₁,p′₁) and (p₂,p′₂) as described above for similarity transformation.

[0092] The following expression, b₁=sR_θq₁+t, b₂=sR_θq₂+t, is computed and forms a random vector z as the follows:

[0093] z=[v₁^(χ),v₁^(y),v₂^(χ),v₂^(y)]^T  (16)

[0094] where v₁=b₁−q′₁, and v₂=b₂−q′₂. Ideally, if the local similarity transformation is valid and the point coordinates are noise-free, the result is z=0. Typically, these conditions are not satisfied in practice, and thus, it is assumed that the components of z are i.i.d, and have the same standard deviations σ, i.e., z=_z(0,Σ) where Σ=diag({σ}).

[0095] There are several advantages of the binary measurements z given here over the traditional ones. First, measurements are invariant under the similarity transformation. Traditional measurement, such as the distance between the midpoints of line segments, may suffer from the scale change between views. Also, the set of binary measurements is complete. Under similarity transformation, two pairs of line segments have 8 equations, and there are 4 degrees of freedom for the similarity transformation. Therefore, the number of invariants is equal to 4, and the same number of measurements is produced. Further, measurements are evaluated in the same physical space, namely, they are quantified in pixels in the second image. This means that only one a for all the measurements is needed, whose computation is given below.

[0096] 2. Combined Binary Measurement for Curves and the Compatibility Function

[0097] A pair of curves a_iand a_jis now considered. The numbers of line segments are defined as _iand _j, respectively. For each line segment on the shorter curve, the closest segment from the other curve is selected, and measurement z as defined in (16) is computed. The rationale of choosing the closest line segments is that the similarity transformation better applies to a small neighborhood than to a larger one. For the vector set {z_j|jε[1, . . . , ]}, where =min (_i,_j), the following measurement vector is considered:

[0098] {tilde over (z)}=ζ₁z₁+ . . . +ζz  (17)

[0099] where ζ's are coefficients and $\sum _{k=1}^K{Ϛ}_k=1.$

[0100] It is obvious that {tilde over (z)} is also a joint Gaussian with {tilde over (z)}=_{{tilde over (z)}}(0,{tilde over (Σ)}) where {tilde over (Σ)}=diag[{{tilde over (σ)}}], and

[0101] {tilde over (σ)}²=ζ₁²σ₁²+ . . . +ζ²σ²  (18)

[0102] Next, ζ_jis selected to minimize (18), which yields $\begin{array}{cc}{Ϛ}_i={\left[{\sigma }_i^2\sum _{j=1}^K{\sigma }_j^{-2}\right]}^{-1}& \left(19\right)\end{array}$

[0103] Equation (17) is an unbiased estimate of the measurement error with minimal variance. The compatibility function is then given by $\begin{array}{cc}p\left(A_{\mathrm{ij}}^{\left(\mathrm{\alpha \beta }\right)}|{\theta }_i={\omega }_{\alpha },{\theta }_j={\omega }_{\beta },B_{\mathrm{ij}}\right)=p\left(\tilde{z}|{\theta }_i={\omega }_{\alpha },{\theta }_j={\omega }_{\beta },\sum ^{~}\right)={𝒩}_{\tilde{z}}\left(0,\sum ^{~}\right)& \left(20\right)\end{array}$

[0104] where A_ij^(αβ)={tilde over (z)} is the combined binary measurements, and B_ij={tilde over (Σ)} is the uncertainty measurements.

[0105] 3. The Distance Between Segments and the Standard Deviation

[0106] The standard deviation σ of vector z in (17) should be a function of the distance between the line segments. This is because the local similarity assumption becomes weaker when becomes larger. The function that is used is: $\begin{array}{cc}\sigma \left(d\right)=\frac{\rho }{\sqrt{2\pi }}\left[\left(1-\gamma \right)\left(1-l^{-\frac{{\lambda }^2}{r^2}}\right)+\gamma \right]& \left(21\right)\end{array}$

[0107] where ρ=min(,), and are respectively the image width and height, τ is a positive scalar that controls the range within which the contribution from neighboring segment is effective, and γ={square root over (2πσ⁰/ρ)} where σ⁰is the desired standard deviation when the neighboring segment is very close to the segment under consideration. Several observations can be made for the function defined in (21):

[0108] Namely, when is small, σ()≈σ⁰a which is the desired standard deviation when neighboring segments are close. Also, when is much larger than τ,σ()≈ρ/{square root over (2π)}. In this case, _z(0,Σ)≈1/ρ⁴, indicating that the probabilistic density function approaches to a uniform distribution, and provides no information about the compatibility between the two pairs of line segments. Further, the intermediate value of or σ() varies smoothly between the above two extreme cases.

[0109] As a consequence of the second point above, when all the distance measurements {_j|jε[1, . . . , ]} are much larger than τ, the compatibility function in (20) is approximately a constant 1/ρ⁴. As a result, if all the other curves are far from the current curve a_i, it is not difficult to see, from (8) and the definition of , that P⁽ⁿ⁺¹⁾(θ_i=ω_θ)=P⁽ⁿ⁾(θ_i=ω_θ). This is in accordance with the above that the labeling probability cannot be improved when the neighborhood support is weak.

[0110] The adjustment of the parameter τ depends on the type of the scene in question. If the scene is close to the image producing device, such as a camera, there is a severe perspective distortion, and τ needs to be small enough to discard the support from curves far away. On the other hand, if the scene is far from the camera, τ could be large in order to include support from as many neighboring curves as possible.

[0111] D. Preprocessing

[0112] In the present invention, as described above, computational complexity is reduced if a seed point on one curve matches at most one seed point on the other. Also, it is assumed that in computing binary measurements, a curve is approximated by a piece-wise linear model with line segments. Two preprocessing techniques described below can be used to ensure that a seed point on one curve matches at most one seed point (epipolar breaking) and that the binary measurements are computed with a curve approximated by a piece-wise linear model (high curvature breaking). It should be noted that any suitable technique can be used to achieve the above.

[0113] 1. Epipolar Breaking

[0114] When intersecting with a curve, an epipolar line may cut the same curve several times. In order to reduce the matching complexity, the epipolar line of a seed point in one image cuts at most once the corresponding curve in the other image. The technique described below breaks curves into shorter pieces, and thus, each piece only cuts an epipolar line once.

[0115] FIG. 7 is a computation of the high curvature and the epipolar breakpoint of the working example of FIG. 4 in accordance with the present invention. The epipolar breaking technique of the present invention is based on the following observations. First, the only epipolar line passing through a given point p on a curve in one image is the line connecting point p and epipole l in that image, as shown in FIG. 7. Second, it is impossible for a curve to have multiple intersections with an epipolar line if there is no point on the curve whose tangent vector is parallel to the epipolar line passing through that point. As such, it follows that if a curve can be broken at the point p where the tangent vector T(p) is parallel to the epipolar line e_p, the problem will be solved.

[0116] Namely, the cosine of the angle between the tangent vector and the epipolar line is computed:

[0117] ε_p={overscore (T({overscore (e

[0118] where {overscore (v)} is the normalized vector of v. As depicted in FIG. 7, an index worm w_p(s)=p+s,s=[−, . . . , ] of size 2+1, centered on the pth edge point, crawls along the edge chain, and ε_pis computed each time when an edge point is visited. The tangent vector T(p) is approximated by V₂in FIG. 7. The original edge chain is broken at point p if its ε_pis the local maxima or minima, and the absolute value |ε_p| is larger than a predefined threshold (for example, 0.99 in one implementation). Therefore, curves are preferably not broken at reflection points.

[0119] 2. High Curvature Breaking

[0120] In order to have a good piecewise linear approximation to a curve, it is necessary to break the curve at points with high curvature. The high curvature breaking technique works in a very similar way as the epipolar breaking technique described above. For instance, the curvature is approximated by $\begin{array}{cc}{𝒦}_p=\frac{\left|\right|\stackrel{\_}{{𝒯}_1}-\stackrel{\_}{{𝒯}_2}\left|\right|}{\left|\right|{𝒯}_1\left|\right|+\left|\right|{𝒯}_2\left|\right|}& \left(22\right)\end{array}$

[0121] where ₁=C(w_p())−C(w_p(0)), ₂=C(w_p(0))−C(w_p(−)), and _jdenotes the normalized vector of _j. The original edge chain is broken at point p if its curvature _pis the local maxima and is larger than a predefined threshold (0.85 in one implementation).

[0122] The present invention performs curve matching within a probabilistic relaxation framework for determining a geometrical representation of a scene. Novel combined unary and binary measurements of the present invention are used in this framework, which are similarity-invariant. Also, the uncertainty in binary measurements is explicitly modeled, which is very important in computing the matching support from neighboring matches. Preprocessing techniques, such as epipolar breaking and high curvature breaking, contributing to the success of the curve matching have been developed and described.

[0123] 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.