Методы анализа и распознавания трехмерных изображений на основе стохастической геометрии Семов Алексей Александрович

Содержание к диссертации

Введение

ГЛАВА 1. Постановка задачи. обзор подходов к проблеме распознавания 3D изображений 10

1.1 Распознавание образов: постановка задачи, типы и проблемы 10

1.2 Обзор методов анализа и распознавания 3D изображений 15

1.3 Проблема инвариантности распознавания 3D изображения при его произвольной ориентации в пространстве 22

1.4 Методы построения равномерных сеток на сфере 28

1.5 Основные результаты и выводы по главе 1 31

ГЛАВА 2. Новое геометрическое 3D трейс - преобразование 33

2.1 Математическая модель 3D трейс-преобразования 33

2.2 Гипертрейс-матрица как математический инструмент для анализа 3D изображений

2.2.1 Способы построения гипертрейс-матриц 39

2.2.2 Свойства гипертрейс-матриц 43

2.2.3 Анализ 3D объектов при помощи гипертрейс-матрицы

2.3 Режимы сканирования 3D изображений 53

2.4 Основные результаты и выводы по главе 2 57

ГЛАВА 3. Свойства гипертриплетных признаков 59

3.1 Свойства и примеры функционалов, входящих в аналитическую структуру признака 59

3.2 Конструирование признаков, обладающих свойством полной инвариантности к группе движений и масштабированию 3D изображений

3.2.1 Функционалы, инвариантные к переносу 3D изображений 64

3.2.2 Функционалы, инвариантные к повороту 3D изображений 66

3.2.3 Функционалы, инвариантные к масштабированию 3D изображений 67

3.2.4 Примеры признаков, полностью инвариантных к группе движений и масштабированию 3D изображений 68

3.3 Конструирование признаков с заданными свойствами 70

3.3.1 Построение признаков сенситивных к группе движений 3D изображений и анализ их свойств 71

3.3.2 Определение различных метрических характеристик 3D объекта

3.4 Сокращение размерности признакового пространства 76

3.5 Основные результаты и выводы по главе 3 84

ГЛАВА 4. Экспериментальная проверка свойств 3d трейс преобразования 86

4.1 Определение оптимальных параметров сканирования 87

4.2 Экспериментальная проверка свойств инвариантности конструируемых признаков к переносу, повороту и масштабированию 3D изображения 92

4.3 Анализ точности вычисления метрических признаков 3D объектов 98

4.4 Анализ стохастического и детерминированного способов сканирования 3D изображений 101

4.5 Распознавание и классификация 3D изображений 104

4.6 Основные результаты и выводы по главе 4 119

Заключение 121

Публикации автора по теме диссертации 122

Список литературы 126

Приложение а. Свидельства о государственной регистрации разработанных программ для эвм 136

Приложение б. Акт о внедрении результатов диссертационной работы

• Проблема инвариантности распознавания 3D изображения при его произвольной ориентации в пространстве
• Гипертрейс-матрица как математический инструмент для анализа 3D изображений
• Функционалы, инвариантные к переносу 3D изображений
• Экспериментальная проверка свойств инвариантности конструируемых признаков к переносу, повороту и масштабированию 3D изображения

Введение к работе

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

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

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

Важные результаты в области распознавания образов и анализа изображений получены отечественными научными школами Ю. И. Журавлева, К. В. Рудакова, В. А. Сойфера, Н. Г. Федотова, В. В. Сергеева, С. С. Садыкова; зарубежными научными школами R. Szeliski (Microsoft Research’s Interactive Visual Media Group), I. H. Witten (University of Waikato New Zealand).

Целью диссертационной работы является разработка новых методов анализа и распознавания 3D изображений на основе стохастической геометрии. Для достижения поставленной цели необходимо решить следующие основные задачи:

1. Провести анализ современного состояния работ в области анализа и распознавания 3D изображений. Выявить сильные и слабые стороны методов, применяемых в данной области.

2. Разработать метод сканирования 3D изображений для достижения инвариантности их распознавания к группе движений и масштабированию.

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

