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

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

Введение

Глава 1. Постановка задач и обзор методов 8

1.1. Постановка задач распознавания и позиционирования 8

1.2. Обзор методов распознавания образов 12

1.3. Обзор методов вычислительной геометрии 25

1.4. Выводы 32

Глава 2. Алгоритмы вычислительной геометрии 33

2.1. Необходимые сведения о метрике Никодима 33

2.2. Алгоритмы минимизации на -сетях большого объема 38

2.3. Алгоритмы построения пересечения полигонов 45

2.4. Алгоритмы кусочно-линейной аппроксимации 50

2.5. Выводы 60

Глава 3. Позиционирование летательных аппаратов 62

3.1. Математическая модель оптического канала 62

3.2. Решение задачи позиционирования методом внешних контуров 72

3.3. Решение задачи позиционирования методом опорных точек 85

3.4. Оценки точности алгоритмов позиционирования 95

3.5. Выводы 101

Глава 4. Распознавание летательных аппаратов и наземных объектов 103

4.1. Распознавание летательных аппаратов на фоне небосвода 103

4.2. Распознавание летательных аппаратов на фоне аэродрома 114

4.3. Распознавание наземных объектов на подстилающей поверхности 128

4.4. Выводы 138

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

• Обзор методов распознавания образов
• Алгоритмы минимизации на -сетях большого объема
• Решение задачи позиционирования методом внешних контуров
• Распознавание летательных аппаратов на фоне аэродрома

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

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

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

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

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

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

Задачи диссертационной работы.

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

2. Применение метрики Никодима совмещения внешних контуров для решения задачи распознавания летательных аппаратов на динамических изображениях в полете на фоне небосвода.

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

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

Направление исследований. Развитие методов распознавания летательных аппаратов и наземных объектов в оптических и лазерных каналах.

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

Научная новизна.

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

6. С целью ускорения вычисления невязки внешних контуров по метрике Никодима предложен алгоритм построения пересечения полигонов на основе построения минимальных по числу структурных элементов выпуклых упаковок, что позволяет обеспечить ускорение вычислений в 5-И1 раз по сравнению с алгоритмами из библиотек GPC, Boost и Clipper.

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

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

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

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

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

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

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

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

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

Реализация результатов исследований. Алгоритмическое и программное обеспечение, разработанное в рамках диссертационной работы, использовалось при проведении исследований в организации НИЦ (г. Тверь) ЦНИИ ВВКО Минобороны России при выполнении НИР «Решетник» (2011 -2013 гг.), НИР «Таймень» (2015 - 2016 гг.), НИР «Грейфон 7» (2015 г.), НИР «Фон-13» (2015 г.), выполняемых по заказу Минобороны России.

Апробация работы. Основные результаты диссертации докладывались на конференциях: 55-я научная конференции МФТИ, 56-я научная конференции МФТИ, Теория и практика системного анализа 2014, 57-я научная конференции МФТИ, 13-я Международная конференция «Авиация и космонавтика-2014», на совещаниях НИИ ТП (г. Москва) и

на семинаре кафедры «Теоретическая кибернетика» СПбГУ.

Публикации. Основные результаты диссертации опубликованы в 15 печатных работах, в том числе 6 статьях в журналах, рекомендованных перечнем ВАК, 5 работах в материалах научно-технических конференций, 1 монографии, а также получены 3 свидетельства о государственной регистрации программы для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы (98 наименований). Общий объем диссертации – 150 страниц машинописного текста. Диссертация содержит 85 рисунок и 9 таблиц.

Обзор методов распознавания образов

Основой предложенного в работах [20-22] метода решения задачи распознавания летательных аппаратов на фоне небосвода является решение задачи определения их пространственных положений. Изложенный в работе [20] метод определения пространственного положения летательного аппарата (трех линейных и трех угловых координат) заключается в соответствующей обработке его внешнего контура G. В результате по внешнему контуру G с достаточной степенью точности определяются координаты (х,у) проекции центра летательного аппарата, тройка углов (k,t,r) пространственного поворота и расстояние р до летательного аппарата. Следует отметить, что предлагаемый в работе [20] метод определения координат пространственного положения летательного аппарата не является точным, поскольку за точку (х,у) проекции центра летательного аппарата принимается центр масс области, заключенной внутри контура G.

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

