Обробка растрових зображень

Шуми, їх властивості, методи зменшення впливу.

У останньому випадку компонентами сигналу можуть бути кольори – червоний (R), зелений (G), синій (B), або хроматичні складові Y - освітленість, Cr- теплі відтінки, Cb-холодні відтінки, або елементи простору HSV, головні компоненти PCA простору кольорів, або компоненти іншого простору кольорів.

До аддитивних відносяться, в основному, шуми, обумовлені властивостями чутливих елементів відео або фотокамер. Ці шуми виникають з наступних причин:

1. Дефекти (домішки та ін.) потенційного бар'єру, які викликають витік заряду, згенерованого за час експозиції - т. зв. чорний дефект. Такідефекти видно на світлому фоні у вигляді темних крапок.
2. Темновий струм (Dark current) - є шкідливим наслідком термоелектронної емісії і виникає в сенсорі при подачі потенціалу на електрод. Такі дефекти видно на темному тлі у вигляді світлих точок, це т. зв. білий дефект. Білі дефекти особливо проявляються при великих експозиціях. Основна причина виникнення темнового струму - це домішки в кремнієвій пластині або пошкодження кристалічної решітки. Чим чистіше кремній, тим менше темновий струм. На темновий струм впливає температура елементів камери і електромагнітні наводки. При збільшенні температури на 6-8 градусів, значення темнового струму подвоюється.
3. Шум, що виникає внаслідок стохастичної природи взаємодії фотонів світла з атомами матеріалу фотодіодів сенсора. Під час руху фотону усередині кристалічної решітки може виникнути ситуація, що фотон, «потрапивши» в атом кремнію, виб'є з нього електрон, народивши пару електрон-дірка. Електричний сигнал, що знімається з сенсора, буде відповідати кількості народжених пар.
4. Наявність дефектних (які не працюють) пікселів, які виникаютьпри виробництві фотосенсорів. Для усунення їх негативного впливу використовуються математичні методи інтерполяції, коли замість дефектного «підставляється» або просто сусідній елемент, або середнє по прилеглим елементам, або значення, обчислене більш складним чином. Природно, що обчислене значення відрізняється від фактичного і погіршує якість отриманого зображення.

Трохи про фільтри.

• Фільтр низких частот (low-pass filter)

  
  

• Фільтр високих частот (high-pass filter)

  
  

• Полосно-пропускаючий фільтр (band-pass filter)

  
  

• Полосно-обмежуючий фільтр (band-stop filter)

  
  

Препарування зображення

а	б	в
г	д	е
ж	з	и

Безумовно, ключовим у бінарізації є вибір порогу. Існує багато різних підходів до вибору порогу бінарізації, але найбільш популярним є метод Оцу (大津展之 ŌtsuNobuyuki).

Оригінальне зображення Lena	Бінарізація зображення Lena методом Оцу.

Просторові методи обробки зображень.

У загальному випадку просторова обробка зображення описується рівнянням: \[G(x,y)=T(I(x,y)),\] де \(G(x,y)\)- зображення на виході процедури обробки;
\(I(x,y)\) - вхідне зображення для обробки;
\(T\) - оператор системи обробки.

Градаційні методи покращення зображень.

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

Функція, яка описує солярізацію.

Солярізація зображення Lena.

Гамма-корекція яскравості.

По горизонталі - яскравість на вході, по вертикалі - на виході.

По горизонталі - яскравість на вході, по вертикалі - на виході.

Оригінальне зображення Lena.	Зображення після \(\gamma\)-корекції для \(\gamma=0.5\).	Зображення після сплайн-корекції.

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

Розглянемо методи покращення зображень шляхом корекції їх гістограм.

1. Лінійна корекція гістограм (лінійне контрастування) зводиться до зміни діапазону інтенсивності вхідного зображення, так, у разі наявності області освітлення [a,b], треба розтягнути його до [0,255], тобто \[\tilde{Y}_{i,j}=255\times \frac{Y_{i,j}-a}{b-a}.\]
2. Нормалізація гістограми передбачає не тільки зміну діапазону інтенсивності освітлення, але і їх найінформативніші значення. Ясно, що найінформативніші значення відповідають пікам гістограм. Значення гістограми, які відповідають значенням освітлення, що зустрічаються рідко, в процесі нормацізації викидаються, після чого проводиться лінійна корекція.
3. Інтуїтивно можна зробити висновок, що найбільш зручним для сприйняття людиною буде зображення, для якого гістограма близька до рівномірного розподілу. Тобто для поліпшення візуальної якості, до зображення треба застосувати таке перетворення, щоб гістограма результату містила всі можливі значення яскравості і при цьому в приблизно однаковій кількості. Таке перетворення називається еквалізацією гістограми.

