СПОСОБ ВЫДЕЛЕНИЯ ХАРАКТЕРНЫХ ДЕТАЛЕЙ НА ЦИФРОВЫХ ИЗОБРАЖЕНИЯХ (ВАРИАНТЫ) Российский патент 2008 года по МПК G06T7/60 

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

В настоящее время существуют способы распознавания личности по отпечаткам пальцев, основанные на использовании характерных деталей папиллярного узора (окончаний и ветвлений папиллярных линий отпечатков пальцев) [1, 2]. Эффективность указанных способов распознавания личности зависит от точности выделения характерных деталей на цифровом изображении отпечатка пальца.

Известны способы выделения характерных деталей отпечатков пальцев, включающие пороговое разделение изображения, операцию формирования скелета объектов обрабатываемого изображения (папиллярного рисунка отпечатка пальца) и выделение характерных деталей с помощью сформированного на предыдущем этапе скелета объектов обрабатываемого изображения [3-7].

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

Наиболее близким к предлагаемому изобретению является способ выделения характерных деталей, описанный в статье [8]. Этот способ включает в себя следующие этапы:

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

- операцию порогового разделения изображения, в качестве которой выступает бинаризация;

- операцию формирования скелета объектов изображения, которая заключается в выделении контуров папиллярных линий путем последовательного обхода границ объектов (папиллярных линий) бинарного изображения;

- операцию выделения характерных деталей путем выделения и анализа участков контурных линий, где линии изменяют направление на заданный угол.

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

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

Для достижения указанного результата в способе выделения характерных деталей на цифровых изображениях [8], включающем:

1) операцию порогового разделения пикселей обрабатываемого изображения,

2) операцию формирования скелета объектов обрабатываемого изображения,

3) выделение характерных деталей скелета объектов обрабатываемого изображения, предложены следующие операции, являющиеся отличительными признаками предлагаемого способа:

1) при проведении операции порогового разделения пикселей обрабатываемого изображения выполняют разделение пикселей на три непересекающиеся группы;

при этом

a) относят при последовательном просмотре изображения рассматриваемый пиксель к группе 1, если значение интенсивности пикселя меньше или равно значению первого порогового коэффициента, или

b) относят рассматриваемый пиксель к группе 2, если значение интенсивности пикселя больше значения первого порогового коэффициента, но меньше или равно значению второго порогового коэффициента, или

c) относят рассматриваемый пиксель к группе 3, если значение интенсивности пикселя больше значения второго порогового коэффициента, при этом первый пороговый коэффициент должен быть меньше второго порогового коэффициента;

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

при этом

a) находят при последовательном просмотре изображения пиксель, принадлежащий группе 1;

b) обнуляют счетчик шагов, первый и второй массивы координат пикселей;

c) удаляют найденный пиксель из группы 1 и сохраняют его координаты в первом массиве координат пикселей;

d) проводят процесс формирования скелета объектов обрабатываемого изображения:

e) при последовательном просмотре пикселей, координаты которых сохранены в первом массиве координат пикселей, просматривают все соседние пиксели изображения, и если среди них находятся пиксели, отнесенные к группе 1, то их удаляют из группы 1 и добавляют координаты этих пикселей во второй массив координат пикселей;

f) если второй массив координат пикселей пуст, то просматривают соседние пиксели всех пикселей, координаты которых сохранены в первом массиве координат пикселей, и если среди соседних пикселей находят пиксели, отнесенные к группе 2, то их удаляют из группы 2, а их координаты сохраняют во втором массиве координат пикселей;

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

h) сохраняют координаты этого и предыдущего центрального пикселя, в массив ребер скелета объектов обрабатываемого изображения;

i) первый массив координат пикселей заменяют вторым массивом координат пикселей; после чего во втором массиве координат пикселей удаляются все элементы;

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

k) увеличивают счетчик шагов на 1;

