[IEEE 14th International Conference on Image Analysis and Processing (ICIAP 2007) - Modena, Italy...

A New Stereo Algorithm Integrating Luminance, Gradient and Segmentation Informations in a Belief-Propagation Framework

Nello Balossino, Maurizio Lucenteforte, Luca Piovano

Dept. of Computer Science Università degli Studi di Torino

{nello.balossino,maurizio.lucenteforte,piovano}@di.unito.it

Giuseppe Pettiti, Massimiliano Spertino IEIIT of the Italian National Council of

Research (CNR) [email protected],

[email protected]

Abstract

The paper deals with the design and implementation of a stereo algorithm. Disparity map is formulated as a Markov Random Field with a new smoothness constraint depending not only on image derivatives, but also on segmentation results and gradient directions. With these constraints we force disparity continuity inside each segmented object, while its contours are well preserved. Moreover we have designed a modified version of Belief Propagation which gives the solution to the stereo matching problem: the optimization has remarkable improvements and especially with respect to message propagation, which is actually driven by segmentation and boundary knowledge. Preliminary results are presented both on synthetic and benchmark images to demonstrate the effectiveness of our method. 1. Introduction

Stereo matching is a fundamental task in computer vision. It relies on the search for correspondences in two images, in order to infer the 3D structure of the framed scene [9].

The goal of a stereo algorithm is the computation of disparities for all pixels in an image. This process for its inherent nature is ambiguous because of multiple possible assignments to the same pixel. Anyhow the interest for stereo vision, as an interface with the real world, makes it an active research field, especially for its many possible applications: view synthesis [3], image based rendering, autonomous navigation, medical imaging, surveillance, industrial automation, virtual reality, and so on.

Several techniques have been proposed during the last decades: the simplest ones make use of correlation [11] or match extracted features [4] (local methods), others are probabilistic [1] and cooperative [17]. However many other approaches can be found in literature: for instance, an interesting review on this topic can be found in [13], where a very comprehensive taxonomy is given in order to classify and evaluate many of them.

Among stereo algorithms, those making use of probabilistic models (like Markov random fields (MRF) and Bayesian networks) are the most effective and robust. Solution to this kind of problems is generally NP-hard, so different approximate and sub-optimal algorithms, such as graph cuts [8] and belief propagation [14], have been proposed. The above methodologies integrate different visual constraints to recover disparity especially in textureless and occluded regions, where local methods typically fail.

In our work we propose a probabilistic MRF model for stereo disparity based on a novel visual constraint depending not only on image derivatives, but also on segmentation results and gradient directions. Moreover we implement a modified version of the Belief Propagation scheme proposed in [7], by integrating segmentation and contour knowledge during optimization. The key idea here is that a robust belief propagation should be object-driven, namely it should stops and be re-initialized whenever a new object is detected. The algorithm refinement is still in progress, but however we are able to give few preliminary results, both on synthetic and benchmark images. These results only refer to a partial implementation of the whole set of constraints we want to deal with and of the optimization method. Although in a partial form, they are quite comforting about the strength and the effectiveness of the methodology , so that its future

14th International Conference on Image Analysis and Processing (ICIAP 2007)0-7695-2877-5/07 $25.00 © 2007

development could lead to very interesting improvements.

The paper is organized as follows: in section 2 our algorithm is outlined, with a brief digression on probabilistic methods and in particular on MRFs. In section 3 we discuss about preliminary results on synthetic and benchmark images, while section 4 is focused on conclusions and future work.

2. Our algorithm

We address stereo matching problem using a probabilistic approach. We have implemented in our work a Belief Propagation algorithm, in particular a version based on Single Connected Graphs. Moreover, constraints on segmentation process and knowledge about object boundaries are exploited in order to build more accurate dense disparity maps.

2.1. Probabilistic models and Markov random fields

Graphs are an useful tool to successfully represent a probabilistic model, where edges describe relationships among different variables. This fact allows both to simplify system modeling and to draw high-performance, fast algorithms. It has been shown in a number of works (i.e. [14], [15]) that MRF is the most suited approach to express a probabilistic model in retrieving a disparity map. Therefore, it is the same model used in our work. (For a more detailed discussion on MRFs, please refer, for instance to [12]).

We consider our pixel disparity as a random variable and we will refer to it in the following as xp or xij , where p is a pixel located in the reference image IL of the stereo pair (IL,IR) at the i-th row and j-th column. A possible value that each variable can assume is one (and only one) of the Λ discrete states representing disparities.

In our MRF, each disparity xp has an associated cost resulting from the intensity difference between the two matching pixels p and p + xp. This cost is directly involved in defining the observability function

),( pp yxφ , a measure for estimating how much a disparity value xp is consistent with respect to the observed luminance difference yp. Another compatibility function is provided, and we call it

),( qp xxψ , where q is the position of an adjacent pixel to p in a MRF. This function influences disparity assignment with respect to some previous computed result. Although these compatibility functions are written considering only close pixels, they can however condition all the other variables.

Having defined an observability and a compatibility function, we can write the MRF joint probability as:

∏∏=qp

qpr

rrNN xxyxyyxxP,

11 ),(),(),...,,,...,( ψφ (1)

where p, q are the positions of a pair of adjacent pixels. The final disparity map is the configuration x1, x2, ..., xN maximizing the likelihood P defined above.

2.2. Probabilistic model formulation

Following the notation found in [6], we can rewrite equation 1 using exponential terms, as referring to Gibbs distribution:

∝),...,,,...,( 11 NN yyxxP

∏ ∏ −−r qp V

qp

D

rr xxVyxD

,2

2

2

2)

