Into the Human Representation

And Processing of Visual Information

David Man-Late of the Massachusetts Institute of Technology

W H Freeman and Company New York

Д.МАРР

ЗРЕНИЕ

Информационный подход

к изучению

представления и обработки

зрительных образов

Перевод с английского

Н. Г. Гуревич

под редакцией канд. физ.-мат. наук

И. Б. Гуревича

 

Москва «Радио и связь» 1987

УДК 007.001.362

Д. Марр. Зрение. Информационный подход к изучению представления и обработки зрительных образов: Пер. с англ. - М.: Радио и связь, 1987. - 400 с: ил.

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

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

Табл. 6. Ил. 149. Библиог. 274 назв.

Редакция переводной литературы

_м 1502000000-207 ₅. _g? 046 (01)-87

© 1982 by W. H. Freeman and Company

© Перевод на русский язык, предисловие к русскому изданию, примечания редактора и переводчика. Издательство " Радио и связь", 1987

ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ ЗРЕНИЕ КАК ИНФОРМАЦИОННЫЙ ПРОЦЕСС

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

Н. Винер " Я - математик"

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

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

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

5

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

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

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

6

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

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

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

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

При анализе пространственной организации изображения ставятся две основные задачи: построение характерных объектов, выделяемых наизобра-

7

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

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

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

8

не зависящее от направления наблюдения объекта, т. е. финальное описание привязано к объекту.

6. Информационная теория зрения предусматривает разбиение процесса получения информации о форме по изображению на три этапа, соответствующие используемым видам представления: 1) представление характеристик двухмерного изображения (типа изменений значений яркости и локальных геометрических свойств); 2) представление характеристик видимых поверхностей в системе координат наблюдателя (типа ориентации поверхности, расстояния от наблюдателя, скачкообразных изменений значений этих параметров, коэффициентов отражения поверхности, освещения); 3) представление в системе координат объекта трехмерной структуры и организации формы наблюдаемого объекта в сочетании с каким-либо описанием свойств его поверхности.

Таким образом, объяснение феномена зрения в рамках информационной теории Д. Марра основывается на постановке следующей проблемы: какие задачи решает мозг человека в то время, когда человек " видит"? Утверждается, что " видение" — это построение эффективных символьных описаний внешнего мира по его изображениям. Поэтому существенной особенностью зрения оказывается выбор представлений для различных видов информации, содержащихся в наблюдаемой сцене. Постулируется универсальная структура процесса извлечения информации о форме объектов из изображений, в соответствии с которой процесс анализа проходит через смену трех представлений: 1) первоначального эскиза, представляющего в явном виде изменения яркости и локальные двухмерные геометрические свойства изображения; 2) 2, 5-мерного эскиза, представляющего в системе координат наблюдателя глубину, ориентацию и нарушения непрерывностей наблюдаемых поверхностей; 3.) трехмерной модели, представляющей в координатах объекта описание трехмерной структуры и организации его наблюдаемой формы. Решающим элементом информационного подхода к определению процессов, обеспечивающих построение таких представлений, является выделение действенных ограничений, отражающих свойства реального мира и предоставляющих дополнительную информацию, позволяющую получать искомые характеристики наблюдаемых сцен. После того как сформулирована информационная теория процесса, можно сконструировать алгоритмы, реализующие его, и сопоставить их характеристики с характеристиками зрительной системы человека.

Основными отличительными свойствами концепции Д. Марра являются: использование нескольких уровней объяснения феномена зрения; определение общей структуры информационных процессов, составляющих основу зрения; использование реальных физических ограничений в качестве основы для получения информации об истинных свойствах сцены по ее изображению; осознание дуализма процессов обработки информации и ее представлений, присущего зрению.

Информационная теория зрения создана Д. Марром в классических традициях кибернетики, традициях, составляющих концептуальную основу совре-

