Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 70

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 70)

Оиисаниз линии и формы таких числа с, и с„чтобы функция ошибки ~~ь~, [(с,+с,х;) — у,)' 1=! была минимальна. Другими словами, мы хотим найти такую прямую линию, чтобы сумма квадратов расстояний по вертикали от каж. дой из точек до этой линии была минимальна. Эта задача и другие задачи такого типа могут быть элегантно решены посредством пеев.

дообращеиия матрицы. В гл. 5 псевдообратная матрица была полу. чена чисто аналитическими методами. Потратим некоторое время, чтобы для разнообразия получить тот же результат геометрически. Пусть дано матричное уравнение Ап=Ь. Если мы обозначим через а', 1=1,..., й, столбцы матрицы А, а через и; составляющие вектора п, то обычная интерпретация этого уравнения будет заключаться в том, что величины и, представляют собой весовые коэффициенты, которые используются при суммировании в линейной комбинации столбцов матрицы А, в результате чего получается данный вектор Ь: ~ и;а' = Ь. с=и Если вектор Ь лежит внутри линейной оболочки, образованной столбцами матрицы А, уравнение, конечно, имеет решение.

Предположим, однако, что вектор Ь лежит вне линейной оболочки векторов (а'). В этом случае мы можем лишь пытаться найти «наилучшее приближение» к вектору Ь, какое только существует в пределах линейном оболочки векторов а'. А именно мы можем искать такие коэффициенты и, или такой вектор и, чтобы величина 11Ап — Ь!~' была минимальна. Ясно, что наилучшая оценка будет получена в случае, когда вектор ошибки (Ь вЂ” Ан) ортогонален линейной оболочке векторов (а'). Рис, 9.1 иллюстрирует эту ситуацию для случая, когда матрица А содержит только два трехмерных столбца и вектор Ь лежит вне их линейной оболочки.

Обозначим через и' оптимальный взвешивающий вектор, н тогда величина Ап* будет наилучшим приближением к Ь, какое только может быть найдено внутри линейной оболочки векторов (а'). Запишем условие ортогональности вектора (Ь вЂ” Апе) столбцам матрицы А следующим образом: А'(Ь вЂ” Ап') =О, илн А Ь А~Апе 9.2. Онисание линии Теперь, если матрица А'А имеет обратную, мы можем решить уравпение относительно н* и при этом получим и'=(А'А) 'А'Ь=А' Ь. Матрица Ат =(А'А)-'А' называется лсевдообратной по отношению к матрице А. Заметим, что если матрица А обратима, то Ат =А-'. Прежде чем покончить с псевдообращением, мы должны показать, что матрица (А'А) имеет обратную. В общем случае зта матрица обратима, если столбцы матрицы А линейно независимы, и в этом Рис.

9Л. Аиироисимация ио минимуму суммы квадратов ошибок, можно убедиться следующим простым рассуждением. Всякая матрица обратима, если ее обнуляющий множитель равен нулю, т. е., в нашем случае, если из равенства (АтА)«=-О следует, что вектор « сам равен нулю. Предположим противное: пусть «ФО. Поскольку столбцы матрицы А считаются линейно независимыми, из этого следует, что А«ФО. Тогда матричное произведение А'(А«) можно интерпретировать как вектор, составленный из скалярных произведений столбцов матрицы А на вектор А«.

Поскольку А«представляет собой не равный нулю вектор, лежащий в линейной оболочке столбцов матрицы А, он не может быть ортогонален всем столбцам. Следовательно, все скалярные произведения не могут быть равны нулю, т. е. А'А«ФО. Это противоречит предположению, а, следовательно, обнуляющий множитель матрицы А'А есть нулевой вектор, и эта матрица обратима. Подведем итоги обсуждению вопросов, связанных с псевдообращением. Предположив, что столбцы матрицы А линейно независимы, мы нашли, что величина йАа — Ь!!а минимальна при н=Ат Ь. Вернемся теперь к нашей исходной задаче подбора линий.

Предпо- Гя. 9. Олисания линии и формы ложим, что мы взяли наше множество точек ((хо у,)) и записали в форме Ап=Ь следующее матричное уравнение: 1 х, 1 х, 1 х„ А -Ун ь Если мы возьмем вектор ~ '1 равным Аг Ь, то можем быть уверены, Гс, (сг что величина 1(Ан — Ьйз минимальна '). Но с, + с,х, у, с+с х, у, ~~Ап — Ь~~з= с, +с,х„ н = ~~~~ ~((са+ сгх;) — уг]а, что представляет собой в точности критерий МСКО для коэффициентов с, и с, наилучшей линии. Следовательно, решение, соответствующее МСКО, получается умножением вектора Ь„составленного из значений координат )г, на матрицу, псевдообратную матрице А, составленной из значений координат Х: ~ '~ =А' Ь.

Подход на основе псевдообращения может быть легко распространен на случай аппроксимации множества точек по критерию МСКО с помощью многочлена. Пусть мы хотим найти такие коэффициенты с„с„..., сл, при которых сумма ~((с,+с,ха+о,х,'+... +саха) — у;]' минимальна. Мы будем поступать так же, как и в линейном случае, но на этот раз запишем матрицу А для значений координат Х в виде ') Замазал, что столбцы А ллнеало зависимы тогда к только тогда. когда яг=ха=... х„. 9.2. Опи«ение ливии а вектор и в виде са с, Положив и=А г Ь, мы сразу же найдем такие коэффициенты с«, с„.

..., св, при которых величина ЦАп — Ь!~'= ~~'„,'((с«+... +сех',) — у;)' 1=1 минимальна. 9.2.2. ПОДБОР ЛИНИИ ПО СОБСТВЕННОМУ ВЕКТОРУ Можно получить хороший аналитический способ аппроксимации множества точек прямой линией, если изменить слегка определение «наилучшегоэ подбора, использованное в методе МСКО. А именно будем считать, что линия аппроксимирует множество точек наилучшим образом, если при этом минимальна сумма квадратов расстояний по перпендикуляру от точек до линии.

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

Введем несколько обозначений. Как обычно, положим, что дано множество из и точек ((х„у;)), 1=1,..., и, которое надлежит аппроксимировать прямой линией. Мы будем рассматривать (-ю точку (хо у;) как вектор чь а расстояние по перпендикуляру от ч; до линии обозначим через 4. (Таким образом, при заданном множестве точек 4 есть функция от этой линии. В данный момент мы не будем вводить явного обозначения этой зависимости.) Наша задача « состоит в отыскании линии, минимизирующей сумму «(«=э~~~«(о Вывод уравнения для наилучшей линии значительно упростится, если мы сразу же установим тот факт, что линия, минимизирующая б«, должна проходить через среднее (т.

е. центр тяжести) точек ((хь уД). Это можно легко показать следующими доводами. Предположим, что мы нашли линию, минимизирующую У, Введем новую систему координат («У, Яг), такую, что ось 1в" параллельна наилуч- Гл. 9. Описания линии и»рармы шей линии. Пусть (иь и»») — координаты точки (х», у») в систем» (у, )р'), В этой системе уравнение наилучшей линии имеет вид и=и, где и,— некоторая константа; квадрат расстояния от»-й точки д» Рис. 9.2. Даа критерия наилучшего подбора, Рис. 9.3. Способ прсдстаалсиия линии. наилучшей линии равен (и» вЂ” и,)'.

Элементарные вычисления показывают, что величина»(а минимальна, если и, представляет собой среднее значение координат (л' для и точек. Поэтому наилучшая линия проходит через нентр тяжести, и, так как его положение не зависит от системы координат, наше первоначальное утверждение доказано. 9.2.

О!!а!!иие линии В силу доводов, приведенных выше, мы можем на тех же основаниях предположить, что множество из а заданных точек имеет нулевое среднее. Наша задача теперь формулируется следующим образом: для данного множества точек с нулевым средним найти наилучшую прямую линию, проходящую через начало координат и минимизирующую величину !1-". Пусть прямая, проходящая через начало координат, задается с помощью единичного нормального вектора Х (как показано на рис.

9.3). Тогда, обозначая явно зависимость от Х, получим !1! (Х) (Х,у )2 (Х!т!)а !Р(Х) = ~4(Х)= 1=! = ~~'„. (Х!т,)!=- с=! и = ~ (Х!т!)(т,'Х) = с-! юй = Х! Х (т!т0 Х. !=! Симметричная матрица и 5= ~ т!т', 1=! представляет собой матрицу рассеяния заданных п точек. Тогда наилучшая прямая определяется единичным нормальным вектором Х, минимизирующим величину ср(Х) =Х'5Х.

! 1ы предоставляем читателю доказать в качестве упражнения, что в случае, когда 11Х1~=1, эта квадратичная форма достигает минимума, если вектор Х является собственным вектором матрицы 5, относящимся к наименьшему собственному значению. Поскольку различные собственные векторы симметричных матриц ортогональны, прямая наилучшего приближения совпадает по направлению с главным собственным вектором матрицы 5, т. е. с собственным вектором, относящимся к наибольшему собственному значению. Тогда наши правила подбора наилучшей прямой сводятся к следующему: 1) Привести точки к стандартному виду вычитанием среднего значения из координат каждой точки. 2) Найти главный собственный вектор матрицы рассеяния для множества стандартизованных точек.

Гл. 9. Описания линии а формы 3) Линией наилучшего приближения является единственная прямая, проходящая через среднее множества точек н параллельная этому собственному вектору. На рис.9.4 приведен интересный пример, показывающий, насколько различными могут быть приближения, полученные по МСКО и по собственному вектору.

Приближение по собственному вектору представляет собой как раз ту прямую, какую можно было бы заранее пожелать, а вариант, полученный по МСКО, настолько «не- г'уСЮ Рнс. 9.4. Йва различных варианта подбора для одного и того же множества точек. верен>, насколько это возможно, Такой слабый результат вызван только данной системой координат.

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

Характеристики

Список файлов книги