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

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

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

Все другие методы подбора линий, обсуждаемые в этой главе, были разработаны для целей анализа изображений. Преобразование точки в кривую, описанное в п. 9.1.3, было предложено Дудой и Хартом (1972). Оно основано на преобразовании точки в прямую, представленном ранее Хохом в патенте США (1962) и введенном в более обычную техническую литературу РозенфельдЬм (1969). Некоторые методы, обсуждаемые в этой главе, насколько нам известно, в литературе не появлялись. О методе кластерного анализа сегментов линии из п. 9.1.3 нам сообщил Н. Дж. Нильсон; итеративный метод подбора концевой точки из п. 9.1.4 был подсказан нам Дж. Е. Форсеном. Идея разбиения границ объектов в точках большой кривизны основывается на очевидной важности этих точек для человеческого восприятия, что было установлено психологами, в частности Аттнивом (1954). Цань (1969) использовал этот подход для упрощения описаний кривых. Очень полезный метод цепного кодирования был разработан Фримэном (1961а, 196lb) и применен им же и его коллегами для решения таких задач, как головоломки типа «собирание картинки по кусочкам» (Фримэн и Гардер (1964)) и автоматическое сопоставление карт (Федер и Фримэн (1966)). Фримэн и Гласс (1969) использовали сплайны для исследования эффекта квантования при цепном кодировании кривых. Монтанари (1970а) создал итеративный метод для вычисления относительно гладкого приближения в виде ломаной для произвольной кривой, заданной в форме цепного кода. Монтанари (1970b) рассмотрел квантование кривых в общем случае и установил некоторые интересные предельные свойства. Наконец, мы должны упомянуть ценный обзор, подготовленный Левайном (1969), который охватывает общие проблемы получения описаний объектов.