Image Processing + Fourier
13 отговора
348 прегледа
Image Processing + Fourier
Zdraveite vsichki.
Imam sledniq problem: trqwba da polu4a spektyra na Fourier za kontura na obekt ot binarno 2D izobrajenie. W chastnost me interesuwa maksimalnata 4estota na spektyra.
Ako nqkoi ima predstava ot image processing i Fourier transformation bi mi bil ot golqma pomosht :)
10x
Imam sledniq problem: trqwba da polu4a spektyra na Fourier za kontura na obekt ot binarno 2D izobrajenie. W chastnost me interesuwa maksimalnata 4estota na spektyra.
Ako nqkoi ima predstava ot image processing i Fourier transformation bi mi bil ot golqma pomosht :)
10x
Re: Image Processing + Fourier
при положение че контура ти е отделен, трябва да си направиш алгоритъм за следване на контура. сега няма да се спирам на това как се прави. аз лично го правя с рекурсия - тя е лесен, но опасен метод. след това правиш анализ на фурие на ъгъла който сключва контура със произволна ос, да речем х.
ъгълът се намира като
atan2(dx,dy)
много полезна функция, която е всъщност atan(dy/dx), но ако я има в езика който ползваш, ползвай нея, защото ти спестява неприятностите с делене на 0.
все пак имайки предвид че спектъра ще е почти със сигурност безкраен, то предполагам в задачата се търси не най-високата честота, а последният максимум. може и да се търси честотата, под която се намира константна част (примерно 90%) от енергията. така че ти трябва да си изясниш този въпрос. а самия спектър се намира по стандартния начин - ако бележим функцията на ъгъла с f(x)
A=integral(f(t)*sin(w*t))*dt
B=integral(f(t)*cos(w*t))*dt
като за амплитуда ползвай величината A^2+B^2.
сега, тука е тънкия момент - определяне на ъгъла на контура. тъй като картинката ти е пиксели наредени в решетка, то преместванията на следящия елемент ще са със 8 възможни стойност. това със сигурност ще ти добави високочестотни компоненти в спектъра. най-добре да записваш последните няколко премествания в буфер и да смяташ средна стойност. мисля 4 стойности ще е добре. това обаче ще ти подтисне леко спектъра във високочестотната част. ти си прецени. а интегралите горе ги смятай просто като сума, където dt e дължината на прехода, а t е дължината на проинтегрирания контур. имай предвид че дължината на контура не е просто броя пиксели от които се състои, защото прехода (1,0) е с дължина 1, а прехода (1,1) е с дължина корен 2.
w трябва да заема стойности 2*pi*k/s където k е цяло число, а s е дължината на целия контур. k не бива да бъде по-голямо от броя пиксели/2, дори до там не трябва да стига.
ъгълът се намира като
atan2(dx,dy)
много полезна функция, която е всъщност atan(dy/dx), но ако я има в езика който ползваш, ползвай нея, защото ти спестява неприятностите с делене на 0.
все пак имайки предвид че спектъра ще е почти със сигурност безкраен, то предполагам в задачата се търси не най-високата честота, а последният максимум. може и да се търси честотата, под която се намира константна част (примерно 90%) от енергията. така че ти трябва да си изясниш този въпрос. а самия спектър се намира по стандартния начин - ако бележим функцията на ъгъла с f(x)
A=integral(f(t)*sin(w*t))*dt
B=integral(f(t)*cos(w*t))*dt
като за амплитуда ползвай величината A^2+B^2.
сега, тука е тънкия момент - определяне на ъгъла на контура. тъй като картинката ти е пиксели наредени в решетка, то преместванията на следящия елемент ще са със 8 възможни стойност. това със сигурност ще ти добави високочестотни компоненти в спектъра. най-добре да записваш последните няколко премествания в буфер и да смяташ средна стойност. мисля 4 стойности ще е добре. това обаче ще ти подтисне леко спектъра във високочестотната част. ти си прецени. а интегралите горе ги смятай просто като сума, където dt e дължината на прехода, а t е дължината на проинтегрирания контур. имай предвид че дължината на контура не е просто броя пиксели от които се състои, защото прехода (1,0) е с дължина 1, а прехода (1,1) е с дължина корен 2.
w трябва да заема стойности 2*pi*k/s където k е цяло число, а s е дължината на целия контур. k не бива да бъде по-голямо от броя пиксели/2, дори до там не трябва да стига.
а, още нещо
внимавай с прехода между ъгъл -пи,пи. там ще получиш голям скок, който в действителност го няма. двата ъгъла са съседни в множеството на ъглите, но в множеството на реалните числа пи и -пи са несъседни. всеки такъв преход ще добави в спектъра ти съставка, която намалява с 1/w, което опорочава анализа.
аз имам готов алгоритъм за решаване на такива ситиации, но ще те оставя да се поблъскаш
аз имам готов алгоритъм за решаване на такива ситиации, но ще те оставя да се поблъскаш
Re: Image Processing + Fourier
Opasiavam se, 4e towa mi doide malko slojno... 
Po printsip razglevdam neshtata predimno teoreti4no, taka 4e ne polzwam nikakyw ezik. Samo opitah da naprawq FFT na MicroCal Origin, no tyi kato matemati4eskata strana na neshtata mi se gubi w kraina smetka ne postignah osoben rezultat: Polu4iha se grafiki na amplitudata, ygyla i syotwetno 4estotata, no rezultata za neq me symnqwa...
Zna4i shte dam konkretnata situaciq koqto razglejdam:
Kontura na obekta se opiswa s vektor r wyw funkciq ot parameryra l, koito se izmenq ot 0 do dyljinata na kontura L. Taka se polu4awa modificirana radialna funkciq (MRF) R(l), kydeto Ri e radiusa mejdu centroida na obekta i wsqka to4ka i ot kontura. n1 e obshtiq broi na konturnite to4ki. No za da se realizira mashtabno inwariantno opisanie na obekta e neobhodimo komponentite na MRF da bydat normalizirani, taka, 4e da imat postoqnna dyljina nezawisimo ot goleminata na obekta. Towa stawa posredstwom reduciraneto na n1 do N1. Iziskwaneto za izbora na N1 trqbwa da otgowarq na iziskwaniqta na teoremata za diskretizaciq, t.e 4estotata na diskretizaciq na kontura na obekta Fd, koqto se opredelq kato Fd=N1/2*pi, trqbwa da otgowarq na nerawenstwoto Fd>=2*Fmax, kydeto Fmax e maksimalnata 4estota ot 4estotniq spektyr (spektyra na Furie) na MRF na obekta, t.e. N1>=4*pi*Fmax
Taka, 4e eto tazi 4estota Fmax mi e neobhodima i ne znam kak da ia nameria...
Po printsip razglevdam neshtata predimno teoreti4no, taka 4e ne polzwam nikakyw ezik. Samo opitah da naprawq FFT na MicroCal Origin, no tyi kato matemati4eskata strana na neshtata mi se gubi w kraina smetka ne postignah osoben rezultat: Polu4iha se grafiki na amplitudata, ygyla i syotwetno 4estotata, no rezultata za neq me symnqwa...
Zna4i shte dam konkretnata situaciq koqto razglejdam:
Kontura na obekta se opiswa s vektor r wyw funkciq ot parameryra l, koito se izmenq ot 0 do dyljinata na kontura L. Taka se polu4awa modificirana radialna funkciq (MRF) R(l), kydeto Ri e radiusa mejdu centroida na obekta i wsqka to4ka i ot kontura. n1 e obshtiq broi na konturnite to4ki. No za da se realizira mashtabno inwariantno opisanie na obekta e neobhodimo komponentite na MRF da bydat normalizirani, taka, 4e da imat postoqnna dyljina nezawisimo ot goleminata na obekta. Towa stawa posredstwom reduciraneto na n1 do N1. Iziskwaneto za izbora na N1 trqbwa da otgowarq na iziskwaniqta na teoremata za diskretizaciq, t.e 4estotata na diskretizaciq na kontura na obekta Fd, koqto se opredelq kato Fd=N1/2*pi, trqbwa da otgowarq na nerawenstwoto Fd>=2*Fmax, kydeto Fmax e maksimalnata 4estota ot 4estotniq spektyr (spektyra na Furie) na MRF na obekta, t.e. N1>=4*pi*Fmax
Taka, 4e eto tazi 4estota Fmax mi e neobhodima i ne znam kak da ia nameria...
ясно, зацепих ти целта
с една дума играеш си с разпознаване на образи. така, както ти казах спектъра ти е безкраен, така че трябва за този случай който посочи, да си избереш една константа, да кажем 0.9, като търсиш честотата за която 0.9 от всичката "енергия" е под нея. според мене обаче по-добрият подход е да си заложиш някаква предварително зададена максимално допустима грешка, зависеща от това доколко са близки обектите които искаш да различиш. по този начин ако искаш да различиш квадрат от кръг, ще получиш доста по-компактно представяне, защото дистанцията между тях е голяма и можеш да си позволиш малък брой точки за разпознаване. докато ако си назначиш изсмукана от пръстите граница ще получиш или нормализиран обект с излишък или с недостиг. обаче това с точките нещо не ми се нрави - както ти казах броят им не е точно пропорционален на дължината на кривата. както и да е.по-добре използвай някакъв друг по-показателен параметър, например средна стойност на модул R(l). аз лично обаче бих използвал средна стойност на R^2(l). верно че не е пропорционална на големината, но си има други предимства.
Re: Image Processing + Fourier
Мисля чак сега разбрах за какво става дума, но не съм много сигурен, та да се провери и от другите. Струва ми се че това дето МЕ азначава с Fmax и N1 е едно и също. Зависи какви искаме да правим.
Входния сигнал: Значи да речем, че сме фиксирали N1 до което нормализираме. Тогава ако контура е по-къс n1<N1 трябва да дублираме някои точки, а иначе когато контура е по-голям n1>N1 трябва да изтрием точки. Все едно, че сме направили предварително Strech (мащабиране) но малко по-изкривено.
Както каза Zaphod, от горе базовата честота на FFT няма какво да се ограничава - колкото повече - толкова по-добре. Индекса 'max' ако е заблудил някого, то е че Fmax е максималната честота която можем да хванем когато изберем N=4*пи*Fmax - точково FFT. По теоремата на Котелников (или Шанон) достатъчно е Fmax да е не по-малко от полувината на честота на дадена синусоида, че да може да се регистрира тази синусоидка. Ако в данните присъства някоя синусоида дето половината и' е по-дълга от синусоидата с честота Fmax, тя няма да се хване, ами ще се намаже грешно в спектара (aliasing).
Тогава да речем, че търсим окръжност -- нейната графика R(l) е константа и не е интересно, понеже във FFT само коефициента A0 ще е различен от 0. После, за фигура приличаща на Елипса имаме 2 синусоиди, или честота N = 2 е достатъчна. За нещо като триъгълник имаме 3 синусоиди, или честота N=3 е достатъчна. По-нататък за да гепиш един m-ъгълник е ясно, че трябва да избереш за Фурие базова честота N >= m.
Как да нормализирме в най-простата задача? Ами избираме съгласно фигурата <достатъчно> висока базова честота за FFT, и да е степен на 2 щото нали е по-лесно за алгоритъма. Примерно вземаме N = 32 за фигури с не повече от 30-тина върха. Тогава, нормализираме контура именно до това число N = N1. А пък онази формула, Fd=N/(2*пи) ти дава кръговата честота Fd - за формулите (тя е ясна веднага след като изберем стойността за N).
Горното разсъждение е става, ако сме решили да разпознаваме прости фигури, като търсим пик в спектъра - приложимо е и върши работа, естествено.
Възможно е и друг по-сложен вариант:
Да разделим контура на много фреймове, да направим FFT на всеки фрейм за да открием детайл в него, а после да разпознаваме <правилната> поредица от фреймове (детайли).
Примерно, имаме много сложен контур, като контур на границите на държави взети от географска карта. Тогава, можем да изберем сравнително малка базова честота, да речем N = 32 и да нормализираме рисунката до доста по-голям мащаб N1 >> N, съобрано точността на входните данни (колкото е по-голямо N1, толкова по-точно). Така, от входния сигнал - контура, ще получим няколко парчета N1/N и всяко парче ни дава спектър-вектор. С тези вектори може да обучим някой статистически алгоритъм като HMM. После получавайки неизвестна сканирана редица от вектори (obzervations), разпознаваме.
В последния случай числото N1 до което се нормализира е много по-голямо от размера N на FFT. Избора пак е интуитивен и с експерименти. N трябва да е достатъчно голяма за да хване един <елементарен> детайл във фрвйма си, но не много голямо, че да влизат във фрейма няколко <елементарни> детайли. А пък колкото по-голямо е N1 ще имаме по-голяма точност, но пък по-тежки сметки.
Това е.
Поздрави,
/b33
P.S.
Ако има нещо неясно, грешки или критика -- ще отговоря, следя темата.
.
Входния сигнал: Значи да речем, че сме фиксирали N1 до което нормализираме. Тогава ако контура е по-къс n1<N1 трябва да дублираме някои точки, а иначе когато контура е по-голям n1>N1 трябва да изтрием точки. Все едно, че сме направили предварително Strech (мащабиране) но малко по-изкривено.
Както каза Zaphod, от горе базовата честота на FFT няма какво да се ограничава - колкото повече - толкова по-добре. Индекса 'max' ако е заблудил някого, то е че Fmax е максималната честота която можем да хванем когато изберем N=4*пи*Fmax - точково FFT. По теоремата на Котелников (или Шанон) достатъчно е Fmax да е не по-малко от полувината на честота на дадена синусоида, че да може да се регистрира тази синусоидка. Ако в данните присъства някоя синусоида дето половината и' е по-дълга от синусоидата с честота Fmax, тя няма да се хване, ами ще се намаже грешно в спектара (aliasing).
Тогава да речем, че търсим окръжност -- нейната графика R(l) е константа и не е интересно, понеже във FFT само коефициента A0 ще е различен от 0. После, за фигура приличаща на Елипса имаме 2 синусоиди, или честота N = 2 е достатъчна. За нещо като триъгълник имаме 3 синусоиди, или честота N=3 е достатъчна. По-нататък за да гепиш един m-ъгълник е ясно, че трябва да избереш за Фурие базова честота N >= m.
Как да нормализирме в най-простата задача? Ами избираме съгласно фигурата <достатъчно> висока базова честота за FFT, и да е степен на 2 щото нали е по-лесно за алгоритъма. Примерно вземаме N = 32 за фигури с не повече от 30-тина върха. Тогава, нормализираме контура именно до това число N = N1. А пък онази формула, Fd=N/(2*пи) ти дава кръговата честота Fd - за формулите (тя е ясна веднага след като изберем стойността за N).
Горното разсъждение е става, ако сме решили да разпознаваме прости фигури, като търсим пик в спектъра - приложимо е и върши работа, естествено.
Възможно е и друг по-сложен вариант:
Да разделим контура на много фреймове, да направим FFT на всеки фрейм за да открием детайл в него, а после да разпознаваме <правилната> поредица от фреймове (детайли).
Примерно, имаме много сложен контур, като контур на границите на държави взети от географска карта. Тогава, можем да изберем сравнително малка базова честота, да речем N = 32 и да нормализираме рисунката до доста по-голям мащаб N1 >> N, съобрано точността на входните данни (колкото е по-голямо N1, толкова по-точно). Така, от входния сигнал - контура, ще получим няколко парчета N1/N и всяко парче ни дава спектър-вектор. С тези вектори може да обучим някой статистически алгоритъм като HMM. После получавайки неизвестна сканирана редица от вектори (obzervations), разпознаваме.
В последния случай числото N1 до което се нормализира е много по-голямо от размера N на FFT. Избора пак е интуитивен и с експерименти. N трябва да е достатъчно голяма за да хване един <елементарен> детайл във фрвйма си, но не много голямо, че да влизат във фрейма няколко <елементарни> детайли. А пък колкото по-голямо е N1 ще имаме по-голяма точност, но пък по-тежки сметки.
Това е.
Поздрави,
/b33
P.S.
Ако има нещо неясно, грешки или критика -- ще отговоря, следя темата.
.
броят на върховете и спектъра
разбирам те какво искаш да кажеш, но фигурите които наричаш "нещо като..." , са доста далеч от катото. с една дума ако разгледаш фигура R(l)=pi*sin(3*2*pi*l/L) която наричаш "нещо като триъгълник, то тя прилича по-скоро на маргаритка, отколкото на триъгълник. а и помисли - колкото повече ъгли, по-голяма гранична честота. как става така че за граничния преход n->oo отиваме към окръжност, за която R(l)=const?
Re: броят на върховете и спектъра
Абсолютно съм съгласен с това което казваш. Контурът на тези фигури даже е прекъсната функция а ние вземаме само дислретни стоиности от нея. Изобщо за <точно> преобразование в <математическия> смисъл си е нужно пълното преобразопвание на Фурие с неограничена и плътна честота.
[tova li iskash da kazes?]
За практически цели DFT не става ли? Аз всичко това го написах чрез собствени разсъждения - не съм го чел никъде. Сигурен съм, от опита който имам, че един четириъгълник може да се разпозна е с N > 4 точково Фурие. Например при N=5, ще се получи при четитириъгълника пик в честота n=4, а за триъгълника пик в спектъра около честота n=2 или 3. На ум се вижда, че ще се получи нещо такова. Няма начин да не се разпознаят толкова прости контури. И то само чрез локаризиране на максималната амплитуда; още повече, че ако разпознаваме измежду многоъгълници, те и спектрите са симетрични.
Поздрави,
/b33
[tova li iskash da kazes?]
За практически цели DFT не става ли? Аз всичко това го написах чрез собствени разсъждения - не съм го чел никъде. Сигурен съм, от опита който имам, че един четириъгълник може да се разпозна е с N > 4 точково Фурие. Например при N=5, ще се получи при четитириъгълника пик в честота n=4, а за триъгълника пик в спектъра около честота n=2 или 3. На ум се вижда, че ще се получи нещо такова. Няма начин да не се разпознаят толкова прости контури. И то само чрез локаризиране на максималната амплитуда; още повече, че ако разпознаваме измежду многоъгълници, те и спектрите са симетрични.
Поздрави,
/b33
Re: Image Processing + Fourier
Значи... попрочетох туй-онуй, попитах тоя-оня и стигнах до следните заключения:
За да се получи честотата ще ми трябва честотата на дискретизация или (за да я получа) стъпката на дискретизация. Оказва се че в повечето случаи тази информация просто я няма, особено в случая когато ползваш вече цифровизирани изображения. Ако се тръгне в обратна посока и се приеме за максимална стойност на N1 стойността на n1, може да се определи каква стойност да не надвишава честотата на дискретизация и съответно максималната честота, но това всъщност съвсем не решава проблема...
Затова направих следното: направих ФФТ на компонентите на радиалните функции на външните и вътрешните контури. В резултата се получава гoляма DC съставка и оттам нататък стойностите постепенно намаляват, като в средата започват да нарастват в обратен ред. Като се разгледа първата половина от резултата се стига до момент, в който числата стават много близки, т.е. дотук се съдържа около 90% от енергията. Следователно може да се засече при номера на кой елемент от контура става това. След това този брой се умножава по 2 и резултата е нужния брой редуцирани контурни точки N1. Така броя им може да се намали повече от два пъти без да има някаква съществена загуба на информация.
Това вече ми звучи значително по-разумно, отколкото търсенето на конкретни стойности за честотите...
За да се получи честотата ще ми трябва честотата на дискретизация или (за да я получа) стъпката на дискретизация. Оказва се че в повечето случаи тази информация просто я няма, особено в случая когато ползваш вече цифровизирани изображения. Ако се тръгне в обратна посока и се приеме за максимална стойност на N1 стойността на n1, може да се определи каква стойност да не надвишава честотата на дискретизация и съответно максималната честота, но това всъщност съвсем не решава проблема...
Затова направих следното: направих ФФТ на компонентите на радиалните функции на външните и вътрешните контури. В резултата се получава гoляма DC съставка и оттам нататък стойностите постепенно намаляват, като в средата започват да нарастват в обратен ред. Като се разгледа първата половина от резултата се стига до момент, в който числата стават много близки, т.е. дотук се съдържа около 90% от енергията. Следователно може да се засече при номера на кой елемент от контура става това. След това този брой се умножава по 2 и резултата е нужния брой редуцирани контурни точки N1. Така броя им може да се намали повече от два пъти без да има някаква съществена загуба на информация.
Това вече ми звучи значително по-разумно, отколкото търсенето на конкретни стойности за честотите...
Re: Image Processing + Fourier
Tова наблюдение,
че от средата амплитудите започват обратно и симетрично да нарастват сигорно е заради симетричността на реалното FFT. Нали ако правиш N-точково дискретно преобразование на Фурие от реален сигнал (имагинерните компоненти са 0), образа е симетричен - огледален около N/2. Тогава си ползваме само първата полувина - втората полувина не дава нова информация.
Pozdravi,
/b33
че от средата амплитудите започват обратно и симетрично да нарастват сигорно е заради симетричността на реалното FFT. Нали ако правиш N-точково дискретно преобразование на Фурие от реален сигнал (имагинерните компоненти са 0), образа е симетричен - огледален около N/2. Тогава си ползваме само първата полувина - втората полувина не дава нова информация.
Pozdravi,
/b33
Re: Image Processing + Fourier
Голямия нулев коефицент (DC) има смисъл на средно-аритметично разстояние от центъра на фигурата до контура; винаги ще го има и ще е голям.
Другото което правиш не ми е ясно от текста ти, обаче лично се интересувам какво точно си направил.
Pozdravi
/b33
Другото което правиш не ми е ясно от текста ти, обаче лично се интересувам какво точно си направил.
Pozdravi
/b33
Re: постоянната съставка - 2*пи
Интересно Zaphod,
обясни математическата част понеже не ми се рови в учебника.
Товоето твърдение е само, че нулевия коефициент ще го има. Това не изключва <физическото> ми обяснение за смисъла на коефициента, а от моята интерпретация наистина следва, че коефициента трябва да го има (освен контура да е нулев - свит до точка).
Поздрави,
/b33
обясни математическата част понеже не ми се рови в учебника.
Товоето твърдение е само, че нулевия коефициент ще го има. Това не изключва <физическото> ми обяснение за смисъла на коефициента, а от моята интерпретация наистина следва, че коефициента трябва да го има (освен контура да е нулев - свит до точка).
Поздрави,
/b33