Shoda šablon

Jste zde:Start „Průvodce strojovým viděním „Shoda šablon

Úvod

Shoda šablon je technika strojového vidění na vysoké úrovni, která identifikuje části obrazu, které odpovídají předem definované šabloně. Pokročilé algoritmy porovnávání šablon umožňují najít výskyty šablony bez ohledu na jejich orientaci a místní jas.

Techniky porovnávání šablon jsou flexibilní a relativně jednoduché na použití, což z nich činí jednu z nejoblíbenějších metod lokalizace objektů. Jejich použitelnost je omezena především dostupným výpočetním výkonem, protože identifikace velkých a složitých šablon může být časově náročná.

Koncept

Očekává se, že techniky porovnávání šablon budou řešit následující potřebu: za předpokladu referenčního obrazu objektu (obraz šablony) a obrazu, který má být kontrolován (vstupní obraz), chceme identifikovat všechna místa vstupního obrazu, na kterých se vyskytuje objekt z obrazu šablony. V závislosti na konkrétním problému můžeme (ale nemusíme) chtít identifikovat otočené nebo zmenšené výskyty.

Začneme ukázkou naivní metody Template Matching, která je pro reálné aplikace nedostatečná, ale ilustruje základní koncept, z něhož vycházejí skutečné algoritmy Template Matching. Poté si vysvětlíme, jak je tato metoda vylepšena a rozšířena v pokročilých rutinách Grayscale-based Matching a Edge-based Matching.

Naive Template Matching

Představte si, že budeme prohlížet obrázek zástrčky a naším cílem je najít její vývody. Máme k dispozici šablonový obrázek představující referenční objekt, který hledáme, a vstupní obrázek, který má být zkontrolován.

Šablonový obrázek	Vstupní obrázek

Samotné prohledávání provedeme poměrně jednoduchým způsobem – šablonu umístíme nad obrázek na všechna možná místa, a pokaždé vypočítáme nějakou číselnou míru podobnosti mezi šablonou a segmentem obrázku, se kterým se aktuálně překrývá. Nakonec určíme pozice, které dávají nejlepší míru podobnosti, jako pravděpodobné výskyty šablony.

Korelace obrazu

Jedním z dílčích problémů, které se vyskytují ve výše uvedené specifikaci, je výpočet míry podobnosti zarovnaného obrazu šablony a překrytého segmentu vstupního obrazu, což je ekvivalentní výpočtu míry podobnosti dvou obrazů stejných rozměrů. Jedná se o klasickou úlohu a číselná míra podobnosti obrazu se obvykle nazývá korelace obrazu.

Křížová korelace

Základní metodou výpočtu obrazové korelace je tzv. křížová korelace.korelace, která je v podstatě jednoduchým součtem párových násobků odpovídajících hodnot pixelů obrazů.

Ačkoli si můžeme všimnout, že hodnota korelace skutečně zdánlivě odráží podobnost porovnávaných obrazů, metoda křížové korelace zdaleka není robustní. Její hlavní nevýhodou je, že je zkreslena změnami globálního jasu snímků – zjasnění snímku může zvýšit jeho křížovou korelaci s jiným snímkem, i když druhý snímek není vůbec podobný.

Normalizovaná křížová korelace

Normalizovaná křížová korelace je vylepšená verze klasické křížové korelační metody, která oproti původní zavádí dvě vylepšení:

• Výsledky jsou invariantní vůči globálním změnám jasu, tj.tj. důsledné zjasnění nebo ztmavení obou obrazů nemá na výsledek žádný vliv (toho se dosáhne odečtením středního jasu obrazu od každé hodnoty pixelu).
• Konečná hodnota korelace je škálována podle rozsahu, takže NCC dvou stejných obrazů se rovná 1,0, zatímco NCC obrazu a jeho negace se rovná -1,0.

Šablona korelačního obrázku

Vraťme se k danému problému. Po zavedení normalizované křížové korelace – robustní míry podobnosti obrázků – jsme nyní schopni určit, jak dobře se šablona hodí do každé z možných pozic. Výsledky můžeme znázornit ve formě obrázku, kde jas každého pixelu představuje hodnotu NCC šablony umístěné nad tímto pixelem (černá barva představuje minimální korelaci -1,0, bílá barva představuje maximální korelaci 1,0).

.

Obraz šablony	Vstupní obraz	Obraz korelace šablony

Identifikace shod

