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




math image-processing (4)

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

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

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

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


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

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

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

कई नोट्स:

  • मैंने धारणा की है कि मंडल बिखरे हुए बिंदुओं से परे नहीं जा सकते हैं (यानी स्कैटर के बाउंडिंग वर्ग "अदृश्य दीवार" के रूप में कार्य करता है)।
  • उपयुक्त प्रतिशत इस बात पर निर्भर करता है कि प्रारंभिक ग्रिड कितना ठीक है। यह पुनरावृत्तियों के while , और 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% बिंदुओं को ध्यान में रखते हुए, और केवल उस क्षेत्र पर विचार करते हुए जिसमें सबसे बड़ी दूरी होती है (सतह का टुकड़ा रखा मूल्यों का प्रतिनिधित्व करता है):

और अंत में:


मुझे छवि प्रसंस्करण के लिए उपयोग नहीं किया जाता है, इसलिए यह सिर्फ एक विचार है:

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

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


आइए मेरे दोस्त को कुछ गणित करें, क्योंकि गणित हमेशा खत्म हो जाएंगे!

विकिपीडिया:

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

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

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


voronoi(x,y);

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

दिलचस्प बात यह है कि वोरोनोई क्षेत्रों के किनारों को डेलाउने त्रिभुज द्वारा उत्पन्न त्रिकोणों के circumcenters के रूप में भी परिभाषित किया जाता है।

तो अगर हम क्षेत्र के डेलाउने त्रिकोण और उनके circumcenters की गणना करते हैं

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

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

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





particle