9.2.4.2. Точки максимальной кривизны

Нам хотелось бы рассмотреть здесь задачу сегментации несколько иного рода. Пусть задан гладкий контур (он может быть получен, например, с помощью процедуры прослеживания контура). В чем может заключаться разумный способ разбиения этой кривой на последовательные прямолинейные отрезки? Один способ, подсказанный психологическими экспериментами, состоит в том, чтобы разбить кривую в точках высокой кривизны и соединить точки излома прямыми линиями. Ценность этого метода подтверледается известным рисунком, принадлежащим Аттни- ву ^), который построен в соответствии с описанным правилом (рис. 9.7).

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

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

наносим сетку на аналоговую картинку и фиксируем точки, в которых кривая пересекает линии сетки. Для представления кривой отбираются узлы сетки, ближайшие к каждому пересечению. Рис. 9.8, а показывает выделенные узлы для данной кривой. Затем мы кодируем последовательность узлов восьмеричными числами, обозначая направления от одного узла к другому в соответствии с кодами, показанными на рис. 9.8, б. Так, например, цепное кодирование данной кривой начиная с крайней нижней точки дает последовательность 1, 1, 2, 1, 0. Заметим, что такая схема может рассматриваться как дискретный вариант естественного уравнения кривой. Код определяет угол (в другом варианте — изменение угла) как функцию длины дуги с учетом того, что диагональные отрезки в У^2 раз длинней, чем вертикальные и горизонтальные.

Цепное кодирование особенно удобно при сравнении формы двух кривых. Предположим для простоты, что мы хотим измерить сходство между двумя кривыми одинаковой длины и ориентации. Обозначим цепи через а=аи . . . , а„ и b=bi, . . . , Ь„. Определим цепную взаимно-корреляционную функцию С^ь Двух кривых с по-

мощью выражения 1-де

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

где k — длина общего уч^астка двух последовательностей. Таким образом, наилучшее соответствие достигается вычислением величины Саь(І) для всех значений сдвига / и выбором максимальной из них. Главное ограничение эффективности цепной функции взаимной корреляции связано с тем, что обе кривые должны иметь одинаковый масштаб и ориентацию. Если хотя бы одно из этих условий нарушается, то либо следует отвергнуть этот метод, либо нужно повернуть на плоскости одну из последовательностей и (или) изменить ее масштаб относительно другой.