1. Знаходимо гістограму зображення h.
2. Будуємо функцію розподілу \(F(x)=\sum_{i=1}^xh_i\) за гістограмою.
3. Обновлюємо пікселі зображення за правилом \[ f(x)=\textrm{round}\left(255×\frac{F(x)-F_\min}{W×H-1}\right). \]

Імпульсні шуми і заходи зменшення їх впливу.

1. Для кожної точки вхідного зображення береться деяка область (наприклад, \(3\times 3\)).
2. Точки даної області сортуються за зростанням яскравості.
3. Серединна (медіанна) точка (5-я для фільтра \(3\times 3\)) відсортованої множини записується в підсумкове зображення.
4. На наступному кроці вікно пересувається на один відлік і обчислення повторюються. Крайні значення масиву дублюються стільки раз, щоб можна було застосувати вікно до першого і до останнього значенням.

Алгоритм медіанної фільтрації.

Просторові методи фільтрації з використанням згортки.

1. Визначення центральної точки (x, y) околу;
2. Здійснення операції, яка використовує лише значення пікселів з заздалегідь обумовленої області навколо центральної точки;
3. Призначення результату цієї операції центральній точці;
4. Повторення всього процесу для кожної точки зображення. В результаті переміщення позиції центральної точки утворюються нові області, що відповідають кожному пікселю зображення.

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

Оригінальне зображення Cougar.	Згладжене зображення Cougar.

Методи зміни різкості зображень.

Методи, які використовують другі дискретні різниці.

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

Оригінальне зображення Cougar.	Результат застосування Лапласіана.

Градієнтні методи.

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

Оригінальне зображення Cougar.	Мапа змінності освітлення по горизонталі.	Мапа змінності освітлення по вертикалі.

Оригінальне зображення Cougar.	Інверсне зображення величини градієнта Cougar.	Мапа нормованного направлення градієнта Cougar.

Нерізке маскування.

Фільтрація з підйомом високих частот є узагальненням процедури нерізкого маскування. Ця операція зводиться до застосування правила контрастування виду \[ h(x, y)= k\cdot f (x, y) -\nabla^2f (x, y), \] за умови, що ваговий коефіцієнт у центрі фільтру менше нуля, інакше знак перед лапласіаном змінюється на протилежний. У такій ситуації підвищення різкості зображення може проводитися із застосуванням фільтрів \[ \left( \begin{array}{ccc} 0 & -1 & 0 \\ -1 &4+k & -1 \\ 0 & -1 & 0 \\ \end{array} \right) \hbox{ або } \left( \begin{array}{ccc} -1 & -1 & -1 \\ -1 &8+k & -1 \\ -1 & -1 & -1 \\ \end{array} \right). \]

Оригінальне зображення Cougar.	Застосування нерізкого маскування з маскою М1.	Застосування нерізкого маскування з маскою М2.

Побудова методів відновлення зображення.

Через \(\ell^2_2\) позначимо лінійний простір всіх обмежених двовимірних послідовностей (масивів) \(A=\{a_{i,j}\}_{(i,j)\in Z^2}\) з нормою \(\|A\|=\left(\sum_{i,j\in Z}a^2_{i,j}\right)^{1/2}\) і покладемо \(|A|=\left|\sum_{i,j\in Z}a_{i,j}\right|\).

Основою для побудови відновлюючих фільтрів є наступне твердження:

Як приклад розглянемо побудову контрастуючого фільтру псевдозворотного до згладжуючого фільтру S, побудованого раніше: \[ S=[s_{i,j}]_{i,j=-1}^1=\frac{1}{9}\left( \begin{array}{ccc} -1 & 2 & -1 \\ 2 &5 & 2 \\ -1 & 2 & -1 \\ \end{array} \right). \]

Згладжене зображення.	Результат після застосування зворотного фільтру першої ітерації.	Результат після застосування зворотного фільтру другої ітерації.	Результат після застосування зворотного фільтру третьої ітерації.
PSNR=27.26.	PSNR=32.08.	PSNR=35.53.	PSNR=37.96.

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

Для монохромних зображень I та K розміру H×W, одне з яких вважається зашумленими наближенням іншого, обчислюється наступним чином: \[ PSNR=20\times \rm{lg} \frac{\max \{I\}}{\sqrt{MSE}}, \] де \[ MSE=\frac{1}{H\times W}\sum_{i=1}^W\sum_{j=1}^H|I_{i,j}-K_{i,j}|^2. \] У разі порівняння повнокольорових зображень, використовуємо суму MSE по кожній кольоровій компоненті і поділемо на 3.

