Weathernews Programming Contest 参加記

だいぶ遅れてしまいましたが、自分の記録用に書きました。

先日、 Weathernews Programming Contest (お天気コン)に参加しました。

wn2017_1.contest.atcoder.jp

結果は4位でした。全体的にかなり強実装なのが辛かったですが、動くenc/decを初めて作ったし超楽しかった！

やったこと

大まかに、

  1. 画像を10x10のブロックに分割
  2. ブロック内の画素値を予測
  3. 予測誤差の相関除去
  4. 2.3.の情報＋3で残った誤差を算術符号で圧縮

という流れでした。

1.画像を10x10のブロックに分割

予測誤差を抑えるゲームと思っていたので、付加情報を送ってでも誤差を下げようと考えてました。 予測方法や相関除去の付加情報が増えすぎないように、ブロック単位で取れる選択肢を制限しています。 大きさを2べきでなく10x10にした理由は、適当な大きさで画像をピッタリ埋め尽くせるためです。

付加情報を周囲の状況から推測する方法もあります(machyさんはそうしていたよう)が、 最初は素直なものを作ろうと思ってそうしました。 付加情報を送れば予測誤差はまぁ下がるはずなので、どっちがいいかはともかく、トレードオフにはなってるはずです。 きっと推測すべきなのだとは思います。

ブロックによる分割は、画像にとって自然な分割にならないから辛いことも多いのですが、目視で時間変化を見て大丈夫そうな雰囲気(適当)を感じたのと、自分にとって慣れてるということでブロック単位の管理を選択しました。

2.ブロック内の画素値を予測

ブロック単位で、以下の3つの選択肢から選びます。 どれを選択するかは、後述する相関除去後の差分が小さいやつが選択されます。

  1. 同じ画像内の1つ上の画素と1つ左の画素の平均値をピクセル単位で計算して予測値とする
  2. 同じ波長画像で1つ前の時間の画像でブロックマッチングしてコピー
  3. 同じ時刻の1つ短い波長の画像で、同じ位置のブロックを線形変換してコピー
    • 何も考えずにコピーできるように、圧縮が終わった画像は参照される画像にスケールを合わせて保存。
    • 1つ短い波長ブロック → 圧縮対象ブロックの線形変換をブロックごとにやった。必要な係数は周辺画素から動的に求めてた。
    • 同時刻に撮った画像同士のマッチングなので、動き量は0に限定してもよいだろうと判断した。動き量を送らなくて良くなるのもポイント高い。

ブロック単位で2bitの情報 + 2.での動き量を伝えます。 動き量は似てることが多いため、動き量どうしの差分を伝えます。

最終的に、最初の時刻に撮られた画像の圧縮率が他と比べて圧倒的に悪かった(2. の予測方法を使えないため)です。 なので、3. の部分をどうにか出来ないかなぁというので結構苦労してました。

3.予測誤差の相関除去

予測誤差を眺めてみると、誤差の乗り方も似ていることがよくあるので、予測誤差どうしもブロック内で差分をとります。 差分のとり方は

  1. 横方向に差分を取る
  2. 縦方向に差分を取る
  3. 斜め方向に差分を取る
  4. そもそも差分を取らない

を全通り試して、ブロック内で差分とった結果の絶対値和が一番小さいやつを選んでいます。 1〜3は、ジグザグする感じの訪問順序になります（伝われ）。 ブロック単位で2bit + 最終的な差分の情報を伝えます。

4. 2.3.の情報＋3で残った誤差を算術符号で圧縮

まず前提として、ビット列は01の出現頻度の偏りが大きいほど圧縮しやすいです。直感的には、1000桁のビット列を覚える時、①全部0のデータと②01がランダムに混じるデータを比べると、前者が覚えやすい、位で十分と思います。

今回は、 付加情報として送付したビット情報を全部別々のビット列とみなして算術符号化にかけました(実際にビット列を分割したわけではなく、01の発生頻度の確率だけ分けた)。ビット列毎に01の出現頻度は、直前に受け取ったビット列の出現頻度を元に、動的に計算しています(適応的算術符号とかでググると色々出てくると思います)。直感的には、圧縮時と復元時に同じパラメータを使って同じ手順で処理を再現できるなら、特に正確な固定値の出現頻度値を使わなくてもOKという話です。

ビット列が生成された由来や状況に応じてビット列を別物として扱う(=コンテキスト分類する)ことで、01の偏りを強めることができる場合があります。が、今回は特に強いコンテキスト分類まで考えられていませんでした。

コンテスト中に考えていたけどやり残したこと

  1. ある波長画像を別の波長画像にマッピングする処理
    • 大局的に見て線形性がなかったので、参照画像を圧縮するときの予測誤差の大きさに応じて、ピクセル単位で画素位置をN分割して、各分割領域ごとに輝度値と輝度値の対応表をそのまま送ろうと思ってました。が、バグがとれず…
    • 画素位置を分割せずに、入力輝度値に対応する出力輝度値のヒストグラムを見ると、2山になってた。特に深く調べてなかったけど、海と陸で取れる波長の傾向が違うのかなーなんて妄想をしていた。画素位置を分割したらほぼ1山になってたから深くは追わなかったけど、実際のところは知らない。
  2. 予測方法1. で、平均を取らずに誤差最小の係数を線形回帰して計算
    • 予測方法2. 3. の方が圧倒的に効果があると思っていたので、結局手付かずになってしまった
  3. 一旦最適な予測方法が決まった後で、予測方法1. を使うブロックに限定して改めて線形回帰用の係数を計算し直す
    • 予測方法2. 3. のブロック内画素位置を回帰対象に含める必要がない
      1. と同じく、画像間の重ね合わせ部分が最重要だと思ってたので、手付かずになってしまった。
  4. 誤差最小ではなく、符号量最小の選択肢を選ぶ
    • 厳密な測定をしようと思うと、様々な状態に依存するので正直無理ですが、近似的には出来ます。最大サイズの画像は時間的にかなり厳しいですが、小さい画像の最適化ではやるチャンスがあったかもしれないです。
  5. 画像の拡大にBilinearを使っていたけど、もうちょいましな拡大方法を使っても良かったかも

余談

  • 圧縮率と関係無いですが、エンコーダとデコーダって同じ順番で付加情報なり誤差を読まなきゃいけないんだけど、どうにかして共通化する方法ないのだろうか(これのせいで、デバッグ時間的に微ロスを重ねていたので)

感想

  • 前職でチョットやってたので、いつか作りたいと思ってた。実際動くものが作れてからはテンションが5割増くらいだった。
  • いろんな処理を無限にバグらせたし、思ったことが一部できずに終わってしまったので、無限に実装力が欲しくなった。精進しなきゃ。
  • データの圧縮って個人的にすごい好きなんですが、「圧縮っていいよね！！」て言ってる人たちが少なからずいたようで、何か嬉しかった。
  • 今年からマラソンの参加記を書こうという気になったので、これからは終わってすぐ公開できるように準備しておきたいと思います。よろしくお願いします。