Лучше всего подходит для пересечения нескольких линий

Question

Я пытаюсь решить следующую проблему:

• Я анализирую изображение и получаю из этого анализа набор сегментов
• Я хочу знать пересечение этих линий (лучше всего подходит)

Я использую для этой функции opencv cvSolve . Для достаточно хорошего ввода все работает отлично.

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

подробности:

• На верхнем левом изображении показаны «одинокие» фиолетовые линии, влияющие на результат (все строки используются в качестве входных данных).

• Верхнее правое изображение показывает, как одна фиолетовая линия (одна удаленная) может повлиять на результат.

• Нижнее левое изображение показывает, что мы хотим - пересечение линий, как и ожидалось (обе фиолетовые линии исключены).

• В правом нижнем изображении показано, как другая фиолетовая линия (другая удаляется) может повлиять на результат.

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

Спасибо

Юлиан

Answer 1

Алгоритм, который вы используете, находит, как описано в ссылке, решение проблемы методом наименьших квадратов.Это означает, что если будет больше точек пересечения, результатом будет среднее (для разумного определения среднего) реальных решений.

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

Answer 2

Общим ответом на подобные проблемы является алгоритм RANSAC ( вопрос, касающийся этого ), однако он имеет несколько недостатков, например, вам необходимо оценить такие вещи, как "«Ожидаемое количество выбросов» заранее.Другая проблема, которую я вижу с вашим примером, состоит в том, что удаление двух зеленых линий также приводит к довольно хорошей подгонке, так что это может быть более общей проблемой.

Answer 3

вы можете решить, используя SVD incase line1 = (x1, y1) - (x2, y2);line2 = (x2, y2) - (x3, y3)

пусть Ax = b где;

A = [-(y2-y1) (x2-x1);
     -(y3-y2) (x3-x2);
    .................
    .................] -->(nx2)
x = transpose[s t]     -->(2x1)
b = [-(y2-y1)x1 + (x2-x1)y1 ;
     -(y3-y2)x2 + (x3-x2)y2 ;
    ........................
    ........................] --> (nx1)

Example; Matlab Code

line1=[0,10;5,10]
line2=[10,0;10,5]
line3=[0,0;5,5]

A=[-(line1(2,2)-line1(1,2)),(line1(2,1)-line1(1,1));
-(line2(2,2)-line2(1,2)),(line2(2,1)-line2(1,1));
-(line3(2,2)-line3(1,2)),(line3(2,1)-line3(1,1))];


b=[(line1(1,1)*A(1,1))+ (line1(1,2)*A(1,2));
   (line2(1,1)*A(2,1))+ (line2(1,2)*A(2,2));
   (line3(1,1)*A(3,1))+ (line3(1,2)*A(3,2))];

[U D V] = svd(A)
bprime = U'*b

y=[bprime(1)/D(1,1);bprime(2)/D(2,2)]

x=V*y