Диссертация (1143951), страница 18

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

Текст из файла (страница 18)

Диапазон изменения ширины линии составляет [0..cos(α)∆xi], где α –угол ориентации линии (рисунок 2.8, в).103а)б)в)+∆+α∆∆2ℎ++г)∆ ∗ Рисунок 2.8 Вычисление производной по параметрам границы: прямое иоптимизированное дифференцирование по двум точкам (а, б), быстроеприближенное вычисление (в), результат вычисления (г)При малых величинах шага дифференцирования ∆xi (по сравнению с ширинойимпульсного отклика h), соответствующее изображение каждой из составляющихего линий может быть аппроксимировано суммой множества изображенийимпульсного отклика, центры которых расположены вдоль линии, а яркостьпропорциональна ширине линии в данной точке. Дополнительным множителемяркости является разность яркости объекта и фона в данной точке (это следует извыражения для расчета производной 2.27).Посколькуцентрыизображенийимпульсногооткликамогутбытьрасположены в любой части пикселя моделируемого изображения, а не только вего центре, необходим способ расчета изображения импульсного отклика сосмещением менее пикселя.

Точный расчет смещенного изображения импульсногоотклика может быть получен, например, с помощью ранее рассмотренного методаизменения фазы фурье-образа.Рассмотримприближенноевычислениесубпиксельно-смещенногоизображения импульсного отклика с использованием билинейной интерполяции.104Тогда выражение для вычисления субпиксельно-смещенного изображенияимпульсного отклика является взвешенной суммой 4-х изображений импульсногоотклика с относительным смещением в один пиксель:h r [i, j ] = (1 − xs )(1 − y s ) h[i, j ] + y s (1 − xs ) h[i, j + 1] + xs (1 − y s ) h[i + 1, j ] + y s xs h[i + 1, j + 1],(2.29)где (xs, ys) – субпиксельное смещение изображения (0≤xs<1, 0≤ys<1).Алгоритм приближенного вычисления разностного изображения дляпроизводной с учетом предложенных аппроксимаций выглядит следующимобразом:1. Инициализировать нулями матрицу разностного изображения ∆IM.2.

Разбить отрезок между точками (Pi-1, Pi) на отрезки с заданным шагом Δl.3. Для каждой точки разбиения:3.1. Определить координату точки разбиения (x΄, y΄), вычислить яркостныйкоэффициент:C = sin( )где...( x − xi −1 ) 2 + ( y  − yi −1 ) 2( xi − xi −1 ) 2 + ( yi − yi −1 ) 2(IOB[  x ,  y ] − I BG [  x ,  y ]) ,- целая часть числа.3.2. Добавить к ∆IM матрицу изображения смещенного импульсного откликаhr, вычисленную по (2.29) и перемноженную с яркостным коэффициентом C.4.

Повторить шаги 2-3 для точек (Pi, Pi+1).Посформированномуврезультатеработыалгоритмаразностномуизображению ∆IM с помощью (2.28) вычисляется искомая производная.Производные по параметрам yi вычисляются аналогичным образом с заменой sinна cos.Оптимизационная стратегия решения обратной задачи2.4.3.В предыдущих разделах описано вычислительно-эффективное решениепроблемы моделирования изображения (прямая задача), а также предложеныалгоритмы вычисления вектора градиента оптимизируемого функционала E задачи(2.25).Такимобразом,воспользовавшисьполученнымирешениями,105оптимизационная задача оценивания границ (2.25) может быть решенаградиентными методами численной оптимизации.Как известно, градиентные методы оптимизации отличаются порядкомпроизводной оптимизируемого функционала. К методам первого порядкаотносятся, например, наискорейший спуск, покоординатный спуск и методсопряженных градиентов (СГ).

Классическими методами второго порядкаявляются методы Ньютона и Ньютона-Рафсона. С учетом потенциально большойразмерности задачи (103..105 параметров), непосредственное применение методоввторого порядка затруднено в связи с необходимостью вычисления матрицы Гесседля оптимизируемого функционала.

Вместо этого могут быть применены методы,в которых вычисление матрицы Гессе заменено каким-либо приближением – т.н.квазиньютоновские методы. К ним относится, например, метод БройденаФлетчера-Гольдфарба-Шанно (БФГШ).Посколькуисследованиеэффективностивсехуказанныхметодовоптимизации представляется для решения задачи оценки границ представляетсязатруднительным, рассмотрим лишь по одному представителю методов первогопорядка и квазиньютоновских, а именно методы СГ и БФГШ.Рассмотрим работу выбранных методов оптимизации для оценки границ напримере решения простой модельной задачи. В качестве простого тест-объектавыступает многоугольник равномерной яркости, фон отсутствует (рисунок 2.9).Вкачественачальныйрешенийвыбранодвавариантаграницы,отличающиеся количеством точек.

