Despre ce este proiectul si care este scopul acestuia?
Articolul de mai jos va cuprinde o aplicatie care face denoise unor imagini de tip PGM P2 (vom vedea mai jos ce sunt acestea si ce reprezinta). Aplicatia mi-a fost sugerata facultativ in cadrul facultatii. Parundu-mi-se interesanta am ales sa fac o descriere pe larg a modului in care este gandita si functioneaza aplicatia. Voi aborda secvential modul de gandire in cele ce urmeaaza
I. Breviar teoretic
- Ce este un filtru median?
În teoria procesării semnalelor, un filtru este un dispozitiv sau un proces care înlătură o parte nedorită dintr-un semnal. Există nenumărate tipuri de filtre, dar cel pe care îl vom studia în această temă este filtrul median. Acest tip de filtru este utilizat în mod curent pentru eliminarea zgomotului (puricilor) din imagini.
Rezultatul aplicării unui filtru median pe o imagine se poate observa mai jos:
- Tipul de fisier de procesat, implicit PGM tip P2
În memoria unui calculator, o imagine alb-negru este salvată memorând nivelul de gri pentru fiecare pixel, nivel care este întotdeauna în intervalul [0; 255], unde 0 înseamnă negru și 255 înseamnă alb.
PGM este un acronim ce vine de la Portable GrayMap. Există două formate de fișier PGM – P5, care este un fișier binar, și P2 care este un fișier text. Un fișier în format P2 are următoarea structură:
- Pe prima linie se află codul P2 care semnalizează tipul fișierului.
- Orice linie care începe cu # se consideră comentariu și se ignoră.
- Următoarea linie validă conține două valori (width și height), ce reprezintă lățimea și înalțimea imaginii
- Următoarea linie validă conține o valoare ce reprezintă valoarea maximă al unui pixel care va fi întâlnit în imagine (deci valoarea corespunzătoare nivelului de alb).
- Pe următoarele linii se află width x height valori, separate prin whitepace-uri, ce reprezintă nivelurile de gri pentru fiecare pixel, de la stânga la dreapta și apoi de sus în jos.
Exemplu:
- Aplicarea unui filtru median
Un filtru median se aplică întotdeauna pe o fereastră de n x n în jurul fiecărui pixel din imaginea originală, unde n este un număr întreg pozitiv impar (3, 5, 7, etc.). Astfel, pentru fiecare pixel din imaginea originală, se extrag toți vecinii săi dintr-o fereastră de n x n în jurul lui. Acești pixeli sunt plasați într-un vector care se sortează. Valoarea pixelului din imaginea filtrată este valoarea din mijlocul vectorului sortat. Pentru o fereastra de 3 x 3:
Ce fac la margini?
La limită, acolo unde fereastra de n x n depășește marginea imaginii, aceasta este bordată prin repetiția pixelilor de la margine. Fie colțul din stânga sus al imaginii originale:
Dacă se aplică un filtru de 5×5 pentru pixelul din stânga sus (cu valoarea 10), atunci e nevoie de o fereastră pătrată de 5×5 în jurul lui:
Cu bold este elementul din colț, iar pentru a obține fereastra de 5×5, s-au replicat elementele de pe margine.
Cerință
Dându-se un algoritm de sortare dintre BubbleSort și MergeSort, o dimensiune de fereastră și două nume de fișiere cu format PGM-P2, unul de intrare și altul de ieșire, să se aplice un filtru median de dimensiunea specificată pe fiecare pixel din imaginea de intrare, folosind algoritmul specificat pentru sortarea ferestrei, și să se scrie imaginea filtrată în fișierul de ieșire. Ambele fișiere sunt în format PGM-P2.
Date de intrare
De la tastatură se dă, pe o singură linie, tipul de algoritm (bubble sau merge), dimensiunea ferestrei, și numele celor două fișiere (de intrare și de ieșire), toate separate prin unul sau mai multe caractere whitespace.
Exemplu:
merge 3 test_in.pgm test_out.pgm
II. Descrierea programului
Vom discuta pe baza codului asa cum am spus, secvential. In primul rand, stiind ca primim de la intrare un fisier, trebuie mai intai sa il deschidem si sa citim datele care ne intereseaza din el. Pentru asta ne vom folosi de o functie de tip bool readPGM.
Tipul de functie ales. De ce bool?
Tipul bool memoreaza doar 2 valori, 0 sau 1, in aritmetica logica True sau False. Deocamdata ne intereseaza sa verificam daca fisierul nostru se deschide cu success si daca reusim sa citim din el ce ne intereseaza, respectiv valorile din el, lungimea, inaltime si maxVal.
Argumentele functiei? De ce sunt declarate ca referinta? Ce este vector<vector <uint8_t>>& image?
Transmiterea prin referinta ne ofera doua avantaje cruciale pentru tipul nostru de aplicatie. In primul rand, ne dorim sa ne folosim de valorile pe care le vom citi atunci cand vom crea outputul, care evident va avea aceleasi dimensiuni. Astfel, la apelarea functiei in cadrul functiei main() voi avea nevoie de volorile lor, lucru posibil doar prin transmiterea prin referinta. Daca nu le declar ca referinta la apelare, functia ar fi lucrat doar cu niste copii locale ale valorilor (doar in interiorul functiei readPGM), iar la iesire nu m-as fi ales decat cu niste valori arbitrare.
Un alt avantaj al transmiterii prin referinta este eficienta. Acest lucru devine puternic atunci cand vom citi si prelucra valorilor nivelurilor de gri din imagine cu ajutorul lui vector<vector<uint8_t>>& image. Acesta este defapt o matrice de tip uint8_t.
Buclele while citesc si verifica daca ce s-a citit este valid.
Aici are loc o parcurgere secventiala a vectorului unde sunt introduce valorile citite din fisier. De ce am folosit static_cast aici si nu direct image[i][j]=pixel?
Am declarat pixel de tip int pentru ca ma astept sa primiesc inclusive fisiere corupte sau gresit scrise care pot avea inauntrul lor o valoare mai mare decât 255 sau o valoare negativă. Este doar o masura de singuranta. Astfel sunt nevoit sa fac cast inapoi la uint8_t.
Daca totul a decurs cum trebuie intorc true semnaland ca citirea a avut loc cu success.
Functia de scriere
Acum argumentele latime, inaltime si maxVal nu mai sunt pasate prin referinta deoarece scrierea fisierului este ultimul pas si nu mai am nevoide de valorile lor pentru a face alte operatii. In rest, acele doua for-uri imbricate au rolul de a trata fisierul ca o matrice, de a-o parcurge si de a scrie in el valorile.
Functia uint8_t getPixel(vector<vector<uint8_t>>& image, int x, int y, int latime, int inaltime) si de ce este importanta.
Rolul ei este de a gestiona corect marginile imaginii incat sa nu iesim din imagine in momentul aplicarii filtrului.
Rezultat: Dacă filtrul cere pixelul de la coordonatele (-1, 5), funcția va returna valoarea pixelului de la (0, 5). Dacă cere (50, 1000) într-o imagine de înălțime 500, va returna valoarea pixelului de la (50, 499).
Urmeaza apoi functiile de sortare. Nu vom trece in amanunt prin ele deoarece diferenta o constituie doar diferenta de eficienta dintre ele. Se poate folosi orice algoritm de sortare. Tot ce am facut a fost sa respect cerinta.
De ce avem doua functii mergeSort?
Prima (cea cu 3 argumente) este funcția de bază, recursivă, a algoritmului Merge Sort. Rolul ei este de a descompune vectorul în sub-secțiuni din ce în ce mai mici și, ulterior, de a le combina înapoi în ordine sortată. Cea de a doua are rolul de o “impacheta”, adica sa simplidice modul de apelare reducandu-l la un singur argument. Are rol in simplificarea codului.
Aplicarea filtrului
Intr-un final ajungem si la aplicarea efctiva a filtrului.
La ce folosim variabila k?
Variabila k calculează deplasarea de la centrul ferestrei (pixelul curent (x, y)) până la margine. Dacă marimeFereastra este 3, k este 1. Fereastra se extinde de la -1 la +1 față de centru.
Primele 2 bucle imi incep parcurgerea fisierului.
Ce rol are window?
Se creaza un vector temporar care va stoca toate valorile pixelilor din fereastra de filtrare.
Urmeaza Bucla de fereastra. În interiorul celei mai interne bucle, se calculează coordonatele efective din imaginea de intrare:
int pixelX = x + wx;
int pixelY = y + wy;
Apoi valoarea obtinuta este adaugata in vectorul window.
Problema este ca si terminata. Functia main() asigura doar legatura cu utilizatorul. Pentru a rula introducem de exemplu merge 3 test_in.pgm test_out.pgm. In urma executiei ni se va crea un fisier test_out.pgm in radacina unde am programul salvat. Atentie, tot acolo trebuie sa se afle si test_in.pgm!
III. Note de final:
Problema mi-a fost sugerata in interiorul cursului de SDA (Structuri de date si algoritmi), Facultatea de Electronică, Telecomunicaţii şi Tehnologia Informaţiei din carul Universitatii Nationale de Stiinta si Tehnologie Politehnica Bucuresti.
Titular curs Radu Hobincu.
Noiembrie 2025.
Surse: https://cppreference.com/
*M-am ajutat de AI in rezolvarea problemei si intelegerea si rezolvarea aparitiilor unor bug-uri.