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

4В0ии£3

БУГАЕНКО ЕЛЕНА ИВАНОВНА

МЕТОД, АЛГОРИТМ И СПЕЦИАЛИЗИРОВАННОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ФОРМИРОВАНИЯ ПАНОРАМНЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ МЕТРИЧЕСКИХ ДЕРЕВЬЕВ

05.13.05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Курск 2011

1 6 июн 2011

4850023

Работа выполнена в ГОУ ВПО «Юго-Западный государственный университет» на кафедре «Вычислительная техника» в совместной научно-исследовательской лаборатории Центра информационных технологий в проектировании РАН и Юго-Западного государственного университета «Информационные распознающие телекоммуникационные интеллектуальные системы».

Научный руководитель: заслуженный деятель науки РФ, доктор

технических наук, профессор Титов B.C.

Официальные оппоненты доктор технических наук, профессор

Бурмака А. А.

кандидат технических наук Таныгин М.О.

Ведущая организация: Учреждение Российской академии наук

Институт проблем информатики РАН

Защита диссертации состоится «27» июня 2011 г. в 14.00 часов на заседании сов! по защите докторских и кандидатских диссертаций Д212.105.02 при ГОУ ВП Юго-Западный государственный университет по адресу: 305040, Курск, ул. 50 л Октября, 94.

С диссертацией можно ознакомиться в библиотеке Юго-Западно государственного университета.

Автореферат разослан «25» мая 2011 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью, про направлять по адресу: 305040, Курск, ул. 50 лет Октября, 94, ЮЗГУ, учен секретарю совета по защите докторских и кандидатских диссертаций Д212.105.0

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д21 д.т.н., профессор

Зотов]

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В настоящее время достигнут значительный прогресс в решении указанной задачи и наибольший вклад в развитие методов и устройств формирования панорамных изображений, а также методов выделения, описания и сопоставления особенностей изображений, как наиболее важных этапов обработки изображений, внесли С. Harris, M. Brown, H. Moravec, M. Stephens, J. Shi, C. Tomasi, H. Wang, M. Brady, RI. Hartley, A. Zisserman, P. Torr, A. Zisserman, B. Triggs, R. Szeliski, M. Irani, R. Radke, P. Ramadge, T. Echigo, S. Iisaku, T. Lindeberg, К. Mikolajczyk, С. Schmid, J. Matas, О. Chum, M. Urban, T. Pajdla, D. Capel, D. Lowe, H. Bay, T. Tuytelaars, L. Van Gool, Сойфер B.A., Потапов A. A., Пахомов A. A., Никитин С. A., Гуляев Ю. В., Фурман Я.А. Существенные результаты в данной области получены в отечественных работах, выполненных в Институте прикладной математики РАН, Московском государственном университете, Московском физико-техническом институте и в других организациях. Однако большинство из известных методов и устройств имеют существенные недостатки, такие как низкая производительность, являющаяся следствием большой вычисщгтельной сложности алгоритмов, и низкая точность результирующих изображений, обусловленная наличием случайных искажений различной природы на исходных изображениях. Кроме того, не в полной мере решена задача сопоставления объектов изображений, имеющих схожие характеристики, что также обуславливает понижение точности панорамных изображений.

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

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

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

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

Диссертационная работа выполнена в рамках Федеральной Целевой Программ «Научные и научно-педагогические кадры инновационной России», которые ведутся Юго-Западном государственном техническом университете Госконтракт П2398 17.11.2009 г. «Создание интеллектуальной оптико-электронной системы д очувствления и управления транспортным роботом», при финансовой подцерз программы «Участник молодежного научно-инновационного конкурса» («У.М.Н.И.К.») теме «Разработка способов и устройства повышения качества изображен»" Госкошракт №7463р/10265 от 04.12.2009.

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

Задачи исследования, решаемые в работе:

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

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

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

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

Новыми научными результатами и положениями, выносимыми на защи являются:

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

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

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

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

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

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

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

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

Результаты диссертационной работы внедрены в ООО «ЯНДЕКС» в прототипах разрабатываемых продуктов и используются в учебном процессе Юго-Западного государственного университета на кафедре ВТ по дисциплине «Архитектура систем обработки, анализа и интерпретации данных».

Соответствие паспорту специальности. Согласно паспорту специальности 05.13.05 - Элементы и устройства вычислительной техники и систем управления, проблематика, рассмотренная в диссертации, соответствует следующим областям исследования:

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

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

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на международных и российских конференциях: Всероссийская конференция по проблемам информатики, физики и химии (г. Москва РУДН 2005 г.); Оптико-электронные- приборы и устройства в системах распознавания образов, обработки изображений и символьной информации «Распознавание 2005, 2008, 2010» (г. Курск, Курский государственный технический университет 2005, 2008, 2010 гг.); «Молодежь и XXI век: 2005,2006,2007» (г. Курск, Курский государственный технический университет 2005, 2006, 2007 гг.), Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУ СУР - 2007» (г. Томск 2007 г.), Международная научно-техническая конференция «Медико-экологические технологии-2007» (г. Курск, Курский государственный технический университет 2007 г.), Международная конференция «Распознание образов и анализ изображений: новые информационные технологии» (г. Йошкар-Ола 2007 г.), Международная научно-

техническая конференция «Биомедицинские и технические системы: анат проектирование и управление» (г. Курск, Юго-Западный государственный университ 2008, 2009, 2010, 2011 гг.), Международная научно-техническая конферен «Диагностика - 2009» (г. Курск, Курский государственный технический университет 200 г.), а также на научно-технических семинарах кафедры «Вычислительной техники» с 20 по 2011 годы.

Публикации. Основные результаты выполненных исследований и разрабо опубликованы в 14 печатных работах, в том числе в 6 статьях. Среди них: 3 стать опубликованные в рецензируемых научных журналах., входящих в перечень журналов изданий, рекомендуемых ВАК РФ, а также 3 патента Российской Федерации.

Личный вклад автора. В работах, опубликованных в соавторстве, лич соискателем предложены: в [1, 6, 15] - метод формирования панорамных изображений, [7, 12, 14] - метод и устройства создания панорамных изображений на основе поис особенностей с коррекцией геометрических искажений, в [2,3,4,5,6, 8,10,11] - методы устройства автоматического определения и коррекции радиальной дисторсии.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Низкая точность сопоставления обусловлена использованием данных, полученнь из исходных искаженных радиальной дисторсией изображений, и применени алгоритмов сопоставления, не учитывающих специфику анализируемых данны Существующие алгоритмы сопоставления, применяемые при сопоставлении особых точ SIFT (Scale-invariant feature transform) или SURF (Speed-Up Robust Features) принимают расчет только информацию об окрестности особой точки (дескриптор), но не использ; информацию о взаимном расположении особых точек на изображении, поэтому они име высокую вероятность ошибочных сопоставлений, что приводит к выполни дополнительных действий, таких как фильтрация ложных сопоставлений, как в раС Кудряшова А.П., или увеличению количества итераций при подборе трехмерной моде снимаемой сцены, что в целом негативно сказывается на производительности. Кроме то производительность снижается из-за необходимости оценки всех возможных вариант сопоставления.

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

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

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

