Finden Sie die Ecken eines Polygons durch eine Region Maske dargestellt

Question

  

BW = poly2mask(x, y, m, n) berechnet ein   binäre Region of Interest (ROI) Maske,   BW, von einem ROI Polygon, vertreten   durch die Vektoren x und y. Die Größe des BW   ist m-mal-n.

     

poly2mask setzt Pixel in BW   sind, die innerhalb des Polygons (X, Y) bis 1   und setzt Pixel außerhalb des Polygons   0.

Problem: Bei einer solchen binären Maske BW eines konvexen Vierecks, was wäre der effizienteste Weg, um die vier Ecken zu bestimmen?

z. B.

Beste Lösung so weit: Verwenden edge die Begrenzungslinien zu finden, die die Hough-Transformation, die 4 Zeilen in dem Kantenbild zu finden und dann die Schnittpunkte dieser Linien finden oder 4 einen Eckendetektor auf dem Kantenbild verwenden. Scheint kompliziert, und ich kann nicht eine einfachere Lösung gibt es da draußen helfen fühlen.

Btw, convhull kehrt nicht immer 4 Punkte (vielleicht kann jemand qhull Optionen lassen vermuten, dass zu verhindern): es auch ein paar Punkte entlang der Kanten zurück

.

EDIT: Amro Antwort scheint recht elegant und effizient. Aber es könnte mehrere „Ecken“ an jeder realen Ecke sein, da die Spitzen nicht eindeutig sind. Ich konnte sie Cluster basierend auf θ und der Mittelwert der „Ecken“ um eine echte Ecke, aber das Hauptproblem ist die Verwendung von order(1:10).

Ist 10 genug für alle Ecken zur Verantwortung gezogen oder wird zu einer echten Ecke eine „Ecke“ dies ausschließen?

Answer 1

Dies ist etwas ähnlich wie @AndyL vorgeschlagen. Allerdings verwende ich die Grenze Signatur in Polarkoordinaten anstelle der Tangente.

Beachten Sie, dass ich zunächst die Kanten zu extrahieren, die Grenze bekommen, dann ist es zur Unterzeichnung zu konvertieren. Schließlich finden wir die Punkte auf der Grenze, die am weitesten vom Schwerpunkt sind, bilden diese Punkte die gefundenen Ecken. (Alternativ können wir auch für Ecken Spitzen in der Unterschrift erkennen).

Hier finden Sie eine vollständige Implementierung:

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: Als Reaktion auf Jakobs Kommentar möchte ich erklären, dass ich die Spitzen in der Unterschrift unter Verwendung eines ersten / zweiten Ableitungen zuerst zu finden versucht, aber am Ende die am weitesten N-Punkte nehmen. 10 war nur ein Ad-hoc-Wert, und wäre schwer zu verallgemeinern (Ich habe versucht, 4 gleiche wie Anzahl der Ecken nehmen, aber es hat nicht alle von ihnen decken). Ich denke, die Idee, sich von Clustern um Duplikate zu entfernen lohnt einen Blick in.

Soweit ich das sehe, war das Problem mit dem ersten Ansatz, dass, wenn Sie Grundstück rho ohne θ berücksichtigt, werden Sie eine andere Form bringen (nicht die gleichen Peaks), da die Geschwindigkeit durch die Spuren wir die Grenze unterschiedlich und hängt von der Krümmung. Wenn wir herausfinden können, wie man normalisiert , die Wirkung, können wir genauere Ergebnisse erhalten Derivaten.

Answer 2

Wenn Sie die Image Processing Toolbox haben, gibt es eine Funktion namens cornermetric , die einen Harris Eckendetektor oder Shi und Tomasi des Mindesteigenwert-Methode implementieren können. Diese Funktion ist seit Version 6.2 der Bildverarbeitung Toolbox (MATLAB Version R2008b) präsent.

