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

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

1.Вступ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1 Рис. 2

Табл. 1                 

Околиця         

Число контрольних точок         

Ваговий поріг         

R             

Малюнок 1         

Квадрат 5 * 5         

6         

0.56         

16.55%             

Малюнок 2         

Квадрат 5 * 5         

14         

0.52         

1.38%     

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

Рис. 3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Hecker Y.C., Bolle R.M. 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 р.