Линейная аппроксимация комбинации линий по набору зашумленных точек

Постановка задачи

Рассмотрим задачу аппроксимации комбинации прямых линий по набору зашумленных координат точек, находящихся на данной комбинации линий (см. Рис. 1 и Рис. 2). Обычная формула линейной аппроксимации здесь не подойдет, так как точки перемешаны и результат будет некая усредненная линия между ними (см. Рис. 3).

Рис. 1 Комбинация линий и зашумленный набор координат

Рис. 2 Комбинация линий и зашумленный набор координат в увеличенном масштабе

Рис. 3 Результат линейной аппроксимации

Алгоритм

Единственный способ, который пришел в голову, это перебирать разные варианты линий. Т.е. перебираем все возможные углы, естественно на ограниченной сетке, от -90 градусов до +90 градусов (от -180 до 180 бессмысленно, т.к. линия симметрична относительно центра координат).

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

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

1. Набор рассматриваемых углов

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

2. Определение расстояния от точки до прямой

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

Пусть уравнение линии и координаты точки, расстояние от которой измеряем, принимают следующие обозначения:

Тогда, так как кратчайшее расстояние от точки до линии это перпендикуляр к этой линии, получаем уравнение перпендикуляра, проходящего через заданную точку следующего вида:

Тогда, точка пересечения этих двух прямых:

$\$\$display\$\$y=\; k\; (x\_p+ky\_p-bk)/(k^2+1)+b=\; (〖kx〗\_p+k^2\; y\_p-bk^2+bk^2+b)/(k^2+1)=(〖kx〗\_p+k^2\; y\_p+b)/(k^2+1)\$\$display\$\$$

Получаем расстояние от интересующей точки до точки пересечения:

3. Построение гистограммы расстояний

Если мы построим просто гистограмму расстояний, она будет малоинформативной, поэтому нам необходимо построить гистограмму по скользящему окну, таким образом она будет более плавной и результат мы получим с меньшей ошибкой (см. Рис. 4-6).

По построенной гистограмме определяем расстояние с максимальным количеством точек. По полученному набору максимального количества точек для каждого угла, строим зависимость количества точек и угла наклона линии (см. Рис. 7, 8). На Рис. 7 видно четких два пика, данные пики и есть углы наклона интересующих нас линий.

Рис. 4 Гистограмма расстояний (ошибочная линия)

Рис. 5 Гистограмма расстояний (правильная линия)

Рис. 6 Увеличенная гистограмма расстояний (правильная линия)

Рис. 7 Гистограмма распределения максимального количества равноудаленных точек в зависимости от угла наклона рассматриваемой линии (Шаг 1)

Рис. 8 Гистограмма распределения максимального количества равноудаленных точек в зависимости от угла наклона рассматриваемой линии (Шаг 2)

4. Построение линейной аппроксимации

Полученный из гистограммы угол наклона линии является неточным, так как он был получен на фиксированной сетке углов. Для получения более точного угла наклона и смещения интересующей линии, необходимо выполнить линейную аппроксимацию полученного набора точек по следующим формулам (см. Рис. 9 и Рис. 10):

$\$\$display\$\$k=\; (N\sum \_1^N(xy)-\; \sum \_1^Nx\; \sum \_1^Ny)/(N\sum \_1^Nx^2\; -\; (\sum \_1^Nx)^2\; );\; b\; =(\sum \_1^Ny-k\sum \_1^Nx)/N\$\$display\$\$$

Рис. 9 Результат аппроксимации первой линии

Рис. 10 Результат аппроксимации второй линии

Примеры использования

Приведем примеры распознавания линий на произвольных наборах точек (см. Рис 11-13).

Рис. 11 Результат работы на произвольной выборке точек

Рис. 12 Результат работы на произвольной выборке точек

Рис. 13 Результат работы на произвольной выборке точек

Вывод

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

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

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