Нейросетевые технологии в задачах обработки видеоинформации

1




Реферат


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

    Ключевые слова: СЖАТИЕ ИЗОБРАЖЕНИЙ, НЕЙРОННЫЕ СЕТИ, ПЕРСЕПТРОН, АСУ ДД, АЛГОРИТМ СЖАТИЯ, ПРОЦЕСС ОБУЧЕНИЯ, СВЕРТОЧНЫЕ НЕЙРОННЫЕ СЕТИ, РЕКУРРЕНТНЫЕ НЕЙРОННЫЕ СЕ-ТИ, TENSORFLOW, CUDA.

    Магистерская диссертация посвящена актуальной проблеме сжатия ви-деоинформации с помощью нейросетевых технологий. Рассмотрены основ-ные технические, функциональные и информационные аспекты сжатия изоб-ражений с помощью нейронных сетей. Проведен анализ современных плат-форм для реализации нейросетевых алгоритмов. Разработаны алгоритмы сжатия изображений в персептронных нейронных схемах и рекуррентных се-тях. Исследованы вопросы применения нейросетевых технологий сжатия изображений в АСУ ДД. Проведен сравнительный анализ эффективности разработанных алгоритмов сжатия статических изображений. Выполнена программная реализация разработанного алгоритма на языке программиро-вания Python с использованием набора инструментов для машинного обуче-ния таких как TensorFlow и CUDA.
    



2


Оглавление

Введение ...................................................................................................................
4
1.  Нейросетевые технологии в задачах обработки видеоинформации ...........
6
1.1
Прикладные возможности нейронных сетей ..............................................
6
1.2
Задача нейросетевого сжатия видеоизображений ......................................
9
1.3
Внедрение нейросетевых технологий сжатия видеоизображений в

АСУДД ...................................................................................................................
14
Выводы ...................................................................................................................
17
2.  Обзор классических методов сжатия изображений ....................................
18
2.1

Постановка задачи .......................................................................................
18
2.2
Проблема сжатия цифровых изображений ...............................................
21
2.2.1
Оценка качества декодированного изображения ..................................
23
2.2.2
Оценка времени работы алгоритма сжатия изображений ....................
25
2.3
Анализ методов сжатия изображений без потери качества ....................
25
2.3.1
Алгоритм RLE ...........................................................................................
26
2.3.2
Алгоритм Хаффмана ................................................................................
26
2.3.3
Алгоритм сжатия Лемпела-Зива .............................................................
28
2.3.4
Алгоритм сжатия Лемпеля-Зива-Велча (Lempel-Ziv-Welch-LZW) .....
29
2.3.5
Алгоритм JPEG-LS ...................................................................................
30
2.4
Анализ методов сжатия изображений без потери качества ....................
31
2.4.1
Метод усеченного блочного кодирования (УБК) .................................
31
2.4.2
Дискретные преобразования изображений в сжатии данных ..............
33
2.4.3
JPEG ...........................................................................................................
35
Выводы ...................................................................................................................
38
3.  Нейросетевые технологии в задаче сжатия изображений ..........................
39
3.1

Общие положения ........................................................................................
39
3.2
Процесс обучения нейронных сетей ..........................................................
44
3.2.1
Обучение, основанное на коррекции ошибок .......................................
45
3.3

Сети Цао Ена ................................................................................................
46
3.4

Рециркуляционные нейронные сети ..........................................................
49
3.4.1
Метод главных компонент .......................................................................
49
3.4.2
Архитектура рециркуляционной нейронной сети .................................
51

3

3.4.3	Обработка изображений	53

3.5	Сверточные нейронные сети	53

3.5.1	Архитектура сверточной нейронной сети	53

3.5.2	Математическое описание СНС	56

3.5.3	Сверточный слой	56

3.5.4	Субдискретизирующий слой (слой пулинга)	57

3.5.5	Слой MLP	57

Выводы	58

4. Программная реализация нейросетевого алгоритма сжатия

изображений	59

4.1	Архитектура нейронной сети для сжатия изображений	59

4.2	Рекуррентные нейронные сети	61

4.3	Реконструкция изображения	63

4.4	Инструменты для реализации нейросетевых алгоритмов	64

4.4.1	Технология CUDA	65

4.4.2	Выбор средств для реализации нейросетевого алгоритма	67

4.4.3	Библиотека машинного обучения TensorFlow	68

4.5	Результаты работы программы	71

Выводы	75

Заключение	76

Список используемой литературы	77

4

Введение

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

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

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

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

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

    Сегодня существует множество различных подходов к сжатию изобра-жений. Одними из самых используемых на практике являются алгоритмы, основанные на кодировании блоков изображения с применением дискретных преобразований. Среди таких алгоритмов фактическим эталоном служит ал-горитм JPEG (Joint Photographic Experts Group). Однако данные алгоритмы сложно реализуемы и имеют относительно невысокую скорость работы.

    В последнее время возник интерес к альтернативным способам сжатия. Одним из перспективных представляется развитие подхода, в основе которо-го лежат искусственные нейронные сети (ИНС). В связи с этим актуальной
    
