Encontre os cantos de um polígono representado por uma máscara região

Question

BW = poly2mask(x, y, m, n) calcula um região binário de interesse (ROI) de máscara, BW, a partir de um polígono ROI, representado por os vetores x e y. O tamanho de BW é m-a-n.

poly2mask define pixels em BW que estão no interior do polígono (X, Y) para uma e conjuntos de pixels fora do polígono para 0.

Problema: Diante de tal BW máscara binária de um convexo quadrilátero, qual seria a maneira mais eficiente para determinar os quatro cantos?

por exemplo.,

Melhor Solução até agora: Use edge para encontrar as linhas delimitadoras, a transformada de Hough para encontrar as 4 linhas na imagem de ponta e, em seguida, encontrar os pontos de intersecção dessas 4 linhas ou usar um detector de cantos na imagem borda. Parece complicado, e eu não posso deixar de sentir que há uma solução mais simples lá fora.

Btw, convhull nem sempre voltar 4 pontos (talvez alguém pode sugerir opções qhull para evitar que.): Ele retorna alguns pontos ao longo das bordas bem

EDIT: do Amro resposta parece muito elegante e eficiente. Mas poderia haver vários "cantos" em cada canto real desde os picos não são exclusivos. Eu poderia agrupar-los com base em ? e a média dos "cantos" em torno de um canto real, mas o principal problema é o uso de order(1:10).

É 10 suficiente para conta para todos os cantos ou isso irá excluir um "canto" em um canto real?

Answer 1

Este é um pouco semelhante ao que @AndyL sugeriu. No entanto, eu estou usando a assinatura limite em coordenadas polares em vez da tangente.

Note que eu começar por extrair as bordas, ficando a fronteira, em seguida, convertê-lo para assinatura. Finalmente, encontramos os pontos da fronteira que estão mais afastados do centróide, esses pontos constituem os cantos encontrados. (Alternativamente, pode também detectar picos na assinatura para cantos).

A seguir é uma implementação completa:

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')

---

EDIT: Em resposta ao comentário de Jacob, devo explicar que eu primeiro tentou encontrar os picos na assinatura utilizando primeiro / segundo derivados, mas acabou levando os mais distantes N-pontos. 10 era apenas um valor ad-hoc, e seria difícil generalizar (Eu tentei tomar 4 mesmo que número de cantos, mas não cobrir todos eles). Eu acho que a idéia de agrupamento-los para remover duplicatas vale a pena olhar em.

No que diz respeito a meu ver, o problema com o 1º abordagem foi a de que se você traçar rho sem tomar θ em conta, você terá uma forma diferente (não o mesmo picos), uma vez que o velocidade por que traçamos o limite é diferente e depende da curvatura. Se pudéssemos descobrir como normalize esse efeito, podemos obter resultados mais precisos usando derivados.

Answer 2

Se você tem o Imagem Processing Toolbox , há uma função chamada cornermetric que pode implementar um detector de cantos de Harris ou método autovalor mínimo de Shi e Tomasi. Esta função está presente desde a versão 6.2 da Imagem Processing Toolbox (MATLAB versão R2008b).

Com esta função, eu vim com uma abordagem um pouco diferente das outras respostas. A solução abaixo baseia-se na ideia de que uma área circular centrada em cada "verdadeiro" ponto de canto irá sobrepor o polígono por uma quantidade mais pequena do que uma área circular centrada sobre um ponto de canto errada que é, na verdade, na borda. Esta solução também pode lidar com casos onde vários pontos são detectados na mesma esquina ...

O primeiro passo é carregar os dados:

rawImage = imread('oxyjj.png');
rawImage = rgb2gray(rawImage(7:473, 9:688, :));  % Remove the gray border
subplot(2, 2, 1);
imshow(rawImage);
title('Raw image');

Em seguida, calcular a métrica canto usando cornermetric . Note que estou mascarando o canto métrica pelo polígono original, de modo que estamos à procura de pontos de canto que são dentro do polígono (ou seja, tentando encontrar os pixels dos cantos do polígono). imregionalmax é então usada para encontrar os máximos locais. Desde que você pode ter grupos de mais de 1 pixel com o mesmo canto métrica, eu, em seguida, adicionar ruído aos valores máximos e recalcular para que eu só obter 1 pixel em cada região máxima. Cada região máxima é então rotulado usando 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);

As regiões marcadas são então dilatado (usando imdilate ) com um elemento de estruturação em forma de disco (criado usando strel ):

diskSize = 5;
dilatedImage = imdilate(labeledImage, strel('disk', diskSize));
subplot(2, 2, 2);
imshow(dilatedImage);
title('Dilated corner points');

Agora que as regiões de canto rotulados foram dilatados, eles se sobrepõem parcialmente o polígono originais. Regiões sobre uma borda do polígono terá cerca de 50% de sobreposição, enquanto que as regiões que se encontram no canto terá cerca de 25% de sobreposição. A função regionprops pode ser utilizado para encontrar as áreas de sobreposição para cada região marcada, e as 4 regiões que têm a menor quantidade de sobreposição pode, assim, ser considerados como os verdadeiros cantos:

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

E agora podemos obter as coordenadas de pixels dos cantos usando find e 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');

E aqui está um teste com uma região em forma de diamante:

Answer 3

Eu gosto de resolver este problema, trabalhando com um limite, porque reduz este a partir de um problema 2D para um problema 1D.

Use bwtraceboundary() do kit de ferramentas de processamento de imagem para extrair uma lista de pontos sobre a fronteira. Em seguida, converter a fronteira em uma série de vetores tangentes (há uma série de maneiras de fazer isso, uma maneira seria subrtact o ponto ith ao longo do limite do ponto i+deltath). Uma vez que você tem uma lista de vetores, levar o produto escalar de vetores adjacentes. Os quatro pontos com os produtos mais pequenos pontos são seus cantos!

Se você quiser que o seu algoritmo para trabalhar em polígonos com um número abritrary de vértices, em seguida, basta procurar produtos de ponto que são um certo número de desvios padrão abaixo o produto do ponto mediano.

Answer 4

Eu decidi usar um Harris detector canto (aqui está um descrição mais formal) para obter os cantos. Isso pode ser implementado da seguinte forma:

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

Aqui, o problema com vários cantos graças à função de janelas Gaussian que suaviza a mudança de intensidade. Abaixo, é uma versão ampliada de um canto com o colormap hot.

Answer 5

Aqui está um exemplo usando Ruby e HornetsEye . Basicamente, o programa cria um histograma da orientação gradiente de Sobel quantificado para encontrar orientações dominantes. Se quatro orientações dominantes são encontrados, as linhas são montados e os cruzamentos entre as linhas vizinhos são considerados os cantos do retângulo projetada.

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