MagickCore  7.1.1-43
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/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 {
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 
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 
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 
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*PerceptibleReciprocal(M00);
436  centroid.y=M01*PerceptibleReciprocal(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*PerceptibleReciprocal(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 
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*PerceptibleReciprocal(M00);
535  centroid.y=M01*PerceptibleReciprocal(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*PerceptibleReciprocal(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 
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*PerceptibleReciprocal(M00);
635  centroid.y=M01*PerceptibleReciprocal(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*PerceptibleReciprocal(M00))*((M20+M02)+
660  sqrt(4.0*M11*M11+(M20-M02)*(M20-M02))));
661  ellipse_axis.y=sqrt((2.0*PerceptibleReciprocal(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  PerceptibleReciprocal(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 
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*PerceptibleReciprocal(M00);
738  centroid.y=M01*PerceptibleReciprocal(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  PerceptibleReciprocal(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 
797  *object;
798 
799  char
800  *c;
801 
802  const char
803  *artifact,
804  *metrics[CCMaxMetrics];
805 
806  double
807  max_threshold,
808  min_threshold;
809 
810  Image
811  *component_image;
812 
813  MagickBooleanType
814  status;
815 
816  MagickOffsetType
817  progress;
818 
819  MatrixInfo
820  *equivalences;
821 
822  size_t
823  size;
824 
825  ssize_t
826  background_id,
827  connect4[2][2] = { { -1, 0 }, { 0, -1 } },
828  connect8[4][2] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 } },
829  dx,
830  dy,
831  first,
832  i,
833  last,
834  n,
835  step,
836  y;
837 
838  /*
839  Initialize connected components image attributes.
840  */
841  assert(image != (Image *) NULL);
842  assert(image->signature == MagickCoreSignature);
843  assert(exception != (ExceptionInfo *) NULL);
844  assert(exception->signature == MagickCoreSignature);
845  if (IsEventLogging() != MagickFalse)
846  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
847  if (objects != (CCObjectInfo **) NULL)
848  *objects=(CCObjectInfo *) NULL;
849  component_image=CloneImage(image,0,0,MagickTrue,exception);
850  if (component_image == (Image *) NULL)
851  return((Image *) NULL);
852  component_image->depth=MAGICKCORE_QUANTUM_DEPTH;
853  if (AcquireImageColormap(component_image,MaxColormapSize,exception) == MagickFalse)
854  {
855  component_image=DestroyImage(component_image);
856  ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
857  }
858  /*
859  Initialize connected components equivalences.
860  */
861  size=image->columns*image->rows;
862  if (image->columns != (size/image->rows))
863  {
864  component_image=DestroyImage(component_image);
865  ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
866  }
867  equivalences=AcquireMatrixInfo(size,1,sizeof(ssize_t),exception);
868  if (equivalences == (MatrixInfo *) NULL)
869  {
870  component_image=DestroyImage(component_image);
871  return((Image *) NULL);
872  }
873  for (n=0; n < (ssize_t) (image->columns*image->rows); n++)
874  (void) SetMatrixElement(equivalences,n,0,&n);
875  object=(CCObjectInfo *) AcquireQuantumMemory(MaxColormapSize,sizeof(*object));
876  if (object == (CCObjectInfo *) NULL)
877  {
878  equivalences=DestroyMatrixInfo(equivalences);
879  component_image=DestroyImage(component_image);
880  ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
881  }
882  (void) memset(object,0,MaxColormapSize*sizeof(*object));
883  for (i=0; i < (ssize_t) MaxColormapSize; i++)
884  {
885  object[i].id=i;
886  object[i].bounding_box.x=(ssize_t) image->columns;
887  object[i].bounding_box.y=(ssize_t) image->rows;
888  GetPixelInfo(image,&object[i].color);
889  }
890  /*
891  Find connected components.
892  */
893  status=MagickTrue;
894  progress=0;
895  image_view=AcquireVirtualCacheView(image,exception);
896  for (n=0; n < (ssize_t) (connectivity > 4 ? 4 : 2); n++)
897  {
898  if (status == MagickFalse)
899  continue;
900  dx=connectivity > 4 ? connect8[n][1] : connect4[n][1];
901  dy=connectivity > 4 ? connect8[n][0] : connect4[n][0];
902  for (y=0; y < (ssize_t) image->rows; y++)
903  {
904  const Quantum
905  *magick_restrict p;
906 
907  ssize_t
908  x;
909 
910  if (status == MagickFalse)
911  continue;
912  p=GetCacheViewVirtualPixels(image_view,0,y-1,image->columns,3,exception);
913  if (p == (const Quantum *) NULL)
914  {
915  status=MagickFalse;
916  continue;
917  }
918  p+=(ptrdiff_t) GetPixelChannels(image)*image->columns;
919  for (x=0; x < (ssize_t) image->columns; x++)
920  {
921  PixelInfo
922  pixel,
923  target;
924 
925  ssize_t
926  neighbor_offset,
927  obj,
928  offset,
929  ox,
930  oy,
931  root;
932 
933  /*
934  Is neighbor an authentic pixel and a different color than the pixel?
935  */
936  GetPixelInfoPixel(image,p,&pixel);
937  if (((x+dx) < 0) || ((x+dx) >= (ssize_t) image->columns) ||
938  ((y+dy) < 0) || ((y+dy) >= (ssize_t) image->rows))
939  {
940  p+=(ptrdiff_t) GetPixelChannels(image);
941  continue;
942  }
943  neighbor_offset=dy*((ssize_t) GetPixelChannels(image)*(ssize_t)
944  image->columns)+dx*(ssize_t) GetPixelChannels(image);
945  GetPixelInfoPixel(image,p+neighbor_offset,&target);
946  if (IsFuzzyEquivalencePixelInfo(&pixel,&target) == MagickFalse)
947  {
948  p+=(ptrdiff_t) GetPixelChannels(image);
949  continue;
950  }
951  /*
952  Resolve this equivalence.
953  */
954  offset=y*(ssize_t) image->columns+x;
955  neighbor_offset=dy*(ssize_t) image->columns+dx;
956  ox=offset;
957  status=GetMatrixElement(equivalences,ox,0,&obj);
958  while (obj != ox)
959  {
960  ox=obj;
961  status=GetMatrixElement(equivalences,ox,0,&obj);
962  }
963  oy=offset+neighbor_offset;
964  status=GetMatrixElement(equivalences,oy,0,&obj);
965  while (obj != oy)
966  {
967  oy=obj;
968  status=GetMatrixElement(equivalences,oy,0,&obj);
969  }
970  if (ox < oy)
971  {
972  status=SetMatrixElement(equivalences,oy,0,&ox);
973  root=ox;
974  }
975  else
976  {
977  status=SetMatrixElement(equivalences,ox,0,&oy);
978  root=oy;
979  }
980  ox=offset;
981  status=GetMatrixElement(equivalences,ox,0,&obj);
982  while (obj != root)
983  {
984  status=GetMatrixElement(equivalences,ox,0,&obj);
985  status=SetMatrixElement(equivalences,ox,0,&root);
986  }
987  oy=offset+neighbor_offset;
988  status=GetMatrixElement(equivalences,oy,0,&obj);
989  while (obj != root)
990  {
991  status=GetMatrixElement(equivalences,oy,0,&obj);
992  status=SetMatrixElement(equivalences,oy,0,&root);
993  }
994  status=SetMatrixElement(equivalences,y*(ssize_t) image->columns+x,0,
995  &root);
996  p+=(ptrdiff_t) GetPixelChannels(image);
997  }
998  }
999  }
1000  /*
1001  Label connected components.
1002  */
1003  n=0;
1004  component_view=AcquireAuthenticCacheView(component_image,exception);
1005  for (y=0; y < (ssize_t) component_image->rows; y++)
1006  {
1007  const Quantum
1008  *magick_restrict p;
1009 
1010  Quantum
1011  *magick_restrict q;
1012 
1013  ssize_t
1014  x;
1015 
1016  if (status == MagickFalse)
1017  continue;
1018  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
1019  q=QueueCacheViewAuthenticPixels(component_view,0,y,component_image->columns,
1020  1,exception);
1021  if ((p == (const Quantum *) NULL) || (q == (Quantum *) NULL))
1022  {
1023  status=MagickFalse;
1024  continue;
1025  }
1026  for (x=0; x < (ssize_t) component_image->columns; x++)
1027  {
1028  ssize_t
1029  id,
1030  offset;
1031 
1032  offset=y*(ssize_t) image->columns+x;
1033  status=GetMatrixElement(equivalences,offset,0,&id);
1034  if (id != offset)
1035  status=GetMatrixElement(equivalences,id,0,&id);
1036  else
1037  {
1038  id=n++;
1039  if (id >= (ssize_t) MaxColormapSize)
1040  break;
1041  }
1042  status=SetMatrixElement(equivalences,offset,0,&id);
1043  if (x < object[id].bounding_box.x)
1044  object[id].bounding_box.x=x;
1045  if (x >= (ssize_t) object[id].bounding_box.width)
1046  object[id].bounding_box.width=(size_t) x;
1047  if (y < object[id].bounding_box.y)
1048  object[id].bounding_box.y=y;
1049  if (y >= (ssize_t) object[id].bounding_box.height)
1050  object[id].bounding_box.height=(size_t) y;
1051  object[id].color.red+=QuantumScale*(double) GetPixelRed(image,p);
1052  object[id].color.green+=QuantumScale*(double) GetPixelGreen(image,p);
1053  object[id].color.blue+=QuantumScale*(double) GetPixelBlue(image,p);
1054  if (image->alpha_trait != UndefinedPixelTrait)
1055  object[id].color.alpha+=QuantumScale*(double) GetPixelAlpha(image,p);
1056  if (image->colorspace == CMYKColorspace)
1057  object[id].color.black+=QuantumScale*(double) GetPixelBlack(image,p);
1058  object[id].centroid.x+=x;
1059  object[id].centroid.y+=y;
1060  object[id].area++;
1061  SetPixelIndex(component_image,(Quantum) id,q);
1062  p+=(ptrdiff_t) GetPixelChannels(image);
1063  q+=(ptrdiff_t) GetPixelChannels(component_image);
1064  }
1065  if (n > (ssize_t) MaxColormapSize)
1066  break;
1067  if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
1068  status=MagickFalse;
1069  if (image->progress_monitor != (MagickProgressMonitor) NULL)
1070  {
1071  MagickBooleanType
1072  proceed;
1073 
1074  progress++;
1075  proceed=SetImageProgress(image,ConnectedComponentsImageTag,progress,
1076  image->rows);
1077  if (proceed == MagickFalse)
1078  status=MagickFalse;
1079  }
1080  }
1081  component_view=DestroyCacheView(component_view);
1082  image_view=DestroyCacheView(image_view);
1083  equivalences=DestroyMatrixInfo(equivalences);
1084  if (n > (ssize_t) MaxColormapSize)
1085  {
1086  object=(CCObjectInfo *) RelinquishMagickMemory(object);
1087  component_image=DestroyImage(component_image);
1088  ThrowImageException(ResourceLimitError,"TooManyObjects");
1089  }
1090  background_id=0;
1091  min_threshold=0.0;
1092  max_threshold=0.0;
1093  component_image->colors=(size_t) n;
1094  for (i=0; i < (ssize_t) component_image->colors; i++)
1095  {
1096  object[i].bounding_box.width=(size_t) ((ssize_t)
1097  object[i].bounding_box.width-(object[i].bounding_box.x-1));
1098  object[i].bounding_box.height=(size_t) ((ssize_t)
1099  object[i].bounding_box.height-(object[i].bounding_box.y-1));
1100  object[i].color.red/=(QuantumScale*object[i].area);
1101  object[i].color.green/=(QuantumScale*object[i].area);
1102  object[i].color.blue/=(QuantumScale*object[i].area);
1103  if (image->alpha_trait != UndefinedPixelTrait)
1104  object[i].color.alpha/=(QuantumScale*object[i].area);
1105  if (image->colorspace == CMYKColorspace)
1106  object[i].color.black/=(QuantumScale*object[i].area);
1107  object[i].centroid.x/=object[i].area;
1108  object[i].centroid.y/=object[i].area;
1109  max_threshold+=object[i].area;
1110  if (object[i].area > object[background_id].area)
1111  background_id=i;
1112  }
1113  max_threshold+=MagickEpsilon;
1114  n=(-1);
1115  artifact=GetImageArtifact(image,"connected-components:background-id");
1116  if (artifact != (const char *) NULL)
1117  background_id=(ssize_t) StringToLong(artifact);
1118  artifact=GetImageArtifact(image,"connected-components:area-threshold");
1119  if (artifact != (const char *) NULL)
1120  {
1121  /*
1122  Merge any object not within the min and max area threshold.
1123  */
1124  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1125  for (i=0; i < (ssize_t) component_image->colors; i++)
1126  if (((object[i].area < min_threshold) ||
1127  (object[i].area >= max_threshold)) && (i != background_id))
1128  object[i].merge=MagickTrue;
1129  }
1130  artifact=GetImageArtifact(image,"connected-components:keep-colors");
1131  if (artifact != (const char *) NULL)
1132  {
1133  const char
1134  *p;
1135 
1136  /*
1137  Keep selected objects based on color, merge others.
1138  */
1139  for (i=0; i < (ssize_t) component_image->colors; i++)
1140  object[i].merge=MagickTrue;
1141  for (p=artifact; ; )
1142  {
1143  char
1144  color[MagickPathExtent];
1145 
1146  PixelInfo
1147  pixel;
1148 
1149  const char
1150  *q;
1151 
1152  for (q=p; *q != '\0'; q++)
1153  if (*q == ';')
1154  break;
1155  (void) CopyMagickString(color,p,(size_t) MagickMin(q-p+1,
1156  MagickPathExtent));
1157  (void) QueryColorCompliance(color,AllCompliance,&pixel,exception);
1158  for (i=0; i < (ssize_t) component_image->colors; i++)
1159  if (IsFuzzyEquivalencePixelInfo(&object[i].color,&pixel) != MagickFalse)
1160  object[i].merge=MagickFalse;
1161  if (*q == '\0')
1162  break;
1163  p=q+1;
1164  }
1165  }
1166  artifact=GetImageArtifact(image,"connected-components:keep-ids");
1167  if (artifact == (const char *) NULL)
1168  artifact=GetImageArtifact(image,"connected-components:keep");
1169  if (artifact != (const char *) NULL)
1170  {
1171  /*
1172  Keep selected objects based on id, merge others.
1173  */
1174  for (i=0; i < (ssize_t) component_image->colors; i++)
1175  object[i].merge=MagickTrue;
1176  for (c=(char *) artifact; *c != '\0'; )
1177  {
1178  while ((isspace((int) ((unsigned char) *c)) != 0) || (*c == ','))
1179  c++;
1180  first=(ssize_t) strtol(c,&c,10);
1181  if (first < 0)
1182  first+=(ssize_t) component_image->colors;
1183  last=first;
1184  while (isspace((int) ((unsigned char) *c)) != 0)
1185  c++;
1186  if (*c == '-')
1187  {
1188  last=(ssize_t) strtol(c+1,&c,10);
1189  if (last < 0)
1190  last+=(ssize_t) component_image->colors;
1191  }
1192  step=(ssize_t) (first > last ? -1 : 1);
1193  for ( ; first != (last+step); first+=step)
1194  object[first].merge=MagickFalse;
1195  }
1196  }
1197  artifact=GetImageArtifact(image,"connected-components:keep-top");
1198  if (artifact != (const char *) NULL)
1199  {
1200  CCObjectInfo
1201  *top_objects;
1202 
1203  ssize_t
1204  top_ids;
1205 
1206  /*
1207  Keep top objects.
1208  */
1209  top_ids=(ssize_t) StringToLong(artifact);
1210  top_objects=(CCObjectInfo *) AcquireQuantumMemory(component_image->colors,
1211  sizeof(*top_objects));
1212  if (top_objects == (CCObjectInfo *) NULL)
1213  {
1214  object=(CCObjectInfo *) RelinquishMagickMemory(object);
1215  component_image=DestroyImage(component_image);
1216  ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1217  }
1218  (void) memcpy(top_objects,object,component_image->colors*sizeof(*object));
1219  qsort((void *) top_objects,component_image->colors,sizeof(*top_objects),
1220  CCObjectInfoCompare);
1221  for (i=top_ids+1; i < (ssize_t) component_image->colors; i++)
1222  object[top_objects[i].id].merge=MagickTrue;
1223  top_objects=(CCObjectInfo *) RelinquishMagickMemory(top_objects);
1224  }
1225  artifact=GetImageArtifact(image,"connected-components:remove-colors");
1226  if (artifact != (const char *) NULL)
1227  {
1228  const char
1229  *p;
1230 
1231  /*
1232  Remove selected objects based on color, keep others.
1233  */
1234  for (p=artifact; ; )
1235  {
1236  char
1237  color[MagickPathExtent];
1238 
1239  PixelInfo
1240  pixel;
1241 
1242  const char
1243  *q;
1244 
1245  for (q=p; *q != '\0'; q++)
1246  if (*q == ';')
1247  break;
1248  (void) CopyMagickString(color,p,(size_t) MagickMin(q-p+1,
1249  MagickPathExtent));
1250  (void) QueryColorCompliance(color,AllCompliance,&pixel,exception);
1251  for (i=0; i < (ssize_t) component_image->colors; i++)
1252  if (IsFuzzyEquivalencePixelInfo(&object[i].color,&pixel) != MagickFalse)
1253  object[i].merge=MagickTrue;
1254  if (*q == '\0')
1255  break;
1256  p=q+1;
1257  }
1258  }
1259  artifact=GetImageArtifact(image,"connected-components:remove-ids");
1260  if (artifact == (const char *) NULL)
1261  artifact=GetImageArtifact(image,"connected-components:remove");
1262  if (artifact != (const char *) NULL)
1263  for (c=(char *) artifact; *c != '\0'; )
1264  {
1265  /*
1266  Remove selected objects based on id, keep others.
1267  */
1268  while ((isspace((int) ((unsigned char) *c)) != 0) || (*c == ','))
1269  c++;
1270  first=(ssize_t) strtol(c,&c,10);
1271  if (first < 0)
1272  first+=(ssize_t) component_image->colors;
1273  last=first;
1274  while (isspace((int) ((unsigned char) *c)) != 0)
1275  c++;
1276  if (*c == '-')
1277  {
1278  last=(ssize_t) strtol(c+1,&c,10);
1279  if (last < 0)
1280  last+=(ssize_t) component_image->colors;
1281  }
1282  step=(ssize_t) (first > last ? -1 : 1);
1283  for ( ; first != (last+step); first+=step)
1284  object[first].merge=MagickTrue;
1285  }
1286  artifact=GetImageArtifact(image,"connected-components:perimeter-threshold");
1287  if (artifact != (const char *) NULL)
1288  {
1289  /*
1290  Merge any object not within the min and max perimeter threshold.
1291  */
1292  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1293  metrics[++n]="perimeter";
1294  PerimeterThreshold(component_image,object,n,exception);
1295  for (i=0; i < (ssize_t) component_image->colors; i++)
1296  if (((object[i].metric[n] < min_threshold) ||
1297  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1298  object[i].merge=MagickTrue;
1299  }
1300  artifact=GetImageArtifact(image,"connected-components:circularity-threshold");
1301  if (artifact != (const char *) NULL)
1302  {
1303  /*
1304  Merge any object not within the min and max circularity threshold.
1305  */
1306  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1307  metrics[++n]="circularity";
1308  CircularityThreshold(component_image,object,n,exception);
1309  for (i=0; i < (ssize_t) component_image->colors; i++)
1310  if (((object[i].metric[n] < min_threshold) ||
1311  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1312  object[i].merge=MagickTrue;
1313  }
1314  artifact=GetImageArtifact(image,"connected-components:diameter-threshold");
1315  if (artifact != (const char *) NULL)
1316  {
1317  /*
1318  Merge any object not within the min and max diameter threshold.
1319  */
1320  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1321  metrics[++n]="diameter";
1322  for (i=0; i < (ssize_t) component_image->colors; i++)
1323  {
1324  object[i].metric[n]=ceil(sqrt(4.0*object[i].area/MagickPI)-0.5);
1325  if (((object[i].metric[n] < min_threshold) ||
1326  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1327  object[i].merge=MagickTrue;
1328  }
1329  }
1330  artifact=GetImageArtifact(image,"connected-components:major-axis-threshold");
1331  if (artifact != (const char *) NULL)
1332  {
1333  /*
1334  Merge any object not within the min and max ellipse major threshold.
1335  */
1336  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1337  metrics[++n]="major-axis";
1338  MajorAxisThreshold(component_image,object,n,exception);
1339  for (i=0; i < (ssize_t) component_image->colors; i++)
1340  if (((object[i].metric[n] < min_threshold) ||
1341  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1342  object[i].merge=MagickTrue;
1343  }
1344  artifact=GetImageArtifact(image,"connected-components:minor-axis-threshold");
1345  if (artifact != (const char *) NULL)
1346  {
1347  /*
1348  Merge any object not within the min and max ellipse minor threshold.
1349  */
1350  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1351  metrics[++n]="minor-axis";
1352  MinorAxisThreshold(component_image,object,n,exception);
1353  for (i=0; i < (ssize_t) component_image->colors; i++)
1354  if (((object[i].metric[n] < min_threshold) ||
1355  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1356  object[i].merge=MagickTrue;
1357  }
1358  artifact=GetImageArtifact(image,"connected-components:eccentricity-threshold");
1359  if (artifact != (const char *) NULL)
1360  {
1361  /*
1362  Merge any object not within the min and max eccentricity threshold.
1363  */
1364  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1365  metrics[++n]="eccentricity";
1366  EccentricityThreshold(component_image,object,n,exception);
1367  for (i=0; i < (ssize_t) component_image->colors; i++)
1368  if (((object[i].metric[n] < min_threshold) ||
1369  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1370  object[i].merge=MagickTrue;
1371  }
1372  artifact=GetImageArtifact(image,"connected-components:angle-threshold");
1373  if (artifact != (const char *) NULL)
1374  {
1375  /*
1376  Merge any object not within the min and max ellipse angle threshold.
1377  */
1378  (void) sscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1379  metrics[++n]="angle";
1380  AngleThreshold(component_image,object,n,exception);
1381  for (i=0; i < (ssize_t) component_image->colors; i++)
1382  if (((object[i].metric[n] < min_threshold) ||
1383  (object[i].metric[n] >= max_threshold)) && (i != background_id))
1384  object[i].merge=MagickTrue;
1385  }
1386  /*
1387  Merge any object not within the min and max area threshold.
1388  */
1389  component_view=AcquireAuthenticCacheView(component_image,exception);
1390  object_view=AcquireVirtualCacheView(component_image,exception);
1391  (void) SetCacheViewVirtualPixelMethod(object_view,TileVirtualPixelMethod);
1392  for (i=0; i < (ssize_t) component_image->colors; i++)
1393  {
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+=(ptrdiff_t) 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+=(ptrdiff_t) 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+=(ptrdiff_t) GetPixelChannels(component_image);
1570  }
1571  }
1572  for (i=0; i < (ssize_t) component_image->colors; i++)
1573  {
1574  object[i].bounding_box.width=(size_t) ((ssize_t)
1575  object[i].bounding_box.width-(object[i].bounding_box.x-1));
1576  object[i].bounding_box.height=(size_t) ((ssize_t)
1577  object[i].bounding_box.height-(object[i].bounding_box.y-1));
1578  object[i].centroid.x=object[i].centroid.x/object[i].area;
1579  object[i].centroid.y=object[i].centroid.y/object[i].area;
1580  }
1581  component_view=DestroyCacheView(component_view);
1582  order=1;
1583  artifact=GetImageArtifact(image,"connected-components:sort-order");
1584  if (artifact != (const char *) NULL)
1585  if (LocaleCompare(artifact,"decreasing") == 0)
1586  order=(-1);
1587  key=0;
1588  artifact=GetImageArtifact(image,"connected-components:sort");
1589  if (artifact != (const char *) NULL)
1590  {
1591  if (LocaleCompare(artifact,"area") == 0)
1592  key=1;
1593  if (LocaleCompare(artifact,"width") == 0)
1594  key=2;
1595  if (LocaleCompare(artifact,"height") == 0)
1596  key=3;
1597  if (LocaleCompare(artifact,"x") == 0)
1598  key=4;
1599  if (LocaleCompare(artifact,"y") == 0)
1600  key=5;
1601  }
1602  for (i=0; i < (ssize_t) component_image->colors; i++)
1603  object[i].key=order*key;
1604  qsort((void *) object,component_image->colors,sizeof(*object),
1605  CCObjectInfoCompare);
1606  if (objects == (CCObjectInfo **) NULL)
1607  {
1608  ssize_t
1609  j;
1610 
1611  artifact=GetImageArtifact(image,
1612  "connected-components:exclude-header");
1613  if (IsStringTrue(artifact) == MagickFalse)
1614  {
1615  (void) fprintf(stdout,"Objects (");
1616  artifact=GetImageArtifact(image,
1617  "connected-components:exclude-ids");
1618  if (IsStringTrue(artifact) == MagickFalse)
1619  (void) fprintf(stdout,"id: ");
1620  (void) fprintf(stdout,"bounding-box centroid area mean-color");
1621  for (j=0; j <= n; j++)
1622  (void) fprintf(stdout," %s",metrics[j]);
1623  (void) fprintf(stdout,"):\n");
1624  }
1625  for (i=0; i < (ssize_t) component_image->colors; i++)
1626  if (object[i].census > 0.0)
1627  {
1628  char
1629  mean_color[MagickPathExtent];
1630 
1631  GetColorTuple(&object[i].color,MagickFalse,mean_color);
1632  (void) fprintf(stdout," ");
1633  artifact=GetImageArtifact(image,
1634  "connected-components:exclude-ids");
1635  if (IsStringTrue(artifact) == MagickFalse)
1636  (void) fprintf(stdout,"%.20g: ",(double) object[i].id);
1637  (void) fprintf(stdout,
1638  "%.20gx%.20g%+.20g%+.20g %.1f,%.1f %.*g %s",(double)
1639  object[i].bounding_box.width,(double)
1640  object[i].bounding_box.height,(double)
1641  object[i].bounding_box.x,(double) object[i].bounding_box.y,
1642  object[i].centroid.x,object[i].centroid.y,
1643  GetMagickPrecision(),(double) object[i].area,mean_color);
1644  for (j=0; j <= n; j++)
1645  (void) fprintf(stdout," %.*g",GetMagickPrecision(),
1646  object[i].metric[j]);
1647  (void) fprintf(stdout,"\n");
1648  }
1649  }
1650  }
1651  if (objects == (CCObjectInfo **) NULL)
1652  object=(CCObjectInfo *) RelinquishMagickMemory(object);
1653  else
1654  *objects=object;
1655  return(component_image);
1656 }
1657 
1658 /*
1659 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1660 % %
1661 % %
1662 % %
1663 % I n t e g r a l I m a g e %
1664 % %
1665 % %
1666 % %
1667 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1668 %
1669 % IntegralImage() returns the sum of values (pixel values) in the image.
1670 %
1671 % The format of the IntegralImage method is:
1672 %
1673 % Image *IntegralImage(const Image *image,ExceptionInfo *exception)
1674 %
1675 % A description of each parameter follows:
1676 %
1677 % o image: the image.
1678 %
1679 % o exception: return any errors or warnings in this structure.
1680 %
1681 */
1682 MagickExport Image *IntegralImage(const Image *image,ExceptionInfo *exception)
1683 {
1684 #define IntegralImageTag "Integral/Image"
1685 
1686  CacheView
1687  *image_view,
1688  *integral_view;
1689 
1690  Image
1691  *integral_image;
1692 
1693  MagickBooleanType
1694  status;
1695 
1696  MagickOffsetType
1697  progress;
1698 
1699  ssize_t
1700  y;
1701 
1702  /*
1703  Initialize integral image.
1704  */
1705  assert(image != (const Image *) NULL);
1706  assert(image->signature == MagickCoreSignature);
1707  assert(exception != (ExceptionInfo *) NULL);
1708  assert(exception->signature == MagickCoreSignature);
1709  if (IsEventLogging() != MagickFalse)
1710  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1711  integral_image=CloneImage(image,0,0,MagickTrue,exception);
1712  if (integral_image == (Image *) NULL)
1713  return((Image *) NULL);
1714  if (SetImageStorageClass(integral_image,DirectClass,exception) == MagickFalse)
1715  {
1716  integral_image=DestroyImage(integral_image);
1717  return((Image *) NULL);
1718  }
1719  /*
1720  Calculate the sum of values (pixel values) in the image.
1721  */
1722  status=MagickTrue;
1723  progress=0;
1724  image_view=AcquireVirtualCacheView(integral_image,exception);
1725  integral_view=AcquireAuthenticCacheView(integral_image,exception);
1726  for (y=0; y < (ssize_t) integral_image->rows; y++)
1727  {
1728  const Quantum
1729  *magick_restrict p;
1730 
1731  MagickBooleanType
1732  sync;
1733 
1734  Quantum
1735  *magick_restrict q;
1736 
1737  ssize_t
1738  x;
1739 
1740  if (status == MagickFalse)
1741  continue;
1742  p=GetCacheViewVirtualPixels(integral_view,0,y-1,integral_image->columns,1,
1743  exception);
1744  q=GetCacheViewAuthenticPixels(integral_view,0,y,integral_image->columns,1,
1745  exception);
1746  if ((p == (const Quantum *) NULL) || (p == (Quantum *) NULL))
1747  {
1748  status=MagickFalse;
1749  continue;
1750  }
1751  for (x=0; x < (ssize_t) integral_image->columns; x++)
1752  {
1753  ssize_t
1754  i;
1755 
1756  for (i=0; i < (ssize_t) GetPixelChannels(integral_image); i++)
1757  {
1758  double
1759  sum;
1760 
1761  PixelTrait traits = GetPixelChannelTraits(integral_image,
1762  (PixelChannel) i);
1763  if (traits == UndefinedPixelTrait)
1764  continue;
1765  if ((traits & CopyPixelTrait) != 0)
1766  continue;
1767  sum=(double) q[i];
1768  if (x > 0)
1769  sum+=(double) (q-GetPixelChannels(integral_image))[i];
1770  if (y > 0)
1771  sum+=(double) p[i];
1772  if ((x > 0) && (y > 0))
1773  sum-=(double) (p-GetPixelChannels(integral_image))[i];
1774  q[i]=ClampToQuantum(sum);
1775  }
1776  p+=(ptrdiff_t) GetPixelChannels(integral_image);
1777  q+=(ptrdiff_t) GetPixelChannels(integral_image);
1778  }
1779  sync=SyncCacheViewAuthenticPixels(integral_view,exception);
1780  if (sync == MagickFalse)
1781  status=MagickFalse;
1782  if (image->progress_monitor != (MagickProgressMonitor) NULL)
1783  {
1784  MagickBooleanType
1785  proceed;
1786 
1787  progress++;
1788  proceed=SetImageProgress(integral_image,IntegralImageTag,progress,
1789  integral_image->rows);
1790  if (proceed == MagickFalse)
1791  status=MagickFalse;
1792  }
1793  }
1794  integral_view=DestroyCacheView(integral_view);
1795  image_view=DestroyCacheView(image_view);
1796  if (status == MagickFalse)
1797  integral_image=DestroyImage(integral_image);
1798  return(integral_image);
1799 }
_MatrixInfo
Definition: matrix.c:62
_RectangleInfo
Definition: geometry.h:129
_CacheView
Definition: cache-view.c:65
_Image
Definition: image.h:131
_PixelInfo
Definition: pixel.h:181
_CCObjectInfo
Definition: vision.h:27
_ExceptionInfo
Definition: exception.h:101
_PointInfo
Definition: geometry.h:122