Компьютерная Графика и Мультимедиа Сетевой журнал

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

Содержание

1. Введение
2. Деформируемые модели свободной формы
1. Активные контурные модели
2. Деформируемые модели, основанные на сплайнах.
3. Параметрические деформируемые модели.
1. Аналитические параметрические деформируемые модели.
2. Параметрическая деформируемая модель, основанная на прототипе.
4. Заключение
5. Литература

Введение

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

Рисунок 1. Примеры приложений, использующих деформируемые модели.

Деформируемая модель (deformable template model) представляет собой шаблон некоторой формы (для двумерного случая - открытая либо замкнутая кривая, для трехмерного - поверхность). Наложенный на изображение, шаблон деформируется под воздействием различных сил, внутренних (определенных для каждого конкретного шаблона) и внешних (определенных изображением, на которое наложен шаблон) -- модель меняет свою форму, подстраиваясь под входные данные. В результате из шаблона, инициированного в приблизительном местонахождении искомого объекта, получаем явное описание границы объекта. (см.рис.2) Задачи поиска границы объекта при наличии информации о его приблизительном положении широко распространены в области создания естественных интерфейсов человек-компьютер (отслеживание положения руки, чтение по губам, распознавание черт лица), в задачах трэкинга (отслеживания) объектов. (см. рис. 1)

Рисунок 2. Работа контурной модели:
a)       начальное положение - инициация
b)       после 10 итераций
c)       конечное положение - результат

По типу задания шаблона деформируемые модели делятся на параметрически заданные модели (parametric deformation models) и модели свободной формы (free form deformation models). [1] (см.рис.3)

Рисунок 3. Типы деформируемых моделей.

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

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

Изменения деформируемой модели можно описать аналитической функцией, аргументом которой служит текущая геометрическая форма модели, входное изображение играет роль параметра, а значением функции является мера несоответствия модели на текущей стадии деформации искомому объекту на входном изображении. Чем меньше значение функции - тем ближе модель к тому, что требуется найти. В этом случае задача поиска искомого контура может быть переформулирована в задачу оптимизации этой функции, то есть поиска такого набора аргументов, при котором функция при текущих значениях параметра достигает своего оптимального значения. Такая функция в литературе носит название функция энергии (energy). Силы, действующие на деформируемую модель, выражены в функции энергии как комбинация ограничений на форму модели (внутренние силы) и свойств искомого контура (внешние силы). [2]

1. Внутренняя энергия (internal energy) является мерой соответствия геометрической формы деформированного шаблона некоторой идеальной форме искомого объекта. Внутренняя энергия является свойством модели, и не зависит от входных данных
   1. В моделях свободной формы внутренняя энергия соответствуют общим ограничениям на форму шаблона - гладкость и компактность контура.
   2. В аналитически заданных деформируемых моделях внутренняя энергия описывает геометрическую форму и взаимное расположение составных частей шаблона.
   3. В деформируемых моделях, основанных на прототипах, внутренняя энергия оказывает влияние на выбор геометрической формы модели. Например, она может определять штраф за отклонение от ожидаемой формы.
2. Внешняя энергия (external energy) -- мера <похожести> деформированного шаблона на искомый объект. С помощью внешней энергии деформируемая модель взаимодействует с данными, притягивается к искомым контурам на изображении. Внешняя энергия - это мера точности соответствия деформируемой модели входному изображению.

На примере (рис. 4) приведена модель свободной формы. Внутренняя энергия для нее - условие гладкости контура. Внешняя энергия - условие резкого перепада яркости на границе объекта. При разных деформациях модели получаем разные значения для внутренней и внешней энергий.

Рисунок 4. Внутренняя и внешняя энергии.

Деформируемые модели свободной формы

Деформируемые модели свободной формы характеризуются отсутствием строго заданной формы шаблона - вводятся лишь общие ограничения, такие как непрерывность и гладкость контура. Наиболее известным типом деформируемой модели свободной формы является активная контурная модель (active contour model), также в литературе называемый змеей (snake).

Активные контурные модели

Активная контурная модель, или змея - это деформируемая модель, шаблон которой задан в форме параметрической кривой, инициализированный вручную набором контрольных точек, лежащих на открытой или замкнутой кривой на входном изображении. Обозначим массив контольных точек
C = { c(s) } = { (x(s), y(s)), s= 1,...,n }.

Функция энергии активной контурной модели выглядит следующим образом: [3]

где E₁ - внутренняя энергия, а E₂ - внешняя.

Условие непрерывности и гладкости контура можно записать:

Параметр w₂ регулирует жесткость контура. При w₂(s) = 0 контур образует угол в точке (x(s), y(s)) (нарушается условие гладкости). Параметр w₁ регулирует эластичность контура. При w₁(s) = w₂(s) = 0 в точке (x(s), y(s)) происходит разрыв контура (нарушается условие непрерывности). В простейшем случае параметры могут быть одинаковыми для всех точек контура. [7, 8]

Внешняя энергия выглядит следующим образом:

где P(c(s)) - потенциальное поле силы, ассоциированной с входным изображением. Каждая точка входного изображения обладает силой, притягивающей или отталкивающей деформируемую модель. Например, в случае когда с помощью активной контурной модели производится поиск краев (резких перепадов яркости) изображения, потенциальное поле силы имеет такую форму:

Здесь I - яркость изображения.

