{'fraction_non_alphanumeric': 0.034334677010958735, 'fraction_numerical': 0.01571900257256872, 'mean_word_length': 4.665366077576314, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 8, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Combining Stereovision Matching Constraints for Solving the Correspondence Problem

A major portion of the research efforts of the computer vision community has been directed toward the study of the three-dimensional (3-D) structure of objects using machine analysis of images (Scharstein & Szeliski, 2002). We can view the problem of stereo analysis as consisting of the following steps: image acquisition, camera modelling, feature acquisition, image matching, depth determination and interpolation. The key step is that of image matching, that is, the process of identifying the corresponding points in two images that are cast by the same physical point in 3-D space (Barnard & Fishler, 1982). This chapter is devoted solely to this problem. A correspondence needs to be established between features from two images that correspond to some physical feature in space. Then, provided that the position of centres of projection, the focal length, the orientation of the optical axes, and the sampling interval of each camera are known, the depth can be established by triangulation. The stereo correspondence problem can be defined in terms of finding pairs of true matches, namely, pairs of features in two images that are generated by the same physical entity in space. These true matches generally satisfy some constraints (Tang et al., 2002): 1. Epipolar, given two features, one in an image and a second in the other one in the stereoscopic pair, if we follow a given line, established by the system geometry, these two features must lie on this line, which is the epipolar. 2. Similarity, matched features have similar local properties or attributes. 3. Smoothness, disparity values in a given neighbourhood change smoothly, except at a few depth discontinuities. 4. Ordering, the relative position among two features in an image is preserved in the other one for the corresponding matches. 5. Uniqueness, each feature in one image should be matched to a unique feature in the other image. A review of the state-of-art in stereovision matching allows us to distinguish two sorts of techniques broadly used in this discipline: area-based and feature-based. Area-based stereo techniques use correlation between brightness (intensity) patterns in the local neighbourhood of a pixel in one image with brightness patterns in the local neighbourhood of the other image (Scharstein & Szeliski, 2002; Herrera et al., 2009a,b,c; Herrera, 2010; Klaus et al., 2006). Feature-based methods use sets of pixels with similar attributes, normally, either pixels belonging to edges (Grimson, 1985; Ruichek & Postaire, 1996; Tang et al., 2002),

the corresponding edges themselves (Medioni & Nevatia, 1985;Pajares & Cruz, 2006;Ruichek et al., 2007;Scaramuzza et al., 2008), regions (Marapane & Trivedi, 1989;Lopez-Malo & Pla, 2000;McKinnon & Baltes, 2004;Herrera et al., 2009d;Herrera, 2010) or hierarchical approaches (Wei & Quan, 2004) where firstly edges or corners are matched and afterwards the regions. The stereovision system geometry is another issue concerning the application of methods and constraints. Conventional stereovision systems consist of two cameras under perspective projection with the optical axes in parallel (Scharstein & Szeliski, 2002) or in convergence (Krotkov, 1990); they have a limited field of view. In opposite, the omnidirectional stereovision systems allow enhancing the field of view, under this category fall the systems in which the optics and consequently the image projection is based on fish-eye lenses (Abraham & Förstner, 2005;Schwalbe, 2005;Herrera et al., 2009a,b,c,d;Herrera, 2010). Depending on the application for which the stereovision system is to be designed one must choose either area-based or feature-based, the system geometry and also the strategy for combining the different constraints. In this chapter we focus the attention on the combination of the matching constraints. As features we use area-based when the pixels are the basic elements to be matched and also feature-based with straight line segments and regions. Moreover, both area-based and feature-based are used in conventional and omnidirectional stereovision systems with parallel optical axes. The main contribution of this work is the design of a general scheme with three approaches for combining the matching constraints. The aim is to solve different stereovision correspondence problems. The chapter is organised as follows. In section 2 we give details about the three approaches for combining the matching constraints. In sections 3, 4 and 5 these approaches are explained giving details about their application with different features and optical projections. Finally, in section 6 some conclusions are provided.

Matching constraints combination
The matching constraints can be combined under different strategies, figure 1 displays a tree with three branches (A,B and C). Each branch represents a path where the matching constraints are applied in a different way. As one can see, given a pair of stereoscopic images the epipolar and similarity constraints are always applied and then depending on some factors, explained below, one can choose one of the three alternatives, i.e. branch A, B or C. All paths end with the computation of a disparity map, in the path A this map is a refined version of the one previously obtained after the application of the smoothness constraint. This combination is more suitable if an area-based strategy is being used because pixels are the most flexible features for smoothness. Nevertheless, following the path A, we could use feature-based approaches, such as edge-segments or regions, for computing the first disparity map. On the contrary, branch B is more suitable when regions are used as features because it does not include the smoothness constraint. Indeed, this constraint assumes similar disparities for entities which are spatially near among them, but the regions could belong to different objects in the scene and these objects do not necessarily present similar disparities. Finally, branch C could be considered as a mixed approach where area-based or feature-based could be used, although in this last case perhaps excluding regions. The system's geometry which is determinant for defining the epipolar constraint does not affect the choice of a given branch.
In summary, following the branch A in section 3, we describe a first procedure based on edgesegments as features under a conventional stereovision system and compute the first disparity map. A second procedure is described for an omni-directional stereovision system under an area-based approach (pixels) where a refined disparity map is finally obtained. Following the branch B, section 4, we describe a procedure for matching regions as features from an omnidirectional stereovision system. Finally, following the branch C, section 5, the procedure described uses again edge-segments as features in a conventional stereovision system.

Branch A: edge-segment based and pixel-based approaches
As mentioned before, under the combination scheme displayed in branch A, we describe two procedures for computing the disparity map. The first is based on edge-segments as features under a conventional stereovision system with parallel optical axes, where only the first disparity map is obtained. The second uses pixels as features under a fish-eye lens based optical system, also with parallel optical axes, where the first map is later filtered and refined by removing errors and spurious disparity values.

Edge-segments as features: conventional stereovision systems
Under this approach the stereo matching system is designed with a parallel optical axis geometry working in the following three stages: 1. Extracting edge-segments and their attributes from the images; 2. Performing a training process, with the samples (true and false matches) which are supplied to a classifier based on the Support Vector Machines (SVM) framework, where an output function is estimated through a set of attributes extracted from the edgesegments; 3. Performing a matching process for each new incoming pair of features. According to the value of the estimated output function provide d by the SVM, each p air of e dgesegments is classified as a true or false match. The first segmentation stage is common for both training and matching processes. This scheme follows the well-known SVM learning based strategy. It has been described in Pajares & Cruz (2003). Other learning-based methods with a similar approach, but different learning strategies can be found in Pajares & Cruz (2002) which applies the Parzen´s window, Pajares & Cruz (2001) which uses the ADALINE neural network,  based on a fuzzy clustering strategy, Pajares & Cruz (1999) where the Hebbian learning is applied and the Self-organizing framework in Pajares et al. (1998a). Figure 2 dispalys a mapping of edge segments (u,v,h,i,c,z,k,j,s,q) as features for matching under a conventional stereovision system with parallel optical axes and the cameras horizontally aligned. With this geometry, the epipolar lines are horizontal crossing the left (LI) and right (RI) images. This figure contains details about the overlapping concept firstly introduced in Medioni & Nevatia (1985). Two segments, one in LI and the second in RI, overlap if by sliding one of them following the epipolar line they intersect. By example, u overlaps with c, z, s and q, but segment v does not overlap with s. Moreover, Figure 2 contains two windows, w(i) and w(j) for applying a neighbourhood criterion, described in section 5.2.1, for mapping the smootheness constraint. Left (LI) and right (RI) images based on a conventional stereovision system with parallel optical axes geometry and perspective projection with edge-segments as features.

Feature and attribute extraction
This is the first stage of the proposed approach. The contour edge pixels in both images are extracted using the Laplacian of the Gaussian filter in accordance with the zero-crossing criterion (Huertas & Medioni, 1986). At each zero-crossing in a given image we compute the magnitude and the direction of the gradient vector as in Leu and Yau (1991), the Laplacian as in Lew et al. (1994) and the variance as in Krotkov (1989). These four attributes are computed from the gray levels of a central pixel and its eight immediate neighbors. The gradient magnitude is obtained by taking the largest difference in gray levels of two opposite pixels in the corresponding eight-neighbourhood of a central pixel. The gradient direction points from the central pixel towards the pixel with the maximum absolute value of the two opposite pixels with the largest difference. It is measured in degrees, quantified by multiples of 45. The normalization of the gradient direction is achieved by assigning a www.intechopen.com digit from 0 to 7 to each principal direction. The Laplacian is computed by using the corresponding Laplacian operator over the eight neighbors of the central pixel. The variance indicates the dispersion of the nine gray level values in the eight-neighborhood of the same central pixel. In order to avoid noise effects during edge-detection that can lead to later mismatches in realistic images, the following two globally consistent methods are used: 1) the edges are obtained by joining adjacent zero-crossings following the algorithm in Tanaka & Kak (1990), in which a margin of deviation of ± 20% and ±45° is tolerated in magnitude and direction respectively; 2) then each detected contour is approximated by a series of line segments as in Nevatia & Babu (1980); finally, for each segment an average value for the four attributes is obtained from all computed values of its zero-crossings. All average attribute values are scaled, so that they fall within the same range. Each segment is identified by its initial and final pixel coordinates, its length and its label. Therefore, each stereo-pair of edge-segments has two associated four-dimensional vectors x l and x r , where the components are the attribute values and the sub-indices l and r denote features belonging to the left and right images respectively. A four-dimensional difference vector of the attributes x = {x m , x d , x p , x v } is obtained from x l and x r , whose components are the corresponding differences for the module of the gradient vector, the direction of the gradient vector, the Laplacian and the variance respectively.

