Хранение данных в изображениях при сжатии с потерями

Здравствуйте.

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

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

Есть, например, готовые решения c QR-кодами, но нужно что-то получше.

0

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

0

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

0

Сообщение от Igor3D То есть в исходное изображение добавляются некоторые "водяные знаки" по которым можно идентифицировать имедж. И требуется чтобы они "выживали" при компрессии имеджа?

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

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

0

Сообщение от wingblack Нет, никакой стеганографии и водяных знаков

Если речь идёт не о наложении данных на картинку, а о беспотерьном сжатии данных алгоритмом, предназначенным для сжатия картинок с потерями, то или используйте алгоритмы, предназначенные для сжатия данных, или представляйте элементы данных в виде, максимально приближенном к элементам картинок. Причём к достаточно крупным элементам, чтобы при "ситуации, когда изображение пересжималось несколько раз" не возникали потери.
Вообще, если это не скрытая передача данных в картинках, то чем это отличается от QR-кодов?
Допустим, что если формировать картинку в виде текста (нули и единицы, или более различимые знаки - белые и чёрные квадраты), то до тех пор, пока при пересжатиях картинка распознаётся, можно считать, что данные передаются без потерь.
Но это в сущности и есть те самые QR-коды...

wingblack, в чём изюминка нового велосипеда?

0

Сообщение от i8085 wingblack, в чём изюминка нового велосипеда?

Присоединяюсь к вопросу. Не очень понятно что надо получить

0

Сообщение от i8085 Вообще, если это не скрытая передача данных в картинках, то чем это отличается от QR-кодов?

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

Сообщение от i8085 Допустим, что если формировать картинку в виде текста (нули и единицы, или более различимые знаки - белые и чёрные квадраты), то до тех пор, пока при пересжатиях картинка распознаётся, можно считать, что данные передаются без потерь.

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

Сообщение от Igor3D Присоединяюсь к вопросу. Не очень понятно что надо получить

Описать алгоритм который умеет следующее:
1) на вход передается файл с произвольными данными, и число R от 0 до 100
2) алгоритм на основе данных в файле создает серию изображений - матрицы RGB пикселей размера N*M (bitmap-ы)
3) каждое изображение сохраняется в JPG файл с качеством равным R

Далее должен быть обратный процесс
1) читаем серию JPG файлов, извлекаем массивы точек RGB(bitmap)
2) извлекаем данные из изображений согласно нашему алгоритму
3) сохраняем данные в файл

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

0

Сообщение от wingblack такой алгоритм должен преобразовывать данные в изображения настолько компактно, насколько возможно

Уже просчитано и реализовано: QR-коды.

0

Сообщение от wingblack Описать алгоритм который умеет следующее:

Примерно понятно, спасибо за подробные разъяснения. Т.е. вся картинка (целиком) посвящена "кодированию", ничего другого там нет.

Если так, то неясно какие трудности (с точки зрения изображения). Ну задал набор цветов (типа палитры) чтобы можно было удобно восстановиться, из тех же соображений размер квадратика. И кодируйте на здоровье, как - это уже др вопрос.

0

Сообщение от Igor3D И кодируйте на здоровье, как - это уже др вопрос.

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

0

Сообщение от wingblack можно попытаться компенсировать возникновение смещения по цветности

Почитайте про реализацию в фото-редакторах фильтра JPEG Artifact Removal.

0

Сообщение от wingblack Для ч/б сразу напрашивается среднее арифметическое по квадрату, и округление серого квадрата до ближайшего ч/б значения.

То же самое напрашивается и для цветного, конечно палитра взята с каким-то "шагом".

0

Сообщение от Igor3D То же самое напрашивается и для цветного...

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

А вообще, чтобы сделать оптимальное кодирование, надо, чтобы элемент изображения максимально соответствовал виду функции, применяемой в JPEG, чтобы при кодировании получалось минимальное количество коэффициентов и чтобы коэффициенты были максимально простые. Тогда и при многократном перекодировании нарастание ошибок будет минимально, и сжатие максимально. Конечно, до степени сжатия алгоритмов, предназначенных для сжатия данных тут как пешком до Луны - избыточность колоссальная.
Считать надо. А то, что в уме у ТС - всего лишь "протокол о намерениях". Кстати, wingblack, а вы вообще алгоритм JPEG хорошо знаете?

0

Сообщение от i8085 Надо считать эффективность сжатия.

Лучше ее просто "оценить" сравнив тестовые картинки до и после компрессии

0

Сообщение от Igor3D сравнив тестовые картинки

Для этого надо уже иметь алгоритм, реализованный в программе.
Опять "хотим как лучше, а получится как всегда"? (c) В.С.Ч.
Сначала сляпаем "какой-нибудь" алгоритм, а потом будем изучать, чегой-то оно при старте падает?
Методом "тыка" только дети хорошо получаются.
Считать надо. Моделировать.
Алгоритм сжатия GPEG "заточен" под сжатие вполне определённого типа данных. Если данные описываются функциями разложения без округления, то такие данные GPEG сохранит без потерь.
Вот в эту сторону и надо копать.

Добавлено через 6 минут
Кстати, wingblack, а что вы будете делать, если картинку пережмут в PNG, GIF, TIFF?

0

Сообщение от i8085 Кстати, wingblack, а что вы будете делать, если картинку пережмут в PNG, GIF, TIFF?

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

0

Сообщение от wingblack Пока рассматривается только...

Да, этот тяжёлый отрешённый взгляд чувствуется.

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

0

Сообщение от i8085 Для этого надо уже иметь алгоритм, реализованный в программе. Опять "хотим как лучше, а получится как всегда"? (c) В.С.Ч. Сначала сляпаем "какой-нибудь" алгоритм, а потом будем изучать, чегой-то оно при старте падает? Методом "тыка" только дети хорошо получаются. Считать надо. Моделировать.

Ну вот зачем "нагнетать"? Я говорю о простом тесте. Заполнили картинку цветными квадратиками 8x8 и сжали. Потом загрузили сжатую картинку и посчитали средний цвет по каждому квадратику. Отклонение умножить на 4 - вот собственно и "шаг палитры" для 8x8 и данного сжатия. Попробовали уменьшить квадратик и.т.п.

0

Сообщение от i8085 Пора вам более подробно раскрыть задачу. Что-то в условии не так. Если это какая-то передача информации с защитой от поисковых роботов, то можно сначала сжать архиватором (можно с паролем), а потом, что получилось, рисовать как QR-коды, только изменив размер картинки.

Подготовительная стадия к "а давайте файлы на ютубе хранить будем"

0

Недавно вернулся к данному вопросу и смог сделать пробную версию программки по данному топику.
Как результат хождения по граблям:
- бит передается как черный или белый квадрат в формате RGB
- размер получаемого видео файла: для текста - примерно равен исходному файлу, для сжатых файлов или файлов которые плохо сжимаются архиваторами - примерно в 3 раза больше оригинала.
- исходный файл успешно извлекается без изменений после перекодирования видео из-за выкладывания на Youtube, анализ показывает что видео переживет и немного более "жестокое" перекодирование.

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

0