🚀 Zilliz Cloudを無料で試す、完全管理型のMilvus—10倍の高速パフォーマンスを体験しよう!今すぐ試す>>

milvus-logo
LFAI

概要

  • Scenarios
August 04, 2020
Rife Wang

Yupoo Picture Managerは数千万人のユーザーにサービスを提供し、数百億枚の画像を管理しています。そのユーザーギャラリーが大きくなるにつれ、Yupooは画像を素早く検索できるソリューションの緊急なビジネスニーズを持っています。言い換えれば、ユーザーが画像を入力すると、システムはその元画像とギャラリー内の類似画像を見つける必要があります。画像検索サービスの開発は、この問題に対する効果的なアプローチを提供します。

画像検索サービスは、2つの進化を遂げてきた:

  1. 2019年初頭に最初の技術検討を開始し、2019年3月と4月に第一世代のシステムを立ち上げた;
  2. 2020年初頭からバージョンアップ計画の検討を開始し、2020年4月から第2世代システムへの全面的なバージョンアップを開始した。

本稿では、2世代にわたる画像検索システムの技術選定と基本原理について、筆者の実体験に基づき解説する。

概要

画像とは何か?

画像を扱う前に、画像とは何かを知らなければならない。

答えは、画像とはピクセルの集まりである。

例えば、この画像の赤枠の部分は、事実上ピクセルの集まりである。

1-what-is-an-image.png 1-画像とは何か.png

仮に赤枠の部分が画像だとすると、画像内の独立した小さな四角はそれぞれピクセルであり、基本的な情報単位である。すると、画像の大きさは11 x 11 pxとなる。

2-what-is-an-image.png 2-画像とは何か.png

画像の数学的表現

各画像は行列で表すことができます。画像の各ピクセルは行列の要素に対応します。

二値画像

2値画像のピクセルは黒か白のどちらかであるため、各ピクセルは0か1で表すことができます。例えば、4 * 4の2値画像の行列表現は次のようになります:

0 1 0 1
1 0 0 0
1 1 1 0
0 0 1 0

RGB画像

3原色(赤、緑、青)を混ぜて任意の色を作ることができます。RGB画像の場合、各ピクセルは3つのRGBチャンネルの基本情報を持っています。同様に、各チャンネルが8ビットの数値(256レベル)でグレースケールを表現する場合、ピクセルの数学的表現は次のようになります:

([0 .. 255], [0 .. 255], [0 .. 255])

4×4のRGB画像を例にとると

3-4-x-4-rgb-image.png 3-4-x-4-rgb-image.png

画像処理の本質は、これらのピクセル行列を処理することである。

画像による検索の技術的問題

元の画像、つまりまったく同じピクセルを持つ画像を探すのであれば、MD5値を直接比較すればよい。しかし、インターネットにアップロードされた画像は圧縮されていたり、透かしが入っていたりすることが多い。画像にわずかな変更が加えられただけでも、MD5の結果は異なってしまうのです。ピクセルに矛盾がある限り、元の画像を見つけることは不可能です。

画像単位で検索するシステムでは、類似した内容の画像を検索したい。そのためには、2つの基本的な問題を解決する必要がある:

  • 画像をコンピュータで処理可能なデータ形式として表現または抽象化すること。
  • 計算のために比較可能なデータであること。

具体的には、以下のような特徴が必要である:

  • 画像の特徴抽出。
  • 特徴計算(類似度計算)。

第一世代の画像検索システム

特徴抽出 - 画像の抽象化

第一世代の画像検索システムでは、特徴抽出にPerceptual hashまたはpHashアルゴリズムが用いられている。このアルゴリズムの基本は何か?

4-first-generation-image-search.png 4-第一世代画像検索.png

上図に示すように、pHashアルゴリズムはハッシュ値を得るために画像に対して一連の変換を行います。変換処理中、アルゴリズムは画像を連続的に抽象化し、それによって類似画像の結果を互いに近づける。

特徴計算-類似度計算

2つの画像のpHash値の類似度を計算するには?答えはハミング距離を使うことです。ハミング距離が小さいほど、画像の内容が類似していることになります。

ハミング距離とは?異なるビットの数です。

例えば

Value 1: 0 1 0 1 0
Value 2: 0 0 0 1 1

上の2つの値には2つの異なるビットがあるので、両者のハミング距離は2である。

これで類似度計算の原理はわかった。次の問題は、1億スケールの写真から1億スケールのデータのハミング距離をどのように計算するかである。要するに、どうやって類似画像を検索するのか?

プロジェクトの初期段階では、ハミング距離を素早く計算できる満足のいくツール(あるいは計算エンジン)が見つからなかった。そこで私は計画を変更した。

私の考えは、もし2つのpHash値のハミング距離が小さければ、pHash値をカットして、対応する小さな部分が等しくなる可能性が高いということです。

例えばこうだ:

Value 1: 8 a 0 3 0 3 f 6
Value 2: 8 a 0 3 0 3 d 8

上の2つの値を8つのセグメントに分割すると、6つのセグメントの値はまったく同じである。ハミング距離が近いので、この2つの画像は類似していると推測できます。

変換後、ハミング距離の計算問題が等価性のマッチングの問題になったことがわかります。各pHash値を8つのセグメントに分割すると、まったく同じ値を持つセグメントが5つ以上ある限り、2つのpHash値は類似していることになる。

したがって、等価マッチングを解くのは非常に簡単である。伝統的なデータベースシステムの古典的なフィルタリングを使うことができる。

もちろん、私は多項式マッチングを使い、ElasticSearchのminimum_should_matchを使ってマッチングの度合いを指定しています(この記事ではESの原理は紹介しませんので、ご自身で勉強してください)。

なぜElasticSearchなのか?第一に、前述の検索機能を備えていること。第二に、画像管理プロジェクト自体がESを利用して全文検索機能を提供しており、既存のリソースを利用できるため非常に経済的である。

第一世代システムの概要

第一世代の画像検索システムでは、以下の特徴を持つpHash + ElasticSearchソリューションを選択している:

  • pHashアルゴリズムは使いやすく、ある程度の圧縮、透かし、ノイズに耐えることができる。
  • ElasticSearchは、検索に追加コストをかけることなく、プロジェクトの既存のリソースを利用する。
  • しかし、このシステムの限界は明らかである。pHashアルゴリズムは画像全体の抽象的表現である。元の画像に黒い枠線を加えるなど、画像の完全性をいったん壊してしまうと、元の画像と他の画像との類似性を判断することはほとんど不可能になる。

このような制約を打破するために、全く異なる基盤技術を持つ第二世代の画像検索システムが登場したのである。

この記事は、Milvusユーザーであり、UPYUNのソフトウェアエンジニアであるrifewangによって書かれました。この記事が気に入ったら、ぜひご挨拶に来てください! https://github.com/rifewang

Try Managed Milvus for Free

Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.

Get Started

Like the article? Spread the word

続けて読む