2

),(exp()

2),(exp(

σσ,

where: σV and σD are two parameters for tuning Gaussian distributions, D is a data term linked to luminance difference and V is a potential function.

The energy function D(xr,yr) is the term corresponding to the matching cost described in the previous section and its mathematical definition is:

||

|)()(|),( )(

N

nInIyxD rNn RL

rr∑ ∈

−= ,

where N(p) is a neighborhood of pixel p (a 3×3 mask in our implementation), | N | is its cardinality.

With regard to the potential function V(xp,xq), we define it as:

=),;,( qp xxqpV

)],(),([),( qpConqpSegxxG qp +∗ (2)

In the above formulation, new terms appear. Function G(xp, xq) is defined with respect to the image gradient, as described in [16], which we found as the most effective in our tests. Its mathematical expression is the following:

||),( qpsqp xxxxG −∗= ρ ,

norms δρ −=1 , (3) where δnorm.is the luminance difference between neighboring pixels, normalized in the interval [0,1] and then subtracted to the mean value over the whole


image. In this manner, we assume that depth (color) luminance discontinuities are likely indicative of object boundaries. Therefore, smoothness cost should decrease in those regions. This formulation differs from those provided by Potts model [2], because here is defined a non-constant penalization factor.

In our preliminary tests we have set σV = min {ρs} * max {| xp − xq |} ≈ min {ρs} (considering that for most natural scenes disparity gradient | xp − xq | between correct matches is usually < 1, as demonstrated in [10], then we have set max {| xp − xq | ≈ 1) and σD = 8 (we have fixed a suitable threshold on D(xr,yr) of 24 and σD

is the solution of equation: 01.0224exp 2

2=

−

Dσ). We

think this is not the better way of setting these parameters and in the future we will go better inside this question.

The other two terms in equation 2 provide a mathematical expression for a segmentation and a continuity constraint. The first one is defined as follows:

=,,0

),(s

qpSeg if

otherwise

qSpS )()( =

where S(p) represents a region deriving from a previous segmentation step: for each pixel belonging to the same segment, the term is constant, while we have a penalty s if two adjacent pixels come from different regions. We exploit this constraint under the assumption that, whether two neighboring pixels fall in the same region, they have to share a similar disparity too.

The other constraint is written as:

=,,0

),(c

qpCon if

otherwise

TqIpI LL <∇⋅∇ )()(

where )( pIL∇ is the gradient at pixel position p, T is a suitable continuity threshold and c a penalty value for those pixels that, though they are found on a boundary, their gradients exhibit different directions ( )()( qIpI LL ∇⋅∇ is a scalar product). The key idea for this constraint is that also disparity of points on an object boundary should be continuous.

At the moment our implementation is limited to considering only the smoothness constraint G in equation 3. However, our researches and tests are actively orienting in understanding how it is possible to combine Seg and Con functions in the more efficient manner. In particular, we will focus on how setting

parameters s, c and threshold T and their mutual effect on the effectiveness of the constraints.

2.3. Inference by belief propagation with single connected graphs

The major drawback in treating belief propagation algorithms is the presence of loops, leading to iterative schemes in which belief messages are repeatedly updated till either a convergence or a stop criterium is met. However, drawing a suitable message update step or providing those criteria is often a challenge. Moreover, there is no guarantee that beliefs could converge to the right joint probability. The approach described here, originally proposed in [7], overcomes these problems by allowing us to break up a MRF into a proper, equivalent set of Single Connected Graphs (SCG in the following). Some original extensions have been introduced in our work: first of all, we give a particular formulation of the algorithm in order to suit it to the stereo matching problem.

A SCG is a tree. There are two main reasons to resort to trees: first of all, a sake of simplicity - message computations stop at the leaves -, and next, precision in calculations, because it has been shown in [7] that, given a node xij , its belief b(xij) equals to the marginal probabilities pi(xi) of the node itself. In figure 1(a), a typical MRF is drawn and in figure 1(b), an example of (horizontal) SCG built from the original graph is depicted. SCG main properties are: (1) the radix is one of the pixel in the original MRF; (2) the radix is connected only to its adjacent pixels; (3) each other node is linked to its left and right adjacents and, if and only if it lays in the same column of the radix, to its above and below ones too; (4) each node of the original MRF is reachable from the radix. Each pixel in the MRF is in turn a radix of a tree: all those trees form the forest approximating the MRF.

The updating belief message step follows the same rules given in [7]. Figure 1(b) shows how it works. Messages flow across horizontal and vertical connections towards the radix, where they are collected and beliefs are computed. Messages can run across the SCG according to right-, left-, up- and down-going directions. This scheme allows us to simulate loops in the original graph: so, each node has a full knowledge of the local informations of its neighborhood and then, its computations should be more accurate. Since all the considered SCGs show a common shape, we exploit that fact to devise an efficient message passing scheme. Four different iterations are needed for each pixel to compute its belief. So, a message passing iteration from the leftmost column to the rightmost one is followed by one in the opposite way, which in turn is followed by an iteration from the top row to the last


one and that from the bottom row to the top. In such iterations, each node receive from either its left- or right or up- or down most neighbor a message, it processes it, it updates its inner state accordingly and then propagates it to its closest neighbor. Once those iterations are ended up, beliefs are computed.

We introduce with respect to the original proposal a couple of remarkable improvements. The first one directly involves iterations and their mutual relationships. During its different visits, each pixel receives a message: if its computation takes into account some of the previous arrived messages - as in the original proposal -, we say the iterations are dependent, otherwise they are independent (as in our proposal). In the latter case, a node puts informations together according to some rule. In our tests, we used to multiply messages and this scheme seems to work better than any other.

(a) (b)

Figure 1. a) A MRF and b) its approximation by a horizontal graph. In the MRF black nodes are called observable nodes, while white ones represent the random variables expressing disparities of our model. In b) is shown a typical horizontal graph, where the black node represents the pixel generating it.

