[解決済み] Twitter画像エンコードに挑戦【終了しました

質問

百聞は一見にしかず、では140文字でどれだけの写真を収めることができるのでしょうか？

備考 : 皆さん、お待たせしました。懸賞金の締め切りが迫ってきました。 ブージャムさんのエントリー をギリギリで抑えて サム・ホセバーの . 詳しいメモを書き上げたら、また掲載します。もちろん、皆さんはこれからも気軽に解答を提出したり、解答を改良して投票に加えたりしてください。応募してくれた皆さん、ありがとうございました。この大会は、私にとってとても楽しいものでした。

私が出会ったのは この興味深い記事 Twitterのコメントに画像を圧縮しようとすることについて、そのスレッドでたくさんの人たち（と Redditのスレッド という提案がありました。そして、エンコーディングに関する彼らのアイデアが、限られたスペースでより詳細な情報を提供することにつながることを示すことができるのです。

140文字のTwitterメッセージに画像をエンコードし、再び画像にデコードする汎用的なシステムを考え出すことに挑戦します。ユニコード文字が使えるので、1文字あたり8ビット以上得られます。しかし、ユニコード文字を使用するとしても、画像を非常に小さなスペースに圧縮する必要があります。これは確実に非可逆圧縮であり、それぞれの結果がどの程度良く見えるかについて主観的な判断が必要になります。

原作者が出した結果がこちらです。 クワジモンド の下でライセンスされている）。 クリエイティブ・コモンズ 表示 - 非商用ライセンス ):

もっとうまくできる？

ルール

1. プログラムには2つのモードが必要です。 エンコーディング と デコード .
2. いつ エンコーディング :
   1. あなたのプログラムは、任意の合理的な方法でグラフィックを入力として受けなければなりません。 ラスター グラフィック形式を選択します。でサポートされているラスターフォーマットであれば、どのようなものでも良いということにします。 ImageMagick はリーズナブルとカウントされます。
   2. あなたのプログラムは、140以下のユニコードコードポイントで表現できるメッセージを出力しなければなりません。 U+0000 - U+10FFFF の場合、非文字を除く ( U+FFFE , U+FFFF , U+ n FFFE , U+ n FFFF ここで n は 1 - 10 16進数で、範囲は U+FDD0 - U+FDEF ) とサロゲートコードポイント ( U+D800 - U+DFFF ). それは、あなたが選んだ合理的なエンコーディングで出力されるかもしれません; でサポートされている任意のエンコーディング。 GNU iconv は合理的であるとみなされ、あなたのプラットフォームのネイティブエンコーディングまたはロケールエンコーディングが良い選択となる可能性があります。参照 ユニコード注釈 詳細は下記をご覧ください。
3. いつ デコード :
   1. の出力を入力とするプログラムでなければなりません。 エンコーディング モードを使用します。
   2. あなたのプログラムは、上記で定義されたように、あなたが選んだ合理的なフォーマットで画像を出力しなければなりませんが、出力のためのベクターフォーマットもOKです。
   3. 出力される画像は入力画像の近似値であるべきで、入力画像に近ければ近いほどよい。
   4. つまり、画像をどこかにアップロードして、デコーディングプロセスがダウンロードするためのURLを出力するとか、そんな馬鹿げたことはできないのです。

4. ユーザーインターフェースの一貫性を保つために、あなたのプログラムは次のように動作する必要があります。

   1. プログラムは、適切なインタプリタがあるプラットフォームで実行可能な設定にできるスクリプト、または実行形式にコンパイルできるプログラムである必要があります。
   2. プログラムは、最初の引数として、以下のいずれかを取る必要があります。 encode または decode をクリックして、モードを設定します。

   3. プログラムは、以下のいずれか、または複数の方法で入力を受け付ける必要があります（ファイル名を受け付けるものを実装した場合、ファイル名がない場合はstdinとstdoutから読み書きしてもかまいません）。

      1. 標準入力から入力を受け、標準出力に出力する。

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

      2. 第2引数で指定されたファイルから入力を受け取り、第3引数で指定されたファイルに出力を生成する。

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

