Кластеризація зображення за фрагментами інтенсивності

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

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

Опис методу

Алгорим методу складається з чотирьох основних етапів:

1. Фрагментація за інтенсивністю кольору
2. Поділ зображення на області
3. Обчислення ключів
4. Пошук

Фрагментація за інтенсивністю кольору

Тривимірна модель зображення

Першим етапом є побудова тривимірної поверхні зображення, де на осі Z відкладені значення інтенсивністі кольору. Для отримання тривимірної поверхні зображення спочатку кольорове зображення перетворюється у відтінки сірого. Кожна елементарна клітинка, піксель, приймає значення від чорного до білого кольору, яке позначимо як b — яскравість. Діапазон всіх можливих значень яскравості знаходиться в межах 0÷255. Для перетворення використовуємо алгоритм BT709 [Архівовано 26 Грудня 2016 у Wayback Machine.] з наступними коефіцієнтами R, G, B:

$R=0,2125;G=0,7154;B=0,0721$

Значення яскравості пікселів обчислюється з рівняння відносного заповнення клітинки у відсотках від чорного кольору:

$b=(256-c_{i})\cdot 100/256$

або у відсотках від білого кольору:

$b=c_{i}\cdot 100/256$

де c_i (i = 1, 2, 3) — значення  компоненти R (G або B) сірого кольору пікселя.

І-ий фрагмент — це множина пікселів, значення інтенсивності кольору яких рівне і (0 <= і <=255). 

Поділ зображення на області

Приклад накладання сітки розміром 2х2

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

Обчислення ключів

Для характеристики окремої області використовується значення кількості фрагментів, центри яких належать цій області (N_f).

На початку етапу для кожного паралелепіпеда N_f =0.

Визначення координат середньої точки для кожного фрагмента/сегмента інтенсивності:

${\bar {x}}=1/k_{s}\sum X(s)$,

${\bar {y}}=1/k_{s}\sum Y(s)$,

$x_{i}\in X(s),y_{i}\in Y(s)$,

де s — номер фрагмента чи сегмента, X, Y — множини координат пікселів.

Визначення приналежності точки до проєкції конкретного паралелепіпеда на площину зображення, де i та j  - індекси проєкції:

$i=({\bar {x}}(s)/L_{x})_{ceil}+1$

$j=({\bar {y}}(s)/L_{y})_{ceil}+1$

Тут  $L_{x}$ та $L_{y}$-кількість областей по X  та У.

Інкремент значення кількості фрагментів для знайденої проєкції:

$N_{f}(i,j)=N_{f}(i,j)+1$

Характеристика N_f використовується як індекс кластера зображення для проведення пошуку зображень.

Пошук

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

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

Варіанти методу

Іноді використовують сегменти інтенсивності кольору. Іим сегментом називають сукупність фрагметів інтенсивності кольору від 0 до і, або від і до максимального значення (255 для моделі RGB).

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

Використання

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

Джерела та література

• Vailaya, A.K. Jain, H.J. Zhang, «On image classification: city vs. landscape», Pattern Recognition, vol. 31, p. 1921—1935, 1998.
• M.J. Swain, D.H. Ballard, «Color indexing», International journal of Computer Vision, vol. 7, n. 1, p. 11-32, 1991.
• H. Nezamabadi-pour, E. Kabir, «Image retrieval using histograms of unicolor and bicolor blocas and direccional changes in intensity gradient», Pattern Recognition Letters, vol. 25, n. 14, p. 1547—1557, 2004.
• Мельник Р. Пошук образів за індексами кластерів фрагментів зображень [Електронний ресурс] / Р. Мельник, Ю. Каличак // Вісник Національного університету «Львівська політехніка». Комп'ютерні науки та інформаційні технології. — 2011. — № 719. — С. 269—277