Baseline dct huffman coding что это

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

Источник

Метаданные – как узнать, где была сделана фотография?

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

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

Метаданные фотографии что это?

Рассмотрим понятие «метаданные» на очень простом и бытовом примере. Цифровая фотография (то, что мы видим и анализируем с внешней стороны) является своего рода пирогом, который испекла любящая мама и поставила на стол – мы видим его, но не знаем, что внутри. Метаданные – информация о том, как и где была сделана фотография, название города или достопримечательности, время, дата, устройство, т. е. другими словами – пирог в разрезе, когда уже можем сказать о структуре, цвете, о том какие ингредиенты внутри, в каком виде, количестве, объеме, какой у него вкус и т. д.

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

Виды метаданных цифровой фотографии

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

Наиболее широкое распространение среди метаданных имеет стандарт EXIF, который является неотъемлемой частью цифровых изображений и содержит в себе полное описание настроек камеры, а именно:

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

Наглядным примером, является, например, сервис Google Images и Яндекс.Картинки. Достаточно добавить любое фото и поиск, благодаря метаданным, покажет идентичные или же похожие изображения по объектам, структуре, содержанию, цветовому оформлению и т. д.

Область применения метаданных

В правильных руках метаданные могут быть, как «спасательный круг», в ином случае, как «камень привязанный к ногам и тянущий на дно». При наличии знаний и умений, метаданные цифровых фотографий, файлов и документов – невероятно мощный инструмент. Они находят свое применение среди злоумышленников, хакеров, в правоохранительных органах и специалистов службы безопасности при тестах на проникновение. О том, какую опасность содержат в себе скрытие данные о файлах и какое применения им можно найти – смотрите в ролике на YouTube от блоггера «overbafer1»:

Одним из примеров, где метаданных стали роковой ошибкой для человека, является история с Джоном Макафи, основателем и разработчиком одноименного антивирусного программного обеспечения – McAfee.

В определенный период времени он находился в бегах скрываясь от правительства по обвинению в убийстве, несмотря на это – имел множество поклонников и подражателей. Так, журналисты от компании Vice имели честь провести несколько дней с беглецом в тайном убежище, впоследствии чего опубликовали статью об этом приключении содержащую в себе фотографию с iPhone.

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

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

«Мы слепо стали использовать технологии, без понимания рисков. А риск – в полной потере конфиденциальности!» – заявил в одном из интервью Джон Макафи.

Как посмотреть метаданные и узнать, где была сделана фотография?

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

Узнать GPS-координаты и метаданные фотографии через свойства

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

Просмотр свойств – самый доступный из всех способ получения метаданных, т. к. реализуем если и не на любой, то практически на всех современных операционных системах. Для примера рассмотрим, как это сделать на ОС Windows 10. В настоящее время существует два доступных варианта, и первый из них:

В этом окне помимо технических метаданных, так же содержится ряд других разделов:

В разделе GPS (отображается не на всех фото) можно увидеть координаты. Загрузив их в карты Google или Яндекс возможно узнать, где была сделана фотография:

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

Точность идентификации крайне высокая. Погрешность составляет порядка 5-15 метров.

Просмотреть метаданные фотографии онлайн

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

Самый простой по функционалу и, вероятно, самый востребованный ресурс по поиску метаданных. По заявлению автора, фотографии и данные, просматриваемые с помощью этого сервиса, никому не передаются, и при этом, они не сохраняются после временного периода, необходимого для функционирования сервиса. Поддерживает очень большое количество форматов фото. Для того, чтобы воспользоваться поиском, перейдите на официальный сайт Jeffrey’s Image Metadata Viewer по ссылке выше:

Загрузите изображение с компьютера или же укажите ссылку. Пройдите проверку, что Вы не робот и нажмите кнопку «View Image Data». Спустя несколько секунд фото будет загружено и отобразится окно с базовой информацией:

В этом окне, помимо различного рода параметров и характеристик присутствуют координаты и ссылки на онлайн-карты от Google, Yahoo, WikiMapia, OpenStreetMap, Bing, что с легкостью позволяет узнать и увидеть место съемки. Если пролистать страницу ниже, будете наблюдать полную информацию о фотографии в разделе EXIF, File и Composite.

