Модель активного контура

Модель активного контура , также называемая змеями , представляет собой основу компьютерного зрения, предложенную Майклом Кассом , Эндрю Уиткиным и Деметри Терзопулосом. для выделения контура объекта из возможно зашумленного 2D- изображения . Модель змей популярна в компьютерном зрении, а змеи широко используются в таких приложениях, как отслеживание объектов, распознавание форм, сегментация , обнаружение краев и сопоставление стереоизображений.

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

Змеи – активные деформируемые модели

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

Мотивация

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

По сравнению с классическими методами извлечения признаков змеи имеют ряд преимуществ:

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

Ключевые недостатки традиционных змей:

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

Энергетическая формулировка

Простая эластичная змея определяется набором из n точек. $\mathbf {v} _{i}$ для $i=0,\ldots ,n-1$, член внутренней упругой энергии $E_{\text{internal}}$и внешний энергетический член на основе ребра $E_{\text{external}}$. Целью внутренней энергии является контроль деформаций, производимых змеей, а целью внешней энергии является контроль соответствия контура изображению. Внешняя энергия обычно представляет собой комбинацию сил, обусловленных самим изображением. $E_{\text{image}}$ и силы ограничения, введенные пользователем $E_{\text{con}}$

Энергетическая функция змеи представляет собой сумму ее внешней энергии и внутренней энергии, или

$E_{\text{snake}}^{*}=\int \limits _{0}^{1}E_{\text{snake}}(\mathbf {v} (s))\,ds=\int \limits _{0}^{1}(E_{\text{internal}}(\mathbf {v} (s))+E_{\text{image}}(\mathbf {v} (s))+E_{\text{con}}(\mathbf {v} (s)))\,ds$

Внутренняя энергия

Внутренняя энергия змеи складывается из непрерывности контура $E_{\text{cont}}$ и плавность контура $E_{\text{curv}}$.

$E_{\text{internal}}=E_{\text{cont}}+E_{\text{curv}}$

Это можно расширить как

$E_{\text{internal}}={\frac {1}{2}}(\alpha \,\!(s)\left|\mathbf {v} _{s}(s)\right\vert ^{2})+{\frac {1}{2}}(\beta \,\!(s)\left|\mathbf {v} _{ss}(s)\right\vert ^{2})={\frac {1}{2}}{\bigg (}\alpha \,\!(s)\left\|{\frac {d{\bar {v}}}{ds}}(s)\right\Vert ^{2}+\beta \,\!(s)\left\|{\frac {d^{2}{\bar {v}}}{ds^{2}}}(s)\right\Vert ^{2}{\bigg )}$

где $\alpha (s)$ и $\beta (s)$ определяемые пользователем веса; они контролируют чувствительность функции внутренней энергии к величине растяжения и кривизны змеи соответственно и тем самым контролируют количество ограничений на форму змеи.

На практике большой вес $\alpha (s)$ поскольку член непрерывности наказывает изменения в расстояниях между точками контура. Большой вес $\beta (s)$ поскольку термин гладкости наказывает колебания контура и заставляет контур действовать как тонкая пластина.

Энергия изображения

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

Для изображения $I(x,y)$, линии, края и окончания, присутствующие на изображении, общая формулировка энергии, обусловленной изображением, такова:

$E_{\text{image}}=w_{\text{line}}E_{\text{line}}+w_{\text{edge}}E_{\text{edge}}+w_{\text{term}}E_{\text{term}},$

где $w_{\text{line}}$, $w_{\text{edge}}$, $w_{\text{term}}$ являются весами этих существенных особенностей. Более высокие веса указывают на то, что значимая особенность будет иметь больший вклад в силу изображения.

Линейный функционал

Функционал линии – это интенсивность изображения, которую можно представить как

$E_{\text{line}}=I(x,y)$

Знак $w_{\text{line}}$ определит, будет ли линия притягиваться к темным или светлым линиям.

На изображении можно использовать некоторое сглаживание или шумоподавление, после чего функционал линии будет выглядеть как

$E_{\text{line}}=\operatorname {filter} (I(x,y))$

Краевой функционал

Краевой функционал основан на градиенте изображения. Одной из реализаций этого является

$E_{\text{edge}}=-\left|\nabla I(x,y)\right\vert ^{2}.$

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

