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

Пример сегментации живой проволоки на фотографии ребенка

Livewire — это метод сегментации, который позволяет пользователю выбирать интересующие области для быстрого и точного извлечения с помощью простых щелчков мыши. Он основан на алгоритме пути с наименьшей стоимостью , разработанном Эдсгером В. Дейкстрой . Сначала сверните изображение с помощью фильтра Собеля, чтобы выделить края. Каждый пиксель результирующего изображения является вершиной графа и имеет ребра, ведущие к 4 пикселям вокруг него: вверх, вниз, влево, вправо. Краевые затраты определяются на основе функции стоимости. В 1995 году Эрик Н. Мортенсен и Уильям А. Барретт провели дополнительную работу над инструментом сегментации под напряжением, известным как «Интеллектуальные ножницы».

Сегментация в реальном времени

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

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

Алгоритм Livewire

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

Алгоритм поиска двумерного графа DP Live-Wire в псевдокоде

algorithm Livewire is
    input:
        s                       {Start (or seed) pixel.}
        l(q, r)                 {Local cost function for link between pixels q and r.} 
    data structures:
        L                       {List of active pixels sorted by total cost (initially empty).}
        N(q)                    {Neighborhood set of q (contains 8 neighbors of pixel).} 
        e(q)                    {Boolean function indicating if q has been expanded/processed.}
        g(q)                    {Total cost function from seed point to q.}
    output:
        p                       {Pointers from each pixel indicating the minimum cost path.}

    g(s) ← 0; L ← s;        {Initialize active list with zero cost seed pixel.}
    while L≠∅ do begin      {While still points to expand.}
        q ← min(L);             {Remove minimum cost pixel q from active list.}
        e(q) ← TRUE;             {Mark q as expanded (i.e., processed).}
        for each r∈N(q) such that not e(r) do begin
            gtmp ←g(q) + l(q, r);        {Compute total cost to neighbor.}
            if r∈L and gtmp < g(r) then  {Remove higher cost neighbor's from list.}
                r ← L;                      
            if r∉L then begin            {If neighbor not on list, }
                g(r) ← gtmp;             {assign neighbor's total cost, }
                p(r) ← q;                {set (or reset) back pointer, } 
                L ← r;                   {and place on (or return to)  active list.} 
            end                                
        end
    end

Extension to 3D

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

См. также

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

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

• Реализация Java с открытым исходным кодом инструмента сегментации изображений Livewire для ImageJ - Дэниел Лелис Баджо
• Видео коронарной сегментации
• Реализация Python с открытым исходным кодом