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

Исследователи, работавшие в области анализа сцен, в течение некоторого времени открыли много задач, требующих методов решения, основанных на описании, а не на классификации. Первоначальная работа в этом направлении была основана на синтаксическом анализе, и, может быть, первый пример разложения картинки на первичные элементы был дан Гримсдейлом и др. (1959). Синтаксический подход получил дополнительный толчок в результате работ Кирша (1964) и Нарасимхана (1964, 1969), в которых были представлены формальные грамматики для целей обработки изображений. О применении синтаксических методов к задаче автоматического анализа хромосом сообщил Ледли (1964), который мог использовать только подход, основанный на описании границы. Шоу (1969, 1970) разработал развитый «язык описания изображений», фрагмент которого мы представили как метод стандартных точек притяжения. Гренандер (1969) дал абстрактное математическое описание механизма преобразования идеальных, или незашумленных, объектов в реальные. Пфальц и Розенфельд (1969) в попытке найти естественное обобщение синтаксического метода на два измерения ввели грамматику сетей. Эванса (1970) особенно интересовало определение по набору сцен грамматики, которая может их порождать. Уинстон (1970) использовал графы отношений в исследовании, направленном на построение абстрактных моделей объектов по набору сцен. Два хороших обзора по синтаксическим методам в анализе сцен были написаны Миллером и Шоу (1968), а также Фу и Свайном (1971). Фельдман и Грис (1968) написали, видимо, самое лучшее введение в обширную литературу по синтаксическому анализу и грамматическому разбору; Эрли (1970) описал особенно эффективный алгоритм грамматического разбора.

О применении трехмерных моделей в анализе сцен, которое в ретроспективе можно считать прямым подходом, не было известно ничего до появления имевшей большой резонанс статьи Робертса (1965). Дуда и Харт (1970) использовали частичные трехмерные модели для управления анализом сцены, - выполняемым подвижным роботом. Барроу и Поппельстоун (1971) хранили информацию о модели в виде графов отношений, описывающих скорее изображения объектов, чем сами объекты. Методы подбора модели часто требуют решения проблемы невидимых линий — проблемы определения той части трехмерного объекта, которая видна в данной проекции. Алгоритмы для решения такой задачи были описаны Уорноком (1968), Лоутрелом (1970) и Букнайтом (1970).

Кажущаяся простота многогранных объектов привлекла внимание многих исследователей. Хаффман (1971) интересовался в первую очередь формулировкой свойств изображений реальных трехгранных тел, чтобы определять, не показывает ли картинка невозможный

или бессмысленный, объект; наша процедура разметки линий основана прямо на его работе. Альтернативная процедура дана Клоувзом (1971). Простые эвристические правила, которые мы обсуждали, для объединения областей картинки в объекты были придуманы Гузманом (1968); он развил эти простые методы до высокой степени совершенства и построил алгоритм, способный анализировать идеальные картинки, достаточно сложные, чтобы вызвать по крайней мере кратковременное замешательство у человека. Брайс и Феннема (1970) включили простую версию этих правил в программу, использующую области в качестве основного вида данных на протяжении всего анализа сцены. Определение трехмерной структуры по расширенной монокулярной информации было исследовано Фальком (1970), который разработал метод дуальных графов для определения количества необходимой дополнительной информации. В неопубликованном отчете Хорна (1968) обсуждается использование данных фокусировки для определения информации о дальности.

Читатель, видимо, уже заметил, что некоторые методы, обсуждавшиеся в этой главе, в конце концов приводят к некоторому виду комбинаторного поиска. Грамматический разбор представляет собой существенно поисковый процесс; процедура разметки линий использует дерево поиска; и, хотя мы не показали это ясно, метод дуальных графов, анализирующий степени свободы в трехмерной структуре трехгранного тела, также связан с процессом поиска. Задачи комбинаторного поиска такого рода часто возникают в области искусственного интеллекта, и были исследованы общие методы для их эффективного решения. Превосходное введение в этот класс методов дано в монографии Нильсона (1971).

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

(см. скан)