DOI:https://doi.org/10.15407/kvt211.01.029
Cybernetics and Computer Engineering, 2023, 1(211)
KRYGIN V.M.1, PhD Student,
Junior Researcher of Pattern Recognition Department,
https://orcid.org/0000-0002-9000-1685 ,
e-mail: valeriy.krygin@gmail.com
KHOMENKO R.O.2,
Programmer
https://orcid.org/0000-0001-7640-4077 ,
e-mail: ruslank3584@gmail.com
MATSELLO V.V.1, PhD (Engineering), Senior Researcher,
Head of Pattern Recognition Department
https://orcid.org/0000-0001-7640-4077 ,
e-mail: matsello@gmail.com
1International Research and Training Center for Information Technologies and Systems of the National Academy of Sciences of Ukraine and Ministry of Education and Science of Ukraine, 40, Acad. Glushkova av., Kyiv, 03187, Ukraine
2Postindustria Inc.,
1935 Walgrove av., Los Angeles CA 90066, USA.
EXPERIMENTAL VERIFICATION OF THE SELF-DRIVEN ALGORITHMS FOR SOLVING MAX-SUM LABELING PROBLEMS
Introduction. Max-sum labeling problems play an essential role in modern pattern recognition and can be used with other methods and a stand-alone approach. An essential step in building a pattern recognition system is the choice of an algorithm to solve the problem, which may require experimentation with different algorithms. This fires a need for software that allows solving different problems with the help of different algorithms for further analysis of the results of experiments and the final selection of the algorithm.
The purpose of the paper is to demonstrate the capabilities of the developed software for solving max-sum labeling problems.
Results. The software containing various algorithms for solving max-sum labeling problems was developed and experimentally tested. The program operation is shown on the example of image processing problems based on labeling: color image restoration, binary image denoising, posterization and binocular stereo vision.
Conclusions. The software described in the article verifies in practice the correctness of the self-driven algorithm for solving max-sum labeling problems. The application allows the operator to choose an algorithm for the labeling task and configure its parameters. This program will be helpful for developers of computer vision systems based on labeling problems and under-graduates, graduate students, and researchers studying structural pattern recognition methods.
Keywords: labeling problems, pattern recognition, computer vision, software.
REFERENCES
1. Ishikawa H., Geiger D. Segmentation by grouping junctions. Proceedings of IEEE computer society conference on computer vision and pattern recognition (cat. no.98CB36231), 1998, pp. 125-131.
2. Kovtun I.V. Technology of image texture segmentation on the basis of Markov random fields and solution of (max,+) problem. Control Systems and Computers. 2004, №2, pp. 61-66. (in Russian)
3. Held K. Markov random field segmentation of brain MR images. Transactions on Medical Imaging. IEEE, 1997, Vol. 16, № 6, pp. 878-886.
https://doi.org/10.1109/42.650883
4. Schlesinger M.I., Flach B. Analysis of optimal labeling problems and their applications to image segmentation and binocular stereovision. East-west-vision 2002 (EWV’02). International workshop & project festival computer vision, computer graphics, new media. 2002, pp. 55-60.
5. Schlesinger D., Flach B., Shekhovtsov A. A higher order MRF-model for stereo-reconstruction. Pattern recognition. 2004, pp. 440-446.
https://doi.org/10.1007/978-3-540-28649-3_54
6. Boykov Y., Veksler O., Zabih R. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2001, Vol. 23, № 11, pp. 1222-1239.
https://doi.org/10.1109/34.969114
7. Boykov Y., Kolmogorov V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Mach. Intell. USA: IEEE Computer Society. 2004, Vol. 26, № 9, pp. 1124-1137.
https://doi.org/10.1109/TPAMI.2004.60
8. Schlesinger M.I., Gygynyak V.V. Solution of Structural Recognition (MAX,+)-problems by their Equivalent Transformations. Part 2. Control Systems and Computers. 2007, N 2, pp. 3-18. (in Russian)
9. Szeliski R. 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, № 6, pp. 1068-1080.
https://doi.org/10.1109/TPAMI.2007.70844
10. Savchynskyy B. Discrete graphical models – an optimization perspective. Foundations and Trends® in Computer Graphics and Vision. 2019, Vol. 11, № 3-4, pp. 160-429.
https://doi.org/10.1561/0600000084
11. Li M., Shekhovtsov A., Huber D. Complexity of discrete energy minimization problems Computer vision – ECCV 2016, 2016, pp. 834-852.
https://doi.org/10.1007/978-3-319-46475-6_51
12. Schlesinger M.I., Antoniuk K.V. Diffusion algorithms and structural recognition optimization problems. Cybernetics and System Analysis. 2011, № 2, pp. 3-12. (in Russian)
https://doi.org/10.1007/s10559-011-9300-z
13. Krygin V., Khomenko R. Self-driven algorithm for solving supermodular (max,+) labeling problems based on subgradient descent. Cybernetics and Sys. Anal. 2022, Vol. 58, № 4. pp. 510-517.
https://doi.org/10.1007/s10559-022-00485-8
14. Bradski G. The OpenCV Library. Dr. Dobb’s Journal of Software Tools. 2000.
15. Gould S. DARWIN: A framework for machine learning and computer vision research and development. The Journal of Machine Learning Research. 2012 Vol. 13, № 1, pp. 3533-3537.
16. Kosov S. Direct graphical models C++ library. URL: http://research.project-10.de/dgm/, 2013.
17. Kosov S. Multi-layer conditional random fields for revealing unobserved entities: PhD thesis. Siegen University, 2018.
18. Mooij J.M. LibDAI: A free and open source C++ library for discrete approximate inference in graphical models. Journal of Machine Learning Research. 2010, Vol. 11, pp. 2169-2173.
19. Andres B., Beier T., Kappes J.H. OpenGM: A C++ library for discrete graphical models. CoRR. 2012. Vol. abs/1206.0111.
20. Kappes J.H. A comparative study of modern inference techniques for structured discrete energy minimization problems. International Journal of Computer Vision. Springer US, 2015,Vol. 115, № 2, pp. 155-184.
https://doi.org/10.1007/s11263-015-0809-x
21. Ankan A., Panda A. Pgmpy: Probabilistic graphical models using python. Proceedings of the 14th python in science conference (SCIPY 2015). Citeseer, 2015.
https://doi.org/10.25080/Majora-7b98e3ed-001
22. Schlesinger M.I., Hlavac V. Ten Lectures on Statistical and Structural Pattern Recognition. Kyiv: Naukova dumka, 2004. (in Russian)
23. Shor N.Z. Minimization methods for non-differentiable functions. Springer Series in Computational Mathematics. 1985, Vol. 3,pp. 22-48.
https://doi.org/10.1007/978-3-642-82118-9_3
24. Koval V.K., Schlesinger M.I. Two-dimensional programming in image analysis problems. Automatics and Telemechanics. 1976, V. 37, № 8. pp. 149-168. (in Russian)
25. Rossi F., Beek P. van, Walsh T. Handbook of constraint programming. Elsevier Science, 2006.
26. Scharstein, Daniel. High-accuracy stereo depth maps using structured light [Text] / Daniel Scharstein, Richard Szeliski. 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. IEEE. 2003, Vol. 1 -2003, pp. 195-202.
Received 02.01.2023