В первом варианте начального решенияколичество точек точно соответствует измеряемому многоугольнику (7 точек) и,такимобразом,имитируетситуацию,прикоторыйаприорноизвестнаприблизительная форма объекта. Во втором варианте начального решения формаобъекта предполагается неизвестной, и точки границы расположены с шагом в 1пиксель (146 точек). Начальное решение задано со смещением в несколькопикселей от истинного значения, что имитирует возможные ошибки при работеприближенных методов оценивания границ. Параметры яркости исключены из106процесса оптимизации для упрощения демонстрации работы метода (оптимизацияпри неизвестных параметрах яркости рассмотрена ниже).Работа методов проиллюстрирована на рисунке 2.9 эволюцией решения впроцессе оптимизации в зависимости от номера итерации N метода оптимизации(на примере метода СГ), а также зависимостью значения минимизируемогофункционала от времени оптимизации (рисунок 2.10, оба метода). Приведенырезультаты для обоих вариантов начального решения.Начальное решениеN=1N=5N=20а)б)x1x1x2x10x20x80в)г)x1x2Рисунок 2.9 Эволюция решения в процессе оптимизации (а, в), разностьнаблюдаемого и моделируемого изображения (б, г).

Количестве точекграницы: 7 (а, б), 146 (в, г)Контраст разностных изображений на рисунке 2.9 усилен, абсолютныезначения усиления показаны рядом с изображениями. Значение функционала на107графиках нормировано на количество пикселей изображения. Яркость модельногообъекта – 100 единиц.Полученное двумя методами оптимизации решение практически идентично(рисунок 2.10), однако для достижения одного и того же значения функционаламетоду СГ требуется до двух раз меньше времени, что особенно заметно для задачс большим числом точек границы (рисунок 2.10, б). Таким образом, использованиеметода СГ представляется более выигрышным по сравнению с БФГШ с учетом10Значение функционалаЗначение функционалавремени решения задачи.10,10,010,00101234510СГБФГШ10,10,010,0010246Время, сВремя, са)б)81012Рисунок 2.10 Эволюция функционала в процессе оптимизации при разномколичестве точек границы: 7 (а), 146 (б)Стратегия оптимизации для задач с неизвестной яркостью. Врассмотренной модельной задаче параметры яркости объекта предполагалисьизвестными.

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

В результате декомпозиции вместо одноуровневой оптимизационнойзадачи (2.25) предлагается сформулировать двухуровневую задачу. При этомпараметры границы следует вынести на верхний уровень, а параметры яркости – нанижний. Формально такая задача может быть представлена следующим образом:ˆ ,Yˆ ,Kˆ ,Kˆ ) = arg min  arg min ( E )  : E = 1  I [ x, y ]2 ,(XOBBGD K ,K2 ( x . y )X ,Y OB BGID = IMX ,Y ,K OB ,K BG(2.30)− IE .Несмотря на кажущееся усложнение задачи, при такой декомпозиции удаетсядостичь качественного решения значительно быстрее по сравнению с исходной,одноуровневой формулировкой.Для демонстрации проблемы рассмотрена та же модельная задача, что и нарисунке 2.9, но яркость теперь рассматривается как неизвестная величина.

Нарисунке 2.11 (а) приведена зависимость значения функционала от временирешения задачи для случая с неизвестной, но равномерной яркостью. На этойзависимости видно, что при одноуровневой оптимизации формирование решениятакого же качества, как и с известной яркостью требует в два раза больше времени.При двухуровневой оптимизации по (2.30) сравнимое по качеству решение требуетна 25% меньше времени.10000Фикс. яркость1000Перем. яркость, 1 уровень100Перем.

яркость, 2 уровняЗначение функционалаЗначение функционала100001010,10,010,0011 уровень10002 уровня1001010,10246805T, са)1015T, сб)Рисунок 2.11 Сравнение одноуровневой и двухуровневой оптимизации в задаче снеизвестной яркостью: равномерная модель (а), сверточная модель (б)109Применение двухуровневой оптимизации особенно актуально для сложноймодели яркости (например, сверточной). На рисунке 2.11 (б) приведеназависимость функционала от времени решения задачи для сверточной моделияркости с Гауссовой базисной функцией (модель 2.12, σOB=σBG=20 пикселей).Размерность задачи в данном случае возрастает с 14 до 20014 параметров (7 точекграницы+двематрицыпараметровяркостиразмерностью100x100).Одноуровневая оптимизация в таком случае является существенно менееэффективной по сравнению с двухуровневой.На рисунке 2.12 приведены траектории ошибок трех параметров задачи(отклонения абсцисс трех точек от истинных значений) для сверточной моделияркости.

Характеристики

Список файлов диссертации