Evaluation of Similarity Measures for Shift-Invariant Image Motif Discovery

e4exp commented 3 years ago

光学イメージング技術の急速な発展により、データへのアクセスやデータの収集が増加し、データや知識の発見の需要が高まっています。これは、いくつかの産業や研究分野で急成長しているテーマです。今日では、適切な知識を得て学習するためには、大量の画像や信号を分析する必要があります。最近では、画像を指定せずに類似した内容の画像を検出することが、画像処理分野の研究で注目されています。画像処理におけるモチーフ探索は、画像データベースから構造を導き出したり、規則性を検出したりする問題に取り組むことを目的としています。多くのモチーフ探索手法は，前処理として画像を一次元時系列に変換し，その一次元時系列に対してモチーフ探索を行うことで，この問題を解決しています．しかし、この変換では、情報が失われるだけでなく、大きさの異なるシフトしたマルチスケールの画像モチーフを発見することができないという問題がある。

そこで本研究では，画像を一次元の時系列に変換せず，元の次元（2次元）のまま用いることで，画像データセットから異なるサイズの画像モチーフを検出する手法を提案する．

提案手法は，3つのステップで構成されている．提案手法は，マッピングまたは変換，特徴抽出，類似性の測定の3つのステップからなる．まず，画像を複素四重木のウェーブレットパケット変換によって検査し，様々なスケールの画像の幅広い周波数分析を行う．次に、ウェーブレット係数から統計的特徴を抽出します。最後に，様々な類似性尺度を用いて特徴量の類似性を測定することにより，画像のモチーフを検出します。ここでは，6つの類似性尺度の性能を詳細に評価した．さらに、ハンドジェスチャー、テキスト認識、葉や植物の識別など、様々なアプリケーションの画像を含むデータセットを用いて、提案手法の効率性を実証した。さらに，ノイズやブラーなどの歪みが重なった画像データに対して，本手法のロバスト性を検証する．

e4exp commented 3 years ago

I. はじめに

デジタルコンピューティング，テレコミュニケーション，イメージング技術の加速的な発展により，情報やデータが氾濫しています。これらのデータは，テキスト，グラフィックス，写真，ビデオ，統合されたマルチメディアなど，さまざまな形で得られます。このようなデータは、そこから効率的な情報を得ることができれば価値があります。この問題は、データマイニングや機械学習タスクによって解決されます。これらのタスクは，クラスタリング，分類，異常検知，モチーフ発見に分類される[1]．このようなタスクには，クラスタやクラスの数，各クラスのプロトタイプパターンや画像，あるいは画像を検索するためのクエリの提供などの情報が必要となる[2]．画像のクラスタリングや分類の問題や，画像データベースからクエリ画像を見つける問題は，ここ数十年の間に研究されてきた既知の問題である[3]-[5]．しかし，画像データベースから構造を抽出したり，規則性を検出したりする問題はかなり新しいテーマであり，研究者によって研究されている[6]．この新しいテーマは，モチーフ探索と呼ばれ，データベース内で頻繁に繰り返される未知の画像を，事前の情報なしに検出することを目的としている．モチーフという言葉は，遺伝学やDNA配列にそのルーツを持っています。 DNAの配列モチーフとは，生物学的に重要な意味を持つ広範なアミノ酸配列パターンのことである[7]。時系列データマイニングにおいて、モチーフという言葉はPatelらによって初めて使われました[8]。モチーフの発見は、近年、様々な画像データベースを用いた画像処理アプリケーションに応用されています。画像モチーフ探索の目的は、画像データベース内の類似した画像や形状を事前情報なしに検出することでもある。このような画像を「画像モチーフ」と呼びます。

図1は、アメリカで集められたペトログリフを例にとり、イメージモチーフの役割を強調したものである[9]。このようなペトログリフの研究は、文化や人々の広がりを示す画像であるため、人類学者にとって重要である。したがって，異なる場所で撮影された類似の画像を検出することは，人類学者にとって関心事である．図1に示すように、キャピトル・リーフで撮影された（a）と（c）の画像は、ナイン・マイル・キャニオンで撮影された（b）と（d）の画像と類似しています[10]。そのため、人類学者は、ペトログリフ画像データセットの中からこのような画像（画像モチーフ）を発見することに興味を持っています[9]。

モチーフを検出することで，調査中の問題に関する貴重な洞察をユーザに与えることができる．このテーマについては、膨大な研究が行われている[6]、[11]。しかし，多くの画像モチーフ探索手法は，画像を一次元の時系列に変換し，そのデータからモチーフ探索アルゴリズムを用いてモチーフを発見しようとするものである．この変換では，情報が失われる可能性があり，また，サイズの異なるシフトしたモチーフやマルチスケールのモチーフを検出できないという問題がある[9]．そこで，画像データを1次元の時系列に変換せず，元の次元のまま適用することで，異なるサイズのシフトしたモチーフやマルチスケールのモチーフを発見する手法が提案されている[1], [9]．

