How to compress an image by 10 times?

背景

ユーザーがスマートフォンで衣類の写真を撮影したとき、類似画像を探したいという明確なニーズがある。画像検索プロジェクトの目的は、このユーザーニーズに応えることだ。

プロジェクトは当初 5 カテゴリを想定し、各カテゴリに 500 万枚の画像を検索対象として保持する。特徴抽出後、各画像は 30976 次元空間内の 1 つの点として表現される。つまり、30976 個の浮動小数点値で表現できる。処理を容易にするため、特徴値に 100000 を乗算し、浮動小数点値の精度を損なわずに int32_t で画像特徴を格納する。

画像検索時には、クエリ画像とインデックス画像のユークリッド距離を計算する必要がある。画像間のユークリッド距離計算には 50 マイクロ秒かかる。CPU 命令セット最適化（SSE）により、ユークリッド距離計算時間は 13 マイクロ秒に短縮される。

圧縮前、全画像のサイズは 3T（4 × 30k × 25000000）で、各マシンには画像格納用に 30G のメモリがあり、全量を格納するには 100 台のマシンが必要だ。

ユークリッド距離計算の効率を低下させずに画像を圧縮し、大規模なマシン占有を削減する必要がある。
目標は約 500G への圧縮、つまり各画像を圧縮後約 20k にし、ユークリッド距離計算を約 15 マイクロ秒に収めることだ。

ユークリッド距離計算にはマイクロ秒レベルの処理時間が必要だ。p4delta や valgrind 圧縮などの既存の圧縮方式では性能要件を満たせないため、データの特性に応じたカスタム圧縮方式を設計する必要がある。

成果
現在の圧縮方式により、単一画像を 120k から平均 13k に圧縮した。
ユークリッド距離計算は平均 9 マイクロ秒だ。
いかにしてこれほど信頼性の高い結果を達成したのか。

初期の取り組み

ビットマップ方式
データの特性を観察したところ、各画像には平均 7000 個の非ゼロ値があり、残りはすべて 0 であることが分かった。最初に思いつくのは、ビットマップで 30976 個の値の各位置がゼロかどうかを示す方法だ。ビットマップには 30976 / 8 = 4k バイトが必要だ。そして非ゼロ値のみを格納すれば 7k × 4 が必要となり、圧縮後の各画像の平均サイズは 32k となる。圧縮コードの大枠は次のとおりだ。

ただし、画像間のユークリッド距離を計算する際、ビットマップを 30976 回走査し、特定のビットがゼロかどうかを判定する必要がある。つまり、ビットマップとマスク配列の AND 演算を行うが、これに時間がかかり、計算には 100 マイクロ秒以上を要する。2 枚の圧縮画像のユークリッド距離を計算するコードは次のとおりだ。

オフセット圧縮方式の使用
非ゼロデータのオフセットと値のみを保存する。オフセットの最大値は 30975 で、int16_t で保存する必要がある。値の範囲は 0 から 100 万で、int32_t で表現する必要がある。この方式では、各画像の占有スペースは 42k（7k × (2 + 4)）だ。

2 枚の圧縮画像のユークリッド距離を計算する際、オフセットに基づいてマージする方法を用いる。


この方式でユークリッド距離計算に 55 マイクロ秒かかる。if 条件分岐に時間がかかると考え、if をビットマスクに置き換えてみた。

この方式では if 条件判定を排除できるが、処理時間は 70 マイクロ秒で、かえって性能が低下した。時間増加の原因は CPU 命令数の増加だ。

性能最適化
シーン分析

2 枚の圧縮画像の計算 → 1 枚の圧縮画像と 1 枚の非圧縮画像
現在の最適化はボトルネックに直面している。どうすれば性能を 10 マイクロ秒レベルまで向上できるか。アプリケーションシナリオを改めて考えてみよう。オンラインシナリオではクエリ画像と一連の画像の距離を計算し、オフラインシナリオでは中心点画像と一連の他の画像の距離を計算する。つまり、1 枚の画像と複数枚の画像の距離計算だ。この場合、1 枚の画像は圧縮する必要がなく、完全に非圧縮でよい。圧縮されている場合でも、先に伸張してからユークリッド距離を計算できる。実際、1 枚の非圧縮画像と複数枚の圧縮画像のユークリッド距離計算に変換できる。このような状況では、効率向上の課題を再考する必要がある。

オフセット圧縮方式の採用を確認
1 枚の圧縮画像と 1 枚の非圧縮画像のユークリッド距離計算について、ビットマップ圧縮方式とオフセット圧縮方式を比較する。オフセット圧縮方式に明確な優位性がある。ビットマップ方式では、最も時間がかかるのは依然としてビットマップへの 30976 回のアクセスと、AND 演算による伸張値の取得だ。ビットマップを 30976 回走査するには少なくとも 50 マイクロ秒かかる。一方、オフセット方式は非ゼロデータ 7000 個のオフセットを保持しているため、非ゼロ配列を 7000 回走査するだけでユークリッド距離を計算できる。

1 枚の圧縮画像と 1 枚の非圧縮画像