$E_{\text{edge}}=-\left|G_{\sigma }\cdot \nabla ^{2}I\right\vert ^{2}$

где $G_{\sigma }$ является гауссовой функцией со стандартным отклонением $\sigma$. Минимумы этой функции приходятся на пересечения нуля точки $G_{\sigma }\,\nabla ^{2}I$ которые определяют края согласно теории Марра – Хилдрета .

Функционал завершения

Кривизну линий уровня на слегка сглаженном изображении можно использовать для обнаружения углов и границ изображения. Используя этот метод, пусть $C(x,y)$ быть изображением, сглаженным

$C(x,y)=G_{\sigma }\cdot I(x,y)$

с углом градиента

$\theta =\arctan \left({\frac {C_{y}}{C_{x}}}\right),$

единичные векторы вдоль направления градиента

$\mathbf {n} =(\cos \theta ,\sin \theta ),$

и единичные векторы, перпендикулярные направлению градиента

$\mathbf {n} _{\perp }=(-\sin \theta ,\cos \theta ).$

Функционал терминации энергии можно представить как

$E_{\text{term}}={\partial \theta \over \partial n_{\perp }}={\partial ^{2}C/\partial n_{\perp }^{2} \over \partial C/\partial n}={{C_{yy}C_{x}^{2}-2C_{xy}C_{x}C_{y}+C_{xx}C_{y}^{2}} \over (C_{x}^{2}+C_{y}^{2})^{3/2}}$

Энергия ограничения

Некоторые системы, включая оригинальную реализацию змей, позволяли пользователю управлять змеями не только при их первоначальном размещении, но и с точки зрения их энергии. Такая энергия ограничения $E_{con}$ может использоваться для интерактивного направления змей к определенным объектам или от них.

Оптимизация посредством градиентного спуска

Учитывая начальное предположение о змее, энергетическая функция змеи итеративно минимизируется. Минимизация градиентного спуска — одна из простейших оптимизаций, которую можно использовать для минимизации энергии змеи. Каждая итерация занимает один шаг в отрицательном градиенте точки с контролируемым размером шага. $\gamma$ найти локальный минимум. Эту минимизацию градиентного спуска можно реализовать как

${\bar {v}}_{i}\leftarrow {\bar {v}}_{i}+F_{\text{snake}}({\bar {v}}_{i})$

Где $F_{\text{snake}}({\bar {v}}_{i})$ — это сила, действующая на змею, которая определяется отрицательным градиентом энергетического поля.

$F_{\text{snake}}({\bar {v}}_{i})=-\nabla E_{\text{snake}}({\bar {v}}_{i})=-{\Bigg (}w_{\text{internal}}\,\nabla E_{\text{internal}}({\bar {v}}_{i})+w_{\text{external}}\,\nabla E_{\text{external}}({\bar {v}}_{i}){\Bigg )}$

Предполагая веса $\alpha (s)$ и $\beta (s)$ постоянны по отношению к $s$, этот итерационный метод можно упростить до

${\bar {v}}_{i}\leftarrow {\bar {v}}_{i}-\gamma {\Bigg \{}w_{\text{internal}}{\bigg [}\alpha {\frac {\partial ^{2}{\bar {v}}}{\partial s^{2}}}({\bar {v}}_{i})+\beta {\frac {\partial ^{4}{\bar {v}}}{\partial s^{4}}}({\bar {v}}_{i}){\bigg ]}+\nabla E_{\text{ext}}({\bar {v}}_{i}){\Bigg \}}$

Дискретное приближение

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

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

$E_{\text{snake}}^{*}\approx \sum _{1}^{n}E_{\text{snake}}({\bar {v}}_{i})$

Следовательно, силы змеи можно аппроксимировать как

$F_{\text{snake}}^{*}\approx -\sum _{i=1}^{n}\nabla E_{\text{snake}}({\bar {v}}_{i}).$

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

Численная нестабильность из-за дискретного времени

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

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

Альтернативно, силы изображения можно нормализовать для каждого шага так, чтобы силы изображения обновляли змею только на один пиксель. Это можно сформулировать как

$F_{\text{image}}=-k{\frac {\nabla E_{\text{image}}}{\|\nabla E_{\text{image}}\|}}$

