Trouver les coins d'un polygone représenté par un masque de région

Question

  

BW = poly2mask(x, y, m, n) calcule une   région binaire d'intérêt (ROI) masque,   BW, d'un polygone de ROI, représenté   par les vecteurs x et y. La taille de BW   est m par n.

     

poly2mask fixe pixels dans BW   qui sont à l'intérieur du polygone (X, Y) à 1   et définit les pixels en dehors du polygone de   0.

Problème: Avec un tel BW de masque binaire d'un quadrilatère convexe, ce serait le moyen le plus efficace pour déterminer les quatre coins?

par exemple.

La meilleure solution à ce jour: Utilisez edge pour trouver les lignes de délimitation, la transformée de Hough pour trouver les 4 lignes de l'image de bord et ensuite trouver les points d'intersection de ces 4 lignes ou utiliser un détecteur d'angle sur l'image de bord. Semble compliqué, et je ne peux me sentir il y a une solution plus simple là-bas.

BTW, convhull ne retourne pas toujours 4 points (peut-être quelqu'un peut-il proposer des options de qhull pour éviter que): elle retourne quelques points le long des bords et

.

EDIT: réponse de Amro semble assez élégant et efficace. Mais il pourrait y avoir plusieurs « coins » à chaque coin réel puisque les pics ne sont pas uniques. Je pourrais les regrouper en fonction de θ et la moyenne des « coins » autour d'un véritable coin, mais le principal problème est l'utilisation de order(1:10).

est assez 10 pour tenir compte de tous les coins ou ce sera exclure un « coin » dans un coin réel?

Answer 1

est un peu semblable à ce que @AndyL suggéré. Cependant, je suis en utilisant la signature limite en coordonnées polaires au lieu de la tangente.

Notez que je commence par extraire les bords, obtenir la frontière, puis la convertir à la signature. Enfin, nous trouvons les points sur la frontière qui sont les plus éloignées du centre de gravité, ces points constituent les coins trouvés. (En variante on peut également détecter des pics dans la signature pour les coins).

Ce qui suit est une mise en œuvre complète:

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 réponse au commentaire de Jacob, je dois préciser que j'ai essayé de trouver les pics de la signature en utilisant les premiers dérivés / seconde, mais a fini par prendre les N-points les plus éloignés. 10 était juste une valeur ad hoc, et il serait difficile de généraliser (j'essayé de prendre 4 même que le nombre de coins, mais il ne couvre pas tous). Je pense que l'idée de les grouper pour supprimer les doublons mérite d'être étudiée.

Pour autant que je le vois, le problème avec la 1ère approche était que si vous intrigue rho sans prendre θ en compte, vous obtiendrez une forme différente (pas les mêmes pics), depuis le Vitesse par lequel on trace la frontière est différent et dépend de la courbure. Si nous pouvions comprendre comment Normaliser cet effet, nous pouvons obtenir des résultats plus précis en utilisant des dérivés.

Answer 2

Si vous avez le Image Processing Toolbox , il y a une fonction appelée cornermetric qui peut mettre en œuvre un détecteur d'angle Harris ou méthode de Shi valeur propre minimale et Tomasi. Cette fonction est présente depuis la version 6.2 de l'Image Processing Toolbox (version Matlab R2008b).

Cette fonction, je suis venu avec une approche légèrement différente des autres réponses. La solution ci-dessous sont basées sur l'idée selon laquelle une zone circulaire centrée à chaque point d'angle « true » chevauche le polygone en une quantité inférieure à une zone circulaire centrée sur un point d'angle erroné qui est en fait sur le bord. Cette solution peut également gérer les cas où plusieurs points sont détectés dans le même coin ...

La première étape consiste à charger les données:

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

Ensuite, calculer la métrique d'angle en utilisant cornermetric . Notez que je masquage le coin métrique par le polygone d'origine, de sorte que nous recherchons des points d'angle qui sont dans le polygone (à savoir essayer de trouver les pixels de coin du polygone). imregionalmax est ensuite utilisée pour trouver les maxima locaux. Étant donné que vous pouvez avoir des groupes de plus de 1 pixel avec la même métrique de coin, je puis ajouter du bruit au maximum et recalculées pour que je ne reçois 1 pixel dans chaque région maximale. Chaque région maximale est ensuite marqué à l'aide 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);

Les régions marquées sont ensuite dilatées (en utilisant imdilate ) avec un élément structurant en forme de disque (créé en utilisant strel ):

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

Maintenant que les régions d'angle marquées ont été dilatée, ils se recouvrent partiellement le polygone d'origine. Régions sur un bord du polygone auront un chevauchement d'environ 50%, tandis que les régions qui se trouvent sur un coin auront environ 25% de chevauchement. La fonction regionprops peut être utilisé pour trouver les zones de recouvrement pour chaque région marquée, et les 4 régions qui ont le moins de chevauchement peuvent donc être considérés comme les véritables angles:

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

Et nous pouvons maintenant obtenir les coordonnées de pixels des coins en utilisant find et 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');

Et voici un test avec une région en forme de diamant:

Answer 3

J'aime résoudre ce problème en travaillant avec une limite, car elle réduit ce d'un problème 2D à un problème 1D.

Utilisation bwtraceboundary() de la boîte à outils de traitement d'image pour extraire une liste de points sur la limite. Ensuite, convertir la frontière en une série de vecteurs tangents (il y a un certain nombre de façons de faire, d'une façon serait de la subrtact le point ith le long de la limite du point i+deltath.) Une fois que vous avez une liste de vecteurs, prendre le produit scalaire des vecteurs adjacents. Les quatre points avec les plus petits produits de points sont vos coins!

Si vous voulez que votre algorithme pour travailler sur des polygones avec un nombre abritrary de sommets, puis recherchez simplement des produits de points qui sont un certain nombre d'écarts-types au-dessous du produit médian point.

Answer 4

J'ai décidé d'utiliser un détecteur d'angle Harris (est ici description plus formelle ) pour obtenir les coins. Cela peut être mis en œuvre comme suit:

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

Ici, le problème avec plusieurs angles grâce à la fonction de fenêtrage gaussienne qui aplanit le changement d'intensité. Ci-dessous, une version agrandie d'un coin avec la palette de couleurs de hot.

Answer 5

Voici un exemple en utilisant Ruby et HornetsEye . Fondamentalement, le programme crée un histogramme de l'orientation du gradient Sobel pour trouver quantifiée orientations dominantes. Si quatre orientations dominantes se trouvent, les lignes sont montés et les intersections entre les lignes voisines sont supposés être les coins du rectangle projetée.

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