The second change we have introduced is about

message propagation, which is driven by segmentation and boundary informations. Namely, we have embedded a segmentation algorithm (i.e. [5]) and a contour operator (Sobel in our implementation). Their introduction is due to the following key idea: discontinuities between objects are likely to introduce a different statistical behavior in messages. Indeed, the information carried by those messages can differ because of luminance changes, occlusions, difference in texture and so on. So, it is desirable that messages too should reflect the new situation about the underlying scene structure. That is why, we propose a scheme in which we reset messages as soon as a segment or an object boundary is detected. We take into account both segmentation and boundary information for a sake of consistency and robustness of the entire process.

We show in the following the right going updating scheme as a typical example of our iteration. m(xij) and

b(xij) are respectively the current message and the current belief for node xij:

1. Initialize: )),(),((max)( 10001

0iiii

xi xxyxxm

i

ψφ ∗=Λ∈

),()( 000 iii yxxb φ=

2. for all the pixels in the image: (a) if a new segment or a boundary is detected:

)),(),((max)( 1−

Λ∈∗= ijijijij

xij xxyxxm

ij

ψφ

(b) update belief: )(),()( ijijijij xmyxxb ∗= φ (4) or: )()()( ijijij xmxbxb ∗= (5)

(Equation 4 and 5 refer to, respectively, independent and dependent iterations.) (c) update the next message: ∗∗= +

Λ∈+ ),(),((max)( 11 ijijijij

xij xxyxxm

ij

ψφ

))(),( 1 ijijij xmxxG ∗+ ,

where G is introduced in our implementation to strengthen smoothness constraint.

3. Results Our work has been tested on both synthetic and benchmark images available online at the Middlesbury College http://cat.middlebury.edu/stereo/ data.html.

Even if these results are to be considered as preliminary at the moment, they however show the effectiveness of our proposal and come up to our expectations. However, further refinements have to be added up to our implementation in order to improve stereo matching task.

Figure 2 shows the synthetic stereo pair used in our tests. In particular, figures 2(a) and 2(b) represent respectively the left (reference) and the right images of the input stereo pair, while figure 2(c) is the final computed disparity map. The two images have an


horizontal shift of 5 pixels and the true disparity is correctly retrieved by our algorithm. This kind of tests are useful to verify, at least for an ideal and very simple case, the goodness of our method.

(a) (b) (c)

Figure 2. a),b) Synthetic stereo pair and c) the resulting disparity map.

