A Multiscale Variable-grouping Framework for MRF Energy Minimization

ICCV, 2015

Back to top.

Chinese character inpainting

The Chinese Character Inpainting dataset includes 100 instances of 64-connected grids with approximately 10,000 binary variables, the parameters of the model are learned from data. The input is a masked image of a Chinese character and the goal is to reconstruct the binary image. The dataset is considered hard to optimize due to the type of pairwise interaction, which involves many frustrated cycles.

We compare performance of single-scale and multiscale inference, as well as to a collection algorithms that achieved top-performance on this dataset. Five (ten) V-cycles of multiscale inference with LSA-TR reported the best energy on 40% (53%) of the dataset with outstanding runtimes. The best value can sum to more than 100% in case of ties.

algorithm mean run-time mean energy best
MCBC-pct 2053.89 sec -49550.10 66%
ogm-ILP-pct 3553.71 sec -49547.41 49%
ogm-LF-3 637.92 sec -49535.37 13%
SA -49533.02 12%
BPS-TAB 62.69 sec -49537.08 10%
Bagon&Galun 41.8 sec -49547.65 10%
ogm-TRWS-LF 83.78 sec -49519.42 6%
ogm-LBP-0.5 482.00 sec -49509.81 3%
Wang&Koller 3600 sec -49526.49 3%
LSA-TR (euc.) 0.05 sec -49548.10 22%
LSA-TR (multiscale) 5 V-cycles 12.4 sec -49549.68 40%
LSA-TR (multiscale) 10 V-cycles 23.7 sec -49549.89 53%
QPBO 0.14 sec 49501.95 0%
QPBO (multiscale) 8.85 sec -49542.78 9%
Lazy-Flipper 13 sec -49531.11 5%
Lazy-Flipper (multiscale) 41.9 sec -49544.82 11%


algorithm mean run-time mean energy best
ogm-LBP-LF2 152.94 sec -18401.12 20%
ogm-ADSAL 476.17 sec -18379.01 0%
TRWS-pct 3.62 sec -17009.28 0%
ogm-ILP-pct 3260.65 sec 0%
Lazy-Flipper 151.99 sec -17275.32 0%
Lazy-Flipper (multiscale) 227.96 sec -19138.93 70%
LSA-TR 196.73 sec -18833.20 0%
LSA-TR (multiscale) 87.10 sec -19135.65 90%
QPBO 0.01 sec 0 0%
QPBO (long) 645.04 sec -190614.3 80%
QPBO (multiscale) 100.05 sec -19213.05 100%

The Scribble dataset is an image segmentation task with a user-interactive interface, in which the user is asked to mark boundaries of objects in the scene. These boundaries are used for determining negative affinities between pixels on different sides of the boundary. The dataset contains 10 instances of approximately 70K variables with 1.5M edges each.

We compare single-scale and multiscale inference and report results for a selection of competitive methods that were not incorporated in our framework. On this challenging large-scale dataset, multiscale inference was repeatedly superior to single-scale. QPBO (long) denotes a single-scale, iterative application of QPBO-I; this highlights the advantage of multiscale inference, as even when QPBO-I was run exhaustively it came short compared with multiscale inference.

Further results are available in our paper.

Back to top.


A Matlab implementation can be grabbed here. Have a look in the README to get started, contact us with questions.

Back to top.