Підходи для декомпозиції зображень

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

Згортання полягає в поділі візуальних образів на класи – групи об’єктів, схожі між собою за певними ознаками. Початково образ (об’єкт) розбивається на мікрооб’єкти за певним правилом. Надалі при об’єднанні мікрооб’єктів утворюються мікрокластери, характеристики F ₁, F ₂, …, F_n яких формуються як суми чи інші функції характеристик мікрооб’єктів, що повинні задовольняти обмеженням певного виду. Значення функцій ознак мікрокластерів, що формуються, відповідають за яскравість, колір, співвідношення заповнених та пустих клітинок тощо. Вершини, що не підлягають подальшому згортанню, відповідають кластерами результату.

Послідовність кроків алгоритму згортання є наступною:

Крок 1. Розбиття простору. Накладання на образ сітки із кроком з ряду 1× 1, 2× 1, 2× 1, …, N × M, та формування мікрооб’єктів (МО) (заповнених клітинок).

Крок 2. Для кожного МО пошук сусіда справа та знизу.

Крок 3. Занесення у список кандидатів на об’єднання (СКО) двох МО, якщо при об’єднанні вони формують кластер (МК) прямокутної форми і який відповідає вимозі наповнення.

Крок 4. Видалення зі СКО повторень: для кожної пари списку перевірка входження у інші пари елементів, з яких вона складається. Видалення пар при їх наявності. Наприклад, у списку (a, b), (b, c), (a, d), (d, f) пари (a, d), (b, c) будуть видалені.

Крок 5. Побудова мікрокластерів вищого рівня на основі СКО.

Крок 6. Повторення попередніх кроків із заміною МО на МК до повного покриття образу прямокутниками.

На рис. 3.13 зображено приклад роботи процедури згортання при скануванні зображення зліва–направо зверху–вниз. Після накладання сітки на образ утворено 11 мікрооб’єктів (рис. 3.13, а). На першому кроці алгоритму об’єднаються мікрооб’єкти (3, 4) = 12, (5, 6) = 13, (7, 8) = 14, (10, 11) = 15 (рис. 3.13, б), на другому кроці – (13, 14) = 16 (рис. 3.13, в). Цей процес зображено деревом згортання на рис. 3.14.

а б в

Рис. 3.13. Приклад згортання

Рис. 3.14. Дерево згортання