Vytvoření mobilního skeneru dokumentů s nulovými závislostmi:operátor Sobel

Pokud jste zmeškali předchozí článek této série (Rozděl a panuj), budete si ho chtít přečíst jako první, abyste pochopili, o čem zde budeme diskutovat.

Sobelův operátor aproximuje velikost a směr gradientu obrazu na konkrétním pixelu, ale teoreticky jej lze aplikovat na jakoukoli diskrétní funkci dvou proměnných. Pro ty, kteří si nepamatují nebo nestudovali mnohorozměrný počet, pojďme diskutovat, co to znamená. V opačném případě, pokud jste obeznámeni s kalkulem, klidně přeskočte několik následujících částí tohoto článku.

Deriváty

Matematické funkce s jednou proměnnou berou jednu číselnou vstupní proměnnou a vytvářejí jediný číselný výstup. Jednoduché, že? Zde je příklad:

f ( x ) = 3 x s p a c e f ( 0 ) = 0 f ( 2 ) = 6 f ( 10101 ) = 30303 f(x) =3x\nový řádek\vphantom{mezera}\novýřádek(0) =0\novýřádek(2) =6\novýřádek(10101) =30303 f(x)=3xspacef(0)=0f(2)=6f(10101)=30303

Pokud bychom to měli napsat v JavaScriptu:

function f(x) {
  return 3 * x;
}
console.log(f(1)) // 3
console.log(f(2)) // 6
// You get the idea...

Pokud vyneseme výstup na svislou osu a vstup na vodorovnou osu (tj. y = f(x) ), dostaneme tento pěkný řádek:

To už samozřejmě víte. Věci jsou o něco zajímavější, když vypočítáme sklon této čáry, který je numerickým vyjádřením „strmosti“ čáry a vypočítá se výpočtem „nárůstu nad přeběhem“. Strmější funkce mají větší sklony. V tomto případě se funkce zvýší o 3 pokaždé, když se spustí o 1 (hodnota y se zvýší o 3 pokaždé, když se x zvýší o 1). Proto je sklon 3 / 1 , nebo 3. Mohli jsme také vidět, že se zvedne o 6 pokaždé, když přeběhne o 1, a našli bychom sklon 6 / 2 , která je rovněž hodnocena jako 3.

Přesněji řečeno, sklon představuje rychlost změny funkce nebo to, jak moc se změní výstup funkce při změně na vstupu 1.

Jaký je sklon složitější funkce, řekněme

g ( x ) = x 2 g(x) =x^2 g(x)=x2

? Pokud to vykreslíme, vidíme, že funkce je tím strmější, čím dále jdete od x = 0 , takže sklon nemůže být reprezentován pouze jedním číslem.

Jak se ukazuje, tato funkce opravdu nemá spád. Můžeme pouze vypočítat sklony tečných čar pro každou hodnotu x. Tečna je lineární aproximací původní funkce, která je s ní identická v blízkosti nějakého bodu. Zde je graf funkce s tečnou na x = 1 :

Zdá se, že modrá čára je stejná jako červená křivka poblíž x = 1 , od (1, 1) je bod tečnosti. Jak jsem uvedl výše, můžeme vypočítat sklon tečny v libovolném bodě červené křivky. Pro tuto funkci se ukáže, že sklon tečné přímky je roven 2x na libovolné souřadnici x. Říkáme tomu derivace funkce; derivát se často označuje apostrofem, který nazýváme "prvočíslo". Proto:

f ( x ) = 3 x f ( x ) = d f d x = 3 s p a c e g ( x ) = x 2 g ( x ) = d g d x = 2 x f(x) =3x\newlinef'(x) =\frac{\mathrm{d} f}{\mathrm{d} x} =3\newline\vphantom{mezera}\newlineg(x) =x^2\ newlineg'(x) =\frac{\mathrm{d} g}{\mathrm{d} x} =2x f(x)=3xf′(x)=dxdf​=3mezerag(x)=x2g′(x)=dxdg​=2x

Můžeme říci, že "f-prvočíslo x je 3 a g-prvočíslo x je 2x", protože pro f(x) , tečna je ve skutečnosti stejná jako funkce samotná (vlastnost všech lineárních funkcí), takže derivace je pouze sklon, zatímco pro g(x) musíme udělat ještě nějakou práci, abychom našli sklon tečny. Za sekundu se dostaneme k tomu, proč nás ta derivace zajímá.

Derivace funkce je okamžitá rychlost změny této funkce. Nechci, aby tento článek byl pouze o matematice, takže jsem přeskočil spoustu podrobností, které byste se měli opravdu naučit, pokud jste nikdy nestudovali kalkul (včetně toho, jak vlastně počítáte derivaci pro libovolnou funkci!) I vřele doporučuji kurz Calculus 1 od Khan Academy nebo toto skvělé video, pokud spěcháte.

