УСТРОЙСТВО РЕДАКТИРОВАНИЯ ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЕЙ

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

Упрощенная математическая модель изображения представляет собой двумерный дискретный сигнал S_{i, j}, , , (фиг. 1), где S_{i, j} - доступные пиксели неискаженного изображения, η_{i, j} - область изображения с отсутствующими пикселями, δS - граница области S.

Основная решаемая задача - восстановления значений пикселей кадров видеопоследовательностей.

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

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

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

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

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

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

Известен способ восстановления текстуры и структуры изображений [Bertalmio М., Vese L., Sapiro G., Osher S. Simultaneous texture and structure image inpainting // Proceedings of the International Conference on Computer Vision and Pattern Recognition, 2003. - P. 707-712], который позволяет экстраполировать значения пикселей изображений, как в структуре, так и текстуре изображений, при этом каждая составляющая представляется разряженно значимыми коэффициентами спектрального преобразования. Данный способ основан на декомпозиции изображения, называемого также морфологическим компонентным анализом, разделяющего изображение на линейную комбинацию текстуры и структуры изображения. Для восстановления текстуры используется курвет-преобразование, а для структуры - дискретное косинусное преобразование.

Изображение представляется в виде суммы:

S=G_sD_s+G_tD_t,

где G - матрица ортогонального преобразования изображения, D - матрица значимых коэффициентов, s - структура изображения, t - текстура изображения.

При этом выражение целевой функции для определения значимых коэффициентов запишется в виде:

где М - маска области с потерянными пикселями, γ, λ - параметры способа, TV - total variation (корректировка с помощью модели общего отклонения), R - остаток, который на первой итерации равен случайному числу.

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

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

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

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

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

На первом шаге вычисляется приоритет Р(р) для каждого пикселя границы, который состоит из двух множителей:

где р - текущий пиксель на границе доступных пикселей;

С(р) - данные доверия;

D(p) - данные градиента;

|Ψ_p| - количество пикселей квадратного блока с центром в пикселе р;

- вектор, ортогональный градиенту в точке р;

n_p - вектор, ортогональный границе δS в точке р;

α - нормированный множитель для черно-белых изображений равен 255.

Вначале предполагается, что значение данных доверия С для пикселей из области S равно 1, а для области равно 0.

Вычисление приоритета с помощью выражения (1) позволяет придать больший вес пикселям, находящимся на перепадах яркости (границах), таким образом, восстанавливая их в первую очередь. Учет данных доверия С(р) позволяет присваивать меньший вес восстановленным пикселям при увеличении дистанции от доступных пикселей из области S.

На втором шаге находится блок ψ_q в области доступных пикселей S, для которого евклидова норма минимальна:

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

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

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

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

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

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

Известен способ и система выделения данных об изображении объекта переднего плана на основе данных о цвете и глубине [Патент №2426172, МПК G06K 9/34]. Изобретение относится к области распознавания и сегментации изображений, и в частности к способу и системе для выделения целевого объекта из фонового изображения и изображения объекта путем создания маски, используемой для выделения целевого объекта. Техническим результатом является создание усовершенствованного способа выделения данных об изображении объекта, используя данные о глубине изображения. Указанный технический результат достигается тем, что создается скалярное изображение разности изображения объекта и фона на основе разности освещенности, а в областях, где разность освещенности ниже заранее установленного порогового значения, на основе разности цвета; инициализируется маска по результатам, полученным из предыдущего видеокадра, где скалярное изображение разности меньше заранее установленного порога, если эти результаты доступны, при этом маску объекта заполняют нулями и единицами, где единица означает, что соответствующий пиксель принадлежит объекту, и нуль в ином случае; кластеризуется скалярное изображение разности и данные по глубине на основе нескольких кластеров; создается маска для каждого положения пикселя видеокадра, используя центры тяжести кластеров скалярной разности и данные по глубине для текущего положения пикселя; компенсируется изменение фона сцены во времени путем обновления изображения фона на основе использования созданной маски и изображения разности.

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

Недостатками известного способа и системы являются:

использование двух видеокамер приводит к большим вычислительным затратам при получении альфа-канала выделяемого объекта.

Известен способ выделения объекта на изображении на основе решения уравнений Пуассона (Poisson matting for images) [Patent USA №7636128]. Способ основан на решении системы уравнений Пуассона с граничными условиями для изображения, сегментированного на три области: передний план, фон, неизвестная область, разделяющая передний план и фон. Для нахождения альфа-канала решают уравнение Пуассона вида:

с граничным условием Дирихле

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

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

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

Наиболее близким к изобретению является устройство обработки двумерных сигналов при реконструкции изображений [Пат. №2440614, Российская Федерация, C1, МПК G06F 17/17. 2010132434/08; заявл. 02.08.2010; опубл. 20.01.2012, бюл. №2]. Рассматриваемое устройство-прототип предполагает:

1) записываются значения входного изображения S_{i, j}, , ;

