7.4. ТЕОРЕМА ОТСЧЕТОВ ДЛЯ ИЗОБРАЖЕНИЙ КЛАССА 2

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

Определение 7.4. Изображение класса 2 и сетка выборки с квадратными элементами называются совместимыми при выполнении следующих двух условий: а) существует такое число где — длина стороны элемента сетки выборки, что для каждой граничной точки каждой области заданного цвета найдется окружность С диаметром касающаяся границы и полностью лежащая внутри области то же самое справедливо и для дополнения области

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

содержат углы. Выберем радиус кривизны и заменим каждый угол дугой окружности радиуса Если достаточно мал, то может не возникнуть заметных искажений формы объектов, но теперь появилась возможность найти совместимую сетку выборки. Достоинством определения 7.4 является то, что при решении ряда прикладных задач оказывается возможной проверка выполнения условия совместимости. Так, например, литеры типографского шрифта часто имеют такие начертания, что оказывается возможным измерить их минимальную ширину и минимальную кривизну.

Выполнение условия совместимости гарантирует наличие ряда свойств, которые характеризуются приведенными ниже леммами. Термин «сосед» используется в смысле определения 7.1, т. е. соседями считаются элементы, соприкасающиеся как углами, так и сторонами.

Лемма 7.1. Если условие совместимости выполняется и элемент дискретизации пересекается с областью то либо центр элемента дискретизации расположен в области либо элемент дискретизации имеет соседа, центр которого расположен в области

Доказательство. Пусть С — одна из окружностей диаметром расположенная в области и пересекающаяся с элементом дискретизации но не содержащая его центр. Тогда окружность С должна касаться прямой X, как показано на рис.

Рис. 7.7 Иллюстрации к доказательствам леммы 7.1 (а) и леммы 7.2 (б)

Если окружность С не содержит центров каких-либо других элементов дискретизации, то она должна также касаться прямых и Однако поскольку расстояние между любыми двумя такими параллельными прямыми меньше значения то, следовательно, оно меньше значения . В результате мы пришли к противоречию!

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

Доказательство. Допустим, что указанные элементы дискретизации не имеют ни одной общей стороны и центры элементов дискретизации расположены вне области (рис. Если бы угол А находился в области то он должен был бы быть расположен внутри окружности диаметром целиком лежащей в области Окружность С представляет собой такую окружность, которая не содержит центров элементов дискретизации Рассмотрим теперь аналогичную окружность, содержащую центр элемента дискретизации Последняя может пересекаться с окружностью С (вариант расположения или не пересекаться с ней (вариант расположения Если пересечение имеет место, то пусть М и — соответствующая пара точек пересечения. Обе эти точки расположены в области и любая окружность диаметром содержащая их, должна содержать также центр одного из элементов дискретизации . В результате мы пришли к противоречию. Если окружности не пересекаются, то, как показано на рис. должна существовать точна не принадлежащая области и принадлежащая элементу дискретизации Таким образом, невозможно построить окружность диаметром содержащую указанную точку и не содержащую центры элементов дискретизации Это означает, что условие совместимости не выполняется. Следовательно, лемма для случая, когда угол А расположен в области доказана. Аналогичным образом доказывается лемма для случая, когда угол А расположен вне области

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

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

Утверждение 7.1. Пусть А и В — две точки множества принадлежащего непрерывному изображению I, и К — кривая, соединяющая их и целиком лежащая в множестве Последнее отображается в множестве принадлежащем восстановленному изображению . В таком случае все точки кривой К можно отобразить на кривую целиком лежащую в множестве причем ни для одной пары соответствующих точек кривых К и К расстояние, разделяющее их, не превышает значения

Доказательство. Если допустить, что условие совместимости выполняется, то из этого следует, что каждая точка кривой К расположена внутри окружности диаметром целиком лежащей в

множестве R. Размеры этой окружности таковы, что в ней должен быть расположен некоторый элемент дискретизации. Следовательно, можно установить некоторое соответствие между всеми точками кривой К и центрами элементов дискретизации (рис. 7.8, а). Согласно лемме 7.2 существует некоторый маршрут, соединяющий центры всех этих элементов дискретизации, причем он будет пересекать только стороны элементов дискретизации, не проходя через их углы.

Рис. 7.8. Иллюстрации к доказательству утверждения 7.1

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

Следствие. Границы соответствующих областей изображений и при наложении этих изображений разделены расстоянием, не превышающим

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

Теорема 7.1. Выполнение условия совместимости обеспечивает сохранение топологии.

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

Рис. 7.9. Иллюстрация к доказательству теоремы 7.1

Исходная область заштрихована с наклоном влево, а восстановленная — вправо. Отрезки прямых и дискретного изображения отображены на отрезки прямых и непрерывного изображения, отрезки прямых и — на отрезки и отрезок — на — на и т. д., точки и — фиксированы; дуга отображена на — на (кусочно-линейную) дугу

Область представляет собой избыток, поскольку является частью непрерывной области, лежащей за пределами восстановленной области. Если элемент дискретизации содержит такую часть области или является смежным с ней, то он подвергается разбиению на части. Части элемента, не входящие ни в одну из таких областей, рассматриваются как точки непрерывной области, в которой все точки элемента дискретизации имеют отображение. (Так, элемент стягивается в часть элемента — в и т. д.) Остальные части отображаются Б соответствующие симметричные (относительно непрерывной границы) области, как показано на рис. 7.9. Наши две леммы гарантируют непрерывность данных преобразований. В частности, из леммы 7.1 следует, что любой избыток оказывается смежным с элементом дискретизации того же цвета. Поскольку эта лемма справедлива как для множества, так и для его дополнения, из нее следует, что заполнение недостатков не приводит к слиянию областей. Лемма 7.2 гарантирует отсутствие соприкосновений углов и, следовательно, возможность выполнения всех преобразований вдоль сторон элементов, как показано на рис. 7.9.

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

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

В топологическом смысле условие совместимости означает, что все непрерывные множества являются открытыми, и оно гарантирует, что восстановленные множества также являются открытыми. Этот подход оставляет, судя по всему, открытой проблему тонких линий, которые теоретически имеют нулевую толщину, а топологически не являются открытыми множествами. Отметим, что в реальных условиях линии всегда имеют конечную толщину и их невозможно корректно дискретизировать, если условие совместимости для них не выполняется. С другой стороны, может быть целесообразно как с теоретической, так и с практической точек зрения рассматривать отдельно восстановление таких линий и множеств, имеющих конечную толщину. Мы так и поступим в разд. 7.6.