28. Выделение средних линий объектов изображения.

Задача выделения средних линий (скелетов) изображений является одной из основных задач предварительной обработки. Средние линии позволяют описывать геометрические особенности объектов и удобны для последующей обработки. Термин «утоньшение» – наиболее общий термин для обозначения процесса преобразования линий, имеющие ширину в несколько пикселей, в линии единичной ширины. К операциям утоньшения предъявляются, как правило, три основных требования:

- связность объектов изображения и фона должна быть сохранена;

- концы средней линии должны располагаться как можно ближе к их истинному положению;

- центральные линии объектов должны быть выделены достаточно точно.

Как правило, все существующие алгоритмы удовлетворяют этим требованиям. Эти алгоритмы можно условно разделить на несколько групп на основе идеи или метода. Рассмотрим сперва алгоритмы, работающие с бинарными растровыми изображениями.

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

Алгоритмы данной группы можно разделить на два класса: параллельные и последовательные. В параллельных алгоритмах окно располагается одновременно во всех пикселях, и при его обработке не используются новые (полученные на данной итерации) значения пикселей. При работе последовательных алгоритмов пиксели обрабатываются последовательно, и последнее правило не соблюдается.

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

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

Уменьшение или сохранение обрабатываемого пикселя зависит от конфигурации его окрестности.

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

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