2) определяется значение коэффициента доверия С, C_{i, j}=1, если C_{i, j}∈S_{i, j}, C_{i, j}=0, если C_{i, j}∈η_{i, j};

3) вычисляется значение приоритета P(δS_{i, j}) для каждого значения пикселя границы P(δS_{i, j})=C(δS_{i, j})·D(δS_{i, j}), где

4) определяется пиксель p∈(i, j) с максимальным значением приоритета max(Р(δS_{i, j})) на границе δS;

5) определяется квадратная форма области для поиска подобия с центральным пикселем р∈(i, j);

6) вычисляется евклидова метрика для всех доступных значений пикселей изображения , q∈i, j, , ;

7) восстанавливаются значения пикселей в области η путем копирования из области, для которой евклидова метрика минимальна;

8) пересчитывается коэффициент доверия С для восстановленных пикселей;

9) процедуры 4-10 повторяются, пока не будут восстановлены все значения пикселей из области η, то есть проверяется условие Т=0, где Т - количество пикселей границы δS.

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

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

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

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

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

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

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

- на изображении при поиске похожих блоков не учитывается их ориентация.

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

При невыполнении данного условия пользователю предлагается расставить метки повторно. Метки, установленные пользователем и найденные в автоматическом режиме необходимы для создания бинарной маски , на которой единичными значениями помечены пиксели, относящиеся к объекту, а нулевыми - к фону. Создание бинарной маски осуществляется с помощью способа, предложенного в патенте [Устройство выделения контуров объектов на текстурированном фоне при обработке цифровых изображений, №2522044]. Суть данного метода заключается в следующем. На первом шаге исходное изображение , на котором представлен некоторый объект на произвольном фоне, двумерный массив H_{i, j}, содержащий маркеры фона и выделяемого объекта, двумерный массив V_{i, j}, содержащий маркеры только выделяемого объекта, децимируются на 2. На втором шаге для изображения mI_{i, j} с уменьшенным разрешением и двумерного массива mM_{i, j} с уменьшенной размерностью строится разреженная матрица Лапласа L размерностью М×М:

где Σ_f - ковариационная матрица 3×3, µ_f - вектор 3×1 средних цветов в окне w_f и I₃ - идентичная матрица 3×3.

На третьем шаге для двумерного массива H_{i/2, j/2} с уменьшенной размерностью строится диагональная матрица D_{i/2, j/2}, диагональные элементы которой равны единице для маркированных пикселей и равны 0 для всех остальных. На четвертом шаге из двумерного массива mV_{i/2, j/2} формируется вектор-столбец b размерностью 1, , с поэлементным возведением в квадрат. Полученный вектор-столбец b и диагональная матрица D_{i/2, j/2} умножаются на константу λ. На пятом шаге формируется разреженная матрица K_{i/2, j/2}:

K_{i/2, j/2}=(L+λD)

Для полученной разреженной матрицы K_{i/2, j/2} находят обратную матрицу . На шестом шаге формируется альфа-канал для изображения с уменьшенным размером:

α^*=K^-1·λb.

Далее с помощью исходного изображения I_{i, j}, уменьшенного изображения mI_{i/2, j/2} альфа-канал α^* интерполируется в 2 раза на основе линейных коэффициентов по формуле

где с - канал цвета, , .

После чего альфа-канал α бинаризуется, образуя маску . Далее по полученной маске , на кадре , алгоритмом восстановления изображений происходит удаление отмеченного объекта. Данный алгоритм реализован в устройстве [«Устройство для восстановления изображений», Пат. №2450342, Российская Федерация, С1, МПК G06F 17/17, 2011132449/08; заявл. 01.08.2011; опубл. 10.05.2012, бюл. №13]. Суть данного алгоритма заключается в следующем. На первом этапе загружается изображение с потерянными пикселями, а также изображение с маской. После чего создаются двумерные матрицы. Данные матрицы используются для заполнения участков изображения с потерянными пикселями. Заполнение происходит для пикселей, смежных к пикселю, для которого приоритет оказывается максимальным. Вычисление значения приоритета Р(δS_{i, j}) для каждого значения пикселя границы состоит из двух множителей (фиг. 2):

