Methods and Algorithms for Constructing Mathematically Correct Comparison Functions of Binary Images Based on Skeletons 

(RFBR Grant  18-07-00942)

Project objectives: The aim of the project is the creation of mathematically correct, a computationally effective comparison of binary images on the basis of skeletal morphology, metric satisfying the hypothesis of compactness in the context of the applied problems in computer vision.

 

Problem formulation

The description of the form is an important task of computer vision, which can be solved based on different approaches. Our contribution based on the skeleton representation of a binary raster shape. The skeleton is constructed by calculating the median axes of the binary image.

The task of direct comparison of two skeletons does not have a unique solution. There is a promising approach to constructing a procedure for pairwise comparison of skeletons given by chains of primitives. The comparison method is based on the procedure for finding the optimal pairwise alignment of chains of primitives (coded descriptions of skeletal graphs).

The results of the preliminary studies are reflected in the publications of the team and the leader investigator, as well as in the final report on the RFBR project 14-07-31271 "Methods and algorithms for unambiguous analysis of skeletal graphs of binary images". The algorithms for regularizing the skeletal description of a form unstable to noise, the coding of skeletons by chains of primitives that consider both the topological features of the skeleton and its width function, algorithms for comparing the chains by means of the pair alignment mechanism and obtaining the difference function are developed. However, a number of serious problems still remain unresolved, which do not allow to call the established methodology exhaustive, universal and theoretically strictly justified.

OBJECTIVE OF THE PROPOSED PROJECT is the construction of mathematically correct, computationally effective functions for comparing binary images based on skeletal morphology that satisfy the metric hypothesis of compactness in the context of the applied task.

The results obtained should make it possible to compare any pairs of images without involving a priori information about the applied task. This will eliminate the stage of heuristic selection of attributes-descriptors of image forms and directly use methods of unambiguous, metric recognition of the forms of binary raster images.

Project Team

Oleg Seredin (Principal Investigator), Olesia Kushnir, Sofia Fedotova, Andrei Kopylov, Sergey Dvoenko, Valentina Sulimova, Olga Krasotkina, Vadim Mottl, Alexander Larin (2018, 2019), Denis Rodionov (2018), Egor Surkov (2020).

Main Ideas

 

Рисунок 1 – Скелет замкнутой области

Рисунок 2 – Иллюстрация неустойчивости скелетного описания:

незначительные изменения контура приводят

к существенному изменению скелета

Рисунок 3 – Исходное изображение (а), его скелет (б),

скелет после регуляризации (в), регуляризированный скелет после

аппроксимации (г), аппроксимированный скелет после склейки (д)

1

Рисунок 4 – Бинарное изображение, его скелет, множитель нормировки – диаметр минимальной описанной окружности, направление обхода скелета

и цепочка примитивов

 

Рисунок 5 – Иллюстрация процедуры получения параметрического

описания радиальной функции скелета

 

Рисунок 6 – Бинарные изображения (показаны черным цветом),

их скелет и восстановленные по цепочке примитивов изображения

 

Рисунок 7 – Изображения, их скелеты и парное выравнивание цепочек

 

Рисунок 8 – Визуализация совмещения скелетов двух листьев,

выполненная автоматически при помощи модуля

 в составе разработанного программного комплекса

 

Рисунок 9 – Результат классификации 32 типов растений из базы Flavia

 

Рис. 10 – Пример поиска оси (квази)симметрии для бинарных изображений

 

Рис. 10 – Пример совмещения пары бинарных изображений с учетом информации об оси симметрии

 

Publications

Опубликованные в 2018 году работы:

 

1) Kopylov, A., Seredin, O., Kushnir, O., Gracheva, I. and Larin, A. Background-Invariant Robust Hand Detection based on Probabilistic One-Class Color Segmentation and Skeleton Matching // Proceedings of the 7th International Conference on Pattern Recognition Applications and Methods (ICPRAM 2018). P. 503-510. ISBN: 978-989-758-276-9 DOI: 10.5220/0006649805030510

http://www.scitepress.org/DigitalLibrary/Link.aspx?doi=10.5220/0006649805030510

