A. Juozapavičius: "Lygiagretūs algoritmai"

Dalyko turinys:

Dalyko tikslas - suteikti studentams teorines ir praktines žinias apie lygiagrečius algoritmus, sudaryti galimybę įgyti patirties taikymuose, pereinant nuo nuoseklių prie lygiagrečių algoritmų. Paskaitų metu pirmiausia bus dėstomi kompiuterinės regos, vaizdų apdorojimo ir kompiuterinės grafikos algoritmai, kuriuos įsisavinus, reikės sukurti jų lygiagrečius analogus. Tuo tikslu studentams bus pateikta lygiagretaus programavimo ir lygiagretaus užduočių vykdymo aplinka: LAM/MPI, PVM, BLACS, ScaLAPACK, S3L, kurią jie galės realizuoti fakultete esančiuose Linux ir Sun klasteriuose.
Pasirenkant šį dalyką, studentams būtina turėti neblogai įsisavintas matematines žinias (matematinės analizės kurso apimtyje) ir programavimo C++ įgūdžius.

Darbas semestro metu:

Dalyko paskaitų metu studentams pateikiamos teorinės žinios. Praktinėms užduotims kiekvienas studentas (arba grupė studentų) pasirenka (arba jam/jiems paskiriama) temą - praktinę užduotį, kurią jis/jie nagrinėja teoriškai, parengia ir realizuoja praktiškai šiai užduočiai tinkamus algoritmus, parašydami atitinkamas kompiuterines programas. Po to studentai algoritmus analizuoja ir modifikuoja, sukurdami ar projektuodami jų išlygiagretintus variantus. Šiuos variantus studentai realizuoja praktiškai, parengdami tinkamas kompiuterines programas. Abu algoritmų variantus studentai lygina, o jų testavimo, lyginimo ir veikimo analizės rezultatus aprašo atskiruose dokumentuose.

Dalyko žinių vertinimas

Dalyko žinios vertinimos egzaminu. Egzamino vertinimui nustatomos tokios proporcijos:

• kokybiškai ir laiku išnagrinėta ir realizuota pasirinkta tema, atlikta pagal aukščiau aprašytus reikalavimus, yra vertinama iki 4 balų (jei studentai užduoties vykdymo metu yra iniciatyvūs, atlieka darbo daugiau, nei užduotyje reikalaujama, užduotis gali būti vertinama ir daugiau balų)
• 2005 m. kovo 31 d. ir balandžio 7 d. yra numatomas užduočių algoritmų ir jų lygiagrečių variantų pristatymas ir svarstymas, kuris gali būti vertinamas iki 1 balo
• semestro metu yra numatytas teorinis testas, kuris gali būti vertinamas iki 1 balo, šio testo temos bus įjungtos į dalyko egzamino klausimus.
• testo turinį sudarys praktinių užsiėmimų metu nagrinėtos temos iš LAM/MPI, kurių aprašą galima rasti čia. Tikslesnės temos ir reikalavimai žinioms testui ir egzaminui bus pateikti vėliau,
• žinios, parodytos sesijos egzamino metu, bus vertinamos iki 4 balų.

Duomenis praktinėms užduotims, su kuriais turi dirbti programos, sudaro medicininiai vaizdai (rentgeno nuotraukos arba rentgeno filmai, zip failas, apie 21 MB), kurie yra pasiekiami čia. Tiesinio, Gauso ir medianos filtrų programos/vaizdai bus čia patalpinti vėliau. Numatomos tokios praktinės užduotys:

1. Realizuoti tiesinio filtro, Gauso filtro, medianos filtro algoritmus ir sukurti bei realizuoti jų lygiagrečius variantus. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Užduotį atlieka: K. Aliulis, T. Andrikys
2. Realizuoti Canny-Edge-Detector algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: M. Bobinas, A. Burokas - darbas įvertintas 10 balų (A. Burokui)
3. Realizuoti Roger-Detector ir Sobel-Detector algoritmus ir sukurti bei realizuoti jų lygiagrečius variantus. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: Š. Belickas
4. Realizuoti Corners algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Realizuoti interfeisą, kuris surastus kraštus atvaizduoja originaliame vaizde. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: A. Daugaravičius, L.Reklaitis
5. Realizuoti Range-Surf-Patches algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba) pagal H, K klaidų kiekį ir sudarytų skiaučių dydį. Užduotį atlieka: M. Gedminas, A. Gridziuška
6. Realizuoti Hough_Lines algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: V. Domarkas, P. Vaitkevičius
7. Realizuoti Hough_Circles (pagal Hough_Curves) algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: M. Janulis - darbas įvertintas 10 balų
8. Realizuoti Eucl_Ellipse_Fit algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: T. Januševičius
9. Realizuoti Alg_Ellipse_Fit algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: J. Kameneckaitė
10. Realizuoti Rob_Ellipse_Fit algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: V. Karosas
11. Realizuoti SNAKE algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: E. Kiela, A. Krasauskas - darbas įvertintas 10 balų
12. Realizuoti SNAKE algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus esant įvairioms parametrų alfa, beta, gama reikšmėms. Užduotį atlieka: P. Krilius - darbas įvertintas 10 balų
13. Realizuoti Corr_Matching algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: G. Kurklietytė
14. Realizuoti Feature_Matching algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: J. Liubertas, R. Petkus
15. Realizuoti Eight_Point algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: G. Šipelytė
16. Realizuoti Epipoles_Location algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: T. Mikėnas, A. Nikšas
17. Realizuoti Rectification algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: A. Pavlov, J. Liubinskas
18. Realizuoti TRIANG algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: P. Petrov - darbas įvertintas 10 balų
19. Realizuoti Euclid_Rec algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: D. Piatov - darbas įvertintas 10 balų
20. Realizuoti Uncal_Stereo algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: A. Rekerta, M Kriščiūnas - darbas įvertintas 10 balų
21. Realizuoti Constant_Flow algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: M. Skripka, E. Račkauskas
22. Realizuoti Feature_Point_Matching algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: R. Šaltis, E. Matijošius - darbas įvertintas 10 balų
23. Realizuoti Kalman_Tracking algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: L. Šlepetys, R. Urbanavičiūtė
24. Realizuoti Motstruct_From_Feats algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: G. Vaira, K. Janilionytė
25. Realizuoti Motstruct_From_Flow algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: T. Valiukas, J. Veršelis
26. Realizuoti Change_Detection algoritmą ir sukurti bei realizuoti jo lygiagretų variantą. Analizuoti ir palyginti šių algoritmų veikimą (pagal jų greitį, reikalingos atminties dydį), pateikti teorinius vertinimus. Palyginti algoritmų rezultatus duotiems vaizdams ir jų filtruotiems analogams (tiesinio, Gauso ir medianos filtrų pagalba). Užduotį atlieka: T. Zulgis
27. Veido detektavimo lygiagretūs algoritmai. Užduotį atlieka L. Virbalas - darbas įvertintas 10 balų

Kurso turinys, vadovėliai, konspektai ir kita medžiaga:

1. Pagrindinis vadovėlis, kuris naudojamas šiame kurse yra: Emanuele Trucco, Alessandro Verri. Introductory Techniques for 3-D Computer Vision, Prentice Hall, New Jersey, 1998
2. įvadinė dalis, kuri gali būti reikalinga užduotims atlikti, yra išdėstyta 1-2-ame knygos skyriuose (p.p. 1 - 50)
3. 1-os užduoties medžiaga yra išdėstyta 3-ame knygos skyriuje (p.p. 51 - 66)
4. 2 - 5 užduočių medžiaga yra išdėstyta 4-ame knygos skyriuje (p.p. 67 - 94)
5. 6 - 12 užduočių medžiaga yra išdėstyta 5-ame knygos skyriuje (p.p. 95 - 122)
6. 13 - 20 užduočių medžiaga yra išdėstyta 7-ame knygos skyriuje (p.p. 139 - 176)
7. 21 - 26 užduočių medžiaga yra išdėstyta 8-ame knygos skyriuje (p.p. 177 - 218)
8. knygos turinys ir papildoma informacija yra išdėstyta indeksiniame knygos skyriuje (p.p. iii - xvii)

   ---

   į kursų sąrašą
   į Katedros svetainę
   į Lietuvos baroko aprašą

   ---