Training process: the support vector machines classifier
The SVM classifier is based on the observation of a set X of n pattern samples to classify them as true or false matches, i.e. the stereovision matching is mapped as the well-known two classification problem. The outputs of the system are two symbolic values y ∈ {+1,-1} corresponding each to one of the classes. So, y = +1 and y = -1 are with the class of true and false matches respectively.
The finite sample (training) set is denoted by: ( ) i y ∈+ − the class it belongs to. In our problem x i is as before the 4-dimensional difference vector. The goal of SVM is to find, from the information stored in the training sample set, a decision function capable of separating the data into two groups. The technique is based on the idea of mapping the input vectors into a high-dimensional feature space using nonlinear transformation functions. In the feature space a separating hyperplane (a linear function of the attribute variables) is constructed (Vapnik 2000;Cherkassky & Mulier 1998). The SVM decision function has the following general form The equation (1)  , the inner product kernel H, and the regularization parameter c. As stated in Cherkassky & Mulier (1998), at present, there is not a well-developed theory on how to select the best c, although in several applications it is set to a large fixed constant value, such as 2000, which is used in Pajares & Cruz (2003).
The data points x i associated with the nonzero α i are called support vectors. Once the support vectors have been determined, the SVM decision function has the form, support vectors (, )

Matching process: epipolar, similarity and uniqueness constraints
Now, given a new pair of edge-segments the goal is to determine if they represent a true or false match. Only those pairs fulfilling the overlapping concept, section 3.1, are considered. This represents the mapping of the epipolar constraint. The pair of segments is represented by its attribute vector x, therefore through the function estimated in equation (3), we compute the scalar output f(x) whose polarity, sign of f(x), determines the class membership, i.e. if x represents a true or false match for the incoming pair of edge segments. This is the mapping of the similarity constraint. During the decision process there are unambiguous and ambiguous pairs of features, depending on whether a given left image segment corresponds to one and only one, or several right image segments, respectively based only on the polarity of f(x). In any case, the decision about the correct match is made by choosing the pair with the greater magnitude f(x) when ambiguity. Because, f(x) ranges in [-1, +1] we only consider pairs with a certain guarantee of correspondence, this means that only pairs with positive values of f(x) are potential candidates. Therefore, the uniqueness constraint is formulated based on the following decision rule: if the sign of f(x) is positive and its value is the greatest among the ambiguous pairs, it is chosen as a correct match, otherwise it is a false correspondence. Figure 3 displays a pair of stereo images, which is a representative pair of the 70 pairs used for testing in Pajares & Cruz (2003), where (a) and (b) are respectively the left and right www.intechopen.com images of the stereo pair. In (c) and (d) are represented the edge segments extracted following the procedure described in section 3.1.1. Details about the experiments are provided in Pajares & Cruz (2003), where on average the percentage of successes overpasses the 94%. The matching between these edge segments determines the disparity map, as one can see this map is sparse because only edges are considered.

