9.3.4. ОПИСАНИЯ, ОСНОВАННЫЕ НА НЕРЕГУЛЯРНОСТЯХ

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

9.3.4.1. Выпуклая оболочка и дефицит, выпуклости

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

как множество, ограниченное резиновой лентой, натянутой по периметру множества 5. Разность множеств называется дефицитом выпуклости D множества 5. На рис. 9.16 дефицит выпуклости множества S показан в виде заштрихованной области. Очевидно, что любое множество полностью определяется его выпуклой оболочкой и дефицитом выпуклости. Причина, по которой мы рассматриваем эти множества в описаниях объектов, заключается в том, что они часто позволяют разделить естественным образом сложный объект на несколько менее сложных частей. Например, если читатель поставит задачу описать на английском языке множество S на рис. 9.16, он может с успехом ее решить, описав сначала выпуклую оболочку, а потом обе части дефицита выпуклости. Естественным образом можно получить дальнейшее разделение объекта, заметив, что компоненты всякого дефицита выпуклости распадаются на два различных вида: компоненты, лежащие на границе выпуклой оболочки, и компоненты, заключенные в множество 5. За неимением лучшего термина эти два вида компонент иногда называют заливами и озерами. На рис. 9.16 часть есть залив, а часть — озеро. Заливы и озера объекта могут быть описаны их номером, приблизительным положением относительно объекта и в общем любыми средствами, имеющимися для описания объектов. Таким образом, описание объекта может состоять из описания его выпуклой оболочки, которая обычно проще, чем сам объект, а также его озер и заливов.

Рис. 9.16. Дефицит выпуклости объекта.

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

9.3.4.2. Локальные экстремумы границы объекта

В предыдущем пункте мы обсуждали способ описания кривой через ее точки высокой кривизны. Довод здесь заключался в том, что информативными следует считать такие точки, в которых имеют место какие-либо резкие изменения. Подобным же образом мы можем описать границу объекта с помощью точек, в которых она достигает локального экстремума по оси X или Y. На рис. 9.17, например, точки 1, 2, 3 и 5 представляют собой попеременно локальные минимумы и максимумы в направлении оси X, а точки 4 и б — максимум и минимум (единственные) в направлении оси Y. Как видно из рисунка, эти точки находятся вблизи точек границы с высокой кривизной, что бывает часто, хотя и не всегда.

Рис. 9.17. Локальные экстремумы объекта.

Если должно использоваться описание объекта через экстремальные точки, необходимо, очевидно, сгладить малые флуктуации границы объекта. Один из способов выполнить эту операцию заключается в регуляризации объекта посредством скользящего среднего, но при этом неизбежно возникает существенная потеря разрешающей способности. Более мощный метод называется гистерезисным сглаживанием. Гистерезисное сглаживание на самом деле представляет собой нелинейную процедуру для отыскания «существенных» экстремумов вещественной функции; для целей описания объекта она просто применяется отдельно к координатам X и Y точек границы. Имея это в виду, проиллюстрируем ее действие на примере функции одной переменной.

Предположим, как показано на рис. 9.18, нам дана функция существенный экстремум которой мы ищем. Вообразим, что вертикальный проволочный прямоугольник перемещается вдоль кривой посредством указателя, который точно отслеживает функцию g. Считается, что проволочный прямоугольник обладает следующим свойством: не перемещается вверх до тех пор, пока его не потянет вверх указатель, и, наоборот, не перемещается вниз до тех пор, пока его не потянут вниз. Другими словами, прямоугольник просто тянут в сторону вдоль кривой, не изменяя его вертикального положения. В точке А объекта указатель при его движении вдоль кривой тянет прямоугольник вверх. В точке В указатель только что прошел малый локальный максимум, а прямоугольник просто перемещается в сторону на одной и той же высоте, поскольку его не

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

Рис. 9.18. Механизм гистерезисного сглаживания.

Локальный экстремум сглаженной функции определяет существенный локальный экстремум исходной функции. В типичном случае, как показано на рис. 9.18, сглаженная функция достигает локального экстремума не в единственной точке. Когда это имеет место, разумно в качестве экстремальной выбрать точку с наименьшей координатой X — в данном случае точку С. (Заметим, что область функции вблизи точки В является «областью перегиба», а не экстремума.)

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

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

Рис. 9.19. Регуляризация функций.

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

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

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