Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

УДК 681.3.21

ЧЕКОТУН Костянтин Михайлович

КОРЕЛЯЦІЙНІ МЕТОДИ ОБЧИСЛЕННЯ ГЕОМЕТРИЧНИХ

І ТОПОЛОГІЧНИХ ОЗНАК ЗОБРАЖЕНЬ

01.05.02 - математичне моделювання та обчислювальні методи

Автореферат дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ 1999

Дисертацією є рукопис.

Робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України.

Науковий керівник: доктор фізико-математичних наук, професор

КИРИЧЕНКО Микола Федорович,

Інститут кібернетики

ім. В.М. Глушкова НАН України,

провідний науковий співробітник

Офіційні опоненти: доктор фізико-математичних наук, професор

КНОПОВ Павло Соломонович,

Інститут кібернетики

ім. В.М. Глушкова НАН України,

завідувач відділу,

кандидат фізико-математичних наук, професор

ДОНЧЕНКО Володимир Степанович,

Київський університет ім. Тараса Шевченка,

завідувач кафедри.

Провідна установа : Інститут космічних досліджень НАН України та

НКА України, відділ космічних інформаційних

технологій та систем.

Захист відбудеться "28" травня 1999 р. о 11 год. на засіданні спеціалізованої вченої ради

Д 26.194.02 при Інституті кібернетики

ім. В.М. Глушкова НАН України

за адресою: 252650, МСП, Київ 22, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розісланий "27" квітня 1999 р.

Учений секретар

спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Стрімке зростання актуальності розпізнавання зображень у першу чергу пов'язане з тим, що високопродуктивні комп'ютери і засоби введення зображень стали доступними масовому споживачеві. У цій галузі вже існують численні продукти: від автоматичного введення текстів (OCR), класифікації клітин у медичних дослідженнях і до зору роботів на складальному виробництві.

Обробці і розпізнаванню зображень було присвячено роботи Р. Дуди, П. Харта, У. Претта, Б.К.П. Хорна, К. Фу, К. Фукунаги, Г.А. Івахненка, В.І. Васильєва, М.Ф. Кириченка, М.І. Шлезінгера, Т.К. Вінцюка, В.К. Задираки, Б.П. Русина, В.В. Грицика, С.В. Гупала, В.М. Кийка, У. Гренандера, В.Н. Вапника, А.Я. Червоненкіса, Е.А. Патрика та ін. У цих працях та іншими авторами створено формальні теорії класифікації образів за обчисленими ознаками. Разом з тим, етап вибору ознак, які б достатньо описували заданий клас зображень, досі залишається не формалізованим.

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

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

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

Зв'язок роботи з науковими програмами. Робота виконувалась в науково-дослідному проекті Міністерства України у справах науки і технологій № 06.02/01717 "Програмно-алгоритмічне та математичне забезпечення дослідження екологічного стану суттєво неоднорідних грунтових середовищ".

Наукова новизна. Властивості, які характеризують зображення в напрямку, систематизовано з точки зору використання їх як ознак. Вперше побудовано дискретні еквіваленти формул для обчислення характеристик на основі властивостей функціонала типу автокореляційних перетворень від функції освітленості. Здійснено розпаралелювання одержаних алгоритмів. Узагальнено поняття затоки області і вперше одержано структурний опис неопуклих областей через затоки вищих порядків. Вперше побудовано паралельний алгоритм виділення заток області.

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

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

Апробація результатів роботи. Результати досліджень, що включені до дисертації, доповідались на Третій всеукраїнській міжнародній конференції "Оброблення сигналів і зображень та розпізнавання образів" (УкрОбраз 96), наукових семінарах Інституту кібернетики ім. В.М. Глушкова НАН України (1999 р.).

Публікації. За матеріалами дисертації опубліковано чотири наукові праці, у тому числі три статті у фахових виданнях.

Особистий внесок дисертанта в роботах, виконаних у співавторстві. В роботі [1] автор дисертації одержав дискретний еквівалент виявлення геометро-топологічних ознак зображень з оцінкою похибок, що виникають за рахунок дискретизації.

