Диссертация (1143951), страница 17
Текст из файла (страница 17)
онимогут быть заменены однократным предварительным вычислением полярныхкоординат всех точек многоугольника (шаг 1) и параметров колебаний (шаг 2.1).Также потребуется выполнить операцию обратного преобразования Фурьедля изображения размерностью Ky×Kx, такое же количество вычислений IOB и IBG,2KyKx операций умножения, KyKx операций сложения, а также свертку результатаумножения с импульсным откликом. Очевидно, наибольший объем вычисленийприходится на тригонометрические операции при расчете фурье-образа: 7nKF парcos/sin.
Каждое вычисление cos/sin на современном процессоре архитектуры x86требует приблизительно в 10-20 раз больше тактов по сравнению с умножением.Теоретическая оценка числа операций показывает, что для синтеза изображенияразмером 100×100 пикселей при полном заполнении фурье-плоскости, а также приколичестве точек границы n=100, эквивалентное число операций составитприблизительно 107. Это на порядок меньше, чем при использованиирассмотренного выше эффективного метода субпиксельного синтеза (раздел 2.3.3)(при тех же параметрах с шагом дискретизации 1/100 пикселя), и на два порядкаэффективнее простого метода субпиксельного синтеза (раздел 2.3.2).Важным свойством предлагаемого алгоритма является то, что еговычислительнаясложностьнезависитотсубпиксельнойточностивоспроизведения геометрии моделируемого объекта. Кроме того, алгоритмэффективно поддается параллелизации, т.к.
каждый фурье-коэффициент длякаждого из треугольников разбиения рассчитывается независимо от других.972.4. Оценка параметров модели по дискретному изображению(обратная задача)2.4.1.Постановка задачиОбратнаязадачаметодадвумернойаппроксимациизаключаетсявминимизации критерия отклонения регистрируемого и синтезируемого двумерныхсигналов изображений.
Распространенным критерием в задачах обработкиизображений является L2-норма разностного сигнала. Для упрощения решениязадачи, воспользуемся в качестве оптимизируемого критерия квадратом L2-нормы.Тогда обратная задача метода формулируется следующим образом:ˆ ,Yˆ ,Kˆ ,Kˆ ) = arg min ( E ) : E = 1 I [ x, y ]2 ,(XOBBGD2 ( x. y )μX ,Y ,K OB ,K BGID = IMX ,Y ,K OB ,K BG(2.25)− IE ,где Xˆ , Yˆ – искомые параметры границы (декартовы координаты точек),ˆKOBиˆKBG– параметры яркости объекта и фона соответственно, IM и IE – матрицысинтезированногоизарегистрированногосигналовизображений,µ-анализируемая область пикселей изображения.
Коэффициент ½ введен дляупрощения записи градиента функционала E.Решение оптимизационной задачи (2.25) предлагается искать методамичисленной оптимизации. Поскольку искомые параметры являются непрерывнымивеличинами, а также учитывая требование высокой точности решения, интереспредставляют градиентные методы оптимизации, такие как метод градиентногоспуска, метод наискорейшего спуска, нелинейный метод сопряженных градиентови другие [96]. Вне зависимости от конкретного метода, градиентная стратегияоптимизациитребуетвычислениявектораградиентаоптимизируемогофункционала E.
Частные производные, составляющие вектор градиента, можноразделить на две группы: производные по параметрам моделей яркости, ипроизводные по параметрам границы объекта.98Заметим, что вне зависимости от параметра, для искомых частныхпроизводных выполняется следующее соотношение: ( I M [ x, y ]) E= I D [ x, y ], ( x. y )μ (2.26)где υ – некоторый параметр модели. Таким образом, для расчета производнойдостаточно определить, каким образом будет изменяться матрица синтезируемогоизображения при изменении того параметра, для которого рассчитываетсяпроизводная.
В связи с этом, способы расчета производных по параметрам яркостии границы объекта несколько отличаются друг от друга.Точные значения производных также зависят от способа расчета матрицысинтезируемого изображения IM. Дальнейший расчет производных осуществляетсяв рамках дискретной модели изображения (2.21) при допущении постоянствараспределения яркости в пределах пикселя синтезируемого изображения.Соответствующий указанным допущениям алгоритм моделирования изображения(на основе расчета фурье-образа ограничивающего объект многоугольника) описанв разделе 2.3.4.2.4.2.Расчет вектора градиента функционалаЧастные производные по параметрам яркости.Проведем расчет отдельно для полиномиальной и сверточной моделейраспределения яркости.Полиномиальная модель яркости.
В общем виде эта модель определяетсяNвыражением (2.8): I ( x, y ) = K[i ]Qi ( x, y ), где K – вектор параметров модели (i=1..N),i =1Qi – базисные функции модели. Объединяя эту модель с дискретной модельюизображения (2.21), получаем: NOB N BGI M = ( K OB [i ]Qi ) M + ( K BG [i ]Qi ) ( U − M ) h , i =1 i =199где KOB и KBG – векторы параметров модели для объекта и фона соответственно,NOB и NBG – размерности векторов параметров, Qi – матрица отсчетов i-й базиснойфункции яркости.Дифференцируя по i-му параметру яркости объекта и фона, получаем:I M= K OB [i ]Qi M h, ( K OB [i ])I M= K BG [i ]Qi ( U − M ) h, ( K BG [i ]) где под дифференцированием матрицы IM понимается дифференцирование каждойиз функций, описывающих значения ее элементов.
Частная производнаяоптимизируемого функционала далее вычисляется очевидным образом с помощьювыражения (2.26). Для ускорения расчета производной в случае небольшого числабазисных функций следует предварительно вычислить матрицы базисных функцийяркости Qi.Сверточная модель яркости. Сверточная модель яркости в общем случаеописывается выражением (2.10), а с учетом допущения постоянства яркости впределах пикселя изображения приобретает вид свертки (2.11). Объединяя этумодель с дискретной моделью изображения (2.21), получаем:I M = ( K OB QOB ) M + ( K BG Q BG ) ( U − M ) h,где KOB и KBG – матрицы параметров моделей яркости объекта и фона, QOB и QBG –матрицы отсчетов базисной функции модели яркости объекта и фона.
Матрицы KOBи KBG имеют ту же размерность, что моделируемое изображение.Дифференцируя по элементу матрицы параметров яркости объекта и фона скоординатами (x, y), получаем:I M= ( Λ( x, y ) QOB ) M h, ( K OB [ x, y ]) I M= ( Λ( x, y ) Q BG ) ( U − M ) h, ( K BG [ x, y ]) где Λij ( x, y ) = δixδ jy , δ – символ дельты Кронекера.100Независимое дифференцирование по каждому параметру яркости потребуетбольшого объема вычислений, связанных со сверткой, а количество параметровяркости равно удвоенному числу пикселей изображения, что потребует несколькодесятков тысяч операций свертки для вычисления вектора градиента.
Однакоструктура рассматриваемых производных позволяет выполнить расчет сразу повсем параметрам яркости с использованием лишь двух операций свертки, и приэтом без потери точности. Запишем выражение для производной оптимизируемогофункционала по параметру матрицы яркости объекта, подставляя последнеевыражение в (2.26):E= I D [i, j ] ( Λ( x, y ) QOB ) M h [i, j ] . ( K OB [ x, y ]) ( i. j )(())Заменим сумму элементов матрицы с заданными индексами на поэлементноепроизведение со вспомогательной матрицей C:E= ( I D С ) ( Λ( x, y ) QOB ) M h [i, j ], ( K OB [ x, y ]) i , j())(1,(i, j ) μC[i, j ] = 0,(i, j ) μ .Теперь представим дискретную свертку через сумму и преобразуем результатпутем перестановки слагаемых и множителей к удобному для вычислений виду:E= ( I D С ) [i, j ] QOB [ x − m, y − n ]M[m, n ]h[i − m, j − n ] = ( K OB [ x, y ]) i , j m ,n= ( I D С ) [i, j ]QOB [ x − m, y − n ]M[m, n ]h[i − m, j − n ] =i , j m ,n= QOB [ x − m, y − n ]M[m, n ] ( I D С ) [i, j ]h[i − m, j − n ].m ,ni, jЗаметим, что вложенная сумма является дискретной корреляцией, тогда:) ()E= QOB [ x − m, y − n] M[m, n] ( ( I D С) h ) [m, n] = ( ( I D С) h ) M QOB [ x, y ], ( K OB [ x, y ]) m,n(где символ «∘» обозначает дискретную корреляцию.Следовательно, все производные для параметров яркости объекта могут бытьрассчитаны с помощью двух операций поэлементного умножения и двух операцийсвертки, что на несколько порядков быстрее независимого дифференцирования по101каждому параметру матрицы яркости.
Для параметров матрицы яркости фонарасчет производной осуществляется аналогичным образом с заменой M на (U-M).Таким образом, все производные по параметрам матрицы яркости длярассмотренных моделей вычисляются аналитически, что во многом определяетэффективность применения градиентных методов оптимизации. Для производныхпо параметрам границы объекта такого простого решения найти не удается,требуется численное дифференцирование.Частные производные по параметрам границы объекта.Рассмотримизменениематрицысинтезируемогоизображения,соответствующее изменению координаты какой-либо точки границы. Не умаляяобщности, рассмотрим абсциссу i-й точки границы:I M M = IOB − I BG h.xi xi (2.27)В силу сложной структуры функций, описывающих значения элементовматрицы бинарной маски M, определяемых процедурой синтеза в разделе 2.4.2,аналитического решения для производной найти не удается.
Воспользуемсячисленной аппроксимацией производной по двум точкам с шагом ∆xi:I M I M1=(IOB − I BG M ) h ,xixi xi(2.28)где ∆M - изменение матрицы маски М, соответствующее изменению абсциссы i-йточки границы объекта на величину ∆xi. Это изменение можно вычислитьнесколькими способами.Наиболее простой способ заключается в том, чтобы непосредственновычислить две дискретные бинарные маски для пары векторов координат точек,отличающихся абсциссой одной лишь i-й точки (рисунок 2.8, а). Поскольку интереспредставляет лишь разность этих масок, то данный способ избыточен свычислительной точки зрения.Заметим, что разность бинарных масок для всей фигуры представляет собойразность бинарных масок для двух треугольников, образованных сдвинутой вдоль102оси абсцисс i-й точкой и двумя ее ближайшими соседями (рисунок 2.8, б), чтоформально записывается следующим образом:M = MT ({( xi −1 , yi −1 ),( xi +xx, yi ),( xi +1, yi +1 )}) − MT ({( xi −1, yi −1 ),( xi −, yi ),( xi +1, yi +1 )}) ,22где MT – дискретная маска треугольника.
Тогда алгоритм расчета производнойсводится к вычислению ∆M описанным способом, перемножении с матрицейразности модельных распределений яркости объекта и фона и последующейсверткой результата с h. Данный способ по сути эквивалентен решению прямойзадачи для двух треугольников и значительно эффективнее классическогочисленного дифференцирования, которое потребовало бы полного решенияпрямой задачи. Однако, поскольку в данном случае речь идет о численном, а неаналитическом расчете производной, то следует рассмотреть возможностьснижения объема вычислений за счет ее дальнейшей аппроксимации. На этомоснован третий, быстрый способ вычисления.Быстрое приближенное вычисление производной (2.28) основано на том, чтосоответствующее разностное изображение ∆IM может быть аппроксимированопарой линий с переменной шириной, которая меняется линейно при движениивдоль линии.