Многомасштабный подход к определению контуров
объектов на цифровых изображениях
, Институт Системного Анализа Российской Академии Наук
В данной статье представлен новый метод многомасштабного определения контуров объектов на цифровых изображениях. Для получения точного расположения контуров объектов в нашем методе применяется стратегия построения градиентного изображения путем последовательного комбинирования информации, полученной при разных масштабах дифференциального оператора, начиная с точных масштабов и продвигаясь к грубым. Определение точного расположения контуров объектов имеет большое значение для многих практических задач распознавания образов. Мы предлагаем метод, который позволяет при движении к грубым масштабам избежать потерь информации о расположении резких контуров объектов, определенных на точных масштабах. В то же время представленный алгоритм позволяет успешно определять плавные контуры объектов на больших масштабах. В отличие от других многомасштабных методов, которые дают в результате картину расположения контуров объектов, наш метод позволяет получить многомасштабное градиентное изображение, которое может применяться в различных алгоритмах сегментации цифровых изображений или использоваться для дальнейшего анализа изображения. Также в работе представлена модификация метода для изображений с наличием шума.
1. Введение
Сегментация изображений, основанная на определении контуров объектов, по-прежнему, является одним из актуальных методов, используемых при обработке цифровых изображений. Обычно задачей сегментации является разделение изображения на области, состоящие из точек, имеющих примерно одинаковый уровень яркости (в случае полутоновых изображений) или схожие цветовые характеристики (в случае цветных изображений). Соответственно, контурами, или границами, данных областей являются совокупности точек на изображении, в которых происходит изменение уровня яркости или цвета. Для определения границ или контуров областей разработано много различных методов[1][2], основой для которых, в большинстве случаев, является построение градиентного изображения [2], то есть, применения к исходному изображению оператора первой производной для дискретной функции, определенной на плоскости. Оператор градиента можно рассматривать как линейный фильтр изображения. Линейные фильтры изображений, как правило, задаются квадратной матрицей коэффициентов или маской фильтра, которая применяется для каждой точки изображения. Размер маски оператора первой производной, или, другими словами, его масштаб, может быть различным. Часто подходящий масштаб оператора градиента, а именно дающий в результате наилучшую картину контуров объектов, подбирается путем экспериментальных проверок. Но так как изображения, встречаемые на практике, в большинстве случаев содержат контуры с различными скоростями изменения яркости (для случая полутоновых изображений) или цвета (для случая цветных изображений), то есть, как резкие, так и плавные, то, очевидно, что невозможно наилучшим образом определить все существующие на изображении границы, используя лишь оператор градиента одного определенного масштаба[3]. Все вышесказанное показывает актуальность применения методов, позволяющих построить картину контуров объектов изображения на основе информации, получаемой в результате применения оператора градиента различных масштабов.
В литературе существует несколько подходов к анализу многомасштабной информации, то есть, к построению картины контуров объектов на основе градиентных изображений различных масштабов[3]. Существуют подходы, в которых анализ градиентных изображений проводится от грубых масштабов к точным[4][5], также существуют подходы где анализ выполняется, наоборот, от к точных масштабов к грубым[6][7] и подходы, в которых анализ не зависит от последовательности рассматривания изображений[8][9]. Данные подходы различаются и по принципам построения градиентного изображения одного масштаба, то есть, видом применяемого оператора градиента. Но все же ключевым является вопрос о том, каким образом следует комбинировать имеющуюся многомасштабную информацию для построения конечной картины границ. Бергольм [4], один из первых, кто обратился к теме многомасштабного определения контуров, предлагает метод, заключающийся в последовательном анализе многомасштабной информации от грубых масштабов к точным. Такой подход позволяет значительно уменьшить влияние шума, и таким образом избежать ложного определения контуров получаемых вследствие присутствия на изображении шума, и, в тоже время, дает приемлемую картину границ. Однако недостатком данного метода является возможное разделение контуров, определяемых на грубых масштабах, на несколько отдельных при переходе к более точному масштабу. Стратегии рассматривания градиентных изображений от грубых масштабов к точным также придерживаются и другие авторы [5]. Однако в тех случаях, когда изображение содержит небольшие объекты с резкими границами, точное определение границ этих объектов, при движении от грубых масштабов к точным, нам представляется затруднительным, так как на градиентных изображениях грубого масштаба возникает значительное перемещение положения резких контуров [5].
Другие авторы придерживаются подхода, при котором окончательная картина границ составляется на основе анализа градиентных изображений от точных масштабов к грубым[6][7]. При этом, основными задачами при таком подходе является уменьшение влияния шума, к которому чувствительны операторы градиента малого размера, и комбинирование границ, полученных на точных масштабах, с плавными границами, которые определяются лишь на грубых масштабах. При успешном решении этих проблем подход к анализу градиентных изображений от точных масштабов к грубым представляется нам наиболее предпочтительным для многих практических случаев, в которых необходимо достаточно точное определение контуров объектов. Характерные примеры таких задач – это сегментация сканированных изображений страниц книг, газет, журналов, содержащих большое количество объектов небольшого размера, например, букв и символов. Задача сегментирования таких изображений остается, по-прежнему, актуальной, особенно, для случая цветных изображений.
Многие методы сегментации, основанные на определении контуров объектов, например, ватершед-преобразование[2], используют в качестве основы для проведения сегментации градиентное изображение. Однако предлагаемые в литературе методы многомасштабного определения контуров дают в качестве результата уже готовую картину контуров, а не составленное на основе многомасштабной информации комбинированное градиентное изображение, доступное для дальнейшей обработки. Поэтому, нас заинтересовала разработка метода, позволяющего получить градиентное изображение, составленное на основе многомасштабной информации, которое далее можно было бы использовать в различных методах сегментации, основанных на обработке градиентного изображения.
2. Многомасштабное градиентное изображение
В качестве оператора градиента, используемого для построения градиентного изображения определенного масштаба, нами было выбран дискретный случай дифференциального оператора Гаусса, то есть, первой производной функции Гаусса определенной на плоскости (1). Известно, что дифференциальный оператор Гаусса является единственным оператором, который обладает необходимыми для многомасштабного дифференцирования изображений свойствами [10][11].
Основой стратегии анализа многомасштабной информации нами была выбран подход последовательного комбинирования градиентных изображений от точных масштабов к грубым. При рассмотрении точных масштабов основной проблемой является большое влияние шума на градиентное изображение, на грубых же масштабах велика ошибка смещения положения контуров объектов, особенно резких, от их реального месторасположения. Здесь мы предложим подход, позволяющий избегать ошибки смещения положения контуров, в следующей главе мы предложим метод, позволяющий избегать влияние шума.
Рассмотрим для простоты, сначала, одномерный случай применения дифференциального оператора Гаусса различного масштаба для профиля изображения, содержащего резкую и плавную границы. На рис.1 показаны случаи применения оператора Гаусса точного и грубого масштабов. На рис.1а приведен профиль изображения, содержащего резкую и плавную границы объектов. При малом масштабе градиентного оператора (рис. 1б) положение резкой границы на профиле исходного изображения соответствует значительному всплеску интенсивности на градиентном изображении, однако для плавной границы всплеск интенсивности значительно меньший, чем для резкой границы. Из рис. 1в, который соответствует крупному масштабу применения дифференциального оператора, можно заметить, что, с увеличением масштаба интенсивность плавной границы на градиентном изображении будет расти. Однако на градиентном изображении малого масштаба ее интенсивность еще довольно мала. Малая интенсивность точек контура на градиентном изображении может являться причиной потери контура при дальнейшем применении к градиентному изображению методов выделения контуров. Поэтому при построении градиентного изображения желательно получать наибольшую возможную интенсивность точек контура. При крупном масштабе градиентного изображения (рис. 1в) интенсивность плавной границы становится уже довольно большой и, далее, при увеличении масштаба, остается практически постоянной. Нетрудно показать, что интенсивность границы становится близкой к максимально возможной, когда размер маски дифференциального оператора Гаусса достигает реальной ширины границы. Следовательно, для получения максимального отклика на градиентном изображении для границы ширины достаточно применение оператора градиента маштаба не меньшего чем s > WE , где s - параметр масштаба в уравнении (1).
Из рисунков 1(б) и 1(в) можно увидеть, что ширина всплеска интенсивности для резкой границы с увеличением масштаба увеличивается и становится большей, по сравнению с шириной всплеска интенсивности для этой же границы на изображении малого масштаба. При этом, максимальная величина всплеска интенсивности остается примерно на одном уровне. Величину ширины всплеска интенсивности WI на градиентном изображении масштаба s границы имеющей реальную ширину путем простых вычислений можно оценить как WI = WE + 2s. Следовательно, с увеличением масштаба s ширина всплеска интенсивности WI для границы шириной увеличивается и может привести к его наложению на отклик от другой соседней границы. Это и приводит к ошибкам смещения границ на градиентных изображениях больших масштабов - соседние, близко расположенные к друг другу границы могут сливаться в одну. В тоже время, для определения границы, то есть, для получения максимально возможного отклика, достаточно применение дифференциального оператора масштаба равного реальной ширине границы. Таким образом, мы показали, что для изображений, содержащих одновременно резкие и плавные границы, что часто встречается на практике, применение оператора одного масштаба либо недостаточно для определения плавных границ, либо дает большую ошибку положения резких границ объектов.
Мы предлагаем следующий подход к решению данной проблемы, и представляем следующий метод комбинирования многомасштабной информации при последовательном анализе градиентных изображений от точных масштабов к грубым. Начинать построение многомасштабного градиентного изображения следует с масштаба s0, соответствующего наименьшей предполагаемой ширине границы. Как уже было сказано выше, для определения границы ширины необходимо применение масштаба не меньшего чем ширина границы s > WE . Если наименьшая ширина границы неизвестна, то начинать следует с наименьшего возможного масштаба. После получения первого градиентного изображения D0(x, y) для масштаба s0 необходимо построить, используя любой традиционный метод, картину границ E0(x, y) для первого градиентного изображения, которая будет использоваться на следующем шаге процесса. Шаг Ds, с которым следует увеличивать масштаб градиентного изображения на каждом шаге, может быть выбран в зависимости от разрешения изображения или подобран экспериментально. На следующем шаге выполняется построение градиентного изображения D1(x, y) масштаба s1 = s0 + Ds . Данное градиентного изображения строится с учетом информации полученной на предыдущем шаге и выполняется следующим образом:
1) Если точка градиентного изображения D1(x, y) лежит в окрестности (s1,-s1) какой-либо границы картины контуров E0(x, y), то значение градиента масштаба s1 не расчитывается в данной точке и принимается значению градиента изображения D0(x, y) полученном на предыдущем шаге.
2) Если точка изображения D1(x, y) не лежит ни в одной окрестности (s1,-s1) границ картины контуров E0(x, y), то в этой точке расчитывается значение градиента масштаба s1.
Иными словами, для устранения эффекта «расширения границ» при продвижении к большим масштабам, мы запрещаем вычисление градиента большего масштаба в точках, прилегающих к уже известным границам ближе чем размер масштаба градиента. Тем самым, мы не получаем ложные значения градиента вблизи известных границ и, в результате, можем избежать ошибки смещения или соединения границ на больших масштабах. Данная последовательность действий завершается на некотором большом масштабе smax, размер масштаба которого характеризует наибольшую возможную ширину границы объекта.
На рисунке 1г изображен профиль градиентного изображения, полученного предлагаемым нами методом в одномерном случае. Можно видеть, что ширина всплеска интенсивности для резкой границы осталась узкой, как на изображениях малого масштаба, в то время как интенсивность отклика плавной границы велика, как на градиентном изображении большого масштаба. Недостатком данного подхода является то, что при наличие на изображении шума, на малых масштабах, когда оператор градиента особо чувствителен к наличию шума, мы можем получать ложные контуры объектов. Эти ложные границы, полученные вследствие наличия шума на изображении, могут препятствовать вычислению градиентов большего масштаба в их окрестностях. Далее мы предлагаем решение данной проблемы для частого практического случая, когда исходное изображение содержит в подавляющем большинстве объекты с замкнутыми контурами и имеющими границы с слабо меняющимся наклоном вдоль контура.
3. Модификация метода для изображений содержащих шум.
В данной главе рассматривается применение предложенного нами метода для изображений, которые можно характеризовать следующей моделью. Будем считать, что исходное изображение содержит объекты с замкнутыми контурами, и наклон границы каждого объекта вдоль контура слабо меняется. Изображения, которые можно описать данной моделью часто встречаются на практике. Действительно, сканированные изображения страниц книг, газет, журналов, содержат в подавляющем большинстве, текст, заголовки, картинки в рамках, то есть, объекты, имеющие замкнутые контуры. И, как правило, наклон границ данных объектов вдоль контура слабо меняется.
Данные предположения позволяют использовать в предложенном нами методе, на шаге определения картины границ Ei(x, y), известный метод сегментации - ватершед-преобразование [2]. Известно [1], что 
ватершед-преобразование позволяет получать всегда замкнутые границы объектов, а объекты с незамкнутыми границами не определяются. А так как в предположениях нашей модели наклон границ объектов вдоль контура слабо меняется, то применение ватершед-преобразования позволит получать замкнутые контуры объекта полностью на одном шаге масштаба. Действительно, неизменность наклона границ объектов вдоль контура позволяет получать одинаковый отклик для всех границ одного объекта на градиентном изображении конкретного масштаба.
Что дает нам использование ватершед-преобразования? Используя ватершед-преобразование, мы сможем определять такие характеристики объекта как его размер и резкость его границ, что позволит нам на основе этих характеристик классифицировать объекты на реальные объекты и ложные объекты, возникающие вследствие наличия на исходном изображении шума. Шум на цифровом изображении представляет собой сигнал высокой частоты, определенный на плоскости изображения. Поэтому, относящиеся к шуму объекты на изображении имеют небольшой размер и в основном не сильно отклоняются по интенсивности от основного сигнала. Следовательно, можно построить некую нечеткую функцию f(q, e), описывающую степень принадлежности каждого найденного объекта к шуму, где q - площадь объкта, а e – степень отклонения от основного сигнала. В качестве степени отклонения от основного сигнала нами предлагается использовать средную интенсивность границы объекта на градиентном изображении. Так как, чем меньше объект и чем меньше его отклонение от основного сигнала, тем больше он подходит под определение шума, то функция f(q, e) должна быть обратно пропорциональна площади объекта q и средней интенсивности границ объекта e. Точный вид этой функции может быть установлен экспериментально. Установив некий порог значений для данной функции, мы сможем пользуясь таким критерием разделять определяемые на изображении объекты на две категории – шум и реальные объекты. И далее удалять контуры шумовых объектов с картины границ Ei(x, y).
На рис.2 схематически изображена последовательность выполнения операций для данной модификации предлагаемого нами метода. Первый этапом построения градиентного изображения Di(x, y) масштаба si остается таким же, как он и был описан в предыдущей главе и заключается в комбинированном построении градиентного изображения масштаба si на основе градиентного изображения Di-1(x, y) масштаба si-1 и картины границ Ei-1(x, y), полученной на si-1 шаге. Далее, на втором этапе, к полученному градиентному изображению применяется метод ватершед - преобразования, который позволяет получить замкнутые контуры объектов и построить соответствующую картину границ Ei(x, y). После чего, на третьем этапе, выполняется классификация полученных объектов, используя в качестве критерия принадлежности объекта к шуму нечеткую функцию f(q, e). Границы объектов, отнесенных к шуму, удаляются с изображения границ Ei(x, y). После чего, выполняются аналогичные последовательности действий для последующих шагов.
4. Экспериментальные результаты
На рис. 3 представлен пример полутонового изображения содержащего объекты, имеющие резкие и плавные границы. Текст в верхней части изображения имеет резкие контуры, в то время как три латинские буквы в нижней части изображения имеют плавные контуры. На рис. 4а и рис. 4б прелставлено градиентное изображение точного масштаба, полученное на основе исходного изображения и, соответственно, результат применения ватершед-преобразования. На рис. 4 в и рис. 4г показаны аналогичные изображения для случая грубого масштаба. На рис. 4 д и рис. 4е показан результат использования предлагаемого алгоритма. Легко видеть, что только в случае применения предложенного алгоритма все контуры объектов были определены наилучшим образом.
5. Заключение
Предлагаемый нами метод позволяет получать комбинированное градиентное изображение, суммирующее информацию полученную на градиентных изображениях различного масштаба. В отличие от других методов, основанных на многомасштабном анализе градиентных изображений, результатом которых является картина границ, наш метод позволяет получить многомасштабное градиентное изображение, к которому далее могут быть применены традиционные методы сегментации. Анализ градиентных изображений от точных масштабов к грубым позволяет точно определить резкие контуры объектов малого размера, что является актуальным для часто встречающихся на практике изображений, содержащих буквы и символы. Предлагаемый метод позволяет избежать при переходе к крупным масштабам «размазывание» резких границ, полученных на точных масштабах. Это достигается отменой применения оператора градиента крупного масштаба в окрестностях резких границ. Но, в то же время, наш метод позволяет определить и плавные границы, получаемые только при применении дифференциального оператора крупного масштаба.
Так как предлагаемый нами метод является чувствительным к шуму, то для зашумленных изображений нами предлагается модификация метода, основанная на применении ватершед-преобразования. Предлагаемая модификация метода позволяет значительно уменьшить отрицательное влияние шума на результирующее градиентное изображение.
6. Литература
[1] R. C. Gonzalez, R. E.Woods, Digital Image Processing, Prentice-Hall, Inc, Upper Saddle River, New Jersey, pp. 617-626, 2002.
[2] S. Beucher, F. Meyer, The Morphological Approach to Segmentation: The Watershed Transformation, in “Mathematical Morphology in Image Processing”, E. R. Dougherty Editor, Marcel Dekker, Inc, New York, pp.433-481, 1992.
[3] D. Ziou, S. Tabbone, “Edge Detection Techniques”- An Overview, technical report, No. 195, Dept Math & Informatique. Universit de Sherbrooke, 1997.
[4] F. Bergholm. “Edge Focusing”. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(6), Nov 1987, pp. 726-741.
[5] D. J.Williams and M. Shas. “Edge Contours Using Multiple Scales”. Computer Vision, Graphics and Image Processing, 51, 1990, pp.256-274.
[6] V. Lacroix. “The Primary Raster: A Multiresolution Image Description”. In Proceedings of the 10th International Conference on Pattern Recognition, 1990, pp. 903-907.
[7] J. F.Canny. “A Computational Approach to Edge Detection”. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6), Nov 1986, pp. 679-698.
[8] D. Ziou and S. Tabbone. “A Multi-Scale Edge Detector”. Pattern Recognition, 26(9), 1993, pp..
[9] T. Lindeberg. “Edge Detection and Ridge Detection with Automatic Scale Selection”. In Proceedings of IEEE, International Conference on Computer Vision and Pattern Recognition, San Francisco, 1996, pp. 465-470.
[10] J. J. Koenderink and A. J. van Doorn. “Generic neighborhood operators”. IEEE Trans. Pattern Analysis and Machine Intelligence, 14(6), Jun 1992,pp.597-605.
[11] L. M. J. Florack, B. M. ter Haar Romeny, J. J. Koenderink, and M. A. Viergever. “Scale and the diferential structure of images”. Image and Vision Computing, 10(6), Jul 1992, pp.376-388.
