Устранение нерегулярностей

Нерегулярности можно устранять на уровне исходных фигур или построенных скелетов [340], а также комбинируя эти два способа [79], [341]. Определим некоторые базовые процедуры устранения нерегулярностей скелета.

Устранение рудиментных терминальных рёбер

Устранение нерегулярности первого типа обычно представляет собой стрижку (удаление) терминальных рёбер скелета. Например, в работе [340] выполняется стрижка всех терминальных рёбер скелета. Большинство методов стрижки эвристические. Математически строгий метод – построение базового скелета с фиксированной точностью аппроксимации [79] (рис. 6.1.38). Обозначим – оператор, который строит базовый скелет с точностью.

@Рис. 6.1.38: Результаты устранения рудиментных терминальных ребер.

Устранение перехлёстов

В работе [341] описана проблема «перехлёста» в рамках задачи поиска аппроксимирующих фигур с изоморфными скелетами. Для ее решения предложено проводить удаление внутренних ребер скелетного графа – так называемую склейку ребер (рис. 6.1.39). Обозначим через оператор, который проводит склейку всех ребер скелета таким образом, что фигурадеформируется не более, чем на величинув метрике Хаусдорфа (то есть склейка с точностью).

@Рис. 6.1.39: Устранение внутренних коротких ребер.

Утранение циклов

Устранение циклов в топологическом смысле выполняется довольно просто: нужно разорвать этот цикл и удалить его часть из скелета. Но по метрическим критериям этого недостаточно. Например, слон с глазом-«дыркой» при разрыве цикла потеряет часть головы со стороны разрыва цикла (рис. 6.1.40). С другой стороны, появление мелких отверстий в дискретной фигуре за счёт шумов – это обычное дело. Можно выполнять регуляризацию на уровне фигуры, для чего использовать диаметры дыр. Необходимо выставить порог по диаметру «дырки» и удалить контуры, окружающие мелкие отверстия, что устранит указанную нерегулярность (рис. 6.1.41). Обозначим через оператор, который удаляет все «дырки» фигуры таким образом, что фигурадеформируется не более, чем на величинув метрике Хаусдорфа (устранение циклов с точностью ).

@Рис. 6.1.40: Устранение циклов как преобразование скелета: a-б – скелет с циклом и фигура; в – удаление цикла; г – потеря части головы.

@Рис. 6.1.41: Устранение циклов как преобразование фигуры: a-б – скелет с циклом и фигура; в – преобразование фигуры; г – скелет без цикла.

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