Морфологічна обробка бінарних зображень.

A	B

\(А\oplus В\) Розширення (dilation)	\(А\ominus В\) Звуження (erosion)	\((А\oplus В)\ominus В\) Відкриття (open)	\((А\ominus В) \oplus В\) Закриття (close)

Костел святого Миколая (м.Кам'янське) кінець ХІХ ст.

A	B

\(А\oplus В\) Розширення (dilation)	\(А\ominus В\) Звуження (erosion)

\((А\oplus В)\ominus В\) Відкриття (open)	\((А\ominus В) \oplus В\) Закриття (close)

Використання морфологічної обробки для знаходження контуру.

\(А\oplus В\) Розширення (dilation)	\(А\ominus В\) Звуження (erosion)

\((А\oplus В)\ominus В\) Відкриття (open)	\((А\ominus В) \oplus В\) Закриття (close)

Мета морфологічної обробки:

• Зниження шумів.
• Виділення меж об'єкта.
• Виділення кістяка об'єкта.
• Модифікація контурного представлення.

Сегментація зображень.

k-means

В основі даного підходу лежить метод кластеризації k-середніми (k-means) (див., наприклад, тут).

Алгоритм розбиття об'єктів \(x_i (i=0,1,…,n)\) заснований на мінімізації межкластерної відстані, у разі, якщо в якості відстані використовується середньоквадратична норма \(\ell_2\), тобто цільовою функцією є \[ J=\sum_{j=1}^k\sum\left\{\left.\|x_i-\mu_j\|^2\right|x_i\in C_j\right\}, \] де \(x_i\)-i -й об'єкт, а \(C_j\) являє собою j -й кластер із центром \(\mu_j\).

Структура алгоритму полягає в наступному:

1. Для ініціалізації алгоритму вибираємо k центрів кластерів.
2. Кожному з n об'єктів ставимо у відповідність кластер, виходячи з мінімізації \(\ell_2\) норми між об'єктом і центром відповідного кластера.
3. Перераховуємо центри знову отриманих кластерів.
   Для вирішення цього завдання серед усіх елементів кластера \(x\in C_j\) знайдемо елемент \(\mu_j\), який мінімізує ухилення \(\sum\left\{\left.\|x_i-\mu_j\|^2\right|x_i\in C_j\right\}\), для чого знайдемо розв'язок задачі \[ \frac{\partial}{\partial\mu_j}\sum_{x_i\in C_j}\|x_i-\mu_j\|^2=-2\sum_{x_i\in C_j}(x_i-\mu_j)=0, \] тобто \[ \mu_j=\frac{1}{n_j}\sum_{x_i\in C_j}x_i. \]
4. Для кожного \(i\) , такого, що \(x_i\in C_j\) обчислимо \[ h=\rm{argmin}\left\{\frac{n_j \|x_i-\mu_j\|}{n_j-1}\right\}, \] де \(n_j\) число об'єктів кластера \(C_j\).

5. Якщо виконується умова \[ \frac{n_h\|x_i-\mu_h\|}{n_h-1}\lt \frac{n_j\|x_i-\mu_j\|}{n_j-1}, \] то слід перемістити об'єкт \(x_i\) з кластеру \(C_j\) у кластер \(C_h\), після чого перерахувати значення центрів кластерів.

6. Якщо \(i\lt n\), то переходимо до кроку 4, інакше до кроку 3.

У нашому випадку для двох пікселів \(X(X_{red},X_{green}, X_{blue} )\) та \(Y(Y_{red},Y_{green}, Y_{blue} )\) відстань між ними дорівнює \[ \|X-Y\|^2=(X_{red}-Y_{red})^2+(X_{green}-Y_{green})^2+(X_{blue}-Y_{blue})^2 \] і колір пікселів всього кластеру \(C_j\) співпадає з кольором центру кластера \(\mu_j\).

EM-алгоритм.

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

ЕМ-алгоритм складається з послідовного застосування двох кроків.

У разі суміші нормальних розподілів \(N(\mu_i,\sigma_i^2)\) Е-крок буде виглядати наступним чином \[ g_{i,j}=\frac{\omega_ip_i(x_j)}{\sum_{\nu=1}^k\omega_\nu p_\nu(x_j)},i=1,…,k,j=1,…,n. \] де \[ p(x|\mu_i,\sigma_i)=\frac{1}{\sigma_i\sqrt{2\pi}}\exp\left(-\frac{(x-\mu_i)^2}{2\sigma_i^2}\right). \] Для М-кроку задача \[ \sum_{j=1}^ng_{i,j}\ln p_i(x_j)\to \max_{\Theta}, i=1,...,k, \] запишеться у наступному вигляді \[ \sum_{j=1}^ng_{i,j}\ln \left(\frac{1}{\sigma_i\sqrt{2\pi}}\exp\left(-\frac{(x-\mu_i)^2}{2\sigma_i^2}\right)\right)\to \max_{\Theta}, i=1,...,k, \] або,що теж саме \[ G\left(\left\{\mu_i,\sigma_i\right\}_{i=1}^k\right)=\sum_{j=1}^ng_{i,j} \left(-\ln\left(\sigma_i\sqrt{2\pi}\right)-\frac{(x-\mu_i)^2}{2\sigma_i^2}\right)\to \max_{\Theta}, i=1,...,k. \] Знайдемо похідні та прирівняємо їх до нуля \[ \frac{\partial}{\partial \mu_i}G\left(\left\{\mu_i,\sigma_i\right\}_{i=1}^k\right)=-\sum_{j=1}^ng_{i,j}\frac{x-\mu_i}{\sigma_i^2}=0, \] звідси \[ \mu_i=\frac{\sum_{j=1}^ng_{i,j}x_j}{\sum_{j=1}^ng_{i,j}}. \] Аналогічно, \[ \frac{\partial}{\partial \sigma_i}G\left(\left\{\mu_i,\sigma_i\right\}_{i=1}^k\right)= -\sum_{j=1}^ng_{i,j} \left(\frac{1}{\sigma_i}-\frac{(x-\mu_i)^2}{\sigma_i^3}\right)= -\sum_{j=1}^ng_{i,j} \left(\frac{\sigma_i^2-(x-\mu_i)^2}{\sigma_i^3}\right)=0, \] таким чином, \[ \sigma_i^2=\frac{\sum_{j=1}^ng_{i,j}(x-\mu_i)^2}{\sum_{j=1}^ng_{i,j}}, \] що дозволяє отримати параметри у явному вигляді.

Застосування ЕМ-алгоритму до сегментації зображень.

Вважаючи, що кожна гістограма являє собою суміш функцій Гаусса \[ \sum_{i=1}^n\frac{\omega_i}{\sigma_i\sqrt{2\pi}}\exp\left(-\frac{(x-\mu_i)^2}{2\sigma_i^2}\right) \] застосуємо ЕМ-алгоритм із заданою кількістю елементів суміші n (це ж кількість сегментів, на яке ми розбиваємо кожну колірну площину зображення). І як результат, нехай множина значень інтенсивності \(X_j=(x_j,x_{j+v_j }\) ) така, що \[ \forall x\in X_j: \frac{\omega_j}{\sigma_j\sqrt{2\pi}}\exp\left(-\frac{(x-\mu_j)^2}{2\sigma_j^2}\right)\ge \frac{\omega_i}{\sigma_i\sqrt{2\pi}}\exp\left(-\frac{(x-\mu_i)^2}{2\sigma_i^2}\right) (i\ne j). \] Тоді всім точкам, інтенсивність яких лежить в проміжку \(X_j\). Поставимо у відповідність значення \(\mu_j\) (при практичній реалізації - її цілу частину). Результатом роботи алгоритму буде сегментація зображення на n сегментів по кожній колірної компоненті.

EM-алгоритм для випадку двох змінних.

Як видно з розглянутого ЕМ-алгоритму, у разі використання даних двох змінних (i,j,r_(i,j) ), (i,j,g_(i,j) ), (i,j,b_(i,j) ) кожну з множин можна описати лінійною комбінацією двовимірних функцій Гауса \[ \frac{1}{2\pi|\Sigma_i^{-1}|^{1/2}}\exp\left(-\frac{1}{2}(x-\mu_i)^T\Sigma_i^{-1}(x-\mu_i)\right) \] за допомогою ЕМ-алгоритму аналогічно тому, як було зроблено у одновимірному випадку.

Порогова і мультіпорогова сегментація.

Порогова сегментація виконується наступним чином: \[ Bin_{i,j}= \left\{ \begin{array}{ll} 1, & \hbox{якщо }I_{i,j}\ge T,\\ 0, & \hbox{якщо }I_{i,j}\lt T, \end{array} \right. \] де \(Bin_{i,j}\) - елемент результуючого бінарного зображення, \(I_{i,j}\)- елемент вихідного зображення.

Мультіпороговая сегментація.

Про побудову асимптотически оптимальних гістограм.

Нехай \(X_1,X_2,...,X_N\)-вибірка заданого розподілу, розбиття \(\Delta_n=\{-\infty\lt x_0\lt x_1\lt ...\lt x_n\lt \infty\}\) із кроком \(h_{i-1/2}=x_i-x_{i-1}\) і \(m_i=\sum_{i=1}^N\left\{1\left|X_k\in (x_{i-1},x_{i}]\right.\right\},i=1,...,n\) число елементів вибірки з i-го інтервалу. Тоді кусково-постійна функція \(H:R\to R\) \[ H(x)=H(\Delta_n,x)=m_i,x\in (x_{i-1},x_i],i=1,2,...,n \] називається гістограмою вибірки \(X_1,X_2,...,X_N\), якщо ж кусочно-постійна функція \(\hat{H}:R\to R\) така, що \[ \hat{H}(x)=\hat{H}(\Delta_n,x)=\frac{m_i}{Nh_{i-1/2}},x\in (x_{i-1},x_i],i=1,2,...,n, \] то вона називається нормалізованою гістограмою. Помітимо, що нормалізована гістограма є функцією щільності ймовірності, тому що \[ \hat{H}(t)\ge 0 \hbox{ при } t\in R \hbox{ і, крім того, }\int_{-\infty}^\infty \hat{H}(t)dt=1. \] Для абсолютно неперервних розподілів випадкових величин із щільністю ймовірності \(f(x)\) для нормалізованих гістограм при \(N\to\infty\) \[ \forall x\in (x_{i-1},x_i], \hat{H}(x)=\frac{m_i}{Nh_{i-1/2}}\to P\left(X\in (x_{i-1},x_i]\right)\equiv \int_{x_{i-1}}^{x_i}f(x)dx,i=1,2,...,n. \] Таким чином, для неперервної випадкової величини, гістограма на кожній ділянці свого постійного значення повинна зберігати середнє значення. Традиційно розглядаються гістограми з рівновіддаленими вузлами, але вибір вузлів гістограмы істотно впливає на якість опису випадкового процесу. Розглянемо задачу побудови гістограми з асимптотично оптимальними вузлами.

Для функції \(y(x)\) , неперервної на [0,T], розглянемо задачу \[ \varepsilon=\min_{x_i}\min_{a_{i+\frac{1}{2}}}\sum_{i=0}^{n-1}\int_{x_i}^{x_{i+1}}\left(a_{i+\frac{1}{2}}-y(x)\right)^2dx. \] Теорема 1. Нехай \(y(x)\)- неперервно диференційована функція \(y\in C^2_{[0,T]}\) така, що \(y'(x)\) на проміжку \([0,T]\) має не більше скінченного числа нулів, тоді \[ \varepsilon=\frac{1}{12n^2}\left(\int_0^T\left(y'(x)\right)^{\frac{2}{3}}dx\right)^3+O\left(\frac{1}{n^3}\right) \] і при цьому мінімум досягається для розбиття \(\Delta^*_n=\{x^*_i\}_{i=0}^n\) такого, що \[ \int_{x^*_i}^{x^*_{i+1}}\left(y'(x)\right)^{\frac{2}{3}}dx=\frac{1}{n}\int_0^T\left(y'(x)\right)^{\frac{2}{3}}dx \hbox{ і } a_{i+\frac{1}{2}}^*=\frac{1}{h^*_{i+\frac{1}{2}}}\int_{x^*_i}^{x^*_{i+1}}y(x)dx. \] Доведемо це твердження. На початку розглянемо наступну задачу \[ \Phi\left(a_{i+\frac{1}{2}}\right)=\int_{x_i}^{x_{i+1}}\left(a_{i+\frac{1}{2}}-y(x)\right)^2dx\to\min_{a_{i+\frac{1}{2}}}. \] Тоді зважаючи на опуклість задачі, необхідна умова мінімума є і достатньою, тобто, розв’язок цієї задачі знаходиться з рівняння \[ \frac{d}{da_{i+\frac{1}{2}}}\Phi\left(a_{i+\frac{1}{2}}\right)=2\int_{x_i}^{x_{i+1}}\left(a_{i+\frac{1}{2}}-y(x)\right)dx=0, \] і тоді, \[ a_{i+\frac{1}{2}}=\frac{1}{h_{i+\frac{1}{2}}}\int_{x_i}^{x_{i+1}}y(x)dx. \] Таким чином, первісну задачу можна переписати у вигляді \[ \varepsilon=\min_{x_i}\sum_{i=0}^{n-1}\int_{x_i}^{x_{i+1}}\left(y(x)-\frac{1}{h_{i+\frac{1}{2}}}\int_{x_i}^{x_{i+1}}y(x)dx\right)^2dx. \] Використовуючи формулу Тейлора \[ y(x)=y_{i+\frac{1}{2}}+y'_{i+\frac{1}{2}}\left(x-x_{i+\frac{1}{2}}\right)+O(h^2), \] де \(h=\max_ih_{i+\frac{1}{2}}\), отримуємо \[ \varepsilon=\min_{x_i}\sum_{i=0}^{n-1}\int_{x_i}^{x_{i+1}}\left(y_{i+\frac{1}{2}}+y'_{i+\frac{1}{2}}\left(x-x_{i+\frac{1}{2}}\right)+O(h^2) -\frac{1}{h_{i+\frac{1}{2}}}\int_{x_i}^{x_{i+1}}\left(y_{i+\frac{1}{2}}+y'_{i+\frac{1}{2}}\left(x-x_{i+\frac{1}{2}}\right)+O(h^2)\right)dx\right)^2dx= \] \[ =\min_{x_i}\sum_{i=0}^{n-1}\int_{x_i}^{x_{i+1}}\left(y_{i+\frac{1}{2}}+y'_{i+\frac{1}{2}}\left(x-x_{i+\frac{1}{2}}\right)- y_{i+\frac{1}{2}}+O(h^2)\right)^2dx= \min_{x_i}\frac{1}{12}\sum_{i=0}^{n-1}\left(\left(y'_{i+\frac{1}{2}}\right)^2h^3_{i+\frac{1}{2}}+O(h^4)\right). \] Із теореми про середнє для інтегралів маємо, що знайдеться точка \(\xi_{i+\frac{1}{2}}\in [x_i,x_{i+1}]\) така, що \[ \left(y'\left(\xi_{i+\frac{1}{2}}\right)\right)^2h^3_{i+\frac{1}{2}}= \left(\left(y'\left(\xi_{i+\frac{1}{2}}\right)\right)^{\frac{2}{3}}h_{i+\frac{1}{2}}\right)^3= \left(\int_{x_i}^{x_{i+1}}\left(y'(x)\right)^{\frac{2}{3}}dx\right)^3, \] Звідси і із попереднього одразу маємо \[ \varepsilon=\min_{x_i}\frac{1}{12}\sum_{i=0}^{n-1}\left(\left(y'_{i+\frac{1}{2}}\right)^2h^3_{i+\frac{1}{2}} +\left(y'\left(\xi_{i+\frac{1}{2}}\right)\right)^2h^3_{i+\frac{1}{2}}- \left(y'\left(\xi_{i+\frac{1}{2}}\right)\right)^2h^3_{i+\frac{1}{2}} +O(h^4)\right)=\min_{x_i}\frac{1}{12}\sum_{i=0}^{n-1}\left(\left( \int_{x_i}^{x_{i+1}}\left(y'(x)\right)^{\frac{2}{3}}dx\right)^3+O(h^4)\right). \] Лема. Нехай \(\alpha\gt 0\) і \(C\gt 0\), тоді \[ \min\left\{\sum_{i=0}^{n-1}C^\alpha_i|C_i\ge 0,\sum_{i=0}^{n-1}C_i=C\right\}=n\left(\frac{C}{n}\right)^\alpha, \] і при цьому мінімум досягається тоді, коли всі \(C_i\) рівні між собою, тобто, \[ C^*_i=\frac{C}{n},i=0,...,n-1. \] Для доведення цього твердження використаємо метод невизначених множників Лагранжу.

