2.4. Формування регіонів та звязних областей
Метою другого етапу опрацювання зображення є його декомпозиція на регіони. Утворення регіонів реалізується алгоритмом у просторі отриманих прямокутників, що покривають зображення. Множина всіх прямокутників Q(Q1, Q2, Q3 ,…, QN), де N – достатньо велике значення, є об’єктом алгоритму згортання, в результаті роботи якого формуються p підмножин O1(Q1, Q2, Q3, …, Qz), O2(Qz+1, Q z+2, Q z+3, … , Qt), … , Op(Qt+1, Q t+2, Qt+3, …, QN), кожна з яких визначає фрагмент зображення. Як функція критерію об’єднання прямокутників у регіони приймається кількість суміжних між прямокутниками мікроб’єктів з однаковою яскравістю (рис. 3 .13, а).
Як правило, образи, що плануються для опрацювання, характеризуються втратами інформації. Через це при їх покритті прямокутниками останні, будучи частинами одного цілого зображення, розташовані на певній віддалі між собою. Для врахування втрат сформульовано критерій сусідства, на основі відстані між кластерами. Згідно нього, кластери беруть участь в об’єднанні при умові, якщо вони знаходяться на віддалі d (рис. 3 .13, б).
d
а б
Рис. 3.13. Кластери для об’єднання (а) та відстань d між кластерами (б)
Для врахування типу зображень критерій відстані розширено на “діагональну” та “головну” відстані (рис. 3 .14).
а б
Рис. 3.14. Діагональна (а) і головна (б) відстані
Використаємо позначення Br для інтегральної характеристики інтенсивності регіону (зв’язної області кластерів) як середнє значення інтенсивності s кластерів, що його формують:
Br=1/s × Σbi (3.12)
Ознака інтенсивності використовується в критеріях відбору кластерів на формування регіонів за їх яскравістю.
Із сформованих кластерів формуємо регіони за наступними критеріями об’єднання:
1) Інтенсивності кластерів Bi, Bj є однаковими;
2) Результуюча яскравість регіону більша або рівна величині wB;
3) Яскравість шуканого кластера Bj для об’єднання його із кластером Bi є у межах:
Bi - lo ≤ Bj ≤ Bi + hi, (3.13)
де lo, hi задають границі чутливості до інтенсивності кластерів.
4) Як умову формування регіону задаємо головну та діагональні відстані між кластерами.
Алгоритм формування регіонів. Здійснюється згортання кластерів у регіони за заданими критерієм, головною та діагональною відстаннями.
Вхідні дані алгоритму:
С – множина з n кластерів;
F* – функція критерію об’єднання кластерів;
головна та діагональна відстані для обмеження сканувальної області.
Вихідні дані алгоритму:
Сформовані регіони в множині R.
Блок-схема алгоритму зображена на рис. Error: Reference source not found, де числами справа та зліва від блок-схеми позначено кроки алгоритму. Для пояснення алгоритму введемо наступні позначення:
S – область сканування поточного регіона – сукупність кластерів-кандидатів для об’єднання.
S(Ci) – область сканування регіона Ci.
d(Ci, Cj) – відстань між двома регіонами Ci, та Cj.
В операторі П1 здійснюється ініціалізація змінної RID (Region ID – ідентифікатор регіона), яка використовується для вказання приналежності кластера до регіону. Оператори П2 здійснюють перебір всіх елементів вхідної множини. Оператор П3 перевіряє чи кластер Ci не входить до жодного регіону. Якщо це так, то кластеру Ci в поле Region заноситься значення змінної RID, і збільшується значення змінної RID на одиницю (П4). Для зменшення складності алгоритму та реалізації сканувальної області наступні дві умови в П5 обмежують простір пошуку кандидатів для об’єднання:
1. Умова задає обмеження на ширину сканувальної області: якщо кандидат для об’єднання знаходиться за межами сканувальної області, ітераційний процес продовжуємо для наступного елементу з вхідної множини завдяки оператору П6.
2. Умова задає обмеження на максимальну відстань між двома кластерами в межах сканувальної області: якщо кандидат для об’єднання знаходиться на відстані більшій за допустиму, то ітераційний процес продовжується для наступного елементу з вхідної множини. Це відбувається завдяки оператору П6. Величина рівна висоті кластера і обчислюється динамічно в роботі алгоритму.
При оцінюванні межі сканувальної області береться до уваги головна та діагональні відстані.
Формування зв’язних областей. Умовою об’єднання регіонів у зв’язні області є відстань між ними. Тому для їх формування послідовно здійснюється пошук оптимального значення функції близькості між ними:
F* = max (Fk j), k, j I, (3.14)
де I – множина всіх можливих пар об’єктів на верхньому доступному рівні ієрархічного дерева, F – функція відстані між регіонами.
Крім того, об’єднання об’єктів з номерами і та j здійснюється при виконанні обмежень:
1) на середню яскравість області:
Blo ≤ (Bi + Bj ) /2 ≤ Bhi, (3.15)
де Blo та Bhi – допустимі межі інтенсивності сегментів.
2) на допустиму різницю яскравостей об’єктів-кандидатів на об’єднання:
Bmin ≤ |Bi - Bj | ≤ Bmax , (3.16)
де Bmin та Bmax – допустимі різниці яскравостей регіонів в межах області.
Вказані обмеження дозволяють контролювати однорідність інтенсивності областей, а також редагувати фрагменти зображення: підсилити або послабити контраст, видалити, вказати контури тощо. Елементами редагування виступають: 1) все зображення, 2) зв’язані області зображення, 3) регіони областей. Зміна контрасту здійснюється приведенням поточної інтенсивності до іншого масштабу значень, а саме:
1) Зміна інтенсивності регіону на основі граничних значень яскравостей області, до якого він входить,
2) Зміна інтенсивності регіону на основі граничних значень якравостей всього зображення.
Приклад застосування інструменту зміни контрасту наведено на рис. 3 .15.
а б в
Рис. 3.15. Виділення та опрацювання контрасту сегментів зображення
а – вихідне зображення; б – два регіони підсилені, два – послаблені;
в – змінено яскравість області
Використаємо позначення Ba для інтегральної характеристики інтенсивності замкнутої області (зв’язної області регіонів) як середнє значення інтенсивності p регіонів, що її формують:
Ba=1/p × ΣBr (3.17)
Для формування із отриманих регіонів замкнуті області, застосовуємо наступні критерії:
1) Яскравість шуканого регіону Br для об’єднання його із регіоном Bp є у межах:
Bp - lo ≤ Br ≤ Bp + hi, (3.18)
де lo, hi задають границі чутливості до інтенсивності регіонів.
2) Регіони що об’єднуються мають інтенсивності кластерів, що відрізняються на задану величину ω.
3) Регіони що об’єднуються мають щонайменше задане число спільних яскравостей кластерів.
4) Як умову формування зв’язної області задаємо головну та діагональні відстані між регіонами.
Алгоритм формування областей здійснює згортання регіонів в області за заданими критерієм, головною та діагональною відстаннями.
Вхідні дані алгоритму:
С – множина з n регіонів;
F* – функція критерію об’єднання регіонів;
головна та діагональна відстані для обмеження сканувальної області.
Вихідні дані алгоритму:
Сформовані області в множині I.
Блок-схема алгоритму зображена на рис. Error: Reference source not found, де числами справа та зліва від блок-схеми позначено кроки алгоритму. Для пояснення алгоритму введемо наступні позначення:
S – область сканування поточної зв’язної області – сукупність регіонів-кандидатів для об’єднання.
S(Ci) – область сканування зв’язної області Ci.
d(Ci, Cj) – відстань між двома зв’язними областями Ci, та Cj.
В операторі П1 здійснюється ініціалізація змінної IID (Integrated Area ID – ідентифікатор області), яка використовується для вказання приналежності регіону до області. Оператори П2 здійснюють перебір всіх елементів вхідної множини. Оператор П3 перевіряє чи регіон Ci не входить до жодної області. Якщо це так, то регіону Ci в поле AreaID заноситься значення змінної IID, і збільшується значення змінної IID на одиницю (П4). Для зменшення складності алгоритму умова П5 задає обмеження на ширину сканувальної області: якщо кандидат для об’єднання знаходиться за межами сканувальної області, ітераційний процес продовжуємо для наступного елементу з вхідної множини завдяки оператору П6. При оцінюванні межі сканувальної області береться до уваги головна та діагональні відстані.
Оператор П7 здійснює оцінку об’єднання двох кластерів F(Ci +Cj). Якщо отримана оцінка задовільняє китерій об’єднання (П8), то здійснюється запис інформації про приналежність регіону Cj до області, в якій міститься кластер Ci (П9).
Після завершення ітераційного процесу, оператором П11 викликається функція FormListOfClosedAreas, яка здійснює формування областей з множини регіонів С на основі інформації про входження до області – змінної IID.