l) в процессе последовательного просмотра пикселей, координаты которых сохранены в первом массиве координат пикселей, формируют из них связные области пикселей;

m) создают массивы для хранения координат пикселей по числу связных областей и переносят координаты пикселей, составляющих каждую связную область, в отдельный массив координат пикселей связной области, для каждого из созданных массивов запоминается отдельно значение координат последнего центрального пикселя;

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

о) если вышеуказанный критерий окончания процесса формирования скелета объектов обрабатываемого изображения не удовлетворяется, продолжают последовательный просмотр пикселей изображения, если среди них находятся пиксели группы 1, повторяют описанный выше процесс формирования скелета объектов обрабатываемого изображения;

р) преобразуют полученный массив ребер скелета объектов обрабатываемого изображения к его растровому представлению путем рисования ребер скелета на изображении;

3) при выделении характерных деталей скелета объектов обрабатываемого изображения определяют параметры характерных деталей путем трассировки скелета;

при этом

a) при последовательном просмотре пикселей растрового представления скелета объектов обрабатываемого изображения для каждого пикселя подсчитывают число соседних пикселей, принадлежащих растровому скелету объектов обрабатываемого изображения, если число соседних пикселей равно одному, то пиксель помечается как пиксель-кандидат окончания линии, если число соседних пикселей равно трем или более, то пиксель помечается как пиксель-кандидат ветвления линии, пиксели окончания и ветвления линии считают характерными деталями скелета обрабатываемого изображения;

b) при последовательном просмотре для очередного пикселя-кандидата растрового представления скелета объектов обрабатываемого изображения, проводят трассировку с заданным числом шагов, в результате трассировки определяют количество скелетных линий, отходящих от рассматриваемого пикселя-кандидата, а также их длину;

c) если от рассматриваемого пикселя отходит одна скелетная линия, длина которой в пикселях не меньше, чем заданное число шагов трассировки, то данный пиксель помечают как окончание линии;

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

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

Краткое описание чертежей.

На фиг.1 приведена схема алгоритма, реализующего способ-прототип.

На фиг.2 изображена схема алгоритма, реализующего предлагаемый способ.

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

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

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

Вариант 1

В качестве входных данных для предлагаемого способа выступает полутоновое (в градациях серого) цифровое изображение Р, которое имеет размеры Н×W, которое может быть предварительно подвергнуто операции улучшения, например, как описано в работе [4].

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

a) пороговое разделение пикселей обрабатываемого изображения (Фиг.2, блок 2.1);

b) формирование скелета объектов обрабатываемого изображения (Фиг.2, блок 2.2);

с) выделение характерных деталей скелета объектов обрабатываемого изображения (Фиг.2, блок 2.3).

Операция порогового разделения пикселей обрабатываемого изображения (Фиг.3) заключается в выборе очередного пикселя р_i,j∈P, i=1, ..., H, j=1, ..., W при последовательном просмотре пикселей обрабатываемого изображения Р (Фиг.3, блок 3.1). В случае если все пиксели просмотрены (Фиг.3, блок 3.2), операция порогового разделения завершается.

Обозначим через G₁, G₂, G₃ первую, вторую и третью группы пикселей соответственно. Рассматриваемый пиксель р_i,j∈Р включают в группу G₁, если р_i.j≤K₁ (Фиг.3, блоки 3.3 и 3.4). В противном случае пиксель р_i,j∈Р включают в группу G₂, если р_i,j≤K₂ (Фиг.3, блоки 3.5 и 3.6). Здесь К₁ и К₂ - первый и второй пороговые коэффициенты, связанные между собой отношением К₁<К₂. Если рассматриваемый пиксель р_i,j∈Р на предыдущих шагах не был включен в состав групп G₁ и G₂, то пиксель р_i,j∈Р включают в группу G₃ (Фиг.3, блок 3.7).

