reconocimiento de bordes usando combinaciones lineales de

Resumen

La deteccion de bordes es una herramienta esencial del tratamiento digitalde imagenes, y es utilizada en una amplia gama de aplicaciones. Una clasede detector de bordes compuesto por filtros de estadısticas de orden basadosen combinaciones lineales de cuasirrangos es estudiada, extendiendo trabajosprevios al respecto. Son obtenidas expresiones para las distribuciones de estascombinaciones, y se calculan algunas de sus indicadores estadısticos comoel valor esperado y la varianza. Se presentan algunas consecuencias de laescogencia de geometrıa de ventana, ası como criterios para el diseno y unejemplo de su aplicacion.

Dedicado a la constancia, paciencia y carino de mis padres

A mi hermano, mi familia, mis amigos y mi nina por ensenarme la felicidad.

Indice general

1. Introduccion 1

2. OSEDS 3

2.1. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2. Propiedades de los Cuasirrangos . . . . . . . . . . . . . . . . . 5

2.3. Geometrıas de ventana . . . . . . . . . . . . . . . . . . . . . . 7

3. Distribucion de estadısticas de orden y combinaciones lin-eales de cuasirrangos 11

3.1. Funciones de probabilidad . . . . . . . . . . . . . . . . . . . . 12

3.2. Distribucion de estadısticas de orden . . . . . . . . . . . . . . 12

3.3. Distribucion de cuasirrangos . . . . . . . . . . . . . . . . . . . 14

3.4. Distribucion de las QLC para una ventana de tamano 5 . . . . 16

3.5. Outliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.5.1. Distribucion de la r-esima estadıstica de orden con out-liers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.5.2. Distribucion de cuasirrangos con outliers . . . . . . . . 24

3.5.3. Distribucion de las QLC para una ventana de tamano5 con outliers . . . . . . . . . . . . . . . . . . . . . . . 25

3.6. Valores Esperados y Varianzas . . . . . . . . . . . . . . . . . . 27

4. Comportamiento de los OSED en presencia de ruido 35

4.1. Determinacion del Umbral . . . . . . . . . . . . . . . . . . . . 36

0

5. Pruebas Visuales 41

5.1. Imagen sin ruido . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.2. Imagen con ruido . . . . . . . . . . . . . . . . . . . . . . . . . 44

6. Conclusiones e Investigacion Futura 50

Indice de figuras

2.1. Imagen unidimensional filtrada con una QLC . . . . . . . . . . 7

2.2. Geometrıas de ventana para tamano 5: ’+’ y ’x’ . . . . . . . . 8

2.3. No deteccion de bordes paralelos a los ejes de la ventana . . . 9

2.4. Perdida de bordes: Imagen Original . . . . . . . . . . . . . . . 9

2.5. Perdida de bordes: Geometrıa en ’x’ . . . . . . . . . . . . . . . 10

2.6. Perdida de bordes: Geometrıa en ’+’ . . . . . . . . . . . . . . 10

3.1. Posicion de las muestras para obtener la FCP de la r-esimaestadıstica de orden . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2. Posicion de las muestras para obtener la FDP de la r-esimaestadıstica de orden . . . . . . . . . . . . . . . . . . . . . . . . 13

3.3. Densidad de probabilidad 1a estadıstica de orden, distribu-ciones laplaciana y gaussiana . . . . . . . . . . . . . . . . . . . 15

3.4. Densidad de probabilidad 5a estadıstica de orden, distribu-ciones laplaciana y gaussiana . . . . . . . . . . . . . . . . . . . 16

3.5. Densidad de probabilidad Q1::5, sin outliers . . . . . . . . . . . 17

3.6. Densidad de probabilidad Q1::5, sin outliers . . . . . . . . . . . 18

3.7. Densidad de probabilidad QLC5, distribucion gaussiana . . . . 20

3.8. Densidad de probabilidad QLC5, distribucion laplaciana . . . 21

3.9. Densidad de probabilidad Q1::5, 2 outliers, H=1 . . . . . . . . 25

3.10. Densidad de probabilidad Q2::5, 2 outliers, H=1 . . . . . . . . 26

3.11. Densidad de probabilidad QLC tamano 5, con 2 outliers, H=5.Distribucion Gaussiana . . . . . . . . . . . . . . . . . . . . . . 27

2

3.12. Densidad de probabilidad QLC tamano 5, con 2 outliers, H=5.Distribucion Laplaciana . . . . . . . . . . . . . . . . . . . . . 28

3.13. Densidad de probabilidad QLC tamano 5, con 2 outliers, H=2.Distribucion Gaussiana . . . . . . . . . . . . . . . . . . . . . . 29

3.14. Densidad de probabilidad QLC tamano 5, con 2 outliers, H=2.Distribucion Laplaciana . . . . . . . . . . . . . . . . . . . . . 31

3.15. Valores Esperados QLC5,Distribucion Normal, 2 outliers . . . 32

3.16. Varianza QLC5,Distribucion Normal, 2 outliers . . . . . . . . 33

3.17. Valores Esperados QLC5,Distribucion Laplaciana, 2 outliers . 33

3.18. Varianza QLC5,Distribucion Laplaciana, 2 outliers . . . . . . 34

4.1. Efectos del ruido en el desempeno del OSED: Izquierda, ima-gen lineal con ruido. Derecha: Salida de la QLC y tres posiblesumbrales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.2. Clases de errores en que incurre el OSED en presencia de ruido 38

5.1. Pruebas: Original y α = 1, β = 0 . . . . . . . . . . . . . . . . 44

5.2. Pruebas:α = 0,5, β = 0,5 y α = 0, β = 1 . . . . . . . . . . . . 45

5.3. Pruebas: Ruido normal y α = 1, β = 0 . . . . . . . . . . . . . 46

5.4. Izquierda: Imagen + ruido normal detectada con ventana x,con α = 0, β = 1, FE = 7 % Derecha: Imagen + ruido normaldetectada con ventana x con α = 0,5, β = 0,5, FE = 0,5 % . . 47

5.5. Izquierda: Imagen + ruido normal detectada con ventana +,con α = 1, β = 0, FE = 7 % Derecha: Imagen + ruido normaldetectada con ventana +, con α = 0, β = 1, FE = 7 % . . . . 47

5.6. Pruebas: Ruido laplaciano y α = 1, β = 0 . . . . . . . . . . . . 48

5.7. Izquierda: Imagen + ruido laplaciano detectada con ventanax, con α = 0, β = 1, FE = 7 % Derecha: Imagen + ruidolaplaciano detectada con ventana x con α = 0,5, β = 0,5,FE = 0,5 % . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.8. Izquierda: Imagen + ruido laplaciano detectada con ventana+, con α = 1, β = 0, FE = 7 % Derecha: Imagen + ruidolaplaciano detectada con ventana +, con α = 0, β = 1, FE =7 % . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Indice de cuadros

3.1. Valores esperados y varianzas para la r-esima estadıstica deorden para la Distribucion Laplaciana sin outliers . . . . . . . 28

3.2. Valores esperados y varianzas para la r-esima estadıstica deorden para la Distribucion Normal sin outliers . . . . . . . . . 30

3.3. Valores Esperados y Varianzas para una QLC sin outliers, N=5 30

3.4. Valores Esperados y Varianzas para una QLC con 2 outliers,Laplaciana, N=5 . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.5. Valores Esperados y Varianzas para una QLC con 2 outliers,Gaussiana, N=5 . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.1. T0 y H0 mınimos para ME, FE < 5 %; Ruido con densidadGaussiana, N=5, L=2 . . . . . . . . . . . . . . . . . . . . . . 39

4.2. T0 y H0 mınimos para ME, FE < 5 %; Ruido con densidadLaplaciana, N=5, L=2 . . . . . . . . . . . . . . . . . . . . . . 39

Capıtulo 1

Introduccion

El problema de detectar bordes es de suma importancia en el analisisde imagenes. Clasicamente, un borde se define como un cambio abrupto odiscontinuidad en la imagen. Ası, un borde no es una entidad real sino unarelacion de cambio entre la informacion de dos zonas: una sombra y la pared,un arbol y el cielo azul, una ventana y su marco.

