fast connected components implementation (with patch) (Patch #1236)

any reason this has been bumped / ignored?

Lack of resources... There are 45 more patches, most likely that they will be integrated in one of future versions. Sorry for that, we'll try to adopt your patch next time.

Hm, I was going to let this go till a future version but i have a few things worth mentioning:

A friend's work who intended on contributing hysteresis thresholding as a stand alone function waiting on this to make it in.

More importantly, this is still an unsolved problem for most users... cvbloblib et all are in disarray and sometimes broken. Current solutions are too complicated and slow as they are based on floodfill where as this is a constant time 2 pass algorithm. AFAIK it also comes up often on the ML from what I remember.

Take a look at these results, both posted long after I submitted my patch:
http://stackoverflow.com/questions/9291175/opencv-and-python-connected-components-analysis/10052376#10052376
http://nghiaho.com/?p=1102
http://areshopencv.blogspot.com/2011/12/blob-detection-connected-component-pure.html

Is there any thing I can do to expedite inclusion? I'm not against submitting more patches but I honestly think it's time opencv has this functionality built in.

Vadim, what is your opinion?

Hi, one more thread postiing I found today on stackoverflow that I should've posted before,

http://stackoverflow.com/questions/4641817/blob-extraction-in-opencv

You can see other users think its a rather surprising oversight for a library such as opencv.

+1

Reposting benchmarks with preformatting to preserve readability:

reaper (i7 3820, x86_64, gcc 4.6.3), -O2
     spiral1-big.png 4       1000   0.0000 111.3650 222.5280
         spiral1.png 4       1000   0.0000   7.0330  14.1660
   spiral1-small.png 4       1000   0.0000   0.2950   0.5980
     spiral2-big.jpg 4       1000   0.0000  32.9920  79.4010
         spiral2.jpg 4       1000   0.0000   0.5960   1.1360
   spiral2-small.jpg 4       1000   0.0000   0.1330   0.2730
       stuff-big.jpg 4       1000   0.0000  36.3200  93.7240
           stuff.jpg 4       1000   0.0000   0.6390   1.5160
     spiral1-big.png 8       1000 103.4610  77.1300 184.3070
         spiral1.png 8       1000   5.9270   4.9480  11.5160
   spiral1-small.png 8       1000   0.4770   0.2190   0.4740
     spiral2-big.jpg 8       1000  49.4940  26.9110  72.6570
         spiral2.jpg 8       1000   1.3150   0.3980   0.9550
   spiral2-small.jpg 8       1000   0.8260   0.1460   0.3370
       stuff-big.jpg 8       1000  48.8870  30.6580  86.3620
           stuff.jpg 8       1000   0.8930   0.5070   1.3710
reaper, -O3
     spiral1-big.png 4       1000   0.0000 110.7130 215.6300
         spiral1.png 4       1000   0.0000   7.0950  13.6260
   spiral1-small.png 4       1000   0.0000   0.3540   0.6170
     spiral2-big.jpg 4       1000   0.0000  32.9020  77.7780
         spiral2.jpg 4       1000   0.0000   0.4570   1.0110
   spiral2-small.jpg 4       1000   0.0000   0.1270   0.2880
       stuff-big.jpg 4       1000   0.0000  36.1840  91.7420
           stuff.jpg 4       1000   0.0000   0.5650   1.5810
     spiral1-big.png 8       1000 118.9170  77.0660 183.9130
         spiral1.png 8       1000   6.4080   4.9450  11.8380
   spiral1-small.png 8       1000   0.5010   0.2190   0.4810
     spiral2-big.jpg 8       1000  52.0180  26.8950  72.2840
         spiral2.jpg 8       1000   1.4720   0.3970   0.9370
   spiral2-small.jpg 8       1000   0.5930   0.1090   0.2430
       stuff-big.jpg 8       1000  51.6680  30.6020  86.4960
           stuff.jpg 8       1000   0.9620   0.5740   1.3500

spyker (core 2 duo, x86_64, gcc 4.6.3), -O3
     spiral1-big.png 4       1000    0.0000 216.9970 358.0390
         spiral1.png 4       1000    0.0000  13.5170  22.4210
   spiral1-small.png 4       1000    0.0000   0.5000   0.9370
     spiral2-big.jpg 4       1000    0.0000  70.7200 129.7390
         spiral2.jpg 4       1000    0.0000   0.8100   1.6770
   spiral2-small.jpg 4       1000    0.0000   0.2250   0.4490
       stuff-big.jpg 4       1000    0.0000  83.6310 155.5480
           stuff.jpg 4       1000    0.0000   0.9410   2.3050
     spiral1-big.png 8       1000  226.0340 156.2490 291.3120
         spiral1.png 8       1000   10.0530   9.5950  18.2160
   spiral1-small.png 8       1000    0.7030   0.3310   0.7450
     spiral2-big.jpg 8       1000   87.6270  58.3730 116.4080
         spiral2.jpg 8       1000    1.8560   0.6220   1.4930
   spiral2-small.jpg 8       1000    0.8580   0.1800   0.4010
       stuff-big.jpg 8       1000   94.7050  71.7530 142.8330

Building this patch on Windows using Visual Studio 2008 (against 2.4.2, not trunk) yields a lot of warnings of the following nature:

..\..\..\OpenCV-2.4.2\modules\imgproc\src\connectedcomponents.cpp(213) : warning C4127: conditional expression is constant

Additionally, the uint32_t, uint64_t, and int64_t types are not defined on Windows, so I would suggest using the OpenCV defined equivalents instead (unsigned int, int64, uint64). The python bindings for OpenCV do not seem to properly handle two functions that differ only by argument type, so you should either drop one of the exported functions, or name them differently. You should mark the statsv vector as CV_OUT as well.

The python bindings do not build properly, one needs to add appropriate conversion functions for your new structure to cv2.cpp.

typedef vector<ConnectedComponentStats> vector_ConnectedComponentStats;

static inline PyObject* pyopencv_from(const ConnectedComponentStats& c)
{
    return Py_BuildValue("{s:i,s:i,s:i,s:i,s:d,s:d,s:K,s:K,s:I}",
        "lower_x", c.lower_x, "lower_y", c.lower_y, 
        "upper_x", c.upper_x, "upper_y", c.upper_y,
        "centroid_x", c.centroid_x, "centroid_y", c.centroid_y,
        "integral_x", c.integral_x, "integral_y", c.integral_y,
        "area", c.area );
}

static inline PyObject* pyopencv_from(const vector_ConnectedComponentStats& c)
{
    return pyopencv_from_generic_vec(c);
}

Curiously, the python bindings don't properly support converting from uint64/int64, and casts them to a double instead. I'm not sure of the proper solution for that, but adding the following functions to cv2.cpp seems to allow your function to return a value properly:

static PyObject* pyopencv_from(int64 value)
{
    return PyLong_FromLongLong(value);
}

static PyObject* pyopencv_from(uint64 value)
{
    return PyLong_FromUnsignedLongLong(value);
}

Note that I haven't attached these in patch form because I'm not 100% sure of the best way to fix all of these issues, but the solutions detailed above seem to work for me.

Also, adding some documentation would be useful. At the very minimum, when one builds the documentation for OpenCV on a patched build your function doesn't show up in the docs.

Dustin,

I've fixed most of your issues. The warnings are a non-issue and I suggest you submit a patch to disable the warnings for that compiler if it concerns you.

I've also made a git repo from itsees branch on github and put in a pull-request. I figured it was better than the molasses speed of this issue tracker.

Jason Newton wrote:

I've also made a git repo from itsees branch on github and put in a pull-request. I figured it was better than the molasses speed of this issue tracker.

Sorry long and busy day, url:
https://github.com/nevion/opencv