Metódy a algoritmy na spracovanie obrazu. Algoritmy predbežného spracovania obrazu. Aplikácia neurónových sietí na rozpoznávanie vzorov

Laboratórium č. 1

Algoritmy spracovania obrazu

Konvolučná operácia

Konvolúcia je veľmi široký aplikačný algoritmus, na ktorý sa dá použiť predúprava obrázky a na rozpoznávanie a identifikáciu predmetov. Nech je obraz daný dvojrozmernou maticou jasu F" a maticu impulznej odozvy H. Matematicky konvolúcia matice F s jadrom H možno definovať podľa nasledujúceho vzorca:

kde M2xN2 - veľkosť matice konvolučného jadra. Veľkosť matice F sa rovná (M1+M2-1)x(N1+N2-1), kde M1xN1 - veľkosť pôvodnej matrice F" . Matrix F sa získa z originálu pridaním prvkov na okraje matrice podľa nejakého pravidla, aby sa dostala na požadovanú veľkosť. Pôvodná matica je zvyčajne vyplnená nulami na okrajoch na polovicu šírky matice. H doľava a doprava, respektíve polovica výšky hore a to isté dole. Potom veľkosť výslednej matice R bude rovnaký ako matica F" .

Konvolúciu je možné vypočítať priamo „bežením“ jednej matice cez druhú, ako už bolo uvedené vyššie. Na obr. 1 ukazuje schému na výpočet konvolúcie (veľkosť matice masky sa rovná 3x3). Na konvolučný operátor sa možno pozerať ako na maticu koeficientov (masiek), ktoré sú vynásobené element po elemente s vybraným obrazovým fragmentom, po čom nasleduje súčet na získanie novej hodnoty filtrovaného obrazového elementu. Táto matica môže mať ľubovoľnú veľkosť, nie nevyhnutne štvorcovú.

Ryža. 1. Implementácia konvolučnej operácie.

Cvičenie

Implementujte algoritmus, ktorý vykonáva operáciu konvolúcie pôvodného obrazu s maticovou maskou.

Veľkosť a typ maticovej masky nastavuje používateľ.

Na implementáciu rôznych algoritmov spracovania obrazu použite nasledujúce matice masiek:

• na vyhladenie a potlačenie šumu v obraze sa používa maticová maska ​​3x3 nasledujúceho tvaru:

na zvýraznenie kontúr sa používajú maticové masky nasledujúceho tvaru:

1/9*

Na výber kontúr sa používa maska ​​nasledujúceho formulára:

4. Implementujte stredový filter, ktorý sa používa na potlačenie bodového a impulzného šumu. Obrazový pixel a jeho susedia v uvažovanej oblasti sú usporiadané vo variačnom rade (vo vzostupných alebo zostupných hodnotách pixelov) a stredná hodnota tohto variačného radu je vybraná ako nová pixelová hodnota. Výsledkom priemerného filtrovania je, že akýkoľvek náhodný šum obsiahnutý v obrázku bude účinne eliminovaný. Je to preto, že každá náhodná náhla zmena intenzity pixelov v rámci posudzovaného regiónu bude triedená, t.j. bude umiestnený buď navrchu alebo na spodok zoradených hodnôt v danej oblasti a nebude sa počítať, pretože hodnota nového prvku sa vždy berie ako stredová hodnota.

5. Implementujte embosovací algoritmus. Razenie sa vykonáva podobným spôsobom ako algoritmy spriemerovania alebo vylepšenia hrán. Každý pixel na obrázku je spracovaný 3x3 raziacim jadrom (matrix-maska). Napríklad ako embosovacie jadro môžete použiť nasledujúcu matricu masky:

Po spracovaní hodnoty pixelov embosovacím mechanizmom sa k nej pridá 128. Hodnota pixelov pozadia sa teda stane priemernou sivou farbou (červená = 128, zelená = 128, modrá = 128). Sumy vyššie ako 255 možno zaokrúhliť na 255 nahor.

V reliéfnej verzii obrazu sa zdá, že obrysy sú vytlačené nad povrch. Smer zvýraznenia obrázka je možné zmeniť zmenou pozícií 1 a -1 v jadre. Ak sú napríklad hodnoty 1 a -1 zamenené, smer podsvietenia sa obráti.

6. Akvarelizácia obrazu. Akvarelový filter transformuje obrázok a po spracovaní vyzerá, ako keby bol napísaný akvarelom:

Prvým krokom pri aplikácii akvarelového filtra je vyhladenie farieb na obrázku. Jedným zo spôsobov vyhladenia je použitie stredného priemeru farieb v každom bode. Farebná hodnota každého pixelu a jeho 24 susedov (veľkosť matice-masky je 5x5) sú usporiadané vo variačných sériách v zostupnom alebo vzostupnom poradí. Stredná (trinásta) hodnota farby v sérii variácií je priradená centrálnemu pixelu.

po vyhladení farieb je potrebné použiť filter na zvýraznenie okrajov, aby ste zvýraznili okraje farebných prechodov.

DIGITÁLNY LIEČBA SIGNÁLY

Téma 17. SPRACOVANIE OBRAZU

Nič nie je nad predstavivosť človeka.

Titus Lucretius. Rímsky filozof a básnik. 1. storočie BC e.

Predstavivosť je dobrá vec. Ale vytiahnuť vandráka z pivnice, umyť ho, urobiť z neho Apollo, zabaliť do zápalkovej škatuľky a poslať priateľovi e-mail dobre grafický program urobí lepšie.

Anatolij Pyshmintsev, novosibirský geofyzik Uralskej školy. 20. storočie

Úvod.

1. Základné pojmy. Grafické znázornenie obrázkov. Reprezentácia farieb v počítačovej grafike. RGB farebný model. Farebný systém CIE XYZ.

2. Geometrické transformácie rastrových obrázkov. Oblasti a štádiá transformácie. Vzorkovanie. Interpolačné série obnovy dvojrozmerného signálu. Frekvenčné skreslenia obrazu a ich eliminácia. Prevzorkovanie obrázkov.

3. Filtrovanie obrázkov. Linkové filtre. Vyhladzovacie filtre. Kontrastné filtre. rozdielové filtre. Dvojrozmerná cyklická konvolúcia. nelineárne filtre. Prahové filtrovanie. stredné filtrovanie. Extrémne filtre.

4. Kompresia obrazu. Algoritmy kódovania dĺžky opakovania (RLE). Slovníkové algoritmy. Štatistické kódovacie algoritmy. Stratová kompresia obrazu. Odhad straty obrazu. Fourierova transformácia. Waveletová transformácia.

ÚVOD

Rozsah výskumu v oblasti digitálneho zobrazovania rýchlo rastie. Je to preto, že spracovanie obrazu je viacrozmerné spracovanie signálu a väčšina signálov v reálnom svete je viacrozmerná.

Obraz v matematickom znázornení je dvojrozmerný signál, ktorý nesie obrovské množstvo informácií. Farebný obrázok s rozmermi 500 × 500 prvkov predstavuje pole niekoľkých stoviek tisíc bajtov. Takéto informácie je možné spracovať iba racionálnou organizáciou výpočtov. Pre špecifické úlohy spracovania obrazu môžete použiť efektívnymi spôsobmi spracovanie, berúc do úvahy vlastnosti a obmedzenia tejto konkrétnej úlohy. Ak však hovoríme o spracovaní obrazu na riešenie širokej triedy problémov, potom je potrebné vybrať súbor štandardných operácií, z ktorých možno zostaviť algoritmy na riešenie ľubovoľných problémov. Patria sem lineárne transformácie, 2D konvolúcia a 2D diskrétne Fourierove transformácie.

Ale pri spracovaní obrazu sa široko používajú aj nelineárne transformácie. Charakteristickým znakom obrázkov je to jednotlivé prvky obrazy sú v určitom vzťahu so susednými prvkami. Preto väčšina algoritmov transformácie obrazu má lokálny charakter, t. j. spracovávajú obrazy skupinami prvkov nachádzajúcich sa v susedstve daného. Lineárne transformácie vyhovujú vlastnosti lokality a umožňujú konštrukciu algoritmov, ktorých výpočtová náročnosť veľmi nezávisí od veľkosti pokrytého okolia. Rovnaké vlastnosti sú potrebné pre nelineárne transformácie obrazu. Trieda takýchto transformácií zahŕňa algoritmy, ktoré sa nazývajú algoritmy filtrovania hodnotenia, založené na výpočte lokálnych štatistík hodnotenia. Pri výpočte poradových štatistík a ich derivátov sú možné zjednodušenia súvisiace s informačnou redundanciou obrázkov. Najznámejším algoritmom tejto triedy je algoritmus mediánového filtrovania. Ďalšími príkladmi hodnotiacich algoritmov sú algoritmy extrémneho filtrovania, ktoré nahradia analyzovaný prvok obrazu maximom alebo minimom v okolí. Ďalšou vlastnosťou rank algoritmov je lokálne prispôsobenie sa charakteristikám spracovávaného obrazu a možnosť ich využitia nielen na vyhladzovanie a odšumovanie, ale aj na extrakciu vlastností pri automatickom rozpoznávaní obrazu.

Pri spracovaní obrazu sú široko používané metódy jednorozmerného spracovania signálov, ak je možné ich zovšeobecniť na viacrozmerné signály. Zároveň je potrebné vziať do úvahy, že matematické metódy na opis viacrozmerných systémov nie sú úplné. Viacrozmerné systémy majú veľký počet stupňov voľnosti a ich dizajn získava flexibilitu, ktorá nie je charakteristická pre jednorozmerné systémy. Zároveň sa viacrozmerné polynómy nedajú rozložiť na jednoduché faktory, čo komplikuje analýzu a syntézu viacrozmerných systémov.

17.1. Základné pojmy

Grafické znázornenie obrázkov. Na zobrazenie grafickej informácie v dvojrozmernej rovine (obrazovke monitora) sa používajú dva prístupy: rastrový a vektorový.

S vektorovým prístupom grafické informácie je opísaný ako súbor abstraktných geometrických objektov - priamky, úsečky, krivky, obdĺžniky atď. Vektorový popis predpokladá a priori poznatky o štruktúre obrazu.

Rastrová grafika pracuje s ľubovoľnými obrázkami vo forme bitových máp. Raster je popis obrázku v rovine jeho rozdelením (vzorkovaním) na identické prvky pozdĺž pravidelnej mriežky a priradením každého prvku jeho vlastnej farby a akýchkoľvek iných atribútov. Najjednoduchší raster je pravouhlý, najekonomickejší z hľadiska počtu vzoriek na prenos obrázkov je šesťuholníkový. Matematicky je raster po častiach konštantná aproximácia v rovine spojitej obrazovej funkcie.