Mit dieser Funktion kam ich mit einem etwas anderen Ansatz aus den anderen Antworten auf. Die nachstehende Lösung liegt der Gedanke zugrunde, dass eine kreisförmige Fläche an jedem „true“ Eckpunkt zentriert wird das Polygon um einen kleineren Betrag als eine kreisförmige Fläche über einen fehlerhaften Eckpunkts zentriert überlappen, die tatsächlich auf der Kante ist. Diese Lösung kann auch Fälle behandeln, in denen mehrere Punkte an der gleichen Ecke erkannt ...

Der erste Schritt ist, um die Daten zu laden:

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

Als nächstes berechnen die Ecke Metrik cornermetric . Beachten Sie, dass ich Maskierung der Ecke Metrik durch das ursprüngliche Polygon, so dass wir für die Eckpunkte suchen, sind innen das Polygon (das heißt zu versuchen, die Eckpixeln des Polygons zu finden). imregionalmax wird dann verwendet, um die lokalen Maxima zu finden. Da Sie Cluster von mehr als 1 Pixel mit der gleichen Ecke Metrik haben, füge ich dann Rauschen auf die Maxima und recompute so, dass ich nur 1 Pixel in jedem maximalen Bereich erhalten. Jede maximale Region wird dann markiert mit 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);

Die markierten Bereiche werden dann erweitert (mit imdilate ) mit ein scheibenförmiges Strukturelement (erstellt unter Verwendung strel ):

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

Nun, da die markierten Eckbereichen erweitert worden sind, werden sie teilweise das ursprüngliche Polygon überlappen. Regionen auf einer Kante des Polygons werden etwa 50% Überdeckung aufweisen, während Regionen, die an einer Ecke sind, werden etwa 25% Überdeckung aufweisen. Die Funktion regionprops verwendet werden können, um die Überlappungsbereiche für jeden zu finden Region bezeichnet, und die 4 Regionen, die die geringste Menge an Überlappung aufweisen können somit als die wahren Ecken betrachtet:

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

Und wir können nun die Pixelkoordinaten der Ecken erhalten mit find und 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');

Und hier ist ein Test mit einem rautenförmigen Bereich:

Answer 3

Ich mag dieses Problem lösen, indem sie mit einer Grenze arbeiten, weil es diese aus einem 2D-Problem zu einem 1D-Problem reduziert.

Mit bwtraceboundary() von der Bildverarbeitungs Toolkit eine Liste von Punkten an der Grenze zu extrahieren. Dann wandelt die Grenze in eine Reihe von Tangentenvektoren (es gibt eine Reihe von Möglichkeiten, dies zu tun, wäre ein Weg sein, die subrtact ith Punkt entlang der Grenze vom i+deltath Punkt.) Sobald Sie eine Liste von Vektoren haben, nehmen Sie das Skalarprodukt von benachbarten Vektoren. Die vier Punkte mit den kleinsten Punktprodukte sind Ihre Ecken!

Wenn Sie Ihren Algorithmus auf Polygone mit einer abritrary Anzahl der Ecken arbeiten möchten, dann suchen Sie einfach für Punktprodukte, die eine bestimmte Anzahl von Standardabweichungen unterhalb des Medians Skalarprodukt sind.

Answer 4

Ich beschloss, einen Harris Eckendetektor (hier ein mehr formale Beschreibung ), um die Ecken zu erhalten. Dies kann wie folgt implementiert werden:

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

Hier ist das Problem mit mehreren Ecken dank Gauß-Windowing-Funktion, die die Intensitätsänderung glättet. Unten ist eine vergrößerte Version einer Ecke mit dem hot colormap.

Answer 5

Hier ist ein Beispiel mit Ruby und HornetsEye . Im Grunde genommen erzeugt das Programm ein Histogramm der quantisierten Sobel Gradientenausrichtung dominant Orientierungen zu finden. Wenn vier dominanten Ausrichtungen gefunden werden, werden Linien angebracht, und die Schnittpunkte zwischen benachbarten Linien angenommen werden die Ecken des projizierten Rechteck sein.

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