python एक बिंदु का पालन करने वाले बिंदुओं के समूह सेट करने के लिए एल्गोरिदम



image algorithm (3)

नोट: मैं इस प्रश्न को MATLAB और पायथन टैग दोनों में रख रहा हूं क्योंकि मैं इन भाषाओं में सबसे अधिक कुशल हूं। हालांकि, मैं किसी भी भाषा में समाधान का स्वागत करता हूं।

प्रश्न प्रस्तावना

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

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

मेरी समस्या के लिए पृष्ठभूमि

यह पूछे जाने वाले प्रश्न के संबंध में यह वास्तव में महत्वपूर्ण नहीं है, लेकिन यदि आप जानना चाहते हैं कि मुझे अपना डेटा कहां से मिला है और मैं जो सवाल पूछ रहा हूं उसे और समझने के लिए, कृपया पढ़ें। यदि आप रुचि नहीं रखते हैं, तो आप नीचे समस्या सेटअप अनुभाग पर दाएं छोड़ सकते हैं।

जिस छवि के साथ मैं काम कर रहा हूं उसका एक उदाहरण नीचे दिखाया गया है:

यह एक 960 x 960 छवि है। छवि मूल रूप से उच्च रिज़ॉल्यूशन थी, लेकिन मैं तेजी से प्रसंस्करण समय की सुविधा के लिए छवि को कम करता हूं। जैसा कि आप देख सकते हैं, छवि पैटर्न में फैले वर्ग पैटर्न का एक गुच्छा है। साथ ही, मैंने जिन केंद्रों की गणना की है, वे उपर्युक्त छवि के संबंध में हैं।

मैंने सेंट्रॉइड को पुनः प्राप्त करने के लिए स्थापित पाइपलाइन निम्नलिखित है:

  1. एक कैनी एज डिटेक्शन करें
  2. ब्याज के क्षेत्र पर ध्यान केंद्रित करें जो झूठी सकारात्मक को कम करता है। ब्याज का यह क्षेत्र मूल रूप से वर्गों में से किसी भी काले टेप के बिना है जो उनके पक्षों में से एक को कवर करता है।
  3. सभी अलग बंद contours खोजें
  4. प्रत्येक अलग बंद contour के लिए ...

    ए। हैरिस कॉर्नर डिटेक्शन करें

    ख। निर्धारित करें कि परिणाम में 4 कोने पॉइंट हैं या नहीं

    सी। यदि ऐसा होता है, तो यह समोच्च एक वर्ग से संबंधित था और इस आकार का केंद्र ढूंढता है

    घ। यदि ऐसा नहीं होता है, तो इस आकार को छोड़ दें

  5. आगे की परीक्षा के लिए सभी # पता लगाए गए सेंट्रॉइड को चरण # 4 से मैट्रिक्स में रखें।

उपरोक्त छवि के साथ एक उदाहरण परिणाम यहां दिया गया है। प्रत्येक ज्ञात वर्ग में चार बिंदु रंग कोड होते हैं जहां यह वर्ग के संबंध में कहां है। मैंने पाया है कि प्रत्येक केंद्र के लिए, मैं एक आईडी सही लिखता हूं जहां वह केंद्र छवि में ही है।

उपर्युक्त छवि के साथ, 37 ज्ञात वर्ग हैं।

समस्या सेटअप

मान लीजिए मेरे पास N x 3 मैट्रिक्स में संग्रहीत कुछ छवि पिक्सेल पॉइंट हैं। पहले दो कॉलम x (क्षैतिज) और y (लंबवत) निर्देशांक होते हैं जहां छवि समन्वय स्थान में, y समन्वय उलटा होता है , जिसका अर्थ है कि सकारात्मक y नीचे की ओर जाता है। तीसरा कॉलम बिंदु से जुड़े एक आईडी है।

MATLAB में लिखा गया कुछ कोड यहां दिया गया है जो इन बिंदुओं को लेता है, उन्हें 2 डी ग्रिड पर प्लॉट करता है और प्रत्येक बिंदु को मैट्रिक्स के तीसरे कॉलम के साथ लेबल करता है। यदि आप उपर्युक्त पृष्ठभूमि को पढ़ते हैं, तो ये वे बिंदु हैं जिन्हें ऊपर उल्लिखित मेरे एल्गोरिदम द्वारा पता चला था।

data = [ 475.  ,  605.75,    1.;
       571.  ,  586.5 ,    2.;
       233.  ,  558.5 ,    3.;
       669.5 ,  562.75,    4.;
       291.25,  546.25,    5.;
       759.  ,  536.25,    6.;
       362.5 ,  531.5 ,    7.;
       448.  ,  513.5 ,    8.;
       834.5 ,  510.  ,    9.;
       897.25,  486.  ,   10.;
       545.5 ,  491.25,   11.;
       214.5 ,  481.25,   12.;
       271.25,  463.  ,   13.;
       646.5 ,  466.75,   14.;
       739.  ,  442.75,   15.;
       340.5 ,  441.5 ,   16.;
       817.75,  421.5 ,   17.;
       423.75,  417.75,   18.;
       202.5 ,  406.  ,   19.;
       519.25,  392.25,   20.;
       257.5 ,  382.  ,   21.;
       619.25,  368.5 ,   22.;
       148.  ,  359.75,   23.;
       324.5 ,  356.  ,   24.;
       713.  ,  347.75,   25.;
       195.  ,  335.  ,   26.;
       793.5 ,  332.5 ,   27.;
       403.75,  328.  ,   28.;
       249.25,  308.  ,   29.;
       495.5 ,  300.75,   30.;
       314.  ,  279.  ,   31.;
       764.25,  249.5 ,   32.;
       389.5 ,  249.5 ,   33.;
       475.  ,  221.5 ,   34.;
       565.75,  199.  ,   35.;
       802.75,  173.75,   36.;
       733.  ,  176.25,   37.];

figure; hold on;
axis ij;
scatter(data(:,1), data(:,2),40, 'r.');
text(data(:,1)+10, data(:,2)+10, num2str(data(:,3)));

इसी प्रकार पायथन में, numpy और matplotlib का उपयोग करके, हमारे पास है:

import numpy as np
import matplotlib.pyplot as plt

data = np.array([[ 475.  ,  605.75,    1.  ],
   [ 571.  ,  586.5 ,    2.  ],
   [ 233.  ,  558.5 ,    3.  ],
   [ 669.5 ,  562.75,    4.  ],
   [ 291.25,  546.25,    5.  ],
   [ 759.  ,  536.25,    6.  ],
   [ 362.5 ,  531.5 ,    7.  ],
   [ 448.  ,  513.5 ,    8.  ],
   [ 834.5 ,  510.  ,    9.  ],
   [ 897.25,  486.  ,   10.  ],
   [ 545.5 ,  491.25,   11.  ],
   [ 214.5 ,  481.25,   12.  ],
   [ 271.25,  463.  ,   13.  ],
   [ 646.5 ,  466.75,   14.  ],
   [ 739.  ,  442.75,   15.  ],
   [ 340.5 ,  441.5 ,   16.  ],
   [ 817.75,  421.5 ,   17.  ],
   [ 423.75,  417.75,   18.  ],
   [ 202.5 ,  406.  ,   19.  ],
   [ 519.25,  392.25,   20.  ],
   [ 257.5 ,  382.  ,   21.  ],
   [ 619.25,  368.5 ,   22.  ],
   [ 148.  ,  359.75,   23.  ],
   [ 324.5 ,  356.  ,   24.  ],
   [ 713.  ,  347.75,   25.  ],
   [ 195.  ,  335.  ,   26.  ],
   [ 793.5 ,  332.5 ,   27.  ],
   [ 403.75,  328.  ,   28.  ],
   [ 249.25,  308.  ,   29.  ],
   [ 495.5 ,  300.75,   30.  ],
   [ 314.  ,  279.  ,   31.  ],
   [ 764.25,  249.5 ,   32.  ],
   [ 389.5 ,  249.5 ,   33.  ],
   [ 475.  ,  221.5 ,   34.  ],
   [ 565.75,  199.  ,   35.  ],
   [ 802.75,  173.75,   36.  ],
   [ 733.  ,  176.25,   37.  ]])

