Ez a szakasz egy adott S "elvékonyításának" módszereit tárgyalja ívek és görbék csoportjában. Feltételezzük, hogy S teljes egészében hosszúkás részekből áll, így a kapott ívek és görbék ésszerű közelítést jelentenek az S-hez (1.5c. Szakasz). Más típusú S-k esetében a súlycsökkenés eredménye nem lehet különösebben jelentős. (A nyúlás meghatározását lásd a 3.4b szakaszban). S elvesztésének eredményét S csontvázának nevezzük .

topológiáról

A bárhol elvékonyodott S MA-ja csontváznak tekinthető, de két hibája van. Azokban a helyeken, ahol S kiszélesedett, MA két pont vastag, mivel az MA az a distances távolság maximumainak halmaza, amint az a 2.1a. Szakaszban látható. Továbbá, amint azt ott megjegyeztük, az MA hajlamos megszakadni, és azt szeretnénk, ha az összekapcsolt S-darabok elvékonyodnának összekapcsolt ívekké vagy görbékké. Ebben a részben egy vékonyodási sémát írunk le, amely összekapcsolt és vékony csontvázakat állít elő.

Hígítási algoritmusunk egy speciális zsugorodási folyamat, amely minden iterációnál eltávolítja az S-ből azokat az élpontokat, amelyek eltávolításával lokálisan nem választják le a szomszédságukat; Megmutatható [54], hogy ez garantálja, hogy az S csatlakozási tulajdonságai nem változnak, még akkor sem, ha az ilyen pontokat egyszerre távolítják el. Annak megakadályozására, hogy egy már elvékonyodott ív a végén zsugorodjon, azt is előírjuk, hogy azokat a pontokat, amelyeknek csak egy szomszédja van S-ben, nem törlik.

Sajnos, ha eltávolítjuk az összes pontot S széléről, és S vastagsága csak két pont, pl.,

akkor S teljesen eltűnik. Ezt elkerülhetnénk olyan algoritmus használatával, amely nemcsak egy pont közvetlen szomszédját vizsgálja, de egy ilyen algoritmus túl bonyolult lenne. Ehelyett csak azokat a pontokat távolítjuk el az élen, amelyek az S adott oldalán vannak, azaz amelyeknek adott szomszédságuk van (észak, kelet, nyugat vagy dél) Љ-ben, adott iterációban. Annak biztosítása érdekében, hogy a csontváz a lehető legközelebb legyen S "középső részéhez", az ellenkező oldalakat használjuk felváltva, pl. Észak, dél, kelet, nyugat. (Lehetséges olyan algoritmusok kidolgozása, amelyek egyidejűleg eltávolítják az élpontokat két szomszédos oldalról, pl. Észak és kelet, majd nyugat és dél, de ez a megközelítés egy kicsit bonyolultabb, és itt nem írjuk le részletesen. két pont szomszédjainak ellenőrzése annak megállapításához, hogy azokat is eltávolítják-e, és ha igen, ne törölje az adott pontot).

Az algoritmus pontosabb bemutatásához meg kell adnunk azokat a pontos feltételeket, amelyek mellett egy élpont eltávolítható. S S élpontját egyszerűnek nevezzük, ha P 8 szomszédjának S-ben lévő halmazának pontosan egy olyan komponense van, amely szomszédos P-vel. Ez az utolsó mondat azt jelenti, hogy ha az S 4-összekapcsolhatóságát használjuk, akkor csak azok a komponensek foglalkoznak, amelyek 4-vel szomszédosak a P-vel. Ha 8-kapcsolatot használunk, az utolsó tagmondat elhagyható. Például P 4 egyszerű, ha a szomszédsága megegyezik

mivel ebben az esetben az 1-eknek csak egy 4-komponense van 4-szomszédos P-vel; de P nem 4-egyszerű, ha a szomszédsága az

Másrészt P a harmadik esetben 8-egyszerű, de az első két esetben nem.

Könnyen belátható, hogy egyetlen pont törlése az S-ből nem változtatja meg sem S, sem Љ kapcsolati tulajdonságait; S - < P >komponensei ugyanazok, mint az S, azzal a különbséggel, hogy egyikükből hiányzik a P pont, és Љ И < P >komponensei megegyeznek a Љ-vel, azzal a különbséggel, hogy most P az egyik. Vegye figyelembe, hogy egy elszigetelt pont (amelynek nincs szomszédja S-ben) nem egyszerű, és hogy egy végpont (amelynek pontosan egy szomszédja van S-ben) automatikusan egyszerű.

