VPF::Обход изображения по краю - Форум программистов

DissDoc

Дата 4.8.2007, 19:15 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 463
Регистрация: 13.7.2006

Репутация: нет
Всего: нет

Ребят, помогите каким угодно образом решить мою проблему. Не могу догадаться, как "как бы выделить прямоугольником" изображение. Допустим есть на картинке круг (квадрат, какая-нить абракадабра) при условии что он весь внутри закрашен (т.е. идеальный случай). Картинка бинарная (не стоит усложнять). И как мне по краю пройтись, чтобы получить начальные и конечноые XY координаты, т.е. для прямоугольника, в который вписана какая-то фигура.
Знаю что просто, но не получается.
Помогите кто чем
... в идеале конечно небольшой код был бы очень кстати, хотя бы наводочка. smile

dmage

Дата 4.8.2007, 22:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 21.6.2007

Репутация: 1
Всего: 1

Прочитав первый раз пропустил слово "по контуру", поэтому сделал на Python через обход всей фигуры.
Для ускорения можно не добавлять в очередь точки, у которых все соседи одного цвета. Но при этом на вход придется давать граничную точку.

Код


#!/usr/bin/python
# coding: utf8
import Image ; Image.init( )

file = "./x.png";

im = Image.open( file )
startx, starty, endx, endy = im.getbbox( )
endx -= 1 ; endy -= 1

max_x, min_x, max_y, min_y = 0, 0, 0, 0 

def Fill( x, y, new_color ):
    pixels_queue = [ ]
    pixels_queue.append( (x, y) )

    global max_x, max_y, min_x, min_y
    max_x, min_x, max_y, min_y = x, x, y, y

    def Fill_PixelRoutine( pixel, new_color ):
        self_color = im.getpixel( pixel )
        im.putpixel( pixel, new_color )

        x, y = pixel
        
        global max_x, max_y, min_x, min_y
        if x > max_x: max_x = x
        if x < min_x: min_x = x
        if y > max_y: max_y = y
        if y < min_y: min_y = y
        
        check = (x-1, y)
        if x > startx and im.getpixel( check ) == self_color:
            if not check in pixels_queue: pixels_queue.append( check )
        
        check = (x+1, y)
        if x < endx   and im.getpixel( check ) == self_color:
            if not check in pixels_queue: pixels_queue.append( check )
            
        check = (x, y-1)
        if y > starty and im.getpixel( check ) == self_color:
            if not check in pixels_queue: pixels_queue.append( check )
        
        check = (x, y+1)
        if y < endy   and im.getpixel( check ) == self_color:
            if not check in pixels_queue: pixels_queue.append( check )

    counter = 0
    while pixels_queue: # not empty
        pixel = pixels_queue.pop( 0 )
        print counter, pixel
        Fill_PixelRoutine( pixel, new_color )
        if counter % 10000 == 0:
            im.show( )
        counter += 1

    print "(%d, %d) (%d, %d)" % ( min_x, min_y, max_x, max_y )
    im.show( )

Fill( 50, 30, 160 )

Это сообщение отредактировал(а) dmage - 4.8.2007, 22:50

maxim1000

Дата 4.8.2007, 22:48 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

хм... пройтись по всем чёрным пикселам и посчитать минимальные и максимальные значения для x и y...

--------------------

qqq

dmage

Дата 4.8.2007, 22:53 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 4
Регистрация: 21.6.2007

Репутация: 1
Всего: 1

maxim1000, такой способ не поможет, если на картинки 2 и более фигур.

maxim1000

Дата 4.8.2007, 23:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110

и то правда, это я подумал, что бинарная картинка представляет сам объект, который нам нужен

Это сообщение отредактировал(а) maxim1000 - 4.8.2007, 23:19

--------------------

qqq

DissDoc

Дата 5.8.2007, 08:43 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 463
Регистрация: 13.7.2006

Репутация: нет
Всего: нет

