Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
7.7. КРАТНЫЕ ПИКСЕЛЫХотя мы теперь и располагаем неким определением тонкого множества, мы еще не покончили с этой проблемой. В самом деле, мы можем столкнуться со смешанными областями, допускающими представление в виде объединения полных и линейчатых областей. В таком случае необходимо иметь определение, применимое к подмножествам области, а также (путем его расширения) к отдельным пикселам. Мы уже убедились в том, что пикселы, значение метки которых после обхода контура оказывается больше двух, играют особую роль. Рассмотрим их свойства после ввода нескольких определений. Определение 7.8. Ко-соседями пиксела, принадлежащего контуру С, называются пикселы, являющиеся для этого пиксела предыдущим и следующим элементами при обходе, осуществляемом в соответствии с алгоритмом 7.1. Заметим, что два ко-соседа пиксела не обязательно должны быть разными пикселами, но они всегда различны в случаях, когда контур представляет собой простой маршрут. Пример, иллюстрирующий введенное определение, дан на рис. 7.18.
Рис. 7.18. К определению ко-соседей для некоторого пиксела контура; пикселы В и Рис. 7.19. Содержательная иллюстрация понятия «кратный пиксел»: А соответствует развороту границы [условие (б)]; В — двум непересекающимся дугам, отображенным на один и тот же пиксел [условие (а)], а С и Определение 7.9 Пиксел называется кратным при выполнении одного или нескольких из следующих условий: (а) данный пиксел просматривается более одного раза в про цессе построения контура; (б) данный пиксел не имеет соседей во внутренней части со ответствующей области; (в) данный пиксел имеет, по меньшей мере, одного н-соседа, который принадлежит контуру, но не является его ко-соседом. Смысл этого определения иллюстрируется на рис. 7.19. Кратными оказываются те пикселы, на которые попадают две дуги контура, а также пикселы, на которых происходит «разворот» контура. Первые два условия легко проверяются с помощью разметки, предусмотренной в процедуре TRACER (см. алгоритм 7.1). В самом деле, по окончании построения контура «обычные» пикселы контура будут снабжены меткой, значение которой будет равно 2, а кратные пикселы, удовлетворяющие условию (а), будут иметь метки, значения которых будут больше 2. Условия (б) (отсутствие соседей со значением метки 1) и (в) (наличие н-соседа со значением метки, равным или больше 2, при условии, что он не является ко-соседом) могут быть проверены с помощью второго обхода. Несмотря на существенную простоту обнаружения кратных пикселов при помощи обходов контура, этот метод может оказаться неприемлемым при решении тех прикладных задач, в которых целесообразно использовать параллельную обработку. Поскольку проверка условия (в) существенным образом зависит от этой последовательной процедуры обхода, то определение 7.9 начинает создавать проблемы. Интуитивно кажется, что последовательность не должна быть столь уж важной, так как нас интересуют пикселы, на которые приходится две или несколько дуг контура, или те пикселы, на которых дуги изгибаются, т. е. конфигурации, не зависящие от порядка обхода. Продолжим изучение пикселов, не зависящих от порядка обхода. Если в процессе построения контура некоторого множества Определение 7.10. В качестве меток, присваиваемых некоторому пикселу в процессе обхода контура, используются
Рис. 7.20. Конфигурация окрестности пиксела, являющегося существенным для связности соответствующей области следующие числа: 1— для пикселов, находящихся внутри области; 2 — для пикселов контура, осматриваемых однократно; 3 или большее число — для пикселов контура, осматриваемых более одного раза. С помощью числа, за которым следует знак Таким образом, в эталонных конфигурациях, приведенных на рис. 7.20, по меньшей мере один из трех пикселов, обозначенных символом А, имеет ненулевую метку (левый эталон) и по меньшей мере один из трех пикселов, обозначенных символом В, имеет ненулевую метку. Отметим, что принадлежность пиксела контуру можно установить, не прибегая к обходу. Достаточно установить, что данный пиксел имеет н-соседа, снабженного нулевой меткой. Итак, нами доказано следующее. Утверждение 7.2. Условие (а) определения 7.9 можно заменить требованием, чтобы восьмиэлементная окрестность пиксела соответствовала хотя бы одной из эталонных конфигураций, приведенных на рис. 7.20 (или полученных в результате их поворота на 90° в любом направлении). Условие (б) легко поддается проверке с помощью какого-либо параллельного алгоритма. Ни один из восьми пикселов-соседей не может иметь метку, равную 1. Это обеспечивает сохранение одиночных (т. е. пикселов, не имеющих ни одного соседа) и концевых (пикселов, имеющих ровно одного соседа) точек. Таким образом, проверка соответствуя второму эталону на рис. 7.20 может быть упрощена, если допустить, чтобы все обозначенные символом А пикселы имели нулевые метки. Заметим, что условие (б) обеспечивает также сохранение всех линий, имеющих ширину, равную двум (типа линии, изображенной на рис. 7.17). Нам осталось рассмотреть условие (в). Если пиксел удовлетворяет этому условию, а также условию (а) или (б), то в любом случае он будет отнесен к разряду кратных пикселов. Следовательно, можно попытаться найти критерий, более жесткий, чем условие (в), однако обладающий той особенностью, что отсеянные по нему пикселы «отлавливаются» при помощи двух других условий. Покажем, что для проверки таких пикселов вместо условия (в) можно использовать эталонную конфигурацию пикселов размерами порождающие условие (в). Общий случай такой конфигурации представлен на рис. 7.21. Без потери общности можно считать, что Утверждение 7.3. Любой пиксел, удовлетворяющий условию (в) определения 7.9 и не удовлетворяющий условию (а) или (б), входит в конфигурацию, обозначаемую кодом
Рис. 7.21. Разметка пикселов, использованная при введении альтернативной формы определения 7.9 Доказательство. Докажем это свойство для пиксела Этот результат позволяет без потери общности допустить, что пиксел 2. Теперь перейдем к рассмотрению допустимых конфигураций пикселов Случай 1. Пикселы
Рис. 7.22. Иллюстрация к случаю 1: а — общий и
Рис. 7.23. Иллюстрация к случаю 2: ни один из пикселов с метками 2 и Случай 2. Пикселы Случай 3. Пиксел Мы исчерпали все допустимые конфигурации, возникающие в прямоугольнике пикселов размерами Утверждение 7.4. Проверка условия (в) эквивалентна поиску конфигурации вида, приведенного на рис. 7.25 (а также конфигураций, полученных в результате поворота указанной конфигурации на 90° в произвольном направлении). По меньшей мере, один из обозначенных символом С пикселов должен иметь ненулевую метку; если ненулевую метку имеют оба пиксела, обозначенные символом
Рис. 7.24. Иллюстрация к случаю 3: а — общий и б — частный случаи
Рис. 7.25. Конфигурация, наличие которой эквивалентно выполнению условия (в) На рис. 7.26 приведено несколько характерных конфигураций пикселов (вместе с соответствующими кодами). Если осматриваемый пиксел является кратным, то он обозначен символом, набранным жирным шрифтом.
Рис. 7.26. Пример кратного пиксела Итак, нами получено другое определение для кратных пикселов. Теорема 7.3. Пиксел является кратным, если он удовлетворяет хотя бы одному из следующих условий: (а) его окрестность соответствует одной из конфигураций, представленных на рис. 7.20 (или конфигурациям, полученным их поворотом на 90° в произвольном направлении); пикселы второй конфигурации, обозначенные символом А, могут иметь метки с произвольными значениями; (б) пиксел имеет хотя бы одного соседа с ненулевой меткой или не имеет соседей с метками, равными единице; (в) окрестность пиксела соответствует конфигурации, представленной на рис. 7.25 (или конфигурациям, полученным ее поворотом на 90° в произвольном направлении). Очевидно, что перечисленные условия можно проверять как в последовательном, так и параллельном режимах. Сформулируем результат, связывающий понятие кратных пикселов с тонкими линиями и кривыми. Утверждение 7.5. Любая линейчатая область состоит исключительно из кратных пикселов. И, наоборот, если некоторая область содержит только кратные пикселы, то она является линейчатой. Доказательство. Поскольку данное множество не содержит никаких пикселов, за исключением составляющих его контур, ни один из пикселов контура не имеет соседей внутри области, и, следовательно, условие (б) определения 7.9 справедливо. Доказательство обратного утверждения тривиально, поскольку любой кратный пиксел всегда входит в контур. Проведенный нами анализ имеет значение для обнаружения линий и выполнения операций над ними на дискретной сетке. Мы не касались задачи построения соответствующих отображений, исходя из уравнений прямых и кривых. Эта тема будет затронута в гл. 10
|
1 |
Оглавление
|