Для решения задачи минимизации функции энергии применяется метод ветвей и границ. Алгоритм циклический. Для всех контрольных точек c(s), s=1,...,n вычисляем E₁, E₂ и E во всех точках некоторой окрестности текущей контрольной точки c(i), 1 ≤ i ≤ n, после чего выбираем ту точку этой окрестности, которая минимизирует функцию энергии E - эта точка становится контрольной точкой c(s) на следующем шаге (см. рис.5). Для полученного набора контрольных точек проводим ту же операцию. Алгоритм заканчивает свою работу когда на очередном проходе ни одна контрольная точка не поменяла своего положения.

Рисунок 5. Активные контурные модели: метод ветвей и границ.

Активные контурные модели являются эффективным, но "близоруким" средством - метод ветвей и границ чувствителен к присутствию локального оптимума, может принять локальный минимум за финальный результат. Поэтому активные контурные модели чувствительны к шуму на входных изображениях (шум добавляет локальные перепады яркости на изображение) и к инициализации (при плохой инициализации между инициированным контуром и желаемым результатом может оказаться локальный минимум). Для достижения стабильности и точности необходимо проведение подготовительных мер с входным изображением - например размытие для устранения шума. Также можно достичь большей стабильности используя другие методы решения задачи оптимизации - например, динамическое программирование [2, 4].

Деформируемые модели, основанные на сплайнах.

Другим примером деформируемой модели свободной формы являются деформируемые модели, основанные на сплайнах.

Модель, основанная на сплайнах, обладает более четко определенной структурой чем змея. Шаблон основанной на сплайнах модели выражается линейной комбинацией набора базисных функций, и его форма определяется коэффициентами этих функций. В качестве базиса сплайна может быть использован как базис В-сплайна, так и тригонометрический базис, и вейвлеты. [4]

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

Параметрические деформируемые модели.

Параметрическая деформируемая модель - это модель формы некоторого класса, представленная параметрически. [5] Под классом (типом, видом) формы подразумевается априорное знание о структурных свойствах класса объектов. На (см. рис. 6) представлен класс формы рыбы. Рыба может иметь разные пропорции, размер и ориентацию. Рыбы одного вида имеют идентичную форму, рыбы разных видов - похожие формы, а животные имеют совершенно иную форму. При деформации параметрической модели рыбы мы никогда не сможем получить форму кота.

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

Рисунок 6. Класс формы на примере формы рыбы

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

Аналитические параметрические деформируемые модели.

Представляя класс формы в виде набора параметрически заданных кривых, получим аналитическую параметрическую деформируемую модель, основанную на форме (Analytical Form-based Parametric Deformable Models).

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

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

Параметрическая деформируемая модель, основанная на прототипе.

Альтернативный подход параметризации деформируемой модели состоит в задании прототипа формы (характерной геометрической структуры) и набора параметрических деформаций, которые могут изменять прототип. На наборе трансформаций может быть определена вероятность возникновения каждой конкретной трансформации. Такие модели называют параметрическую деформируемую модель, основанную на прототипе (Prototype-based Parametric Deformable Models). При такой параметризации все объекты одного класса имеют схожую структуру, но у каждого возможны индивидуальные отклонения от <стандартной> формы. [6]

Прототипный шаблон выбирается на основе априорного знания объекта интереса. Это знание может быть получено либо в результате обработки изображения более высокого уровня либо получено путем тренировки. [1]

Заключение

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

Литература

1. 2-D Deformable Template Models: A Review (URL: http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/ZHONG1/zhong.html)
2. Active Contour Models & Active Shape Models (Snakes & Smart Snakes) (URL: http://www.s2.chalmers.se/undergraduate/courses/ess060/PDFdocuments/ForScreen/Notes/ACM_ASM.pdf)
3. Blair T. Mackiewich. Intracranial boundary detection and radio frequency correction in magnetic resonance images. M.Sc. thesis, Simon Fraser University, August 1995. (URL: http://www.cs.sfu.ca/~stella/papers/blairthesis/main/main.html)
4. Vedad Hadziavdic. A Comparative Study of Active Contour Models for Boundary Detection in Brain Images. Diploma Project of Faculty for Mathematical and Natural Sciences University of Tromso (URL: http://www.uib.no/med/avd/miapr/arvid/vedad_diploma.pdf)
5. Ananda M. Mondal. Parametric Deformable Models - A Review. Computational Vision and Perseption Seminar, University of South Carolina. February 3, 2003. (URL: http://www.cse.sc.edu/~kubota/Seminar/Handouts/DeformableModels.ppt)
6. Anil K. Jain, Fellow, IEEE, Yu Zhong, and Sridhar Lakshmanan. Object Matching Using Deformable Templates. IEEE Transactions on Pattern Analisys And Machine Intelligence, vol.18, no. 3, March 1996 (URL: http://www.cse.msu.edu/prip/Files/ deformableTemplateMatching.pdf)
7. Gilson A. Giraldi, Antonio A. F. Oliveira. SnakeModels. Tutorial. (URL: http://virtual01.lncc.br/~giraldi/minicurso/snakes.pdf.gz)
8. Bob Sumner. Active Contour Models: Snakes. (URL: http://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Sumner/discussions/snakes.html)
9. CVOnline: Active Shape Models (URL: http://homepages.inf.ed.ac.uk/cgi/rbf/CVONLINE/entries.pl?TAG752)

Дополнительная информация

Ссылка: 

Анна Дегтярева. Деформируемые модели. Компьютерная графика и мультимедиа. Выпуск №3(2)/2005. http://cgm.computergraphics.ru/content/view/75

Выпуск: 

Выпуск №3(2)/2005