“Compressive Sensing” “Compressive Sensing” Novos Paradigmas para Aquisição e Compressão de Imagens Projeto Final , 17 de Dezembro de 2008 Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros Autora: Orientadores: Examinadores: Adriana Schulz Prof. Eduardo A. B. da Silva Prof. Luiz Velho Prof. Gelson Vieira Mendonça Prof. Lisandro Lovisolo 1 Objetivos “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing • estudo teórico • exemplos de aplicações em processamento de imagens Teoria de Compressive Sensing Resultados Trabalhos Futuros 2 Motivação “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 3 “Compressive Sensing” Motivação Compressão de Imagens Amostragem =⇒ Nyquist Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 3 “Compressive Sensing” Motivação Compressão de Imagens Amostragem =⇒ Nyquist Nyquit era pessimista!!! Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 3 “Compressive Sensing” Motivação Compressão de Imagens Amostragem =⇒ Nyquist Nyquit era pessimista!!! Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros Taxa de Nyquit × Taxa de Informação 3 “Compressive Sensing” 1 Compressão de Imagens 2 Representação de Sinais 3 Introdução a Compressive Sensing Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados 4 Teoria de Compressive Sensing Trabalhos Futuros 5 Resultados 6 Trabalhos Futuros 4 “Compressive Sensing” 1 Compressão de Imagens 2 Representação de Sinais 3 Introdução a Compressive Sensing Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados 4 Teoria de Compressive Sensing Trabalhos Futuros 5 Resultados 6 Trabalhos Futuros 5 “Compressive Sensing” Sinais naturais são compressíveis Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 6 “Compressive Sensing” Compressão de Imagens Transform Coding Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 7 “Compressive Sensing” 1 Compressão de Imagens 2 Representação de Sinais 3 Introdução a Compressive Sensing Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados 4 Teoria de Compressive Sensing Trabalhos Futuros 5 Resultados 6 Trabalhos Futuros 8 “Compressive Sensing” Representação de Sinais x2 x2 Compressão de Imagens y1 Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing y2 Resultados Trabalhos Futuros x1 x1 9 Representação de Sinais “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 10 “Compressive Sensing” 1 Compressão de Imagens 2 Representação de Sinais 3 Introdução a Compressive Sensing Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados 4 Teoria de Compressive Sensing Trabalhos Futuros 5 Resultados 6 Trabalhos Futuros 11 Sinais Esparsos “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 12 Sinais Esparsos “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros Não sabemos onde os pontos estão... 12 O Truque amostras pontuais “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 13 O Truque amostras pontuais × medidas do sinal “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 13 O Truque amostras pontuais × medidas do sinal “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Cada medida yk é o produto interno sobre uma função teste diferente φk : Teoria de Compressive Sensing Resultados Trabalhos Futuros y1 = hx, φ1 i , y2 = hx, φ2 i , . . . , yM = hx, φM i onde M é o número de medidas. 13 O Problema Algébrico “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros • Este problema é mal condicionado! 14 O Problema Algébrico “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros • Mas e se existe um domínio onde x é esparso? 15 O Problema Algébrico “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros • ΘΩ = ΦΩ Ψ∗ • Medidas y = ΘΩ s 16 “Compressive Sensing” • Existem infinitas soluções para o problema. • Desejamos encontrar aquela que torna s esparso. Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 17 “Compressive Sensing” • Existem infinitas soluções para o problema. • Desejamos encontrar aquela que torna s esparso. Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Problema NP Complexo!!! Teoria de Compressive Sensing Resultados Trabalhos Futuros 17 “Compressive Sensing” • Existem infinitas soluções para o problema. • Desejamos encontrar aquela que torna s esparso. Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Problema NP Complexo!!! Teoria de Compressive Sensing Resultados Trabalhos Futuros • Como tornar o problema viável? 17 A Norma l1 e a Esparsidade “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 18 A Norma l1 e a Esparsidade “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 19 O Algoritmo de Reconstrução min kskl1 sujeito a ΘΩ s = y s “Compressive Sensing” Compressão de Imagens Representação de Sinais onde ΘΩ = ΦΩ Ψ∗ Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 20 O Algoritmo de Reconstrução min kskl1 sujeito a ΘΩ s = y s “Compressive Sensing” Compressão de Imagens Representação de Sinais onde ΘΩ = ΦΩ Ψ∗ Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Parece um boa forma de resolver o problema. • Mas quando vai funcionar? • O que devemos assumir sobre a matriz ΦΩ ? • E sobre o número de medidas? • Que tipo de resultados podemos garantir? Trabalhos Futuros 20 “Compressive Sensing” 1 Compressão de Imagens 2 Representação de Sinais 3 Introdução a Compressive Sensing Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados 4 Teoria de Compressive Sensing Trabalhos Futuros 5 Resultados 6 Trabalhos Futuros 21 O Primeiro Teorema “Compressive Sensing” • O modelo MRI • Amostras no domínio da freqüência Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 22 Backprojection × Minimização de Total Variation “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros (a) Imagem de teste 23 Backprojection × Minimização de Total Variation “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros (a) Imagem de teste (b) Reconstrução a partir de backprojection 23 Backprojection × Minimização de Total Variation “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros (a) Imagem de teste (b) Reconstrução a partir de backprojection (c) Reconstrução a partir de otimização convexa Reconstrução perfeita! 23 Fourier Sampling Theorem “Compressive Sensing” Compressão de Imagens Teorema N • x ∈ R é S-esparso • M coeficientes de Fourier selecionados aleatoriamente. M ≥ Const · S · log N Então a reconstrução é exata com alta probabilidade. Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 24 Fourier Sampling Theorem “Compressive Sensing” Compressão de Imagens Teorema N • x ∈ R é S-esparso • M coeficientes de Fourier selecionados aleatoriamente. M ≥ Const · S · log N Então a reconstrução é exata com alta probabilidade. Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros princípio da incerteza 24 Fourier Sampling Theorem “Compressive Sensing” Compressão de Imagens Teorema N • x ∈ R é S-esparso • M coeficientes de Fourier selecionados aleatoriamente. M ≥ Const · S · log N Então a reconstrução é exata com alta probabilidade. Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros princípio da incerteza =⇒ possibilita os resultados! 24 Extensão do Fourier Sampling Theorem “Compressive Sensing” • outras possibilidades de Φ e Ψ Compressão de Imagens Definição (Coerência entre Ψ and Φ) √ µ(Φ, Ψ) = N max |hφi , ψj i| , kφi kl2 kψi kl2 = 1 i,j Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 25 Extensão do Fourier Sampling Theorem “Compressive Sensing” • outras possibilidades de Φ e Ψ Compressão de Imagens Definição (Coerência entre Ψ and Φ) √ µ(Φ, Ψ) = N max |hφi , ψj i| , kφi kl2 kψi kl2 = 1 i,j Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros Teorema Suponha que M ≥ Const · S · µ2 (Φ, Ψ) · log N Então a reconstrução é exata com alta probabilidade. 25 Princípio da Isometria Restrita (RIP) “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 26 Princípio da Isometria Restrita (RIP) “Compressive Sensing” Definição (Constante de Isometria Restrita) Para cada inteiro S = 1, 2, . . . , N define-se a constante de isometria S-restrita δS de uma matriz ΘΩ como o menor número tal que (1 − δS )ksk2l2 ≤ kΘΩ sk2l2 ≤ (1 + δS )ksk2l2 para todos vetores S-esparsos. Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros RIP ⇒ propriedade de ΘΩ relacionada à existência e limitação de δS 26 Princípio da Isometria Restrita (RIP) “Compressive Sensing” Definição (Constante de Isometria Restrita) Para cada inteiro S = 1, 2, . . . , N define-se a constante de isometria S-restrita δS de uma matriz ΘΩ como o menor número tal que (1 − δS )ksk2l2 ≤ kΘΩ sk2l2 ≤ (1 + δS )ksk2l2 para todos vetores S-esparsos. Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros RIP ⇒ propriedade de ΘΩ relacionada à existência e limitação de δS • Na verdade, RIP garante que a solução mais esparsa é única! 26 Se as colunas de ΘΩ forem l.d., ∃a, b tais que “Compressive Sensing” y = ΘΩ a = ΘΩ b Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 27 Se as colunas de ΘΩ forem l.d., ∃a, b tais que “Compressive Sensing” y = ΘΩ a = ΘΩ b • Isso sempre ocorre pois ΘΩ é gorda! • Mas, só é necessário que a combinação de quaisquer S colunas de ΘΩ seja l.i.! Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 27 Se as colunas de ΘΩ forem l.d., ∃a, b tais que “Compressive Sensing” y = ΘΩ a = ΘΩ b • Isso sempre ocorre pois ΘΩ é gorda! • Mas, só é necessário que a combinação de quaisquer S colunas de ΘΩ seja l.i.! • Se δ2S < 1 a solução que maximiza a esparsidade é única. Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 27 Se as colunas de ΘΩ forem l.d., ∃a, b tais que “Compressive Sensing” y = ΘΩ a = ΘΩ b • Isso sempre ocorre pois ΘΩ é gorda! • Mas, só é necessário que a combinação de quaisquer S colunas de ΘΩ seja l.i.! • Se δ2S < 1 a solução que maximiza a esparsidade é Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing única. Resultados Trabalhos Futuros Seja s1 e s2 S-esparsos tais que ΘΩ s1 = ΘΩ s2 = y . Seja h = s1 − s2 . ΘΩ h = ΘΩ (s1 − s2 ) = ΘΩ s1 − ΘΩ s2 = 0. Já que h é 2S-esparso, temos pela RIP: (1 − δ2S ) khk2 ≤ kΘΩ hk2 = 0 ⇒ h = 0 | {z } >0 27 Se as colunas de ΘΩ forem l.d., ∃a, b tais que “Compressive Sensing” y = ΘΩ a = ΘΩ b • Isso sempre ocorre pois ΘΩ é gorda! • Mas, só é necessário que a combinação de quaisquer S colunas de ΘΩ seja l.i.! • Se δ2S < 1 a solução que maximiza a esparsidade é Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing única. √ 2 − 1 a solução que maximiza a esparsidade e a que minimiza a norma l1 são únicas e equivalentes. • Se δ2S < Compressão de Imagens Resultados Trabalhos Futuros Teorema Seja s S-esparso. Se para a matriz ΘΩ a constante de isometria é tal que √ δ2S < 2 − 1 Então a reconstrução é exata com alta probabilidade. 27 CS Robusto “Compressive Sensing” A teoria deve ser robusta e considerar • o sinal não é exatamente esparso; ou • medições estão corrompidas por ruído. Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 28 CS Robusto “Compressive Sensing” A teoria deve ser robusta e considerar • o sinal não é exatamente esparso; ou • medições estão corrompidas por ruído. Seja: • sS a melhor aproximação S-esparsa de s Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 28 CS Robusto “Compressive Sensing” A teoria deve ser robusta e considerar • o sinal não é exatamente esparso; ou • medições estão corrompidas por ruído. Seja: • sS a melhor aproximação S-esparsa de s • y = Φx + n, onde o ruído n é limitado por knkl2 ≤ Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 28 “Compressive Sensing” CS Robusto A teoria deve ser robusta e considerar • o sinal não é exatamente esparso; ou • medições estão corrompidas por ruído. Seja: Representação de Sinais • sS a melhor aproximação S-esparsa de s • y = Φx + n, onde o ruído n é limitado por knkl2 ≤ Teorema Se δ2S < Compressão de Imagens Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados √ Trabalhos Futuros 2 − 1, a solução ŝ para ŝ = min kskl1 sujeito a kΘΩ s − y kl2 ≤ s obedece kŝ − skl2 ≤ C0 s−1/2 · kŝ − sS kl1 + C1 para valores razoáveis das constantes C0 e C1 . 28 “Compressive Sensing” 1 Compressão de Imagens 2 Representação de Sinais 3 Introdução a Compressive Sensing Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados 4 Teoria de Compressive Sensing Trabalhos Futuros 5 Resultados 6 Trabalhos Futuros 29 Procedimento Experimental “Compressive Sensing” • Diferentes cenários de aquisição de dados • Simulação com imagens já armazenadas • Variações do número de medida • Avaliação baseada em PSNR • Bases • Ψ: DCT e Wavelets • Φ: Noiselets : incoerente, ortogonal e auto-adjunta 1 −1 1 1 1 −1 1 1 1 Φ= · 1 −1 1 2 1 1 1 1 −1 Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros • Otimização: l1-Magic ŝ = mins kskl1 sujeito a y = ΘΩ s ⇒ não converge! Solução: ŝ = mins kskl1 sujeito a ky − ΘΩ skl2 ≤ 30 “Compressive Sensing” 80 80 70 70 60 60 PSNR PSNR Imagem Esparsa (DCT) 50 40 40 30 30 20 1 2 3 4 Number of Measurements 5 20 6 x 10 Compressão de Imagens 50 Representação de Sinais Introdução a Compressive Sensing 1 2 4 (a) Imagem 3.5k -Esparsa 3 4 Number of Measurements 5 6 x 10 4 Teoria de Compressive Sensing (b) Imagem 6k -Esparsa 80 70 70 60 60 PSNR PSNR Resultados 80 50 50 40 40 30 30 20 1 2 3 4 Number of Measurements 5 20 6 x 10 (c) Imagem 10k -Esparsa 4 Trabalhos Futuros 1 2 3 4 Number of Measurements 5 6 x 10 4 (d) Imagem 14k -Esparsa Figura: DCT Linear (azul), CS baseado na DCT (verde). 31 “Compressive Sensing” PSNR Imagem Aproximadamente Esparsa (DCT) 60 Compressão de Imagens 50 Representação de Sinais Introdução a Compressive Sensing 40 Teoria de Compressive Sensing 30 Resultados Trabalhos Futuros 20 1 2 3 4 Number of Measurements 5 6 x 10 4 Figura: DCT Linear (azul), CS baseado na DCT (verde). 32 “Compressive Sensing” PSNR Imagem Aproximadamente Esparsa (Wavelets) 60 Compressão de Imagens 50 Representação de Sinais 40 Introdução a Compressive Sensing 30 Teoria de Compressive Sensing Resultados 20 Trabalhos Futuros 1 2 3 4 Number of Measurements 5 6 x 10 4 Figura: DCT Linear (azul), CS baseado na DCT (verde), CS baseado em Wavelets (cian). 33 “Compressive Sensing” Avaliação Taxa × Distorção • Diversos passos de quantização Compressão de Imagens • Variações do número de medida Representação de Sinais • Avaliação baseada em PSNR Introdução a Compressive Sensing Teoria de Compressive Sensing Cálculo da taxa: Taxa = M · Ey 2562 Resultados Trabalhos Futuros onde Ey = K X k =1 pk · log 1 pk 34 “Compressive Sensing” Imagem Esparsa Quantizada 100 90 Compressão de Imagens 80 Representação de Sinais Introdução a Compressive Sensing 70 Teoria de Compressive Sensing PSNR 60 Resultados step = 0.01 step = 0.02 step = 0.05 step = 0.1 step = 0.2 step = 0.5 step = 1 step = 2 step = 3 step = 4 step = 5 step = 10 step = 20 step = 50 step = 100 50 40 30 20 Trabalhos Futuros 10 0 0 2 4 6 8 10 12 14 16 18 Rate 35 “Compressive Sensing” Imagem Original Quantizada 70 Compressão de Imagens 60 Representação de Sinais 50 Introdução a Compressive Sensing Teoria de Compressive Sensing 40 PSNR Resultados step = 0.01 step = 0.02 step = 0.05 step = 0.1 step = 0.2 step = 0.5 step = 1 step = 3 step = 5 step = 10 step = 20 step = 50 step = 100 JPEG2000 30 20 10 0 0 2 4 6 8 10 12 14 16 Trabalhos Futuros 18 Rate 36 Imagem Aproximadamente Esparsa no Domínio DCT “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing (a) Medidas = 5k (b) Medidas = 20k Resultados Trabalhos Futuros (c) Medidas = 35k (d) Medidas = 50k 37 Imagem Aproximadamente Esparsa no Domínio Wavelet “Compressive Sensing” Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing (a) Medidas = 5k (b) Medidas = 20k Resultados Trabalhos Futuros (c) Medidas = 35k (d) Medidas = 50k 38 “Compressive Sensing” Imagem Quantizada Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing (a) Medidas = 5k , Taxa = 0.36bits/pixel (b) Medidas = 20k , Taxa = 1.46bits/pixel Teoria de Compressive Sensing Resultados Trabalhos Futuros (c) Medidas = 35k , Taxa = 3.09bits/pixel (d) Medidas = 50k , Taxa = 5.17bits/pixel 39 “Compressive Sensing” 1 Compressão de Imagens 2 Representação de Sinais 3 Introdução a Compressive Sensing Compressão de Imagens Representação de Sinais Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados 4 Teoria de Compressive Sensing Trabalhos Futuros 5 Resultados 6 Trabalhos Futuros 40 Trabalhos Futuros “Compressive Sensing” Compressão de Imagens Representação de Sinais • Norma Total-Variation Introdução a Compressive Sensing • Alternativas para Noiselets Teoria de Compressive Sensing • Wavelets Biortogonais • Particionamento em blocos Resultados Trabalhos Futuros 41 “Compressive Sensing” Compressão de Imagens Representação de Sinais Obrigada pela Atenção! Introdução a Compressive Sensing Teoria de Compressive Sensing Resultados Trabalhos Futuros 42