S q_{v u} = round (\frac{S _{v u}}{Q _{v u}})

計算の裏側

JPEGはどうやって写真を小さくしているのか

How JPEG makes photos small

品質75の正体は、規格にある表の例を2で割った数だった。

8×8画素を64枚のしま模様の重みに直し、細かいしまほど粗く丸めて0を並べ、ハフマン符号で詰める。規格の式と表の例、libjpegの品質の目盛りを分けて、坂のかたまりが41ビットになるまでを追う。

種類: 計算の裏側
公式: 4 本
人物: グレゴリー・ウォレス、エリック・ハミルトン、トーマス・G・レーン

フーリエ級数シャノンの情報エントロピー三角関数の加法定理等比級数(ゼノンのパラドックス)

場面

規格にない「品質」の目盛り

画像を保存するとき、品質を0から100の数で選ばせるソフトがある。この数が動かしているのは、画像を8×8画素のかたまりに切り、それぞれを64枚のしま模様の重ねあわせに直したときの、重みの丸め方だ。細かいしまの重みほど粗く丸めて0にし、並んだ0をハフマン符号で短く詰める。JPEGが写真を小さくする仕組みの芯は、この3つの段にある。

ところが、JPEGの規格を開いても、品質75という数はどこにも出てこない。

1992年9月18日に承認されたCCITTの勧告T.81は、ISO/IECの国際規格10918-1と同じ文である。丸めの細かさを決める64個の数の表について、規格は既定の値を定めていない。附属書Kに表の例が載っているだけで、その附属書も規格の一部ではないと断ってある。0から100の目盛りは、Independent JPEG Group（IJG）が1991年10月7日に最初の版を出したライブラリ、libjpegの決めごとである。

既定の75は、規格の一文とちょうど重なる。附属書Kには「この量子化の値を2で割ると、復元した画像は、たいてい元の画像とほとんど見分けがつかない」と書かれている。libjpegが品質75で使うのは、まさに附属書Kの表の数を2で割って四捨五入した表だ。

考え方

64枚のしま模様

8×8画素のかたまりにある64個の明るさは、決まった64枚のしま模様にそれぞれ重みを掛けて足したものとして、過不足なく書き直せる。1枚目は全体が一様な模様で、その重みはかたまりの平均の明るさを表す。規格はこの重みをDC係数、残りの63個をAC係数と呼ぶ。64枚を8×8に並べると、右へ進むほど縦じまが、下へ進むほど横じまが細かくなり、右下の1枚は縦横とも1画素ごとに明暗が入れ替わる、市松に近い模様になる。

写真では、隣どうしの画素の明るさがたいてい少ししか違わない。グレゴリー・ウォレスは、1991年に書き翌年に改訂したJPEGの規格の解説で、そのため変換すると信号の大部分が低い周波数に集まる、と説明している。ふつうの画像のかたまりなら、多くの周波数の重みは0か0に近く、符号にしなくてよい。変換を「調和解析器」、逆の変換を「調和合成器」とみると直観がつかめる、ともウォレスは書いた。形をsinとcosの重ねあわせに分けるフーリエ級数を、8個の点の上でやり直したものと考えればよい。

では、なぜsinを使わず、コサインだけなのか。

8個の点にふつうのフーリエ級数を当てはめると、8個がそのままくり返す形とみなすことになる。右の端から左の端へ戻るところで、明るさが飛ぶ。離散コサイン変換（DCT）のコサインは、8個を鏡に映すように折り返して16個にし、それをくり返す形に当たる。折り返しの所では値が飛ばない。

この記事のために、坂になった1行69、73、77、…、97で比べてみた。平均を引いて2乗した和のうち、DCTでは最も粗いしま1本の重みが98.8%を占める。8個の点の離散フーリエ変換では、最も低い周波数の組が65.0%にとどまり、残りが細かい周波数に散る。飛びのある形の係数がなかなか減らないことは、フーリエ級数の記事の矩形波と三角波の例題が示すとおりだ。つまり、折り返す形を選んだおかげで、なだらかなかたまりはほぼ1本のしまで書ける。

