Dışbükey olmayan bir poligonun köşe koordinatlarını saat yönünde düzenleyin MATLAB

Question

Hem dışbükey hem de dışbükey olmayan çokgenler içeren bazı resimlerim var. Her görüntü tam olarak bir çokgen içerir. Köşe koordinatlarını tespit etmem gerekiyor ve bunları saat yönünde veya saat yönünün tersine sıralamak gerekiyor. Dışbükey çokgenler için köşeleri tespit etmek için Harris corner detection ve noktaları sıralamak için convexhull kullanın. Ancak, dışbükey olmayan çokgenin nasıl sıralanacağına dair bir fikrim yok. Girişlerim görüntülendikçe, çokgenin kenarının yanında hareket ederek bunları sıralamakta yardımcı olabileceğini düşünüyorum. En az karmaşıklığı olan bir yolu var mı?

Örnek Resim: Ben rastgele köşeleri adında var

.

Beklenen çıkışı:

Ben Köşe bu düzenin 1 3 5 9 4 2 8 7 6 10 veya 1 10 6 7 8 2 4 9 5 3 koordinatlarını bekliyoruz. Sen mutlaka, herhangi bir noktada başlayabilir 1

Düzenleme 1: olmayan bazı dışbükey çokgen için olduğu kadar bütün dışbükey çokgen için çalışır rayryeng's çözümü, sonra bazı olmayan dışbükey çokgenler vardır

hangi onun algoritması ile iyi gitmiyor.

İşte Bu görüntü işlemede yaygın bir sorundur örneği

Answer 1

Başka bir yaklaşım, köşeleri kenarlarınızdan mesafelerine göre sıralamak için bwdistgeodesic'u kullanmaktır. Bu, sürekli bir kenar tespit edebileceğiniz herhangi bir çokgen için çalışmalıdır.

Biz yığın taşması gelen görüntüde yükleme başlamak ve siyah-beyaz görüntüye dönüştürerek daha kolay kenara bulmasını sağlamak bwmorph fonksiyon siyah işlemek için birçok seçenek sunar

A = imread('http://i.stack.imgur.com/dpbpP.jpg'); 
A_bw = im2bw(A,100/255); %binary image 
A_bw1 = imcomplement(A_bw); %inverted binary image 

ve beyaz görüntüler. Çokgenimizin kenarını bulmak için remove seçeneğini kullanacağız, ancak isterseniz başka bir kenar detektörü de kullanabilirsiniz.güzel bir açık sürekli kenar var,