5

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

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

Решаемые в работе задачи:

1. Анализ перспектив применения нейронных сетей в задачах сжатия изображений.

2. Исследование вопросов применения технологий нейросетевого сжатия изображений в автоматизированных системах управления дорожным движением (АСУ ДД).

3. Разработка алгоритма сжатия изображений на основе персептронных нейронных схем и нейронных рекуррентных сетей.

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

5. Сравнительный анализ эффективности разработанных алгоритмов сжа-тия изображений.

6

1. Нейросетевые технологии в задачах обработки видеоинформации

1.1 Прикладные возможности нейронных сетей

    Нейронные сети представляют из себя новую и весьма перспективную вычислительную технологию, дающую новые подходы к решению различно-го типа задач. Термин «нейронная сеть» появился в середине 20-го века. Пер-вые работы, в которых были получены одни из первых результатов в данном направлении, были проделаны Мак-Каллоком и Питтсом. В 1943 году ими была разработана компьютерная модель нейронной сети на основе математи-ческих алгоритмов и теории деятельности головного мозга. Они выдвинули предположение, что нейроны могут быть рассмотрены в упрощенном виде в качестве устройства, оперирующие двоичными числами, и назвали эту мо-дель «пороговой логикой».

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

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

? аппроксимация и интерполяция;

? распознавание и классификация образов;

? сжатие данных;

7

? прогнозирование;

? идентификация;

? управление;

? ассоциация.

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

    В каждой из вышеперечисленных задач нейронная сеть выполняет роль аппроксиматора функции нескольких переменных реализуя нелинейную функцию
=  ( ),

где	- это входной вектор, а	– векторное представление функции от

нескольких переменных.

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

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

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

предыдущие действия. Если известны все значения , которые предшествуют прогнозируемому событию:  (  ? 0),  (  ? 1), … ,  (  ? ? 1), то задача нейронной сети состоит в том, чтобы предсказать наиболее вероятное значе-ние на шаге :  ?( ). Для того, чтобы оптимально настроить весовые коэф-фициенты нейронная сеть вычисляет фактическую погрешность предсказа-ния: =  ( ) ?  ?( ), а также значение погрешности на всех предыдущих шагах алгоритма.

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

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

    В задачах ассоциации нейронные сети играют роль ассоциативного за-поминающего устройства (ЗУ). Существует два основных вида запоминаю-щих устройств:

1) ЗУ автоассоциативного типа – данные устройства рассчитывают кор-реляцию между различными компонентами одного и того же входно-го вектора.

2) ЗУ гетероассоциативного типа – эти устройства рассчитывается кор-

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

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

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

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

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

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

1.2 Задача нейросетевого сжатия видеоизображений

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

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

    В отличие от традиционных методов сжатия изображений, которые за-ключаются в математическом вычислении и удалении избыточности, нейронные сети для решения этой задачи исходят из соображения нехватки ресурсов. Устройство и способ обучения нейросети таковы, что входные данные большой размерности должны быть обработаны и переданы на ее выход с помощью относительно небольших каналов связи. Чтобы осуще-ствить сжатие таким способом можно использовать многослойный персеп-трон, который имеет следующую архитектуру: размерность входного и вы-ходного слоев совпадает и равна размерности поступающих данных. Между ними находится один или несколько скрытых (промежуточных) слоев мень-шего размера. Их количество определяет сложность преобразования сжимае-мых данных. Например, нейронная сеть с одним промежуточным слоем мо-жет показывать худшие результаты сжатия обучающих изображений, чем сеть с четырьмя слоями, но может показать лучший результат в реальных си-туациях. Это зависит от того, что в начальных данных может образоваться некая зависимость, не имеющая никакого отношения к действительности.

    В качестве примера сжатия изображений нейронной сетью возьмем ли-нейную сеть с одним промежуточным слоем. Ее архитектура изображена на рисунке ниже.

























Рис. 1.1 Структура нейронной сети с одним скрытым слоем

11

    Количество нейронов, образующих выходной слой совпадает с нейро-нов, образующих входной слой. Скрытый слой содержит нейронов. Важ-ным условием является то, что ? . Пара входной – скрытый слой выпол-няет непосредственной сжатие данных подающихся на вход нейронной сети. Пара скрытый – выходной слой осуществляет их восстановление.

    Сжатию подвергаются данные, разделенные на кадры, представляемые последовательностью -элементных векторов ( — количество входных уз-лов). Кадры имеют форму прямоугольника с размерами ? пикселов по гори-зонтали и - по вертикали. Градации интенсивности пикселов, входящих в кадр, задаются значениями компонентов вектора . Пример разделения изоб-ражения на кадры с последующим соотнесением повторяющихся пикселов изображения вектору представлен на следующем рисунке.
























