ابحث عن زوايا المضلع الذي يمثله قناع المنطقة

Question

BW = poly2mask(x, y, m, n) يحسب قناع منطقة ثنائية من الاهتمام (ROI) ، BW ، من مضلع العائد على الاستثمار ، ويمثله المتجهات X و Y.حجم BW هو m-by-n.

poly2mask يضبط وحدات البكسل في BW الموجودة داخل المضلع (x ، y) إلى 1 ويضع بكسل خارج المضلع إلى 0.

مشكلة:ونظرا لمثل هذا القناع الثنائي BW في شكل رباعي محدب، ما هي الطريقة الأكثر فعالية لتحديد الزوايا الأربع؟

على سبيل المثال،

أفضل حل حتى الآن:يستخدم edge للعثور على الخطوط المحيطة، قم بتحويل هوغ للعثور على الخطوط الأربعة في صورة الحافة ثم ابحث عن نقاط التقاطع لتلك الخطوط الأربعة أو استخدم كاشف الزاوية على صورة الحافة.يبدو الأمر معقدًا، ولا يسعني إلا أن أشعر بوجود حل أبسط.

بالمناسبة، convhull لا يُرجع دائمًا 4 نقاط (ربما يمكن لأي شخص أن يقترح qhull خيارات لمنع ذلك):تقوم بإرجاع بضع نقاط على طول الحواف أيضًا.

يحرر: جواب عمرو يبدو أنيقًا وفعالًا للغاية.ولكن يمكن أن يكون هناك "زوايا" متعددة في كل زاوية حقيقية لأن القمم ليست فريدة من نوعها.يمكنني تجميعها على أساس θ ومتوسط ​​"الزوايا" حول زاوية حقيقية ولكن المشكلة الرئيسية هي استخدام order(1:10).

يكون 10 ما يكفي لمراعاة جميع الزوايا أم أن هذا سيستبعد "الزاوية" في الزاوية الحقيقية؟

Answer 1

هذا مشابه إلى حد ما لما @ آندي إل مقترح.ومع ذلك فأنا أستخدم التوقيع الحدودي في الإحداثيات القطبية بدلاً من الظل.

لاحظ أنني أبدأ باستخراج الحواف والحصول على الحدود ثم تحويلها إلى توقيع.وأخيرًا، نجد النقاط الموجودة على الحدود الأبعد عن المركز الأوسط، وتشكل تلك النقاط الزوايا الموجودة.(بدلاً من ذلك، يمكننا أيضًا اكتشاف القمم في توقيع الزوايا).

وفيما يلي التنفيذ الكامل:

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

---

يحرر:ردًا على تعليق جاكوب، يجب أن أوضح أنني حاولت أولاً العثور على القمم في التوقيع باستخدام المشتقات الأولى/الثانية، لكن انتهى بي الأمر بالحصول على أبعد نقاط N.كانت 10 مجرد قيمة مخصصة، وسيكون من الصعب تعميمها (حاولت أخذ 4 مثل عدد الزوايا، لكنها لم تغطيها جميعًا).أعتقد أن فكرة تجميعها لإزالة التكرارات تستحق النظر فيها.

بقدر ما أرى، كانت المشكلة في النهج الأول هي أنك إذا قمت بالتخطيط rho دون اتخاذ θ في الاعتبار، سوف تحصل على شكل مختلف (وليس نفس القمم)، منذ سرعة الذي من خلاله نرسم الحدود يختلف ويعتمد على الانحناء.إذا تمكنا من معرفة كيفية ذلك تطبيع بهذا التأثير، يمكننا الحصول على نتائج أكثر دقة باستخدام المشتقات.

Answer 2

إذا كان لديك صندوق أدوات معالجة الصور, ، هناك وظيفة تسمى cornermetric والتي يمكنها تنفيذ كاشف زاوية هاريس أو طريقة القيمة الذاتية الدنيا لشي وتوماسي.كانت هذه الوظيفة موجودة منذ الإصدار 6.2 من Image Processing Toolbox (إصدار 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 يمكن استخدامها للعثور على مناطق التداخل لكل منطقة مصنفة، وبالتالي يمكن اعتبار المناطق الأربع التي تحتوي على أقل قدر من التداخل هي الزوايا الحقيقية:

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

أحب حل هذه المشكلة من خلال العمل مع الحدود، لأنها تقلل من مشكلة ثنائية الأبعاد إلى مشكلة أحادية البعد.

يستخدم bwtraceboundary() من مجموعة أدوات معالجة الصور لاستخراج قائمة النقاط الموجودة على الحدود.ثم قم بتحويل الحدود إلى سلسلة من المتجهات المماسية (هناك عدة طرق للقيام بذلك، إحدى الطرق هي طرحiالنقطة ال على طول الحدود من i+deltaالنقطة الرابعة.) بمجرد حصولك على قائمة بالمتجهات، خذ حاصل الضرب النقطي للمتجهات المجاورة.النقاط الأربع مع أصغر المنتجات النقطية هي زواياك!

إذا كنت تريد أن تعمل الخوارزمية الخاصة بك على المضلعات ذات عدد عشوائي من الرؤوس، فما عليك سوى البحث عن منتجات النقاط التي تمثل عددًا معينًا من الانحرافات المعيارية أسفل حاصل الضرب النقطي المتوسط.

Answer 4

قررت استخدام أ كاشف زاوية هاريس (هنا أ وصف أكثر رسمية) للحصول على الزوايا.ويمكن تنفيذ ذلك على النحو التالي:

%% 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 و هورنتس آي.يقوم البرنامج بشكل أساسي بإنشاء رسم بياني لاتجاه التدرج الكمي Sobel للعثور على التوجهات السائدة.إذا تم العثور على أربعة اتجاهات سائدة، يتم تركيب الخطوط ويفترض أن التقاطعات بين الخطوط المتجاورة هي زوايا المستطيل المسقط.

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