Найти углы многоугольника, представленного областью маски

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

Используйте bwtraceboundary () из набор инструментов обработки изображений для извлечения списка точек на границе. Затем преобразуйте границу в серию касательных векторов (есть несколько способов сделать это, один из них - вычесть i -я точка вдоль границы от i + delta -й точки.) Когда у вас есть список векторов, возьмите скалярное произведение смежных векторов. Четыре точки с наименьшими скалярными произведениями - это ваши углы!

Если вы хотите, чтобы ваш алгоритм работал с полигонами с ограниченным числом вершин, просто ищите скалярные произведения, которые на определенное количество стандартных отклонений ниже среднего скалярного произведения .

I decided to use a Harris corner detector (here's a more formal description) to obtain the corners. This can be implemented as follows:

%% 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*');

Here, the problem with multiple corners thanks to Gaussian windowing function which smooths the intensity change. Below, is a zoomed version of a corner with the hot colormap.

Если у вас есть Image Processing Toolbox , есть функция, называемая cornermetric , которая может реализовать угловой детектор Харриса или метод минимальных собственных значений Ши и Томази. . Эта функция присутствует с версии 6.2 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');

Затем, вычислить угловую метрику с помощью угловой метрики . Обратите внимание, что я маскирую угловую метрику исходным многоугольником, так что мы ищем угловые точки, которые находятся внутри многоугольника (т.е. пытаемся найти угловые пиксели многоугольника). Затем 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');

А вот тест с областью в форме ромба:

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

#!/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