寻找用于构建最小尺寸边界框/凸包的顶点

Question

我有一组来自灰度图像的数据，我从中分割出具有特定强度值的连续点集。

目前我正在做一个简单的边界框例程，我在其中找到最小和最大 (x,y) [行，列] 点。这显然没有提供包含点集的最小可能框，只需旋转一个矩形即可证明最长的轴不再与主轴对齐。

我想做的是找到最小尺寸的定向边界框。这似乎可以使用称为旋转卡尺的算法，但是该算法的实现似乎依赖于您有一组顶点开始的想法。该算法的一些细节：https://www.geometrictools.com/Documentation/MinimumAreaRectangle.pdf

我的主要问题是在我当前拥有的数据中找到顶点。我相信我至少需要找到候选顶点以减少我正在执行的迭代次数，因为点的数量相对较大并且如果我能找到一种方法来处理内部点就好像它们是顶点是不必要的不包括它们。

这是我正在使用的一些示例数据：

这是使用朴素算法的分割场景，由于 objects 大部分与图像轴对齐，它相对较好地分割出中心 objects：

.

在红色部分，您可以看到我正在使用 2 个顶点绘制的当前边界框：我找到的点组的 top-left 和 bottom-right 个角。

旋转部分是我当前方法失败的地方，因为我只使用两个点定义边界框，任何旋转的而不是 axis-aligned 将占用比封装点所需的更多的区域。

这是场景中 objects 旋转的示例：

这是当前朴素分割在那个场景上的表现，它在旋转的 objects 周围绘制了比必要的更大的框：

理想情况下，边界框与被分割点的最长轴对齐，这是我在实现时遇到的问题。

这是一张大致显示我真正想要完成的图片：

您还可以注意到在边界周围的图像中进行了不必要的分割以及一些小片段，应该使用我尚未开发的一些进一步启发法将其删除。我也愿意接受替代的分割算法建议，这些建议可以更可靠地检测我感兴趣的 objects。

我不确定这个问题是否会完全清楚，因此我会尽力澄清我的问题是否不明显。

Answer 1

来晚了，但这可能仍有帮助。这是您需要做的：

扩展像素使小段连接较大的物体
找到连接的物体
select 每个物体的像素样本
find the MBR selected 集

第一步，您可以执行 dilation. It's somehow like DBSCAN 聚类。对于第 3 步，您可以简单地 select 来自均匀分布的随机像素。显然，保留的像素越多，MBR 就越准确。我在 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

您还可以使用更多的处理和形态学操作来删除一些无效像素：

remove holes
寻找界限
find skeleton

在 MATLAB 中：

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

寻找用于构建最小尺寸边界框/凸包的顶点

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

image-processing

geometry

computational-geometry

image-segmentation

bounding-box