4. Построить новый тип признаков 3D изображений, который давал бы возможность описывать различные метрические характеристики пространственных объектов.

5. Провести эксперименты по оценке эффективности предлагаемого метода и сравнить полученные результаты с основными методами распознавания 3D изображений.

Объектом исследования являются 3D изображения.

Предметом исследования являются методы анализа и распознавания 3D изображений на основе положений стохастической геометрии.

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

Соответствие паспорту специальности. Диссертация выполнена в соответствии с требованием специальности 05.13.17 – Теоретические основы информатики. Области исследования: п. 5 – «Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях, разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений», п. 7 – «Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания».

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

1. Впервые для анализа и распознавания 3D изображений предложен подход на основе стохастической геометрии, который благодаря построению признаков, инвариантных к группе движений и масштабированию, позволяет повысить надежность и универсальность распознавания. Сканирование со случайными параметрами улучшает соотношение «надежность – быстродействие» распознавания 3D изображений по сравнению с детерминированным сканированием, что было не только обосновано теоретически, но и показано практически.

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

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

4. Построен новый тип признаков 3D изображений, имеющих аналитическую структуру, – гипертриплетные признаки. Благодаря их аналитической структуре возможна автоматическая генерация большого количества признаков с заранее заданными свойствами, в частности, инвариант-

ности и сенситивности по отношению к группе движений и масштабным преобразованиям.

Практическая значимость работы. Результаты исследования могут быть использованы при разработке интегрированных систем безопасности для сканирования и обнаружения пространственных объектов в системах видеонаблюдения, а также в сигнализационных комплексах и системах при распознавании 3D изображений в технических средствах обнаружения. Инвариантное описание, получаемое разработанным методом, позволяет увеличить скорость обработки результатов обнаружения искомого объекта и тем самым сократить время на включения сигнализации и системы оповещения. Данные положения подтверждаются актом о внедрении.

На основе результатов исследования разработаны программные комплексы по сканированию и распознаванию 3D изображений (свидетельства об официальной регистрации программ для ЭВМ в Роспатенте № 2015612257 от 16.02.15 и № 2015612814 от 26.02.15), которые позволяют повысить качество распознавания пространственных объектов в системах машинного зрения.

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

5. Метод сканирования 3D изображений плоскостями, обеспечивающий возможность достижения инвариантного распознавания объекта при его произвольной ориентации в пространстве.

6. Математический инструмент для анализа 3D изображений – гипер-трейс-матрица, позволяющая извлекать параметры масштаба, положения и ориентации объекта в пространстве.

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

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

Реализация и внедрение результатов работы. Работа выполнялась по гранту РФФИ (проект № 12-07-00501). Результаты исследований используются на предприятии «НИКИРЭТ» (филиал ФГУП ФНЦП «ПО "СТАРТ" им. М. В. Проценко», г. Заречный), что подтверждается актом о внедрении.

Достоверность и обоснованность научных и практических результатов диссертации обеспечивается корректным применением математического аппарата; апробацией на научно-технических конференциях; сходимостью результатов и выводов теоретических и компьютерных исследований; проведением экспериментов по классификации базы данных 3D изображений The Princeton Shape Benchmark; практическим применением полученных результатов, подтвержденных актом о внедрении.

Апробация работы. Основные результаты и положения диссертации докладывались и обсуждались на конференциях: «Intelligent Information Processing» (2014), «Pattern Recognition and Image Analasis: New Information technologies» (2013), «Надежность и качество» (2013-2015), «Проблемы информатики в образовании, управлении, экономике и технике» (2013-2014), «Новые информационные технологии и системы» (2012, 2014), «Модели, системы, сети в экономике, технике, природе и обществе» (2014), «Современные методы и средства обработки пространственно-временных сигналов» (2012-2015).

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