V tomto okamžiku je třeba pouze rozhodnout, které body korelačního obrazu šablony jsou dostatečně dobré, aby mohly být považovány za skutečné shody. Obvykle identifikujeme jako shody polohy, které (současně) představují korelaci šablony:

• silnější, než je nějaká předem definovaná prahová hodnota (tj. silnější, než je 0.5)
• lokálně maximální (silnější než korelace šablony v sousedních pixelech)

Oblasti korelace šablony nad 0.75	Body lokálně maximální korelace šablon	Body lokálně maximální korelace šablon nad 0,75

Souhrn

Popsanou metodu lze v Adaptive Vision Studiu vyjádřit poměrně snadno – budeme potřebovat pouze dva vestavěné filtry. Pomocí filtru ImageCorrelationImage vypočítáme korelační obraz šablony a poté identifikujeme shody pomocí ImageLocalMaxima – stačí nastavit parametr inMinValue, který z výsledků odřízne slabá lokální maxima, jak bylo uvedeno v předchozí části.

Přestože zavedená technika postačovala k řešení uvažovaného problému, můžeme si všimnout jejích důležitých nedostatků:

• Výskyt šablony musí zachovávat orientaci referenčního obrazu šablony.
• Metoda je neefektivní, protože výpočet korelačního obrazu šablony pro středně velké až velké obrazy je časově náročný.

V dalších částech se budeme zabývat tím, jak jsou tyto problémy řešeny v pokročilých technikách porovnávání šablon:

Srovnávání na základě stupňů šedi, srovnávání na základě hran

Srovnávání na základě stupňů šedi je pokročilý algoritmus srovnávání šablon, který rozšiřuje původní myšlenku detekce šablon na základě korelace, zvyšuje její účinnost a umožňuje vyhledávat výskyty šablon bez ohledu na jejich orientaci. Edge-based Matching tuto metodu ještě více vylepšuje tím, že omezuje výpočet na oblasti okrajů objektu.

V této části popíšeme vnitřní podrobnosti obou algoritmů. V další části (Sada nástrojů Filtr) si vysvětlíme, jak tyto techniky používat v Adaptive Vision Studiu.

Obrázková pyramida

Obrázková pyramida je série obrázků, přičemž každý obrázek je výsledkem převzorkování (zmenšení, v tomto případě o dvojnásobek) předchozího prvku.

.

Úroveň 0 (vstupní obrázek)	Úroveň 1	Úroveň 2

Zpracování pyramid

Pro zvýšení účinnosti korelace lze použít obrazové pyramidy-.založené na detekci šablon. Důležitým zjištěním je, že šablona zobrazená v referenčním obraze je obvykle rozeznatelná i po výrazném zmenšení vzorku obrazu (i když se při tom samozřejmě ztratí jemné detaily). Proto můžeme identifikovat kandidáty na shodu ve zmenšeném (a tedy mnohem rychleji zpracovatelném) obrazu na nejvyšší úrovni naší pyramidy a poté opakovat hledání na nižších úrovních pyramidy, přičemž pokaždé vezmeme v úvahu pouze pozice šablony, které dosáhly vysokého skóre na předchozí úrovni.

Na každé úrovni pyramidy budeme potřebovat vhodně zmenšený obraz referenční šablony, tj. je třeba vypočítat jak pyramidu vstupního obrazu, tak pyramidu obrazu šablony.

Úroveň 0 (referenční obraz šablony)	Úroveň 1	Úroveň 2

Šedá škála-.based Matching

Ačkoli v některých aplikacích je orientace objektů jednotná a pevná (jak jsme viděli v příkladu se zástrčkou), často se stává, že objekty, které mají být detekovány, vypadají natočené. V algoritmech pro porovnávání šablon je klasické pyramidové vyhledávání upraveno tak, aby umožňovalo porovnávání pod více úhly, tj. identifikaci pootočených instancí šablony.

Toho je dosaženo tím, že se nevypočítá pouze jedna pyramida obrazu šablony, ale sada pyramid – jedna pro každé možné pootočení šablony. Během prohledávání pyramid na vstupním obrazu algoritmus identifikuje dvojice (poloha šablony, orientace šablony), nikoliv pouze polohy šablony. Podobně jako u původního schématu algoritmus na každé úrovni vyhledávání ověřuje pouze ty dvojice (poloha, orientace), které na předchozí úrovni dobře zabodovaly (tj. zdálo se, že odpovídají šabloně na obrázku s nižším rozlišením).

