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.