Trova gli angoli di un poligono rappresentato da una maschera regionale

Question

BW = poly2mask(x, y, m, n) Calcola una maschera binaria di interesse (ROI), BW, da un poligono ROI, rappresentata dai vettori X e Y.La dimensione di BW è m-by-n.

poly2mask Imposta pixel in BW che si trovano all'interno del poligono (x, y) a 1 e imposta pixel all'esterno del poligono su 0.

Problema:Data una maschera così binaria BW di un quadrilatero convesso, quale sarebbe il modo più efficiente per determinare i quattro angoli?

Per esempio.,

La migliore soluzione finora:Utilizzo edge per trovare le linee di delimitazione, la trasformazione di Hough per trovare le 4 linee nell'immagine del bordo e quindi trovare i punti di intersezione di quelle 4 linee o utilizzare un rilevatore di angoli sull'immagine del bordo.Sembra complicato e non posso fare a meno di pensare che esista una soluzione più semplice là fuori.

Comunque, convhull non sempre restituisce 4 punti (forse qualcuno può suggerire qhull opzioni per impedirlo):restituisce anche alcuni punti lungo i bordi.

MODIFICARE: La risposta di Amrò sembra piuttosto elegante ed efficiente.Ma potrebbero esserci più "angoli" in ogni angolo reale poiché i picchi non sono unici.Potrei raggrupparli in base a θ e mediare gli "angoli" attorno a un angolo reale, ma il problema principale è l'uso di order(1:10).

È 10 abbastanza per tenere conto di tutti gli angoli o questo escluderà un "angolo" in un angolo reale?

Answer 1

Questo è in qualche modo simile a cosa @AndyL suggerito.Tuttavia sto utilizzando la firma del confine in coordinate polari anziché in tangente.

Tieni presente che inizio estraendo i bordi, ottenendo il confine, quindi convertendolo in firma.Infine troviamo i punti sul confine più lontani dal baricentro, quei punti costituiscono gli angoli trovati.(In alternativa possiamo anche rilevare picchi nella segnatura degli angoli).

Quella che segue è un'implementazione 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')

---

MODIFICARE:In risposta al commento di Jacob, dovrei spiegare che prima ho provato a trovare i picchi nella firma utilizzando le derivate prime/seconde, ma alla fine ho preso gli N punti più lontani.10 era solo un valore ad hoc e sarebbe stato difficile generalizzare (ho provato a prendere 4 come numero di curve, ma non le copriva tutte).Penso che valga la pena esaminare l'idea di raggrupparli per rimuovere i duplicati.

Per quanto la vedo io, il problema con il primo approccio era che se tracciavi rho senza prendere θ in considerazione, otterrai una forma diversa (non gli stessi picchi), poiché il velocità con cui tracciamo il confine è diverso e dipende dalla curvatura.Se potessimo capire come farlo normalizzare In tal modo, possiamo ottenere risultati più accurati utilizzando i derivati.

Answer 2

Se avete la Image Processing Toolbox , c'è una funzione chiamata cornermetric che può implementare un rivelatore di angolo Harris o metodo autovalore minimo Shi e Tomasi di. Questa funzione è stata presente sin dalla versione 6.2 del Image Processing Toolbox (versione MATLAB R2008b).

Con questa funzione, mi si avvicinò con un approccio leggermente diverso dalle altre risposte. La soluzione qui di seguito si basa sull'idea che un'area circolare centrata in ogni "vero" punto angolo si sovrapporrà il poligono di una quantità più piccola di una zona circolare centrata su un punto angolo erronea che è in realtà sul bordo. Questa soluzione può anche gestire i casi in cui vengono rilevati più punti allo stesso angolo ...

Il primo passo è quello di caricare i dati:

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

Avanti, calcolare la metrica angolo utilizzando cornermetric . Si noti che sto mascherando l'angolo metrica dal poligono originale, in modo che siamo alla ricerca di punti d'angolo che sono all'interno il poligono (vale a dire cercando di trovare i pixel angolo del poligono). imregionalmax viene quindi utilizzato per trovare la massimi locali. Dal momento che si può avere gruppi di maggiore di 1 pixel con la stessa metrica angolo, ho quindi aggiungere rumore al massimo e recompute modo che ho solo 1 pixel in ogni regione massima. Ogni regione massima viene quindi all'etichetta 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);

Le regioni marcate vengono quindi dilatate (utilizzando imdilate ) con un elemento strutturante discoidale (creati utilizzando strel ):

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

Ora che le zone d'angolo marcati sono stati dilatati, si sovrappongono parzialmente il poligono originale. Regioni su un bordo del poligono avranno circa il 50% di sovrapposizione, mentre le regioni che si trovano su un angolo avranno circa il 25% di sovrapposizione. La funzione regionprops può essere utilizzato per trovare le aree di sovrapposizione per ogni regione etichettata e 4 regioni che hanno la minor quantità di sovrapposizione possono quindi essere considerate come veri angoli:

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 possiamo ora ottenere le coordinate dei pixel degli angoli utilizzando 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');

Ed ecco un test con una regione a forma di diamante:

Answer 3

mi piace risolvere questo problema lavorando con un confine, perché riduce questo da un problema 2D ad un problema 1D.

Usa bwtraceboundary() dal toolkit di elaborazione delle immagini per estrarre un elenco di punti sul perimetro. Poi convertire il confine in una serie di vettori tangenti (ci sono un certo numero di modi per farlo, in un modo sarebbe quello di subrtact il punto ith lungo il confine dal punto i+deltath.) Una volta che avete una lista di vettori, prendere il prodotto scalare di vettori adiacenti. I quattro punti con il più piccolo prodotto scalare sono le tue curve!

Se volete che il vostro algoritmo di lavorare su poligoni con un numero di abritrary di vertici, poi semplicemente cercare i prodotti di punti che sono un certo numero di deviazioni standard al di sotto del prodotto mediana dot.

Answer 4

ho deciso di utilizzare un Harris rilevatore angolo (ecco un descrizione più formale ) per ottenere gli angoli. Ciò può essere implementato come segue:

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

Qui, il problema con molteplici angoli grazie alla funzione di windowing gaussiana che leviga il cambiamento di intensità. Qui di seguito, è una versione ingrandita di un angolo con la mappa dei colori hot.

Answer 5

Ecco un esempio utilizzando Ruby e HornetsEye . Fondamentalmente il programma crea un istogramma della quantizzato orientamento del gradiente Sobel trovare orientamenti dominanti. Se vengono trovati quattro orientamenti dominanti, linee siano montate e le intersezioni tra linee adiacenti vengono considerati gli angoli del rettangolo proiettata.

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