Abstract

Realitatea augmentată înseamnă combinarea datelor generate de calculator cu cele obținute din lumea reala. Cu ajutorul realității augmentate interacțiunea cu calculatorul nu mai este doar un banal schimb fata – ecran. Aceasta se dizolvă în obiectele și spațiul înconjurător. Ea încetează chiar sa fie un act conștient și intenționat.

O interacțiune completă intre lumea reală și cea virtuală trebuie sa fie bidirecționala: calculatorul trebuie sa fie capabil sa înțeleagă lumea reala, iar obiectele generate de calculator trebuie sa fie complet compatibile cu lumea reala in care sunt plasate.

Aceasta lucrare își propune sa realizeze un sistem ce folosește realitatea augmentata pentru a permite unui utilizator uman sa joace șah cu un calculator, folosind o tabla reală. Calculatorul observa tabla cu ajutorul unei camere și răspunde la mutările făcute de utilizatorul uman, prin voce.

Sistemul permite și jocuri intre 2 utilizatori umani conectați prin internet. În acest caz fiecare utilizator are propria sa cameră și tablă de șah. Sistemul observă și înțelege mișcările făcute de cei 2 utilizatori si le transmite de la unul la celălalt prin internet.

Sistemul nu face nici o presupunere asupra:

• Culorii pieselor de pe tabla de șah
  
• Mărimea tablei de șah
  
• Aspectul vizual al tablei de șah
  
• Intensitatea și direcția luminii
  

Sistemul face următoarele presupuneri:

• Tabla de șah este complet conținută in imagine.
  
• Camera observă tabla de șah de la aceeași înălțime ca un utilizator uman.
  
• Imaginea conține o singură o tablă de șah și nu conține altă structură ce poate fi confundată cu o tablă de șah.
  
• Tabla nu se mișcă după ce piesele au fost aranjate.
  
• Utilizatorul uman respectă regulile jocului de șah.
  

Sistemul poartă numele de Mihos, după numele zeului egiptean al vederii.

Introducere

Șahul este un joc jucat de 2 jucători. Un jucător joacă cu piese albe, al doilea cu piese negre. Fiecare jucător are 16 piese la începutul jocului: un rege, o regină, două ture, doi nebuni, doi cai și opt pioni. Jocul se joacă pe o tablă cu 64 de pătrate: 8 rânduri și 8 coloane. Pătratele sunt alternativ albe și negre. Pentru a facilita notarea mișcărilor fiecare pătrat are o adresă proprie. Din punctul de vedere al jucătorului alb rândurile sunt numerotate 1, 2, 3, 4, 5, 6, 7, 8 de jos în sus, iar coloanele a, b, c, d, e, f, g, h de la dreapta la stânga. Adresa fiecărui pătrat este formata prin combinarea literei pentru coloană, cu cifra pentru rând. De exemplu pătratul din dreapta jos este are adresa a1 (1).

In studiul șahului majoritatea cercetărilor s-au axat pe inteligență artificială, pe construirea de programe capabile să joace șah (2). Aceste studii au fost parțial încheiate când un calculator a reușit să învingă un campion mondial de șah (3). Un studiu similar cu acesta a urmărit citirea mișcărilor de șah de către roboți (4).

Pentru captura de imagine Mihos folosește o camera web si imagini cu rezoluție de 640×480, 15fps.

Mihos întâi detectează o tablă de șah fără piese aflată in fața camerei. A fost implementat un algoritm, explicat in detaliu in Capitolul 2, care detectează cele 64 de pătrate ale tablei de șah.

Mihos nu restricționează poziția camerei raportată la tabla de șah. Din acest motiv este necesară determinarea matricei de proiecție 2D, din in care tabla de șah se află in o postură arbitrară fată de cameră (figura 1.1) , in o imagine in care camera este perpendiculară pe tabla de șah (figura 1.2).

Figura 1.1 – Camera în o postură arbitrară față de tabla de șah

