Варіаційний підхід до згладжування та визначення характерних
точок чорно-білих зображень
А.Н. Каркіщенко, А.Г.
Броневіч, Н.С. Зюзерова
1.
Основні визначення
Чорно-біле зображення,
збережене в ЕОМ у цифровій формі, можна описати за допомогою функції 
від двох змінних.
Пара цілих чисел визначає координати
елемента зображення (ЕІ), а значення функції характеризує яскравість
даного ЕІ. Оскільки цифрова форма представлення зображення - це лише
апроксимація реального зображення, яка виходить як квантуванням по
значеннями координат елементів зображення, так і за значеннями яскравості, введемо в
розгляд функцію 
від дійсних
аргументів 
і 
, яку будемо називати функцією яскравості реального зображення.
Будемо вважати, що
функції і 
пов'язані між собою
співвідношенням 
.
Тут? - Випадкова складова, що враховує
оптичні перешкоди; функція 
визначає згладжують
властивості оптичної системи і, як правило, апроксимується щільністю
сферичного нормального розподілу
= 
.
Можна отримати більше
складну формулу, якщо враховувати квантування значень функції .
Функція , що описує реальні зображення, може мати достатньо довільний
характер: на реальному зображенні можуть бути різні перепади яскравості, що буде
порушувати гладкість , функція 
може мати різне розташування точок мінімуму і максимуму
і пр.
У зв'язку з цим виникає
завдання вибору найбільш оптимального опису функції яскравості зображення.
Слід зазначити, що традиційні підходи, засновані на двовимірному
перетворення Фур'є 
, на апроксимації сплайнами 
, можуть не привести до бажаного результату. При обробці
зображень, як показав досвід багатьох досліджень, необхідно дотримуватися
ідеології штучного інтелекту: перетворення зображень повинні бути
зрозумілими людині в тій мірі, щоб він розпізнавав послідовність
одержуваних абстрагованих зображень і міг маніпулювати ними; дану інтелектуальну
діяльність людини повинна відтворювати система аналізу зображень.
Вивчення питання про
сприйнятті зображення людиною дає підставу говорити про те, що найбільш
інформативними ознаками при розпізнаванні об'єктів є контури - лінії,
уздовж яких спостерігаються значні перепади яскравості зображення.
Мовою математики --
це криві, що складаються з особливих точок функції , де функція не диференційовних або
має великий модуль градієнта.
У статті розглядається
варіаційний підхід до вибору аналітичного опису функції яскравості . Його ідея полягає в наступному: оскільки точні значення
функції невідомі, то в якості оптимального аналітичного
опису функції яскравості слід вибирати найбільш просте з усіх можливих. З
точки зору інформативності це буде найбільш гладка функція, що має
найменше число особливих точок і невеликі значення модуля градієнта. Для
визначення гладкості функції яскравості вводиться функціонал. Це дозволяє
сформулювати варіаційної задачі знаходження найбільш гладкої функції з
множини всіх можливих. При практичної реалізації даного методу приватні
похідні функції яскравості апроксимуються кінцевими речами на сітці
зображення, що дозволяє перейти до кінцевої оптимізаційної задачі і вирішувати
її методом градієнта.
У процесі рішення
оптимізаційної завдання автоматично обчислюються координати точок контурів (в
даних точках функція не задовольняє необхідним критеріям гладкості), а також
координати інших особливих точок, що дозволяють оптимальним чином кодувати
зображення.
2.
Безперервна модель для гладкої функції яскравості
Нехай 
- оцінка дійсної функції яскравості 
, яка схильна до згладжуючим перетворення оптичної
системи. Оскільки помилки при одержанні оцінки 
, як правило, носять інтервальний характер, можна з
достатньою впевненістю вважати, що:
| 
- 
| 
?.
Тут? - Область визначення функції . Наведене умову, що значення функції і 
Далі ступінь гладкості
функції в точці 
можна оцінити за
величиною квадрата модуля градієнта:
.
З урахуванням цього можна
ввести в розгляд наступний функціонал за критерієм гладкості:
.
3.
Дискретна модель для вибору найбільш гладкої функції яскравості
Будемо вважати, що
значення функції відомі тільки в
цілочисельних точках , 
= 
, 
= 
. Тоді необхідно
знайти значення найбільш «гладкою» функції 
у вузлах сітки 
, що задовольняє умові:
| 
- 
| ?, 
= 1,2, ... , N1, 
= 1,2, ... , 
. (1)
Неважко отримати
дискретний аналог 
(
) функціонала гладкості 
, якщо апроксимувати квадрат модуля градієнта кінцевими
дивовижними речами:
| 
-- 
, 
| 
? 
- 
,
| 
.
Замінюючи
інтегрування кінцевою сумою,
отримуємо:
. (2)
Далі необхідно вирішити
задачу на умовний екстремум - мінімізувати функціонал 
за умови (1 ). Це можна зробити методом парних
градієнтів.
Мінімізація функціоналу за допомогою методу сполучених градієнтів
Неважко помітити, що
функціонал можна розглядати
як векторну функцію від аргументу 
. Тому, враховуючи умову (1), функціонал 
необхідно мінімізувати
в області
.
Розглянемо практичну
реалізацію методу сполучених градієнтів.
Як початковий
наближення вибирається оригінал чорно-біле зображення, тобто 
= 
.
Нехай на кроці ми маємо
згладжені зображення 
. Тоді напрямок 
мінімізації
у методі сполучення градієнтів слід вибрати з умови:
+ 
. (3)
Таким чином,
напрям мінімізації залежить від попереднього
напрями мінімізації 
. Ми вважаємо, що 
= 0. При вич?? сленіі напрямки слід
враховувати, що точка може лежати на
кордоні області 
, тобто для деяких значень і 
буде виконуватися
рівність
= 
? (знак «+» або «-»).
Тоді координату вектора 
слід обнулити, якщо
мінімізація вздовж цього напрямку в будь-якому випадку призводить до переміщення точки
за межі області допустимих значень? .
При програмної
реалізації положення точки 
зручно закодувати:
Тоді координату слід обнулити, якщо
виконується умова:
> 0.
Після того, як обчислено напрям
мінімізації , функціонал 
мінімізується уздовж
даного напрямку. Для цього необхідно вирішити оптимізаційних задач
щодо параметра 
. Враховуючи, що 
- це поліном другого
мірою від багатьох змінних (позитивно визначена квадратична форма),
розкриваючи дужки і приводячи подібні, отримаємо многочлен другого ступеня
щодо?:
.
Неважко помітити, що
остання оптимізаційна завдання має явне рішення:
= - 
.
З логіки пропонованого
методу випливає, що значення повинно бути
позитивним. Згладжені зображення на наступному кроці ітераційне визначаємо
за формулою:
.
(4)
Однак безпосередньо
формулу (4) використовувати не можна, оскільки точка 
може потрапити за межі
області допустимих значень. З урахуванням
цього слід коректувати координати вектора за формулою:
Збіжність даного алгоритму слід оцінювати
за модулем градієнта 
, при цьому модуль варто розраховувати тільки по тим
координатами , які не перебувають на межі області (у цьому випадку 
). Аналогічно
розраховується модуль градієнта і у формулі (3).
5. Виділення контурів і
характерних точок зображення будемо називати характерними ті точки зображення, які є найбільш інформативними, тобто
за якими можна відновити з деякою точністю вихідне зображення.
Неважко помітити, що запропонований метод згладжування дозволяє виділити
характерні точки. Це точки з координатами , які є граничними в тому сенсі , що 
. Дані точки повинні визначати згідно з рішенням
оптимізаційної завдання становище всіх нехарактерних точок.
Неважко помітити, що
граничними точками будуть також точки, що визначають контури краю зображення. У
цих точках є великим значення модуля градієнта, тому в околиці
цих точок не вдасться згладити зображення і значення яскравості в цих точках
згладженому зображення опиняться на межі допустимих значень.
Пропонована процедура
згладжування дозволяє поліпшити якісні характеристики методів попередньої
обробки зображень, що використовують
градієнт зображення. Відзначимо на закінчення, що запропонований метод
згладжування особливо ефективно фільтрує помилки, що виникають при оцифровці
реальних зображень.
Список
літератури
Lee
D. Coping with discontinuities in Computer Vision: Their Detection,
Classification and Measurement// IEEE Transactions on Pattern Analysis and
Machine Intelligence, vol.12, № 4, 1990.
Дуда Р.,. Харт П.
Розпізнавання образів та аналіз сцен. - М.: Світ, 1976.
Павлідіс Т. Алгоритми
машинної графіки та обробки зображень. - М.: Радіо і зв'язок, 1986.
