MagickCore 7.1.2-32
Convert, Edit, Or Compose Bitmap Images
Loading...
Searching...
No Matches
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
119static 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
150static 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
257static 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
366static 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
465static 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
564static 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
668static 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
786MagickExport 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 *neighbors,
825 size;
826
827 ssize_t
828 background_id,
829 connect4[2][2] = { { -1, 0 }, { 0, -1 } },
830 connect8[4][2] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 } },
831 dx,
832 dy,
833 first,
834 i,
835 last,
836 n,
837 step,
838 y;
839
840 /*
841 Initialize connected components image attributes.
842 */
843 assert(image != (Image *) NULL);
844 assert(image->signature == MagickCoreSignature);
845 assert(exception != (ExceptionInfo *) NULL);
846 assert(exception->signature == MagickCoreSignature);
847 if (IsEventLogging() != MagickFalse)
848 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
849 if (objects != (CCObjectInfo **) NULL)
850 *objects=(CCObjectInfo *) NULL;
851 component_image=CloneImage(image,0,0,MagickTrue,exception);
852 if (component_image == (Image *) NULL)
853 return((Image *) NULL);
854 component_image->depth=MAGICKCORE_QUANTUM_DEPTH;
855 if (AcquireImageColormap(component_image,MaxColormapSize,exception) == MagickFalse)
856 {
857 component_image=DestroyImage(component_image);
858 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
859 }
860 /*
861 Initialize connected components equivalences.
862 */
863 size=image->columns*image->rows;
864 if (image->columns != (size/image->rows))
865 {
866 component_image=DestroyImage(component_image);
867 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
868 }
869 equivalences=AcquireMatrixInfo(size,1,sizeof(ssize_t),exception);
870 if (equivalences == (MatrixInfo *) NULL)
871 {
872 component_image=DestroyImage(component_image);
873 return((Image *) NULL);
874 }
875 for (n=0; n < (ssize_t) (image->columns*image->rows); n++)
876 (void) SetMatrixElement(equivalences,n,0,&n);
877 object=(CCObjectInfo *) AcquireQuantumMemory(MaxColormapSize,sizeof(*object));
878 if (object == (CCObjectInfo *) NULL)
879 {
880 equivalences=DestroyMatrixInfo(equivalences);
881 component_image=DestroyImage(component_image);
882 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
883 }
884 (void) memset(object,0,MaxColormapSize*sizeof(*object));
885 for (i=0; i < (ssize_t) MaxColormapSize; i++)
886 {
887 object[i].id=i;
888 object[i].bounding_box.x=(ssize_t) image->columns;
889 object[i].bounding_box.y=(ssize_t) image->rows;
890 GetPixelInfo(image,&object[i].color);
891 }
892 /*
893 Find connected components.
894 */
895 status=MagickTrue;
896 progress=0;
897 image_view=AcquireVirtualCacheView(image,exception);
898 for (n=0; n < (ssize_t) (connectivity > 4 ? 4 : 2); n++)
899 {
900 if (status == MagickFalse)
901 continue;
902 dx=connectivity > 4 ? connect8[n][1] : connect4[n][1];
903 dy=connectivity > 4 ? connect8[n][0] : connect4[n][0];
904 for (y=0; y < (ssize_t) image->rows; y++)
905 {
906 const Quantum
907 *magick_restrict p;
908
909 ssize_t
910 x;
911
912 if (status == MagickFalse)
913 continue;
914 p=GetCacheViewVirtualPixels(image_view,0,y-1,image->columns,3,exception);
915 if (p == (const Quantum *) NULL)
916 {
917 status=MagickFalse;
918 continue;
919 }
920 p+=(ptrdiff_t) GetPixelChannels(image)*image->columns;
921 for (x=0; x < (ssize_t) image->columns; x++)
922 {
923 PixelInfo
924 pixel,
925 target;
926
927 ssize_t
928 neighbor_offset,
929 obj,
930 offset,
931 ox,
932 oy,
933 root;
934
935 /*
936 Is neighbor an authentic pixel and a different color than the pixel?
937 */
938 GetPixelInfoPixel(image,p,&pixel);
939 if (((x+dx) < 0) || ((x+dx) >= (ssize_t) image->columns) ||
940 ((y+dy) < 0) || ((y+dy) >= (ssize_t) image->rows))
941 {
942 p+=(ptrdiff_t) GetPixelChannels(image);
943 continue;
944 }
945 neighbor_offset=dy*((ssize_t) GetPixelChannels(image)*(ssize_t)
946 image->columns)+dx*(ssize_t) GetPixelChannels(image);
947 GetPixelInfoPixel(image,p+neighbor_offset,&target);
948 if (IsFuzzyEquivalencePixelInfo(&pixel,&target) == MagickFalse)
949 {
950 p+=(ptrdiff_t) GetPixelChannels(image);
951 continue;
952 }
953 /*
954 Resolve this equivalence.
955 */
956 offset=y*(ssize_t) image->columns+x;
957 neighbor_offset=dy*(ssize_t) image->columns+dx;
958 ox=offset;
959 status=GetMatrixElement(equivalences,ox,0,&obj);
960 while (obj != ox)
961 {
962 ox=obj;
963 status=GetMatrixElement(equivalences,ox,0,&obj);
964 }
965 oy=offset+neighbor_offset;
966 status=GetMatrixElement(equivalences,oy,0,&obj);
967 while (obj != oy)
968 {
969 oy=obj;
970 status=GetMatrixElement(equivalences,oy,0,&obj);
971 }
972 if (ox < oy)
973 {
974 status=SetMatrixElement(equivalences,oy,0,&ox);
975 root=ox;
976 }
977 else
978 {
979 status=SetMatrixElement(equivalences,ox,0,&oy);
980 root=oy;
981 }
982 ox=offset;
983 status=GetMatrixElement(equivalences,ox,0,&obj);
984 while (obj != root)
985 {
986 status=GetMatrixElement(equivalences,ox,0,&obj);
987 status=SetMatrixElement(equivalences,ox,0,&root);
988 }
989 oy=offset+neighbor_offset;
990 status=GetMatrixElement(equivalences,oy,0,&obj);
991 while (obj != root)
992 {
993 status=GetMatrixElement(equivalences,oy,0,&obj);
994 status=SetMatrixElement(equivalences,oy,0,&root);
995 }
996 status=SetMatrixElement(equivalences,y*(ssize_t) image->columns+x,0,
997 &root);
998 p+=(ptrdiff_t) GetPixelChannels(image);
999 }
1000 }
1001 }
1002 /*
1003 Label connected components.
1004 */
1005 n=0;
1006 component_view=AcquireAuthenticCacheView(component_image,exception);
1007 for (y=0; y < (ssize_t) component_image->rows; y++)
1008 {
1009 const Quantum
1010 *magick_restrict p;
1011
1012 Quantum
1013 *magick_restrict q;
1014
1015 ssize_t
1016 x;
1017
1018 if (status == MagickFalse)
1019 continue;
1020 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
1021 q=QueueCacheViewAuthenticPixels(component_view,0,y,component_image->columns,
1022 1,exception);
1023 if ((p == (const Quantum *) NULL) || (q == (Quantum *) NULL))
1024 {
1025 status=MagickFalse;
1026 continue;
1027 }
1028 for (x=0; x < (ssize_t) component_image->columns; x++)
1029 {
1030 ssize_t
1031 id,
1032 offset;
1033
1034 offset=y*(ssize_t) image->columns+x;
1035 status=GetMatrixElement(equivalences,offset,0,&id);
1036 if (id != offset)
1037 status=GetMatrixElement(equivalences,id,0,&id);
1038 else
1039 {
1040 id=n++;
1041 if (id >= (ssize_t) MaxColormapSize)
1042 break;
1043 }
1044 status=SetMatrixElement(equivalences,offset,0,&id);
1045 if (x < object[id].bounding_box.x)
1046 object[id].bounding_box.x=x;
1047 if (x >= (ssize_t) object[id].bounding_box.width)
1048 object[id].bounding_box.width=(size_t) x;
1049 if (y < object[id].bounding_box.y)
1050 object[id].bounding_box.y=y;
1051 if (y >= (ssize_t) object[id].bounding_box.height)
1052 object[id].bounding_box.height=(size_t) y;
1053 object[id].color.red+=QuantumScale*(double) GetPixelRed(image,p);
1054 object[id].color.green+=QuantumScale*(double) GetPixelGreen(image,p);
1055 object[id].color.blue+=QuantumScale*(double) GetPixelBlue(image,p);
1056 if (image->alpha_trait != UndefinedPixelTrait)
1057 object[id].color.alpha+=QuantumScale*(double) GetPixelAlpha(image,p);
1058 if (image->colorspace == CMYKColorspace)
1059 object[id].color.black+=QuantumScale*(double) GetPixelBlack(image,p);
1060 object[id].centroid.x+=x;
1061 object[id].centroid.y+=y;
1062 object[id].area++;
1063 SetPixelIndex(component_image,(Quantum) id,q);
1064 p+=(ptrdiff_t) GetPixelChannels(image);
1065 q+=(ptrdiff_t) GetPixelChannels(component_image);
1066 }
1067 if (n > (ssize_t) MaxColormapSize)
1068 break;
1069 if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
1070 status=MagickFalse;
1071 if (image->progress_monitor != (MagickProgressMonitor) NULL)
1072 {
1073 MagickBooleanType
1074 proceed;
1075
1076 progress++;
1077 proceed=SetImageProgress(image,ConnectedComponentsImageTag,progress,
1078 image->rows);
1079 if (proceed == MagickFalse)
1080 status=MagickFalse;
1081 }
1082 }
1083 component_view=DestroyCacheView(component_view);
1084 image_view=DestroyCacheView(image_view);
1085 equivalences=DestroyMatrixInfo(equivalences);
1086 if (n > (ssize_t) MaxColormapSize)
1087 {
1088 object=(CCObjectInfo *) RelinquishMagickMemory(object);
1089 component_image=DestroyImage(component_image);
1090 ThrowImageException(ResourceLimitError,"TooManyObjects");
1091 }
1092 background_id=0;
1093 min_threshold=0.0;
1094 max_threshold=0.0;
1095 component_image->colors=(size_t) n;
1096 for (i=0; i < (ssize_t) component_image->colors; i++)
1097 {
1098 object[i].bounding_box.width=(size_t) ((ssize_t)
1099 object[i].bounding_box.width-(object[i].bounding_box.x-1));
1100 object[i].bounding_box.height=(size_t) ((ssize_t)
1101 object[i].bounding_box.height-(object[i].bounding_box.y-1));
1102 object[i].color.red/=(QuantumScale*object[i].area);
1103 object[i].color.green/=(QuantumScale*object[i].area);
1104 object[i].color.blue/=(QuantumScale*object[i].area);
1105 if (image->alpha_trait != UndefinedPixelTrait)
1106 object[i].color.alpha/=(QuantumScale*object[i].area);
1107 if (image->colorspace == CMYKColorspace)
1108 object[i].color.black/=(QuantumScale*object[i].area);
1109 object[i].centroid.x/=object[i].area;
1110 object[i].centroid.y/=object[i].area;
1111 max_threshold+=object[i].area;
1112 if (object[i].area > object[background_id].area)
1113 background_id=i;
1114 }
1115 max_threshold+=MagickEpsilon;
1116 n=(-1);
1117 artifact=GetImageArtifact(image,"connected-components:background-id");
1118 if (artifact != (const char *) NULL)
1119 background_id=(ssize_t) StringToLong(artifact);
1120 artifact=GetImageArtifact(image,"connected-components:area-threshold");
1121 if (artifact != (const char *) NULL)
1122 {
1123 /*
1124 Merge any object not within the min and max area threshold.
1125 */
1126 (void) MagickSscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1127 for (i=0; i < (ssize_t) component_image->colors; i++)
1128 if (((object[i].area < min_threshold) ||
1129 (object[i].area >= max_threshold)) && (i != background_id))
1130 object[i].merge=MagickTrue;
1131 }
1132 artifact=GetImageArtifact(image,"connected-components:keep-colors");
1133 if (artifact != (const char *) NULL)
1134 {
1135 const char
1136 *p;
1137
1138 /*
1139 Keep selected objects based on color, merge others.
1140 */
1141 for (i=0; i < (ssize_t) component_image->colors; i++)
1142 object[i].merge=MagickTrue;
1143 for (p=artifact; ; )
1144 {
1145 char
1146 color[MagickPathExtent];
1147
1148 PixelInfo
1149 pixel;
1150
1151 const char
1152 *q;
1153
1154 for (q=p; *q != '\0'; q++)
1155 if (*q == ';')
1156 break;
1157 (void) CopyMagickString(color,p,(size_t) MagickMin(q-p+1,
1158 MagickPathExtent));
1159 (void) QueryColorCompliance(color,AllCompliance,&pixel,exception);
1160 for (i=0; i < (ssize_t) component_image->colors; i++)
1161 if (IsFuzzyEquivalencePixelInfo(&object[i].color,&pixel) != MagickFalse)
1162 object[i].merge=MagickFalse;
1163 if (*q == '\0')
1164 break;
1165 p=q+1;
1166 }
1167 }
1168 artifact=GetImageArtifact(image,"connected-components:keep-ids");
1169 if (artifact == (const char *) NULL)
1170 artifact=GetImageArtifact(image,"connected-components:keep");
1171 if (artifact != (const char *) NULL)
1172 {
1173 /*
1174 Keep selected objects based on id, merge others.
1175 */
1176 for (i=0; i < (ssize_t) component_image->colors; i++)
1177 object[i].merge=MagickTrue;
1178 for (c=(char *) artifact; *c != '\0'; )
1179 {
1180 while ((isspace((int) ((unsigned char) *c)) != 0) || (*c == ','))
1181 c++;
1182 d=c;
1183 first=(ssize_t) strtol(c,&d,10);
1184 if (d == c)
1185 break;
1186 c=d;
1187 if (first < 0)
1188 first+=(ssize_t) component_image->colors;
1189 last=first;
1190 while (isspace((int) ((unsigned char) *c)) != 0)
1191 c++;
1192 if (*c == '-')
1193 {
1194 last=(ssize_t) strtol(c+1,&c,10);
1195 if (last < 0)
1196 last+=(ssize_t) component_image->colors;
1197 }
1198 step=(ssize_t) (first > last ? -1 : 1);
1199 for ( ; first != (last+step); first+=step)
1200 if ((first >= 0) &&
1201 (first < (ssize_t) component_image->colors))
1202 object[first].merge=MagickFalse;
1203 }
1204 }
1205 artifact=GetImageArtifact(image,"connected-components:keep-top");
1206 if (artifact != (const char *) NULL)
1207 {
1208 CCObjectInfo
1209 *top_objects;
1210
1211 ssize_t
1212 top_ids;
1213
1214 /*
1215 Keep top objects.
1216 */
1217 top_ids=(ssize_t) StringToLong(artifact);
1218 if (top_ids < 0)
1219 top_ids=0;
1220 if (top_ids >= (ssize_t) component_image->colors)
1221 top_ids=(ssize_t) component_image->colors-1;
1222 top_objects=(CCObjectInfo *) AcquireQuantumMemory(component_image->colors,
1223 sizeof(*top_objects));
1224 if (top_objects == (CCObjectInfo *) NULL)
1225 {
1226 object=(CCObjectInfo *) RelinquishMagickMemory(object);
1227 component_image=DestroyImage(component_image);
1228 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1229 }
1230 (void) memcpy(top_objects,object,component_image->colors*sizeof(*object));
1231 qsort((void *) top_objects,component_image->colors,sizeof(*top_objects),
1232 CCObjectInfoCompare);
1233 for (i=top_ids+1; i < (ssize_t) component_image->colors; i++)
1234 {
1235 ssize_t id = (ssize_t) top_objects[i].id;
1236 if ((id >= 0) && (id < (ssize_t) component_image->colors))
1237 object[id].merge=MagickTrue;
1238 }
1239 top_objects=(CCObjectInfo *) RelinquishMagickMemory(top_objects);
1240 }
1241 artifact=GetImageArtifact(image,"connected-components:remove-colors");
1242 if (artifact != (const char *) NULL)
1243 {
1244 const char
1245 *p;
1246
1247 /*
1248 Remove selected objects based on color, keep others.
1249 */
1250 for (p=artifact; ; )
1251 {
1252 char
1253 color[MagickPathExtent];
1254
1255 PixelInfo
1256 pixel;
1257
1258 const char
1259 *q;
1260
1261 for (q=p; *q != '\0'; q++)
1262 if (*q == ';')
1263 break;
1264 (void) CopyMagickString(color,p,(size_t) MagickMin(q-p+1,
1265 MagickPathExtent));
1266 (void) QueryColorCompliance(color,AllCompliance,&pixel,exception);
1267 for (i=0; i < (ssize_t) component_image->colors; i++)
1268 if (IsFuzzyEquivalencePixelInfo(&object[i].color,&pixel) != MagickFalse)
1269 object[i].merge=MagickTrue;
1270 if (*q == '\0')
1271 break;
1272 p=q+1;
1273 }
1274 }
1275 artifact=GetImageArtifact(image,"connected-components:remove-ids");
1276 if (artifact == (const char *) NULL)
1277 artifact=GetImageArtifact(image,"connected-components:remove");
1278 if (artifact != (const char *) NULL)
1279 for (c=(char *) artifact; *c != '\0'; )
1280 {
1281 /*
1282 Remove selected objects based on id, keep others.
1283 */
1284 while ((isspace((int) ((unsigned char) *c)) != 0) || (*c == ','))
1285 c++;
1286 d=c;
1287 first=(ssize_t) strtol(c,&d,10);
1288 if (d == c)
1289 break;
1290 c=d;
1291 if (first < 0)
1292 first+=(ssize_t) component_image->colors;
1293 last=first;
1294 while (isspace((int) ((unsigned char) *c)) != 0)
1295 c++;
1296 if (*c == '-')
1297 {
1298 last=(ssize_t) strtol(c+1,&c,10);
1299 if (last < 0)
1300 last+=(ssize_t) component_image->colors;
1301 }
1302 step=(ssize_t) (first > last ? -1 : 1);
1303 for ( ; first != (last+step); first+=step)
1304 if ((first >= 0) &&
1305 (first < (ssize_t) component_image->colors))
1306 object[first].merge=MagickTrue;
1307 }
1308 artifact=GetImageArtifact(image,"connected-components:perimeter-threshold");
1309 if (artifact != (const char *) NULL)
1310 {
1311 /*
1312 Merge any object not within the min and max perimeter threshold.
1313 */
1314 (void) MagickSscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1315 metrics[++n]="perimeter";
1316 PerimeterThreshold(component_image,object,n,exception);
1317 for (i=0; i < (ssize_t) component_image->colors; i++)
1318 if (((object[i].metric[n] < min_threshold) ||
1319 (object[i].metric[n] >= max_threshold)) && (i != background_id))
1320 object[i].merge=MagickTrue;
1321 }
1322 artifact=GetImageArtifact(image,"connected-components:circularity-threshold");
1323 if (artifact != (const char *) NULL)
1324 {
1325 /*
1326 Merge any object not within the min and max circularity threshold.
1327 */
1328 (void) MagickSscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1329 metrics[++n]="circularity";
1330 CircularityThreshold(component_image,object,n,exception);
1331 for (i=0; i < (ssize_t) component_image->colors; i++)
1332 if (((object[i].metric[n] < min_threshold) ||
1333 (object[i].metric[n] >= max_threshold)) && (i != background_id))
1334 object[i].merge=MagickTrue;
1335 }
1336 artifact=GetImageArtifact(image,"connected-components:diameter-threshold");
1337 if (artifact != (const char *) NULL)
1338 {
1339 /*
1340 Merge any object not within the min and max diameter threshold.
1341 */
1342 (void) MagickSscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1343 metrics[++n]="diameter";
1344 for (i=0; i < (ssize_t) component_image->colors; i++)
1345 {
1346 object[i].metric[n]=ceil(sqrt(4.0*object[i].area/MagickPI)-0.5);
1347 if (((object[i].metric[n] < min_threshold) ||
1348 (object[i].metric[n] >= max_threshold)) && (i != background_id))
1349 object[i].merge=MagickTrue;
1350 }
1351 }
1352 artifact=GetImageArtifact(image,"connected-components:major-axis-threshold");
1353 if (artifact != (const char *) NULL)
1354 {
1355 /*
1356 Merge any object not within the min and max ellipse major threshold.
1357 */
1358 (void) MagickSscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1359 metrics[++n]="major-axis";
1360 MajorAxisThreshold(component_image,object,n,exception);
1361 for (i=0; i < (ssize_t) component_image->colors; i++)
1362 if (((object[i].metric[n] < min_threshold) ||
1363 (object[i].metric[n] >= max_threshold)) && (i != background_id))
1364 object[i].merge=MagickTrue;
1365 }
1366 artifact=GetImageArtifact(image,"connected-components:minor-axis-threshold");
1367 if (artifact != (const char *) NULL)
1368 {
1369 /*
1370 Merge any object not within the min and max ellipse minor threshold.
1371 */
1372 (void) MagickSscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1373 metrics[++n]="minor-axis";
1374 MinorAxisThreshold(component_image,object,n,exception);
1375 for (i=0; i < (ssize_t) component_image->colors; i++)
1376 if (((object[i].metric[n] < min_threshold) ||
1377 (object[i].metric[n] >= max_threshold)) && (i != background_id))
1378 object[i].merge=MagickTrue;
1379 }
1380 artifact=GetImageArtifact(image,"connected-components:eccentricity-threshold");
1381 if (artifact != (const char *) NULL)
1382 {
1383 /*
1384 Merge any object not within the min and max eccentricity threshold.
1385 */
1386 (void) MagickSscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1387 metrics[++n]="eccentricity";
1388 EccentricityThreshold(component_image,object,n,exception);
1389 for (i=0; i < (ssize_t) component_image->colors; i++)
1390 if (((object[i].metric[n] < min_threshold) ||
1391 (object[i].metric[n] >= max_threshold)) && (i != background_id))
1392 object[i].merge=MagickTrue;
1393 }
1394 artifact=GetImageArtifact(image,"connected-components:angle-threshold");
1395 if (artifact != (const char *) NULL)
1396 {
1397 /*
1398 Merge any object not within the min and max ellipse angle threshold.
1399 */
1400 (void) MagickSscanf(artifact,"%lf%*[ -]%lf",&min_threshold,&max_threshold);
1401 metrics[++n]="angle";
1402 AngleThreshold(component_image,object,n,exception);
1403 for (i=0; i < (ssize_t) component_image->colors; i++)
1404 if (((object[i].metric[n] < min_threshold) ||
1405 (object[i].metric[n] >= max_threshold)) && (i != background_id))
1406 object[i].merge=MagickTrue;
1407 }
1408 /*
1409 Merge any object not within the min and max area threshold.
1410 */
1411 neighbors=(size_t *) AcquireQuantumMemory(component_image->colors+1,
1412 sizeof(*neighbors));
1413 if (neighbors == (size_t *) NULL)
1414 {
1415 object=(CCObjectInfo *) RelinquishMagickMemory(object);
1416 component_image=DestroyImage(component_image);
1417 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1418 }
1419 component_view=AcquireAuthenticCacheView(component_image,exception);
1420 object_view=AcquireVirtualCacheView(component_image,exception);
1421 (void) SetCacheViewVirtualPixelMethod(object_view,TileVirtualPixelMethod);
1422 for (i=0; i < (ssize_t) component_image->colors; i++)
1423 {
1424 RectangleInfo
1425 bounding_box;
1426
1427 size_t
1428 count,
1429 id;
1430
1431 ssize_t
1432 j;
1433
1434 if (status == MagickFalse)
1435 continue;
1436 if ((object[i].merge == MagickFalse) || (i == background_id))
1437 continue; /* keep object */
1438 /*
1439 Merge this object.
1440 */
1441 count=0;
1442 bounding_box=object[i].bounding_box;
1443 for (y=0; y < (ssize_t) bounding_box.height; y++)
1444 {
1445 const Quantum
1446 *magick_restrict p;
1447
1448 ssize_t
1449 x;
1450
1451 if (status == MagickFalse)
1452 continue;
1453 p=GetCacheViewVirtualPixels(component_view,bounding_box.x,
1454 bounding_box.y+y,bounding_box.width,1,exception);
1455 if (p == (const Quantum *) NULL)
1456 {
1457 status=MagickFalse;
1458 continue;
1459 }
1460 for (x=0; x < (ssize_t) bounding_box.width; x++)
1461 {
1462 ssize_t
1463 k;
1464
1465 if (status == MagickFalse)
1466 continue;
1467 j=(ssize_t) GetPixelIndex(component_image,p);
1468 if (j == i)
1469 for (k=0; k < (ssize_t) (connectivity > 4 ? 4 : 2); k++)
1470 {
1471 const Quantum
1472 *q;
1473
1474 /*
1475 Compute area of adjacent objects.
1476 */
1477 if (status == MagickFalse)
1478 continue;
1479 dx=connectivity > 4 ? connect8[k][1] : connect4[k][1];
1480 dy=connectivity > 4 ? connect8[k][0] : connect4[k][0];
1481 q=GetCacheViewVirtualPixels(object_view,bounding_box.x+x+dx,
1482 bounding_box.y+y+dy,1,1,exception);
1483 if (q == (const Quantum *) NULL)
1484 {
1485 status=MagickFalse;
1486 break;
1487 }
1488 j=(ssize_t) GetPixelIndex(component_image,q);
1489 if (j != i)
1490 {
1491 if (object[j].census == 0.0)
1492 neighbors[count++]=(size_t) j;
1493 object[j].census++;
1494 }
1495 }
1496 p+=(ptrdiff_t) GetPixelChannels(component_image);
1497 }
1498 }
1499 /*
1500 Merge with object of greatest adjacent area.
1501 */
1502 id=0;
1503 for (j=0; j < (ssize_t) count; j++)
1504 if ((object[neighbors[j]].census > object[id].census) ||
1505 ((object[neighbors[j]].census == object[id].census) &&
1506 (neighbors[j] < id)))
1507 id=neighbors[j];
1508 for (j=0; j < (ssize_t) count; j++)
1509 object[neighbors[j]].census=0.0;
1510 object[i].area=0.0;
1511 for (y=0; y < (ssize_t) bounding_box.height; y++)
1512 {
1513 Quantum
1514 *magick_restrict q;
1515
1516 ssize_t
1517 x;
1518
1519 if (status == MagickFalse)
1520 continue;
1521 q=GetCacheViewAuthenticPixels(component_view,bounding_box.x,
1522 bounding_box.y+y,bounding_box.width,1,exception);
1523 if (q == (Quantum *) NULL)
1524 {
1525 status=MagickFalse;
1526 continue;
1527 }
1528 for (x=0; x < (ssize_t) bounding_box.width; x++)
1529 {
1530 if ((ssize_t) GetPixelIndex(component_image,q) == i)
1531 SetPixelIndex(component_image,(Quantum) id,q);
1532 q+=(ptrdiff_t) GetPixelChannels(component_image);
1533 }
1534 if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
1535 status=MagickFalse;
1536 }
1537 }
1538 object_view=DestroyCacheView(object_view);
1539 component_view=DestroyCacheView(component_view);
1540 neighbors=(size_t *) RelinquishMagickMemory(neighbors);
1541 artifact=GetImageArtifact(image,"connected-components:mean-color");
1542 if (IsStringTrue(artifact) != MagickFalse)
1543 {
1544 /*
1545 Replace object with mean color.
1546 */
1547 for (i=0; i < (ssize_t) component_image->colors; i++)
1548 component_image->colormap[i]=object[i].color;
1549 }
1550 (void) SyncImage(component_image,exception);
1551 artifact=GetImageArtifact(image,"connected-components:verbose");
1552 if ((IsStringTrue(artifact) != MagickFalse) ||
1553 (objects != (CCObjectInfo **) NULL))
1554 {
1555 ssize_t
1556 key,
1557 order;
1558
1559 /*
1560 Report statistics on each unique object.
1561 */
1562 for (i=0; i < (ssize_t) component_image->colors; i++)
1563 {
1564 object[i].bounding_box.width=0;
1565 object[i].bounding_box.height=0;
1566 object[i].bounding_box.x=(ssize_t) component_image->columns;
1567 object[i].bounding_box.y=(ssize_t) component_image->rows;
1568 object[i].centroid.x=0;
1569 object[i].centroid.y=0;
1570 object[i].census=object[i].area == 0.0 ? 0.0 : 1.0;
1571 object[i].area=0;
1572 }
1573 component_view=AcquireVirtualCacheView(component_image,exception);
1574 for (y=0; y < (ssize_t) component_image->rows; y++)
1575 {
1576 const Quantum
1577 *magick_restrict p;
1578
1579 ssize_t
1580 x;
1581
1582 if (status == MagickFalse)
1583 continue;
1584 p=GetCacheViewVirtualPixels(component_view,0,y,component_image->columns,
1585 1,exception);
1586 if (p == (const Quantum *) NULL)
1587 {
1588 status=MagickFalse;
1589 continue;
1590 }
1591 for (x=0; x < (ssize_t) component_image->columns; x++)
1592 {
1593 size_t
1594 id;
1595
1596 id=(size_t) GetPixelIndex(component_image,p);
1597 if (x < object[id].bounding_box.x)
1598 object[id].bounding_box.x=x;
1599 if (x > (ssize_t) object[id].bounding_box.width)
1600 object[id].bounding_box.width=(size_t) x;
1601 if (y < object[id].bounding_box.y)
1602 object[id].bounding_box.y=y;
1603 if (y > (ssize_t) object[id].bounding_box.height)
1604 object[id].bounding_box.height=(size_t) y;
1605 object[id].centroid.x+=x;
1606 object[id].centroid.y+=y;
1607 object[id].area++;
1608 p+=(ptrdiff_t) GetPixelChannels(component_image);
1609 }
1610 }
1611 for (i=0; i < (ssize_t) component_image->colors; i++)
1612 {
1613 object[i].bounding_box.width=(size_t) ((ssize_t)
1614 object[i].bounding_box.width-(object[i].bounding_box.x-1));
1615 object[i].bounding_box.height=(size_t) ((ssize_t)
1616 object[i].bounding_box.height-(object[i].bounding_box.y-1));
1617 object[i].centroid.x=object[i].centroid.x/object[i].area;
1618 object[i].centroid.y=object[i].centroid.y/object[i].area;
1619 }
1620 component_view=DestroyCacheView(component_view);
1621 order=1;
1622 artifact=GetImageArtifact(image,"connected-components:sort-order");
1623 if (artifact != (const char *) NULL)
1624 if (LocaleCompare(artifact,"decreasing") == 0)
1625 order=(-1);
1626 key=0;
1627 artifact=GetImageArtifact(image,"connected-components:sort");
1628 if (artifact != (const char *) NULL)
1629 {
1630 if (LocaleCompare(artifact,"area") == 0)
1631 key=1;
1632 if (LocaleCompare(artifact,"width") == 0)
1633 key=2;
1634 if (LocaleCompare(artifact,"height") == 0)
1635 key=3;
1636 if (LocaleCompare(artifact,"x") == 0)
1637 key=4;
1638 if (LocaleCompare(artifact,"y") == 0)
1639 key=5;
1640 }
1641 for (i=0; i < (ssize_t) component_image->colors; i++)
1642 object[i].key=order*key;
1643 qsort((void *) object,component_image->colors,sizeof(*object),
1644 CCObjectInfoCompare);
1645 if (objects == (CCObjectInfo **) NULL)
1646 {
1647 ssize_t
1648 j;
1649
1650 artifact=GetImageArtifact(image,
1651 "connected-components:exclude-header");
1652 if (IsStringTrue(artifact) == MagickFalse)
1653 {
1654 (void) fprintf(stdout,"Objects (");
1655 artifact=GetImageArtifact(image,
1656 "connected-components:exclude-ids");
1657 if (IsStringTrue(artifact) == MagickFalse)
1658 (void) fprintf(stdout,"id: ");
1659 (void) fprintf(stdout,"bounding-box centroid area mean-color");
1660 for (j=0; j <= n; j++)
1661 (void) fprintf(stdout," %s",metrics[j]);
1662 (void) fprintf(stdout,"):\n");
1663 }
1664 for (i=0; i < (ssize_t) component_image->colors; i++)
1665 if (object[i].census > 0.0)
1666 {
1667 char
1668 mean_color[MagickPathExtent];
1669
1670 GetColorTuple(&object[i].color,MagickFalse,mean_color);
1671 (void) fprintf(stdout," ");
1672 artifact=GetImageArtifact(image,
1673 "connected-components:exclude-ids");
1674 if (IsStringTrue(artifact) == MagickFalse)
1675 (void) fprintf(stdout,"%.17g: ",(double) object[i].id);
1676 (void) fprintf(stdout,
1677 "%.17gx%.17g%+.20g%+.20g %.1f,%.1f %.*g %s",(double)
1678 object[i].bounding_box.width,(double)
1679 object[i].bounding_box.height,(double)
1680 object[i].bounding_box.x,(double) object[i].bounding_box.y,
1681 object[i].centroid.x,object[i].centroid.y,
1682 GetMagickPrecision(),(double) object[i].area,mean_color);
1683 for (j=0; j <= n; j++)
1684 (void) fprintf(stdout," %.*g",GetMagickPrecision(),
1685 object[i].metric[j]);
1686 (void) fprintf(stdout,"\n");
1687 }
1688 }
1689 }
1690 if (objects == (CCObjectInfo **) NULL)
1691 object=(CCObjectInfo *) RelinquishMagickMemory(object);
1692 else
1693 *objects=object;
1694 return(component_image);
1695}
1696␌
1697/*
1698%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1699% %
1700% %
1701% %
1702% I n t e g r a l I m a g e %
1703% %
1704% %
1705% %
1706%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1707%
1708% IntegralImage() returns the sum of values (pixel values) in the image.
1709%
1710% The format of the IntegralImage method is:
1711%
1712% Image *IntegralImage(const Image *image,ExceptionInfo *exception)
1713%
1714% A description of each parameter follows:
1715%
1716% o image: the image.
1717%
1718% o exception: return any errors or warnings in this structure.
1719%
1720*/
1721MagickExport Image *IntegralImage(const Image *image,ExceptionInfo *exception)
1722{
1723#define IntegralImageTag "Integral/Image"
1724
1725 CacheView
1726 *image_view,
1727 *integral_view;
1728
1729 Image
1730 *integral_image;
1731
1732 MagickBooleanType
1733 status;
1734
1735 MagickOffsetType
1736 progress;
1737
1738 ssize_t
1739 y;
1740
1741 /*
1742 Initialize integral image.
1743 */
1744 assert(image != (const Image *) NULL);
1745 assert(image->signature == MagickCoreSignature);
1746 assert(exception != (ExceptionInfo *) NULL);
1747 assert(exception->signature == MagickCoreSignature);
1748 if (IsEventLogging() != MagickFalse)
1749 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1750 integral_image=CloneImage(image,0,0,MagickTrue,exception);
1751 if (integral_image == (Image *) NULL)
1752 return((Image *) NULL);
1753 if (SetImageStorageClass(integral_image,DirectClass,exception) == MagickFalse)
1754 {
1755 integral_image=DestroyImage(integral_image);
1756 return((Image *) NULL);
1757 }
1758 /*
1759 Calculate the sum of values (pixel values) in the image.
1760 */
1761 status=MagickTrue;
1762 progress=0;
1763 image_view=AcquireVirtualCacheView(integral_image,exception);
1764 integral_view=AcquireAuthenticCacheView(integral_image,exception);
1765 for (y=0; y < (ssize_t) integral_image->rows; y++)
1766 {
1767 const Quantum
1768 *magick_restrict p;
1769
1770 MagickBooleanType
1771 sync;
1772
1773 Quantum
1774 *magick_restrict q;
1775
1776 ssize_t
1777 x;
1778
1779 if (status == MagickFalse)
1780 continue;
1781 p=GetCacheViewVirtualPixels(integral_view,0,y-1,integral_image->columns,1,
1782 exception);
1783 q=GetCacheViewAuthenticPixels(integral_view,0,y,integral_image->columns,1,
1784 exception);
1785 if ((p == (const Quantum *) NULL) || (p == (Quantum *) NULL))
1786 {
1787 status=MagickFalse;
1788 continue;
1789 }
1790 for (x=0; x < (ssize_t) integral_image->columns; x++)
1791 {
1792 ssize_t
1793 i;
1794
1795 for (i=0; i < (ssize_t) GetPixelChannels(integral_image); i++)
1796 {
1797 double
1798 sum;
1799
1800 PixelTrait traits = GetPixelChannelTraits(integral_image,
1801 (PixelChannel) i);
1802 if (traits == UndefinedPixelTrait)
1803 continue;
1804 if ((traits & CopyPixelTrait) != 0)
1805 continue;
1806 sum=(double) q[i];
1807 if (x > 0)
1808 sum+=(double) (q-GetPixelChannels(integral_image))[i];
1809 if (y > 0)
1810 sum+=(double) p[i];
1811 if ((x > 0) && (y > 0))
1812 sum-=(double) (p-GetPixelChannels(integral_image))[i];
1813 q[i]=ClampToQuantum(sum);
1814 }
1815 p+=(ptrdiff_t) GetPixelChannels(integral_image);
1816 q+=(ptrdiff_t) GetPixelChannels(integral_image);
1817 }
1818 sync=SyncCacheViewAuthenticPixels(integral_view,exception);
1819 if (sync == MagickFalse)
1820 status=MagickFalse;
1821 if (image->progress_monitor != (MagickProgressMonitor) NULL)
1822 {
1823 MagickBooleanType
1824 proceed;
1825
1826 progress++;
1827 proceed=SetImageProgress(integral_image,IntegralImageTag,progress,
1828 integral_image->rows);
1829 if (proceed == MagickFalse)
1830 status=MagickFalse;
1831 }
1832 }
1833 integral_view=DestroyCacheView(integral_view);
1834 image_view=DestroyCacheView(image_view);
1835 if (status == MagickFalse)
1836 integral_image=DestroyImage(integral_image);
1837 return(integral_image);
1838}