Commit e202c9668 for imagemagick.org

commit e202c9668c991e73927eff4d5520a0bd11c78efa
Author: Artem Lytkin <146867384+4RH1T3CT0R7@users.noreply.github.com>
Date:   Sun Sep 27 16:24:41 2026 +0300

    track adjacent objects when merging connected components (#8978)

    for every object it merged, ConnectedComponentsImage cleared the census
    of all objects and then scanned all of them again to pick the adjacent
    object to merge into. with tens of thousands of objects the merge step
    was quadratic in the object count.

    the neighbors found while scanning the merged object's bounding box are
    now kept in a list, and only those are compared and reset. the choice
    is the same as before: the lowest id with the highest count, or 0 when
    there is no neighbor.

diff --git a/MagickCore/vision.c b/MagickCore/vision.c
index b03baf73e..ff0123b90 100644
--- a/MagickCore/vision.c
+++ b/MagickCore/vision.c
@@ -821,6 +821,7 @@ MagickExport Image *ConnectedComponentsImage(const Image *image,
     *equivalences;

   size_t
+    *neighbors,
     size;

   ssize_t
@@ -1407,6 +1408,14 @@ MagickExport Image *ConnectedComponentsImage(const Image *image,
   /*
     Merge any object not within the min and max area threshold.
   */
+  neighbors=(size_t *) AcquireQuantumMemory(component_image->colors+1,
+    sizeof(*neighbors));
+  if (neighbors == (size_t *) NULL)
+    {
+      object=(CCObjectInfo *) RelinquishMagickMemory(object);
+      component_image=DestroyImage(component_image);
+      ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
+    }
   component_view=AcquireAuthenticCacheView(component_image,exception);
   object_view=AcquireVirtualCacheView(component_image,exception);
   (void) SetCacheViewVirtualPixelMethod(object_view,TileVirtualPixelMethod);
@@ -1416,6 +1425,7 @@ MagickExport Image *ConnectedComponentsImage(const Image *image,
       bounding_box;

     size_t
+      count,
       id;

     ssize_t
@@ -1428,8 +1438,7 @@ MagickExport Image *ConnectedComponentsImage(const Image *image,
     /*
       Merge this object.
     */
-    for (j=0; j < (ssize_t) component_image->colors; j++)
-      object[j].census=0;
+    count=0;
     bounding_box=object[i].bounding_box;
     for (y=0; y < (ssize_t) bounding_box.height; y++)
     {
@@ -1478,7 +1487,11 @@ MagickExport Image *ConnectedComponentsImage(const Image *image,
               }
             j=(ssize_t) GetPixelIndex(component_image,q);
             if (j != i)
-              object[j].census++;
+              {
+                if (object[j].census == 0.0)
+                  neighbors[count++]=(size_t) j;
+                object[j].census++;
+              }
           }
         p+=(ptrdiff_t) GetPixelChannels(component_image);
       }
@@ -1487,9 +1500,13 @@ MagickExport Image *ConnectedComponentsImage(const Image *image,
       Merge with object of greatest adjacent area.
     */
     id=0;
-    for (j=1; j < (ssize_t) component_image->colors; j++)
-      if (object[j].census > object[id].census)
-        id=(size_t) j;
+    for (j=0; j < (ssize_t) count; j++)
+      if ((object[neighbors[j]].census > object[id].census) ||
+          ((object[neighbors[j]].census == object[id].census) &&
+           (neighbors[j] < id)))
+        id=neighbors[j];
+    for (j=0; j < (ssize_t) count; j++)
+      object[neighbors[j]].census=0.0;
     object[i].area=0.0;
     for (y=0; y < (ssize_t) bounding_box.height; y++)
     {
@@ -1520,6 +1537,7 @@ MagickExport Image *ConnectedComponentsImage(const Image *image,
   }
   object_view=DestroyCacheView(object_view);
   component_view=DestroyCacheView(component_view);
+  neighbors=(size_t *) RelinquishMagickMemory(neighbors);
   artifact=GetImageArtifact(image,"connected-components:mean-color");
   if (IsStringTrue(artifact) != MagickFalse)
     {
diff --git a/tests/validate.h b/tests/validate.h
index 1b37d7c16..12ff4a1d4 100644
--- a/tests/validate.h
+++ b/tests/validate.h
@@ -129,6 +129,7 @@ static const char
     "-crop 17x9+10+10",
     "-crop 60x70+10+10",
     "-cycle 200",
+    "-define connected-components:area-threshold=16 -connected-components 8",
     "-density 75x75 -resample 50x50",
     "-depth 7",
     "-depth 16",