Improved generalized belief propagation for vision processing.

*(English)*Zbl 1202.94026Summary: Generalized belief propagation (GBP) is a region-based belief propagation algorithm which can get good convergence in Markov random fields. However, the computation time is too heavy to use in practical engineering applications. This paper proposes a method to accelerate the efficiency of GBP. A caching technique and chessboard passing strategy are used to speed up algorithm. Then, the direction set method which is used to reduce the complexity of computing clique messages from quadric to cubic. With such a strategy the processing speed can be greatly increased. Besides, it is the first attempt to apply GBP for solving the stereomatching problem. Experiments show that the proposed algorithm can speed up by 15+ times for typical stereo matching problem and infer a more plausible result.

##### MSC:

94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |

94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |

##### References:

[1] | M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky, “MAP estimation via agreement on trees: message-passing and linear programming,” IEEE Transactions on Information Theory, vol. 51, no. 11, pp. 3697-3717, 2005. · Zbl 1318.94025 · doi:10.1109/TIT.2005.856938 |

[2] | J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, 1988. · Zbl 0746.68089 |

[3] | J. S. Yedidia, T. F. William, and Y. Weiss, “Understanding belief propagation and its generalizations,” in Exploring Artificial Intelligence in the New Millennium, chapter 8, pp. 236-249, 2003. |

[4] | J. S. Yedidia, W. T. Freeman, and Y. Weiss, “Generalized belief propagation,” Neural Information Processing Systems, vol. 13, no. 7, pp. 689-695, 2000. |

[5] | J. S. Yedidia, W. T. Freeman, and Y. Weiss, “Constructing free-energy approximations and generalized belief propagation algorithms,” IEEE Transactions on Information Theory, vol. 51, no. 7, pp. 2282-2312, 2005. · Zbl 1283.94023 · doi:10.1109/TIT.2005.850085 |

[6] | P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient belief propagation for early vision,” International Journal of Computer Vision, vol. 70, no. 1, pp. 41-54, 2006. · Zbl 05062736 · doi:10.1007/s11263-006-7899-4 |

[7] | K. Petersen, J. Fehr, and H. Burkhardt, “fast generalized belief propagation for MAP estimation on 2D and 3D grid-like markov random fields,” in In Proceedings of the 30th Deutsche-Arbeitsgemeinschaft-fur-Mustererkennung (DAGM) Symposium on Pattern Recognition, pp. 10-13, Munich, Germany, June 2008. |

[8] | K. M. Pawan and P. H. S. Torr, “Fast memory-efficient generalized belief propagation,” in Proceedings of the European Conference on Computer Vision, Part IV, pp. 451-463. |

[9] | S. Z. Li, Markov Random Field Modeling in Image Analysis, Springer, 3rd edition, 2009. · Zbl 1183.68691 |

[10] | S. Geman and D. Geman, “Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 6, no. 6, pp. 721-741, 1984. · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596 |

[11] | C. Cattani, “Fractals and hidden symmetries in DNA,” Mathematical Problems in Engineering, vol. 2010, Article ID 507056, 31 pages, 2010. · Zbl 1189.92015 · doi:10.1155/2010/507056 · eudml:232469 |

[12] | Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, no. 11, pp. 1222-1239, 2001. · doi:10.1109/34.969114 |

[13] | J. Sun, Y. Li, S. B. Kang, and H.-Y. Shum, “Symmetric stereo matching for occlusion handling,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR ’05), pp. 399-406, June 2005. |

[14] | J. S. Yedidia, W. T. Freeman, and Y. Weiss, “Bethe free energy, kikuchi approximations and belief propagation algorithms,” Tech. Rep. TR-2001-16, Mitsubishi Electric Research Laboratories, 2001. |

[15] | E. G. Bakhoum and C. Toma, “Dynamical aspects of macroscopic and quantum transitions due to coherence function and time series events,” Mathematical Problems in Engineering, vol. 2010, Article ID 428903, 13 pages, 2010. · Zbl 1191.35219 · doi:10.1155/2010/428903 · eudml:225118 |

[16] | W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Reciples in C, Cambridge University Press, Cambridge, UK, 2nd edition, 1992. · Zbl 0845.65001 |

[17] | R. Balasubramanian, S. Das, and K. Swaminathan, “Reconstruction of quadratic curves in 3-D from two or more perspective views,” Mathematical Problems in Engineering, vol. 8, no. 3, pp. 207-219, 2002. · Zbl 1130.68330 · doi:10.1080/10241230215283 · eudml:53759 |

[18] | C. L. Zitnick and S. B. Kang, “Stereo for image-based rendering using image over-segmentation,” International Journal of Computer Vision, vol. 75, no. 1, pp. 49-65, 2007. · Zbl 05186875 · doi:10.1007/s11263-006-0018-8 |

[19] | R. Szeliski, R. Zabih, D. Scharstein et al., “A comparative study of energy minimization methods for Markov random fields with smoothness-based priors,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 6, pp. 1068-1080, 2008. · Zbl 05340877 · doi:10.1109/TPAMI.2007.70844 |

[20] | O. J. Woodford, P. H. S. Torr, I. D. Reid, and A. W. Fitzgibbon, “Multiview stereo via volumetric graph-cuts and occlusion robust photo-consistency,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 12, pp. 2241-2246, 2007. · Zbl 05341087 · doi:10.1109/TPAMI.2007.70712 |

[21] | M. Bleyer, C. Rother, and P. Kohli, “Surface stereo with soft segmentation,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 1570-1577, June 2010. |

[22] | Q. Yang, L. Wang, R. Yang, H. Stewénius, and D. Nistér, “Stereo matching with color-weighted correlation, hierarchical belief propagation, and occlusion handling,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 3, pp. 492-504, 2009. · doi:10.1109/TPAMI.2008.99 |

[23] | D. Scharstein and R. Szeliski, “A taxonomy and evaluation of dense two-frame stereo correspondence algorithms,” International Journal of Computer Vision, vol. 47, no. 1-3, pp. 7-42, 2002. · Zbl 1012.68731 · doi:10.1023/A:1014573219977 |

[24] | D. Scharstein and R. Szeliski, “Middlebury Stereo Vision Research,” 2008, http://vision.middlebury.edu/stereo/eval/. · Zbl 1039.68731 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.