Может и много будет изображений на картинке. Но мне нужен был сам принцип понять. Спасибо. Сейчас с кодом разбираюсь.
Я пытался и матрицей 3х3 и 5х5 проходится - откровенно говоря путался в конечном итоге. =(

Earnest

Дата 17.8.2007, 19:04 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 7
Всего: 183

Вот, держи код C++ обхода контура методом "жука".

Код


///////////////////////////////////////////////////////////////////////////////////////////
// Определим, является ли точка граничной, т.е:
//        - точка удовлетворяет предикату IsOk
//        - имеет хотя бы одного "не Ok" 4-соседа
//        - имеет хотя бы одного "Ok" 8-соседа        (не изолирована)
template <class _PRED>
bool IsOutlinePoint(const POINT& pt,_PRED IsOk)
{
    if (!IsOk(pt)) return false;

    // проверяем 4-соседей
    int cnt[2] = { 0,0 };            // не-Ok-соседи, Ok-соседи
    for (CDir dir = 0; dir < 8; dir+=2)    
        cnt[IsOk(dir.Move(pt))]++;
    if (!cnt[0]) return false;        // нет пустых соседей
    if (cnt[1]) return true;
    
    // проверяем 8-соседей
    for (CDir dir=1; dir < 8; dir+=2)    
        if (IsOk(dir.Move(pt))) return true;

    return false;
}

///////////////////////////////////////////////////////////////////////////////////////////
// Прослеживание контура: предикат IsOk как в предыдущем алгоритме + накопитель точек Store
// с интерфейсом bool operator ()(const POINT&) должен возвращать false для прекращения
// цикла; он же отвечает за проверку замыкания
// Возвращаемое значение: true, если возврат произошел по инициативе Store, false - ошибка:
// начальная точка не является точкой границы (см. код)
// Начальная точка не заносится в Store!!!
template <class _PRED, class _STORE>
_STORE OutlineContour(POINT pt,_PRED IsOk,_STORE Store)
{
    if (!IsOutlinePoint(pt,IsOk)) { ASSERT(0); return Store; }

    // ищем пустую точку, задающую стартовое направление поиска
    POINT tmp;
    for (CDir dir=0; IsOk(tmp=dir.Move(pt)); ++dir);            

    while (true)
    {
        ASSERT(!IsOk(tmp));
        // pt - предыдущая точка границы и центр поиска; ищем внутреннюю точку
        POINT ptPrev = tmp;
        for ( ; !IsOk(tmp=dir.Move(pt)); ++dir, ptPrev=tmp);
        // сохраняем
        if (!Store(pt=tmp)) break;
        // ptPrev - последняя пустая точка; 
        // начальное направление след. итерации задается направлением на нее
        dir = CDir(pt,tmp=ptPrev);
    }
    return Store;
}

Здесь предполагается, что IsOk дает дает ответ на вопрос - закрашен ли пиксел.
STORE - накопитель точек. Если контур замкнулся, должен вернуть false.
Алгоритм предполагает, что первую точку найдешь сам, хотя бы сканируя растр и проверяя IsOutlinePoint
Вспомогательный классик CDir:

Код


///////////////////////////////////////////////////////////////////////////////////////////
// Направления на целочисленной решетке: ось X - вправо, ось Y - вниз
//  
//        3   2   1        
//          \ | /          
//        4 - 8 - 0 -+ X   
//          / | \          
//        5   6   7        
//         |            
//             +
//        Y
class CDir
{
public:
    enum { R=0,RU,U,LU,L,LD,D,RD,Z };

    CDir(int dir): m_dir(dir%8) { }
    CDir(POINT p,POINT q);                // направление из точки <p> в точку <q>

    operator int() const { return m_dir; }

    CDir& operator++();
    CDir  operator++(int);
    CDir& operator+=(int);
    CDir& operator--();
    CDir  operator--(int);
    CDir& operator-=(int);

    int   Dir () const;
    POINT Move(const CPoint& pt) const;
    SIZE    Step() const;

private:
    static int Dir(int dx,int dy);    // направление из точки <0,0> в точку <dx,dy>

private:
    int m_dir;
};

inline CDir::CDir(POINT p,POINT q)
{
    m_dir = Dir(q.x-p.x,q.y-p.y);
}
inline CDir& CDir::operator++()        
{ 
    m_dir++; return *this;    
}
inline CDir CDir::operator++(int)
{ 
    CDir tmp = *this; 
    ++(*this); 
    return tmp;    
}
inline CDir& CDir::operator--()        
{ 
    m_dir--; return *this;    
}
inline CDir CDir::operator--(int)
{ 
    CDir tmp = *this; 
    --(*this); 
    return tmp;    
}
inline CDir& CDir::operator+=(int n)
{ 
    m_dir += n;    return *this;    
}
inline CDir& CDir::operator-=(int n)
{ 
    m_dir -= n;    return *this;    
}
inline int CDir::Dir() const
{
    int dir = m_dir%8;
    if (dir < 0) dir +=8;
    ASSERT(dir >= 0 && dir < 8);
    return dir;
}
inline int CDir::Dir(int dx,int dy)
{        
    static int _dir[9] = { LU,U,RU,L,Z,R,LD,D,RD };
    if (dx < -1 || dx > 1 || dy < -1 || dy > 1) { ASSERT(0); return Z; }
    else return _dir[(dy+1)*3 + (dx+1)];
}
inline POINT CDir::Move(const CPoint& pt) const
{
    return pt + Step();
}
inline SIZE CDir::Step() const
{
    static SIZE    _inc[] = { {1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1} };
    return _inc[Dir()];
}

--------------------

...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »