Хитри алгоритми

Кажете някъв хитър алгоритъм за намиране на контур на изображение в битмап например, като се знае, че в битмапа има само два цвята col1 и col2. Например син фон и един червен кръг посредата, като преди това уточним:
линия е последователност от точки, като всяка от тях има по два непосредствени съседа, освен първата и последната.
контур е линия, на която първата и последната точка съвпадат.

За който не знае:
1 2 3
4 Х 5
6 7 8

непосредствени съседи на точката Х са 2,4,5 и 7.

Доколкото знам повечето алгоритми за edge detection първо намират първата производна на образа като по този начин от образа остават само ръбовете всичко останало се премахва, а след това с някакви други методи търсят линии. В твоя случай би трябвало да установиш в 1 всяка точка която има поне един съсед с различен цвят. Останалите точки стават 0. За алгоритни които намират линии в контурите предполагам не трябва да питаш в този форум, а да потърсиш с някоя търсачка в интернет.

Търси Image processing. Принципът е следния: Имаш конкретен пиксел. Новата му стойност (която копираш в нов Canvas) се получава в зависимост от стойностите на околните пиксели. Виж дали Sobel filter ще ти свърши работа. Имах нещо подобно, но не можах да го намеря от първо търсене.

Зная следното по въпроса.
Първо се прилага заострящ филтър, например конволюция с filter kernel

-1 -1 +1
-1 +1 +1
-1 +1 +1

Това дава ефект, подобен на Embose, ако си гледал програми като Adobe Photoshop.

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

Наистина източник на информация са книги по "Image Processing", и може да търсиш в интернет.
Такъв алгоритъм, обяснен сравнително добре има в една книга, която я има в сайтовете на Analog Devices. Погледни

[линк]

Тази книге не е специално за Imdge Processing, но две от главите са специално за това. Преди време книгата си имаше собствен сайт [линк] но сега като опитах, не ми излезе.

поправка за филтъра:

-1 -1 +1
-1 0 +1
-1 +1 +1

или

-1 -1 -1
-1 0 +1
+1 +1 +1

...

Има много варианти. Виж книгата, там пише.

Още нещо.
Алгоритъма в тази книга използва именно тези понятия за "съседни точки", за които ти говориш, за да отстрани излишните точки от грубия контур. Иначе си е напълно евристичен - и ти можеш да си измислиш подобни правила.

(отговарям на автора поставил темата, разбира се)

oswen wsichko kazano:
Ako silno te marzi i za netochni rezultati - mojesh da izpolzwsh rekursiwen algoritam
ako porazgledash kak se rasterizira liniq pos 45 gradusa moje i da preosmislish tochkata s "neposredstweni"-te sysedi

Имам едно въпросче - би ли ме светнал тия филтри как се прилагат върху битмапа защото нещо не мога да стопля. Това е маска с някакви стойности, който се прилагат върху битмапа като центъра на филтъра се поставя върху всяка точка или матрица която се смята някак с матрица от точки на битмапа или що? Гледал съм такива филтри по разни софтуери но нищо не ми говорят. Малко помощ pls!

towa koeto se ochakwa ot teb w sluchaia
e za wsiaka tochka da izchislish now cwiat
kato si predstwsih che w sredata na tozi filtyr e
tekushtata tochka a stoinostta e suma ot proizwedeniata
na chislata ot filtyra i stoinostite w syotwetnite im tochki
ot bitmapa wse edno go slagash toia filter wyrhu bitmapa
ili filityra ako e
-1 -1 1
-1 0 1
-1 1 1
a tochkite sa
1 2 3
4 5 6
7 8 9

za 5 imash nowa stoinost -1*1 + -1*2 + 1*3 + -1*4 + 0*5 + 1*6 + -1*7 + 1*8
+ 1*9
i si predstawiash che okolo bitmapa ima niakolko reda i koloni s 0
ili naistina si gi slagash da ti e po-lesno sys smetkite

Благодаря за съветите, сега свалям книгата, надявам се да ми помогне.

Така е.

Още нещо.
Този алгоритъм е така неречената конволюция на изходния сигнал F(x,y) (в случая bitmap-а) с импулсната характеристика (Inpulse Response) на филтъра G(x,y) (т.e. в нашия случай матричката).
Така действат всички линейни филтри.

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

