Belief propagation (BP) has been successfully used to approximate the solutions of various Markov random field (MRF) formulated energy minimization problems. However, large MRFs require a significant amount of memory to store the intermediate belief messages. We observe that these messages have redundant information due to the imposed smoothness prior. In this paper, we study the feasibility of applying compression techniques to the messages in the min-sum/max-product BP algorithm with 1D labels to improve the memory efficiency and reduce the read/write bandwidth. We articulate properties that an efficient message representation should satisfy. We investigate two common compression schemes, predictive coding and linear transform coding (PCA), and then propose a novel envelope point transform (EPT) method. Predictive coding is efficient and supports linear operations directly in the compressed domain, but it is only compatible with the L1smoothness function. PCA has the disadvantage that it does not guarantee the preservation of the minimal label. EPT is not limited to L1smoothness cost and allows a flexible quality vs. compression ratio tradeoff compared with predictive coding. Experiments on dense stereo reconstruction have shown that the predictive scheme and EPT can achieve 8times or more compression without significant loss of depth accuracy.

We show that the approaches to 3D reconstruction that use volumetric graph cuts to minimize a cost function over the object surface have two types of biases, the minimal surface bias and the discretization bias. These biases make it difficult to recover surface extrusions and other details, especially when a non-lambertian photo-consistency measure is used. To reduce these biases, we propose a new iterative graph cuts based algorithm that operates on the Surface Distance Grid (SDG), which is a special discretization of the 3Dspace, constructed using a signed distance transform of the current surface estimate. It can be shown that SDG significantly reduces the minimal surface bias, and transforms the discretization bias into a controllable degree of surface smoothness. Experiments on 3D reconstruction of non-lambertian objects confirm the effectiveness of our algorithm over previous methods.

Recently, nonlinear shape models have been shown to improve the robustness and flexibility of segmentation. In this paper, we propose shape regularized active contour (ShRAC) that incorporates existing nonlinear shape models into the classical active contour approach. ShRAC uses a discrete representation of the contour to allow efficient combinatorial search. The search for optimal contour is performed by coarse-to-fine algorithm that iterates between combinatorial search and gradient-based local optimization. First, multi-solution dynamic programming (MSDP) is used to generate initial candidates by minimizing only the image energy. In the second step, a combination of image energy and shape energy determined by a given prior shape model is minimized for the initial candidates using a local optimization method and the best one is selected. To have diverse initial candidates, we employ a clustered solution pruning procedure in the MSDP search space. Finally, local shape regularization is used to feed shape constraints back into the new MSDP search space of the next iteration. Our search strategy combines the advantages of global combinatorial search and local optimization, and has shown excellent robustness to local minima caused by distracting suboptimal segmentations. Experimental results on segmentation of different anatomical structures using ShRAC are provided.