9.2.2. ПОДБОР ЛИНИИ ПО СОБСТВЕННОМУ ВЕКТОРУ

Можно получить хороший аналитический способ аппроксимации множества точек прямой линией, если изменить слегка определение «наилучшего» подбора, использованное в методе МСКО. А именно будем считать, что линия аппроксимирует множество точек наилучшим образом, если при этом минимальна сумма квадратов расстояний по перпендикуляру от точек до линии. По некоторым причинам, которые вскоре прояснятся, мы будем называть эту линию наилучшим приближением по собственному вектору. Различие между определениями иллюстрируется рис. 9.2, на котором метод МСКО выбрал бы линию, минимизирующую сумму квадратов длин вертикальных сплошных отрезков, в то время как метод, который будет обсуждаться в данном пункте, минимизировал бы сумму квадратов длин пунктирных отрезков. Таким образом, подбор по собственному вектору в противоположность подбору по МСКО не зависит от выбора осей координат.

' Введем несколько обозначений. Как обычно, положим, что дано множество из п точек {(л:;, уі)), і=1, . . . , п, которое надлежит аппроксимировать прямой линией. Мы будем рассматривать і-ю точку (Хі, Уі) как вектор ѵ/, а расстояние по перпендикуляру от Vj до линии обозначим через di. (Таким образом, при заданном множестве точек di есть функция от этой линии. В данный момент мы не будем вводить явного обозначения этой зависимости.) Наша задача

П

состоит в отыскании линии, минимизирующей сумму

Вывод уравнения для наилучшей линии значительно упростится, если мы сразу же установим тот факт, что линия, минимизирующая d^, должна проходить через среднее (т. е. центр тяжести) точек Уі)}- Это можно легко показать следующими доводами. Предположим, что мы нашли линию, минимизирующую d^. Введем новую систему координат {ІІ, U?'), такую, что ось W параллельна наилуч-

шей линии. Пусть (щ, Wi) — координаты точки (хі, уі) в систем» ((У, W). В этой системе уравнение наилучшей линии имеет вид ы=Ыо где Ыо—некоторая константа; квадрат расстояния от і-н точки д<

 

наилучшей линии равен (ui—UoY- Элементарные вычисления показывают, что величина <Р минимальна, если щ представляет собой среднее значение координат U для п точек. Поэтому наилучшая линия проходит через центр тяжести, и, так как его положение не зависит от системы координат, наше первоначальное утверждение доказано.

в силу доводов, приведенных выше, мы можем на тех же основаниях предположить, что множество из п заданных точек имеет нулевое среднее. Наша задача теперь формулируется следующим образом: для данного множества точек с нулевым средним найти наилучшую прямую линию, проходящую через начало координат и минимизирующую величину d?. Пусть прямая, проходящая через начало координат, задается с помощью единичного нормального вектора N (как показано на рис. 9.3). Тогда, обозначая явно зависимость от N, получим

Симметричная матрица

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

Мы предоставляем читателю доказать в качестве упражнения, что в случае, когда |1N|1=1, эта квадратичная форма достигает минимума, если вектор N является собственным вектором матрицы S, относящимся к наименьшему собственному значению. Поскольку различные собственные векторы симметричных матриц ортогональны, прямая наилучшего приближения совпадает по направлению с главным собственным вектором матрицы 5, т. е. с собственным вектором, относящимся к наибольшему собственному значению. Тогда наши правила подбора наилучшей прямой сводятся к следующему:

1)   Привести точки к стандартному виду вычитанием среднего значения из координат каждой точки.

2)   Найти главный собственный вектор матрицы рассеяния для множества стандартизованных точек,

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

На рис. 9.4 приведен интересный пример, показывающий, насколько различными могут быть приближения, полученные по МСКО и по собственному вектору. Приближение по собственному вектору представляет собой как раз ту прямую, какую можно было бы заранее пожелать, а вариант, полученный по МСКО, настолько «не

верен», насколько это возможно. Такой слабый результат вызван только данной системой координат. Если поменять местами оси X и Y, то приближения, полученные по собственному вектору и по МСКО, будут полностью идентичны.

В заключение нашей дискуссии об аппроксимации по МСКО и по собственному вектору отметим, что оба метода основаны на аналитическом решении задачи минимизации некоторого критерия наилучшего приближения. При работе с дискретными изображениями во многих случаях желательно применение других критериев, которые не поддаются аналитическим методам ^). Часто удается минимизировать такой критерий методом поиска, при условии, конечно, что для поиска можно легко найти хорошую начальную точку. Пред-

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