Prvok rastra sa nazýva pixel. Štandardná identifikácia pixelov:

f(i, j) = (A(i, j), C(i, j)), (17.1.1)

kde A(i, j) Ì R2 - plocha pixelu, C(i, j) Î C - atribút pixelu (zvyčajne farba). Dva najčastejšie používané atribúty sú:

C(i, j) = I(i, j) - intenzita (jas) pixelu;

C(i, j) = (R(i, j), G(i, j), B(i, j)) - atribúty farieb vo farebnom modeli RGB.

V maticovej forme:

Mij ​​​​= (Aij, Cij).

Pri vzorkovaní súvislých obrázkov možno hodnoty Aij definovať dvoma spôsobmi, buď ako hodnoty bodov Aij = (i, j), pre ktoré sú definované atribúty Cij, alebo ako hodnoty štvorcov. Aij = (i, i+1) × (j, j+1) alebo akýkoľvek iný tvar, pričom Cij je definovaný priemernými hodnotami v rámci tohto tvaru (obr. 17.1.1).

V praxi sú X a Y spravidla obmedzené množiny nezáporných celých čísel štvorcového alebo obdĺžnikového rastra s pomerom strán (pomerom strán) šírky k výške rastra, ktorý sa zapisuje napr. "4:3".

Reprezentácia farieb v počítačovej grafike. Pojem farby je založený na vnímaní elektromagnetických vĺn ľudským okom určitý rozsah frekvencie. Nami vnímané denné svetlo má vlnové dĺžky λ od 400 nm (fialová) do 700 nm (červená). Opis svetelného toku môže byť jeho spektrálna funkcia I(λ). Svetlo sa nazýva monochromatické, ak má jeho spektrum iba jednu špecifickú vlnovú dĺžku.

Na sietnici sú dva typy receptorov: tyčinky a čapíky. Spektrálna citlivosť tyčiniek (obr. 17.1.2) je priamo úmerná jasu dopadajúceho svetla. Kužele sú rozdelené do troch typov, z ktorých každý má určitú citlivosť v obmedzených rozsahoch s maximami pre červenú, zelenú a modrú farbu a v tme prudko strácajú citlivosť. Náchylnosť oka na modrú farbu je oveľa nižšia ako na ostatné dve. Dôležitou vlastnosťou ľudského vnímania svetla je lineárnosť pri pridávaní farieb s rôznymi vlnovými dĺžkami.

RGB farebný model (Red, Green, Blue - červená, zelená, modrá) v počítačovej grafike je v súčasnosti najrozšírenejšia. V tomto modeli je spektrálna funkcia reprezentovaná ako súčet kriviek citlivosti pre každý typ kužeľa s nezápornými váhovými koeficientmi (normalizovanými od 0 do 1), ktoré sú označené ako R, G a B. Model je charakterizovaný vlastnosť aditívnosti na získanie nových farieb. Napríklad kódovanie spektrálnych funkcií:

Čierna: fblack = 0, (R, G, B) = (0,0,0);

Fialová ffialová = fred + fmodrá, (R, G, B) = (1,0,1);

Biela fbiela = fred + fgreen + fblue, (R, G, B) = (1,1,1).

Trojrozmerný farebný priestor RGB modelu je znázornený na obr. 17.1.3. Kvôli zvláštnostiam vnímania svetla receptormi nie sú v tomto modeli reprezentovateľné všetky farby viditeľné pre ľudí. Podiel reprodukovateľných farieb je však oveľa väčší ako podiel farieb, ktoré nie sú v tomto modeli reprezentovateľné.