plt.figure()
plt.gca().invert_yaxis()

plt.plot(data[:,0], data[:,1], 'r.', markersize=14)

for idx in np.arange(data.shape[0]):
    plt.text(data[idx,0]+10, data[idx,1]+10, str(int(data[idx,2])), size='large')

plt.show()

हमें मिला:

सवाल पर वापस

जैसा कि आप देख सकते हैं, ये अंक ग्रिड पैटर्न में कम या कम हैं और आप देख सकते हैं कि हम बिंदुओं के बीच रेखाएं बना सकते हैं। विशेष रूप से, आप देख सकते हैं कि ऐसी रेखाएं हैं जिन्हें क्षैतिज और लंबवत रूप से बनाया जा सकता है।

उदाहरण के लिए, यदि आप मेरी समस्या के पृष्ठभूमि खंड में छवि का संदर्भ देते हैं, तो हम देख सकते हैं कि अंक के 5 समूह हैं जिन्हें क्षैतिज तरीके से समूहीकृत किया जा सकता है। उदाहरण के लिए, 23, 26, 2 9, 31, 33, 34, 35, 37 और 36 अंक एक समूह बनाते हैं। अंक 1 9, 21, 24, 28, 30 और 32 एक और समूह बनाते हैं और इतने पर और आगे। इसी प्रकार एक लंबवत अर्थ में, हम देख सकते हैं कि अंक 26, 1 9, 12 और 3 एक समूह बनाते हैं, अंक 2 9, 21, 13 और 5 अन्य समूह बनाते हैं और इसी तरह।

पूछने के लिए सवाल

मेरा सवाल यह है: एक ऐसी विधि क्या है जो क्षैतिज समूह और लंबवत समूह में अलग-अलग बिंदुओं को सफलतापूर्वक समूहित कर सकती है, बशर्ते कि अंक किसी भी अभिविन्यास में हो सकें?

शर्तेँ

  1. प्रति लाइन कम से कम तीन अंक होना चाहिए । यदि उससे कम कुछ भी है, तो यह एक सेगमेंट के रूप में योग्य नहीं है। इसलिए, अंक 36 और 10 लंबवत रेखा के रूप में योग्य नहीं होते हैं, और इसी तरह पृथक बिंदु 23 को लंबवत रेखा के रूप में गुणवत्ता नहीं होना चाहिए, लेकिन यह पहले क्षैतिज समूह का हिस्सा है।

  2. उपरोक्त अंशांकन पैटर्न किसी भी अभिविन्यास में हो सकता है। हालांकि, मैं जिस चीज से निपट रहा हूं, उसके लिए आपको सबसे खराब अभिविन्यास मिल सकता है जो आप पृष्ठभूमि अनुभाग में ऊपर देखते हैं।

अपेक्षित उत्पादन

आउटपुट सूचियों की एक जोड़ी होगी जहां पहली सूची में तत्व होते हैं जहां प्रत्येक तत्व आपको क्षैतिज रेखा बनाने वाले बिंदु आईडी का अनुक्रम देता है। इसी प्रकार, दूसरी सूची में ऐसे तत्व होते हैं जहां प्रत्येक तत्व आपको पॉइंट आईडी का अनुक्रम देता है जो लंबवत रेखा बनाता है।

इसलिए, क्षैतिज अनुक्रमों के लिए अपेक्षित आउटपुट इस तरह कुछ दिखाई देगा:

MATLAB

horiz_list = {[23, 26, 29, 31, 33, 34, 35, 37, 36], [19, 21, 24, 28, 30, 32], ...};
vert_list = {[26, 19, 12, 3], [29, 21, 13, 5], ....};

अजगर

horiz_list = [[23, 26, 29, 31, 33, 34, 35, 37, 36], [19, 21, 24, 28, 30, 32], ....]
vert_list = [[26, 19, 12, 3], [29, 21, 13, 5], ...]

मैंने क्या कोशिश की है

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

