Deformed lattice detection in real-world images using mean-shift belief propagation

Minwoo Park, Kyle Brocklehurst, Robert T. Collins, Yanxi Liu

Research output: Contribution to journalArticlepeer-review

142 Scopus citations


We propose a novel and robust computational framework for automatic detection of deformed 2D wallpaper patterns in real-world images. The theory of 2D crystallographic groups provides a sound and natural correspondence between the underlying lattice of a deformed wallpaper pattern and a degree-4 graphical model. We start the discovery process with unsupervised clustering of interest points and voting for consistent lattice unit proposals. The proposed lattice basis vectors and pattern element contribute to the pairwise compatibility and joint compatibility (observation model) functions in a Markov Random Field (MRF). Thus, we formulate the 2D lattice detection as a spatial, multitarget tracking problem, solved within an MRF framework using a novel and efficient Mean-Shift Belief Propagation (MSBP) method. Iterative detection and growth of the deformed lattice are interleaved with regularized thin-plate spline (TPS) warping, which rectifies the current deformed lattice into a regular one to ensure stability of the MRF model in the next round of lattice recovery. We provide quantitative comparisons of our proposed method with existing algorithms on a diverse set of 261 real-world photos to demonstrate significant advances in accuracy and speed over the state of the art in automatic discovery of regularity in real images.

Original languageEnglish (US)
Pages (from-to)1804-1816
Number of pages13
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number10
StatePublished - 2009

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Deformed lattice detection in real-world images using mean-shift belief propagation'. Together they form a unique fingerprint.

Cite this