Работа с изображениями BMP

Данный проект предназначен для работы с изображенями в формате BMP.

Возможности проекта

Проект позволяет выполнять три команды:

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

2. insert: вставить в изображение секретную строчку (это один из вариантов стеганографии), согласно ключу.

3. extract: вытащить из изображения секретную строчку по ключу.

Для сборки проекта в Linux используется Makefile. После сборки появится исполняемый файл hw-01_bmp.

Программа запускается из командной строки следующими командами:

1. Для crop-rotate:

./hw-01_bmp crop-rotate ‹in-bmp› ‹out-bmp› ‹x› ‹y› ‹w› ‹h›

Используемые параметры:

• crop-rotate — обязательный параметр, означающий выполняемое действие.
• in-bmp — имя входного файла с изображением bmp.
• out-bmp — имя выходного файла, куда будет сохранён результат (изображение bmp, являющееся повернутым куском исходного изображения).
• x, y — координаты левого верхнего угла области исходного изображения, которую необходимо вырезать и повернуть. Координаты начинаются с нуля, таким образом (0, 0) — это верхний левый угол.
• w, h — соотвественно, ширина и высота области до поворота.

2. Для insert:

./hw-01_bmp insert ‹in-bmp› ‹out-bmp› ‹key-txt› ‹msg-txt›

Используемые параметры:

• insert — обязательный параметр, означающий выполняемое действие.
• in-bmp — имя входного файла с изображением.
• out-bmp — имя выходного файла, куда будет сохранён результат (изображение с записанным в него сообщением).
• key-txt — тестовый файл с ключом.
• msg-txt — текстовый файл с секретным сообщением.

3. Для extract:

./hw-01_bmp extract ‹in-bmp› ‹key-txt› ‹msg-txt›

Используемые параметры:

• extract — обязательный параметр, означающий выполняемое действие.
• in-bmp — имя входного файла с изображением bmp, в котором записана секретная строчка.
• key-txt — тестовый файл с ключом.
• msg-txt — текстовый файл, куда сохранить секретное сообщение, извлечённое из входного изображения.

Дополнение: в Windows собрать проект с Makefile может не получиться, тогда можно собрать проект вручную с помощью gcc (просто вручную каждый файл .c компилипровать в .o, а потом собрать все .o файлы в единый исполняемый), или ещё проще - можно объединить весь код воедино в файле main.c (для этого можно просто во всеx #include файлы .h заменить на те же файлы .c - это просто подставит весь текст этих файло в main.c (этим и занимается директива #include)) и собрать один этот файл. Так или иначе, в Windows тоже можно собрать проект и получить исполняемый файл hw-01_bmp.exe. Тогда запуск из командной строки будет точно таким же, только вместо ./hw-01_bmp использовать hw-01_bmp.exe.

Замечание: система, на которой запускается проект должна быть little-endian (так как именно так записыаваются биты в bmp-файлах) (для big-endian систем придётся все считанные байты переворачивать).

Описание входных данных

Все изображения (изначальное для чтения и сохранённый результат) хранятся в заданном формате:

• Общий формат — BMP.
• В рамках формата BMP используется формат DIB с заголовком BITMAPINFOHEADER (версия 3).
• Значение поля biHeight (высота изображения) строго больше нуля.
• Используются 24 бита цвета на пиксель (один байт на цветовой канал).
• Палитра (таблица цветов) не используется.
• Сжатие не используется.

Пример изображения, удовлетворяющий этим пунктам, можно найти в папке samples: изображение lena_512.bmp. Также некоторые графические редакторы могут генерировать изображение в нужном формате («24-битное изображение BMP»).

Ключ для вставки/извлечения сообщения в изображении представляет собой текстовый файл, где в каждой строчке находятся два числа (координаты пикселя на изображении) и буква (R, G или B), обозначающая цветовой канал пикселя. Пример ключа находится в папке samples: файл key.txt.

Теоретическая информация

Общая структура BMP

Данные в формате BMP состоят из трёх основных блоков различного размера:

1. Заголовок из структуры BITMAPFILEHEADER и блока BITMAPINFO. Последний содержит:
   • Информационные поля.
   • Битовые маски для извлечения значений цветовых каналов (опциональные).
   • Таблица цветов (опциональная).
2. Цветовой профиль (опциональный).
3. Пиксельные данные.

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

BITMAPFILEHEADER

BITMAPFILEHEADER — 14-байтная структура, которая располагается в самом начале файла. Эта структура содержит различные поля с общей информацией о bmp-файле.

BITMAPFILEHEADER очень удобно записать в коде C такой структурой (имена, количество и размер (занимаемой памяти) полей в структуре далее полностью совпадает с тем, что записано в BITMAPFILEHEADER в реальном файле):

typedef struct tagBITMAPFILEHEADER {
    uint16_t bfType;
    uint32_t bfSize;
    uint16_t bfReserved1;
    uint16_t bfReserved2;
    uint32_t bfOffBits;
} BITMAPFILEHEADER;

(typedef нужен, чтобы имя структуры было не длинное "struct tagBITMAPFILEHEADER", а удобное "BITMAPFILEHEADER")

Нужно понимать, что реальный bmp-файл (как и любой другой файл) - это просто очень много подряд записанных байт информации. Просто первые 14 из этих байт, согласно документации формата BMP, обозначают заголовок, который является структурой. Под струткурой имеется в виду то, что эти 14 байт разбиваются на несколько кусочков - полей. Каждое поле структуры занимает несколько байт, в которых записана некоторая информация. Так вот согласно документации, в заголовке 5 полей: первое занимает 2 байта (=16 битов), второе 4 байта, далее два поля по 2 байта и снова поле из 4 байтов (а все вместе эти поля, записаннные подряд, как раз и дают 14 байт заголовка... то есть эти слова "поле" и "заголовок" - это лишь обозначение для нескольких байт из тысячи, которой является bmp-файл). Так вот написанная структура для C как раз в точности повторяют структуру заголовка.

Важное замечание, что в реальном bmp-файле поля струткур расположены подряд друг за другом, без выравнивания! Поэтому, мы также можем отключить выравнивание при создании структур в коде C (просто #pragma pack(1) пишем перед созданием "struct tagBITMAPFILEHEADER"). Это позволит очень удобно считывать всю структуру из файла одной операцией чтения:

BITMAPFILEHEADER header;  // создали заголовок
fseek(bmp_file, 0, SEEK_SET);  // переходим в начало bmp_file (в котором находится изображение)
fread(&header, 14, 1, bmp_file);  // считали заголовок (первые 14 байт файла) одной операцией чтения

/*
Итак:
1. Первые 14 байт файла занимает заголовок
2. При этом мы создали струткуру BITMAPFILEHEADER, поля которой идут в том же порядке и имеют тот же размер, что и в реальном заголовке в файле
3. Также у нас отключено выравнивание, а значит все поля структуры BITMAPFILEHEADER (также как и поля в реальном заголовке в файла) идут подряд и суммарно занимают как раз 14 байт.

Поэтому после одной операции чтения, мы считаем 14 байт заголовка в созданный нами header, а все поля этой структуры совпадут с полями заголовка, то есть примут как раз те значения, которые и записаны в файле. Очень удобно так считывать.
*/

Каждое из 5 полей заголовка содержит некоторую информацию, а именно:

• bfType - отметка для отличия формата от других.
• bfSize - размер файла в байтах.
• bfReserved1 - зарезервировано и должно содержать 0.
• bfReserved2 - зарезервировано и должно содержать 0.
• bfOffBits - положение пиксельных данных относительно начала файла (количество байт).

BITMAPINFO

BITMAPINFO в файле идёт сразу за BITMAPFILEHEADER и состоит из 3 частей:

1. Структура с информационными полями.
2. Битовые маски для извлечения значений цветовых каналов (присутствуют не всегда).
3. Таблица цветов (присутствует не всегда).

Битовые маски: если битность изображения 16 или 32 (то есть используется 16 или 32 бита для кодировки каждого пикселя), то могут быть указаны 32-битные маски для извлечения цветовых каналов. Это связано с тем, что 16 не кратно трём (ведь у каждого пикселя три цветовых канала - R, G и B) и поэтому биты могут быть распределены (между цветовыми каналами) разными способами.

Таблица цветов нужна, когда цвет задаётся не напрямую битами, а как индекс в таблице цветов.

В данной проекте мы работаем с теми BMP, которые не содержит таблицу цветов, а битность изображения 24 (поэтому битовые маски не используются). Поэтому в этом проекте блок BITMAPINFO для нас состоит только из структуры с информационными полями.

Как уже было сказано, данный проект работает с BMP с заголовком версии 3. В данной версии структура в блоке BITMAPINFO называется BITMAPINFOHEADER и занимает 40 байтов.

Эту структуру снова удобно записать в C:

typedef struct tagBITMAPINFO {
    uint32_t biSize;
    uint32_t biWidth;
    uint32_t biHeight;
    uint16_t biPlanes;
    uint16_t biBitCount;
    uint32_t biCompression;
    uint32_t biSizeImage;
    uint32_t biXPelsPerMeter;
    uint32_t biYPelsPerMeter;
    uint32_t biClrUsed;
    uint32_t biClrImportant;
} BITMAPINFO;

Поля обозначают следующее:

• biSize - размер данной структуры в байтах (по её размеру можно понять её версию, но мы и так знаем, что у нас версия 3).
• biWidth - ширина изображения в пикселях, указывается целым числом со знаком (ноль и отрицательные не документированы).
• biHeight - высота изображения в пикселях, указывается целым числом со знаком (ноль не документирован); знак означает порядок следования строк с пикселями изображения в файле (положительный - строки идут, начиная с последней; отрицательный - строки идут, начиная с первой) (в данном проекте мы работаем только с положительной высотой, что значит, что строки идут начиная с последней).
• biPlanes - в BMP только значение 1.
• biBitCount - количество бит на пиксель (в этом проекте мы работаем только с 24-битными изображениями, поэтому в данном поле для данного проекта допустимо только значение 24)
• biCompression - метод сжатия, применённый в данном изображении (в данном проекте работаем с изображениями без сжатия).
• biSizeImage - размер пиксельных данных в байтах, может быть обнулено если хранение осуществляется двумерным массивом.
• biXPelsPerMeter - количество пикселей на метр по горизонтали.
• biXPelsPerMeter - количество пикселей на метр по вертикали.
• biClrUsed - размер таблицы цветов в ячейках.
• biClrImportant - количество ячеек от начала таблицы цветов до последней используемой (включая её саму).

Пиксельные данные

В используемом в этом проекте варианте изображений BMP не используется ни таблица цветов, ни сжатие, ни битовые маски. Поэтому пиксельные данные (то есть данные о цвете каждого пикселя на изображении) выглядят просто как двумерный массив из h строк и w столбцов (h и w - высота и ширина изображения). В этом двумерном массиве каждый элемент в i-ой строке и j-ом столбце представляет из себя 24 подряд идущих бита, в которых записана информация о цвете пикслеля, расположенного на картинке в i-ой строке и j-ом столбце.

Цвет каждого пикселя записывается как смесь трёх цветовых каналов: красного (R), зелёного (G) и синего (B). Суммарно вся эта информация занимает 24 бита, а значит по 8 бит = 1 байт на каждый цветовой канал.

То есть каждый пиксель в коде на C удобно представлять такой структурой:

typedef struct tagPIXEL {
    uint8_t blue;
    uint8_t green;  
    uint8_t red;
} PIXEL;

В этой структуре три поля по 1 байту каждое - для записи каждого цветового канала одного пикселя. Порядок записи цветовых каналов в BMP именно такой: сначала синий, потом зелёный и потом красный.

Таким образом, пиксельные данные - это фактически двумерный массив h на w, где каждый элемент - это просто структура "PIXEL".

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

Но есть особенности. Во первых, каждая строка пиксельного массива должна дополняться нулями до кратного 4 байтам размера! То есть у нас записывается h строк по (24 бита) * w = 3 * w байт в каждой строке. И вот каждая строка в конце должна дополняться нулевыми байтами так, чтобы итоговый рамзер был кратен 4 байтам. Например, если w = 201 пикселей, то каждая строка с пиксельными данными занимает 3 * 201 = 603 байта. Тогда к каждой строке нужно дописать один нулевой байт (чтобы итоговый размер строк стал 603 + 1 = 604 байта - кратно 4 байтам).

Ещё одна особенность - это порядок следования строк пиксельного массива в файле. Можно эти строки записывать начиная с последней, а можно - начиная с первой. То есть в пиксельном массиве h строк, тогда можно в файл записать их начиная с последней (то есть сначала в файл записывается h-1-ая строка, за ней h-2-ая, ..., затем 1-ая строка и в конце 0-ая строка), а можно начиная с первой (сначала записывается 0-ая строка, затем 1-ая, ..., в конце h-1-ая строка) (но строки все слева направо записываются!). Так вот, какой способ использовать указывает знак высоты, находящейся в поле biHeight структуры BITMAPINFOHEADER. Данный проект работает с положительной высотой (то есть строки записываются, начиная с последней). Хотя, если подать на вход изображение с отрицательной высотой, то ничего в проекте не сломается, просто строки пикселей прочитаются в обратном порядке, а значит изображение будет будет отзеркалено...

BMP в данном проекте

Подведём итог по тому, как выглядит bmp-файл, с которым работает данный проект. Используемый нами вариант изображений BMP выглядит так: первые 14 байт файла занимает заголовок BITMAPFILEHEADER, сразу за ним идёт структура BITMAPINFO и занимает 40 байтов. Далее где-то в файле начинается пиксельный массив, который записан по строкам, начиная с последней строки массива.

Стеганография

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

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

Базовые возможности такие: исходное сообщение состоит только из заглавных латинских букв, пробела, точки и запятой. Каждый символ преобразовывается в число от 0 до 28, соответственно (всего 29 различных значений), а число — в пять бит (пять бит позволяют записывать числа от 0 до 2^5-1 = 31), записанных от младших к старшим. Всего сообщение из N символов кодируется при помощи 5N Бит.

Далее мы берём изображение BMP, которое станет носителем сообщения. И каждый из этих 5N бит записывается в самый младший (нулевой) бит какого-то цветового канала какого-то пикселя изображения.

Для передачи сообщения, помимо изображения-носителя, потребуется ключ — текстовый файл, описывающий, в каких пикселях кодируются биты сообщения. В этом файле на каждой строчке записаны три объекта:

• Координаты x и y (0 <= x < w, 0 <= y < h) пикселя, в который надо сохранить соответствующий бит.
• Буква R/G/B обозначающая цветовой канал, в младшем бите которого требуется записать бит сообщения.

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

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

Дополнительные возможности: в коде файла main.c есть два настраиваемых параметра. Первый - это параметр MAX_SIZE_KEY - это максимальное количество строк, которое будет считано из ключа (если используется очень длинный ключ, нужно не забывать менять этот параметр). Второй - это STEGO_BITS_CODE - это количество бит, которым кодируется каждый символ (то есть элемент типа char) сообщения (n бит может принимать 2^n значений, поэтому можно кодировать не более 2^STEGO_BITS_CODE различных символов). По умолчанию он равен 5 (как и говорилось до этого, каждый символ кодируется 5 битами). Но, в принципе, его можно поменять (в общем случае, сообщение из N символов кодируется STEGO_BITS_CODE * N битами), если хочется поддерживать кодирование большего числа символов (для этого придётся поменять функции get_num и get_char в файле stego.c - именно эти функции отвечают за кодировку символа).

Но одна возможность в проекте уже поддерживается: заметим, что символ в C - это элемент типа char и занимает он 8 битов. То есть фактически в C уже есть кодировка символов, которая обеспечивает кодирование каждого символа 8 битами. Это и применено в данном проекте: если установить STEGO_BITS_CODE равным 8, то в качестве кода символа будет использоваться само значение переменной char. И это даёт мощные возможности, так как исходное сообщение просто открывается как бинарный файл и считывается как набор элементов типа char - а потом каждый этот элемент типа char (char занимает 1 байт = 8 бит!) записывается по одному биту в 8 цветовых каналов изображения (согласно ключу) и таким образом кодируется. Но самое интересное то, что нам абсолютно неважно, что именно означал каждый элемент типа char в исходном сообщении: это мог быть просто ASCII символ текстового сообщения, это мог быть кусок символа в другой кодировке (например, буква ы не является ASCII символом, а потому будет кодироваться не одним байтом, а несколькими... то есть, чтобы сохранить букву ы нужно несколько элементов типа char), а мог быть просто кусок в 8 бит какого-то бинарного файла. То есть фишка в том, что сначала исходный файл кусками типа char записывается (команда insert) в изображение, а потом извлекается (команда extract) также кусками типа char воедино. И так можно записать в изображние любой файл. Только нужно помнить, что файлы могут быть очень большими, а мы можем записывать лишь один бит на каждый цветовой канал... то есть для больших файлов нужны большие изображения и огромные ключи.

Таким образом, в проекте реализована возможность кодировать сообщения из заглавных латинских букв, пробела, точки и запятой (STEGO_BITS_CODE = 5) или кодировать любые файлы (STEGO_BITS_CODE = 8).

Если же нужно кодировать сообщения из небольшого количества символов, или просто кодировать символы по-другому, можно поменять STEGO_BITS_CODE (но этот параметр должен быть от 1 до 8) в файле main.c, а также функции кодировки и раскодировки символов в файле stego.c.