Структура та обсяг дисертації. Дисертаційна робота складається із вступу, трьох розділів, висновків та списку літератури. Загальний обсяг роботи складає 136 сторінок. Текст дисертації містить 111 рисунків та 26 таблиць. Бібліографія містить 157 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі досліджуються властивості зображення в напрямку.

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

Вводиться функція , яка дорівнює кількості таких відрізків [A, B] прямої , що

, (1)

, (2)

, , (3)

, (4)

. (5)

Іншими словами, вона дорівнює кількості “опуклих підобластей”, які перетинає пряма (рис. 1).

Рис. 1

Вигляд функції проілюстровано на рис. 2.

Рис. 2.

Функція обчислюється на основі теореми 1, доведеної М.Ф. Кириченком.

Теорема 1. Якщо задана на числовій осі функція неперервна і диференційовна, крім скінченної кількості точок , в яких вона зазнає розривів першого роду (рис. 3), то

,

де ,

,

.

Рис. 3.

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

Вектором задається напрямок і дається означення різних видів порушень опуклості "в напрямку". Ці означення дещо модифіковані порівняно з працями Кириченка М.Ф., Лепехи П.П., Куценка А.А.

Нехай - багатозв’язна область, - її межа, де - зовнішній контур, - внутрішні.

Позначимо через множину всіх відрізків, паралельних до

Означення 1. Область - опукла в напрямку , якщо існує відрізок і .

Нехай- множина всіх таких відрізків , що

,.

Запишемо множину у вигляді об'єднання

,

де множини мають такі властивості:

- опукла в напрямку , (6)

: . (7)

Означення 2. Множиною заток області в напрямку називається

,

така, що задовольняють умови (6)-(7) і не існує іншої множини , що відповідає зазначеним умовам і при цьому .

Множина називається затокою області в напрямку .

На рис. 4 затоки в напрямку заштриховані.

Рис. 4.

Означення 3. Отвором називається множина відрізків , таких, що

На рис. 5 отвір заштрихований.

Рис. 5.

Аналогічно до затоки області в напрямку вводиться поняття затоки отвору в напрямку. На рис. 6 затока отвору заштрихована.

Рис. 6.

Даються означення характеристик (“узагальнена ширина”, “абсолютна ширина”, “кількість опуклостей”, "кількість крайніх заток") неопуклої області в напрямку і формули для їх обчислення.

Наступну суму називаємо узагальненою шириною зображення в напрямку :

, (8)

де проекція області D на пряму , перпендикулярну до , проекція і-ої затоки; проекція j-го отвору; проекція

і-ої затоки j-го отвору; - кількість заток; - кількість отворів;

- кількість заток - го отвору. На рис. 7 показано елементи, з яких складається узагальнена ширина.

Рис. 7.

Узагальнена ширина обчислюється за формулою (М.Ф. Кириченка)

, (9)

де . (10)

Абсолютною шириною області в напрямку називаємо проекцію області на пряму, перпендикулярну до .

Обчислюється абсолютна ширина за формулою (М.Ф. Кириченка):

, (11)

де ,

.

Справедлива наступна теорема.

Теорема 2. Якщо зовнішній і внутрішні контури області опуклі, то кількість внутрішніх контурів

,

де , (12)

- кількість внутрішніх контурів, для будь-якого , крім напрямків , де .

Кількістю опуклостей області в напрямку називаємо

,

де - кількість заток, - кількість отворів, - кількість заток -го отвору.

У напрямку є крайня затока, якщо серед таких відрізків , що

, ,

є такий, що вся область D лежить по один бік від цього відрізка. На рис.8 є крайні затоки в напрямках та в протилежних до них напрямках.

Рис. 8.

Кількість крайніх заток в напрямку обчислюється за формулою (М.Ф. Кириченка):

. (13)

Таким чином, введені характеристики обчислюються через формули (9), (11), (13). Відповідні функції пов'язані між собою співвідношеннями:

,

при фіксованих і

,

,

де - функціонал, який для одновимірної функції , що виникає при фіксованих і , дорівнює , де - кількість “опуклих підобластей”, які перетинає пряма ().

