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