закодируйте с помощью шестнадцатеричного кода рисунок

Урок 9
Кодирование рисунков
§ 12. Кодирование рисунков: растровый метод
§ 13. Кодирование рисунков: другие методы

Содержание урока

§ 12. Кодирование рисунков: растровый метод

Что такое растровое кодирование?

§ 13. Кодирование рисунков: другие методы

§ 12. Кодирование рисунков: растровый метод

Что такое растровое кодирование?

Ключевые слова:

• растр
• пиксель
• разрешение
• цветовая модель RGB
• цветовая модель CMYK
• цветовая модель HSB
• глубина цвета
• цветовая палитра

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

И линия, и область состоят из бесконечного числа точек. Цвет каждой из этих точек нам нужно как-то закодировать. Так как точек бесконечно много, для этого нужно бесконечно много памяти, поэтому таким способом изображение закодировать не удастся. Однако «поточечную» идею всё-таки можно использовать.

Начнём с чёрно-белого рисунка. Представим себе, что на изображение ромба наложена сетка, которая разбивает его на квадратики. Такая сетка называется растром. Теперь каждый квадратик внутри ромба зальём чёрным цветом, а каждый квадратик вне ромба — белым. Для тех квадратиков, в которых часть оказалась закрашена чёрным цветом, а часть — белым, выберем цвет в зависимости от того, какая часть (чёрная или белая) больше (рис. 2.19).

У нас получился растровый рисунок, состоящий из квадратиков-пикселей.

Пиксель (англ. pixel: picture element — элемент рисунка) — это наименьший элемент рисунка, для которого можно задать свой цвет.

Разбив рисунок на квадратики, мы выполнили его дискретизацию. Действительно, у нас был непрерывный рисунок — изображение ромба. В результате мы получили дискретный объект — набор пикселей.

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

1) кодируем белые пиксели нулями, а чёрные — единицами 1) ;
2) выписываем строки полученной таблицы одну за другой.

1) Можно сделать и наоборот, чёрные пиксели обозначить нулями, а белые — единицами.

Покажем это на простом примере (рис. 2.20).

Ширина этого рисунка — 8 пикселей, поэтому каждая строка таблицы состоит из 8 двоичных разрядов — битов. Чтобы не писать очень длинную цепочку нулей и единиц, удобно использовать шестнадцатеричную систему счисления, закодировав 4 соседних бита (тетраду) одной шестнадцатеричной цифрой. Например, для первой строки получаем код 1А₁₆:

а для всего рисунка: 1A2642FF425A5A7E₁₆.

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

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

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

Разрешение обычно измеряется в пикселях на дюйм (используется английское обозначение ppi: — pixels per inch). Например, разрешение 254 ppi означает, что на дюйм приходится 254 пикселя.

Чем больше разрешение, тем точнее кодируется рисунок (меньше информации теряется), однако одновременно растёт и объём файла.

Одна и та же картинка была отсканирована дважды: в первый раз с разрешением 300 ppi, а второй раз — с разрешением 600 ppi. Что можно сказать о размерах полученных файлов?

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

1) ввод с помощью какого-либо устройства, например сканера, цифрового фотоаппарата или веб-камеры; напомним, что при сканировании происходит преобразование информации в компьютерные данные (оцифровка);

2) создание рисунка с помощью какой-либо программы.

Используя дополнительные источники, найдите ответы на вопросы.

— Чему равен один дюйм в миллиметрах?
— Если отсканировать рисунок с разрешением 254 ppi, какой размер будет иметь изображение одного пикселя?
— Какие размеры в пикселях будет иметь изображение рисунка размером 10 х 15 см, если отсканировать его с разрешением 254 ppi?

Следующая страница Как кодируется цвет?

Cкачать материалы урока

Источник

Декодирование JPEG для чайников

[FF D8]

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

Специально взял рисунок поменьше. Это знакомый, но сильно пережатый favicon Гугла:

Последующее описание упрощено, и приведенная информация не полная, но зато потом будет легко понять спецификацию.

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

[FF D8] — маркер начала. Он всегда находится в начале всех jpg-файлов.

Следом идут байты [FF FE]. Это маркер, означающий начало секции с комментарием. Следующие 2 байта [00 04] — длина секции (включая эти 2 байта). Значит в следующих двух [3A 29] — сам комментарий. Это коды символов «:» и «)», т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.

Немного теории

Закодированные данные располагаются поочередно, небольшими частями:

