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-2016 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 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/pixel-private.h" 72#include "MagickCore/property.h" 73#include "MagickCore/quantum.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 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. The returned connected components image colors member 95% defines the number of unique objects. Choose from 4 or 8-way connectivity. 96% 97% You are responsible for freeing the connected components objects resources 98% with this statement; 99% 100% objects = (CCObjectInfo *) RelinquishMagickMemory(objects); 101% 102% The format of the ConnectedComponentsImage method is: 103% 104% Image *ConnectedComponentsImage(const Image *image, 105% const size_t connectivity,CCObjectInfo **objects, 106% ExceptionInfo *exception) 107% 108% A description of each parameter follows: 109% 110% o image: the image. 111% 112% o connectivity: how many neighbors to visit, choose from 4 or 8. 113% 114% o objects: return the attributes of each unique object. 115% 116% o exception: return any errors or warnings in this structure. 117% 118*/ 119 120static int CCObjectInfoCompare(const void *x,const void *y) 121{ 122 CCObjectInfo 123 *p, 124 *q; 125 126 p=(CCObjectInfo *) x; 127 q=(CCObjectInfo *) y; 128 return((int) (q->area-(ssize_t) p->area)); 129} 130 131MagickExport Image *ConnectedComponentsImage(const Image *image, 132 const size_t connectivity,CCObjectInfo **objects,ExceptionInfo *exception) 133{ 134#define ConnectedComponentsImageTag "ConnectedComponents/Image" 135 136 CacheView 137 *image_view, 138 *component_view; 139 140 CCObjectInfo 141 *object; 142 143 char 144 *p; 145 146 const char 147 *artifact; 148 149 double 150 area_threshold; 151 152 Image 153 *component_image; 154 155 MagickBooleanType 156 status; 157 158 MagickOffsetType 159 progress; 160 161 MatrixInfo 162 *equivalences; 163 164 register ssize_t 165 i; 166 167 size_t 168 size; 169 170 ssize_t 171 first, 172 last, 173 n, 174 step, 175 y; 176 177 /* 178 Initialize connected components image attributes. 179 */ 180 assert(image != (Image *) NULL); 181 assert(image->signature == MagickCoreSignature); 182 if (image->debug != MagickFalse) 183 (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename); 184 assert(exception != (ExceptionInfo *) NULL); 185 assert(exception->signature == MagickCoreSignature); 186 if (objects != (CCObjectInfo **) NULL) 187 *objects=(CCObjectInfo *) NULL; 188 component_image=CloneImage(image,image->columns,image->rows,MagickTrue, 189 exception); 190 if (component_image == (Image *) NULL) 191 return((Image *) NULL); 192 component_image->depth=MAGICKCORE_QUANTUM_DEPTH; 193 if (AcquireImageColormap(component_image,MaxColormapSize,exception) == MagickFalse) 194 { 195 component_image=DestroyImage(component_image); 196 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed"); 197 } 198 /* 199 Initialize connected components equivalences. 200 */ 201 size=image->columns*image->rows; 202 if (image->columns != (size/image->rows)) 203 { 204 component_image=DestroyImage(component_image); 205 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed"); 206 } 207 equivalences=AcquireMatrixInfo(size,1,sizeof(ssize_t),exception); 208 if (equivalences == (MatrixInfo *) NULL) 209 { 210 component_image=DestroyImage(component_image); 211 return((Image *) NULL); 212 } 213 for (n=0; n < (ssize_t) (image->columns*image->rows); n++) 214 (void) SetMatrixElement(equivalences,n,0,&n); 215 object=(CCObjectInfo *) AcquireQuantumMemory(MaxColormapSize,sizeof(*object)); 216 if (object == (CCObjectInfo *) NULL) 217 { 218 equivalences=DestroyMatrixInfo(equivalences); 219 component_image=DestroyImage(component_image); 220 ThrowImageException(ResourceLimitError,"MemoryAllocationFailed"); 221 } 222 (void) ResetMagickMemory(object,0,MaxColormapSize*sizeof(*object)); 223 for (i=0; i < (ssize_t) MaxColormapSize; i++) 224 { 225 object[i].id=i; 226 object[i].bounding_box.x=(ssize_t) image->columns; 227 object[i].bounding_box.y=(ssize_t) image->rows; 228 GetPixelInfo(image,&object[i].color); 229 } 230 /* 231 Find connected components. 232 */ 233 status=MagickTrue; 234 progress=0; 235 image_view=AcquireVirtualCacheView(image,exception); 236 for (n=0; n < (ssize_t) (connectivity > 4 ? 4 : 2); n++) 237 { 238 ssize_t 239 connect4[2][2] = { { -1, 0 }, { 0, -1 } }, 240 connect8[4][2] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 } }, 241 dx, 242 dy; 243 244 if (status == MagickFalse) 245 continue; 246 dy=connectivity > 4 ? connect8[n][0] : connect4[n][0]; 247 dx=connectivity > 4 ? connect8[n][1] : connect4[n][1]; 248 for (y=0; y < (ssize_t) image->rows; y++) 249 { 250 register const Quantum 251 *magick_restrict p; 252 253 register ssize_t 254 x; 255 256 if (status == MagickFalse) 257 continue; 258 p=GetCacheViewVirtualPixels(image_view,0,y-1,image->columns,3,exception); 259 if (p == (const Quantum *) NULL) 260 { 261 status=MagickFalse; 262 continue; 263 } 264 p+=GetPixelChannels(image)*image->columns; 265 for (x=0; x < (ssize_t) image->columns; x++) 266 { 267 PixelInfo 268 pixel, 269 target; 270 271 ssize_t 272 neighbor_offset, 273 object, 274 offset, 275 ox, 276 oy, 277 root; 278 279 /* 280 Is neighbor an authentic pixel and a different color than the pixel? 281 */ 282 GetPixelInfoPixel(image,p,&pixel); 283 neighbor_offset=dy*(GetPixelChannels(image)*image->columns)+dx* 284 GetPixelChannels(image); 285 GetPixelInfoPixel(image,p+neighbor_offset,&target); 286 if (((x+dx) < 0) || ((x+dx) >= (ssize_t) image->columns) || 287 ((y+dy) < 0) || ((y+dy) >= (ssize_t) image->rows) || 288 (IsFuzzyEquivalencePixelInfo(&pixel,&target) == MagickFalse)) 289 { 290 p+=GetPixelChannels(image); 291 continue; 292 } 293 /* 294 Resolve this equivalence. 295 */ 296 offset=y*image->columns+x; 297 neighbor_offset=dy*image->columns+dx; 298 ox=offset; 299 status=GetMatrixElement(equivalences,ox,0,&object); 300 while (object != ox) 301 { 302 ox=object; 303 status=GetMatrixElement(equivalences,ox,0,&object); 304 } 305 oy=offset+neighbor_offset; 306 status=GetMatrixElement(equivalences,oy,0,&object); 307 while (object != oy) 308 { 309 oy=object; 310 status=GetMatrixElement(equivalences,oy,0,&object); 311 } 312 if (ox < oy) 313 { 314 status=SetMatrixElement(equivalences,oy,0,&ox); 315 root=ox; 316 } 317 else 318 { 319 status=SetMatrixElement(equivalences,ox,0,&oy); 320 root=oy; 321 } 322 ox=offset; 323 status=GetMatrixElement(equivalences,ox,0,&object); 324 while (object != root) 325 { 326 status=GetMatrixElement(equivalences,ox,0,&object); 327 status=SetMatrixElement(equivalences,ox,0,&root); 328 } 329 oy=offset+neighbor_offset; 330 status=GetMatrixElement(equivalences,oy,0,&object); 331 while (object != root) 332 { 333 status=GetMatrixElement(equivalences,oy,0,&object); 334 status=SetMatrixElement(equivalences,oy,0,&root); 335 } 336 status=SetMatrixElement(equivalences,y*image->columns+x,0,&root); 337 p+=GetPixelChannels(image); 338 } 339 } 340 } 341 image_view=DestroyCacheView(image_view); 342 /* 343 Label connected components. 344 */ 345 n=0; 346 image_view=AcquireVirtualCacheView(image,exception); 347 component_view=AcquireAuthenticCacheView(component_image,exception); 348 for (y=0; y < (ssize_t) component_image->rows; y++) 349 { 350 register const Quantum 351 *magick_restrict p; 352 353 register Quantum 354 *magick_restrict q; 355 356 register ssize_t 357 x; 358 359 if (status == MagickFalse) 360 continue; 361 p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception); 362 q=QueueCacheViewAuthenticPixels(component_view,0,y,component_image->columns, 363 1,exception); 364 if ((p == (const Quantum *) NULL) || (q == (Quantum *) NULL)) 365 { 366 status=MagickFalse; 367 continue; 368 } 369 for (x=0; x < (ssize_t) component_image->columns; x++) 370 { 371 ssize_t 372 id, 373 offset; 374 375 offset=y*image->columns+x; 376 status=GetMatrixElement(equivalences,offset,0,&id); 377 if (id == offset) 378 { 379 id=n++; 380 if (n > (ssize_t) MaxColormapSize) 381 break; 382 status=SetMatrixElement(equivalences,offset,0,&id); 383 } 384 else 385 { 386 status=GetMatrixElement(equivalences,id,0,&id); 387 status=SetMatrixElement(equivalences,offset,0,&id); 388 } 389 if (x < object[id].bounding_box.x) 390 object[id].bounding_box.x=x; 391 if (x > (ssize_t) object[id].bounding_box.width) 392 object[id].bounding_box.width=(size_t) x; 393 if (y < object[id].bounding_box.y) 394 object[id].bounding_box.y=y; 395 if (y > (ssize_t) object[id].bounding_box.height) 396 object[id].bounding_box.height=(size_t) y; 397 object[id].color.red+=GetPixelRed(image,p); 398 object[id].color.green+=GetPixelGreen(image,p); 399 object[id].color.blue+=GetPixelBlue(image,p); 400 object[id].color.black+=GetPixelBlack(image,p); 401 object[id].color.alpha+=GetPixelAlpha(image,p); 402 object[id].centroid.x+=x; 403 object[id].centroid.y+=y; 404 object[id].area++; 405 SetPixelIndex(component_image,(Quantum) id,q); 406 p+=GetPixelChannels(image); 407 q+=GetPixelChannels(component_image); 408 } 409 if (n > (ssize_t) MaxColormapSize) 410 break; 411 if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse) 412 status=MagickFalse; 413 if (image->progress_monitor != (MagickProgressMonitor) NULL) 414 { 415 MagickBooleanType 416 proceed; 417 418 proceed=SetImageProgress(image,ConnectedComponentsImageTag,progress++, 419 image->rows); 420 if (proceed == MagickFalse) 421 status=MagickFalse; 422 } 423 } 424 component_view=DestroyCacheView(component_view); 425 image_view=DestroyCacheView(image_view); 426 equivalences=DestroyMatrixInfo(equivalences); 427 if (n > (ssize_t) MaxColormapSize) 428 { 429 object=(CCObjectInfo *) RelinquishMagickMemory(object); 430 component_image=DestroyImage(component_image); 431 ThrowImageException(ResourceLimitError,"TooManyObjects"); 432 } 433 component_image->colors=(size_t) n; 434 for (i=0; i < (ssize_t) component_image->colors; i++) 435 { 436 object[i].bounding_box.width-=(object[i].bounding_box.x-1); 437 object[i].bounding_box.height-=(object[i].bounding_box.y-1); 438 object[i].color.red=object[i].color.red/object[i].area; 439 object[i].color.green=object[i].color.green/object[i].area; 440 object[i].color.blue=object[i].color.blue/object[i].area; 441 object[i].color.alpha=object[i].color.alpha/object[i].area; 442 object[i].color.black=object[i].color.black/object[i].area; 443 object[i].centroid.x=object[i].centroid.x/object[i].area; 444 object[i].centroid.y=object[i].centroid.y/object[i].area; 445 } 446 artifact=GetImageArtifact(image,"connected-components:area-threshold"); 447 area_threshold=0.0; 448 if (artifact != (const char *) NULL) 449 area_threshold=StringToDouble(artifact,(char **) NULL); 450 if (area_threshold > 0.0) 451 { 452 /* 453 Merge object below area threshold. 454 */ 455 component_view=AcquireAuthenticCacheView(component_image,exception); 456 for (i=0; i < (ssize_t) component_image->colors; i++) 457 { 458 double 459 census; 460 461 RectangleInfo 462 bounding_box; 463 464 register ssize_t 465 j; 466 467 size_t 468 id; 469 470 if (status == MagickFalse) 471 continue; 472 if ((double) object[i].area >= area_threshold) 473 continue; 474 for (j=0; j < (ssize_t) component_image->colors; j++) 475 object[j].census=0; 476 bounding_box=object[i].bounding_box; 477 for (y=0; y < (ssize_t) bounding_box.height+2; y++) 478 { 479 register const Quantum 480 *magick_restrict p; 481 482 register ssize_t 483 x; 484 485 if (status == MagickFalse) 486 continue; 487 p=GetCacheViewVirtualPixels(component_view,bounding_box.x-1, 488 bounding_box.y+y-1,bounding_box.width+2,1,exception); 489 if (p == (const Quantum *) NULL) 490 { 491 status=MagickFalse; 492 continue; 493 } 494 for (x=0; x < (ssize_t) bounding_box.width+2; x++) 495 { 496 j=(ssize_t) GetPixelIndex(component_image,p); 497 if (j != i) 498 object[j].census++; 499 } 500 } 501 census=0; 502 id=0; 503 for (j=0; j < (ssize_t) component_image->colors; j++) 504 if (census < object[j].census) 505 { 506 census=object[j].census; 507 id=(size_t) j; 508 } 509 object[id].area+=object[i].area; 510 for (y=0; y < (ssize_t) bounding_box.height; y++) 511 { 512 register Quantum 513 *magick_restrict q; 514 515 register ssize_t 516 x; 517 518 if (status == MagickFalse) 519 continue; 520 q=GetCacheViewAuthenticPixels(component_view,bounding_box.x, 521 bounding_box.y+y,bounding_box.width,1,exception); 522 if (q == (Quantum *) NULL) 523 { 524 status=MagickFalse; 525 continue; 526 } 527 for (x=0; x < (ssize_t) bounding_box.width; x++) 528 { 529 if ((ssize_t) GetPixelIndex(component_image,q) == i) 530 SetPixelIndex(image,(Quantum) id,q); 531 q+=GetPixelChannels(component_image); 532 } 533 if (SyncCacheViewAuthenticPixels(component_view,exception) == MagickFalse) 534 status=MagickFalse; 535 } 536 } 537 (void) SyncImage(component_image,exception); 538 } 539 artifact=GetImageArtifact(image,"connected-components:mean-color"); 540 if (IsStringTrue(artifact) != MagickFalse) 541 { 542 /* 543 Replace object with mean color. 544 */ 545 for (i=0; i < (ssize_t) component_image->colors; i++) 546 component_image->colormap[i]=object[i].color; 547 } 548 artifact=GetImageArtifact(image,"connected-components:keep"); 549 if (artifact != (const char *) NULL) 550 { 551 /* 552 Keep these object (make others transparent). 553 */ 554 for (i=0; i < (ssize_t) component_image->colors; i++) 555 object[i].census=0; 556 for (p=(char *) artifact; *p != '\0';) 557 { 558 while ((isspace((int) ((unsigned char) *p)) != 0) || (*p == ',')) 559 p++; 560 first=strtol(p,&p,10); 561 if (first < 0) 562 first+=(long) component_image->colors; 563 last=first; 564 while (isspace((int) ((unsigned char) *p)) != 0) 565 p++; 566 if (*p == '-') 567 { 568 last=strtol(p+1,&p,10); 569 if (last < 0) 570 last+=(long) component_image->colors; 571 } 572 for (step=first > last ? -1 : 1; first != (last+step); first+=step) 573 object[first].census++; 574 } 575 for (i=0; i < (ssize_t) component_image->colors; i++) 576 { 577 if (object[i].census != 0) 578 continue; 579 component_image->alpha_trait=BlendPixelTrait; 580 component_image->colormap[i].alpha=TransparentAlpha; 581 } 582 } 583 artifact=GetImageArtifact(image,"connected-components:remove"); 584 if (artifact != (const char *) NULL) 585 { 586 /* 587 Remove these object (make them transparent). 588 */ 589 for (p=(char *) artifact; *p != '\0';) 590 { 591 while ((isspace((int) ((unsigned char) *p)) != 0) || (*p == ',')) 592 p++; 593 first=strtol(p,&p,10); 594 if (first < 0) 595 first+=(long) component_image->colors; 596 last=first; 597 while (isspace((int) ((unsigned char) *p)) != 0) 598 p++; 599 if (*p == '-') 600 { 601 last=strtol(p+1,&p,10); 602 if (last < 0) 603 last+=(long) component_image->colors; 604 } 605 for (step=first > last ? -1 : 1; first != (last+step); first+=step) 606 { 607 component_image->alpha_trait=BlendPixelTrait; 608 component_image->colormap[first].alpha=TransparentAlpha; 609 } 610 } 611 } 612 (void) SyncImage(component_image,exception); 613 artifact=GetImageArtifact(image,"connected-components:verbose"); 614 if ((IsStringTrue(artifact) != MagickFalse) || 615 (objects != (CCObjectInfo **) NULL)) 616 { 617 /* 618 Report statistics on unique object. 619 */ 620 for (i=0; i < (ssize_t) component_image->colors; i++) 621 { 622 object[i].bounding_box.width=0; 623 object[i].bounding_box.height=0; 624 object[i].bounding_box.x=(ssize_t) component_image->columns; 625 object[i].bounding_box.y=(ssize_t) component_image->rows; 626 object[i].centroid.x=0; 627 object[i].centroid.y=0; 628 object[i].area=0; 629 } 630 component_view=AcquireVirtualCacheView(component_image,exception); 631 for (y=0; y < (ssize_t) component_image->rows; y++) 632 { 633 register const Quantum 634 *magick_restrict p; 635 636 register ssize_t 637 x; 638 639 if (status == MagickFalse) 640 continue; 641 p=GetCacheViewVirtualPixels(component_view,0,y, 642 component_image->columns,1,exception); 643 if (p == (const Quantum *) NULL) 644 { 645 status=MagickFalse; 646 continue; 647 } 648 for (x=0; x < (ssize_t) component_image->columns; x++) 649 { 650 size_t 651 id; 652 653 id=GetPixelIndex(component_image,p); 654 if (x < object[id].bounding_box.x) 655 object[id].bounding_box.x=x; 656 if (x > (ssize_t) object[id].bounding_box.width) 657 object[id].bounding_box.width=(size_t) x; 658 if (y < object[id].bounding_box.y) 659 object[id].bounding_box.y=y; 660 if (y > (ssize_t) object[id].bounding_box.height) 661 object[id].bounding_box.height=(size_t) y; 662 object[id].centroid.x+=x; 663 object[id].centroid.y+=y; 664 object[id].area++; 665 p+=GetPixelChannels(component_image); 666 } 667 } 668 for (i=0; i < (ssize_t) component_image->colors; i++) 669 { 670 object[i].bounding_box.width-=(object[i].bounding_box.x-1); 671 object[i].bounding_box.height-=(object[i].bounding_box.y-1); 672 object[i].centroid.x=object[i].centroid.x/object[i].area; 673 object[i].centroid.y=object[i].centroid.y/object[i].area; 674 } 675 component_view=DestroyCacheView(component_view); 676 qsort((void *) object,component_image->colors,sizeof(*object), 677 CCObjectInfoCompare); 678 if (objects == (CCObjectInfo **) NULL) 679 { 680 (void) fprintf(stdout, 681 "Objects (id: bounding-box centroid area mean-color):\n"); 682 for (i=0; i < (ssize_t) component_image->colors; i++) 683 { 684 char 685 mean_color[MagickPathExtent]; 686 687 if (status == MagickFalse) 688 break; 689 if (object[i].area < MagickEpsilon) 690 continue; 691 GetColorTuple(&object[i].color,MagickFalse,mean_color); 692 (void) fprintf(stdout, 693 " %.20g: %.20gx%.20g%+.20g%+.20g %.1f,%.1f %.20g %s\n",(double) 694 object[i].id,(double) object[i].bounding_box.width,(double) 695 object[i].bounding_box.height,(double) object[i].bounding_box.x, 696 (double) object[i].bounding_box.y,object[i].centroid.x, 697 object[i].centroid.y,(double) object[i].area,mean_color); 698 } 699 } 700 } 701 if (objects == (CCObjectInfo **) NULL) 702 object=(CCObjectInfo *) RelinquishMagickMemory(object); 703 else 704 *objects=object; 705 return(component_image); 706} 707