Geometrický hash - Geometric hashing - Wikipedia

v počítačová věda, geometrický hash je metoda pro efektivní hledání dvojrozměrných objektů představovaných diskrétními body, které prošly afinní transformace, ačkoli existují rozšíření pro další reprezentace a transformace objektů. V off-line kroku jsou objekty kódovány zpracováním každé dvojice bodů jako geometrické základ. Zbývající body mohou být zastoupeny v neměnný módy s ohledem na tento základ pomocí dvou parametrů. Pro každý bod je to kvantováno transformované souřadnice jsou uloženy v souboru hash tabulka jako klíč a indexy bazických bodů jako hodnota. Poté je vybrána nová dvojice základních bodů a postup se opakuje. V kroku on-line (rozpoznávání) jsou náhodně vybrané páry datových bodů považovány za kandidátské báze. Pro každý kandidátský základ jsou zbývající datové body zakódovány podle základu a možné korespondence z objektu se nacházejí v dříve vytvořené tabulce. Kandidátská báze je přijata, pokud dostatečně velký počet datových bodů indexuje konzistentní objektovou základnu.

Geometrický hash byl původně navržen v počítačové vidění pro rozpoznávání objektů ve 2D a 3D,^[1] ale později byl aplikován na různé problémy jako např strukturální vyrovnání z bílkoviny.^[2]^[3]

Geometrický hash v počítačovém vidění

Geometrický hash je metoda používaná pro rozpoznávání objektů. Řekněme, že chceme zkontrolovat, zda lze na vstupním obrázku vidět modelový obrázek. Toho lze dosáhnout geometrickým hašováním. Metodu lze použít k rozpoznání jednoho z více objektů v základně, v tomto případě by hash tabulka měla ukládat nejen informace o póze, ale také index objektového modelu v základně.

Příklad

Pro zjednodušení tento příklad příliš mnoho nepoužije bodové funkce a předpokládejme, že jejich deskriptory jsou dány pouze jejich souřadnicemi (v praxi místní deskriptory jako PROSÍT lze použít pro indexování).

Fáze tréninku

Body objektu v souřadnicovém systému obrazu a osy souřadnicového systému pro základnu (P2, P4)

Najděte rysové body modelu. Předpokládejme, že v obraze modelu se souřadnicemi se nachází 5 prvků ${ displaystyle (12,17);}$ ${ displaystyle (45,13);}$ ${ displaystyle (40,46);}$ ${ displaystyle (20,35);}$ ${ displaystyle (35,25)}$ , viz obrázek.
Představte základ pro popis umístění hlavních bodů. Pro 2D prostor a transformace podobnosti základ je definován dvojicí bodů. Počáteční bod je umístěn uprostřed segmentu spojujícího dva body (v našem příkladu P2, P4), symbol ${ displaystyle x '}$ osa směřuje k jednomu z nich, k ${ displaystyle '$ je kolmý a prochází počátkem. Měřítko je vybráno tak, aby absolutní hodnota ${ displaystyle x '}$ pro oba bazické body je 1.
Popište umístění prvků s ohledem na tento základ, tj. Vypočítejte projekce do nových souřadnicových os. Souřadnice by měly být diskretizovány, aby bylo rozpoznání robustní hluk, vezmeme velikost koše 0,25. Získáme tak souřadnice ${ displaystyle (-0,75; -1,25);}$ ${ displaystyle (1,00,0,00);}$ ${ displaystyle (-0,50,1,25);}$ ${ displaystyle (-1,00,0,00);}$ ${ displaystyle (0,00,0,25)}$
Uložte základnu do a hash tabulka indexovány prvky (v tomto případě pouze transformované souřadnice). Pokud by existovalo více objektů, se kterými by se mělo shodovat, měli bychom také uložit číslo objektu spolu s párem bází.
Opakujte postup pro jiný pár bází (krok 2). Je třeba to zvládnout okluze. V ideálním případě by všechnykolineární páry by měly být vyjmenovány. Poskytujeme hashovací tabulku po dvou iteracích, pár (P1, P3) je vybrán pro druhou.

Tabulka hash:

Vektor ( ${ displaystyle x '}$ , ${ displaystyle '$ )	základ
${ displaystyle (-0,75; -1,25);}$	(P2, P4)
${ displaystyle (1,00,0,00);}$	(P2, P4)
${ displaystyle (-0,50,1,25);}$	(P2, P4)
${ displaystyle (-1,00,0,00);}$	(P2, P4)
${ displaystyle (0,00,0,25)}$	(P2, P4)
${ displaystyle (1,00,0,00);}$	(P1, P3)
${ displaystyle (0,00,1,25);}$	(P1, P3)
${ displaystyle (-1,00,0,00);}$	(P1, P3)
${ displaystyle (0,00, -0,25);}$	(P1, P3)
${ displaystyle (0,00,0,50)}$	(P1, P3)

Většina hash tabulek nemůže mít identické klíče namapované na různé hodnoty. Ve skutečném životě tedy nebude kódovat základní klíče (1,0, 0,0) a (-1,0, 0,0) v hašovací tabulce.

Fáze rozpoznávání

Najděte na vstupním obrázku zajímavé body funkcí.
Vyberte libovolný základ. Pokud neexistuje vhodný libovolný základ, je pravděpodobné, že vstupní obrázek neobsahuje cílový objekt.
Na nové bázi popište souřadnice hlavních bodů. Kvantujte získané souřadnice tak, jak tomu bylo dříve.
Porovnejte všechny prvky transformovaného bodu ve vstupním obrazu s hashovací tabulkou. Pokud jsou bodové prvky identické nebo podobné, zvyšte počet pro odpovídající základnu (a typ objektu, pokud existuje).
U každého základu tak, aby počet přesahoval určitou prahovou hodnotu, ověřte hypotézu, že odpovídá obrazovému základu zvolenému v kroku 2. Přeneste souřadný systém obrazu do modelového (pro předpokládaný objekt) a zkuste je porovnat. Pokud je úspěšný, je objekt nalezen. V opačném případě se vraťte ke kroku 2.

Hledání zrcadlového vzoru

Zdá se, že tato metoda je schopná zpracovat pouze změnu měřítka, překlad a rotaci. Vstupní obraz však může obsahovat objekt v zrcadlové transformaci. Proto by měl být objekt schopen najít i geometrický hash. Existují dva způsoby, jak detekovat zrcadlené objekty.

U vektorového grafu udělejte levou stranu kladnou a pravou stranu zápornou. Vynásobením pozice x číslem -1 získáte stejný výsledek.
Jako základ použijte 3 body. To umožňuje detekovat zrcadlové obrazy (nebo objekty). Ve skutečnosti je použití 3 bodů pro základ dalším přístupem k geometrickému hašování.

Geometrické hašování ve vyšších dimenzích

Podobně jako v předchozím příkladu platí hash pro data ve vyšších dimenzích. U trojrozměrných datových bodů jsou pro základ zapotřebí také tři body. První dva body definují osu x a třetí bod definuje osu y (s prvním bodem). Osa z je kolmá na vytvořenou osu pomocí pravidla pravé ruky. Všimněte si, že pořadí bodů ovlivňuje výsledný základ

Viz také

Percepční hašování

Reference

^ TAK JAKO. Mian, M. Bennamoun a R. Owens, Trojrozměrné modelové rozpoznávání a segmentace objektů v přeplněných scénách., IEEE Transactions on Pattern Analysis and Machine Intelligence, sv. 28, říjen 2006, str. 1584-601.
^ Moll, Mark; Bryant, Drew H .; Kavraki, Lydia E. (11.11.2010). "Algoritmus LabelHash pro shodu spodní stavby". BMC bioinformatika. 11: 555. doi:10.1186/1471-2105-11-555. ISSN 1471-2105. PMC 2996407. PMID 21070651.
^ Nussinov, R .; Wolfson, H. J. (1991-12-01). „Efektivní detekce trojrozměrných strukturních motivů v biologických makromolekulách technikami počítačového vidění“. Sborník Národní akademie věd Spojených států amerických. 88 (23): 10495–10499. doi:10.1073 / pnas.88.23.10495. ISSN 0027-8424. PMC 52955. PMID 1961713.

Wolfson, H. J. a Rigoutsos, I (1997). Geometrický hash: Přehled. IEEE Computational Science and Engineering, 4 (4), 10-21.

[Mian2006-1] TAK JAKO. Mian, M. Bennamoun a R. Owens, Trojrozměrné modelové rozpoznávání a segmentace objektů v přeplněných scénách., IEEE Transactions on Pattern Analysis and Machine Intelligence, sv. 28, říjen 2006, str. 1584-601.

[2] Moll, Mark; Bryant, Drew H .; Kavraki, Lydia E. (11.11.2010). "Algoritmus LabelHash pro shodu spodní stavby". BMC bioinformatika. 11: 555. doi:10.1186/1471-2105-11-555. ISSN 1471-2105. PMC 2996407. PMID 21070651.

[3] Nussinov, R .; Wolfson, H. J. (1991-12-01). „Efektivní detekce trojrozměrných strukturních motivů v biologických makromolekulách technikami počítačového vidění“. Sborník Národní akademie věd Spojených států amerických. 88 (23): 10495–10499. doi:10.1073 / pnas.88.23.10495. ISSN 0027-8424. PMC 52955. PMID 1961713.

[1]

[2]

[3]