Про один спосіб векторного і аналітичного подання контуру зображення

О.М. Каркищенко, А.Є. Лепський, А.В. Безуглов

1.Вступ

Попередня обробка оцифрованого зображення об'єкта включає виділення, згладжування та векторизацію контуру. Під векторизацією будемо розуміти процес зіставлення контуру послідовності скінченновимірних векторів, що характеризують зображення об'єкта. Всі способи векторизации можна розділити на векторизацію по контрольних точках і покрокову векторизацію. До останніх відноситься широкий клас методів, що використовують так зване перетворення Хау (див. [1], [2]). В якості контрольних точок можуть бути кутові точки [3], точки екстремуму функції кривизни [4], точки перегину та ін

У статті розглянуто простий алгоритм виділення контрольних точок і побудови інваріантного векторного представлення зображення об'єкта. Крім того, запропоновано спосіб функціоналізації векторного представлення зображення. Результатом функціоналізації є деяка функція зображення, за якою частково або повністю може бути відновлено векторне подання. У ряді завдань, наприклад, при розпізнаванні симетрій, аналіз функції зображення дозволяє отримати додаткову інформацію про зображення. Обговорюються питання стійкості функції зображення до зміни центру мас векторного представлення, до появи нової контрольної точки і т.д.

2. Алгоритм простежування контуру і виявлення контрольних точок

Розглянемо дискретне бінарне зображення на тлі . Вважаємо, що , Де - Контур зображення, - Внутрішність зображення , - Може, зокрема, містити інші контури. Крім того, вважаємо, що зображення є згладженим і не містить висячих точок. Введемо матрицю Будемо розглядати наступні параметри: , 0, - початковий поріг відбору контрольних точок; , > 0 - зміна порогу відбору контрольних точок; , > 0 - розмір околиці контрольної точки. Нам буде потрібно обчислювати відстань між елементами, які задають зображення і фон, тобто необхідно ввести деяку метрику на дискретній площині. В якості метрики можна використовувати , , та ін Алгоритм, що дозволяє простежити контур зображення і сформувати масив контрольних точок, складається з наступних кроків.

Переглядаємо елементи матриці зліва - направо, зверху - вниз і знаходимо перший елемент . Вважаємо ,

. Тут - Номер відслідковується точки контуру; - Точка початку обходу навколо останньої відслідковується точки контуру з метою відстеження поточної точки.

Розглянемо -Околиця точки . Підрахуємо кількість точок , Що належать фону і не належать йому: , , Де - Потужність (кількість точок) околиці .

Обчислюємо вага -Ї точки: .

Якщо , То - Контрольну точку. У цьому випадку додаємо у вектор , - У вектор , - У вектор .

Продовжуємо обхід контуру. Нехай - Елементи матриці , Розташовані навколо елемента за годинниковою стрілкою, причому . Здійснюємо пошук першого ненульового матричного елемента з оточуючих його елементів . Якщо такий елемент, то вважаємо і .

Якщо , То обхід контуру зображення закінчився і переходимо до пункту 80., В іншому випадку - до пункту 30.

Нехай - Довжина вектора (Число контрольних точок). Якщо (Тобто число контрольних точок невелика), то і переходимо до пункту 10 (здійснюємо новий обхід контуру). Якщо , То масив контрольних точок побудований.

Даний алгоритм був реалізований і апробований у системі Borland Delphi.

На рис. 1 і 2 представлені результати векторизации бінарного зображення. Результати роботи програми зведені в таблицю 1.

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

де - Символ симетричної різниці множин.

Рис. 1 Рис. 2

Табл. 1

На рис. 3 наведені графіки зміни кількості контрольних точок та їх приросту в залежності від обраного порога h.

Рис. 3.

Приріст точок кількісно дорівнює зменшенню кількості контрольних точок при збільшеннях вагового порогу. Оптимальне порогове значення слід вибирати з інтервалу від (h?, H??), Де h? - Значення вагового порогу, відповідне максимуму приросту кількості контрольних точок, h-значення, починаючи з якого число контрольних точок дорівнює нулю. Слід зазначити, що в літературі є вказівка ​​на те, що оптимальним для розпізнавання зображень вважається одержання приблизно 40 контрольних точок [4].

3. Формування векторного представлення контуру

Після виконання алгоритму простежування контуру і виявлення контрольних точок є три вектора: , , - Абсциси, ординати і ваги контрольних точок відповідно. Трійку назвемо скелетом зображення . Далі обчислимо:

центр мас контрольних точок , Де , ;

довжини радіус-векторів контрольних точок щодо центру мас: , , А також довжини нормованих радіус-векторів , Де ;

косинуси кутів між сусідніми радіус-векторами контрольних точок: , (Рахуючи , )

З обчислених компонент складаємо вектори . Вектори будуть інваріантні щодо зсуву, повороту і гомотетии зображення щодо центру мас (якщо «замкнути» ці вектори, вважаючи ). Четвірку будемо називати нормованим векторним представленням зображення . Розглянемо питання про стійкість центру мас зображення до додавання нової контрольної точки.

Теорема 1. Якщо до нормованого векторного поданням додати контрольну точку з вагою , То для евклідового відстані між новим центром тяжіння і старим справедлива оцінка , Де - Точки скелета зображення . Зокрема, якщо , То .

Іншими словами, якщо число контрольних точок достатньо велика, а вага нової точки невеликий, то центр симетрії зміститься незначно.

4.Функції зображення

Замість аналізу векторного представлення в ряді завдань (одна з яких буде розглянута в наступному розділі) зручніше вивчати властивості деякої функції, яка зв'язує вектори з подання . Наприклад, розглянемо функцію ,
де ( ). Цю функцію можна розглядати як узагальнення дескриптора Фур'є [5]. По функції коефіцієнти (А, отже, і ) Визначатимуться однозначно, як коефіцієнти часткової суми ряду Фур'є. За дискретним значенням цієї функції , Коефіцієнти можна знайти з лінійної системи , , Якщо значення , , Такі, що визначник матриці відмінний від нуля, де , Де - Ціла частина числа. Безліч функцій зображення будемо розглядати разом з нормою . Наступна теорема свідчить про стійкість функції зображення до зміни ваг (і, отже, до зміни центру мас).

Теорема 2. Нехай і два скелети зображення такі, що . Тоді, якщо і відповідні цим скелетам функції зображення, то , Де .

Однак при додаванні нової контрольної точки навіть з невеликою вагою функція зображення, взагалі кажучи, може сильно змінитися, тому що вона не є інваріантної щодо зсуву векторів векторного представлення . Таким властивістю буде мати, наприклад, функція , Хоча коефіцієнти цієї функції вже не будуть однозначно відновлюватися за її значенням.

5.Распознаваніе симетрій

Зображення називається -Осесиметричним [6], якщо воно перекладається саму в себе після повороту на будь-який кут, кратний навколо свого центру мас. Симетрія є важливою в задачах розпізнавання характеристикою зображуваного об'єкта. Докладний огляд існуючих методів виявлення симетрій і визначення орієнтації об'єкта, у тому числі і за допомогою дескрипторів Фур'є, можна знайти в роботі [6]. Розпізнавати симетрію можна безпосередньо аналізуючи векторне представлення , Якщо воно досить точно відображає характер симетрії (не містить «зайвих» контрольних точок). Векторне представлення назвемо -Осесиметричним, якщо побудований з цього векторного поданням багатокутник буде -Осесиметричним. З іншого боку, для розпізнавання симетрії можна використовувати і функцію зображення . У цьому випадку краще перейти до комплексної формі запису функції зображення. Позначимо через , Де . Тоді і справедлива

Теорема 3. є -Осесиметричним векторним представленням зображення тоді і тільки тоді, коли знайдеться така , Що , де .

Це мультиплікативне властивість функції зображення можна використовувати для розпізнавання симетрій, а саме, якщо для заданого малого знайдуться такі і , Що , То можна вважати векторне подання -Осесиметричним.

Список літератури

Hecker YC, Bolle RM On geometric hashing and the generalized Hough transform, IEEE Trans. Syst., Man and Cybern. 24, N9, 1994, p.1328-1338.

Dufresne TE, Dhawan AP, Chord-tangent transformation for object recognition, Pattern Recogn. 28, N9, 1995, p.1321-1332.

Bolles R., Cain RA, Recognizing and locating partiavisible objects: The local-feature-focus method, Robot Vision A. Publ. Ed., 1984.

Liu HC, Srinath MD, Partial Shape Classification Using Contour Matching in Distance Transformer; IEEE Trans. Pattern Anal. and Mach. Intell, 12, N11, p.1072-1079.

Zahn CT, Roskies RS, Fourier descriptors for plane closed curves, IEEE Trans. Comput. C-21, March, 1972, p.269-281.

Pei SC, Liov LG, Automatic symmetry determination and normalization for rotationally symmetric 2D shapes and 3D solid objects, Pattern Recogn, 27, N9, 1994, p.1193-1208. послідовностей ".- Таганрог, вид. ТРТУ, 1996 р.