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



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


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



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




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



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


Алгоритм


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


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


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


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


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


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


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


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

$y = kx + b, x_p, y_p$


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


$y-y_p=-(x-x_p)/k =>y= -x/k+ x_p/k+y_p$


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


$-x/k+ x_p/k+y_p=kx+b => -x+ x_p+ky_p= k^2 x+bk$


$-bk+ x_p+ky_p= k^2 x+x => x= (x_p+ky_p-bk)/(k^2+1)$


$$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$$


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


$dist= v((x_p- (x_p+ky_p-bk)/(k^2+1))^2+(y_p- (?kx?_p+k^2 y_p+b)/(k^2+1))^2 )$


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


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


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



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



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



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



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



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


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


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


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



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



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


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


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



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



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



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


Вывод


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


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


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




Комментарии (37):

  1. Shkaff
    /#21838622 / +5

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

    • YakMik
      /#21838948 / +2

      В Хафе расстояния тоже перебираются по фиксированной сетке, а тут более плавно)

      • m03r
        /#21839158

        а Вы не пробовали multiscale преобразование Хафа?

        • YakMik
          /#21839190

          Было бы классно если сразу ссылку дали где про него читать, и что именно имеется ввиду.

          • m03r
            /#21839672

            OpenCV предлагает два прохода детектора: сначала с обычным разрешением, а потом с увеличенным.

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

            Похожую проблему я решил однажды следующим способом: вручную проводил преобразование Хафа (потому что функция OpenCV выдаёт уже сами линии), а потом аккуратно blur'ил результат преобразования Хафа так, что несколько близкорасположенных линий сливались в одну усреднённую.

            Соединяя всё вместе, получается какой-то такой алгоритм:
            1. Провести преобразование Хафа с низким разрешением
            2. Заблюрить его результат, выделить интересные области
            3. Провести преобразование Хафа с высоким разрешением только по этим областям
            4. Найти уточнённое значение: возможно с помощью лёгкого размытия, а, возможно, сразу считать центр масс всех точек.

            • YakMik
              /#21839776

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

  2. aamonster
    /#21839050

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

    • YakMik
      /#21839080

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

      • YakMik
        /#21839092

        На Хафа похоже) и он и использовался в начале) никто не спорит, но далее используются преимущества конкретной задачи, а именно, то что детектируем линии. Допустим мы перебираем сетку из 100 углов и 100 смещений, получаем расчёт расстояний для 10000 вариаций линий, а в данном случае мы рассчитываем вариации расстояний для 100 вариантов линий, а далее на базе полученных смещений, ищем то, на котором имеется максимальное количество приблизительно одинаковых расстояний. Чувствуете изменение сложности вычислений?)

        • Shkaff
          /#21839144

          Было бы любопытно сравнить скорость работы двух алгоритмов. А еще, вот что интересно: как себя ведет ваш алгоритм с увеличением шума и уменьшением угла между прямыми? Если не ошибаюсь, если смотреть на гистограммы, ширина пиков будет задаваться уровнем шума, а разрешающая способность — углом между кривыми (для какого-то угла при заданном уровне шума вы не сможете отличить одну от другой).

          • YakMik
            /#21839216 / +1

            В выводе я как раз указал на то, что точки должны быть максимально раскиданы пространственно, тогда все будет работать стабильно. Если точки будут рядом друг с другом, естественно две линии будет детектировать проблематично.
            Но в случае если мы знаем про особенность что линии у нас близко расположены друг другу мы можем навешать новые ограничительные условия и использовать особенность данной задачи.
            Классический Хаф тоже будет проблематично детектировать две близко расположенные линии.
            По поводу скорости распознавания, то данная схема должна работать веселее) Из за того что не нужно перебирать разные варианты расстояний.

            • Shkaff
              /#21839428

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

              А Хафа, наверное, можно рандомизировать для ускорения. Или по адаптивной сетке пустить.

              • YakMik
                /#21839550 / +1

                Смотрите, по Хафу у вас есть фиксированный набор смещений, все, мы уперлись в то что нужно много считать. Хотим найти смещений с точностью 1 ед нужно выполнить 1000 вычислений, с шагом 0.5 ед нужно выполнить 2000 вычислений.
                А по данной схеме, вы за одно вычисления определили все расстояния. Т.е. мы берем линию с нулевым смещением и определяем расстояния всех точек до этой линии с этим нулевым смещением. Далее мы просто смотрим на каком расстоянии больше всего точек сконцентрировано => то расстояние на котором расположена линия. Итого 1 вычисление + вспомогательные вычисления по определению того самого расстояния, на котором больше всего точек.

                • Shkaff
                  /#21839722

                  Хотим найти смещений с точностью 1 ед нужно выполнить 1000 вычислений, с шагом 0.5 ед нужно выполнить 2000 вычислений.
                  А вот я нашел рандомизированный Хаф. А вот еще на байесовской оценке.

                  Но вообще, ваш метод выглядит быстро, действительно.

            • aamonster
              /#21841284 / +1

              По сложности – вроде сопоставимо получается.
              Пусть у нас M точек и делаем преобразование Хафа N*N (N значений угла, N значений исходной точки). Для «нанесения образа» каждой точки на итоговую картинку надо «нарисовать» кривую (синусоиду или что там) длиной O(N). Итого сложность O(M*N).
              Для вашего варианта: цикл по углам (N), для каждого строим гистограмму по M точкам – итого опять O(M*N). Более того: эта гистограмма – это аккурат строчка в результате преобразования Хафа (если его выполнять по тому же преобразованию координат, которое используетет вы). По сути, вы меняете местами циклы в преобразовании Хафа (ну и вносите дополнения типа сглаживания строки, обычная практика). Не знаю, как выгоднее – надо проверять на конкретных данных. Но такого, чтобы один метод принципиально выигрывал у другого, вроде не должно быть – скорей удастся сыграть на более тонких вещах вроде уменьшения числа cache misses.

              • YakMik
                /#21841326

                Читайте внимательнее описание и комментарии и вы поймете где именно вы со сложности O(M*N*N) перепрыгните на сложность O(M*N)

                • YakMik
                  /#21841336

                  «Чёткие» пацанчики строят гистограмму за O(N) ))))

                • aamonster
                  /#21841382

                  Нигде не перепрыгиваем. Нету в алгоритме Хафа O(M*N*N). Есть O(M*N): для каждой точки строим кривую, наносимую на образ.

                  Вы, наверное, попутали из-за того, что считали алгоритм Хафа для перевода изображения в изображение, а не списка точек в изображение (там M=N*N). Ну так он, как и ваш алгоритм, «любит», когда входных точек мало.

      • aamonster
        /#21839180

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

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

        Интереснее разница с RANSAC. Хотя RANSAC скорее актуален для более сложных случаев – когда у нас 3 и более параметра, определяющих объект.

        Меня на самом деле смутила фраза «единственный способ, который пришел в голову» – ну, вы понимаете)

        • YakMik
          /#21839234

          «единственный способ, который пришел в голову» тут согласен) просто это не совсем Хаф был) Скажите как написать корректно и литературно, исправлю)

          • aamonster
            /#21841212 / +1

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

            Смутила – в том плане, что для подобных статей характерен обзор «люди делают так, так и так; у этих методов такие-то недостатки, поэтому сделаем так – получим такие-то плюсы и такие-то минусы, плюсы в нашей задаче перекрывают минусы».

  3. /#21839182

    К части 2 — откройте учебник Александрова по аналитической геометрии, расстояние от точки до прямой вычисляется гораздо проще:

    bookre.org/reader?file=440728&pg=28

    К тексту вообще — а почему бы не использовать что-нибудь тупое, типа метода наименьших квадратов?

    • YakMik
      /#21839238

      Я уверен именно так и вычисляется) Просто привел вывод формулы)

  4. YDR
    /#21839390

    Я не могу сразу понять, почему это не простейший линейный МНК?

    • YakMik
      /#21839404

      Когда не можете понять, берете и пробуете) Получаете картинку с 3 рисунка)

      • Arastas
        /#21841250

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

        • YakMik
          /#21841300

          А теперь помедленнее и поподробнее, что вы имели ввиду)

          • Arastas
            /#21841342

            Я имел ввиду, что вашу задачу можно решить с использованием МНК.

            • YakMik
              /#21841384 / +1

              Сразу две линии по методу МНК? это как?) тут я что то не понимаю)
              Как я себе представляю 2 линии в общем понимании: это набор из 4 коэффициентов, а именно k1 b1 и k2 b2. МНК это по сути взятие производных по этим 4 параметрам и решение общей системы уравнений с 4 неизвестными, нооооооо так как у нас две разные линии, а мы априори не знаем какие точки в какой линии участвуют, как вы решать собираетесь?)
              Если действительно есть какой то способ, расскажите, это действительно интересно)

              • Arastas
                /#21841438 / +2

                Ну так ваши две линии это же на смом деле одна кривая второго порядка, верно? Точнее, если я правильно помню, это вырожденная гипербола.
                Смотрите, у нас каждая точка должна принадлежать либо прямой y=k1 x+b1, либо прямой y=k2 x+b2. То есть для любой точки на этих прямых вы получите
                (k1 x+b1-y) (k2 x+b2-y) = 0,
                или
                A x^2+B xy+C x+D y + E = y^2,
                где A, B, C, D, E зависят от k1, b1, k2 ,b2 (зная одни можно найти другие, в обе стооны). А это, кстати, уже почти что обобщенное уравнение кривой второго порядка на плоскости.
                Применяете МНК, находите A, B, C, D, E, а из них k1, b1, k2, b2. Если использовать в качестве измерений не x1, x2, y1, y2, а попарные разницы, то можно обойтись без нахождения E, так как оно всё равно не нужно.
                я мучительно страдаю от отсутствия поддержки LaTeX в комментариях. Ну как так...

                • YakMik
                  /#21841484

                  По ходу это то, что я искал) Буду изучать дома)
                  А вы всмысле решали подобную задачу? Она имеет аналитическое решение в конце? Не будет там что корни невозможно найти аналитически?
                  Вы красавчик! Это реально красиво с перемножением)

                  • Arastas
                    /#21841514 / +1

                    Просто знакомая область.
                    С нахождением корней — там получится одно квадратное уравнение для k1, k2, и либо линейная система из двух уравнений для b1, b2, либо ещё одно квадратное уравнение. Но осторожно, так как вычисление b1 и b2 через линейную систему может быть плохо обусловлено когда k1 и k2 почти одинаковые (параллельные прямые).

    • Shkaff
      /#21839436

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

    • YakMik
      /#21841498

      Так вы это и подразумевали?) То, что дальше писал Arastas?)

  5. iShrimp
    /#21841552

    В общем, суть вашей задачи — преобразовать облако точек из пространства (х, у) в пространство (r, ?), где ? — угол наклона прямой, а r — расстояние до центра.
    В вашей реализации, если я правильно понимаю, вы заполняете массив (r, ?) с помощью 3 вложенных циклов: радиус, угол, номер точки.
    Не пробовали ли вы решить задачу с другого конца: для каждой точки перебирать все возможные прямые (т.е. пары значений r, ?), которым она может принадлежать? Тогда у вас получится не 3, а 2 вложенных цикла — с параметрами n и ?.
    Этот метод может сработать быстрее, но с ним намного труднее контролировать точность детекции прямых, так как собственно сама по себе операция преобразования координат очень нелинейна.

    • YakMik
      /#21841578

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

      • iShrimp
        /#21841744

        Да, я понял, внешний цикл — перебор углов, внутренний цикл — перебор точек.
        У меня была похожая задача по поиску прямых линий, и я делал массив (r, ?) c таким разрешением, чтобы линия определялась с точностью до пикселя. Т.е. в Вашем случае из одномерных гистограмм можно сложить двумерную и искать в ней локальные максимумы. Но, если чрезмерно поднять разрешение, гистограмма станет очень шумной и потребует сглаживания фильтром Гаусса, ширина которого зависит от требуемой точности разделения линий.

        Заголовок спойлера