Comments 37
В Хафе расстояния тоже перебираются по фиксированной сетке, а тут более плавно)
а Вы не пробовали multiscale преобразование Хафа?
Но по зрелом размышлении Хаф не подходит по другой причине: OpenCV'шная, например, реализация совсем не дружит с такими линиями, выдавая кучу близкорасположенных прямых вместо одной необходимой.
Похожую проблему я решил однажды следующим способом: вручную проводил преобразование Хафа (потому что функция OpenCV выдаёт уже сами линии), а потом аккуратно blur'ил результат преобразования Хафа так, что несколько близкорасположенных линий сливались в одну усреднённую.
Соединяя всё вместе, получается какой-то такой алгоритм:
1. Провести преобразование Хафа с низким разрешением
2. Заблюрить его результат, выделить интересные области
3. Провести преобразование Хафа с высоким разрешением только по этим областям
4. Найти уточнённое значение: возможно с помощью лёгкого размытия, а, возможно, сразу считать центр масс всех точек.
Хороший подход, рабочий, но стоило бы сразу сравнить свой алгоритм с часто используемыми для подобных задач.
Навскидку – уже названное преобразование Хафа (по сути оно же) и RANSAC.
В Хафе вы будете перебирать фиксированную сетку, а именно линии с определенным углом и смещением. Таким образом потом оценивая какой из вариантов больше всего подходит.
В данной схеме у вас изначальный подход другой. Вы измеряете всевозможные расстояния от точки до вариаций линий с различным углом, таким образом далее оценивая с каким смещением линия имеет максимальное количество точек.
Таким образом если вы действительно использовали Хафа от начала до конца, при этом реализовывая собственноручно, вы бы поняли что при необходимости более точного нахождения линии с первого шага преимущество данного метода. Данный метод изначально покрывает всевозможные вариации линий)
На Хафа похоже) и он и использовался в начале) никто не спорит, но далее используются преимущества конкретной задачи, а именно, то что детектируем линии. Допустим мы перебираем сетку из 100 углов и 100 смещений, получаем расчёт расстояний для 10000 вариаций линий, а в данном случае мы рассчитываем вариации расстояний для 100 вариантов линий, а далее на базе полученных смещений, ищем то, на котором имеется максимальное количество приблизительно одинаковых расстояний. Чувствуете изменение сложности вычислений?)
Но в случае если мы знаем про особенность что линии у нас близко расположены друг другу мы можем навешать новые ограничительные условия и использовать особенность данной задачи.
Классический Хаф тоже будет проблематично детектировать две близко расположенные линии.
По поводу скорости распознавания, то данная схема должна работать веселее) Из за того что не нужно перебирать разные варианты расстояний.
А Хафа, наверное, можно рандомизировать для ускорения. Или по адаптивной сетке пустить.
А по данной схеме, вы за одно вычисления определили все расстояния. Т.е. мы берем линию с нулевым смещением и определяем расстояния всех точек до этой линии с этим нулевым смещением. Далее мы просто смотрим на каком расстоянии больше всего точек сконцентрировано => то расстояние на котором расположена линия. Итого 1 вычисление + вспомогательные вычисления по определению того самого расстояния, на котором больше всего точек.
Хотим найти смещений с точностью 1 ед нужно выполнить 1000 вычислений, с шагом 0.5 ед нужно выполнить 2000 вычислений.А вот я нашел рандомизированный Хаф. А вот еще на байесовской оценке.
Но вообще, ваш метод выглядит быстро, действительно.
Пусть у нас M точек и делаем преобразование Хафа N*N (N значений угла, N значений исходной точки). Для «нанесения образа» каждой точки на итоговую картинку надо «нарисовать» кривую (синусоиду или что там) длиной O(N). Итого сложность O(M*N).
Для вашего варианта: цикл по углам (N), для каждого строим гистограмму по M точкам – итого опять O(M*N). Более того: эта гистограмма – это аккурат строчка в результате преобразования Хафа (если его выполнять по тому же преобразованию координат, которое используетет вы). По сути, вы меняете местами циклы в преобразовании Хафа (ну и вносите дополнения типа сглаживания строки, обычная практика). Не знаю, как выгоднее – надо проверять на конкретных данных. Но такого, чтобы один метод принципиально выигрывал у другого, вроде не должно быть – скорей удастся сыграть на более тонких вещах вроде уменьшения числа cache misses.
Вы, наверное, попутали из-за того, что считали алгоритм Хафа для перевода изображения в изображение, а не списка точек в изображение (там M=N*N). Ну так он, как и ваш алгоритм, «любит», когда входных точек мало.
Imho более важное отличие чуть другое (хотя по нынешним временам это не очень существенно): вам единовременно нужна одномерная гистограмма, а не двумерная.
Интереснее разница с RANSAC. Хотя RANSAC скорее актуален для более сложных случаев – когда у нас 3 и более параметра, определяющих объект.
Меня на самом деле смутила фраза «единственный способ, который пришел в голову» – ну, вы понимаете)
Смутила – в том плане, что для подобных статей характерен обзор «люди делают так, так и так; у этих методов такие-то недостатки, поэтому сделаем так – получим такие-то плюсы и такие-то минусы, плюсы в нашей задаче перекрывают минусы».
bookre.org/reader?file=440728&pg=28
К тексту вообще — а почему бы не использовать что-нибудь тупое, типа метода наименьших квадратов?
Справедливости ради, для случая двух прямых эта задача сводится к МНК с квадратичной нелинейностью, что при отсутсвии шумов точно восстанавливает требуемые прямые, а при наличии шумов даёт оптимальную в некотором смысле оценку. Которую потом резонно использовать как начальное приближение для локальной оптимизации с требуемым критерием оптимальности.
Точнее сказать, задача сводится к линейной регрессии с квадратичными функциями координат и билинейностями по параметрам. А дальше хоть МНК, хоть что угодно.
Я имел ввиду, что вашу задачу можно решить с использованием МНК.
Как я себе представляю 2 линии в общем понимании: это набор из 4 коэффициентов, а именно k1 b1 и k2 b2. МНК это по сути взятие производных по этим 4 параметрам и решение общей системы уравнений с 4 неизвестными, нооооооо так как у нас две разные линии, а мы априори не знаем какие точки в какой линии участвуют, как вы решать собираетесь?)
Если действительно есть какой то способ, расскажите, это действительно интересно)
Ну так ваши две линии это же на смом деле одна кривая второго порядка, верно? Точнее, если я правильно помню, это вырожденная гипербола.
Смотрите, у нас каждая точка должна принадлежать либо прямой 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 в комментариях. Ну как так...
А вы всмысле решали подобную задачу? Она имеет аналитическое решение в конце? Не будет там что корни невозможно найти аналитически?
Вы красавчик! Это реально красиво с перемножением)
Просто знакомая область.
С нахождением корней — там получится одно квадратное уравнение для k1, k2, и либо линейная система из двух уравнений для b1, b2, либо ещё одно квадратное уравнение. Но осторожно, так как вычисление b1 и b2 через линейную систему может быть плохо обусловлено когда k1 и k2 почти одинаковые (параллельные прямые).
В вашей реализации, если я правильно понимаю, вы заполняете массив (r, θ) с помощью 3 вложенных циклов: радиус, угол, номер точки.
Не пробовали ли вы решить задачу с другого конца: для каждой точки перебирать все возможные прямые (т.е. пары значений r, θ), которым она может принадлежать? Тогда у вас получится не 3, а 2 вложенных цикла — с параметрами n и θ.
Этот метод может сработать быстрее, но с ним намного труднее контролировать точность детекции прямых, так как собственно сама по себе операция преобразования координат очень нелинейна.
У меня была похожая задача по поиску прямых линий, и я делал массив (r, θ) c таким разрешением, чтобы линия определялась с точностью до пикселя. Т.е. в Вашем случае из одномерных гистограмм можно сложить двумерную и искать в ней локальные максимумы. Но, если чрезмерно поднять разрешение, гистограмма станет очень шумной и потребует сглаживания фильтром Гаусса, ширина которого зависит от требуемой точности разделения линий.
Линейная аппроксимация комбинации линий по набору зашумленных точек