Випишемо функцію мети \[ \mathfrak{L}=\lambda_0\sum_{i=0}^{n-1}C_i^\alpha+\lambda_1\left(\sum_{i=0}^{n-1}C_i-C\right), \] тоді \[ \frac{\partial\mathfrak{L}}{\partial C_i}=\lambda_0\alpha C_i^{\alpha-1}+\lambda_1=0, \] і \(\lambda_0\alpha(C_i^{\alpha-1}+\lambda_2)=0,\) де \(\lambda_2=\frac{\lambda_1}{\lambda_0\alpha}\).

Лема доведена.

Ідея отриманого результату складається в тому, що вузли розподіляються таким чином, щоб похибки наближення на кожному відрізку функції \(x(t)\) кусково-постійною функцією \(S\left(\left\{a_{i+\frac{1}{2}}\right\}_{i=1}^{n-1},\Delta_n,x\right)\) будуть рівні між собою.

Алгоритм вибору асимптотично оптимальних порогів сегментації.

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

Простий алгоритм заповнення із затравкою.

Простий алгоритм заповнення
	Затравка(х, у) видає затравочний піксел.
	Push - процедура, яка вкладає піксел в стек.
	Pop - процедура, яка виймає піксел зі стека.
Піксел(х, у) = Затравка(х, у)
Push Піксел(х, у)  ; ініціалізація стеку
While (стек не пустий)
	Pop Пиксел(х, у)  ; виймаємо піксел зі стека
	If Пиксел(х, у) <> Нов_значенняthen
		Пиксел(х, у) = Нов_значення
	End if
	Перевірка, чи треба вкладати сусідні пікселі у стек
	If (Піксел(х + 1, у) <> Нов_значення and
		Піксел(х + 1, у) <> Гран-значення)then
			Push Піксел (х + 1, у)
	If (Піксел(х, у + 1) <> Нов_значення and
		Піксел(х, у + 1) <> Гран_значення)then
			Push Пиксел (х, у + 1) 
	If (Піксел(х - 1, у) <> Нов_значення and
		Піксел(х - 1, у) <> Гран_значення)then
			Push Піксел (х - 1, у)
	If (Піксел(х, у - 1) <> Нов_значення and
		Піксел(х, у - 1) <> Гран_значення)then
			PushПіксел (х, у - 1) 
	End If 