First of all we have tested the original SCG optimization scheme, as proposed in [7]. Results, as depicted in figure 3, are very poor, confirming our hypothesis on the limits of such procedure.

(a) (b) Figure 3. a) The final disparity map using our stereo model with the original SCG optimization scheme [7] on Tsukuba database; b) true disparity map.

The most interesting results however come when

running our algorithm on some benchmark images, such as on the Tsukuba set. For example, figure 4(a) shows the reference image of the stereo pair. We provide here also the boundary for the left image (figure 4(b)), our implementation of the smoothness constraint as described in equation 3 (figure 4(c)), the original segmented image (figure 4(d)).

Some preliminary results are then shown. We have computed the final disparity maps (figure 5) letting the “passing” message scheme be independent from each direction (from left-to-right and right-to-left): a different map is produced for each direction and then all of them are merged together. There are two ways for obtaining the final disparity map: using a max belief (maximum of probability between partial disparity maps) and a max product of beliefs (disparity assigned to each pixel maximizes the product of all probabilities for each possible disparity and propagation direction).

The results of figure 5 shows the behavior of our algorithm without (figures 5(a),(b)) and with (figures 5(c),(d)) the smoothness constraint of equation 3. The improvement of figure 5(d) is clearly visible.

Some interesting indication can be outlined here. Our method is able to capture objects boundary, by properly retrieving disparity discontinuities, and small details on the scene (look at the lamp in figure 5 (d), for instance). However, it is not so accurate in textureless regions and on the background. Somewhere disparities form some unwanted stripe along the image: we think this effect is due to occluded pixels, which we have to take into consideration for subsequent updates of our work. 4. Conclusions and future work

In this paper we have proposed a new disparity model and a new Belief Propagation approach to the stereo matching problem.

We define a new visual constrain and embed it in a Markov Random Field without loops, by introducing a proper set of single connected graphs. In that way, we introduce less complexity in the problem treatment and, at the same time, precision and effectiveness are guaranteed.

Then, belief message computation is driven by constraints regarding and combining luminance difference measures and, more important, knowledge coming from a segmentation and a boundary extraction step. Moreover, the latter two are directly involved into the passing message scheme: it means messages can quickly fit themselves to the underlying scene as soon as a new object is detected. Then, as a general result, we have at our disposal a better disparity map.

Some of the temporary results we have collected till now are then shown and discussed.