एक बार मेरे पास यह हो जाने के बाद, यह कुछ स्कैनलाइन प्रोसेसिंग करने का एक साधारण मामला है जहां आप क्षैतिज या लंबवत निर्देशांक पर अंतर परिवर्तन के आधार पर अंक समूह बना सकते हैं। आप निर्देशांक को या तो x या y मानों से सॉर्ट करेंगे, फिर इन सॉर्ट किए गए निर्देशांक की जांच करें और बड़े बदलाव की तलाश करें। एक बार जब आप इस परिवर्तन का सामना कर लेंगे, तो आप अपनी लाइनों को बनाने के लिए एक साथ परिवर्तनों के बीच बिंदुओं को समूहित कर सकते हैं। प्रत्येक आयाम के संबंध में ऐसा करने से आपको या तो क्षैतिज या लंबवत समूह मिलेंगे।

पीसीए के संबंध में, मै मैटलैब और पायथन में मैंने जो किया है:

MATLAB

%# Step #1 - Get just the data - no IDs
data_raw = data(:,1:2);

%# Decentralize mean
data_nomean = bsxfun(@minus, data_raw, mean(data_raw,1));

%# Step #2 - Determine covariance matrix
%# This already decentralizes the mean
cov_data = cov(data_raw);

%# Step #3 - Determine right singular vectors
[~,~,V] = svd(cov_data);

%# Step #4 - Transform data with respect to basis
F = V.'*data_nomean.';

%# Visualize both the original data points and transformed data
figure;
plot(F(1,:), F(2,:), 'b.', 'MarkerSize', 14);
axis ij;
hold on;
plot(data(:,1), data(:,2), 'r.', 'MarkerSize', 14);

अजगर

import numpy as np
import numpy.linalg as la

# Step #1 and Step #2 - Decentralize mean
centroids_raw = data[:,:2]
mean_data = np.mean(centroids_raw, axis=0)

# Transpose for covariance calculation
data_nomean = (centroids_raw - mean_data).T

# Step #3 - Determine covariance matrix
# Doesn't matter if you do this on the decentralized result
# or the normal result - cov subtracts the mean off anyway
cov_data = np.cov(data_nomean)

# Step #4 - Determine right singular vectors via SVD
# Note - This is already V^T, so there's no need to transpose
_,_,V = la.svd(cov_data)

# Step #5 - Transform data with respect to basis
data_transform = np.dot(V, data_nomean).T

plt.figure()
plt.gca().invert_yaxis()

plt.plot(data[:,0], data[:,1], 'b.', markersize=14)
plt.plot(data_transform[:,0], data_transform[:,1], 'r.', markersize=14)

plt.show()

उपर्युक्त कोड न केवल डेटा को दोहराता है, बल्कि यह मूल बिंदुओं और अनुमानित बिंदुओं को एक ही आंकड़े में एक साथ प्लॉट करता है। हालांकि, जब मैंने अपने डेटा को दोबारा लगाने की कोशिश की, तो यह वह साजिश है जो मुझे मिलती है:

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

शायद मैं समस्या पर विचार कर रहा हूं, लेकिन इसके बारे में आपके पास जो अंतर्दृष्टि है, उसकी सराहना की जाएगी। अगर जवाब वास्तव में शानदार है, तो मैं एक उच्च बक्षीस देने के इच्छुक हूं क्योंकि मैं इस समस्या पर कुछ समय से फंस गया हूं।

मुझे आशा है कि यह सवाल लंबे समय तक घुमाया नहीं गया था। अगर आपको इसका समाधान करने का कोई विचार नहीं है, तो मैं आपके प्रश्न को ध्यान में रखते हुए आपके समय के लिए धन्यवाद देता हूं।

आपके पास हो सकता है कि किसी भी अंतर्दृष्टि के लिए तत्पर हैं। बहुत बहुत धन्यवाद!


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

छवि को बिनराइज़ करें ताकि विकृत वर्ग भर जाए। यहां मैं एक साधारण ओत्सु थ्रेसहोल्डिंग का उपयोग करता हूं। फिर इस बाइनरी छवि के दूरी परिवर्तन को ले लो।