Во второй главе разработана математическая модель ММсвуфпи специализированного вычислительного устройства формирования панорамных изображений (СВУФПИ):

ММСВУФП1Г — МСЯЯ(Л/ рмп(Мсот вог(МКРД№ОЮ>Д<М«/)))))))> (1)

которая описывает преобразование пары входных изображений 1ВХ1,1ВХ2 в панорамное изображение 1,ш,, выполняя операции, описанные следующими моделями: МВИ - модель ввода изображений; Мокрд - модель определения коэффициента радиальной дисторсии; Мкрд " модель коррекции радиальной дисторсии; Мваг - модель выделения особых точек на изображениях; - модель создания дескрипторов особых точек; МШ(Ц- модель

построения метрических деревьев для хранения дескрипторов особых точек; MCXJT -модель сопоставления особых точек; Мрмп- модель расчета матрицы преобразования; Маш - модель соединения исходных изображений.

Модель ввода изображений рабочей сцены МВИ = /(/йг,,/аг2) описывает преобразование входных цифровых изображений /ДГ1,/Ш.2 (цветовая модель RGB) в изображения 1т и 102 (цветовая модель RGB) и соответствующие рабочие изображения /, и /2 в градациях серого.

Если коэффициент радиальной дисторсии не задан, то его определяют в соответствии с моделью определения коэффициента радиальной дисторсии ^окрд =/(^ап'^жг'^вди^шдг'^аадз)'

Модель коррекции радиальной дисторсии М№д - f(MS!J,k,) описывает получение изображений 1\, Г2, I'ol и Га1 с восстановленной геометрией и заключается в перемещении точек {xd, yd) исходных изображений на их истинные позиции (х , уи):

Поиск особенностей на изображениях 1\, 1\ выполняют в соответствии с моделью выделения особых точек МЮТ = /(М1(рД) ■

Выделение особых точек основано на расчете определителя матрицы Гессе. Матрица Гессе для точки изображения Х(х,у) выглядит следующим образом:

где Ьа{х,а) - свертка по Гауссу производной второго порядка а2^(сг)/сх2 изображения 7 в точке X, аналогично для и Ь№{х,а), g{a) - функция Гаусса, значение а

позволяет задавать масштаб для вычисления определителей.

Вычисление определителя матрицы Гессе аппроксимируют применением фильтров соответствующего размера ШНаррпа)=МоМп1-(Ъ.9Мху)г, где М^, и М)у -значения, полученные в результате применения фильтров к изображению по соответствующим направлениям, что повышает точность и скорость выявления особых точек. Для обеспечения инвариантности к изменению масштаба поиск особых точек осуществляют на нескольких масштабах исходных изображений. Для этого создают серии карт откликов, содержащих рассчитанные значения определителей для различных

(2)

Н(х,<т)~-

L (х,ст) L (х,а) '

(3)

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

Для сопоставления особых точек создаются дескрипторы на основе их окрестносте в соответствии с моделью создания дескрипторов Мw = f{MBOT), которая позволя ассоциировать каждую особую точку с некоторым вектором значений (векторо. признаков) и обеспечивает инвариантность к незначительным изменениям угла обзор сцены, условий съемки (освещенности).

Формирование дескрипторов основано на использовании откликов вейвлега Хаар первого порядка и включает определение ориентации окрестности особой точки вычисление сумм вейвлета Хаара в соответствии с подходом SURF (Speed-Up Robu Features). Хранение дескрипторов особых точек организовано в виде метрически деревьев, их создание описывается моделью построения метрических деревь

мшд=кмсд).

Создание метрического дерева происходит последовательным добавление дескрипторов Оп к наиболее подходящему узлу. Первоначальный поиск рассчитан на что существует такой листовой узел в поддереве Г(Ог), радиус покрытия которого больше, чем расстояние между родительским узлом и новым объектом:

d(Or,On)<r(Or), (4)

где d - расстояние между родительским узлом и новым объектом (особой точкой), г радиус покрытия узла.

Анализ дерева начинается с корня и постепенно происходит спуск к иском on листовому узлу. На каждом уровне анализируется очередное поддерево. Если существу более одного поддерева, которое удовлетворяет (4), то выбирается поддерево О. * наименьшим расстоянием до нового объекта 0*\mm{d (Ог *, О,)). Если ни одного объе в соответствии с (4) не найдено, то выбирается узел Ог *, ближайший к новому объе при условии 0*\mm(d{0*,0n)~r{0*)). Далее увеличивают радиус покры найденного дочернего узла до тех пор, пока новый объект не будет покрыт. Новый рад] определяют как r(0*) = d(0*,0n). Хранение дескрипторов особых точек в метричеы деревьях организовано для возможности дальнейшего использования при сопоставлеш изображений, учитывающего взаимосвязи особых точек.

Сопоставление особых точек основано на поиске «ближайших» и. «соответствующих» поддеревьев с дескрипторами в метрических деревьях и описывае моделью сопоставления особых точек Мсот = /(Мпт).

Исходя из того, что исходные изображения имеют общие области, то существу такое поддерево T(Ot) е 7¡, которое соответствует поддереву Т(0})еТг, 7¡ и Т2 множества деревьев созданных после формирования дескрипторов особых точек дв рабочих изображений.

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

d(0,)е [d(0,) - y,d(0,) + 7}, r{Oj) б [r(0,,0„.)-ь-,г(ОпОр1) + е], (5) где у,е - величины допустимых отклонений значений, определяются экспериментально.