2) Кушнир О.А., Середин О.С. Параллельные реализации алгоритма сравнения бинарных изображений на основе описания скелетов цепочками примитивов // Вестник компьютерных и информационных технологий, № 1, 2018. С. 24 – 33.

http://vkit.ru/index.php/current-issue-rus/682-024-033

3) Кушнир О.А. Методы и алгоритмы сравнения форм бинарных растровых изображений на основе скелетизации // Дисс. канд. техн. наук, Тула, 2018, 129 с.

http://tsu.tula.ru/science/dissertation/diss-212-271-05/Kushnir_OA/

4) Кушнир О.А., Середин О.С. Программа сравнения бинарных растровых изображений на основе скелетного описания формы, представленного цепочками примитивов //Свидетельство о государственной регистрации программы для ЭВМ №2018611213, 25.01.2018.

5) Mottl V., Seredin O., Krasotkina O. Compactness hypothesis, potential functions, and rectifying linear space in machine learning //Braverman Readings in Machine Learning. Key Ideas from Inception to Current State. – Springer, Cham, 2018. – pp. 52-102.

https://elibrary.ru/item.asp?id=35736162

6) Федотова С.А., Середин О.С., Кушнир О.А. Об использовании инвариантов отражения в практическом решении задачи определения зеркальной симметрии //В книге: Интеллектуализация обработки информации. Тезисы докладов 12-й Международной конференции. 2018. С. 114-115.

https://elibrary.ru/item.asp?id=36345393

7) Середин О.С., Копылов А.В., Родионов Д.С. Использование Microsoft Kinect v2 для детектирования падений человека //В книге: Интеллектуализация обработки информации. Тезисы докладов 12-й Международной конференции. 2018.С. 140-141.

https://elibrary.ru/item.asp?id=36370369

8) Dvoenko S.D., Pshenichny D.O. On conditionality of pairwise comparisons in machine learning //ICPRAI-2018 Proceedings, Montreal, May 13-18, 2018. CENPARMI, Concordia University, pp. 618-621.

https://users.encs.concordia.ca/~icprai18/ICPRAI2018-CFP.pdf

9) Двоенко С.Д., Пшеничный Д.О. Применение t-распределения Стьюдента при метрической коррекции матриц парных сравнений //В книге: Интеллектуализация обработки информации. Тезисы докладов 12-й Международной конференции. 2018.С. 16-17.

https://elibrary.ru/item.asp?id=36345295

10) Федотова С.А., Середин О.С., Кушнир О.А., Об использовании инвариантов отражения в практическом решении задачи определения

зеркальной симметрии //Известия ТулГУ, Серия Технические науки, №10, 2018. С 125-137.

11) Яковлев С.С., Середин О.С., Использование деревьев решений при визуализации многомерных данных //Известия ТулГУ, Серия Технические науки, №10, 2018. С 137-145.

12) Двоенко С.Д., Пшеничный Д.О. Коррекция метрических нарушений на основе проверки статистических гипотез //Известия ТулГУ, Серия Технические науки, №10, 2018. с. 100-107.

 

Опубликованные в 2019 году работы:

 

1) Kushnir O. A., Seredin O. S., Fedotova S. A. Algorithms for Adjustment of Symmetry Axis Found for 2d Shapes by the Skeleton Comparison Method //International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. – 2019. – Т. 42. – №. 2/W12, pp. 129-136. DOI: 10.5194/isprs-archives-XLII-2-W12-129-2019

https://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XLII-2-W12/129/2019/isprs-archives-XLII-2-W12-129-2019.pdf

2) Seredin O. S., Kopylov, A. V., Huang, S. C., & Rodionov, D. S. A Skeleton Features-Based Fall Detection Using Microsoft Kinect v2 with One Class-Classifier Outlier Removal //International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. – 2019. – Т. 42. – №. 2/W12, pp.189-195. DOI: 10.5194/isprs-archives-XLII-2-W12-189-2019

https://pdfs.semanticscholar.org/5c05/81c7a5228730bb72d2f6fefe14d54d8a742a.pdf