Hígítási algoritmusunk most a következőképpen állítható be: Töröljük az összes élpontot az S adott oldalán, amennyiben azok egyszerűek és nem végpontok. Ezt egymást követően északi, déli, keleti, nyugati, északi oldalról fogjuk megtenni. addig, amíg nincs több változás. Az algoritmus működésének egyszerű példáját a 14. ábra mutatja.

Az S adott oldalának széleiről a pontokat ki kell küszöbölni "párhuzamosan", azaz. bármely pont törlése előtt ellenőrizni kell a pont törlésének feltételeit. (Tegyük fel, hogy nem tesszük, és csak soronként végezzük a törlést. Az északi perempontok törlésével rétegenként eltávolítjuk az S tetejét, és az így kapott csontváz nem lesz szimmetrikus; pl., Ha S egy téglalap, az első művelet után az alsó során kívül semmi sem maradna). Ily módon az algoritmus minden iterációja elvégezhető a multiprocesszoros számítógép egyszerű párhuzamos műveleteként.

Az algoritmus megvalósítható egy hagyományos számítógépen, minden iterációhoz képkövetést alkalmazva. Minden sorban a pontok megjelölésre kerülnek a törléshez, de addig nem törlődnek, amíg a következő sorban lévő pontokat meg nem jelölik. Elkerülhetjük a teljes kép ismételt feltérképezését, ha az 1. sorrendben működtetjük a sorokat; huszonegy; 3, 2, 1; . mint a 2.1c szakaszban. K lépés után, ahol 2 k + 1 az S maximális szélessége, az első sorban nincs szükség további elvékonyításra, így elhagyható; így egyelőre csak k sornak kell rendelkezésre állnia.

b. Alternatív fogyókúrák

A ritkítás egyszerűsített megközelítései néha alkalmazhatók. Például, ha S-nek lényegében állandó vastagsága van mindenütt (lásd a 3.2d. Szakaszt), mondjuk 2 k + 1, akkor azt k-szeres zsugorítással (legalábbis nagymértékben) elvékonyíthatjuk. Ne feledje azonban, hogy a csontváz eredménye időnként vastag vagy törött lehet. A (leírt) hígítási folyamat különböző vastagságú S-eket fog kezelni. Egy másik módszer [32], amely akkor használható, ha S állandó vastagságú ív, az az, hogy az S egyik végén két élkövető folyamatot kell elindítani, amelyek áthaladnak az ellentétes oldalakon Hasonlóképpen, ha S zárt, állandó vastagságú görbe, akkor két élkövetési folyamatot indítunk olyan pontokon, amelyek csak S vastagságúak egymástól, keresztezve az S két szélét.) Ha az élkövetők közötti távolság nagyobb lesz, mint a vastagságot, az egyiket addig állítjuk meg, amíg a másik el nem éri, így mindig megközelítőleg egymás mellett maradnak. Az élkövetőket összekötő vonal szegmensének középpontja egy S .


14. ábra Hígítás. a) S eredeti; (b) - (e) északról, délről, keletről és nyugatról történő egymást követő elvékonyodás eredményei, az S-t 8-kapcsoltként kezelve. A következő északi lépésben az e) pont fölötti pontot törlik; a következő déli hágónál a legalacsonyabbtól balra legtávolabbi pont; a következő nyugati hágón pedig a csúcs legtávolabbi pontjai. Más változás nem lesz. Figyelje meg, hogyan zsugorodik le a sarok a bal felső sarokban a jobb felső sarokban lévő átlós vonalra. (b ’) - (e’) analóg eredmények, amelyek S-t 4-kapcsoltként kezelik, és meghatározzák azokat a végpontokat, amelyeknek csak egyetlen 4 szomszédja van S-ben. A további északi lépés megszűnik a következő északi lépésben; nem lesz több változás.

Hígító algoritmusok többféleképpen definiálhatók a többértékű képekhez. Közelítés [15] az általános pont definíciójának általánosítása a következőképpen: meghatározzuk a P 1 út erejét. P n, mint az út bármely pontjának minimális értéke, valamint P és Q, mint bármely P-től Q-ig terjedő út maximális erejének összekapcsolódásának mértéke. Azt mondjuk, hogy P "egyszerű", ha helyettesítjük a a szomszédok nem csökkentik egyetlen pontpár összekapcsolásának mértékét a 8 szomszédságában. Ellenőrizhető, hogy ez általánosítja-e az a) pontban megadott kétértékű definíciókat. A ritkítást ezután speciális helyi minimális műveletként definiáljuk: a pontokat többször kicseréljük a szomszédaik minimumára, amennyiben azok egyszerűek és több szomszédjuk is magasabb értékkel rendelkezik (ez általánosítja azt a feltételt, hogy az izolált és a végső pontok ne eltávolítják). Minden iterációban ezt csak az egyik oldalról tesszük, vagyis csak azokig a pontokig tesszük, amelyeknek szomszédja alacsonyabb értékkel rendelkezik egy adott oldalon (északon, délen.). Ennek a folyamatnak egy képsorra történő alkalmazásának eredményeit a 15. ábra mutatja.

