struct cannyAlgorithm
{
unsigned char * image;
unsigned width;
unsigned height;
unsigned size;
unsigned bpp;
short * Gx;
short * Gy;
short * Direction;
double * Magnitude;
cannyAlgorithm( unsigned char * data, unsigned imgw, unsigned imgh, unsigned bitsperpixel )
{
width = imgw;
height = imgh;
size = width* height;
bpp = bitsperpixel;
Gx = new short[ size ];
Gy = new short[ size ];
Direction = new short[ size ];
Magnitude = new double[ size ];
image = new unsigned char[ size* bpp ];
memcpy( image, data, size* bpp );
}
~cannyAlgorithm( void )
{
delete[] Gx;
delete[] Gy;
delete[] Direction;
delete[] Magnitude;
}
int max( int a, int b )
{
int c = a > b ? a : b;
return c;
}
int min( int a, int b )
{
int c = a < b ? a : b;
return c;
}
short getAngle( double X, double Y )
{
short Angle;
if( X* Y > 0 ) // Quadrant 1 or 3
{
if( abs( X ) >= abs( Y ) )
Angle = 0;
else
Angle = 180;
}
else // Quadrant 2 or 4
{
if( abs(X) >= abs(Y) )
Angle = 90;
else
Angle = 270;
}
return( Angle );
}
double hypotenuse( double a, double b )
{
double h = sqrt( a*a + b*b );
return(h);
}
bool isLocalMax( unsigned offset )
{
unsigned bottom = max(offset - width, 0);
unsigned top = min(offset + width, size);
unsigned left = max(offset - 1, 0);
unsigned right = min(offset + 1, size);
unsigned bottomLeft = max(bottom - 1, 0);
unsigned bottomRight= min(bottom + 1, size);
unsigned topLeft = max(top - 1, 0);
unsigned topRight = min(top + 1, size);
double thisPoint = 0.0;
double mag[2] = { 0.0 };
switch( Direction[offset] )
{
case 0:
{
/* 90
*
|******
|******
-------------* 0
|
|
*/
thisPoint = abs( Gx[offset]* Magnitude[offset] );
mag[0] = abs( Gy[offset]* Magnitude[topRight ] + ( Gx[offset] - Gy[offset] )* Magnitude[right] );
mag[1] = abs( Gy[offset]* Magnitude[bottomLeft] + ( Gx[offset] - Gy[offset] )* Magnitude[left ] );
}break;
case 90:
{
/*
90
*
*****|
*****|
180 *-------------
|
|
*/
thisPoint = abs(Gx[offset]* Magnitude[offset] );
mag[0] = abs( Gy[offset]* Magnitude[bottomRight] - ( Gx[offset] + Gy[offset])* Magnitude[right] );
mag[1] = abs( Gy[offset]* Magnitude[topLeft ] - ( Gx[offset] + Gy[offset])* Magnitude[left ] );
}break;
case 180:
{
/*
|
|
180 *-------------
******|
******|
*
270
*/
thisPoint = abs( Gy[offset]* Magnitude[offset] );
mag[0] = abs( Gx[offset]* Magnitude[topRight ] + ( Gy[offset] - Gx[offset] )* Magnitude[top ] );
mag[1] = abs( Gx[offset]* Magnitude[bottomLeft] + ( Gy[offset] - Gx[offset] )* Magnitude[bottom] );
}break;
case 270:
{
/*
|
|
-------------* 0
|*******
|*******
*
270
*/
thisPoint = abs( Gy[offset]* Magnitude[offset] );
mag[0] = abs( Gx[offset]* Magnitude[bottomRight] - ( Gy[offset] + Gx[offset] )* Magnitude[bottom] );
mag[1] = abs( Gx[offset]* Magnitude[topLeft ] - ( Gy[offset] + Gx[offset] )* Magnitude[top ] );
}break;
default:
break;
}
if( thisPoint >= mag[0] && thisPoint >= mag[1] )
return( true );
return( false );
}
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;
}
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 */
}
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;
}
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;
}
}
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;
}
void grayScaleDecompress( void )
{
size = width* height* bpp;
unsigned char * decompressed = new unsigned char[ size ];
for( unsigned offset = 0; offset < width* height; offset++ )
decompressed[offset*bpp + 0] = decompressed[offset* bpp + 1] = decompressed[offset* bpp + 2] = image[offset];
delete[] image;
image = new unsigned char[ size ];
memcpy( image, decompressed, size );
delete[] decompressed;
}
void AutoEdgeDetection( unsigned char * data, float lowV, float highV )
{
grayScaleCompress();
computeGradients();
nonMaxSupress();
hysteresis(lowV, highV);
grayScaleDecompress();
memcpy( data, image, size );
}
unsigned char * get_data( void )
{
grayScaleDecompress();
return( image );
}
};