Odpovídající pronásledování - Matching pursuit

Signál a jeho vlnková reprezentace. Každý pixel v teplotní mapa (nahoře) představuje atom (vlnka vycentrovaná v čase podle vodorovné polohy a s frekvencí odpovídající výšce). Barva pixelu dává vnitřní produkt odpovídajícího waveletového atomu se signálem (dole). Sledování shody by mělo představovat signál jen několika atomy, jako jsou tři ve středu jasně viditelných elips.

Odpovídající pronásledování (MP) je a řídká aproximace algoritmus, který najde „nejlépe se shodující“ projekce vícerozměrných dat do rozsahu úplného (tj. redundantního) slovníku ${displaystyle D}$. Základní myšlenkou je přibližně představovat signál ${displaystyle f}$ z Hilbertův prostor ${displaystyle H}$ jako vážený součet konečně mnoha funkcí ${displaystyle g_ {gamma _ {n}}}$ (nazývané atomy) převzaty z ${displaystyle D}$. Aproximace s ${displaystyle N}$ atomy mají formu

${displaystyle f (t) cca {hat {f}} _ {N} (t): = součet _ {n = 1} ^ {N} a_ {n} g_ {gamma _ {n}} (t)}$

kde ${displaystyle g_ {gamma _ {n}}}$ je ${displaystyle gamma _ {n}}$sloupec matice ${displaystyle D}$ a ${displaystyle a_ {n}}$ je skalární váhový faktor (amplituda) pro atom ${displaystyle g_ {gamma _ {n}}}$. Normálně ne každý atom ${displaystyle D}$ bude použit v této částce. Místo toho si hledání shody vybírá atomy jeden po druhém, aby maximálně (chamtivě) snížil chybu aproximace. Toho je dosaženo nalezením atomu, který má nejvyšší vnitřní produkt se signálem (za předpokladu, že jsou atomy normalizovány), odečtením od signálu aproximace, která používá pouze tento jeden atom, a opakováním procesu, dokud není signál uspokojivě rozložen, tj. norma rezidua je malá, kde reziduální po výpočtu ${displaystyle gamma _ {N}}$ a ${displaystyle a_ {N}}$ je označen

${displaystyle R_ {N + 1} = f- {hat {f}} _ {N}}$.

Li ${displaystyle R_ {n}}$ konverguje rychle na nulu, pak je k získání dobré aproximace potřeba pouze několik atomů ${displaystyle f}$. Takový řídké reprezentace jsou žádoucí pro kódování a kompresi signálu. Přesněji řečeno, problém sparity, k němuž má odpovídat pronásledování přibližně vyřešit je

${displaystyle min _ {x} | f-Dx | _ {2} ^ {2} {ext {subject to}} | x | _ {0} leq N,}$

kde ${displaystyle | x | _ {0}}$ je ${displaystyle L_ {0}}$ pseudonorma (tj. počet nenulových prvků ${displaystyle x}$). V předchozí notaci byly nenulové položky ${displaystyle x}$ jsou ${displaystyle x_ {gamma _ {n}} = a_ {n}}$. Řešení problému se sparitou přesně je NP-tvrdé, proto se používají aproximační metody jako MP.

Pro srovnání zvažte Fourierova transformace reprezentace signálu - to lze popsat pomocí výše uvedených výrazů, kde je slovník sestaven ze sinusových základních funkcí (nejmenší možný úplný slovník). Hlavní nevýhodou Fourierovy analýzy při zpracování signálu je to, že extrahuje pouze globální vlastnosti signálů a nepřizpůsobuje se analyzovaným signálům ${displaystyle f}$. Když vezmeme extrémně redundantní slovník, můžeme v něm hledat atomy (funkce), které nejlépe odpovídají signálu ${displaystyle f}$.

Algoritmus

Příklad načítání neznámého signálu (šedá čára) z několika měření (černé tečky) pomocí algoritmu sledování ortogonální shody (fialové tečky ukazují načtené koeficienty).

Li ${displaystyle D}$ obsahuje velké množství vektorů, které hledají většina řídké zastoupení ${displaystyle f}$ je výpočetně nepřijatelný pro praktické aplikace. V roce 1993 Mallat a Zhang^[1] navrhl a chamtivý řešení, které pojmenovali „Matching Pursuit.“ Pro jakýkoli signál ${displaystyle f}$ a jakýkoli slovník ${displaystyle D}$, algoritmus iterativně generuje seřazený seznam atomových indexů a váhových skalárů, které tvoří neoptimální řešení problému řídké reprezentace signálu.

