matlab - वितरित कण के साथ छवि में मुक्त क्षेत्र में सबसे बड़ा सर्कल फिटिंग




math image-processing (4)

मैं वितरित कणों वाले छवि के किसी भी मुक्त क्षेत्र में सबसे बड़े संभावित सर्कल का पता लगाने और फिट करने के लिए छवियों पर काम कर रहा हूं:

(कण के स्थान का पता लगाने में सक्षम)।

एक दिशा किसी भी 3-बिंदु संयोजन को छूने वाले सर्कल को परिभाषित करना है, यह जांचना कि यदि सर्कल खाली है, तो सभी खाली सर्कल के बीच सबसे बड़ा सर्कल ढूंढना है। हालांकि, यह संयोजन की एक बड़ी संख्या अर्थात C(n,3) , जहां n छवि में कणों की कुल संख्या है।

मैं सराहना करूंगा अगर कोई मुझे कोई संकेत या वैकल्पिक तरीका प्रदान कर सकता है जो मैं तलाश कर सकता हूं।


चलो कुछ मैथ्स करते हैं मेरे दोस्त, मैथ्स हमेशा के लिए खत्म हो जाएगा!

विकिपीडिया:

गणित में, एक वोरोनोई आरेख विमान के एक विशिष्ट सबसेट में बिंदुओं के आधार पर क्षेत्रों में एक विमान का विभाजन है।

उदाहरण के लिए:

rng(1)
x=rand(1,100)*5;
y=rand(1,100)*5;


voronoi(x,y);

इस आरेख के बारे में अच्छी बात यह है कि यदि आप नोटिस करते हैं, तो उन नीले क्षेत्रों के सभी किनारे / कोने सभी उनके साथ अंक के बराबर दूरी पर हैं। इस प्रकार, यदि हम लंबों के स्थान को जानते हैं, और निकटतम बिंदुओं के लिए दूरी की गणना करते हैं, तो हम सर्कल के केंद्र के रूप में उच्चतम दूरी के साथ शीर्ष चुन सकते हैं।

दिलचस्प बात यह है कि एक वोरोनोई क्षेत्रों के किनारों को एक डिलायुन ट्राइंगुलेशन द्वारा उत्पन्न त्रिकोण के परिधि के रूप में भी परिभाषित किया गया है।

तो अगर हम क्षेत्र के Delaunay त्रिकोणीय गणना करते हैं, और उनके परिधि

