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

где h (i,j) = F-1 {H ( I , m)}, а символом * обозначена операция свертки. Например, чтобы получить фильтр, подавляющий высокочастотные компоненты, можно воспользоваться функциями типа

где L, М — положительные константы.

Поскольку программная реализация алгоритмов, базирующихся на Фурье-преобразованиях, требует сравнительно больших вычислительных затрат, предпринимались попытки использования более простых интегральных преобразований. Так, преобразование Адамара имеет спектр (при пx = пу = п)

значением v-ro разряда числа q, представленного в двоичной системе счисления.

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

m M l L

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

60

M L

G(i, j) G(i 1, j m) A(l, m)

m M l L

Таким образом реализуется взвешенное усреднение, например, о матрицами А (I, т) вида

или анизотропная фильтрация (нормировочные коэффициенты подбираются так, чтобы данная операция не меняла средней яркости изображения).

При рекуррентной фильтрации элементы (i + l, j + m) берутся из исходного массива G (i, j), для части изображения, еще не подвергшейся процедуре сглаживания, и из «выходного» массива

просканированных точек окна.

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

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

2)при усреднении учитывают только те пикселы выбранного окна, яркость которых отличается от яркости рассматриваемого элемента не более чем на заранее заданное значение;

3)в выбранном окне выделяют подмножество элементов, лежащих по разные стороны от рассматриваемого пиксела и

61

дающих минимальный разброс значений яркости, и усреднение проводят только по этому подмножеству;

4) при сглаживании яркость рассматриваемого пиксела заменяют не средним, а медианным значением яркости элементов выбранного окна, т. е. эти элементы, упорядочивают в соответствии с уровнями их яркости в неубывающую последовательность Gi, Ga,

..., GLM-1; GLM (LxM— размер окна), и медианное значение отвечает номеру m = [(LM + l)/2]. Можно показать, что в результате реализации такого алгоритма из изображения удаляются все детали,

площадь которых внутри окна не превышает (LM 1) / 2

пикселов, причем размывания границ при этом не происходит. Отметим, что в методах 1—3 те из элементов окна, которые не

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

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

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

Логические операторы, применяемые для удаления шума, весьма разнообразны. Например, можно заменять «О» на «1» тогда и только тогда, когда все соседи имеют единичную яркость, а «1» заменять на «О», либо когда все соседние элементы суть «О», либо если среди восьми соседей есть лишь один элемент с яркостью «1», расположенный к тому же не иначе, как по диагонали от данного.

62

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

При фильтрации бинарных изображений с помощью оператора Лапласа (точнее — его дискретной модификации) L (i, j) = G(i-l, j) + G(i, j-1) + G(i, j+1) + G(i + l, j) - 4G (i, j) вводят два порога

(положительный Тр и отрицательный Тп) и пользуются следующей логикой: при Тп <= L (i, j) <= Тр яркость G (i, j) не меняется; если L (i, j) > Тр, то в точке (i,j) «О» заменяется на «1», а если L (i, j) < Тп, то, наоборот, «1» заменяется на «О».

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

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

Особо следует остановиться на вопросе сжатия информации при формировании изображения. В принципе рассмотренные процессы дискретизации и квантования (в частности, бинаризации) видеоинформации уже реализуют ее сжатие. Кроме того, в целях экономии памяти, отводимой для хранения изображения, предлагались различные способы «упаковки» видеоинформации, когда данные о каждом пикселе занимают не целую ячейку памяти, а лишь ее часть. Например, 16-разрядное машинное слово может содержать данные о двух пикселах, представленных 256 градациями яркости (с записью в 8-разрядные байты), или сразу о 16 точках бинарного изображения. Важно, что благодаря возможности ЭВМ

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

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

Идея кодирования состоит в таком представлении видеоинформации, которое за счет использования статистических свойств изображения оказывается в среднем более компактным, чем исходное представление, но позволяет точно восстановить оригинал. Ясно, что если различные уровни яркости пикселов неравновероятны, то потребность в памяти при хранении изображения можно уменьшить, представляя часто встречающиеся уровни короткими кодами, а редко встречающиеся уровни — длинными кодами. Статистические методы кодирования учитывают и присущую изображениям большую корреляцию между соседними пикселами. Так, если яркость последовательных элементов вдоль строки развертки представить в виде разностей G1 ,G2 — Gl ,G3 —- G2, ..., то удается добиться значительного сжатия информации, поскольку малые значения разности появляются гораздо с большей вероятностью, чем большие, т. е. в основном будут использоваться короткие коды. К сожалению, таким методам присущ серьезный недостаток, связанный с накоплением ошибок, для борьбы с которым приходится несколько раз на строке начинать отсчет заново от истинного уровня яркости.

64

Рис. 1.3. Пример цепного кода контура

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

—числом пикселов в ней. Исследования показали, что одномерное кодирование длин серий обеспечивает сжатие информации в 4 ... 5 раз (для бинарных изображений), а обобщение этого подхода на случай двух пространственных переменных доводит коэффициент сокращения объема данных до 10. Известны и

другие методы кодирования изображений (например, с использованием симплексных кодов), которые успешно могли бы быть применены в робототехнике.

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

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

654

средствами.

1.2.3. Методы сегментации изображений в робототехнических задачах

