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