RECUNOASTEREA FORMELOR(2/2)

METODE STRUCTURALEPotrivirea numerelor de formaPotrivirea de siruriRecunoasterea sintactica a sirurilorRecunoasterea sintactica a arborilor

Potrivirea numerelor de forma

~ distanta minima

Gradul de simiaritate k intre doua granite de regiuni (forme) = cel mai mare ordin pentru care numerele de forma ale acestora inca coincid.

Exemplu: doua forme a si b (coduri inlantuite cu 4 directii) grad de similaritate k daca:

sj(a) = sj(b) pentru j = 4, 6, 8, ... , k

sj(a) ≠ sj(b) pentru j = k+2, k+4, ...

(s = numar de forma, j = ordinul numarului de forma = numar de cifre pentru reprezentare).

Obs. k mare => forme asemanatoare, k =∞ =>forme identice.

Distanta dintre doua forme a si b:D(a,b) = 1/k

Proprietati:D(a,b) ≥ 0D(a,b) = 0 daca a = bD(a,c) ≤ max [D(a, b), D(b, c)]

Aplicatie. (a) Care forma a-e se potriveste cel mai bine cu f ? (b) => arborele de similaritate (radacina ~ grad de similaritate minim, 4 in acest exemplu) => f grad maxim de similaritate cu c; (c) aceleasi informatii si din matricea de similaritate.

a)

b) c)

Potrivirea de siruri

-a1a2...an si b1b2...bn = siruri codificand granite de regiuni a si b;

-α = numar de potriviri intre cele doua siruri (potrivire in pozitia k: ak =

bk);

-numarul de simboluri care nu se potrivesc:β = max (|a|, |b|) - α

( |arg| = lungimea sirului, numar de simboluri) => β = 0 siruri identice.

Masura de similaritate, raportul:

|)||,max(| baR

(R = ∞ potrivire perfecta, R = 0 nu se potriveste niciun simbol).

Important punctul de start!

Aplicatie. (a), (b) granite, doua clase; (c), (d) apoximate prin poligoane, unghiul dintre segmente succesive codificate cu opt posibile simboluri α1: 0˚ < θ

≤ 45˚; α2: 45˚ < θ ≤ 90˚; ... ; α8: 315˚ < θ ≤ 360˚; (e) R pentru cinci esantioane

de obiecte din clasa 1 (ex: notatia 1.c indica al treilea sir din clasa 1); (f) analog pentru clasa 2; (g) R la compararea de siruri din clase diferite.

a) b)

c) d)

e) f)

g)

Recunoasterea sintactica a sirurilor

Baza:-set de primitive de forme;-set de reguli (gramatica) interconectarea acestora;-automat de recunoastere.

Gramatici de siruri

- ω1 si ω2 doua clase de forme ~ siruri de primitive (descriptori

relationali);-primitiva ~ simbol permis in alfabetul unei gramatici;-gramatica = set de reguli de sintaxa genereaza propozitii formate

din simboluri apartinand alfabetului;- limbaj L(G) = setul de propozitii generate de o gramatica G.

Gramatici G1 si G2 :

-G1 propozitii ~ forme din clasa ω1 ;

-G2 propozitii ~ forme din clasa ω2.

Procesul de recunoastere de forme: o propozitie (forma necunoscuta) in care limbaj forma reprezinta o propozitie valida?

-propozitia Є L(G1) => forma Є ω1;

-propozitia Є L(G2) => forma Є ω2;

-propozitia invalida in ambele limbaje => forma rejectata.

Asemanator pentru mai multe clase.

Gramatica:G = {N, ∑, P, S}

undeN = set finit de variabile numite nonterminali;∑ = set finit de constante numite terminali;P = set de reguli de rescriere numite productii;S = simbolul de start, apartinand lui N.

(N si ∑ disjuncte).

