Устройство для реконструкции изображений на основе хэш-функций

Устройство для реконструкции изображений на основе хэш-функций

Иллюстрации

Показать все

Реферат

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

Упрощенная математическая модель изображения (фиг.1) может быть представлена в виде:

Y i,j =(1− M i,j )⋅ S i,j + M i,j ⋅ R i,j , i= 1,I ¯ , j= 1,J ¯ ,

где Y_i,j – исходное изображение, S_i,j – оригинальное (неискаженное) изображение, M i,j – бинарная маска области с искаженными значениями (1 – соответствует искаженным пикселям, 0 – соответствует не искаженным пикселям), R i,j – искаженные значения пикселей.

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

Упрощенно способы реконструкции значений пикселей изображений можно разделить на следующие группы:

1) Способы на основе решения дифференциальных уравнений в частных производных.

2) Способы на основе ортогональных преобразований.

3) Способы на основе синтеза текстур.

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

Известно цифровое сглаживающее устройство [Патент RU № 2010325, МПК G 06 F 15/353, опубл. 06.02.1991]. Данное устройство может быть использовано при обработке изображений, при этом потерянные пиксели принимаются за аномальные. Устройство содержит первый сумматор, счетчик отсчетов, первый и второй дешифраторы, первый и второй элементы И, элемент ИЛИ, триггер, блок задания коэффициента деления, первый регистр и второй сумматор, второй регистр, третий дешифратор, счетчик аномальных измерений, блок выделения модуля, схему сравнения, третий элемент и генератор тактовых импульсов.

Недостатками известного устройства являются:

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

- необходимо априорное знание допустимого значения строба Δ.

Известно устройство по способу восстановления изображений на основе заполнения похожими областями и устройство, его реализующее (Image region filling by exemplar-based inpainting) [Patent USA № 11/095,138, № 10/453,404].

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

Недостатками известного устройства являются:

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

– неправильное восстановление при отсутствии похожего блока;

– зависимость эффективности восстановления от выбора размера блока.

Наиболее близким к изобретению является устройство для восстановления изображений [Патент RU № 2450342, МПК G06F 17/17, опубл. 10.05.2012]. Устройство для восстановления изображений содержит блок хранения изображения, блок хранения пикселей, блок поворота, блок создания словаря, блок хранения словаря, блок обработки, блок вычисления приоритета, блок поворота, блок определения адаптивной формы, блок поиска подобия, блок усреднения пикселей, блок заполнения изображения, генератор тактовых импульсов.

Недостатками известного устройства-прототипа являются:

– неправильное восстановление при отсутствии похожего блока;

– зависимость эффективности восстановления от структуры изображения.

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

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

Устройство реализует следующий алгоритм. На первом шаге вычисляется значение приоритета P(δ S i,j ) для каждого значения пикселя границы, который состоит из двух множителей:

P(δ S i,j )=С(δ S i,j )⋅D(δ S i,j ) , i= 1,N ¯ ,j= 1,M ¯

C(δ S i,j )= ∑ l∈ Ψ δ S i,j C(l) | Ψ δ S i,j | , D(δ S i,j )= | ∇ I δ S i,j ⊥ ⋅ n δ S i,j | α , i= 1,N ¯ ,j= 1,M ¯

где: δ S i,j - текущий пиксель на границе доступных пикселей; С(δ S i,j ) - коэффициент доверия; D(δ S i,j )- коэффициент градиента; Ψ δ S i,j - квадратный блок пикселей с центром в пикселе δ S i,j ; | Ψ δ S i,j | - количество пикселей квадратного блока, ∇ I δ S i,j ⊥ вектор, ортогональный градиенту в точке δ S i,j ; n δ S i,j - вектор, ортогональный границе δS в точке δ S i,j ; α- нормированный множитель, который для восьми битных изображений равен 255.

Вначале предполагается, что значение коэффициента доверия С для пикселей из области S i,j , i= 1,N ¯ ,j= 1,M ¯ равно 1, а для области η равно 0.

Вычисление приоритета позволяет придавать больший вес пикселям, которые находятся на перепадах яркости (границах), таким образом, восстанавливая их в первую очередь. Учет коэффициента доверия C(δ S i,j ) позволяет присваивать меньший вес восстановленным пикселям при увеличении расстояния от доступных пикселей из области S i,j , i= 1,N ¯ ,j= 1,M ¯ .

