(57)【要約】【課題】記述子関連のアルゴリズムの複雑さを減らしながら、画像をより効果的且つ効率的な方法で記述、索引付け、および検索できるようにＡＲＴ記述子の精度を向上させる【解決手段】画像検索システムは、画像を入力すべく構成された画像入力ユニットを含んでいる。記述子決定ユニットが画像を受信し、例えば、距離変換（ＤＴ）アプリケーションを用いて当該画像を中間画像に変換して当該画像の記述子を生成する。画像比較ユニットは、当該画像の記述子を複数の候補画像の記述子と比較することにより、当該画像を複数の候補画像と比較する。最後に、検索ユニットがこれらの記述子の比較に基づいて入力画像に類似している１個以上の候補画像を取得する。【選択図】図２
2010531010.tif 000002
【特許請求の範囲】
【請求項１】
入力として画像を受信すべく構成されている画像入力ユニットと、
前記画像を中間画像に変換して前記画像の記述子を生成すべく構成されている記述子決定ユニットと、
前記画像の記述子を１個以上の候補画像の記述子と比較することにより、前記画像を前記１個以上の候補画像と比較すべく構成されている画像比較ユニットと、
前記画像に類似している前記１個以上の候補画像の少なくとも１個を、それらの記述子の比較に基づいて取得すべく構成されている検索ユニットと、を含む画像検索システム。
【請求項２】
前記記述子決定ユニットが、第１の変換ユニットおよび第２の変換ユニットを含んでいる、請求項１に記載の画像検索システム。
【請求項３】
前記入力画像に類似している前記１個以上の候補画像の少なくとも１個を表示すべく構成されているディスプレイをさらに含んでいる、請求項１に記載の画像検索システム。
【請求項４】
前記複数の候補画像を格納するデータベースをさらに含んでいる、請求項１に記載の画像検索システム。
【請求項５】
前記画像比較ユニットが、前記画像の記述子と前記候補画像の記述子との距離を測定して前記画像を前記複数の候補画像と比較すべく構成されている、請求項１に記載の画像検索システム。
【請求項６】
前記検索ユニットが、前記画像との距離が最短である前記１個以上の候補画像の少なくとも１個を取得すべく構成されている、請求項５に記載の画像検索システム。
【請求項７】
前記第１の変換ユニットが前記画像に対して距離変換（ＤＴ）を実行する、請求項２に記載の画像検索システム。
【請求項８】
前記第１の変換ユニットが前記画像の追加的な特徴を生成すべく構成されている、請求項７に記載の画像検索システム。
【請求項９】
前記画像の追加的な特徴が、前記画像の等高線、中間軸、および形状の骨格のうち少なくとも１個を含んでいる、請求項８に記載の画像検索システム。
【請求項１０】
前記第２の変換ユニットが、前記第１の変換ユニットにより処理された前記画像に対してアンギュラー・ラディアル・トランスフォーム（ＡＲＴ）を実行すべく構成されている、請求項２に記載の画像検索システム。
【請求項１１】
画像に関連付けられた記述子を生成する装置であって、
画像を入力すべく構成されている入力ユニットと、
前記画像を中間画像に変換すべく構成されている第１の変換ユニットと、
前記中間画像に作用して前記画像の記述子を生成すべく構成されている第２の変換ユニットと、を含む装置。
【請求項１２】
前記中間画像がグレースケール画像である、請求項１１に記載の装置。
【請求項１３】
前記第１の変換ユニットが前記画像に対して距離変換（ＤＴ）を実行すべく構成されている、請求項１１に記載の装置。
【請求項１４】
前記第１の変換ユニットが前記画像の追加的な特徴を生成すべく構成されている、請求項１３に記載の装置。
【請求項１５】
前記画像の追加的な特徴が、前記画像の等高線、中間軸、および形状の骨格のうち少なくとも１個を含んでいる、請求項１４に記載の装置。
【請求項１６】
前記第２の変換ユニットが、前記第１の変換ユニットにより処理された画像に対してアンギュラー・ラディアル・トランスフォーム（ＡＲＴ）を実行すべく構成されている、請求項１１に記載の装置。
【請求項１７】
前記第２の変換ユニットが、前記中間画像の特徴を表す１個以上の係数に前記中間画像を変換すべく構成されている、請求項１１に記載の装置。
【請求項１８】
前記第２の変換ユニットが、前記１個以上の係数を集めて前記画像の記述子を生成すべく構成されている、請求項１７に記載の装置。
【請求項１９】
前記装置が携帯機器である、請求項１１に記載の装置。
【請求項２０】
画像を中間画像に変換すべく構成されている変換ユニットと、
前記中間画像から前記画像の記述子を生成すべく構成されている記述子生成ユニットと、
前記画像の記述子を１個以上の候補画像の記述子と比較すべく構成されているマッチングユニットと、を含む画像マッチング装置。
【請求項２１】
前記１個以上の候補画像を格納すべく構成されている記憶装置をさらに含んでいる、請求項２０に記載の画像マッチング装置。
【請求項２２】
前記マッチングユニットが、前記画像の記述子と前記１個以上の候補画像の記述子との距離を測定すべくさらに構成されている、請求項２０に記載の画像マッチング装置。
【請求項２３】
前記変換ユニットが前記画像に対して距離変換（ＤＴ）を実行して中間画像を生成すべく構成されている、請求項２０に記載の装置。
【請求項２４】
前記記述子生成ユニットが、前記変換ユニットにより処理された画像に対してアンギュラー・ラディアル・トランスフォーム（ＡＲＴ）を実行すべく構成されている、請求項２０に記載の装置。
【請求項２５】
画像の記述子を生成する方法であって、
入力として画像を受信するステップと、
前記画像を中間画像に変換するステップと、
前記中間画像に基づいて前記画像の記述子を生成するステップと、を含む方法。
【請求項２６】
前記画像を変換するステップが、前記画像に対して距離変換（ＤＴ）を実行するステップを含んでいる、請求項２５に記載の方法。
【請求項２７】
前記記述子を生成するステップが、アンギュラー・ラディアル・トランスフォーム（ＡＲＴ）を実行するステップを含んでいる、請求項２５に記載の方法。
【請求項２８】
画像を中間画像に変換するステップと、
前記中間画像の特徴に基づいて前記画像の記述子を生成するステップと、
前記画像の記述子を候補画像の記述子と比較することにより、前記画像を１個以上の前記候補画像と比較するステップと、
前記記述子の比較に基づいて、前記画像に類似している前記１個以上の候補画像の少なくとも１個を取得するステップと、を含む、画像検索方法。
【請求項２９】
前記画像を比較するステップが、前記画像の記述子と前記候補画像の記述子との距離を測定して前記画像を前記複数の候補画像と比較するステップを含んでいる、請求項２８に記載の画像検索システム。
【請求項３０】
１個以上の候補画像を取得するステップが、前記画像との距離が最短である前記候補画像の少なくとも１個を取得するステップを含んでいる、請求項２９に記載の画像検索システム。
【請求項３１】
コンピュータにより実行されたときに、画像の記述子を生成する方法を前記コンピュータに実行させる命令を格納しているコンピュータ可読媒体であって、前記方法が、
画像を中間画像に変換するステップと、
前記中間画像に基づいて前記画像の記述子を生成するステップと、を含んでいる、コンピュータ可読媒体。
【請求項３２】
コンピュータにより実行されたときに、画像を取得する方法を前記コンピュータに実行させる命令を格納しているコンピュータ可読媒体であって、前記方法が、
画像を中間画像に変換するステップと、
前記中間画像の特徴に基づいて前記画像の記述子を生成するステップと、
前記画像の記述子を候補画像の記述子と比較することにより、前記画像を複数の前記候補画像と比較するステップと、
前記記述子の比較に基づいて前記画像に類似している１個以上の候補画像を取得するステップと、を含んでいる、コンピュータ可読媒体。
【請求項３３】
コンピュータにより実行されたときに、画像の記述子を生成する方法を前記コンピュータに実行させる命令を含むコンピュータプログラムであって、前記方法が、
入力画像を受信するステップと、
前記画像を中間画像に変換するステップと、
前記中間画像に基づいて前記画像の記述子を生成するステップと、を含むコンピュータプログラム。
【請求項３４】
コンピュータにより実行されたときに、画像を取得する方法を前記コンピュータに実行させる命令を含むコンピュータプログラムであって、前記方法が、
入力画像を中間画像に変換するステップと、
前記中間画像の特徴に基づいて前記画像の記述子を生成するステップと、
前記画像の記述子を候補画像の記述子と比較することにより、前記画像を複数の前記候補画像と比較するステップと、
前記記述子の比較に基づいて前記画像に類似している１個以上の候補画像を取得するステップと、を含んでいる、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
技術分野
本開示は一般に、画像記述子（image descriptors）に関する。
【背景技術】
【０００２】
背景
デジタル・カメラ、画像編集ソフトウェア、および他の関連技術、装置、またはその両方が広く利用されているため、ユーザはデジタル画像の管理および操作を強いられている。ユーザが効率的且つ効果的に画像を管理、検索、操作、および使用できる機能を提供することがデジタル画像装置、アプリケーションまたはその両方にとって重要な態様である。その結果、記憶装置から画像を取得する効率的且つ簡単な方法を開発する努力がなされている。例えば、画像処理分野において、動画エキスパートグループ（ＭＰＥＧ）は数種類の画像検索アプリケーションを開発している。
【０００３】
例示的な画像検索アプリケーションは、画像の索引付けおよび検索のために画像の記述子を生成することができる。画像の形状は、画像の記述に利用できる有用な特徴である。形状は、色、テクスチャ等、画像の他の特徴を含める必要無しに、画像を地理的形状だけで記述することができる。例えば、ＭＰＥＧは、曲率尺度空間（ＣＳＳ）記述子およびアンギュラー・ラディアル・トランスフォーム（ＡＲＴ）記述子として公知のものを含むいくつかの記述子を採用している。
【０００４】
ＣＳＳ記述子は、画像の１本以上の等高線に関する情報に基づいて画像の特徴を抽出する。一方、ＡＲＴ記述子は、等高線に関する情報を直接使用せず、その代わりに画像に関する領域固有の情報、例えば画像内における画素の位置により変化する画素値のアンギュラー成分およびラディアル成分を利用する。ＡＲＴはこのように、画像内の等高線の数とは無関係に、各種の画像に対してより一般的に適用することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、従来のＡＲＴ記述子には限界がある。例えば、等高線が１本である画像のように比較的単純な特徴を有する画像の場合、ＡＲＴ記述子は、画像の形状を表す際の精度で所望のレベルを達成することができない。その理由は、正確なＡＲＴ記述子を取得するには画像の各種の側面に関する情報を抽出する必要があるためである。さらに、ＡＲＴ記述子は、相当の計算リソースを要する比較的複雑な数値アルゴリズムに依存している。従って、記述子関連のアルゴリズムの複雑さを減らしながら、画像をより効果的且つ効率的な方法で記述、索引付け、および検索できるようにＡＲＴ記述子の精度を向上させることが必要である。
【課題を解決するための手段】
【０００６】
概要
一実施形態において、距離変換（ＤＴ）装置を用いて、入力されたクエリー画像用に追加的な特徴（例えば、記述子パラメータ）を提供する中間画像を生成する。ＤＴユニットは、入力クエリー画像を、画像内の画素の位置に応じて各種の画素値を有する中間画像に変換することができる。中間画像内で生成された各種の画素値は、クエリー画像用の画像記述子をより効率的且つ効果的に生成すべく利用することができる追加的な画像属性または記述子パラメータとして用いられる。画像記述子生成装置は、中間画像に対しＡＲＴ記述子生成アルゴリズムを適用することにより、入力クエリー画像の記述子を生成することができる。
【０００７】
別の実施形態において、画像検索システムは、画像入力ユニット、記述子決定ユニット、画像比較ユニット、および検索ユニットを含んでいる。画像入力ユニットは、入力として画像を受信すべく構成されている。記述子決定ユニットは、ＤＴユニットを用いて画像を受信して中間画像に変換し、画像の記述子を生成すべく適合されている。画像比較ユニットは、例えばクエリー画像の記述子をデータベースに格納されている画像の記述子と比較することにより、画像をデータベースに格納されている１個以上の画像と比較すべく構成されている。最後に、検索ユニットは、記述子の比較に基づいて、入力画像に極めて良く一致している、または類似している１個以上の候補画像を取得すべく構成されている。
【０００８】
本概要は、特定の概念を、以下の詳細な説明でさらに述べる単純化された形式で導入すべく提供するものである。本概要は、権利請求対象である主題の重要な特徴または本質的な特徴を示すものではなく、また権利請求対象である主題の範囲を限定することを意図するものではない。
【図面の簡単な説明】
【０００９】
図面の簡単な説明
【図１】一実施形態による画像検索システムの模式的ブロック図を示す。
【図２】一実施形態による画像検索システムの画像マッチングユニットの模式的ブロック図である。
【図３】一実施形態による距離変換（ＤＴ）の適用を示す模式図である。
【図４】一実施形態による２値画像を中間画像に変換する距離変換の適用を示す模式図である。
【図５】一実施形態によるＤＴの結果を表す例示的な画像を示す。
【図６】一実施形態において用いられるＡＲＴの基底関数の例を示す。
【図７】一実施形態による記述子生成方法を示すフロー図である。
【図８】一実施形態による、記述子を用いた画像検索方法を示すフロー図である。
【図９】本開示による装置および方法の一実施形態によるＧＡＲＴ（グレーレベル・アンギュラー・ラディアル・トランスフォーム）記述子と、従来のＡＲＴ記述子との的中率（ＢＥＰ）で測定したデータベース検索性能を比較して示す図である。
【発明を実施するための形態】
【００１０】
詳細な説明
本明細書に主に記述し、図示するように、本開示の構成要素を多様な異なる構成で配置および設計できる点が容易に理解されよう。従って、図に示すように、本開示による装置および方法の実施形態をより詳細に以下に記述しているが、権利請求する本開示の範囲を限定することを意図しておらず、あくまでも本開示に従い現在考察している実施形態の特定の例を表しているに過ぎない。以下に記述する実施形態は図面を参照すれば理解可能であり、図面全体を通じて同一要素は同一の参照番号で示されている。
【００１１】
図１を参照するに、画像検索システム１００の一実施形態を示す。画像検索システム１００は、コントローラ１１０、画像入力ユニット１２０、画像マッチングユニット１４０、記憶装置としてのデータベース（ＤＢ；１６０）、およびディスプレイ１８０を含んでいてよい。各々の構成要素１１０、１２０、１４０、１６０および１８０は、所望の実施態様に従い、単一ユニットまたは装置、あるいは１個以上のユニットまたは装置として提供されていてよい。例えば、画像マッチングユニット１４０およびＤＢ１６０は、画像入力ユニット１２０と一体化された単一の装置に実装されていてよい。あるいは、画像マッチングユニット１４０およびＤＢ１６０は、画像入力ユニット１２０とは別個に遠隔的に実装されていてもよい。
【００１２】
実際には、ユーザは画像入力ユニット１２０を用いて画像検索システム１００への入力用の画像を選択することができる。画像入力ユニット１２０は、キーパッド、キーボード、マウス、タッチパッド、タッチスクリーン、ポインティングデバイス、トラックボール、ライトペン、ジョイスティック、音声認識装置、スタイラス装置、目および頭の動作トラッカ、デジタイザ・タブレット、バーコードリーダ等、様々な形式の入力装置を含んでいてよいがこれに限定されず、これら各々がユーザに所望のクエリー画像に入力するためのインターフェースを提供することができる。画像入力ユニット１２０は次いで、コントローラ１１０により構成またはプログラムされた通りに、入力された画像を画像マッチングユニット１４０へ配信することができる。
【００１３】
画像マッチングユニット１４０が画像入力ユニット１２０とは別個の遠隔装置またはサーバにインストールされている特定の実施形態において、入力画像は有線または無線通信プロトコルを介して画像入力ユニット１２０から画像マッチングユニット１４０へ送信することができる。例えば、シリアルポート、パラレル・ポート、ＰＳ／２ポート、ユニバーサル・シリアル・バス（ＵＳＢ）リンク、ファイアワイヤまたはIEEE1394リンク等のデジタル・インターフェース・プロトコル、あるいは赤外インターフェース、BlueTooth、ZigBee、高解像度マルチメディア・インターフェース（ＨＤＭＩ）、高帯域デジタルコンテンツプロテクション（ＨＤＣＰ）、無線フィデリティ（Ｗｉ−Ｆｉ）等の無線インターフェース接続を採用することにより、通信プロトコル（有線または無線の）を実装することができる。あるいは、モバイル通信用グローバルシステム（ＧＳＭ）、全地球測位システム（ＧＰＳ）、デジタルモバイルマルチメディア（ＤＭＢ）、符号分割多重アクセス（ＣＤＭＡ））、高速ダウンリンク・アクセス（ＨＳＤＰＡ）、Ｗｉ−Ｂｒｏ無線ブロードバンド等の移動通信システム経由で画像を画像マッチングユニット１４０へ送信することができる。
【００１４】
画像マッチングユニット１４０は、画像（例えば、クエリー画像）を受信して、受信した画像が画像の識別またはマッチング用の記述子を含んでいるか否かを判定することができる。画像マッチングユニット１４０が記述子の検出に失敗した場合、画像マッチングユニット１４０は次いで、クエリー画像に記述子生成アルゴリズムを適用することによりクエリー画像用に記述子を取得する処理を開始することができる。画像マッチングユニット１４０は、クエリー画像の記述子をＤＢ１６０に保存されている候補画像の記述子と比較して少なくとも１個のマッチング画像を選択する。マッチング画像は、例えばユーザの参照用にディスプレイ１８０へ配信される。
【００１５】
図２に、画像マッチングユニット１４０の一実施形態を示す。いくつかの実施形態において、画像マッチングユニット１４０は、記述子生成ユニット２８０および類似度比較ユニット２６０を含んでいてよい。図２に示すように、記述子生成ユニット２８０は距離変換ユニット（ＤＴユニット）２２０およびアンギュラー・ラディアル・トランスフォームユニット（ＡＲＴユニット）２４０を含んでいてよい。画像マッチングユニット１４０は、画像入力ユニット１２０から、クエリー画像２１０を受信し、クエリー画像２１０をＤＢ１６０に保存されている候補画像とマッチングさせる処理を実行する。例えば、画像マッチングユニット１４０は、クエリー画像２１０の記述子を候補画像の記述子と比較することにより、クエリー画像２１０を候補画像とマッチングさせることができる。画像マッチングユニット１４０は、マッチング画像２７０をディスプレイ１８０へ配信する。
【００１６】
特定の実施形態において、記述子生成ユニット２８０がクエリー画像２１０を受信した際に、記述子生成ユニット２８０内のＤＴユニット２２０がクエリー画像２１０を中間画像に変換して、中間画像をＡＲＴユニット２４０へ配信する。例えば、ＤＴユニット２２０は、入力クエリー画像を、入力画像の形状に対応する形状を有する２値画像に変更して、該２値画像を、２値画像との境界に対する相対的な画素の位置に応じた種々の画素値を有する中間画像に変換することができる。ＡＲＴユニット２４０は中間画像に対しＡＲＴ記述子生成アルゴリズムを実行することにより、データベースに格納される画像との最終的な比較およびマッチングのために、入力クエリー画像２１０の記述子を生成することができる。ＡＲＴユニット２４０は、追加的な特徴またはパラメータとして中間画像の多様な画素値を用いて、原入力画像（すなわちクエリー画像２１０）の記述子を生成することができる。ＡＲＴユニット２４０は、記述子およびクエリー画像２１０を類似度比較ユニット２６０へ配信する。類似度比較ユニット２６０は次いで、クエリー画像２１０の記述子をＤＢ１６０に保存されている画像の記述子と比較することにより、クエリー画像２１０に最も良く類似している候補画像をＤＢ１６０から検索して取得することができる。候補画像の記述子は、候補画像と共に事前にＤＢ１６０に保存されていてよい。あるいは、画像マッチングユニット１４０は、候補画像の１個を無作為に、あるいはＤＢ１６０に保存されている候補画像に付与されたシーケンス番号を用いて選択することができる。画像マッチングユニット１４０は、クエリー画像２１０の記述子の生成に用いたのと同一の処理を適用して候補画像の記述子を生成する。画像マッチングユニット１４０はこのような方法で、クエリー画像が候補画像と比較される時点で（またはほぼ同じ時点で）、候補画像の記述子を取得することができる。いずれの場合も、類似度比較ユニット２６０は、クエリー画像２１０と候補画像の記述子を比較したならば、クエリー画像２１０に最も良くマッチするかまたは類似している候補画像を取得することができる。
【００１７】
類似度比較ユニット２６０が、クエリー画像２１０の画像記述子と、ＤＢ１６０に保存されている画像記述子の全てのまたはいくつかを比較した後で、類似度比較ユニット２６０はクエリー画像２１０に最も良く類似している少なくとも１個の画像（すなわちマッチング画像２７０）をＤＢ１６０から取得し、取得した画像または画像群をディスプレイ１８０に出力する。一例として、類似度比較ユニット２６０は、入力クエリー画像２１０の記述子と候補画像の記述子との距離を判定して、距離が最短であるマッチング画像２７０を決定することができる。類似度比較ユニット２６０は入力クエリー画像２１０を、入力画像２１０を記載する記述子と共にＤＢ１６０に格納することができる。類似度比較ユニット２６０は、マッチング画像をディスプレイ１８０へ配信する。
【００１８】
いくつかの実施形態において、記述子生成ユニット２８０は最初に、直接接続または通信プロトコルを含む各種の方法により、画像入力ユニット１２０からクエリー画像２１０を受信することができる。記述子生成ユニット２８０内のＤＴユニット２２０は次いで、クエリー画像２１０を中間画像に変換して、原クエリー画像２１０に対し、その１個以上の境界または等高線から直接抽出されたものに加えて、より多くのパラメータまたは特徴を提供することができる。例えば、記述子生成ユニット２８０は、クエリー画像２１０を２値画像に変換する。ＤＴユニット２１０は、２値画像をグレースケールの中間画像に変換することができる。換言すれば、ＤＴユニット２１０は、２値画像の等高線からの距離に応じて段階的に変化する境界を有するように、原クエリー画像２１０を変換する。ＤＴユニット２２０は入力クエリー画像２１０を、画素の位置に応じて（または外部境界または等高線からの画素の距離に基づいて）グレー画素値（純白から純黒まで）を有する中間画像に変換することができる。ＤＴユニット２２０はこのような方法で、クエリー画像２１０のパラメータや特徴に追加的なパラメータまたは特徴を提供して、例えばグレースケール画像のような中間画像を生成することができる。説明の便宜上、中間画像をグレースケール画像として記述しているが、中間画像は、クエリー画像２１０に特徴が追加された任意の変換済み画像、例えば段階的に変化する境界を有する画像、カラー付加画像、および輝度付加画像等を含んでいてよく、そのような特徴（例えば、グレースケール、色、輝度等）が画像内の画素の位置に応じて変化するものであればよい。例えば、画像の境界からの距離に応じて様々な色の陰影、明度、または強度を各々の画素値に割り当てることができる。
【００１９】
一旦中間画像が上記の通りに生成されたならば、ＡＲＴユニット２４０へ配信され、そこで中間画像に対してアルゴリズムを実行することにより、中間画像のＡＲＴ記述子が生成される。そのようなＡＲＴ記述子を、クエリー画像２１０を記述するＧＡＲＴ（グレーレベル偏角動径変換）記述子と呼ぶ場合がある。ＧＡＲＴ記述子および原クエリー画像２１０は類似度比較ユニット２６０へ転送される。類似度比較ユニット２６０は、クエリー画像２１０のＧＡＲＴ記述子をＤＢ１６０に保存されている候補画像の記述子と比較する。類似度比較ユニット２６０は従って、ＤＢ１６０に保存されていて、クエリー画像２１０に最も良くマッチする（または最も近い）１個以上の候補画像を決定することができる。例えば、類似度比較ユニット２６０は、クエリー画像２１０の記述子と候補画像の記述子との距離を判定して差異の距離が最も短いマッチング画像２７０を決定することができる。類似度比較ユニット２６０は、直接接続またはコントローラ１１０によりプログラムまたは構成されたような通信プロトコルを含む各種の方法により、マッチング画像２７０（すなわち、クエリー画像２１０に最も良く類似しているかまたは比較的近いと判定された１個以上の候補画像）をディスプレイ１８０へ配信する。
【００２０】
ディスプレイ１８０が画像マッチングユニット１４０とは別個の遠隔装置に設置されている特定の実施形態において、マッチング画像またはいくつかの最適候補画像は、有線または無線通信プロトコルを介してディスプレイ１８０へ送信することができる。別の実施形態において、画像入力ユニット１２０およびディスプレイ１８０は、携帯電話、ＰＤＡ、無線端末等、通信機能を有する単一の装置に実装されていてよい。
【００２１】
図３を参照して、ＤＴユニット２２０が用いる距離変換（ＤＴ）の概念またはアプリケーションを示す。図３は、入力クエリー画像２１０の２値画像（左側）、およびＤＴアプリケーション実行後の中間画像（右側）を示す。図３に示すように、クエリー画像２１０は、クエリー画像２１０内の形状の境界画素が画素値「０」により示され、他の画素は画素値「１」で示される、２値形式で表すことができる。特定の実施形態において、ＤＴユニット２２０は、２値クエリー画像２１０内の各画素が２値画像の境界と当該画素の距離に対応する値を有するように、クエリー画像２１０の２値形式をグレーレベル画像（すなわち中間画像）に変換することができる。ＤＴユニット２２０は、図３の右側に示すようなグレースケール画像を出力することができる。グレースケール画像の画素値は、形状の中央に最も近く位置する画素が最大の画素値（この場合は「３」）を有するように、画像内の形状の境界からの距離に対応する。このように、原２値クエリー画像を、境界からの距離に応じて画素値が変更されたグレースケール画像に変換することができる。
【００２２】
図４に、距離変換（ＤＴ）を適用して２値画像を中間画像（例えば、グレースケール画像）に変換する様子を描いた別の例を示す。左側に示す２値画像において、画像の境界に沿った画素が第１の画素値「Ａ」を有し、残りの画素は第２の画素値「Ｂ」を有する。ＤＴユニット２２０は、境界と対応画素の各位置の距離に応じて、各々の画素値を変換することができるため、ＤＴの後の中間画像（右側）において、境界に直接隣接する画素は第１の画素値「Ａ」を有し、境界に直接隣接しない残りの画素は他の様々な画素値を有する。例えば、２値画像は画素の位置に応じて変化する画素値を有するように中間画像に変換されることにより、ＤＴ適用画像の画素のうち境界に斜めに隣接する（頂点だけが境界に隣接する）画素が第２の値「Ｂ」、値「Ａ」を有する画素に直接隣接する画素位置において第３の画素値「Ｃ」、および値「Ｃ」を有する画素に直接隣接する画素位置において第４の画素値「Ｄ」を有するようにできる。ＤＴ適用画像（中間画像）はこのように、「Ａ」〜「Ｄ」の範囲にある追加的な画素値を有することができ、これら様々な画素値は、画像の幾何学的成分、例えば画素のアンギュラーおよびラディアル成分の解像度を高めて、画像をより正確に記述するように、画素の位置を示すことができる。
【００２３】
図５を参照するに、ＤＴを適用した結果を本開示の一実施形態に従い示す。図５に、２値クエリー画像の各々の形状に対してＤＴを適用する前（左側）および後（右側）の形状を有する画像を示す。図５に示すように、ＤＴ適用画像（右側に示す中間画像）は、画像内の形状の境界の滑らかな階調を有しており、クエリー画像に追加的な幾何学的成分を与えることができる。中間画像はこのように、クエリー画像その他各種のものより広範な画素値を有していてよい。そのように広範な画素値は、クエリー画像をより正確に記述するための追加的なパラメータまたは属性を与えることができる。従って、ＤＴ適用画像は、各画素値においてパラメータまたは属性に追加的なレベルを有することができ、それにより、ＤＴ適用画像から得られたＡＲＴ記述子が、原画像をより正確に記述することができる。いくつかの実施形態において、左側の画像の形状が白黒で表現されており、画像の画素から抽出可能な情報によって、白と黒の間の色変化に基づいて、形状の境界がどこに存在するかを示すことができる。図５の右側のＤＴ適用画像から、画像の境界に階調付けする（the boundaries of the image are graded）ことにより、等高線、中間軸、骨格等、画像に関する追加的な情報が与えられる。例えば、画素の位置がクエリー画像の境界から遠いほどＤＴ適用画像はより大きい画素値を有するため、値が最も大きい画素は画像の中間軸に一致することができる。記述子生成ユニット２８０はこのように、画像をより正確に特徴付けることができるため、画像検索システム１００は、より正確な記述子を用いて、より正確に画像を取得することができる。
【００２４】
特定の実施形態において、ＡＲＴユニット２４０は、ＤＴ適用画像のＡＲＴ記述子を生成するアルゴリズムを実行することにより、クエリー画像２１０のＧＡＲＴ記述子を取得する。例えば、ＡＲＴユニット２４０は、極座標（ρ、θ）を用いてグレースケール画像をｆ（ρ、θ）で表すことができる。ＡＲＴ基底関数Ｖｎｍ（ρ、θ）を用いることにより、次式で定義される極座標系においてグレースケール画像の特徴係数Ｆｎｍを表すことができる。
【数１】
2010531010.tif 000003
ここに、ＡＲＴ基底関数Ｖｎｍ（ρ、θ）は以下により計算できる。
Ｖｎｍ（ρ、θ）＝Ａｍ（θ）Ｒｎ（ρ）
また、ＡＲＴ基底関数Ｖｎｍ（ρ、θ）の各要素は次式により計算または定義される。
【数２】
2010531010.tif 000004
ここに、ｎは角度成分の１レベルを示し、ｍは径成分の１レベルを示す。
例えば、ｎ＝０，１，２、且つｍ＝０，１，．．．，１１の場合、図６に示すように合計３６個の基底関数を生成することができる。基底関数を用いて、ｍおよびｎ（ｎ＝０，１，２；ｍ＝０，１，．．．，１１）に対して上記の方程式（１）で得られた特徴係数の振幅ａｉが集計されて、以下のようにｊ番目の画像のＧＡＲＴ記述子を形成する。
【数３】
2010531010.tif 000005
ここに、ｊはｊ番目の画像を示す記述子インデックスである。ＡＲＴ演算を記述するために３６個の基底関数を用いているが、特定の数に限定されることなく異なる個数の基底関数を用いてもよいことは当業者には明らかであろう。
【００２５】
再び図２を参照するに、ＡＲＴユニット２４０は、クエリー画像２１０のＧＡＲＴ記述子を類似度比較ユニット２６０へ配信する。特定の実施形態において、類似度比較ユニット２６０は、クエリー画像と候補画像の「距離」を測定することにより、クエリー画像を候補画像と比較することができる。距離を測定するために、類似度比較ユニット２６０は画像のＧＡＲＴ記述子を用いて実際に距離を計算する。例えば、クエリー画像と１個の候補画像の、各々ベクトル形式
【数４】
2010531010.tif 000006
および
【数５】
2010531010.tif 000007
で表すことができる２個のＧＡＲＴ記述子について、次式で与えるように、同じインデックス（ｍ，ｎ））を有する係数同士の差の合計を用いて距離を計算することができる。
【数６】
2010531010.tif 000008
類似度比較ユニット２６０は、クエリー画像からの距離（例えば、距離ベクトルの長さ）が最も短い候補画像をマッチング画像として選択してよい。あるいは、類似度比較ユニット２６０は、閾値距離より短い距離を有する候補画像を選択して、選択された画像の全てまたは一部をマッチング画像として決定することができる。類似度比較ユニット２６０は、どのマッチング画画像もユーザが見ることができるようにディスプレイ２７０へ送信することができる。
【００２６】
図７および図１を参照して、本開示の一実施形態に従い画像のＧＡＲＴ記述子を生成する方法を示す。ステップ７１０において、ユーザは最初に、画像入力ユニット１２０を用いて画像検索システム１００に画像を入力することができる。ユーザは、キーパッド、キーボード、マウス等、各種の入力ユニットを用いて画像検索システム１００に所望の画像を入力することができる。オプションとして、ユーザは所望の画像をリモート・システムへ送信して、リモート・システムのデータベースに格納されている１個以上の画像を取得することができる。そのような場合、所望の画像を携帯電話、ＰＤＡ等の携帯機器に入力し、次いで無線または有線の通信プロトコルを用いて画像検索システム２００へ送信することができる。
【００２７】
画像入力ユニット１２０は、クエリー画像２１０を画像マッチングユニット１４０へ送信することができる。ステップ７２０において、ＤＴユニット２２０（画像マッチングユニット１４０内に実装されていてよい）は、クエリー画像２１０に対して距離変換（ＤＴ）を実行して中間画像を作成することができる。例えば、クエリー画像が２値画像である場合、ＤＴユニット２１０は２値画像をグレースケール画像に変換することができる。ＤＴユニット２２０は、ハードウェア実装、ソフトウェア実装またはこれらの組合せを用いて、ＤＴを実行する任意の適当な方法を採用することができる。ステップ７３０において、ＡＲＴユニット２４０はＤＴ適用画像を受信して、ＤＴ適用画像（例えば、グレースケール画像）に対して、ＡＲＴ記述子生成アルゴリズムを実行する。
【００２８】
ステップ７４０において、ＡＲＴユニット２４０は、ＤＴ適用画像のＡＲＴ記述子を取得することにより、クエリー画像のＧＡＲＴ記述子を取得することができる。特定の実施形態において、ＡＲＴユニット２４０は極座標系を用いてＤＴ適用画像を表すことができる。ＡＲＴユニット２４０は、ＤＴ適用画像の極座標表現に対して数値的演算を実行することができる。例えば、ＡＲＴユニット２４０は、ＤＴ適用画像の極座標表現に基底関数の１個を乗算して、乗算された関数を取得し、次いで乗算された関数を積分して、上記の方程式（１）で与えるように、ＧＡＲＴ係数の１個を計算することができる。異なる基底関数の各々についてそのような演算を実行して、１個以上のＧＡＲＴ係数を取得する。演算７５０において、ＡＲＴユニット２４０は、係数に基づいてクエリー画像２１０の記述子を決定する。換言すれば、ＡＲＴユニット２４０は、上記の方程式（２）で与えるように、ＧＡＲＴ係数を集めて、クエリー画像２１０のＧＡＲＴ記述子のベクトル形式を得ることができる。
【００２９】
図８を参照して、本開示の一実施形態に従いＧＡＲＴ記述子を用いて画像を取得する方法を示す。最初に、ステップ８１０において、ユーザは画像検索システム１００の画像入力ユニット１２０にクエリー画像２１０を入力することができる。画像入力ユニット１２０は、例えば直接接続または通信プロトコルを含む各種の手段を介して画像マッチングユニット１４０へ、クエリー画像を送信する。ステップ８２０において、画像マッチングユニット１４０内の記述子生成ユニット２８０が、クエリー画像２１０の記述子を決定する。ＤＴユニット２２０は、クエリー画像２１０のＤＴ変換を実行して中間画像を生成する。例えば、クエリー画像が２値画像である場合、ＤＴユニット２１０は２値画像をグレースケール画像（例えば、図５に示すように）に変換することができる。ＡＲＴユニット２４０は、グレースケール画像に対してＡＲＴ記述子生成アルゴリズムを実行して、クエリー画像２１０のＧＡＲＴ記述子を生成する。
【００３０】
ステップ８３０において、類似度比較ユニット２６０は次いで、クエリー画像２１０のＧＡＲＴ記述子を、ＤＢ１６０に格納されている候補画像の記述子と比較することができる。そのような動作は、クエリー画像２１０のＧＡＲＴ記述子と候補画像のＧＡＲＴ記述子との距離を測定することにより実現することができる。例えば、類似度比較ユニット２６０は、この距離を測定するために、上記の方程式（３）で表されているように、２個のＧＡＲＴ記述子のベクトル表現間のユークリッド距離を計算する。この処理は、類似度比較ユニット２６０が候補画像の中で最も近いマッチング（すなわち十分に距離が短い画像）を見つけるまで続けることができる。ステップ８４０において、ユーザは次いで動作８３０で得られた結果に基づいて最も近いマッチング画像２７０を取得することができる。この画像は画像検索システム１００のディスプレイ１８０へ配信され、これによりユーザは画像２７０を視覚的に識別して、更なる次のアクションを行なうことができる。
【００３１】
特定の実施形態において、ディスプレイ１８０は携帯機器（例えば、携帯電話またはＰＤＡ）に実装されていてよい。そのような実施形態では、画像マッチングユニット１４０は、BlueTooth、ZigBee、ＧＳＭ、ＣＤＭＡ等の通信プロトコルを介して、マッチング画像２７０をパソコン、ラップトップ・コンピュータまたは携帯電話等の携帯機器へ送信することができる。ＧＡＲＴ記述子のデータベース検索性能を評価すべく、現在ＭＰＥＧ−７で採用されているデータベースを用いて、データベース検索テストが行なわれた。使用されたデータベースは、８個の上位カテゴリおよび１０２個の下位または「末端」カテゴリを含む４層の階層構造に分類された１，３００個の画像を含んでいる。性能評価尺度としてＭＰＥＧ−７で採用されている的中率（Bull's Eye Performance）（ＢＥＰ）が適用された。ＢＥＰスコアが高いほど性能がより優れていることを意味する。
【００３２】
図９は、２６個の画像について、一実施形態におけるＧＡＲＴ記述子と従来のＡＲＴ記述子との検索性能を比較している。図８から明らかなように、ＢＥＰにより測定されたＧＡＲＴ記述子の性能が、従来のＡＲＴ記述子よりも（この特定の例では類似度が約３％）優れている。
【００３３】
本開示を通じて、本明細書に記載されているシステム、装置、および方法が、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、またはこれらを組合せて実装可能であって、システム、サブシステム、構成要素、またはこれらの下位要素において利用できることが当業者には理解されよう。例えば、ソフトウェアで実装された方法には、本方法の動作を実行するコンピュータコードが含まれていてよい。このコンピュータコードは、プロセッサ可読媒体またはコンピュータプログラム製品等の機械可読の媒体に保存されていても、あるいは搬送波に乗せられたコンピュータ・データ信号またはキャリアにより変調された信号として伝送媒体または通信リンクを介して送信されてもよい。機械可読媒体またはプロセッサ可読媒体は、機械（例えば、プロセッサ、コンピュータ等）により、読み込み可能且つ実行可能な形式で情報を格納または転送可能な任意の媒体を含んでいてよい。
【００３４】
本開示は、その基本的特徴または必須特徴から逸脱することなく、他の特定の形式で実施されていてよい。従って、図示された実施形態は、あらゆる点においてあくまでも例示目的のものであって、限定的なものではないと理解されたい。本開示の範囲は従って、上記の説明ではなく添付された特許請求の範囲により規定される。特許請求の範囲の意味および同等な範囲内でのあらゆる変更がこれらの範囲に含まれる。
【図１】
2010531010.tif 000009
【図２】
2010531010.tif 000010
【図３】
2010531010.tif 000011
【図４】
2010531010.tif 000012
【図６】
2010531010.tif 000013
【図７】
2010531010.tif 000014
【図８】
2010531010.tif 000015
【図９】
2010531010.tif 000016
【図５】
2010531010.tif 000017
【手続補正書】
【提出日】平成21年1月28日(2009.1.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力として画像を受信すべく構成されている画像入力ユニットと、
前記画像を中間画像に変換して前記画像の記述子を生成すべく構成されている記述子決定ユニットと、
前記画像の記述子を１個以上の候補画像の記述子と比較することにより、前記画像を前記１個以上の候補画像と比較すべく構成されている画像比較ユニットと、
前記画像に類似している前記１個以上の候補画像の少なくとも１個を、それらの記述子の比較に基づいて取得すべく構成されている検索ユニットと、を含む画像検索システム。
【請求項２】
前記記述子決定ユニットが、第１の変換ユニットおよび第２の変換ユニットを含んでいる、請求項１に記載の画像検索システム。
【請求項３】
前記入力画像に類似している前記１個以上の候補画像の少なくとも１個を表示すべく構成されているディスプレイをさらに含んでいる、請求項１に記載の画像検索システム。
【請求項４】
前記１個以上の候補画像を格納するデータベースをさらに含んでいる、請求項１に記載の画像検索システム。
【請求項５】
前記画像比較ユニットが、前記画像の記述子と前記候補画像の記述子との距離を測定して前記画像を前記１個以上の候補画像と比較すべく構成されている、請求項１に記載の画像検索システム。
【請求項６】
前記検索ユニットが、前記画像との距離が最短である前記１個以上の候補画像の少なくとも１個を取得すべく構成されている、請求項５に記載の画像検索システム。
【請求項７】
前記第１の変換ユニットが前記画像に対して距離変換（ＤＴ）を実行する、請求項２に記載の画像検索システム。
【請求項８】
前記第１の変換ユニットが前記画像の追加的な特徴を生成すべく構成されている、請求項７に記載の画像検索システム。
【請求項９】
前記画像の追加的な特徴が、前記画像の等高線、中間軸、および形状の骨格のうち少なくとも１個を含んでいる、請求項８に記載の画像検索システム。
【請求項１０】
前記第２の変換ユニットが、前記第１の変換ユニットにより処理された前記画像に対してアンギュラー・ラディアル・トランスフォーム（ＡＲＴ）を実行すべく構成されている、請求項２に記載の画像検索システム。
【請求項１１】
画像に関連付けられた記述子を生成する装置であって、
画像を入力すべく構成されている入力ユニットと、
前記画像を中間画像に変換すべく構成されている第１の変換ユニットと、
前記中間画像に作用して前記画像の記述子を生成すべく構成されている第２の変換ユニットと、を含む装置。
【請求項１２】
前記中間画像がグレースケール画像である、請求項１１に記載の装置。
【請求項１３】
前記第１の変換ユニットが前記画像に対して距離変換（ＤＴ）を実行すべく構成されている、請求項１１に記載の装置。
【請求項１４】
前記第１の変換ユニットが前記画像の追加的な特徴を生成すべく構成されている、請求項１３に記載の装置。
【請求項１５】
前記画像の追加的な特徴が、前記画像の等高線、中間軸、および形状の骨格のうち少なくとも１個を含んでいる、請求項１４に記載の装置。
【請求項１６】
前記第２の変換ユニットが、前記第１の変換ユニットにより処理された画像に対してアンギュラー・ラディアル・トランスフォーム（ＡＲＴ）を実行すべく構成されている、請求項１１に記載の装置。
【請求項１７】
前記第２の変換ユニットが、前記中間画像の特徴を表す１個以上の係数に前記中間画像を変換すべく構成されている、請求項１１に記載の装置。
【請求項１８】
前記第２の変換ユニットが、前記１個以上の係数を集めて前記画像の記述子を生成すべく構成されている、請求項１７に記載の装置。
【請求項１９】
前記装置が携帯機器である、請求項１１に記載の装置。
【請求項２０】
画像を中間画像に変換すべく構成されている変換ユニットと、
前記中間画像から前記画像の記述子を生成すべく構成されている記述子生成ユニットと、
前記画像の記述子を１個以上の候補画像の記述子と比較すべく構成されているマッチングユニットと、を含む画像マッチング装置。
【請求項２１】
前記１個以上の候補画像を格納すべく構成されている記憶装置をさらに含んでいる、請求項２０に記載の画像マッチング装置。
【請求項２２】
前記マッチングユニットが、前記画像の記述子と前記１個以上の候補画像の記述子との距離を測定すべくさらに構成されている、請求項２０に記載の画像マッチング装置。
【請求項２３】
前記変換ユニットが前記画像に対して距離変換（ＤＴ）を実行して中間画像を生成すべく構成されている、請求項２０に記載の装置。
【請求項２４】
前記記述子生成ユニットが、前記変換ユニットにより処理された画像に対してアンギュラー・ラディアル・トランスフォーム（ＡＲＴ）を実行すべく構成されている、請求項２０に記載の装置。
【請求項２５】
画像の記述子を生成する方法であって、
入力として画像を受信するステップと、
前記画像を中間画像に変換するステップと、
前記中間画像に基づいて前記画像の記述子を生成するステップと、を含む方法。
【請求項２６】
前記画像を変換するステップが、前記画像に対して距離変換（ＤＴ）を実行するステップを含んでいる、請求項２５に記載の方法。
【請求項２７】
前記記述子を生成するステップが、アンギュラー・ラディアル・トランスフォーム（ＡＲＴ）を実行するステップを含んでいる、請求項２５に記載の方法。
【請求項２８】
画像を中間画像に変換するステップと、
前記中間画像の特徴に基づいて前記画像の記述子を生成するステップと、
前記画像の記述子を候補画像の記述子と比較することにより、前記画像を１個以上の前記候補画像と比較するステップと、
前記記述子の比較に基づいて、前記画像に類似している前記１個以上の候補画像の少なくとも１個を取得するステップと、を含む、画像検索方法。
【請求項２９】
前記画像を比較するステップが、前記画像の記述子と前記候補画像の記述子との距離を測定して前記画像を前記１個以上の候補画像と比較するステップを含んでいる、請求項２８に記載の画像検索方法。
【請求項３０】
１個以上の候補画像を取得するステップが、前記画像との距離が最短である前記候補画像の少なくとも１個を取得するステップを含んでいる、請求項２９に記載の画像検索方法。
【請求項３１】
コンピュータにより実行されたときに、画像の記述子を生成する方法を前記コンピュータに実行させる命令を格納しているコンピュータ可読媒体であって、前記方法が、
画像を中間画像に変換するステップと、
前記中間画像に基づいて前記画像の記述子を生成するステップと、を含んでいる、コンピュータ可読媒体。
【請求項３２】
コンピュータにより実行されたときに、画像を取得する方法を前記コンピュータに実行させる命令を格納しているコンピュータ可読媒体であって、前記方法が、
画像を中間画像に変換するステップと、
前記中間画像の特徴に基づいて前記画像の記述子を生成するステップと、
前記画像の記述子を候補画像の記述子と比較することにより、前記画像を複数の前記候補画像と比較するステップと、
前記記述子の比較に基づいて前記画像に類似している１個以上の候補画像を取得するステップと、を含んでいる、コンピュータ可読媒体。
【請求項３３】
コンピュータにより実行されたときに、画像の記述子を生成する方法を前記コンピュータに実行させる命令を含むコンピュータプログラムであって、前記方法が、
入力画像を受信するステップと、
前記画像を中間画像に変換するステップと、
前記中間画像に基づいて前記画像の記述子を生成するステップと、を含むコンピュータプログラム。
【請求項３４】
コンピュータにより実行されたときに、画像を取得する方法を前記コンピュータに実行させる命令を含むコンピュータプログラムであって、前記方法が、
入力画像を中間画像に変換するステップと、
前記中間画像の特徴に基づいて前記画像の記述子を生成するステップと、
前記画像の記述子を候補画像の記述子と比較することにより、前記画像を複数の前記候補画像と比較するステップと、
前記記述子の比較に基づいて前記画像に類似している１個以上の候補画像を取得するステップと、を含んでいる、コンピュータプログラム。
【国際調査報告】
2010531010.tif 000018
2010531010.tif 000019
2010531010.tif 000020