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

На правах рукописи

005005586

ПОТАПОВ Михаил Александрович

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

Специальность: 05.13.18 - Математическое моделирование,

численные методы и комплексы программ

- 8 ДЕК 2011

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

Ульяновск-2011

005005586

Работа выполнена на кафедре «Системы автоматизированного проектирования» Ульяновского государственного технического университета.

Научный руководитель: доктор технических наук, профессор

Крашенинников Виктор Ростиславович

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

Бутов Александр Александрович

кандидат технических наук, доцент Дементьев Виталий Евгеньевич

Ведущая организация:

Новосибирский государственный технический университет

Защита состоится 28. декабря 2011г. в 15 часов на заседании диссертационного совета Д 212.277.02 при Ульяновском государственном техническом университете по адресу: 432027, Ульяновск, ул. Северный Венец, 32, аудитория 211 (главный корпус).

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

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

Ученый секретарь диссертационного совета, д.т.н., профессор

Крашенинников В.Р.

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

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

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

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

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

В настоящее время существует множество методов и алгоритмов оценивания параметров ГТ, однако они требуют неприемлемых вычислительных затрат при больших значениях параметров ГТ. Например, в корреляционно-экстремальных алгоритмах для достижения высокой точности требуется производить пробные совмещения при большом количестве комбинаций значений параметров ГТ. Псевдо1радиентные алгоритмы дают высокоточные оценки параметров при небольших вычислительных затратах, но их существенным недостатком является небольшая рабочая зона, то есть требуется иметь достаточно точные начальные приближения значений параметров ГТ, при которых эти алгоритмы работоспособны. Поэтому при возможных больших значениях параметров приходится применять эти алгоритмы многократно для множества возможных начальных приближений, что также ведёт к большим вычислительным затратам. Из сказанного следует, что было бы весьма полезно иметь алгоритмы, которые при небольших вычислительных затратах обладают большой рабочей зоной и дают оценки параметров ГТ, которые можно использовать в качестве начальных приближений для высокоточных алгоритмов.

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

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

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

1. Построение алгоритмов оценки параметров ГТ изображений на основе метода неподвижной точки оператора ГТ.

2. Исследование математических моделей ГТ изображений и нахождение их неподвижных точек.

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

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

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

6. Разработка комплекса программ, реализующего предложенные алгоритмы.

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

Научная новизна положений, выносимых на защиту

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

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

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

4. Разработан комплекс прикладных программ для совмещения изображений со значительными ГТ.

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

Реализация результатов работы. Результаты диссертационной работы использованы при выполнении госбюджетной НИР УлГТУ, гранта РФФИ а09-08-00725 и в учебном процессе УлГТУ в дисциплине «Основы теории обработки изображений», что подтверждено соответствующим актом.

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

Апробация работы. Основные результаты работы докладывались на VI и VII Всероссийских с участием стран СНГ научно-практических конференциях «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 2009 и 2011); LXIV и LXV научных сессиях Российского научно-технического общества радиотехники, электроники и связи им. А.С.Попова, посвященных Дню радио (Москва, 2009 и 2010); 10-й Международной научно-технической конференции PRIA-2010 «Распознавание образов и анализ изображений: новые информационные технологии» (Санкт-Петербург, 2010) и ежегодных конференциях профессорско-преподавательского состава Ульяновского государственного технического университета (2008-2011 гг.).

Публикации. По теме диссертации опубликовано 8 статей, из них 2 опубликованы в изданиях из перечня ВАК и 6 в трудах научных конференций.

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

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

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

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

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

Пусть / - отображение множества W в себя. Элемент w е W , для которого /(w) = w, называется неподвижной точкой отображения /.

Рассмотрим два изображения x(W) и y(J), заданные на целочисленных т - мерных сетках W = {w} = {(wl,...,wm)} и J = {j} = {(Jv—Jm)} ■ Пусть известен вид ГТ, связывающий координаты точек этих изображений:

