Уточнение контура объекта

[Smorodov 579]

А методом поиска кратчайшего пути на взвешенном графе, по ссылке mrgloom-а (https://facwiki.cs.byu.edu/cs312ringger/index.php/Project_4) не пробовали? (там и исходнник есть), мне кажется, это то, что Вам нужно (судя по Вашей картинке).

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

Таким образом, чем больше градиент, тем меньше вес ребра (короче путь) между соседними пикселями. Алгоритм Дейкстры ищет (приближение) наикратчайшего пути, который и будет искомым контуром объекта. Причем в Вашем случае он не будет обращать внимание на нежелательные перепады яркости.

[kazanOpenCV 0]

Smorodov, спасибо, сейчас занимаюсь как раз этим!

[Smorodov 579]

Поиск кратчайшего пути на CUDA (vs проект).

http://code.google.com/p/cuda-shortest-path/

[kazanOpenCV 0]

Smorodov, спасибо за ссылку.

Нашел вот такой алгоритм Дейкстры.

он ищет минимальную "стоимость пути" от исходного узла до всех узлов.

Чтобы сформировать цепочку из узлов я добавил код с комментарием //kazanOpenCV 18.02.2013.

Еще не проверял, вечером попробую скомпилировать.

#include <cstdio>

#include <queue>

#include <vector>

using namespace std;


#define MAX 100001

#define INF (1<<20)

#define DEBUG if(0)

#define pii pair< int, int >

#define pb(x) push_back(x)


struct comp {

    bool operator() (const pii &a, const pii &B )/>/>/>/> {

        return a.second > b.second;

    }

};


priority_queue< pii, vector< pii >, comp > Q;

vector< pii > G[MAX];

int D[MAX];

bool F[MAX];


int main() {

    int i, u, v, w, sz, nodes, edges, starting;


//kazanOpenCV 18.02.2013 

  vector<vector<int> > e;



    DEBUG freopen("in.txt","r", stdin);


    // create graph

    scanf("%d %d", &nodes, &edges);

    for(i=0; i<edges; i++) {

        scanf("%d %d %d", &u, &v, &w);

        G[u].pb(pii(v, w));

        G[v].pb(pii(u, w)); // for undirected

    }

    scanf("%d", &starting);


    // initialize graph

    for(i=1; i<=nodes; i++) D[i] = INF;




//kazanOpenCV 18.02.2013 


 for(i=1; i<=nodes; i++) e.push_back(vector<int>()); - начальное заполнение массива векторов пустыми векторами



    D[starting] = 0;

    Q.push(pii(starting, 0));


    // dijkstra

    while(!Q.empty()) {

        u = Q.top().first;

        Q.pop();

        if(F[u]) continue;

        sz = G[u].size();

        DEBUG printf("visiting from %d:", u);

        for(i=0; i<sz; i++) {

            v = G[u][i].first;

            w = G[u][i].second;

            if(!F[v] && D[u]+w < D[v]) {

                DEBUG printf(" %d,", v);

                D[v] = D[u] + w;




//kazanOpenCV 18.02.2013 


//std::vector<int> newvector(oldvector); -копирование одного вектора в другой



std::vector<int> e[v](e[u]);//-копирование одного вектора в другой


// vector<vector<int> > e;

// e.push_back(vector<int>());


e[v].push_back(u);//вставка элемента u в конец цепочки узлов в пути



                Q.push(pii(v, D[v]));

            }

        }

        DEBUG printf("\n");

        F[u] = 1; // done with u

    }


    // result

    for(i=1; i<=nodes; i++) printf("Node %d, min weight = %d\n", i, D[i]);

    return 0;

}

[kazanOpenCV 0]

Для куска изображения размером 200x200 пикселов (количество вершин графа 40 000),

время выполнения алгоритма поиска кратчайшего пути от заданной точки до всех остальных ~25 секунд.

Что-то многовато. Если 1920x1080 то совсем долго будет.

Как же, интересно, реализуют подобные алгоритмы в gimp или photoshope.

Smorodov, mrgloom, может быть есть соображения по оптимизации?

[Smorodov 579]

Во-первых, можно обрабатывать не весь экран, а кусок (квадрат или прямоугольник, с точками начального отрезка на диагонали), почти всегда граница будет содержаться в этом куске. Если точек больше двух, то-можно взять и составить цепочку таких прямоугольников.

Во-вторых, я привел выше кусок на CUDA, насколько помню, время выполнения для 200000 узлов примерно 0.1 с.

[kazanOpenCV 0]

Smorodov, да, я использую кусок исходного изображения соответствующий отрезку.

Исходник на CUDA смотрел, но там нужно подключать Boost Graph Library, не хотелось бы.

Пока реализовал сам на основе кода с priority_queue, выкладываю программу, если будет время посмотрите, пожалуйста.

Там небольшая проблемка (см. приложенный рисунок). На рисунке тестовое изображение 10x10 пикселов. Черная горизонтальная полоса на уровне второго пиксела сверху на белом фоне.

Граф состоит из 100 вершин. Веса для соединяющих ребер нахожу как в http://www.cs.washington.edu/education/courses/cse455/02wi/projects/project1/project1.htm (см. рис.2).

В итоге кратчайший путь из 10 вершины в 9 определяется как показано красной линией (т.е. путь из номеров пикселов 10-1-12-3-14-5-16-7-18).

Вероятно я что то делаю не так.

Dijkstra.rar

[mrgloom 242]

время выполнения алгоритма поиска кратчайшего пути от заданной точки до всех остальных

так зачем до всех остальных то искать? надо же всего между двумя точками найти.

[kazanOpenCV 0]

так зачем до всех остальных то искать? надо же всего между двумя точками найти.

mrgloom, так Dijkstra, насколько, я понял работает именно перебором всех узлов графа.

Если координаты концов отрезка (x1,y1)-(x2,y2), то получается прямоугольный граф с количеством узлов N=(x2-x1+1)*(y2-y1+1)

и количеством ребер L=(x2-x1-1)*(y2-y1-1)*8+ //серединные пиксели - у них по 8 связей со всеми остальными

+(width-2)*2*5+(height-2)*2*5+ //краевые пиксели без угловых - у них по 5 связей со всеми остальными

+4*3; //угловые пиксели - у них по 3 связи со всеми остальными

Upd. Единственное, можно остановиться когда дойдем до узла, соответствующего концу отрезка, но как много узлов будет уже посещено до этого зависит

от характера картинки. Но в среднем, конечно это ускорит выполнение алгоритма.

[kazanOpenCV 0]

Пришла в голову идея определять вес ребра, соединяющего 2 пикселя, как Weight ((i,j); (i1,j1))=(Max - 1/2*(img(i,j)+img(i1,j1)))*koef;

koef=sqrt(2) для диагональных ребер, =1 для верикальных и горизонтальных ребер. Max-для grayscale =255, для чернобелого изображения =1.

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

[mrgloom 242]

по первой ссылке которую давал там оказывается не были реализованы методы.

вот тут тоже самое, но полный код.

https://github.com/freelancejounin/intelligent-scissors

код я не смотрел, но во всяком случае при использовании intellegent scissors задумывается на несколько секунд.

возможно есть и более оптимизированные варианты.

[kazanOpenCV 0]

mrgloom, спасибо, посмотрю.

Первая ссылка в любом случае мне помогла в плане понимания.

[kazanOpenCV 0]

Всем доброго времени суток,

на картинке слева результат работы Gimp'а, справа моего алгоритма.

Пока еще дорабатываю, остаются вопросы по скорости и по детализации мелких деталей. Вообщем есть большое поле для оптимизации.

Smorodov, mrgloom большое вам спасибо за ощутимую помощь, думаю еще возникнут вопросы и не раз)