Каждый блок Y_ij, Cb_ij, Cr_ij — это матрица коэффициентов ДКП (так же 8×8), закодированная кодами Хаффмана. В файле они располагаются в таком порядке: Y₀₀Y₁₀Y₀₁Y₁₁Cb₀₀Cr₀₀Y₂₀.

Чтение файла

Файл поделен на секторы, предваряемые маркерами. Маркеры имеют длину 2 байта, причем первый байт [FF]. Почти все секторы хранят свою длину в следующих 2 байта после маркера. Для удобства подсветим маркеры:

Маркер [FF DB]: DQT — таблица квантования

Оставшимися 64-мя байтами нужно заполнить таблицу 8×8.

Приглядитесь, в каком порядке заполнены значения таблицы. Этот порядок называется zigzag order:

Маркер [FF C0]: SOF0 — Baseline DCT

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

Находим H_max=2 и V_max=2. Канал i будет прорежен в H_max/H_i раз по горизонтали и V_max/V_i раз по вертикали.

Маркер [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.

Обратное дискретно-косинусное преобразование

Формула не должна доставить сложностей. S_vu — наша полученная матрица коэффициентов. u — столбец, v — строка. C_x = 1/√2 для x = 0, а в остальных случаях = 1. s_yx — непосредственно значения каналов.

Приведу результат вычисления только первой матрицы канала 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, поэтому вряд ли смогу ответить на все вопросы. Просто когда я писал свой декодер, мне часто приходилось сталкиваться с различными непонятными проблемами. И когда изображение выводилось некорректно, я не знал где допустил ошибку. Может неправильно проинтерпретировал биты, а может неправильно использовал ДКП. Очень не хватало пошагового примера, поэтому, надеюсь, эта статья поможет при написании декодера. Думаю, она покрывает описание базового метода, но все-равно нельзя обойтись только ей. Предлагаю вам ссылки, которые помогли мне:

Источник

Алгоритм RLE

Алгоритм RLE

1. Используя алгоритм RLE, закодируйте последовательность символов

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

66.67 % коэффициент сжатия, MAAAAAAAAAAAAAAMAAAAAAAAAAAAAA

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

4. Проверьте результат, полученный в предыдущем пункте, с помощью программы RLE. Предложите два способа проверки.

1.Сжатие без потерь и 2. сжатие с потерей

5. Постройте последовательности, которые сжимаются алгоритмом RLE ровно в 2 раза, в 4 раза, в 5 раз. Проверьте свои ответы с помощью программы RLE.

6. Придумайте три последовательности, которые невозможно сжать с помощью алгоритма RLE:

7. Используя программу RLE, примените RLE-сжатие к следующим файлам и найдите для каждого из них коэффициент сжатия:

Размер после сжатия

8. Объясните результаты, полученные в предыдущем пункте:

· почему не удается сжать рисунки в формате JPEG?

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

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

9. Оцените максимально достижимый коэффициент сжатия с помощью рассмотренного в учебнике варианта RLE-алгоритма. В каком случае его удастся достичь?

Максимальное значение при одной длинной серии, минимальное при отсутствии серий

10. Оцените коэффициент сжатия с помощью RLE-алгоритма в худшем случае. Опишите этот худший случай.

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

Источник

Кодирование растровых рисунков

Содержимое разработки

Тема: «Кодирование рисунков: растровый метод»

Тип урока: повторительно-обобщающий с выходом на получение новых знаний.

Цели урока:
— систематизировать представления учащихся о растровой графике.
— помочь научится правильно выбирать формат (способ представления) графических файлов в зависимости от решаемой задачи;
— развитие познавательных интересов, навыков работы с графическим редактором.
— воспитывать внимательность, аккуратность, интерес к предмету.

Оборудование:
интерактивная доска (экран), компьютер, компьютерная презентация, тесты, светодиодная лента (rgb).

План урока:
I. Орг. момент. (1 мин)
II. Проверка и актуализация знаний. (12 мин)
III. Теоретическая часть. (15 мин)
IV. Практическая часть. (7 мин)
V. Д/з (1 мин)
VI. Вопросы учеников. (2 мин)
VII. Итог урока. (2 мин)

Приветствие, проверка присутствующих. Объяснение хода урока.

II. Актуализация знаний.

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

Язык, «понятный» компьютеру – это нули и единицы. Это значит, что все типы данных хранятся, обрабатываются и передаются как цепочки нулей и единиц. Говорят, что они закодированы с помощью двоичного кода. Двоичный код – это код, в котором используются только два знака (обычно – 0 и 1).

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

Учащиеся выполняют тест на компьютерах.

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

С помощью игры «Поле чудес» учащиеся вспоминают:

О кодировании какого вида информации мы будем говорить сегодня?

III. Теоретическая часть.

Вы уже работали с графическими редакторами и видели, что получается, если очень сильно увеличить рисунок:

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

Как преобразовать «обычный» рисунок в растровый?

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

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

Разбив «обычный» рисунок на квадратики, мы выполнили его дискретизацию – разделили единый объект на отдельные элементы. Действительно, у нас был единый рисунок – изображение ромба. В результаты мы получили дискретный объект – набор пикселей.

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

Чаще всего для преобразования «обычных» рисунков в растровые мы используем сканер.

Разрешающая способность (разрешение) сканера – это наибольшее количество точек на единицу длины, которые способен различить сканер.

Разрешение обычно измеряется в пикселях на дюйм (используется английское обозначение ppi = pixels per inch). Чем больше разрешение, тем точнее кодируется рисунок (меньше информации теряется), однако одновременно растет и объем файла.

Учащиеся решают задачи:

Размер растрового изображения 20 на 15 пикселей. Из какого количества пикселей состоит это изображение?
Размер растрового изображения 800 на 600 пикселей. Из какого количества пикселей состоит это изображение?
Размер растрового изображения 2592 на 1944 пикселей. Из какого количества пикселей состоит это изображение?

Как же получить двоичный код рисунка, состоящего из пикселей-квадратиков?

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

• заменяем белые пиксели нулями, а черные – единицами;
• выписываем строки полученной таблицы одну за другой.

Закодируйте рисунок двоичным кодом (учащиеся выполняю кодирование):

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

Запишите результат в шестнадцатеричном виде (учащиеся переводят двоичной код в шестнадцатеричную запись).

А теперь решите обратную задачу: нарисуйте в тетрадях закодированный рисунок.

«Постройте черно-белый рисунок размером 8 на 8 пикселей, закодированный шестнадцатеричной последовательностью 00707F7E5EDE9212».

Учащиеся строят рисунок.

Компьютерные изображения «превращают» в «обычные» бумажные с помощью принтера. Одна из важных характеристик принтера – это разрешение.

Разрешающая способность (разрешение) принтера — это максимальное количество точек, которые он способен напечатать на единицу длины.

Учащиеся решают задачу:

Какой размер в пикселях должен иметь закодированный рисунок с разрешением 300 ppi, чтобы с него можно было напечатать фотографию размером 10×15 см?

Как закодировать рисунок, содержащей оттенки серого цвета?

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

«Сколько нужно бит для кодирования цвета одного пикселя, если рисунок содержит …. оттенков серого?»

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

Как же кодируется цвет?

По современной теории цветного зрения, глаз человека содержит чувствительные элементы трёх типов. Элементы первого типа лучше всего чувствуют красный цвет, элементы второго типа – зелёный, а элементы третьего типа – оттенки синего цвета. Цвет, который мы видим, получается как результат сложения сигналов от всех чувствительных элементов. Поэтому считается, что любой цвет (то есть ощущения человека) можно имитировать, используя только три световых луча (красный, зелёный и синий) разной яркости. Эта модель цвета называется моделью RGB по начальным буквам английских слов Red (красный), Green (зелёный) и Blue (синий).

Подобным образом работает светодиодная RGB лента, которая часто применяется в отделке интерьера дома. Учитель демонстрирует работу ленты.

Существует очень много различных форматов файлов для хранения изображений. Чаще всего мы встречаемся с такими форматами:

III. Практическая часть.

У нас есть рисунок веселого паровозика с вагончиками. Давайте раскрасим его. Для каждой области дан RGB код цвета. Но, чтобы выполнить задание полностью, вам потребуется еще вспомнить двоичную систему счисления (на рисунке код в 10-й, в таблице к заданию в 2-й системе счисления, строки начиная с 6-й перепутаны).

Далее учащиеся самостоятельно выполняют задание на компьютерах.

1) Постройте черно-белый рисунок шириной 16 пикселей, закодированный шестнадцатеричной последовательностью 0018810CC306FF03DB03FF03FFFE7EFE18C600C601CE01CE

2) Творческое:
Нарисуйте свой черно-белый рисунок шириной 8 или 16 пикселей, закодируйте его шестнадцатеричной последовательностью.

V. Вопросы учеников.
Ответы на вопросы учащихся.

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

Источник