Folosind parametri intrinseci ai camerei Mihos este capabil să găsească și coordonatele 3D ale tablei de șah, raportate la coordonatele camerei. Este folosit algoritmul Iterației ortogonale (5), care va fi detaliat in Capitolul 3.

Figura 1.2 – Camera
în o postură ideală fată de tabla de șah

După detecția inițială a tablei de șah Mihos va urmări mutările utilizatorului uman si după ce a fost detectată o mutare scena va fi analizată folosind tehnici bazate atât pe procesare de imagine cât și pe cunoștințe. Mihos urmărește mărimea diferenței intre 2 imagini pentru a detecta producerea unei mișcări si apoi variații in culoare in aceeași diferență pentru a vedea ce poziții pe tablă s-au modificat. Programul folosește reguli de șah și alte reguli empirice pentru a valida mutările detectate din imagine. Acest procedeu este descris in capitolele 4 și 5.

Mihos este scris în principal folosind platforma .NET, versiunea 3.5 și limbajul de programare C#, versiunea 3.0. Totuși anumite părți din program au necesitat folosirea de alte platforme sau limbaje de programare. Astfel algoritmul de găsire al tabelei de șah este scris in Matlab, versiunea 2008a, iar algoritmii de detecție și interpretare a mișcării sunt scriși in Managed C++, versiunea 9.

Aplicația Windows oferă utilizatorului o interfață în care obiecte 3D sunt generate și desenate în timp real peste o imagine de la o cameră web. Acest fel de interfață nu se putea obține, cu performanțe bune și în timp relativ scurt, decât folosind Windows Presentation Foundation din platforma .NET 3.0 și 3.5. În plus platforma .NET 3.5 include și extensii precum Linq, care au accelerat considerabil procesul de implementare. O altă caracteristică ce a determinat alegerea platformei .NET este interoperabilitatea foarte bună cu alte limbaje de programare și platforme (Matlab și Managed C++).

Am implementat algoritmii de detecție a tablei și de recuperare a posturii în Matlab pentru a accelera procesul de dezvoltare. Matlab nu oferă viteză de procesare foarte mare, dar în partea de detecție a tablei de șah o diferență de 200ms nu este foarte importantă.

Algoritmii de detecție și înțelegere a imaginii necesită viteză mare de procesare, pentru a obține o interacțiune in timp real între om și calculator. Este deci nevoie de C++. Pentru a face interfațarea cu platforma .NET mai rapidă și sigură am folosit extensiile managed ale C++, care permit folosirea obiectelor din platforma .NET și in un mediu unmanaged, precum C++.

Detecția tablei de șah

Înainte de a putea detecta și înțelege mișcări trebuie detectată tabla de șah. Aceasta poate fi de orice formă, cu orice culori și in orice postură față de cameră. Am impus totuși restricția ca ea să fie inclusă complet în imagine și in imagine să nu existe alte structuri care ar putea fi confundate cu o tablă de șah.

Figura 2.1 – Detecția tablei de șah

Prima etapă in detecția tablei de șah este achiziția imaginii. Mihos poate lucra cu orice camera video, conectată la calculator si compatibilă DirectShow. In continuare voi folosii o camera Philips SPC900NC, la rezoluția standard de 640×480, 15fps. Detalii mai multe despre conectarea camerei web la calculator vor fi date in capitolul 5.

FPS (frames per second) este unitatea de măsură a frecvenței cu care un producător de imagine produce imagini consecutive.

După achiziție imaginea este convertită in nuanțe de gri, după care a doua etapă este aplicarea operației morfologice de dilatare imaginii, prin care valoarea unui pixel din imagine devine maximul dintre valoare lui și valorilor vecinilor lui.

Pixelul este cea mai mică componentă a unei imagini.

Imaginea este apoi binarizată. Cele 256 de nivele de gri devin 2 nivele, alb și negru.

