У цьому розділі розглядаються методи "витончення" даного S в групі дуг і кривих. Будемо вважати, що S повністю складається з видовжених частин, тому отримані дуги та криві є розумним наближенням до S (Розділ 1.5c). Для інших типів S результати схуднення не повинні бути особливо значущими. (Визначення подовження див. У розділі 3.4b). Результат схуднення S буде називатися скелетом S .

цифрової

MA розрідженого в будь-якому місці можна вважати скелетом, але він має дві вади. У місцях, де S розширено, його MA має товщину в дві точки, оскільки MA - це набір максимумів відстаней a Љ, як показано в розділі 2.1a. Крім того, як зазначається там, 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-компонент одиниць є 4-суміжним з Р; але P не є 4-простим, якщо його сусідство є

З іншого боку, P - 8-простий у третьому випадку, але не в перших двох випадках.

Неважко помітити, що видалення однієї точки з S не змінює властивостей з'єднання ні S, ні Љ; S - < P >має ті самі компоненти, що і S, за винятком того, що в одному з них зараз відсутня точка P, і Љ И < P >має ті самі компоненти, що і Љ, за винятком того, що зараз P є одним з них. Зверніть увагу, що ізольована точка (яка не має сусіда в S) не проста, і що кінцева точка (яка має рівно одного сусіда в S) автоматично проста.

Наш алгоритм стоншення тепер можна встановити наступним чином: Ми видаляємо всі крайові точки на заданій стороні S, якщо вони є простими, а не кінцевими точками. Ми будемо робити це послідовно з півночі, півдня, сходу, заходу, півночі. з S, поки більше не буде змін. Простий приклад роботи цього алгоритму показаний на рис. 14.

Видалення точок з країв заданої сторони S слід робити "паралельно", тобто умови видалення точки слід перевірити перед видаленням будь-якої іншої точки. (Припустимо, ми цього не робимо, а просто виконуємо видалення рядок за рядком. Коли ми стираємо точки північного краю, ми б видаляли шар за шаром зверху S, і отриманий скелет не був би симетричним; наприклад, якби S був прямокутник, після першої операції не залишиться нічого, крім нижнього рядка). Таким чином кожна ітерація алгоритму може виконуватися як проста паралельна операція багатопроцесорного комп'ютера.

Алгоритм може бути реалізований на звичайному комп'ютері, використовуючи відстеження зображень для кожної ітерації. У кожному рядку точки позначені для стирання, але вони не стираються, поки не буде позначено точки в наступному рядку. Ми можемо уникнути повторного сканування всього зображення, оперуючи рядками в послідовності 1; двадцять один; 3, 2, 1; . як у Розділі 2.1c. Після k кроків, де 2 k + 1 - це максимальна ширина S, подальшого стоншування на першому ряду не потрібно, тому від нього можна відмовитись; таким чином, на той момент потрібно мати лише k рядків.

b. Альтернативні схеми схуднення

Іноді можна використовувати спрощені підходи до проріджування. Наприклад, якщо S всюди має по суті постійну товщину (див. Розділ 3.2d), скажімо, 2 k + 1, його можна розріджувати (принаймні значно), скорочуючи в k разів. Однак зверніть увагу, що результат скелета може іноді бути товстим або зламаним. Процес витончення, описаний у (буде обробляти S різної товщини. Інший метод [32], який можна використовувати, якщо S є дугою постійної товщини, полягає у запуску двох процесів відстеження країв на одному кінці S, що проходить протилежні сторони ( Аналогічно, якщо S є замкненою кривою постійної товщини, ми ініціюємо два процеси відстеження ребер у точках, які просто товщиною S один від одного, перетинаючи два ребра S.) Якщо відстань між ребрами слідування стає більше ніж товщину, зупиняємо одну з них, доки інша не досягне її; таким чином, вони завжди залишаються приблизно поруч. Середина відрізка лінії, що приєднується до крайових послідовників, простежує скелет S .


Рис. 14 Витончення. (а) S оригінал; (b) - (e) результати послідовного стоншення з півночі, півдня, сходу та заходу, обробляючи S як 8-з'єднаний. На наступному північному етапі пункт вище (e) буде видалено; на наступному південному перевалі, крайна точка зліва від найнижчої; а на наступному західному переході точки, найбільш віддалені ліворуч від вершини. Інших змін не буде. Зверніть увагу, як кут у верхньому лівому куті зменшується до тієї самої висоти, що і діагональна лінія у верхньому правому куті. (b ’) - (e’) Аналогічні результати, розглядаючи S як 4-зв’язаний, та визначаючи кінцеві точки, які мають лише одного 4-сусіда в S. Ще одна точка буде усунена на наступному північному етапі; змін більше не буде.

Алгоритми стоншення можна визначити для багатозначних зображень різними способами. Наближення [15] полягає в узагальненні визначення простої точки таким чином: ми визначаємо силу шляху P 1. P n як мінімальне значення будь-якої точки на шляху, а ступінь зв'язку P і Q як максимальна сила будь-якого шляху від P до Q, ми говоримо, що P "простий", якщо замінити його на мінімальний його сусідів не зменшує ступінь зв'язку будь-якої пари точок в межах 8-околиць. Можна перевірити, що це узагальнює двозначні визначення, наведені в (а). Потім витончення визначається як спеціалізована локальна мінімальна операція: ми неодноразово замінюємо точки мінімумом їхніх сусідів, за умови, що вони прості і мають більше одного сусіда з вищим значенням (це узагальнює умову, що ізольовані та кінцеві точки не є видалено). У кожній ітерації ми робимо це лише з одного боку, тобто ми робимо це лише в точках, які мають сусіда з меншим значенням на певній стороні (північ, південь.). Результати застосування цього процесу до набору зображень показані на рис. 15.

Вихід операторів виявлення обмежень, як правило, товстий. Його можна проріджувати, придушуючи не максимуми у напрямку градієнта в кожній точці; це виключає все, крім найвищого граничного значення в кожному поперечному перерізі межі, але не дозволяє точкам уздовж межі конкурувати між собою. Інша можливість полягає у збільшенні або зменшенні значення кожної точки пропорційно залежно від того, наскільки вона велика чи мала по відношенню до свого сусіда в напрямку градієнта. Це призводить до зростання максимального значення в кожному поперечному перерізі межі за рахунок нижчих значень, тому врешті-решт поглинає всі відповіді цього перерізу [17].


Рис. 15 Приклад витончення сірої шкали.

c. Результат схуднення

В ідеалі ми говоримо, що підмножина A набору T є простою цифровою дугою, якщо це зв’язана складова T, кожна точка якої має рівно два сусіди в T, за винятком двох кінцевих точок, які мають по одному сусіду. Зверніть увагу, що це два визначення в одному, залежно від того, чи маємо на увазі 4- чи 8-сусідів. Також зауважте, що дуга не може розгалужуватися, перехрещуватися і навіть не торкатися, інакше вона може містити точки, які мають більше двох сусідів у S. Проста замкнута цифрова крива - це зв’язана складова C Т, кожна точка якої має рівно двох сусідів у Т; тут ми також маємо два визначення. Зверніть увагу, що ребро не завжди є простою замкнутою кривою, оскільки воно може проходити через деякі точки двічі.

Метою стоншення S є отримання Т, що є об'єднанням таких дуг і кривих, можливо, після того, як було ліквідовано кілька пройдених або розгалужених точок - тобто точок, які мають більше двох сусідів. Зауважте, що такі точки часто з’являються в кластерах; наприклад, давайте розглянемо

1 J J J 1 і J J

де ми вказали пункти об'єднання за допомогою J. Якщо багато гілок кривих і перетинів проходять дуже тісно між собою, буде важко визначити та класифікувати окремі стики. Тонкіший S також може мати внутрішні точки; 8-підключеним прикладом є

в якій кожна крайова точка є або кінцевою, або непростою, так що витончення не впливає на неї. Результати схуднення залежать від орієнтації; наприклад, коли 8-ми худнемо

1 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] виявити невідповідну гілку скелета є врахування відстані точок відгалуження від Љ або, що еквівалентно, ітерацій, в яких вони стають крайовими точками. У реальній гілці скелета ці відстані повинні бути приблизно постійними, але в точковій гілці вони повинні постійно збільшуватися, коли ми рухаємось від кінця точки.