где $\tau k$ находится рядом со значением размера пикселя. Это позволяет избежать проблемы доминирования внутренней энергии, возникающей при настройке шага по времени.

Численная нестабильность из-за дискретного пространства

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

Некоторые варианты змей

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

Модель змеи GVF

Модель змеи градиентного векторного потока (GVF) решает две проблемы со змеями:

• плохая производительность сходимости для вогнутых границ
• плохая производительность сходимости, когда змея инициализируется далеко от минимума

В 2D векторное поле GVF $F_{\text{GVF}}$ минимизирует энергетический функционал

$E_{\text{GVF}}=\iint \mu (u_{x}^{2}+u_{y}^{2}+v_{x}^{2}+v_{y}^{2})+|\nabla f|^{2}|\mathbf {v} -\nabla f|^{2}\,dx\,dy$

где $\mu$ — управляемый сглаживающий член. Это можно решить, решив уравнения Эйлера

$\mu \,\nabla ^{2}u-{\Bigg (}u-{\frac {\partial }{\partial x}}F_{\text{ext}}{\Bigg )}{\Bigg (}{\frac {\partial }{\partial x}}F_{\text{ext}}(x,y)^{2}+{\frac {\partial }{\partial y}}F_{\text{ext}}(x,y)^{2}{\Bigg )}=0$

$\mu \,\nabla ^{2}v-{\Bigg (}v-{\frac {\partial }{\partial y}}F_{\text{ext}}{\Bigg )}{\Bigg (}{\frac {\partial }{\partial x}}F_{\text{ext}}(x,y)^{2}+{\frac {\partial }{\partial y}}F_{\text{ext}}(x,y)^{2}{\Bigg )}=0$

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

$u_{i+1}=u_{i}+\mu \,\nabla ^{2}u_{i}-{\Bigg (}u_{i}-{\frac {\partial }{\partial x}}F_{\text{ext}}{\Bigg )}{\Bigg (}{\frac {\partial }{\partial x}}F_{\text{ext}}(x,y)^{2}+{\frac {\partial }{\partial y}}F_{\text{ext}}(x,y)^{2}{\Bigg )}$

$v_{i+1}=v_{i}+\mu \,\nabla ^{2}v_{i}-{\Bigg (}v_{i}-{\frac {\partial }{\partial y}}F_{\text{ext}}{\Bigg )}{\Bigg (}{\frac {\partial }{\partial x}}F_{\text{ext}}(x,y)^{2}+{\frac {\partial }{\partial y}}F_{\text{ext}}(x,y)^{2}{\Bigg )}$

Этот результат заменяет внешнюю силу по умолчанию.

$F_{\text{ext}}^{*}=F_{\text{GVF}}$

Основная проблема с использованием GVF — это сглаживающий фактор. $\mu$ вызывает закругление краев контура. Снижение стоимости $\mu$ уменьшает округление, но ослабляет степень сглаживания.

Модель воздушного шара

Модель воздушного шара решает эти проблемы с помощью модели активного контура по умолчанию:

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

Модель воздушного шара вводит член инфляции в силы, действующие на змею.

$F_{\text{inflation}}=k_{1}{\vec {n}}(s)$

где ${\vec {n}}(s)$ - нормальный унитарный вектор кривой в точке $v(s)$ и $k_{1}$ это величина силы. $k_{1}$ должен иметь ту же величину, что и коэффициент нормализации изображения $k$ и быть меньше по стоимости, чем $k$ чтобы позволить силам на краях изображения преодолеть силу инфляции.

При использовании баллонной модели возникают три проблемы:

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

Модель диффузных змей

Модель диффузной змеи касается чувствительности змей к шуму, беспорядку и окклюзии. Он реализует модификацию функционала Мамфорда-Шаха и его мультипликационный предел и включает в себя статистические знания о форме. Функционал энергии изображения по умолчанию $E_{\text{image}}$ заменяется на

$E_{\text{image}}^{*}=E_{i}+\alpha E_{c}$

где $E_{i}$ основан на модифицированном функционале Мамфорда – Шаха

