Сегментування зображень за кумулятивною гістограмою

Задача сегментування зображення має на меті різні цілі: 1) віднімання світло-сірого фону від облич та інших зображень, 2) віднімання чорного фону з зображень, 3) поділ інтенсивності зображення на дві і більше частин для опрацювання образу по частинах, 4) виділення регіонів зображення тощо. Для знаходження порогу сегментування в перших двох задачах застосуємо наступний алгоритм.

Використаємо поняття гіпотетичного зображення – це множина пікселів, у якій всі інтенсивності представлені однаковою кількістю. Число пікселів інтенсивності кожного значення дорівнює , де N, M – розміри зображення, для якого ведеться пошук порогу сегментування, n – кількість інтервалів кумулятивної гістограми.

Для гіпотетичного зображення побудуємо нормовану кумулятивну гістограму за формулою:

(3)

де – кількість пікселів (накопичена частота) гіпотетичного зображення в інтервалі інтенсивності 1 s.

Побудуємо функцію різниці між кумулятивними гістограмами реального та гіпотетичного зображень:

(4)

На рис.1б наведено графік гістограми для зображення “фотографа” (рис.1а). На рис.1в наведено графіки кумулятивних гістограм: пряма – залежність для гіпотетичного зображення, крива – для реального. На рис.1г представлено графік залежності функції – різниці між кумулятивними гістограмами реального та гіпотетичного зображень.

а б

в г

Рис. 1. Тестове зображення (а), гістограма (б), кумулятивні гістограми (б)

та різниця між ними (в)

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

На початку інтервалу інтенсивності мінімум вказує про слабе наповнення інформацією лівої частини інтервалу. Тому крайній зліва мінімум алгоритмом ігнорується (правило 1). На правому краю інтервалу частина, що могла б відсікатися не є інформативною. Крайній справа максимум алгоритмом ігнорується (правило 2).

Для знаходження порогу сегментування сформулюємо одновимірну оптимізаційну задачу: знайти значення (k=1, 2 ….) локальних екстремумів, при яких модуль функції в межах інтервалів пошуку приймає максимальні значення і виконуються умови екстремуму функції:

(5)

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

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

, (6)

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

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

(7)

де позначає вибір екстремуму, при якому додатковий критерій приймає мінімальне значення. Приймаємо: – для сегментування чорного фону, – для сегментування світлого сірого фону.

Для сегментування чорного , а для світлого сірого – . Практично в задачі (7) для сірого фону шукається екстремум, найближчий до величини , а для чорного – максимум, найближчий до чорного, тобто до 0.

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

.

Рис. 2. Синтетичний образ, кумулятивні гістограми та різниця між ними

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

Рис. 3. Сегментування світлого сірого і чорного

Експериментальні результати. Застосуємо розроблений метод до зображень, поданих в роботі [8]. Оригінали зображень надані авторами. Зображення, нормовані кумулятивні гістограми реальних та гіпотетичних зображень, а також функція різниці кумулятивних гістограм реальних та гіпотетичних зображень представлені на рис. 4.

Рис. 4. Тестові зображення (а), кумулятивні гістограми (б) та різниця (в)

Знайдені для зображень з рис.4 координати максимумів функції в задачі (7), найближчих до лівої границі інтервалу інтенсивності, прийняті порогам сегментування цих зображень (таблиця). Сегменти – найтемніші частини зображень – представлені на рис. 5.

Рис. 5. Сегментовані частини зображень

Розроблений метод не чутливий до розмірів сегментованих зображень. Зокрема, зображення «монети» (220х216) було зменшене і збільшене в 1, 5 рази (відповідно до 66 і 150 відсотків). Для трьох різних за розмірами зображень отримані гістограми та функції різниці (рис.6а, 6б). Різні розміри одного зображення підтверджують графіки залежності дисперсії координат пікселів 3-х зображень для кожного значення інтенсивності від 0 до 255 (рис.6 б). В світлих тонах гістограми дещо відрізняються, але в кумулятивних відбувається згладжування коливань. Отже, метод дає однакові пороги різних за розмірами зображень, якщо їх гістограми мають однакову форму.

а б в

Рис. 6. Гістограми, різниці кумулятивних гістограм та дисперсія координат пікселів

зображень «монети» 3-х різних розмірів (66, 100, 150 відсотків)

Для порівняння результатів сегментування з іншими алгоритмами використано дані з роботи [8]. В таблиці наведені значення порогів сегментування розглянутих зображень, а на рис.7 наведені сегменти, отримані за допомогою вказаних алгоритмів [9-12].

Рис. 7. Сегментовані частини зображень за різними алгоритмами

Таблиця. Пороги сегментування різними методами

Три з чотирьох наших результатів близькі до результатів з другого стовпчика [Rosin], які базуються на аналізі однієї переважаючої групи пікселів. Однак цей алгоритм не зміг виділити групи пікселів, близьких до початку координат, і подати чисте «12». Решта статистичних методів [Kapur, Otsu, Xu] в принципі не зауважують коливань гістограми чи кумулятивної гістограми. Лінійна складність та отримані результати є свідченням переваг представленого алгоритму.

На рис. 8 наведено приклад сегментування зображення “числа” з пакету Matlab (R2012b). Отримано поріг сегментування 180. Алгоритм Отцу дає значення 203 (без виділення числа 12). Вихідне зображення, кумулятивні гістограми, функція різниці з позначеним порогом та сегментовані зображення за методами кумулятивної гістограми та Отцу відповідно подані на рис.8.

Рис. 8. Сегментування зображення “числа” з пакету Matlab

Експеримент, поданий на рис.8, підтверджує незалежність методу від інтервалу інтенсивності, виду гістограми та його перевагу, зокрема, над методом Отцу.

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