Komprimované snímání (anglicky compressed sensing nebo také compressive sampling) je metoda snímání a rekonstrukce signálu, která za předpokladu řídkosti signálu ve vhodné reprezentaci vede ke snížení počtu měření Hrbáček, R.; Rajmic, P.; Veselý, V. & Špiřík, J. Řídké reprezentace signálů: komprimované snímání. Elektrorevue – Internetový časopis, 2011, 1-8 . Z pohledu matematiky se jedná o řešení nedourčené soustavy lineárních rovnic se snahou o nalezení řešení s co nejmenším počtem nenulových koeficientů.
náhled|vpravo|Schéma úlohy
Oproti obvyklému přístupu ke snímání dat, kdy nejprve musíme nasbírat veškerá data, poté provést vhodnou transformaci a následně zachovat jen ty koeficienty, které nesou dostatečné množství informace, při komprimovaném snímání stačí snímat signál pouze tolikrát, kolik je skutečně třeba pro následnou rekonstrukci (snímání a komprimace jsou tedy jediným nedělitelným procesem). Signál z předpokládáme řídký v nějakém slovníku (bázi či framu) Ψ (z = Ψx, x je řídké) a provedeme malý počet měření, které mají charakter lineárních kombinací složek signálu. Proces snímání lze tedy zapsat jako y = Pz = PΨx. Zde P je tzv. měřicí matice rozměru m×N, kde m ≪ N. Fáze rekonstrukce signálu je pak řešením problému:
Tento problém je již nelineární a časově velmi náročný, dokonce NP-těžký Hrbáček, R.; Rajmic, P.; Veselý, V. & Špiřík, J. Řídké reprezentace signálů: úvod do problematiky. Elektrorevue – Internetový časopis, 2011, 1-10 , a proto jej nelze řešit přímo. Jednou z možností je nahradit -normu nějakou jinou (např. ), takové metody se pak nazývají relaxační a patří mezi ně především Basis Pursuit (BP), Least Angle Regression homotopy method (LARS) a Iterative Reweighted Least Squares (IRLS). Druhou skupinu metod tvoří hladové (greedy) algoritmy, které iterativně aproximují signál hledáním nejvýznamnějších atomů ze slovníku. Výhodou těchto metod je nízká složitost, bohužel však není zaručeno dosažení globálního minima. Zástupci této kategorie jsou Matching Pursuit (MP), Orthogonal Matching Pursuit (OMP) a další modifikace. Mimo tyto dvě kategorie existují algoritmy hybridní, využívající rysy obou předchozích skupin (např. A*OMP) .
Aplikace komprimovaného snímání zahrnují zpracování obrazu (např. rychlé snímání v magnetické rezonanci Lustig, M.; Donoho, D.; Santos, J.; aj.: Compressed Sensing MRI. IEEE Signal Processing Magazine, ročník 25, č. 2, 2008: s. 72–82, ISSN 1053-5888. nebo tzv. jednopixelová kamera Duarte, M.; Davenport, M.; Takhar, D.; aj.: Single-Pixel Imaging via Compressive Sampling. IEEE Signal Processing Magazine, ročník 25, č. 2, 2008: s. 83–91, ISSN 1053-5888.), odšumování signálů (denoising), odstraňování rozmazání (deblurring), doplňování chybějící informace v signálu (inpainting) Elad, M.: Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer, 2010, ., nové metody radiolokace Fannjiang, A. C.; Strohmer, T.; Yan, P.: Compressed Remote Sensing of Sparse Objects. SIAM Journal on Imaging Sciences, ročník 3, č. 3, 2010: s. 595–618., optimalizace ekvalizace v bezdrátových OFDM kanálech Tauböck, G.; Hlawatsch, F.; Eiwen, D.; aj.: Com-pressive Estimation of Doubly Selective Channels in Multicarrier Systems: Leakage Effects and Sparsity-Enhancing Processing. IEEE Journal of Selected Topics in Signal Processing, ročník 4, č. 2, 2010: s. 255–271, ISSN 1932-4553., korekční kódování v komunikačních technologiích Candes, E. J.; Tao, T.: Decoding by Linear Programming. IEEE Transactions on Information Theory, ročník 51, 2005: s. 4203–4215. nebo pokusy o konstrukci nových typů A/D převodníků Candes, E. J.; Wakin, M. B.: An introduction to compressive sampling. IEEE Signal Processing Magazine, ročník 25, č. 2, 2008: s. 21–30, ISSN 1053-5888..
Reference
Související články Nedourčená soustava rovnic Frame Řídký vektor
Kategorie:Zpracování signálu Kategorie:Řídká reprezentace signálů Kategorie:Optimalizace (matematika) Kategorie:Lineární algebra Kategorie:Teorie informace