dt=delaunayTriangulation([x;y].');
cc=circumcenter(dt); %voronoi edges

और प्रत्येक त्रिभुज को परिभाषित करने वाले किसी भी बिंदु पर परिधि और बिंदुओं के बीच की दूरी की गणना करें:

for ii=1:size(cc,1)
    if cc(ii,1)>0 && cc(ii,1)<5 && cc(ii,2)>0 && cc(ii,2)<5
    point=dt.Points(dt.ConnectivityList(ii,1),:); %the first one, or any other (they are the same distance)
    distance(ii)=sqrt((cc(ii,1)-point(1)).^2+(cc(ii,2)-point(2)).^2);
    end
end

फिर हमारे पास सभी संभावित हलकों का केंद्र ( cc ) और त्रिज्या ( distance ) है जिनका उनके अंदर कोई मतलब नहीं है। हमें बस सबसे बड़ी जरूरत है!

[r,ind]=max(distance); %Tada!

अब प्लॉट देता है

hold on

ang=0:0.01:2*pi; 
xp=r*cos(ang);
yp=r*sin(ang);

point=cc(ind,:);

voronoi(x,y)
triplot(dt,'color','r','linestyle',':')
plot(point(1)+xp,point(2)+yp,'k');
plot(point(1),point(2),'g.','markersize',20);

गौर करें कि वोरोनोई आरेख के एक शीर्ष पर सर्कल का केंद्र कैसे है।

नोट : यह केंद्र [0-5], [0-5] के अंदर मिलेगा। आप इस बाधा को बदलने के लिए इसे आसानी से संशोधित कर सकते हैं। आप उस सर्कल को खोजने का भी प्रयास कर सकते हैं जो इच्छुक क्षेत्र के अंदर अपनी संपूर्णता पर फिट बैठता है (जैसा कि सिर्फ केंद्र के विपरीत है)। यह अंत में एक छोटे से अतिरिक्त की आवश्यकता होगी जहां अधिकतम प्राप्त किया जाता है।


छवि की दूरी परिवर्तन की गणना करने के लिए आप इमेज प्रोसेसिंग टूलबॉक्स से bwdist उपयोग कर सकते हैं। इसे वोरोनोई आरेख बनाने की एक विधि के रूप में माना जा सकता है, जो @ अंधेरगिरी के उत्तर में अच्छी तरह से समझाया गया है।

img = imread('AbmxL.jpg');
%convert the image to a binary image
points = img(:,:,3)<200;
%compute the distance transform of the binary image
dist = bwdist(points);
%find the circle that has maximum radius
radius = max(dist(:));
%find position of the circle
[x y] = find(dist == radius);
imshow(dist,[]);
hold on
plot(y,x,'ro');


मुझे इमेज प्रोसेसिंग की आदत नहीं है, इसलिए यह सिर्फ एक आइडिया है:

एक गाऊसी फिल्टर (धब्बा) जैसा कुछ लागू करें जो प्रत्येक कण (पिक्सेल) को r = image_size (उन सभी को अतिव्यापी) के साथ एक गोल क्रम में बदल देता है। इस तरह, आपको एक चित्र प्राप्त करना चाहिए जहां सबसे अधिक सफेद पिक्सेल सबसे अच्छे परिणाम होने चाहिए। दुर्भाग्य से, जिम्प में प्रदर्शन विफल हो गया क्योंकि चरम धुंधलापन ने डॉट्स को गायब कर दिया।

वैकल्पिक रूप से, आप एक क्षेत्र में सभी पड़ोसी पिक्सेल को चिह्नित करके सभी मौजूदा पिक्सल का विस्तार कर सकते हैं (उदाहरण: r = 4), जो पिक्सेल बचे हैं वे एक ही परिणाम होंगे (वे जो किसी भी पिक्सेल की सबसे बड़ी दूरी हैं)


मैं शोधन के साथ ग्रिड खोज के आधार पर एक और समाधान प्रस्तावित करना चाहता हूं। यह एंडर के रूप में या rahnema1 के रूप में कम के रूप में उन्नत नहीं है, लेकिन इसका पालन करना और समझना बहुत आसान होना चाहिए। साथ ही, यह काफी तेज चलता है।

एल्गोरिथ्म में कई चरण होते हैं:

  1. हम एक समान दूरी पर ग्रिड उत्पन्न करते हैं।
  2. हम सभी उपलब्ध बिंदुओं के लिए ग्रिड में बिंदुओं की न्यूनतम दूरी पाते हैं।
  3. हम उन सभी बिंदुओं को छोड़ देते हैं जिनकी दूरी एक निश्चित प्रतिशत से कम है (उदाहरण के लिए 95)।
  4. हम उस क्षेत्र को चुनते हैं जिसमें सबसे बड़ी दूरी होती है (इसमें सही केंद्र होना चाहिए अगर मेरा प्रारंभिक ग्रिड पर्याप्त ठीक है)।
  5. हम चुने हुए क्षेत्र के चारों ओर एक नया मेशग्रिड बनाते हैं और फिर से दूरी पाते हैं (यह भाग स्पष्ट रूप से उप-इष्टतम है, क्योंकि दूर और अप्रासंगिक वाले सभी बिंदुओं के लिए दूरी की गणना की जाती है)।
  6. हम शीर्ष 5% मूल्यों के विचरण पर नज़र रखते हुए, क्षेत्र के भीतर परिशोधन को पुन: व्यवस्थित करते हैं -> यदि यह कुछ पूर्व निर्धारित सीमा से नीचे गिरता है तो हम टूट जाते हैं।

कई नोट:

  • मैंने यह धारणा बना ली है कि सर्कल बिखरे हुए बिंदुओं की सीमा से परे नहीं जा सकते (यानी बिखरने का वर्ग "अदृश्य दीवार" के रूप में कार्य करता है)।
  • उपयुक्त प्रतिशतक इस बात पर निर्भर करता है कि प्रारंभिक ग्रिड कितना ठीक है। यह भी पुनरावृत्तियों की मात्रा को प्रभावित करेगा, और cnt लिए इष्टतम प्रारंभिक मूल्य।

function [xBest,yBest,R] = q42806059
rng(1)
x=rand(1,100)*5;
y=rand(1,100)*5;

%% Find the approximate region(s) where there exists a point farthest from all the rest:
xExtent = linspace(min(x),max(x),numel(x)); 
yExtent = linspace(min(y),max(y),numel(y)).';
% Create a grid:
[XX,YY] = meshgrid(xExtent,yExtent);
% Compute pairwise distance from grid points to free points:
D = reshape(min(pdist2([XX(:),YY(:)],[x(:),y(:)]),[],2),size(XX));
% Intermediate plot:
% figure(); plot(x,y,'.k'); hold on; contour(XX,YY,D); axis square; grid on;
% Remove irrelevant candidates:
D(D<prctile(D(:),95)) = NaN;
D(D > xExtent | D > yExtent | D > yExtent(end)-yExtent | D > xExtent(end)-xExtent) = NaN;
%% Keep only the region with the largest distance
L = bwlabel(~isnan(D));
[~,I] = max(table2array(regionprops('table',L,D,'MaxIntensity')));
D(L~=I) = NaN;
% surf(XX,YY,D,'EdgeColor','interp','FaceColor','interp');
%% Iterate until sufficient precision:
xExtent = xExtent(~isnan(min(D,[],1,'omitnan')));
yExtent = yExtent(~isnan(min(D,[],2,'omitnan')));
cnt = 1; % increase or decrease according to the nature of the problem
while true
  % Same ideas as above, so no explanations:
  xExtent = linspace(xExtent(1),xExtent(end),20); 
  yExtent = linspace(yExtent(1),yExtent(end),20).'; 
  [XX,YY] = meshgrid(xExtent,yExtent);
  D = reshape(min(pdist2([XX(:),YY(:)],[x(:),y(:)]),[],2),size(XX));
  D(D<prctile(D(:),95)) = NaN;
  I = find(D == max(D(:)));
  xBest = XX(I);
  yBest = YY(I);  
  if nanvar(D(:)) < 1E-10 || cnt == 10
    R = D(I);
    break
  end
  xExtent = (1+[-1 +1]*10^-cnt)*xBest;
  yExtent = (1+[-1 +1]*10^-cnt)*yBest;
  cnt = cnt+1;
end
% Finally:
% rectangle('Position',[xBest-R,yBest-R,2*R,2*R],'Curvature',[1 1],'EdgeColor','r');

परिणाम मुझे एंडर के उदाहरण डेटा के लिए मिल रहा है [x,y,r] = [0.7832, 2.0694, 0.7815] (जो समान है)। निष्पादन का समय एंडर के समाधान का लगभग आधा है।

यहाँ मध्यवर्ती भूखंड हैं:

सभी बिंदुओं के सेट के लिए एक बिंदु से सबसे बड़ी (स्पष्ट) दूरी का कंटूर:

सीमा से दूरी पर विचार करने के बाद, केवल शीर्ष 5% दूर बिंदुओं को रखते हुए, और केवल उस क्षेत्र पर विचार करें जिसमें सबसे बड़ी दूरी होती है (सतह का टुकड़ा रखे गए मूल्यों का प्रतिनिधित्व करता है):

और अंत में:





particles