Содержание к диссертации
Введение
Глава 1 . Подходы к обеспечению безопасности видеоинформации 15
1.1 Алгоритм сжатия видеоинформации 20
1.2 Понятие качества изображения ,.26
1.3 Алгоритм шифрования опорных кадров 28
1.4 Алгоритм шифрования видеоинформации 31
1.5 Алгоритм чистых перестановок 33
1.6 Шифрование с помощью множественных таблиц Хаффмана 33
1.7 Алгоритм изменения порядка следования коэффициентов в матрице..34
1.8 Метод перестановок, трансформации и шифрования в частотной области .36
Постановка задачи исследования 38
Глава 2. Схема алгоритма перестановок 42
2.1 Структурная схема сжатия видеоинформации 43
2.2 Состав алгоритма перестановок 44
2.3 Понятие таблицы перестановок 45
2.4 Перестановка текста по таблице 46
2.5 Понятие блока изображения 47
2.6 Свойства таблицы перестановок 48
2.7 Использование секретного ключа для формирования таблицы перестановок 50
2.8 Безопасные методы получения псевдослучайных данных 51
2.9 Предварительная оценка стойкости 53
Выводы по главе 2 54
Глава 3. Перестановка блоков перед сжатием и её влияние на эффективность сжатия 55
3.1 Перестановка неподвижных изображений формата JPEG 56
3.2 Перестановка блоками кадров видео
3.2.1 Понятие качества сжатия видеоинформации на основе метрики PSNR 58
3.2.2 Понятие битрейта видеоинформации 58
3.3 Результаты сжатия видеоинформации с низкой межкадровой корреляцией после перестановки 59
3.4 Типы кодеков, использованных в сравнении и их результаты 62
3.5 Результаты сжатия видеоинформации с высокой межкадровой корреляцией после перестановки 63
3.6 Объяснение влияния субдискретизации 64
3.7 Перестановка в ближайшей окрестности и её влияние на эффективность сжатия 65
Выводы по главе 3 67
Глава 4. Перестановка блоков в процессе сжатия и её влияние на эффективность сжатия 68
4.1 Выбор блока изображения 68
4.2 Операции над блоками данных в процессе сжатия видеоинформации 68
4.3 Обработка блоков данных в кадрах различных типов 69
4.4 Структура данных перед сжатием статистическими кодами 70
4.5 Оценка влияния перестановки блоков изображения на сжатие статистическими кодами 71
4.6 Оценка деградации качества изображения при перестановке блоков по всему кадру и просмотре без ключа 72
4.7 Оценка деградации качества изображения при перестановке блоков в ближайшей окрестности и просмотре без ключа 4.8 Оценка деградации качества изображения при перестановке блоков с различными ограничениями и просмотре без ключа 76
4.9 Проверка влияния перестановки блоков на степень сжатия видеоинформации при заданном качестве 78
Выводы по главе 4 80
Глава 5. Восстановление данных обратной перестановкой при неизвестной таблице перестановок 82
5.1 Оценка эффективности перестановок блоков как механизма защиты видеоконтента 82
5.2 Определение «натуральности» изображения 83
5.3 Использование алгоритмов сжатия информации для определения корректности перестановки 83
5.4 Анализ границы смежных блоков для определения корректности перестановки 85
5.5 История головоломок-мозаик и их математическое изучение 86
5.6 Типы задач с точки зрения теории алгоритмов 87
5.7 Функция оптимизации для задачи поиска обратной таблицы перестановок 88
5.8 Использование ЭВМ для решения головоломок-мозаик 89
5.9 Наиболее успешные методы решения задачи 5.9.1 Задачами линейного/целочисленного программирования 92
5.9.2 Генетический алгоритм 92
5.9.3 Алгоритм имитации отжига 93
5.9.4 Алгоритм поиска табу 94
5.9.5 Метод удовлетворения ограничений 5.10 Оценка времени, которое может потребоваться для восстановления мозаики методом удовлетворения ограничений 96
5.11 Анализ информации, доступной после перестановки в процессе сжатия... 98
5.12 Подробная структура опорных кадров 98
5.13 Соотношение между предсказанными и независимыми макроблоками 100 5.14 Алгоритм восстановления мозаики в условиях отсутствия части
блоков , 101
5.15 Ограничения алгоритма 102
5.16 Восстановление таблицы перестановок по её части 102
5.16.1 Методы формирования яаблицы перестановок к иценка аи
стойкости 102
Выводы по главе 5 104
Глава б. Алгоритм блочного 64-битового шифра Video-64u. 106
6.1 Оценка статистических свойств 109
6.2 Анализ стойкости шифра к дифференциальному криптоанализу ПО
6.3 Сопоставление с известными алгоритмами 112
Выводы по главе 6 113
Заключение 114
Литература 117
- Алгоритм чистых перестановок
- Понятие блока изображения
- Результаты сжатия видеоинформации с низкой межкадровой корреляцией после перестановки
- Обработка блоков данных в кадрах различных типов
Введение к работе
Актуальность. С широким распространением цифрового медиаконтента, остро встал вопрос его защиты от хищения, искажения и незаконного использования. Повсеместное использование высокоскоростного Интернета, локальных вычислительных сетей, беспроводных сетевых технологий делает данную проблему ещё более актуальной [1]. Видеоконференции, видеосвязь, видеонаблюдение, цифровое наземное, кабельное и спутниковое ТВ - вот далеко неполный перечень актуальных приложений, которые не могут быть конфиденциальны без применения в том или ином виде защиты в связи с тем, что большинство такого рода приложений использует сети общего назначения (например, Интернет или радиоканал в случае эфирного цифрового телевидения) для передачи данных. Соблюдение авторских прав также является одной из задач конфиденциальности передачи видеоинформации. Так например, один из телеканалов приобрел права на показ телефильма на территории нашей страны. Однако на сопредельной стороне также можно принимать передачи этого канала. Обеспечение конфиденциальности при передаче и приёме видеоинформации может решить такие проблемы. Необходимость достаточно надёжного закрытия данных диктуется и всё более производительными ПК, которые доступны злоумышленникам. Хакеры объединяют свои ПК в вычислительные кластеры, которые обладают большими возможностями по раскрытию конфиденциальной информации. Методы, считавшиеся достаточно надежными несколько лет назад, теперь не выдерживают простых атак с помощью перебора ключа. С другой стороны, многие методы закрытия видеоинформации, которые не могли быть применены ещё относительно недавно по причине отсутствия элементной базы, сегодня вполне возможны и применимы.
Особо нужно сказать об актуальности применении шифрования видеоинформации в военной технике. По сообщению газеты «The Wall Street Journal», противостоящие силам НАТО в Ираке и Афганистане боевики использовали простую программу SkyGrabber для перехвата видеоинформации разведывательно-ударных беспилотных летательных аппаратов (БПЛА) MQ-1 Predator. Реализация шифрования данных на этапе разработки в этих БПЛА была свёрнута из-за сложностей шифрования видео в реальном времени (разработка велась в конце 80-х — начале 90-х годов, на тот момент отсутствовала элементная база для обеспечения шифрования таких потоков данных в малогабаритном варианте с приемлемым энергопотреблением). А на текущий момент доработка затруднена в связи с внесением изменений в большой парк уже выпущенных изделий и опасениями за их совместимость с существующими системами управления и связи. Отдельное беспокойство вызывает возможное нарушение функций дистанционного управления БПЛА из-за увеличения времени на доставку данных оператору, который осуществляет управление.
Ещё одной проблемой является объём передаваемой информации. При использовании цифровой видеосвязи общая задержка в канале связи не должна превышать 150 мс, причём это суммарная задержка, которая учитывает не только шифрование/дешифрование конфиденциальных данных, но и сжатие — передачу — приём — разжатие — отображение. И чем меньшие накладные расходы вносит шифрование/дешифрование, тем лучше. Таким образом, успешное решение задачи закрытия видеоинформации возможно с учётом целого комплекса проблем [2], в том числе и в смежных областях (энергопотребление, связь, элементная база и т.д.).
Дополнительный аспект, связанный с исследованиями в этой области, заключается в доступности исходных текстов различных видеокодеков, разработанных в рамках свободного программного обеспечения (СПО). Внеся небольшие изменения в разработанный видеокодек мы имеем возможность быстро проверить различные подходы к обеспечению безопасности информации, не разрабатывая сами кодеки с «нуля», так как их разработка ведётся обычно несколько лет.
С точки зрения безопасности, необходимо также иметь возможность оценить экономический аспект введения защитных механизмов [3]. Не любая информация нуждается в высокой степени защиты, для каждой необходимо подобрать свой уровень конфиденциальности.
Актуальность темы диссертационного исследования заключается в том, что она связана с разработкой подходов к решению задачи создания скоростных методов защиты видеоинформации с заданной стойкостью и простой программной, микропрограммной и/или аппаратной реализацией.
Целью диссертационной работы является снижение затрат на реализацию защищенных систем передачи видеоинформации.
Объектом исследования диссертационного исследования являются
системы обработки видеоинформации.
Предметом исследования являются алгоритмы сжатия и методы защиты видеоинформации, включая механизмы криптографического преобразования данных.
Исследовательские задачи, решаемые в работе, включают:
изучение методов сжатия и шифрования видеоинформации;
анализ и оценку возможности перестановки исходной видеоинформации до её сжатия;
определение элементов перестановки;
разработку алгоритма получения таблицы перестановок;
разработку ПСЧ-генератора, работающего по секретному ключу;
сравнительный анализ производительности, необходимой при шифровании всей видеоинформации и выборочным шифрованием по предложенному методу;
разработка алгоритмов шифрования видеопотока, ориентированных на обеспечение стойкости достаточной для коммерческого использования и использование в устройствах с низкой производительностью центрального процессора, а также снижение временных затрат на доступ к защищённому видеопотоку.
Используемые методы : В диссертационной работе используются методы криптографии, дискретной математики, комбинаторики, теории вероятностей.
Достоверность полученных результатов подтверждается математическими доказательствами, статистическими экспериментами, анализом стойкости предложенных алгоритмов, практическими разработками а также широкой апробацией в открытой печати и на научно-технических конференциях.
Научные положения, выносимые на защиту:
-
-
Способ селективного шифрования видеоданных, учитывающий неоднородность информации в видеопотоке.
-
Алгоритм полного шифрования видеоданных с несложной аппаратной реализацией на основе управляемых подстановочно- перестанововочных сетей для защиты видеоинформации с гарантированной стойкостью.
-
Способ генерации большого количества уникальных таблиц перестановок по секретному ключу путём комбинирования блочного шифрования в режиме счётчика с алгоритмом Фибоначчи с запаздываниями.
Научная новизна результатов работы заключается в следующем:
-
-
-
Способ селективного шифрования видеоданных, учитывающий неоднородность информации в видеопотоке, отличающийся использованием уникальной ключевой информации для каждого кадра видеоданных и низкими требованиями к вычислительным ресурсам, что позволяет усилить стойкость к атаке известного контекста, затруднить получение сжатой и незащищённой копии видеоинформации даже при наличии секретного ключа и построить на его основе систему защиты видеоконтента с небольшими требованиями к вычислительным ресурсам.
-
Алгоритм полного шифрования видеоданных с несложной аппаратной реализацией на основе управляемых подстановочно- перестанововочных сетей для защиты видеоинформации с гарантированной стойкостью, отличающийся невысокими требованиями к вычислительным ресурсам, что позволяет реализовывать гарантированную защиту видеоинформации в режиме реального времени с меньшими затратами.
3. Способ генерации большого количества уникальных таблиц перестановок по секретному ключу путём комбинирования блочного шифрования в режиме счётчика с алгоритмом Фибоначчи с запаздываниями, что позволяет повысить стойкость селективного метода защиты видеоданных.
Практическая ценность полученных результатов состоит в создании новых методов защиты видеоинформации, которые могут использоваться при использовании существующей (неадаптированной к защите видеоинформации) инфраструктуре и функционирующих в реальном масштабе времени путём внесения изменений в алгоритм сжатия видеоинформации. Модифицированные алгоритмы сжатия видеоинформации получают новые свойства и позволяют получать сжатую видеоинформацию, которая защищена от несанкционированного просмотра.
Для видеоинформации, которая должна быть защищена с большей стойкостью и может использовать выделенную (защищённую) инфраструктуру, разработан блочный шифр на основе управляемых подстановочно-перестановочных сетей, обеспечивающий высокую эффективность реализации в программируемых логических матрицах нового поколения.
Конкретную практическую значимость имеют следующие полученные результаты:
-
-
-
-
Разработан комбинированный алгоритм получения псевдослучайных чисел на основе метода Фибоначчи с запаздыванием и блочного шифра в режиме счётчика, который позволяет получать различные псевдослучайные последовательности в зависимости от используемого секретного ключа. Алгоритм имеет возможность управления степенью защиты от восстановления всей псевдослучайной последовательности по раскрытой её части.
-
Исследовано влияние перестановки блоков изображения до кодирования и в его процессе на степень сжатия при заданном качестве.
-
Разработан блочный шифр на основе управляемых подстановочно-перестановочных сетей, обеспечивающий высокую эффективность реализации в программируемых логических матрицах нового поколения.
Реализация результатов
Апробация полученных результатов и научных положений подтверждена их обсуждением на следующих конференциях : XVI Общероссийской научно-технической конференции «Методы и технические средства обеспечения безопасности информации» (Санкт-Петербург, 2007 год), Международной конференции по мягким вычислениям и измерениям (Санкт-
Петербург, 2005 год), 2-й межвузовской научной конференции по проблемам информатики (Санкт-Петербург, 2011год).
На основе полученных в диссертационной работе результатов сделан следующий общий вывод : разработанные методы защиты видеоданных позволяют снизить риски раскрытия, искажения и подмены при передаче защищённой видеоинформации по сетям общего доступа, а также позволяют осуществить контроль за распространением защищённого видеоконтента и обеспечить интересы его производителей. Результаты и положения диссертационной работы могут быть использованы в научно- исследовательских и проектно-конструкторских организациях, специализирующихся в области информацонной безопасности, и в университетах при подготовке специалистов в области телекоммуникаций, вычислительных сетей, защиты информации и компьютерной безопасности.
Публикации: Основные результаты по материалам диссертационной работы опубликованы в 7 печатных работах, среди них 2 работы в журналах из перечня ВАК.
Структура и объём диссертации. Диссертация состоит из введения, 6 глав с выводами по каждой их них, заключения, списка литературы и приложения. Она изложена на 121 страницах машинописного текста, включает 33 рисунка, 12 таблиц и список литературы из 58 наименований.
Алгоритм чистых перестановок
Эффективность сжатия необходимо рассматривать в неразрывной связи с понятием качества изображения. Применительно к сжатию видеоданных, качеством изображения называется характеристика сжатого видеопотока при визуальном сравнении с оригиналом. При этом можно оценивать как субъективную степень похожести изображений, так и пытаться получать объективную характеристику разницы между оригиналом и сжатым изображением.
Субъективный метод оценки качества основан на усреднении экспертной оценки группы зрителей. Наблюдатели оценивают качество изображения по определённой шкале, считая, что исходное изображение имеет максимальный балл [16]. В процессе сравнения оцениваются такие характеристики, как правильность цветопередачи, блочность структуры изображения, степень искажения мелких деталей изображения и т. д.
Для интерпретации полученных оценок, разработаны методы их представления (формализации результатов), позволяющие количественно оценить степень искажения той или иной характеристики а также всего набора оценок (усреднённый показатель).
В связи с необходимостью привлечения экспертов, данный метод при сжатии изображений и видеоинформации применяется достаточно редко. Однако он является достаточно точным, потому что учитывает (в среднем) особенности зрительного восприятия. Всё дело в том, что эти особенности пока далеки от формализации, как и само понятие «зрительный акт».
Объективные методы, напротив, целиком основаны на математических моделях, в той или иной степени стремящихся учесть особенности зрительного восприятия. Однако ввиду того, что математически модели далеко не совершенны, вполне вероятны случаи, когда объективно вычисленный показатель качества не соответствует субъективному показателю. Преимуществами объективных методов являются возможность числового представления качества изображения и их сравнительная вычислительная несложность. Фактически, в каждый видеокодек встроен один или несколько таких методов для оценки сжатия. Существует несколько часто используемых объективных методик для вычисления качества изображения, таких как PSNR, Sarnoff JND-Metrix, MSSIM. Некоторые современные методики рассматриваются в работе [17].
Наиболее простой и общеупотребительный - PSNR (peak signalo-noise ratio), который обозначает соотношение между максимумом возможного значения сигнала и мощности шума, который полезный сигнал искажает. PSNR меряется по логарифмической шкале в децибеллах. Вычисляется он с помощью следующей формулы [6]: МАХ/хпХт / PSNR = I0loglo т,п X {I{i,j)-K(i,j)f где I{i,j) и K(i,j) - это оригинал и закодированное изображение размера тхп , МАХ, - это максимальное значение, которое может принять данный компонент изображения (яркость, цвет, цветоразностный сигнал и т.д.). Если изображение цветное, то PSNR считается по всем компонентам цвета, для монохромных - по яркости. Типовое значение PSNR для кодирования видео принимает значение от 30 до 45 децибел л, чем оно выше, тем выше качество изображения. Качество изображения при PSNR 40 децибелл считается хорошим.
Качество изображения меняется в зависимости от параметров видеокодера, используемого при сжатии видеоинформации. Важнейшими из них является битрейт (количество сжатого видеопотока за единицу времени), режим работы видеокодера (одно-/двух-/многопроходной), параметры поиска похожих макроблоков и содержимое матрицы квантования. Любое изменение этих параметров меняет PSNR получаемого сжатого видео в сравнении с исходным.
Данный алгоритм, предложенный в [18][19], использует шифрование опорных кадров (I-кадров), исходя из того, что без них нельзя реконструировать Р- и В-кадры. На самом деле, в Р- и В-кадрах содержатся 1-макроблоки, с помощью которых можно декодировать значительную часть видеоданных. В качестве улучшения в алгоритм добавили шифрование 1-макроблоков вР-иВ-кадрах. Однако суммарная часть таких данных (вместе с 1-кадрами) приближается к 50-70% от общего объема данных в MPEG видеопотоке, что делает такое селективное шифрование похожим на полное шифрование всего потока с соответствующим ухудшением коэффициента сжатия.
Для декодирования закрытого таким методом потока без ключа, можно использовать следующий (или предыдущий) Р- или В-кадр вместо шифрованного 1-кадра (для случая, когда не шифруются 1-макроблоки вР-иВ-кадрах). Для улучшения секретности, авторы предлагают сделать интервалы между 1-кадрами маленькими, однако это дополнительно приблизит алгоритм к полному шифрованию MPEG-потока.
Данный алгоритм с трудом можно назвать селективным, поскольку он шифрует существенную часть видеоинформации, делает видеопоток несовместимым с обычными видеокодеками и катастрофически ухудшает степень сжатия информации.
Алгоритм, предложенный [20] пытается преодолеть данные недостатки. Так как 1-макроблоки и 1-кадры состоят из DCT-коэффициентов, то шифрование некоторых DCT-коэффициентов должно сделать скорость шифрования приемлемой. Действительно, основная информация об изображении сохраняется в DC-коэффициентах (яркость), а АС-коэффициенты хранят информацию о более мелких деталях изображения. Поэтому в этом алгоритме используется шифрование алгоритмом DES всех DC-коэффициентов, а все АС-коэффициенты скремблируются - перемешиваются с помощью блочной перестановки.
Понятие блока изображения
Вместо использования таблицы перестановок в качестве ключа удобно использовать секретный ключ для формирования таблиц перестановок. Основным требованием с точки зрения безопасности при этом, является невозможность восстановления ключа или последующих таблиц перестановок при раскрытии одной из предыдущих таблиц или её части.
Сложность заключается в том, что по короткому ключу необходимо получить достаточно длинную по сравнению с длиной ключа таблицу перестановок. При этом необходимо, чтобы таблица перестановок имела дискретное равномерное распределение (принимала конечное число значений с равными вероятностями) и её элементы располагались в случайном порядке. Для удовлетворения этим требованиям можно использовать псевдослучайную последовательность.
Кроме этого, для повышения безопасности, необходимо, чтобы таблица перестановок для каждого кадра была своя, то есть на основе одного секретного ключа необходимо вычислять большое количество таблиц перестановок.
К сожалению, большинство методов получения псевдослучайных чисел обладают серьёзным недостатком — при условии вычисления нескольких элементов псевдослучайной последовательности, можно вычислить все последующие, а в некоторых случаях — даже все предыдущие. То есть злоумышленник, вычислив несколько элементов таблицы перестановок, сможет определить оставшуюся часть таблицы, или даже всю таблицу не зная секретного ключа.
Поэтому лучше использовать методы получения псевдослучайных чисел либо значительно затрудняющие, либо исключающие такую возможность. Необходимо также, чтобы эти методы позволяли использовать секретный ключ для формирования псевдослучайной последовательности. 2.8 Безопасные методы получения псевдослучайных данных
Рассмотрим 2 метода получения псевдослучайных чисел: метод Фибоначчи с запаздываниями и метод использования блочного шифра в режиме счётчика.
Метод Фибоначчи с запаздываниями [32] [33] характеризуется высокой скоростью работы (для формирования последовательности используются простые арифметические операции) и высоким качеством получаемых псевдослучайных чисел [34]. Использованный в данной работе метод [34] основан на следующей итеративной формуле:
xk=(xk_aXxk-b)mod264 где хк —целые числа из диапазона [0,264-1] ,аи Ъ — целые положительные числа, называемые лагами, их выбор зависит от реализации алгоритма. Существует несколько различных вариантов значений этих чисел, например (17,5), (55,24), (71, 65), (97,33).
По результатам анализа такого генератора псевдослучайных чисел [34] [35], он обладает периодом 261х(2 -1) , где 1=таха,Ь . Это позволяет даже при небольших лагах получать качественные псевдослучайные числа. Однако выбор лагов дополнительно влияет на безопасность получаемых данных.
Для работы методу необходимо начальное наполнение из таха.Ь элементов, которое можно получить любым способом, например линейным конгруэнтным генератором псевдослучайных чисел. Однако, так как от этой последовательности зависит стойкость всей получаемой таблицы, то лучше использовать какой-либо стойкий генератор псевдослучайных чисел, например -блочный шифр в режиме счётчика (описано ниже). При формировании начального наполнения используется секретный ключ, от которого в конечном итоге, зависит вся генерируемая последовательность.
Для формирования таблицы перестановок, необходимо чтобы Хк был целым числом из диапазона [0,п) , где п — число элементов в таблице перестановок. В процессе формирования таблицы перестановок, необходимо следить за тем, чтобы получаемые Хк не повторялись и в этом случае выборка производилась заново.
Для восстановления злоумышленником какой-либо части таблицы перестановок необходимо восстановить хотя бы таха.Ь элементов подряд. Так например, в случае использования пары лагов а, ={97,33} ,необходимо восстановить 97 последовательно расположенных элементов таблицы перестановок, причём чем ближе к началу таблицы они будут восстановлены, тем большую часть таблицы можно будет восстановить.
Результаты сжатия видеоинформации с низкой межкадровой корреляцией после перестановки
Как видим, практически везде наблюдается существенное увеличение размера потока при размере блока, отличном от размера DCT-матрицы (16x16 для большинства кодеков). Исключение составляет алгоритм сжатия Х264, который при увеличении размера блока перестановки до значения 24x24 показывает лучший, чем для случая 16x16 результат. Это является следствием того, что он имеет механизм адаптации с изменением размерности DCT-блока. Даже при размере блока перестановки, равном 36x36 (т.е. некратном 8), его возможности к адаптации позволяют показать лучший результат. Основной причиной, из-за которой остальные кодеки ухудшают свои результаты при увеличении размера блока после блока 16x16 - нарушение естественной последовательности точек в изображении. Действительно, если наложить размерность блоков перестановки (например, 24x24) на внутренний размер блока 16x16, то становится видно, что существенная часть блоков 16x16 делится на несколько частей (см. рисунок 14). Для размеров блоков перестановки 24x24 и 36x36, количество блоков 16x16, которые не были разделены на несколько частей (т.е. сохранивших свою натуральную последовательность) равно 44%. Дополнительные сложности для кодирования видео создают и контрастные границы различных блоков при их совмещении.
Дополнительные сложности для кодирования представляет собой процесс субдискретизации, так как при выборе отличного от 4:4:4 типа происходит уменьшение количества отсчётов для цветоразностных слоёв, в результате чего размерность элементов перестановки не совпадает с границами блоков, которые обрабатыватся кодеками. Это приводит к дополнительным издержкам при кодировании. Схема же субдискретизации 4:4:4 применяется лишь в студийных и профессиональных кодеках и ещё больше снижает эффективность сжатия, но тем самым позволяя повысить качество изображения.
В таблице 3 представлены 4 вида кодеков. MJPEG (Motion JPEG) не учитывает связи между кадрами, каждый кадр сжимает, как отдельное изображние. Алгоритм сжатия в нём похож на алгоритм сжатия JPEG, применяемый для сжатия неподвижных изображений. Применяется в некоторых системах нелинейного монтажа видео, в платах видеозахвата, в вебкамерах и камерах видеонаблюдения. Не требователен к ресурсам, однако имеет сравнительно низкую степень сжатия. В связи с определённым характером тестируемого материала (съёмка из движущейся машины, слабая корреляция между кадрами), кодек показал неплохую эффективность по сравнению с другими, видимо в связи со слабой корреляцией между кадрами. Н263+ (также известный, как H.263v2) является второй версией кодека Н.263, разработанного для развития Н.261 и алгоритмов MPEG1/MPEG2. Он был предназначен для использования в видеоконференциях и оказался эффективен для сжатия последовательности кадров — использовал похожесть кадров для лучшего кодирования видео. Следующее поколение кодеков — MPEG4 (Part 2 ASP - LAVC MPEG4, XVID MPEG4 и Part 10 AVC - H.264) в ещё большей степени реализуют возможности сжатия последовательности кадров, а также имеют более эффективные механизмы для реализации пространственной корреляции внутри каждого кадра изображения. Кроме того, кодек Х264 (MPEG4 Parti AVC - H.264) для конечного сжатия использует контекстнозависимый адаптивный арифметический кодер вместо кодов Хаффмана. Однако по мере улучшения степени сжатия, растут требования к производительности при кодировании и декодировании видеоданных.
По таблице видно, что при сжатии видеоданных с очень малой корреляцией между кадрами и без перемешивания, выделяются 2 группы кодеков с похожими битрейтами - MJPEG/Н263+ и МРЕ04-кодеки (LAVC MPEG4, XVID МPEG4 и Х264). Однако при сжатии перемешанного видео ситуация не столь однозначна - по крайней мере MJPEG/Н263+ уже не выглядят полными аутсайдерами, так как корреляции между такими кадрами становится существенно меньше. Дело в том, что при поиске похожих фрагментов в соседних кадрах, анализируется не весь кадр, а небольшой участок. После перемешивания, найти похожий фрагмент становится затруднительно и эффективность использования корреляции между кадрами падает.
Стоит объяснить также разницу, которая прослеживается при сравнении эффективности сжатия между МРЕ04-кодеками. По таблице выходит, что более новый Х264 проигрывает в степени сжатия кодекам LAVС МPEG4 и XVID МPEG4. Однако это справедливо только с точки зрения сравнения при использовании PSNR, как объективной методики сравнения качества видео. Более новый Х264, исполъзует другие методики для измерения качества сжатия видео, учитывающие особенности зрения человека. То есть при равном Р8NR, видео сжатое Х264 будет, в общем случае, выглядеть лучше (для так называемого “среднего наблюдателя”), чем сжатое LAVC МPEС4 или XVID МРЕС4.
Рассмотрим сжатие тестового видео, где корреляция между кадрами сильна (то есть отсутствует сильное движение, панорамирование, изменение масштаба изображения и т.д.). Для премешивания использовались блоки размером 16x16 точек, то есть равные размеру DCT-блока. Методика получения сжатого видео не изменилась.
Обработка блоков данных в кадрах различных типов
Использование ЭВМ для решения головоломок типа мозаика, впервые было описано в 1964 году в работе Фримана (Freeman) и Гардера (Garder) [42] и стала фундаментальной в данной области. Авторы совмещали на плоскости одноцветные кусочки, подобные кускам разбитой вазы, для получения единого целого.
Следующие работы Левисона (Levison) 1965 [43], 1967 [44], описывали использование ЭВМ для сборки текстовых рукописей из фрагментов. В более поздней работе 1999 года [45] , он же сообщил, что с помощью такого же алгоритма и на значительно большем тексте (использовалось произведение «Алиса в стране чудес») ему удалось составить вместе 8600 фрагментов за 12 минут.
Желая решить головоломку за линейное время, Альтман (Altaian) в 1989 году использовал дерево поиска в комбинации с попарными разностями граней элементов. Фактически, алгоритм работал линейно только при получении попарных сравнений граней. Сборка готового решения (лучшего соответствия попарных сравнений) оказалась NP-C сложной и автор доказал это. Он представил два решения полиномиального типа для конкретного подмножества общей задачи. В качестве такого ограничения был принят тот факт, что попарные разности достаточно уникальны, чтобы на их основе можно было точно установить принадлежность граней различных элементов друг другу.
В качестве инновационного метода сборки головоломки, Бунке (Bunke) и Кауфман (Kaufmann) в 1993 году использовали локальный анализ формы, базирующийся на аппроксимации для проверки пар соседних граней. После рекурсивной оптимизации дерева поиска, оно использовалось для получения решения. Авторы отметили, что алгоритм выполняется за экспоненциальное время, что и можно было ожидать с учётом NP-С природы задачи. Самой большой головоломкой, которую удавалось решить за приемлемое время, была мозаика 6x9 частей (54 элемента).
Охман (Ohman) в 1997 году сканировал элементы мозаики и описал ряд алгоритмов, которые используют сканированные изображения для принятия решения о сборке конечной мозаики. Этот набор эвристических алгоритмов работал с граничными точками элементов мозаики и мог использовать цвет. Для каждой грани определялось, является она «подъёмом» или «впадиной». Несмотря на использование такого упрощённого подхода, автор сообщил об успешной сборке головоломки размером 9x7 (63 элемента).
В работе [46] детально рассмотрен процесс восстановления мозаики с помощью генетического алгоритма, дано определение функции оптимизации и выполнена сборка нескольких тестовых двухцветных (чёрно-белых) головоломок-кроссвордов размером 7x7, 8x8 и 9x9. Для функции оптимизации использовались данные границ блоков. Успешно собрать все тестовые последовательности удалось только для головоломок размера 7x7.
В наиболее полном на данный момент исследовании Яо (Yao) и Шао (8hao) 2003 года [47] использовали информацию и о форме границы элемента мозаики и графическую информацию самого элемента. Целью работы было улучшение нахождения парных соответствий границ. Процесс обработки состоял из шести последовательных шагов.
Актуальность подобных задач активизирует поиски автоматизированных и полуавтоматизированных решений. В частности, DARPA (Агентство по перспективным оборонным научно-исследовательским разработкам США) в октябре 2011 года провело очередной конкурс [48], в ходе которого группам исследователей предлагалось восстановить ряд порезанных на полоски документов (имитировалась работа уничтожителей бумаг). В ходе решения задачи [49], было зарегистрировано 9000 команд исследователей, одна из которых спустя 33 дня смогла восстановить все 5 предложенных документов из более чем 10000 частей. Для решения задачи этой командой было затрачено 600 человеко-часов.
Анализ литературы показывает, что независимые издания не используют результаты друг друга и пытаются самостоятельно решить поставленную задачу. Авторы осознают сложность проблемы, но не пытаются решить лежащую в основе NP-C задачу восстановления исходного изображения. В качестве решения приводится либо набор ограничений, которые позволяют сравнительно быстро найти решение, либо эвристический способ уменьшения количества вычислений, который необходим для решения мозаики.
В число ограничений обычно вводят так называемую «уникальность» изображения. Она подразумевает, что в изображении мало или вообще нет одинаковых элементов (таких, как например, протяжённые участки неба или другой поверхности с повторяющимися границами).
Похожие диссертации на Метод защиты видеоданных с различной степенью конфиденциальности
-
-
-
-
-
-