5. 解決策については、投稿してください。
   1. あなたのコード全体、または他の場所でホストされているコードへのリンク (非常に長い場合、またはコンパイルに多くのファイルを必要とする場合など)。
   2. コードからすぐにはわからない場合、またはコードが長く、人々が要約に興味を持つような場合、その動作の説明。
   3. 元画像、圧縮されたテキスト、デコードされた画像の例です。
   4. 他の人が持っていたアイデアを基にする場合、その人の名前を明記してください。他人のアイデアの改良を試みるのは良いのですが、あなたは 必ず を付けてください。

ガイドライン

これらは基本的に、破ってもよいルール、提案、または採点基準です。

1. 美観は重要です。私が審査し、他の人が審査することを提案するのは、以下の点による。
   1. 出力された画像の見栄え、原画にどれだけ似せているか。
   2. テキストの見栄え 本当に賢い圧縮スキームがあれば、完全にランダムなゴブレットもOKですが、画像を多言語の詩に変えるとか、そういう賢い答えも見てみたいです。なお、原文の作者は、漢字だけの方が見栄えが良いので、漢字だけにしました。
   3. 興味深いコードと巧妙なアルゴリズムは常に良いものです。私は短くて要領の良い、明快なコードが好きですが、本当に賢い複雑なアルゴリズムも、良い結果を生むのであればOKです。
2. スピードも重要ですが、画像をいかにうまく圧縮するかということほど重要ではありません。何日も遺伝的アルゴリズムを走らせるようなプログラムよりも、コンマ1秒で画像を変換できるプログラムの方がいい。
3. 私は、品質がある程度同等であれば、長いソリューションよりも短いソリューションを好みます。
4. プログラムは、Mac OS X、Linux、Windowsのいずれかで自由に利用できる実装を持つ言語で実装してください。私はプログラムを実行できるようにしたいのですが、もしあなたが素晴らしいソリューションを持っていて、それが MATLAB とかでもいいんですけどね。
5. プログラムはできるだけ一般的なものであるべきです。できるだけ多くの異なる画像に対して動作すべきですが、あるものは他のものより良い結果を生むかもしれません。特に
   1. プログラムにいくつかの画像を組み込んで、マッチングして参照を書き込み、デコード時にマッチングした画像を生成するというのはかなりいい加減で、いくつかの画像しかカバーできないでしょう。
   2. 単純で平らな幾何学的形状の画像を取り込んで、あるベクトルプリミティブに分解するプログラムはかなり気の利いたものだが、もしある複雑さを超える画像で失敗するなら、おそらく十分な一般性がないのだろう。
   3. 特定の固定アスペクト比の画像しか撮影できないが、その画像をうまく処理するプログラムもOKだが、理想的ではない。
   4. カラー画像よりも白黒画像の方が、より小さなスペースに多くの情報を取り込むことができることが分かるかもしれません。一方、白黒画像は適用できる画像の種類が限られます。顔は白黒でうまく表現できますが、抽象的なデザインはあまりうまくいかないかもしれません。
   5. 出力画像は入力画像より小さくても、ほぼ同じ比率であれば全く問題ありません。元画像と比較するために画像を拡大縮小する必要があっても問題ありません。重要なのは、どのように見えるかです。
6. あなたのプログラムは、実際にTwitterを通過して、無傷で出てくるような出力を生成する必要があります。サポートされている文字の正確なセットに関する文書が見つからなかったので、これは規則というよりもガイドラインに過ぎませんが、おそらく制御文字、ファンキーな見えない結合文字、私用文字などは避けるべきでしょう。

採点ルーブリック