A határfelismerő operátorok kimenete általában vastag. Hígítható a nem-maximák elnyomásával a gradiens irányában az egyes pontokban; ez mindent kizár, kivéve az egyes határkeresztmetszetek legmeredekebb határértékét, de nem engedi, hogy a határ mentén lévő pontok versenyezzenek egymással. Egy másik lehetőség az egyes pontok értékének arányos növelése vagy csökkentése aszerint, hogy mekkora nagyobb vagy kisebb a szomszédjához képest a gradiens irányában. Ez azt eredményezi, hogy a határ egyes keresztmetszeteiben a maximális érték növekszik az alacsonyabb értékek rovására, így végül elnyeli az összes választ e keresztmetszetből [17].


15. ábra Példa szürkeárnyalatos ritkításra.

c. A fogyás eredménye

Ideális esetben azt mondjuk, hogy a T halmaz A részhalmaza egyszerű digitális ív, ha ez egy T összekapcsolt alkotóeleme, amelynek minden pontján pontosan két szomszéd van T-ben, kivéve a két végpontot, amelyeknek egy-egy szomszédja van. Vegye figyelembe, hogy ez két definíció egyben, attól függően, hogy 4 vagy 8 szomszédokra gondolunk. Vegye figyelembe azt is, hogy egy ív nem tud elágazni, keresztezni önmagát vagy akár megérinteni önmagát, különben olyan pontokat tartalmazhat, amelyeknél kettőnél több szomszéd van S-ben. Egy egyszerű zárt digitális görbe a T összekapcsolt C komponense, amelynek minden pontján pontosan két szomszéd van T-n; itt is két definíciónk van. Vegye figyelembe, hogy egy él nem mindig egyszerű zárt görbe, mivel kétszer is áthaladhat egyes pontokon.

Az S elvékonyításának célja egy olyan T előállítása, amely az ilyen ívek és görbék egyesülése lehet, miután néhány áthaladt vagy elágazó pont - azaz kétnél több szomszéddal rendelkező pont - megszűnt. Ne feledje, hogy az ilyen pontok gyakran megjelennek fürtökben; például mérlegeljük

1 J J J 1 és J J

ahol J-ekkel jelöltük az egyesülési pontokat. Ha a görbék és kereszteződések sok ága nagyon közel fut egymáshoz, akkor nehéz lesz azonosítani és osztályozni az egyes ízületeket. A karcsúbb S-nek lehetnek belső pontjai is; egy 8 kapcsolt példa

amelyben minden élpont vagy végpont, vagy nem egyszerű, így a ritkításnak nincs hatása. A fogyás eredményei a tájolástól függenek; például amikor 8-fogyunk

1 1 1 1 1 1 1 1 1

de amikor 8-haladunk

1 1 1 1 1 1 1 1 1 1

(4 elvékonyodás alatt ezek a minták nem változnak)

A kettőnél több szomszéddal rendelkező pontok kiküszöbölése után könnyen felépíthető a szomszédból a szomszédba mozgó ív húrjainak kódja, amely az egyik végponttól kezdve a másikig végződik; vagy egy tetszőleges kezdőponttól kezdődő és egy irányban haladó éles görbe, amíg a kiindulási pontot ismét el nem érik.

A ritkítás néha "tüskés" csontvázakat eredményez, különösen akkor, ha S "szőrös" élekkel rendelkezik, amelyek sok végpontot tartalmaznak, vagy amikor a végpontok idő előtt előjönnek a ritkítási folyamat során; ezt különösen nagyra értékelik az algoritmus 4-kapcsolati változatában. A nem megfelelő csontvázág észlelésének egyik módja [56], ha figyelembe vesszük az elágazási pontok távolságát the-től, vagy ezzel egyenértékűen az iterációkat, amelyekben élpontokká válnak. Egy valódi csontvázágban ezeknek a távolságoknak megközelítőleg állandóaknak kell lenniük, de egy csúcságban folyamatosan növekedniük kell, ahogy haladunk a csúcs végétől.