EndWhile

Алгоритм водорозділу.

Крок перший – бінарізація.

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

Суперпіксельна сегментація.

Проста лінійна ітераційна кластеризація (SLIC) є адаптацією k-середніх для генерації суперпікселів з двома важливими відмінностями:

1. Оптимізація кількісті розрахунків відстані значно скорочується шляхом обмеження простору пошуку на область, пропорційну розміру суперпікселя. Це робить складність лінійною за кількістю пікселів N і незалежним від числа суперпікселів k.
2. Міра зваженої відстані поєднує в собі колірну і просторову близькість, одночасно забезпечуючи контроль за розміром і компактністю суперпікселів.

SLIC простий у використанні та розумінні. За замовчуванням єдиним параметром алгоритму є параметр k - бажана кількість суперпікселів приблизно рівного розміру. Для кольорових зображень у колірному просторі CIELAB процедура кластеризації починається з етапу ініціалізації, де k стартових центрів кластерів \(C_i = [l_i a_i b_i x_i y_i]^T\) вибираються на регулярній сітці, з кроком на S пікселів. Для отримання приблизно однакових розмірів суперпікселів, інтервал сітки вибираємо \(S=\sqrt{\frac{N}{k}}\). На кожній ітерації центри переміщуються на місце, що відповідає найменшій позиції градієнта в околі 3 × 3 пікселя \[ G(x,y)=\|I(x+1,y)-I(x-1,y)\|^2+\|I(x,y+1)-I(x,y-1)\|^2, \] де \(I(x,y)\) lab вектор, що відповідає пікселю з позицією (x,y) та \(\|\cdot\|\) норма \(L_2\).