दूरी परिवर्तित छवि में हम वर्गों के बीच अंतराल को चोटी के रूप में देखते हैं।

क्षैतिज उन्मुख रेखाएं प्राप्त करने के लिए, दूरी छवि के प्रत्येक कॉलम की स्थानीय अधिकतमता लें और फिर कनेक्टेड घटकों को ढूंढें।

लंबवत उन्मुख रेखाएं प्राप्त करने के लिए, दूरी छवि की प्रत्येक पंक्ति की स्थानीय अधिकतमता लें और फिर कनेक्टेड घटकों को ढूंढें।

नीचे दी गई छवियां क्षैतिज और ऊर्ध्वाधर रेखाएं दिखाती हैं जो इस प्रकार कोने बिंदुओं के साथ मंडलियों के रूप में पाई जाती हैं।

उचित रूप से लंबे समय से जुड़े घटकों के लिए, आप एक वक्र (एक रेखा या बहुपद) फिट कर सकते हैं और उसके बाद कोने की दूरी को वर्गीकृत कर सकते हैं, वक्र की दूरी के आधार पर कहें, वक्र के किनारे बिंदु पर इत्यादि।

मैंने यह मैटलैब में किया था। मैंने वक्र फिटिंग और वर्गीकरण भागों की कोशिश नहीं की।

clear all;
close all;

im = imread('0RqUd-1.jpg');
gr = rgb2gray(im);
% any preprocessing to get a binary image that fills the distorted squares
bw = ~im2bw(gr, graythresh(gr));

di = bwdist(bw);                % distance transform
di2 = imdilate(di, ones(3));    % propagate max

corners = corner(gr);           % simple corners

% find regional max for each column of dist image
regmxh = zeros(size(di2));
for c = 1:size(di2, 2)
    regmxh(:, c) = imregionalmax(di2(:, c));
end
% label connected components
ccomph = bwlabel(regmxh, 8);

% find regional max for each row of dist image
regmxv = zeros(size(di2));
for r = 1:size(di2, 1)
    regmxv(r, :) = imregionalmax(di2(r, :));
end
% label connected components
ccompv = bwlabel(regmxv, 8);

figure, imshow(gr, [])
hold on
plot(corners(:, 1), corners(:, 2), 'ro')
figure, imshow(di, [])
figure, imshow(label2rgb(ccomph), [])
hold on
plot(corners(:, 1), corners(:, 2), 'ro')
figure, imshow(label2rgb(ccompv), [])
hold on
plot(corners(:, 1), corners(:, 2), 'ro')

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


नोट 1: इसमें कई सेटिंग्स हैं -> जो परिणाम आपको प्राप्त करने के लिए अन्य छवियों को बदलने की आवश्यकता हो सकती है % सेटिंग्स - इन मानों के साथ खेलें

नोट 2: यह उन सभी लाइनों को नहीं ढूंढता है जिन्हें आप चाहते हैं -> लेकिन यह एक प्रारंभिक बिंदु है ....

इस फ़ंक्शन को कॉल करने के लिए, कमांड प्रॉम्प्ट में इसे आमंत्रित करें:

>> [h, v] = testLines;

हमें मिला:

>> celldisp(h)

h{1} =
     1     2     4     6     9    10
h{2} =
     3     5     7     8    11    14    15    17
h{3} =
     1     2     4     6     9    10
h{4} =
     3     5     7     8    11    14    15    17
h{5} =
     1     2     4     6     9    10
h{6} =
     3     5     7     8    11    14    15    17
h{7} =
     3     5     7     8    11    14    15    17
h{8} =
     1     2     4     6     9    10
h{9} =
     1     2     4     6     9    10
h{10} =
    12    13    16    18    20    22    25    27
h{11} =
    13    16    18    20    22    25    27
h{12} =
     3     5     7     8    11    14    15    17
h{13} =
     3     5     7     8    11    14    15
h{14} =
    12    13    16    18    20    22    25    27
h{15} =
     3     5     7     8    11    14    15    17
h{16} =
    12    13    16    18    20    22    25    27
