Формування мікро кластерів та кластерів

Формування мікро кластерів. Мікрооб’єкти образу утворюються при його поділі сіткою. Кроки сітки вибираються з ряду величин 1× 1, 1× 2, 2× 1, 2× 2 тощо (керує кроком користувач). Кожний елементарний квадрат (піксель) – набуває значення у діапазоні від чорного до білого, яке позначимо як b (яскравість мікрооб’єкту). Діапазон інтенсивності становить 0÷ 100 (від білого до чорного) (рис. 3.4).

(R, G, B): (0, 0, 0) (255, 255, 255)

b: 100% 0%

Рис. 3.4. Діапазон значень інтенсивності мікрооб’єктів
та поріг чутливості алгоритму

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

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

При формуванні мікрокластерів керуємо наступними параметрами:

1) Кроком сітки розбиття зображення: 1× 1, 1× 2, 2× 1, 2× 2 тощо;

2) Порогом чутливості алгоритму в межах 0÷ 100 %;

3) Процентом заповнення мікрооб’єкту в межах 0÷ 100 %;

4) Типом опрацьовуваного образу: сірого, чорно-білого;

5) Методом сканування зображення: однонапрямлений, однонапрямлений із накладанням, двонапрямлений із формуванням нечітких кластерів, двонапрямлений із формуванням чітких кластерів.

Алгорти сканування. В попередніх роботах [118, 119] для формування мікрокластерів використовувався простий алгоритм однонапрямленого (швидкого) сканування (рис. 3.5, а). Для покращення характеристик декомпозиції зображень в межах сітки більших розмірів запропоновано використати наступні алгоритми сканування: одновісьовий, повний із формуванням нечітких кластерів, повний із формуванням чітких кластерів.

В алгоритмі однонапрямленого сканування скануюче вікно із розмірами сітки розбиття рухається по зображенню лише за вибраним кроком сітки (рис. 3.5, а). В алгоритмі одновісьового сканування із накладанням скануюче вікно із розмірами сітки розбиття m × n рухається по зображенню за наступним правилом: якщо можна сформувати з об’єкту мікрокластер, то переходимо на наступний крок сітки m × n, у протилежному випадку переходимо на крок m × 1 (рис. 3.5, б).

а б в г

Рис. 3.5. Алгоритми сканування з кроком сітки 2× 2 та фрагмент зображення

Вважаємо кластер чітким, якщо він не перетинається із жодним іншим кластером, і нечітким – у протилежному випадку. На рис. 3.6, а зображено чіткі кластери, рис. 3.6, б – нечіткі.

а б

Рис. 3.6. Чіткі та нечіткі кластери

В алгоритмі повного сканування із формуванням нечітких кластерів скануюче вікно із розмірами сітки розбиття m × n рухається по зображенню за таким правилом: якщо можна сформувати з об’єкту мікрокластер, то переходимо на наступний крок сітки 1× n, у протилежному випадку переходимо на крок 1× 1. Колір використаних пікселів встановлюються у білий (0% інтенсивності), що дає змогу сформувати нечіткий кластер при заданому параметрі інтенсивності мікрокластера (рис. 3.5, в).

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

Порівняння алгоритмів сканування з кроком сітки 2× 2 зображено на рис. 3.5. На рис. 3.5, г зображено фрагмент зображення із пронумерованими об’єктами, які формуються різними методами сканування. Залежність кількості мікрокластерів від обмеження на яскравість в різних алгоритмах сканування зображення з рис. 3.5, г зведено у табл. 3.1.

Таблиця 3.1.
Залежність кількості мікрокластерів від обмеження на яскравість в різних алгоритмах сканування зображення

*) індекси позначають половину даного кластера.

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

− при збільшенні кроку сітки є сенс зменшити параметр інтенсивності мікрокластера та вибрати повний алгоритм сканування із формуванням чітких кластерів для подальшого аналізу;

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

− одновісьовий алгоритм дає кращі результати за швидкий коли треба детальніше проаналізувати окремий сегмент;

− для аналізу всього образу достатньо використати швидкий алгоритм сканування та малий крок сітки.

Формування кластерів. Мікрооб’єкти виступають у ролі листків ієрархічного дерева, у вузлах якого формуються кластери (рис. 3.7).

Рис. 3.7. Фрагмент 3-ступеневого ієрархічного дерева

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