実装
まず非圧縮画像の累積平方和を事前に計算する。各クエリで複数回のユークリッド距離計算を行うが、累積平方和の計算は 1 回だけでよい。

圧縮画像の配列を走査し、その値ともう一方の非圧縮画像の対応するオフセット位置の値の差分の二乗を計算する。

圧縮画像のゼロ値については、ユークリッド距離に非圧縮画像のそれらの値の二乗和を加えるだけでよい。

例：
a. 非圧縮画像：[0 2 3 0 4 0 0 5 6 0 0]、圧縮画像：[0 0 0 6 6 6 0 0]
b. 非圧縮画像の特定ビットまでの全値の二乗和を事前に計算：sqrt[0 4 13 13 29 29 29 54 90 90 90]
c. 圧縮配列は off[3 4 5]、data[6 6 6]
d. off 配列と data 配列を走査

olength += (6 - 0) * (6 - 0) olength += (sqrt[2] - sqrt[0])
olength += (6 - 4) * (6 - 4)olength += (sqrt[3] - sqrt[3])
olength += (6 - 0) * (6 - 0) olength += (sqrt[4] - sqrt[4])
効率：20 マイクロ秒
この方式では配列を 7000 回走査し、7000 回の差分二乗演算と 7000 回の sqrt 配列アクセスを行うだけで、複雑度が大幅に削減される。

コードは次のとおり：
data1 は圧縮データ、data2 は非圧縮データ：

二乗差の展開

さらに最適化された方法はあるか。
ユークリッド距離の計算式は (a[1]-b[1])(a[1]-b[1]) + (a[2]-b[2])(a[2]-b[2]) + ... +(a[n]-b[n])*(a[n]-b[n]) だ。

展開すると、a[1]a[1] + a[2]a[2] + ... +a[n]a[n]+ b[1]b[1] + b[2]b[2] + ... b[n]b[n] - 2(a[1]b[1] + a[2]b[2] + ... + a[n]b[n]) となる。

そして a[1]a[1] + ... a[n]a[n] と b[1]b[1] + ... + b[n]b[n] は圧縮時に事前に計算して保存できる。圧縮にはより多くの時間をかけられるからだ。したがって、ユークリッド距離の計算には a[1]b[1] + a[2]b[2] + ... + a[n]*b[n] を計算するだけでよい。

たとえば、上記の例の場合：
a. 非圧縮画像：[0 2 3 0 4 0 0 5 6 0 0]、圧縮画像：[0 0 0 6 6 6 0 0]
b. 圧縮画像と非圧縮画像の二乗和を計算。sqrt1：90 sqrt2：108
c. 各クエリ画像の二乗和を計算。圧縮画像の二乗和は圧縮時に計算して保存する。
d. 圧縮配列を走査

multi += 6 * 0
multi += 6 * 4
multi += 6 * 0
e. ユークリッド距離 = 90 + 108 - 2 * multi
効率：11 マイクロ秒
この方式では乗算 7000 回のみを計算し、上記の方式と比較して効率が倍増する。

圧縮率の最適化
基本のオフセット圧縮

方式
基本のオフセット圧縮については前述した。

効果
各画像を 42k に圧縮する。

例
画像：[5 5 8 0 0 ... 0 7 6 3 0 0 0 0]（8 と 7 の間に 500 個の 0）。208 は二乗和、6 は非ゼロ要素数。

オフセットの最適化

方式
基本方式では int16_t で非ゼロデータのオフセットを保存する。非ゼロ値の各オフセットは 2 バイトを占有する。オフセットの占有スペースをどう削減するか。

自然な発想として、データのオフセットと直前の非ゼロデータのオフセットの差分を保存する方法が考えられる。この場合、値は大幅に小さくなり、通常 255 以下になるため、uint8_t でオフセット差分を保存できる。

しかし、オフセット差分が 255 より大きい場合はどうするか。

ゼロ値の一部を非ゼロ値として保存する。2 つの非ゼロ値間のオフセットが 255 より大きい場合、最初の非ゼロオフセット + 255 の位置に値 0 の非ゼロ値を配置する。

その 0 のオフセットと次の非ゼロオフセットの差分が 255 未満なら次の非ゼロ値を保存し、そうでなければさらに別の非ゼロ値を追加する。

統計によると、オフセット差分が 255 を超える非ゼロ値は各画像に平均 2 個あり、性能への影響はほぼない。

効果
この方式を用いれば、オフセット部分は 1 バイトを占有し、圧縮後の画像サイズは 7k × (1+4) = 35k となる。

例：
画像：[5 5 8 0 0 ... 0 7 6 3 0]（8 と 7 の間に 500 個の 0）。

下図に示すように、非ゼロ要素数は 7 個になる。要素 8 と 7 のオフセット差分が 255 を超えるため、オフセット差分が 255 未満になるよう追加の 0 を非ゼロ値として加える。ユークリッド距離計算時には影響がない。

値の最適化

方式
値は int32_t で格納されている。統計によると、65535 を超える値は平均 6 個あり、uint16_t で値を格納する。65535 を超える値は圧縮バッファの末尾に配置し、int32_t で格納する。

効果
圧縮後、各画像のサイズは 7k × (2+1) = 21k となる。