Операция формирования скелета объектов обрабатываемого изображения (Фиг.4) заключается в следующем: при последовательном просмотре пикселей обрабатываемого изображения выбирают очередной пиксель р_i,j∈G₁ (Фиг.4, блок 4.1). Если группа G₁ оказывается пустой (Фиг.4, блок 4.2), то производят преобразование сформированного массива ребер скелета R в растровое представление S (Фиг.4, блок 4.3) и завершают операцию формирования скелета объектов для обрабатываемого изображения Р.

Для выбранного на предыдущем шаге пикселя р_i,j∈G₁ выполняют следующие действия. Производят инициализацию счетчика шагов С=0, а также обнуление первого и второго массивов координат пикселей M₁ и М₂ (Фиг.4, блок 4.4). Затем координаты выбранного пикселя р_i,j∈G₁ добавляют в массив М₁, а пиксель р_i,j удаляют из группы G₁ (Фиг.4, блок 4.5). Затем выполняется добавление элементов в массив М₂; (Фиг.4, блок 4.6). При этом для каждого пикселя р_i,j, координаты которого включены в массив M₁, проводят последовательный просмотр пикселей р_i+dx,j+dy. Здесь dx∈{-1,0,1} и d_y={-1,0,1} - значения приращений соответствующих координат пикселей. В случае, если очередной пиксель р_i+dx,j+dy∈G₁, пиксель р_i+dx,j+dy удаляют из группы G₁, а его координаты добавляют в массив М₂. Затем проводят проверку, пуст ли массив М₂ (Фиг.4, блок 4.7).

Если массив М₂ не пуст, то удаляют все элементы из массива M₁, а все элементы массива М₂ переносят в массив М₁ (Фиг.4, блок 4.9). После этого выполняют процедуру добавления очередного ребра в массив ребер формируемого скелета R (Фиг.4, блок 4.11). Если величина С оказывается кратной заданному значению частоты дискретизации скелета, то производят вычисление координат центрального пикселя с=(x_c,,y_c):

где N_M - количество элементов в массиве координат М₁; элемент массива координат M₁. Затем формируют очередное ребро скелета (с, с′) и добавляют его в массив ребер R. Здесь с' - центральный пиксель, полученный на предыдущем шаге. В случае если С=0, то ребро не добавляют и только запоминают координаты центрального пикселя с=(х_С,, у_С).

После этого переходят к выполнению операции С=С+1 (Фиг.4, блок 4.13). Затем переходят к формированию связных областей и соответствующих им массивов координат пикселей Z_C,j, j=1, ..., N_C (Фиг.4, блок 4.15). Здесь N_C - количество связных областей для текущего значения шага С.

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

Затем в качестве массива М₁ выбирают массив координат пикселей Z_C,1, а в качестве последнего центрального пикселя с′ - пиксель , и переходят к добавлению очередных элементов в массив М₂ (Фиг.4, блок 4.6).

Если массив М₂ оказывается пустым (Фиг.4, блок 4.7), то выполняют процедуру добавления дополнительных элементов в массив М₂ (Фиг.4, блок 4.8). Для каждого пикселя p_i,j, координаты которого включены в массив М₁, проводят последовательный просмотр пикселей р_i+dx,j+dy. Здесь dx∈{-1,0,1} и dy={-1,0,1} - значения приращений соответствующих координат пикселей. В случае если очередной пиксель р_i+dx,j+dy∈G₂, то пиксель р_i+dx,j+dy удаляют из группы G₂, а его координаты добавляют в массив М₂. Затем проводят проверку, пуст ли массив М₂ (Фиг.4, блок 4.10).

В случае, если массив М₁ не пуст, переходят к операции обновления массивов М₁ и М₂ (Фиг.4, блок 4.9). Иначе, если значение счетчика шагов С отлично от нуля, то выполняют процедуру добавления конечного ребра в массив ребер скелета R (Фиг.4, блок 4.12). Для этого производят вычисление координат центрального пикселя с=(x_C,,y_C):

