Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

problem z algorytmem bfs do segmentacji

Ostatnio zmodyfikowano 2013-01-06 11:11
Autor Wiadomość
setius
Temat założony przez niniejszego użytkownika
problem z algorytmem bfs do segmentacji
» 2013-01-03 23:08:42
Witam,

Nie jestem z wykształcenia informatykiem ale z konieczności czasami coś muszę sam napisać. Mam problem z pewnym fragmentem mojego programu. Na wejściu mam tablicę 2-wymiarową boolowską zawierającą monochromatyczny obraz. Tworzę listę w której umieszczam współrzędne wszystkich punktów o wartości true (zawarte w strukturze jako argumenty x i y). Następnie, za pomocą rekurencyjnej funkcji, wyszukuję wszerz (algorytm bfs) wszystkie punkty sąsiadujące z pierwszym ze znajdujących się w liście punktów. Dana grupa punktów wpisywana jest do nowej tablicy 2-wymiarowej int jako piksele o takiej samej i innej od pozostałych wartości jasności. Niestety coś się psuje i nie wychodzi mi z rekurencji... zamieszczam fragment programu i z góry dziękuję za wskazówki (pewnie to jakiś szczegół jak zawsze...)

C/C++
/*deklaracje*/

int ** utworz_tablice( int, int );
void szukaj( std::list < struct piksel >*, std::list < struct piksel >::iterator, int **, int );

/*używane we fragmencie zmienne*/

int i, j, szerokosc, wysokosc;
bool ** tab_bool;
int ** tab_region;
int wskaznik; //sluzy przy segmentacji do nadawania wartosci danym segmentom koherentnym
std::list < piksel > nr; //lista do przechowywania współrzędnych interesujących nas pikseli
std::list < piksel >::iterator it2;
struct piksel pix;

struct piksel
{
    int x;
    int y;
};

/*tworzenie tablicy do której mają być wpisywane zbiory punktów w skali szarości*/

tab_region = utworz_tablice( wysokosc, szerokosc ); //tworzenie tablicy
for( i = 0; i < wysokosc; i++ ) //wstępne zapełnanie tablicy zerami
{
    for( j = 0; j < szerokosc; j++ )
    {
        tab_region[ i ][ j ] = 0;
    }
}

/*szukanie współrzędnych jasnych pikseli i wpisywanie ich do listy*/

for( i = 0; i < wysokosc; i++ )
{
    for( j = 0; j < szerokosc; j++ )
    {
        if( tab_bool[ i ][ j ] == true )
        {
            pix.x = i;
            pix.y = j;
            nr.push_back( pix );
        }
    }
}

/*pętla w której wywoływana jest funkcja rekurencyjna aż do opróżnienia listy*/

wskaznik = 0;
it2 = nr.begin();
while( nr.size() > 0 )
{
    wskaznik++;
    tab_region[ it2->x ][ it2->y ] = wskaznik;
    szukaj( & nr, it2, tab_region, wskaznik );
    std::cout << nr.size() << '\n';
}

/*funkcja do segmentacji*/

void szukaj( std::list < struct piksel > * nr, std::list < struct piksel >::iterator it1, int ** tab_region, int wskaznik )
{
    int x, y;
    x = it1->x;
    y = it1->y;
    nr->erase( it1 );
    std::list < struct piksel >::iterator it2;
    for( it2 = nr->begin();( it2 != nr->end() ); ++it2 )
    {
        if(( abs( x - it2->x ) + abs( y - it2->y ) ) == 1 )
        {
            tab_region[ it2->x ][ it2->y ] = wskaznik;
            std::cout << nr->size() << '\n';
            szukaj( nr, it2, tab_region, wskaznik );
        }
    }
    return;
}
P-72879
DejaVu
» 2013-01-04 00:02:07
Program się wywala czy zwraca błędne wyniki?

/edit:
cofam pytanie - wywala się :P Nie możesz usuwać iteratora po którym chcesz dalej iterować, a to właśnie robisz.
1. wchodzisz w funkcję
2. uruchamiasz pętlę for
3. bierzesz 'jakiś iterator'
4. wchodzisz w funkcję
5. USUWASZ ITERATOR
6. bla bla ...
7. kończy się pętla
8. wracasz do funkcji (powrót z pkt 4.)
9. iterujesz do następnego elementu, ALE iterator ten już jest nieprawidłowy, BO został on usunięty w kroku 5.
P-72881
Mrovqa
» 2013-01-04 08:12:50
Hmm, pierwszy raz widzę, by ktoś implementował BFSa na rekurencji. BFSa jest wygodniej i łatwiej zaimplementować normalnie na kolejce. Na rekurencji zazwyczaj implementuje się DFSa (bo masz już 'naturalny' stos).
P-72887
setius
Temat założony przez niniejszego użytkownika
» 2013-01-04 20:28:25
dziękuję za odpowiedzi. Teraz trochę edytowałem funkcję ale nadal mi ją wywala z powodu błędu segmentacji.