Дискретним відповідником можна вважати

,

якщо задані значення в точках сітки:

, , - крок сітки.

Доведено, що похибка обчислення має вигляд

,

де M - таке число, що при .

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

Як відомо, головним показником ефективності розпаралелювання алгоритму є коефіцієнт прискорення:

,

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

Показано, що для алгоритму обчислення узагальненої ширини

,

де - кількість напрямків, у яких обчислюється характеристика, - кількість відрізків в одному напрямку, - кількість точок в одному відрізку, - середній час виконання арифметичної операції на стандартному процесорі, - час виконання елементарної операції паралельного алгоритму, а для обчислення кількості опуклостей і абсолютної ширини:

.

Другий розділ присвячений затокам (не "в напрямку") двовимірних областей. Наступні означення узагальнюють поняття затоки, яке є, наприклад, у відомій монографії Дуди Р., Харта П. і вводять поняття заток вищих порядків.

Нехай D - однозв’язна область на площині,- її опукла оболонка (опуклою оболонкою області D називається найменша опукла область, що містить D). Подамо “дефіцит опуклості” (де знак "\" позначає різницю множин, тобто ) у вигляді об’єднання ,

де області , , мають такі властивості:

1)

1)

1)

Означення 4. Множина називається затокою області D.

Означення 5. Затокою n-го порядку, , називається затока затоки (n-1)-го порядку. На рис. 9 затоки першого порядку заштриховані одинарною, а другого - подвійною штриховкою.

Рис. 9.

Описом області називаємо кожен з наступних виразів, які є композицією опуклих областей:

, (14)

, (15)

, ..., (16)

,..., (17)

Тобто для області на рис. 9 описи будуть виглядати так:

Рис. 10.

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

Відстанню між областями називаємо площу різниці:

, (18)

де - площа області.

Теорема 3. Якщо відстань між областями задана формулою (18), то для області D та послідовності її описів (14) - (17) виконується:

, (19)

, (20)

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

Побудовано паралельний алгоритм виділення заток. На його вхід надходить бінарний масив розмірності , де точкам області відповідає 1, а точкам фону - 0. Результат його роботи - декілька масивів тієї ж розмірності, у кожному з яких записана окрема затока, тобто точкам затоки відповідає 1, а інші елементи дорівнюють нулю (рис. 11).

Рис. 11.

Алгоритм складається з таких основних блоків.

1. Побудова кришечок (кришечкою затоки називаємо відрізок , який належить затоці і вся область лежить по один бік від прямої (Рис. 12)).

Рис. 12.

Тут використовується алгоритм виділення крайніх заток в напрямку з першого розділу. Роботу цього блоку показано на рис. 13. Причому різними числами позначені кришечки різних заток.

Рис. 13.

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

Рис. 14.

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

Крок (3) повторюється якусь наперед визначену кількість разів. Ця кількість залежить від складності областей, які планується обробляти. Наприклад, для області на рис. 14 достатньо трьох кроків.

4. Розділення заток по окремих масивах.

У дисертаційній роботі алгоритм розписано детально в термінах елементарних операцій.

Показано, що ефективність розпаралелювання

,

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

У третьому розділі, щоб оцінити, наскільки введені характеристики можуть розділяти задані класи зображень, розглядається простий приклад: написані від руки цифри "0" . . . "9".

Розглядається три варіанти використання узагальненої ширини і абсолютної ширини як векторів ознак:

1) ;

2) ;

3) (у наших експериментах ) та дві відстані в цих просторах. Нехай

, ,

і оцінюється якість класифікації за методом найближчого сусіда.

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

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

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

Основні результати дисертації:

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

2. Побудовано дискретні еквіваленти формул для обчислення характеристик зображення в напрямку.

3. Здійснено розпаралелювання одержаних алгоритмів для архітектури типу багатошарових нейромереж.

4. Введено поняття затоки k-го порядку неопуклої області. Запропоновано структурний опис області через композицію заток.

5. Побудовано паралельний алгоритм виділення заток.