Личный вклад автора. Основные научные результаты, приведенные в диссертации и выносимые на защиту, получены автором лично. Автором был выполнен следующий объем исследований: получение теоретических результатов (метод сканирования 3D изображений, математический инструмент для анализа 3D изображений, процедура сокращения признакового пространства), разработка и тестирование программных комплексов для распознавания 3D изображений, проведение эксперимента по классификации базы изображений The Princeton Shape Benchmark.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 88 наименований и двух приложений. Общий объем работы - 140 страниц, в том числе: 121 страница основного текста (включая 10 таблиц, 23 рисунка), 10 страниц списка литературы.

Проблема инвариантности распознавания 3D изображения при его произвольной ориентации в пространстве

За последние полвека отечественными и зарубежными учеными было получено много важнейших результатов в области анализа сцен и распознавания 2D образов [13, 44, 45]. Большой вклад в развитие теории распознавания изображений был получен отечественными научными школами Ю.И. Журавлева, К.В. Рудакова, В.А. Сойфера, Н.Г. Федотова, В.В. Сергеева, С.С. Садыкова, зарубежными научными школами R. Szeliski (Microsoft Research s Interactive Visual Media Group), I.H. Witten (University of Waikato New Zealand) и другими.

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

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

Среди ранних исследований, относящихся к первой группе методов, можно выделить статью Охбучи [67]. В данной работе при распознавании 3D изображения используются гистограммы формы, которые дискретно параметризуются по главным осям инерции модели. Данные гистограммы формы имеют три типа: момент инерции по оси, среднее расстояние от поверхности до оси и дисперсия расстояния от поверхности до оси.

В работе [84], в контексте стандарта MPEG 7, 3D объект описывается набором двумерных примитивов. Эти примитивы рассчитываются с использованием различных проекций объекта, полученных под различными углами обзора. Эффективность данного метода зависит от количества построения данных проекций.

В [59] представлен подход быстрого запроса 3D модели. Дескрипторы, которые извлекаются из входной модели, представляют собой геометрические характеристики 3D-объектов и выбираются аналогично базовым критериям, которыми пользуется аналитик (например, углы и грани модели).

К современным исследованиям, продолжающим традиции первой группы методов, можно отнести [74]. В этой работе для каждого 3D изображения непосредственно перед его распознаванием формируется карта глубины под разными углами обзора (рис. 1.1).

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

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

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

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

Аналогичные методы, которые используют плавающее окно 3D детектора обнаружения объекта и его границ, можно найти в работах [79, 82, 86] и других.

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

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

В работе [40] предлагается подход, определяющий похожесть пространственных объектов на основе визуального подобия. Предполагается, что если 3D модели подобны, то со всех углов зрения они должны выглядеть одинаково. Таким образом, сто проекций объекта кодируются с помощью моментов Zernike и дескрипторов Фурье, которые используются для извлечения в качестве характерных признаков.

В [53] представлена сложная методика, представляющая 3D изображения в виде графов, создание которого требует значительных вычислительных затрат. Кроме того, данный метод пригоден только для определенного типа моделей и имеет узкую область применения.

Современные исследования, продолжающие традиции второй группы методов, можно разделить условно на две категории. Первая категория методов анализирует геометрию поверхности пространственного объекта, особенности его локальных участков и/или кривизны его отдельных частей. Вторая категория методов анализирует непосредственно сразу объёмную 3D форму объекта как одно целое.

К первой категории современных методов, дающих инвариантное 3D изображение вне зависимости от его пространственного положения и ориентации, можно отнести работу [36]. Предложенный в ней метод относится к классу спектральных методов на стыке областей спектральной геометрии и дифференциальных уравнений. Этот метод является весьма перспективным, поскольку обеспечивает естественную библиотеку инструментов для анализа непосредственно поверхности 3D объекта в целом, а не его проекций. Данный метод позволяет обнаруживать повторяющиеся регионы на поверхности тела (рис. 1.2).

Гипертрейс-матрица как математический инструмент для анализа 3D изображений

Следовательно, значение элементов трейс-матрицы ТМ при ju 1 увеличатся в fi раз, а при ju \ - уменьшатся в ju раз, если в качестве значения трейс функционала была взята длина высекаемого отрезка. В зависимости от вида функционала Т значения элементов матрицы могут изменяться по разному.

