9.4. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ СВЕДЕНИЯ

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), который охватывает общие проблемы получения описаний объектов.

9.4.2. ОПИСАНИЕ ФОРМЫ

Самые простые топологические свойства, обсуждавшиеся в разд. 9.3, использовались многими исследователями. Например, Гриниас и др. (1963) применяли топологические свойства для частичного описания знаков алфавита, написанных от руки в виде «печатных» букв и цифр. Фишлер (1963) использовал формулу Эйлера для проверки правильности описания объекта, полученного другими средствами. Мансон (1968) также использовал топологические

свойства для частичного описания «печатных» знаков алфавита, написанных от руки.

Теория линейных свойств была развита Минским и Пейпертом (1969) в попытке ответить на вопросы (наряду с многими другими) о способностях линейных схем к распознаванию образов. Эта общая проблема определения способностей данного класса абстрактных схем классифицировать образы была исследована также Блюмом и Хьюитом (1967), которые подошли к ней с точки зрения теории автоматов. Грей (1971) показал, что значительное число свойств объекта может быть вычислено с помощью правильно подобранных локальных операций, и описал специализированное вычислительное устройство для обработки изображений, реализующее эти операции. Ходе (1970) предложил измерять сложность некоторого свойства объекта, опираясь на размер логической формулы, необходимой для его определения.

Такие простые метрические свойства, как площадь, периметр, протяженность в заданном направлении и т. п., настолько фундаментальны, что они использовались в той или иной форме практически всеми исследователями, работавшими в данной области. Задача аппроксимации евклидовой метрики на квантованной плоскости изучалась Розенфельдом и Пфальцем (1968). Пойа и Сегё (1951) заинтересовались семейством физических следствий, проистекающих из того факта, что отношение толщины принимает максимальное значение для круга.

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

Преобразование «степного пожара», или «средних осей», было первоначально разработано Блюмом (1967). Калаби и Хартнет (1968) имели дело с математическими деталями его применения для описания подмножеств двумерной плоскости. Монтанари (1968) разработал эффективный метод нахождения, скелета квантованного объекта, сведя эту задачу к отысканию пути с минимальной стоимостью на графе. Монтанари (1969) построил метод определения скелета многоугольного объекта, основанный на аналитическом моделировании распространения.

Аналитический подход к описанию объекта использовался относительно небольшим числом исследователей, видимо, потому, что получаемые при нем коэффициенты разложения не всегда имеют ясную геометрическую интерпретацию. Брилл (1968) и Брилл и др. (1969) применяли разложение Фурье угловой естественной функции границы объекта. Более детальная и доступная обработка описана Цанем и Роскисом (1972). Аппроксимация с помощью моментов рассматривалась Ху (1962) и Альтом (1962).

Возможность применения интегральной геометрии для описания объектов была впервые указана в прекрасно написанной статье Новикова (1962). Некоторые из этих идей были обобщены Боллом (1962а, 1962b). Уонг и Стип (1969) объединили теорию последовательных решений с интегральной геометрией, существенно уменьшив тем самым число бросаний линии, необходимых при получении заданного описания. Кендалом и Мореном (1963) было написано хорошее математическое введение в предмет интегральной геометрии, которое содержит большую библиографию.

СПИСОК ЛИТЕРАТУРЫ

(см. скан)

(см. скан)

(см. скан)