式

8本のコサインは直交する

64枚の重みを1枚ずつ取り出せるのは、しま模様どうしが直交しているからだ。まず1方向の8本で確かめる。 $x = 0, 1, \dots, 7$ は画素の位置、 $u$ はしまの細かさである。

8本のコサインを決める。半整数の位置 $x + \frac{1}{2}$ で値をとるのが、DCTの形である。
$c_{u} (x) = cos \frac{( 2 x + 1 ) u π}{16}, u = 0, 1, \dots, 7$
加法定理から出る積和の公式で、2本の積を和に直す。
$c_{u} (x) c_{u^{'}} (x) = \frac{1}{2} (cos \frac{( 2 x + 1 ) ( u - u ^{'} ) π}{16} + cos \frac{( 2 x + 1 ) ( u + u ^{'} ) π}{16})$
$k$ を1から15の整数とし、 $θ = k π /16$ とおく。 $e^{i (2 x + 1) θ}$ の8項の和は、公比 $e^{2 i θ}$ の等比級数の和である。
$x = 0 \sum 7 e^{i (2 x + 1) θ} = \frac{e ^{i θ} ( 1 - e ^{16 i θ} )}{1 - e ^{2 i θ}} = \frac{1 - ( - 1 ) ^{k}}{e ^{- i θ} - e ^{i θ}}$
分母は $- 2 i sin θ$ で、分子は0か2なので、和は0か純虚数になる。実部をとると、8点のコサインの和は0である。コサインは偶関数なので、 $k$ が $- 15$ から $- 1$ でも同じになる。
$x = 0 \sum 7 cos \frac{( 2 x + 1 ) k π}{16} = 0 (k = 1, 2, \dots, 15)$
$u \neq = u^{'}$ なら、 $u - u^{'}$ と $u + u^{'}$ はどちらも0でなく、絶対値は14以下なので、手順2の和は0になる。
$x = 0 \sum 7 c_{u} (x) c_{u^{'}} (x) = 0 (u \neq = u^{'})$
$u = u^{'} \geq 1$ なら第1項が $cos 0 = 1$ になり、第2項の和は手順4で消える。 $u = 0$ では $c_{0} (x) = 1$ なので、和は8になる。
$x = 0 \sum 7 c_{u} (x)^{2} = {84 (u = 0) (u \geq 1)$
長さをそろえるため、 $u = 0$ にだけ $C_{0} = 1/ 2$ を掛け、全体を2で割る。これで8本とも2乗の和が1になる。
$x = 0 \sum 7 (\frac{C _{u}}{2} c_{u} (x))^{2} = 1, C_{0} = \frac{1}{2}, C_{u} = 1 (u \geq 1)$
横と縦の積で64枚にすると、T.81の附属書Aにある順方向の変換（FDCT）になる。 $s_{y x}$ は $y$ 行 $x$ 列の明るさから128を引いた値、 $S_{v u}$ は係数である。
$S_{v u} = \frac{1}{4} C_{u} C_{v} x = 0 \sum 7 y = 0 \sum 7 s_{y x} cos \frac{( 2 x + 1 ) u π}{16} cos \frac{( 2 y + 1 ) v π}{16}$
直交しているので、同じしま模様に係数を掛けて足し戻すと元の明るさに戻る。これが逆の変換（IDCT）である。
$s_{y x} = \frac{1}{4} u = 0 \sum 7 v = 0 \sum 7 C_{u} C_{v} S_{v u} cos \frac{( 2 x + 1 ) u π}{16} cos \frac{( 2 y + 1 ) v π}{16}$

手順2から手順5は、フーリエ級数の記事で、周波数の違うsinの積を積分すると0になることを追った手順と同じ形をしている。積分が8点の和に変わっただけだ。

T.81は、この2つの式を理想の定義と位置づけて参考扱いにし、実際の計算に求める精度は第2部で決めている。コサインの値は、どんな計算機でも正確には表せないからだ。変換の前には、0から255の明るさから128を引いて、0を中心にそろえる。

図

表K.1とジグザグの道

左は、規格T.81の附属書Kにある輝度の量子化表の例（表K.1）。左上ほど値が小さく、右下ほど大きい。右は、係数を一列に並べるジグザグの順で、左上のDC係数から右下の63番へ斜めに往復する。

情報を大きく捨てるのは、量子化の段である。ウォレスによれば、DCTを使う符号化で情報が失われる主な原因は、この段にある。係数 $S_{v u}$ を表の同じ位置の値 $Q_{v u}$ で割って、いちばん近い整数に丸める。復号では $Q_{v u}$ を掛け戻す。

S q_{v u} = round (\frac{S _{v u}}{Q _{v u}}), R_{v u} = S q_{v u} \times Q_{v u}

表K.1の左上は16、11、10と小さく、右下の8行目には112、100、103、99が並ぶ。ただし、附属書Kは、この表が見え方のしきい値を調べる実験から経験的に求めたもので、あくまで例であり、どの用途にも合うとは限らないと書いている。地味だが大事な点がもう1つある。附属書Aの見出しは、量子化を参考、逆量子化を規定としている。規格が必ず守らせるのは復号する側の掛け算で、割る側の式は参考の扱いだ。どの表で割るかも符号化する側が選び、表はファイルに書き込んで渡す。

丸めたあとの64個は、図の右の順に並べ直してから符号にする。ウォレスの解説によれば、0でない値になりやすい低い周波数を、高い周波数より先に置くための並べ方である。こうすると、後ろの方に0が長く続く。

式

坂のかたまりが41ビットになる

このあと動かす画像の左上のかたまりで、量子化から符号までを順にたどる。右へ1画素ごとに4、下へ2ずつ明るくなる坂で、左上が69、右下が111になる。品質は75、つまり表K.1を2で割って四捨五入した表を使う。

128を引いた明るさは、横の坂と縦の坂を足した形で書ける。
$s_{y x} = 69 + 4 x + 2 y - 128$
DC係数は、 $C_{0}^{2} = 1/2$ から平均の8倍になる。かたまりのまん中の明るさは90である。
$S_{00} = \frac{1}{8} x = 0 \sum 7 y = 0 \sum 7 s_{y x} = 8 \times (90 - 128) = - 304$
横の坂からは1行目の係数だけが出る。8点のコサインの和は0なので、 $u \geq 1$ では定数と縦の坂が消える。
$S_{0 u} = 42 x = 0 \sum 7 (x - \frac{7}{2}) cos \frac{( 2 x + 1 ) u π}{16}$
$u$ が偶数の項は左右で打ち消して0になり、奇数の項が残る。縦の坂からも係数が1列目に出て、傾きが半分なので値も半分になる。0でない係数は全部で9個である。
$S_{01} = - 72.89, S_{03} = - 7.62, S_{10} = - 36.44, S_{30} = - 3.81$
品質75の表では $Q_{00} = 8$ 、 $Q_{01} = 6$ 、 $Q_{03} = 8$ 、 $Q_{10} = 6$ 、 $Q_{30} = 7$ である。割って丸めると5個が残る。 $S_{05} = - 2.27$ は $Q_{05} = 20$ で割ると $- 0.11$ で、0に丸められる。
$S q_{00} = - 38, S q_{01} = - 12, S q_{03} = - 1, S q_{10} = - 6, S q_{30} = - 1$
ジグザグに並べると、DCのあとに $- 12$ と $- 6$ 、0が3つ、 $- 1$ 、0が2つ、 $- 1$ と続き、残りの54個はすべて0になる。
$- 38 ∣ - 12, - 6, 0, 0, 0, - 1, 0, 0, - 1, 54 0, \dots, 0$
DCは、1つ前のかたまりとDCの差をとって符号にする。左上は最初のかたまりなので予測は0で、差は $- 38$ 。大きさが32から63の差はカテゴリ6で、表K.3の符号1110に6ビットを続ける。負の数は、1を引いた $- 39$ の下6ビットを書く。
$- 38 \to 1110011001$
ACは、直前に続く0の個数とカテゴリを組にして表K.5で符号にし、値のビットを続ける。 $(0, 4)$ は「0がなく、カテゴリ4」を表す。
$(0, 4) - 12 (0, 3) - 6 (3, 1) - 1 (2, 1) - 1 \to 10110011 \to 100001 \to 1110100 \to 111000$
残りが全部0なので、ブロックの終わりを表すEOBの符号1010を置く。合計は41ビットで、元の64画素×8ビット、512ビットの約12分の1になる。
$10 + 8 + 6 + 7 + 6 + 4 = 41$
復号では、表の値を掛け戻してIDCTにかける。たとえば $S_{01}$ は $- 72.89$ が $- 72$ になる。戻した64画素のうち24画素が元と1だけずれ、残りは元のとおりになった。
$R_{01} = - 12 \times 6 = - 72$

品質を50に下げると、表は表K.1そのものになる。 $S_{03}$ と $S_{30}$ も0に丸められて残る係数は3個、符号は22ビットになり、元と違う画素は48個、ずれは最大で2になる。

ウォレスの解説にも、実際の画像から取った8×8のかたまりを、規格の案の附属書にあった量子化表とハフマン符号で符号にする例がある。使っている値は表K.1、K.3、K.5と同じで、64個の係数が31ビットになり、1画素あたり0.5ビットを少し下回る。

シミュレーション

品質のつまみを下げていく

画像は24×24画素で8×8のかたまりが3×3並び、左上から右下へ明るくなる坂の上に、右上のかたまりには1画素おきの薄い縦じまを、右下の4つのかたまりが接する角には暗い円を描いた。品質を下げると、読み出しに出る係数の個数と、符号のビット数が減っていく。見せ方を「元との差」にすると誤差が4倍の網点で出て、円の縁とかたまりの境目に集まるのが見える。「64個の係数」では、選んだかたまりに残ったしま模様と、ジグザグに並べた数が出る（画像の上でたたいたかたまりを選び、ここでたたくと次へ移る）。

品質75では、576個の係数のうち150個が残り、9つのかたまりの符号を合わせて959ビットになる。1画素を8ビットで表した元の4,608ビットの1/4.8で、50では99個で1/7.6、5では33個で1/25.0まで縮む。右上の薄いしまは、いちばん細かい縦じまの係数が品質26以下で0になる。円の縁を含むまん中のかたまりは、品質75でも29個の係数が残り、坂だけのかたまりで残る5個と比べて6倍近い。つなぎ目をはさむ隣どうしの画素の差は、元の画像で平均3.5、品質5では14.4に開く。

ただし、数えたのはかたまりの符号だけで、ファイルの頭に付くヘッダーや表は入れていない。同じ画像をlibjpeg-turbo 3.2.0で品質75のJPEGに保存してみると453バイトになり、元の576バイトの8割近くもあった。量子化表1つと表K.3、K.5を書き込むだけで285バイトになるからだ。

考え方

libjpegが決めた0から100

では、品質の数から表はどう作られるのだろうか。libjpegの関数jpeg_quality_scalingとjpeg_add_quant_tableは、IJGのコードとして、いまもlibjpeg-turboに残っている。ファイルの冒頭には、トーマス・G・レーンの名と1991年から1998年の著作権の表示がある。品質 $q$ から百分率の倍率 $f$ を決め、表K.1の値 $K$ に掛けて表を作る。

f (q) = {5000/ q 200 - 2 q (q < 50) (q \geq 50), Q = ⌊ \frac{K f ( q ) + 50}{100} ⌋

品質50で倍率は100%になり、表K.1がそのまま使われる。75で50%、95で10%、100では0%になって、表の値はすべて1に置き換えられる。反対に10では500%で、左上の16が80になり、右下の多くは、基本の方式（ベースライン）に合わせる設定で上限の255に止まる。0を入れると1として扱い、0での割り算を避けている。

libjpegの文書は、この目盛りを「IJGが勧める0から100の目盛り」と呼び、品質の数から表への対応は、DCTの量子化について分かることが増えれば将来の版で変わりうると断っている。IJGは、規格をまとめた委員会とは関係のない集まりだ。規格の外で決めた目盛りなので、ほかのソフトで同じ品質の数を選んでも、同じ表になるとは限らない。

コマンドcjpegの使い方の文書は、写真ならふつう50から95のあいだで、既定は75、75で傷が見えたら5か10ずつ上げればよいと勧める。95を超えるとファイルは急に大きくなるのに、その差を人の目で感じることはまれだという。品質100で表がすべて1になっても、色の間引きと丸めの誤差で情報は失われる。

既定が75になったのは、附属書Kの「2で割る」の一文に合わせたからだろう。jcparam.cのコメントにも、規格によれば表の値そのままで「良い」画質、2で割ると「とても良い」画質になる、と書かれている。

考え方

色だけを縦横半分に間引く

カラー写真では、量子化の前にもう1つ、規格の外の段がある。

JPEGの規格は色の表し方を決めておらず、ファイルの形を定めたJFIFが、色を明るさのYと、色の差のCb、Crに分けると決めた。JFIFの版1.02は1992年9月1日付で、C-Cube Microsystemsのエリック・ハミルトンがまとめた。8ビットのRGBからは、次の式で求める。

Y C_{b} C_{r} = 0.299 R + 0.587 G + 0.114 B = - 0.1687 R - 0.3313 G + 0.5 B + 128 = 0.5 R - 0.4187 G - 0.0813 B + 128

libjpegは、既定でCbとCrを縦横とも半分の細かさに間引く。cjpegの文書が「4:2:0」と呼ぶ形である。2×2画素ごとに、RGBなら12個の数が要るところを、Yの4個とCb、Crの1個ずつ、合わせて6個にする。DCTに入る前に、数はもう半分になっている。文書は、人の目は色より明るさの空間的な変化に敏感だからと理由を書いている。附属書Kの表の例も、色の成分を横に2:1で間引いた画像で求めたものだ。

ウォレスの言い方では、カラー画像の圧縮は、灰色の画像を何枚か圧縮することとほぼ同じとみなせる。色の成分に使う表の例（表K.2）は、左上の13個のほかがすべて99である。

歴史

12の方式から選ばれたADCT

1974年1月、N・アーメド、T・ナタラジャン、K・R・ラオの3人は『IEEE Transactions on Computers』に、「Discrete Cosine Transform（離散コサイン変換）」と題した4ページの論文を載せた。

T.81の序文によると、JPEG（Joint Photographic Experts Group）は1986年にできた。濃淡のある白黒とカラーの静止画を圧縮する規格をつくるための、専門家の集まりである。ウォレスの解説によれば、名前の「Joint」は、CCITTとISOの共同作業を指す。1987年6月、JPEGは目隠しで画質を比べる評価で、提案された12の方式を3つに絞った。1988年1月の、より厳しい2回目の評価で、8×8のDCTを使う「ADCT」の画質が最もよかった。それから1990年まで、互換性を保つための細部を定め、試験し、合意する作業が続いた。

量子化の表の例は、ウォレスによれば、H・ローシェラーが1984年に発表した視覚の実験から生まれ、規格には要件ではなく参考として載ることになった。

ウォレスはディジタル・イクイップメント社（DEC）に所属し、解説を1991年4月の『Communications of the ACM』に書いた。改訂版は翌年の『IEEE Transactions on Consumer Electronics』に載っている。この記事で引いたのは、IJGのサイトにある、1991年12月に投稿した改訂版の原稿である。31ビットの例は、イーストマン・コダックのマジッド・ラバニが用意したと謝辞にある。解説には、JPEGのメンバーが試した多くの画像で、算術符号がハフマン符号より5〜10%よく圧縮できたとも書かれている。それでも、最も基本の方式（ベースライン）はハフマン符号を使う。

同じ1991年の10月7日には、IJGがlibjpegの最初の版を出した。1992年9月1日付でJFIF 1.02がまとまり、9月18日にT.81が承認された。IJGのページによれば、最新は2026年1月25日の第10版である。

ウォレスは解説の結びに、委員会の成功を測る最後の物差しは、JPEGで圧縮した画像が、いまの文字や図形と同じく「ありふれたデータの一種」とみなされ、当たり前になったときだと書いた。

使いどころ

文字の画面写真がにじむわけ

縁のくっきりした絵は、JPEGが苦手とする。上の画像の円の縁のように、明るさが急に飛ぶかたまりでは細かいしまの重みが大きく、品質を下げると縁のまわりに波のような誤差が残る。cjpegの文書も、漫画や線画のように色の少ない画像をJPEGにしないよう勧めている。画面写真の文字のまわりに出るもやも、縁を作っていた細かいしまが丸められた跡なのだろう。文字の画面写真や図は、可逆圧縮の形式で保存するほうがよい。

保存し直すたびに、誤差は積み重なる。cjpegの文書によれば、圧縮と復元を10回ほどくり返すと、1回目より目に見えて悪くなることがある。編集のあいだは可逆圧縮の形式で持ち、JPEGにするのは最後の1回にするよう勧めている。

符号の段は、もう少し縮められる。表K.3とK.5は、多くの画像から平均をとった統計で作った表で、規格も既定の表ではないとしている。1記号あたりの符号の長さは、平均すると、記号の出る割合で決まる限界より短くならない。このことはシャノンのエントロピーの記事にある。その画像だけの割合に合わせてハフマンの表を作り直すのが、libjpegのoptimize_codingで、cjpegでは-optimizeにあたる。libjpegの文書によれば、既定の表と比べて縮むのは、たいてい数%である。

自分で確かめるなら、次の順に進めるとよい。

シミュレーションで見せ方を「元との差」にし、品質を75から5まで下げる。
「64個の係数」に切り替え、円の縁を含むかたまりと坂だけのかたまりで、残る係数の個数を比べる。
表計算に69、73、77、…、97の8個を入れ、 $\frac{1}{2} \sum (s_{x} - 83) cos \frac{( 2 x + 1 ) π}{16}$ を計算して、 $- 25.77$ になるかを見る。
使っている画像のソフトの文書で、品質の数がlibjpegの目盛りかどうかを調べる。

手順3の値を2乗して、平均を引いた8個の2乗の和672で割ると、0.988になる。坂の1行の98.8%が、粗いしま1本に入っている。

ほかの読みものでは、0.1 + 0.2が0.3にならないのはなぜかが、計算機が小数を丸めるときに出る誤差を扱っている。JPEGは、その丸めをわざと大きくして、写真を小さくしている。

参考文献

CCITT, Recommendation T.81, "Information technology: Digital compression and coding of continuous-tone still images: Requirements and guidelines" (09/92). 同文がISO/IEC 10918-1（W3Cが置いている写しで、A.3.1〜A.3.6・F.1.2・附属書Kを確認）
G. K. Wallace, "The JPEG still picture compression standard", Communications of the ACM 34(4) (1991), 30-44. DOI 10.1145/103085.103089。改訂版はIEEE Transactions on Consumer Electronics 38(1) (1992), xviii-xxxiv. DOI 10.1109/30.125072（IJGが置いている、1991年12月に投稿した改訂版の原稿で確認）
N. Ahmed, T. Natarajan, K. R. Rao, "Discrete Cosine Transform", IEEE Transactions on Computers C-23(1) (1974), 90-93. DOI 10.1109/T-C.1974.223784（書誌はCrossref）
H. Lohscheller, "A Subjectively Adapted Image Communication System", IEEE Transactions on Communications 32(12) (1984), 1316-1322. DOI 10.1109/TCOM.1984.1096017（書誌はCrossref）
E. Hamilton, "JPEG File Interchange Format, Version 1.02"（C-Cube Microsystems, 1992年9月1日）
libjpeg-turboのソースコードsrc/jcparam.c（jpeg_quality_scaling・jpeg_add_quant_table・jpeg_set_defaults）と文書doc/usage.txt・doc/libjpeg.txt
Independent JPEG Group, ijg.org（最初の版の日付・最新の版・規格の委員会との関係）