Бележки по цифровата топология
Този раздел обсъжда методи за "изтъняване" на даден S в група дъги и криви. Ще приемем, че S се състои изцяло от удължени части, така че получените дъги и криви са разумно приближение към S (раздел 1.5в). За други видове S, резултатът от загуба на тегло не трябва да бъде особено важен. (За дефиниция на удължаване вижте раздел 3.4б). Резултатът от загубата на S ще се нарече скелет на S .
MA на S, изтънен навсякъде, може да се счита за скелет, но има два недостатъка. На места, където S е разширен, неговият MA е с дебелина две точки, тъй като MA е набор от максимуми на разстоянията a Љ, както е показано в раздел 2.1а. Също така, както е отбелязано там, MA има тенденция да бъде изключен и бихме искали свързаните парчета от S да бъдат изтънени в свързани дъги или криви. В този раздел ще опишем схема за изтъняване, която създава свързани и тънки скелети.
Нашият алгоритъм за изтъняване е специализиран процес на свиване, който премахва от S, при всяка итерация, крайните точки, чието премахване не прекъсва локално техните квартали; Може да се покаже [54], че това гарантира, че свойствата на свързване на S не се променят, дори ако всички тези точки се премахнат едновременно. За да предотвратим свиването на вече изтънена дъга в своя край, ние също така предвиждаме, че точките само с един съсед в S не се изтриват.
За съжаление, ако премахнем всички тези точки от ръбовете на S и S има дебелина само две точки, напр.,
тогава S ще изчезне напълно. Можем да избегнем това, като използваме алгоритъм, който изследва не само непосредствения съсед на точка, но такъв алгоритъм би бил твърде сложен. Вместо това ще премахнем само точките на ръба, които са от дадена страна на S, т.е. които имат специфичен съсед (север, изток, запад или юг) в Љ, в дадена итерация. За да гарантираме, че скелетът е възможно най-близо до "средата" на S, използваме последователно противоположни страни, например север, юг, изток, запад. (Възможно е да се създадат алгоритми, които премахват точки на ръба от две съседни страни едновременно, например север и изток, а след това запад и юг, но този подход е малко по-сложен и няма да бъде описан подробно тук. Друга възможност е да се проверят съседите. на точка от две страни, за да се определи дали и те ще бъдат премахнати и ако е така, не изтривайте дадената точка).
За да представим алгоритъма по-точно, трябва да дадем точните условия, при които дадена точка на ръба може да бъде премахната. Точката на ръба P на S се нарича проста, ако множеството от 8-съседи на P, които са в S, има точно един компонент, който е в съседство с P. Тази последна клауза означава, че ако използваме 4-свързаност на S, ние се занимаваме само с компонентите, които са 4-съседни на P. Ако използваме 8-свързаност, последната клауза може да бъде пропусната. Например, P е 4-прост, ако неговият квартал е
тъй като в този случай само 4-компонент от 1 е 4-съседен на P; но P не е 4-прост, ако неговият квартал е
От друга страна, P е 8-прост в третия случай, но не и в първите два случая.
Лесно е да се види, че изтриването на една точка от S не променя свойствата на връзката нито на S, нито на Љ; С - < P >има същите компоненти като S, с изключение на това, че в един от тях сега липсва точката P, и Љ И < P >има същите компоненти като Љ, с изключение на това, че сега P е един от тях. Имайте предвид, че изолирана точка (която няма съсед в S) не е проста и че крайната точка (която има точно един съсед в S) е автоматично проста.
Нашият алгоритъм за изтъняване вече може да бъде настроен по следния начин: Изтриваме всички точки на ръба от дадена страна на S, стига да са прости, а не крайни точки. Ще правим това последователно от север, юг, изток, запад, север. от S, докато няма повече промени. Прост пример за работата на този алгоритъм е показан на фиг. 14.
Елиминирането на точките от ръбовете на дадена страна на S трябва да се извършва "паралелно", т.е. условията за изтриване на точка трябва да бъдат проверени преди да се изтрие друга точка. (Да предположим, че не го правим и просто изпълняваме изтриването ред по ред. Когато изтрием точките на северния ръб, бихме премахнали слой по слой от горната част на S и полученият скелет не би бил симетричен; напр. Ако S беше правоъгълник, няма да остане нищо освен долния му ред след първата операция). По този начин всяка итерация на алгоритъма може да бъде изпълнена като проста паралелна операция на многопроцесорен компютър.
Алгоритъмът може да бъде реализиран на конвенционален компютър, като се използва проследяване на изображения за всяка итерация. Във всеки ред точките са маркирани за изтриване, но не се изтриват, докато не бъдат маркирани точките в следващия ред. Можем да избегнем повтарящи се обхождания на цялото изображение, като работим върху редовете в последователност 1; двадесет и едно; 3, 2, 1; . както в раздел 2.1в. След k стъпки, където 2 k + 1 е максималната ширина на S, не е необходимо по-нататъшно изтъняване на първия ред, така че той може да бъде изоставен; по този начин само k редове ще трябва да са налични по това време.