Методы и алгоритмы селекции контурных изображений деталей машин тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Торопчин Дмитрий Анатольевич

• Торопчин Дмитрий Анатольевич
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Торопчин Дмитрий Анатольевич

ВВЕДЕНИЕ

ГЛАВА 1. Контурные изображения и методы их обработки

1.1 Общие положения, обзор методов решения задач распознавания и селекции

1.2 Понятие контурного изображения и контурный анализ

1.3 Чертежи и схемы как источник контурных изображений

1.4 Обзор методов поиска чертежей и схем по визуальному подобию

1.5 Анализ алгоритмов распознавания контурных изображений

1.6 Обоснование выбора технологии Nvidia CUDA для программно-алгоритмической реализации

1.7 Основные выводы

ГЛАВА 2. Разработка методов и алгоритмов алфавитного представления контурных изображений

2.1 Формально-логическое представление контурных изображений

2.2 Выделение контуров изображения и определение граничного контура

2.3 Выделение кривых из контуров изображений

2.4 Символьное представление контуров изображений

2.5 Инвариантность символьного представления изображений к поворотам, смещениям, сжатиям и растяжениям

2.6 Выводы и результаты главы

ГЛАВА 3. Селекция контурных изображений

3.1 Метод селекции контурных изображений по признакам

3.2 Формализация задачи поиска изображений. Многоэтапный подход

3.3 Отношения эквивалентности на множестве символьных представлений

3.4 Метрические расстояния на множестве символьных представлений контуров

3.5 Многоэтапная процедура поиска контурных изображений

3.6. Выводы и результаты главы

ГЛАВА 4. Экспериментальное исследование эффективности разработанной методики

4.1 Оценка эффективности параллельных алгоритмов селекции деталей машин

4.2 Архитектура программно-аппаратной реализации процедур селекции

4.3 Процедура селекции контурных изображений деталей машин

4.4 Результаты и выводы

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ А

ПРИЛОЖЕНИЕ Б

ПРИЛОЖЕНИЕ В

152

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы селекции контурных изображений деталей машин»

ВВЕДЕНИЕ

Актуальность. Автоматизация обработки графических данных на основе современных цифровых технологий является одним из важных путей повышения эффективности, надежности и качества технических систем за счет совершенствования существующих методов и средств анализа обработки информации и управления сложными системами, что обусловило большое внимание к этой проблематике со стороны отечественных и зарубежных ученых.

Значительную часть компьютерной графической информации о деталях машин составляют контурные изображения, представленные только контурами отдельных его элементов, вследствие чего информативное содержание изображений отражено линиями различных типов.

Контурные изображения являются результатами специальной обработки изображений общего вида (выделения контуров), а также входят в состав технической и научной документации (карты, схемы, чертежи), разрабатываемой с использованием специализированных графических редакторов.

В современных условиях все большее значение приобретает использование графической информации при автоматизации управления робототехническими комплексами, где (в ряде случаев) достаточными являются данные, представимые контурными изображениями.

Остается актуальной задача оцифровки, накопленной за долгие годы документации, выполненной на бумажных носителях. Среди прочих задач обработки контурных изображений, например, в сфере машиностроения особенно остро стоит задача поиска оцифрованных чертежей и схем, так как существуют недостатки систем графического поиска чертежей и схем, а именно: не соответствие требуемой степени запросам пользователя; гибкость задания пользовательских запросов. Поэтому в подобных системах возникает проблема задания адаптированной к конкретной задаче оптимальной поисковой стратегии.

Стандартные способы поиска чертежей деталей машин с использованием информационно-графических представлений не приводят к удовлетворительным

результатам. Одним из перспективных подходов для решения данного вопроса является введение контентного поиска, основанного на сопоставлении и распознавании образов. Использование распознавания образов в поиске деталей машин, их чертежей, изображений связана с преодолением размерности пространства поиска и может решаться с помощью селекции.

Использование информационных графических представлений, не учитывающих специфику контурных изображений, связано с неоправданными затратами на хранение, обработку и передачу информации. Применение для решения практических задач обработки контурных изображений мощного математического аппарата алгебраической геометрии, основы которого были заложены еще в XVIII веке, а затем развиты в работах современных математиков А. Вейля, А. Гротендика, О. Зарисского, Ж.-П. Серра, И.Р. Шафаревича и др., затрудняется сложностью и громоздкостью этого инструментария, не рассчитанного на применение современных вычислительных систем. Все это обуславливает целесообразность развития специализированного инструментария, ориентированного на учет особенностей такого рода информации, решаемые на ее основе задачи и применение современных цифровых технологий больших данных (big data technology).

Селекция, являясь одним из общих методов системного анализа сложных объектов, применительно к обработке контурных изображений позволяет решить ряд таких прикладных задач, как выявление дубликатов изображений, распознавание изображений по заданным эталонам, выделение характерных признаков изображений и др.

В широком смысле, под селекцией понимают выделение в составе сцены заранее заданного объекта путем оценки способности каждого признака в разных классах различать классы, а не отождествлять объект с классом.

Селекция деталей машин - выявление различных классов контуров изображений путем оценки способностей каждого признака и состоит в том, что по измеренным значениям признаков всех наблюдаемых изображений деталей необходимо принять решение какой из объектов относится к интересующему

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

Существующие методы селекции контурных изображений требуют разделение всего множества деталей машиностроения путем выделения в деталях общих признаков класса, что связано с поиском этих признаков на всем множестве деталей. Кроме того, для всех деталей недопустимым является аффинное преобразование при их представлении. Это обусловливает актуальность разработки новых методов и алгоритмов селекции контурных изображений, ориентированных на реализацию современными высоко производительными вычислительными системами.

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

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

Степень разработанности. Существенный вклад в разработку общетеоретических основ методологии и развитие инструментальных средств обработки изображений внесли Галушкин А.И., Дмитриенко В.Д., Головко В.А., Путятин Е.П., Гроссберг С., Кохонен Т., Журавлев Ю.И., Филист С.А, С.В. Абламейко, Н. Ахмед, Р. Бейтс, Д.С. Ватолин, Ю. В. Визильтер, Р. Гонсалес, В.Г. Грибунин, И.С. Грузман, В.П. Дворкович, В.П. Дьяконов, Е.Г. Жиляков, Ю.И. Журавлев, В.Ф. Кравченко, Н.Н. Красильников, Дж. Миано, Е.П. Путятин, Ю.П. Пытьев, У. Прэтт, Ж. Серра, А.А. Сирота, В.А. Сойфер, Д. Сэломон, Д. Форсайт, Б. Хорн, Р. Шовенгердт, Б. Яне, Л.П. Ярославский, Дегтярев С.В. и др.

В работах, посвященных распознаванию изображений, достаточно полно решены задачи фильтрации, формирования контуров изображений, нахождение

особых угловых точек, выделение признаков изображения и использование этих признаков для отнесения изображения к эталонному. Как правило, задача селекции решается полным перебором эталонных контуров для выявления характерных признаков отдельных групп контуров изображений. Отнесение контура к соответствующей группе эталонных требует определение наличия признака группы в контуре изображения и сопряжено с большими трудностями, вносимым аффинным преобразованием распознаваемого контура, определения начальной особой точки для использования отношения эквивалентности двух контуров, а процедура селекции сопровождается существенным количеством ошибок первого рода. Эти факторы снижают эффективность поиска контуров эквивалентных эталону. В литературных источниках решение задачи повышения эффективности поиска при решении задач селекции отражено недостаточно.

Целью диссертационного исследования является повышение эффективности задач поиска контурных изображений в больших массивах графических данных за счет введенного алфавитного кодирования и аффинно-инвариантной селекции, реализованного средствами параллельного программирования.

Для достижения поставленной цели сформулированы следующие задачи:

1) Выполнить анализ существующих представлений и методов обработки контурных изображений.

2) Разработать алфавитную модель представления контурных изображений.

3) Разработать методы и процедуры построения алфавитных представлений контуров изображений инвариантных к аффинным преобразованиям контуров.

4) Разработать комплекс отношений эквивалентности на множестве контурных изображений, представленных последовательностями алфавитных символов.

5) Разработать алгоритмическое обеспечение селекции контурных изображений и отношений эквивалентности, с использованием их алфавитных представлений.

6) Разработать и программно реализовать алгоритмическое обеспечение селекции контурных изображений с использованием технологий Nvidia CUDA и в ходе вычислительных экспериментов выполнить оценку эффективности предложенных методов селекции.

Объект исследования - контурные изображения деталей машин.

Предмет исследования - методы распознавания контурных изображений.

Методы исследования. В работе использованы методы системного анализа, дискретной математики, теории принятия решений, теории обработки графической информации, параллельного программирования.

