Сортировка 2d точек в матрице

Question

У меня проблема:

Изображение дано, и я выполняю обнаружение blob. Как предел, скажем, у меня максимум 16 капли, и из каждого блоба я вычисляю центроид (положение x, y). Если никакие искажения не происходят, эти центроиды расположены в эквидистантной сетке 4x4, но они могут быть сильно искажены. Предполагается, что они сохраняют более или менее форму сетки, но они могут быть сильно искажены.

Мне нужно отсортировать капли, чтобы я знал, какой из них ближайший слева, справа, вверх и вниз. Поэтому лучше всего написать эти капли в матрицу.

Если этого недостаточно, может случиться, что я обнаружил менее 16, а затем мне также нужно отсортировать их в матрице.

Кто-нибудь знает, как это можно было бы эффективно решить в Matlab?

Спасибо.

[обновление 1:]

Я загрузил изображение и красные цифры числа, которые мой алгоритм обнаружения блоб присваивают каждый блоб.

Полученная матрица должна выглядеть следующим образом с этими числами:

1 2 4 3 
6 5 7 8 
9 10 11 12 
13 16 14 15 

например Я начинаю с сгустком 11 и ближайший правый номер 12 и так далее

[обновление 2:]

Опубликованным решение выглядит довольно хорошо. На самом деле это может случиться, что одно из внешних пятен отсутствует или может быть два ... Я знаю, что это делает все намного сложнее, и я просто хочу получить представление, если это стоит потратить время.

Эти проблемы возникают, если вы анализируете волновой фронт с датчиком волнового фронта shack-hartmann и хотите увеличить динамический диапазон :-) Пункты могут быть действительно искажены, так что разделительные линии больше не ортогональны.

Возможно, кто-то знает хорошую литературу для алгоритмов классификации.

Лучшим решением будет одно, которое может быть реализовано на FPGA без особых усилий, но на данном этапе это не так важно.

Answer 1

Это будет работать до тех пор, как сгустки образуют квадрат и относительно скомандовал:

Изображение:

Код:

bw = imread('blob.jpg'); 
bw = im2bw(bw); 

rp = regionprops(bw,'Centroid'); 

% Must be a square 
side = sqrt(length(rp)); 
centroids = vertcat(rp.Centroid); 
centroid_labels = cellstr(num2str([1:length(rp)]')); 

figure(1); 
imshow(bw); 
hold on; 
text(centroids(:,1),centroids(:,2),centroid_labels,'Color','r','FontSize',60); 
hold off; 

% Find topleft element - minimum distance from origin 
[~,topleft_idx] = min(sqrt(centroids(:,1).^2+centroids(:,2).^2)); 

% Find bottomright element - maximum distance from origin 
[~,bottomright_idx] = max(sqrt(centroids(:,1).^2+centroids(:,2).^2)); 

% Find bottom left element - maximum normal distance from line formed by 
% topleft and bottom right blob 
A = centroids(bottomright_idx,2)-centroids(topleft_idx,2); 
B = centroids(topleft_idx,1)-centroids(bottomright_idx,1); 
C = -B*centroids(topleft_idx,2)-A*centroids(topleft_idx,1); 
[~,bottomleft_idx] = max(abs(A*centroids(:,1)+B*centroids(:,2)+C)/sqrt(A^2+B^2)); 

% Sort blobs based on distance from line formed by topleft and bottomleft 
% blob 
A = centroids(bottomleft_idx,2)-centroids(topleft_idx,2); 
B = centroids(topleft_idx,1)-centroids(bottomleft_idx,1); 
C = -B*centroids(topleft_idx,2)-A*centroids(topleft_idx,1); 
[~,leftsort_idx] = sort(abs(A*centroids(:,1)+B*centroids(:,2)+C)/sqrt(A^2+B^2)); 

% Reorder centroids and redetermine bottomright_idx and bottomleft_idx 
centroids = centroids(leftsort_idx,:); 
bottomright_idx = find(leftsort_idx == bottomright_idx); 
bottomleft_idx = find(leftsort_idx == bottomleft_idx); 

% Sort blobs based on distance from line formed by bottomleft and 
% bottomright blob 
A = centroids(bottomright_idx,2)-centroids(bottomleft_idx,2); 
B = centroids(bottomleft_idx,1)-centroids(bottomright_idx,1); 
C = -B*centroids(bottomleft_idx,2)-A*centroids(bottomleft_idx,1); 
[~,bottomsort_idx] = sort(abs(A*reshape(centroids(:,1),side,side)+B*reshape(centroids(:,2),side,side)+C)/sqrt(A^2+B^2),'descend'); 

disp(leftsort_idx(bsxfun(@plus,bottomsort_idx,0:side:side^2-1))); 

Выход:

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

Любопытно, используете ли вы это для автоматизации калибровки камеры с помощью шахматной доски или чего-то еще?

---

ОБНОВЛЕНИЕ: Для перекос изображения

tform = maketform('affine',[1 0 0; .5 1 0; 0 0 1]); 
bw = imtransform(bw,tform); 

Выход:

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

для повернутого изображения:

bw = imrotate(bw,20); 

Выход:

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