Pixels as features: fish-eye based systems
Following the branch A, Figure 1, we again combine the epipolar, similarity and uniqueness constraints obtaining a first disparity map. The difference with respect the method described in section 3.1 is twofold: (a) here the pixels are used as features, instead of edge segments; (b) the disparity map is later refined by applying the smoothness constraint. Additionally, the stereovision is based on cameras equipped with fish eye lenses. This affects mainly the epipolar constraint, which is considered in section 3.2.1. Following the full branch in figure 1, we give details about how the stereovision matching constraints are applied under this approach. This method is described in Herrera (2010). Figure 4 displays a pair of stereovision images captured with fish eye lenses. The method proposed here is based on the work of Herrera et al. (2009a) and was intended as a previous stage for forest inventories, where the estimation of wood or the growth are some of the inventory variables to be computed.  Figure 5 displays the stereo vision system geometry (Abraham & Förstner, 2005). The 3D object point P with world coordinates with respect to the systems (X 1 , Y 1 , Z 1 ) and (X 2 , Y 2 , Z 2 ) is imaged as (x i1 , y i1 ) and (x i2 , y i2 ) in image-1 (left) and image-2 (right) respectively in coordinates of the image system; a 1 and a 2 are the angles of incidence of the rays from P; y 12 is the baseline measuring the distance between the optical axes in both cameras along the yaxes; r is the distance between an image point and the optical axis; R is the image radius, identical in both images. According to Schwalbe (2005), the following geometrical relations can be established,