În imaginea binarizată sunt detectate contururile parților negre (intre care si pătratele negre, dar si alte contururi negre din imagine).

Aceste poligoane detectate sunt reduse folosind algoritmul Douglas Peucker la doar câteva segmente, apoi aceste segmente sunt reduse 4 folosind câteva reguli statistice si empirice.

Următoare etapă este aplicarea altor reguli statistice și empirice figurilor cu 4 laturi detectate în imagine. Rămân maxim 35 de pătrate, intre care și pătratele negre din tabla de șah.

Folosind morfologia tablei de șah găsesc orientarea tablei și 4 puncte care vor fi folosite apoi la recuperarea posturii tablei.

Morfologie matematică și dilatarea imaginii

Morfologia matematică este analizarea imaginilor folosind funcții matematice și teoria mulțimilor.

Mulțimile in morfologia matematică reprezintă formele obiectelor în o imagine. În imaginile binare toate mulțimile sunt membre ale spațiului întreg , unde fiecare element al unei mulțimi este un vector 2D, ale cărui coordonate sunt coordonatele ale pixelului în imagine. În imaginile în nuanțe de gri elementul unei mulțimi este , unde g este valoarea intensității. Mulțimi in spații n – dimensionale pot conține informații suplimentare (de exemplu culoare) (6).

Figura 2.1.1 – Două mulțimi A și B. (sursă (6))

Fie și două mulțimi în , având componentele și (figura 2.1.1). Câteva exemple de operații cu cele 2 mulțimi sunt:

• Translarea lui cu , notată , definită ca:
  

  
  

• Reflexia lui B, notată , definită ca:
  

  
  

• Complementul lui A, notat , definit ca:
  

  
  

• Diferența , definită ca:
  

  
  

Fie mulțimea vidă. Dilatarea lui A prin B este definită ca:

Dilatarea este deci mulțimea tuturor deplasărilor x astfel încât intersecția lui A cu B conține cel puțin un element. B este numit elementul structural în dilatare.

Dacă presupunem imaginea în nuanțe de gri sursă , elementul structural , domeniul lui și domeniul lui , atunci dilatarea pentru o imagine în nuanțe de gri este:

Mihos folosește dilatarea pentru a micșora părțile întunecate și deci pentru a separa pătratele negre de restul tabelei (figura 2.2.3).

Conversia imaginii: imagine color în imagine cu nuanțe de gri și apoi in imagine binară

Înainte de dilatare este nevoie de o conversie a imaginii din color în nuanțe de gri. După dilatare imaginea este convertită în imagine binară.

Imaginile color sunt in spațiul de culori RGB.

In spațiul de culori RGB fiecare culoare este reprezentată ca o combinație de 3 culori, roșu, verde și albastru.

Fie imaginea color inițială, imaginea în nuanțe de gri si imaginea binară. În acest caz , unde r, b, g sunt componentele roșu, verde și albastru ale culorii pixelului de la coordonatele , , unde i este valoarea intensității pixelului de la coordonatele în imaginea in nuanțe de gri si , unde v este valoarea intensității pixelului la coordonatele in imaginea binarizată.

Pentru a obține intensitatea pixelilor aplicăm formula:

Imaginea binară are numai 2 culori, 0 pentru negru și 255 pentru alb. Binarizarea se face in funcție de o valoare prag. Toate intensitățile mai mici decât valoarea prag vor devenii 0, și toate mai mari vor devenii 1. Mihos folosește pentru a determina valoarea prag următoarea formulă:

Trasarea conturului în jurul pătratelor negre

Pentru a găsii contururile Mihos întâi caută toate punctele ce mărginesc zonele negre. Un punct mărginește o zonă neagră daca are in apropierea lui pixeli albi. În continuare sunt grupate punctele după distanța intre ele și sunt găsite marginile zonelor negre (figura 2.3.1).

Figura 2.3.1 – Imaginea cu marginile marcate