Свойства гипертрейс-матриц в зависимости от операций, применяемых к 3D изображению: 1) Поворот 3D изображения в пространстве. В глобальных осях 3D объекта каждая сканирующая плоскость В будет характеризоваться расстоянием г от начала координат до нее и углами со и ср ( 0 со 2ж, 0 ср ж ), где r/ = [cosco-sin ср, sin со

Как уже было сказано выше, для учета произвольной неизвестной пространственной ориентации объекта необходимо определить ключевые точки, которые однозначно идентифицируются для исходного F и повернутого F изображений еще до занесения результатов сканирования в гипертрейс-матрицу, так как данные точки характеризуют уникальные свойства 3D объекта, независящие от его вращения в пространстве. Ключевым точкам будут соответствовать плоскости в{ц(5,у),г) и B (rj(S ,/ ),r), для которых B{ri(5,y),r) = B {ri(5 ,y ),r).

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

Другими словами, плоскостям В{г,(8,у),г) и В%(8 + л,л-у),г) будут соответствовать диаметрально противоположные точки опорной сетки на сфере. Так как вектор нормали плоскости определяет направление порядка следования сечений 3D объекта сеткой сканирующих плоскостей (элементы матрицы ЗТМ по глубинной оси Or), то через каждый интервал длины по оси Од переворачиваются вертикальные столбцы (ось Оу) и глубинные строки (ось Or) гипертрейс-матрицы ЗТМ. Если плоскость В повернуть в пространстве относительно прямой d на угол — 2 радиан, то она совпадёт сама с собой, в том числе и ее вектор нормали -ц: в{гі(8,у),г) = В {гі(8 + 2ж,у),г) и = -? для любого значения угла д. Поэтому матрица ЗТМ будет 2-периодична в направлении горизонтальной оси Од. 2) Перенос 3D изображения в пространстве.

Если происходит сдвиг исходного 3D изображения на некоторый вектор fa-cos A- sin в; a- sin A- sin в; a-cos в] длины а, то точка (x ,y ,zr) сдвинутого изображения F будет соответствовать точке (x,y,z) исходного изображения F следующим образом: сканирующая плоскость