На втором шаге, для пикселя p∈(i,j) с максимальным значением приоритета max(P(δ S i,j )) на границе δS с помощью способа инверсий адаптивно определяется форма области для поиска подобия, что позволяет корректно учитывать форму области восстановления и не захватывать лишние границы, которые могут привести к неправильной реконструкции изображения.

Для формирования адаптивных областей двумерного сигнала для пикселя p∈(i,j) задаются восемь направлений h= 1,8 ¯ , в которых определяются интервалы квазистационарности. Условие квазистационарности проверяется с помощью вычисления случайной величины τ, равной сумме числа инверсий значений пикселей в каждом из направлений двумерного сигнала S i,j , i= 1,N ¯ ,j= 1,M ¯ , в котором присутствуют доступные пиксели.

Например, сумма числа инверсий для направления 5 равна:

τ d = ∑ l=0 d−1 ∑ k=l+1 d u( S i+l,j , S i+k,j ) , d= 1,R ¯ ,

u( S i+l,j , S i+k,j )={ 1,   S i+l,j > S i+k,j , 0,   S i+l,j ≤ S i+k,j . ,

где S i+l,j , l=0...d−1- текущее значение пикселя изображения с координатами ( i+l,j); S i+k,j , k=l+1...d - последующие значения пикселей изображения по j-му столбцу (движение в направлении 5), R - максимальная длина интервала квазистационарности.

Количество сочетаний, для которых вычисляется сумма инверсий, составляет:

X= d⋅(d−1) 2 .

Первая альтернатива (убывающий сигнал) принимается, если τ d > c 1 = τ α 2 ⋅ X +X/2 −0,5.

Правило для принятия второй альтернативы (возрастающий сигнал) имеет вид τ d < c 2 = τ 1−α 2 ⋅ X +X/2 −0,5,

где α – значение ошибки первого рода.

Гипотеза о стационарности сигнала принимается, если

c 2 ≤ τ d ≤ c 1 ,

По полученным границам интервалов для каждого из восьми секторов, образованных направлениями 1-2, 2-3, 3-4, 5-6, 7-8, 8-1, происходит формирование областей квазистационарности. Для этого используется линейная интерполяция границ смежных интервалов уравнением прямой, проходящей через две точки:

j− j 1 j 2 − j 1 = i− i 1 i 2 − i 1 ,

i= i 2 − i 1 j 2 − j 1 ⋅j+ i 1 ⋅ j 2 − i 2 ⋅ j 1 j 2 − j 1 ,

где ( i 1 , j 1 ) - координаты границы направления h, ( i 2 , j 2 ) - координаты границы направления h+1.

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

Для пикселя границы, смежного с пикселем p∈(i,j), имеющего большее значение ∇ I δ S i,j , также определяется адаптивно область с помощью способа инверсий. Каждая из полученных областей является квазистационарной, и они находятся по разные стороны от перепада яркости. Данные области объединяются в одну, таким образом, определяется область Ψ p с адаптивными размерами и перепадом яркости.

Определяется пиксель p∈(i,j) с максимальным значением приоритета max(P(δ S i,j )) на границе δS и выбирается адаптивная область Ψ p , принадлежащая данному пикселю, использование которой позволяет корректно учитывать форму области восстановления и не захватывать лишние границы, которые могут привести к неправильной реконструкции изображения. Далее количество блоков, полученных из исходного изображения с доступными пикселями, увеличивается путем их поворота на 90, 180, 270 градусов. Данный подход позволяет уменьшить погрешность восстановления изображения за счет увеличения количества блоков и увеличения вероятности нахождения более похожего блока.

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

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

Значения пикселей в области η, смежные к пикселю с максимальным приоритетом p, восстанавливаются путем усреднения соответствующих пикселей найденных областей ψ q (h) из области доступных пикселей S i,j :

S ¯ = ∑ h=1 R ψ q (h) R .

Коэффициент доверия С для восстановленных пикселей присваивается равным текущему значению C(p). После чего процедура пересчета приоритета и поиска похожих областей с последующей заменой повторяется.

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

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

На фиг. 1 представлена математическая модель изображения.

На фиг. 2 представлена блок-схема устройства для реконструкции изображений на основе хэш-функций.

Устройство для реконструкции изображений на основе хэш-функций содержит блок хранения изображения 1, первый вход которого является информационным входом устройства, второй выход которого подключен к входу блока хранения пикселей 2, выход которого подключен к входу блока поворота 3, выход которого подключен к входу первого блока преобразования изображения в градации серого 4, выход которого подключен к входу первого блока вычисления среднего значения 5, выход которого подключен к входу первого блока получения двоичного изображения 6, выход которого подключен к входу первого блока вычисления хеш-функции 7, выход которого подключен к входу блока создания словаря 8, выход которого подключен к входу блока хранения словаря 9, выход которого подключен к второму входу блока поиска подобия 17; третий выход блока хранения изображения 1 подключен к входу блока обработки 10, выход которого подключен к входу блока вычисления приоритета 11, выход которого подключен к входу блока определения адаптивной формы 12, выход которого подключен к входу второго блока преобразования изображения в градации серого 13, выход которого подключен к входу второго блока вычисления среднего значения 14, выход которого подключен к входу второго блока получения двоичного изображения 15, выход которого подключен к входу второго блока вычисления хеш-функции 16, выход которого подключен к первому входу блока поиска подобия 17, выход которого подключен к входу блока усреднения пикселей 18, выход которого подключен к входу блока заполнения изображения 19, выход которого подключен к второму входу блока хранения изображения 1, первый выход которого является информационным выходом устройства; синхронность работы устройства обеспечивается генератором тактовых импульсов 20.

Устройство для реконструкции изображений на основе хэш-функций работает следующим образом. На вход блока хранения изображения 1 поступает изображение с потерянными пикселями. Доступные пиксели сохраняются в блоке хранения пикселей 2, далее они поворачиваются на 90, 180, 270 градусов в блоке поворота 3, преобразуются в первом блоке преобразования в градации серого 4 и поступают на вход первого блока вычисления среднего значения 5, далее данные поступают на вход первого блока получения двоичного изображения 6, далее происходит вычисление хеш-функций в первом блоке вычисления хеш-функций 7. Такой подход позволяет получить структуру, которая содержит хеш-функции всех блоков изображения. Значения пикселей блоков и соответственные им хэш-функции, которые вычислены для всех блоков с учётом поворота изображения, формируются в блоке создания словаря 8. Результат формирования словаря сохраняется в блоке хранения словаря 9. В блоке обработки 10 происходит формирование граничных пикселей вокруг области с потерянными пикселями из блока хранения изображения 1. Далее информация о граничных пикселях поступает на вход блока вычисления приоритета 11, в котором вычисляется приоритет для всех граничных пикселей, который состоит из двух множителей: коэффициент доверия и коэффициент градиента. В данном блоке также осуществляется ранжировка приоритета и определение граничного пикселя с максимальным значением приоритета. В блоке определения адаптивной формы 12 вокруг пикселя с максимальным значением приоритета формируется адаптивная область близких по яркости пикселей с помощью способа инверсий. Адаптивная область поступает на вход второго блока преобразования изображения в градации серого 13, выход которого подключен к входу второго блока вычисления среднего значения 14, далее происходит преобразование во втором блоке получения двоичного изображения 15, выход которого подключен к входу второго блока вычисления хеш-функции 16. То есть в блоке 16 вычисляется значения хэш-функции для восстанавливаемого блока. Далее в блоке поиска подобия 17 для восстанавливаемого блока и каждого блока из хеш-таблицы из блока хранения словаря 9 вычисляется количество различных бит, то есть расстояние Хэмминга. Далее определяются блоки, для которых расстояние Хэмминга минимально. Данные блоки поступают на вход блока усреднения пикселей 18, в котором происходит формирование усредненной оценки. Полученная оценка поступает в блок заполнения изображения 19, в котором копируются значения пикселей, смежных к пикселю с максимальным приоритетом из усредненной оценки, в блок хранения изображения 1 на соответственные координаты. Далее процесс вычисления приоритета с поиском похожих блоков и последующей заменой повторяется до тех пор, пока не будут восстановлены все значения в блоке хранения изображения 1. Синхронность работы устройства обеспечивается генератором тактовых импульсов 20.

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