Algoritmus Odpovídající pronásledování Vstup: Signál: ${displaystyle f (t)}$, slovník ${displaystyle D}$ s normalizovanými sloupci ${displaystyle g_ {i}}$. Výstup: Seznam koeficientů ${displaystyle (a_ {n}) _ {n = 1} ^ {N}}$ a indexy pro odpovídající atomy ${displaystyle (gamma _ {n}) _ {n = 1} ^ {N}}$. Inicializace: ${displaystyle R_ {1}, leftarrow, f (t)}$;   ${displaystyle n, leftarrow, 1}$; Opakovat: Najít ${displaystyle g_ {gamma _ {n}} v D}$ s maximálním vnitřním produktem ${displaystyle | langle R_ {n}, g_ {gamma _ {n}} úhel |}$;   ${displaystyle a_ {n}, leftarrow, langle R_ {n}, g_ {gamma _ {n}} úhel}$;   ${displaystyle R_ {n + 1}, leftarrow, R_ {n} -a_ {n} g_ {gamma _ {n}}}$;   ${displaystyle n, leftarrow, n + 1}$; Do stavu zastavení (například: ${displaystyle | R_ {n} |$) vrátit se

Ve zpracování signálu je koncept sledování shody spojen se statistikou pronásledování projekce, ve kterých se nacházejí „zajímavé“ projekce; ty, které se více odchylují od a normální distribuce jsou považovány za zajímavější.

Vlastnosti

• Algoritmus konverguje (tj. ${displaystyle R_ {n} o 0}$) pro všechny ${displaystyle f}$ to je v prostoru překlenutém slovníkem.
• Chyba ${displaystyle | R_ {n} |}$ monotónně klesá.
• Jako v každém kroku je zbytek kolmý k vybranému filtru, rovnice zachování energie je pro každý splněna ${displaystyle N}$:

${displaystyle | f | ^ {2} = | R_ {N + 1} | ^ {2} + součet _ {n = 1} ^ {N} {| a_ {n} | ^ {2}}}$.

• V případě, že vektory v ${displaystyle D}$ jsou ortonormální, místo aby byly nadbytečné, pak MP je forma analýza hlavních komponent

Aplikace

Na signál, obraz bylo použito odpovídající pronásledování^[2] a kódování videa,^[3][4] tvarová reprezentace a rozpoznávání,^[5] Kódování 3D objektů,^[6] a v interdisciplinárních aplikacích, jako je monitorování strukturálního zdraví.^[7] Ukázalo se, že funguje lépe než DCT založené kódování pro nízké přenosové rychlosti jak v efektivitě kódování, tak v kvalitě obrazu.^[8]Hlavním problémem sledování shody je výpočetní složitost kodéru. V základní verzi algoritmu je třeba při každé iteraci hledat velký slovník. Mezi vylepšení patří použití přibližných reprezentací slovníku a neoptimální způsoby výběru nejlepší shody při každé iteraci (extrakce atomu).^[9]Algoritmus sledování shody se používá v MP / SOFT, metodě simulace kvantové dynamiky.^[10]

MP se také používá v slovníkové učení.^[11][12] V tomto algoritmu se atomy učí z databáze (obecně přirozené scény, jako jsou obvyklé obrázky) a nevybírají se z obecných slovníků.

Rozšíření

Populární rozšíření Matching Pursuit (MP) je jeho ortogonální verze: Orthogonal Matching Pursuit^[13][14] (OMP). Hlavní rozdíl oproti MP spočívá v tom, že po každém kroku Všechno doposud extrahované koeficienty se aktualizují výpočtem ortogonální projekce signálu do podprostoru překlenutého dosud vybranou sadou atomů. To může vést k lepším výsledkům než standardní MP, ale vyžaduje to více výpočtů.

Rozšíření, jako je vícekanálový MP^[15] a vícekanálový OMP^[16] umožnit člověku zpracovávat vícesložkové signály. Zřejmým rozšířením Matching Pursuit je více pozic a měřítek rozšířením slovníku o slovník waveletů. To lze efektivně provést pomocí operátoru konvoluce beze změny jádrového algoritmu.^[17]

Odpovídající pronásledování souvisí s oblastí komprimované snímání a byl rozšířen výzkumníky v této komunitě. Pozoruhodné rozšíření jsou Orthogonal Matching Pursuit (OMP),^[18] Postupně OMP (StOMP),^[19] pronásledování porovnávání kompresního vzorkování (CoSaMP),^[20] Zobecněný OMP (gOMP),^[21] a Multipath Matching Pursuit (MMP).^[22]

Viz také

• Algoritmus CLEAN
• Analýza hlavních komponent (PCA)
• Pronásledování projekce
• Zpracování obrazu
• Zpracování signálu
• Řídká aproximace

Reference