В данной работе рассмотрены основные виды избыточности графической информации, а также способы ее устранения. В результате сжатия уменьшается размер изображения, что сокращает время передачи изображения по сети, и экономит пространство для хранения. Все большую актуальность приобретают эффективные методы сжатия, влекущие за собой наименьшие потери данных. Ежедневно огромное количество информации запоминается, преобразуется и передается в цифровом виде. Поскольку большая часть передаваемых данных является графической или видеоинформацией, возникает все большая потребность в качественном сжатии, влекущем за собой как можно меньшие потери. Сжатие изображений ориентировано на сокращение объема данных представляющих определенное количество информации. Зачастую эта проблема решается путем удаления избыточной информации. Пусть и обозначают число элементов носителей информации в двух наборах данных, представляющих одну и ту же информацию. Тогда относительная избыточность данных может быть определена как. Различают три вида избыточности данных в задаче цифрового сжатия изображений: Сжатие данных достигается в том случае, когда устраняется или сокращается избыточность одного или нескольких из вышеуказанных видов. Рассмотрим каждый из видов по отдельности [1]. Пусть дискретная случайная переменная появляется с вероятностью , — общее число уровней яркости, — число пикселей, имеющих значение яркости , а — общее число элементов в изображении. Если число битов, используемых для представления каждого из значений , равно , то среднее число битов, требуемых для представления значения одного элемента, равно:. Если код значения яркости образуется не минимизацией предыдущего уравнения, то говорят, что изображение имеет кодовую избыточность. Нетрудно увидеть, что присвоение кодовых слов с меньшим числом битов более вероятным значениям яркости, и наоборот, более длинных кодовых слов менее вероятным значениям т. С другой стороны, кодирование, используемое для представления значений яркости, не может изменить корреляции между пикселями, которая является следствием структурных или геометрических взаимосвязей между объектами на изображении. Коэффициенты автокорреляции , вычисленные вдоль одной строки каждого изображения могут быть получены с помощью уравнения:. Поскольку значение каждого элемента изображения может быть предсказано по значениям его соседних, то информация, содержащаяся в отдельном элементе, оказывается достаточно малой. Большая часть содержащейся информации является избыточной. Такая избыточность называется межэлементной. Для ее уменьшения двумерный массив пикселей должен быть преобразован в некоторый более рациональный формат. Другими словами, нужно найти отображение данного множества в более упрощенное, достигнутое, допустим, разностью между соседними пикселями. Известно, что воспринимаемая глазом яркость зависит не только от количества света, исходящего из рассматриваемой области. При обычном визуальном восприятии часть информации оказывается менее важной, чем другая. Такую информацию называют визуально избыточной. Она может быть удалена без заметного ухудшения визуального качества изображения [1,2,3]. Рассмотренные выше методы избавления от разных видов избыточности информации на практике обычно используются совместно. Система сжатия любого изображения состоит из двух структурных блоков: Исходное изображение поступает на вход кодера, который преобразует его в набор символов. После передачи по каналу данные поступают в декодер, где создается восстановленное изображение. В результате может получиться как точная копия исходного изображения кодирование без потерь , так и несколько измененная кодированная с потерями. Кодер источника сокращает возможные виды избыточности на входном изображении. Благодаря отдельным приложениям выбирается тот или иной способ шифрования, являющийся оптимальным в каждом конкретном случае. Процедура кодирования представляется в виде последовательности трех стадий: На этапе преобразователя входные данные изображение представляется в формате, предназначенном для сокращения межэлементной избыточности. Второй шаг, или блок квантователя, позволяет сократить визуальную избыточность за счет уменьшения точности выхода преобразователя. На третьей и последней стадии кодер символов создает равномерный или неравномерный код. Таким образом, после прохождения трех этапов кодирования изображение избавляется от всех видов избыточности. Однако, следует помнить, что этап квантователя является необратимым, что в случае сжатия без потерь требует пропуска этого шага [4,6]. Схема декодера источника включает лишь два блока: Здесь осуществляются операции, обратные тем операциям, которые выполнялись в кодере источника, причем в обратном порядке, исключая лишь этап квантователя, по той же причине его необратимости. В случае, когда канал передачи имеет собственные шумы и помехи, важную роль в процессе кодирования играют кодер и декодер канала. Уменьшение влияния шума в канале передачи достигается путем наращивания к исходным закодированным данным избыточной информации. К слову добавляются проверочные биты, способные исправить и обнаружить единичные ошибки. Этот прием позволяет добиться большей устойчивости передаваемым данным к помехам. Декодер канала, аналогично декодеру источника выполняет обратные преобразования. Алгоритмы сжатия изображений подразделяются на две большие группы: Первые в ходе передачи сохраняют информацию об изображении полностью, а вторые — только частично. Первая группа методов сжатия обеспечивает восстановление исходного изображения без потерь и искажений. К изображениям, предназначенным для хранения с целью дальнейшей обработки, следует применять методы первого типа. Однако, если изображение предназначено для визуального восприятия, это не всегда необходимо. В ряде случаев исходный сигнал уже содержит такие искажения и шумы, что небольшие потери информации при кодировании в пользу высокой степени сжатия не испортят качества изображения в целом [5]. Одна из серьезных проблем компьютерной графики заключается в том, что до сих пор не найден адекватный и однозначный критерий оценки потерь качества изображения. Для изображений, наблюдаемых визуально, основным является неотличимость глазом исходного и компрессированного изображения. При передаче сжатых данных неизбежно возникают потери. Однако в некоторых отдельных случаях такое положение вещей недопустимо. Одним из примеров может служить архивация медицинских и деловых документов, сжатие с потерями которых зачастую запрещено законом. Другим примером являются спутниковые изображения, способ получения которых слишком дорогостоящ, для того, чтобы производить сжатие с потерями. Таким образом, сжатие изображения без потерь всегда будет достаточно востребовано. Алгоритмы такого сжатия обычно состоят из двух не зависящих друг от друга операций: К наиболее распространенным подходам сжатия без потерь относятся: Сжатие с потерями основано на выборе баланса между точностью восстановления изображения и степенью его сжимаемости. Если можно допустить появление некоторого искажения в конечном результате кодирования, то возможно значительное увеличение коэффициента сжатия. Как показано выше, принципиальная разница между структурными схемами двух подходов заключается в наличии или отсутствии блока квантования. Различают следующие виды сжатия с потерями: В данной статье мы изложили теоретические основы сжатия цифровых изображений, а также описали наиболее распространенные методы сжатия, составляющие ядро существующей на данный момент технологии. Предложенные методы играют все более важную роль в архивном хранении изображений документов, в также при передаче данных. Наряду с обработкой изображений, сжатие является высоко перспективной областью, что гарантирует дальнейшее развитие имеющихся методов и стандартов [1]. Полезная информация Спецвыпуски Правила оформления Оплата и скидки Вопрос — ответ Отзывы и защиты наших авторов. Черногорова Юлия Викторовна Рубрика: Скачать электронную версию Скачать Часть 2 pdf. Основные термины генерируются автоматически: Ключевые слова кодирование , сжатие изображений, избыточность информации, кодер, декодер. Похожие статьи Метод согласованной идентификации в задаче ректификации изображений. Итерационная процедура высокоточного совмещения аффинно-преобразованных изображений. Разработка и исследование методов сжатия геометрической информации и оценка близости сложных объектов на основе порождающих моделей. Проблема сжатия геометрической информации сложных объектов. Разработка средств компьютерной визуализации для научных исследований: Правила оформления статей Оплата и скидки. Подпишитесь на нашу рассылку:
Только полноправные пользователи могут оставлять комментарии. TM Feed Хабрахабр Geektimes Тостер Мой круг Фрилансим. Хабрахабр Публикации Пользователи Хабы Компании Песочница. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений. Все существующие алгоритмы можно разделить на два больших класса: Алгоритмы сжатия без потерь; Алгоритмы сжатия с потерями. Когда мы говорим о сжатии без потерь, мы имеем в виду, что существует алгоритм, обратный алгоритму сжатия, позволяющий точно восстановить исходное изображение. Для алгоритмов сжатия с потерями обратного алгоритма не существует. Существует алгоритм, восстанавливающий изображение не обязательно точно совпадающее с исходным. Алгоритмы сжатия и восстановления подбираются так, чтобы добиться высокой степени сжатия и при этом сохранить визуальное качество изображения. Алгоритмы сжатия без потерь Алгоритм RLE Все алгоритмы серии RLE основаны на очень простой идее: Рассмотрим этот алгоритм на примере последовательности бит. В этой последовательности будут чередовать группы нулей и единиц. Причём в группах зачастую будет более одного элемента. Тогда последовательности 00 будет соответствовать следующий набор чисел 5 6 8 2. Эти числа обозначают количество повторений отсчёт начинается с единиц , но эти числа тоже необходимо кодировать. Будем считать, что число повторений лежит в пределах от 0 до 7 то есть нам хватит 3 бит для кодирования числа повторов. Тогда рассмотренная выше последовательность кодируется следующей последовательностью чисел 5 6 7 0 1 2. Легко подсчитать, что для кодирования исходной последовательности требуется 21 бит, а в сжатом по методу RLE виде эта последовательность занимает 18 бит. Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности. Для примера рассмотрим следующую последовательность Соответствующая ей RL-последовательность выглядит так: Длина исходной последовательности — 17 бит, длина сжатой последовательности — 18 бит. Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов. Словарные алгоритмы Идея, лежащая в основе словарных алгоритмов, заключается в том, что происходит кодирование цепочек элементов исходной последовательности. При этом кодировании используется специальный словарь, который получается на основе исходной последовательности. Существует целое семейство словарных алгоритмов, но мы рассмотрим наиболее распространённый алгоритм LZW, названный в честь его разработчиков Лепеля, Зива и Уэлча. Словарь в этом алгоритме представляет собой таблицу, которая заполняется цепочками кодирования по мере работы алгоритма. При декодировании сжатого кода словарь восстанавливается автоматически, поэтому нет необходимости передавать словарь вместе с сжатым кодом. Словарь инициализируется всеми одноэлементными цепочками, то есть первые строки словаря представляют собой алфавит, в котором мы производим кодирование. При сжатии происходит поиск наиболее длинной цепочки уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда, при этом выводится сжатый код, соответствующий уже записанной в словаре цепочки. В теории на размер словаря не накладывается никаких ограничений, но на практике есть смысл этот размер ограничивать, так как со временем начинаются встречаться цепочки, которые больше в тексте не встречаются. Кроме того, при увеличении размеры таблицы вдвое мы должны выделять лишний бит для хранения сжатых кодов. Для того чтобы не допускать таких ситуаций, вводится специальный код, символизирующий инициализацию таблицы всеми одноэлементными цепочками. Рассмотрим пример сжатия алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Предположим, что словарь будет вмещать 32 позиции, а значит, каждый его код будет занимать 5 бит. Изначально словарь заполнен следующим образом: Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия. В таблице представлен процесс заполнения словаря. Легко подсчитать, что полученный сжатый код занимает бит, а исходный текст при условии, что на кодирование одного символа мы тратим 4 бита занимает бит. По сути, процесс декодирования сводится к прямой расшифровке кодов, при этом важно, чтобы таблица была инициализирована также, как и при кодировании. Теперь рассмотрим алгоритм декодирования. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c — это один символ, а S — строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются. Алгоритмы статистического кодирования Алгоритмы этой серии ставят наиболее частым элементам последовательностей наиболее короткий сжатый код. Причём, чем чаще встречается последовательность, тем короче, соответствующий ей сжатый код. Алгоритм Хаффмана Алгоритм Хаффмана позволяет строить префиксные коды. Можно рассматривать префиксные коды как пути на двоичном дереве: Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева. Опишем алгоритм построения дерева Хаффмана и получения кодов Хаффмана. Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа Выбираются два свободных узла дерева с наименьшими весами Создается их родитель с весом, равным их суммарному весу Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0 Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева. С помощью этого алгоритма мы можем получить коды Хаффмана для заданного алфавита с учётом частоты появления символов. Арифметическое кодирование Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею. Пусть наш алфавит состоит из N символов a1,…,aN, а частоты их появления p1,…,pN соответственно. Разобьем полуинтервал [0;1 на N непересекающихся полуинтервалов. Каждый полуинтервал соответствует элементам ai, при этом длина полуинтервала пропорциональна частоте pi. Кодирующая дробь строится следующим образом: После того, как все интервалы вложены друг в друга можно взять любое число из получившегося полуинтервала. Запись этого числа в двоичном коде и будет представлять собой сжатый код. Декодирование — расшифровка дроби по известному распределению вероятностей. Очевидно, что для декодирования необходимо хранить таблицу частот. Арифметическое кодирование чрезвычайно эффективно. Коды, получаемые с его помощью, приближаются к теоретическому пределу. Это позволяет утверждать, что по мере истечения сроков патентов, арифметическое кодирование будет становиться всё более и более популярным. Алгоритмы сжатия с потерями Не смотря на множество весьма эффективных алгоритмов сжатия без потерь, становится очевидно, что эти алгоритмы не обеспечивают и не могут обеспечить достаточной степени сжатия. Сжатие с потерями применительно к изображениям основывается на особенностях человеческого зрения. Мы рассмотрим основные идеи, лежащие в основе алгоритма сжатия изображений JPEG. Алгоритм сжатия JPEG JPEG на данный момент один из самых распространенных способов сжатия изображений с потерями. Опишем основные шаги, лежащие в основе этого алгоритма. Будем считать, что на вход алгоритма сжатия поступает изображение с глубиной цвета 24 бита на пиксел изображение представлено в цветовой модели RGB. Перевод в цветовое пространство YCbCr В цветовой модели YCbCr мы представляем изображение в виде яркостной компоненты Y и двух цветоразностных компонент Cb,Cr. Человеческий глаз более восприимчив к яркости, а не к цвету, поэтому алгоритм JPEG вносит по возможности минимальные изменения в яркостную компоненту Y , а в цветоразностные компоненты могут вноситься значительные изменения. Перевод осуществляется по следующей формуле: Выбор Kr и Kb зависит от оборудования. Субдискретизация компонент цветности После перевода в цветовое пространство YCbCr выполняется дискретизация. Возможен один из трёх способов дискретизации: Очевидно, что чем больше информации мы теряем, тем сильнее будут искажения в итоговом изображении. Это приводит к уплотнению энергии в коде. Преобразования применяются к компонентам независимо. Квантование Человек практически не способен замечать изменения в высокочастотных составляющих, поэтому коэффициенты, отвечающие за высокие частоты можно хранить с меньшей точностью. Для этого используется покомпонентное умножение и округление матриц, полученных в результате ДКП, на матрицу квантования. На данном этапе тоже можно регулировать степень сжатия чем ближе к нулю компоненты матрицы квантования, тем меньше будет диапазон итоговой матрицы. Зигзаг-обход матриц Зигзаг-обход матрицы — это специальное направление обхода, представленное на рисунке: При этом для большинства реальных изображений в начале будут идти ненулевые коэффициенты, а ближе к концу будут идти нули. RLE- кодировние Используется особый вид RLE-кодирования: Кодирование методом Хаффмана Используется описанный выше алгоритм Хаффмана. При кодировании используется заранее определённая таблица. Алгоритм декодирования заключается в обращении выполненных преобразований. К достоинствам алгоритма можно отнести высокую степень сжатие 5 и более раз , относительно невысокая сложность с учётом специальных процессорных инструкций , патентная чистота. Недостаток — артефакты, заметные для человеческого глаза. Фрактальное сжатие Фрактальное сжатие — это относительно новая область. Фрактал — сложная геометрическая фигура, обладающая свойством самоподобия. Алгоритмы фрактального сжатия сейчас активно развиваются, но идеи, лежащие в их основе можно описать следующей последовательностью действий. Разделение изображения на неперекрывающиеся области домены. Набор доменов должен покрывать всё изображение полностью. Ранговые области могут перекрываться и не покрывать целиком всё изображение. Сжатие и сохранение параметров аффинного преобразования. В файл записывается информация о расположении доменов и ранговых областей, а также сжатые коэффициенты аффинных преобразований. Создание двух изображений одинакового размера A и B. Размер и содержание областей не имеют значения. Изображение B делится на домены так же, как и на первой стадии процесса сжатия. Для каждого домена области B проводится соответствующее аффинное преобразование ранговых областей изображения A, описанное коэффициентами из сжатого файла. Результат помещается в область B. После преобразования получается совершенно новое изображение. Преобразование данных из области B в область A. Этот шаг повторяет шаг 3, только изображения A и B поменялись местами. Шаги 3 и 4 повторяются до тех пор, пока изображения A и B не станут неразличимыми. Точность полученного изображения зависит от точности аффинного преобразования. Сложность алгоритмов фрактального сжатия в том, что используется целочисленная арифметика и специальные довольно сложные методы, уменьшающие ошибки округления. Отличительной особенностью фрактального сжатия является его ярко выраженная ассиметрия. Алгоритмы сжатия и восстановления существенно различаются сжатие требует гораздо большего количества вычислений. Тестирование IT-систем авторов , 1,1k публикаций. Программирование 2,9k авторов , 6,5k публикаций. JavaScript 1,9k авторов , 4k публикаций. Совершенный код авторов , публикации. Системное программирование авторов , публикации. IT-стандарты авторов , публикаций. Разработка веб-сайтов 4,1k авторов , 9,6k публикаций. HTML автора , публикаций. CSS авторов , 1,2k публикаций. Разработка под Linux авторов , публикаций. Добавить в закладки Горьков Алексей GORKOFF карма. Как раз получается около 6 мб. Добавили бы ещё алгоритмы на основе вейвлет преобразований JPEG Статья полезная, но несколько сумбурная. Я с удовольствием напишу про вейвлеты, но мне кажется, что эта тема заслуживает отдельного топика, а возможно даже нескольких. Вот спасибо, а я думал, что мне для описания стеганографического метода Коха-Жао прийдётся начинать писать статью о JPEG. А зачем такой зигзаг обход? Вроде бы в этом случае соседние отсчеты будут слабокррелируемы — а значит сигнал станет более подобен шуму — что должно только отрицательно сказываться на сжатии. При использовании ДКП, после квантинизации его коэффициентов у нас получается матрица, у который бОльшие элементы сосредоточены в верхнем левом углу, а нули в нижнем правом. Зигзаг позволяет ранжировать эти величины по убыванию, что положительно сказывается на дальнейшей обработки этих коэффициентов RLE алгоритмом. Зигзаг позволяет ранжировать эти величины по убыванию, что положительно сказывается на дальнейшей обработке этих коэффициентов RLE алгоритмом. Почему-то мой комментарий не опубликовался, дублирую. Реально зигзагом обхдят не само изображение, а после DCT. Вообще, как я понял, такой порядок выбрали для оптимизации под процессоры. Форматирование нда… Я так понял, чем понятнее метод, тем более подробно он расписан. Сумбурно как-то, да и многовато для одного поста. Я для всеобъемлющего же обзора неполно, неохвачены другие подходы. Ни одной ссылки на литературу, одна иллюстрация — тоже никуда не годится. Но за старание спасибо. Метки лучше разделять запятой. Сейчас Вчера Неделя ядерный CPU, а я не могу сдвинуть курсор 5,8k Первая российская материнская плата массового сегмента 22,2k Интересные публикации Хабрахабр Geektimes. Как я боролся с комарами. Личный опыт и тесты на себе GT. Neuralink — Будущее, которое сложно себе представить. Вы будете его частью GT. Как запутать аналитика — 5. Linux все еще не торт. Почему нет русского Amazon, или где зарыта? Мифы, которые надо закрыть. Китай заблокирует VPN для частных лиц GT. Как пенсионный фонд сливает персональные данные GT. Разделы Публикации Хабы Компании Пользователи Песочница. Информация О сайте Правила Помощь Соглашение Конфиденциальность. Услуги Реклама Тарифы Контент Семинары.
https://gist.github.com/e291b04d82e7dec41790cd49c2485a8e
https://gist.github.com/634301d60f63d74d278d273d261e3596
https://gist.github.com/4fed19dfdedbe903eaba3501ca29261b