extraccion interactiva de´ objetos en restauracion...

EXTRACCION INTERACTIVA DEOBJETOS EN RESTAURACION DIGITAL

DE IMAGENES

Fernanda Andrade

Universidad de las Fuerzas Armadas - ESPE

Sangolquı, Ecuador

Introduccion Segmentacion Restauracion Diseno de experimento Resultados Conclusiones

Contenido

Introduccion

Segmentacion

Restauracion

Diseno de experimento

Resultados

Conclusiones

2/67


IntroduccionExtraccion de objetos

Segmentación Restauración

3/67


IntroduccionSegmentacion de imagen

(a) Imagen (b) Imagen segmentada

Fuente: The Berkeley Segmentation Dataset

4/67


IntroduccionSegmentacion es subjetiva

(a) Imagen (b) 18 regiones (c) 7 regiones

(d) 10 regiones (e) 8 regiones

Fuente: The Berkeley Segmentation Dataset5/67


IntroduccionSegmentacion interactiva

Objetivo: dividir imagen en objeto de interes y fondo

Guía de usuario


6/67


IntroduccionRestauracion de imagen


7/67


Contenido

Introduccion

Segmentacion

Restauracion


Resultados

Conclusiones

8/67


SegmentacionSegmentacion basada en umbral

Dos regiones segun un valor deintensidad.

b(x) =

1 si i(x, y) ≥ T0 si i(x, y) < T

Figura: Histograma de una imagen enescala de grises.

Desventajas:I Sensible a variaciones de iluminacion.I No considera relacion espacial de pixeles.I Objeto y fondo deben tener diferentes intensidades.

9/67


SegmentacionSegmentacion basada en regiones

(a) Imagen (b) Primera division (c) Segunda division

Condiciones:I Pixeles con propiedad en

comun (e.g. intensidad)I Regiones con propiedades

diferentes entre ellas.

Desventajas:I No consideran

informacion de bordes.I Resultados con bordes

irregulares.10/67


SegmentacionSegmentacion basada en bordes

I Busqueda de diferencias entrepixeles.

I Operadores como Robert,Sobel, Prewitt, Canny oKrisch.

Desventajas:I Es muy sensible al ruido.I Requiere la seleccion de un

valor umbral para el borde.I No genera bordes completos

de objetos solapados.

Figura: Imagen segmentada.

Fuente: The BerkeleySegmentation Benchmark

11/67


SegmentacionSegmentacion basada en cuencas

I Imagen es considerada unasuperficie con diferentesalturas.

I Crestas: pixeles con valoresaltos de intensidad.

I Valles: pixeles con valoresbajos de intensidad.

Desventajas:I Problemas de sobre

segmentacionFuente: Pratt

12/67


SegmentacionSegmentacion basada en energıa: Active Contour

(a) Imagen (b) Primera division (c) Segunda division

Fuente: PrattEcontorno = Einterna + Eexterna

I Contorno se cine gradualmente.I Desventaja: es necesario conocer la funcion.

13/67


SegmentacionSegmentacion basada en energıa: Grafos

G = 〈E,V〉

I Nodos (V): nodos fuente s (s-node) o sumidero t (t-node).I Arcos (E): conecta nodos vecinos (n-links) y nodos con

terminales (t-links).14/67


SegmentacionSegmentacion basada en energıa: Graph Cuts

Corte mınimo (min-cut) de manera que:I t-links: elimina arcos que se conectan a S o T.I n-links: elimina arcos entre dos pixeles vecinos.

Teorema max-flow/min-cut (Ford y Fulkerson).15/67


SegmentacionSegmentacion basada en energıa: Graph Cut

I Factor de importancia relativa

E(L) = α ( R(L) ) + B(L)

I Termino regional (costo de t-links)I Termino lımite (costo de n-links)

L = l1, l2, l3, ..., li, ..., lp

16/67


SegmentacionSegmentacion basada en energıa: Graph Cut

Fuente: Boykov y JollyCosto especial (K) cuando el pixel es etiquetado por el usuario.

17/67


SegmentacionSegmentacion basada en energıa: GrabCut

I Modelamiento de color: Gaussian Mixture Model paramodelar color del fondo y del objeto de interes.

I Segmentacion por proceso iterativo de minimizacion deenergıa: Algoritmo vuelve a estimar el modelo GMMsegun se etiquetan nuevos pixeles.