Conventii de notatie:A, B, ... ,S, ... : nonterminali;a, b, c, ... (litere mici la inceputul alfabetului): terminali;v, w, x, y, z (litere mici la sfarsitul alfabetului): siruri de terminali;α, β, θ, ... (litere mici grecesti): siruri cu terminali si nonterminali;λ : propozitia vida (fara simboluri);V* : setul tuturor propozitiilor compuse cu elemente din setul de simboli

V.

Exemplu. Obiect reprezentat prin schelet primitive pentru descriere. Gramatica G = {N, ∑, P, S}, cu N = {A, B, S}, ∑ = {a, b, c} si P = {S aA, A bA, A bB, B c} (terminalele a, b, c corespund primitivelor). Aplicand aceste productii => sirul abbbbbc (~ structurii obiectului).

Limbajul generat:L(G) = {abnc | n≥1} => schelete de forma din figura de lungime arbitrara.

Productia Informatii semanticeS aA Conexiunea numai la punct. Directia lui a, notata cu

θ, data de bisectoare. Lungimea segmentelor 3 cm fiecare.

A bA Conexiunea numai la punct. Fara conexiuni multiple. Directia lui b aceeasi cu directia lui a. Lungimea 0.25 cm. Numar maxim de aplicari ale productiei 10.

A bB Aceeasi directie cu a. Conexiune simpla. Conexiune numai la punct.

B c Aceeasi directie cu a. Conexiune simpla. Conexiune numai la punct.

Utilizarea semanticilor

-forme complicate reguli de conectivitate, alti factori (lungimea si directia primitivelor), de cate ori se pot aplica productiile => reguli semantice memorate in baza de cunostinte.

Exemplul precedent: informatii semantice:

=> clasa de forme larga, dar limitata!

Automate de recunoastere a sirurilor

Problema: recunoasterea daca o forma apartine limbajului L(G) generat de o gramatica G => automat: recunoaste daca un sir de intrare (forma) Є limbajului asociat (automate finite care recunosc limbaje generate de gramatici regulate).

Automat finit:Af = (Q, ∑, δ, q0, F)

undeQ = set finit si nevid de stari;∑ = alfabet finit de intrare;δ = o mapare de la Qx∑ la colectia tuturor subseturilor lui Q;q0 = starea de start;

F = set de stari finale sau acceptabile (un subset al lui Q).

Exemplu. automat Q = {q0, q1, q2}, ∑ = {a, b}, F = { q0} si maparile

