Vo všeobecnosti možno rozlíšiť tri spôsoby rozpoznávania vzorov: Metóda enumerácie. V tomto prípade sa vykoná porovnanie s databázou, kde sú pre každý typ objektu uvedené všetky možné úpravy zobrazenia. Napríklad pre optické rozpoznávanie obrazu môžete použiť metódu enumerácie typu objektu v rôznych uhloch, mierkach, posunoch, deformáciách atď. Pri písmenách musíte prechádzať písmom, vlastnosťami písma atď. -známe vzory (napríklad slovo vyslovené viacerými ľuďmi).

Druhým prístupom je hlbšia analýza charakteristík obrazu. V prípade optického rozpoznávania to môže byť definícia rôznych geometrických charakteristík. Vzorka zvuku je v tomto prípade podrobená frekvenčnej, amplitúdovej analýze atď.

Ďalšou metódou je použitie umelých neurónových sietí (ANN). Táto metóda vyžaduje buď veľké množstvo príkladov úlohy rozpoznávania počas tréningu, alebo špeciálnu štruktúru neurónovej siete, ktorá zohľadňuje špecifiká tejto úlohy. Vyznačuje sa však vyššou účinnosťou a produktivitou.

4. História rozpoznávania vzorov

Pozrime sa stručne na matematický formalizmus rozpoznávania vzorov. Objekt pri rozpoznávaní vzorov je opísaný súborom základných charakteristík (vlastnosti, vlastnosti). Hlavné charakteristiky môžu byť rôzneho charakteru: môžu byť prevzaté z usporiadanej množiny typu reálnej čiary alebo z diskrétnej množiny (ktorá však môže byť vybavená aj štruktúrou). Toto chápanie objektu je v súlade s potrebou praktických aplikácií rozpoznávania vzorov, ako aj s naším chápaním mechanizmu ľudského vnímania objektu. Skutočne veríme, že keď človek pozoruje (meria) objekt, informácie o ňom prichádzajú cez konečný počet senzorov (analyzovaných kanálov) do mozgu a každý senzor môže byť spojený s príslušnou charakteristikou objektu. Okrem znakov, ktoré zodpovedajú našim meraniam objektu, existuje aj vybraný znak, alebo skupina znakov, ktoré nazývame klasifikačné znaky a zistiť ich hodnoty pre daný vektor X je úloha, ktorá je prirodzená a systémy umelého rozpoznávania.

Je jasné, že na stanovenie hodnôt týchto vlastností je potrebné mať informácie o tom, ako známe vlastnosti súvisia s klasifikačnými. Informácie o tomto vzťahu sú uvedené vo forme precedensov, to znamená súboru popisov objektov so známymi hodnotami klasifikačných znakov. A podľa týchto precedensných informácií je potrebné vybudovať rozhodovacie pravidlo, ktoré určí svojvoľný popis predmetu hodnoty jeho klasifikačných znakov.

Toto chápanie problému rozpoznávania vzorov je vo vede zavedené od 50. rokov minulého storočia. A potom sa zistilo, že takáto produkcia nie je vôbec nová. Takejto formulácii čelili a už existovali osvedčené metódy štatistickej analýzy údajov, ktoré sa aktívne využívali pri mnohých praktických úlohách, ako je napríklad technická diagnostika. Preto prvé kroky rozpoznávania vzorov prešli pod znakom štatistického prístupu, ktorý diktoval hlavný problém.

Štatistický prístup je založený na myšlienke, že počiatočný priestor objektov je pravdepodobnostný priestor a znaky (charakteristiky) objektov sú na ňom dané náhodné premenné. Úlohou dátového vedca bolo potom z niektorých úvah predložiť štatistickú hypotézu o rozdelení znakov, alebo skôr o závislosti klasifikačných znakov od ostatných. Štatistická hypotéza bola spravidla parametricky špecifikovaná množina funkcií distribúcie funkcií. Typickou a klasickou štatistickou hypotézou je hypotéza normality tohto rozdelenia (takýchto hypotéz je v štatistike veľmi veľa). Po sformulovaní hypotézy ostávalo túto hypotézu otestovať na precedensných dátach. Táto kontrola spočívala vo výbere nejakého rozdelenia z pôvodne daného súboru rozdelení (parameter hypotézy rozdelenia) a posúdení spoľahlivosti (intervalu spoľahlivosti) tohto výberu. V skutočnosti bola táto distribučná funkcia odpoveďou na problém, len objekt nebol klasifikovaný jednoznačne, ale s určitou pravdepodobnosťou, že patrí do tried. Štatistici tiež vyvinuli asymptotické odôvodnenie takýchto metód. Takéto zdôvodnenia boli urobené podľa nasledujúcej schémy: bola stanovená určitá kvalitatívna funkcionalita výberu rozdelenia (interval spoľahlivosti) a ukázalo sa, že s nárastom počtu precedensov sa náš výber s pravdepodobnosťou smerujúcou k 1 stal správnym v r. zmysel tohto funkcionálu (interval spoľahlivosti má tendenciu k 0). Pri pohľade do budúcnosti môžeme povedať, že štatistický pohľad na problém rozpoznávania sa ukázal ako veľmi plodný nielen z hľadiska vyvinutých algoritmov (ktoré zahŕňajú metódy zhlukovej a diskriminačnej analýzy, neparametrickej regresie atď.), ale následne viedol aj Vapnik vytvoriť hlbokú štatistickú teóriu rozpoznávania .

Napriek tomu existuje silný argument v prospech skutočnosti, že problémy rozpoznávania vzorov sa neobmedzujú na štatistiku. Každý takýto problém možno v zásade posudzovať zo štatistického hľadiska a výsledky jeho riešenia možno štatisticky interpretovať. Na to je potrebné iba predpokladať, že priestor objektov problému je pravdepodobnostný. Ale z hľadiska inštrumentalizmu môže byť kritériom úspešnosti štatistickej interpretácie určitej metódy rozpoznávania len existencia opodstatnenia tejto metódy v jazyku štatistiky ako odvetvia matematiky. Odôvodnenie tu znamená vypracovanie základných požiadaviek na problém, ktoré zabezpečia úspech pri uplatňovaní tejto metódy. V súčasnosti sa však pre väčšinu metód rozpoznávania, vrátane tých, ktoré vznikli priamo v rámci štatistického prístupu, nenašli takéto uspokojivé zdôvodnenia. Okrem toho, v súčasnosti najčastejšie používané štatistické algoritmy, ako je Fisherov lineárny diskriminant, Parzenovo okno, EM algoritmus, najbližší susedia, nehovoriac o Bayesovských sieťach presvedčení, majú silne výraznú heuristickú povahu a môžu mať odlišné interpretácie od štatistických. A na záver k vyššie uvedenému treba dodať, že okrem asymptotického správania sa metód rozpoznávania, ktoré je hlavnou témou štatistiky, prax rozpoznávania vyvoláva otázky výpočtovej a štrukturálnej zložitosti metód, ktoré ďaleko presahujú samotný rámec teórie pravdepodobnosti.

