ALGORITMOS GENÉTICOS:
DETECCIÓN DE BORDES EN
IMÁGENES
Daniel Mejías Pinto
Luis Manuel Merino
Suárez
INTRODUCCIÓN



Orígenes: Darwin (Teoría de la evolución)
Aplicación de los principios en los que se
basan los procesos de la evolución natural
como reglas en el diseño de sistemas
artificiales para la resolución de problemas
Conceptos relacionados:
- Individuo -> Población
- Adaptación -> Reproducción ->
Supervivencia
DESCRIPCIÓN DEL PROBLEMA



Entrada: I, imagen de niveles de grises, con
tamaño U x V (filas,columnas) de píxeles.
Suposición: I contiene un número de píxeles
cuya intensidad relativa respecto a sus píxeles
vecinos satisface cierta condición matemática
bien definida (píxeles característicos).
Objetivo: Extraer información de I, en este
caso los bordes de los objetos que la
componen, mediante la búsqueda y marcado
de sus píxeles característicos.
DESCRIPCIÓN DE LA SOLUCIÓN

Píxel (agente) -> Vecindad
DESCRIPCIÓN DE LA SOLUCIÓN


El comportamiento de un agente vendrá dado
por el número de píxeles vecinos cuya
diferencia de contraste (nivel de gris) con éste,
esté por debajo de un umbral .
Dicho comportamiento variará en función de
que este número (el de vecinos cuya variación
de contraste está por debajo de ) esté o no
dentro de un rango =[x,y].
DESCRIPCIÓN DE LA SOLUCIÓN

Esta condición viene dada por la siguiente
expresión (1)
DESCRIPCIÓN DE LA SOLUCIÓN

Un ejemplo:
COMPORTAMIENTO DEL AGENTE

A lo largo de la evolución de un agente, esté
actuará de diferentes formas atendiendo a los
resultados obtenidos de la evaluación de la
expresión (1).
- Marcado de píxel característico
- Función de capacidad del agente
- Difusión
- Reproducción
- Vector dirección
- Desvanecimiento o muerte del agente
MARCADO DE PÍXEL
CARACTERÍSTICO

Cuando en la evaluación de (1), el resultado
está dentro del rango marcado por , el agente
ha detectado un píxel característico.
Una vez detectado, el agente procede a
marcarlo como tal, es decir, como píxel
característico.
FUNCIÓN DE CAPACIDAD DEL
AGENTE

Para su difusión y reproducción el agente
selecciona los agentes progenitores más
adecuados y copia sus direcciones (de difusión
y reproducción) para llevar a cabo estas
tareas.
Está selección se basa en la función de
capacidad, (2), de los agentes, que se define
como:
FUNCIÓN DE CAPACIDAD DEL
AGENTE
Esta función determina cuanto tarda un agente
en encontrar un píxel característico. El valor
máximo, 1, se alcanza si el agente fue
reproducido justo sobre un píxel característico.
DIFUSIÓN

Si un agente no encuentra un píxel
característico en su posición actual, éste llevará
a cabo una difusión moviéndose hacia una
nueva posición dentro de la región formada por
sus píxeles vecinos. Este comportamiento de
difusión, juega un papel fundamental en la
búsqueda de píxeles característicos.
DIFUSIÓN

La dirección de la difusión se selecciona a
través de un vector de probabilidades, donde
cada elemento representa el valor de dicha
probabilidad para cada una de las 8 posibles
direcciones. Los valores de este vector se
ajustan atendiendo a las direcciones de
difusión de los agentes progenitores al actual.
DIFUSIÓN

La longitud de la difusión es generada de
forma aleatoria dentro de los márgenes de su
región de vecindad.
REPRODUCCIÓN

Si el agente detecta un píxel característico en
su posición actual, llevará a cabo una labor de
reproducción mediante la generación de un
número finito de descendientes que se situarán
dentro de su región de vecindad en una
determinada dirección.
REPRODUCCIÓN

De nuevo la dirección vendrá determinada a
través del ya comentado vector de
probabilidades, y su longitud, aleatoria.
VECTOR DIRECCIÓN


Se trata de un vector, de tamaño 8, que
contiene la información referente a la
probabilidad de selección de cada una de las
posibles direcciones para difusión y
reproducción de un agente.
Para calcular estos valores (de actualización
constante) asociados a un determinado agente
de cierta edad, se tendrán en cuenta todos los
agentes de su misma edad y sus progenitores
que verifiquen que su función de capacidad
sea mayor que cero.
VECTOR DIRECCIÓN

Para todos los agentes seleccionados calcular:
DESVANECIMIENTO O MUERTE
DEL AGENTE

Cuando la edad del agente excede su
esperanza de vida, este dejará de buscar
píxeles característicos, y desaparecerá de su
mundo bidimensional.
DESCRIPCIÓN DEL ALGORITMO


Entrada: imagen de grises de tamaño U x V
Salida: un conjunto de píxeles característicos
de la imagen, que determinan los bordes de
sus elementos componentes.
DESCRIPCIÓN DEL ALGORITMO


Distribuir un conjunto de agentes de forma
aleatoria sobre la imagen.
Mientras que el conjunto de agentes no sea
vacío, hacer:
- Para cada uno de los agentes del conjunto:
- Actualizar los valores de probabilidad de
su vector dirección.
DESCRIPCIÓN DEL ALGORITMO
- Si se ha detectado un píxel característico,
generar la descendencia de forma
adecuada , marcar el píxel, eliminar el
agente actual y añadir los agentes
generados.
- Si no se ha detectado píxel característico:
- si la vida del agente llega a su
límite, eliminar el agente actual.
- sino, realizar la difusión adecuada
del agente y aumentar su edad.
DESCRIPCIÓN DEL ALGORITMO

El pseudocódigo de dicho algoritmo es el
siguiente:
DESCRIPCIÓN DEL ALGORITMO

Detalles de nuestro código:
- Para almacenar los agentes se ha utilizado
una pila.
- En la reproducción y en la difusión no
utilizamos vector de dirección.
(i-1,j)
(i,j-1)
Píxel (i,j)
(i+1,j)
(i,j+1)
Para no pasar dos veces
por el mismo píxel,
utilizamos una matriz de
valores lógicos.
DESCRIPCIÓN DEL ALGORITMO
Algoritmo_Genetico(.....){
//Se genera un conjunto de agentes de forma aleatoria.
while(!pila->esVacia()){
celda=pila->cima();
if(local_stimulus( ... )) //REPRODUCCIÓN
{ // PÍXEL CARACTERÍSTICO
Se marca como píxel característico.
Se genera los descendientes posibles.
Se marcan como visitados.
}else{
if(celda.life !=0){ //DIFUSIÓN
Se genera los descendientes posibles.
Se marcan como visitados.
}//en caso de =0 nada
}
}
Descargar

algoritmos genéticos: detección de bordes en imágenes