Есть такая задача
Заданы точки, которые примерно описывают прямоугольник/квадрат
нужно найти прямоугольник (4 точки вершин), который будет максимально приближен к заданным точкам
пробовал преобразование Хафа, искал 4 прямых, находил их пересечение, как бы работает, даже неплохо, но плохая точность, то ли из-за дискретности угла/радиуса, то ли еще чего
крутится решения перебрать пары точек (соединять их прямыми), потом как-то выбрать 4 прямых, которых больше
или как-то бросать прямые и искать минимальное отклонение точек (сумму расстояний от точек до прямой)
Здравствуйте, alexwin, Вы писали:
A>пробовал преобразование Хафа, искал 4 прямых, находил их пересечение, как бы работает, даже неплохо, но плохая точность, то ли из-за дискретности угла/радиуса, то ли еще чего
Ты отбросил данное тебе в задаче условие связи — это не просто произвольные 4 прямые, а они образуют прямоугольник. Можно использовать этот факт при использовании преобразования Хафа.
Обычный Хаф отображает точки в плоскости (x, y) в синусоиды в двумерной области (θ, ρ) — (угол нормали с осью абсцисс, расстояние от начала координат). Это если искать фигуры типа «прямая». А тебе есть смысл искать фигуры типа «пара параллельных прямых». Тогда пространство Хафа станет трёхмерным: (θ, ρ₁, ρ₂) — (угол до нормали, расстояние до первой прямой, расстояние до второй прямой).
Здравствуйте, alexwin, Вы писали:
A>Есть такая задача A>Заданы точки, которые примерно описывают прямоугольник/квадрат
A>нужно найти прямоугольник (4 точки вершин), который будет максимально приближен к заданным точкам
A>
A>пробовал преобразование Хафа, искал 4 прямых, находил их пересечение, как бы работает, даже неплохо, но плохая точность, то ли из-за дискретности угла/радиуса, то ли еще чего
A>крутится решения перебрать пары точек (соединять их прямыми), потом как-то выбрать 4 прямых, которых больше A>или как-то бросать прямые и искать минимальное отклонение точек (сумму расстояний от точек до прямой)
A>у кого какие мысли будут?
прямоугольник имеет прмые углы, а просто пересечение 4-х прямых это многоугольник с 4 углами
Здравствуйте, Qbit86, Вы писали:
Q>Обычный Хаф отображает точки в плоскости (x, y) в синусоиды в двумерной области (θ, ρ) — (угол нормали с осью абсцисс, расстояние от начала координат). Это если искать фигуры типа «прямая». А тебе есть смысл искать фигуры типа «пара параллельных прямых». Тогда пространство Хафа станет трёхмерным: (θ, ρ₁, ρ₂) — (угол до нормали, расстояние до первой прямой, расстояние до второй прямой).
У меня могут быть совсем не прямоугольники (перспективные искажения), или прямоугольники и с отклонениями 10..20 градусов, т.е. нужно найти 4-ех угольник
p.s.
не совсем понял, что такое "расстояние до второй прямой"
Здравствуйте, alexwin, Вы писали:
A>У меня могут быть совсем не прямоугольники (перспективные искажения), или прямоугольники и с отклонениями 10..20 градусов, т.е. нужно найти 4-ех угольник
А, тогда всё-таки, обычный Хаф. Можно подумать ещё над такой оптимизацией. Сначала быстро пройти грубой сеткой, полученные результаты кластеризовать. Потом уже с маленьким шагом в пределах упомянутых 10–20 градусов пройти точнее.
Q>>Обычный Хаф отображает точки в плоскости (x, y) в синусоиды в двумерной области (θ, ρ) — (угол нормали с осью абсцисс, расстояние от начала координат). Это если искать фигуры типа «прямая». А тебе есть смысл искать фигуры типа «пара параллельных прямых». Тогда пространство Хафа станет трёхмерным: (θ, ρ₁, ρ₂) — (угол до нормали, расстояние до первой прямой, расстояние до второй прямой).
A>не совсем понял, что такое "расстояние до второй прямой"
Прямую можно задать двумя параметрами множеством способов; для преобразования Хафа удобнее всего нормальный вид, когда задаётся угол между нормалью к прямой и осью абсцисс и расстояние от прямой до начала координат. У двух параллельных прямых угол наклона нормали одинаков, отличаются только их расстояния до начала координат.
Здравствуйте, alexwin, Вы писали:
A>у кого какие мысли будут?
Я бы попробовал что-то типа RANSAC + МНК для поиска первой прямой. После выкидываем из выборки её точки. И снова RANSAC + МНК для второй прямой. И т.д.
Re: прямоугольник по точкам
От:
Аноним
Дата:
02.06.11 07:45
Оценка:
Здравствуйте, alexwin, Вы писали:
A>Есть такая задача A>Заданы точки, которые примерно описывают прямоугольник/квадрат
A>нужно найти прямоугольник (4 точки вершин), который будет максимально приближен к заданным точкам
A>
A>пробовал преобразование Хафа, искал 4 прямых, находил их пересечение, как бы работает, даже неплохо, но плохая точность, то ли из-за дискретности угла/радиуса, то ли еще чего
A>крутится решения перебрать пары точек (соединять их прямыми), потом как-то выбрать 4 прямых, которых больше A>или как-то бросать прямые и искать минимальное отклонение точек (сумму расстояний от точек до прямой)
A>у кого какие мысли будут?
Проще искать как в Procrust анализе:
задаете любой прямоугольник и ишите (по МНК) x,y перенос + поворот + масштабирование
Re[2]: прямоугольник по точкам
От:
Аноним
Дата:
02.06.11 08:57
Оценка:
А>Проще искать как в Procrust анализе: А>задаете любой прямоугольник и ишите (по МНК) x,y перенос + поворот + масштабирование
Функция квадрата расстояния от точек до произвольного прямоугольника не выражается элементарными функциями и не является дифференцируемой. Как предлагается найти решение?
Параметрами функции служат параметры задающие прямоугольник.
Для минимизации такой функции потенциально можно попробовать субградиентный метод со стартовых точек в узлах покрывающей сетки для поисков локальных минимумов(метод предполагает локальную выпуклость функции). Чисто градиентные методы вероятно не подойдут, так как в точке экстремума может отсутствовать производная. Субградиент в точке (т.е. при фиксированном прямоугольнике) можно посчитать аналитически . Обычно он будет равен градиенту, когда все точки имеют как ближайшую ровно одну прямую. Когда таких прямых становится две, возникает два вектора субградиента, как направления возрастания функции.
В целом такой подход сложен для реализации и требует подгонки параметров.
Здравствуйте, alexwin, Вы писали:
A>Есть такая задача A>Заданы точки, которые примерно описывают прямоугольник/квадрат
A>нужно найти прямоугольник (4 точки вершин), который будет максимально приближен к заданным точкам
A>
A>пробовал преобразование Хафа, искал 4 прямых, находил их пересечение, как бы работает, даже неплохо, но плохая точность, то ли из-за дискретности угла/радиуса, то ли еще чего
A>крутится решения перебрать пары точек (соединять их прямыми), потом как-то выбрать 4 прямых, которых больше A>или как-то бросать прямые и искать минимальное отклонение точек (сумму расстояний от точек до прямой)
A>у кого какие мысли будут?
Если без выпендрежа, то приблизь прямоугольник прямой, как бы это не смешно звучало, ты получишь хорошее приближение для оси твоего прямогольника.
Дальше ищешь минимальный описывающий {X_i,Y_i} и минимальный вложенный в твое множество прямоугольники {x_i,y_i}, формально решение для твоего будет представлять собой выпуклую комбинацию этих прямоугольников, но ты не заморачивайся. Выбери среди точек, принадлежащие 4 классам
{
1 : y > max(y_i), x > min(x_i), x < max(x_i)
2 : y < min(y_i), x > min(x_i), x < max(x_i)
3 : x > max(x_i), y > min(y_i), y < max(y_i)
4 : x < min(x_i), y > min(y_i), y < max(y_i)
}
Точки в каждом классе приблизь прямой каким нибудь робастным к малому числу выбросов МНК и получишь искомый четырехугольник (скорее всего прямые будут наклонены под небольшим углом к оси), а далее либо оставь его, либо замени прямоугольником усреднив параметры.
На окончательном этапе использую МНК чтобы получить прямую
y = a*x + b
столкнулся с очень странным поведением МНК
1.
вот на таком наборе точек
95, 12,
95, 19,
95, 25,
95, 30,
115, 35,
95, 40,
95, 45,
95, 51,
95, 58,
a==0
т.е. прямая как бы проходит под углом 0, что неправильно, значение выброса (115) может меняться (пробовал 99..115), но результат тот же
что это за фигня? какой-то не тот минимум МНК нашелся? как это побороть
2.
еще одна проблема, если из набора точек убрать последнюю, то все начинает как-бы работать, только прямая идет строго за выбросом, такое же поведение наблюдается и на других наборах точек, тут как не смотри, но это неправильно
1. Проверьте расчеты.
2. С выбросами МНК ВООБЩЕ не работает.
3. Может оптимизировать сразу 4х угольник вместо линий ?
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[3]: прямоугольник по точкам
От:
Аноним
Дата:
13.06.11 14:00
Оценка:
A>y = a*x + b
A>столкнулся с очень странным поведением МНК
A>1. A>вот на таком наборе точек A> 95, 12, A> 95, 19, A> 95, 25, A> 95, 30, A> 115, 35, A> 95, 40, A> 95, 45, A> 95, 51, A> 95, 58,
A>a==0
A>т.е. прямая как бы проходит под углом 0, что неправильно, значение выброса (115) может меняться (пробовал 99..115), но результат тот же A>что это за фигня? какой-то не тот минимум МНК нашелся? как это побороть
Чему ,по вашему, должно быть равно "a" в этом случае?
А>Чему ,по вашему, должно быть равно "a" в этом случае?
Ладно, на самом деле это сложный, но пока не главный вопрос. Проблема чуть шире.
У вас неправильный МНК.
К тем формулам (см. например http://en.wikipedia.org/wiki/Simple_linear_regression )
есть очень важное примечание: The above equations assume that {xi} data are known exactly whereas {yi} data have random distribution.
Это немножно другое, не так ли? В регрессии минимизируется расстояние по вертикали, а вам надо расстояние до прямой, что совсем другое дело.
Здравствуйте, Аноним, Вы писали:
А>а вам надо расстояние до прямой, что совсем другое дело.
а есть ли какие-то готовые рецепты, а то смотрю не так просто это
Re[6]: прямоугольник по точкам
От:
Аноним
Дата:
14.06.11 08:43
Оценка:
Здравствуйте, alexwin, Вы писали: A>Здравствуйте, Аноним, Вы писали: А>>а вам надо расстояние до прямой, что совсем другое дело. A>а есть ли какие-то готовые рецепты, а то смотрю не так просто это
В смысле? Готовые рецепты чего? По ссылке Deming Regression есть совсем готовая формула. Даже написано,что к счастью формула такая же простая как для линейной. (The Deming regression is only slightly more difficult to compute compared to the simple linear regression.)
Здравствуйте, Аноним, Вы писали:
А>В смысле? Готовые рецепты чего? По ссылке Deming Regression есть совсем готовая формула. Даже написано,что к счастью формула такая же простая как для линейной. (The Deming regression is only slightly more difficult to compute compared to the simple linear regression.)
Если бы у меня было много вычислительного времени, мало времени на ресёрч, а результат нужно что бы скорее всего заработал, я бы для таких картинок делал так:
Нашел бы для каждой точки самую близкую пару (две и более точки -- "группа").
Начал бы объединять имеющие общую точку группы выбирая на каждом шаге пару групп такую, что бы сумма квадратов расстояний от всех точек одной группы до некоторой прямой была минимальна.
Делал бы так, пока не осталось бы 4 группы.
Потом можно уточнить "границы" (множества точек, входящие в них) групп, перекидывая "крайние" точки групп из одной в другую таким же жадным алгоритмом (минимизируя на каждом шаге сумму квадратов отклонений).
Вроде как должно работать.
Еще сумасшедшие варианты в порядке мозгового шторма:
1. строим МНК прямую по всему "облаку точек". Запускаем Дугласса-Пеккера пока не появится 4 вершины ломаной. Вдруг эти вершины окажутся вершинами четырехугольника.
2. берем алгоритм построения минимальной охватывающей окружности. Три вершины будут лежать на ней. Четвертая вершина -- максимально удаленная точка от "диагонали"
