Note privind topologia digitală
Această secțiune discută despre metodele de „subțire” a unui S dat într-un grup de arce și curbe. Vom presupune că S constă în întregime din părți alungite, astfel încât arcurile și curbele rezultate sunt o aproximare rezonabilă la S (secțiunea 1.5c). Pentru alte tipuri de S, rezultatul pierderii în greutate nu ar trebui să fie deosebit de semnificativ. (Pentru o definiție a alungirii vezi secțiunea 3.4b). Rezultatul pierderii în greutate S va fi numit scheletul lui S .
MA al unui S subțiat oriunde poate fi considerat un schelet, dar are două defecte. În locurile în care S a fost lărgit, MA are o grosime de două puncte, deoarece MA este setul maxim al distanțelor a Љ, așa cum se arată în secțiunea 2.1a. De asemenea, după cum sa menționat acolo, MA tinde să fie deconectat și am dori ca bucăți conectate de S să fie subțiate în arcuri sau curbe conectate. În această secțiune vom descrie o schemă de subțiere care produce schelete conectate și subțiri.
Algoritmul nostru de subțiere este un proces special de contracție care elimină din S, la fiecare iterație, punctele de margine a căror eliminare nu le deconectează local vecinătățile; Se poate arăta [54] că acest lucru garantează că proprietățile conexiunii lui S nu se modifică, nici măcar dacă astfel de puncte sunt eliminate simultan. Pentru a preveni micșorarea unui arc deja subțiat la sfârșitul său, stipulăm, de asemenea, că punctele care au un singur vecin în S nu sunt șterse.
Din păcate, dacă eliminăm toate acele puncte de pe marginile lui S, iar S are o grosime de doar două puncte, de ex.,
atunci S va dispărea complet. Am putea evita acest lucru folosind un algoritm care examinează mai mult decât doar vecinul imediat al unui punct, dar un astfel de algoritm ar fi prea complicat. În schimb, vom elimina doar punctele de pe margine care se află pe o parte dată a lui S, adică care au un vecin specific (nord, est, vest sau sud) în Љ, într-o anumită iterație. Pentru a ne asigura că scheletul este cât mai aproape de „mijlocul” lui S, putem folosi laturi opuse alternativ, de exemplu, nord, sud, est, vest. (Este posibil să se elaboreze algoritmi care elimină punctele de margine de pe două laturi adiacente în același timp, de exemplu, nord și est, apoi vest și sud, dar această abordare este puțin mai complicată și nu va fi descrisă în detaliu aici. O altă posibilitate este de a verifica vecinii. unui punct de pe două părți pentru a determina dacă vor fi șterse și ele și, dacă da, nu ștergeți punctul dat).
Pentru a prezenta algoritmul mai precis, trebuie să oferim condițiile exacte în care un punct de margine poate fi eliminat. Punctul de margine P al lui S este numit simplu dacă setul de 8 vecini ai lui P care sunt în S are exact o componentă adiacentă lui P. Această ultimă clauză înseamnă că, dacă folosim 4 conectivități ale lui S, ne preocupă doar componentele care sunt 4-adiacente lui P. Dacă folosim conectivitatea 8, ultima clauză poate fi omisă. De exemplu, P este 4-simplu dacă vecinătatea sa este
întrucât în acest caz doar o 4-componentă a lui 1 este 4-adiacentă lui P; dar P nu este 4-simplu dacă vecinătatea sa este
Pe de altă parte, P este 8-simplu în al treilea caz, dar nu și în primele două cazuri.
Este ușor de văzut că ștergerea unui singur punct din S nu modifică proprietățile de conexiune ale lui S sau Љ; S - < P >are aceleași componente ca S, cu excepția faptului că uneia dintre ele îi lipsește acum punctul P și Љ И < P >are aceleași componente ca Љ, cu excepția faptului că acum P este una dintre ele. Rețineți că un punct izolat (care nu are un vecin în S) nu este simplu și că un punct final (care are exact un vecin în S) este automat simplu.
Algoritmul nostru de subțiere poate fi acum setat după cum urmează: Ștergem toate punctele de margine de pe o parte dată a lui S, atâta timp cât acestea sunt simple și nu puncte finale. Vom face acest lucru succesiv din partea de nord, sud, est, vest, nord. de S până nu mai există modificări. Un exemplu simplu al funcționării acestui algoritm este prezentat în Fig. 14.
Eliminarea punctelor de pe marginile unei laturi date a lui S trebuie făcută „în paralel”, adică condițiile pentru ștergerea unui punct trebuie verificate înainte ca orice alt punct să fie șters. (Să presupunem că nu o facem și că efectuăm doar îndepărtarea rând cu rând. Când ștergem punctele marginii nordice, vom elimina strat cu strat din partea de sus a S, iar scheletul rezultat nu ar fi simetric; de exemplu, dacă S ar fi un dreptunghi, nu ar mai rămâne nimic în afară de rândul său inferior după prima operație). În acest fel, fiecare iterație a algoritmului poate fi efectuată ca o simplă operație paralelă a unui computer multiprocesor.
Algoritmul poate fi implementat pe un computer convențional, utilizând urmărirea imaginilor pentru fiecare iterație. În fiecare rând, punctele sunt marcate pentru ștergere, dar nu sunt șterse până când punctele din rândul următor nu au fost marcate. Putem evita accesarea cu crawlere repetată a întregii imagini operând pe rândurile din secvența 1; douăzeci și unu; 3, 2, 1; . ca în secțiunea 2.1c. După k pași, unde 2 k + 1 este lățimea maximă a lui S, nu mai este necesară nicio subțire pe primul rând, deci poate fi abandonată; în acest fel, numai k rânduri vor trebui să fie disponibile în acel moment.