9.3.5. СКЕЛЕТ ОБЪЕКТА

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

Существует много эквивалентных определений скелета объекта. По-видимому, наиболее близко к интуитивным представлениям следующее определение. Представим себе, что внутренняя часть объекта покрыта сухой травой, а его окрестность (т. е. фон) — негорючей сырой травой. Предположим, что огонь возник одновременно во всех точках на границе объекта. Огонь будет распространяться с неизменной скоростью по направлению к центру объекта. Однако в некоторых точках линия продвижения огня от одной области границы будет пересекать фронт огня от какой-либо другой области, и эти два фронта будут гасить друг друга. Эти точки называются точками гашения огня; множество точек гашения определяет скелет объекта. Рассмотрим два очень простых примера. Если объект имеет форму круга, линия продвижения огня будет описываться концентрическими окружностями с непрерывно уменьшающимся радиусом до тех пор, пока огонь не погаснет в центре круга. В этом простейшем из всех возможных случаев скелет состоит из единственной точки — из центра круга. В качестве второго примера рассмотрим прямоугольник на рис. 9.20. Линия продвижения огня сначала также имеет прямоугольную форму, и прилегающие стороны гасят друг друга, образуя ребра скелета а, b, с и d. В некоторый момент эти ребра заканчиваются, короткие стороны огненного прямоугольника становятся равными нулю, а две оставшиеся длинные стороны гасят друг друга, образуя ребро скелета.

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

расстояние от х до ближайшей точки множества А. Формально величина для данной метрики d определяется выражением

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

Рис. 9.20. Скелет прямоугольника.

Интуитивно ясно, что это определение скелета эквивалентно предыдущему. Поскольку огонь распространяется с постоянной скоростью, точки гашения должны быть эквидистантны по крайней мере двум отдельным точкам границы, которые в свою очередь должны быть ближе к точке гашения, чем все другие граничные точки. Ясно, что для круглого объекта только центр удовлетворяет этому условию. На рис. 9.20 ребра а, b, с и d эквидистантны одной длинной и одной короткой стороне прямоугольника, а ребро эквидистантно двум длинным сторонам. Это определение делает очевидной зависимость скелета от выбора метрики d. Здесь мы молчаливо приняли евклидову метрику и будем продолжать ее использовать.

Метрическая интерпретация понятия скелета дает естественное средство для построения более полного описания объекта. Свяжем с каждой точкой х скелета объекта, имеющего границу В, величину определяемую равенством

Функция называется функцией гашения скелета. Очевидно, что она представляет собой просто расстояние от данной точки скелета до границы объекта. (Мы можем также заметить, что величина

пропорциональна времени, в течение которого огонь достигает точки Для каждого объекта, имеющего скелет 5 и функцию гашения q, мы назовем пару скелетной парой объекта. Наибольший интерес представляет тот факт, что исходный объект может быть восстановлен по его скелетной паре. Восстановление выполняется просто: каждую точку х скелета мы делаем центром диска с радиусом Объединение всех таких дисков точно соответствует исходному объекту. Таким образом, скелетная пара в некотором смысле представляет собой естественное расширение описания круга на произвольные множества.

Рассмотрим несколько подробнее утверждение, что скелетная пара содержит всю информацию, необходимую для восстановления исходного объекта. Чтобы установить истинность этого утверждения, мы должны показать, что множество F точек объекта идентично объединению U дисков. Мы покажем это неформально, обычным способом — продемонстрировав, что каждое из множеств содержится в другом. Сначала предположим, что точка у принадлежит множеству U. Тогда у принадлежит по крайней мере одному из дисков. Но по определению каждый диск содержится в множестве F, так как радиус любого диска представляет собой расстояние от центра диска х до границы F. Следовательно, у принадлежит F. С другой стороны, предположим, что нам дана точка у, принадлежащая F. Чтобы показать, что у принадлежит также U, достаточно найти один диск, содержащий у. Мы можем найти такой диск следующим образом. Сначала проведем линию от у до ближайшей точки границы. Эта линия устанавливает последовательные положения фронта огня по мере его приближения к точке у. Продолжим эту линию за точку у, пока она не достигнет точки гашения х, лежащей на скелете. Диск с центром в точке х содержит точку у; следовательно, у принадлежит

Мы видели сейчас, что функцию гашения можно использовать для дополнения скелета S с тем, чтобы получить полное описание объекта. Ее можно также применять для получения менее информативного и поэтому более простого описания. Основная идея заключается в том, чтобы исключить части скелета, вдоль которых огонь распространяется медленно. Проверим эту идею с помощью рис. 9.20. Предположим сначала, что огонь распространяется по нормали к своему фронту с единичной скоростью. Тогда каждое из ребер а, b, С и d делит пополам соответствующий ему прямой угол, что можно видеть непосредственно из обоих определений скелета. Нетрудно установить, наконец, что каждая из точек А, В, С и D движется вдоль соответствующего ребра со скоростью 12. С другой стороны, вдоль ребра огонь распространяется с бесконечной скоростью, так как это ребро формируется полностью в один момент времени. Мы можем тогда принять решение исключить из скелета все ребра, для которых скорость распространения меньше чем 1,5.

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

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

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

Рис. 9.21. Восстановление объекта по скелету, состоящему из одного ребра.

Рис. 9.22. Скелет вблизи угла границы.

Попробуем вникнуть немного глубже в смысл понятия скорости распространения вдоль ребра. Предположим, у нас есть часть границы объекта, как это показано на рис. 9.22, где две прямые линии пересекаются под углом 20. Скелет в этой области объекта делит угол пополам. Поскольку мы сразу же получим, что Таким образом, чем больше угол между двумя сторонами границы, тем меньше скорость распространения вдоль этой части скелета. Две крайние скорости равны единице и бесконечности, и достигаются они соответственно, когда угол либо вырождается

(см. скан)

Рис. 9.23. Пример скелета.

(см. скан)

Рис. 9.24. Скелет, обработанный с порогом 1,25.

(см. скан)

Рис. 9.25. Скелет, обработанный с порогом 1,5.

в прямую линию, либо, постепенно уменьшаясь, превращается в две параллельные линии (как для ребра на рис. 9.20). Таким образом, игнорирование ребер скелета с низкой скоростью распространения сводится, грубо говоря, к игнорированию слабых изгибов «почти прямых» линий.

Более сложный пример показан на рис. 9.23-9.25, где изображен многоугольный объект с одной дырой. Рис. 9.23 показывает его полный скелет. Существует интересная теорема, утверждающая, что скелет любого многоугольника составлен из частей, которые суть либо прямые линии, либо дуги парабол. Фундаментальная причина заключается в том, что геометрическое место точек, равноудаленных от двух прямых линий, есть прямая (биссектриса угла), а геометрическое место точек, равноудаленных от точки и прямой, есть парабола. На рис. 9.24 показан скелет, на котором стерты все части, имеющие скорость распространения меньше чем 1,25. Единственное изменение наблюдается внизу слева, где стерты ветви, связанные с тупыми углами границы. Если бы объект был восстановлен по этому скелету, его нижний левый угол представлял бы собой четверть круга. На рис. 9.25 порог был повышен до 1,5. Здесь один только скелет (т. е. взятый без функции гашения) весьма близко соответствует тому, что можно считать аппроксимацией объекта «внутренними» линиями.

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