Finding vertexes for construction of minimum size bounding box / convex hull

Question

I have an array of data from a grayscale image that I have segmented sets of contiguous points of a certain intensity value from.

Currently I am doing a naive bounding box routine where I find the minimum and maximum (x,y) [row, col] points. This obviously does not provide the smallest possible box that contains the set of points which is demonstrable by simply rotating a rectangle so the longest axis is no longer aligned with a principal axis.

What I wish to do is find the minimum sized oriented bounding box. This seems to be possible using an algorithm known as rotating calipers, however the implementations of this algorithm seem to rely on the idea that you have a set of vertices to begin with. Some details on this algorithm: https://www.geometrictools.com/Documentation/MinimumAreaRectangle.pdf

My main issue is in finding the vertices within the data that I currently have. I believe I need to at least find candidate vertices in order to reduce the amount of iterations I am performing, since the amount of points is relatively large and treating the interior points as if they are vertices is unnecessary if I can figure out a way to not include them.

Here is some example data that I am working with:

Here's the segmented scene using the naive algorithm, where it segments out the central objects relatively well due to the objects mostly being aligned with the image axes:

.

In red, you can see the current bounding boxes that I am drawing utilizing 2 vertices: top-left and bottom-right corners of the groups of points I have found.

The rotation part is where my current approach fails, as I am only defining the bounding box using two points, anything that is rotated and not axis-aligned will occupy much more area than necessary to encapsulate the points.

Here's an example with rotated objects in the scene:

Here's the current naive segmentation's performance on that scene, which is drawing larger than necessary boxes around the rotated objects:

Ideally the result would be bounding boxes aligned with the longest axis of the points that are being segmented, which is what I am having trouble implementing.

Here's an image roughly showing what I am really looking to accomplish:

You can also notice unnecessary segmentation done in the image around the borders as well as some small segments, which should be removed with some further heuristics that I have yet to develop. I would also be open to alternative segmentation algorithm suggestions that provide a more robust detection of the objects I am interested in.

I am not sure if this question will be completely clear, therefore I will try my best to clarify if it is not obvious what I am asking.

Answer 1

It's late, but that might still help. This is what you need to do:

1. expand pixels to make small segments connect larger bodies
2. find connected bodies
3. select a sample of pixels from each body
4. find the MBR ([oriented] minimum bounding rectangle) for selected set

For first step you can perform dilation. It's somehow like DBSCAN clustering. For step 3 you can simply select random pixels from a uniform distribution. Obviously the more pixels you keep, the more accurate the MBR will be. I tested this in MATLAB:

% import image as a matrix of 0s and 1s
oI = ~im2bw(rgb2gray(imread('vSb2r.png'))); % original image
% expand pixels
dI = imdilate(oI,strel('disk',4)); % dilated
% find connected bodies of pixels
CC = bwconncomp(dI);
L = labelmatrix(CC) .* uint8(oI); % labeled 
% mark some random pixels
rI = rand(size(oI))<0.3;
sI = L.* uint8(rI) .* uint8(oI); % sampled
% find MBR for a set of connected pixels
for i=1:CC.NumObjects
   [Y,X] = find(sI == i);
   mbr(i) = getMBR( X, Y );
end

You can also remove some ineffective pixels using some more processing and morphological operations:

1. remove holes
2. find boundaries
3. find skeleton

In MATLAB:

I = imfill(I, 'holes');
I = bwmorph(I,'remove');
I = bwmorph(I,'skel');