Intelligent scissors Опции

[wiz29]

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

[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