h{17} =
    19    21    24    28    30
h{18} =
    21    24    28    30
h{19} =
    12    13    16    18    20    22    25    27
h{20} =
    19    21    24    28    30
h{21} =
    12    13    16    18    20    22    24    25
h{22} =
    12    13    16    18    20    22    24    25    27
h{23} =
    23    26    29    31    33    34    35
h{24} =
    23    26    29    31    33    34    35    37
h{25} =
    23    26    29    31    33    34    35    36    37
h{26} =
    33    34    35    37    36
h{27} =
    31    33    34    35    37

>> celldisp(v)
v{1} =
    33    28    18     8     1
v{2} =
    34    30    20    11     2
v{3} =
    26    19    12     3
v{4} =
    35    22    14     4
v{5} =
    29    21    13     5
v{6} =
    25    15     6
v{7} =
    31    24    16     7
v{8} =
    37    32    27    17     9

एक आंकड़ा भी उत्पन्न होता है जो प्रत्येक उचित सेट के माध्यम से रेखाएं खींचता है:

function [horiz_list, vert_list] = testLines

global counter;
global colours; 
close all;

data = [ 475.  ,  605.75,    1.;
       571.  ,  586.5 ,    2.;
       233.  ,  558.5 ,    3.;
       669.5 ,  562.75,    4.;
       291.25,  546.25,    5.;
       759.  ,  536.25,    6.;
       362.5 ,  531.5 ,    7.;
       448.  ,  513.5 ,    8.;
       834.5 ,  510.  ,    9.;
       897.25,  486.  ,   10.;
       545.5 ,  491.25,   11.;
       214.5 ,  481.25,   12.;
       271.25,  463.  ,   13.;
       646.5 ,  466.75,   14.;
       739.  ,  442.75,   15.;
       340.5 ,  441.5 ,   16.;
       817.75,  421.5 ,   17.;
       423.75,  417.75,   18.;
       202.5 ,  406.  ,   19.;
       519.25,  392.25,   20.;
       257.5 ,  382.  ,   21.;
       619.25,  368.5 ,   22.;
       148.  ,  359.75,   23.;
       324.5 ,  356.  ,   24.;
       713.  ,  347.75,   25.;
       195.  ,  335.  ,   26.;
       793.5 ,  332.5 ,   27.;
       403.75,  328.  ,   28.;
       249.25,  308.  ,   29.;
       495.5 ,  300.75,   30.;
       314.  ,  279.  ,   31.;
       764.25,  249.5 ,   32.;
       389.5 ,  249.5 ,   33.;
       475.  ,  221.5 ,   34.;
       565.75,  199.  ,   35.;
       802.75,  173.75,   36.;
       733.  ,  176.25,   37.];

figure; hold on;
axis ij;

% Change due to Benoit_11
scatter(data(:,1), data(:,2),40, 'r.'); text(data(:,1)+10, data(:,2)+10, num2str(data(:,3)));
text(data(:,1)+10, data(:,2)+10, num2str(data(:,3)));

% Process your data as above then run the function below(note it has sub functions)
counter = 0;
colours = 'bgrcmy';
[horiz_list, vert_list] = findClosestPoints ( data(:,1), data(:,2) );


function [horiz_list, vert_list] = findClosestPoints ( x, y )
  % calc length of points
  nX = length(x);
  % set up place holder flags
  modelledH = false(nX,1);
  modelledV = false(nX,1);
  horiz_list = {};
  vert_list = {};

  % loop for all points
  for p=1:nX
    % have we already modelled a horizontal line through these?
    % second last param - true - horizontal, false - vertical
    if modelledH(p)==false
      [modelledH, index] = ModelPoints ( p, x, y, modelledH, true, true );
      horiz_list = [horiz_list index];
    else
      [~, index] = ModelPoints ( p, x, y, modelledH, true, false );
      horiz_list = [horiz_list index];
    end

    % make a temp copy of the x and y and remove any of the points modelled 
    %  from the horizontal -> this  is to avoid them being found in the 
    %  second call.
    tempX = x;
    tempY = y;
    tempX(index) = NaN;
    tempY(index) = NaN;
    tempX(p) = x(p);
    tempY(p) = y(p);
    % Have we found a vertial line?
    if modelledV(p)==false
      [modelledV, index] = ModelPoints ( p, tempX, tempY, modelledV, false, true );
      vert_list = [vert_list index];
    end
  end
