crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

> Intelligent scissors
wiz29
  опции профиля:
сообщение 20.8.2010, 16:06
Сообщение #1


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

Спасибо сказали: 94 раз(а)




Репутация:   12  


Реализовывал ли кто нибудь данный алгоритм?(нужна консультация по производительности, моя реализация считает несколько секунд на картинке 1500+ х 1500+, тогда как продвинутые реализации справляются "мгновенно" с точки зрения пользователя, не беру в расчет время на вычисление весов ребер)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
 
Начать новую тему
Ответов
wiz29
  опции профиля:
сообщение 27.8.2010, 13:17
Сообщение #2


Старейший участник
****

Группа: Участник
Сообщений: 600
Регистрация: 7.7.2010
Из: Санкт-Петербург
Пользователь №: 1866

Спасибо сказали: 94 раз(а)




Репутация:   12  


Раскрывающийся текст
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




блин нелзя файлы почемуто прикрепить:(
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

Сообщений в этой теме
- wiz29   Intelligent scissors   20.8.2010, 16:06
- - Алексей1153   Какой алгоритм ?   20.8.2010, 16:32
|- - kibsoft   Цитата(Алексей1153 @ 20.8.2010, 17:32) Ка...   20.8.2010, 18:59
- - Алексей1153   ааа, вона чего... То есть выбор произвольной замкн...   20.8.2010, 19:19
|- - wiz29   Цитата(Алексей1153 @ 20.8.2010, 20:19) аа...   27.8.2010, 13:09
- - ufna   приведи код реализации, посмотрим.   27.8.2010, 13:10
- - wiz29   Раскрывающийся текстnamespace liveware { //solve ...   27.8.2010, 13:17
- - ufna   оберни плз в тег code, чтобы читабельность сохрани...   27.8.2010, 13:20
- - Алексей1153   в zip-архиве можно )   27.8.2010, 13:26
- - wiz29   CODE#ifndef LWSOLVE_H #define LWSOLVE_H #include ...   27.8.2010, 13:57
- - Алексей1153   блин, интересно, конечно, но сейчас вапще некогда ...   27.8.2010, 14:02
- - ufna   И покажи код где ты этот алгоритм запускаешь и как...   27.8.2010, 14:02
- - wiz29   Здесь именно вычисляется маршрут от SeedNode до вс...   27.8.2010, 14:29
- - ufna   а SeedNode всегда одна? т.е. можно увидеть как пр...   27.8.2010, 14:30
- - wiz29   Сейчас, расскажу как на практике, всю задачу как т...   27.8.2010, 14:49
- - ufna   а что происходит после того, как кратчайшие пути п...   27.8.2010, 15:04
- - wiz29   Если ты видел в фотошопе магнетик лассо, то он осн...   27.8.2010, 15:12
- - ufna   ну вот смотри, промелькнуло название "заданна...   27.8.2010, 15:29
- - wiz29   1. в алгоритме участвует 1 заданная вершина (затра...   27.8.2010, 15:32
- - ufna   а теперь поподробнее про ньюанс. В чем конкретно о...   27.8.2010, 15:37
- - wiz29   переход и вершины "а" в вершину "b...   27.8.2010, 15:39
- - ufna   с Флойдом сразу "отпало" как только речь...   27.8.2010, 15:41
- - wiz29   Самая критичная операция именно решение дейкстры, ...   27.8.2010, 15:41
- - ufna   А просчет дейкстры - это как раз часть прокладки м...   27.8.2010, 15:44
- - wiz29   А можешь сказать временную сложность?   27.8.2010, 15:45
- - ufna   Вся суть сего алгоритма - в правильном задании эвр...   27.8.2010, 15:50
- - wiz29   ну у меня количиства измеряются через 1М+ порядка ...   27.8.2010, 15:56
- - ufna   ну по атласам у меня тоже миллионные значения идут...   27.8.2010, 16:00
- - wiz29   Если положить h(x) = 0 для всех вершин, то мы полу...   27.8.2010, 16:03
- - ufna   Если h(x) = 0 (а это и есть эвристическая функция)...   27.8.2010, 16:43
- - Nik92   Цитата(wiz29 @ 20.8.2010, 16:06) Реализов...   1.3.2011, 17:51


Быстрый ответОтветить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 29.3.2024, 2:07