Celkovo, v rozpore s ašpiráciami štatistikov považovať rozpoznávanie vzorov za časť štatistiky, do praxe a ideológie uznávania vstúpili úplne iné myšlienky. Jeden z nich bol spôsobený výskumom v oblasti vizuálneho rozpoznávania vzorov a je založený na nasledujúcej analógii.

Ako už bolo uvedené, v každodennom živote ľudia neustále riešia (často nevedome) problémy s rozpoznávaním rôznych situácií, sluchových a vizuálnych obrazov. Takáto schopnosť pre počítače je v najlepšom prípade otázkou budúcnosti. Z toho niektorí priekopníci rozpoznávania vzorov usúdili, že riešenie týchto problémov na počítači by malo vo všeobecnosti simulovať procesy ľudského myslenia. Najznámejším pokusom priblížiť problém z tejto strany bola slávna štúdia F. Rosenblatta o perceptrónoch.

V polovici 50-tych rokov sa zdalo, že neurofyziológovia pochopili fyzikálne princípy mozgu (v knihe „The New Mind of the King“ slávny britský teoretický fyzik R. Penrose zaujímavo spochybňuje model neurónovej siete mozgu, pričom podstatnú úlohu kvantových mechanických efektov v jeho fungovaní; aj keď tento model bol od začiatku spochybňovaný. Na základe týchto objavov F. Rosenblatt vyvinul model na učenie sa rozpoznávať vizuálne vzorce, ktorý nazval perceptrón. Rosenblattov perceptrón je nasledujúca funkcia (obr. 1):

Obr. 1. Schéma perceptrónu

Na vstupe prijíma perceptrón objektový vektor, ktorý bol v dielach Rosenblatta binárnym vektorom, ktorý ukazuje, ktorý z pixelov obrazovky je zatemnený obrazom a ktorý nie. Ďalej je každý zo znakov privádzaný na vstup neurónu, ktorého pôsobením je jednoduché násobenie určitou hmotnosťou neurónu. Výsledky sa privádzajú do posledného neurónu, ktorý ich sčítava a porovnáva celkové množstvo s určitým prahom. V závislosti od výsledkov porovnania sa vstupný objekt X rozpozná ako potrebný alebo nie. Potom bolo úlohou učenia sa rozpoznávania vzorov vybrať váhy neurónov a prahovú hodnotu tak, aby perceptrón dával správne odpovede na predchádzajúce vizuálne obrázky. Rosenblatt veril, že výsledná funkcia bude dobrá pri rozpoznávaní požadovaného vizuálneho obrazu, aj keď vstupný objekt nepatrí medzi precedensy. Z bionických úvah prišiel aj na metódu výberu váh a prah, nad ktorou sa nebudeme zdržiavať. Povedzme, že jeho prístup bol úspešný v mnohých problémoch s rozpoznávaním a dal podnet na celý rad výskumov algoritmov učenia založených na neurónových sieťach, ktorých špeciálnym prípadom je perceptrón.

Ďalej boli vynájdené rôzne zovšeobecnenia perceptrónu, funkcia neurónov bola komplikovaná: teraz neuróny mohli nielen násobiť vstupné čísla alebo ich sčítať a porovnávať výsledok s prahmi, ale aplikovať na ne zložitejšie funkcie. Obrázok 2 ukazuje jednu z týchto komplikácií neurónov:

Ryža. 2 Schéma neurónovej siete.

Okrem toho by topológia neurónovej siete mohla byť oveľa komplikovanejšia ako tá, ktorú zvažoval Rosenblatt, napríklad toto:

Ryža. 3. Schéma Rosenblattovej neurónovej siete.

Komplikácie viedli k zvýšeniu počtu nastaviteľných parametrov počas tréningu, no zároveň k zvýšeniu schopnosti naladiť sa na veľmi zložité vzory. Výskum v tejto oblasti teraz prebieha v dvoch úzko súvisiacich oblastiach – skúmajú sa rôzne topológie sietí a rôzne metódy ladenia.

Neurónové siete sú v súčasnosti nielen nástrojom na riešenie problémov s rozpoznávaním vzorov, ale využívajú sa aj pri výskume asociatívnej pamäte a kompresie obrazu. Hoci sa táto línia výskumu výrazne prekrýva s problémami rozpoznávania vzorov, ide o samostatnú časť kybernetiky. Pre rozpoznávača v súčasnosti nie sú neurónové siete ničím iným ako veľmi špecifickou, parametricky definovanou množinou zobrazení, ktorá v tomto zmysle nemá žiadne významné výhody oproti mnohým iným podobným modelom učenia, ktoré budú stručne uvedené nižšie.

V súvislosti s týmto hodnotením úlohy neurónových sietí pre správne rozpoznávanie (teda nie pre bioniku, pre ktorú majú teraz prvoradý význam), by som rád poznamenal nasledovné: neurónové siete sú mimoriadne zložitým objektom pre matematické analýzy nám pri ich správnom použití umožňujú nájsť v dátach veľmi netriviálne zákony. Ich náročnosť analýzy sa vo všeobecnosti vysvetľuje ich zložitou štruktúrou a v dôsledku toho prakticky nevyčerpateľnými možnosťami zovšeobecnenia širokej škály zákonitostí. Ale tieto výhody, ako sa často stáva, sú zdrojom potenciálnych chýb, možnosťou preškolenia. Ako bude diskutované neskôr, takýto dvojitý pohľad na vyhliadky akéhokoľvek modelu učenia je jedným z princípov strojového učenia.

Ďalším populárnym smerom v rozpoznávaní sú logické pravidlá a rozhodovacie stromy. V porovnaní s vyššie uvedenými metódami rozpoznávania tieto metódy najaktívnejšie využívajú myšlienku vyjadrenia našich vedomostí o predmetnej oblasti vo forme pravdepodobne najprirodzenejších (na vedomej úrovni) štruktúr - logických pravidiel. Elementárne logické pravidlo znamená výrok typu „ak sú nezaradené znaky v pomere X, potom klasifikované sú v pomere Y“. Príklad takéhoto pravidla v lekárskej diagnostike je nasledujúci: ak je vek pacienta starší ako 60 rokov a predtým mal srdcový infarkt, potom operáciu nevykonávajte - riziko negatívneho výsledku je vysoké.

Na hľadanie logických pravidiel v dátach sú potrebné 2 veci: určiť mieru „informatívnosti“ pravidla a priestor pravidiel. A úloha nájsť pravidlá sa potom zmení na úlohu úplného alebo čiastočného vymenovania v priestore pravidiel s cieľom nájsť z nich čo najinformatívnejšie. Definíciu informatívnosti možno zaviesť rôznymi spôsobmi a nebudeme sa tým zaoberať, keďže ide tiež o niektorý parameter modelu. Vyhľadávací priestor je definovaný štandardným spôsobom.

Po nájdení dostatočne informatívnych pravidiel nastáva fáza „skladania“ pravidiel do výsledného klasifikátora. Bez toho, aby sme do hĺbky rozoberali problémy, ktoré tu vznikajú (a je ich značné množstvo), uvádzame 2 hlavné metódy „montáže“. Prvým typom je lineárny zoznam. Druhým typom je vážené hlasovanie, kedy je každému pravidlu priradená určitá váha a objekt je klasifikátorom priradený triede, za ktorú hlasovalo najviac pravidiel.

V skutočnosti sa fáza vytvárania pravidiel a fáza „zhromažďovania“ vykonávajú spoločne a pri zostavovaní váženého hlasovania alebo zoznamu sa znova a znova vyvoláva vyhľadávanie pravidiel o častiach údajov o prípade, aby sa zabezpečilo lepšie prispôsobenie údajov a model.

Iteračná metóda. Pri tejto metóde sa robí porovnanie s určitou databázou, kde pre každý z objektov existujú rôzne možnosti úpravy zobrazenia. Napríklad na optické rozpoznávanie obrazu môžete použiť metódu iterácie v rôznych uhloch alebo mierkach, posunoch, deformáciách atď. V prípade písmen môžete opakovať písmo alebo jeho vlastnosti. V prípade rozpoznávania zvukových vzorov existuje porovnanie s niektorými známymi vzormi (slovo, ktoré hovorí veľa ľudí). Ďalej sa vykonáva hlbšia analýza charakteristík obrazu. V prípade optického rozpoznávania to môže byť definícia geometrických charakteristík. Vzorka zvuku je v tomto prípade podrobená frekvenčnej a amplitúdovej analýze.

Ďalšia metóda je použitie umelých neurónových sietí(INS). Vyžaduje si to buď obrovské množstvo príkladov úlohy rozpoznávania, alebo špeciálnu štruktúru neurónovej siete, ktorá zohľadňuje špecifiká tejto úlohy. Táto metóda sa však vyznačuje vysokou účinnosťou a produktivitou.

Metódy založené na odhadoch distribučných hustôt hodnôt znakov. Vypožičané z klasickej teórie štatistického rozhodovania, v ktorej sa predmety skúmania považujú za realizácie viacrozmernej náhodnej premennej distribuovanej v priestore znakov podľa nejakého zákona. Sú založené na Bayesovej schéme rozhodovania, ktorá sa odvoláva na počiatočné pravdepodobnosti objektov patriacich do určitej triedy a hustoty distribúcie podmienených prvkov.

Skupina metód založených na odhade distribučných hustôt hodnôt znakov priamo súvisí s metódami diskriminačnej analýzy. Bayesovský prístup k rozhodovaniu je jednou z najrozvinutejších parametrických metód v modernej štatistike, pre ktorú sa analytické vyjadrenie distribučného zákona (normálny zákon) považuje za známe a len malý počet parametrov (stredné vektory a kovariančné matice ) je potrebné odhadnúť. Za hlavné ťažkosti pri aplikácii tejto metódy sa považuje potreba zapamätať si celý tréningový set na výpočet odhadov hustoty a vysoká citlivosť na tréningový set.

Metódy založené na predpokladoch o triede rozhodovacích funkcií. V tejto skupine sa typ rozhodovacej funkcie považuje za známy a je daná jej kvalitatívna funkcionalita. Na základe tohto funkcionálu sa z tréningovej sekvencie zistí optimálna aproximácia k rozhodovacej funkcii. Funkcionalita kvality rozhodovacieho pravidla je zvyčajne spojená s chybou. Hlavnou výhodou metódy je prehľadnosť matematickej formulácie rozpoznávacieho problému. Možnosť získavania nových poznatkov o povahe objektu, najmä poznatkov o mechanizmoch interakcie atribútov, je tu zásadne obmedzená danou štruktúrou interakcie, fixovanou vo zvolenej forme rozhodovacích funkcií.

Metóda porovnávania prototypov. Ide o najjednoduchšiu metódu rozšíreného rozpoznávania v praxi. Platí, keď sú rozpoznateľné triedy zobrazené ako kompaktné geometrické triedy. Potom sa ako prototypový bod vyberie stred geometrického zoskupenia (alebo objekt najbližšie k stredu).

Na klasifikáciu neurčitého objektu sa nájde prototyp, ktorý je mu najbližšie, a objekt patrí do rovnakej triedy ako on. Je zrejmé, že touto metódou sa nevytvárajú žiadne zovšeobecnené obrazy. Ako meradlo možno použiť rôzne typy vzdialeností.

Metóda k najbližších susedov. Metóda spočíva v tom, že pri klasifikácii neznámeho objektu sa nájde daný počet (k) geometricky najbližšieho priestorového priestoru ďalších najbližších susedov s už známou príslušnosťou do triedy. Rozhodnutie o priradení neznámeho objektu sa robí analýzou informácií o jeho najbližších susedoch. Potreba znížiť počet objektov v trénovacej vzorke (diagnostické precedensy) je nevýhodou tejto metódy, pretože to znižuje reprezentatívnosť trénovacej vzorky.

Na základe skutočnosti, že rôzne rozpoznávacie algoritmy sa správajú odlišne na tej istej vzorke, vyvstáva otázka syntetického rozhodovacieho pravidla, ktoré by využívalo silné stránky všetkých algoritmov. Na tento účel existuje syntetická metóda alebo súbory rozhodovacích pravidiel, ktoré kombinujú najpozitívnejšie aspekty každej z metód.

Na záver prehľadu metód rozpoznávania uvádzame podstatu vyššie uvedeného v súhrnnej tabuľke a pridávame niektoré ďalšie metódy používané v praxi.

Tabuľka 1. Klasifikačná tabuľka metód rozpoznávania, porovnanie oblastí ich použitia a obmedzení

Klasifikácia metód rozpoznávania	Oblasť použitia	Obmedzenia (nevýhody)
Intenzívne metódy rozpoznávania	Metódy založené na odhadoch hustoty	Problémy so známou distribúciou (normálna), potreba zbierať veľké štatistiky	Potreba vyčísliť celý tréningový súbor pri rozpoznávaní, vysoká citlivosť na nereprezentatívnosť tréningového súboru a artefaktov
Metódy založené na predpokladoch	Triedy by mali byť dobre oddeliteľné	Forma rozhodovacej funkcie musí byť známa vopred. Nemožnosť brať do úvahy nové poznatky o koreláciách medzi znakmi
Booleovské metódy	Problémy malých rozmerov	Pri výbere logických rozhodovacích pravidiel je potrebný úplný zoznam. Vysoká pracovná náročnosť
Lingvistické metódy		Úloha určenia gramatiky pre určitú množinu výrokov (popisov objektov) je ťažko formalizovateľná. Nevyriešené teoretické problémy
Rozširujúce metódy rozpoznávania	Metóda porovnávania prototypov	Problémy malého rozmeru priestoru prvkov	Vysoká závislosť výsledkov klasifikácie od metriky. Neznáma optimálna metrika
k metóda najbližšieho suseda		Vysoká závislosť výsledkov klasifikácie od metriky. Potreba úplného vyčíslenia tréningovej vzorky počas rozpoznávania. Výpočtová zložitosť
Algoritmy výpočtu známok (ABO)	Problémy malého rozmeru z hľadiska počtu tried a vlastností	Závislosť výsledkov klasifikácie na metrike. Potreba úplného vyčíslenia tréningovej vzorky počas rozpoznávania. Vysoká technická náročnosť metódy
Pravidlá kolektívneho rozhodovania (CRC) sú syntetickou metódou.	Problémy malého rozmeru z hľadiska počtu tried a vlastností	Veľmi vysoká technická náročnosť metódy, nevyriešené množstvo teoretických problémov ako pri určovaní oblastí kompetencie jednotlivých metód, tak aj v samotných metódach.

Nedeľa, 29. marec 2015

V súčasnosti existuje veľa úloh, pri ktorých je potrebné urobiť nejaké rozhodnutie v závislosti od prítomnosti objektu na obrázku alebo ho klasifikovať. Schopnosť „rozpoznať“ sa považuje za hlavnú vlastnosť biologických bytostí, zatiaľ čo počítačové systémy túto vlastnosť úplne nevlastnia.

Zvážte všeobecné prvky klasifikačného modelu.

Trieda- súbor predmetov, ktoré majú spoločné vlastnosti. Pre objekty rovnakej triedy sa predpokladá prítomnosť „podobnosti“. Pre úlohu rozpoznávania je možné definovať ľubovoľný počet tried, viac ako 1. Počet tried je označený číslom S. Každá trieda má svoj vlastný identifikačný štítok triedy.

Klasifikácia- proces priraďovania označení tried k objektom, podľa nejakého popisu vlastností týchto objektov. Klasifikátor je zariadenie, ktoré prijíma množinu vlastností objektu ako vstup a ako výsledok vracia označenie triedy.

Overenie- proces porovnávania inštancie objektu s jedným objektovým modelom alebo popisom triedy.

Pod spôsobom názov oblasti budeme chápať v priestore atribútov, v ktorom sú zobrazené mnohé predmety či javy hmotného sveta. znamenie- kvantitatívny popis konkrétnej vlastnosti skúmaného objektu alebo javu.

priestor funkcií toto je N-rozmerný priestor definovaný pre danú úlohu rozpoznávania, kde N je pevný počet meraných prvkov pre ľubovoľné objekty. Vektor z priestoru znakov x zodpovedajúci objektu rozpoznávacieho problému je N-rozmerný vektor so zložkami (x_1,x_2,…,x_N), čo sú hodnoty znakov pre daný objekt.

Inými slovami, rozpoznávanie vzorov možno definovať ako priradenie počiatočných údajov k určitej triede extrahovaním základných znakov alebo vlastností, ktoré charakterizujú tieto údaje, zo všeobecného množstva irelevantných detailov.

Príklady klasifikačných problémov sú:

• rozpoznávanie znakov;
• rozpoznávanie reči;
• stanovenie lekárskej diagnózy;
• predpoveď počasia;
• rozpoznávanie tváre
• triedenie dokumentov a pod.

Zdrojovým materiálom je najčastejšie obraz prijatý z fotoaparátu. Úlohu možno formulovať ako získanie vektorov znakov pre každú triedu v uvažovanom obrázku. Proces možno považovať za proces kódovania, ktorý spočíva v priradení hodnoty každému prvku z priestoru prvkov pre každú triedu.

Ak vezmeme do úvahy 2 triedy objektov: dospelých a detí. Ako vlastnosti si môžete vybrať výšku a hmotnosť. Ako vyplýva z obrázku, tieto dve triedy tvoria dve nepretínajúce sa množiny, čo možno vysvetliť zvolenými znakmi. Nie vždy je však možné zvoliť správne namerané parametre ako znaky tried. Zvolené parametre napríklad nie sú vhodné na vytváranie neprekrývajúcich sa tried futbalistov a basketbalistov.

Druhou úlohou rozpoznávania je výber charakteristických znakov alebo vlastností z pôvodných obrázkov. Túto úlohu možno pripísať predbežnému spracovaniu. Ak vezmeme do úvahy úlohu rozpoznávania reči, môžeme rozlíšiť také znaky, ako sú samohlásky a spoluhlásky. Atribút musí byť charakteristickou vlastnosťou konkrétnej triedy, pričom musí byť pre túto triedu spoločný. Znaky, ktoré charakterizujú rozdiely medzi - medzitriednymi znakmi. Funkcie spoločné pre všetky triedy nenesú užitočné informácie a nepovažujú sa za vlastnosti v probléme rozpoznávania. Výber vlastností je jednou z dôležitých úloh spojených s konštrukciou rozpoznávacieho systému.

Po určení znakov je potrebné určiť optimálny rozhodovací postup pre klasifikáciu. Zvážte systém rozpoznávania vzorov navrhnutý tak, aby rozpoznával rôzne triedy M, označované ako m_1,m_2,…,m 3. Potom môžeme predpokladať, že priestor obrazu pozostáva z M oblastí, z ktorých každá obsahuje body zodpovedajúce obrázku z jednej triedy. Potom možno problém rozpoznávania považovať za konštrukciu hraníc oddeľujúcich M triedy na základe akceptovaných meracích vektorov.

Riešenie problému predspracovania obrazu, extrakcie znakov a problém získania optimálneho riešenia a klasifikácie je zvyčajne spojený s potrebou vyhodnocovania množstva parametrov. To vedie k problému odhadu parametrov. Okrem toho je zrejmé, že extrakcia funkcií môže využívať ďalšie informácie založené na povahe tried.

Porovnanie objektov je možné vykonať na základe ich reprezentácie vo forme meracích vektorov. Je vhodné reprezentovať namerané údaje ako reálne čísla. Potom možno podobnosť vektorov príznakov dvoch objektov opísať pomocou euklidovskej vzdialenosti.

kde d je rozmer charakteristického vektora.

Existujú 3 skupiny metód rozpoznávania vzorov:

• Ukážkové porovnanie. Táto skupina zahŕňa klasifikáciu podľa najbližšieho priemeru, klasifikáciu podľa vzdialenosti k najbližšiemu susedovi. Do porovnávacej skupiny vzoriek možno zahrnúť aj metódy štrukturálneho rozpoznávania.
• Štatistické metódy. Ako už názov napovedá, štatistické metódy využívajú niektoré štatistické informácie pri riešení problému rozpoznávania. Metóda určuje príslušnosť objektu ku konkrétnej triede na základe pravdepodobnosti. V niektorých prípadoch ide o určenie aposteriórnej pravdepodobnosti objektu patriaceho do určitej triedy za predpokladu, že vlastnosti tohto objektu nadobudli primeranú hodnotu. hodnoty. Príkladom je metóda Bayesovho rozhodovacieho pravidla.
• Neurálne siete. Samostatná trieda metód rozpoznávania. Charakteristickým znakom od ostatných je schopnosť učiť sa.

Klasifikácia podľa najbližšieho priemeru

V klasickom prístupe rozpoznávania vzorov, v ktorom je neznámy objekt na klasifikáciu reprezentovaný ako vektor elementárnych znakov. Systém rozpoznávania založený na vlastnostiach možno vyvinúť rôznymi spôsobmi. Tieto vektory môžu byť systému známe vopred ako výsledok školenia alebo predpovedané v reálnom čase na základe niektorých modelov.

Jednoduchý klasifikačný algoritmus pozostáva zo zoskupenia referenčných údajov triedy pomocou vektora očakávania triedy (priemer).

kde x(i,j) je j-tý referenčný znak triedy i, n_j je počet referenčných vektorov triedy i.

Potom bude neznámy objekt patriť do triedy i, ak je oveľa bližšie k očakávanému vektoru triedy i ako k očakávaným vektorom iných tried. Táto metóda je vhodná pre problémy, v ktorých sú body každej triedy umiestnené kompaktne a ďaleko od bodov iných tried.

Ťažkosti nastanú, ak majú triedy o niečo zložitejšiu štruktúru, napríklad ako na obrázku. V tomto prípade je trieda 2 rozdelená na dve neprekrývajúce sa časti, ktoré sú zle opísané jednou priemernou hodnotou. Trieda 3 je tiež príliš pretiahnutá, vzorky 3. triedy s veľkými hodnotami súradníc x_2 sú bližšie k priemernej hodnote 1. triedy ako 3. triedy.

Opísaný problém možno v niektorých prípadoch vyriešiť zmenou výpočtu vzdialenosti.

Zohľadníme charakteristiku „rozptylu“ hodnôt triedy - σ_i pozdĺž každého smeru súradníc i. Smerodajná odchýlka sa rovná druhej odmocnine rozptylu. Škálovaná euklidovská vzdialenosť medzi vektorom x a vektorom očakávania x_c je

Tento vzorec vzdialenosti zníži počet klasifikačných chýb, ale v skutočnosti väčšina problémov nemôže byť reprezentovaná takouto jednoduchou triedou.

Klasifikácia podľa vzdialenosti k najbližšiemu susedovi

Iný prístup ku klasifikácii je priradiť neznámy znakový vektor x triede, ktorej je tento vektor najbližšie k samostatnej vzorke. Toto pravidlo sa nazýva pravidlo najbližšieho suseda. Klasifikácia najbližšieho suseda môže byť efektívnejšia, aj keď sú triedy zložité alebo keď sa triedy prekrývajú.

Tento prístup nevyžaduje predpoklady o distribučných modeloch charakteristických vektorov v priestore. Algoritmus používa iba informácie o známych referenčných vzorkách. Metóda riešenia je založená na výpočte vzdialenosti x ku každej vzorke v databáze a nájdení minimálnej vzdialenosti. Výhody tohto prístupu sú zrejmé:

• do databázy môžete kedykoľvek pridať nové vzorky;
• stromové a mriežkové dátové štruktúry znižujú počet vypočítaných vzdialeností.

Navyše, riešenie bude lepšie, ak si v databáze pozriete nie jedného najbližšieho suseda, ale k. Potom pre k > 1 poskytuje najlepšiu vzorku rozloženia vektorov v d-rozmernom priestore. Efektívne využitie hodnôt k však závisí od toho, či je v každej oblasti priestoru dostatok. Ak existuje viac ako dve triedy, potom je ťažšie urobiť správne rozhodnutie.

Literatúra

• M. Castrillon, . O. Deniz, . D. Hernández a J. Lorenzo, „Porovnanie detektorov tváre a tvárových prvkov na základe všeobecného rámca detekcie objektov Viola-Jones“, International Journal of Computer Vision, č.22, str. 481-494, 2011.
• Y.-Q. Wang, "Analýza algoritmu detekcie tváre Viola-Jones", IPOL Journal, 2013.
• L. Shapiro a D. Stockman, Počítačové videnie, Binom. Knowledge Lab, 2006.
• Z. N. G., Metódy rozpoznávania a ich aplikácia, Sovietsky rozhlas, 1972.
• J. Tu, R. Gonzalez, Matematické princípy rozpoznávania vzorov, Moskva: „Mir“ Moskva, 1974.
• Khan, H. Abdullah a M. Shamian Bin Zainal, "Efektívny algoritmus detekcie očí a úst pomocou kombinácie detekcie pixelov violy Jonesovej a farby pleti" International Journal of Engineering and Applied Sciences, č. 3 č. 4, 2013.
• V. Gaede a O. Gunther, "Multidimenzionální prístupové metódy," ACM Computing Surveys, str. 170-231, 1998.

• tutoriál

Dlho som chcel napísať všeobecný článok obsahujúci úplné základy rozpoznávania obrazu, akýsi sprievodca základnými metódami, ktorý by povedal, kedy ich použiť, aké úlohy riešia, čo sa dá robiť večer na kolene a na čo je lepšie nemyslieť bez toho, aby sme mali tím ľudí v 20.

O optickom rozpoznávaní píšem nejaké články už dlho, preto mi párkrát do mesiaca píšu rôzni ľudia s otázkami na túto tému. Niekedy máte pocit, že s nimi žijete v iných svetoch. Na jednej strane chápete, že osoba je s najväčšou pravdepodobnosťou profesionálom v príbuznej téme, ale vie veľmi málo o metódach optického rozpoznávania. A najnepríjemnejšie na tom je, že sa snaží aplikovať metódu z blízkej oblasti poznania, ktorá je síce logická, no v Rozpoznávaní obrázkov úplne nefunguje, no nerozumie tomu a veľmi sa urazí, ak mu začne rozprávať niečo z toho. veľmi základy. A vzhľadom na to, že rozprávanie od základov je veľa času, ktorý často nie je, je to ešte smutnejšie.

Tento článok je koncipovaný tak, aby si človek, ktorý sa nikdy nezaoberal metódami rozpoznávania obrazu, v priebehu 10-15 minút vytvoril v hlave určitý základný obraz sveta zodpovedajúci téme a pochopil, akým smerom by sa mal uberať. Mnohé z tu opísaných metód sú použiteľné na radarové a audio spracovanie.
Začnem niekoľkými zásadami, ktoré vždy začneme hovoriť potenciálnemu zákazníkovi alebo osobe, ktorá chce začať s optickým rozpoznávaním:

• Pri riešení problému vždy choďte od najjednoduchšieho. Je oveľa jednoduchšie zavesiť oranžový štítok na osobu, ako nasledovať osobu a zvýrazňovať ju v kaskádach. Je oveľa jednoduchšie vziať kameru s vyšším rozlíšením, ako vyvinúť algoritmus s vysokým rozlíšením.
• Prísne vyjadrenie problému v metódach optického rozpoznávania je rádovo dôležitejšie ako v problémoch systémového programovania: jedno slovo navyše v TK môže pridať 50 % práce.
• V problémoch s rozpoznávaním neexistujú univerzálne riešenia. Nemôžete vytvoriť algoritmus, ktorý jednoducho „rozpozná akýkoľvek nápis“. Nápis na ulici a list textu sú zásadne odlišné predmety. Pravdepodobne je možné vytvoriť všeobecný algoritmus (dobrý príklad od spoločnosti Google), ale bude to vyžadovať veľa práce od veľkého tímu a bude pozostávať z desiatok rôznych podprogramov.
• OpenCV je biblia, ktorá má veľa metód a pomocou ktorej môžete vyriešiť 50% objemu takmer akéhokoľvek problému, ale OpenCV je len malá časť toho, čo sa dá urobiť v skutočnosti. V jednej štúdii bolo v záveroch napísané: "Problém nie je vyriešený metódami OpenCV, preto je neriešiteľný." Snažte sa tomu vyhnúť, nebuďte leniví a triezvo vyhodnoťte aktuálnu úlohu zakaždým od začiatku, bez použitia OpenCV šablón.

Je veľmi ťažké poskytnúť nejakú univerzálnu radu alebo povedať, ako vytvoriť nejakú štruktúru, okolo ktorej môžete postaviť riešenie ľubovoľných problémov s počítačovým videním. Účelom tohto článku je štruktúrovať, čo možno použiť. Pokúsim sa rozdeliť existujúce metódy do troch skupín. Prvou skupinou je predfiltrovanie a príprava obrazu. Druhou skupinou je logické spracovanie výsledkov filtrovania. Treťou skupinou sú rozhodovacie algoritmy založené na logickom spracovaní. Hranice medzi skupinami sú veľmi ľubovoľné. Na vyriešenie problému nie je zďaleka vždy potrebné použiť metódy zo všetkých skupín, niekedy stačia dve a niekedy dokonca jedna.

Zoznam tu uvedených metód nie je úplný. Navrhujem pridať do komentárov kritické metódy, ktoré som nenapísal a priradiť ku každému 2-3 sprievodné slová.

Časť 1. Filtrovanie

Do tejto skupiny som umiestnil metódy, ktoré vám umožňujú vybrať oblasti záujmu na obrázkoch bez ich analýzy. Väčšina týchto metód aplikuje nejaký druh jednotnej transformácie na všetky body v obraze. Na úrovni filtrovania sa obraz neanalyzuje, ale body, ktoré sú filtrované, možno považovať za oblasti so špeciálnymi charakteristikami.

Prahová binarizácia, výber oblasti histogramu

Najjednoduchšou transformáciou je binarizácia obrazu prahom. Pre obrázky RGB a obrázky v odtieňoch sivej je prahovou hodnotou hodnota farby. Existujú ideálne problémy, v ktorých takáto transformácia postačuje. Predpokladajme, že chcete automaticky vyberať položky na bielom hárku papiera:




Voľba prahu, pri ktorom binarizácia prebieha, do značnej miery určuje samotný proces binarizácie. V tomto prípade bol obrázok binarizovaný priemernou farbou. Zvyčajne sa binarizácia vykonáva pomocou algoritmu, ktorý adaptívne vyberá prah. Takýmto algoritmom môže byť výber očakávania alebo režimu. A môžete si vybrať najväčší vrchol histogramu.

Binarizácia môže poskytnúť veľmi zaujímavé výsledky pri práci s histogramami, vrátane situácie, ak neuvažujeme o obrázku v RGB, ale v HSV. Napríklad segmentujte farby, ktoré vás zaujímajú. Na tomto princípe je možné postaviť ako detektor etikiet, tak aj detektor ľudskej kože.

Klasické filtrovanie: Fourier, LPF, HPF

Klasické metódy filtrovania z radaru a spracovania signálov možno úspešne použiť v rôznych úlohách rozpoznávania vzorov. Tradičnou metódou v radare, ktorá sa na snímkach v čistej forme takmer nikdy nepoužíva, je Fourierova transformácia (presnejšie FFT). Jednou z mála výnimiek, kde sa používa 1D Fourierova transformácia, je kompresia obrazu. Na analýzu obrazu zvyčajne nestačí jednorozmerná transformácia, musíte použiť dvojrozmernú transformáciu, ktorá je oveľa náročnejšia na zdroje.

Málokto to skutočne vypočíta, zvyčajne je oveľa rýchlejšie a jednoduchšie použiť konvolúciu záujmovej oblasti s hotovým filtrom zaostreným na vysoké (HPF) alebo nízke (LPF) frekvencie. Takáto metóda samozrejme neumožňuje analýzu spektra, ale pri konkrétnej úlohe spracovania videa zvyčajne nie je potrebná analýza, ale výsledok.


Najjednoduchšie príklady filtrov, ktoré zdôrazňujú nízke frekvencie (Gaussov filter) a vysoké frekvencie (Gaborov filter).
Pre každý bod obrázka sa vyberie okno a vynásobí sa filtrom rovnakej veľkosti. Výsledkom takejto konvolúcie je nová hodnota bodu. Pri implementácii LPF a HPF sa získajú obrázky tohto typu:

Vlnky

Čo ak však použijeme ľubovoľnú charakteristickú funkciu na konvolúciu so signálom? Potom sa to bude volať "Wavelet Transform". Táto definícia vlniek nie je správna, ale tradične v mnohých tímoch vlnková analýza predstavuje hľadanie ľubovoľného vzoru v obraze pomocou konvolúcie s modelom tohto vzoru. Vo vlnkovej analýze sa používa súbor klasických funkcií. Patria sem vlnka Haar, vlnka Morlet, vlnka mexického klobúka atď. Haarove primitívy, o ktorých bolo niekoľko mojich predchádzajúcich článkov ( , ), označujú takéto funkcie pre dvojrozmerný priestor.


Vyššie sú 4 príklady klasických vlniek. 3D vlnka Haar, vlnka 2D Meyer, vlnka Mexican Hat, vlnka Daubechies. Dobrým príkladom použitia rozšírenej interpretácie vlniek je problém nájdenia lesku v oku, pre ktorý je samotný lesk vlnkou:

Klasické vlnky sa zvyčajne používajú na , alebo na ich klasifikáciu (popíšeme nižšie).

Korelácia

Po takejto voľnej interpretácii vlniek z mojej strany stojí za zmienku ich skutočná korelácia. Pri filtrovaní obrázkov je to nepostrádateľný nástroj. Klasickou aplikáciou je korelácia video streamu na nájdenie posunov alebo optických tokov. Najjednoduchší detektor posunu je v istom zmysle aj rozdielovým korelátorom. Tam, kde obrázky nekorelujú, nastal pohyb.

Filtrovanie funkcií

Zaujímavou triedou filtrov sú filtrovacie funkcie. Ide o čisto matematické filtre, ktoré umožňujú odhaliť jednoduchú matematickú funkciu v obraze (priamka, parabola, kruh). Vytvorí sa kumulatívny obraz, v ktorom sa pre každý bod pôvodného obrazu nakreslí množina funkcií, ktoré ho generujú. Najklasickejšou transformáciou je Houghova transformácia pre čiary. Pri tejto transformácii sa pre každý bod (x;y) nakreslí množina bodov (a;b) priamky y=ax+b, pre ktoré platí rovnosť. Získajte krásne obrázky:


(prvé plus pre toho, kto prvý nájde na obrázku háčik a takúto definíciu a vysvetlí to, druhé plus pre toho, kto prvý povie, čo je tu zobrazené)
Houghova transformácia vám umožňuje nájsť ľubovoľné parametrizovateľné funkcie. Napríklad kruhy. K dispozícii je upravená transformácia, ktorá umožňuje vyhľadávať ľubovoľné . Táto transformácia sa matematikom strašne páči. Ale pri spracovaní obrázkov to, bohužiaľ, nie vždy funguje. Veľmi nízka rýchlosť, veľmi vysoká citlivosť na kvalitu binarizácie. Aj v ideálnych situáciách som si radšej vystačil s inými metódami.
Náprotivkom Houghovej transformácie pre čiary je Radonova transformácia. Vypočítava sa cez FFT, čo dáva výkonnostný zisk v situácii, keď je veľa bodov. Okrem toho sa dá použiť aj na nebinarizovaný obrázok.

Filtrovanie obrysov

Samostatnou triedou filtrov je okrajové a obrysové filtrovanie. Cesty sú veľmi užitočné, keď chceme prejsť od práce s obrázkom k práci s objektmi na tomto obrázku. Keď je objekt pomerne zložitý, ale dobre rozlíšený, potom často jediným spôsobom, ako s ním pracovať, je vybrať jeho obrysy. Existuje niekoľko algoritmov, ktoré riešia problém filtrovania obrysov:

Najčastejšie sa používa Kenny, ktorý funguje dobre a ktorého implementácia je v OpenCV (je tam aj Sobel, ale horšie hľadá kontúry).

Iné filtre

Vyššie sú filtre, ktorých úpravy pomáhajú vyriešiť 80-90% úloh. Ale okrem nich existujú vzácnejšie filtre používané v miestnych úlohách. Takýchto filtrov sú desiatky, nebudem ich všetky uvádzať. Zaujímavé sú iteračné filtre (napr. ), ako aj ridgeletové a krivkové transformácie, ktoré sú zliatinou klasickej vlnkovej filtrácie a analýzy v oblasti radónovej transformácie. Beamletová transformácia funguje nádherne na hranici vlnkovej transformácie a logickej analýzy, čo vám umožňuje zvýrazniť kontúry:

Ale tieto transformácie sú veľmi špecifické a prispôsobené pre zriedkavé úlohy.

Časť 2. Logické spracovanie výsledkov filtrovania

Filtrovanie poskytuje súbor údajov vhodných na spracovanie. Tieto údaje však často nemôžete len vziať a použiť bez ich spracovania. V tejto časti bude niekoľko klasických metód, ktoré umožňujú prejsť od obrázku k vlastnostiam objektov, prípadne k objektom samotným.

Morfológia

Prechodom od filtrovania k logike sú podľa mňa metódy matematickej morfológie ( , ). V skutočnosti ide o najjednoduchšie operácie zväčšovania a erodovania binárnych obrazov. Tieto metódy umožňujú odstrániť šum z binárneho obrazu zvýšením alebo znížením dostupných prvkov. Na základe matematickej morfológie existujú kontúrovacie algoritmy, ale zvyčajne používajú nejaký druh hybridných algoritmov alebo algoritmov v spojení.

analýza obrysov

V časti o filtrovaní už boli spomenuté algoritmy na získanie hraníc. Výsledné hranice sú celkom jednoducho prevedené na obrysy. Pri Cannyho algoritme sa to deje automaticky, pri iných algoritmoch je potrebná dodatočná binarizácia. Kontúru pre binárny algoritmus môžete získať napríklad pomocou algoritmu chrobáka.
Obrys je jedinečná charakteristika objektu. Často to umožňuje identifikovať objekt pozdĺž obrysu. Existuje výkonný matematický aparát, ktorý vám to umožňuje. Prístroj sa nazýva analýza obrysov ( , ).

Aby som bol úprimný, nikdy sa mi nepodarilo použiť analýzu kontúr v skutočných problémoch. Vyžadujú sa príliš ideálne podmienky. Buď tam nie je žiadna hranica, alebo je tam príliš veľa hluku. Ak však potrebujete niečo rozpoznať za ideálnych podmienok, potom je analýza obrysu skvelou voľbou. Funguje to veľmi rýchlo, krásna matematika a zrozumiteľná logika.

Singulárne body

Kľúčové body sú jedinečné charakteristiky objektu, ktoré umožňujú priradenie objektu k sebe samému alebo k podobným triedam objektov. Existujú desiatky spôsobov, ako vybrať takéto body. Niektoré metódy zvýrazňujú špeciálne body v susedných snímkach, niektoré po dlhom čase a pri zmene osvetlenia, niektoré umožňujú nájsť špeciálne body, ktoré tak zostanú, aj keď sa objekt otáča. Začnime metódami, ktoré nám umožňujú nájsť špeciálne body, ktoré nie sú také stabilné, ale sú rýchlo vypočítané, a potom pôjdeme so zvyšujúcou sa zložitosťou:
Prvá trieda. Singulárne body, ktoré sú stabilné niekoľko sekúnd. Takéto body sa používajú na vedenie objektu medzi susednými snímkami videa alebo na zbližovanie obrazov zo susedných kamier. Tieto body zahŕňajú lokálne maximá obrazu, rohy v obraze (najlepší z detektorov, možno Harisov detektor), body, v ktorých sa dosahujú maximá disperzie, určité gradienty atď.
Druhá trieda. Singulárne body, ktoré sú stabilné pri zmene osvetlenia a malých pohyboch objektu. Takéto body slúžia predovšetkým na trénovanie a následnú klasifikáciu typov objektov. Napríklad klasifikátor chodcov alebo klasifikátor tváre je produktom systému postaveného práve na takýchto bodoch. Niektoré z vyššie uvedených vlniek môžu byť základom pre takéto body. Napríklad primitívy Haar, vyhľadávanie odleskov, hľadanie ďalších špecifických funkcií. Medzi tieto body patria body nájdené metódou histogramov smerových gradientov (HOG).
Tretia trieda. stabilné body. Viem len o dvoch metódach, ktoré poskytujú úplnú stabilitu a o ich modifikáciách. Toto a . Umožňujú vám nájsť kľúčové body aj pri otáčaní obrázka. Výpočet takýchto bodov trvá dlhšie ako iné metódy, ale pomerne obmedzený čas. Bohužiaľ, tieto metódy sú patentované. Aj keď v Rusku nie je možné patentovať algoritmy, použite ich pre domáci trh.

Časť 3. Školenie

Tretia časť príbehu bude venovaná metódam, ktoré nepracujú priamo s obrazom, no umožňujú vám rozhodovať sa. V podstate ide o rôzne metódy strojového učenia a rozhodovania. Nedávno Yandyks písal na Habr na túto tému, je tam veľmi dobrý výber. Tu je v textovej verzii. Pre seriózne štúdium predmetu dôrazne odporúčam, aby ste si ich pozreli. Tu sa pokúsim identifikovať niekoľko základných metód používaných špeciálne pri rozpoznávaní vzorov.
V 80 % situácií je podstata učenia v probléme rozpoznávania nasledovná:
Existuje skúšobná vzorka, na ktorej je niekoľko tried objektov. Nech je to prítomnosť / neprítomnosť osoby na fotografii. Pre každý obrázok existuje súbor funkcií, ktoré boli zvýraznené nejakou vlastnosťou, či už je to Haar, HOG, SURF alebo nejaká vlnka. Učiaci sa algoritmus musí zostaviť taký model, podľa ktorého bude schopný analyzovať nový obrázok a rozhodnúť, ktorý z objektov je na obrázku.
Ako sa to robí? Každý z testovacích obrázkov je bod v priestore funkcií. Jeho súradnice predstavujú váhu každého prvku na obrázku. Nech sú naše znaky: „Prítomnosť očí“, „Prítomnosť nosa“, „Prítomnosť dvoch rúk“, „Prítomnosť uší“ atď. Všetky tieto znaky pridelíme detektorom, ktoré máme, ktoré sú trénované na častiach tela podobných ľudským. Pre človeka v takomto priestore bude správny bod . Pre opicu bodka pre koňa. Klasifikátor je trénovaný na vzorke príkladov. Nie všetky fotografie však ukazovali ruky, iné nemali oči a na tretej mala opica ľudský nos kvôli chybe klasifikátora. Trénovateľný ľudský klasifikátor automaticky rozdelí priestor prvkov takým spôsobom, aby povedal: ak prvý prvok leží v rozsahu 0,5 Účelom klasifikátora je v podstate nakresliť do priestoru znakov oblasti charakteristické pre objekty klasifikácie. Takto bude vyzerať postupná aproximácia k odpovedi pre jeden z klasifikátorov (AdaBoost) v dvojrozmernom priestore:


Existuje veľa klasifikátorov. Každý z nich funguje lepšie v niektorých svojich úlohách. Úloha výberu klasifikátora pre konkrétnu úlohu je do značnej miery umením. Tu je pár pekných obrázkov k téme.

Jednoduchý prípad, jednorozmerné oddelenie

Uveďme si príklad najjednoduchšieho prípadu klasifikácie, keď je priestor prvkov jednorozmerný a potrebujeme oddeliť 2 triedy. Situácia nastáva častejšie, ako by sa mohlo zdať: napríklad, keď potrebujete rozlíšiť dva signály alebo porovnať vzor so vzorkou. Povedzme, že máme tréningovú vzorku. V tomto prípade sa získa obrázok, kde os X bude mierou podobnosti a os Y bude počet udalostí s takouto mierou. Keď je požadovaný objekt podobný sebe, získa sa ľavý Gaussian. Keď nie podobné - správne. Hodnota X=0,4 oddeľuje vzorky, takže chybné rozhodnutie minimalizuje pravdepodobnosť akéhokoľvek nesprávneho rozhodnutia. Práve hľadanie takéhoto oddeľovača je úlohou klasifikácie.


Malá poznámka. Kritérium, ktoré minimalizuje chybu, nebude vždy optimálne. Nasledujúci graf je grafom skutočného systému rozpoznávania dúhovky. Pre takýto systém je kritérium zvolené tak, aby sa minimalizovala pravdepodobnosť falošného vstupu cudzinca do objektu. Takáto pravdepodobnosť sa nazýva „chyba prvého druhu“, „pravdepodobnosť falošného poplachu“, „falošne pozitívny“. V anglickej literatúre "False Access Rate".
) AdaBusta je jedným z najbežnejších klasifikátorov. Je na nej postavená napríklad Haarova kaskáda. Zvyčajne sa používa, keď je potrebná binárna klasifikácia, ale nič nebráni výučbe pre viac tried.
SVM ( , , , ) Jeden z najvýkonnejších klasifikátorov s mnohými implementáciami. V princípe na učebných úlohách, s ktorými som sa stretol, to fungovalo podobne ako adabusta. Považuje sa za pomerne rýchly, ale jeho tréning je náročnejší ako u Adabusty a vyžaduje si výber správneho jadra.