Epipolar constraint: system geometry
Now the problem is that the 3D world coordinates (X 1 , Y 1 , Z 1 ) are unknown. They can be estimated by varying the distance d as follows, 1 cos ; Xd β = 1 sin ; Yd From (4) we transform the world coordinates in the system O 1 X 1 Y 1 Z 1 to the world coordinates in the system O 2 X 2 Y 2 Z 2 taking into account the baseline as follows, Assuming no lenses radial distortion, we can find the imaged coordinates of the 3D point in image-2 as in Schwalbe (2005), Because of the system geometry, the epipolar lines are not concentric circumferences and this fact is considered for matching. Figure 6 displays four epipolar lines, in the third quadrant of the right image, they have been generated by the four pixels located at the positions marked with the squares, which are their equivalent locations in the left image. Fig. 5. Geometric projections and relations for the fish-eye based stereo vision system.
Using only a camera, we capture a unique image and each 3D point belonging to the line 1 OP, is imaged in 11 (,) ii xy . So, the 3D coordinates with a unique camera cannot be obtained. When we try to match the imaged point represented by 22 (,) ii xy in the image-2. The best match is associated to a distance d for the 3D point in the scene, which is computed from the stereo vision system. Hence, for each d we obtain a specific 22 (,) ii xy , so that when it is matched with 11 (,) ii xy d is the distance for the point P. Different measures of distances during different time intervals (years) for specific points in the trunks, such as the ends or the width of the trunk measured at the same height, allow determining the evolution of the tree and consequently its state of growth and also the volume of wood, which are as mentioned before inventory variables. This requires that the stereovision system is placed at the same position in the 3D scene and also with the same camera orientation (left camera North and right camera South).

Similarity constraint: attributes or properties
Each pixel l in the left image is characterized by its attributes; one of such attributes is denoted as A l . In the same way, each candidate i in the list of m candidates is described by identical attributes, A i . So, we can compute differences between attributes of the same type A, obtaining a similarity measure for each one as follows, the difference between attributes is large enough (minimum similarity), otherwise if they are equal, 1 iA s = and maximum similarity is obtained. We use the following six attributes for describing each pixel: a) correlation; b) texture; c) colour; d) gradient magnitude; e) gradient direction and f) Laplacian. Both first ones are area-based computed on a 3 3 × neighbourhood around each pixel through the correlation coefficient (Barnea & Silverman, 1972 ;Koschan & Abidi, 2008;Klaus et al., 2006) and standard deviation (Pajares & Cruz, 2007) respectively. The four remaining ones are considered as feature-based (Lew et al., 1994). The colour involves the three red-green-blue spectral components (R,G,B) and the absolute value in the equation (8) is extended as the sum of absolute differences as , It is a similarity measurement for colour images (Koschan & Abidi, 2008), used satisfactorily in Klaus et al. (2006) for stereovision matching. Gradient (magnitude and direction) and Laplacian are computed by applying the first and second derivatives respectively (Pajares & Cruz, 2007) over the intensity image after its transformation from the RGB plane to the HSI (hue, saturation, intensity) one. The gradient magnitude has been used in Lew et al. (1994) and Klaus et al. (2006) and the direction in Lew et al. (1994). Both, colour and gradient magnitude have been linearly combined in Klaus et al. (2006) producing satisfactory results as compared with the Middlebury test bed (Scharstein & Szeliski, 2002). The coefficients www.intechopen.com involved in the linear combination are computed by testing reliable correspondences in a set of experiments carried out during a previous stage. Given a pixel in the left image and the set of m candidates in the right one, we compute the following similarity measures for each attribute A: s ia (correlation), s ib (colour), s ic (texture), s id (gradient magnitude), s ie (gradient direction) and s if (Laplacian). The identifiers in the sub-indices identify the attributes according to these assignments. The attributes are the six ones described above, i.e.

Uniqueness constraint: Dempster-Shafer theory
Based on the conclusions reported in Klaus et al. (2006), the combination of attributes appears as a suitable approach. The Dempster-Shafer theory owes its name to the works by the both authors in Dempster (1968) and Shafer (1976) and can cope specifically with the combination of attributes because they are specifically designed for classifier combination Kuncheva (2004). With a little adjusting they can be used for combining attributes in stereovision matching. They allow making a decision about a unique candidate (uniqueness constraint). Now we must match each pixel l in the left image with the best of the m potential candidates. The Dempster-Shafer theory as it is applied in our stereovision matching approach is as follows (Kuncheva, 2004): 1. A pixel l is to be matched either correctly or incorrectly. Hence, we identify two classes, which are the class of true matches, w 1, and the class of false matches, w 2 . Given a set of samples from both classes, we compute the similarities of the matches belonging to each class according to (8) 3. For every class w j and for every candidate i, we calculate the belief degrees, 4. The final degree of support that candidate i, represented by i x , receives for each class w j taking into account that its match is l is given in equation (11) www.intechopen.com 5. We chose as the best match for l, the candidate i with the maximum support received for the class of true matches (w 1 ), i.e.
( ) { } 1 max i i μ x but only if it is greater than a threshold, which can be fixed to 0.5, as in Herrera et al. (2009a). Other approaches based on the combination of attributes have been applied in Herrera et al., (2009b,c) where the Choquet, Sugeno and a Fuzzy multicriteria decision making methods are respectively used for applying the uniqueness constraint.

