что такое кодирование и декодирование изображения
DataGlyphs — кодирование информации в изображении
Исследовательский центр в Пало-Альто (Palo Alto Research Center — PARC), филиал знаменитой американской корпорации Xerox, разработал систему, которая позволяет совместить бумажные документы, предназначенные для людей, с машинным чтением, обладающую ошеломляющим преимуществом над прежними принципами кодировки.
Система называется «ДатаГлифы» (DataGlyphs).
Данные кодируются в виде множества диагональных штрихов (создатели технологии назвали их глифами), каждый из которых соответствует одному биту. Значение бита зависит от направления глифа.
Если оборудование, на котором печатается документ, имеет достаточно высокое разрешение, размеры глифов будут очень малы — не больше сотых долей дюйма. Благодаря этому, на крохотном участке страницы можно уместить сотни байтов цифровых данных. Впоследствии, отсканировав документ, эти данные можно извлечь и раскодировать.
Каждый «ДатаГлиф» (то есть — штрихкод нового типа) содержит решётку синхронизации — регулярный повтор одного и того же набора глифов, который и отмечает границы напечатанной информации и повышает надёжность чтения, благодаря избыточности кодирования.
Даже при уровне избыточности кодирования почти в 30%, по сравнению с самым распространённым стандартом штрихкодов — code39 (без дублирования информации) — новый тип кодирования обеспечивает почти в двадцать раз большую плотность упаковки данных: примерно 155 байт на квадратный сантиметр (при печати на принтере с разрешением 600 точек на дюйм).
И даже в сравнении со стандартом pdf417 — самым совершенным штрихкодом из прежних систем — разница составляет 1,8 раз (в пользу DataGlyphs).
Пользуясь вариацией в толщине соседних глифов и в их цвете, глифами можно напечатать чёрно-белое или цветное изображение, «глифовая» структура которого будет незаметна на глаз (как мы не видим точки разного диаметра при печати фотографий в газете).
Рассуждая дальше, из глифов можно делать серенький фон на текстовых документах, содержащий в себе сам документ в цифровом виде. Эта технология двусторонней печати одного и того же документа (одна сторона «буковками» — для людей, вторая «глифами» — для машин), назван разработчиками GlyphSeal, ему прочат больше будущее. Ведь теперь не нужно будет никаких программ распознавания напечатанных символов для сканирования, скажем факса.
На одной из презентаций разработчики представили прототип сканера, представляющий из себя прозрачную поверхность, на которой, если расположить сканнер над закодированным участком, выводиться закодированная информация.
Что такое кодирование и декодирование изображения
В процессах восприятия, передачи и хранения информации живыми организмами, человеком и техническими устройствами происходит кодирование информации. В этом случае информация, представленная в одной знаковой системе, преобразуется в другую. Каждый символ исходного алфавита представляется конечной последовательностью символов кодового алфавита. Эта результирующая последовательность называется информационным кодом (кодовым словом, или просто кодом).
Примерами кодов являются последовательность букв в тексте, цифр в числе, двоичный компьютерный код и др.
Код состоит из определенного количества знаков (имеет определенную длину), которое называется длиной кода. Например, текстовое сообщение состоит из определенного количества букв, число — из определенного количества цифр.
Преобразование знаков или групп знаков одной знаковой системы в знаки или группы знаков другой знаковой системы называется перекодированием.
При кодировании один символ исходного сообщения может заменяться одним или несколькими символами нового кода, и наоборот — несколько символов исходного сообщения могут быть заменены одним символом в новом коде. Примером такой замены служат китайские иероглифы, которые обозначают целые слова и понятия.
Кодирование может быть равномерным и неравномерным. При равномерном кодировании все символы заменяются кодами равной длины; при неравномерном кодировании разные символы могут кодироваться кодами разной длины (это затрудняет декодирование). Неравномерный код называют еще кодом переменной длины.
Примером неравномерного кодирования является код азбуки Морзе. Длительное время он использовался для передачи сообщений по телеграфу. Кодовый алфавит включал точку, тире и паузу. При передаче по телеграфу точка означала кратковременный сигнал, тире — сигнал в 3 раза длиннее. Между сигналами букв одного слова делалась пауза длительностью одной точки, между словами — длительностью трех точек, между предложениями — длительностью семи точек.
Вначале код Морзе был создан для букв английского алфавита, цифр и знаков препинания. Принцип этого кода заключался в том, что часто встречающиеся буквы кодировались более простыми сочетаниями точек и тире. Это делало код компактным. Позже код был разработан и для символов других алфавитов, включая русский.
Коды Морзе для некоторых букв.
Чтобы избежать неоднозначности, код Морзе включает также паузы между кодами разных символов.
Декодирование информации
В зависимости от системы кодирования информационный код может или не может быть декодирован однозначно. Равномерные коды всегда могут быть декодированы однозначно.
Для однозначного декодирования неравномерного кода важно, имеются ли в нем кодовые слова, которые являются одновременно началом других, более длинных кодовых слов.
Закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова.
Закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.
Неравномерные коды, для которых выполняется условие Фано, называются префиксными. Префиксный код — такой неравномерный код, в котором ни одно кодовое слово не является началом другого, более длинного слова. В таком случае кодовые слова можно записывать друг за другом без разделительного символа между ними.
Например, код Морзе не является префиксным — для него не выполняется условие Фано. Поэтому в кодовый алфавит Морзе, кроме точки и тире, входит также символ–разделитель — пауза длиной в тире. Без разделителя однозначно декодировать код Морзе в общем случае нельзя.
Конспект урока по информатике «Кодирование и декодирование информации».
Кодирование и декодирование изображений Base64 с помощью Python
Допустим, вам нужно передать по сети бинарный графический файл.
Когда вы это сделаете, вы с удивлением обнаружите, что файл был неправильно принят на другом конце, и что он содержит странные символы. Это происходит потому, что вы пытаетесь отправить файл в формате байтов, в то время как используемый канал предназначен для передачи текста.
Каким должно быть решение, чтобы избежать такой проблемы?
Ответ кроется в кодировке Base64. В этой статье я собираюсь показать, как мы можем использовать Python для кодирования и декодирования двоичного изображения.
Программа, которую мы сегодня создадим, предполагает использование в качестве автономной локальной программы, но вы можете применять ее для различных концепций, таких как отправка закодированного изображения с мобильного устройства на сервер, и многих других приложений.
Что такое кодирование Base64?
Прежде чем перейти к этому, давайте определим, что мы подразумеваем под Base64.
Base64 – это способ, с помощью которого 8-битные двоичные данные кодируются в формат, который можно представить в 7 битах. Для этого используются только символы A-Z, a-z, 0-9, + и / для представления данных. Символ = используется для данных прокладок. Например, при таком кодировании три 8-битных байта превращаются в четыре 7-битных байта.
Термин base 64 происходит от стандарта Multipurpose Internet Mail Extensions (MIME), который широко используется для HTTP и XML, и изначально был разработан для кодирования вложений электронной почты и их правильной передачи.
Для чего мы используем Base64?
Base64 очень важен для отображения двоичных данных, настолько, что позволяет представлять двоичные данные так, что они выглядят и ведут себя как обычный текст. Это делает более безопасным их хранение в базах данных, отправку по электронной почте или использование в текстовых форматах, таких как XML.
Base64 в основном используется для представления данных в формате ASCII.
Как мы уже говорили во введении к этой статье, без Base64 данные вообще не могут быть прочитаны.
Кодирование Base64
Кодирование Base64 – это процесс преобразования двоичных данных в набор символов, ограниченный 64 символами. Как мы уже говорили в первом разделе, это символы A-Z, a-z, 0-9, + и / (Вы посчитали их? Вы заметили, что в сумме они составляют 64?). Этот набор символов считается наиболее распространенным и известен как Base64 в MIME. Он использует A-Z, a-z, 0-9, + и / для первых 62 значений и + и / для последних двух значений.
Закодированные в Base64 данные в итоге оказываются больше исходных данных, поэтому, как мы уже говорили, на каждые 3 байта двоичных данных приходится как минимум 4 байта закодированных в Base64 данных. Это связано с тем, что вы сжимаете данные в меньший набор символов.
Вы когда-нибудь видели необработанный файл электронной почты, подобный тому, который показан ниже? Если да, то вы видели кодирование Base64 в действии.
Кодирование Base64 выполняется в несколько этапов:
Декодирование Base64
Декодирование Base64 противоположно кодированию Base64. Другими словами, это делается путем обратных действий, описанных в предыдущем пункте.
Таким образом, этапы декодирования Base64 можно описать следующим образом:
Кодирование изображения
Теперь перейдем к сути дела. В этом разделе я покажу вам, как мы можем легко закодировать изображение в Base64 с помощью Python. Для этого я собираюсь использовать следующий двоичный образ. (Имя файла изображения – deer.gif).
Первое, что нам нужно сделать, чтобы использовать Base64 в Python, – это импортировать модуль Base64:
Для кодирования нашего изображения в Base64 нужно сделать следующее:
Если вы хотите увидеть результат процесса кодирования, введите следующее:
Декодирование изображения
Чтобы декодировать изображение с помощью Python, мы просто используем функцию base64.decodestring(s).
Таким образом, чтобы декодировать изображение, которое мы закодировали в предыдущем разделе, делаем следующее:
Собираем все вместе
Давайте соберем код, которая кодирует и декодирует изображение Base64.
Похожие записи
Если вам нужно скопировать файл с помощью Python, но вы не знаете, как это сделать,…
Иногда нам нужно преобразовать Excel или CSV в другой формат, в этот раз мне нужно…
Декодирование JPEG для чайников
[FF D8]
Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся! Прогревайте ваш любимый компилятор и hex-редактор, будем декодировать это:
Специально взял рисунок поменьше. Это знакомый, но сильно пережатый favicon Гугла: 
Последующее описание упрощено, и приведенная информация не полная, но зато потом будет легко понять спецификацию.
Даже не зная, как происходит кодирование, мы уже можем кое-что извлечь из файла.
[FF D8] — маркер начала. Он всегда находится в начале всех jpg-файлов.
Следом идут байты [FF FE]. Это маркер, означающий начало секции с комментарием. Следующие 2 байта [00 04] — длина секции (включая эти 2 байта). Значит в следующих двух [3A 29] — сам комментарий. Это коды символов «:» и «)», т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.
Немного теории
Закодированные данные располагаются поочередно, небольшими частями:
Каждый блок Yij, Cbij, Crij — это матрица коэффициентов ДКП (так же 8×8), закодированная кодами Хаффмана. В файле они располагаются в таком порядке: Y00Y10Y01Y11Cb00Cr00Y20.
Чтение файла
Файл поделен на секторы, предваряемые маркерами. Маркеры имеют длину 2 байта, причем первый байт [FF]. Почти все секторы хранят свою длину в следующих 2 байта после маркера. Для удобства подсветим маркеры:
Маркер [FF DB]: DQT — таблица квантования
Оставшимися 64-мя байтами нужно заполнить таблицу 8×8.
Приглядитесь, в каком порядке заполнены значения таблицы. Этот порядок называется zigzag order:
Маркер [FF C0]: SOF0 — Baseline DCT
Этот маркер называется SOF0, и означает, что изображение закодировано базовым методом. Он очень распространен. Но в интернете не менее популярен знакомый вам progressive-метод, когда сначала загружается изображение с низким разрешением, а потом и нормальная картинка. Это позволяет понять что там изображено, не дожидаясь полной загрузки. Спецификация определяет еще несколько, как мне кажется, не очень распространенных методов.
Находим Hmax=2 и Vmax=2. Канал i будет прорежен в Hmax/Hi раз по горизонтали и Vmax/Vi раз по вертикали.
Маркер [FF C4]: DHT (таблица Хаффмана)
Эта секция хранит коды и значения, полученные кодированием Хаффмана.
Следующие 16 значений:
Количество кодов означает количество кодов такой длины. Обратите внимание, что секция хранит только длины кодов, а не сами коды. Мы должны найти коды сами. Итак, у нас есть один код длины 1 и один — длины 2. Итого 2 кода, больше кодов в этой таблице нет.
С каждым кодом сопоставлено значение, в файле они перечислены следом. Значения однобайтовые, поэтому читаем 2 байта:
Далее в файле можно видеть еще 3 маркера [FF C4], я пропущу разбор соответствующих секций, он аналогичен вышеприведенному.
Построение дерева кодов Хаффмана
Мы должны построить бинарное дерево по таблице, которую мы получили в секции DHT. А уже по этому дереву мы узнаем каждый код. Значения добавляем в том порядке, в каком указаны в таблице. Алгоритм прост: в каком бы узле мы ни находились, всегда пытаемся добавить значение в левую ветвь. А если она занята, то в правую. А если и там нет места, то возвращаемся на уровень выше, и пробуем оттуда. Остановиться нужно на уровне равном длине кода. Левым ветвям соответствует значение 0, правым — 1.
Деревья для всех таблиц этого примера:
В кружках — значения кодов, под кружками — сами коды (поясню, что мы получили их, пройдя путь от вершины до каждого узла). Именно такими кодами закодировано само содержимое рисунка.
Маркер [FF DA]: SOS (Start of Scan)
Байт [DA] в маркере означает — «ДА! Наконец-то то мы перешли к финальной секции!». Однако секция символично называется SOS.
[00], [3F], [00] — Start of spectral or predictor selection, End of spectral selection, Successive approximation bit position. Эти значения используются только для прогрессивного режима, что выходит за рамки статьи.
Отсюда и до конца (маркера [FF D9]) закодированные данные.
Закодированные данные
Последующие значения нужно рассматривать как битовый поток. Первых 33 бит будет достаточно, чтобы построить первую таблицу коэффициентов:
Нахождение DC-коэффициента
1) Читаем последовательность битов (если встретим 2 байта [FF 00], то это не маркер, а просто байт [FF]). После каждого бита сдвигаемся по дереву Хаффмана (с соответствующим идентификатором) по ветви 0 или 1, в зависимости от прочитанного бита. Останавливаемся, если оказались в конечном узле.
2) Берем значение узла. Если оно равно 0, то коэффициент равен 0, записываем в таблицу и переходим к чтению других коэффициентов. В нашем случае — 02. Это значение — длина коэффициента в битах. Т. е. читаем следующие 2 бита, это и будет коэффициент:
Нахождение AC-коэффициентов
1) Аналогичен п. 1, нахождения DC коэффициента. Продолжаем читать последовательность:
2) Берем значение узла. Если оно равно 0, это означает, что оставшиеся значения матрицы нужно заполнить нулями. Дальше закодирована уже следующая матрица. В нашем случае значение узла: 0x31.
Читать AC-коэффициенты нужно пока не наткнемся на нулевое значение кода, либо пока не заполнится матрица.
В нашем случае мы получим:
Вы заметили, что значения заполнены в том же зигзагообразном порядке? Причина использования такого порядка простая — так как чем больше значения v и u, тем меньшей значимостью обладает коэффициент Svu в дискретно-косинусном преобразовании. Поэтому, при высоких степенях сжатия малозначащие коэффициенты обнуляют, тем самым уменьшая размер файла.
Аналогично получаем еще 3 матрицы Y-канала…
Но! Закодированные DC-коэффициенты — это не сами DC-коэффициенты, а их разности между коэффициентами предыдущей таблицы (того же канала)! Нужно поправить матрицы:
Теперь порядок. Это правило действует до конца файла.
… и по матрице для Cb и Cr:
Вычисления
Квантование
Вы помните, что матрица проходит этап квантования? Элементы матрицы нужно почленно перемножить с элементами матрицы квантования. Осталось выбрать нужную. Сначала мы просканировали первый канал. Он использует матрицу квантования 0 (у нас она первая из двух). Итак, после перемножения получаем 4 матрицы Y-канала:
… и по матрице для Cb и Cr.
Обратное дискретно-косинусное преобразование
Формула не должна доставить сложностей. Svu — наша полученная матрица коэффициентов. u — столбец, v — строка. Cx = 1/√2 для x = 0, а в остальных случаях = 1. syx — непосредственно значения каналов.
Приведу результат вычисления только первой матрицы канала Y (после обязательного округления):
Ко всем полученным значениям нужно прибавить по 128, а затем ограничить их диапазон от 0 до 255:
Например: 138 → 266 → 255, 92 → 220 → 220 и т. д.
YCbCr в RGB
4 матрицы Y, и по одной Cb и Cr, так как мы прореживали каналы и 4 пикселям Y соответствует по одному Cb и Cr. Поэтому вычислять так: YCbCrToRGB(Y[y,x], Cb[y/2, x/2], Cr[y/2, x/2]):
Вот полученные таблицы для каналов R, G, B для левого верхнего квадрата 8×8 нашего примера:
Конец
Вообще я не специалист по JPEG, поэтому вряд ли смогу ответить на все вопросы. Просто когда я писал свой декодер, мне часто приходилось сталкиваться с различными непонятными проблемами. И когда изображение выводилось некорректно, я не знал где допустил ошибку. Может неправильно проинтерпретировал биты, а может неправильно использовал ДКП. Очень не хватало пошагового примера, поэтому, надеюсь, эта статья поможет при написании декодера. Думаю, она покрывает описание базового метода, но все-равно нельзя обойтись только ей. Предлагаю вам ссылки, которые помогли мне:
Кодирование для чайников, ч.1
Не являясь специалистом в обозначенной области я, тем не менее, прочитал много специализированной литературы для знакомства с предметом и прорываясь через тернии к звёздам набил, на начальных этапах, немало шишек. При всём изобилии информации мне не удалось найти простые статьи о кодировании как таковом, вне рамок специальной литературы (так сказать без формул и с картинками).
Статья, в первой части, является ликбезом по кодированию как таковому с примерами манипуляций с битовыми кодами, а во второй я бы хотел затронуть простейшие способы кодирования изображений.
0. Начало
Давайте рассмотрим некоторые более подробно.
1.1 Речь, мимика, жесты
1.2 Чередующиеся сигналы
В примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы «включено/выключено». Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.
1.3 Контекст
2. Кодирование текста
Текст в компьютере является частью 256 символов, для каждого отводится один байт и в качестве кода могут быть использованы значения от 0 до 255. Так как данные в ПК представлены в двоичной системе счисления, то один байт (в значении ноль) равен записи 00000000, а 255 как 11111111. Чтение такого представления числа происходит справа налево, то есть один будет записано как 00000001.
Итак, символов английского алфавита 26 для верхнего и 26 для нижнего регистра, 10 цифр. Так же есть знаки препинания и другие символы, но для экспериментов мы будем использовать только прописные буквы (верхний регистр) и пробел.
Тестовая фраза «ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП».
2.1 Блочное кодирование
Информация в ПК уже представлена в виде блоков по 8 бит, но мы, зная контекст, попробуем представить её в виде блоков меньшего размера. Для этого нам нужно собрать информацию о представленных символах и, на будущее, сразу подсчитаем частоту использования каждого символа: