Encuentra las esquinas de un polígono representado por una máscara región

Question

  

BW = poly2mask(x, y, m, n) calcula una   región binario de interés máscara (ROI),   BW, a partir de un polígono ROI, representada   por los vectores x e y. El tamaño de BW   es m-por-n.

     

poly2mask establece píxeles en BW   que están dentro del polígono (X, Y) a 1   y define los píxeles fuera del polígono a   0.

Problema: Teniendo en cuenta tales BW una máscara binaria de un cuadrilátero convexo, ¿cuál sería la forma más eficiente para determinar las cuatro esquinas?

por ejemplo.,

Mejor solución hasta el momento: Utilice edge para encontrar las líneas que delimitan, la transformada de Hough para encontrar las 4 líneas de la imagen de bordes y luego encontrar en los puntos de intersección de las líneas de 4 o utilizar un detector de esquina en la imagen de bordes. Parece complicado, y no puedo evitar la sensación de que hay una solución más simple que hay.

Por cierto, convhull no siempre devuelven 4 puntos (tal vez alguien puede sugerir opciones para evitar que qhull): devuelve un par de puntos a lo largo de los bordes, así

.

EDIT: de Amro respuesta parece bastante elegante y eficiente. Pero puede haber múltiples "esquinas" en cada esquina real, ya que los picos no son únicos. Podría agruparlas en base a θ y promediar las "esquinas" alrededor de una esquina real, pero el principal problema es el uso de order(1:10).

¿Es suficiente 10 dar cuenta de todas las esquinas o se presente excluir una "esquina" en una esquina real?

Answer 1

Esto es algo similar a lo que @AndyL sugerido. Sin embargo, yo estoy usando la firma límite en coordenadas polares en lugar de la tangente.

Tenga en cuenta que empiezo mediante la extracción de los bordes, para obtener el límite, a continuación, convirtiéndola en la firma. Por último nos encontramos con los puntos de la frontera que están más alejados del centro de gravedad, estos puntos constituyen las esquinas que se encuentran. (Alternativamente también podemos detectar picos en la firma para las esquinas).

La siguiente es una implementación 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: En respuesta al comentario de Jacob, debo explicar que probé por primera vez para encontrar los picos en la firma usando primeras segundas derivadas /, pero terminamos tomando los más lejanos N-puntos. 10 fue sólo un valor ad-hoc, y sería difícil generalizar (He intentado tomar 4 mismo que el número de esquinas, pero que no cubría todos ellos). Creo que la idea de agrupar a eliminar duplicados vale la pena examinar.

Por lo que veo, el problema con la primera aproximación fue que si parcela rho sin tomar θ en cuenta, obtendrá una forma diferente (no los mismos picos), ya que el velocidad mediante el cual se traza el límite es diferente y depende de la curvatura. Si pudiéramos encontrar la manera de normalizar en este sentido, podemos obtener resultados más precisos utilizando derivados.

Answer 2

Si usted tiene la Caja de herramientas de procesamiento de imágenes , hay una función llamada cornermetric que puede implementar un detector de esquina Harris o el método de valor propio mínimo de Shi y Tomasi. Esta función ha estado presente desde la versión 6.2 de la Imagen Processing Toolbox (versión de MATLAB R2008b).

Con esta función, se me ocurrió con un enfoque ligeramente diferente de las otras respuestas. La solución a continuación se basa en la idea de que un área circular con centro en cada una "verdadera" punto de esquina se superpondrá el polígono por una cantidad menor que un área circular centrado sobre un punto de esquina errónea de que es en realidad en el borde. Esta solución también puede manejar los casos en que se detectan varios puntos en la misma esquina ...

El primer paso es para cargar los datos:

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

A continuación, calcular la métrica de esquina utilizando cornermetric . Tenga en cuenta que estoy enmascaramiento de la esquina métrica por el polígono original, por lo que estamos buscando puntos de esquina que son dentro de el polígono (es decir, tratando de encontrar los píxeles de las esquinas del polígono). imregionalmax se utiliza a continuación para encontrar los máximos locales. Ya que puede tener grupos de más de 1 pixel con la misma métrica esquina, a continuación, añadir ruido a los máximos y Recompute de manera que solo me dan 1 píxel en cada región máxima. Cada región máxima se etiqueta a continuación, utilizando 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);

Las regiones marcadas se dilatan entonces (utilizando imdilate ) con un elemento estructurante en forma de disco (creada usando strel ):

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

Ahora que las zonas de las esquinas marcadas se han dilatado, que se superponen parcialmente el polígono originales. Regiones sobre una arista del polígono tendrán aproximadamente el 50% de solapamiento, mientras que las regiones que se encuentran en una esquina tendrán aproximadamente el 25% de solapamiento. La función regionprops se puede utilizar para encontrar las áreas de superposición para cada región de marcado, y las 4 regiones que tienen la menor cantidad de solapamiento de este modo pueden ser considerados como las esquinas verdaderas:

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

Y ahora podemos obtener las coordenadas en píxeles de las esquinas utilizando find y 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');

Y aquí está una prueba con una región en forma de diamante:

Answer 3

Me gusta resolver este problema mediante el trabajo con un límite, ya que reduce esto desde un problema en 2D a un problema 1D.

Uso bwtraceboundary() de la caja de herramientas de procesamiento de imágenes para extraer una lista de puntos de la frontera. A continuación, convertir la frontera en una serie de vectores tangentes (hay varias maneras de hacer esto, una forma sería la de la subrtact ith punto a lo largo de la frontera desde el punto i+deltath). Una vez que tenga una lista de vectores, tomar el producto escalar de los vectores adyacentes. Los cuatro puntos con los productos de punto más pequeños son sus esquinas!

Si usted quiere que su algoritmo para trabajar en polígonos con un número abritrary de vértices, entonces simplemente buscar productos escalares que son un cierto número de desviaciones estándar por debajo de la mediana de producto escalar.

Answer 4

decidí utilizar un Harris detector de esquina (aquí está un descripción más formal ) para obtener las esquinas. Esto se puede implementar de la siguiente manera:

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

Aquí, el problema con múltiples esquinas gracias a la función de ventanas de Gauss que suaviza el cambio de intensidad. A continuación, es una versión ampliada de una esquina con el mapa de colores hot.

Answer 5

Este es un ejemplo usando Ruby y HornetsEye . Básicamente, el programa crea un histograma de la orientación cuantificada gradiente de Sobel para encontrar orientaciones dominantes. Si se encuentran cuatro orientaciones dominantes, las líneas están equipados y las intersecciones entre las líneas vecinas se supone que son las esquinas del rectángulo proyectado.

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