δ(q0,a) ={ q2}, δ(q0,b) ={ q1}, δ(q1,a) ={ q2}, δ(q1,b ={ q0}, δ(q2,a) ={ q0}, δ(q2,b)

={q1}. Diagrama de stari:

(aici starea initiala si starea finala coincid)Sir w acceptat (recunoscut): starea initiala starea finala (ex: automatul recunoaste abbabb, dar rejecteaza aabab).

Proiectarea unui automat finit (recunoastere sintactica de siruri ) dintr-o gramatica regulata data.

Fie gramatica G = {N, ∑, P, X0}, unde X0 ≡ S, N = X0 plus n

nonterminali suplimentari X1 , X2 , .... , Xn .

=> Q (automat) = n + 2 stari {q0, q1,...., qn, qn+1,} (qi ~ Xi pentru 0 ≤ i ≤ n

si qn+1 starea finala).

=> ∑ (set de simboluri de intrare pentru automat) = ∑ (set terminali din G).

=> maparile δ: utilizarea a doua reguli bazate pe productiile lui G, adica pentru fiecare i si j cu 0 ≤ i ≤ n, 0 ≤ j ≤ n:

1. daca Xi aXj este in P atunci δ(qi, a) contine pe qj.

2. daca Xi a este in P atunci δ(qi, a) contine pe qn+1.

Proiectarea gramaticii regulate dintr-un automat finit dat.

Fie un automat finit Af = (Q, ∑, δ, q0, F) => gramatica regulata

corespunzatoare G = {N, ∑, P, X0}:

=> N = elemente din Q cu X0 (simbolul de start ) ~ q0;

=> productiile P:

1. qj Є δ(qi, a) => Xi aXj Є P.

2. o stare F Є δ(qi, a) => Xi a Є P.

=> setul terminali ∑ acelasi.

Exemplu. Automatul finit pentru gramatica din exemplul precedent de la "Gramatici de siruri“:

=> productiile X0 aX1, X1 bX1, X1 bX2, X2 c.

=> Af = (Q, ∑, δ, q0, F) cu Q = {q0, q1, q2, q3}, ∑ = {a, b, c}, F = { q3} si

maparile δ(q0,a) ={ q1}, δ(q1,b) ={ q1, q2}, δ(q2,c) ={ q3}.

Pentru a fi complet: δ(q0,b) = δ(q0,c) = δ(q1,a) = δ(q1,c = δ(q2,a) =

δ(q2,b) = Ø (multimea vida) ~ tranzitii nedefinite.

Recunoasterea sintactica a arborilorregiunile / obiectele de interes ~ arbori

Gramatici de arbori

Gramatica de arbori:G = (N, ∑, P, r, S)

N = set finit de variabile - nonterminali;∑ = set finit de constante - terminali;P = set de reguli de rescriere - productii Ti Tj, (Ti ,Tj arbori);

r = functie de rang = numarul de descendenti directi (fii) ai unui nod a carui eticheta este un terminal din gramatica;

S = simbolul de start (in general poate fi un arbore) Є N.

Gramatica de arbori expansivi cu productii de forma:

(X1, X2, ... , Xn nonterminali, k terminal)

Exemplu. scheletul unei structuri generat cu gramatica N = { X1, X2, X3,

S}, ∑ = {a, b, c, d, e} (terminali ~ primitivele din figura).

-conectivitate cap-la-coada ("head-to-tail") a primitivelor linie;-conexiuni arbitrare la cerc de-a lungul circumferintei;

=> productii:

(5) X2 a=> functiile de rang r(a) ={0, 1}, r(b) = r(d) = {1}, r(e) = {0,1}, r(c) = {2}.

Restrictii: -productiile 2, 4 si 6 aplicate de acelasi numar de ori => structura cu

cele trei picioare de aceeasi lungime.-productiile 4 si 6 aplicate de acelasi numar de ori => structura

simetrica dupa axa verticala (informatii semantice ~ gramatici de siruri).

Automate de arbori

Automat de arbori:-incepe scanarea simultan la fiecare nod de pe frontiera (frunzele de la

stanga la dreapta);-continua dupa cai paralele spre radacina.

Automat frontiera-la-radacina:At = (Q, F, { fk | kЄ ∑ } )

Q = set finit de stari;F = subset al lui Q, set al starilor finale;fk = relatie in QmxQ (deci un subset al setului QmxQ) astfel incat m este

un rang al lui k.

Gramatica de arbori expansivi G = (N, ∑, P, r, S) => automatul de arbori corespunzator: Q = N, F = {S}, pentru fiecare simbol k Є ∑ se defineste o relatie fk astfel incat (X1, X2, ... , Xm, X) Є fk daca si numai daca exista in G o

productie:

Exemplu. Gramatica de arbori G = (N, ∑, P, r, S) cu N = {S, X}, ∑ = {a, b, c, d}, productiile:

rangurile: r(a) = {0}, r(b) = {0}, r(c) = {1}, r(d) = {2} => automatul de arbori corespunzator At = (Q, F, { fk | kЄ ∑ } ) cu Q = {S, X}, F = {S} si { fk | kЄ ∑ } = { fa,

fb, fc, fd } relatiile:

fa = {(Ø, X)}, provenind din productia X a

fb = {(Ø, X)}, provenind din productia X b

fc = {(X, X)}, provenind din productia

fd = {(X, X, S)}, provenind din productia

Interpretare:-relatia fa : un nod cu eticheta a fara fii (Ø) i se asigneaza starea X;

-relatia fc : un nod cu eticheta c cu un fiu avand starea X, i se

asigneaza starea X;-relatia fd : un nod cu eticheta d cu doi fii, fiecare avand starea X, i se

asigneaza starea S.

Arbore generat de gramatica recunoscut de automatul de arbori:

Aplicatie. Imagine din fizica energiilor inalte (ciocniri intre particule).

Remarca: structura naturala de arbore a unei ciocniri (mijlocul imaginii). Experiment tipic => sute de mii de fotografii, multe fara evenimente de interes => prelucrare automata.

Gramatica de arbori G = (N, ∑, P, r, S) => arbori ~ evenimente tipice din experiment.

N = {S, X1, X2}, ∑ = {a, b}, interpretate astfel:

Productiile in P:

rangurile: r(a) ={0, 1, 2, 4, 6} si r(b) = {0, 1} (productiile de ramificare ~ numarul de urme rezultate dintr-o coliziune, perechi, maxim 6). Ex: coliziune segmentata in sectiuni convexe si concave => arbore (acesta + variatii generate cu gramatica precedenta).

Automatul de arbori: At = (Q, F, { fk | kЄ ∑ } ) cu Q = {S, X1, X2}, F = {S} si { fk |

kЄ ∑ } = { fa, fb,} relatiile:

fa = {(S,S), (X1, X2, S), (X1, X1, X2, X2, S), (X1, X1, X1, X2, X2, X2, S), (X1,

X1), (Ø, X1)}

fb = { (X2, X2), (Ø, X2)}

Tema. Sa se arate ca acest automat accepta arborele de mai sus.

Invatare

In aplicatii complexe: algoritm de invatare a automatelor din esantioane de forme (siruri / arbori).

Presupuneri:-toate formele unei clase generate de o gramatica necunoscuta G;-este disponibil un set finit de esantioane R+ cu proprietatea:

)}(|{ GLinvvR

(“set de esantioane pozitive” = set de forme de antrenare din clasa asociata cu gramatica G)

-set de esantioane complet structural ~ fiecare productie in G este utilizata sa genereze cel putin un element din R+.

Problema: invatarea (sinteza) unui automat finit Af care va accepta

siruri din R+ si posibil anumite siruri care seamana cu cele din R+.

corespondenta dintre G si Af => *R

(∑* = setul tuturor sirurilor compuse cu elemente din ∑)

Definitie. Pentru un intreg pozitiv k se defineste coada k a lui z Є ∑* fata de R+ ca fiind setul h(z, R+ , k):

h(z, R+ , k) = { w | zw Є R+, |w| ≤ k }

Definitie echivalenta. Coada k a lui z este setul de siruri w cu proprietatile:(1) zw Є R+;(2) lungimea lui w este ≤ k.

Procedura de invatare a unui automat Af (R+,k)= (Q, ∑, δ, q0, F) dintr-un

set de esantioane R+ si o valoare particulara k:

1) seteazaQ = { q | q = h(z, R+ , k) pentru z Є ∑* }

2) seteazaq0 = h(λ, R+,k)