менных работ в области искусственного интеллекта и информатики в целом, в стиле и духе работ Н. Винера, А. Ляпунова и У. Маккаллока (последний, кстати, был основателем и руководителем лаборатории, известной ныне как Лаборатория искусственного интеллекта Массачусетсского технологического института, в которой родилась и реализовалась концепция Марра). Кибернетика в момент своего рождения (в конце 40-х — начале 50-х годов нашего века) привлекла всеобщее внимание главным образом потому, что указала на подобие процессов управления и связи в машинах, живых организмах и обществах и на то, что эти процессы имеют информационный характр, т. е. представляют собой по существу процессы сбора, передачи, хранения и обработки информации. Это придало новые стимулы изучению человека, его мышления, процессов принятия решений, распознавания, т. е. всего того, что, как утверждает кибернетика, происходит на основе информационных процессов. Кибернетики, обращаясь к наукам, традиционно занимавшимся изучением человека, главным образом к биологии и психологии, рассчитывали получить у них ответы, касающиеся специфических человеческих способов реализации информационных процессов, и намеревались использовать полученные сведения при разработке программ для того, что теперь называют системами искусственного интеллекта (в особенности — экспертными системами), и создании соответствующих технических устройств. В этой же связи возникла и проблема " вычислительные машины и мышление", которая в чистом виде выглядит следующим образом: создать на основе вычислительных машин системы, способные выполнять отдельные функции, традиционно считавшиеся интеллектуальной прерогативой человека.

Ход работ в области сложных методов обработки информации (таким образом в 50—60-е годы определялись работы в области искусственного интеллекта), а также все развитие кибернетики в целом привели к некоторой переориентации целей искусственного интеллекта. В силу ряда обстоятельств создание " мыслящей машины" постепенно теряло значение. Во-первых, ни науки о человеке, ни техническая ветвь кибернетики не были еще готовы к тому, чтобы совместно решать эту задачу. Во-вторых, расширение сфер приложений кибернетики выдвигало собственные задачи и усугубляло разрыв кибернетики с проблемой человека. В-третьих, интенсивное развитие вычислительной техники требовало разработки вычислительных систем, совершенствования методов работы с машинами, создания систем программного обеспечения, языков, инструментальных средств, а также развития теоретического аппарата информатики. Более подробные сведения об этих процессах, а также их критический анализ можно найти в работах [Ш—П5]¹.

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

См. список литературы к предисловию. 10

века. Это относится в полной мере к проблеме зрения и соответственно к распознаванию образов в целом как к задаче, решение которой является конечной целью зрительного процесса.

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

Основная часть задач анализа изображений решалась в рамках так называемой проблемы машинного зрения, которая в целом формулировалась как понимание сцены, " описываемой" изображением. На протяжении 50—70-х годов в рамках этой общей проблемы выделились, хотя и не очень четко разделились, такие направления, как обработка изображений, распознавание образов, анализ сцен, интерпретация изображений, оптическая обработка информации, обработка видеоинформации и понимание изображений.

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

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

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

На начальном этапе работы над проблемой распознавания изображений было затрачено много усилий на попытки построить процесс распознавания, ис-

11

пользуя понятие " образ". Они сводились в основном к следующим двум направлениям:

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

2) построению системы распознавания на основе имитации способностей человека к распознаванию, т. е. путем выявления эвристических беспереборных приемов обработки и анализа информации, свойственных зрительной системе человека, и использования этих эвристик, их вариантов и обобщений в качестве алгоритмов распознавания.

Последнее направление существенно зависело от успехов в области психофизиологии и психофизики восприятия, а именно от выяснения того, как объекты внешнего мира представляются в человеческом мозге, какими приемами и принципами пользуется человек при восприятии и различении зрительных образов: воспринимает ли он образ " в целом" либо ориентируется на какие-то специфические признаки и, если верно последнее, то каким способом он их выбирает, выделяет, преобразует и использует.

