Data Driven Mean-shift Belief Propagation (DDMSBP)


Members: Minwoo Park, S. Kashyap, R. Collins, and Y. Liu 


Abstract


We introduce a novel data-driven mean-shift belief propagation(DDMSBP) method for non-Gaussian MRFs, which often arise in computer vision applications. With the aid of scale space theory, optimization of non-Gaussian, multimodal MRF models using DDMSBP becomes less sensitive to local maxima. This is a significant improvement over standard BP inference, and extends the range of methods that are computationally tractable. In particular, when pair-wise potentials are Gaussians, the time complexity of DDMSBP becomes bilinear in the numbers of states and nodes in the MRF. Experimental results from simulation and non-rigid deformable neuro image registration demonstrate that our method is faster and more accurate than state-of-the-art inference algorithms.


DDMSBP


We develop two theorems that connect MSBP [22, 21], smoothing based optimization [14], and Gaussian belief propagation for inference of a non-Gaussian MRF. Since the proposed method adapts gradually to the given data during the MSBP procedures, we call this method data driven mean-shift belief propagation (DDMSBP).



Validation of DDMSBP


To validate our approach, we demonstrate applications of DDMSBP to an interpolation problem on a continuous MRF, and to 3D deformable registration using a discrete MRF.


Interpolation Problem on Continuous MRF : To test the performance of the proposed method on a continuous MRF, we adopt the approach of Park et al [21] who modified the simulation performed by Weiss and Freeman [31] to use non-Gaussian unary potentials. Likewise, we also run NBP [27, 11, 29], simulated annealing using Markov Chain Monte Carlo (MCMC) moves [6, 24], MSBP, EP, and the proposed method on the same problem to perform inference on a 25 by 25 grid with the same parameter settings (Fig. 3). Approximating the joint MAP by the max-marginal estimate using NBP is a common practice in problems defined on graphs since there is no max-product BP for continuous multimodal MRFs [10]. We use L=200 samples for DDMSBP, NBP, and simulated annealing, epsilon=0.01 for DDMSBP and MSBP, and 11 bins for MSBP for the first experiment.




Figure 3: (a) Surface z(x; y) = (x2 + y2)=50 (b) Sample non-Gaussian unary potentials out of 25 by 25 functions (c) Actual measurement where only 20% of the nodes are measurable (d) Random initialization of pixel labels at the 2D grid points.





Figure 4: (a) Accuracy vs time trade off by -log(P(X; z)) (b) The results of estimation using the proposed method (Left) and the smoothing bandwidth at sample iterations (Right) are shown.



As can be seen in Fig. 4a, EP converges fast but with less accuracy in terms of MAP criterion than NBP, MSBP, and DDMSBP. This lack of accuracy is expected when EP is used for multimodal unary potentials. The proposed method converges several orders of magnitude faster than the other methods (except EP) while achieving better accuracy in terms of MAP criterion. We ran both MSBP and the proposed DDMSBP method 100 times to measure the bounds plotted in Fig. 4a. Fig. 4b shows progress of variance (bandwidth) smoothing parameter updates during a sample run.


3D Deformable Registration via discrete MRF: Neuroimage registration has been a fundamental research topic for many years in medical image analysis, where establishing correspondence between two sample images is crucial for many applications, including neuroimage classification [26], computer aided diagnosis [17, 18], statistical quantification of human brains and neuroimage segmentation [30]. While traditional registration techniques such as affine registration can account for differences in position and shape, they are not sufficient for modeling local deformations. Many deformable registration techniques have been proposed [12]. One of the major limitations of these algorithms is their execution time, which can take hours to complete. Recently Glocker et al. and Shekhovtsov et al. [7, 25] proposed a fast deformable registration algorithm using an MRF-based model. In this section we compare our DDMSBP algorithm with [7] on a volumetric deformable registration problem.




(e) Volume overlap


Figure 5: Sample results of registration for one subject are shown. Checkerboard and difference image before and after registration clearly show the performance of DDMSBP-based deformable registration. (e) shows the volume overlap of gray matter between the manual segmentation by experts and the one found by our algorithm. The red color shows True Positive (TP) regions, the yellow color shows False Positive (FP) regions, and the blue color shows False Negative (FN) regions. ITK-SNAP was used to generate this figure [32].



Figure 6: We compare the proposed method to FastPD in terms of DICE, sensitivity, and specificity.




Related Publications


Minwoo Park, S. Kashyap, R. Collins, and Y. Liu, “Data Driven Mean-Shift Belief Propagation For non-Gaussian MRFs“, Computer Vision and Pattern Recognition Conference (CVPR '10) (To Appear)


Minwoo Park, Kyle Brocklehurst, Robert T. Collins, and Yanxi Liu. “Deformed Lattice Detection in Real-World Images using Mean-Shift Belief Propagation”, IEEE Transaction on Pattern Analysis and Machine Intelligence (PAMI). Special Issue on Probabilistic Graphical Models, Volume 31, number 10 in October 2009.


Minwoo Park, Yanxi Liu and Robert T. Collins , “Efficient Mean Shift Belief Propagation for Vision Tracking”, Computer Vision and Pattern Recognition Conference (CVPR '08)