треугольник кажется более ярким, чем фон, хотя бумага имеет всюду одинаковую степень белизны. Ведутся поиски объяснения этого факта.
Интерпретация куба Нэккера не однозначна. Очень часто наблюдатель испытывает самопроизвольные переходы от одной интерпретации к другой. Этот пример показывает, что зрение является конструктивным. Иными словами, мы часто видим то, что хотим увидеть.
Рисунок 10.15 – Фигуры Шэпарда и Мэтцлера
Рисунок 10.16 – Треугольник Каница
Рисунок 10.17 – Куб Нэккера
Компьютерное зрение
571
10.3. Системы компьютерного зрения
Идея создания универсального решателя задач (GPS) захватила воображение исследователей на начальном этапе развития ИИ. Затем было обнаружено, что для решения задачи требуется большой объём фактических и процедурных знаний. База знаний решателя должна быть настолько большой, что стало очевидной не возможность его реализации, а сама идея создания универсального решателя задач стала рассматриваться как утопическая. Можно задать вопрос: “Действительно ли попытка, направленная на построение универсальной системы компьютерного зрения, тоже является утопической?”
Развитием систем компьютерного зрения, которые не ориентировались бы на решение узких задач, а наоборот, удовлетворяли бы некоторым требованиям общности, занимались около трёх дюжин рабочих групп во всем мире. Хотя работы над некоторыми из таких систем продолжались примерно четверть века, нельзя утверждать, что цель создания универсальной системы была достигнута. Такие системы могут быть весьма полезными в относительно узком контексте. Несмотря на это, вновь и вновь возникают попытки создания подобных систем. Приведем краткое упоминание некоторых систем.
VISIONS. Система была разработана А. Хэнсоном и Э. Райзманом в Массачуссетском университете. Работы по созданию VISIONS были начаты в начале семидесятых годов. Эта система технического зрения, основанная на знаниях, представляла собой среду для универсальной обработки и логических выводов. Вместе с тем система решала задачи в конкретной области. Она выполняла интерпретацию изображений пригородных и дорожных сцен [67]. На основе этой системы был создана коммерческая сис-
тема KBVision (Knowledge based Vision).
ACRONYM. Система была разработана Р. Бруксом в Стэнфордском университете в середине семидесятых [62]. Эта система предвосхитила важную роль 3-D моделирования. Возможности системы были продемонстрированы при интерпретации изображений аэропортов, полученных с самолетов, а также в робототехнических системах.
SIGMA. Система была разработана Т. Матсуямой и В. Нагао в университетах Сендая и Киото[79]. Работы над этой системой были начаты в конце семидесятых. Назначение системы интерпретация аэроснимков. Система использовала принцип классной доски. В ней предусматривались средства взаимодействия с оператором.
Все эти системы имели много общего: они представляли универсальную среду, в которую встраивались контекстно-зависимые модули. Предполагалось, что на более поздних этапах развития системы будут способны сами выбирать необходимые модули для решения конкретных
572
Глава 10
задач.
Несмотря на различия указанных систем, существовало определенное согласие относительно компонентов, которые должны были входить в систему компьютерного зрения, а также относительно последовательности обработки визуальных данных. На рисунке 10.18 изображена обобщенная структурная схема системы компьютерного зрения. Она соответствует структурной схеме системы SIGMA. Хотя рассматриваемые ниже системы, ориентированные на решение более узких задач, и будут проще, тем не менее, они обладают общими признаками, которые следует подчеркнуть.
Во-первых, системы являются многоуровневыми. Сложность генерируемых структур данных увеличивается при переходе на более высокие уровни системы. Структуры, сформированные на одном уровне, могут играть роль примитивов на следующих уровнях. В общем, представление структур меняется от уровня к уровню.
Во-вторых, знания, используемые в системах компьютерного зрения, включаются в модели, которые являются одновременно и простыми, и сложными. Модели могут описывать как отдельные объекты сцены, так и всю сцену. Такие модели весьма характерны для систем технического зрения. Они вводятся в систему разными способами, например, с помощью предварительного обучения.
В-третьих, несмотря на существование систем, функционирующих в мире двумерных изображений (например, системы зрения роботов), обычно предусматривается этап получения трехмерных структур по двумерным структурам с помощью различных моделей и процесса сопоставления.
В-четвертых, нет необходимости, чтобы системы работали исключительно в направлении снизу вверх (управление со стороны данных, т.е. от сигналов к символам), хотя во многих системах оно является основным. Возможность возврата к предыдущим шагам обработки часто обеспечивает разрешение неоднозначности. Активизация моделей и генерация гипотез происходит в нисходящем направлении.
В настоящее время возрождается идея построения универсальной системы компьютерного зрения в рамках японского проекта Компьютеризации Реального Мира, который является 10-летней исследовательской программой со сроком завершения в 20011). В нем реализуется новый подход. Системы компьютерного зрения, которые разрабатываются в настоящее время – это обучающиеся системы. Они не наполняются заранее всеми видами возможно невостребованных в дальнейшем знаний, а обучаются в процессе работы. Это должно привести к построению действительно “тонких” систем компьютерного зрения. В этом случае не полагаются ис-
1) http:/www.rwcp.or.jp/home-E.html
Компьютерное зрение
573
ключительно на логический и процедурный подходы, которым ранее отдавалось предпочтение, а опираются на концепции нейроинформатики.
Рисунок 10.18 – Обобщенная схема системы компьютерного зрения
574
Глава 10
10.4. Выделение граничных элементов
Рассмотрим последовательность шагов преобразований, которые упоминались при описании систем компьютерного зрения. Входом для систем компьютерного зрения, также как и входом для систем зрения в живой природе, являются атомарные части изображения. Изображение представляет собой регулярный массив, в котором сохраняются отношения соседства, т.е. смежные элементы массива соответствуют элементам реальности, видимым в определенном направлении, в котором они воспринимаются как соседние. Это объясняет, почему операторы, выполняемые на первых этапах обработки изображений, применяются к множеству соседних точек. Наиболее известными из них являются дифференциальные операторы выделения границ, а также различные виды фильтров (Габора, wavelet- и т.д.), которые пока обдумываются людьми и о которых природа уже “подумала”. В дальнейшем, из-за ограниченности объема учебного пособия, будем говорить в основном об операторах выделения границ и рассматривать их в качестве примеров обобщенных фильтров локальных областей изображений.
Психофизические эксперименты убедительно показали, что те локальные области изображения, которые характеризуются значительным градиентом интенсивности, являются чрезвычайно важными для визуального восприятия человека. Следующие наблюдения подтверждают это:
-нейроны, обнаруживающие границы, изобилуют на первых этапах зрительного пути;
-прерывистые движения глаза сканируют контуры при восприятии объекта (рисунок 10.19);
-человек способен идентифицировать объект на основе простого рисунка в виде контурных линий (технические чертежи, шаржи и т.п.).
Рисунок 10.19 – Сканирование контуров при восприятии изображения
Компьютерное зрение
575
Границы на изображении обнаруживаются путем вычисления градиента интенсивности, который характеризуется:
-направлением (например, вдоль границы или перпендикулярно по отношению к ней);
-позицией;
-силой.
Контуры объекта обычно видны как некоторые границы на изображении. Поэтому естественным является стремление выделить объект по его границам. Конечно, это не всегда правильно, так как имеются и другие причины формирования границ: изменение отражающей способности или цвета поверхности объекта, тени или искажение пространственной ориентации.
Поэтому целесообразно распознавать границы не сразу, а постепенно, формируя их из меньших элементов, продвигаясь от отдельных точек, представляющих границу, к её сегментам. Вероятно, система зрения человека выполняет обработку изображений таким же пошаговым способом.
Элементом границы является пиксель (англ. edgel – дословно “элемент границы”), для которого утверждается, что он, возможно, принадлежит части контура или сегменту границы. Строго говоря, принадлежность к границе не является непосредственно свойством пикселя, а является свойством точек небольшой окрестности, в которой он расположен. Поэтому это свойство должно проверяться. Элементы границы первоначально обнаруживаются при помощи градиентных (граничных) операторов, например, операторов Собела, Кирша или Канни [6]. Они отличаются степенью подавления шумов и угловой разрешающей способностью. Данные операторы относятся к области обработки изображений и здесь не рассматриваются.
Восстановление границ. Методы восстановления границ используют информацию о геометрическом соседстве точек изображения для присвоения им согласованных меток на основе ненадежных данных, формируемых датчиками границ. В конце постобработки формируется некоторая улучшенная граница изображения, элементы которой первоначально определяются с помощью соответствующего граничного оператора.
Предположим, что для выделения элементов границы используется множество меток, которые фиксируют наличие границы и её направление. Одна из возможностей состоит в использовании кода Фримэна со значениями, лежащими в диапазоне от 0 до 7 (0 обозначает восточное направление, 1 - северо-восточное и т.д.). При этом используется некоторое соглашение о направлении границы и о положении объекта, например, слева от границы. Кроме этого, применяется специальная метка, обозначающая отсутствие границы (рисунок 10.20). Инициализация выполняется так,
576
Глава 10
чтобы с каждым элементом границы (пикселем) были связаны все 9 меток с суммарной относительной силой (вероятностью), равной 1. Распределение значений меток для каждого элемента определяется выходными значениями датчиков границ, которые настраиваются так, чтобы ни одна метка не получила нулевой вероятности с целью исключения бесконечного итерационного процесса. Начальная нормализация выполняется по отношению к датчику границ, на выходе которого формируется наибольшее значение. Детальные указания о процессе восстановления (релаксации) приведены в [71]
Рисунок 10.20 - Метки пикселей в соответствии с кодом Фримэна
Веса совместимости rij отражают степень усиления или взаимного
ослабления меток двух элементов границ, находящихся на определенных относительных позициях. Данные веса определяются пользователем на основе здравого смысла или методом проб и ошибок. Другая возможность состоит в том, чтобы определять их статистически, в виде частоты появления определенных пар меток на изображении. Функция совместимости qi(k) ( )определяет, насколько необходимо уменьшить или увеличить текущую вероятность (относительную силу) метки для пикселя i в процессе восстановления границы. Возможная формула:
qi( k ) ( ) dij [ rij ( , ' ) p (jk ) j '
( ')] .
Здесь k – номер шага итерации. Величины rij и qi(k) ( ) характеризуются
Компьютерное зрение
577
знаком. Массив весов dij учитывает пространственное положение пиксе-
лей
i и j. Внутреннее суммирование выполняется по всем меткам пикселя
нее суммирование взвешивает вклады различных пикселей, например, согласно их расстоянию до i-го элемента границы. Обновление значений вероятностей выполняется на основе формулы:
pi( k 1) ( )
p ( k ) ( )[1
q ( k ) ( )]
i
i
pi( k ) ( )[1
qi( k ) ( )] .
Знаменатель гарантирует, сохранение нормализации в процессе выполнения итераций. Процесс сходится грубо в течение 10 итераций. Результатом является изображение, в котором метки граничных элементов согласованы между собой лучше. Это позволяет улучшить формирование сегментов границ.
Процедура восстановления находит применение не только на первых этапах обработки систем компьютерного зрения. Всюду, где необходимо воссоздавать компоненты целого из элементов, главным образом, когда они являются смежными в пространстве, говорят о восстановлении.
В заключение отметим, что первый этап преобразования информации в системах компьютерного зрения начинается с пикселя, который характеризуется одним атрибутом – уровнем интенсивности цвета. Применение операторов выделения границ обеспечивает нахождение пикселей граничных элементов изображения с более богатым набором атрибутов, т.е. позицией, направлением границы, силой и размером.
Указанные граничные элементы остаются не связанными друг с другом и после процесса восстановления, описанного выше. Но они могут быть использованы как примитивы, чтобы формировать более сложные структуры.
Как уже отмечалось, имеются и другие возможности для выбора примитивов нижнего уровня. Позже рассмотрим другой подход к выбору примитивов – метод наращивания областей.
10.5. От граничных элементов к граничным сегментам
Система зрения человека способна группировать элементы изображения в структуры без априорных знаний содержания изображения. Эта способность называется перцептивным группированием и изучается ког-
Наблюдатель не может воспрепятствовать сам себе в том, чтобы увидеть в случайном расположении линейных отрезков некоторые группы, воспринимаемые его глазами. Существуют три принципа группирования, которые следуют из этого примера, – коллинеарность, параллелизм и геометрическая близость. Благодаря указанным принципам создаётся впечатление, что отдельные элементы изображения образуют нечто целое. Они дают человеку возможность воспринимать структуры в тех случаях, когда соответствующие данные фрагментированы. Было бы весьма полезно, чтобы и системы компьютерного зрения обладали подобным свойством.
10.5.1. Преобразование Хафа
Рассмотрим преобразование Хафа как один из методов группирования, применяемый в системах компьютерного зрения. Предположим, что к изображению уже был применен некоторый граничный оператор, и на изображении сохранены для дальнейшей обработки только те граничные пиксели, для которых абсолютное значение градиента выше некоторого порога. Информация о направлении градиента в данном случае не используется. Сохраненные пиксели маркируются. Вместе с немаркированными пикселями фона они образуют бинарное изображение.
Преобразование Хафа позволяет обнаруживать на изображении кривые заданной формы (прямую линию, круг, эллипс и т.п.) даже, когда они
Компьютерное зрение
579
представлены фрагментами. Самый простой случай – обнаружение прямых линий по коллинеарным точкам, которые могут быть не связаны между собой.
Первоначально Хаф предложил следующую параметрическую формализацию этой задачи
y mx b ,
где m, b – параметры восстанавливаемой прямой линии. При этом рассмат-
риваются два пространства: пространство изображений и пространство параметров (рисунок 10.22). Прямые линии пространства изображения представляются точками в пространстве параметров, а точки (или семейство прямых, проходящих через эти точки) пространства изображений представляются прямыми в пространстве параметров.
Рисунок 10.22 - Преобразование Хафа для прямых линий
Трудности возникают при построении вертикальных линий, когда m . Имеется два решения этой проблемы:
- использование двух или более частных пространств параметров,
т.е. 1 m 1 и 1 1/ m 1;
- использование для прямой линии другой системы параметров, например, в полярных координатах.
Уравнения прямой линии в полярных координатах (нормальная форма) имеет вид
x cos y sin ,
где – расстояние до прямой из начала координат; – угол наклона перпендикуляра, опущенного на прямую из начала координат; x,y – координаты точки, лежащей на прямой. Недостатком такого представления является потеря дуальности: теперь точке в пространстве изображений соответствует синусоида в пространстве параметров.