Рис. 1.2 Разбиение изображения на кадры

    Поскольку ? , скрытый слой способен обрабатывать меньшее коли-чество информации нежели входной слой, однако она будет репрезентатив-ной для множества данных и достаточной для реконструкции с заранее за-данной точностью исходных входных данных. Связи скрытого слоя образуют главные компоненты преобразования PCA (англ.: Principal Component Analysis), из которых и образуется информационное ядро. Количество этих компонентов совпадает с числом нейронов в скрытом слое, которое равняет-
    
12

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

        Мы используем полностью линейную нейронную сеть. Веса скрытого слоя в матричной форме обозначим (1), а выходного слоя (2).

    С учетом однонаправленного распространения сигналов можно полу-чить:

? вектор сигналов скрытого слоя (сжатые данные):
? =  (1)  .

? вектор выходных сигналов (восстановленные данные):
 ? =	(2)? = ? =  (2)   (1)  .

Обучение данной сети состоит в том, чтобы оптимально подобрать веса,
которые образуют матрицы	(1) и	(2). Это позволит получить минималь-
ную разность между	( ) и  ?( ) для всех   составляющих вектора  ( ) при  =
1,????? (где	обозначено количество векторов).

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

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

Основными возможностями нейронных сетей являются следующие:

? Гибкость структуры: можно различными способами настраивать элементы нейросети (количество слоев, нейроны и связи между

13

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

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

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

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

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

? Обученная нейронная сеть обладает устойчивостью к отказам от-дельных элементов (нейронов). Также можно использовать и спе-циальные методы для повышения отказоустойчивости. Чаще всего это применяется при аппаратной реализации нейронной сете ? для обеспечения построения надежных систем из ненадежных элемен-тов.

? Возможность распараллеливания вычислений (например, исполь-зование многопоточности или многопроцессорности) в процессе

14

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

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

1.3 Внедрение нейросетевых технологий сжатия видеоизображений в

АСУДД

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

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

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

? медицинские изображения;

? изображения, полученные в результате спутникового мониторинга;

? фотоизображения.

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

    Сегодня в крупных городах широко применяются автоматизированные системы управления дорожным движением (АСУДД).

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

    Контроль транспортных потоков в АСУДД осуществляются посред-ством системы видеомониторинга. Источниками данных здесь являются ви-деокамеры, которые устанавливаются непосредственно над автомобильной дорогой, образуя рубеж контроля системы.

    Цифровая и видеоинформация о дорожной обстановке, характеристиках транспортных потоков, погодных условиях и состоянии дорожного покрытия передается на сервер в центральный пункт управления АСУДД. Данный сер-вер осуществляет долговременное хранение информации, выписку и хране-ние постановлений о нарушении ПДД, проверку ТС по базам розыска.



























Рис. 1.3 Принцип работы АСУДД

    Наиболее важным процессом управления транспортным движением яв-ляется анализ транспортных потоков (АТП). В общем случае система АТП может включать в себя следующие подсистемы:
    
16

1) системы видеонаблюдения за потоком;

2) средств отображения и регистрации видеоинформации;

3) системы автоматического распознавания номеров;

4) системы учета и ведения базы данных автомобильных номерных знаков;

5) центральный диспетчерский пункт управления.

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

    АСУДД может состоят из множества камер, фиксирующих и отправля-ющих различную видеоинформацию в режиме реального времени.

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

    Данные, получаемые с камер наблюдения, обязательно должны хранить-ся определенное время. При возникновении спорных или сложных ситуаций можно будет воспользоваться видеоархивом и получить детальную инфор-мацию о происшествии, случившемся некоторое время назад. Объем одной секунды видеоролика с частотой 30 кадр/с при разрешении 640 ? 480 пиксе-лов, представленных 8-разрядным кодом (256 цветов), составляет 9 Мбайт. При использовании 24-разрядной цветовой палитры (16 млн. цветов) и раз-решении 1280 ? 1024 эта цифра увеличится до 114 Мбайт. Ежедневно на ви-деосерверы АСУДД поступают данные с тысяч камер, установленных по го-
    
17

роду. Для ее длительного хранения необходимо внедрение действенных ал-горитмов компрессии.

    Для решения данной задачи также предлагается использовать нейросе-тевые технологии компрессии видеоданных. На видеосерверах можно более широко использовать преимущества нейросетевых технологий. Здесь можно развернуть платформы для распараллеливания вычислений (такие как CUDA, TensorFlow или Pytorch) и реализовать более сложные алгоритмы компрессии данных.