3) pentru fiecare a Є ∑δ (q, a) = { q' Є Q | q' = h(za, R+ , k), cu q = h(z, R+ , k) }

4) seteazaF = { q | q Є Q, λ Є q}

(λ = sirul vid, fara simboluri)

Exemplu. R+ = {a, ab, abb}, k = 1 =>1) , 2)

z = λ, h(λ, R+,1) ={ w | λw Є R+, |w| ≤ 1 } = {a} = q0

z = a, h(a, R+,1) ={ w | aw Є R+, |w| ≤ 1 } = { λ,b} = q1

z = ab, h(ab, R+,1) = { λ,b} = q1

z = abb, h(abb, R+,1) = { λ} = q2

Alte siruri z Є ∑* furnizeaza siruri zw care nu apartin lui R+ => a patra stare notata qØ, corespunzand conditiei ca h este setul nul.

=> starile: q0 = {a}, q1 = {λ,a}, q2 = { λ} si qØ => Q = { q0, q1, q2, qØ,}

11 )1,,(),( qRabhbq

21 )1,,(),( qRabbhbq

3) functiile de tranzitie.

Deoarece q0 = h(λ, R+,1) =>

δ (q0, a) = h(λa, R+,1) = h(a, R+,1) = q1

δ (q0, b) = h(λb, R+,1) = h(b, R+,1) = qØ