Научную новизну работы составляют:

1) Модель алфавитного представления контурных изображений, основанная на использовании предложенного алфавита кодонов и позволяющая обеспечить инвариантность относительно аффинных преобразований.

2) Комплекс отношений эквивалентности на множестве контурных изображений, позволяющий построить процедуру последовательного сокращения области поиска для класса, определяемого заданным эталонным контуром.

3) Мера сходства контурных изображений в признаковом пространстве алфавита кодонов, позволяющая сократить область поиска заданием степени близости к эталону.

4) Совокупность решающих правил по использованию отношений эквивалентности и меры сходства для выполнения селекции контурных изображений.

5) Использование введенных отношений эквивалентности и решающих правил для разработки алгоритмического обеспечения селекции контуров изображений на основе технологии NVIDIA CUDA.

Теоретическая значимость работы определяется развитием методов системного анализа применительно к решению задач селекции контурных

изображений, а так же во введении новых отношений эквивалентности и решающих правил селекции, приводящих к уменьшению множества эталонных контуров, к которым может быть отнесен распознаваемый контур изображения, что характеризует эффективность селекции, определяемую отношением разности исходного множества контуров с полученным подмножеством к исходному множеству при минимуме ошибок первого рода.

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

Практическая значимость работы состоит в применении программных реализаций разработанных алгоритмов, в том параллельных, в задачах мониторинга и управления при анализе изображений. Создан прикладной интерфейс поиска электронных схем и чертежей, который испытан в компании ООО «КОНСТРУКТОРСКОЕ БЮРО КВАНТА» и рекомендован для внедрения, что подтверждено актом опытно-промышленных испытаний. Методы и алгоритмы, разработанные в данном исследовании использованы в системе контроля и управления доступом в компании ООО «Технологии Надежности», что подтверждается соответствующими актами внедрения.

Связь с научными и инновационными программами. Работа связана с планами научно-исследовательских работ БелГУ, проводимых на кафедрах МИПОиС (математического и программного обеспечения информационных систем) и ПИиИТ (прикладной информатики и информационных технологий), поддержанных министерством наук РФ, проекты: 14.578.21.0138 и КЕМБЕ157815Х0138.

Область исследования. Содержание диссертации соответствует следующим пунктам паспорта специальности 05.13.01 Системный анализ, управление и обработка информации (технические науки):

- п.4. Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации;

- п.5. Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации.

Положения, выносимые на защиту:

1) Математическое и алгоритмическое обеспечение обработки графической информации, включающее комплекс процедур выделения контуров, определения узловых точек, аппроксимации фрагментов контуров изображений и построение алфавитных представлений контуров.

2) Комплекс процедур селекции контурных изображений, основанный на использовании алфавитных представлений и решающих правил с использованием введенных отношений эквивалентности и меры сходства.

3) Программная реализация алгоритмов селекции алфавитных представлений контуров изображений с использованием технологии СЦОА и результаты вычислительных экспериментов.

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

Личный вклад соискателя. Все изложенные в диссертации результаты исследования получены либо соискателем лично, либо при его непосредственном участии.

Апробация результатов диссертационного исследования. Результаты диссертационного исследования обсуждались на следующих научно-технических конференциях:

1) Всероссийская молодежная конференция Теория и практика системного анализа, Белгород, 1-3 октября 2012 г.

2) Международная молодежная конференция Прикладная математика, управление и информатика, Белгород, 3-5 октября 2012 г.

3) XII Всероссийская конференция, форум суперкомпьютерные технологии в образовании, науке и промышленности, Н. Новгород, 26-28 ноября 2012 г.

4) VIII международная научно-практическая конференция "Научные перспективы XXI века. Достижения и перспективы нового столетия" (Россия, г. Новосибирск, 13-14.02.2015 г.).

5) The 8th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS'2015) September 24-26, 2015 Warsaw, Poland.

6) Международная научная конференция «Проблемы информатики и математики», Харьков-Одесса, 13-16 сентября 2016г.

7) XX Международная конференция «Информатика: проблемы, методы, технологии» (IPMT-2020). 13-14 февраля 2020 года, город Воронеж.

Публикации. По материалам диссертационного исследования опубликовано 14 научных работ: 5 в рецензируемых изданиях, 7 из которых в изданиях, рекомендованных ВАК РФ и 2 статьи в журналах, индексируемых в базе Scopus. Получено 3 свидетельства о государственной регистрации программы для ЭВМ.

Структура и объем диссертации. Диссертационная работа состоит из введения, 4 глав, заключения, списка использованных источников и приложений.

Диссертационная работа изложена на 149 страницах основного текста, включающего 48 рисунков, 13 таблиц. Три приложения на 14 страницах и список использованных источников из 143 наименований.

ГЛАВА 1. Контурные изображения и методы их обработки

1.1 Общие положения, обзор методов решения задач распознавания и

селекции

Распознавание образов как часть методики принятия решений на основе результатов наблюдений за объектами и процессами окружающего мира появилась гораздо раньше, чем современные компьютерные системы и технологии. В ходе развития компьютерных и информационных технологий эта дисциплина, а также концепция распознавания значительно изменились и продолжает быстро развиваться. На текущий момент трудно точно определить класс проблем, которые касаются исключительно распознавания образов, и точно определить предмет изучения.

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

Под образом понимается «описание объекта или процесса, которое позволяет человеку отличать его от окружающей среды и группировать его с другими объектами или процессами для принятия необходимых решений» [1]. Те категории объектов, которые необходимо распознать или на которые должна быть разделена вся выборка изображений в процессе распознавания - называются классами, в работе [1] показан один из примеров классификации изображений.

Одним из подходов, который применяется для решения проблемы распознавания, является байесовский подход, основанный на условных вероятностях, а именно для измеренных значений признаков вычисляются условные апостериорные вероятности, затем эти вероятности сравниваются и

принимается решение на основании сравнения этих вероятностей. Такой подход обеспечивает минимум ошибок.

Приведем одну из простейших проблем распознавания, когда существует только два класса объектов. Чтобы присвоить наблюдаемому объекту первый класс, отношение правдоподобия, то есть отношение условной плотности

вероятности первого к измеренному значению характеристического вектора х1, ,хя к условной плотности вероятности второго, при значении характеристического векторах^'. А(х1, , • • •, должно быть

больше порога, который равен - - в свою очередь, и С2 - это элементы

платежной матрицы [2] за ошибочные решения отличаются от нуля, а за

правильные равны нулю, Р^), Р (П2) - априорные вероятности нахождения

объектов искомых классов.

Взяв во внимание все вышесказанное, можно вывести решающее правило:

(1.1)