где: δS_{i, j} - текущий пиксель на границе доступных пикселей; C(δS_{i, j}) - коэффициент доверия; D(δS_{i, j}) - коэффициент градиента; - квадратный блок пикселей с центром в пикселе δS_{i, j}; - количество пикселей квадратного блока, - вектор, ортогональный градиенту в точке δS_{i, j}; - вектор, ортогональный границе δS в точке δS_{i, j}; α - нормированный множитель, который для восьмибитных изображений равен 255.

Вначале предполагается, что значение коэффициента доверия С для пикселей из области I_{i, j} равно 1, а для области η равно 0. Вычисление приоритета позволяет придавать больший вес пикселям, которые находятся на перепадах яркости (границах), таким образом, восстанавливая их в первую очередь. Учет коэффициента доверия C(δS_{i, j}) позволяет присваивать меньший вес восстановленным пикселям при увеличении расстояния от доступных пикселей из области I_{i, j}, , . Далее происходит поиск блока ψ_p с максимальным приоритетом .

На следующем шаге находится блок Ψ_q в области доступных пикселей I_{i, j}, для которого евклидова норма минимальна (фиг. 3):

Значения пикселей из найденного блока копируются в области . Данные доверия С для восстановленных пикселей присваиваются равным текущему значению С(р) с ограничением Ψ_p, что ∀p∈ψ_p∩S. Процедура пересчета приоритета и поиска похожих областей с последующей заменой повторяется. После того как объект был удален, текущий кадр и все последующие кадры формируются в видеопоследовательность.

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

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

Устройство редактирования видеопоследовательностей работает следующим образом. На вход блока хранения кадров 1 поступает видеопоследовательность, где она разбивается на кадры. После чего кадры через блок задержки 8 поступают на вход блока поиска меток 7. Далее пользователь помечает на кадре объект и фон в блоке установки меток пользователем 2. В блоке 4 выделения объекта по найденным меткам с помощью алгоритма альфа-канала происходит выделение объекта по меткам пользователя. Найденная маска сохраняется в блоке хранения маски 5 и далее поступает на вход блока выбора меток случайным образом 6 и на вход блока хранения данных 9. В блоке выбора меток случайным образом 6 на найденной маске расставляются метки случайным образом и подаются в блок поиска меток 7. В блоке поиска меток 7 происходит поиск похожих меток на следующем кадре. После чего кадр подается в блок управления 3, в котором проверяется условие поиска меток. Метка считается найденной, если евклидова метрика для каждой из найденных меток не превышает пороговое значение. При невыполнении данного условия пользователю предлагается расставить метки повторно. На вход блока хранения данных 9 поступает маска с потерянными пикселями. Доступные пиксели сохраняются в блоке хранения пикселей 10, с помощью которых в блоке создания словаря 11 создаются двумерные матрицы, которые используются далее для восстановления изображения. Матрицы создаются путем формирования квадратных блоков размером 15 на 15 пикселей из исходного изображения путем смещения блока по всем доступным пикселям изображения. Данные матрицы хранятся в блоке хранения словаря 12. В блоке обработки 13 происходит формирование граничных пикселей вокруг области с потерянными пикселями из блока хранения данных 9. Далее информация о граничных пикселях поступает на вход блока вычисления приоритета 14, в котором вычисляется приоритет для всех граничных пикселей, который состоит из двух множителей: коэффициент доверия и коэффициент градиента. В данном блоке также осуществляется ранжировка приоритета и определение граничного пикселя с максимальным значением приоритета. Область поступает на вход блока поиска подобия 15, в котором осуществляется вычисление евклидовой метрики со всеми двумерными матрицам, которые хранятся в блоке хранения словаря 13. В блоке поиска подобия 15 также определяется количество похожих блоков, для которых евклидова метрика не превосходит порогового значения. Далее эти блоки поступают в блок заполнения изображения 16, в котором копируются значения пикселей, смежных к пикселю с максимальным приоритетом в блок хранения данных 9 на соответственные координаты. Далее процесс вычисления приоритета с поиском похожих блоков и последующей заменой повторяется до тех пор, пока не будут восстановлены все значения в блоке хранения данных 9. Синхронность работы устройства обеспечивается генератором тактовых импульсов 17.

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