Алгоритмы приближения набора точек прямой

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

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

1. Какое количество кривых имеет изображение?
2. Вид, какой кривой (уравнения) представляют собой координаты точек на изображении?
3. Какие точки на изображении относятся к определённой кривой?

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

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

В данной статье мы рассмотрим пять методов:

1. Наименьших квадратов
2. Последовательных приближений
3. K-средних
4. Метод, являющийся модификацией метода наименьших квадратов
5. RANSAC

Наименьшие квадраты

Цель:

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

Алгоритм:

Для выполнения нашей цели нам необходимо найти такой набор параметров прямой, при которых каждая из точек изображения была бы максимально близко расположена к ней. Возьмём, для примера, прямую, которая наиболее верно аппроксимирует значение координаты y для каждой точки изображения (x_i , y_i), при совпадении координаты x. Прямую можно единственным образом определить, используя пару параметров:

• a – тангенс угла наклона прямой;
• b – расстояние по оси Оу до прямой.

Уравнение прямой имеет вид: y = ax + b. Разница между координатами у некоторой точки на изображении (x_i , y_i) и точки, принадлежащей прямой с такой же координатой х, может быть вычислена по следующей формуле: y_i – ax_i – b. Получили, что наилучшие параметры прямой можно определить, минимизировав сумму:

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

Рис 1."Варианты нахождения расстояния для метода наименьших квадратов."

Рассмотрим уравнение прямой: ax + by + c = 0, где a² + b² = 1 (нормализующие правило). Тогда длину перпендикуляра между точкой(u, v) и прямой можно представить следующей формулой: au + bv + c, при удовлетворении коэффициентов a, b нормализующему правилу. Тогда мы можем решить задачу приближения, проведя минимизацию следующей функции (при условии a² + b² = 1):

Последовательные приближения

Цель:

Входные данные – набор точек на изображении, которые образуют некую связанную кривую.

Алгоритм:

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

Рис 2."Алгоритм работы метода последовательных приближений."

K – Средние

Цель:

На входе имеем набор точек на изображении, которые образуют k прямых. Нужно найти какие точки, к какой прямой относятся.

Алгоритм:

Для оптимального решения необходимо минимизировать следующую функцию:

Где dist(l_i, x_i) ,будет расстоянием от точки x_i до прямой l_i. Минимизация проводится по двум направлениям:

• набору точек, для каждой прямой;
• по параметрам прямых.

Когда мы имеем дело с большим числом точек, то параметрическое пространство для перебора достаточно большое. Чтобы справится с этой проблемой, необходимо приспособить метод k-средних, тогда он будет состоять из двух повторяющихся этапов:

1. Каждая точка относится к той прямой, расстояние до которой минимально.
2. Параметры каждой прямой преобразуются так, чтобы оптимально приблизить принадлежащие прямым точки.

Рассмотрим полную схему алгоритма k-средних, она состоит из четырёх шагов:

1. Берутся k прямых, которые могут быть выбраны случайным образом.
2. Пока у нас есть изменения, мы делаем шаги 3, 4.
3. Рассматриваем каждую точку и относим её к одной из прямых, которая ближе всех расположена к точке.
4. Для получившегося набора точек пересчитываем параметры.

Метод, являющийся модификацией метода наименьших квадратов

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

Рис 3.

Для избавления от такого эффекта используют функцию, которая преобразует расчёт суммы квадратов расстояний от точек до прямой, поэтому влияние точки становится меньше по мере её отдаления от прямой. Функция представляется следующим образом:

Где u – расстояние между точкой и прямой, а &sigma – коэффициент, который определяет скорость уменьшения влияния точки.

Расстояние от точки до прямой является в свою очередь функцией вида: r = r (x,&theta), x – вектор координат точки, &theta – вектор параметров прямой. Тогда задача приближения сводится к минимизации суммы вида:

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

Рассмотрим подробней алгоритм данного метода:

1. Необходимо найти начальное приближение набора точек прямой, для этого можно воспользоваться методом наименьших квадратов. Таким образом, мы получим вектор параметров прямой &theta ⁰
2. Для &theta ⁰ нужно рассчитать начальное приближение &sigma ⁰
3. Пока вектор параметров существенно изменяется, т. е. разница между вектором параметров прямой на n шаге и n-1 шаге больше некоторого эпсилон, выполняем шаг 4, 5.
4. Производим аппроксимацию набора точек, для этого используем параметр &sigma^n-1 и получаем &theta ⁿ
5. Производим пересчёт &sigma ⁿ

Есть общепринятый метод расчёта &sigmaⁿ,его можно представить формулой:

RANSAC

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

Для использования данного алгоритма, нужно решить две задачи:

1. Какое количество точек должно находиться в подмножестве?
2. Какое количество итераций с выбором подмножеств нам необходимо?

Предположим, что k – минимальное количество итераций, n – количество точек на входе из которых w точек представлены корректно, остальные точки в свою очередь являются шумом. Количество точек в подмножестве не менее 2. Тогда корректна формула:

Алгоритм:

N – Наименьшее число точек, которое должно быть в подмножестве.

K – Нужное количество итераций.

T – Порог (наибольшее расстояние между прямой и точкой, при котором точка относится к прямой).

D – Наименьшее число точек, когда прямая не будет приниматься за шум.

1. Пока количество итераций не превышает заданное k.
2. Случайным образом берём подмножество из N точек.
3. Производим аппроксимацию текущего подмножества прямой, можно воспользоваться методом наименьших квадратов.
4. Производим обнуление счётчика близких к прямой точек.
5. Для каждой точки, которая не принадлежит подмножеству
6. Находим расстояние от неё до данной прямой.
7. Если расстояние не превышает заданного порога или равно ему
8. Увеличиваем счётчик на единицу.
9. Если значение счётчика стало равно D
10. Производим аппроксимацию текущей прямой по всем рядом лежащим к ней точкам.
11. Прямая считается «хорошей» и добавляется в набор «хороших» прямых.
12. Из «хороших» прямых необходимо выбрать прямую, у которой значение счётчика будет максимально.

Источник: http://cgm.computergraphics.ru