39 #include "MagickCore/studio.h"
40 #include "MagickCore/artifact.h"
41 #include "MagickCore/blob.h"
42 #include "MagickCore/cache-view.h"
43 #include "MagickCore/color.h"
44 #include "MagickCore/color-private.h"
45 #include "MagickCore/colormap.h"
46 #include "MagickCore/colorspace.h"
47 #include "MagickCore/constitute.h"
48 #include "MagickCore/decorate.h"
49 #include "MagickCore/distort.h"
50 #include "MagickCore/draw.h"
51 #include "MagickCore/enhance.h"
52 #include "MagickCore/exception.h"
53 #include "MagickCore/exception-private.h"
54 #include "MagickCore/effect.h"
55 #include "MagickCore/gem.h"
56 #include "MagickCore/geometry.h"
57 #include "MagickCore/image-private.h"
58 #include "MagickCore/list.h"
59 #include "MagickCore/log.h"
60 #include "MagickCore/matrix.h"
61 #include "MagickCore/memory_.h"
62 #include "MagickCore/memory-private.h"
63 #include "MagickCore/monitor.h"
64 #include "MagickCore/monitor-private.h"
65 #include "MagickCore/montage.h"
66 #include "MagickCore/morphology.h"
67 #include "MagickCore/morphology-private.h"
68 #include "MagickCore/opencl-private.h"
69 #include "MagickCore/paint.h"
70 #include "MagickCore/pixel-accessor.h"
71 #include "MagickCore/property.h"
72 #include "MagickCore/quantum.h"
73 #include "MagickCore/resource_.h"
74 #include "MagickCore/signature-private.h"
75 #include "MagickCore/string_.h"
76 #include "MagickCore/string-private.h"
77 #include "MagickCore/thread-private.h"
78 #include "MagickCore/token.h"
79 #include "MagickCore/vision.h"
119 static int CCObjectInfoCompare(
const void *x,
const void *y)
128 return((
int) (q->bounding_box.y-(ssize_t) p->bounding_box.y));
130 return((
int) (q->bounding_box.x-(ssize_t) p->bounding_box.x));
132 return((
int) (q->bounding_box.height-(ssize_t) p->bounding_box.height));
134 return((
int) (q->bounding_box.width-(ssize_t) p->bounding_box.width));
136 return((
int) (q->area-(ssize_t) p->area));
138 return((
int) (p->area-(ssize_t) q->area));
140 return((
int) (p->bounding_box.width-(ssize_t) q->bounding_box.width));
142 return((
int) (p->bounding_box.height-(ssize_t) q->bounding_box.height));
144 return((
int) (p->bounding_box.x-(ssize_t) q->bounding_box.x));
146 return((
int) (p->bounding_box.y-(ssize_t) q->bounding_box.y));
147 return((
int) (q->area-(ssize_t) p->area));
150 static void PerimeterThreshold(
const Image *component_image,
160 #if defined(MAGICKCORE_OPENMP_SUPPORT)
161 #pragma omp parallel for schedule(dynamic) shared(status) \
162 magick_number_threads(component_image,component_image,component_image->colors,1)
164 for (i=0; i < (ssize_t) component_image->colors; i++)
173 pattern[4] = { 1, 0, 0, 0 };
181 if (status == MagickFalse)
183 component_view=AcquireAuthenticCacheView(component_image,exception);
184 bounding_box=
object[i].bounding_box;
185 for (y=(-1); y < (ssize_t) bounding_box.height+1; y++)
193 p=GetCacheViewVirtualPixels(component_view,bounding_box.x-1,
194 bounding_box.y+y,bounding_box.width+2,2,exception);
195 if (p == (
const Quantum *) NULL)
200 for (x=(-1); x < (ssize_t) bounding_box.width+1; x++)
216 for (v=0; v < 2; v++)
221 for (u=0; u < 2; u++)
226 offset=v*(bounding_box.width+2)*
227 GetPixelChannels(component_image)+u*
228 GetPixelChannels(component_image);
229 pixels[2*v+u]=GetPixelIndex(component_image,p+offset);
230 if ((ssize_t) pixels[2*v+u] == i)
239 if ((((ssize_t) pixels[0] == i) &&
240 ((ssize_t) pixels[3] == i)) ||
241 (((ssize_t) pixels[1] == i) &&
242 ((ssize_t) pixels[2] == i)))
250 p+=GetPixelChannels(component_image);
253 component_view=DestroyCacheView(component_view);
254 object[i].metric[metric_index]=ceil(MagickSQ1_2*pattern[1]+1.0*pattern[2]+
255 MagickSQ1_2*pattern[3]+MagickSQ2*pattern[0]-0.5);
259 static void CircularityThreshold(
const Image *component_image,
269 #if defined(MAGICKCORE_OPENMP_SUPPORT)
270 #pragma omp parallel for schedule(dynamic) shared(status) \
271 magick_number_threads(component_image,component_image,component_image->colors,1)
273 for (i=0; i < (ssize_t) component_image->colors; i++)
282 pattern[4] = { 1, 0, 0, 0 };
290 if (status == MagickFalse)
292 component_view=AcquireAuthenticCacheView(component_image,exception);
293 bounding_box=
object[i].bounding_box;
294 for (y=(-1); y < (ssize_t) bounding_box.height; y++)
302 p=GetCacheViewVirtualPixels(component_view,bounding_box.x-1,
303 bounding_box.y+y,bounding_box.width+2,2,exception);
304 if (p == (
const Quantum *) NULL)
309 for (x=(-1); x < (ssize_t) bounding_box.width; x++)
325 for (v=0; v < 2; v++)
330 for (u=0; u < 2; u++)
335 offset=v*(bounding_box.width+2)*
336 GetPixelChannels(component_image)+u*
337 GetPixelChannels(component_image);
338 pixels[2*v+u]=GetPixelIndex(component_image,p+offset);
339 if ((ssize_t) pixels[2*v+u] == i)
348 if ((((ssize_t) pixels[0] == i) &&
349 ((ssize_t) pixels[3] == i)) ||
350 (((ssize_t) pixels[1] == i) &&
351 ((ssize_t) pixels[2] == i)))
359 p+=GetPixelChannels(component_image);
362 component_view=DestroyCacheView(component_view);
363 object[i].metric[metric_index]=ceil(MagickSQ1_2*pattern[1]+1.0*pattern[2]+
364 MagickSQ1_2*pattern[3]+MagickSQ2*pattern[0]-0.5);
365 object[i].metric[metric_index]=4.0*MagickPI*
object[i].area/
366 (
object[i].metric[metric_index]*
object[i].metric[metric_index]);
370 static void MajorAxisThreshold(
const Image *component_image,
380 #if defined(MAGICKCORE_OPENMP_SUPPORT)
381 #pragma omp parallel for schedule(dynamic) shared(status) \
382 magick_number_threads(component_image,component_image,component_image->colors,1)
384 for (i=0; i < (ssize_t) component_image->colors; i++)
398 centroid = { 0.0, 0.0 };
415 if (status == MagickFalse)
417 component_view=AcquireAuthenticCacheView(component_image,exception);
418 bounding_box=
object[i].bounding_box;
419 for (y=0; y < (ssize_t) bounding_box.height; y++)
421 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
422 bounding_box.y+y,bounding_box.width,1,exception);
423 if (p == (
const Quantum *) NULL)
428 for (x=0; x < (ssize_t) bounding_box.width; x++)
430 if ((ssize_t) GetPixelIndex(component_image,p) == i)
436 p+=GetPixelChannels(component_image);
439 centroid.x=M10*PerceptibleReciprocal(M00);
440 centroid.y=M01*PerceptibleReciprocal(M00);
441 for (y=0; y < (ssize_t) bounding_box.height; y++)
443 if (status == MagickFalse)
445 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
446 bounding_box.y+y,bounding_box.width,1,exception);
447 if (p == (
const Quantum *) NULL)
452 for (x=0; x < (ssize_t) bounding_box.width; x++)
454 if ((ssize_t) GetPixelIndex(component_image,p) == i)
456 M11+=(x-centroid.x)*(y-centroid.y);
457 M20+=(x-centroid.x)*(x-centroid.x);
458 M02+=(y-centroid.y)*(y-centroid.y);
460 p+=GetPixelChannels(component_image);
463 component_view=DestroyCacheView(component_view);
464 object[i].metric[metric_index]=sqrt((2.0*PerceptibleReciprocal(M00))*
465 ((M20+M02)+sqrt(4.0*M11*M11+(M20-M02)*(M20-M02))));
469 static void MinorAxisThreshold(
const Image *component_image,
479 #if defined(MAGICKCORE_OPENMP_SUPPORT)
480 #pragma omp parallel for schedule(dynamic) shared(status) \
481 magick_number_threads(component_image,component_image,component_image->colors,1)
483 for (i=0; i < (ssize_t) component_image->colors; i++)
497 centroid = { 0.0, 0.0 };
514 if (status == MagickFalse)
516 component_view=AcquireAuthenticCacheView(component_image,exception);
517 bounding_box=
object[i].bounding_box;
518 for (y=0; y < (ssize_t) bounding_box.height; y++)
520 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
521 bounding_box.y+y,bounding_box.width,1,exception);
522 if (p == (
const Quantum *) NULL)
527 for (x=0; x < (ssize_t) bounding_box.width; x++)
529 if ((ssize_t) GetPixelIndex(component_image,p) == i)
535 p+=GetPixelChannels(component_image);
538 centroid.x=M10*PerceptibleReciprocal(M00);
539 centroid.y=M01*PerceptibleReciprocal(M00);
540 for (y=0; y < (ssize_t) bounding_box.height; y++)
542 if (status == MagickFalse)
544 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
545 bounding_box.y+y,bounding_box.width,1,exception);
546 if (p == (
const Quantum *) NULL)
551 for (x=0; x < (ssize_t) bounding_box.width; x++)
553 if ((ssize_t) GetPixelIndex(component_image,p) == i)
555 M11+=(x-centroid.x)*(y-centroid.y);
556 M20+=(x-centroid.x)*(x-centroid.x);
557 M02+=(y-centroid.y)*(y-centroid.y);
559 p+=GetPixelChannels(component_image);
562 component_view=DestroyCacheView(component_view);
563 object[i].metric[metric_index]=sqrt((2.0*PerceptibleReciprocal(M00))*
564 ((M20+M02)-sqrt(4.0*M11*M11+(M20-M02)*(M20-M02))));
568 static void EccentricityThreshold(
const Image *component_image,
578 #if defined(MAGICKCORE_OPENMP_SUPPORT)
579 #pragma omp parallel for schedule(dynamic) shared(status) \
580 magick_number_threads(component_image,component_image,component_image->colors,1)
582 for (i=0; i < (ssize_t) component_image->colors; i++)
596 centroid = { 0.0, 0.0 },
597 ellipse_axis = { 0.0, 0.0 };
614 if (status == MagickFalse)
616 component_view=AcquireAuthenticCacheView(component_image,exception);
617 bounding_box=
object[i].bounding_box;
618 for (y=0; y < (ssize_t) bounding_box.height; y++)
620 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
621 bounding_box.y+y,bounding_box.width,1,exception);
622 if (p == (
const Quantum *) NULL)
627 for (x=0; x < (ssize_t) bounding_box.width; x++)
629 if ((ssize_t) GetPixelIndex(component_image,p) == i)
635 p+=GetPixelChannels(component_image);
638 centroid.x=M10*PerceptibleReciprocal(M00);
639 centroid.y=M01*PerceptibleReciprocal(M00);
640 for (y=0; y < (ssize_t) bounding_box.height; y++)
642 if (status == MagickFalse)
644 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
645 bounding_box.y+y,bounding_box.width,1,exception);
646 if (p == (
const Quantum *) NULL)
651 for (x=0; x < (ssize_t) bounding_box.width; x++)
653 if ((ssize_t) GetPixelIndex(component_image,p) == i)
655 M11+=(x-centroid.x)*(y-centroid.y);
656 M20+=(x-centroid.x)*(x-centroid.x);
657 M02+=(y-centroid.y)*(y-centroid.y);
659 p+=GetPixelChannels(component_image);
662 component_view=DestroyCacheView(component_view);
663 ellipse_axis.x=sqrt((2.0*PerceptibleReciprocal(M00))*((M20+M02)+
664 sqrt(4.0*M11*M11+(M20-M02)*(M20-M02))));
665 ellipse_axis.y=sqrt((2.0*PerceptibleReciprocal(M00))*((M20+M02)-
666 sqrt(4.0*M11*M11+(M20-M02)*(M20-M02))));
667 object[i].metric[metric_index]=sqrt(1.0-(ellipse_axis.y*ellipse_axis.y*
668 PerceptibleReciprocal(ellipse_axis.x*ellipse_axis.x)));
672 static void AngleThreshold(
const Image *component_image,
682 #if defined(MAGICKCORE_OPENMP_SUPPORT)
683 #pragma omp parallel for schedule(dynamic) shared(status) \
684 magick_number_threads(component_image,component_image,component_image->colors,1)
686 for (i=0; i < (ssize_t) component_image->colors; i++)
700 centroid = { 0.0, 0.0 };
717 if (status == MagickFalse)
719 component_view=AcquireAuthenticCacheView(component_image,exception);
720 bounding_box=
object[i].bounding_box;
721 for (y=0; y < (ssize_t) bounding_box.height; y++)
723 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
724 bounding_box.y+y,bounding_box.width,1,exception);
725 if (p == (
const Quantum *) NULL)
730 for (x=0; x < (ssize_t) bounding_box.width; x++)
732 if ((ssize_t) GetPixelIndex(component_image,p) == i)
738 p+=GetPixelChannels(component_image);
741 centroid.x=M10*PerceptibleReciprocal(M00);
742 centroid.y=M01*PerceptibleReciprocal(M00);
743 for (y=0; y < (ssize_t) bounding_box.height; y++)
745 if (status == MagickFalse)
747 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
748 bounding_box.y+y,bounding_box.width,1,exception);
749 if (p == (
const Quantum *) NULL)
754 for (x=0; x < (ssize_t) bounding_box.width; x++)
756 if ((ssize_t) GetPixelIndex(component_image,p) == i)
758 M11+=(x-centroid.x)*(y-centroid.y);
759 M20+=(x-centroid.x)*(x-centroid.x);
760 M02+=(y-centroid.y)*(y-centroid.y);
762 p+=GetPixelChannels(component_image);
765 component_view=DestroyCacheView(component_view);
766 object[i].metric[metric_index]=RadiansToDegrees(1.0/2.0*atan(2.0*M11*
767 PerceptibleReciprocal(M20-M02)));
770 if ((fabs(M20-M02) >= 0.0) && ((M20-M02) < 0.0))
771 object[i].metric[metric_index]+=90.0;
776 if (fabs(M20-M02) >= 0.0)
779 object[i].metric[metric_index]+=90.0;
781 object[i].metric[metric_index]+=180.0;
785 if ((fabs(M20-M02) >= 0.0) && ((M20-M02) < 0.0))
786 object[i].metric[metric_index]+=90.0;
790 MagickExport
Image *ConnectedComponentsImage(
const Image *image,
793 #define ConnectedComponentsImageTag "ConnectedComponents/Image"
808 *metrics[CCMaxMetrics];
831 connect4[2][2] = { { -1, 0 }, { 0, -1 } },
832 connect8[4][2] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 } },
845 assert(image != (
Image *) NULL);
846 assert(image->signature == MagickCoreSignature);
848 assert(exception->signature == MagickCoreSignature);
849 if (IsEventLogging() != MagickFalse)
850 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
853 component_image=CloneImage(image,0,0,MagickTrue,exception);
854 if (component_image == (
Image *) NULL)
855 return((
Image *) NULL);
856 component_image->depth=MAGICKCORE_QUANTUM_DEPTH;
857 if (AcquireImageColormap(component_image,MaxColormapSize,exception) == MagickFalse)
859 component_image=DestroyImage(component_image);
860 ThrowImageException(ResourceLimitError,
"MemoryAllocationFailed");
865 size=image->columns*image->rows;
866 if (image->columns != (size/image->rows))
868 component_image=DestroyImage(component_image);
869 ThrowImageException(ResourceLimitError,
"MemoryAllocationFailed");
871 equivalences=AcquireMatrixInfo(size,1,
sizeof(ssize_t),exception);
874 component_image=DestroyImage(component_image);
875 return((
Image *) NULL);
877 for (n=0; n < (ssize_t) (image->columns*image->rows); n++)
878 (
void) SetMatrixElement(equivalences,n,0,&n);
879 object=(
CCObjectInfo *) AcquireQuantumMemory(MaxColormapSize,
sizeof(*
object));
882 equivalences=DestroyMatrixInfo(equivalences);
883 component_image=DestroyImage(component_image);
884 ThrowImageException(ResourceLimitError,
"MemoryAllocationFailed");
886 (void) memset(
object,0,MaxColormapSize*
sizeof(*
object));
887 for (i=0; i < (ssize_t) MaxColormapSize; i++)
890 object[i].bounding_box.x=(ssize_t) image->columns;
891 object[i].bounding_box.y=(ssize_t) image->rows;
892 GetPixelInfo(image,&
object[i].color);
899 image_view=AcquireVirtualCacheView(image,exception);
900 for (n=0; n < (ssize_t) (connectivity > 4 ? 4 : 2); n++)
902 if (status == MagickFalse)
904 dx=connectivity > 4 ? connect8[n][1] : connect4[n][1];
905 dy=connectivity > 4 ? connect8[n][0] : connect4[n][0];
906 for (y=0; y < (ssize_t) image->rows; y++)
914 if (status == MagickFalse)
916 p=GetCacheViewVirtualPixels(image_view,0,y-1,image->columns,3,exception);
917 if (p == (
const Quantum *) NULL)
922 p+=GetPixelChannels(image)*image->columns;
923 for (x=0; x < (ssize_t) image->columns; x++)
940 GetPixelInfoPixel(image,p,&pixel);
941 if (((x+dx) < 0) || ((x+dx) >= (ssize_t) image->columns) ||
942 ((y+dy) < 0) || ((y+dy) >= (ssize_t) image->rows))
944 p+=GetPixelChannels(image);
947 neighbor_offset=dy*(GetPixelChannels(image)*image->columns)+dx*
948 GetPixelChannels(image);
949 GetPixelInfoPixel(image,p+neighbor_offset,&target);
950 if (IsFuzzyEquivalencePixelInfo(&pixel,&target) == MagickFalse)
952 p+=GetPixelChannels(image);
958 offset=y*image->columns+x;
959 neighbor_offset=dy*image->columns+dx;
961 status=GetMatrixElement(equivalences,ox,0,&obj);
965 status=GetMatrixElement(equivalences,ox,0,&obj);
967 oy=offset+neighbor_offset;
968 status=GetMatrixElement(equivalences,oy,0,&obj);
972 status=GetMatrixElement(equivalences,oy,0,&obj);
976 status=SetMatrixElement(equivalences,oy,0,&ox);
981 status=SetMatrixElement(equivalences,ox,0,&oy);
985 status=GetMatrixElement(equivalences,ox,0,&obj);
988 status=GetMatrixElement(equivalences,ox,0,&obj);
989 status=SetMatrixElement(equivalences,ox,0,&root);
991 oy=offset+neighbor_offset;
992 status=GetMatrixElement(equivalences,oy,0,&obj);
995 status=GetMatrixElement(equivalences,oy,0,&obj);
996 status=SetMatrixElement(equivalences,oy,0,&root);
998 status=SetMatrixElement(equivalences,y*image->columns+x,0,&root);
999 p+=GetPixelChannels(image);
1007 component_view=AcquireAuthenticCacheView(component_image,exception);
1008 for (y=0; y < (ssize_t) component_image->rows; y++)
1019 if (status == MagickFalse)
1021 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
1022 q=QueueCacheViewAuthenticPixels(component_view,0,y,component_image->columns,
1024 if ((p == (
const Quantum *) NULL) || (q == (Quantum *) NULL))
1029 for (x=0; x < (ssize_t) component_image->columns; x++)
1035 offset=y*image->columns+x;
1036 status=GetMatrixElement(equivalences,offset,0,&
id);
1038 status=GetMatrixElement(equivalences,
id,0,&
id);
1042 if (
id >= (ssize_t) MaxColormapSize)
1045 status=SetMatrixElement(equivalences,offset,0,&
id);
1046 if (x <
object[
id].bounding_box.x)
1047 object[id].bounding_box.x=x;
1048 if (x >= (ssize_t)
object[
id].bounding_box.width)
1049 object[id].bounding_box.width=(size_t) x;
1050 if (y <
object[
id].bounding_box.y)
1051 object[id].bounding_box.y=y;
1052 if (y >= (ssize_t)
object[id].bounding_box.height)
1053 object[
id].bounding_box.height=(
size_t) y;
1054 object[id].color.red+=QuantumScale*GetPixelRed(image,p);
1055 object[id].color.green+=QuantumScale*GetPixelGreen(image,p);
1056 object[id].color.blue+=QuantumScale*GetPixelBlue(image,p);
1057 if (image->alpha_trait != UndefinedPixelTrait)
1058 object[id].color.alpha+=QuantumScale*GetPixelAlpha(image,p);
1059 if (image->colorspace == CMYKColorspace)
1060 object[id].color.black+=QuantumScale*GetPixelBlack(image,p);
1061 object[id].centroid.x+=x;
1062 object[id].centroid.y+=y;
1064 SetPixelIndex(component_image,(Quantum)
id,q);
1065 p+=GetPixelChannels(image);
1066 q+=GetPixelChannels(component_image);
1068 if (n > (ssize_t) MaxColormapSize)
1070 if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
1072 if (image->progress_monitor != (MagickProgressMonitor) NULL)
1078 proceed=SetImageProgress(image,ConnectedComponentsImageTag,progress,
1080 if (proceed == MagickFalse)
1084 component_view=DestroyCacheView(component_view);
1085 image_view=DestroyCacheView(image_view);
1086 equivalences=DestroyMatrixInfo(equivalences);
1087 if (n > (ssize_t) MaxColormapSize)
1089 object=(
CCObjectInfo *) RelinquishMagickMemory(
object);
1090 component_image=DestroyImage(component_image);
1091 ThrowImageException(ResourceLimitError,
"TooManyObjects");
1096 component_image->colors=(size_t) n;
1097 for (i=0; i < (ssize_t) component_image->colors; i++)
1099 object[i].bounding_box.width-=(
object[i].bounding_box.x-1);
1100 object[i].bounding_box.height-=(
object[i].bounding_box.y-1);
1101 object[i].color.red/=(QuantumScale*
object[i].area);
1102 object[i].color.green/=(QuantumScale*
object[i].area);
1103 object[i].color.blue/=(QuantumScale*
object[i].area);
1104 if (image->alpha_trait != UndefinedPixelTrait)
1105 object[i].color.alpha/=(QuantumScale*
object[i].area);
1106 if (image->colorspace == CMYKColorspace)
1107 object[i].color.black/=(QuantumScale*
object[i].area);
1108 object[i].centroid.x/=
object[i].area;
1109 object[i].centroid.y/=
object[i].area;
1110 max_threshold+=
object[i].area;
1111 if (
object[i].area >
object[background_id].area)
1114 max_threshold+=MagickEpsilon;
1116 artifact=GetImageArtifact(image,
"connected-components:background-id");
1117 if (artifact != (
const char *) NULL)
1118 background_id=(ssize_t) StringToLong(artifact);
1119 artifact=GetImageArtifact(image,
"connected-components:area-threshold");
1120 if (artifact != (
const char *) NULL)
1125 (void) sscanf(artifact,
"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1126 for (i=0; i < (ssize_t) component_image->colors; i++)
1127 if (((
object[i].area < min_threshold) ||
1128 (
object[i].area >= max_threshold)) && (i != background_id))
1129 object[i].merge=MagickTrue;
1131 artifact=GetImageArtifact(image,
"connected-components:keep-colors");
1132 if (artifact != (
const char *) NULL)
1140 for (i=0; i < (ssize_t) component_image->colors; i++)
1141 object[i].merge=MagickTrue;
1142 for (p=artifact; ; )
1145 color[MagickPathExtent];
1153 for (q=p; *q !=
'\0'; q++)
1156 (void) CopyMagickString(color,p,(
size_t) MagickMin(q-p+1,
1158 (void) QueryColorCompliance(color,AllCompliance,&pixel,exception);
1159 for (i=0; i < (ssize_t) component_image->colors; i++)
1160 if (IsFuzzyEquivalencePixelInfo(&
object[i].color,&pixel) != MagickFalse)
1161 object[i].merge=MagickFalse;
1167 artifact=GetImageArtifact(image,
"connected-components:keep-ids");
1168 if (artifact == (
const char *) NULL)
1169 artifact=GetImageArtifact(image,
"connected-components:keep");
1170 if (artifact != (
const char *) NULL)
1175 for (i=0; i < (ssize_t) component_image->colors; i++)
1176 object[i].merge=MagickTrue;
1177 for (c=(
char *) artifact; *c !=
'\0'; )
1179 while ((isspace((
int) ((
unsigned char) *c)) != 0) || (*c ==
','))
1181 first=(ssize_t) strtol(c,&c,10);
1183 first+=(ssize_t) component_image->colors;
1185 while (isspace((
int) ((
unsigned char) *c)) != 0)
1189 last=(ssize_t) strtol(c+1,&c,10);
1191 last+=(ssize_t) component_image->colors;
1193 step=(ssize_t) (first > last ? -1 : 1);
1194 for ( ; first != (last+step); first+=step)
1195 object[first].merge=MagickFalse;
1198 artifact=GetImageArtifact(image,
"connected-components:keep-top");
1199 if (artifact != (
const char *) NULL)
1210 top_ids=(ssize_t) StringToLong(artifact);
1211 top_objects=(
CCObjectInfo *) AcquireQuantumMemory(component_image->colors,
1212 sizeof(*top_objects));
1215 object=(
CCObjectInfo *) RelinquishMagickMemory(
object);
1216 component_image=DestroyImage(component_image);
1217 ThrowImageException(ResourceLimitError,
"MemoryAllocationFailed");
1219 (void) memcpy(top_objects,
object,component_image->colors*
sizeof(*
object));
1220 qsort((
void *) top_objects,component_image->colors,
sizeof(*top_objects),
1221 CCObjectInfoCompare);
1222 for (i=top_ids+1; i < (ssize_t) component_image->colors; i++)
1223 object[top_objects[i].id].merge=MagickTrue;
1224 top_objects=(
CCObjectInfo *) RelinquishMagickMemory(top_objects);
1226 artifact=GetImageArtifact(image,
"connected-components:remove-colors");
1227 if (artifact != (
const char *) NULL)
1235 for (p=artifact; ; )
1238 color[MagickPathExtent];
1246 for (q=p; *q !=
'\0'; q++)
1249 (void) CopyMagickString(color,p,(
size_t) MagickMin(q-p+1,
1251 (void) QueryColorCompliance(color,AllCompliance,&pixel,exception);
1252 for (i=0; i < (ssize_t) component_image->colors; i++)
1253 if (IsFuzzyEquivalencePixelInfo(&
object[i].color,&pixel) != MagickFalse)
1254 object[i].merge=MagickTrue;
1260 artifact=GetImageArtifact(image,
"connected-components:remove-ids");
1261 if (artifact == (
const char *) NULL)
1262 artifact=GetImageArtifact(image,
"connected-components:remove");
1263 if (artifact != (
const char *) NULL)
1264 for (c=(
char *) artifact; *c !=
'\0'; )
1269 while ((isspace((
int) ((
unsigned char) *c)) != 0) || (*c ==
','))
1271 first=(ssize_t) strtol(c,&c,10);
1273 first+=(ssize_t) component_image->colors;
1275 while (isspace((
int) ((
unsigned char) *c)) != 0)
1279 last=(ssize_t) strtol(c+1,&c,10);
1281 last+=(ssize_t) component_image->colors;
1283 step=(ssize_t) (first > last ? -1 : 1);
1284 for ( ; first != (last+step); first+=step)
1285 object[first].merge=MagickTrue;
1287 artifact=GetImageArtifact(image,
"connected-components:perimeter-threshold");
1288 if (artifact != (
const char *) NULL)
1293 (void) sscanf(artifact,
"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1294 metrics[++n]=
"perimeter";
1295 PerimeterThreshold(image,
object,n,exception);
1296 for (i=0; i < (ssize_t) component_image->colors; i++)
1297 if (((
object[i].metric[n] < min_threshold) ||
1298 (
object[i].metric[n] >= max_threshold)) && (i != background_id))
1299 object[i].merge=MagickTrue;
1301 artifact=GetImageArtifact(image,
"connected-components:circularity-threshold");
1302 if (artifact != (
const char *) NULL)
1307 (void) sscanf(artifact,
"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1308 metrics[++n]=
"circularity";
1309 CircularityThreshold(image,
object,n,exception);
1310 for (i=0; i < (ssize_t) component_image->colors; i++)
1311 if (((
object[i].metric[n] < min_threshold) ||
1312 (
object[i].metric[n] >= max_threshold)) && (i != background_id))
1313 object[i].merge=MagickTrue;
1315 artifact=GetImageArtifact(image,
"connected-components:diameter-threshold");
1316 if (artifact != (
const char *) NULL)
1321 (void) sscanf(artifact,
"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1322 metrics[++n]=
"diameter";
1323 for (i=0; i < (ssize_t) component_image->colors; i++)
1325 object[i].metric[n]=ceil(sqrt(4.0*
object[i].area/MagickPI)-0.5);
1326 if (((
object[i].metric[n] < min_threshold) ||
1327 (
object[i].metric[n] >= max_threshold)) && (i != background_id))
1328 object[i].merge=MagickTrue;
1331 artifact=GetImageArtifact(image,
"connected-components:major-axis-threshold");
1332 if (artifact != (
const char *) NULL)
1337 (void) sscanf(artifact,
"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1338 metrics[++n]=
"major-axis";
1339 MajorAxisThreshold(component_image,
object,n,exception);
1340 for (i=0; i < (ssize_t) component_image->colors; i++)
1341 if (((
object[i].metric[n] < min_threshold) ||
1342 (
object[i].metric[n] >= max_threshold)) && (i != background_id))
1343 object[i].merge=MagickTrue;
1345 artifact=GetImageArtifact(image,
"connected-components:minor-axis-threshold");
1346 if (artifact != (
const char *) NULL)
1351 (void) sscanf(artifact,
"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1352 metrics[++n]=
"minor-axis";
1353 MinorAxisThreshold(component_image,
object,n,exception);
1354 for (i=0; i < (ssize_t) component_image->colors; i++)
1355 if (((
object[i].metric[n] < min_threshold) ||
1356 (
object[i].metric[n] >= max_threshold)) && (i != background_id))
1357 object[i].merge=MagickTrue;
1359 artifact=GetImageArtifact(image,
"connected-components:eccentricity-threshold");
1360 if (artifact != (
const char *) NULL)
1365 (void) sscanf(artifact,
"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1366 metrics[++n]=
"eccentricy";
1367 EccentricityThreshold(component_image,
object,n,exception);
1368 for (i=0; i < (ssize_t) component_image->colors; i++)
1369 if (((
object[i].metric[n] < min_threshold) ||
1370 (
object[i].metric[n] >= max_threshold)) && (i != background_id))
1371 object[i].merge=MagickTrue;
1373 artifact=GetImageArtifact(image,
"connected-components:angle-threshold");
1374 if (artifact != (
const char *) NULL)
1379 (void) sscanf(artifact,
"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1380 metrics[++n]=
"angle";
1381 AngleThreshold(component_image,
object,n,exception);
1382 for (i=0; i < (ssize_t) component_image->colors; i++)
1383 if (((
object[i].metric[n] < min_threshold) ||
1384 (
object[i].metric[n] >= max_threshold)) && (i != background_id))
1385 object[i].merge=MagickTrue;
1390 component_view=AcquireAuthenticCacheView(component_image,exception);
1391 object_view=AcquireVirtualCacheView(component_image,exception);
1392 for (i=0; i < (ssize_t) component_image->colors; i++)
1403 if (status == MagickFalse)
1405 if ((
object[i].merge == MagickFalse) || (i == background_id))
1410 for (j=0; j < (ssize_t) component_image->colors; j++)
1412 bounding_box=
object[i].bounding_box;
1413 for (y=0; y < (ssize_t) bounding_box.height; y++)
1421 if (status == MagickFalse)
1423 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
1424 bounding_box.y+y,bounding_box.width,1,exception);
1425 if (p == (
const Quantum *) NULL)
1430 for (x=0; x < (ssize_t) bounding_box.width; x++)
1435 if (status == MagickFalse)
1437 j=(ssize_t) GetPixelIndex(component_image,p);
1439 for (k=0; k < (ssize_t) (connectivity > 4 ? 4 : 2); k++)
1447 if (status == MagickFalse)
1449 dx=connectivity > 4 ? connect8[k][1] : connect4[k][1];
1450 dy=connectivity > 4 ? connect8[k][0] : connect4[k][0];
1451 q=GetCacheViewVirtualPixels(object_view,bounding_box.x+x+dx,
1452 bounding_box.y+y+dy,1,1,exception);
1453 if (q == (
const Quantum *) NULL)
1458 j=(ssize_t) GetPixelIndex(component_image,q);
1462 p+=GetPixelChannels(component_image);
1469 for (j=1; j < (ssize_t) component_image->colors; j++)
1470 if (
object[j].census >
object[
id].census)
1473 for (y=0; y < (ssize_t) bounding_box.height; y++)
1481 if (status == MagickFalse)
1483 q=GetCacheViewAuthenticPixels(component_view,bounding_box.x,
1484 bounding_box.y+y,bounding_box.width,1,exception);
1485 if (q == (Quantum *) NULL)
1490 for (x=0; x < (ssize_t) bounding_box.width; x++)
1492 if ((ssize_t) GetPixelIndex(component_image,q) == i)
1493 SetPixelIndex(component_image,(Quantum) id,q);
1494 q+=GetPixelChannels(component_image);
1496 if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
1500 object_view=DestroyCacheView(object_view);
1501 component_view=DestroyCacheView(component_view);
1502 artifact=GetImageArtifact(image,
"connected-components:mean-color");
1503 if (IsStringTrue(artifact) != MagickFalse)
1508 for (i=0; i < (ssize_t) component_image->colors; i++)
1509 component_image->colormap[i]=
object[i].color;
1511 (void) SyncImage(component_image,exception);
1512 artifact=GetImageArtifact(image,
"connected-components:verbose");
1513 if ((IsStringTrue(artifact) != MagickFalse) ||
1523 for (i=0; i < (ssize_t) component_image->colors; i++)
1525 object[i].bounding_box.width=0;
1526 object[i].bounding_box.height=0;
1527 object[i].bounding_box.x=(ssize_t) component_image->columns;
1528 object[i].bounding_box.y=(ssize_t) component_image->rows;
1529 object[i].centroid.x=0;
1530 object[i].centroid.y=0;
1531 object[i].census=
object[i].area == 0.0 ? 0.0 : 1.0;
1534 component_view=AcquireVirtualCacheView(component_image,exception);
1535 for (y=0; y < (ssize_t) component_image->rows; y++)
1543 if (status == MagickFalse)
1545 p=GetCacheViewVirtualPixels(component_view,0,y,component_image->columns,
1547 if (p == (
const Quantum *) NULL)
1552 for (x=0; x < (ssize_t) component_image->columns; x++)
1557 id=(size_t) GetPixelIndex(component_image,p);
1558 if (x <
object[
id].bounding_box.x)
1559 object[id].bounding_box.x=x;
1560 if (x > (ssize_t)
object[id].bounding_box.width)
1561 object[
id].bounding_box.width=(
size_t) x;
1562 if (y <
object[
id].bounding_box.y)
1563 object[id].bounding_box.y=y;
1564 if (y > (ssize_t)
object[id].bounding_box.height)
1565 object[
id].bounding_box.height=(
size_t) y;
1566 object[id].centroid.x+=x;
1567 object[id].centroid.y+=y;
1569 p+=GetPixelChannels(component_image);
1572 for (i=0; i < (ssize_t) component_image->colors; i++)
1574 object[i].bounding_box.width-=(
object[i].bounding_box.x-1);
1575 object[i].bounding_box.height-=(
object[i].bounding_box.y-1);
1576 object[i].centroid.x=
object[i].centroid.x/
object[i].area;
1577 object[i].centroid.y=
object[i].centroid.y/
object[i].area;
1579 component_view=DestroyCacheView(component_view);
1581 artifact=GetImageArtifact(image,
"connected-components:sort-order");
1582 if (artifact != (
const char *) NULL)
1583 if (LocaleCompare(artifact,
"decreasing") == 0)
1586 artifact=GetImageArtifact(image,
"connected-components:sort");
1587 if (artifact != (
const char *) NULL)
1589 if (LocaleCompare(artifact,
"area") == 0)
1591 if (LocaleCompare(artifact,
"width") == 0)
1593 if (LocaleCompare(artifact,
"height") == 0)
1595 if (LocaleCompare(artifact,
"x") == 0)
1597 if (LocaleCompare(artifact,
"y") == 0)
1600 for (i=0; i < (ssize_t) component_image->colors; i++)
1601 object[i].key=order*key;
1602 qsort((
void *)
object,component_image->colors,
sizeof(*
object),
1603 CCObjectInfoCompare);
1609 artifact=GetImageArtifact(image,
1610 "connected-components:exclude-header");
1611 if (IsStringTrue(artifact) == MagickFalse)
1613 (void) fprintf(stdout,
"Objects (");
1614 artifact=GetImageArtifact(image,
1615 "connected-components:exclude-ids");
1616 if (IsStringTrue(artifact) == MagickFalse)
1617 (void) fprintf(stdout,
"id: ");
1618 (void) fprintf(stdout,
"bounding-box centroid area mean-color");
1619 for (j=0; j <= n; j++)
1620 (
void) fprintf(stdout,
" %s",metrics[j]);
1621 (void) fprintf(stdout,
"):\n");
1623 for (i=0; i < (ssize_t) component_image->colors; i++)
1624 if (
object[i].census > 0.0)
1627 mean_color[MagickPathExtent];
1629 GetColorTuple(&
object[i].color,MagickFalse,mean_color);
1630 (void) fprintf(stdout,
" ");
1631 artifact=GetImageArtifact(image,
1632 "connected-components:exclude-ids");
1633 if (IsStringTrue(artifact) == MagickFalse)
1634 (void) fprintf(stdout,
"%.20g: ",(
double)
object[i].id);
1635 (void) fprintf(stdout,
1636 "%.20gx%.20g%+.20g%+.20g %.1f,%.1f %.*g %s",(
double)
1637 object[i].bounding_box.width,(double)
1638 object[i].bounding_box.height,(
double)
1639 object[i].bounding_box.x,(double)
object[i].bounding_box.y,
1640 object[i].centroid.x,
object[i].centroid.y,
1641 GetMagickPrecision(),(double)
object[i].area,mean_color);
1642 for (j=0; j <= n; j++)
1643 (
void) fprintf(stdout,
" %.*g",GetMagickPrecision(),
1644 object[i].metric[j]);
1645 (void) fprintf(stdout,
"\n");
1650 object=(
CCObjectInfo *) RelinquishMagickMemory(
object);
1653 return(component_image);
1682 #define IntegralImageTag "Integral/Image"
1703 assert(image != (
const Image *) NULL);
1704 assert(image->signature == MagickCoreSignature);
1706 assert(exception->signature == MagickCoreSignature);
1707 if (IsEventLogging() != MagickFalse)
1708 (void) LogMagickEvent(TraceEvent,GetMagickModule(),
"%s",image->filename);
1709 integral_image=CloneImage(image,0,0,MagickTrue,exception);
1710 if (integral_image == (
Image *) NULL)
1711 return((
Image *) NULL);
1712 if (SetImageStorageClass(integral_image,DirectClass,exception) == MagickFalse)
1714 integral_image=DestroyImage(integral_image);
1715 return((
Image *) NULL);
1722 image_view=AcquireVirtualCacheView(integral_image,exception);
1723 integral_view=AcquireAuthenticCacheView(integral_image,exception);
1724 for (y=0; y < (ssize_t) integral_image->rows; y++)
1738 if (status == MagickFalse)
1740 p=GetCacheViewVirtualPixels(integral_view,0,y-1,integral_image->columns,1,
1742 q=GetCacheViewAuthenticPixels(integral_view,0,y,integral_image->columns,1,
1744 if ((p == (
const Quantum *) NULL) || (p == (Quantum *) NULL))
1749 for (x=0; x < (ssize_t) integral_image->columns; x++)
1754 for (i=0; i < (ssize_t) GetPixelChannels(integral_image); i++)
1759 PixelTrait traits = GetPixelChannelTraits(integral_image,
1761 if (traits == UndefinedPixelTrait)
1763 if ((traits & CopyPixelTrait) != 0)
1767 sum+=(q-GetPixelChannels(integral_image))[i];
1770 if ((x > 0) && (y > 0))
1771 sum-=(p-GetPixelChannels(integral_image))[i];
1772 q[i]=ClampToQuantum(sum);
1774 p+=GetPixelChannels(integral_image);
1775 q+=GetPixelChannels(integral_image);
1777 sync=SyncCacheViewAuthenticPixels(integral_view,exception);
1778 if (sync == MagickFalse)
1780 if (image->progress_monitor != (MagickProgressMonitor) NULL)
1786 proceed=SetImageProgress(integral_image,IntegralImageTag,progress,
1787 integral_image->rows);
1788 if (proceed == MagickFalse)
1792 integral_view=DestroyCacheView(integral_view);
1793 image_view=DestroyCacheView(image_view);
1794 if (status == MagickFalse)
1795 integral_image=DestroyImage(integral_image);
1796 return(integral_image);