本寄稿は，[1]に掲載された論文の拡張版である．本論文では，提案手法に関する詳細な情報と包括的な結果を提供している．また，提案手法のロバスト性を確認するために，歪んだテストケースを用いてベンチマークを行った．本論文は以下のように構成されている：セクションIIでは，画像データタイプに対するモチーフ発見の関連研究を説明する．セクションIIIでは，提案手法を説明する．セクションIVでは，評価と得られた結果を示す．最後に，セクションVで結論と今後の課題を示す．

e4exp commented 3 years ago

II. 関連研究

過去数十年にわたり、画像と形状の解析は複数の研究者を魅了し、議論の対象となってきました。クラスタリング、分類、コンテンツによるクエリ、セグメンテーションなど、いくつかの画像処理タスクにおいて膨大な量の研究が行われている。[4], [12]-[15]. 最近、この研究分野に、画像・形状解析におけるモチーフ探索という新しいトピックが加わりました。

モチーフ探索は、時系列データマイニングのタスクや問題を画像・形状解析領域にリンクさせることを目的としたいくつかの研究で関心を呼び起こしています[6]、[9]、[16]。例えば，Baroneら[17]は，デジタル画像の順序付きシーケンスを分類する問題を研究している．画像モチーフの発見に関する最初のアプローチは，Xiら[9]によって提案されている．著者らは，画像や図形を1次元の時系列で表現することで，画像データセットから画像モチーフを検出した．この方法は，画像の輪郭から時系列を抽出するものである．このような手法の主な問題点は，2次元のデータを1次元に変換すると，情報が失われる可能性があることである．また，画像中の形状を得るためには，画像を分割する必要がある． Chiら[18]は、顔画像データセットから画像モチーフを検出するために、[9]と同様の手順を適用している。シェイプレットという言葉は，Ye and Keogh [16]によって導入された．シェイプレットとは、時系列全体を分析する代わりに、時系列の判別可能な部分列を考慮したものである。 Ye and Keogh [9]やGrabockaら[19]は、[9]で提案されたアプローチを拡張しました。画像を1次元表現に変換した後，シェープレットを分析してモチーフを検出する．これらの手法の性能は有望であるが，これらのアプローチはデータを1次元の時系列に変換する．

Caballero and Aranda [20]は、葉っぱの画像に対して効果的な形状ベースの画像検索システムを提案した。この輪郭記述子は、形状表現のためのポイント数を大幅に削減します。 Rakthanmanonら[21]は、画像中のモチーフを1次元の信号に表現せずに検出することで、この問題に対処した。彼らは，まず，固定サイズのスライディング・ウィンドウを用いてテスト画像をセグメント化し，次に，これらのセグメント間の類似性を一般化ハフ変換によって測定しました[22]．スライディング・ウィンドウのサイズが固定されていることは，この方法の短所の1つである．固定サイズのスライディング・ウィンドウでは，様々な比率のモチーフを検出することができないからです． Enら[23]も同様のアプローチをとっているが，彼らは20，40，80，160ピクセルとサイズの異なるスライディング・ウィンドウを採用している．我々の最初のアプローチ[24]では、画像データベース内のモチーフを、時系列に変換することなく、元の次元で発見する。画像は，DTCWT（dual tree complex wavelet transform）[25]によって複数の周波数スケールに分解され，次にウェーブレット係数から特徴が抽出され，最後に特徴の類似性を測定することでモチーフ画像が発見される．しかし，さらなる実験により，DTCWTはシフト耐性があり，シフト不変ではないことがわかった[26]．

このため，本研究では，[26]で示されたモチーフ発見のためのシフト不変特徴抽出法(SIMD)に基づいたアプローチを提案する．この方法は、我々のアプローチの中核として適用され、次のセクションで説明される。また、本論文は、[1]で発表された論文の拡張版であり、包括的な実験を行っています。

e4exp commented 3 years ago

III. 提案手法

提案手法は、パターン認識とモチーフ探索という2つの研究分野を組み合わせたものである。モチーフ発見アルゴリズムは、主に、表現ステップと類似性測定ステップから構成される。今回の提案では、図2に示したアプローチの手順に、主にパターン認識タスクで適用される特徴抽出ステップを追加している。まず、画像はCQTWP（Complex Quad Tree Wavelet Packet）により、広い周波数スケールに変換されます。ウェーブレットは、データを異なる周波数スケールで分析できること、時間-周波数分解能が柔軟であること、完璧な再構成が可能であることなどの特性を持っています。ウェーブレット変換は，信号および画像処理アプリケーションにおいてその性能が実証されている[27]-[29]．第2段階では、正規化されたウェーブレット係数から特徴が抽出されます。最後に，様々な距離尺度を用いて特徴間の類似性を測定することにより，モチーフが発見される．これらのステップを詳細に説明する前に、本稿で使用するいくつかの表記法と有用な定義を以下に説明する。

