Intelligent scissors Опции Подписка на тему Сообщить другу Версия для печати Скачать тему Подписка на этот форум Режимы отображения Переключить на: Древовидный Переключить на: Стандартный Линейный

[wiz29]

Реализовывал ли кто нибудь данный алгоритм?(нужна консультация по производительности, моя реализация считает несколько секунд на картинке 1500+ х 1500+, тогда как продвинутые реализации справляются "мгновенно" с точки зрения пользователя, не беру в расчет время на вычисление весов ребер)

[Алексей1153]

Какой алгоритм ?

[kibsoft]

Какой алгоритм ?

Название сабжа

[Алексей1153]

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

wiz29, ну дык, словесный алгоритм и саму реализацию - в студию попросим ) Для оптимизации

[wiz29]

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

wiz29, ну дык, словесный алгоритм и саму реализацию - в студию попросим ) Для оптимизации

нет, ты говоришь про так называемый Magic Wand алгоритм , здесь другой алгоритм, просто хотел проконсультироваться с человеком который вероятно сталкивался с ним. Материала слишком много , чтобы писать в посте, поэтому и написал ("Если кто то сталкивался").
Последнюю реализацию я смог ускорить в 5 раз, но время решения всеравно занимает порядка 1сек на моей не медленной машине, хотелось бы быстрее

[ufna]

приведи код реализации, посмотрим.

[wiz29]

Раскрывающийся текст

namespace liveware
{
    //solve for seed point with coord (xSeed, ySeed)
    void Dijkstra(ImageGraph& graph, int xSeed, int ySeed);
}//namespace liveware

namespace liveware
{
    //---------------------------------------------------------------------------------------------------------
    enum NodeSate 
    {
        NONE = 0x00,        //if node was not processed
        PROCESSED = 0x01,    //node was processed
        ACTIVE = 0x02        //node in active queue
    };

    //---------------------------------------------------------------------------------------------------------
    //functor
    //reset all calc dijkstra data
    class cleanGraph
    {
        public:

            void operator()(GraphNode* pNode)
            {
                if (pNode)
                {
                    pNode->SetState(NONE);//reset state
                    pNode->SetPrevNode(NULL);//reset prev node
                    pNode->SetWeight(1.0e+10);//set "infinite" weight
                }
            }
    };

    //---------------------------------------------------------------------------------------------------------
    //functor
    //calculate transit cost for neighborhood nodes
    class calcCost
    {
        public:

            calcCost(PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& pq,
                GraphNode* pCurrNode)
                : m_pq(pq)
                , m_pCurrNode(pCurrNode)
            {
            }

            ~calcCost()
            {
            }

        public:

            void operator()(std::pair<GraphNode*, double>& pDstNodeData)
            {
                GraphNode* pNode(pDstNodeData.first);
                if (!(pNode->state() & PROCESSED))
                {                    
                                        double localCost(m_pCurrNode->Weight() + pDstNodeData.second);
                    if (!(pNode->state() & ACTIVE))
                    {//node is not in queue
                        pNode->SetWeight(localCost);
                        pNode->SetPrevNode(m_pCurrNode);
                        m_pq.push(pNode);
                        pNode->SetState(ACTIVE);
                    }
                    else if (localCost < pNode->Weight())
                    {//node already in queue
                        pNode->SetWeight(localCost);
                        pNode->SetPrevNode(m_pCurrNode);
                        m_pq.update();                        
                    }
                }
            }

        private:

            PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& m_pq;
            GraphNode* m_pCurrNode;
    };

    //---------------------------------------------------------------------------------------------------------
    //solve for seed point with coord (xSeed, ySeed)
    void Dijkstra(ImageGraph& graph, int xSeed, int ySeed)
    {        
        std::for_each(graph.Begin(), graph.End(), cleanGraph());//clean all dijkstra data
        PriorityQueue<GraphNode*, std::vector<GraphNode*>, less> pq;//construct empty priority queue
                                                                    //of active nodes
        GraphNode* pCurr(graph.ElementAt(xSeed, ySeed));//take seed node
        pCurr->SetWeight(0.0);    
        pq.push(pCurr);//push seed node into queue
        pCurr->SetState(ACTIVE);//set active node state
        while(!pq.empty())
        {
            pCurr = pq.top();
            pq.pop();
            pCurr->SetState(PROCESSED);
            std::for_each(pCurr->NeighborhoodBegin(), pCurr->NeighborhoodEnd(),
                calcCost(pq, pCurr));
        }
    }
    //---------------------------------------------------------------------------------------------------------
}//namespace liveware

блин нелзя файлы почемуто прикрепить

[ufna]

оберни плз в тег code, чтобы читабельность сохранилась, а то без indent'ов сложно воспринимать