%Find the edges 
A_edges = bwmorph(A_bw, 'remove'); 
[edge_x, edge_y] = find(A_edges'); 

en kenarları görselleştirmek edelim biz Tamam

figure; imshow(A_edges); 

algılandı. Şimdi köşeleri bulalım.

A_corners = corner(A_bw1, 'QualityLevel',.3); 

en

figure; imshow(A_bw1); 
hold on 
plot(A_corners(:,1), A_corners(:,2), 'r.', 'MarkerSize', 18) 
text(A_corners(:,1), A_corners(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24); 
hold off 

fark olmayabilir başka şey sipariş eden ilk köşe görselleştirmek edelim ben corner kullanır, ancak favori köşe dedektör yerine olabilir, bunlar doğrudan doğruya olmaması kenarlarda. Her köşe noktasına kenar boyunca en yakın noktayı bularak başlayacağım ve sonra köşeleri kırmızı ve en yakın kenar noktalarını yeşil olarak görselleştireceğim. Her köşe için kenar etrafında mesafeyi hesaplamak için

[~, ind] = min(pdist2(A_corners, [edge_x, edge_y]), [], 2); 
A_edge_corners = [edge_x(ind), edge_y(ind)]; 

figure; imshow(A_edges); 
hold on; 
plot(A_corners(:,1), A_corners(:,2), 'r.', 'MarkerSize', 18) 
plot(A_edge_corners(:,1), A_edge_corners(:,2),'g.', 'MarkerSize', 18) 
hold off; 

, biz köşe noktasının kendisi A_corners (kırmızı nokta yerine kenarında köşe noktası yaklaşım, A_edge_corners (yeşil nokta) kullanacağız).

Şimdi bwdistgeodesic'u kullanmamız için gereken tüm parçalara sahibiz. Bu işlev, siyah beyaz bir görüntüdeki sıfır olmayan piksellerin her biri için bir tohum noktasına olan mesafeyi bulur. İlk köşeden, her noktaya kadar olan mesafeyle ilgileniyoruz. Hadi deneyelim.

% Calculate distance from seed corner 
first_corner = A_edge_corners(1,:); 
D = bwdistgeodesic(A_edges, first_corner(1), first_corner(2)); 
figure; imagesc(D); 

Biz doğru en köşeden başlıyoruz ve piksel uzağa değerindeki köşe artışından hareketli. Ama bu bizim istediğimiz şey değil. Köşeleri bu değerleri kullanarak sipariş edersek, başlangıç ​​noktasından uzakta bir sipariş veririz.

[~, corner_order] = sort(D(sub2ind(size(D), A_edge_corners(:,2), A_edge_corners(:,1)))); 
A_corners_reorder1 = A_corners(corner_order, :); 

figure; imshow(A_bw1); 
hold on 
plot(A_corners_reorder1(:,1), A_corners_reorder1(:,2),'r.', 'MarkerSize', 18) 
text(A_corners_reorder1(:,1), A_corners_reorder1(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24); 
hold off 

Bu sorunu çözmek için, sadece sipariş yalnızca ilk noktadan tek yönde ilerler, böylece kenar kırmak zorunda. Saat yönünde veya saat yönünün tersine bir sıralamayla ilgileniyorsanız, kenarın yönüne bağlı olarak bir takım kurallara göre kenarı kırmanız gerekir. Yön önemli değilse, ilk köşeye bitişik bir piksel bulabilir ve oradaki kenarı kırabilirsiniz.

%Break the edge into one path by removing a pixel adjacent to first corner 
%If the corner is near the edge of the image, you would need to check for 
%edge conditions 
window = A_edges(first_corner(2)-1:first_corner(2)+1, first_corner(1)-1:first_corner(1)+1); 
window(2,2) = 0; %Exclude the corner itself 
[x, y] = find(window, 1); 
A_edges(first_corner(2)+x-2, first_corner(1)+y-2) = 0; 

figure; imshow(A_edges); 
hold on; 
plot(first_corner(1), first_corner(2), 'r.', 'MarkerSize', 18) 
hold off; 

Şimdi kenar boyunca ilk noktadan itibaren mesafe, sadece Bu bize kenarlarının istenen sipariş verir bir yol

%Find order the pixels along edge 
D = bwdistgeodesic(A_edges, first_corner(1), first_corner(2)); 
figure; imagesc(D); 

takip edebilir

[~, corner_order] = sort(D(sub2ind(size(D), A_edge_corners(:,2), A_edge_corners(:,1)))); 
A_corners = A_corners(corner_order, :); 

figure; imshow(A_bw1); 
hold on 
plot(A_corners(:,1), A_corners(:,2),'r.', 'MarkerSize', 18) 
text(A_corners(:,1), A_corners(:,2), strsplit(num2str(1:length(A_corners))), 'Color', 'g', 'FontSize', 24); 
hold off 

Bu yöntem, aynı zamanda, ikinci bir demo görüntü olarak ağırlık merkezi ile ilgili olarak, dengesiz çokgenler çalışır.

eğlence için, dengesiz bir çokgen daha net bir örnek olarak, ağırlık merkezi karşı tarafında bir köşe sahip üçüncü bir görüntü sunar. Benim yöntemim de bu resmi doğru şekilde ayrıştırıyor.

Answer 2

olduğunu. Tipik cevap, şeklin merkezini bulmak ve centroid ile her köşe noktası arasındaki açıyı bulmaktır. Açıların [0,360) derece arasında olacak şekilde temsil edildiğinden emin olursunuz. Bunu aldıktan sonra, türlerini ayarsınız, ardından puanların sırasını belirlemek için ortaya çıkan sırayı kullanın.

Sunulan görüntü, ön işlem öncesi biraz gerektirir, bu yüzden üzerinde çalışmaya başlayabilirim. Doğrudan görüntüde StackOverflow'tan okudum, sonra görüntüyü tersine çevirerek siyah yıldızın beyazlaşmasını sağlayın. Ayrıca sayıları kaldırmam gerekiyor, bu yüzden küçük metin alanlarını kaldırmak için bwareaopen kullanıyorum. Bu işlem tamamlandığında, corner aracılığıyla bu görüntü üzerinde bir köşe tespiti gerçekleştiririm ve QualityFactor değerini 0.3 olarak ayarladım, böylece 10 köşeyi algılayabilirim. Çok özel olarak:

%// Read image from StackOverflow 
im = rgb2gray(imread('http://i.stack.imgur.com/dpbpP.jpg')); 

%// Threshold the image and area open it 
im_thresh = im <= 100; 
im_open = bwareaopen(im_thresh, 50); 

%// Detect corner points 
out = corner(im_open, 'QualityLevel', 0.3); 

%// Show the image with the corner points 
imshow(im_open); 
hold on 
plot(out(:,1), out(:,2), 'r.') 

im_open bizim nihai işlenmiş bir resim içeriyor.

---

Şimdi, ağırlık noktasına bulalım: Bu ne alıyorum.Bu sadece her boyutun ortalama sıfır olmayan yerlerde koordinatlarını bulma ve bularak yapılabilir:

[rows, cols] = find(im_open); 
cenX = mean(cols); 
cenY = mean(rows); 

cenX ve cenY görüntünün sentroid (x,y) yerleri içerir. Sadece biz bunun doğru olduğundan emin olmak için:

imshow(im_open); 
hold on; 
plot(cenX, cenY, 'r.', 'MarkerSize', 18); 

Biz alıyorum:

Çok güzel. Şimdi, önceki kodda out, köşe noktalarının (x,y) noktalarını içerir. Yapmanız gereken tek şey centroid'den her köşe noktasına olan açıyı belirlemek ve daha sonra açıları sıralamak. Düzenlenmiş puanlarınızı vermek için köşe noktalarını yeniden düzenlemek için bu sıralama düzenini kullanırsınız. saat yönünde öğesini istiyorsanız, değerini düzenine göre sıralamanız gerekir. saat yönünün tersine'u istiyorsanız, sırasını azalan sırayla sıralamanız gerekir. Buna karar vermek istediğiniz şeyi size bırakacağım, ama ikisini de yapmanıza izin verecek bir kod yazacağım. Bu nedenle, sadece bunu:

%// Determine angles (in degrees) 
angles = atan2d(out(:,2) - cenY, out(:,1) - cenX); 

%// Any negative angles, add 360 degrees to convert to positive 
angles(angles < 0) = 360 + angles(angles < 0); 

%// Sort the angles 
[~,ind] = sort(angles); %// clockwise 
%[~,ind] = sort(angles, 'descend'); %// counter-clockwise 

%// Re-arrange the corner points to respect the order 
out_reorder = out(ind,:); 

Şimdi son test bu noktaları çizmek ve aynı zamanda biz doğru var olmadığını görmek için her noktanın yanında bir numara çizmektir.

Bana iyi görünüyor: Biz almak

%// Show image 
imshow(im_open); 
hold on; 
%// Show points 
plot(out_reorder(:,1), out_reorder(:,2), 'r.', 'MarkerSize', 18); 

%// Place a textbox at each point and show a sequence number 
for idx = 1 : size(out_reorder,1) 
    text(out_reorder(idx,1), out_reorder(idx,2), num2str(idx), 'FontSize', 24, 'Color', 'green'); 
end 

: That yapılabilir! Bu nedenle, out_reorder size köşe noktalarını verir, böylece saat yönünde veya saat yönünün tersi sırayla takip edilirler. Ardı arda karşılaştığınız her satır, doğal olarak saat yönünde veya aradığınız saat yönünün tersine takip eden bir sonraki noktayı size verir. Ayrıca, numaralamanın nerede başladığını da not edin. 0 açısı, merkeze göre doğuya işaret eden yatay bir çizgi ile tanımlanır. Bu nedenle, artan sıraya girerken 0'a en yakın nokta, 1 sayısını gördüğünüz yerdir. 1'den sonra, köşe noktaları tükenene kadar saat yönünde sırayla geldiğini görürsünüz.