Farebný systém CIE XYZ. Medzinárodný štandard zobrazenia farieb CIE (CIE - Commission Internationale de l "Eclairage) bol prijatý Medzinárodnou komisiou pre osvetlenie v roku 1931. Definuje tri základné funkcie ρX (λ), ρY (λ), ρZ (λ) v závislosti od vlnová dĺžka , ktorej lineárne kombinácie s nezápornými koeficientmi (X, Y a Z) vytvárajú všetky farby viditeľné pre človeka. Tieto funkcie zohľadňujú relatívne vnímanie intenzity svetla receptormi oka. V trojrozmernom priestore CIE farebný systém tvorí kužeľ v prvom kvadrante a slúži na kvalitné zobrazenie farebných obrázkov.

17.2. Geometrické transformácie bitových máp

Oblasti a štádiá transformácie. Obrázky je možné rozdeliť na textúrne a detailné. V obrázkoch textúr nesú všetky vzorky (prvky) informáciu (obrázok na TV obrazovke). Detailný obrázok je obrázok, na ktorom možno rozlíšiť rušivé predmety, pozadie a užitočné predmety.

Existujú tri hlavné skupiny algoritmov spracovania obrazu na počítačoch:

1. Primárne (predbežné) spracovanie obrazu za účelom reštaurovania, čistenia od náhodného šumu, zlepšovania kvality, korekcie geometrických skreslení optické systémy(rozostrenie, aberácie atď.).

2. Popis obrázkov, rozpoznávanie vzorov. Vykonáva sa na určenie parametrov detailov obrazu a zahŕňa: nájdenie oblastí obrazu, ktoré sú jednotné z hľadiska osvetlenia a farby, zvýrazňovanie znakov tvaru obrazov, určenie súradníc špeciálnych bodov objektov atď.

3. Efektívne kódovanie na zníženie množstva prenosu a ukladania.

Väčšina metód predbežného spracovania je založená na použití lineárnych priestorovo invariantných (LPI) filtrov. Lineárne algoritmy sa vykonávajú pomocou dvojrozmerných analógov jednorozmerných filtrov FIR a IIR. Môžu byť použité napríklad pri implementácii filtrov na zníženie úrovne šumu v obrázkoch.

FIR filtre sú implementované pomocou konvolučnej metódy. Výhodou 2D FIR filtrov je viditeľnosť, jednoduchosť a absolútna stabilita. IIR filtre sú implementované pomocou diferenčných rovníc a z-transformácií. Sú rýchlejšie ako FIR filtre, ale môžu byť nestabilné. Syntéza dvojrozmerných IIR filtrov sa líši od syntézy jednorozmerných, pretože pre dvojrozmernú funkciu nie je možné explicitne vybrať póly.

Na obnovenie obrázkov a zlepšenie ich kvality môžu byť potrebné aj nelineárne metódy. Napríklad, aby sa potlačil šum a zároveň sa zachovala obrysová časť obrázkov, je potrebné použiť nelineárne alebo lineárne priestorovo neinvariantné (SPNI) filtre, ktoré sú implementované rank algoritmami. Všetky rank nelineárne filtre sú založené na rýchlych algoritmoch na výpočet lokálnych histogramov.

Jednou z takýchto metód je mediánové filtrovanie. Použitie mediánových filtrov je účinné na potlačenie určitých typov šumu a periodického šumu bez súčasného skreslenia signálu, napríklad na potlačenie nárazových emisií hluku, vrátane výpadkov linky. Metódu možno použiť aj na riešenie problémov súvisiacich s rozpoznávaním, napríklad na zvýraznenie tenkých čiar a malých izolovaných objektov.

Algoritmy na opis obrázkov a rozpoznávanie obrázkov sú spravidla nelineárne a majú heuristickú povahu. Znaky objektov sú zvyčajne plocha obrazu objektu, obvod obrysu obrazu, pomer plochy k štvorcu obvodu obrazu. Tvar objektu možno charakterizovať polomerom kružnice vpísanej do obrazu alebo opísanej okolo obrazu predmetu, dĺžkou minimálneho a maximálneho polomeru-vektora od „ťažiska“ obrazu.

Vzorkovanie. Transformácie obrazu v počítači a ukladanie spracovaných údajov sa vykonávajú v diskrétnej forme. Vzorkovanie sa používa na získanie diskrétnej reprezentácie zo súvislých analógových obrazov reálneho sveta. V praxi sa to vykonáva pomocou vstupných zariadení (digitálny fotoaparát, skener, alebo iné). Pre vizuálne vnímanie spracovaných obrazov na výstupných zariadeniach (displej, plotr atď.) sa analógový obraz rekonštruuje podľa jeho diskretizovaného zobrazenia.

V najjednoduchšom prípade čiernobielych obrázkov máme dvojrozmerné pole sa(x, y). Pre farebné obrázky v modeli RGB, berúc do úvahy vlastnosť aditivity pri pridávaní farieb, možno každú vrstvu R, G a B tiež považovať a spracovať ako dvojrozmerné pole s následným sčítaním výsledkov.

Zo spôsobov, ako zovšeobecniť jednorozmernú periodickú diskretizáciu na dvojrozmerný prípad, je najjednoduchšia periodická diskretizácia v pravouhlých súradniciach:

s(n, m) = sa(nDx, mDy),

kde Dx a Dy sú horizontálne a vertikálne intervaly vzorkovania dvojrozmerného spojitého signálu sa(x, y) so spojitými súradnicami x a y. Nižšie sú hodnoty Dx a Dy, ako v jednorozmernom prípade, rovné 1.

Diskretizácia dvojrozmerného signálu vedie aj k periodizácii jeho spektra a naopak. Podmienka informačnej ekvivalencie súradnicových a frekvenčných reprezentácií diskrétneho signálu je tiež zachovaná pri rovnakom počte vzorkovacích bodov v hlavných rozsahoch signálu. Pre pravouhlú diskretizáciu sú priame a inverzné Fourierove transformácie definované výrazmi:

S(k, l) =s(n, m) exp(-jn2pk/N-jm2pl/M), (17.2.1)

S(k, l) =exp(-jn2pk/N) s(n, m) exp(-jm2pl/M), (17,2,1")

s(n, m) = S(k, l) exp(-jn2pk/N-jm2pl/M). (17.2.2)

s(n, m) = exp(-jn2pk/N) S(k, l) exp(-jm2pl/M). (17,2,2")

Tieto výrazy ukazujú, že 2D DFT cez obdĺžnikový vzorkovací raster údajov možno vypočítať pomocou 1D sériových DFT. Druhé súčty výrazov (17.2.1") a (17.2.2") sú jednorozmerné DFT úsekov funkcií s(n, m) a S(k, l) pozdĺž čiar n a k, v tomto poradí a prvé súčty sú jednorozmerné DFT vypočítaných funkcií v sekciách podľa ma l. Inými slovami, počiatočné matice hodnôt s(n, m) a S(k, l) sa najprv prepočítajú na stredné matice s DFT po riadkoch (alebo po stĺpcoch) a medziľahlé matice sa prepočítajú na konečné matice s DFT. po stĺpcoch (resp. po riadkoch).

Aby sa periodické opakovanie spektra (obr. 17.2.1), spôsobené vzorkovaním analógového signálu s frekvenciou Fx=1/Dx a Fy=1/Dy, nezmenilo spektrum v hlavnej frekvencii rozsahu (vo vzťahu k spektru pôvodného analógového signálu), je potrebné a postačuje, aby maximálne frekvenčné zložky fmax v spektre analógového signálu v riadkoch aj v stĺpcoch nepresiahli Nyquistovu frekvenciu (fmax. x £ fN = Fx/2, fmax y £ fM = Fy/2). To znamená, že vzorkovacia frekvencia signálu musí byť aspoň dvakrát vyššia ako maximálna frekvenčná zložka v spektre signálu:

Fx ³ 2fmax. x, Fy ³ 2fmax. y, (17.2.3)

čo zaisťuje, že spektrálne funkcie dosahujú nulové hodnoty na koncoch hlavného rozsahu spektra.

Interpolačné série obnovy dvojrozmerného signálu. Ak je spojitý signál sa(x, y) signálom s obmedzeným spektrom a periódy vzorkovania sú zvolené dostatočne malé a spektrá susedných periód sa neprekrývajú:

Sa(Wx, Wy) = 0 pre |Wx|p/Dx, |Wy|p/Dx,

potom, ako v jednorozmernom prípade, signál sa(x, y) možno rekonštruovať z diskrétneho signálu pomocou dvojrozmerného analógu radu Kotelnikov-Shannon:

sa(x, y) = Sn Sm s(n, m) . (17.2.4)

Frekvenčné skreslenia obrazu a ich eliminácia. Neobmedzené spektrum signálu môže byť tiež vzorkované, ale v tomto prípade je aliasing v susedných periódach, s vysoké frekvencie, veľké Nyquistove frekvencie, budú „maskované“, ako v jednorozmernom prípade, pod nízke frekvencie hlavné obdobie. Efekt „odrazu“ od hraníc periódy dáva ešte komplexnejší obraz vďaka interferencii frekvencií odrážaných v rôznych súradniciach. K podobnému efektu, známemu ako aliasing, dôjde aj pri podvzorkovaní obrázkov. Tento efekt možno pozorovať obzvlášť zreteľne pri ostrých kontrastných zmenách jasu.

Na boj proti takýmto javom sa používa predbežné filtrovanie (anti-aliasing) - predbežná konvolúcia analógového obrazu s funkciou váhového filtra, ktorá oddeľuje vysokofrekvenčné komponenty, ktoré môžu viesť k aliasingu. V dvojrozmernom prípade je filtrovanie opísané nasledovne:

z(x, y) = h(x", y") ③③ s(x-x", y-y"). (17.2.5)

Treba poznamenať, že analógové obrazy existujú iba v optickom rozsahu, napríklad vo forme svetelného zobrazenia na obrazovke, fotografickom papieri alebo fotografickom filme, ale nemôžu existovať v pamäti počítača. Fyzická implementácia predfiltrovania je preto možná len pri registrácii obrazu jeho rozostrením, čo sa spravidla nepoužíva. Primárne informácie by mali byť vždy zaznamenané s maximálnou úplnosťou a presnosťou a čistenie primárnych informácií od nepotrebných detailov a redundancie je otázkou následného spracovania údajov. Preto vo vzťahu k rovnici 17.2.5 môže byť dvojrozmerné predfiltrovanie vo svojej praktickej realizácii iba filtrovaním obrazov vzorkovaných s veľkou rezervou v hlavnom frekvenčnom rozsahu (s nadmerným rozlíšením) a spravidla sa používa , pri prevzorkovaní na väčší krok, napríklad pri kompresii obrázkov. Predfiltrovanie môže byť tiež zabudované do zobrazovacích algoritmov.

Na obr. 17.2.3 a nižšie, tabuľka 17.2.1 ukazuje príklady najbežnejších jednorozmerných antialiasingových filtrov. Môžu byť implementované aj vo forme analógových filtrov a používajú sa napríklad pri prenose televíznych riadkov obrazu v analógovej forme cez rádiové kanály (horizontálny anti-aliasing). V zásade je možné podobnú operáciu vykonať na stĺpcoch (duplikát - obrázok) a po sčítaní obrázka sa vykoná kompletná operácia vyhladzovania, táto metóda však patrí skôr do oblasti špeciálneho vedeckého výskumu.

Tabuľka 17.2.1.

Základné váhové funkcie

Dvojrozmerné analógy jednorozmerných filtrov f1(x) sú konštruované v dvoch variantoch symetrie: alebo ako funkcia polomeru:

f2(x, y) = f1(),

alebo ako dielo:

f2(x, y) = f1(x) x f1(y).

Prvá možnosť je správnejšia, ale druhá má vlastnosť oddeliteľnosti, t. j. dvojrozmernú konvolúciu možno vykonať dvoma jednorozmernými konvolúciami postupne v riadkoch s f1(x) a v stĺpcoch s f1(y).

Prevzorkovanie obrázkov alebo prevzorkovanie je zmena vzorkovacej frekvencie digitálneho signálu. Pre digitálne obrázky to znamená zmenu veľkosti obrázka.

Existujú rôzne algoritmy prevzorkovania obrázkov. Napríklad na 2-násobné zväčšenie obrazu pomocou metódy bilineárnej interpolácie sa medziľahlé stĺpce a riadky získajú lineárnou interpoláciou hodnôt susedných stĺpcov a riadkov. Každý bod nového obrázku je možné získať ako vážený súčet väčšieho počtu bodov pôvodného obrázku (bikubická a iné typy interpolácie). Prevzorkovanie najvyššej kvality sa dosiahne pri použití algoritmov, ktoré berú do úvahy nielen čas, ale aj frekvenčnú oblasť signálu.

Zvážte algoritmus prevzorkovania s maximálnym zachovaním frekvenčných informácií obrazu. Budeme uvažovať o fungovaní algoritmu na jednorozmerných signáloch, pretože dvojrozmerný obraz možno najskôr roztiahnuť alebo stlačiť horizontálne (v riadkoch) a potom vertikálne (v stĺpcoch) a prevzorkovanie dvojrozmerného obrazu môže byť zredukované na prevzorkovanie jednorozmerných signálov.

Predpokladajme, že máme jednorozmerný signál (obr. 17.2.4), daný na intervale 0-T a diskretizovaný s krokom Dt=1 (N intervalov). Signál je potrebné "natiahnuť" o m krát. Spektrum signálu znázorneného na obrázku je vypočítané rýchlou Fourierovou transformáciou (FFT, počet vzoriek spektra sa rovná počtu vzoriek signálu) a je uvedené v hlavnom rozsahu FFT (0-2p, Nyquistova frekvencia wN = p/Dt = p, alebo 0,5N podľa číslovania vzoriek spektra s krokom pozdĺž spektra Df = 1/T alebo Dw = 2p/T). Strečing vyžaduje 2 kroky.

Prvým krokom je nulová interpolácia, ktorá zväčší dĺžku signálu m-krát. (obr. 17.2.5). Všetky vzorky pôvodného signálu je potrebné vynásobiť ma potom za každú vzorku signálu vložiť nulovú hodnotu m-1. Na intervale 0-T, ktorého hodnota zostáva nezmenená, je teraz m-krát viac vzorkovacích intervalov (mN) a nový vzorkovací krok bude rovný Dx=Dt/m. V súlade s tým je nová Nyquistova frekvencia pre tento signál mp/Dt = mp. Fyzická hodnota kroku spektra v jednotkách frekvencie je však opačná ako fyzikálna hodnota intervalu nastavenia signálu (Df=1/T), a preto FFT na mN signálových bodoch vypočíta mN bodov spektra v hlavný rozsah FFT 0-14pm s krokom spektra pôvodného signálu, v ktorom bude prítomných m-periód spektra pôvodného signálu (jedna hlavná a m-1 strana).

Druhým krokom je odfiltrovanie postranných pásiem spektra pomocou dolnopriepustného filtra, či už v časovej alebo spektrálnej doméne. Na obr. 17.2.6 sa spektrum vyčistilo a vykonala sa inverzná Fourierova transformácia, v dôsledku čoho sa získal signál m-krát dlhší ako pôvodný signál pri plnom zachovaní všetkých frekvenčných informácií.

Podľa podobného princípu možno zostaviť algoritmus na kompresiu (decimáciu) signálu n-krát, pričom poradie krokov je obrátené. Pri kompresii signálu sa zvýši krok vzorkovania signálu a tým sa zníži Nyquistova frekvencia, zatiaľ čo hraničné vysoké frekvencie (šum a nevýznamné vysokofrekvenčné časti spektra signálu) sa budú odrážať od hranice hlavného rozsahu. a pridané k hlavným informáciám, čím sa vytvárajú skreslenia. Aby sa tento jav eliminoval, signál sa najprv dolnopriepustne filtruje s medznou frekvenciou rovnajúcou sa novej Nyquistovej frekvencii (anti-aliasing) a až potom sa signál zdecimuje stenčovaním.

Keď sa prevzorkovanie vykonáva iba v časovej oblasti, algoritmy naťahovania a kompresie sa zvyčajne kombinujú do jedného sekvenčného procesu s nastavením zmeny kroku vzorkovania vo forme pomeru m/n, čo umožňuje nastaviť celočíselné hodnoty m a n pre zlomkové hodnoty zmeny kroku vzorkovania. To výrazne zjednodušuje algoritmy a zvyšuje efektivitu a kvalitu ich práce. Napríklad, keď sa signál natiahne 1,5-krát pri m/n = 3/2, signál sa najskôr roztiahne 3-krát (jednoduché a rovnomerné pridanie núl ku všetkým vzorkám, potom sa vykoná dolnopriepustná filtrácia, po ktorej signál je zdecimovaný faktorom dva. Antialiasingový filter nie je potrebný, pretože jeho medzná frekvencia sa prekrýva s frekvenciou prvého dolnopriepustného filtra. Pri reverznej kompresii (napríklad m/n = 2/3 ), podobne sa používa iba antialiasingový filter.

17.3. filtrovanie obrázkov

Filtrovanie obrázkov je operácia, ktorej výsledkom je obrázok rovnakej veľkosti, získaný z pôvodného podľa určitých pravidiel. Typicky je intenzita (farba) každého pixelu vo výslednom obrázku určená intenzitami (farbami) pixelov nachádzajúcich sa v niektorom z jeho susedstiev na pôvodnom obrázku.

Pravidlá filtrovania môžu byť veľmi rôznorodé. Filtrovanie obrazu je jednou z najzákladnejších operácií počítačového videnia, rozpoznávania vzorov a spracovania obrazu. Prevažná väčšina metód spracovania obrazu začína jedným alebo druhým filtrovaním pôvodných obrázkov.

Linkové filtre majú veľmi jednoduchý matematický popis. Budeme predpokladať, že pôvodný poltónový obraz A je daný a intenzity jeho pixelov označíme A(x, y). Lineárny filter je definovaný reálnou hodnotou h (jadro filtra) definovanou na rastri. Samotné filtrovanie sa vykonáva pomocou operácie diskrétnej konvolúcie (vážený súčet):

B(x, y) = h(i, j) ③③A(x, y) = h(i, j) A(x-i, y-j). (17.3.1)

Výsledkom je obrázok B. Zvyčajne je jadro filtra nenulové iba v niektorom okolí N bodu (0, 0). Mimo tohto okolia sa h(i, j) rovná nule alebo je jej veľmi blízke a možno ho zanedbať. Sčítanie sa vykonáva cez (i, j) н N a hodnota každého pixelu B(x, y) je určená pixelmi obrázka A, ktoré ležia v okne N so stredom v bode (x, y) ( označuje množinu N(x, y) ). Filtračné jadro definované na pravouhlom susedstve N si možno predstaviť ako maticu m x n, kde dĺžky strán sú nepárne čísla. Keď špecifikujete jadro ako maticu, malo by byť vycentrované. Ak sa pixel (x, y) nachádza v blízkosti okrajov obrázka, potom súradnice A(x-i, y-j) pre určité (i, j) môžu zodpovedať neexistujúcim pixelom A mimo obrázka. Tento problém je možné vyriešiť niekoľkými spôsobmi.

Nefiltrujte takéto pixely orezaním okrajov obrázka B alebo použitím pôvodných hodnôt obrázka A pre ich hodnoty.

Nezahŕňajte chýbajúci pixel do súčtu tak, že jeho váhu h(i, j) rozdelíte rovnomerne medzi ostatné pixely v okolí N(x, y).

Predefinujte hodnoty pixelov mimo hraníc obrázka pomocou extrapolácie.

Predefinujte hodnoty pixelov mimo hraníc obrázka pomocou zrkadlového pokračovania obrázka.

Výber metódy sa robí s prihliadnutím na špecifické vlastnosti filtra a obrazu.

Vyhladzovacie filtre. Najjednoduchší obdĺžnikový vyhladzovací filter s polomerom r je daný maticou (2r+1) × (2r+1), ktorej všetky hodnoty sú 1/(2r+1)2 a súčet hodnôt je jeden. Toto je 2D analóg dolnopriepustného 1D filtra s kĺzavým priemerom v tvare U. Pri filtrovaní s takýmto jadrom je hodnota pixelu nahradená priemernou hodnotou pixelu v štvorci 2r+1 okolo nej. Príklad masky filtra 3×3:

.

Jednou z aplikácií filtrov je redukcia šumu. Šum sa mení nezávisle od pixelu k pixelu a za predpokladu, že matematické očakávanie hodnoty šumu je nula, šum susedných pixelov sa pri sčítaní navzájom vyruší. Čím väčšie je filtrovacie okno, tým nižšia je priemerná intenzita šumu, avšak dôjde aj k zodpovedajúcemu rozmazaniu výrazných detailov obrazu. Obraz bielej bodky na čiernom pozadí počas filtrovania (reakcia na jeden impulz) bude rovnomerne šedý štvorec.

Redukcia šumu pomocou obdĺžnikového filtra má značnú nevýhodu: všetky pixely v maske filtra v akejkoľvek vzdialenosti od spracovaného majú rovnaký vplyv na výsledok. O niečo lepší výsledok sa dosiahne úpravou filtra so zvýšením hmotnosti centrálneho bodu:

.

Efektívnejšiu redukciu šumu je možné dosiahnuť, ak s rastúcou vzdialenosťou od spracovávaného klesá vplyv pixelov na výsledok. Túto vlastnosť má Gaussov filter s jadrom: h(i, j) = (1/2ps2) exp(-(i2+j2)/2s2). Gaussov filter má nenulové jadro nekonečnej veľkosti. Hodnota jadra filtra však veľmi rýchlo klesá na n), a preto sa v praxi môžeme obmedziť na konvolúciu s malým oknom okolo (0, 0), pričom polomer okna sa rovná 3σ.

Gaussovo filtrovanie je tiež vyhladzovanie. Na rozdiel od obdĺžnikového filtra však bude obraz bodu s Gaussovým filtrovaním symetrickým rozmazaným bodom, s poklesom jasu od stredu k okrajom. Mieru rozmazania obrazu určuje parameter σ.

Kontrastné filtre . Ak vyhladzovacie filtre znižujú lokálny kontrast obrazu a rozmazávajú ho, potom filtre zvyšujúce kontrast vytvárajú opačný efekt a v podstate sú to filtre s vysokými priestorovými frekvenciami. Jadro zosilňovacieho filtra na (0, 0) má hodnotu väčšiu ako 1, pričom celkový súčet hodnôt sa rovná 1. Zosilňovacie filtre sú napríklad filtre s jadrom daným maticami:

. .

Príklad použitia filtra je znázornený na obr. 17.3.1. Efekt zvýšenia kontrastu je dosiahnutý vďaka tomu, že filter zvýrazňuje rozdiel medzi intenzitami susedných pixelov, pričom tieto intenzity od seba navzájom odstraňuje. Tento efekt bude tým silnejší, čím väčšia bude hodnota centrálneho termínu jadra. Charakteristickým artefaktom lineárneho filtrovania zosilnenia kontrastu je zreteľné svetlo a menej nápadné tmavé halo okolo okrajov.

Diferenčné filtre sú lineárne filtre definované diskrétnymi aproximáciami diferenciálnych operátorov (metódou konečných diferencií). Tieto filtre hrajú dôležitú úlohu v mnohých aplikáciách, napríklad na vyhľadávanie hrán v obraze.

Najjednoduchším diferenciálnym operátorom je x-derivát d/dx, ktorý je definovaný pre spojité funkcie. Bežné varianty podobných operátorov pre diskrétne obrázky sú filtre Prewitt a Sobel:

. .

Filtre aproximujúce derivačný operátor vzhľadom na y-ovú súradnicu d/dy sa získajú transponovaním matíc.

Najjednoduchší algoritmus na výpočet normy gradientu cez tri susedné body:

G(x, y) = .

Používa sa aj zjednodušený vzorec výpočtu:

Výpočet normy gradientu cez štyri susedné body (operátor Roberts):

Sobelov algoritmus používa osem vzoriek jasu v blízkosti centrálneho bodu:

G(x, y) = , G(x, y) @ ,

Gxx, y = - ,

Gyx, y = -.

Spolu s presnejšou definíciou normy gradientu vám Sobelov algoritmus tiež umožňuje určiť smer vektora gradientu v rovine analýzy obrazu vo forme uhla j medzi vektorom gradientu a smerom riadkov matice:

j(x, y) = argtg(Gyx, y/Gxx, y).

Na rozdiel od vyhladzovacích a kontrastných filtrov, ktoré nemenia priemernú intenzitu obrazu, sa v dôsledku použitia rozdielových operátorov spravidla získa obraz s priemernou hodnotou pixelov blízkou nule. Vertikálne kvapky (okraje) pôvodného obrázku zodpovedajú pixelom s veľkými hodnotami modulo vo výslednom obrázku. Preto sa rozdielové filtre nazývajú aj filtre detekcie hraníc objektu.

Podobne ako vyššie uvedené filtre, metódu konečných rozdielov možno použiť na zostavenie filtrov pre iné diferenciálne operátory. Najmä diferenciálny Laplaceov operátor (Laplacián) D= 𝝏2/𝝏x2 + 𝝏2/𝝏y2, ktorý je dôležitý pre mnohé aplikácie, možno aproximovať pre diskrétne obrázky pomocou filtra s maticou (jedna z možností):

.

Ako je vidieť na obr. 17.3.2, v dôsledku použitia diskrétneho Laplacianu, veľké hodnoty v absolútnej hodnote zodpovedajú vertikálnym aj horizontálnym rozdielom jasu. Filter je teda filter, ktorý nájde hranice akejkoľvek orientácie. Hľadanie hrán na obrázku je možné vykonať použitím tohto filtra a zobratím všetkých pixelov, ktorých absolútna hodnota presahuje určitú hranicu.

Tento algoritmus má však značné nevýhody. Hlavnou je neistota pri výbere prahovej hodnoty. Pre rôzne časti obrazu sa zvyčajne dosiahne prijateľný výsledok pri výrazne odlišných prahových hodnotách. Diferenciálne filtre sú navyše veľmi citlivé na obrazový šum.

Dvojrozmerná cyklická konvolúcia. Rovnako ako u 1D signálov, 2D konvolúcia môže byť vykonaná v priestorovej frekvenčnej doméne pomocou FFT algoritmov a násobením 2D obrazových spektier a filtračného jadra. Je tiež cyklický a zvyčajne sa vykonáva v posuvnej verzii. Berúc do úvahy cyklickosť, na výpočet konštantného vzoru spektra jadra sa rozmery masky jadrového filtra zdvojnásobia pozdĺž osí a doplnia sa nulami a rovnaké rozmery masky sa použijú na zvýraznenie okna posúvajúceho sa po obrázku, v rámci ktorého sa vykoná sa FFT. Implementácia FIR filtra s FFT je obzvlášť účinná, ak má filter veľkú referenčnú plochu.

Nelineárne filtre . V digitálnom spracovaní obrazu sú nelineárne algoritmy založené na štatistike poradia široko používané na obnovu obrázkov poškodených rôznymi modelmi šumu. Umožňujú vyhnúť sa dodatočnému skresleniu obrazu pri odstraňovaní šumu, ako aj výrazne zlepšiť výsledky filtrov na obrázkoch s vysokým stupňom šumu.

Predstavme si koncept M-okolia obrazového prvku A(x, y), ktorý je pre toto okolie centrálny. V najjednoduchšom prípade M-okolie obsahuje N-pixelov - bodov, ktoré spadajú do masky filtra, vrátane (alebo nezahŕňajú) centrálneho. Hodnoty týchto N-prvkov možno umiestniť do variačného radu V(r), zoradeného vzostupne (alebo zostupne) a určité momenty tohto radu možno vypočítať, napríklad priemernú hodnotu jasu mN a disperzia dN. Výpočet výstupnej hodnoty filtra, ktorý nahrádza centrálnu vzorku, sa vykonáva podľa vzorca:

B(x, y) = aA(x, y) + (1-a)mN. (17.3.2)

Hodnota koeficientu a = je spojená s určitou závislosťou od štatistiky vzoriek v okne filtra, napr.

a = dN /(dN + k dS), (17.3.3)

kde dS je rozptyl šumu nad obrazom ako celkom alebo nad S-okolím pre S > M a MнS, k je konštanta spoľahlivosti rozptylu S-okolia. Ako vyplýva z tohto vzorca, pre k=1 a dN » dS platí a » 0,5 a hodnota B(x, y) = (A(x, y) + mN)/2, t.j. sú sčítané rovnako na hodnotách centrálnej vzorky a priemernej hodnote pixelov jej M-okolia. S nárastom hodnôt dN sa zvyšuje príspevok hodnoty centrálnej referencie k výsledku, s poklesom hodnota mN. Váhu príspevku priemerných hodnôt nad M-okolie je možné zmeniť o hodnotu koeficientu k.

Voľba štatistickej funkcie a povaha závislosti koeficientu a od nej môže byť značne rôznorodá (napríklad podľa rozptylov rozdielov odčítaní v M-okolí s centrálnym odčítaním) a závisí jednak od veľkosť otvoru filtra a charakter obrázkov a šumu. Hodnota koeficientu a musí v podstate špecifikovať stupeň poškodenia centrálnej vzorky a podľa toho aj výpožičnú funkciu na jej korekciu vzoriek z M-okolia.

Najjednoduchšie a najbežnejšie typy nelineárnych filtrov na spracovanie obrazu sú prahové a mediánové filtre.

Prahové filtrovanie sa uvádza napríklad takto:

B(x, y) =

Hodnota p je prahová hodnota filtra. Ak hodnota centrálneho bodu filtra prekročí priemernú hodnotu vzoriek mN v jeho M-okolí o prahovú hodnotu, potom je nahradená priemernou hodnotou. Prahová hodnota môže byť buď konštantná alebo funkčne závislá od hodnoty centrálneho bodu.

Stredné filtrovanie je definovaný nasledovne:

B(x, y) = med (M(x, y)),

t.j. výsledkom filtrovania je stredná hodnota susedných pixelov, ktorých tvar je určený maskou filtra. Mediánové filtrovanie dokáže efektívne odstrániť šum z obrázka, ktorý nezávisle ovplyvňuje jednotlivé pixely. Takýmito rušeniami sú napríklad „rozbité“ pixely pri digitálnom snímaní, „snehový“ šum, keď sú niektoré pixely nahradené pixelmi s maximálnou intenzitou atď. Výhodou mediánového filtrovania je, že „horúci“ pixel na tmavom pozadí bude nahradil tmavé, a nie "rozmazané" po okolí.

Mediánové filtrovanie má výraznú selektivitu vzhľadom na prvky poľa, ktoré sú nemonotónnou zložkou postupnosti čísel v otvore filtra. Mediánový filter zároveň ponecháva monotónnu zložku sekvencie nezmenenú. Vďaka tejto funkcii stredné filtre s optimálne zvolenou clonou zachovávajú ostré hrany objektu bez skreslenia, potláčajú nekorelovaný alebo slabo korelovaný šum a malé detaily.

Extrémne filtre určené pravidlami:

Bmin(x, y) = min(M(x, y)),

Bmax(x, y) = max (M(x, y)),

t.j., výsledok filtrovania je minimálny a maximálna hodnota pixelov v maske filtra. Takéto filtre sa spravidla používajú pre binárne obrázky.

17.4. KOMPRESIA OBRAZU

Typický obrázok s rozlíšením asi 3000×2000 pri 24 bitoch na pixel na prenos farieb má veľkosť 17 megabajtov. Pri profesionálnych zariadeniach môže byť veľkosť výsledného obrazového rastra oveľa väčšia, farebná hĺbka je až 48 bitov na pixel a veľkosť jedného obrázka môže byť aj viac ako 200 megabajtov. Preto sú algoritmy kompresie obrázkov veľmi dôležité na zníženie množstva údajov reprezentujúcich obrázok.

Existujú dve hlavné triedy algoritmov:

1. Bezstratová kompresia A (bezstratová kompresia), ak existuje taký inverzný algoritmus A-1, že pre ľubovoľné h - obraz A[h] = h1 máme A-1 = h. Používa sa bezstratová kompresia v grafických formátov obrazové reprezentácie ako: GIF, PCX, PNG, TGA, TIFF a používa sa pri spracovaní obzvlášť cenných primárnych informácií (medicínske snímky, letecké a vesmírne snímky atď.), kedy je nežiaduce aj najmenšie skreslenie

2. Stratová kompresia, ak neposkytuje možnosť presnej obnovy pôvodného obrazu. Približný algoritmus obnovy obrazu spárovaný s A bude označený ako A*. Pár (A, A*) je zvolený tak, aby poskytoval vysoký kompresný pomer pri zachovaní vizuálnej kvality. Stratová kompresia sa používa v grafických formátoch: JPEG, JPEG2000 atď.

Všetky algoritmy a príkazy sa vzťahujú na obrázky aj na ľubovoľné sekvencie, ktorých prvky môžu nadobudnúť konečný počet hodnôt. Zároveň je potrebné vziať do úvahy, že neexistujú žiadne ideálne algoritmy, ktoré dokážu komprimovať akýkoľvek súbor údajov bez straty.

Algoritmy kódovania dĺžky opakovania (RLE). založené na jednoduchý princíp: nahradenie opakujúcich sa skupín prvkov pôvodnej postupnosti dvojicou (množstvo, prvok), alebo len množstvo.

bitová úroveň. Pôvodné dáta budeme uvažovať na úrovni sekvencie bitov, napríklad reprezentujúcich čiernobiely obrázok. Zvyčajne je za sebou niekoľko 0 alebo 1 a je možné zakódovať počet po sebe idúcich rovnakých číslic. Ale počet opakovaní musí byť tiež zakódovaný v bitoch. Dá sa uvažovať, že každý počet opakovaní sa mení od 0 do 7 (3-bitový kód), pričom sa strieda sekvencia kódov jednotiek a núl. Postupnosti môžeme porovnávať napríklad s číslami 7 0 4, teda 7 jednotiek, 0 núl, 4 jednotky, pričom máme nový rok - Čím dlhšie sekvencie identických bitov, tým väčší efekt. Takže sekvencia 21 jednotiek, 21 núl, 3 jednotiek a 7 núl je zakódovaná nasledovne: t.j. z pôvodnej sekvencie 51 bitov máme sekvenciu 36 bitov.

Úroveň bajtov. Predpokladajme, že vstupom je obrázok v odtieňoch sivej, kde je pre hodnotu intenzity pixelov alokovaný 1 bajt, pričom je výrazne znížené očakávanie dlhého reťazca identických bitov.

Vstupný tok rozdelíme na bajty (kód od 0 do 255) a opakované bajty zakódujeme ako pár (číslo, písmeno). Nie je možné zmeniť jeden bajt. Takže bajty AABBBCDAA kódujú (2A) (3B) (C) (D) (2A).

Modifikácie tohto algoritmu sa však len zriedka používajú samostatne (napríklad vo formáte PCX), pretože podtrieda sekvencií, na ktoré je algoritmus účinný, je relatívne úzka. Častejšie sa používajú ako jeden zo stupňov kompresného potrubia.

Slovníkové algoritmy namiesto kódovania iba jedného prvku prichádzajúcej sekvencie sa vykonáva kódovanie reťazca prvkov. Toto používa slovník reťazcov (vytvorený zo vstupnej sekvencie) na kódovanie nových.

Algoritmus LZ77 bol jedným z prvých, ktorý používal slovník. N posledných už zakódovaných prvkov sekvencie sa používa ako slovník. Počas kompresie sa podsekvencia slovníka „skĺzne“ po prichádzajúcej sekvencii. Reťazec prvkov na výstupe je zakódovaný nasledovne: pozícia zhodnej časti spracovávaného reťazca prvkov v slovníku - posun (vzhľadom k aktuálnej polohe), dĺžka, prvý prvok nasledujúci za zhodnou časťou reťazca. Dĺžka zodpovedajúceho reťazca je zhora obmedzená číslom n. Úlohou je teda nájsť najväčší reťazec zo slovníka, ktorý zodpovedá spracovanej sekvencii. Ak neexistujú žiadne zhody, zapíše sa offset nula, dĺžka jedna a prvý prvok nekódovanej sekvencie.

Vyššie opísaná schéma kódovania vedie ku koncepcii posuvného okna, ktoré pozostáva z dvoch častí:

Podsekvencia už zakódovaných prvkov dĺžky N-dictionary - search buffer;

Následná postupnosť dĺžky n z reťazca prvkov, pre ktoré bude vykonaný pokus o nájdenie zhody - buffer Náhľad(predbežná vyrovnávacia pamäť).

Dekódovanie komprimovanej sekvencie je dekódovanie zaznamenaných kódov: ku každému záznamu sa priradí reťazec zo slovníka a explicitne zapísaný prvok, po ktorom sa slovník posunie. Slovník sa znova vytvorí pri spustení dekódovacieho algoritmu.

Tento algoritmus je predchodcom celej rodiny algoritmov. Medzi jeho výhody patrí slušný stupeň kompresie na dostatočne veľkých sekvenciách a rýchla dekompresia. Medzi nevýhody patrí nízka rýchlosť kompresie a nižší kompresný pomer ako alternatívne algoritmy.

Algoritmus LZW. Slovník v tomto algoritme je tabuľka, ktorá je pri behu algoritmu vyplnená reťazami prvkov. Proces kompresie hľadá najdlhší reťazec už zapísaný do slovníka. Zakaždým, keď sa v slovníku nenájde nový reťazec prvkov, pridá sa do slovníka a zaznamená sa kód reťazca. Teoreticky neexistuje obmedzenie veľkosti tabuľky, ale obmedzenie veľkosti umožňuje lepšiu kompresiu hromadením nepotrebných (nevyskytujúcich sa) reťazcov. Čím viac záznamov tabuľka obsahuje, tým viac informácií je potrebné prideliť kódom uloženia.

Dekódovanie spočíva v priamom dekódovaní kódov, t.j. v konštrukcii slovníka a výstupe zodpovedajúcich reťazcov. Slovník sa inicializuje rovnakým spôsobom ako v kódovači. Medzi výhody algoritmu patrí vysoký stupeň kompresie a pomerne vysoká rýchlosť kompresie aj dekódovania.

Entropické kódovacie algoritmy priraďte každému prvku sekvencie kód tak, aby jeho dĺžka zodpovedala pravdepodobnosti výskytu prvku. Kompresia nastáva nahradením prvkov pôvodnej sekvencie, ktoré majú rovnakú dĺžku (každý prvok zaberá rovnaký počet bitov) prvkami rôznych dĺžok, úmerných zápornému logaritmu pravdepodobnosti, t. j. prvky, ktoré sa vyskytujú častejšie ako ostatné, majú kód. menšej dĺžky.

Huffmanov algoritmus používa prefixový kód s premenlivou dĺžkou, ktorý má špeciálnu vlastnosť: kratšie kódy sa nezhodujú s predponou (počiatočnou časťou) dlhších. Takýto kód umožňuje kódovanie jedna ku jednej. Proces kompresie spočíva v nahradení každého prvku vstupnej sekvencie jeho kódom. Konštrukcia súboru kódov sa zvyčajne uskutočňuje pomocou tzv kódové stromy.

Huffmanov algoritmus je dvojpriechodový. Prvý prechod cez obrázok vytvorí tabuľku hmotností prvkov a pri druhom prechode prebieha kódovanie. Existujú implementácie algoritmu pevnej tabuľky. Často sa stáva, že apriórne rozdelenie pravdepodobnosti prvkov abecedy nie je známe, pretože celá postupnosť nie je dostupná naraz, pričom sa používajú adaptívne modifikácie Huffmanovho algoritmu.

Stratová kompresia obrazu. Množstvo informácií potrebných na uloženie obrázkov je zvyčajne veľké. Klasické algoritmy, ktoré sú všeobecnými algoritmami, neberú do úvahy, že komprimovaná informácia je obraz - dvojrozmerný objekt a neposkytujú dostatočný stupeň kompresie.

Stratová kompresia je založená na vlastnostiach ľudského vnímania obrazu: najväčšia citlivosť v určitom rozsahu farebných vlnových dĺžok, schopnosť vnímať obraz ako celok, bez povšimnutia malých skreslení. Hlavnou triedou obrázkov, na ktoré sa zameriavajú stratové kompresné algoritmy, sú fotografie, obrázky s plynulými prechodmi farieb.

Odhad straty obrazu. Existuje mnoho opatrení na odhadnutie strát na obrázkoch po ich obnove (dekódovaní) z komprimovaných, avšak pre všetky je možné vybrať dva obrázky tak, aby ich miera rozdielu bola dostatočne veľká, ale rozdiely boli takmer nepostrehnuteľné. oko. A naopak - môžete zachytiť obrázky, ktoré sa veľmi líšia podľa oka, ale majú malý rozdiel.

Štandardná numerická miera straty je zvyčajne štandardná odchýlka (RMS) hodnôt pixelov rekonštruovaného obrazu od originálu. Najdôležitejším „meradlom“ hodnotenia straty je však názor pozorovateľa. Čím menej rozdielov (alebo lepšie ich absencia) pozorovateľ zaznamená, tým je kompresný algoritmus kvalitnejší. Algoritmy stratovej kompresie často umožňujú užívateľovi vybrať si množstvo „stratených“ dát, t. j. právo vybrať si medzi kvalitou a veľkosťou komprimovaný obrázok. Prirodzene, čím lepšia je vizuálna kvalita pri vyššom kompresnom pomere, tým lepší je algoritmus.

Fourierova transformácia. Vo všeobecnom prípade možno obraz považovať za funkciu dvoch premenných, definovaných v bodoch konečného rastra. Množina takýchto funkcií na bodoch pevného konečného rastra tvorí konečnorozmerný euklidovský priestor a možno na ne aplikovať diskrétnu Fourierovu transformáciu, teda spektrálnu reprezentáciu obrazu. To poskytuje:

Nekorelácia a nezávislosť spektrálnych koeficientov, t.j. presnosť zobrazenia jedného koeficientu nezávisí od žiadneho iného.

- Energetické zhutnenie. Transformácia ukladá základné informácie v malom počte koeficientov. Táto nehnuteľnosť je najvýraznejší vo fotorealistických obrázkoch.

Koeficienty spektrálneho zobrazenia sú amplitúdy priestorových frekvencií obrazu. V prípade obrázkov s plynulými prechodmi je väčšina informácií obsiahnutá v nízkofrekvenčnom spektre.

Kompresný algoritmus použitý v formát JPEG, je postavená na použití diskrétnej kosínusovej Fourierovej transformácie. Schéma kompresie v algoritme je potrubie, kde táto transformácia je len jednou z fáz, ale jednou z hlavných. Algoritmus obsahuje tieto hlavné operácie:

1. Preneste sa do farebného priestoru YCbCr. Y je tu luma zložka, Cb a Cr sú farbonosné zložky. Ľudské oko je citlivejšie na jas ako na farbu. Preto je dôležitejšie zachovať väčšiu presnosť pri vysielaní Y ako pri vysielaní Cb a Cr.

2. Diskrétna kosínusová transformácia (DCT). Obraz je rozdelený na bloky 8 × 8. Na každý blok sa aplikuje diskrétna kosínusová transformácia (zvlášť pre zložky Y, Cb a Cr).

3. Redukcia vysokofrekvenčných zložiek v matriciach DCT. Ľudské oko takmer nevníma zmeny vo vysokofrekvenčných zložkách, preto je možné koeficienty zodpovedné za vysoké frekvencie uložiť s menšou presnosťou.

4. Kľukaté usporiadanie matíc. Toto je špeciálny maticový prechod na získanie jednorozmernej sekvencie. Najprv príde prvok T00, potom T01, T10, T1 Navyše pre typické fotorealistické obrázky budú najprv nenulové koeficienty zodpovedajúce nízkofrekvenčným zložkám a potom veľa núl (vysokofrekvenčné zložky).

5. Najprv komprimujte Metóda RLE a potom Huffmanovou metódou.

Algoritmus obnovy obrazu funguje v opačné poradie. Kompresný pomer je od 5 do 100 alebo viackrát. Zároveň zostáva vizuálna kvalita väčšiny fotorealistických obrázkov na dobrej úrovni aj pri 15-násobnej kompresii. Algoritmus a formát sú najbežnejšie na prenos a ukladanie plnofarebných obrázkov.

Waveletová transformácia signály sú zovšeobecnením klasickej Fourierovej transformácie. Výraz "vlnka" (vlnka) v preklade z angličtiny znamená "malá (krátka) vlna". Vlnky sú zovšeobecneným názvom pre rodiny matematických funkcií určitej formy, ktoré sú lokálne v čase a frekvencii a v ktorých sa všetky funkcie získavajú z jednej základnej funkcie jej posúvaním a rozširovaním pozdĺž časovej osi.

V stratových kompresných algoritmoch sú spravidla všetky operácie kompresného potrubia zachované s nahradením diskrétnej Fourierovej transformácie diskrétnou vlnkovou transformáciou. Vlnkové transformácie majú veľmi dobrú frekvenčno-priestorovú lokalizáciu a v tomto ukazovateli prekonávajú tradičné Fourierove transformácie. V tomto prípade je možné použiť silnejšiu kvantizáciu, čím sa zlepšujú vlastnosti sekvencie pre následnú kompresiu. Algoritmy kompresie obrazu založené na tejto transformácii s rovnakým kompresným pomerom ukazujú najlepšie skóre aby sa zachovala kvalita obrazu.

literatúre

46. ​​​​et al. Rýchle algoritmy v digitálnom spracovaní obrazu. - M.: Rozhlas a komunikácia, 1984. - 224 s.

47. Spracovanie obrazu sóje. Časť 2. Metódy a algoritmy. - Sorosov vzdelávací časopis číslo 3, 1996.

48. Šum chrupavky z obrázkov založených na nelineárnych algoritmoch s použitím štatistiky poradia. - Jaroslavľská štátna univerzita, 2007.

49. Andreevské televízne sledovacie systémy. Časť II. Aritmetika - logické základy a algoritmy. Návod. - Petrohrad: Petrohrad, GUITMO, 2005. - 88. roky.

51. Úvod do digitálneho spracovania signálov (matematické základy) - M.: Moskovská štátna univerzita, Laboratórium počítačovej grafiky a multimédií, 2002. - http://pv. *****/dsp/dspcourse. pdf, http://dsp-book. *****/dspkurz. djvu, http://geogin. *****/archiv/dsp/dsp4.pdf.

1i. a iné algoritmické základy rastrovej grafiky. – Internetová univerzita informačných technológií. – http://www. *****/goto/kurz/rastrograf/

2i. Lukin - elektronické systémy: Poznámky k prednáške. ITMO, 2004. - Petrohrad, MFF ITMO, 2004. - http://iff. *****/kons/oes/KL. htm

O zaznamenaných chybách a návrhoch na doplnenie: ****@***ru.

Autorské práva©2008DavydovALE.V.

Tento článok vyvíja algoritmy spracovania obrazu pre inteligentné mobilné roboty založené na fuzzy logike a neurálne siete, ktorý umožňuje výber hraníc v obraze pomocou Sobelovho operátora. Podstatou spracovania obrazu je priniesť pôvodný obraz scény do podoby, ktorá umožňuje vyriešiť problém rozpoznávania jej objektov. Zvažujú sa hlavné problémy, ako aj spôsoby ich riešenia počas počiatočnej prípravy obrazu na rozpoznanie. Podrobne je analyzovaný algoritmus predbežného spracovania využívajúci fuzzy logiku a proces binarizácie obrazu. Na extrakciu hraníc v obraze pomocou Sobelovho operátora bol skonštruovaný fuzzy algoritmus spracovania.

spracovanie obrazu

fuzzy logika

inteligentný systém

rozpoznávanie objektov

1. Vesnin E.N., Veto A.V., Tsarev V.A. K problematike vývoja a aplikácie adaptívnych optoelektronických systémov videnia// Automatizácia v priemysle, 2009.- č. 11.- S. 48-52.

2. Grishin V.A. Systémy videnia pri riešení problémov riadenia bezpilotných prostriedkov // Senzory a systémy, č. 2, 2009.- C. 46-52.

3. Klevalin V.A., Polivanov A.Yu. Metódy digitálneho rozpoznávania v systémoch videnia priemyselných robotov// Mechatronika, automatizácia, riadenie, 2008, č. 5.- S. 56-56.

4. Michajlov S.V., Romanov V.V., Zaikin D.A. Systém videnia na diagnostiku procesu rezania materiálov // Bulletin of computer and informačných technológií, 2007, č. 3.- S. 12-19.

5. Semina M.S. Prehľad riešenia aplikovaných problémov pomocou systémov videnia// http://www.videoscan.ru/page/718#13.

V súčasnosti je automatické spracovanie obrazu jednou z najdôležitejších oblastí v oblasti umelej inteligencie a zahŕňa vývoj robotických systémov, ktoré vykonávajú rozpoznávanie vzorov. Jedným z najúčinnejších nástrojov na rozpoznávanie vzorov sú systémy postavené na fuzzy logike a umelých neurónových sieťach. V systéme technického videnia (VTS) je na vyriešenie rovnakého problému potrebných niekoľko metód a algoritmov rôzne cesty, pričom poskytuje potrebné ukazovatele pre rýchlosť a spoľahlivosť identifikácie.

Podstatou hybridného algoritmu spracovania obrazu vo VS mobilných robotických systémov (MRC) je priniesť pôvodný obraz scény do podoby, ktorá umožňuje riešiť problém rozpoznávania jej objektov.

Algoritmus predspracovania obrazu pomocou fuzzy systému vo VS

Pre spracovanie obrazu predstavuje fuzzy spracovanie množstvo rôznych fuzzy prístupov, ktorými sú porozumenie, reprezentácia, spracovanie obrazu, segmenty a fuzzy množiny. V procese rozpoznávania vzorov má veľký význam proces predbežného spracovania fuzzy obrazu, pretože od neho závisí kvalita údajov, ktoré sa ďalej privádzajú na vstupy neurónovej siete. V rámci riešeného problému je možné vyvinutý algoritmus na predbežné fuzzy spracovanie znázorniť ako nasledujúcu postupnosť krokov (obr. 1): snímanie obrazu pomocou webovej kamery; prevod výsledného farebného obrázka na obrázok v odtieňoch sivej; fuzzy spracovanie obrazu.

Ryža. 1. Algoritmus pre predbežné fuzzy spracovanie obrazu

Prvým krokom pri predbežnom fuzzy spracovaní je teda prevod obrazu z farebného do odtieňov sivej. Prevod farieb obrázka na odtiene sivej sa vykonáva nasledovne. Celá farebná paleta je znázornená ako kocka, ktorej vrcholy zodpovedajú rôznym farbám. Šedá stupnica je umiestnená na uhlopriečke kocky spájajúcej čierne a biele vrcholy.

Ak chcete previesť obrázok na odtiene sivej, pre každý bod obrázka sa vyberú intenzity červenej, zelenej a modrej zložky farby a potom sa farba prevedie podľa nasledujúceho vzorca:

kde je nová hodnota farby, je intenzita červenej zložky farby, je intenzita zelenej zložky farby a je intenzita modrej zložky farby. Výstup každého algoritmu v odtieňoch sivej je medzi 0 a 1. Existuje niekoľko metód na konverziu obrázkov len na odtiene sivej. Metóda na určenie svetlosti využíva priemernú hodnotu medzi dvoma najviac a najmenej významnými farbami: . Priemerná metóda používa priemer všetkých troch farieb: . Metóda jasu používa vážený priemer všetkých troch farieb na zohľadnenie ľudského vnímania. Takže, keďže ľudské oko najviac vníma zelenú, za najdôležitejšiu sa považuje jeho hmotnosť: . Použitá metóda detekcie jasu softvér na spracovanie obrazu. Implementovala funkciu " rgb2gray“ v prostredí MATLAB a často sa používa na počítačové videnie. V procese fuzzy predbežného spracovania má proces konvertovania obrázkov z farieb (RGB) do odtieňov sivej pomocou metódy detekcie jasu. Ďalej sa obrázok prevedie z odtieňov sivej na čiernobiely (obr. 2).

Ryža. 2. proces prevodu obrázkov z farebných do odtieňov sivej

Binarizácia obrazu počas predspracovania

Účelom predbežného spracovania fuzzy obrazu je vytvorenie a následné zlepšenie obrazu, jeho binarizácia a kódovanie (najmä získanie obrysového znázornenia). Binarizácia obrazu je proces premeny obrazu pozostávajúceho z gradácie jednej farby (v našom prípade sivej) na binárny obraz, t.j. obrázok, v ktorom môže mať každý pixel iba dve farby (v našom prípade sú to čierne a biele). V dôsledku takejto transformácie sa farba pixelu podmienečne považuje za rovnú nule alebo jednej, zatiaľ čo pixely s nulovou hodnotou (v tomto prípade sú to biele pixely) sa nazývajú pozadie a pixely s hodnotou rovnou jedna (čierna) sa nazýva popredie. Binárny obraz získaný v dôsledku takejto transformácie je však skreslený v porovnaní s originálom, ktorý sa vyznačuje výskytom medzier a rozmazaní na objektoch, výskytom obrazového šumu v homogénnych oblastiach, ako aj stratou integrity. štruktúry objektu.

Strata celistvosti predmetu, ako aj roztrhnutie predmetu vzniká z viacerých príčin, ako je veľké nerovnomerné osvetlenie predmetu alebo dotyk (alebo prekrývanie predmetov na sebe). Je to prekrytie (alebo dotyk - ako špeciálny prípad prekrytia), ktoré spôsobuje zvláštne ťažkosti pri spracovaní. na jednej strane môže byť obraz niekoľkých objektov interpretovaný ako jeden objekt a na druhej strane algoritmy, ktoré kontrolujú geometrickú integritu objektu, vytvoria medzery v prekrývajúcich sa bodoch, čím sa tieto oblasti zobrazia ako pozadie. Zložitosť spracovania spočíva v absencii teoretického riešenia problému interpretácie prekrytia objektov, pretože časť informácií sa stratí. Pri implementácii algoritmov v praxi sa jedna z uvedených možností považuje za správne rozhodnutie - buď sa priesečník považuje za pokračovanie aktuálneho objektu, alebo sa oblasť prekrytia považuje za pozadie.

Prahová hodnota prevedie farebný alebo sivý obrázok na čiernobiely. Prahové transformácie sú ústredným prvkom aplikovaných problémov segmentácie obrazu vďaka ich intuitívnym vlastnostiam a jednoduchosti implementácie. Pre každý pixel v obraze sa skúma jeho úroveň intenzity, ak je jeho hodnota nad nejakou prahovou úrovňou, zodpovedá bielej. Ak je pod nastavenou hranicou, nastaví sa na čiernu. Prahová úroveň bude medzi 0 a 255.

V súčasnosti existuje veľké množstvo metód binarizácie. Podstatou tejto transformácie rastrových obrázkov je komparatívna analýza jas aktuálneho pixelu s nejakou prahovou hodnotou : ak jas aktuálneho pixelu prekročí prahovú hodnotu, t.j. , potom bude farba pixelu v binárnom obrázku biela, inak bude farba čierna. Prahová plocha je matica, ktorej rozmer zodpovedá rozmeru pôvodného obrazu.

V procese binarizácie sú všetky metódy rozdelené do dvoch skupín podľa princípu konštrukcie prahovej plochy - ide o metódy globálneho a lokálneho spracovania binarizácie. Pri globálnych metódach spracovania binarizácie je prahová plocha rovina s konštantnou hodnotou prahového jasu, t.j. prahová hodnota sa vypočíta na základe analýzy histogramu celého obrázka a je rovnaká pre všetky pixely pôvodného obrázka. Global Thresholding má významnú nevýhodu – ak má pôvodný obrázok nerovnomerné osvetlenie, oblasti, ktoré sú slabo osvetlené, sú úplne klasifikované ako popredie. Pri lokálnych metódach spracovania binarizácie sa prahová hodnota mení pre každý bod na základe niektorých vlastností oblasti patriacej do nejakého okolia daného bodu. Nevýhodou tohto typu transformácie je pomalá rychlosť práca algoritmov spojených s prepočítaním prahových hodnôt pre každý bod obrazu.

Ako metódu riešenia problému používame Bernsenovu metódu. Metóda je založená na myšlienke porovnania úrovne jasu transformovaného pixelu s hodnotami miestnych priemerov vypočítaných v jeho prostredí. Obrazové pixely sa spracovávajú jeden po druhom porovnávaním ich intenzity s priemernými hodnotami jasu v oknách so stredom bodov (obr. 3).

Ryža. 3. Transformácia obrazových pixelov

Fuzzy algoritmus spracovania pre extrakciu okrajov a segmentáciu obrazu

Po prevode obrazu na čiernobiely sa pomocou Sobelovho operátora získa gradientný obraz a privedie sa na vstupy fuzzy spracovania obrazu (FP) (obr. 4).

Fuzzy spracovanie obrazu pozostáva z troch hlavných krokov: fuzzifikácia obrazu, fuzzy inferenčný systém na hodnotách príslušnosti a defuzzifikácia obrazu. Hlavné fuzzy spracovanie obrazu je v strednom kroku (fuzzy inferenčný systém). Po prechode obrazových údajov z úrovne šedej do fuzzifikácie je fuzzy inferenčný systém určený hodnotami príslušnosti. Fuzzifikácia je kódovanie obrazových údajov a defuzzifikácia je dekódovanie výsledkov, ktoré umožňujú spracovanie obrázkov fuzzy metódami.

Obrázok - veľkosť s úrovňami šedej a môže byť definovaná ako fuzzy jednobodová množina poľa (fuzzy množiny môžu byť podporované iba jedným bodom) označujúce hodnotu príslušnosti každého pixelu vo vzťahu k vlastnostiam predobrazu (napr. jas, hladkosť atď.).

(1)

kde a sú pixelové príslušnosti v zápise fuzzy množín. Definícia hodnôt členstva závisí od špecifických požiadaviek konkrétnej aplikácie a od príslušnej znalostnej bázy.

Výstup systému pre vstupný systém je daný nasledujúcim vzorcom:

(2)

Ryža. 4. Fuzzy algoritmus spracovania obrazu na detekciu hrán

Aplikácia neurónových sietí na rozpoznávanie vzorov

Viacvrstvový perceptrón je umelá neurónová sieť pozostávajúca z niekoľkých vstupných uzlov, ktoré tvoria vstupnú vrstvu, jednu alebo viac výpočtových vrstiev neurónov a jednu výstupnú vrstvu (obr. 6). V takýchto sieťach sa signál aplikovaný na vstupnú vrstvu prenáša postupne v smere dopredu z vrstvy na vrstvu. Tento typ ANN sa úspešne používa na riešenie rôznych problémov, najmä na problém rozpoznávania vzorov.

Neurónová sieť spätného šírenia pozostáva z niekoľkých vrstiev neurónov, pričom každý neurón predchádzajúcej vrstvy je spojený s každým neurónom ďalšej vrstvy. V takýchto sieťach je po určení počtu vrstiev a počtu prvkov každej vrstvy potrebné vypočítať hodnoty váh a prahov siete tak, aby sa minimalizovala chyba predpovede. Tento problém sa rieši pomocou rôznych algoritmov učenia. Podstatou týchto algoritmov je prispôsobiť sieť trénovacím údajom. Chyba implementovanej siete bude určená spustením všetkých vstupných údajov a porovnaním skutočných hodnôt získaných na výstupe siete s cieľovými hodnotami. Potom sa získané rozdiely zhrnú do spoločnej, takzvanej chybovej funkcie, ktorá charakterizuje častá chyba siete. Častejšie sa však ako funkcia chýb berie súčet štvorcových chýb.

Jedným z najbežnejších algoritmov učenia pre viacvrstvové neurónové siete je algoritmus spätného šírenia. V tomto algoritme sa vypočíta gradientový vektor chybovej plochy. Potom sa posunieme o určitú mieru v smere vektora (naznačí nám smer najstrmšieho klesania), kde už bude hodnota chyby menšia. Takýto konzistentný pokrok postupne povedie k minimalizácii chyby. Tu vzniká problém pri určovaní výšky zálohy. Ak je veľkosť kroku relatívne veľká, povedie to k najrýchlejšiemu zostupu, ale existuje možnosť „skočenia“

požadovaný bod alebo ísť nesprávnym smerom, ak má povrch pomerne zložitý tvar. Napríklad, ak je povrch úzka roklina so strmými svahmi, algoritmus sa bude pohybovať veľmi pomaly a bude skákať z jedného svahu na druhý. Ak je veľkosť kroku malá, povedie to k nájdeniu najoptimálnejšieho smeru, ale môže to výrazne zvýšiť počet iterácií. Na dosiahnutie čo najoptimálnejšieho výsledku sa veľkosť kroku berie úmerne k strmosti svahu s určitou konštantou - rýchlosťou učenia. Voľba tejto konštanty sa uskutočňuje experimentálne a závisí od podmienok konkrétneho problému.

Uveďme si nasledujúci zápis. Maticu váhových koeficientov zo vstupov do skrytej vrstvy označíme a maticu váh spájajúcich skrytú a výstupnú vrstvu označíme . Pre indexy použijeme nasledujúci zápis: vstupy budeme číslovať iba indexom , prvky skrytej vrstvy - indexom a výstupy - indexom . Počet sieťových vstupov je , počet neurónov v skrytej vrstve je , počet neurónov vo výstupnej vrstve je . Nechajte sieť trénovať na vzorke , . Potom bude algoritmus učenia pre viacvrstvový perceptrón vyzerať takto:

Krok 1. Inicializácia siete. Váhovým koeficientom sú priradené malé náhodné hodnoty, napríklad z rozsahu (-0,3, 0,3); sú nastavené - parameter presnosti učenia, - parameter rýchlosti učenia (spravidla sa môže v procese učenia stále znižovať), - maximálny povolený počet iterácií.

Krok 2. Vypočítajte aktuálny výstupný signál. Jeden z obrázkov tréningovej vzorky sa privádza na sieťový vstup a určujú sa hodnoty výstupov všetkých neurónov neurónovej siete.

Krok 3. Nastavenie synoptických váh. Vypočítajte zmenu váh pre výstupnú vrstvu neurónovej siete pomocou vzorcov:

kde , . Vypočítajte zmenu hmotnosti pre skrytú vrstvu pomocou vzorcov: , kde

Krok 4. Kroky 2-3 sa opakujú pre všetky tréningové vektory. Tréning sa skončí, keď hodnota chybovej funkcie pre každý z trénovacích obrázkov neprekročí e alebo po maximálnom povolenom počte opakovaní.

V kroku 2 je lepšie prezentovať vektory z trénovacej sekvencie na vstup v náhodnom poradí.

Počet vstupov a výstupov siete je spravidla diktovaný podmienkami problému a experimentálne sa zistí veľkosť skrytej vrstvy. Zvyčajne je počet neurónov v ňom 30-50% z počtu vstupov. Príliš veľa neurónov v skrytej vrstve spôsobuje, že sieť stráca schopnosť zovšeobecňovať (jednoducho si dôkladne pamätá prvky trénovacej vzorky a na podobné vzorky nereaguje, čo je pre úlohy rozpoznávania neprijateľné). Ak je počet neurónov v skrytej vrstve príliš malý, sieť sa jednoducho nedokáže naučiť.

Záver

Zvažujú sa hlavné problémy, ako aj spôsoby ich riešenia počas počiatočnej prípravy obrazu na rozpoznanie. Podrobne je analyzovaný algoritmus predbežného spracovania využívajúci fuzzy logiku a proces binarizácie obrazu. Na extrakciu hraníc v obraze pomocou Sobelovho operátora bol skonštruovaný fuzzy algoritmus spracovania.

Recenzenti:

Gagarina L.G., doktor technických vied, profesor, vedúci Katedry informatiky a softvéru výpočtových systémov» Národná výskumná univerzita MIET, Moskva.

Portnov E.M., doktor technických vied, profesor Katedry informatiky a softvéru pre výpočtové systémy, vedúci výskumného laboratória „Control Information Systems“ Národnej výskumnej univerzity „MIET“, Moskva.

Bibliografický odkaz

Podstatou spracovania obrazu je priniesť pôvodný obraz scény do podoby, ktorá umožňuje vyriešiť problém rozpoznávania jej objektov.

Konečným cieľom spracovania obrazu vo VS je pripraviť objekty scény na rozpoznanie, t.j. priraďovanie ich obrázkov k niektorým vopred určeným triedam. Napriek rôznorodosti prezentovaných postupov konverzie informácií sa vo VS zvyčajne rozlišujú tri hlavné fázy spracovania:

1) predbežné spracovanie obrazu;

2) segmentácia;

3) popis.