Представленные в работе [21] экспериментальные результаты показывают достаточно высокую вероятность порядка 85-95% правильного распознавания на реальных видеоизображениях полетов летательных аппаратов. Однако изложенные в данной работе результаты программной реализации показывают, что при числе летательных аппаратов порядка 10-14 время, затрачиваемое на обработку одного кадра, оказывается равным порядка 3000-4000 мс. В частности, столь высокая временная задержка не позволяет использовать данную программную реализацию при решении задач распознавания в реальном времени. А именно, при частоте кадров 25 Гц требуемое время обработки одного кадра должно быть не 3000-4000 мс, а 30-40 мс. Иными словами, скорость процесса распознавания должна быть увеличена в 100 раз, что требует качественно других программных и математических средств. Предлагаемая в диссертационной работе программная реализация решения задачи распознавания летательных аппаратов основана на использовании алгоритмов с предобработкой, позволяющих существенно ускорить вычисление невязки контуров по метрике Никодима. В результате время, затрачиваемое на обработку одного кадра, оказывается достаточным для решения задачи распознавания в реальном времени.

К задаче распознавания летательных аппаратов в полете на фоне небосвода близка задача распознавания летательных аппаратов на фоне подстилающей поверхности аэродрома, рассматриваемая в работах [23-33]. Другие алгоритмы, связанные с распознаванием летательных аппаратов и близких им геометрических объектов изложены в работах [34-45].

В работе [23] описан алгоритм разбиения бинаризованного изображения летательного аппарата на компоненты связности. Пример данного разбиения показан на рисунке 1.2.3, заимствованном из [23].

Компоненты связности летательного аппарата Распознавание летательных аппаратов осуществляется по их компонентам связности на основе теории моментов с учетом свойств симметрии геометрических форм. В работе [24] дана классификация сегментов компонент связности летательных аппаратов на фоне аэродрома. Изложенный в работе [24] алгоритм работы системы распознавания, основан на построении цепочек фильтрации для каждого сегмента каждой модели летательного аппарата из заданного класса. Геометрической основой данного алгоритма является то, что при повышении пороговой яркости к от минимального значения 0 до максимального значения 255 границы яркости образуют упорядоченное по вложению семейство замкнутых контуров. Поэтому для каждого сегмента летательного аппарата на реальном изображении существует такой диапазон яркостей к0 к ки в котором соответствующие границы яркостей наилучшим образом выделяют конур данного сегмента. Тем не менее, в некоторых случаях не удается должным образом выделить границы сегментов и тогда используемый в работе [24] алгоритм приводит к ошибкам распознавания. Например, вследствие пространственной формы летательного аппарата при наклонных ракурсах его реальное изображение может существенно отклоняться от идеального изображения вида сверху, что приводит к деформациям границ сегментов. Кроме того, границы сегментов могут захватывать посторонние объекты (при их примыкании к корпусу летательного аппарата) и части поверхности аэродрома (по причине локальной засветки или особенностей стоянки). В этих случаях границами яркостей удается выделить только отдельные элементы конструкции летательного аппарата (нос, размахи и заделки крыла, размахи и заделки горизонтального стабилизатора). В диссертационной работе будет изложен алгоритм распознавания летательных аппаратов по элементам их конструкции. Совместное использование алгоритмов распознавания по сегментам летательных аппаратов и элементам конструкции летательных аппаратов предоставляет потенциальную возможность увеличения вероятности правильного распознавания.

В работах [25-26] описан алгоритм распознавания на основе сопоставления изображения летательных аппаратов и их тени с эталонными изображениями, полученными в результате рендеринга 3D моделей летательных аппаратов заданного класса. Особое внимание уделяется переносу вычислений с CPU на GPU CUDA. Время распознавания изображения при 70 моделях составляет порядка 4.5 с.

В работе [27] описан алгоритм распознавания летательных аппаратов на основе двумерного фильтра Габора, вычисляемого при различных трансформациях входного изображения. Алгоритм работает на изображениях летательных аппаратов, как на рисунке 1.2.4, заимствованном из [27].

Алгоритмы минимизации на -сетях большого объема