În acest moment am găsit o lista de mulțimi de puncte, care mărginesc zone negre. Fiecare mulțime de puncte va fi simplificată folosind algoritmul Douglas Peucker și apoi din segmentele rămase vor fi alese numai 4, in funcție de unghiul dintre ele (rămân cele 4 segmente cu unghiul dintre ele cât mai apropiat de 90).

Algoritmul Douglas Peucker

Algoritmul Douglas Peucker folosește apropierea unui punct de o linie pentru a determina daca el face sau nu parte din linia respectivă.

Algoritmul funcționează de sus în jos, pornind cu o aproximare inițială a poligonului: o linie cu primul punct din lista de puncte la un capăt si cu ultimul la celălalt capăt. Apoi punctele rămase sunt testate pentru apropierea de această linie. Dacă un punct este mai departe de linie cu o toleranță , atunci este adăugat la simplificare și este creată o nouă aproximare a poligonului. Folosind recursie procesul continuă până când toate punctele au fost ori adăugate în poligon, ori distanța dintre ele și linie este mai mică decât toleranța (7).

Algoritmul este exemplificat în figura 2.3.2.

Figura 2.3.2 – Algoritmul Douglas-Peucker

Figura 2.3.3 – Rezultatul simplificărilor poligoanelor detectate

După cum se observă in figura 2.3.3 au fost detectate toate pătratele din tablă, dar au fost detectate și alte pătrate. Este chiar posibil sa nu fie detectate toate pătratele din tablă, dar să fie detectate alte pătrate din imagine.

Filtrare empirică, statistică și morfologică a pătratelor detectate

Din pătratele detectate se aleg numai acelea care respectă următoarele reguli empirice:

• să nu fie prea mici
  
• raportul dintre cea mai mică latură și cea mai mare să fie mai mic decât 0.6
  

După eliminarea empirică Mihos face una statistică. Sunt luați in calcul următorii factori:

• Aria
  
• Raportul între latura cea mai mică și cea mai mare
  
• Raportul între unghiurile dintre laturi
  
• Numărul de muchii detectate de algoritmul Douglas-Peucker.
  

Pentru fiecare din acești factori sunt calculați parametrii pentru o distribuție gaussiană: este media factorului (media ariilor detectate de exemplu) , iar este variabilă funcție de factor:

• Aria:
  
• Raportul între latura cea mai mică și cea mai mare:
  
• Raportul între unghiurile dintre laturi:
  
• Numărul de muchii detectate de algoritmul Douglas-Peucker:
  

  Distribuția gaussiană are 2 parametrii: media și deviația standard :
  

  
  

Fiecare pătrat din cele detectate va avea 4 probabilități, de corespondență la factorii de mai sus. Probabilitatea ca un pătrat să aparțină tablei este dată de produsul acestor 4 probabilități.

Figura 2.4.1 – Rezultatul eliminării statistice și empirice a pătratelor

Se observă în figura 2.4.1 că eliminarea nu a este perfectă. Este posibil ca să rămână pătate care nu aparțin tablei de șah, dacă ele sunt similare cu cele care aparțin tablei.

Ultima filtrare este una bazată pe morfologia tablei. Se poate observa că tabla de șah are o singura diagonala formată din pătrate negre. Aceasta trece prin centrul celor 8 pătrate. Daca deci tragem o linie din centrul fiecărui pătrat la centrul fiecărui alt pătrat exista o singură pereche de pătrate a cărei linie trece prin alte 6. Aceste 2 pătrate determină și orientarea tablei. Similar se observă că există si 3 perechi de pătrate a căror linie trece prin alte 5 pătrate. Pornind de la aceste premize vom găsii 8 pătrate, câte 2 pentru fiecare colț al tablei (figura 2.4.2).

Figura 2.4.2 – Cele 8 pătrate care marchează colțurile tablei

Interesat? Intra in contact cu autorul pentru restul lucrarii.