Алгоритм (пошагово) и используемые геометрические элементы.
1) Предобработка
- Удаление шума: гауссов фильтр или нелинейные (median) + нормализация.
- Детекция границ: Canny. (Эвклидова геометрия: градиенты, нормали).
2) Поиск прямых (границ) в шуме
- Использовать вероятностный Hough (Probabilistic Hough) или LSD; порог по длине и согласованности направления.
- Группировать линии по углу (кластеры направлений) — ожидаются две доминирующие ортогональные группы для прямоугольника. (Проективная/евклидова: направление линии в изображении).
3) Устойчивое выделение релевантных линий (робастность к выбросам)
- RANSAC для подгонки прямых/параллельных групп и удаления выбросов. (Робастная оценка параметров в проективной плоскости).
4) Построение вершин (углов) как пересечений найденных линий
- Если линии заданы гомогенными коэффициентами $l=(a,b,c)$, пересечение двух линий $l_1,l_2$ даётся как вектор в гомогенной форме:
$$x=l_1\times l_2.$$ - Аналогично, линия через два гомогенных точки $x_1,x_2$: $l=x_1\times x_2$.
5) Проверка и фильтрация четырехугольников
- Перебрать пары направлений, взять 4 пересечения; проверить выпуклость, непрерывность краёв, минимальную сторону/площадь.
- Оценить близость углов к $90^{\circ }$ в декартовых координатах после метрической ректификации (см. далее) или использовать проективные инварианты для ранней фильтрации (например, отношение углов/длин).
6) Проективная реставрация (выпрямление)
- Прямоугольник в сцене даёт на изображении общую четырёхугольник — требуется найти гомографию $H$, переводящую найденный четырёхугольник в образ прямоугольника. Решается по 4 соответствиям точек: для каждой пары $x_i\leftrightarrow X_i$ имеем
$$x_i^{\prime }\sim H{x}_i,$$ линейные уравнения для вектора $h$ (строки/столбцы $H$) и решение через SVD (нормализация точек по Hartley улучшает численную устойчивость).
- Формула (общее): для каждого соответствия даём 2 уравнения вида
$$\begin{array}{rl}& x(h_{7}X+h_{8}Y+h_9)-(h_{1}X+h_{2}Y+h_3)=0,\\ & y(h_{7}X+h_{8}Y+h_9)-(h_{4}X+h_{5}Y+h_6)=0.\end{array}$$
7) Получение ванишинг-точек и линия бесконечности (проект. геометрия для метрической ректификации)
- В пересечении параллельных в 3D сторон в изображении появляются vanishing points $v$. Для двух направлений (две группы параллельных сторон) получаем $v_1,v_2$:
$$v=l_i\times l_j(\text{пересечение двух образов параллельных линий}).$$ - Линия бесконечности изображений: $l_{\infty }=v_1\times v_2$.
- Проективная ректификация: подобрать гомографию $H_p$, которая отправит $l_{\infty }$ в $(0,0,1)$ — это устраняет проектные искажения (переводит в аффинную систему).
8) Метрическая ректификация (восстановление углов/масштаба)
- Для восстановления ортогональности требуется найти изображение абсолютного круга/комплексной точки или матрицу $\omega$ (образ абсолютной конки) из условий ортогональности двух пар направлений: для двух ортогональных ванишинг-точек $v_i,v_j$ справедливо
$$v_i^{\top }\omega v_j=0.$$ - Решив систему для $\omega$ (нужно минимум 2 независимые ортогональные пары → 2 уравнения), получить аффин→евклид-гомографию $H_e$, восстанавливающую углы. Если известны внешние параметры камеры или соотношение сторон, использовать как дополнительное ограничение.
9) Финальные шаги: уточнение и валидация
- Подстройка (nonlinear refinement) через оптимизацию (bundle adjustment / Levenberg–Marquardt) минимизируя геометрическую ошибку (например суммарное расстояние краёв до линий или reprojection error для вершин).
- Крайняя валидация: проверка прямолинейности/ортогональности сторон, ожидаемых размеров, симметрий.
Почему используются элементы евклидовой и проективной геометрии
- Проективная геометрия: изображение плоской прямоугольной поверхности при произвольной камере — это проективное отображение (гомография). Для коррекции перспективных искажений и получения фронтальной (аффинной) проекции нужны гомографии, ванишинг-точки, линия бесконечности и проектные инварианты (например cross-ratio). Эти инструменты позволяют корректно соединять линии и вершины в присутствии перспективы. Формулы: пересечения, гомография $x^{\prime }\sim Hx$.
- Евклидова геометрия: после устранения проектной составляющей мы хотим восстановить истинные углы и расстояния (метрические свойства): ортогональность, длины сторон, соотношения — это уже евклидовы понятия (включают скалярное произведение, норму). Для этого нужна метрическая/евклидова ректификация (образ абсолютной конки $\omega$, проверка ортогональности через $v^{\top }\omega v^{\prime }=0$).
Практические приёмы для шума/нестабильности
- Нормализация точек (Hartley) перед SVD, RANSAC при поиске gомографий/vanishing points/линий, sub-pixel refinement углов (corner refinement), пороги по длине и согласованности линий.
- Проверять несколько гипотез (альтернативные наборы 4 линий) и выбирать по метрике качества (reprojection error, согласованность углов).
Короткое резюме формул, которые понадобятся:
- пересечение линий: $x=l_1\times l_2$, линия через точки: $l=x_1\times x_2$;
- ванишинг-точка: пересечение произведённых параллельных линий $v$;
- линия бесконечности: $l_{\infty }=v_1\times v_2$;
- однострочное соотношение гомографии: $x^{\prime }\sim Hx$;
- ортогоничность ванишинг-точек: $v_i^{\top }\omega v_j=0$.
Эти шаги и инструменты дают устойчивый геометрический пайплайн для распознавания и восстановления прямоугольных объектов в шумных изображениях.