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