1 /*
2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3 % %
4 % %
5 % %
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 %
11 % %
12 % %
13 % MagickCore Computer Vision Methods %
14 % %
15 % Software Design %
16 % Cristy %
17 % September 2014 %
18 % %
19 % %
20 % Copyright 1999-2021 ImageMagick Studio LLC, a non-profit organization %
21 % dedicated to making software imaging solutions freely available. %
22 % %
23 % You may not use this file except in compliance with the License. You may %
24 % obtain a copy of the License at %
25 % %
26 % https://imagemagick.org/script/license.php %
27 % %
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. %
33 % %
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35 %
36 %
37 */
38
39 #include "magick/studio.h"
40 #include "magick/artifact.h"
41 #include "magick/blob.h"
42 #include "magick/cache-view.h"
43 #include "magick/color.h"
44 #include "magick/color-private.h"
45 #include "magick/colormap.h"
46 #include "magick/colorspace.h"
47 #include "magick/constitute.h"
48 #include "magick/decorate.h"
49 #include "magick/distort.h"
50 #include "magick/draw.h"
51 #include "magick/enhance.h"
52 #include "magick/exception.h"
53 #include "magick/exception-private.h"
54 #include "magick/effect.h"
55 #include "magick/gem.h"
56 #include "magick/geometry.h"
57 #include "magick/image-private.h"
58 #include "magick/list.h"
59 #include "magick/log.h"
60 #include "magick/matrix.h"
61 #include "magick/memory_.h"
62 #include "magick/memory-private.h"
63 #include "magick/monitor.h"
64 #include "magick/monitor-private.h"
65 #include "magick/montage.h"
66 #include "magick/morphology.h"
67 #include "magick/morphology-private.h"
68 #include "magick/opencl-private.h"
69 #include "magick/paint.h"
70 #include "magick/pixel-accessor.h"
71 #include "magick/pixel-private.h"
72 #include "magick/property.h"
73 #include "magick/quantum.h"
74 #include "magick/resource_.h"
75 #include "magick/signature-private.h"
76 #include "magick/string_.h"
77 #include "magick/string-private.h"
78 #include "magick/thread-private.h"
79 #include "magick/token.h"
80 #include "magick/vision.h"
81
82 /*
83 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
84 % %
85 % %
86 % %
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 %
88 % %
89 % %
90 % %
91 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92 %
93 % ConnectedComponentsImage() returns the connected-components of the image
94 % uniquely labeled. Choose from 4 or 8-way connectivity.
95 %
96 % The format of the ConnectedComponentsImage method is:
97 %
98 % Image *ConnectedComponentsImage(const Image *image,
99 % const size_t connectivity,ExceptionInfo *exception)
100 %
101 % A description of each parameter follows:
102 %
103 % o image: the image.
104 %
105 % o connectivity: how many neighbors to visit, choose from 4 or 8.
106 %
107 % o exception: return any errors or warnings in this structure.
108 %
109 */
110
111 typedef struct _CCObjectInfo
112 {
113 ssize_t
114 id;
115
116 RectangleInfo
117 bounding_box;
118
119 MagickPixelPacket
120 color;
121
122 PointInfo
123 centroid;
124
125 double
126 area,
127 census;
128
129 MagickBooleanType
130 merge;
131 } CCObjectInfo;
132
CCObjectInfoCompare(const void * x,const void * y)133 static int CCObjectInfoCompare(const void *x,const void *y)
134 {
135 CCObjectInfo
136 *p,
137 *q;
138
139 p=(CCObjectInfo *) x;
140 q=(CCObjectInfo *) y;
141 return((int) (q->area-(ssize_t) p->area));
142 }
143
ConnectedComponentsImage(const Image * image,const size_t connectivity,ExceptionInfo * exception)144 MagickExport Image *ConnectedComponentsImage(const Image *image,
145 const size_t connectivity,ExceptionInfo *exception)
146 {
147 #define ConnectedComponentsImageTag "ConnectedComponents/Image"
148
149 CacheView
150 *component_view,
151 *image_view,
152 *object_view;
153
154 CCObjectInfo
155 *object;
156
157 char
158 *c;
159
160 const char
161 *artifact;
162
163 double
164 max_threshold,
165 min_threshold;
166
167 Image
168 *component_image;
169
170 MagickBooleanType
171 status;
172
173 MagickOffsetType
174 progress;
175
176 MatrixInfo
177 *equivalences;
178
179 ssize_t
180 i;
181
182 size_t
183 size;
184
185 ssize_t
186 background_id,
187 connect4[2][2] = { { -1, 0 }, { 0, -1 } },
188 connect8[4][2] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 } },
189 dx,
190 dy,
191 first,
192 last,
193 n,
194 step,
195 y;
196
197 /*
198 Initialize connected components image attributes.
199 */
200 assert(image != (Image *) NULL);
201 assert(image->signature == MagickCoreSignature);
202 if (image->debug != MagickFalse)
203 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
204 assert(exception != (ExceptionInfo *) NULL);
205 assert(exception->signature == MagickCoreSignature);
206 component_image=CloneImage(image,0,0,MagickTrue,exception);
207 if (component_image == (Image *) NULL)
208 return((Image *) NULL);
209 component_image->depth=MAGICKCORE_QUANTUM_DEPTH;
210 if (AcquireImageColormap(component_image,MaxColormapSize) == MagickFalse)
211 {
212 component_image=DestroyImage(component_image);
213 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
214 }
215 /*
216 Initialize connected components equivalences.
217 */
218 size=image->columns*image->rows;
219 if (image->columns != (size/image->rows))
220 {
221 component_image=DestroyImage(component_image);
222 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
223 }
224 equivalences=AcquireMatrixInfo(size,1,sizeof(ssize_t),exception);
225 if (equivalences == (MatrixInfo *) NULL)
226 {
227 component_image=DestroyImage(component_image);
228 return((Image *) NULL);
229 }
230 for (n=0; n < (ssize_t) (image->columns*image->rows); n++)
231 (void) SetMatrixElement(equivalences,n,0,&n);
232 object=(CCObjectInfo *) AcquireQuantumMemory(MaxColormapSize,sizeof(*object));
233 if (object == (CCObjectInfo *) NULL)
234 {
235 equivalences=DestroyMatrixInfo(equivalences);
236 component_image=DestroyImage(component_image);
237 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
238 }
239 (void) memset(object,0,MaxColormapSize*sizeof(*object));
240 for (i=0; i < (ssize_t) MaxColormapSize; i++)
241 {
242 object[i].id=i;
243 object[i].bounding_box.x=(ssize_t) image->columns;
244 object[i].bounding_box.y=(ssize_t) image->rows;
245 GetMagickPixelPacket(image,&object[i].color);
246 }
247 /*
248 Find connected components.
249 */
250 status=MagickTrue;
251 progress=0;
252 image_view=AcquireVirtualCacheView(image,exception);
253 for (n=0; n < (ssize_t) (connectivity > 4 ? 4 : 2); n++)
254 {
255 if (status == MagickFalse)
256 continue;
257 dx=connectivity > 4 ? connect8[n][1] : connect4[n][1];
258 dy=connectivity > 4 ? connect8[n][0] : connect4[n][0];
259 for (y=0; y < (ssize_t) image->rows; y++)
260 {
261 const PixelPacket
262 *magick_restrict p;
263
264 ssize_t
265 x;
266
267 if (status == MagickFalse)
268 continue;
269 p=GetCacheViewVirtualPixels(image_view,0,y-1,image->columns,3,exception);
270 if (p == (const PixelPacket *) NULL)
271 {
272 status=MagickFalse;
273 continue;
274 }
275 p+=image->columns;
276 for (x=0; x < (ssize_t) image->columns; x++)
277 {
278 ssize_t
279 neighbor_offset,
280 obj,
281 offset,
282 ox,
283 oy,
284 root;
285
286 /*
287 Is neighbor an authentic pixel and a different color than the pixel?
288 */
289 if (((x+dx) < 0) || ((x+dx) >= (ssize_t) image->columns) ||
290 ((y+dy) < 0) || ((y+dy) >= (ssize_t) image->rows))
291 {
292 p++;
293 continue;
294 }
295 neighbor_offset=dy*image->columns+dx;
296 if (IsColorSimilar(image,p,p+neighbor_offset) == MagickFalse)
297 {
298 p++;
299 continue;
300 }
301 /*
302 Resolve this equivalence.
303 */
304 offset=y*image->columns+x;
305 ox=offset;
306 status=GetMatrixElement(equivalences,ox,0,&obj);
307 while (obj != ox)
308 {
309 ox=obj;
310 status=GetMatrixElement(equivalences,ox,0,&obj);
311 }
312 oy=offset+neighbor_offset;
313 status=GetMatrixElement(equivalences,oy,0,&obj);
314 while (obj != oy)
315 {
316 oy=obj;
317 status=GetMatrixElement(equivalences,oy,0,&obj);
318 }
319 if (ox < oy)
320 {
321 status=SetMatrixElement(equivalences,oy,0,&ox);
322 root=ox;
323 }
324 else
325 {
326 status=SetMatrixElement(equivalences,ox,0,&oy);
327 root=oy;
328 }
329 ox=offset;
330 status=GetMatrixElement(equivalences,ox,0,&obj);
331 while (obj != root)
332 {
333 status=GetMatrixElement(equivalences,ox,0,&obj);
334 status=SetMatrixElement(equivalences,ox,0,&root);
335 }
336 oy=offset+neighbor_offset;
337 status=GetMatrixElement(equivalences,oy,0,&obj);
338 while (obj != root)
339 {
340 status=GetMatrixElement(equivalences,oy,0,&obj);
341 status=SetMatrixElement(equivalences,oy,0,&root);
342 }
343 status=SetMatrixElement(equivalences,y*image->columns+x,0,&root);
344 p++;
345 }
346 }
347 }
348 /*
349 Label connected components.
350 */
351 n=0;
352 component_view=AcquireAuthenticCacheView(component_image,exception);
353 for (y=0; y < (ssize_t) component_image->rows; y++)
354 {
355 const IndexPacket
356 *magick_restrict indexes;
357
358 const PixelPacket
359 *magick_restrict p;
360
361 IndexPacket
362 *magick_restrict component_indexes;
363
364 PixelPacket
365 *magick_restrict q;
366
367 ssize_t
368 x;
369
370 if (status == MagickFalse)
371 continue;
372 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
373 q=QueueCacheViewAuthenticPixels(component_view,0,y,component_image->columns,
374 1,exception);
375 if ((p == (const PixelPacket *) NULL) || (q == (PixelPacket *) NULL))
376 {
377 status=MagickFalse;
378 continue;
379 }
380 indexes=GetCacheViewVirtualIndexQueue(image_view);
381 component_indexes=GetCacheViewAuthenticIndexQueue(component_view);
382 for (x=0; x < (ssize_t) component_image->columns; x++)
383 {
384 ssize_t
385 id,
386 offset;
387
388 offset=y*image->columns+x;
389 status=GetMatrixElement(equivalences,offset,0,&id);
390 if (id != offset)
391 status=GetMatrixElement(equivalences,id,0,&id);
392 else
393 {
394 id=n++;
395 if (id >= (ssize_t) MaxColormapSize)
396 break;
397 }
398 status=SetMatrixElement(equivalences,offset,0,&id);
399 if (x < object[id].bounding_box.x)
400 object[id].bounding_box.x=x;
401 if (x >= (ssize_t) object[id].bounding_box.width)
402 object[id].bounding_box.width=(size_t) x;
403 if (y < object[id].bounding_box.y)
404 object[id].bounding_box.y=y;
405 if (y >= (ssize_t) object[id].bounding_box.height)
406 object[id].bounding_box.height=(size_t) y;
407 object[id].color.red+=QuantumScale*p->red;
408 object[id].color.green+=QuantumScale*p->green;
409 object[id].color.blue+=QuantumScale*p->blue;
410 if (image->matte != MagickFalse)
411 object[id].color.opacity+=QuantumScale*p->opacity;
412 if (image->colorspace == CMYKColorspace)
413 object[id].color.index+=QuantumScale*indexes[x];
414 object[id].centroid.x+=x;
415 object[id].centroid.y+=y;
416 object[id].area++;
417 component_indexes[x]=(IndexPacket) id;
418 p++;
419 q++;
420 }
421 if (n > (ssize_t) MaxColormapSize)
422 break;
423 if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
424 status=MagickFalse;
425 if (image->progress_monitor != (MagickProgressMonitor) NULL)
426 {
427 MagickBooleanType
428 proceed;
429
430 progress++;
431 proceed=SetImageProgress(image,ConnectedComponentsImageTag,progress,
432 image->rows);
433 if (proceed == MagickFalse)
434 status=MagickFalse;
435 }
436 }
437 component_view=DestroyCacheView(component_view);
438 image_view=DestroyCacheView(image_view);
439 equivalences=DestroyMatrixInfo(equivalences);
440 if (n > (ssize_t) MaxColormapSize)
441 {
442 object=(CCObjectInfo *) RelinquishMagickMemory(object);
443 component_image=DestroyImage(component_image);
444 ThrowImageException(ResourceLimitError,"TooManyObjects");
445 }
446 background_id=0;
447 min_threshold=0.0;
448 max_threshold=0.0;
449 component_image->colors=(size_t) n;
450 for (i=0; i < (ssize_t) component_image->colors; i++)
451 {
452 object[i].bounding_box.width-=(object[i].bounding_box.x-1);
453 object[i].bounding_box.height-=(object[i].bounding_box.y-1);
454 object[i].color.red/=(QuantumScale*object[i].area);
455 object[i].color.green/=(QuantumScale*object[i].area);
456 object[i].color.blue/=(QuantumScale*object[i].area);
457 if (image->matte != MagickFalse)
458 object[i].color.opacity/=(QuantumScale*object[i].area);
459 if (image->colorspace == CMYKColorspace)
460 object[i].color.index/=(QuantumScale*object[i].area);
461 object[i].centroid.x/=object[i].area;
462 object[i].centroid.y/=object[i].area;
463 max_threshold+=object[i].area;
464 if (object[i].area > object[background_id].area)
465 background_id=i;
466 }
467 max_threshold+=MagickEpsilon;
468 artifact=GetImageArtifact(image,"connected-components:background-id");
469 if (artifact != (const char *) NULL)
470 background_id=(ssize_t) StringToLong(artifact);
471 artifact=GetImageArtifact(image,"connected-components:area-threshold");
472 if (artifact != (const char *) NULL)
473 {
474 /*
475 Merge any object not within the min and max area threshold.
476 */
477 (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
478 for (i=0; i < (ssize_t) component_image->colors; i++)
479 if (((object[i].area < min_threshold) ||
480 (object[i].area >= max_threshold)) && (i != background_id))
481 object[i].merge=MagickTrue;
482 }
483 artifact=GetImageArtifact(image,"connected-components:keep-colors");
484 if (artifact != (const char *) NULL)
485 {
486 const char
487 *p;
488
489 /*
490 Keep selected objects based on color, merge others.
491 */
492 for (i=0; i < (ssize_t) component_image->colors; i++)
493 object[i].merge=MagickTrue;
494 for (p=artifact; ; )
495 {
496 char
497 color[MagickPathExtent];
498
499 MagickPixelPacket
500 pixel;
501
502 const char
503 *q;
504
505 for (q=p; *q != '\0'; q++)
506 if (*q == ';')
507 break;
508 (void) CopyMagickString(color,p,(size_t) MagickMin(q-p+1,
509 MagickPathExtent));
510 (void) QueryMagickColor(color,&pixel,exception);
511 for (i=0; i < (ssize_t) component_image->colors; i++)
512 if (IsMagickColorSimilar(&object[i].color,&pixel) != MagickFalse)
513 object[i].merge=MagickFalse;
514 if (*q == '\0')
515 break;
516 p=q+1;
517 }
518 }
519 artifact=GetImageArtifact(image,"connected-components:keep-ids");
520 if (artifact == (const char *) NULL)
521 artifact=GetImageArtifact(image,"connected-components:keep");
522 if (artifact != (const char *) NULL)
523 for (c=(char *) artifact; *c != '\0'; )
524 {
525 /*
526 Keep selected objects based on id, merge others.
527 */
528 for (i=0; i < (ssize_t) component_image->colors; i++)
529 object[i].merge=MagickTrue;
530 while ((isspace((int) ((unsigned char) *c)) != 0) || (*c == ','))
531 c++;
532 first=(ssize_t) strtol(c,&c,10);
533 if (first < 0)
534 first+=(ssize_t) component_image->colors;
535 last=first;
536 while (isspace((int) ((unsigned char) *c)) != 0)
537 c++;
538 if (*c == '-')
539 {
540 last=(ssize_t) strtol(c+1,&c,10);
541 if (last < 0)
542 last+=(ssize_t) component_image->colors;
543 }
544 step=(ssize_t) (first > last ? -1 : 1);
545 for ( ; first != (last+step); first+=step)
546 object[first].merge=MagickFalse;
547 }
548 artifact=GetImageArtifact(image,"connected-components:keep-top");
549 if (artifact != (const char *) NULL)
550 {
551 CCObjectInfo
552 *top_objects;
553
554 ssize_t
555 top_ids;
556
557 /*
558 Keep top objects.
559 */
560 top_ids=(ssize_t) StringToLong(artifact);
561 top_objects=(CCObjectInfo *) AcquireQuantumMemory(component_image->colors,
562 sizeof(*top_objects));
563 if (top_objects == (CCObjectInfo *) NULL)
564 {
565 object=(CCObjectInfo *) RelinquishMagickMemory(object);
566 component_image=DestroyImage(component_image);
567 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
568 }
569 (void) memcpy(top_objects,object,component_image->colors*sizeof(*object));
570 qsort((void *) top_objects,component_image->colors,sizeof(*top_objects),
571 CCObjectInfoCompare);
572 for (i=top_ids+1; i < (ssize_t) component_image->colors; i++)
573 object[top_objects[i].id].merge=MagickTrue;
574 top_objects=(CCObjectInfo *) RelinquishMagickMemory(top_objects);
575 }
576 artifact=GetImageArtifact(image,"connected-components:remove-colors");
577 if (artifact != (const char *) NULL)
578 {
579 const char
580 *p;
581
582 /*
583 Remove selected objects based on color, keep others.
584 */
585 for (p=artifact; ; )
586 {
587 char
588 color[MagickPathExtent];
589
590 MagickPixelPacket
591 pixel;
592
593 const char
594 *q;
595
596 for (q=p; *q != '\0'; q++)
597 if (*q == ';')
598 break;
599 (void) CopyMagickString(color,p,(size_t) MagickMin(q-p+1,
600 MagickPathExtent));
601 (void) QueryMagickColor(color,&pixel,exception);
602 for (i=0; i < (ssize_t) component_image->colors; i++)
603 if (IsMagickColorSimilar(&object[i].color,&pixel) != MagickFalse)
604 object[i].merge=MagickTrue;
605 if (*q == '\0')
606 break;
607 p=q+1;
608 }
609 }
610 artifact=GetImageArtifact(image,"connected-components:remove-ids");
611 if (artifact == (const char *) NULL)
612 artifact=GetImageArtifact(image,"connected-components:remove");
613 if (artifact != (const char *) NULL)
614 for (c=(char *) artifact; *c != '\0'; )
615 {
616 /*
617 Remove selected objects based on color, keep others.
618 */
619 while ((isspace((int) ((unsigned char) *c)) != 0) || (*c == ','))
620 c++;
621 first=(ssize_t) strtol(c,&c,10);
622 if (first < 0)
623 first+=(ssize_t) component_image->colors;
624 last=first;
625 while (isspace((int) ((unsigned char) *c)) != 0)
626 c++;
627 if (*c == '-')
628 {
629 last=(ssize_t) strtol(c+1,&c,10);
630 if (last < 0)
631 last+=(ssize_t) component_image->colors;
632 }
633 step=(ssize_t) (first > last ? -1 : 1);
634 for ( ; first != (last+step); first+=step)
635 object[first].merge=MagickTrue;
636 }
637 /*
638 Merge any object not within the min and max area threshold.
639 */
640 component_view=AcquireAuthenticCacheView(component_image,exception);
641 object_view=AcquireVirtualCacheView(component_image,exception);
642 for (i=0; i < (ssize_t) component_image->colors; i++)
643 {
644 RectangleInfo
645 bounding_box;
646
647 ssize_t
648 j;
649
650 size_t
651 id;
652
653 if (status == MagickFalse)
654 continue;
655 if ((object[i].merge == MagickFalse) || (i == background_id))
656 continue; /* keep object */
657 /*
658 Merge this object.
659 */
660 for (j=0; j < (ssize_t) component_image->colors; j++)
661 object[j].census=0;
662 bounding_box=object[i].bounding_box;
663 for (y=0; y < (ssize_t) bounding_box.height; y++)
664 {
665 const IndexPacket
666 *magick_restrict indexes;
667
668 const PixelPacket
669 *magick_restrict p;
670
671 ssize_t
672 x;
673
674 if (status == MagickFalse)
675 continue;
676 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
677 bounding_box.y+y,bounding_box.width,1,exception);
678 if (p == (const PixelPacket *) NULL)
679 {
680 status=MagickFalse;
681 continue;
682 }
683 indexes=GetCacheViewVirtualIndexQueue(component_view);
684 for (x=0; x < (ssize_t) bounding_box.width; x++)
685 {
686 size_t
687 k;
688
689 if (status == MagickFalse)
690 continue;
691 j=(ssize_t) indexes[x];
692 if (j == i)
693 for (k=0; k < (ssize_t) (connectivity > 4 ? 4 : 2); k++)
694 {
695 const IndexPacket
696 *magick_restrict indexes;
697
698 const PixelPacket
699 *p;
700
701 /*
702 Compute area of adjacent objects.
703 */
704 if (status == MagickFalse)
705 continue;
706 dx=connectivity > 4 ? connect8[k][1] : connect4[k][1];
707 dy=connectivity > 4 ? connect8[k][0] : connect4[k][0];
708 p=GetCacheViewVirtualPixels(object_view,bounding_box.x+x+dx,
709 bounding_box.y+y+dy,1,1,exception);
710 if (p == (const PixelPacket *) NULL)
711 {
712 status=MagickFalse;
713 break;
714 }
715 indexes=GetCacheViewVirtualIndexQueue(object_view);
716 j=(ssize_t) *indexes;
717 if (j != i)
718 object[j].census++;
719 }
720 }
721 }
722 /*
723 Merge with object of greatest adjacent area.
724 */
725 id=0;
726 for (j=1; j < (ssize_t) component_image->colors; j++)
727 if (object[j].census > object[id].census)
728 id=(size_t) j;
729 object[i].area=0.0;
730 for (y=0; y < (ssize_t) bounding_box.height; y++)
731 {
732 IndexPacket
733 *magick_restrict component_indexes;
734
735 PixelPacket
736 *magick_restrict q;
737
738 ssize_t
739 x;
740
741 if (status == MagickFalse)
742 continue;
743 q=GetCacheViewAuthenticPixels(component_view,bounding_box.x,
744 bounding_box.y+y,bounding_box.width,1,exception);
745 if (q == (PixelPacket *) NULL)
746 {
747 status=MagickFalse;
748 continue;
749 }
750 component_indexes=GetCacheViewAuthenticIndexQueue(component_view);
751 for (x=0; x < (ssize_t) bounding_box.width; x++)
752 {
753 if ((ssize_t) component_indexes[x] == i)
754 component_indexes[x]=(IndexPacket) id;
755 }
756 if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
757 status=MagickFalse;
758 }
759 }
760 object_view=DestroyCacheView(object_view);
761 component_view=DestroyCacheView(component_view);
762 artifact=GetImageArtifact(image,"connected-components:mean-color");
763 if (IsMagickTrue(artifact) != MagickFalse)
764 {
765 /*
766 Replace object with mean color.
767 */
768 for (i=0; i < (ssize_t) component_image->colors; i++)
769 {
770 component_image->colormap[i].red=ClampToQuantum(object[i].color.red);
771 component_image->colormap[i].green=ClampToQuantum(
772 object[i].color.green);
773 component_image->colormap[i].blue=ClampToQuantum(object[i].color.blue);
774 component_image->colormap[i].opacity=ClampToQuantum(
775 object[i].color.opacity);
776 }
777 }
778 (void) SyncImage(component_image);
779 artifact=GetImageArtifact(image,"connected-components:verbose");
780 if (IsMagickTrue(artifact) != MagickFalse)
781 {
782 /*
783 Report statistics on each unique objects.
784 */
785 for (i=0; i < (ssize_t) component_image->colors; i++)
786 {
787 object[i].bounding_box.width=0;
788 object[i].bounding_box.height=0;
789 object[i].bounding_box.x=(ssize_t) component_image->columns;
790 object[i].bounding_box.y=(ssize_t) component_image->rows;
791 object[i].centroid.x=0;
792 object[i].centroid.y=0;
793 object[i].census=object[i].area == 0.0 ? 0.0 : 1.0;
794 object[i].area=0;
795 }
796 component_view=AcquireVirtualCacheView(component_image,exception);
797 for (y=0; y < (ssize_t) component_image->rows; y++)
798 {
799 const IndexPacket
800 *indexes;
801
802 const PixelPacket
803 *magick_restrict p;
804
805 ssize_t
806 x;
807
808 if (status == MagickFalse)
809 continue;
810 p=GetCacheViewVirtualPixels(component_view,0,y,
811 component_image->columns,1,exception);
812 if (p == (const PixelPacket *) NULL)
813 {
814 status=MagickFalse;
815 continue;
816 }
817 indexes=GetCacheViewVirtualIndexQueue(component_view);
818 for (x=0; x < (ssize_t) component_image->columns; x++)
819 {
820 size_t
821 id;
822
823 id=(size_t) indexes[x];
824 if (x < object[id].bounding_box.x)
825 object[id].bounding_box.x=x;
826 if (x > (ssize_t) object[id].bounding_box.width)
827 object[id].bounding_box.width=(size_t) x;
828 if (y < object[id].bounding_box.y)
829 object[id].bounding_box.y=y;
830 if (y > (ssize_t) object[id].bounding_box.height)
831 object[id].bounding_box.height=(size_t) y;
832 object[id].centroid.x+=x;
833 object[id].centroid.y+=y;
834 object[id].area++;
835 }
836 }
837 for (i=0; i < (ssize_t) component_image->colors; i++)
838 {
839 object[i].bounding_box.width-=(object[i].bounding_box.x-1);
840 object[i].bounding_box.height-=(object[i].bounding_box.y-1);
841 object[i].centroid.x=object[i].centroid.x/object[i].area;
842 object[i].centroid.y=object[i].centroid.y/object[i].area;
843 }
844 component_view=DestroyCacheView(component_view);
845 qsort((void *) object,component_image->colors,sizeof(*object),
846 CCObjectInfoCompare);
847 artifact=GetImageArtifact(image,"connected-components:exclude-header");
848 if (IsStringTrue(artifact) == MagickFalse)
849 (void) fprintf(stdout,
850 "Objects (id: bounding-box centroid area mean-color):\n");
851 for (i=0; i < (ssize_t) component_image->colors; i++)
852 if (object[i].census > 0.0)
853 {
854 char
855 mean_color[MaxTextExtent];
856
857 GetColorTuple(&object[i].color,MagickFalse,mean_color);
858 (void) fprintf(stdout,
859 " %.20g: %.20gx%.20g%+.20g%+.20g %.1f,%.1f %.20g %s\n",(double)
860 object[i].id,(double) object[i].bounding_box.width,(double)
861 object[i].bounding_box.height,(double) object[i].bounding_box.x,
862 (double) object[i].bounding_box.y,object[i].centroid.x,
863 object[i].centroid.y,(double) object[i].area,mean_color);
864 }
865 }
866 object=(CCObjectInfo *) RelinquishMagickMemory(object);
867 return(component_image);
868 }
869