MagickCore  7.0.3
segment.c
Go to the documentation of this file.
1 /*
2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
3 % %
4 % %
5 % %
6 % SSSSS EEEEE GGGG M M EEEEE N N TTTTT %
7 % SS E G MM MM E NN N T %
8 % SSS EEE G GGG M M M EEE N N N T %
9 % SS E G G M M E N NN T %
10 % SSSSS EEEEE GGGG M M EEEEE N N T %
11 % %
12 % %
13 % MagickCore Methods to Segment an Image with Thresholding Fuzzy c-Means %
14 % %
15 % Software Design %
16 % Cristy %
17 % April 1993 %
18 % %
19 % %
20 % Copyright 1999-2019 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 % Segment segments an image by analyzing the histograms of the color
37 % components and identifying units that are homogeneous with the fuzzy
38 % c-means technique. The scale-space filter analyzes the histograms of
39 % the three color components of the image and identifies a set of
40 % classes. The extents of each class is used to coarsely segment the
41 % image with thresholding. The color associated with each class is
42 % determined by the mean color of all pixels within the extents of a
43 % particular class. Finally, any unclassified pixels are assigned to
44 % the closest class with the fuzzy c-means technique.
45 %
46 % The fuzzy c-Means algorithm can be summarized as follows:
47 %
48 % o Build a histogram, one for each color component of the image.
49 %
50 % o For each histogram, successively apply the scale-space filter and
51 % build an interval tree of zero crossings in the second derivative
52 % at each scale. Analyze this scale-space ''fingerprint'' to
53 % determine which peaks and valleys in the histogram are most
54 % predominant.
55 %
56 % o The fingerprint defines intervals on the axis of the histogram.
57 % Each interval contains either a minima or a maxima in the original
58 % signal. If each color component lies within the maxima interval,
59 % that pixel is considered ''classified'' and is assigned an unique
60 % class number.
61 %
62 % o Any pixel that fails to be classified in the above thresholding
63 % pass is classified using the fuzzy c-Means technique. It is
64 % assigned to one of the classes discovered in the histogram analysis
65 % phase.
66 %
67 % The fuzzy c-Means technique attempts to cluster a pixel by finding
68 % the local minima of the generalized within group sum of squared error
69 % objective function. A pixel is assigned to the closest class of
70 % which the fuzzy membership has a maximum value.
71 %
72 % Segment is strongly based on software written by Andy Gallo,
73 % University of Delaware.
74 %
75 % The following reference was used in creating this program:
76 %
77 % Young Won Lim, Sang Uk Lee, "On The Color Image Segmentation
78 % Algorithm Based on the Thresholding and the Fuzzy c-Means
79 % Techniques", Pattern Recognition, Volume 23, Number 9, pages
80 % 935-952, 1990.
81 %
82 %
83 */
84 
85 #include "MagickCore/studio.h"
86 #include "MagickCore/cache.h"
87 #include "MagickCore/color.h"
88 #include "MagickCore/colormap.h"
89 #include "MagickCore/colorspace.h"
91 #include "MagickCore/exception.h"
93 #include "MagickCore/image.h"
95 #include "MagickCore/memory_.h"
97 #include "MagickCore/monitor.h"
101 #include "MagickCore/quantize.h"
102 #include "MagickCore/quantum.h"
104 #include "MagickCore/resource_.h"
105 #include "MagickCore/segment.h"
106 #include "MagickCore/string_.h"
108 
109 /*
110  Define declarations.
111 */
112 #define MaxDimension 3
113 #define DeltaTau 0.5f
114 #if defined(FastClassify)
115 #define WeightingExponent 2.0
116 #define SegmentPower(ratio) (ratio)
117 #else
118 #define WeightingExponent 2.5
119 #define SegmentPower(ratio) pow(ratio,(double) (1.0/(weighting_exponent-1.0)));
120 #endif
121 #define Tau 5.2f
122 
123 /*
124  Typedef declarations.
125 */
126 typedef struct _ExtentPacket
127 {
128  double
130 
131  ssize_t
133  left,
134  right;
135 } ExtentPacket;
136 
137 typedef struct _Cluster
138 {
139  struct _Cluster
140  *next;
141 
144  green,
145  blue;
146 
147  ssize_t
149  id;
150 } Cluster;
151 
152 typedef struct _IntervalTree
153 {
154  double
156 
157  ssize_t
159  right;
160 
161  double
163  stability;
164 
166  *sibling,
167  *child;
168 } IntervalTree;
169 
170 typedef struct _ZeroCrossing
171 {
172  double
174  histogram[256];
175 
176  short
177  crossings[256];
178 } ZeroCrossing;
179 
180 /*
181  Constant declarations.
182 */
183 static const int
184  Blue = 2,
185  Green = 1,
186  Red = 0,
188  TreeLength = 600;
189 
190 /*
191  Method prototypes.
192 */
193 static double
194  OptimalTau(const ssize_t *,const double,const double,const double,
195  const double,short *);
196 
197 static ssize_t
198  DefineRegion(const short *,ExtentPacket *);
199 
200 static void
202  InitializeHistogram(const Image *,ssize_t **,ExceptionInfo *),
203  ScaleSpace(const ssize_t *,const double,double *),
204  ZeroCrossHistogram(double *,const double,short *);
205 
206 /*
207 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
208 % %
209 % %
210 % %
211 + C l a s s i f y %
212 % %
213 % %
214 % %
215 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
216 %
217 % Classify() defines one or more classes. Each pixel is thresholded to
218 % determine which class it belongs to. If the class is not identified it is
219 % assigned to the closest class based on the fuzzy c-Means technique.
220 %
221 % The format of the Classify method is:
222 %
223 % MagickBooleanType Classify(Image *image,short **extrema,
224 % const double cluster_threshold,
225 % const double weighting_exponent,
226 % const MagickBooleanType verbose,ExceptionInfo *exception)
227 %
228 % A description of each parameter follows.
229 %
230 % o image: the image.
231 %
232 % o extrema: Specifies a pointer to an array of integers. They
233 % represent the peaks and valleys of the histogram for each color
234 % component.
235 %
236 % o cluster_threshold: This double represents the minimum number of
237 % pixels contained in a hexahedra before it can be considered valid
238 % (expressed as a percentage).
239 %
240 % o weighting_exponent: Specifies the membership weighting exponent.
241 %
242 % o verbose: A value greater than zero prints detailed information about
243 % the identified classes.
244 %
245 % o exception: return any errors or warnings in this structure.
246 %
247 */
248 static MagickBooleanType Classify(Image *image,short **extrema,
249  const double cluster_threshold,
250  const double weighting_exponent,const MagickBooleanType verbose,
251  ExceptionInfo *exception)
252 {
253 #define SegmentImageTag "Segment/Image"
254 #define ThrowClassifyException(severity,tag,label) \
255 {\
256  for (cluster=head; cluster != (Cluster *) NULL; cluster=next_cluster) \
257  { \
258  next_cluster=cluster->next; \
259  cluster=(Cluster *) RelinquishMagickMemory(cluster); \
260  } \
261  if (squares != (double *) NULL) \
262  { \
263  squares-=255; \
264  free_squares=squares; \
265  free_squares=(double *) RelinquishMagickMemory(free_squares); \
266  } \
267  ThrowBinaryException(severity,tag,label); \
268 }
269 
270  CacheView
271  *image_view;
272 
273  Cluster
274  *cluster,
275  *head,
276  *last_cluster,
277  *next_cluster;
278 
280  blue,
281  green,
282  red;
283 
285  progress;
286 
287  double
288  *free_squares;
289 
291  status;
292 
293  register ssize_t
294  i;
295 
296  register double
297  *squares;
298 
299  size_t
300  number_clusters;
301 
302  ssize_t
303  count,
304  y;
305 
306  /*
307  Form clusters.
308  */
309  cluster=(Cluster *) NULL;
310  head=(Cluster *) NULL;
311  squares=(double *) NULL;
312  (void) memset(&red,0,sizeof(red));
313  (void) memset(&green,0,sizeof(green));
314  (void) memset(&blue,0,sizeof(blue));
315  while (DefineRegion(extrema[Red],&red) != 0)
316  {
317  green.index=0;
318  while (DefineRegion(extrema[Green],&green) != 0)
319  {
320  blue.index=0;
321  while (DefineRegion(extrema[Blue],&blue) != 0)
322  {
323  /*
324  Allocate a new class.
325  */
326  if (head != (Cluster *) NULL)
327  {
328  cluster->next=(Cluster *) AcquireMagickMemory(
329  sizeof(*cluster->next));
330  cluster=cluster->next;
331  }
332  else
333  {
334  cluster=(Cluster *) AcquireMagickMemory(sizeof(*cluster));
335  head=cluster;
336  }
337  if (cluster == (Cluster *) NULL)
338  ThrowClassifyException(ResourceLimitError,"MemoryAllocationFailed",
339  image->filename);
340  /*
341  Initialize a new class.
342  */
343  cluster->count=0;
344  cluster->red=red;
345  cluster->green=green;
346  cluster->blue=blue;
347  cluster->next=(Cluster *) NULL;
348  }
349  }
350  }
351  if (head == (Cluster *) NULL)
352  {
353  /*
354  No classes were identified-- create one.
355  */
356  cluster=(Cluster *) AcquireMagickMemory(sizeof(*cluster));
357  if (cluster == (Cluster *) NULL)
358  ThrowClassifyException(ResourceLimitError,"MemoryAllocationFailed",
359  image->filename);
360  /*
361  Initialize a new class.
362  */
363  cluster->count=0;
364  cluster->red=red;
365  cluster->green=green;
366  cluster->blue=blue;
367  cluster->next=(Cluster *) NULL;
368  head=cluster;
369  }
370  /*
371  Count the pixels for each cluster.
372  */
373  status=MagickTrue;
374  count=0;
375  progress=0;
376  image_view=AcquireVirtualCacheView(image,exception);
377  for (y=0; y < (ssize_t) image->rows; y++)
378  {
379  register const Quantum
380  *p;
381 
382  register ssize_t
383  x;
384 
385  p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
386  if (p == (const Quantum *) NULL)
387  break;
388  for (x=0; x < (ssize_t) image->columns; x++)
389  {
390  for (cluster=head; cluster != (Cluster *) NULL; cluster=cluster->next)
391  if (((ssize_t) ScaleQuantumToChar(GetPixelRed(image,p)) >=
392  (cluster->red.left-SafeMargin)) &&
393  ((ssize_t) ScaleQuantumToChar(GetPixelRed(image,p)) <=
394  (cluster->red.right+SafeMargin)) &&
395  ((ssize_t) ScaleQuantumToChar(GetPixelGreen(image,p)) >=
396  (cluster->green.left-SafeMargin)) &&
397  ((ssize_t) ScaleQuantumToChar(GetPixelGreen(image,p)) <=
398  (cluster->green.right+SafeMargin)) &&
399  ((ssize_t) ScaleQuantumToChar(GetPixelBlue(image,p)) >=
400  (cluster->blue.left-SafeMargin)) &&
401  ((ssize_t) ScaleQuantumToChar(GetPixelBlue(image,p)) <=
402  (cluster->blue.right+SafeMargin)))
403  {
404  /*
405  Count this pixel.
406  */
407  count++;
408  cluster->red.center+=(double) ScaleQuantumToChar(
409  GetPixelRed(image,p));
410  cluster->green.center+=(double) ScaleQuantumToChar(
411  GetPixelGreen(image,p));
412  cluster->blue.center+=(double) ScaleQuantumToChar(
413  GetPixelBlue(image,p));
414  cluster->count++;
415  break;
416  }
417  p+=GetPixelChannels(image);
418  }
419  if (image->progress_monitor != (MagickProgressMonitor) NULL)
420  {
422  proceed;
423 
424 #if defined(MAGICKCORE_OPENMP_SUPPORT)
425  #pragma omp atomic
426 #endif
427  progress++;
428  proceed=SetImageProgress(image,SegmentImageTag,progress,2*image->rows);
429  if (proceed == MagickFalse)
430  status=MagickFalse;
431  }
432  }
433  image_view=DestroyCacheView(image_view);
434  /*
435  Remove clusters that do not meet minimum cluster threshold.
436  */
437  count=0;
438  last_cluster=head;
439  next_cluster=head;
440  for (cluster=head; cluster != (Cluster *) NULL; cluster=next_cluster)
441  {
442  next_cluster=cluster->next;
443  if ((cluster->count > 0) &&
444  (cluster->count >= (count*cluster_threshold/100.0)))
445  {
446  /*
447  Initialize cluster.
448  */
449  cluster->id=count;
450  cluster->red.center/=cluster->count;
451  cluster->green.center/=cluster->count;
452  cluster->blue.center/=cluster->count;
453  count++;
454  last_cluster=cluster;
455  continue;
456  }
457  /*
458  Delete cluster.
459  */
460  if (cluster == head)
461  head=next_cluster;
462  else
463  last_cluster->next=next_cluster;
464  cluster=(Cluster *) RelinquishMagickMemory(cluster);
465  }
466  number_clusters=(size_t) count;
467  if (verbose != MagickFalse)
468  {
469  /*
470  Print cluster statistics.
471  */
472  (void) FormatLocaleFile(stdout,"Fuzzy C-means Statistics\n");
473  (void) FormatLocaleFile(stdout,"===================\n\n");
474  (void) FormatLocaleFile(stdout,"\tCluster Threshold = %g\n",(double)
475  cluster_threshold);
476  (void) FormatLocaleFile(stdout,"\tWeighting Exponent = %g\n",(double)
477  weighting_exponent);
478  (void) FormatLocaleFile(stdout,"\tTotal Number of Clusters = %.20g\n\n",
479  (double) number_clusters);
480  /*
481  Print the total number of points per cluster.
482  */
483  (void) FormatLocaleFile(stdout,"\n\nNumber of Vectors Per Cluster\n");
484  (void) FormatLocaleFile(stdout,"=============================\n\n");
485  for (cluster=head; cluster != (Cluster *) NULL; cluster=cluster->next)
486  (void) FormatLocaleFile(stdout,"Cluster #%.20g = %.20g\n",(double)
487  cluster->id,(double) cluster->count);
488  /*
489  Print the cluster extents.
490  */
491  (void) FormatLocaleFile(stdout,
492  "\n\n\nCluster Extents: (Vector Size: %d)\n",MaxDimension);
493  (void) FormatLocaleFile(stdout,"================");
494  for (cluster=head; cluster != (Cluster *) NULL; cluster=cluster->next)
495  {
496  (void) FormatLocaleFile(stdout,"\n\nCluster #%.20g\n\n",(double)
497  cluster->id);
498  (void) FormatLocaleFile(stdout,
499  "%.20g-%.20g %.20g-%.20g %.20g-%.20g\n",(double)
500  cluster->red.left,(double) cluster->red.right,(double)
501  cluster->green.left,(double) cluster->green.right,(double)
502  cluster->blue.left,(double) cluster->blue.right);
503  }
504  /*
505  Print the cluster center values.
506  */
507  (void) FormatLocaleFile(stdout,
508  "\n\n\nCluster Center Values: (Vector Size: %d)\n",MaxDimension);
509  (void) FormatLocaleFile(stdout,"=====================");
510  for (cluster=head; cluster != (Cluster *) NULL; cluster=cluster->next)
511  {
512  (void) FormatLocaleFile(stdout,"\n\nCluster #%.20g\n\n",(double)
513  cluster->id);
514  (void) FormatLocaleFile(stdout,"%g %g %g\n",(double)
515  cluster->red.center,(double) cluster->green.center,(double)
516  cluster->blue.center);
517  }
518  (void) FormatLocaleFile(stdout,"\n");
519  }
520  if (number_clusters > 256)
521  ThrowClassifyException(ImageError,"TooManyClusters",image->filename);
522  /*
523  Speed up distance calculations.
524  */
525  squares=(double *) AcquireQuantumMemory(513UL,sizeof(*squares));
526  if (squares == (double *) NULL)
527  ThrowClassifyException(ResourceLimitError,"MemoryAllocationFailed",
528  image->filename);
529  squares+=255;
530  for (i=(-255); i <= 255; i++)
531  squares[i]=(double) i*(double) i;
532  /*
533  Allocate image colormap.
534  */
535  if (AcquireImageColormap(image,number_clusters,exception) == MagickFalse)
536  ThrowClassifyException(ResourceLimitError,"MemoryAllocationFailed",
537  image->filename);
538  i=0;
539  for (cluster=head; cluster != (Cluster *) NULL; cluster=cluster->next)
540  {
541  image->colormap[i].red=(double) ScaleCharToQuantum((unsigned char)
542  (cluster->red.center+0.5));
543  image->colormap[i].green=(double) ScaleCharToQuantum((unsigned char)
544  (cluster->green.center+0.5));
545  image->colormap[i].blue=(double) ScaleCharToQuantum((unsigned char)
546  (cluster->blue.center+0.5));
547  i++;
548  }
549  /*
550  Do course grain classes.
551  */
552  image_view=AcquireAuthenticCacheView(image,exception);
553 #if defined(MAGICKCORE_OPENMP_SUPPORT)
554  #pragma omp parallel for schedule(static) shared(progress,status) \
555  magick_number_threads(image,image,image->rows,1)
556 #endif
557  for (y=0; y < (ssize_t) image->rows; y++)
558  {
559  Cluster
560  *clust;
561 
562  register const PixelInfo
563  *magick_restrict p;
564 
565  register ssize_t
566  x;
567 
568  register Quantum
569  *magick_restrict q;
570 
571  if (status == MagickFalse)
572  continue;
573  q=GetCacheViewAuthenticPixels(image_view,0,y,image->columns,1,exception);
574  if (q == (Quantum *) NULL)
575  {
576  status=MagickFalse;
577  continue;
578  }
579  for (x=0; x < (ssize_t) image->columns; x++)
580  {
581  SetPixelIndex(image,0,q);
582  for (clust=head; clust != (Cluster *) NULL; clust=clust->next)
583  {
584  if (((ssize_t) ScaleQuantumToChar(GetPixelRed(image,q)) >=
585  (clust->red.left-SafeMargin)) &&
586  ((ssize_t) ScaleQuantumToChar(GetPixelRed(image,q)) <=
587  (clust->red.right+SafeMargin)) &&
588  ((ssize_t) ScaleQuantumToChar(GetPixelGreen(image,q)) >=
589  (clust->green.left-SafeMargin)) &&
590  ((ssize_t) ScaleQuantumToChar(GetPixelGreen(image,q)) <=
591  (clust->green.right+SafeMargin)) &&
592  ((ssize_t) ScaleQuantumToChar(GetPixelBlue(image,q)) >=
593  (clust->blue.left-SafeMargin)) &&
594  ((ssize_t) ScaleQuantumToChar(GetPixelBlue(image,q)) <=
595  (clust->blue.right+SafeMargin)))
596  {
597  /*
598  Classify this pixel.
599  */
600  SetPixelIndex(image,(Quantum) clust->id,q);
601  break;
602  }
603  }
604  if (clust == (Cluster *) NULL)
605  {
606  double
607  distance_squared,
608  local_minima,
609  numerator,
610  ratio,
611  sum;
612 
613  register ssize_t
614  j,
615  k;
616 
617  /*
618  Compute fuzzy membership.
619  */
620  local_minima=0.0;
621  for (j=0; j < (ssize_t) image->colors; j++)
622  {
623  sum=0.0;
624  p=image->colormap+j;
625  distance_squared=squares[(ssize_t) ScaleQuantumToChar(
626  GetPixelRed(image,q))-(ssize_t)
627  ScaleQuantumToChar(ClampToQuantum(p->red))]+squares[(ssize_t)
628  ScaleQuantumToChar(GetPixelGreen(image,q))-(ssize_t)
629  ScaleQuantumToChar(ClampToQuantum(p->green))]+squares[(ssize_t)
630  ScaleQuantumToChar(GetPixelBlue(image,q))-(ssize_t)
631  ScaleQuantumToChar(ClampToQuantum(p->blue))];
632  numerator=distance_squared;
633  for (k=0; k < (ssize_t) image->colors; k++)
634  {
635  p=image->colormap+k;
636  distance_squared=squares[(ssize_t) ScaleQuantumToChar(
637  GetPixelRed(image,q))-(ssize_t)
638  ScaleQuantumToChar(ClampToQuantum(p->red))]+squares[
639  (ssize_t) ScaleQuantumToChar(GetPixelGreen(image,q))-(ssize_t)
640  ScaleQuantumToChar(ClampToQuantum(p->green))]+squares[
641  (ssize_t) ScaleQuantumToChar(GetPixelBlue(image,q))-(ssize_t)
642  ScaleQuantumToChar(ClampToQuantum(p->blue))];
643  ratio=numerator/distance_squared;
644  sum+=SegmentPower(ratio);
645  }
646  if ((sum != 0.0) && ((1.0/sum) > local_minima))
647  {
648  /*
649  Classify this pixel.
650  */
651  local_minima=1.0/sum;
652  SetPixelIndex(image,(Quantum) j,q);
653  }
654  }
655  }
656  q+=GetPixelChannels(image);
657  }
658  if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
659  status=MagickFalse;
660  if (image->progress_monitor != (MagickProgressMonitor) NULL)
661  {
663  proceed;
664 
665 #if defined(MAGICKCORE_OPENMP_SUPPORT)
666  #pragma omp atomic
667 #endif
668  progress++;
669  proceed=SetImageProgress(image,SegmentImageTag,progress,2*image->rows);
670  if (proceed == MagickFalse)
671  status=MagickFalse;
672  }
673  }
674  image_view=DestroyCacheView(image_view);
675  status&=SyncImage(image,exception);
676  /*
677  Relinquish resources.
678  */
679  for (cluster=head; cluster != (Cluster *) NULL; cluster=next_cluster)
680  {
681  next_cluster=cluster->next;
682  cluster=(Cluster *) RelinquishMagickMemory(cluster);
683  }
684  squares-=255;
685  free_squares=squares;
686  free_squares=(double *) RelinquishMagickMemory(free_squares);
687  return(MagickTrue);
688 }
689 
690 /*
691 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
692 % %
693 % %
694 % %
695 + C o n s o l i d a t e C r o s s i n g s %
696 % %
697 % %
698 % %
699 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
700 %
701 % ConsolidateCrossings() guarantees that an even number of zero crossings
702 % always lie between two crossings.
703 %
704 % The format of the ConsolidateCrossings method is:
705 %
706 % ConsolidateCrossings(ZeroCrossing *zero_crossing,
707 % const size_t number_crossings)
708 %
709 % A description of each parameter follows.
710 %
711 % o zero_crossing: Specifies an array of structures of type ZeroCrossing.
712 %
713 % o number_crossings: This size_t specifies the number of elements
714 % in the zero_crossing array.
715 %
716 */
717 static void ConsolidateCrossings(ZeroCrossing *zero_crossing,
718  const size_t number_crossings)
719 {
720  register ssize_t
721  i,
722  j,
723  k,
724  l;
725 
726  ssize_t
727  center,
728  correct,
729  count,
730  left,
731  right;
732 
733  /*
734  Consolidate zero crossings.
735  */
736  for (i=(ssize_t) number_crossings-1; i >= 0; i--)
737  for (j=0; j <= 255; j++)
738  {
739  if (zero_crossing[i].crossings[j] == 0)
740  continue;
741  /*
742  Find the entry that is closest to j and still preserves the
743  property that there are an even number of crossings between
744  intervals.
745  */
746  for (k=j-1; k > 0; k--)
747  if (zero_crossing[i+1].crossings[k] != 0)
748  break;
749  left=MagickMax(k,0);
750  center=j;
751  for (k=j+1; k < 255; k++)
752  if (zero_crossing[i+1].crossings[k] != 0)
753  break;
754  right=MagickMin(k,255);
755  /*
756  K is the zero crossing just left of j.
757  */
758  for (k=j-1; k > 0; k--)
759  if (zero_crossing[i].crossings[k] != 0)
760  break;
761  if (k < 0)
762  k=0;
763  /*
764  Check center for an even number of crossings between k and j.
765  */
766  correct=(-1);
767  if (zero_crossing[i+1].crossings[j] != 0)
768  {
769  count=0;
770  for (l=k+1; l < center; l++)
771  if (zero_crossing[i+1].crossings[l] != 0)
772  count++;
773  if (((count % 2) == 0) && (center != k))
774  correct=center;
775  }
776  /*
777  Check left for an even number of crossings between k and j.
778  */
779  if (correct == -1)
780  {
781  count=0;
782  for (l=k+1; l < left; l++)
783  if (zero_crossing[i+1].crossings[l] != 0)
784  count++;
785  if (((count % 2) == 0) && (left != k))
786  correct=left;
787  }
788  /*
789  Check right for an even number of crossings between k and j.
790  */
791  if (correct == -1)
792  {
793  count=0;
794  for (l=k+1; l < right; l++)
795  if (zero_crossing[i+1].crossings[l] != 0)
796  count++;
797  if (((count % 2) == 0) && (right != k))
798  correct=right;
799  }
800  l=(ssize_t) zero_crossing[i].crossings[j];
801  zero_crossing[i].crossings[j]=0;
802  if (correct != -1)
803  zero_crossing[i].crossings[correct]=(short) l;
804  }
805 }
806 
807 /*
808 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
809 % %
810 % %
811 % %
812 + D e f i n e R e g i o n %
813 % %
814 % %
815 % %
816 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
817 %
818 % DefineRegion() defines the left and right boundaries of a peak region.
819 %
820 % The format of the DefineRegion method is:
821 %
822 % ssize_t DefineRegion(const short *extrema,ExtentPacket *extents)
823 %
824 % A description of each parameter follows.
825 %
826 % o extrema: Specifies a pointer to an array of integers. They
827 % represent the peaks and valleys of the histogram for each color
828 % component.
829 %
830 % o extents: This pointer to an ExtentPacket represent the extends
831 % of a particular peak or valley of a color component.
832 %
833 */
834 static ssize_t DefineRegion(const short *extrema,ExtentPacket *extents)
835 {
836  /*
837  Initialize to default values.
838  */
839  extents->left=0;
840  extents->center=0.0;
841  extents->right=255;
842  /*
843  Find the left side (maxima).
844  */
845  for ( ; extents->index <= 255; extents->index++)
846  if (extrema[extents->index] > 0)
847  break;
848  if (extents->index > 255)
849  return(MagickFalse); /* no left side - no region exists */
850  extents->left=extents->index;
851  /*
852  Find the right side (minima).
853  */
854  for ( ; extents->index <= 255; extents->index++)
855  if (extrema[extents->index] < 0)
856  break;
857  extents->right=extents->index-1;
858  return(MagickTrue);
859 }
860 
861 /*
862 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
863 % %
864 % %
865 % %
866 + D e r i v a t i v e H i s t o g r a m %
867 % %
868 % %
869 % %
870 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
871 %
872 % DerivativeHistogram() determines the derivative of the histogram using
873 % central differencing.
874 %
875 % The format of the DerivativeHistogram method is:
876 %
877 % DerivativeHistogram(const double *histogram,
878 % double *derivative)
879 %
880 % A description of each parameter follows.
881 %
882 % o histogram: Specifies an array of doubles representing the number
883 % of pixels for each intensity of a particular color component.
884 %
885 % o derivative: This array of doubles is initialized by
886 % DerivativeHistogram to the derivative of the histogram using central
887 % differencing.
888 %
889 */
890 static void DerivativeHistogram(const double *histogram,
891  double *derivative)
892 {
893  register ssize_t
894  i,
895  n;
896 
897  /*
898  Compute endpoints using second order polynomial interpolation.
899  */
900  n=255;
901  derivative[0]=(-1.5*histogram[0]+2.0*histogram[1]-0.5*histogram[2]);
902  derivative[n]=(0.5*histogram[n-2]-2.0*histogram[n-1]+1.5*histogram[n]);
903  /*
904  Compute derivative using central differencing.
905  */
906  for (i=1; i < n; i++)
907  derivative[i]=(histogram[i+1]-histogram[i-1])/2.0;
908  return;
909 }
910 
911 /*
912 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
913 % %
914 % %
915 % %
916 + G e t I m a g e D y n a m i c T h r e s h o l d %
917 % %
918 % %
919 % %
920 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
921 %
922 % GetImageDynamicThreshold() returns the dynamic threshold for an image.
923 %
924 % The format of the GetImageDynamicThreshold method is:
925 %
926 % MagickBooleanType GetImageDynamicThreshold(const Image *image,
927 % const double cluster_threshold,const double smooth_threshold,
928 % PixelInfo *pixel,ExceptionInfo *exception)
929 %
930 % A description of each parameter follows.
931 %
932 % o image: the image.
933 %
934 % o cluster_threshold: This double represents the minimum number of
935 % pixels contained in a hexahedra before it can be considered valid
936 % (expressed as a percentage).
937 %
938 % o smooth_threshold: the smoothing threshold eliminates noise in the second
939 % derivative of the histogram. As the value is increased, you can expect a
940 % smoother second derivative.
941 %
942 % o pixel: return the dynamic threshold here.
943 %
944 % o exception: return any errors or warnings in this structure.
945 %
946 */
948  const double cluster_threshold,const double smooth_threshold,
949  PixelInfo *pixel,ExceptionInfo *exception)
950 {
951  Cluster
952  *background,
953  *cluster,
954  *object,
955  *head,
956  *last_cluster,
957  *next_cluster;
958 
960  blue,
961  green,
962  red;
963 
965  proceed;
966 
967  double
968  threshold;
969 
970  register const Quantum
971  *p;
972 
973  register ssize_t
974  i,
975  x;
976 
977  short
978  *extrema[MaxDimension];
979 
980  ssize_t
981  count,
982  *histogram[MaxDimension],
983  y;
984 
985  /*
986  Allocate histogram and extrema.
987  */
988  assert(image != (Image *) NULL);
989  assert(image->signature == MagickCoreSignature);
990  if (image->debug != MagickFalse)
991  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
992  GetPixelInfo(image,pixel);
993  for (i=0; i < MaxDimension; i++)
994  {
995  histogram[i]=(ssize_t *) AcquireQuantumMemory(256UL,sizeof(**histogram));
996  extrema[i]=(short *) AcquireQuantumMemory(256UL,sizeof(**histogram));
997  if ((histogram[i] == (ssize_t *) NULL) || (extrema[i] == (short *) NULL))
998  {
999  for (i-- ; i >= 0; i--)
1000  {
1001  extrema[i]=(short *) RelinquishMagickMemory(extrema[i]);
1002  histogram[i]=(ssize_t *) RelinquishMagickMemory(histogram[i]);
1003  }
1004  (void) ThrowMagickException(exception,GetMagickModule(),
1005  ResourceLimitError,"MemoryAllocationFailed","`%s'",image->filename);
1006  return(MagickFalse);
1007  }
1008  }
1009  /*
1010  Initialize histogram.
1011  */
1012  InitializeHistogram(image,histogram,exception);
1013  (void) OptimalTau(histogram[Red],Tau,0.2f,DeltaTau,
1014  (smooth_threshold == 0.0f ? 1.0f : smooth_threshold),extrema[Red]);
1015  (void) OptimalTau(histogram[Green],Tau,0.2f,DeltaTau,
1016  (smooth_threshold == 0.0f ? 1.0f : smooth_threshold),extrema[Green]);
1017  (void) OptimalTau(histogram[Blue],Tau,0.2f,DeltaTau,
1018  (smooth_threshold == 0.0f ? 1.0f : smooth_threshold),extrema[Blue]);
1019  /*
1020  Form clusters.
1021  */
1022  cluster=(Cluster *) NULL;
1023  head=(Cluster *) NULL;
1024  (void) memset(&red,0,sizeof(red));
1025  (void) memset(&green,0,sizeof(green));
1026  (void) memset(&blue,0,sizeof(blue));
1027  while (DefineRegion(extrema[Red],&red) != 0)
1028  {
1029  green.index=0;
1030  while (DefineRegion(extrema[Green],&green) != 0)
1031  {
1032  blue.index=0;
1033  while (DefineRegion(extrema[Blue],&blue) != 0)
1034  {
1035  /*
1036  Allocate a new class.
1037  */
1038  if (head != (Cluster *) NULL)
1039  {
1040  cluster->next=(Cluster *) AcquireMagickMemory(
1041  sizeof(*cluster->next));
1042  cluster=cluster->next;
1043  }
1044  else
1045  {
1046  cluster=(Cluster *) AcquireMagickMemory(sizeof(*cluster));
1047  head=cluster;
1048  }
1049  if (cluster == (Cluster *) NULL)
1050  {
1051  (void) ThrowMagickException(exception,GetMagickModule(),
1052  ResourceLimitError,"MemoryAllocationFailed","`%s'",
1053  image->filename);
1054  return(MagickFalse);
1055  }
1056  /*
1057  Initialize a new class.
1058  */
1059  cluster->count=0;
1060  cluster->red=red;
1061  cluster->green=green;
1062  cluster->blue=blue;
1063  cluster->next=(Cluster *) NULL;
1064  }
1065  }
1066  }
1067  if (head == (Cluster *) NULL)
1068  {
1069  /*
1070  No classes were identified-- create one.
1071  */
1072  cluster=(Cluster *) AcquireMagickMemory(sizeof(*cluster));
1073  if (cluster == (Cluster *) NULL)
1074  {
1075  (void) ThrowMagickException(exception,GetMagickModule(),
1076  ResourceLimitError,"MemoryAllocationFailed","`%s'",image->filename);
1077  return(MagickFalse);
1078  }
1079  /*
1080  Initialize a new class.
1081  */
1082  cluster->count=0;
1083  cluster->red=red;
1084  cluster->green=green;
1085  cluster->blue=blue;
1086  cluster->next=(Cluster *) NULL;
1087  head=cluster;
1088  }
1089  /*
1090  Count the pixels for each cluster.
1091  */
1092  count=0;
1093  for (y=0; y < (ssize_t) image->rows; y++)
1094  {
1095  p=GetVirtualPixels(image,0,y,image->columns,1,exception);
1096  if (p == (const Quantum *) NULL)
1097  break;
1098  for (x=0; x < (ssize_t) image->columns; x++)
1099  {
1100  for (cluster=head; cluster != (Cluster *) NULL; cluster=cluster->next)
1101  if (((ssize_t) ScaleQuantumToChar(GetPixelRed(image,p)) >=
1102  (cluster->red.left-SafeMargin)) &&
1103  ((ssize_t) ScaleQuantumToChar(GetPixelRed(image,p)) <=
1104  (cluster->red.right+SafeMargin)) &&
1105  ((ssize_t) ScaleQuantumToChar(GetPixelGreen(image,p)) >=
1106  (cluster->green.left-SafeMargin)) &&
1107  ((ssize_t) ScaleQuantumToChar(GetPixelGreen(image,p)) <=
1108  (cluster->green.right+SafeMargin)) &&
1109  ((ssize_t) ScaleQuantumToChar(GetPixelBlue(image,p)) >=
1110  (cluster->blue.left-SafeMargin)) &&
1111  ((ssize_t) ScaleQuantumToChar(GetPixelBlue(image,p)) <=
1112  (cluster->blue.right+SafeMargin)))
1113  {
1114  /*
1115  Count this pixel.
1116  */
1117  count++;
1118  cluster->red.center+=(double) ScaleQuantumToChar(
1119  GetPixelRed(image,p));
1120  cluster->green.center+=(double) ScaleQuantumToChar(
1121  GetPixelGreen(image,p));
1122  cluster->blue.center+=(double) ScaleQuantumToChar(
1123  GetPixelBlue(image,p));
1124  cluster->count++;
1125  break;
1126  }
1127  p+=GetPixelChannels(image);
1128  }
1130  2*image->rows);
1131  if (proceed == MagickFalse)
1132  break;
1133  }
1134  /*
1135  Remove clusters that do not meet minimum cluster threshold.
1136  */
1137  count=0;
1138  last_cluster=head;
1139  next_cluster=head;
1140  for (cluster=head; cluster != (Cluster *) NULL; cluster=next_cluster)
1141  {
1142  next_cluster=cluster->next;
1143  if ((cluster->count > 0) &&
1144  (cluster->count >= (count*cluster_threshold/100.0)))
1145  {
1146  /*
1147  Initialize cluster.
1148  */
1149  cluster->id=count;
1150  cluster->red.center/=cluster->count;
1151  cluster->green.center/=cluster->count;
1152  cluster->blue.center/=cluster->count;
1153  count++;
1154  last_cluster=cluster;
1155  continue;
1156  }
1157  /*
1158  Delete cluster.
1159  */
1160  if (cluster == head)
1161  head=next_cluster;
1162  else
1163  last_cluster->next=next_cluster;
1164  cluster=(Cluster *) RelinquishMagickMemory(cluster);
1165  }
1166  object=head;
1167  background=head;
1168  if (count > 1)
1169  {
1170  object=head->next;
1171  for (cluster=object; cluster->next != (Cluster *) NULL; )
1172  {
1173  if (cluster->count < object->count)
1174  object=cluster;
1175  cluster=cluster->next;
1176  }
1177  background=head->next;
1178  for (cluster=background; cluster->next != (Cluster *) NULL; )
1179  {
1180  if (cluster->count > background->count)
1181  background=cluster;
1182  cluster=cluster->next;
1183  }
1184  }
1185  if (background != (Cluster *) NULL)
1186  {
1187  threshold=(background->red.center+object->red.center)/2.0;
1188  pixel->red=(double) ScaleCharToQuantum((unsigned char)
1189  (threshold+0.5));
1190  threshold=(background->green.center+object->green.center)/2.0;
1191  pixel->green=(double) ScaleCharToQuantum((unsigned char)
1192  (threshold+0.5));
1193  threshold=(background->blue.center+object->blue.center)/2.0;
1194  pixel->blue=(double) ScaleCharToQuantum((unsigned char)
1195  (threshold+0.5));
1196  }
1197  /*
1198  Relinquish resources.
1199  */
1200  for (cluster=head; cluster != (Cluster *) NULL; cluster=next_cluster)
1201  {
1202  next_cluster=cluster->next;
1203  cluster=(Cluster *) RelinquishMagickMemory(cluster);
1204  }
1205  for (i=0; i < MaxDimension; i++)
1206  {
1207  extrema[i]=(short *) RelinquishMagickMemory(extrema[i]);
1208  histogram[i]=(ssize_t *) RelinquishMagickMemory(histogram[i]);
1209  }
1210  return(MagickTrue);
1211 }
1212 
1213 /*
1214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1215 % %
1216 % %
1217 % %
1218 + I n i t i a l i z e H i s t o g r a m %
1219 % %
1220 % %
1221 % %
1222 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1223 %
1224 % InitializeHistogram() computes the histogram for an image.
1225 %
1226 % The format of the InitializeHistogram method is:
1227 %
1228 % InitializeHistogram(const Image *image,ssize_t **histogram)
1229 %
1230 % A description of each parameter follows.
1231 %
1232 % o image: Specifies a pointer to an Image structure; returned from
1233 % ReadImage.
1234 %
1235 % o histogram: Specifies an array of integers representing the number
1236 % of pixels for each intensity of a particular color component.
1237 %
1238 */
1239 static void InitializeHistogram(const Image *image,ssize_t **histogram,
1240  ExceptionInfo *exception)
1241 {
1242  register const Quantum
1243  *p;
1244 
1245  register ssize_t
1246  i,
1247  x;
1248 
1249  ssize_t
1250  y;
1251 
1252  /*
1253  Initialize histogram.
1254  */
1255  for (i=0; i <= 255; i++)
1256  {
1257  histogram[Red][i]=0;
1258  histogram[Green][i]=0;
1259  histogram[Blue][i]=0;
1260  }
1261  for (y=0; y < (ssize_t) image->rows; y++)
1262  {
1263  p=GetVirtualPixels(image,0,y,image->columns,1,exception);
1264  if (p == (const Quantum *) NULL)
1265  break;
1266  for (x=0; x < (ssize_t) image->columns; x++)
1267  {
1268  histogram[Red][(ssize_t) ScaleQuantumToChar(GetPixelRed(image,p))]++;
1269  histogram[Green][(ssize_t) ScaleQuantumToChar(GetPixelGreen(image,p))]++;
1270  histogram[Blue][(ssize_t) ScaleQuantumToChar(GetPixelBlue(image,p))]++;
1271  p+=GetPixelChannels(image);
1272  }
1273  }
1274 }
1275 
1276 /*
1277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1278 % %
1279 % %
1280 % %
1281 + I n i t i a l i z e I n t e r v a l T r e e %
1282 % %
1283 % %
1284 % %
1285 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1286 %
1287 % InitializeIntervalTree() initializes an interval tree from the lists of
1288 % zero crossings.
1289 %
1290 % The format of the InitializeIntervalTree method is:
1291 %
1292 % InitializeIntervalTree(IntervalTree **list,ssize_t *number_nodes,
1293 % IntervalTree *node)
1294 %
1295 % A description of each parameter follows.
1296 %
1297 % o zero_crossing: Specifies an array of structures of type ZeroCrossing.
1298 %
1299 % o number_crossings: This size_t specifies the number of elements
1300 % in the zero_crossing array.
1301 %
1302 */
1303 
1304 static void InitializeList(IntervalTree **list,ssize_t *number_nodes,
1305  IntervalTree *node)
1306 {
1307  if (node == (IntervalTree *) NULL)
1308  return;
1309  if (node->child == (IntervalTree *) NULL)
1310  list[(*number_nodes)++]=node;
1311  InitializeList(list,number_nodes,node->sibling);
1312  InitializeList(list,number_nodes,node->child);
1313 }
1314 
1315 static void MeanStability(IntervalTree *node)
1316 {
1317  register IntervalTree
1318  *child;
1319 
1320  if (node == (IntervalTree *) NULL)
1321  return;
1322  node->mean_stability=0.0;
1323  child=node->child;
1324  if (child != (IntervalTree *) NULL)
1325  {
1326  register ssize_t
1327  count;
1328 
1329  register double
1330  sum;
1331 
1332  sum=0.0;
1333  count=0;
1334  for ( ; child != (IntervalTree *) NULL; child=child->sibling)
1335  {
1336  sum+=child->stability;
1337  count++;
1338  }
1339  node->mean_stability=sum/(double) count;
1340  }
1341  MeanStability(node->sibling);
1342  MeanStability(node->child);
1343 }
1344 
1345 static void Stability(IntervalTree *node)
1346 {
1347  if (node == (IntervalTree *) NULL)
1348  return;
1349  if (node->child == (IntervalTree *) NULL)
1350  node->stability=0.0;
1351  else
1352  node->stability=node->tau-(node->child)->tau;
1353  Stability(node->sibling);
1354  Stability(node->child);
1355 }
1356 
1357 static IntervalTree *InitializeIntervalTree(const ZeroCrossing *zero_crossing,
1358  const size_t number_crossings)
1359 {
1360  IntervalTree
1361  *head,
1362  **list,
1363  *node,
1364  *root;
1365 
1366  register ssize_t
1367  i;
1368 
1369  ssize_t
1370  j,
1371  k,
1372  left,
1373  number_nodes;
1374 
1375  /*
1376  Allocate interval tree.
1377  */
1378  list=(IntervalTree **) AcquireQuantumMemory((size_t) TreeLength,
1379  sizeof(*list));
1380  if (list == (IntervalTree **) NULL)
1381  return((IntervalTree *) NULL);
1382  /*
1383  The root is the entire histogram.
1384  */
1385  root=(IntervalTree *) AcquireCriticalMemory(sizeof(*root));
1386  root->child=(IntervalTree *) NULL;
1387  root->sibling=(IntervalTree *) NULL;
1388  root->tau=0.0;
1389  root->left=0;
1390  root->right=255;
1391  root->mean_stability=0.0;
1392  root->stability=0.0;
1393  (void) memset(list,0,TreeLength*sizeof(*list));
1394  for (i=(-1); i < (ssize_t) number_crossings; i++)
1395  {
1396  /*
1397  Initialize list with all nodes with no children.
1398  */
1399  number_nodes=0;
1400  InitializeList(list,&number_nodes,root);
1401  /*
1402  Split list.
1403  */
1404  for (j=0; j < number_nodes; j++)
1405  {
1406  head=list[j];
1407  left=head->left;
1408  node=head;
1409  for (k=head->left+1; k < head->right; k++)
1410  {
1411  if (zero_crossing[i+1].crossings[k] != 0)
1412  {
1413  if (node == head)
1414  {
1416  sizeof(*node->child));
1417  node=node->child;
1418  }
1419  else
1420  {
1422  sizeof(*node->sibling));
1423  node=node->sibling;
1424  }
1425  if (node == (IntervalTree *) NULL)
1426  {
1427  list=(IntervalTree **) RelinquishMagickMemory(list);
1428  FreeNodes(root);
1429  return((IntervalTree *) NULL);
1430  }
1431  node->tau=zero_crossing[i+1].tau;
1432  node->child=(IntervalTree *) NULL;
1433  node->sibling=(IntervalTree *) NULL;
1434  node->left=left;
1435  node->right=k;
1436  left=k;
1437  }
1438  }
1439  if (left != head->left)
1440  {
1442  sizeof(*node->sibling));
1443  node=node->sibling;
1444  if (node == (IntervalTree *) NULL)
1445  {
1446  list=(IntervalTree **) RelinquishMagickMemory(list);
1447  FreeNodes(root);
1448  return((IntervalTree *) NULL);
1449  }
1450  node->tau=zero_crossing[i+1].tau;
1451  node->child=(IntervalTree *) NULL;
1452  node->sibling=(IntervalTree *) NULL;
1453  node->left=left;
1454  node->right=head->right;
1455  }
1456  }
1457  }
1458  /*
1459  Determine the stability: difference between a nodes tau and its child.
1460  */
1461  Stability(root->child);
1462  MeanStability(root->child);
1463  list=(IntervalTree **) RelinquishMagickMemory(list);
1464  return(root);
1465 }
1466 
1467 /*
1468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1469 % %
1470 % %
1471 % %
1472 + O p t i m a l T a u %
1473 % %
1474 % %
1475 % %
1476 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1477 %
1478 % OptimalTau() finds the optimal tau for each band of the histogram.
1479 %
1480 % The format of the OptimalTau method is:
1481 %
1482 % double OptimalTau(const ssize_t *histogram,const double max_tau,
1483 % const double min_tau,const double delta_tau,
1484 % const double smooth_threshold,short *extrema)
1485 %
1486 % A description of each parameter follows.
1487 %
1488 % o histogram: Specifies an array of integers representing the number
1489 % of pixels for each intensity of a particular color component.
1490 %
1491 % o extrema: Specifies a pointer to an array of integers. They
1492 % represent the peaks and valleys of the histogram for each color
1493 % component.
1494 %
1495 */
1496 
1497 static void ActiveNodes(IntervalTree **list,ssize_t *number_nodes,
1498  IntervalTree *node)
1499 {
1500  if (node == (IntervalTree *) NULL)
1501  return;
1502  if (node->stability >= node->mean_stability)
1503  {
1504  list[(*number_nodes)++]=node;
1505  ActiveNodes(list,number_nodes,node->sibling);
1506  }
1507  else
1508  {
1509  ActiveNodes(list,number_nodes,node->sibling);
1510  ActiveNodes(list,number_nodes,node->child);
1511  }
1512 }
1513 
1514 static void FreeNodes(IntervalTree *node)
1515 {
1516  if (node == (IntervalTree *) NULL)
1517  return;
1518  FreeNodes(node->sibling);
1519  FreeNodes(node->child);
1520  node=(IntervalTree *) RelinquishMagickMemory(node);
1521 }
1522 
1523 static double OptimalTau(const ssize_t *histogram,const double max_tau,
1524  const double min_tau,const double delta_tau,const double smooth_threshold,
1525  short *extrema)
1526 {
1527  IntervalTree
1528  **list,
1529  *node,
1530  *root;
1531 
1533  peak;
1534 
1535  double
1536  average_tau,
1537  *derivative,
1538  *second_derivative,
1539  tau,
1540  value;
1541 
1542  register ssize_t
1543  i,
1544  x;
1545 
1546  size_t
1547  count,
1548  number_crossings;
1549 
1550  ssize_t
1551  index,
1552  j,
1553  k,
1554  number_nodes;
1555 
1556  ZeroCrossing
1557  *zero_crossing;
1558 
1559  /*
1560  Allocate interval tree.
1561  */
1562  list=(IntervalTree **) AcquireQuantumMemory((size_t) TreeLength,
1563  sizeof(*list));
1564  if (list == (IntervalTree **) NULL)
1565  return(0.0);
1566  /*
1567  Allocate zero crossing list.
1568  */
1569  count=(size_t) ((max_tau-min_tau)/delta_tau)+2;
1570  zero_crossing=(ZeroCrossing *) AcquireQuantumMemory((size_t) count,
1571  sizeof(*zero_crossing));
1572  if (zero_crossing == (ZeroCrossing *) NULL)
1573  {
1574  list=(IntervalTree **) RelinquishMagickMemory(list);
1575  return(0.0);
1576  }
1577  for (i=0; i < (ssize_t) count; i++)
1578  zero_crossing[i].tau=(-1.0);
1579  /*
1580  Initialize zero crossing list.
1581  */
1582  derivative=(double *) AcquireCriticalMemory(256*sizeof(*derivative));
1583  second_derivative=(double *) AcquireCriticalMemory(256*
1584  sizeof(*second_derivative));
1585  i=0;
1586  for (tau=max_tau; tau >= min_tau; tau-=delta_tau)
1587  {
1588  zero_crossing[i].tau=tau;
1589  ScaleSpace(histogram,tau,zero_crossing[i].histogram);
1590  DerivativeHistogram(zero_crossing[i].histogram,derivative);
1591  DerivativeHistogram(derivative,second_derivative);
1592  ZeroCrossHistogram(second_derivative,smooth_threshold,
1593  zero_crossing[i].crossings);
1594  i++;
1595  }
1596  /*
1597  Add an entry for the original histogram.
1598  */
1599  zero_crossing[i].tau=0.0;
1600  for (j=0; j <= 255; j++)
1601  zero_crossing[i].histogram[j]=(double) histogram[j];
1602  DerivativeHistogram(zero_crossing[i].histogram,derivative);
1603  DerivativeHistogram(derivative,second_derivative);
1604  ZeroCrossHistogram(second_derivative,smooth_threshold,
1605  zero_crossing[i].crossings);
1606  number_crossings=(size_t) i;
1607  derivative=(double *) RelinquishMagickMemory(derivative);
1608  second_derivative=(double *) RelinquishMagickMemory(second_derivative);
1609  /*
1610  Ensure the scale-space fingerprints form lines in scale-space, not loops.
1611  */
1612  ConsolidateCrossings(zero_crossing,number_crossings);
1613  /*
1614  Force endpoints to be included in the interval.
1615  */
1616  for (i=0; i <= (ssize_t) number_crossings; i++)
1617  {
1618  for (j=0; j < 255; j++)
1619  if (zero_crossing[i].crossings[j] != 0)
1620  break;
1621  zero_crossing[i].crossings[0]=(-zero_crossing[i].crossings[j]);
1622  for (j=255; j > 0; j--)
1623  if (zero_crossing[i].crossings[j] != 0)
1624  break;
1625  zero_crossing[i].crossings[255]=(-zero_crossing[i].crossings[j]);
1626  }
1627  /*
1628  Initialize interval tree.
1629  */
1630  root=InitializeIntervalTree(zero_crossing,number_crossings);
1631  if (root == (IntervalTree *) NULL)
1632  {
1633  zero_crossing=(ZeroCrossing *) RelinquishMagickMemory(zero_crossing);
1634  list=(IntervalTree **) RelinquishMagickMemory(list);
1635  return(0.0);
1636  }
1637  /*
1638  Find active nodes: stability is greater (or equal) to the mean stability of
1639  its children.
1640  */
1641  number_nodes=0;
1642  ActiveNodes(list,&number_nodes,root->child);
1643  /*
1644  Initialize extrema.
1645  */
1646  for (i=0; i <= 255; i++)
1647  extrema[i]=0;
1648  for (i=0; i < number_nodes; i++)
1649  {
1650  /*
1651  Find this tau in zero crossings list.
1652  */
1653  k=0;
1654  node=list[i];
1655  for (j=0; j <= (ssize_t) number_crossings; j++)
1656  if (zero_crossing[j].tau == node->tau)
1657  k=j;
1658  /*
1659  Find the value of the peak.
1660  */
1661  peak=zero_crossing[k].crossings[node->right] == -1 ? MagickTrue :
1662  MagickFalse;
1663  index=node->left;
1664  value=zero_crossing[k].histogram[index];
1665  for (x=node->left; x <= node->right; x++)
1666  {
1667  if (peak != MagickFalse)
1668  {
1669  if (zero_crossing[k].histogram[x] > value)
1670  {
1671  value=zero_crossing[k].histogram[x];
1672  index=x;
1673  }
1674  }
1675  else
1676  if (zero_crossing[k].histogram[x] < value)
1677  {
1678  value=zero_crossing[k].histogram[x];
1679  index=x;
1680  }
1681  }
1682  for (x=node->left; x <= node->right; x++)
1683  {
1684  if (index == 0)
1685  index=256;
1686  if (peak != MagickFalse)
1687  extrema[x]=(short) index;
1688  else
1689  extrema[x]=(short) (-index);
1690  }
1691  }
1692  /*
1693  Determine the average tau.
1694  */
1695  average_tau=0.0;
1696  for (i=0; i < number_nodes; i++)
1697  average_tau+=list[i]->tau;
1698  average_tau/=(double) number_nodes;
1699  /*
1700  Relinquish resources.
1701  */
1702  FreeNodes(root);
1703  zero_crossing=(ZeroCrossing *) RelinquishMagickMemory(zero_crossing);
1704  list=(IntervalTree **) RelinquishMagickMemory(list);
1705  return(average_tau);
1706 }
1707 
1708 /*
1709 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1710 % %
1711 % %
1712 % %
1713 + S c a l e S p a c e %
1714 % %
1715 % %
1716 % %
1717 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1718 %
1719 % ScaleSpace() performs a scale-space filter on the 1D histogram.
1720 %
1721 % The format of the ScaleSpace method is:
1722 %
1723 % ScaleSpace(const ssize_t *histogram,const double tau,
1724 % double *scale_histogram)
1725 %
1726 % A description of each parameter follows.
1727 %
1728 % o histogram: Specifies an array of doubles representing the number
1729 % of pixels for each intensity of a particular color component.
1730 %
1731 */
1732 
1733 static void ScaleSpace(const ssize_t *histogram,const double tau,
1734  double *scale_histogram)
1735 {
1736  double
1737  alpha,
1738  beta,
1739  *gamma,
1740  sum;
1741 
1742  register ssize_t
1743  u,
1744  x;
1745 
1746  gamma=(double *) AcquireQuantumMemory(256,sizeof(*gamma));
1747  if (gamma == (double *) NULL)
1749  "UnableToAllocateGammaMap");
1750  alpha=PerceptibleReciprocal(tau*sqrt(2.0*MagickPI));
1751  beta=(-1.0*PerceptibleReciprocal(2.0*tau*tau));
1752  for (x=0; x <= 255; x++)
1753  gamma[x]=0.0;
1754  for (x=0; x <= 255; x++)
1755  {
1756  gamma[x]=exp((double) beta*x*x);
1757  if (gamma[x] < MagickEpsilon)
1758  break;
1759  }
1760  for (x=0; x <= 255; x++)
1761  {
1762  sum=0.0;
1763  for (u=0; u <= 255; u++)
1764  sum+=(double) histogram[u]*gamma[MagickAbsoluteValue(x-u)];
1765  scale_histogram[x]=alpha*sum;
1766  }
1767  gamma=(double *) RelinquishMagickMemory(gamma);
1768 }
1769 
1770 /*
1771 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1772 % %
1773 % %
1774 % %
1775 % S e g m e n t I m a g e %
1776 % %
1777 % %
1778 % %
1779 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1780 %
1781 % SegmentImage() segment an image by analyzing the histograms of the color
1782 % components and identifying units that are homogeneous with the fuzzy
1783 % C-means technique.
1784 %
1785 % The format of the SegmentImage method is:
1786 %
1787 % MagickBooleanType SegmentImage(Image *image,
1788 % const ColorspaceType colorspace,const MagickBooleanType verbose,
1789 % const double cluster_threshold,const double smooth_threshold,
1790 % ExceptionInfo *exception)
1791 %
1792 % A description of each parameter follows.
1793 %
1794 % o image: the image.
1795 %
1796 % o colorspace: Indicate the colorspace.
1797 %
1798 % o verbose: Set to MagickTrue to print detailed information about the
1799 % identified classes.
1800 %
1801 % o cluster_threshold: This represents the minimum number of pixels
1802 % contained in a hexahedra before it can be considered valid (expressed
1803 % as a percentage).
1804 %
1805 % o smooth_threshold: the smoothing threshold eliminates noise in the second
1806 % derivative of the histogram. As the value is increased, you can expect a
1807 % smoother second derivative.
1808 %
1809 % o exception: return any errors or warnings in this structure.
1810 %
1811 */
1813  const ColorspaceType colorspace,const MagickBooleanType verbose,
1814  const double cluster_threshold,const double smooth_threshold,
1815  ExceptionInfo *exception)
1816 {
1818  previous_colorspace;
1819 
1821  status;
1822 
1823  register ssize_t
1824  i;
1825 
1826  short
1827  *extrema[MaxDimension];
1828 
1829  ssize_t
1830  *histogram[MaxDimension];
1831 
1832  /*
1833  Allocate histogram and extrema.
1834  */
1835  assert(image != (Image *) NULL);
1836  assert(image->signature == MagickCoreSignature);
1837  if (image->debug != MagickFalse)
1838  (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1839  for (i=0; i < MaxDimension; i++)
1840  {
1841  histogram[i]=(ssize_t *) AcquireQuantumMemory(256,sizeof(**histogram));
1842  extrema[i]=(short *) AcquireQuantumMemory(256,sizeof(**extrema));
1843  if ((histogram[i] == (ssize_t *) NULL) || (extrema[i] == (short *) NULL))
1844  {
1845  for (i-- ; i >= 0; i--)
1846  {
1847  extrema[i]=(short *) RelinquishMagickMemory(extrema[i]);
1848  histogram[i]=(ssize_t *) RelinquishMagickMemory(histogram[i]);
1849  }
1850  ThrowBinaryException(ResourceLimitError,"MemoryAllocationFailed",
1851  image->filename)
1852  }
1853  }
1854  /*
1855  Initialize histogram.
1856  */
1857  previous_colorspace=image->colorspace;
1858  (void) TransformImageColorspace(image,colorspace,exception);
1859  InitializeHistogram(image,histogram,exception);
1860  (void) OptimalTau(histogram[Red],Tau,0.2,DeltaTau,
1861  smooth_threshold == 0.0 ? 1.0 : smooth_threshold,extrema[Red]);
1862  (void) OptimalTau(histogram[Green],Tau,0.2,DeltaTau,
1863  smooth_threshold == 0.0 ? 1.0 : smooth_threshold,extrema[Green]);
1864  (void) OptimalTau(histogram[Blue],Tau,0.2,DeltaTau,
1865  smooth_threshold == 0.0 ? 1.0 : smooth_threshold,extrema[Blue]);
1866  /*
1867  Classify using the fuzzy c-Means technique.
1868  */
1869  status=Classify(image,extrema,cluster_threshold,WeightingExponent,verbose,
1870  exception);
1871  (void) TransformImageColorspace(image,previous_colorspace,exception);
1872  /*
1873  Relinquish resources.
1874  */
1875  for (i=0; i < MaxDimension; i++)
1876  {
1877  extrema[i]=(short *) RelinquishMagickMemory(extrema[i]);
1878  histogram[i]=(ssize_t *) RelinquishMagickMemory(histogram[i]);
1879  }
1880  return(status);
1881 }
1882 
1883 /*
1884 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1885 % %
1886 % %
1887 % %
1888 + Z e r o C r o s s H i s t o g r a m %
1889 % %
1890 % %
1891 % %
1892 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1893 %
1894 % ZeroCrossHistogram() find the zero crossings in a histogram and marks
1895 % directions as: 1 is negative to positive; 0 is zero crossing; and -1
1896 % is positive to negative.
1897 %
1898 % The format of the ZeroCrossHistogram method is:
1899 %
1900 % ZeroCrossHistogram(double *second_derivative,
1901 % const double smooth_threshold,short *crossings)
1902 %
1903 % A description of each parameter follows.
1904 %
1905 % o second_derivative: Specifies an array of doubles representing the
1906 % second derivative of the histogram of a particular color component.
1907 %
1908 % o crossings: This array of integers is initialized with
1909 % -1, 0, or 1 representing the slope of the first derivative of the
1910 % of a particular color component.
1911 %
1912 */
1913 static void ZeroCrossHistogram(double *second_derivative,
1914  const double smooth_threshold,short *crossings)
1915 {
1916  register ssize_t
1917  i;
1918 
1919  ssize_t
1920  parity;
1921 
1922  /*
1923  Merge low numbers to zero to help prevent noise.
1924  */
1925  for (i=0; i <= 255; i++)
1926  if ((second_derivative[i] < smooth_threshold) &&
1927  (second_derivative[i] >= -smooth_threshold))
1928  second_derivative[i]=0.0;
1929  /*
1930  Mark zero crossings.
1931  */
1932  parity=0;
1933  for (i=0; i <= 255; i++)
1934  {
1935  crossings[i]=0;
1936  if (second_derivative[i] < 0.0)
1937  {
1938  if (parity > 0)
1939  crossings[i]=(-1);
1940  parity=1;
1941  }
1942  else
1943  if (second_derivative[i] > 0.0)
1944  {
1945  if (parity < 0)
1946  crossings[i]=1;
1947  parity=(-1);
1948  }
1949  }
1950 }
size_t rows
Definition: image.h:172
#define magick_restrict
Definition: MagickCore.h:41
struct _IntervalTree IntervalTree
ExtentPacket blue
Definition: segment.c:143
ExtentPacket green
Definition: segment.c:143
MagickExport CacheView * DestroyCacheView(CacheView *cache_view)
Definition: cache-view.c:252
static void ConsolidateCrossings(ZeroCrossing *zero_crossing, const size_t number_crossings)
Definition: segment.c:717
struct _ExtentPacket ExtentPacket
ssize_t right
Definition: segment.c:158
PixelInfo * colormap
Definition: image.h:179
ExtentPacket red
Definition: segment.c:143
MagickProgressMonitor progress_monitor
Definition: image.h:303
struct _IntervalTree * sibling
Definition: segment.c:165
MagickExport MagickBooleanType SyncImage(Image *image, ExceptionInfo *exception)
Definition: image.c:3883
MagickExport MagickBooleanType TransformImageColorspace(Image *image, const ColorspaceType colorspace, ExceptionInfo *exception)
Definition: colorspace.c:1326
ssize_t right
Definition: segment.c:132
static Quantum GetPixelRed(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
#define ThrowFatalException(severity, tag)
#define WeightingExponent
Definition: segment.c:118
double mean_stability
Definition: segment.c:162
ssize_t index
Definition: segment.c:132
MagickRealType red
Definition: pixel.h:191
#define MagickPI
Definition: image-private.h:30
#define MagickAbsoluteValue(x)
Definition: image-private.h:25
struct _Cluster * next
Definition: segment.c:139
#define Tau
Definition: segment.c:121
static void * AcquireCriticalMemory(const size_t size)
MagickExport const Quantum * GetCacheViewVirtualPixels(const CacheView *cache_view, const ssize_t x, const ssize_t y, const size_t columns, const size_t rows, ExceptionInfo *exception)
Definition: cache-view.c:651
ssize_t count
Definition: segment.c:148
#define MagickEpsilon
Definition: magick-type.h:110
static void Stability(IntervalTree *node)
Definition: segment.c:1345
#define ThrowBinaryException(severity, tag, context)
Definition: log.h:52
ssize_t MagickOffsetType
Definition: magick-type.h:129
MagickExport void GetPixelInfo(const Image *image, PixelInfo *pixel)
Definition: pixel.c:2170
static void ScaleSpace(const ssize_t *, const double, double *)
Definition: segment.c:1733
Definition: image.h:151
static IntervalTree * InitializeIntervalTree(const ZeroCrossing *zero_crossing, const size_t number_crossings)
Definition: segment.c:1357
static const int Green
Definition: segment.c:185
MagickExport MagickBooleanType GetImageDynamicThreshold(const Image *image, const double cluster_threshold, const double smooth_threshold, PixelInfo *pixel, ExceptionInfo *exception)
Definition: segment.c:947
#define MagickCoreSignature
MagickExport Quantum * GetCacheViewAuthenticPixels(CacheView *cache_view, const ssize_t x, const ssize_t y, const size_t columns, const size_t rows, ExceptionInfo *exception)
Definition: cache-view.c:299
static void MeanStability(IntervalTree *node)
Definition: segment.c:1315
double histogram[256]
Definition: segment.c:173
static void InitializeList(IntervalTree **list, ssize_t *number_nodes, IntervalTree *node)
Definition: segment.c:1304
MagickExport ssize_t FormatLocaleFile(FILE *file, const char *magick_restrict format,...)
Definition: locale.c:404
MagickBooleanType
Definition: magick-type.h:158
unsigned int MagickStatusType
Definition: magick-type.h:121
static double PerceptibleReciprocal(const double x)
struct _ZeroCrossing ZeroCrossing
double center
Definition: segment.c:129
MagickExport MagickBooleanType SegmentImage(Image *image, const ColorspaceType colorspace, const MagickBooleanType verbose, const double cluster_threshold, const double smooth_threshold, ExceptionInfo *exception)
Definition: segment.c:1812
MagickExport const Quantum * GetVirtualPixels(const Image *image, const ssize_t x, const ssize_t y, const size_t columns, const size_t rows, ExceptionInfo *exception)
Definition: cache.c:3230
MagickExport void * AcquireQuantumMemory(const size_t count, const size_t quantum)
Definition: memory.c:543
struct _Cluster Cluster
#define SegmentImageTag
static Quantum GetPixelGreen(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
static void ActiveNodes(IntervalTree **list, ssize_t *number_nodes, IntervalTree *node)
Definition: segment.c:1497
MagickRealType blue
Definition: pixel.h:191
short crossings[256]
Definition: segment.c:177
MagickExport MagickBooleanType ThrowMagickException(ExceptionInfo *exception, const char *module, const char *function, const size_t line, const ExceptionType severity, const char *tag, const char *format,...)
Definition: exception.c:1145
MagickExport MagickBooleanType LogMagickEvent(const LogEventType type, const char *module, const char *function, const size_t line, const char *format,...)
Definition: log.c:1399
size_t signature
Definition: image.h:354
size_t columns
Definition: image.h:172
static double OptimalTau(const ssize_t *, const double, const double, const double, const double, short *)
Definition: segment.c:1523
static void ZeroCrossHistogram(double *, const double, short *)
Definition: segment.c:1913
static ssize_t DefineRegion(const short *, ExtentPacket *)
Definition: segment.c:834
#define MagickMax(x, y)
Definition: image-private.h:26
static MagickBooleanType Classify(Image *image, short **extrema, const double cluster_threshold, const double weighting_exponent, const MagickBooleanType verbose, ExceptionInfo *exception)
Definition: segment.c:248
size_t colors
Definition: image.h:172
static const int SafeMargin
Definition: segment.c:187
static size_t GetPixelChannels(const Image *magick_restrict image)
MagickExport MagickBooleanType AcquireImageColormap(Image *image, const size_t colors, ExceptionInfo *exception)
Definition: colormap.c:104
char filename[MagickPathExtent]
Definition: image.h:319
#define SegmentPower(ratio)
Definition: segment.c:119
#define GetMagickModule()
Definition: log.h:28
ssize_t id
Definition: segment.c:148
static Quantum ClampToQuantum(const MagickRealType value)
Definition: quantum.h:84
MagickExport CacheView * AcquireVirtualCacheView(const Image *image, ExceptionInfo *exception)
Definition: cache-view.c:149
static void DerivativeHistogram(const double *histogram, double *derivative)
Definition: segment.c:890
unsigned short Quantum
Definition: magick-type.h:82
static void FreeNodes(IntervalTree *)
Definition: segment.c:1514
static const int TreeLength
Definition: segment.c:188
#define DeltaTau
Definition: segment.c:113
MagickExport void * AcquireMagickMemory(const size_t size)
Definition: memory.c:472
static void SetPixelIndex(const Image *magick_restrict image, const Quantum index, Quantum *magick_restrict pixel)
static const int Red
Definition: segment.c:186
#define MagickMin(x, y)
Definition: image-private.h:27
#define ThrowClassifyException(severity, tag, label)
ColorspaceType
Definition: colorspace.h:25
MagickExport void * RelinquishMagickMemory(void *memory)
Definition: memory.c:1069
ssize_t left
Definition: segment.c:132
MagickRealType green
Definition: pixel.h:191
MagickBooleanType(* MagickProgressMonitor)(const char *, const MagickOffsetType, const MagickSizeType, void *)
Definition: monitor.h:26
static const int Blue
Definition: segment.c:184
ssize_t left
Definition: segment.c:158
#define MagickExport
MagickExport MagickBooleanType SyncCacheViewAuthenticPixels(CacheView *magick_restrict cache_view, ExceptionInfo *exception)
Definition: cache-view.c:1100
MagickExport CacheView * AcquireAuthenticCacheView(const Image *image, ExceptionInfo *exception)
Definition: cache-view.c:112
static void InitializeHistogram(const Image *, ssize_t **, ExceptionInfo *)
Definition: segment.c:1239
double tau
Definition: segment.c:155
double tau
Definition: segment.c:173
static Quantum GetPixelBlue(const Image *magick_restrict image, const Quantum *magick_restrict pixel)
struct _IntervalTree * child
Definition: segment.c:165
#define MaxDimension
Definition: segment.c:112
ColorspaceType colorspace
Definition: image.h:157
MagickExport MagickBooleanType SetImageProgress(const Image *image, const char *tag, const MagickOffsetType offset, const MagickSizeType extent)
Definition: monitor.c:136
double stability
Definition: segment.c:162
MagickBooleanType debug
Definition: image.h:334