Binary Image, Concentrations of White Dots with OpenCV

Question

Given a binary image of black, with a few sporadic white dots, I'm looking for a way to "lasso" a majority of the white dots inside a bounding rectangle. Consider this image:

See how not all of the dots are enclosed, but just the clusters (or set of clusters) where there are clearly more white dots than anywhere else?

I already know how to put a bounding box around all of the white dots with OpenCV. Can anyone direct me as to how I can analyze this image for one big concentration of dots, ignoring any peripheral dots which are not really part of a group?

N.B.: This bounding box doesn't have to be skew. Even a convex hull would be nice as output.

I can adjust the size, color, alpha, location, density, etc. of these dots. So if your thoughts involve doing something with these dots in order to process them, that might work.

Answer 1

What you need is sort of a 1-cluster detection algorithm, where outlier detection is important. Clustering algorithms in general are designed and tuned to produce more than one cluster; a portion of them (k-means for example) do not even handle outliers. If you decide to use a real clustering algorithm, try DBSCAN and set it to detect 1 cluster - it has outlier detection ability.

Otherwise, you can consider your problem as a metric maximization problem.

You want a metric that is rewarded for data density, but also rewarded for box size (so you don't end up with a 1x1 box). I propose something along the lines of:

metric_to_maximize = White_Dot_Density * Area^x, where x is calibrated ad hoc.

Another idea that may work is to divide the image into m x n box-rectangles. Calculate each box's average density. Pick the top x% (or all rectangles that have density>threshold). Create a bounding box around these "good boxes" without including too much additional area.