採用するソリューションを選ぶ際に、私がどのようにソリューションをランク付けするかの一般的なガイドとして、おそらく25点満点で評価するとします（これは非常に大雑把なもので、私が直接何かを採点するわけではありません、ただ基本ガイドラインとしてこれを使います）。

• 15点 様々な入力画像を再現するエンコード方式であること。これは主観的、美的な判断です。
  • 0は、全く機能しない、毎回同じ画像が返ってくる、など。
  • 5は、いくつかの画像をエンコードできるが、デコードされたバージョンは醜く、より複雑な画像では全く動作しない可能性があることを意味します。
  • 10は、幅広い種類の画像に対応し、見栄えの良い画像を生成し、時には見分けがつくこともあることを意味します。
  • 15は、ある画像の完全な複製を作成し、より大きく複雑な画像であっても、認識できるものを作成することを意味します。あるいは、よくわかるような画像は作れないが、明らかに原画に由来する美しい画像が得られることを意味する。
• 3点 Unicode文字セットの巧みな使用について
  • 0点：単純に許容されるすべての文字セットを使用した場合
  • 1ポイント：Twitterで転送しても安全な文字や、より幅広い場面で使える文字に限定して使用した場合
  • 漢字のみ、右から左への文字のみなど、テーマ別のサブセットを使用した場合は2点
  • 読みやすいテキストを生成したり、問題の画像と同じような文字を使用するなど、本当にすばらしいことをした場合は3点。
• 3点 巧みなアルゴリズムアプローチとコードスタイル
  • 0点：画像を縮小し、1ピクセルあたり1ビットとして扱い、それをbase64エンコードするためだけに1000行のコードがあるもの。
  • 標準的なエンコーディング技術を使用し、簡潔に書かれているものには1点。
  • 2ポイント：比較的新しいエンコーディング技術を導入しているもの、または驚くほど短くすっきりしているもの
  • 3点：実際に良い結果を出したワンライナー、またはグラフィックスエンコーディングの新境地を開いたもの（新境地を開くための点数が低いと思われる場合は、これほど良い結果は美的にも高得点となる可能性があることを思い出してください）。
• 2点 は、スピードのため。他の条件がすべて同じであれば、速い方が良いですが、上記の基準はすべて速度よりも重要です
• 1点 私はフリーソフトウェアを好むので、フリー（オープンソース）ソフトウェア上で実行されている場合（C#はMono上で実行されている限り、このポイントの対象となることに注意してください、同様にMATLABコードはGNU Octave上で実行されていれば対象となるでしょう）。
• 1点 実際にすべてのルールに従った場合。このルールは少し大きく複雑になったので、細かいところを1つでも間違えている他の良い答えも受け入れると思いますが、実際にすべてのルールに従った解答には追加点をあげたいと思います。

参考画像

参考画像が欲しいという声もありました。小さいサイズの画像はここに埋め込んでありますが、必要であればすべて大きいサイズの画像にリンクしています。

賞品

を提供しています。 500リップバウンティ (さらにStackOverflowが負担する50ドル) 上記の基準に基づいて、私が最も気に入ったソリューションに贈られます。もちろん、他の皆さんも同様に、お気に入りのソリューションに投票することをお勧めします。

締切に関する注意事項

このコンテストは、懸賞金がなくなるまで、5月30日（土）午後6時頃まで行われます。正確な終了時刻は言えませんが、午後5時から7時くらいになるかもしれません。午後2時までに提出されたすべての作品に目を通すことを保証し、午後4時までに提出されたすべての作品に目を通すよう最善を尽くしますが、それ以降に提出された作品については、私が判断を下す前に公正な目で見る機会がないかもしれません。また、早く応募すればするほど、私が最適な解決策を選ぶための投票のチャンスが増えるので、締め切り間際に応募するのではなく、早めに応募するようにしてください。

ユニコードに関する注意事項