Deoarece q1 = h(a, R+,1) = h(ab, R+,1) =>

δ (q1, a) = h(aa, R+,1) = h(aba, R+,1) = qØ

=> δ (q1, b)={ q1, q2 }

Analog:δ (q2, a)= δ (q2, b)= δ (qØ, a)= δ (qØ, b)= qØ

4) setul starilor finale = stari care au sirul vid λ in reprezentarea lor de tip coada k => q1 = { λ , b}, q2 = { λ } => F = { q1, q2 }.

Automatul de inferenta obtinut:Af ( R

+,1) = (Q, ∑, δ, q0, F)

unde Q = { q0, q1, q2, qØ,}, ∑ = {a, b}, F= { q1, q2 } si functiile de tranzitie

precedente. Diagrama de stari:

Automatul accepta siruri de forma: a, ab, abb, ... , abn.

0)],([ ktotipentrukRALR f

)],([)]1,([ kRALkRAL ff

Valoarea lui k controleaza natura automatului rezultat Af ( R+,k) !

Proprietati (exemplifica dependenta de k):

Proprietatea 1.

unde L[Af ( R+,k)] = limbajul accetat de Af ( R

+,k).

Proprietatea 2.

L[Af ( R+,k)] = R+ daca k ≥ lungimea celui mai lung sir din R+;

L[Af ( R+,k)]= ∑* daca k = 0.

Proprietatea 3.

Observatii.

Proprietatea 1 garanteaza ca Af ( R+,k) va accepta sirurile din setul de

esantioane R+.

Daca k ≥ lungimea celui mai lung sir din R+ => automatul va accepta numai sirurile din R+ (proprietatea 2).

Daca k = 0 => Af ( R+,0) cu o singura stare q0 ={ λ } (stare initiala si

stare finala), functiile de tranzitie de forma δ (q0, a) = q0 pentru a Є ∑ =>

L[Af( R+,k)] = ∑* (automatul va accepta sirul vid λ si toate sirurile compuse din

simboluri din ∑).

Proprietatea 3: sfera (intinderea) limbajului acceptat de Af ( R+,k) scade

cu cresterea lui k.

Exemplu. R+ = {caaab, bbaab, caab, bbab, cab, bbb, cb}, k = 1=>

1. z = λ, h(λ, R+,1) = {Ø} = qØ;

2. z = c, h(λ, R+,1) = {b} = q1;

3. z = ca h(λ, R+,1) = {b} = q1;

4. z = cb, h(λ, R+,1) = { λ } = q0;

5. z = caa, h(λ, R+,1) = {b} = q1;

6. z = cab, h(λ, R+,1) = { λ } = q0;

7. z = caaa, h(λ, R+,1) = {b} = q1;

8. z = caab, h(λ, R+,1) = { λ } = q0;

9. z = caaab, h(λ, R+,1) = { λ } = q0;

10. z = b, h(λ, R+,1) = {Ø} = qØ;

11. z = bb, h(λ, R+,1) = {b} = q1;

12. z = bba, h(λ, R+,1) = {b} = q1;

13. z = bbb, h(λ, R+,1) = { λ } = q0;

14. z = bbaa, h(λ, R+,1) = {b} = q1;

15. z = bbab, h(λ, R+,1) = { λ } = q0;

16. z = bbaab, h(λ, R+,1) = { λ } = q0;

Automatul:Af ( R

+,1) = (Q, ∑, δ, q0, F)

unde Q = { q0, q1, qØ,}, ∑ = {a, b, c}, F= { q0 } si functiile de tranzitie date in

diagrama de stari:

Pentru a fi acceptat un sir trebuie sa inceapa cu a, b sau c si sa se termmine cu un simbol b. De asemenea sunt acceptate siruri cu repetitii ale lui a, b sau c.

Avantajul metodei: simplitatea implementarii. Dezavantaj: decizia pentru o valoare potrivita a lui k.