Найти внешние углы шахматной доски

Question

На нижнем рисунке у меня есть двумерные местоположения зеленых точек, и я хочу рассчитать местоположения красных точек или, в качестве промежуточного шага, я хочу рассчитать местоположения синих точек , Все в 2D.

Если, конечно, я не только хочу, чтобы найти те места для фотографии выше. В конце концов, я хочу автоматизированный алгоритм, который принимает набор угловых точек шахматной доски для вычисления внешних углов.

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

Если OpenCV может это сделать, укажите мне в этом направлении.

Answer 1

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

Кроме того, конфигурация также инвариантна к поворотам на 180 град в плоскости шахматной доски и, если вы не будете осторожны, чтобы различать цвета квадратов, примыкающих к каждому углу, к поворотам на 90 градусов и отражениям относительно центра и срединные линии.

Это означает, что помимо обнаружения углов вам необходимо извлечь из изображения некоторые особенности физической шахматной доски, которые можно использовать для нарушения вышеуказанной инвариантности. Самый простой разрыв - обнаружить все 9 углов одной строки и одной колонки или, по крайней мере, их концевые углы. Они могут использоваться непосредственно для исправления изображения путем введения условия, чтобы их линии были под углом 90 градусов. Однако это может оказаться невозможным из-за закупорки или отказа детектора, и могут потребоваться более сложные методы.

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

Кстати, если фотография, которую вы опубликовали, является только красной селедкой, и вы заинтересованы в обнаружении общих шаблонов, похожих на шахматные доски, и можете контролировать тип рисунка, есть способы более надежных методов его выполнения. Мой личный фаворит "known 2D crossratios" pattern of Matsunaga and Kanatani.

Answer 2

я решил ее энергично, но не точно, со следующим раствором:

• Ищите линии с по крайней мере 3 зеленых точек близко соответствует линии. (тонкие красные линии на рис.)
• Продолжайте ограничивать линии: От этих линий держите их с точками только на одной стороне линии или очень близко к линии.
• Фильтрующие ограничивающие линии: от ограничивающих линий, возьмите 4 лучших из них с большинством точек на них. (жирные белые линии на рис.)
• Вычислите пересечения четырех оставшихся ограничивающих линий (ни одна из линий не является абсолютно параллельной, поэтому это приводит к 6 пересечениям, из которых мы хотим только 4).
• Из перекрестков удалите один из самых удаленных от среднего положения пересечений, пока не останется только 4 из них.
• Это 4 голубые точки.

Вы можете кормить эти 4 точки в findPerspectiveTransform функции OpenCV, чтобы найти перспективное преобразование (ака гомография):

Point2f* srcPoints = (Point2f*) malloc(4 * sizeof(Point2f));  
std::vector<Point2f> detectedCorners = CheckDet::getOuterCheckerboardCorners(srcImg); 
for (int i = 0; i < MIN(4, detectedCorners.size()); i++) { 
    srcPoints[i] = detectedCorners[i]; 
} 

Point2f* dstPoints = (Point2f*) malloc(4 * sizeof(Point2f)); 
int dstImgSize = 400; 
dstPoints[0] = Point2f(dstImgSize * 1/8, dstImgSize * 1/8); 
dstPoints[1] = Point2f(dstImgSize * 7/8, dstImgSize * 1/8); 
dstPoints[2] = Point2f(dstImgSize * 7/8, dstImgSize * 7/8); 
dstPoints[3] = Point2f(dstImgSize * 1/8, dstImgSize * 7/8); 

Mat m = getPerspectiveTransform(srcPoints, dstPoints); 

Для нашего примера изображения, входной и выходной findPerspectiveTranform выглядит следующим образом:

input 
    (349.1, 383.9) -> (50.0, 50.0) 
    (588.9, 243.3) -> (350.0, 50.0) 
    (787.9, 404.4) -> (350.0, 350.0) 
    (506.0, 593.1) -> (50.0, 350.0) 
output 
    (  1.6  -1.1 -43.8) 
    (  1.4  2.4 -1323.8) 
    (  0.0  0.0  1.0) 

You ca п, то преобразование точки зрения изображения к плате координаты:

Mat plainBoardImg; 
warpPerspective(srcImg, plainBoardImg, m, Size(dstImgSize, dstImgSize)); 

Результаты в следующем изображении:

Для моего проекта, красные точки, которые вы можете увидеть на доске в вопросе, больше не нужны, но я уверен, что их можно легко вычислить из гомографии, инвертируя его, а затем используя обратный для обратного преобразования точек (0, 0), (0, dstImgSize), (dstImgSize, dstImgSize) и (dstImgSize, 0).

Алгоритм работает на удивление надежно, однако он не использует всю доступную информацию, поскольку использует только внешние точки (те, которые связаны с белыми линиями). Для дополнительной точности он не использует данные внутренних точек. Я все равно хотел бы найти еще лучшее решение, которое использует данные внутренних точек.