Embed Size (px)
Citation preview
Deteccion de Cavidades Circulares en Imagenes
Ecograficas.
Monografıa de Tratamiento Estadıstico de Senales
Gonzalo SanguinettiCI: 3083574-2
Facultad de IngenierıaUniversidad de la RepublicaEmail: [email protected]
20 de julio de 2005
Resumen
La segmentacion en ecografıas es muchas veces difıcil de implementardebido al ruido que presentan este tipo de imagenes. Por otro lado son unmetodo economico, relativamente sencillo y practicamente no intrusivo deobtener imagenes biologicas, lo que las hace atractivas en muchas apli-caciones. Es por ello que existen un sinnumero de implementaciones desegmentacion automatica de ecografıas sobre todo aplicadas al tratamien-to de imagenes medicas en donde se detectan cavidades. Una de esastecnicas es el algoritmo PDAF que describiremos en esta monografıa.
1
Indice
1. Introduccion 2
2. El algoritmo PDAF 32.1. Descripcion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2. Resumen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Implementacion 63.1. STAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.2. PDAF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4. Analisis 94.1. Numero de rayos . . . . . . . . . . . . . . . . . . . . . . . . . . . 104.2. Numero de candidatos a bordes . . . . . . . . . . . . . . . . . . . 114.3. Filtro detector de bordes . . . . . . . . . . . . . . . . . . . . . . . 124.4. Varianza del ruido de prediccion . . . . . . . . . . . . . . . . . . 134.5. Varianza del ruido de deteccion de bordes . . . . . . . . . . . . . 13
5. Testeo 14
6. Conclusiones 16
1
1. Introduccion
La segmentacion de imagenes medicas es una de las aplicaciones mas intere-santes del procesamiento de imagenes y en los ultimos anos ha adquirido muchaimportancia. Estas segmentaciones brindan una plataforma estandar para de-tectar y medir tumores, reconstruir modelos anatomicos en tres dimensioneso ayudar a realizar cirugıas asistidas por computadora. Muchos tipos de seg-mentacines, especialmente en imagenes de ultrasonido han sido propuestos. Sinembargo, en la mayorıa de los casos, los resultados no son demasiado buenos.Esto se debe en gran parte a la componente de ruido que poseen ecografıas,caracterıstica intrınseca del metodo.
Esta monografıa intenta analizar el desempeno de un algoritmo de deteccionde cavidades circulares en ecografıas presentado en el artıculo [1]. El mismo poseecomo cualidad interesante el hecho de que funciona en tiempo real. Ademas, nonecesita ser asistido como otros algoritmos y se puede lograr que funcione demanera automatica tan solo indicando (o detectando si se posee un algoritmo)un punto interior a la cavidad. Osea, no necesita una condicion inicial cercanaa la solucion como la mayorıa de los metodos de segmentacion.
La idea del algoritmo se basa en el funcionamiento de un radar. Se diparanrayos equiespaciados desde un punto semilla y sobre los rayos se detectan can-didatos a borde. Luego se elige de manera inteligente, teniendo en cuenta unmodelo y los datos de rayos vecinos, un punto frontera por cada rayo. Estaselecciones se hacen mediante un filtro de Kalman modificado.
La monografıa esta organizada de la siguiente manera: en la Seccion 2 de-scribimos el funcionamiento del algoritmo. En la Seccion 3 se comenta comofue implementado y la Seccion 4 analiza que tan robusto es frente a variacionesen algunos de sus parametros. En la Seccion 5 se muestran resultados sobreimagenes reales y las conclusiones se expresan en la Seccion 6.
2
2. El algoritmo PDAF
En esta seccion intentaremos explicar como funciona el algoritmo PDAF1 otambien llamado Star-Kalman (Estrella de Kalman). El proposito del mismo essegmentar una cavidad aproximadamente circular.
2.1. Descripcion
Consideremos un punto semilla que se encuentre proximo al centro de la cavi-dad. Desde allı disparamos Nr rayos equiespaciados que atraviesen la frontera.Equiespaciados significa que el angulo que forman dos rayos consecutivos entresı es constante. Si llamamos θk al angulo que forma el rayo k con la horizontal,luego:
θk+1 = θk +2π
Nr(1)
d(k|k-1)
d(k-1|k-1)
candidato a frontera
semilla
frontera de
la cavidad
frontera estimada
r (k)i
Figura 1: Esquema del Algoritmo Star Kalmann
Sea d(k) la distancia desde la frontera al punto semilla. A d(k) lo modelamoscomo la trayectoria de un objeto que se mueve de forma randomica. Asumamospor simplicidad que la dinamica del objeto esta gobernada por el siguiente mod-elo:
d(k + 1) = d(k) + ξ(k) (2)
donde la secuencia ξ(k) tiene propiedades de Rudio Gaussiano Blanco. Estemodelo es adecuado para un contorno con forma aproximadamente circular, sinembargo, el mismo se puede cambiar por uno mas adecuado al problema que sequiera resolver.
1Probabilistic Data Association Filter
3
El paso siguiente es encontrar Nc candidatos a frontera. Para ello se utilizaun filtro detector de bordes unidimesional aplicado a lo largo de cada uno de losrayos. Se espera que el filtro devuelva puntos del contorno que se quiere detectarjunto con otras falsas alarmas.
Como detector de bordes utilizaremos el siguiente filtro:
Fedge(r, θ) =13{I(r + 2∆r, θ) + I(r + ∆r, θ) + I(r+, θ)− I(r −∆r, θ)
−I(r − 2∆r, θ)− I(r − 3∆r, θ)} (255− I(r, 0))n (3)
donde:
θ es el angulo que forma el rayo con la horizontal.
r es la distancia al centro a lo largo de un rayo.
∆r es el incremento diferencial radial.
I(r, θ) es el nivel local de gris de la imagen en el punto determinado porlas coordenadas polares descritas arriba.
El filtro sera aplicado en el rango de valores que se encuentra a una distanciaal centro entre Lmın y Lmax.
Los autores del artıculo recomiendan ademas utilizar n = 2, ya que con el selogran mejores resultados para imagenes de ultrasonido codificadas en 8 bits.
La medicion del borde la llamaremos z(k) y esta dada por:
z(k) = d(k) + φ(k) (4)
con φ(k) una secuencia de ruido gausiano blanco.
Las senales aleatorias ξ(k) y φ(k) son caracterizadas por sus matrices decovarianza Q(k) y R(k) respectivamente. ξ(k) permite un desvıo randomico delmodelo, mientras que φ(k) representa el error en el algoritmo de deteccion debordes.
El estado del filtro d(k−1|k−1) en la iteracion k−1 es el punto estimado dela frontera a lo largo del rayo k−1. Usando este estado y el modelo de transicion(2), el radio de la frontera en la siguiente iteracion se puede predecir como:
d(k|k − 1) = d(k − 1|k − 1) (5)
La extraccion de la frontera se realiza de forma recursiva utilizando un filtrode Kalman modificado. Los candidatos a puntos frontera en la iteracion k seutilizan para actualizar el estimador de la siguiente manera:
d(k|k) = d(k|k − 1) + W (k)(z(k)− d(k|k − 1)) (6)
donde W (k) es la ganancia del filtro de Kalman.
4
Notar que a diferencia del problema de estimacion estandar, hay mas de unamedida de las cuales solamente una sera considerada.
Luego, la medicion z(k) se define como:
z(k) =Nc∑
i=1
r1(k)βi (7)
Los βi son factores de peso determinados por la confianza de cada puntocandidato a frontera i en el rayo k.
Los factores de peso βi los calculamos asumiendo que el punto frontera tieneuna distribucion normal de media d (k|k − 1). Las magnitudes de los bordes seincluyen tambien en el calculo de los βi de forma tal que el borde con mayormagnitud recibe mayor peso. Luego, la fomula para calcular los βi queda:
βi =pi(k)∑i
pi(k)(8)
donde:
pi(k) =
(Fedge(ri(k), θk)
)2
√2πS(k)
e−(ri(k)−d(k|k−1))2
2S(k) (9)
S(k) es la incertidumbre de la prediccion del borde.
2.2. Resumen
La siguiente formulacion recursiva resume el metodo:
1. Predecir la ubicacion de la frontera:
d (k|k − 1) = d (k − 1|k − 1) (10)
2. Actualizar la incertidumbre de prediccion del paso:
P (k|k − 1) = P (k − 1|k − 1) + Q(k − 1) (11)
3. Calcular la incertidumbre de la prediccion del borde:
S (k) = P (k|k − 1) + R(k) (12)
4. Calcular la ganancia del filtro:
W (k) = P (k|k − 1)S−1(k) (13)
5. Utilizar las equaciones (6) a (9) para estimar el radio de la frontera:
d (k|k) = d (k|k − 1) + W (k)(z(k)− d (k|k − 1)
)(14)
6. Calcular la incertidumbre de la prediccion:
P (k|k) = (1−W (k))P (k|k − 1) + W (k)2(
Nr∑
i
βi(k)ri(k)2 − z(k)2)
(15)
5
3. Implementacion
El algoritmo descrito en la seccion anterior fue implementado en MatLab.En esta seccion comentaremos algunos detalles de esta implementacion.
El algoritmo consta de dos etapas muy independientes:
1. El diparo de los rayos equiespaciados y la deteccion de los candidatos aborde sobre cada uno de los mismos. Llamaremos a esta etapa STAR.
2. El filtro de Kalman modificado para estimar la trayectoria del punto. Nosreferiremos a esta segunda etapa como PDAF.
Como ayuda para la implementacion se utilizo la imagen sintetica que semuestra en la figura 2, en donde se aprecia una cavidad aproximadamente cir-cular y una textura similar a una ecografıa.
Figura 2: Imagen sintetica utilizada para probar la implementacion.
6
3.1. STAR
El punto semilla Xo (punto desde donde se disparan las rayos) es indicadomanualmente ası como el radio maximo de los rayos (Lmax). Como radio mınimo(Lmın) se eligio un cuarto del radio maximo, pero este valor es configurable.
Otros parametros configurables son:
Nr, la cantidad de rayos equiespaciados.
Nc, la cantidad de candidatos a borde sobre cada rayo.
Como analizaremos mas adelante estos dos ultimos parametros son bastanteinfluyentes en la performance del algoritmo, tanto en velocidad como resultados.
Figura 3: Nr = 64, Nc = 16 con detector de bordes positivos
En la figura 3 se observa la imagen de prueba con los rayos dibujados sobreella y luego los candidatos a borde obtenidos.
Para la imagen anterior se utilizo como detector de bordes un filtro que solotoma en cuenta los cambio de positivos (de negro a blanco), y es este filtro elque utilizaremos en la mayorıa de los ejemplos que probaremos mas adelante.
7
3.2. PDAF
Esta etapa recibe como entrada vectores con las distancias al centro o puntosemilla de los candidatos a bordes y otro vector con los pesos correspondientesde los bordes detectados.
Para evitar problemas de inicializacion aplicamos el filtro de manera circularsobre los rayos con el objetivo de lograr una trayectoria estable.
Los parametros que debemos configurar son:
Q, varianza del ruido de prediccion.
R, varianza del ruido de deteccion de bordes.
El resultado de aplicar el algoritmo PDAF sobre la imagen de prueba semuestra en la figura 4, en donde se puede observar una segmentacion bastanterazonable de la cavidad.
Figura 4: Q = 10, R = 10
8
4. Analisis
En esta seccion veremos se desempena el algoritmo Star-Kalman al variaralgunos de sus parametros y analizaremos que tan robusto es el mismo frente aellos. Los valores por defecto de los parametros son los indicados en la seccionanterior.
Los parametros que analizaremos son:
Numero de rayos.
Numero de candidatos a bordes.
Filtro detector de bordes.
Varianza del ruido de prediccion.
Varianza del ruido de deteccion de bordes.
9
4.1. Numero de rayos
Probamos el algoritmo PDAF variando la cantidad de rayos Nr y dejandolos demas paramtro constantes. Los valores de Nr elegidos son 16, 64, y 256.Los resultados se aprecian en las figura 5.
Figura 5: Variacion en la cantidad de rayos: Nr = 16, 64, 256
Los tiempos que demoro cada una de las corridas fueron2:
Numero de Rayos 16 64 256Tiempo (segundos) 0.6610 0.8210 1.5720
Como era de esperar los resultados mejoran considerablemente al ir aumen-tando la cantidad de rayos, pero esto se da no solo por el detalle sino porque elfiltro PDAF se desempena mejor. Observar que los bordes predecidos se ubicanmas cercanos a la frontera. Por otro lado los tiempos no aumentan demasiadoal considerar mas rayos.
2Los tiempos fueron medidos con el algoritmo corriendo en Matlab R13 en un procesadorPentium Centrino de 1.5 Ghz con 512 Mb de memoria RAM
10
4.2. Numero de candidatos a bordes
Veremos ahora como se comporta el algoritmo si variamos la cantidad decandidatos a bordes Nc. Probamos los siguientes valores de Nc: 1, 4, 16, 64. Losresultados obtenidos se observan en la figura 6.
Figura 6: Variacion en la cantidad de candidatos a borde: Nc = 1, 4, 16, 64
Los tiempos que demoro cada una de las corridas fueron:
Nc 1 4 16 64Tiempo (segundos) 0.7810 0.7810 0.8110 0.9010
Se observa que si tomamos poca cantidad de candidatos el algoritmo espoco robusto frente a falsas alarmas de bordes detectados y corro riesgo de con-fundirme. Si en cambio tomamos demasiados candidatos se obtiene una imagendemasiado suavizada. Un valor intermedio parece lo mas razonable. El tiempoque demora el algoritmo practicamente no depende de la cantidad de candidatoselegida.
11
4.3. Filtro detector de bordes
Otra variante que puede tener el algoritmo PDAF es el filtro de bordesutilizado. Como ya mencionamos, hasta ahora hemos trabajado con un filtrodetector de bordes positivo, ya que se adapta bastante bien a nuestro proble-ma de detectar cavidades en imagenes ecograficas. Sin embargo, el algoritmoperfectamente puede ser utilizado en otro tipo de imagenes adaptando el filtroa las mismas. Otra opcion serıa implementarlo con un detector de bordes masgeneral que por ejemplo detecte tanto cambios positivos como negativos y con-fiar en que a pesar de las falsas alarmas igual se va a desempenar correctamente.
Observemos que pasa si utilizamos un detector de bordes mas general ennuestra imagen de prueba en la figura .
Figura 7: Star-Kalman con un filtro detector de bordes tanto positivo comonegativos.
Claramente los resultados empeoran, a cambio de lograr mas generalidad.
12
4.4. Varianza del ruido de prediccion
Veremos ahora como se comporta el filtro al ir aumentando la varianza delruido de prediccion Q. Para ello consideraremos valores de Q iguales a 0.1, 1,10, 100.
Figura 8: Distintas varianzas del ruido de prediccion, Q = 0,1, 1, 10, 100
Como se observa en la figura 9 los valores muy bajos en la prediccion tiendena hacer que tenga mucho peso el modelo, que en este caso es circular. Estoprovoca que practicamente se detecte un cırculo. Si en cambio tomamos unQ alto, no le damos importancia al modelo y podemos detectar esquinas muypronunciadas, pero corremos el riesgo de confundirnos con algun ruido cercano.
4.5. Varianza del ruido de deteccion de bordes
Idem a la parte anterior pero al variar R.
Figura 9: Distintas varianzas del ruido de deteccion de bordes, R = 0,1, 1, 10,100
En esta parte ocurre un efecto tipo pasabajos con un R alto, osea se obtieneuna curva muy suave, mientras que con un R bajo el efecto es tipo pasa alto R endonde hay cambios mas abruptos entre puntos consecutivos. El comportamientoal variar R, aunque por motivos distintos, es aproximadamente inverso al decambiar la varianza del ruido de prediccion.
13
5. Testeo
En esta seccion se muestran los resultados de probar el algoritmo en imagenesreales. Las imagenes seleccionadas fueron obtenidas de la base LOGIQLibrary3
que contiene una gran variedad ejemplos. Se incluyen tan solo un pequenonumero de segmentaciones tratando que las mismas difieran bastante entre el-las. Se indica debajo de figura a que zona pertenece cada una. Los resultadosobtenidos parecen ser bastante razonables.
Figura 10: Breast Cyst 1
Figura 11: RtOvary
3www.LOGIQLibrary.com
14
Figura 12: Ovarian Mass and Jugular Vein
Figura 13: Breast Cyst 2
15
6. Conclusiones
A lo largo de la monografıa se presento el analisis de un algoritmo semi-automatico de segmentacion basado en un filtro de Kalman. Los resultadosobtenidos parecen razonables pero para poder tener datos mas objetivos de-berıamos comparar su funcionamiento contra marcas realizadas por expertros.No es un problema sencillo la validacion de un algoritmo de segmentacion, peroalgunas ideas de como encararlo se pueden ver en [2].
El algoritmo estudiado, como todos, presenta tanto ventajas como desven-tajas si se lo compara frente a otros. Enumeraremos a continuacion algunas deellas:
Ventajas
• Funciona en tiempo real, a diferencia de los algoritmos basados enEDP’s, que generalmente son muy lentos.
• No necesita practicamente inicializarse, salvo por el punto semilla yel largo de los rayos. En [3], se pueden ver algunos metodos paraestimar estos de parametros.
• Se puede extender facilmente a imagenes que no sean ecograficas.
• Se puede utilizar para segmentar en video si se realiza una estimaciondel punto semilla entre cuadro y cuadro. Ver [4].
Desventajas
• Solo se permite segmentar formas aproximadamente circulares. Losautores del artıculo utlizan el PDAF junto con el algoritmo IMM4
que le permite ir cambiando el modelo y detectar esquinas o cambiosde direccion. Aun ası solo es posible detectar cavidades convexas.
• Es necesario ajustar los parametros de acuerdo al tipo imagen paralograr buenos resultados.
• No es posible incluirle otra informacion ademas de la del modelo y lade bordes, por ejemplo regiones o textura.
Respecto a la calibracion del algoritmo, los parametros mas sensibles sinduda son la varianza del ruido de prediccion y la del de deteccion de bordes. Noes facil lorgar un buen compromiso entre ellos.
A futuro queda agregarle a nuestra implementacion el algoritmo IMM y unaetapa automatica de seleccion del punto semilla.
4Interactive Multi-Model
16
Referencias
[1] M.R. Abolmaesumi, P. Sirouspour. An interacting multiple model proba-bilistic data association filter for cavity boundary extraction from ultrasoundimages. IEEE Transactions on Medical Imaging, 23:772–784, June 2004.
[2] K.H. Kaus M.R. Wells W.M. Warfield, S.K. Zou. Simultaneous validation ofimage segmentation and assessment of expert quality. IEEE InternationalSymposium on Biomedical Imaging. Proceedings., pages 94– 97, 2002.
[3] Metaxas DN. Madabhushi A. Combining low-, high-level and empirical do-main knowledge for automated segmentation of ultrasonic breast lesions.IEEE Transactions on Medical Imaging, 22:155–69, Feb 2003.
[4] M.R. Sirouspour P. Abolmaesumi and S.E. Salcudean. Real-time extrac-tion of carotid artery contours from ultrasound images. IEEE InternationalConference on Computer-Based Medical Systems, pages 181–186, June 2000.
17