Як тільки кожен піксель асоціюється з найближчим центром кластера, крок оновлення регулює центри кластера як середнього вектору \([l a b x y]^Т\) всіх пікселів, що належать кластеру.

Алгоритм SLIC суперпіксельної сегментації
/  Ініціалізація /
		Ініціалізація центрів кластерів Ck = [lk ak bk xk yk]T - вибірка пікселів на регулярній  сітці з кроком S.
		Перемістити центри кластера в найнижчу позицію градієнта в околі 3 × 3.
		Встановити мітку l (i) = −1 для кожного пікселя i.
		Встановити відстань d (i) = ∞ для кожного пікселя i.
repeat
/  Призначення /
for кожного кластерного центру Ck do
	for кожного пікселя i в області 2S × 2S навколо Ck do
		Обчислити відстань D між Ck та i.
			if D < d (i) then
				множина d (i) = D
				множина l (i) = k
			end if
	end for
end for
/  Оновлення /
Обчислити нові центри кластерів.
Обчислення залишкової помилки E.
until  E ≤ порогу

Міра відстані.

Просто визначення D як п'ятивимірної евклідової відстані у просторі labxy призведе до невідповідності у кластеризації. Для великих суперпікселів просторові відстані перевершують колірну близькість, надаючи більш відносне значення просторовій близькості, ніж колір. Це продукує компактні суперпікселі, які не добре дотримуються меж зображення. Для дрібних суперпікселів є вірним зворотне.

