Control Systems and Computers, N2, 2017, Article 3

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. Ковалевский В.А. Оптимальный алгоритм распознавания некоторых последовательностей изображений // Кибернетика. – 1967. – N 4. – С. 75–80.
  2. Ковалевский В.А. Методы оптимальных решений в распознавании изображений. – М.: Наука, 1976. – 328 с.
  3. Kovalevsky V.A. Application of Mathematical Programming for Character and Pattern Recognition // Proc. of the 5th Int. Cong. on Cybernetics, Assosiation Int. de Cybernetique, Namur. – 1967. – P. 746–755.
  4. Kovalevsky V.A. Recognition by Imitating the Process of Pattern Generation / Watanabe S. (Ed): Methodologies of Pattern Recognition. – Acad. Press. – 1969. – P. 345–358.
  5. Винцюк Т.К. Распознавание устной речи методами динамического программирования // Кибернетика. – 1968. – № 1. – С. 81–88.
  6. Винцюк Т.К. Анализ, распознавание и интерпретация речевых сигналов. – Киев: Наук. думка, 1987. – 262 с.
  7. Rossi F., van Beek P., Walsh T. Handbook of Constraint Programming, Foundations of Artificial Intelligence. – Elsevier, 975 p.
  8. Рябоконь Д.И. Пространственная реконструкция поверхностей по стереопаре изображений с помощью алгоритма поиска минимального сечения на графе // УСиМ. – 2004. – № 3. – С. 47–51.
  9. Рябоконь Д.І. Технологія побудови тривимірних моделей неперервних поверхонь за стереопарами зображень: Дис. ¼ канд. техн. наук. – К.: МННЦ ІТіС, 2005. – 138 с.
  10. Ковтун И.В. Технология текстурной сегментации изображений на основании марковских случайных полей и решения (max,+)-задач // УСиМ. – 2004. – № 2. – С. 61–66.
  11. Ковтун І.В. Сегментація зображень на основі достатніх умов оптимальності в NP-повних класах задач структурної розмітки: Дис. ¼ канд. техн. наук. – К.: МННЦ ІТіС, 2004. – 135 с.
  12. Tyshchenko M.A. 3D reconstruction of human face based on single or several images // УСиМ. – 2011. – № 2. – С. 79–85.
  13. Тищенко М.А. Тривимірна реконструкція людського обличчя в задачах ідентифікації особи: Дис. ¼ канд. техн. наук. – К.: МННЦ ІТіС, 2011. – 118 с.
  14. Cooper M.C. Reduction operations in fuzzy or valued constraint satisfaction, Fuzzy Sets and Systems 134. – 2003. – Р. 311–342. – www.elsevier.com/locate/fss
  15. The complexity of soft constraint satisfaction / D.A. Cohen, M.C. Cooper, P.G. Jeavons et al. // Artificial Intelligence 170. – 2006. – Р. 983–1016. – www.elsevier. com/locate/artint
  16. Шлезингер М.И. Синтаксический анализ двумерных зрительных сигналов в условиях помех // Кибернетика. – 1976. – № 4. – С. 113–130.
  17. Коваль В.К., Шлезингер М.И. Двумерное программирование в задачах анализа изображений // Автоматика и телемеханика. – 1976. – № 8. – С. 149–168.
  18. Шлезингер М.И. Математические средства обработки изображений. – Киев: Наук. думка, 1989. – 197 с.
  19. Flerova N., Marinescu R., Dechter R. Searching for the M Best Solutions in Graphical Models // J. of Artificial Intelligence Research. – 2016. – N 55. – P. 889–952.
  20. Ruttkay Zs. Fuzzy constraint satisfaction // Proc. 3rd IEEE Int. Conf. on Fuzzy Syst. – 1994. – P. 1263–1268.
  21. Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. – К.: Наук. думка, 2004. – 545 с.
  22. Cohen D.A., Jeavons P.G. The Complexity of Constraint Languages, Chapter 8, in Handbook of Constraint Programming. – Elsevier, 2006. – P. 245–280.
  23. Водолазский Е., Флах Б., Шлезингер М. Минимаксные задачи дискретной оптимизации, инвариантные относительно мажоритарных операторов // ЖВММФ/ – 2014. – Т. 54, № 8. – С. 1368–1378.
  24. Lovasz L. Submodular functions and convexity. Ed. by A. Bachem, M. Grotschel, B. Korte // Mathematical Programming – The State of the Art. – Springe–Verlag, New York, 1983. – P. 235–257.
  25. Schlesinger M., Flach B. Some solvable subclasses of structural recognition problems, Czech Pattern Recognition Workshop, 2000. – Р. 55–62.
  26. Werner T. A Linear Programming Approach to Max-sum Problem: A Review // IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI). – July 2007. – 29(7). – P.1165–1179.
  27. Werner T. Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction // Ibid. Aug. 2010. – 32(8). – P. 1474–1488.
  28. Шлезингер М.И., Гигиняк В.В. Решение (max,+)-за­дач структурного распознавания с помощью их эквивалентных преобразований // УСиМ. – 2007, Ч. 1, № 1, С. 3–15, Ч. 2, № 2, С. 5–17.
  29. Шлезингер М.И., Антонюк К.В. Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания // Кибернетика и системный анализ. – 2011. – № 2. – С. 3–12.
  30. Ishikawa H., Geiger D. Segmentation by grouping junctions // IEEE Comp. Society Conf. on Computer Vision and Pattern Recognition. – 1998. – P. 125–131.
  31. Boykov Y., Veksler O., Zabih R. Fast Approximate Energy Minimization via Graph Cuts. IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI). – 2001. – 23(11) – P. 1222–1239.
  32. Kolmogorov V., Zabih R. What energy functions can be minimized via graph cuts? / Eur. Conf. on Comp. Vision (ECCV). – Springer-Verlag, 2002. – P. 65–81.
  33. Шлезингер М., Вернер Т. О супермодулярной максимизации. – http://www.irtc.org.ua/image/app/web­root/Files/publications/Schlesinger/Smachivanije.pdf
  34. Lawler E.L. 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. 1972. – 18, N 7. –P. 401–405.
  35. Schlesinger M., Flach B., Vodolazskiy E. M-best so­lutions for a class of fuzzy constraint satisfaction problems (Submitted on 23 Jul 2014), arXiv:1407.6166v1.
  36. Time bounds for selection / M. Blum, R. Floyd, V. Pratt et al. // J. of Comp. and Syst. Sci., 1973. – 7, N 4. – P. 448–461
  37. Rollon E., Flerova N., Dechter R. Inference Schemes for M Best Solutions for Soft CSPs Article // Proc. of Workshop on Preferences and Soft Constraints. – 2011. – Р. 124–138.

Received 27.03.2017