crossplatform.ru

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

4 страниц V   1 2 3 > »   
Ответить в данную темуНачать новую тему
> Intelligent scissors
wiz29
  опции профиля:
сообщение 20.8.2010, 16:06
Сообщение #1


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

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

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




Репутация:   12  


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


фрилансер
******

Группа: Участник
Сообщений: 2921
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

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




Репутация:   34  


Какой алгоритм ?
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
kibsoft
  опции профиля:
сообщение 20.8.2010, 18:59
Сообщение #3


Участник
**

Группа: Участник
Сообщений: 180
Регистрация: 21.7.2009
Из: Самара
Пользователь №: 928

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




Репутация:   2  


Цитата(Алексей1153 @ 20.8.2010, 17:32) *
Какой алгоритм ?

Название сабжа :)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 20.8.2010, 19:19
Сообщение #4


фрилансер
******

Группа: Участник
Сообщений: 2921
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

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




Репутация:   34  


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

wiz29, ну дык, словесный алгоритм и саму реализацию - в студию попросим ) Для оптимизации
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 27.8.2010, 13:09
Сообщение #5


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

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

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




Репутация:   12  


Цитата(Алексей1153 @ 20.8.2010, 20:19) *
ааа, вона чего... То есть выбор произвольной замкнутой области на битмапе

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

нет, ты говоришь про так называемый Magic Wand алгоритм , здесь другой алгоритм, просто хотел проконсультироваться с человеком который вероятно сталкивался с ним. Материала слишком много , чтобы писать в посте, поэтому и написал ("Если кто то сталкивался").
Последнюю реализацию я смог ускорить в 5 раз, но время решения всеравно занимает порядка 1сек на моей не медленной машине, хотелось бы быстрее:)
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ufna
  опции профиля:
сообщение 27.8.2010, 13:10
Сообщение #6


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

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




Репутация:   5  


приведи код реализации, посмотрим.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 27.8.2010, 13:17
Сообщение #7


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

Группа: Участник
Сообщений: 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




блин нелзя файлы почемуто прикрепить:(
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ufna
  опции профиля:
сообщение 27.8.2010, 13:20
Сообщение #8


Активный участник
***

Группа: Участник
Сообщений: 362
Регистрация: 24.5.2008
Из: Курган/СПб
Пользователь №: 182

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




Репутация:   5  


оберни плз в тег code, чтобы читабельность сохранилась, а то без indent'ов сложно воспринимать
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 27.8.2010, 13:26
Сообщение #9


фрилансер
******

Группа: Участник
Сообщений: 2921
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

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




Репутация:   34  


в zip-архиве можно )
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
wiz29
  опции профиля:
сообщение 27.8.2010, 13:57
Сообщение #10


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

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

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




Репутация:   12  


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
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

4 страниц V   1 2 3 > » 
Быстрый ответОтветить в данную темуНачать новую тему
Теги
Нет тегов для показа


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




RSS Текстовая версия Сейчас: 21.4.2021, 20:40