Начиная со второй половины 50-х и в течение 60-х годов это направление стало областью интенсивных исследований. В наиболее целостном виде методология эвристического программирования была реализована в так называемом перцептронном подходе к распознаванию. Перцептрон, предложенный американским ученым Ф. Розенблаттом в 1957 году в качестве относительно простой модели, воспроизводящей некоторые принципы работы мозга человека, послужил основой для создания целого класса обучающихся и самообучающихся распознающих систем, став своего рода мостом* между эвристическим подходом и математическим исследованием процедур обучения в системах распознавания [П6]. Перцептрон явился первой серьезной альтернативой чисто эмпирическому подходу к синтезу алгоритмов распознавания, однако тщательное теоретическое изучение этой модели показало, что круг интересных практических задач, поддающихся решению в ее рамках, довольно узок. Отметим, что существенный вклад в изучение перцептронов внесли чл.-корр. АН УССР А. Г. Ивахненко [П7] и американские ученые М. Минский и С. Пейперт [П8].

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

главным образом на попытках переносить в эту область методы обработки одномерных сигналов и спонтанных усилиях, связанных с введением в процесс распознавания структурной информации. Господствующим же стало направление обработки изображений, поскольку чисто исторически сложилось так, что работой с изображениями до недавнего времени занимались в основном специалисты по обработке сигналов, телевизионным и оптическим системам, которые принесли в эту область привычный им приоритет разработок измерительной аппаратуры. Довольно часто " обработка" сводится к измерению и воспроизведению сигнала, а основными математическими средствами анализа продолжают служить спектральный анализ и различные разновидности статистических фильтров. В результате решение внутренних, технических задач полностью доминировало и выдавалось за продвижение к конечной цели — разработке систем машинного зрения (иначе — автоматизированных систем обработки изображений (АСОИЗ)).

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

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

Современное состояние теории распознавания полностью определяется результатами советской школы распознавания, созданной чл.-корр. АН СССР Ю. И. Журавлевым и развиваемой им и его учениками (см., например, работы [П9-П11]).

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

13

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

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

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

п. а) вида.

В основе современной математической теории распознавания лежит так называемый алгебраический подход, предложенный Ю. И. Журавлевым [П9]. Алгебраический подход к распознаванию позволяет получать алгоритмы, обеспечивающие выделение из представленных данных всей полезной информации и получение решения, точно соответствующего " информативности" этой информации. Такое решение характеризуется минимальной вычислительной сложностью, устойчивостью по отношению к шуму и искажениям исходной информации и статистической надежностью. В процессе решения

14

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

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

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

В рамках алгебраического подхода к обработке информации в задачах распознавания и прогнозирования для работы с изображениями сформулирован так называемый дескриптивный подход [П12, ШЗ]. Он предусматривает решение задач, связанных с получением формальных описаний изображений как объектов распознавания и с формированием и выбором процедур распознавания с.помощью изучения внутреннего строения, структуры и содержания изображения как результата тех операций, которые позволяют построить изображение из подизображений или объектов более простой природы, т. е. непроизводных элементов и объектов, выделяемых на изображении на различных этапах работы с ним (в зависимости от того, применительно к какому морфологическому или масштабному уровню формируется модель изображения). Поскольку этот способ характеризации изображения является операциональным, весь процесс анализа и распознавания изображений, включая построение формального описания — модели изображения, рассматривается как реализация на изображении некоторой системы преобразований, которая определена на классах эквивалентности, представляющих ансамбли допустимых изображений. Следовательно, в процессе распознавания используется иерархия формальных опиеаний изображений, т. е. используются модели изображений, относящиеся к разным морфологическим и масштабным уровням представления — многоуровневые модели, позволяющие в процессе распознавания выбирать и изменять необходимую степень подробности описания объекта распознавания.

Дескриптивный подход к распознаванию изображений характеризуется следующими основными особенностями: а) построение формального описания (модели изображения как объекта распознавания) становится самосто-

15

