gaussianBlur(15, 2);
grayScale();
cannyAlgorithm cpix( ~self.data, self.width, self.height, self.bpp / 8 );
cpix.AutoEdgeDetection( ~self.data, 0.2f, 0.25f );
La linea 1 es necesaria y asumo que ya tienen una funcion llamada "gaussian blur" que aplica el algoritmo gaussiano para disminuir el ruido de una imagen, si no la tienen pueden continuar , pero notaran la diferencia.
La linea 2 es necesaria, asumo que ya tienen una funcion llamada "grayscale" que convierta la imagen a escala de grises , el concepto es sencillo , gray = (r + g + b) / 3
r = g = b = gray
la linea 3 es la inicializacion del algoritmo en mi caso ~self.data es el unsigned char, self.width el ancho, self.height el alto, self.bpp / 8 los bits por pixel.
la linea 4 es iniciar la dectecion de bordes , le introduzco el unsigned char de salida , y dos valores decimales que luego explicare el porque los introduje
grayScaleCompress();
computeGradients();
nonMaxSupress();
hysteresis(lowV, highV);
grayScaleDecompress();
Son las 5 fases del algoritmo, sin contar la fase de aplicacion de Gauss, iré explicando una por una y al final mostrare imagenes de lo que obtuve.
1) Gray scale compresión
La imagen introducida debe tener 1 byte por pixel o superior, y se va a trabajar con una imagen que obligatoriamente debe ser de 1 byte por pixel, para eso se comprime la imagen, para evitar errores, ademas se obtiene un mejor resultado si la imagen esta en escala de grises.
void grayScaleCompress( void )
{
unsigned char * compressed = new unsigned char[ size ];
for( unsigned offset = 0; offset < size; offset++ )
compressed[offset] = image[offset* bpp];
delete[] image;
image = new unsigned char[ size ];
memcpy( image, compressed, size );
delete[] compressed;
}
Como se ve facilmente, se crea una nueva data con un tamaño de solo ancho x alto y se obliga a la imagen a estar en escala de grises , osea, se convierte a 1 byte por pixel
2) Calcular gradientes
Tuve que leer demasiado ... No soy el mejor en matemáticas , pero se me dan bien y me encuentro con esto. Gradientes ?
Gradientes esta definido como la velocidad con que una función varia.
En nuestro caso estamos trabajando con colores !, es necesario calcular y guardar la velocidad con que en un punto I los colores varian en el eje X y en el eje Y
void computeGradients( void )
{
// Compute Gradients in X
for( unsigned y = 0; y < height; y++ )
{
unsigned offset = y* width;
Gx[offset] = image[offset + 1] - image[offset];
offset++;
for( unsigned x = 1; x < width - 1; x++, offset++ )
Gx[offset] = image[offset + 1] - image[offset - 1];
Gx[offset] = image[offset] - image[offset - 1];
}
// Compute Gradients in Y
for( unsigned x = 0; x < width; x++ )
{
unsigned offset = x;
Gy[offset] = image[offset + width] - image[offset];
offset += width;
for( unsigned y = 1; y < height - 1; y++, offset += width )
Gy[offset] = image[offset + width] - image[offset - width];
Gy[offset] = image[offset] - image[offset - width];
}
// Hypotenuse = sqrt(x^2 + y^2)
for( unsigned y = 0, offset = 0; y < height; y++ )
for( unsigned x = 0; x < width; x++, offset++ )
Magnitude[offset] = hypotenuse( Gx[offset], Gy[offset] );
// Okay, edges of the image must be null
for( unsigned x = 0; x < width; x++ )
Magnitude[x] = 0;
for( unsigned x = 0, offset = width* (height - 1); x < width; x++, offset++ )
Magnitude[offset] = 0;
for( unsigned y = 0; y < width* height; y += width )
Magnitude[y] = 0;
for( unsigned y = 0, offset = width - 1; y < width* height; y += width, offset += width)
Magnitude[offset] = 0;
}
Solo piensen, estan en el centro a su izquierda el color negro, a la derecha el azul, la velocidad con que varian es la resta de ellos dos, calculo entonces esta variacion en todos los puntos I , compruebo la variacion hacendo (I+1) - (I -1), pixel de la derecha - pixel de la izquierda.
Realizo lo mismo con el eje Y, pixel de arriba - pixel de abajo: (I + ancho) - ( I - ancho )
Bien, ahora tengo el array de las variaciones en X y las variaciones en Y ahora calculo la magnitud, que ?? magnitud??
la magnitud de un vector es la distancia entre P1 y P2, la distancia entre el punto de X y el punto de Y , la hipotenusa ! , okay okay, para que hago esto ? porque hago todo esto ?
haha Un borde es facil de detectar porque hay una variacion de colores cuando termina una imagen y comienza otra.Debemos calcular donde ocurren esas variaciones y hacia donde son más altas
3 ) Supresión de los falsos positivos
Oka, hasta ahora todo parece lógico, fácil de entender. Esta es la parte más dificil de entender ,por ende dificil de explicar.
void nonMaxSupress( void )
{
/* Compute magnitudes direction and save it */
for( unsigned y = 0, offset = 0; y < height; y++ )
for( unsigned x = 0; x < width; x++, offset++ )
Direction[offset] = getAngle( Gx[offset], Gy[offset] );
/*
The most complicated part:
If the pixel is not a local maximum then kill it.
How do I know if my point is a local max ?
I will compare the current pixel with neighboring pixels in the gradient direction.
Remember: Pixel with null magnitude are not candidate to be an edge.
*/
for( unsigned y = 0, offset = 0; y < height; y++ )
for( unsigned x = 0; x < width; x++, offset++ )
{
if( Magnitude[offset] && isLocalMax(offset) )
image[offset] = Magnitude[offset] > 255 ? 255 : (unsigned char)Magnitude[offset];
else
image[offset] = 0;
}
}
Primero, si la variacion de colores es positiva en X y la variacion de colores es positiva en Y , eso significa que en el plano cartesiano, los colores varian hacia el primer cuadrante, entre los grados 0 - 90
Calculare hacia que direccion apunta la variacion de colores de cada pixel
eso se nota en el primer ciclo, en el segundo ciclo viene lo bueno...
Si saben programar y pueden manipular este codigo a voluntad e intentan visualizar la imagen como va en esta fase, tendrian algo como esto
Los bordes son muy gruesos ...y hay demasiados bordes, no pareciera, pero si los hay, si pusieran todos los colores de los bordes actuales en 255, la imagen se pondria toda blanca ... porque no esta listo ?? que es la supresion de los falsos positivos ?
Explicare ...
Mencione que al llegar al borde en una imagen hay un cambio de color porque pasas a otro objeto no ? bueno, si tienes un cubo blanco, y te situas en un pixel, de que color es el pixel de la derecha ( I + 1 ) ? blanco no ? y el pixel de la izquierda ( I - 1 ) ? blanco tambien xd entonces la gradiente cuanto sera ? blanco - blanco = 0 !
oka resulta que no solo la gradiente en X es 0 sino la gradiente en Y tambien es 0, que se obtiene ? cuanto vale la hipotenusa ? ?? 0 ! xd
hipotenusa = sqrt( x*x + y*y )
Magnitud = hipotenusa.
lo que se hizo en la imagen de arriba es setear el color del pixel cuya magnitud sea 0 en negro, oka, pero quedan pixeles con magnitud de 2 3 6, que aun es muy bajo ! ... esos son los falsos positivos, puntos en la imagen que no son bordes pero que no se han eliminado, por eso se realiza este proceso
Entonces, como sabemos que un pixel es un verdadero positivo ? un verdadero borde ? comparamos el pixel con la magnitudes de los pixeles en la direccion del gradiente... no es tan complicado como suena xd
si la variacion de colores de tu pixel apunta hacia el noroeste, lo compararemos con las variaciones de colores de los pixeles del noroeste y del suroeste y si es mayor es un verdadero positivo, o tambien llamado un maximo local , entonces el pixel es un posible borde,sino es background
if( Magnitude[offset] && isLocalMax(offset) )
4 ) Histeresis.
oka, despues de la non maximal suppression tendriamos una imagen con bordes muy delgados, pero no conectados. osea, un borde llega a un punto y no conecta a otro hasta varios pixeles despues, entonces venimos con esta fase del algoritmo de canny que nos dice que debemos introducir dos valores
El primer valor ( High Value ) Es el valor minimo que debe tener el inicio de un borde.
Debemos tener una imagen de salida toda negra, y mirar en la imagen de entrada( nuestra imagen con la nms apilcada ) si el color de un pixel es >= que el high Value, si esto es cierto entonces boom empieza el trazado de un borde
void hysteresis( float lowScale, float highScale )
{
/*
We need a High value and a Low value, High value will be the edge color.
All pixels with color higher than ' Hight value ' will be edges
and we will follow this pixel until another pixel is founded.
The pixel founded must be a color higher than ' Low value ', if that is the case
then we will set this pixel like edge, else it will be background ( null ).
*/
lowScale = lowScale <= 0.0f ? 0.01f : lowScale > 1.0f ? 1.0f : lowScale;
highScale = highScale <= 0.0f ? 0.01f : highScale > 1.0f ? 1.0f : highScale;
unsigned char globalMax = 0;
for( unsigned offset = 0; offset < size; offset++ )
if( image[offset] > globalMax )
globalMax = image[offset];
unsigned highV = globalMax* highScale;
unsigned lowV = globalMax* lowScale;
unsigned char * finalPic = new unsigned char[ size ];
memset( finalPic, 0, size );
for( unsigned y = 1,offset = 1; y < height - 1; y++ )
for( unsigned x = 1; x < width - 1; x++, offset++ )
if( image[offset] >= highV && !finalPic[offset] )
{
finalPic[offset] = 255;
continuousTracing( offset, image, finalPic, lowV );
}
delete[] image;
image = new unsigned char[ size ];
memcpy( image, finalPic, size );
delete[] finalPic;
}
Entonces, que es el trazado de un borde ?, imaginate dibujando algo, tu lapiz empieza en un punto X,Y y lo mueves hasta otro punto X,Y dependiendo de lo que quieras dibujar ...
si deseas dibujar una linea recta y vertical, entonces tu lapiz se movera unicamente hacia arriba:
Repeat (X, Y+1) Until Y >= limite de la linea a dibujar.
eso es lo que se hara a continuacion , pero no dibujaremos una linea recta, dibujaremos en diferentes direcciones ! , arriba, abajo, izquierda , derecha , etc ! ... dibujaremos siempre y cuando el pixel sobre el que vayamos a dibujar sea mayor que el Low Value
void continuousTracing( unsigned offset, unsigned char * in, unsigned char * out, unsigned thresholding )
{
/*
The concept is sample:
I found a possible edge and I will follow this edge until its end.
Test 8 neighboring pixels and if someone is higher than thresholding then
that pixel will be another edge and I will follow it.
This process is repeated until the value of the current pixel tested is null.
*/
const unsigned edge = 255;
unsigned dir[2];
dir[0] = width; // Top - Bottom
dir[1] = 1; // Left - Right
unsigned top = min( offset + dir[0], size );
if( in[top] >= thresholding )
do
{
if( !out[top] )
{
out[top] = edge;
continuousTracing( top, in, out, thresholding );
}
else
break;
top += dir[0];
if( top > size )
break;
}while( in[top] >= thresholding );
unsigned bottom = max( offset - dir[0], 0 );
if( in[bottom >= thresholding] )
do
{
if( !out[bottom] )
{
out[bottom] = edge;
continuousTracing( bottom, in, out, thresholding );
}
else
break;
bottom -= dir[0];
if( bottom < 0 )
break;
}while( in[bottom] >= thresholding );
unsigned right = min( offset + dir[1], size );
if( in[right] >= thresholding )
do
{
if( !out[right] )
{
out[right] = edge;
continuousTracing( right, in, out, thresholding );
}
else
break;
right += dir[1];
if( right > size )
break;
}while( in[right] >= thresholding );
unsigned left = max( offset - dir[1], 0 );
if( in[left] >= thresholding )
do
{
if( !out[left] )
{
out[left] = edge;
continuousTracing( left, in, out, thresholding );
}
else
break;
left -= dir[1];
if( left < 0 )
break;
}while( in[left] >= thresholding );
unsigned topRight = min( offset + dir[0] + dir[1], size );
if( in[topRight] >= thresholding )
do
{
if( !out[topRight] )
{
out[topRight] = edge;
continuousTracing( left, in, out, thresholding );
}
else
break;
topRight += dir[0] + dir[1];
if( topRight > size )
break;
}while( in[topRight] >= thresholding );
unsigned bottomLeft = max( offset - dir[0] - dir[1], 0 );
if( in[bottomLeft] >= thresholding )
do
{
if( !out[bottomLeft] )
{
out[bottomLeft] = edge;
continuousTracing( bottomLeft, in, out, thresholding );
}
else
break;
bottomLeft -= dir[0] - dir[1];
if( bottomLeft < 0 )
break;
}while( in[bottomLeft] >= thresholding );
unsigned topLeft = min( offset + dir[0] - dir[1], size );
if( in[topLeft] >= thresholding )
do
{
if( !out[topLeft] )
{
out[topLeft] = edge;
continuousTracing( topLeft, in, out, thresholding );
}
else
break;
topLeft += dir[0] - dir[1];
if( topLeft > size )
break;
}while( in[topLeft] >= thresholding );
unsigned bottomRight = max( offset - dir[0] + dir[1], 0 );
if( in[bottomRight] >= thresholding )
do
{
if( !out[bottomRight] )
{
out[bottomRight] = edge;
continuousTracing( bottomRight, in, out, thresholding );
}
else
break;
bottomRight -= dir[0] + dir[1];
if( bottomRight < 0 )
break;
}while( in[bottomRight] >= thresholding );
/* Works with feedback and not will be an infinite loop cause I am saving the new data into a new image */
}
Se dibujara en la imagen de salida, si el punto a pintar ya estaba pintado entonces se rompe el ciclo y se impide que ocurra un bucle infinito..
mi primera función que logra re alimentarse ella misma xd
RESULTADOS FINALES
[/size]
Listop, no puse más porque me da pereza, esto lo hize con la mera intencion de que si alguien busca en google "Canny algorithm" y busca resultados en español, obtenga una buena ayuda.
Y perdonen si mi codigo es desordenado, volvi a la programacion hace un par de meses y solo he leido un par de tutoriales .. en ingles depaso xd