Выводы

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

    На сегодняшний день задача сжатия изображений возникает в различ-ных областях деятельности. Особенно остро она стоит при создании различ-ного рода систем хранения. Было показано какую важную роль играет сжатие видеоизображений АСУДД, поэтому внедрение нейросетевых технологий в системы контроля дорожного движения является перспективной темой для научных работ.
    
18




2. Обзор классических методов сжатия изображений

2.1 Постановка задачи

    Задачу сжатия изображения можно представить следующим образом. Цифровое изображение представляет из себя двумерный массив данных раз-мером ? . Если за обозначить количество строк, а за – количество столбцов, то можно компактно записать полное цифровое изображение в ви-де матрицы:

 (0,0)
 (0,1)
?
 (0,  ? 1)

 ( ,  ) = [
 (1,0)
 (1,1)
?
 (1,  ? 1)
]

?
?
?
?


 (  ? 1,0)
 (  ? 1,1)
?
 (  ? 1,  ? 1)


    Для определения размера памяти, необходимой для хранения цифрового изображения помимо и необходимо также учесть количество уровней (градаций) яркости . Для удобства значения обычно выбирают равным це-лочисленной степени двойки:
= 2 .

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

В случае квадратного изображения, матрица примет вид:
=	2 ?  .

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

    Процесс сжатия изображения в простейшем случае состоит из двух ча-стей:
    
19

1. Кодирование;

2. Декодирование.

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

    В основе большинства современных методов сжатия изображений лежит достаточно простое предположение: любое изображение содержит некото-

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

1) Статистическая избыточность. Этот тип избыточности обуславлива-ется тем, что в изображении присутствуют коррелированные данные, которые можно предсказать. Ее отличительная особенность заключа-ется в том, что она может быть удалена без потери информации, сле-довательно, начальное изображение может быть полностью восста-новлено. Один из самых распространенных подходов удаления такой избыточности основан на знании частоты каждого символа, который присутствует в изображении. На основании этих знаний строятся таблицы кодов, которые имеют следующие свойства:

? различные коды могут иметь различное количество бит;

? чем чаще встречается символ, тем меньше бит требуется для его кодирования;

? полученные коды имеют разную длину, но они могут быть од-нозначно востановлены (осуществляется префиксное посторое-ние кодов).

20

Этими свойствами обладает известный алгоритм Хаффмана.

2) Визуальная (субъективная) избыточность. Другой вид избыточности. Ее удаление приводит к частичной потере исходных данных, которые мало влияют на качество получаемых изображений, поэтому ее устранение практически не нарушает визуального восприятия сжато-го изображения. Данный подход является наиболее применяемым се-годня для передачи информации. Здесь необходимо соблюдение двух формальных условий: стараться полностью удалять избыточную ин-

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

    Рассмотрим основные этапы процесса сжатия изображений в общем ви-де. Любой метод сжатия реализует три основных этапа:

? первичное сжатие;

? вторичное сжатие;

? восстановление изображения.


























Рис. 2.1 Общая схема сжатия изображений

    На первом шаге производится перевод исходного изображения в другую форму представления данных.
    
21

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

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

2.2 Проблема сжатия цифровых изображений

    Методы, которые используют обратимые преобразования (сжатие без потерь) имею достаточно узкую область применения: научные или медицин-ские приложения. Зачастую в данных областях не допускается потеря какой-либо информации. Более того, в некоторых случаях самым важным элемен-том изображения может являться шум. Данные методы позволяют сжать изображение в 1.5 – 2 раза, в то время как методы использующие необрати-мые преобразования (сжатие с потерями) достигают показателя коэффициен-та сжатия равного 200.
    
22




























Рис. 2.2 Методы сжатия изображений

    Однако при сжатии с потерями происходит искажение исходного изоб-ражения, что ведет к ухудшению его качества. В связи с этим при сравнении различных подходов к сжатию помимо коэффициента сжатия нужно также учитывать и качество восстановленного изображения. Для симметричных методов процедуры сжатия и восстановления полностью идентичны. Это означает, что время, затраченное на сжатие и восстановления изображения, практически не различается. Для несимметричных методов процедура сжатия отличается от процедуры восстановления и чаще всего занимает больше вре-мени. Дадим определение основным величинам, характеризующим алгорит-мы сжатия изображений.
Коэффициент сжатия	сж:
1
сж =	2.


     Эта величина показывает, во сколько раз сжатое изображение меньше исходного изображения (учитывая некоторые недостатки определенных ме-тодов, данный коэффициент может быть больше 1). Величины 1 и 2выра-жаются в байтах. сж– величина безразмерная.
     
23

2.2.1  Оценка качества декодированного изображения

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

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

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

? , [ ( ,  ) ?  (? ,  )]2
 ( ,  ) = ?	 , 	.



    Данный метод имеет множество недостатков: если измени.......................