Перечислим необходимые сведения геометрического характера [69]. Множество X называется метрическим пространством, если в нем задана функция р: XxX R, называемая расстоянием и удовлетворяющая следующим свойствам: 1. Невырожденность р(х, у) = 0ох = у. 2. Симметричность р(х, у) = р(х, у). 3. Неравенство треугольника p(x,z) р(х,у) +p(y,z). При фиксированных х0 и г О множество B(xQ,r) = {хєХ: р(х0,х) г} называется открытым шаром радиуса г с центром х0. Множество [/с! называется открытым, если для любого x0eU существует г 0 такое, что B(xQ,r) U.

Метрическое пространство X называется компактным, если каждое его покрытие открытыми множествами содержит конечное подпокрытие. Важнейшим свойством компактного метрического пространства является существование конечной є -сети.

Построение конечной -сети х0,х1,...,хп в компактном метрическом пространстве осуществляется по следующему алгоритму. Точка х0 є X выбирается произвольно. Пусть точки х0,...,хп_х построены. Далее, точка хпєХ выбирается произвольно вне объединения шаров В(х0,є)и...иВ(хп_1,є). При добавлении каждой новой точки хп указанное объединение шаров увеличивается. Алгоритм заканчивает работу на таком номере п, при котором X = B(X0,S)KJ...KJB(X„,S). Конечная -сеть х0,х1,...,хп дает дискретизацию компактного метрического пространства X . В дальнейшем при решении задач распознавания существенную роль играет метрика Никодима [70]. На множествах A, B R2 абсолютная метрика Никодима задается по правилу р(А, В) = S(A и В)- S(A п В), где S - площадь. Относительная метрика Никодима задается по правилу S(AvB)-S(AnB) S(AuB) Поскольку S(A KJB) = S(A) + S(B) - S(A n B) для вычисления расстояний по метрикам Никодима достаточно знать площадь множества А, площадь множества В и площадь их пересечения АглВ.

Покажем, что относительная метрика Никодима удовлетворяет аксиомам метрического пространства. Невырожденность и симметричность относительной метрики Никодима очевидны. Рассмотрим три области А, В,С, произвольным образом расположенные на плоскости. Для доказательства неравенства треугольника ju(A, С) ju(A, В) + ju(B, С) требуется доказать, что + s2 + s3 + s4 + s5 + s6 s1+s2+s3+s4+s5+ s7 s1+s2+s3+s4+s6+ s7 где величины 5 1,5 2,...,5 7 имеют смысл площадей, изображенных на рисунке 2.1.1. А именно, S1 - площадь АслВслС, s2 - площадь (АпС)-Ви т. д.

Поэтому элемент g группы G можно ассоциировать с 3 х 3 -матицей Mg = Xcos(p -Xsinq) JC0] Л sincp Xcoscp y0 0 0 Для заданного множества B R2 обозначим через gB множество В, преобразованное элементом g группы G. Величина luinv(A,B) = miniu(A,gB) geG называется инвариантной метрикой Никодима. Инвариантная метрика Никодима используется в тех случаях, когда требуется определять близость множеств A,B R2 независимо от сдвигов, поворотов и растяжений плоскости R2.

Вычисление инвариантной метрики Никодима /Jinv(A,B) сводится к определению сдвига V растяжения Л и поворота р множества В, обеспечивающих минимальную относительную невязку площадей между множеством А и преобразованным множеством В. Точное вычисление параметров сдвига, растяжения и поворота является трудоемкой задачей четырех-параметрической минимизации. Однако в случае приближенного решения задачи сдвиг V может быть определен по формуле v = cA-cB через центры масс СА и Св множеств А и В, растяжение Л может быть определено по формуле diamA diamB через отношение диаметров diam А и diam В множеств А и В, а поворот р может быть определен из совмещения направлений на вершины выпуклых оболочек множеств А и В. В частности, при таком решении задачи некоторый перебор сохраняется только при определении угла поворота р.

Опишем процедуру определения угла поворота р на примере множеств А и В, порожденных внешними контурами летательных аппаратов, как слева и справа на рисунке 2.1.2.