[Алексей1153]

в zip-архиве можно )

[wiz29]

CODE

#ifndef LWSOLVE_H
#define LWSOLVE_H

#include "lwimagegraph.h"

namespace liveware
{
//solve for seed point with coord (xSeed, ySeed)
void Dijkstra(ImageGraph& graph, int xSeed, int ySeed);
}//namespace liveware

#endif //LWSOLVE_H

#include "lwsolve.h"
#include "lwpriorityqueue.h"
#include <algorithm>
#include <functional>
#include <QDebug>

namespace liveware
{
//---------------------------------------------------------------------------------------------------------
enum NodeSate
{
NONE = 0x00, //if node was not processed
PROCESSED = 0x01, //node was processed
ACTIVE = 0x02 //node in active queue
};

//---------------------------------------------------------------------------------------------------------
//functor
//reset all calc dijkstra data
class cleanGraph
{
public:

void operator()(GraphNode* pNode)
{
if (pNode)
{
pNode->SetState(NONE);//reset state
pNode->SetPrevNode(NULL);//reset prev node
pNode->SetWeight(1.0e+10);//set "infinite" weight
}
}
};

//---------------------------------------------------------------------------------------------------------
//functor
//calculate transit cost for neighborhood nodes
class calcCost
{
public:

calcCost(PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& pq,
GraphNode* pCurrNode)
: m_pq(pq)
, m_pCurrNode(pCurrNode)
{
}

~calcCost()
{
}

public:

void operator()(std::pair<GraphNode*, double>& pDstNodeData)
{
GraphNode* pNode(pDstNodeData.first);
if (!(pNode->state() & PROCESSED))
{
double localCost(m_pCurrNode->Weight() + pDstNodeData.second);
if (!(pNode->state() & ACTIVE))
{//node is not in queue
pNode->SetWeight(localCost);
pNode->SetPrevNode(m_pCurrNode);
m_pq.push(pNode);
pNode->SetState(ACTIVE);
}
else if (localCost < pNode->Weight())
{//node already in queue
pNode->SetWeight(localCost);
pNode->SetPrevNode(m_pCurrNode);
m_pq.update();
}
}
}

private:

PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& m_pq;
GraphNode* m_pCurrNode;
};

//---------------------------------------------------------------------------------------------------------
//solve for seed point with coord (xSeed, ySeed)
void Dijkstra(ImageGraph& graph, int xSeed, int ySeed)
{
std::for_each(graph.Begin(), graph.End(), cleanGraph());//clean all dijkstra data
PriorityQueue<GraphNode*, std::vector<GraphNode*>, less> pq;//construct empty priority queue
//of active nodes
GraphNode* pCurr(graph.ElementAt(xSeed, ySeed));//take seed node
pCurr->SetWeight(0.0);
pq.push(pCurr);//push seed node into queue
pCurr->SetState(ACTIVE);//set active node state
while(!pq.empty())
{
pCurr = pq.top();
pq.pop();
pCurr->SetState(PROCESSED);
std::for_each(pCurr->NeighborhoodBegin(), pCurr->NeighborhoodEnd(),
calcCost(pq, pCurr));
}
}
//---------------------------------------------------------------------------------------------------------
}//namespace liveware

если кому интересна данная задача могуть дать литературу

Сообщение отредактировал wiz29 - 27.8.2010, 13:31

[Алексей1153]

