영역 마스크로 표시되는 다각형의 모서리 찾기

Question

BW = poly2mask(x, y, m, n) 벡터 x 및 y로 표시되는 ROI 다각형에서 이진 영역 (ROI) 마스크 BW를 계산합니다.BW의 크기는 m-by-n입니다.

poly2mask 다각형 (x, y) 내부에있는 BW로 픽셀을 설정하고 다각형 외부의 픽셀을 0으로 설정합니다.

문제:그러한 바이너리 마스크가 주어지면 BW 볼록 사각형의 네 모서리를 결정하는 가장 효율적인 방법은 무엇입니까?

예:

지금까지 최고의 솔루션:사용 edge 경계선을 찾으려면 Hough 변환을 통해 가장자리 이미지에서 4개 선을 찾은 다음 해당 4개 선의 교차점을 찾거나 가장자리 이미지에서 코너 감지기를 사용합니다.복잡해 보이고, 더 간단한 해결책이 있다는 느낌을 지울 수 없습니다.

그런데, convhull 항상 4점을 반환하지는 않습니다(누군가 제안할 수 있음). qhull 이를 방지하기 위한 옵션):가장자리를 따라 몇 개의 점도 반환합니다.

편집하다: 암로의 답변 꽤 우아하고 효율적인 것 같습니다.그러나 정점이 고유하지 않기 때문에 각 실제 모서리에는 여러 개의 "모서리"가 있을 수 있습니다.다음을 기반으로 클러스터링할 수 있습니다. θ 실제 모퉁이 주변의 "모서리"를 평균화하지만 주요 문제는 다음을 사용하는 것입니다. order(1:10).

~이다 10 모든 모서리를 설명하기에 충분합니까? 아니면 실제 모서리의 "모서리"가 제외됩니까?

Answer 1

이거랑 좀 비슷한데 @앤디L 제안했습니다.그러나 나는 접선 대신 극좌표에서 경계 서명을 사용하고 있습니다.

먼저 가장자리를 추출하고 경계를 얻은 다음 이를 서명으로 변환합니다.마지막으로 중심에서 가장 멀리 있는 경계의 점을 찾습니다. 이러한 점은 발견된 모서리를 구성합니다.(또는 모서리의 시그니처에서 피크를 감지할 수도 있습니다).

다음은 완전한 구현입니다.

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

---

편집하다:Jacob의 의견에 대한 응답으로 처음에는 1차/2차 도함수를 사용하여 서명에서 최고점을 찾으려고 시도했지만 결국 가장 먼 N 포인트를 사용하게 되었음을 설명해야 합니다.10은 임시 값일 뿐이며 일반화하기 어려울 것입니다(모서리 수와 동일한 4개를 시도했지만 모두 포함하지는 않았습니다).중복을 제거하기 위해 클러스터링하는 아이디어는 살펴볼 가치가 있다고 생각합니다.

내가 보기에 첫 번째 접근 방식의 문제점은 다음과 같습니다. rho 복용하지 않고 θ 이를 고려하면 (동일한 피크가 아닌) 다른 모양을 얻게 됩니다. 속도 경계를 추적하는 방식은 다르며 곡률에 따라 다릅니다.우리가 방법을 알아낼 수 있다면 정규화하다 그 효과로 우리는 도함수를 사용하여 더 정확한 결과를 얻을 수 있습니다.

Answer 2

당신이 가지고 있다면 이미지 처리 도구 상자, 라는 함수가 있습니다. cornermetric Harris 코너 검출기 또는 Shi와 Tomasi의 최소 고유값 방법을 구현할 수 있습니다.이 함수는 Image Process Toolbox 버전 6.2(MATLAB 버전 R2008b)부터 제공되었습니다.

이 기능을 사용하여 다른 답변과 약간 다른 접근 방식을 생각해 냈습니다.아래 솔루션은 각 "실제" 모서리 점을 중심으로 하는 원형 영역이 실제로 가장자리에 있는 잘못된 모서리 점 위에 중심을 둔 원형 영역보다 작은 양만큼 다각형과 겹친다는 아이디어를 기반으로 합니다.이 솔루션은 동일한 모서리에서 여러 점이 감지되는 경우도 처리할 수 있습니다.

첫 번째 단계는 데이터를 로드하는 것입니다.

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

다음으로 다음을 사용하여 코너 측정항목을 계산합니다. cornermetric.원래 다각형으로 모서리 측정항목을 마스크하여 다음과 같은 모서리 점을 찾고 있습니다. 내부에 다각형(예:다각형의 모서리 픽셀을 찾으려고 합니다.) imregionalmax 그런 다음 로컬 최대값을 찾는 데 사용됩니다.동일한 모서리 측정항목을 사용하여 1픽셀보다 큰 클러스터를 가질 수 있으므로 최대값에 노이즈를 추가하고 각 최대값 영역에서 1픽셀만 얻도록 다시 계산합니다.그런 다음 각 최대 영역은 다음을 사용하여 레이블이 지정됩니다. 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);

그런 다음 레이블이 지정된 영역이 확장됩니다(사용하여 imdilate) 디스크 모양의 구조 요소(다음을 사용하여 생성됨) strel):

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

이제 레이블이 지정된 모서리 영역이 확장되었으므로 원래 다각형과 부분적으로 겹칩니다.다각형 가장자리에 있는 영역은 약 50% 겹치는 반면 모서리에 있는 영역은 약 25% 겹칩니다.함수 regionprops 라벨이 붙은 각 영역에 대해 겹치는 부분을 찾는 데 사용할 수 있으며, 따라서 겹치는 부분이 가장 적은 4개 영역을 실제 모서리로 간주할 수 있습니다.

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

이제 다음을 사용하여 모서리의 픽셀 좌표를 얻을 수 있습니다. find 그리고 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');

다음은 다이아몬드 모양 영역을 사용한 테스트입니다.

Answer 3

경계로 작업 하여이 문제를 해결하고 싶습니다.이 문제는 2D 문제에서 1D 문제로 줄어 듭니다.

사용 bwtraceboundary() 이미지 처리 툴킷에서 경계에서 점 목록을 추출합니다. 그런 다음 경계를 일련의 탄젠트 벡터로 변환합니다 (이를 수행하는 방법에는 여러 가지가 있습니다. 한 가지 방법은iTh는 경계를 따라 가리 킵니다 i+delta벡터 목록이 있으면 인접한 벡터의 도트 제품을 가져 가면됩니다. 가장 작은 도트 제품이있는 4 점은 코너입니다!

알고리즘이 연마 수의 정점이있는 다각형에서 작업하기를 원한다면 중간 점 제품 아래의 특정 표준 편차 인 DOT 제품을 검색하십시오.

Answer 4

나는 사용하기로 결정했다 해리스 코너 탐지기 (여기 a 보다 공식적인 설명) 모서리를 얻습니다. 다음과 같이 구현할 수 있습니다.

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

여기에서는 강도 변화를 부드럽게하는 가우스 윈도우 기능 덕분에 여러 구석에 문제가 있습니다. 아래는 코너의 확대 버전입니다. hot Colormap.

Answer 5

다음은 Ruby를 사용하는 예입니다 Hornetseye. 기본적 으로이 프로그램은 지배적 인 방향을 찾기 위해 양자화 된 솜 그라디언트 방향의 히스토그램을 만듭니다. 4 개의 지배적 방향이 발견되면 선이 장착되고 인접한 선 사이의 교차점은 투사 된 사각형의 모서리로 가정됩니다.

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