B (?](8,y),rr-a-(sinj3-siny-cos(8-X)+cosj3-cosy)) сдвинутого изображения F, то при переносе исходного трехмерного изображения на некоторый вектор {a -cos Я- sin f3; a- sin Я- sin В; a- cos /?} произойдет сдвиг строк гипертрейс-матрицы ЗТМ в глубинном направлении на а {sin (3 sin у cos(8 -Я)+со8 (З-cos у) единиц вверх или вниз в зависимости от знака выражения. При этом вертикальные столбцы и горизонтальные строки матрицы ЗТМ остаются на своём месте и не сдвигаются вдоль осей Осо и 0(р, так как при сдвиге 3D изображения угол сканирующей плоскости В (г/(8 ,у ),г% соответствующей сканирующей плоскости В(г/(8,у),г) исходного изображения, не изменяется: 8 = 8, у = у.

Таким образом, при сдвиге 3D изображения в гипертрейс-матрице ЗТМ увеличивается или уменьшается количество нулевых элементов в глубинных строках (ось Or) в зависимости от его приближения или удаления от глобального начала координат. Поэтому 3D трейс-образ изображения будет растягиваться вдоль оси Or на соответствующее число, определяемое вектором переноса. 3) Операция масштабирования 3D изображения в пространстве.

Если происходит масштабирование исходного 3D изображения в ju раз, то точка (x .y .z ) масштабированного изображения F будет соответствовать точке (x,y,z) исходного изображения F следующим образом: Поэтому сканирующей плоскости в(г,(8,у),г) исходного изображения F будет соответствовать следующая сканирующая плоскость В {ц(5 ,у ),г ) масштабированного изображения F\

Функционалы, инвариантные к переносу 3D изображений

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

Так как функционалы, входящие в состав признака, имеют композиционную структуру, то по мере уменьшения шага число сканирований 3D изображения растёт комбинаторно, и время вычисления признака заметно возрастает. Поэтому целесообразно исследовать сканирование 3D изображения на оптимальность соотношения «надежность – быстродействие» распознающей системы при использовании различных параметров сканирования (количество узлов опорной сетки на сфере, количество узлов опорной сетки на окружности и другие).

Все рассматриваемые в данной главе 3D изображения были взяты из известной базы данных принстонского университета The Princeton Shape Benchmark [88]. Каждый пространственный объект данной базы имеют полигональную структуру поверхности. Данная база включает наборы 3D моделей различных классов: от предметов неживой природы (двери, машины, самолёты и другие) до объектов живой природы (муравьи, кошки, люди, птицы и другие). Количество полигонов в моделях объектов варьируется в диапазоне от 1000 до 300 000 штук.

Реализация и экспериментальная проверка предложенного метода 3D трейс-преобразования производилась с использованием инженерного пакета MathCAD 15М030. Визуализация трехмерных объектов осуществлялась с помощью средств пакета MeshLab 1.3.

Обобщая вышесказанное, для достижения цели экспериментальной проверки свойств 3D трейс-преобразования целесообразно решить следующие задачи: 1) определить оптимальные параметры сканирования для достижения наилучшего соотношения «надежность - быстродействие» распознающего алгоритма; 2) экспериментально проверить свойства инвариантности конструируемых признаков к переносу, повороту и масштабированию 3D изображения; 3) оценить погрешность вычисления признаков, описывающих геометрические свойства объектов; 4) сравнить экспериментально результаты стохастического и детерминированного способов сканирования 3D изображений; 5) решить задачу классификации базы данных 3D изображений разработанным и другими известными методами распознавания 3D изображений и сравнить полученные результаты между собой.

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

Во-первых, более общим параметром, влияющим на точность вычисления признака, является параметр N(p - количество узлов опорной сетки на сфере. От него не зависит метод построения трехмерной гипертрейс-матрицы ЗТМ (в отличие от параметров со и ср). Во-вторых, для детерминированного сканирования используется 4 параметра: A3 - расстояние между параллельными плоскостями, Ncp - количество различных углов сканирования плоскостями 3D изображения (количество узлов равномерной опорной сетки на сфере), А2 - расстояние между параллельными прямыми в плоскости сечения, N6 - количество различных углов сканирования прямыми 2D изображения сечения (количество узлов равномерной опорной сетки на окружности).

Для стохастического же сканирования показатель A3 показывает усреднённое расстояние между параллельными плоскостями: A3 = dist / cross, где dist - расстояние между двумя граничными касательными плоскостями в сетке плоскостей под данным углом обзора, cross - количество пересечений 3D объекта сканирующей плоскостью. Аналогичное замечание будет и для показателя А2. Параметры Ncp и N9 для стохастического сканирования характеризуют равномерное случайное распределение точек опорной сетки на сфере и окружности соответственно.

В-третьих, полноценный анализ всех параметров сканирования затруднён, так как точность вычисления признака меняется при совместном изменении параметров сканирования, причём как в прямом, так и обратном направлениях прироста значений данных параметров. Более того, невозможно графически отобразить шестимерное пространство (четыре параметра сканирования Аг, Ncp, Ар, N6, коэффициент относительной погрешности вычисления признака Б и показатель времени t вычисления признака) в трёхмерном пространстве.

Чтобы при анализе конкретной переменной (например, Аг) нивелировать эффект влияния других параметров сканирования изображения, все остальные параметры сканирования {Ncp, Ар, N9) должны иметь такие значения, при которых точность вычисления признака является очень высокой. Тем самым, точность сканирования 3D изображения будет являться чувствительной к изменению только одного параметра (Аг) и не зависеть от уровня значений других параметров. В связи с этим анализ времени вычисления признака не предоставит информативной картины, так как вычисление признака будет осуществляться достаточно долго. В этом случае необходимо руководствоваться общим принципом при отборе требуемого уровня точности вычисления признака: чем крупнее шаг сканирований и меньше число узлов на сетке, тем меньше времени требуется на его вычисление.

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

Экспериментальная проверка свойств инвариантности конструируемых признаков к переносу, повороту и масштабированию 3D изображения

Данный результат затем делится на максимально возможное значение DCG статистики, то есть такого значения, которое было бы получено, если все первые N элементов списка R имели бы правильно распознанный класс: DCG- DCG . 1=2log2(i) Применительно к задаче классификации, расчёт показателя DCG будет производиться следующим образом. Список объектов в классе будет ранжироваться по расстоянию объектов до средней характеристики объектов в классе. Затем, аналогично показателям precision и recall, будет рассчитываться усреднённое значение DCG-статистики по всем классам, где количество ранжированных списков і? и их показателей DCGt будет равно количеству классов:

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

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

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

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

Опорная сетка на полусфере с вдвое меньшим числом узлов: а) для детерминированного сканирования; б) для стохастического сканирования Стоит отметить, что при таком способе построения опорной сетки на сфере в плоскости Оху будет находиться только половина точек окружности, которая получается при пересечении плоскостью z = 0 сферы с единичным радиусом и центром в начале координат. Аналогичное свойство будет находить своё отражение в генерации узлов и для стохастического способа сканирования.

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

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

