Uvod u raspoznavanje uzoraka 8670590549 [PDF]

Zitiervorschau

Zn.k: 8810 p Izdsnje: Prof. dr. LUDVIK GYERGYEK, dipl. ing. Prof. dr. NIKOLA PAVEŠiĆ, dipl. ing. Prof. dr. SLOBODAN RIBARIĆ, dipl. ing. UVOD U RASPOZNAVANJE UZORAKA Recenzenti: Prof. dr. VLADIMIR MUWEVIĆ Prof. dr. STANKO TURK Izdslf.�: Izdavačka radna organizacija TEHNIĆKA KNJIGA Zagreb, Juri�ćeva 10 Za izdBIRla odgolfBrB: Ing. ZVONIMIR VISTRIĆKA Urednik izdBniB: Mr. ŽEUKO HORVATIĆ,dipl. ing. Tehni�ki urednik: SLAVKO VLAHOV .Jezi�ns recenzijB: JOSIP ŽiVKOVIĆ Korigirali: AUTORI Tisak: BIROGRAFIKA, Subotica Tiskano u 2000 primjeraka TiAk dOlfmn: U LISTOPADU 1988.

© G yergyek, Pave§ić, Ribarić, 1988. YU ISBN 86-7059-054-9

Ovo djelo izdano je uz novčanu pomoć Samoupravne interesne zajednice :;l:Oanosti SR Hrvatske kao društveno vrijedna znanstvena knjiga.

Prof. dr Ludvik Gyergyek, dipl. ing.

redovni

član SAZU

Prof. dr Nikola Pavelič, dipl. ing. Prof. dr Slobodan Ribarič, dipl. ing.

UVOD U RASPOZNAVANJE UZORAKA Primjena računala i mikroračunala u sustavima za raspoznavanje uzoraka

TEHNI(;KA KNJIGA. ZAGREB

PREDGOVOR

Raspoznavanje uzoraka predstavlja temelje umjetne percepcije poimanja svijeta strojem. Stroj s percepcijom ima sposobnost da podražajima iz vanjskog svijeta, koji su prisutni na senzorima, dodjeljuje pojmove i na temelju njih i njihovih odnosa zaključuje o svijetu koji ga okružuje. Teorija raspoznavanja tako omogućava oblikovanje prijateljskih korisničkih sučelja ekspertnih sustava i nji­ hovo izravno povezivanje s okolinom. Pristup teoriji raspoznavanja u ovoj knjizi prividno je klasičan, međutim pored teorije nenumeričkog raspoznavanja složenih uzoraka (npr. slika prirodnih prizora) opisani su i p ostupci učenja (određivanje funkcija odlučivanja pomoću algoritama perceptrona, učenje klasifikatora s mrežom memorijskih elemenata i sL). Ti postupci učenja imaju svoje srodne postupke učenja na području umjetne inteligencije, te učenja u neuronskim mrežama. Na primjer, postupak grupiranja nazvan k-srednjih vrijednosti (poglavlje 3) odgovara Kohonenovoj samoorgani­ zirajućoj mreži, Gaussov klasifikator (poglavlje 5) odgovara perceptronu, postupak k-bližih susjeda odgovara višerazinskom perceptronu, a optimalni klasifikator Hamm ingovoj neuronskoj mreži. Neuronske mreže su upravo ono područje paralelnih arhitektura računala koje najviše obećava. . Postupci grupiranja (poglavlje 3) uPotrebljavaju se kao sredstvo za istra­ živanje strukture velikih skupova višedimenzionalnih podataka, a u kontekstu raspoznavanja uzoraka, za "otkrivanje"ra�reda uzoraka koji čovjeku nisu bili poznati. Raspoznavanje uzoraka nije ograničeno samo na rješavanje problema unutar granica čovjekove percepcije, već se bavi i rješava probleme raspoznavanja uzo­ raka izvan njih (npr. raspoznavanje vrste potresa i njegova predikacija, raspozna­ vanje slika u različitim dijelovima spektra, raspoznavanje mikroskopskih struktura itd.). Drugi dio knjige opisuje izvedbe sustava za raspoznavanje, arhitekturu računala za obradu slika i model visokoparalenog računala piramidne organizacije. Knjiga je namijenjena studentima elektrotehnike, strojarstva, računarskih znanosti, informatike ali i studentima društvenih znanosti koji u analizi ponašanja složenih sustava (društvo, zajednica, veliki ekonomski sustavi i sl.) moraju upo­ trebljavati elemente teorije raspoznavanja. Knjiga je namijenjena znanstvenicima i stručnjacima koji rade na projektiranjU, oblikovanju i upotrebi strojeva i sustava s ugrađenom inteligencijom i umjetnom percepcijom. Sadržaj knjige odgovara gradivu predmeta "Raspoznavanje uzoraka" koji se predaju na elektrotehničkim fakultetima u Ljubljani i Zagrebu.

6 Zahvaljujemo se Fakulteti za elektrotehnika, Ljubljana, Elektrotehničkom fakultetu u Zagrebu, Tehničkoj vojnoj akademiji KoV JNA, Zagreb, Razisko­ valnoj skupnosti Slovenije, SIZ-u za znanost SR Hrvatske i Humboldtova; fondaciji i svima onima koji su na bilo koji način doprinjeli da ovo djelo bude pred Vama. Zagreb, Ljubljana, ruj�a

1988.

Autori

SADRžAJ

UVOD U l.

RASPOZNAVANJE

Ralpoznavaaje uzoraka.

UZORAKA.

.

. .. .. . . .. . .. . . . .... . . . .. .. .. ... .. .

II

.. ...... ... .... .. .. . . . .. . .. ... . . .. .. .. .. . . ... .

1 3

l.l Uvod .. . .. .. .. .. .. .. . . . .. .. .. .. .. ... .. .. .... .. . .... . . . . .. ... . ...... 1.2. Model sustava za raspoznavanj e . . . .. .. .. ..... .. .... . . .. . . . ... ... .. .. ...... 1.3. Skup uzoraka za učenje i skup uzoraka za ispitivanje. . ... .. .. ... .... .. .. .. .. .... 1.4. Primjer raspoznavanja uzoraka. . . .. .. .. .... ........ . .. .. ........... . .... .. LS. Primjeri upotrebe sustava za raspoznavJlnl� : .. .....................' .. .. .... .. 1.6. Odnos umjetne inteligencije i raspoznavanja uzoraka................ ... . . ....... 1.7. Literatura . . . . . .... . . . . . ..... . . ... . ' .. ..... ..... . .. .... . ... .. .........

1 3 IS 18 19 2 0 2 1 22

l. Izbor OtIDOYII.Ih 2.1. 2.2. 2.3. 2.4. 2.S.

.

značajki uzorka. ... .... ..... .. .. . .

. . .. ..... .. ...... .. . . . .

2 3

Uvod. . ... .. .. .. .. .... ... .. .... .. ..... ... . .. .. .. ..... .. .. .. .. .... .. Linearne transformacije. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nelinearne transformacije . . ..... .. .. .. ....... .... .. .. .... . .. .... .. .. . ... Kodiranje osnovnih značajki uzoraka . . . .. .. .. .. . . ... .. .. .... . .. .. .. .. .. . ... Literatura. . . . . . . ........... . ..... ... ... ..... .... . .. .. .. . .. ... .... ...

2 3

24 32 3 3 3 6

3. AaaIiZa arrupa. .. .. .. . .. .... .. .. .... .. . . .. . .. .. .. .. .. ..... .. .... . . ... .

3 7

Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . : . Mj�re � ličnosti . . . .. .... .. . .... .. .. .. .... . ...... .. .. ..... .. .. .... .. .. . . : KrIt� I' �PU'8nJ� ... .. . . . .. .. .. . . .. ..... .... .. .. .. .. ... .. .. .. .. .. .. : : Iterativni postuPCI grupiranja . . .. .. . . .. .. . . . . . . . .. ...................... Postupci grupiranja na temelju teorije grafova . . . .. . . . . . . . . . . . . .. . . . . . . . . ... . . Literatura. . .... . ... ... . . .. .. .. .. .. .. .. ... .... . . .. .. .. ... . . .. .. .... ..

3 7 3 8 39

3.1. 3.2. 3.3. 3.4. 3.S. 3.6.

4.

Uneame fuakdje odlufiv_j..

.

... .. .... ... ... ......... .... ............ .

4.1. Uvod.. ...... . . . ... .... . .... .. .. ... . . ...... . . .. . . .. ......... .... ... 4.2. Linearne funkcije od1učivanja i granice ... .. .. ... . ... .. . . .. .. ... .. .. .. .. .. .. 4.3. Uopćene linearne funkcije odlučivanja .. .. .. ..... ... . .. .. . . ..... .. .. .. . . .. .. 4.4. Gradijentni postupci . . . . . . . . ...... . . . . . .... . . . .. . . . . . . . ..... . .. . . . . . ' . .. 4.S. Postupak učenja s potencijalnim funkcijama. . .. ... . ... .. .. .. ..... .. .. .. . . .. . . 4.6. Literatura. . . . ............ .. ... ... ...... . . . ........ ............ ......

5. Stadad&. S.1. S.2. S.3. S.4. S.S. S.6. S.7.

Idaai8kaclj. uzoraka. ...... .. .... . . . ...... .. ....... .. . ... ....

Uvod.. ... .. .. .. . . ... . ..... . . .... .. ....... .. .. .. .. ..... .. .. .. .... .. Jednostavan test dviju hipoteza .....................................: ..... Bayesov kriterij odlučivanja . .. . . . ',' . ... . . .. ..... ........................ Pravilo minimaks . . ................ ... ............ ............... ... . . ProJirenje na M razreda (M hipoteza) . . .. .. .. .. ... .. .. .. .. .... ..... .. .. .. .. Qqena parametra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Literatura... . . . .. .. .... .. ... .. .. .. .. .. ....... . . .. .. ..... .... .. .... ..

40 Sl S S S 6 56 57 59 6 1 70 74 7S 7S 7S 76 78 80

84

87

8 6. NenumerU!ko (siDtBktič!Jro) raspoznavanje

uzoraka

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . •

6.1. Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Elementi formalne teorije jezika .......................................... . 6.3. Raspoznavanje sintaktičkih struktura-tipovi automata ............: . . . . . . . . . . . . . . 6.4. Strukturno razvrstavanje uzoraka......................................... . 6.S. Sintaktičko raspoznavanje uzoraka pomoću stohastičkih jezika ..................... 6.6. Sintaktičko opisivanje uzoraka ........................................... . 6.7. Automatsko generiranje gramatike ......................................... 6.8. Literatura...........................................................

PRIMJERI SUSTAVA ZA RASPOZNAVANjE...............................

18

BI IJO 91 94 'Tl 99

103 106

.

107

7. Primjena ortogona1ne Haarove transformacije u raspoznavanju i automatskom dlJaposticiranJu sipala EKG ......................................... .

109

7.1. Uvod .............................................................. 7.2. Haarova transformacija signala EKG ....................................... 7.3. Raspoznavanje signala EKG ............................................. 7.4. Lesterova dijagnostička metoda ...........................: . . . . . . . . . . . . . .. 7.S. Literatura................................................: . . . . . . . . . .

109

III lIS

120 124

8. Sustav za raspoznavanje brojčano-slovnih znakova......................... .

12S

8.J.' Uvod ............................................................. . 8.2. Konfiguracija sustava za raspoznavanje .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3. Utjecaj translacije, rotacije i povećanja znakova na Fourierove koeficijente - teorijska osnova sustava . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • . . . . . 8.4. Izbor značajki. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • . . 8.S. Postupak raspoznavanja...............................................'.. 8.6. Literatura............., . . . . . . . . .. ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12S 130

9. Sustav za raspoznavanje rukom pisanih broJa-nih znakova ...................

9.1. Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • • : 9.2. Dvodimenzionalni prilagođeni filtri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • 9.3. Sustav za raspoznavanje zasnovan na dvodimenzionalnim prilagođenim filtrima ....... 9.4. Učenje sustava za raspoznavanje ..................................., . . • • • • 9.S. Sinteza sustava za raspoznavanje rukom pisanih brojčanih znakova ................. 9.6. Rezultati raspoznavanja. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • 9.7. Literatura. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • •

13l

137

138 143

144 144 144

14.5 146 146 1.50 1.53

.

1S4

10.1. Uvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • • • • • 10.2. Sustav za automatsku identifikaciju otisaka prstiju ......................•••••• 10.3. Strukturno razvrstavanje uzoraka otisaka prstiju . . . . . . . . . . . . . . . . . . . . . . . • • • • • • • 10.4. Literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • • • • •

1S4

10. Sustav za k1asifiltaclJu otiuka prstiju...................................

156

161 167

ll. Arbitektura računala

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. • • • • •

168

ILI. Uvod .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

• • • • • •

168 170 173 183 187 192 196

.

.

.

.

.

.

.

.

.

.

.

11.2. Klasifikacija arhitekture računalskih sustava . . . . . . . . . . . . . . . . . . . . . . . . . . • . . • • • • 11.3. Arhitektura tipa SISD von Neumannovo računalo . . . . . . . . . . . . . . . . . . . . . . • . • • 11.4. Arhitektura tipa MISD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • • • • • 11.5. Arhitektura tipa SIMD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • . . • 11.6. Arhitektura tipa MIMD ............................................... l l.7. Stogovna arhitektura računalskih sustava ................................... 1 1.8. Literatura ..................................................••.••.•• 12. Računala upravljana tokom podataka ........ '.

200

.

201

12.1. Uvod ..........." . . . . .. . . . . . . . . . . . . . . . . . . . ... . . . . . . . . . . . . . . . . . . . . 12.2. Računalo s upravljačkim tokom i kritika von Neumannove arhitekture ..............

201 202

.

.

.

.

.

.

.. .. .......

. . . . . . . .

9 12.3. Model paralelne obrade.. ..... . .. . .... .. ... .. .. ... .. .. ... .. . .... ... . ... 12.4. Računala upravljana tokom podataka . ... . .. .. . . ... . . .. ... . ....... . . . . . . . .. 1 2.5. Multiprocesorski sustavi upravljani tokom podataka ..... ....... .... .. .. .. .... . 12. 6. VLSI procesor upravljan tokom podataka.. . ... . ...: .................... .. . . 1 2.7. Literatura.. . . . . . .... . .. . . . .. . . . . . .. ... . .... . .................... ...

203 208 212 215 217

13. Arhitektura ra� za obradu slika .

.. ... ...... ....... . . ........ ......

219

1 3.1 . Uvod .... . ...... . .. ... . . ...... .. .. . ... ... . ....... . ... ... . . . . ...... 13.2. Oprema za obradu slike.. ....... .... ... ..... . . . ............. ... . .. . .... 1 3.3. Paralelne arhitekture računala za obradu slika. . ........ ... .. ........ .. . . . . . . . 1 3.4. Literatura.... . .. .... ... . . ... . . .. . . . .. .. . . .. .. .... . .... .. .... ..... . .

219 225 227 251

.

.

... .. . . . .. .

253

1 4. 1 . Uvod . . . . . . . . . . . . . . . . . • . .. ... . . . ... .. .. ... ..... ..... .. ... .. .... . . . 14.2. Obrada slike primjenom sustava mikroračunala. ..... . . .. ....... .. ...... ... . . . 14.3. Mikroprocesorski klasifikator brojčanih znakova ... . .. . .. . . . . . ... ...... .... . .. 14.4. Sustavi za automatsko raspoznavanje govora. . . .. ...... . ..... ... . . . .... . .... . 14.5. Osnovne komponente sustava za strojni vid . ...... . . ......... .. . ..... ..... . . 14.6. Literatura.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

253 253 2 61 2 69 279 289

IS. MOdel procesora za obradu l raspoznavanje slika. ... .... .. .. .. .. ..... .... .

290

1 5.1 . Uvod . . ....... . . . .. .. ...... . .... .. ..... ... ..... .. ... .. .. .... ... . .. 1 5.2. Paralelizam u obradi i raspoznavanju slika . .. ..... . ..... . .. ........... . . .... 1 5.3. Hijerarhija procesora.. ... ... ... .... .. .. ... ......... .......... ..... .... 1 5.4. Paralelizam na razini slikovne operacije . . . . .. ... . . . ... .. . .. . . " .... . ...... 15.5. Model računala R . . ... ..... .. .. . ..... ... .. . . . ......... ... . .. . . . ...... 1 5.6. Dva primjera ocjene stupnja paralelnosti . . . . .. . .. .. . . ....... . . . ... .. . . . . . . . 15.7. Literatura . . . ..... . . . . . . .. .. .. . . . . . . . ...... .. . . ..'.' ....... ... .. ... ..

290 292 293 299 301 304 308

14. PrimJena mikroprocesora u sustavima za raspoznavanje uzoraka.

Kazalo pojmova . . . ....... . .. . ....... . ... ...... .. . .. . .. . .. .. .. .. ... ..

311

1.

RASPOZNAVANJE UZORAKA

(Prof. dr. Ludvik Gyergyek, dipL ing., prof. dr. Nikola Pavešić, dipL ing., prof. dr. Slobodan Ribarić, dipL ing.)

1.1. UVOD Raspoznavanje je osnovno svojstvo ljudskog bića, odnosno svih živih bića. Raspoznajemo u svakom trenutku našeg života. I upravo sada dok čitate ovaj tekst raspoznajete slova, bjeline i riječi. Covjek raspoznaje objekte koji ga okružuju, kreće se među njima i uspostavlja odnose izmedu njih. Uzroci, u najširem značenju te riječi, jesu opisi objekata i sredstvo kojim tumačimo svijet koji nas okružuje. Ljudsko biće je vrlo savršen informacijski sustav upravo zbog superiornog svojstva raspoznavanja. Kao dijete čovjek najprije nauči razlikovati vizualne uzorke (lice svoje majke, oca i dr.), zvu�ne uzroke (govor, glazbu, šum, ... ), dodirne uzorke (toplo, hladno, ...) itd. S vremenom se djetetu izoštrava sposobnost raspoznavanja, pa je ono sada već sposobno razlikovati na licu osmijeh od ljutnje, razlikovati prijatelja u grupi ljudi i razumjeti što on kaže, razlikovati različite glasove ljudi i različite vrste glazbe, razlikovati umjetničke slike različitih autora i slično. Osim raspoznavanja ftzi�Jdh uzoraka koji pobuđuju naša osjetila (predmeti, geometrijska tijela, biča koja nas okružuju, znakovi na papiru, prikaz elektromagnetskih signala na zaslonu radara i st), čovjek raspoznaje i pojmovne, odnosno apstraktne uzroke. Tako, na primjer, matematičar razlikuje dobro od lošeg rješenja, otkriva elegantan dokaz, sociolog ili psiholog u svojim istraživanji­ ma nalazi uzorke i razvrstava ih u pojedine grupe i sL Raspoznavanje takvih apstraktnih uzoraka naziva se pojmovno raspoznavanje (engl. conceptual recognition). Iako čovjek od samog rođenja neprestano raspoznaje fizičke i apstraktne uzorke i na temelju toga se snalazi u svijetu koji ga okružuje, te saobraća s drugim ljudima, vrlo bi teško mogao opisati postupak raspoznavanja. Na primjer, teško bi objasnio na temelju kojih značajki razlikuje glasove različitih govornika. Vještina raspoznavanja razvija se tisućljećima, međutim znanost o raspozna­ vanju uzoraka nalazi se u povojima. Tek u posljednja tri desetljeća pokušavaju znanstvenici rasvijetliti to područje, otkriti njegove zakonitosti i postaviti teorijske temelje raspoznavanja uzoraka. Osnovni motivi istraživanja na području ra$pOzna­ vanja uzoraka jesu (Proc. of the IEEE, 1972):

14

l. RASPOZNAVANJE UZORAKA

"IntelektualI}a radoznalost", odnosno traženje odgovora na pitanje: Kako oblikovati i konstruirati stroj kojega će perceptivni odgovori biti slični čovjekovim? Odgovor na to izazovno pitanje može voditi k rješenju problema koje se skriva u pitanju kako biološki sustavi obrađuju informacije. Razvoj strojeva koji će omogućiti efIkasno saobraćanje između čovjeka i drugih strojeva. Taj motiv ima izuzetno značenje u saobraćanju čovjeka s računalom (npr. unos podataka u računalo pomoću glasa, razvoj i usa­ vršavanje grafičkih ulaznih i izlaznih jedinica, unos podataka s dokumen­ ta i sL). Intelektualna pomoć, odnosno oblikovanje i konstrukcija strojeva koji izvode određene operacije brže, točnije i sigurnije od čovjeka. Na pri­ mjer, automatsko čitanje adresa i razvrstavanje poštanskih pošiljaka, razvrstavanje satelitskih snimaka, dijagnostika bolesti i sl. Problemi raspoznavanja uzoraka tijesno se prožimaju s većim brojem znan­ stvenih područja. Mnoge ideje, posebno u ranim fazama razvoja teorije raspozna­ vanja uzoraka, crpljene su iz neurofIziologije. Kao i svako znanstveno područje, teorija raspoznavanja uzoraka zasniva se na upotrebi matematičkog aparata, pri čemu se služi različitim matematičkim područjima: od klasičnih matematičkih metoda, matematičke logike pa sve do teorije razmazanih skupova (engl. fuzzy set). Metode iz područja obrade informacija, automatskog upravljanja, formalnih jezika također su u tijesnoj vezi s raspoznavanjem uzoraka (S. Ribarić, 1986) . Navedimo neke osnovne pristupe raspoznavanju uzoraka: heuristički pristup, jezični ili sintaktički pristup i matematički pristup (J. T. Tou, 1978). Heuristički pristup se temelji na ljudskoj intuiciji i iskustvu. Sustav za raspoznavanje tako je oblikovan da se sastoji od skupa ad hoc postupaka koji su razvijeni za specijalizirani zadatak raspoznavanja. Djelotvornost i struktura takva sustava u velikoj mjeri zavisi od spretnosti, umijeća i iskustva dizajnera sustava. Jezični se pristup zasniva na opisu uzoraka pomoću osnovnih ili primitivnih elemenata (poduzoraka) i na njihovu odnosu koji je opisan primjenom sintaktičkih pravila nekog formalnog jezika. Gramatika uzorka se sastoji od konačnog skupa elemenata koji se nazivaju varijable, od skupa konstanata i skupa produkcijskih pravila. Ulaz u klasifIkator je rečenica koja predstavlja ulazni uzorak. KlasifIka­ tor je zapravo analizator jezičnog niza. Ako analizator ustanovi da rečenica pripada jeziku s određenom gramatikom, tada je ulazni uzorak razvrstava u razred· koji odgovara toj gramatici. U matematičkom se pristupu zasnivaju pravila razvrstavanja upotrebom matematičkih metoda. Matematički pristup može biti dvojak: determinisdčld i stadsdčld. Prvi se temelji na matematičkim principima gdje se ne upotrebljavaju statistička svojstva uzoraka. Statistički se pristup temelji na upotrebi statističkih . svojstava uzoraka i razreda, te na osnovi njih razvrstava uzorke u pojedine razrede. U tehničkom pogledu raspoznavanje uzoraka osigurava teorijsku osnovu za građenje sustava za raspoznavanje uzoraka ili, jednostavnije, sustava za raspozna­ vanje. Takvi se sustavi izvode pomoću različitih tehničkih sredstava (V. I. Timohin, 1983). Prije negoli se upoznamo s formalnim zadatkom raspoznavanja i modelom sustava za raspoznavanje, pogledajmo jednostavan primjer strojnog, odnosno automatskog raspoznavanja velikih slova A i C. Tipične primjere slova A i C

1.2. MODEL SUSTAVA ZA RASPOZNAVANJE

15

predstavljamo, na primjer, slijedom točaka - koordinate tih točaka upisujemo u memoriju računala. Pokušajmo ustanoviti koje su i kakve značajke tipične za slovo A, odnosno za slovo C. Lako ćemo ustanoviti: Slovo e sadrži slijed točaka razmještenih u obliku luka, odnosno zakrivljene crte. Za slovo A točke su razmještene u tri ravne crte. Te su značajke dovoljne za razlikovanje slova A i C. Kada prispije jedno od tih slova, e ili A, računalo mora samo utvrditi da li su točke nepoznatog uzorka. razmještene u obliku krive crte ili su razmještene u obliku triju ravnih crta. Na temelju toga računalo određuje da li je nepoznato slovo e ili A. Iz toga vrlo jednostavnog primjera upoznali smo jednu važnu činjenicu koja se uvelike upotre­ bljava u sustavima za raspoznavanje uzoraka: za razUkovanJe Jednog obUka od

drugoga nije potrebno promatrad sva svojstva pojedinih objekata dovoljno Je promatrad samo neke njegove -značajke, i to prije svega one koje drugi objekt nema. Zadatak raspoznavanja uzoraka može se pojednostavnjeno opisati na

sljedeći način: Nepoznati uzorak X, koji je predočen nizom osnovnih značajki, treba razvrstati u jedan od razreda 2 (eN + l ),

b) Ne�KI2, tada možemo razjediniti aritmetičku sredinu mj u dvije nove aritmetičke sredine m/ i mi, brišemo mj i povećavamo Ne za l . Sredinu m/ tvorirno tako da pribrojirno određenu vrijednost Yj onoj kompo­ nenti mj koja trna najveće standardno odstupanje. Sredinu mj- tvorimo tako da istoj komponenti mj oduzmemo Yj' Obično uzimamo da je:

Yj = k(Jj max'

gdje je

O 9

gdje je e granična duljina. Matrica definira graf sličnosti u kojem grane grafa povezuju čvorove (uzorke u prostoru uzoraka) samo ako je odgovarajući element matrice sličnosti jednak j edan. Na primjer, čvorovi k i l su povezani s granom grafa samo ako je Skl = L Grupe su odredene odvojenim podgrafovima sličnosti (C. Abraham, 1 962). Pogle­ dajmo jednostavan postupak odredivanja odvojenih podgrafova sličnosti iz grafa sličnosti (W. S. Meisei, 1974).

I. korak Izabiremo redak matrice sličnosti koja ima najveći broj jedinica. Pretposta­ vljamo da je najviše jedinica u i-tom retku.

52

3. ANALIZA GRUPA

2. korak

Tvarima grupu od uzoraka koji odgovaraju jedinicama u i-tom retku. Pretpo­ stavljamo da su jedinice u stupcima j, k, l, . . . Toj grupi pridodamo još uzorke koji .-tom retku. U slučaju da su u tim recima odgovaraju jedinicama u j, k, I, -tog stupca, na primjer u stupcima m, n, o, . , pridodamo jedinice i izvanj, k, l, -tom retku. Ako sada u toj grupi i uzorke koj i odgovaraju jedinicama u m, n, 0, m, n, 0, -tom retku nema jedinica izvan i, j, k, l, m, n, o, . . .-tog stupca, postupak prirodavanja uzoraka u tu grupu završavamo. U suprotnom, pridodajemo toj grupi i uzorke koji odgovaraju jedinicama u p, r, s, . -tom retku, itd. . .

. .

. . .

• . •

. . •

. .

3. korak

Brišemo redak i stupac uzoraka koje smo već grupirali. Postupak ponavljamo za reduciranu matricu i nastavljamo sve dok matrica sličnosti ne nestane.

Pogledajmo kako uzorke iz slike 3. 2 grupiramo pomoću opisanog postupka. Najprije računamo N(N 1)/2 udaljenosti između uzoraka:

DI4 = ?,2;

D1 S = 9,43 ;

D16 = 1 1 , 1 8;

Dz4= 5,39;

Dzs = 7,62;

DZ6 = 9,49;

DZ7 = 1 1,18;

D u = 7,07;

D36 = 8,60;

D37 = 9,85 ;

D38= 1 3,45 .

D 13 = 3,00 ;

Du = 0,00;

D u = 2,24;

D l1 = 1 3,00 ;

D1S = 1 5,62 .

Dzz = 0,00;

DZ3 = 2,83 ;

D33 = 0,00;

D34 = 5,00;

D44 = 0,00 ;

D4S = 2,24;

D46 = 4, 1 2 ;

D47 = 6,OO ;

D ss = 0,00;

D S6 = 2,00 ;

D s7 = 4,1 2 ;

D58 = 6,40 .

D66 = 0.,00;

D6 7 = 2,24 ;

D68 = 5,39.

D77 = 0,00 ;

D78 = 6,00.

Dn= 1 3,60. D4S = 8,40 .

Dss = 0,00 .

Ako izaberemo 8 = 4, dobivamo sljedeĆU matricu sličnosti:

2

3 l

4 O

5 O

6 O

7 O

8 O

1

1

1

O

O

O

O

O

2

1

1

O

O

O

O

O

3

O

O

O

1

O

O

O

4

O

O

O

1

1

O

O

S

O

O

O

O

1

1

1

O

6

O

O

O

O

O

1

O

7

O

O

O

O

O

O

1

8

1 l

s=

l. korak

l

O

Za redak koji ima najveći broj jedinica izabiremo prvi redak matrice S. Znači

i= l .

3.5

53

POSTUPCI GRUPIRANJA

2. korak Tvorirno grupu od uzoraka Xl' x2 i X3• Budući da u recima 2 i 3 nemamo do­ datnih j edinica izvan stupaca 1 , 2, 3, grupu ne uvetavamo. Znači, Sl = {Xl' x2, x3}·

3. korak Tvorirno reduciranu matricu tako da brišemo retke Dobivamo:

4

5

l s'

l

l

6

7

8

O

O

O

4

l

O

O

5

O

6

O

7

l

8

O O

O

O

O

O O

stupce

l, 2

3.

l. korak Redak

5

ima najveći broj jedinica.

2. korak U grupu S:z uvrštavamo uzorke x4, Xs i x6• Zato što redak 6 u sedmom stupcu ima jedinicu, uvrštavamo x1 u grupu S2' Pošto u sedmom retku nema jedinica izvan 4-, završavamo.

5- , 6-,

7-tog stupca, postupak pridodavanja uzoraka u grupu S:z

3. korak Tvorimo reduciranu matricu tako da brišemo retke i stupce 4, Dobivamo: S"

=

[1] 8.

l. korak Biramo redak

8.

2. korak Tvorirno novu grupu u koju uvrštavamo uzorak xs: S) = {x8 } ,

5, 6

h 7.

54

3. ANALIZA GRUPA

3. korak

Matrica S je brisanjem retka 8 nestala, pa je postupak završen. Rješenje primjera prikazuje slika 3.3.

Stablo minimalne duljine (c. T. Zahn, 1971) Problem izbora granične duljine e možemo izbjeći ako izravno obrađujemo matricu udaljenosti između uzoraka. Uzorci, njih N, predstavljaju u prostoru uzoraka čvorove punoga neusmjerenog grafa koji povezuje sve čvorove grafa. Svakoj grani grafa dodjeljujemo težinsku vrijednost koja odgovara udaljenosti između odgovarajućih čvorova. Tvorimo stablo grafa (djelomični graf koji pove­ zuje sve čvorove grafa i ne sadrži ni jednu petlju) tako da je ukupna duljina njegovih grana najmanja (stablo minimalne duljine). Razmotrimo primjer uzoraka sa slike 3.2. Stablo minimalne duljine povezuje sljedeće parove uzoraka:

To stablo prikazuje slika 3.6.

15

10

5

O

5

10

15

Xl

Sl. 3.6. Stablo minimalne duljine uzoraka sa slike 3.2

Problem je grupiranja u principu riješen; svi su uzorci povezani u okviru pojedinih grupa. Postoje samo dvije suvišne veze koje povezuju uzorke iz suprotnih grupa. Prekidom tih dvaju grana stablo se grafa raspada u tri odvojena stabla, od kojih svako stablo povezuje uzorke jedne grupe. Kako otkriti suvišne grane u stablu minimalne duljine?

3.5 POSTUpCI GRUPIRANJA

55

Jedan od osnovnih pomoćnih sredstava je određivanje razdiobe duljina grana u stablu minimalne duljine. Očekujemo, naime, da je ta razdioba bimodalna, što se vidi i iz histograma na slici 3.7. Slika 3.7 prikazuje razdiobu duljine grana stabla minimalne duljine sa slike 3.6.

6 5 4

ModusA

3 2

o

Modus B

6

7

8

SI. 3.7. Histogram distribucije duljina grana u stablu minimalne dulji1le sa slike 3.5

Granična duljina što dijeli grane koje povezuju uzorke u grupama od grana koje povezuje grupe zauzima vrijednost između dvaju modusa.

3.5. UTERATURA Abraham, C. Evaluation of Clusters on the Basis of Ra1ldom Graph Theory, IBM Corp., Yorktown Heights, New York, nov. 1962. Augustson J. G., J. Minker, An ONJlysis of some graph theoretical cluster techniqu&, J. ACM, 1 7, 571 - 588, okt. 1970. Ball G. H., Hall D. J., lsodata, A1I lterative Method of Multivariate AlIIQlysis and Patter1l Classification, Proceedings of the IFIPS Congress, 1965. Bennett R. S., The Intrinsic Dimensionality of Single Collections, IEEE Trans. PGIT, Vol. IT- I S, No. 5, 5 1 7 - 525, Sept. 1 969. MacQueen J., Some Methods for Classification and AlIIQlysis of Multivariate Data, Proceedings of the 5th Berkeley Symposium on Probability and Statistics, University of California Press, Berkeley, 1967. Meisel W. S., Computer-Oriented Approaches to Pattern ReC()gnitUm, Academic Press, New York, 1972. Sokal R. R., Sneath P. H. A., Principles of Numeril;al Taxonomy, W. H . Freeman, S. Francisco, 1963. Zahn C. T., Graph- TheQwical Methods for Detecting and Describing Gestalt Clusters, IEEE Trans. Computers, 20, 68 - 86, 197 1 .

4. LINEARNE FUNKCIJE ODLUČIVANJA

(DECIZljSKE FUNKCIJE)

(Prof. dr. Nikola Pavešić, dipl. ing.) 4.1. UVOD

Osnovni zadatak sustava za raspoznavanje j e razvrstavanje uzoraka u razrede uzoraka. To se može izvršiti pomoću funkcija koje dijele prostor uzoraka u međusobno neprekrivena područja, gdje svako područje pripada samo jednom razredu uzoraka. Takve funkcije u teorij i raspoznavanja uzoraka nazivamo funkciJe odlučivanja (engl. decision function). Ako imamo M razreda uzoraka, moramo imati i toliko funkcija odlučivanja . . . , M, tako da je

dl< (x), k = 1 , 2,

za

j =1= i.

Drugim riječima, to znači da funkcija odlučivanja di (x) ima najveću vrijednost na području kojem pripadaju uzorci iz razreda IDI' Granicu koja dijeli područja IDI i ID sastavljaju točke prostora uzoraka sa svojstvom dj (x) = dj ex), odnosno j di (x) d/x) O. Slučaj M razreda uzoraka rješavamo sa M (M - l )/2 granica. Moramo odmah reći da ne trebamo toliko granica u svim slučajevima. To se vidi iz primjera što ga prikazuje slika 4. 1 , gdje je granica dt ex) -d3 (x) = o suvišna. -

H=4

HIH-lll2 = 6

Sl. 4.1. Primjer suvišnih gramca odlult.vanja

4,2.

57

LINEARNE FUNKCIJE ODLUCIVANJA I GRANICE

4.1. LINEARNE FUNKCIJE ODLUČIVANJA I GRANICE Vjerojatno najjednostavniji oblik funkcije odlučivanja predstavlja upravo linearna funkcija:

d (X) = W1X1 +WlXl + . . . +W"X" +W" + l = w!x +W" + l '

gdje je w = (w 1, w l' ..Q praga. W IJ+ 1 koetlcijent

W,,)T vektor koeficijenta, x = (X1, Xl'

o o .

o o .

,

X,,)T uzorak, a

Granica koja dijeli (Oj i (Oj također je linearna:

d/ ex) - d/x) = 0,

odnosno:

(WiU _Wj�T ' X =

-

(wi• n + l - WJ• n + l) '

Slika 4.2 prikazuje primjer granica koje u prostoru uzoraka dijele razrede (01' i (03' Na slici možemo također opaziti da su područja što ih omeđuju linearne granice uvijek konveksna, (Ol

Sl. 4.2.

Granice odlučivanja za primjer triju razreda uzoraka

Pomoću slike 4.3 prikazat ćemo neka geometrijska svojstva granica linearnih funkcija odlučivanja.

Na slici sino sa ii označili jedinični vektor koji je u točki p okomit na hiperravninu (granicu) i usmjeren tako da pokazuje na pozitivnu stranu hiperrav­ nine. Jednadžbu_hiperravnine možemo zapisati kao:

...:Io T x.J.

U

�, = u...,l. T p

gdje su x i p točke hiperravnine. Ako jednadžbu hiperravnine usporedimo s jednadžbom granice što smo je l l prethodno normirali sa i Cw10 - wJ� = (wh - Wjt) + . . . +(wh. -W},,) , dobit ćemo:

i

li J

4. LINEARNE FUNKCIJE ODLUCIVANJA

58

"' T]1:t =

U

(WI• n + 1 - Wj, .. + 1)

!I(WiO - Wj�1 I .

Hiperrovnino

Sl. 4.3. Geometrijska svojstva hiperravnina

Prema slici 4.3 vidi se da koeficijent (wi n + 1 - W ', n + 1) odreduje položaj granice s obzirom na ishodište. Ako je taj koeficijent jednat 0, granica prolazi točno kroz ishodište, a ako je veći od 0, ishodište se nalazi na pozitivnoj strani granice i obratno, ako je manji od 0, nalazi se na negativnoj strani. Jedinični vektor u odreduje orijentaciju hiperravnine. Ako je neka komponenta vektora u jednaka 0, hiperravnina je paralelna s koordinatnom osi koja odgovara toj komponenti. Budući da je u= (wl o - Wj�/ II Wi - wjo ! l , možemo ispitivanjem vektora (wi O - Wj� ustanoviti da li je granica paralefna s nekom koordinatnom osi. Udaljenost između neke točke x i hiperravnine je:

1

T x (Wi, II + 1 - Wj, n + 1) ( io = I "'P _ "' Tpl = W _Wj� · + l I(wiO - Wj�1 1 II wiO - Wjo l l _ Idi (x) - d/x) 1 - I (wi I O - Wj�1I . Iz gornjeg izraza vidimo da je udaljenost izmedu uzorka x i granice proporcional­ na razlici funkcija odlučivanja, di (x) - dj (x) . D.x =

U X

U

I

Linearne funkcije odlučivanja obično zapisujemo u obliku:

di (x) = wix·, ax _ " -( . . . , wn' wn + l )T vektor koefiCljenata,

_ (w 1' wl' ... gd·Je Je . w "prošireni" uzorak. Trivijalno rješenje jednadžbe granice

(wi - Wj? ·x· = O

... .

Xl' X3' . . . , Xn'

I )T

kazuje nam da granica odlučivanja prolazi uvijek ishodištem (n + 1)­ dimenzionalnog prostora uzoraka, i to bez obzira kako je prolazila u n-dimenzio­ nalnom prostoru. Slika 4.4 prikazuje primjer preslikavanja n-dimenzionalnog prostora uzoraka u (n + l)-dimenzionalni prostor uzoraka.

4.3. UOPCENE LINEARNE FUNKCIJE ODLUCIVANJA

a) Jednodimenzionalni prostor uzoraka

b)

Wl • • ••

S9

W) W2 _ I---" .-l. --l .I--.. II-i O-O--O--+--.

.1

xl

Dvodimenzionalni

"projireni" prostor uzoraka

b) SI. 4.4. Lillear7Ul granice odlučivanja

Udaljenost izmedu uzorka

II

profirenttm prostoru llZoraka

X* = (X1, Xl' . . . , X ",

l ? i granice u

dimenzionalnom prostoru uzoraka je

(n + l)­

I (dj (x) - diX)) 1 I I Cwi - wi)11 Kako Je

! l Wi wi l l � I I (wio - Wia:> II, -

ta j e udaljenost manja ili najviše jednaka

udaljenosti izmedu uzorka X = (X1, Xl' . . . , X,,)T i granice u n-dimenziona1nom prostoru. Ako razrede uzoraka ne možemo razdijeliti linearnim granicama, moramo upotrijebiti nelinearne funkcije koje dijele prostor i na nekonveksna područja.

4.3. uopćENE LINEARNE FUNKCIJE ODLUĆIVANJA Sljedeći stupanj u izboru funkcija odlučivanja jest kvadratna funkcija odluči­ vanja. Ona se sastoji od koeficijenata članova nultog, prvog i drugog reda. Ako su uzorci n-dimenzionalni, funkcija odlučivanja ima oblik:

d (x) =

JI

n-i

II

...

L WJ.f; + Ll L+ l Wjrr" + Ll WrJ + W" + l ' i"' 1 O - l ako je WTX � O .

Zamjenom dobivamo

w Ck + l ) w Ck) +� {x Ck) -x Ck) sgn [w T Ck) X Ck)] }, 2 gdje je x (k) uzorak skupa za učenje koji primjenjujemo u k-tom koraku učenja. Gornju jednadžbu možemo zapisati: =

{

O ako je wT Ck)x Ck» O � � w Ck + l ) = w Ck) + p x Ck) ako je wT Ck)x Ck) �O)

gdje su p> O i w cl) izabrani po volji. Ovakav postupak po:tnat je pod imenom postupak perceptrona sa stalnim

prirastom CF. Rosenblatt, 1962).

l JCw, x) = � p CjwTX! " _ l wTx!WTX) 4x x Parcijalna derivacija kriterijske funkcije J po w dana je izrazom: 1 == � t>l [2I wTxl x sgnCwTx) - lwTx!x - l wTxl xsgn CwTx)], uw 4x T �

b)

��

koji možemo zapisati kao:

, o� =

[I

l � p wTx!xsgnCwTx) - ! wTx l x]. aw 2 x x Postupak učenja w daje izraz: w Ck + l ) w Ck) + =

AI �: Ck)� Ck) ! {x Ck) - x Ck)sgn ['fP Ck)x Ck)] h

2x Ck)x Ck) gdje smo umjesto p napi s a li A da izbjegnemo eventualnu zabunu s korekcijskim faktorom u slučaju a).

64

4. LINEARNE FUNKCIJE ODLUCIVANJA

Ako

U

obzir uzmemo:

� �

sgn (wTx) =

{

1 ako je WTX > O - 1 ako je WTX � O '

dobiva se: �

�

w (k + 1) = w (k) +

{

A. l wT (k) ' x (k) 1 O ako je wT (k)x (k» O xT (k) ' x (k) x (k) ako je wT(k)x (k) �O �

�

�

�

�

.

Jasno je da početna vrijednost vektora w mora biti različita o d O. Ako je A.> 1 , promatrani uzorak pravilno uvrštavamo nakon svake korekcije vektora W. Jedno­ stavno se može dokazati da taj postupak konvergira za O < A. < 2. Postupak je poznat pod nazivom postupak perceptrona s djelomičnom korekcijom. c) Kriterijska funkcija:

�

� � (wTxj - bY = I I [X]w - b W J (w, X, b) = 2 j= 1 2 neka dostigne minimum kada je

[X]w = b,

b = (b b2, . . . , bN? vektor pozitivnih komponenata. l' Dakle, umjesto da� tražimo vektor w koj i zadovoljava nejednadibu [X]w > O, tražimo vektore w i b tako da zadovoljavaju jednadibu [X]w = b. Budući da minimiziramo kriterijsku funkciju J s obzirom na w i b, taj se postupak donekle gdje je

razlikuje od općega gradijentnog postupka. Parcijalne derivacije kriterijske funkcije po

�

w i po b jesu:

� � aJ aJ = [X] T ([X]w -b) --== -([x]w -b). aw ob b Vrijednosti za moraju biti pozitivne, zato vektor b mijenjamo tako da ne �

prekoračimo to ograničenje:

b ek + 1 ) = b (k) +p { [X]w (k) - b (k) + I [X]w (k) - b (k) I } . Uvedimo oznaku -e (k) = [X]w (k) - b ek). Ako je ej (k) �O, korekcija bj (k) jednaka je O, ako je ej (k» O, korekcija je jednaka 2pej (k). Dakle, ako su p i bj (1) veći od nule, tada će biti i bj (k) > O. Vrijednosti za w ne ograničavamo, zato možemo postaviti oJ/ow = O. Dobivamo:

w = ([X]T [X]) - l [X]Tb. Ako uvedemo oznaku [X'] = ([X]T [x]) - 1 [X]T, možemo zapisati: w (k + 1 ) = [X'] b (k + 1 ) = [X']b (k) + [X'] p [-e (k) + l-e (k) I I = w (k) + p [X'] [-e (k) + l e (k) I ] . Sada možemo zapisati postupak učenja vektora koeficijenata linearne funkcije odlučivanja:

w ( 1 ) = [X'] b (1),

4.4. GRADIJENTNI POSTUPCI

65

bi ( l ) proizvoljna vrijednost, ali veća od O za svaki i = 1 , 2, , N, e Ck) = [X]iV Ck) - b Ck), iV Ck + 1 ) = iV Ck) + P [X'] [eCk) + I t Ck) I ] , b Ck + 1 ) = b Ck) + p [t Ck) + Ie (k) I ]· Kada za nejednadžbu [X]iV > O rješenje postoji, postupak konvergira za O < p :::::; l . Ako su u postupku pri bilo kojoj iteraciji sve komponente vektora e (k) pozitivne (ali nisu sve jednake nuli), t 0, bit će: w (5) = w (4).

Rješenje ćemo dobiti kada na temelju izračunatog w pravilno razvrstamo sve uzorke iz skupa za učenje. U ovom primjeru došlo je do dva pogrešna razvrstava­ nja koja su imala za posljedicu popravljanje vektora koeficijenata funkcije odluči­ vanja w. Postupak učenja nastavljamo tako da pretpostavimo da je x (5) = x ( l), x (6) x (2), x (7) = x (3) i x (8) = x (4). Dobivamo:

wT (5) � (5) = o,

slijedi

;;' (6) = ;;' (5) +% (5) =

;;'T (6)% (6) = I ,

slijedi

;;' (7) = ;;' (6) =

wT (7)% (7) = I,

slijedi

w (8) = w (7) =

;t,T (8)% (8) = I,

slijedi

w (9) = w (8) =

r�J [-�] [n [-� ] -

Ni u drugom ponavljanju nisu bili svi uzorci iz skupa za učenje pravilno razvrstani. Jednostavno se možemo uvjeriti da će svi uzorci biti pravilno razvrsta­ ni u trećoj iteraciji. Rješenje je vektor koeficijenata funkcije odlučivanja:

w = ( -2, 0, l)T. Odgovarajuća je funkcija:

d (x) = wT ' x = -lx1 + 1 . Ako postavimo d(x) = O, dobivamo jednadžbu uzoraka 011 i Ol,. (slika 4.6b).

granice koja dijeli razrede

Postupak perceptrona konvergira ako su razredi razdvojivi izabranom grani­ com (A. B. J. Novikoff, 1 962), što je očito iz prethodnog primjera. Medutim kada razredi nisu razdvojivi izabranom granicom, postupak ne konvergira. Na žalost,

4, LINEARNE FUNKCIJE ODLUCI VANJA

68

nije moguće unaprijed izračunati broj iteracija koji nas dovodi do rješenja. Zbog toga dugotrajno učenje još ne znači da razredi nisu razdvojivi izabranom granicom. b) Potražimo, još jednom, vektor koeficijenata linearne funkcije odlučivanja prema Hoovu i Kashyapovu postupku.

[=: :

Potražimo [X'] = ([X]T [X] ) - l [X] T: [X'] =

�

Neka bude b (1)= ( I , l, l, 1) T,

-

1/2 1/2

3/2 1/2

p=

]

I -I

-I

lr-2�- .

I , pa imamo:

'lO ( l ) = [X' ] b ( l )

Budući da je:

J

1

o

O O O bit će 'lO ( l ) = ( -2, O, I ) T traženo rješenje. Granicu prikazuje slika 4.6b. e (l ) = [x] 'lO ( l )

-;;(1)=

=

