Материал: Системы технического зрения. Литвиненко А.М., Машаров А.В

полную связную компоненту контурного изображения и определим контурную последовательность контура Г как упорядоченную

последовательность его точек { k }k 0,K такую, что

контура Г входит в нее ровно 1 раз, причем точки bk-1 K), а также точки bк и b0 являются соседними.

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

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

На практике методы численного дифференцирования дают

70

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

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

При всех достоинствах оператора Хюккеля можно утверждать, что громоздкость требуемых вычислений делает маловероятным его применение в практической робототехнике. Упрощенной модификацией оператора Хюккеля является оператор О'Гормана, в котором вместо «круглого» окна используется квадратное, а в качестве базисных функций приняты удобные при вычислениях функции Уолша. Тем не менее операция выделения контура сравнительного несложного изображения для приведенного в примера заняла около 10 с на ЭВМ ICL 1906 А.

ВСТЗ роботов часто более эффективны, хотя и менее общие, но зато не такие сложные алгоритмы нахождения контурных точек на основе упрощенных расчетов и активного использования логических процедур. Так, для повышения помехоустойчивости при оценках поля градиентов стремятся сглаживать отсчеты яркости вдоль искомой границы и усиливать разность яркостей поперек границы. С этой целью можно брать разности не между яркостями самих пикселов, а между их (взвешенными) средними значениями в выбранном окне размером (2L + 1) X (2М + 1) или пользоваться такими величинами, как

max | G(i l, j m) |; / L l L; M m M

71

либо

Разработаны также алгоритмы «направленного» дифферен-

цирования, в которых | G | рассчитывают путем свертки G * h со специально подбираемыми матрицами h для разных направлений. Например, 3x3 матрицы h, ―окружающие‖ пиксел (i,j) с восьми сторон, могут иметь вид:

1 1 1

1 2 1

11 1 - юговосток

Вразвитие этой идеи можно сразу реализовать свертку

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

Хорошие результаты дают нелинейные детекторы края, которые удается реализовать на современных вычислительных средствах, включаемых в состав СТЗ роботов. Для описания нелинейных локальных операторов введем следующие обозначения уровней яркости восьми соседей пиксела (i, j)

A0 A1 A2

A7 G(i, j) A3

A6 A5 A4

Тогда формулы, задающие ряд известных операторов, примут

вид:

оператор Собела; | G |~ U 2 V 2

где U = А2 + 2А3 + А4 — А0 — 2 А7 — А6; V = А0 + 2А1 + А2 – А6 - 2 А5 — А4,

оператор Кирша: | G |~ max{1, max | 5U k 3Vk |}

оператор Уоллиса: | G |~ log[| G(i, j) | / A1 A3 A5 A7 } достоинством этого оператора является малая

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

оператор Розенфельда: | G |~ D1 D2 ....DM

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

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

если в данном окне имеются пикселы с большими значениями яркости. После этого выполняется обычное сравнение с порогом. В модифицированном варианте этой процедуры центральный элемент «подавляется», если какой-то другой пиксел окна имеет величину | G(i, j) | , которая больше чем на фиксированный перепад

превышает | G(i, j) | центрального элемента.

На основании нейрофизиологического исследования эффекта латерального торможения в зрительной системе живых организмов

фильтром, задаваемым гауссовой функцией f (r) = (1/(2па2)) ехр (— r2/(2а2)), где r — расстояние данной точки от центра фильтра, а a2 — дисперсия нормального распределения.

Результирующий оператор Марра—Хилдрета имеет вид

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

Известны и более сложные алгоритмы, учитывающие не только модуль вектора градиента, но и его направление O (i, j),

являющееся оценкой угла arctg [(dg/dy)/(dg/dx)].

74

Рис. 1.5. Локализация контурных точек

Точка считается контурной, если при выполнении условия 1 неравенство 2 справедливо при двух значениях m = m1 и m = m2, причем m1 и m2 противоположны по знаку. В случае, когда неравенство 2 удовлетворяется только для одного значения m следует проверить неравенство 3 в точке (il, jl), такой, что ml < 0,и если оно окажется выполненным, то точка (i, j) не будет относиться к числу контурных. Такой алгоритм выявляет не только прямолинейные, но и криволинейные контурные линии, однако пока его реализация при приемлемых вычислительных затратах возможна лишь для изображений, описываемых матрицами <G (i, j)> небольшого размера.

Итак, можно сделать следующее общее замечание. Размер матрицы отсчетов яркости N = [P/h], где Р — характерный линейный размер поля зрения, a h — шаг сетки фотоприемников или дискретность съема видеосигнала при использовании телекамеры.

75

