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...)
int ** utworz_tablice( int, int ); void szukaj( std::list < struct piksel >*, std::list < struct piksel >::iterator, int **, int );
int i, j, szerokosc, wysokosc; bool ** tab_bool; int ** tab_region; int wskaznik; std::list < piksel > nr; std::list < piksel >::iterator it2; struct piksel pix;
struct piksel { int x; int y; };
tab_region = utworz_tablice( wysokosc, szerokosc ); for( i = 0; i < wysokosc; i++ ) { for( j = 0; j < szerokosc; j++ ) { tab_region[ i ][ j ] = 0; } }
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 ); } } }
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'; }
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; }
|
|
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. |
|
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). |
|
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. 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 ); } 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... |
|
DejaVu |
» 2013-01-04 20:34:16 Dalej się wywala z tego samego powodu. Usuwasz iterator, a potem chcesz z niego korzystać. |
|
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... |
|
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ć. |
|
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: 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? |
|
« 1 » |