Устройство восстановления папиллярных узоров оптечатка пальца
FINGERPRINT PAPILLARY PICTURES RECONSTRUCTION DEVICE

Предлагаемое изобретение относится к области вычислительной техники и может быть использовано в системах анализа и обработки изображений, цифровом телевидении.
Известен способ восстановления изображений на основе заполнения похожими областями и устройство его реализующее (Image region filling by exemplar-based inpainting) [[Patent USA US 6987520 В2]. Данное устройство может быть использовано при обработке изображений. Метод работы устройства основывается на поиске похожего квадратного блока в области доступных пикселей и его копировании в область отсутствующих пикселей, тем самым уменьшая или минимизируя объем ручного редактирования, необходимый для заполнения области на изображении. Алгоритм устройства состоит из следующих шагов: Записываются значения входного изображения, определяется значение коэффициента доверия, вычисляется значение приоритета для каждого значения пикселя границы с определением пикселей с максимальным значением приоритета, определяется квадратная форма области для поиска подобия с центральным пикселем, вычисляется евклидова метрика для всех доступных значений пикселей изображения, восстанавливаются значения пикселей из области для которой евклидова метрика минимальна, пересчитывается коэффициент доверия для восстановленных пикселей, затем процедуры повторяются, пока не будут восстановлены все значения пикселей.
Признаки аналога, совпадающие с признаками заявляемого технического решения, следующие: вычисление приоритета для всех граничных пикселей (в заявляемом устройстве - блок вычисления приоритета), вычисление евклидовой метрики (в заявляемом устройстве - блок поиска подобия), копирование значений пикселей из найденного блока в потерянную область (в заявляемом устройстве - блок заполнения изображения).
Недостатками известного способа и устройства, его реализующего являются:
- видимость границ на восстановленном изображении между найденными похожими блоками;
- неправильное восстановление при отсутствии похожего блока;
- зависимость эффективности восстановления от выбора размера блока.
k
Известно цифровое сглаживающее устройство с предварительным обнаружением и устранением аномальных измерений [Патент РФ №2010325, МПК G06F 15/353]. Данное устройство может быть использовано при обработке изображений, при этом потерянные пиксели принимаются за аномальные. Блок обнаружения и устранения аномальных измерений обеспечивает получение абсолютной величины разности  между текущим k-м отсчетом входного сигнала S и значением сглаженного выходного сигнала  схема сравнения обеспечивает сравнение сигнала абсолютной величины разности  с кодом допустимого значения строба Δ и формирует на выходе признак превышения.
В сглаживающем устройстве реализуется следующий алгоритм сглаживания:
k
k-1
где величины m и m определены как приведенное значение входного сигнала относительно своего среднего значения соответственно для k-го и (k-1)-го моментов текущего времени равны:
c
Величина Δ есть допустимое значение строба приведенного отклонения входного сигнала, N - значение коэффициента деления.
k
k-1
При проверке условия  (1), являющегося условием отсутствия ошибки, происходит переход на ту или иную ветвь вычислений. Если условие отсутствия ошибки не выполняется, то вычисленное значение m считается неверным и вместо него для формирования текущего сглаженного значения используется предыдущее верное значение m. Такая замена вследствие монотонности исходного сглаженного сигнала не ведет к его искажению. Если после этого на следующем шаге сглаживания условие отсутствия выполняется, то ошибка классифицируется как исправленное аномальное измерение. Невыполнение условия отсутствия ошибки является признаком отказа.
Структурная схема устройства, реализующего рассмотренный алгоритм, содержит первый сумматор, счетчик отсчетов, первый и второй дешифраторы, первый и второй элемент И, элемент ИЛИ, триггер, блок задания коэффициента деления, первый регистр и второй сумматор, второй регистр, третий дешифратор, счетчик аномальных измерений, блок выделения модуля, схема сравнения, третий элемент и генератор тактовых импульсов.
Признаки аналога, совпадающие с признаками заявляемого технического решения, следующие: запоминание цифрового сигнала (в заявляемом устройстве - блок хранения изображения), сравнение с пороговым уровнем (в заявляемом устройстве - блок поиска подобия), восстановление аномальных значений (в заявляемом устройстве - блок заполнения изображения).
Недостатками известного способа и устройства, его реализующего являются:
- процедура обнаружения не эффективна в случае обработки групповых аномальных значений;
- необходимо априорное знание допустимого значения строба Δ.
Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:
- так как данный способ позволяет обнаруживать только одиночные аномальные значения, то эффективность обнаружения групповых аномальных значений будет низкой;
- величина Δ задается в зависимости от класса входных сигналов и области их применения.
Наиболее близким к изобретению является устройство восстановления искаженных значений пикселей изображений [Патент РФ №2580456, МПК G06F 17/17].
Рассматриваемое устройство - прототип, представленное на фиг 1, предполагает:
i,j
1) записываются значения входного изображения S,
i,j
i,j
i,j
i,j
i,j
i,j
2) определяется значение коэффициента доверия С, C=1, если C ∈ S, C=0, если C ∈ n;
i,j
i,j
i,j
i,j
3) вычисляется значение приоритета Р(δS) для каждого значения пикселя границы P(δS)=C(δS)⋅D(δS), где
i,j
4) определяется пиксель p∈(i,j) с максимальным значением приоритета max(Р(δS)) на границе δS;
p
5) определяется квадратная форма области для поиска подобия Ψ с центральным пикселем p∈(i, j);
6) вычисляется евклидова метрика для всех доступных значений пикселей изображения
7) восстанавливаются значения пикселей в области η путем копирования из области, для которой евклидова метрика минимальна;
8) пересчитывается коэффициент доверия С для восстановленных пикселей;
9) процедуры 4-10 повторяются пока не будут восстановлены все значения пикселей из области η, то есть проверяется условие T=0, где Т - количество пикселей границы δS.
Устройство восстановления искаженных значений пикселей изображений содержит: блок хранения изображения, блок хранения пикселей, блок создания словаря, блок хранения словаря, блок обработки, блок вычисления приоритета, блок определения адаптивной формы, блок поиска подобия, блок вычисления СКО, блок анализа, блок заполнения изображения, генератор тактовых импульсов.
Признаки прототипа, совпадающие с признаками заявляемого технического решения, следующие блок хранения изображения, первый вход которого является информационным входом устройства, второй выход которого подключен к входу блока хранения пикселей, выход которого подключен к входу блока создания словаря, выход которого подключен к входу блока хранения словаря, выход которого подключен ко второму входу блока поиска подобия; выход блока обработки подключен к входу блока вычисления приоритета, выход которого подключен к входу блока определения адаптивной формы, выход которого подключен к первому входу блока поиска подобия, выход которого подключен к входу блока вычисления СКО, выход которого подключен к входу блока анализа, выход которого подключен к входу блока заполнения изображений, выход которого подключен ко второму входу блока хранения изображений, первый выход которого является информационным выходом устройства.
Недостатками известного устройства-прототипа являются:
- видимость границ на восстановленном изображении между найденными похожими блоками;
- неправильное восстановление при отсутствии похожего блока;
- зависимость эффективности восстановления от выбора размера блока.
Причины, препятствующие достижению требуемого технического результата, заключаются в следующем:
- отсутствие похожего блока приводит к неправильному восстановлению, так как замена пикселей происходит на пиксели блока, для которого евклидова метрика минимальна, даже в том случае если она имеет большое значение по абсолютной величине;
- выбор размера блока зависит от априорной информации о размере и формы области восстановления и геометрических свойств изображения.
Предлагаемое устройство восстановления папиллярных узоров отпечатка пальца позволяет повысить эффективность распознавания отпечатков пальцев в биометрических системах идентификации человека, путем восстановления поврежденных участков на изображениях отпечатков пальцев. К изображению отпечатка пальца следует применить методы повышения качества изображений с целью четкого выделения папиллярных линий. Для устранения проблемных участков исходных изображений были выбраны такие методы обработки изображений, как пороговое преобразование и морфологическая фильтрация.
Технический результат - реконструкция значений пикселей изображений с целью восстановления папиллярных узоров отпечатка пальца.
Технический результат достигается тем, что в устройство восстановления папиллярных узоров отпечатка пальца, содержащее блок хранения изображения, первый вход которого является информационным входом устройства, второй выход которого подключен к входу блока хранения пикселей, выход которого подключен к входу блока создания словаря, выход которого подключен к входу блока хранения словаря, выход которого подключен ко второму входу блока поиска подобия; выход блока обработки подключен к входу блока вычисления приоритета, выход которого подключен к входу блока определения адаптивной формы, выход которого подключен к первому входу блока поиска подобия, выход которого подключен к входу блока вычисления СКО, выход которого подключен к входу блока анализа, выход которого подключен к входу блока заполнения изображений, выход которого подключен ко второму входу блока хранения изображений, первый выход которого является информационным выходом устройства, третий выход блока хранения изображения подключен к входу блока сегментации, выход которого подключен к входу блока вычисления дисперсии, выход которого подключен к входу блока пороговой обработки, выход которого подключен к входу блока распределения уровней яркости, выход которого подключен к входу блока операции эрозии, выход которого подключен к входу блока операции размыкания, выход которого подключен к входу блока определения дефектов изображения, выход которого подключен к входу блока обработки.
На фиг. 2 представлена схема устройства восстановления папиллярных узоров отпечатка пальца.
Устройство восстановления папиллярных узоров отпечатка пальца содержит блок хранения изображения 1, первый вход которого является информационным входом устройства, второй выход которого подключен к входу блока хранения пикселей 2, выход которого подключен к входу блока создания словаря 3, выход которого подключен к входу блока хранения словаря 4, выход которого подключен ко второму входу блока поиска подобия 15; третий выход блока хранения изображения 1 подключен к входу блока сегментации 5, выход которого подключен к входу блока вычисления дисперсии 6, выход которого подключен к входу блока пороговой обработки 7, выход которого подключен к входу блока распределения уровней яркости 8, выход которого подключен к входу блока операции эрозии 9, выход которого подключен к входу блока операции размыкания 10, выход которого подключен к входу блока определения дефектов изображения 11, выход которого подключен к входу блока обработки 12, выход которого подключен к входу блока вычисления приоритета 13, выход которого подключен к входу блока определения адаптивной формы 14, выход которого подключен к первому входу блока поиска подобия 15, выход которого подключен к входу блока вычисления СКО 16, выход которого подключен к входу блока анализа 17, выход которого подключен к входу блока заполнения изображений 18, выход которого подключен ко второму входу блока хранения изображений, первый выход которого является информационным выходом устройства.
Устройство восстановления папиллярных узоров отпечатка пальца реализуется следующим образом. На вход блока хранения изображения поступает изображение отпечатка пальца с потерянными пикселями. Доступные пиксели сохраняются в блоке хранения пикселей, с помощью которых в блоке создания словаря создаются двумерные матрицы. Данные матрицы используются для заполнения участков изображения с потерянными пикселями. Далее в блоке сегментации происходит этап предобработки, который разбивает изображения на области. Затем в блоке вычисления дисперсии рассчитываются дисперсии областей и сравниваются с заданным пороговым значением. В блоке пороговой обработки происходит перевод изображения в оттенки серого и процедура отделения фона от отпечатка пальца. Следующим шагом в блоке распределения уровней яркости происходит регулировка интервалов значений уровней серого так, чтобы они находились в пределах нужного диапазона значений. После этапа предобработки выполняется поиск поврежденных участков на изображении, для этого используются операции эрозия и размыкания. Далее к найденным поврежденным участкам изображения применяется алгоритм восстановления. Обработка происходит итеративно, до тех пор, пока все пиксели в блоке хранения изображения не будут восстановлены, после чего полученные значения поступают на информационный выход устройства.
1
2
Устройство восстановления папиллярных узоров отпечатка пальца работает следующим образом. На вход блока хранения изображения 1 поступает изображение отпечатка пальца с потерянными пикселями. Доступные пиксели сохраняются в блоке хранения пикселей 2, с помощью которых в блоке создания словаря 3 создаются двумерные матрицы, которые используются далее для восстановления изображения. Матрицы создаются путем формирования квадратных блоков размером 15 на 15 пикселей из исходного изображения путем смещения блока по всем доступным пикселям изображения. Данные матрицы хранятся в блоке хранения словаря 4. В блоке сегментации 5 происходит разбиение изображения на участки. В блоке вычисления дисперсии 6 рассчитываются дисперсии участка и сравниваются с заданным пороговым значением. В блоке пороговой обработки 7 происходит перевод изображения в оттенки серого и отделение фонового изображения от отпечатка пальца. Эта процедура необходима для правильной работы дальнейшего алгоритма нормализации. В блоке распределения уровней яркости 8 происходит регулировка интервалов значений уровней серого так, чтобы они находились в пределах нужного диапазона значений. В блоке операции эрозии 9 удаляются все объекты, меньшие чем структурный элемент, а объекты, соединенные тонкими линиями, становятся разъединенными и размеры всех объектов уменьшаются. В блоке операции размыкания 10 удаляются все объекты, меньшие, чем структурный элемент, что помогает избежать сильного уменьшения размера объектов. Далее выполняется поиск поврежденных участков на изображении в блоке определения дефектов на изображении 11. В блоке обработки 12 происходит формирование граничных пикселей вокруг области с потерянными пикселями из блока хранения изображения 1. Далее информация о граничных пикселях поступает на вход блока вычисления приоритета 13, в котором вычисляется приоритет для всех граничных пикселей, который состоит из двух множителей: коэффициент доверия и коэффициент градиента. В данном блоке так же осуществляется ранжировка приоритета и определение граничного пикселя с максимальным значением приоритета. В блоке определения адаптивной формы 14 вокруг пикселя с максимальным значением приоритета формируется адаптивная область близких по яркости пикселей с помощью способа инверсий. Адаптивная область поступает на вход блока поиска подобия 15, в котором осуществляется вычисление евклидовой метрики со всеми двумерными матрицам, которые хранятся в блоке хранения словаря 4. В блоке поиска подобия 15 так же определяется количество похожих блоков, для которых евклидова метрика не превосходит порогового значения. Данные блоки поступают на вход блока вычисления СКО 16, где вычисляется СКО для данных областей. После чего в блоке анализа 17 происходит проверка условия схожести среднеквадратических отклонений двух участков Ψ и Ψ для всех найденных областях. Выбирается область, для которой выполняется условие (4). Далее в блоке заполнения изображения 18, происходит копирование значений пикселей найденного блока в блок хранения изображения 1 на соответственные координаты. Далее процесс вычисления приоритета с поиском похожих блоков и последующей заменой повторяется до тех пор, пока не будут восстановлены все значения в блоке хранения изображения 1.
Устройство реализуют следующий алгоритм.
Дефекты на изображении отпечатка пальца оказывают значительное влияние на результат работы алгоритмов (фиг. 3), поэтому требуется этап предобработки изображения. Этап предобработки включает в себя перевод изображения в оттенки серого и сегментацию изображения. Сегментацией называют процедуру отделения фонового изображения от интересующего нас рисунка отпечатка пальца. Эта процедура необходима для правильной работы дальнейшего алгоритма нормализации. После этапа предобработки выполняется поиск поврежденных участков на изображении, для этого используются операции эрозия и размыкания. Далее к найденным поврежденным участкам изображения применяется алгоритм восстановления.
Алгоритм сегментации состоит из нескольких этапов. На первом этапе изображение делится на участки размером W×W. В каждом участке вычисляется среднее значение яркости по всему участку в соответствии с (3).
где I(i,j) - значение цвета в пикселе с соответствующими координатами;
M(k) - среднее значение оттенка серого для сегмента k.
Затем вычисляется значение дисперсии для каждого участка. Для участка размером W×W пикселей дисперсия вычисляется как:
где V(k) - значение дисперсии для данного участка k.
Далее происходит сравнение величин V(k) с заданным пороговым значением. Если значение дисперсии меньше, чем заданное пороговое значение, то участок будет считаться фоновой областью, и каждому пикселю в этом участке присваивается значение яркости, соответствующее белому цвету, иначе, считается, что это часть основного изображения, и значения яркости в каждом пикселе участка становятся равными значениям яркости пикселей исходного изображения.
Алгоритм работает следующим образом: определяется количество участков на изображении по горизонтали и вертикали:
где W - ширина изображения,
Segm - размер участка,
Н - высота изображения.
Затем рассчитываются и сохраняются значения границ участка, средней яркости и дисперсии. Рассчитанные дисперсии участка сравниваются с заданным пороговым значением. Если дисперсия меньше порогового значения, то каждый пиксель участка заполняется белым цветом; если больше, то пиксели участка не меняются (фиг. 4).
Следующим шагом является нормализация изображения, необходимая для установления значений интенсивности пикселей изображения способом регулировки интервала значений уровней серого так, чтобы они находились в пределах нужного диапазона значений. Такой способ позволяет равномерно распределить все цвета пикселей изображения в заданном интервале.
Под нормализацией понимается расчет значений средней яркости и дисперсии изображения всего изображения с последующим преобразованием в соответствии с выражением (6):
где М и V - среднее значение яркости и дисперсия для пикселя исходного изображения I(i,j);
0
0
M и V - необходимые средние значение яркости и дисперсии, соответственно.
Нормализация не влияет на структуру папиллярных линий, и сохраняет всю уже имеющуюся в изображении информацию (фиг. 5).
После этапа предобработки выполняется операции эрозия и размыкания (фиг. 6). При выполнении операции эрозии структурный элемент проходит по всем пикселам изображения. Если в некоторой позиции каждый единичный пиксел структурного элемента совпадет с единичным пикселом бинарного изображения, то выполняется логическое сложение центрального пиксела структурного элемента с соответствующим пикселом выходного изображения. В результате применения операции эрозии все объекты, меньшие чем структурный элемент, стираются, объекты, соединенные тонкими линиями, становятся разъединенными и размеры всех объектов уменьшаются. Операция эрозии полезна для удаления малых объектов и различных шумов, но у этой операции есть недостаток - все остающиеся объекты уменьшаются в размере. Этого эффекта можно избежать, если после операции эрозии применить операцию размыкания с тем же структурным элементом. Размыкание отсеивает все объекты, меньшие, чем структурный элемент, но при этом помогает избежать сильного уменьшения размера объектов. Также размыкание идеально подходит для удаления линий, толщина которых меньше, чем диаметр структурного элемента. Также важно помнить, что после этой операции контуры объектов становятся более гладкими.
Далее к найденным поврежденным участкам изображения применяется алгоритм восстановления, который состоит из следующих шагов:
i,j
На первом шаге вычисляется значение приоритета P(δS) для каждого значения пикселя границы, который состоит из двух множителей:
i,j
i,j
i,j
i,j
i,j
i,j
где: δS - текущий пиксель на границе доступных пикселей; C(δS) - коэффициент доверия; D(δS) - коэффициент градиента;  - квадратный блок пикселей с центром в пикселе δS;  - количество пикселей квадратного блока,  вектор, ортогональный градиенту в точке δS;  - вектор, ортогональный границе δS в точке δS; α - нормированный множитель, который для восьми битных изображений равен 255.
i,j
Вначале предполагается, что значение коэффициента доверия С для пикселей из области S,  равно 1, а для области η равно 0.
i,j
i,j
Вычисление приоритета с помощью выражения (3) позволяет придавать больший вес пикселям, которые находятся на перепадах яркости (границах), таким образом, восстанавливая их в первую очередь. Учет коэффициента доверия C(δS) позволяет присваивать меньший вес восстановленным пикселям при увеличении расстояния от доступных пикселей из области S,
i,j
На втором шаге, для пикселя p∈(i,j) с максимальным значением приоритета max(Р(δS)) на границе δS с помощью способа инверсий адаптивно определяется форма области для поиска подобия, что позволяет корректно учитывать форму области восстановления и не захватывать лишние границы, которые могут привести к неправильной реконструкции изображения.
i,j
Для формирования адаптивных областей двумерного сигнала для пикселя p∈(i,j) задаются восемь направлений  в которых определяются интервалы квазистационарности. Условие квазистационарности проверяется с помощью вычисления случайной величины τ, равной сумме числа инверсий значений пикселей в каждом из направлений двумерного сигнала S,  в котором присутствуют доступные пиксели.
Например, сумма числа инверсий для направления 5 равна:
где  - текущее значение пикселя изображения с координатами  - последующие значения пикселей изображения по j-ому столбцу (движение в направлении 5), R - максимальная длина интервала квазистационарности.
Количество сочетаний, для которых вычисляется сумма инверсий, составляет:
Первая альтернатива (убывающий сигнал) принимается, если:
Правило для принятия второй альтернативы (возрастающий сигнал) имеет вид:
где α - значение ошибки первого рода.
Гипотеза о стационарности сигнала принимается, если
По полученным границам интервалов для каждого из восьми секторов, образованных направлениями 1-2, 2-3, 3-4, 5-6, 7-8, 8-1 происходит формирование областей квазистационарности. Для этого используется линейная интерполяция границ смежных интервалов уравнением прямой проходящей через две точки:
1
1
2
2
где (i,j) - координаты границы направления h, (i,j) - координаты границы направления h+1.
Значения пикселей, попавшие между всеми направлениями и интерполирующими прямыми, проходящими через границы интервалов квазистационарности, объединяются в одну область Ω.
p
Для пикселя границы смежного с пикселем p∈(i,j), имеющего большее значение  так же определяется адаптивно область с помощью способа инверсий. Каждая из полученных областей является квазистационарной, и они находятся по разные стороны от перепада яркости. Данные области объединяются в одну, таким образом, определяется область Ψ с адаптивными размерами и перепадом яркости.
i,j
На третьем шаге, находятся блоки  в области доступных пикселей S, для которых евклидова метрика минимальна:
при этом h обозначает порядковые номера подобных блоков, ранжированных по евклидовой метрике.
Количество блоков подобия R определяется с помощью доверительного интервала:
где:  α - уровень значимости.
На этапе выбора блока для замены проверяется дополнительное условие на однородность с помощью вычисления среднеквадратического отклонения (СКО). Доверительный интервал для СКО принимается равным Г=0,9. Таким образом, для каждого найденного похожего блока проверяется следующее условие:
i,j
Значения пикселей в области η смежные к пикселю с максимальным приоритетом p восстанавливаются путем усреднения соответствующих пикселей найденных областей  из области доступных пикселей S:
Коэффициент доверия С для восстановленных пикселей присваивается равным текущему значению С(р). После чего процедура пересчета приоритета и поиска похожих областей с последующей заменой повторяется.
После выполнения вышеописанного алгоритма на выход устройства подается восстановленное изображение отпечатка пальца (фиг. 7).
Предлагаемое устройство восстановления папиллярных узоров отпечатка пальца позволяет устранять часть искажений, вызванных упругими деформациями, на этапе регистрации и сканирования отпечатков пальцев, что приводит к увеличению точности идентификации. Предлагаемое изобретение, позволяет увеличить эффективность распознавания в сравнении с известными подходами.