6. На основі затокової структури і ознак у напрямку розроблено алгоритм розпізнавання написаних від руки цифр.

Основні положення дисертації опубліковані в таких працях:

1. Кириченко Н.Ф., Куценко А.А., Чекотун К.М. Выделение геометро - топологических признаков изображений методом автокорреляционных преобразований // Проблемы управления и информатики. - 1997. - №1. - С. 138-152.

2. Чекотун К.М. Метод паралельного обчислення геометро-топологічних властивостей зображень // Математические машины и системы. - 1998. - №1. - С. 95-104.

3. Чекотун К.М. Дискретна реалізація методів виділення ознак зображень через автокореляційні перетворення // Математические методы в компьютерных системах. - Киев: Ин-т кибернетики им. В.М.Глушкова НАН Украины, 1996. - С. 75-79.

ЧЕКОТУН К.М. Кореляційні методи обчислення геометричних і топологічних ознак зображень.- Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. - Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 1999.

Дисертація присвячена розвитку математичних засобів виявлення ознак зображень на основі властивостей функціонала типу автокореляційних перетворень від функції освітленості. Побудовано дискретні еквіваленти формул для обчислення характеристик зображення в напрямку. Здійснено розпаралелювання одержаних алгоритмів. Узагальнено поняття затоки області і одержано структурний опис неопуклих областей через затоки вищих порядків. Побудовано паралельний алгоритм виділення заток області.

Ключові слова: автокореляція, неопукла область, паралельний алгоритм, затока області, ознаки зображення.

ЧЕКОТУН К.М. Корреляционные методы вычисления геометрических и топологических признаков изображений.- Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 1999.

Диссертация посвящена развитию математических средств выявления признаков изображений на основе свойств функционала типа автокорреляционных преобразований от функции освещенности. Построены дискретные эквиваленты формул для вычисления характеристик изображения в направлении. Осуществлено распараллеливание полученных алгоритмов. Обобщено понятие залива области и получено структурное описание невыпуклых областей через заливы высших порядков. Построен параллельный алгоритм выделения заливов области.

Ключевые слова: автокорреляция, невыпуклая область, параллельный алгоритм, залив области, признаки изображения.

CHEKOTUN K.M. Correlation methods for calculating geometrical and topological features of image.- Manuscript.

The dissertation for degree of Candidate of physical-mathematical Science by speciality 01.05.02 - mathematical simulation and calculus methods. - NAS of Ukraine V.M. Glushkov Institute of Cybernetics, Kyiv, 1998.

Mathematical methods for image feature extraction based on properties of autocorrelation of illumination function are developed in the thesis.

Let is multiconnected region, - its boundary, where - exterior contour, - interior. The direction is defined by vector . The definitions of different types of convexity distortion "in direction" are given: gulfs of region, holes and gulfs of hole:

Formulae for calculating characteristics of non-convex region in direction (“generalized width”, “absolute width”, “number of convexities”, "number of gulfs") are presented. If an image is defined by function , that is continuous and differentiable within the bounds of a region, where particular derivatives are limited, has break on boundary, and its value is equal to , is equal to 0 outside the region, then generalized width , that is a sum of region projection and the projections of the elements mentioned above, can be calculated by formula

,

where .

If interior and exterior contours of region are convex, then number of interior contours is , where ,,

for any , except the directions , where , functional is of function , that appears when and are fixed.

Discrete implementation of can be

, if values in grid points are defined: , , - grid step. The error of such a discretization have been found.

The parallel algorithms for calculating image characteristics in direction are built for multilayer neural-like architecture. Speed-up coefficients are estimated.

Concept of gulf is developed in Chapter 2. Higher order gulfs are defined. On the picture the gulfs of order 1 are single-hatched and the gulfs of order 2 are double-hatched.

The following expression are regarded as a region descriptions. They are compositions of convex envelops of respective gulfs.

, , .

It is proved, that the higher order gulfs is included in description, the more precise is description. The parallel algorithm for gulf extraction have been built.

Recognition of handprinted characters is proposed as a test problem.

Keywords: autocorrelation, non-convex region, parallel algorithm, gulf of region, image feature.