Funkce s více proměnnými

Funkce s více proměnnými jsou pro studenty matematiky často matoucí, ale jako programátor je používáte neustále! Jsou to pouze funkce, které mají více než jednu vstupní proměnnou. Zde je příklad:

f ( x , y ) = 3 x + y 2 f(x, y) =3x + y^2 f(x,y)=3x+y2

V JavaScriptu je to jen:

function f(x, y) {
  return 3 * x + y * y;
}

Je to trochu těžší představit si mentálně, protože to už nemůžeme vykreslit na 2D rovině; potřebovali bychom 3-D povrch, abychom ukázali, jak to vypadá. Funkce má pro vstup jak osu x, tak osu y a nyní používá osu z pro výstup. Na následujícím obrázku je osa z svislá a osy x a y vodorovné.

Opravdu nedává smysl brát derivaci této funkce:je to 3D povrch, ne křivka, takže v každém bodě můžete vzít nekonečné množství tečných čar (x, y, f(x, y)) v každém směru.

Nicméně můžeme vezměte derivaci, pokud určíme, kterým směrem naše tečna ukazuje na vodorovné rovině. Například můžeme vypočítat sklon tečné přímky ve směru kladné x. Toto se nazývá parciální derivace vzhledem k x. Můžeme to udělat pro libovolný směr, ale v mnoha případech se staráme pouze o dílčí části s ohledem na vstupní proměnné (v tomto případě x a y). Pro tuto funkci:

f ( x , y ) = 3 x + y 2 s p a c e f x = 3 s p a c e f y = 2 y f(x, y) =3x + y^2\nový řádek\vphantom{mezera}\nový řádek\frac{\částečné f}{\částečné x} =3\nový řádek\vphantom{mezera}\nový řádek\frac{\částečné f }{\částečné y} =2 roky f(x,y)=3x+y2mezera∂x∂f​=3mezera∂y∂f​=2y

To znamená, že parciální derivace vzhledem k x je 3 a částečná vzhledem k y je 2y . Použití parciálních derivací je velmi snadné, pokud víte, jak derivace vypočítat:považujte všechny ostatní proměnné za konstanty, když derivujete s ohledem na jednu. Například, když vezmeme částečné vzhledem k x, jednoduše předpokládáme, že y je konstantní hodnota, a proto můžeme ignorovat y^2 období. (Nemůžete však pouze předpokládat, že hodnoty jsou nulové; částečné vzhledem k x z xy je stále y.)

Pro spojité funkce s více proměnnými existuje užitečná hodnota, která se nazývá gradientní vektor. Pokud jste obeznámeni s vektory, gradient pro funkci dvou proměnných (x a y) je definován takto:

f = f x , f y \nabla f =\left\langle \frac{\částečné f}{\částečné x}, \frac{\částečné f}{\částečné y} \pravo\rangle ∇f=⟨∂x∂f​,∂y∂f​⟩

V mnoha případech nás opravdu zajímá pouze směr a velikost gradientu (které stejně jednoznačně definují vektor). Pro jakékoli konkrétní x a y je směr gradientu směr „nejstrmějšího vzestupu“, tj. směr v rovině XY, ve kterém se výstup funkce nejvíce zvyšuje, zatímco velikost gradientu je hodnota derivace v směr sklonu (jinými slovy, sklon nejstrmější tečné čáry v libovolném směru na (x, y, f(x, y)) ). Zde je návod, jak vypočítáte tyto hodnoty (sloupce představují velikost a theta je úhel):

f = ( f x ) 2 + ( f y ) 2 s p a c e θ = a t a n 2 ( f y , f x ) | \nabla f | =\sqrt{\left(\frac{\partial f}{\partial x}\right)^2 + \left(\frac{\partial f}{\partial y}\right)^2}\newline\vphantom {mezera}\nový řádek\theta =\mathrm{atan2}\left(\frac{\částečné f}{\částečné y}, \frac{\částečné f}{\částečné x}\vpravo) ∣∇f∣=(∂x∂f​)2+(∂y∂f​)2​mezeraθ=atan2(∂y∂f​,∂x∂f​)

Pokud jste nikdy předtím nedělali vícerozměrný počet, může se to zdát matoucí, ale časem by vám to mělo začít připadat docela intuitivní, pokud skutečně rozumíte předběžnému výpočtu! Opět platí, že Khan Academy je váš přítel.

Kde je počítačové vidění?

Možná se ptáte, jak se celá tato teoretická matematika vlastně vztahuje na skenování dokumentů. Nejprve musíte přehodnotit svou představu o tom, co je obrázek.