Prednosti ovog postupka lakše uočavamo na sljedećem primjeru. Zadani su skupovi uzoraka za učenje: Ol = {CO, O ) T, (I, l?}, t Ol = {(O, l ) T, CI, O)T}, z §oji nisu linearno razdvojivi kao što se vidi iz slike 4.6c. Neka je i u ovom slučaju b ( l ) = (l, I , I , I )T i c = l . Matrice [x] i [X'] jesu: [x]

=

O I O -1

O -l

-I

O

-1

�.4.

GRADIJENTNI POSTUPCI

[�

69

-1

[X'l =

-1

- 1 /2

3/2

Vektor koeficijenata

w (1)

-1

1

- 1 /2

jest:

w (l ) [X']b ( l ) � �

e ( 1 ) = [X]w ( 1 ) - b ( 1 ) =

[�l

o

-1

O

-1

O O

-1 -1

Budući da vektor e ( l ) ima negativne komponente, zaključujemo da ne postoj i rješenje sustava nejednadžbi [x]w > O. Dakle, vrijednosti komponenata vektora e nam kažu da li su razredi uzoraka za učenje razdvojivi linearnom granicom. To lijepo svojstvo ovog postupka plaćamo povećanom složenosti računanja (osobito računanje matrice [X'l pri velikim n i N). Problem učenja koeficij enata linearne funkcije odlučivanja za više od dva razreda uzoraka za učenje (M > 2) također rješavamo postupkom perceptrona ili Hoovim i Kashyapovim postupkom. Problem razdvajanja M > 2 razreda uzoraka za učenje možemo transformirati u M (M - 1 )/2 problema razdvajanja dvaju razreda. Funkcije odlučivanja dij (x) = wJx zauzimaju vrijednosti veće od nule ako uzorak x pripada razredu uzoraka wi' odnosno:

dij (x» O, (vrijedi dij (x) = -dji (x)).

za

't/X E Wj

U slučaju da se dva razreda ne mogu razdvojiti linearnom funkcijom, upotrebljavamo funkciju odlučivanja višeg reda. Koeficijente tih funkcija možemo dobiti učenjem po bilo kojem do sada opisanom postupku. Ako izaberemo pravilo odlučivanja: 't/j =1= i,

za

možemo upotrijebiti uopćeni postupak perceptrona koji nam omogućava da istovremeno odredimo sve vektore koeficijenata funkcije odlučivanja Wi' i = 1 , 2, . . . , M > 2. Postupak možemo opisati na ovaj način:

x (k)

Pretpostavimo da u k-toj iteraciji procesa učenja razmatramo uzorak učenja koji pripada razredu Wi. Računamo vrijednosti za M funkcija odlučivanja:

dj [x (k) l = wJ (k)x (k)

za

j = I , 2, . . . , M.

70

4.

LINEARNE FUNKCIJE ODLUCIVANJA

Ako je dJx (k)] > dj [x (k)] za sve j= d , 2, . . . , M, j :l: i, vektor koeficijenata ne mijenjamo: j = 1, 2, . . . , M. Ako je za neki I: di [x (k)] �d, [x Ck)] ,

vektor koeficijenata popravljamo na sljedeći način: w, (k + l ) = w, (k) + px (k) w, (k + l ) = w, (k) wj (k + l ) = w/k),

px (k)

j = l , 2, . . . , M,

j:l: i,

j:l: l,

gdje je p pozitivna konstanta. Jednostavno se može dokazati da postupak konvergira u konačnom broju iteradja za proizvoljno izabrane početne vrijednosti vektora koeficijenata wj ( l ), j = l , 2, . . . , M, ako se razredi uzoraka za učenje mogu razdvajati izabranim granicama. Kada skupovi za učenje nisu linearno razdvojivi, postupak zahtijeva za sve funkcije odlučivanja polinom stupnja r. Na taj način rješavamo najsloženije probleme razdvajanja uzoraka za učenje. 4.5. POSTUPAK UČENJA S POTENCIJALNIM FUNKCIJAMA

Za postupke učenja koje smo do sada razmatrali u ovom poglavlju karakte­ ristično je da smo već prije učenja pretpostavili konačan oblik funkcije odlu­ čivanja. Potencijalne funkcije nam dopuštaju da pristupimo učenju funkcije odlučivanja bez takve pretpostavke (M. A. Aizerman, 1964),Postupakse temelji na ideji da se točkama prostora značajki (uzorcima za učenje XI) dodijeli jedinični električni naboj q,. Taj naboj neka bude pozitivan ako uzorak pripada razredu 0)1' odnosn� negativan ako je uzorak iz razreda O)l' Elektrostatički potencijal u točkama prostora značajki gdje njegova vrijednost poprima vrijednost nula može poslužiti kao granica izmedu razreda 0)1 i O)l (sl. 4.7).

v

----..e--IK*-..... __ --\---()----O--o---- x,

Sl. 4.7. Pvtencijal1W polje kav funkcija vdlučWanja

4.5. POSTUPAK UCEN}A S POTENCIJALNIM FUNKCIJAMA

71

Ako j e potencijal u točki x zbog naboja u točki Xi jednak K (x, Xi)' tada će potencijal u toj točki zbog naboja N uzoraka za učenje biti jednak: d (x) =

N

L qjK (x, xJ

i= l

Pretpostavimo da funkciju odlučivanja određujemo pomoću N uzoraka za učenje iz razreda (Ot i (02 ' Pretpostavimo još da smo funkcijom odlučivanja dk _ I (x) pogrešno razvrstali uzorak x k' Da bismo tu pogrešku uklonili, mijenjamo naboj q k uzorka xk. To činimo tako da pribrojirno uzorku x k jedinični naboj q k ako uzorak pripada razredu (O t' odnosno oduzmemo qk ako uzorak pripada razredu (02' Dakle: dk _ I (X k) � O,

- ako je X k E (Ot

tada je

dk (x) = dk _ 1 (x) + K (x, xk); dk _ I (xk»

O,

tada je

dk (x) = dk _ 1 (x) - K (x, xk); ako je X k E (Ot Xk E (02

dk _ I (x k) > O

ili ako je

dk _ I (x k) < O,

tada je

dk (x) = dk _ 1 (x). Iz tih jednadžbi možemo izvesti postupak za iterativno određivanje funkcija odlučivanja. Postupak zapisujemo na sljedeći način: dk (x) = dk _ 1 (x) +rk K (x, xk), gdje je do (x) = 0, a rk korekcijski faktor koji ima sljedeće vrijednosti:

rk =

O

ako je

Xk E (O t

dk - t (xk»

O

ako je

X k E (02

dk - t (x k) < O

ako je

Xk E (O t

dk - t (Xk) � O

ako je

XkE (02

dk - t (X k) � O.

-l

O

Ako je uzorak za učenje x k pravilno razvrstan, korekcij ski faktor je O, ako je, međutim, pogrešno razvrstan, korekcijski faktor je l ili - l, već prema tome da li uzorak x k pripada razredu (O t ili (02 '

Očito je da na oblik funkcije odlučivanja utječu samo oni uzorci iz obaju razreda koji su bili u postupku određivanja funkcije odlučivanja pogrešno razvrstani. Potecijalne funkcije određujemo tako da zadovoljavaju sljedeće uvjete: a)

K (x, Xk) = K (xk' x). Potencijalna funkcija je simetrična funkcija dvaju varijabla.

b)

K (x, Xk) je neprekinuta funkcija koja monotono pada prema nuli ako udaljenost Ilx -xk l l raste u beskonačnost.

4. LINEARNE FUNKCIJE ODLUCIVANJA

72

Najčešće upotrebljavamo kao potencijalne funkcije sljedeće njihove oblike: K (x, xJ = exp { - (X llx -x/c ll l }, I K (x.., x.. /c) = I - (X !Ix - X.Jl l '

I

l

in(X llx -xk l l K (..x, x.. k) = S (X llx -xk Il 2 ' gdje je (X pozitivna konstanta. Meisei je dokazao da je uvijek moguće naći takvu potencijalnu funkciju K (x, x/c) da pomoću d(X) pravilno možemo razvrstati sve uzorke u razredu ffi l i ffi2 (W . S. Meisel, 1969). Kao primjer razmotrimo kako bismo s potencijalnom funkcijom K (x, x,,) = exp { - (X l l x -x/c1 1 2} odredili funkciju odlučivanja za skup uzoraka za učenje koji su prikazani na slici 4.6c. Zadana su dva razreda: ffi l = {(O, O)T, ( I , l )T}, ffi2 = { (O, 1 )T, ( I , O)T}. .

Neka je (X = l . Za n = 2 potencijalna funkcija poprima oblik: K (x, x.) = exp { - [(xl -0) l + (Xl -0)2 ] ) 1

Započnimo postupak učenja. Neka je X l = (O, O) T effi prvi uzorak za učenje. Iz do (x) = ° slijedi d l (x) = K (x, xl) = exp - [(Xl - 0)2 + (x2 - 0)2 ] = exp { - (X� +x�)} za

uzorak iz skupa za učenje x2 = (1, 1) T effi l vrijedi: dl (x:z ) = exp { - ( I + l ) } = e - 2 > 0,

zato je Za uzorak X3 (O, 1) T effi2 je dl (x3) = e -(0+1)= e- l > 0, zato je d3 (x) dl (x) -K (x, x3) = exp { - (x� +x�) } - exp { - [( X l -0) 2 + (X2 1 )2]) Za sljedeći uzorak x4 = ( 1 , Of effi:z dobivamo: d3 (x4) = e- l - e - h + l ) = e - l -e -2 > 0.

45, POSTUPAK

73

S POTENCIJALNIM FUNKCIJAMA

Zato što je X4 eroz i d3 (x4) > 0, ponovno moramo popravljati funkciju odlučiva­ nja. Dobivamo: d4 (x) = d3 (x) -K(x, x4) = exp { - (xi +,x�)} - exp { - [xi +(x.z 1 }�1 ) - exp { - [(Xl _ 1 )2 + x� 1 ) Provjerimo da li tom funkcijom odlučivanja možemo pravilno razvrstati sve uzorke iz skupa za učenje: Za xs = (O, O?Erol je d4 (x S) = e-O - e - l -e 1 > 0, zato je ds (x) d4 (x) . Za X6 = cl, 1 ) T Erol j e ds (xJ = e - 2 -e - l -e - l < 0, zato j e d6 (x) ds (x) + K (x, X6) = e xp { - (x� +x;) } - exp { - [x� + (X - 1 )2] ) - e xp { - [(Xl - 1 )2 +x; ] : + 2 + e x p { [ (X l 1 )2 + (X - 1 )2] : . 2 Za X7 = (0, l)TEro je d6 (x7) = e - l - eO -e - 2 + c - l < 0, zato je 2 d7 (X) d6 (X) · Za xs = ( l, O)T Eroz je d7 (xS) = e - l -e-Z -eo + e - l < 0, zato je dil ex) = d7 ex). z Za x9 = (0, O? Ero l je ds(x� e - o -e- l -e- l + e- > O, zato je d9(x) = ds (x). Za xl o = (l, I )fErol je d9 (x l o) e - 2 - e l - e - l + eO > O, zato je d10(X) = d9 (x). Sve uzorke iz skupa za učenje smo pravilno rasvrstali funkcijom odlučivanja: d ex) = exp { - (x� + x;) } - ex p { [x� + (X _ 1 ) 2] } - ex p { - [(Xl 1 ) 2 +x;J l + 2 + exp { [ (X l 1 ) 2 + (X _ 1 ) 2] ) . 2 Uočavamo da funkcija odlučivanja ima onoliko eksponencijalnih članova koliko je bilo korekcija u postupku učenja. Rješenje prikazuje slika 4.6d. Postupak koji se temelji na potencijalnim funkcijama može se na sličan naČIn, kao postupak perceptrona, uopćiti na više od dva razreda. Na početku učenja sve su funkcije odlučivanja d! (x), d� (x), . . . , d':: (x) jednake O. Pretpostavimo da se u k-tom koraku učenja razmatra uzorak Xl koji pripada razredu roi' Funkciju odlučivanja u k-tom koraku određujemo sljedećim postupkom: - ako je xlEroj i za

'Vj #i,

funkcije odlučivanja se ne mijenjaju, odnosno d�1 (x) = d��1 (x), i= 1 , 2, . . . , M; ako je xlEroj i za neki l je JI;) � ) :« Jll) (� ) Uk- l (X l "", Uk - 1 X,, ,

4. LlNEARNE FUNKCIJE ODLUCIVANJA

74

moramo izvršiti sljedeće korekcije na funkcijama odlučivanja

d�) (x) = tJ;� 1 (x) + K (x, x,,) d�) (x) = tJi� 1 (x) - K (x, x,,) 1 , 2, d�) (x) = r1f- 1 (x),

. . . , M,

j� i,

d"- l (x):

j � l.

U ovom smo poglavlju prikazali osnove prepoznavanja uzoraka pomoću postupaka determinističkog učenja funkcija odlučivanja. Na početku smo pomoću općeg gradijentnog postupka razvili tri postupka učenja. Na primjerima smo ta tri postupka međusobno usporedili. Potrebno j e istaknuti da gradijentnih postupaka ima puno više (npr. R. O. Duda, 1 973), međutim navedeni postupci su karakteristični (J. T. Tou, 1 974). Osnovni problem pri upotrebi tih postupaka predstavlja određivanje stupnja polinoma funkcije odlučivanja. Njega prije početka učenja, na žalost, ne znamo. Jedini ekonomski opravdan put koji nas vodi do funkcije odlučivanja jest postup­ no povećavanje stupnja polinoma, i to sve dok postupak za zadane uzorke iz skupa za učenje ne počne konvergirati. Prilikom izvedbe stvarnih slučajeva možemo, međutim, tolerirati određen broj (odnosno postotak) pogrešno razvrstanih uzoraka kada to povoljno utječe na složenost (manju složenost) funkcije odlučivanja. Međutim, kada predviđeni postotak dopuštene pogreške ne možemo postići s izabranim funkcijama odlučivanja, moramo ili povećati postotak dopuštene pogre­ ške ili povećati stupanj polinoma funkcije odlučivanja, ili pak izabrati koji drugi postupak prepoznavanja. Potrebno je zapamtiti da j e uvijek moguće odrediti funkcije odlučivanja na takav način da svi uzorci iz skupa za učenje budu pravilno razvrstani. Naravno, uz uVjet da razredi uzoraka ne dijele identične uzorke (npr. X EO)l i 0)2)' Na kraju poglavlja smo razmatrali prepoznavanje uzoraka pomoću potencijal­ nih funkcija, i to prije svega sa stanovišta učenja funkcija odlučivanja bez unaprijed pretpostavljanja njenoga konačnog oblika. To poželjno svojstvo, među­ tim, može prouzrokovati teškoće. Funkcija odlučivanja u tom slučaju sadrži onoliko članova koliko je bilo potrebnih korekcija u postupku učenja. Njih može biti vrlo mnogo ako učimo brojnim skupom uzoraka za učenje.

4.6. UTERATURA M.A. Ai zerm an, E. M.B raverm an, L. l. Rozonoe r, Theoretical Foundations of the Potemial Functions Method in PaZlern Recognition Learning, Auto matio n an d R emot e Co nt ro l, 25, juni 1964, st r.

821 -837.

K. O. D ud a, P. E. Hart, Pauem Classification and Scene Analysis, John Wi ley an d So ns, 1973. W. H.Hi ghley man, linear Decision Function with Application on Panem Recognition, Proc. IRE, 50, juni 1962, 1 50 1 1 51 4 st r. Y. C.Ho, R. L. Kashy ap, An Algoritlon for linear inequa/ities and iu Applications, !EEE T rans.Elee. Co mp., EC - 14, okto bar 1 965, st r.683 - 688 .

W. S. Meis eI, Potential Functions in Mathematical Pauern Recognition, IEEE T r ans.o n Com put ers, Vo l.e- 1 8, N° 10, o ktob a r 1 969, st r. 9 1 1 - 9 1 8. A. B. J. Nov ikoff, On Convergence Proofs for Perceptrons, Pro c. Sym p o n Ma th, T heory of Automata, 1 962, st r.6 1 5 - 622. F. Ros enb latt, Principles of Neurodinamics: Perceptrons and Theory of Brain Mechanisms, Spart an . Books, 1962. J. T. Tou, R. C. Go nz al es, Pallern Recognition Principles, Addiso n-W es l ey Pu bl. Co., 1 974.

5.

STATISTIeKA KLASIFIKACIJA UZORAKA (Prof. dr. Ludvik Gyergyek, dipl. ing.)

5.1. UVOD Fizički prostor oko sebe spoznajemo tako da primamo o njemu informacije. Nosioci informacija su signali. Promatranjem signala možemo uočiti karakteristič­ na svojstva okoline, odnosno dobiti informaciju o objektima raspoznavanja. Mora­ mo uzeti u obzir da objekti raspoznavanja "odašilju" o sebi idealne, neiskrivijene signale S (t). To su signali koje možemo detektirati i mjeriti. Medutim, pri mjerenju tih signala činimo pogreške, odnosno korisnoj informaciji kojoj je nosilac S et) pridaje se šum n (t). Znači, u stvarnosti mjerimo signal x koji je suma signala S (t) i šuma n (t):

x (t) = S (t) +n (t). Na temelju promatranja funkcije x (t) možemo raspoznavati objekte. Ako funkciju x (t) uzorkujemo u trenucima tl' t2, . . . , tn i prikažemo u vektorskom obliku:

dobivamo

uzorak koji možemo smatrati kao realizaciju slučajne varijable Prostor uzoraka je prostor realizacije slučajne varijable X. Upravo taj prostor želimo podijeliti i razgraničiti na područja Dj tako da uzorci iz razreda Olj padaju u područje Dj" Na dijelove Dl' D�, . . . , DM razgraničeni prostor značajki (odnosno prostor realizacija slučajne varIJable x) označimo sa D i nazivamo ga prostor odlučivanja. Odlučivati, dakle, znači razgraničiti prostor realizacija slu­ čajne varijable X na područja Di' i = I , 2, . , M. Dijeljenje prostora X na područja Dj predstavlja razvrstavanje. Budući da je varijabla X slučajnog karaktera, problem klasifikacije rješavamo statističkim ispitivanjem (testiran;em) hipoteza.

X = S + N.

.

.

5.2. JEDNOSTAVAN TEST DvijU IDPOTEZA Upoznajmo prvo jednostavno testiranje dviju hipoteza, odnosno statističko raspoznavanje uzoraka iz dvaju razreda Oll i 0l2' Fizički prostor uzoraka "odašilje" informaciju o uzorcima S = S l (t), odnosno S = S2 (t) iz obaju razreda. To je izvor uzoraka,

5. STATISTIeKA KLASIFIKACIJA UZORAKA

76

Za vrijeme "odašiljanja" i prijenosa tim se signalima primješao šum n (t). Dobivamo signal x (t) = s (t) +n (t). Tu dostupnu informaciju mjerimo i uzorkuje­ rno. Dobivamo realizaciju x:

�

X=

Xl X:z Xn

slučajne varijable X koja je predočena točkom u prostoru X. Pomoću određenog pravila odlučivanja uvrštavamo dani uzorak u jedan od razreda.

Kriterij odlučivanja Pri testiranju dviju hipoteza (ili binarnom testiranju) znamo da je istinita hipoteza Hl ili pak hipoteza H:z, odnosno da objekt raspoznavanja pripada razredu (01 ili razredu (O:Z. Realizacija događaja uvjetuje jednu od četiriju odluka:

(01 istinito, x razvrstavamo u Dl' 2. (01 istinito, x razvrstavamo II D :z, 3. (O:Z istinito, ; razvrstavamo u D:z, 4. (O :Z istinito, x razvrstavamo II Dl. l.

Prva i treća odluka odgovaraju pravilnoj odluci. Druga i četvrta odluka su pogrešne. Namjena kriterija odlučivanja je dodjeljivanje vrijednosti ili određenog značaja nekoj odluci. Izabrani kriterij će pri ulaznom uzorku x utjecati na izbor jedne od četiriju mogućnoSti.

5.3. BAYESOV KRITERIJ ODLUCIVAN)A Prilikom odlučivanja važna je i cijena. Neka je C (Di' (O t) cijena koju moramo platiti ako razvrstamo uzorak iz razreda (O t u područje Dj; to znači da biramo hipotezu i kada je istinita hipoteza k. U našem slučaju imamo četiri mogućnosti: označimo ih simbolima C11, CI :z, C:z 1, C . Funkcija cijene C=C(Dj, (Ot) nudi p nam mogućnost da nekim određemm �pogrešnim) odlukama dodijelirno veće težinske vrijednosti nego drugima. Naravno, izabrat ćemo takvo pravilo odlučiva­ nja koje je u prosjeku "najjeftinije", odnosno pri upotrebi takvog pravila neka je rizik u prosjeku najmanji. U tu svrhu napišemo unaprijed izraz za očekivanu vrijednost cijene. Da bismo mogli napisati taj izraz, trebaju nam: ci priori vjerojatnosti pojavljivanja razreda p ((01) i P ((O :z), funkcija cijene C (Dp (Ot)' i = l , 2, k = l , 2, te uvjetna razdioba gustoće vjerojatnosti uzoraka x pri realizaciji (O k; označavamo je sa P (xl (O k) ·

5.l BAYESOV KRITERIJ ODLUCIVANJA

77

Izraz koji nam određuje rizik možemo prikazati pomoću gornjih podataka i područja odlučivanja Dl i Dl:

R = CuP (001) J P (x I (0 1) dX + D, D.

+ CllP (Oll) J p (x I (01) dx . D.

Potpuno je prirodno da pogrešna odluka pridonosi višoj cijeni negoli pravilna odluka. Dakle vrijedi:

Cl1 > Cu'

Cll > Cn

Naše odlučivanje, u stvari, znači dijeljenje prostora ,D na D l i Dl tako da promatrana točka x iz X padne u D 1 ako je istinita hipoteza 001, odnosno tako da padne x iz X U Dl ako je istinita 001 , Pravilo odlučivanja koje ima za posljedicu najmanji rizik, odnosno najmanju prosječnu cijenu R, nazivamo Bayesovo pravi­

lo odlučivanja.

Budući da vrijedi: D = D l + Dl'

odnosno

možemo zapisati rizik

Dl = D - Dl'

R u obliku:

R = P (001) Cu +P (001) Cll + J

D.

{ [P (0l 1)(Cl 1 - C l l)p (X I Ol l)] -

Naš je zadatak da izaberemo područje Dl tako da rizik R postane minimalan. Prva dva člana gornjeg izraza tvore nepromjenjivi dio rizika. Izraz pod integralom je dio rizika kojem pridonose one točke iz X koje razvrstavamo u Dl ' Budući da smo uzeli da je Cll > Cl 1 i Cu > C ' izrazi u uglatim zagradama su uvijek pozitivni. p Uzorke x za koje Je izraz u drugim uglatim zgradama veći od izraza u prvim uglatim zagradama uključujemo u D zbog njihova negativnog doprinosa integra­ lu. Na sličan način uvrštavamo u h sve one x za koje prvi izraz u uglatim ) zagradama veći od drugoga, odnosno Isključujemo ih iz Dl zbog njihova pozitiv­ nog doprinosa integralu. Uzroci x za koje su oba izraza u uglatim zagradama jednaki nemaju utjecaja na rizik i možemo ih razvrstati po volji. S obzirom na sve to uzorke x razvrstavamo pomoću sljedećeg pravila: Ako je

P (001) (Cll - Cu) P (x I 0l 1) ?: P (001) (Cll -Cn) P (x I (01), uvrstavamo X u D i kažemo da je pravilna hipoteza 001 , U suprotnom slučaju razvrstavamo x u b l (odnosno, to znači da područje Dl "rastegnemo�' tako da pokriva uzorak x) i kažemo da je ispravna hipoteza Oll"

S.

78

STATISTIeKA KLASIFIKACIJA UZORAKA

Drugačije zapisano:

odnosno ....

at,

A (x) � 11, gdje je:

Izraz 11 nazivamo prag odlučivanja, a izraz A (x) omjer vjerojatnosti ili

omjer sličnosti. Izraz A (x) � TJ nazivamo test omjera sličnosti ili test omjera vjerojatnosti. Cesto se pokaže da je računanje ugodnije ako se obje strane izraza omjera sličnosti logaritmiraju:

logA (x ) � IO�l1. Označimo sa jednadžba:

d (x) granicu između područja D 1 logA (x) -log 11 = O.

Granica d (x) dijeli prostor D na područja Dl i Cesto biramo cijene tako da vrijedi:

Cn = Cll= O

D 2; za d (x) vrijedi

D7,'

CU = Cl 1 = 1 .

To znači: pravilna odluka nas ne stoji niita, dok cijena pogrešne odluke iznosi l . U tom slučaju .za R dobivamo:

R = p (m1) J p(x l m1)dX +p(ml) J p (x I ml) dX. D,

Vidimo da taj izraz predstavlja upravo ukupnu vjerojatnost da se odlučimo pogrešno. Pri tako izabrano; cijeni odlučivati u Bayesovu smislu znači upravo odlučivanje tako da smanjimo vjerojatnost pogrešnog odlučivanja na najmanju moguću vrijednost. 5.4. PRAvn.O MlNIMAKS

Kod Bayesova kriterija osim uvjetnih razdioba gustoća vjerojatnost, za odlu­ čivanje trebamo cijene i ti priori vjerojatnosti pojedinih razreda, odnosno hipoteza. U ovom odjeljku razmatrat ćemo kriterij minhnaks koji se upotrebljava kada ne znamo ti priori vjerojatnosti razreda. To je kriterij gdje je najveća moguća cije­ na najmanja. Rješenje problema zahtijeva pronalaženje najnepovoljnijeg Bayesova rizika s obzirom na ti priori vjerojatnosti p (OJ ) i p (OJl)' Budući da je

1

79

5.4. PRAVILO MINIMAKS

p (0) 1) = 1 -p (0)1)' zamjenjujemo U izrazu za rizik R vjerojatnost p (0) 1) vjerojatnoš­ ću l -p (0)1) i pomatramo tako dobiveni rizik R. Imamo: D, D, D, D,

iz gornjeg izraza vidimo da je pri izabranim područjima D l i Dl rizik R jedino još samo funkcija vjerojatnosti p (0)1)' Derivirajmo izraz po p (0)1) i izjednačimo dobivenu derivaciju s nulom. Na taj način dobivamo uvj et za rješenje minimaks. Taj uvjet je: D,

D,

D,

D,

Lijeva strana te jednadžbe je uvjetni rizik r ex,

D,

0>1) ako je uzorak iz razreda 0> 1 : D,

Desna strana jednadžbe predstavlja uvjetni rizik pri poznatom razredu

r ex, 0>l.) = Cn

f p (x I O>l) dX = Cu f p (x I 0>7.) dX.

D,

0>1:

D,

Ako uvrstimo taj uvjet u izraz za Bayesov rizik, dobivamo:

R = Cn f P (X I O>l)dX + C21 J P (xlo>;z) dX D,

Da

D,

D,

= r (X, 0>1) = r (X, 0>1)' Vidimo da je taj rizik nezavisan od tl priori vjerojatnosti i zavisi samo od dijeljenja područja D l i Dl.' Ako mijenjamo granic� izmedu D l i Dz' uvjetni rizici r ex, 0>1) i r ex, O>z) se mijenjaju. Jedan rizik raste, a drugi pada. Granicu d (x) izmedu područja moramo postaviti ondje gdje su uvjetni rizici jednaki:

Odnos prikazuje slika S. l .

5. STATISTICKA KLASIFIKACIJA UZORAKA

80

dixI

tIl1:'

?

SI. 5.1. Prikaz razgraničenja podruqa Dt i D. odlučivanjem pomoću pravila minimaks

d(X)

x

Pri mijenjanjem prelazimo iz jednog uvjetnog rizika (iz onoga koji pada) na drugi uvjetni rizik (onaj koji raste). Ondje gdje su oba uvjetna rizika jednaka, najveći rizik s obzirom na i (debelo izvučena krivulja na slici 5. 1 ) ima najmanju vrijednost s obzirom na D l 1 D 7.' Pretpostavimo da je uvjetni rizik označen sa r takav da mu se može i O)z. Prilikom mijenjati i našem slučaju može poprimiti vrijednosti testa minimaks krećemo se s obzirom na varijablu tako da uzimamo uvijek (krećemo se po najvišem .obronku "planine"), a s najveću vrijednost r ex,

0)1 O)�

x 0)". U

(x, O)A)

O)i

O)i

O) k)

x

0)1

x

obzirom na krećemo se tako da naderno onu točku gdje krivulja koja povezuje najveće vrijednosti r pri mijenjanju indeksa k ima najmanju vrijednost (to je sedlo "planine"). Pravilo minimaks možemo zapisati u obliku:

(x, O)k)

lpih maks r (x, >:eX

....eO

O)k) = d (x).

Granične točke izmedu Dl i postavljamo tako da zauzimaju najpovoljniji i O)z' to znači najmanju vrijednost. Tu smo vrijednost uvjetni rizik s obzirom na označili sa Iz toga proizlazi i ime pravila minimaks. (Vrijednosti jesu dno sedla izmedu dva vrha "planine".)

x

d(x).

0) 1

D2

d(x)

5.5. PRoA� NA M RAZREDA

(M

HIPOTEZA)

Proširimo sada rezultate naših razmatranja sa dva razreda na M razreda (M > 2), odnosno sa dvije hipoteze na M hipoteza. Imamo izvor, odnosno prostor razreda s razredima;

n

odgovarajuće a

priori vjerojatnost: P (0)1)' p (O)l)' . . . , p (O)M)

uvjetne gustoće razdiobe vjerojatnosti:

p (x I 0)1) ' p ex 1 0)2)'

. .

.,

p (x I O)M) '

5.s

81

PROSIRENJE NA M RAZREDA (M HIPOTEZA)

Za slučaj M razreda imamo M" odluka i naravno upravo toliko odredenih cijena Cih• Kod cijene prvi indeks znači da smo izabrali i-ti razred, a drugi da uzorak (koji smo uvrstili u i-ti razred) u stvarnosti pripada razredu m ' Odnose ' k prikazuje slika 5.2.

Izvor

plw,1. plwp

• ... •

p lWr11 Odlučujemo

wH

Sl. 5.2. Proces preslikavanja i odlulitla1fia za slučaj M razreda (M 2)

Izraz za srednju vrijednost rizika M

R je

M

P (Olh)Cih J p (x I Olk)dX. D, i=l k= l Da nademo najmanji rizik, odnosno Bayesovo pravilo odlučivanja, mijenjamo granice područja Di tako da rizik R postane najmanji. To je proširenje postupka optimizacije što smo ga upotrijebili u slučaju dvaju razreda.

R= L L

Da bismo pojednostavnili označavanje i pisanje, ograničimo se samo na slučaj triju razreda, M = 3. Imamo M2 odnosno 9 odluka: l . m istinito, l 2. m istinito, l 3. m l istinito, 4. 012 istinito,

5. 6.

(02 012

x razvrstavamo u D l

x razvrstavamo u D;z x razvrstavamo u D3

x razvrštavamo u D2

istinito,

x razvrstavamo u D

istinito,

x razvrstavamo u D 3

7. (03 istinito, x razvrstavamo u

8. 9.

l

D3 013 istinito, x razvrstavamo u D l 013 istinito, x razvrstavamo u D2•

Vrijedi:

5. STATISTIeKA KLASIFIKACIJA UZORAKA

82 odnosno

Dt = D -Dz -D" jer se područja međusobno ne prekrivaju. U skladu s tim možemo rizik

R napisati u obliku:

R = p (oot ) Gll +P (OOl) GU +P (003) G33 + + J [p (003)(G1 3 - G33)p (x l 003) +P (OOz)(Gu - Gn)p (xl ml)] dx + D,

D, D,

i= 1, 2, . . , M, .

Kao i prije, prva tri člana predstavljaju nepromjenjivi dio rizika, a integrali predstavljaju promjenjivi dio rizika koji je zavisan od granice između područja Dt' Dl i D 3. Rizik R u gornjem izrazu možemo zapisati i u općenitijem obliku:

R=

� G.uP (OOj)+ j� fL�t (G}I; -GU)P (OOI;) P (X I 001;)] j t

dx,

DJ

gdje je u našem slučaju M = 3. U skladu s Bayesovim pravilom odlučivanja razdijelimo prostor D na potpro­ store Dt' D i D 3 tako da svakom x odredimo neko područje iz D za koje je izraz � pod integra.lom najmanji. Označimo integrale koji odgovaraju područjima Dt' Dl i D, simbolima: It (x), Il (x) i 13 (x). Odlučujemo u skladu sa sljedećim nejednadžbama:

It (X) l ) = qt'

o (qt' O) = ql'

x

1: u K:

o (ql' O) = qo i o (q2 ' l ) = qt '

Dijagram prijelaza stanja za automat prikazuje slika

6.4.

Sl. 6.4. Konačni automat

Pretpostavimo da se na ulazu u automat nalazi niz x = OOI I OO I I i da je automat u početnom stanju qo' Ulazna glava promatra znakove niza slijeva udesno. Kada prvi put utvrdi znak O, automat mijenja stanje qo u stanje ql' Sljedeći znak O vraća automat u stanje qo' Na sličan način prvi znak l mijenja stanje automata u qt' a sljedeća jedinica vraća ga u qo' Niz x ostavlja automat u stanju qo' Automat A je prihvatio niz x ako i samo ako ga je niz x ostavio u jednom od mogućih konačnih stanja. Skup svih nizova koje prihvaća automat A je: T (A) = {x l o (q, x) u

F} ,

gdje

o (q, x ) od ređuj e stanje automata nakon pročitanog niza x . Automat A možemo upotrijebiti za razvrstavanje uzoraka u dva razreda uzoraka: Uzorke koje automat prihvaća razvrstavamo u razred uzoraka 0) 1 " Sve one uzorke koje automat otklanja (ne prihvaća) razvrstavamo u razred O)l'

6.4. STRUKTURNO RAZVRSTAVANJE UZORAKA S obzirom na spoznaju iz odjeljka 6.2 možemo razvrstavanje uzoraka zasnovati na sljedeći način: Svakom razredu uzoraka pridružujemo vlastitu gramatiku. Gramatika Gi sa svojim pravilima u skupu PI opisuje svojstva uzoraka u razredu uzoraka 0)1' Svaki uzorak predstavljamo pomoću konačnog niza znakova. Uzorci iz razreda O)i čine jezik L (Gl) gramatike Gi. Imamo toliko gramatika koliko imamo- i razreda uzoraka. Uzoru s nizom x uvrštavamo u razred 0)1 ako je pomoću analize rečenice (niza) utvrđeno da je

6.4.

95

STRUKTURNO RAZVRSTAVANJE UZORAKA

X EL (Gj)

,

X E V�.

Na taj način smo problem razvrstavanja uzoraka sveli na analizu rečenice. Problem analize možemo grafički prikazati trokutom (sl . 6.5.). Trokut ispunjuje­ mo u skladu s pravilima iz skupa P. s

s

Sl. 6.5. Rečenična analiza

Svaki konačni znak a jE VT U nizu XE V� moramo povezati, pomoću međučvo­ rova - varijabla A E VN' S početnom varijablom S u skladu s pravilima P. Ako nam to uspije, tada je xEL (G). Postoji cijeli niz općih i problemski usmjerenih postupaka analize rečenica kon­ tekstno slobodnih jezika (A. V. Aho, 1972). Opisat ćemo postupak koji je predložio Earley (J. Earley, 1 970).

Earlyjev postupak analize rečenice: Kontekstno slobodna gramatika G = ( VN, VT, P, S) i ulazni niz x = a 1 , az, . . . , an' n � O, X E V} .

Ulaz:

Izlaz: Popisi analize rečenice lo, ll' . . . , lp . . , III' Postupak: (A) sastavljanje popisa lo: .

l . korak:

2.

korak:

3. korak:

Ako je pravilo S --+ Cl iz skupa P, uvrsti u popis lo postavku [S--+ . Cl, O], gdje točka označava znak koji nije u VN ili VT' Korake 2 . i 3. ponaVljaj dok je moguće uvrštavati nove postavke u popis lo' Ako je u popisu 19 postavka [B--+ 'Y ' , O], uvrsti u lo postavku [A --+ ctB · p, O] za sve LA --+ Cl ' BP, O]. Pretpostavimo da je postavka [A --+ Cl ' BP, O] u popisu lo. Za sva pravila B--+'Y iz P uvrsti u lo postavku [B--+ 'Y ' , O] (ako se već ne nalazi u popisu). (B) Sastavljanje popisa lj kada su popisi lo, ll' . . . , IJ - 1 već sastavljeni:

4.

korak:

S. korak:

6. korak:

za svaku postavku [B --+ Cl ' a p, j] iz popisa IJ - , gdje je a = ap uvrsti u popis lj postavku [B--+ cxa ' p, .l. Korake S. i �. ponavljaju đok je još moguće uvrštavati nove postavke u popis ln' Neka je postavka [A --+ 'Y ' , .1 iz popisa lj' Potraži u popisu II postavke [B--+ Cl ' A P, k]. za svaku postavku kOJU nadeš uvrsti u lj postavku [B--+ Cl ' p, k] . Neka bude postavka [A --+ Cl ' BP, j] iz popisa I). Za sva pravila B --+'Y iz . P uvrsti u lj postavku [B --+ · 'Yll .

Kraj pottupka: Niz

Je

je iz L (G) ako i samo ako je u popisu I. postavka [S--+Cl., O].

96

6.

NENUMERICKO (SINTAKTICKO) RASPOZNAVANJE UZORAKA

Pokušajmo utvrd iti da li je rečenica

ima gramatiku G

==

(VN' VT'

x=

P, S), gdje je:

(a +a)*a

VN

{S, A l ' A , J

VT

{a , (,) , + ,

P:

iz

j ezika L (G). J e zik L (G)

*}

S->A I + S S->Al

Al -> A /Az A l ->A z

Primijenimo Earlyjev postupak analize rečenice: U prvom koraku uvrstimo u popis lo postavke [S-> . Al + S, O]

[S-> . A l ' OJ,

u trećem uvrštavamo još

Ponovnim izvršavanjem trećeg koraka dodajemo popisu postavke Nakon toga više nije moguće uvrštavati nove postavke u popis lo ' U četvrtom koraku uvrštavamo u popis 11 postavku smo uzeli u obzir da je al C. =

[Al -> C ' S),

O]. Pri tom

U šestom koraku možemo uvrstiti u I I još [S-> ' A l + S, 1 ], [S-> ' A l' l ], l ], [A l -> ' A z' 1 ], [Al-> ' (S), l j i [Al-> ' a, 1 ]. To su ujedno sve postavke ll ' [A 1-> ' A l *A l,

Pri sastavljanju popisa II uzimamo u obzir da je uvrštavamo u Iz postavku [Al ->a ' , 1 ] .

al = a.

U četvrtom koraku

U petom koraku uzimamo tu postavku tako da u I potražimo one postavke koje imaju znak A z desno od "lažnog" znaka točke.I Nalazimo dvije takve postavke, Zbog toga u II uvrštavamo [A 1 ->A z · *Al, l] i [A 1 ->A 2 ' , l ] .

Druga postavka zahtijeva ponovno pretraživanje popisa 11' Sada tražimo postavke koje sadrže · A l• Nalazimo dvije takve postavke. Uvrštavamo ih u l : [S->A1 ' + S, 1] ; [S->A ' , l ] Ponovo druga postavka zahtijeva da se u jl 1 uvrsti postavka [Al -> (S ' ), u]. Sada je popis II popunjen. .

Potpune popise analize rečenice prikazuje slika 6.6.

6.5.

97

SINTAKTlCKO RASPOZNAVANJE UZORAKA POMOCU STOHASTICKIH JEZIKA la

II

lo

[ S-+o A l + S , eJ

[ A 2 -+ ( o S ) , e ]

[A2-+a ' , 1 J

[S-+A l + o S , 1 )

[ S-+ o A l ,e J

[ S-+o A l + S , 1 J

[A l -+A2 - *A l , 1 ]

[ S-+o A l +S,3J

[A l -+ o A 2 *A l ,eJ

[ S-+ oA l , 1 J

[A l -+A2 - , 1 J

[ S-+o A l , 3 J

[ A l -+ o A 2 ,4tJ

[A l -+o A 2 *A l , 1 J

[ S-+A l ' +S , 1 J

[A 1 -+ · A 2 *A l , 3 J

[ A 2-+ 0 ( S ) ,eJ

[A l -+ o A 2 , 1 J

[ S-+A l ' , 1 J

[A 1 -+ · A v 3J

[A2-+ o a ,e J

[A2-+0 ( S ) , 1 J

[A 2 -+ ( S ' ) ,eJ

[A2-+ o ( S> , 3 J

,

[A2 -+ · a .. 3 J

[A2-+o a, 1 J

h

ls

[A2-+a o , 3 J

[ A 2-+ ( S ) o , e J,

[A l -+A 2 * - A l ,.J

[A2-+a - .. 6J

[A l -+A 2 o *A l , 3J

[ A l -+A 2 " *A l ,e J

[ A l -+o A2 *A l ,6J

[A l -+A2 ° *A l ,6J

[A l -+A2 o , 3J

[A l -+A 2 " ,e J

[ A l -+ o A 2 , 6J

[A 1 -+A 2 - ,6J

[ S-+A l - + S , 3J

[ S-+A l o +S , e J

[ A 2-+o ( S ) ,6 J

[A l -+A2*A l - ,e]

[ S-+A l o , 3 J

[ S-+A 1 0 , e J

[A2-+ o a , 6 J

[S-+A l - + S , e J [S-+A l - , e]

[ S-+A l +S - , 1 J [A2-+( S ;' ) , eJ Sl. 6.6. Potpuni popisi rečenične analiza za razmatrani primjer

Budući da j e u popisu 17 postavka

[ S-A l ' , O], niz

x

je element jezika L (G).

6.S_ sINTAKnćKo RASPOZNAVANJE UZORAKA POMOĆU STOHASnCKDI JEZIKA

U realnim primjerima raspoznavanja uzoraka u obzir moramo uzeti šum koji utječe na uzorke i pogreške koje nastaju prilikom odredivanja osnovnih sastavnih dijelova objekta koji se prepoznaje. Nepreciznost i nesigurnost opisivanja uzoraka možemo obuhvatiti primjenom teorije vjerojatnosti (K. S. Fu, 1 974) ili teorije razmazanih skupova (R. De Mori, 1 976). Te probleme možemo rješavati i pomoću transformaci;skih gramatika (A. K. Joshi, 1 973; B. K. Bhargava, 1 974), pomoću aproksimacija (T. Pavlidis, 1 976) iIi pomoću odgovarajućih postupaka analize rečenice (S. Y. Lu, 1 977; K. S. Fu, . 1 977). Razmotrimo modeliranje uzoraka sa šumom pomoću teorije vjerojatnosti. Stohastička (slučajna) gramatika je četvorka:

GS = ( VN, VT> Ps, S),

gdje je VN skup meduznakova (neterminala), VT skup konstanata (terminala), S početni znak u VN' a Ps = (P, D) skup pravila oblika:

98

6. NENUMERICKO (SINTAKTICKO) RASPOZNAVANJE UZORAKA

Ovaj nam zapis kaže da možemo s vjerojatnošću p zamijeniti niz Skup L (G.) je stohastički jezik gramatike G S :

p (x)

o:

nizom �.

K

L:1 Pr

}=

gdje je K broj pravila koja nas iz S dovode u x. Tako je svakom nizu x konačnih znakova iz skupa V;: pridružena vjerojatnost P (x) s kojem gramatika GS gradi taj niz. Nepoznati uzorak opisan nizom x uvrštavamo u razred uzoraka (op i = 1 , 2, . . . , M, tako da ga analiziramo sa svakom stohastičkom gramatikom GSI = ( VT' VN'

Ps , S). I Pomoću analize rečenice dobivamo vjerojatnosti: p (x l GS); i= 1 , 2, . . . , M, koje nam govore s kakvom vjerojatnošću gramatika Gs gradi niz x. Uzorak koji je opisan nizom

x

razvrstavamo u onaj razred

p (GSI I x) =

(Oi

za kOli Je vjerojatnost

P (Gs) P (x I Gs) P (x)

najveća. Pri tome je P (x) vjerojatnost uzorka koji je opisan nizom x, p eGs ) vjerojatnost gramatike Gs" odnosno njoj odgovarajućeg razreda (Oi' I

plx/G s'l 1

Izbor IIQjveće Y/'ijednosH

plxlG.21 x

Odluka

plx/GoIII Sl. 6 . 7. Blok-shema sustava za raspoznavanje koji se temelji na stohastičkim gramatikama

Slika 6.7 prikazuje blok-shemu sustava za raspoznavanje koji se temelji na upotrebi stohastičkih gramatika. Razmotrimo sada kako se iz skupa uzoraka za učenje

Rt = {(x 1, n1),

• • •

,

(x.., nJ,

o o .

,

(XN> n� }

6.6,

99

SINTAKTICKO OPISIVANJE UZORAKA

ocjenjuju vjerojatnosti u skupovima Dl' i = l , 2, . . . , M. Sa Xh smo označili niz konačnih znakova, a sa nh njihovu učestalost. Izvedimo analizu rečenice nad svakim nizom. Sa N l (xJ označavamo broj y ponavljanja pravila Ar" P1 iz skupa Ps prilikom analize ruza xh• Matematičku naiiu broja ponavljanja pravila A{"'+ PA: iz skupa PSr prilikom analize nizova iz skupa Rt izračunavamo kao: , n1jk =

gdje

L nh ' p (Gs, ! xJ NiJA: (xJ,

x" e R,

'

p eGs ! xJ označava vjerojatnost da je niz xh izgrađen pomoću gramatike Gs'Vjerojatnost pravila A{"'+ Pt iz skupa Ps, možemo ocijeniti sa: nljl Pijl = �' .t.... nijl �

I

Suma u nazivniku uzima u obzir sva pravila u skupu strani varijablu AJ'

Ps koja imaju na lijevoj '

Lee i Fu (H. C. Lee, 1972) dokazali su da se ocjena Pil ' približava pravoj vrijednosti vjerojatnosti pravila Pijt ako se broj nizova u s�upu Rt približava . beskonačnosti i ako su ispunjeni sljedeći uvjeti: l ) Rt je skup nizova konačnih znakova jezika L (Gs), i = 1, 2, vrijedi Rt-+L =

2) Ocjena vjerojatnosti niza xh e Rt

_ _ _

, M, tako da

M

U L (G s).

1= 1

približava se pravoj vrijednosti vjerojatnosti. 3) U postupku učenja moguće je odrediti vjerojatnost P (Gs' l x) za svaki niz x eRi• Naravno, vrijedi: M

L p eGs, ! x) = l .

i= 1

Vrlo se često uzima da je p (Gs, I x) = l /M.

6.6. SINTAKTICKo OPISIVANJE UZORAKA Da bismo realizirali sintaktički sustav za raspoznavanje, moramo opisati uzorke pomoću formalnih jezika. Za to treba imati: osnovne elemente od kojih ćemo graditi uzorke, - operacije udruživanja elemenata u rečenice. Pri izboru elemenata valja naglasiti da želimo da ih bude što manje različitih tipova. Na taj način dobivamo pri sintaktičkom raspoznavanju jednostavnije gramatike. Što je manje tipova elemenata, to se u većoj mjeri objekti mogu opisati

6. NENUMERICKO (SINTAKTICKO) RASPOZNAVANJE UZORAKA

1 00

kao rekurzivne funkcij e osnovnih elemenata. Freeman (H. Freeman, 1 96 1 ) predlo­ žio je lančani kod (engl. chain code) koji opisuje uzorke kao slijed od osam osnovnih elemenata, odnosno smjerova (sl. 6. 8a).

bl

Sl. 6.8. Opis uzoraka "lančanim" kodom

Uzorak opisujemo tako da na njega prvo položimo kvadratnu mrežu i zatim ga prekrijemo osnovnim elementima tako da se oni što bolje poklapaju s uzorkom (sl. 6.8b). Jedina relacija koja nastaje pri ovom načinu opisivanja uzoraka j e slijedno nizanje elemenata, odnosno "ulančavanje" strelica prethodnog elementa s repom sljedećeg. Uzorak prema slici 6.8b možemo zapisati rečenicom: 1 8681 8, koji se može generarirati kontekstno osjetljivom gramatikom.

/"., ttll

SI. 6.9. Element opisnog jeZika za slike

t�

h

o-b

t {xI AJ�x} . U našem primjeru s u pravila koja imaju na lijevoj strani A l i Al ekvivalentna. Ujedinjujemo A l i Al i brišemo pravilo koje se najviše puta pojavljuje u skupu pravila. Dobivamo pravila:

S-CA l

A4-bAs

S -bA4

As-b

A1-b

As- aA s

A I -aA1

A l i As su takoder ekvivalentna pravila. Njih takoder ujedinjujemo. Budući da u pravilima naše gramatike nema više ekvivalentnih pravila, postupak smo završili.

6. NENUMERICKO (SINTAKTICKO) RASPOZNAVANJE UZORAKA

106

Iz ulaznog skupa nizova "naučili" smo gramatiku: G = (VN, VT, P, S),

gdje je:

VN = {S,A,B} P:

S-+cA S-+bB A-+aA B-+bA A-b

Jednostavno se možemo uvjeriti da je to gramatika koja generira ulazni skup nizova.

6.S. LITERATURA A. V. Aho, J. E. Hopcroft, J. D. Ullman, A General Theory of Translation, Math. Syst. Theory 3, 193 221, 1969. A. V. Aho, ]. D. Ullman, The Theory of Parsing, Translation and Compiling, Vol. I, Premice-Hall, Englewood Cliffs, New Jersey, 1972. B. K. Bhargava, K. S. Fu, Transformation and Inference of Tree Grammars of Syntactic Pattern Recognition, Proc. 1974 IEEE Int. Conf. on Cybernetics and Society, Dallas, 1974. W. S. Brainerd, Tree Generating Regular Systems, Inf. Control, 14,217, 1969. N. Choinsky, Three Models for the Description of Language, PGIT, Vol. 2, N°. 3, str. 113 -124, 1956. R. DeMori, P. Tomasso, Lexical Classification in a Speech Understanding System Using Fuzzy Relations, Proc. IEEE Conf. Acoustics, Speech and Signal Processing, IEEE, Piscataway, N. J., 1976. ]. Earley, An Efficent Context-free Parsing Algorithm, Comm. ACM 13:2, str. 94 -102, 1970. J. Feldman, S_ Decidobility Results on Grammatical Inference and Complexity, Artifical Intelligence Memo. 93, Computer Science Dept., Stanford University, Stanford, 1969. H. Freeman, on the Encoding of Arbitrary Geo1Mtric Configurations,IRE Trans. El. Comp. EC-lO, str. 260 -268, 1961. K. S. Fu, Error-Correction Parsing fur Syntactic Pattern Recognition, Data Structure, Computer Graphics and Pattern Recognition, A. Klinger, K. S. Fu, T. Kunii, Eds., Academic Press, New York, 1977. K. S. Fu, B. K. Bhargava, Tree Systems fur Syntact� Pattern Recognition, Symposium on Computer Image Processing and Recognition, University of Missouri, Columbia, 1972. K. S. Fu, Syntactic Methods in Pattern Recognition, Academic Press, New York, 1974. E. B. Hunt, Artificial Intelligence, Academic Press, New York, 1975. A. K. Joshi, Remarks on S_ Aspects of Language Structure and Their Relevance to Pattern Analysis, Pattern Recognition, 5 (4),1973. H. C. Lee, K. S. Fu, A Syntact� Pattern Recognition System with Learning Capability, Iriformatirm Systems-COINS-72, J. T. Tou, Ed., Plenum Press, New York, 1972. S. Y. Lu, K. S. Fu, Stohast� Error-CurTet:tUw Synlax Analysis fur Recognition of Noisy Patterns, IEEE Trans. Computers, C-26, (l2), 1268, 1977. . T. Pavlidis, Syntactic Pattern R"ognition on the Basis of FlI1fCtionaJ Approximation, Pattern Recognition aItd Artijical Intelligence, Chen, C. H., Ed., Academic Press, New York, 1976. A. C. Shaw, Parsing of Graph-Representable Pictures, J. ACM, Vol. 17, No. 3, str. 453 -481, 1970. J. T. Tou, R. C. Gonzales, Pattern Recognition Principles, Addison-Wesley Publishing Company, Reading, Massachusetts, 1974. -

PRIMJERI SUSTAVA ZA RASPOZNAVANJE

7.

PRIMJENA ORTOGONALNE HAAROVE TRANSFORMACIJE U RASPOZNAVANJU I AUTOMATSKOM DIJAGNOSTICIRANJU SIGNALA EKG (Prof. dr. Slobodan Ribarić, dipl. ing.)

7.1. UVOD . Elektrokardiogram je pronađen 1887. godine. U fazu eksperimentalne upotre­ be u Evropi se uvodi početkom 1900. godine, a nekih desetak godina kasnije i u Sjedinjenim Američkim Državama. Međutim, tek tridesetih godina ovog stoljeća elektrokardiogram ulazi u §iru upotrebu. Sredinom pedesetih godina pojavila se ideja o automatizp.ciji elektrokardio­ grama, da bi krajem pedesetih godina to postala stvarnost (c. A. Caceres, 1973). Prvi sustavi pojavili su se početkom šezdesetih godina. Prva javna demonstracija potpunog sustava bila je na znanstvenom skupu American Heart Association 1962. godine. Komercijalni sustavi pojavili su se početkom sedamdesetih godina. Razvoj tehnologije i računalske tehnike omogućio je djelotvornu primjenu računala u području automatske interpretacije signala EKG. Razlozi za primjenu računala su sljedeći (M. L. Simoons, 1975): - Sum u signalu EKG može se reducirati usrednjavanjem (engl. averaging) većeg broja perioda signala .. Prije usrednjavanja treba izlučiti valne oblike koji se bitno razlikuju od tipičnog signala EKG (na primjer, ventrikular­ ne iii supraventrikularne ekstrasistole, sl. 7.1), te točno odrediti stabilnu točku početka periode. Za tu točku uzima se obično vrh vala R ili

Sl. 7.1. Pnm;er YJentrikuJarne ekstramtolne

u

snimci EKG

7. PRIMJENA ORTOGONALNE HAAROVE TRANSFORMACIJE ...

lIO

OJ

Sl. 7.2. Signal EKG

s

oznakom valmh oblika i intervala

najstrmiji dio spojnice valova Q i R (sl. 7.2). To se teško može izvesti automatski bez primjene digitalnog računala. Točnost mjerenja karakterističnih veličina digitalnim računalom je 0,005 mV ili čak i veća, dok se vizualnim očitavanjem postiže točnost samo od 0,05 mV. Prilikom vizualnog očitavanja signala EKG moguće su subjektivnosti promatrača. Računalo tu mogućnost isključuje (H. Blackburn, 1969); u uskoj vezi s tim je i ponovljivost interpretacije i dijagnoze EKG. Mjerenja nagiba i trenutnih promjena u .EKG-u za vrijeme testa optere­ ćenja mogu se izvesti samo pomoću računala. Posmpak donošenja dijagnoze može se poboljšati primjenom ekspertnih sustava u kojima se pomoću baza podataka (znanja) i mehanizma zaklju­ čivanja dobiva dijagnoza koja je jednakovrijedna dijagnozi skupine eksperata (S. Ribarić, 1983). Osim toga, računalo za EKG u on-line okolini zamjenjuje tehničko osoblje u zadacima kao što su postavljanje radnih točaka i kalibriranje opreme, određivanje protokola ispitivanja, automatski zapis signala EKG, automatski zapis ostalih signala kao što su krvni tlak i respiratorni parametri, te automatsko generiranje sažetka interpretacije EKG-a za potrebe datoteke o pacijentima. Računalo ujedno trenutno detektira izrazite nenormalnosti u sustavu za zapis EKG-a (ispadanje elektroda, neispravan kontakt elektroda, pomak osnovne linije i st). Danas se na svjetskom tržiAtu mogu naći sustavi za automatsku analizu i dijagnozu elektrokardiograma. Ti se sustavi sastoje od procesnog računala, instru­ mentacije za sniIianje i konverziju signala i posebnih programskih modula. Poznati su takvi sustavi tvrtki Hawlett-Packard, IBM i Siemens. Na domaćem tržištu može se naći uredaj za analizu i interpretaciju signala EKG koji se zasniva na mikroprocesoru. Uredaj je rezultat viAegodiinje suradnje grupe iz Laboratorija za sisteme, automatiku i kibemetiku (Fakulteta za elektrotehniko, Ljubljana), tvornice Gorenje i ekipe liječnika Kliničkog centra u Ljubljani. Grupa se već vi§e od deset godina bavi istraživanjem i razvojem sustava za automatsku analizu, interpretaciju i dijagnozu EKG u testu opterećenja (L. Gyergyek, 1975, 1978).

7.2. HAAROVA TRANSFORMACIJA SIGNALA EKG

111

Obrada signala EKG uglavnom se temelji na dva opća pristupa. Prvi pristup je uvjetovan iskustvom liječnika kardiologa. Program računaia identificira u vremenskom prostoru fiziološki i klinički značajne parametre, kao Ato su valovi P, Q, R, S, T, nagib segmenta ST i drugo (sl. 7.2), te na temelju njih postavlja dijagnozu. Drugi pristup, koji se tek potvrđuje u širem krugu stručnjaka, zasniva se na primjeni matematičkih postupaka u analizi signala EKG (L. Gyergyek, 1977). U ovom ćemo poglavlju opisati metodu u kojoj se primjenjuje drugi pristup. Signal EKG se može iz vremenskog prostora pomoću neke transformacije presli­ kati u neki drugi prostor i tako se o njemu viAe doznati. Posebno su zanimljive . diskretne ortogonalne transformacije što ih upotrebljavamo za raspoznavanje nekih karakterističnih svojstava koja se u originalnoj funkciji (signalu) teAko nalaze (S. Ribarić, 1976). Za analizu i raspoznavanje karakterističnih točaka signala EKG upotrebljavamo Haarovu transformaciju zbog njezina važnog svojstva - lokalne osjetljivosti (A. Haar, 1910), (S. Ribarić, 1976).

7.2.

HAAROVA TRANSFORMACIJA SIGNALA EKG

Signal EKG snimljen je u skladu sa standardom za test opterećenja u laboratorijima za ergometriju (Thalassotherapija u Opatiji, Klinički center u Ljubljani). Frekventno moduliran signal EKG zapisan je standardnim magnetof0nom. Magnetofonska vrpca sa snimkom analizirana je na Fakulteti za elektroteh­ niko u Ljubljani. Analogno-digitalni pretvarač (10 bita) pretvara analogni signal u digitalni oblik. Frekvencija uzorkovanja je oko 800 Hz. Nakon izlučivanja šuma (V. Valenčič, 1974) i ekstrasistula, diskretni signal EKG transformiramo u Haarov prostor. Haarova transformacija se temelji na skupu Haarovih ortogonalnih funkcija l koje su definirane u intervalu [O, l):

1(0, O;

x) = l , J'Y(n)

I (n, k; x) =

-J'Y(n) ;

O�x� l

k l - 1, prikazani su odredeni lokalni odsječci funkcije I(x) i zato ih nazivamo lokalnim fUDkcl,ama. Funkcije x (O,

O; x) i x ( 1 ,

l;

x)

su globalne funkcije.

Za diskretnu funkciju ft. izračunavamo Haarovu transformaciju Xt, na sl;ede-· ći način:

[X}]

[JI] �],

gdje je: [JI] Haarova transformacijska matrica, [Xt,] Haarova transformacija dis­ kretne funkcije ft., N broj diskretnih vrijednosti funkcije ft., odnosno Xt,. �] matrica diskretnih vrijednosti funkcije ft. (dimenzija za N x l ),

1

[HJ"'

I'[ II

1

1

1

-1

II

•

•

I'[

•

II 2

I'[ -I'[ -I'[

l! •

-2

•

•

II

•

•

• 2

• -2

II

•

II

•

•

II

-1

•

-1

•

-1

• I'[ -I'[ -I'[ •

• -2 II

•

• II 2

•

• •

-2

Sl. 7.4. Haarooa transformacija matrica za N =8

1 13

7.2. HAARO VA TRANSFORMACUA SIGNALA EKG

Slika 7.4 prikazuje Haarovu transformacijsku matricu za N = 8. Ako je N = 2", gdje je k cijeli broj, primjenom brze Haarove transformacije izračunavamo XN sa samo 2 (N -1) zbrajanja, odnosno oduzimanja (V. J. Rejchart, 1 972). Slika 7.5 prikazuje graf brze Haarove transformacije za N = 16. Grana u grafu izvučena pl,lnom linijom označava zbrajanje, a crtkana linije oduzimanje. Oznaka .fi nad punom linijom označava množenje s

.fi.

Fo

lo

F,

fl 12 ')

fi

fi

'4

fi {'l

{1

ls 16 17

I.

f'i

ho

1 ,2

f'i

f'i

f'i

f'i

f'i

i'I

vi

vi

y'i.

y'i.

f'i

lu 114

i'I

11 5

f'i .fi

f'i

f'i

111

f'i

f'i

f'i

19

iZ

f'i

f'i

f'i

vi

vi

f'i

Sl. 7.5. Graf brze Haarove transformacije za N

vi.

=

F2 F) F. Fs F6 F7 Fa F, FlO F l1 F 12 Fn F14 F1S

16

Za ilustraciju prikažimo računanje Haarove transformacije za funkciju koja ima N = 8 diskretnih vrijednosti: A, B, C, D, E, F, G, H. Na klasičan način računamo Haarove koeficijente, odnosno Haarovu transformaciju:

+A+B+C+D+E+F+G+H= X (O, O) +A+B+C+D -E -F -G -H = X (l , l) l

= -2X (2, 2

+A+B+C -D

l)

l

+E +F - G-H= 22X(2, 2) l

+A -B

= 2X (3, 1 ) l

+C-D

= 2X (3, 2) +E -F

l

= 2X (3, 3) l

+G -H=2X (3, 4).

1 14

7. PRIMJENA ORTOGONALNE HAAROVE TRANSFORMACIJE . . .

Za računanje Haarove transformacije na klasičan način za N = 8 potrebno je 2 (23 - 1)+21 (2:3 - 1 )+21 (21-1) = 24 zbrajanja i oduzimanja. Općenito, za raču­ nanje Haarove transformacije za N=2" potrebno je zbrajanja i oduzimanja: 2 (2k - l) +21 (2"-1 - 1) + . . . +2 "-1 (21- 1) = 2"·k. H. C. Andrews je prvi upozorio na postojanje brze Haarove transformacije (H. C. Andrews, 1 970). Brza Haarova transformacija, općenito, zahtijeva zbrajanja i oduzimanja samo:

21:+2"-1+ . . . +2=2 (2"-1). Primjer računanja brze Haarove transformacije za tablici 7.1 . Tablica 7.1. Prikaz

� .. o

::ot::

O A

1

A+B

N=8 (k=3)

prikazan je u

računanja brze Haarove transformacije 2 (A +B) +(G+D)

3 [(A +B) +(G+D)] + + [(E+F) +(G+H)] =X (O, O)

B

G+D

(E +F) +(G+H)

-[(E+F) +(G+H) }=X(1,1)

.p o e!.

3) Ponovo tvorimo razlike, ali sada Haarovih komponenata razreda višeg za jedan (Haarovih komponenata koje sadrže informaciju s intervala širine osam vremenskih uzoraka): IX(6,J)-X(6, j-1)1 IX(6, j

l ) -X(6, j-2)1

Kada ustanovimo da je jedna od razlika veća od praga e2, uzimamo Haarovu komponentu razreda koji je opet viši za jedan i ponovno računamo razlike. Postupak se nastavlja sve dok se na dva uzorka točno ne odredi"interval na kojem se nalazi koljeno J. Tablica 7.2.

Vrijednosti pragova i

ej

ej

1

70

2

25

3

15.9

4

11.3

Pragovi el' e e3, e4 određeni su eksperimentalno (S. Ribarić, 1974) uz � pomoć signala EKu iz skupa za učenje (Elektrokardiogram, odvod CM 5, 78 pacijenata). Tablica 7.2 daje vrijednosti pragova el do e4• Slika 7.9 prikazuje način određivanja koljena J. Kada se utvrdi položaj koljena J u Haarovom prostoru, taj se položaj preslikava u vremenski prostor. Pomak koljena J u odnosu na nultu razinu signala jest srednja vrijednost uzoraka u okolini točke J (oko 5 ms u vremenskom mjerilu).

Određivanje nagiba segmenta ST Segment ST je spojnica između kompleksa QRS i vala T. kazličite bolesti prouzrokuju promjene na segmentu ST: promjene razine i promjenu nagiba.

7. PRIMJENA ORTOGONALNE HAAROVE TRANSFORMACIJE . . .

120

Nagib i položaj segmenta ST važni su za dijagnosticiranje mnogih bolesti (lezija, perikarditis, subendokarni infarkt) (M. J. Goldman, 1973). Po�etak segmenta ST definiran je krajem kompleksa QRS (koljeno J), dok je kraj segmenta definiran početkom vala T. Vrijeme trajanja segmenta ST zavisi od frekvencije otkucaja srca. Ako propišemo fiksno trajanje segmenta ST, možemo načiniti pogrešku pri određivanju nagiba (sl. 7.10) jer tada val T utječe na nagib segmenta ST. Ako skratimo interval i dodijelimo mu čvrstu vrijednost, gubimo . informaciju o duljini segmenta, a ona je važna za dijagnosticiranje ishemije.

Sl. 7.10. PogreIka u određivanju nagiba spujnice ST u sJulaju fiksnog

wemena

trajanja

Problem smo riješili tako da smo propisali interval od 75ms i uveli kontrolu trajanja tog interv:ala. Ona se provodi tako da se pomoću Haarovih komponenata koje sadrže informaciju o šesnaest vremenskih uzoraka traži početak vala T, i to po jednakom kriteriju (prag e,!), kao pri traženju koljena J. Ako računalo na raspoznaje početak vala T, uzima se interval 75ms kao vrijeme trajanja segmenta" jer je utjecaj vala T na nagib ST vrlo malen, tako da je pogreška u određivanju nagiba zanemarljiva. Ukoliko računalo registrira početak vala T koji se nalazi unutar intervala 75 ms, skraćuje se trajanje segmenta ST. Na taj način dobivamo dinamičku zavisnost trajanja segmenta ST od frekvencije srca, odnosno oblika EKG-a. Na tako određenom intervalu nagib segmenta ST određujemo na dva načina: aproksimacijom segmenta ST optimalnim pravcem u odnosu na srednju kvadrat­ nu pogrešku i pomoću Haarov'ih komponenata koje su definirane na tom intervalu.

7.4.

LBSTEROVA DIJAGNOSnčKA METODA

Lesterova dijagnostička metoda, koju upotrebljavamo kao jednu od modula za obradu signala EKG u testu opterećenja, razvrstava elektrokardiograme u tri razreda: normalni, nenormalni i granični. Osnova za to razvrstavanje su dva klinički važna parametra: nagib segmenta ST i depresija koljena J. Slika 7.11 prikazuje kriterije razvrstavanja EKG-a poLesterovo; metodi. Slika 7.12 prikazu­ je primjere izlaznih lista računala s rezultatima analize kompleksa QRS, valova P, Q, S, T iLesterove dijagnostične metode. Liječnik s ulaznom listom dobiva i grafički prikaz signala EKG s ispisom indeksa vremenskih uzoraka.

7.4.

121

LESTEROVA DIJAGNOSTICKA METODA

.. 6 ;;::

ES ,..: "'4 E :;;3 E

�2

i z'

Or-

��E-----------------------

____

oo,

-2

BGlestan

-3 -,

o

-2

-3 -4 -S [mm] Depresija IIOI/ena J

Sl. 7.11. Kriterij za raZ'f!rstauanje EKG po LesterOfJoj metodi

Taj povećani grafički prikaz signala može mu poslužiti za provjeru dijagnoze koju je dalo računalo. •

lJ t:.

ll! ...; g -2 '" :g .>< d

:�

�

-1

t:. .

e-

o

o

.

�

A

Ocjena lijelnika

Hoorovo. transformacija Metoda ('2')

t

!:.

t:. o

A .

A o

.

A

CI.

'"

&

CI

o

2

3

4

S

(,

I

I

I

7

8

9

I

I

10

"

I

12

..

N testova.

Sl. 7.13. Usporedba rezullata u odredifJanju depresije koljena J

•

',4

o A

�

D A

� O, 8 '"

�O,4 z

0,2

-0,2

liječnIku � o

A

',0

0 (' i .. ,

Otjeno

Hoarovu tra.nsform(l(ija.

A H!ta.dIl [12]

o

.

11',2 ...,. '"

o

D

tt.

� A

.

A

o

t:.

o

2

4

5

6

D 8

o

9

10

N testova.

Sl. 7.14. Usporedba rezultata u odrediuanju nagiba segmenta ST

Sustav za automatsku analizu i dijagnozu signala EKG razvijen je i ispitan na računalu PDP 11/40, dok su kao ulazni podaci upotrijebljeni filtrirani i digitalizi­ rani signali EKG koji su dobiveni pomoću maloga procesnog računala HP 2116,

122

7. PRIMJENA ORTOGONALNE HAAROVE TRANSFORMACIJE ...

ANAL rSIS AND RECOGNITION ECQ

TAPE NO N"I'IE S3

6/S QRS CO"PLEX RECOGNITION

POSITION OF STEEPEST NEGATIVE SLOPE

131

WIDTH OF QRS CONPLEX A"PLITUDE OF R WAVE J POINT INTERVAL POINT DEPRESSION J ST SLOPE R-R1 WAVE

68.400MSEC 9.417l'1l'I 137- 135 -1I.7'8MM '.282I'1V/SEC ....EXISTS

Q WAIIE RECOGNITION AIWLlTUDE PEAK POSITION START END IiIDTH

-11.6671'1" 1.4 97 104 12.611111'1SEC

P WAVE RECOGNITlOft AlWLlTUDE PEAK POSITION START END WIDTH

1.4171'11'1 52 21 73 93.6OOIISEC

S WAVE RECOGIIITION S WAVE IS NOT SIGNIFICANT T WAVE RECOGNITION ANPLlTUDE PEAK POS ITION START END WIDTH

-1.5"1'1" 222 177 248 127.81I11'1SEC

BASE LINE RECOGNITION NN INTERVAL VALUE OF BASE LINE t•

TESTER OlAGNOSIS "ETHOD •

\1

90RDERLINE PQ INTERVAL••••••••• •••• • • 136.81I1I'1SEC ST INTERVAL............... 75.60f1I'1SEC QT INTERVAL • •••••••••••••• 271.8'III'I SEC Q/RRATIO.................. -'.'71

73-

811

191....

123

7.4. LESTEROVA DIJAGNOSTICKA METODA

ANALYSIS AND RECOGNITION ECQ

NAME

TAPE NO

TEST 521178

S 2

QRS COMPLEX RECOGNITION POSITION OF STEEPEST NEGATIVE SLOPE

131

WI DTIi OF QRS COI'IPLEX AMPLITUDE OF R WAVE J POINT INTERVAL POINT DEPRESSION J ST SLOPE R-R1 WAVE

118.se'MSEC 9.448.... 157- 155 -'.538111 '.863MV/SEC ••••ABSENT

Q WAVE RECOGNITION

IZ:

'

-1.635"" 1.2 89

AMPLITUDE PEAK POSITION START END WIDTIi

••

1.9 36 ....MSEC

P WAVE RECOGNITION AMPLITUDE PEAK POSITION START END WIDTH

..

..

,. .. .. ..

.. ..

,.

2.115MM

..

46

...... .. .... � oo .. ..

17 81 115.2HMSEC .. .. .......... .. .... . ....................

OI .......... .. ......

S WAVE RECOGNITION AMPLITUDE PEAK POSITION

...... .. .. .. ..

..

" ..

..........

.. ..

1 . 969l1li

-

152

.. ....

T WAVE RECOGNITION AMPLITUDE PEAK POSITION START END WIDTH

.... .. .... .. ........ ..

..

................

...... .. ............ ................... .. .. ...... .. ..........

1.6981'1f11 223 193 244 91.8HltSEC

BAse LINE RECOGNITION NN INTERVAL VALUE OF BASE LINE

81- 88 169.625

LESTER DIAGNOSIS METHOD NORMAL PQ ............... 129.6e'MSEC ST INTERVAL............... 68.441.MSEC QT INTERVAL••••••• •••••••• 279._MSEC Q/R RATIO.............. ••• ..173

Sl. 7.12. Primjeri izlaznih lista računala s rezultatima

na

analiza i dijagnozom

7. PRIMJENA ORTOGONALNE HAAROVE TRANSFORMACIJE ...

124

Sustavom smo analizirali elektrokardiograme više od 60 pacijenata u testu optere­ ćenja. Na slici 7.13 i 7.14 prikazana je usporedba rezultata dobivenih interpretaci­ jom liječnika, primjenom Haarove transformacije i računalske dijagnoze u vre­ menskom prostoru (V. Valenčič, 1975, K. Turkulin, 1980). a �

8.

170

lIaarOftI transfllnlal:1ja. H.1adG112J

t;. e

160

t;. e

·2

4

6

8

W tl

� � � � N t.stOYQ Sl. 7.J5. UstxJredba rezultata odredivania nulte razine (nivoa) NN

7.5. LITERATURA C. A. Caceres, The Case Against Electrocardiographic Automation, Computer, Vol. 6, N°. 7, juli 1973, str. 15-21. M. L. Simoons et al., On-Line Analysis of Exercise Electrocardiograms, Vol. 8, N°. 7, juli 1975, str. 42 -45. H. Blackburn u djelu: Measurement in Exercise Electrocardiography, 'The Ernst Simonson Conference, Springfield, Ill., Charles C. Thomas, 1969. L. Gyergyek, Procesiranje in razpoznavanje elektrokardiograma, Fakulteta za elektrotehniko, Ljubljana, znanstveno-istraživački zadatak za SBK, Ljubljana 1975. L. Gyergyek et al., Pregled dejavnosti skupine Fakultete za elektrotehniko v Ljubljani na podroiju analize in razpoznavanja signaloo EKG, Elektrotehniški vesnik, Vol. 45, N°. 5, Ljubljana, str. 197- 199. L. Gyergyek, N. Pavešić, S. Ribarić, Use of Fast Haar Transfarm and Shannon's Theory of Information in ECG Diagnosis According to Lester Method, Computers and Mathematical Models in Medicine, Lecture Notes in Medical Informatics (ed. D. A. B. Lindberg), Springer-Verlag, Berlin, 1977, str. 5-23. S. Ribarić, Magistrska naloga, Fakulteta za elektrotehniko, Ljubljana, 1976. A. Haar, Zur Theorie der Orthogonalen Funktionesysteme, Math. Ann, Vol. 69, 1910, str. 3 1 1-371. V. Valenčič, ]. K. Tront� , L. Gyergyek, K. Turkulin, Analysis Recognition, and Diagnosis of Electrocardiogram, 3 Conference on Bioengineering, Budapest, 1974. V. ]. Rejchrt, Signal Flour Graph and Fortran Program for Haar-Fourier Transform, IEEE Trans. on Computers, septembar 1972. L. Gyergyek, S. Ribarić, N. Paveiić, on the Use of Haar Transform for ECG Recognition, l . Jahrestagung Osterreichische Gesellschaft fUr Biomedizinische Technik, Graz, maj 1976, str. 7 1-76. L. Gyergyek, S. Ribarić, Recognition and Analysis of ECG Signals, Proceedings of the DECUS 78. J. Wartak, J. Milliken, J. Karehmar, Computer Program for Pattern Recognition of Electrocardiograms, Computer and Biomedical Research, 4, 1970. H. C. Andrews, W. K. Pratt, Digital Image Transform Processing, Proc. 1970, Walsh Functions Symposium. L. Gyergyek, Računališka diagnoza elektromiograma in elektrokardiograma, Poročilo znanstveno-raz­ iskovalne naloge, što pogodbe 124, SBK, Ljubljana, 1974. S. Ribarić, Diplomsko delo, Fakulteta za elektrotehniko, Ljulhljana, 1974. M. J. Goldman, Principles of Clinical Electrocardiography, 8 Edition, Lange Lange Medical Publications, Los Altos, 1973. 1h M. J. Goldman, Principles of Clinical Electrocardiography, 8 Edition, Lange Medical Publications, Los Altos, 1973. V. Valenčič, Magistrska naloga, Fakulteta za elektrotehniko, Ljubljana, 1975. K. Turkulin, et al., Automatska analiza elektrokardiograma u opterećenju, Međunarodni simpozij Neinvazivne metode, Dubrovnik, april 1980. •

.

8.

SUSTAV ZA RASPOZNAVANJE BROJCANO-SLOVNm ZNAKOVA

(Prof. dr. Ludvik Gyergyek, dipl. ing., prof. dr. Nikola Pavešić, dipl. ing., prof. dr. Slobodan Ribarić, dipl. ing.)

8.1. UVOD U posljednja dva desetljeća ulažu se veliki napori u istraživanje, razvoj i primjenu metoda i tehnika raspoznavanja znakova. Od jednostavnih sustava u prošlosti za raspoznavanje nekoliko strojno tiskanih znakova, današnji sustavi su se razvili u vrlo složene "inteligentne" sustave za raspoznavanje rukom pisanih znakova (na primjer, cijelog skupa znakova za programski jezik FORTRAN).

8. 1):

Takvi sustavi raspoznaju širok spektar rukom pisanih znakova i simbola (sl. •

brojčane znakove,

•

brojčano-slovne znakove,

•

skup znakova i simbola viših programskih jezika, Katakaha·znakove i dr.

•

Razvoj sustava za raspoznavanje koji su potpomognuti bazama znanja i mehanizmima zaključivanja smanjit će jaz između čovjeka i stroja i povećati mogućnosti njihova izravnijeg saobraĆ8flja (T. Kanade, 1 983). Upravo takva težnja je izražena u sustavima računala pete generacije. Njihova osnovna značajka je primjena umjetne inteligencije i raspoznavanja uzoraka u što izravnijem komu­ niciranju s računalom (S. Ribarić, 1 983, E. K. Yasaki, 1 982). Tipičan sustav za raspoznavanje znakova ili, kako se jednostavno naziva, optički čitač (engl. Optical reader) sastoji se od sljedećih funkcionalnih dijelova (sl. 8.2): • • • • •

optičkog skanera (pretražnika) ili jedinice za unos i digitalizaciju slike, podsustava za lociranje i segmentiranje znakova, pretprocesora, podsustava za izlučivanje osnovnih značajki, podsustava za razvrstavanje (klasifikaciju).

126

8 )\ , i

s

8.

SUSTAV ZA RASPOZNAVANJE BROJUNO·SLOVNIH ZNAKOVA

r

9

�

J

J

I'

,.

k

7

1

7

)"

'7

b

�

o

"

G

s-

$'

:;

s-

q

q

q

q

't

a

8

8

8

�

7

�1'

'7

'1

7

b

6

G

,

6

t-

s-

s

t

..t-

!s-

9 f

l.,

if

.f.

lt'.

4-

ft

4-

tt

4-

tl-

lJ..

�

3

3

3

.3

.s

.3

3

"

.a

3

..}

cl

2

l

'"

2.

2

Z.

7v

2

J..

1

1

!

l

1

1

I

,

1

i

,

o

o

()

4

o

�

D

o

o

p

o

D123�56ZK 8 'BC IJE F G"HI

al

O1234-5678Q ABCDEFGHI JKLMNoPQR STUVWXY� c)

bl

7t-T'::'X=f/I\t:

7'\*Y�b.j.=c-r �371)JI,.tI/D77

KI.MNOeGE2S [1 SZ W XY;Z

7-1?I�:tJ:t:7'T :J -iJ� A t '}� T \?

O123't567gQ dl

:;

\\ o

_

�)

Sl. 8.1. Primjeri ulaznih :makova za StUl4Ve raspoznavanja: a) Primjeri broj&Jnih znakova napisanih rukom b) Broj&Jno-slmmi :makllĐi (američki uandard) e) Broj&JM-slWlli :enakooi (japamJei sta.l'Ulllrd) d) Brojčani :maIu1vI' (kanadski standard) e) Katakana-znaktNi (japanski nandard)

127

8.1. UVOD

,--- -- - - --- --Računalo - -- --- -- -- --- - l ". I I

I

I I L

Ulaz

lociranje i segmentacija znakova

Raspoznavanje i donošenje odluke

L--_-----' _ _____

____ _

Digitalizacija

Znakovna matrica

Glađenje. filtriranje i normalizacija

Podudaranje

I

I I

......J

Razred znakova

Sl. 8.2. Funkcionalna blok-shema sustava za raspoznavanje znakova

Zadnja četiri bloka tipičnog optičkog čitača obično su izvedena pomoću računala. Ulaz u sustav za raspoznavanje je rukom napisani znak ili simbol. U fazi razvoja, ispitivanja i provjere ttspješnosti sustava istraživači se obično služe već standardnim skupovima uzoraka (tzv. bazama podataka). Na primjer, Munsonova baza podataka sastoji se od 46 znakova i simbola programskog jezika FORTRAN II i ima 12 760 uzoraka, od kojih je više od polovine dobiveno izravno od 49 korisnika računala. Highleymanova baza podataka sastoji se od 36 brojčano­ -slovnih znakova, odnosno od l 800 slova i 500 brojeva. Znakovi su napisani u predviđena pravokutna okna i to olovkom tvrdoće HB (c. Y. Suen, 1980). Rukom pisani znakovi i simboli se optičkim skanerom digitaliziraju i unose u sustav za raspoznavanje. Znak simbol je obično u digitalnom obliku prikazan binarnom matricom1). Dimenzije matrice su različite, od 12 x 12 slikovnih elemenata (High­ leymanova baza podataka) od 24 x 24 (Munsonova baza podataka) ili 64 x 52 slikovna elemenata (T. Sepešy, 1975). Svaki ulazni uzorak se locira i segmentira. To se izvršava računalom uz pomoć programske podrške. Izlaz iz podsustava za lociranje i segmentiranje znakova (matrica znaka) upućuje se pretprocesoru. Pretprocesor gladi matricu (popunjuje prekide i rupe u linijskim segmentima), izlučuje šum (na primjer šum "salt-and-pepper") i normalizira uzorak (Uklanja utjecaj povećanja, rotacije uzorka i sl.). Značajke bitne za postupak razvrstavanja izlučuju se u podsustavu za izlučivanje. Podsustav za razvrstavanje klasificira uzorak u jedan od razreda na temelju njegovih značajki. Razvrstavanje se obično temelji ili na primjeni funkcija odlu­ čivanja ili na sintaktičnim metodama (S. Ribarić, 1982). Tehnike raspoznavanja rukom pisanih znakova i simbola zavise od izabranih značajki, načinu njihova izlučivanja i do primijenjenih shema razvrstavanja. Tehnike raspoznavanja prema osjetljivosti na izobllčenje uzorka u pr� tlčnoj izvedbi (c. Y. Suen, 1980) mogu se podijeliti na one u kojima se upotrebljavaju: globalna svojstva uzoraka, raznolikost distribucije slikovnih elemenata, geometrijska i topološka svojstva uzoraka. ') Matrica koja ima elemente O i I.

128

8. SUSTAV ZA RASPOZNAVANJE BROJCANO-SLOVNIH ZNAKOVA

Izobiličenja slike uzorka nastaju zbog: a) luma koji ima za posljedicu prekid linijskih segmenata, procjepa u linijama, mrlje i zapunjene . lukove ili nepotrebno povezane linijske segmente, b) izobličenja uzorka lokalne promjene u uzorku, kao što su zaoblje­ nost kutova, izbrisani ili stanjeni linijski segmenti i sL, c) promjene u stilu pisanja uzorka različito pisanje crtica na znakovima (7, 1) ili koso pisanje znakova, d) translacije - pomaci cijelog znaka ili njegovih dijelova, e) rotacije - promjene u orijentaciji znaka. -

Sum se u sustav unosi optičkim skanerom a nastaje zbog pogreške u sustavu, površine na kojoj se znak upisuje ili unosi sredstvom za pisanje. Izvor izobličenja uzorka i promjene u stilu je sam čovjek - pisac znakova. Translacija i rotacija uzorka može nastati. dvojako: zbog pisanja znakova ili kao posljedica svojstva mehaničkog dijela sustava.' Praktična izvedba tehnike raspoznavanja odnosi se na sljedeće faktore; to su: a) način generiranja maski za razvrstavanje, odnosno da li je lako automatski generirati maske koje odgovaraju svakom razredu znakova i na temelju njih razvrstavati nepoznati uzorak, b) brzina razvrstavanja znakova, c) složenost tehnike, d) nezavisnost tehnike. Postupak uspješno razvrstanih uzoraka je za različite sustave i za različite ispitn� uzorke u granicama od 70% do 100% (L. D. Larmon, 1972; C. Y. Suen, 1980). Uobičajene tehnike u kojima se upotrebljavaju globalna svojstva uzorka jesu podudaranje maski (engl. template matching), korelacije i transformacije. Transformacije (npr. Fourierova, Walshova, Haarova, Hadamardova) upotreblja­ vaju se za redukciju količine podataka i izlučivanje značajki koje su invarijantne prema nekim globalnim deformacijama (npr. prema translaciji i rotaciji). U jednom razredu tehnika koje reduciraju diri:tenzije značajki upotrebljava se statistička raspodjela slikovnih elemenata ulaznog uzorka. Različiti tipovi raspo­ djele odgovaraju različitim tehnikama raspoznavanja. Tehnike "razbijanja" ulazne slike u zone i procjene gustoće slikovnih elemenata u tim zonama omogućavaju razvrstavanje uzoraka. U taj razred tehnika spada i primjena momenata slikovnih elemenata znaka s obzirom na izabrani koordinatni sustav. Zanimljiva je i primje­ na n-torki u raspoznavanju!), primjena presjecišta linijskih segmenata i mjere udaljenosti.

��� }bJ4>� +� 8 .; " \I"r\)(

Sl. 8.3. Neka topološka i geometrijska svojstva uzoraka ') Vidi poglavlje 14.

129

8.1. UVOD

U tehnikama što se temelje na izlučivanju značajki koje opisuju geometrijska ili topološka svojstva iskorištava se Činjenica da su ta svojstva neosjetljiva na izobličenja i promjene u stilu pisanja. Neka topološka i geometrijska svojstva koja se upotrebljavaju u tim tehnikama prikazana su na slici 8.3 (linije i lukovi, krajnje točke, presjecišta linijskih segmenata, oblici). Tablica 8. 1 prikazuje usporedbu različitih tehnika s obzirom na njihovu osjetljivost prema izobličenju slike i pogodnosti za praktičnu izvedbu tehnike raspoznavanja. Tablica 8.1.

Usporedba načina raspoznavanja v

Kriterij

Neosjetlji vost na izobličenje slike

OI)

·s OI)

..s := .... fil OI)

c:: OI)

..s

::::;"

�

u!

El

� :c

N -

j:I.,

5 E!::

Podudaranje s maskom

+

o

-

Transformacija

-

+

Područja

-

Momenti

..s

::;a (.)

..s o �

-

+

o

o

Momenti n -torke SjeciMa i udaljenosti

Način raspoznavanja

o

.S' o

Jednostavnost izvedbe

OI)

.§ ...

:g ..s

..s

.�

.... fil

o c::

OI) ON

.... fil

o c:: .� >

::!:

...

C:Q

o til

Z

-

+

-

o

-

+

+

o

-

-

o

-

-

o

-

+

+

-

o

-

+

+

o

-

o

-

o

-

o

-

o

-

+

+

o

-

+

+

+

o

-

+

+

-

-

+

+

+

o

-

+

o

+

::s

lei)

...

....

!3

OI)

Globalna svojstva uzoraka

Distribucija slikovnih elemenata

Geometrijska i topoloIka svojstva + o

veliko iIi lako malo ili telko srednje

13 0

8. SUSTAV ZA RASPOZNAVANJE BROJCANO·SLOVNIH ZNAKOVA

U ovom poglavlju opisat ćemo tehniku raspoznavanja u kojoj se upotrebljava­ ju globalne značajke i koja se temelji na Fourierovoj transformaciji. Sustav je razvijen na MIT-u (G. H. Graniund, 1972). Na temelju originalnog rada G. H. Granlunda jednak sustav je razvijen i ispitan u Laboratoriju za automatiku i kibernetiku (Fakulteta za elektrotehniko, Ljubljana) 1975. godine. Sustav je upotrijebljen za razvrstavanje rukom pisanih slova i brojki: (A, B, e, e, e, D, Đ, E, F, G, H, I, J , K, L, M , N, 0, P, Q, R, S, S, T, U, V, W, z, 2:, Y, X; O, 1 ,2,3 , 4,5,6, 7 , 8, 9).

8.2. KONFIGURACIJA SUSTAVA ZA RASPOZNAVANJE Slika 8.4 prikazuje komponente sustava za raspoznavanje pomoću kojeg smo ispitali metodu G. H. Granlunda. Uzorci su napisani na posebnim bbrascima (sl. 8.5) i pomoću televizijske kamere se unose u sustav. Jedinica za digitalizaciju ima UlO Cf _i ,--_ ...,,

t

�

....J

_

---

Rolunolo (DC - CYBER 72174

Bušena papirna nIKa

Sl. 8.4. Komponente sustava za raspoznavanje

na raspolaganju tri dimenzije matrica: 16 x 12 ,32 x 16 i 64 x 52 elementa. Iako su standardne matrice dimenzije 24 x 24 (Munsonova baza podataka) ili 12 x 12 (High1eymanova baza podataka), odlučili smo se za matricu dimenzija 32 x 16 iz sljedećih razloga (T. Sepešy, 1975): iskustva s raspoznavanjem numeričkih znakova s matricom dimenzija 16 x 12 pokazala su da je relativna pogreška u raspoznavanju ispitnih brojki velika (pogl. 9), pri raspoznavanju slova imamo tri puta više razreda uzoraka, uzorci slova iz različitih razreda međusobno su sličniji negoli oni kod brojki. Pomoću međusklopa digitalni se podaci prikupljaju u procesno miniračunalo HP 21 16 e. Izlaz iz miniračunala je digitalizirana slika, opisana sa 256 sivih razina i zapisana na perforiranu papirnu vrpcu. Ti su podaci ulaz za daljnju obradu računalom eDe-CYBER 72/7 4. Za potrebe eksperimenta upotrijebili smo bazu podataka od trideset i jednog razreda po 7 uzoraka (ukupno 217 uzoraka za slova) i deset razreda, svaki po 15 uzoraka (ukupno 150 uzoraka za brojke). Ugađanjem jedinice za unos podataka i brižljivim izborom osvjetljenja i praga binarizacije

8.2.

KONFIGURACIJA SUSTAVA ZA RASPOZNAVANJE

131

Sl. 8.5. Obrasci za upis .uzoTaka

dobiveni su kvalitetni uzorci (digitalizirane binarne slike; sl. 8.6), tako da je faza pretprocesiranja izostavljena (izlučivanje šuma, popunjavanje linijskih segmenata i slično).

132

8. SUSTAV ZA RASPOZNAVANJE BROJCANO-SLOVNIH ZNAKOVA

.,(:1,0: u : I(I(I(XI II " II: '( . ' ( ( I[ ( I( II:I.'X

xx, 1]11 IC

nu '" :t1U

U '(

1( 11 '( 11

)( .(]I:

X I[ X

X X .(

XXU

:tI .(

lXI

XX,

,xx X,U

xa:.(

xx, .XUXIIX'(1f

UX

. '( '(1[ ,( I['( X '(I[ U XXA:"'.(

If X '( X U '('f'.C X 1If lf A: l l lf "( '

'( '.C IC 1 U X '( U X

lI C U

)11[ ".(

1 )(

x x ( o . X X '( '(I[ X X ,1II[

X'U

IUI

nl

'C u

X (X'.C X X '( U X xx 111'1(

XXI

X U If

xn

UX(

X (J'(

I I O[

XXXX

Jr'(

X lf X .( l I Of O{.( )(

XXU

1( 111: )(1[UIC

I.X

XI[IC

1( .( U

I( U '.C U U : X U : lC

'" l)flt

X::ll[

X X ,(

1I: t' ( 1C . U: U X )[

I Cl! K '( IO ' X X 'C X

1flI ,( )( )( I .( I[ )Oflf

lUX

'UX X X IC X

"

1f )( 1( 1I )0( 1 1 ( ( )f 1l I[ )( �

.(n

" If U .. . 1I K 1( X

lXX XXI lU IClI: X K U U lI. lI

)f K ,( I[ 1I K I. K I I 1I 1[ )( )(1(1111 K If ,( )(

I I X I I[ ( I .( 1I[ X .( X ::l .( I X 1 X 'I' X If

. IC )( I[ H I[ ' U 1I 'U).J:J(

Il l' '( lC .( l' l l' '( .c , l' 11 1[ "( ,( ' '' . C(1' ( U ,,, 1t U . 1C

xx,

:('UI:

'xx x IC'(

JJX'( ,XX

X'X

X."X

'( I X X X lf X l l lf lf X

XU

UU

I .( X U X U X '.C U ,

'( U (

'(XJIJ'(

I J[1(lf lf U , I. K .( lO I IfJ( X

X U X X ( X XXXXXXX;(I(J'(

'II:'r: )( j( . U lf U J( ' II( l(

"( X X ;( ll O tXXXX(lCX'.C X X X (�X,(XX lC.( X I U U 1

I I U )( )( Ii:X K X '(

,xx

xiuu'UlIun

I I U 1[ I[ U .( )( )(

1 1 )( I[ X j(

I IC I X I(

I['( K.(X'(1

UJ:

'( u u

3 X U U X U "( X lO: I [I[ X '(

XIU

U

'( IOOC

.lUX

XU

1( 1I 1f )(

UU

ICO'

( " ,( l X I

.ox

I I[ I X J( .( .( l If (

1 101

' X j( j( 1[

u XlI U lI 1 U X )[ (

X U X JC)I ( '( .( X IOOI IC X I X

XC,

,XX

U lili:

IXUXX

,XX

XX,

X It:"J' IC '( U X X X

'XX

'XX

looooe

'x x

I[ .( .( X

'xx

JJXX

'XX

XOIX

I[ I[ X I I .( I X

,xx xxx

I I I OC X ( IC'U.(j(1

'xx

,x x xx,

X .( '(lI

'xx

1 II: IOClClC ' CJC U U lI

'xx

I X "( X

",

Ul

X X '( '.( ",

'XX

,n ,xx

X . (J( .(

X

XUX

IC IC U « ( '( U IC X

,xx ,XX

nllf

"( 1lI IC 'Ul

XlX

X If lt,

:iIlC

I X C X U : I X IC ( U

X IC IC

(XC

]]'" [a�O) exp [j.] R exp [jq>]]'" t [a 1O)+ Ja] '" [atlO) "] '" d'. (o) ",,, ' [a;O)]'" + " _

-

Vidimo da su značajke tf"," invarijantne prema translaciji, rotaciji i povećanju. Na sličan način kao za slučaj značajke bl možemo definirati značajku d;"l koja je zavisna od rotacije:

= tf��) exp [ - jmq>] , Ako postoji zajednički faktor k za m i sljedeći način:

n,

možemo značajke tf"," zapisati na

d"," što daje relaciju

Kada m i n nemaju zajedničkog faktora k (k = I), vrijedi

d;"" = d",,.. Jednostavno

se

može utvrditi da vrijedi i d"," = b,.;

što znači da su značajke b" samo poseban oblik značajki d", ", 8.5. POSTUPAK RASPOZNAVANJA Uzorak je zapisan u binarnoj matrici dimenzija 32 x 26, i to tako da su kontura i njegova unutrašnjost prikazani jedinicama, a ostali dio matrice nulama. Kontura odnosno funkcija u (t) određuje se sljedećim postupkom:

1 39

8.S. POSTUPAK RASPOZNAVANJA

Analizira se redak za retkom matrice sve dok se ne nade prva jedinica. Tada se ispituje njena okolica i traži najbliža jedinica. Postupak se nastavlja sve dok se ne obide cijela kontura, odnosno dok točka P ne dođe opet u početnu točku. Ispitivanje se provodi u osam smjerova (sl. 8. 1 0). Svakoj jedinici elementu konture pripada jedna realna i jedna imaginarna komponenta - one predstavljaju kooridi­ nate točke u sustavu x, jy. lB}

1

14'

/ {\ 1 3)

aj

• 111

21

16}

"\JJ" "(j\,,

..

Sl. 8.10. Smierovi ispitivanja sustava

1

•

12}

14}

bl

Nakon odredivanja konture računaju se Fourierovi koeficijenti diskretne kompleksne funkcije u (t). Bez ispitivanja i pokusa nije moguće odrediti tip značajki koje bi učinile postupak raspoznavanja djelotvornim. Tip značajki u sustavu za raspoznavanje odreden je eksperimentalno na skupu uzoraka za učenje (G. H. GranIund, 1 972). Za eksperiment smo upotrijebili sedam značajki:

Taj izbor ne znači i najbolji izbor. Tri značajke su takve qa uz informaciju o konturi sadrže i informaciju o rotaciji. To je potrebno da bi se u sustavu za raspoznavanje mogli razlikovati parovi uzoraka koji pripadaju razredima e i U, Z i N, te 6 i 9. Budući da su općenito značajke kompleksne, ulazni uzorak u prostoru značaj­ ki je predočen vektorom sa četrnaest komponenata. To znači da svakom ulaznom uzorku pripada točka u četrnaestodimenzionalnom prostoru. Uz pretpostavku da točke-elementi svakog razreda tvore u prostoru grupe, možemo za svaki razred naći točku (težište) koja karakterizira odredeni razred. Postupak razvrstavanja ulaznog uzorka temelji se na računanju udaljenosti točke koja opisuje taj uzorak od karakterističnih točaka pojedinih razreda. Uzorak se klasificira u razred uzoraka za koji je ta udaljenost najmanja (metoda najmanje udaljenosti). Takvim algoritmom klasifikacije dobivena je točnost sustava za raspoznavanje od 95,85% što je za 2, 15% slabije od ocjene u izvornom radu G. H. GranJunda. Za test raspoznavanja može se broj značajki izabrati po volji. Veći broj značajki ujedno znači i povećanje vremena potrebnog za razvrstavanje uzoraka, a ne jamči bolje rezultate raspoznavanja. Kako i koliko značajki izabrati da se rezultat raspoznavanja poboljša a da vrijeme razvrstavanja ne bude predugo? Rješenje ćemo potražiti primjenom statistike i teorije vjerojatnosti.

140

8. SUSTAV ZA RASPOZNAVANJE BROJCANO-SLOVNIH ZNAKOVA

Pretpostavit ćemo (G. H. Graniund, 1972) da je distribucija značajki normal­ na i budući da su značajke kompleksne, bit će distribucija dvodimenzionalna. Gustoća vjerojatnosti p (x, y) odredena je izrazom: p (x, y) =

Q (x,

� [ - � Q (X' ] [l (X -a)l l 2r (x -a) (y -b) (Y-b?] l '

2xGXG)I l -rl I

l

-r

Gx

exp

y) ,

GxG .,

+

G.,

gdje x i y označavaju realnu i imaginarnu komponentu, a i b su njihove aritmetičke srednje vrijednosti, G; i G ; su njihove prirodne varijance, a r je korelacijski faktor:

gdje je

gdje je

n

broj komponenata.

Iz dvodimenzionalnih normalnih distribucija može se za svaku značajku naći skup korelacijskih elipsa za svaki razred uzoraka (T. Sepešy, 1 975; G. H. Gran­ lund, 1972). One nam govore da sa pretpisanom vjerojatnosti P (c) značajka pada za odredeni razred c unutar odgovarajuće vjerojatnosne elipse. Tamo gdje se elipse prekrivaju vrijednosti značajki za uzorke iz različitih razreda su približno jednake. To znači da se razredi po toj značajki ne mogu potpuno razlikovati. Znači, za veću razlučljivost razreda bolje su one značajke za koje se vjerojatnosne elipse za isti PCc) što manje prekrivaju. Slika 8. l l a prikazuje vjerojatnosne elipse za značajke d31 i razred uzoraka od N do X. Vidimo iz slike da se, na primjer, uzorci iz razreda R i Z ili N i U mogu razlikovati na osnovi te značajke budući da im se elipse ne prekrivaju. Zahvaljujući distribuciji pojedinih značajki i razreda uzorka može se primije­ niti bolji postupak razvrstavanja uzorka II razrede. Prikažimo to na pojednostav­ njenom primjeru. Radi lakšeg razumijevanja upotrijebit ćemo trodimenzionalni prostor, što praktično znači da uzorke razvrstavamo na osnovi samo jedne značajke. Neka broj razreda bude 2 (A i B). n uzoraka razreda A odreduje normalnu distribuciju P/J (x, y), a n uzoraka razreda B odreduje Pb (x, y). Nekom nepoznatom uzorku pripada u prostoru značajki točka G koja je odredena vekto­ rom G = [Xc> YJ. Računamo gustoću vjerojatnosti II toj točki za razred A:

� = Pa [Xc> YJ

i razred B:

Ako umjesto točke G uzmemo u obzir malo područje �S, imat ćemo odgovarajuće vjerojatnosti Pa i Pb' koje nam pokazuju kolika j e vjerojatnost da točka G, odnosno nepoznati uzorak, pripada razredu A, odnosno razredu B.

141

8.5. POSTUPAK RASPOZNAVANJA

0 3 1 N +X

D 13 A + M

8. SUSTAV ZA RASPOZNAVANJE BROJCANo-SLOVNIH ZNAKOVA

142 D 12 A + M G

Sl. 8.11. aJ Primjer vjerojatnosnih elipsa za značajku d i raZTed uzoraka od N do X bJ Primjer ] vjerojatnosnih elipsa za značajku d31 i raZTed uzoraka oY A do M ej Primjer vjerojatnostnih elipsa za značajku du i razred uzoraka od 4 do M

Ulazni, nepoznati uzorak razvrstava se u razred A �o vrijedi

U opisanom sustavu za raspoznavanje ovaj pojednostavnjeni postupak razvr­ stavanja proširen je za 7 značajki i 3 1 razred. Nepoznati se uzorak razvrstava u razred koji ima najveću vjerojatnost (različiti koeficijenti dlRlI su nezavisni te se može definirati logaritamska relativna vjerojatnost da uzorak pripada određenom razredu). Primjer ispisa rezultata razvrstavanja prikazan je na slici 8. 12. Sustav za raspoznavanje realiziran je računalom Cyber 72/24 tvrtke CDC. Programska podrška omogućava generiranje konture i računanje Fourierovih koeficijenata. Te se operacije računalom opće namjene izvode sporo zbog velikog broja potrebnih operacija. Primjenom posebnih procesora za brzo računanje Fourierovih koeficijenata postupak se raspoznavanja može ubrzati (G. H. Gran­ lund, 1 972; W. R. Cyre, 1972; M. C. Pease, 1969). Ispitivanje ove metode pokazalo se da ona daje dovoljno dobre rezultate (pogreška 2,3%) unatoč izrazito različitim ulaznim uzorcima.

143

8.6. LITERATURA

ULAZNO SLOVO .. Z

RASPOZNAlO SLOVO " Z

ULAZNO SLOVO .. Z

RASPOZNAlO SLOVO .. Z

ULAZNO SLOVO .. Z

RASPOZNAlO SLOVO .. Z

ULAZNO SLOVO .. Z

RASPOZNAlO SLOVO .. Z

ULAZNO SLOVO .. Z

RASPOZNAlO SLOVO .. Z

ULAZNO SLOVO .. Z

RASPOZNAlO SLOVO .. Z

ULAZNO SLOVO .. Z

RASPOZNAlO SLOVO ... Z

ULAZNO SLOVO .. ZZ

RASPOZNAlO SLOVO " Z Z RASPOZNAlO SLOVO " Z Z

ULAZNO SLOVO .. ZZ ULAZNO SLOVO .. ZZ

RASPOZNAlO SLOVO " ZZ

ULAZNO SLOVO .. ZZ

RASPOZNAlO SLOVO " ZZ

ULAZNO SLOVO .. ZZ

RASPOZNAlO SLOVO ... ZZ RASPOZNAlO SLOVO .. ZZ

ULAZNO SLOVO .. ZZ

RASPOZNAlO SLOVO ... Z Z

ULAZNO SLOVO " Z Z

RASPOZNAlO SLOVO '" II

ULAZNO SLOVO " II

RASPOZNAlO

ULAZ NO SLOVO .. II

ULAZNO SLOVO .. II

SLOVO ... II .

RASPOZNAlO SLOVO .. II RASPOZNAlO SLOVO '" II

ULAZNO SLOVO .. II

RASPOZNAlO SLOVO ... II

ULAZNO SLOVO .. II

II II RASPOZNAlO SLOVO ... Y RASPOZNAlO SLOVO '" Y ' RASPOZNAlO SLOVO .. Y

ULAZNO SLOVO .. II

ULAZNO SLOVO .. II ULAZNO SLOVO .. Y

ULAZNO SLOVO .. Y

ULAZNO SLOVO .. Y

ULAZNO SLOVO .. Y

RASPOZNAlO SLOVO

...

RASPOZNAlO SLOVO

...

RASPOZNAlO SLOVO ... Y RASPOZNAlO SLOVO .. Y

ULAZNO SLOVO .. Y

Y

RASPOZNAlO SLOVO ... Y

ULAZNO SLOVO .. X

RASPOZNAlO SLOVO " X

ULAZNO SLOVO

..

ULAZNO SLOVO .. Y

RASPOZNAlO SLOVO .. Y

RASPOZNAlO SLOVO .. X

ULAZNO SLOVO .. X

RASPOZNAlO SLOVO " X

ULAZNO SLOVO " X

RASPOZNAlO SLOVO .. X

ULAZNO SLOVO .. X

RASPOZNAlO SLOVO .. X

ULAZNO SLOVO " X ULAZNO SLOVO .. X

RASPOZNAlO SLOVO " X

ULAZ NO SLOVO .. X

RASPOZNAlO SLOVO .. X

POGRESNO JE RASPOZNAT I H

ODBACENIH JE

• SLOVA

RELATIVNA POGRESKA JE

UIOME7B UIOME711

!lIAPOMENA:

5 SLOVA

2 . 311

X

I I I I END OF L I S I I I I I I I II END OF L I S I I I I I

Z Z označava sl ovo Z

Sl. 8.12. Primjer ispisa rezultata razvrstavanja

8.6. LITERATURA S. Ribarić, Peta generacija sustatJa računala, VTG, br. 6, 1 983. str. 726 -734. T. Kanade, R . Reddy, Computer Vision: The Challenge of Imperfect Inputs, IEEE Spectrum, Vol. 20, novembar 1 983, str. 88 - 9 1 . E . K . Yasalti, Tokyo Looks t o the '90s. Datamation, januar 1982. The State of the C. Y. Suen, M. Berthod, S. Mori, Automatic Recognition of Handprinted Characters Art, Proce edings of the IEEE, Vol. 68, N°. 4, april 1 980, str. 469 -487.

L. D. Harmon, Automatic Recognition of Print and Script, Proceedings of the I EEE, Vol. 60, N°. 10, oktobar 1 972, str. 1 165 - 1 1 76. G. H. Granlund, Fourier Preprocessing for Hand Print Character Recognotion, IEEE Trans. on Compt, februar 1 972, str. 1 95 -201. T. Sepešy, Diplomski rad, Elektrote hnički fakulteJ u Ljubljani, 1 975. S. Ribarić, Dva primjera mikroprocesorskih sustat1a u obradi i raspoznatJanju slika, ElektrotehniČ8r 4, 1 982, str. 97 - 102. W. R. Cyre, G. J. Lipovski, on Generating Mu/tipHers for a Cellular Fast Fourier Transform Processor, IEEE Trans. on Comp., januar 1 972, str. 83 - 87. M. C. P ease, Organization of Large Scale Fourier Processors, J ournal of the ACM, Vol. 1 6, N°. 3, juli 1 969, str. 474 - 482.

9.

SUSTAV ZA RASPOZNAVANJE RUKOM PISANm BROJčANm ZNAKOVA (Prof. dr. Nikola Pavešić, dipl. ing.)

9.1.

UVOD

Za raspoznavanje rukom pisanih brojčanih (numeričkih) znakova možemo upotrijebiti sustav za raspoznavanje koji se zasniva na skupu dvodimenzionalnih prilagođenih filtara. Opisani sustav za raspoznavanje pokazao se pogodnim za automatsko razvrstavanje poštanskih pošiljaka, za razvrstavanje i obradu liječnič­ kih recepa4l, za obradu narudžbi i sl. 9.2.

DVODIMENZIONALNI PRILAGOĐENI m.TRI

Andrews je koncepciju jednodimenzionalnog prilagodenog filtra što ga je predložio Turin (G. L . Turin, 1960), proširio na dvodimenzionalne filtre (H. C . Andrews, 1 970). Osnovna značajka tih filtara je prijenosna funkcija koja u odredenoj točki izlazne funkcije maksimizira omjer izmedu signala i šuma. Ulazna funkcija se sastoji od signala lex, y) i aditivnog šuma b (x, y): gv(x, y) =lex, y) +b (x, y), pri čemu može biti l(x, y) = O za sve x i y. Prijenosna funkcija filtra H (u, v) koji odgovara postavljenim zahtijevima je: F (u, 'll) ex� [ -j (u!; +ll'll)] ( _K H u, v) , B (u, v) gdje je K kompleksna konstanta po volji, F(u, v) konjugirano kompleksna vrijednost spektra signala, B (u, v) spektralna gustoća šuma, a !; i II koordinate točke izlazne funkcije gdje je omjer snage signala i šuma najveći. Spektar signala i spektralna gustoća šuma dani su relacijama: F(u, v) = , [{(x, y)]

B (u, v) = !F [q>b ( T1, T)],

i

gdje je (fl " (Tl' Tz) autokorelacijska funkcija šuma b (x, y), a !F [ . ] označava Fourierovu transformaciju. ,

1 45

9.4. UCENJE SUSTAVA ZA RASPOZNAVANJE

9.3.

SUSTAV ZA RASPOZNAVANJE ZASNOVAN NA DVODIMENZIONALNIM PRn.AGOĐENIM FILTRIMA

Sustav za raspoznavanje uzoraka gradimo pomoću prilagođenih filtara tako

da svakom razredu uzoraka ID/ priredimo prijenosnu funkciju prilagođenog filtra Hj (u, v). Ulaze svih filtara povezujemo paralelno u zajedničku točku koja predsta­

vlja ulaz u sustav raspoznavanja. Izlaze iz prilagođenih filtara dovodimo do jedinice za određivanje maksimalne vrijednosti izlaznih funkcija u točki (�, 11). Blok-shemu tako organiziranog sustava prikazuje slika 9. 1 (N. Pavešić, 1973). Detektor maksimalne vrij ednosti gl1 l � :lI l

gJ21 �.11 1

Uzorak g. l x. y l

Odluka �

QII '�.l1l

gJHI�.l1l Sl. 9.1 Blok-shema sustava za raspoznavanje koji se zasniva na prilagođenim Jiltrima

Postupak razvrstavanja je sljedeći: Za ulaznu funkciju (uzorak) gv ( x, y) potražimo najveći element skupa: Uzorak razvrstavamo u razred IDj ako je %"-ti element skupa najveći. 9.4.

Ul:ENJE SUSTAVA ZA RASPOZNAVANJE

Sustav za raspoznavanje uzoraka gradimo pomoću prilagođenih filtara tako da svakom razredu uzoraka IDj priredimo prijenosnu funkciju prilagođenog filtra Hj (u, v). Signal fi ( x, y) definiramo kao srednju vrijednost uzoraka za učenje koji određuju razred uzoraka IDi' i= 1 , 2, . , M. . .

1 fi ( x, y) = N i

icEN, gt,Cx, y),

gdje je Nj broj uzoraka za učenje i-tog razreda. Vrijednost šuma za pojedine razrede određujemo pomoću razlike između odgovarajućih funkcija gy, i fj:

blc ( x, y) =gt,(x, y) -fj (x, y),

za

k= 1, 2, . . . , N,

9.

146

SUSTAV ZA RASPOZNAVANJE PISANIH BROJCANJH ZNAKOVA

Odgovarajuće spektre F (u, 'V) i B (u, v) određujemo numerički pomoću postupaka koji se temelje na brzoj Fourierovo; transformaciji. Prilikom izvedbe sustava za raspoznavanje izabrali smo K = l + jO i � = 11 = O, tako da je učenje sustava reducirano na određivanje koeficijenta F; (u, v)/B; (u, v), za sv�i razred uzoraka 0);, i= l, 2, . . . , M. �.S. SINTEZA SUSTAVA ZA RASPOZNAVANJE RUKOM PISANIH

BROjĆANIII ZNAKOVA

Za raspoznavanje rukom pisanih brojčanih znakova možemo uspješno upotri­ jebiti sustav za raspoznavanje koji se zasniva na skupu dvodimenzionalnih prilago­ đenih filtara (L. Gyergyek, 1 975). Ulazni podaci su rukom pisane brojke. One su napisane na posebnim obrascima (sl. 9.2) zajedno s velikim slovima. Brojke su napisane u kvadratnim poljima dimenzije 7 x 1 0 mm. Stranice kvadrata su označene svijetloplavim linija­ ma. Udaljenost među kvadratima je 2 mm. Takav obrazac je pogodan i za praktičnu upotrebu.

Izbor veličine matrice Dvodimenzionalni uzorak, općenito, možemo opisati pomoću funkcije s (x, y), gdje je x E [ -X, x] i y E [ Y, VJ; X i Y su konstante. Fourierova transformacija funkcije s ex, y): ' [s ex, y)] = S (u, v) neka je jednaka nuli izvan područja određenog konstantama U i V: S Cu, '0) = 0 za sve u ;: [ - U, ul i 'O M � V, VJ. Funkciju s ex, y) možemo rekonstruirati iz njezinih uzoraka ako joj vrijednosti uzimamo u točkama: n '" , l1l gušce, - , 2U 2 V

(m

m

)

gdje su i n cijeli brojevi između -X i X, odnosno između rekonstruiranu funkciju određuje izraz:

s (x, y) =

� �

L.

m= -X

L.

s(!!!... )

n� - Y

'

�

2U 2 V

2nv

-

n

2V

x-

2nU x -

& -�) � )

sin2n V

( iu) ( ";;)

S in 2n u

.

2

"

-

Y i Y, a

1 47

9.4. S I NTEZA SUSTAVA ZA RASPOZNAVANJE

Primijenimo gornje razmatranje na naš prImJer. Vrijednosti uzoraka (rukom pisanih brojčanih znakova) najprije odabiramo u točkama kartezijskog produkta skupova: i

{O, 2, . . . , 255 }

[0, 2, . . . , 255 } .

Dobiveni podaci opisuju funkcije g�(x, y), gdje j e k = l , 2, . . . , N broj uzoraka u skupu za učenje. Iz skupa {gv (x, y } određujemo diskretnu funkciju g (x, y) koja je karakteristična za sve znakove: ' g (x, y) =

N g� (x, y) "�1 N l

i računamo diskretnu Fourierovu transformaciju funkcije g (x, y):

{

}

1 55 1 55 21tj G (u, v) = L L g (x, y) exp --(xu +yv) . 256 x=O y=O

Potom, određujemo minimalan broj elemenata u skupu 2X odnosno u skupu 2 Y pomoću relacije: N2X= 2Nu odnosno N2y= 2Nv, gdje su Nu odnosno Nv granični brojevi odabiraka, od kojih je dalje G (u, V) � E, E-+O.

Ako uzmemo E=

G (O, O)

1 00

�----

dobivamo:

zato uzimamo matricu uzoraka dimenzija 16

x

1 6.

Izlučivanje suvišne informacije Uređaj za unos slike (TV kamere s odgovarajućim impulsno-sinkronizacij­ skim generatorom) pretvara ulaznu sliku u analogni signal. Taj analogni signal se

Sl. 9.3. Histogram sivih razina ulaznih funkcija gv (x, y)

148

9. SUSTAY ZA RASPOZNAYANJE PISANIH BROJĆANIH ZNAKOYA

pomoću međusklopa i računala pretvara u matricu određenih dimenzija. U sustavu je upotrijebljen A/D pretvarač kojr kvantizira ulazni signal u 256 razina (8 bita). Za opis uzoraka rukom pisanih znakova dovoljne su dvije razine, što nam potvrđuje i histogram svih razina funkcije gy (x, y) (sl. 9.3).

Izbor praga p zavisi od osvijetljenosti slike, vrste i boje pisaljke kojol!l su brojke napisane, te od vrste i boje podloge. Skup diskretnih funkcija {gv (x, y) } binarizirali smo s obzirom na prag p, koji smo odredili tako da se nalazi na minimumu između vrhova histograma. Slika 9.4 prikazuje nekoliko binarnih matrica dimenzija 1 6 x 16 elemenata. � ---------------

--------------------------------------------

xxxxxxx xx xxx xx xxxxxxx xxxxxxxxxx xxx xx xxx xxx xx xxx

x

JJxxxxx xxx xxxxxx xxxxxx xx xxx xxx xxx n xxxx xxx xxxx xxxxxxx xxx xx xxx xxxxxxxx

x x xxx xx xx xxx xxxxxxxx xxx x xx xx x x

xxxxxxx xx xxxx xxxxxx XX xx xxxx xxxx xn xx xxx xxxxx xxxxxxx x xxx xxxxxxxxx x

xx xxx xx xxx xxxx xxxxxxx xxx xxx xxx xxxxxx xx xx xx xxxxxx xxxxxxx xx xx xxxx x

xx xxx . xxx xxxxxx xxx xxx xxx xxx xxxxx

x

x x xxx xx xx xxxxxx xxx xxx xx xxx xxx

xx xxxxx xx xxxx xxxxxx x xx x xx xx

xxx xx xxxx xxxxxxx xxx xxx xxxx x xxxxxxxx

Sl. 9.4. Primjeri binarnih matrica rukom pisanog znaka 5

Određivanje signalne komponente ulazne funkcije Pomoću skupa uzoraka za učenje funkcija:

{gy (x, y)}

određujemo skup statističkih

Sti (x, y) = Pi (gy (x, y) = I I rOi) i y = 0, l , 2, . . . , 1 5, gdje je rOi E {O,

za x = 0, l , 2, . . . , 1 5 l , 2, . . . , 9 } = razred uzoraka a Pi ( . ) funkcija uvjetne vj erovatnoće. Primjer funkcije St (x, y) dan je na slici 9.5 i predstavlja vjerojatnost (u postocima) pojavljivanja jedinice u pojedinim točkama karakteristične binarne matrice.

1 49

9.4. SINTEZA SUSTAVA ZA RASPOZNAVANJE

Skup funkcija relacije:

Stj (x, y)

signala Ji (x, y) pomoću sljedeće

preslikavamo u skup

ako je St/ (X, y» qi Jj (x, y) = l ako je Stj (x, y) � ql' J1 (x, y) = 0 gdje je ql E {qo" ql' q1.' . . . , q9} određen eksperimentalno.

�**..*••****'*.*.************••*.*****************••* *: ! 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 : ! o o o o o o o o o o o o o o o o : i o o o o o o o o o o o o o o o o i i o o o o o o o o o o o o o o o o i ! o o o o o o o o o o o o o o o o i i o o o o o 6 13 20 o o o o o o o o ! ! o o o 13 T3 93100 93 86 66 33 26 o o o o i ! o o 60100100 66 26 26 46 73 93 40 26 o o o i i* o 20100100 53 o o o o 66 93 80 26 o o o :: : o 66100 93 6 o o o o 40 86 93 26 6 e o : i o 60100 86 o o o o o 40 86 86 26 6 o o ! i o 26100 93 20 o o o 13 80100 66 20 o o o ! i o 6 73100 80 40 20 33 93100 86 26 6 o o o e i o o 6 53 80100100100 93 80 20 o o o o o i ! 0 0 0 0 0 6 6 0 0 0 0 0 0 0 0 0 : ! 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 : * * .*.*•••••* •••••••••••••••••••_••••••_*...............

Sl. 9.5. Statistička slika brojke O

Sumna komponenta ulazne funkcije

2, . . . , Nj.

Sum za pojedini numerički znak određujemo kao razliku:

Nj je broj

k = l, b� (x, y) =g�,(x, y) -J, (x, y), elemenata u razredu roj, i 0, I, 2, . . . , 9. =

Sustav za raspoznavanje

Za svaki razred uzoraka gradimo prilagođeni filtar (ukupno njih deset):

1, 2, . . . , 9. Fi { 2X (x, u)} F* (u, y) = L Ji (x, y) } Fi (u, y� F* (u, y) {

H/

Spektre signala

(

) F/ Cu, v)

u, 'o -

_

Bj (u, v)

,

za

i = O,

dobivamo pomoĆU sljedećih relacija: 15

x=o

'0) =

15

exp --j

16

exp

2x j (y, v) . 16

Oba izraza računamo postupkom brze Fourierove transformacije (H. C . Andrews,

1968).

1 50

9. SUSTAY ZA RASPOZNAYANJE PISANIH BROJCANIH ZNAKOYA

Spektrainu gustoću računamo izrazom:

I

B; Cu, v) = � I F [b� (x, y) · w (x, y}w· Ni k= 1 Pojedine funkcije b� (x, y) množili smo Hammingovom funkcijom (H. Gold, 1969) zato da bismo umanjili utjecaj Gibbsova efekta (A. Papoulis, 1962). Pomoću Huangova teorema (T. S. Huang, 1972) možemo Hammingovu funkciju napisati u . ' obliku: W

za

211: � (x, y) = 0,54 +0,46 cos T6v x:Z +y:Z

x i y E {O, I, 2, . . . , I S } . w (x, y) = O

za

x i y � {O, 1, 2,

. . . , I S }.

Izvedba sustava za raspoznavanje rukom pisanih znakova jednostavnija je ako se raspoznavanje odvija u vremenskom prostoru. Izlazne funkcije u točki (0,0) određuje izraz: gl,

za i = 0, I,

(0,0 )

2, . . . , 9.

=

1S IS L L ' - 1 [Fi (u, v)] ·gY (x, y),

y = o y=o

Detektor maksimalne vrijednosti traži najveći element u skupu:

{gl, (0,0), gl, (0,0), za danu ulaznu funkciju maksimalan.

gy

(x, y)

. . . , gl,

(0,0),

. . . , gl,

(O,O)}

i razvrstava je u i-ti razred ako je i-ti element

9.6. REZULTATI RASPOZNAVANJA

Opisani sustav za raspoznavanje ispitali smo na četiri zbirke rukom pisanih brojčanih znakova. Pokus I

Prva zbirka sastoji se od 1 50 brojčanih znakova. Brojke su pisane tušem i tehničkim pismom (sl. 9.6). Sustav za raspoznavanje je cijelu zbirku razvrstao bez pogreške. Pokus II

Druga se zbirka sastoji od 50 brojčanih znakova koji su napisani kemijskom olovkom i "normalnim" pismom (sl. 9. 7). Rezultat raspoznavanja je i sada 100%. Sastavili smo i zbirku od 77 rukom pisanih brojčanih znakova i slova X pisanih kemijskom olovkom. Neki od znakova nisu bili zatvoreni (npr. ° i sl., v. sliku 9.8 ) . I u ovom je slučaju rezultat raspoznavanja bio 100%.

9.6. REZULTATI RASPOZNAVANJA

151

Sl. 9.6. Brojke pisane tu/em i tehničkim pismom

Pokus m

Sastavili smo zbirku od 132 znaka. Zbirka sadrži brojčane znakove O do 9 i slovo X. Znakove smo pisali tako da smo dopustili 20% promjene u visini i širini znakova (sl. 9.9) . Bilo je pogrešno razvrstano 1 1 ,36% znakova.

1 52

9. SUSTAV ZA RASPOZNAVANJE PISANIH BROJCANIH ZNAKOVA

Sl. 9.8. Primjeri iz zbirke 77 rukom pisanih numeričkih znakooa i slooa X

Sl. 9.9. Primjeri iz zbirke 132 rukom pisanih znakooQ i siooQ X

9.7. LITERATURA

1 53

9.7. LITERATURA H. C. Andrews, Computer Techniques in Image Processing, Academic Press, New York, 1970. H. C. Andrews, A High Speed Algorithm for the Computer Generation of Fourier Transforms", IEEE Trans: Computers, Vol. C-17, N°. 4, 373, 1968. B. Gold, C. M. Rader, Digital Processing of Signals, McGraw Hill, New York, 1969. L. Gyergyek (nosilac projekta), ,,Razpoznavanje z roko napisanih numeričkih znakov", Naloga za Sklad Borisa Kidriča, Pogodba što 2-781/149 1-74, Ljubljana, 1975. T. S. Huang, " Two-Dimensional Windows", IEEE Trans. on Audio and Electroacoustics, AU-20, N°. I , str. 88 -90, mart 1972. A. Papoulis, The Fourier Integral and its Applications, str. 30-31, McGraw-HiII, New York, 1969. N. Pavešić, Ma!Jistrsko delo, Fakulteta za elektrotehniko, Univerza v Ljubljani, april 1973. G. L. Turin, "An Introduction to MalChed Filters", IRE Transaction on Information Theory, 3 1 1 329, juni 1960. -

10.

SUSTAV ZA KLASIFIKACIJU OTISAKA PRSTIJU

(Prof. dr. L. Gyergyek, dipl. ing., prof. dr.

N.

Pavešić, dipl. ing.)

10.1. UVOD Otisci prstiju upotrebljavaju se već od početka 20. stoljeća kao vrlo pouzdano sredstvo za identifikaciju osoba (V. Vidie, 1 975). Budući da razvoj tehnologije nije bitno utjecao na same postupke uspoređivanja nepoznatih otisaka prstiju s pozna­ tim, danas se u većini slučajeva identifikacija izvodi ručno. U posljednjih nekoliko godina zahtjevi za automatizacijom postupka identifikacije sve su veći, a uspored­ no s razvojem računalske tehnologije i novim spoznajama s područja raspoznava­ nja uzoraka raste i zanimanje istraživača i istraživačkih ustanova za daktiloskopiju. Od godine 1 966. kada se prvi put susrećemo sa zamisli o automatskoj obradi otisaka prstiju (izvor: Rockwell Int., 1 976) bilo j e uloženo puno napora i sredstava da bi se postupak identifikacije automatizirao, odnosno poluautomatizirao. Iako postoje sličnosti ručnog i automatskog raspoznavanja, ta dva postupka se razlikuju u istoj mjeri kao što se razlikuju sposobnosti čovjeka i stroja (L. Gyergyek, 1 979): Stručnjak za otiske prstiju ima izvanrednu sposobnost kompleksnog promatranja i heurističkog zaključivanja, ali relativno slabu memoriju za mnoge detalje. Velika prednost stroja je u memoriranju velikog broja podataka i u velikoj brzini izvršavanja operacije. Otisci prstiju značajkama:

našli

su

primjenu

u. kriminalistici

zahvaljujući

svojim

nepromjenljivosti : oblik i detalji uzoraka otisaka prstiju ne mijenjaju se cijeloga života,

jednoznačnosti :

praktički ne postoje otiscima prstiju,

razvrstavanje :

već grubi potezi otiska omogućavaju sustavno razvrstavanje uzoraka,

dvije

osobe

s

jednakim

i predstavljaju jedinstvenu metodu identifikacije osoba i na drugim područjima kao što su: obavještajna služba, bankarstvo, trgovina, osiguranje ulaska u objekte i slično (c. W. Swonger, 1 973).

U višegodišnjem radu na području raspoznavanja otisaka prstiju, grupa istraživača iz Laboratorija za sisteme, automatiku i kibernetiku pod vodstvom prof. dr. L. Gyergyeka projektirala je i razvila sustav za automatsko raspoznavanje otisaka prstiju CL. Gyergyek, 1 977, 1 978, 1980). Takav sustav omogućava: •

uspoređivanje nepoznatih otisaka s kartotekom poznatih otisaka prstiju,

1 55

HU. UVOD

•

•

upoređivanje tragat) s kartotekom jednoprsnih otisaka (mono) ili s kartotekom koja sadrži otiske svih deset prstiju (sl. 10. 1 i 1 0.2). Zahtjevi za takvim uspoređivanjem su najčešći, a vrijeme pretraživanja zavisi u prvom redu od kvalitete traga, uspoređivanje otiska s tragovima iz kartoteke tragova.

Iz karakteristika sustava vidimo da na jednoj strani imamo opsežnu zbirku otisaka, a na drugoj strani malu zbirku tragova ili samo jedan trag.

SI. 10.1. Otisak prsta

Sl. 10.2. Trag prsta

Sustav je od samog početka zamišljen kao sustav koji će svoj rad temeljiti na značajkama otisaka prstiju, a ne na potpunoj slici otiska. Razlog takvu izboru jednim je dijelom u tome što je to i osnova za ručno raspoznavanJe, a većim dijelom što potpuna slika uzorka zahtijeva velik kapacitet memorije za pohranjiva­ nje i veliku moć obrade računala. Na primjer, standardne dimenzije slike otiska prstiju su 1 024 x 1 024 ili 512 x 5 1 2 slikovnih elemenata, a svaki je element prikazan u 1 6 (ili više) sivih razina, što predstavlja informaciju veću od 224 bita. Značajke otisaka prstiju za naš sustav raspoznavanja su minucije ili karakteristične točke2) tokovi papilarnih linija. S lika 1 0.3 prikazuje otisak prsta i njegovo i potezi polje minucija i poteza.

///// / / // / //// / I I I I I I I I I I I I I I \.. \.. '. '. / Otisak prs ta

Polje potezQ

- - \.. - \.. \.. \.. \.. \.. I l \.. I I I I I I ///

o o o

0

o

o

o

o

o 0 0

o o

o

°o

o

o

o

dil

o

0

°o

o

o

o o

oO

o

O

O

o o

o o

0 00

� �

�

o

o

o

O

o

o

o oo o o

o 0 00 0 a a 0 0 0 0 00 O o o o

g

Polje mlnu(ijll

Sl. 10.3. Otisak, prsta, polje poteza i polje minUCJ}a

') Trag je otisak skinut s različitih predmeta i obično je slabije kvalitete (sastavljen je od neprekidni h i isprekidanih papilarnih linija). ') Prekidi normalnih tokova linija

-

nepredviden prekid, grananje papi\arnih linija j sl.

1 56

10. SUSTAV ZA KLASIFIKACIJU OTISAKA PRSTIJU

10.2. SUSTAV ZA AUTOMATSKU IDENTIFIKACIJU OTISAKA PRSTIJU

, Slika 1 0.4 prikazuje blok-shemu sustava za automatsku identiflkaciju otisaka prstiju. Na slici je uz blokove označena i količina infonnacija koja se obrađuje u pojedinim razinama sustava za identiflkaciju.

Rnspoređivanje otisnkn

�--.l Pret rniivnnje Oznnkn

nizn

1100 bl!ovn/trag Minucije

Rezultnt identifikllcije

Sl. 10.4. Blok-shema sustava za automatsku identifikaciju otisaka prstiju

Minimalnu sklopovsku podršku sustava (sl. 10.5) za automatsku identiflkaciju otisaka prstiju predstavlja miniračunalo PDP 1 1/34, televizijski sustav zatvorenog tipa (CCTV) i analogno/digitalni međusklop (CVI digitizer) za pretvaranje televi­ zijskog signala u digitalne podatke koji se mogu obrađivati u računalu. Otiske prstiju unosimo u računalo preko televizijske opreme kojom postižemo dimenzije matrice 5 1 2 x 5 1 2 slikovnih elemenata. Ispitivanja su pokazala da je to dovoljno za prikaz svih važnih detalja otiska. Kada je trag vrlo slabe kvalitete, ne pretvaramo ga u digitalni oblik. On se tada projicira na zaslon i operator izdvaja sve minucije. Tako izdvojeni podaci moraju biti kompatibilni s podacima o minucijama koje iz digitalne slike izdvaja računalo (F. Pemuš, 1978). Poslije A/D konverzije dobrog traga ili otiska prsta, dobiva se digitalna matrica uzorka gdje je svaki element matrice kvantiziran u 16 sivih razina. Slika izvornog otiska prsta je u stvari crno-bijela, ali mi želimo pomoću slike sa sivim razinama dobiti binarnu sliku (sliku s dvije razine). Prijelaz na binarnu sliku i uklanjanje smetnj i izvršava se u fazi pretprocesira­ nja (S. Kovačič, 1 976).

157

10.2. SUSTAV ZA AUTOMATSKU IDBNTIFIKACIJU OTISAKA PRSTIJU

-- -

, ---- -

I

I I I I I I I I I

I I I I I

I I I L

_ _ _ __ __

___ _ _

x-v digitizer

Raiuna� J

-- - -- -,

t------!II"-i Svjetleći indikator

i-----...."'l._��=__.J . Konlola operotoral ,------

I I I I I I

L

Kalibracija

-,

- ---

grešaKa

I I I

��skl'1U _ ____ __ __ ---- ---------- 1 mv komera.

I

I I

I

I

I

__

__ __

.JCT�

Sl. 10.5. Minimalna skiopovska podrška za automatsku identifikaciju otisaka prstiju

Pretprocesiranje se izvodi u tri razine: • određivanjem kontrasta u pojedinim dijelovima digitalne slike izdvajamo dijelove koji se slabo vide te razmazane i neotisnute dijelove ( sl. 10.6),

Sl. 10.6. Tamni dijelovi otiska su dijelovi koje ne obradujemo zbog slaba kontrasta

158

10. SUSTAV ZA KLASIFIKACIJU OTISAKA PRSTIJU

dinamičkim pragom koji se mijenja u zavisnosti od pojedinih dijelova slike prelazimo iz slike s više sivih razina u binarnu sliku, • binarna slika otiska se promatra kao dvodimenzionalna struktura linija. Linije se povezuju u njihovu smjeru i prekidaju se veze između dviju susjednih linija (J. P. Riganati, 1977). Pretprocesiranjem smo dobili sliku otiska iz koje želimo izdvojiti minucije i odrediti karakteristične točke. Debljine papilamih linija su različite. Zbog smetnji i šuma razlike su u debljini još očiglednije. Binarni prikaz papilarne linije treba stanjiti tako smanjujemo višak informacije, a ne mijenjamo karakteristike otiska prsta (sl. 10.7a i b). •

aj

::.":':r:!�r;�f !;;�,:?, :il;;l,,:;!:i!i!!i:ii§!ii,;.

IJigil\lli2ironn blnnrnn slika otiska prsta

bJ

,., .•.,

.. , ...•.,"".,•., .. ,.'.

Stanjena binnrna

Sl. 10.7. Stanjivanje binarno prikazane papi/arne linije

Svaki element u stanjenoj slici može imati jednog, dva ili više susjeda. Zato se ispituje najbliža okolina svakog elementa. Pojam susjedstva objašnjava slika 10.8, gdje je prikazano osam susjeda elementa (i, J).

159

10.2. SUSTAV ZA AUTOMATSKU IDENTIFIKACIJU OTISAKA PRSTIJU

Razlikujemo dva tipa karakterističnih točaka, i to po sljedećem pravilu: • krajnja minucija je element koji ima samo jednog susjeda, • element-točka grananja je onaj koji ima tri ili više susjednih elemenata. Tako određujemo koordinate svake karakteristične točke i karakteristične smjero­ ve, odnosno smjerove papilarnih linija u okolini minucija. Slika 10.9 prikazuje polje karakterističnih izdvojenih točaka iz otiska na slici 10.1, a slika 10.1 O prikazuje polje smjerova papi1arnih linija.

« )I

o '"

o

l' --" " ! I I l' l'l' /---" " I' I I ////---" " " ' 1 1////--" " " " /////--" " " " /////1--" " " " // 1 1 11-" " " " , l' l' I 1 1 I l' , , , , , , , ,////11/ " " " " ­ ///I 1/" " " '-­ ,///11-" " '---­ / // //---" " ---­ /// //---" -----------�--------

o I

�

o

•

Sl. 10.9. Polje karakterističnih izdvojenih točaka iz otiska na slici 10.1

Sl. 10.10. Polje smjerova papilarnih linija otiska na slici 10.1

Otisci i tragovi su prikazani koordinatama i smjerovima karakterističnih točaka, zato prije identifikacije treba ukloniti ( L. Gyergyek, 1979): osjetljivost osjetljivost osjetljivost osjetljivost osjetljivost

• • • • •

minucija na pomak, minucija na okretanje, na broj minucija, na lokalna poveeanja, na tip minucija.

Pomak, okretanje, broj i lokalna povećanja prouzrokovana su mehaničkim svojstvima naprave za unos, kvalitetom skidanja traga i promijenjenim uvjetima optičkog sustava TV kamere. Otiske možemo nonnalizirati pomoću matematičkih momenata. Otisak pomaknemo u težište i zavrtimo ga za kut za koji je varijanca minucije u smjeru jedne koordinatne osi jednaka varijanci u smjeru druge koordinatne osi.

] [�

Opisani postupak možemo prikazati ovako:

rx ,, Lvn

=

sq> -sinq>

SIDq>

cosq>

] rLv ] x-mx -my

,

gdje su: 2cov(x,y) q>=arctg---��­ var (x)-var(y) var (x)=E (x _E (X))2,

var(y)=E(y -E (y))2,

cov (x, y) =E ( (x -E (x))(y-E (y)), a

mJe

i

m

y

su koordinate težišta minucija.

160

10. SUSTA V ZA KLASIFIKACIJU OTISAKA PRSTIJU

Ta metoda, međutim, nije dobra za tragove jer na njima otkrivamo samo dio minucija koje se inače vide u otisku. Tragove normaliziramo tako da svaki dio traga gdje je minucija obrađujemo posebno. Trag učvršćujemo u svakoj minuciji i rotiramo za kut koji određuje minuciju najbližu fiksnoj. Broj podataka se poveća­ va, ali su tako normalizirani svi dijelovi važni za identifikaciju (F. Pernuš, 1978; L. Gyergyek, 1978). Algoritam raspoznavanja temelji se na činjenici da uzorak (otisak prsta) prototip - i nepoznati uzorak (trag otiska) čine grupu, tj. da su udaljenosti među njihovim značajkama vrlo male i posljedica su samo šuma i smetnji. Kada računalo uspoređuje dvije normalizirane grupe minucija, ono radi isto što bi radio operator kada bi imao jednu grupu minucija na papiru, a drugu na providnoj foliji CI. P. Rigana.ti, 1977). Foliju bi stavio preko papira. Budući da su obje grupe minucija već normalizirane, foliju ne treba pomicati i vrtjeti u raznim smjerovima. Operator mora zaključiti da li minucije na foliji dobro prekrivaju minucije na papiru. Da bismo izračunali stupanj prekrivanja računamo udaljenost svake minucije na foliji od svake minucije na drugom mediju, a zatim između tih udaljenosti . tražimo minimalne. Grupu najmanjih udaljenosti možemo unijeti u koorinatni sustav XY (sl. 10.12). Ako trag i otisak pripadaju istom prstu, točke u koordinat­ nom sustavu bit će nagomilane oko koordinatnog ishodišta, a u suprotnom slučaju bit će raspršene (V. K. Singh, 1978). U postupku identifikacije računalo ispisuje sve otiske sa stupnjem nagomilavanja koji je dovoljno velik, a te otiske stručnjak daktiloskop još ručno uspoređuje s nepoznatim tragom i bira pripadajući otisak.

.

Sl. JO.ll. Slik4 otiska prsta s označenim centrom i de/tom i papi/arnim linijama izmedu njih

o "o

Sl. JO.12. Mini'ln(l/ne udaijnwsli k4raklerisličnih lolak4 dvaju otisak4 isto; prSla (o) j minimalna udoJjnwst k4rakterističnih točak4 dvaju otisak4 različilih prstiju (x)

U velikim zbirkama otisaka prstiju potrebno je otiske razvrstati u razrede, jer bismo inače svaki nepoznati otisak morali uspoređivati sa cijelom zbirkom podata­ ka. Za automatsko razvrstavanje postoje dvije mogućnosti: l . diskriminantni način odlučivanja, kojemu j e osnova položaj centra ili delte i broj papilarnih linija među njima (sl. 10.11), 2. strukturni, sintaktički način, koji uzima u obzir osnovne strukturne značajke (S. Kovačič, 1978; B. Moayer, K. S. Fu, 1975). U drugom ćemo dijelu ovog poglavlja upoznati strukturno razvrstavanje uzoraka otisaka prstiju.

10.3.

STRUKTURNO RAZVRSTAVANJE UZORAKA OTISAKA PRSTIJU

161

10.3. STRUKTURNO RAZVRSTAVANJE UZORAKA OTISAKA PRSTIJU

Zbirke su otisaka prstiju obično vrlo velike. U njima raspoznavanje postaje, unatoč brzim algorinnima, nedjelotvorno jer se uzorak mora uspoređivati gotovo sa svim uzorcima u zbirci. Postupak se može ubrzati prethodnim razvrstavanjem uzoraka u nekoliko osnovnih grupa. Primjenom hijerarhijskog razvrstavanja u manje podgrupe lakše se nalazi nepoznati uzorak. . Razvrstavanju u grupe pomoću diskriminantnog načina (položaj centra, delte i sl.) nedostatak je u velikoj osjetljivosti na kvalitetu uzorka, a često se vrlo teško određuje položaj centra. Delta, koja se obično nalazi na rubu uzorka, obično je slab�tisnuta (sl. 10.11), a može i izostati (L. Gyergyek, 1979). Metode koje se koriste osnovnim strukturnim karakteristikama uzorka su pouzdanije (H. Moayer, 1975). Na osnovi toka papilarnih linija mogu se definirati neki karakteristični oblici uzorka koji predstavljaju osnovne grupe za razvrstava­ nje. K. S. Fu, H. Moayer i A. Graselli predlažu sintaktički pristup (K. S. Fu, 1977; A. Graselli, 1969) i opis uzorka po smjerovima papilarnih linija (sl. 10.13), što je i polazna točka našeg načina strukturnog razvrstavanja. Ručna klaSifikacija grubo određuje uzorke u lučne, kružne, petljaste i posebne. Oko 60% svih otisaka prstiju su petijasti otisci, 5% su lučni, 30% kružni, a svi ostali oblici su rjeđi. Zbog toga smo se odlučili za sustav razvrstavanja u pet osnovnih grupa (sl. 10.14). Uz to smo predvidjeli i mogućnost daljnjeg hijerarhijskog razvrstavanja na manje pod­ grupe. Strukturno razvrstavanje u uskoj je vezi sa sintaksom jezika. Zbog toga ćemo ponoviti nekoliko osnovnih definicija iz teorije formalnih jezika, koje smo već imali u poglavlju 6. .

Sl. 10.13. Prikaz otiska prsta matricom smjerova koja je dobivena u toku pretprocesiranja. Smjerove odreduju tokovi papilamih linija

Definicija l

Gramatika je četvorka: gdje su: V N konačni skup varijabla ili međuznakova (neterminala), VT p

konačni skup konstanata ili konačnih znakova (terminala), -

konačni skup pravila ili produkcija: Cl-+�; Cl, �E(VTUVN)*'

162

10. SUSTAV ZA KLASIFIKACIJU OTISAKA PRSTIJU

ZBIRKA UZORAKA OTISAKA PRSTIJU

lijevI! petlje

Kružni uzorci

Of!Slle petlje

lufni , u.orcl

Posebni

u.orci

�����

Sl. 10.14. Ostwuni razredi otiska prstiju. U razredu posebnih uzoraka sakupljeni su uzorci oblika koji se rjeđe pojavlj,qu i uni koje ne moiemo sa sigurnoIću razvrstati

s

-

poče tni simbol

S

E

V N'

Definicija l Skup L (G) predstavlja jezik gramatike G ako: L(G)=

x S

{x IXE

� i

S�x}.

L (G) je skup nizova koji su sastavljeni od konstanata (tenninala) što ih možemo dobiti iz početnog simbola u skladu s pravilima iz skupa P. Ako skupu pravila pridružimo skup pripadnih vjerojatnosti stohastičku gramatiku Gs i njen stohastički jezik L (GS).

D,

dobit ćemo

Definicija 3 Stohastička gramatika je četvorka:

gdje vrijedi za V N> , VT> pravila oblika:

S

D) pED. p.

isto kao u definiciji l, a Ps=(P,

Vidimo da niz a smijemo zamijeniti nizom p s vjerojatnosti

konačni je skup

10.3.

163

STRUKTURNO RAZVRSTAVANJE UZORAKA OTISAKA PRSTIJU

Definicija 4 Skup

L(Gs) je stohastički jezik gramatike GS ako:

K

p(x)= •

L Pi'

j= 1

gdje je K broj različitih produkcija S �X. Time svakom nizu V T određujemo vjerojatnost

P (x)

Gs

x konstanata iz sk,upa

s kojom gramatika GS gradi taj niz.

Uzorak

--

Gramatike grupa

Raspodjela

Sl. 10.15. Shematski prikaz postupka strukturnog raZtJTstavanja uzorka

Postupak strukturnog razvrstavanja sadrži sljedeće faze (sl. 10.15): pretprocesiranje, - oblikovanje niza konstanata, - analizu rečenice s izabranom gramatikom. Razyrstavanje se odvija na sljedeći način: • Svakoj grupi, odnosno razredu uzoraka određujemo gramatiku. Gramati­ ka Gj svojim produkcijskim pravilima Pj opisuje svojstva uzoraka u razredu OOj' • Svaki uzorak prikazujemo nizom konstanata. Uzorci iz razreda OOj tvore jezik L (Gj) gramatike Gj• • Imamo toliko gramatika koliko i razreda uzoraka, a svaki je uzorak prikazan odgovarajućim nizom. Uzorak s nizom x ne može biti u razredu OOj ako analizom rečenice1) ne zaključimo da vrijedi:

xEL(Gj), ') Niz" naziva

se

rečenica.

XE V;.

164

10.

SUSTAV ZA KLASIFIKACIJU OTISAKA PRSTIJU

Ovdje je problem razvrstavanja sveden na analizu rečenice, odnosno uzorak se razvrstava u razred IDi ako i samo ako je njegov pripadni niz element jezika generiranog gramatikom Gi• Poznato je više općih ili usmjerenih postupaka za analizu rečenice. Za naš sustav za strukturno razvrstavanje uzoraka izabrali smo algoritam analize naniže s vraćanjem (A. V. Aho, 1972).

[SJ OO

[2J

11

22

[ZJ�[SJ[2] K1

K2

K4

K3

[OC] M1

M2

C1

C2

B M4

� (3

� (4

�[AJQJ� OO

OO

OO

OO

Sl. 10.16. OmO'lmi potezi u uzorcima otiska prstiju i odgovarajuće konstante (terminali)

Zbog složene strukture otisaka prstiju, za njihov opis moramo imati priličan broj karakteristika kojima pridružujemo konstante iz izabranih gramatika. Pokaza­ lo se da svaki uzorak možemo opisati sljedećim osnovnim potezima, odnosno konstantama (sl. 10.16): V T= {OO, l l , 22, 33, Kl, K2, K3, K4, Ml, M2, M3, M4, Cl, C2, C3, C4, DD,

NN},

gdje smo svim potezima karakterističnim za deltu dodijelili istu konstantu DD, a nekarakteristični i dvosmisleni potezi dobivaju oznaku NN. Iz skupa terminala V T gradimo za svaki uzorak vlastiti niz konstanata. Polazna točka su matrice smjerova papilarnih linija veličina 16 x 16, koje određuju osnovne poteze uzorka. Od njih formiramo niz konstanata (sl. 10.17),

/ iL / f "- "- "- "l/ / / f "- "- "- "/ / / "- "- "- "/ / / I I I, ""\ //// 1 I l I / / / / / ...d ..J /// / / / / ......

c::::>

Niz konačnih simbola

-

-

-- ---

Matrica smjera

..J ../ -

MotrlCC1 osnovnih poteza

Niz konačnitI simbola x;22 22 22 22 K1·· ....... 33 33

22 22 22 22 22 22 22 11 11 11 11 11 11 K4 K4 11 Matrica konllČnih simbola

22 K4

Sl. 10.17. Oblikovanje niza konstanata. Prikaz prijelaza s m1ltrice smjera na niz konstanata

10.3.

STRUKTURNO RAZVRSTAVANJE UZORAKA OTISAKA PRSTIJU

165

Gramatikama opisujemo svojstva uzoraka u pripadnim razredima. Važno je koju smo vrstu gramatike izabrali da bi postupak bio djelotvoran. Zbirke otisaka prstiju sadrže vrlo različite oblike uzoraka. Sami uzorci često sadrže i smetnje, tako da je točno razgraničavanje osnovnih oblika teško. Neki oblici uzoraka su češći od drugih. Te se razlike u broju pojavljivanja opažaju već kod oblika uzoraka u istoj osnovnoj grupi. Sve to upućuje na primjenu stohastičkih gramatika koje se koriste vjerojatnošću raspodjele uzoraka i razreda. Poznato je da povećanje izražajne moći jezika zahtijeva opširniju gramatiku. Takvom se gramatikom lakše opisuju svojstva uzoraka, ali se time komplicira analiza rečenice kojom se uzorak razvrstava. Upravo zbog toga veliku pažnju treba posvetiti izboru vrste gramatike. U našem slučaju izabrali smo gramatiku sa sljedećim pravilima (\-. Gyergyek, 1979):

VE(j,

k, I, m, n)

a. E VNU VT

Pravilo prvog oblika ima svojstvo podjele uzorka. Na primjer, pravilo S-->XIX2X3X4 dijeli uzorak S na četiri dijela, pravilo Xl-->Xl l Xl 2 Xl 3 Xl 4 dijeli kvadrat Xl na četiri potkvadrata, itd. Na taj način dijelimo uzorak na trećoj razini dijeljenja na 6 4 kvadrata koji odgovaraju veličini matrice terminalnih značajki uzoraka (sl. 10.18). Zatim upotrebljavamo pravilo drugog oblika, koje određuje terminale na određenim mjestima u uzorku. Na primjer, pravilo Xl l l-->22 određuje u gornjem lijevom kutu slike uzorka konstantu 22 (sl. 10.19). Xlll

O=>C: :G => liIJ S-Xl X2 X3X4

.-----I I I I I

Xl-X11 X12 xn X14

__

I I ----t I I I I ..1 ___ 1I ____ _ I I I I I

Xll-X111 X1ll Xlll Xlll

Sl. 10.18. Prikaz pravila prvo;; oblika. Dijeljenje uzorka na matricu 8 x8 sa tri razine dijeljenja

Xlll

�-i __.J:

I I I I I , ----;----I I I I I

22

�_"

I

J_ ! __� I

.L_t-

I

__l __�-----I I I I I I

X111-22

Sl. 10.19. Prikaz djelovanja pravila drugog oblika

Na taj način moguć je strukturni opis svakog uzorka bez obzira na njegovu osnovnu grupu. Takva gramatika može biti karakteristična gramatika svake stoha­ stičke gramatike bez obzira na podjelu uzoraka u razrede. Znači, stohastičke gramatike pojedinih osnovnih razreda razlikuju se međusobno samo po skupovima D koji određuju vjerojatnosti pravila iz skupa P.

166

10.

SUSTAV ZA KLASIFIKACIJU OTISAKA PRSTIJU

Ako je G;= (VN , V T , P, S) karakteristična gramatika stohastičkih gramatika Gs, imat ćemo:

GS = (V N, VT> PSi' s) ,

PS (P, Dj) i =

,

i

=

l,

. .

stohastička gramatika uzoraka iz razreda . , M; M je broj razreda uzoraka.

co;

Vjerojatnosti u grupama DI ocjenjujemo pomoću skupa uzoraka za učenje. Uzorci iz skupa za učenje tipični su predstavnici svojih razreda. Opišimo postupak ocjenjivanja vjerojatnosti.

l) Izaberemo skup uzoraka za učenje za svaki pojedini razred: •

•

Rt,= {(xp!j)"'" (x",!,,), ... , (XN,, !�)} i=l , .. . , M.

gdje je R"

COl

-

M x" !" Ni -

skup uzoraka za učenje iz razreda co" i-ti razred uzoraka, broj razreda, odnosno grupa, niz konstanata - uzorak iz skupa za učenje, frekvencija pojavljivanja niza x" broj uzoraka za učenje u razredu co;,

2) Karakterističnom gramatikom G = (V N' V T' P, s) analiziramo uzorke iz skupa za učenje za pojedine grupe. Za ocjenu vjerojatnosti u grupi Di analiziramo uzorke iz R". Želimo odrediti ocjene vjerojatnosti Pn pravila

Xr-+a.;

Izračunavamo ih izrazom: n ..

gdje je: Nn (XJ nlO

Pr.

-

=

L

!"Nn�X,,),

x.eRHj,

broj ponavljanja pravila Xr -+al U analizi niza XI Ps�.

167

10.4. LITERATURA

Zelimo odrediti razred uzorka koji je opisan nizom konstanata izvodimo za svaku stohastičku gramatiku i dobivamo vjerojatnosti:

P(x/ Gs);

x.

Analizu

. . , M. koja nam kazuje s kakvom vjerojatnosti gramatika Gs gradi upravo niz x. Uzorak sa nizom x pripada razredu co; za koji je vjerojatnost _P(Gs)P(xIGs) ć naJve a. P(Gs,/ x) P(x) P(x) je vjerojatnost uzorka s nizom x, peGs) je vjerojatnost gramatike Gs" odnosno pripadnog razreda co;. peGs, I x) je vjerojatnost da uzorak s nizom x 2'= 1,

2,

.

•

-

pripada razredu co;. Za simulaciju razvrstavanja imali smo premalo uzoraka da bi ocjena vjerojat­ nosti i bila pouzdana. Zato smo pretpostavili da su svi uzorci kao i svi razredi uzoraka jednako vjerojatni. Iz toga slijedi da je za razvrstavanje bilo dovoljno odrediti najveću vjerojatnosti Razvrstavanje je simulirano na računalu CYBER 72/172. Razvrstali smo sto uzoraka koje smo izabrali tako da se broj pojedinih oblika uzoraka približno podudarao sa stvarnom raspodjelom u velikim zbirkama. Za najkarakterističnije predstavnike osnovnih grupa izabrali smo uzorke iz skupa za učenje. Rezultati simulacije potvrđuju djelotvornost izabrane metode. Uzorci su raspoređivani s točnošću oko 94%, dok je prosječno vrijeme razvrstavanja relativno malo (0,2 s).

P(x) P(Gs)

P(xj Gs).

10.4. UTERATURA V. Vidic: Galton-Henryev ristem klasifikacije otisaka prstiju, Ljubljana, 1975. Rockwell International, Fingerprint Identification Systems, 1976. L. Gyergyek, F. Pernuš, S. Kovačič, N. Pavešić, Automatska identifikacija otisaka prstiju, Elektro­ tehnički vjesnik, Vol. 46, br. 4, august-oktobar, 1979, str. 268 -272. C. W. Swonger, Application of Fingerprint Identification Technology to Criminal Identification and Security Systems, Edinburgh, juli 1973. L. Gyergyek (voditelj projekta), AfJtomatićno razpoznavanje oseh na omovi fJzorcev prstnih odtisov. RaziskovaIna naloga RSS, Ljubljana, septembar 1978. L. Gyergyek (voditelj projekta), Procesiranje dvodimenzionaInih povrlin podatkov, Naloga RSS, Lju­ bljana, septembar 1977. L. Gyergyek (voditelj projekta), Razpoznavanje rokopisov, tipkopisov in prstnih odtisov, Naloga RSS, Ljubljana, novembar 1980. F. Pernuš, Magistrska naloga, Falrulteta za elektrotehniko, Ljubljana, 1978. S. Kovačič, Diplomsko delo, Fakulteta za elektrotehniko, Ljubljana, 1976. J. P. Riganati, An Overoiew of Algorithms Employed in Automated Fingerprint Processing, Proc. 77. Int. Conference on Crime, Countermeaures-Science and Engineering, juli 1977. S. Kovačič, Magistrska naloga, Falrulteta za elektrotehniko, Ljubljana, 1978. B. Moayer, K. S. Fu, A Syntactic Approach to Fingerprint Pattern Recognition, Pattern Recognition, 1975. L. Gyergyek, F. Pernuš, N. Pavešić, Normaliziranje fJzorcev prstnih odtisov, XXII ETAN, Zadar, juni 1978. V. K. Singh, Doktorska disertacija, Fakulteta za elektrotehniko, Ljubljana 1978. L. Gyergyek, S. Kovačič, F. Pemuš, N. Pavešić, Strukturno razvrstavanje uzoraka otisaka prstiju, Elektrotehnički vjesnik, Vol. 46, br. 4, august-oktobar, 1979, str. 273 -277. K. S. Fu, Syntactic Pattern Recognition, Applications, Springer-Verlag, Berlin-Heidelberg -New York, 1977. A. Graselli, On the Automatic Clasrification of Fingerprints, u djelu: Methodologies of Pattern Recognition, ed. S. Watanabe, AP 1969. A. V. Aho, J. D. Ullman, The Theory of Parsing, Translation and Compiling, Vol. I i II, Prentice-Hall Inc., 1972.

ll.

ARHITEKTURA RAČUNALA

(Prof. dr. Slobodan Ribarić, dipl. ing.)

11.1. UVOD Sustav računala može se prikazati hijerarhijskim modelom prema slici 11.1. Najnižu razinu, odnosno samu jezgru modela čini sklopovska oprema ili hardver. Pod tim pojmom razumijevamo sve materijalno od čega je računalo načinjeno: sve mehaničke, magnetne, električne i elektroničke sastavne dijelove i naprave (npr. pogonski motor jedinice diska, magnetna traka, disk, memorija s feritnim jezgrica­ ma, izvori električnog napajanja, tranzistori, sklopovi načinjeni u tehnologiji niskog (SSI - Small Scale Integration)), srednjeg (MSI - Medium Scale Integration) i visokog stupnja (LSI - Large Scale Integration) integracije i sl. U užem smislu pod sklopovskom podrškom razumijevamo elektroničke dijelove računala.

/ /

I I I I I I I I I I I \ \ \ \ \ \ \ \ "-

/

/

/

/�

/---�iW Ils\uirl programi

.

,

,

':l'I

\.

"

,

,

,

Sl. 11.1. Model sustava računala

,

"

"-

11.1. UVOD

169

Sklopovska oprema okružena je sljedećom razinom: dijelom programske opreme (ili softverom) koji se naziva jezgrom operativnog sustava (monitor). Sljedeću višu razinu čine namjenski i uslužni programi (engl. utility program), editori, prevodioci, punioci, programi za otkrivanje pogreški i sl. Pod pojmom programska oprema ili softver razumijevaju se prije spomenute dvije razine. Softver tvore tri glavna dijela: •

namjenski ili aplikacijski programi koji su pisani za rješavanje određenih specifičnih problema, • sustavni programi koji omogućavaju lakši razvoj namjenskih programa, • dokumentacija, kao nužni dio svakog programa, da bi se omogućila efikasna i pravilna upotreba programa u obje razine). Najvišu razinu u modelu računalskog sustava sačinjavaju ljudi-korisnici računala. Oni svoje zadatke upućuju kroz niže razine sklopovskoj podršci, koja te zadatke izvršava uz sudjelovanje operativnog sustava. S razvojem tehnologije visokog stupnja integracije pojavljuje se, uz pojmove hardver i softver, i pojam "firmware'" a odnosi se na programe što ih je obično proizvođač upisao u ispisne memorije - ROM (Read Only Memory). Iako je na prvi pogled granica između razina hardvera i softvera oštra i jasna (hardver se odnosi na komponente, a softver se odnosi na programe), razvoj tehnologije (posebno u prošlom desetljeću) potvrdio je tzv. "dualizam" hardvera i softvera. On se očituje u tome da gotovo sve što ie realizirano u hardveru može biti načinjeno u softveru i obrnuto. Takvim dualizmom izbrisana je oštra granica između hardvera i softvera. Na primjer, prije desetak godina smo prevodioce za više programske jezike smatrali isključivo programskim komponentama. Među­ tim, danas postoje računala koja imaju realizirane takve prevodioce u hardveru (npr. mikroprocesor WD9000 tvrtke Western Digital ima izravnu implementaciju prevodioca za jezik PASCAL). Razvoj tehnologije snažno je utjecao i na pristup izvedbi računalskih sustava. Prije nešto više od deset godina vrijedio je pristup koji se može opisati geslom: "Sve što se dade realiziraj u softveru!". Međutim danas, zahvaljujući niskoj cijeni sklopova, vrijedi pristup: "Sve što se dade realiziraj u hardveru!". Takav pristup omogućio je povećanje faktora brzina/cijena za sustave računala. Izraz "arhitektura sustava računala" nastao je u tvrtki IBM šezdesetih godina. Upotrebljavao se za opisivanje sustava računala serije IBM 360 s pro­ gramske točke gledišta. Tako definirana arhitektura uključivala je opise skupa instrukcija, registara i adresnog prostora na razini zbirnog jezika (asemblera). S vremenom se pojam "arhitektura sustava računala" proširio, tako da P. H. Enslow i I. Flores pod tim pojmom razumijevaju algoritme koji se upotrebljavaju u osnovnim funkcionalnim jedinicama (aritmetičko-logičkoj jedinici, upravljačkoj jedinici, U /1 (ulazno-izlaznoj) jedinici i sL). E. C. Joseph promatra arhitekturu sustava računala, poput arhitekture u modernom građevinarstvu, funkcionalno usmjerenom. Ona je definirana kao način uređenja i struktura sustava s postupcima koji su potrebni za postizanje određenih ciljeva. Ti su ciljevi, obično, povećanje propusnosti (engl. throughput) , prilagod­ ljivosti (engl. flexibiIity), pouzdanosti (engl. reliability), raspoloživosti (engl. availability) i smanjenje cijene sustava. Ostvarivanje tih ciljeva postiže se zahvatima na trima sastavnim područjima arhitekture: hardveru (sklopovska oprema), softveru (programska oprema) i engl. humanware područje koje se bavi problemom odnosa čovjeka i računala te

170

ll. ARHITEKTURA RACUNALA

postupcima i načinom čovjekove primjene sustava računala. Prvo područje arhi­ tekture odnosi se na proučavanje sklopova i uređaja (niža razina) te organizacije i povezivanja sklopovskih komponenata (viša razina) u sustav računala. Te kompo­ nente su sabirnice, memorije, aritmetičko-logičke jedinice i U/I jedinice. Programska oprema odnosi se na upravljačke i namjenske programe koji su potrebni za maksimalno iskorištenje sklopovskih sposobnosti sustava računala. U skladu s hijerarhijskim modelom sustava računala i gornjih pristupa arhitekturi možemo dati sljedeću, dovoljno općenitu, definiciju arhitekture:

Arhitektura sustava računala je vještina oblikovanja računala kako bi se ostvarili zahtjevi korisnika, što se postiže primjenom niza tehnika, postupaka i zahvata u svim hIjerarhijskim razinama sustava računala.

11.2. KLASIFIKACIJA ARHITEKTURE SUSTAVA RAČUNALA Kao rezultat primjene niza zahvata, postupaka i tehnika u svih hijerarhijskim razinama, u skladu s modelom sustava računala, nastao je širok spektar različitih sustava računala koji se razlikuju svojom organizacijom i povezanosti sklopovskih komponenata, organizacijom programske opreme i namjenom - jednom riječi razlikuju se u arhitekturi. Postoje mnogi pristupi klasifikaciji arhitekture sustava računala. Većina tih pristupa upotrebljava globalna svojstva arhitekture i zbog toga vrijede samo unutar ograničenog područja. U ovom ćemo poglavlju opisati klasifikaciju koja će u dovoljnoj mjeri omogućiti razvrstavanje i opis sustava računala primijenjenih u sustavima za raspoznavanje. Jedna je od mogućih klasifikacija arhitekture ona prema promjenjivosti strukture sustava računala. Razvoj LSI tehnologije i pojava višefunkcionalnih LSI modula omogućava nove pristupe u projektiranju i konstrukciji složenih sustava računala. Višefunkcionalni LSI moduli reduciraju broj tipova modula u sustavu raču­ nala i time smanjuju cijenu realizacije. Takvi LSI moduli imaju procesor, U/ I jedinicu i sklop za međumodularne veze, a njihova se funkcija određuje upisiva­ njem funkcijskog koda. Upravo su takvi moduli razlog za klasifikaciju prema promjenjivosti strukture: •

Statička arhitektura - ne dopušta programski upravljane promjene međumodularnih veza. Svaka promjena u konfiguraciji arhitekture zahti­ jeva zahvat u sklop.

•

Rekonfigurabilna arhitektura omogućuje djelomično programski upravljive promjene u međumodularnim vezama (ili jedinicama). , Na primjer, promjene veze procesora s memorijskim modulima, promje­ ne duljine memorijske riječi, promjena strukture klasično realiziranih modula. Dinamička arhitektura omogućuje potpunu rekonfiguraciju sustava po­ moću programskog upravljanja. Na primjer, 64-bitno računalo se rekon­ figura u dva 16-bitna i jedno 32-bitno računalo1).

•

') Kada ne pravimo razliku "računalo".

II

složenosti, ravnopravno upotrebljavamo

uz

izraz "sustav računala" i izraz

11.2.

171

KLASIFIKACIJA ARHITEKTURE SUSTAVA RACUNALA

Jedna je od općenito prihvaćenih klasifikacija arhitekture (M. S. Flynn, 1972) ona koja se temelji na toku instrukcija (slijedi instrukcija koje izvodi procesor) i toku podataka (slijedu podataka povezanih s instrukcijskim tokom),

-f�-

____

_

ftl'MO

"

41�

I

__

SIMQB

I

+

I

'

l l'

t

I I

4.��I-�:�-�OO I

I I

I I

�I ISO

�I- ____

N o, Ins!rukcijski tok

01 Polje Yektom A (prem Flynnul

MIMOW

SIMOW

I

I I

I

SlSOW

SISoB-

� J ,.

---

1

I +

I

+ -- t-

�

I I

MISOW

MISOB

--N

o.l riječ podo.tkn (WI ili semo bit IBI bl Klo.sifikarijo. p remo. Hlindleru

0.,

Sl. 1l.2. Polja vektora A

Tip arhitekture sustava računala opisuje vektor A= (al' a;,)', gdje prva komponenta al opisuje tok instrukcija, a druga komponenta al opisuje tok podataka. Postoje četiri osnovna tipa arhitekture s obzirom na vektor A (sl. 11.1): • Vektor A=(I, l )' opisuje SIDS (Single Instruction Stream Single Data Stream) - jednostruki tok instrukcija - jednostruki tok podataka. Predstavnik tog tipa arhitekture je standardno serijsko računalo s jednim procesorom (uniprocesor), npr. DEC-ov PDP l l ili IBM360. •

Vektor A= (N, 1)' opisuje MISD (Multiple Instruction Stream Single Data Stream) - višestruki tok instrukcija - jednostruki tok podataka. Primjer za taj tip arhitekture je protočno računalo (pipeline computer), npr. IBM 360/91, te računalo ASC tvrtke Texas Instruments.

Vektor A=(I, M)' opisuje SIMD (Single Instruction Stream Multiple Data Stream) - jednostruki tok instrukcija - višestruki tok podataka. Za taj tip računala osnovna je značajka da se jedna instrukcija izvodi istodobno na više podataka. Primjeri takvih sustava računala su ILLlAC IV, MPP (Massively Parallel Processor) i STARAN. • Vektor A= (N, M)' predstavlja MIMD (Multiple Instruction Stream Multiple Data Stream) - višestruki tok instrukcija višestruki tok podataka. Računalo tog tipa arhitekture sastoji se od sustava više procesora u kojem procesori izvode različite instrukcije na različitim podacima. Primjeri takvih sustava računala su multiprocesorski sustav UNIVAC 1108 i sustav C. mmp. Slika 11.3 shematski prikazuje pojedine tipove arhitekture prema Flynnovoj klasifikaciji. L. C. Higbie (1973) uzima kao osnovu Flynnovu klasifikaciju s tim da tip arhitekture SIMD dijeli na sljedeće podtipove: • asocijativno računalo izvodi operacije nad podacima adresirajući ih pomoću oznake ili same vrijednosti (asocijativno) umjesto adresom loka­ cije - mjesta u memoriji. •

172

ll.

ARHITEKTURA RAL:UNALA

Instrukcija

Memorija al SlSO- A= 11,11'

Memorija bl MISO-A= IN,ll'

Programskll memorijll Upravljanje Instrukcija Procesor Procesor Procesor Procesor

Memorija podatIlka cl SIMO -A=ll,MI'

•

Memorijll dl MIMO-A=IN,M)'

Sl. J J.1. Shematski prikaz tipova arhitekture prema F/ynnu

asocijativno matrično (engl. array) računalo - djeluje na dijelovima podataka (bit-slice of data) adresirajući ih asocijativno. Podaci se obradu­ ju pomoću polja vrlo jednostavnih procesnih elemenata. • matrično računalo - obraduje podatke paralelno, poput asocijativnog matričnog računala, ali ih adresira adresom lokacije, a ne oznakom ili vrijednošću. • ortogonalno računalo - sastoji se od dva dijela: asocijativnog matričnog računala i klasičnog računala s jednim procesorom (SISD tip arhitektu': re). Takvo računalo dopušta pristup do dijela riječi (pristup bit-slice) i pristup do cijele riječi. Slika 11.4 prikazuje pojednostavnjenu organizaci­ ju ortogonalnog računala. Neki autori (L. C. Hobbs, 1970) predlažu klasifikaciju arhitekture s obzirom na stupanj paralelizma u upravljačkoj jedinici, procesoru i toku podataka, medu­ tim takva klasifikacija nije primjerena jer su u visokoparalelnim sustavima računala svi ti oblici paralelizma prisutni u velikoj mjeri, što otežava razlučivanje pojedinih tipova arhitekture. W. Hlindler je kvadratu koji se dobiva povezivanjem točaka SIMD-MIMD­ -MISD-SISD (sl. 11.2a) pridodao novu dimenziju - mjeru koja govori o tome da li se tok podataka sastoji od riječi ili samo od jednog bita (sl. 11.2b). U daljnjem razmatranju arhitekture sustava računala upotrijebit ćemo Flyn­ novu klasifikaciju.

173

11.3. ARHITEKTURA TIPA SISD - VON NEUMANNOVO RACUNALO

Konvencionalno računalo SISO arhitekture

Procesni elementi PE, PEz PE3 PE4

•

PE5 · · ·

PEn_, PEn Dio riječi

I bit-slice of dataJ

MAR-Memorijski adresni registar PE -Procesni elementi

Sl. 11.4. Pojednostavnjeni prikaz organizacije ortogonalnog računala

11.3. ARHITEKTURA TIPA SISD­ VON NEUMANNOVO RAČUNALO

Von Neumannovo računalo Jedan od najznačajnijih radova na području arhitekture računala autora A. W. Burksa, H. H. Goldstinea, J. Neumanna (1946) nastao je nekih petnaestak godina prije pojave samog izraza "arhitektura sustava računala". Taj rad predstavlja detaljan opis računala s pohranjivanjem programa (engl. stored-program compu­ ter) i imao je velik utjecaj ne samo na prvu generaciju računala već i. na sve ���� Von Neumannovo računalo je konvencionalno serijsko računalo - tipičan predstavnik SIDS arhitekture. Opišimo ga! Slika 11.5 prikazuje model von Neumannova računala. Računalo se sastoji od četiri funkcionalne jedinice: • aritmetičko-logičkog modula, • upravljačke jedinice, • memorije, • UII jedinice. Na slici 11.5 punom linijom označen je tok instrukcija i podataka, a crtkanom upravljački tok. Aritmetičko-logički modul sastoji se od aritmetičko-logičke jedinice (ALU) i registara koji privremeno pohranjuju podatke koji sudjeluju u operacijama ALU. Aritmetičko-logička jedinica se u von Neumannovu računalu sastojala od zbrajala i sklopa za posmak (adderlshifter)_ Složenije operacije, kao što su množenje i dijeljenje, izvodile su se ponavljanjem operacija zbrajanja i posmaka.

174

II.

Periferni uređcji

Uli Jedinica

L-,----L ,..---L _

ARHITEKTURA RACUNALA

-

-,. I I I

Aritmetičke­ -Iogifko. jedinko.

CPU-centralno. procesorsko. jedinica

l Memorijo. (MemorijskI! jedinico.l

SJ. ll.5. Von Neumannov model računala

legendll: A

o.kull1lllnlllrA

B registor B p progrQIIIsko brojilo I instrukcijski regislQr S memorijski regis tar podntolU1 li memorijski adresni registar

!{

Skt�v i lU generiro.nje uprovljočkih signala.

. ]. ....-+---�

i

�

.�-+------�------------�

Sl. ll.6. Organizacija centralne procesne jedinice

175

l \.3. ARHITEKTURA TIPA SISD - VON NEUMANNOVa RACUNALO

Slika 11.6 prikazuje detaljniju organizaciju centralne procesne jedinice (CPU - Central Processing Unit). Zbrajanje i oduzimanje izvodilo se pomoću zbrajala i registra A (koji se naziva akumulator). U akumulatoru A smještao se jedan operand, a nakon operacije u aklimulatoru A bi se nalazio rezultat. Kao proširenje akumulatora A upotrebljavao se registar B. Množenje, kao što je već spomenuto, izvodilo se zbrajanjem i posmakom i davalo je rezultat dvostruke duljine operanada. Duljina operanada u von Neumannovu računalu bila je 40 bita. Rezultat množenja smještao se u registar A (značajniji bitovi) i registar B (manje značajni bitiovi). Pažnja von Neumanna bila je usmjerena na računalo kao sredstvo koje se primjenjuje u rješavanju numeričkih zadataka. Analizom tadašnjih matematičkih problema (1946. god.) došao je do potrebnog kapaciteta memorije i duljine riječi (kapacitet 4096 riječi duljine 40 bita, tako da je preciznost računanja

2-40�0,9 x 10-12). Upravljačka jedinica daje sve potrebne signale za vremensko vođenje i upravljanje ostalim jedinicama računala. Na taj način ona upravlja radom memorije i aritmetičko-logičke jedinice i usmjerava ih na izvođenje slijednih koraka zadanog algoritma. Upravljačka jedinica pribavlja instrukciju iz memorije, dekodira je, pribavlja potrebne operande iz memorije i izvršava instrukciju. Von Neumann, Goldstine i Burks su razradili postupak prikazivanja algo­ ritma kao sekvencije ill slijeda elementarnih akcija s tim da je svaka takva

akcija izvodljiva za računalo. Računa se tako da upravljačka jedinica pribavlja pojedine korake algoritma u kodiranom obliku i u skladu s njihovim značenjem generira signale pomoću kojih aritmetičko-logička jedinica i memorija izvode potrebne akcije. Algoritam je upisan u memoriji. To je jedna od osnovnih značajki von Neumannova računala - ono pohranjuje podatke i instrukcije u istu memoriju. Računalo s takvom značajkom naziva se računalo s pohranjivanjem programa (engl. stored-program computer). U skupu instrukcija von Neumann je predvidio i posebne instrukcije koje modificiraju adresni dio instrukcije. Na taj način programi mogu preoblikovati svoje instrukcije za vrijeme rada, tako se ista instrukcija može primijeniti na skup različitih podataka. Takvo preoblikovanje instrukcija reduciralo je zahtjeve za većim kapacitetom memorije. Međutim, početkom 6O-ih godina ta je koncepcija preoblikovanja adresnog dijela napuštena kao neprikladna zbog niza nedostataka vezanih uz ispitivanje ispravnosti djelovanja programa. Budući da se instrukcije pohranjuju u istu memoriju kao i podaci (duljina riječi 40 bita), von Neumann i ostali predložili su da se u 4O-bitnu riječ smjeste . dvije instrukcije, svaka sastavljena od 20 bita (sl. l l . 7). Instrukcija 1 Instrukcija 2 r------A.--�v,--A·--� Operacijski ktld 8 billi

I

Adresa 12 bilo

20 bilo

Operacijski ktld 8 bitll

Adreso 12 bilo

20 bilo

Sl. 11.7. Organizacija riječi u von Neuman1WflU ralutuJlu

176

II. ARHITEKTURA RACUNALA

Prvo polje, 8-bitni operacijski kod, odreduje operaciju koja će biti izvedena, a 12-bitna adresa odreduje operand. Osam-bitni kod omogućuje 256 različitih operacija, dok 12-bitna adresa dopušta izravno adresiranje cijele memorije: 21Z 4096. Ovdje je važno napomenuti da je memorija jednodimenzionalna, odnosno da se pojavljuje kao vektor sastavljen od riječi (duljine 40 bita) sa sekvencijainim načinom adresiranja (koncepcija linearnog adresiranja; memorijske lokacije imaju adrese 000, 001, 002, . , FFF (heksadekadno». Tablica 11.1 daje pregled tipičnih instrukcija za von Neumannovo računalo. . .

Tablica 1J.J .

Pregled tipičnih instrukcija za von Neumannovo računalo Operacija

Primjer

Instrukcija Pun (load)

LOADX

A: =-MEMORIJA [X];

Pohrani (store)

STOREY

MEMORIJA [Y]: =A;

Puni negativnu vrijednost (load negative)

LNEGZ

A:

Puni apsolutnu vrijednost (load absolute value)

LABSW

A: =ABS (MEMORIJA [WJ);

Zbroji (add)

ADDX

A: =A+MEMORIJA [X];

Oduzmi (subract)

SUBY

A: =A-MEMORIJA [Y];

Pomnoži (multiply)

MULZ

A: =-A

Podijeli (divide)

DIVW

A: Af MEMORIJA rW];

Granaj (lijevo) Branch (left»

BRAL X

P:X, LIJEVA INSTRUKCIJA;

Granaj (desno) (Branch (right»

BRARY

P:Y, DESNA INSTRUKCIJA;

Granaj akoje pozitivno (Jijevo) (Branch positive (left»

BPOSLX

AKO JE A :;'0, TADA P: =X, LIJEVA INSTRUKCIJA;

Gornja ako je pozitivno (desno) (Branch positive (right»

BPOSRY

AKO JE A:;'O, TADA P:Y, DESNA INSTRUKCIJA;

Pohrani (lijevo) S tore address (left)

STADLX

MEMORIJA [X], LIJEVA ADRESA: =A

Pohrani (desno) Store address (right)

STARY

MEMORIJA [y], DESNA ADRESA: =A

Posmik (shift) lijevo (left)

SHL

A:=2'A;

Posmik desno (right)

SHR

A:=Af2;

.

-MEMORIJA [Z];

x MEMORIjA

[Z];

: = označava tok podataka, pokazuje da je vrijednost na desnoj strani od simbola prenesena prema registru ili memoriji s imenom na lijevoj strani simbola: = MEMORIJA [X] označava nurneričku vrijednost operanda na dokaciji s adresom X O "X" 4096 vrijednost adrese Izraz LIJEVA i DESNA INSTRUKCIJA odnosi se na instrukcijske riječi smještene u 40-bitnoj riječi

11.3.

ARHITEKTURA TIPA SISD

VON NEUMANNOVO RACVNALO

177

Registar P, u centralnoj procesnoj jedinici, ima funkciju programskog brojila i sadrži adresu sljedeće instrukcije koja će biti izvršena. Registar I je instrukcijski registar i sadrži kopiju instrukcije koja se upravo izvodi. Duljina je programskog brojila, registra P, l3 bita, 12 bita za izravno adresiranje memorije i I bit za identifikaciju lijeve ili desne instrukcije u riječi koja je adresirana. Instrukcija se izvodi u dvije faze: PRIBAVI i IZVRŠI. U . fazi PRIBAVI dogada se sljedeće: l. KORAK. Cita se sljedeća instrukcija i prenosi se u registar I. Adresa je instrukcije sadržana u registru P. 2. KORAK. Sadržaj registra P povećava se za jedan i određuje instrukciju koja neposredno slijedi za instrukcijom koja je upravo pročitana. 3. KORAK. Dekodira se 8-bitni operacijski kod. Probuđena je samo ona izlazna linija dekodera kojoj odgovara opera­ cijski kod pribavljene instrukcije. Trećim korakom završava se faza PRIBAVI. Računalo prelazi u fazu IZVRŠI. 4. KORAK. Pobuđuju se slijedovi operacija kojima se izvršava instrukcija. Slije­ dovi tih operacija su, na primjer, prijenos podataka prema memoriji ili od memorije, prijenos podataka prema registrima, prijenos pod­ ataka prema aritmetičko-Iogičkoj jedinici; aktiviranje zbrajala ili sklo­ pa za posmak radi obrade podataka, pr()mjena vrijednosti program­ skog brojila ukoliko se izvodi instrukcija grananja i sl. Izvođenjem 4. KORAKA upravljanje se usmjerava opet na l. KORAK, odnosno fazu PRIBAVI. Taj se ritam prijelaza iz faze PRIBAVI u fazu IZVRŠI, i opet ponovo, provodi sve dok se ne izvrši instrukcija HALT (Stoj). Slika 11.8 prikazuje dijagram prijelaza za von Neumannovo računalo.

Sl. 11.B. Dijagram prijelaza za

von

Neumannuvo računalo

Kako računalo, odnosno upravljačka jedinica, razlikuje instrukciju od podatka? Upotrebom zajedničke memorije za podatke i instrukcije, 40-bitna riječ može biti razlikovana (je li instrukcija ili podatak?) samo prema stanju računala. Ako je računalo u fazi PRIBAVI, tada se riječ iz memorije pribavlja u instrukcijski registar I i tumači kao instrukcija. Ako je računalo u fazi IZVRŠI, riječ koja se pribavlja iz memorije tumači se kao podatak, odnosno operand. Memorija von Neumannova računala sastoji se od 4096 4O-bitnih riječi. Ta je memorija bila izvedena kao katodna cijev za memoriranje (engl. cathoderay storage tube Selectroni»), jer tadađnji razvoj tehnologije nije omogućavao primjenu 163840 bistabila=4096 x 40. Von Neumann, Burks iGoldstine predvi­ dali su vrijeme pristupa od 5 do 50 mikrosekundi, što je za ono vrijeme bilo prilično ambiciozno. ') Upotrijebljeno je 40 Selectrona, svaki kapaciteta 4096 bita.

178

ll. ARHITEKTURA RACUNALA

Riječ se iz memorije pribavlja tako da se 12-bitna adresa smještava u memorijski adresni registar M (sl. 11.6) i generira upravljački signal. titaj (READ). Izabrana se riječ nakon 5 ili 50 !.Ls (vrijeme pristupa) smješta u memorij­ ski registar podataka S. Upis u memoriju izvodi se tako da se 12-bitna adresa smješta u memorijski adresni registar M, a podatak koji se upisuje u memoriju smješta se u memorijski registar podataka S. Upravljačka jedinica generira upravljački signal Piši (WRI­ TE) i podatak se iz registra S upisuje na lokaciju adresiranu sadržajem registra M. Von Neumann, Burks i Goldstine, svjesni da postoje i mnogi problemi koji zahtijevaju kapacitet memorije veći od 2u riječi, razmatraju hijerarhijsku organi­ zaciju memorije gdje se sekundarna memorija (sporija, ali većeg kapaciteta) sastoji od medija koji može pohranjivati veće blokove riječi. Ta se memorija upravlja računalom i predstavlja sastavni dio sustava, ali prilikom rada ne zahtijeva intervenciju operatora. Kao medij za sekundarnu memoriju oni predlažu svjetlo­ sno ili magnetno osjetljiv film ili magnetnu žicu ili vrpcu kojima je pokretanje upravljivo pomoću servomehanizama koji su jntegralni dio upravljanja. Treća razina memorije trebala bi biti tzv. dead storage, odnosno memorija koja nije integralni dio računala. Ona predstavlja proširenje sekundarne memorije i uključuje se u raČQnalo prema potrebi. Od memorije u drugoj razini razlikuje se samo po svojoj raspoloživosti prema računalu. Ulazno--izlazna (UlI) Jedinica omogućuje saobraćanje operatora s ra­ čunalom. Kao grafička izlazna jedinica u von Neumannovu računalu poslužila je cijev Selectron koja je imala svijetlo polje na poziciji gdje je bila upisana binarna vrijednost l i tamno polje koje je odgovaralo O. Upisivanjem uzoraka (nula i jedinica) u memoriju programer je mogao imati grafički prikaz na Selectronu (koji je ujedno služio i za pohranjivanje podataka). Kao UII jedinica upotrebljavao se teleprinter i pomoćna magnetna žičana memo­ rija. Oprema teleprintera bila je tako modificirana da je omogućavala upis informacija s bušene papirne vrpce na magnetnu žicu i obratno. Tok podataka između memorije i U/I jedinice ostvarivao se preko registra A, a upravljao se programom. Budući da je računalo bilo orijentirano prema jednom korisniku (single-user oriented), procesor je upravljao izvođenjem U/I prijenosa. Procesor je čekao na prijenos podataka od U II uređaja ili prema njemu. U svom radu "Preliminary Discussion of the Logical Design of an Electronic Computing Instrument" Neumann, Burks i Goldstine razmatraju i prekrivanje aktivnosti U/I jedinice s aktivnostima procesora, m�đutim zbog sklopovske slože­ nosti (dodatnih registara za privremeno pohranjivanje) i problema sinkronizacije oni tu koncepciju u prvom računalu ne upotrebljavaju. Za gotovo četiri desetljeća von Neumannov model računala je doživio i doživljava promjene i poboljšanja koja su se odrazila na njegovu performansu, ali su još uvijek ostala poboljšanja u implementaciji dotične arhitekture, a ne pobolj­ šanja u arhitekturi (G. J. Myers, 1978). Aritmedčka Jedinica se sredinom pedesetih godina sastojala od sklopova za množenje, brzih zbrajala i sklopova za brzi posmak. Tvrtka IBM 1954. godine uvodi sklopove za aritmetiku s brojevima s pomičnim zarezom (računalo IBM Norc, IBM 704). Sklopovi za dijeljenje su se, kao i danas, rijetko upotrebljavali. Dijeljenje je izvedeno primjenom iterativnog algoritma koji upotrebljava sklopove

11.3, ARHITEKTURA TIPA SISD - VON NEUMANNOVO RACUNALO

179

za množenje, zbrajanje i posmak. Sredinom šezdesetih godina u aritmetičkim se jedinicama vrlo brzih računala (high-speed computer) upotrebljava više istovrsnih aritmetičkih sklopova koji djeluju istodobno (računalo CDC 6600 tvrtka Control Data Corporation, 1964. god.). U isto vrijeme uvodi se i protočna (pipeline) organizacija ALU jedinice. Aritmetičko-logičkom modulu pridodaju se registri opće namjene (general-purpose register, računalo Pegasus tvrtke Ferannti Ltd., 1956. god.). Razvoj LSI (Large Scale Integration) tehnologije u novije vrijeme omogućio je izvedbu ALU-sklopova koji aritmetičke i logičke operacije izvode u vremenu od 50 do 250 ns.

Upravljačka Jedinica od vremena von Neumannova računala pa do danas doživjela je značajne promjene. Razlog je u tome što je ona kritična komponenta arhitekture pa se njene karakteristike izravno i snažno održavaju u cijeni i performansi računala. Promjene su se odnosile na repertoar instrukcija (skup instrukcija), kodiranje instrukcija, način adresiranja i na samu izvedbu upravljačke jedinice. Iako je iz teorije automata poznato (M. L. Minsky, 1967. god.) da računalo koje ima samo dvije instrukcije - DECREMENT AND JUMP I F ZERO (Dekrementiraj i skoči ako je O) i ADD ONE (Pridodaj l ) - može izvršiti svaki zadatak koji danas izvodi bilo koje računalo, velika se pa�nja posve'ćuje skupu instrukcija i odgovoru na pitanje koje operacije moraju biti osnovne (primitive) instrukcije, a koje se operacije mogu izvesti kao niz instrukcija (G. J. Lipovski, K. L. Doty, 1978). Odgovor je na to pitanje u kompromisu između brzine izvođenja, veličine programa i složenosti sklopova. Skup se instrukcija od prvih računala koja su obično imala instrukcije za aritmetiku s brojevima s nepomičnim zarezom, za logičke operacije i operacije posrnaka, te nekoliko osnovnih instrukcija za upravljanje slijedom izvođenja programa, pretvorio u snažniji i fleksibilniji skup koji sadrži instrukcije za rad sa znakovima (npr. instrukcije za razvrstavanje i stapanje) i u poslovnim računalima druge generacije i instrukcije za aritmetiku s brojevima s pomičnim zarezom (računala druge generacije za znanstvenu primjenu). Sredinom šezdesetih godina proizvodači su sjedinili funkcije poslovnog i računala za znanstvenu primjenu u jedno računalo opće namjene. U trećoj generaciji računala dostigao je broj instrukcija dvije stotine zahvalju­ jući padu cijene sklopova. Aritmetičke instrukcije su zauzimale saino manji njihov dio. Nove funkcije zahtijevale su instrukcije za grananje u potprogram, vraćanje iz potprograma, rukovanje zastavicama stanja, pohranjivanje statusa računala, zaštitu memorije i sl. (H. S. Stone, 1975). I U dizajnu skupa instrukcija, što je ključno pitanje arhitekture računala, postoje tri pristupa, odnosno tri škole. Najstariji se pristup temelji na statistici, i to na osnovi iskustva u kodiranju za starije već postojeće računalo. To iskustvo, koje se steklo izvođenjem niza programa i detekcijom najčešće upotrebljavanih instrukcija i operacija, poslužit će kao osnova za uvođenje novih instrukcija. Naime, statistički signiflkantne ma­ kroinstrukcije bit će u novom računalu realizirane kao primitivne (osnovne) instrukcije. Drugi se pristup zasniva na izboru široko rasprostranjenog višeg program­ skog jezika. Nakon toga treba utvrditi koje su to primitivne operacije potrebne za izvođenje toga višeg programskog jezika. Skup instrukcija tada određuju te primitivne operacije.

180

l l . ARHITEKTURA RACUNALA

Treći pristup zahtijeva identifikaciju šire grupe problema koji će se rješavati upotrebom računala i identifikaciju skupa značajki tehnologije koja će se upotre­ bljavati u realizaciji računala. Problemi koji će se rješavati predstavljaju premise, a odluke koje se odnose na arhitekturu računala smatraju se implikacijama. Dokazi daju sve razloge za određenu odluku u konstrukciji računala (a time i odluku o skupu instrukcija). U novije doba, zahvaljujući mikroprogramiranju i razvoju sklopova, stvara se mogućnost da se većina primitivnih operacija u višem programskom jeziku realizira kao instrukcija. Tako se dobivaju računala koja izravno . prihvaćaju programe pisane u višem programskom jeziku (engl. direct-execution architectu­ re) (Y: ehu, 1978).

Već je spomenuto mikroprograrniranje kao način izvedbe upravljačke j edinice. M. V. Wilkes ( 195 1. god.) uveo je mikroprogramiranje kao najbolji način realizaci- . je upravljačke jedinice a prvo računalo s mikroprogramiranom upravljačkom j edinicom bilo je IBM 360 ( 1964. god.). Do tada su upravljačke jedinice bile izvedene primjenom logike razine složenosti logičkih vrata (gate-level logic). To j e imalo svoje prednosti u brzini, ali s u takve upravljačke jedinice predstavljale velike probleme za projektiranje, konstrukciju i realizaciju, a posebno u slučaju potrebnih modifikacija. M. V. Wilkes je predložio da se upravljačka jedinica realizira kao memorij a u kojoj će biti upisan program (mikroprogram) koji će' interpretirati instrukciju računala kao niz osnovnih koraka (mJkrooperacija) koji omogućavaju odnosno aktiviraju određene putove podataka, pobuđu­ ju sklopove u aritmetičko-Iogičkoj j edinici, postavljaju operande i sl. Svaka se instrukcija u mikroprogramiranoj upravljačkoj jedinici sastoji od slijeda pohranjenih mikroinstrukcija (mikroinstrukcije opisuju mikrooperacije). Slika 1 1.9 prikazuje izvornu Wilkesovu shemu mikroprogramirane upravljač­ ke jedinice. Ona se sastoji od dvaju diodnih matrica. Informacija iz instrukcijskog registra (kOd instrukcije) zajedno s dijelom koji odreduje sljedeću adresu mikro­ programa smješta se u adresni registar mikroprogramske memorije. Njegov sa­ držaj je adresa memorijske lokacije, odnosno adresa sljedeće mikrooperacije (zapisane u matrici A) i adresa lokacije u matrici B koja pridonosi određivanju sljedeće adrese mikroprograma. Adresa se u adresnom registru mikroprogramske memorije dekodira i jedan od redaka matrice A i B biva omogućen (izabran). I zabrani redak matrice A (npr. 7) s kombinacijom 1 1 1 10 1 0 (mikroinstrukci;a) upotrebljava se za omo8Ućavanje putova podataka, upravljačkih registara, za aktiviranje određenih skupova u aritmetičko-Iogičkoj jedinici radi izvođenja zahti­ j evane operacije. Izvođenje operacije može postaviti neki bistabil uvjeta i njime određivati izbor dijela koji odlučuje o sljedećoj adresi. Jedna je od bitnih prednosti mikroprogramiranja sustavna metoda realizacije upravljače jedinice i zahvaljujući svojoj homogenoj strukturi to je izrazito pogo­ dan način realizacije upravljačke jedinice uz pomoć LSI komponenata. Mikropro­ gramiranje omogućuje i visoku prilagodljivost, jer korisnik može da mijenja mikroprograme (mJkroprogramabUna upravljačka jedinica), a time i obliku­ je skup instrukcija. Jedno od važnijih poboljšanja upravljačke jedinice je primjena prekidnog sustava (engl. interrupt system; računalo Univac l l 03 tvrtke Univac I ERA 1954. godine). Danas je bez te komponente gotovo nezamisliv rad računala opće namjene ili procesnog računala.

181

11.3. ARHITEKTURA TIPA S[SD - VON NEUMANNOVa RACUNALO

Instrukcija iz registra I

I

Adresa sljedeće mikroinstrukcije

J 0I "

I

AdresOl registar

__--' mikroprogromske L-_ --.--.

--I---t-n-linijo .V

lIemorije

Matrica A 1. - -- ---- - - - l Redolc

ls I

j/ /'1

17

�.-.......... J-+....�q1 .

� 1--+-/ �+t-�-"I--_-+-_-+_-+-_+_-+u-l"----4

vremenskog vođenja

� '- I /

B

�-------- �

1

Dekoder

--:--+Signo!

Mmrica

2" linija

18

_

_�

Jedinici, registrima, upravljačkim sklopovima i sl.

Sl. 11.9. Wilkesova shema mikroprogramirane upravljačke jedinice

Von Neumannovo računalo bilo je jednoadresno računalo budući da je svaka instrukcija imala jedno adresno polje (sl. 1 1.7). Međutim, većina njegovih instrukcija imala je dva ili tri operanda, tako da su neki operandi u jednoadresnoj instrukciji bili implicitni. Na primjer, instrukci ja LOAD Y - Napuni akumulator A sadržajem memorijske lokacije Y, sadrži adresu memorijske lokacije Y (u adresnom polju) - to je izvorišna adresa, a adresa odredišta je implici tna i u ovom slučaju je akumulator A. U drugoj generaciji računala također je bila popularna jednoadresna struktura. Razvoj arhitekture imao je za posljedicu pojavu dvoadresnih i troadresnih računala. Sredinom sedamdesetih godina u arhitekturi je prisutan trend koji omogućuje maksimal nu prilagodljivosti uz minimalno " rasipanje" memorije. Računalo sada ima promjenjiv broj adresnih polja prema broju operanada i načinu adresiranja. Uvođenje indeksnih registara (računalo Datatron, 1953. god. ) i indirektnog načina adresiranja (računalo IBM 709, 1958. god. ) predstavlja značajno povećanje prilagodljivosti adresne strukture (indeksno adresiranje, indirektno adresiranje, kombinacija tih načina adresiranja - preindeksno i postindeksno).

Memorija je doživjela niz promjena zahvaljujući razvoju tehnologije. Pede­ setih godina memorija je bila realizirana pomoću bubnjeva (rotating drum). Početkom šezdesetih godina druga generacija računala primjenjuje memoriju s

Q2

182

lL

ARHITEKTURA RACUNALA

magnetnim jezgricama. Memorije dobivaju karakteristike memorija s izravnim pristupom (engl. Random Access Memory) kojima vrijeme pristupa (engl. access time) ne zavisi od mjesta gdje je podatak pohranjen. Početkom sedamdesetih godina primjenjuju se memorije izvedene u tehnologiji LST - to su memorije s izravnim pristupom, jeftinije, većeg kapaciteta i brže od memorija s magnetnim jezgricama. Magnetni diskovi su, kao primarna memorija, potpuno istisnuti i upotrebljavaju se kao sekundarna memorija. U novije vrijeme primjenjuju se i memorije s magnetnim mjehurićima (engl. bubble memory) koje se mogu upotrebljavati kao memorija u drugoj hijerarhijskoj razini. Osim napretka u tehnologiji doživjela je memorija računala i promjene u organizaciji. Krajem pedesetih godina uvodi se koncepcija virtualne memorije, što omogućava da se memorija sastavljena od triju hijerarhijskih razina pojavljuje prema programu i korisniku kao jedinstvena velika memorija s brzinom gotovo jednakom brzini memorije u prvoj hijerarhijskoj razini (računalo ATLAS, razvije­ no na ManchesterUniversity 1959. god.). Brzina se memorije povećava i uvođenjem brzih priručnih (cache) memo­ riJa (računalo IBM 360, model 85, 1968. god.).

Jedna od značajnih promjena u arhitekturi memorije jest i uvođenje konce- ' pcije multiprogramiranja koja omogućava da se nekoliko nezavisnih programa može odvijati simultano u istom računalu, koristeći se potpuno odvojenim skupom memorijskih lokacija. U Ufl jedinicama još je i danas prisutan problem nejednakosti brzina između procesora (centralne procesne jedinice) i sporih U/I uređaja. U/I uređaji su nekoliko redova veličine sporiji od procesora. U prvim računalima su primje­ njivani meduspremnici (Buffer) za prilagođavanje brzina. Razlika u brzini izmedu procesora i U/I operacija vodila je do ideje o uvođenju obrade dodjeljivanjem vremena (engL timeshared). C. Strachey je još 1959. godine predložio da zbog velike brzine računala (i male brzineU/I operacije, uvjetovane, na kraju krajeva, i brzinom ljudskog procesa mišljenja, percepcije i odgovora) više korisnika "istovre­ meno" saobraća preko više teleprintera s računalom. To izravno saobraćanje korisnika s računalom postiže se, zahvaljujući velikoj brzini računala, preklapa­ njem resursa računala s jednog korisnika na drugog. Svakom se korisniku pri tom čini da računalo radi samo za njega, budući da se njegove naredbe izvršavaju (u usporedbi s našom brzinom percepcije i odgovara) gotovo trenutačno. Primjena prekidnog sustava za upravljanje U/I funkcijama predstavlja znača­ jan napredak u organizaciji U/I sustava (računalo TX-2, Lincoln Labora­ tory, 1957). Druga generacija računala upotrebljava zaU/I operacije funkcionalno nezavisne jedinice kanale podataka (engl. data channel). Daljnji napredak uU/I organizaciji predstavlja primjena perifernih procesora sa svojstvom pohranjivanja programa (Stored program 110 processor) koji poslu­ žuje brzi centralni procesor (na primjer, računalo CDC 6600 tvrtke Control Data Corporation ima deset perifernih procesora). Razvoj tehnologje LSI i pojava mikroprocesora početkom prošlog desetlje­ ća (1971. god.) ostvarila je nove dimenzije u konstrukciji i gradnji digitalnih

11.4.

183

ARHITEKTURA TIPA MISD

sustava i računala. Mikroprocesor je čip (chip) koji odgovara po funkciji i namjeni centralnoj procesorskoj jedinici (CPU) digitalnog računala. Mikroproce­ sor je procesor izveden u tehnologiji visokog stupnja integracije koji služi kao osnova za mikroračunalo (S. Ribarić, 1982. god.). Zahvaljujući svojim karakteristikama: niskoj cijeni, velikoj prilagodljivosti i pouzdanosti, mikroprocesor je izazvao revoluciju u elektronici, računalnim znano­ stima i industrijskim sustavima, te posebno u područjima specijalne namjene kao što su: vojno područje, biomedicina, raspoznavanje uzoraka i sl. Zbog takve važnosti mikroprocesoru je posvećeno posebno poglavlje. 11.4. ARHITEKTURA TIPA MISD Arhitektura ovog tipa opisana je vektorom A (N, l )' koji označava višestruki tok instrukcija i jednostruki tok podataka. Uobičajeno je da se računalo tipa MISD naziva protomo (engl. pipeline) računalo. Osnovna je značajka takva računala da na svaki operand simultano djeluje više instrukcija. "Pipelining" je jedan oblik paralelizma ili konkurentnosti koji je ugrađen u računalo (c. V. Ramamoorthy 1977). On se odnosi na segmentiranje (u različitim razinama) procesa računanja u nekoliko potprocesa koji se izvršavaju dodjeljiva­ njem autonomnim jedinicama (engl. facilities, pipelining segments). Slijedni procesi, npr. izvođenje instrukcije, izvršavaju se tako da se njihove aktivnosti međusobno prekrivaju (engl. overlap) poput aktivnosti na industrijskoj vrpci. Segmentiranje procesa može se načiniti na različitim razinama organizacije računala: na primjer segmentiranje na razini sustava u izvedbi upravljačke jedini­ ce, odnosno jedinice za izvođenje instrukcije IPU (engl. Instruction Processing Unit), ili pak segmentiranje na razini podsustava, npr. segmentiranje pojedinih sklopova u ALU. Prikazat ćemo segmentiranje na razini jedinice IPU, odnosno segmentiranje izvođenja instrukcije. Izvođenja instrukcije zahtijeva fazu njezina pribavljanja, dekodiranja, zatim pribavljanja operanada i konačno fazu izvršenja same operacije (određene instruk­ cijom). U procesoru bez izvedenog segmentiranja jedinice IPU (sl. 11.10) vrijeme potrebno za izvođenje instrukcije jest: =

t;= tpi +td +tl'" + tjz)

gdje je t i vrijeme pribavljanja instrukcije, td vrijeme potrebno za dekodiranje F instrukciJe, tl'" vrijeme pribavljanja operanada, a tiz vrijeme izvršenja instrukcije. Iz�ođerte Instrukcije T; =tpi

•

td +tpo

•

f---+-­

til

Sl. 11.10. Procesor koji nije segmentiran

Ako je proces izvođenja instrukcije rastavljen na četiri potprocesa i ako se izvodi u četiri autonomna modula (sl. ILli), četiri slijedne nezavisne instrukcije mogu biti izvedene paralelno. Slika 11. 12 prikazuje vremenski dijagram izvođenja instrukcije u takvoj "pipeline" jedinici. Iz slike 11. 12 vidimo da u vremenskom intervalu 3 do 4 jedinica IPU obrađuje četiri instrukcije: 1. instrukcija je u fazi

184

ll.

ARHITEKTURA RACUNALA

izvršavanja, 2. instrukcija u postupku pribavljanja operanda, 3. instrukcija u postupku dekodiranja i 4. instrukcija u fazi pribavljanja. Pribavljanje instrukCIje

-+1

Pl

1. modu l

Pribavljanje operanadn

Dekodiranje instrukdje

H

D

2. modul

H

H

PO

l modu l

Sl. 11.11. Protočni procesor, segmentacija

Izvršenje instrukcije

r+

II

4. modul

na

razini jedinice [PU

Modul II

2

PO

2

3

D

3

l,

Pl

4 l,

4

5

6

7

tlvrijemel

Sl. 11.12. Vremenski dijagram iZ'lJodenja instrukcije u "pipeline" [PU jedinici

Vrijeme za izvođenje četiriju instrukcija za protočni procesor iznosi 7, dok bi za "nonpipeline" procesor (sl. 11.10) vrijeme iznosilo 4 x4= 16 vremenskih jedinica. Prikazat ćemo primjer segmentiranja na razini aritmetičke jedinice. Slika lLl3 prikazuje aritmetički sklop za izvođenje operacije zbrajanja brojeva s pomič­ nim zarezom (FLOATING ADD). Postupak zbrajanja može biti rastavljen na sljedeća četiri koraka: Operacija l. 2. 3. 4.

Oduzimanje eksponenata .......................................... . Poravnava nJe ................................................................ Zbrajanje ....................................................................... . Normalizacija ............................................................... .

Vrijeme trajanja 40 ns 70 ns 50 ns 80 ns Ukupno: 240 ns

Operacija zbrajanja brojeva s pomičnim zarezom traje 240 ns. Međutim, rezultate - komponente vektora e D + E - dobivamo svakih 80 ns, što odgovara najdu­ žem vremenu trajanja ošeracije pojedinog koraka, u ovom slučaju normalizacije. =

Slika 11.14 ilustrira pojam protočno "računalo", u stvari opisanu obradu možemo pojednostavnjeno, ali zorno prikazati kao tok podataka koji "teče" kroz "cijev" i prolaskom kroz segmente cijevi doživljava promjene. Zar djelovanje "pipelined" jedinice1) ne podsjeća na protjecanje tekućine kroz cijev? U svakom vremenskom trenutku ll.t rezultat istječe iz otvora cijevi, dok na ulaz pritječu novi podaci. ,) Jedinica koja je segmentirana u "pipeline" module.

11.4.

185

ARHITEKTURA TIPA MISD flOATING AlJI)

AXED HUlTIPlY

·

Mnoie"'e \�.to •••

r-�-------' .

Akumulironje

Rezultat

Rezultat ·Množenje brojeva

sn

rvrstim zaremm

Sl. 11.13. Primjer segmentiranja na razini aritmetičke jedinice (za računalo ASe, tvrtke Texas Instruments)

S obzirom na kofiguraciju i upravljanje, "pipelined" jedinice mogu biti razvrstane u statičke ili dinamičke. U nekim slučajevima "pipelined" jedinica služi samo jednoj funkciji, na primjer "pipeline" zbrajalo ili sklop za množenje u računalu IBM 360/91. Takva je jedinica jednofunkcijska (engl. functional pipe) sa statičkom konfiguracijom. U nekim slučajevima "pipelined" jedinica može poslu­ žiti skup funkcija, svaku od njih s različitom konfiguracijom. Na primjer u računalu TI ASe aritmetička jedinica ima različite konfiguracije za izvođenje

Voda

Protočni segment 1

Protorn! segment 2

Protočni segment 3

Sl. 11.14. Fizički cjevovod kao analogija za protočno računalo

187

11.5, ARHITEKTURA TIPA SIMD

kašnjenje u daljnjem izvođenju već utječe i na cijeli postupak počevši od segmenta (modula) za pribavljanje instrukcije (PI, sl. 11. 11). Problem uvjetnog grananja rješava se različitim zahvatima (lookahead1l mehanizam u računalu ASC, instruk­ cijski stog u računalu STAR-lOO). Slika 11.15 prikazuje pojednostavnjen model protočnog računala pomoću kojeg ćemo ocijeniti propusnost takva sustava. Neka se operacija nad N riječi (N � l ) dade rastaviti u M segmenata, a t. je vrijeme potrebno za izvođenje podoperacije u jednom od segmenata. Neka je To vrijeme potrebno za strukturira­ nje i povezivanje tih M segmenata. Nakon vremena T + M· t. pojavljuje se prvi rezultat. Poslije toga svakih t. I' vremenskih jedinica na Izlaz pristižu novi rezultati. Vrijeme potrebno za obradu N riječi (N � l ) jest:

TN= To +M·t. +(N -l) t.

Efektivno vrijeme obrade jedne riječi je: To +M·t. + (N - l ) t. To= . N

Za N-H/J, efektivno vrijeme obrade jedne riječi teži vremenu t•. Postupak "pipeline" na različitim razinama i u različitim konfiguracijama upotrebljava se u nizu računala: TI, ASC, IBM 360/91, IMB 360/195, CDC 6600 i CDC 7600, CRAY-l (Cray, 1975) i Amdahl 470V/6 (AmdahI, 1975).

II.S. ARHITEKTURA TIPA SIMD

Veći broj procesora koji istovremeno izvode istu instrukciju nad različitim procesoru pridruženim podacima predstavlja osnovnu značajku računala s arhitek­ turom SIMO. Svi procesori ili procesne jedinice:Z) moraju sinkrono i konkurentno izvršavati operacije nad vlastitim skupovima podataka. Razlozi primjene arhitekture SIMO su sljedeći (K. J. Thurber, 1975): a)

Funkcionalni: •

• • • •

b)

Sklopovski: •

• •

c)

složeni problemi obrade (npr. vremenski modeli, hidrodinamički modeli), problemi s visokim stupnjem paralelizma u podacima i operacijama, pouzdanost i postupnost degradacije, važnost sustava, opterećenje u pogledu obrade.

bolje iskorištenje sklopova na problemima s velikim stupnjem paralelnosti, razvoj tehnologije LSI (mikroprocesora), ekonomičnost uvišestručenih struktura.

Programski: •

•

programska oprema je jednostavnija od one za multiprocesorske sustave, lakša konstrukcija velikih sustava.

') Vidi lit. (R M, Keller, 1975). - l) Processor Unit.

188

ll.

ARHITEKTURA RACUNALA

Računala s arhitekturom SIMD mogu se klasificirati u tri velike skupine. Prvu čine paralelna ili matrična (engl. array) računala. Procesne jedinice (procesori ili ćelije) u takvim računalima iskazuju neke topološke međusobne odnose i imaju visok �tupanj međupovezanosti. Druga skupina su skupna (engl. ensemble) računala. To su paralelna računala kojima je stupanj međupovezanosti procesnih jedinica vrlo nizak, ili čak: veze između procesnih jedinica i nema.

Asocijadvna računala su treća skupina. To su takva SIMD računala u kojima procesne jedinice obrađuju podatke koje pribavljaju bez eksplicitnog adresiranja memorijskih lokacija. Podaci se pribavljaju na osnovi nekih svojih karakteristika, odnosno adresiraju se pomoću nekih svojih svojstava (asocijativ­ no), npr. pomnoži međusobno sve A i B za koje vrijedi A> B).

Blok-dijagram tipičnog paralelnog ili matričnog računala prikazuje slika

11.16. Svakom od

N nezavisnih procesnih elemenata pridružena je memorija podataka. Svi procesni elementi su identične strukture i preko prospojne mreže (engl. interconnection network) izmjenjuju međusobno informacije. U našem slučaju prospojna mreža je tipa procesni element -procesni element, međutim može postojati i prospojna mreža tipa memorija -memorija.

Memorija podataka je preko memorijske sabirnice povezana sU/I podsusta­ vom. Potrebno je napomenuti da su u ovom tipu računala memorija podataka j programska memorija izdvojeni. U računalu postoji samo jedna upravljačka jedinica koja upravlja radom N procesnih elemenata. Budući da procesni elementi nemaju svojih programa (izuzev mikroprograme), upravljačka jedinica pribavlja

r-+-

Procesni element 1

......

I'Iemorija podataka 1

......

Programska memorija

t

Središnja upravljačka jedinica

�

Procesni element 2

......

�

Memorija podataka 2

Prospojna mreža

.......

.

�

Procesni element N

�

Memarija podataka N

� Memarijska SIlbirniro

Podaci i instrukcije

Uli SI. 11.16. BkJk dijagram para/e/nog procesora

1l.5.

189

ARHITEKTURA TIPA SIMO

instrukcije iz programske memorije (sl. 11. l6) i prosljeđuje instrukcijski kod svim procesnim elementima. Oni izvršavaju instrukciju paralelno. Neki od procesnih elemenata mogu biti u neaktivnom stanju i propuštati izvođenje zadane instrukcije. Upravljačka jedinica je u stvari i procesor koji ima registre, lokalnu memoriju i aritmetičku jedinicu. Njezina je organizacija takva da joj omogućuje izvođenje upravljačkih instrukcija i instrukcija uvjetnog grananja (ta dva tipa instrukcija procesni elementi ne mogu izvoditi). Paralelno računalo je obično preko upravljač­ ke jedinice vezano s nekim većim računalom opće namjene (domačin ili host). Ako je prospojna mreža vrlo jednostavna ili je nema, takvo paralelno računalo se naziva skupno računalo. Da bismo ilustrirali potencijalne mogućnosti paralelnog ili matričnog računa­ la, razmotrit ćemo operaciju množenja dviju matrica (L. E. Cannon, 1969). Slika 11.17 prikazuje matrični procesor s procesnim elementima od kojih je svaki povezan sa svoja četiri susjeda. Svaki procesni element neka ima četiri registra A, I B, C i T. r--------------- ---------

-

I I I I I I

��----�--+-----��--�

I I I I I I I

L

,

I

I I I I I I I I

I

��----_r----r_�--_,I I I P E I M I I ____ _

__________

-.1

Procesno pol Je

Sl. J J .17. Paralelni procesor sa 4-susje , te X (engl. don't care - nije važno), izlaz središnjeg modula zauzima unaprijed zadanu vrijednost T. Operaciju sklopa NML možeIl).o opisati sa: V41

V31

V15

V1

V61

V71

o

V1 2

V1 1 V81

--+

Tt,

...,

V4k

V3k

5

Vk o

V6k

V7k

Vk

V2k

Vk 1 Vk

--+

k T .

8

Za neke l � � � k za koje se svi elementi susjedstva podudaraju s elementima gornjih maski, središnji element susjedstva zauzima vrijednost P, tako da je � = �min' Ukoliko ne dolazi do podudaranja, vrijednost se središnjeg elementa ne mijenja. Budući da se operacije vrlo često sastoje od upoređivanja samo s jednom maskom, primjenjuje se sekvencijaIni postupak podudaranja (maska za maskom), tako da je potreban samo jedan sklop za podudaranje. U skladu s definiranom operacij om, postupak podudaranja se prekida u trenutku pojave podudaranja. Tada se novo stanje T pohranjuje u registar rezultata. Istovremeno se brojilo susjedstva NCR povećava za jedan. Na kraju izvođenja instrukcije sadržaj se NCR i COR prenosi malom računalu koje je odgovorno za prijenos sljedeće instrukcije u PICAP I. Upravljačka jedinica računala PICAP I izvedena je kao klasična jedinica, s tim da joj je pridodana mikroprogramska memorija kapaciteta osam riječi od 4 1 bita (za pohranjivanje osam maski; k = 8). Računalo PICAP I upotrebljavalo se do sada u većem broju projekata s područja raspoznavanja uzoraka (raspoznavanje otisaka prstiju, ispitivanje tiskanih pločica, detekcija uzročnika malarije) i pokazalo se vrlo djelotvornim. Primjeri programa za fazu pretprocesiranja slike dani su u lit. (B. Kruse, 1 973). Brzina obrade, tzv. pixel-rate, u računalu PICAP I jest 1 06/s. Na osnovi iskustva s PICAP I na Link6ping University su 1 977 - 1 979. godine razvili računalo nove arhitekture, PICAP II , koje ima brzinu oko 40 puta veću od PICAP I. Računalo PICAP II je multiprocesorski sustav u kojem svaki procesor ima specijaliziranu funkciju (sl. 1 3. 30). Neki procesori (B. Kruse, 1 982) rukuju U/I operacijama, dok drugi izvršavaju specifične procesne operacije. Osnovne značajke sustava jesu: • svi procesori imaju brz pristup velikoj memoriji, • memorija za pohranjivanje slika (kapaciteta 4 M bajta) ima linearno uređen adresni prostor i time omogućuje djelotvorno pohranjivanje slika različitih dimenzija, • procesori mogu djelovati istovremeno na različitim slikama - time se postiže velika propustnost sustava, • sustav je modularan i mogu mu se pridodavati novi procesori s novim funkcijama. Procesori se aktiviraju pomoću računala domaćina koji preko upravljačke sabirnice dodjeljuje procesorima parametre (mikrokod).

247

13.3. PARALALNE ARHITEKTURE RACUNALA ZA OBRADU SLIKA

Sabirnica omogućuje priključenje petnaest procesora (npr. ulazni videopro­ cesor, procesor prikazne jedinice, među stupanj za jedinicu diska, procesor za filtriranje i sL). Računalo PICAP II pripada tipu arhitekture MIMO.

Memorijski moduli

...,rL---__r----r'----......

-r--.L..--r------...I.t.

-

Vremenski dijeljena sabirnica

Rafunalo domaćin

SH 77/35

Ter minoll. periferna oprema

Sl. J3.30. Računalo PleAP II

CLIP IV Pod vodstvom M. J. Ouffa na University College, London, razvijen je čitav niz računala za obradu slika. Godine 1 967. razvijeno je računalo UCPR l (M. J. B. Duff, 1 969) za automatsku lokalizaciju sljedova na fotografijama tragova čestica. Računalo je bilo izgrađeno s procesnim poljem dimenzija 20 x 20, a u konstrukciji sustava poštovani su sljedeći principi: • sustav mora imati paralelan unos i paralelnu obradu slike, • komponente sustava moraju biti takve da su pogodne za mikrominij aturizaciju, • sustav neka primjenjuje tehnike i metode koje se osnivaju na iskustvima dobivenim analizom fizioloških sustava. Nakon računala UCPR l slijedilo je računalo CLIP I (Cellular Logic Image Processor) realizirano 1 97 1 . godine u tehnologiji niskog stupanja integracije (SSI TTL), s procesnim poljem dimenzija 1 0 x 1 0. Godine 1 972. konstruirano je računalo CLIP II, s procesnim poljem di­ menzija 16 x 1 2, također realizirano u tehnologiji niskog stupnja integracije (SSI TTL). Računalo CLIP I II, kao prethodnik zadnjeg usavršenog računala, građeno je 1 974. godine u tehnologiji niskog i srednjeg stupnja integracije (i to kombinacija tehnologija TTL i MO S), s procesnim poljem dimenzija 96 x 96 procesnih elemenata.

248

13.

ARHITEKTURA RAĆUNALA ZA OBRADU SLIKA

U razdoblju 1 978. do 1 980. godine konstruirano je zadnje računalo u tom nizu: CLIP IV - računalo u tehnologiji NMOS; s procesnim poljem dimenzija 96 x 96 (L. P. Cordella, 1 978).

r�-�------------------------------ - ----------------------------- -------- --, I I I I I I I I

i

I

j I I I I I I I

i

I I I I I I

iI

I

I

lI

I I

I I I I I I I I I I

ll

r----;====��--IJ-·------ -----J

Ulczni podalQk

Izlazni podatak Omogu{1 B

R Sl. 13.32. Procesni e lement računala CLIP IV

o

Load (tock

1 3.3. PARALALNE ARHITEKTURE RAC:UNALA ZA OBRADU SLIKA

249

Središnji dio računala CLIP IV je polje s 96 x 96 procesora, kojem je pridodan međustupanj (engl. data-shuff1ing system) koji povezuje polje s U/I uređajima (sl. 1 3.3 1 ). Izabrano okno TV slike dimenzija 96 x 96 s vrijednostima prikazanim sa šest bita (64 sive razine), pohranjuje se u šest posrnačnih registara ulazne memorije, i to u bit-memorijskim ravninama. Jedna takva ravnina, pretvorena u kvadrat dimenzija 96 x 96 bitova (9 2 1 6-bitni posrnačni registri) može se posmaknuti u dvodimenzionalno procesno polje. Procesni element se sastoji od bit-serijskog procesora (Boolova procesora) (slika 1 3 . 32). Zajednički instrukcijsko-upravljački vektor (naredba) šalje se svim procesnim elementima koji djeluju potpuno si,nkronizirano (P. E. Danieisson, 98 1 ). Lokalna memorija procesnog elementa sastoji se od 32 jednobitna registra, . dva jednobitna registra opće namjene (A i B) i registra prijenosa (engl. carry register C). Svi su procesori povezani s osam najbližih susjeda. Procesor je izrazito jednostavan, tako da je moć sustava u tome što takvih procesora ima 9 2 1 6. Računalo CLIP IV ma po svojim značajkama arhitekturu tipa SIMD. CLIP IV je djelotvoran u izvođenju lokalnih slikovnih operacija (svođenje na jedinični element, stanjivanje), tako da se sustav može primjenjivati kao računalo za obradu slike u realnom vremenu (M. J. B. Duff, 1 982).

MPP (Massively Parallel Processor) Računal� MPP (Massively Parallel Processor) razvijeno je u NASA Goddard Space Flight Center. Ono je namijenjeno obradi satelitskih snimaka. Osnovne Polje procesnih elemenata IARUI

128-bllni izlazni međusklop

Upruvljalka jedinica

Vanjski upravljafki sklop

12B-bllni ulazni međusklop

I A CUI

Hardcopy jedinica

Jedinica Yrpce

Jedinica diska

JedinIca za uproyljanje podacima i programima ( POMUl

Međusklop za povezivanje s računalom domaćinom

Sl. 13.33. Sustav za obradu slike MPP

Brojčano-sloyni terminal

1 3 . ARHITEKTURA RAl:UNALA ZA OBRADU SLIKA

250

komponente sustava prikazane su na slici 1 3.33. Polje procesnih elemenata (AR U) dimenzija 128 x 1 28 ( 1 6 384 procesna elementa!) upravlja se upravljačkom jedi­ nicom polja (ACU) koja izvršava i skalarne aritmetičke operacije.

N-bitni posmačni registar IN =2, 6.10,14,16,22 , 2 6 , ili 30J

G P

logika

od lij evog

PE

Prema desno m PE

Memorija s izravnim pristupom

Adresa

Sl. 13.34. Bit-senjski procesni element" računala MPP

Jedinica za upravljanje podacima programom (PDMU) upravlja tokom podataka i programima. Ujedno ima pomoćnu funkciju kao što je razvoj programa i dijagnostika. Međusklopovi s pohranjivanjem (staging memories) služe kao međustupnjevi za preuređivanje i slanje podataka između ARU, PDMU i računala domaćina (host computer). Polje procesnih elemenata (PE) sastoji se od 1 6 384 PE organiziranih kao kvadrat dimenzija 1 28 x 1 28. ARU ima i posebno polje od 1 28 x 4 PE koje služi za rekonfiguriranje AR U ako se otkrije neispravnost u nekim PE. Procesni elementi su bit-serijski procesori (sl. 1 3.34). Oni svi djeluju para­ lelno, tako da MPP ima veliku brzinu obrade. Na primjer, MPP izvodi 6 553 MOPS (Million Operations per Second) zbrajanja 8-bitnih cijelih brojeva ili npr. 2 1 6 MOPS množenja 32-bitnih brojeva s pomičnom točkom (K. E. Batcher, 1 980). Svaki PE u polju 1 28 x 1 28 saobraća sa svoja četiri susjeda (topologija jednako kao i u Ungerovu računalu SPAC). Rubni PE mogu imati "otvorene" veze (ne saobraćaju s rubnim PE na suprotnoj strani) ili mogu biti spojeni sa suprotnim rubnim PE. Veze rubnih PE mogu biti izvedene na više načina i ostvaruju se pod programskim upravljanjem. Vrste veza su: • otvorena (nema veze sa suprotnim rubnim PE), • cilindrična (svaki rubni lijevi PE vezan je u svakom redu s rubnim desnim PE),

13.4. LITERATURA

251

•

otvorena spirala (za l � n � 1 27 lijevi PE u redu n spojen je s desnim PE u redu n - 1 ), • zatvorena spirala (kao otvorena spirala samo što je lijevi PE u redu O spojen s desnim PE u redu 1 27). Procesni element upotrebljava bit-serijsku obradu, odnosno obrađuje ope­ rande bit po bit i može rukovati operandima bilo koje duljine s relativno jednostavnim sklopovima. Njihova manja brzina (u usporedbi s bit-paralelnim procesorima) kompenzira se upotrebom više procesnih elemenata koji djeluju paralelno. Svaki procesni element računala MPP (sl. 1 3. 34) sastoji se od šest jednobitnih registara (A, B, C, G, P i S), posmačnog registra s programabilnom duljinom, memorije s izravnim pristupom, potpunog zbrajala, interne sabirnice podataka (D) i kombinacijske logike. Osnovni ciklus izvođenja operacije procesnog ele­ menta je 1 00 ns. Registar P se upotrebljava za logičke operacije i operacije usmjeravanja podataka. Logičke operacije kombiniraj u stanje registra P i stanje na internoj sabirni ci podataka D te novo stanje pohranjuju u registru P. Operacije usmjeravanja posmiču sadržaj P registra u registre P susjednih PE. Potpuno zbrajalo, programabiIni posmačni registar i registri A, B i C upotre­ bljavaju se za bit-serijske aritmetičke operacije. Dva operanda koji sudjeluju u operaciji zbrajanja pribavljaju se bit po bit iz registara A i P, a registar C pohranjuje prijenos. Rezultat se pohranjuje uz pomoć registra B u posmačni registar i/ili u memoriju s izravnim pristupom. Registar G sadrži masku za upravljanje aktivnošću PE. Kapaciteta je memori­ je s izravnim pristupom svakog PE l 024 bita. Procesni elementi djeluju paralelno pod upravljanjem jedinice ACU, koja polju izdaje instrukcije frekvencijom l O MHz. Jedinica ACU je mikroprograma­ bilna i primjenj uje tehniku prekrivanja izvođenja operacija za postizanje veće brzine djelovanja. U ovom poglavlj u opisan je manji broj računala za obradu slika, a potpuniju informaciju i opis brojnih sustava čitatelj može naći u literaturi (P. E. DanieIsson, 1 98 1 ; S, Ribarić, 1 980; K. S. Fu, 1 982. i K. Preston, 1 979). 13.4. LITERATURA J. A. G. Hale, P. Saraga, Digital Image Proce ssing, u djelu: Pattern Recognition, Ideas in Practice, B. G. Batchelor (ed.), Plenum Press, New York, London, 1978, str. 1 77 - 202. W. K. Pratt, Digital Image Processing, J. Wi1ey&Sons, New York, 1978. L. Gyergyek, Statistične metode v teoriji sistemov, teorija o informacijah, Univerza v Ljubljani, Fakulteta za elektrotehniko, Ljubljana, 1971. N. Wiener, Cybernetics, MIT, 1962. R. Allan, Military Electronics, New Architectures Will Meet Systems Needs, Electronic Design, august 1981 , str. 87 -94. D. Casasent, Coherent Optical Computing, Computer, Vol. 1 2, No. I, januar 1979, str. 27 -40. W. Myers, What is Optical Computin Computer, Vol. 1 2, N°. I, januar 1979, str. 29. K. Preston, A Comparison of A nalog and Digital Techniques for Pattern Recognition, Proceedings of the IEEE, Vol. 60, N°. 1 0, oktobar 1972, str. 1 21 6 - 1 23 1 . E . C . Lyons, Digital Image Processing: A n Overview, Computer, Vol. 1 0, N°. 8 , august f977, str. 1 2 -14. S. Ribarić, Paralelizem v razpoznavan.iu dvodimenzionalnih vzorcev in njegov vpliv na m odel procesor ja, Doktorska disertacija, Fakulteta za elektrotehniko, Ljubljana, 1982.

g(

252

13. ARHITEKTURA RA(;UNALA ZA OBRADU SLIKA

S. H. Unger, A Computer Oriented Toward Spatial Problems, Proceedings of the IRE, Vol. 46, oktobar 1958, str. 1 744 - 1 750. S. H. Unger, Pattern Detection and Recognition, Proc. IRE, Vol. 47, )959, str. 1 737 -1 752. D. L. Slotnick, et al., " The SOLOMON Computer", 1962 FJCC, decembar 1962, str. 97 - 1 07. J. Gregory, R. McReynolds, The SOLOMON Computer, IEEE Trans. on Electronic Computers, decembar 1963, str. 744 - 780. B. H. McCormick, The Illinois Pattern Recognition Computer - ILLlAC III, IEEE Trans. on Electronic Computers, decembar 1963, str. 791 - 809. K. Preston, et al., Basics of Cellular Logic with Some Applications in Medical Image Processing, Proc. of the IEEE, Vol. 67, N°. 5, maj 1979, str. 826 - 856. J. H. Holland, Iterative Circuit Computers, Proc. 1960, Western Joint Computer Conf. , str. 259 - 265. K. J. Thurber, Large Scale Computer Architecture, Hayden Book Co., New Jersey, 1976. R. Gonzalez, A Multilayer Iterative Circuit Computer, IEEE Trans. on Computers, decembar 1963, str. 781 - 790. S. I. Kartashev, S. P. Kartashev, Dynamic Architectures: Problems and Solutions, Computer, Vol. I I, N°. 7, juli 1978, str. 26 - 40. J. K. Hawkins, C. J. Munsey, A Parallel Computer Organization and Mechanizations, IEEE Transac­ tion Electronic Computer, juni 1963, str. 251 -262. J. L. Potter, Pattern Processing on STARAN, u djelu: Special Computer Architectures for Pattern Processing, K, K, Fu, T. Ischikawa (ed .." CRC Press, Boca Raton, 1982, str. 88 -101. D. Rohrbacher, J. L . Potter, Image Processing with the Staran Parallel Computer, Computer, Vol. lO, N°. 8, august 1977, str. 54 - 59. K. J. Thurber, L. D. Wald, Associative and Parallel Processors, ACM Computing Surveys, Vol. 7, N°. 4, decembar 1975, str. 215 -255. B. Kruse, A Parallel Picture Processing Machine, IEEE Transactions on Computers, Vol. C-22, N°. 1 2, decembar 1973, str. 1 075 - 1 087. B. Kruse et al., Fron PICAP I to PICAP II, u djelu: Special Computer Architectures for Pattern Processing, K. S. Fu, T. Ichikawa (ed.), CRC Press, Boca Raton, 1982, str. 127 -155. M. J. B. Duff, et al., A Cellular Logic Array for Image Processing, Pattern Recognition, Vol. 5, 1973, str. 229 -247. L. P. Cordella, M. J. B. Duff, S. Leviaidi, Au Analysis of Computational Cost in Image Processing: A Case Study, IEEE Trans. on Computers, Vol. C-27, N°. l O, oktobar 1978, str. 904 -910. M. J. B. Duff, Parallel Computation in Pattern Recognition, u djelu: Methodologies of Pattern Recognition, S. Watanabe (ed.), Academic Press, New York, 1969. P. E. Danielsson, S. Leviaidi, Computer Architectures for Pictoriai Information Systems, Computer, Vol 1 4, N°. l l , novembar 1981, str. 53 - 67. M. J. B. Duff, CLIP 4, u djelu: Special Computer Architectures for Pattern Processing, K. K. Fu, T. Ichikawa (ed.), CRC Pres, Inc, Boca Raton, 1982. K. E. Batcher, Design of a Massively Parallel Processor, IEEE Trans. on Computers, Vol. C-29, N°. 9, septembar 1980, str. 836 - 840. S. Ribarić, Arhitektura računara za obradu dvodim enzionalnih slika, Informatica, Vol. 4, br. 3, 1980, str. 16 -22. K. S. Fu, T. Ichikawa (ed.), Special Computer Architectures for Pattern Processing, CRC Press, Inc. Boca Raton, 1982.

14.

PRIMJENA MIKROPROCESORA U SUSTAVIMA ZA RASPOZNAVANJE UZORAKA

(Prof. dr. S lobodan Ribarić, dipL ing.)

14.1. UVOD Razvoj tehnologije visokog (LSI) i vrlo visokog (VLSI) stupnja integracije u proteklom desetljeću doveo je do stanja koje se opravdano naziva mz'kroprocesorskz' izazov. Mikroprocesor j e predstavljao i predstavljat će izazov velikom broju stručnjaka. Izazov se odražava u nastojanju da se mikroprocesorski čip i kompo­ nente iz njegove široke porodice primjene na različitim područjima ljudske djelatnosti. Mikroprocesor ima raznovrsnu primjenu u upravljačkim i informacij­ skim uređajima ugrađuje se u tisuće i tisuće uređaja: u komunikacijske uređaje, u sustave za prikupljanj e i obradu podataka, sustave za daljinsko upravljanje, inteligentne terminale, sustave za upravljanje prometom, telefonske centrale, sustave za upravljanje vatrom na avionima, u uređaje za obradu tekstova, u upravljačke periferne jedinice, u upravljačke sklopove stimulatora oštećenih ekstre­ miteta, u opremu za ispitivanje uređaja i drugdje (S. Ribarić, 1 983). Jedno od područja izazova jesu sustavi za raspoznavanje uzoraka. Mikroprocesori sa svojom niskom cij enom i širokim spektrom performansi (od kalkulatorski orijentiranih mikroprocesora, mikroprocesora orijentiranih za primjenu u upravljanju, preko mikroprocesora opće namjene, pa sve do 16 i 32bitnih mikroprocesora koji svojim značajkama i razinom arhitekture premašuj u karakteristike centralnih procesnih jedinica velikih računala (tabL 1 4. 1 ) omoguća­ vaju realizaciju složenih procesorskih i multiprocesorskih sustava vrlo visokih performansi koje se zahtijevaju na području umjetne inteligencije i raspoznavanja uzoraka. Za ilustraciju moći 32-bitnih mikroprocesora u tabL 1 4.2 prikazane su neke značajke i sposobnosti četiriju novijih mikroprocesora: i APX 432, N S 1 6 032, Bellmac 32 A i HP 32 (A. Gupta, 1 983). U ovom poglavlju prikazat ćemo primjere primjene mikroprocesora i drugih komponenata visokog stupnja in­ tegracije u sustavima za obradu i raspoznavanje slika, raspoznavanje govora i u sustavima za strojni vid.

14.2. OBRADA SLIKE PRIMJENOM SUSTAVA MIKRORACUNALA Razvoj tehnologije LSI omogućio j e primjenu sustava mikroračunala kao osnove za izgradnju malih sustava za digitalnu obradu slike, uz relativno nisku cijenu (450 do 800 tisuća dinara; cijena 1 982. god.).

14. PRIMJENA MIKROPROCESORA U SUSTAVIMA ZA RASPOZNAVANJE UZORAKA

254 Tablica 14. 1 .

Prikaz dijela mikroprocesorskog spektra

� Manje od miniračunala

'" -"

"5h o ....:l

MC 1 4 500

.... o

'tU "3

�

�

. - ;g

.s ", "' "� :=-"> t) '" o) .... 0. 0. (/) ;:1

Više od miniraČUllala

Miniračunala

oo

�

cl

�

.... o)

.Šo �

'" > o

Z

l'

+'

'7

�

'-' �

cl

�

'-' -

cl

�

o ..... M

o ..... M

o o \cl M

\cl M

::E ::E

ll:)

>-
-


-:;;

::> 'CI OI lE

2'3 ;;< '" f '" vl

110 V

llapajnnje

14.33. Robotsko-vizualni sustav na bazi mikroprocesora (tvrtka Optical Recognition Systems)

286

14. PRIMJENA MIKROPROCESORA U SUSTAVIMA ZA RASPOZNAVANJE UZORAKA

t-----�

Međuslupanj prema robalu

Mikrop'rocesorski razvojni suslav

Sl. 14.34. Visoko prilagodljivi sustav SAM

Laboratorijska oprema Istraživanja u području strojnog vida predstavljaju djelatnost mnogih istraživačkih institucija i tvrtki kao što su: Artificial I ntelligence Laboratory na M. L T. (P. H. Winston), University of Illinois (D. Waltz), Electro-technical Laboratory, Tokyo (Y. Shirai), O saka University (M. Yachida), Australian Natio­ nal University (R. A. Jarvis), grupa iz Gorkog (O. Baškirov, S . Salmin, B . (:udinovič), Novosibirska (R. Baglai) i Lenjingrada (V. Haričev), SRI Internatio­ nal, Hitachi Central Research Laboratory, Mitsubishi Electric, Optical Recogni­ tion Systems Inc. i drugi. Zbog širokog područja primjene sustava za strojni vid (industrijski robotski sustavi, sustavi za i straživanje morskog dna i svemira, sustavi za pomoć hendikepiranim osobama) i zbog intenzivnih teorijskih istraživanja (psihologija strojnog videnja, razvoj algoritma za pojedine faze obrade) laboratorijska oprema mora omogućiti širok spektar eksperimenata bez značajnije reorganizacije potreb­ nih funkcionalnih komponenata. Slika 1 4. 35 prikazuje pet osnovnih funkcionalnih komponenata laboratorijske opreme za strojni vid i robotiku. Primjena l6-bitnih i 32-bitnih mikroračuna­ la i drugih sklopova u tehnologiji L S I omogućila je konfiguriranje laboratorij-

14.5.

287

OSNOVNE KOMPONENTE SUSTAVA ZA STROJNI VID

skog sustava za istraživanje, razvoj i ispitivanje uz umjerenu cijenu (R. A. Jarvis, 1 982; sl. 1 4.36) . Središnju obradu podržavaju dva računala domaćina (host com­ puter): miniračunala ili 1 6-bitna, odnosno 32-bitna mikroračunala. Računalo domaćin l ima funkciju središnjeg upravljača sustavom, a računalo domaćina 2 podržava sustav za pohranj ivanje slika i rukovanj e datotekama. Dva su računala povezana tipom veza memorij a-memorija. Brzina izmjene podataka je veća od 50 K riječi u sekundi. Oba računala domaćina imaju diskovne jedinice (ili floppy disk) većeg kapaciteta. Podsustav za prikupljanje slike sastoji se od kvalitetne studijske TV kamere u boji, upravljačkog sklopa kamere i sustava za unos slike. Takav sustav unosi sliku dimenzija 256 x 256 slikovnih elemenata i 4 bita rezoluci­ j e ( 1 6 razina) za svaku osnovnu boju. Jedinka za unos, prikupljanje i pohranjivanje slike

Jedinica za prikupljanje i pohran j ivanje podataka

Sl.

14.35. Osnovne funkcionalne

Robotski manipulator

komponente laboratorijske opreme za stroj1W viđenje i robotiku

Grafički TV monitor u boji svojim upravlj ačkim sklopom omogućava kvali­ tetnu rekonstrukciju slike u boji, a ima i ulogu pomoćne memorije za računalo domaćin l (na primjer, 96 K bajta). Prijenos podataka i upravljanje s oba podsu­ stava obavlja se tehnikom izravnog pristupa memoriji (DMA). kobotskim manipulatorom treće generacije Unimate 250 upravlja mikrora­ čunalo (na primjer LSI- l l , tvrtka DEC) koje koordinira radom šest mikroproce­ sora kojima j e povjereno upravljanje za šest vrsta kretanja (sl. 1 4. 37). Mikroraču­ nalo kao upravljački sklop manipulatora saobraća s računalom domaćinom preko standardnog međustupnja RS-232. Programska podrška zavisi od tipa opreme. Na primjer, za upravljanje manipulatorom može se upotrebljavati sustav Val kojemu je osnova ROM. Mikroračunalskom sustavu za unos slike obično služi standardni industrijski operacijski sustav CP/M. Programsku opremu za računala domaćine čini operacij­ ski sustav (za miniračunalo ili mikroračunalo) sa zbirnim j ezikom Casembler) i s višim programskim jezicima Pascal, Fortran, Ada i drugima. Na primjer, u laboratoriju Australian National University CR. A. Jarvis, 1982) sustav za strojni vid se zasniva na jedinici Genisco color ' image display, koja ima svoje mikroračunalo, i operacijskom sustavu š to ga puni računalo domaćin (tzv. "gra­ phic files"). Kao računalo domaćin upotrebljava se miniračunalo Nova, a mikrora­ čunalski sustav za unos slike zasnovan je na mikroprocesoru Z-80 i ima operacijski sustav CP/M. Uslužni programi podržavaju veze između podsustava Nova/Nova, Nova/Genisco i Nova/Z-80. Saobraćanje NovaJVal (upravljački sklop manipulato­ ra, računalo LSI- I l ) ostvaruj e se standardnim kodom ASC I I preko serijske veze RS-232.

288

[ 4. PRIMJENA MIKROPROCESORA U SUSTAVIMA ZA RASPOZNAVANJE UZORAKA

Računalo domotin 2 Imlnlnočuno.!o ill 16 il i 32-bllno mlkroračunalol

Ponolelni međustupanj Hlknoračunolo

Inpr. ZOO ili 808SJ

lill novijaeki sklop kamere

TV monitor

u boji

Upnovljanje fokusom i zoomom

Sl. 14.36. Primjer konfiguraCIje laboratorijske opreme za strojno viđenje i r obotiku

I

�

Sl. 14.37. Vrste kretanja manipulatora Unimatc 250

14.6. LITERATURA

289

14.6. LITERATURA S. Ribarić, Deset mikroprocesora, Elektrotehniča!, br. 2, 1983, str. 53 - 59. A. Gupta, H. D. Toong, An Architectural Comparison of 32-bit Microprocessors, IEEE Micro, februar 1983, str. 9 -22. S. Ribarić, Obrada slika primjenom sustava mikroračunala, Cavtat, IV međunarodni simpozij , "Kompjuter na sveučiiHtu", maj 1982. S. Ribarić, Arhitektura mikroprocesora, Tehnička knjiga, Zagreb, 1982. S. Ribarić, Ocjena stupnja paralelnosti u algoritmima za pretprocesiranj"e slika, ETAN, Priština 1980. I. Renyi, LSI Technology for Digital Image Processing, Euromicro Journal 6, 1980, str. 232 - 236. R. Allan, Military Electronics, New Architectures Will Meet Systems Needs, Electronic Design, august 198 1, str. 86 -94. ... .. Real Time Video Digitizer{ Gray Level, Graphics Monitor Interface, Environmental Interfaces, 1978. C. Y. Suen et aL, Automatic Recognition of Handprinted Characters - The State of the Art, Proceedings of the IEEE, VoL 68, N°. 4, april 1980, str. 469 -487. L. D. Hannon, Automatic Recognition of Print and Script, Proceedings of the IEEE, VoL 60, N°. 1 0, oktobar 1972, str. 1 1 65 - 1 1 76. N. PaveŠić, Avtomatično razpoznavanje dvodimenzionalnih tekstov, u djelu: Problemi semantike, sintakse in obravnove tekstov, IJS Poročilo P-277, Ljubljana 1972. J. T. Tou, R C. Gonzalez, Pattern Recognition Principles Addison-Wesley Pub. Co., Massachusetts, 1974. W. W. Bledsoe, L Browning, Pattern Recognition and Reading by Machine, u djelu: Pattern Recognition, Theory, Experiment, Computer Simulations, and Dinamic Models, L. Uhr (Ed.), J. Wiley, Inc., New York, 1966, str. 3 0 1 - 3 1 6. S. Ribarić, N. Pavešić, Mikroprocesorski klasifikator numeričkih znakova s mreiom memorijskih kompo­ nenti L S I , Infonnatica, br. 2{3, Ljubljana, 1983, str. 1 62 - 1 67. L Aleksander, Pattern Recognition with Networks of Memory Elements, u djelu: Pattern Recognition, Ideas in Practice, B. B. Batchelor (ed.), Plenum Press, New York, 1978, str. 43 -64. L. Gyergyek (nosilac zadatka), Raspoznavanje z roko napisanih numeričkih znakov, Naloga za sklad B . Kidriča, br. 2-78 l { 1 49 1-74,Ljubljana, 1975. W. A. Ainsworth, P. D. Green, Current Problems in Automatic Speech Recognition, u djelu: Pattern Recognition, Ideas in Practice, B. G. Batchelor (ed.), Plenum Press, New York, 1978, str. 365 - 398. Threshold Technology Inc., VIP- 1 00 Automatic Speech Recognition System, 1978. F. Koperda, Voice Recognition, u djelu: Microprocessor Application Handbook, str. 14. 1 - 14. 1 1 . L. Gyergyek, Statističke metode v teoriji sistenwv, teorija o informacijah, Univerza v Ljubljani, Fakulteta za elektrotehniko, Ljubljana, 1971 . D . Ridyard, Speak to Your Computer, Elektor, novembar 198 1, str. I I -45 I I - 49. ..... Computing Power Boom Speech Quality, Staff Report, Digital Design, mai 1982, str. 44 - 50. R. D. Fennell, V. R Lesser, Parallelism in Arti/icial Intelligence Problem Solving, A Case Study of Hearsay II lEE E Trans. on Computers, VoL C-26, N°. 2, februar 1977, str. 98 1 1 1 . H. G. Barrow, J. M. Tenenbaum, Computational Vision, Proceedings of the IEEE, Vol. 69, N°. 69, maj 1981 , str. 572 - 579. W. K. Pratt, Digital Image Processing, J. Wiley Sons, New York, 1978. L. G. Roberts, Machine Perception of Three-Dimensional Solids, Optical and Electro-optical Information Processing, J. T. Tippett et al. (editor), MIT Press, 1965. M. Minsky, A Framework for Representing Knowledge, Massachusetts Institute of Technology, Cambrid­ ge, 1 974. P. H. Winston, The Psychology of Computer Vision, McGraw-Hil1, New York, 1975. R. P. Kruger, W. B. Thompson, A Technical and Economic Assessment of Computer Vision for Industrial Inspection and Robotic Assembly, Proceeding of the I EEE, Vol. 69, N°. 12, decembar 198 1 , str. 1 524 - 1 538. R. Allan, Industrial Electronics, Electronic Design, Vol. 30, N°. 1 , januar, 1982, str. 91 - 1 1 8. G. J. Agin, Computer Vision Systems for Industrial Inspection and Assembly, Computer, Vol. 1 3, N0. 5, maj 1980, str. I I -20. R. A. Jarvis, A Computer Vision and Robotics Laboratory, Computer, VoL 1 5, N0. 6, juni 1982, str. 9 - 23.

15.

MODEL PROCESORA ZA OBRADU I RASPOZNAVANJE SLIKA (Prof. dr. Slobodan Ribarić, dipl. ing.)

1 5. 1 . UVOD

U posljednjem desetljeću zanimanje za područje raspoznavanja uzoraka u stalnom j e porastu. Razvoj tehnologija VSLI i rad na rješavanju problema prijateljskog saobraćanja čovjeka i stroja (u okviru projekta sljedeće generacije računala) snažno je pospješio istraživanja i primjenu novih metoda u području raspoznavanja uzoraka. Raspoznavanje slika nesumnjivo je jedno od najvažnijih područja raspoznava­ nja uzoraka. Područje primjene digitalne obrade i raspoznavanja slika vrlo je široko od analize sljedova čestica na fotografskoj ploči, raspoznavanja brojčano­ slovnih znakova, automatske interpretacije snimaka u medicini, analize satelitskih snimaka u meteorologiji, raspoznavanja otisaka prstiju u kriminalistici, pa sve do analize snimaka izviđanja, identifikacije ciljeva i detekcije letjelica u vojnoj primje­ ni. U velikom broju primjena problemi s područja obrade i raspoznavanja slika zahtijevaju vrlo složenu obradu i predstavljaju velik računski problem, tako da zahtijevaju vrlo visoku performansu računala. Samo za ilustraciju ocijenimo potrebnu performansu računala (izraženu u M IPS1) milijunima instrukcija u sekundi) za obradu slike u realnom vremenu: Neka je slika dimenzija 1 024 x 1 024 slikovna elementa, a vrijednost ' slikovnog elementa neka je kvantizirana u 256 razina (8 bita x 3 za boju). U ovom primjeru pod obradom slike u realnom vremenu razumijevamo obradu jedne slike u vremenu kraćem od 0,04 sekunde, odnosno obradu 25 slika u sekundi; vrijeme 0,04 s odgovara vremenu obnavljanja slike na zaslonu. Tipična obrada slike, na primjer filtriranje uz pomoć maske dimenzija 3 x 3 slikovna elementa ili ortogonalna transformacija slike, zahtijeva od deset do stotinu instrukcija po slikovnom elementu (J. A. G. Hale, 1 978). Potrebna performansa računala (izražena u M IPS) jest: (broj slikovnih elemenata) x (broj instrukcija za slikovni element) x (broj slika u sekundi) x 1 0- 6. Za naš slučaj potrebna performansa iznosi: ( 1 024 x 1 024 slikovna elemen­ ta) x ( 1 O do 1 00 instrukcija za s likovni element) x (25 slika u sekundi) x 1 0 - 6, odnosno 262 M I PS do 2620 MIPS. Tako visoka performansa predstavlja za konvencionalna računala koja se temelje na sekvencijainom von Neumannovu modelu nedostižnu vrijednost. Na primjer, velika računala kao što su I B M 308 1 (iz tzv. vala H), Amdalh 5860 ili ') MIPS

Million Instructions Per Second.

1 5 . 1 . UVOD

29 1

Hitachi A S/9000 DPC imaiu performansu u granicama od 14 do 1 6 MIPS, a superračunala (vektorski ili multiprocesorski sustavi) poput CRAY X-MP ili CDC 205 postižu performanse između 400 . . . 630 MIPS (D. F. Farmer, 1 9 8 1 ; C. Norrie, 1 984). Obrada i raspoznavanje slika, s druge strane, predstavlja problem s visokim stupnjem paralelizma koji j e svojstven podacima i operacijama. S .razvojem tehnologije vrlo visokog stupnja integracije visoko paralelne elektroničke i računalske strukture postale su dostupne, a njihova upotreba ekonomski opravdana u području obrade i raspoznavanja slika. Međutim, sada se pojavljuje problem: Kako upotrijebiti i iskoristiti te paralelne strukture? Postoje dva glavna pristupa: a) traženjem i iskorištavanjem paralelizma u postojećim sekvencijainim algoritmima, te prilagođavanjem tih algoritama visokoparalelnim struktu­ rama (D. J. Kuck, 1 977; C. V. Rammamoorthy, 1 969), b) vraćanjem na izvorne probleme, uvođenjem novih matematičkih i pro­ gramskih modela, koji će sačuvati svejstveni paralelizam prisutan u problemu (K. J . Thurber, 1 973; Thurber, 1 9 73). Prvi pristup daje određene rezultate. Međutim, upravo zbog sekvencijainosti, koja je posljedica prilagođavanja postupaka sekvencijalnom računalu, postoje ograničenja u djelotvornom iskorištenju visokoparalelnih struktura. Razlozi sekvencijaine obrade su povijesni - kao posljedica činjenice da ljudski, mehanički i elektronički mehanizmi (u širem smislu te riječi) koji su se upotrebljavali u rješavanju problema nisu bili sposobni za veće paralelne aktivnosti. S druge strane, naše kvantitativno opažanje i opisivanje svijeta (koji j e sam inherentno paralelan) već je više od tri stotine godina podvrgnuto utjecaju sekvencijaine matematike, više od 70 godina je pod teretom sekvencijainih algori­ tama i više od 30 godina pod utjecajem sekvencijainog programiranja. Prvi pristup nas ne oslobađa utjecaja "intelektualnog uskog grla" (prema J. Backusu) koj i nas vodi slijednom načinu rješavanja problema (word-at-a-time-thinking; J. Backus, 1 978). Drugi nam pristup omogućava djelotvorno iskorištenje svoj stvenog paraleli­ zma i upotrebu visokoparalelnih računalskih struktura (sistoličkih polja, računala upravljanih tokom podataka, matričnih procesora i sL), kojima se mogu postići potrebne performanse (S. Ribarić, 1 986). U ovom se poglavlju opisuje drugi pristup. U prvom se dijelu opisuju različite definicije paralelizma u obradi i raspoznavanju slika i prikazuje takso­ nornija paralelizma što su ga predložili P. E. Danielsson i S . Leviaidi (P. E. Danielsson, 1 98 1 ). P rocesori, odnosno procesni elementi, bez obzira koliko arhitektura računala odstupa od von Neumannova modela, važna su komponenta paralelnog sustava. Oni gotovo izravno utječu na performansu sustava. Zato se u prvom dijelu rada daju definicije procesora u sustavima za raspoznavanje i obradu slika. Prema odlikama obrade aritrnetičkih izraza E i logičkih izraza L procesori su razvrstani u četiri hij erarhijske razine. U drugom dijelu poglavlja definiraju se osnovni elementi modela paralelne obrade (slika, slikovna operacija, međuslika) koji su nam poslužili kao o snova za ocjenjivanje paraleinosti. U modelu je uvedena i izvorna mjera paralelizma stupanj paraleinosti slikovne operacije. Na temelju modela paralelne obrade predložen je model visokoparalelnog računala za obradu i raspoznavanje slika. _

15. MODEL PROCESORA ZA OBRADU l RASPOZNAVANJE SLIKA

292 1S.2.

PARALELIZAM U OBRADI I RASPOZNAVANJU SLIKA

U uvodnom dijelu rada upotrebljavali smo iZraz "paralelizam", međutim opće prihvaćena formalna definicija tog pojma u obradi i raspoznavanju slika n� postoji (M. J . B . Duff, 1 978). Paralelizam se definira prema pristupu: B . Kruse (B. Kruse, 1 973) smatra paralelizmom u obradi slike istovremenu aktivnost više procesora koji izvode operacije nad slikovnim elementima. M. J. Duff razumijeva pod paralelizmom istovremenu transformaci ju dijela slike (susjedstva) u novu vrijednost CM. J. Duff, 1 978). L. P. Cordena i S. Leviaidi ocjenjuju paralelizam pomoću koeficijenta povećanja brzine obrade SP = Tl I L, gdje je TP vrijeme potrebno za obradu sa p .. Jr procesora, a Tl vrIjeme potreb no za obradu uniprocesorom (računalo s jednim procesorom). P. E. Danielsson i S. LeviaIdi predlažu sljedeću taksonorniju paralelizma u obradi i raspoznavanju slike (P. E. Danieisson, 1 98 1 ): a) paralelizam na razini operatora ko> b) paralelizam na razini slike ki' c) paralelizam na razini lokalne operacije, odnosno operacije nad susjed­ stvom kn' d) paralelizam na razini slikovnog elementa kp• Paralelizam na razini operatora ko definiran je brojem stupnjeva (engL stage) u protočno; (engL pipeline) obradi. Svaki stupanj protočne strukture sastoji se iz memorijskog međuspremnika i procesora. Procesor u i-tom stupnju pribavlja podatak iz svog međuspremnika, izvodi operaciju nad njim i rezultat šalje međus­ premniku u i + l -tom stupnju. Procesor iz stupnja (i + l ) nastavlja obradu nad prispjelim podatkom dok procesor i-tog stupnja obrađuje podatak iz svog međus­ premnika (koj i je rezultat operacije procesora u stupnju i - I ). I stovremeno su svi procesori aktivni, ali na različitim podacima (c. V. Rammamoorthy, 1 977).

Paralelizam na razini slike ki definiran je brojem istovremeno pribavljenih i obrađenih različitih susjedstava slikovnih elemenata (brojem lokalnih operacija koje se izvršavaju istovremeno). Istovremeno izračunane (izlazne) vrijednosti slikovnih elemenata pripadaju istoj slici. Paralelizam na razini lokalne slikovne operacije kn definiran je brojem slikovnih elemenata koji pripadaju susjedstvu i koji se pribavljaju istovremeno. Procesor računa jedan (izlazni) slikovni element. Nakon toga prelazi na obradu sljedećeg susjedstva. Paralelizam na razini slikovnog elementa kp izražen je brojem bitova (kojim je zadana vrijednost slikovnog elementa) koji se pribavljaju istovremeno. Na temelju ko> ki' kn i kp dobiva se četverodimenzionalni prostor gdje pojedine vrste paralelizma predstavljaju ortogonalne osi prostora. Paralelizam u obradi i raspoznavanju određen je položajem točke u tom 4-dimenzionalnom prostoru. P. E. Danielsson i S. LeviaIdi uvode mjeru ukupnog paralelizma K (total paralle­ lism): K = ko · kj · kn · kp• Uz pomoć opisane taksonornije i uvedene mjere paralelizma P. E. Danielsson i S . Leviaidi su ocijenili niz procesora za obradu i raspoznavanje slika. Tako, na primjer, procesor Diff 3, koji je komercijalna verzija procesora GLOPR (razvije­ nog u Perkin Elemen Corp.), ima ukupni paralelizam K = 1 232 (ko = 2, ki = 8, kn = 7 i kp = 1 1), Kruseov procesor PICAP I ima K = 36 (ko = l , ki = l , kn = 9, i kp = 4) (B.

15,3, HlJERARNIJA PROCESORA

293

Kruse, 1 973, 1982), Duffov procesor CLIP IV ima K = 55 296 (k = l , kj = 96 x 96, kn' k =:= 6), a Cytocomputer (R. M . Lougheed, 1 980) ima K = 6336 (ko = 88, ki = l , kn = ,l;''J l kp = 8). Sve opisane mjere para1elnosti imaju zajedničko svojstvo da su definirane na temelj u svojstva arhitekture procesora (broj istovremeno aktivnih procesora, broj procesora koji izvršavaju operacije nad susjedstvom, broj protočnih segmenata u računalu i sl.). Mjera ukupnog paralelizma K ima još jedno važno svojstvo: ne zavisi od brzine upotrijebljenih sklopova (za razliku npr. od mjere-koeficijenta povećanja brzine obrade Sp) i frekvencije signalnog generatora vremenskog vođe� nja za procesor ili procesore koji su u sustavu raspoznavanja. Mjera K ne podrazumijeva da dva sustava s istim K imaju i jednake brzine obrade - oni samo imaju potencijalno jednake brzine. Mjera paralelizma opisana u odjeljku 1 5.4 ne zavisi od arhitekture procesora, već je samo funkcija značajki slikovnih operacija. Štoviše, takva mjera paralelizma može poslužiti kao referentna vrijednost kojoj trebamo težiti pri izboru arhitektu­ re i izvedbi procesora za obradu i raspoznavanje slika. 15.3. HIJERARlDJA PROCESORA

Procesori, odnosno procesni elementi, važna su komponenta visokoparalelnih računalskih sustava. Procesori u zavisnosti od svojih sposobnosti obrade gotovo i zravno utječu na performansu sustava. Od njihove izvedbe zavisi broj koraka T koji je potreban za računanje aritmetičkih E