MagickCore  7.1.0
vision.c
Go to the documentation of this file.
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 "MagickCore/studio.h"
40 #include "MagickCore/artifact.h"
41 #include "MagickCore/blob.h"
42 #include "MagickCore/cache-view.h"
43 #include "MagickCore/color.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"
54 #include "MagickCore/effect.h"
55 #include "MagickCore/gem.h"
56 #include "MagickCore/geometry.h"
58 #include "MagickCore/list.h"
59 #include "MagickCore/log.h"
60 #include "MagickCore/matrix.h"
61 #include "MagickCore/memory_.h"
63 #include "MagickCore/monitor.h"
65 #include "MagickCore/montage.h"
66 #include "MagickCore/morphology.h"
69 #include "MagickCore/paint.h"
72 #include "MagickCore/property.h"
73 #include "MagickCore/quantum.h"
74 #include "MagickCore/resource_.h"
76 #include "MagickCore/string_.h"
79 #include "MagickCore/token.h"
80 #include "MagickCore/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. The returned connected components image colors member
95 % defines the number of unique objects. Choose from 4 or 8-way connectivity.
96 %
97 % You are responsible for freeing the connected components objects resources
98 % with this statement;
99 %
100 % objects = (CCObjectInfo *) RelinquishMagickMemory(objects);
101 %
102 % The format of the ConnectedComponentsImage method is:
103 %
104 % Image *ConnectedComponentsImage(const Image *image,
105 % const size_t connectivity,CCObjectInfo **objects,
106 % ExceptionInfo *exception)
107 %
108 % A description of each parameter follows:
109 %
110 % o image: the image.
111 %
112 % o connectivity: how many neighbors to visit, choose from 4 or 8.
113 %
114 % o objects: return the attributes of each unique object.
115 %
116 % o exception: return any errors or warnings in this structure.
117 %
118 */
119 
120 static int CCObjectInfoCompare(const void *x,const void *y)
121 {
123  *p,
124  *q;
125 
126  p=(CCObjectInfo *) x;
127  q=(CCObjectInfo *) y;
128  return((int) (q->area-(ssize_t) p->area));
129 }
130 
131 static void PerimeterThreshold(const Image *component_image,
132  CCObjectInfo *object,const ssize_t metric_index,ExceptionInfo *exception)
133 {
135  status;
136 
137  ssize_t
138  i;
139 
140  status=MagickTrue;
141 #if defined(MAGICKCORE_OPENMP_SUPPORT)
142  #pragma omp parallel for schedule(dynamic) shared(status) \
143  magick_number_threads(component_image,component_image,component_image->colors,1)
144 #endif
145  for (i=0; i < (ssize_t) component_image->colors; i++)
146  {
147  CacheView
148  *component_view;
149 
151  bounding_box;
152 
153  size_t
154  pattern[4] = { 1, 0, 0, 0 };
155 
156  ssize_t
157  y;
158 
159  /*
160  Compute perimeter of each object.
161  */
162  if (status == MagickFalse)
163  continue;
164  component_view=AcquireAuthenticCacheView(component_image,exception);
165  bounding_box=object[i].bounding_box;
166  for (y=(-1); y < (ssize_t) bounding_box.height+1; y++)
167  {
168  const Quantum
169  *magick_restrict p;
170 
171  ssize_t
172  x;
173 
174  if (status == MagickFalse)
175  continue;
176  p=GetCacheViewVirtualPixels(component_view,bounding_box.x-1,
177  bounding_box.y+y,bounding_box.width+2,2,exception);
178  if (p == (const Quantum *) NULL)
179  {
180  status=MagickFalse;
181  break;
182  }
183  for (x=(-1); x < (ssize_t) bounding_box.width+1; x++)
184  {
185  Quantum
186  pixels[4];
187 
188  ssize_t
189  v;
190 
191  size_t
192  foreground;
193 
194  /*
195  An Algorithm for Calculating Objects’ Shape Features in Binary
196  Images, Lifeng He, Yuyan Chao.
197  */
198  foreground=0;
199  for (v=0; v < 2; v++)
200  {
201  ssize_t
202  u;
203 
204  for (u=0; u < 2; u++)
205  {
206  ssize_t
207  offset;
208 
209  offset=v*(bounding_box.width+2)*
210  GetPixelChannels(component_image)+u*
211  GetPixelChannels(component_image);
212  pixels[2*v+u]=GetPixelIndex(component_image,p+offset);
213  if ((ssize_t) pixels[2*v+u] == i)
214  foreground++;
215  }
216  }
217  if (foreground == 1)
218  pattern[1]++;
219  else
220  if (foreground == 2)
221  {
222  if ((((ssize_t) pixels[0] == i) &&
223  ((ssize_t) pixels[3] == i)) ||
224  (((ssize_t) pixels[1] == i) &&
225  ((ssize_t) pixels[2] == i)))
226  pattern[0]++; /* diagonal */
227  else
228  pattern[2]++;
229  }
230  else
231  if (foreground == 3)
232  pattern[3]++;
233  p+=GetPixelChannels(component_image);
234  }
235  }
236  component_view=DestroyCacheView(component_view);
237  object[i].metric[metric_index]=ceil(MagickSQ1_2*pattern[1]+1.0*pattern[2]+
238  MagickSQ1_2*pattern[3]+MagickSQ2*pattern[0]-0.5);
239  }
240 }
241 
242 static void CircularityThreshold(const Image *component_image,
243  CCObjectInfo *object,const ssize_t metric_index,ExceptionInfo *exception)
244 {
246  status;
247 
248  ssize_t
249  i;
250 
251  status=MagickTrue;
252 #if defined(MAGICKCORE_OPENMP_SUPPORT)
253  #pragma omp parallel for schedule(dynamic) shared(status) \
254  magick_number_threads(component_image,component_image,component_image->colors,1)
255 #endif
256  for (i=0; i < (ssize_t) component_image->colors; i++)
257  {
258  CacheView
259  *component_view;
260 
262  bounding_box;
263 
264  size_t
265  pattern[4] = { 1, 0, 0, 0 };
266 
267  ssize_t
268  y;
269 
270  /*
271  Compute perimeter of each object.
272  */
273  if (status == MagickFalse)
274  continue;
275  component_view=AcquireAuthenticCacheView(component_image,exception);
276  bounding_box=object[i].bounding_box;
277  for (y=(-1); y < (ssize_t) bounding_box.height; y++)
278  {
279  const Quantum
280  *magick_restrict p;
281 
282  ssize_t
283  x;
284 
285  if (status == MagickFalse)
286  continue;
287  p=GetCacheViewVirtualPixels(component_view,bounding_box.x-1,
288  bounding_box.y+y,bounding_box.width+2,2,exception);
289  if (p == (const Quantum *) NULL)
290  {
291  status=MagickFalse;
292  break;
293  }
294  for (x=(-1); x < (ssize_t) bounding_box.width; x++)
295  {
296  Quantum
297  pixels[4];
298 
299  ssize_t
300  v;
301 
302  size_t
303  foreground;
304 
305  /*
306  An Algorithm for Calculating Objects’ Shape Features in Binary
307  Images, Lifeng He, Yuyan Chao.
308  */
309  foreground=0;
310  for (v=0; v < 2; v++)
311  {
312  ssize_t
313  u;
314 
315  for (u=0; u < 2; u++)
316  {
317  ssize_t
318  offset;
319 
320  offset=v*(bounding_box.width+2)*
321  GetPixelChannels(component_image)+u*
322  GetPixelChannels(component_image);
323  pixels[2*v+u]=GetPixelIndex(component_image,p+offset);
324  if ((ssize_t) pixels[2*v+u] == i)
325  foreground++;
326  }
327  }
328  if (foreground == 1)
329  pattern[1]++;
330  else
331  if (foreground == 2)
332  {
333  if ((((ssize_t) pixels[0] == i) &&
334  ((ssize_t) pixels[3] == i)) ||
335  (((ssize_t) pixels[1] == i) &&
336  ((ssize_t) pixels[2] == i)))
337  pattern[0]++; /* diagonal */
338  else
339  pattern[2]++;
340  }
341  else
342  if (foreground == 3)
343  pattern[3]++;
344  p+=GetPixelChannels(component_image);
345  }
346  }
347  component_view=DestroyCacheView(component_view);
348  object[i].metric[metric_index]=ceil(MagickSQ1_2*pattern[1]+1.0*pattern[2]+
349  MagickSQ1_2*pattern[3]+MagickSQ2*pattern[0]-0.5);
350  object[i].metric[metric_index]=4.0*MagickPI*object[i].area/
351  (object[i].metric[metric_index]*object[i].metric[metric_index]);
352  }
353 }
354 
355 static void MajorAxisThreshold(const Image *component_image,
356  CCObjectInfo *object,const ssize_t metric_index,ExceptionInfo *exception)
357 {
359  status;
360 
361  ssize_t
362  i;
363 
364  status=MagickTrue;
365 #if defined(MAGICKCORE_OPENMP_SUPPORT)
366  #pragma omp parallel for schedule(dynamic) shared(status) \
367  magick_number_threads(component_image,component_image,component_image->colors,1)
368 #endif
369  for (i=0; i < (ssize_t) component_image->colors; i++)
370  {
371  CacheView
372  *component_view;
373 
374  double
375  M00 = 0.0,
376  M01 = 0.0,
377  M02 = 0.0,
378  M10 = 0.0,
379  M11 = 0.0,
380  M20 = 0.0;
381 
382  PointInfo
383  centroid = { 0.0, 0.0 };
384 
386  bounding_box;
387 
388  const Quantum
389  *magick_restrict p;
390 
391  ssize_t
392  x;
393 
394  ssize_t
395  y;
396 
397  /*
398  Compute ellipse major axis of each object.
399  */
400  if (status == MagickFalse)
401  continue;
402  component_view=AcquireAuthenticCacheView(component_image,exception);
403  bounding_box=object[i].bounding_box;
404  for (y=0; y < (ssize_t) bounding_box.height; y++)
405  {
406  if (status == MagickFalse)
407  continue;
408  p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
409  bounding_box.y+y,bounding_box.width,1,exception);
410  if (p == (const Quantum *) NULL)
411  {
412  status=MagickFalse;
413  break;
414  }
415  for (x=0; x < (ssize_t) bounding_box.width; x++)
416  {
417  if ((ssize_t) GetPixelIndex(component_image,p) == i)
418  {
419  M00++;
420  M10+=x;
421  M01+=y;
422  }
423  p+=GetPixelChannels(component_image);
424  }
425  }
426  centroid.x=M10*PerceptibleReciprocal(M00);
427  centroid.y=M01*PerceptibleReciprocal(M00);
428  for (y=0; y < (ssize_t) bounding_box.height; y++)
429  {
430  if (status == MagickFalse)
431  continue;
432  p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
433  bounding_box.y+y,bounding_box.width,1,exception);
434  if (p == (const Quantum *) NULL)
435  {
436  status=MagickFalse;
437  break;
438  }
439  for (x=0; x < (ssize_t) bounding_box.width; x++)
440  {
441  if ((ssize_t) GetPixelIndex(component_image,p) == i)
442  {
443  M11+=(x-centroid.x)*(y-centroid.y);
444  M20+=(x-centroid.x)*(x-centroid.x);
445  M02+=(y-centroid.y)*(y-centroid.y);
446  }
447  p+=GetPixelChannels(component_image);
448  }
449  }
450  component_view=DestroyCacheView(component_view);
451  object[i].metric[metric_index]=sqrt((2.0*PerceptibleReciprocal(M00))*((M20+M02)+
452  sqrt(4.0*M11*M11+(M20-M02)*(M20-M02))));
453  }
454 }
455 
456 static void MinorAxisThreshold(const Image *component_image,
457  CCObjectInfo *object,const ssize_t metric_index,ExceptionInfo *exception)
458 {
460  status;
461 
462  ssize_t
463  i;
464 
465  status=MagickTrue;
466 #if defined(MAGICKCORE_OPENMP_SUPPORT)
467  #pragma omp parallel for schedule(dynamic) shared(status) \
468  magick_number_threads(component_image,component_image,component_image->colors,1)
469 #endif
470  for (i=0; i < (ssize_t) component_image->colors; i++)
471  {
472  CacheView
473  *component_view;
474 
475  double
476  M00 = 0.0,
477  M01 = 0.0,
478  M02 = 0.0,
479  M10 = 0.0,
480  M11 = 0.0,
481  M20 = 0.0;
482 
483  PointInfo
484  centroid = { 0.0, 0.0 };
485 
487  bounding_box;
488 
489  const Quantum
490  *magick_restrict p;
491 
492  ssize_t
493  x;
494 
495  ssize_t
496  y;
497 
498  /*
499  Compute ellipse major axis of each object.
500  */
501  if (status == MagickFalse)
502  continue;
503  component_view=AcquireAuthenticCacheView(component_image,exception);
504  bounding_box=object[i].bounding_box;
505  for (y=0; y < (ssize_t) bounding_box.height; y++)
506  {
507  if (status == MagickFalse)
508  continue;
509  p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
510  bounding_box.y+y,bounding_box.width,1,exception);
511  if (p == (const Quantum *) NULL)
512  {
513  status=MagickFalse;
514  break;
515  }
516  for (x=0; x < (ssize_t) bounding_box.width; x++)
517  {
518  if ((ssize_t) GetPixelIndex(component_image,p) == i)
519  {
520  M00++;
521  M10+=x;
522  M01+=y;
523  }
524  p+=GetPixelChannels(component_image);
525  }
526  }
527  centroid.x=M10*PerceptibleReciprocal(M00);
528  centroid.y=M01*PerceptibleReciprocal(M00);
529  for (y=0; y < (ssize_t) bounding_box.height; y++)
530  {
531  if (status == MagickFalse)
532  continue;
533  p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
534  bounding_box.y+y,bounding_box.width,1,exception);
535  if (p == (const Quantum *) NULL)
536  {
537  status=MagickFalse;
538  break;
539  }
540  for (x=0; x < (ssize_t) bounding_box.width; x++)
541  {
542  if ((ssize_t) GetPixelIndex(component_image,p) == i)
543  {
544  M11+=(x-centroid.x)*(y-centroid.y);
545  M20+=(x-centroid.x)*(x-centroid.x);
546  M02+=(y-centroid.y)*(y-centroid.y);
547  }
548  p+=GetPixelChannels(component_image);
549  }
550  }
551  component_view=DestroyCacheView(component_view);
552  object[i].metric[metric_index]=sqrt((2.0*PerceptibleReciprocal(M00))*((M20+M02)-
553  sqrt(4.0*M11*M11+(M20-M02)*(M20-M02))));
554  }
555 }
556 
557 static void EccentricityThreshold(const Image *component_image,
558  CCObjectInfo *object,const ssize_t metric_index,ExceptionInfo *exception)
559 {
561  status;
562 
563  ssize_t
564  i;
565 
566  status=MagickTrue;
567 #if defined(MAGICKCORE_OPENMP_SUPPORT)
568  #pragma omp parallel for schedule(dynamic) shared(status) \
569  magick_number_threads(component_image,component_image,component_image->colors,1)
570 #endif
571  for (i=0; i < (ssize_t) component_image->colors; i++)
572  {
573  CacheView
574  *component_view;
575 
576  double
577  M00 = 0.0,
578  M01 = 0.0,
579  M02 = 0.0,
580  M10 = 0.0,
581  M11 = 0.0,
582  M20 = 0.0;
583 
584  PointInfo
585  centroid = { 0.0, 0.0 },
586  ellipse_axis = { 0.0, 0.0 };
587 
589  bounding_box;
590 
591  const Quantum
592  *magick_restrict p;
593 
594  ssize_t
595  x;
596 
597  ssize_t
598  y;
599 
600  /*
601  Compute eccentricity of each object.
602  */
603  if (status == MagickFalse)
604  continue;
605  component_view=AcquireAuthenticCacheView(component_image,exception);
606  bounding_box=object[i].bounding_box;
607  for (y=0; y < (ssize_t) bounding_box.height; y++)
608  {
609  if (status == MagickFalse)
610  continue;
611  p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
612  bounding_box.y+y,bounding_box.width,1,exception);
613  if (p == (const Quantum *) NULL)
614  {
615  status=MagickFalse;
616  break;
617  }
618  for (x=0; x < (ssize_t) bounding_box.width; x++)
619  {
620  if ((ssize_t) GetPixelIndex(component_image,p) == i)
621  {
622  M00++;
623  M10+=x;
624  M01+=y;
625  }
626  p+=GetPixelChannels(component_image);
627  }
628  }
629  centroid.x=M10*PerceptibleReciprocal(M00);
630  centroid.y=M01*PerceptibleReciprocal(M00);
631  for (y=0; y < (ssize_t) bounding_box.height; y++)
632  {
633  if (status == MagickFalse)
634  continue;
635  p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
636  bounding_box.y+y,bounding_box.width,1,exception);
637  if (p == (const Quantum *) NULL)
638  {
639  status=MagickFalse;
640  break;
641  }
642  for (x=0; x < (ssize_t) bounding_box.width; x++)
643  {
644  if ((ssize_t) GetPixelIndex(component_image,p) == i)
645  {
646  M11+=(x-centroid.x)*(y-centroid.y);
647  M20+=(x-centroid.x)*(x-centroid.x);
648  M02+=(y-centroid.y)*(y-centroid.y);
649  }
650  p+=GetPixelChannels(component_image);
651  }
652  }
653  component_view=DestroyCacheView(component_view);
654  ellipse_axis.x=sqrt((2.0*PerceptibleReciprocal(M00))*((M20+M02)+
655  sqrt(4.0*M11*M11+(M20-M02)*(M20-M02))));
656  ellipse_axis.y=sqrt((2.0*PerceptibleReciprocal(M00))*((M20+M02)-
657  sqrt(4.0*M11*M11+(M20-M02)*(M20-M02))));
658  object[i].metric[metric_index]=sqrt(1.0-(ellipse_axis.y*ellipse_axis.y*
659  PerceptibleReciprocal(ellipse_axis.x*ellipse_axis.x)));
660  }
661 }
662 
663 static void AngleThreshold(const Image *component_image,
664  CCObjectInfo *object,const ssize_t metric_index,ExceptionInfo *exception)
665 {
667  status;
668 
669  ssize_t
670  i;
671 
672  status=MagickTrue;
673 #if defined(MAGICKCORE_OPENMP_SUPPORT)
674  #pragma omp parallel for schedule(dynamic) shared(status) \
675  magick_number_threads(component_image,component_image,component_image->colors,1)
676 #endif
677  for (i=0; i < (ssize_t) component_image->colors; i++)
678  {
679  CacheView
680  *component_view;
681 
682  double
683  M00 = 0.0,
684  M01 = 0.0,
685  M02 = 0.0,
686  M10 = 0.0,
687  M11 = 0.0,
688  M20 = 0.0;
689 
690  PointInfo
691  centroid = { 0.0, 0.0 };
692 
694  bounding_box;
695 
696  const Quantum
697  *magick_restrict p;
698 
699  ssize_t
700  x;
701 
702  ssize_t
703  y;
704 
705  /*
706  Compute ellipse angle of each object.
707  */
708  if (status == MagickFalse)
709  continue;
710  component_view=AcquireAuthenticCacheView(component_image,exception);
711  bounding_box=object[i].bounding_box;
712  for (y=0; y < (ssize_t) bounding_box.height; y++)
713  {
714  if (status == MagickFalse)
715  continue;
716  p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
717  bounding_box.y+y,bounding_box.width,1,exception);
718  if (p == (const Quantum *) NULL)
719  {
720  status=MagickFalse;
721  break;
722  }
723  for (x=0; x < (ssize_t) bounding_box.width; x++)
724  {
725  if ((ssize_t) GetPixelIndex(component_image,p) == i)
726  {
727  M00++;
728  M10+=x;
729  M01+=y;
730  }
731  p+=GetPixelChannels(component_image);
732  }
733  }
734  centroid.x=M10*PerceptibleReciprocal(M00);
735  centroid.y=M01*PerceptibleReciprocal(M00);
736  for (y=0; y < (ssize_t) bounding_box.height; y++)
737  {
738  if (status == MagickFalse)
739  continue;
740  p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
741  bounding_box.y+y,bounding_box.width,1,exception);
742  if (p == (const Quantum *) NULL)
743  {
744  status=MagickFalse;
745  break;
746  }
747  for (x=0; x < (ssize_t) bounding_box.width; x++)
748  {
749  if ((ssize_t) GetPixelIndex(component_image,p) == i)
750  {
751  M11+=(x-centroid.x)*(y-centroid.y);
752  M20+=(x-centroid.x)*(x-centroid.x);
753  M02+=(y-centroid.y)*(y-centroid.y);
754  }
755  p+=GetPixelChannels(component_image);
756  }
757  }
758  component_view=DestroyCacheView(component_view);
759  object[i].metric[metric_index]=RadiansToDegrees(1.0/2.0*atan(2.0*M11*
760  PerceptibleReciprocal(M20-M02)));
761  if (fabs(M11) < 0.0)
762  {
763  if ((fabs(M20-M02) >= 0.0) && ((M20-M02) < 0.0))
764  object[i].metric[metric_index]+=90.0;
765  }
766  else
767  if (M11 < 0.0)
768  {
769  if (fabs(M20-M02) >= 0.0)
770  {
771  if ((M20-M02) < 0.0)
772  object[i].metric[metric_index]+=90.0;
773  else
774  object[i].metric[metric_index]+=180.0;
775  }
776  }
777  else
778  if ((fabs(M20-M02) >= 0.0) && ((M20-M02) < 0.0))
779  object[i].metric[metric_index]+=90.0;
780  }
781 }
782 
784  const size_t connectivity,CCObjectInfo **objects,ExceptionInfo *exception)
785 {
786 #define ConnectedComponentsImageTag "ConnectedComponents/Image"
787 
788  CacheView
789  *component_view,
790  *image_view,
791  *object_view;
792 
794  *object;
795 
796  char
797  *c;
798 
799  const char
800  *artifact,
801  *metrics[CCMaxMetrics];
802 
803  double
804  max_threshold,
805  min_threshold;
806 
807  Image
808  *component_image;
809 
811  status;
812 
814  progress;
815 
816  MatrixInfo
817  *equivalences;
818 
819  ssize_t
820  i;
821 
822  size_t
823  size;
824 
825  ssize_t
826  background_id,
827  connect4[2][2] = { { -1, 0 }, { 0, -1 } },
828  connect8[4][2] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 } },
829  dx,
830  dy,
831  first,
832  last,
833  n,
834  step,
835  y;
836 
837  /*
838  Initialize connected components image attributes.
839  */
840  assert(image != (Image *) NULL);
841  assert(image->signature == MagickCoreSignature);
842  if (image->debug != MagickFalse)
843  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
844  assert(exception != (ExceptionInfo *) NULL);
845  assert(exception->signature == MagickCoreSignature);
846  if (objects != (CCObjectInfo **) NULL)
847  *objects=(CCObjectInfo *) NULL;
848  component_image=CloneImage(image,0,0,MagickTrue,exception);
849  if (component_image == (Image *) NULL)
850  return((Image *) NULL);
851  component_image->depth=MAGICKCORE_QUANTUM_DEPTH;
852  if (AcquireImageColormap(component_image,MaxColormapSize,exception) == MagickFalse)
853  {
854  component_image=DestroyImage(component_image);
855  ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
856  }
857  /*
858  Initialize connected components equivalences.
859  */
860  size=image->columns*image->rows;
861  if (image->columns != (size/image->rows))
862  {
863  component_image=DestroyImage(component_image);
864  ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
865  }
866  equivalences=AcquireMatrixInfo(size,1,sizeof(ssize_t),exception);
867  if (equivalences == (MatrixInfo *) NULL)
868  {
869  component_image=DestroyImage(component_image);
870  return((Image *) NULL);
871  }
872  for (n=0; n < (ssize_t) (image->columns*image->rows); n++)
873  (void) SetMatrixElement(equivalences,n,0,&n);
874  object=(CCObjectInfo *) AcquireQuantumMemory(MaxColormapSize,sizeof(*object));
875  if (object == (CCObjectInfo *) NULL)
876  {
877  equivalences=DestroyMatrixInfo(equivalences);
878  component_image=DestroyImage(component_image);
879  ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
880  }
881  (void) memset(object,0,MaxColormapSize*sizeof(*object));
882  for (i=0; i < (ssize_t) MaxColormapSize; i++)
883  {
884  object[i].id=i;
885  object[i].bounding_box.x=(ssize_t) image->columns;
886  object[i].bounding_box.y=(ssize_t) image->rows;
887  GetPixelInfo(image,&object[i].color);
888  }
889  /*
890  Find connected components.
891  */
892  status=MagickTrue;
893  progress=0;
894  image_view=AcquireVirtualCacheView(image,exception);
895  for (n=0; n < (ssize_t) (connectivity > 4 ? 4 : 2); n++)
896  {
897  if (status == MagickFalse)
898  continue;
899  dx=connectivity > 4 ? connect8[n][1] : connect4[n][1];
900  dy=connectivity > 4 ? connect8[n][0] : connect4[n][0];
901  for (y=0; y < (ssize_t) image->rows; y++)
902  {
903  const Quantum
904  *magick_restrict p;
905 
906  ssize_t
907  x;
908 
909  if (status == MagickFalse)
910  continue;
911  p=GetCacheViewVirtualPixels(image_view,0,y-1,image->columns,3,exception);
912  if (p == (const Quantum *) NULL)
913  {
914  status=MagickFalse;
915  continue;
916  }
917  p+=GetPixelChannels(image)*image->columns;
918  for (x=0; x < (ssize_t) image->columns; x++)
919  {
920  PixelInfo
921  pixel,
922  target;
923 
924  ssize_t
925  neighbor_offset,
926  obj,
927  offset,
928  ox,
929  oy,
930  root;
931 
932  /*
933  Is neighbor an authentic pixel and a different color than the pixel?
934  */
935  GetPixelInfoPixel(image,p,&pixel);
936  if (((x+dx) < 0) || ((x+dx) >= (ssize_t) image->columns) ||
937  ((y+dy) < 0) || ((y+dy) >= (ssize_t) image->rows))
938  {
939  p+=GetPixelChannels(image);
940  continue;
941  }
942  neighbor_offset=dy*(GetPixelChannels(image)*image->columns)+dx*
943  GetPixelChannels(image);
944  GetPixelInfoPixel(image,p+neighbor_offset,&target);
945  if (IsFuzzyEquivalencePixelInfo(&pixel,&target) == MagickFalse)
946  {
947  p+=GetPixelChannels(image);
948  continue;
949  }
950  /*
951  Resolve this equivalence.
952  */
953  offset=y*image->columns+x;
954  neighbor_offset=dy*image->columns+dx;
955  ox=offset;
956  status=GetMatrixElement(equivalences,ox,0,&obj);
957  while (obj != ox)
958  {
959  ox=obj;
960  status=GetMatrixElement(equivalences,ox,0,&obj);
961  }
962  oy=offset+neighbor_offset;
963  status=GetMatrixElement(equivalences,oy,0,&obj);
964  while (obj != oy)
965  {
966  oy=obj;
967  status=GetMatrixElement(equivalences,oy,0,&obj);
968  }
969  if (ox < oy)
970  {
971  status=SetMatrixElement(equivalences,oy,0,&ox);
972  root=ox;
973  }
974  else
975  {
976  status=SetMatrixElement(equivalences,ox,0,&oy);
977  root=oy;
978  }
979  ox=offset;
980  status=GetMatrixElement(equivalences,ox,0,&obj);
981  while (obj != root)
982  {
983  status=GetMatrixElement(equivalences,ox,0,&obj);
984  status=SetMatrixElement(equivalences,ox,0,&root);
985  }
986  oy=offset+neighbor_offset;
987  status=GetMatrixElement(equivalences,oy,0,&obj);
988  while (obj != root)
989  {
990  status=GetMatrixElement(equivalences,oy,0,&obj);
991  status=SetMatrixElement(equivalences,oy,0,&root);
992  }
993  status=SetMatrixElement(equivalences,y*image->columns+x,0,&root);
994  p+=GetPixelChannels(image);
995  }
996  }
997  }
998  /*
999  Label connected components.
1000  */
1001  n=0;
1002  component_view=AcquireAuthenticCacheView(component_image,exception);
1003  for (y=0; y < (ssize_t) component_image->rows; y++)
1004  {
1005  const Quantum
1006  *magick_restrict p;
1007 
1008  Quantum
1009  *magick_restrict q;
1010 
1011  ssize_t
1012  x;
1013 
1014  if (status == MagickFalse)
1015  continue;
1016  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
1017  q=QueueCacheViewAuthenticPixels(component_view,0,y,component_image->columns,
1018  1,exception);
1019  if ((p == (const Quantum *) NULL) || (q == (Quantum *) NULL))
1020  {
1021  status=MagickFalse;
1022  continue;
1023  }
1024  for (x=0; x < (ssize_t) component_image->columns; x++)
1025  {
1026  ssize_t
1027  id,
1028  offset;
1029 
1030  offset=y*image->columns+x;
1031  status=GetMatrixElement(equivalences,offset,0,&id);
1032  if (id != offset)
1033  status=GetMatrixElement(equivalences,id,0,&id);
1034  else
1035  {
1036  id=n++;
1037  if (id >= (ssize_t) MaxColormapSize)
1038  break;
1039  }
1040  status=SetMatrixElement(equivalences,offset,0,&id);
1041  if (x < object[id].bounding_box.x)
1042  object[id].bounding_box.x=x;
1043  if (x >= (ssize_t) object[id].bounding_box.width)
1044  object[id].bounding_box.width=(size_t) x;
1045  if (y < object[id].bounding_box.y)
1046  object[id].bounding_box.y=y;
1047  if (y >= (ssize_t) object[id].bounding_box.height)
1048  object[id].bounding_box.height=(size_t) y;
1049  object[id].color.red+=QuantumScale*GetPixelRed(image,p);
1050  object[id].color.green+=QuantumScale*GetPixelGreen(image,p);
1051  object[id].color.blue+=QuantumScale*GetPixelBlue(image,p);
1052  if (image->alpha_trait != UndefinedPixelTrait)
1053  object[id].color.alpha+=QuantumScale*GetPixelAlpha(image,p);
1054  if (image->colorspace == CMYKColorspace)
1055  object[id].color.black+=QuantumScale*GetPixelBlack(image,p);
1056  object[id].centroid.x+=x;
1057  object[id].centroid.y+=y;
1058  object[id].area++;
1059  SetPixelIndex(component_image,(Quantum) id,q);
1060  p+=GetPixelChannels(image);
1061  q+=GetPixelChannels(component_image);
1062  }
1063  if (n > (ssize_t) MaxColormapSize)
1064  break;
1065  if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
1066  status=MagickFalse;
1067  if (image->progress_monitor != (MagickProgressMonitor) NULL)
1068  {
1070  proceed;
1071 
1072  progress++;
1073  proceed=SetImageProgress(image,ConnectedComponentsImageTag,progress,
1074  image->rows);
1075  if (proceed == MagickFalse)
1076  status=MagickFalse;
1077  }
1078  }
1079  component_view=DestroyCacheView(component_view);
1080  image_view=DestroyCacheView(image_view);
1081  equivalences=DestroyMatrixInfo(equivalences);
1082  if (n > (ssize_t) MaxColormapSize)
1083  {
1084  object=(CCObjectInfo *) RelinquishMagickMemory(object);
1085  component_image=DestroyImage(component_image);
1086  ThrowImageException(ResourceLimitError,"TooManyObjects");
1087  }
1088  background_id=0;
1089  min_threshold=0.0;
1090  max_threshold=0.0;
1091  component_image->colors=(size_t) n;
1092  for (i=0; i < (ssize_t) component_image->colors; i++)
1093  {
1094  object[i].bounding_box.width-=(object[i].bounding_box.x-1);
1095  object[i].bounding_box.height-=(object[i].bounding_box.y-1);
1096  object[i].color.red/=(QuantumScale*object[i].area);
1097  object[i].color.green/=(QuantumScale*object[i].area);
1098  object[i].color.blue/=(QuantumScale*object[i].area);
1099  if (image->alpha_trait != UndefinedPixelTrait)
1100  object[i].color.alpha/=(QuantumScale*object[i].area);
1101  if (image->colorspace == CMYKColorspace)
1102  object[i].color.black/=(QuantumScale*object[i].area);
1103  object[i].centroid.x/=object[i].area;
1104  object[i].centroid.y/=object[i].area;
1105  max_threshold+=object[i].area;
1106  if (object[i].area > object[background_id].area)
1107  background_id=i;
1108  }
1109  max_threshold+=MagickEpsilon;
1110  n=(-1);
1111  artifact=GetImageArtifact(image,"connected-components:background-id");
1112  if (artifact != (const char *) NULL)
1113  background_id=(ssize_t) StringToLong(artifact);
1114  artifact=GetImageArtifact(image,"connected-components:area-threshold");
1115  if (artifact != (const char *) NULL)
1116  {
1117  /*
1118  Merge any object not within the min and max area threshold.
1119  */
1120  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1121  for (i=0; i < (ssize_t) component_image->colors; i++)
1122  if (((object[i].area < min_threshold) ||
1123  (object[i].area >= max_threshold)) && (i != background_id))
1124  object[i].merge=MagickTrue;
1125  }
1126  artifact=GetImageArtifact(image,"connected-components:keep-colors");
1127  if (artifact != (const char *) NULL)
1128  {
1129  const char
1130  *p;
1131 
1132  /*
1133  Keep selected objects based on color, merge others.
1134  */
1135  for (i=0; i < (ssize_t) component_image->colors; i++)
1136  object[i].merge=MagickTrue;
1137  for (p=artifact; ; )
1138  {
1139  char
1140  color[MagickPathExtent];
1141 
1142  PixelInfo
1143  pixel;
1144 
1145  const char
1146  *q;
1147 
1148  for (q=p; *q != '\0'; q++)
1149  if (*q == ';')
1150  break;
1151  (void) CopyMagickString(color,p,(size_t) MagickMin(q-p+1,
1152  MagickPathExtent));
1153  (void) QueryColorCompliance(color,AllCompliance,&pixel,exception);
1154  for (i=0; i < (ssize_t) component_image->colors; i++)
1155  if (IsFuzzyEquivalencePixelInfo(&object[i].color,&pixel) != MagickFalse)
1156  object[i].merge=MagickFalse;
1157  if (*q == '\0')
1158  break;
1159  p=q+1;
1160  }
1161  }
1162  artifact=GetImageArtifact(image,"connected-components:keep-ids");
1163  if (artifact == (const char *) NULL)
1164  artifact=GetImageArtifact(image,"connected-components:keep");
1165  if (artifact != (const char *) NULL)
1166  {
1167  /*
1168  Keep selected objects based on id, merge others.
1169  */
1170  for (i=0; i < (ssize_t) component_image->colors; i++)
1171  object[i].merge=MagickTrue;
1172  for (c=(char *) artifact; *c != '\0'; )
1173  {
1174  while ((isspace((int) ((unsigned char) *c)) != 0) || (*c == ','))
1175  c++;
1176  first=(ssize_t) strtol(c,&c,10);
1177  if (first < 0)
1178  first+=(ssize_t) component_image->colors;
1179  last=first;
1180  while (isspace((int) ((unsigned char) *c)) != 0)
1181  c++;
1182  if (*c == '-')
1183  {
1184  last=(ssize_t) strtol(c+1,&c,10);
1185  if (last < 0)
1186  last+=(ssize_t) component_image->colors;
1187  }
1188  step=(ssize_t) (first > last ? -1 : 1);
1189  for ( ; first != (last+step); first+=step)
1190  object[first].merge=MagickFalse;
1191  }
1192  }
1193  artifact=GetImageArtifact(image,"connected-components:keep-top");
1194  if (artifact != (const char *) NULL)
1195  {
1196  CCObjectInfo
1197  *top_objects;
1198 
1199  ssize_t
1200  top_ids;
1201 
1202  /*
1203  Keep top objects.
1204  */
1205  top_ids=(ssize_t) StringToLong(artifact);
1206  top_objects=(CCObjectInfo *) AcquireQuantumMemory(component_image->colors,
1207  sizeof(*top_objects));
1208  if (top_objects == (CCObjectInfo *) NULL)
1209  {
1210  object=(CCObjectInfo *) RelinquishMagickMemory(object);
1211  component_image=DestroyImage(component_image);
1212  ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1213  }
1214  (void) memcpy(top_objects,object,component_image->colors*sizeof(*object));
1215  qsort((void *) top_objects,component_image->colors,sizeof(*top_objects),
1217  for (i=top_ids+1; i < (ssize_t) component_image->colors; i++)
1218  object[top_objects[i].id].merge=MagickTrue;
1219  top_objects=(CCObjectInfo *) RelinquishMagickMemory(top_objects);
1220  }
1221  artifact=GetImageArtifact(image,"connected-components:remove-colors");
1222  if (artifact != (const char *) NULL)
1223  {
1224  const char
1225  *p;
1226 
1227  /*
1228  Remove selected objects based on color, keep others.
1229  */
1230  for (p=artifact; ; )
1231  {
1232  char
1233  color[MagickPathExtent];
1234 
1235  PixelInfo
1236  pixel;
1237 
1238  const char
1239  *q;
1240 
1241  for (q=p; *q != '\0'; q++)
1242  if (*q == ';')
1243  break;
1244  (void) CopyMagickString(color,p,(size_t) MagickMin(q-p+1,
1245  MagickPathExtent));
1246  (void) QueryColorCompliance(color,AllCompliance,&pixel,exception);
1247  for (i=0; i < (ssize_t) component_image->colors; i++)
1248  if (IsFuzzyEquivalencePixelInfo(&object[i].color,&pixel) != MagickFalse)
1249  object[i].merge=MagickTrue;
1250  if (*q == '\0')
1251  break;
1252  p=q+1;
1253  }
1254  }
1255  artifact=GetImageArtifact(image,"connected-components:remove-ids");
1256  if (artifact == (const char *) NULL)
1257  artifact=GetImageArtifact(image,"connected-components:remove");
1258  if (artifact != (const char *) NULL)
1259  for (c=(char *) artifact; *c != '\0'; )
1260  {
1261  /*
1262  Remove selected objects based on id, keep others.
1263  */
1264  while ((isspace((int) ((unsigned char) *c)) != 0) || (*c == ','))
1265  c++;
1266  first=(ssize_t) strtol(c,&c,10);
1267  if (first < 0)
1268  first+=(ssize_t) component_image->colors;
1269  last=first;
1270  while (isspace((int) ((unsigned char) *c)) != 0)
1271  c++;
1272  if (*c == '-')
1273  {
1274  last=(ssize_t) strtol(c+1,&c,10);
1275  if (last < 0)
1276  last+=(ssize_t) component_image->colors;
1277  }
1278  step=(ssize_t) (first > last ? -1 : 1);
1279  for ( ; first != (last+step); first+=step)
1280  object[first].merge=MagickTrue;
1281  }
1282  artifact=GetImageArtifact(image,"connected-components:perimeter-threshold");
1283  if (artifact != (const char *) NULL)
1284  {
1285  /*
1286  Merge any object not within the min and max perimeter threshold.
1287  */
1288  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1289  metrics[++n]="perimeter";
1290  PerimeterThreshold(image,object,n,exception);
1291  for (i=0; i < (ssize_t) component_image->colors; i++)
1292  if (((object[i].metric[n] < min_threshold) ||
1293  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1294  object[i].merge=MagickTrue;
1295  }
1296  artifact=GetImageArtifact(image,"connected-components:circularity-threshold");
1297  if (artifact != (const char *) NULL)
1298  {
1299  /*
1300  Merge any object not within the min and max circularity threshold.
1301  */
1302  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1303  metrics[++n]="circularity";
1304  CircularityThreshold(image,object,n,exception);
1305  for (i=0; i < (ssize_t) component_image->colors; i++)
1306  if (((object[i].metric[n] < min_threshold) ||
1307  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1308  object[i].merge=MagickTrue;
1309  }
1310  artifact=GetImageArtifact(image,"connected-components:diameter-threshold");
1311  if (artifact != (const char *) NULL)
1312  {
1313  /*
1314  Merge any object not within the min and max diameter threshold.
1315  */
1316  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1317  metrics[++n]="diameter";
1318  for (i=0; i < (ssize_t) component_image->colors; i++)
1319  {
1320  object[i].metric[n]=ceil(sqrt(4.0*object[i].area/MagickPI)-0.5);
1321  if (((object[i].metric[n] < min_threshold) ||
1322  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1323  object[i].merge=MagickTrue;
1324  }
1325  }
1326  artifact=GetImageArtifact(image,"connected-components:major-axis-threshold");
1327  if (artifact != (const char *) NULL)
1328  {
1329  /*
1330  Merge any object not within the min and max ellipse major threshold.
1331  */
1332  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1333  metrics[++n]="major-axis";
1334  MajorAxisThreshold(component_image,object,n,exception);
1335  for (i=0; i < (ssize_t) component_image->colors; i++)
1336  if (((object[i].metric[n] < min_threshold) ||
1337  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1338  object[i].merge=MagickTrue;
1339  }
1340  artifact=GetImageArtifact(image,"connected-components:minor-axis-threshold");
1341  if (artifact != (const char *) NULL)
1342  {
1343  /*
1344  Merge any object not within the min and max ellipse minor threshold.
1345  */
1346  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1347  metrics[++n]="minor-axis";
1348  MinorAxisThreshold(component_image,object,n,exception);
1349  for (i=0; i < (ssize_t) component_image->colors; i++)
1350  if (((object[i].metric[n] < min_threshold) ||
1351  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1352  object[i].merge=MagickTrue;
1353  }
1354  artifact=GetImageArtifact(image,"connected-components:eccentricity-threshold");
1355  if (artifact != (const char *) NULL)
1356  {
1357  /*
1358  Merge any object not within the min and max eccentricity threshold.
1359  */
1360  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1361  metrics[++n]="eccentricy";
1362  EccentricityThreshold(component_image,object,n,exception);
1363  for (i=0; i < (ssize_t) component_image->colors; i++)
1364  if (((object[i].metric[n] < min_threshold) ||
1365  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1366  object[i].merge=MagickTrue;
1367  }
1368  artifact=GetImageArtifact(image,"connected-components:angle-threshold");
1369  if (artifact != (const char *) NULL)
1370  {
1371  /*
1372  Merge any object not within the min and max ellipse angle threshold.
1373  */
1374  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1375  metrics[++n]="angle";
1376  AngleThreshold(component_image,object,n,exception);
1377  for (i=0; i < (ssize_t) component_image->colors; i++)
1378  if (((object[i].metric[n] < min_threshold) ||
1379  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1380  object[i].merge=MagickTrue;
1381  }
1382  /*
1383  Merge any object not within the min and max area threshold.
1384  */
1385  component_view=AcquireAuthenticCacheView(component_image,exception);
1386  object_view=AcquireVirtualCacheView(component_image,exception);
1387  for (i=0; i < (ssize_t) component_image->colors; i++)
1388  {
1390  bounding_box;
1391 
1392  size_t
1393  id;
1394 
1395  ssize_t
1396  j;
1397 
1398  if (status == MagickFalse)
1399  continue;
1400  if ((object[i].merge == MagickFalse) || (i == background_id))
1401  continue; /* keep object */
1402  /*
1403  Merge this object.
1404  */
1405  for (j=0; j < (ssize_t) component_image->colors; j++)
1406  object[j].census=0;
1407  bounding_box=object[i].bounding_box;
1408  for (y=0; y < (ssize_t) bounding_box.height; y++)
1409  {
1410  const Quantum
1411  *magick_restrict p;
1412 
1413  ssize_t
1414  x;
1415 
1416  if (status == MagickFalse)
1417  continue;
1418  p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
1419  bounding_box.y+y,bounding_box.width,1,exception);
1420  if (p == (const Quantum *) NULL)
1421  {
1422  status=MagickFalse;
1423  continue;
1424  }
1425  for (x=0; x < (ssize_t) bounding_box.width; x++)
1426  {
1427  if (status == MagickFalse)
1428  continue;
1429  j=(ssize_t) GetPixelIndex(component_image,p);
1430  if (j == i)
1431  for (n=0; n < (ssize_t) (connectivity > 4 ? 4 : 2); n++)
1432  {
1433  const Quantum
1434  *q;
1435 
1436  /*
1437  Compute area of adjacent objects.
1438  */
1439  if (status == MagickFalse)
1440  continue;
1441  dx=connectivity > 4 ? connect8[n][1] : connect4[n][1];
1442  dy=connectivity > 4 ? connect8[n][0] : connect4[n][0];
1443  q=GetCacheViewVirtualPixels(object_view,bounding_box.x+x+dx,
1444  bounding_box.y+y+dy,1,1,exception);
1445  if (q == (const Quantum *) NULL)
1446  {
1447  status=MagickFalse;
1448  break;
1449  }
1450  j=(ssize_t) GetPixelIndex(component_image,q);
1451  if (j != i)
1452  object[j].census++;
1453  }
1454  p+=GetPixelChannels(component_image);
1455  }
1456  }
1457  /*
1458  Merge with object of greatest adjacent area.
1459  */
1460  id=0;
1461  for (j=1; j < (ssize_t) component_image->colors; j++)
1462  if (object[j].census > object[id].census)
1463  id=(size_t) j;
1464  object[i].area=0.0;
1465  for (y=0; y < (ssize_t) bounding_box.height; y++)
1466  {
1467  Quantum
1468  *magick_restrict q;
1469 
1470  ssize_t
1471  x;
1472 
1473  if (status == MagickFalse)
1474  continue;
1475  q=GetCacheViewAuthenticPixels(component_view,bounding_box.x,
1476  bounding_box.y+y,bounding_box.width,1,exception);
1477  if (q == (Quantum *) NULL)
1478  {
1479  status=MagickFalse;
1480  continue;
1481  }
1482  for (x=0; x < (ssize_t) bounding_box.width; x++)
1483  {
1484  if ((ssize_t) GetPixelIndex(component_image,q) == i)
1485  SetPixelIndex(component_image,(Quantum) id,q);
1486  q+=GetPixelChannels(component_image);
1487  }
1488  if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
1489  status=MagickFalse;
1490  }
1491  }
1492  object_view=DestroyCacheView(object_view);
1493  component_view=DestroyCacheView(component_view);
1494  artifact=GetImageArtifact(image,"connected-components:mean-color");
1495  if (IsStringTrue(artifact) != MagickFalse)
1496  {
1497  /*
1498  Replace object with mean color.
1499  */
1500  for (i=0; i < (ssize_t) component_image->colors; i++)
1501  component_image->colormap[i]=object[i].color;
1502  }
1503  (void) SyncImage(component_image,exception);
1504  artifact=GetImageArtifact(image,"connected-components:verbose");
1505  if ((IsStringTrue(artifact) != MagickFalse) ||
1506  (objects != (CCObjectInfo **) NULL))
1507  {
1508  /*
1509  Report statistics on each unique object.
1510  */
1511  for (i=0; i < (ssize_t) component_image->colors; i++)
1512  {
1513  object[i].bounding_box.width=0;
1514  object[i].bounding_box.height=0;
1515  object[i].bounding_box.x=(ssize_t) component_image->columns;
1516  object[i].bounding_box.y=(ssize_t) component_image->rows;
1517  object[i].centroid.x=0;
1518  object[i].centroid.y=0;
1519  object[i].census=object[i].area == 0.0 ? 0.0 : 1.0;
1520  object[i].area=0;
1521  }
1522  component_view=AcquireVirtualCacheView(component_image,exception);
1523  for (y=0; y < (ssize_t) component_image->rows; y++)
1524  {
1525  const Quantum
1526  *magick_restrict p;
1527 
1528  ssize_t
1529  x;
1530 
1531  if (status == MagickFalse)
1532  continue;
1533  p=GetCacheViewVirtualPixels(component_view,0,y,component_image->columns,
1534  1,exception);
1535  if (p == (const Quantum *) NULL)
1536  {
1537  status=MagickFalse;
1538  continue;
1539  }
1540  for (x=0; x < (ssize_t) component_image->columns; x++)
1541  {
1542  size_t
1543  id;
1544 
1545  id=(size_t) GetPixelIndex(component_image,p);
1546  if (x < object[id].bounding_box.x)
1547  object[id].bounding_box.x=x;
1548  if (x > (ssize_t) object[id].bounding_box.width)
1549  object[id].bounding_box.width=(size_t) x;
1550  if (y < object[id].bounding_box.y)
1551  object[id].bounding_box.y=y;
1552  if (y > (ssize_t) object[id].bounding_box.height)
1553  object[id].bounding_box.height=(size_t) y;
1554  object[id].centroid.x+=x;
1555  object[id].centroid.y+=y;
1556  object[id].area++;
1557  p+=GetPixelChannels(component_image);
1558  }
1559  }
1560  for (i=0; i < (ssize_t) component_image->colors; i++)
1561  {
1562  object[i].bounding_box.width-=(object[i].bounding_box.x-1);
1563  object[i].bounding_box.height-=(object[i].bounding_box.y-1);
1564  object[i].centroid.x=object[i].centroid.x/object[i].area;
1565  object[i].centroid.y=object[i].centroid.y/object[i].area;
1566  }
1567  component_view=DestroyCacheView(component_view);
1568  qsort((void *) object,component_image->colors,sizeof(*object),
1570  if (objects == (CCObjectInfo **) NULL)
1571  {
1572  ssize_t
1573  j;
1574 
1575  artifact=GetImageArtifact(image,
1576  "connected-components:exclude-header");
1577  if (IsStringTrue(artifact) == MagickFalse)
1578  {
1579  (void) fprintf(stdout,"Objects (");
1580  artifact=GetImageArtifact(image,
1581  "connected-components:exclude-ids");
1582  if (IsStringTrue(artifact) == MagickFalse)
1583  (void) fprintf(stdout,"id: ");
1584  (void) fprintf(stdout,"bounding-box centroid area mean-color");
1585  for (j=0; j <= n; j++)
1586  (void) fprintf(stdout," %s",metrics[j]);
1587  (void) fprintf(stdout,"):\n");
1588  }
1589  for (i=0; i < (ssize_t) component_image->colors; i++)
1590  if (object[i].census > 0.0)
1591  {
1592  char
1593  mean_color[MagickPathExtent];
1594 
1595  GetColorTuple(&object[i].color,MagickFalse,mean_color);
1596  (void) fprintf(stdout," ");
1597  artifact=GetImageArtifact(image,
1598  "connected-components:exclude-ids");
1599  if (IsStringTrue(artifact) == MagickFalse)
1600  (void) fprintf(stdout,"%.20g: ",(double) object[i].id);
1601  (void) fprintf(stdout,
1602  "%.20gx%.20g%+.20g%+.20g %.1f,%.1f %.*g %s",(double)
1603  object[i].bounding_box.width,(double)
1604  object[i].bounding_box.height,(double)
1605  object[i].bounding_box.x,(double) object[i].bounding_box.y,
1606  object[i].centroid.x,object[i].centroid.y,
1607  GetMagickPrecision(),(double) object[i].area,mean_color);
1608  for (j=0; j <= n; j++)
1609  (void) fprintf(stdout," %.*g",GetMagickPrecision(),
1610  object[i].metric[j]);
1611  (void) fprintf(stdout,"\n");
1612  }
1613  }
1614  }
1615  if (objects == (CCObjectInfo **) NULL)
1616  object=(CCObjectInfo *) RelinquishMagickMemory(object);
1617  else
1618  *objects=object;
1619  return(component_image);
1620 }
size_t rows
Definition: image.h:172
#define magick_restrict
Definition: MagickCore.h:41
MagickExport CacheView * DestroyCacheView(CacheView *cache_view)
Definition: cache-view.c:252
MagickExport Image * ConnectedComponentsImage(const Image *image, const size_t connectivity, CCObjectInfo **objects, ExceptionInfo *exception)
Definition: vision.c:783
#define MagickSQ1_2
Definition: image-private.h:41
PixelInfo * colormap
Definition: image.h:179
MagickProgressMonitor progress_monitor
Definition: image.h:303
MagickExport MagickBooleanType SyncImage(Image *image, ExceptionInfo *exception)
Definition: image.c:3897
static Quantum GetPixelAlpha(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
static Quantum GetPixelRed(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
size_t signature
Definition: exception.h:123
#define CCMaxMetrics
Definition: vision.h:25
static void MajorAxisThreshold(const Image *component_image, CCObjectInfo *object, const ssize_t metric_index, ExceptionInfo *exception)
Definition: vision.c:355
MagickExport const char * GetImageArtifact(const Image *image, const char *artifact)
Definition: artifact.c:273
#define MaxColormapSize
Definition: magick-type.h:78
#define MagickPI
Definition: image-private.h:40
MagickExport size_t CopyMagickString(char *magick_restrict destination, const char *magick_restrict source, const size_t length)
Definition: string.c:731
#define MAGICKCORE_QUANTUM_DEPTH
Definition: magick-type.h:32
MagickExport const Quantum * GetCacheViewVirtualPixels(const CacheView *cache_view, const ssize_t x, const ssize_t y, const size_t columns, const size_t rows, ExceptionInfo *exception)
Definition: cache-view.c:651
static long StringToLong(const char *magick_restrict value)
static void PerimeterThreshold(const Image *component_image, CCObjectInfo *object, const ssize_t metric_index, ExceptionInfo *exception)
Definition: vision.c:131
#define MagickSQ2
Definition: image-private.h:42
#define MagickEpsilon
Definition: magick-type.h:114
MagickExport MagickBooleanType GetMatrixElement(const MatrixInfo *matrix_info, const ssize_t x, const ssize_t y, void *value)
Definition: matrix.c:706
size_t width
Definition: geometry.h:131
Definition: log.h:52
ssize_t MagickOffsetType
Definition: magick-type.h:133
MagickExport void GetPixelInfo(const Image *image, PixelInfo *pixel)
Definition: pixel.c:2170
Definition: image.h:151
MagickExport MagickBooleanType SetMatrixElement(const MatrixInfo *matrix_info, const ssize_t x, const ssize_t y, const void *value)
Definition: matrix.c:1111
double x
Definition: geometry.h:124
#define MagickCoreSignature
MagickExport Quantum * GetCacheViewAuthenticPixels(CacheView *cache_view, const ssize_t x, const ssize_t y, const size_t columns, const size_t rows, ExceptionInfo *exception)
Definition: cache-view.c:299
MagickBooleanType
Definition: magick-type.h:165
static double PerceptibleReciprocal(const double x)
MagickExport void * AcquireQuantumMemory(const size_t count, const size_t quantum)
Definition: memory.c:665
MagickExport void GetColorTuple(const PixelInfo *pixel, const MagickBooleanType hex, char *tuple)
Definition: color.c:1518
double y
Definition: geometry.h:124
static void EccentricityThreshold(const Image *component_image, CCObjectInfo *object, const ssize_t metric_index, ExceptionInfo *exception)
Definition: vision.c:557
static void CircularityThreshold(const Image *component_image, CCObjectInfo *object, const ssize_t metric_index, ExceptionInfo *exception)
Definition: vision.c:242
#define MagickPathExtent
static Quantum GetPixelGreen(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
MagickExport MagickBooleanType IsStringTrue(const char *value)
Definition: string.c:1386
static void GetPixelInfoPixel(const Image *magick_restrict image, const Quantum *magick_restrict pixel, PixelInfo *magick_restrict pixel_info)
PixelTrait alpha_trait
Definition: image.h:280
MagickExport int GetMagickPrecision(void)
Definition: magick.c:942
static Quantum GetPixelIndex(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
static Quantum GetPixelBlack(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
MagickExport Quantum * QueueCacheViewAuthenticPixels(CacheView *cache_view, const ssize_t x, const ssize_t y, const size_t columns, const size_t rows, ExceptionInfo *exception)
Definition: cache-view.c:977
MagickExport MatrixInfo * AcquireMatrixInfo(const size_t columns, const size_t rows, const size_t stride, ExceptionInfo *exception)
Definition: matrix.c:201
MagickExport MagickBooleanType LogMagickEvent(const LogEventType type, const char *module, const char *function, const size_t line, const char *format,...)
Definition: log.c:1660
size_t signature
Definition: image.h:354
#define QuantumScale
Definition: magick-type.h:119
size_t columns
Definition: image.h:172
static void MinorAxisThreshold(const Image *component_image, CCObjectInfo *object, const ssize_t metric_index, ExceptionInfo *exception)
Definition: vision.c:456
MagickBooleanType(* MagickProgressMonitor)(const char *, const MagickOffsetType, const MagickSizeType, void *)
Definition: monitor.h:26
ssize_t x
Definition: geometry.h:135
static void AngleThreshold(const Image *component_image, CCObjectInfo *object, const ssize_t metric_index, ExceptionInfo *exception)
Definition: vision.c:663
size_t height
Definition: geometry.h:131
MagickExport MagickBooleanType QueryColorCompliance(const char *name, const ComplianceType compliance, PixelInfo *color, ExceptionInfo *exception)
Definition: color.c:2265
size_t colors
Definition: image.h:172
static size_t GetPixelChannels(const Image *magick_restrict image)
MagickExport MagickBooleanType AcquireImageColormap(Image *image, const size_t colors, ExceptionInfo *exception)
Definition: colormap.c:105
char filename[MagickPathExtent]
Definition: image.h:319
#define GetMagickModule()
Definition: log.h:28
#define ThrowImageException(severity, tag)
MagickExport CacheView * AcquireVirtualCacheView(const Image *image, ExceptionInfo *exception)
Definition: cache-view.c:149
static double RadiansToDegrees(const double radians)
Definition: image-private.h:69
double area
Definition: vision.h:42
unsigned short Quantum
Definition: magick-type.h:86
MagickExport MagickBooleanType IsFuzzyEquivalencePixelInfo(const PixelInfo *p, const PixelInfo *q)
Definition: pixel.c:6054
static void SetPixelIndex(const Image *magick_restrict image, const Quantum index, Quantum *magick_restrict pixel)
#define MagickMin(x, y)
Definition: image-private.h:37
MagickExport void * RelinquishMagickMemory(void *memory)
Definition: memory.c:1162
static int CCObjectInfoCompare(const void *x, const void *y)
Definition: vision.c:120
#define MagickExport
MagickExport MagickBooleanType SyncCacheViewAuthenticPixels(CacheView *magick_restrict cache_view, ExceptionInfo *exception)
Definition: cache-view.c:1100
ssize_t y
Definition: geometry.h:135
MagickExport CacheView * AcquireAuthenticCacheView(const Image *image, ExceptionInfo *exception)
Definition: cache-view.c:112
static Quantum GetPixelBlue(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
#define ConnectedComponentsImageTag
MagickExport Image * DestroyImage(Image *image)
Definition: image.c:1177
MagickExport Image * CloneImage(const Image *image, const size_t columns, const size_t rows, const MagickBooleanType detach, ExceptionInfo *exception)
Definition: image.c:788
ColorspaceType colorspace
Definition: image.h:157
MagickExport MagickBooleanType SetImageProgress(const Image *image, const char *tag, const MagickOffsetType offset, const MagickSizeType extent)
Definition: monitor.c:136
MagickBooleanType debug
Definition: image.h:334
MagickExport MatrixInfo * DestroyMatrixInfo(MatrixInfo *matrix_info)
Definition: matrix.c:370
size_t depth
Definition: image.h:172