[C++] Filtr medianowy


(Blady214) #1

Witam,

 

zwracam się do Was z problemem dotyczącym napisania programu realizującego filtrowanie medianowe dla plików PPM zapisanych w formacie ASCII, na wstępie chcę zaznaczyć, iż raczej nie będę potrzebował pomocy w pisaniu kodu, a jedynie zrozumieniu logiki tego filtru.

 

Plik PPM zapisany w formacie ASCII przechowuje w nagłówku informacje na temat rozmiaru grafiki np:

512 228

W następnych wierszach są zapisane informacje na temat wartości poszczególnych pikseli np:

125
75
44
26

No i tutaj pojawia się pierwsze pytanie. Czy zbudować z tego macierz dwuwymiarową o podanych wymiarach i zastosować filtr dla macierzy dwuwymiarowej, czy też wczytać to jako listę i realizować filtr jednowymiarowy?

 

Jeżeli ma to być traktowane jako macierz z użyciem filtru 2-wymiarowego, to pojawia się kolejne pytanie. Zakładając, że fragment naszej macierzy wygląda następująco:

11 25 36 67 125 222 46
55 79 89 65 123 210 78
44 25 22 11 179 102 56

a rozmiar filtra wynosi 3 x 3, to do pierwszej próbka, dla której zostanie zastosowany filtr będzie wyglądała następująco:

11 25 36 
55 79 89 
44 25 22

Jak będzie wyglądała następna próbka, czy poruszam się cały czas o 3 piksele (najpierw w prawo, później w dół), czy poruszam się po jednym pikselu?


(GL1zdA) #2

Wydaje mi się, że rozmiary to szerokość i wysokość, więc ja bym traktował to jak obrazek 2D - skorzystaj więc z filtru dwuwymiarowego. Co do przesuwania się, to przesuwasz co 1 piksel.


(kostek135) #3

Bez różnicy ponieważ każdą tablicę n-wmiarową możesz przedstawić w sposób spłaszczony (wpisz w google array flatten). Tablice jednowymiarowe zajmują mniej pamięci oraz lepiej cache-ują się w pamięci podręcznej procesora. A ich używanie po napisaniu makra nie różni się od 2D.

 

Po jednym.

PS znalazłem jeszcze pseudokod, który powinien rozwiać wszelkie wątpliwości

http://atol.am.gdynia.pl/tc/Radzienski/Mediana.htm


(Blady214) #4

Sporo wątpliwości zdążyłem już rozwiać, aczkolwiek zostało mi jedno pytanie, ponieważ wzoruję się na tym: http://angeljohnsy.blogspot.com/2011/03/2d-median-filtering-for-salt-and-pepper.html i tutaj jest napisane, by krawędzie macierzy dopełnić zerami. Dlaczego, to akurat rozumiem, ale czy aby na pewno mają tam być zera, a nie na przykład powielona ostatnia kolumna/wiersz?


(kostek135) #5

Widzisz, problem filtrowania jest taki sam jak tworzenia hashy. Którego algorytmu nie użyjesz w swojej implementacji będzie zawierał jakąś stałą “od czapy”. A na pytanie czemu ta liczba jest lepsza niż inne uzyskasz odpowiedź, bo daje lepsze wyniki, tak samo jest tutaj.


(Blady214) #6

kostek135  takiej odpowiedzi potrzebowałem, co prawda już jestem na końcowym etapie, czyli zapis przefiltrowanej grafiki do pliku, aczkolwiek dzięki wielkie za wskazówki, jak starczy mi czasu (w co szczerze wątpię), to zajmę się też optymalizacją.


(Blady214) #7

Sądziłem, że nie będę prosił o pomoc z kodowaniem, aczkolwiek chyba będzie ona jednak niezbędna, ponieważ kompilator pluje mi błędem, który nie bardzo wiem jak rozwiązać.

sources: malloc.c:2369: sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.

RUN FINISHED; Aborted; core dumped; real time: 300ms; user: 0ms; system: 60ms

Pojawia się on wewnątrz jednej z funkcji odpowiedzialnej za pobieranie części, w której wybierana jest mediana, a dokładniej w poniższym fragmencie kodu:

for (int j = startX; j < tX; j++){        
        for (int i = startY;i< tY;i++){
            part[tmp] = outputMap[j][i];
            tmp++;
        }
    }

Dokładniej rzecz biorąc po 112 wywołaniu tej funkcji dostaję błąd. Poniżej wklejam jeszcze kod całej funkcji:

void filter::getPart(int startX, int startY){
 //pobiera do listy elementy, z których ma zostać policzona mediana;
    int mediana, tmp = 0, tX = startX + sampleSize, tY = startY + sampleSize;
    part = new int[sampleSize];
    cout<<"StartX:"<<startX<<endl<<"Start Y:"<<startY<<endl;
    
    for (int j = startX; j < tX; j++){        
        for (int i = startY;i< tY;i++){
            part[tmp] = outputMap[j][i];
            tmp++;
        }
    }  
    
    sortList();
    mediana = calcMedian();
    switchValue(mediana, startX, startY);
    
   // delete [] part;
}