No obstante la aparente no realidad de los bordes, resultan ser esencialesen la decodificacion de informacion visual que realizan los humanos, puesbrindan gran cantidad de informacion sobre la forma de los objetos, porque¿De que manera podemos clasificar un objeto como un triangulo si no esobservando la forma de su borde?. Esta caracterıstica hace que la deteccionde bordes sea una herramienta de gran importancia en distintas areas de laingenierıa que trabajan con analisis visual, usandose por ejemplo para difer-enciar globulos blancos y rojos en una muestra de sangre, o para lograr queun robot reconozca un objeto que debe manipular.

La importancia que los bordes tienen en el tratamiento de imagenes hallevado al desarrollo de numerosos algoritmos y metodos que buscan unaadecuada deteccion ajustada a los requerimientos que distintas aplicacionespueden exigir. Estos algoritmos se basan en distintas cualidades que puedentener los bordes. Por ejemplo, de la definicion clasica dada se desprenden doscaracterısticas importantes: por un lado son localmente detectables, siendoposible encontrarlos observando vecindades para cada punto en la imagen,

1

IEL2-03-II-15 2

ya que si la vecindad encierra una discontinuidad considerable podemos ase-gurar que un borde fue hallado. Por otra parte, ya que son definidos comocambios abruptos, es posible utilizar algun indicador de dispersion para de-tectar su presencia. Estas dos caracterısticas en particular son las explotadaspor una clase de detectores basados en un filtro discreto de estadısticas de

Capıtulo 2

Detectores de bordes deestadısticas de orden (OSEDs)

Este capıtulo presenta la terminologıa y las definiciones basicas con las quese expone el estudio. De gran importancia son la definicion formal de OSED y lademostracion de algunas de sus propiedades que permiten que este filtro discretoreconozca las discontinuidades que deseamos llamar bordes.

Aunque la motivacion para escoger estos filtros como detectores de bordesse encuentra en el caso unidimensional, el paso a mas dimensiones se realiza connaturalidad eligiendo una geometrıa de ventana apropiada. La ultima seccion deeste capıtulo pretende evidenciar las implicaciones y limitaciones que resultan deesta eleccion.

2.1. Definiciones

Un filtro de estadısticas de orden de tamano N con coeficientes [c1, . . . , cN ],es un filtro discreto que determina su salida y = {yi} en terminos de su en-trada, x = {xi}, de la siguiente manera:

yi = [c1, . . . , cN ][xi(1), . . . , x

i(N)]

T

3

2.1. DEFINICIONESIEL2-03-II-15 4

Donde [xi(1), . . . , x

i(N)] es el vector compuesto por las muestras ordenadas

de manera ascendente (i.e. x(i) ≥ x(j) ⇔ i ≥ j) correspondientes al vectormuestreado de la senal de entrada con centro en la coordenada i. Ası, este fil-tro consiste en una ventana que recorre todas las coordenadas de una imagen,asignando como salida el producto de ciertos coeficientes con el vector orde-nado de las muestras que toma.

Asumiendo que tenemos un tamano de ventana impar (N = 2k + 1),definimos Un cuasirrango movil como un filtro de estadısticas de orden convector de coeficientes tal que cr = −1 para algun r < k + 1, cs = 1 paraalgun s > k + 1, y ci = 0, ∀i /∈ {r, s}. Para r ∈ {1, . . . , k} notamos Qr::N aun cuasirrango con cr = −1, cN−r+1 = 1.

Un Detector de bordes de estadısticas de orden (OSED) puede definirsecomo un filtro de estadısticas de orden que a su salida es comparado con unumbral, con las siguientes condiciones:

N = 2k + 1 (2.1)N

∑

i=1

ci = 0 (2.2)

N∑

i=1

|ci| = 2 (2.3)

−ci = cN−i+1 ≥ 0, i = 1, . . . , k (2.4)

ck+1 = 0 (2.5)

La condicion (2.1) pide que el tamano de la ventana sea impar, lo cuales recomendable para tener simetrıa en el comportamiento del detector. Lascondiciones (2.2), (2.3), (2.4) y (2.5) nos permiten ver que el filtro de estadısti-cas de orden asociado al OSED puede representarse como una combinacionlineal (convexa) de cuasirrangos, mas especıficamente como una combinacion

de la formak∑

i=1

κiQi::N , con:

CAPITULO 2. OSEDSIEL2-03-II-15 5

k∑

i=1

κi = 1; κi ≥ 0, ∀i ∈ {1, . . . , k}

Llamaremos QLC a una combinacion con estas condiciones.

Como fue expresado anteriormente, la salida del OSED es comparada conun umbral: si es mayor se mantiene inalterada pero si es menor la salida sehace cero. Ası, el umbral determina que cambio en la imagen merece ser con-siderado como un borde y cuales no.

2.2. Propiedades de los Cuasirrangos

Es posible considerar a los cuasirrangos como funciones de <N en <.Hacer esto permite identificar y demostrar caracterısticas que son propiasde los cuasirrangos y no dependen de la poblacion sobre la que se realice lamuestra.

Teorema 1 Qr::N , como funcion de <N en <, tiene las siguientes propiedades:

1. Homogeneidad Positiva:Si Qr::N [ζ1, . . . , ζN ] = x, entonces Qr::N [kζ1, . . . , kζN ] = |k|x, ∀k ∈ <

2. Invariantes con respecto a traslaciones iguales en todas sus compo-nentes:Si Qr::N [ζ1, . . . , ζN ] = x, entonces Qr::N [ζ1 + k, . . . , ζN + k] = x

3. Invariantes respecto a permutaciones de su argumento:Si Qr::N [ζ1, . . . , ζN ] = x, entonces Qr::N [ζσ(1), . . . , ζσ(N)] = x, para todaσ permutacion de {1, . . . , N}.

4. Si r < s, entonces Qr::N [ζ1, . . . , ζN ] ≥ Qs::N [ζ1, . . . , ζN ]

Demostracion:

Sea ρ permutacion de 1, . . . , N que ordena a ζ , es decir, tal que ζρ(i) ≥ζρ(j) ⇔ i ≥ j.

2.2. PROPIEDADES DE LOS CUASIRRANGOSIEL2-03-II-15 6

1. Si k ≥ 0, ζρ(i) ≥ ζρ(j) ⇒ kζρ(i) ≥ kζρ(j), y por lo tanto el vector ordena-do de [kζ1, . . . , kζN ] es [kζρ(1), . . . , kζρ(N)], luego Qr::N [kζ1, . . . , kζN ] =kζρ(N−r+1) − kζρ(r) = kQr::N [ζ1, . . . , ζN ] = kx = |k|x

Si k < 0, ζρ(i) ≥ ζρ(j) ⇒ kζρ(i) ≤ kζρ(j), luego el vector ordena-do de [kζ1, . . . , kζN ] es [kζρ(N), . . . , kζρ(1)], luego Qr::N [kζ1, . . . , kζN ] =kζρ(r) − kζρ(N−r+1) = k(−Qr::N [ζ1, . . . , ζN ]) = −kx = |k|x

2. ζρ(i) ≥ ζρ(j) ⇒ ζρ(i)+k ≥ ζρ(j)+k, y ası ordenamos [ζ1+k, . . . , ζN +k] co-mo [ζρ(1)+k, . . . , ζρ(N)+k], luego Qr::N [ζ1+k, . . . , ζN +k] = (ζρ(N−r+1)+k) − (ζρ(r) + k) = x

3. Es claro

4. Puesto que r < s, N − r − 1 > N − s − 1, luego ζρ(N−r−1) ≥ ζρ(N−s−1)

y −ζρ(r) ≥ −ζρ(s), de donde Qr::N ≥ Qs::N

Corolario: Las propiedades 1-3 son heredadas por las QLC.

La importancia de las propiedades anteriores no debe ser subestimada,pues son justamente las caracterısticas que habilitan a las QLC como de-tectores de bordes. La propiedad 2 hace que las QLC no sean sensibles alnivel de la senal de entrada. Ası, por ejemplo, si una QLC es pasada por unaimagen sin ruido constante a trozos, siempre sera 0 si todas sus muestras soniguales, sin importar que valor tengan. La propiedad 3 permite que se detecteel borde bien sea en un flanco de bajada o de subida, y que no importe elsentido en que se recorre la senal en la deteccion. La figura 2.1 ilustra estascaracterısticas. En la parte superior de la misma se presenta un ejemplo deimagen unidimensional que es pasada por una QLC cuya salida es mostradaen la parte inferior, y en la que se verifican las propiedades mencionadas.