ятельной задачей, которая ставится и разрешается в процессе распознавания; б) модель изображения должна включать структурную (в частности, реляционную) информацию, т. е. представлять собой некоторую формальную конструкцию, при получении которой все время учитываются иерархичность структуры объекта распознавания и отношения, существующие между отдельными элементами этой иерархии как в пределах одних и тех же морфологических и масштабных уровней, так и между ними; в) изменяются понятия начальной и финальной информации; процесс распознавания изображений имеет многоуровневый характер: исходная модель изображения в результате применения к ней процедуры распознавания преобразуется в модель изображения, относящуюся к другому морфологическому (масштабному) уровню; к полученной модели снова применяется процедура распознавания и т. д., причем правило остановки определяется видом и типом результатов, требующихся при решении поставленной задачи; г) тесная связь процессов описания и распознавания изображений и необходимость включения в итерационный процесс распознавания моделей изображений, относящихся к различным морфологическим (масштабным) уровням, означают, что модель алгоритма распознавания изображений включает, помимо распознающего оператора и решающего правила, оператор, осуществляющий приведение изображения к виду, удобному для распознавания; д) построение распознающего алгоритма из элементарных распознающих операторов выполняется в соответствии со структурой, обеспечивающей реализацию механизма реверсивного алгебраического замыкания [ПИ]; в качестве элементарных распознающих операторов используются алгебраические преобразования двух видов — формирования и анализа; механизм реверсивного алгебраического замыкания создает общую структуру алгоритма, фиксирующую отдельные этапы процесса распознавания изображения и их последовательность, а также структуру процедур, составляющих отдельные этапы процесса; сам же распознающий алгоритм в целом и процедуры отдельных этапов могут варьироваться; е) ввиду итерационности процесса распознавания изображений на каждом шаге итерации реализуются все три этапа, предусмотренные методологией алгебраического подхода (как для распознающего оператора, так и для оператора приведения изображения к виду, удобному для распознавания).

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

16

го теперь возможность познакомиться с монографией, завоевавшей абсолютное первенство по цитированию в литературе по анализу и распознаванию изображений.

И. Б. Гуревич

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

Ш. Вычислительные машины и мышление/Под ред. Э. Фейгенбаума и Дж. Фельдмана; Пер. с англ. под ред. Э. М. Бравермана, А. В. Напалкова и Ю. В. Орфеева. - М.: Мир, 1967. - 552 с.

П2. Фейгенбаум Э. А. Искусственный интеллект; темы исследований во втором десятилетии развития//Кибернетический сборник: Сб. переводов. Новая серия/Под ред. А. А. Ляпунова и О. Б. Лупанова. - М., 1973. - Вып. 10. - С. 171-203.

ПЗ. Дрейфус X. Чего не могут вычислительные машины. Критика искусственного разума: Пер. с англ./Общ. ред., послесловие и примечания Б. В. Бирюкова. - М.: Прогресс, 1978. - 336 с.

П4. Вейценбаум Дж. Возможности вычислительных машин и человеческий разум. От суждений к вычислениям: Пер. с англ./Иод ред. А. Л. Горелика. — М.: Радио и связь, 1982. - 368 с.

П5. The Study of Information. Interdisciplinary Messages/Ed by F. Machlup and U. Mansfield. John Wiley and Sons, 1983. - 744 p.

П6. Розенблатт Ф. Принципы нейродинамики. Перцептроны и теория механизмов мозга: Пер. с англ./Под ред. С. М. Осовца. - М.: Мир. 1965. - 480 с.

П7. Перцептрон - система распознавания образов/Под общ. ред. А. Г. Ивахненко. -Киев: Наукова д^мка, 1975. - 432 с.

П8. Минский М., Пейперт С. Персептроны: Пер. с англ./Под ред. В. А. Ковалевского. -М.: Мир, 1971.- 264 с.

П9. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания и клас-сификации//Проблемы кибернетики: Сб. статей. - М.: Наука, 1978. - Вып. 33. -С. 5 - 68.