За това има по-бърз метод, който използва една теорема за конволюцията и преобразуванието на Фурие.
Изобщо не е сложно. Първо инпулсната характеристика на филтъра G(x, y) се преобразува по Фурие, и това което се получава се нарича честотна характеристика (Frequensy Response).
След това, като получим входния сигнал F(x,y) и него преобразуваме по Фурие, прилагаме филтъра в честотната област, и след това получения резулт връщаме чрез обратно преобразувание на Фурие обратно в пространствената област.

Резултата е същия, но така е по-бързо.
При по-големи битмап и филтър се постига 100 пъти и повече ускорение.

По-бързо е понеже прилагането на филтъра в честотната област е само еднократно почленно умножение, без никакво влачене по образа.
Освен това, за дискретно преобразувание на Фурие (DFT) се използва бързия алгоритъм FFT (Fast Fourier Transform).

В книгата която цитирах го пише.
Не е толкова сложно, колкото изглежда на думи. Правил съм го.
В интернет има много free софтуер за FFT. Пиши FFT в google и гледай какво става!
Обяснено е и в тази книга, има го и в Numerical Reciepes.

Благодаря и на двамата. Светнах се в едната посока, но в другата ми се вижда, че няма отговор - т.е. имам битмап и искам да си направя някакъв филтър (не просто "филтър", а филтър който да ми върши работа). Tа при това положение, ако се опитам да "обърна" формулата на emo, то най-вероятно ще получа нищо. Въпросът ми е как се построява матрицата на филтъра и за да не пълня форума с тъпи въпроси има ли някоя свестна книжка, където да прочета тия неща?

ei da ne mislish che az shte ti izkaram 6cata po KGD AAA!?!?

Не ти трябва да поставяш този въпрос.
Навсякъде дето съм гледал дават по 5-6 примера.
Сигурно е ноу-хау.

Иначе, какво очакваш да получиш от един линеен филтър?
Това което пише по въпроса в книги за DSP е как да направиш заглаждане, изостряне, контрастиране - все неща които ги има по копчетата на някой телевизор. Едно време са го правили чрез електроника, а сега се използва цифрова техника.

Ще се опитам да ти помогна малко - иначе подробностите ще си ги прочетеш, стига да те интересува.

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

Физическия смисъл на тази матрица, с която правим конволюция, е реакцията на филтъра, ако му подадем на входа единичен импулс. Затова на английски му казват Impulse Response. При графиката, единичен импулс означава целия битмап да е черен и само един пиксел, импулса, да не.

За да се убедиш и разбереш това, направи следното: разчертай си на хартия един битмап в който навсякъде има нули а само в средата има една 1. Приложи върху него ръчно един малък 3x3 филтър, да речем онези за които писахме по-горе. Ще видиш, че резултата е самата 3x3 матрица, само че траспонирана. Това е Impulse Response.

Когато искаш да си измислиш свой филтър може да разсъждаваш по този начин. Ако знаеш как трябва да реагира на единичен импулс, значи имаш данните за филтъра. Не казвам че е лесно.

Това на мен ми помага.

Думата филтър се използва абстрактно - някаква черна кутия в която влиза сигнала (при нас образа) и от другия край излиза преработен. Може да е направена от електроника, а може и софтуерно по начина за който говорим. Условието линейност означава определени аксиоми - аналогично на това във векторните пространства - нали там казваме, че матриците са линейни оператори и това значи нещо.
Това условие позволява пресмятания когато прилагаме няколко филтъра паралелно или успоредно, чрез едни правила за декомпозиция.
Ама това става вече дълго - пише го в книгите.

Помогнах ли?

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

За Image Processing има още много алгоритми и е напикано в съответни книги.

Мерси отново! Не съм се занимавал с тия неща преди (а ми се иска). Горе-долу имам понятие от математика и от електроника, но това не ми помага особено с цифровата обработка (по скоро програмната обработка). Всичко започна от там, че ми се искаше да премахна шум от AVI файл (едни досадни точици, които се получават при ниска осветеност в помещението където е снимано). Очевидно задачата ми не е лека но ще се разровя за литреатура.

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

Мога да те информирам горе-долу какво пише по въпроса във [линк] за да ти спеся време напразно да я четеш преди да знаеш дали ти върши работа.
Но не искам тук, за да не стана досаден - без това много се раздрънках.

Ако те интересува, остави някакъв e-mail тук.