Найдите углы многоугольника, представленного маской региона.
-
19-09-2019 - |
Вопрос
BW = poly2mask(x, y, m, n)
Вычисляет маску бинарной области интересов (ROI), BW, из многоугольника ROI, представленной векторами X и Y.Размер BW составляет M-By-N.
poly2mask
Устанавливает пиксели в BW, которые находятся внутри многоугольника (x, y) до 1 и устанавливают пиксели за пределами полигона до 0.
Проблема:Учитывая такую бинарную маску BW
Что касается выпуклого четырехугольника, какой самый эффективный способ определить четыре угла?
Например.,
Лучшее решение на данный момент:Использовать edge
чтобы найти ограничивающие линии, используйте преобразование Хафа, чтобы найти 4 линии на краевом изображении, а затем найдите точки пересечения этих четырех линий или используйте угловой детектор на краевом изображении.Кажется сложным, и я не могу избавиться от ощущения, что есть более простое решение.
Кстати, convhull
не всегда возвращает 4 балла (может кто подскажет qhull
варианты предотвращения этого):он также возвращает несколько точек по краям.
РЕДАКТИРОВАТЬ:
Ответ Амро выглядит довольно элегантно и эффективно.Но в каждом реальном углу может быть несколько «углов», поскольку пики не уникальны.Я мог бы сгруппировать их на основе θ и усреднять «углы» вокруг реального угла, но основная проблема заключается в использовании order(1:10)
.
Является 10
достаточно, чтобы учесть все углы, или это исключит «угол» в реальном углу?
Решение
Это чем-то похоже на то, что @ЭндиЛ предложенный.Однако я использую подпись границы в полярных координатах вместо касательной.
Обратите внимание, что я начинаю с извлечения краев, получения границы и последующего преобразования ее в подпись.Наконец, мы находим точки на границе, которые находятся дальше всего от центроида, эти точки составляют найденные углы.(В качестве альтернативы мы также можем обнаружить пики в сигнатуре углов).
Ниже приведена полная реализация:
I = imread('oxyjj.png');
if ndims(I)==3
I = rgb2gray(I);
end
subplot(221), imshow(I), title('org')
%%# Process Image
%# edge detection
BW = edge(I, 'sobel');
subplot(222), imshow(BW), title('edge')
%# dilation-erosion
se = strel('disk', 2);
BW = imdilate(BW,se);
BW = imerode(BW,se);
subplot(223), imshow(BW), title('dilation-erosion')
%# fill holes
BW = imfill(BW, 'holes');
subplot(224), imshow(BW), title('fill')
%# get boundary
B = bwboundaries(BW, 8, 'noholes');
B = B{1};
%%# boudary signature
%# convert boundary from cartesian to ploar coordinates
objB = bsxfun(@minus, B, mean(B));
[theta, rho] = cart2pol(objB(:,2), objB(:,1));
%# find corners
%#corners = find( diff(diff(rho)>0) < 0 ); %# find peaks
[~,order] = sort(rho, 'descend');
corners = order(1:10);
%# plot boundary signature + corners
figure, plot(theta, rho, '.'), hold on
plot(theta(corners), rho(corners), 'ro'), hold off
xlim([-pi pi]), title('Boundary Signature'), xlabel('\theta'), ylabel('\rho')
%# plot image + corners
figure, imshow(BW), hold on
plot(B(corners,2), B(corners,1), 's', 'MarkerSize',10, 'MarkerFaceColor','r')
hold off, title('Corners')
РЕДАКТИРОВАТЬ:В ответ на комментарий Джейкоба я должен объяснить, что сначала я пытался найти пики в сигнатуре, используя первую/вторую производную, но в итоге взял самые дальние N-точки.10 было всего лишь специальным значением, и его было бы трудно обобщить (я пытался взять 4 за количество углов, но оно не охватывало их все).Я думаю, что идея их кластеризации для удаления дубликатов заслуживает внимания.
Насколько я понимаю, проблема с первым подходом заключалась в том, что если вы построите график rho
не принимая θ
принимая во внимание, вы получите другую форму (не одинаковые пики), так как скорость по которому мы прослеживаем границу, различна и зависит от кривизны.Если бы мы могли придумать, как нормализовать Благодаря этому эффекту мы можем получить более точные результаты, используя производные.
Другие советы
Если у вас есть Панель инструментов обработки изображений, есть функция под названием cornermetric
который может реализовать угловой детектор Харриса или метод минимальных собственных значений Ши и Томази.Эта функция присутствует с версии 6.2 Image Processing Toolbox (версия MATLAB R2008b).
Используя эту функцию, я придумал подход, немного отличающийся от других ответов.Решение, приведенное ниже, основано на идее, что круглая область с центром в каждой «истинной» угловой точке будет перекрывать многоугольник на меньшую величину, чем круглая область с центром над ошибочной угловой точкой, которая фактически находится на краю.Это решение также может обрабатывать случаи, когда в одном и том же углу обнаружено несколько точек...
Первым шагом является загрузка данных:
rawImage = imread('oxyjj.png');
rawImage = rgb2gray(rawImage(7:473, 9:688, :)); % Remove the gray border
subplot(2, 2, 1);
imshow(rawImage);
title('Raw image');
Затем вычислите угловую метрику, используя cornermetric
.Обратите внимание, что я маскиру угловую метрику исходного многоугольника, чтобы мы искали угловые точки, которые внутри многоугольник (т.пытаюсь найти угловые пиксели многоугольника). imregionalmax
затем используется для поиска локальных максимумов.Поскольку у вас могут быть кластеры размером более 1 пикселя с одинаковой угловой метрикой, я затем добавляю шум к максимумам и пересчитываю так, чтобы получить только 1 пиксель в каждой максимальной области.Затем каждая максимальная область помечается с помощью bwlabel
:
cornerImage = cornermetric(rawImage).*(rawImage > 0);
maxImage = imregionalmax(cornerImage);
noise = rand(nnz(maxImage), 1);
cornerImage(maxImage) = cornerImage(maxImage)+noise;
maxImage = imregionalmax(cornerImage);
labeledImage = bwlabel(maxImage);
Затем меченые области расширяются (с использованием imdilate
) с дискообразным элементом структурирования (созданным с помощью strel
):
diskSize = 5;
dilatedImage = imdilate(labeledImage, strel('disk', diskSize));
subplot(2, 2, 2);
imshow(dilatedImage);
title('Dilated corner points');
Теперь, когда помеченные угловые области расширены, они будут частично перекрывать исходный многоугольник.Области на краю многоугольника будут перекрываться примерно на 50 %, а регионы, находящиеся на углах, — примерно на 25 %.Функция regionprops
может использоваться для поиска областей перекрытия для каждой помеченной области, и поэтому 4 области, которые имеют наименьшее количество перекрытия, могут рассматриваться как истинные углы:
maskImage = dilatedImage.*(rawImage > 0); % Overlap with the polygon
stats = regionprops(maskImage, 'Area'); % Compute the areas
[sortedValues, index] = sort([stats.Area]); % Sort in ascending order
cornerLabels = index(1:4); % The 4 smallest region labels
maskImage = ismember(maskImage, cornerLabels); % Mask of the 4 smallest regions
subplot(2, 2, 3);
imshow(maskImage);
title('Regions of minimal overlap');
И теперь мы можем получить пиксельные координаты углов, используя find
и ismember
:
[r, c] = find(ismember(labeledImage, cornerLabels));
subplot(2, 2, 4);
imshow(rawImage);
hold on;
plot(c, r, 'r+', 'MarkerSize', 16, 'LineWidth', 2);
title('Corner points');
А вот тест с ромбовидной областью:
Мне нравится решать эту проблему, работая с границей, потому что это сводит ее от 2D-задачи к 1D-задаче.
Использовать bwtraceboundary()
из набора инструментов обработки изображений, чтобы извлечь список точек на границе.Затем преобразуйте границу в серию касательных векторов (есть несколько способов сделать это, один из способов — вычестьi
Точка вдоль границы от i+delta
Эта точка.) Получив список векторов, возьмите скалярное произведение соседних векторов.Четыре точки с наименьшими скалярными произведениями — это ваши углы!
Если вы хотите, чтобы ваш алгоритм работал с многоугольниками с произвольным количеством вершин, просто найдите скалярные произведения, которые на определенное количество стандартных отклонений ниже медианного скалярного произведения.
Я решил использовать Угловой детектор Харриса (вот более формальное описание), чтобы получить углы.Это можно реализовать следующим образом:
%% Constants
Window = 3;
Sigma = 2;
K = 0.05;
nCorners = 4;
%% Derivative masks
dx = [-1 0 1; -1 0 1; -1 0 1];
dy = dx'; %SO code color fix '
%% Find the image gradient
% Mask is the binary image of the quadrilateral
Ix = conv2(double(Mask),dx,'same');
Iy = conv2(double(Mask),dy,'same');
%% Use a gaussian windowing function and compute the rest
Gaussian = fspecial('gaussian',Window,Sigma);
Ix2 = conv2(Ix.^2, Gaussian, 'same');
Iy2 = conv2(Iy.^2, Gaussian, 'same');
Ixy = conv2(Ix.*Iy, Gaussian, 'same');
%% Find the corners
CornerStrength = (Ix2.*Iy2 - Ixy.^2) - K*(Ix2 + Iy2).^2;
[val ind] = sort(CornerStrength(:),'descend');
[Ci Cj] = ind2sub(size(CornerStrength),ind(1:nCorners));
%% Display
imshow(Mask,[]);
hold on;
plot(Cj,Ci,'r*');
Здесь проблема с несколькими углами благодаря функции гауссова окна, которая сглаживает изменение интенсивности.Ниже представлена увеличенная версия угла с hot
цветовая карта.
Вот пример использования Ruby и ШершниГлаз.По сути, программа создает гистограмму квантовой ориентации градиента Собеля для поиска доминирующих ориентаций.Если найдены четыре доминирующие ориентации, линии подгоняются, а пересечения соседних линий считаются углами проецируемого прямоугольника.
#!/usr/bin/env ruby
require 'hornetseye'
include Hornetseye
Q = 36
img = MultiArray.load_ubyte 'http://imgur.com/oxyjj.png'
dx, dy = 8, 6
box = [ dx ... 688, dy ... 473 ]
crop = img[ *box ]
crop.show
s0, s1 = crop.sobel( 0 ), crop.sobel( 1 )
mag = Math.sqrt s0 ** 2 + s1 ** 2
mag.normalise.show
arg = Math.atan2 s1, s0
msk = mag >= 500
arg_q = ( ( arg.mask( msk ) / Math::PI + 1 ) * Q / 2 ).to_int % Q
hist = arg_q.hist_weighted Q, mag.mask( msk )
segments = ( hist >= hist.max / 4 ).components
lines = arg_q.map segments
lines.unmask( msk ).normalise.show
if segments.max == 4
pos = MultiArray.scomplex *crop.shape
pos.real = MultiArray.int( *crop.shape ).indgen! % crop.shape[0]
pos.imag = MultiArray.int( *crop.shape ).indgen! / crop.shape[0]
weights = lines.hist( 5 ).major 1.0
centre = lines.hist_weighted( 5, pos.mask( msk ) ) / weights
vector = pos.mask( msk ) - lines.map( centre )
orientation = lines.hist_weighted( 5, vector ** 2 ) ** 0.5
corner = Sequence[ *( 0 ... 4 ).collect do |i|
i1, i2 = i + 1, ( i + 1 ) % 4 + 1
l1, a1, l2, a2 = centre[i1], orientation[i1], centre[i2], orientation[i2]
( l1 * a1.conj * a2 - l2 * a1 * a2.conj -
l1.conj * a1 * a2 + l2.conj * a1 * a2 ) /
( a1.conj * a2 - a1 * a2.conj )
end ]
result = MultiArray.ubytergb( *img.shape ).fill! 128
result[ *box ] = crop
corner.to_a.each do |c|
result[ c.real.to_i + dx - 1 .. c.real.to_i + dx + 1,
c.imag.to_i + dy - 1 .. c.imag.to_i + dy + 1 ] = RGB 255, 0, 0
end
result.show
end