а .....> ^ р (д2>

Го С*?.....О ' С1РФ1У

где Р (П,), - априорная вероятность появления ¿-го класса, I = 1,2,

С - плата за ошибки первого рода, С: - плата за ошибки второго рода,

с2 Р (Пя)

= Л0 отношение правдоподобия.

Таким образом, результат правила (1.1) зависит от вероятностей и элементов, указанных в матрице платежей.

Так же, описанная выше методика справедлива и для т классов. Решающее правило аналогично (1.1). Логика выплат за правильные и не правильные решения та же - за правильные 0, за неправильные 1, все вероятности появления объектов различных классов равны, а для поиска оптимального решения, согласно

соотношению (1.1), необходимо найти максимум вероятности в отношении • •, (хь • • •, Стоит отметить, что в таком случае правило (1.1) уже

не будет пороговым.

Для задачи распознавания входной информацией является генерация данных реальным источником, представляющим собой некий физический объект, погруженный в какую-то среду, процесс, эксперимент, экономическую систему и т.д. В свою очередь, выходная информация сводится к указанию класса.

Основная идея распознавания образов заключается в том, что данные, которые поступают с датчика отображаются в один класс. То есть представляя собой однозначное отображение, следовательно, все данные будут эквивалентны (хотя и различны) относительно релевантного образа, например, это можно проследить в работе [3]. На рисунке 1.1 представлена схема распознавания образов.

Рисунок 1.1 - Схема распознавания образов

На этой схеме датчик отвечает за поступление входных данных. Блок предварительной обработки выделяет из входных данных, признаки. Классификатор на основе признаков выносит решение о принадлежности к тому или иному классу.

Системы распознавание классифицируются на:

- простые;

- сложные;

- системы без обучения;

- системы с обучением;

- самообучающиеся системы;

- геометрические;

- спектральные;

- структурные;

- яркостные;

- статистические.

В зависимости, от информации, которая используется для описания объектов системы распознавания разделяют на простые и сложные. Если признаки, описывающие объект, имеют единую физическую природу, то системы считают простыми, в противном случае системы называют - сложными.

В случае, когда для классификации используется характер информации о признаках распознаваемых объектов, системы называют комбинированными, структурными, детерменированными или вероятностными.

В работах [4], авторы разделяют свои системы на обучающиеся с учителем, обучающиеся без учителя и самообучающиеся.

С учителем. Проводят первичную классификацию принудительно указывая класс распознаваемого объекта. Для этого процесса существует обучающее множество. В процессе обучения система учится корректно определять входную информацию и отображать ее в релевантные классы. На ряду с релевантными классами система так же должна определять объекты, не входящие в обучающее множество. Это можно увидеть на примере работы [5].

Без учителя. Распознавание без учителя можно использовать в том, случае если обучающая выборка не размечена. Обычно такие задачи решают при помощи кластерного анализа.

Для большинства задач, решающих проблему распознавания, используют корреляционные или признаковые методы (рисунок 1.2). Первые основываются на критерии близости эталона и образца. Вторые, соответственно, основываются на признаках, такие методы менее ресурсоемкие и требуют значительно меньший объем вычислений.

Многообразие методик распознавания изображений позволяет сделать вывод, что для каждой конкретной постановки задачи распознавания образов существует свои алгоритмы, позволяющие с той или иной степенью вероятности решить задачу эффективно.

Рисунок 1.2 - Методы распознавания изображений

В системах навигации, техническом зрении, слежении, промышленных роботах широкое применение получили корреляционные методы. Считается, что подобная процедура является базовой и обеспечивает наиболее высокую устойчивость к различным искажениям. Однако, наряду со своими преимуществами можно сказать, что так же подобные методы являются одними из самых трудоемких.

Признаковые методы являются менее ресурсоемкими и вычислительно сложными, так как работа идет не со всем изображением, а только с множеством его признаков, которая в общем случае значительно меньше, объема данных всего изображения. Синтаксические методы являются одними из наиболее проработанных. В их основе лежат статистические и детерминированные подходы. Основная сложность - это получение признаков.

На ряду с вышеописанными методами нельзя не упомянуть задачу селекции [6], которая является достаточно близкой к задаче распознавания. Главное отличие задачи селекции от задачи распознавания заключается в распознавании конкретного объекта в составе сцены, а не классификация этого объекта.

То есть задача селекции заключается в следующем: по найденным признакам всех наблюдаемых объектов необходимо понять, какой из этих объектов относится к эталонному классу [7]. В задаче селекции известно [8]:

- отношение распределения значений признаков

- распределение значений признаков для конкретного класса

- какая будет выборка исследуемых объектов

- какие исходы принимаются на основе обработки всей выборки

Для каждого из п объектов получены значения ..., л:^ (г = 1,...1п). Гипотеза Н^г = 1,... ,п) заключается в том, что ¿-ый объект относится к нужному классу, а все остальные (тг — 1) являются объектами других классов.

Обычно, в процессе распознавания, используют условные вероятности ошибочных решений [9]. В задачах селекции все виды решений образуют группу несовместных событий, в качестве искомого объекта случайным образом выбирают объект из фоновой группы. Вероятности нерелевантного и релевантного решений в совокупности равны единице. Обычно решающее

правило селекции имеет А, > Л,, V, Ф I —> (1.3) где Х{ = .....| - гипотеза,

состоящая в том, что ¿-ый объект относится к искомому классу, остальные объекты относятся к другому классу.

1.2 Понятие контурного изображения и контурный анализ

Контурное изображение (КИ), представляет собой изображение, созданное только контурами отдельных его элементов, например, чертежи и схемы [10]. Контур - это кривая, описывающая границу объекта на изображении и содержащая достаточно информации о форме объекта. Простой контур,

описывающий границу объекта на изображении без учета кривых внутри него, будем называть граничным. Примерами простых контуров могут служить карты границы континента, государства (рисунок 1.3).

Рисунок 1.3 - Пример простого контура

Сложный контур - это контур, в котором наряду с граничными учитываются кривые внутри граничного контура (рисунок 1.4). Примерами сложных контуров являются карты континента с кривыми, разделяющими границы разных государств; контур государства с кривыми тех или иных коммуникаций внутри этого государства, связывающие между собой несколько точек граничного контура (например, железные дороги).

Рисунок 1.4 - Пример сложного контура

Для работы с КИ используется метод контурного анализа [11] (КА) -описание, хранение, распознавание, сравнение и поиск графических образов (объектов) по их контурам. КА позволяет решать задачи распознавания образов,

достоинством данного метода является инвариантность к переносу, повороту, изменению масштаба.

В наиболее распространённых методах кодирования (например, код Фримена [12], полигональное кодирование, двумерное кодирование) контур - это граница объекта, то есть совокупность точек (пикселов), отделяющих объект от фона. Отличительной особенностью метода КА от упомянутых выше методов, в том, что в КА контур описывается совокупностью векторов смещения вида а+Л, где а - смещение точки по оси X, Ь - смещение по оси У [13] (рисунок 1.5).

Вектор-Контур 1

1ч 1ч

-14 -1 -1-н -1-н

1+1

Рисунок 1.5 - Контур в методе контурного анализа (КА)

Обход контура начинается с начальной точки, случайным образом, взятым на контуре, смещение осуществляется относительно предыдущей точки, при этом последний вектор смещения контура возвращается в начальную точку.

Так как контуры трехмерных объектов всегда замкнуты и не самопересекаются, можно однозначно определить пути обхода контура.

Список литературы диссертационного исследования кандидат наук Торопчин Дмитрий Анатольевич, 2021 год

СПИСОК ЛИТЕРАТУРЫ

1. Корсунов, Н.И. Метод классификации изображений на основе кластеризации сложных объектов/ Н.И. Корсунов, Д.А. Торопчин// Научные ведомости БелГУ. Сер. Экономика. Информатика. - 2016. - № 23 (244), вып. 40. -С. 100-103.

2. Вентцель, Е. С. Исследование операций/ Е. С. Вентцель. - Москва: «Советское радио», 1972. - 552 с.

3. Korsunov, N.I. Recognition method of near-duplicate images based on the perceptual hash and image key points using/ N.I. Korsunov, D.A. Toropchin// IDAACS'2015: proceedings of the 2015 IEEE 8th International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS), Warsaw, Poland, September 24-26, 2015. - P. 261-264.

4. Чабан, Л.Н. Теория и алгоритмы распознавания образов: учебное пособие/ Л.Н. Чабан. - Москва, 2004. - 236 с.

5. Корсунов, Н.И. Метод обучения персептрона распознаванию текстовых символов при зашумлениях/ Н.И. Корсунов, К.В. Лысых, Д.А. Торопчин // Научные ведомости БелГУ. Сер. Экономика. Информатика. - 2015. -№ 13 (210), вып. 35/1. - С. 99-103.

6. Потапов, А. А. Новейшие методы обработки изображений/ А. А. Потапов, А. А. Пахомов, С. А. Никитин, Ю. В. Гуляев. - Mосква: Физматлит, 2008. - 298 с.

7. Гнилицкий, В. В. Обнаружение и локализация объектов на изображениях трехмерных наземных сцен/ В. В. Гнилицкий, В. В. Инсаров // Известия РАН. Теория и системы управления. - 2011. - № 6. - с.79-87.

8. Горелик, А.Л. Общая постановка задачи распознавания объектов и явлений/ А.Л. Горелик// Кибернетика. - 1980. - №6. - с.72-75.

9. Местецкий, Л. М. Математические методы распознавания образов: курс лекций/ Л. М. Местецкий. - МГУ, ВМиК, кафедра «Математические методы прогнозирования», 2004. - 126 с.

10. Стефанов, С. И. Реклама и полиграфия: опыт словаря-справочника/ С. И. Стефанов. - Москва: Гелла-принт, 2004. - 320 с.

11. Фурман, Я.А. Введение в контурный анализ/ Я.А. Фурман. - Москва: Физматлит, 2003. - 592 с.

12. Баскаков, С.И. Радиотехнические цепи и сигналы/ С.И. Баскаков. -Москва: Высшая школа, 2016. - 446 с.

13. Родина, Т.В. Комплексные числа: учебно-методическое пособие/ Т.В. Родина. - СПб: СПбГУ ИТМО, 2009. - 30 с.

14. Гонсалес, Р. Цифровая обработка изображений/ Р. Гонсалес, Р. Вудс. -Москва: Техносфера, 2005. - 1007 с.

15. Патент 2362210. Российская Федерация. Устройство выделения контуров объектов на изображении/ Орлов А.В., Дегтярев С.В., Мирошниченко С.Ю. - 6 с.

16. LS. Davis A survey of edge detection techniques/ LS. Davis// Computer Graphics and Image Processing. - 1975. - vol 4, no. 3. - P. 248-260.

17. Duda R. Pattern Classification and Scene Analysis/ Duda R., Hart P. - John Wiley and Sons, 1973. - P. 271-272.

18. Prewitt, J.M.S. Object Enhancement and Extraction / J.M.S. Prewit. -Picture processing and Psychopictorics. Academic Press, 1970. - P. 389.

19. Kirsch, R. Computer determination of the constituent structure of biological images/ R. Kirsch// Computers and Biomedical Research. - 1971. - 4 (3). -315-328.

20. Robinson, G. Edge detection by compass gradient masks/ G. Robinson// Computer graphics and image processing. 1977. - 6. - P. 492-501.

21. Marr, D. Theory of edge detection Marr/ D. Marr, E. Hildreth// Proc. Royal Society of London, B. - 1980. - 207. - P. 187-217.

22. Зайцев, В. В. Элементарная математика/ В. В. Зайцев, В. В. Рыжков, М. И. Сканави. - Москва: Наука, 1976. - 591 с.

23. Young, Richard The Gaussian derivative model for spatial vision: I. Retinal mechanisms/ Richard Young// Spatial Vision. - 1987. - 2 (4) - Р.273-293.

24. Shapiro, L. Computer Vision/ Shapiro L. G. & Stockman G. C. - Prentice Hall, 2001. - Р.150.

25. Evans, L. Partial Differential Equations/ Evans L.// American Mathematical Society,1998. - 5. - P. 65-69.

26. Canny, J. A Computational Approach To Edge Detection / J. Canny// IEEE Transactions on Pattern Analysis and Machine Intelligence - 1986. - 8(6) - P. 679-698.

27. Тиман, А. Ф. Введение в теорию гармонических функций/ А. Ф. Тиман, В. Н. Трофимов - Москва: Наука, 1968. - 208с.

28. Дьяконов, В. П. Справочник по применению системы PC/ В. П. Дьяконов. - Москва: «Физматлит», 1993. - 112 с.

29. Ahlfors, Lars V. Complex analysis. An introduction to the theory of analytic functions of one complex variable. /Ahlfors Lars V. //Third edition. - Harvard University:McGraw-Hill Book Company, 1979. - 317 с.

30. Свешников, А. Г. Теория функций комплексной переменной/ А. Г. Свешников, А. Н. Тихонов - Москва: Наука, 1967. - 304 с.

31. Соломенцев, Е. Д. Функции комплексного переменного и их применения/ Е. Д. Соломенцев. - Москва: Высшая школа, 1988. - 167 с.

32. Crowe, M. J. A History of Vector Analysis. The Evolution of the Idea of a Vectorial System/ M. J. Crowe //Courier Dover Publications. - 1994. - P. 32 - 270.

33. Виноградов, И.М. Векторная алгебра: математическая энциклопедия / И.М. Виноградов - Москва: Советская Энциклопедия, 1977. - Т. 1. - 634 c.

34. Bounjakowsky, W. Mémoires de l'Académie des sciences de St-Pétersbourg. 7 série» /Bounjakowsky W. - 1859. - № 9.

35. Фурман, Я.А. Введение в контурный анализ приложения к обработке изображений и сигналов/ Я.А. Фурман, А.В. Кревецкий, А.К. Передреев, А.А. Роженцов, Р.Г. Хафизов, И.Л. Егошина, А.Н. Леухин - Москва: ФИЗМАТЛИТ, 2003. - 592 с.

36. Charles, Therrien/ Probability and Random Processes for Electrical and Computer Engineers/ Charles Therrien, Murali Tummala. - CRC Press, 2012. - P. 287.

37. Tenopir, С. Communication patterns of engineers / Carol Tenopir, Donald W. King. - IEEE// Wiley InterScience, 2004. - P. 2бб.

38. Allard, S. Design Engineers and Technical Professionals at Work: Observing Information Usage in the Workplace / S. Allard, K.J. Levine, C. Tenopir // Journal of the American Society for Information Science and Technology. - 2009. - P. 443-454.

39. Court, A. W. The influence of information technology in new product development: Observations of an empirical study of the access of engineering design information / Andrew W. Court, Stephen J. Culley, Christopher A. McMahon // International Journal of Information Management. - 1997. - P. 359-375.

40. Gessesse. Scientific communication, electronic access, and document delivery: The new challenges to the science/engineering reference librarian / Gessesse, Kebede // International Information and Library Review. - 1994. - P. 341-349.

41. Carstensen, P. H. Towards information exploration support for engineering designers / Peter H. Carstensen // Advances in Concurrent Engineering (CE97). - l997.

- P. 2б-ЗЗ

42. McMurry, D. Defense Parts Management. Program Update / Donna McMurry // Defense Standardization Program Journal. - 2008. - P. 3-11.

43. Wemmerlöv, U. Cellular manufacturing in the U.S. industry: A survey of users / U. Wemmerlöv, N. L. Hyer // International Journal of Production Research. -1989. - P. 1511-1530.

44. Техническое зрение в системах управления мобильными объектами 2010: Труды научно-технической конференции-семинара/ Под ред. Р.Р. Назирова.

- Москва: КДУ, 2011. - 328 с.

45. BERNSEN, J. Dynamic thresholding of gray-level images/ J. BERNSEN// In Int. Conf. Pattern Recognition. - 198б. - 1251- 1255 c.

46. Lienhart, R. An extended set of Haar-like features for rapid object detection / R. Lienhart, J. Maydt, // ICIP02, 2002. - P.900-903.

47. Herbert, Bay Speeded Up Robust Features/ Bay Herbert, Ess Andreas, Tuytelaars Tinne, Luc Van Gool //ETH Zurich, Katholieke Universiteit Leuven, 2006 -P.14.

48. Patent, U.S. Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image/ David Lowe's patent for the SIFT algorithm, March 23, 2004. - P.91.

49. Papageorgiou, C. A general framework for object detection»/ C. Papageorgiou, M. Oren, T. Poggio// International Conference on Computer Vision -1998 - P.15.

50. Фурман, Я. А. Цифровые методы обработки и распознавания бинарных изображений / Я. А. Фурман, А. Н. Юрьев, В. В. Яншин. - Красноярск: Изд-во Краснояр. ун-та, 1992. - 245 с.

51. Eckstain, R. Interactive Search Processes in Complex Work Situations - A Retrieval Framework/ R. Eckstain//Bamberg: University of Bamberg Press, 2011. - 223 p.

52. Классификатор ЕСКД. Введение. - М.: Издательство стандартов, 1988. -

20 с.

53. ГОСТ 2.102-68 Единая система конструкторской документации. Виды и комплектность конструкторских документов. - М.: Изд-во стандартов, 2002. - С. 38-45.

54. ГОСТ 2.109-73 Единая система конструкторской документации. Основные требования к чертежам. - М.: Изд-во стандартов, 2002. - С. 119-143.

55. Митрофанов, С. П. Групповая технология машиностроительного производства: В 2-х т. Т. 1. Организация группового производства / С. П. Митрофанов. - Ленинград: Машиностроение, 1983. - 407 с.

56. Митрофанов, С. П. Групповая технология машиностроительного производства: В 2-х т. Т. 2. Проектирование и использование технологической оснастки металлорежущих станков/ С. П. Митрофанов. - Ленинград: Машиностроение, 1983. - 376 с.

57. Михелев, В.М. Метод поиска изображений по визуальному подобию на основе гибридных технологий параллельного программирования / В.М. Михелев, К.В. Кузнецов, Д.В. Петров, Д.А. Торопчин// Сб. трудов междунар. молодежной конф., Белгород, 3-5 окт. 2012 г.: в 2 т. - 2012. - Т. 1. - С. 463-467.

58. Bhatti, N. Image search in patents: a review / N. Bhatti, A. Hanbury // International Journal on Document Analysis and Recognition. - 2013. - Vol. 16, Is. 4. -P. 309-329.

59. Кузнецов, К.В. Суперкомпьютерные технологии в задаче поиска изображений по визуальному подобию/ К.В. Кузнецов// Высокопроизводительные параллельные вычисления на кластерных системах: Нижегор. гос. ун-т.- 2012. - С. 231-235.

60. Fonseca, M. J. Content-based retrieval of technical drawings / M.J. Fonseca, A. Ferreira, J.A. Jorge // International Journal of Computer Applications in Technology.

- 2005. - Vol. 23, No. 2-4. - P. 86-100.

61. Sousa, P. Sketch-based retrieval of drawings using spatial proximity / P. Sousa, M.J. Fonseca // Journal of Visual Languages and Computing. - 2010. - Vol. 21, Is. 2. - P. 69-80.

62. Fonseca, M. J. Sketch-Based Retrieval of Vector Drawings / M. J. Fonseca, A. Ferreira, J. A. Jorge // Sketch-based Interfaces and Modeling. - 2011. - Vol. 12. - P. 181-204.

63. Cvetkovic, D. Eigenspaces of Graphs / D. Cvetkovic, P. Rowlinson, S. Simic.

- UK: Cambridge University Press, 1997. - 276 p .

64. Liu, R. Attributed Graph Matching Based Engineering Drawings Retrieval / R. Liu, T. Baba, D. Masumoto // Lecture Notes in Computer Science. - 2004. - Vol. 3163. - P. 378-388.

65. Препарата Ф, М. Вычислительная геометрия: Введение / Ф.Препарата, М.Шеймос - Москва: Мир, 1989. - 295 с.

66. Liu, R. Shape detection from line drawings with local neighborhood structure / R. Liu, Y. Wang, T. Baba, D. Masumoto // Pattern Recognition. - 2010. - Vol. 43, Is. 5. - P. 1907-1916

67. Jiao, L. An Engineering Drawings Retrieval Method based on Density Feature and improved Moment Invariants / L. Jiao, F. Huang, Z. Teng // Proceedings of the 2009 International Symposium on Information Processing. - 2009. - P. 352-355.

68. Huet, B. Relational Skeletons for Retrieval in Patent Drawings / B. Huet, N.J. Kern, G. Guarascio, B. Merialdo // Proceedings of the International Conference on Image Processing. - 2001. - Vol. 3. - P. 737-740.

69. Huet, B. Fuzzy relational distance for large-scale object recognition / B. Huet, E.R. Hancock // Conference on Computer Vision and Pattern Recognition. - 1998. - P. 138-143.

70. Huet, B. Line pattern retrieval using relational histograms / B. Huet, E.R. Hancock // Pattern Analysis and Machine Intelligence. - 1999. - Vol. 21, Is. 12. - P. 1363-1370.

71. Pu, J. On visual similarity based 2D drawing retrieval / J. Pu, K. Ramani // Computer-Aided Design. - 2006. - Vol. 38, Is. 3. - P. 249-259.

72. Franti, P. Content-based matching of line-drawing images using the Hough transform / P. Franti, A. Mednonogov, V. Kyrki, H. Kalviainen // International Journal on Document Analysis and Recognition. - 2000. - Vol. 3, Is. 3. - P. 117-124.

73. Leavers, V. F. Survey: Which Hough Transform? / V.F. Leavers // CVGIP Image Understanding. - 1993. - Vol. 58, Is. 2. - P. 250-264.

74. Rubner, Y. A metric for distributions with applications to image databases/ Y. Rubner, C. Tomasi, L.J. Guibas // IEEE International Conference on Computer Vision. -1998. - January - P. 59-66.

75. Tabbone, S. Indexing of Technical Line Drawings Based on F-Signatures/ S. Tabbone, L. Wendling, K. Tombre // ICDAR'01 Proceedings. - 2001. - P. 1220-1224.

76. CADFind - Design Retrieval The Comprehensive Solution [Электронный ресурс]. - Системные требования: Adobe PDF Reader. - Режим доступа: http://www.cadfind3d.com.

77. Love, D. Aspects of design retrieval performance using automatic GT coding of 2D Engineering Drawings/ D. Love, J. Barton // IDDME 2004 Proceedings, 2004. -351 p.

78. Hou, S. Structure-oriented contour representation and matching for engineering shapes/ Suyu Hou, Karthic Ramani // Computer-Aided Design. - 2008. - P. 94-108.

79. Latecki, L. J. Convexity rule for shape decomposition based on discrete contour evolution/ L.J. Latecki, R. Lakamper // Computer Vision and Image Understanding. - 1999. - Vol. 73, Is. 3. - P. 441-454.

80. Arkin, E. An efficiently computable metric for comparing polygonal shapes/ E. Arkin, L. Chew, D. Huttenlocher, K. Kedem, J. Mitchell // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 1991. - Vol. 13, Is. 3. - P. 209-216.

81. Belongie, S. J. Shape matching and object recognition using shape contexts / S.J. Belongie, J. Malik, J. Puzicha // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2002. - Vol. 24, Is. 4. - P. 509-522.

82. Korsunov, N. I. The method of finding the spam images based on the hash of the key points of the image/ S. J. Belongie, D.A. Toropchin // International Journal of Computing. - 2016. - Vol. 15, № 4. - P. 259-264.

83. Корсунов, Н.И. Метод построения спам-фильтра для поиска нечетких дубликатов изображений/ Н.И. Корсунов, Д.А. Торопчин / Информационные системы и технологии. - 2017. - № 1 (99). - С. 13-20.

84. Лысых, К.В. Распознавание изображений на основе аппроксимации функций комбинированных нейронных сетей. / К.В. Лысых, Н.И. Корсунов, Д.А. Торопчин // Информационные системы и технологии - 2015. № 5 (91). - С. 105109.

85. Bang-Jensen, J. When the greedy algorithm fails. / J. Bang-Jensen, G. Gutin and A. Yeo // Discrete Optimization 1- 2004, - P. 121-127.

86. Nomizu, K. Affine Differential Geometry (New ed.), / N. Press, K. Sasaki // Cambridge University, 1994. - 113 p.

87. Beets, K. Super-sampling [Electronic resource]/ K. Beets, B. Dave // -2020. -April 19. -Режим доступа: http://www.x86-secret.com/articles/divers/v5-6000/datasheets/FSAA.pdf .

88. Напалков, В. В. Уравнения свертки в многомерных пространствах/ В. В. Напалков.- М., Наука, 1982. - 240 с.

89. Burger, W. Principles of digital image processing: core algorithm/ W. Burger, Mark J. Burge // Springer. -2009. - P. 231-232.

90. Burger, W. Principles of Digital Image Processing Core Algorithms/ W. Burger, Mark J. Burge // Springer Science & Business Media. -2010. - P. 110-111.

91. Сойфер, В.А. Методы компьютерной обработки изображений/ В.А. Сойфер. - М.: ФИЗМАТЛИТ, 2003. - C. 91

92. Zuiderveld K. Contrast limited adaptive histogram equalization/ K. Zuiderveld // Graphics Gems IV, 1994. - Chapter VIII.5. - P. 474-485.

93. Huang, D. A fast two-dimensional median filtering algorithm/ D. Huang, S. T. Yang, M. George, Y. Gregory // IEEE Transactions on Acoustics, Speech, and Signal Processing. - 1979. - February 27 - P. 13-18.

94. Koenderink, J. Representation of local geometry in the visual system / J. Koenderink, A. van Doorn // Biological Cybernetics. - 1987. - P. 383-396.

95. Moravec, H. Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover/ H. Moravec // Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute. - 1980. - P. 237-267.

96. Harris, C. A combined corner and edge detector/ C. Harris, M. Stephens // Proceedings of the 4th Alvey Vision Conference. - 1988. -P. 147-151.

97. Shi, J. Good Features to Track/ J. Shi C. Tomasi // 9th IEEE Conference on Computer Vision and Pattern Recognition. -1994. -June. -P. 593-600.

98. Forstner, W. A Fast Operator for Detection and Precise Location of Distinct Points, Corners and Centres of Circular Features/ Forstner W., Gulch// Proc. ISPRS intercommission conference on fast processing of photogrammetric data. - 1987. - pp. 281-305.

99. Smith, S. M. SUSAN - a new approach to low level image processing/S. M. Smith, J. M. Brady// International Journal of Computer Vision. - 1997. - №23. - pp. 45-78.

100. Bae, S.C. COP: a new corner detector./S.C Bae., I.S. Kweon and C.D. Yoo.// Pattern Recognition Letters. - 2002.

101. Montero, A. S. Robust Detection of Corners and Corner-line links in images/ Andres Solis Montero, Milos Stojmenovic, Amiya Nayak// 10th IEEE International Conference on Computer and Information Technology. - 2010.

102. Mikolajczyk, K. A performance evaluation of local descriptors/ Mikolajczyk K., Schmid C.// PAMI. - 2005. - Vol. 27. - P. 1615-1630.

103. Gauglitz, S. Evaluation of interest point detectors and feature descriptors for visual tracking /Gauglitz, S., Hollerer T., Turk M.// International Journal of Computer Vision. - 2011. - P. 1-26.

104. Макаров, А.С. Сравнительный анализ методов обнаружения особых точек на изображениях при различных уровнях освещения/Макаров, А.С., Болсуновская М.В.// Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. - 2018. - № 11:2. - C. 7-18.

105. Mikolajczyk, K. An affine invariant interest point detector / Mikolajczyk K., Schmid C.// In Heyden A., Sparr G., Nielsen M., Johansen P. ECCV LNCS. - 2002. - Vol. 2350. - P. 128-142.

106. Mikolajczyk, K. Scale and Affine invariant interest point detectors/ Mikolajczyk, K., Schmid C.// In IJCV. - 2004. - Vol. 60 (1). - P. 63-86.

107. Accurate Junction Detection and Characterization in Natural Images GuiSong Xia, Julie Delon, Yann Gousseau Telecom ParisTech, LTCI CNRS, 46, rue Barrault, 75013 Paris, France {xia,delon,gousseau}@enst.fr

108. Abhishak Yadav, Poonam Yadav. Digital Image Processing, 2009.

109. Михелев, В.М. Параллельные вычисления при распознавании нечетких текстовых дубликатов на основе технологии CUDA /Михелев В.М., Кузнецов К.В., Торопчин Д.А.//Вопросы радиоэлектроники. Серия Электронная вычислительная техника (ЭВТ). - 2012. - Т. 4, № 1. - С. 20-27. (№ 620 из Перечня изданий ВАК от 17.06.2011).

110. Use your Nvidia GPU for scientific computing [Электронный ресурс]. -BOINC, 2008.

111. Хеллман, Даг. Стандартная библиотека Python 3: справочник с примерами/ Хеллман Даг.//2-е изд.: Пер. с англ. - СПб.: ООО «Диалектика», 2019.

- 1376 с.

112. OracleJVM and Java Stored Procedures (англ.). Oracle Inc. [Электронный ресурс]. — Раздел портала Oracle, посвящённый технологиям Java в составе сервера СУБД Oracle.

113. Khailany, B. K. A Programmable 512 GOPS Stream Processor for Signal, Image, and Video Processing/Brucek K. Khailany, Ted Williams, Jim Lin, Eileen Peters Long, Mark Rygh, DeForest W. Tovey, William J. Dally//IEEE Journal of SolidState Circuits. - 2008. - Vol. 43. - p. 202 - 213.

114. CUDA Toolkit Documentation v11.2.0 [Электронный ресурсу/NVIDIA.

- Режим доступа: https://docs.nvidia.com/cuda/.

115. Андронов, А. А. Теория бифуркаций динамических систем на плоскости/ Андронов А. А., Леонтович Е. А., Гордон И. М., Майер А. Г. - М.: Наука, 1967.

116. Di Battista, Giuseppe Graph Drawing: Algorithms for the Visualization of Graphs./ Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. -Prentice-Hall, 1999. - p. 397

117. Борисович, Ю. Г. Введение в топологию/ Борисович Ю. Г., Близняков Н. М., Израилевич Я. А., Фоменко Т. Н. - М.: ЛЕНАНД, 2015.

118. Фихтенгольц, Г. М. Функции нескольких переменных/ Фихтенгольц, Г. М. - М.: ФМЛ, 1962. - 608 с.

119. Харари, Ф. Теория графов./ Харари Ф. - М.: УРСС, 2003. - 300 с.

120. Abeysinghe, Sasakthi Segmentation-free skeletonization of grayscale volumes for shape understanding/ Abeysinghe Sasakthi, Baker Matthew, Chiu Wah, Ju Tao// IEEE Int. Conf. Shape Modeling and Applications. - 2008. - pp. 63-71.

121. Widiarti, A.R. Comparing Hilditch, Rosenfeld, ZhangSuen, and Nagendraprasad-Wang-Gupta Thinning / A.R. Widiarti // International Journal of Computer, Electrical, Automation, Control and Information Engineering. - 2011. - Vol. 5(6). - P. 20-24.

122. Zhang, T.Y. A Fast Parallel Algorithm for Thinning Digital Patterns / T.Y. Zhang, C.Y. Suen // Communications of the ACM. - 1984. - Vol. 27, Issue 3. - P. 236239. - DOI: 10.1145/357994.358023.

123. Freeman, H. On the encoding of arbitrary geometric configurations / H. Freeman // IRE Transactions on Electronic Computers - 1961 - №10 - P. 260-268.

124. Jepson, Allan CSC420: Image Features / Jepson Allan // Readings: Szeliski

- 2011 - September - Section 4.1 and 4.2.

125. Выделение и описание контуров [Электронный ресурс]. - Википедия.

- Свободная энциклопедия. - Режим доступа: http://wiki.technicalvision.ru/index.php?title=Выделение_и_описание_контуров.

126. Korsunov, N.I. The theory of codons for pattern recognition. / Korsunov N.I., Toropchin D.A.// Проблеми шформатики та моделювання: тезиси шютнадцято 1 мiжнародно 1 науково-техшчно I конф. Харюв-Одесса.: М-ВО освгги i науки Украши, НАН Укра1ни, Нац. техн. ун-т «Харювський полггехшчний ш-т». - 12-16 вересня 2016. - С. 42.

127. Лоран, П. Ж. Аппроксимация и оптимизация/ П. Ж. Лоран. - М.: Мир, 1975. - С. 496.

128. Shu, Jian-Jun A new integrated symmetrical table for genetic codes / Jian-Jun, Shu // BioSystems. - 2017 - №151 - P. 21-26.

129. Левитин, А. В. Метод преобразования: Схема Горнера и возведение в степень. Алгоритмы. Введение в разработку и анализ/ А. В. Левитин. - Москва: Вильямс, 2006. - 576 с.

130. Белага, Э. Г. О вычислении значений многочлена от одного переменного с предварительной обработкой коэффициентов. Проблемы кибернетики / Э. Г. Белага. - М.: Физматгиз, 1961, 589 с.

131. Карминская, Т.Д. Математическая модель оценки показателей качества деятельности системы однородных объектов / Т.Д. Карминская, В.З. Ковалев, П.И. Ципорин // Доклады ТУСУРа. - 2011 - № 2. - С. 27-32.

132. Болдырев, В.И. Метод кусочно-линейной аппроксимации для решения задач оптимального управления, дифференциальные уравнения и процессы

управления / В.И. Болдырев // Электронный журнал, рег. N П23275 от 07.03.97. -2004. - №1.

133. Korsunov, N.I. Procedure for selection of contour images based on the relations of equivalence / N.I. Korsunov, V.A. Lomazov, D.A. Toropchin // Colloquium-journal. - 2019. - № 26-1. - С. 57-58.

134. Кузнецов, К.В. Метод поиска нечетких дубликатов изображений на основе гибридных технологий параллельного программирования/ Кузнецов К.В., Михелев В.М., Петров Д.В., Торопчин Д.А.// Теория и практика системного анализа: сб. трудов всерос. молодежной конф., Белгород 1-3 окт. 2012 г. М-во образования и науки РФ, Департамент образования, культуры и молодежной политики Администрации Белгор. обл., РАН, Ин-т системного анализа, НИУ «БелГУ». - Белгород, 2012. - С. 264-267.

135. Howard, Anton. Elementary Linear Algebra (7th ed.)/ Howard Anton// John Wiley & Sons,1994. - P. 170-171.

136. Krause, Eugene F. Taxicab Geometry. Dover / Eugene F., Krause, - 1987.

- P. 136.

137. Воеводин, В.В. Параллельные вычисления / В.В. Воеводин. - Санкт-Петербург: БХВ, 2002. - 608 с.

138. Herlihy, Maurice. The Art of Multiprocessor Programming / Morgan Kaufmann, Maurice Herlihy - 2008. - P. 231.

139. Bondi, André B. Characteristics of scalability and their impact on performance. Proceedings of the second international workshop on Software and performance. / André B. Bondi - 2000. - P. 195.

140. Карпов, В.Е. Введение в распараллеливание алгоритмов и программ/ В.Е. Карпов // Компьютерные исследования и моделирование. - 2010. - т. 2, № 3.

- С. 231-272.

141. Mark D. Hill Amdahl's Law in the Multicore Era / Mark D. Hill, Michael R. Marty // Computer. - 2008. - 41 (7). - Р. 33-38.

142. Батищев, Д.С. Архитектура программно-аппаратной поддержки распознавания нечетких дубликатов изображений / Д.С. Батищев, А.С Медведев,

В.М. Михелев, Д.А. Торопчин // Вопросы радиоэлектроники. Сер. Электронная вычислительная техника (ЭВТ). - 2014. - Т. 4, № 2. - С. 78-88.

143. Hou, S. Structure-oriented contour representation and matching for engineering shapes / Suyu Hou, Karthic Ramani // Computer-Aided Design. - 2008. -Vol. 40, Is. 1. - P. 94-108.

РОССИЙСКАЯ ФЕДЕРАЦИЯ Общество с ограниченной ответственностью «Технологии Надежности»

Адрес: 308033, г. Белгород, ул. Королева, 2ак2, офис 549 Тел.: [phone] E-mail: [e-mail]

об использовании методов и алгоритмов поиска нечетки» дубликатов изображений с применением технологий параллельного программирования

1. Настоящий акт составлен о том, что ООО «Технологии Надежное™» приняло к использованию, в выполняемых работах, разработанные Торопчиным Д.А. методы и алгоритмы поиска нечетких дубликатов изображений с применением технологий параллельного программирования.

2. В основе методов и алгоритмов лежит использование теории кодонов для выделения ключевых особенностей изображения, а так же модифицированные алгоритмы перцептивного хеширования для построения дескрипторов ключевых особенностей изображений. Для ускорения методов и алгоритмов разработаны их параллельные аналоги и реализованы с использованием таких технологий, как: MPI, OpenMP и Nvidia CUDA.

3. Применение этих методов и алгоритмов позволяет производить эффективный поиск нечетких дубликатов изображений более адекватно, нежели широко используемые для этой задачи методы (классические алгоритмы перцептивного хеширования (phash, dethash), алгоритмы выделения ключевых особенностей (Moravec, Hanis, SUSAN, Trajkovic, CSS)).

г. Белгород

14.09.2018

АКТ

Директор

ООО «Технологии Надежности»

Дубовицкий А.Н.

ООО КБ «Кванта» 308000, г. Белгород улица Королева, д.2а

УТВЕРЖДАЮ Директор

Перваков В.В

«

¿У"» ноЛ^э*_2018

АКТ

О внедрении (использовании) результатов Диссертационной работы Торопчина Дмитрия Анатольевича

Комиссия в составе: председатель - Перваков В В., члены комиссии: Дубовицкий А.Н. составила настоящий акт о том, что результаты диссертационной работы Торопчина Д А. использованы в работе ООО КБ «Кванта», в следующем виде:

I Программных модулей поиска схем, планов и чертежей в архивных хранилищах

2. Методических рекомендаций по использованию системы графического поиска схем, планов, чертежей в архивных хранилищах данных. Использование указанных результатов позволяет:

осуществлять поиск чертежей, планов, схем в архивных хранилищах данных, опираясь на символьные признаки контурных изображений и многоэтапную процедуру поиска контурных изображений:

1. Существенно повысить качество поиска;

2. Сократить сроки проектирования новых изделений;

3. Устранить дублирование элементов (графических изображений);

данных.

Члены комиссии:

Председатель комиссии:

Дубовиций А.Н.

Перваков В.В.

Фрагмент исходного кода разработанной программы.

import copy

import warnings

import cv2 import math as m import networkx as nx import numpy as np

warnings.simplefilter(' ignore', np.RankWarning)

from matplotlib import pyplot as plt

from skimage.morphology import skeletonize

from additions import show_image

class Line():

def_init_(self, filepath, mode='skelet', withshow=False, polynom=10, p_size=3000, img_size = 300):

self.filename = filepath self.img_size = img_size self.g_point = [] self.polynom = polynom self.p_size = p_size

self.all_pathes = self._build_all_pathes(filepath, mode) self.cadons = self.run(withshow)

def _angle_between_two_points(self, x1, y1, x2, y2): deltax = x2 - x1 deltay = y2 - y1

angle_rad = m.atan2(deltay, deltax) angle_deg = angle_rad * 180.0 / m.pi

# print("The angle is %.5f radians (%.5f degrees)." % (angle_rad, angle_deg))

return angle_deg

def _bug_met(self, img, i, j): try:

# if sum(img[i][j]) == 255 * 3: if img[i][j] == 255:

return True else:

return False except IndexError as e:

pass

# print('[Error]: {}'.format(e})

# print('index: {},{}'.format(i, j))

def _build_all_pathes(self, filepath, mode): img = self.open_img(filepath) img, binar = self.perimetr(img)

if mode == 'schema':

img = self._clean_schema(img)

n_img, img = self._find_spec_points(img) h, w, c = img.shape img = binar

# img = self.open_img(filepath, gr=True) if mode == 'skelet':

img = self._skelet(img)

# HARISS SHOW self.show_haris(img)

img = self._coloring_g_point(img) all_pathes = {} for i in range(h): for j in range(w):

if self._bug_met(img, i, j):

# show_image(img, wait_time=20, scale=2, namewin='ll', close=False) # GIF path = []

path.append([i, j]) self._find_path(img, i, j, path) if len(path) > 1:

all_pathes[i, j, path[-1][0], path[-1][1]] = path img [path[- 1][0]][path[-1][1]] = 0

points = list(all_pathes) for i in range(len(points)): for j in range(len(points)): if len(points) > 2:

if self.calc_dist(points[i][0], points[i][1], points[j][2], points[j][3]) and i ! = j: p1 = all_pathes[points[i][0], points[i][1], points[i][2], points[i][3]] p2 = all_pathes[points[j][0], points[j][1], points[j][2], points[j][3]] all_pathes[p2[-1][0], p2[-1][1], p1[-1][0], p1[-1][1]] = p2 + p1

# cut line by small lines all_pathes_new = {}

for k, v in all_pathes.items(): if len(v) > self.p_size:

parts = len(v) // self.p_size

for i in range(parts + 1):

all_pathes_new[k, i] = all_pathes[k][self.p_size * i:self.p_size * (i + 1)]

else:

all_pathes_new[k] = v del all_pathes

all_pathes = all_pathes_new

# REMOVE short points

for i in list(all_pathes.items()): if len(i[1]) == 2: del all_pathes[i[0]]

return all_pathes

def _coloring_g_point(self, img):

# part with G point - each path end on g_point for i in self.g_point:

img[i[0], i[1]] = 0 try:

img[i[0]+1, i[1]] = 0 img[i[0]+1, i[1]-1] = 0 img[i[0], i[1]+1] = 0 img[i[0]+1, i[1]+1] = 0 img[i[0] - 1, i[1]] = 0 img[i[0] - 1, i[1]+1] = 0 img[i[0], i[1] - 1] = 0 img[i[0] - 1, i[1] - 1] = 0 except:

print('Error: _coloring_g_point() out of range index!')

return img

def _find_path(self, img, i, j, path):

# global path triger = False

if self._bug_met(img, i + 1, j): # d path.append([i + 1, j]) triger = True elif self._bug_met(img, i + 1, j - 1): # d+l path.append([i + 1, j - 1]) triger = True elif self._bug_met(img, i, j - 1): # l path.append([i, j - 1]) triger = True elif self._bug_met(img, i - 1, j - 1): # u+l path.append([i - 1, j - 1]) triger = True

elif self._bug_met(img, i - 1, j): # u path.append([i - 1, j]) triger = True elif self._bug_met(img, i - 1, j + 1): # u+r path.append([i - 1, j + 1]) triger = True elif self._bug_met(img, i, j + 1): # r path.append([i, j + 1]) triger = True elif self._bug_met(img, i + 1, j + 1): # r+d path.append([i + 1, j + 1]) triger = True

# print(len(path))

if triger: img[i][j] = 0

self._fmd_path(img, path[-1][0], path[-1][1], path)

def _clean_schema(self, img): for idx, i in enumerate(img): for jdx, j in enumerate(i): if j[0] == j[1] == j[2] or (j[2] > j[1] and j[2] > j[0] or abs(40 > j[0] - j[1] > 0)): img[idx][jdx] = [255, 255, 255] img = cv2.resize(img, (self.img_size, self.img_size)) for idx, i in enumerate(img): for jdx, j in enumerate(i): if sum(j) < 255 * 3: img[idx][jdx] = [255, 0, 0]

# show_image(img, wait_time=0, namewin-AFTER CLEAN', scale=1, close=False)

return img

def _find_spec_points(self, img):

gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) canny = cv2.Canny(img, 127, 250)

# show_image(canny, namewin='CANNY',wait_time=0, scale=2, close=False) gray = np.float32(gray)

dst = cv2.cornerHarris(gray, 2, 3, 0.12)

dst = cv2.dilate(dst, None)

_, dst = cv2.threshold(dst, 0.01 * dst.max(), 255, 0)

dst = np.uint8(dst)

_, labels, stats, centroids = cv2.connectedComponentsWithStats(dst)

criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 100, 0.001)

corners = cv2.cornerSubPix(gray, np.float32(centroids), (5, 5), (-1, -1), criteria)

# draw corners

res = np.hstack((centroids, corners))

res = np.intO(res) img[:,:, :] = [0, 0, 0] for idx, i in enumerate(canny): for jdx, j in enumerate(i): if j == 255: for kdx, k in enumerate(res):

if self.calc_dist(res[kdx][1], res[kdx][0], idx, jdx): self. g_point. append([res[kdx][1], res[kdx][0]]) res[kdx] = [0, 0, 0, 0] img[idx][jdx] = [255, 255, 255] # make white contour n_img = copy.copy(img) cv2.imwrite('./data/out/subpixel5.png', canny)

return n_img, img

def _polynomial(self, xdata, coefs): _coefs = [0, 0, 0, 0, 0, 0, 0, 0] for idx, i in enumerate(list(reversed(coefs))): _coefs[idx] = i

y = []

for x in xdata: y.append(_coefs[6] * x ** 6 + _coefs[5] * x ** 5 + \ _coefs[4] * x ** 4 + _coefs[3] * x ** 3 + \ _coefs[2] * x ** 2 + _coefs[1] * x ** 1 + \ _coefs[0])

return y

def _polyn_np(self, xdata, coefs):

y = []

for i in xdata: y.append(np.polyval(coefs, i))

return y

def _rotate_line(self, line):

# point 1

x1 = line[0][0] y1 = line[0][1]

# point 2

x2 = line[-1][0] y2 = line[-1][1]

ang = self._angle_between_two_points(x1=x1, y1=y1, x2=x2, y2=y2) return self._turn(line=line, param_angle=-ang) def _sr_ot(self, y1, y2):

summ = 0

for idx, i in enumerate(yl):

summ += (yl [idx] - y2[idx]) ** 2

return summ

def _skelet(self, img, th1=200, th2=255):

# for schemas special thresh params

_, img = cv2.threshold(img, thl, th2, cv2.THRESH_BINARY_INV)

# show_image(img, namewin='after') for idx, i in enumerate(img):

for jdx, j in enumerate(i): ifj > 0:

img[idx][jdx] = 1 else:

img[idx][jdx] = 0 skelet = skeletonize(img) for idx, i in enumerate(skelet): for jdx, j in enumerate(i): ifj:

img[idx][jdx] = 255 else:

img[idx][jdx] = 0

# show_image(img, namewin='skeleton', scale=1, wait_time=0, close=False) return img

def _turn(self, param_angle=90.0, line=None):

x = [] y = []

for pdx, p in enumerate(line): x.append(line[pdx][0]) y.append(line[pdx][1])

nx = [] ny = []

for pdx, p in enumerate(line): angle = m.radians(param_angle)

nx.append(round(line[pdx][0] * m.cos(angle) - line[pdx][1] * m.sin(angle), 1)) ny.append(round(line[pdx][0] * m.sin(angle) + line[pdx][1] * m.cos(angle), 1))

return nx, ny

def calc_dist(self, x0, y0, x1, y1): answer = False

d = m.sqrt((x1 - x0) ** 2 + (y1 - y0) ** 2) if d < 1.5:

answer = True return answer

def dist_between_points(self, x0, y0, x1, y1, pr=False): d = m.sqrt((x1 - x0) ** 2 + (y1 - y0) ** 2) if pr:

print('[d]: {}'.format(d)) return d

def open_img(self, path, gr=False): if gr:

img = cv2.resize(cv2.imread(path, 0), (self.img_size, self.img_size)) else:

img = cv2.resize(cv2.imread(path), (self.img_size, self.img_size)) return img def perimetr(self, img):

all_p = []

g = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) _, a = cv2.threshold(g, 125, 255, cv2.THRESH_BINARY) h, w = a.shape

