This dissertation addresses the problem of inferring scene depth information from a collection of calibrated images taken from different viewpoints via stereo matching. Although it has been heavily investigated for decades, depth from stereo remains a long-standing challenge and popular research topic for several reasons. First of all, in order to be of practical use for many real-time applications such as autonomous driving, accurate depth estimation in real-time is of great importance and one of the core challenges in stereo. Second, for applications such as 3D reconstruction and view synthesis, high-quality depth estimation is crucial to achieve photo realistic results. However, due to the matching ambiguities, accurate dense depth estimates are difficult to achieve. Last but not least, most stereo algorithms rely on identification of corresponding points among images and only work effectively when scenes are Lambertian. For non-Lambertian surfaces, the "brightness constancy" assumption is no longer valid. This dissertation contributes three novel stereo algorithms that are motivated by the specific requirements and limitations imposed by different applications. In addressing high speed depth estimation from images, we present a stereo algorithm that achieves high quality results while maintaining real-time performance. We introduce an adaptive aggregation step in a dynamic-programming framework. Matching costs are aggregated in the vertical direction using a computationally expensive weighting scheme based on color and distance proximity. We utilize the vector processing capability and parallelism in commodity graphics hardware to speed up this process over two orders of magnitude. In addressing high accuracy depth estimation, we present a stereo model that makes use of constraints from points with known depths - the Ground Control Points (GCPs) as referred to in stereo literature. Our formulation explicitly models the influences of GCPs in a Markov Random Field. A novel regularization prior is naturally integrated into a global inference framework in a principled way using the Bayes rule. Our probabilistic framework allows GCPs to be obtained from various modalities and provides a natural way to integrate information from various sensors. In addressing non-Lambertian reflectance, we introduce a new invariant for stereo correspondence which allows completely arbitrary scene reflectance (bidirectional reflectance distribution functions - BRDFs). This invariant can be used to formulate a rank constraint on stereo matching when the scene is observed by several lighting configurations in which only the lighting intensity varies.

3D representation nowadays has attracted much more public attention than ever before. One of the most important techniques in this field is depth extraction. In this thesis, we first introduce a well-known stereo matching method using color segmentation and belief propagation, and make an implementation of this framework. The color-segmentation based stereo matching method performs well recently, since this method can keep the object boundaries accurate, which is very important to depth map. Based on the implemented framework of segmentation based stereo matching, we proposed a color segmentation based 2D-to-3D video conversion method using high quality motion information. In our proposed scheme, the original depth map is generated from motion parallax by optical flow calculation. After that we employ color segmentation and plane estimation to optimize the original depth map to get an improved depth map with sharp object boundaries. We also make some adjustments for optical flow calculation to improve its efficiency and accuracy. By using the motion vectors extracted from compressed video as initial values for optical flow calculation, the calculated motion vectors are more accurate within a shorter time compared with the same process without initial values. The experimental results shows that our proposed method indeed gives much more accurate depth maps with high quality edge information. Optical flow with initial values provides good original depth map, and color segmentation with plane estimation further improves the depth map by sharpening its boundaries.

3D representation nowadays has attracted much more public attention than ever before. One of the most important techniques in this field is depth extraction. In this thesis, we first introduce a well-known stereo matching method using color segmentation and belief propagation, and make an implementation of this framework. The color-segmentation based stereo matching method performs well recently, since this method can keep the object boundaries accurate, which is very important to depth map. Based on the implemented framework of segmentation based stereo matching, we proposed a color segmentation based 2D-to-3D video conversion method using high quality motion information. In our proposed scheme, the original depth map is generated from motion parallax by optical flow calculation. After that we employ color segmentation and plane estimation to optimize the original depth map to get an improved depth map with sharp object boundaries. We also make some adjustments for optical flow calculation to improve its efficiency and accuracy. By using the motion vectors extracted from compressed video as initial values for optical flow calculation, the calculated motion vectors are more accurate within a shorter time compared with the same process without initial values. The experimental results shows that our proposed method indeed gives much more accurate depth maps with high quality edge information. Optical flow with initial values provides good original depth map, and color segmentation with plane estimation further improves the depth map by sharpening its boundaries.

General 3D stereo vision is composed of two major phases. In the first phase, an image and its corresponding depth map are generated using stereo matching. In the second phase, depth-based image rendering (DIBR) is employed to generate images of different view angles. Stereo matching, a computation-intensive operation, generates the depth maps from two images captured at two different view positions. In this thesis, we present hardware designs of three different stereo matching methods: pixel-based, window-based, and dynamic programming (DP)-based. Pixel--based and window-based methods belong to the local optimization stereo matching methods while DP, one of the global optimization methods, consists of three main processing steps: matching cost computation, cost aggregation, and back-tracing. Hardware implementation of DP-based stereo matching usually requires large memory space to store the intermediate results, leading to large area cost. In this thesis, we propose a tile-based DP method by partition the original image into smaller tiles so that the processing of each tile requires smaller memory size.

