% The format of the EdgeImage method is:
%
% Image *CannyEdgeImage(const Image *image,const double radius,
-% const double sigma,const double low_percent,const double high_percent,
-% const size_t threshold,ExceptionInfo *exception)
+% const double sigma,const double lower_percent,
+% const double upper_percent,ExceptionInfo *exception)
%
% A description of each parameter follows:
%
% o image: the image.
%
-% o channel: the channel type.
-%
% o radius: the radius of the gaussian smoothing filter.
%
% o sigma: the sigma of the gaussian smoothing filter.
%
-% o low_percent: percentage of pixels in the low threshold.
+% o lower_precent: percentage of edge pixels in the lower threshold.
%
-% o high_percent: percentage of pixels in the high threshold.
+% o upper_percent: percentage of edge pixels in the upper threshold.
%
% o exception: return any errors or warnings in this structure.
%
int
orientation;
+
+ ssize_t
+ x,
+ y;
} CannyInfo;
-static MagickBooleanType IsAuthenticPixel(const Image *image,const ssize_t x,
- const ssize_t y)
+static inline MagickBooleanType IsAuthenticPixel(const Image *image,
+ const ssize_t x,const ssize_t y)
{
if ((x < 0) || (x >= (ssize_t) image->columns))
return(MagickFalse);
return(MagickTrue);
}
-static MagickBooleanType TraceEdge(Image *edge_image,CacheView *edge_view,
- MatrixInfo *pixel_cache,const ssize_t x,const ssize_t y,
- const double threshold,ExceptionInfo *exception)
+static MagickBooleanType TraceEdges(Image *edge_image,CacheView *edge_view,
+ MatrixInfo *canny_cache,const ssize_t x,const ssize_t y,
+ const double lower_threshold,ExceptionInfo *exception)
{
CannyInfo
+ edge,
pixel;
- Quantum
- *q;
-
MagickBooleanType
status;
+ register Quantum
+ *q;
+
+ register ssize_t
+ i;
+
q=GetCacheViewAuthenticPixels(edge_view,x,y,1,1,exception);
- if ((q != (Quantum *) NULL) && (GetPixelIntensity(edge_image,q) == 0))
+ if (q == (Quantum *) NULL)
+ return(MagickFalse);
+ *q=QuantumRange;
+ status=SyncCacheViewAuthenticPixels(edge_view,exception);
+ if (status == MagickFalse)
+ return(MagickFalse);;
+ if (GetMatrixElement(canny_cache,0,0,&edge) == MagickFalse)
+ return(MagickFalse);
+ edge.x=x;
+ edge.y=y;
+ if (SetMatrixElement(canny_cache,0,0,&edge) == MagickFalse)
+ return(MagickFalse);
+ for (i=1; i != 0; )
+ {
+ ssize_t
+ v;
+
+ i--;
+ status=GetMatrixElement(canny_cache,i,0,&edge);
+ if (status == MagickFalse)
+ return(MagickFalse);
+ for (v=(-1); v <= 1; v++)
{
ssize_t
- v;
+ u;
- *q=QuantumRange;
- status=SyncCacheViewAuthenticPixels(edge_view,exception);
- if (status != MagickFalse)
- {
- for (v=(-1); v <= 1; v++)
+ for (u=(-1); u <= 1; u++)
+ {
+ if ((u == 0) && (v == 0))
+ continue;
+ if (IsAuthenticPixel(edge_image,edge.x+u,edge.y+v) == MagickFalse)
+ continue;
+ /*
+ Not an edge if gradient value is below the lower threshold.
+ */
+ q=GetCacheViewAuthenticPixels(edge_view,edge.x+u,edge.y+v,1,1,
+ exception);
+ if (q == (Quantum *) NULL)
+ return(MagickFalse);
+ status=GetMatrixElement(canny_cache,edge.x+u,edge.y+v,&pixel);
+ if (status == MagickFalse)
+ return(MagickFalse);
+ if ((GetPixelIntensity(edge_image,q) == 0.0) &&
+ (pixel.intensity >= lower_threshold))
{
- ssize_t
- u;
-
- for (u=(-1); u <= 1; u++)
- {
- if ((u == 0) && (v == 0))
- continue;
- if (IsAuthenticPixel(edge_image,x+u,y+v) == MagickFalse)
- continue;
- (void) GetMatrixElement(pixel_cache,x+u,y+v,&pixel);
- if (pixel.intensity < threshold)
- continue;
- status=TraceEdge(edge_image,edge_view,pixel_cache,x+u,y+v,
- threshold,exception);
- if (status != MagickFalse)
- return(MagickTrue);
- }
+ *q=QuantumRange;
+ status=SyncCacheViewAuthenticPixels(edge_view,exception);
+ if (status == MagickFalse)
+ return(MagickFalse);
+ edge.x+=u;
+ edge.y+=v;
+ status=SetMatrixElement(canny_cache,i,0,&edge);
+ if (status == MagickFalse)
+ return(MagickFalse);
+ i++;
}
- return(MagickTrue);
- }
+ }
}
- return(MagickFalse);
+ }
+ return(MagickTrue);
}
MagickExport Image *CannyEdgeImage(const Image *image,const double radius,
- const double sigma,const double low_percent,const double high_percent,
+ const double sigma,const double lower_percent,const double upper_percent,
ExceptionInfo *exception)
{
CacheView
*edge_view;
+ CannyInfo
+ pixel;
+
char
geometry[MaxTextExtent];
double
- high_threshold,
- low_threshold;
+ lower_threshold,
+ max,
+ min,
+ upper_threshold;
Image
*edge_image;
status;
MatrixInfo
- *pixel_cache;
-
- register ssize_t
- i;
-
- size_t
- *histogram,
- number_pixels;
+ *canny_cache;
ssize_t
- count,
y;
assert(image != (const Image *) NULL);
assert(exception != (ExceptionInfo *) NULL);
assert(exception->signature == MagickSignature);
/*
- Filter out noise before trying to locate and detect any edges.
+ Filter out noise.
*/
(void) FormatLocaleString(geometry,MaxTextExtent,
"blur:%.20gx%.20g;blur:%.20gx%.20g+90",radius,sigma,radius,sigma);
return((Image *) NULL);
}
/*
- Find the edge strength by taking the gradient of the image.
+ Find the intensity gradient of the image.
*/
- pixel_cache=AcquireMatrixInfo(edge_image->columns,edge_image->rows,
+ canny_cache=AcquireMatrixInfo(edge_image->columns,edge_image->rows,
sizeof(CannyInfo),exception);
- if (pixel_cache == (MatrixInfo *) NULL)
+ if (canny_cache == (MatrixInfo *) NULL)
{
edge_image=DestroyImage(edge_image);
return((Image *) NULL);
if (status == MagickFalse)
continue;
- p=GetCacheViewVirtualPixels(edge_view,-1,y-1,edge_image->columns+2,3,
+ p=GetCacheViewVirtualPixels(edge_view,0,y,edge_image->columns+1,2,
exception);
if (p == (const Quantum *) NULL)
{
v;
static double
- Gx[3][3] =
+ Gx[2][2] =
{
- { -1.0, 0.0, +1.0 },
- { -2.0, 0.0, +2.0 },
- { -1.0, 0.0, +1.0 }
+ { -1.0, +1.0 },
+ { -1.0, +1.0 }
},
- Gy[3][3] =
+ Gy[2][2] =
{
- { +1.0, +2.0, +1.0 },
- { 0.0, 0.0, 0.0 },
- { -1.0, -2.0, -1.0 }
+ { +1.0, +1.0 },
+ { -1.0, -1.0 }
};
(void) ResetMagickMemory(&pixel,0,sizeof(pixel));
dx=0.0;
dy=0.0;
kernel_pixels=p;
- for (v=0; v < 3; v++)
+ for (v=0; v < 2; v++)
{
ssize_t
u;
- for (u=0; u < 3; u++)
+ for (u=0; u < 2; u++)
{
double
intensity;
intensity=GetPixelIntensity(edge_image,kernel_pixels+u);
- dx+=Gx[v][u]*intensity;
- dy+=Gy[v][u]*intensity;
+ dx+=0.5*Gx[v][u]*intensity;
+ dy+=0.5*Gy[v][u]*intensity;
}
- kernel_pixels+=edge_image->columns+2;
+ kernel_pixels+=edge_image->columns+1;
}
- pixel.magnitude=sqrt(dx*dx+dy*dy);
- pixel.orientation=2;
- if (dx != 0.0)
+ pixel.magnitude=hypot(dx,dy);
+ pixel.orientation=0;
+ if (fabs(dx) > MagickEpsilon)
{
double
- theta;
+ slope;
- theta=dy/dx;
- if (theta < 0.0)
+ slope=dy/dx;
+ if (slope < 0.0)
{
- if (theta < -2.41421356237)
+ if (slope < -2.41421356237)
pixel.orientation=0;
else
- if (theta < -0.414213562373)
+ if (slope < -0.414213562373)
pixel.orientation=1;
else
pixel.orientation=2;
}
else
{
- if (theta > 2.41421356237)
+ if (slope > 2.41421356237)
pixel.orientation=0;
else
- if (theta > 0.414213562373)
+ if (slope > 0.414213562373)
pixel.orientation=3;
else
pixel.orientation=2;
}
}
- if (SetMatrixElement(pixel_cache,x,y,&pixel) == MagickFalse)
+ if (SetMatrixElement(canny_cache,x,y,&pixel) == MagickFalse)
continue;
p+=GetPixelChannels(edge_image);
}
}
edge_view=DestroyCacheView(edge_view);
/*
- Non-maxima suppression; reset edge image.
+ Non-maxima suppression, remove pixels that are not considered to be part
+ of an edge.
*/
- histogram=(size_t *) AcquireQuantumMemory(65536,sizeof(*histogram));
- if (histogram == (size_t *) NULL)
- {
- pixel_cache=DestroyMatrixInfo(pixel_cache);
- edge_image=DestroyImage(edge_image);
- return((Image *) NULL);
- }
- (void) ResetMagickMemory(histogram,0,65536*sizeof(*histogram));
+ (void) GetMatrixElement(canny_cache,0,0,&pixel);
+ max=pixel.intensity;
+ min=pixel.intensity;
edge_view=AcquireAuthenticCacheView(edge_image,exception);
#if defined(MAGICKCORE_OPENMP_SUPPORT)
#pragma omp parallel for schedule(static,4) shared(status) \
beta_pixel,
pixel;
- (void) GetMatrixElement(pixel_cache,x,y,&pixel);
+ (void) GetMatrixElement(canny_cache,x,y,&pixel);
switch (pixel.orientation)
{
case 0:
{
/*
- 0 degrees.
+ 0 degrees, north and south.
*/
- (void) GetMatrixElement(pixel_cache,x,y-1,&alpha_pixel);
- (void) GetMatrixElement(pixel_cache,x,y+1,&beta_pixel);
+ (void) GetMatrixElement(canny_cache,x,y-1,&alpha_pixel);
+ (void) GetMatrixElement(canny_cache,x,y+1,&beta_pixel);
break;
}
case 1:
{
/*
- 45 degrees.
+ 45 degrees, northwest and southeast.
*/
- (void) GetMatrixElement(pixel_cache,x-1,y-1,&alpha_pixel);
- (void) GetMatrixElement(pixel_cache,x+1,y+1,&beta_pixel);
+ (void) GetMatrixElement(canny_cache,x-1,y-1,&alpha_pixel);
+ (void) GetMatrixElement(canny_cache,x+1,y+1,&beta_pixel);
break;
}
case 2:
{
/*
- 90 degrees.
+ 90 degrees, east and west.
*/
- (void) GetMatrixElement(pixel_cache,x-1,y,&alpha_pixel);
- (void) GetMatrixElement(pixel_cache,x+1,y,&beta_pixel);
+ (void) GetMatrixElement(canny_cache,x-1,y,&alpha_pixel);
+ (void) GetMatrixElement(canny_cache,x+1,y,&beta_pixel);
+ break;
}
case 3:
{
/*
- 135 degrees.
+ 135 degrees, northeast and southwest.
*/
- (void) GetMatrixElement(pixel_cache,x+1,y-1,&alpha_pixel);
- (void) GetMatrixElement(pixel_cache,x-1,y+1,&beta_pixel);
+ (void) GetMatrixElement(canny_cache,x+1,y-1,&beta_pixel);
+ (void) GetMatrixElement(canny_cache,x-1,y+1,&alpha_pixel);
+ break;
}
}
pixel.intensity=pixel.magnitude;
if ((pixel.magnitude < alpha_pixel.magnitude) ||
(pixel.magnitude < beta_pixel.magnitude))
pixel.intensity=0;
- else
- if (pixel.magnitude > QuantumRange)
- pixel.intensity=QuantumRange;
- (void) SetMatrixElement(pixel_cache,x,y,&pixel);
+ (void) SetMatrixElement(canny_cache,x,y,&pixel);
#if defined(MAGICKCORE_OPENMP_SUPPORT)
#pragma omp critical (MagickCore_CannyEdgeImage)
#endif
- histogram[ScaleQuantumToShort(ClampToQuantum(pixel.intensity))]++;
+ {
+ if (pixel.intensity < min)
+ min=pixel.intensity;
+ if (pixel.intensity > max)
+ max=pixel.intensity;
+ }
*q=0;
q+=GetPixelChannels(edge_image);
}
/*
Estimate hysteresis threshold.
*/
- number_pixels=(size_t) (low_percent*(image->columns*image->rows-
- histogram[0]));
- count=0;
- for (i=65535; count < (ssize_t) number_pixels; i--)
- count+=histogram[i];
- high_threshold=(double) ScaleShortToQuantum((unsigned short) i);
- for (i=0; histogram[i] == 0; i++) ;
- low_threshold=high_percent*(high_threshold+
- ScaleShortToQuantum((unsigned short) i));
- histogram=(size_t *) RelinquishMagickMemory(histogram);
+ lower_threshold=lower_percent*(max-min)+min;
+ upper_threshold=upper_percent*(max-min)+min;
/*
- Hysteresis thresholding.
+ Hysteresis threshold.
*/
edge_view=AcquireAuthenticCacheView(edge_image,exception);
-#if defined(MAGICKCORE_OPENMP_SUPPORT)
- #pragma omp parallel for schedule(static,4) shared(status) \
- magick_threads(edge_image,edge_image,edge_image->rows,1)
-#endif
for (y=0; y < (ssize_t) edge_image->rows; y++)
{
- register Quantum
- *restrict q;
-
register ssize_t
x;
if (status == MagickFalse)
continue;
- q=GetCacheViewAuthenticPixels(edge_view,0,y,edge_image->columns,1,
- exception);
- if (q == (Quantum *) NULL)
- {
- status=MagickFalse;
- continue;
- }
for (x=0; x < (ssize_t) edge_image->columns; x++)
{
CannyInfo
pixel;
- (void) GetMatrixElement(pixel_cache,x,y,&pixel);
- if (pixel.intensity >= high_threshold)
- (void) TraceEdge(edge_image,edge_view,pixel_cache,x,y,low_threshold,
+ register const Quantum
+ *restrict p;
+
+ /*
+ Edge if pixel gradient higher than upper threshold.
+ */
+ p=GetCacheViewVirtualPixels(edge_view,x,y,1,1,exception);
+ if (p == (const Quantum *) NULL)
+ continue;
+ status=GetMatrixElement(canny_cache,x,y,&pixel);
+ if (status == MagickFalse)
+ continue;
+ if ((GetPixelIntensity(edge_image,p) == 0.0) &&
+ (pixel.intensity >= upper_threshold))
+ status=TraceEdges(edge_image,edge_view,canny_cache,x,y,lower_threshold,
exception);
}
- if (SyncCacheViewAuthenticPixels(edge_view,exception) == MagickFalse)
- status=MagickFalse;
}
edge_view=DestroyCacheView(edge_view);
- pixel_cache=DestroyMatrixInfo(pixel_cache);
+ /*
+ Free resources.
+ */
+ canny_cache=DestroyMatrixInfo(canny_cache);
return(edge_image);
}
\f