Monocular Depth Ordering Using Occlusion Cues

Universitat Polit` ecnica de Catalunya Master Thesis Project Monocular Depth Ordering Using Occlusion Cues Author: Guillem Palou Visa Advisor: Philippe Salembier Clairon Document presented to obtain the Master’s degree for the European Master of Research on Information and Communication Technologies Barcelona, June 7, 2011 Contents List of Figures 5 List of Tables 10 I Introduction 13 1 Background 15 1.1 DepthPerception............................ 15 1.1.1 History of vision . . . . . . . . . . . . . . . . . . . . . . . . 15 1.1.2 Depth Perception . . . . . . . . . . . . . . . . . . . . . . . . 19 1.2 StateoftheArt............................. 28 1.2.1 On Depth Perception . . . . . . . . . . . . . . . . . . . . . . 28 1.2.2 On Figure/Ground Classification . . . . . . . . . . . . . . . 31 2 Motivation and Organization 36 2.1 Motivation................................ 36 2.2 Organization .............................. 37 II Methods 39 3 System Models 41 3.1 The Binary Partition Tree . . . . . . . . . . . . . . . . . . . . . . . 41 3.1.1 ImageModel .......................... 43 3.1.2 RegionModel.......................... 43 3.2 GeneralAlgorithm ........................... 46 4 BPT Construction 48 4.1 The Merging Algoritm . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.1.1 ColorCriterion ......................... 49 3 Contents 4.1.2 Shape/Contour Criterion . . . . . . . . . . . . . . . . . . . . 52 4.1.3 AreaCriterion.......................... 52 4.1.4 Depth Criterion . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2 T-Junction Confidence Calculation . . . . . . . . . . . . . . . . . . 55 4.2.1 Overall Confidence . . . . . . . . . . . . . . . . . . . . . . . 55 4.2.2 ColorandArea ......................... 55 4.2.3 Angle .............................. 60 4.2.4 Curvature ............................ 64 4.2.5 Examples of estimated T-junctions . . . . . . . . . . . . . . 68 5 Depth Ordering 70 5.1 Overview: BPT Analysis . . . . . . . . . . . . . . . . . . . . . . . . 70 5.2 T-Junction Candidate Selection . . . . . . . . . . . . . . . . . . . . 70 5.3 Initial BPT Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.4 DepthReasoning ............................ 74 5.4.1 The Energy Function . . . . . . . . . . . . . . . . . . . . . . 75 5.4.2 The Minimization . . . . . . . . . . . . . . . . . . . . . . . . 78 IIIResults and Conclusions 89 6 Results 91 6.1 Objective Evaluation on synthetic images . . . . . . . . . . . . . . . 91 6.1.1 Errormeasure.......................... 91 6.1.2 Algorithm Performance . . . . . . . . . . . . . . . . . . . . . 93 6.1.3 Results.............................. 94 6.2 Results on natural images . . . . . . . . . . . . . . . . . . . . . . . 96 6.2.1 Benchmark on figure/ground labeling . . . . . . . . . . . . . 96 6.2.2 Comparison to the state of the art in Depth Ordering . . . . 103 7 Conclusions 110 7.1 Conclusions ...............................110 7.2 Futurework...............................111 IVBibliography 113 Bibliography 115 4 List of Figures 1.1 From left to right, laws of proximity, symmetry, similarity and closure of the Gestalt perception theory. Humans normally relate shapes using these laws to create bigger and more complex objects. . . . . . . . . . . 17 1.2 Images and their primal sketch, top and bottom respectively. . . . . . . 19 1.3 From left to right: left image, right image and true depth map. The depth map can be constructed from binocular disparity. . . . . . . . . . 21 1.4 Examples of relative size curse. Left: Balls, all of them similar appear to be one behind the other due to its relative size. (right) Persons, as the size of a person is approximately known, people at the end of the queue appear to be further apart (right) . . . . . . . . . . . . . . . . . 22 1.5 T-junction examples. In the left image: locally, region R2is the one forming the largest angle, appearing to be over R1and R3. At the right image, the depth ordering is inverted, since the sky region is forming the largest angle but belongs to the background. . . . . . . . . . . . . 24 1.6 T-junction counterexample. Stripes in the tiger form junctions with the background, but the foreground regions are the smallest ones. The same case appears whith the golfer black and pink clothes with the greenbackground. ............................. 24 1.7 Horse figure segmented into regions according to convexity and the minimarule.................................. 25 1.8 Texture gradient examples. Notice the incrementing high frequencies when the surfaces move away from the camera. . . . . . . . . . . . . . 27 1.9 Results of the algorithm in [1]. The second column represents the range images measured with a laser. Second and third column are the results from two different models of MRF, a Gaussian and a Laplacian model. Red/Orange means closer and blue corresponds to further regions. . . . 29 5 List of Figures 1.10 Results of the algorithm in [2]. Boundaries found by the algorithm are also overlaid on the color images. The two depth images for each scene refer to the maximum and minimum depth estimation values. Red/Orange means closer and blue corresponds to further regions. . . 30 1.11 At the top row the pdf of the position of each class of surface are presented. .From left to right: sky, tree, road, grass, water, building, mountain and foreground class labels. Red values are higher probabilities, while blue represent low values. The next three rows present the results of the algorithm in [3]. For each scene (first and fifth columns), results are (from left to right): predicted surface labels, measured ground truth depth map and predicted depth map. For the depth images, red means further and blue corresponds to closer regions. . . . . . . . . . . . . . . 31 1.12 Results of the algorithm in [4]. White means closer regions and black corresponds to the further ones. The second column shows the local cuesdetected................................. 32 1.13 Results of the algorithm in [5]. The second column represents the Pb boundaries. The third and fourth columns are the results from averaging local depth cues (third) and when the global CRF is applied (fourth). .................................. 33 1.14 Results of the algorithm in [6]. The first column correspond to the results of the algorithm applied on human marked segmentations. the second column shows results from automatic generated boundaries. Green are the correctly assigned figure/ground labeling, red are incorrect, and blue are the boundaries which could not be matched. . . . . . . . . . 33 1.15 Results of the algorithm in [7]. The second column represents the local figure/ground classifier based only on contours. At each boundary point, the green lines point to the figure perceived region. The third column shows the global figure/ground assignment, with red and blue meaning nearer (figure) and further (ground) respectively. . . . . . . . 35 3.16 Original image (left) and the quantized image created from the BPT construction. Each image pixel is assigned the most similar color on the signature found in the root BPT region. The rightmost image shows the colors found, being the percentage proportional to the height. . . . 45 3.17BPTprocess ................................ 46 3.18 BPT Creation process . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6 List of Figures 4.19 Effect of bin-to-bin distances. The second and the third histogram have the same distance with the first histogram although the colors are perceptually very different. While Kullback-Liebler and Bhattacharyya distance say that they are equally different, cross bin distances solve this problem by assigning a bin-to-bin cost. . . . . . . . . . . . . . . . 50 4.20 Graph representing the EMD problem. The arrows represent the flow from/to the bins and the nodes are the bins themselves . . . . . . . . . 51 4.21 Example of two adjacent regions having more that one T-junction (4) . 53 4.22 A T-junction boundary presents boundary pixels (red) which may introduce bias in mean and variance estimation. The three different regions are marked with white, gray and yellow. . . . . . . . . . . . . . . . . . 58 4.23 Three examples of region meeting points. Contours are outlined in white. From left to right: a background point, an edge and a T-junction. Below each image the value of λmin and λmax are displayed . . . . . . . 59 4.24 Values of Γ depending on the λmin and λmax distances measured. The invalid regions correspond to points where λmin > λmax, which is not possible. .................................. 59 4.25 Boundary uncertainty at the junction point. Original image(left), partition (center) and abstraction (left) for angle calculation. . . . . . . . 61 4.26 Frequency response of the angle estimation filter . . . . . . . . . . . . . 62 4.27 Example of the curves meeting at a junction point . . . . . . . . . . . . 66 4.28 Process to calculate the curvature. Left, local window with the three regions and some outliers (diagonal striped pixels, belonging to other regions). Center, binary image with Region 1 isolated. Right, reconstructed image without outliers . . . . . . . . . . . . . . . . . . . . . . 67 5.29 Block diagram of the minimization step of the algorithm . . . . . . . . 71 5.30 Example of T-junction candidate reevaluation. Since the background and the uppermost region are merged, there are some T-junctions disappearing (red circles) and some reevaluations (white circles). The T-junctions reevaluated are the ones involving the merging regions. Regions are represented by their mean color value. . . . . . . . . . . . . . 71 5.31 From left to right and top to bottom, last mergings of a BPT on a given image. Note that each time a merging occurs, some regions are changed making T-junction points to be reevaluated or, simply, to disappear. . . 72 7 List of Figures 5.32 From left to right. Original image and three image partitions obtained from the pruned BPT, varying the final threshold for T-junctions, with thresholds of 0.2, 0.1 and 0.05 relative to pmax. The absolute threshold of pth = 0.1 is kept constant in the three images. . . . . . . . . . . . . . 73 5.33 Tree pruning example. The two marking colors correspond to two different T-junctions. Left: initial T-junction marked regions. Center: a T-junction candidate is changed to one of its previous estimates. Right: final T-junction marked nodes (light green) and completed to form a partition (dark green). . . . . . . . . . . . . . . . . . . . . . . . 74 5.34 Detailed block diagram of the minimization step of the algorithm. The two concatenated loops are the basis of the algorithm. . . . . . . . . . 75 5.35 Depth ordering (right) of the image on the left . . . . . . . . . . . . . . 77 5.36 Three possible prunings of a given BPT. For each pruning, the framed leave nodes are pruned and its parent becomes a new leave, reducing the number of BPT nodes by one. All other possible prunings in this BPT reduce the tree by more than one node. The results of the prunings (red, blue and green) are shown a the bottom (left,center and left respectively). 79 5.37 Example of convexity. Left: original image with the segmentation overlaid. Right: possible partition with convexity cues showed. Points of high curvature/convexity are cues to determine the relative depth. Convexity should be averaged to decide the correct sign of convexity. . 80 5.38 Convex regions, R1, have less area (marked in light blue) in discs at the boundaries with their adjacent regions, R2. The less the area is, more convex R1appearstobe. ...................... 81 5.39 Directed graph constructed from the depth cues. Labels on the edge represent their strength. The conflict formed by the loop R2←→ R3 may be eliminated by deleting the red edge. . . . . . . . . . . . . . . . 83 5.40 Conflict resolution for the graph in Figure 5.39. At left, the remaining graph resulting from the deletion of the edge p4. At right, the conflict is resolved by turning edge p4. Both solutions are feasible, depending on the nature of the cue represented by the edge with weight p4. Either case, the remaining graph is a DAG. . . . . . . . . . . . . . . . . . . . 86 5.41 Hasse representation of a graph. The top nodes have the lowest partial order. At each lower level, the partial order is increased. . . . . . . . . 87 6.42 Example of the Gaussian window used in T-junctions for error computation. A maximum displacement of 2 pixels in horizontal or vertical direction is allowed. Dark colors are lower values. . . . . . . . . . . . . 92 8 List of Figures 6.43 Test image with several noise contaminations. From left to right, PSNR = 48, 38, 28, 18, 8 and -2 dB respectively. . . . . . . . . . . . . . . . . 93 6.44 Error in dB encountered in T-junctions as a function of the window size. The left plot shows the evolution of the errors for different window sizes, depending on the PSNR. The right plot shows the mean error for each windowsize.................................. 94 6.45 Error in dB encountered in T-junctions with a window radius of 10 pixels. .................................... 96 6.46 From left to right. Original image, depth estimation results and figure/ground labeling on contours. In the depth order image, white regions are closer to the viewer. In the figure/ground labels, white pixels belong to the foreground region, the black belong to the ground region. Gray pixels are unassigned because they don’t lie on a depth contour. . 97 6.47 Original images (color) and their human-marked segmentation (gray level). Each region is colored with a different gray level. . . . . . . . . . 98 6.48 Probability of occurrence of normal and inverted T-junctions, depending on the number of times the largest region is at the top of other T-junctions.................................. 99 6.49 Probability for R1to be the foreground region (green) or the background region (blue) depending on the value K(x, y). The radius of the neighborhood Ω(x, y) is set to 5,10 and 15% of the contour length. Clearly, if log a1 a2is positive, R1is more likely perceived as ground. . 100 6.50 Left: Images with contours overlaid. Green contours are correct assignments of figure/ground and red are incorrect. Right: depth order representation of the regions. White regions are closer to the viewpoint, while black regions are further away. . . . . . . . . . . . . . . . . . . . 102 6.51 Results on depth estimation and figure/ground assignment on some of the BSDS500 images. From left to right, for each column: original image with marked T-junctions, depth estimation and figure/ground boundaries. For T-junctions, black T-junctions are inverted and white are normal. .................................104 6.52 More results on the BSDS500 dataset. For each column (3 images) and from left to right: original image with marked T-junctions, depth estimation and figure/ground boundaries. the white marked T-junctions are normal or black if they are inverted. .................105 9 1. Background proposed that vision was the result of unconscious processes based on previously learned situations. Examining the eye, this german physicist stated that it had poor optical features and that perception was a phenomenon hardly linked with a learning process that lasted many years: the unconscious inference. In that way, humans have a priori expectations of the scene structures such as the position of light and the object orientations. Due to the introduction of the learning process, human vision was seen with a broader perspective, introducing new disciplines for its comprehension. Helmholtz work [9] provided empirical theories about his studies on spatial, color and motion perception. The relevance of this study made it the reference on the theory of vision throughout the second half of the nineteenth century. After that, other theories appeared but in the recent years, its principles were rethought with minor refinements. In the latter years, namely between 1930-1940, Gestalts psychologists presented their theory of the Laws of Organization where it was stated that the brain was behaving in a holistic, self-organizing way in all its activities, and vision was one of them. Their theory of vision was based on the capacity of the brain on figureforming and visual completion instead of perception of individual, simpler visual elements. The Gestalt school was also created in Germany (as Helmholtz) and its roots came from philosophers such as Kant or Goethe. The methodology used in the investigations following Gestalt laws were conducted under two principles: Principle of Totality This principle states that the conscious experience is the sum of individual aspects of the individual and it must be considered as a whole. That is, all the senses contribute to an experience. Principle of Psychophysical Isomorphism This principle relates the visual perception and the cerebral activity. Gestaltists believed that the order in which stimulus were perceived was the same order in which the brain processed the information. That is, if two situations are perceived similarly, the brain will process them in identical ways. Assuming these principles it is possible to state some properties about the perception of figures and postulate the famous laws of organization. Gestalt psychology stated some perception rules: Emergence is the process of complex pattern formation thanks to several, simpler rules. That is, objects are first perceived as a whole. After, once the overall structure is inferred, the details are extracted. 16 1.1. Depth Perception Reification is the constructive aspect of perception and its strongly related to visual completions. The theory states that humans complete the image, by means of the laws of organization, to construct objects, even if these objects don’t exist. Multi-stability is the ability of seeing two different things in a situation. This theory is clearly involved in illusions where several interpretations of a scene are possible. Invariance is presented as the ability of humans to perceive the same objects independently of rotation, scale, deformation, lighting conditions and other situations. Note that these situations are always common events that may appear in normal scenes. These properties may appear separated or jointly, but the Gestalt theory does not explain how they arise. Instead, the theory describes how the perception is organized. The fundamental vision processes for Gestalt are the Laws of organization in which it is possible to encounter proximity, similarity, closure, symmetry, common fate and continuity; some of which are shown in Figure 1.1. These laws try to explain how objects are perceived as a whole, relating minor features to construct the overall interpretation. It is important to note that for Gestaltists objects are perceived first as objects and then details are examined. Although these principles seem to play an important role in many situations, the Gestalt theory was strongly criticized due to its descriptive nature instead of explaining these processes. At this point, several theories arose to explain how the perceived information was processed. The two most important ideologies were the cognitive and the computational approaches. The former returned to the roots of the perception, recalling Helmholtz, and presented the problem as a subconscious process based on a Bayesian framework. The latter was interpreting the brain as a sort of computer and proposed an algorithm to explain the vision process. The modifiFigure 1.1: From left to right, laws of proximity, symmetry, similarity and closure of the Gestalt perception theory. Humans normally relate shapes using these laws to create bigger and more complex objects. 17 1. Background cation of the Helmholtz principles to introduce a more objective concept, such as probability, was a first step to explain the vision from a more technical point of view. Although a universal model is still unknown, the proponents considered that the human brain, through processes of (un)conscious learning, stated the problem as a form of Bayesian inference from sensory data. This inference was not treated in the Helmholtz original theory, although the rules that governed this probabilistic approach were not known. The base of this approach was the so called Inverse Optics Problem: Information in visual stimuli cannot be mapped unambiguously back onto realworld sources, a quandary referred to as the Inverse Optics Problem. The same problem exists in all other sensory modalities. [10] Hence, in the presence of ambiguous input, the correct interpretation is found by evaluating all possible solutions and choosing the candidate with higher a posteriori probability. The brain, seen as a Bayesian Network, is constantly modified by the introduction of new experiences. Although the Bayesian approach is widely used nowadays in vision systems, David Marr proposed a computational model for the human vision. In his work, [11], he presented the vision process as an algorithm consisting on three information processing steps: 2D or Primal Sketch: the first stage of vision consists in gathering the principal features of the scene, namely lines, common figures, forming edges and regions. This sketch can be compared with the first step an artist would take to represent a drawing. 2.5D Sketch: the second stage gathers texture. In this step, the lighter and darker regions are detected, identifying shades, as well as surface orientations thanks to textures. 3D Sketch: the final step of the algorithm combines all the previous perceived structures and constructs a 3D scene. Figure 1.2 represents what the first sketch is. Marr theory does not include the use of multiple points of view (the two retinal images, for example). To adopt several perspectives, the general approach is to consider that after the three sketches the different images are combined for a better scene understanding. 18 1.1. Depth Perception Figure 1.2: Images and their primal sketch, top and bottom respectively. The model of David Marr was very helpful in computer vision and image processing areas which were seeking algorithms for scene understanding. Nowadays, in the computer vision field, the primal sketch is performed mainly by the edge detectors, the 2.5D Sketch is more focused on region/texture segmentation while the last step, the most difficult one even now for computer systems, is performed by (among others) pattern recognition and scene understanding/interpretation algorithms. After reviewing vision history, one can better understand the steps performed by computer systems and the concepts they are based on. Although psychology and image processing seem two very different fields, they are somehow related: the former are the foundations and basis of the latter. Such influence may be noticed for various topics such as Color Perception, in which the CIE L*a*b color space was created to correspond to the brain stimulus; or JPEG image compression and encoding, where frequencies on the image are encoded depending on their perceptual importance. In other words, modern psychology states the basis to develop automated computer vision systems. Vision, per se, covers a wide range of topics. This project focuses on some aspects of depth perception for which an introduction is presented in the following section. 1.1.2 Depth Perception Depth perception, as a field of scene understanding, is the one of the most difficult part of image processing, either for the brain or for a computer. History of depth perception is not as rich as the overall vision process. Some consensus exists about the main processes acting to achieve a 3D scene construction from 2D images. The step is to separate the different cases that may appear where observing a 19 1. Background scene. It is possible to distinguish three different cases, each of them involving its advantages and drawbacks. Multiple Views: This case occurs either in natural human vision or in multiple camera systems. It provides multiple points of view of the same scene. In the case of humans, these two viewpoints correspond to the eyes; for computers, there can be more than two viewpoints Monocular View: A single point of view is present. This situation can be found also in nature (animals with one eye on each side of the head) or in computer systems (for instance, viewing a photo in a LED display). Motion Information: This type of information can be associated to either multiple or monocular views. The particularity resides in the temporal information that can be gathered. As in the first two cases, motion information is present in nature or in computer systems equipped with video devices. Motion information will be discussed in Section 1.1.2.3. For the other two cases, depth perception is easier with multiple views than with only one image. it is commonly agreed that depth perception initially relies on cues, such as image structure or disparity. Sections 1.1.2.1 and 1.1.2.2 present some of these depth cues that help humans reconstruct the three-dimensional world. 1.1.2.1 Multiple View Vision Multiple view appears naturally in humans with only two points of view. This kind of structure is known as stereo vision: only two points of view are available and very close together. Although there are popular systems, such as the 3D cinema, which uses stereo vision, systems relying on multiple viewpoints (more than 2) usually perform more robustly. Obviously, a system with more than two viewpoints is impossible to have for human vision. Architectures with more points of view are only available in computer-aided systems. Two types of cues can be found to infer the depth from a pair of (or more) images. Note that cues that are strictly monocular may also work in the multiple view case. These cues will be commented in Section 1.1.2.2. Vergence: In humans, the visual axes of the eyes (cameras) must converge on the observed object to allow to focus and to infer the depth information. Note that situations in which the eyes do not converge correspond to peripheral vision. Although humans can see outside the main focused object, their ability to detect 20 1.1. Depth Perception shapes and depth decreases abruptly outside a field of view of approximately 30 degrees. Peripheral vision is used to detect rapid movements and the background structure, but humans must focus objects to examine them carefully [12]. From the eyes muscles, humans may infer if they are focusing a near of far object. Binocular Disparity: When two cameras located at different positions observe the same scene, the created images are closely related. Normally, large regions of both images can be matched as shown in Figure 1.3. From the displacement of the matched region and the knowledge of the camera positions, it is possible to infer the absolute depth of the objects present in the scene. The use of only two points of view may introduce some uncertainty areas. these areas are regions that can be observed only from one point of view. Therefore, in these areas disparity is not available. If the uncertainty regions needs to be reduced, this can be achieved gradually by introducing more cameras. 1.1.2.2 Monocular Vision Monocular vision does not occur only in computer vision. Animals that have one eye on each side of the head, can only rely on monocular cues to detect depth. There is an evolutionary theory stating that animals that need high precision in their fast movements (such as predators) have their eyes coupled to permit stereo vision, while animals which do not (as herbivores) can rely only on monocular cues [13]. It is important to note that the cues acting for monocular vision may work together with multiple viewpoints. Humans, for example, a part from disparity, they can take advantage of monocular depth cues. To infer depth using only one image, there are several cues which can be used, and some of them are presented here. Figure 1.3: From left to right: left image, right image and true depth map. The depth map can be constructed from binocular disparity. 21 1. Background Relative Size: If two objects are known to be of the same class (e.g. two persons) but their absolute size is unknown within a degree of variability, the two objects observed size in the image can provide information about their relative depth. From the viewpoint (a camera, for example) the observed size of an object is measured by the visual angle occupied on the field of view. The bigger object will appear to be nearer, Figure 1.4. Familiar Size: If some insights are known about the size, some suppositions about their absolute depth can be inferred, Figure 1.4. This cue is strongly related with the previous one. As the visual angle projected to the camera (or retina) decreases with distance, the lesser the area is occupied in the image, the further appears the object. This cue is only applicable with prior learning of the objects, such as persons, cars and several other familiar things from which its size can be approximated. Aerial Perspective and Contrast: This cue is observed in very specific situations, where the scene extend may reach several kilometers. Typically, when one observes a landscape, points very far away appear blurred and with low contrast. This blurring is due to the effects of the atmosphere, making further away points to fade into the same color than the sky. Although it can be used to distinguish relative depth, this cue is very approximate since the effects of the sky will differ from one place to another, or even from day to day at the same place. Since now several cues have been discussed. To be able to use them in a computer-based system, some prior knowledge has to be introduced. Size and aerial perspectives cues work on very specific situations and, for them to work, a Figure 1.4: Examples of relative size curse. Left: Balls, all of them similar appear to be one behind the other due to its relative size. (right) Persons, as the size of a person is approximately known, people at the end of the queue appear to be further apart (right) 22 1.1. Depth Perception previous analysis of the scene should be done. For example, to classify depth with the relative size, some detector of known objects need to be used, and to use the aerial perspective a supposition about the scene needs to be specified. Other types of cues, however, are known to be very effective to order depth but, differing from the previously commented, they work on low-level image features, such as the geometric structure. Five of these cues (there may be other, but less important) are perspective, occlusion, convexity, texture gradient and shading. Perspective: This cue is closely related to what is called vanishing point. Due to the projection of the 3D-world into the image plane, parallel lines in the real scene appearing the 2D image as lines crossing at a common point. This effect appears mostly in lines perpendicular to the image plane. Lines parallel to the image plane do not experiment this effect. Needless to say, the closer are the lines observed in the image, the further they appear to be. Occlusion: Occlusion is known to be a strong depth cue and it is found locally in some special points, known at T-junctions [14]. These kind of points are created thanks to the projection of the real world scene to a visualization plane. If an object is between the point of view and two other objects or regions, it is likely that a T-junction will be created. As an example, in Figure 1.5, when projecting spheres in the real world into circles in the image, some intersections (juntions) are created where generally three objects meet. Locally, in this intersections, the boundaries of the objects define the junction angle characteristics. If occlusion is perceived, this angle configuration is somewhat specific, although the depth ordering is not straightforward to state. Normally (but not always), the region belonging to the object lying closer to the viewpoint will form almost a flat angle. The other two regions will form two arbitrary but similar angles. In Figure 1.5, it can be seen that, in the marked T-junction, the red region, R2, occupies most of the local window, shaping a nearly perfect 180 degree boundary with the other regions. From among all the types of junctions, there are some which will indicate stronger signs of occlusion than others. For instance, stronger T-junctions appear when the two rear regions, although not having any restriction about the angle, form a smallest angle bigger that 40 degrees; below from that, the perception of depth may be decreased rapidly, [15]. [15] states that the detection of these points is difficult locally and some global reasoning from the image structure is needed. Moreover, the scale to correctly classify T-junctions greatly depends on the image 23 1. Background Figure 1.5: T-junction examples. In the left image: locally, region R2is the one forming the largest angle, appearing to be over R1and R3. At the right image, the depth ordering is inverted, since the sky region is forming the largest angle but belongs to the background. nature (synthetic or natural) and many other factors such as colors, angles, etc. If no global reasoning is done, T-junction depth order cannot be reliably set. For example, textures may generate color differences which, at a small image extent, can replicate the region angle configuration. In Figure 1.6 some of these examples may be observed. A imple classification on T-junction can be done, depending on their local depth ordering: the normal and the inverted. . The former class is when the region forming the largest angle is the foreground. The latter class is when the opposite Figure 1.6: T-junction counterexample. Stripes in the tiger form junctions with the background, but the foreground regions are the smallest ones. The same case appears whith the golfer black and pink clothes with the green background. 24 1.1. Depth Perception depth order is found. Locally, both types of junctions have the same feature configurations. However, humans interpret correctly the types of junctions easily. Convexity: Convexity is also a good sign for perceptual organization in an image. Psychological studies such as [16,17,18] aim to prove that natural objects which present convex shapes appear to be int the foreground, while the concave ones seem to lie in the background. Convexity also helps in object segmentation. In [19], is stated that natural objects such as persons, animals, trees... are mainly composed of convex parts. When facing an image, the human visual system first detects the object boundaries. The shape of an object will be characterized by its curvature. This curvature will be positive in object extremities such as the legs or the head, and negative otherwise. From the curvature characteristics, the overall shape is divided into smaller parts at the points of negative minima curvature. This concept cap also be extended to meshes. That is, the minima rule [20,21] is a procedure for dividing a shape/mesh into simpler subparts, at the points of high curvature. For instance, taking [22] as an example of segmenting an object into simpler subparts, Figure 1.7 shows a horse mesh. The segmentation, as expected, breaks the overall animal into its most salient and relevant parts only taking points of minima curvature into account. As a result, objects in the scene may present points of high positive curvature (and thus locally convex) and points of high negative curvature (perceived locally as concave). Thus, to decide if an object is the foreground or background region, humans integrate along the overall shape the local convexity decisions. The overall decision will depend on the averaged sign of the curvature/convexity. Although convexity may present a correct approach for depth perception, like ocFigure 1.7: Horse figure segmented into regions according to convexity and the minima rule. 25 1. Background Chapter 4. Monocular Depth Cue Integration 140 (a) (b) (c) (d) Figure 4.19: Results obtained by performing the two proposed approaches. (a) Original image. (b) T-junction detection. (c) Depth ordering obtained by using the diffusion based framework. (d) Depth ordering obtained by using the region-merging based framework. Figure 1.12: Results of the algorithm in [4]. White means closer regions and black corresponds to the further ones. The second column shows the local cues detected. boundary ownership problem, and many approaches have been proposed in the literature [5,6,7]. The work on [5] was one of the first to deal with this problem. From the several approaches that [5] offered, the one which performs the best is again a learning based approach. First, the algorithm clusters boundary shapes into what the authors called shapemes. Afterwards, a model using a CRF is learned to ensure global consistency on junctions (junctions are considered as the boundary points with high curvature and the ones where three or more boundaries meet). The boundaries used on the overall process are either obtained from human segmentations or by thresholding values [41]. The results are shown in Figure 1.13 The approach in [6] comes from a completely different perspective. First, a probabilistic model is stated by means of empirical observation on the data. Once the model is trained, the system infers the probability of the depth of the boundary points. Using a CRF, the global joint probability si maximized. After the probability of the segments’ depth is maximized, the ownership of a curve is determined according to the depths of the neighboring image segments. The closer regions are assigned the owner of the boundaries. The last approach, found in [7], is a joint image segmentation and figure/ground labeling process. The concept lying behind [7] is to add order to the segmentation boundaries, which is solved by means of Angular Embedding, [42], a novel technique that relate the local luminance in different regions of an image to obtain the global perceptual brightness. 32 1.2. State of the Art 13 Fig. 10. Results based on Pb boundaries. Shown here are the images, the Pb edge map, figure/ground labels from the local shapeme model (average accuracy 64.9%), and labels from the global CRF model (average accuracy 68.9%). Without using humanmarked segmentations, the results are more noisy and less consistent. Nevertheless the local shapeme model applies without any difficulty, and global inference on a bottom-up contour/junction structure still significantly improves performance. Figure 1.13: Results of the algorithm in [5]. The second column represents the Pb boundaries. The third and fourth columns are the results from averaging local depth cues (third) and when the global CRF is applied (fourth). (a) (b) Figure 5. Sample results for (a) human-marked curves, and (b) automatically generated curves. Green denotes correct, red denotes incorrect, and blue denotes unmatched curve pixels. The original color images are shown here in gray-scale so that the curves can be seen clearly. Cues Performance Convexity 71.4% (68.4%) Lower region 64.1% (61.9%) Fold/cut 71.8% (69.2%) Parallelism 64.7% (52.4%) Curve (Vi) 80.7% (78.1%) Junction (Vy) 70.2% Curve + junction 82.1% All 82.8% Table 1. Performance evaluation on the human-marked segmentations for various cue combinations. The non-parenthesized figures report the performance under the proposed model (2.1D). The parenthesized figures report the performance when the curves are independently assigned the label of higher likelihood conditioned on the corresponding curve cue(s). curve end to the curve end closest to it or to its closest point on the image boundary, whichever was closer. A similar heuristic was used in [15] for constructing the junction graph. In order to transfer the ground truth labels from the human-marked curves to the automatically generated ones, we matched each pixel on the latter curves to its closest pixel on the former curves, while allowing a maximal Euclidean distance between matched pixels (0.75% of the image diagonal, which is about 4.3 pixels). Then, we transferred the ground truth labels according to the local curve orientations at the corresponding pixels1. Sample results are shown in Fig. 5(b). As in [15], we measured the figure/ground assignment accuracy as the ratio between the number of correctly labeled pixels to the total number of pixels for which the ground truth label was transferred. This yielded 69.1% accuracy. Although this accuracy percentage for the automatically generated curves is similar to that in [15] (68.9%), the two methods might not perform similarly for such curves because of differences between the generated curves here and in [15] and because of the noted difference in the pixel matching process. 5. Discussion A new method for estimating the figure/ground labels of boundary curves in images was proposed. The main novelty of the method lies in its use of the 2.1D model. The method estimates the ordinal depths of the image segments 1A similar process was carried out in [15], except that the matching between the pixels was bipartite. Bipartite matching between ground truth data and noisy data is more suitable under the condition that each ground truth datum generates at most one noisy datum. Looking at the ground truth and generated edge maps, we concluded that this condition does not hold and so we opted for the other matching method. Note also that a bipartite matching might match only a fraction of a noisy tortuous curve to its corresponding true, smooth curve. This will reduce the weight of the curve in the overall accuracy evaluation, which might bias the evaluation positively since the labeling of noisy curves is more likely to be wrong. (a) (b) Figure 5. Sample results for (a) human-marked curves, and (b) automatically generated curves. Green denotes correct, red denotes incorrect, and blue denotes unmatched curve pixels. The original color images are shown here in gray-scale so that the curves can be seen clearly. Cues Performance Convexity 71.4% (68.4%) Lower region 64.1% (61.9%) Fold/cut 71.8% (69.2%) Parallelism 64.7% (52.4%) Curve (Vi) 80.7% (78.1%) Junction (Vy) 70.2% Curve + junction 82.1% All 82.8% Table 1. Performance evaluation on the human-marked segmentations for various cue combinations. The non-parenthesized figures report the performance under the proposed model (2.1D). The parenthesized figures report the performance when the curves are independently assigned the label of higher likelihood conditioned on the corresponding curve cue(s). curve end to the curve end closest to it or to its closest point on the image boundary, whichever was closer. A similar heuristic was used in [15] for constructing the junction graph. In order to transfer the ground truth labels from the human-marked curves to the automatically generated ones, we matched each pixel on the latter curves to its closest pixel on the former curves, while allowing a maximal Euclidean distance between matched pixels (0.75% of the image diagonal, which is about 4.3 pixels). Then, we transferred the ground truth labels according to the local curve orientations at the corresponding pixels1. Sample results are shown in Fig. 5(b). As in [15], we measured the figure/ground assignment accuracy as the ratio between the number of correctly labeled pixels to the total number of pixels for which the ground truth label was transferred. This yielded 69.1% accuracy. Although this accuracy percentage for the automatically generated curves is similar to that in [15] (68.9%), the two methods might not perform similarly for such curves because of differences between the generated curves here and in [15] and because of the noted difference in the pixel matching process. 5. Discussion A new method for estimating the figure/ground labels of boundary curves in images was proposed. The main novelty of the method lies in its use of the 2.1D model. The method estimates the ordinal depths of the image segments 1A similar process was carried out in [15], except that the matching between the pixels was bipartite. Bipartite matching between ground truth data and noisy data is more suitable under the condition that each ground truth datum generates at most one noisy datum. Looking at the ground truth and generated edge maps, we concluded that this condition does not hold and so we opted for the other matching method. Note also that a bipartite matching might match only a fraction of a noisy tortuous curve to its corresponding true, smooth curve. This will reduce the weight of the curve in the overall accuracy evaluation, which might bias the evaluation positively since the labeling of noisy curves is more likely to be wrong. Figure 1.14: Results of the algorithm in [6]. The first column correspond to the results of the algorithm applied on human marked segmentations. the second column shows results from automatic generated boundaries. Green are the correctly assigned figure/ground labeling, red are incorrect, and blue are the boundaries which could not be matched. 33 1. Background The algorithm also works with an external boundary detector such as the one proposed in [43]. The results obtained with this technique can be found in Figure 1.15. The human performance on figure/ground segregation is assumed to be around 88%. Since it is a fairly new field of study, depth perception and figure/ground organization are considered to be an open problem. Still, state of the art results in figure/ground are around 65-70% of correct boundary predictions, leaving much room for improvement. Nevertheless, since there is also a perceptual component, each subject may perceive scenes in different ways, depending on the objects on the scene, thus making it difficult for computers to deal with inconsistencies. In this work, the problem of perceptual image structure is considered to be an immediate extension of the depth organization, considering foreground objects (figure) to be the objects placed in front others with respect to the point of view. The novelty of the proposed approach is that the problem is addressed from a region-based framework, unlike the other commented algorithms. 34 1.2. State of the Art 10 Segmentation and Figure/Ground Organization using Angular Embedding invariant). Clustering these descriptors using K-means (with K= 64) yields a vocabulary of shapemes [24], which capture local contour configuration. A point of interest on a test contour is described by the vector measuring the similarity of its Geometric Blur descriptor to each of the shapemes. We transfer human figure/ground labeling to the automatically generated nonmax-suppressed mPb contours using bipartite matching of edge pixels. We then train a logistic-regression classifier fthat predicts local figure/ground assignment using the vector of shapeme similarities. This learned classifier performs at 62% accuracy, similar to the 65% accuracy reported by Ren et al. [24] for their local classifier. Figure 5 shows example human-annotated training data for this task and Figure 6 demonstrates local figure/ground predictions and recovered global ordering. In order to take only fairly reliable predictions into account during globalization, we sample edge locations (x, y) for which mPb(x, y)>τand only run the local figure/ground classifier at those locations. We set τ=0.3. Fig. 6. Local to global figure/ground. Left: Image. Middle: Local figure/ground assignment by our shape-based classifier for the most salient mPb [17] contours. Vectors drawn from edge points indicate the predicted figural side by their red tip. Vector length corresponds to classifier confidence. Right: Recovered global figural ordering. Figure 1.15: Results of the algorithm in [7]. The second column represents the local figure/ground classifier based only on contours. At each boundary point, the green lines point to the figure perceived region. The third column shows the global figure/ground assignment, with red and blue meaning nearer (figure) and further (ground) respectively. 35 2. Motivation and Organization 2 Motivation and Organization 2.1 Motivation Monocular depth ordering systems are currently an active field of research in the image processing and computer vision field. While most of the works assume some image structures, there are very few that perform the depth ordering task under the supposition of Gestalt cues. The proposed system is motivated by the work [4], refusing a learning based approach. The previously cited work is also based on occlusion relations to retrieve a depth ordering of the objects on the scene. The proposed approach, however, redefined some of the concepts such as the depth order provided by T-junctions. The discontinuity on depth is not questioned, but the depth order is not straightforward to decide by a merely local decision. That is, the region forming the largest angle is not always closer to the viewer. Instead, the order depends on all the nearby T-junctions involving the same region. The work [4] relied on external, state of the art, junction detectors working with hard thresholds. The problem with pixel-based detectors is that some difficult junction points are not detected but the use of a region-based approach can overcome some of these cases. As said in Section 1.1, many vision theories state that the human perception is a Bayesian inference process. To adequate the proposed algorithm to existing vision theories, our work states a a probabilistic framework to detect T-junctions and order image regions according to depth. Moreover, human scene interpretation is known to be a cooperative process of smaller problems such edge detection, texture recognition, cue inference, etc. For this reason, a hierarchical image representation is performed jointly with T-junction detection; and depth ordering is computed while finding a possible image segmentation. The following section outlines the presentation of the work. 36 2.2. Organization 2.2 Organization The proposed system attempts to recover the relative depth of images by working on low-level depth cues. From the depth order image, the figure/ground labelings are assigned for contour points. Similar to [4], the algorithm does not rely on a priori information. Instead, it is based only on simple Gestalt principles for depth perception. Moreover, only occlusion and convexity cues are used to discriminate depth regions in the images. The region-based algorithm in [4] has three clear steps. First, estimation of T-junction points and convexity cues is performed. Second, the image is segmented using a region growing technique. In the last step the relative depth for each region is determined, resolving conflicts appeared due to contradictory cues. The proposed approach differs from [4] in two basic aspects. Due to the difficulty of detecting local depth cues, the first and second steps are merged. The region growing approach is done by means of a Binary Partition Tree (BPT) and the Tjunction estimation is performed within the tree construction. The BPT creation process is considered to be complementary with the T-junction estimation since the former defines the regions and the latter evaluates if these regions are indeed different objects in the scene. Once the BPT is constructed, the depth estimation is performed by an iterative minimization of a defined energy function. Results obtained with only low-level occlusion cues are comparable with the state of the art systems that use learning and, therefore, higher level information. This is a clear advantage since no a priori information is needed and no scene assumptions are made. This manuscript is organized as follows. In the following part of the manuscript, the algorithm architecture is exposed in two parts: the construction and the pruning. In Chapter 3, the models used for the BPT construction are presented, along with the region similarity measure, a key concept in the BPT structure. Chapter 4 exposes the construction process and the T-junction candidate points estimation, focusing on the details for the different characteristics that these points have (color, angle and curvature structure). Concluding with the algorithm, in Chapter 5, the process of depth reasoning with the previously constructed BPT is explained. Finally, in Chapter 6the results are presented on synthetic and natural images. The algorithm is compared quantitatively with state of the art figure/ground segregation approaches. Due to the lack of a ground truth database for relative depth, depth estimation results are qualitatively compared with absolute depth retrieval systems. 37 Part II Methods 39 3 System Models Before starting to comment the system architecture and the processing, it is important to define the basic models used by the algorithm. Section 3.1 states the basic concepts for the used core structure, the Binary Partition Tree (BPT). 3.1 The Binary Partition Tree In most image processing applications, an image is viewed as a set of pixels placed on a planar grid. This low level and unstructured representation only offers the possibility to use simple algorithms due to the large number of pixels composing the whole image. Moreover, the representation does not describe the spatial composition and does not provide support to easily handle semantic notion. In the recent years, there has been an increasing interest to consider the image as a set of superposed regions. Thus, a region-based representation has to be computed from the pixel level. Since the information in an image may be present at different scales, the image representation should be able to deal with different levels of detail. This characteristic is obtained by constructing a hierarchical set of regions. To generate such regions, two main approaches handle the problem either with a top-down or a bottom-up perspective. The former initially considers the image as a unique region and then, splits iteratively the newly created regions to obtain the final partition. The latter considers the pixels as a starting point and the final regions will grow from these initial seeds. Among the literature, examples of these systems can be found in[44,45,46]. The most common hierarchical structure to use is a tree. The simplest form of a tree, known as the BPT, was proposed in [47] and proved to be fast and efficient. The BPT per se is an abstract concept used in a wide variety of algorithms. Some of its applications are, for example, classification, regression and clustering. One of its uses in image processing is image representation. The BPT is a structured representation of the image regions that can be obtained from an initial parti41 4. BPT Construction 4 BPT Construction 4.1 The Merging Algoritm The construction of the BPT is done by merging regions iteratively as explained in 3.1. The order in which these regions are merged is given by a similarity measure. Usually, this measure is based on low-level features of the regions such as color, area, or shape. In this project, however, depth information is also introduced to contribute to the similary measure. The overall distance between regions is a contribution of all the features mentioned above. Namely, the expression for the measure is: d(R1, R2) = da(R1, R2)×(αdc(R1) + (1 −α)ds(R1, R2)) ×dd(R1, R2) (4.1.1) Where R1and R2are two arbitrary (but adjacent) regions. dastands for the area distance. dcand dsare the color and shape measures respectively. αis the weighting factor between shape and color. Its value was experimentally set to α= 0.7. ddis the depth measure introduced. These four contributions (area,color,shape and depth) are considered to be key characteristics to define regions, and color is the most important feature. In practice, however, objects in the real world have more or less compact and round shapes. The exclusive use of color distances lead to regions with unnatural shapes so a measure evaluating the region contour is introduced. Moreover, relevant objects in a scene present similar areas so a term addressing region size is also included. Since the goal of this project is to estimate depth planes, the inclusion of a depth measure attempts to differentiate different levels of depth during the BPT construction. The first region clue to examine is the color characteristics. Two regions are different depending on their color distribution. Abstracting the problem, each region is characterized by a 3D histogram, represented by a signature and thus, in theory, any distance comparing two pdf ’s would be valid. In Section 4.1.1, the choice of this distance is formulated. 48 4.1. The Merging Algoritm 4.1.1 Color Criterion Histograms are a way to represent probability density functions (pdf ). In this case, they are applied to the represent the color/intensity of the pixels. Therefore, the problem to compare two region colors is equivalent to compare two color histograms. There is a wide repertory of measures that can be considered, ranging from Lpnorms to ground distance measures like the histogram intersection [61]. For the purposes of the project, only three distances are examined, two of them proposed by [53] and the Earth Mover’s Distance (EMD) stated in [62]. The EMD is proposed here and studied for the first time in the context of BPT construction. The two distances proposed in [53] are the Kullback-Leibler and the Bhattacharyya information theory-related divergences. The former is defined as KL (h,g) = N−1 X i=0 hilog gi hi+gilog hi gi (4.1.2) And the latter can be written as B(h,g) = −log N−1 X i=0 h1/2 ig1/2 i!(4.1.3) Where hand gare two pdf ’s represented by a set of values gi,hiwith i= 0 . . . N. These values are the probability to observe the color value i. It is assumed that both hand ghave the same number of bins in both equations. The first measure can be seen as the probability of the two pdf ’s being generated from a common one and the second can be understood as an approximation of the Chernoff Information between two N-dimensional vectors. Although these measures can achieve good results, they have a strong limitation. The limitation is that, a part from the general metric properties, histogram comparison must obey some perceptual distance. That is, two colors that are perceived very differently (e.g. black and white) must have a higher distance than two similar colors (e.g blue and turkish). This intuitive reasoning is not fulfilled in bin-to-bin distance like the ones presented in (4.1.3) and (4.1.2). If the distances (4.1.2) and (4.1.3) are used to compare the left histogram with the center and right histogram in Figure 4.19, the same result is obtained. Perceptually, however, the red color is much more different to the dark blue than the light blue. This limitation can be overcome by using the so called cross bin distances, such as the Diffusion Distance [63] or the Earth Mover’s Distance (EMD). The Diffusion Distance measures the distance by iteratively computing the energy of the 49 4. BPT Construction Pixel Intensity Probability Pixel Intensity Pixel Intensity Figure 4.19: Effect of bin-to-bin distances. The second and the third histogram have the same distance with the first histogram although the colors are perceptually very different. While Kullback-Liebler and Bhattacharyya distance say that they are equally different, cross bin distances solve this problem by assigning a bin-to-bin cost. convolution of a Gaussian Kernel with the bin-to-bin histogram difference. It turns out that this process, which has the same behavior as the heat propagation in a medium, can be seen as an approximation of the EMD. The EMD was first presented as a transportation problem. In this project, like in [64], it is used to compare two pdfs. The EMD was first proposed to find the minimum cost to transport units of material from a source to a destinations. In our case, the EMD can be reformulated as an algorithm to compare two signatures and it was first stated in [64]. It measures the amount of probability mass that has to be moved, to convert one histogram h into another gfollowing some cross-bin unit costs. Although it is a good measure for image query (as it was first used in [62]) to our knowledge, it has not been used for complete image segmentation nor BPT construction. However, in [57] a simplified version of the EMD is used for corner and junction detection. The EMD distance can be defined with two histograms hand gwith number of bins Nh,Ng. The value for bin i,hi,giis defined to be the probability to observe the color i. Since histograms represent a pdf,PNh i=1 hi= 1, PNg j=1 gj= 1. The problem is how to transform histogram hinto g. That is, some probability mass of hshould be displaced to form g. The amount of probability mass displaced from one bin ito another bin jis represented by a flow fi,j. The unit cost of this displacement is given by ci,j. In Figure 4.20 the graph representing the transformation of hinto gis represented. The mathematical formulation of the 50 4.1. The Merging Algoritm EMD can be written as follows: EMD(h,g) = min fi,j Nh X i=1 Ng X j=1 ci,jfi,j Ng X i=1 Nh X j=1 fi,j (4.1.4) The minimization (4.1.4) has some constraints on the flows fi,j that can be written as fi,j ≥0 (4.1.5) Nh X i=1 fi,j =gj(4.1.6) Ng X j=1 fi,j ≤hi(4.1.7) Equation (4.1.5) simply states that the amount of probability mass moved should be positive. Equation (4.1.6) forces that the flows going to a bin j, sum up to the value in gj. Equation (4.1.7) makes sure that no more than the available probability is displaced from its original bin, hi. The costs ci,j are defined to be the costs of moving a unit of probability mass from a bin ito a bin j. In this project, since the histogram bins are colors, ci,j are the unit costs to transform a color ito a color j. Cross bin costs can be the euclidean distance or a statistical measure. Taking advantage of the CIE Lab color space, the costs proposed in this scheme are perceptual. The distance between one color ifrom histogram hto a color jfrom histogram g(the cross bin cost) is perceptually defined as in equation (3.1.1): ci,j =1−e−∆i,j γ(4.1.8) h1 h2 . . . hN g1 g2 . . . gN Figure 4.20: Graph representing the EMD problem. The arrows represent the flow from/to the bins and the nodes are the bins themselves 51 4. BPT Construction Where ∆i, j is the euclidean distance between colors iand j.γ= 14 is the decay factor. Clearly, this type of problem is a convex optimization problem, and can be solved by linear programming algorithms such as the simplex method. Note that efficient ways to compute the EMD do exist when the costs are linear with respect to the bin distance [65], i.e ci,j ∝ |i−j|. However, since the costs defined in (4.1.8) are not linear, another implementation was used from [64]. The EMD computation is a rather costly operation, but the use of few dominant colors on each region leads to reasonable computational times. As an important fact, the output of the EMD using the defined costs ci,j in (4.1.8), ranges from [0; 1]. The output 1 conforms to two completely equal regions and 0 two completely different ones. The measure used for (4.1.1) for color is then dc(R1, R2) = EMD(h,g) (4.1.9) With h,gbeing the histograms representing regions R1and R2respectivelty. 4.1.2 Shape/Contour Criterion The contour criterion was studied in [52] and the measure was simply the increase of perimeter of the merged region with respect to the region with the largest perimeter. To adapt the contour criterion to the dynamic range of the color distance, the increase of perimeter is normalized to the largest perimeter. Define the length of the perimeters of the two regions R1and R2as P1and P2respectively. The common perimeter is P1,2. The measure is then ds(R1, R2) = max 0,min(P1, P2)−2P1,2 max(P1, P2)(4.1.10) It is important to mention that the contour criterion should only be applied when the shapes of the regions are meaningful. In practice, the contour measure is only applied when the areas of both regions exceed a threshold (i.e. 50 pixels), but other numbers may work as well. 4.1.3 Area Criterion As stated above, the relevant objects in the scene usually have similar sizes. It is then intuitive to introduce a measure to balance these sizes. That is, all the regions at a given iteration of the BPT construction should have approximately the same area. There is no general consensus about the area measure [52]. All of 52 4.1. The Merging Algoritm them, however, are monotically increasing with the region areas. Generally, the measure depends on the dynamic range of the other measures. For the purposes of this project, the area contribution is defined to be da(R1) = log2(1 + min (|R1|,|R2|)) (4.1.11) With |R1|,|R2|being the respective region areas, in pixels. 4.1.4 Depth Criterion One of the local cues that allow to infer some depth relationships between regions are the so called T-junction points. These points appear where three different regions meet. To detect them in our approach, the Region Adjacency Graph (RAG) is used. The RAG is a graph structure where two regions (represented by graph nodes) are connected if their share at least a common pixel edge. At each BPT construction iteration, a RAG is available. T-junctions are potentially located where a region triplet Ri,Rjand Rkis fully connected on this RAG. This also can be seen as Riand Rjhaving a common neighbor Rk. The point where the three regions meet in the image, defines a possible candidate for a T-junction point. Each possible location is characterized with a probability value, measured with a confidence value, 0 ≤p≤1. The computation of this confidence value is described in 4.2. It is clear that two adjacent regions may have more than one T-junction candidate and that each of these candidates may define two different depth planes. Figure 4.21 shows a possible example where the regions Riand Rjhave four T-junctions in common. Note that some of the T-junctions between Riand Rjare also between Riand Rk. The information relying on the T-junction candidates structure is used to modify the distance between two regions. Consider the set of T-junction candidates Tbetween any pair of regions Riand Rj. Following the perceptual cues exposed in Section 5, it is possible to distinguish three kinds of T-junctions RiRj Rk Figure 4.21: Example of two adjacent regions having more that one T-junction (4) 53 4. BPT Construction on the set T. Ones telling that Riis in front of Rj, others telling Rjis in front of Riand finally others telling that some other region is in front of Riand Rj. The first two groups indicate that one of the two regions, Rior Rj, is in a different plane than the other. The last group does not tell anything about the depth order for this pair Riand Rj. However, for the first two groups the information is contradictory as two regions cannot be at the top of each other at the same time. Thus, one of the two suppositions (assuming a constant depth for regions) may not be true. The region depth model considered in this project assumes that no self-occlusion is present in the scene. From the confidence of each T-junction candidate, it is possible calculate the probability that either Rior Rjis in front of the other: pi= 1− Ni Y n1−pi n!Nj Y n1−pj n(4.1.12) pj= 1− Nj Y n1−pj n  Ni Y n1−pi n(4.1.13) Where pi nis the confidence of the n-th T-junction candidate telling that Riis in front. pj nis defined similarly. Niand Njare the number of T-junctions for each group. To understand the previous expressions, an intuitive explanation follows for Ri. The probability of Ribeing in front of Rjis that at least one of the Tjunctions indicating Riis in front is true while all of the T-junctions having Rj in front are false. Since calculating the confidence of a T-junction is not intuitive, Section 4.2 is devoted to carefully explain the process of finding T-junctions pi n values. With these two probabilities, the confidence difference is defined as δ=|pi−pj| and the depth contribution to define the region distance is dd(R1, R2) = 1 1−δ(4.1.14) It should be clear that δ= 1 when the two values piand pjdiffer very much and the depth order is clear. When the two values are close the modifier δis close to zero. This situation appears either when there are no cues that permit to order by depth the two regions or when two T-junctions give contradictory information. During the BPT construction, the similarity measure increases the distance of regions that do not belong to the same depth plane. Thus, the tree is expected to be partially depth-structured. The following section shows how to calculate the confidence values pi nand pj nof each T-junction candidate point. The characteristics to evaluate the confidence 54 4.2. T-Junction Confidence Calculation are based on a local analysis of the color difference, the boundary curvature and the angle distribution. 4.2 T-Junction Confidence Calculation On sections 3and 4.1, the image and regions models used in the construction of the tree were presented together with similarity measures. However, when stating the merging order, a depth criterion was introduced. In this criterion, all the T-junction candidates were represented by a value, called the confidence value p. The goal of this section is to describe how to estimate this confidence value for individual T-junction candidate. 4.2.1 Overall Confidence To calculate this value, three different magnitudes related to low-level features are used: color, angle and curvature. The confidence value pof a T-junction is defined as p= Γ ×Θ×Υ (4.2.1) To calculate p, the three more important features of a T-junction point are used: Γ, Θ and Υ are the color, the angle and the curvature confidences respectively. The following sections show how these values are computed. First, in Section 4.2.2, techniques used for color structure will be discussed. Second, in Section 4.2.3, the angle organization of the branches meeting at a candidate point will be discussed. Third and last, the straightness of the branches will be measured in Section 4.2.4. Although the three features contribute in equal terms to the final pvalue, practice shows that color structure is the most important cue for T-junction classification. In Section 4.2.5, some examples of detected T-junctions are shown, along with their respective confidence values. 4.2.2 Color and Area Although in this project the junction confidence is clearly distributed among three main features, junctions are perceived mainly by their color characteristics. Almost state of the art corner/junction detectors are based on color information. The 55 4. BPT Construction following section outlines the main detectors found in the literature, emphasizing the importance of the color features. 4.2.2.1 State of the Art Junction Detection Color is a key feature when detecting junctions. Most of the approaches consider the junction detection as a particular case of corner detection. Corner detectors are a widely studied topic in image processing. In [66] corners are defined to be points with low self-similarity in the image. Self -similarity between pixels is computed using sum of squares differences between small patches within a neighborhood of the two considered pixels. An improvement of [66] was proposed in [67] by introducing the Harris matrix of a pixel pt: Hpt= < I2 x> < IxIy> < IxIy> < I2 y>!(4.2.2) Angle brackets indicate averaging along a local neighborhood, and Ix,Iyrefer to the image gradients in xand ydirections respectively. The matrix Hpt, also known as a structure tensor, can be used to detect edge and corner points at the same time. Examining the eigenvalues λ1, λ2of Hpt, Harris and Stepehens noticed that: •If λ1≈0, λ2≈0, the pixel ptdoes not have any feature of interest. •If λ1≈1, λ2≈0, the pixel ptis likely to belong to an edge. •If λ1≈1, λ2≈1, the pixel ptbelongs to a corner. Subsequent improvements of this algorithm were based on a multiscale approach, calculating Hptat different resolutions [68]. The work in [69] makes use of the level sets theory [70] considering corners/junctions as points of high curvature. Although there exist several other methods to detect corners such as [71,72,73], they are all mainly based on detecting high variations on the image gradient/curvature. All the above mentioned systems rely directly on the image pixels to detect and localize junctions, however, the approach followed in this project takes advantage of the BPT structure. In this work, since the region boundaries are defined during the BPT construction, the localization of potential junctions is already known. As all corner detection systems, an operator to detect salient points has to be proposed. Rather than operating with the image gradient or the curvature of the level sets, junction strength is computed here using histogram comparison. 56 4.2. T-Junction Confidence Calculation 4.2.2.2 Local Region Model When a T-junction is present in an image at a location pt, its color characteristics may indicate a discontinuity on depth. The analysis of the color characteristics are limited to a local neighborhood Ω (pt). In this local window, the three regions can be modeled with a three dimensional histogram, like the region model for the BPT construction. As in the region model, the 3D histogram is modeled by its n most dominant colors: Ri(Ω (pt)) = {(p1,c1),(p2,c2). . . (pn,cn)}(4.2.3) With i= 1,2,3, Rirefers to each one of the meeting regions at the junction points. c1. . . cnare the ndominant colors for the histogram and p1. . . pnare their respective probability of occurrence. nis fixed to 3 and the representative colors are found by using a k-means clustering approach. The window used for all the calculations is circular with a radius Rof 10 pixels. The choice of this value comes from [15] where the author states that a large window is required to have a robust junction detection. In natural images, junctions may appear in different resolutions/scales. In [74,69] an automatic scale selection algorithm is proposed but, for this project, a fixed window radius proved to be adequate to detect almost all the possible junction candidates. Considered pixels The pixels which are included for color confidence(s) evaluation are the ones which are not neighbors of the other two regions. All the region boundary pixels are discarded to avoid a bias in mean and variance calculation. During the image formation process, optical devices act as low pass filters. Parts of the image such as edges, that contain high frequencies, appear to be somehow blurred. This blurring introduces false statistics during the color characterization of the regions. For this reason, as seen in Figure 4.22, these pixels are discarded for the color characterization. 4.2.2.3 Color confidence The color confidence measure for a T-junction is based on the color difference between the three histograms defined by each region Riin a small neighborhood of a candidate T-junction. The histogram difference is computed with the same distance used in the BPT construction process. Define hii= 1,2,3 to be the histograms of each respective region near the T-junction candidate. Since the measure can only be applied to a histogram pair, a total of three color distances 57 4. BPT Construction 4.2.4 Curvature In physics, a corpse moving on a given trajectory may experience some changes in its direction. These changes are reflected mathematically in a change of the trajectory’s derivatives. The first derivative gives a vector tangent to the trajectory. The faster the object changes its direction, the faster changes the normal vector to the trajectory. The modulus of the tangent vector reflects changes only when celerity changes. Abrupt changes in direction can be characterized by the curvature, defined as the modulus of the normal vector. If the curvature is high, the trajectory of the object will change fast. If it is close to zero, the corpse will follow a more straight movement. Although the definition of curvature was originally thought in the physics domain, it has its own applications in image processing. Stated in [70], it may help to describe the shape of the objects presents in a particular scene. It was originally used in curvature scale space representation [75] and anisotropic diffusion [76]. More recently curvature was also used jointly with the level sets theory [70]. In this project, curvature is used similarly to [70] to measure the straightness of the T-junction branches. In the following sections, a brief summary of the curvature equations and the level sets theory are presented. After the background introduction, the use of curvature for T-junction detection is explained. The work in [4] also uses curvature for T-junction candidate point validation. Similarly, in this work, curvature confidence is calculated to contribute to the overall T-junction confidence. 4.2.4.1 Continous parametric curves To introduce the concept of curvature, first continous domain curves are explained. A curve in the continuous domain <2is represented as c(t)=(x(t), y (t)) (4.2.19) tis a parametric variable and may be defined under an interval t∈[a, b]. The curve c(t) must be of class C2at least, that is, continuous and differentiable over the domain of t. For such a curve, there exists an arc length parametrization of with respect to a variable s,c(s), such that with this parametrization:     ∂c(s) ∂s     2 =∂x(s) ∂s 2 +∂y(s) ∂s 2 = 1 (4.2.20) 64 4.2. T-Junction Confidence Calculation With this definition, the tangent vector to the curve τ(s), the normal to the curve n(s) and the curvature κ(s) are given by: τ(s) = ∂c(s) ∂s (4.2.21) ∂τ(s) ∂s =κ(s)n(s) (4.2.22) κ(s) =     ∂τ(s) ∂s    =    ∂2c(s) ∂s2   (4.2.23) Therefore, the curvature is defined as the modulus of the second derivative of the arc length parametrization of a curve c(t). To define curvature in a discrete domain, as an image is, the discrete version of the previous equations are achieved by means of the level sets theory. 4.2.4.2 Curves on Level Sets Consider a single channel image Iand a pixel p0. Let u(p) be the gray level of the image at a certain pixel p(which can be the gray level or the luminance for example). Conversely, it can be proven that the set of pixels on a level λ,u−1(λ), forms a set of disjoint curves. To a particular curve cof this set it is possible to apply the curvature equations to obtain the curvature. Without loss of generality, from now on a particular pixel p0on an arbitrary level set λis considered. The resulting equations, deduced in [77,70], are briefly summarized here. If the image first order partial derivatives ux, uyalong the xand ydirections are avaiable at a point p0and u2 x+u2 y6= 0. The curvature of the level λis defined as: κ(p) = uxxu2 y−2uxyuxuy+uyyu2 x u2 x+u2 y3/2(4.2.24) Where uxx, uyy and uxy are the second order partial derivatives. Since the image is a discrete domain, the value of the derivatives should be estimated using any of the available techniques such as convolution by a high pass filter. 4.2.4.3 T-Junction Curvature Extraction In this project, curvature is used to discriminate T-junction candidates. The branches of a T-junction should be straight and, if not, the candidate may not be perceived as an occlusion point. The objective of this part of the system is to determine the mean curvature of boundaries of the regions. These boundaries are determined by the region shapes during the BPT construction. In figure 4.27 an example of three regions forming a T-junction is shown. 65 4. BPT Construction Region 1 Region 2 Region 3 Figure 4.27: Example of the curves meeting at a junction point The approach used in this project has a fundamental difference with systems using the Level Sets Theory for image segmentation. State of the art segmentation methods operate with the image itself, while the proposed approach operates with regions created by the BPT. The analysis is limited to a local neighborhood, i.e. a small window, centered on the T-junction point. The main steps to retrieve the curvature on the edges are shown in the following list: 1. Isolate each of the three regions 2. Reconstruct the regions to eliminate interfering pixels 3. Interpolate the resulting image 4. Calculate the mean absolute value of curvature of each region boundaries. After these steps, the values obtained for each edge are combined to form the curvature confidence for this T-junction point. Isolating and Reconstructing Regions The presented method computes the edge curvature defined by the BPT region boundaries. Therefore some transformations are needed before proceeding with the curvature calculation. In a neighborhood of a T-junction there are three edges marking the boundaries between regions. Ideally, one would like to have high gradient points in region boundaries, although in the real image this may not be true. To calculate the curvature of the region boundaries, the proposed approach constructs three binary images, considering only one region at a time. Each image is constructed by setting to 1 the examined (the considered region) points, and 0 to the other two regions. Normally, as shown in Figure 4.28, there can be interfering pixels that may contaminate the curvature estimation. Although the analysis is limited to local window of a fixed size, there can be other regions than those three inside the 66 4.2. T-Junction Confidence Calculation Region 1 Region 2 Region 3 Figure 4.28: Process to calculate the curvature. Left, local window with the three regions and some outliers (diagonal striped pixels, belonging to other regions). Center, binary image with Region 1 isolated. Right, reconstructed image without outliers window, specially in the first steps of the BPT merging process where regions are small. Those regions, although considered as background, may lie very close to an edge contributing wrongly to the curvature estimation. To eliminate the spurious points, a reconstruction from the edges of the region is done. The purpose of the reconstruction process is to eliminate all the transitions but the ones in the examined edges. Following this procedure, all the holes produced by foreign regions are eliminated and the following steps for the curvature estimation can be performed securely. The reconstruction process result is shown in the rightmost part of Figure 4.28, where the outliers are already eliminated. Curvature Computation Once the binary image is available, the curvature for each boundary region has to be calculated. Because the borders lie in-between pixels, the binary image is interpolated. The interpolation is by a factor of 2 and the value of the pixel in the interpolated image is the average of the closest neighbors. The result of the interpolation is used to compute the curvature value for each edge point. For every region, the closest points to the T-junction are discarded, since they may introduce some high curvature for the edges which shall not be taken into account. As for the angle, points lying within a R= 3 pixel radius are discarded. The curvature value in equation (4.2.24) may have positive or negative values, depending on the curvature direction. Since the purpose is to discriminate points with high curvature values, regardless the sign, the averaging is performed over the curvature absolute value. Therefore, the curvature measure for a region κi with i= 1,2,3 is calculated by averaging the absolute value of equation (4.2.24) on the boundary points. 67 4. BPT Construction 4.2.4.4 Confidence Calculation The mean absolute value of the curvature is used to compute a confidence. The resulting measure is considered to Rayleigh distributed. Since the ideal T-junction is a T-shaped image, with three straight branches coming out of the center point, the curvature of each region is expected to be 0. The larger the curvature, the less likely that the center point forms a true T-junction. A similar approach to color and angle to obtain the confidence value is used. The formal expression for the curvature confidence for a given region iis defined as: Υi=e−κi σ2 c(4.2.25) With σ2 c= 0.5. From the three measures Υi, the maximum and minimum are chosen to obtain the final curvature confidence: Υ = 2ΥmaxΥmin Υmax + Υmin (4.2.26) Although the curvature confidence is not as important as color and angle confidence, it mainly helps in discriminating very irregular branches, where the perception of a T-junction is indeed unclear 4.2.5 Examples of estimated T-junctions A few examples of T-junction confidence estimation are shown on table 1. Note that the color confidence is the measure that has the highest relevance of the junction as it is the first feature detected by humans when examining the scene [15]. Angle plays also an important role in perception. When the biggest region does not give a clear occlusion cue, confidence drops rapidly. Curvature is the less sensitive parameter. 68 4.2. T-Junction Confidence Calculation T-Junctions Example Local Window Confidence Value Local Window Confidence Value color 0.84 color 0.73 angle 1.00 angle 0.56 curvature 1.00 curvature 0.39 overall 0.84 overall 0.16 color 0.97 color 0.55 angle 0.66 angle 0.39 curvature 0.80 curvature 0.57 overall 0.52 overall 0.12 color 0.88 color 0.51 angle 0.90 angle 0.25 curvature 0.56 curvature 0.77 overall 0.45 overall 0.10 color 0.77 color 0.19 angle 0.66 angle 0.40 curvature 0.59 curvature 0.57 overall 0.30 overall 0.04 color 0.42 color 0.12 angle 0.54 angle 0.60 curvature 0.79 curvature 0.92 overall 0.18 overall 0.03 Table 1: Examples of T-junctions, ordered in decreasing value of confidence, from top to bottom and left to right. Junctions are marked with a red circle, filled in white is the region lying on top of the other two. 69 5. Depth Ordering 5 Depth Ordering 5.1 Overview: BPT Analysis After BPT construction, a hierarchical representation of image regions is avaiable. From this representation, a set of regions should be extracted and further processed to obtain a depth ordering between them. The overall process consists of mainly two steps Initial T-junction Selection In this first step, from all the T-junction candidates estimations, the most confident ones are selected. With these points, a first pruning of the BPT is performed which serves as starting point for the next algorithm step. The Minimization Process The final depth order is obtained from an iterative minimization process. The input to this process is the first BPT pruning previously obtained. From this points, further processing on the tree is performed to obtain a final depth ordered partition. As illustrated in Figure 5.29, the systems first perform an initial simplification of the created BPT. After that, it enters an iterative procedure that attempts to find the optimal depth ordering of an image. 5.2 T-Junction Candidate Selection Once the BPT is constructed, the tree nodes should be extracted by pruning to contruct a partition of the image representing the various depth planes. Knowing that at the construction process presented in section 4the T-junction points were estimated, this information is used to perform an initial pruning of the tree. This first pruning is performed based on an initial selection of the most confident Tjunction points as explained below. 70 5.2. T-Junction Candidate Selection Figure 5.29: Block diagram of the minimization step of the algorithm During the BPT construction process, all image points are potentially considered as T-junction candidates. At each region merging, every time that any of the three regions forming a candidate changes, the junction properties are updated to the current region configuration. Therefore, during the BPT construction, a T-junction candidate point can be reevaluated many times, as shown in Figure 5.30, until it disappears. Since the BPT stops when only one region is left, all T-junctions gradually disappear. T-junctions disappear when two of the three regions forming it are merged. Figure 5.31 shows how at the final BPT mergings all the T-junctions disappear when regions are merged together. Prior to BPT pruning, some of the T-junction estimations should be discarded for depth ordering. Since each estimation can be identified by a confidence value, only the points with high confidence are kept. When selecting the candidates, it is considered that the last estimate of a point is the one with more reliable features. Figure 5.30: Example of T-junction candidate reevaluation. Since the background and the uppermost region are merged, there are some T-junctions disappearing (red circles) and some reevaluations (white circles). The T-junctions reevaluated are the ones involving the merging regions. Regions are represented by their mean color value. 71 5. Depth Ordering That is, color, angle and curvature structure are more reliable just before two of the three regions forming the T-junction are merged and the junction disappears. This assumptions comes from the fact that at each T-junction evaluation, the regions have increasingly more pixels. Larger areas mean that more accurate and reliable estimations can be done. Therefore, the confidence values used for each T-junction candidate are the values obtained for the last estimation. Since a true T-junctions are assumed to have a high confidence value, the selected T-junctions are the ones that are above some threshold. To decide which threshold to use, an empirical value was manually set. Actually, there are two main criteria to discriminate between T-junctions: •An absolute confidence threshold pth. Good T-junction candidates have high confidence values so, low pvalues are neglected. •A relative threshold, based on the maximum T-junction confidence found in the image, pmax. This threshold is used to make the selection of T-junction as contrast invariant as possible. If the overall image contrast is high, Tjunctions with low contrast are not considered even if their confidence exceeds the absolute threshold. Taking a look at figure 5.32, one can see the effects of setting lower thresholds, i.e. more T-junctions candidates are selected and more false alarms are introduced. While setting high thresholds eliminates false T-junctions produced by texture variations, it keeps almost all the interesting points. The thresholds used are set for each image as pr= 0.2×pmax for the relative threshold and pth = 0.1 for the absolute threshold. Thus, all the candidates that fall below a 20% of the maximum T-junction individual confidence are discarded as well as the ones having confidence values below 0.1. With this threshold, a typical image of 350 ×350 Figure 5.31: From left to right and top to bottom, last mergings of a BPT on a given image. Note that each time a merging occurs, some regions are changed making T-junction points to be reevaluated or, simply, to disappear. 72 5.3. Initial BPT Pruning Figure 5.32: From left to right. Original image and three image partitions obtained from the pruned BPT, varying the final threshold for T-junctions, with thresholds of 0.2, 0.1 and 0.05 relative to pmax. The absolute threshold of pth = 0.1 is kept constant in the three images. pixels would finish with 10-25 possible points. A typical image contained 5-6 true junction points so, it is expected that among the initial selection, the true candidates are present. 5.3 Initial BPT Pruning After the initial T-junction candidates are selected, the initial BPT pruning is obtained by defining the minimum number of regions that preserves the selected T-junction coordinates. To achieve this pruning, an iterative algorithm is proposed. From the initially constructed BPT, a set of regions/nodes are pruned to obtain a simplified tree. Some of the initial regions to be pruned are the ones forming the selected T-junctions. The Pruning Algorithm Each final T-junction candidate is formed by 3 regions. Due to the hierarchical nature of the BPT, it is possible that the regions forming T-junction tkare contained in some of the regions of a candidate ti. That is, some of the regions of candidate tiare the parent regions of regions of candidate tk. This situation is shown in the left tree in Figure 5.33. The containing candidate tiis formed by the three blue regions. tkis formed by the red regions, but two of them are descendants of a blue region. If such situation is encountered, the coordinates of tkwill be contained inside one of the regions of ti. Clearly, one of the blue regions is masking the coordinates of the T-junction tk. If coordinates tkshould be preserved, the regions of tishould be changed. Since the candidate tihas been reevaluated many times during BPT construction, the regions forming one of its previous estimates can be used as new candidate t0 i. If the new candidate is properly chosen, no containing regions between tkand t0 iare found and the coordinates of both points are preserved. This process is shown in the center tree of Figure 5.33, where the blue candidate is changed to one of its previous estimations so that no marked regions are contained in any other. 73 5. Depth Ordering 5.4.2.2 Convexity Reasoning When measuring convexity, it is commonly agreed that convex objects seem to be in front of the concave ones [17,16]. Therefore, convexity and occlusion are two depth cues. Although there are many Gestalt theorists that state that occlusion cues are stronger than convexity, in this work, it is assumed that both types work together for the reconstruction of a scene. Therefore, convexity relations between regions is considered to be as important as occlusion cues. Human vision and, consequently, depth interpretation of a scene, is a brain’s global reasoning coming from detected cues and (possibly) prior learned information. Vision, according to the Gestalt theory [80], is a joint collaboration of perceived cues. Following the same principles, in this work we assumed that both convexity and junctions help in equal terms to the scene depth interpretation. Evaluation of convexity depth cues is performed on the leaves of each generated BPT by the algorithm in Section 5.4.2.1. Technically, since the BPT is a hierarchical representation and a region can be adjacent to many nodes in the tree (not only the leaves) convexity could be measured between all the BPT levels. Exploring all the adjacencies would be unpractical due to the high computational cost of the process. Convexity Computation Convexity depth cues are defined locally for boundaries between pair of regions. A region R1is convex with respect to R2if, on average, the curvature vector on the common boundary is pointing towards R1. If R1appears to be convex, it is perceptually seen as the foreground region (and thus, closer to the viewer). Generally, when examining boundary pixels, if R1presents less area than R2in a local neighborhood, R1may be seen as convex. Figure 5.38 Figure 5.37: Example of convexity. Left: original image with the segmentation overlaid. Right: possible partition with convexity cues showed. Points of high curvature/convexity are cues to determine the relative depth. Convexity should be averaged to decide the correct sign of convexity. 80 5.4. Depth Reasoning illustrates this concept. Formally, the overall boundary convexity is obtained from the combinations of two measures: ζc(R1, R2) = 1 LX (x,y)∈Γ α(x, y) (5.4.5) ζb(R1, R2) = 1 LX (x,y)∈Γ w(x, y) (5.4.6) With Lbeing the length of the contour. α(x, y) = 1 if the area of R1is greater than the area of R2in Ω(x, y), α(x, y) = −1 otherwise. The function α(x, y) is a simplification of the convexity measure of [17]. The function 0 ≤w(x, y)≤1 is a weighting function of the contour points and it is chosen to be the normalized Sobel gradient of the image, although other gradient operators work too. Lis the number of points where the measure α(x, y) is calculated. The overall convexity confidence of a boundary is: ζ(R1, R2)=1−exp ζc(R1, R2)×ζb(R1, R2) γc(5.4.7) With γc=1 12 determined experimentally. If the result ζc(R1, R2) is positive, R1 is considered to be convex and, therefore, on top of R2. The converse indicates that R2is on top of R1. To make the measure as scale invariant as possible, the neighborhood Ω(x, y) of a pixel is chosen to be a circle of radius equal to 5% of the contour length. Points lying near junctions, image borders and other regions are discarded for the measures. Contours having small lengths L < 100 points are considered to be non-significant for convexity cues. Figure 5.38: Convex regions, R1, have less area (marked in light blue) in discs at the boundaries with their adjacent regions, R2. The less the area is, more convex R1appears to be. 81 5. Depth Ordering 5.4.2.3 Depth Order Graph Construction When the final regions are available, there are two sets of depth cues that may contribute to determine the relative depth order between regions. T-junction and convexity cues should be combined to determine the final relative depth order. The depth order defined by T-junctions is different from the proposed scheme in [81]. As said in Section 1.1, T-junctions indicate a discontinuity on depth but the order information is not straightforward. Instead, it has been found by examining ground truth junctions in the segmentations of the BSDS5000 dataset [82] that the local depth order of a T-junction depends on the angle configuration of other T-junctions. If the same region Ris seen more than once forming the largest angle, the T-junction is likely to define the normal depth order (the foreground region is R), as in [4]. If the largest region is only seen once forming the largest angle, the depth order is, a priori, inverted (Ris the background). Convexity depth order is clear in this proposed scheme: the convex region is seen as the figural region. Since the computed cues are merely local, a more global reasoning should be done to arrive at a consistent solution for the whole image. To do so, a Depth Order Graph (DOG) is constructed. Nodes in the graph represent regions of the partition extracted from the BPT. The depth relations are represented in the graph by directed weighted edges, going from the foreground region to the background one. Once all the edges are defined, a directed graph is obtained like the one illustrated by Figure 5.39. A depth cue characterizes the relation between one (or more, in case of T-junctions) pair of nodes. If the cue confidence relating node Ri and node Rjis p, the directed edge weight is pij =p. Since the perception of depth involves the interpretation of (sometimes) conflicting cues, the DOG may also present these conflicts. A depth conflict occurs when, due to a set of depth cues, a region can be on the top of itself. If that is the case, two regions exist, R1and R2, which are at the top of each other at the same time making depth ordering impossible.These conflicts are identified as cycles in the DOG. That is, if one can find a cycle in the graph, all the regions belonging to the cycle are classified as incompatible between them. The main idea of conflict resolution is to modify/eliminate depth cues with low confidences to achieve a direct acyclic graph. To do so, a global reasoning of all the cues is performed using the principles of Network Reliability computation [83]. The DOG is a graph with edge weights representing probabilities of precedence. That is, if only two nodes Riand Rjwere present in a DOG, and these nodes were connected by a single edge eij with weight p; the probability that node Ri 82 5.4. Depth Reasoning Figure 5.39: Directed graph constructed from the depth cues. Labels on the edge represent their strength. The conflict formed by the loop R2←→ R3may be eliminated by deleting the red edge. precedes Rj(the node Riis in the foreground) would be p. In practice, more than one node and more than one edge form a DOG. The DOG can be seen equivalently as a network of reliable links [83] and the reliability between two nodes, in the proposed case, is called probability of precedence (PoP). The overall goal of this step is to perform a global reasoning of the DOG to eliminate cycles for a posterior depth ordering. To this purpose, the following solution is proposed: 1. Compute the PoP for every pair of regions (nodes), Riand Rj. That is, the probability that Riis foreground with respect to Rj,ρij. 2. Examine all pairs ρij and ρji. If a cycle is present, both Riand Rjcan be foreground and, therefore, both ρij, ρji 6= 0. 3. In case of conflict, modify one of the paths from Rito Rjor vice versa to eliminate the cycle. Probability of Precedence Computation To Compute the probability that a region Riprecedes Rjall the paths going from the former to the latter should be considered [84]. Since edge weights represent the confidence of precedence between pair of directly connected regions (two regions Aand Bare directly connected if there is an edge from Ato B), this reasoning can be used to calculate the probability of precedence of two non-directly connected regions. Simple rules exist to compute ρij when graphs have special topologies. Single Path If only a single path Pqexists: ρij =p(Pq) = L Y l=1 pl,l+1 (5.4.8) 83 5. Depth Ordering Where Lis the number of edges forming the path and pl,l+1 is the weight of the edge connecting the nodes land l+ 1 on the path Pq. Equation (5.4.8) shows that the PoP of node Rito a node Rjwith respect to Pqis just the joint probability of all the edges forming Pq. That is, for a node Ri to precede Rj, all the edges in a path Pqshould be reliable. Multiple direct edges If there exist NEedges between Riand Rj,ρij is the probability that at least one edge is reliable: ρij = 1 − NE Y l=1 (1 −pl ij) (5.4.9) Where pl ij is the l-th weight of the edge connecting Riand Rj General Topology If a set of NPpaths connect Riand Rjthe PoP ρij is the probability that at least one of these NPpaths is reliable. This probability can be calculated by the inclusion-exclusion principle: Sk=X 1≤i1<...<ik≤NP p(Pi1\Pi2\···\Pik) (5.4.10) ρij =p( NP [ i Pi) = NP X k=1 (−1)(k−1)Sk(5.4.11) To illustrate a simple example of the inclusion-exclusion principle, ρ13 is computed for the DOG in figure 5.39, not including the red stripped edge. Only two paths going from R1to R3are found, passing both through nodes R1−R2−R3. The edge weights forming these paths are P1: (p1, p3) and P2: (p2, p3). The PoP of R1to R3is defined according to (5.4.11), for this particular case, as: ρ13 =p(P1∪P2) = p(P1) + p(P2)−p(P1∩P2) (5.4.12) That is, ρ13 is the probability that at least one path is reliable between R1and R3. The terms p(P1) = p1p3and p(P2) = p2p3are the probabilities that a given path is reliable. The term p(P1∩P2) = p1p2p3is the probability that both paths are reliable at the same time. Therefore: ρ13 =p(P1∪P2) = p1p3+p2p3−p1p2p3(5.4.13) In an arbitrary large graph, the inclusion-exclusion principle is not feasible, since its computation cost is exponentially proportional to the number of paths. Instead, the proposed algorithm is an approximation giving an upper bound for all the pairs of nodes. To approximately compute ρij with more than one path between nodes, 84 5.4. Depth Reasoning consider that there are only three nodes Ri,Rjand Rkand that ρij and ρjk are already known. Moreover, assume there is a direct edge from Rito Rkwith strength pik. An approximate PoP of node Rito Rkis then given by equation (5.4.9): ρik = 1 −(1 −ρijρjk)(1 −pik) (5.4.14) Equation (5.4.14) is only valid if all the paths connecting Ri,Rjand Rkare independent, although this assumption is not fulfilled in most of the practical cases. The problem of (5.4.14) resides in computing the values ρij and ρjk which were assumed to be known. It is possible to iteratively compute ρij for paths of shorter length and sequentially increase the path length. This process is performed using a modified FloydWarshall algorithm [85]. If the DOG contains any cycle, the path length may be infinite so, for practical reasons, the maximum path length is assumed to be the number of nodes on the DOG. The computation of all the pairs ρij leads to a new graph which is the transitive closure of the DOG, the DOG+. The transitive closure of a graph Gis a graph G+with the same nodes of G.G+contains a direct edge (possibly weighted) from node Rito Rjif there exists a path Pqin Gthat connects both nodes. In the case exposed here, the transitive closure of the DOG contain edges with weigths ρij. The graph G+allows to detect cycles easily as paths with arbitrary lengths are reduced to direct edges. It is known that identifying all cycles in a graph Gis an NP problem [86], meaning that there is no efficient solution. Instead, making use of G+, cycles can be detected easily by direct comparison of ρij and ρji. The building of the DOG+is illustrated for the graph of Figure 5.39. The probability of precedence between nodes is shown in table 2: The transitive closure DOG+of the corresponding DOG is shown in Table 2as Adjacency Matrix form. Clearly, there is a conflict between nodes R2and R3since ρ23 6= 0 and ρ32 6= 0. Conflict Resolution If a cycle is found, no depth ordering of the nodes is possible. Therefore, some edges should be removed. A conflict may occur mainly because of two factors. The first may be because some false alarms have been introduced in the final T-junction candidate selection and/or in the convexity reasoning. The second may be because self occlusion actually exists in the image. Assuming that self-occlusion is rather difficult to find in natural images, the conflicts are said to come from bad depth cue selection. The conflict resolution iteratively seeks the minimum ρij of all the pairs of nodes 85 5. Depth Ordering -R1R2R3 R10ρ12 = 1 −(1 −p1)(1 −p2)ρ13 = (1 −(1 −p1)(1 −p2))p3 R20 0 ρ23 =p3 R30ρ32 =p40 Table 2: Adjacency matrix representing the transitive closure of the graph in 5.39. The non-zero terms are shown as ρij. The graph representation is shown at the bottom causing a cycle in the DOG. Each time a conflict is found, either ρij or ρji must be wrongly estimated. Following an intuitive approach, the less confident depth cues should be eliminated. Therefore, the minimum of the two PoP values is considered to be wrong. Therefore, assuming that ρij < ρji, some modifications on the paths that go from Rito Rjshould be done by deleting or turning some edges (and thus possibly breaking the cycle). For each path Pqfrom Rito Rj, the cue with lower confidence forming Pqis identified and modified, depending on its nature: Convexity Cue: The cue is considered to be wrong and the corresponding edge is eliminated T-junction Cue: According to the depth perception principles, exposed in section 1.1, the depth order indicated by a T-junction is not clear. Therefore, Figure 5.40: Conflict resolution for the graph in Figure 5.39. At left, the remaining graph resulting from the deletion of the edge p4. At right, the conflict is resolved by turning edge p4. Both solutions are feasible, depending on the nature of the cue represented by the edge with weight p4. Either case, the remaining graph is a DAG. 86 5.4. Depth Reasoning if the T-junction depth order has not been modified before, the occluding side is changed, inverting the depth order relationship and turning the edge’s inward and outward nodes. If it was modified before, the cue is considered wrong and it is deleted with the corresponding edges. Each time a modification to the DOG is done, the transitive closure is recomputed, until no cycles are found and a DAG is obtained. Possible solutions of conflict resolution for the graph in 5.39 are illustrated in Figure 5.40. 5.4.2.4 Depth Ordering When all the conflicts are removed from the DOG, no cycles are present. Moreover a DOG should have a unique order for its nodes. To order the nodes on the DOG, a topological partial ordering is proposed. This ordering is a linear ordering of a graph’s nodes in which each node comes before all nodes to which it has outbound edges. That is, if node N1has an outbound edge to node N2,N1will precede N2 in the sorted list of nodes, N1< N2. Since in a depth image, two different regions may have the same depth order (i.e. do not have any depth relationship between them), the relation N1=N2should also be considered. A typical way to represent the partial order of a graph is known as the Hasse diagram, shown in Figure 5.41. In this representation, the graph is draw with nodes having low order at the top, while at each level the nodes corresponding to that order are drawn at the same height. R169390 R170094 R170100 R170090 R170104 R169915 R170035 R170079 Figure 5.41: Hasse representation of a graph. The top nodes have the lowest partial order. At each lower level, the partial order is increased. 87 Part III Results and Conclusions 89 6. Results 0 5 10 15 20 25 30 35 40 45 −70 −60 −50 −40 −30 −20 −10 0 PSNR [dB] Error [dB] Figure 6.45: Error in dB encountered in T-junctions with a window radius of 10 pixels. 6.2 Results on natural images In this section the performance of the system is assessed on natural images. Two main kinds of evaluation are performed: objective evaluation on figure/ground labeling and subjective/qualitative evaluation on depth ordering. The former class uses a ground truth subset of the database presented [87]. Using the ground truth labels allows to examine natural scene statistics on figure/ground organization, proving the validity of the chosen occlusion cues. Depth ordering is evaluated qualitatively against state of the art result, as no ground truth data was available. 6.2.1 Benchmark on figure/ground labeling Depth order estimation results can be seen also as a solution to the boundary ownership problem. At the depth region boundaries, the region owning the boundary is considered to be the one lying closer to the viewer. However, when examining ground truth figure/ground labellings on an image, sometimes the figure regions may not coincide with the real 3D structure of the image, according the guidelines of the labeling process [17]. That is, often humans identify as figure regions the objects which are perceptually more relevant, discarding the depth structure. Nevertheless, to evaluate the system results, it is assumed that figure/ground labellings at boundaries agree mostly with the depth structure of the image. To assess the system performance, the figure/ground labelings on contour points should be extracted. Since figure regions are considered to be the ones lying closer to the viewer, boundary points belonging to the nearest region are considered to be figure. Contour points lying on further regions are considered to be ground as shown 96 6.2. Results on natural images in figure 6.46. 6.2.1.1 Results on Ground Truth Segmentations Although the proposed system is capable to jointly obtain a segmentation and a depth ordering for the regions, it is possible to assess the performance of the system when an initial segmentation is available. This test does not evaluate the segmentation quality obtained from the BPT, but only the depth ordering step. Performing such evaluation permits to compare the proposed system to state of the art figure/ground labeling systems. In Section 4the BPT construction began with pixels as the initial regions. Instead, to introduce human marked regions, the starting regions of the algorithm are set according to the predefined segmentations in the BSDS500 dataset [82]. This dataset was built to provide good human segmentations, and a subset of 200 images have also figure/ground labeling, which makes it the best candidate to test the algorithm results. Figure 6.47 shows some of the given segmentations. For each image, the ground truth figure ground labellings were performed by two different subjects according to a given segmentation. Since subjects react differently to some of the boundaries, the considered contours are the ones which are commonly agreed. Taking into account all the labeled contours on all the images, the agreement was about 88%. That is, 88% of the pixels in contours were equally labeled by both subjects. First, the performance of simple T-junction and convexity classifiers are assessed. Second, the performance of the system is evaluated, considering T-junctions only, convexity only and both depth cues at the same time. Results show that the integration of both cues helps to retrieve more accurate depth orderings than using individual cues. Figure 6.46: From left to right. Original image, depth estimation results and figure/ground labeling on contours. In the depth order image, white regions are closer to the viewer. In the figure/ground labels, white pixels belong to the foreground region, the black belong to the ground region. Gray pixels are unassigned because they don’t lie on a depth contour. 97 6. Results Figure 6.47: Original images (color) and their human-marked segmentation (gray level). Each region is colored with a different gray level. To evaluate the performance of the different depth cues, several tests were performed. T-junction Classification Performance With the ground truth segmentations, T-junctions are examined at each intersection where 3 regions meet. Each one is characterized to be normal if the largest angle region is closer to the viewer and inverted if it is not the case. Figure 6.48 shows the probability of each type of T-junctions encountered on the ground-truth segmentations, according to the number times the largest region is seen forming the largest angle in other T-junctions. If a region is seen as the largest region at several T-junctions, these T-junctions are more likely to be normal. For instance, if the same region is seen forming the largest angle in few T-junctions, the T-junction is likely to be inverted. More important, if only a single T-junction is telling a region is at the top, the T-junction is most likely to be inverted. Therefore, when examining a ground truth T-junction, it is considered normal if the region forming the largest angle is seen more than once as the largest. It is considered inverted otherwise. Applying the mentioned criteria, the depth interpretation on ground truth T-junctions is correct 63% of the times. If no inverted T-junction had been considered as in [4], the system would only be correct 57% of the times. 98 6.2. Results on natural images 0 2 4 6 8 10 12 14 16 18 20 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Number of times the largest region is at the top Probability Normal Tïjunctions Inverted Tïjunctions Figure 6.48: Probability of occurrence of normal and inverted T-junctions, depending on the number of times the largest region is at the top of other T-junctions. Convexity Performance Convexity relations are examined along all the ground truth contours. Two measures are proposed to assess the performance of the convexity depth cue. The first measure is a local measure for each contour point, proposed by [17]. The second measure integrates the local measures into a whole contour. First, for each contour point (x, y) the local measure is: K(x, y) = log a1 a2(6.2.1) a1and a2stand for the areas of the two regions R1and R2involved in the contour point in a local circular neighborhood Ω(x, y). If R1is convex (considered, a priori, to be the foreground region), K(x, y) has negative sign. Notice that choosing which of the two regions forming a contour act as R1and R2(and thus a1,a2) is completely arbitrary. Therefore, K(x, y) can be positive or negative, depending on the order in which the regions are considered. Since a1and a2can be changed, each contour point can be assigned two values of equal value but opposite sign [17]. To verify that the measure (6.2.1) may give insights about occlusion cues in contours, this measure is computed on all the ground truth labeled contour points. The same experiment than in [17] is performed. For each labeled contour point, R1can be the either foreground region or the background. It is then possible to find the probability that R1is figure/ground depending on the values of K(x, y). The estimated probabilities are shown in Figure 6.49. For each contour point, if a single decision had to be done according to K(x, y), one would choose R1as figure if the log ratio is negative and ground if it is positive. This classifier is the basis of the proposed convexity measure in Section 99 6. Results 0 0.5 1 1.5 2 2.5 3 ï50 ï45 ï40 ï35 ï30 ï25 ï20 ï15 ï10 ï5 0 Radius 5% 10log10 Probability 0 0.5 1 1.5 2 2.5 3 ï50 ï45 ï40 ï35 ï30 ï25 ï20 ï15 ï10 ï5 0 Radius 10% 0 0.5 1 1.5 2 2.5 3 ï50 ï45 ï40 ï35 ï30 ï25 ï20 ï15 ï10 ï5 0 Radius 15% Ground Figure Figure 6.49: Probability for R1to be the foreground region (green) or the background region (blue) depending on the value K(x, y). The radius of the neighborhood Ω(x, y) is set to 5,10 and 15% of the contour length. Clearly, if log a1 a2is positive, R1is more likely perceived as ground. 5.4.2.2. The decision of this classifier is correct on 61.2% of the contour points, with a window size of 15% of the contour length. That is, the local figure/ground decision was correct at 62.1% of the contour points. A similar performance is obtained in other local convexity classifiers [5,7,17]. As a second performance measure, for each contour cdetermined by R1and R2, the proposed measure is the following: ζ(c) = X (x,y)∈c sign (K(x, y)) (6.2.2) The measure (5.4.6) in Section 5.4.2.2 is strongly related to ζ(c). Similarly to (6.2.1), one would choose R1as the foreground region if ζ(c) is negative or background if ζc is positive. This proposed measure along boundaries and deciding depending on the sign of the final measure, yielded a performance over a 74.2%. This result is obtained by counting the number of correct decision on contours, weighting the decision by the length of each contour. Clearly, integrating the local measure along contour points, greatly improves the performance. Integration of the cues In the previous paragraphs, the performance of simple classifiers was analyzed over contours and junctions. Since the system makes use of these classifiers, the performance of the system is assessed by including them separately and at the same time. Therefore, the system is run considering only T-junction depth relations, only convexities and both cues at the same time. The input of the system is the original image and a given ground truth segmentation. Its output is the corresponding depth ordering of the regions and the figure/ground labeling on contour points. 100 6.2. Results on natural images If the automatically labeled contour points are compared with the ground truth labels, the performance of the system can be computed. Performance of a system considering only T-junction depth order relations was about 61.2% on contour points. Taking into account only convexity depth relations, a performance of 73.2% is achieved. This decrease in performance over the 74.2% of the convexity classifier, proposed in equation (6.2.2), could be mainly due the conflict resolution step, forcing a global consistency on the image. If both cues are used at the same time, an overall performance of 78.2% is achieved, similar to the 78.3% reported in [5]. Additionally, to verify the minimization process and the energy minimization criterion, the following test was performed. Among all the solutions generated during the minimization step, the solution that matched best the ground truth labeled contours was picked, regardless of its cost (5.4.1). This yielded a performance of 84.4% on all the contours, much better than the 78.2% obtained with the minimum cost criteria. Examples are shown in Figure 6.50. These results show that the system performs very similar to the state of the art algorithms, and may generate an accurate ordering of the depth planes if a good segmentation is found. However, there is room for improvement, as picking this best solution may be a more complex problem than calculating an energy function. Table 4summarizes the different performances using human segmentations. Results in [6] show better performance on human marked segmentation, possibly because more cues are used in the figure/ground decision. In practice, however, the ground truth segmentation is not available and the system should compute it. Results with automatic segmentations are commented in the next section. Self [5] [6] Junction Performance One Kind 57.3% Two Kinds 63.0% Convexity Performance Point Based 61.2% 55.6% Contour Based 74.2% 72.0% System Performance Convexity 73.2% - 71.4% Junctions 61.2% - 70.2% Conv. + Junc. 78.2% 78.3% 82.1% Table 3: Results of the figure/ground labeling on ground truth segmentations, compared with the state of the art. First two rows refer to the classification rate of the individual classifiers. The last row shows the performance of the systems 101 6. Results Figure 6.50: Left: Images with contours overlaid. Green contours are correct assignments of figure/ground and red are incorrect. Right: depth order representation of the regions. White regions are closer to the viewpoint, while black regions are further away. 6.2.1.2 Results on Automatic Segmentations To evaluate the results, a similar matching than in [5,6] is performed on region contours. Is is assumed that it exists some uncertainity on the location of the boundaries. Therefore, the shape of the ground truth contour may not coincide with the detected by the algorithm. To evaluate the ground truth labels on automatic generated contours, each detected contour pixel is matched to a ground truth contour point having the same orientation. That is, horizontal/vertical contour points are matched accordingly. This matching is performed within a small window. The amount of uncertainty allowed may be very arbitrary. Where boundaries are very close together, big displacements shouldn’t be tolerated but, when boundaries are blurred and the location is not clear, small displacements could be insufficient. Hence, the size of the window, which is basically the maximum displacement that a pixel can have, was varied from 1 to 4. Results were reported in Table 4. The results obtained can be compared with results of the state of the art for automatically generated boundaries. The results should be looked with skepticism, as differences in the matching process can lead to slight differences in the performances. The proposed system, however, performs similarly to the state of the art 102 6.2. Results on natural images Allowed displacement 1 2 3 4 Results 71.28% 73.23% 75.16% 76.72% Table 4: Percentage of correct assigned figure/ground labelings on contour points, depending on the maximum displacement allowed. as can be seen in Table 5. The system outperforms [5],[6] for automatically generated boundaries. The reported results of [2] did not use the same dataset than the proposed system so, no fair comparison is possible. However, their results are close 80 % of correctness, but using much more information than our system. For instance, the system presented in [2] makes use of semantic estimated labellings on surfaces. If these labellings are not used, their performance is about 68.2%, showing that the algorithm relies very much on high level information. The performance obtained is similar to the current state of the art for figure/ground segregation. Figures 6.51 and 6.52 show some of the results on the BSDS500 dataset, with the detected T-junctions, the depth ordering result and the corresponding figure/ground labels on contours. There is, however, one major difference. In [5,6] the figure/ground labeling systems operate only on boundaries, discarding region information. The proposed approach retrieves instead these labelings from a previously obtained segmentation. In [7], as in the proposed system, figure ground and segmentation are done jointly. A system that retrieves the figure ground labelings at region boundaries is capable to resolve depth conflicts. These depth inconsistencies cannot be detected if the approach is based only on boundaries. 6.2.2 Comparison to the state of the art in Depth Ordering Systems in [1,8] can be compared with the proposed algorithm. Both systems are learning based, therefore, before testing, they should be trained with part of Algorithm Proposed Algorithm [5] [6] [8] Results 71.28% 68.9% 69.1% 79.9% Table 5: Percentage of correct assigned figure/ground labeling on automatically generated contour points. The result of the proposed system is the minimum found in Table 4. Results in [8] are from another database, not the BSDS500 used in the other experiments. 103 6. Results Figure 6.51: Results on depth estimation and figure/ground assignment on some of the BSDS500 images. From left to right, for each column: original image with marked T-junctions, depth estimation and figure/ground boundaries. For T-junctions, black T-junctions are inverted and white are normal. the ground truth database. The comparison, however, should be done carefully, noting that previously cited works estimate the absolute depth of the image, while the proposed approach only offers the relative depth order. Despite the differences, both results can be compared by looking at the major structure of the final depth image. Results in Figure 6.53 show that the proposed system offers much clearer boundaries in most of the cases. However, [1] and [8] permit arbitrary surface orientation, leading to smooth depth gradients which our system is unable to obtain. Note also that most of the learning based results present the same general image structure, being the lower regions the ones that normally are closer to the viewer, specially in [1]. This can be a drawback if non-typical pictures are presented to the system as the algorithm will try to fit the learned model into the input image. Of course, 104 6.2. Results on natural images Figure 6.52: More results on the BSDS500 dataset. For each column (3 images) and from left to right: original image with marked T-junctions, depth estimation and figure/ground boundaries. the white marked T-junctions are normal or black if they are inverted. this can be overcome by a more extensive training dataset but the variety of scenes that must be presented may turn this process unfeasible. Our algorithm does not make assumptions on the type of image and relies only on low-level information.Obviously, trusting only pixel information, without any previous knowledge of the scene can be limiting, but it also has its positive points. For instance, the input of the system can be arbitrary images, assuming always that some kind of considered occlusion cue is present. This makes the algorithm work in more situations such as a landscape, an office or a portrait. Such examples can be found in Figures 6.54 6.55 and where a variety of scenes are presented. Some of these scenes were downloaded from the Internet, some were taken with a camera and some others are from the test part of the BSDS500 database. The system also presents some weaknesses. First, there may exist some low level cues which do not conform with the assumed model. This case is specially seen in T-junctions in textured regions, and where convexity does not offer a good depth cue (take, for example, holes). Second, the constant depth model for each region can be limiting for some applications, as all the surfaces of the scene are considered to be parallel to the camera view plane. If a complete depth map has to be retrieved, this model is insufficient since it does not permit to have oriented surfaces which can indeed exist in normal situations. However, for many applications, depth ordering can be sufficient. For instance, if depth ordering is available, with some little user interactions, an approximate depth map may be available. These kind of limitations of the system are exposed in Figure 6.56. 105 7. Conclusions •The depth region model could allow a flexible surface orientation, having smooth depth gradients and not only depth discontinuities. Surface orientation may be estimated with state of the art techniques [8,23,29] and further integrated with the occlusion detection. •Adopting a low-level learning approach to avoid the current system limitations. Results show that a scene structure learning is a too-ambitious model for the infinite number of situations possible, but focusing the efforts on a low-level scheme (such as contours, junctions) could lead to better cue classification. •Introducing more depth cues. For example, systems such as [88,89] makes use of haze to recover original images. Since haze is a function of the image depth, the structure of the image could also be recovered. Furthermore, the proposed system could also be applied to other computer vision areas, such as multiple view or video. Monocular depth perception may help the other image processing fields by introducing some depth cues to improve the overall depth image estimation. For example, multiple views and temporal image sequences could make use of occlusion to recover high discontinuities in depth maps. Some state of the art algorithms in this field try to recover depth maps under the supposition of depth smoothness. By introducing occlusion cues, discontinuous depth maps could be easily recovered. 112 Part IV Bibliography 113 Bibliography Bibliography [1] A. Saxena, A. Ng, and S. Chung, “Learning depth from single monocular images,” Neural Information Processing systems (NIPS), vol. 18, 2005. [2] D. Hoiem, A. A. Efros, and M. Hebert, “Recovering occlusion boundaries from an image,” International Journal of Computer Vision, pp. 328–346, 2011. [3] B. Liu, S. Gould, and D. Koller, “Single image depth estimation from predicted semantic labels,” in Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, pp. 1253 –1260, 2010. [4] M. Dimiccoli, Monocular Depth Estimation for Image Segmentation and Filtering. PhD thesis, Universitat Politecnica de Catalunya, 2009. [5] X. R. Charless, X. Ren, C. C. Fowlkes, and J. Malik, “Figure/ground assignment in natural images,” in ECCV, pp. 614–627, Springer, 2006. [6] I. Leichter and M. Lindenbaum, “Boundary ownership by lifting to 2.1d,” in IEEE ICCV’09, pp. 9 –16, 2009. [7] M. Maire, “Simultaneous segmentation and figure/ground organization using angular embedding,” in ECCV (2), pp. 450–464, 2010. [8] D. Hoiem, A. N. Stein, A. Efros, and M. Hebert, “Recovering occlusion boundaries from a single image,” in IEEE Int. Conf. on Computer Vision ICCV 2007, (Rio de Janeiro, Brazil), pp. 1–8, Oct. 2007. [9] H. v. Helmholtz, Handbuch der physiologischen Optik [microform] / bearbeitet von H. von Helmholtz. L. Voss, Leipzig :, 1867. [10] G. Berkeley, Philosophical works : including the works on vision / George Berkeley ; introd. and notes by M. R. Ayers. Dent ; Rowman and Littlefield, London : Totowa, N.J. :, new ed., rev. and enl. ed., 1975. [11] D. Marr, Vision : a computational investigation into the human representation and processing of visual information / David Marr. W.H. Freeman, San Francisco ; New York :, 1982. [12] S. Steinman, B. Steinman, and R. Garzia, Foundations of Binocular Vision: A Clinical Perspective. McGraw-Hill Medical, 1 ed., June 2000. [13] D. Raczkowski and M. Cartmill, “Primate evolution: Were traits selected for arboreal locomotion or visually directed predation?,” Science, vol. 187, pp. 455–456, Feb. 1975. [14] D. Waltz, “Understanding line drawings of scenes with shadows,” in The Psychology of Computer Vision (P. Winston, ed.), pp. 19–91, McGraw-Hill, 1975. [15] J. McDermott, “Psychophysics with junctions in real images,” Perception, vol. 33, no. 9, pp. 1101–1127, 2004. [16] J. Burge, C. C. Fowlkes, and M. S. Banks, “Natural-Scene Statistics Predict How the Figure-Ground Cue of Convexity Affects Human Depth Perception,” J. Neurosci., vol. 30, no. 21, pp. 7269–7280, 2010. 115 Bibliography [17] C. C. Fowlkes, D. R. Martin, and J. Malik, “Local figure-ground cues are valid for natural images.,” J Vis, vol. 7, no. 8, p. 2, 2007. [18] M. Bertamini, J. Martinovic, and S. M. Wuerger, “Integration of ordinal and metric cues in depth processing,” Journal of Vision, vol. 8, no. 2, 2008. [19] D. D. Hoffman and M. Singh, “Salience of visual parts.,” Cognition, vol. 63, pp. 29–78, Apr 1997. [20] M. L. Braunstein, D. D. Hoffman, and A. Saidpour, “Parts of visual objects: an experimental test of the minima rule.,” Perception, vol. 18, no. 6, pp. 817–826, 1989. [21] K. Siddiqi, K. J. Tresness, and B. B. Kimia, “Parts of visual form: psychophysical aspects.,” Perception, vol. 25, no. 4, pp. 399–424, 1996. [22] Y. Lee, S. Lee, A. Shamir, D. Cohen-Or, and H.-P. Seidel, “Mesh scissoring with minima rule and part salience,” Comput. Aided Geom. Des., vol. 22, pp. 444–465, July 2005. [23] R. Zhang, P.-S. Tsai, J. Cryer, and M. Shah, “Shape-from-shading: a survey,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 21, pp. 690–706, Aug 1999. [24] D. A. Kleffner and V. S. Ramachandran, “On the perception of shape from shading,” Perception & Psychophysics, vol. 52, pp. 18–36, 1992. [25] J. J. Atick, P. A. Griffin, and A. N. Redlich, “Statistical approach to shape from shading: Reconstruction of 3d face surfaces from single 2d images,” Neural Computation, vol. 8, pp. 1321–1340, 1997. [26] E. Prados and O. Faugeras, “Shape from shading,” in Handbook of Mathematical Models in Computer Vision (Y. C. N. Paragios and O. Faugeras, eds.), ch. 23, pp. 375–388, Springer, 2006. [27] M. Clerc and S. Mallat, “The texture gradient equation for recovering shape from texture,” vol. 24, no. 4, pp. 536–549, 2002. [28] D. A. Clausi and M. E. Jernigan, “Designing gabor filters for optimal texture separability,” Pattern Recognition, vol. 33, no. 11, pp. 1835 – 1849, 2000. [29] B. J. Super and A. C. Bovik, “Planar surface orientation from texture spatial frequencies,” Pattern Recognition, vol. 28, no. 5, pp. 729 – 743, 1995. [30] J. Malik and R. Rosenholtz, “Computing local surface orientation and shape from texture forcurved surfaces,” Int. J. Comput. Vision, vol. 23, pp. 149–168, June 1997. [31] S. H. Schwartz, Visual Perception: A Clinical Orientation. McGraw-Hill Medical, 3 ed., May 2004. [32] L. Lid´en and E. Mingolla, “Monocular occlusion cues alter the influence of terminator motion in the barber pole phenomenon,” Vision Research, vol. 38, no. 24, pp. 3883 – 3898, 1998. [33] N. Apostoloff and A. Fitzgibbon, “Learning spatiotemporal t-junctions for occlusion detection,” in Proc. IEEE Computer Society Conf. Computer Vision and Pattern Recognition CVPR 2005, vol. 2, pp. 553–559, 2005. [34] S. Ayer and H. S. Sawhney, “Layered representation of motion video using robust maximum-likelihood estimation of mixture models and mdl encoding,” in Proc. Conf. Fifth Int Computer Vision, pp. 777–784, 1995. [35] F. H. Durgin, D. R. Proffitt, T. J. Olson, and K. S. Reinke, “Comparing depth from motion with depth from binocular disparity,” Journal of Experimental Psychology: Human Perception and Performance, vol. 21, pp. 679–699, 1995. [36] M. E. Ono, J. Rivest, and H. Ono, “Depth perception as a function of motion parallax and absolute-distance information.,” Journal of Experimental Psychology: Human Perception and Performance, vol. 12, pp. 331– 337, 1986. 116 Bibliography [37] M. Nawrot and K. Stroyan, “The motion/pursuit law for visual depth perception from motion parallax,” Vision Research, vol. 49, no. 15, pp. 1969 – 1978, 2009. [38] A. Ogale, C. Fermuller, and Y. Aloimonos, “Motion segmentation using occlusions,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 27, no. 6, pp. 988 –992, 2005. [39] A. Criminisi, I. Reid, and A. Zisserman, “Single view metrology,” in Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on, vol. 1, pp. 434–441 vol.1, 1999. [40] A. Torralba and A. Oliva, “Depth estimation from image structure,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, p. 2002, 2002. [41] D. Martin, C. Fowlkes, and J. Malik, “Learning to detect natural image boundaries using local brightness, color, and texture cues,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 26, pp. 530–549, May 2004. [42] S. Yu, “Angular embedding: From jarring intensity differences to perceived luminance,” in Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, pp. 2302 –2309, 2009. [43] P. Arbelaez, M. Maire, C. Fowlkes, and J. Malik, “From contours to regions: An empirical evaluation,” in Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, pp. 2294 –2301, 2009. [44] P. Colantoni and B. Laget, “Color image segmentation using region adjacency graphs,” vol. 2, pp. 698 –702 vol.2, jul. 1997. [45] A. Tremeau and P. Colantoni, “Regions adjacency graph applied to color image segmentation,” Image Processing, IEEE Transactions on, vol. 9, pp. 735 –744, apr. 2000. [46] M. Pardas, P. Salembier, F. Marques, and R. Morros, “Partition tree for a segmentation-based video coding system,” in ICASSP ’96: Proceedings of the Acoustics, Speech, and Signal Processing, 1996. on Conference Proceedings., 1996 IEEE International Conference, (Washington, DC, USA), pp. 1982–1985, IEEE Computer Society, 1996. [47] P. Salembier and L. Garrido, “Binary partition tree as an efficient representation for image processing, segmentation, and information retrieval,” IEEE Trans. on Image Processing, vol. 9, pp. 561 –576, apr 2000. [48] G. Paschos, “Perceptually uniform color spaces for color texture analysis: an empirical evaluation,” Image Processing, IEEE Transactions on, vol. 10, pp. 932 –937, jun. 2001. [49] G. Sharma, Digital Color Imaging Handbook. Boca Raton, FL, USA: CRC Press, Inc., 2002. [50] I. 15076-1:2005, “Image technology colour management – architecture, profile format and data structure – part 1: Based on icc.1:2004-10,” tech. rep., International Organization for Standarization, 2005. [51] A. R. Robertson, “Historical development of cie recommended color difference equations,” Color Research & Application, vol. 15, no. 3, pp. 167–170, 1990. [52] V. Vilaplana, F. Marques, and P. Salembier, “Binary partition trees for object detection,” IEEE Trans. on Image Processing, vol. 17, pp. 2201 –2216, nov. 2008. [53] F. Calderero and F. Marques, “General region merging approaches based on information theory statistical measures,” in Image Processing, 2008. ICIP 2008. 15th IEEE International Conference on, pp. 3016–3019, Oct. 2008. [54] F. Calderero, F. Marques, and A. Ortega, “Performance evaluation of probability density estimators for unsupervised information theoretical region merging,” in Image Processing (ICIP), 2009 16th IEEE International Conference on, pp. 4397 –4400, nov. 2009. [55] F. Calderero and F. Marques, “Region merging techniques using information theory statistical measures,” Image Processing, IEEE Transactions on, vol. 19, pp. 1567 –1586, jun. 2010. 117 Bibliography [56] A. Buades, B. Coll, and J. M., “A review of image denoising algorithms, with a new one,” Multiscale Modeling & Simulation, vol. 4, no. 2, pp. 490–530, 2005. [57] M. A. Ruzon and C. Tomasi, “Edge, junction, and corner detection using color distributions,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 23, no. 11, pp. 1281–1295, 2001. [58] B. S. Manjunath, J. rainer Ohm, V. V. Vasudevan, and A. Yamada, “Color and texture descriptors,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 11, pp. 703–715, 1998. [59] R. N. Shepard, “Toward a universal law of generalization for psychological science,” Science, vol. 237, no. 4820, pp. 1317–1323, 1987. [60] P. Salembier, F. Marques, M. Pardas, J. Morros, I. Corset, S. Jeannin, L. Bouchard, F. Meyer, and B. Marcotegui, “Segmentation-based video coding system allowing the manipulation of objects,” Circuits and Systems for Video Technology, IEEE Transactions on, vol. 7, pp. 60 –74, feb 1997. [61] J. Puzicha, T. Hofmann, and J. Buhmann, “Non-parametric similarity measures for unsupervised texture segmentation and image retrieval,” in Computer Vision and Pattern Recognition, 1997. Proceedings., 1997 IEEE Computer Society Conference on, pp. 267–272, Jun 1997. [62] Y. Rubner, C. Tomasi, and L. Guibas, “A metric for distributions with applications to image databases,” in Computer Vision, 1998. Sixth International Conference on, pp. 59–66, Jan 1998. [63] H. Ling and K. Okada, “Diffusion distance for histogram comparison,” in CVPR ’06: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, (Washington, DC, USA), pp. 246–253, IEEE Computer Society, 2006. [64] F. Hillier and G. Lieberman, Introduction to Mathematical Programming. McGraw-Hill, 1990. [65] H. Ling and K. Okada, “Emd-l1: An efficient and robust algorithm for comparing histogram-based descriptors,” in ECCV, pp. 330–343, 2006. [66] H. Moravec, “Obstacle avoidance and navigation in the real world by a seeing robot rover,” in tech. report CMU-RI-TR-80-03, Robotics Institute, Carnegie Mellon University. Doctoral Dissertation, Stanford University, no. CMU-RI-TR-80-03, September 1980. [67] C. Harris and M. Stephens, “A combined corner and edge detection,” in Proceedings of The Fourth Alvey Vision Conference, pp. 147–151, 1988. [68] K. Mikolajczyk and C. Schmid, “An affine invariant interest point detector,” in Proc. European Conf. Computer Vision, pp. 128–142, Springer Verlag, 2002. [69] T. Lindeberg, “Principles for automatic scale selection,” in ISRN KTH, 1999. [70] F. Guichard and J. Morel, “Image analysis and PDEs,” Institute for Pure and Applied Mathematics GBM Tutorial, 2001. [71] L. Parida, D. Geiger, and R. Hummel, “Junctions: Detection, classification and reconstruction,” [72] S. M. Smith and J. M. Brady, “Susan-a new approach to low level image processing,” International Journal of Computer Vision, pp. 45–78, May 1997. [73] R. Bergevin and A. Bubel, “Detection and characterization of junctions in a 2d image,” Computer Vision and Image Understanding, vol. 93, no. 3, pp. 288 – 309, 2004. [74] T. Lindeberg, “Junction detection with automatic selection of detection scales and localization scales,” in In Proc. 1st International Conference on Image Processing, volume I, pp. 924–928, IEEE Computer Society Press, 1994. [75] H. Asada and M. Brady, “The curvature primal sketch,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. PAMI-8, pp. 2 –14, jan. 1986. 118 Bibliography [76] P. Perona and J. Malik, “Scale-space and edge detection using anisotropic diffusion,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 12, pp. 629 –639, jul 1990. [77] S. Osher and N. Paragios, Geometric Level Set Methods in Imaging,Vision,and Graphics. Secaucus, NJ, USA: Springer-Verlag New York, Inc., 2003. [78] V. Kolmogorov and R. Zabih, “Computing visual correspondence with occlusions using graph cuts,” vol. 2, pp. 508–515 vol.2, 2001. [79] Y. Weiss and W. Freeman, “On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs,” Information Theory, IEEE Transactions on, vol. 47, pp. 736–744, Feb 2001. [80] R. R. Behrens, Design in the Visual Arts. Prentice Hall College Div, 1985. [81] M. Dimiccoli and P. Salembier, “Exploiting t-junctions for depth segregation in single images,” in Acoustics, Speech and Signal Processing, 2009. ICASSP 2009. IEEE International Conference on, pp. 1229–1232, April 2009. [82] P. Arbelaez, M. Maire, C. Fowlkes, and J. Malik, “Contour detection and hierarchical image segmentation,” Tech. Rep. UCB/EECS-2010-17, EECS Department, University of California, Berkeley, Feb 2010. [83] R. Terruggia, Reliability Analysis of Probabilistic Networks. PhD thesis, Universita degli Studi di Torino, 2010. [84] J. Galtier, A. Laugier, and P. Pons, “Algorithms to evaluate the reliability of a network,” in Design of Reliable Communication Networks, 2005. (DRCN 2005). Proceedings.5th International Workshop on, p. 8 pp., 2005. [85] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. The MIT Press, 2nd revised edition ed., Sept. 2001. [86] P. Mateti and N. Deo, “On algorithms for enumerating all circuits of a graph,” SIAM J. Comput., vol. 5, no. 1, pp. 90–99, 1976. [87] D. Martin, C. Fowlkes, D. Tal, and J. Malik, “A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics,” in Proc. 8th Int’l Conf. Computer Vision, vol. 2, pp. 416–423, July 2001. [88] Y. Wang and B. Wu, “Improved single image dehazing using dark channel prior,” in Intelligent Computing and Intelligent Systems (ICIS), 2010 IEEE International Conference on, vol. 2, pp. 789 –792, oct. 2010. [89] P. Wei, Y. Liu, Y. Liu, and S. Wang, “Dehazing model based on multiple scattering,” in Image and Signal Processing (CISP), 2010 3rd International Congress on, vol. 1, pp. 249 –252, oct. 2010. 119