Под сегментацией изображения сцены понимается процесс его разбиения на составные части, имеющие содержательный смысл: объекты, их границы или другие информативные фрагменты, характерные геометрические особенности и др. [15,16,17,18]. Количество предложенных алгоритмов сегментации исчисляется сотнями, однако, обобщая, большинство из них можно свести к выявлению одного из двух фундаментальных свойств изображения: сходства и различия. В соответствии с этим остановимся на двух основных подходах к сегментации, используемых в СТЗ роботов: методах нахождения однородных областей и методах выделения контурных линий.

Нахождение однородных областей. Сегментацию изображе-

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

Рассмотрим более строго понятие связности элементов дикретизованного изображения. Формально можно считать, например, что каждый пиксел (i, j) связан только с четырьмя элементами, примыкающими к нему по строке и столбцу: (i — 1, j), (i + 1, j), (i, j — 1) и (i, j + 1). С не меньшим основанием можно полагать его связанным со всеми восемью ближайшими элементами, включая диагональные. В первом случае говорят о 4-окрестности пиксела, во втором — о 8-окрестности. Множество пикселов Р назовем восьмисвязным, если между любыми двумя его элементами а

и b существует последовательность элементов {ek P}k 0,K , такая,

66

что е0 = а; ек = b, и при любом k, 1 <= k <= К элемент ek

Аналогичным образом определяется четырехсвязность. Важность точного определения связности иллюстрирует рис. 1.4. В изображении на рис. 1.4, а легко выделить три области — черный кон

Рис. 1.4. К определению связности элементов изображения содержит в своей 8-окрестности элемент.

тур и две белые зоны (внутри и вне контура), которые отвечают как интуитивным представлениям, так и обоим приведенным выше определениям связности. Но уже для изображения на рис. 1.4, б возникает неоднозначность. Если определять соседей в 8- окрестности, то черные элементы по-прежнему составляют единый контур, а если принять концепцию четырехсвязности, то изображение разобьется на четыре отдельных соприкасающихся прямоугольника. Парадокс здесь заключается в том, что в первом случае мы были бы обязаны считать белые элементы внутри «единого контура», связанными с белой внешней областью. Чтобы устранить подобные противоречия, условимся в общем случае пользоваться принципом восьми-связности, группируя, пикселы в области, однородные по некоторому свойству S, и принципом четырехсвязности для областей, обладающих противоположным свойством 5 (например, на рис. 1.4 оба изображения черного «контура» будем считать объектами, а белые зоны—фоном).

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

67

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

Пусть область R1 с периметром Р1 граничит с областью R2, имеющей периметр Р2, причем их общая граница имеет длину С. Найдем протяженность D той части этой границы, для которой перепад яркостей граничащих элементов окажется меньше заранее заданного порога p > 0. Тогда слияние смежных областей Rl и R2 происходит в том случае, если выполняется неравенство D > 0,5 min [Р1, Р2]. При такой эвристике происходит поглощение малых областей большими, а области более или менее близких размеров остаются раздельными.

Согласно другому эвристическому правилу, смежные области RI и R2 сливаются, если D > 0,75C. В отличие от первого алгоритма, который сегментирует изображение на много мелких фрагментов, эта эвристика может приводить к чрезмерному слиянию областей. Поэтому метод наращивания областей в случае сложных сцен иногда дает ошибочную сегментацию изображений. Делались попытки модифицировать его путем применения многопроходных и интерактивных процедур, использования контекстной информации. Хотя существует мнение, что алгоритмы наращивания областей не найдут практического применения в робототехнике, операции на однородных областях удалось использовать в СТЗ робота, предназначенного для взятия деталей из беспорядочного навала в бункере Там же для нахождения однородных областей предложено использовать не только алгоритм наращивания, но и обратную операцию сжатия однородной области, выполняемую по шагам путем удаления всех элементов, среди соседей которых есть элемент, не принадлежащий области. Такая процедура позволяет найти достаточно большие однородные участки на изображении бункера с деталями, которые трактовались как вероятные места захватывания деталей вакуумной присоской робота.

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

68

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

Один из способов сегментации изображений состоит в представлении объектов сцены в виде их остовов. Остов — это геометрическое место точек, обладающих тем свойством, что минимум расстояния от каждой из них до границы однородной области достигается не для какого-то одного, а сразу для нескольких элементов границы. В алгоритмах получения остовов используется преобразование к срединным осям [40]. Эта идея была практически реализована [15] с помощью алгоритма «фронтов столкновения», обеспечивающего выделение на изображении бункера с деталями длинных параллельных кромок, за которые деталь может быть захвачена роботом. Подобные методы пока не получили широкого распространения в робототехнике из-за их сильной чувствительности к шумам, однако этот недостаток в принципе можно преодолеть, вводя сглаживающие фильтры.

Выделение контурных линий. В СТЗ роботов гораздо чаще применяют методы сегментации, основанные на выделении контуров. Контурные линии на изображении образуются из видимых участков границ объектов, причем они могут служить границами не только между предметами рабочей сцены и фоном, но и между изображениями различных предметов и даже между изображениями смежных поверхностей одного и того же предмета. С учетом упомянутой выше проблемы определения связности формально будем считать контурной точкой для области R, однородной по свойству элемент r из R, такой, что в его 4-окрестности содержится хотя бы один пиксел, не обладающий свойством S. Две контурные точки назовем соседними, если одна из них содержится в 8- окрестности другой. Контурное изображение определяется как множество всех контурных точек, выделенных в соответствии с одним и тем же свойством S. Интерес представляют такие контурные изображения, каждая точка которых имеет ровно двух соседей. В этом случае назовем (замкнутым) контуром любую

69