В Загребнюк, А Кидисюк, А Яворський - Застосування методу карунена-лоева для кластеризації кольорових зображень - страница 1

Страницы:
1 

УДК 004.932.1

1 2 1

В. Загребнюк, А. Кидисюк, А. Яворський

1 Одеська національна академія зв'язку ім. О.С. Попова, 2 Львівська дирекція УДППЗ «Укрпошта»

ЗАСТОСУВАННЯ МЕТОДУ КАРУНЕНА-ЛОЕВА ДЛЯ КЛАСТЕРИЗАЦІЇ КОЛЬОРОВИХ ЗОБРАЖЕНЬ

© Загребнюк В., Кидисюк А., Яворський А., 2009

Запропоновано модифікацію алгоритму ІЗОДАТА з використанням перетворення Карунена-Лоева. Показано, що використання тільки компонентів кольору недостатньо для забезпечення надійної кластеризації з подальшим виділенням об'єктів інтересу. Якісніих результатів можна досягти при сумісному врахуванні координат та розподілу компонент R, G, B.

In article updating of algorithm ISODATA with use of transformation Karhunen-Loeve is offered. It is shown, that use only a component of chromaticity is not enough for support reliable clustering with the subsequent allocation of objects of interest. Qualitative results can be reached at the additional account of distribution component R, G, B in an image plane.

Вступ

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

Сьогодні розроблено доволі багато таких алгоритмів [1-4] як для автоматичної, так і для інтерактивної кластеризації. При цьому слід зазначити, що більшість із них не забезпечують прийнятних результатів кластеризації в системах розпізнавання. Тому, як правило, обмежуються виявленням заздалегідь заданих типів об'єктів з відомими ознаками. Для кластеризації й сегментації зображень застосовуються евристичні методи [2, 3, 5], методи глобальної оптимізації [6], виділення границь [7, 8] та ін. У системах розпізнавання образів найширеніші кластеризація й сегментація зображень поєднано з різними методами попередньої обробки зображень. Незважаючи на велику кількість прикладних досліджень, присвячених кластеризації та сегментації зображень, слід підкреслити, що розроблені в межах цих досліджень алгоритми та системи ефективні тільки у вузьких предметних областях, тобто орієнтовані на вирішення вузькоспеціалізованих задач.

Постановка задачі

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

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

Відобразимо зображення на рис.1 у простір RGB. В RGB просторі (рис. 2) виділяються два кластери: перший - відповідає фону (показаний сірим кольором); другий - об'єкту інтересу (чорний колір). На рис. 3 наведено проекцію цих двох кластерів на площину GB.

Рис. 2. Вид усього зображення (сірі точки) і області інтересу (чорні точки) у тривимірному колірному просторі RGB

Рис. 3. Проекція всього зображення на площину GB

Опис алгоритму

Як видно з наведених результатів, ці кластери мають еліптичну форму й перетинаються, а це означає, що необхідно розробляти спеціальну процедуру кластеризації, що давала б надійні результати при автоматичному дослідженні гістологічних препаратів. Відомо, що надійні результати в задачі кластеризації можна одержати за умови, що істотні ознаки різних класів є незалежними, або по іншому класи не перетинаються. Одним з можливих рішень, яке забезпечує прийнятний розподіл класів, є використання перетворення Карунена-Лоева (метод головних компонент). Це перетворення - це розкладання сигналу X(t) за базисом ортогональних функцій, кожна з яких є власною функцією інтегрального "характеристичного" рівняння із симетричним безперервним ядром:

J K (t, s)f j (s)ds = 1jf j (t) (1)

0

де X It) =

X (t) = £ Vl nan f n (t), 0<t<T, E[an an}=\

0 ПФШ  - вхідний сигнал;  K (t, S)  - кореляційна

n=1

або ковариаційна функція; f j (s) - j -та власна функція; 1j - j -те власне число.

У дискретному випадку перетворення Карунена-Лоева полягає у знаходженні подібної до

T

коваріаційної матриці S діагональної матриці Л , тобто S = Ф ЛФ, де Л - діагональна матриця, а Ф - матриця власних векторів цього перетворення y = Фх. Матриця S є дискретним відображенням кореляційної функції K(t, s) .

Обробка зображення на основі перетворення Карунена-Лоева полягає в тому, що кожна точка кольорового зображення xi, i = N, де N - кількість точок на зображенні розглядається як

об'єкт із трьома координатами, які відповідають значенням R, G та B. Потім по всьому зображенню обчислюється ковариаційна матриця між трьома компонентами R, G та B:

(2)

 

' S RR

S RG

SRB "

 

S GR

S GG

S GB

 

V S BR

S BG

s BB 0

Л tti1'-x" >№<-x<"), а k, j = R, G, B

n      1 i=1

n

Розв'язок характеристичного рівняння: |£~ = 0 дає власні числа І1,12,-", l p;    l і > 0   "i.. Для кожного кореня характеристичного рівняння \ визначаємо