Predspracovanie má zasa dve základné etapy: tvorbu obrazu a jeho kódovanie (komprimovanie). Postupnosť krokov nie je pevná a závisí od konkrétnej úlohy.

Predspracovanie obrazu

Všetky spôsoby predspracovania obrazu vo VS sú rozdelené na priestorové a frekvenčné. Priestorové metódy sú postupy, ktoré pôsobia priamo na pixely v obrázku. Jas sa používa ako charakteristika obrazu. Y(x, y). Frekvenčné metódy sú spojené s prekladom obrazu do komplexnej roviny pomocou Fourierovej transformácie.

Pri zvažovaní postupov predbežného spracovania sa obmedzíme len na priestorové metódy a pôvodný obrázok budeme považovať za poltónový.

V prvej fáze predspracovania formovanie obrazu. Vytváranie obrazu je postup na priame získanie obrazu vo forme poľa diskrétnych prvkov umiestnených v pamäti video procesora - pixelov, ktoré tvoria maticu alebo obrys.

V STZ sa vo fáze vytvárania obrazu vyberie prah jasu nastavením osvetlenia a obraz sa filtruje.

Filtrácia obraz je najdlhšia a najzložitejšia fáza predbežného spracovania. Vo všeobecnosti filtrovanie rieši tieto hlavné úlohy:

