Диссертация (1143951), страница 16
Текст из файла (страница 16)
субпиксельной дискретизации не требуется.Несмотря на внешнюю схожесть предлагаемой здесь дискретной моделиизображения (2.21) и описанной в разделе 2.2 непрерывной модели (2.7), онисущественно отличаются друг от друга. Главное отличие заключается в том, что внепрерывной модели бинарная маска (функция M(x, y)) принимает лишь двазначения (0 или 1), а в предлагаемой здесь дискретной модели элементы матрицыM являются непрерывными функциями от параметров границы объекта. Такимобразом, основной задачей предлагаемого алгоритма синтеза в фурье-области90является расчет фурье-образа дискретной маски объекта (FМ). Как будет показанодалее, этот расчет может быть выполнен аналитически, следовательно, с высокойточностью и вычислительно эффективно.Следует отметить, что предлагаемая модель дискретного изображения (2.21)адекватна лишь в случае выполнения условия теоремы Котельникова о частотедискретизации сигнала.
В том случае, если фактическая частота дискретизациирегистрируемого изображения ниже удвоенной предельной пространственнойчастоты изображения, размерность синтезируемого изображения I предлагаетсякратно увеличить до той, которая будет соответствовать выполнению условиятеоремы, а в процессе решения обратной задачи учитывать лишь те отсчетысинтезированного изображения, которые соответствуют зарегистрированным.Аналогичным образом может быть учтено влияние других факторов, связанных сдискретизацией изображения: массивы светофильтров в мультиспектральныхсистемах, биннинга пикселей или неравномерной по полю частоты дискретизациив системах выборочного считывания растра изображений.В предлагаемом далее вычислительно-эффективном решении границаобъекта аппроксимируется кусочно-линейным контуром.
Обозначим множествоузловых точек границы {Pi=(xi, yi), i=1..k}, где (xi, yi) – декартовы координаты точек.Ограниченнуютакимобразомобластьможноразбитьнамножествонепересекающихся треугольников. Теперь, если найти аналитический способрасчета двумерного комплексного фурье-образа для произвольного треугольника,то в силу линейности преобразования, фурье-образ всей области является суммойфурье-образов отдельных треугольников (рисунок 2.6).911. ТриангуляцияГраницаобъекта2. Расчет фурье-образаМножествотреугольников5.
Свертка с имп. откликом3. Обратноепреобразование ФурьеОграниченныйЧастотно-ограниченноефурье-образ маскиизображение маски4. Перемножение сраспределениями яркостиРаспределения яркости объекта и фонаСинтезированноеизображениеРисунок 2.6 Основные этапы вычислительно-эффективного синтеза изображенияв фурье-областиАналитический расчет двумерного фурье-образа бинарной маскитреугольника.ВсоответствиисопределениемпреобразованияФурье,комплексный коэффициент двумерного фурье-образа для пространственнойчастоты (ωx, ωy) задается следующим образом:FM (x , y ) =+ + M ( x, y ) exp(−i[ x + xyy ])dxdy ,(2.22)− −где M(x, y) – бинарная маска объекта. Для треугольника, заданного точками (ABC):1,( x, y ) ( ABC )M ( x, y ) = .0,( x, y ) ( ABC )Надекартовойплоскости(x, y)множительexp(-i[ωxx+ωyy])задаетгармоническое колебание с частотой ω и углом поворота α относительно началакоординат (рисунок 2.7): = x 2 + y 2 , = arctan y . x (2.23)92y΄yAA΄BℎCkB΄D΄xℎC΄cadbx΄Рисунок 2.7 К расчету фурье-образа бинарной маски треугольникаПоскольку функция M принимает только лишь значения 0 или 1, интеграл(2.22) можно переписать следующим образом:FM (x , y ) =( x , y )( ABC )exp( −i x x + y y )dxdy.Теперь повернем систему координат на угол α.
Обозначим треугольник (ABC)в повернутой системе координат (A΄B΄C΄). В повернутой системе координатпоследнее выражение эквивалентно:FM (x , y ) =exp( −i x)dxdy .( x, y )( ABC )Определим на отрезке (A΄C΄) такую точку (D΄), что прямая (B΄D΄) параллельнаоси абсцисс в повернутой системе координат. Теперь представим искомые фурьекоэффициенты в виде суммы фурье-коэффициентов треугольников (A΄B΄D΄) и(C΄B΄D΄):FM (x , y ) = F( ABD) (x , y ) + F( C BD) (x , y ).Обозначим высоту треугольника (A΄B΄D΄) – hA, а высоту треугольника(C΄B΄D΄) – hC. Тогда, исходя из геометрического смысла интеграла, фурьекоэффициенты каждого из этих треугольников определяются выражениями:93F( ABD) (x , y ) =hAb−k( b −a )hA exp( −i x)dxdk ,0 d + k ( a −d )hAF( C BD) (x , y ) =hCb−k( b−c )hC exp( −i x)dxdk ,0 d − k ( d −c )hCгде (a, b, c, d) – значения проекции точек (A΄B΄C΄D΄) на ось абсцисс в повернутойсистеме координат.Решая эти интегралы, получим аналитическое решение в элементарныхфункциях:F( ABD) hA ( a − b exp( −id ) + b − d exp( −ia ) + d − a exp( −ib) ) 2, ( d − a )( a − b) 0 2 ( d − a )( a − b) hA ( exp( −id ) − exp( −ib) + d − b i exp( −ib) ) 2=, ( d − b) 0,2(d−b) hA ( b − d ) 2, ( d − b) = 02F( C BD) hС ( с − b exp( −id ) + b − d exp( −iс ) + d − с exp( −ib) ) 2, ( d − c )( c − b) 0 2 ( d − с)( с − b) hC ( exp( −id ) − exp( −ib) + d − b i exp( −ib) ) 2=, ( d − b) 0. 2 ( d − b) hC (b − d ) 2, ( d − b) = 02(2.24)Сформулируем алгоритм расчета фурье-образа треугольной области.Входные данные алгоритма – вершины треугольника Pi=(xi, yi), i=(1, 2, 3).1.
Перевести точки Pi в полярные координаты (φi, ri).2. Для каждой пары частот (ωx, ωy):2.1.Вычислить угол поворота α и частоту колебания ω по (2.23).2.2.Вычислить координаты точек Pi΄=(xi΄, yi΄) в повернутой системекоординат: xi = ri cos( i + ), i = (1,2,3) yi = ri sin( i + )2.3.Упорядочить точки Pi΄ по возрастанию yi΄.942.4.Вычислить абсциссу точки пересечения прямой, образованной точкамиP1΄ и P3΄, и прямой (y΄=y2΄):x = x3 + (x1 − x3 )y 3 − y 2y 3 − y12.5.Если x΄> x2΄, обменять значения x2΄ и x΄.2.6.Вычислитьпарукоэффициентовфурье-образапо(2.24)приa=x1΄, b=x2΄, c=x3΄, d=x΄, hA= y2΄- y1΄, hC= y3΄- y2΄.2.7.Просуммировать вычисленные коэффициенты, записать результат всоответствующую ячейку матрицы фурье-образа.Определение полосы частот для расчета фурье-образа маски. Полосапространственныхчастотдлярасчетафурье-образамаскиопределяетсядифракционным ограничением моделируемой оптической системы и частотнымихарактеристиками распределений яркости объекта и фона.
Полоса частотмоделируемого изображения ограничена полосой частот импульсного откликасистемы h и, вследствие дифракционного предела оптической системы, являетсяконечной величиной. Соответственно, в случае равномерной яркости расчет такжеследует проводить в пределах той же дифракционно-ограниченной полосы частот(рисунок 2.4).При неравномерной яркости объекта или фона полоса частот определяется нетолько дифракционным ограничением оптической системы, но и частотнымихарактеристиками распределений яркости объекта и фона (IBG и IOB).
Применивтеорему о свертке к модели (2.7), можно заметить, что в фурье-области сначалаосуществляется свертка функций бинарной маски и распределений яркости, а затемперемножение результата с ограниченным с фурье-образом импульсного отклика.Следовательно, на результирующий фурье-образ в пределах дифракционноограниченной полосы частот оказывают влияние и те участки частотного спектра,которыенаходятсявнеэтойполосы.Аналогичныйэффектсмещенияпространственно-частотного спектра объекта в полосу частот пропусканияоптическойсистемыприменяется,например,вметодахоптическогосверхразрешения на основе структурированного освещения [79]. Таким образом,95при расчете фурье-образа бинарной маски в случае неравномерной яркости объектаили фона следует расширить полосу частот на величину, равную наибольшей изпредельных частот функций, описывающих распределения яркости, а сами этифункции следует строить таким образом, чтобы их частотный спектр был строгоограничен.
На практике частотный спектр распределений яркости может бытьнеограничен, в таком случае следует ограничиться лишь той частью диапазоначастот, которая является существенной с точки зрения решаемой задачи.Длярассматриваемогоалгоритмасинтезаформаобъектазадаетсяограничивающим многоугольником. Чтобы выполнить синтез, необходимовыполнитьдекомпозициюэтогомногоугольникананепересекающиесятреугольники (задача триангуляции). Для выпуклых многоугольников задачарешается тривиально, интерес представляют невыпуклые случаи. Известнонесколько методов решения этой задачи, отличающихся вычислительнойсложностью [94].
Метод полного перебора имеет сложность O(n4), где n – числовершин. Более эффективным является т.н. «ушной» метод [95], заключающийся витерационном отделении вершин многоугольника, составляющих треугольниквместе с двумя соседними. Сложность этого метода O(n2). Наконец, известен методмонотонных многоугольников со сложностью O(nlog2n). Суть метода заключаетсяв разбиении многоугольника на т.н. y- или x-монотонные многоугольники –многоугольники, имеющие не более двух пересечений с любой прямой,перпендикулярнойосиабсциссилиординатсоответственно;такиемногоугольники далее легко триангулируются.Оценка объема вычислений. В отличие от субпиксельных методов, объемвычислений для данного метода определяется прежде всего числом точек границы(n) и не зависит от дискретности локализации элементов границы.
Также дляоценки необходимо определить размерность изображения (Ky×Kx) и количествокоэффициентов фурье-образа (KF).Вне зависимости от метода триангуляции, без создания дополнительныхвершин точное число результирующих треугольников составляет (n-2), но с цельюупрощения расчета, далее это количество предполагается равным n. Тогда для96синтеза потребуется выполнить nKF итераций алгоритма расчета коэффициентовфурье-образа треугольника, каждая из которых состоит из:Шаг 2.2 – 3 пары cos/sin, 6 умножений, 3 операции сложенияШаг 2.3 – 2 операции сравненияШаг 2.4 – 1 умножение, 1 деление, 4 сложенияШаг 2.5 – 1 сравнениеШаг 2.6 – 4 пары cos/sin, 18 умножений, 2 деления, 6 сложенийШаг 2.7 – 4 сложенияШаги 1 и 2.1 алгоритма исключены из расчета объема вычислений, т.к.