власний вектор l     з розв' язку системи рівнянь:

-4£ Уk } = 0, \l(k ^ = 1. (3)

Для обчислення власних значень Л та матриці власних векторів Ф симетричної ковариаційної використовують методу обертань Якобі.

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

Y = Ф TX. (4)

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

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

Для виділення кластерів на перетвореному зображенні застосовувався алгоритм ІЗОДАТА. Перевагою цього алгоритму кластеризації є можливість завдання різних вхідних параметрів (бажана кількість кластерів, мінімальна кількість об'єктів у кластері та ін.), а також динамічна зміна кількості кластерів у процесі обробки зображення.

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

Дослідження ефективності

Ефективність запропонованого методу кластеризації визначали шляхом порівняння результатів кластеризації у просторі RGB та у просторі Карунена-Лоева.

На рис. 5 наведені результати кластеризації зображення в просторі RGB, а на рис. 6 результати кластеризації у просторі головних компонент. Вхідні параметри алгоритму кластеризації були встановлені однаковими для кожного способу кластеризації. На рис. 5, а показаний результат кластеризації всього зображення, а на інших трьох - 5, б, в, г представлена кожна із трьох компонент R, G та B. На рис. 6, а показано результат кластеризації всього зображення у новому просторі, а на інших трьох - 6, б, в, г представлені проекції компонент, що відповідають власним числам 47, 2321 і 110, на площину зображення.

З наведених рисунків видно, що у системі RGB три компоненти кольору корелюють між собою (рис. 5, б, в, г), що ускладнює виділення об'єкта інтересу. При використанні перетворення Карунена-Лоева відбувається перерозподіл інформації між трьома компонентами (рис. 6, б, в, г) так, що підпростір, який відповідає найбільшому власному числу, міститиме переважно інформацію щодо тла зображення. Підпростір, що відповідає найменшому власному числу, міститме детальнішу інформацію про лімфоцит.

Рис. 5. Результат кластеризації в системі RGB

Рис. 6. Результат кластеризації в просторі головних компонентів: а - кластеризоване зображення; б, в і г - підпростори, що відповідають різним власним числам

Тому можна зробити висновок, що об'єкт (лімфоцит) можна простіше виділити, якщо проводити кластеризацію в просторі головних компонентів і аналізувати зображення 6, б, що відповідає найменшому власному значенню.

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

На рис. 7 наведено результат кластеризації з використанням п'яти істотних ознак.

Рис. 7. Результат кластеризації в п 'ятивимірному просторі (а); відображення на підпростори (б, в, г)

На рис. 7, а показано відображення у простір RGB результату кластеризації зображення в п' ятивимірному просторі, а на інших 7, б, в, г - відображення на підпростори, що відповідають власним числам: 46, 2144, 104.

Висновок

Класифікації у RGB просторі значима інформація про об'єкти зберігається в проекції на підпростір, що відповідає мінімальному власному числу (рис. 7, б). При додатковому використанні двох просторових координат об'єкти пошуку мають вигляд цілісних сегментів однакового кольору, що забезпечує надійне виділення лімфоцитів.

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

1. Попова Г.Н. Степанов В.Н. Автоматизация процесса сегментации изображений медико биологических микрообъектов // 7-я Международная конференция DSPA-2005. - 3 с. 2. Семенов С.М., Татарников А. В. Распознавание некоторых объектов на изображениях, получаемых со спутников // Солнечно-земная физика. - 2004. - Вып. 5. - С. 80-83 3. Saeid Sanei, Tracey K.M. Lee Cell recognition based on pca and bayesian classification // 4th International Symposium on Independent Component Analysis and Blind Signal Separation, pp. 239-243, Nara, Japan 2003. 4. James Bruce, Tucker Balch, Manuela Veloso. Fast and inexpensive color image segmentation for interactive robots // Proceedings of the 2000IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '00) - 2000. - V.3. - P.2061 - 2066. 5. Williams P.S., Alder M.D. Generic texture analysis applied to newspaper segmentation // Proc. ICNN96. - 1996 - V.3 - P. 1664-1669. 6. Huseyin Tek, Benjamin B. Kimia Volumetric Segmentation of Medical Images By Three-Dimensional Bubbles // CVIU. - 1997. 7. Marroquin J.L. Probabilistic Solution of Inverse Problems // Tech. Rep. Massachusetts Institute of Technology, 1985. 8. Newsam S., Bhagavathy S., Fonseca L., Kenney C., Manjunath B. S. Object based representations of spatial images // 51st International Aeronautical Congress. - 2000. 9. Deng Y., Manjunath B.S., Shin H. Color Image Segmentation // Proc. of IEEE Conf. on Computer Vision and Pattern Recognition - 1999. - pp. 6.

Страницы:
1 


Похожие статьи

В Загребнюк, А Кидисюк, А Яворський - Застосування методу карунена-лоева для кластеризації кольорових зображень