$E[J,B]={\frac {1}{2}}\int _{D}(I({\vec {x}})-J({\vec {x}}))^{2}\,d{\vec {x}}+\lambda {\frac {1}{2}}\int _{D/B}{\vec {\nabla }}J({\vec {x}})\cdot {\vec {\nabla }}J({\vec {x}})\,d{\vec {x}}+\nu \int _{0}^{1}{\Bigg (}{\frac {d}{ds}}B(s){\Bigg )}^{2}\,ds$

где $J({\vec {x}})$ — кусочно-гладкая модель изображения $I({\vec {x}})$ домена $D$. Границы $B(s)$ определяются как

$B(s)=\sum _{n=1}^{N}{\vec {p}}_{n}B_{n}(s)$

где $B_{n}(s)$ являются квадратичными базисными функциями B-сплайна и ${\vec {p}}_{n}$ являются контрольными точками сплайнов. Модифицированный мультипликационный предел получается как $\lambda \to \infty$ и является допустимой конфигурацией $E_{i}$.

Функционал $E_{c}$ основано на обучении по бинарным изображениям различных контуров и по силе контролируется параметром $\alpha$. Для гауссовского распределения векторов контрольных точек ${\vec {z}}$ со средним вектором контрольной точки ${\vec {z}}_{0}$ и ковариационная матрица $\Sigma$ , квадратичная энергия, соответствующая гауссовой вероятности, равна

$E_{c}({\vec {z}})={\frac {1}{2}}({\vec {z}}-{\vec {z}}_{0})^{t}\Sigma ^{*}({\vec {z}}-{\vec {z}}_{0})$

Сила этого метода зависит от силы обучающих данных, а также настройки модифицированного функционала Мамфорда – Шаха. Разным змеям потребуются разные наборы обучающих данных и настройки.

Геометрические активные контуры

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

Например, уравнение эволюции кривой градиентного спуска GAC:

${\frac {\partial C}{\partial t}}=g(I)(c+\kappa ){\vec {N}}-\langle \,\nabla g,{\vec {N}}\rangle {\vec {N}}$

где $g(I)$ — функция остановки, c — множитель Лагранжа, $\kappa$ это кривизна, а ${\vec {N}}$ Является ли блок внутри нормальным. Эта конкретная форма уравнения эволюции кривой зависит только от скорости в нормальном направлении. Поэтому его можно эквивалентно переписать в эйлеровой форме, вставив функцию набора уровней $\Phi$ в него следующим образом

${\frac {\partial \Phi }{\partial t}}=|\nabla \Phi |\operatorname {div} {\Bigg (}g(I){\frac {\nabla \Phi }{|\nabla \Phi |}}{\Bigg )}+cg(I)|\nabla \Phi |$

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

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

Статистические модели, сочетающие локальные и глобальные характеристики, были сформулированы Лэнктоном и Алленом Танненбаумом .

Связь с разрезами графа

Разрезы графа , или max-flow/min-cut , — это общий метод минимизации определенной формы энергии, называемой энергией марковского случайного поля (MRF). Метод разрезов графика также применялся к сегментации изображений, и иногда он превосходит метод набора уровней, когда модель представляет собой MRF или может быть аппроксимирована MRF.

См. также

• Граничное векторное поле

Внешние ссылки

• Дэвид Янг, март 1995 г.
• Змеи: Активные контуры, CVOnline
• Активные контуры, деформируемые модели и градиентный векторный поток от Чэньян Сюй и Джерри Принса, включая загрузку кода.
• ICBE, Манчестерский университет
• Реализация активных контуров и графический интерфейс тестовой платформы
• Простая реализация змей от доцента Криса Луенго.
• Документация MATLAB для activecontour, которая сегментирует изображение с использованием активных контуров.

Пример кода

• Практические примеры различных змей, разработанные Сюй и Принсом.
• Базовый инструмент для игры со змеями (активные контурные модели) от Тима Кутса, Манчестерский университет.
• Реализация в Matlab 2D и 3D змеи, включая GVF и баллонную силу.
• Демонстрация Matlab Snake от Криса Бреглера и Малкольма Слейни , Interval Research Corporation.
• Демонстрация использования Java
• Реализация Active Contours и графический интерфейс тестовой платформы Николая С. и Алекса Блехмана, реализующих «Активные контуры без краев»
• Активная сегментация контуров от Шона Лэнктона, реализующая «Активные контуры без краев».
• Код геометрического активного контура от Ярно Ралли
• Морфологические Змеи