Как проверить, образуют ли четыре точки прямоугольник

Question

Я работаю над приложением распознавания формы. В этот момент набор точек (x,y) определяется детектором угла (красные точки, рис. 2.). Четыре из этих точек (в красных рамках, рис. 2.) Являются вершинами прямоугольника (иногда немного деформированного прямоугольника). Как лучше всего найти их среди других?

Вот пример входного изображения:

И это выглядит после обнаружения угла:

Answer 1

Это не ответ на ваш вопрос - это просто предложение.

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

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

Обновить:

Вот еще одно решение, которое также должно работать в серых изображениях.

1. Сделать порог для преобразования изображения в 1 бит (я использовал 200 из 255 в качестве порога).
2. Найдите все контуры в новом изображении, площадь которых больше некоторой константы (я взял 1000).
3. Найдите ограничительный прямоугольник для каждого контура и выполните проверку:

ContourArea / BoundingReactangleArea> константа

Я беру это constant как 0,9.

И этот алгоритм дал мне следующий результат:

Вот код OpenCV:

Mat src = imread("input.jpg"), gray, result;
vector<vector<Point> > contours;
vector<Vec4i> hierarchy;

result = Mat(src.size(), CV_8UC1);

cvtColor(src, src, CV_BGR2GRAY);
threshold(src, gray, 200, 255, THRESH_BINARY_INV);
findContours(gray, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE, Point(0, 0));

result = Scalar::all(0);
for (size_t i=0; i<contours.size(); i++)
{
    Rect rect = boundingRect(contours[i]);
    if (rect.area() > 1000)
    {
        double area = contourArea(contours[i]);
        if (area/rect.area() > 0.9)
        {
            drawContours(result, contours, i, Scalar(255), -1);
        }
    }
}

Answer 2

Рассчитайте набор из 6 длин, которые вы будете иметь между каждой парой из 4 различных точек. В этом наборе из 6 длин, если имеется более 3 различных значений, у вас нет прямоугольника (2 равных длины стороны плюс равные длины диагонали)

Answer 3

Вы знаете, что визуально осматривая облако точек, вы уже можете различить множество прямоугольников? Другими словами, вы, вероятно, найдете много прямоугольников, если не будете выполнять какую-то процедуру предварительного выбора...

В любом случае, кроме метода, уже заданного @mathematician1975, вы также можете просто проверить, параллельны ли стороны (более или менее).

Давайте назовем метод @ mathematician1975 method 1 и параллельная проверка method 2, Затем:

%# method 1: 
n1 = |u1-u2|    %#  3 sub., 3 mult, 2 add. per distance
n2 = |u3-u2|    %#  total of 6 distances to compute.
n3 = |u4-u3|    %#  then max 5+4+3+2+1 = 15 comp. to find unique distances
n4 = |u1-u4|    
n5 = |u4-u2|    %#  Total:
n6 = |u3-u1|    %#  12 sub., 18 mult., 12 add, 15 comp



%# method 2:
w1 = u1-u2       %#  3 subtractions per vector
w2 = u3-u2       %#  total of 4 vectors to compute 
w3 = u3-u2
w4 = u1-u4                
                        %#  12 sub.
abs(w1-w3) == [0 0 0]   %#  3 sub., 3 comp., 1 sign.
abs(w2-w4) == [0 0 0]   %#  3 sub., 3 comp., 1 sign.

                        %# Total: 18 sub., 6 comp. 2 sign.

Обратите внимание, что оба они наихудшие; с небольшим количеством бухгалтерии вы можете значительно снизить стоимость обоих.

Обратите внимание, что method 2 Необходимо заранее знать, что вершины уже находятся в правильном порядке. Если это не так, это увеличит стоимость в 4 раза, что более method 1.,

Могу я спросить, как вы вычисляете расстояния?

Answer 4

Считайте, что у вас должен быть номер 8 но у тебя есть номер 7, тогда вы собираетесь добавить номер 1 (называется дельта или исправление ошибок), чтобы исправить это.

Аналогичным образом, есть координаты дельта-прямоугольника, чтобы исправить прямоугольник. Убедитесь, что точка (координата) находится внутри треугольника.

Координаты прямоугольника указаны ниже:

x+delta,y+delta
x-delta,y+delta
x+delta,y-delta
x-delta,y-delta

Дайте мне знать, если это работает хорошо для вас или если вы найдете лучшее решение