3) Sulimova V., Seredin O., Mottl V. Recognition of Herpes Viruses on the Basis of a New Metric for Protein Sequences //Journal of Physics: Conference Series. – IOP Publishing, 2019. – Т. 1368. – №. 5. – С. 052039. doi:10.1088/1742-6596/1368/5/052039

https://iopscience.iop.org/article/10.1088/1742-6596/1368/5/052039/pdf

4) Сулимова В.В., Середин О.С., Моттль В.В. Применение новой метрики, основанной на парном выравнивании биомолекулярных последовательностей, для распознавания вирусов герпеса // Сборник трудов V международной конференции и молодежной школы "Информационные технологии и нанотехнологии" (ИТНТ-2019), г. Самара, 2019 г., Том 4. Науки о данных – Самара: Новая техника, С. 259-268.

http://repo.ssau.ru/handle/Informacionnye-tehnologii-i-nanotehnologii/Primenenie-novoi-metriki-osnovannoi-na-parnom-vyravnivanii-biomolekulyarnyh-posledovatelnostei-dlya-raspoznavaniya-virusov-gerpesa-75656

5) Середин О.С., Копылов А.В., Сурков Е.Э. Исследование сокращения скелетного описания для задачи детектирования падений. Математические методы распознавания образов: Тезисы докладов 19-й Всероссийской конференции с международным участием, г. Москва, 2019 г.   М.: Российская академия наук, 2019. C. 223-226.

http://machinelearning.ru/wiki/images/b/bf/MMPR2019.pdf

6) Федотова С.А., Середин О.С. Кушнир О.А. Метод сравнения бинарных растровых изображений, содержащих дыры, с учетом информации об осях симметрии. Математические методы распознавания образов: Тезисы докладов 19-й Всероссийской конференции с международным участием, г. Москва, 2019 г. М.: Российская академия наук, 2019. C. 140-143.

http://machinelearning.ru/wiki/images/b/bf/MMPR2019.pdf

7) Gracheva I. A., Kopylov A. V. Tone Compression Algorithm for High Dynamic Range Medical Images //ISPRS-International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. – 2019. – Т. 4212. – С. 87-95.

https://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XLII-2-W12/87/2019/isprs-archives-XLII-2-W12-87-2019.pdf

8) Семенов П. В., Князев Д. В., Копылов А. В. Алгоритм стабилизации видео с выбором ведущей группы движений с сохранением размерности кадра. Математические методы распознавания образов: Тезисы докладов19-й Всероссийской конференции с международным участием, г. Москва2019 г.   М.: Российская академия наук, 2019. C. 171-174.

http://machinelearning.ru/wiki/images/b/bf/MMPR2019.pdf

9) Sergey Dvoenko, On Clustering by Metric Medians, PRIP'2019, Pattern recognition and Information Processing. Proc. of the 14 Int. Conf. 21-23 May 2019, Minsk, Belarus. pp. 285-289.

https://prip.bsuir.by/

10) Двоенко СД, Пшеничный ДО Метрическая кластеризация ранжирований. Математические методы распознавания образов: Тезисы докладов19-й Всероссийской конференции с международным участием, г. Москва2019 г.   М.: Российская академия наук, 2019. С. 42-43.

http://machinelearning.ru/wiki/images/b/bf/MMPR2019.pdf

11) Двоенко СД, Пшеничный ДО Технология коррекции и обработки парных сравнений. Математические методы распознавания образов: Тезисы докладов19-й Всероссийской конференции с международным участием, г. Москва2019 г.   М.: Российская академия наук, 2019. с.50-51.

http://machinelearning.ru/wiki/images/b/bf/MMPR2019.pdf

 

Опубликованные в 2020 году работы:

 

1) S. Fedotova, O. Kushnir, and O. Seredin, Comparison of Binary Images based on Jaccard Measure using Symmetry Information, in Proceedings of the 15th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2020), 2020, vol. 4, pp. 398–404.

https://www.elibrary.ru/item.asp?id=43263137

