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

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

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

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

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

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

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

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

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

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

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

${\displaystyle E_{\text{змея}}^{*}=\int \limits _{0}^{1}E_{\text{змея}}(\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}$

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

${\displaystyle E_{\text{internal}}=E_{\text{cont}}+E_{\text{curv}}}$ ^[3]

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

${\displaystyle 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 )}}$

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

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

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

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

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

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

Линейный функционал — это интенсивность изображения, которую можно представить как

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

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

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

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

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

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

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

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

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

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

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

с углом наклона

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

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

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

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

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

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

${\displaystyle 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}}}$

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

При наличии начального предположения для змеи функция энергии змеи итеративно минимизируется. Минимизация градиентного спуска является одной из простейших оптимизаций, которая может быть использована для минимизации энергии змеи. ^[4] Каждая итерация делает один шаг в отрицательном градиенте точки с контролируемым размером шага для поиска локальных минимумов. Эта минимизация градиентного спуска может быть реализована как${\displaystyle \gamma }$

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

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

${\displaystyle 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 )}}$

Предполагая, что веса и постоянны относительно , ​​этот итерационный метод можно упростить до${\displaystyle \alpha (s)}$${\displaystyle \beta (s)}$${\displaystyle s}$

${\displaystyle {\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 \}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}$

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

${\displaystyle \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}$

${\displaystyle \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}$

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

${\displaystyle 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 )}}$

${\displaystyle 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 )}}$

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

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

Основная проблема с использованием GVF заключается в том, что сглаживающий член вызывает скругление краев контура. Уменьшение значения уменьшает скругление, но ослабляет степень сглаживания.${\displaystyle \mu }$${\displaystyle \mu }$

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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