画像圧縮で広く使われている、Jpeg の仕組みについて、簡単にまとめてみました。
こんな疑問に答えられると思います。

なぜビットマップ(BMP)から Jpeg にすると恐ろしく小さくなるのか
なぜ背景が真っ白な画像を Jpeg 圧縮すると、↓みたいなにじむのか

画像ファイルは数値の列

コンピュータで画像を扱うときには、まず画像を細かい四角(ピクセル)に分けています。デジカメが何万画素っていいますが、「100万画素」というのは、一枚の画像を 100 万の四角に分けているという意味です。

例えば上の写真のように、青い空のところは■という四角(ピクセル)がたくさん集まって出来ています。

さらに、各ピクセルの色を数値で表します。コンピュータのディスプレイでは、すべての色を赤、緑、青の組み合わせで表示しています。どんな色でも、赤、緑、青の割合を変えることで作り出すことが出来ます。一般的によく使われるのは、赤、緑、青の各色を0-255 の数値で表します。たとえば、■の水色の場合は、赤が187, 緑が 221, 青が 238 と表せます。

こうして、画像を小さな四角に分割して、それぞれの色を数値で表すと、画像全体を数値で表すことが出来ます。ビットマップと呼ばれるファイル (bmp) は、まずファイルの大きさの情報、色数の情報を書いたあと、各ピクセルの色の情報が順番に書かれています。

ビットマップと圧縮

ビットマップファイルは、一番基本的なファイル形式です。画像を生成するのも楽だし、表示するのも楽です。しかし、ファイルサイズが大きくなってしまう欠点があります。
先ほど、一つのピクセルを赤、緑、青それぞれに 0-255 の強さで表す、と書きました。この場合、1 ピクセルに 24bit = 3 バイト使うので、1000万画素の場合は 3000万バイト、つまり 30 MB になります。これだと CD-ROM 一枚には画像が 20 枚くらいしか入らないことなります。
このため、様々な画像の圧縮方法が研究されてきました。圧縮には、元々の画像のデータを変えないもの (可逆圧縮) と、画像を劣化させることで劇的にサイズを小さくするもの (不可逆圧縮) があります。もしもプログラムやパスワードや、大事な文書を圧縮する場合には、元々のデータを 1 バイトたりとも変えることは出来ません。しかし画像や音声など、「マルチメディア」と言われるデータでは、受け取るのは人間なので、人間が違和感を感じなければ、少しくらいデータが違っていても大丈夫です。少しデータが変わっても、サイズが劇的に小さくなるなら、そのほうがメリットが大きいです。実際、可逆圧縮では zip のようなアルゴリズムが使われていますが、圧縮率は数割にとどまります。これに対し、不可逆圧縮では、見た目はほぼ変わらないまま、ファイルサイズを 1/10 以下にできることが知られています。

Jpeg (DCT) による圧縮

Jpeg のアイディアの基礎をなすのは、DCT (離散コサイン変換) と呼ばれる変換です。これは、元々の「ピクセルを1つずつ数値にあてはめる」という考えを変えて、「画像をいくつかのパターンに分解して、それぞれの強さに数値を当てはめる」ものです。
以下、Jpeg のアイディアを簡単に説明します。(わかりやすくするため、一部実際の jpeg と異なる部分があります)

まずは色で分解

次に、いくつかの「基本画像」で分解

次に、この色ごとに分けた画像を、さらに以下のように、いくつかの「基本画像」の足し合わせで表してみます。

それぞれの基本画像に a₀₀ みたいな係数がついてるのがポイントです。
「足し合わせ」というのがピンとこないかもしれませんが、単純に行列の演算だと思ってください。例えば、元々の画像の各画素の値が、

8	2
4	6

だったら、以下のように分解できます。

(a₀₀ や a₀₁ の係数の計算方法は別の機会に説明します。)

高周波成分を間引く

ここまでの説明では、画像のサイズが小さくなる操作は何もありませんでした。ですが、これで jpeg の準備はほとんど完了しています。
先ほど、元々の画像のデータを、いくつかの基本パターンの和で表して、それぞれの係数を a₀₀ とか a₀₁ とか、数値で表しました。つまり、元々の画像の情報は、この a₂₃ みたいな係数の情報に置き換えられています。
ここで、この係数は、等しく大切なわけではなく、とても重要なものと、そうでもないものがあります。例えば、一番左上の係数 (a₀₀) は、全体の色味を表すもので、とても大切です。これに対し、右下の方の成分は、隣のピクセルとの細かい差分を表しています。 1 ピクセル単位の差分の情報は、全体的な色の傾向に比べるとあまり大事ではありません。

そこで Jpeg では、若い係数 (上の図では a₀₀) はきめ細かく表現する一方、大きな係数 (上の図では a₃₃ など) は大雑把に表現します。例えば、a₀₀ は (0,1,2,...,255) と 256 階調で表しますが、 a₃₃ は (0,85,170,255) の 4 階調で表します。こうすると、a₀₀ には 8 bit 必要ですが、a₃₃ には 2 bit で済むことになります。
実際この作業をしてみると、大きな係数のほうが係数の数は多いので、かなりのデータを省略できることになります。これが、1/10 といった、大幅な圧縮を可能にしています。

白っぽい画像でにじみが発生する理由

この原理を説明すると、白い画像に黒い線…といった画像で、にじみが発生する理由が説明できます。 Jpeg では、全体の平均的な色は正確に表現できますが、隣同士の細かい色の差は思い切って間引いています。なので、黒と白が接しているような、隣同士の差が大きい画像では、間引きの影響が出てしまいます。しかも Jpeg では、隣同士の差を直接数値にしているわけではなく、市松模様の「そこらじゅうの隣同士の差を一気に表す」係数にしているため、離れた部分の影響を受けてしまったりもします。

この説明で抜けていたトピック

この説明では、以下の点が実際の jpeg とは異なっていたり、省略されていたりします。さらなる理解に役立ててください。

yuv 変換 (RGB の信号は、実際には別々に計算されるのではなく、RGB の絶対値と、その差分で計算されます)
直交変換と離散コサイン変換 (ここで用いた基本パターンは、全部の値が 1 か -1 ですが、実際には sin カーブのような値が用いられます )
ハフマン符号化 (計算された数値は、さらによく出てくる値のビット長が短くなるような符号化がされています)

JPEG の仕組み (お手軽版)