Proiect SDA 2014-2015: Diferență între versiuni

De la WikiLabs
Jump to navigationJump to search
(Pagină nouă: <!-- Analysis of Algorithms: Project 2 Deadline: March 1 The project involves application of sorting algorithms to median filtering of an image, which is a technique for smoothing ...)
 
 
(Nu s-au afișat 12 versiuni intermediare efectuate de același utilizator)
Linia 1: Linia 1:
<!--
== Descriere ==


Analysis of Algorithms: Project 2
Scopul acestui proiect este realizarea unei aplicații care să aplice un filtru median pe o imagine. Aceasta este o tehnică folosită pentru a uniformiza o imagine cu zgomot. Pentru fiecare pixel din imagine, filtrarea constă în selectarea unei ferestre de n x n pixeli, centrată pe pixelul sursă, calcularea medianei nivelurilor de gri din fereastră, și înlocuirea pixelului original cu valoarea mediană. Mediana este definită ca valoarea din mijlocul secvenței sortate. De exemplu, pentru următoarea fereastră de 3 x 3:


Deadline: March 1
The project involves application of sorting algorithms to median filtering of an image, which is a technique for smoothing a "noisy" image. For each pixel of an image, the filtering procedure considers an (n x n) window centered on that pixel, computes the median of gray-level values in the window, and replaces the original pixel with the median value. The median is defined as the middle value in a sorted sequence. For example, consider the following (3 x 3) window of pixels:
  11 90 74
  11 90 74
  71 14 92
  71 14 92
  20 87 68
  20 87 68
The sorted sequence of these pixels is <11, 14, 20, 68, 71, 74, 87, 90, 92>, and the middle of the sequence is 71, which is the median of the window; thus, the filtering procedure will replace the center pixel with 71.
The result of replacing all pixels with median values is a smoothed image, with almost no background noise, which improves the effectiveness of image-recognition algorithms. On the negative side, the new image is blurrier than the original, that is, it looks like an unfocussed monitor.


Your task is to implement sorting algorithms for median filtering. You should copy the source files median.c and mysort.c to your account; in addition, you need the old files imageio.h and imageio.c. The median.c file contains the filtering procedure, which calls three sorting functions from mysort.c. You should write the code for these functions: insertion_sort, quick_sort, and counting_sort. The mysort.c file already includes the names and argument declarations for the sorting functions, and you need to code their bodies. You should not modify any files except mysort.c, and you should submit only mysort.c to heath@suntan.eng.usf.edu.
Secvența sortată a acestor pixeli este <11, 14, 20, 68, 71, 74, 87, 90, 92>, iar valoarea din mijloc este 71, care este valoarea mediană a acestei ferestre. Prin urmare, procedura de filtrare va înlocui valoarea din centrul ferestrei (14) cu valoarea mediană: 71.
 
Rezultatul înlocuirii tuturor pixelilor din imagine cu valorile mediane este o imagine uniformizată, aproape fără zgomot de fundal, lucru care îmbunătățește performanțele algoritmilor de recunoaștere de imagini. Partea negativă este că în noua imagine se pierd detaliile.
 
