A Fast Semidefinite Approach to Solving Binary Quadratic Problems
Segmentation results on the Berkeley dataset. The top row shows the original images with partial labelled pixels. Our SDCut (bottom) achieves better results than BNCut (middle).
Many computer vision problems can be formulated as binary quadratic programs (BQPs). Two classic relaxation methods are widely used for solving BQPs, namely, spectral methods and semidefinite programming (SDP), each with their own advantages and disadvantages. Spectral relaxation is simple and easy to implement, but its bound is loose. Semidefinite relaxation has a tighter bound, but its computational complexity is high for large scale problems.
We present a new SDP formulation for BQPs, with two desirable properties. First, it has a similar relaxation bound to conventional SDP formulations. Second, compared with conventional SDP methods, the new SDP formulation leads to a significantly more efficient and scalable dual optimization approach, which has the same degree of complexity as spectral methods. Extensive experiments on various applications including clustering, image segmentation, co-segmentation and registration demonstrate the usefulness of our SDP formulation for solving large-scale BQPs.
A fast semidefinite approach to solving binary quadratic problems.
P. Wang, C. Shen, A. van den Hengel. Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), 2013.
A scalable dual approach to semidefinite metric learning.
C. Shen, J. Kim, L. Wang. Proc. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), 2011.
C. Shen's participation in this research was supported by Australian Research Council Future Fellowship FT120100969.
The documents contained in these directories are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright.