]> granicus.if.org Git - imagemagick/blob - MagickCore/vision.c
(no commit message)
[imagemagick] / MagickCore / 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-2015 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 %    http://www.imagemagick.org/script/license.php                            %
27 %                                                                             %
28 %  Unless required by applicable law or agreed to in writing, software        %
29 %  distributed under the License is distributed on an "AS IS" BASIS,          %
30 %  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
31 %  See the License for the specific language governing permissions and        %
32 %  limitations under the License.                                             %
33 %                                                                             %
34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35 %
36 %
37 */
38 \f
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/colorspace.h"
46 #include "MagickCore/constitute.h"
47 #include "MagickCore/decorate.h"
48 #include "MagickCore/distort.h"
49 #include "MagickCore/draw.h"
50 #include "MagickCore/enhance.h"
51 #include "MagickCore/exception.h"
52 #include "MagickCore/exception-private.h"
53 #include "MagickCore/effect.h"
54 #include "MagickCore/gem.h"
55 #include "MagickCore/geometry.h"
56 #include "MagickCore/image-private.h"
57 #include "MagickCore/list.h"
58 #include "MagickCore/log.h"
59 #include "MagickCore/matrix.h"
60 #include "MagickCore/memory_.h"
61 #include "MagickCore/memory-private.h"
62 #include "MagickCore/monitor.h"
63 #include "MagickCore/monitor-private.h"
64 #include "MagickCore/montage.h"
65 #include "MagickCore/morphology.h"
66 #include "MagickCore/morphology-private.h"
67 #include "MagickCore/opencl-private.h"
68 #include "MagickCore/paint.h"
69 #include "MagickCore/pixel-accessor.h"
70 #include "MagickCore/pixel-private.h"
71 #include "MagickCore/property.h"
72 #include "MagickCore/quantum.h"
73 #include "MagickCore/quantum-private.h"
74 #include "MagickCore/resource_.h"
75 #include "MagickCore/signature-private.h"
76 #include "MagickCore/string_.h"
77 #include "MagickCore/string-private.h"
78 #include "MagickCore/thread-private.h"
79 #include "MagickCore/token.h"
80 #include "MagickCore/vision.h"
81 \f
82 /*
83 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
84 %                                                                             %
85 %                                                                             %
86 %                                                                             %
87 %     C o n n e c t e d C o m p o n e n t s I m a g e                         %
88 %                                                                             %
89 %                                                                             %
90 %                                                                             %
91 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
92 %
93 %  ConnectedComponentsImage() returns the connected-components of the image
94 %  uniquely labeled.  Choose from 4 or 8-way connectivity.
95 %
96 %  The format of the ConnectedComponentsImage method is:
97 %
98 %      Image *ConnectedComponentsImage(const Image *image,
99 %        const size_t connectivity,ExceptionInfo *exception)
100 %
101 %  A description of each parameter follows:
102 %
103 %    o image: the image.
104 %
105 %    o connectivity: how many neighbors to visit, choose from 4 or 8.
106 %
107 %    o exception: return any errors or warnings in this structure.
108 %
109 */
110
111 typedef struct _CCObject
112 {
113   ssize_t
114     id;
115
116   RectangleInfo
117     bounding_box;
118
119   PixelInfo
120     color;
121
122   PointInfo
123     centroid;
124
125   size_t
126     area,
127     census;
128 } CCObject;
129
130 static int CCObjectCompare(const void *x,const void *y)
131 {
132   CCObject
133     *p,
134     *q;
135
136   p=(CCObject *) x;
137   q=(CCObject *) y;
138   return((int) (q->area-(ssize_t) p->area));
139 }
140
141 static MagickBooleanType MergeConnectedComponents(Image *image,
142   const size_t number_objects,const double area_threshold,
143   ExceptionInfo *exception)
144 {
145   CacheView
146     *image_view;
147
148   CCObject
149     *object;
150
151   MagickBooleanType
152     status;
153
154   register ssize_t
155     i;
156
157   ssize_t
158     y;
159
160   /*
161     Collect statistics on unique objects.
162   */
163   object=(CCObject *) AcquireQuantumMemory(number_objects,sizeof(*object));
164   if (object == (CCObject *) NULL) {
165     (void) ThrowMagickException(exception,GetMagickModule(),ResourceLimitError,
166       "MemoryAllocationFailed","`%s'",image->filename);
167     return(MagickFalse);
168   }
169   (void) ResetMagickMemory(object,0,number_objects*sizeof(*object));
170   for (i=0; i < (ssize_t) number_objects; i++) {
171     object[i].id=i;
172     object[i].bounding_box.x=(ssize_t) image->columns;
173     object[i].bounding_box.y=(ssize_t) image->rows;
174   }
175   status=MagickTrue;
176   image_view=AcquireVirtualCacheView(image,exception);
177   for (y=0; y < (ssize_t) image->rows; y++) {
178     register const Quantum
179       *restrict p;
180
181     register ssize_t
182       x;
183
184     if (status == MagickFalse)
185       continue;
186     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
187     if (p == (const Quantum *) NULL) {
188       status=MagickFalse;
189       continue;
190     }
191     for (x=0; x < (ssize_t) image->columns; x++) {
192       i=(ssize_t) *p;
193       if (x < object[i].bounding_box.x)
194         object[i].bounding_box.x=x;
195       if (x > (ssize_t) object[i].bounding_box.width)
196         object[i].bounding_box.width=(size_t) x;
197       if (y < object[i].bounding_box.y)
198         object[i].bounding_box.y=y;
199       if (y > (ssize_t) object[i].bounding_box.height)
200         object[i].bounding_box.height=(size_t) y;
201       object[i].area++;
202       p+=GetPixelChannels(image);
203     }
204   }
205   image_view=DestroyCacheView(image_view);
206   for (i=0; i < (ssize_t) number_objects; i++) {
207     object[i].bounding_box.width-=(object[i].bounding_box.x-1);
208     object[i].bounding_box.height-=(object[i].bounding_box.y-1);
209   }
210   /*
211     Merge objects below area threshold.
212   */
213   image_view=AcquireAuthenticCacheView(image,exception);
214   for (i=0; i < (ssize_t) number_objects; i++) {
215     RectangleInfo
216       bounding_box;
217
218     register ssize_t
219       j;
220
221     size_t
222       census,
223       id;
224
225     if (status == MagickFalse)
226       continue;
227     if ((double) object[i].area >= area_threshold)
228       continue;
229     for (j=0; j < (ssize_t) number_objects; j++)
230       object[j].census=0;
231     bounding_box=object[i].bounding_box;
232     for (y=0; y < (ssize_t) bounding_box.height+2; y++) {
233       register const Quantum
234         *restrict p;
235
236       register ssize_t
237         x;
238
239       if (status == MagickFalse)
240         continue;
241       p=GetCacheViewVirtualPixels(image_view,bounding_box.x-1,bounding_box.y+y-
242         1,bounding_box.width+2,1,exception);
243       if (p == (const Quantum *) NULL) {
244         status=MagickFalse;
245         continue;
246       }
247       for (x=0; x < (ssize_t) bounding_box.width+2; x++) {
248         j=(ssize_t) *p;
249         if (j != i)
250           object[j].census++;
251         p+=GetPixelChannels(image);
252       }
253     }
254     census=0;
255     id=0;
256     for (j=0; j < (ssize_t) number_objects; j++)
257       if (census < object[j].census) {
258         census=object[j].census;
259         id=(size_t) j;
260       }
261     for (y=0; y < (ssize_t) bounding_box.height; y++) {
262       register Quantum
263         *restrict q;
264
265       register ssize_t
266         x;
267
268       if (status == MagickFalse)
269         continue;
270       q=GetCacheViewAuthenticPixels(image_view,bounding_box.x,bounding_box.y+y,
271         bounding_box.width,1,exception);
272       if (q == (Quantum *) NULL) {
273         status=MagickFalse;
274         continue;
275       }
276       for (x=0; x < (ssize_t) bounding_box.width; x++) {
277         if ((ssize_t) *q == i)
278           *q=(Quantum) id;
279         q+=GetPixelChannels(image);
280       }
281       if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
282         status=MagickFalse;
283     }
284   }
285   image_view=DestroyCacheView(image_view);
286   object=(CCObject *) RelinquishMagickMemory(object);
287   return(status);
288 }
289
290 static MagickBooleanType StatisticsComponentsStatistics(const Image *image,
291   const Image *component_image,const size_t number_objects,
292   ExceptionInfo *exception)
293 {
294   CacheView
295     *component_view,
296     *image_view;
297
298   CCObject
299     *object;
300
301   MagickBooleanType
302     status;
303
304   register ssize_t
305     i;
306
307   ssize_t
308     y;
309
310   /*
311     Collect statistics on unique objects.
312   */
313   object=(CCObject *) AcquireQuantumMemory(number_objects,sizeof(*object));
314   if (object == (CCObject *) NULL) {
315     (void) ThrowMagickException(exception,GetMagickModule(),ResourceLimitError,
316       "MemoryAllocationFailed","`%s'",image->filename);
317     return(MagickFalse);
318   }
319   (void) ResetMagickMemory(object,0,number_objects*sizeof(*object));
320   for (i=0; i < (ssize_t) number_objects; i++) {
321     object[i].id=i;
322     object[i].bounding_box.x=(ssize_t) component_image->columns;
323     object[i].bounding_box.y=(ssize_t) component_image->rows;
324     GetPixelInfo(image,&object[i].color);
325   }
326   status=MagickTrue;
327   image_view=AcquireVirtualCacheView(image,exception);
328   component_view=AcquireVirtualCacheView(component_image,exception);
329   for (y=0; y < (ssize_t) image->rows; y++) {
330     register const Quantum
331       *restrict p,
332       *restrict q;
333
334     register ssize_t
335       x;
336
337     if (status == MagickFalse)
338       continue;
339     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
340     q=GetCacheViewVirtualPixels(component_view,0,y,component_image->columns,1,
341       exception);
342     if ((p == (const Quantum *) NULL) || (q == (const Quantum *) NULL)) {
343       status=MagickFalse;
344       continue;
345     }
346     for (x=0; x < (ssize_t) image->columns; x++) {
347       i=(ssize_t) *q;
348       if (x < object[i].bounding_box.x)
349         object[i].bounding_box.x=x;
350       if (x > (ssize_t) object[i].bounding_box.width)
351         object[i].bounding_box.width=(size_t) x;
352       if (y < object[i].bounding_box.y)
353         object[i].bounding_box.y=y;
354       if (y > (ssize_t) object[i].bounding_box.height)
355         object[i].bounding_box.height=(size_t) y;
356       object[i].color.red+=GetPixelRed(image,p);
357       object[i].color.green+=GetPixelGreen(image,p);
358       object[i].color.blue+=GetPixelBlue(image,p);
359       object[i].color.alpha+=GetPixelAlpha(image,p);
360       object[i].color.black+=GetPixelBlack(image,p);
361       object[i].centroid.x+=x;
362       object[i].centroid.y+=y;
363       object[i].area++;
364       p+=GetPixelChannels(image);
365       q+=GetPixelChannels(component_image);
366     }
367   }
368   for (i=0; i < (ssize_t) number_objects; i++) {
369     object[i].bounding_box.width-=(object[i].bounding_box.x-1);
370     object[i].bounding_box.height-=(object[i].bounding_box.y-1);
371     object[i].color.red=ClampToQuantum(object[i].color.red/object[i].area);
372     object[i].color.green=ClampToQuantum(object[i].color.green/object[i].area);
373     object[i].color.blue=ClampToQuantum(object[i].color.blue/object[i].area);
374     object[i].color.alpha=ClampToQuantum(object[i].color.alpha/object[i].area);
375     object[i].color.black=ClampToQuantum(object[i].color.black/object[i].area);
376     object[i].centroid.x=object[i].centroid.x/object[i].area;
377     object[i].centroid.y=object[i].centroid.y/object[i].area;
378   }
379   component_view=DestroyCacheView(component_view);
380   image_view=DestroyCacheView(image_view);
381   /*
382     Report statistics on unique objects.
383   */
384   qsort((void *) object,number_objects,sizeof(*object),CCObjectCompare);
385   (void) fprintf(stdout,
386     "Objects (id: bounding-box centroid area mean-color):\n");
387   for (i=0; i < (ssize_t) number_objects; i++) {
388     char
389       mean_color[MaxTextExtent];
390
391     if (status == MagickFalse)
392       break;
393     if (object[i].area < MagickEpsilon)
394       continue;
395     GetColorTuple(&object[i].color,MagickFalse,mean_color);
396     (void) fprintf(stdout,
397       "  %.20g: %.20gx%.20g%+.20g%+.20g %.1f,%.1f %.20g %s\n",(double)
398       object[i].id,(double) object[i].bounding_box.width,(double)
399       object[i].bounding_box.height,(double) object[i].bounding_box.x,
400       (double) object[i].bounding_box.y,object[i].centroid.x,
401       object[i].centroid.y,(double) object[i].area,mean_color);
402   }
403   object=(CCObject *) RelinquishMagickMemory(object);
404   return(status);
405 }
406
407 MagickExport Image *ConnectedComponentsImage(const Image *image,
408   const size_t connectivity,ExceptionInfo *exception)
409 {
410 #define ConnectedComponentsImageTag  "ConnectedComponents/Image"
411
412   CacheView
413     *image_view,
414     *component_view;
415
416   const char
417     *artifact;
418
419   double
420     area_threshold;
421
422   Image
423     *component_image;
424
425   MagickBooleanType
426     status;
427
428   MagickOffsetType
429     progress;
430
431   MatrixInfo
432     *equivalences;
433
434   size_t
435     size;
436
437   ssize_t
438     n,
439     y;
440
441   /*
442     Initialize connected components image attributes.
443   */
444   assert(image != (Image *) NULL);
445   assert(image->signature == MagickSignature);
446   if (image->debug != MagickFalse)
447     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
448   assert(exception != (ExceptionInfo *) NULL);
449   assert(exception->signature == MagickSignature);
450   component_image=CloneImage(image,image->columns,image->rows,MagickTrue,
451     exception);
452   if (component_image == (Image *) NULL)
453     return((Image *) NULL);
454   component_image->depth=MAGICKCORE_QUANTUM_DEPTH;
455   component_image->colorspace=GRAYColorspace;
456   status=SetImageStorageClass(component_image,DirectClass,exception);
457   if (status == MagickFalse) {
458     component_image=DestroyImage(component_image);
459     return((Image *) NULL);
460   }
461   /*
462     Initialize connected components equivalences.
463   */
464   size=image->columns*image->rows;
465   if (image->columns != (size/image->rows)) {
466     component_image=DestroyImage(component_image);
467     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
468   }
469   equivalences=AcquireMatrixInfo(size,1,sizeof(ssize_t),exception);
470   if (equivalences == (MatrixInfo *) NULL) {
471     component_image=DestroyImage(component_image);
472     return((Image *) NULL);
473   }
474   for (n=0; n < (ssize_t) (image->columns*image->rows); n++)
475     status=SetMatrixElement(equivalences,n,0,&n);
476   /*
477     Find connected components.
478   */
479   status=MagickTrue;
480   progress=0;
481   image_view=AcquireVirtualCacheView(image,exception);
482   for (n=0; n < (ssize_t) (connectivity > 4 ? 4 : 2); n++) {
483     ssize_t
484       connect4[2][2] = { { -1,  0 }, {  0, -1 } },
485       connect8[4][2] = { { -1, -1 }, { -1,  0 }, { -1,  1 }, {  0, -1 } },
486       dx,
487       dy;
488
489     if (status == MagickFalse)
490       continue;
491     dy=connectivity > 4 ? connect8[n][0] : connect4[n][0];
492     dx=connectivity > 4 ? connect8[n][1] : connect4[n][1];
493     for (y=0; y < (ssize_t) image->rows; y++) {
494       register const Quantum
495         *restrict p;
496
497       register ssize_t
498         x;
499
500       if (status == MagickFalse)
501         continue;
502       p=GetCacheViewVirtualPixels(image_view,0,y-1,image->columns,3,exception);
503       if (p == (const Quantum *) NULL) {
504         status=MagickFalse;
505         continue;
506       }
507       p+=image->columns*GetPixelChannels(image);
508       for (x=0; x < (ssize_t) image->columns; x++) {
509         PixelInfo
510           pixel,
511           target;
512
513         ssize_t
514           neighbor_offset,
515           object,
516           offset,
517           ox,
518           oy,
519           root;
520
521         /*
522           Is neighbor an authentic pixel and a different color than the pixel?
523         */
524         GetPixelInfoPixel(image,p,&pixel);
525         neighbor_offset=dy*(image->columns*GetPixelChannels(image))+dx*
526           GetPixelChannels(image);
527         GetPixelInfoPixel(image,p+neighbor_offset,&target);
528         if (((x+dx) < 0) || ((x+dx) >= (ssize_t) image->columns) ||
529             ((y+dy) < 0) || ((y+dy) >= (ssize_t) image->rows) ||
530             (IsFuzzyEquivalencePixelInfo(&pixel,&target) == MagickFalse)) {
531           p+=GetPixelChannels(image);
532           continue;
533         }
534         /*
535           Resolve this equivalence.
536         */
537         offset=y*image->columns+x;
538         neighbor_offset=dy*image->columns+dx;
539         ox=offset;
540         status=GetMatrixElement(equivalences,ox,0,&object);
541         while (object != ox) {
542           ox=object;
543           status=GetMatrixElement(equivalences,ox,0,&object);
544         }
545         oy=offset+neighbor_offset;
546         status=GetMatrixElement(equivalences,oy,0,&object);
547         while (object != oy) {
548           oy=object;
549           status=GetMatrixElement(equivalences,oy,0,&object);
550         }
551         if (ox < oy) {
552           status=SetMatrixElement(equivalences,oy,0,&ox);
553           root=ox;
554         } else {
555           status=SetMatrixElement(equivalences,ox,0,&oy);
556           root=oy;
557         }
558         ox=offset;
559         status=GetMatrixElement(equivalences,ox,0,&object);
560         while (object != root) {
561           status=GetMatrixElement(equivalences,ox,0,&object);
562           status=SetMatrixElement(equivalences,ox,0,&root);
563         }
564         oy=offset+neighbor_offset;
565         status=GetMatrixElement(equivalences,oy,0,&object);
566         while (object != root) {
567           status=GetMatrixElement(equivalences,oy,0,&object);
568           status=SetMatrixElement(equivalences,oy,0,&root);
569         }
570         status=SetMatrixElement(equivalences,y*image->columns+x,0,&root);
571         p+=GetPixelChannels(image);
572       }
573     }
574   }
575   image_view=DestroyCacheView(image_view);
576   /*
577     Label connected components.
578   */
579   n=0;
580   component_view=AcquireAuthenticCacheView(component_image,exception);
581   for (y=0; y < (ssize_t) component_image->rows; y++) {
582     register Quantum
583       *restrict q;
584
585     register ssize_t
586       x;
587
588     if (status == MagickFalse)
589       continue;
590     q=QueueCacheViewAuthenticPixels(component_view,0,y,component_image->columns,
591       1,exception);
592     if (q == (Quantum *) NULL) {
593       status=MagickFalse;
594       continue;
595     }
596     for (x=0; x < (ssize_t) component_image->columns; x++) {
597       ssize_t
598         object,
599         offset;
600
601       offset=y*image->columns+x;
602       status=GetMatrixElement(equivalences,offset,0,&object);
603       if (object == offset) {
604         object=n++;
605         status=SetMatrixElement(equivalences,offset,0,&object);
606       } else {
607         status=GetMatrixElement(equivalences,object,0,&object);
608         status=SetMatrixElement(equivalences,offset,0,&object);
609       }
610       *q=(Quantum) (object > (ssize_t) QuantumRange ? (ssize_t) QuantumRange :
611         object);
612       q+=GetPixelChannels(component_image);
613     }
614     if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse)
615       status=MagickFalse;
616     if (image->progress_monitor != (MagickProgressMonitor) NULL) {
617       MagickBooleanType
618         proceed;
619
620       proceed=SetImageProgress(image,ConnectedComponentsImageTag,progress++,
621         image->rows);
622       if (proceed == MagickFalse)
623         status=MagickFalse;
624     }
625   }
626   component_view=DestroyCacheView(component_view);
627   equivalences=DestroyMatrixInfo(equivalences);
628   if (n > QuantumRange) {
629     component_image=DestroyImage(component_image);
630     ThrowImageException(ResourceLimitError,"TooManyObjects");
631   }
632   artifact=GetImageArtifact(image,"connected-components:area-threshold");
633   area_threshold=0.0;
634   if (artifact != (const char *) NULL)
635     area_threshold=StringToDouble(artifact,(char **) NULL);
636   if (area_threshold > 0.0)
637     status=MergeConnectedComponents(component_image,(size_t) n,area_threshold,
638       exception);
639   artifact=GetImageArtifact(image,"connected-components:verbose");
640   if (IsStringTrue(artifact) != MagickFalse)
641     status=StatisticsComponentsStatistics(image,component_image,(size_t) n,
642       exception);
643   if (status == MagickFalse)
644     component_image=DestroyImage(component_image);
645   return(component_image);
646 }