Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2017.02.020

Upr. sist. maš., 2017, Issue 2 (268), pp. 20-37.

UDC 519.683:681.3

Schlesinger Michail I., Doctor of science (Ph. and Math.), Professor, Researcher, International Research and Training Centre of Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, E-mail: schles@irtc.org.ua

Pattern Recognition as an Implementation of a Certain Type of Thought Processes

Purpose. The paper presents a review of pattern recognition research conducted by the International Research and Training Center for Information Technologies and Systems during the last 20 years since the moment of it’s foundation. This research lies on the edge of classical pattern recognition and constraint satisfaction problems. The system of concepts, problems and algorithms produced by the merge of these fields formalizes a particular type of thought process performed by humans and other living beings.

Introduction. The application of Constraint Satisfaction Problem theory to pattern recognition problems has produced a breakthrough in such traditionally hard problems in computer vision as stereo vision and texture segmentation. At the same time, the merge of Constraint Satisfaction Problem theory and practical computer vision problems has led to expansion of mathematical theory of the former. First of all it has resulted in introduction of a quality function over the set of solutions and finding the best solution instead of an arbitrary one. The next generalization consisted in finding a given number of best solutions and not just a singe best solution.

Methods. The paper describes methods of finding the best solution to the Weighted (Soft) Constraint Satisfaction Problem as well as the method of finding any given number of best solutions. These methods are implemented as algorithms whose domain is the set of all possible Weighted (Soft) Constraint Satisfaction Problems, i.e. a NP-hard problem class. For any given problem from the domain the algorithms either find it’s solution or reject the problem. It is essential that the algorithms automatically distinguish the subdomains of their competence, i.e. the subset of problems that they do not reject. The subdomain of competence of the algorithm that finds the best solution includes the known class of submodular minimization problems but is not restricted to it. The subdomain of competence of the algorithm that finds a given number of best solutions includes the minimization of functions with a majority polymorphism but is not restricted to it.

Keywords: pattern recognition, thought processes, submodular minimization problems, Constraint Satisfaction Problem theory.

Download full text!

1. Kovalevsky, V.A., 1967. “The optimal algorithm for recognizing certain image sequences”. Cybernetics. 4. pp. 75–80.
2. Kovalevsky, V.A., 1976. Methods of optimal solutions in image recognition. M .: Nauka, 328 p.
3. Kovalevsky, V.A., 1967. “Application of Mathematical Programming for Character and Pattern Recognition”. Proc. of the 5th Int. Cong. on Cybernetics, Assosiation Int. de Cybernetique, Namur, pp. 746–755.
4. Kovalevsky, V.A., 1969. “Recognition by Imitating the Process of Pattern Generation”. Acad. Press, pp. 345–358.
   https://doi.org/10.1016/B978-1-4832-3093-1.50023-7
5. Vintsyuk, T.K.,1968. “Speech recognition methods of dynamic programming”. Cybernetics. 1968. 1. pp. 81–88.
6. Vintsyuk, T.K., 1987. Analysis, recognition and interpretation of speech signals. Kiev: Sciences. Dumka, 1987. 262 p.
7. Rossi F., van Beek P., Walsh T. Handbook of Constraint Programming, Foundations of Artificial Intelligence. Elsevier, 975 p.
8. Ryabokon, D.I., 2004. “Spatial reconstruction of surfaces using a stereo pair of images using the algorithm for finding the minimum cross section on a graph”. Upravlausie sistemy i masiny. 3. pp. 47–51.
9. Ryabokon, D.I., 2005. Technology of construction of three-dimensional models of continuous surfaces under stereopsis of images: PhD Thesis, tech sciences K .: IISC ITIS, 138 p.
10. Kovtun, I.V., 2004. “The technology of textural segmentation of images based on Markov random fields and solving (max, +) tasks”. Upravlausie sistemy i masiny, 2. pp. 61–66.
11. Kovtun, I.V., 2004. Segmentation of images on the basis of sufficient optimality conditions in NP-complete classes of structural marking tasks: PhD Thesis, tech sciences K .: IISC ITIS, 135 p.
12. Tyshchenko, M.A., 2011. “3D reconstruction of human face based on single or several images”. Upravlausie sistemy i masiny, 2, pp. 79–85.
13. Tischenko, M.A., 2011. Three-dimensional reconstruction of a human face in the tasks of identification: PhD Thesis,  tech sciences K .: ISTC ITSi, 2011. 118 p.
14. Cooper, M.C., 2003. Reduction operations in fuzzy or valued constraint satisfaction, Fuzzy Sets and Systems 134, pp. 311–342. www.elsevier.com/locate/fss.
    https://doi.org/10.1016/S0165-0114(02)00134-3