また、どのようなUnicode文字が許可されているのか、正確に把握することに若干の混乱があったようです。Unicodeのコードポイントの範囲は以下の通りです。 U+0000 から U+10FFFF . オープンなデータ交換において、ユニコード文字として決して有効でないコードポイントがいくつか存在します。 非文字 と サロゲートコードポイント . 非文字は ユニコード規格5.1.0 16.7項 を値として U+FFFE , U+FFFF , U+ n FFFE , U+ n FFFF ここで n は 1 - 10 16進数で、範囲は U+FDD0 - U+FDEF . これらの値は、アプリケーション固有の内部使用のために使用されることを意図しており、適合するアプリケーションは、処理するテキストからこれらの文字を取り除くことができる。サロゲートコードポイントは ユニコード規格5.1.0項3.8号 として U+D800 - U+DFFF したがって、これらのコードポイントをUTF-16の符号化方式で直接表現することは不可能であり、他の符号化方式で符号化することは無効である。したがって、このコンテストでは、以下の範囲から140個以下のユニコードコードポイントのシーケンスに画像をエンコードするプログラムを許可することにします。 U+0000 - U+10FFFF ただし、上記で定義されたすべての非文字とサロゲートペアは除く。

私は 好む のソリューションは、割り当てられた文字のみを使用し、さらに割り当てられた文字の巧妙なサブセットを使用したり、使用する文字セットで何か面白いことをしたりするものがよいでしょう。割り当てられた文字の一覧は ユニコード文字データベース ある文字は直接、ある文字は範囲の開始と終了としてのみリストアップされていることに注意してください。また、サロゲートコードポイントもデータベースに掲載されていますが、上記のように禁止されていることに注意してください。もしあなたが、出力するテキストをより面白くするために、文字の特定の性質を利用したいのであれば、以下のようなものがあります。 文字情報データベースの数々 などが利用できます。 名前付きコードブロックのリスト と 各種文字プロパティ .

Twitterは正確な文字セットをサポートしていないので、ある文字が余分にカウントされたり、ある文字が削除されたりして、Twitterで実際に動作しないソリューションについては、私は寛容に対応します。すべてのエンコードされた出力が、Twitterや他のマイクロブログサービス（例えば、"Mixi"）で問題なく転送できることが望ましいのですが、必須ではありません。 IDI.CA . Twitterは、<、>、&をエンティティエンコードして、それぞれ4文字、4文字、5文字とカウントすると書いてあるドキュメントを見たことがあります。

ヒントとリンク

• 規則における有効なユニコード文字の定義は、少し複雑です。CJK Unified Ideographs (U+4E00-U+9FCF) のような単一の文字ブロックを選択する方が簡単かもしれません。
• のように、既存の画像ライブラリを利用することもできます。 ImageMagick または Python イメージングライブラリ 画像処理に使用します。
• Unicode文字セットとその様々なエンコーディングについて理解する手助けが必要な場合は、以下を参照してください。 このクイックガイド または LinuxとUnixのUTF-8に関する詳細なFAQです。 .
• 早く提出すればするほど、私（や投票する人たち）がその解決策を見る時間が増えます。解答を改善した場合は編集することができます。私は、解答に最後に目を通したときの最新版を賞金の基準にします。
• もし、パースや書き込みが簡単な画像フォーマットが欲しいなら（そして、既存のフォーマットをそのまま使いたくないなら）、私がお勧めするのは PPM形式 . これはテキストベースのフォーマットで、非常に扱いやすく 画像処理 との変換が可能です。

どのように解決するのですか？

さて、これが私のだ。 nanocrunch.cpp と、その CMakeLists.txt ファイルを使用してビルドします。 CMakeを使用します。 に依存しています。 Magick++ ImageMagick API は、そのほとんどの画像処理に使用されています。 また、この API を使用するには GMP ライブラリで、文字列のエンコードにビグナム演算を使用しています。

私は、フラクタル画像圧縮をベースに、いくつかのユニークな工夫を凝らした解決策を考えました。 基本的な考え方は、画像を取り、そのコピーを50％に縮小し、様々な方向から、元の画像の重ならないブロックに似ている部分を探すというものです。 この検索には非常に強引なアプローチをとりますが、そのおかげで私の修正を導入しやすくなっています。

まず、90度の回転と反転だけでなく、45度の向きも考慮するようにしたことです。 1ブロックあたり1ビット多くなりますが、画質の向上には非常に有効です。

もうひとつは、各ブロックの色成分ごとにコントラストや明るさの調整を保存するのは、あまりにもコストがかかりすぎるということです。 その代わりに、高度に量子化された色（パレットには4×4×4＝64色しかない）を保存して、単純にある割合でブレンドするようにしています。 数学的には、これは各色ごとに明るさを変え、コントラストを一定に調整することと同じです。 残念ながら、これは色を反転させるための負のコントラストがないことも意味します。

各ブロックの位置、向き、色を計算したら、それをUTF-8文字列にエンコードする。 まず、ブロックテーブルのデータと画像サイズを表現するために、非常に大きなビグナムを生成します。 この方法は、Sam Hocevarのソリューションに似ています -- 位置によって異なる基数を持つ大きな数値のようなものです。

そして、利用可能な文字セットのサイズが何であれ、それをベースに変換します。 デフォルトでは、割り当てられたユニコード文字セットから、小文字、大文字、アンパサンド、制御文字、結合文字、サロゲート文字、プライベート文字を除いたものをフルに使用することになります。 これはきれいなものではありませんが、機能します。 デフォルトの表をコメントアウトして、代わりに印刷可能な7ビットASCII（やはり<、>、&文字を除く）またはCJK Unified Ideographsを選択することも可能です。 どの文字コードが利用できるかの表は、無効な文字と有効な文字が交互に並ぶランレングスでエンコードされて保存されています。

とにかく、ここにいくつかの画像と時間（私の古い3.0GHzのP4で測定したもの）があり、上記の完全に割り当てられたユニコード・セットで140文字に圧縮されています。 全体的に、私はこれらの結果がどうなったかにかなり満足しています。 もっと時間があれば、解凍された画像のブロック感を減らしたいところです。 それでも、極端な圧縮率の割には、かなり良い結果だと思います。 解凍された画像は少し印象的ですが、ビットがオリジナルとどのように対応しているかは比較的わかりやすいと思います。

Stack Overflow Logo (エンコードに 8.6s, デコードに 7.9s, 485 bytes)。
http://i44.tinypic.com/2w7lok1.png

Lena (エンコードに 32.8s, デコードに 13.0s, 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

編集：日中韓統一文字

Samがコメントで、これを日中韓で使うことについて質問しています。 これはモナリザを日中韓統合文字セットから139文字に圧縮したバージョンです。

http://i43.tinypic.com/2yxgdfk.png 咏璘驞凄脒鵚据蛥鸂拗朐朖辿韩瀦魷歪痫栘璯緍脲蕜抱揎頻蓼債鑡嗞靊寞柮嚛嚵籥聚隤慛絖銓馿渫櫰矍昀鰛掾撄粂敽牙稉擎蔍螎葙峬覧絀蹔抆惫冧笻哜搀澐芯譶辍澮垝黟偞媄童竽梀韠镰猳閺狌而羶喙伆杇婣唆鐤諽鷍鴞駫搶毤埙誖萜愿旖鞰萗勹鈱哳垬濅鬒秀瞛洆认気狋異闥籴珵仾氙熜謋繴茴晋髭杍嚖熥勳縿餅珝爸擸萿

これに使ったプログラムの先頭のチューニングパラメーターは 19, 19, 4, 4, 3, 10, 11, 1000, 1000. また、number_assignedとcodesの最初の定義をコメントアウトし、最後の定義をコメントアウト解除して、日中韓統合文字集合を選択するようにしました。