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

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

 

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

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

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

где Yi,j – исходное изображение, Si,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 d1 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...d1- текущее значение пикселя изображения с координатами ( i+l,j); S i+k,j , k=l+1...d - последующие значения пикселей изображения по j-му столбцу (движение в направлении 5), R - максимальная длина интервала квазистационарности.

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

X= d(d1) 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.

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



 

Похожие патенты:

Изобретение относится к средствам проверки подлинности защитных знаков. Технический результат заключается в повышении точности.

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

Изобретение относится к вычислительному устройству. Технический результат заключается в обеспечении защиты от атак компьютерных систем по сторонним каналам.

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

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

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

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

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

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

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

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

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

Изобретение относится к области вычислительной техники, в частности к цифровой обработке сигналов. Техническим результатом является сокращение времени обработки.

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

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

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

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

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

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

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

Изобретение относится к автоматике и вычислительной технике. Техническим результатом является повышение точности интерполяции. Цифровой линейный интерполятор содержит регистры координатных приращений, сумматор, блоки совпадений, блоки анализа разности координатных приращений, блок анализа знака оценочной функции, регистр разности координатных приращений, при этом двоичная разрядность всех блоков увеличена на один путем добавления младшего (n+1)-го разряда. 1 ил.
Наверх