Intelligent scissors Опции

[Алексей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. что-то дальше

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