где N_M - количество элементов в массиве координат M₁; элемент массива координат M₁. Затем формируют очередное ребро скелета (с, с′) и добавляют его в массив ребер R.

Затем переходят к выбору очередного непустого массива Z_i,j, i=0, ..., C, j=1, ..., N_i и полагают М₁=Z_i,j, а с′=. Здесь N_i - количество связных областей для i-го значения счетчика шагов С. В случае, если все массивы Z_i,j=⊘ (Фиг.3, блок 3,16), то переходят к выбору очередного пикселя р_i,j∈G₁ (Фиг.4, блок 4.1). Иначе переходят к добавлению очередных элементов в массив М₂ (Фиг.4, блок 4.6).

Операция выделения характерных деталей (Фиг.5) проводится для построенного на предыдущем этапе растрового представления скелета S объектов обрабатываемого изображения. Обозначим через S′ множество пикселей, принадлежащих непосредственно построенному скелету объектов. При последовательном просмотре пикселей растрового представления скелета выбирают очередной пиксель s_i,j∈S′, i=1, ..., H, j=1, ..., W (Фиг.5, блок 5.1). В случае если все пиксели просмотрены (Фиг.5, блок 5.2), операция выделения характерных деталей завершается.

Для выбранного пикселя s_i,j∈S′ определяют количество N_s соседних пикселей, которые также принадлежат множеству S′ (Фиг.5, блок 5.3). Если N_s=0 или N_s=2 (Фиг.5, блок 5.4), то выбранный пиксель s_i,j∈S′ не принадлежит к множеству характерных деталей скелета объектов для обрабатываемого изображения. В этом случае переходят к выбору следующего пикселя s_i,j∈S′ (Фиг.5, блок 5.1). Иначе проводят трассировку скелета S' (Фиг.5, блок 5.5). При этом трассировку начинают с выбранного пикселя s_i,j∈S'. Число шагов трассировки задается пороговой величиной T_max. По окончании трассировки определяют количество скелетных линий N_L, длина которых в пикселях L_k≥T_max, k=1, ..., N_TL (здесь N_TL - общее количество скелетных линий), отходящих от выбранного пикселя s_i,j∈S′.

В случае если N_L=1 (Фиг.5, блок 5.6), то выбранный пиксель s_i,j∈S′ помечают как характерную деталь - окончание линии (Фиг.5, блок 5.9). После пометки пикселя s_i,j∈S′ переходят к выбору очередного пикселя s_i,j∈S′ (Фиг.5, блок 5.1).

В противном случае определяют углы α_m, m=1, ..., N_L между соседними отходящими от выбранного пикселя s_i,j∈S' скелетными линиями (Фиг.5, блок 5.7). Затем среди полученных углов определяют α_min=minα_m и α_max=maxα_m. Если α_min≤К_α1 и α_max≤К_α2 (Фиг.5, блок 5.8), то выбранный пиксель s_i,j∈S' помечают как характерную деталь - ветвление линии (Фиг.5, блок 5.10). Здесь K_α1 и К_α2 - первый и второй пороговые коэффициенты угла соответственно.

После пометки пикселя s_i,j∈S′ переходят к выбору очередного пикселя s_i,j∈S′ (Фиг.5, блок 5.1). В противном случае, непосредственно переходят к выбору следующего пикселя s_i,j∈S′ (Фиг.4, блок 5.1).

Вариант 2

При формировании скелета объектов обрабатываемого изображения волновым методом операции, представленные блоками 4.6-4.13, 4.15 на фиг.4, выполняются параллельно для каждого из массивов Z_i,j≠⊘, i=0, ..., C, j=1, ..., N_i. При этом нет необходимости в операции выбора очередного непустого массива Z_i,j (Фиг.4, блок 4.14). Необходимо заметить, что для указанных выше операций, выполняемых параллельно, в качестве массива M₁ выступает соответствующий массив Z_i,j, а в качестве последнего центрального пикселя с′ выступает .

