|
Deformed Lattice Detection Via Efficient Belief Propagation
|
|
Minwoo Park, Robert Collins, and Yanxi Liu
|
|
[pdf]
|
Introduction
|
|
A regular wallpaper pattern can be generated by two basis vectors, (t1, t2). The lattice generated by (t1, t2) divides a 2D plane into identical parallelograms, called tiles. Given the natural match between tiles/basis-vectors in wallpaper theory, and observable nodes/edges in probabilistic graph models, we can encode domain knowledge from wallpaper theory into the observation model and pairwise compatibility function of a degree-4 Markov Random Field (MRF). Belief Propagation (BP) can then be used to locate a deformed lattice in an unsegmented image.
|
.. |
|
|
|
Motivation
|
|
An automatic, robust and fast lattice detection algorithm can facilitate novel applications in 1) automated near-regular texture (NRTs) analysis and manipulation 2) photo editing for Image Defencing 3) Geo-tagging, and 4) 3D modeling.
|
|
|
|
(1) Liu et al "NRT analysis and manipulation" SIGGRAPH2004
|
|
|
|
(2) Liu et al , "Image de-fencing", CVPR2008
|
|
|
|
|
|
(3) Shindler et al [5] .......................................(4) Google Earth
|
|
Experimental Results
|
|
We evaluate performance of three deformed lattice detection algorithms on 32 images with ground truth labeled by two human coders. Our proposed algorithm is 10 times faster and 72.3% better at deformed lattice detection than Hays et al [3].
|
|
|
Lattice Detection Rate
|
| Lin and Liu [2] | 20 ± 21% |
| Hays et al [3] | 47 ± 38% |
| Ours | 81 ± 19%
|
|
|
Avg. Run Time Ratio
|
| Hays et al [3]/Ours | 10.66±9.6 |
|
|
|
|
|
Conclusion
|
|
We have developed a robust and fast lattice detection algorithm using a probabilistic graph model that has a better detection rate and is approximately 10 times faster than the current state-of-the-art algorithm [3].
|
|
Binary executable will be available upon request, please send email to mipark(at)cse.psu.edu
|
|
