phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

Weathernews Programming Competition

概要

圧縮やRangeCoderの勉強のつもりで参加。

最終順位は26927.87点で20位。
といっても、一つ前との差分値をRangeCoderで圧縮しただけのコード。

問題

5分おき4観測分の衛星データが波長(16チャネル)ごとに64枚ある。このデータすべてを可能なかぎり圧縮・回答するプログラムを作成せよ。
スコアは、bz2の-9オプションでのサイズbase_comp_sizeに対して、「max(0.0, (1.0 - 圧縮サイズ/base_comp_size) * 10^6)」で計算される。

最終的に提出したアプローチ

  • 各画像ごとに、2byte単位で読み込み、直前の2byteとの差分を作成し、それをRangeCoderで圧縮

振り返り、というか勉強

ロスレスな(動)画像圧縮、ファイル圧縮あたりが関係しそうということで、そこらへんの勉強のために参加。
いくつかメモ。

画像形式

画像形式でパッとでてきたのがPNG形式で、wikipedia見てみると結構いろいろ載っていて勉強になった。

Portable Network Graphics - Wikipedia

やっていることは「フィルタ処理→圧縮」。
フィルタ処理では「左との差」「上との差」「左と上の平均値との差」「左と上と左上の値を使ったPaethアルゴリズムでの予測値との差」、圧縮はLZ77とハフマン符号の組み合わせ。

この記事を読んで「どっかの値を使う(位置を保存)」とか「ある位置との差分を使う(差分を保存)」を考えてた。
けど、ちょっと複雑な「いろんな情報からそのピクセル値の予測をしてその差分を保存」のようなアイデアは保存する情報が増えて圧縮あんまりできなそうと思ってしまっていたので、全然考えてなかった。

Lossless JPEG - Wikipedia

Lossless JPEGなど損失なしの画像フォーマットがいくつもあるようだったので、それをちゃんと調べられていなかったのは調査不足だった。

1byte単位か2byte単位か

最初、hexdumpコマンドとかで眺めてて、偶数byteと奇数byteで分けて考えてみてもよいかなと思い、それを考えた。
片方はほとんど種類数がないので結構つぶせそうで、もう片方のbyte列をどう圧縮するか?が重要かと考えていた。

しかし、「上位byte列+下位byte列」で扱うと、それぞれ別に圧縮しても、まとめて圧縮しても、あまり圧縮効果が変わらず、正の点数が取れてなかった。
他にも、差分を取って圧縮するときに「正か負か」と「差分値」を保存するよう別々に分けようとすると同様に圧縮効果があまり得られず。
結局、twitterでも見かけていた「2byte単位」でまとめて扱って~というのが必要だった。

RangeCoder

エントロピー符号化で、Huffman Codingは情報理論とかでも知っていたけど、さらに圧縮率の高い算術符号化(≒RangeCoder)があるとのことで、それを実装するのを目的にすることにした。

Algorithms with Python / レンジコーダ (range coder)

RangeCoderの実装や内容は上記のページを参考に、写経。
理解が怪しくて、1byte単位のコードはそのままでいいけど、2byteやそれ以上の単位を扱う場合の処理がうまく書き直すのに苦労してた。というか、提出コード、いろいろ変えたりして定数がおかしいまま提出してた、、、バグってるはずなのに普通に動いているよう・・・

予測符号化・変換符号化

http://www.pcsj-imps.org/archive/2013tutorial.pdf

終了後に調べた限りだけど、上記資料がまとまってた。
「予測符号化」というっぽいが、「次の値を予測し、予測値との差分値を符号化」をどうやるかがアイデアとして重要だったよう。

そもそも「隣接画素が似ている(画素の相関が高い)場合に、隣の画素を予測値として注目画素との差を取ることで、分散(値の種類数)を減らせて(冗長性を減らせて)、効率よく圧縮できる」ので、この考えだと「前の画素の値を予測値にする」の発展として、いろんな情報や予測手法(線形・非線形な手法、用いる予測器を切り替える「適応予測」など)を考える方向へ行けてたよう。

また、データを互いに相関のないデータへ変換する「変換符号化」も。
ブロックに分ける、離散コサイン変換、・・・。