Smoothness constraint: mean filtering
We have available a first disparity map after applying the above three constraints: epipolar, similarity and uniqueness. The disparity map contains pixels which have been erroneously classified either as true or false matches. Based on the obvious assumption that the structures in the 3-D scene are spatially preserved in the 2-D images we consider that if a pixel with a disparity value different from those values on its neighbourhood, such value must be changed toward the disparities of the pixels which are surrounding it. This is an obvious interpretation of the smoothness constraint. Indeed, if a point and its neighbours belong to a region in the 3-D space, all are probably placed at a given distance from the stereovision system, this spatial region is mapped as a 2-D region in the images and the disparities still preserve similar values. A simple statistical averaging filter has the ability for changing erroneous or spurious disparity values of a pixel with respect its neighbours. This technique is used in Lankton (2010) which implements the method described in Klaus et al. (2006). Other statistical filters could be used such as the median or the mode. In Herrera (2010) is reported that the errors obtained without smoothing are about the 11% and after the filtering the error decreases until the 8% on average. Figure 7 displays the disparity maps obtained without and with smoothing. The colour bar represents the disparity levels in sexagesimal degrees considering a circumference of 360º. The maximum disparity value found in the twenty pairs of stereovision images used is 8º, therefore the colour bar ranges from 0º to 8º.

Branch B: regions based
Now we describe the mapping of the matching constraints in the branch B, figure 1, i.e. epipolar, similarity, ordering and uniqueness. Under this feature-based approach, the features are regions. The stereovision system is also equipped with fish eye lenses obtaining omnidirectional images, as the ones in figure 4. Figure 8 displays a pair of such stereo images. As we can see, the images display similar geometry but different types of forest environments, i.e. pines and oaks respectively. The main goal on the images in figure 8 is the correspondence between the trunks of the trees for forest inventories because they concentrate the greatest volume of wood and determines the growth stage of the trees, which are important variables for inventories, as mentioned before. Therefore, this is a clear example where the type of scene is decisive for choosing one or another strategy. So, the strategy here differs from the one described in section 3.2, although the same final goal (inventories) is pursued. The trunks are the regions to be matched due to its appearance. Therefore, under this approach, an important issue concerning the stereovision matching is the regions segmentation, including the identification and extraction of properties, which are used for matching. In section 4.1 we describe the segmentation process and in section 4.2 the correspondence process, describing how the matching constraints are applied during the correspondence process. This procedure can be found exhaustively described in Herrera et al. (2009d).

Segmentation process
This process is focused on the isolation of the trunks. As we can see from figure 8, the trunks (dark) and the sky (clear) display high contrast in a broad area in the inner part of the image, but in the outer part they get confused with the grass in the soil. The procedure exploits the high contrast and takes into account the last observation. By applying the following steps in a sequential order the trunks are conveniently extrated: 1. Valid image: the central part of the image is the one to be processed, the Charge Coupled Device of the cameras has 1616 × 1616 pixels in width and height dimensions respectively. The centre is located in the coordinates (808, 808). The radius R of the valid image is 808 pixels. 2. Detecting thin branches: thin branches are not significant for forest inventories, but they are highly harmful from the point of view of segmentation; this is because most of these thin branches belonging to different trees appear overlapped among them. With such purpose we compute the standard deviation at pixel-level (Pajares & Cruz, 2007) with a www.intechopen.com window of size 5x5. Considering this window, a pixel belonging to a thin branch fullfills the following conditions: a) displays a low intensity value, as it belongs to the tree; b) must be surrounded by pixels with high intensity values, belonging to the sky, this means that in the window appear pixels of this class at least in two opposite sides, i.e. left and right or up and bottom; c) the standard deviation computed through this window is greater than a threshold set to a value of twenty five in our experiments after several trial and error tests, which verifies the high variability in the contrast. 3. Concentric circumferences: we draw concentric circumferences starting with a radius r of 250 pixels from the centre, with increases of 50 pixels until r = R. We trace the intensity profile for each circunference until a profile displays large dark areas. This means that we have already reached the area where the trunks and soil get confused. The other circunferences display alternative dark and clear levels, these last circumferences are identified as type 1 and the remainder ones as type 2. 4. Putting seeds in the trunks: given a profile of type 1, we consider a pixel in each dark region as a seed and compute the average intensity value and standard deviation of the dark region associated to the seed. Only dark regions with more than T 1 =10 pixels in the profile and with intensity values below T 2 =75 are retained. Considering the outer circumference of type 1, identified as c i we select only dark regions whose intersection with this circumference gives a line with a number of pixels lower than T 3 =120. The maximum value of all lines of intersection is max 3 .
i tT < Then for the next circumference towards the centre of the image, c i+1, 3 T is now set to max i t , which is the value used when the next circumference is processed and so on until the inner circumference of type 1 is reached. This is justified because the thickness of the trunks always diminishes towards the centre. 5. Region growing: this process is based on the procedure described in Gonzalez & Woods (2008), we start in the outer circumference of type 1 by selecting the seed pixels obtained in this circumference. From these seed points we append to each seed those neighbouring pixels that have a similar intensity value than the seed. The similarity is measured as the difference between the intensity value of the pixel under consideration and the mean value in the zone where the seed belongs to, they do not differ more than the standard deviation for each zone. The region growing ends when no more similar neighbouring pixels are found for that seed between this circumference and the centre of the image. The regions obtained are labelled following the procedure described in Haralick & Shapiro (1992). 6. Estimation: for each labelled region we have available its orientation towards the centre of the image and also its decreasing ratio. This allows to estimate the part of the trunk confused with the soil. So, after this operation we obtain new enlarged regions representing the full trunks. These regions are finally re-labelled and for each region we extract the following attributes: area (number of pixels), centroid (xy-averaged pixel positions in the region), angles in degrees of each centroid and the seven Hu invariant moments (Pajares & Cruz, 2007;Gonzalez and Woods, 2008).