La propiedad 1 sera de importancia en el momento de analizar el com-portamiento de las QLC en condiciones de ruido.


Figura 2.1: Arriba: Un ejemplo de imagen unidimensional. Abajo: La salidaal ser filtrada con una cierta QLC

2.3. Geometrıas de ventana

El modelo elegido para el desarrollo del detector es un modelo unidimen-sional, pero las imagenes a ser tratadas son bidimensionales. El paso a dosdimensiones requiere la escogencia de una geometrıa de ventana apropiadapara recorrer la imagen. Para su uso en deteccion de bordes, es convenienteque la ventana sea simetrica y de tamano impar. Varias muestras de ge-ometrıas para tamanos N=5,9,13 y 25 pueden ser encontradas en [3].En esteestudio nos centramos en ventanas de tamano N=5, que nos dan como posi-bles geometrıas simetricas las ventanas en ’+’ y en ’x’ ilustradas en la figura2.2. El aumento en el tamano de la ventana hace que menos imagenes puedancumplir la suposicion de ser constantes a trozos de orden N, pero ventanasmas grandes permiten un mayor numero de geometrıas con mayor grado desimetrıa axial

La geometrıa de ventana es responsable de lograr que el detector en elcaso bidimensional detecte los bordes de la manera adecuada como en el casounidimensional. Las imagenes tienen como dominio usual una grilla rectan-

2.3. GEOMETRIAS DE VENTANAIEL2-03-II-15 8

Figura 2.2: Geometrıas de ventana para tamano 5: ’+’ y ’x’

gular que dificulta obtener una alta simetrıa axial en la ventana, necesariapara que el comportamiento en los dos casos sea equivalente. Como conse-cuencia, el comportamiento de los cuasirrangos depende de la geometrıa deventana y la orientacion de los bordes. Las figuras 2.4, 2.5 y 2.6 muestranel comportamiento de Q1::5 y Q2::5 con las geometrıas ’+’ y ’x’ a distintasorientaciones en una imagen binaria sin ruido. En ellas se observa que parala ventana con geometrıa en ’x’, el primer cuasirrango es sensible a cambiosen cualquier direccion, mientras el segundo cuasirrango pierde toda sensibili-dad a orientaciones de 45◦ o 135◦, y es poco sensible a inclinaciones cercanasa estas. Por otra parte, si la ventana tiene geometrıa en ’+’, se encuentraque de nuevo el primer cuasirrango es sensible a cualquier direccion, pero elsegundo cuasirrango no encuentra bordes verticales ni horizontales y es pocosensible a cambios en orientaciones que se acercan a los 0◦ o 90◦. La figura 2.3aclara esta situacion. Al ser ’paralelos’ un eje de la ventana y la orientaciondel borde, el numero de outliers que se presentan alrededor del cambio essiempre 1. Ası, el valor de Q2::5 es 0, y este cuasirrango no detecta el borde.

Como es apreciable, los bordes que se pierden en la deteccion que utilizala ventana en ’x’ pueden ser reconocidos mediante el uso de la ventana en’+’, y viceversa. De esta forma, si se desea trabajar con un OSED con unaQLC5 asociada con un valor alto de la componente de Q2::5, es recomend-able utilizar como salida del filtro el maximo entre las arrojadas por ambasgeometrıas.


Figura 2.3: No deteccion de bordes paralelos a los ejes de la ventana

Figura 2.4: Imagen original

Todo lo anterior muestra que la eleccion de la geometrıa de ventana esun factor importante que depende de la orientacion de las imagenes a serreconocidas.

2.3. GEOMETRIAS DE VENTANAIEL2-03-II-15 10

Figura 2.5: Imagen filtrada con ventanas en ’x’. Arriba con Q1::5, Abajo conQ2::5

Figura 2.6: Imagen filtrada con ventanas en ’+’. Arriba con Q1::5, Abajo conQ2::5

Capıtulo 3

Distribucion de estadısticas deorden y combinaciones linealesde cuasirrangos

La deteccion de bordes juega un papel fundamental en la reconstruccion deimagenes, en particular de aquellas que han sido contaminadas con ruido, circun-stancia que se puede presentar en varias aplicaciones. Para estudiar el compor-tamiento del detector en estas condiciones, asumiremos un modelo restringido deimagen constante a trozos (de orden N), contaminada con ruido blanco aditivocon distribuciones gaussiana y laplaciana, y estudiaremos varias de sus carac-terısticas estadısticas.

Bajo estas hipotesis, una ventana de tamano n obtiene muestras independi-entes de a lo sumo dos poblaciones distribuidas en la misma familia pero condiferente media. A las componentes en minorıa de la muestra las llamaremosoutliers, y una muestra de exclusivamente una distribucion se denomina muestrasin outliers. En el caso con outliers llamaremos contraste (H) al valor absolutode la diferencia entre las medias de las dos distribuciones, y en el caso sin outliers

decimos que el contraste es cero.

En este capıtulo se presentan las distribuciones halladas para las estadısticasde orden y las QLC, con y sin outliers; se demuestran propiedades de estas dis-tribuciones y se hallan valores esperados y varianzas en algunos casos especıficos.

11

3.1. FUNCIONES DE PROBABILIDADIEL2-03-II-15 12

3.1. Funciones de probabilidad

Puesto que seran usadas a lo largo de este capıtulo, se recordaran breve-mente las propiedades de las Funciones Cumulativas de Probabilidad y de laFunciones de Densidad de Probabilidad (FDP).

Si FX es FCP (seran notadas por letras mayusculas), se tiene:

1. lımx→−∞

FX(x) = 0, y lımx→+∞

FX(x) = 1

2. FX(·) es una funcion monotona, no decreciente.

3. FX(·) es continua por la derecha.

Si fX es FDP, tenemos:

1. f(x) ≥ 0 para todo x

2.∞∫

−∞

f(x)dx = 1

Otras propiedades, extensiones a otros dominios, y varios ejemplos deutilidad se pueden encontrar en cualquier libro de probabilidad, en particu-lar en [2].

3.2. Distribucion de estadısticas de orden

Para deducir la expresion para la FCP de la r-esima estadıstica de orden,podemos observar la Fig. 3.1. En ella se muestra la recta real partida en doszonas, a la izquierda y la derecha de un punto x.

CAPITULO 3. DISTRIBUCION DE ESTADISTICAS DE ORDEN YCOMBINACIONES LINEALES DE CUASIRRANGOSIEL2-03-II-15 13

Supongamos que tenemos una ventana de tamano N, en la que cada unade sus entradas se distribuye independientemente como F. Si se desea hallarFXr

(x) = P (X(r)) ≤ x, se deben considerar los casos en que el numero demuestras menores o iguales a x sea mayor o igual a r. La independencia demuestras nos lleva a la siguiente expresion:

n∑

i=r

(

ni

)

F (x)i[1 − F (x)]n−i

Figura 3.1: Posicion de las muestras para obtener la FCP de la r-esima es-tadıstica de orden

Figura 3.2: Posicion de las muestras para obtener la FDP de la r-esima es-tadıstica de orden

Donde cada uno de los terminos de la sumatoria representa la probabili-

3.3. DISTRIBUCION DE CUASIRRANGOSIEL2-03-II-15 14

dad de que existan exactamente i muestras menores o iguales a x.

Para hallar la densidad de probabilidad correspondiente, serıa necesarioderivar la formula recientemente mostrada. Este proceso se mostrara en uncaso mas general en la seccion 3.5.1 No obstante otro camino expresado en[4] se basa en la Fig. 3.2. En ella se muestra la recta real dividida en treszonas, una de ellas de longitud dx. Al considerar el caso en el que una delas muestras ’cae’ en este intervalo y se analiza cuando dx tiende a cero seencuentra la siguiente expresion:

w(r):n(x) =

(

nr − 1

)

(

n − r + 1)

F (x)r−1[1 − F (x)]n−rf(x)

El proceso para hallar las distribuciones que en adelante consideraremosimita el que hasta aquı hemos realizado, y por lo tanto no sera repetido nue-vamente. Mostraremos graficas obtenidas para esta distribucion para N=5,valores de r de 1 y 5 y distribuciones normal y laplaciana en Fig. 3.3 y3.4

3.3. Distribucion de cuasirrangos

