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