A. 定義と表記

定義1 (Image).

デジタル画像Xm,nは、2次元離散空間において、m×n, m, n ∈Nの行列で表される。

画像は、そのサイズや取り込まれるアプリケーションによって異なる。

定義2（画像モチーフ）。

画像データベースにおける画像モチーフとは、m, p∈Nを行数、n,q∈Nを列数とし、distance(X,Y)がすべての可能なペアの中で最小となるような画像のペア(X{m,n}, Y{p,q})である[9]。関数distance(X, Y)は、距離類似性指標である。

定義3 (1st-Image Motifs).

画像データベースD = X^ i , i = 1, 2, ..., N, N∈Nが与えられたとき、Dの中で最も重要な画像モチーフは、最も多くのマッチ数を持つ画像X^jである。この画像モチーフを「1st-Image Motif」と呼ぶ。

定義4（K-画像モチーフ）。

DのK番目に有意な画像モチーフは、k番目に高い量の画像マッチを持つ画像X^kである。

B. Complex Quad Tree Wavelet Packet Transform

1) 1D-CQTWP:

CQTWPは、DTCWTの欠点を克服するために提案されています。これはDTCWT[25]の拡張版で，互いに並行して動作する2つのウェーブレットパケットツリー（WPT）で構成されています． "WPT A "は信号の実数部を表し、"WPT B "は信号の虚数部を表します。 "1D-WPT A "を図3に示します。 ↓2^eと↓2^oは、偶数と奇数のダウンサンプリングを表しています。ローパス・フィルターとハイパス・フィルターは，s∈Nの場合，s g_aとs h_aで表される。パラメータsは，分解のスケールを表す。ウェーブレット係数は，i∈[0, 4^s ]の場合，s c_iで与えられる。

CQTWP で適用されるローパスおよびハイパス・フィルタは，DTCWT のフィルタと同様です． DTCWTのフィルタは、解析的で複雑なウェーブレット変換を行うために必要な条件を満たしています[25]。 CQTWPのフィルタがHilbertペアを形成している場合にのみ、信号の解析的な表現が達成されます[25], [26]。

定義 5.

以下の性質を持つウェーブレットψaとψbはヒルベルトペアと呼ばれる PSI(j omega)はpsi(t)のフーリエ変換．

その結果、「WPT A」の各ブランチの応答と「WPT B」の対応するブランチの応答はヒルベルト対を形成し、したがって、CQTWPは各サブバンドでほぼ解析的になります。解析的な表現には、複素数のウェーブレット係数が得られるほか、エイリアシングの低減などの利点があります。 Hilbert形式のウェーブレットを実現するためには、以下の定理に基づいて設計する必要があります。

定理1 (ハーフサンプル遅延 [30]).

ウェーブレットψa とψb は、フィルタs g_a と s g_b が以下の条件を満たす場合、ヒルベルト対を形成する。

式（1）は、マグニチュード関数と位相関数で表すことができます。

これは、2つのローパスフィルタs g_a, s g_bの間の、いわゆる「ハーフサンプル・ディレイ」条件である。

証明

証明はSelsnickによって[30]に表されている。ハーフサンプルディレイの定理に基づき、スケーリングローパスフィルタは半サンプルずつ互いにオフセットしていなければならない。これは、Yu and Ozkaramanli [31]によって証明された、2つのウェーブレットがヒルベルト変換ペアを形成するための必要かつ十分な条件である。

定義6（q-shiftフィルター[32]）。

このような適切なフィルタを設計するためのKingsburyの解法は「q-shift」と呼ばれ、定理1で与えられた「半サンプル遅れ」の条件を満たす、ローパスフィルタを以下のように設定する。

ここで、M∈N +は、フィルタs gbの偶数長であり、0≦n≦M - 1に対応している。半サンプル遅延の定理を実現するためには、各スケールにおいて、2秒ずつ変換されたWPT Aのフィルターが、変換されたWPT Bのフィルターの中間に位置する必要があります。すべてのフィルターは実数で、直交しており、Abdelnour [33]とKingsbury [32]によって与えられた設計によって得られます。最初のスケールでは，フィルタの偶数長は10 [33]であり，1より大きいスケールでは，フィルタの偶数長は14 [32]である． CQTWPのウェーブレット関数とスケーリング関数は次のように定義されます。

e4exp / paper_manager_abstract