Для характеристики інтегральної інтенсивності кластера приймемо середнє зважене значення яскравостей мікрооб’єктів (а також кластерів)з номерами i та j, що його формують:

(3.6)

де b_i, b_j – інтенсивності складових мікрооб’єктів (кластерів), a_{i 1}, a_{i 2}, a_{j 1}, a_{j 2} – значення їх геометричних розмірів (довжини сторін прямокутника). Прикладом покриття образів прямокутниками є фрагмент зразка крові (рис. 3.8).

Рис. 3.8. Покриття образу кластерами-прямокутниками

Введемо наступні критерії формування кластерів:

1) Інтенсивності мікрокластерів b_i, b_j є однаковими;

2) Результуюча яскравість кластера більша або рівна величині w_b;

3) Яскравість шуканого мікрокластера b_j для об’єднання його із мікрокластером b_i є у межах:

b_i - lo ≤ b_j ≤ b_i + hi, (3.7)

де lo, hi задають границі чутливості до інтенсивності мікрокластерів.

4) Інтенсивності мікрокластерів b_i, b_j відрізняються не більше чим на задану абсолютну величину a:

| b_i - b_j | ≤ a (3.8)

5) Заповнення результуючого кластера складає не менше заданої величини z.

Алгоритм формування кластерів. Даний алгоритм здійснює згортання мікрокластерів у кластери за заданими критерієм та способом об’єднання.

Вхідні дані алгоритму:

С – множина з n мікрокластерів;

F ^* – функція критерію об’єднання мікрокластерів;

mode – прапорець, що визначає спосіб згортання: одне об’єднання на кроці (mode = 1) або максимальна можлива кількість.

Вихідні дані алгоритму:

Сформовані кластери в множині С.

Блок-схема алгоритму зображена на рис. Ошибка! Источник ссылки не найден.. На схемі числами справа та зліва від блок-схеми позначено кроки алгоритму. Для пояснення алгоритму введемо наступні позначення:

S – область сканування поточного кластера – сукупність мікрокластерів-кандидатів для об’єднання.

S (C_i) – область сканування кластера C_i.

d (C_i, C_j) – відстань між двома кластерами C_i, та C_j.

В алгоритмі використовується цикл ВИКОНАТИ {оператори} ПОКИ {умова завершення циклу}. Поки значення змінної w = false цикл виконується. В операторі П1 здійснюється присвоєння, необхідне для закінчення ітераційного процесу. Оператори П2 здійснюють перебір всіх елементів вхідної множини. Для зменшення складності алгоритму та реалізації сканувальної області наступні дві умови в П3 обмежують простір пошуку кандидатів для об’єднання:

1. Умова задає обмеження на ширину сканувальної області: якщо кандидат для об’єднання знаходиться за межами сканувальної області, зокрема, якщо кластер C_j не входить до сканувальної області кластера C_i, то ітераційний процес продовжуємо для наступного елементу з вхідної множини завдяки оператору П4.

2. Умова задає обмеження на максимальну відстань між двома кластерами в межах сканувальної області: якщо кандидат для об’єднання знаходиться на відстані більшій за допустиму, то ітераційний процес продовжується для наступного елементу з вхідної множини. Це здійснюється завдяки оператору П4. Величина рівна висоті кластера і обчислюється динамічно в роботі алгоритму.

Оператор П5 здійснює оцінку об’єднання двох мікрокластерів F (C_i + C_j). Якщо отримана оцінка задовільняє критерій об’єднання (П6), то здійснюється об’єднання двох мікрокластерів в результуючий кластер C_i (П7). При цьому, в П7 мікрокластер C_j видаляється з вхідної множини. В операторі П7 також здійснюється присвоєння, необхідне для продовження ітераційного процесу.

Для підтримки побудови різних дерев згортання, що утворюються в процесі різної максимальної кількості згортання на кроці, використовуємо змінну mode. Дана перевірка здійснюєтсья в операторі П8. Якщо задано одне згортання на кроці (mode = 1), то ітераційний процес продовжується для наступного елементу з вхідної множини, завдяки оператору П10. В протилежному випадку, оператор П9 дозволяє повторити ітераційний процес для новоутвореного кластера. Оператори П11 здійснюють інкремент значень змінних циклу.

Оператор П12 здійснює перевірку для зупинки ітераційного процесу. Вихід з ітераційного процесу відбувається, коли не існує кандидатів для об’єднання, що задовільняють заданий критерій згортання (П6).