C/C++
void szukaj( std::list < struct piksel > * nr, std::list < struct piksel >::iterator it1, int ** tab_region, int wskaznik, int x, int y )
{
    std::list < struct piksel >::iterator it2;
    int x1, y1, i;
    i = nr->size();
    int j = 0;
    for( it2 = nr->begin();( it2 != nr->end() ) &&( j < i ); ++it2 )
    {
        x1 = it2->x;
        y1 = it2->y;
        if(( abs( x - x1 ) + abs( y - y1 ) ) == 1 )
        {
            tab_region[ x1 ][ y1 ] = wskaznik;
            if( it2 == nr->end() ) return;
           
            it2 = nr->erase( it2 );
            std::cout << nr->size() << '\n';
            szukaj( nr, it2, tab_region, wskaznik, x1, y1 );
            //return;
        }
        j++;
    }
    return;
}

Nie wiem za bardzo jak zabrać się do pisania bfs'a przy użyciu stosu. W liście mam wczytane współrzędne wszystkich pikseli białych. Muszę znaleźć wszystkie grupy tych pikseli i każdej grupie nadać inną jasność - wpisując je do tablicy reprezentującej obraz w skali szarości. Przy stosie mógłbym wyciągać tylko górne piksele. jeśli mamy 3 piksele leżące w jednej linii to jeśli wyjmę najpierw 1szy potem 2gi potem 3ci, to zostaną uznane za tę samą grupę. Jeśli jednak zostanie najpierw wybrany 1szy potem 3ci, to utworzą się 2 różne grupy.... Wydaje mi się, że muszę brać 1 piksel i sprawdzać czy w tablicy są jego sąsiedzi (jak tak, to dodaję ich do grupy piksela), potem z sąsiadami robić to samo...
P-72932
DejaVu
» 2013-01-04 20:34:16
Dalej się wywala z tego samego powodu. Usuwasz iterator, a potem chcesz z niego korzystać.
P-72934
setius
Temat założony przez niniejszego użytkownika
» 2013-01-04 20:37:50
wydawało mi się, że jeśli napiszę:

it2 = nr->erase( it2 )

,to wstawię na miejsce it2 wskaźnik na jego sąsiada...
P-72938
DejaVu
» 2013-01-04 20:50:35
Ale... jeżeli usuniesz ostatni prawidłowy element to następny jest iterator nieprawidłowy, a mimo wszystko na nim dalej chcesz pracować.
P-72941
setius
Temat założony przez niniejszego użytkownika
» 2013-01-06 11:11:21
Wydawało mi się, że sprawdzałem czy element jest ostatni czy nie. W każdym razie teraz uprościłem algorytm i nadal miałem błędy. Okazało się, że po prostu za dużo pamięci zjada ta rekurencja - wstawiłem zmienną zamykającą funkcję jeśli będzie miała za dużo wywołań... może później zrobię to na stosie - ale muszę mieć czas żeby zrozumieć jak to się robi.

Mam teraz inny problem. Otóż wczytuję sobie w programie zdjęcie w formacie BMP 24bit i przerzucam każdy kolor RGB do osobnej tablicy 2D. W formacie BMP piksele zaczynają się zawsze po offsecie 54 (tutaj jest trochę informacji http://smsoftdev-solutions.blogspot.com/2011/01/reading-bmp-image-directly-in-c-part-1.html). Później wczytuję po kolei kolory ale spotkałem się z pewną dziwną anomalią - w zależności od zdjęcia w co 0 ,1, 2 lub 4 linijce muszę usuwać pojedynczy znak, bo mi się rozjeżdża obraz wynikowy (robi się coś w rodzaju rombu - rozchodzą się linijki). Obecnie dla każdego zdjęcia muszę sobie indywidualnie dobierać ten parametr:

C/C++
fseek( obraz, 54, SEEK_SET );
for( j = 0; j < wysokosc; j++ )
{
    for( i = 0; i < szerokosc; i++ )
    {
        fread( rgb, sizeof( unsigned char ), 1, obraz );
        blue = * rgb;
        fread( rgb, sizeof( unsigned char ), 1, obraz );
        green = * rgb;
        fread( rgb, sizeof( unsigned char ), 1, obraz );
        red = * rgb;
        tab_red[ j ][ i ] = red;
        tab_green[ j ][ i ] = green;
        tab_blue[ j ][ i ] = blue;
    }
    if( j % dzielnik == 0 ) fread( rgb, sizeof( unsigned char ), 1, obraz );
   
}
fclose( obraz );

to jest strasznie upierdliwe i nie mam pojęcia z czym związane. Myślałem, że to może coś z kompresją ale parametr "compression type (0=none, 1=Run Length Encoding (RLE)-8, 2=RLE-4)" dla każdego otwieranego przeze mnie zdjęcia wyświetla 0;

Czy ktoś z użytkowników forum ma może pomysł z czym to jest związane?
P-73121
« 1 »
  Strona 1 z 1