П10. Гуревич И. Б. Методы распознавания в анализе изображений//Автоматизированные системы обработки изображений (АСОИз-86): Тез. докл. II Всесоюз. конф. (Львов, сентябрь 1986 г.). - М.: Наука, 1986. - С. 124-126.

ПИ. Рудаков К. В. О применении алгебраической теории распознавания при обработке изображений//Автоматизированные системы обработки изображений (АСОИз-86): Тез. докл. II Всесоюз. конф. (Львов, сентябрь 1986 г.). - М.: Наука, 1986. - С. 168 - 169.

П12. Горелик А. Л., Гуревич И. Б., Скрипкин В. А. Современное состояние проблемы распознавания. Некоторые аспекты. - М.: Радио и связь, 1985. - 162 с. - (Кибернетика).

П13. Гуревич И. Б. Анализ изображений методом реверсивного алгебраического замыка-ния//Проблемы искусственного интеллекта и распознавания образов: Научная конференция с участием ученых из социалистических стран (Киев, 13-18 мая 1984 г.).-Тез. докл. и сообщений. Секция II. Распознавание образов. - Киев: Институт кибернетики им. В. М. Глушкова АН УССР, 1984. - С. 41-43.

Моим родителям и Лусии ПРЕДИСЛОВИЕ

Эта книга должна понравиться читателю. Она посвящена волнующим событиям, которые я пережил с тех пор, как в 1973 году М. Минский и С. Пей-перт пригласили меня в Лабораторию искусственного интеллекта Массачусетсского технологического института. Благодаря умелому руководству П. Уин-стона, щедрости Управления перспективных исследовательских программ Министерства обороны США и Национального научного фонда США, свободе действий, предоставленной мне У. Ричардсом, и доброму отношению Р. Хелда условия для работы в лаборатории были идеальными. Мне посчастливилось встретиться и работать с целым рядом замечательных людей, среди которых особенно хотелось бы выделить Т. Поджо. В числе их было много бывших студентов, ставших нашими коллегами. Я многому научился у К. Нисихары, С. Уллмана, К.Форбаса, К. Стивенса, Э. Гримсона и Э. Хилдрет, М. Райли и Д. Батейли. Б. Хорн помог нам ближе познакомиться с физической оптикой, а У. Ричарде — с возможностями человека (и их границами).

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

Многие помогли мне преодолеть этот довольно трудный период моей жизни. Мои родители, сестра, жена Лусиа, а также Дженнифер, Томазо, Симон, Уитман и Инге, в частности, делали для меня больше, чем я порой заслуживал. Благодарю их за все, хотя и понимаю, что просто слов благодарности здесь явно недостаточно. У. Принс направил меня к проф. Ф. Г. Хейхи и д-ру Д. Рису из Адденбрукской больницы в Кембридже, которым я благодарен за то, что они дали мне возможность написать эту книгу.

Лето 1979 г.                                                                        Дейвид Марр

От издательства

Мы хотели бы выразить нашу признательность всем тем, кто помог довести до конца издание книги Д. Марра " Зрение".

Мы благодарим Г. Стента, дружеское участие которого обеспечило сотрудничество Д. Марра с издательством W. H. Freeman and Company, а квалифицированное руководство помогло нам подготовить книгу к изданию.

Мы благодарим коллегу Д. Марра К. Нисихару за знания и огромные усилия, вложенные им в это предприятие; без него завершение этой работы оказалось бы невозможным.

Мы благодарим помощницу Д. Марра К. Папино за внимательное отношение к проблемам, связанным как с рукописью, так и с делами издательства.

Мы благодарим группу сотрудников Лаборатории искусственного интеллекта Массачусетсского технологического института, занимающихся зрением, особенно Э. Хилдрет и Э. Гримсона, которые и в большом, и в малом помогли выходу этой книги в свет.

ЧАСТЬ I

12345678910Следующая ⇒

Поделиться: