Проблема кодирования изображений в Twitter

Если изображение состоит из 1000 слов, сколько изображения можно уместить 140 символами?

Примечание. Вот и все, ребята! Крайний срок награждения уже здесь, и после некоторых напряженных размышлений я решил, что запись Boojum едва вытеснил Сэма Хосевара. Я отправлю более подробные заметки, как только у меня будет возможность их написать. Конечно, каждый должен свободно предлагать решения и улучшать решения, за которые люди могут голосовать. Спасибо всем, кто прислал заявку; Мне все они понравились. Мне было очень весело бежать, и я надеюсь, что это было весело как для участников, так и для зрителей.

Я наткнулся на этот интересный пост о попытке сжатия изображений. в комментарий Twitter, и множество людей в этой ветке (а также ветку на Reddit) предлагали разные способы сделать это. Так что, я полагаю, это станет хорошей проблемой для кодирования; пусть люди вкладывают свои деньги туда, где есть их рот, и показывают, как их идеи о кодировании могут привести к более подробным деталям в ограниченном пространстве, которое у вас есть.

Я призываю вас придумать универсальную систему для кодирования изображений в 140-символьные сообщения Twitter и снова декодировать их в изображение. Вы можете использовать символы Unicode, так что вы получаете более 8 бит на символ. Однако даже с учетом символов Unicode вам придется сжимать изображения до очень небольшого объема; это, безусловно, будет сжатие с потерями, поэтому нужно будет делать субъективные суждения о том, насколько хорошо выглядит каждый результат.

Вот результат, который исходный автор, Quasimondo, получил из своей кодировки (изображение лицензировано под лицензией Creative Commons Attribution-Noncommercial): Мона Лиза

Вы можете лучше?

Правила

  1. В вашей программе должно быть два режима: кодирование и декодирование.
  2. When encoding:
    1. Your program must take as input a graphic in any reasonable raster graphic format of your choice. We'll say that any raster format supported by ImageMagick counts as reasonable.
    2. Ваша программа должна выводить сообщение, которое может быть представлено 140 или менее кодовыми точками Unicode; 140 кодовых точек в диапазоне _1 _ – _ 2_, исключая несимвольные (U+FFFE, U+FFFF, U+ n FFFE, U+ n FFFF, где n - _9 _ – _ 10_ шестнадцатеричный, диапазон _11 _ – _ 12_) и суррогатные кодовые точки (_13 _ – _ 14_). Он может быть выведен в любой разумной кодировке по вашему выбору; любая кодировка, поддерживаемая GNU iconv, будет считаться разумной, а собственная кодировка вашей платформы или кодировка локали вероятно будет хорошим выбором. Дополнительные сведения см. В примечаниях к Unicode ниже.
  3. When decoding:
    1. Your program should take as input the output of your encoding mode.
    2. Ваша программа должна выводить изображение в любом разумном формате по вашему выбору, как определено выше, хотя для вывода векторные форматы также подходят.
    3. Выходное изображение должно быть приближенным к входному изображению; чем ближе вы сможете подойти к входному изображению, тем лучше.
    4. Процесс декодирования может не иметь доступа к любому другому выходу процесса кодирования, кроме выходных данных, указанных выше; то есть вы не можете куда-то загрузить изображение и вывести URL-адрес для загрузки процесса декодирования или что-нибудь в этом роде.

  4. Для единообразия пользовательского интерфейса ваша программа должна вести себя следующим образом:

    1. Your program must be a script that can be set to executable on a platform with the appropriate interpreter, or a program that can be compiled into an executable.
    2. Ваша программа должна принимать в качестве первого аргумента encode или decode для установки режима.

    3. Ваша программа должна принимать входные данные одним или несколькими из следующих способов (если вы реализуете тот, который принимает имена файлов, вы также можете читать и писать из stdin и stdout, если имена файлов отсутствуют):

      1. Принимайте входные данные из стандартного входа и производите выходные данные из стандартного выхода.

        my-program encode <input.png >output.txt
my-program decode <output.txt >output.png

      2. Принимайте входные данные из файла, названного во втором аргументе, и производите вывод в файле, названном в третьем аргументе.

        my-program encode input.png output.txt