== Cerință ==
Programul vostru trebuie să citească o imagine în format [https://en.wikipedia.org/wiki/Netpbm_format PGM], să aplice o filtrare mediană cu fereastă de '''n''' x '''n''' (cu '''n''' specificat la execuția programului) folosind un algoritm de sortare specificat tot la execuție, și să scrie imaginea rezultată într-un fișier nou. Dacă fișierul executabil obținut la compilare se numește '''filtru.exe''', atunci programul va fi rulat astfel:
 
filtru.exe <fisier_intrare> <fisier_iesire> [ins|qs|cnt] <n>
 
Unde ''ins'' - insertion sort, ''qs'' - quick sort, ''cnt'' - counting sort, iar '''n''' este dimensiunea ferestrei. Spre exemplu:
 
filtru.exe enb.pgm enb_filtered.pgm qs 3
 
Această comandă va rula filtrul cu o fereastră de 3 x 3 pixeli, folosind quick sort pentru sortare pe fișierul de intrare '''enb.pgm''' și va scrie rezultatul în '''enb_filtered.pgm'''.
 
Programul va afisa în consolă timpul de execuție la finalul rulării.
 
Se va răspunde la următoarele întrebări:
* Care algoritm de sortare e mai eficient din punct de vedere al timpului de execuție pentru o fereastră de 3 x 3? Dar pentru una de 20 x 20?
* Care este complexitatea în timp, în funcție de dimensiunea imaginii (m) și a ferestrei (n)?
* Care este dimensiunea maximă a ferestrei pentru care imaginea filtrată poate fi încă recunoscută?
 
În plus, pentru fiecare din cei trei algoritmi de sortare, se va realiza un grafic al timpului de execuție în funcție de '''suprafața''' ferestrei în intervalul (3 x 3) - (20 x 20).
 
== Observații ==


You should then apply the filtering procedure to the enb.pgm file, which is a noisy image of the Engineering Building II. To download the image, point the mouse, click the right button, and then select "Save Link As" or "Save Target As" in the resulting menu. To apply the filtering, compile median and use the following syntax to run it:
* Pentru pixelii care sunt prea aproape de margine pentru a putea selecta o fereastră de dimensiunea cerută, se vor duplica pixelii din margine. De exemplu, pentru colțul din stânga sus al unei imaginii:


median -n # [-insertion | -quick | -counting] input.pgm output.pgm
34 12 54 23 53
21 45 23 67 33
23 64 23 62 35
34 67 46 23 12
14 66 43 23 67
23 63 35 23 63


The "-n #" argument specifies the window size, for instance, "-n 5" means the (5 x 5) window; the second argument is the choice of sorting; and the last two arguments are the input and output file. For example, you may run the filtering with a (5 x 5) window, using quick_sort:
Pentru aplicarea unei ferestre de 3 x 3 pe pixelul cu valoarea 34 (din stânga sus), se duplică pixelii cu valorile 21, 34 și 12 în felul următor:


median -n 5 -quick enb.pgm filtered.pgm
34 34 12
34 34 12 54 23 53
21 21 45 23 67 33
    23 64 23 62 35
    34 67 46 23 12
    14 66 43 23 67
    23 63 35 23 63


The procedure produces a smoothed PGM image and displays two numbers: the window area (in pixels) and the filtering time (in seconds). For example, if you run "median -n 5 -quick ...," it may display "25 1.950000," which means that the window is 25 pixels and the running time is 1.95 seconds.
* Pentru specificarea de argumente la execuția programului, se folosesc parametri pentru funcția '''main''', conform [http://www.cprogramming.com/tutorial/c/lesson14.html acestui] tutorial.
* Pentru testare puteti folosi imaginea ftp://hermes.arh.pub.ro/public/imageset/enb.pgm (acest fișier poate fi vizualizat ca imagine cu programul [https://inkscape.org/en/ Inkscape]).
* Dimensiunea ferestrei (n) este întotdeauna impară.


You should run the filtering procedure with different sorting functions, and with window sizes ranging from (2 x 2) to (20 x 20). For each of the three sorting techniques, plot the dependency between the window area and running time, and include it into your report. In addition, answer the following questions in the report:
== Evaluare ==


Which sorting function gives the best running time for the (3 x 3) window? Which is the best for the (20 x 20) window?
*Se punctează următoarele:
What is the dependency of the running time on the image size and window area?
** funcționalitatea implementată conform cerinței - 20p
What is the maximal window size for which the smoothed image is still recognizable for the human eye?
** răspunsul la întrebările cerute și graficele realizate corect - 10p
** formatarea codului - 5p
** memoria alocată dinamic dezalocată corect la finalul execuției programului - 5p


-->
* Acest proiect valorează 40 de puncte din nota totală la SDA. Se cer minim 20 de puncte din 40 pentru promovarea laboratorului și implicit pentru intrarea în examen.
* Proiectul va fi prezentat public de către autor și va fi evaluat, acordându-se o notă între 0 și 40.
* Autorului i se vor pune 5 întrebări exclusiv din codul scris în cadrul proiectului și partea teoretică asociată. Orice întrebare la care se răspunde greșit, sau nu se răspunde, va fi penalizată cu 5 puncte. Rezultatul este că examenul se poate pica și cu un proiect de 40 de puncte.

Versiunea curentă din 26 august 2015 17:31

Descriere

Scopul acestui proiect este realizarea unei aplicații care să aplice un filtru median pe o imagine. Aceasta este o tehnică folosită pentru a uniformiza o imagine cu zgomot. Pentru fiecare pixel din imagine, filtrarea constă în selectarea unei ferestre de n x n pixeli, centrată pe pixelul sursă, calcularea medianei nivelurilor de gri din fereastră, și înlocuirea pixelului original cu valoarea mediană. Mediana este definită ca valoarea din mijlocul secvenței sortate. De exemplu, pentru următoarea fereastră de 3 x 3: 

11	 90	 74
71	 14	 92
20	 87	 68

Secvența sortată a acestor pixeli este <11, 14, 20, 68, 71, 74, 87, 90, 92>, iar valoarea din mijloc este 71, care este valoarea mediană a acestei ferestre. Prin urmare, procedura de filtrare va înlocui valoarea din centrul ferestrei (14) cu valoarea mediană: 71.

Rezultatul înlocuirii tuturor pixelilor din imagine cu valorile mediane este o imagine uniformizată, aproape fără zgomot de fundal, lucru care îmbunătățește performanțele algoritmilor de recunoaștere de imagini. Partea negativă este că în noua imagine se pierd detaliile.

Cerință

Programul vostru trebuie să citească o imagine în format PGM, să aplice o filtrare mediană cu fereastă de n x n (cu n specificat la execuția programului) folosind un algoritm de sortare specificat tot la execuție, și să scrie imaginea rezultată într-un fișier nou. Dacă fișierul executabil obținut la compilare se numește filtru.exe, atunci programul va fi rulat astfel: 

filtru.exe <fisier_intrare> <fisier_iesire> [ins|qs|cnt] <n>

Unde ins - insertion sort, qs - quick sort, cnt - counting sort, iar n este dimensiunea ferestrei. Spre exemplu: 

filtru.exe enb.pgm enb_filtered.pgm qs 3

Această comandă va rula filtrul cu o fereastră de 3 x 3 pixeli, folosind quick sort pentru sortare pe fișierul de intrare enb.pgm și va scrie rezultatul în enb_filtered.pgm.

Programul va afisa în consolă timpul de execuție la finalul rulării.

Se va răspunde la următoarele întrebări:

  • Care algoritm de sortare e mai eficient din punct de vedere al timpului de execuție pentru o fereastră de 3 x 3? Dar pentru una de 20 x 20?
  • Care este complexitatea în timp, în funcție de dimensiunea imaginii (m) și a ferestrei (n)?
  • Care este dimensiunea maximă a ferestrei pentru care imaginea filtrată poate fi încă recunoscută?

În plus, pentru fiecare din cei trei algoritmi de sortare, se va realiza un grafic al timpului de execuție în funcție de suprafața ferestrei în intervalul (3 x 3) - (20 x 20).

Observații

  • Pentru pixelii care sunt prea aproape de margine pentru a putea selecta o fereastră de dimensiunea cerută, se vor duplica pixelii din margine. De exemplu, pentru colțul din stânga sus al unei imaginii:
34 12 54 23 53
21 45 23 67 33
23 64 23 62 35
34 67 46 23 12
14 66 43 23 67
23 63 35 23 63

Pentru aplicarea unei ferestre de 3 x 3 pe pixelul cu valoarea 34 (din stânga sus), se duplică pixelii cu valorile 21, 34 și 12 în felul următor: 

34 34 12
34 34 12 54 23 53
21 21 45 23 67 33
   23 64 23 62 35
   34 67 46 23 12
   14 66 43 23 67
   23 63 35 23 63
  • Pentru specificarea de argumente la execuția programului, se folosesc parametri pentru funcția main, conform acestui tutorial.
  • Pentru testare puteti folosi imaginea ftp://hermes.arh.pub.ro/public/imageset/enb.pgm (acest fișier poate fi vizualizat ca imagine cu programul Inkscape).
  • Dimensiunea ferestrei (n) este întotdeauna impară.

Evaluare

  • Se punctează următoarele:
    • funcționalitatea implementată conform cerinței - 20p
    • răspunsul la întrebările cerute și graficele realizate corect - 10p
    • formatarea codului - 5p
    • memoria alocată dinamic dezalocată corect la finalul execuției programului - 5p
  • Acest proiect valorează 40 de puncte din nota totală la SDA. Se cer minim 20 de puncte din 40 pentru promovarea laboratorului și implicit pentru intrarea în examen.
  • Proiectul va fi prezentat public de către autor și va fi evaluat, acordându-se o notă între 0 și 40.
  • Autorului i se vor pune 5 întrebări exclusiv din codul scris în cadrul proiectului și partea teoretică asociată. Orice întrebare la care se răspunde greșit, sau nu se răspunde, va fi penalizată cu 5 puncte. Rezultatul este că examenul se poate pica și cu un proiect de 40 de puncte.
Adus de la „https://wiki.arh.pub.ro/index.php?title=Proiect_SDA_2014-2015&oldid=2990”