Този раздел обсъжда методи за "изтъняване" на даден 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 редове ще трябва да са налични по това време.

б. Алтернативни схеми за отслабване

Понякога могат да се използват опростени подходи за изтъняване. Например, ако S има по същество постоянна дебелина навсякъде (виж раздел 3.2г), да речем 2 k + 1, той може да бъде изтънен (поне значително), като го свие k пъти. Имайте предвид обаче, че резултатът от скелета може понякога да е дебел или счупен. Процесът на изтъняване, описан в (ще третира S с различна дебелина. Друг метод [32], който може да се използва, ако S е дъга с постоянна дебелина, е да се стартират два процеса на проследяване на ръбовете в единия край на S, който преминава срещу противоположните страни ( Аналогично, ако S е затворена крива с постоянна дебелина, ние инициираме два процеса на проследяване на ръба в точки, които са само дебелината на S един от друг, който преминава през двата ръба на S.) Ако разстоянието между последователите на ръбовете стане по-голяма от дебелината, спираме едната от тях, докато другата я достигне; по този начин те винаги остават приблизително една до друга. Средната точка на отсечката на линията, която се присъединява към последователите на ръбовете, проследява скелет на S .


Фиг. 14 Изтъняване. а) S оригинал; (б) - (д) резултати от последователно изтъняване от север, юг, изток и запад, третиране на S като 8-свързани. В следващата северна стъпка, горната точка (e) ще бъде изтрита; на следващия южен проход, точката, най-отдалечена от най-ниската; а в следващия западен проход, точките, най-отдалечени отляво на върха. Няма да има други промени. Забележете как ъгълът в горния ляв ъгъл се свива до същата височина като диагоналната линия горе вдясно. (b ’) - (e’) Аналогични резултати, третиращи S като 4-свързани и определящи крайните точки, които имат само един 4-съсед в S. Още една точка ще бъде премахната в следващата северна стъпка; няма да има повече промени.

Разреждащите алгоритми могат да бъдат дефинирани за многозначни изображения по различни начини. Приближение [15] е да обобщим дефиницията на проста точка, както следва: дефинираме силата на пътя P 1. P n като минимална стойност на която и да е точка от пътя и степента на свързване на P и Q като максимална сила на всеки път от P до Q, ние казваме, че P е "проста", ако я замести с минималната от нейната съседите не намалява степента на връзка на която и да е двойка точки в рамките на 8-квартала. Може да се провери, че това обобщава двузначните определения, дадени в (а). Тогава изтъняването се определя като специализирана локална минимална операция: многократно заменяме точките с минимума на техните съседи, стига те да са прости и да имат повече от един съсед с по-висока стойност (това обобщава условието, че изолираните и крайните точки не са премахнати). Във всяка итерация правим това само от едната страна, т.е. правим го само до точките, които имат съсед с по-ниска стойност от определена страна (север, юг.). Резултатите от прилагането на този процес към набор от изображения са показани на фиг. 15.

Изходът на операторите за откриване на граници обикновено е дебел. Може да се изтъни чрез потискане на не-максимумите по посока на градиента във всяка точка; това изключва всичко, освен най-стръмната гранична стойност при всяко гранично сечение, но не позволява точките по границата да се конкурират помежду си. Друга възможност е да увеличите или намалите стойността на всяка точка пропорционално в зависимост от това колко голяма или малка е тя по отношение на съседа си по посока на градиента. Това води до нарастване на максималната стойност във всяко напречно сечение на лимита за сметка на по-ниските стойности, така че в крайна сметка тя абсорбира всички отговори от това напречно сечение [17].


Фиг. 15 Пример за изтъняване на сивата скала.

° С. Резултатът от загуба на тегло

В идеалния случай казваме, че подмножество на A от множеството на T е проста цифрова дъга, ако е свързан компонент от T, всяка точка от който има точно два съседа в T, с изключение на двете крайни точки, които имат по един съсед. Имайте предвид, че това са две дефиниции в едно, в зависимост от това дали имаме предвид 4- или 8-съседи. Също така имайте предвид, че дъгата не може да се разклонява, да се пресича или дори да се докосва, в противен случай тя може да съдържа точки, които имат повече от два съседи в S. Една проста затворена цифрова крива е свързан компонент C от T, всяка точка от който има точно два съседа в T; тук също имаме две определения. Имайте предвид, че ръбът не винаги е обикновена затворена крива, тъй като може да премине през някои точки два пъти.

Целта на изтъняването на S е да се получи Т, което е обединение на такива дъги и криви, може би след като са били премахнати няколко пресечени или разклонени точки - т.е. точки, които имат повече от двама съседи. Имайте предвид, че такива точки често се появяват в клъстери; например, нека помислим

1 J J J 1 и J J

където сме посочили точките на присъединяване от J's. Ако много клонове на криви и пресичания се движат много близо един до друг, ще бъде трудно да се идентифицират и класифицират отделните стави. По-тънкият S може също да има вътрешни точки; 8-свързан пример е

където всяка точка на ръба е или крайна точка, или не е проста, така че изтъняването няма ефект върху нея. Резултатите от загубата на тегло зависят от ориентацията; например, когато 8-отслабваме

1 1 1 1 1 1 1 1 1

но когато 8-ние напредваме

1 1 1 1 1 1 1 1 1 1 1

(При 4-изтъняване никой от тези модели не се променя)

След като точките, които имат повече от двама съседи, са премахнати, лесно е да се изгради кодът на низовете на дъга, движеща се от съсед на съсед, започвайки от едната крайна точка и завършвайки в другата; или рязка крива, започваща от произволна начална точка и движеща се в една посока, докато отново се достигне началната точка.

Изтъняването понякога създава "остри" скелети, особено когато S има "космати" ръбове, които съдържат много крайни точки, или когато крайните точки излизат преждевременно в процеса на изтъняване; това е особено оценено във версията на алгоритъма с 4 връзки. Един от начините [56] за откриване на неподходящ скелетен клон е да се вземат предвид разстоянията на точките на клона от Љ или, еквивалентно, итерациите, в които те се превръщат в точки на ръба. В истински скелетен клон тези разстояния трябва да бъдат приблизително постоянни, но в точков клон те трябва да се увеличават непрекъснато, докато се движим от края на точката.