Нехай \[ d_c=\sqrt{(l_j-l_i)^2+(a_j-a_i )^2+(b_j-b_i )^2 }, \] \[ d_s=\sqrt{(x_j-x_i )^2+(y_j-y_i )^2 }, \] \[ D'=\sqrt{\left(\frac{d_c}{N_c} \right)^2+\left(\frac{d_s}{N_s} \right)^2 }. \] Максимальна просторова відстань, що очікується в межах даного кластера повинна відповідати інтервалу вибірки, \(N_s=S=\sqrt{\frac{N}{K}}\). Визначення максимальної відстані кольору \(N_c\) не так просте, оскільки кольорові відстані можуть істотно відрізнятися від кластера до кластера і від зображення до зображення. Цієї проблеми можна уникнути, замінивши \(N_c\) на константу m, тоді \[ D'=\sqrt{\left(\frac{d_c}{m} \right)^2+\left(\frac{d_s}{S} \right)^2 }. \] що спрощує вимірювання відстані. На практиці використовується значення відстані \[ D=\sqrt{\left(d_c \right)^2+m^2\left(\frac{d_s}{S} \right)^2 }. \] Визначаючи D таким чином, m також дозволяє зважувати відносну важливість між колірною подібністю і просторовою близькістю. Коли m є великим, просторова близькість є більш важливою і результуючі суперпікселі є більш компактними (тобто вони мають більш низьке співвідношення області до периметра). Коли m є малим, отримані суперпікселі щільніше прилипають до меж зображення, але мають менший розмір і форму. При використанні колірного простору CIELAB параметр m змінюється у діапазоні \(m\in [1; 40]\), але, як правило, вибирається значення m=20.

