Линия, проходящая через заданные точки, так что

Question

Привет друзья….

Я пытаюсь найти угол внешней линии объекта в зеленой области изображения, как показано на изображении выше ...

Для этого я отсканировал зеленую область и получил точки (синие точки, как показано на рисунке) ...

Как видите, точки не образуют прямую линию, поэтому я не могу легко найти угол ...

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

Так, как я могу найти линию, чтобы каждая точка выставляла минимальное расстояние до нее ……?

Есть ли какой-нибудь алгоритм для этого или есть какой-то хороший способ, кроме этого?

Answer 1

Очевидным маршрутом было бы сделать линейную регрессию наименьших квадратов через точки.

Answer 2

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

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

С:

• n = ∑ 1
• sx = ∑ x
• sx2 = ∑ x ²
• sy = ∑ y
• sy2 = ∑ y ²
• sxy = ∑ x · y

Вы можете рассчитать дисперсию x и y и ковариацию:

• v _x = sx2 - ((sx * sx) / n)
• v _y = sy2 - ((sy * sy) / n)
• v _xy = sxy - ((sx * sy) / n)

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

• наклон = четырехугольник ((vx - vy) / vxy, vxy)
• intcpt = (sy - slope * sx) / n

Где quad () - функция, которая вычисляет корень квадратного уравнения x ² + b · x - 1 с тем же знаком, что и c.В Си это будет:

double quad(double b, double c)
{
    double b1;
    double q;

    b1 = sqrt(b * b + 4.0);
    if (c < 0.0)
        q = -(b1 + b) / 2;
    else
        q = (b1 - b) / 2;
    return (q);
}

Отсюда вы можете легко найти угол наклона вашей линии.

Answer 3

Хорошим вариантом может быть и грубое преобразование:

http://en.wikipedia.org/wiki/Hough_transform

Answer 4

Очевидно, что линия пройдет через усредненную точку (x_average, y_average).

Для направления вы можете использовать следующий алгоритм (полученный непосредственно из минимизации среднего квадратного расстояния между линией и точками):

dx[i]=x[i]-x_average;
dy[i]=y[i]-y_average;

a=sum(dx[i]^2-dy[i]^2);
b=sum(2*dx[i]*dy[i]);

direction=atan2(b,a);

Обычная линейная регрессия здесь не будет работать, поскольку она предполагает, что переменные не симметричны - одна зависит от другой, поэтому, если вы поменяете местами x и y, у вас будет другое решение.

Answer 5

Вы можете попробовать поискать "общее наименьшее число квадратов" или "наименьшее ортогональное расстояние", но когда я попытался это сделать, я не увидел ничего подходящего.

В любом случае предположим, что у вас есть точки x [], y [], и линия представлена ​​a * x + b * y + c = 0, где hypot (a, b) = 1. Наименьшая ортогональная линия расстояния тот, который минимизирует Sum {(a * x [i] + b * y [i] + c) ^ 2}. Некоторая алгебра показывает, что:

c - - (a * X + b * Y) где X - среднее значение x, а Y - среднее значение y.

(a, b) - собственный вектор C, соответствующий его меньшему собственному значению, где C - ковариационная матрица из x и y