Патент на изобретение №2328770

(54) СПОСОБ ВЫДЕЛЕНИЯ ХАРАКТЕРНЫХ ДЕТАЛЕЙ НА ЦИФРОВЫХ ИЗОБРАЖЕНИЯХ (ВАРИАНТЫ)

(57) Реферат:

Настоящее изобретение относится к цифровой обработке изображений. Технический результат заключается в уменьшении числа ложно выделенных характерных деталей изображения, а также в снижении вычислительных затрат на последующих этапах, направленных на удаление ложных характерных деталей. Технический результат достигается за счет использования операции порогового разделения пикселей изображения на три группы с последующим построением скелета с помощью волнового метода, а также за счет определения параметров характерных деталей с помощью трассировки скелета и применения правил отбраковки ложных характерных деталей при выделении характерных деталей. 5 з.п. ф-лы, 5 ил.P, i=1, …, H, j=1, …, W при последовательном просмотре пикселей обрабатываемого изображения Р (Фиг.3, блок 3.1). В случае если все пиксели просмотрены (Фиг.3, блок 3.2), операция порогового разделения завершается.

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

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

Для выбранного на предыдущем шаге пикселя р_i,jG₁ выполняют следующие действия. Производят инициализацию счетчика шагов С=0, а также обнуление первого и второго массивов координат пикселей M₁ и М₂ (Фиг.4, блок 4.4). Затем координаты выбранного пикселя р_i,jG₁ добавляют в массив М₁, а пиксель р_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+dyG₁, пиксель р_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+dyG₂, то пиксель р_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,jG₁ (Фиг.4, блок 4.1). Иначе переходят к добавлению очередных элементов в массив М₂ (Фиг.4, блок 4.6).

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

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

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

В противном случае определяют углы _m, m=1, …, N_L между соседними отходящими от выбранного пикселя s_i,jS’ скелетными линиями (Фиг.5, блок 5.7). Затем среди полученных углов определяют _min=min_m и _max=max_m. Если _minК₁ и _maxК₂ (Фиг.5, блок 5.8), то выбранный пиксель s_i,jS’ помечают как характерную деталь – ветвление линии (Фиг.5, блок 5.10). Здесь K₁ и К₂ – первый и второй пороговые коэффициенты угла соответственно.

После пометки пикселя s_i,jS переходят к выбору очередного пикселя s_i,jS (Фиг.5, блок 5.1). В противном случае, непосредственно переходят к выбору следующего пикселя s_i,jS (Фиг.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, а в качестве последнего центрального пикселя с выступает .

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

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 л. ил.

Формула изобретения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

РИСУНКИ