[PYTHON] 방향을 따르는 점들의 집합을 그룹화하는 알고리즘
PYTHON방향을 따르는 점들의 집합을 그룹화하는 알고리즘
참고 :이 질문은 MATLAB과 Python 태그 모두에 적용됩니다.이 언어에 능숙합니다. 그러나 어떤 언어로든 솔루션을 환영합니다.
어안 렌즈로 이미지를 찍었습니다. 이 이미지는 일련의 정사각형 개체가있는 패턴으로 구성됩니다. 이 이미지로 수행하고자하는 작업은 이러한 각 사각형의 중심을 감지 한 다음이 포인트를 사용하여 이미지의 왜곡을 수행하는 것입니다. 특히 올바른 왜곡 모델 매개 변수를 찾고 있습니다. 모든 사각형이 감지 될 필요는 없다는 점에 유의해야합니다. 좋은 대다수가있는 한, 그건 완전히 괜찮아요 ....하지만이 게시물의 요점은 아닙니다. 매개 변수 추정 알고리즘은 이미 작성했지만 문제는 이미지에 동일 선상에 나타나는 점이 필요하다는 것입니다.
내가 물어보고 싶은 기본 질문에 이러한 점이 주어지며, 각 그룹이 수평선 또는 수직선으로 구성되도록 함께 그룹화하는 가장 좋은 방법은 무엇입니까?
이것은 제가 묻고있는 질문과 관련해서는별로 중요하지 않습니다. 그러나 제가 데이터를 얻은 곳을 알고 싶습니다. 제가 묻고있는 질문을 더 잘 이해하고 싶다면, 읽어보십시오. 관심이 없으면 아래의 문제 설정 섹션으로 건너 뛸 수 있습니다.
내가 다루고있는 이미지의 예가 아래와 같습니다 :
그것은 960 x 960 이미지입니다. 이미지는 원래 더 높은 해상도 였지만 이미지를 서브 샘플링하여 처리 시간을 단축했습니다. 보시다시피 이미지에 흩어져있는 정사각형 패턴이 잔뜩 있습니다. 또한, 내가 계산 한 centroid는 위 subsampled 된 이미지를 기준으로합니다.
중심선을 검색하기 위해 설정 한 파이프 라인은 다음과 같습니다.
위의 그림을 예로 들어 보겠습니다. 감지 된 각 사각형에는 사각형 자체에 대한 위치에 따라 색상이 지정된 4 개의 점이 있습니다. 내가 발견 한 각 중심점에 대해, 그 중심점이 이미지 자체에있는 ID를 바로 쓰게됩니다.
위 이미지에서 37 개의 감지 된 사각형이 있습니다.
N x 3 매트릭스에 저장된 이미지 픽셀 포인트가 있다고 가정합니다. 처음 두 열은 이미지 좌표 공간에서 y 좌표가 반전 된 x (가로) 및 y (세로) 좌표입니다. 즉, 양수 y가 아래쪽으로 이동 함을 의미합니다. 세 번째 열은 점과 관련된 ID입니다.
다음은 이러한 점을 취하고 2D 그리드에 그려주고 각 점을 행렬의 세 번째 열로 레이블링하는 MATLAB로 작성된 코드입니다. 위의 배경을 읽으면 위에서 설명한 알고리즘에 의해 감지 된 포인트입니다.
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, 29, 31, 33, 34, 35, 37 및 36은 하나의 그룹을 형성합니다. 19, 21, 24, 28, 30 및 32 점은 다른 그룹을 형성하는 식으로 등등합니다. 마찬가지로 수직적 의미에서 우리는 점 26, 19, 12, 3이 하나의 그룹을 형성하고, 점 29, 21, 13, 5가 또 다른 그룹을 형성한다는 것을 알 수 있습니다.
제 질문은 이것입니다 : 포인트가 임의의 방향으로있을 수 있다고 가정 할 때, 수평 그룹핑과 수직 그룹핑의 포인트를 성공적으로 그룹화 할 수있는 방법은 무엇입니까?
출력은 첫 번째 목록에 요소가있는 한 쌍의 목록입니다. 각 요소는 수평선을 형성하는 일련의 점 ID를 제공합니다. 마찬가지로 두 번째 목록에는 각 요소가 수직선을 형성하는 일련의 점 ID를 제공하는 요소가 있습니다.
따라서 수평 계열의 예상 출력은 다음과 같습니다.
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], ...]
알고리즘 적으로, 내가 시도한 것은이 시점에서 경험 한 회전을 취소하는 것입니다. 필자는 Principal Components Analysis를 수행했으며 계산 된 직교 기저 벡터와 관련하여 포인트를 투영 해 보았습니다. 따라서 직선형 사각형 그리드에 점이 더 많거나 적습니다.
일단 그렇게하면 수평 또는 수직 좌표의 차분 변경을 기반으로 포인트를 그룹화 할 수있는 스캔 라인 처리를 수행하는 것만 큼 간단합니다. 좌표를 x 또는 y 값으로 정렬 한 다음 이러한 정렬 된 좌표를 검사하고 큰 변화를 찾습니다. 이 변경 사항이 발생하면 변경 사항 사이에 포인트를 그룹화하여 라인을 구성 할 수 있습니다. 각 차원과 관련하여이 작업을 수행하면 수평 또는 수직 그룹화가됩니다.
PCA와 관련하여, MATLAB과 Python에서 내가 한 것은 다음과 같습니다.
%# 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()
위의 코드는 데이터를 재 투영 할뿐만 아니라 원본 점과 투영 된 점을 하나의 그림으로 함께 표시합니다. 그러나 데이터 재 투영을 시도했을 때 얻은 결과는 다음과 같습니다.
빨간색의 점은 원래의 이미지 좌표이며 파란색 점은 기초 벡터에 재 투영되어 회전을 시도하고 제거합니다. 아직도 그 일을 제대로하지 못합니다. 점에 관해서는 여전히 약간의 방향이 있기 때문에 스캔 라인 알고리즘을 수행하려고하면 수평 추적을위한 아래 라인 또는 수직 추적을위한 라인의 포인트가 실수로 그룹화되어 올바르지 않습니다.
아마 나는이 문제에 대해 지나치게 생각하고 있지만, 당신이 이것에 관해 가지고있는 통찰력은 크게 감사 할 것입니다. 대답이 참으로 훌륭하다면, 나는이 문제에 대해 꽤 오랫동안 붙어있어 많은 현상금을 수여 할 것입니다.
나는이 질문이 오래도록 끝나지 않았기를 바란다. 이 문제를 해결하는 방법에 대한 아이디어가 없으면 내 질문을 읽지 않고 시간을내어 감사드립니다.
당신이 가질 수있는 통찰력을 기대합니다. 매우 감사합니다!
해결법
-
==============================
1.참고 1 : 여러 가지 설정이 있습니다 -> 원하는 이미지를 얻기 위해 다른 이미지를 변경해야 할 수도 있음 % 설정 -이 값으로 놀기
참고 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 -
==============================
2.이미 시도한 것보다 중력 점을 그룹화하는 더 좋은 방법을 제안 할 수는 없지만 다음 아이디어가 도움이되기를 바랍니다.
이미 시도한 것보다 중력 점을 그룹화하는 더 좋은 방법을 제안 할 수는 없지만 다음 아이디어가 도움이되기를 바랍니다.
이미지의 내용 (사각형 필드 포함)에 대해 매우 구체적이기 때문에 사실 문제 설정에서 주어진 데이터로부터 중심점을 그룹화해야하는지 아니면 배경에 설명 된 데이터를 사용할 수 있는지 궁금합니다. 문제에 대해서도 마찬가지입니다. 여러분이 이미 감지 된 각 사각형의 모서리와 주어진 사각형 내에서의 위치를 이미 결정했기 때문에 모서리 좌표를 비교하여 주어진 사각형의 이웃을 결정하는 것이 정확하다고 생각됩니다.
그래서 어떤 광장의 오른쪽 이웃에 대한 후보를 찾는, 나는 당신이 사각형의 오른쪽 상단과 오른쪽 하단 모서리와 다른 사각형 (또는 특정 거리 이내에 사각형)의 왼쪽 하단 모서리와 비교하는 것이 좋습니다 것이 좋습니다. 작은 수직 차이와 약간 큰 수평 차이 만 허용하면 두 개의 사각형이 서로 충분히 가까워지면 두 개의 사각형을 "일치"시킬 수 있습니다.
모서리 사이에 허용되는 수직 / 수평 차이의 상한을 사용하면이 경계 내에서 가장 잘 일치하는 사각형을 이웃으로 할당 할 수도 있습니다
문제는 모든 사각형을 감지하지 못할 수 있으므로 사각형 30과 32 사이에 약간 큰 공간이있는 것입니다. 행당 3 개 이상의 사각형이 필요하다고 말했기 때문에 간단히 무시할 수 있습니다. 그 수평선에서 32 제곱. 그것이 당신을위한 옵션이 아니라면, 가능한 한 많은 사각형을 맞추고, 이전에 계산 된 데이터를 사용하여 그리드의 한 지점에 "누락 된"사각형을 할당하십시오 :
사각형 32에 대한 예제에서 위쪽 및 아래쪽 이웃 27 및 37이 있음을 감지했을 것입니다. 또한 사각형 27이 행 1에 있고 37이 행 3 안에 있다고 판단 할 수 있어야합니다. 그러면 사각형을 할당 할 수 있습니다 32 사이의 "가장 일치하는"행으로,이 경우 분명히 2입니다.
이 일반적인 접근법은 기본적으로 이미 시도한 접근 방식이지만 그리드에서 두 지점의 위치를 단순히 비교하는 대신 두 줄의 방향과 거리를 비교하기 때문에 훨씬 정확할 것입니다.
이전 시도에서의 사이드 노드로서 - 검은 색 코너 라인을 사용하여 이미지의 초기 회전을 약간 보정 할 수 있습니까? 이렇게하면 더 많은 왜곡 알고리즘 (주석에서 knedlsepp으로 논의한 알고리즘처럼)을 훨씬 더 정확하게 만들 수 있습니다. (편집 : 나는 Parag의 코멘트를 지금 막 읽었다 - 선의 각에 의하여 점을 비교하는 것은 기본적으로 심상을 미리 자전하는 것과 기본적으로 동일하다)
-
==============================
3.게시 된 이미지의 자른 버전을 입력으로 사용하고 있습니다. 여기서는 그리드의 방향을 가로 / 세로와 비슷하게 생각할 수있는 경우에 대해서만 설명합니다. 이것은 당신의 범위를 완전히 다루지는 못하지만, 그것이 당신에게 어떤 조언을 줄 것이라고 생각합니다.
게시 된 이미지의 자른 버전을 입력으로 사용하고 있습니다. 여기서는 그리드의 방향을 가로 / 세로와 비슷하게 생각할 수있는 경우에 대해서만 설명합니다. 이것은 당신의 범위를 완전히 다루지는 못하지만, 그것이 당신에게 어떤 조언을 줄 것이라고 생각합니다.
왜곡 된 사각형이 채워지도록 이미지를 이진화하십시오. 여기서 나는 간단한 Otsu thresholding을 사용합니다. 그런 다음이 이진 이미지의 거리 변환을 가져옵니다.
거리가 변환 된 이미지에서 우리는 정사각형 사이의 간격을 정점으로 봅니다.
가로 방향의 선을 얻으려면 거리 이미지의 각 열의 로컬 최대 값을 가져온 다음 연결된 구성 요소를 찾습니다.
세로 방향의 선을 얻으려면 거리 이미지의 각 행에 대한 로컬 최대 값을 가져온 다음 연결된 구성 요소를 찾습니다.
아래의 이미지는 모서리 점이 원으로 표시된 수평선과 수직선을 보여줍니다.
합리적으로 긴 연결 요소의 경우 곡선 (선 또는 다항식)을 맞추고 구석 점을 구별 할 수 있습니다. 예를 들어 커브까지의 거리를 기준으로 말하며 커브의 어느 점에 점이 있는지 등을 분류 할 수 있습니다.
Matlab에서이 작업을 수행했습니다. 커브 피팅 및 분류 부품을 사용하지 않았습니다.
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')임의의 지향 그리드에 대해 이러한 선을 얻으려면 거리 이미지를 그래프로 생각하고 최적의 경로를 찾을 수 있습니다. 훌륭한 그래프 기반 접근법은 여기를 참조하십시오.
from https://stackoverflow.com/questions/29550785/algorithm-to-group-sets-of-points-together-that-follow-a-direction by cc-by-sa and MIT license
'PYTHON' 카테고리의 다른 글
| [PYTHON] Windows 용 psycopg2를 사용하여 어디서 바이너리 달걀을 다운로드 할 수 있습니까? (0) | 2018.11.13 |
|---|---|
| [PYTHON] cv2.waitKey (1)의 0xFF는 무엇입니까? (0) | 2018.11.13 |
| [PYTHON] 팬더 데이터 프레임에서 2 열의 값을 단일 열로 합치십시오. (0) | 2018.11.13 |
| [PYTHON] 파이썬 : 객체가 명명 된 튜플의 인스턴스인지 확인하는 방법은 무엇입니까? (0) | 2018.11.13 |
| [PYTHON] Python Paramiko를 사용하여 SSH를 통해 명령 / 스크립트에 입력 / 변수 전달 (0) | 2018.11.13 |