В-третьих, в целях повышения качества работы распознающего алгоритма из списка формируемых функций для каждого типа функционала были удалены те, применение которых могло бы заведомо вызвать высокую коррелированность вычисляемых значений признаков. Такие функционалы вносят приблизительно одинаковый вклад в информативность конструируемого признака. Например, 2 0О и „ІЦх, однотипны в смысле различающей способности признака, так приблизительно одинаковую лепту в повышение (понижении) информативности признака.

Следовательно, каждый тип функционала Т, Р, в, НурегР, Нурегв будет иметь свой набор функций, который они будут принимать при вычислении признака. Так, в трейс функционале Т было использовано всего четыре вида функционала: число пересечений одной сканирующей прямой с 2D изображением сечения, сумма длин отрезков пересечения одной сканирующей прямой с 2D изображением сечения, а также максимальная и минимальная длины отрезков пересечения одной сканирующей прямой с 2D изображением сечения. Это объясняется тем, что в целях повышения информативности конструируемых признаков, например, вряд ли эффективным будет вычисление прироста значений длин отрезков, высекаемых одной сканирующей прямой на 2D изображении сечения, так как число таких отрезков, как правило, не более трёх-четырёх. Только для сложно структурированных 3D объектов (например, 3D изображение храмового комплекса) данное значение будет в пределах 10 и выше, а таких классов в исследуемой базе всего несколько.

Аналогично, в функционале Р неэффективным будет вычисление гармоник при разложении функции g(e,p) в ряд Фурье по столбцам р трейс-матрицы ТЫ, так как функция g(e,p) описывает особенности формы 2D изображения сечения под конкретным углом в .

Согласно данному принципу отбора, функционалы Т, Р, в, НурегР, Нурегв будут иметь 4, 32, 16, 32, 16 различных видов принимаемых функций соответственно. Поэтому возможно построение 4-32-16-32-16 = 1048 576 потенциально различных по информативности признаков. Для сравнения, в общем случае с учётом коррелированности признаков по разработанной программе всего можно построить 645 = 1 073 741 824 признаков для двумерной гипертрейс-матрицы 2ТМп [22].

В-четвёртых, в целях повышения качества работы распознающего алгоритма для решения задачи классификации 907 объектов было построено 70 признаков с заранее предопределёнными свойствами, которые определяют те или иные геометрические особенности 3D объекта. Такие признаки с высокой вероятностью должны оказаться информативными. Остальные ИЗО признаков были случайным образом сгенерированы из заданного списка функционалов, так, чтобы вероятность появления двух одинаковых признаков (с одинаковой последовательностью композиции функционалов) была ничтожна мала.