2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6 % V V IIIII SSSSS IIIII OOO N N %
7 % V V I SS I O O NN N %
8 % V V I SSS I O O N N N %
9 % V V I SS I O O N NN %
10 % V IIIII SSSSS IIIII OOO N N %
13 % MagickCore Computer Vision Methods %
20 % Copyright 1999-2015 ImageMagick Studio LLC, a non-profit organization %
21 % dedicated to making software imaging solutions freely available. %
23 % You may not use this file except in compliance with the License. You may %
24 % obtain a copy of the License at %
26 % http://www.imagemagick.org/script/license.php %
28 % Unless required by applicable law or agreed to in writing, software %
29 % distributed under the License is distributed on an "AS IS" BASIS, %
30 % WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. %
31 % See the License for the specific language governing permissions and %
32 % limitations under the License. %
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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/colorspace.h"
46 #include "MagickCore/constitute.h"
47 #include "MagickCore/decorate.h"
48 #include "MagickCore/distort.h"
49 #include "MagickCore/draw.h"
50 #include "MagickCore/enhance.h"
51 #include "MagickCore/exception.h"
52 #include "MagickCore/exception-private.h"
53 #include "MagickCore/effect.h"
54 #include "MagickCore/gem.h"
55 #include "MagickCore/geometry.h"
56 #include "MagickCore/image-private.h"
57 #include "MagickCore/list.h"
58 #include "MagickCore/log.h"
59 #include "MagickCore/matrix.h"
60 #include "MagickCore/memory_.h"
61 #include "MagickCore/memory-private.h"
62 #include "MagickCore/monitor.h"
63 #include "MagickCore/monitor-private.h"
64 #include "MagickCore/montage.h"
65 #include "MagickCore/morphology.h"
66 #include "MagickCore/morphology-private.h"
67 #include "MagickCore/opencl-private.h"
68 #include "MagickCore/paint.h"
69 #include "MagickCore/pixel-accessor.h"
70 #include "MagickCore/pixel-private.h"
71 #include "MagickCore/property.h"
72 #include "MagickCore/quantum.h"
73 #include "MagickCore/quantum-private.h"
74 #include "MagickCore/resource_.h"
75 #include "MagickCore/signature-private.h"
76 #include "MagickCore/string_.h"
77 #include "MagickCore/string-private.h"
78 #include "MagickCore/thread-private.h"
79 #include "MagickCore/token.h"
80 #include "MagickCore/vision.h"
83 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
87 % C o n n e c t e d C o m p o n e n t s I m a g e %
91 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
93 % ConnectedComponentsImage() returns the connected-components of the image
94 % uniquely labeled. Choose from 4 or 8-way connectivity.
96 % The format of the ConnectedComponentsImage method is:
98 % Image *ConnectedComponentsImage(const Image *image,
99 % const size_t connectivity,ExceptionInfo *exception)
101 % A description of each parameter follows:
103 % o image: the image.
105 % o connectivity: how many neighbors to visit, choose from 4 or 8.
107 % o exception: return any errors or warnings in this structure.
111 typedef struct _CCObject
130 static int CCObjectCompare(const void *x,const void *y)
138 return((int) (q->area-(ssize_t) p->area));
141 static MagickBooleanType MergeConnectedComponents(Image *image,
142 const size_t number_objects,const double area_threshold,
143 ExceptionInfo *exception)
161 Collect statistics on unique objects.
163 object=(CCObject *) AcquireQuantumMemory(number_objects,sizeof(*object));
164 if (object == (CCObject *) NULL) {
165 (void) ThrowMagickException(exception,GetMagickModule(),ResourceLimitError,
166 "MemoryAllocationFailed","`%s'",image->filename);
169 (void) ResetMagickMemory(object,0,number_objects*sizeof(*object));
170 for (i=0; i < (ssize_t) number_objects; i++) {
172 object[i].bounding_box.x=(ssize_t) image->columns;
173 object[i].bounding_box.y=(ssize_t) image->rows;
176 image_view=AcquireVirtualCacheView(image,exception);
177 for (y=0; y < (ssize_t) image->rows; y++) {
178 register const Quantum
184 if (status == MagickFalse)
186 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
187 if (p == (const Quantum *) NULL) {
191 for (x=0; x < (ssize_t) image->columns; x++) {
193 if (x < object[i].bounding_box.x)
194 object[i].bounding_box.x=x;
195 if (x > (ssize_t) object[i].bounding_box.width)
196 object[i].bounding_box.width=(size_t) x;
197 if (y < object[i].bounding_box.y)
198 object[i].bounding_box.y=y;
199 if (y > (ssize_t) object[i].bounding_box.height)
200 object[i].bounding_box.height=(size_t) y;
202 p+=GetPixelChannels(image);
205 image_view=DestroyCacheView(image_view);
206 for (i=0; i < (ssize_t) number_objects; i++) {
207 object[i].bounding_box.width-=(object[i].bounding_box.x-1);
208 object[i].bounding_box.height-=(object[i].bounding_box.y-1);
211 Merge objects below area threshold.
213 image_view=AcquireAuthenticCacheView(image,exception);
214 for (i=0; i < (ssize_t) number_objects; i++) {
225 if (status == MagickFalse)
227 if ((double) object[i].area >= area_threshold)
229 for (j=0; j < (ssize_t) number_objects; j++)
231 bounding_box=object[i].bounding_box;
232 for (y=0; y < (ssize_t) bounding_box.height+2; y++) {
233 register const Quantum
239 if (status == MagickFalse)
241 p=GetCacheViewVirtualPixels(image_view,bounding_box.x-1,bounding_box.y+y-
242 1,bounding_box.width+2,1,exception);
243 if (p == (const Quantum *) NULL) {
247 for (x=0; x < (ssize_t) bounding_box.width+2; x++) {
251 p+=GetPixelChannels(image);
256 for (j=0; j < (ssize_t) number_objects; j++)
257 if (census < object[j].census) {
258 census=object[j].census;
261 for (y=0; y < (ssize_t) bounding_box.height; y++) {
268 if (status == MagickFalse)
270 q=GetCacheViewAuthenticPixels(image_view,bounding_box.x,bounding_box.y+y,
271 bounding_box.width,1,exception);
272 if (q == (Quantum *) NULL) {
276 for (x=0; x < (ssize_t) bounding_box.width; x++) {
277 if ((ssize_t) *q == i)
279 q+=GetPixelChannels(image);
281 if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
285 image_view=DestroyCacheView(image_view);
286 object=(CCObject *) RelinquishMagickMemory(object);
290 static MagickBooleanType StatisticsComponentsStatistics(const Image *image,
291 const Image *component_image,const size_t number_objects,
292 ExceptionInfo *exception)
311 Collect statistics on unique objects.
313 object=(CCObject *) AcquireQuantumMemory(number_objects,sizeof(*object));
314 if (object == (CCObject *) NULL) {
315 (void) ThrowMagickException(exception,GetMagickModule(),ResourceLimitError,
316 "MemoryAllocationFailed","`%s'",image->filename);
319 (void) ResetMagickMemory(object,0,number_objects*sizeof(*object));
320 for (i=0; i < (ssize_t) number_objects; i++) {
322 object[i].bounding_box.x=(ssize_t) component_image->columns;
323 object[i].bounding_box.y=(ssize_t) component_image->rows;
324 GetPixelInfo(image,&object[i].color);
327 image_view=AcquireVirtualCacheView(image,exception);
328 component_view=AcquireVirtualCacheView(component_image,exception);
329 for (y=0; y < (ssize_t) image->rows; y++) {
330 register const Quantum
337 if (status == MagickFalse)
339 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
340 q=GetCacheViewVirtualPixels(component_view,0,y,component_image->columns,1,
342 if ((p == (const Quantum *) NULL) || (q == (const Quantum *) NULL)) {
346 for (x=0; x < (ssize_t) image->columns; x++) {
348 if (x < object[i].bounding_box.x)
349 object[i].bounding_box.x=x;
350 if (x > (ssize_t) object[i].bounding_box.width)
351 object[i].bounding_box.width=(size_t) x;
352 if (y < object[i].bounding_box.y)
353 object[i].bounding_box.y=y;
354 if (y > (ssize_t) object[i].bounding_box.height)
355 object[i].bounding_box.height=(size_t) y;
356 object[i].color.red+=GetPixelRed(image,p);
357 object[i].color.green+=GetPixelGreen(image,p);
358 object[i].color.blue+=GetPixelBlue(image,p);
359 object[i].color.alpha+=GetPixelAlpha(image,p);
360 object[i].color.black+=GetPixelBlack(image,p);
361 object[i].centroid.x+=x;
362 object[i].centroid.y+=y;
364 p+=GetPixelChannels(image);
365 q+=GetPixelChannels(component_image);
368 for (i=0; i < (ssize_t) number_objects; i++) {
369 object[i].bounding_box.width-=(object[i].bounding_box.x-1);
370 object[i].bounding_box.height-=(object[i].bounding_box.y-1);
371 object[i].color.red=ClampToQuantum(object[i].color.red/object[i].area);
372 object[i].color.green=ClampToQuantum(object[i].color.green/object[i].area);
373 object[i].color.blue=ClampToQuantum(object[i].color.blue/object[i].area);
374 object[i].color.alpha=ClampToQuantum(object[i].color.alpha/object[i].area);
375 object[i].color.black=ClampToQuantum(object[i].color.black/object[i].area);
376 object[i].centroid.x=object[i].centroid.x/object[i].area;
377 object[i].centroid.y=object[i].centroid.y/object[i].area;
379 component_view=DestroyCacheView(component_view);
380 image_view=DestroyCacheView(image_view);
382 Report statistics on unique objects.
384 qsort((void *) object,number_objects,sizeof(*object),CCObjectCompare);
385 (void) fprintf(stdout,
386 "Objects (id: bounding-box centroid area mean-color):\n");
387 for (i=0; i < (ssize_t) number_objects; i++) {
389 mean_color[MaxTextExtent];
391 if (status == MagickFalse)
393 if (object[i].area < MagickEpsilon)
395 GetColorTuple(&object[i].color,MagickFalse,mean_color);
396 (void) fprintf(stdout,
397 " %.20g: %.20gx%.20g%+.20g%+.20g %.1f,%.1f %.20g %s\n",(double)
398 object[i].id,(double) object[i].bounding_box.width,(double)
399 object[i].bounding_box.height,(double) object[i].bounding_box.x,
400 (double) object[i].bounding_box.y,object[i].centroid.x,
401 object[i].centroid.y,(double) object[i].area,mean_color);
403 object=(CCObject *) RelinquishMagickMemory(object);
407 MagickExport Image *ConnectedComponentsImage(const Image *image,
408 const size_t connectivity,ExceptionInfo *exception)
410 #define ConnectedComponentsImageTag "ConnectedComponents/Image"
442 Initialize connected components image attributes.
444 assert(image != (Image *) NULL);
445 assert(image->signature == MagickSignature);
446 if (image->debug != MagickFalse)
447 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
448 assert(exception != (ExceptionInfo *) NULL);
449 assert(exception->signature == MagickSignature);
450 component_image=CloneImage(image,image->columns,image->rows,MagickTrue,
452 if (component_image == (Image *) NULL)
453 return((Image *) NULL);
454 component_image->depth=MAGICKCORE_QUANTUM_DEPTH;
455 component_image->colorspace=GRAYColorspace;
456 status=SetImageStorageClass(component_image,DirectClass,exception);
457 if (status == MagickFalse) {
458 component_image=DestroyImage(component_image);
459 return((Image *) NULL);
462 Initialize connected components equivalences.
464 size=image->columns*image->rows;
465 if (image->columns != (size/image->rows)) {
466 component_image=DestroyImage(component_image);
467 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
469 equivalences=AcquireMatrixInfo(size,1,sizeof(ssize_t),exception);
470 if (equivalences == (MatrixInfo *) NULL) {
471 component_image=DestroyImage(component_image);
472 return((Image *) NULL);
474 for (n=0; n < (ssize_t) (image->columns*image->rows); n++)
475 status=SetMatrixElement(equivalences,n,0,&n);
477 Find connected components.
481 image_view=AcquireVirtualCacheView(image,exception);
482 for (n=0; n < (ssize_t) (connectivity > 4 ? 4 : 2); n++) {
484 connect4[2][2] = { { -1, 0 }, { 0, -1 } },
485 connect8[4][2] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 } },
489 if (status == MagickFalse)
491 dy=connectivity > 4 ? connect8[n][0] : connect4[n][0];
492 dx=connectivity > 4 ? connect8[n][1] : connect4[n][1];
493 for (y=0; y < (ssize_t) image->rows; y++) {
494 register const Quantum
500 if (status == MagickFalse)
502 p=GetCacheViewVirtualPixels(image_view,0,y-1,image->columns,3,exception);
503 if (p == (const Quantum *) NULL) {
507 p+=image->columns*GetPixelChannels(image);
508 for (x=0; x < (ssize_t) image->columns; x++) {
522 Is neighbor an authentic pixel and a different color than the pixel?
524 GetPixelInfoPixel(image,p,&pixel);
525 neighbor_offset=dy*(image->columns*GetPixelChannels(image))+dx*
526 GetPixelChannels(image);
527 GetPixelInfoPixel(image,p+neighbor_offset,&target);
528 if (((x+dx) < 0) || ((x+dx) >= (ssize_t) image->columns) ||
529 ((y+dy) < 0) || ((y+dy) >= (ssize_t) image->rows) ||
530 (IsFuzzyEquivalencePixelInfo(&pixel,&target) == MagickFalse)) {
531 p+=GetPixelChannels(image);
535 Resolve this equivalence.
537 offset=y*image->columns+x;
538 neighbor_offset=dy*image->columns+dx;
540 status=GetMatrixElement(equivalences,ox,0,&object);
541 while (object != ox) {
543 status=GetMatrixElement(equivalences,ox,0,&object);
545 oy=offset+neighbor_offset;
546 status=GetMatrixElement(equivalences,oy,0,&object);
547 while (object != oy) {
549 status=GetMatrixElement(equivalences,oy,0,&object);
552 status=SetMatrixElement(equivalences,oy,0,&ox);
555 status=SetMatrixElement(equivalences,ox,0,&oy);
559 status=GetMatrixElement(equivalences,ox,0,&object);
560 while (object != root) {
561 status=GetMatrixElement(equivalences,ox,0,&object);
562 status=SetMatrixElement(equivalences,ox,0,&root);
564 oy=offset+neighbor_offset;
565 status=GetMatrixElement(equivalences,oy,0,&object);
566 while (object != root) {
567 status=GetMatrixElement(equivalences,oy,0,&object);
568 status=SetMatrixElement(equivalences,oy,0,&root);
570 status=SetMatrixElement(equivalences,y*image->columns+x,0,&root);
571 p+=GetPixelChannels(image);
575 image_view=DestroyCacheView(image_view);
577 Label connected components.
580 component_view=AcquireAuthenticCacheView(component_image,exception);
581 for (y=0; y < (ssize_t) component_image->rows; y++) {
588 if (status == MagickFalse)
590 q=QueueCacheViewAuthenticPixels(component_view,0,y,component_image->columns,
592 if (q == (Quantum *) NULL) {
596 for (x=0; x < (ssize_t) component_image->columns; x++) {
601 offset=y*image->columns+x;
602 status=GetMatrixElement(equivalences,offset,0,&object);
603 if (object == offset) {
605 status=SetMatrixElement(equivalences,offset,0,&object);
607 status=GetMatrixElement(equivalences,object,0,&object);
608 status=SetMatrixElement(equivalences,offset,0,&object);
610 *q=(Quantum) (object > (ssize_t) QuantumRange ? (ssize_t) QuantumRange :
612 q+=GetPixelChannels(component_image);
614 if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
616 if (image->progress_monitor != (MagickProgressMonitor) NULL) {
620 proceed=SetImageProgress(image,ConnectedComponentsImageTag,progress++,
622 if (proceed == MagickFalse)
626 component_view=DestroyCacheView(component_view);
627 equivalences=DestroyMatrixInfo(equivalences);
628 if (n > QuantumRange) {
629 component_image=DestroyImage(component_image);
630 ThrowImageException(ResourceLimitError,"TooManyObjects");
632 artifact=GetImageArtifact(image,"connected-components:area-threshold");
634 if (artifact != (const char *) NULL)
635 area_threshold=StringToDouble(artifact,(char **) NULL);
636 if (area_threshold > 0.0)
637 status=MergeConnectedComponents(component_image,(size_t) n,area_threshold,
639 artifact=GetImageArtifact(image,"connected-components:verbose");
640 if (IsStringTrue(artifact) != MagickFalse)
641 status=StatisticsComponentsStatistics(image,component_image,(size_t) n,
643 if (status == MagickFalse)
644 component_image=DestroyImage(component_image);
645 return(component_image);