блин, интересно, конечно, но сейчас вапще некогда ((( А так бы посидел поковырялся

[ufna]

И покажи код где ты этот алгоритм запускаешь и какие в него данные.

Пока косо смотрю на дейкстру, не думаю что это лучший вариант когда вычисляется не маршрут.

[wiz29]

Здесь именно вычисляется маршрут от SeedNode до всех осталных вершин

CODE

namespace liveware
{

class ImageGraph
{

public:

typedef std::vector<GraphNode*>::iterator iterator;
typedef std::vector<GraphNode*>::const_iterator const_iterator;

public:

ImageGraph(void);
~ImageGraph(void);

public:

//set size for image graph
void SetSize(int w, int h);
//return begin iterator for ImageGraph
iterator Begin();
//return begin iterator for ImageGraph
const_iterator Begin() const;
//return end iterator for ImageGraph
iterator End();
//return end iterator for ImageGraph
const_iterator End() const;
//return elemet count of ImageGraph
size_t GetSize() const;
//return width of ImageGraph
int GetWidth() const;
//return height of ImageGraph
int GetHeight() const;
//return element at cell
GraphNode* ElementAt(int x, int y);
GraphNode* ElementAt(int index);
//make image graph from QImage
bool LoadImage(const QImage& img);

private:

//release resources
void release();

private:

int m_w;//width of image graph
int m_h;//height of image graph
std::vector<GraphNode*> m_nodes;//image graph nodes
};//class ImageGraph
}//namespace liveware

namespace liveware
{
class less;
class ImageGraph;

class GraphNode
{
public:

friend class liveware::less;
friend class liveware::ImageGraph;

//first param of pair is dst node
//second param of pair is transition cost to dst node
typedef std::vector<std::pair<GraphNode*, double> > NeighboorhoodContainer;
typedef NeighboorhoodContainer::iterator iterator;
typedef NeighboorhoodContainer::const_iterator const_iterator;

public:

GraphNode(double weight = 0.0);
~GraphNode();

public:

//return x coord of node
int GetX() const;
//return y coord of node
int GetY() const;
//set x coord of node
void SetX(int);
//set y coord of node
void SetY(int);
//set x, y coord of node
void SetXY(int x, int y);
//set state of node (used for live ware)
void SetState(int);
//return state of node
int state() const;
//set weight of node
void SetWeight(double);
//return const reference for node weight
double Weight() const;
//return itertor for first neighborhood node
iterator NeighborhoodBegin();
//return const itertor for first neighborhood node
const_iterator NeighborhoodBegin() const;
//return iterator for end neighborhood node
iterator NeighborhoodEnd();
//return const iterator for end neighborhood node
const_iterator NeighborhoodEnd() const;
//return prev Node (for solve)
GraphNode* PrevNode();
//set prev Node
void SetPrevNode(GraphNode*);

private:

int m_x;//x coord of node
int m_y;//y coord of node
int m_state;// node state (for live ware algo)
double m_weight;//node weight (total cost of path to this node)
GraphNode* m_pPrevNode;//pointer to prev graph node (for liveware algo)
NeighboorhoodContainer m_neighborhood;//list of neighborhood (for liveware algo),
//second parametr is cost of transition from this node to
};//class GraphNode

//---------------------------------------------------------------------------------------------------------
//predicate
class less
: public std::binary_function<GraphNode*, GraphNode*, bool>
{
public:
bool operator()(const GraphNode* pNode1, const GraphNode* pNode2);
};//class less
}//namespace liveware

[ufna]

а SeedNode всегда одна?

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

[wiz29]

Сейчас, расскажу как на практике, всю задачу как ты понимаешь решает алгоритм дейкстры.
На вход ему подается 3 параметра ImageGraph - взвешенный граф изображения и хSeed, ySeed это координаты затравочной точки.
Дальше дейкстра находит кратчайшие пути к каждой из вершин графа от затравочной. ImageGraph строится по картинке например QImage, число вершин графа соответсвует количеству пикселей изображения. Пути после очень просто построить к затравочной точке, взять любой GraphNode и спустится по PrevNode к затаравочной точке (PrevNode затравочной точки равен 0) вот так на практике. Как вычисляются веса это уже соответсвует качеству того или иного алгоритма.

[ufna]

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

второе - как вычисляются веса? Сама идея.

[wiz29]

Если ты видел в фотошопе магнетик лассо, то он основан именно на этом алгоритме Дальше просто стораятся траетории от заданной вершины к Затравочной. как вычисляются веса почитай вот тут http://cgm.computergraphics.ru/content/view/172 (там весьма бщие сведения правда))


в статье есть ряд неточностей но они больше касаюся формул, идея думаю там будет понятна

вот еще одна очень наглядная статья http://www.cs.washington.edu/education/cou...t1/project1.htm сейчас вычисление весов взято отсюда, но это не главное в данной задаче.

[ufna]

ну вот смотри, промелькнуло название "заданная вершина". Как вывод, нас интересуют кратчайшие маршруты от этих точек до затравочной. Как вариант, возможно использование A*, либо алгоритм Флойда. Во втором случае мы получаем уже просчитанную матрицу, поэтому для всех заданных вершин значения будут вычислены, а не считаться "до затравочной" - это как минимум снижает объем вычислений. В первом - вычисление всей матрицы становится нафиг не нужно, но возникает определенная погрешность, вызываемая эвристической функцией (но здесь нужно продумать правильно эвристику, возможно вариант будет очень быстрым).

А сколько "заданных вершин" участвуют в алгоритме? Т.е. откуда они беруться? Это те пиксели где пользователь провел пером?

про вычисление весов спрашивал в том контексте, что нельзя ли матрицу "сжать" по размером, не слишком теряя точность.


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

Сообщение отредактировал ufna - 27.8.2010, 15:29

[wiz29]

1. в алгоритме участвует 1 заданная вершина (затравачная) и 1 (любая) вершина выбранная пользователем (для построения пути).
2. матрица весов не вычисляется каждый раз (ее вычисление производится толко при создании ImageGraph 1раз)
Есть один ньюанс переход из 1->2 не обязательно будет совпадать по стоимости с переходом из 2->1

я тестил профайлером
построение путей в решенной задаче занимает << времени чем решение задачи


Сообщение отредактировал wiz29 - 27.8.2010, 15:31

[ufna]

а теперь поподробнее про ньюанс. В чем конкретно он выражается, если веса просчитаны? Что-то еще влияет на маршрут?

если учавствуют всего две вершины, то путь находится куда быстрее именно алгоритмом A*, тем более на больших полях где число точек глобально. Я его использую на гпс навигаторах для прокладки маршрута по десяткам тысяч точек и работает - секунды, на компе - менее полсекунды на самых диких атласах. Могу скинуть код-схему алгоритма.

ну если отставить пути, то что занимает большее количество времени? Какая часть? Как я понял, основные части:

1. просчет весов графа
2. построение путей
3. что-то дальше

какие пропорции по временным затратам?

[wiz29]

переход и вершины "а" в вершину "b" стоит не столько же сколькоперехо из "b" в "a" ребра имеют 2 направления
и альго Флойда здесь не совсем подойдет т.к. его сложность O(n^3) тогда как Дейкстра решает задачу за O(n^2 + m) m-число ребер (это самая плохая оценка для Дейкстры)

Хех, круто зато Флойд паралелится спс за подсказку

[ufna]

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

по весам понял, т.е. путь из b в a может быть не кратчайшим, просто совпадает с из а в b.

Сообщение отредактировал ufna - 27.8.2010, 15:42

[wiz29]

Самая критичная операция именно решение дейкстры, на моей машине рассчитывается порядка 0.8 сек (это дороговато)
Если могешь, скинь А* просто ничего про него не слышал

[ufna]

А просчет дейкстры - это как раз часть прокладки маршрута, поэтому я об этом речь и завел.


A* - наверное самый популярный алгоритм в геймдеве. Описание ниже. Если нужно, могу скинуть код с классами для Open, Closed и сам алгоритм в Qt.

/*
приоритетная очередь Open
список Closed

ПоискАЗвездочка
   s.g = 0  // s - стартовый узел
   s.h = ЭвристическаяОценка( s )
   s.f = s.g + s.h
   s.родитель = null
   добавить s в Open
   пока очередь Open не пуста
      извлечь n из Open  // n - узел с наименьшей стоимость в Open
      если n целевой узел
         сконструировать путь
         выйти с кодом "успешное завершение"
      для каждого наследника n' узла n
         newg = n.g + стоимость(n,n')
         если n' в Open или Closed, и n'.g <= newg
             пропустить n'
         n'.родитель = n
         n'.g = newg
         n'.h = ЭвристическаяОценка( n' )
         n'.f = n'.g + n'.h
         если n' в Closed
            удалить n' из Closed
         если n' не в Open
            положить n' в Open
      положить n в Closed
   выйти с кодом "путь не найден"
*/

[wiz29]

А можешь сказать временную сложность?

[ufna]

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

На вики есть описание

к примеру, ситуация на практике - 70к вершин, 100к ребер. Прокладка из А в Б "обход в ширину" - около 45к итераций, через А* - около 700. Дейкстру использовать на мобильных девайсах предполагается невозможным, поэтому это чисто практика работы с GPS маршрутами.

[wiz29]

ну у меня количиства измеряются через 1М+ порядка ну или около того это по вершинам.

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

[ufna]

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


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

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

[wiz29]

Если положить h(x) = 0 для всех вершин, то мы получим ещё один специальный случай — алгоритм Дейкстры.

а ты очередь с приоритетом сам писал или заимствовал гдето? (просто я у себя использовал стл вариант а апдейт сделал тупо окучивание всей последовательности, если какойто более производительный вариант?)

[ufna]

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

очередь с приоритетом писал сам, на основе QList для хранения самой очереди и QSet для быстрой отсечки "есть/нет" в очереди. Не факт что оптимально, но для моих целей работает как часы. Список Closed у меня тоже свой, но все основано на QHash - у меня просто стандартизированный под мой проект интерфейс.

вот еще ссылочка хорошая, там по некоторым алгоритмам хорошо написано: http://khpi-iip.mipk.kharkiv.edu/library/d...gsu/oglav6.html

дядька из КГУ нашего писал, плюс я сам немного лапку для создания некоторых шагов приложил

[Гость_Nik92_*]

Реализовывал ли кто нибудь данный алгоритм?(нужна консультация по производительности, моя реализация считает несколько секунд на картинке 1500+ х 1500+, тогда как продвинутые реализации справляются "мгновенно" с точки зрения пользователя, не беру в расчет время на вычисление весов ребер)

привет! ты не мог бы мне кинуть свою реализацию? nikolas9292@rambler.ru