Нахождение вершин для построения ограничивающего прямоугольника минимального размера / выпуклой оболочки

Question

У меня есть массив данных из изображения в градациях серого, из которого я сегментировал наборы смежных точек с определенным значением интенсивности.

В настоящее время я выполняю простую процедуру ограничивающего прямоугольника, где я нахожу минимальное и максимальное (х, у) [ряд, кол] точек. Это, очевидно, не дает наименьшего возможного прямоугольника, содержащего набор точек, который можно продемонстрировать простым вращением прямоугольника, чтобы самая длинная ось больше не выравнивалась с главной осью.

Что я должен сделать sh это найти ориентированный ограничивающий прямоугольник минимального размера. Это представляется возможным с использованием алгоритма, известного как вращающиеся штангенциркули, однако реализации этого алгоритма, похоже, основаны на идее, что у вас есть набор вершин для начала. Некоторые подробности об этом алгоритме: https://www.geometrictools.com/Documentation/MinimumAreaRectangle.pdf

Моя главная проблема заключается в поиске вершин в данных, которые у меня есть в настоящее время. Я считаю, что мне нужно, по крайней мере, найти подходящие вершины, чтобы уменьшить количество итераций, которые я выполняю, поскольку количество точек относительно велико, и обработка внутренних точек, как если бы они были вершинами, не нужна, если я могу найти способ не включайте их.

Вот некоторые примеры данных, с которыми я работаю:

Вот сегментированная сцена с использованием наивного алгоритма где он относительно хорошо сегментирует центральные объекты из-за того, что объекты в основном выровнены по осям изображения:

.

Красным цветом вы можете видеть текущие ограничивающие рамки, которые я рисую, используя 2 вершины: верхний левый и нижний правый углы групп точек, которые я нашел.

Поворотная часть - это то место, где мой текущий подход терпит неудачу, так как я определяю ограничивающий прямоугольник, используя только две точки все, что повернуто и не выровнено по оси, будет занимать гораздо большую площадь, чем необходимо для инкапсуляции точек.

Вот пример с повернутыми объектами в сцене:

Вот текущая производительность наивной сегментации на этой сцене, которая рисует больше, чем необходимо, рамок вокруг повернутых объектов:

В идеале результатом будут ограничивающие прямоугольники, выровненные по самой длинной оси сегментируемых точек, что я испытываю с трудностями при реализации.

Вот изображение, примерно показывающее, чего я действительно хочу достичь sh:

Вы также можете заметить ненужную сегментацию, выполненную в изображении вокруг границ, а также некоторые небольшие сегменты, которые должны быть удалены с некоторыми дальнейшими эвристиками, которые мне еще предстоит разработать. Я также был бы открыт для альтернативных предложений алгоритма сегментации, которые обеспечивают более надежное обнаружение интересующих меня объектов.

Я не уверен, что этот вопрос будет полностью ясен, поэтому я постараюсь уточнить если не очевидно, о чем я спрашиваю.

Answer 1

Уже поздно, но это все равно может помочь. Это то, что вам нужно сделать:

1. расширить пиксели, чтобы маленькие сегменты соединяли более крупные тела
2. найти связанные тела
3. выбрать образец пикселей из каждого тела
4. найти MBR ([ориентированный] минимальный ограничивающий прямоугольник) для выбранного набора

Для первого шага вы можете выполнить расширение . Это как-то похоже на кластеризацию DBSCAN . На шаге 3 вы можете просто выбрать случайные пиксели из равномерного распределения. Очевидно, что чем больше пикселей вы сохраняете, тем точнее будет 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

Вы также можете удалить некоторые неэффективные пиксели, используя дополнительные операции обработки и морфологические операции:

1. удалить отверстия
2. найти границы
3. найти скелет

В MATLAB:

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