7.6.1.       ОСНОВНЫЕ ПОНЯТИЯ

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

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

первоначально определили, что соединения элементов будут в смысле 8-связок. Тогда, поскольку элементы, имеющие хотя бы только одну общую вершину, связаны, »аш объект в целом считается связным. Однако в силу того же рассуждения здесь фон также оказывается связным — «отверстие» в объекте не отделено от окружающего его фона. Следовательно, мы оказались в довольно неприятной ситуации: мы вынуждены иметь дело со связным объектом в виде оболочки, не имеющей внутренности. Предположим поэтому, что в качестве определения мы используем 4-связки. Тогда наш объект несвязный, но и фон, однако, тоже.

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

Определив понятие связности, вернемся к вопросу об анализе изображения путем разбиения его на области. Будем называть мно-

 

жество R элементов изображения элементарной связной областью, если:

1)   Все элементы в R имеют одинаковый уровень полутонов.

2)   Любые два элемента в R соединены цепочкой смежных элементов, каждый из которых принадлежит R.

3)   Любое множество элементов, целиком содержащее и не совпадающее с ним, не удовлетворяет обоим предыдущим условиям.

Второе условие может быть взято за определение связной области. Третье условие гарантирует, что элементарные области настолько велики, насколько это возможно. На рис. 7.16 изображены элементарные связные области дискретного изображения, показанного на рис. 7.2. Алгоритм, по которому созданы границы между этими областями, просто провел линию между каждыми двумя смежными

 

элементами, имеющими различные значения полутонов. (Для разборчивости мы укрупнили первоначальную сетку разбиения размером 120 X 120 до размера 60x60.) Заметим, что эти элементарные области наряду с «существенными» областями, соответствующими поверхностям геометрических объектов, выявляют легкие изменения в тенях и световых переходах, что обычно нежелательно. Существуют по крайней мере два способа борьбы с этими явлениями: путем ослабления первого условия или путем слияния областей. В первом случае мы переводим два смежных элемента в одну элементарную область, если разность их уровней полутонов меньше, чем точно установленный порог. На рис. 7.17 показан простой пример, где разрешено отклонение в один полутоновый уровень. Линия между смежными элементами проводится только в том случае, если разность их полутоновых уровней строго больше единицы. В результате появляется «отросток» границы в пределах одной из областей. Более серьезно то, что у нас смежные элементы со значениями 4 и 8 оказались в пределах одной области. В общем случае эта процедура разрешает помещать смежные элементы с произволь-

но различными уровнями полутонов в одну область. В качестве альтернативы мы могли бы образовать элементарные связные области, как мы их определили первоначально, а затем использовать некоторый критерий при решении вопроса о том, когда соединять две области, имеющие общую границу. Например, предположим, что мы решили объединить две смежные области, если средняя разность значений уровня полутонов для элементов по разные стороны их общей границы меньше или равна единице. Как показано на рис. 7. 18, в результате сольются области со значениями элементов 4 и 5, а также области со значениями 7 и 8. Область со значением 6 будет объединена с областью значений либо 5, либо 7 в зависимости от

порядка, в котором рассматриваются границы областей. Кроме того, область со значениями 4 или же со значениями 8’ (в зависимости от порядка рассмотрения областей) не будет объединена ни с какими другими областями. Следовательно, результат зависит от конкретной реализации алгоритма, но в любом случае область со значения^ ми 8 не будет объединяться с областями значений 4 и 5.

Нетрудно построить и другие критерии как для первоначального выделения, так и для слияния областей. В качестве примера рассмотрим следующий алгоритм объединения. Пусть Ri и R^,— две области с общей границей, и пусть периметры этих областей равны Рі и Ра. Пусть L — длина части общей границы, разделяющей элементы, полутоновые уровни которых отличаются меньше, чем на

d. Мы объединяем две области, если для данного порога t

Одна из интерпретаций такого алгоритма состоит в следующем. Мы можем считать, что L — подозрительная часть общей границы. Если одна из этих областей, скажем R^, более или менее окружена областью Ri, то общая граница составит значительную часть от Р^. Далее, если эта общая граница вызывает сомнения, то величина L также окажется значительной частью периметра Р^, и области будут объединены. Следовательно, алгоритм будет стремиться придать Ri более правильную форму во всех случаях, когда это можно сделать, не игнорируя хорошо определенные границы. На рис. 7.19 показан результат обработки рис. 7.16 с помощью этого алгоритма при d=2 и ^=0,45.