# 1

for i in range(h): for j in range(w): if a[i][j] == 0:

all_p.append([i, j]) break

# 4

for j in range(w):

for i in reversed(range(h)): if a[i][j] == 0:

all_p.append([i, j]) break

# 3

for i in reversed(range(h)): for j in reversed(range(w)): if a[i][j] == 0:

all_p.append([i, j]) break

# 2

for j in reversed(range(w)): for i in range(h): if a[i][j] == 0:

all_p.append([i, j])

break

n_img = copy.copy(a) for i in range(h): for j in range(w): n_img[i][j] = 255

for i in all_p: n_img[i[0], i[1]] = 0

# show_image(n_img)

# exit(0)

# cv2.imwrite('myimg1.png', n_img) a = n_img

n_img = cv2.cvtColor(n_img, cv2.COLOR_GRAY2BGR)

# show_image(n_img, wait_time=0)

# exit()

return n_img, a

def run(self, show): res = [] cadons = ''

poly_alph = 'abcdefghijklmnopqrstuvwxyz' for k, v in self.all_pathes.items(): xdata, ydata = self._rotate_line(v) x = np.linspace(min(xdata), max(xdata), len(xdata)) plt.plot(xdata, ydata, label='input')

all_y = []

for i in range(self.polynom):

coefs = np.polyfit(xdata, ydata, i + 1) y_temp = self._polyn_np(xdata=x, coefs=coefs) all_y.append(y_temp) plt.plot(x, y_temp, label='yA' + str(i + 1)) plt.legend() plt.grid() if show:

plt.show() plt.close()

out = {}

for idx, i in enumerate(all_y): _t = self._sr_ot(ydata, i) out[poly_alph[idx]] = _t # out['y'+str(idx+1)] = _t res.append([k for k, v in out.items() if v == min(out.values())]) # FOR Sr_ot # res.append([k for k, v in out.items() if v == max(out.values())]) # FOR PEARSONR for symbol in res:

cadons += symbol[0] return cadons

def show_haris(self, img):

_,img = cv2.threshold(img, 127,255, cv2.THRESH_BINARY_INV) img = cv2. cvtColor(img,cv2.COLOR_GRAY2BGR) for idx, i in enumerate(self.g_point): img[i[0], i[1]] = [0, 255, 0] try:

img[i[0]+1, i[1]] = [0, 255, 0] img[i[0]+1, i[1]-1] = [0, 255, 0] img[i[0], i[1]+1] = [0, 255, 0] img[i[0]+1, i[1]+1] = [0, 255, 0] img[i[0] - 1, i[1]] = [0, 255, 0] img[i[0] - 1, i[1]+1] = [0, 255, 0] img[i[0], i[1] - 1] = [0, 255, 0] img[i[0] - 1, i[1] - 1] = [0, 255, 0] except:

print('Error: _coloring_g_point() out of range index!') show_image(img, namewin='haris', wait_time=0, scale=3)