I Suavizado del borde:

(a) Segmentacion (b) Trimap

Fuente: Radke18/67


SegmentacionSegmentacion basada en energıa: GrabCut

19/67


SegmentacionSegmentacion basada en energıa: OneCut

R(S) = −β||θS − θS||L1

I Nuevo termino de energıa que mide la distancia L1 entrelos modelos de apariencia del objeto y del fondo.

I Minimizacion en un solo corte.I Se reemplaza suma de pixeles por suma de bins.

20/67


SegmentacionSegmentacion basada en energıa: Random Walks

I Grafo G = 〈E,V〉I Arco epq ∈ E tiene un peso no

negativo wpq.I No evaluan las ruta mas corta,

sino las probabilidades de laruta que tome un randomwalker.

Fuente: Radke

21/67


SegmentacionOtros metodos: SIOX

I Entrada: Trimap con fondoconocido, objeto conocido yregion desconocida.

I Conversion a espacioCIELAB.

I Segmentacion por color:Modelo de color del fondoconocido.

I Refinamiento: Eliminacion deregiones pequenas.

Fuente: Radke

22/67


Contenido

Introduccion

Segmentacion

Restauracion


Resultados

Conclusiones

23/67


RestauracionRestauracion de imagenes

Fuente: Museo Nacional del Prado

24/67


RestauracionMetodos basados en ecuaciones diferenciales parciales

I Ω es el area deteriorada.I Rellenan Ω desde el borde ∂Ω hacia interior.

Fuente: Bertalmio et al.

25/67


SegmentacionMetodos basados en ecuaciones diferenciales parciales

I Laplaciano

∇(∇2I) · ∇⊥ = 0

I Direccion isotropica (cambio mınimo)

∂I∂t

= ∇(∇2I) · ∇⊥I

26/67


RestauracionMetodos basados en ecuaciones diferenciales parciales

Solucion:I Navier Stokes: Ecuacion de transporte de la teorıa de

fluidos fluidos (Bertalmio et al.)I Fast Marching Method: Metodo FMM (Fast Marching

Method) para propagar. No es iterativo (Telea).

27/67


RestauracionMetodos basados en parches

(c) Imagen original (d) Seleccion de p

Fuente: Criminisi et al.

28/67


RestauracionMetodos basados en parches

(e) Busqueda de parche Ψq⊂ Phi (f) Reemplazo de pixeles.

Fuente: Criminisi et al.

29/67


Contenido

Introduccion

Segmentacion

Restauracion


Resultados

Conclusiones

30/67


SegmentacionObjetivo

Segmentación de imagen

Determinación de eficiencia

Determinación de exactitud (regiones)

Determinación de exactitud

(bordes)

Determinación de esfuerzo

I ¿Cual es el algoritmo mas eficiente?I ¿Cual es el algoritmo mas eficaz?I ¿Cual es el algoritmo que requiere menos esfuerzo por

parte del usuario?

31/67


SegmentacionAlgoritmos

I GrabCutI OneCutI Random WalkerI SIOX

32/67


SegmentacionMetodologıa de evaluacion

ProblemasI Criterio subjetivo.I No hay estandares de evaluacion.

Existe criterio generalizado para definir una buenasegmentacion.Evaluacion supervisada: se utiliza como referenciasegmentacion manual.

33/67



Base de datos: Base de datos de Berkeley.

(a) Imagenes origina-les

(b) Seg. manual (c) Seg. manual

Fuente: The Berkeley Segmentation Dataset34/67



Base de datos: Base de datos GrabCut.

(a) Imagenes origina-les

(b) Ground truth (c) Trimaps

Fuente: Rother et al.35/67



Evaluacion con usuarios:

I Evaluacion a traves deexperimentos con usuarios.

I Requiere tiempo.I No permite reproducibilidad

de resultados.

Fuente: McGuinness et al.

36/67



Evaluacion automatizada:I Usuarios robot.I Secuencia de scribbles de acuerdo al resultado de

segmentacion previa.I No permite reproducibilidad de resultados.

37/67



I No hay entrada de usuarios.I No consideran reproducibilidad de resultados.

Se recopila base de datos: imagenes de GrabCut y scribbles.

38/67


SegmentacionMetricas

I EficienciaI EsfuerzoI Exactitud

39/67


SegmentacionExactitud basada en regiones