例：
画像：[5 5 8 0 0 0 0 7 67676 66666 0 0 0]。

下図に示すように、9024396695 は二乗和、4 は uint16_t の値の数、2 は uint16_t を超える値の数だ。前方の非ゼロ値は uint16_t で格納され 2 バイトを占有し、後方の 67676 と 66666 は 65535 より大きいため int32_t 型で格納され 4 バイトを占有する。各画像で 65535 を超える値は平均 6 個のため、スペース占有は大幅に削減される。

重複値の除去

さらに圧縮する可能性はあるか。

方式
データを分析したところ、画像内の隣接する非ゼロ値の多くが同じ値であることが分かった。統計によると、平均して各画像に隣接する非重複値は 2400 個、隣接する重複値は 4300 個あり、そのうち 700 個が 2 隣接で同じ値、3600 個が 3 隣接で同じ値だ。

例：0 1 1 1 0 0 3 3 3 2 2 0 0。

上記の 1 1 1 と 3 3 3 と 2 2 を正規化し、1、3、2 とその個数のみを保存すれば、スペースをさらに圧縮できる。各値の個数をどこに格納するか。オフセット配列に格納する。現在のオフセットは 8 ビットで保存され、最大オフセット差分 255 を保持する。8 ビットのオフセットを分割し、6 ビットでオフセット差分を保存する。最大保存差分は 63 で、残り 2 ビットで同一値の個数を保存する。格納可能な同一値数は 0（未使用）、1、2、3 だ。

統計によると、オフセット差分が 63 を超える値は各クエリに平均 250 個あり、追加で 200 個以上のゼロ値を保存する必要があるが、スペース占有への影響は特に大きくない。

効果
この方式で画像を 13k に圧縮する。おおよそ 2.4k × 3 + (1.2+0.3)k × 3 に等しい。2.4k は隣接する非重複値の数、1.2k は 3 つ隣接する重複値の数、0.3k は 2 つ隣接する重複値の数、3 は 1 バイトのオフセット + 2 バイトの値だ。

オフセット差分が 63 を超える場合と値が 65535 を超える場合のスペースへの影響は小さい。

ユークリッド距離計算の処理時間は 35 マイクロ秒になる。効率低下の主な原因は、int8_t のバイトを 6 ビットと 2 ビットに分割することだ。

例：
画像：[0 1 1 1 0 0 3 3 3 2 2 0 0]

38 は二乗和、3 は値の数、0 は 65535 を超える値の数を表す。(1:3) は uint8_t で表現され、最初の 6 ビットはオフセット 1 を格納し、残り 2 ビットは 3 つの同一値があることを示す。(5:3) も同様で、オフセット差分が 5、同一値が 3 つあることを示す。(3:2) も同様だ。以下の 1 3 2 は非ゼロ値で、直前の方式との違いは重複値がないことだ。隣接する同一値は 1 つのみ保存される。

重複値除去の最適化

上記の方式は圧縮率が高いものの、効率が低下している。効率を改善できるか。

方式

上記の方式では、オフセットを 6 ビットと 2 ビットに分割しているため効率が低下している。ユークリッド距離の計算時に AND 演算が必要となり、複雑度が増す。

保存時に、非重複値をまとめて保存し、2 回重複値をまとめて保存し、3 回重複値をまとめて保存する。これにより、ユークリッド距離の計算時に 3 回重複値を走査する際、3 回の乗算を計算するだけでよく、重複値の個数を保持する必要がない。

この方式のオフセット差分は変化する。非ゼロ値間のオフセット差分ではなく、非重複値のオフセット差分と 3 重複値間のオフセット差分だ。このオフセットは増加する。統計によると、重複値間のオフセット差分が 255 を超えるものが 4 個、2 重複値間のオフセット差分が 255 を超えるものが 25 個、3 重複オフセット間の差分が 255 を超えるものが 5 個ある。2 重複値の方が 255 を超えるオフセット差分が多い理由は、2 重複値が約 300 個と少なく、互いの距離が比較的遠いためだ。つまりオフセット差分が比較的大きい。そこで、2 重複値は非重複値として扱う。

効果
この方式で画像を約 14k に圧縮する。(2.4k + 0.7k) × 3 + 1.3k × 3。2.4k は非重複値の合計、0.7k は重複数 2 の値の合計、1.3k は重複数 3 の値の合計。3 はオフセットバイト + 値バイト。その他の値は総スペースに無視できる影響しか与えない。

性能：9 マイクロ秒。11 マイクロ秒をベースに 2 マイクロ短縮された。重複数が 3 の場合、配列の繰り返し走査が不要なためだ。配列の走査回数は 7000 回ではなく 3000 + 1300 = 4300 回だ。

例：
画像：[0 1 1 1 0 0 3 3 3 2 2 0 0]。

38 は二乗和、2 は非重複値の数を表す。次の 2 は重複数 3 の値の数を表す。0 は 65535 を超える値の数を表す。9 と 1 は非重複値のオフセット差分を表し、2 と 2 は非重複値を表す。1 と 5 は重複数 3 のオフセット差分を表し、1 と 3 は重複数 3 の値を表す。