9.2. ОПИСАНИЕ ЛИНИИ

В этом разделе мы рассмотрим различные способы описания линий или составленных из линий объектов. Общий подход будет заключаться в том, чтобы аппроксимировать объект одной или многими прямыми линиями (или, может быть, кривыми, которые описываются многочленами). Таким образом, имеются две задачи: как раз- бить исходный объект на сегменты и как подобрать линию для каждого сегмента. Мы будем обсуждать методы решения задач обоих видов, но должны сразу предупредить читателя, что в большинстве своем эти методы эвристические — они не облагорожены какой-либо лежащей в их основе теорией и должны применяться с разумной осторожностью. Мы начнем наше обсуждение со второй, более простой задачи и в связи с этим будем считать, что нам дано множество дискретных точек на плоскости (X, У), которое мы хотим аппроксимировать одной линией. В следующих пунктах описываются два аналитических подхода к этой задаче.

9.2.1. ПОДБОР ЛИНИЙ ПО МИНИМУМУ СУММЫ КВАДРАТОВ ОШИБОК

Классический метод подбора линий состоит в отыскании одиночной линии, дающей минимальную сумму квадратов ошибок (МСКО). Говоря более точно, нам дано множество точек , лежащих на плоскости, и мы пытаемся отыскать два

таких числа чтобы функция ошибки

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

Пусть дано матричное уравнение

Если мы обозначим через столбцы матрицы А, а через составляющие вектора и, то обычная интерпретация этого уравнения будет заключаться в том, что величины представляют собой весовые коэффициенты, которые используются при суммировании в линейной-комбинации столбцов матрицы А, в результате чего получается данный вектор b:

Если вектор b лежит внутри линейной оболочки, образованной столбцами матрицы А, уравнение, конечно, имеет решение. Предположим, однако, что вектор b лежит вне линейной оболочки векторов . В этом случае мы можем лишь пытаться найти «наилучшее приближение» к вектору b, какое только существует в пределах линейной оболочки векторов а. А именно мы можем искать такие коэффициенты или такой вектор и, чтобы величина была минимальна. Ясно, что наилучшая оценка будет получена в случае, когда вектор ошибки ортогонален линейной оболочке векторов . Рис. 9.1 иллюстрирует эту ситуацию для случая, когда матрица А содержит только два трехмерных столбца и вектор b лежит вне их линейной оболочки. Обозначим через и оптимальный взвешивающий вектор, и тогда величина будет наилучшим приближением к b, какое только может быть найдено внутри линейной оболочки векторов . Запишем условие ортогональности вектора столбцам матрицы Л следующим образом:

или

Теперь, если матрица имеет обратную, мы можем решить уравнение относительно и и при этом получим

Матрица называется псевдообратной по отношению к матрице . Заметим, что если матрица Л обратима, то Прежде чем покончить с псевдообращением, мы должны показать, что матрица имеет обратную. В общем случае эта матрица обратима, если столбцы матрицы Л линейно независимы, и в этом можно убедиться следующим простым рассуждением.

Рис. 9.1. Аппроксимация по минимуму суммы квадратов ошибок.

Всякая матрица обратима, если ее обнуляющий множитель равен нулю, т. е., в нашем случае, если из равенства следует, что вектор v сам равен нулю. Предположим противное: пусть Поскольку столбцы матрицы считаются линейно независимыми, из этого следует, что Тогда матричное произведение можно интерпретировать как вектор, составленный из скалярных произведений столбцов матрицы Л на вектор . Поскольку представляет собой не равный нулю вектор, лежащий в линейной оболочке столбцов матрицы , он не может быть ортогонален всем столбцам. Следовательно, все скалярные произведения не могут быть равны нулю, т. е. . Это противоречит предположению, а, следовательно, обнуляющий множитель матрицы есть нулевой вектор, и эта матрица обратима.

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

что мы взяли наше множество точек и записали в форме следующее матричное уравнение:

Если мы возьмем вектор равным b, то можем быть уверены, что величина минимальна 1). Но

что представляет собой в точности критерий МСКО для коэффициентов наилучшей линии. Следовательно, решение, соответствующее МСКО, получается умножением вектора b, составленного из значений координат Y, на матрицу, псевдообратную матрице А, составленной из значений координат X:

Подход на основе псевдообращения может быть легко распространен на случай аппроксимации множества точек по критерию МСКО с помощью многочлена. Пусть мы хотим найти такие коэффициенты при которых сумма

минимальна. Мы будем поступать так же, как и в линейном случае, но на этот раз запишем матрицу А для значений координат X в виде

а вектор и в виде

Положив мы сразу же найдем такие коэффициенты при которых величина

минимальна.

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

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

Введем несколько обозначений. Как обычно, положим, что дано множество из точек , которое надлежит аппроксимировать прямой линией. Мы будем рассматривать точку как вектор а расстояние по перпендикуляру от v до линии обозначим через (Таким образом, при заданном множестве точек есть функция от этой линии. В данный момент мы не будем вводить явного обозначения этой зависимости.) Наша задача состоит в отыскании линии, минимизирующей сумму

Вывод уравнения для наилучшей линии значительно упростится, если мы сразу же установим тот факт, что линия, минимизирующая должна проходить через среднее (т. е. центр тяжести) точек Это можно легко показать следующими доводами. Предположим, что мы нашли линию, минимизирующую Введем новую систему координат , такую, что ось W параллельна наилучшей

линии. Пусть координаты точки в систем» . В этой системе уравнение наилучшей линии имеет вид где некоторая константа; квадрат расстояния от точки наилучшей линии равен

(см. скан)

Рис. 9.2. Два критерия наилучшего подбора.

(см. скан)

Рис. 9.3. Способ представления линии.

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

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

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

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

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

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

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

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

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

Рис. 9.4. Два различных варианта подбора для одного и того же множества точек.

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

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

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

9.2.3. ПОДБОР ЛИНИЙ ПОСРЕДСТВОМ КЛАСТЕРНОГО АНАЛИЗА

Ранее мы полагали, что все точки объекта должны аппроксимироваться единственной линией. Обратим теперь наше внимание к более общей задаче описания объекта посредством совокупности линий. А именно это означает, что мы должны уметь разделять объект на такие подмножества, что каждое из них может быть хорошо представлено единственной линией. Существует много методов для выполнения этой операции. В следующих пунктах описываются два метода, основанные на кластерном анализе. Идея, лежащая в основе каждого из них, заключается в том, чтобы перевести исходный объект в новое пространство, в котором коллинеарные подмножества объекта образуют группы или кластеры. Эти кластеры затем могут быть найдены, например, с помощью методов кластерного анализа, подобных описанным в гл. 6.

9.2.3.1. Преобразование точек в кривые

Предположим, как обычно, что нам дано множество из точек объекта , которое мы хотим аппроксимировать некоторым еще нуждающимся в определении числом прямых линий. Один класс методов связан с переводом каждой точки в некоторую кривую в новом пространстве параметров таким образом, чтобы коллинеарные точки превращались в пересекающиеся кривые. Если несколько кривых пересекаются, их общая точка определяет в некоторой системе параметров уравнение прямой линии на плоскости содержащей коллинеарные точки.

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

выглядит следующим образом:

В соответствии с этим мы переводим каждую точку в кривую на плоскости , определяемую уравнением

Заметим, что это преобразование сводится всего лишь к тому, что мы иначе интерпретируем те же величины: мы считаем величины фиксированными, а величины — переменными. Если у нас есть несколько точек на плоскости (X, Y), лежащих на прямой , то соответствующие им кривые на плоскости должны проходить через точку Выражаясь формальным языком, для нашего преобразования образ точки есть кривая

или, поскольку точка лежит на линии, определяемой параметрами

Рис. 9.5. Нормальная система параметров прямой линии.

Но последнее равенство справедливо при поэтому образы всех коллинеарных точек проходят через точку

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

кривая заносится в массив посредством увеличения содержимого счетчиков в каждой клетке вдоль кривой. Коллинеарные точки создадут в результате большие числа в некоторых счетчиках. Приближенно коллинеарные точки создадут моды в двумерной гистограмме, отображаемой массивом. Заметим, кстати, что нам нужно рассматривать значения 8 только от 0 до а значения от 0 до величины максимального диаметра сетчатки. Более того, метод изотропен в том смысле, что он не чувствителен к ориентации координатных осей. Эти качества представляют собой важное свойство нормальной системы параметров прямой линии, и они делают такую систему более удобной, чем, скажем, известный способ представления прямой через наклон и точку пересечения с осью координат. Другие сведения о нормальной форме прямой линии мы получим позже, когда будем обсуждать интегральные геометрические методы.

9.2.3.2. Кластерный анализ сегментов

Мы расширим временно основные правила подбора линий с тем, чтобы включить задачу подбора линий для совокупности коротких (как правило) прямых сегментов. Довод в пользу такой постановки заключается в том, что иногда изображение преобразуется в набор коротких прямых сегментов посредством операции сравнения с эталоном. В таком случае следующий очевидный шаг может состоять в аппроксимации коллинеарных сегментов прямыми линиями. Ключ к тому, как это можно было бы сделать, дает специальный способ представления сегментов, показанный на рис. 9.5. Мы будем представлять данный сегмент в координатах , где — длина вектора, проведенного из начала координат по нормали к прямой, содержащей сегмент, угол наклона этой нормали относительно оси X. Мы сразу же видим, что такой способ представления сегментов неоднозначен. В самом деле, все коллинеарные сегменты дадут одни и те же координаты (0, р). Это наводит на мысль, что почти коллинеарные сегменты могут быть найдены посредством представления каждого из них в виде точки на плоскости и выделения кластеров для этих точек. Один из недостатков этого метода состоит в том, что он также чувствителен к выбору координатных осей на плоскости изображения. Если сегмент расположен далеко от начала координат, небольшая ошибка в определении его ориентации приводит к большой ошибке в определении его координаты р.

9.2.4. СЕГМЕНТАЦИЯ ЛИНИИ

В некоторых случаях задача разбиения объекта на подмножества может рассматриваться как задача сегментации. Мы, например, имеем основания ожидать, что точки объекта скорее лежат на

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

9.2.4.1. Итеративный подбор концевых точек

В своей простейшей форме метод итеративного подбора концевых точек заключается в следующем. Нам дано, как обычно, множество из точек, и мы проводим первую линию, например линию АВ, соединяя просто концевые точки множества.

Рис. 9.6. Итеративный подбор концевых точек.

Вычисляются расстояния от каждой точки до этой линии, и, если все они меньше некоторого установленного заранее порога, процесс закончен. Если это не так, мы находим точку, наиболее удаленную от АВ, например точку С, и заменяем первоначальную линию двумя новыми линиями АС и СВ. Этот процесс затем повторяется отдельно для двух новых линий, возможно, с различными порогами. Рис. 9.6 иллюстрирует этот метод. Исходная линия А В разбивается на AС и СВ, а затем линия СВ разбивается на CD и DB. Конечным результатом является последовательность связанных сегментов AC, CD и DB.

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

котором для уточнения позиций сегментов линии используется более изощренный алгоритм. Другими словами, итеративный алгоритм можно применять для приближенного подбора и приближенного определения точек излома, а затем улучшать аппроксимацию во время второго прохода. Более серьезный недостаток итеративного процесса заключается в том, что единственная «дикая» точка может резко изменить конечный результат. Хотя с этим также можно бороться, например с помощью процесса предварительного сглаживания, та же самая основная проблема встречается и во многих других алгоритмах обработки изображений. Простота часто достигается ценой принятия решения на основании только локальной информации об изображении. Поэтому область применения простых алгоритмов ограничена случаями, когда исходные данные в основном не содержат шумов.

9.2.4.2. Точки максимальной кривизны

Нам хотелось бы рассмотреть здесь задачу сегментации несколько иного рода. Пусть задан гладкий контур (он может быть получен, например, с помощью процедуры прослеживания контура). В чем может заключаться разумный способ разбиения этой кривой на последовательные прямолинейные отрезки? Один способ, подсказанный психологическими экспериментами, состоит в том, чтобы разбить кривую в точках высокой кривизны и соединить точки излома прямыми линиями. Ценность этого метода подтверждается известным рисунком, принадлежащим Аттниву, который построен в соответствии с описанным правилом (рис. 9.7).

Рис. 9.7. Пример Аттнива (из книги Аттнива, 1954).

Мало кто не узнает здесь спящую кошку. С математической точки зрения такой подход связан с так называемым естественным уравнением кривой. Естественное уравнение кривой определяет ее кривизну как функцию длины дуги. Следовательно, обсуждаемый метод, по существу, эквивалентен заданию естественного уравнения кривой ее экстремальными точками. (Мы оставили без внимания некоторые математические трудности, связанные с определением кривизны в точке пересечения двух прямых линий.)

9.2.5. ЦЕПНОЕ КОДИРОВАНИЕ

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

Рис. 9.8. Цепное кодирование.

Для представления кривой отбираются узлы сетки, ближайшие к каждому пересечению. Рис. 9.8, а показывает выделенные узлы для данной кривой. Затем мы кодируем последовательность узлов восьмеричными числами, обозначая направления от одного узла к другому в соответствии с кодами, показанными на рис. 9.8, б. Так, например, цепное кодирование данной кривой начиная с крайней нижней точки дает последовательность 1, 1, 2, 1, 0. Заметим, что такая схема может рассматриваться как дискретный вариант естественного уравнения кривой. Код определяет угол (в другом варианте — изменение угла) как функцию длины дуги с учетом того, что диагональные отрезки в раз длинней, чем вертикальные и горизонтальные.

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

выражения

где

Заметим, что, если две кривые идентичны, их цепная функция взаимной корреляции достигает своего максимального значения, равного 1. В более общем случае две цепи имеют разную длину, и нам будет нужно двигать одну цепь относительно другой с тем, чтобы найти наилучщее соответствие. В связи с этим мы обобщим определение цепной функции взаимной корреляции следующим образом:

где k — длина общего участка двух последовательностей. Таким образом, наилучшее соответствие достигается вычислением величины для всех значений сдвига j и выбором максимальной из них. Главное ограничение эффективности цепной функции взаимной корреляции связано с тем, что обе кривые должны иметь одинаковый масштаб и ориентацию. Если хотя бы одно из этих условий нарушается, то либо следует отвергнуть этот метод, либо нужно повернуть на плоскости одну из последовательностей и (или) изменить ее масштаб относительно другой.