Содержание к диссертации
Введение
1 Задача поиска схем и чертежей в электронных архивах технической документации 13
1.1 Архив технической документации как актив предприятия 13
1.2 Актуальность проблемы поиска чертежей и схем 14
1.3 Обзор методов и систем поиска чертежей по изображению-образцу 16
1.4 Обзор методов и систем восстановления 3D модели по чертежу 26
1.5 Системы автоматической векторизации чертежей 35
1.6 Выводы, постановка цели и задач исследования 37
2 Модели представления графической конструкторско-технологической информации в поисковой подсистеме САПР 40
2.1 Когнитивная модель описания чертежных изображений 40
2.2 Уровни описания чертежных изображений
2.2.1 Граф особых точек и участков примитивов 43
2.2.2 Граф замкнутых контуров 45
2.2.3 Граф 3D объектов 52
2.2.4 Граф разнородных составляющих
2.3 Строгие и упрощенные графические образы 58
2.4 Области применения графических образов 59
2.5 Способы представления атрибутов 61
2.6 Грамматики проекций твердотельных кинематических объектов 68
2.7 Метод структурного распознавания твердотельных кинематических объектов на чертеже 77
2.8 Выводы по главе 80
3 Методики графического сопоставления и поиска архивных чертежей и схем ... 82
3.1 Лучевой граф как инструмент анализа 82
3.2 Методика сопоставления графов образов чертежных изображений 88
3.3 Оценка сходства графов образов чертежных изображений 93
3.4 Модель расширенного диалога между проектировщиком и поисковой подсистемой САПР 3.4.1 Этапы поиска 96
3.4.2 Поисковые стратегии 105
3.5 Методика поиска чертежей и схем по содержанию 109
3.6 Выводы по главе 111
4 Экспериментальное исследование эффективности разработанных моделей и методики 113
4.1 Система поиска чертежей и схем по содержанию «GrSearch» 113
4.2 Тестовый архив чертежей 123
4.3 Используемые критерии оценки качества информационного поиска 124
4.4 Сопоставление, распознавание и поиск на основе графов особых точек и участков примитивов 125
4.5 Поиск на основе графов замкнутых контуров 135
4.6 Исследование представлений атрибутов и оценок сходства 138
4.7 Исследование средств уточнения запроса 145
4.8 Выделение твердотельных кинематических объектов на чертеже 155
4.9 Сравнение системы поиска чертежей и схем «GrSearch» с аналогами 158
4.10 Выводы по главе 163
Заключение 164
Список условных обозначений и сокращений 167
Список литературы
- Обзор методов и систем поиска чертежей по изображению-образцу
- Граф разнородных составляющих
- Оценка сходства графов образов чертежных изображений
- Сопоставление, распознавание и поиск на основе графов особых точек и участков примитивов
Введение к работе
Актуальность работы. При проектировании новых изделий немаловажными являются патентные исследования и применение накопленных знаний: существующих компонентов, конструкторских решений, технологических процессов. Однако найти требуемый документ среди тысяч непросто, учитывая характер технической документации, которую образуют схемы, чертежи, 3D-модели, сканированные документы, содержащие как текст, так и графику.
В настоящий момент проблема поиска чертежей решается главным образом на основе текстово-числовых атрибутов, кодов классификации и текстовых описаний, создаваемых человеком. При этом, помимо высоких затрат ручного труда при создании и сопровождении архива, неполноты описания геометрии деталей, трудно формулировать запросы, в том числе из-за влияния субъективизма, когда люди описывают одну и ту же деталь по-разному. Стандартные способы поиска чертежей в некоторых ситуациях не приводят к удовлетворительным результатам.
Очевидно, арсенал поисковых инструментов проектировщиков должен быть расширен новыми средствами графического поиска по содержанию – кон-тентного поиска (content-based retrieval), основанного на сопоставлении и распознавании зрительных образов. Опыт применения систем, ведущих поиск чертежей и схем по задаваемому пользователем изображению-образцу, показывает их превосходство перед традиционными способами поиска в ряде ситуаций.
Тем не менее, возможности существующих систем графического поиска чертежей и схем еще далеки от желаемых: недостаточная степень соответствия выдачи требованиям пользователя, малая гибкость средств задания запросов. Выработка и реализация оптимальной поисковой стратегии, адаптированной к конкретной задаче, в существующих системах затруднительна.
Информационная потребность проектировщика может иметь множество тонкостей, не выразимых полностью только чертежом или эскизом, а уж тем более одними лишь текстовыми атрибутами или глобальными агрегированными характеристиками изображения. Поисковый диалог следует расширить различными способами выражения поисковой потребности и уровнями абстрагирования (от особых точек и примитивов до унифицированных конструктивов и взаимосвязей между ними).
О качественном решении проблемы графического поиска чертежей и схем можно говорить тогда, когда автоматический анализ и сопоставление графической конструкторско-технологической информации происходит подобно процессу ее восприятия инженером. При чтении чертежей инженер обычно оперирует трехмерными образами. Поэтому желательно, чтобы поисковая система была способна автоматически извлекать из чертежей трехмерные геометрические тела и строить на их основе поисковые образы.
Учитывая вышеизложенное, считаем, что проблема повышения релевантности и гибкости поиска чертежей и схем является актуальной.
Степень научной разработанности проблемы. Разработке и исследованию методов поиска технических чертежей и схем по содержанию и алгоритмов автоматического чтения чертежей уделено большое внимание в работах отечественных и зарубежных ученых: Баба Т., Баркова И.А., Бартона Дж.А., Ванна Дж., Ванна П., Гэнга В., Керницкого Д.В., Котова И.И., Кумсапа П., Ку-чуганова В.Н., Лава Д.М., Лиу Р., Ложкина А.Г., Масумото Д., Полозова В.С., Пу Дж., Рамани К., Роткова С.И., Соуза П., Сунанона П., Тэна З., Тюриной В.А., Фонсеки М.Дж., Хуанга Ф., Цзяна Ш., Цзяо Л., Чжана И., Широковой Л.В. и др.
Область исследования. Работа соответствует пунктам «4. Разработка принципиально новых методов и средств взаимодействия “проектировщик – система”», «7. Разработка научных основ построения … процессов работы электронных архивов технической документации …» паспорта специальности 05.13.12 – «Системы автоматизации проектирования» (САПР).
Объектом исследования являются процессы поиска графической информации в архивах технической документации.
Предметом исследования являются модели и методы поиска графической информации по содержанию на примере технических чертежей и схем.
Цель работы. Повышение эффективности функционирования систем автоматизации проектирования на этапах анализа и применения существующих решений при проектировании новых изделий путем разработки способов анализа и сопоставления чертежных изображений для поиска чертежей и схем в архивах технической документации.
Для достижения поставленной цели решаются следующие задачи:
1. Анализ существующих моделей и методов представления, сопоставле
ния и поиска графической конструкторско-технологической информации.
2. Создание модели и алгоритмов описания чертежного изображения,
обеспечивающих его содержательное и комплексное представление в поиско
вой подсистеме САПР.
-
Разработка способа распознавания трехмерных геометрических тел на чертежах деталей, обеспечивающего возможность формирования трехмерных поисковых образов.
-
Создание модели взаимодействия проектировщика с поисковой подсистемой САПР, обеспечивающей высокую прозрачность и управляемость процесса поиска в архивах технической документации.
-
Разработка методики контентного поиска чертежей и схем.
-
Разработка экспериментальной системы графического поиска чертежей и схем в архивах технической документации на основе предложенной методики и экспериментальное исследование ее эффективности.
Методы исследования. Теоретические исследования выполнены с использованием моделей и методов структурного распознавания образов, теории графов, математической лингвистики, теории нечетких множеств, нечеткой логики, теории проектирования баз данных. Экспериментальные исследования выполнены с помощью разработанных программных систем графического по-
иска чертежей и схем, синтеза 3D модели по чертежу с привлечением методов оценки качества информационного поиска.
Научная новизна работы состоит в следующем:
-
Предложена графовая модель чертежного изображения, отличающаяся от существующих тем, что для организации гибкой стратегии поиска содержит четыре взаимосвязанных уровня абстрагирования: граф особых точек и участков примитивов; граф замкнутых контуров; граф 3D объектов; граф разнородных составляющих.
-
Разработан метод структурного распознавания трехмерных геометрических тел на чертежах, отличающийся конструктивной грамматикой, связывающей два и более проекционных вида, позволяющий формировать трехмерные образы деталей по чертежам для осуществления поиска чертежей деталей в терминах составляющих их 3D объектов.
-
Разработана процессная модель расширенного поискового диалога, отличающаяся наличием нескольких видов поиска, возможностью задания общих и специальных требований к результатам, визуализацией элементов сходства и различия, наличием параметров настройки соотношения вычислительные затраты/качество, что позволяет пользователю реализовывать гибкую стратегию поиска и уточнять поисковые потребности.
-
Предложена новая методика контентного поиска чертежей и схем, отличающаяся:
– формированием четырех видов графов чертежных изображений, – применением лучевого графа при сопоставлении образов, – использованием модели расширенного поискового диалога,
позволяющая повысить эффективность функционирования САПР на этапах анализа и применения существующих решений при проектировании новых изделий.
На защиту выносятся:
-
графовая модель и алгоритмы описания чертежного изображения;
-
метод и инструментальные средства структурного распознавания трехмерных геометрических тел на чертежах;
-
процессная модель и инструментальные средства расширенного поискового диалога;
-
методика и инструментальные средства контентного поиска чертежей и схем.
Теоретическая и практическая значимость работы. Разработаны модели и методика представления, анализа, сопоставления и оценки сходства чертежных изображений, представляющие основу процесса гибкого поиска графической конструкторско-технологической информации по содержанию.
Реализованные система графического поиска чертежей и схем и система синтеза 3D модели по чертежу позволяют автоматизировать процесс использования накопленного опыта в виде документации по техническим решениям (чертежи, схемы, 3D модели, техпроцессы).
Кроме того, система синтеза 3D модели по чертежу позволяет автоматизировать обучающий процесс по инженерной графике.
Реализация результатов работы. Результаты исследования использованы:
– на ОАО «Ижевский электромеханический завод “Купол”» в рамках опытной эксплуатации;
– в работе ООО «Нордика-Стерлинг» при реализации проектов по техническому перевооружению предприятий;
– в рамках госбюджетной темы №4043 Госзаказ МОиН на 2012 год «Разработка и экспериментальное исследование системы аэрокосмического и геоинформационного мониторинга для визуализации результатов геоэкологических исследований северных экосистем»;
– на кафедре «Автоматизированные системы обработки информации и управления» ФГБОУ ВПО «ИжГТУ имени М.Т. Калашникова» в преподавании дисциплины «Инженерная и компьютерная графика».
Достоверность и обоснованность результатов работы подтверждается использованием известных положений фундаментальных наук; корректностью созданных моделей; результатами применения разработанных моделей, методики и алгоритмов в различных предметных областях (поиск чертежей, автоматический синтез 3D модели по чертежу, геоинформационный мониторинг); высокими значениями показателей полноты и точности поиска, которые были определены в ходе экспериментальных исследований; примерами результатов поиска с визуализацией совпавших элементов; сравнением с результатами аналогов.
Апробация результатов исследования. Основные результаты диссертационной работы докладывались: на международной научной конференции “Информационные технологии и письменное наследие” (Уфа, 2010); на межвузовской студенческой научной конференции “Communication of Students, Master Students and Post-Graduates in Academic, Professional and Scientific Fields” (Ижевск, 2011); на мероприятии презентации бизнес-проектов “Startuppoint” (Ижевск, 2011); на международном конгрессе по интеллектуальным системам и информационным технологиям “IS-IT’2011” (Дивноморское, 2011); на I и VII республиканских конкурсах инновационных проектов по программе “УМНИК” (Ижевск, 2011, 2014); на 8-ом открытом немецко-российском семинаре “Pattern Recognition and Image Understanding” (Нижний Новгород, 2011); на II Всероссийской конференции аспирантов, магистрантов и молодых ученых с международным участием «Молодые ученые – ускорению научно-технического прогресса в XXI веке» (Ижевск, 2013); на IV Форуме молодых ученых в рамках международной конференции «Технические университеты: интеграция с европейскими и мировыми системами образования» (Ижевск, 2014); на международном конгрессе по интеллектуальным системам и информационным технологиям “IS-IT’2015” (Дивноморское, 2015); на международном форуме “Instrumentation Engineering, Electronics and Telecommunications – 2015” в рамках международной конференции “Приборостроение в XXI веке. Интеграция науки, образования и производства” (Ижевск, 2015).
Публикации. Результаты работы отражены в 15 публикациях, в том числе в 7 статьях в рецензируемых научных изданиях, включенных в Перечень ВАК (4 статьи), Scopus (2 статьи) и Web of Science (1 статья). Отдельные результаты включены в отчеты по проектам РФФИ № 11-07-00632-а, ФЦП «Научные и научно-педагогические кадры инновационной России» № 16.740.11.0423, Госзадания МОиН РФ № 625, программы «УМНИК», Стипендии Президента РФ молодым ученым и аспирантам. Имеется 1 свидетельство о регистрации программы для ЭВМ.
Структура и объем диссертационной работы. Диссертационная работа состоит из введения, четырех глав, заключения и приложений. Основной текст изложен на 166 машинописных страницах с иллюстрациями. Список литературы включает 116 наименований.
Обзор методов и систем поиска чертежей по изображению-образцу
Ниже описываются некоторые существующие методы графического поиска чертежей, приводятся основные результаты их экспериментального исследования, представленные в литературе, дается собственная оценка этих методов. Комплексными обзорами существующих методов поиска технических чертежей по содержанию являются работы [15, 16].
В работах [17, 18, 19, 20] представлен метод поиска векторных чертежей по эскизу, нарисованному на планшетном устройстве от руки. Содержимое чертежей раскладывается на топологию (пространственное расположение полигонов, имеющихся на чертеже) и геометрию (форма этих полигонов). Топологическая информация организуется в виде топологического графа, в котором узлы представляют полигоны чертежа, а ребра – отношения между ними. Этот граф описывает глобальную топологию чертежа. С целью независимости представления чертежа от переноса и поворота, а также упрощения топологического графа используются только три топологических отношения между полигонами: 1) вложенность (один полигон содержит внутри себя другой полигон), 2) смежность (полигоны соприкасаются или пересекаются), 3) расстояние между полигонами, нормализованное с использованием диагонали габаритного прямоугольника родительского объекта, содержащего эти полигоны. Топологический граф имеет хорошо определенную структуру: дерево (отношение вложенности) с боковыми связями на одном уровне (отношение смежности). Корень дерева представляет весь чертеж. Топологический граф преобразуется в многомерные дескрипторы, чтобы решать задачу поиска не на основе определения изоморфизма графов (NP-полная задача), а путем вычисления расстояний между дескрипторами. Преобразование топологического графа в топологический дескриптор осуществляется на основе вычисления спектра графа [21]: построение матрицы смежности графа, вычисление ее собственных значений, упорядочивание абсолютных значений по убыванию. Для возможности использования эскизов-запросов различной степени детализации и осуществления частичного сопоставления создается несколько топологических дескрипторов по одному топологическому графу чертежа: для каждого уровня древовидной структуры графа и для каждого его подграфа. Каждый дескриптор представляет уровень детализации или часть чертежа. Для ускорения поиска дескрипторы индексируются на основе NB-дерева. Геометрическая информация о полигоне представляется в виде геометрического дескриптора и включает: площадь и периметр выпуклой оболочки, площадь, периметр, высоту и ширину объемлющего прямоугольника, площадь и периметр наибольшего четырехугольника и треугольника, периметр исходного полигона. Процесс поиска разбит на два этапа: 1) выборка чертежей, топологически похожих на эскиз-запрос, 2) вычисление геометрического подобия между каждым чертежом-кандидатом и эскизом-запросом. Описанный метод был реализован в системе SIBR. Тестирование системы осуществлялось на коллекции из 38 простых чертежей, состоящих из 1-3 фигур типа «прямоугольник», «треугольник», «звезда» и т.п., и 40 чертежей пресс-форм, представляющих собой прямоугольную плиту с множеством круглых, квадратных и треугольных элементов. Было выполнено 12 запросов-эскизов, нарисованных весьма небрежно. В большинстве запросов искомые чертежи были среди первых пяти результатов и почти всегда среди первых десяти результатов. Время поиска составляло 2–10 секунд. По данному методу поиск можно производить только по тем фрагментам чертежа, для которых система создала дескрипторы. Используемый в запросе фрагмент обязательно должен быть композицией из замкнутых контуров. В качестве запросов нельзя использовать конструктивные элементы типа канавок, выступов и т.п. В методе не предусмотрено выявление соответствий элементов, нет механизмов уточнения запроса. В работе [22] предлагается метод поиска технических чертежей на основе сопоставления атрибутивных графов, описывающих чертежи. Узлы графов соответствуют значимым примитивам (отрезкам и кривым), а ребра описывают пространственные отношения между этими примитивам. При построении графа чертежа применяется модификация метода тесселяции Делоне. Указывается, что традиционный метод Делоне приводит к потере важных отношений и возникновению ложных связей. Предложенная авторами модификация метода Делоне, названная стратегией выборки, заключается в следующем: 1) равномерный выбор нескольких точек на длинном примитиве; 2) использование выбранных точек в качестве входных данных для тесселяции Делоне; 3) упрощение графа путем слияния узлов и ребер, полученных из одного и того же примитива. Для решения проблемы сопоставления графов применена теория среднего поля, позволяющая достичь компромисса между скоростью и производительностью. Тестовая база данных (БД) содержала 100 растровых чертежей умывальников 3-х категорий (22, 22 и 56 чертежей соответственно). Было выполнено 20 запросов (10 – из первой категории, 10 – из второй). Статистика экспериментов следующая: на компьютере P4-1.3G система просматривает 1 чертеж в среднем за 1.1 секунды, при этом средняя точность результатов поиска составляет около 56%, а полнота – 80%. В данном методе не осуществляется выявление соответствий элементов, не предусмотрено задание специальных требований к результатам.
Граф разнородных составляющих
Ключевые концепции, положенные в основу предлагаемого в настоящей работе подхода, следующие: – рассмотрение чертежного изображения как многоуровневой системы; – использование терминов и типовых элементов приборо- и машино- строения при описании чертежных изображений; – автоматическое извлечение 3D объектов из чертежа и использование их при его описании; – представление графических объектов на различных уровнях абстракции; – осуществление распознавания/сопоставления графических образов путем анализа отдельных составляющих и отношений между ними; – инвариантность к повороту и масштабу сравниваемых объектов, устойчивость к местным изгибам и растяжениям; – фиксация элементов сходства и различия графических объектов. С этих позиций наиболее предпочтительную основу для компьютерного представления и анализа сложных чертежных изображений предоставляют структурный подход к распознаванию образов [75], теория графов [76], теория нечетких множеств [77] и нечеткой логики [78].
Будем исходить из предположения, что сложный неизвестный объект человек мысленно раскладывает на простые знакомые конфигурации [79]. При описании объектов чертежа инженер использует следующие категории понятий (тезаурус) [80, 81, 82]: 1. Общие характеристики деталей, например: тело вращения, плоская деталь, штамповка, корпусная, трубчатая, крестовина и т.п. 2. Вспомогательные характеристики: ось, разрез, сечение, количество видов и т.д. 3. Контур: прямоугольник, параллелограмм, трапеция, квадрат, ромб, треугольник, звезда, круг и т.д. 4. Стандартные детали и узлы (СДУ): крепежные изделия и др. 5. Типовые конструктивные элементы (ТКЭ): фаски, канавки, отверстия и др. Некоторые ТКЭ представлены на рисунке 2.1. Рисунок 2.1 – Примеры типовых конструктивных элементов 6. Характеристики элементов, составляющих графический образ: прямой, тупой, острый, изогнутый, растянутый и т.п. 7. Термины, характеризующие положение и связи составляющих элементов: слева, справа, вверху, внизу, в углу, внутри, больше, меньше и т.п. [79]. При этом человек практически не использует количественные понятия (точную длину, площадь, периметр, угол и т.п.). В качестве компьютерного представления графического образа (ГО), описывающего чертежное изображение с использованием качественных, нечетких понятий, будем использовать нечеткий пространственно нагруженный граф [83, 84, 85]: G = (V, AV, E, AE, AO), где V – множество узлов, описывающих составляющие чертежного изображения с помощью параметров AV; Е с: VxV - множество ориентированных ребер, отображающих пространственные отношения между составляющими чертежного изображения с помощью параметров АЕ; Ао - параметры, относящиеся ко всему чертежному изображению; параметры А у, АЕ, Ао включают лингвистические переменные.
В компьютерной системе элементы, составляющие графический образ чертежного изображения, можно содержательно представить в виде оценок их сходства с типовыми конфигурациями, определяемыми экспертом применительно к конкретному предприятию. Посредством типовых составляющих системе будут передаваться знания, опыт, способ восприятия рисунков конкретного человека [86]. С их помощью становится возможным выполнение косвенного, более быстрого сопоставления составляющих графических образов. Дадим определение типовым составляющим: с, п, RP , где с - класс составляющей, например, особая точка, цепочка элементов, контур, проекция объекта, ЗБ-объект и т.п.; п - наименование типовой составляющей в классе, например, острый угол, прямоугольник, усеченный конус и т.п.; RP - представление изображения типовой составляющей, пригодное для осуществления сопоставлений некоторым имеющимся методом. Классы составляющих соответствуют уровням восприятия изображения.
Оценка сходства графов образов чертежных изображений
Сопоставление графических образов, представленных в виде НПНГ, заключается в синхронном построении лучевых графов на основе НПНГ и анализе лучевых графов.
Узел НПНГ, который может быть использован в качестве корневой вершины лучевого графа, будем называть базовым. Т.е. базовый узел - это узел, с которого в графе потенциально может начинаться процесс распознавания. В общем случае необходим механизм автоматического назначения базовых узлов. Но возможно и ручное указание базовых узлов, например, чтобы акцентировать внимание на некотором фрагменте запроса [79].
Результатом сопоставления графических образов является оценка сходства и метки соответствия составляющих.
Методика сопоставления графа эталона (запроса) GQ с графом представителя GE следующая: 1. Выбрать очередные vQb є в№ и vEb є Blf. Множество базовых узлов В1\г графа GQ либо задается пользователем путем непосредственного перечисле ния, либо определяется автоматически путем реализации определенной стратегии. Множество B}f графа GE определяется автоматически по определенной страте гии. В зависимости от используемой стратегии определения базовых узлов, каж дому элементу vQb может соответствовать свое множество BIS ; может осуществ ляться предварительное сопоставление графов на ограниченную глубину; множе ства могут формироваться не сразу, а порциями (с целью повышения быстродействия сопоставления). 2. Определить общее покрытие, т.е. соответствия между вершинами и ребрами GQ и вершинами и ребрами GE, путем построения и анализа лучевого графа эталона BGQ и лучевого графа представителя BGE, за прототипы корней которых взять вершины 3. Объединить покрытия, найденные на текущей и предыдущих итерациях. 4. Вычислить оценку сходства GQ и GE. 5. Если результаты достаточны для принятия положительного или отрицательного решения, то конец, иначе переход на шаг 1.
Определение общего покрытия из вершин лучевых графов vQc и /с, изначально корневых, происходит по следующим шагам: 1. Достроить (по исходным графам) в лучевых графах ребра, исходящие из VQC и VEС, и вершины на их концах. Выделить среди них подмножества VN и J N вершин, которые еще не принадлежат общему покрытию. 2. Установить соответствия между вершинами VеN и VЕN. Соответствие вершин друг другу определяется путем сравнения их атрибутов и атрибутов входящих в них ребер. В случае наличия нескольких вариантов соответствия произвести просмотр на несколько шагов вперед. Пороги, задающие максимальную дальность и глубину рекурсивного предпросмотра, на начальных этапах больше, чем на последующих. 3. Повторить для каждой пары добавленных в общее покрытие вершин.
Предложенная методика сопоставления применима на всех четырех уровнях представления чертежных изображений. Рассмотрим методику на примере сопоставления графов особых точек и участков примитивов.
Сопоставление графов особых точек и участков примитивов. Ниже представлен алгоритм сопоставления связных графов особых точек и участков G\ и G2. Общее покрытие графов определяется из заданных базовых узлов рекурсивной процедурой Recognizeeh v2): 1) если CompareKnots(v1} v2) = False, то перейти к шагу 4; 2) Pairs - SimilarOutEdges(vh v2); 3) для каждого/? є Pairs выполнять: 3.1) R, vTx\ v2next - CompareEdges(p.e1, p.e2); 3.2) Если R = True, то Recognizee Г\ v2next); 4) СТОП; где функция SimilarOutEdges(vh v2) возвращает множество пар вида еь е2 таких что: - ej и е2 - ребра, исходящие из узлов vj и v2 соответственно; -\BegDir(e!) - BegDir(e2)\ -+min; функция BegDir(e) = e.BegOnent (?rev.BegEndOnent вычисляет направление начала ребра-цепочки е относительно предыдущего ребра; функция CompareKnots(v1} v2) сравнивает узлы v} и v2 путем сравнения их атрибутов; функция CompareEdges(e1} е2) ищет оптимальный вариант объединения ребер-цепочек, начиная с е7 и е2. Значение функции имеет вид: R, v/exf, v2next , где R - результат сравнения, vjnext и v2next - узлы графов, соответствующие концам найденных объединенных участков [87]. Указанным образом осуществляется распознавание ТКЭ на чертежах (рисунок 3.7), сопоставление замкнутых контуров и т.д.
Важной задачей, решаемой на уровне особых точек и участков примитивов, является задача сопоставления внешних контуров деталей. Особенности данной задачи: 1. Малая степень классификации особых точек: только прямой, тупой, острый угол. 2. Как следствие – проблема автоматического назначения базовых узлов. 3. Конструктивная многозначность, выражающаяся в существовании особых точек, которые в зависимости от ситуации являются либо важными, либо отвлекающими (рисунок 3.8). Описываемый алгоритм сопоставления учитывает перечисленные особенности.
При подборе базового узла рассматриваются особые точки, к которым примыкают самые длинные цепочки изображения, поскольку конструкторско-технологической базой детали обычно является одна из таких цепочек. В качестве эталонной принимается габаритная длина детали [87].
Проблема отвлекающих особых точек возникает, когда сопоставляемые графы получены по исходным данным низкого качества, с разными порогами предобработки или выбран режим грубого сравнения. На каждом из графов требуется проводить серьезный предварительный анализ. На рисунке 3.9 представлен пример того, какие части изображений должны автоматически признаваться схожими. Аналогичное требование высказано также в работе [37].
Сопоставление, распознавание и поиск на основе графов особых точек и участков примитивов
Основными критериями качества информационного поиска, используемыми в настоящем исследовании, являются полнота и точность выдаваемых результатов.
Полнота выдачи – отношение числа найденных релевантных документов к общему количеству релевантных документов. С точки зрения автора, в задаче графического поиска чертежей наиболее важен именно показатель полноты выдачи ввиду того, что поиск осуществляется главным образом с целью анализа и заимствования конструкторских решений и технологических процессов изготовления, и релевантными могут считаться достаточно сильно отличающиеся друг от друга детали.
Точность выдачи – отношение числа найденных релевантных документов к общему количеству документов в выдаче.
Хорошее представление о качестве поиска дает график полноты/точности. Эти графики построены по методу 11-точечной интерполированной средней точности [112], который применяется в большинстве аналогичных работ [19, 22, 24, 29, 36].
Для автоматизации процесса оценки качества поиска в системе GrSearch была реализована функция анализа результатов (рисунок 4.10).
Распознавание и удаление конструктивных элементов. На рисунке 4.11 представлен пример результата автоматической предобработки чертежа, включающей этап распознавания и удаления конструктивных элементов. При включенном режиме распознавания и удаления конструктивных элементов система индексирует 300 сложных чертежей за 24 минуты, а при выключенном – за 8 минут [74].
Автоматическое распознавание и удаление конструктивных элементов: а) база образов ТКЭ; б) исходный чертеж; в) граф особых точек и участков примитивов объекта чертежа; г) объект чертежа после удаления конструктивных элементов
Поиск деталей по внешнему контуру. Методика проведения эксперимента по поиску деталей по внешнему контуру была следующей: 1. Выбрать деталь-запрос. 2. Найти в архиве все детали, аналогичные детали-запросу по форме. 3. Определить релевантность каждой детали-аналога (степень соответствия запросу): высокая, средняя, низкая. 4. Выполнить графический поиск. 5. Построить графики полноты выдачи отдельно по каждой категории релевантности.
На рисунке 4.12 представлены использованные запросы и релевантные им чертежи с указанием степени соответствия запросу.
Таким образом, чем точнее архивный чертеж соответствует запросу, тем выше вероятность его нахождения (стремится к 100%).
В следующем эксперименте по поиску деталей по внешнему контуру качество поиска оценивалось следующим образом. Релевантный документ считался найденным, если он присутствовал на первой странице выдачи, среди первых 75 результатов. Сначала поиск осуществлялся со стандартными параметрами без какой-либо настройки образа запроса (в этом случае допускаются достаточно большие отклонения). Затем пользователь осуществлял анализ совпавших с точки зрения системы конструктивных элементов некоторых деталей выдачи и выполнял новые итерации поиска с усиленными или ослабленными требованиями, например, с запретом на игнорирование зубьев (рисунок 4.14).