vyhladzovanie (potlačenie vysokofrekvenčného hluku, ako je "sneh");

zvýšenie kontrastu;

výber obrysu.

Postup vyhladzovania sa realizuje ihneď po zvolení prahu jasu. Jeho význam spočíva v spriemerovaní hodnôt funkcie jasu podľa určitého pravidla Y(X, y) vnútri analyzovaného fragmentu obrazu.

Na elimináciu vysokofrekvenčného rušenia typu „sneh“ sa používa dolnopriepustný filter. nevýhodou dolnopriepustné filtrovanie je zhoršenie kontrastu obrazu.

Segmentácia

V dôsledku predbežného spracovania obrázok obsahuje jednu alebo viac obrysových reprezentácií objektov. Postup na oddelenie týchto obrysov a ich priradenie k určitým objektom sa nazýva segmentácia.

Ak je vopred známe, že obraz obsahuje niekoľko objektov, postup segmentácie sa uskutoční po extrakcii obrysu pred fázou kódovania obrazu.

Segmentačné algoritmy sú spravidla založené na hľadaní diskontinuít v obryse a podobnosti oblastí. V prvom prípade sa nájde obrys a jeho softvérový premostenie sa vykoná podľa stanoveného pravidla. Ak je obrys uzavretý, považuje sa za patriaci objektu. V druhom prípade sa určujú oblasti obrazu, ktoré majú spoločné vlastnosti (napríklad rovnaký jas pixelov). Keď sa takéto oblasti nájdu, priradia sa buď k pozadiu, alebo k objektu.