15. D.A. Cohen, M.C. Cooper, P.G. Jeavons et al., 2006. “The complexity of soft constraint satisfaction”. Artificial Intelligence 170, pp. 983–1016. www.elsevier.com/locate/artint
    https://doi.org/10.1016/j.artint.2006.04.002
16. Schlesinger, M.I., 1976. “Syntactic analysis of two-dimensional visual signals in terms of interference”. Cybernetics, 4. pp. 113–130.
17. Koval, V.K., Schlesinger, M.I., 1976. “Two-dimensional programming in image analysis tasks”. Automation and remote control, 8. pp. 149–168.
18. Schlesinger, M.I., 1989. Mathematical image processing tools. Kiev: Sciences. Dumka, 197 p.
19. Flerova N., Marinescu R., Dechter R., 2016. “Searching for the M Best Solutions in Graphical Models”. J. of Artificial Intelligence Research, 55, pp. 889–952.
    https://doi.org/10.1613/jair.4985
20. Ruttkay, Zs., 1994. “Fuzzy constraint satisfaction”. Proc. 3rd IEEE Int. Conf. on Fuzzy Syst, pp. 1263–1268.
    https://doi.org/10.1109/FUZZY.1994.343640
21. Schlesinger, M., Glavach, V., 2004. Ten lectures on statistical and structural recognition. K .: Science. Dumka, 545 p.
22. Cohen, D.A., Jeavons, P.G., 2006. “The Complexity of Constraint Languages”, Chapter 8, Handbook of Constraint Programming. Elsevier, pp. 245–280.
    https://doi.org/10.1016/S1574-6526(06)80012-X
23. Vodolazsky, E., Flach, B., Schlesinger, M., 2014. “Minimax discrete optimization problems invariant with respect to majority operators”. ZHVMMF,  54 (8), pp. 1368–1378.
24. Lovasz, L., 1983. “Submodular functions and convexity”. Mathematical Programming – The State of the Art. Springe–Verlag, New York, pp. 235–257.
    https://doi.org/10.1007/978-3-642-68874-4_10
25. Schlesinger, M., Flach, B., 2000. “Some solvable subclasses of structural recognition problems”, Czech Pattern Recognition Workshop, pp. 55–62.
26. Werner, T., 2007. “A Linear Programming Approach to Max-sum Problem: A Review”. IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI). July 2007. 29(7). pp.1165–1179.
    https://doi.org/10.1109/TPAMI.2007.1036
27. Werner, T., 2010. “Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction”. IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI). Aug. 2010. 32(8). pp. 1474–1488.
    https://doi.org/10.1109/TPAMI.2009.134
28. Schlesinger, M.I., Giginyak, V.V., 2007. “The solution of (max, +) – problems of structural recognition with the help of their equivalent transformations”. Upravlausie sistemy i masiny, Part 1, 1, pp. 3–15, Part 2, 2, pp. 5–17.
29. Schlesinger, M.I., Antonyuk, K.V., 2011. “Analysis of diffusion algorithms for solving optimization problems of structural recognition”. Cybernetics and system analysis, 2. pp. 3–12.
30. Ishikawa, H., Geiger, D., 1998. “Segmentation by grouping junctions”. IEEE Comp. Society Conf. on Computer Vision and Pattern Recognition, pp. 125–131.
    https://doi.org/10.1109/CVPR.1998.698598
31. Boykov, Y., Veksler, O., Zabih, R., 2001. “Fast Approximate Energy Minimization via Graph Cuts”. IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI). 23(11). pp. 1222–1239.
    https://doi.org/10.1109/34.969114
32. Kolmogorov, V., Zabih, R., 2002. “What energy functions can be minimized via graph cuts?”. Eur. Conf. on Comp. Vision (ECCV). Springer-Verlag, pp. 65–81.
    https://doi.org/10.1007/3-540-47977-5_5
33. Schlesinger, M., Werner, T. On Supermodular Maximization. http://www.irtc.org.ua/image/app/web­root/Files/publications/Schlesinger/Smachivanije.pdf
34. Lawler, E.L., 1972. “A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem”, Management Science. Theory Series. Mar. 18 (7). pp. 401–405.
35. Schlesinger, M., Flach, B., Vodolazskiy, E., 2014. M-best so­lutions for a class of fuzzy constraint satisfaction problems (Submitted on 23 Jul 2014), arXiv:1407.6166v1.
36. Blum, M., Floyd, R., Pratt V. et al., 1973. “Time bounds for selection”. J. of Comp. and Syst. Sci., 7 (4). pp. 448–461.
    https://doi.org/10.1016/S0022-0000(73)80033-9
37. Rollon, E., Flerova, N., Dechter, R., 2011. “Inference Schemes for M Best Solutions for Soft CSPs Article”. Proc. of Workshop on Preferences and Soft Constraints, pp. 124–138.

Received 27.03.2017