Модель активного контура - Active contour model

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

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

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

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

Мотивация

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

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

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

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

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

Формулировка энергии

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

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

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

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

Внутренняя энергия змеи складывается из непрерывности контура ${ displaystyle E _ { text {cont}}}$ и гладкость контура ${ 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 альфа (s)}$ и ${ displaystyle beta (s)}$ - веса, определяемые пользователем; они управляют чувствительностью функции внутренней энергии к величине растяжения змейки и величине кривизны змейки, соответственно, и тем самым контролируют количество ограничений на форму змейки.

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

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

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

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

${ displaystyle E _ { text {image}} = w _ { text {line}} E _ { text {line}} + w _ { text {edge}} E _ { text {edge}} + w _ { text {term}} E _ { text {term}},}$

куда ${ Displaystyle ш _ { текст {строка}}}$, ${ Displaystyle ш _ { текст {край}}}$, ${ Displaystyle ш _ { текст {термин}}}$ веса этих характерных черт. Более высокие веса указывают на то, что характерный элемент будет иметь больший вклад в силу изображения.

Линия функциональная

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

${ displaystyle E _ { text {line}} = I (x, y)}$

Знак ${ Displaystyle ш _ { текст {строка}}}$ определит, будет ли линия притягиваться темными или светлыми линиями.

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

${ displaystyle E _ { text {line}} = operatorname {filter} (I (x, y))}$

Edge функционал

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

${ 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 С (х, у)}$ быть сглаженным изображением

${ Displaystyle С (х, у) = G _ { sigma} cdot I (х, у)}$

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

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

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

${ Displaystyle mathbf {п} = ( соз тета, грех тета),}$

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

${ 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 {змея}} ({ 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 [} альфа { 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 тау}$. Таким образом, для практической реализации змей должны быть сделаны дискретные приближения.

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

${ displaystyle E _ { text {snake}} ^ {*} приблизительно sum _ {1} ^ {n} E _ { text {snake}} ({ bar {v}} _ {i})}$

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

${ displaystyle F _ { text {snake}} ^ {*} приблизительно - sum _ {i = 1} ^ {n} nabla E _ { text {snake}} ({ bar {v}} _ { я}).}$

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

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

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

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

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

${ displaystyle F _ { text {image}} = - k { frac { nabla E _ { text {image}}} { | nabla E _ { text {image}} |}}}$

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

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

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

Выполнение

Следующее псевдокод реализует метод змей в общем виде

функцияv =змеи (Я, в)% INPUT: N на M изображение I, контур v из n контрольных точек  % OUTPUT: сходящийся контур v из n контрольных точек  E_image = generateImageEnergy (я);  пока не сходится    F_cont = масса.альфа * contourDerivative(v, 2);    F_curv = масса.бета * contourDerivative(v, 4);    F_image = Interp2 (E_image, v(:,2), v(:,1));    F_image_norm = масса.k * F_image ./ норма (F_image);    F_con = inputForces();    F_internal = F_cont + масса.внешний * F_curv;    F_external = масса.внешний * (F_image + F_con);    v = updateSnake(v, F_internal, F_external);    checkConvergence ();  конецконец

Где generateImageEnergy (I) можно записать как

функцияE_image =generateImageEnergy (я)[C, Сх, Сай, Cxx, Cxy, Cyy] = generateGradients (я);  E_line = я;  E_edge = -(Сх.^2 + Сай.^2)^0.5;  E_term = (Cyy.*Сх.^2 - 2*Cxy.*Сх.*Сай + Cxx.*Сай.^2)./((1 + Сх.^2 + Сай.^2).^(1.5));  E_image = масса.линия * E_line + масса.край * E_edge + масса.срок * E_term;конец

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

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

Модель змеи GVF

В векторный градиент потока (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 _ { текст {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 _ { текст {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_ {я + 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 _ { текст {инфляция}} = 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 {изображение}}}$ заменяется на

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

куда ${ displaystyle B_ {n} (s)}$ являются квадратичными базисными B-сплайн-функциями и ${ 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}}}$

куда ${ displaystyle g (I)}$ это функция остановки, c множитель Лагранжа, ${ 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]

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

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

Рекомендации

внешняя ссылка

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

Образец кода

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