View
13
Download
0
Category
Preview:
Citation preview
Reducción del ruido de cuantificación en señales suaves usando proyecciones sobre conjuntos convexos reducibles
Luis Mancera PascualDECSAI – VIP
Luis Mancera - 07/05/2004 2
ÍNDICE
Motivación
Introducción Teórica a POCS
POCS y minimización
Ejemplos de aplicación
Luis Mancera - 07/05/2004 3
MOTIVACIÓN
Luis Mancera - 07/05/2004 4
¿QUÉ QUEREMOS HACER?
Utilizar la información a priori sobre la imagen para disminuir el ruido de cuantificación.
•Recuperar, a partir de una observación cuantificada y sin pérdida de información, la forma de la señal original.•Obtener una señal con el mínimo error promedio con respecto a la original dada la observación cuantificada.
Luis Mancera - 07/05/2004 5
CUANTIFICACIÓN (I)
El proceso de cuantificación de una imagen supone una degradación de la señal.La cuantificación introduce frecuencias espúreas que resultan en artificios yfalsos contornos molestos para lainterpretación y el proceso de lasimágenes.El proceso de descuantificación debe de realizarse sin pérdida de información.
Luis Mancera - 07/05/2004 6
CUANTIFICACIÓN (II)
Luis Mancera - 07/05/2004 7
DESCUANTIFICACIÓN COMO INTERPOLACIÓN
La descuantificación y la interpolación son operaciones ‘equivalentes’.
qi,max
qi
qi,min
Luis Mancera - 07/05/2004 8
DESCUANTIFICACIÓN COMO RESTAURACIÓN
desemborronadaemborronada
Luis Mancera - 07/05/2004 9
INTRODUCCIÓN TEÓRICA A POCS
Luis Mancera - 07/05/2004 10
CONJUNTOS CONVEXOS
[Marks97] [Marks97]
Convexo No convexo
Un conjunto A es convexo si para todo par u1 ∈ A y u2 ∈ A, se tiene que αu1 + (1 - α)u2 ∈ A para todo 0 ≤ α ≤ 1.
Luis Mancera - 07/05/2004 11
EJEMPLOS DE CONJUNTOS CONVEXOS
Limitación en espacio / frecuencia
Fase en Fourier
Subespacios vectoriales
Intervalos de cuantificación
Subconjunto de coeficientes wavelets(caso particular de subespacio vectorial)
Luis Mancera - 07/05/2004 12
PROYECCIÓN ORTOGONAL SOBRE UN CONJUNTO CONVEXO
[Marks97]
Sea A un conjunto convexo y un elemento v ∉ A, la proyección de ven A es el único elemento u ∈ A tal que la distancia euclídea entre v y u es mínima.
Luis Mancera - 07/05/2004 13
PROBLEMA DE VIABILIDAD CONVEXA
Sea (Si), i∈I una familia de conjuntos convexos cerrados, el problema de viabilidad convexa se define como:Encontrar u* ∈ S = ∩i∈I Si
[Combettes97]
La solución a muchos problemas de restauración está en encontrar solución al problema de viabilidad convexa.El uso de métodos de proyección para resolverlo data de 1933 [VonNeumann50].
Luis Mancera - 07/05/2004 14
EL MÉTODO DE PROYECCIONES ALTERNAS (I)
Sean A, B dos conjuntos convexos en el espacio H cuyos operadores de proyección ortogonal son PA, PB respectivamente. Sea u0 ∈ H:
un = (PAPB)n u0 n ∞lim un = u ∈ A∩B
En otras palabras: Proyectando alternadamente sobre dos conjuntos convexos A y B se converge a un punto en la intersección de ambos.[Youla78] aplicó este método a restauración de imágenes
Luis Mancera - 07/05/2004 15
EL MÉTODO DE PROYECCIONES ALTERNAS (II)
u0
un
B
A
[Marks97]
Luis Mancera - 07/05/2004 16
EL MÉTODO DE PROYECCIONES ALTERNAS (III)
Si los conjuntos A y B no intersecan, el método converge a un ciclo límite entre los puntos uA y uB, donde el punto uB es el más cercano en B a uA y viceversa
u0
[Marks97]uA
uB
A B
Luis Mancera - 07/05/2004 17
POCS Y MINIMIZACIÓN
Luis Mancera - 07/05/2004 18
POCS Y MINIMIZACIÓN (I)
Planteamos el siguiente problema de minimización con restricciones:
x’ = arg min C(x)s.t.
x ∈ A
Donde:A es un conjunto convexoBi = {x: C(x) ≤ λi}, con λi ∈ ℜ, i ∈ I, es otro conjunto convexo
Luis Mancera - 07/05/2004 19
POCS Y MINIMIZACIÓN (II)
ABi
x’
Luis Mancera - 07/05/2004 20
POCS Y MINIMIZACIÓN (III)
Ejemplos:
Minimizar el soporte espacial restringido a unas condiciones
Minimizar la energía a la salida de un filtro paso – alto
Limitación del espectro
Luis Mancera - 07/05/2004 21
BUSCANDO LA MÍNIMA INTERSECCIÓN
Buscamos el menor Bi que todavía tenga intersección no vacía con A. Aplicar POCS a los diferentes “tamaños” de Bi.Detectar un ciclo límite nos indica intersección vacía.Aplicar alguna optimización para converger al punto deseado.
Luis Mancera - 07/05/2004 22
OBJETIVO
Encontrar una señal lo más limitada en frecuencia posible pero todavía compatible con la señal cuantificada observada.
Luis Mancera - 07/05/2004 23
DEFINIMOS DOS CONJUNTOS CONVEXOS (I)
Q: Conjunto de señales compatibles con la señal cuantificada observada.
Es decir, aquellas que al cuantificarse dan exactamente la observación.Proyección en Q:
qi qimaxqi
min ui ujuk
Luis Mancera - 07/05/2004 24
DEFINIMOS DOS CONJUNTOS CONVEXOS (II)
Ffc: Conjunto de señales limitadas a una determinada frecuencia de corte fc.
Se asume que las señales a procesar son suaves (limitadas en frecuencia).Según el valor de fc, puede o no tener intersección no vacía con Q.Proyección en Ffc: poner a cero frecuencias mayores que fc.
Luis Mancera - 07/05/2004 25
APLICAMOS EL MÉTODO
Fω1
Fω4
Fω2
Fω3
Q
Luis Mancera - 07/05/2004 26
EJEMPLOS DE APLICACIÓN
Luis Mancera - 07/05/2004 27
EJEMPLOS DE APLICACIÓN
Señal suave unidimensional cuantificada
Señal suave bidimensional cuantificada
Imágenes emborronadas y cuantificadas:128×128 ‘einstein’256×256 ‘lena’
Ejemplo de deconvolución
Luis Mancera - 07/05/2004 28
SEÑAL SUAVE UNIDIMENSIONAL
Probamos con este ejemplo:
original cuantificada 40 niveles restaurada
PSNR: 42,40 dB 53,59 dBVmax
2
(Vmax = 20)10 · log10 <error>2
Luis Mancera - 07/05/2004 29
SEÑAL SUAVE BIDIMENSIONALImagen 2D Suave cuantificada a 8 niveles (3 bits):
original cuantificada restaurada
PSNR: 34,67 dB 58,19 dB
(Vmax = 255)
Luis Mancera - 07/05/2004 30
IMÁGENES NATURALES (I)
emborronadagaussiano σ = 4
cuantificada4 bits
restaurada
PSNR: 35,11 dB 41,74 dB
(Vmax = 255)
Luis Mancera - 07/05/2004 31
IMÁGENES NATURALES (II)
emborronadagaussiano σ = 4
restauradacuantificada4 bits
PSNR 4 BITS: 34,82 dB 40,51 dB(Vmax = 255)
PSNR 8 BITS: 58,93 dB 60,83 dB
Luis Mancera - 07/05/2004 32
DESEMBORRONAMIENTO (I)
Aplicación de mejora del resultado de la deconvolución como ejemplo de uso de la descuantificación
Se ha usado el algoritmo de desemborronamiento regularizado de Matlab, añadiendo un ruido blanco muy pequeño.
Luis Mancera - 07/05/2004 33
CUANTIFICADA 4 BITS RESTAURADAEMBORRONADA σ = 4
DESEMBORRONADAS (v=2·10-6)
Luis Mancera - 07/05/2004 34
DECONVOLUCIÓN (III)
PSNR:(Vmax = 255)
Emborronada Cuantificada Restaurada
Emborronadas 21.37 dB 21.18 dB 21.46 dB
27.91 dBσn = 4.47 · 10-4
Desemborronadas 20.13 dBσn = 0.14
22.73 dBσn = 0.014
Luis Mancera - 07/05/2004 35
CONCLUSIONES Y FUTUROEl modelo propuesto ofrece resultados satisfactorios para recuperar señales suaves a partir de cuantificaciones
Trabajo futuro: Los resultados obtenidos son prometedoresExtender a imágenes no emborronadasProcesamiento espacialmente varianteRedefinir el conjunto convexo en el dominio de frecuencias a formas no circulares
Luis Mancera - 07/05/2004 36
REFERENCIAS (I)[Combettes97]. P.L. Combettes. Hilbertian Convex Feasibility Problem: Convergence of Projection Methods. Appl. Math. Optim. 35: 311-330. 1997.[Marks97]. Robert J. Marks. Chapter 14 -Alternating Projections onto Convex Sets. Deconvolution and Images Spectra. Ed. Peter A. Jansson. Academic Press. 1997. (http://cialab.ee.washington.edu/REPRINTS/1997-AlternatingProjections.pdf)[Gunturk02] B. K. Gunturk, Y. Altunbasak, R. Mersereau. A Multi-Frame Blocking Artifact Reduction Method for Transform-Coded Video. IEEE Trans. on Circuits and Systems for Video Technology, Vol. 12, nº 4, pp 217-227. April 2002.
Luis Mancera - 07/05/2004 37
REFERENCIAS (II)[Unal01]. G. B. Unal, A. E. Çetin. Restoration of Error-Diffused Images Using Projections Onto Convex Sets. IEEE Trans. on Image Processing, Vol. 10, nº 12, pp 1836-1841. December 2001.[VonNeumann50]. J. Von Neumann. The Geometry of Orthogonal Spaces. Princeton University Press., Princeton. New Yersey, 1950. (first appeared in 1933 lecture notes).[Youla78]. D. C. Youla. Generalized Image Restoration by the Method of Alternating Orthogonal Projections. IEEE Transactions on Circuit and Systems. Vol CAS-25, nº 9. September 1978.
Luis Mancera - 07/05/2004 38
BIBLIOGRAFÍA BÁSICA[VonNeumann50][Youla78]H. Stark, editor, “Image Recovery: Theory and Application.” Academic Press, Orlando, Florida, 1987.L. M. Bregman, “Finding the Common Point of Convex Sets by the Method of Successive Projections”. Dokl. Akud. Nauk. USSR, 162 (Nº 3), 487-490. 1965.D. C. Youla, H. Webb, “Image Restoration by Method of Convex Set Projections: Part I - Theory”, IEEE Trans. on Medical Imaging MI-1, 81-94, 1982.M. I. Sezan, H. Stark, “Image Restoration by Method of Convex Set Projections: Part II – Applications and Numerical Results”. IEEE Trans. on Medical Imaging, MI-1, 95-101, 1982.P.L. Combettes, “The Foundation of Set Theoretic Estimation”. Proc. IEEE 81, 182-208. 1993.
Recommended