w = F(j;ñ

где ¡5 - неизвестные параметры ГТ, подлежащие оценке. Выполнив вспомогательную трансформацию Р изображения О , получим изображение -г(У), связанное с х(Ж) сложным ГТ

Предположим, что Н имеет единственную неподвижную точку V, то есть

у=Н(у;/?). (1)

Если её удастся найти, то (1) после подстановки V превращается в систему т уравнений относительно параметров Р . Если количество параметров ГТ равно размерности изображений, то из системы (1) эти параметры определяются. Если ГТ имеет большее количество параметров, то можно выполнить К вспомогательных преобразований, найти их неподвижные точки и получить систему уравнений

Ук=Нк(ук-Пк = \,...,К, (2)

из которой находятся оценки всех параметров ГТ.

На рис. 1 иллюстрируется наличие неподвижной точки после вспомогательного преобразования. На рис. 1,а изображён смайл. При параллельном сдвиге этого изображения вправо смещается и этот смайл (рис. 1,6). Очевидно, что неподвижной точки при параллельном сдвиге нет. Выполним вспомогательную ГТ - разворот изображения 1,6 на угол Я (рис. 1,в). На рис. 1,г показано наложение рис. 1,в на рис. 1,а. Видно, что помеченная стрелкой точка на рис.1,г расположена одинаково на обоих смайлах, это и есть неподвижная точка преобразования рис. 1,а в рис. 1,в.

Рис. ]. Неподвижная точка сложного преобразования перенос-поворот

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

Пусть х(к,1) и у{1, /)- два двумерных изображения с известным видом ГТ (/, £), связывающей координаты точек этих изображений:

k = f(i,j;P), l = g(i,S\P),

где P - параметры, подлежащие оценке. Выполнив вспомогательное преобразование (p,q) изображения y(i,j), получим изображение z(i,j)t связанное с х(к,1) преобразованием

к = f(p(i,j),qQM) = HiW), I = 8(p(',j)M'jyJ) = G(i,rJ).(3)

Пусть преобразование (3) имеет единственную неподвижную точку (и, v):

u = F{u,v,p), v = G{u,v\P). (4)

Если эту неподвижную точку удастся найти (хотя бы приближенно), то (4) превращается в систему уравнений относительно параметров Р .

Если ГТ имеет только два параметра (например, при параллельном сдвиге или при изменении масштаба и повороте относительно известной точки), то из системы (4) эти параметры определяются. Если же ГТ имеет более двух параметров, то можно выполнить М вспомогательных преобразований, найти их неподвижные точки и получить систему уравнений

«* = Fk(uk,vk\P), vk =Gk(uk,vk;P), m = l,...,M,

из которой находятся оценки всех параметров ГТ. Эта система может быть решена аналитически только при простом сдвиге изображений. При более сложных ГТ её приходится решать численными методами.

Основная трудность применения описываемого подхода состоит в нахождении неподвижных точек. При отсутствии яркостных искажений значения изображений х(к,1) и z(i, j) в неподвижной точке (и, v) одинаковы, то есть

Но это условие не является достаточным, так как на изображении х(к,1) могут быть и другие точки со значением z(i, j), а неподвижная точка - только одна из них. Поэтому для каждого конкретного вида ГТ нужно подобрать свои вспомогательные преобразования и найти признаки неподвижности точки.

Оценка сдвига двумерных изображений при малых поворотах и изменениях масштаба. Рассмотрим следующий, часто встречающийся вид ГТ: поворот на угол а вокруг центра изображения, изменение масштаба от центра с коэффициентом s и пйрштлельньти сдвиг из. вектор (¿г. Для упрощения ВЫкладок расположим начало координат (U, (J) в центре сетки. Тогда преобразованием изображения y(i,j) в изображение х(к,1) будет

к = а + s(i cos а - j sin а), 1 = b + í(/sin а + j cos a). (5) Возьмем в качестве вспомогательного преобразования {p,q) поворот y{i, j) вокруг его центра на угол л, тогда система (5) принимает вид:

и - а - s(u cos a - vsin a), v = b - s(u sin a + v cos a). Она имеет единственное решение

и = [a(l +scosa) + bs sin a] /[(1 + s cos a)2 +(s sin a)2 ], v = [¿(1 + ä cos a)- as sin «]/[(1 + ¿'cos a)¿ + (s sin a)2. При a ~ 0, s ~ 1 из (6) получаем

a да 2и, b » 2v . (7)

Таким образом, найдя положение (u,v) неподвижной точки преобразования х(к,1) в z(i, j) ; мы получим оценки (7) параметров сдвига (а,Ь).

Для нахождении неподвижной точки рассмотрим изображение Д(/, J) =| z(z',j)-х(/, j) I. Значения изображений х(к,1) и z(i,j) в неподвижной точке (м, v) совпадают, поэтому А(м, v) = 0 . Но могут быть и другие точки, в которых А(/,_/') = 0 из-за случайного совпадения значений x(i,j) и z(i,j) . Пусть сначала в (5) а = 0 и J = l, тогда очевидно, что изображение A (i, j) переходит само в себя при повороте на угол я вокруг неподвижной точки. То есть A (i,j) имеет центральную симметрию относительно неподвижной точки (и, v). Поэтому e(u, v; т, rí) A(u + m,v+ri)-A(u-m,v-ri)\=0 при любых т ии. Однако, снова могут быть и другие точки, в которых s(i, j;m,n) = 0 при некоторых значениях т и п. Но таких точек обычно немного, если (i, j) не является неподвижной точкой. Поэтому для статистики

г г

E(ij) = X X E{i,j\m,n) (8)

т-0 п=-г

характерны малые значения, когда точка (/, j) находится вблизи неподвижной точки («, v), следовательно, за оценку координат неподвижной точки (и, v) можно принять координаты точки минимума {i, j) статистики (7).

в) г)

Рис. 2. Нахождение неподвижной точки при параллельном сдвиге изображений

Для иллюстрации этих выкладок приведен рис. 2. Байтовые спутниковые изображения облачности размеров 128x128 на рис. 2,а и рис. 2,6 имеют сдвиг (а,Ь) = (22,-38) без поворота и изменения масштаба. На рис. 2,в показано изображение A(i,j) : заметна его центральная симметрия относительно неподвижной точки (и,у) = (д/2,/>/2) = (22/2,~38/2) = (11,-19). На рис. 2,г показано изображение e(í, /'), при этом £(11,-19) = 0 , а остальные значения положительны.

Совмещение двумерных изображений при больших углах поворота и изменениях масштаба. Нахождение неподвижных точек. Если условия не выполняются, то изображение A(i,j) не будет иметь центральной симметрии. Для нахождения неподвижной точки применим к имеющемуся изображению y(i,j) вспомогательную IT

k = at +j,(/cosa1 -j'sina,), / = è, +í|(/sina, + Jcosa,), (9) где а,, b¡, s¡, а, - известные параметры. Эта ГТ есть параллельный сдвиг на вектор (я,, i, ), поворот па угол Ct\ вокруг точки (<з,, ¿», ) и масштабирование с

коэффициентом . Для различных значений этих параметров имеется соответствующая неподвижная точка, координаты (m,v) которой удовлетворяют системе уравнений

c(l-ssip)-dss}q ú?(1-ss{p) + css^q

U= (l-ss.pf+iss^' V~(l -ssip)2+{ss]q)2' (10)

где

c=a+s(a¡ cosa-Ь, sina), p-cos(pi + a,), d = b + s(ai sina + è, cosa), q = sin(a + a,).

Пусть параметры (a,, 6, ) в (9) изменяются, тогда соответствующая неподвижная точка будет перемещаться, описывая при этом некоторую траекторию. Математическая модель этой траектории зависит от того, как изменяются параметры в (9). Если, например, точки (a,, 6, ) движутся по прямой линии

aK(f) = m+nt, b¡(t) = g-ht, (11)

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

, , ,AB0-BB.S AU,-BU, „ „

и(0 = (—£-г-4f +-1-^ = Pt + D,

А + В А + В

, ч . АВ, + ВВ() АН, +ВНа „ „

v(0 = —-+--^ = Qt + E,

л + в А2+В2

где

А = 1 - ss¡p, В = ssxq, В0 = s(n eos а + h sin а ), Вх - s(n sin а - h eos a ), #0 = a + s(m eos a - g sin a ), = b + s (m sin a + g eos a ).

Пример такой траектории показан на рис. 3,а. Если в (9)-(10) изменять

только угол поворота или только масштабный коэффициент ^, оставляя остальные параметры постоянными, то траектория соответствующей неподвижной точки будет эллиптической (рис. 3,6). Таким образом, на бинарном изображении, состоящем из точек, в которых А(/, j) = 0 хотя бы при одном вспомогательном преобразовании, следует обнаружить эллипс или прямую линию и определить параметры этой линии. Мы будем отдавать предпочтение прямым линиям, так как их легче обнаружить (рис. 3,в).

Рис. 3. Траектории движения неподвижных точек геометрического преобразования

Пусть найдена прямолинейная траектория и(/) = Л + Д = + £ неподвижных точек. Возьмем на ней две неподвижных точки и получим систему четырёх нелинейных уравнений (две пары уравнений (10)) с четырьмя неизвестными , решение которой численным методом даст искомые оценки параметров ГТ (применялся метод Пыотона).

Уменьшение перебора при нахождении траекторий неподвижных го-чек. На изображении Л(.', ]), помимо неподвижной точки, могут быть и другие точки, где А (г, ]) = 0 из-за случайного совпадения величин *(',./) и

]) (рис. 3,в). Кроме того, из-за ошибок интерполяции изображений и возможной их зашумленности равенство Л(/, ]) = 0 может не выполняться даже в неподвижной точке. Поэтому будем в качестве индикатора применять неравенство Д(/, /') < Л., где Я - некоторый порог. Но при этом возрастает количество случайных точек, «подозрительных» на неподвижность, а также и количество ложных прямолинейных траекторий, что увеличивает дальнейший пере-

ним IIоV(".-.т/чг>ггч'г (т-гглтIгг\тл ТТ">Я лт/*, ч-чг^тятя' ог»оттт.тъ*а£»т ЧОТТОТТ^ЛТТТрТ/'Л_

I "•-'''1 1' * ^"" " ' - -■ ~ -

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

Для уменьшения количества точек, «подозрительных» на неподвижность, кроме близости яркостей изображений, примем во внимание другие локальные особенности изображений, например, квадрат градиента и лапласиан изображений х(к,1) и у) . Нетрудно показать, что

| Vz(U)|2= 1Vx(k(i,j),l(i,j))I2, Az(i,j) = (sst)2¿*MiJ),I(i,j)).

Эти равенства в неподвижной точке (u,v) принимают вид:

| VZ(K,V)|2=(JÍ,)2 | VX(M,V)|2, AZ(",v) = (^1)2AX(W,V), (12)

где коэффициент (sí,)2 неизвестен из-за неизвестности s . Рассмотрим преобразование

(/, j) Н Vx(i, j) \2 A z(i, j), z' (/, j) =| Vz(i, j) |2 A x(i, j), (13) изображений x(k,l) и z{¡, j). В силу (12) значения (13) в неподвижной точке (m,v) совпадают: x'(u,v) - z'(u,v). Учёт только тех точек, в которых дополнительно к A(i,j) = 0 выполняется x'(i,j)-z'(¡,j), значительно уменьшает количество точек, «подозрительных» на неподвижность, что сокращает дальнейший перебор. Изображения заданы на целочисленных сетках, поэтому преобразования (13) можно выполнить только численно. Из-за погрешностей численного дифференцирования и возможной зашумлённости изображений соотношение x'(i,j) = z'(i,j) и А(г,7') = 0 в точках, «подозрительных» на неподвижность, должны выполняться хотя бы приближенно, то есть с некоторой допустимой погрешностью.

Рассмотрим теперь задачу обнаружения прямолинейных траекторий на бинарном изображении, состоящем из точек, «подозрительных» на неподвижность. Истинная прямолинейная траектория представляет собой приблизительно прямую линию, расположенную среди хаотически разбросанных посторонних точек. Возможно также наличие ложных прямолинейных траекторий, параллельных истинной траектории. На рис. 4а показан пример изображения, на котором просматриваются восемь прямых линий на фоне беспорядочного множества посторонних'точек. Отметим, что это изображение «объединённое» -оно является суммой нескольких бинарных изображений, каждое из которых состоит из точек, отобранных для своего центра поворота (а,,^).

Пусть дано бинарное изображение С = {c(i,j)}. Требуется на этом изображении обнаружить прямые линии, то есть группы точек, приблизительно расположенные на прямых. Рассмотрим на изображении С окно с центром (i,j) . Пусть {{(р{п), у/(п)), п = I...N} - координаты точек, попавших в это окно. Будем рассматривать каждую точку (?>("), у (и)) как наблюдение пары случайных величин {Ф,*?}. Тогда, если в окне находится значительное количество точек, приблизительно расположенных на прямой линии, и сравнительно немного посторонних точек, то между этими случайными величинами будет большое значение квадрата выборочного коэффициента корреляции

p\i,j) = соу^Ф.ЧО/^ОР^От (14)

где (Т2(Ф),<т2(Чу),соу(ФЛР) - выборочные дисперсии величин {Ф,ЧР} и их ко-вариации в этом окне. Если количество точек в окне меньше допустимого, то полагаем p2(i,j) = 0. Таклм образом, за индикатор прямой линии принимается превышение порога статистикой (14). По коэффициенту корреляции не обиа-

руживаются вертикальные и горизонтальные прямые линии при отсутствии посторонних точек, но такие прямые линии легко обнаруживаются по признаку сг2(Ф) » 0 или сг2^) да 0 . На рис. 4,6 показано множество точек, в которых имело место превышение порога статистикой (14) при обработке изображения с рис. 4,а. Эти точки группируются около прямых линий. В таких участках производится вспомогательная обработка для о тсева ложных тревог и более точной локализации прямых линий. В частности, строится линия среднеквадратиче-ской регрессии, положение которой уточняется исключением из рассмотрения наиболее удаленных от неё точек.

у

У У У

Рис. 4. Обнаружение прямых линий на изображении

В качестве способа отсева ложных прямолинейных траекторий может быть предложена траекторная обработка последовательного появления точек. Здесь учитывается тот факт, что при поступательном движении точки поворота (Я] (0>(0) по прямой (11) истинные неподвижные точки (и(?),г(/)) появляются на прямолинейных траекториях также поступательно с постоянной скоростью. На ложных ж? прямолинейных траекториях могут быть значительные скачки скорости появления -точек и нарушения поступательного движения.

После исключения по данному признаку ложных прямолинейных траекторий для каждой оставшейся «подозрительной» прямолинейной траектории находятся параметры Р = (а,Ъ,8,а) и выбирается тот их набор, при котором происходит наилучшее совпадение изображений х(/(г, у';а), у';а)) и у {г, у), то есть когда

X, ГУ РУ> - Л!2 - пнп,

что и принимается за окончательную искомую оценку параметров ГГ.

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

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

ких хаотично разбросанных точек. Интерес представляют полоски, в которых точки находятся приблизительно на равных расстояниях. Пусть поле случайных точек на изображении площади S - пуассоновское с плотностью Я, а полосы имеют ширину а и направления с дискретом А<р радиана. Тогда для математического ожидания М случайных траекторий, содержащих т точек, расположенных на расстояниях h±s друг от друга, получается оценка

М < nSXmam-\^m A)lahem-' / Аср. (15)

Отметим, что значение (15) обычно очень мало. Например, для изображения размеров 1000x1000 с плотностью Д = 0.05, при <2 = 1, h = 1, £ = 0.5, т = 6 и = 1/180 имеем М<0.072.

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

Совмещение трехмерных изображений. Рассмотрим теперь применение алгоритмов, основанных на неподвижной точке, к трёхмерным изображениям x(I,J,K) и y(i,j,k) при оценке параметров часто встречающегося ГТ, включающего в себя параллельный перенос (а,Ь,с), поворот вокруг нового начала координат на углы Эйлера а,(р,у , изменение масштаба с коэффициентом s : I = а + ф'cos a cos (р + y(cos а sin <Р sin ^ — sin a cos у) + + ¿(eos a sin (р eos у + sin a sin у)\,

J = Ъ + s[i sin a cos (р + j(sin a sin (р sin у + cos a cos у) + ^^ + ¿(sin a sin (р cos у - cos a sin у)], К = с + í[-¡'sin <р + j cos ср sin у + к cos ср cos у)]. Применим к изображению y{i,j,k) вспомогательное преобразование того же вида (16) с параметрами ((а,, 6,, с,),, , , i',). Если точку поворота (а,, bl, с,) перемещать по любой прямой, то и неподвижная точка сложной ГТ так же, как и в двумерном случае, будет перемещаться по некоторой прямолинейной траектории, но параметрам которой можно определить искомые параметры ГТ. Но эту прямолинейную траекторию нужно обнаружить во множестве точек трёхмерного пространств?., «подозрительных» на неподвижность, некоторые из которых MOiyr образовывать ложные прямолинейные траектории. На рис. 5,а показано изображение, полученное описанной процедурой из имитированных с помощью волновой модели трехмерных изображений 120x120x120, параметры ГТ: а = 20,6 = 20,с = 20, а = 5, ср' = 0, у° = 0 и

i = 0.9. На рисунке точки даны в проекции и поэтому выглядят плотнее, чем на самом деле. Кроме истинной прямолинейной траектории неподвижных точек, может оказаться несколько параллельных ей ложных. Предлагается следующий алгоритм поиска истинной прямолинейной траектории. Группу прямых линий, в которую входит истинная прямолинейная траектория, назовем основной группой. Кроме неё, может оказаться несколько групп взаимно па-

раллельных прямых линий, но линий в этих группах обычно бывает значительно меньше, чем в основной группе. Поэтому будем искать группу с наибольшим количеством параллельных прямых линий. Она почти наверняка будет содержать истинную прямолинейную траекторию. На рис. 5,6 показаны все найденные линии, жирными показаны три линии основной группы. Подставляя параметры всех прямых линий из основной группы в систему уравнений (2) и решая эту систему, найдем несколько наборов возможных значений параметров ГТ. Совмещая два изображения по всем наборам, выберем в качестве искомой оценки параметров ГТ тот набор, который соответствует наилучшему совмещению по критерию минимума среднего квадрата разностей.

а) б)

Рис. 5. Бинарное трёхмерное изображение из «подозрительных» на неподвижность точек

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

о___300

220

* > и ¡¡¡¡г 220

600

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

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

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

В таблице показан размер рабочей зоны алгоритма неподвижной точки я псевдоградиентиого алгоритма в зависимости от коэффициентов корреляции Р|,Р2 модели Хабиби (размер изображений 800x600). Например, на рис. 6 площадь рабочей зоны равна 0.39 от площади изображения. У исевдоградиент-ных алгоритмов рабочая зона 01раничена двойным интервалом корреляции, она на рисунке обозначена черным тоном. При этом рабочая зона алгоритмов неподвижной точки оказалась в несколько десятков раз больше, чем у псевдоградиентных алгоритмов (например, при размере изображения 800x600 пикселей и коэффициенте корреляции 0.9 рабочая зона алгоритма неподвижной точки в 64 раза больше рабочей зоны пссвдоградиентного алгоритма).

Р\ = Р7 0.75 0.80 0.85 0.90 0.95

Площадь рабочей зоны алгоритма неподвижной точки 172255 178024 182621 186610 188522

Площадь рабочей зоны псевдоградиентного алгоритма 392 642 1218 2888 12168

Отношение площадей рабочих зон 439 277 150 64 15

Получены зависимости СКО ошибок оценок сдвига, угла поворота и масштаба от параметров моделей изображений. Все оценки оказались несмещёнными, СКО (при отношении сигнал/ шум 100) не превышало по сдвигу 1.5 пикселя, по углу поворота 0.03 радиана и по масштабу 0.04. Точность оценок повышалась с увеличением коррелированности изображений. Аналогичные результаты были получены при испытаниях алгоритмов на реальных спектрозо-нальных изображениях. Время обработки пары изображений 1000x1000 (при сдвигах до 280 пикселей, любом угле поворота и коэффициенте масштаба в пределах (0.5;2)) около 0.4 с.

Точность оценивания параметров ГТ у предлагаемых алгоритмов значительно ниже, чем, например, у псевдоградиентных и корреляционно-экстремальных алгоритмов, характеристики точности которых близки к потенциально достижимым. Например, для изображений 1000x1000 при отношении сигнал/шум 100 СКО ошибки оценки сдвига составляет около 0.005 пикселя, угла поворота - 0.001 радиана и коэффициента масштаба - 0.0005. Однако даже для достижения точности оценивания, даваемой алгоритмами неподвижной точки (предыдущий абзац), в корреляционно-экстремальном-алгоритме придётся перебрать около (560 /1,5)2(2лг /0.03)(1.5/ 0.04) » Ю.9-108 комбинаций

значений параметров ГТ, что займёт около 9 часов машинного времени. Ещё больше времени потребовалось бы для достижения потенциальной точности. Псевдоградиентные алгоритмы более быстрые, чем корреляционно-экстремальные, например, при наличии начального приближения в пределах рабочей зоны обработка нары рассматриваемых в этом примере изображений требует около 0.001 с. Однако выполнение перебора комбинаций значений параметров для получения такого начального приближения может потребовать несколько минут.

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

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

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

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

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

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

Программный комплекс выполнен в среде программирования Borland С++ Builder 6 на языке программирования высокого уровня С++. Весь комплекс может выполняться автоматически без вмешательства оператора посредством задания всех нужных данных для работы алгоритма в окне программы. На рис. 8 показан пример окна программы при оценке заданных значений параметров ГТ.

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

Рис. 7. Структура комплекса программ

Сдвиг по X е ¡30

Сдвиг no Y.b [-зГГ

Угол поворота А Го.174 » радианах

Коэффициент IñT"" мисштаоирования. к i -1"

Параметры испомогательиих ГТ

Дополнительный Дополнительный поворот. А1-180 коэффициент

масштабирования. кЫ

Дополнительные сдвиги el (t)=m+nt bl(t)-g-ht m- [2 g- ¡3

n- íi h- ií

Оценки ППрПМвГрйН П Оценке сдвигало X.e~ ¡30.42 Оценке сдвиги по V. b~ ^3034"

Оценка угла поворота А~ 10.183 в радианах

Оценка коэффициенте масштвбироовния. к"

. Оценить

Ошибки оценок парометров ГТ

Сдвиг no X

Сдвиг по Y

Угол поворота в радианах

Коэффициент масштабирования

Показать

[0.42 ~

[Ö54

¡0.009

ГоГоз

Преобразованное изображение

Исходное изображение

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

Рекомендуемые системные требования для комплекса программ.

1) Вычислительная машина класса IBM PC.

2) Операционная система Windows ХР.

3) Процессор с тактовой частотой 1.2 ГГц и выше.

4) 256 Мб оперативной памяти.

5) Оценка параметров Г'Г пары двумерных изображений размером 1000x1000 занимает около 0.4 сек, трехмерных изображений размера 1000x1000x1000 - 4 мин на PC с тактовой частотой 1.2 ГГц. Алгоритмы допускают большое распараллеливание, поэтому при применении параллельных вычислительных систем можно значительно сократить время выполнения программы.

6) Размер программы с исполняемым файлом и наборами обрабатываемых изображений около 40 Мб. Объем программного кода примерно 2500 строк.

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

Основными результатами работы являются следующие.

1. Показано, что форма рабочей зоны при оценке сдвига изображений для двумерных - эллипс и эллипсоид для трехмерных, и составляет около 30% от обрабатываемых изображений, практически независимо от их размеров, что в несколько десятков раз превышает размер рабочей зоны псевдоградиентных алгоритмов (например, при размере изображения 800x600 и коэффициенте корреляции на единичном расстоянии 0.9 - больше в 64 раза).

2. Статистическое испытание разработанных алгоритмов на различных реальных и имитированных изображениях показало, что погрешность в оценке сдвига не превышала 1,7 пикселя, максимальная погрешность оценки коэффициента масштаба составляла 0.04 от истинного значения, погрешность в определении угла поворота 2-4°. Эти показатели примерно на два порядка ниже точности псевдоградиентных алгоритмов. Однако большая рабочая зона предложенных алгоритмов позволяет использовать их для получения начального приближения параметров ГТ, а для дальнейшего их уточнения использовать другие алгоритмы, что в целом значительно сокращает вычислительные затраты на получение высокоточных оценок параметров ГТ (па изображениях размеров 1000x1000 примерно в 100 раз).

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

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

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

В изданиях из перечня ВАК:

1. Krasheninnikov V. R., Potapov М.А. Estimating Parameters of Interframe Geometric Transformation of an Image Sequence by the Fixed Point Method // Pattern Recognition and Image Analysis. - 2010. - Vol. 20, No.3. - P. 316-323.

2. Krasheninnikov V. R., Potapov M.A. A Way to Detect the Straight Line Trajectory of an Immovable Point for Estimating Parameters of Geometrical Transformation of 3D Images // Pattern Recognition and Image Analysis. - 2011. - Vol. 21, No.2. - P. 280-284.

В других изданиях:

3. Крашенинников В.Р., Потапов М.А. Метод неподвижной точки для оценки параметров геометрической трансформации изображений // Электронная техника: Сб. научных трудов / под ред. В.А. Сергеева. - Ульяновск: УлГТУ, 2008. - С. 102-107.

4. Крашенинников В.Р., Потапов М.А. Нахождение неподвижных точек для оценки параметров геометрической трансформации // Доклады LXIV научной сессии НТО РЭС, посвященной Дню радио. - Москва, 2009.- С.315-317.

5. Крашенинников В.Р., Потапов М.А. Обнаружение прямых линий при совмещении изображений методом неподвижной точки // Современные проблемы создания и эксплуатации радиотехнических систем: Труды шестой всероссийской научно - практической конференции (с участием стран СНГ), г. Ульяновск, 22-23 сентября 2009 г. -Ульяновск: УлГТУ, 2009. - С. 38-42.

6. Крашенинников В.Р., Потапов М.А. Исследование точности метода неподвижной точки для оценки параметров геометрической трансформации // Доклады LXV научной сессии НТО РЭС, посвященной Дню радио. - Москва, 2010. - С. 380-383.

7. Krasheninnikov V. R., Potapov М. A. Detection of Rectilinear Path of a Fixed Point for the Geometrical Transformation Parameters Estimation of Three-Dimensional Images // 10th International Conference "Pattern Recognition and Image Analysis: New information Technologies". - December 5-12. 2010. - P. 219-222.

8. Потапов М.А. Исследование размеров и формы рабочей зоны при оценке параллельного сдвига изображений методом неподвижной точки // Труды седьмой Всероссийской научно-практической конференции «Современные проблемы создания и эксплуатации радиотехнических систем». - Ульяновск, 2011. - С. 54-56.

Потапов Михаил Александрович Разработка и моделирование алгоритмов оценки параметров геометрической трансформации изображений с использованием неподвижной точки.

Автореферат

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

Подписано в печать 22.11.2011. Формат 60x84/16. Усл. печ. л. 1,16. Тираж 100 экз. Заказ 1236.

Типография УлГТУ, 432027, г. Ульяновск, Северный Венец, 32.

Список сокращений, принятых в диссертации.

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ СОВМЕЩЕНИЯ ИЗОБРАЖЕНИЙ.

1.1. Постановка задачи.

1.2. Методы построения оценок параметров.

1.3. Классификация методов совмещения.

1.4. Тензорная фильтрация смещений.

1.5. Адаптивно-морфологические методы.

1.6. Методы совмещения изображений при растровых искажениях.

1.7. Алгоритмы совмещения по опорным точкам.

1.8. Корреляционные методы.

1.8.1. Простейший метод корреляции.

1.8.2. Метод выделения корреляционных окон.

1.8.3. Метод поиска минимума с большим шагом. Определение параметров трансформации с использованием эллипсов ошибок.

1.8.4. Методы определения сдвига менее одного пикселя.

Поиск смещения по сжатым кадрам.

1.9. Псевдоградиентные алгоритмы совмещения.

1.9.1. Совмещение при заданной модели трансформации.

1.9.2. Совмещение при незаданной модели трансформации.

1.10. Выводы.

ГЛАВА 2. ОЦЕНИВАНИЕ ПАРАМЕТРОВ ГЕОМЕТРИЧЕСКОЙ ТРАНСФОРМАЦИИ ИЗОБРАЖЕНИЙ, ОСНОВАННОЕ

НА ИСПОЛЬЗОВАНИИ НЕПОДВИЖНОЙ ТОЧКИ ОТОБРАЖЕНИЯ.

2.1. Неподвижная точка и принцип сжимающих отображений.

2.2. Использование неподвижной точки для оценивания параметров геометрической трансформации изображений.

2.3. Выводы.

ГЛАВА 3. АЛГОРИТМЫ ОЦЕНИВАНИЯ ПАРАМЕТРОВ ГЕОМЕТРИЧЕСКОЙ ТРАНСФОРМАЦИИ ИЗОБРАЖЕНИЙ

С ИСПОЛЬЗОВАНИЕМ НЕПОДВИЖНОЙ ТОЧКИ.

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

3.1.1. Оценивание сдвига двумерных изображений при малых углах поворота и изменениях масштаба.

3.1.2. Нахождение неподвижных точек.

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

3.1.4. Уменьшение перебора при нахождении траекторий неподвижных точек.

3.1.5. Обнаружение прямых линий на двумерных изображениях.

3.1.6. Ложные прямолинейные траектории во множестве хаотических точек.

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

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

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

3.2.1. Отбраковка ложных неподвижных точек.

3.2.2. Поиск траектории неподвижной точки на трехмерном бинарном изображении.

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

3.3. Исследование формы и размеров рабочей зоны алгоритма неподвижной точки.

3.4. Показатели точности и вычислительные затраты алгоритма неподвижной точки.

3.5. Выводы.

ГЛАВА 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ

ОЦЕНКИ ПАРАМЕТРОВ ГЕОМЕТРИЧЕСКОЙ ТРАНСФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ НЕПОДВИЖНОЙ ТОЧКИ.

4.1. Структура комплекса программ.

4.2. Описание и возможности комплекса программ.

4.3. Системные требования для комплекса программ.

4.4. Дополнительные возможности комплекса программ.

4.5. Выводы.

Актуальность темы. В настоящее время обработка изображений (двумерных и многомерных) широко применяется при решении многих научных и практических проблем, среди которых исследование космического пространства, мониторинг Земли, навигация, биология, медицина, робототехника и т.д. [8,13, 53, 58, 63, 71, 73, 74, 75, 77 , 84, 99, 100, 101].

Многие из этих исследований связаны с обработкой совокупностей изображений - их временных последовательностей или же единовременно зарегистрированных изображений, полученных с различных сенсоров, например, спектрозональных изображений [7, 16, 23, 27, 44, 48, 50, 52, 64, 65, 70, 78, 85, 90, 97]. При обработке совокупностей изображений может потребоваться их совмещение, то есть установление соответствия между точками этих изображений, относящимися к одним и тем же элементам сцены. Это позволяет обнаруживать временные изменения в серии изображений. Совмещение изображений, полученных от различных сенсоров, даёт возможность извлечения более полной информации о наблюдаемом объекте, чем из отдельных изображений [15, 19, 28, 59, 87, 98]. Совмещение изображений применяется также при обнаружении и распознавании объектов [55, 61, 68, 69].

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

Совмещение изображений обычно требуется выполнять в реальном времени, что ведёт к необходимости разработки алгоритмов с приемлемыми вычислительными затратами. Очень часто задача совмещения изображений может быть сведена к оцениванию параметров межкадровой геометрической трансформации (ГТ) этих изображений (сдвига, поворота, масштаба и т.д.). [11, 20, 25, 42]. При этом в прикладных задачах значения этих параметров могут быть большими (например, в медицине и робототехнике).

В настоящее время существует множество методов и алгоритмов оценивания параметров ГТ, однако они требуют неприемлемых вычислительных затрат при больших значениях параметров ГТ. Например, в корреляционно-экстремальных алгоритмах для достижения высокой точности требуется производить пробные совмещения при большом количестве комбинаций значений параметров ГТ [22]. Псевдоградиентные алгоритмы (ПГ) дают высокоточные оценки параметров при небольших вычислительных затратах, но их существенным недостатком является небольшая рабочая зона (РЗ), то есть требуется иметь достаточно точные начальные приближения значений параметров ГТ, при которых эти алгоритмы работоспособны [10]. Поэтому, при возможных больших значениях параметров, приходится применять эти алгоритмы многократно для множества возможных начальных приближений, что также ведёт к большим вычислительным затратам. Из сказанного следует, что было бы весьма полезно иметь алгоритмы, которые при небольших вычислительных затратах обладают большой РЗ и дают оценки параметров ГТ, которые можно использовать в качестве начальных приближений для высокоточных алгоритмов.

Таким образом, разработка алгоритмов оценивания параметров ГТ изображений с большой РЗ является актуальной.

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

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

1. Построение алгоритмов оценки параметров ГТ изображений на основе метода неподвижной точки (НТ) оператора ГТ.

2. Исследование математических моделей ГТ изображений и нахождение их НТ.

3. . Математическое моделирование траекторий НТ последовательности ГТ. Выбор вспомогательных ГТ, обеспечивающих траектории простого типа для облегчения их обнаружения.

4. Разработка численных процедур для вычисления параметров ГТ по параметрам траектории НТ оператора ГТ.

5. Исследование точности разработанных алгоритмов, а также формы и размера их РЗ на реальных и имитированных изображениях.

6. Разработка комплекса программ, реализующего предложенные алгоритмы.

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

Научная новизна положений, выносимых на защиту.

1. Предложен новый способ оценки параметров ГТ изображений с использованием НТ оператора ГТ, который при небольших вычислительных затратах имеет РЗ, значительно большую по сравнению с известными алгоритмами.

2. Для ряда моделей ГТ определены виды вспомогательных преобразований, обеспечивающих прямолинейность траекторий НТ.

3. Разработаны алгоритмы обнаружения прямолинейных траекторий (ПТ) и численные процедуры оценивания параметров ГТ изображений по параметрам этих траекторий.

4. Разработан комплекс прикладных программ для совмещения изображений со значительными ГТ.

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

Реализация результатов работы. Результаты диссертационной работы использованы при выполнении госбюджетной НИР УлГТУ, гранта РФФИ а09-08-00725 и в учебном процессе УлГТУ в дисциплине «Основы теории обработки изображений», что подтверждено соответствующим актом.

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

Апробация работы. Основные результаты работы докладывались на VI и VII Всероссийских с участием стран СНГ научно-практических конференциях «Современные проблемы создания и эксплуатации радиотехнических систем» (Ульяновск, 2009 и 2011); ЬХ^ и ЬХУ научных сессиях Российского научно-технического общества радиотехники, электроники и связи им. А.С.Попова, посвященных Дню радио (Москва, 2009 и 2010); 10-й Международной научно-технической конференции РША-2010 «Распознавание образов и анализ изображений: новые информационные технологии» (Санкт-Петербург, 2010) и ежегодных конференциях профессорско-преподавательского состава Ульяновского государственного технического университета (2008-2011 гг.).

Публикации. По теме диссертации опубликовано 8 статей, из них 2 опубликованы в изданиях из перечня ВАК и 6 в трудах научных конференций.

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

4.5. Выводы

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

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

ЗАКЛЮЧЕНИЕ

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

Основными результатами работы являются следующие.

1. Показано, что форма РЗ при оценивании сдвига изображений для двумерных — эллипс и эллипсоид для трехмерных, и составляет около 30% от обрабатываемых изображений, практически независимо от их размеров, что в несколько десятков раз превышает размер РЗ псевдоградиентных алгоритмов (например, при размере изображения 800x600 и коэффициенте корреляции на единичном расстоянии 0.9 - больше в 64 раза).

2. Статистическое испытание разработанных алгоритмов на различных реальных и имитированных изображениях показало, что погрешность в оценке сдвига не превышала 1,7 пикселя, максимальная погрешность оценки коэффициента масштаба составляла 0.04 от истинного значения, погрешность в определении угла поворота 2-4°. Эти показатели примерно на два порядка ниже точности псевдоградиентных алгоритмов. Однако большая РЗ предложенных алгоритмов позволяет использовать их для получения начального приближения параметров ГТ, а для дальнейшего их уточнения использовать другие алгоритмы, что в целом значительно сокращает вычислительные затраты на получение высокоточных оценок параметров ГТ (на изображениях размеров 1000x1000 примерно в 100 раз).

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

1. Аксёнов О. Ю. Совмещение изображений // Цифровая обработка сигналов. 2005.-№3.-С. 51-55.

2. Андреев Г. А. Алгоритмы обработки навигационной пространственно-временной информации. Часть II / Г. А. Андреев. А. А. Потапов // Зарубежная радиоэлектроника. 1989. - № 4. - С. 3-21.

3. Афанасьева Т. В. Статистический алгоритм распознавания прямых линий / Т. В. Афанасьева, Г. А. Герчес, А. И. Стражнов // Методы обработки сигналов и полей. Межвузовский сборник научных трудов. Ульяновск: -УлПИ, 1990.-С. 60-65.

4. Бочкарев А. М. Корреляционно-экстремальные системы навигации // Зарубежная радиоэлектроника. 1981. - №9. - С. 28-53.

5. Бутаков Е. А. Обработка изображений на ЭВМ / Е. А. Бутаков, В. И Островский, И. Л Фадеев. М.: Радио и связь, 1987. - 240 с.

6. Быков Р. Е. Анализ и обработка цветных и объемных изображений / Р. Е. Быков, С. Б. Гуревич. М.: Радио и связь, 1984. - 248 с.

7. Бьемон Ж. Итерационные методы улучшения изображений /Ж. Бье-мон, Р. Л. Лагендейк, Р. М. Марсеро // ТИИЭР, 1990. Т.78, № 5. - С. 58-84.

8. Васильев К. К. Методы фильтрации многомерных случайных полей / К. К. Васильев, В. Р. Крашенинников. Саратов: СГУД990. - 128 с.

9. Васильев К. К. Статистический анализ многомерных изображений / К. К. Васильев, В. Р. Крашенинников. Ульяновск: УлГТУ,2007. - 170 с.

10. Волегов Д. Б. Поиск карты смещений по пирамиде детальности / Д. Б. Волегов, Д. В. Юрин // 17-я международная конференция по компьютерной графике и ее приложениям ГрафиКон'2007. Москва,2007. - С. 223-226.

11. Волегов Д. Б. Грубое совмещение изображений по найденным на них прямым линиям / Д. Б. Волегов, Д. В. Юрин // 16-я международная конференция по компьютерной графике и ее приложениям ГрафиКон'2006. -Новосиб., 2006. С. 463-466.

12. Гимельфарб Г. JI. Аппаратные средства и особенности программного обеспечения диалоговой цифровой обработки изображений // Зарубежная радиоэлектроника. 1985. -N 10. - С. 87-128.

13. Гмурман В. Е. Теория вероятностей и математическая статистика / В.Е. Гмурман. -М.: Высш. шк., 2003. 449 с.

14. Голд Б., Рэйдер Ч. Цифровая обработка сигналов: Пер. с англ. / Под ред. A.M. Трахтмана. М.: Советское радио, 1973. - 368 с.

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

16. Горьян И. С. Оптимальное обнаружение протяженных областей в изображении / И. С. Горьян, В. Н Зеленцов, В. Т Фисенко // Методы обработки сигналов и полей. Межвузовский сборник научных трудов. Ульяновск: УлПИ, 1990. - С. 56-60.

17. Гутер Р. С. Элементы численного анализа и математической обработки результатов опыта / Р. С. Гутер, Б. В. Овчинский. М.: Физматгиз, 1962.-356 с.

18. Даджион Д. Цифровая обработка многомерных сигналов / Д. Дад-жион, Р. Мерсеро М.: Мир, 1988. - 488 с.

19. Дейхин JL Е. Использование непараметрических статистик для совмещения изображений / JI. Е. Дейхин // Тезисы докладов междунар. конф. ОИДИ-90. Новосибирск: ВЦ СО АН СССР, 1990. С. 70.

20. Дейхин Л. Е. Непараметрическое обнаружение и распознавание линий на изображениях // Тезисы докл. науч.-техн. семинара. Ульяновск: УлПИ, 1987.-С. 22-23.

21. Дейхин Л.Е. Исследование корреляционных функций изображений. В кн.: Методы статистической обработки изображений и полей / Новосибирский электротехн. ин т, 1986. - С.67-69.

22. Журавлев Ю. И. Распознавание образов и распознавание изображений / Ю. И. Журавлев, И. Б. Гуревич // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 2. - М.: Наука, 1989.-С. 5-72.

23. Залогова Л.А. Компьютерная графика. Элективный курс: учебное пособие. М.: Бином, 2005. - 245 с.

24. Заславский А. А. Геометрические преобразования. М.: МЦНМО, 2004. - 86 с.

25. Захарченко А. А. Морфологические методы анализа многофокусных изображений: Сб. докладов 12-й Всероссийской конференции "Математические методы распознавания образов". М.: МАКС Пресс, 2005.

26. Зубарев Ю. Б. Цифровая обработка телевизионных и компьютерных изображений / Ю. Б. Зубарев, В. П. Дворкович. М.: МЦНиТИ, 1997. -216 с.

27. Ким А. К. Алгоритмы подавления нестационарного мешающего фона в сенсорах с неточно известной и меняющейся во времени системой координат / А. К. Ким, А. Е. Колесса, В. Н. Лагуткин, А. В. Лотоцкий, В. Г. Репин // Радиотехника. 1998. - №12. - С. 39-41.

28. Кожушко Я. Н. Алгоритмы совмещения изображений в корреляционно-экстремальных системах навигации летательных аппаратов // Системы обработки информации. X.: Харьковский университет Воздушных сил им. И. Кожедуба, 2008. - Выпуск 1 (68). - С. 25-28.

29. Колмогоров А. Н. Элементы теории функций и функционального анализа / А. Н. Колмогоров, C.B. Фомин. М.: Наука, 1972. - 544 с.

30. Кондратенков Г. С. Методика автоматического совмещения радиолокационных изображений с цифровыми картами и оптическими снимками местности / Г. С. Кондратенков, В. Н. Быков, А. Ю. Викентьев // Радиотехника. 2007. - №8. - С. 99-101.

31. Конкин Ю. В. Разработка системы определения координат летательного аппарата на основе совмещения радиолокационной и картографической информации: Автореф. дис. канд. техн. наук: 05.13.01/ Рязан. гос. ра-диотехн. акад. Рязань, 2007. — 19 с.

32. Красносельский М. А. Положительные решения операторных уравнений. М.: Физматгиз, 1962. - 394 с.

33. Крашенинников В. Р. Исследование точности метода неподвижной точки для оценки параметров геометрической трансформации / В. Р. Крашенинников, М. А. Потапов // Доклады LXV научной сессии НТО РЭС, посвященной дню радио. Москва, 2010. - С. 380-383.

34. Крашенинников В. Р. Метод неподвижной точки для оценки параметров геометрической трансформации изображений / В.Р. Крашенинников, М.А. Потапов // Электронная техника. Сб. научных трудов под ред. В.А. Сергеева. Ульяновск: УлГТУ, 2008. - С. 102-107.

35. Крашенинников В. Р. Адаптивные алгоритмы совмещения изображений / В. Р. Крашенинников, А. Г. Ташлинский // Тез. докл. Междунар. конф. ОИДИ-90, Новосибирск: ВЦ СО АН СССР, 1990. С. 138-139.

36. Крашенинников В. Р. Оценка геометрических трансформаций бинарных изображений / В. Р. Крашенинников, А. Г. Ташлинский // Тез. докл. 49-й научной сессии, поев. Дню радио. М.: РНТО РЭС им. А.С.Попова, 1994, ч.2.-С. 122-123.

37. Крупицкий Э. И. Сравнение эффективности аналоговых оптических процессоров для обработки изображений с ЦВМ / Э. И. Крупицкий, А. Я. Смирнов, В. С. Эмдин. В сб.: Повышение эффективности и надежности РЭС // ЛЭТИ. - Л., 1976. - Вып. 4. - С. 69-73.

38. Крючков А. Н. Методы трансформирования аэрокосмических изображений // Цифровая обработка изображений под ред. С. В. Абламейко. -Минск: Ин-т техн. кибернетики HAH Беларуси, 1999. Вып.З. - С. 202-218.

39. Ласло М. Вычислительная геометрия и компьютерная графика на С++ / Пер. с англ. М.: БИНОМ, 1997. 304 с.

40. Люстерник Л. А. Элементы функционального анализа / Л. А. Люс-терник, В. И. Соболев. М.: Наука, 1965. - 520 с.

41. Мартинес Ф. Синтез изображений. М.: Радио и связь, 1990. - 192с.

42. Павлидис Т. Алгоритмы машинной графики и обработки изображений. -М.: Радио и связь, 1986.

43. Прэтт У. Цифровая обработка изображений. М.: Мир, 1982. - 790с.

44. Путятин Е. П. Обработка изображений в робототехнике / Е.П. Путятин, С.И. Аверин. -М.: Машиностроение, 1990. 320 с.

45. Пытьев Ю. П. Задачи морфологического анализа изображений. В сб.: Математические методы исследования природных ресурсов Земли из Космоса. -М.: Наука, 1984.

46. Пытьев Ю.П., Морфологический метод в задаче идентификации объектов по их изображениям / Ю. П. Пытьев, А. И. Чуличков В сб. Проблемы искусственного интеллекта и распознавания образов. Киев - 1984.

47. Пытьев Ю. П. Морфологический анализ изображений: Докл. АН СССР. 1983. -т.269. -Ы 5. - С. 1061-1064.

48. Пытьев Ю. П. Морфологический и нечеткий анализ изображений групп точечных объектов / Ю. П. Пытьев, А. И. Чуличков // Математические методы распознавания образов. Звенигород, 1993.

49. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов / Л. Рабинер, Б. Гоулд // Пер. с англ. под ред. Ю. Н. Александрова. -М.: Мир, 1978.-848 с.

50. Репин В. Г. Спектральный метод компенсации смещений и повышения разрешения изображений при обработке последовательности смещающихся цифровых кадров / В. Г. Репин, В. Н. Лагуткин // Радиотехника и электроника. Том 45. - №11. — С. 1359-1364.

51. Роджерс X. Теория вычислимых функций и эффективная вычислимость. М.: Изд-во МИР, 1972г. - 624 с.

52. Розенфельд А. Распознавание и обработка изображений. М.: Мир, 1972.-230 с.

53. Савиных В. П. Преобразование космических снимков в заданную картографическую проекцию / В. П. Савиных, Л. М. Бугаевский, В. А Малинников // Геодезия и картография. 2004. -№ 4. - С. 30-32.

54. Сойфер В. А. Компьютерная обработка изображений, Ч. 1 // Соров-ский образовательный журнал. № 2. - 1996. - С. 118-124.

55. Сойфер В. А. Компьютерная обработка изображений Ч. 2 // Соров-ский образовательный журнал. -№ 3. 1996. - С. 110-121.

56. Спектор А. А. Текущая марковская оценка смещения кадров, формируемых различными датчиками изображений // Научный вестник НГТУ. -2002.-№1.-С. 3-11.

57. Ташлинский А. Г. Оценивание параметров пространственных деформаций последовательностей изображений / Ульяновский государственный технический университет. Ульяновск: УлГТУ, 2000. - 132 с.

58. Томашевич Н. С. Методы реализации инвариантности к аффинным преобразованиям при распознавании двумерных изображений / Н.С. Томашевич, Д. С. Томашевич, А. И. Галушкин // Информационные технологии. -2001. -№1-С. 1-19.

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

60. Хуанг Т. С. Обработка изображений / Т. С Хуанг, В. Шрейбер, О. Третьяк // ТИИЭР. 1971. - Т.59. - №11. - С. 59-89.

61. Хуанг Т. С. Быстрые алгоритмы в цифровой обработке изображений. Преобразования и медианные фильтры. М.: Радиосвязь, 1984. - 224 с.

62. Шилов Г. Е. Математический анализ: Специальный курс. М., 1961.-436 с.

63. Штейнбок М. Я. Иерархический подход в задаче корреляционно-экстремальной обработки изображений // Обработка изображений и дистанционные исследования (0ВДИ-90). Тезисы докладов международной конференции. Новосибирск: ВЦ СО АН СССР, 1990. - С. 202.

64. Эльман Р. И. О синтезе структуры анализатора изображений // Изв. АН СССР: Техническая кибернетика, 1968. №1. - С. 135-150.

65. Яне Б. Цифровая обработка изображений. Москва: Техносфера, 2007.-584 с.

66. Ярославский JI. П. Введение в цифровую обработку изображений. -М.: Сов. радио, 1979. 312 с.

67. Ackermann F. Digital image correlation: Performance and potential application in photogrammetry // Photogrammetric Record. 1984. - No 11 (vol. 64).-P. 429-439.

68. Andrews H. C. Image processing by digital computers / H. С Andrews, A. G. Tescher , R. P. Kruger // IEEE Spectrum. 1972. - No 7 (vol. 9). - P. 2032.

69. Border К. C. Fixed point theorems with applications to economics and game theory. Cambridge, 1985. - 140 p.

70. Chipolla R. Robust Structure from Motion Using Motion Parallax / R. Chipolla, Y. Okamoto, and Y. Kuno // Int'l Conf. Computer Vision. Berlin, May 1993.-P. 374-382.

71. Dowman I. J. Automating image registration and absolute orientation: solutions and problems // Photogrammetric Record, 1998. No 16 (vol. 91). - P. 5-18.

72. Gabrani M. Surface-based matching using elastic transformation / M. Gabrani, O. J. Tretiak // Pattern Recognition, 32. 1999. - P. 87-97.

73. Hill D. L. G. A strategy for automated multimodality image registration incorporating anatomical knowledge and imager characteristics / D. L. G. Hill, D.J. Hawkes, N. A. Harrison, C. F. Ruff. 1993.

74. Gonzalez R. C. Digital Image Processing / R. C. Gonzalez, P. Wintz // Addison-Wesley. Reading. Massachusetts. 1987. - 505 p.

75. Gruen A. W. Adaptive least squares correlation: a powerful image matching technique // S. Afr. J. of Photogrammetry, Remote Sensing and Cartography, 1985.-No. 3 (Vol. 14).-P. 175-187.

76. Horn B. K. P. Direct methods for recovering motion / B. K. P. Horn, E. J. Weldon, Jr. // International Journal of Computer Vision. 1988. - No. 51 (Vol. 2).-P. 51-76.

77. Jain A. K. Fundamentals of Digital Image Processing. N.J.: Prentice-Hall, 1988.-569 p.

78. Krasheninnikov V. R. Estimating Parameters of Interframe Geometric Transformation of an Image Sequence by the Fixed Point Method / V. R. Krasheninnikov, M. A. Potapov // Pattern Recognition and Image Analysis. 2010. - Vol. 20, No. 3,-P. 316-323.

79. Lagunovsky D. Straight-line-primitive extraction in grey-scale object recognition / D. Lagunovsky, S. Ablameyko // Pattern Recognition Letters, 20 -1999.-P. 1005-1014.

80. Lustman F. Motion and Structure from Motion from Point and Line Matching / F. Lustman, O. D. Faugeras, and G. Toscani // Proc. First Int'l Conf. Computer Vision. 1987. - P. 25-34.

81. McLachian G.J. Discriminant Analysis and Statistical Pattern Recognition. John Wiley & Sons, 1992.