Дуда Р., Харт П. - Распознование образов и анализ сцен, страница 2

Считаем своим долгом поблагодарить д-ра Т. О. Бинфорда, д-ра Т. М. Ковера, К. Л. Феннема, д-ра Г. Ф. Гронера, Д. Дж. Холла, д-ра М. Е. Хелмана, д-ра М. А. Касслера и д-ра Дж. Х. Мансона за их ценные замечания. Кроме того, нам хочется поблагодарить д-ра Р. К.

Синглтона за его участие в работе над примерами гл. 8. И наконец, с удовольстием выражаем признательность неутомимой К. Л. Спенс за перепечатку различных вариантов рукописи. Р. О. Дуда, П. Е. Харт Часть ! КЛАССИФИКАЦИЯ ОБРАЗОВ Глава 1 ВВЕДЕНИЕ 1.1. МАШИННОЕ ВОСПРИЯТИЕ Стремление расширить область применения цифровых вычислительных машин существует со времени нх появления. В известной мере это связано с требованиями практики, с поиском наиболее эффективных способов деятельности.

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

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

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

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

ПРИМЕР Чтобы пояснить характер задач, с которыми в дальнейшем придется иметь дело, рассмотрим следующий, несколько надуманный пример. Решение Рис. 1.1. Схема системы классификации. Допустим, что на некоторой деревообделочной фабрике, выпускающей изделия из древесины различных сортов, требуется автоматизировать процесс сортировки обрабатываемой древесины по порода дерева. Первоначально решено попытаться разделять древесину пород березы и ясеня по ее внешнему виду.

Система, предназначенная для выполнения этой задачи, может быть построена по схеме, изображенной на рис. 1.1. Полученное в камере изображение древе<,ины передается на выделитель признаков, назначение которого <остонт в уменьшении объема данных измерением конкретных «признаков» илн «свойств», отличающих вид древесины березы и ясеня, Далее эти признаки (точнее, измеренные значения этих 1з П2. Пример признаков) подаются на классификатор, предназначенный для оценки представленных данных и принятия окончательного решения относительно типа древесины. Рассмотрим, по какому принципу могут быть построены выделитель признаков и классификатор. Допустим, что на фабрике нам сообщили, что окраска березы обычно светлее, нежели ясеня. Таким образом, яркость оттенка древесины становится очевидным признаком, и можно попытаться распознавать древесину, наблюдая попросту, превышает или нет ее средняя яркость х некоторое критическое значение х,.

Для выбора величины х,можно взять несколько кусков древесины той и другой породы, измерить их яркость и Рнс. 1.2. Гистограмма яркости (по оси ординат — число кусков древеснньп 2 — ясень, 2 — береза). оценить результаты измерений. Допустим, что все это проделано и построены гистограммы, приведенные на рис. 1.2. Рассматривая гистограммы, можно установить, что береза обычно светлее ясеня, но вместе с тем очевидно, что один этот критерий не достаточно надежен. Вне зависимости от выбора х„отличить березу от ясеня только по яркости невозможно.

При поиске других признаков можно попытаться воспользоваться тем соображением, что волокна ясеня обычно более заметны. Хотя измерить этот признак значительно труднее, чем среднюю яркость, однако можно предположить, что заметность волокон можно оценивать по амплитуде и частоте появлений на изображении переходов от темного к светлому. Таким образом, теперь мы имеем два признака для распознавания древесины — яркость х, и заметность волокон х,. Выделитель признаков сводит, таким образом, каждую из картинок к точке или вектору признаков х двумерного простран- Гл. д Введение 14 ства, где х=и Наша задача заключается теперь в разделении пространства признаков на две области, все точки одной из которых соответствуют березе, а другой — ясеню.

Предположим, что мы определили значения векторов признаков для наших кусков древесины и получили разброс точек, показанный на рис. 1.3. Анализ графика приводит к следуюшему правилу ~г ° мв распознавания полученных дан° не ных: считать, что данная древесина есть ясень, если вектор признаков попадает выше пря° йвнн~~м ° о цоо о мой АВ; в противном случае ммнИв о 8 о о считать„ что это береза.

Несмотря на то что разделел о о м о ние взятых кусков посредством 8 данного правила достаточно хорошее, нет никакой гарантии, что так же хорошо оно будет и Рнс. 1,3. Днаграмма разброса векторов по отношению к новым кускам. нрнзнакон ( ° — ясень, Π— береза). Безусловно, разумнее было бы взять еще несколько кусков и посмотреть, какая часть из них будет определена правильно. Таким образом, мы приходим к заключению, что поставленная задача включает в себя и элементы статистики, в связи с чем может потребоваться поиск такой процедуры классификации, которая сделает вероятность ошибки минимальной. Говоря об этом, следует помнить, что в качестве примера была выбрана простая задача. Значительно реальнее задача сортировки древесины на много различных классов.

В частности, чтобы отличить дуб от березы и ясеня, вполне могут потребоваться и такие менее очевидные признаки, как «ровность волоконз. При большем числе классов и признаков, возможно, придется отказываться от графического способа представления классификатора. Поэтому для дальнейшего изложения вопроса потребуется развить теоретические основы метода. 1.а. мОдель КлАссиФиКАции Рассмотренный пример содержит многие элементы наиболее распространенной абстрактной модели распознавания образов— модели классификации.

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

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

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

При этом задача классификации превращается в задачу статистической теории принятия решений, широко применяемую в различных областях теории распознавания образов. Этому и ряду других вопросов, относящихся к теории классификации, посвящена часть 1 данной книги. 1М, ОПНСАТЕЛЬПЫЯ ПОДХОД В области распознавания образов и машинного восприятия существует много задач, для которых модели классификации совершенно не пригодны.