2) Середин О. С., Копылов А. В., Сурков Е. Э. Сокращение признакового описания скелетной модели человека в задаче обнаружения падений с учётом антропометрических характеристик. //Техническое зрение в системах управления - 2020: сб. тез. докл. научно-техн. конф. 17-18 марта 2020, Москва, ИКИ РАН. М.: ИКИ РАН, 2020. С. 25-26., ISBN 978-5-00015-046-7.

http://tvcs2020.technicalvision.ru/

3) Ларин А.О., Середин О.С., Копылов А.В. Модифицированный критерий для описания данных гиперсферой с учетом нетипичных объектов // Известия ТулГУ. Серия Технические науки, №10, 2020 г. стр. 231-239.

https://cyberleninka.ru/article/n/modifitsirovannyy-kriteriy-dlya-opisaniya-dannyh-gipersferoy-s-uchetom-netipichnyh-obektov

4) Seredin O.S., Kopylov A.V. Surkov E.E. The study of skeleton description reduction in the human fall-detection task. Computer Optics 2020; 44(6): 951-958. DOI: 10.18287/2412-6179-CO-753.

http://www.computeroptics.smr.ru/KO/Annot/KO44-6/440613.html

5) Ларин А.О., Середин О.С., Копылов А.В. Критерий одноклассовой классификации при наличии нетипичных объектов в обучающей выборке // Тезисы докладов 13-й международной конференции "Интеллектуализация обработки информации", Москва, Россия, М.: Российская академия наук, с.28-30, 2020.

http://www.machinelearning.ru/wiki/images/3/31/Idp20.pdf

6) Двоенко С.Д., Пшеничный Д.О. О новых типах медианы Кемени// Тезисы докладов 13-й международной конференции "Интеллектуализация обработки информации", Москва, Россия, М.: Российская академия наук, с.322-323, 2020.

http://www.machinelearning.ru/wiki/images/3/31/Idp20.pdf

7) Филин А.И., Грачева И.А., Копылов А.В. Совместная оценка карты рассеивания и атмосферной освещенности с использованием вероятностной гамма-нормальной модели для задачи устранения тумана на изображении // Тезисы докладов 13-й международной конференции "Интеллектуализация обработки информации", Москва, Россия, М.: Российская академия наук, с.332-335, 2020.

http://www.machinelearning.ru/wiki/images/3/31/Idp20.pdf

8) Макарова А.И., Курбаков М.Ю., Сулимова В.В. Нелинейный метод средних решающих правил с умными подвыборками для решения больших двухклассовых задач SVM-классификации. // Тезисы докладов 13-й международной конференции "Интеллектуализация обработки информации", Москва, Россия, М.: Российская академия наук, с.41-45, 2020.

http://www.machinelearning.ru/wiki/images/3/31/Idp20.pdf

 

Получено четыре Свидетельства о государственной регистрации программы для ЭВМ.

Разработанные в ходе реализации проекта методы и алгоритма реализованы в виде комплекса программ сравнения бинарных растровых изображений на основе скелетного описания формы, представленного цепочками примитивов, информации об оси симметрии и прикладное ПО для автоматического обнаружения падений человека на основе учета изменения скелетного представления позы во времени.

 

1. Кушнир О.А., Середин О.С. Программа сравнения бинарных растровых изображений на основе скелетного описания формы, представленного цепочками примитивов //Свидетельство о государственной регистрации программы для ЭВМ №2018611213, 25.01.2018.

2. Федотова С.А., Середин О.С., Кушнир О.А. Регистрация программы для ЭВМ «Программа поиска оси симметрии на бинарных растровых изображениях», //Свидетельство о государственной регистрации программы для ЭВМ № 2020616535, 18.06.2020.

3. Федотова С.А., Середин О.С., Кушнир О.А. Регистрация программы для ЭВМ «Программа сравнения бинарных растровых изображений с использованием информации об оси симметрии», //Свидетельство о государственной регистрации программы для ЭВМ № 2020616825, 23.06.2020.

4. Сурков Е.Э., Середин О.С., Копылов А.В. Регистрация программы для ЭВМ «Программа автоматического обнаружения падений человека на основе учета изменения скелетного представления позы во времени». //Свидетельство о государственной регистрации программы для ЭВМ RU 2020663198, 23.10.2020.