Лекциите на ФМИ

За да изглеждаме умни пред другите

Начало

Начална страница

Членове на
сайта

Присъедини
се

За автори

Препоръки за писане на
статии

Формат на статиите

Форум

Новини от
форума

Последни
промени

Списък със
задачи

Първи курс

Анализ

ЕАИ

Геометрия

ООП

Втори курс

Структури от Данни

Компютърни Архитектури

КАрх - Практикум

Основи на компютърната
графика

Функционално програмиране

ФП - Практикум

Трети курс

Логическо програмиранеУпражнения

Числени методиУпражнения

Системно
програмиранеУпражнения

Мрежово
програмиранеУпражнения

За
администратори

Create account or Sign in

Начало

Начална страница

Членове на сайта

Присъедини се

За автори

Препоръки за писане на
статии

Формат на статиите

Последни
промени

Панел за
администратори

Лекции

Първи Курс

Анализ

ЕАИ

Геометрия

ООП

Втори курс

Структури от Данни

Компютърни Архитектури

КАрх - Практикум

Основи на компютърната
графика

Функционално програмиране

ФП - Практикум

Трети курс

Логическо програмиранеУпражнения

Числени методиУпражнения

Системно
програмиранеУпражнения

Мрежово
програмиранеУпражнения

Избираеми дисциплини

Математическа Логика

Дискретна Оптимизация

Теория на Множествата

Теория на Графите

Избрани Глави от
Анализа

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

ФМИ за начинаещи
» Основи на компютърната графика »
Бинаризация на изображение

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

foldunfold

Table of Contents

Бинаризация

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

Threshold

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

Контур

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

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

Zero-crossing

Бинаризация

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

Често се налага в практиката от дадена снимка да се отдели 'обекта'
от 'фона' (object / background). Как точно се
дефинират 'обект' и 'фон' не е много ясно - най-малкото представете си, че
снимате морето и точно преди да снимате някой човек влезе в кадър - в този
случай морето е обект, а човекът е фон :) При алгоритмите, които ще разглеждаме,
изображението ще бъде полутоново, с интензитет на пикселите в интервала
,
а бинаризацията му ще се състои в оцветяване на всеки пиксел
или в черно, или в бяло (т.е черните пиксели ще бъдат обект, белите ще бъдат
фон, каквото и да значи това).

Threshold

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

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

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

(2)

Хистограма

Брой пиксели от обекта

Брой пиксели от фона

Средна стойност на интензитета на обекта

Средна стойност на интензитета на фона

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

и сега вече избираме това
което максимизира :
(4)

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

виж най-дългото изречение на планетата

скрии най-дългото изречение

Естествено, тук е дадена в опростен за ползване вид, като телевизионна
реклама - "просто добави променлива". Формулата има за цел да минимизира
смесената вариация на променливите, която е дефинирана като претеглена линейна
комбинация на вариацията на всяка променлива. Вариацията на една функция е
отклонението от очакваната стойност (медианата), повдигнато на квадрат. След
като се разпишат формулите, получава се хубавата формула горе, което е и
приносът на Otsu по темата.

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

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

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

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

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

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

Освен това, ако например 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) описва последователните посоки на контура
разгледан по положителната/отрицателната посока. (но няма нищо общо с намирането
на самия контур - чети по-надолу за да видиш как става).
За да стане по-ясно
ще си номерираме посоките и ще дам един малък пример

Започваме
от червеното квадратче и се движим по часовниковата стрелка. Ако запишем
номерата на посоките за преминаване на всяко квадратче към следващото ще получим
следната редица:
(6)

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

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

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

Zero-crossing

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

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

Осмелявам се

Мъдро решение

Ще използваме функцията, характеризираща преливане на цветове (градиент)
наготово. От нея ще изведем една формула, с която ще попълним матрица, която ще
използваме за филтър, който е първата част от алгоритъма :)
(8)

След това на тази функция се взема втората производна… защото така
(9)

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

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

стара + + + + - - - - + + + + + - - - - - + + + - + + + +
нова 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 за получения резултат. Всъщност, в този алгоритъм няма нищо кой
знае колко сложно и единствената значима част е по какъв точно начин избираме да
си направим първоначалния филтър. Което, разбира се, си го оставихме за друг път
:)

Footnotes

1. моля не им разкопавайте гроба - не
вярвам да проговорят :)

page_revision: 14, last_edited: 1229162626|%e %b %Y, %H:%M %Z (%O ago)

EditRate
(0)TagsDiscuss History Files
Print Site tools+ Options

Edit sections Append Edit meta Watchers Backlinks Page source Parent Lock
page Rename Delete

Help | Terms
of Service | Privacy | Report a bug | Flag as objectionable
Powered by Wikidot.com

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

Click here to edit contents of this page.

Click here to toggle editing of individual
sections of the page (if possible). Watch headings for an "edit" link when
available.

Append content without editing the whole
page source.

Check out how this page has evolved in the past.

If you want to discuss contents of this page -
this is the easiest way to do it.

View and manage file attachments for this page.

A few useful tools to manage this Site.

See pages that link to and include this page.

Change the name (also URL address, possibly
the category) of the page.

View wiki source for this page without
editing.

View/set parent page (used for creating
breadcrumbs and structured layout).

Notify administrators if there is
objectionable content in this page.

Something does not work as expected? Find out
what you can do.

General Wikidot.com documentation and help
section.

Wikidot.com Terms of Service - what you can,
what you should not etc.

Wikidot.com Privacy Policy.