my-program decode output.txt output.png
  5. For your solution, please post:
    1. Your code, in full, and/or a link to it hosted elsewhere (if it's very long, or requires many files to compile, or something).
    2. Объяснение того, как это работает, если это не сразу видно из кода или если код длинный и людям будет интересно резюме.
    3. Пример изображения с исходным изображением, сжатым текстом и декодированным изображением.
    4. Если вы основываете идею кого-то другого, пожалуйста, укажите их. Это нормально - пытаться усовершенствовать чью-то идею, но вы должны их приписать.

Методические рекомендации

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

  1. Aesthetics are important. I'll be judging, and suggest that other people judge, based on:
    1. How good the output image looks, and how much it looks like the original.
    2. Как красиво выглядит текст. Полностью случайная чепуха - это нормально, если у вас есть действительно умная схема сжатия, но я также хочу видеть ответы, которые превращают изображения в многоязычные стихи или что-то в этом роде. Обратите внимание, что автор оригинального решения решил использовать только китайские иероглифы, так как так оно выглядело лучше.
    3. Интересный код и умные алгоритмы - это всегда хорошо. Мне нравится короткий, по существу и ясный код, но действительно умные сложные алгоритмы тоже подходят, если они дают хорошие результаты.
  2. Скорость также важна, но не так важна, как то, насколько хорошо вы выполняете сжатие изображения. Я бы предпочел программу, которая может конвертировать изображение за десятые доли секунды, чем что-то, что будет запускать генетические алгоритмы в течение нескольких дней.
  3. Я предпочитаю более короткие решения более длинным, если они достаточно сопоставимы по качеству; краткость - это добродетель.
  4. Ваша программа должна быть реализована на языке, который имеет свободно доступную реализацию в Mac OS X, Linux или Windows. Я хотел бы иметь возможность запускать программы, но если у вас есть отличное решение, которое работает только под MATLAB или что-то в этом роде, это нормально.
  5. Your program should be as general as possible; it should work for as many different images as possible, though some may produce better results than others. In particular:
    1. Having a few images built into the program that it matches and writes a reference to, and then produces the matching image upon decoding, is fairly lame and will only cover a few images.
    2. Программа, которая может брать изображения простых плоских геометрических фигур и разлагать их на некоторый векторный примитив, довольно изящна, но если она не работает с изображениями сверх определенной сложности, она, вероятно, недостаточно универсальна.
    3. Программа, которая может делать изображения только с определенным фиксированным соотношением сторон, но хорошо с ними справляется, тоже подойдет, но не идеальна.
    4. Вы можете обнаружить, что черно-белое изображение может содержать больше информации в меньшем пространстве, чем цветное изображение. С другой стороны, это может ограничить типы изображений, к которым оно применимо; лица хорошо выглядят в черно-белом цвете, но абстрактный дизайн может не так хорошо выглядеть.
    5. Совершенно нормально, если выходное изображение меньше, чем входное, при примерно одинаковых пропорциях. Ничего страшного, если вам нужно увеличить изображение, чтобы сравнить его с оригиналом; важно то, как это выглядит.
  6. Ваша программа должна выдавать результат, который может пройти через Twitter и остаться невредимым. Это всего лишь рекомендация, а не правило, так как я не смог найти никакой документации по точному набору поддерживаемых символов, но вам, вероятно, следует избегать управляющих символов, забавных невидимых комбинирующих символов, символов частного использования и т.п.

Рубрика подсчета очков

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

  • 15 points for how well the encoding scheme reproduces a wide range of input images. This is a subjective, aesthetic judgement
    • 0 means that it doesn't work at all, it gives the same image back every time, or something
    • 5 означает, что он может кодировать несколько изображений, хотя декодированная версия выглядит некрасиво и может вообще не работать с более сложными изображениями.
    • 10 означает, что он работает с широким спектром изображений и создает приятные на вид изображения, которые иногда могут быть различимы.
    • 15 означает, что он создает идеальные копии некоторых изображений и даже для более крупных и сложных изображений дает что-то узнаваемое. Или, возможно, он не делает изображения достаточно узнаваемыми, а создает красивые изображения, явно заимствованные из оригинала.
  • 3 points for clever use of the Unicode character set
    • 0 points for simply using the entire set of allowed characters
    • 1 балл за использование ограниченного набора символов, безопасных для передачи через Twitter или в более разнообразных ситуациях.
    • 2 балла за использование тематического подмножества символов, например, только идеограммы Хань или только символы с письмом справа налево
    • 3 балла за то, чтобы сделать что-то действительно аккуратное, например, создать читаемый текст или использовать символы, похожие на изображение, о котором идет речь.
  • 3 points for clever algorithmic approaches and code style
    • 0 points for something that is 1000 lines of code only to scale the image down, treat it as 1 bit per pixel, and base64 encode that
    • 1 балл за то, что использует стандартную технику кодирования, хорошо написано и кратко
    • 2 балла за то, что вводит относительно новую технику кодирования или что на удивление коротко и чисто
    • 3 балла за один лайнер, который на самом деле дает хорошие результаты, или что-то, что открывает новые горизонты в графическом кодировании (если это кажется низким количеством баллов для открытия нового пути, помните, что результат, такой хороший, скорее всего, будет иметь высокий балл за эстетику также)
  • 2 балла за скорость. При прочих равных, быстрее - лучше, но все вышеперечисленные критерии важнее скорости.
  • 1 балл за использование бесплатного программного обеспечения (с открытым исходным кодом), потому что я предпочитаю бесплатное программное обеспечение (обратите внимание, что C # по-прежнему будет иметь право на этот балл, пока он работает на Mono, аналогично код MATLAB будет иметь право, если он работает на GNU Octave)
  • 1 балл за фактическое соблюдение всех правил. Эти правила стали немного большими и сложными, поэтому я, вероятно, приму в остальном хорошие ответы, в которых неверна одна маленькая деталь, но я дам дополнительный балл любому решению, которое действительно следует всем правилам.

Эталонные изображения

Некоторые люди просили предоставить несколько эталонных изображений. Вот несколько эталонных изображений, которые вы можете попробовать; Меньшие версии встроены сюда, все они ссылаются на большие версии изображения, если они вам нужны:

Lena Мона Лиза Корнельский бокс StackOverflow Logo

Приз

Я предлагаю вознаграждение в размере 500 респондентов (плюс 50, которое вводит StackOverflow) за решение, которое мне больше всего нравится, на основе вышеуказанных критериев. Конечно, я призываю всех остальных проголосовать за свои любимые решения и здесь.

Примечание о сроке

Этот конкурс будет длиться до тех пор, пока не закончится награда, около 18:00 в субботу, 30 мая. Я не могу сказать точное время, когда он закончится; это может быть где угодно с 17 до 19 часов. Я гарантирую, что просмотрю все заявки, присланные до 14:00, и сделаю все возможное, чтобы просмотреть все заявки до 16:00; если решения будут отправлены после этого, у меня не будет возможности подробно рассмотреть их, прежде чем я приму свое решение. Кроме того, чем раньше вы отправите заявку, тем больше у вас будет шансов, что голосование поможет мне выбрать лучшее решение, поэтому постарайтесь отправить заявку раньше, а не в срок.

Заметки Unicode

Также была некоторая путаница в том, какие именно символы Unicode разрешены. Диапазон возможных кодовых точек Unicode составляет от U+0000 до U+10FFFF. Есть некоторые кодовые точки, которые нельзя использовать в качестве символов Unicode при любом открытом обмене данными; это несимволы и суррогатные кодовые точки. Несимволы определены в Unidode Standard 5.1.0 раздел 16.7 как значения U+FFFE, U+FFFF, U+ n FFFE, U+ n FFFF, где n - _28 _ – _ 29_ в шестнадцатеричном формате, а диапазон _30 _ – _ 31_. Эти значения предназначены для внутреннего использования в конкретных приложениях, и соответствующие приложения могут удалять эти символы из обрабатываемого ими текста. Суррогатные кодовые точки, определенные в стандарте Unicode 5.1.0, раздел 3.8 как _32 _ – _ 33_, используются для кодирования символов за пределами базовой многоязычной плоскости в UTF-16; таким образом, невозможно представить эти кодовые точки непосредственно в кодировке UTF-16, и недопустимо кодировать их в любой другой кодировке. Таким образом, для целей этого конкурса я разрешаю любую программу, которая кодирует изображения в последовательность, состоящую не более чем из 140 кодовых точек Unicode из диапазона _34 _ – _ 35_, за исключением всех несимволов и суррогатных пар, как определено выше.

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

Поскольку Twitter не указывает точный набор символов, который они поддерживают, я буду снисходительно относиться к решениям, которые на самом деле не работают с Twitter, потому что некоторые символы считаются дополнительными или некоторые символы удаляются. Желательно, но не обязательно, чтобы все закодированные выходные данные могли быть без повреждений переданы через Twitter или другую службу микроблогов, такую ​​как identity.ca < / а>. Я видел документацию, в которой говорилось, что Twitter кодирует объекты ‹,› и &, и поэтому считает их как 4, 4 и 5 символов соответственно, но я не проверял это сам, и их счетчик символов JavaScript не кажется считать их таким образом.

Советы и ссылки

twitter unicode compression
person Community    schedule 21.05.2009    source источник
comment
Не стесняйтесь предлагать предложения по правилам, которые я написал в комментариях; Я, конечно, готов подправить их, если люди чувствуют, что они нуждаются в разъяснении или слишком подробно описаны.   -  person Brian Campbell    schedule 21.05.2009
comment
Вероятно, вы должны сказать, что загрузка изображения на сервер и размещение на нем URL-адреса недействительны.   -  person Shay Erlichmen    schedule 21.05.2009
comment
@Shay Разве я уже не говорил это? Процесс декодирования может не иметь доступа к любому другому выходу процесса кодирования, кроме выходных данных, указанных выше; то есть вы не можете куда-то загрузить изображение и вывести URL-адрес для загрузки процесса декодирования или что-нибудь в этом роде.   -  person Brian Campbell    schedule 21.05.2009
comment
@Brian Я думаю, что было бы неплохо предоставить эталонное изображение или изображения, которые можно было бы использовать для всех записей, это выровняло бы поле и облегчило бы оценку.   -  person Richard Stelling    schedule 22.05.2009
comment
Хороший вызов, но я против того, чтобы вы использовали слово «глупый». Фактически, это решение (с использованием URI / DOI или аналогичного) является чрезвычайно хорошей идеей для решения такого рода проблем, поскольку оно использует (очень простую) семантическую информацию для кодирования изображение. Это в духе проекта Semantic Web. Конечно, справедливо исключить такие решения, потому что их просто невозможно превзойти - но все же они совсем не глупы и определенно являются своего рода алгоритмом сжатия (с использованием очень большого словаря).   -  person Konrad Rudolph    schedule 22.05.2009
comment
@Konrad Rudolph Я согласен; Я не имел в виду глупо с практической точки зрения (ясно, что весь этот конкурс глупо с практической точки зрения), я имел в виду глупый в контексте этого конкурса. Использование URI на самом деле не является алгоритмом сжатия в смысле теории информации, поскольку не позволяет передавать больше информации без простого использования альтернативного канала. Вы можете предоставить кодировщику и декодеру большую базу данных изображений и назвать это сжатием, которое работает только с ограниченным набором изображений, но я указал, что вам нужно иметь возможность обрабатывать произвольное изображение.   -  person Brian Campbell    schedule 23.05.2009
comment
Вот пара ссылок, на которые я наткнулся, которые могут помочь людям: azillionmonkeys.com/qed /unicode.html для объяснения допустимого диапазона символов Юникода. Обратите внимание, что кодировки UTF - это те, которые могут кодировать весь диапазон Unicode; UCS-4 - это надмножество Unicode, а UCS-2 и ASCII - подмножества. Что касается сжатия, то вот техника, аналогичная исходной публикации, хотя он позволяет себе 1 КБ, а не 350 байт: screamingduck.com/Article.php?ArticleID=46&Show=ABCE   -  person Brian Campbell    schedule 23.05.2009
comment
Это где-нибудь написано, если полученное изображение должно быть такого же размера, как оригинал?   -  person Gabriele D'Antona    schedule 24.05.2009
comment
@friol Из рекомендаций: Совершенно нормально, если выходное изображение меньше входного, хотя пропорции примерно такие же. Ничего страшного, если вам нужно увеличить изображение, чтобы сравнить его с оригиналом; важно то, как это выглядит. Вы должны сохранить исходное соотношение сторон (примерно это нормально), поэтому, если у вас есть входное изображение 200x400, это нормально, если выходное изображение имеет размер 20x40 (или даже если на выходе есть какая-то форма векторной графики). Однако не следует превращать все изображения в квадратную форму; соотношение сторон - это одна из тех вещей, которые вам нужно каким-то образом передать.   -  person Brian Campbell    schedule 25.05.2009
comment
Один вопрос правил, но будет ли преобразование в изображение в градациях серого засчитываться против нас, если предположить, что изображение все еще выглядит хорошо?   -  person rjzii    schedule 28.05.2009
comment
@Rob Это будет основано на субъективном суждении. Если преобразование в оттенки серого позволяет получить больше деталей, это прекрасно. Если детализация примерно такая же, как у цветной версии, то версия в оттенках серого, вероятно, не будет хорошо конкурировать. Итак, да, отправляйте решения с использованием шкалы серого, если вы считаете, что это помогает. Частично цель конкурса состоит в том, чтобы просто увидеть, как работают разные подходы; Я бы хотел, чтобы люди экспериментировали и пробовали разные решения.   -  person Brian Campbell    schedule 28.05.2009
comment
На мой взгляд, я бы настроил его так, чтобы вы могли использовать несколько твитов для отправки изображения ... с некоторым кодом типа TCP впереди, чтобы можно было сделать заметки типа 1/3, 2/3 для дешифратора.   -  person Ape-inago    schedule 30.05.2009
comment
@Joey Извини, ты не успел это увидеть! Я старался хорошо об этом разрекламировать, но трудно сделать так, чтобы все это видели. @ ape-inago Да, вы можете уместить любое изображение в несколько твитов, если разделите его и снова скомбинируете. Но тогда не было бы особой проблемы, не так ли? Смысл этого должен был заключаться в том, чтобы увидеть, какое сжатие люди могут делать с жесткими ограничениями.   -  person Brian Campbell    schedule 30.05.2009
comment
Это не будет считаться записью, но будет ли загрузка данных в слот аватара пользователя возможным решением?   -  person chakrit    schedule 20.06.2009
comment
Мне нравится этот вызов. Однако есть альтернативная мысль, поскольку мы можем закодировать данные изображения в текст, что, если мы сделаем наоборот. Возьмите случайную выборку, скажем, 1000 твитов, расшифруйте их в изображения и посмотрите, что мы получим.   -  person Nick Radford    schedule 20.07.2011

Ответы (15)


arrow_upward
244
arrow_downward

Хорошо, вот мой: nanocrunch.cpp и CMakeLists.txt, чтобы создать его с помощью CMake. Он полагается на Magick ++ ImageMagick API для большей части обработки изображений. Также требуется библиотека GMP для большой арифметики для кодировки строк.

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

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

Другое дело, что хранение настроек контрастности / яркости для каждого цветового компонента каждого блока слишком дорого. Вместо этого я храню сильно квантованный цвет (в палитре всего 4 * 4 * 4 = 64 цвета), который просто смешивается в некоторой пропорции. Математически это эквивалентно регулировке переменной яркости и постоянной контрастности для каждого цвета. К сожалению, это также означает, что нет отрицательного контраста, чтобы переворачивать цвета.

После вычисления позиции, ориентации и цвета для каждого блока он кодирует их в строку UTF-8. Во-первых, он генерирует очень большое bignum для представления данных в таблице блоков и размера изображения. Подход к этому аналогичен решению Сэма Хосевара - типа большого числа с основанием, которое зависит от позиции.

Затем он преобразует это в основу любого размера доступного набора символов. По умолчанию он полностью использует назначенный набор символов Юникода за вычетом меньшего, большего чем, амперсанда, управления, комбинирования, а также суррогатных и частных символов. Это некрасиво, но работает. Вы также можете закомментировать таблицу по умолчанию и вместо этого выбрать 7-битный ASCII для печати (опять же, исключая символы ‹,> и &) или CJK Unified Ideographs. Таблица доступных кодов символов хранится в виде серий, закодированных с чередованием серий недопустимых и допустимых символов.

В любом случае, вот несколько изображений и времен (измеренных на моем старом P4 3,0 ГГц), сжатых до 140 символов в полном назначенном наборе Unicode, описанном выше. В целом, я довольно доволен тем, как все они оказались. Если бы у меня было больше времени поработать над этим, я бы, вероятно, попытался уменьшить блочность распакованных изображений. Тем не менее, я думаю, что результаты довольно хороши для предельной степени сжатия. Распакованные изображения немного импрессионистичны, но мне относительно легко увидеть, насколько биты соответствуют оригиналу.

Логотип переполнения стека (8,6 с для кодирования, 7,9 с для декодирования, 485 байт):
http://i44.tinypic.com/2w7lok1.png

Лена (32,8 с для кодирования, 13,0 с для декодирования, 477 байт):
http://i42.tinypic.com/2rr49wg.png http://i40.tinypic.com/2rhxxyu.png

Мона Лиза (43,2 с на кодирование, 14,5 с на декодирование, 490 байт):
http://i41.tinypic.com/ekgwp3.png http://i43.tinypic.com/ngsxep.png

Изменить: унифицированные символы CJK

Сэм спросил в комментариях об использовании этого с CJK. Вот версия Моны Лизы, сжатая до 139 символов из унифицированного набора символов CJK:

http://i43.tinypic.com/2yxgdfk.png 咏 璘 驞 凄 脒 鵚 据 蛥 鸂 拗 朐 朖 辿 韩 瀦 魷 歪 痫 蕜 抱 揎 頻 蓼 嗞 靊 寞 柮 嚛 嚵 籥 聚 絖 銓 馿 渫 櫰 矍 昀 撄 粂 敽 牙 蔍 峬 覧 絀 蹔 抆 惫 冧 笻 哜 搀 澐 垝 黟 偞 媄 童 韠 镰 猳 閺 狌 而 羶 喙 婣 唆 鐤 諽 鷍 鴞 駫 埙 誖 萜 愿 萗 哳 垬 濅 鬒 秀 瞛 洆 闥 籴 珵 仾 氙 熜 謋 繴 茴 髭 杍 嚖 熥 勳 餅 擸 萿

Параметры настройки в верхней части программы, которую я использовал для этого, были: 19, 19, 4, 4, 3, 10, 11, 1000, 1000. Я также закомментировал первое определение number_assigned и code и раскомментировал последние их определения для выбора унифицированного набора символов CJK.

person Community    schedule 30.05.2009
comment
Вау! Хорошая работа. Я скептически относился к сжатию фрактальных изображений для изображений такого размера, но на самом деле оно дает довольно приличные результаты. Его также было довольно легко скомпилировать и запустить. - person Brian Campbell; 30.05.2009
comment
Спасибо, парни! Сэм, вы имеете в виду результаты, содержащие всего 140 символов CJK? Если да, то да, вам нужно настроить числа вверху. Окончательный размер в битах составляет около log2 (steps_in_x steps_in_y steps_in_red steps_in_green steps_in_blue) * блоков_in_x блоков_in_y + log2 (максимальная_ ширина максимальная_ высота). - person Boojum; 30.05.2009
comment
Изменить: в первом log2 () есть * 16, который я пропустил. Это для возможных ориентаций. - person Boojum; 30.05.2009
comment
Кто-нибудь уже использовал это изображение в твиттере? - person dbr; 31.05.2009

arrow_upward
288
arrow_downward

файлы изображений и исходный код Python (версии 1 и 2)

Версия 1 Это моя первая попытка. Я буду обновлять по мере поступления.

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

Для моей первой попытки я использовал онлайн-сервис для трассировки PNG, однако есть МНОГИЕ бесплатные и платные инструменты, которые могут справиться с этой частью, включая potrace (с открытым исходным кодом).

Вот результаты

http://www.warriorhut.org/graphics/svg_to_unicode/so-logo.png Исходный http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded.png После кодирования и декодирования

Символы: 300

Время: не измеряется, но практически мгновенно (без учета этапов векторизации / растеризации).

Следующим этапом будет встраивание 4 символов (точек пути и команд SVG) в каждый символ Юникода. На данный момент моя сборка Python не имеет поддержки UCS4 с широким набором символов, что ограничивает мое разрешение для каждого символа. Я также ограничил максимальный диапазон нижним концом зарезервированного диапазона юникода 0xD800, однако, как только я создам список разрешенных символов и фильтр, чтобы их избежать, я теоретически могу подтолкнуть необходимое количество символов до 70-100 для логотип выше.

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

Версия 2

ОБНОВЛЕНИЕ: теперь v2 допущена к участию. Изменения:

  • Командная строка управления вводом / выводом и отладка
  • Использует синтаксический анализатор XML (lxml) для обработки SVG вместо регулярного выражения
  • Пакует 2 сегмента пути на символ Юникода
  • Документация и очистка
  • Поддержка style = "fill: color" и fill = "color"
  • Ширина / высота документа, упакованные в один символ
  • Цвет пути упакован в один символ
  • Сжатие цвета достигается путем отбрасывания 4 бита данных цвета на цвет, а затем их упаковки в символ с помощью шестнадцатеричного преобразования.

Символы: 133

Время: несколько секунд.

http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded-v2.png После кодирования и декодирования (версия 2)

Как видите, на этот раз есть несколько артефактов. Это не ограничение метода, а ошибка где-то в моих преобразованиях. Артефакты возникают, когда точки выходят за пределы диапазона 0,0–127,0, и мои попытки ограничить их имели смешанный успех. Решение состоит в том, чтобы просто уменьшить масштаб изображения, однако у меня возникли проблемы с масштабированием фактических точек, а не монтажной области или групповой матрицы, и теперь я слишком устал, чтобы заботиться об этом. Короче говоря, если ваши баллы находятся в поддерживаемом диапазоне, это обычно работает.

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

ОБНОВЛЕНИЕ: этот метод подходит для простых объектов, поэтому мне нужен был способ упростить сложные пути и уменьшить шум. Для этой задачи я использовал Inkscape. Мне повезло с удалением ненужных путей с помощью Inkscape, но у меня не было времени попробовать автоматизировать это. Я сделал несколько примеров svgs, используя функцию Inkscape 'Simplify', чтобы уменьшить количество путей.

Упрощение работает нормально, но с таким количеством путей может работать медленно.

http://www.warriorhut.org/graphics/svg_to_unicode/autotrace_16_color_manual_reduction.png http://www.warriorhut.com/graphics/svg_to_unicode/lena_std_washed_autotrace.png

http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_autotrace.png

Вот несколько снимков в сверхнизком разрешении. Это будет ближе к пределу в 140 символов, хотя может потребоваться и некоторое умное сжатие пути.

http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_groomed.png Упрощенный и десктопный.

http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_triangulated.png упрощенный и упрощенный триангулированный.

autotrace --output-format svg --output-file cornell_box.svg --despeckle-level 20 --color-count 64 cornell_box.png

ВЫШЕ: упрощенные пути с использованием autotrace.

К сожалению, мой синтаксический анализатор не обрабатывает вывод автотрассировки, поэтому я не знаю, как точки могут использоваться или насколько нужно упростить, к сожалению, мало времени на то, чтобы написать это до крайнего срока. Тем не менее, это намного проще разобрать, чем вывод inkscape.

person Community    schedule 28.05.2009
comment
Отлично! Сначала я хотел создать гибридное векторное решение как с острыми краями, так и с гладкими областями, но оно оказалось слишком сложным без использования библиотеки трассировки (которую я не хотел использовать). Я с нетерпением жду возможности увидеть, как далеко вы сможете продвинуться с помощью вашего метода! - person sam hocevar; 28.05.2009
comment
Хороший! Я надеялся, что мы увидим несколько попыток использовать векторизацию практически без потерь. Это означает, что он имеет более низкую универсальность, но более высокое качество для изображений, которые он покрывает. Можно использовать онлайн-сервис для векторизации. Удачи в дальнейшем уменьшении размера! - person Brian Campbell; 28.05.2009
comment
Я бы рассмотрел сжатие изображений и кодирование символов как два разных шага - техника Сэма кажется оптимальной для кодирования и может быть легко встроена в отдельную программу. Вы получите больше отдачи от вложенных средств, сконцентрировавшись на уникальной части вашего решения (то есть на части сжатия) и просто выведя строку битов. - person Mark Ransom; 29.05.2009
comment
Ух ты. Эти образы выглядят действительно стильно. - person Rinat Abdullin; 05.06.2009

arrow_upward
199
arrow_downward

Мое полное решение можно найти на странице http://caca.zoy.org/wiki/img2twit. Он имеет следующие особенности:

  • Приемлемое время сжатия (около 1 минуты для высокого качества)
  • Быстрая декомпрессия (доли секунды)
  • Сохраняет исходный размер изображения (а не только соотношение сторон)
  • Приличное качество реконструкции (ИМХО)
  • Длина сообщения и набор символов (ASCII, CJK, символы) могут быть выбраны во время выполнения.
  • Длина сообщения и набор символов определяются автоматически во время декомпрессии.
  • Очень эффективная упаковка информации

http://caca.zoy.org/raw-attachment/wiki/img2twit/so-logo.png http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter4.png

蜥秓鋖筷聝诿缰偺腶漷庯祩皙靊谪獜岨幻寤厎趆脘搇梄踥桻理戂溥欇渹裏軱骿苸髙骟市簶璨粭浧鱉捕弫潮衍蚙瀹岚玧霫鏓蓕戲債鼶襋躻弯袮足庭侅旍凼飙驅據嘛掔倾诗籂阉嶹婻椿糢墤渽緛赐更儅棫武婩縑逡荨璙杯翉珸齸陁颗鳣憫擲舥攩寉鈶兓庭璱篂鰀乾丕耓庁錸努樀肝亖弜喆蝞躐葌熲谎蛪曟暙刍镶媏嘝驌慸盂氤缰殾譑

Вот приблизительный обзор процесса кодирования:

  • Количество доступных бит рассчитывается исходя из желаемой длины сообщения и используемой кодировки.
  • Исходное изображение сегментируется на столько квадратных ячеек, сколько позволяют доступные биты.
  • На каждую ячейку влияет фиксированное количество точек (в настоящее время 2) с начальными координатами и значениями цвета.
  • The following is repeated until a quality condition is met:
    • A point is chosen a random
    • В этой точке произвольно выполняется операция (перемещение внутри ячейки, изменение цвета)
    • Если результирующее изображение (см. Процесс декодирования ниже) ближе к исходному изображению, операция сохраняется.
  • Размер изображения и список точек закодированы в UTF-8

А это процесс декодирования:

  • Размер изображения и точки считываются из потока UTF-8
  • For each pixel in the destination image:
    • The list of natural neigbours is computed
    • Конечный цвет пикселя устанавливается как средневзвешенное значение цветов его естественных соседей.

Я считаю, что самой оригинальной частью программы является битовый поток. Вместо упаковки значений, выровненных по битам (stream <<= shift; stream |= value), я упаковываю произвольные значения, которые не находятся в диапазонах степени двойки (stream *= range; stream += value). Это требует больших вычислений и, конечно, намного медленнее, но дает мне 2009,18 бит вместо 1960 при использовании 20902 основных символов CJK (это еще три точки, которые я могу вставить в данные). А при использовании ASCII он дает 917,64 бита вместо 840.

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

Основной цикл подгонки во многом основан на алгоритме дизеринга Direct Binary Seach (где пиксели случайным образом меняются местами или переворачиваются до тех пор, пока не будет получен лучший полутон). Вычисление энергии представляет собой простое среднеквадратичное расстояние, но сначала я выполняю медианный фильтр 5x5 на исходном изображении. Размытие по Гауссу, вероятно, лучше отражало бы поведение человеческого глаза, но я не хотел терять резкие края. Я также решил не использовать имитацию отжига или другие методы, которые сложно настроить, потому что у меня нет месяцев на калибровку процесса. Таким образом, флаг «качества» просто представляет количество итераций, которые выполняются в каждой точке перед завершением работы кодера.

http://caca.zoy.org/raw-attachment/wiki/img2twit/Mona_Lisa_scaled.jpg http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter2.png

苉憗揣嶕繠剳腏篮濕茝霮墧蒆棌杚蓳縳樟赒肴飗噹砃燋任朓峂釰靂陴貜犟掝喗讄荛砙矺敨鷾瓔亨髎芟氲簵鸬嫤鉸俇激躙憮鄴甮槺骳佛愚猪駪惾嫥綖珏矯坼堭颽箽赭飉訥偁箝窂蹻熛漧衆橼愀航玴毡裋頢羔恺墎嬔鑹楄瑥鶼呍蕖抲鸝秓苾绒酯嵞脔婺污囉酼俵菛琪棺则辩曚鸸職銛蒝礭鱚蟺稿纡醾陴鳣尥蟀惘鋁髚忩祤脤养趯沅况

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

У меня также есть небольшие видеоролики об эволюции состояния кодировщика из случайного начального состояния и из "хорошего" начального состояния.

Изменить: вот как метод сжатия сравнивается с JPEG. Слева изображение джамо размером более 536 байт. Справа Мона Лиза сжала до 534 байтов с помощью метода, описанного здесь (байты, упомянутые здесь, относятся к байтам данных, поэтому игнорируются биты, потраченные впустую из-за использования символов Unicode):

http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona.jpg http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona2.png

Изменить: просто заменил текст CJK на новейшие версии изображений.

person sam hocevar    schedule 24.05.2009
comment
На самом деле мне не нужно иметь возможность запускать код (я поместил часть о его запуске в рекомендации, как предложение, а не правила); Я бы предпочел иметь возможность запускать его, но я буду судить об этом больше по качеству генерируемых вами изображений, кода и любых интересных трюков или алгоритмов. Если я хочу запустить его, а для этого требуются пакеты, которых у меня нет или которые я не хочу устанавливать в моей основной системе, я могу просто загрузить экземпляр Amazon EC2 и установить его. Пока вы работаете с библиотеками, которые упакованы для одного из основных дистрибутивов, я смогу запустить его. Не стесняйтесь использовать CGAL. - person Brian Campbell; 25.05.2009
comment
Хорошо, вот мое решение (исходный код): caca.zoy.org/ browser / libpipi / trunk / examples / img2twit.cpp Моя попытка объяснения и несколько примеров находятся по адресу caca.zoy.org/wiki/img2twit - person sam hocevar; 25.05.2009
comment
Здорово! Это первое полное решение. Как вы думаете, можете ли вы отредактировать свой ответ (тот, в котором вы задали свой первый вопрос), включив в него некоторые или все объяснения и одно или два примера изображений? Намного приятнее иметь его здесь встроенным, чем ссылаться на него из комментария. - person Brian Campbell; 26.05.2009
comment
Мне очень нравится твое решение. Вам следует попробовать уменьшить количество значений, присваиваемых синему каналу, поскольку человеческий глаз не может хорошо различать синий цвет: nfggames.com/games/ntsc/visual.shtm; это позволит вам получить больше деталей за счет потери некоторой информации о цвете. Или, может быть, присвоить ему зеленый цвет? - person rpetrich; 26.05.2009
comment
Хорошая точка зрения. Я пробовал несколько вариантов этой идеи (см. Комментарии перед определением RANGE_X), но не очень тщательно. Как видите, использование 5 синих значений вместо 6 увеличивало ошибку немного меньше, чем использование 7 значений зеленого, уменьшало ее. Я не пробовал делать и то, и другое из-за лени. Еще одна проблема, с которой я столкнулся, заключается в том, что у меня нет очень хорошей функции обработки ошибок. В настоящее время я использую ∑ (∆r² + ∆g² + ∆b²) / 3, который работает нормально. Я попробовал ∑ (0,299∆r² + 0,587∆g² + 0,114∆b²), основанный (без физического обоснования) на YUV-компоненте, но он оказался слишком терпимым с синими ошибками. Я постараюсь найти статьи по этому поводу. - person sam hocevar; 26.05.2009
comment
Фактически, это 536-байтовый jpeg джамо; Я только что отредактировал его ответ, чтобы улучшить форматирование. - person Brian Campbell; 26.05.2009
comment
Выглядит очень красиво, но я очень разочарован. img2twit? Действительно? В САМОМ ДЕЛЕ? Это все, что вы могли придумать? Что случилось с вашим литературным, поэтическим гением? Я ожидал, что что-то увековечит великую родословную libcaca, libcucul, libpipi и toilet. (Как насчет pcul, утилиты сжатия изображений для построчного ведения блогов?) - person niXar; 26.05.2009
comment
@ Брайан: ой, я соответствующим образом переатрибутирую. @niXar: ты прав. У меня уже есть более подходящее имя, но это семейный сайт. - person sam hocevar; 26.05.2009
comment
Какое приложение я могу использовать для просмотра ваших фильмов в формате .ogm? - person An̲̳̳drew; 27.05.2009
comment
@Andrew: VLC должен работать, и MPlayer тоже. Если вы работаете в Windows и хотите использовать свой обычный проигрыватель, я считаю, что FFdshow может помочь (это кодек DirectShow, охватывающий множество кодеков с открытым исходным кодом). - person sam hocevar; 27.05.2009
comment
@rpetrich: Я модифицировал программу, чтобы она динамически увеличивала диапазоны r / g / b, пока доступно достаточно бит. Это гарантирует, что мы никогда не тратим больше 13 бит во всем битовом потоке (но на практике это обычно 1 или 2). И изображения выглядят немного лучше. - person sam hocevar; 27.05.2009
comment
@Sam у вас есть изображения до и после этого последнего изменения? - person Brian Campbell; 28.05.2009
comment
@Brian: Боюсь, что я сломал что-то еще в процессе, собирая все части вместе. Я исправлю это сегодня вечером после работы и выложу новые изображения (хотя не задерживайте дыхание, улучшение не является новаторским). - person sam hocevar; 28.05.2009
comment
Похоже, ваш метод битовой упаковки - это вариант арифметического кодирования без вероятностной части. Вероятно, вы могли бы улучшить качество, фактически используя арифметическое кодирование (или, по крайней мере, уменьшив размер вывода) - person derobert; 29.05.2009
comment
@derobert: проблема в том, что если арифметическое кодирование сэкономит мне биты, я не буду знать, сколько битов, пока не будет выполнено сжатие, и я не смогу использовать эти биты, если я не сделаю еще один прогон сжатия, что вполне может не сохраните любые биты ... - person sam hocevar; 29.05.2009

arrow_upward
45
arrow_downward

Нижеследующее не является официальным заявлением, поскольку мое программное обеспечение никоим образом не адаптировано для указанной задачи. DLI можно описать как оптимизирующий кодек изображений с потерями общего назначения. Это рекордсмен PSNR и MS-SSIM для сжатия изображений, и я подумал, что было бы интересно посмотреть, как он работает для этой конкретной задачи. Я использовал предоставленное эталонное изображение Моны Лизы и уменьшил его до 100x150, а затем использовал DLI, чтобы сжать его до 344 байтов.

http://i40.tinypic.com/2md5q4m.png

Для сравнения со сжатыми образцами JPEG и IMG2TWIT я также использовал DLI для сжатия изображения до 534 байта. Размер JPEG составляет 536 байтов, а IMG2TWIT - 534 байта. Изображения были увеличены примерно до одинакового размера для удобства сравнения. JPEG - левое изображение, IMG2TWIT - центральное, а DLI - правое изображение.

http://i42.tinypic.com/302yjdg.png

На изображении DLI удалось сохранить некоторые черты лица, в первую очередь знаменитую улыбку :).

person Community    schedule 29.05.2009
comment
Ой. Вышеупомянутое следует приписать Деннису Ли, который представил его изначально. Я просто отредактировал его, чтобы встроить изображения в строку и ссылку на ссылку, которую я нашел в Google. И я должен сказать, вау, я впечатлен сжатием. Мне нужно будет проверить сжатие DLI. - person Brian Campbell; 29.05.2009
comment
Кодирование изображения DLI в Unicode определенно даст наилучшие результаты. Не могли бы вы также показать результаты для 251 байта данных? Вот сколько байтов информации содержится в 140 символах CJK. - person sam hocevar; 29.05.2009
comment
Кстати, автор DLI отмечает долгое время обработки. Поскольку я не могу запустить его программу, не могли бы вы дать нам приблизительные цифры времени сжатия? - person sam hocevar; 29.05.2009
comment
При использовании AMD Athlon64 2,4 ГГц сжатие изображения Моны Лизы размером 100x150 занимает 38 секунд, а декомпрессия - 6 секунд. Сжатие до 251 байта сложнее, качество вывода значительно снижается. Используя эталонное изображение Моны Лизы, я уменьшил его до 60x91, затем использовал DLI, чтобы сжать его до 243 байтов (ближе всего к 251 без перехода). Это результат i43.tinypic.com/2196m4g.png Детализация не близка к 534-байтовому DLI, хотя битрейт уменьшился только на ~ 50%. Однако структура изображения сохранилась довольно хорошо. - person ; 30.05.2009
comment
Решил упростить сравнение 250 байт сжатых отсчетов. 243-байтовый DLI был увеличен и помещен рядом с образцом IMG2TWIT. IMG2TWIT слева, DLI справа. Вот изображение i40.tinypic.com/30ndks6.png - person ; 30.05.2009
comment
Это очень впечатляет. Я не знал о DLI, будем надеяться, что этот парень выпустит некоторую информацию о том, что он делает. Последний вопрос: позволяет ли DLI указывать целевой размер, или вам нужно попытаться угадать, нужно ли вам заданное количество байтов? - person sam hocevar; 30.05.2009
comment
DLI использует такой параметр качества, как JPEG, поэтому, если требуется целевой размер вывода, необходим метод проб и ошибок. - person ; 30.05.2009
comment
@Dennis. Есть ли у вас доступный исходный код или какие-либо записи об используемых методах? Я очень впечатлен уровнем детализации, который вы здесь получили, и хотел бы получить дополнительную информацию о том, как это работает. - person Brian Campbell; 30.05.2009
comment
@Sam Если вы хотите запустить dli, я обнаружил, что он отлично работает под Wine. - person Brian Campbell; 31.05.2009
comment
К сожалению, исходный код и описание технологии DLI в настоящее время недоступны. С другой стороны, я был удивлен, что вы выбрали фрактальное решение вместо IMG2TWIT. Лично я предпочитаю решение и качество вывода IMG2TWIT, поэтому я с нетерпением жду подробностей вашей оценки. - person ; 31.05.2009

arrow_upward
21
arrow_downward

Общий обзор моего решения был бы таким:

  1. I start with calculating the maximum amount of raw data that you can fit into 140 utf8 characters.
    • (I am assuming utf8, which is what the original website claimed twitter stored it's messages in. This differs from the problem statement above, which asks for utf16.)
    • Используя этот часто задаваемый вопрос по utf8, я подсчитал, что максимальное количество бит, которое вы можете закодировать в одном символе utf8, составляет 31 бит. Для этого я бы использовал все символы из диапазона U-04000000 - U-7FFFFFFF. (1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, есть 31 x, поэтому я мог кодировать до 31 бит).
    • 31 бит, умноженный на 140 символов, равняется 4340 битам. Разделите это на 8, чтобы получить 524,5, и округлите до 542 байта.
    • (Если мы ограничимся utf16, тогда мы сможем хранить только 2 байта на символ, что будет равняться 280 байтам).
  2. Compress the image down using standard jpg compression.
    • Resize the image to be approximately 50x50px, then attempt to compress it at various compression levels until you have an image that is as close to 542 bytes as possible without going over.
    • Это пример Мона Лизы, сжатой до 536 байт.
  3. Encode the raw bits of the compressed image into utf-8 characters.
    • Replace each x in the following bytes: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, with the bits from the image.
    • Эта часть, вероятно, будет той частью, где нужно будет написать большую часть кода, потому что в настоящее время нет ничего, что бы это делало.

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

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

Еще одно важное замечание: если будет решено, что предпочтительной кодировкой является utf16, то это решение развалится. jpegs не работает при сжатии до 280 байт. Хотя, может быть, для этой конкретной постановки проблемы существует лучший алгоритм сжатия, чем jpg.

person Stephen McCarthy    schedule 21.05.2009
comment
Я сейчас на работе, но окончательно внедряю это решение, когда вернусь домой. - person Paulo Santos; 21.05.2009
comment
Из моих экспериментов кажется, что UTF-16 - это действительно то, как Twitter считает символы; Символы BMP считаются как 1, а символы более высокого уровня считаются как 2. Это не задокументировано, но именно так их счетчик символов JavaScript считается при вводе в поле ввода. Это также упоминается в комментариях в исходной ветке. Я не пробовал отправлять через API, чтобы узнать, не работает ли счетчик; если это так, я обновлю проблему с учетом фактических ограничений. Однако вы вряд ли сможете использовать произвольный UTF-8, поскольку многие из этих более длинных последовательностей, которые вы можете кодировать, не являются допустимыми Unicode. - person Brian Campbell; 21.05.2009
comment
После тестирования с их API выяснилось, что они подсчитывают по символам Unicode (кодовым точкам), а не по единицам кода UTF-16 (это счетчик символов JavaScript, который считается через UTF-16, поскольку, очевидно, именно это и делает метод длины JavaScript) . Так что вы можете получить там немного больше информации; допустимые символы Unicode находятся в диапазоне от U + 0000 до U + 10FFFF (немного больше 20 бит на символ; 2 ^ 20 + 2 ^ 16 возможных значений на символ). UTF-8 позволяет кодировать больше значений, чем разрешено в Unicode, поэтому, если вы ограничитесь Unicode, вы можете получить около 350 байтов пространства, а не 542. - person Brian Campbell; 21.05.2009
comment
Эта 536-байтовая Мона Лиза выглядит на удивление хорошо, учитывая экстремальное сжатие! - person Chris; 22.05.2009
comment
Похоже на MonaCyclops - что-то вроде Uni-browe .... ‹joke› ;-) - person Gineer; 22.05.2009
comment
В настоящее время мы можем кодировать 129775 различных (назначенных, неконтролирующих, не частных) символов Unicode. Если мы ограничимся этим подмножеством, это всего 2377 бит или 297 байт. Код здесь: porg.es/blog/what-can-we -fit-in-140-символов - person porges; 27.05.2009
comment
Сколько BPP вы сделали Мона Лиза? - person Chris S; 29.05.2009

arrow_upward
20
arrow_downward

Хорошо, я опаздываю в игру, но тем не менее свой проект сделал.

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

Функции:

  • чистый Lua. Работает везде, где работает интерпретатор Lua.
  • использует формат netpbm P3
  • поставляется с полным набором модульных тестов
  • сохраняет исходный размер изображения

Mis-feautres:

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

Вот пример твита, который представляет Лену: 犭 楊 谷 杌 蒝 匘 玏 扝 匮 俄 归 晃 摈 硰 划 刀 萕 码 摃 蜁 耂 簜 偑 婊 忈 義 襠 凁 岂 掂 戇 耔 攋 斘 眐 奡 萛 狂 昸 栃 兡 塅 受 橯 戞 优 猫 僘 瑩 吱 賾 卣 腠 綍 蝘 猕 屐 稱 悡 ​​噩 压 罍 尕 厥 虲 兙 罨 縨 炘 排 叁 抠 堃 從 弅 宑 簫 柢 橙 拃 缩 昔 儻 舭 勵 癳 冂 囤 榕 兠 摈 侑 蒖 孂 埮 璐 哠 眛 嫡 訜 厇 廩 焛 瀻 严 啘 刱 垫 仔

исходная леназакодирована Лена

Код находится в репозитории Mercurial на bitbucket.org. Посетите http://bitbucket.org/tkadlubo/circles.lua

person Community    schedule 22.08.2010
comment
Потрясающий! Создает аккуратные художественные изображения. Я рад, что люди все еще работают над этим; Было очень весело увидеть все разные подходы. - person Brian Campbell; 22.08.2010
comment
Я бы хотел, чтобы это использовалось как прозрачное наложение на оригинал, дающее что-то вроде эффекта боке. - person Nick Radford; 20.07.2011

arrow_upward
19
arrow_downward

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

Основная идея, лежащая в основе моей, заключается в следующем:

  1. Уменьшите масштаб изображения по шкале серого таким образом, чтобы было всего 16 различных оттенков.
  2. Преформ РЛЭ на изображении
  3. Упакуйте результаты в символы UTF-16
  4. Предварительно сформировать RLE для сжатых результатов, чтобы удалить любое дублирование символов.

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

乤乤万乐唂伂倂倁企儂2企倁3企倁2企伂8企伂3企伂5企倂倃伂倁3企儁企2伂倃5企倁3企倃4企倂企倁企伂2企伂5企倁企伂쥹皗鞹鐾륶䦽阹럆䧜椿籫릹靭욶옷뎷歩㰷歉䴗鑹㞳鞷㬼獴鏙돗鍴祳㭾뤶殞焻�乹Ꮛ靆䍼

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

Что касается времени выполнения, для небольших изображений код выполняется очень быстро, около 55 мс для предоставленных образцов изображений, но время действительно увеличивается с большими изображениями. Для эталонного изображения Лены 512x512 время обработки составило 1182 мс. Я должен отметить, что весьма высока вероятность того, что сам код не очень оптимизирован для производительности (например, все работает как Bitmap), поэтому время может немного уменьшиться после некоторого рефакторинга.

Не стесняйтесь предлагать мне любые предложения о том, что я мог бы сделать лучше или что может быть не так с кодом. Полный список времени выполнения и пример вывода можно найти по следующему адресу: http://code-zen.info/twitterimage/

Обновить один

Я обновил код RLE, используемый при сжатии строки твита, чтобы выполнить базовый анализ и, если да, использовать его для вывода. Это работает только для пар числовых значений, но сохраняет пару символов данных. Время работы примерно такое же, как и качество изображения, но твиты, как правило, немного меньше. Я буду обновлять таблицу на сайте по мере завершения тестирования. Ниже приводится один из примеров строк твита, опять же для уменьшенной версии Лены:

乤乤万乐唂伂倂倁企儂2企倁3企倁ウ伂8企伂エ伂5企倂倃伂倁グ儁企2伂倃ガ倁ジ倃4企倂企倁企伂ツ伂ス倁企伂쥹皗鞹鐾륶䦽阹럆䧜椿籫릹靭욶옷뎷歩㰷歉䴗鑹㞳鞷㬼獴鏙돗鍴祳㭾뤶殞焻�乹Ꮛ靆䍼

Обновление два

Еще одно небольшое обновление, но я изменил код, чтобы упаковать цветовые оттенки в группы по три, а не четыре, это занимает немного больше места, но если я чего-то не упускаю, это должно означать, что «странные» символы больше не появляются там, где цвет данные есть. Кроме того, я немного обновил сжатие, чтобы теперь оно могло воздействовать на всю строку, а не только на блок подсчета цветов. Я все еще тестирую время выполнения, но оно, похоже, номинально улучшилось; однако качество изображения остается прежним. Далее следует последняя версия твита Лены:

2乤万乐唂伂倂倁企儂2企倁3企倁ウ伂8企伂エ伂5企倂倃伂倁グ儁企2伂倃ガ倁ジ倃4企倂企倁企伂ツ伂ス倁企伂坹坼坶坻刾啩容力吹婩媷劝圿咶坼妛啭奩嗆婣冷咛啫凃奉佶坍均喳女媗决兴宗喓夽兴唹屹冷圶埫奫唓坤喝奎似商嗉乃

http://code-zen.info/twitterimage/images/stackoverflow-logo.bmp http://code-zen.info/twitterimage/images/cornell-box.bmp http://code-zen.info/twitterimage/images/lena.bmp http://code-zen.info/twitterimage/images/mona-lisa.bmp

person Community    schedule 30.05.2009
comment
Отлично, спасибо за запись! Оттенки серого на самом деле неплохо подходят для большинства из них, хотя Лену сложно разобрать. Я искал ваш источник, но получил 404; не могли бы вы убедиться, что это там наверху? - person Brian Campbell; 30.05.2009
comment
Дважды проверьте это сейчас, я обновлял сайт, так что вы могли поймать меня между обновлениями. - person rjzii; 30.05.2009
comment
Ага, я могу скачать это сейчас. Теперь, конечно, мне нужно выяснить, смогу ли я заставить Mono его скомпилировать. - person Brian Campbell; 30.05.2009
comment
Ага! Работает под Mono, я скомпилировал с помощью gmcs -r System.Drawing TwitterImage.cs Program.cs и запустил с моно TwitterImage.exe encode lena.png lena.txt - person Brian Campbell; 31.05.2009
comment
Прохладный! Я дважды проверил, что библиотеки, которые я использую, указаны для Mono, но я еще не работал с Mono, поэтому я не был уверен, будет ли это работать или нет. - person rjzii; 31.05.2009
comment
Образцы изображений не видны - person Jakub Narębski; 18.06.2009

arrow_upward
15
arrow_downward

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

http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

Было бы интересно реализовать программу, но я ее пропущу.

person CiscoIPPhone    schedule 21.05.2009

arrow_upward
12
arrow_downward

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

То, что не упоминается явно (но мое личное правило было моим), заключается в том, что вы должны иметь возможность выбрать твитированное сообщение в своем браузере, скопировать его в буфер обмена и вставить в поле ввода текста вашего декодера, чтобы он мог его отобразить. Конечно, вы также можете сохранить сообщение в виде текстового файла и прочитать его или написать инструмент, который обращается к Twitter API и отфильтровывает любое сообщение, которое выглядит как код изображения (специальные маркеры? подмигнуть подмигнуть). Но по правилу сообщение должно пройти через Twitter, прежде чем вы сможете его расшифровать.

Удачи с 350 байтами - я сомневаюсь, что вы сможете их использовать.

person Quasimondo    schedule 22.05.2009
comment
Да, я добавил рубрику оценки, которая указывает, что более строгие ограничения на набор символов предпочтительны, но не обязательны. Я хотел бы иметь правило, которое требует, чтобы сообщения проходили через Twitter без повреждений, но это потребует много проб и ошибок, чтобы выяснить точные детали того, что работает, и я хотел оставить некоторую свободу действий, чтобы позволить творческое использование кодовое пространство. Итак, единственное требование в моей задаче - 140 действительных символов Unicode. Кстати, спасибо, что заглянули! Мне очень нравится ваше решение, и я хочу посмотреть, сможет ли кто-нибудь из кибицеров на самом деле его улучшить. - person Brian Campbell; 23.05.2009

arrow_upward
12
arrow_downward

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

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

Добавьте немного сжатия к вышесказанному, и это может начать выглядеть жизнеспособным ...

Хороший!!! Теперь вы, ребята, вызвали у меня интерес. До конца дня никаких работ не будет ...

person Gineer    schedule 22.05.2009
comment
s / peaked / piqued / g - person eleven81; 23.05.2009
comment
Мне нравится идея трех изображений, должна быть возможность реализовать такую ​​идею в твиттере, и результат будет неплохим. - person Makis; 29.05.2009

arrow_upward
9
arrow_downward

Что касается части этой проблемы, связанной с кодированием / декодированием. base16b.org - это моя попытка указать стандартный метод безопасного и эффективного кодирования двоичных данных в высших плоскостях Unicode.

Некоторые особенности:

  • Использует только частные пользовательские области Unicode
  • Кодирует до 17 бит на символ; почти в три раза эффективнее, чем Base64
  • Предоставляется эталонная реализация кодирования / декодирования Javascript.
  • Включены некоторые образцы кодировок, в том числе Twitter и Wordpress.

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

person Community    schedule 07.08.2009

arrow_upward
8
arrow_downward

Интересна идея хранить кучу эталонных изображений. Было бы так неправильно хранить, скажем, 25 МБ образцов изображений, а кодировщик попытался бы составить изображение, используя их биты? С такой крохотной трубой оборудование на обоих концах по необходимости будет намного больше, чем объем передаваемых данных, так в чем же разница между 25 МБ кода, 1 МБ кода и 24 МБ данных изображения?

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

person Community    schedule 27.05.2009
comment
Это было бы хорошо, если у вас есть фиксированный конечный объем данных на любой конечной точке. Конечно, вам нужно будет продемонстрировать, что он работает с изображениями, которых нет в обучающем наборе, как и любая статистическая задача обработки естественного языка. Я бы хотел увидеть что-то, что использует статистический подход к кодированию изображений. - person Brian Campbell; 27.05.2009
comment
Я, например, хотел бы увидеть переделку Моны Лизы, используя только фан-арт Бобы Фетта в качестве источника. - person Nosredna; 27.05.2009
comment
Я согласен - подход фотомозаики, кажется, находится в рамках правил, и было бы чрезвычайно интересно увидеть, как кто-то наносит удар. - person An̲̳̳drew; 27.05.2009

arrow_upward
8
arrow_downward

Глупая идея, но sha1(my_image) приведет к "идеальному" представлению любого изображения (без учета коллизий). Очевидная проблема заключается в том, что процесс декодирования требует чрезмерного количества перебора.

1-битный монохромный был бы немного проще ... Каждый пиксель становится 1 или 0, так что у вас будет 1000 бит данных для изображения 100 * 100 пикселей. Поскольку хэш SHA1 состоит из 41 символа, мы можем вместить три в одно сообщение, нужно только перебрать 2 набора из 3333 бит и один набор из 3334 (хотя даже это, вероятно, все еще чрезмерно)

Это не совсем практично. Даже с 1-битным изображением фиксированной длины 100 * 100 пикселей есть ..., если я не ошибаюсь, 49995000 комбинаций или 16661667 при разделении на три.

def fact(maxu):
        ttl=1
        for i in range(1,maxu+1):
                ttl=ttl*i
        return ttl

def combi(setsize, length):
    return fact(length) / (fact(setsize)*fact(length-setsize))

print (combi(2, 3333)*2) + combi(2, 3334)
# 16661667L
print combi(2, 10000)
# 49995000L
person Community    schedule 30.05.2009
comment
Проблема с sha1 (my_image) заключается в том, что если вы потратите время на его грубое форсирование, вы, вероятно, обнаружите, что человек много столкновений, прежде чем вы найдете реальное изображение; и, конечно, грубая форсировка sha1 в значительной степени вычислительно невыполнима. - person Brian Campbell; 31.05.2009
comment
Даже лучше, чем сжатие SHA1: мой алгоритм сжатия flickr! Шаг 1: загрузите изображение на flickr. Шаг 2: разместите ссылку на него в твиттере. Тадда! Используется всего 15 байт! - person niXar; 19.06.2009
comment
niXar: Нет, правило 3.4: Процесс декодирования не может иметь доступа к любому другому выходу процесса кодирования, кроме выходных данных, указанных выше; то есть вы не можете куда-то загрузить изображение и вывести URL-адрес для загрузки процесса декодирования или что-нибудь в этом роде. - person dbr; 20.06.2009
comment
Я знаю, я был саркастичен. - person niXar; 26.06.2009

arrow_upward
8
arrow_downward

Вот эта компрессия хороша.

http://www.intuac.com/userport/john/apt/

http://img86.imageshack.us/img86/4169/imagey.jpg

Я использовал следующий командный файл:

capt mona-lisa-large.pnm out.cc 20
dapt out.cc image.pnm
Pause

Результирующий размер файла составляет 559 байт.

person Community    schedule 19.07.2009

arrow_upward
0
arrow_downward

Идея: можно ли использовать шрифт в качестве палитры? Попробуйте разбить изображение на серию векторов, пытаясь описать их комбинацией наборов векторов (каждый символ, по сути, является набором векторов). Это использование шрифта в качестве словаря. Я мог бы, например, использовать l для вертикальной линии и - для горизонтальной линии? Просто идея.

person Community    schedule 17.04.2011