end
function [modelled, index] = ModelPoints ( p, x, y, modelled, method, fullRun )
  % p - row in your original data matrix
  % x - data(:,1)
  % y - data(:,2)
  % modelled - array of flags to whether rows have been modelled
  % method   - horizontal or vertical (used to calc graadients)
  % fullRun  - full calc or just to get indexes 
  %            this could be made better by storing the indexes of each horizontal in the method above

  % Settings - play around with these values 
  gradDelta = 0.2;  % find points where gradient is less than this value
  gradLimit = 0.45; % if mean gradient of line is above this ignore
  numberOfPointsToCheck = 7; % number of points to check when look along the line
                        % to find other points (this reduces chance of it
                        % finding other points far away
                        %  I optimised this for your example to be 7
                        %  Try varying it and you will see how it effect the result.

  % Find the index of points which are inline.
  [index, grad] = CalcIndex ( x, y, p, gradDelta, method );
  % check gradient of line
  if abs(mean(grad))>gradLimit
    index = [];
    return
  end
  % add point of interest to index
  index = [p index];

  % loop through all points found above to find any other points which are in
  %  line with these points (this allows for slight curvature
  combineIndex = [];
  for ii=2:length(index)
    % Find inedex of the points found above (find points on curve)
    [index2] = CalcIndex ( x, y, index(ii), gradDelta, method, numberOfPointsToCheck, grad(ii-1) );

    % Check that the point on this line are on the original (i.e. inline -> not at large angle
    if any(ismember(index,index2))
      % store points found
      combineIndex = unique([index2 combineIndex]);
    end
  end

  % copy to index
  index = combineIndex;
  if fullRun
    %  do some plotting
    %  TODO: here you would need to calculate your arrays to output.
    xx = x(index);
    [sX,sOrder] = sort(xx);
    % Check its found at least 3 points
    if length ( index(sOrder) ) > 2
      % flag the modelled on the points found
      modelled(index(sOrder)) = true;
      % plot the data
      plot ( x(index(sOrder)), y(index(sOrder)), colours(mod(counter,numel(colours)) + 1));
      counter = counter + 1;
    end
    index = index(sOrder);
  end
end  
function [index, gradCheck] = CalcIndex ( x, y, p, gradLimit, method, nPoints2Consider, refGrad )
  % x - data(:,1)
  % y - data(:,2)
  % p - point of interest
  % method (x/y) or (y\x)
  % nPoints2Consider - only look at N points (options)
  % refgrad          - rather than looking for gradient of closest point -> use this
  %                  - reference gradient to find similar points (finds points on curve)
  nX = length(x);
  % calculate gradient
  for g=1:nX
    if method
      grad(g) = (x(g)-x(p))\(y(g)-y(p));
    else
      grad(g) = (y(g)-y(p))\(x(g)-x(p));
    end
  end
  % find distance to all other points
  delta = sqrt ( (x-x(p)).^2 + (y-y(p)).^2 );
  % set its self = NaN
  delta(delta==min(delta)) = NaN;
  % find the closest points
  [m,order] = sort(delta);

  if nargin == 7
    % for finding along curve
    % set any far away points to be NaN
    grad(order(nPoints2Consider+1:end)) = NaN;
    % find the closest points to the reference gradient within the allowable limit
    index = find(abs(grad-refGrad)<gradLimit==1);
    % store output
    gradCheck = grad(index);
  else
    % find the points which are closes to the gradient of the closest point
    index = find(abs(grad-grad(order(1)))<gradLimit==1);
    % store gradients to output
    gradCheck = grad(index);
  end
end
end

हालांकि, मैंने पहले से कोशिश की तुलना में सेंट्रॉइड पॉइंट्स की किसी दिए गए सूची को समूहबद्ध करने के लिए बेहतर दृष्टिकोण का सुझाव नहीं दे सकता है, मुझे उम्मीद है कि निम्नलिखित विचार आपकी मदद कर सकते हैं:

चूंकि आप अपनी छवि की सामग्री (वर्गों का एक क्षेत्र युक्त) के बारे में बहुत विशिष्ट हैं, इसलिए मैं सोच रहा था कि क्या आपको वास्तव में अपनी problem setup में दिए गए डेटा से सेंट्रॉइड पॉइंट्स को समूहित करने की आवश्यकता है, या यदि आप Background to the problem में वर्णित डेटा का उपयोग कर सकते हैं Background to the problem साथ-साथ। चूंकि आपने पहले से ही प्रत्येक ज्ञात वर्ग के कोनों को निर्धारित किया है और साथ ही उस वर्ग में उनकी स्थिति भी मुझे लगता है कि कोने-निर्देशांक की तुलना करके किसी दिए गए वर्ग के पड़ोसी को निर्धारित करना बहुत सटीक होगा।

तो किसी भी वर्ग के सही पड़ोसी के लिए किसी भी उम्मीदवार को खोजने के लिए, मैं सुझाव दूंगा कि आप उस वर्ग के ऊपरी दाएं और निचले दाएं कोने की तुलना ऊपरी बाएं और किसी अन्य वर्ग के निचले बाएं कोने (या किसी निश्चित दूरी के भीतर किसी भी वर्ग) के साथ करें। केवल छोटे लंबवत मतभेदों और थोड़ा अधिक क्षैतिज मतभेदों के लिए अनुमति देते हुए, आप दो वर्गों से "मिलान" कर सकते हैं, यदि उनके दोनों कोने-बिंदु दोनों एक साथ पर्याप्त हैं।

कोनों के बीच अनुमत लंबवत / क्षैतिज अंतर की ऊपरी सीमा का उपयोग करके, आप पड़ोसी के रूप में इन सीमाओं के भीतर सबसे अच्छा मिलान करने वाला वर्ग भी निर्दिष्ट कर सकते हैं

एक समस्या यह हो सकती है कि आप सभी वर्गों का पता नहीं लगाते हैं, इसलिए वर्ग 30 और 32 के बीच एक बड़ी जगह है। चूंकि आपने कहा है कि आपको कम से कम 3 वर्ग प्रति पंक्ति की आवश्यकता है, तो यह आपके लिए केवल अनदेखा करने के लिए व्यवहार्य हो सकता है उस क्षैतिज रेखा में वर्ग 32। यदि यह आपके लिए कोई विकल्प नहीं है, तो आप जितना संभव हो सके उतने वर्गों से मिलान करने का प्रयास कर सकते हैं और बाद में पहले गिनती वाले डेटा का उपयोग कर अपने ग्रिड में "लापता" वर्गों को एक बिंदु पर असाइन कर सकते हैं:

वर्ग 32 के बारे में उदाहरण में आपको पता चला होगा कि इसमें ऊपरी और निचले पड़ोसी 27 और 37 हैं। इसके अलावा आपको यह निर्धारित करने में सक्षम होना चाहिए कि वर्ग 27 पंक्ति 1 और 37 के भीतर स्थित है पंक्ति 3 के भीतर है, इसलिए आप वर्ग असाइन कर सकते हैं 32 में "सर्वोत्तम मिलान" पंक्ति के लिए, जो इस मामले में स्पष्ट रूप से 2 है।

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

आपके पिछले प्रयासों पर एक सिडेनोड के रूप में - क्या आप अपनी छवि के शुरुआती घूर्णन को सही करने के लिए काले कोनेलाइन का उपयोग कर सकते हैं? यह आगे विरूपण एल्गोरिदम बना सकता है (जैसे कि आपने टिप्पणियों में knedlsepp के साथ चर्चा की थी) बहुत अधिक सटीक। (संपादित करें: मैंने अभी पैराग की टिप्पणियां पढ़ी हैं - रेखाओं के कोण से बिंदुओं की तुलना करना मूल रूप से छवि को घूर्णन करने जैसा ही है)





image-processing