7.7. ПРОСЛЕЖИВАНИЕ КОНТУРОВ

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

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

Рис. 7.21. Пример прослеживания контура для объекта, заданного в аналоговой форме.

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

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

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

На рис. 7.22 показано действие этого алгоритма на простом бинарном изображении. Заметим, что «жук» никогда не проникает в

верхний элемент объекта, соединенный в смысле -связок с его остальной частью. Было бы приятно, если бы мы могли констатировать, что алгоритм «знает» о 4- и -связках и при определении множества элементов объекта, связанных с тем элементом, с которого начиналось прослеживание, использует -связки. К сожалению, это не так. «Жук» мог бы проникнуть в этот элемент, примыкающий в смысле -связок, если бы он вошел в элемент с координатами (4, 5) снизу, а не сбоку. Таким образом, последовательность переходных точек, выделяемых алгоритмом, зависит от правила первоначального просмотра изображения. «Отверстие» в объекте, соединенное в смысле -связок с фоном, точно так же создало бы неопределенность в выборе последовательности переходных точек, выделяемых алгоритмом. Этот недостаток представляет собой результат крайней простоты алгоритма. Характерно, что в каждой точке при выборе, в какую, сторону повернуть, используются только три бита информации: два бита сообщают, с какого направления точка прослеживания проникла в элемент, и третий бит определяет, принадлежит элемент объекту или фону. Могут быть построены и другие алгоритмы прослеживания контуров, в которых не возникает проблем из-за асимметрии и неопределенности, присущих описанному варианту. Эти более тщательно разработанные алгоритмы основаны на просмотре элементов в окрестности текущего положения «жука», и поэтому они требуют большего времени для вычислений.

Рис. 7.22. Пример прослеживания контура для объекта, заданного в дискретной форме.

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

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

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

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