UDC 519.854.3
1 International Scientific-Educational Center of Information Technologies and Systems,
National Academy of Sciences of Ukraine and Ministry of Education and Science of Ukraine, Kyiv, Ukraine
 valeriy.krygin@gmail.com
|
2 National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Kyiv, Ukraine
ruslank3584@gmail.com
|
SELF-DRIVEN ALGORITHM FOR SOLVING SUPERMODULAR (max,+) LABELING
PROBLEMS BASED ON SUBGRADIENT DESCENT
Abstract. An algorithm presented in this article gives a correct answer to one of the two questions
for any (max,+) labeling problem with integer weights: either “What is the best labeling?” or “Is the problem supermodular?”,
and this answer is guaranteed to be correct. The algorithm is called self-driven because the user cannot decide
which of the two questions will be answered — this decision is up to the algorithm.
Also, the algorithm does not need to know the order of labels if the problem is supermodular.
The finite execution time of the algorithm is guaranteed for integer weights of vertices and edges and use of subgradient descent.
Keywords: (max,+) labeling problems, supermodular labeling problems, self-driven pattern recognition, discrete optimization, graphical models, structural pattern recognition
.
FULL TEXT
REFERENCES
- Boykov Y., Veksler O., Zabih R. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2001. Vol. 23, Iss. 11. P. 1222–1239. https://doi.org/10.1109/34.969114.
- Boykov Y., Kolmogorov V. An experimental comparison of min-cut/maxflow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2004. Vol. 26, Iss. 9. P. 1124–1137. https://doi.org/10.1109/TPAMI.2004.60.
- Schlesinger M., Giginyak V. Solving (max, +)-problems of structural recognition using their equivalent transformations. Upravlyayushchiye sistemy i mashiny. 2007. N 1. P. 3–15.
- Szeliski R., Zabih R., Scharstein D. et al. A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2008. Vol. 30, Iss. 6. P. 1068–1080.
- Wang C., Komodakis N., Paragios N. Markov random field modeling, inference & learning in computer vision & image understanding: a survey. Computer Vision and Image Understanding (CVIU). 2013. Vol. 117, Iss. 11. P. 1610–1627.
- Savchynskyy B. Discrete graphical models — an optimization perspective. Foundations and Trends in Computer Graphics and Vision. 2019. Vol. 11, N 3–4. P. 160–429.
- Ishikawa H. Exact optimization for Markov random fields with convex priors. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2003. Vol. 25, Iss. 10. P. 1333–1336.
- Schlesinger M.I., Antonyuk K.V. Analysis of diffusion algorithms for solving optimization problems of structural recognition. Kibernetika i sistemnyj analiz. 2011. Vol. 47, N 2. P. 3–20.
- Schlesinger M.I. Pattern recognition as an implementation of a certain subclass of thought processes. Upravlyayushchiye sistemy i mashiny. 2017. N 2. P. 20–37.
- Vodolazskii E., Flach B., Schlesinger M. Minimax problems of discrete optimization invariant under majority operators. Computational Mathematics and Mathematical Physics. 2014. Vol. 54, Iss. 8. P. 1327–1336.
- Vodolazskiy E.V. Generalized labeling problems with majority polymorphism for some class of semirings. Upravlyayushchiye sistemy i mashiny. 2015. N 6. P. 3–7.
- Shor N. Minimization methods for non-differentiable functions. Springer Series in Computational Mathematics. Berlin: Springer-Verlag, 1985. Vol. 3. P. 22–48.
- Schlesinger M., Vodolazskiy E., Lopatka N. Stop condition for subgradient minimization in dual relaxed (max, +) problem. Proc. 8th International Conference on EMMCVPR (Energy Minimization Methods in Computer Vision and Pattern Recognition) (25-27 July, 2011 Saint Petersburg, Russia). Saint Petersburg, 2011. P. 118–131.
- Schlesinger D., Flach B. Transforming an arbitrary MinSum problem into a binary one. Tech. report. TU Dresden, Fak. Informatik. 2006.
- Shlezinger M. Syntactic analysis of two-dimensional visual signals in the presence of noise. Cybernetics. 1976. Vol. 12, N 4. P. 612–628.
- Werner T. Revisiting the linear programming relaxation approach to Gibbs energy minimization and weighted constraint satisfaction. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2010. Vol. 32, Iss. 8. P. 1474–1488.
- Koval V., Schlesinger M. Two-dimensional programming in image analysis problems. Avtomatika i telemekhanika. 1976. Vol. 37, N 8. P. 149–168.
- Rossi F., van Beek P., Walsh T. Handbook of Constraint Programming. Elsevier Science, 2006. 957 p.
- Li M., Shekhovtsov A., Huber D. Complexity of discrete energy minimization problems. In: Computer Vision — ECCV 2016. Leibe B., Matas J., Sebe N., Welling M. (Eds.). Cham: Springer International Publishing, 2016. P. 834–852.
- Arora S., Barak B. Computational Complexity: A Modern Approach. USA: Cambridge University Press, 2009. 594 p.