Kódovanie obrázkov

Pre systémy, ktoré spracúvajú obrázky v odtieňoch sivej pomocou priestorových metód, existujú dve hlavné metódy kódovania:

· kódovanie samotného obrazu metódou run length codes;

· kódovanie obrysu obrazu Freemanovým reťazovým kódom.

V oboch prípadoch pri kódovaní dochádza k výraznému zníženiu množstva dát charakterizujúcich obrázok. Účinnosť kódovania je určená stupňom kompresie obrazu.

Podstata kódovania metódou kódov dĺžka série, implementovaný pomocou algoritmu RLE, je reprezentovať obraz ako homogénne segmenty skenovacej čiary, kde jas a farba pixelov sú rovnaké. Každá séria je charakterizovaná zodpovedajúca hodnota a dĺžku série (počet pixelov).

Na zakódovanie priamo obrysu obrazu sa najčastejšie používa reťaz. Freemanov kód(Obr. 6.22, b). V tomto prípade je obrys objektu, začínajúci od určitého bodu, daný sekvenciou vektorov, ktoré nadobúdajú diskrétne hodnoty, pričom uhol sklonu modulu je deliteľný 45. Hodnota modulu je 2, ak je uhol sklonu vektora 45 , a 1, ak je vertikálna alebo horizontálna. Zmena smeru vektora pri prechode z jedného bodu krivky do druhého odráža charakter zmeny modelovanej krivky.