Когда найдено первое совпадение, т.е. определены поддеревья, для котор выражения (5) выполняются, происходит сравнение их «соседних» объектов по тем параметрам. Если не менее трех уровней выбранных поддеревьев соответству выполняют сравнение по значениям. Между соответствующими объектами рассчитыв; евклидово расстояние гЕ(ОпОЛ в пространстве признаков, значения которых содер

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

Как только первая пара поддеревьев 7(0,) е 7J и T(Oj)eT2 определена, поиск заканчивается. Данные поддеревья содержат необходимое количество объектов-дескрипторов, которые позволяют продолжить формирование панорамных изображений. Результатом сопоставления является множество «соответствующих» особых точек, на основе которых вычисляют матрицу преобразования Г'изображения Г02 в соответствии с моделью расчета матрицы преобразования МРШ = f(MCj3T).

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

После определения матрицы преобразования V, выполняют собственно преобразование и соединение исходных изображений, этот процесс описывается моделью соединения изображений Маш = ${МРШ,Мщ>д)- Трансформацию изображения Г02 производят в соответствии с правилами выполнения аффинных преобразований rol=rol-V, и затем соединяют изображения Гт с 1"02 на основе применения многомасштабного сплайна методом широкодиапазонного смешивания (multi-band blending). В результате соединения получают итоговое панорамное изображение Iш.

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

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

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

Сущность метода (патент №2365998) заключается в том, что на основе обработки поступающих в СВУФПИ двух изображений выполняют:

- создание рабочих изображений в градациях серого;

- определение коэффициента радиальной дисторсии, если он не задан;

- коррекцию радиальной дисторсии;

- выделение особых точек на рабочих изображениях;

- создание дескрипторов для особых точек;

- построение метрических деревьев для хранения дескрипторов;

- сопоставление особых точек;

- вычисление матрицы преобразований на основе найденных соответствий;

- трансформацию и соединение входных изображений, скорректированных радиальной дисторсии.

Алгоритм формирования панорамных изображений, реализующий рассмотренны

метод, представлен на рис. 1.

Рис. 1. Алгоритм формирования панорамных изображений На основе данного метода формирования панорамных изображений разработа СВУФПИ (рис. 2), которое состоит из программируемой логической интегральной схем (ПЛИС) Уи1сх 4 ХС4У8Х35, цифрового сигнального процессора (ЦСП) ТМ8320Р281 быстродействующего ЗУ1 объемом 64кб, подключенного непосредственно к ПЛИС работающего на частоте ПЛИС, ЗУ2 объемом 128Мб, блока синхронизации и элемент взаимодействия с внешними устройствами (блок ввода и коррекции изображения, бл передачи).

Пересекающиеся

Рис. 2. Обобщенная структурная схема СВУФПИ СВУФПИ включает блоки: ввода изображений БВИ; коррекции изображений влияния радиальной дисторсии БКРД; определения коэффициента радиальной дистора

БОКРД; выделения особенностей БВО; формирования дескрипторов БФД; построения метрических деревьев БПС; анализа и выявления соответствующих точек БАиВСТ; вычисления матрицы преобразования БВМП; соединения изображений БСИ; ЗУ1 -быстродействующее ОЗУ, использующееся для хранения промежуточных данных, таких как карты откликов, метрические деревья и соответствующие особые точки; ЗУ2 - ОЗУ для хранения исходных и результирующего изображений (рис. 3).

изображений

БВИ

БКРД

БСИ

С«

щ

Контроллер обмена

"Блок выделения и анализа особенностей

БВО

Ж

БФД

31

ж

БПС БАиВСТ

ж

Контроллер I Л—Д, ЗУ1

ЗУ1 МГП/ I

плис

ж

Блок синхронизации

Ж

ж

ЦСП ЗУ2

! БОКРД ! ! БВМП 1 1 1

' Общий ] | Управление, |алгоритм 1 I синхронизация ]

ж

| Блок передачи

Рис. 3. Структурно-функциональная организация СВУФПИ Отличительной особенностью структурно-функциональной организации СВУФПИ является реализация большей части вычислений на ПЛИС, что, во-первых, позволило реализовать параллельные вычисления (рис. 4) и повысить производительность устройства, как за счет параллельности выполнения, так и за счет индивидуальной реализации каждой вычислительной процедуры строго в соответствии с алгоритмом без накладных расходов, характерных для процессорной реализации, и, во-вторых, - снизить вычислительную сложность выполняемых на ЦСП операций.

Рис. 4. Структурно-функциональная организация СВУФПИ с параллельной архитектурой

Так, на ПЛИС реализованы блоки БКРД, БФД, БПС, БАиВСТ, БСИ, БВО. Подключение ЗУ1 непосредственно к ПЛИС обеспечивает обмен данными на частоте работы самой ПЛИС, что намного больше частоты работы основного ЗУ2, используемого для хранения больших по размеру изображений. Принцип функционирования блока ввода и коррекции изображения заключается в переносе точек исходных изображений на их

истинные позиции. Отличительной особенностью функционирования СВУФПИ являете коррекция радиальной дисторсии в зависимости от условий получения изображения: пр единственном изображении, содержащим прямые линии (патент №2351091), npi нескольких изображениях, полученных специальным образом (патент №2346326).

Отдельно следует подчеркнуть особенности блоков БПС и БАиВСТ, аппарата реализующих алгоритмы построения метрических деревьев и выполнения поиск соответствующих поддеревьев, что позволило сопоставлять особые точки с существенн большей скоростью. Структура метрического дерева для повышения производительност хранится в ЗУ1.

Отличительный принцип функционирования СВУФПИ заключается в том, что ЦС управляет процессом создания панорамных изображений, управляет вводом изображен! выполняет операции блоков БОКРД и БВМП; ПЛИС выполняет остальные наиболе значимые операции в соответствии с алгоритмом формирования панорамнь изображений, обмен информацией внутри ПЛИС организован по внутреннему интерфейс} соединенному с общим интерфейсом через контролер обмена; внутренний интерфей ПЛИС соединен с ЗУ1 через контроллер, управляющий доступом к ЗУ1.

В четвертой главе приведено описание разработанного аппаратно-программно комплекса (АПК) для проверки адекватности положений, полученных в результат теоретических исследований математической модели специализированног вычислительного устройства и метода формирования панорамных изображений, а так определения точности сопоставления и производительности разработанного устройства, состав АПК (рис. 5) входят макет СВУФПИ на базе платы ML405SXVideo, включающи ПЭВМ Dell Latitude М4310, две видеокамеры Logitech 9000, фотоаппарат Canon 50 видеокамера из состава модуля ML405SXVideo.

Внешний вид АПК представлен на рис. 6. Макет СВУФПИ, реализованный на 6¡ •> ПЛИС-модуля ML405SXVideo, соединенный по специальному интерфейсу видеокамерой, был подключен к ПЭВМ. ПЭВМ выполняла функции ЦСП, остальн блоки устройства были реализованы на ПЛИС в соответствии со схемой, изображенной рис. 5. С видеокамер или с фотоаппарата получали изображения при их различны положениях, которые поступали в макет СВУФПИ и далее модуль совместно с ПЭВ синтезировал панорамное изображение.

ВК2 Logitech 9000

ВК из состава модуля ML405 SX VIDEO

Штатив

ВК1 Logitech 9000

Canon 50D

ПЛИС-модуль

ML405SXVideo

ПЭВМ Dell Latitude

Е4310

USB

USB

USB

us в

Модуль питания 5В, 10А

Рис. 5. Схема АПК

Рис. 6. Внешний вид АПК

