Abstract
In this paper, we present a novel successive relaxation linear programming scheme for solving the important class of consistent labeling problems for which an L 1 metric is involved. The unique feature of the proposed scheme is that we use a much smaller set of basis labels to represent the label space. In a coarse to fine manner, the approximation improves during iteration. The proposed scheme behaves very differently from other methods in which the label space is kept constant in the solution process, and is well suited for very large label set matching problems. Based on the proposed matching scheme, we develop a robust multi-template tracking method. We also increase the efficiency of the template searching by a Markov model. The proposed tracking method uses a small number of graph templates and is able to deal with cases in which objects change appearance drastically due to change of aspect or object deformation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
Ishikawa, H.: Global Optimization using Embedded Graphs, Ph.D. Dissertation, NYU (May 2000)
Breuel, T.M.: A comparison of search strategies for geometric branch and bound algorithms. In: ECCV, vol. III, pp. 837–850 (2002)
Rosenfeld, A., Hummel, R.A., Zucker, S.W.: Scene labeling by relaxation operations. IEEE Trans. Systems, Man, and Cybernetics 6(6), 420–433 (1976)
Besag, J.: On the statistical analysis of dirty pictures. J. R. Statis. Soc. Lond. B 48, 259–302 (1986)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. PAMI 23, 1222–1239 (2001)
Pearl, J.: Probabilistic reasoning in intelligent systems – Networks of plausible inference. Morgan-Kaufmann, San Francisco (1988)
Weiss, Y., Freeman, W.T.: On the optimality of solutions of the max-product belief propagation algorithm in arbitrary graphs. IEEE Trans. on Information Theory 47(2), 736–744 (2001)
Felzenszwalb, P.F., Huttenlocher, D.P.: Efficient belief propagation for early vision. In: CVPR, vol. I, pp. 261–268 (2004)
Kolmogorov, V., Zabih, R.: Multi-camera scene reconstruction via graph cuts. In: ECCV, vol. III, pp. 82–96 (2002)
Kolmogorov, V., Zabih, R.: Computing visual correspondence with occlusions using graph cuts. In: ICCV, vol. II, pp. 508–515 (2001)
Sun, J., Shum, H.Y., Zheng, N.N.: Stereo matching using belief propagation. PAMI 25(7), 787–800 (2003)
Coughlan, J.M., Ferreira, S.J.: Finding deformable shapes using loopy belief propagation. In: ECCV, vol. III, pp. 453–468 (2002)
Luo, B., Hancock, E.R.: Structural matching using the EM algorithm and singular value decomposition. PAMI 23, 1120–1136 (2001)
Chui, H., Rangarajan, A.: A new algorithm for non-rigid point matching. In: CVPR, vol. II, pp. 44–51 (2000)
Rangarajan, A., Chui, H.L., Bookstein, F.L.: The softassign procrustes matching algorithm. In: Information Processing in Medical Imaging, pp. 29–42. Springer, Heidelberg (1997)
Tao, P.D., Phong, T.Q., Horaud, R., Quan, L.: Stability of Lagrangian duality for nonconvex quadratic programming solution methods and applications to computer vision. Mathematical Modelling and Numerical Analysis 31(1), 57–90 (1997)
Bai, X., Yu, H., Hancock, E.: Graph matching using embedding and semidefinite programming. In: BMVC (2004)
Ben-Ezra, M., Peleg, S., Werman, M.: Real-time motion analysis with linear programming. In: ICCV, pp. 703–709 (1999)
Kleinberg, J., Tardos, E.: Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. In: IEEE Symposium on Foundations of Computer Science, pp. 14–23 (1999)
Chekuri, C., Khanna, S., Naor, J., Zosin, L.: Approximation algorithms for the metric labeling problem via a new linear programming formulation. In: Symp. on Discrete Algs, pp. 109–118 (2001)
Comaniciu, D., Ramesh, V., Meer, P.: Real-time tracking of non-rigid objects using mean shift. In: CVPR, vol. II, pp. 142–149 (2000)
Black, M.J., Jepson, A.D.: Eigentracking: robust matching and tracking of articulated objects using a view-based representation. In: ECCV, pp. 329–342 (1996)
Morency, L.P., Rahimi, A., Darrell, T.: Adaptive view-based appearance models. In: CVPR, vol. I, pp. 803–810 (2003)
Jiang, H., Li, Z.N., Drew, M.S.: Optimizing motion estimation with linear programming and detail-preserving variational method. In: CVPR, vol. I, pp. 738–745 (2004)
Jiang, H., Li, Z.N., Drew, M.S.: Posture recognition with convex programming. In: ICME (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jiang, H., Drew, M.S., Li, ZN. (2005). Linear Programming Matching and Appearance-Adaptive Object Tracking. In: Rangarajan, A., Vemuri, B., Yuille, A.L. (eds) Energy Minimization Methods in Computer Vision and Pattern Recognition. EMMCVPR 2005. Lecture Notes in Computer Science, vol 3757. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11585978_14
Download citation
DOI: https://doi.org/10.1007/11585978_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30287-2
Online ISBN: 978-3-540-32098-2
eBook Packages: Computer ScienceComputer Science (R0)