Segmentacion (M) Ground Truth (G)

Negativos verdaderos (TN)

Positivosfalsos (FP)

Negativosfalsos (FN)

Imagen I = PM ∪NM

Positivosverdaderos

(TP)

40/67


SegmentacionExactitud

I Exactitud de clasificacion (ACC):

ACC =TP + TN

TP + FP + TN + FNI Sensibilidad (TPR): Exhaustividad recall en ingles.

TPR =TPPG

=TP

TP + FNI Precision (PPV):

PPV =TPPM

=TP

TP + FPI Valor F (F1):

F1 = (1 + β2)PPV · TRR

β2 · PPV + TRR=

2TP2TP + FN + FP

41/67


SegmentacionExactitud basada en regiones

I Especificidad (SPC):

SPC =TNNG

=TN

TN + FPI Indice Jaccard (Jaccard):

Jaccard =|G ∩M||G ∪M|

=TP

TP + FN + FP=

F12− F1

42/67


SegmentacionEfectividad de metricas basadas en regiones

(a) Original (b) 1: Parcial (c) 2: Extendida (d) 3: Exacta

(e) Original (f) 4: Parcial (g) 5: Extendida (h) 6: Exacta

43/67


SegmentacionEfectividad de metricas basadas en regiones

Cuadro: Medidas de exactitud basadas en regiones.

Caso ACC TPR SPC Jaccard Dice1: Parcial 0.826 0.295 1.000 0.295 0.456

2: Extendida 0.797 0.975 0.738 0.543 0.7043: Exacta 0.992 0.967 1.000 0.966 0.9834: Parcial 0.940 0.324 1.000 0.324 0.490

5: Extendida 0.919 0.773 0.933 0.458 0.6286: Exacta 0.986 0.909 0.994 0.854 0.921

44/67


SegmentacionExactitud basada en bordes

(a) Ground truth (b) Mapa de bordes

45/67


SegmentacionExactitud basada en bordes

I Sensibilidad (TPR): Exhaustividad recall en ingles.

TPR =TPPG

=TP

TP + FNI Precision (PPV):

PPV =TPPM

=TP

TP + FPIdealmente Precision = 1 y Exhaustividad = 1.Curvas para observar compensacion.

46/67


SegmentacionCondiciones experimentales

I GrabCut: OpenCV C++I OneCute: OpenCV C++I Random Walks: MATLABI SIOX: JAVA

47/67


SegmentacionBase de datos

(d) Original (e) Primer conjunto (f) Segundo conjunto

48/67


RestauracionObjetivo

Relleno de imagen

Determinación de eficiencia

Análisis cuantitativo

Análisis cualitativo

¿Es necesario comparar la imagen restaurada con un fondoreal?

49/67


RestauracionAlgoritmos

I Bertalmio (Navier Stokes)I TeleaI Criminisi

50/67


RestauracionMetodologıa de evaluacion

ProblemasI Criterio subjetivo.I No hay estandares de evaluacion.I No hay criterio generalizado para definir una buena

restauracion.

Esfuerzos por realizar mediciones cuantitativas.

51/67


RestauracionCondiciones experimentales

I Bertalmio: OpenCV C++I Telea: OpenCV C++I Criminisi: MATLAB

52/67


RestauracionEvaluacion cuantitativa: metricas

I MSE:

MSE =1

mn

m−1∑y=0

n−1∑x=0

= [IO(x, y)− IR(x, y)]2

I PSNR:PSNR = 10 log10

R2

MSER = 255

53/67


RestauracionEvaluacion cualitativa

I 21 participantesI Metodologıa para medir calidad de servicio de voz (ITU-R)I Pregunta: En una calificacion de 1 a 5, ¿como calificarıa usted la

calidad de las imagenes presentadas?I Calificacion:

1. Mala2. Regular3. Buena4. Muy buena5. Excelente

54/67


RestauracionEvaluacion cualitativa: metrica

I MOS (Mean Opinion Score en ingles):

MOS =1n

n∑i=1

Si

55/67


Contenido

Introduccion

Segmentacion

Restauracion


Resultados

Conclusiones

56/67


SegmentacionEficiencia

0

10

20

30

40

50

1 5 10 15 30 50 75 100 200Iteraciones

Tie

mp

o [

s] Eficiencia

Scribbles 1Scribbles 2

(a) GrabCut