Existujú aj neurónové siete a regresia. Aby sme ich však stručne klasifikovali a ukázali, ako sa líšia, je potrebný oveľa väčší článok.
________________________________________________
Dúfam, že som bol schopný poskytnúť rýchly prehľad použitých metód bez toho, aby som sa ponoril do matematiky a popisu. Možno to niekomu pomôže. Aj keď je samozrejme článok neúplný a nie je tam ani slovo o práci so stereo obrazmi, ani o LSM s Kalmanovým filtrom, ani o adaptívnom bayesovskom prístupe.
Ak sa vám článok páči, pokúsim sa urobiť druhú časť s výberom príkladov, ako sa riešia existujúce problémy ImageRecognition.

A nakoniec

čo čítať?
1) Raz sa mi veľmi páčila kniha "Digitálne spracovanie obrazu" od B. Yana, ktorá je napísaná jednoducho a zrozumiteľne, no zároveň je v nej daná takmer všetka matematika. Dobré na oboznámenie sa s existujúcimi metódami.
2) Klasikou žánru je R Gonzalez, R. Woods „Digital Image Processing“. Z nejakého dôvodu to bolo pre mňa ťažšie ako to prvé. Oveľa menej matematiky, ale viac metód a obrázkov.
3) „Spracovanie a analýza obrazu v problémoch strojového videnia“ - napísané na základe kurzu vyučovaného na jednej z katedier PhysTech. Množstvo metód a ich podrobný popis. Ale podľa mňa má kniha dve veľké mínusy: kniha je silne zameraná na softvérový balík, ktorý je s ňou dodávaný, v knihe sa až príliš často popis jednoduchej metódy premení na matematickú džungľu, z ktorej je ťažké vyčítať štrukturálny diagram metódy. Ale autori vytvorili pohodlnú stránku, kde je prezentovaný takmer celý obsah - wiki.technicalvision.ru Pridať značky