Для проведения экспериментальных исследований устройства формирования панорамных изображений было разработано специальное программное обеспечение на языке С++ (среда разработки Microsoft Visual Studio 2010), реализующее функции ЦСП устройства формирования панорамных изображений, и специальное программное обеспечение для ПЛИС в среде САПР «ICE 8.2» с использованием языка VHDL. Взаимодействие с вычислительной платформой ML405SXVideo обеспечивалось по порту USB с использованием стандартных программных библиотек.

Методика эксперимента заключалась в:

- установке видеокамер и фотоаппарата на поворотном штативе;

- ориентации и смещении видеокамер и фотоаппарата в определенные положения,

- получении наборов тестовых изображений;

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

- оценке характеристик устройства по результатам формирования.

Эксперимент был проведен в два этапа, первый из которых проводился для оценки

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

- выявления соответствий на основе расчета евклидова расстояния между всеми особыми точками двух изображений и сравнения с пороговым значением (использует similarity-threshold-based matching стратегию);

- выявления соответствий на основе расчета евклидова расстояния между всеми особыми точками двух изображений и выбора наиболее похожих, т.е. имеющих расстояние, в два раза меньшее, чем расстояния до всех остальных особых точек (использует the nearest-neighbour-ratio matching стратегию). В данном методе учитывается знак лапласиана и этот метод используется для сравнения SURF (Speed-Up Robust Features) дескрипторов.

Сравнение производилось на основе методики оценки точности сопоставления, используемой авторами Ке, Sukthankar, Mikolajczyk и Schmid в их работах. В зависимости от общего количества выявленных и ложных соответствий вычисляют значения 1-precision по следующей формуле:

количество ложных соответсвий

1 - precision --. (6)

общее количество выявленных соответствий

Входными данными для первого этапа были три набора (рис. 7) по 50 nai изображений размером 640x480 в каждом наборе.

