Техника сегментации Livewire - Livewire Segmentation Technique

Пример сегментации livewire на фото ребенка

Livewire, представляет собой метод сегментации, который позволяет пользователю выбирать интересующие области для быстрого и точного извлечения с помощью простых щелчков мышью.[1] Он основан на алгоритм наименьшей стоимости пути, от Эдсгер В. Дейкстра. Сначала сверните изображение с помощью Фильтр Собеля извлечь края. Каждый пиксель результирующего изображения является вершиной графа и имеет края, идущие к 4 пикселям вокруг него, как вверх, вниз, влево, вправо. Стоимость грани определяется на основе функции стоимости. В 1995 году Эрик Н. Мортенсен и Уильям А. Барретт проделали некоторую работу по расширению инструмента сегментации livewire, известного как Intelligent Scissors.[2]

Сегментация Livewire

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

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

Алгоритм Livewire

Сверните изображение с помощью фильтра Собеля, чтобы выделить края. Используя это отфильтрованное изображение, создайте граф, используя пиксели в качестве узлов с краями в четырех направлениях (вверх, вниз, влево и вправо).[1] Края утяжеляются элементами, собранными с помощью фильтра Собеля, что делает менее затратным оставаться на грани. Возможны несколько различных стоимостных методов, но наиболее важным является величина градиента.[1]

Live-Wire 2-D алгоритм поиска графа DP в псевдокоде [2]

алгоритм Livewire является    ввод:        s                       {Начальный (или начальный) пиксель.} L (q, r) {Функция локальной стоимости для связи между пикселями q и r.} структуры данных:        L {Список активных пикселей, отсортированный по общей стоимости (изначально пустой).} N (q) {Набор соседей q (содержит 8 соседей пикселя).} E (q) {Логическая функция, указывающая, был ли q расширен / обработан.} G (q) {Функция общей стоимости от начальной точки до q.} вывод:        п                       {Указатели от каждого пикселя, указывающие путь минимальной стоимости.} G (s) ← 0; L ← s; {Инициализировать активный список начальным пикселем с нулевой стоимостью.} в то время как L ≠ ∅ начать      {Пока все еще указывает на расширение.} q ← мин (L); {Удалить пиксель минимальной стоимости q из активного списка.} E (q) ← ИСТИНА; {Отметить q как развернутый (т.е. обработанный).} для каждого r∈N (q) такой, что Примечание(р) начать            gtmp ← g (q) + l (q, r); {Вычислить общую стоимость для соседа.} если р∈L и gtmp р) тогда  {Удалите из списка более дорогих соседей.}                r ← L; если r∉L тогда начни            {Если соседа нет в списке,} g (р) ← gtmp; {назначить общую стоимость соседа,} p (р) ← q; {установить (или сбросить) указатель назад,} L ← р; {и поместить в активный список (или вернуться в него).} конец                                        конец    конец

Расширение до 3D

В 2010 году Лео Грейди расширил алгоритм Livewire на 3D.[3] Это расширение рассматривало алгоритм 2D Livewire как позволяющий пользователю указать 0-мерную границу (две точки) и найти минимальную одномерную кограницу (кривую), соединяющую эти точки, где минимум определяется в терминах свойств изображения. Чтобы расширить алгоритм до 3D, пользователя вместо этого просят указать одну или несколько одномерных границ (замкнутые кривые), и алгоритм находит минимальную двумерную кограницу (поверхность), ограниченную одномерными кривыми, где минимальная поверхность определяется с точки зрения свойств изображения. Это 3D-расширение Livewire во многом опирается на концепции дискретное внешнее исчисление переосмыслить алгоритм 2D Livewire с точки зрения граничных / кограничных операторов, а затем применить эти концепции в 3D. Эффективный алгоритм вычисления минимальной трехмерной поверхности также представлен в статье Grady.

Смотрите также

использованная литература

  1. ^ а б c БАДЖИО, Даниэль Лелис. Реализация алгоритма Livewire для сегментации изображений на основе GPGPU. 2007. 108f. Диссертация на степень магистра наук - Технологический институт воздухоплавания, Сан-Жозе-душ-Кампос. http://gpuwire.googlecode.com/files/Master%20Thesis%20-%20Updated%20Feb February%2015th.pdf В архиве 2010-12-17 на Wayback Machine
  2. ^ а б MORTENSEN, E. N .; БАРРЕТ, В. А. Интеллектуальные ножницы для композиции изображений. В: SIGGRAPH ’95: Материалы 22-й ежегодной конференции по компьютерной графике и интерактивным методам. Нью-Йорк, Нью-Йорк, США: ACM Press, 1995. стр. 191–198. ISBN  0-89791-701-4.
  3. ^ Лео Грейди, "Минимальные поверхности расширяют методы сегментации по кратчайшему пути до 3D ”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 32, No. 2, pp. 321-334, февраль 2010 г.

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