УДК 519.854.3
В.М. КРИГІН,
Міжнародний науково-навчальний центр інформаційних технологій та систем НАН України та МОН України, Київ, Україна,
valeriy.krygin@gmail.com
Р.О. ХОМЕНКО,
Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», Київ, Україна,
ruslank3584@gmail.com
АЛГОРИТМ РОЗВ'ЯЗУВАННЯ СУПЕРМОДУЛЯРНИХ (max,+)
ЗАДАЧ РОЗМІТКИ ІЗ САМОКОНТРОЛЕМ НА ОСНОВІ
СУБГРАДІЄНТНОГО СПУСКУ
Анотація. Розглянуто алгоритм, який для будь-якої поданої на вхід (max,+) задачі розмітки з цілочисельними вагами надасть
на вихід одну з двох відповідей: або розв’язок у формі оптимальної розмітки, або фразу «задача не є супермодулярною»,
при цьому будь-яка відповідь гарантовано буде коректною. Самоконтроль у розпізнаванні образів полягає у тому,
що не користувач приймає рішення, на яке питання треба відповісти, а сам алгоритм вирішує, що потрапляє
у зону його компетентності. Іншою особливістю алгоритму є те, що він не потребує відомої впорядкованості міток для супермодулярних задач.
Гарантію скінченної кількості кроків забезпечує використання субградієнтного спуску і цілочисельність ваг вершин та ребер.
Ключові слова: (max,+) задачі розмітки, супермодулярні задачі розмітки, самоконтроль у розпізнаванні образів,
дискретна оптимізація, графові моделі, структурне розпізнавання образів.
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- 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.
- Шлезингер М., Гигиняк В. Решение (max, +)-задач структурного распознавания с помощью их эквивалентных преобразований. Управляющие системы и машины. 2007. № 1. С. 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.
- Шлезингер М.И., Антонюк К.В. Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания. Кибернетика и системный анализ. 2011. Т. 47, № 2. С. 3–20.
- Шлезингер М.И. Распознавание образов как реализация определенного подкласса процессов мышления. Управляющие системы и машины. 2017. № 2. С. 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.
- Водолазский Е.В. Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец. Управляющие системы и машины. 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.
- Коваль В., Шлезингер М. Двумерное программирование в задачах анализа изображений. Автоматика и телемеханика. 1976. Т. 37, № 8. С. 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.