Recently, stereo vision has been widely used in many applications, and depth map is important information in stereo vision. In general, depth map can be generated from the disparity using stereo matching based on two input images of different viewing positions. Due to the large computation complexity, software implementation of stereo matching usually cannot achieve real-time computation speed. In this thesis, we propose hardware implementations of stereo matching to speed up the generation of depth map. The proposed design uses a global optimization method, called dynamic programming, to find the disparity based on two input images: left image and right image. It consists of three main processing steps: matching cost computation (M.C.C.), minimum cost accumulation (M.C.A.), and disparity optimization (D.O.). The thesis examines the impact of different pixel operation orders in M.C.C and M.C.A modules on the cost of hardware. In the design of D.O. module, we use two different approaches. One is a Systolic-Like structure with streaming processing, and the other is memory-based design with low hardware cost. The final architecture with pipelining and memory-based D.O. can save a lot of hardware cost and achieve high throughput rate for processing a sequence of image pairs.

The present graph cut methods cannot be used directly for real time stereo matching applications because of their recursive structure. Graph cut method is modified to change its recursive structure so that making it suitable for real time FPGA (Field Programmable Gate Array) implementation. The modified method is firstly tested by MATLAB on several data sets, and the results are compared with those of previous studies. Although the disparity results of the modified method are not better than other methods&rsquo / , computation time performance is better. Secondly, the FPGA simulation is performed using real data sets. Finally, the modified method is implemented in FPGA with two PAL cameras at 25 Hz. The computation time of the implementation is 40 ms which is suitable for real time applications.

No description available.

A stereo vision system is a robust method to sense the distance information in a scene. This research explores the stereo vision system from the fundamentals of stereo vision and the computer stereo vision algorithm to the final implementation of the system on a FPGA chip. In a stereo vision system, images are captured by a pair of stereo image sensors. The distance information can be derived from the disparities between the stereo image pair, based on the theory of binocular geometry. With the increasing focus on 3D vision, stereo vision is becoming a hot topic in the areas of computer games, robot vision and medical applications. Particularly, most stereo vision systems are expected to be used in real-time applications. In this thesis, several stereo correspondence algorithms that determine the disparities between stereo image pair are examined. The algorithms can be categorized into global stereo algorithms and local stereo algorithms depending on the optimization techniques. The global algorithms examined are the Dynamic Time Warp (DTW) algorithm and the DTW with quantization algorithm, while the local algorithms examined are the window based Sum of Squared Differences (SSD), Sum of Absolute Differences (SAD) and Census transform correlation algorithms. With analysis among them, the window based SAD correlation algorithm is proposed for implementation on a FPGA platform. The proposed algorithm is implemented onto an Altera DE2 board featuring an Altera Cyclone II 2C35 FPGA. The implemented module of the algorithm is simulated using ModelSim-Altera to verify the correctness of its functionality. Along with a pair of stere image sensors and a LCD monitor, a stereo vision system is built. The entire system realizes a real-time video frame rate of 16.83 frames per second with an image resolution of 640 by 480 and produces disparity maps in which the objects are clearly distinguished by their relative distance information.

Perception of depth information is central to three-dimensional (3D) vision problems. Stereopsis is an important passive vision technique for depth perception. Wide baseline stereo is a challenging problem that attracts much interest recently from both the theoretical and application perspectives. In this research we approach the problem of wide baseline stereo using the geometric and structural constraints within feature sets. The major contribution of this dissertation is that we proposed and implemented a more efficient paradigm to handle the challenges introduced by perspective distortion in wide baseline stereo, compared to the state-of-the-art. To facilitate the paradigm, a new feature-matching algorithm that extends the state-of-the-art matching methods to larger baseline cases is proposed. The proposed matching algorithm takes advantage of both the local feature descriptor and the structure pattern of the feature set, and enhances the matching results in the case of large viewpoint change. In addition, an innovative rectification for uncalibrated images is proposed to make wide baseline stereo dense matching possible. We noticed that present rectification methods did not take into account the need for shape adjustment. By introducing the geometric constraints of the pattern of the feature points, we propose a rectification method that maximizes the structure congruency based on Delaunay triangulation nets and thus avoid some existing problems of other methods. The rectified stereo images can then be used to generate a dense depth map of the scene. The task is much simplified compared to some existing method because the 2D searching problem is reduced to 1D searching. To validate the proposed methods, real world images are applied to test the performance and comparisons to the state-of-the-art methods are provided. The performance of the dense matching with respect to the changing baseline is also studied.

In this thesis, a novel and fast method to compute the dense disparity map of a stereo pair of images is presented. Most of the current stereo matching algorithms are ill suited for real-time matching owing to their time complexity. Methods that concentrate on providing a real-time performance, sacrifice much in accuracy. The presented method, Fast Estimation of Dense Disparity Map Using Pivot Points (FEDDUP), uses a hierarchical approach towards reduction of search space to find the correspondences. The hierarchy starts with a set of points and then it moves on to a mesh with which the edge pixels are matched. This results in a semi-global disparity map. The semi global disparity map is then used as a soft constraint to find the correspondences of the remaining points. This process delivers good real-time performance with promising accuracy.