Если считать величину h сравнимой с допустимой погрешностью б определения геометрических характеристик объектов, то размер N в типичных робототехнических задачах должен иметь порядок не менее сотен. Необходимость обрабатывать данные о столь больших массивах элементов изображения весьма затрудняет практическое применение многих перечисленных методов сегментации (как, впрочем, и алгоритмов дальнейших этапов анализа изображения). Опишем некоторые подходы к преодолению этой трудности.

Также было предложено снижать объем перерабатываемой информации за счет обработки данных об изображениях «порциями» в виде грубых матриц отсчетов яркости. В частности, был реализован алгоритм, основанный на идее целенаправленных «сдвигов» поля отсчетов относительно объекта в зависимости от текущих результатов обработки. При вводе очередного k-ro кадра яркость отсчитывается в точках (I, J), I, J = 1, n, с шагом Н, намеренно выбранным гораздо больше допустимой погрешности , т. е. Я > /I и, значит, п ^ N. Каждая точка k-u грубой матрицы <G (I, J)> «смещена» по отношению к соответствующей точке предыдущего (k — 1)-го кадра на расстояние ~ (рис. 1.5). Если в некоторой точке (I, J) обнаруживается достаточное отличие Gk (I, J) от Gk-l (I, J), то делается вывод, что при сдвиге на данном шаге соответствующий элемент «пересек» контур. Следует подчеркнуть, что при этом контурные точки локализуются с погрешностью, сравнимой со сдвигом, т. е. заведомо меньшей шага Я грубой матрицы. Повторяя эту процедуру, можно добиться требуемой точности представления контурных точек (разумеется, с погрешностью, не меньшей, чем минимальное значение сдвига).

Можно показать, что для широкого класса изображений в робототехнических задачах точность, отвечающая «неподвижной» матрице N х N, достигается при общем числе отсчетов яркости

порядка N N , что намного меньше полного объема N2, необходимого при традиционных подходах. В памяти нужно хранить лишь две матрицы отсчетов размером n x n и результирующие контурные точки. На каждом шаге можно выбирать наилучшее направление сдвига в сторону наибольшего разрыва между уже выделенными контурными точками. На практике такие «сдвиги»

76

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

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

Проще всего прослеживать контур, анализируя связность очередной выделенной точки с ее соседями. Так, в случае бинарных изображений можно пользоваться следующим правилом обхода контура (по часовой стрелке). После обнаружения первой точки контурной последовательности повернуть «налево» под прямым углом, перейдя к следующему пикселу (i, j); если G (i, j) = 0 (т. е. это элемент объекта), снова повернуть «налево»; если G (i, j) = 1 (фоновый пиксел), то повернуть «направо». Такая процедура повторяется вплоть до возвращения в исходную точку контура. Все обнаруженные по ходу движения элементы объекта, непосредственно предшествующие переходу от объекта к фону либо непосредственно следующие за переходом от фона к объекту, запоминаются как точки контурной последовательности. Этот простой алгоритм легко реализуется на ЭВМ с помощью булевых операторов.

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

77

турной последовательности. Алгоритмы обработки контурного графического препарата чрезвычайно сильно зависят от характера конкретных задач.

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

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

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

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

78

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

поворота касательной к кривой при переходе между этими точками

зависит от радиуса кривизны R аппроксимируемой кривой. При R

>>h экономия точек получается значительной.

Вробототехнических приложениях при сегментации изображений иногда целесообразно выделять не весь контур объекта, а только его характерные фрагменты, которые наиболее важны для конкретной задачи, решаемой СТЗ данного робота (места взятия объекта, углы, выступы, отверстия и т. п.). Выше упоминался алгоритм нахождения параллельных краев объекта на изображении, соответствующих кромкам детали, за которые робот должен захватить ее. Известен также алгоритм, ориентированный на поиск информативных фрагментов контура, который реализует выделение участков его резкого излома. Идея алгоритма поиска «уголков» наглядно поясняется следующим образом. Если представить себе змею, ползущую по контурной линии, то ясно, что наклон хорды, которая соединяет голову и хвост змеи, при пере-ползании через излом будет меняться быстрее, чем при движении по гладкому участку. Для повышения эффективности метода изменение ориентации хорды оценивают по сумме модулей приращений ее проекций на координатные оси, что снижает объем тригонометрических расчетов. Погрешности, вносимые дискретным представлением контурного изображения, в значительной степени сглаживаются за счет усреднения по участку контура, равного длине «змеи». Алгоритм успешно выделял на полутоновых изображениях 256x256x8 бит контур шестерни с 80 зубьями, хотя размер зуба составлял всего лишь несколько пикселов. В результате исходный контур, содержавший 1576 точек, был аппроксимирован зубчатым многоугольником с 161 вершиной. Время сегментации в данном примере при реализации на микропроцессоре Intel 8085 не превышало 0,4 с.

Взаключение укажем, что для СТЗ роботов развиваются

79