Schnell OCR

OCR simplu şi rapid

5 ian 2011, laboratorul de APP

Functia programului

• Intrare:– Fisier sau lista fisiere imagine. Suporta jpg, tiff, png in

functie de disponibilitatea bibliotecilor de sistem

• Iesire:– Textul recunoscut in imagine

• Precizari calitate OCR– Fara detectia spatiilor– Poate pune la dispozitie si un calificativ de similaritate

(claritate) al caracterului recunoscut– Nu ignora caracterele cu calificativ scazut de

similaritate

Descriere algoritm

• einfach_trennen - ia ca parametru o imagine si intoarce o lista dublu inlantuita cu posibilele litere

• vektor_generieren - calculeaza "semnatura" literei - un vector de caracteristici.– alcatuit din 8 metode - ambele sensuri pe 4 directii (orizontala,

verticala, doua diagonale)– fiecare metoda salveaza coeficienti (de fapt coordonate) in

vector

• vektor_vergleichen - calculeaza diferenta intre doi vectori, adica eroarea patratica: cu cat mai mica, cu atat simbolurile sunt mai probabile sa coincida

Descriere algoritm

• zeichenliste – lista inlantuita de litere probabil– Utilizata implementarea list.h din kernelul de Linux

#define list_entry(ptr, type, member) \

(type *)((char *)(ptr) - (char *)(&((type *)0)->member))

• Comparare iterativa cu toate mostrele hardcodate in kennen_muster.cpp, selectarea celei cu eroare minima

Fişiere de testare

• Fişiere de rezoluţie diferită – 1, 4, 16, 100 megapixeli, jpg, tiff, png– Obţinute prin umplerea cu text– Obţinute prin scalarea primeia

Fişiere de testare• Iată un studiu comparativ al rulării programului cu fişierele obţinute

prin umplere cu text şi cu cele obţinute prin scalare:

Profiling

• Valorile timpilor de procesor folositi de proceduri, sortate dupa timpul exclusiv (fara subprocedurile apelate)

OMP

• Avantaje– Usor de implementat– Fara probleme de sincronizare / deadlock

• Dezavantaje– Flexibilitate redusa de paralelizare– Mult overhead– Aproape imposibil de paralelizat prelucrari pe

liste

OMP

Dimensiune test Timp var. seriala Timp var. OMP (12 thr.)

1 Mpx 6,4 4

4 Mpx 17,9 17

16 Mpx 57,1 35

100 Mpx 341,7 220

Pthreads

• Prima incercare – calcul paralel al similaritatii cu elementele din fisierul de mostre

Pthreads

• A doua incercare – decodare paralela a literelor din imagine (un nivel mai sus)

Pthreads

• Varianta 1 – overheadOH_1 = (overhead_creare_thread-uri +

overhead_eliberare_thread-uri) * Nr_thread-uri * Nr_caractere

• Varianta 2 – overheadOH_2 = (overhead_creare_thread-uri +

overhead_eliberare_thread-uri) * Nr_thread-uri

• OH1 / OH2 = Nr_caractere (poate fi foarte mare!!!)

Pthreads

Dimensiune test Timp var. seriala Timp var. Pthreads (12 thr.)

1 Mpx 6,4 1

4 Mpx 17,9 6

16 Mpx 57,1 11,9

100 Mpx 341,7 78

MPI

• Broadcast bitmap la workeri• Numarare simboluri, repartizarea punctelor de

start si finish pentru fiecare worker– Isend-ul neblocant asigura transmisia fara overhead

• Asteptarea blocanta a rezultatelor– Asigura valabilitatea datelor in context. Rezultatele

sunt concatenate in ordinea in care au fost plasate sarcinile

– Situatie de timp de stall nedorit: nodurile care primesc primele sarcinile sunt mai lente decat cele care le primesc spre final

MPI

Dimensiune test Timp var. seriala Timp var. MPI (12 proc)

1 Mpx 6,4 4

4 Mpx 17,9 8

16 Mpx 57,1 17

100 Mpx 341,7 82

Comparatii

Verificare corectitudine

Simplu! Diff, sau..

Comparatii

Lucrul în echipă

Concluzii

• Flexibilitatea Pthreads a permis obtinerea unei optimizari mai eficiente decat OpenMP

• MPI a obtinut rezultate bune, scalabile pe hardware; eficient cand calculele au o pondere mai mare decat dimensiunea datelor transmise intre noduri

• Un proiect interesant pentru

• utilizarea bibliotecii de manipulare fisiere media OpenCV

• folosirea listei inlanutite din kernelul Linux

• modul de utilizare al clasificatorilor pentru elemente grafice

• calcul paralel si distribuit

Dan Greceanu, dgreceanu@gmail.com

si

Mihnea Simian, contact@mesimian.com

va multumesc pentru atentie!

Nu sunati pana in 10 sau dupa 23. Serios.

Întrebări?