def show_graph(self): G = nx.Graph()

for key, val in self.all_pathes.items(): for idx, i in enumerate(val): if idx == 0:

G.add_node('bs' + str(key) + str(idx), pos=(val[0][0], val[0][1]), size=70) elif idx == len(val) - 1:

G.add_node('be' + str(key) + str(idx), pos=(val[-1][0], val[-1][1]), size=100) else:

for green in self.g_point:

if self.dist_between_points(i[0], i[1], green[0], green[1]) < 1.3: G.add_node('g' + str(key) + str(idx), pos=(i[0], i[1]), size=5) else:

G.add_node('p' + str(key) + str(idx), pos=(i[0], i[1]), size=1)

sizes = []

for key, val in G.nodes.items(): sizes.append(val[' size'])

color_map = []

for node, props in G.nodes.items(): if node[:2] == 'bs':

color_map. append(' orange') elif node[:2] == 'be':

color_map.append('blue') elif node[0] == 'g':

color_map.append('green') else:

color_map.append('red') nodes = G.nodes

pos = nx.get_node_attributes(G, 'pos')

# colors = nx.get_node_attributes(G, 'color')

# d = nx.degree(G)

pathes = []

for node, props in G.nodes.items():

pathes.append(node) n_pathes = [] st = None en = None

for idx, i in enumerate(pathes): if i[:2] == 'bs':

st = idx elif i[:2] == 'be': en = idx

if st is not None and en is not None: n_pathes.append(pathes[st:en + 1]) st = None en = None for i in n_pathes: G.add_path(i)

# #################### CONNECT ALL #######################

# counter = 0

# all_connect = []

# for node_i, props_i in G.nodes.items():

# if node_i[0:2] == 'be':

# counter+=1

# all_connect.append(node_i)

# G.add_path(all_connect)

nx.draw_networkx(G, pos=pos, nodelist=nodes, node_size=sizes, node_color=color_map, with_labels=False,

alpha=0.5) plt. savefig(' ./data/out/base.png')

graph = cv2.rotate(cv2.imread('./data/out/base.png'), cv2.ROTATE_90_CLOCKWISE) show_image(graph, wait_time=0, namewin='Graph', close=False, move=True) plt.close()