Pravděpodobně už víte, že obrázky jsou pouze masivní mřížky pixelů, kde každý pixel má červenou, zelenou a modrou barvu a potenciálně hodnotu alfa (neprůhlednost). Každá z těchto hodnot se typicky pohybuje od 0 do 255 (tj. jeden bajt představuje každou barvu/kanál). Změnou hodnot každého kanálu můžete z jednoho pixelu vytvořit prakticky libovolnou barvu a společně tyto barvy vytvoří obraz, který lze zobrazit na obrazovce.

Pojďme si věci trochu zjednodušit tím, že vezmeme v úvahu obrázek ve stupních šedi. Nyní je zde pouze jeden kanál na pixel, který představuje intenzitu. Přestaňme také uvažovat o kanálech v pojmech bajtů a místo toho jako o pouhých reálných číslech (hodnota s plovoucí desetinnou čárkou spíše než celé číslo). Máme tedy mřížku reálných čísel reprezentujících jas obrazu v každém pixelu, nebo efektivně v každém bodě mřížky. Nyní si zkuste představit, že tento obrázek je ve skutečnosti pouze funkcí x a y (které představují souřadnice každého pixelu), která má výstup intenzity obrazu. Pokud je například jas 0,5 v pixelu ve třicátém sloupci zleva a v osmém řádku zdola, můžeme říci, že:

f ( 30 , 8 ) = 0,5 f(30, 8) =0,5 f(30,8)=0,5

Jedna otázka, která vám možná běží hlavou, je „jak přesně může být obrázek funkcí? Mezi hodnotami pixelů není intenzita. Co je f(30.27, 8.13) ?"

Ačkoli většina funkcí, se kterými se setkáte ve standardních matematických kurzech, má definiční obor všech reálných čísel (to znamená, že jsou definovány v každém možném konečném bodě), některé funkce nejsou definovány všude. Například f(x) = 1 / x není definován jako nula, protože 1 / 0 neexistuje. Obrázek je definován pouze na konkrétních celočíselných souřadnicích, kde má obrázek pixel, ale stále se kvalifikuje jako funkce. Takže ve zkratce f(30.27, 8.13) neexistuje ani f(12, 1.5) nebo f(-1, 100) .

Nyní řekněme, že chceme najít gradient tohoto obrázku. Stejně jako všechny ostatní funkce více než jedné proměnné by mělo být možné vzít gradient, ne? Bohužel máme problém:je nemožné vzít derivaci funkce v bodě, kde není spojitá, takže nemůžeme vypočítat parciální derivace a nemůžeme najít gradient.

Proto nejlépe, co můžeme udělat, je vypočítat aproximaci gradientu obrazu. V průběhu let bylo objeveno mnoho heuristických a teoretických metod pro odhadování gradientu, ale jedna z prvních technik, Sobelův operátor, zůstala populární, protože je relativně levná a přitom zůstává dostatečně přesná pro většinu aplikací.

Operátor Sobel specifikuje dvě konvoluční jádra, která lze použít k výpočtu parciálních derivací vzhledem k x a y v každém pixelu. Oblíbené varianty jader Sobel jsou následující:

S x = [ 3 0 3 10 0 10 3 0 3 ] s p a c e S y = [ 3 10 3 0 0 0 3 10 3 ] S_x =\begin{bmatrix}-3 &0 &3 \newline-10 &0 &10 \newline-3 &0 &3\end{bmatrix}\newline\vphantom{space}\newlineS_y =\begin{bmatrix}3 &10 &3 \nový řádek0 &0 &0 \nový řádek-3 &-10 &-3\end{bmatrix} Sx​=⎣⎡​−3−10−3​000​3103​⎦⎤​mezeraSy​=⎣⎡​30−3​100−10​30−3​⎦⎤​

Pro každou z výše uvedených matic konvoluce najde každou oblast 3x3 pixelů v obraze a vynásobí každou intenzitu odpovídající hodnotou v matici, poté sečte výsledky. Vypočítané parciální derivace platí pro středový pixel (což by byl druhý řádek, druhý sloupec v každé matici). Pomocí parciálních derivací je triviální vypočítat velikost a směr gradientu.

Zde je úžasné video, které vysvětluje konvoluce mnohem podrobněji s několika pěknými vizualizacemi. Dokonce se dozvíte, jak fungují některé neuronové sítě!

Po letech výzkumu a testování bylo zjištěno, že tento algoritmus je účinný, takže nemusíte chápat, proč funguje tak dobře při aproximaci gradientu. Měli byste však být schopni získat obecnou intuici o tom, co dělá.

Zvažte Sx matice. Pokud jsou intenzity přibližně stejné jako vlevo a vpravo od středového pixelu, můžeme předpokládat, že se ve směru x kolem středového pixelu příliš nezmění. Jako takové se vážené hodnoty vzájemně ruší, protože filtr je symetrický napříč druhým sloupcem a vypočtená parciální derivace je 0. V následujícím příkladu jsou však hodnoty pixelů velmi odlišné:

[ 0,72 0,42 0,14 0,81 0,08 0,32 0,56 0,63 0,44 ] \begin{bmatrix}0.72 &0.42 &0.14 \newline0.81 &0.08 &0.32 \newline0.56 &0.63 &0.44\end{bmatrix} ⎣⎡​0.720.810.56​0.420.080.63​0.140.320.44​⎦⎤​

Logicky, protože se hodnoty velmi mění, musí být rychlost změny vysoká, takže parciální derivace vzhledem k x musí být také velká. Odhaduje se, že:

3 0,72 + 0 0,42 + 3 0,14 + 10 0,81 + 0 0,08 + 10 0,32 + 3 0,56 + 0 0,63 + 3 0,44 = 7,00 -3 * 0,72 + 0 * 0,42 + 3 * 0,14 + \nový řádek-10 * 0,81 + 0 * 0,08 + 10 * 0,32 + \nový řádek-3 * 0,56 + 0 * 0,63 + 3 * 0,44 \newline=-7,0> −3∗0,72+0∗0,42+3∗0,14+−10∗0,81+0∗0,08+10∗0,32+−3∗0,56+0∗0,63+3∗0,44=−7,00

Protože maximální možná velikost derivace s touto konvolucí je 16, velikost 7 je relativně vysoká.

Je velmi důležité mít na paměti, že gradienty vypočítané Sobelovým operátorem jsou smysluplné pouze ve vzájemném vztahu, protože úprava vah by změnila maximální velikost vypočítané derivace. Pokud by vaším cílem bylo vypočítat parciální derivaci pro skutečnou matematickou funkci spíše než pro obrázek, Sobelův operátor by nejen poskytl nepřesné výsledky, ale také by byl nesprávně škálován. Vhodnější technikou pro odhad parciální derivace vzhledem k x na vzorcích aktuální, matematicky vyjádřitelné funkce by bylo použití následujícího konvolučního jádra:

S x = [ 0 0 0 0,5 0 0,5 0 0 0 ] S_x =\begin{bmatrix}0 &0 &0 \newline-0.5 &0 &0.5 \newline0 &0 &0\end{bmatrix} Sx​=⎣⎡​0−0,50​000​00,50​⎦⎤​

Tento filtr najde sklon lineární aproximace funkce pomocí dvou bodů o jednotku vzdálených od středu v x, což je teoreticky přesnější odhad derivace.

Abych to shrnul:pomocí některých matematických technik můžete odhadnout vektor gradientu pro každý bod v obrázku, i když diskrétní funkce jako obrázky ve skutečnosti nemají derivace.

Proč nás zajímá gradient obrázku?

Vraťme se k tomu, co vlastně gradient představuje. Popisuje největší rychlost změny, kterou můžete najít v jakémkoli směru v určitém bodě funkce. Pro náš obrázek gradient zakóduje největší změnu intenzity, která existuje kolem daného pixelu. Když se nad tím zamyslíte, to, co vizuálně považujeme za „okraje“ věcí, které vidíme na obrázku, jsou ve skutečnosti jen místa pixelů, ve kterých se intenzita dramaticky mění.

Například na okraji kusu papíru se intenzita změní z téměř 1 (bílá) uvnitř papíru na intenzitu pozadí přes tři pixely, což způsobí vysokou velikost gradientu na okrajových pixelech, zatímco uvnitř papíru jakákoli oblast 3x3 bude mít hodnoty blízké jedné ve všech místech, což poskytne velmi nízkou velikost gradientu. Pokud tedy vezmeme velikost gradientu obrázku, efektivně zdůrazníme okraje všech objektů na obrázku a zároveň potlačíme oblasti s malou změnou (tj. vnitřky těchto objektů). Vizuální příklad by to měl objasnit. Původní obrázek:

Velikost gradientu:

Všimněte si, že okraje papíru jsou téměř bílé a obrys textu uvnitř stránky je šedý, zatímco zbytek obrázku je téměř černý. Toto je nejkritičtější krok detekce okrajů, a proto je jednou z klíčových součástí této aplikace pro skenování dokumentů.

Je důležité poznamenat, že než skutečně provedeme Sobelovu detekci hran, obvykle používáme Gaussovo rozostření, abychom snížili účinky obrazového šumu (které jsou často detekovány jako hrany kvůli náhodným špičkám intenzity, které způsobují). Navíc jsme podstatně zmenšili velikost obrázku ještě před zahájením tohoto procesu, abychom zkrátili dobu zpracování.

K těmto krokům se však dostaneme v budoucích článcích, ke konci této série. Dále probereme, jak můžeme použít tento obrázek s magnitudou gradientu, abychom skutečně našli matematické reprezentace hran v obrázku pomocí Houghovy transformace.