Matching process
Once the regions and their attributes are extracted according to the above procedure, we are ready to apply the stereovision matching constraints in figure 1, branch B, i.e. epipolar, similarity, ordering and uniqueness. www.intechopen.com

Epipolar constraint
As mentioned before, the images in figure 9 are captured with fish eye lenses, therefore the epipolar lines are defined according to equations (4) to (7). So, given a region in an image with its centroid, we search for its potential matched region following the epipolar lines and looking for regions whose centroids fall in or near the corresponding epipolar line generated by the first centroid in the other image of the stereoscopic pair. This idea is illustrated in figure 9, given a red square in the image (a), following the epipolar line towards the south direction we will find the corresponding matching, Figure 9(b). This implies that given a centroid of a region in the left image its corresponding matching in the right image will be probably in the epipolar line.
Because the sensor could introduce errors due to wrong calibration of the cameras, we have considered an offset out of the epipolar lines quantified as 10 pixels in distance. Moreover, in the epipolar line, the corresponding centroids are separated a certain angle, as we can see in Figure 9(b) expressed by the red and blue squares. After experimentation with the set of images tested, the maximum separation found in degrees has been quantified in 22º, i.e. this determines the limit on the disparity.
(a) (b) Fig. 9. Original stereo images captured with a fish eye lens in an outdoor forest environment.

Similarity constraint
All regions with centroids fulfilling the similarity constraint are considered as candidates for matching. We build a list of such candidate regions according to the similarities based on their areas and the seven Hu's invariant moments. So, we have eight similarity measurements, which are mapped to range in the interval [0,1]. The similarities are stablished as differences in the absolute value between attributes. All regions with a number of similarities greater than four and each one less than a threshold of 0.2, are considered as candidates for matching. This threshold is fixed to this relative low value in order to guarantee a strong similarity, taking into account that the most favourable value is zero and the most unfavourable is +1.

Ordering and uniqueness constraints
The ordering constraint assumes that the relative position between two regions in an image is preserved in the other one for the corresponding matches. The application of this constraint is limited to regions with similar heights and areas in the same image and also if the areas overpass a threshold T 4 set to 6400 in this work. This tries to avoid violations of this constraint based on closeness and remoteness relations of the trunks with respect the sensor in the 3D scene. If after applying the similarity constraint still remain ambiguities because different pairs of regions still involve the same region, the application of the ordering constraint could remove these possible ambiguities. This implies the implicit application of the uniqueness constraint. Nevertheless, if still ambiguities persist, we strictly select the most similar pairs in application of the similarity constraint until all ambiguities are resolved. Figure 10 displays the regions extracted by the segmentation process. Each region appears with a unique label. The number near of the regions identifies each label. This number is represented as a color in a scale ranging from 1 to 14, where 1 is blue and 14 orange. This representation is only for a best visualization of the regions. From Figure 10, we can see how the segmented regions come from the trunks in Figure 4, even trunks displaying small areas. The proposed approach over the set of 20 stereo pairs of images analyzed has achieved a performance of 88.4% of successes.

Branch C: edge segments based
This approach follows the branch C in figure 1, i. e. here epipolar, similarity, smoothness ordering and uniqueness are the constraints to be applied. The features are edge segments as the ones used in section 3.1. We extract these features and apply the two first constraints exactly as described in such section. The full procedure is described in Pajares & Cruz (2004). Other similar global stratetigies can be found in  where a Hopfield neural network is the chosen global matching approach selected or in Pajares et al., (1998b) where a relaxation approach is applied. Also global strategies are applied in Ishikawa & Geiger (2007) where an energy minimization is defined with such purpose or in Pajares & Cruz (2006), where the fuzzy cognitive map framework is the method selected for achieving the proposed globality.