[Smorodov 579]

По поводу мелких деталей, можно попробовать такие способы:

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

1) Нарисовать границу толстой (пикселей 10-20) линией, это будет маска. Убить этой маской все лишнее и применить Кэнни (как Вы делали вначале).

2) За первое приближение взять результат выполнения этого алгоритма, а дальше запустить алгоритм активного контура (змеи), там есть параметры, которые и будут определять степень сглаженности и "прилипчивость" контура.

Контур не обязательно должен быть замкнут.

[kazanOpenCV 0]

Smorodov, спасибо за очередную порцию полезных идей.

По п.0) если умножить все значения, например на 10, то разве "прыжков" станет меньше? Или же усиливать только "окрестности" значений, соответствующих началу и концу отрезка.

По поводу п.1) можно поподробнее? не совсем понял.

[Smorodov 579]

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

То есть сила ребер будет определять гладкость пути, чем ребра слабже - тем больше алгоритм будет "срезать".

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

По поводу пункта 1. я имел ввиду тоже что и в посте №25, только предварительно наложить маску, которую Вы посчитали поиском минимального пути. Собель не будет Вам ничего сглаживать и выведет все как есть, а сторонние границы помогает исключить маска.

[mrgloom 242]

http://cseweb.ucsd.edu/classes/wi03/cse291-j/lec16.pdf

непонятно как тут делается Minimum Error Boundary Cut

ведь когда у нас есть 2 конечные точки, то понятно, а тут у нас 2-х точек нету.

[Smorodov 579]

Тут, как я понял, берем узел на верхней границе (его координаты задаются).

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

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

[mrgloom 242]

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

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

[mrgloom 242]

http://www.dirk-farin.net/projects/csp/index.html

еще по теме