Процедура совмещения Пусть над множеством В осуществлены преобразования сдвига и растяжения, при которых масс Св оказывается совмещенным с центром масс СА, а диаметр diamB оказывается равным диаметру diamA. Для окончательного совмещения множества В с множеством А остается определить угол поворота р. С этой целью на выпуклой оболочке множества А определяется вершина Р0, расположенная на максимальном удалении от центра масс СА. Аналогичным образом на выпуклой оболочке множества В определяется вершина Q0, расположенная на максимальном удалении от центра масс Св. Для более надежного определения угла поворота р к вершине Q0 добавляются еще несколько вершин выпуклой оболочки множества В, расположенные в буферном кольце с центром в Св и внешним радиусом Я = і20-С5. В рассматриваемом примере к вершине Q0 добавлены еще две вершины Ql и Q2, расположенные в буферном кольце ширины R/10. Далее, сдвинутое и растянутое множество В поворачивается вокруг точки СА на углы q Q,q\,... , для которых точки QQ,QX,... оказываются на одном луче с точкой Р0. Угол оптимального поворота р выбирается среди углов (p0,(pv... из соображений минимальности значений относительной метрики Никодима между множеством А и преобразованным множеством В. Для удобства последующего изложения будем так определенный угол р называть углом центрального поворота.

Решение задачи позиционирования методом внешних контуров

Пусть замкнутая аппроксимируемая ломаная G: Р0,Р1,...,Рп_1,Рп=Р0 ориентирована против часовой стрелки. Обычно при решении задачи кусочно-линейной аппроксимации вершины аппроксимирующей ломаной L: F0,Fl,...,Fm_l,Fm=F0 выбираются из множества вершин аппроксимируемой ломаной G. В диссертационной работе аналогом алгоритма кусочно-линейной аппроксимации является алгоритм Рамера-Дугласа-Пекера [74-75]. Основное отличие от алгоритма Рамера-Дугласа-Пекера заключается в правиле выбора вершин аппроксимирующей ломаной.

Зададим точность аппроксимации є О. В практических задачах точность є задается в долях от диаметра d аппроксимируемой ломаной G. В начале алгоритма аппроксимирующая ломаная L задается в виде L: F0,FVF2=F0, где точки F0 и F1 реализуют диаметр d аппроксимируемой ломаной. Это означает, что начальная аппроксимирующая ломаная L состоит из двух отрезков

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

Изложим правило построения вершин аппроксимирующей ломаной L на примере отрезков [F0,Fj и [FVF0]. С этой целью рассмотрим фрагмент аппроксимируемой ломаной G между вершинами F0 и F1.

В алгоритме Рамера-Дугласа-Пекера правило выбора вершины аппроксимирующей ломаной на фрагменте аппроксимируемой ломаной G сводится к решению задачи максимизации где h - расстояние до прямой, проходящей через точки F0 и F1. Далее будет показано, что такое правило выбора вершин аппроксимируемой ломаной в предметной области построения внешних контуров изображений летательных аппаратов не является оптимальным. В этой связи предлагается следующая модификация правила выбора вершин аппроксимирующей ломаной в алгоритме Рамера-Дугласа-Пекера. Рассмотрим точки F0 и F1 как фокусы эллипса. Определим вершину F01 на фрагменте аппроксимируемой ломаной G между вершинами F0 и F1 как решение задачи максимизации r0 + rx —» max, где г0 и / - расстояния от точек F0 и Fl. Параметры а,Ь,с эллипса, имеющего фокусы F0 и Fl и проходящего через точку F01 определяются по формулам \\F0-F\\ с = , IK- oi II+ 1 0i- i II а = , b = i2 = ыа -с Важно заметить, что из определения точки F01 как решения задачи максимизации следует, что все вершины фрагмента аппроксимируемой ломаной G между вершинами F0 и Fx лежат внутри построенного эллипса.

Отрезок [FVF0] анализируется аналогичным образом, что приводит к построению точки F10. Алгоритм заканчивает работу, когда малые полуоси Ъ эллипсов, построенных по указанному выше правилу для всех отрезков [Fk,Fk+l] аппроксимируемой ломаной L: F0,F1,...,Fm_1,Fm=F0, удовлетворяют неравенству Ь є. В случае изображенной на рисунке 2.4.1 аппроксимируемой ломаной G при точности аппроксимации d 53.5 є = — = « 2.675 20 20 результирующая аппроксимирующая ломаная L показана на рисунке 2.4.2 Рисунок 2.4.2 - Результирующая аппроксимирующая ломаная Предлагаемое правило выбора вершин позволяет утверждать, что при всех 0 к т фрагменты аппроксимируемой ломаной G, заключенные между последовательно идущими вершинами Fk и Fk+l результирующей аппроксимирующей ломаной L, лежат в -окрестности отрезков [Fk,Fk+l\ Доказательство включения фрагментов аппроксимируемой ломаной G в -окрестности отрезков с концами в последовательно идущих вершинах аппроксимирующей ломаной L основывается на следующем утверждении. Утверждается, что эллипс с большой полуосью а и малой полуосью Ъ = є лежит в є -окрестности отрезка с концами в фокусах данного эллипса.

Действительно, уравнение рассматриваемого эллипса имеет вид х2 у2 , При этом фокусы располагаются в точках + с на оси абсцисс, где с2=а2-є2. Очевидно, что є -окрестность отрезка с концами в фокусах эллипса, состоит из прямоугольника -С Х С, - у и двух полукругов: правого (х-с)2+у2 s2 прих с и левого (x + c)2+y2 s2 прих -с. Очевидно, что точки эллипса удовлетворяющие неравенству - с х с, лежат в указанном прямоугольнике. Проверим, что точки эллипса (х,у), удовлетворяющие неравенству с х а, лежат в правом полукруге, а точки эллипса (х,у), удовлетворяющие неравенству - а х -с, лежат в левом полукруге. Из соображений симметрии достаточно рассмотреть случай правого полукруга.

При с х а квадрат расстояния от точки фокуса (с,0) до точки эллипса (х,у) имеет вид функции f(x) = (x-cf+s2 с линейной производной вида 1 1 а2 X f (x) = 2(x-c)-2s2 Легко видеть, что f (c) = -2s2 2 и 2 1 f (a) = 2{a-c)-2s21- = 2{a-c)-2(a2-c2)1 = -2{a-c)C- 0. а а а Поэтому на отрезке [с, а] функция f(x) убывает, а значит на этом отрезке с2Л є2 1 а2 f(x) f(c) = є2 Отсюда эллипс с полуосями а и є а лежит в є -окрестности отрезка с концами в фокусах эллипса.

Отличие предлагаемого правила выбора вершин аппроксимирующей ломаной L от правила выбора, используемого в алгоритме Рамера-Дугласа-Пекера, заключается в следующем. В алгоритме Рамера-Дугласа-Пекера новые вершины аппроксимирующей ломаной выбираются на фрагменте аппроксимируемой ломаной G между вершинами Fk и Fk+1 при выходе данного фрагмента за бесконечную полосу шириной 2є с центральной прямой, проходящей через точки Fk и Fk+1. Поэтому если все вершины рассматриваемого фрагмента ломаной G лежат в данной полосе, новая вершина аппроксимируемой ломаной из вершин данного фрагмента не будет выбрана. При этом вершины рассматриваемого фрагмента могут лежать на сколь угодно большом расстоянии от точек Fk и Fk+1, что в ряде случаев приводит к снижению качества аппроксимации. В предлагаемом алгоритме вершины аппроксимирующей ломаной выбираются при выходе фрагмента аппроксимируемой ломаной G за эллипс с фокусами в точках Fk и Fk+1 и малой полуосью Ъ = є. Как показано в предыдущем разделе, данный эллипс лежит в є -окрестности отрезка с концами в точках Fk и Fk+1. В частности, это устраняет указанный выше недостаток алгоритма Рамера-Дугласа-Пекера. Проведем сравнение предлагаемого алгоритма с алгоритом Рамера-Дугласа-Пекера в предметной области кусочно-линейной аппроксимации границ яркостей изображений летательных аппаратов. На рисунке 2.4.3 при точности аппроксимации d є = — для аппроксимируемой ломаной G с « = 214 вершинами слева изображена аппроксимирующая ломаная L с т = 14 вершинами, построенная по предлагаемому алгоритму, а справа изображена аппроксимирующая ломаная R с m = 14, построенная по алгоритму Рамера-Дугласа-Пекера.

Распознавание летательных аппаратов на фоне аэродрома

Геометрическая суть метода опорных точек заключается в решении задачи позиционирования пространственного треугольника. Пусть треугольник с вершинами QI,Q2,QT, и длинами сторон гх,г2,гъ расположен в пространстве

R3 так, что ни одна из его вершин не попадает в начало координат. Обозначим через VVV2,V3 центральные проекции вершин QVQ2,Q3 на единичную сферу S2. Очевидно, для некоторых tvt2,t3 имеют место соотношения hvi -чуіі=ri2 \\t2V2 3V3\\2 = r22, {t f =r32. Зададим скалярные произведения s2=(v2,V3), s3=(V3,V1). Тогда tx2-2sxtxt2+t22=rx2, 9 9 9 t2 — 2s2t 2t 3+t3 = r2 , 9 9 9 t3 — 25,3ґ3ґ1+/1 = r3 . Полученная алгебраическая система трех уравнений относительно трех неизвестных tx,t2,t3 обладает следующим свойством: если тройка чисел tx,t2,t3 является ее решением, то тройка чисел x,2,3 также является ее решением. Поскольку каждое уравнение системы имеет вторую степень, после исключения неизвестных t2 и t3 получаем четное алгебраическое уравнение восьмой степени относительно неизвестной tx вида а4 (г, s)t\ + а3 (г, s)tx6 + а2 (г, s)t + ах (г, s)tx2 + а0 (г, s) = 0. Явные выражения коэффициентов aA(r,s), a3(r,s), a2(r,s), ax(r,s), aQ(r,s) через параметры r = (rx,r2,r3) и s = (sx,s2,s3) имеют достаточно громоздкий вид и приводиться не будут. Очевидная замена х = tx сводит задачу к уравнению четвертой степени a4(r,s)x4 +a3(r,s)x3 +a2(r,s)x2 +ax(r,s)x + aQ(r,s) = 0 допускающее точное решение в радикалах. С учетом кратности уравнение четвертой степени с вещественными коэффициентами может иметь только четное число вещественных решений. Поэтому с учетом кратности имеется два или четыре пространственные положения треугольника с длинами сторон rx,r2,r3, для которых вершины QX,Q2,Q3 проектируются в точки VX,V2,V3 единичной сферы.

Решение задачи позиционирования летательного аппарата по методу опорных точек осуществляется в автоматизированном режиме. В связанной системе координат PXYZ математической модели летательного аппарата задается т +1 набор Qk,Qk,Qk,Qk,Qk, где 0 k m, из трех основных Qk,Qk,Qk и двух контрольных Qk,Qk опорных точек. С каждой тройкой точек Qk,Qk,Qk связывается система координат с началом в точке Q\ и ортами X , У , Z выражаемые через векторы A = Q?-Q%, B = Qk-Qk, по правилам Хк = A A Yk = АхВ \АхВ\\ Zk = XkxYk XkxYk Геометрическая идея метода заключается в том, что при определении пространственного положения точек Q1k ,Q2k ,Q3k в системе координат оптического канала однозначным образом определяется положение вспомогательной системы координат Q2k XkYk Zk , через которую однозначным образом определяется положение связанной системы координат PXYZ летательного аппарата.

Изложим алгоритмическую суть метода, когда три основные точки Q10 ,Q20 ,Q30 установлены на носу и размахах крыла, а две контрольные точки Q40 ,Q50 установлены на горизонтальных стабилизаторах, как на рисунке 3.3.4. Зададим расстояния і= Q\ Qi r2= Qi бз з= бз — Q\ между основными опорными точками. Далее расстоянияrx,r2,r3 используются при решении задачи позиционирования пространственного треугольника способом, изложенным в разделе 3.3.4.

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

С помощью пикселей рх,р2,р3 и вектор-функции V(p) трассировки приемной матрицы определяются три нормированные направления Vx=V(px), V2=V(p2), V3=V(p3), по которым вычисляются три скалярные произведения si=(yvV2), s2=(V2,V3), s3=(V3,Vx). Полученные наборы параметров r = (rx,r2,r3) и s = (sx,s2,s3) позволяют найти все ветви пространственных положений основных опорных точек QX,Q2,Q3 летательного аппарата. В конечном счете, после выбора правильной ветви, это позволяет получить решение задачи позиционирования - определения положения связанной системы координат PXYZ летательного аппарата в системе координат оптического канала.

Для каждой ветви решения пространственные положения опорных точек QX,Q2,Q3 в системе координат оптического канала задаются формулами Qx=C + Vxtx, Q2=C + V2t2, Q=C + V3t3, где С - точка положения оптического центра. В соответствии с полученными в разделе 3.3.4 формулами величина tx 0 определяется из соотношения t\ = х, где х - положительное решение уравнения a4(r,s)x4+a3(r,s)x3+a2(r,s)x2+a1(r,s)x + a0(r,s) = 0.

Далее, величины t3 О и t2 О определяются как решения уравнений Неоднозначность решений алгебраических уравнений приводит к нескольким ветвям решения задачи позиционирования. Правильная ветвь решения определяется при помощи пространственных положений контрольных опорных точек Q4,Q, однозначно соответствующих пространственным положениям основных опорных точек Qi ,Q2 ,Q% .

Поясним сказанное в случае, когда в вычислениях участвует только одна контрольная опорная точка Q5. При помощи введенного оператором пикселя р5 и вектор-функции V(p) трассировки приемной матрицы определяется нормированное направление V5=V(p5). Каждой ветви положения основных опорных точек Qi ,Q2,Ql однозначным образом соответствует положение контрольной опорной точки б5. Правильной ветви решения соответствует то положение контрольной опорной точки 2, при котором она ближе всего располагается к лучу, идущему из оптического центра С в направление вектора V5.