Примечание. Я помещаю этот вопрос как в теги MATLAB, так и в Python, так как я наиболее владею этими языками. Тем не менее, я приветствую решения на любом языке.
Вопрос Преамбула
Я взял изображение с линзой с рыбий глаз. Это изображение состоит из рисунка с кучей квадратных объектов. То, что я хочу сделать с этим изображением, - это определить центр тяжести каждого из этих квадратов, а затем использовать эти точки для выполнения искажения изображения - в частности, я ищу параметры правильной модели искажения. Следует отметить, что не все квадраты должны быть обнаружены. До тех пор, пока хорошее большинство из них, то это совершенно нормально.... но это не пункт этого поста. Алгоритм оценки параметров я уже написан, но проблема в том, что для него требуются точки, которые кажутся коллинеарными по изображению.
В базовом вопросе, который я хочу задать, даются эти точки, как наилучшим образом их группировать, чтобы каждая группа состояла из горизонтальной линии или вертикальной линии?
Предыстория моей проблемы
Это не очень важно в отношении вопроса, который я задаю, но если вы хотите узнать, откуда я получил свои данные, и для дальнейшего понимания вопроса, который я задаю, прочитайте. Если вас это не интересует, вы можете перейти к разделу Проблема ниже.
Пример изображения, с которым я имею дело, показан ниже:
Это изображение 960 x 960. Первоначально изображение было более высокого разрешения, но я подбираю изображение, чтобы ускорить время обработки. Как вы можете видеть, есть куча квадратных узоров, рассеянных на изображении. Кроме того, центроиды, которые я вычислил, относятся к вышеуказанному подвыбранному изображению.
Конвейер, который я настроил для извлечения центроидов, следующий:
- Выполните обнаружение Canny Edge
- Сосредоточьтесь на интересующей области, которая минимизирует ложные срабатывания. Эта область интересов представляет собой в основном квадраты без какой-либо черной ленты, которая покрывает одну из сторон.
- Найти все отдельные замкнутые контуры
-
Для каждого отдельного замкнутого контура...
а. Выполните обнаружение Harris Corner
б. Определите, имеет ли результат 4 угловых точки
с. Если это так, то этот контур принадлежал квадрату и нашел центроид этой формы
д. Если это не так, пропустите эту фигуру
-
Поместите все обнаруженные центроиды с шага №4 в матрицу для дальнейшего изучения.
Здесь приведен пример с приведенным выше изображением. Каждый обнаруженный квадрат имеет четыре цвета, закодированные в соответствии с расположением, где он относится к самому квадрату. Для каждого центроида, который я обнаружил, я пишу идентификатор, где этот центроид находится в самом изображении.
С приведенным выше изображением найдено 37 обнаруженных квадратов.
Настройка проблемы
Предположим, что у меня есть пиксельные точки изображения, хранящиеся в матрице N x 3
. Первые два столбца - это координаты x
(горизонтальный) и y
(вертикальный), где в координатном пространстве изображения координата y
инвертирована, что означает, что положительный y
перемещается вниз, Третий столбец - это идентификатор, связанный с точкой.
Вот некоторый код, написанный в MATLAB, который берет эти точки, разбивает их на 2D-сетку и помещает каждую точку в третий столбец матрицы. Если вы читаете приведенный выше фон, это точки, которые были обнаружены моим алгоритмом, описанным выше.
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)));
Аналогично в Python, используя 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 образуют другую группу и т.д.
Вопрос для запроса
Мой вопрос таков: что такое метод, который может успешно группировать точки в горизонтальных группировках и вертикальных группах отдельно, учитывая, что точки могут быть в любой ориентации?
Условия
-
Там должно быть не менее трех точек на строку. Если есть что-то меньшее, то это не относится к сегменту. Поэтому точки 36 и 10 не квалифицируются как вертикальная линия, и аналогично изолированная точка 23 не должна быть качественной как вертикальная линия, но она является частью первой горизонтальной группировки.
-
Вышеуказанный шаблон калибровки может быть в любой ориентации. Однако для того, что я имею в виду, наихудшая ориентация, которую вы можете получить, - это то, что вы видите выше в фоновом разделе.
Ожидаемый результат
Вывод будет представлять собой пару списков, в которых первый список содержит элементы, в которых каждый элемент дает вам последовательность идентификаторов точек, которые образуют горизонтальную линию. Аналогично, во втором списке есть элементы, в которых каждый элемент дает вам последовательность идентификаторов точек, которые образуют вертикальную линию.
Следовательно, ожидаемый результат для горизонтальных последовательностей будет выглядеть примерно так:
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], ....};
Python
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
, затем изучите эти отсортированные координаты и найдите большое изменение. Как только вы столкнетесь с этим изменением, вы можете группировать точки между изменениями вместе, чтобы сформировать ваши линии. Выполнение этого в отношении каждого измерения даст вам либо горизонтальную, либо вертикальную группировку.
Что касается PCA, вот что я сделал в MATLAB и Python:
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);
Python
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 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()
Приведенный выше код не только перепрограммирует данные, но также отображает как исходные точки, так и проецируемые точки вместе на одном рисунке. Однако, когда я пытался перепроверить мои данные, это сюжет, который я получаю:
Красные точки - это исходные координаты изображения, а точки в синем - перепроектированные на базисные векторы, чтобы попытаться удалить поворот. Он все еще не совсем справляется с этой задачей. По-прежнему существует какая-то ориентация относительно точек, поэтому, если я попытаюсь выполнить алгоритм сканирования, точки из строк ниже для горизонтальной трассировки или в сторону для вертикальной трассировки будут непреднамеренно сгруппированы, и это неверно.
Возможно, я переосмыслил проблему, но любые идеи, которые вы имеете в отношении этого, будут очень благодарны. Если бы ответ был действительно превосходным, я был бы склонен присуждать высокую награду, поскольку я уже давно застрял в этой проблеме.
Надеюсь, этот вопрос не был долгим. Если у вас нет идеи, как это решить, я благодарю вас за то, что вы время от времени читаете мой вопрос.
С нетерпением ждем любых сведений, которые могут возникнуть у вас. Большое спасибо!