Epipolar and similarity constraints
Consequently, after applying the training process described in section 3.1.2, we obtain the decision function in equation (3). Given a pair of stereo images as those displayed in figure 3(a) and (b) we obtain for each pair of edge segments the corresponding attribute difference vector, x , as described in section 3.1.1. Once this vector is computed, we could take a decision about tha matching of the pair of edge segments that it represents as in section www.intechopen.com 3.1.3. Nevertheless, in order to embed the similarity in the global matching process described later, we map the value provided by the decision function to range in the continuous interval [-1,+1] as a similarity measurement between features as follows, where, in order to avoid severe bias, the parameter a is estimated experimentally, verifying that a value of 0.2 suffices for the type of images analysed. Implicitly, at this stage we have already applied the epipolar and similarity constraints.

Simulated annealing: a global matching strategy
In order to formulate the Simulated Annealing (SA) we build a network of nodes, where each pair of edge-segments to be matched creates a node with its own state, which determines the strength of the correspondence. Through the equation (12), the nodes are loaded with an initial state, which is updated through the SA optimization process. The correspondences are established based on the final values of the states. The goal of the optimization process is to increase the consistency of a given pair of edge segments among three constraints (smoothness, ordering and epipolar) so that the state of a node representing a correct match can be increased and the state of any incorrect match can be decreased during the optimization process. Suppose the network with N nodes. The simulated annealing optimization problem is: modify the state values s ij so as to minimize the energy, = ) because the nonzero merely add an unimportant constant to E, independent of the s ij . The optimization task is to find the network with the most stable configuration, the one with lowest energy. The energy function is built so that it embeds three stereovision constraints: smoothness, ordering and epipolar, this last once again considered. Therefore, we look for a compatibility coefficient, which must be able to represent the consistency between the current pair of edge segments under correspondence and the pairs of edge segments in a given neighborhood. The compatibility coefficient makes global consistency between neighbors pairs of edge segments based on such constraints.

Mapping the smoothness constraint
The smoothness constraint assumes that neighboring edge segments have similar disparities, except at a few depth discontinuities (Medioni & Nevatia, 1985). Generally, when the smoothness constraint is applied, it is assumed there is a bound on the disparity range allowed for any given segment. We denote this limit as maxd, in the set of images tested, a value of 15 suffices, (see figure 2). According to the procedure described in Medioni & Nevatia (1985), for each edge segment "i" in the left image we define a window w(i) in the right image in which corresponding segments from the right image must lie and, similarly, for each segment "j" in the right image, we define a window w(j) in the left image in which corresponding edge segments from the left image must lie. It is said that "a segment h must lie" if at least the 30% of the length of the segment "h" is contained in the corresponding window. The shape of this window is a parallelogram, one side is "i", for left to right match, and the other a horizontal vector of length 2.maxd. The smoothness constraint implies that "i" in w(j) assumes "j" in w(i). Now, given "i" and "h" in w(j) and "j" and "k" in w(i) where "i" matches with "j" and "h" with "k" the differential disparity |d ij -d hk |, measures how close the disparity between edge segments "i" and "j" denoted as d ij is to the disparity d hk between edge segments "h" and "k". The disparity between edge segments is the average of the disparity between the two edge segments along the length they overlap. This differential disparity criterion is used in Medioni & Nevatia (1985), Ruichek & Postaire (1996), Pajares et al., (1998b, Pajares & Cruz (2004) or Nasrabadi & Choo (1992) among others. We define a compatibility coefficient derived from Ruichek & Postaire (1996) and Nasrabadi & Choo (1992) given by the following expression, Under this assumption and following Kim et al. (1997) and Kreszig (1983), to set the possibility value to 0.1 when the value of cumulative distribution function is 0.9, γ value is  1). This means that a compatibility coefficient of +1 is obtained for a good consistency between two nodes (i,j) and (h,k) (i.e. D = 0) and a compatibility of −1 for a bad consistency between these nodes (i.e. D>>0 ). The energy function embedding the smoothness constraint must be minimum when D = 0 (i.e. corresponding to a high compatibility coefficient value) and high states values. We define an energy function assuming the above as follows, where A is a positive constant to be defined later.

Mapping the ordering constraint
We define the ordering coefficient () ( ) ij hk O for the edge-segments according to (16), which measures the relative average position of edge segments "i" and "h" in the left image with respect to "j" and "k" in the right image, it ranges from 0 to 1.
We trace S scanlines (in our experiments four are sufficient) along the common overlapping length, each scanline produces a set of four intersection points (i S and h S in LI and j S and k S in the RI) with the four edge-segments. Hence, the lower-case o ijhk can be computed as in Ruichek & Postaire (1996) considering the above four edge points, and it takes 0 and 1 as two discrete values.  (17) where B is a positive constant to be defined later.

Mapping the epipolar constraint
Although this constraint has been applied previously during the matching based on the similarity, now it is again mapped under the global point of view based on the overlapping concept, section 3.1. Based on the Figure 2, the overlap rate between edge segments (u,z), a uz is defined as the percentage of coincidence, ranging in [0,1], when two segments u and z overlap, and it is computed taken into account the common overlap length l c defined by c and the two lengths for the involved edge segments l u and l z respectively. All lengths are measured in pixels.
Based on the overlapping concept, we compute the overlapping coefficient as follows, Under the epipolar constraint we can assume that correct matches should have high overlap rates and () ( ) ij hk λ for neighborhoods should be high, increasing the consistency. The overlapping criterion is justified by the fact that the edge segments are reconstructed by piecewise linear line segments as described in section 3.

Deterministic simulated annealing
The total energy function can be obtained as E = E s + E o + E e . By comparison of expressions (15), (17) and (20) and (13), by multiplying the constant term by -1, it is easy to derive the connection weights, where the delta function () ( ) 1 ij hk = for (i,j) = (h,k) and 0 otherwise. To ensure the convergence to stable state, symmetrical inter-connection weights and no self-feedback are required, i.e. we see that by setting A = B = C = 1 both conditions are fulfilled. The simulated annealing process, was originally developed in Kirkpatrick et al. (1983) and Kirkpatrick (1984), in this chapter we have implemented the approach described in Duda et al. (2001) and Haykin (1994). According to Duda et al. (2001), we have chosen deterministic simulated annealing because the stochastic one is slow. Nevertheless, the deterministic version has been faster than the stochastic, by exactly two orders of magnitude, this agrees with Duda et al. (2001). In the original SA algorithm, the forces exerted by the other nodes are summed to find an analogue value s ij without the intervention of the state of the node which is being updated. We modify this in order to include the contribution of its own state, so that the power of the similarity constraint is considered. The temperature (T) also plays a very important role in the optimization process.

t ,T t ) + s t -= tanh F t T t + s t -
where t represents the iteration index. The fraction (,) f ⋅ ⋅ depends upon the temperature. At high T, the value of (,) f ⋅ ⋅ is lower for a given value of the forces F. Details about the behavior of T are given in Duda et al. (2001). We have verified that this fraction must be small as compared to ( -1) ij st in order to avoid that the updating is controlled by this fraction exclusively and that the similarity constraint is cancelled. Under the above considerations and based on Starink & Backer (1995) and Hajek (1988), the following annealing schedule suffices to obtain a global minimum: ( ) () 0 Tt =T l o g t+1 , with T 0 being a sufficiently high initial temperature. We have computed 0 T as follows (Laarhoven & Aarts, 1989): 1) we select four stereo images, previously the Support Vector Machines has been trained and the support vectors obtained; now we compute the initial energy; 2) we choose an initial temperature that permits about 80% of all transitions to be accepted (i.e. transitions that decrease the energy function), and this value is changed until such percentage is achieved ; & Backer (1995) and Hajek (1988)). We have also verified that a value of t max = 100 suffices, www.intechopen.com although the expected condition () 0 , Tt t = →+∞ in the original algorithm is not fully fulfilled. But this last requirement and a possible overly rapid cooling only occur when simulated annealing is applied for achieving the solid thermal equilibrium but not in our approach in which there is not a solid. Moreover, the above cooling scheduling is justified by the fact that our initial state has reached a certain equilibrium as a result of the Support Vector Machines local matching process and it is unnecessary to heat at high temperature, hence we have a prior knowledge about the system before it is relaxed by SA.

Output: ij s updated
np is the number of nodes for which the matching states are modified by the updating procedure, N is the number of nodes, T(t) is the annealing schedule, ε is a constant to accelerate the convergence, set to 0.01.

Mapping the uniqueness constraint
This stage represents the mapping of the uniqueness constraint, which completes the set of matching constraints used for solving our stereovision matching problem. A left edge segment can be assigned to a unique right edge segment (unambiguous pair) or several right edge segments (ambiguous pairs). The decision about whether a match is correct is made by choosing the greater state value in the network of nodes (in the unambiguous case there is only one) whenever it surpasses a previous fixed threshold U 1 (= 0), intermediate value for s ij ranging in [−1,+1]. A true match should have s ij = +1. The ambiguities produced by broken edge segments are allowed. Therefore, we make a provision for broken segments resulting in possible multiple correct matches. The following pedagogical example from figure 2 clarifies this. The edge segment u in LI matches with the broken segment represented by s and q in RI, but under the condition that s and q do not overlap, that the s and q orientations do not differ by more than U 2 (±10°) and both s us , s ut are greater than U 1 .

Conclusion
This chapter presents a survey about the application of several stereovision matching approaches which are applied under different strategies. Three main features are used: pixels, edge-segments and regions. The mapping of the constraints differs depending on these features that in turn are determined depending on the type of scene. Also, a general review is made about different strategies in conventional and fish eye based systems. These last producing omni-directional images.
We have established the bases for extending the scheme in figure 1, if required, by introducing more matching constraints, such as the optical flow (Kim & Yi, 2008).

Acknowledgments
We would like to thank Dr. Finally, partial funding has also been received from DPI2009-14552-C02-01 project, supported by the Ministry of Spain Science and Technology within the Plan Nacional de I+D+i.