Бинаризация на изображение

Бинаризация и контури

Бинаризация

Бинаризация - що е то?

Често се налага в практиката от дадена снимка да се отдели 'обекта' от 'фона' (object / background). Как точно се дефинират 'обект' и 'фон' не е много ясно - най-малкото представете си, че снимате морето и точно преди да снимате някой човек влезе в кадър - в този случай морето е обект, а човекът е фон :) При алгоритмите, които ще разглеждаме, изображението ще бъде полутоново, с интензитет на пикселите в интервала $I(x, y) \in [0 ,L]$, а бинаризацията му ще се състои в оцветяване на всеки пиксел $I'(x, y) \in \{ 1, 0 \}$ или в черно, или в бяло (т.е черните пиксели ще бъдат обект, белите ще бъдат фон, каквото и да значи това).

Threshold

Има много алгоритми за отделяне на обекти от изображения - в тази лекция ще се спрем на един сравително прост. Основната идея е да се намери число $T$ (на английски threshold, на български праг/граница) и всички по-тъмни от него пиксели да стават обект, а всички по-светли - фон:

(1)
\begin{eqnarray} & & 0 \le T \le L \\ & & I(x, y) > T \Rightarrow I'(x, y) = 1 \\ & & I(x, y) \le T \Rightarrow I'(x, y) = 0 \\ \end{eqnarray}

Както може да се досетите, възниква интересният въпрос как точно да се избира тази стойност $T$, така че най-правилно да сме отделили обекта от фона.
Първо ще дефинираме няколко функции:

  • Хистограма на изображението - хистограмата е функция, която по подаден интензитет връща броя на всички пиксели имащи точно този интензитет.
(2)
\begin{align} h(z) = \# \{ I(x, y) | I(x, y) = z \} \quad z \in [0, L] \end{align}
Хистограма $h(z) = \# \{ I(x, y) | I(x, y) = z \} \quad z \in [0, L]$
Брой пиксели от обекта $n_o (T) = \underset{z = T+1}{\overset{L}\sum} h(z)$
Брой пиксели от фона $n_b (T) = \underset{z = 0}{\overset{T}\sum} h(z)$
Средна стойност на интензитета на обекта $m_o = \dfrac{\underset{z = T+1}{\overset{L}\sum} zh(z)}{n_o(T)}$
Средна стойност на интензитета на фона $m_b = \dfrac{\underset{z = 0}{\overset{T}\sum} zh(z)}{n_b(T)}$

Дефинираме си и следната много важна функция на цветовата дисперсия:

(3)
\begin{align} \sigma(T) = n_b(T) n_o(T) \Big[ m_b(T) - m_o(T) \Big]^2 \end{align}

и сега вече избираме това $T$ което максимизира $\sigma(T)$:

(4)
\begin{align} T : \sigma(T) \to \max \end{align}

Идеята за този threshold е на японеца Otsu.

otsu

По $x$ е нанесен интензитетът, по $y$ - броят пиксели (това е хистограма). Ако е бимодална (т.е има 2 върха) алгоритъмът трябва да даде падината между 2та хълма.

Dithering (разпространяване на грешката)

След като си бинаризирахме изображението искаме да изгладим ръбовете - т.е да направим така, че някои от пикселите, които стоят на границата да преминат от обекта във фона и обратно, с цел по-голямо естетическо удовлетворение. Видимият ефект е изображение с донякъде размити контури. Положителните страни са, че се премахват визуални артефакти в некачествени изображения и се повишава качеството в такива с малко на брой цветове (например 256). Лошото е, че при хубавите снимки ефектът е обратен - стават ненужно размазани.
Dithering е добра идея за снимка в MySpace, лоша за залез край морето.

От наистина многото алгоритми за правене на едно изображение по-грозно, ще се спрем подробно на най-популярния. Алгоритъмът на Флойд-Щайнберг.
Идеята е подобна на филтрирането - ще използваме матрицата:

(5)
\begin{align} \frac{1}{16}\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 7 \\ 3 & 5 & 1 \\ \end{matrix} \end{align}

Когато решим даден пиксел да бъде обект/фон ние фактически му променяме интензитета или на плътно черно (т.е 0) или на абсолютно бяло (т.е $L$). Обаче има някаква вероятност да сме избрали грешно дали пикселът е част от фона или от обекта. Така за почти всеки пиксел има дадена грешка (т.е разликата между новата и старата му стойност). За да се сведат до минимум неточните резултати, разпределяме грешката в околните пиксели - точно това е размазването, което прави филтърът. По този начин е възможно част от пикселите, които се намират на границата до $T$ (и близо до нея) да си променят положението (фон/обект).
Какво всъщност прави този алгоритъм?

  • Първото му важно свойство е, че при обхождане на изображението отгоре-надолу и отляво-надясно, никога не пипаме вече разгледани пиксели - всичко се слага надолу и надясно. Няма нужда да се връщаме назад и това го прави по-бърз за смятане.
  • Освен това, ако например T = 128, черно = 0, бяло = 255 и I(x,y) = 127, то рисуваме пиксела черен, но въобще не е сигурно, че той трябва да е такъв - на ръба е. Грешката му е 127. Затова, в известен смисъл, слагаме "повече бяло" на съседните му пиксели. Ако и те са на ръба, то ще станат бели и неточният резултат в (x,y) ще бъде компенсиран. По същия начин, ако изображението е бяло, на съседните се "добавя" черно. Това може да бъде направено да работи и за повече от два цвята - единственото условие е да може да бъде дефинирана мярка за разстояние между два цвята.

Ще демонстрираме с малко псевдокод:

for y in (N, 0]:
    for x in [0,M):
        if (I(x, y) <= T) pix = 0; // black
        else pix  = L; // white
        err = min(I(x, y), L - I(x,y))
        I(x, y) = pix;
        I(x + 1, y) += 7 * err / 16;
        I(x - 1, y + 1) += 3 * err / 16;
        I(x, y + 1) += 5 * err / 16
        I(x + 1, y + 1) += err / 16;

Защо числата са избрани точно такива? Попитайте Флойд и Щайнберг1.

Контур

Контур - що е то?

Контур са пикселите, които се намират на границата между обекта и фона (това понятие е тясно свързано с бинаризацията).
Ще разгледаме 2 алгоритъма за намиране на контур - единият ползва бинаризация като първа стъпка, а вторият го намира директно.

Код на Фриймън

Кодът на Фриймън (Freeman) описва последователните посоки на контура разгледан по положителната/отрицателната посока. (но няма нищо общо с намирането на самия контур - чети по-надолу за да видиш как става).
За да стане по-ясно ще си номерираме посоките и ще дам един малък пример
freeman_dir
freeman_outline
Започваме от червеното квадратче и се движим по часовниковата стрелка. Ако запишем номерата на посоките за преминаване на всяко квадратче към следващото ще получим следната редица:

(6)
\begin{equation} 3, 2, 1, 0, 1, 7, 6, 7, 5, 4, 5, 3 \end{equation}

Ако започнем от друго квадратче ще получим същата редица, но ротирана (т.е ще започва от средата на тази и като стигне до края ще продължи от началото).
Също интерес представлява диференциалният код на Freeman, при който не се записва кода на посоката от едно квадратче от контура към следващото ами се записва разликата по модул между предишната и новата посока. Това позволява 2 контура, завъртяни на ъгъл кратен на 45 градуса да се считат за еднакви. Пример за релативен код на Freeman от горните квадратчета:

(7)
\begin{equation} 7, 7, 7, 1, 6, 7, 1, 6, 7, 1, 6, 0 \end{equation}

За да се провери дали 2 контура са еднакви или даже се различават с мащабиране (т.е единият контур е просто умалена версия на другия) може да се направи хистограма на двата кода (т.е колко често се употребява дадена посока) и после да се провери дали честотите за отделните посоки са пропорционални. Това, разбира се, не познава на сто процента дали два контура са подобни. Но има свойството, че ако са мащабирани (т.е единия е увеличен/умален вариант на другия) - със сигурност ще го познае!

Разбира се кодът на Freeman само описва контура. Ако искате да го получите трябва първо да бинаризирате и после да използвате някой от филтрите които взехме предния час, за да намерите границите между отделните части на картината (първо намирате границите по $x$, после по $y$ и накрая с побитово ИЛИ ги слагате една върху друга).

Zero-crossing

Това е метод, чрез който директно се получава контурът (без предварителна бинаризация). Името му е толкова банално, че няма накъде повече. Идва от електрониката, където се има предвид пресичането на оста Ox от графиката на синусоида. Нас ни интересуват точките, в които функцията на интензитета (I) пресича някаква предварително дефинирана стойност. Тоест, Threshold-a. Точно там, както може да се очаква, има контур. Но тук все още нямаме Threshold и първо трябва да се изчисли функцията на интензитета. Има доста работа свършена по този въпрос и са известни функции, с които се получава по-точно изображение, отколкото с тривиалното $f(x,y) = 1$.

В този момент лекторът или изпадна в мозъчна смърт, или започна да обяснява алгоритъма, така и не разбрах. Във всеки случай, за по-смелите следват факти, които са верни, но им липсва каквото и да е обяснение или доказателство.

След като пуснем филтъра (който в крайна сметка е просто още един конволюционен филтър, каквито вече сме използвали), минаваме по веднъж през всеки ред от получената матрица и правим нужните замени. Всеки път, когато се сменят бяло и черно, поставяме единица - иначе нула. В долния код + означава бяло, а - - черно.

стара + + + + - - - - + + + + + - - - - - + + + - + + + +
нова  0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0

Накрая единиците са търсения контур. Разбира се, има логика да се направи и код на Freeman за получения резултат. Всъщност, в този алгоритъм няма нищо кой знае колко сложно и единствената значима част е по какъв точно начин избираме да си направим първоначалния филтър. Което, разбира се, си го оставихме за друг път :)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License