We want to point out here this is a still going-on work. This means that, even if the theoretical part is fully provided, the implementation still suffers some lack. In particular, we have only provided the horizontal message passing scheme: the vertical one is not ready. We can actually think that introducing that part should increase the general performance of our algorithm, because it could caught vertical, spatial consistency too. Refinement of some of the discussed constraints is on our agenda, looking especially out to region and boundary knowledge. Moreover, constraints about occlusions and disparity monotonic growth in a region have to be added up to this framework as well. References [1] M. Bleyer and M. Gelautz. Graph-based surface reconstruction from stereo pairs using image segmentation.


In Proceedings of SPIE, Videometrics VIII, volume 5665, pages 288–299, January 2005. [2] Y. Boykov, O. Veksler, and R. Zabih. Markov random fields with efficient approximations. In CVPR ’98: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 648–655, Washington, DC, USA, 1998. IEEE Computer Society. [3] A. Criminisi, A. Blake, C. Rother, J. Shotton, and P. Torr. Efficient dense stereo with occlusions for new view-synthesis by four-state dynamic programming. International Journal of Computer Vision, 71(1):89–110, 2007. [4] U. Dhond and J. Aggarwal. Structure from stereo: A review. IEEE Transactions on Systems, Man and Cybernetics, 19(6):1489–1510, November 1989. [5] P. Felzenszwalb and D. Huttenlocher. Efficient graph-based image segmentation. International Journal of Computer Vision, 59(2):167–181, 2004. [6] S. Geman and D. Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. PAMI, 6(6):721–741, November 1984. [7] K. Ju Liu. A Trainable Graph Combination Scheme for Belief Propagation. PhD thesis, New York University, Department of Mathematics, January 2006. [8] V. Kolmogorov and R. Zabih. What energy functions can be minimized via graph cuts? In ECCV ’02: Proceedings of the 7th European Conference on Computer Vision-Part III, pages 65–81, London, UK, 2002. Springer-Verlag. [9] Y. Ma, S. Soatto, J. Kosecka, and S. Sastry. An Invitation to 3-D Vision: From Images to Geometric Models. Springer- Verlag, New York, Inc, 2004. [10] J. Mayhew and J. Frisby. Psychophisical and computational studies towards a theory of human stereopsis. Artificial Intell., 17:349–385, 1981.

[11] H. Moravec. Towards automatic visual obstacle avoidance. In Proceedings of the 5th International Joint Conference on Artificial Intelligence, page 584, August 1977. [12] P. Pèrez. Markov random fields and images. CWI Quarterly, 11(4):413–437, 1998. [13] D. Scharstein and R. Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision, 47(1-3):7–42, 2002. [14] J. Sun, N. Zheng, and H. Shum. Stereo matching using belief propagation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(7):787–800, 2003. [15] M. Tappen and W. Freeman. Comparison of graph cuts with belief propagation for stereo, using identical mrf parameters. In ICCV ’03: Proceedings of the Ninth IEEE International Conference on Computer Vision, pages 900–907, Washington, DC, USA, 2003. IEEE Computer Society. [16] Q. Yang, L. Wang, R. Yang, H. Stewenius, and D. Nister. Stereo matching with color-weighted correlation, hierachical belief propagation and occlusion handling. In CVPR ’06: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 2347–2354, Washington, DC, USA, 2006. IEEE Computer Society. [17] C. Zitnick and T. Kanade. A cooperative algorithm for stereo matching and occlusion detection. In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 22, pages 675–684, 2000.

(a) (b) (c) (d)

Figure 4. The input to our algorithm: a) the reference (Tsukuba) image of the stereo pair; b) extracted contours, c) the ρs of the smoothness constraint of equation 3 and d) the segmented image.

(a) (b) (c) (d)

Figure 5. The final disparity maps using our stereo algorithm on Tsukuba database, after independent passages of message from left to right and from right to left: a) using max belief and b) max product of belief without smoothness constraint; c) using max belief and d) max product of belief with smoothing constraint.


[IEEE 14th International Conference on Image Analysis and Processing (ICIAP 2007) - Modena, Italy...

Documents

Transcript of [IEEE 14th International Conference on Image Analysis and Processing (ICIAP 2007) - Modena, Italy...