Набор 1. Искусственные изображения. Пары пересекающихся изображений бы;и вырезаны из изображений, полученных с размещенного на штативе и вращаемого ( различных направлениях фотоаппарата Canon 50D, таким образом, чтобы имег пересечения. Количество особых точек в каждом изображении этого набора от 50 до 200. 1 Набор 2. Реальные изображения. Пары изображений были получены с каме| Logitech 9000, которые были размещены таким образом, чтобы с них можно было получат пересекающиеся изображения сцены. Количество особых точек небольшое от 50 до 200.

Набор 3. Реальные изображения. Пары изображений (снимков поверхности Зем.т со спутника) были заранее подготовлены и хранились в памяти ПЭВМ. Характсризуютс большим количеством особых точек - от 200 до 700.

Набор 1

Набор 2

Набор 3

Рис. 7. Примеры исходных данных для проведения эксперимента и результирующи-панорамных изображений I

На рис. 8 представлены усредненные значения точности алгоритмов, рассчитанныс| результате проведения первого этапаэкспсримета.

0,8000 0,6000 о.адоо 0,2000 0,0000

■ Алгоритм "similarity-threshold-

based matching"

з Алгоритм "the nearest-neighbour-ratio matching"

• Разработанный алгоритм

Набор 1

Набор 2

Набор 3

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

СВУФПИ с существующими устройствами. В качестве аналогов рассматривались ПЭВМ Dell М1530 и ПЭВМ Intel Core Quad, реализующие разработанный метод и метод, основанный на SURF. Для оценки времени работы метода формирования панорамных изображений, основанного на применении SURF, была использована программа, свободно распространяемая авторами метода (http://www.vision.ee.ethz.ch/~surf7). Показатели производительности разработанного устройства, полученные в ходе исследования, представлены в таблицах 1 и 2.

Таблица 1. Производительность устройств в зависимости от размера входных изображений____

Производительность, пан.изображение/сек ПЭВМ Dell М1530 ПЭВМ Intel Core Quad Разработанное устройство, N=1

Размер входных изображений Метод, основанный на SURF Разработанный метод Метод, основанный на SURF Разработанный метод Разработанный метод

320x240 7,69 8,06 8,85 9,43 15,87

640x480 3,52 3,60 3,88 3,95 9,35

800x600 2,24 2,29 2,50 2,54 5,62

1600x1100 0,83 0,84 0,91 0,92 2,15

3200x2400 0,38 0,38 0,42 0.43 1.06

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

ПЭВМ Dell M1530 ПЭВМ Intel Core Quad Разработанное устройство, N=1

Производительность, пан.изображение/сек Метод, основанный на SURF Разработанный метод Метод, основанный на SURF Разработанный метод Разработанный метод

50 - 200 особенностей 3,39 3,46 3,65 3,72 9,43

200 - 700 особенностей 1,52 1,54 1,74 1,75 3,86

Данные, представленные в таблице 1 и таблице 2, позволяют сделать вывод, что производительность разработанного вычислительного устройства с одним блоком выявления и анализа особенностей (N=1) выше, чем производительность аналогов в 2,33 раза. Дальнейшее повышение производительности СВУФПИ достигается за счет увеличения количества параллельных блоков.

Для оценки производительности разработанного устройства в зависимости от количества параллельных блоков были получены 50 пар изображений размером 3200x2400, из них были сформированы панорамные изображения разработанным СВУФПИ с различным количеством N = 1, 2, 4, 8, 16 параллельных блоков выявления и анализа особых точек. Зависимость производительности от количества параллельных блоков в СВУФПИ представлена в виде гистограммы на рис. 9.__

3,00 А* I 1 2,00

fi 1,00 ЯШ

g s Я i 0,00 s S â

1 2 4 S 16 N

с Количество параллельных блоков выделения и анализа особых точек

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

анализа особенностей вместо одного позволяет увеличить производительность СВУФПИ 2,25 раза. Дальнейшее увеличение количества блоков не приводит к значительном} увеличению производительности. Таким образом, производительность разработанно устройства выше производительности аналогов в 5,58 раза.

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

В заключении сформулированы основные результаты диссертации.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

При решении поставленной в диссертационной работе задачи были получег следующие основные результаты:

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

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

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

4. В процессе экспериментальных исследований подтверждена адекватное разработанной математической модели специализированного вычислительного устройся формирования панорамных изображений, проведен анализ полученных результате который показал, что разработанное устройство характеризуется повышенной точность сопоставления особенностей и производительностью, которая увеличена в 5,58 раз I сравнению с существующими аналогами. Разработанное СВУФПИ, обладающее высокш качественными и эксплуатационными показателями, обеспечивающее ускорение научв технического прогресса является основой для разработки класса специализировать вычислительных устройств формирования панорамных изображений, применение которь возможно в различных системах, и имеет важное народно-хозяйственное значение.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ по Перечню ВАК

1. Бугаенко, Е.И. Метод автоматического формирования панорамных изображений на основе аппарата нечеткой логики [Текст] / Е.И. Бугаенко, В.Н. Гридин // Известия вузов. Приборостроение. - 2009. - Т. 52, №2. - С. 7 - II.

2. Бугаенко, Е.И. Способ автоматического определения и коррекции радиальной дисторсии на цифровых изображениях [Текст] / Е.И. Бугаенко, М.И. Труфанов // Известия вузов. Приборостроение. - 2008. - Т. 51, №2. - С. 16-21.

3. Бугаенко, Е.И. Коррекция искажений изображения, вызванных яркими объектами в кадре и монохроматическими аберрациями [Текст] / М.И. Труфанов [и др.] // Известия Тульского государственного университета. Сер. Вычислительная техника. Информационные технологии. Системы управления. - 2006. - вып.1,- С. 47 - 50.

Монографии

4. Бугаенко, Е.И. Разделы 3.5. Повышение качества изображения при формировании панорамных изображений, 3.1.1. Определение дисторсии по единственному изображению [Текст] / Гридин В.Н., Титов B.C., Труфанов М.И. // Монография «Адаптивные системы технического зрения», Центр информационных технологий в проектировании РАН. ISBN 978-5-02-025391-9. М.: Наука, 2009. - 441с.: ил. - С. 114128,160-168.

5. Бугаенко, Е.И. Параграф 2.2.4. Калибровка радиальной дисторсии по единственному кадру изображения [Текст] / Титов B.C., Тевс С.С., Труфанов М.И. // Монография «Оптико-электронные системы распознавания и анализа трехмерных динамических объектов», Курск: Курск, гос. тех. ун-т., 2008. - 142 е.: ил. - С. 44-52.

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

6. Bugaenko, Е. Creation of panoramic images with use of fuzzy logic [Text] / V. Titov // Proceeding of 9th international conference «Pattern recognition and image analysis: new information technologies" (PRIA-9-2008). Vol. 1. - Nizhni Novgorod, 2008 - P. 63 - 65.

7. Bugaenko, E. Creating panoramic images with radial distortion correction [Text] / V. Titov // Proceeding of Sixth International Conference "Information and telecommunication technologies in intelligent systems". Crete, Greece, 2008. - P. 89 - 92.

8. Bugaenko, E. Radial distortion calibration method and device for images input on its base [Text] / D. Titov, M. Truphanov // Proceeding of 8th international conference Pattern recognition and image analysis: new information technologies. Vol. 2. - Yoshkar-Ola, 2007.-P. 181-184.

Патенты

9. Пат. №2365998, МПК G06T9/00. Способ формирования панорамных изображений [Текст] / Е.И. Бугаенко, М.И. Труфанов, П.А.Сорокин - №2006144943; заявл. 18.12.2006; опубл. 27.08.09, Бюл. № 24. -14 с.

10. Пат. №2351091РФ, МКИ H04N3/23, G06T5/40. Способ автоматического определения и коррекции радиальной дисторсии на цифровом изображении [Текст] / Е.И. Бугаенко, М.И. Труфанов. - №2006142839; заявл. 4.12.2006; опубл. 27.03.09, Бюл. № 9. -13 с.

11. Пат. №2346326РФ, МКИ G06M11/02. Способ калибровки радиальной дисгорс оптической подсистемы системы технического зрения [Текст] / Е.И. Бугаенко, В. Титов, М.И. Труфанов. - №2007107774; заявл. 1.03.2007; опубл. 10.02.09, Бюл. № -12 с.

Материалы и тезисы докладов, опубликованные в трудах Всероссийских и Международных конференций

12. Бугаенко, Е.И. Формирование панорамных изображений на основе поиск особенностей на изображении [Текст] / О.Б. Тарасова, C.B. Кузнецов // С материалов 9-й Межд. конф. Распознавание-2010. Курск: ЮЗГУ. - 2010. - С. 71 - 73

13.Бугаенко, Е.И. Способ формирования панорамных изображений [Текст] Е. И. Бугаенко // Всероссийская научно-техническая конф. «Интеллектуальные информационные системы - 2009». - Тула, 2009. - С. 120-121.

Н.Бугаенко, Е.И. Способ получения панорамных изображений с авгоматическо коррекцией радиальной дисторсии [Текст] / М.И. Труфанов // Материалы докладо всероссийской научно-технической конференции студентов, аспирантов и молоды ученых «Научная сессия ТУСУР - 2007». Часть 4. Сек. Информационн измерительные приборы и устройства. - Томск, 2007. - С. 14-15.

15.Бугаенко, Е.И. Подходы к формированию панорамных изображений [Текст] / М. Труфанов // Материалы международной научно-технической конференци «Диагностика - 2009». - Курск, 2009. - С. 145-147.

Соискатель /VМ Бугаенко Е.И.

ид №06430 от ш&ш Подписано к печати 2-3.05 .2.0 ¿-V. Формат 60x84 1/16. Печатных листов 1.0 Тираж 100 экз. Заказ ?М Юго-Западный государственный университет.

Издательско-полиграфический центр Юго-Западного государственного университета. 305040, г. Курск, ул. 50 лет Октября, 94.

ВВЕДЕНИЕ

1 АНАЛИЗ МЕТОДОВ И УСТРОЙСТВ ФОРМИРОВАНИЯ ПАНОРАМНЫХ ИЗОБРАЖЕНИЙ

1.1 Развитие методов и устройств формирования панорамных изображений

1.2 Наиболее распространенные подходы к формированию панорамных изображений

1.2.1 Методы поиска и описания особенностей на изображениях

1.2.2 Методы сопоставления и выявления наиболее схожих особенностей на основе дескрипторов

1.2.3 Сравнение известных методов выявления, описания и сопоставления особых точек

1.2.3.1 Сравнительный аналнз методов выявления особых точек на изображениях

1.2.3.2 Сравнительный анализ методов создания дескрипторов

1.2.3.3 Анализ методов сопоставления особых точек

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

2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ СПЕЦИАЛИЗИРОВАННОГО ВЫЧИСЛИТЕЛЬНОГО УСТРОЙСТВА ФОРМИРОВАНИЯ ПАНОРАМНЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ МЕТРИЧЕСКИХ ДЕРЕВЬЕВ

2.1 Модель ввода изображения рабочей сцены

2.2 Модель определения коэффициента радиальной дисторсии 43 2.2.1 Определение коэффициента радиальной дисторсии по одиночным линиям

2.2.2 Определение коэффициента радиальной дисторсии на основе трех изображений

2.3 Модель коррекции радиальной дисторсии

2.4 Модель выделения особых точек на изображениях

2.4.1 Создание карт откликов на основе расчета определителей матрицы Гессе

2.4.2 Использование пирамид изображений

2.4.3 Выявление особых точек на основе поиска максимумов определителей матрицы Гессе на картах откликов

2.4.4 Использование интегральных изображений

2.4.5 Использование квадратичной интерполяции для определения значения максимумов определителей

2.5 Модель создания дескрипторов особых точек 66 2.5.1 Формирование дескрипторов особых точек

2.5.1.1 Определение ориентации окрестности особой точки

2.5.1.2 Вычисление сумм откликов вейвлета Хаара

2.6 Модель построения метрических деревьев

2.6.1 Структура метрического дерева для хранения дескрипторов особых точек

2.6.2 Добавление объекта в метрическое дерево

2.7 Модель сопоставления особых точек

2.8 Модель расчета матрицы преобразования

2.8.1 Модель вычисления матрицы преобразования на плоскости

2.8.2 Модель расчета матрицы преобразования в пространстве

2.9 Модель соединения исходных изображений

2.9.1 Модель преобразования второго изображения

2.9.2 Модель соединения изображений 84 3 АНАЛИЗ ХАРАКТЕРИСТИК И РАЗРАБОТКА СПЕЦИАЛИЗИРОВАННОГО ВЫЧИСЛИТЕЛЬНОГО

УСТРОЙСТВА ФОРМИРОВАНИЯ ПАНОРАМНЫХ ИЗОБРАЖЕНИЙ

3.1 Метод формирования панорамных изображений

3.2 Алгоритм формирования панорамных изображений

3.2.1 Алгоритмы определения коэффициента радиальной дисторсии

3.2.2 Алгоритм коррекции радиальной дисторсии

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

3.2.4 Алгоритм создания дескрипторов для особых точек и нахождения соответствующих точек на двух изображениях

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

3.3.1 Структурно-функциональная организация и описание принципов работы устро йства

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

3.4 Анализ времени формирования панорамных изображений

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

4 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ СПЕЦИАЛИЗИРОВАННОГО ВЫЧИСЛИТЕЛЬНОГО УСТРОЙСТВА ФОРМИРОВАНИЯ ПАНОРАМНЫХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ МЕТРИЧЕСКИХ ДЕРЕВЬЕВ

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

4.2 Методика проведения испытаний разработанного устройства

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

4.2.2 Методика проведения экспериментальных исследований производительности разработанного устройства

4.3 Экспериментальная оценка точностных характеристик разработанного устройства

4.4 Оценка производительности разработанного устройства 135 ЗАКЛЮЧЕНИЕ 138 БИБЛИОГРАФИЧЕСКИЙ СПИСОК

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

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

В настоящее время достигнут значительный прогресс в решении указанной задачи, и- наибольший, вклад в, развитие методов и устройств формирования панорамных изображений, а также методов выделения, описания и сопоставления особенностей изображений, как наиболее важных этапов обработки изображений, внесли С. Harris, M. Brown, H. Moravec, M. Stephens, J. Shi, C. Tomasi, H. Wang, M. Brady, R.I. Hartley, A. Zisserman, P. Torr, A. Zisserman, B. Triggs, R. Szeliski, M. Irani, R. Radke, P. Ramadge, T. Echigo, S. Iisaku, T. Lindeberg, К. Mikolajczyk, С. Schmid, J. Matas, О. Chum, M. Urban, T. Pajdla, D. Capel, D. Lowe, H. Bay, T. Tuytelaars, L. Van Gool, Сойфер В.A., Потапов A. A., Пахомов A. A., Никитин С. A., Гуляев Ю. В., Фурман Я.А. Существенные результаты в данной области получены в отечественных работах, выполненных в Институте прикладной математики РАН, Московском государственном университете, Московском физико-техническом институте и в других организациях. Однако большинство из известных методов и устройств имеют существенные недостатки, такие как низкая производительность, являющаяся следствием большой вычислительной сложности алгоритмов, и низкая точность результирующих изображений, обусловленная наличием случайных искажений различной природы на исходных изображениях. Кроме того, не в полной мере решена задача сопоставления объектов изображений, имеющих схожие характеристики, что также обуславливает понижение точности панорамных изображений.

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

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

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

Для достижения поставленной цели требуется решение следующих задач:

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

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

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

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

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

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

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

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

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

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

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

На защиту выносятся следующие положения:

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

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

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

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на Международных и Российских конференциях: Всероссийская конференция по проблемам информатики, физики и химии (г. Москва РУДН 2005 г.); Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации «Распознавание 2005, 2008, 2010» (г. Курск, Курский государственный технический университет 2005, 2008, 2010 гг.); «Молодежь и XXI век: 2005, 2006, 2007» (г. Курск, Курский государственный технический университет, 2005, 2006, 2007 гг.), Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых «Научная сессия ТУСУР - 2007» (г. Томск, 2007 г.), Международная научно-техническая конференция «Медико-экологические технологии-2007» (г. Курск, Курский государственный технический университет, 2007 г.), Международная конференция «Распознание образов и анализ изображений: новые информационные технологии» (г. Йошкар-Ола, 2007 г.), Международная научно-техническая конференция «Диагностика -2009» (г. Курск, Курский государственный технический университет, 2009 г.), а также на научно-технических семинарах кафедры вычислительной техники с 2005 по 2011 годы.

Публикации. Основные результаты выполненных исследований и разработок опубликованы в 15 печатных работах, в том числе в 3 статьях. Среди них: 3 статьи, опубликованные в рецензируемых научных журналах, входящих в перечень журналов и изданий, рекомендуемых ВАК РФ, а также 3 патента Российской Федерации.

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

Результаты работы СВУФПИ в ходе всех частей эксперимента проанализировать.

4.3 Экспериментальная оценка точностных характеристик разработанного устройства

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

119 1

На изображении И1 выделено А^с1=271 особая точка, в таблице 4.1 представлены первые 10 из них:

1. Пат. №1299850 Европейский, МКИ G 06 Т 7/00, G 06 Т 3/00. Merging images to form a panoramic image Text. / Peterson, John №20010931133; заявлено 10.04.2001; опубл. 12.03.2008-5 с.

2. Пат. №1850583 Европейский, МКИ Н 04 N 5/232. Method of photographing panoramic image Text. / Park, Kyoung-Ju, Cho, Sung-Dae, Jeong, Young-Min -№20070106836; заявлено 24.04.2007; опубл. 31.10.2007 7 с.

3. Пат. №7095905 США, МКИ G 06 К 9/36; Н 04 N 7/00. Merging images to form a panoramic image Text. / Peterson, John №09/657949; заявлено 08.09.2000; опубл. 22.08.2006 - 5 с.

4. Пат. №20070159527 США, МКИ Н 04 N 5/253. Method and apparatus for providing panoramic view with geometric correction Text. / Kim, Keun Ho -№11/581401; заявлено 17.10.2006; опубл. 12.07.2007 5 с.

5. Шишкин, Е. В. Компьютерная графика Текст. / Е. В. Шишкин, А. В. Боресков // М.: Диалог-МИФИ, 1995. 288 с.

6. Блинова, Т.А. Компьютерная графика Текст. / Т.А. Блинова, В.Н. Пореев // Киев : Век+, 2006. 520 с.

7. Пат. 2007/122584 Wipo, МКИ G 06 Т 3/40. Method and device for generating a panoramic image from a video sequence Text. / Auberger, Stephane № 2007/051479; заявлено 23.04.2007; опубл. 01.11.2007 - 9 с.

8. Henricsson, О. Analysis of Image Structures using Color Attributes and Similarity Relations Text., PhD Thesis No. 11663, Swiss Federal Institute of Technology. 1996. - 140 p.

9. Jahne, B. Principles of filter design. Handbook of Computer Vision and Applications Text. / B. Jahne, H.Scharr, S.Korkel // Academic Press. 1999.

10. Canny, J. A Computational Approach to Edge Detection Text. // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1986. - Vol. 8, No. 6.-P. 679-714.

11. Deriche, R. Using Canny's criteria to derive a recursively implemented optimal edge detector Text. // Int. J. Computer Vision. 1987. - Vol. 1. - P. 167-187.

12. Lindeberg T. Discrete Derivative Approximations with Scale-Space Properties: A Basis for Low-Level Feature Extraction Text. // J. of Mathematical Imaging and Vision, 3(4). 1993. - P. 349-376.

13. Harris, C. A combined corner and edge detector Text. / C. Harris, M. Stephens // In Fourth Alvey Vision Conference. Manchester, UK, 1988. - P. 147-151.

14. Lowe, D.G. Object recognition from local scale-invariant features Text. // In Proceedings of the 7th International Conference on Computer Vision. Kerkyra, Greece, 1999.-P. 1150-1157.

15. Bay, H. SURF: Speeded up robust features Text. / H. Bay, T. Tuytelaars, L. Van Gool // In ECCV. 2006. - 14 p.

16. Lindeberg, T. Feature Detection with Automatic Scale Selection Text. // International Journal of Computer Vision. V.30, N.2, 1998. - P. 79-116.

17. Matas, J. Robust wide baseline stereo from maximally stable extremal regions Text. / J. Matas, O. Chum, M. Urban, T. Pajdla / Image Vision Comput. 2004. -P. 761-767.

18. Hartley, R. I. Multiple View Geometry in Computer Vision Text. / R. I. Hartley, A. Zisserman // Cambridge University Press, ISBN: 0521540518, second1 edition .- 2004. 672 p.

19. Burt, Peter J. A multiresolution spline with application to .image mosaics Text. / Peter J. Burt, Edward H. Adelson // ACM Transactions on Graphics 2(4). 1983. -P. 217-361.

20. Moravec, H. Towards automatic visual obstacle avoidance Text. // Proc. of the 5th Intern. Joint Conf. of Artificial Intelligence. Cambridge, 1977. - P. 587-598.

21. Schmid, C. Evaluation of interest point detectors Text. / C.Schmid, R.Mohr, C.Bauckhage // International Journal of Computer Vision. -Vol.37, No.2. 2000. -P.151-172.

22. Rockett, P. Performance assessment of feature detection algorithms: A methodology and case study on corner detectors Text. // IEEE Transactions on Image Processing. Vol.12, No. 12. - 2003. - P.1668-1676.

23. Beaudet, P. R. Rotationally Invariant Image Operators Text. // International Joint Conference on Pattern Recognition. 1987. - P. 579-583.

24. Kitchen, L. Grey-level Corner Detection Text. / Kitchen, L, A. Rosenfeld // Pattern Recognition Letters. 1982. - P. 95-102.

25. Cottier, J.C. Extraction et appariements robustes des points d'int'er'et de deux images non 'etalonn'ees Text. // Technical Report, LIFIA-IMAG-INRIA RITone-Alpes. 1994. - 140 p.

26. Horaud, R. Finding geometric and relational structures in an image Text. / Horaud, R., Skordas, T., Veillon, F. // In Proceedings of the 1st European Conference on Computer Vision, Antibes, France. 1990. - P. 374-384.

27. Heitger, F. Simulation of neural contour mechanism: From simple to end-stopped cells Text. / Rosenthaler L., von der Heydt R., Peterhans E., Kuebler O. // Vision Research, vol. 32(5). 1992. - P. 963-981.

28. Fostner, W. A framework for low level feature extraction Text. / Fostner W. // 3rd European Conference on Computer Vision. Stockholm, Sweden, 1994. - P. 383-394.

29. Paler, K. Local orderedgrey-levelsasanaid to corner detection Text. / K.Paler, J.F'oglein, J.Illingworth, J.Kittler // Pattern Recognition. Vol.17, No.5, 1984. -P. 535-543.

30. William, T. Freeman, Edward H. Adelson. The design and use of steerable filters Text. / William, T. Freeman and Edward H. Adelson // PAMI, 13(9). -1991. -P.891 -906.

31. Florack, L. M. J. General intensity transformations and differential invariants Text. / L. M. J. Florack, B. M. ter Haar Romeny, J. J. Koenderink, and M. A. Viergever // JMIV, 4(2). 1994. - P. 171-187.

32. Baumberg, A. Reliable feature matching across widely separated views Text. // In CVPR. 2000. - P. 774 - 781.

33. Carneiro G. Multi-scale phasebased local features Text. / G. Carneiro and A.D. Jepson // In CVPR (1). 2003. - P. 736 - 743.

34. Lowe, D. Distinctive image features from scale-invariant keypoints, cascade filtering approach Text. // IJCV, 60(2). -2004. P. 91 - 110.

35. Ke, Y. PCA-SIFT: A more distinctive representation for local image descriptors Text. / Y. Ke and R. Sukthankar // In CVPR (2). 2004. - P. 506-513.

36. Mikolajczyk, K. A performance evaluation of local descriptors Text. / K. Mikolajczyk and C. Schmid//PAMI, 27(10). -2005. P. 1615-1630.

37. Se, S. Vision based modeling and localization for planetary exploration rovers Text. / S. Se, H.K. Ng, P. Jasiobedzki, T.J. Moyung // Proceedings of International Astronautical Congress. 2004. - P. 356-401.

38. Mikolajczyk, K. A performance evaluation of local descriptors Text. / K. Mikolajczyk, C. Schmid // In: CVPR. Vol. 2. - 2003. - P. 257 - 263.

39. Beis J.S. Shape indexing using approximate nearest-neighbor search in high-dimensional spaces Text. / J.S. Beis, D.G. Lowe // In Proc. IEEE Conf. Сотр. Vision Patt. Recog. 1997. - P. 1000-1006.

40. Bay, H. SURF: Speeded Up Robust Features Text. / H. Bay, A. Ess, T. Tuytelaars, L. V. Gool // Computer Vision and Image Understanding (CVIU). -Vol. 110,No. 3.-2008.-P. 346-359.

41. Mikolajczyk, K. A comparison of affine region detectors Text. / Mikolajczyk, K., Tuytelaars, Т., Schmid, C., Zisserman, A., Matas, J., Schaffalitzky, F., Kadir, Т., Van Gool, L. // IJCV 65. 2005. - P. 43-72.

42. Mikolajczyk, K. Scale and affine invariant interest point detectors Text. / K. Mikolajczyk, C. Schmid // IJCV 60. 2004. - P. 63 - 86.

43. Кудряшов, А.П. Извлечение и сопоставление точечных особенностей Текст. // Электронный журнал "Исследовано в России", 2007, С. 1095-1104.

44. Методы компьютерной обработки изображений Текст. / Под ред. В.А. Сойфера. -М.: Физматлит. 2001. - 784 с.

45. Новейшие методы обработки изображений: монография / под ред. А.А. Потапова; М.: ФИЗМАТЛИТ, 2008. 496 с.143

46. Демидович, Б. П. Основы вычислительной математики Текст. / Б. П. Демидович, И. А. Марон // М.: Наука, Гл. ред. физ.-мат. лит. - 1966.

47. Дегтярев, С.В. Методы цифровой обработки изображений Текст.: учебное пособие 4.1. Гриф УМО / Дегтярев С.В., Садыков С.С., Тевс С.С.,

48. Ширабакина Т.А. Курск: Курск, гос. тех. ун-т., 2001. - 167 с.

49. Бронштейн, И.Н. Справочник по математике Текст. / И.Н.Бронштейн, К.А.Семендяев // Издание седьмое, стереотипное. М.: Гос. изд-во технико-теоретической лит-ры. -1957. 138 с.

50. Красильников Н.Н. Цифровая обработка 2-D и 3-D изображений: учебное пособие / Красильников Н.Н. СПб.: БХВ-Петербург, 2011. - 608 с.

51. Быков Р.Е. Основы телевидения и видеотехники: учебное пособие / Быков Р.Е. М.: Горячая линия - Телеком, 2006. - 399 с.

52. Burt, P. The Laplacian Pyramid as a Compact Image Code Text. / Burt P., Adelson E. // IEEE Transactions on Communications. 1983. - Vol. Com-31, No. 4. - P. 532-540.

53. Lindeberg, T. Real-time scale selection in hybrid multi-scale representations Text. / Lindeberg Т., Bretzner L. // Scale-Space. 2003. -Ch. 2.4. - P. 148-163.

54. Brown, M. Invariant features from interest point groups Text. / Brown M., Lowe D. // BMVC. 2002. - P. 656-665.

55. Viola, P. Robust real-time object detection Text. / Viola P., Jones M. // IEEE ICCV Workshop on Statistical and Computational Theories of Vision. 2001. -P.123 - 145.

56. Grabner, M. Fast approximated sift Text. / Grabner M., Grabner H., Bischof H.//ACCV.-2006.-Vol. 1.-P. 918-927.

57. Venkateswaran, J. A Survey of Recent Multidimensional Access Methods Text. / Venkateswaran J. // Technical Report, University of Missouri-Rolla. -2004. 162 p.

58. Gaede, V. Multidimensional access methods Text. / Gaede V., Gunther O. // ACM Computing Surveys (CSUR). 1998. - Vol. 30, n. 2. - P. 170-231.

59. Ciaccia, P. M-tree: an efficient Access Method for Similarity Search in Metric Spaces Text. / Ciaccia P., Patella M., Zezula P. // Proc. of the 23rd Conference on Very Large Databases (VLDB'97). 1997. - P. 426—435.

60. Longuet-Higgins, H. A computer algorithm for reconstructing a scene from two projections Text. / Longuet-Higgins H. // Nature. 1981. - Ch. 6.2-6.3. - P. 133-135.

61. Бугаенко, Е.И. Способ автоматического определения и коррекции радиальной дисторсии на цифровых изображениях Текст. . / Е.И. Бугаенко, М.И. Труфанов // Известия вузов. Приборостроение. 2008. - Т. 51,,№2. - С. -16-21.

62. Алтунин, A.E. Модели и алгоритмы принятия решений в нечетких условиях Текст. / А.Е. Алтунин, М.В. Семухин // Монография. Тюмень: Издательство Тюменского государственного университета 2000.

63. Оптико-электронные системы распознавания и анализа трехмерных динамических объектов: монография / под ред. B.C. Титова, С.С. Тевса, М.И. Труфанова; Курск, гос. техн. ун-т. Курск, 2008. 142 с. (Параграф 2.2.4, С. 4452).

64. Адаптивные системы технического зрения: монография / под ред. В.Н. Гридина, B.C. Титова, М.И. Труфанова; Центр информационных технологий145в проектировании РАН. Москва, 2009. 441 с. (Разделы 3.5., 3.1.1, С. 114-128, 160-168).

65. Бугаенко, Е.И. Подходы к формированию панорамных изображений Текст. / М.И. Труфанов, Е.И. Бугаенко // Материалы международной научно-технической конференции «Диагностика 2009». — Курск, 2009. — С. 145-147.

66. Бугаенко, Е.И. Метод автоматического формирования панорамных изображений на основе аппарата нечеткой логики Текст. / Е.И. Бугаенко, В.Н. Гридин // Известия вузов. Приборостроение. 2009. — Т. 52, №2. - С. 7

67. Пат. №2365998 Российская Федерация, МПК G06T9/00. Способ формирования панорамных изображений Текст. / Бугаенко Е.И., Труфанов М.И., Сорокин П.А. №2006144943; заявл. 18.12.2006; опубл. 27.08.09, Бюл. № 24. - 14 с.

68. Бугаенко, Е.И. Формирование панорамных изображений на основе поиска особенностей на изображении Текст. / О.Б. Тарасова, С.В. Кузнецов, Е.И.

69. Бугаенко // Сб. матер. 9-й Междунар. конф. «Распознавание-2010». Курск; 2010.-С. 71-73.

70. Савиных, В.П. Аэрокосмическая фотосъемка: учебник / В. П. Савиных,

71. A.C. Кучко, А.Ф. Стеценко. М.: «Картогеоцентр» - «Геодезиздат», 1997. -378 с.

72. Злобин, В.К. Обработка аэрокосмических изображений: монография /

73. B.К. Злобин, В.В. Еремеев; М.: ФИЗМАТЛИТ, 2006. 288 с.

74. Угрюмов, Е.П. Проектирование элементов и узлов ЭВМ // Учеб. пособие для вузов. М.: Высшая школа. — 1987. — 320 с.