Guetzli／Butteraugliに関するあれこれ

2017年3月にGoogleから発表された新しいJPEGエンコーダ「Guetzli」と、同エンコーダが用いる画品質評価アルゴリズム「Butteraugli」について思うところとか。

- [
Announcing Guetzli: A New Open Source JPEG Encoder ](https://research.googleblog.com/2017/03/announcing-guetzli-new-open-source-jpeg.html)
- [GitHub google/guetzli](https://github.com/google/guetzli/)
- [GitHub google/butteraugli](https://github.com/google/butteraugli)

多くのニュースサイトで『[Google、JPEGを35％小さくできるエンコーダー「Guetzli」をオープンソースで公開](http://www.itmedia.co.jp/news/articles/1703/20/news022.html)』のようにセンセーショナルに紹介され、またGoogle社の手によるネームバリューもあったのか、世間の強い興味を引いたように思います。OSS方式にてソースコード公開されており、実際にエンコーダを動してみた方による良い／悪い評価結果が出てきています。

この記事では、同エンコーダ作者 Jyrki Alakuijala氏 の手による公開情報（かつ2017年3月時点で私がアクセスできたもの）から、個人的な解釈・感想をつらつらとまとめます。

たぶん適宜更新するかも。なるべく正確な解釈となるよう努力はしていますが、内容にウソや誤りがあれば指摘ください。あと、個人的な解釈もたまに挟まっています。全部鵜呑みにはしないでね。


# Guetzliって結局どうなのさ
技術的には「JPEGを35%小さくできる」はミスリーディングを誘う表現であり、一般ユーザへの誇大広告になっているきらいがあると感じます。とはいえ、記事タイトルとしてはそんなもんかなと。

現時点の公開情報をもとに、極力ニュートラルに解釈する限りでは：

- ユーザにとって **見た目に気づきにくい部分** の **データを削って** ファイルサイズを小さくするJPEGエンコーダです。データ値は歪みますが、ヒトの目には劣化と映らない “はず” という考え方です。[^note1-1]
- 「Guetzli」エンコーダは"[Proof of Concept(POC)][poc]"段階であり、**実用目的ではありません**。作者自身も処理速度が **超遅い** ことを認めています。[^note1-2]

より画像処理やJPEGについて理解されている方向けの説明だと：

- 古典的な客観評価指標(MSE/PSNR/SSIM etc.)は無視し、同作者の手による **新しい客観評価アルゴリズム「Butteraugli」** に対してのみ最適化されたJPEGエンコーダです。[^note1-3]
- 最適化は “JPEG量子化テーブル” と個々の “DCT係数値” に対して **反復的に** 行われます。膨大な演算時間を要するのはこのためです。[^note1-4]
- “他エンコーダより（平均で）35%小さくなった”のは、**「Butteraugli」スコアが同一** となった出力JPEGファイルを比べたときのファイルサイズ比較です。作者自身も認める通り、旧来の評価指標による比較では「Guetzli」はあっさりと他エンコーダに負けます。[^note1-5][^note1-6]
- OSS方式のため「Butteraugli」アルゴリズムの実装コードは公開されていますが、現時点では客観的データに乏しく科学的プロセスによる検証はこれからだと感じます。

[poc]: https://ja.wikipedia.org/wiki/%E6%A6%82%E5%BF%B5%E5%AE%9F%E8%A8%BC
[^note1-1]: [1] Abstract "Guetzli is a new JPEG encoder that aims to produce _visually indistinguishable images at a lower bit-rate_ than other common JPEG encoders."
[^note1-2]: [1] Abstract "Guetzli’s computation is _currently extremely slow_, which limits its applicability to compressing static content and _serving as a proof-of-concept_ that we can achieve significant reductions in size by combining advanced psychovisual models with lossy compression techniques."
[^note1-3]: [1] Abstract "Guetzli uses _Butteraugli_, _our perceptual distance metric_, as the source of feedback in its optimization process."
[^note1-4]: [1] Abstract "It optimizes both the JPEG global _quantization tables_ and the _DCT coefficient values_ in each JPEG block using a closed-loop optimizer."
[^note1-5]: [1] Abstract "We reach a _29-45% reduction_ in data size for a given perceptual distance, _according to Butteraugli_, in comparison to other compressors we tried."
[^note1-6]: [4] #29 "Guetzli is the worst on SSIM and PSNR, but best on butteraugli. This is really not a miracle nor a proof of its superiority since guetzli is just a complex optimizer for butteraugli rating."


# Butteraugliって何なの
現時点では”情報が少なすぎて何とも言えない”というのが正直な感想です。

arXiv[1]によると、ヒトの目がもつ次の特性を考慮しているとのこと。色彩工学と画像符号化に馴染みがないと意味不明だと思うので、勝手な超意訳をくっつけておきます：

- 3種類ある[錐体細胞][cones]はその[分光感度][cone-spectra]が重複しているため、[ガンマ補正][gamma-correction]をRGB色空間で行うのは適切ではない。YUV色空間はRGB空間からの線形変換に過ぎないため、より適切な処理を行うべき。
 - 意訳：従来の色表現手法(YUV)よりもヒトの目の生物学的・物理的特性に近い色表現手法を使おう。
- 青色の知覚は赤色/緑色に比べて空間解像度が低く、[網膜][retina]の[高解像エリア][fovea]にも青色受容体がほとんど存在しない。青色の高周波成分は正確さを劣化させてエンコードできるはず。
 - 意訳：ヒトの目は青色の変化に対して鈍い。そこから積極的にデータを削ろう。
- 画像中の微細構造の見え方はその周囲の視覚的アクティビティ（≒複雑さ）に依存する。視覚的に乱雑な領域は正確さを劣化させてエンコードできるはず。
 - 意訳：ごちゃごちゃしている部分は、元の画像と異なる風にごちゃごちゃさせてもどうせ気づかない。そこから積極的にデータを削ろう。

[cones]: https://ja.wikipedia.org/wiki/%E9%8C%90%E4%BD%93%E7%B4%B0%E8%83%9E
[cone-spectra]: https://ja.wikipedia.org/wiki/%E8%A6%96%E8%A6%9A#.E8.A6.96.E6.84.9F.E5.BA.A6.E3.81.A8.E9.8C.90.E4.BD.93.E5.88.86.E5.85.89.E6.84.9F.E5.BA.A6
[gamma-correction]: https://ja.wikipedia.org/wiki/%E3%82%AC%E3%83%B3%E3%83%9E%E5%80%A4#.E3.82.AC.E3.83.B3.E3.83.9E.E8.A3.9C.E6.AD.A3
[retina]: https://ja.wikipedia.org/wiki/%E7%B6%B2%E8%86%9C
[fovea]: https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%BF%83%E7%AA%A9

それぞれ言わんとすることは分かるのですが、あまり踏み込んだ説明がなされていません。「Butteraugli」アルゴリズムのソースコードをのぞくと結構な数のマジックナンバー（定数値）が散りばめられており、それらの値をどうやって決めたのか／なぜその値が妥当なのかという説明を見つけられませんでした。

画像圧縮による劣化／歪みを定量化するのは、現時点では **非常に難しい問題** です。古典的なMSE/PSNRや比較的新しいSSIMでも、理想的な評価関数からは程遠いというのが現実だと思います。もちろん、それぞれの評価関数により計算されるスコアと、人間が画像を見て付けるスコアにはちゃんと相関関係はあります。一方で、人間は綺麗と判断するが計算スコアは悪い／その逆となるデータも多数存在します（意図的にそういう画像を生成可能です）。[ITU-T勧告][itu-t]をはじめ画品質劣化を定量化するアルゴリズムはたくさん定義・提案されていますが、私が知る限り決定打のようなものは存在しません（してたら教えて！！）。

言い方は悪いですが「俺が考えた最強のアルゴリズム実装してみた」感が拭えず、もう少し情報がほしいなと思う次第です。

[itu-t]: https://ja.wikipedia.org/wiki/ITU-T


# 画品質評価のどこが難しいの
端的に言えば「ヒトが何かを見るというプロセスに関して、完全には解明されていない」ためです。

## 物理量・心理物理量・心理量
デジタル画像を数値データとして扱うとついつい忘れがちですが、その画像を“見る”行為はヒトの五感：視覚(目)・聴覚(耳)・嗅覚(鼻)・味覚(舌)・触覚(皮膚)の一部です。物理現象は長さ・重さ・時間といった **物理量(physical quantity)** で記述されますが、五感のようにヒトが知覚する量（尺度）は物理量で表せません。後者には **心理量(psychological quantity)** とよばれる、ヒトが心理的／感覚的に受け止める度合いが用いられます。

普段なにげなくRGB値で表現する“色”は、厳密には **心理物理量(psychophysical quantity)** に区分される数量です。文字通り心理量(psycho-)と物理量(-physical)の合いの子的な存在であり、心理物理量は“ヒトを対象とした実験データ”に基づいて定義されます。（注：サイコサスペンス的な人体実験ではありませんのでご安心を）。一例として、2つの色の距離“色差”を求める[CIEDE2000色差式][cie-de2000]は複雑な式で定義されますが、これは色弁別閾値実験データを高い精度で近似した帰結です。数値化された“色”それ自体もまた、等色実験により得られた[等色関数][color-match-func]ありきで定義されます。

具体例として“屋外でリンゴを見る”行為にマッピングしてみます：

- 物理量：ヒトの目に入射する光（電磁波）の周波数分布。太陽光線の分光分布×リンゴの分光反射率。
- 心理物理量：ヒトが知覚している刺激の強さ。CIE XYZ 3刺激値で表される“色”。
- 心理量：ヒトが感覚的に受け止めて認識する色。赤いリンゴ。

本記事中では、ヒトの視覚は心理物理量や心理量という（おそらく一般には耳慣れない）概念で定量化され、それらの数値が **人間の知覚に基づいたもの** であることだけ理解ください。（例：ヒトではなくイヌに対する色彩科学では、私たちヒトとは全く異なる“色”のシステムになります）

[color-match-func]: https://ja.wikipedia.org/wiki/CIE_1931_%E8%89%B2%E7%A9%BA%E9%96%93#.E7.AD.89.E8.89.B2.E9.96.A2.E6.95.B
[cie-de2000]: https://en.wikipedia.org/wiki/Color_difference#CIEDE2000

## 客観評価と主観評価
PNG等のロスレス(lossless)／可逆圧縮コーデックでは、必ず 入力画像＝デコード画像 が保証されるため、人間が見る画像には何ら影響ありません。一方でJPEG等のロッシー(lossy)／非可逆圧縮コーデックでは、入力画像とデコード画像とでは各ピクセル値が歪んでまい、これを人間は“画品質が劣化した”（≒見た目に汚くなった）と知覚します。それでもなおJPEGが使われるのは、ご存知の通りそのデータ圧縮率（データ量削減の度合い）が圧倒的に異なるためです。一般に、PNGコーデックではデータサイズ比1/2～1/3程度が性能限界ですが、JPEGコーデックでは容易に1/10程度まで小さくできます。

JPEGをはじめ全ての非可逆圧縮コーデックは、**人間に画品質劣化を知覚されないよう** 上手いことデータを削るよう設計されます。この観点での達成度を測るため、ある画像の品質を定量的に記述する“画品質評価”が必要となります。画品質評価には、大きく2種類の評価方法が存在します。古典的なMSE(Mean Square Error)、PSNR(Peak Signal-to-Noise Ratio)、SSIM(Structural SIMilarity index)、そして今回の「Butteraugli」はいずれも客観評価に属します。

- **客観評価(objective evaluation)**：画像データを入力値とし、計算された値に基づく評価方法。
- **主観評価(subjective evaluation)**：複数の人間で実際に画像を視聴し、スコアリングを行う評価方法。

主観評価がどんなものかはご存知ない方が多いと思うので、具体的な評価手順を簡単に説明すると：

1. （画像評価の専門家ではない）一般人から複数の被験者を集めます。
2. 被験者に複数の画像を見せ、5段階評価をしてもらいます。アンケート紙面には：非常に良い／良い／普通／悪い／非常に悪い
3. 5段階評価にスコア値1～5を割り当て、全被験者での平均値(MOS index)を求めます。

機械化・自動化を是とするIT技術トレンドからみると、この手順は時代錯誤で前時代的に映るかもしれません。しかしすでに説明した通り、画品質評価では「人間による知覚」こそが正義です。先の主観評価で用いたスコアリング法は、[MOS(Mean Opinion Score)][mos]と呼ばれる[ITU-T勧告 P.800][itu-t-p800]にて規定された由緒正しい手法であり、現時点で **最も信頼のおける画品質評価の技術** です。…そうがっかりしないでください。

[mos]: https://ja.wikipedia.org/wiki/%E5%B9%B3%E5%9D%87%E3%82%AA%E3%83%94%E3%83%8B%E3%82%AA%E3%83%B3%E8%A9%95%E7%82%B9
[itu-t-p800]: https://www.itu.int/rec/T-REC-P.800-199608-I/en

## 客観評価による画品質評価の実情
コンピュータでも計算可能な客観評価は、いずれも「主観評価による **MOS indexと高い相関関係を持つ**」よう設計されます。ゴールは 相関係数＝1.0、つまりヒトの視覚メカニズムの完全なるモデル化です。現状技術だと相関係数 0.90～0.95 付近でしのぎを削っているように思えます［要出典］。

MSE/PSNRは純粋な数理モデルにのみ基づくため、計算は簡単ですが相関係数はそれなりです。MSE/PSNRではピクセル毎の比較しか行いませんが、人間の視覚は“ある位置にあるピクセル値どれだけ変わったか”という局所的変化よりも、“ある小領域の形状が変化したか”という空間的要因に影響をうけます。PSNRは広く利用されますが、MOS indexとの相関関係という観点では、根拠に乏しい他の指標よりもマトモというだけです。（注：数理モデルによる評価目的では、依然としてPSNRはとても有効です。）

SSIMや「Butteraugli」などの新しい客観評価アルゴリズムは、ヒトの視覚メカニズムのモデル化を試み、MOS index相関の改善を目指しています。例えばSSIMではMSE/PSNRでは考慮しなかった空間方向の歪み度合いを考慮するため、[MOS index相関に関してPSNRよりも一歩だけ改善][ssim-mos]されています。

「Butteraugli」のような客観評価アルゴリズムは、 人間が感じる“**知覚的(perceptual)** 画品質”をコンピュータに計算させます。この考え方はマルチメディア客観品質評価の分野で古くから研究されており、いくつかのアルゴリズムはITU-Tで標準化されています。とはいえ、画像エンコーダが利用するアルゴリズムとしては、実績（実験的根拠）や計算速度の問題から、結局は PSNR または SSIM が用いられることが一般的のようです。

- [ITU-T勧告 J.147][itut-j147] "Objective picture quality measurement method by use of in-service test signals"
- [ITU-T勧告 J.247][itut-j247] "Objective perceptual multimedia video quality measurement in the presence of a full reference"
- [ITU-T勧告 J.341][itut-j341] "Objective perceptual multimedia video quality measurement of HDTV for digital cable television in the presence of a full reference"

[ssim-mos]: http://www.cns.nyu.edu/~lcv/ssim/
[itut-j147]: https://www.itu.int/rec/T-REC-J.147/en
[itut-j247]: https://www.itu.int/rec/T-REC-J.247/en
[itut-j341]: https://www.itu.int/rec/T-REC-J.341/en


# Guetzliエンコーダは何をしてるの
1行まとめ：ユーザが指定した知覚的画品質を満たしつつ、出力JPEGファイルサイズがなるべく小さくなるように、設定を少しずつ変えながらJPEGエンコード処理を反復試行する。

## RTFM
知覚的画品質の指定は、`guetzli`コマンドへの`--quality`設定値に対応します。一般的なJPEGエンコーダへの画品質調整パラメータQ値(max 100/default 95)に概ね相当しますが、Guetzliエンコーダ内部では “そのQ値を与えて[libjpeg][libjpeg]でエンコードされたJPEG画像のButteraugliスコア[^guetzli-lut]” へ変換し、このButteraugliスコアと同じになるが出力ファイルサイズは小さくなるよう最適化します。Guetzliエンコーダは **高い画品質を得られるQ値範囲 90～100 に対して設計** されており[^quote4-4]、Q値 84 を閾値に設定パラメータエラーとして拒絶します[^guetzli-q84]。

[README][quetzli-readme]のNoteに記載がある通り、現実装だと入力画像ファイルは **sRGB色空間／ガンマ値=2.2** が必須となります（ICCプロファイル情報は正しく処理されず無視されます）。これはButteraugliアルゴリズムのパラメータが同色空間を前提にチューニングされており、これ以外の色空間を入力するとまともな画品質は望めません。ICCプロファイルを正しく扱う外部ツールでPNG形式へと変換してから、Guetzliエンコーダへ入力する必要があります。

[libjpeg]: https://ja.wikipedia.org/wiki/Libjpeg
[quetzli-readme]: https://github.com/google/guetzli/blob/5bc0d61d188ad76b4b819b2dc0ed28deb2a9e3a5/README.md
[^quote4-4]: [4] #4 "Main differences between mozjpeg and guetzli are that guetzli is a lot slower (perhaps 100x), guetzli optimizes for butteraugli, and guetzli produces a non-progressive jpeg (for faster decoding), and _guetzli targets quality range 90-100_. Probably most testing and optimization we did around quality 95."
[^quote1-fig6]: [1] Figure 6: "High-level overview of Guetzli operation. Guetzli first tunes global parameters and only then tunes local parameters, holding global parameters constant. During the whole course of tuning, candidate JPEGs are generated and the best one of them is chosen as the final output."
[^guetzli-lut]: https://github.com/google/guetzli/blob/5bc0d61d188ad76b4b819b2dc0ed28deb2a9e3a5/guetzli/quality.cc#L26-L30
[^guetzli-q84]: https://github.com/google/guetzli/blob/5bc0d61d188ad76b4b819b2dc0ed28deb2a9e3a5/guetzli/processor.cc#L745-L751


## 最適化アルゴリズム
Guetzliエンコーダが行う処理は次の通りです：[^quote1-fig6]

1. 全体最適化：量子化マトリクスを変化させて、目標Butteraugliスコアに十分近づくまで調整する。
2. 局所最適化：量子化後のDCT係数に対して、画品質への影響が小さいわりにサイズ削減が見込める係数からゼロ丸めを行う。
3. 上記の最適化処理を組合せた中で、最もファイルサイズが小さい候補を採用する。

（以下の処理説明はソースコード解析に基づいたものですが、直接読み取れた処理ロジックを書き下しただけで、高次の目的までは解釈できていません。）

量子化マトリクスの最適化プロセスでは[^guetzli-optqm]、[コントラスト感度関数][csf](CSF; contrast sensitivity function)≒DCT係数Zig-Zagスキャン順位の逆数 とみなして量子化マトリクスと評点値を対応させ[^guetzli-qmscore]、この評点値が収束するように量子化テーブルを反復的に生成します[^guetzli-genqm]。同手順にて生成された候補量子化マトリクスを用いてJPEGエンコード処理を行い、続いて生成JPEGストリームからのデコード画像に対するButteraugliスコアを算出します。算出スコアが目標スコアに十分近づいたら反復打切りです。

DCT係数の最適化プロセスでは[^guetzli-optcoeff]、8×8＝64ピクセルからなるMCU(Minimum Coded Unit)全DCT係数に対してCSFに基づく評点値をつけ、同評点が低い係数から順番に値をゼロ丸めした場合にButteraugliスコアに与える影響度を計算し、影響が小さい係数のみを候補にあげます[^guetzli-mcuorder]。この候補選定を全MCUに対して行ったのち、隣接MCUとの関係性を考慮した “ゼロ丸めにより生じる誤差が小さい順DCT係数候補リスト” を作成します[^guetzli-imgorder]。同リストに従ってDCT係数ゼロ丸めをした場合に、“ファイルサイズ削減効果が予想されるDCT係数候補リスト” へとさらに絞ります。このリストに残ったDCT係数へのゼロ丸めを適用したJPEGエンコード処理を行います。Butteraugliスコアはここまでの処理過程から同時に算出済みです。最適化プロセス全体では前掲処理を反復し、“ゼロ丸めにより生じる誤差が小さい順DCT係数候補リスト” が空リストになるまで試行します。反復収束は`ComputeBlockErrorAdjustmentWeights`関数に依存します[^guetzli-cbeaw]。

[csf]: https://en.wikipedia.org/wiki/Contrast_(vision)
[^guetzli-optqm]: https://github.com/google/guetzli/blob/5bc0d61d188ad76b4b819b2dc0ed28deb2a9e3a5/guetzli/processor.cc#L311-L313
[^guetzli-qmscore]: https://github.com/google/guetzli/blob/5bc0d61d188ad76b4b819b2dc0ed28deb2a9e3a5/guetzli/processor.cc#L170-L178
[^guetzli-genqm]: https://github.com/google/guetzli/blob/5bc0d61d188ad76b4b819b2dc0ed28deb2a9e3a5/guetzli/processor.cc#L254-L264
[^guetzli-optcoeff]: https://github.com/google/guetzli/blob/5bc0d61d188ad76b4b819b2dc0ed28deb2a9e3a5/guetzli/processor.cc#L523-L526
[^guetzli-mcuorder]: https://github.com/google/guetzli/blob/5bc0d61d188ad76b4b819b2dc0ed28deb2a9e3a5/guetzli/processor.cc#L349-L353
[^guetzli-imgorder]: https://github.com/google/guetzli/blob/5bc0d61d188ad76b4b819b2dc0ed28deb2a9e3a5/guetzli/processor.cc#L635-L638
[^guetzli-cbeaw]: https://github.com/google/guetzli/blob/5bc0d61d188ad76b4b819b2dc0ed28deb2a9e3a5/guetzli/butteraugli_comparator.cc#L160-L166


# 情報源
- [1] arXiv: "[Guetzli: Perceptually Guided JPEG Encoder](https://arxiv.org/abs/1703.04421)," March 14, 2017
- [2] arXiv: "[Users prefer Guetzli JPEG over same-sized libjpeg](https://arxiv.org/abs/1703.04416)," March 14, 2017
- [3] encode.ru: [SSIM / MSSIM vs MSE](https://encode.ru/threads/2395-SSIM-MSSIM-vs-MSE), December 2015-
- [4] encode.ru: [Guetzli - a new more psychovisual JPEG encoder](https://encode.ru/threads/2628-Guetzli-a-new-more-psychovisual-JPEG-encoder), October 2016-
- [5] HackerNews: [Guetzli: A New Open-Source JPEG Encoder](https://news.ycombinator.com/item?id=13887295), March 2017-