1

100

0.001 0.01 0.1 1 10 100 1000 10000Beta

Tie

mp

o [

s] Eficiencia


(b) OneCut

Figura: Tiempo promedio de ejecucion.

57/67


SegmentacionEficiencia

0.00

0.25

0.50

0.75

1.00

10 20 30 40 50 60 70 80 90 100 150 300 500

Beta

Tie

mp

o [

s]

Eficiencia


(a) Random Walks

0.00

0.25

0.50

0.75

1.00

1 5 10 20 50 75 100Size Factor

Tie

mp

o [

s] Eficiencia


(b) SIOX


58/67


SegmentacionEficacia (regiones)

0.00

0.25

0.50

0.75

1.00

1 5 10 15 30 50 75 100 200Iteraciones

Ja

cca

rd

Exactitud


(a) GrabCut

0.00

0.25

0.50

0.75

1.00

0.001 0.01 0.1 1 10 100 1000 10000

BetaJaccard

AccuracyScribbles 1Scribbles 2

(b) OneCut

Figura: Valores promedio de Jaccard.

59/67


SegmentacionEficacia (regiones)

0.00

0.25

0.50

0.75

1.00

10 20 30 40 50 60 70 80 90 100 150 300 500

Beta

Ja

cca

rd

Exactitud


(a) Random Walks

0.00

0.25

0.50

0.75

1.00

1 5 10 20 50 75 100Size Factor

Ja

cca

rd

Exactitud


(b) SIOX

Figura: Valores promedio de Jaccard.

60/67


SegmentacionEficacia (bordes)

Recall0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Pre

cis

ion

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

[0.78] Grabcut (S2)[0.81] SIOX (S2)[0.72] Onecut (S2)[0.63] RandomWalker (S2)[0.65] Grabcut (S1)[0.57] SIOX (S1)[0.43] Onecut (S1)[0.4] RandomWalker (S1)

Figura: Curvas de precision y exhaustividad.

61/67


RestauracionEficiencia

0

5

10

15

20

1 5 10 15 20 25 30 35 40 45 50Radio

Tie

mp

o [

s]

(a) Bertalmio

0

5

10

15

20

1 5 10 15 20 25 30 35 40 45 50Radio

Tie

mp

o [

s]

(b) Telea

0

50

100

150

200

9 15 21 27 33 39 41 51Parche

Tie

mp

o [

s]

(c) Criminisi


62/67


RestauracionEficacia (cualitativo)

0

1

2

3

4

Bertalmio Criminisi TeleaAlgoritmo

MO

S

Algoritmo

BertalmioCriminisiTelea

Figura: MOS de algoritmos de restauracion de imagenes.

63/67


RestauracionEficacia (cuantitativo)

18.02 18.1717.83

0

5

10

15

20

Bertalmio Criminisi Telea

PS

NR

Algoritmo

Bertalmio

Criminisi

Telea

(a) PSNR

0

500

1000

1500

2000

Bertalmio Criminisi Telea

MS

E

Canales

Canal R

Canal G

Canal B

(b) MSE

64/67


Contenido

Introduccion

Segmentacion

Restauracion


Resultados

Conclusiones

65/67


Conclusiones

I Recopilacion de base de datos para emular la intervenciondel usuario a traves de dos conjuntos de scribbles ensegmentacion.

I Indice Jaccard refleja mas exhaustivamente la exactitudbasada en regiones que otras metricas utilizadas en elestado del arte.

I Exactitud de los algoritmos de segmentacion incrementacuando se marca el objeto de interes con mayor detalle.

I Desde el punto de vista de la eficacia, GrabCut se ha erigidocomo el algoritmo mas exacto, seguido de cerca por SIOX.

I SIOX y Random Walks son los algoritmos mas eficientes,pero Random Walks es el menos exacto.

66/67


Conclusiones

I La definicion de una buena restauracion depende de lapercepcion de un observador.

I De acuerdo a los observadores, el algoritmo Criminisisupera significativamente a los resultados de Bertalmio yTelea.

I Desempeno no se registra en las metricas cuantitativas.I Algoritmos basados en ecuaciones diferenciales parciales,

de Bertalmio y Telea, son los mas eficientes.I Se requiere optimizacion de la implementacion del

algoritmo de Criminisi.

67/67

extraccion interactiva de´ objetos en restauracion...

Documents