Download Análisis a-priori del algoritmo de convolución bidimensional

MEMORIAS DEL PRIMER CONCURSO DE INVESTIGACIÓN, DESARROLLO E INNOVACIÓN TECNOLÓGICA IDIT 2012
13
Análisis a-priori del algoritmo de
convolución bidimensional aplicado a
imágenes biomédicas.
V. D. Sánchez N1
Resumen— La convolución bidimensional es una técnica de
filtrado de imágenes ampliamente utilizada en el área biomédica
ya que permite filtrar o eliminar elementos no necesarios en un
diagnóstico. Su aplicación práctica lleva implícito un costo
computacional el cual denota la eficiencia del algoritmo. En este
trabajo se llevara a cabo el análisis de complejidad a-priori con
el objetivo ver que tan eficiente desde el punto de vista de
complejidad es la convolución en imágenes biomédicas.
I.
mezcla de colores y su valor en RGB(Red Green Blue) o en
escala de grises. Se puede ejemplificar con la siguiente
matriz Figura1 de 20x15, la cual es una representación de
una imagen.
INTRODUCCIÓN
La imagenología médica permite un mejor diagnostico por
medio de diversos aparatos, estas imágenes pueden ser
filtradas de diferentes formas, en este caso, la convolución
nos permite por medio de máscaras filtrar la imagen para
resaltar ciertos parámetros que permitan un mejor
diagnóstico en este caso analizaremos la extracción de rasgos
a ciertas imágenes.
En la actualidad, se usa este filtrado para encontrar fisuras
minúsculas debidas al esfuerzo, esto en los huesos puede
traer consecuencias graves si no se detectan a tiempo. Uno
de estos modelos es el de Olsen et al [1], el cual propone que
por medio de la convolución se encuentra un patrón en las
minúsculas fisuras de los huesos. Este modelo solo la aplica
para encontrar ciertas fisuras, más no muestra el costo
computacional que tuvo la aplicación.
En nuestro caso ocuparemos la convolución para extraer
rasgos y encontrar la complejidad en este algoritmo. Aquí se
presentara una propuesta a la solución de la convolución
bidimensional como un análisis a-priori del algoritmo
aplicado.
II. CONCEPTOS BASICOS
II.1 Representación de una imagen a una matriz
Una imagen se puede representar por medio de una matriz,
ya que está compuesta puesta por pixeles (elemento de
imagen), cada pixel se puede codificar mediante un byte es
decir 8 bits, quiere decir que se tendrán 28 variaciones,
estas variaciones cambian según el contenido en bits de una
imagen(calidad de imagen). Estos valores dependerán de la
Víctor Daniel Sánchez Nava(1) pertenece a la carrera Maestría en
Ciencias área Cibernética de la Facultad de Ingeniería y realizaron el
proyecto dentro del curso(s) Análisis y diseños de algoritmos
(Email: [email protected]).
El proyecto fue asesorado por el Dr Vázquez A. Roberto
El autor agradece al: CONACYT(Consejo Nacional de Ciencia y
Tecnología.
Figura1.Representación de una imagen en su forma matricial
II.2 Concepto de convolución bidimensional
La convolución bidimensional [2] es una operación de dos
matrices que permite cambiar el contenido de pixeles por
medio de una filtro mascara, el filtro máscara utiliza el
concepto de vecindad es decir cambiar el contenido de
pixeles en el punto medio de la matriz mascara, la cual tiene
dimensiones NxM y ocho elementos en ella. Esto se puede
ejemplificar con el Cuadro 1 que muestra las diversas
vecindades en una matriz de convolución.
Vecindad de un
pixel
Vecindad-4 Diagonal
Vecindad de un
pixel
Vecindad-8
Vecidad de un
pixel
Vecindad 4,
Horizontal y
Vertical
Cuadro1. Vecindades de una matriz de convolución
La vecindad de 8 es la que se utilizara para la convolución
bidimensional, esta tiene la propiedad de usar los elementos
alrededor del pixel central y multiplicar ocho elementos de la
imagen con ocho elementos de la máscara que se sobre
pondrá en la imagen, cada pixel se multiplicara con otro
pixel de la máscara y se sumara con la multiplicación de los
otro 8 pixeles. La máscara recorrerá toda la imagen. Esto se
puede ejemplificar en la Figura 2.
14
MEMORIAS DEL PRIMER CONCURSO DE INVESTIGACIÓN, DESARROLLO E INNOVACIÓN TECNOLÓGICA IDIT 2012
Cotas de complejidad
El propósito de las cotas es intentar clasificar dichas
funciones de forma que se puedan comparar. Las cotas de
complejidad son:
Notación O
Dada una función f, queremos estudiar aquellas funciones g
que a lo sumo crecen tan deprisa como f.
Notación Ω
Dada una función f, queremos estudiar aquellas funciones g
que a lo sumo crecen tan lentamente como f.
Figura 2 Operación de convolución.
II.3 Definición formal de convolución.
La convolucion bidimensional se define con la siguiente
formula:
(
)
∑
∑
(
)
(
Notación Θ
Conjunto de funciones que crecen asintóticamente de la
misma forma.
De manera gráfica estas cotas se pueden ver como se
muestra en la Figura 4.
) (1)
Donde (
) es la posición de la imagen a convolucionar y
) es
( ) es el kernel de convolución y y (
la matriz imagen, el kernel de convolución será el que se
sobre pondrá como lo enseña la Figura 3. La matriz
mascara es también conocida como kernel de convolución,
este kernel desarrollara un recorrido por toda la imagen.
II.4 Concepto de eficiencia de un algoritmo.
Un algoritmo es eficiente cuando logra llegar a sus objetivos
planteados utilizando la menor cantidad de recurso (costo
computacional).
II.5 Análisis de eficiencia
El análisis de eficiencia consta de dos partes que son:
Análisis a priori.
Consiste en obtener una expresión que indique el
comportamiento del algoritmo en función de los parámetros
que influya, esta predicción del costo de este algoritmo
ayudara a evitar una implementación laboriosa. Esta
predicción se base en las operaciones aritméticas básicas que
se tenga en el algoritmo tal como asignación de puntos,
comparaciones lógicas entre otras, un buen ejemplo podría
ser:
a- - son dos operaciones básicas en lenguaje c ya que es
la asignación y la resta.
Los ciclos se cuentan por su tiempo de ejecución, por
ejemplo en el ciclo while se tiene: “while c do s end”, es:
( )
(
) ( ( )
( ))
( )
De este análisis se puede dar el mejor o el peor caso, la
diferencia de estos dos casos radica en el número de veces
que entra el algoritmo en el ciclo.
Análisis a posteriori
Se recogen estadísticas de tiempo y espacio consumidas por
el algoritmo, es necesario dar a conocer las características de
una máquina concreta, un lenguaje y un compilador.
Figura 3. Cotas de complejidad
III. ALGORITMO
Como se mencionó en la sección (II) para convolucionar se
necesita un filtro kernel y una imagen, este kernel debe
centrarse y poder así hacer el recorrido en toda la matriz
imagen, para poder colocarse en la coordenada g(p,r). Se
necesitan hacer unas modificaciones en la definición formal
en la ecuación (1).
(
)
(
)
Si se toma como
y como
y se
sustituyen en la ecuación (1) podemos reescribirla de la
siguiente manera.
Haciendo más fácil identificar la matriz kernel por lo que
nuestro algoritmo quedaría como se muestra a continuación.
(
)
∑
∑
(
)
(
)
Algoritmo 1.
for y igual a uno hasta m de la matriz imagen
for x igual a uno hasta n de la matriz imagen
for ir_n igual a uno hasta la parte m del
kernel
for jr_m igual a uno hasta la parte n del kernel
posición en x va hacer igual a x más la resta de jr_m
menos el valor medio de x
posición en y va hacer igual a y más la resta de ir_n
menos medio y
(3)
SÁNCHEZ: ANÁLISIS A-PRIORI DEL ALGORITMO DE CONVOLUCIÓN BIDIMENSIONAL
if la posición x es menor a uno o la posición en x es
mayor igual a m o la posición en y es menor a 1 o la
posición en y es mayor igual a n
entonces valor es igual a cero
si no
la posición de u va a ser igual a x más la resta de jr_m
menos el valor medio de x
la posición de v va a ser igual a y más la resta de jr_n
menos el valor medio de y
posición ux va a tomar el valor redondeado de u.
posición uy va a tomar el valor redondeado de v
imagen en la coordenada(y,x,1) va hacer igual al valor
más la imagen a convolucionar en (posVy,posUx) por el
kernel(ir_n,jr_m)
imagen en la coordenada(y,x,w) va hacer igual al valor
más la imagen a convolucionar en (posVy,posUx,2) por
el kernel(ir_n,jr_m)
imagen en la coordenada(y,x,1) va hacer igual al valor
más la imagen a convolucionar en (posVy,posUx) por el
kernel(ir_n,jr_m)
end
end
end
end
end
15
imagen(y,x,1)=valor+i(posvy,posux)*k(ir_n,jr_m); 6m
imagen(y,x,2)=valor+i(posvy,posux,2)*k(ir_n,jr_m);6m
imagen(y,x,3)=valor+i(posvy,posux,3)*k(ir_n,jr_m);6m
end
total 44m+2m+2
end
end
end
end
total44nmhu+4nhu+4hu+2u+2
La complejidad total nos da:
( )
Ahora igualando las variables de la ecuación (4) a una sola
variable
y sustituyendo en la ecuación (4)
nos da una expresión de la siguiente forma:
(5)
Ya con la ecuación (4) se tiene que evaluar en un límite,
como se definió en la sección (ii) existe un crecimiento
según f se necesita un límite para poder encontrar a que
definición de cota pertenece, definimos el límite tal que:
(6)
V. RESULTADOS
El algoritmo se implementó el lenguaje de programación de
Matlab 2010a, sobre este programa se hizo el análisis a
priori ya que como se mencionó en la Sección (II) se deben
de tomar encuentra las operaciones aritméticas y como
también se deben de tomar en cuenta los ciclos.
En el análisis a-priori consta de ir contando las operaciones
aritméticas básicas que se indicara con el número de
operaciones y los ciclos se denotaran con una letra y el
número de veces que se hace. el análisis a realizar será el
análisis del peor caso.
i_n=n;
1
i_m=m;
1
medx=f_m/2; 2
medy=f_n/2;
2
valor=0;
1
total
7
for y=1:m
total u+2u+2
for x=1:n
total h+2h+2
for ir_n=1:f_n
total n+2n+2
for jr_m=1:f_m
posx=(x+(jr_m-medx)); 3m
posy=(y+(ir_n-medy));
3m
if((posx<1)||(posx>=m)||(posy<1)||(posy>=n) 9m
valor=0;
1m
else
posu=x+(jr_m-medx); 3m
posv=y+(ir_n-medy);
3m
posux=round(posu);
2m
posvy=round(posv);
2m
el limite se divide entre el exponente más grande[2], de aquí
se puede tomar que:
( )
( )
( )
( ( ))
( )
( ( ))
( )
el limite (9) es la definición formal de la cota o, por lo tanto
esta implementación bajo un esquema de imágenes tiene este
comportamiento, lo que podemos decir que.
( )
( (
))
( )
la ecuación (10) nos dice el tipo de comportamiento de este
algoritmo, esto se puede ilustrar mejor en la figura 5.
Figura 4. Grafica de tiempo vs complejidad
Ya desarrollada el análisis a-priori se mostrara dos imágenes
las cuales se tomaron de [3] que es una tomografía en dos
dimensiones con una dimensión de 492 x 505
correspondiente a la Figura 5, y donde la Figura 6
corresponde a la figura ya convolucionada y [1] una radiogra
16
MEMORIAS DEL PRIMER CONCURSO DE INVESTIGACIÓN, DESARROLLO E INNOVACIÓN TECNOLÓGICA IDIT 2012
fía de un hueso con fisuras marcadas en color verde con una
dimensión de imagen de 74 x 83 correspondiente a la Figura
7 y la figura ya convolucionada en la Figura 8.
Figura 5
Figura 6
Figura 7
Figura 8.
En cada una de estas figuras se tuvo una convolución exitosa
que se pueden extraer los rasgos importantes como se
muestra en la figura 8.En esta imagen se extraen las fisuras
del hueso y se localizan con una mayor facilidad.
VI. CONCLUSIONES
La complejidad computacional que se obtuvo por medio del
método a-priori nos muestra una aplicación factible ya que
su comportamiento O(n4) nos da una complejidad polinomial
es la cual es una complejidad con costo computacional
aceptable. En nuestro caso en una computadora con Athlon
II nos da un resultado favorable a la hora de aplicar el
algoritmo de convolución a estas imágenes biomédicas.
Aunque se pudo implementar la complejidad se puede decir
que no es la más óptima en costo computacional, esto es una
motivación para encontrar mejores algoritmos para
convolucionar imágenes y aplicar un filtrado con mejor
resolución y de detalle. Este estudio puede ser un motivante
para encontrar una me Olsen et al [1].
REFERENCIAS
[1]
[2]
[3]
Aastrup Olsen, M. ;Hartung, D.; Busch, C.;Larsen ,R.;
“Convolution Approach for Feature Detection in Topological
Skeletons
Obtained
from
Vascular
Patterns”
Dept. of Secure Services, Center for Adv. Security Res. Darmstadt
(CASED), Darmstadt, Germany, Computational Intelligence in
Biometrics and Identity Management (CIBIM) IEEE, 2011
Paul Suetens,“Fundamentals of Medical Imaging,” Cambridge
University Press, 2009.
“Brazil Journal of Medical and Biological Research”,
http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0100879X2009000700013.
[4]
[5]
Anke Meyer-Bäse, “Pattern Recognition for Medical Imaging”.
Academic Press, Second Edition, 2003.
Herbert S. Wilf “Algorithms and Complexity”, A. K. Petrs/CRC
Press, Second Edition, 2002.