Obrázek šablony	Vstupní obrázek	Výsledky viac.úhlového porovnávání

Technika pyramidového porovnávání spolu s víceúhelníkovým vyhledáváním tvoří metodu Grayscale-based Template Matching.

Shodování založené na hranách

Shodování založené na hranách rozšiřuje dříve probírané Shodování založené na stupních šedi pomocí jednoho zásadního poznatku – tvar jakéhokoli objektu je definován především tvarem jeho hran. Proto bychom místo porovnávání celé šablony mohli extrahovat její hrany a porovnávat pouze blízké pixely, čímž bychom se vyhnuli některým zbytečným výpočtům. V běžných aplikacích je dosažené zrychlení obvykle značné.

Odpovídání hran objektu namísto objektu jako celku vyžaduje mírnou modifikaci původní metody přiřazování pyramid: představme si, že přiřazujeme objekt jednotné barvy umístěný na jednotném pozadí. Všechny pixely okrajů objektu by měly stejnou intenzitu a původní algoritmus by porovnával objekt kdekoli, kde je dostatečně velká skvrna příslušné barvy, a toho zjevně nechceme dosáhnout. K vyřešení tohoto problému se v případě funkce Edge-based Matching porovnává směr gradientu (pro ilustrační účely reprezentovaný jako barva v prostoru HSV) okrajových pixelů, nikoli jejich intenzita.

Sada nástrojů filtrů

Adaptive Vision Studio poskytuje sadu filtrů implementujících jak funkci Grayscale-based Matching, tak Edge-based Matching. Seznam filtrů naleznete v části Filtry pro porovnávání šablon.

Jelikož před porovnáváním pyramid musí být šablonový obraz předzpracován (musíme vypočítat pyramidy šablonového obrazu pro všechna možná natočení), jsou algoritmy rozděleny do dvou částí:

• Vytvoření modelu – v tomto kroku se vypočítají pyramidy šablonového obrazu a výsledky se uloží do modelu – atomického objektu představujícího všechna data potřebná ke spuštění porovnávání pyramid.
• Shoda – v tomto kroku se model šablony použije ke shodě se šablonou ve vstupním obrázku.

Taková organizace zpracování umožňuje vypočítat model jednou a opakovaně jej použít.

Dostupné filtry

Pro obě metody párování šablon jsou k dispozici dva filtry, jeden pro každý krok algoritmu.

	Shoda na základě stupnice šedi	Shoda na základě hrany
Vytvoření modelu:
Shoda:

Upozorňujeme, že použití filtrů CreateGrayModel a CreateEdgeModel bude nutné pouze v pokročilejších aplikacích. Jinak stačí použít jediný filtr kroku Shoda a model vytvořit nastavením parametru inGrayModel nebo inEdgeModel filtru. Další informace naleznete v části Vytváření modelů pro Template Matching.

Hlavní problém při použití techniky Template Matching spočívá spíše v pečlivém nastavení parametrů filtrů než v návrhu struktury programu.

Schémata pokročilých aplikací

Existuje několik druhů pokročilých aplikací, pro které interaktivní grafické rozhraní pro Template Matching nestačía uživatel potřebuje použít přímo filtr CreateGrayModel nebo CreateEdgeModel. Například:

1. Když vytvoření modelu vyžaduje netriviální předzpracování obrázku.
2. Když potřebujeme celou řadu modelů vytvořených automaticky ze sady obrázků.
3. Když by koncový uživatel měl mít možnost definovat své vlastní šablony v běžící aplikaci (např. výběrem na vstupním obrázku).

Schéma 1: Tvorba modelu v samostatném programu

Pro případy 1 a 2 je vhodné realizovat tvorbu modelu v samostatném makrofiltru Task,uložit model do souboru AVDATA a tento soubor pak propojit se vstupem odpovídajícího filtru vhlavním programu:

Tvorba modelu:	Hlavní program:

Když je tento program připraven, můžete kdykoli spustit úlohu „VytvořitModel“ jako program, abyste vytvořili model. Odkaz na datový soubor na vstupu párovacího filtru pak není třeba nijak upravovat, protože se jedná pouze o odkaz a mění se pouze soubor na disku.

Schéma 2: Dynamické vytváření modelu

Pro případ 3, kdy je třeba model vytvořit dynamicky, musí být jak filtr pro vytváření modelu, tak párovací filtr ve stejné úloze. První z nich by však měl být proveden podmíněně,když je vyvolána příslušná událost HMI (např. uživatel klikne na ImpulseButton nebo provede nějakou akci myší ve VideoBoxu). Pro reprezentaci modelu by měl být použit typ registerof EdgeModel?, který bude uchovávat poslední model (další možností je použít filtr LastNotNil).Zde je příklad realizace s modelem vytvořeným z předdefinovaného pole na vstupním obrázku při kliknutí na tlačítko v HMI:

Vytvoření modelu

Výška pyramidy

Parametr inPyramidHeight určuje počet úrovní shody pyramidy a měl by být nastaven na největší číslo, pro které je šablona ještě rozpoznatelná na nejvyšší úrovni pyramidy. Tato hodnota by měla být zvolena interaktivním experimentováním pomocí diagnostického výstupu diagPatternPyramid (přiřazování na základě stupňů šedi) nebo diagEdgePyramid (přiřazování na základě hran).

V následujícím příkladu by hodnota inPyramidHeight 4 byla příliš vysoká (pro obě metody), protože struktura šablony se na této úrovni pyramidy zcela ztratí. Také hodnota 3 se zdá být poněkud přehnaná (zejména v případě Edge-based Matching), zatímco hodnota 2 by byla rozhodně bezpečnou volbou.

	Úroveň 0	Úroveň 1	Úroveň 2	Úroveň 3	Úroveň 4
Shoda na základě stupnice šedi (diagPatternPyramid):
Shoda na základě hrany (diagEdgePyramid):

Rozsah úhlů

Parametry inMinAngle, inMaxAngle určují rozsah orientací šablony, které budou brány v úvahu při porovnávání. Například (hodnoty v závorkách představují dvojice hodnot inMinAngle, inMaxAngle):

• (0.0, 360.0): uvažují se všechna natočení (výchozí hodnota)
• (-15.0, 15.0): výskyty šablony se mohou odchýlit od orientace referenční šablony nejvýše o 15,0 stupňů (v každém směru)
• (0.0, 0.0): očekává se, že výskyty šablony zachovají orientaci referenční šablony

Široký rozsah možných orientací přináší značnou režii (jak ve využití paměti, tak ve výpočetním čase), proto je vhodné rozsah omezit, kdykoli je to možné.

Nastavení detekce hran (pouze porovnávání na základě hran)

Parametry inEdgeMagnitudeThreshold, inEdgeHysteresis filtru CreateEdgeModel určují nastavení hysterezního prahování použitého pro detekci hran v obrazu šablony. Čím nižší je hodnota inEdgeMagnitudeThreshold, tím více hran bude ve vzorovém obraze detekováno. Tyto parametry by měly být nastaveny tak, aby byly detekovány všechny významné hrany šablony a množství nadbytečných hran (šumu) ve výsledku bylo co nejmenší. Podobně jako u výšky pyramidy je třeba prahové hodnoty detekce hran zvolit interaktivním experimentováním pomocí diagnostického výstupu diagEdgePyramid – tentokrát se musíme podívat pouze na obrázek na nejnižší úrovni.

(15,0, 30.0) – nadměrné množství šumu	(40.0, 60.0) – OK	(60.0, 70.0) – ztraceny významné hrany

Filtr CreateEdgeModel neumožní vytvořit model, ve kterém nebyly na vrcholu pyramidy zjištěny žádné hrany (což znamená, že byly ztraceny nejen některé významné hrany, ale všechny), a v takovém případě dojde k chybě. Kdykoli k tomu dojde, měla by se snížit výška pyramidy nebo prahové hodnoty hran, případně obojí.

Matching

Parametr inMinScore určuje, jak tolerantní bude algoritmus při ověřování kandidátů na shodu – čím vyšší hodnota, tím méně výsledků bude vráceno. Tento parametr by měl být interaktivním experimentováním nastaven na dostatečně nízkou hodnotu, aby bylo zajištěno, že budou vráceny všechny správné shody, ale ne o mnoho nižší, protože příliš nízká hodnota zpomaluje algoritmus a může způsobit, že se ve výsledcích objeví falešné shody.

Tipy a osvědčené postupy

Jak vybrat metodu?

Pro naprostou většinu aplikací bude metoda Edge-based Matching robustnější i efektivnější než metoda Grayscale-based Matching. Lokální souřadnicové systémy