La determinacion de la densidad de probabilidad de un cuasirrango re-quiere como primer paso considerar la densidad conjunta de la r-esima y las-esima estadısticas de orden. Usando una tecnica similar a la descrita en laseccion anterior llegamos a la siguiente expresion:

w(r),(s):n(a, b)

=

{

C(n, r, s)F (a)r−1[F (b) − F (a)]s−r−1[1 − F (b)]n−sf(a)f(b) a ≤ b0 a > b

Con C(n, r, s) =

(

nr − 1

)

(

n − r + 1)

(

n − rn − s

)

(

s − r)


−3 −2.5 −2 −1.5 −1 −0.5 0 0.5 10

0.1

0.2

0.3

0.4

0.5

0.6

0.7

X −−−−−−−−>

Dens

idad

Densidad de Probabilidad de la 1a Estadística de Orden, N=5

laplaciananormal

Figura 3.3: Densidad de probabilidad 1a estadıstica de orden, distribucioneslaplaciana y gaussiana

Para hallar la densidad de un cuasirrango evaluada en un valor x, debemosintegrar sobre toda la region de IR2 que al representar los valores que tomanX(r) y X(s), nos dan x. Es decir, todos los valores de a y b tal que x = b− a.Esto nos lleva a la siguiente expresion que resulta de parametrizar la situaciondescrita:

wX(s)−X(r):n(x) =

∞∫

−∞

w(r),(s):n(b − x, b) db

La expresion anterior no pudo ser resuelta de forma analıtica, por lo quefue necesario recurrir a algoritmos numericos de integracion. En particularfue usada la regla de Simpson 3/8 de multiple aplicacion, que se encuen-tra descrita en [1]. Las figuras 3.5 y 3.6 muestra algunos de los resultadosobtenidos mediante este metodo.

3.4. DISTRIBUCION DE LAS QLC PARA UNA VENTANA DETAMANO 5IEL2-03-II-15 16

−1 −0.5 0 0.5 1 1.5 2 2.5 30

0.1

0.2

0.3

0.4

0.5

0.6

0.7

X −−−−−−−−>

Dens

idad

Densidad de Probabilidad de la 5a Estadística de Orden

laplaciananormal

Figura 3.4: Densidad de probabilidad 5a estadıstica de orden, distribucioneslaplaciana y gaussiana

3.4. Distribucion de las QLC para una ven-

tana de tamano 5

Hallar la densidad de probabilidad para una QLC en una ventana detamano 5 hace necesario obtener la funcion de densidad de probabilidad con-junta wX(5),X(4),X(2),X(1)

(a, b, c, d), que por comodidad sera denotada wConj4:5.

Siguiendo el proceso descrito en la seccion 3.2, encontramos que la funcionde densidad de probabilidad conjunta que estamos buscando es:

wConj4:5(a, b, c, d) =

{

5!f(a)f(b)f(c)f(d)[F (b) − F (c)] si a ≥ b ≥ c ≥ d0 dlc

Teorema 2 La expresion hallada para wConj4:5 cumple con las propiedadesde las funciones de densidad de probabilidad.

Demostracion:


0 0.5 1 1.5 2 2.5 3 3.5 4 4.50

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5Densidad de probabilidad de Q1::5, sin outliers

x −−−−−>

Dens

idad

LaplacianaNormal

Figura 3.5: Densidad de probabilidad Q1::5, sin outliers

1. Debemos evaluar la integral

∫

IR4

wConj4:5

Para desarrollarla, debemos recordar que F (x)′ = f(x), con lo que lasustitucion U(x) = Fx(x), dU

dx= fx es util en la solucion de la integral

planteada. Ası:

∫

IR4

wConj4:5 = 5!∞∫

−∞

a∫

−∞

b∫

−∞

c∫

−∞

f(a)f(b)f(c)f(d)(F (b)−F (c)) dd dc db da

Donde los lımites de integracion son consecuencia de la restriccion sobrelos valores de a,b,c y d para que la funcion no se haga 0. Entonces,∞∫

−∞

a∫

−∞

b∫

−∞

c∫

−∞

f(a)f(b)f(c)f(d)F (b) dd dc db da

=∞∫

−∞

a∫

−∞

b∫

−∞

f(a)f(b)f(c)F (c)F (b) dc db da =∞∫

−∞

a∫

−∞

fx(a)fx(b)Fx(b)3

2db da

3.4. DISTRIBUCION DE LAS QLC PARA UNA VENTANA DETAMANO 5IEL2-03-II-15 18

0 0.5 1 1.5 2 2.50

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Densidad de probabilidad de Q2::5, sin outliers

x −−−−−>

Dens

idad

LaplacianaNormal

Figura 3.6: Densidad de probabilidad Q1::5, sin outliers

=∞∫

−∞

fx(a)Fx(a)4

8da = Fx(x)5

40‖∞−∞

= 140

Y:

∞∫

−∞

a∫

−∞

b∫

−∞

c∫

−∞

f(a)f(b)f(c)f(d)F (c) dd dc db da

=∞∫

−∞

a∫

−∞

b∫

−∞

f(a)f(b)f(c)F (c)2 dc db da =∞∫

−∞

a∫

−∞

fx(a)fx(b)Fx(b)3

3db da

=∞∫

−∞

fx(a)Fx(a)4

12da = Fx(x)5

60‖∞−∞

= 160

Ası, tenemos:

∫

IR4

wConj4:5 = 5!(1

40−

1

60) = 1

2. La segunda propiedad se tiene al ser f y F positivas y la integral unfuncional lineal positivo.


Habiendo demostrado que la expresion efectivamente corresponde a unaFDP, podemos centrarnos ahora en conocer la densidad de una QLC. Tenien-do que QLC = αQ1::5+βQ2::5 = α(X(5)−X(1))+β(X(4)−X(2)), encontramosla densidad de probabilidad de una QLC en un valor real x dado, integrandoel valor de esta funcion conjunta sobre todos los valores de a, b, c y d talesque x = α(a − d) + β(b − c). Esto se puede lograr de muchas maneras, enparticular mediante la parametrizacion:

d = a +β

α(b − c) −

1

αx

Sin olvidar que este cambio de variables tiene jacobiano 1α, se obtiene

finalmente una expresion para la densidad de la QLC:

wQLC(x) =1

α

∞∫

−∞

a∫

−∞

b∫

−∞

wConj4(a, b, c, a +β

α(b − c) −

1

αx) dc db da

Como es usual,

WQLC(x) =

x∫

−∞

wQLC:5(y) dy =

x∫

0

wQLC:5(y) dy

La segunda igualdad desprendiendose de la definicion de la probabilidadconjunta que implica que las funciones de probabilidad son cero para valoresnegativos de x.

Nuevamente nos encontramos con la imposibilidad de resolver analıtica-mente las expresiones que poseemos para estas distribuciones, por lo que esnecesario apelar como anteriormente a los metodos numericos. Las Fig. 3.7 y3.8 muestran las densidades de probabilidad cuando el ruido es gaussiano ylaplaciano y para distintos valores de α y β. Los metodos numericos aunqueefectivos, tardan bastante tiempo en obtener la solucion.

3.5. OUTLIERSIEL2-03-II-15 20

1 2 3 4 5 6 7

0.1

0.2

0.3

0.4

0.5

0.6

0.7

Combinacion lineal de estadisticas de orden − Distribucion Gaussiana MU=0 SIGMA=1

X −−−−−>

Dens

idad

de

prob

abilid

ad −

−−−−

−−> Alpha = 0.25 − Beta = 0.75

Alpha = 0.5 − Beta = 0.5Alpha = 0.75 − Beta = 0.25Alpha = 1 − Beta = 0Alpha = 0 − Beta = 1

Figura 3.7: Densidad de probabilidad QLC5, distribucion gaussiana

3.5. Outliers

Una vez desarrolladas las expresiones para las funciones de probabilidaden el caso en que todas las muestras pertenecen a la misma distribucion mi-raremos el caso en que existen dos distribuciones de probabilidad de las quese obtienen estas muestras.

Para la primera parte de nuestro desarrollo supondremos que tenemos nmuestras de las cuales m pertenecen a la distribucion F y n − m a la dis-tribucion G.

Se define la funcion δx,y : ZZ × ZZ → {0, 1} como:

δx,y =

{

0 si x < y1 si x ≥ y

Esta funcion nos sera util para abreviar la escritura de las funciones deprobabilidad desarrolladas.


Puesto que F y G son funciones de densidad de probabilidad se tiene:

1.

lımx→∞

W(r:n,m)(x) =

(

mm

) (

n − mn − m

)

= 1

lımx→−∞

W(r:n,m)(x) = 0

2. Para mostrar que es monotona creciente, hallaremos su derivada, esdecir la funcion de densidad de probabilidad y mostraremos que es nonegativa en todo real.

w(r:n,m)(x)

=m

∑

i=1

l∑

j=0

iC(i, j)f(x)F (x)i−1G(x)j [1 − F (x)]m−i[1 − G(x)]l−jδi+j,r

+m

∑

i=0

l∑

j=1

jC(i, j)g(x)F (x)iG(x)j−1[1 − F (x)]m−i[1 − G(x)]l−jδi+j,r

−

m−1∑

i=0

l∑

j=1

(m − i)C(i, j)f(x)F (x)iG(x)j [1 − F (x)]m−i−1[1 − G(x)]l−j

·δi+j,r

−

m∑

i=0

l∑

j=1

(l − j)C(i, j)g(x)F (x)iG(x)j [1 − F (x)]m−i[1 − G(x)]l−j−1

·δi+j,r

Con C(i, j) =

(

mi

) (

n − mj

)

; l = n − m

Que, mediante la sustitucion i′ − 1 = i, j′ − 1 = j y sabiendo que:

(

mi

)

i =m!i

i!(m − i)!=

m!(m − i + 1)

(i − 1)!(m − i + 1)!=

(

mi − 1

)

(m − i + 1)


Nos lleva a:

w(r:n,m)(x) =

m∑

i=0

C1(n, m, i, r)g(x)F (x)iG(x)r−i−1[1 − F (x)]m−i[1 − G(x)]n−m−r+i

·δn−m,r−iδr−i,0

+n−m∑

i=0

C2(n, m, j, r)f(x)F (x)r−j−1G(x)j [1 − F (x)]m−r+j [1 − G(x)]n−m−j

·δm,r−jδr−j,0

Con:

C1(n, m, i, r) =

(

mi

) (

n − mr − i

)

(r − i)

C2(n, m, j, r) =

(

mr − j

) (

n − mj

)

(r − j)

Puesto que f , g, F , G y los coeficientes C1 y C2 son no negativos,tambien lo es la funcion de densidad. Esto implica que la funcion cu-mulativa es monotona no decreciente.

3. La continuidad por la derecha se tiene por ser F y G continuas por laderecha y el producto, la suma y la exponenciacion funciones continuas.

Corolario: Wr:n es una Funcion Cumulativa de Probabilidad

Demostracion:

Tomando n=m tenemos:

W(r:n,n)(x) =

n∑

i=0

(

ni

)

F (x)i[1−F (x)]n−iδi,r =

n∑

i=r

(

ni

)

F (x)i[1−F (x)]n−i

Luego,

W(r:n,n)(x) = Wr:n(x)

Ası, el caso sin outliers se puede obtener de los resultados con outliers


3.5.2. Distribucion de cuasirrangos con outliers

Examinemos ahora el caso en que deseamos hallar la expresion para lafuncion de densidad de probabilidad conjunta de la r-esima y la s-esima es-tadısticas de orden (s ≥ r).

Definimos:

h(a, b, i, j) = F (a)iG(a)r−1−i[1 − F (b)]j [1 − G(b)]n−s−j

Entonces, la funcion de densidad de probabilidad conjunta de la r-esimay la s-esima estadısticas de orden es:

w(r),(s)(a, b)

=r−1∑

i=0

n−s∑

j=0

{C1(i, j)f(a)f(b)[F (b) − F (a)]m−i−j−2[G(b) − G(a)]s+i+j+1−m−r

δm−2,i+jδn−m,r−1−i+n−s−j

+ C2(i, j)[f(a)g(b) + f(b)g(a)][F (b) − F (a)]m−i−j−1[G(b) − G(a)]s+i+j−m−r

δm−1,i+jδn−m−1,r−1−i+n−s−j

+ C3(i, j)g(a)g(b)[F (b) − F (a)]m−i−j [G(b) − G(a)]s+i+j−m−r−1

δm,i+jδn−m−2,r−1−i+n−s−j}h(a, b, i, j)

Donde:

D(A, B, i, j, r, s) =

(

Ai

) (

Br − 1 − i

) (

A − ij

) (

B − r + 1 + in − s − j

)

C1(i, j) = m(m − 1)D(m − 2, n − m, i, j, r, s)

C2(i, j) = m(n − m)D(m − 1, n − m − 1, i, j, r, s)

C3(i, j) = (n − m)(n − m − 1)D(m, n − m − 2, i, j, r, s)

Para el caso en que b ≥ a, y cero en caso contrario. Si n = m, se puedeverificar facilmente que regresamos a la expresion para el caso de una soladistribucion (sin outliers). Las Fig. 3.9 y 3.10 muestran las graficas para lasdos distribuciones consideradas, de la densidad de Q1::5 y Q2::5 tomando dosoutliers con media 1.


0 0.5 1 1.5 2 2.5 3 3.5 4 4.50

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45Densidad de probabilidad de Q1::5, 2 outliers, H=1

x −−−−−>

Dens

idad

LaplacianaNormal

Figura 3.9: Densidad de probabilidad Q1::5, 2 outliers, H=1

3.5.3. Distribucion de las QLC para una ventana detamano 5 con outliers

Es de nuestro interes obtener expresiones para conjuntas de un mayornumero de estadısticas de orden. En este caso limitaremos nuestras expre-siones para un tamano de muestra n = 5, para el cual tenemos:

Un ”‘outlier”’:

w(1),(2),(4),(5)(d, c, b, a)

= 24{g(d)f(c)f(b)f(a)[F (b)− F (c)] + f(d)g(c)f(b)f(a)[F (b) − F (c)]

+ f(d)f(c)g(b)f(a)[F (b)− F (c)] + f(d)f(c)f(b)g(a)[F (b)− F (c)]

+ f(d)f(c)f(b)f(a)[G(b) − G(c)]}

Que si tenemos F=G nos lleva a la expresion que ya se habıa obtenidopara el caso de una sola distribucion, a saber:

w(1),(2),(4),(5)(d, c, b, a) = 120 · f(d)f(c)f(b)f(a)[F (b) − F (c)]


0 0.5 1 1.5 2 2.50

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8Densidad de probabilidad de Q2::5, 2 outliers H=1

x −−−−−>

Dens

idad

LaplacianaNormal

Figura 3.10: Densidad de probabilidad Q2::5, 2 outliers, H=1

Dos ”‘outliers”’:

w(1),(2),(4),(5)(d, c, b, a)

= 12{g(d)g(c)f(b)f(a)[F (b)− F (c)] + g(d)f(c)g(b)f(a)[F (b)− F (c)]

+ g(d)f(c)f(b)g(a)[F (b)− F (c)] + g(d)f(c)f(b)f(a)[G(b) − G(c)]

+ f(d)g(c)g(b)f(a)[F (b)− F (c)] + f(d)g(c)f(b)g(a)[F (b)− F (c)]

+ f(d)g(c)f(b)f(a)[G(b) − G(c)] + f(d)f(c)g(b)g(a)[F (b)− F (c)]

+ f(d)f(c)g(b)f(a)[G(b) − G(c)] + f(d)f(c)f(b)g(a)[G(b) − G(c)]}

Que, de nuevo, si F=G, nos lleva al caso de una sola distribucion. La de-mostracion de que estas expresiones cumplen las propiedades deseadas essemejante a la del caso sin outliers.

Resolviendo numericamente se pueden obtener graficas para estas expre-siones. En las figuras


0 1 2 3 4 5 6 7 8 9 100

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

Densidad de una QLC de tamaño 5, 2 outliers, H=5Densidad Gaussiana

X −−−−−−−−>

Dens

idad d

e pro

babil

idad −

−−−−

−−−−

>

3.6. VALORES ESPERADOS Y VARIANZASIEL2-03-II-15 28

0 1 2 3 4 5 6 7 8 9 100

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5


0 1 2 3 4 5 6 7 8 9 100

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

Densidad de una QLC de tamaño 5, 2 outliers, H=2Densidad Gaussiana

X −−−−−−−−−>

Dens

idad d

e pro

babil

idad −

−−−−

−−−>

Alpha= 0.25Alpha=0.50Alpha=0.75

Figura 3.13: Densidad de probabilidad QLC tamano 5, con 2 outliers, H=2.Distribucion Gaussiana

E(QLC) = E(α(X(5) − X(1)) + β(X(4) − X(2)))

= α(E(X(5)) − E(X(1))) + β(E(X(4)) − E(X(2)))

V ar(QLC) = V ar(α(X(5) − X(1)) + β(X(4) − X(2)))

= α2(V ar(X(5)) + V ar(X(1)) − 2Cov(X(5), X(1)))

+ β2(V ar(X(4)) + V ar(X(2)) − 2Cov(X(4), X(2)))

+ 2αβ(Cov(X(5), X(4)) + Cov(X(1), X(2))

−Cov(X(5), X(2)) − Cov(X(1), X(4)))

Donde los valores esperados y las varianzas dependen de los valores paralas estadısticas de orden. Los resultados para una QLC5 son mostrados acontinuacion. En el Cuadro 3.3 se presentan para el caso sin outliers y enlos Cuadros 3.4 y 3.5 se tienen para el caso con outliers y distribucioneslaplaciana y gaussiana respectivamente.

Los expresiones consignadas en los cuadros 3.3, 3.4 y 3.5 se usaron pararealizar las graficas que se consignan en las figuras 3.15, 3.16, 3.17 y 3.18.


Cuadro 3.2: Valores esperados y varianzas para la r-esima estadıstica de ordenpara la Distribucion Normal sin outliers

r E(X(r)) V ar(X(r))1 −1,1697 0,44762 −0,4950 0,31154 0,4051 0,31155 1,1697 0,4476

Cuadro 3.3: Valores Esperados y Varianzas para una QLC sin outliers, N=5

Distribucion E(αQ1::5 + βQ2::5) V ar(αQ1::5 + βQ2::5)Gaussiana 2,3394α + 0,9910β 0,7547α2 + 0,3309β2 + 0,4124αβLaplaciana 2,2553α + 0,8102β 1,2854α2 + 0,2880β2 + 0,5075αβ

Cuadro 3.4: Valores Esperados y Varianzas para una QLC con 2 outliers,Laplaciana, N=5

H E(αQ1::5 + βQ2::5) V ar(αQ1::5 + βQ2::5)1 2,6013α + 1,0591β 1,3255α2 + 0,3691β2 + 0,6356αβ2 3,3978α + 1,6912β 1,3859α2 + 0,5927β2 + 0,8043αβ3 4,3437α + 2,5442β 1,4145α2 + 0,8120β2 + 0,9193αβ4 5,3302α + 3,4930β 1,4233α2 + 0,9421β2 + 0,9410αβ5 6,3269α + 4,4766β 1,4356α2 + 1,0020β2 + 0,8955αβ


0 1 2 3 4 5 6 7 8 9 100

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

Densidad de una QLC de tamaño 5, 2 outliers, H=2Densidad Laplaciana

X −−−−−−−−>

Dens

idad d

e pro

babil

idad −

−−−−

−−>

Alpha= 0.25Alpha=0.50Alpha=0.75

Figura 3.14: Densidad de probabilidad QLC tamano 5, con 2 outliers, H=2.Distribucion Laplaciana

Existen algunos aspectos a resaltar de estas graficas. Como se puede apreciaren Fig. 3.15 y 3.17, el valor esperado en ambas distribuciones crece lineal-mente con α. Ası, los OSED disenados con valores mas altos de α tendransalidas con mayor intensidad. Debe resaltarse tambien que a medida que elvalor de H crece, las rectas de valor esperado tienden a volverse paralelas ya conservar la distancia entre ellas. Esto nos habla de un comportamientoasintotico del valor esperado.

Las graficas 3.16 y 3.18 muestran el comportamiento de las varianzas paralas dos distribcuiones trabajadas. En primer lugar podemos observar en estasgraficas una tendencia asintotica, lo que redunda en una acumulacion de lascurvas a medida que crece el H. Se puede observar igualmente que a medidaque el valor del contraste crece, se modifica el valor del α para el cual seencuentra su mınimo. Como fue dicho, la varianza brinda informacion acercade que tanto afecta el ruido el comprotamiento del detector, de manera quese puede esperar que el ruido afecte la menor cantidad al OSED con α = 0 sino existen outliers y de manera equivalente al detector con α = 0,5 en el casocon outliers. Estos posibles efectos del ruido sobre el OSED seran mostradosen el siguiente capıtulo.


0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10.2

0.4

0.6

0.8

1

1.2

1.4

1.6

Alpha −−−−−>

Varia

nza −

−−−−

−−>

Varianzas para una QLC vs. AlphaDistribución Laplaciana, 2 outliers

H=0 (sin out.)H=1H=2H=3H=4H=5

Figura 3.18: Varianza QLC5,Distribucion Laplaciana, 2 outliers

Capıtulo 4

Comportamiento de los OSEDen presencia de ruido

Para modelar el comportamiento de los OSED en presencia de ruido, usare-mos un modelo restringido de imagen constante a trozos contaminada con ruidoblanco aditivo con distribuciones laplaciana y gaussiana. En el capıtulo anteriorse presentaron distribuciones para la QLC5 bajo estas hipotesis. Este capıtu-lo pretende mostrar complicaciones derivadas de la presencia de ruido, como laposibilidad de cometer errores de deteccion de falso borde o de borde omitido,para desarrollar criterios para enfrentarlas, usando la informacion obtenida en elcapıtulo anterior.

El modelo de imagen constante a trozos con adicion de ruido blanco, nospermite asumir que las muestras pueden tomarse de dos distribuciones conmedias µ1 y µ2 y varianza σ. El analisis del comportamiento bajo ruido de unOSED requiere del estudio de las distribuciones de su correspondiente QLC.En el capıtulo anterior se estudio apenas un caso particular, no siendo estoun problema ya que, por fortuna, las propiedades de las QLC descritas en elcapıtulo 2 y de las funciones de probabilidad consideradas, permiten reducirel caso mas general a aquel con µ1 = 0, µ2 = H y varianza σ = 1, caso parael cual tenemos resultados. Ası, si denotamos WQLCN,L(µ1,µ2,σ) la densidad deuna cierta combinacion lineal de cuasirrangos, donde las distribuciones estandentro de las mencionadas con medias µ1, µ2 y varianza σ, tenemos:

35

4.1. DETERMINACION DEL UMBRALIEL2-03-II-15 36

WQLC5,L(µ1,µ2,σ)(x) = WQLC5,L(0,H,1)(x

σ) (4.1)

Con H =µ2 − µ1

σ

De esta forma, los resultados obtenidos en el capıtulo anterior son validosen el caso mas general. Por ejemplo, los resultados obtenidos sobre valoresesperados y varianzas aplican en todos estos casos, de manera que los valoresy comentarios realizados acerca de estos dos indicadores en la seccion 3.6deben tenerse en cuenta en el analisis del comportamiento del OSED conruido.

4.1. Determinacion del Umbral

La salida del filtro de estadısticas de orden se compara con un umbral (T)para determinar la existencia o no de borde. En el caso de una imagen sinruido, bastaba escoger un umbral con valor menor al contraste para reconoceradecuadamente un borde. Sin embargo, lo mismo no ocurre para el caso enque consideramos contaminacion con ruido. La figura 4.1 muestra una imagenlineal con ruido y su correspondiente salida al ser pasada por una ciertaQLC. Se puede escoger niveles de umbral como los enumerados del 1-3 enesta misma figura. La eleccion de los mismos puede implicar cometer errores.Umbrales muy bajos llevan a detectar falsos bordes (FE) y umbrales muyaltos a omitir bordes existentes (ME). La figura 4.2 ilustra estos errores.

Como se puede ver, determinar el valor del umbral es de gran importanciay debe hacerse buscando reducir la probabilidad de cometer cada uno deestos errores. Las probabilidades asociadas a cada error en el caso de senalcon ruido se definen como:

PFE(T ) = P (QLC5,0(µ1, µ2, σ) > T )

= 1 − WQLC5,0(µ1,µ2,σ)(T )

PME(T, H) = P (QLC5,L(µ1, µ1 + H, σ) ≤ T |L > 0)

= WQLC5,L(µ1,µ1+H,σ)(T )

CAPITULO 4. COMPORTAMIENTO DE LOS OSED EN PRESENCIADE RUIDOIEL2-03-II-15 37

0 5 10 15 20 25 30 35 400

0.5

1

1.5

2

2.5

0 5 10 15 20 25 30 35 400

0.5

1

1.5

2

2.5

2

1

3

Figura 4.1: Efectos del ruido en el desempeno del OSED: Izquierda, imagenlineal con ruido. Derecha: Salida de la QLC y tres posibles umbrales.

En virtud de la transformacion 4.1, podemos definir la probabilidad decometer cada uno de estos errores de la siguiente manera:

PFE(T ′) = P (QLC5,0(0, H, 1) > T )

= 1 − WQLC5,0(0,H,1)(T )

PME(T ′, H) = P (QLC5,L(0, H, 1) ≤ T |L > 0)

= WQLC5,L(0,H,1)(T )

Existen aplicaciones en que se desea detectar bordes con un contrasteH dado, y se deben elegir valores de α, β, T0 para la deteccion. En otras, elcontraste mınimo necesario para considerar un borde es tambien una vari-able de diseno. Ası, podemos plantear el problema de la eleccion de estosvalores como un problema de optimizacion, en que deseamos minimizar elvalor del umbral T0 (y el valor del contraste H0) para satisfacer restriccionessobre la relacion senal a ruido de la salida del detector. Consideramos que elporcentaje maximo aceptable de error, tanto de ME como de FE es de 5%,con variables de decision α, β y T0.

Dado que las probabilidades de los errores estan dadas en terminos dela funcion cumulativa de probabilidad para las combinaciones lineales decuasirrangos, tenemos tanta complejidad para tener explıcitamente estas ex-presiones como lo tuvimos para las distribuciones. Ası, es necesario aplicar


0 5 10 15 20 25 30 35 400

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

0 5 10 15 20 25 30 35 40−1

−0.8

−0.6

−0.4

−0.2

0

0.2

0.4

0.6

0.8

1

0 5 10 15 20 25 30 35 400

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2

Figura 4.2: Arriba Izquierda: Se detectan mas bordes de los existentes (FE).Arriba Derecha: No se detectan bordes (ME). Abajo: Una deteccion adecua-da.

metodos numericos de optimizacion. No obstante tenemos como inconve-niente que estos algoritmos necesitan evaluar un numero importante de ve-ces la funcion, y como fue mencionado cada evaluacion toma un considerabletiempo. Esto obliga a reducir al maximo el problema de optimizacion.

Observando la forma de las probabilidades de error, y su relacion conlas funciones cumulativas, podemos concluir que son monotonas e inyectivas.Por lo tanto, el valor mınimo de T que satisfara la restriccion es aquel que seubique justo en el valor PFE = 5 %. Por otra parte la condicion α + β = 1,puesta en el momento de definir las QLC nos permite reformular el problemacomo:

CAPITULO 4. COMPORTAMIENTO DE LOS OSED EN PRESENCIADE RUIDOIEL2-03-II-15 39

mın f(α) = PFE−1(0,05 %)

s.a α ≤ 1

α ≥ 0

Con una sola variable de diseno, a saber α. Para hallar el valor de f(α)para un α dado, se uso metodo de busqueda de punto fijo, y la optimizacionse realizo mediante el metodo de la razon aurea. Se obtuvieron resultadospara este problema para las distribuciones estudiadas. En ambos casos, elresultado de esta minimizacion arroja que la mejor opcion es con el valorα = 0. Los valores obtenidos de la optimizacion, junto con los respectivosvalores para las combinaciones α = 1 — β = 0 y α = β = 0,5 se encuentranen las tablas 4.1 y 4.2. En ellas tambien se muestran los valores de contrastemınimo para obtener un PME ≤ 5 %.

Cuadro 4.1: T0 y H0 mınimos para ME, FE < 5 %; Ruido con densidadGaussiana, N=5, L=2

α β T0 H0

0 1 2.0516 4.17970.5 0.5 3.7501 4.19481 0 3.8573 4.2239

Cuadro 4.2: T0 y H0 mınimos para ME, FE < 5 %; Ruido con densidadLaplaciana, N=5, L=2

α β T0 H0

0 1 1.8418 3.97780.5 0.5 3.3809 4.5911 0 4.3815 4.7571

Siguiendo un proceso similar se puede buscar un umbral para valoresdeseados de errores de ambos tipos. En algunos casos el sistema sera incon-sistente, y sera necesario relajar las condiciones sobre el problema.


La anterior no es la unica aproximacion posible al problema de determi-nacion de las variables de diseno. Una aproximacion mas veloz y cualitativa,aunque no por ello menos efectiva, surge de observar el comportamiento dela varianza con respecto al valor de α. Como ya fue expresado, la varianzapor ser indicador de dispersion nos da informacion valiosa. Ası, en ausenciade ouliers la menor varianza se alcanza con el valor de α = 0, dando comoresultado la posibilidad de usar valores bajos del umbral con niveles bajos deerror de FE, lo que coincide con los resultados de la optimizacion. De estaforma, si el primer criterio es reducir el valor del error de FE, una buenaeleccion resulta de tomar α = 0. Por otro lado, a medida que H crece, elmınimo de la varianza se acerca a α = 0,5, permitiendo el uso de valores deumbral mas altos con valores de error de ME aun bajos. En otras palabras, siel primer criterio es reducir el error de ME, la eleccion de α = 0,5 es correcta.Estos valores seran probados en el siguiente capıtulo.

Capıtulo 5

Pruebas Visuales

En los capıtulos previos se han desarrollado herramientas teoricas para elestudio de los OSEDs. En este capıtulo se utilizan los detectores estudiados enuna imagen, para mostrar su aplicacion y la correspondencia existente entre losresultados teoricos y la aplicacion practica. Tambien se incluye la implementaciondel algoritmo en una funcion de Matlab.

Para realizar las pruebas visuales con los OSEDs, es necesario implemen-tar primero el algoritmo correspondiente en algun lenguaje apropiado. Paraesto se eligio Matlab, por encontrarse disponible y ser bastante amigable enel manejo de las imagenes.

En primer lugar es necesario leer la imagen, es decir, obtener una matrizque la represente. Esto se puede realizar mediante la funcion imread. Unavez obtenida la matriz se realiza la deteccion que arroja una matriz que rep-resenta una imagen, que se visualiza mediante la funcion imagesc.

El algoritmo que implementa la deteccion es el siguiente:

function S=filtrorden(I,G,T,vec)

% FILTRORDEN OSED de ventana 5

%

% S=FILTRORDEN(I,G,T,VEC) esta funcion regresa

41

IEL2-03-II-15 42

% una imagen tras ser pasada por un filtro de

% estadisticas de orden con funcion una combin.

% lineal de cuasirrangos de una ventana movil

% de tama~no 5, y un umbral dado por T. Recibe

% como parametros I una imagen, G una geometria

% que puede tener valores ’+’ o ’x’, T un valor

% de umbral y VEC un vector de coeficientes de

% dos posiciones donde la i-esima posicion es

% le coeficiente para el i-esimo cuasirrango.

%tic;

if size(vec,1)==1 | size(vec,2)==1

if length(vec)==2

[fil col]=size(I);

d=zeros(5,1);

if G==’x’ % geometria en X

for i=2:(fil-1)

for j=2:(col-1)

if (i==5)

NFL=1;

end

d(1)=I(i-1,j-1);

d(2)=I(i-1,j+1);

d(3)=I(i,j);

d(4)=I(i+1,j-1);

d(5)=I(i+1,j+1);

d=d*1;

d=sort(d);

val=vec(1)*(d(5)-d(1))+vec(2)*(d(4)-d(2));

if (val<T)

S=0;

else

S=val;

end

end

end

elseif G==’+’ % geometria +

CAPITULO 5. PRUEBAS VISUALESIEL2-03-II-15 43

for i=2:(fil-1)

for j=2:(col-1)

d(1)=I(i-1,j);

d(2)=I(i,j-1);

d(3)=I(i,j);

d(4)=I(i,j+1);

d(5)=I(i+1,j);

d=sort(d);

val=vec(1)*(d(5)-d(1))+vec(2)*(d(4)-d(2));

if (val<T)

S=0;

else

S=val;

end

end

end

else

error(’La geometria escogida no es valida’);

return;

end

else

error(’El vector de coeficientes debe tener tama~no 2’);

end

else

error(’La entrada de coeficientes debe ser un vector’);

end

%toc

5.1. Imagen sin ruido

Las pruebas se realizaron sobre una imagen en escala de grises, en la quese muestra un aguila (Fig. 5.1). Las figuras 5.1 y 5.2 muestran los resultadosal utilizar un OSED con QLC dado por α = 1 β = 0 ; α = 0,5 β = 0,5 yα = 0 β = 1. Para realizar la deteccion, se escogio un valor de umbral de 25,con el fin de revelar un gran numero de detalles. Este valor se puede hacermas pequeno o mas alto de acuerdo a si se desea considerar como bordes mas

5.2. IMAGEN CON RUIDOIEL2-03-II-15 44

o menos detalles. Las graficas, ademas de mostrar que la deteccion es satis-factoria, permiten apreciar dos caracterısticas importantes desprendidas delas propiedades demostradas en el capıtulo 2. En primer lugar la intensidadde salida de los bordes detectados con OSEDs es mayor entre mas grandees el valor del coeficiente α de la QLC asociada. Segundo, los bordes detec-tados con valores mas altos de α son mas anchos. Adicionalmente se puedecomprobar que para el caso en que α = 0 en la imagen sin ruido es posibleutilizar como salida el maximo entre las salidas con ventana en ’+’ y ’x’ y deesta forma se garantiza la deteccion en todas las direcciones.

Figura 5.1: Izquierda: Imagen Original. Derecha: Imagen filtrada con OSEDde α = 1, β = 0

5.2. Imagen con ruido

La imagen del aguila se contamina con ruido blanco aditivo con distribu-ciones normal (guassiana) y laplaciana con varianza 26, como se muestra enlas figuras 5.3 y 5.6. En las figuras 5.3 y 5.4 se puede apreciar la salida trasutilizar el detector. Aunque los valores de umbral usados corresponden bajola transformacion senalada a los obtenidos en 4.1, los porcentajes de errorPFE son mayores que los previstos (7 %). Esto se debe a situaciones en lasque no se cumple el modelo por completo (por ejemplo zonas que no cumplen


Figura 5.2: Izquierda: Imagen filtrada con OSED de α = 0,5, β = 0,5.Derecha: Imagen filtrada con OSED de α = 0, β = 1

con ser constantes a trozos de orden N). Ası, existe una leve diferencia entrelos valores calculados y los valores obtenidos. Se muestra tambien una de-teccion con α = β = 0,5 y con un valor de umbral mas alto que redunda enun porcentaje de error PFE = 0,5 % Usar este valor de umbral mayor sinperder una cantidad significativa de bordes con respecto a las otras imagenesconfirma que el OSED con esta combinacion lineal permite valores altos deumbral. Ası mismo, los valores de umbral del OSED con α = 0 usado sonpequenos sin que esto represente una cantidad excesiva de ruido. Estos he-chos confirman las predicciones realizadas a traves de la optimizacion y dela observacion del comportamiento de la varianza.

En estas figuras se aprecian otras caracterısticas senaladas del detectoractuando sobre una imagen con ruido: mayor intensidad y mayor ancho delos bordes con α mas grande. La deteccion con ventana en ’+’ o en ’x’ es a lavista semejante salvo por algunas zonas donde el borde es menos claro paravalores en que β 6= 0.En las figuras 5.6 y 5.7 se encuentran las ilustracionespara la imagen contaminada con ruido laplaciano y la deteccion con algunosOSEDs. Las observaciones hechas para el caso del ruido normal son de nuevopertinentes.


En general, las imagenes muestran que el detector puede filtrar gran partedel ruido con valores apropiados de umbral y si existe un nivel de contrastesuficientemente alto en la imagen sera capaz de detectar los contornos desea-dos. El tiempo de deteccion para esta imagen de 350x350 es de 5.7 segundosen un procesador AMD Athlon de 800MHz.

Figura 5.3: Izquierda: Imagen del aguila contaminada con ruido normal devarianza 26 Derecha: Imagen + ruido normal detectada ventana en x conα = 1, β = 0, FE = 7 %


Figura 5.4: Izquierda: Imagen + ruido normal detectada con ventana x, conα = 0, β = 1, FE = 7 % Derecha: Imagen + ruido normal detectada conventana x con α = 0,5, β = 0,5, FE = 0,5 %

Figura 5.5: Izquierda: Imagen + ruido normal detectada con ventana +, conα = 1, β = 0, FE = 7 % Derecha: Imagen + ruido normal detectada conventana +, con α = 0, β = 1, FE = 7 %


Figura 5.6: Izquierda: Imagen del aguila contaminada con ruido laplacianode varianza 26(/255) Derecha: Imagen + ruido laplaciano detectada ventanaen x con α = 1, β = 0, FE = 7 %

Figura 5.7: Izquierda: Imagen + ruido laplaciano detectada con ventana x,con α = 0, β = 1, FE = 7 % Derecha: Imagen + ruido laplaciano detectadacon ventana x con α = 0,5, β = 0,5, FE = 0,5 %


Figura 5.8: Izquierda: Imagen + ruido laplaciano detectada con ventana +,con α = 1, β = 0, FE = 7 % Derecha: Imagen + ruido laplaciano detectadacon ventana +, con α = 0, β = 1, FE = 7 %

Capıtulo 6

Conclusiones e InvestigacionFutura

Trabajos previos habıan estudiado la deteccion de bordes por medio deOSED’s, usando cuasirrangos simples. Extender el trabajo a detectores queusan QLC plantea el compromiso entre el numero de casos que se consid-eran y el alcance teorico para cada caso. Este trabajo decide centrarse enlas QLC5 para lograr un mayor numero de resultados teoricos que incluyenla obtencion de distribuciones, valores esperados, varianzas y consideracionessobre la eleccion de umbral; todas estas caracterısticas mostraron no ser solu-cionables por metodos analıticos como era la intencion inicial, requiriendo eluso de metodos numericos y de la aplicacion de diversas propiedades.

El trabajo realizado brinda herramientas que amplıan las posibilidades dediseno de los OSEDs en el caso de las ventanas de tamano 5, para conseguircualidades como niveles de senal a ruido, contraste a detectar e intensidad dela salida, que pueden acomodarse a los requerimientos de la aplicacion quelos use. Lo anterior brinda a los OSEDs bastante flexibilidad siendo facilesde implementar y relativamente rapidos.

El comportamiento de los OSED en imagenes contaminadas con ruidoes relativamente satisfactorio, pero su desempeno depende del nivel de con-traste de la imagen con respecto a la varianza del ruido contaminante. Si setene una razon adecuada, se podran tener errores con probabilidades bajas

50

CAPITULO 6. CONCLUSIONES E INVESTIGACION FUTURAIEL2-03-II-15 51

de ocurrencia, niveles de intensidad y localizacion satisfactorios. Estas carac-terısticas fueron comprobadas por medio de una prueba de desempeno visual.

Mejorar estas prestaciones es un reto en adelante. La experiencia rela-cionada con la complejidad de las expresiones muestra que estudiar el caso decombinaciones lineales de cuasirrangos para casos de mayor tamano solo es re-comendable si se logran obtener expresiones solucionables analıticamente quepermitan establecer generalizaciones y mejorar algoritmos de optimizacion.Mas interesante y de alcance mas proximo puede resultar estudiar modifica-ciones en las definiciones iniciales, por ejemplo considerando combinacioneslineales no positivas.

Bibliografıa

[1] S. Chapra and R. Canale. Numerical Methods for engineers. McGraw-Hill, 3rd edition, 1998.

[2] A. Mood, F. Graybill, and D. Boes. Introduction to the theory of statistics.McGraw-Hill International Editions, 3rd edition, 1974.

[3] A. Restrepo, G. Hincapie, and A. Parra. On the detection of edges usingorder statistics filters. Procs. of the First IEEE Int. Conf. on ImageProcessing.

[4] A. Restrepo, A.Naranjo, M. Valderrama, M. Daniels, and R. De la Vega.Designing OSED’s (Order Statistics Edge Detectors). Int. Conf. on ImageProcessing.

52

reconocimiento de bordes usando combinaciones lineales de

Documents