ПРЕДИСЛОВИЕ

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

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

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

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

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

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

(класс 2), кривым (класс 3) и точкам или многоугольникам (класс 4). Главы 2—4 посвящены тоновым изображениям и основное внимание в них уделяется преобразованиям и статистическим методам. В гл. 5 дается введение в методы восстановления изображений, используемые в машинной томографии. Необходимым условием понимания всех четырех глав, в которых речь идет только об изображениях класса 1, является вводный курс по обработке сигналов. Остальной материал книги не требует такой подготовки. В гл. 6 рассматриваются структуры для представления изобразительных данных, а в гл. 7—9 — обработка двухуровневых изображений и, в частности, такие проблемы, как построение и заполнение контура, прореживание. Все алгоритмы, представленные в этих трех главах, являются фактически алгоритмами обхода графа. Предполагается знакомство читателя с терминологией теории графов. Главы 10—13 посвящены построению кривых и поверхностей по точкам. Хотя формально изложенный в них материал базируется на простейших сведениях из анализа, все же некоторая математическая культура здесь не помешает. Главы 14—17 посвящены методам формирования графических отображений и их математическому фундаменту — линейной алгебре. В них рассматриваются в основном изображения класса 4.

Некоторые главы книги содержат больше материала, чем требуется для базового курса. Особенно это относится к гл. 8—11 и 15, в которые я включил дополнительно ряд важных алгоритмов, представляющих практический интерес для тех, кто занимается обработкой изображений и машинной графикой. В односеместровом курсе лучше ограничиться изложением одного алгоритма заполнения контура, прореживания и установления перекрытия многоугольников. Можно, в частности, воспользоваться простейшими алгоритмами: 8.4, 9.4 и 15.2. В подобном курсе, вероятно, можно рассматривать только многочлены Безье или только сплайны, или только сплайны с равномерным распределением узлов. (Минимальным введением в построение кривых по точкам можно считать разд. 10.1, 10.2, 11.1 —

11.3, 11.6 и 11.7, а также 10.8, взятые в указанном порядке.)

Если задачи учебного курса более ограничены, чем задачи нашей книги, то некоторыми главами можно вообще пренебречь. Так, учебный курс, посвященный машинной графике, может включать лишь гл. 1, 6—8, 10, 11 и 13—17, а учебный курс, посвященный обработке изображений — гл. 1—7 и 9; гл. 4, 9 и 12 особенно существенны для распознавания изображений.

Я писал эту книгу в течение трех с половиной лет (с конца 1977 г.) в трех местах: в Принстонском университете, Калифорнийском университете (Беркли) и, с июня 1980 г., в фирме Bell Telephone Laboratories, Марри-Хилл, шт. Нью-Джерси. Первый вариант рукописи был закончен в начале 1980 г. и использовался в качестве учебника по курсу, читавшемуся в Принстоне в весеннем семестре. Зимой 1980-1981 гг. этот текст был существенно переработан.

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

Матрицы, приведенные на рис. 3.8, составлены П. Ч. Чжянем. Большая часть изображений, использованных в примерах гл. 1—5, предоставлена мне Джоном Ф. Джарвисом; он же дал мне возможность пользоваться аппаратурой для документирования данных, воспроизводимых на экране дисплея. Я выражаю благодарность доктору Стэнли С. Сиджелману, Кену Ноултону, Тернеру Уиттеду и Дейвиду М. Ваймеру за предоставление мне оригиналов рис. 5.1, 6.8, 17.1 и 17.2 соответственно.

При подготовке рукописи и окончательного варианта книги было использовано программное обеспечение, действующее в Принстонском университете и в фирме Bell Laboratories в рамках операционной системы UNIX. Лоринда Л. Черри исправила ошибки, имевшиеся в тексте, с помощью программ spell diction и style. Окончательный вариант был подготовлен с помощью программ форматирования tbl, eqn и troff. Рисунки 10.8, 11.4, 11.9, 12.1, 12.7, 12.8 подготовлены Брайаном У. Керниганом с использованием языка pic, а рис. 15.1 и 17.7 — Крисом ван Уиком с использованием языка ideal. Рисунок 10.1 получен на фотонаборном устройстве с помощью универсальной стандартной программы графического вывода.

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

Тео Павлидис Марри-Хилл, шт. Нью-Джерси 30 сентября 1981 г.