Забыли, где сделали снимок с помощью мобильного устройства или же камеры? Может просто желаете узнать, в каком месте сделан снимок? Pic2Map анализирует метаданные EXIF, встроенные в изображение, чтобы найти координаты GPS и местоположение (если они присутствуют) и, в качестве результата, показывает фотографию на карте с полным описанием характеристик и параметров камеры.

Сервис Pic2Map работает очень просто – переходим на главную страницу сайта по ссылке выше, нажимаем кнопку «Select photo files». Если не желаете, чтобы загруженное фото было общедоступным – установите отметку напротив «Keep photos private»:

После того, как сервис обработает EXIF-данные фотографии, Вы увидите отметку на карте с местоположением и краткую информацию:

Несколько ниже, на этой же странице, содержится текстовое описание настроек и параметров снимка:

Из описания следует, что:

Помимо текстового описания, сервис отображает информация по категориям, в структурированном формате:

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

Сервис позволяющий узнать EXIF, IPTC, XMP и другую информацию JPEG фото онлайн. Данный онлайн-инструмент анализирует JPEG фотографию на наличие метаданных и отображает такую информацию, как: разрешение фото, фирму и модель техники, размер в DPI, выдержку, диафрагму, значение ISO, дату и время съёмки, использована вспышка или нет, тип и фокусное расстояние объектива, в том числе и то, которое использовалось при съёмке, наличие цифрового зума, баланс белого, пробег фотоаппарата (количество срабатываний затвора объектива), серийный номер фотоаппарата и объектива отдельно, GPS-координаты и многое другое.

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

Спустя несколько секунд получите результат обработки, где содержится технические, EXIF и просчитанные метаданные:

↓ Анимированное изображение ► нажмите на него, чтобы посмотреть ↓

Программы для просмотра метаданных фотографий

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

На википедии уже содержится полноценное сравнение программ просмотра метаданных с подробным описание платформ, поддерживаемых стандартов и форматов данных. В рамках данной статьи, для примера, возьмем одну программу из представленного списка, а именно Exif Pilot – программа для просмотра, редактирования и создания метаданных:

Является условно-бесплатной, т. е. основной функционал бесплатный, при этом доступен дополнительный контент для расширения возможностей. В бесплатной версии пользователь имеет возможность осуществлять:

Дополнительные возможности в платной версии:

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

Как редактировать или удалить метаданные фотографии?

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

Самый простой и доступный способ изменить или удалить «невидимые» данные фотографии – воспользоваться функциями операционной системы (в рамках примера – это Windows 10):

↓ Анимированное изображение ► нажмите на него, чтобы посмотреть ↓

Здесь необходимо выбрать наиболее подходящий вариант:

Поменять метаданные также можно с помощью онлайн-инструментов, которых в Интернете бесчисленное множество. Одним из таких сервисов является редактор IMGonline, достаточно лишь загрузить фотографию и нажать кнопку «Редактировать»:

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

↓ Анимированное изображение ► нажмите на него, чтобы посмотреть ↓

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

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

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

Для примера, воспользуемся все тем же ПО, что и для просмотра – Exif Pilot. При двойном нажатии на изображение открывается окно с полным набор метаданных доступных для редактирования:

↓ Анимированное изображение ► нажмите на него, чтобы посмотреть ↓

Как видите, спектр настроек и возможностей довольно обширный для экспериментов.

Что делать если не удалось определить метаданные и найти, где была сделана фотография?

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

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

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

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

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

Поэтому ответ на вопрос: «Что делать если не удалось найти, где была сделана фотография?» – экспериментировать. Имея в наличии фото – можно найти контактные данные человека, например, номер телефона. В последствии, определить социальные сети с помощью номера телефона и произвести поиск по мессенджерам. В средствах мгновенного обмена сообщениями определить никнейм. Сделать поиск по нику – получить ряд других источников, которыми пользуется человек и т. д.

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

Рекомендации при публикации фотографий

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

Если Вы делаете фотографию с помощью смартфона – перейдите в настройки и уберите привязку географических координат к снимку:

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

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

Источник