Кількість сегментів 200, m=10.	Кількість сегментів 200, m=40.

Кількість сегментів 200, m=20.	Кількість сегментів 20, m=20.

Текстурна сегментація за фрактальними характеристиками.

Фрактали і фрактальна розмірність.

У найпростішому випадку невелика частина фракталу містить інформацію про весь фрактал. Строге визначення самоподібних множин було дано Дж. Хатчинсоном (J. Hutchinson) в 1981 році. Він назвав множину самоподібною, якщо воно складається з декількох компонентів, подібних всій цій множині, тобто компонент одержуваних афінними перетвореннями.

Нехай є множина G в евклідовому просторі розмірності r. Ця множина покривається кубиками тієї ж розмірності, при цьому довжина ребра будь-якого кубика не перевищує деякого значення δ , тобто \(\delta_i\lt \delta\).

Незважаючи на те, що розмірність Хаусдорфа-Безиковича з теоретичної точки зору визначена бездоганно, для реальних фрактальних об'єктів розрахунок цієї розмірності єдосить скрутним. Тому вводиться трохи спрощений показник - ємнісна розмірність \(d_c\).

Методи оцінювання фрактальності кольорових/напівтонових зображень.

Метод Triangular Prism Surface Area.

Алгоритм полягає в наступному.

Подібна процедура повторюється для всіх пікселів зображення. Для фіксованого r площі всіх фігур формують одну загальну площу A.

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

Метод 2D Variation призначений для обробки бінарних (binary) і напівтонових (grayscale) зображень.

Тоді \(V(r)=r^sconst\), де V - «різницевий» об'єм фігури r - крок сітки, S- фрактальна розмірність.

Нахил s графіка V(r) у логарифмічному масштабі використовується для визначення фрактальної розмірності: \[ D_{2D}=3-\frac{s}{2}. \] Даний метод при роботі з кольоровими зображеннями також як і TPSA дозволяє оцінювати як розмірність кожного колірного каналу RGB окремо, так і розмірність "яркостного” зображення.

Ще одним методом оцінювання фрактальной розмірності напівтонових зображень є броуновская розмірність, що пропорційна експоненті Херста (Hurst`s exponent) D=3-H.

Алгоритм обчислень виглядає в такий спосіб: для всіх точок обчислюються прирости яскравості \(\Delta I\) в \(\Delta R\)-околі, для отриманого масиву приростів обчислюється середньоквадратичне відхилення \(\sigma_{\Delta R}(\Delta I)\), потім змінюємо \(\Delta R\) і повторюємо попередні кроки.

Даний метод при роботі з кольоровими зображеннями також як і TPSA і 2D Variation Procedure дозволяє оцінювати як розмірність кожного кольору RGB окремо, так і розмірність "яркісного" зображення.

Що до практичного використання фрактальних характеристик, то це можна знайти тут.

Використані зображення

Найпопулярніша жінка у фахівців з комп’ютерної графіки – Lena Soderberg (з обкладинки журналу Playboy за листопад 1972 р.)

Костел святого Миколая (Кам'янське) кінець ХІХ ст.

Cougar. Кугуар або пума. Кішка, красива до смерті.

Зображення Superfood. Мрія вегана.

Клітини букального епітелію. (Архів цитопрепаратів крові та кісткового мозку, відділ онкогематології ІЕПОР НАНУ).