Popis obrázku

Pod popis rozumie sa definícia charakteristických parametrov objektu - znamenia(diskriminátory) potrebné na jej výber spomedzi všetkých, ktoré tvoria scénu.

Podľa fyzickej podstaty sa znaky delia na globálne a lokálne. Globálna funkcia obrázky je funkcia, ktorú možno vypočítať pre akýkoľvek obrázok objektu.

Miestne značky používa sa menej; charakterizujú nie celý obraz, ale len jeho časť. Patria sem uhol medzi dvoma obrysovými čiarami, počet a parametre otvorov v obraze objektu atď.

Rozpoznávanie obrázkov

Uznanie je proces, pri ktorom sa na základe súboru znakov určitého obrazu predmetu určuje jeho príslušnosť k určitej triede.

Rozpoznávanie implementuje funkciu vizuálnej analýzy obrazu.

Všetky metódy rozpoznávania možno bežne rozdeliť do dvoch skupín: teoretické a štrukturálne. Najbežnejšie metódy teoretického rozpoznávania využívajú princípy teórie rozhodovania.

Nie je možné určiť skutočnú hodnotu vlastností objektu, pretože hodnoty sa pri každom meraní líšia. Preto je úloha rozpoznávania položená nasledovne: určiť pravdepodobnosť, že objekt patrí do danej triedy.

Jedna z najzaujímavejších oblastí rozpoznávania vzorov vo VS súvisí s vývojom algoritmov rozpoznávania tváre. Rozpoznávací (overovací) algoritmus je blízky registračnému algoritmu. Prvky extrahované z aktuálneho obrázka sa kombinujú do vektora prvkov, ktorého komponenty sa porovnávajú so zodpovedajúcimi komponentmi všetkých vektorov obsiahnutých v databáze.