Dla mniejszych plików wszystko działa poprawnie, zatem na 100% jest to problem związany z zarządzaniem pamięcią, tylko… jak go rozwiązać?


(kostek135) #8

Skoro dla małych jest dobrze, jak duże są te większe pliki?


(Blady214) #9

Pliki, na których próbowałem przetestować mają rozdzielczości 325 x 200px oraz 528 x 220 px i w obu przypadkach program się wysypywał.

Zwalnianie pamięci zakomentowałem, ponieważ jeżeli jest ono aktywne, to program również się wykłada, niestety w tej chwili nie jestem w stanie zrzucić logu błędu. Jeśli chodzi o sprawdzanie wycieków, to nigdy z żadnego narzędzia nie korzystałem.


(kostek135) #10

Moim zdaniem to nie problem tej funkcji, bo tu po dodaniu delete wszystko jest w porządku. Problem może leżeć gdzie indziej, warto użyć czegoś do sprawdzania wycieków.


(Blady214) #11

 

Masz 1000% rację, jak będę w domu, to poprawię tą część kodu i zobaczę jaki będzie wynik oraz odkomentuję zwalnianie pamięci i w razie błędu również postaram się wkleić jego log. Dzięki wielkie za udzieloną do tej pory pomoc.


(Blady214) #12

kostek135 , dzięki wielkie po stokroć, rzeczywiście z pamięcią błąd był w miejscu, które wskazałeś. Niestety pojawił się inny problem, a mianowicie moja błędna interpretacja standardu PPM, gdyż zakładałem, że każdy piksel jest reprezentowany przez jedną wartość, a tutaj okazuje się, że każdy z nich jest reprezentowany przez 3 wartości, przez co dochodzą mi kolejne wymiary tablicy i teraz już niestety nie wiem jak to ugryźć… Teraz tablica ma wymiar [x],[y],[3] (ilość wartości per piksel). Taką tablicę też mogę spłaszczyć? Wydaje mi się jednak, że spłaszczenie takiej tablicy nie przyniesie mi żądanego efektu.

 

//edit:

 

Poradziłem sobie częściowo, pracuję na pgm P2, gdzie macierz jest dwuwymiarowa :slight_smile: Został tylko problem wycieku pamięci w pętli: 

for (int j = startX; j < tX; j++){        
        for (int i = startY;i< tY;i++){
            part[tmp] = outputMap[j][i];
            tmp++;
        }
    }

Dla elementów małych (np. 10x10) jest OK, po wczytaniu nieco większej grafiki dostaję błąd _segmentation fault, _najprawdopodobniej przy ostatnim przebiegu pętli.


(Blady214) #13

Problem rozwiązany, błąd miałem przy zapisie pliku, jednak niestety musiałem gdzieś coś namieszać, bo plik wynikowy nie jest taki, jakbym oczekiwał…


(kostek135) #14

Odpowiem zbiorczo:


(Blady214) #15

Tego się akurat domyśliłem, dlatego nie wstawiałem całego kodu :slight_smile:

 

Analizując program również myślałem, że tutaj popełniam błąd, aczkolwiek wewnątrz tej funkcji wszystko przebiega prawidłowo. Mediana, jest to już docelowa wartość pixela, która ma zostać zamieniony. startX oraz starY są początkowymi punktami, do których dodawana jest jeszcze zaokrąglona w dół połowa próbki (dla próbki o rozmiarze 3, będzie to 1), dzięki czemu otrzymuję pozycję pixela w całej macierzy obrazka, która ma zostać zamieniona i w jej miejsce wpisuję wyliczoną wcześniej medianę.

 

Dziękuję Ci bardzo za pomoc i zaangażowanie, niestety w terminie nie uda mi się tego poprawić (chyba, że nagle mnie oświeci), więc w weekend skonsultuję to z profesorem na uczelni i dam znać, gdzie się pomyliłem.


(Blady214) #16

Witam ponownie,

 

niestety muszę zażegnać pisanie tego projektu, ponieważ mimo szczerych chęci oraz wielu prób i błędów nie potrafię stwierdzić,  gdzie pojawia się rzeczony błąd. Operacje związane z plikami - zapis/odczyt oraz eksport/import macierzy mam na 100% poprawny, zatem występuje gdzieś błąd w implementacji samego filtra, ale nie jestem w stanie określić gdzie, gdyż wszystkie operacje są wykonywane zgodnie z algorytmem. Poniżej przedstawiam obraz wejściowy oraz wynik działania programu:

 

Wynikowy: 75ww.jpg