Источники информации

1. Ratha N.K., Karu К., Chen S., Jain A.K. A Real-Time Matching System for Large Fingerprint Databases // IEEE Trans. on Pattern Analysis and Machine Intelligence, 1996, vol. 18, no. 8, pp.799-813.

2. Jain A.K., Hong L., Bolle R., On-line Fingerprint Verification // IEEE Trans. on Pattern Analysis and Machine Intelligence, 1997, vol. 19, no. 4, pp.302-313.

3. Mehtre B.M. Fingerprint Image Analysis for Automatic Identification // Machine Vision and Application, 1993, vol. 6, no. 2-3, pp.124-139.

4. Thai R. Fingerprint Image Enhancement and Minutiae. Extraction. - Technical Report, The University of Western Australia, 2003, 71 p.

5. Пат.6901155 США МКИ⁷ G06K 9/00. Wavelet-enhanced automated fingerprint identification system/ Xia, Tao (Сингапур); National University of Singapore (Сингапур). - №09/742405; Заяв. 22.12.2000; Опубл. 19.09.2006; НКИ 382/124. - 14 с., 5 л. ил.

6. Пат.5105467 США МКИ⁵ G06K 9/00. Method of fingerprint verification / Kirn Bong I (Республика Корея). - №618299; Заяв. 27.11.1990; Опубл. 14.04.1992; НКИ 382/4. - 7 с., 8 л. ил.

7. Пат.6282304 США МКИ⁷ G06K 9/00. Biometric system for biometric input, comparison, autentification and access control and method therefor / S.O. Novikov (США); Biolink Technologies International, Inc. (США). - №09/312002; Заяв. 14.05.1999; НКИ 382/125; - 6 с., 10 л. ил.

8. Govindaraju V., Shi Z., Schneider J. Feature Extraction Using a Chaincoded Contour Representation of Fingerprint hnages // AVBPA 2003, pp 268-275.

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

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

при проведении операции порогового разделения пикселей обрабатываемого изображения выполняют разделение пикселей на три непересекающиеся группы,

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

при выделении характерных деталей скелета объектов обрабатываемого изображения определяют параметры характерных деталей путем трассировки скелета.

при этом, если второй массив координат пикселей пуст, то просматривают соседние пиксели всех пикселей, координаты которых сохранены в первом массиве координат пикселей, и, если среди соседних пикселей находят пиксели, отнесенные к группе 2, то их удаляют из группы 2, а их координаты сохраняют во втором массиве координат пикселей;

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

сохраняют координаты этого и предыдущего центрального пикселя в массив ребер скелета объектов обрабатываемого изображения;

первый массив координат пикселей заменяют вторым массивом координат пикселей; после чего во втором массиве координат пикселей удаляются все элементы;

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

увеличивают счетчик шагов на 1;

в процессе последовательной просмотра пикселей, координаты которых сохранены в первом массиве координат пикселей, формируют из них связные области пикселей;

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

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

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

преобразуют полученный массив ребер скелета объектов обрабатываемого изображения к его растровому представлению путем рисования ребер скелета на изображении.

при последовательном просмотре пикселей растрового представления скелета объектов обрабатываемого изображения для каждого пикселя подсчитывают число соседних пикселей, принадлежащих растровому скелету объектов обрабатываемого изображения, если число соседних пикселей равно одному, то пиксель помечается как пиксель-кандидат окончания линии, если число соседних пикселей равно трем или более, то пиксель помечается как пиксель-кандидат ветвления линии, пиксели окончания и ветвления линии считают характерными деталями скелета обрабатываемого изображения;

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

если от рассматриваемого пикселя отходит одна скелетная линия, длина которой в пикселях не меньше, чем заданное число шагов трассировки, то данный пиксель помечают как окончание линии;

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