Дуда Р., Харт П. - Распознование образов и анализ сцен (1033979), страница 62
Текст из файла (страница 62)
Прекратите продвижение, если вы находитесь в пределах одного элемента от начальной точки. На рис. 7.22 показано действие этого алгоритма на простом бинарном изображении, Заметим, что «жук» никогда не проникает в 312 Гл. 7. Пред«вава«ми« из«бра»гений верхний элемент объекта, соедйиенный в смысле 8-связок с его оо. тальной частью. Было бы приятно, если бы мы могли констатиро. вать, что алгоритм «знает» о 4- и 8-связках и при определении множества элементов объекта, связанных с тем элементом, с которого начиналось прослеживание, использует 4-связки. К сожалению, это не так.
«Жук» мог бы проникнуть в этот элемент, примыкающий в смысле 8-связок, если бы он вошел в элемент с координатами (4, 5) снизу, а не сбоку. Таким образом, последовательность переходных точек, выделяемых алгоритмом, зависит от правила первоначального просмотра изображения. «Отверстие» в объекте, соединенное в и смысле 8-связок с фоном, точно так же создало бы неопределенность в выборе последовательности переходных точек, выделяеи мых алгоритмом.
Этот недостаток представляет собой результат крайней простоты алгоритма. ХаФ рактерно, что в каждой 1о 3 точке при выборе, в какую сторону повернуть, используются только три бита Рис. 7.22, Пример прослеживания контуРа иифОРМацин: Два бита сО- для объекта, заданного в дискретной форме. общи»от, с какого направ- ления точка прослеживания проникла в элемент, и третий бит определяет, принадлежит элемент объекту или фону. Могут быть построены и другие алгоритмы прослеживания контуров, в которых не возникает проблем из-за асимметрии и неопределенности, присущих описанному варианту. Эти более тщательно разработанные алгоритмы основаны на просмотре элементов в окрестности текущего положения «жука», и поэтому они требуют большего времени для вычислений. Существуют два важных условия, которые должны быть выполнены для того, чтобы алгоритм прослеживания контуров успешно работал.
Во-первых, поскольку функция интенсивности обычно имеет много полутоновых уровней, должен существовать какой-то способ выделения объекта, контур которого необходимо прослеживать. В простых случаях объект может быть отделен от фона с помощью соответствующей пороговой обработки изображения'. Мы можем просто считать объектом все, что на изображении темнее (или светлее) некоторой установленной величины. Этот прием приводит нас к варианту с бинарным изображением, описанному выше. В тех слу- 7.8. БибяиаграФинеснгге и исторгг«вские сведения 3!3 чаях, когда это не может быть сделано, иногда оказывается возможным прослеживать контур, выделяя его локально по большим перепадам полутонового уровня между объектом и фоном.
В некоторых алгоритмах для этой цели объединяют оператор оценки градиента и процедуру прослеживания контуров. Оператор оценки градиента отыскивает локальное направление контура (при условии, что на контуре уже найдена какая-то точка, с которой необходимо начать), определяя для этой цели направление наиболее заметного края вблизи заданной контурной точки. Предполагается, что небольшой шаг, сделанный в найденном направлении, даст новую точку около границы объекта.
Чтобы обнаружить перепад интенсивности вблизи этой точки, снова вызывается оператор оценки градиента, и далее процесс повторяется. Второй важной предпосылкой для успешного прослеживания контуров является отсутствие ложных разрывов в силуэте объекта, Даже в простом случае бинарных дискретных изображений алгоритм прослеживания контуров может случайно «попасть внутрь объекта».
Это представляет серьезную проблему, когда методы прослеживания контуров используются прн опознавании «печатных» букв и цифр, написанных человеком от руки. Если, например, петля у цифры «6> будет не совсем закончена, алгоритм прослеживания контуров даст на выходе информацию, существенно отличающуюся от желаемой. Такие трудности можно иногда преодолеть с помощью предварительного сглаживания изображения, позволяющего заполнить небольшие зазоры. Заметим, что прослеживание контуров — существенно последовательный процесс.
Ошибка, допущенная на любом шаге этого процесса, делает более вероятными ошибки н на последующих шагах. Это качество составляет контрасте такимиоперациями, как, например, сравнение с эталоном, которые могут осуществляться в параллель. В последнем случае неудача прн попытке обнаружить сходство в одной части изображения не оказывает прямого влияния на результат в другой части изображения. Представляется в связи с этим, что алгоритмы прослеживания контуров могут применяться только на изображениях с низким уровнем шума. 7.3. БиБлиОГРАФические и истОРические сВедения Можно указать очень немного работ общего характера по автоматическому анализу сцен.
Единственная монография, посвященная специально этому вопросу, принадлежит Розенфельду (1969). Хорошие сборники работ были изданы Фишером и др. (1962), Типпетом и др. (1965), Уром (1966), Кеналом (1968), Ченгом и др. (1968), Колерсом и Иденом (!968), Граселли (1969), Ватанабе (1969), а также Липкииом и Розенфельдом (1970). Другим полезным сбор- 3!4 Гл. 7. Представление и»абра»лений ником трудов является «Специальный выпуск по выделению и отбору признаков при распознавании образов» '). Мы не будем уделять большого внимания ни проблеме улучшения качества изображений для последующей интерпретации их человеком, нн проблеме кодирования изображений для их более эффективной передачи и хранения. Обзор по этим вопросам написан Хуангом и др.
(1971); он снабжен большим списком литературы. Большая часть тех идей, 'которые обсуждались в этой главе, была выдвинута на ранней стадии исследований, когда «анализ сцен» состоял почти исключительно из опознавания знаков. Далее мы ссылаемся на некоторые наиболее представительные источники этих идей, причем наши ссылки подбирались по принципу ясности и разносторонности изложении, а не по принципу приоритета. Проблема представления изображений в ЭВМ состоит из двух частей: должны быть выбраны способы как амплитудной, так и пространственной дискретизации.
Проблема амплитудного квантования для общего случая была решена путем обращения к физиологическим аналогиям. В работе Грегори (1966) содержится изложенный в доступной форме обзор по этому вопросу; более исчерпывающе эта проблема освещена Грэхемом и др. (1965). Работа Корнсвита (1970) содержит обширные сведения о системе зрительного восприятия человека. Проблема пространственного квантования решалась почти всегда путем дискретизации изображения с помощью сетки квадратных элементов.
Ченг и Ледли (1968), а также Симон и Гюйо (1971) исследуют этот процесс аналитически, рассматривая его с точки зрения теории аппроксимации. (Другой аналитический подход — преобразование Фурье — будет обсуждаться в следующей главе.) Топологнческие преимущества гексагональной сетки в сравнении с квадратной сеткой рассматривались во многих работах, но немногие авторы действительно их использовали. Голэй (1969) предложил конструкцию вычислительного устройства параллельного действия, способного осуществлять ряд интересных операций над изображениями, представленными в виде массивов гексагональных элементов. Ингрэм и Престон (1970) впоследствии использовали его методы для обработки изображений кровяных телец. Взаимно дополнительные операции пространственного дифференцирования н пространственного сглаживания появились в литературе по опознаванию знаков еще в работе Диннина (1955).
Дойль (1960) применил логическое усреднение в тех же задачах, Градиентные операторы использовались на предварительных стадиях в обработке изображений трехмерных сцен Робертсом (1965) и Форсеном (1968). Кенал и Рендал (1964) применили аппроксимацию лапласиана функции интенсивности для подчеркивания перепадов полутонового уровня. Ярбус (1965) представил интересные психо- г) гЕЕЕ Тгапваа)!апв ап СатриГегв, 20, № 9 (Зер!еигьег !97!). 7.д. Библиографические и исторические сведения 315 физические доказательства важности краев с помощью регистрации движений глаза при рассматривании изображения человеком.
Задача сравнения с эталоном возникает вегой или иной форме во многих работах, посвященных анализу зрительных сцен, Хайлиман (1961) использовал глобальные эталоны для распознавания «печатных» букв и цифр, написанных от руки, Мансон (1968) использовал локальные эталоны для той же цели.
Кенал и Рендал (!964) применяли эталоны для обнаружения признаков объектов на аэрофотографиях. Робертс (1965) использовал локальные эталоны, чтобы обнаруживать короткие сегменты прямых линий. Гриффит (!971) взял вероятностную модель за основу при проектировании детектора линий.
Розенфельд и Тэрстон (1971) использовали семейство эталонов для обнаружения переходов текстуры. Барии и Сильверман (1972) обсуждают семейство эффективных алгоритмов сравнения с эталоном. И наконец, классическая работа Хьюбеля и Визеля, итог которой был подведен Хьюбелем (1963), показала, что зрительный аппарат кошки при обнаружении сегментов прямых линий действительно выполняет действия, эквивалентные локальному сравнению с эталоном.
Разбиение сцены в процессе анализа областей — это уже более поздний метод по сравнению с другими обсуждавшимися в этой главе. Гузман (1968) анализировал идеальные контурные рисунки путем группировки областей, принадлежащих одному трехмерному объекту. Брайс и Феннема (!970) разработали методы выделения существенных областей прямо на дискретном изображении; разд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
