(57)【要約】  本明細書においては、ユーザが、動画、印刷物、または、自身の回りの世界から単一の画像スナップショットを捕捉し、且つ、該スナップショットに表示されたメディア自体または関心対象物に関する付加的情報を獲得することを許容する方法およびシステムが記述される。該スナップショットのフィンガープリントは、クエリとして使用されると共にサーバに対して送信され、本明細書中に記述された画像特徴式認識法は、特徴インデックスを使用して、該フィンガープリントに基づき、画像の更に大規模なデータベースから小規模の一群の候補一致物を特定する。距離尺度および急進的なハッシュ・テーブル設計態様を用いる新規な方法およびシステムは、確率的効果を活用すると共に、冗長的な画像特徴と比較して固有的な画像特徴が選好されることを許容することで、更に固有的なデータ点のみがインデックス内に存在して留まることを許容することで、特定プロセスにおいて迅速に使用され得る効率的インデックスを生成する。
2017513150.tif 000002
【特許請求の範囲】
【請求項１】
モバイル機器を以てユーザにより獲得されたクエリ画像に関する付加的情報を特定してモバイル機器へと送信するサーバであって、該サーバは、
ひとつ以上の基準画像に対して関連付けられたひとつ以上の基準特徴記述子を記憶する基準画像データベースであって、少なくともひとつの基準画像特徴は複数の関数を用いて当該基準画像データベースにおける複数のアドレスに対してマッピングされる、基準画像データベースと、
プロセッサであって、
該モバイル機器から、ひとつ以上のクエリ画像特徴記述子を含む第１クエリを受信するクエリ受信モジュールと、
該ひとつ以上のクエリ画像特徴記述子の各々に対して該複数の関数を用いて複数のアドレスを算出し、且つ、該複数のアドレスの各々に対し、該基準画像データベースの所定領域内に記憶された重複的な基準画像特徴記述子の個数を算出するための候補特徴記述子読出しモジュールと、
該算出された重複的な基準画像特徴記述子の個数に基づいて一群の基準画像特徴記述子を選択するための候補画像読出しモジュールと、
該選択された一群の基準画像特徴記述子をひとつ以上のクエリ画像特徴記述子と比較して、いずれかの基準画像が該クエリ画像と一致するか否かを決定する画像マッチング・モジュールと、
を備えて成るひとつ以上のモジュールを実行するプロセッサと、
を備えて成り、
該サーバは更に、
一致基準画像が決定されたなら、該少なくともひとつの一致基準画像に対して関連付けられた付加的情報を注釈データベースから獲得する段階と、
該付加的情報を、該少なくともひとつの関心対象物に関する付加的情報として該ユーザに対して表示するために、該モバイル機器へと送信する段階と、
を実施するように構成される、
サーバ。
【請求項２】
該プロセッサは更に、ハッシュ・テーブル管理モジュールを実行すべく構成される、請求項１に記載のサーバ。
【請求項３】
該ハッシュ・テーブル管理モジュールは、ハッシュ衝突に対処する衝突解決モジュールと、ハッシュ・テーブルにおけるひとつのアドレスに対する(たとえば、一群の特徴記述子などの)新たなデータ点の関連付けを取扱うオーバーフロー対処モジュールと、を更に備えて成る、請求項２に記載のサーバ。
【請求項４】
モバイル機器を以てユーザにより獲得された第１クエリ画像に関する付加的情報を特定かつ表示するコンピュータ実行型の方法であって、
該第１クエリ画像に含まれた該ユーザに対する少なくともひとつの関心対象物に対応するひとつ以上のクエリ画像特徴記述子を含む第１クエリを、該モバイル機器から受信する段階と、
該第１クエリの受信に応じ、類似性検索であって、
該クエリ画像特徴記述子の各々に対し、複数の関数を用いて複数のアドレスを算出する段階と、
該複数のアドレスの各々に対し、データベースの一定領域内に記憶された重複的な基準画像特徴記述子の個数を算出する段階であって、少なくともひとつの基準画像特徴は、該複数の関数を用いて該基準画像データベースにおける複数のアドレスへとマッピングされている、という段階と、
該複数のアドレスの各々に対して関連付けられた該基準画像データベースの該一定領域における該重複的な基準画像特徴記述子の個数に基づいてひとつ以上の候補画像を決定する段階であって、該基準画像データベースはひとつ以上の基準画像特徴記述子を記憶しており、該基準画像特徴記述子の各々は少なくともひとつの基準画像に対して関連付けられている、段階と、
該ひとつ以上の候補画像に対する該特徴記述子を該クエリ画像特徴記述子と比較して、一致物が在るか否かを決定する段階と、
を備えて成るという類似性検索を実施する段階と、
一致物が在るなら、該一致物に対して関連付けられた付加的情報を獲得する段階と、
該一致物に対して関連付けられた付加的情報を、該ユーザに対する表示のために該モバイル機器へと送信する段階と、
を備えて成る、コンピュータ実行型の方法。
【請求項５】
ひとつのアドレスに対して関連付けられた所定領域内の該重複的な基準画像特徴記述子の個数は、該重複的な基準画像特徴記述子と、該アドレスに対してマッピングされた該第１クエリ画像特徴記述子との間の類似性の程度を反映し、且つ、
該ひとつ以上の候補画像を決定する段階は、
該重複的な基準画像特徴記述子の個数は所定スレッショルド値を超過したことを決定する段階と、
該重複的な基準画像特徴記述子に対して関連付けられた該ひとつ以上の候補画像を獲得する段階と、
を備えて成る、
請求項４に記載のコンピュータ実行型の方法。
【請求項６】
該モバイル機器から、ひとつ以上の第２クエリ画像特徴記述子を含む第２クエリを受信する段階と、
該ひとつ以上の第1クエリ画像特徴記述子を、該ひとつ以上の第２クエリ画像特徴記述子と比較する段階と、
該比較の結果に基づき、該類似性検索を実施しないと決定し、且つ、クエリ・キャッシュ内に記憶された該第１クエリと該ひとつ以上の候補画像との間のマッピングに基づき、該ひとつ以上の候補画像を獲得する、段階と、
を更に備えて成る、請求項５に記載のコンピュータ実行型の方法。
【請求項７】
各基準画像特徴記述子は、各バケットがひとつのアドレスに対して関連付けられたという複数のバケットを含むハッシュ・テーブルに基づいてデータベース内に記憶され、
該ハッシュ・テーブルは、一群のハッシュ関数に対して関連付けられ、該一群のハッシュ関数は、ひとつの特徴記述子データ点を、該複数のバケットの内の第１群のバケットに対して関連付けられた第１群のアドレスへとマッピングし、且つ、該第１群のバケットの各々は、ひとつの第２特徴記述子データ点を記憶する、
請求項４に記載の方法。
【請求項８】
モバイル機器を以てユーザにより獲得された画像に関する付加的情報を特定かつ表示するコンピュータ実行型の方法であって、
該モバイル機器を用いて、ユーザがその付加的情報を受信することを望む少なくともひとつの関心対象物を備えて成る少なくともひとつの画像を獲得する段階と、
該少なくともひとつの画像から、該少なくともひとつの関心対象物に対応するひとつ以上の第１特徴を抽出する段階と、
該ひとつ以上の第１特徴を表す第１フィンガープリントを生成する段階と、
該第１フィンガープリントを含む第１クエリをサーバに対して送信する段階であって、該フィンガープリントによれば、該サーバは、ひとつ以上の第２画像を獲得すること、および、該第１クエリに基づいて選択されたひとつ以上の第２画像に基づき、該サーバが、ユーザに対する該少なくともひとつの関心対象物に関する付加的情報を有すると決定することが許容される、段階と、
該サーバから、該ユーザに対する該少なくともひとつの関心対象物に関する該付加的情報を受信し、且つ、該付加的情報を該ユーザに対して表示する段階と、
を備えて成る、コンピュータ実行型の方法。
【請求項９】
該コンピュータ実行型の方法は、該モバイル機器における第１インタフェースを介して、該第１画像の一部に対するユーザの選択を受信する段階を更に備えて成り、
該少なくともひとつの画像からひとつ以上の第１特徴を抽出する該段階は、該選択された部分に対応するひとつ以上の第１特徴を抽出する段階を備えて成り、且つ、
第１フィンガープリントを生成する該段階は、該第１画像の該選択された部分から抽出された該ひとつ以上の第１特徴を表す第１フィンガープリントを生成する段階を備えて成る、
請求項８に記載のコンピュータ実行型の方法。
【請求項１０】
関心対象物に関する付加的情報を特定かつ表示するデバイスであって、該デバイスは、
該関心対象物に含まれた画像を獲得する画像獲得モジュールと、
該画像に対して関連付けられた一種類以上の画像特徴量を抽出する特徴記述子生成モジュールと、
該抽出された一種類以上の画像特徴量に基づいてクエリ・フィンガープリントを生成し、且つ、該クエリ・フィンガープリントをサーバに対して送信するフィンガープリント生成モジュールであって、該クエリ・フィンガープリントによれば、該サーバは、該クエリ・フィンガープリントに基づき、ひとつ以上の基準特徴記述子を記憶するデータベースにおいて類似性検索を実施すること、および、該類似性検索の結果に基づき、該ひとつ以上の基準特徴記述子の少なくともひとつに対して関連付けられたひとつ以上の候補画像を獲得することが許容される、フィンガープリント生成モジュールと、
該画像が、該ひとつ以上の候補画像と一致するか否かを決定する画像マッチング・モジュールと、
該画像マッチング・モジュールにおける該決定に基づき、該ひとつ以上の候補画像の少なくともひとつに対して関連付けられた付加的情報を獲得し、該少なくともひとつの関心対象物に関する付加的情報として該ユーザに対して表示する付加的データベース・モジュールと、
を含むひとつ以上のモジュールを実行するプロセッサを備えて成る、デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願は、2014年2月14日に出願された米国仮特許出願第61/937,859号の優先権を主張するものであり、その内容は言及したことにより全体が本出願中に援用される。
本開示内容は、視覚的物体認識法に関し、更に詳細には、デジタル画像における内容および物体を認識するための方法およびシステム、および、認識された内容／物体に関する付加的な内容および／または情報を迅速に供給する方法およびシステムに関する。本明細書中に開示される方法およびシステムは、検索サービス、および、内容に基づく画像の検索および認識プロセスに対しても適用可能であり得る。
【背景技術】
【０００２】
今日の世界においては、殆ど誰もが、カメラ使用可能なモバイル機器を常に備えている。モバイル機器のユーザは、自身のモバイル機器を使用して自身の回りの世界に関する付加的な情報を獲得すべく該モバイル機器を使用し得ることに慣れてきた。モバイル機器のユーザは今日、インターネットを使用することで、購入の前に、付加的情報を獲得し、価格を調査し、製品を視認し、且つ、対象物またはコンテンツを購入さえしている。ユーザは今日、斯かるアクセスを、可及的に少ない手順にて、可及的に迅速かつ効率的に行うことを望んでいる。
【０００３】
たとえば、看板、ポスターの如き印刷物、もしくは、動画において見られるもの、または、映画の如きスクリーン、TVショー、ウェブ・サイト、または、他のデジタル・コンテンツにて見られるものなどの、我々の回りの世界における物体もしくはシーンを見ることにより、更なる情報に対する要望が誘発され得る。
【０００４】
ユーザのモバイル機器に対する対象物もしくはコンテンツに関する付加的情報の供給を促進する既存の技術が在る。たとえば、１次元的なバーコードまたは２次元的なQRコードの如きマーカは、製品に対して物理的に取付けられ得るか、または、印刷されたページ、ポスター、または、看板上にて、製品の画像に隣接して印刷され得る。幾つかの場合、画像に対しては、人工的に作成されたパターンが付加され得る。上記コードもしくは人工的に作成されたパターンを、専用の走査デバイスにより、または、ユーザのモバイル機器におけるカメラ機能およびアプリケーションを用いて走査することにより、ユーザに対しては更なる情報が供給され得る。上記付加的情報は、上記マーカ内に直接的にコード化され得るか、または、マーカ内にコード化された情報は、データベースから付加的情報を読出すべく使用され得る。
【０００５】
技術的に更に洗練されているのは、人工的なマーカの挿入なしでの画像の認識である、と言うのも、全ての物体が、斯かるマーカは有することは無く、または、有し得ないからである。これらの場合に対しては、物体認識アルゴリズムおよびパターン・マッチングの組み合わせを用いて画像を認識する技術が開発されてきた。たとえば、非特許文献１に記述された如きViola-Jones法は、画像における一定の形状の存在の可能性を評価するために一連の所定のスキャン操作と、AdaBoostの如き分類アルゴリズムとを実施して、物体を特定する。ランダムなピクセル・アクセス・データ構造として“一体的画像”を用い、Viola-Jones法は、更に大規模な汎用集合から少ない個数の重要な視覚的特徴を選択し、分類器の部分集合を生成してから、更に複雑な分類器を順次的に“カスケード”に組み合わせることで(AdaBoost)、バックグラウンド領域が廃棄されることと、有望な物体状の領域に関する更なる演算が実施されることとを許容する。分類方法は典型的に、２つの段階、すなわち、訓練段階、および、訓練データが物体の特定のために使用され得るという試験段階を有している。分類方法は、演算的に集約的であると共に、訓練画像の慎重な事前選択に依存している。これらの形式の物体認識方法は典型的に、顔面、交通標識、ブランド・ロゴなどの如き、同一の形状および特性を備えた物体の検出において使用される。
【０００６】
他の手法は、画像に基づく検出および認識のために、画像内に存在する固有の属性または特徴を利用する。これらのシステムにおいては、一群の訓練画像から特性が抽出されてから、該システムは、一群のスナップショット間に、または、スナップショットと訓練用の一群の画像との間に、対応する特性が在るか否かを検出する。画像に基づく検出および認識の用途は、全景画像統合(panorama and image stitching)、不連続3D再構成、仮想現実(たとえば、Microsoft(登録商標)Photosynth(登録商標)、VisualSFM(登録商標)、Qualcomm(登録商標)、Vuforia(登録商標))から、Google(登録商標)、Googles(登録商標)およびKooaba(登録商標)／Vuforia(登録商標)クラウド認識により提供される画像検索および認識サービスにまで及んでいる。これらの画像系認識技術は、物体を認識するためにのみ使用され、その画像内に置かれた特別の情報は抽出しない。更に、既存の技術は典型的に、(画像自体または動画、および／または、オーディオ・データの如き)データ密度が高いメディアファイルを、(たとえばスマートフォンなどの)捕捉デバイスから、ネットワークを介して処理サーバまで送信することを必要とし、物体の認識が更に遅延される。既存の方法はまた、物体に対して関連付けられた付加的情報の全てがサーバからモバイル機器まで戻し送信されることを必要とするので、時間を取ると共に、サーバに対するネットワーク接続が無い状況では使用され得ない。
【０００７】
動画から一定の特徴を抽出し、且つ、内容の特定のために使用されるべく内容特定サーバに対して送信する“フィンガープリント”を生成する幾つかの方法およびシステムが在る。たとえば、特許文献１は、捕捉された内容からVDNA(動画DNA)フィンガープリントを抽出する。しかし、特許文献１は特に、付随する音声からを含め、(一連の画像を捕捉している)動画からのフィンガープリントの抽出に関している。
【０００８】
メディア・コンテンツの自動認識のための幾つかの方法およびシステムを提供する幾つかの試みも在るが、今日まで、全てが不十分であった。静止的なメディアに対して作用する一切の既存の方法およびシステムは、動画と共に使用するには、容易には良好に適合しない。VDNAフィンガープリントを生成するシステムは、演算的に集約的であると共に、ネットワークを介して迅速に送信することが困難である大きなメディアファイルを使用する。更に、VDNAフィンガープリントを使用する一切のシステムは、使用中のスパイクが問題とならざるを得ない、と言うのも、ネットワークを介しての同時的な複数回のアクセスによれば、帯域幅の問題が更に悪化するからである。動画メディア、および、その中における物体の認識を試みるシステムは、関心対象物を含む良好な使用可能画像を捕捉するという課題を解決すべきである。斯かるシステムはまた、ユーザの興味を引き得るシーンが表示された時点と、ユーザが捕捉を開始する時点との間において必然的に生ずる時間遅延も考慮すべきである。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許第8,793,274号明細書
【非特許文献】
【００１０】
【非特許文献１】ポール・ビオラ(Paul Viola)およびマイケル・ジョーンズ(Michael Jones)による“強化学習された一連の単純な特徴を用いる高速の物体検出法(The Rapid Object Detection Using a Boosted Cascade of Simple Features)
【発明の概要】
【００１１】
故に、物体または内容を検出もしくは認識するために(一連の画像を音声データと共に使用することを必要とするVDNA型のフィンガープリント生成の代わりに、単一の画像の如き)最小限の量のメディア・データのみを必要とし、且つ、ネットワークを介したメディア・データの送信を必要としない、というシステムおよび方法に対する要望が在る。更に、複数の動画フレームからの大容量の訓練データを取扱うことで、複数の動画フレームを訓練集合として使用する画像認識に典型的に付随する制限を克服すべく拡張可能であるというシステムに対する要望も在る。斯かる制限としては、膨大な量の単一画像もしくは動画フレームを分類画像認識領域と比較すること、および、複数の動画フレームから生成された訓練データ集合の膨大な冗長性が挙げられる。更に、特に画像認識が動画に対して実施されるとき、迅速化と認識プロセスの精度の向上とに対する要望も在る。最後に、冗長なクエリを除去することでクエリにおけるスパイクに対処し、貴重なネットワークおよび演算の資源を確保することに対する要望も在る。
【図面の簡単な説明】
【００１２】
取入れられて本開示内容の一部を構成する添付図面は、幾つかの実施形態を例示すると共に、記述内容と協働して、開示された原理を説明する役割を果たす。
【００１３】
【図１Ａ】図１Ａは、表示されたデジタル・コンテンツにおける関心対象物に関する付加的情報をユーザに対して提供するという、本開示内容の実施形態に係る代表的なシステムを示す概略図である。
【図１Ｂ】図１Ｂは、表示されたデジタル・コンテンツにおける物体または事物に関する更なる情報を獲得するために本明細書中に記述された代表的な方法およびシステムの用法を示す図である。
【図１Ｃ】図１Ｃは、デジタル・メディアにおける物体または事物に関する更なる情報をユーザに対して提供するために本明細書中に記述された代表的な方法およびシステムの用法を示す図である。
【図２Ａ】図２Ａは、画像における注目点から、画像フィンガープリントとして組立てられるべき特徴記述子ベクトルの集合を生成する先行技術のプロセスを示す図である。
【図２Ｂ】図２Ｂは、クエリ画像および基準画像の対応特徴箇所を一致させる適合変換を見出す先行技術の方法を例示する図である。
【図３】図３は、画像スナップショットにおける関心物体に関する付加的情報を獲得するという、本開示内容の実施形態に係る代表的なシステムを示すブロック図である。
【図４Ａ】図４Ａは、画像特徴インデックス・データベースを照会して、入力としての生のカメラ動画供給物を処理するという、本開示内容の実施形態に係る代表的方法を示すフローチャートである。
【図４Ｂ】図４Ｂは、画像特徴インデックス・データベースに対する照会の結果を処理して一致画像を見出すという、本開示内容の実施形態に係る代表的方法を示すフローチャートである。
【図４Ｃ】図４Ｃは、画像特徴インデックス・データベースを照会する前にキャッシュ済み画像集合を照会して一致画像を見出すという、本開示内容の実施形態に係る代表的方法を示すフローチャートである。
【図５Ａ】図５Ａ乃至図５Ｈは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、先行技術の方法を示す概略図である。
【図５Ｂ】図５Ａ乃至図５Ｈは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、先行技術の方法を示す概略図である。
【図５Ｃ】図５Ａ乃至図５Ｈは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、先行技術の方法を示す概略図である。
【図５Ｄ】図５Ａ乃至図５Ｈは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、先行技術の方法を示す概略図である。
【図５Ｅ】図５Ａ乃至図５Ｈは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、先行技術の方法を示す概略図である。
【図５Ｆ】図５Ａ乃至図５Ｈは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、先行技術の方法を示す概略図である。
【図５Ｇ】図５Ａ乃至図５Ｈは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、先行技術の方法を示す概略図である。
【図５Ｈ】図５Ａ乃至図５Ｈは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、先行技術の方法を示す概略図である。
【図６Ａ】図６Ａ乃至図６Ｅは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、本開示内容の実施形態に係る別の代表的方法を示す概略図である。
【図６Ｂ】図６Ａ乃至図６Ｅは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、本開示内容の実施形態に係る別の代表的方法を示す概略図である。
【図６Ｃ】図６Ａ乃至図６Ｅは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、本開示内容の実施形態に係る別の代表的方法を示す概略図である。
【図６Ｄ】図６Ａ乃至図６Ｅは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、本開示内容の実施形態に係る別の代表的方法を示す概略図である。
【図６Ｅ】図６Ａ乃至図６Ｅは、画像特徴インデックス・データベースを照会し、体系化し、且つ、アクセスする、本開示内容の実施形態に係る別の代表的方法を示す概略図である。
【図７】図７は、画像フィンガープリントを処理するという、本開示内容の実施形態に係る代表的システムを示すブロック図である。
【図８】図８は、画像フィンガープリントを処理するという、本開示内容の実施形態に係る別の代表的システムを示すブロック図である。
【図９】図９は、本開示内容の実施形態が実現され得る代表的システムを示すブロック図である。
【発明を実施するための形態】
【００１４】
各実施形態に対して詳細に参照が為されるが、それらの例は添付図面中に示される。各図を通し、可能であるときは常に、同一もしくは同様の部材を参照すべく同一の参照番号が使用される。
【００１５】
本明細書においては、デジタル・コンテンツまたはユーザの回りの世界に見られる人々、場所、および、事物に関する付加的情報をユーザに対して提供することにより、情報が豊富な視認体験をユーザに提供する方法およびシステムが記述される。本明細書中に記述される方法およびシステムは、先行技術のシステムと比較して幾つかの利点を提供する。第一に、本明細書における方法およびシステムは、動画、印刷物、または、ユーザの回りの世界のいずれから捕捉されたかに関わらず、単一の画像フレームに関して動作する。本明細書における方法およびシステムは、ユーザのモバイル機器が画像捕捉機能を有すると共に、ウェブ系サーバが画像認識サービスを提供するならば、該サーバに接続された上記モバイル機器上で動作するアプリケーションにより実施され得る。実際、本明細書中に開示される発明の利点のひとつは、これらの方法およびシステムが、マートフォンおよびタブレットにおいて見られる携帯式の民生カメラにより作成された写真を用いて実現され得るということである。
【００１６】
本明細書中に記述された方法およびシステムにおいては、スナップショットの“フィンガープリント”が抽出かつ使用されて、付加的情報を特定する。本明細書においては、画像特徴を特定かつ記述し、且つ、単一画像の固有フィンガープリントを生成する方法およびシステムが記述される。これに加え、オリジナル画像はユーザのモバイル機器内に記憶される必要はない、と言うのも、所望であれば、上記フィンガープリントは、ユーザに対して戻し表示すべく付加的情報と共に使用され得るからである。
【００１７】
本明細書中に記述されたシステムおよび方法を用いると、最初のスナップショットに関連するメディアもしくはコンテンツを特定することによる付加的情報の読出しは、上記フィンガープリントをクエリとして使用することで実施される。本明細書中に記述された如く、画像特徴式認識法は、特徴インデックスを使用して、画像の更に大規模なデータベースから小規模の一群の候補一致物を特定する。特徴インデックスを使用すると、大規模な画像集合に亙る検索が更に高速とされ得る。動画データから抽出された複数の単一フレームの集合に典型的に見られる如く、特徴のインデックス化を用いる既存の解決策は、多数の類似性を有する膨大な集合(数億個)の画像特徴による状況に陥る。代わりに、本明細書中に記述された方法およびシステムは、先行技術による上記問題を、急進的なハッシュ・テーブル設計態様を用い、確率的効果を活用して克服する。本明細書中に記述された方法およびシステムは、複数の冗長な画像特徴の全体に亙り、固有の画像特徴を自動的に選別し、更に固有的なデータ点のみがインデックス内に存在して留まることを許容することで、特定プロセスにおいて迅速に使用され得る効率的インデックスを生成する。対照的に、習用的な近似最近傍探索(ANN)方法は、フィルタリングされない全てのデータ点を記憶し、それらのマッチング性能が大きく低下する。
【００１８】
本明細書中に記述された方法およびシステムは、画像の解像度および固有性を維持し乍ら、大量の画像データを取扱う手段を提供する。本明細書中に記述された方法およびシステムはまた、長い使用時間に起因する要求トラフィックにおけるスパイクにも対処する。
【００１９】
更に、本明細書中に記述された幾つかの実施形態において、付加的情報は、モバイル機器上で全面的な画像認識を実施せずに、特定され得る。本明細書中に記述された方法およびシステムは、ウェブ通信レイヤとサーバ上の検索システムとの間で動作して要求の多くを傍受して取扱うスタンドアロンの再現可能レイヤの使用を導入している。類似するまたは等価的な要求をモバイル機器において選択的にキャッシュかつ特定することにより、サーバに対して前送りされる必要がある要求は更に少なくなる。
【００２０】
本明細書中に記述される複数の発明は、単独で、または、相互に対する種々の組み合わせで実現され得る。以下においては、種々の発明の各々が更に詳細に記述される。
【００２１】
図１Ａは、本明細書中に記述される発明の幾つかまたは全てを用いて、コンテンツ・プロバイダ101を視覚的メディア103を介してユーザ102に対して接続するシステム100を高レベルにて示す概略図である。コンテンツ・プロバイダ101は、たとえば、製造者、小売業者、広告主、メディア・コンテンツ所有者、および、製品もしくはコンテンツを有する他の事業体であり得る。視覚的メディア103は、たとえば、テレビ放送、動画、印刷物、または、看板であり得る。上記視覚的メディアは、分散ネットワーク104を介し、動画メディア放送プラットフォーム105または印刷媒体106に対して供給され得る。
【００２２】
図１Ａに示されたシステムにおいて、ユーザ102は、タブレット121またはスマートフォン122の如きモバイル機器を有している。上記モバイル機器は、幾つかの実施形態においては、プロセッサとメモリと無線通信機能とを備えたカメラでもあり得る。幾つかの実施形態において、上記モバイル機器は、加速度計、ジャイロスコープ、または、該モバイル機器の配向を検出する他のデバイスを備えて成る。本明細書中に記述された実施形態において、上記モバイル機器はインターネット使用可能とされる。上記モバイル機器の実施形態は、図３、図８および図９に関して以下に更に詳細に記述される。
【００２３】
幾つかの実施形態において、ユーザ102は、直接的にプラットフォーム105および106上に表示もしくは放送されたコンテンツ123を消費する。コンテンツ123はまた、ユーザのモバイル機器内に直接的に表示もされ得る。
【００２４】
第１の段階において、ユーザは、自身が更なる情報を知りたいという或る関心事物を特定する。上記関心事物は、たとえば、コンテンツ123もしくは124内に表示された、たとえば製品、小道具、衣服、または、他の物体の如き対象物であり得る。上記関心事物はまた、シーン自体の場所、または、シーン内に描かれた話題でもあり得る。幾つかの実施形態において、上記関心事物は、たとえば、映画、動画、または、表示されつつあるプログラムなどの、特別のコンテンツ自体である。
【００２５】
ユーザのモバイル機器におけるエンドユーザ・アプリケーションおよびカメラ機能を用いて、ユーザは、上記関心事物を描きつつある画面のスナップショットを取り込む。上記スナップショットは、上記事物自体の大写しであり得るか、または、関心事物の周囲領域を含み得る。上記スナップショットはまた、上記コンテンツを表示している表示デバイス、および、画面上に表示されつつあるコンテンツ以外のものまでも含み得る。幾つかの実施形態において、コンテンツ123もしくは124がユーザのモバイル機器上に表示されつつあるときなどにおいて、ユーザは、画面捕捉を選択することにより、関心事物を描いている画面のスナップショットを取り込み得る。
【００２６】
図１Ｂは、表示されたデジタル・コンテンツにおける物体または事物に関する更なる情報を獲得するために本明細書中に記述された代表的な方法およびシステムの用法を示している。図１Ｂに示された如く、ユーザは、(関心事物を含む)大きな視認領域が画面上に示される如く、モバイル機器121または122を保持し得る。幾つかの実施形態においては、視認領域全体が捕捉される。幾つかの実施形態において、上記システムは、視認領域の(コンテンツを示しているディスプレイ画面の如き)一定部分のみが重要であることを自動的に決定し得ると共に、ディスプレイ画面のみが捕捉される。幾つかの実施形態において、ユーザは、インタフェース150を介し、たとえば、ユーザの指またはスタイラスにて、部分151により表された如く、関心事物にタッチし、または、丸で囲むことにより、ディスプレイにおいて示された画像の部分集合を表し得る。すると、エンドユーザ・アプリケーションは、モバイル機器のディスプレイにおける画像の部分151のみを捕捉し得る。もし、ひとつの部分が表されたなら、そのときに画像の該部分151は、画像データベースにより処理されるべきクエリを生成すべく使用される。次に上記画像データベースは、部分151の少なくとも一部と一致すると決定された画像152を、モバイル機器にて表示するために返信し得る。
【００２７】
捕捉された画像に基づき、付加的情報153が選択されると共に、ユーザに対して表示され得る。表示された付加的情報153は、上記スナップショットにおいてメディア・コンテンツに関連または付随する情報である。付加的情報153は、上記スナップショット全体、または、任意の特定部分151に基づいて選択され得る。
【００２８】
幾つかの実施形態において、画像152は、付加的情報153の上方、下方、または、側方にて、付加的情報153と共に表示され得る。幾つかの実施形態において、画像152は、付加的情報154に相関された(注釈とも称される)タグ154を含み得る。少なくとも幾つかの実施形態において、タグ154は、当該画像152に対して付加的情報153が特定されたという画像152中に描かれた対象物の幾つかまたは全てに隣接して出現する。幾つかの実施形態において、タグ154は、該タグによりマーク付けされた対象物に対して関連付けられた付加的情報153の部分へと進行すべく、ユーザにより使用され得る。タグ上をクリックすることにより、たとえば、ユーザは、検索結果であり得るか又は付加的情報へのリンクであり得る画面上の関連情報へと導かれ得る。幾つかの実施形態において、上記タグはそれ自体が、付加的情報へのハイパーリンクを表す。
【００２９】
図１Ｃに示された実施形態において、中央に表示された画像163は、既に注釈付けされている。左側の概略図は、階層にて付加的情報164を記憶するディレクトリ162を示している。付加的情報164は、(たとえば、図１Ｃに示されたソファなどの)物体へと指向された特別のタグ166に対して関連付けられ得ると共に、その物体に関連する情報を含み得る。該情報は、上記物体に関連する、画像、テキスト説明文、価格、更なる情報へのリンクなどを含み得ると共に、該情報は、ディレクトリ162の下で階層構造にて記憶される。図１Ｃにおいて示された如く、ユーザがタグ166を起動した後、付加的情報164の少なくとも一部が表示される。たとえば、ソファの画像167，ソファのテキスト説明文168、および、他の情報が表示され得る。
【００３０】
次に図１Ａに戻ると、ユーザがスナップショットを取り込んだ後、エンドユーザ・アプリケーションは、上記スナップショット、または、該スナップショットの表示された部分のフィンガープリントを生成する。画像のフィンガープリントを生成する多くの公知の方法が存在する。概略的に、第1段階として、これらの方法は、増進セグメント試験由来特徴法(Features from Accelerated Segment Test)(FAST)、Harris、最大安定極値領域法(Maximally stable extremal regions)(MSER)など、または、同等物の如き、注目点検出アルゴリズムを用いて、画像における注目点(salient point)を検出する。上記注目点は次に、図２Ａに示された如く使用されて、特徴記述子ベクトルを生成し得る。図２Ａに示された如く、画像218の注目点219aおよび219bは、夫々、ベクトル220aおよび220bにより表され得る。スケール不変特徴変換法(Scale-invariant feature transform)(SIFT)、高速堅牢特徴法(Speeded Up Robust Features)(SURF)、２進堅牢不変スケーラブル・キーポイント法(Binary Robust Invariant Scalable Keypoint)(BRISK)、高速レチナ・キーポイント法(Fast Retina Keypoint)(FREAK)は、特徴記述子ベクトルを生成する公知の方法の例である。特徴記述子ベクトルは、ピクセル・パッチを特性記述する浮動小数点の数値もしくはビットの固定サイズ・ベクトル(たとえば、64次元もしくは128次元の浮動小数点ベクトル、または、512次元のビット・ベクトル)であり得る。上記ベクトルは、記述子サンプリング格子224内においてピクセル格子222に従い、画像内に配置された各ピクセル・パッチをサンプリングすることにより生成され得ると共に、ベクトル値は、２つのピクセル・パッチを表す２つのベクトル間の距離が、該２つのピクセル・パッチ間の(たとえば、輝度／明度などにおける)類似性の程度に相関する如く、選択され得る。
【００３１】
図２Ｂに示された如く、画像内容は、基準画像における対応内容と比較して異なる様に配向され得ると共に、一致物が依然として見出され得る。たとえば、クエリ画像240のクエリ特徴242は、基準画像250のクエリ特徴252と一致することが見出され得る。そのとき、画像内容240の相対的な姿勢(すなわち配向)は、クエリ画像240内のクエリ特徴242の各々の箇所と、基準画像250内の対応する基準特徴252の箇所との間の一群の関係から導かれ得る。上記一群の関係は、変換行列として表現され得る。幾つかの実施形態において、基準画像250の各特徴の変換済み箇所が、クエリ画像240の特徴の少なくとも幾つかの箇所に適合するまで、上記変換行列は、上記基準画像の各特徴の箇所を変換すべく反復的に算出され得る。変換行列の算出の反復毎に、一致する一群の対応特徴に対し、(変換行列により特徴箇所が変換された)基準画像と(特徴箇所が変換されていない)クエリ画像との間において適合が在るか否かを決定することにより、変換行列の有効性がチェックされ得る。幾つかの実施形態において、上記変換行列は、最小二乗近似を用いて算出され得る。図４Ａおよび図４Ｂに記述される発明的方法に関して後に論じられる如く、上記姿勢の決定は、モバイル機器において、または、サーバにおいて実施され得る。
【００３２】
次に、各特徴記述子の組み合わせが使用されることで、クエリ画像に含まれたひとつ以上の視覚的特徴であって、各特徴記述子に対応するピクセル・パッチの組み合わせにおいてグラフィック的に描写されるという視覚的特徴を表し得る。各特徴記述子の上記組み合わせはまた、一定程度の確実さを以て、各特徴記述子を含む基準画像を特定するためにも使用され得る。上記基準画像の特定は、該基準画像に対して関連付けられた特徴記述子と、クエリ画像から抽出され(且つそれに対して関連付けられ)ると共にフィンガープリント内に含まれた特徴記述子と、の間の関係に基づき得る。各特徴記述子間の関係は、上記特定操作の成功の可能性を決定し得る。
【００３３】
上記フィンガープリントは、上記スナップショットから抽出された幾つかの特徴のデジタル表現物である。上記フィンガープリントは、上記クエリの目的に対して適合作成された一群の特徴記述子を含み(または、それに基づいて生成され)得る。画像フィンガープリントの生成に含まれるべき特徴記述子は、ユーザにより選択され得る。そのときにエンドユーザ・アプリケーションは、画像部分151内の注目点を検出し、それに応じて、特徴記述子を生成し得る。ユーザが選択を行わないとき、エンドユーザ・アプリケーションは、スナップショット全体から複数の注目点を検出し、それに応じて、検出された注目点に対して関連付けられたフィンガープリントを生成し得る。幾つかの実施形態において、ユーザは更に、インタフェース150に対する軽打動作を介して画像における特別の物体を選択し得ると共に、エンドユーザ・アプリケーションは、選択された物体に対して関連付けられたフィンガープリントの送信を優先し得る。
【００３４】
図１Ａを戻り参照すると、スナップショット画像のフィンガープリントが獲得もしくは生成された後、該フィンガープリントは、付加的情報を獲得するために使用される。少なくともひとつの実施形態において、上記フィンガープリントは、通信リンク130を介してサーバ140へと送信される。上記フィンガープリントは、上記サーバに対し、無線リンクを介して無線的に、または、別の通信リンクを介して、送信され得る。
【００３５】
サーバ140は、たとえば、ひとつ以上の再現可能クエリ・キャッシュ141、画像マッチング・モジュール142、および、画像特徴インデックス・データベース143を備えて成り得る。破線円内におけるこれらの構成要素は、Geenee検索システムとも称され得る。
【００３６】
再現可能クエリ・キャッシュ141は、Geenee検索システムに対する入口点として機能し得る。再現可能クエリ・キャッシュ141は、モバイル機器からクエリ・フィンガープリントを直接的に受信し得る。到来するクエリ・フィンガープリントを画像マッチング・モジュール142へと前送りする前に、到来するクエリ・フィンガープリントは、先に受信されたフィンガープリントと比較される。一致が見出されたなら、先に受信されたフィンガープリントに対する前回の応答(たとえば、一群の候補画像、または、一致画像、または、一致しない画像など)が返信され得る。到来するクエリ・フィンガープリントが、先に受信されたフィンガープリントと一致しないなら、到来するクエリ・フィンガープリントは次に、画像マッチング・モジュール142へと前送りされ得る。
【００３７】
幾つかの実施形態において、画像マッチング・モジュール142は、到来するクエリ・フィンガープリントを直接的に受信する。画像マッチング・モジュール142は、上記クエリ・フィンガープリントを画像特徴インデックス・データベース143へと前送りし、更に処理する。上記の更なる処理からは、一群の候補画像(または、これらの画像に対するフィンガープリント参照子)が特定され、且つ、画像マッチング・モジュール142へと返信される。注釈データベース144は、そこから候補画像が特定されるべき一群の基準画像、及び、一群の基準画像と該基準画像に含まれた特徴を表す特徴記述子との間のマッピングを記憶している。注釈付けされた基準画像に対し、注釈データベース144は、注釈と、該注釈に対して関連付けられた付加的情報と、の間のマッピングも記憶している。
【００３８】
画像特徴インデックス・データベース143から候補画像フィンガープリントを受信した後、画像マッチング・モジュール142は、候補画像のフィンガープリントを、クエリ・フィンガープリント(または、その一部)と比較し、一致が在るか否かを決定する。もし一致が在るなら、それは、当該一致画像に添付された注釈と共に一致画像を注釈データベース144から読出すと共に、これを結果として返信する。
【００３９】
以下において更に詳細に記述される如く、画像特徴インデックス・データベース143は、先に提供された基準画像から抽出された特徴記述子に対する検索可能なインデックスを、上記注釈データベースに対して提供する。本開示内容に従う画像特徴インデックスに基づく検索の種々の実施形態は、たとえば、図６Ａ乃至図６Ｅに関して以下に記述される。
【００４０】
サーバ140はまた、コンテンツ・プロバイダ・インタフェース145も備えて成り得る。コンテンツ・プロバイダ・インタフェース145は、ウェブ・サービスとして実現され得る。コンテンツ・プロバイダは、コンテンツ・プロバイダ・インタフェースを使用することで、Geenee検索に含まれることが意図されたメディア材料(および、それに添付された付加的な注釈)を提供し得る。次に、上記メディア材料の少なくとも一部、および、付加的注釈は、注釈データベース144に記憶される。
【００４１】
サーバ140は、一台のサーバ、または、複数台のサーバの集合体であり得ることを理解すべきである。幾つかの実施形態において、サーバ140は、相互に連結されてクラウド160を形成する複数台のサーバを含み得る。更に、画像特徴インデックス143および注釈データベース144はサーバ140上に存在するとして示されるが、それらは、サーバ140に対してアクセス可能な他の記憶領域に存在することが可能である。幾つかの実施形態において、コンテンツ・プロバイダ・インタフェース145はクラウド系アプリケーションである。
【００４２】
代表例として、図１Ｂを戻り参照すると、ユーザは、TVで放送されつつあるTVショーの特別のシーンを選択すると共に、そのスナップショットを撮影し、該特別のシーンをクエリ内に含ませ、次にこれはサーバ140へと送信される。サーバ140内において、上記スクリーン・ショットに対して関連付けられた特徴記述子が画像特徴インデックス・データベース143内にも記憶されているなら、上記クエリは、上記特別のシーンの基準画像を含む一群の候補画像をもたらし得る。画像マッチング・モジュール140は、上記候補画像の中から一致画像を検出し、該一致画像を、または、一致画像が無いことの表示を、ユーザのクエリに対する応答として返信し得る。一致する候補画像に対して関連付けられた付加的情報もまた、注釈データベース144から読出され得る。幾つかの実施形態において、ユーザは更に、軽打により上記スナップショットにおける物体を選択し、該物体に対して関連付けられた特徴記述子に対するクエリの範囲を制限し得る。ユーザはまた、クエリに応じてサーバ140により戻された一致画像における物体を選択し、他の付加的情報も獲得し得る。
【００４３】
モバイル機器における画像特徴式認識
図３は、画像スナップショットにおける関心物体に関する付加的情報を獲得するという、本開示内容の実施形態に係る代表的なシステムを示すブロック図である。システム300は、たとえば、少なくともひとつのプロセッサ、メモリ、通信用のハードウェアおよびソフトウェア、および、カメラを備えて成るモバイル機器であり得る。幾つかの実施形態において、システム300は、図９に示された如きクライアント・デバイス910である。システム300は、関心物体の付加的情報の獲得を試みるユーザにより操作され得ることから、システム300は、ユーザのモバイル機器とも称され得る。図３は、システム300上に存在し得るハードウェアまたはソフトウェアにおいて実現され得る、本明細書中に記述される方法およびシステムに係る、種々のモジュールを示している。図３に示された如く、システム300は、画像獲得モジュール310、特徴記述子生成モジュール320、フィンガープリント生成モジュール330、および、付加的データ獲得モジュール340を含んでいる。
【００４４】
画像獲得モジュール310は、第１画像、すなわち“スナップショット”を表すデータを獲得する。上記スナップショットは、たとえば、カメラにより、または、スマートフォンもしくはタブレットのカメラ機能により捕捉され得る。幾つかの実施形態において、カメラに対して視認可能であるシーン全体のスナップショットが撮影かつ記憶される。幾つかの実施形態において、ユーザは、ディスプレイ上で視認可能であるシーンのひとつ以上の部分を示唆し、示唆された部分のみが記憶される。画像獲得モジュール310はまた、他の供給源から(たとえば、ローカルまたは遠隔的なデータ記憶デバイスから)も、画像データを獲得し得る。上記第１画像データは、更なる処理のために特徴記述子生成モジュール320へと送信される。
【００４５】
特徴記述子生成モジュール320は、上記第1画像データにより表されたピクセル値に基づいてひとつ以上の特徴を抽出し得ると共に、抽出された特徴の数値的表現物を生成し得る。幾つかの実施形態において、特徴記述子生成モジュール320は、上記第１画像の選択されたひとつ以上の部分における注目点を検出して位置決定すると共に、該注目点を表す特徴記述子を生成する。注目点を検出して位置決定し、且つ、それから特徴記述子ベクトルを生成する方法およびシステムは、上記に記述されている。
【００４６】
フィンガープリント生成モジュール330は、特徴記述子生成モジュール220により生成された特徴記述子ベクトルに基づいて、画像フィンガープリントを生成する。上記フィンガープリントは、ユーザにより選択された捕捉済み画像(または、描かれた特別の物体)の一部において検出された複数の注目点に基づく、または、捕捉済み画像の全体において検出された複数の注目点に基づく、一群の特徴記述子を含み(または、それに基づいて生成され)得る。
【００４７】
上記フィンガープリントが生成された後、該フィンガープリントは、付加的情報を獲得すべく付加的データ獲得モジュール340により使用される。幾つかの実施形態において、上記フィンガープリントは、付加的情報を特定する際に使用されるべきネットワークを通して、別のシステム(たとえば、図７において記述されるべきシステム700、または、図９のサーバ940)へと送信される。上記フィンガープリントに基づいて付加的情報を検索かつ特定するプロセスは、たとえば、図４Ａに関して以下に更に詳細に記述される。
【００４８】
幾つかの実施形態において、上記クエリの処理は、クエリ画像の特徴記述子が候補画像の特徴記述子と一致することを、一定程度の確実さを以て決定する段階を含む。この決定に基づき、上記クエリのプロセッサは次に、上記クエリ画像中に描かれているメディア・コンテンツ(たとえば、TVショーのシーンを描く画像、出版された広告の画像など)を特定し得る。上記クエリの処理に関する詳細は、たとえば、図６Ａ乃至図６Ｅにおいて後に記述される。
【００４９】
フィンガープリントによる照会が処理された後、付加的データ獲得モジュール340は、該クエリの結果に基づいて付加的データを獲得し得る。たとえば、上記クエリに基づき、該クエリにおけるフィンガープリントにより表された物体を含む第２画像が、一定程度の確実さを以て突き止められ、且つ、付加的データ獲得モジュール340は、表示のために上記第２画像を獲得し得る。上記第２画像は、上記物体に対して関連付けられた付加的情報であって、上記第１画像においては描かれていないという付加的情報(たとえば、異なる視点、異なるバックグラウンド、第１画像に描かれていない付加的な対象物など)を含み得る。更に、付加的データ獲得モジュール340によれば、上記物体に関連する付加的データも獲得され得る。先に図１Ｂ、図１Ｃにおいて記述された代表例を戻り参照すると、上記ソファの特徴記述子を含むクエリが処理された後、該クエリからは特別のブランドおよび型式のソファが特定され、且つ、該ブランドおよび型式の情報は、付加的データ獲得モジュール340により獲得され且つユーザに対して表示され得る。更に、上記特定の結果として、価格、上記ソファを販売している販売者などの如き他の情報もまた、付加的データ獲得モジュール340により獲得され且つユーザに対して表示され得る。
【００５０】
画像特徴に基づく検索
所定のクエリ画像に対し、画像特徴に基づく検索によれば、大規模な画像の集合体(訓練集合)の事前抽出された画像特徴を、上記クエリ画像から抽出されたものと比較することにより、上記訓練集合における一致物が見出される。これらの画像毎の無駄な比較を最小限に維持すべく、疎らな候補集合を効率的に事前選択するために、付加的な検索データ構造が使用される。画像特徴インデックスと称されるこの検索データ構造によれば、与えられたクエリ画像の特徴データ点が、画像の訓練集合の内で、該データ点に最も近いデータ点へとマッピングされ得るという類似性検索(たとえば、近似最近傍(ANN)探索)の実施が許容される。これらのデータ点に対して関連付けられた画像は、一群の候補画像として読出される。後時に記述される如く、上記画像特徴インデックスは、特徴データ点をインデックス付け／アドレス指定し得るマッピング・テーブルを提供する。斯かるマッピング・テーブルは、ハッシュ・テーブルであり得ると共に、アドレスと特徴データ点との間の関係は、ハッシュ関数に従って定義され得る。
【００５１】
次に、ユーザがスナップショットを取り込まずに、動画から画像特徴式認識を実施する、本開示内容の実施形態に係る代表的方法を示すフローチャートである図４Ａが参照される。ステップ402においては、ユーザのモバイル機器により、安定的なカメラ画像(すなわち、静止的と見える物体)が捕捉される。幾つかの実施形態において、上記モバイル機器は、たとえば、運動を検出する携帯電話または他のデバイスの加速度計センサを用いて、運動を殆どまたは全く検出しないときに、画像は安定的であることを決定し得る。運動を殆どまたは全く検出しない後、上記モバイル機器は、ひとつ以上の画像を捕捉し得る。幾つかの実施形態において、複数の画像が捕捉されたとき、上記モバイル機器は、該複数の画像の内のいずれが最も安定的な画像であるかを決定し、且つ、該最も安定的な画像をクエリ画像として使用し得る。
【００５２】
特に、ユーザが動画のスナップショットを取り込んでいるという幾つかの実施形態においては、画面上に表示されているものと、ユーザがスナップショットの取り込みを開始した後にスナップショットが取り込まれた時点との間に、遅延が在り得る。多くの場合、時間が経過したので、捕捉されたスナップショットはもはや、関心対象となる対象物またはシーンを含まない。本明細書に記述される幾つかの実施形態においては、上記スナップショットが取り込まれるよりも一定量の時間(たとえば、一秒)前に取り込まれた画像がクエリ画像として使用される。
【００５３】
ステップ404において、上記クエリ画像は、基準画像集合における一致画像を見出すべく使用される。上記クエリ画像内で検出された注目点から、特徴記述子が抽出されると共に、該抽出された特徴記述子からはフィンガープリントが生成される。上記フィンガープリントは次にサーバへと送信され、其処で画像特徴式認識が実施されることで一群の候補画像が見出され、それから、一致画像が見出され得る。
【００５４】
ステップ406において、もし一致画像が見出され得ず、その特別のカメラ画像に対する更なる解析が実施され得ないことが意味されたなら、異なる安定的画像を獲得すべくステップ402が再実行される。
【００５５】
ステップ406において一致画像が見出されたなら、ステップ408が、上記モバイル機器において実行され得る。ステップ408においては、上記クエリ画像の姿勢が推定され得る。姿勢および適合の推定は、図４Ｂにおいて記述されるべく、クエリ画像および基準画像が一致するか否かに関する決定の一部でもあり得る。２つの画像が適合するとの決定の後、ステップ410において、姿勢情報は上記モバイル機器へと送信され得る。幾つかの実施形態において、上記姿勢情報は、上記モバイル機器において表示され得る。
【００５６】
ステップ412において、上記システムは、トラッキングが喪失されたか否かを決定する。トラッキングは、たとえば、姿勢の相当の変化が検出されたか否かに基づいて決定され得る。幾つかの実施形態において、ステップ402乃至412は先ず、(ユーザにより、または、他の手段により表された)関心事物を特定かつ追尾すべく、上記システムを訓練するために使用され得る。トラッキングは、たとえば、上記モバイル機器を操作する対象者が撮影方向を相当に変動させたとき、または、以前は特定されていなかった新たな物体が動画内に現れたときに、喪失され得る。
【００５７】
上記システムが一旦、関心事物を追尾し得るなら、ステップ414が実行されて、生のカメラ画像の処理が開始され得、ステップ416においては、それから注目点が検出かつ位置決定され、且つ、ステップ418においては、特徴記述子が生成される。上記特徴記述子はその後、姿勢を推定すべくステップ408において再び使用され得る。
【００５８】
図４Ａに示された如き斯かる配置構成によれば、既に以前に特定されたコンテンツは、再び照会される必要がないこともある。故に、(クエリを生成するデバイスに対して遠隔的またはローカル的に配置された)画像特徴データベースに対するアクセスの回数は、減少され得る。このことは特に、モバイル機器が生の動画からクエリを生成すべく使用され、同一的な特徴を備えた同一の物体の画像が反復的に捕捉されることが予期されるときに有用である。同一的な特徴に対して画像特徴データベースを反復的に照会する必要がないことで、性能は向上され得る。この場合、上記モバイル機器は、(たとえば、ステップ406〜412を介しての)トラッキングが喪失されたか否かを決定するゴールキーパとして作用すると共に、(たとえば、上記モバイル機器を操作する対象者が撮影方向を相当に変動させ、または、以前は特定されていなかった新たな物体が動画内に現れたなどして)トラッキングが喪失されたときにのみ上記データベースにアクセスし得る。
【００５９】
次に、本明細書中に記述された如く、候補画像がクエリ画像と一致するか否かを決定する代表的方法を示す図４Ｂが参照される。ステップ432においては、画像フィンガープリントを含むクエリが受信される。ステップ436においては、上記フィンガープリントから、上記クエリ画像の各注目点に対するひとつ以上の特徴記述子ベクトルが獲得される。ステップ438においては、画像特徴インデックス・データベースが照会され、且つ、該クエリにおける特徴記述子に基づき、一群の候補画像のフィンガープリントが獲得される。幾つかの実施形態において、上記候補画像は、(たとえば、図１Ａの注釈データベース144などの)データベース内に記憶される。上記基準画像は、対応するフィンガープリントおよび注釈と共に記憶され得る。幾つかの実施形態において、上記基準画像および注釈は、コンテンツ・プロバイダにより提供される。
【００６０】
ステップ440〜448は、たとえば図２Ｂに示された直接的なマッチング比較技術を使用して全ての候補をクエリ画像と比較するループであって、図４Ａのステップ404の一部であり得るというループを示している。ステップ440においては、候補画像の集合から基準画像が獲得されると共に、該基準画像は次に上記集合から除去され得る。ステップ442においては、クエリ画像と基準画像との間の特徴距離が算出される。これらの特徴距離は、上記クエリ画像と上記基準画像との間の対応特徴を特定すべく使用され得る。上記特徴距離は、たとえば、特徴空間におけるユークリッド距離を用いて表現され得る。斯かる例においては、クエリ画像におけるＭ個の特徴および基準画像におけるＮ個の特徴に対し、結果は、ユークリッド距離のＭ×Ｎ行列であり得る。典型的には、最も近い特徴の一定割合(たとえば20％)のみが、“対応物”として受け入れられる。ステップ444においては、特定された対応特徴に基づき、クエリ画像に対する基準画像の姿勢(たとえば、配向)が、図２Ｂにおいて記述されたのと同様の様式で推定され得る。上記クエリ画像および上記基準画像は次に、クエリ画像の内容および基準画像の内容の姿勢の一切の相違を考慮して、ステップ446において比較されて、上記クエリ画像が上記基準画像と一致するか否かが決定される。幾つかの実施形態において、ステップ446は、上記基準画像に対して一次変換(homographic transformation)が適用されるという、図２Ｂにおいて記述されたのと同様の様式で実行されると共に、その後、一致する一群の特徴を含む上記クエリ画像の少なくとも一部が、変換済み基準画像に適合するか否かの決定が為され、それに基づき、上記２つの画像が一致するか否かが決定される。上記２つの画像が一致しないと決定されたなら、ステップ448が実行されて、一群の候補画像中に何らかの画像が残されているか否かが決定される。残存する候補画像が在るなら、候補集合内に何らの画像が残されなくなるまで、ステップ440、442、444、446および448が次の基準画像に対して反復される。上記候補集合における基準画像のいずれもがクエリ画像と一致しないなら、一致物が無いと結論付けられ、且つ、ステップ450においては適切な表示がモバイル機器に対して返信される。
【００６１】
図４Ｃは、画像特徴インデックス・データベースを照会する前にキャッシュ済み画像集合を照会して一致画像を見出すという、本開示内容の実施形態に係る代表的方法を示すフローチャートである。幾つかの実施形態において、クエリと一致すると見出された基準画像は、キャッシュ済み画像集合データベース内に載置され得る。幾つかの実施形態において、図４Ｃの方法は、図１Ａの再現可能クエリ・キャッシュ141により実現され得る。最初に上記キャッシュ済み画像集合データベースを検索することにより、二階層検索が実施され得る。上記キャッシュ済み画像集合データベースは典型的に、完全な基準画像データベースよりも相当に小規模であることから、上記検索が必要とするのは、更に短い時間、および、更に少ない演算資源である。幾つかの実施形態において、上記キャッシュ済み画像集合データベースは、(たとえば、画像特徴インデックスを採用する)基準画像データベースと同一様式で、但し更に小規模に、体系化され得る。幾つかの実施形態において、上記キャッシュ済み画像集合データベースは、先に受信されたクエリ・フィンガープリントと、その対応して一致する基準画像との間のマッピングも記憶する。上記キャッシュ済みクエリはまた、複数のユーザに対しても関連付けられ得る。複数の同一的なクエリ(たとえば、同一のフィンガープリントを含む複数のクエリ)が、異なる複数のユーザから受信されたとき、(キャッシュ済み画像集合データベースにおいて、または、基準画像データベースにおいて検索を実施することにより)ひとつのクエリのみが処理されると共に、検索結果は、同一のクエリを呈示する他のユーザに対して送られ得る。
【００６２】
図４Ｃに示された如くステップ432においては、クエリ・フィンガープリントが読出され、且つ、ステップ436においては、上記フィンガープリントから特徴記述子が選択される。ステップ432および436は図４Ｂと同一であり、それらの説明は反復されない。選択された特徴記述子は次に、ステップ463においてキャッシュ済み画像集合データベースを検索すべく使用され得る。上記検索は、キャッシュ済み画像集合における現在のクエリ特徴記述子に対する検索の実施に基づき、または、現在のクエリ・フィンガープリントを先に受信したクエリ・フィンガープリントと比較することにより、行われ得る。
【００６３】
幾つかの実施形態において、ステップ464においてキャッシュ済みクエリ画像が見出されたなら、ステップ465において、ユーザ(または、ユーザに対して関連付けられたモバイル機器)が登録され且つキャッシュ・ヒットに対して関連付けられ得る。上述された如く、ユーザをキャッシュ・ヒットの履歴に対して関連付けることは、キャッシュ・アクセス方針を精緻化する上で有用であり得る。そして次にステップ466が実行され、其処で、図４Ｂのステップ440〜448と同様に、読出された基準画像がクエリ画像と比較されて、それらが一致するか否かが決定される。検索結果はステップ467において報告され得ると共に、それに続き、上記検索結果に基づき、ユーザに対しては付加的情報が提供され得る。
【００６４】
他方、ステップ464において、キャッシュ済みクエリ画像が見出されなければ、次にステップ468においてクエリ・フィンガープリントが呈示されることで、基準画像データベースが照会される。ステップ469において、一致物が見出されたなら、上記クエリ・フィンガープリントは、キャッシュ済み画像集合データベースに対して付加され、且つ、ステップ468において見出された一致基準画像に対して関連付けられ得る。幾つかの実施形態において、上記検索結果は、ステップ470において、他のユーザに対しても一斉送信され得る。該一斉送信は、他のユーザが上記システムに対して同一のクエリを呈示することを防止する上で有用であり得る。
【００６５】
画像特徴インデックス
本明細書中に記述される新規な画像特徴式認識方法およびシステムの重要な特徴は、画像特徴インデックスである。記述される方法およびシステムは、動画フレームの精度における補償可能な損失に代えて、不可逆の確率論的なデータ管理を導入することで、固有性が少ない画像内容の自動的な除去と併せて、劇的に低下された演算コストおよび記憶要件を可能とする。斯かる方法およびシステムは特に、動画から生成された基準画像データの管理に対して適切である。
【００６６】
本明細書中に記述される新たな方法およびシステムを理解するために、以下の内容は、先行技術のシステムの説明である。図５Ａ乃至図５Ｈは、ハッシュ・テーブルを使用する公知の方法に伴う問題を示している。図５Ａにおいて、それから候補画像が選択され得るという一群の訓練画像に対して関連付けられた特徴記述子を体系化すべく、ハッシュ・テーブル510が使用される。該ハッシュ・テーブル510はバケット配列512を含み、其処では、各バケット・アドレスが、ハッシュ関数を介して、特徴空間のひとつ以上のセグメントに対して関連付けられる。そのときに各バケットは、バケットに対して関連付けられた空間セグメント内に幾何学的に存在する(たとえば特徴514などの)特徴に対する参照子を記憶し得る。各ハッシュ・バケットは、無制限数のスロットを有し得ると共に、無制限数の特徴参照子を含み得る。各ハッシュ・バケットは、特徴空間内における特徴ベクトル成分の箇所から決定された特徴記述子と、特徴空間セグメントに対して関連付けられたハッシュ・アドレスと、そのアドレスに対して関連付けられたハッシュ・バケットと、の間に関係に基づいて、特徴記述子(および、そのベクトル成分)に対して関連付けられる。幾つかの場合、特徴記述子ベクトルに対してはひとつ以上のハッシュ関数が適用され、且つ、該ハッシュ関数の出力は、どのアドレス(およびどのハッシュ・バケット)に対し、特徴記述子が関連付けられるべきかを決定するために使用され得る。
【００６７】
幾つかの場合、一群の特徴記述子により表され得る特徴の集合に対して与えられた名称である特徴空間515を区分すべく、ハッシュ関数が使用される。特徴記述子がベクトルとして表現されるとき、特徴記述子ベクトルは、次元の各々における成分を有する。そのとき、上記ハッシュ関数は(上記特徴空間を表す)ベクトル空間をひとつ以上の領域(たとえば、各特徴空間領域518)へと区分し得、その場合、各領域は、データ群特徴514を表す特徴ベクトル成分の集合を有し得ると共に、各領域は、ハッシュ・バケット・アドレスに対して関連付けられ得る。各特徴ベクトルは次に、上記ハッシュ関数により各ハッシュ・バケット内へとマッピングされ、且つ、(たとえば、類似する特徴を表す)一定の基準を満たすベクトルは、同一の領域にマッピングされ(故に、同一のハッシュ・バケットに対してマッピング)され得る。
【００６８】
その様にして、類似性検索を実施すべく局所性敏感型ハッシング(Locality sensitive hashing)(LSH)が使用され得、その場合、ハッシュ・テーブル510は、高確率を以て、類似するデータ点(たとえば、類似する特徴記述子を構成するベクトル)を同一のハッシュ・バケットに対して関連付け得る一群のハッシュ関数に対して関連付けられる。局所性敏感型とは、データ点同士の間における関連付けの確率が、データ点同士の間で増大する類似性に対して一様に増大する、という事実を指している。図５Ａに示された如く、与えられたクエリ特徴519に対し、該特徴519に対応する特徴記述子は、各ベクトル次元と共に、(“ｘ”により表された)一群のベクトル成分520を含み得る。各ベクトル成分520に対しては、クエリ・ベクトル成分と同一のハッシュ・バケット構成要素を共有するデータ点であって、クエリ・ベクトル成分の類似性距離限界値521以内でもあるというデータ点を選択することにより、近似ｋ−最近傍探索(ANN)が実施され得る。これらのデータ点は次に、たとえば、これらのデータ点をベクトル成分として含む特徴記述子ベクトルと、上記クエリ特徴を表す特徴記述子と間の距離に従い、順位付けされ得る。マッチングの決定は、上記順位付け(たとえば、最短の距離)に基づいて行われ得る。
【００６９】
図５Ｂは、先に記述された如く、画像特徴インデックス・データベースに対するクエリ・プロセスを実施する先行技術の方法530を示している。ステップ531においては、クエリ・フィンガープリントに含まれた各特徴記述子が、抽出され、且つ、個々の特徴を一覧するための(たとえばリストなどの)データ構造で記憶される。ステップ534乃至537は、クエリに応じて、画像特徴インデックス・データベースから、一巡目の特徴記述子読出しを実施すべく実行される。先に記述された如く、特徴サンプル空間を区分すべく、一群のハッシュ関数が使用される。故に、(ステップ534において、未使用のハッシュ関数が残されているかをチェックした後で)ステップ535においては、上記群における各ハッシュ関数が読出され、次に、ステップ535において、読出された上記関数は、特別のクエリ特徴記述子に基いてバケットに対するアドレスを生成すべく使用される。次に、ステップ536においては、アドレス指定されたバケットに記憶された基準特徴記述子のデータ点が収集される。ステップ534〜537は、ステップ534において決定される如く、上記群におけるハッシュ関数の全てが使用されるまで、反復される。
【００７０】
基準特徴記述子のデータ点が収集された後、それらはステップ538〜542を介してフィルタリングされるが、その場合、ステップ540においては、収集された基準特徴記述子のデータ点の各々とクエリ特徴記述子のデータ点との間の距離が算出されると共に、該距離はステップ541において一定距離Rと比較され、且つ、ステップ542においては、距離R以内である基準特徴記述子のみが是認される。ステップ538〜542は、ステップ534〜537から収集された全ての基準データ点が解析されるまで、反復される。
【００７１】
全てのクエリ特徴が解析された後、ステップ543においては、是認された特徴を含む基準画像が、候補画像として収集される。次にステップ544において、各候補画像は、たとえば、是認された基準特徴記述子の全ての(クエリ特徴記述子からの)合計距離に従ってソートされ、且つ、ステップ545においては、ソートされたリストが報告される。ソートされたリストに基づき、次に、どの候補画像が更なる処理に対して使用されるかが決定され得る。
【００７２】
図５Ｃは、先に記述された如く、画像特徴インデックス・データベース内へと基準画像を挿入する先行技術の方法550を示している。ステップ551においては、基準画像から基準特徴が抽出される。幾つかの実施形態において、(特徴記述子により表される)基準特徴は、基準画像に対して関連付けられたフィンガープリントから直接的に特定される。次にステップ553において、抽出された特徴は、一度に一個ずつ、選択される。次にステップ555において、選択された特徴記述子は一群のハッシュ関数へと入力され、其処で上記一群の各ハッシュ関数がピックアップされて、ステップ556にては、選択された特徴記述子からバケット・アドレスが算出される。次に、ステップ557においては、特徴記述子データ点をバケットのエントリ・リストに追加することにより、上記基準特徴記述子が上記バケットに対して付加される。ステップ554において、選択された特徴記述子に対するアドレスを算出すべく全てハッシュ関数が使用された後、ステップ553においては、ステップ552において決定される如く、抽出された全ての特徴記述子が処理されるまで、次に抽出された特徴記述子が処理のために選択される。ステップ558において、各特徴ベクトルは、基準画像に対して関連付けられたハッシュ・キーとしても記憶される。
【００７３】
図５Ａ、図５Ｂに記述された方法によるひとつの可能的な欠点は、選択されたバケットが、クエリ・データ点と類似する特徴データ点の良好な包含範囲を提供しないことがある、ということである。たとえば、図５Ｄに示された如く、クエリ特徴ベクトル成分570は特徴空間領域572へとマッピングされる。類似性距離限界値571内においては、クエリ特徴ベクトル成分570と同一の特徴空間領域内である領域部分573のみが検索される。クエリ特徴ベクトル成分570に対する近似最近傍物としては、同様に領域部分573内であるデータ点574が見出される。しかし、データ点575は、クエリ特徴ベクトル成分570から最短距離を有するものであるが、該データ点は選択されない、と言うのも、それは異なる特徴空間領域に属するからである。データ点575は、隣接するバケット(および隣接する特徴空間領域)へと検索が広がるならば見出されるが、斯かる配置構成は非常に演算集約的である、と言うのも、隣接するバケットの個数は次元の増加に対して指数的に増加するからである。故に、隣接するバケットへと検索を広げるのではなく、類似する複数のデータ点は同一バケットに対して関連付けられることで検索の精度を向上させるという可能性を更に高めることが好適である。
【００７４】
図５Ｅに示された如く、類似する複数のデータ点は同一バケットに対して関連付けられる可能性を更に向上させるというひとつの公知技術は、異なるハッシュ関数に対して関連付けられた複数のハッシュ・テーブル530を使用するものである。斯かる方法においては、クエリに含まれた特徴記述子が、同時的に異なるテーブル内である一群の重畳特徴空間領域を同時的にカバーする複数のバケットに対するアクセスに帰着し得る如く、(たとえば、ハッシュ関数群582および584などの)複数のハッシュ関数が、(実線格子および点線格子により表される如く)異なるが重畳しているという様式で、同一の特徴空間を区分し得ると共に、検索は上記一群の領域に局限され得る。重畳している複数のバケットは、区分された特徴空間の更に良好な包含を許容するが、クエリ特徴に最接近してはいない基準特徴が、クエリ特徴によりアドレス指定されたバケットに含まれ得ることがあり得ると共に、(たとえば、バケット内の基準特徴とクエリ特徴との間の距離を算出することによる)付加的なフィルタリングが実施されて、基準特徴が候補画像群内に含まれるべきか否かを決定することが必要とされ得る。
【００７５】
図５Ｆに示された如く、LSHを改善する別の公知技術は、エントロピ式LSHを用いて、クエリ・データ点の近傍にランダムなデータ点を生成する。これらのランダムなデータ点は、ハッシュ関数により、特徴空間領域590、592および594を同一のハッシュ・バケットへとマッピングさせることも可能である。ANN検索に対する類似性距離限界値596もまた、ランダムなデータ点を含むべく(図５Ａの類似性距離限界値521に対して)拡大され得る。更に、図５Ｇに示された如く、多重プローブLSHは、所謂、隣接バケットの配列に関し、クエリ由来の探査順序を採用することにより、付加的なクエリ点を導き得る。
【００７６】
上述のLSH技術は、パラメータ空間の区分に特有のバケット包含効果を向上させ得るが、当該候補画像の特徴記述子が抽出されてハッシュ・テーブル510の元で体系化されるべきである候補画像が動画から生成されるときには、膨大な演算コストおよび記憶要件があり得る。動画から生成された膨大な量のデータの故に、ハッシュ・バケットにおける各データ点とクエリ・データ点との間の実際の距離の算出を伴うANN検索を実施する間に、任意の与えられたバケットに記憶された各データ点を検証することは、非常に時間消費的であり且つ演算的に集約的であり得る。更に、図５Ｈに示された如く、動画は典型的に大量の反復画像内容を含み、結果として、抽出された画像特徴の大部分は、何らかの固有情報に寄与し得ないか、または、少数の固有的な画像特徴が多数の固有性の少ない特徴内で喪失され得ることで、特徴の存在に依存する任意の画像一致確率のランキングが低下される。これに加え、過剰占有されたハッシュ・バケットは、候補特徴記述子集合に対する不均衡に多数のデータ点に寄与すると共に、一定の反復的な画像特徴に対する性能利得を阻害する一方、不変の特徴の動作および変換は、一致物を確実に特定する特徴対応の一次的な整列試験の機能を低下させ得る。
【００７７】
拡張LSH
以下においては、LSHの改変技術を記述する方法およびシステムが提供される。該改変技術は、複数の良好に選択された非合同ハッシュ関数の重畳の統計的包含特性を、概略的な置換距離尺度として活用すべく使用され得る。これらの方法およびシステムが必要とするのは、更に少ない量の演算、および、更に少ない記憶容量である。
【００７８】
記述される方法は、上述された先行技術のLSH式のANNの実施形態における如くハッシュ・テーブルに記憶されたベクトル成分を用いて距離計算を実施する必要性を排除する。複数の重畳された非合同ハッシュ関数に隠された位置的情報が、重畳する各ハッシュ・バケットを、連続的なパラメータ空間の不規則的な過サンプリングとして解釈することにより、直接的に引き出され得る。局所性敏感型ハッシングの特性が与えられたとき、サンプルpiとクエリ・サンプルqとの間のハッシュ・バケット衝突の確率は、それらが近いほど増大する。与えられた一群のL個の異なる局所性敏感型ハッシュ関数に対して逆に解釈すると、このことは、クエリ点qの回りにおける類似性距離限界値内で重畳するハッシュ・バケットのD次元の特徴空間領域包含範囲は、更に小さい半径(R1＜R2)に対して増大することを意味する：
【００７９】
【数１】
2017513150.tif 000003
【００８０】
換言すると、クエリ点qに対し、h(q)によりアドレス指定される同時的に重畳するハッシュ・バケットの個数は、概略的に、上記クエリ点までの距離に関連する。この考察は、量子化された距離順位付け尺度として、直接的に使用され得る：
【００８１】
【数２】
2017513150.tif 000004
【００８２】
サンプル点piがqに近く来るほど、それが、qにより選択された重畳ハッシュ・バケットの幾つかにより包含される確率は高くなり、結果として、各バケットに添付された全ての点を収集するときに、それは重複物(duplicate)として更に高頻度に出現する。或る意味で、全ての空間的なデータ点の箇所は、ハッシュ・テーブル自体のバケット構成要素パターン内で損失が多くコード化または過サンプリングされたと見做され得る。このコード化は、データ点箇所に対する代替物の役割を果たす。
【００８３】
このコード化の品質および解像度は、各ハッシュ関数により定義される。第1に、クエリ点の回りの重畳バケットの密度は、正規分布に収束する(すなわち、更に多くの非合同ハッシュ関数が使用されるほど、解像度は更に精細となる)：
【００８４】
【数３】
2017513150.tif 000005
【００８５】
第２に、絶対的な距離ランクは、更に近いサンプルと(ノイズを含む)残部との間で、増大する。クエリ点qまで最大のバケット・サイズに対応する距離内に位置するデータ点pのみが、バケットの包含と距離との間の上記関係に委ねられる。
【００８６】
【数４】
2017513150.tif 000006
【００８７】
大寸のバケット・サイズ距離の外側に位置するサンプルは、同一のバケット包含領域を共有しないが、ハッシュ・アドレス衝突／バケット・エイリアシングに依り複数のバケットを共有することもある。与えられた理想的な各ハッシュ関数に対し、これらの衝突はパラメータ空間の全体に亙り統計的に均一に分散されると共に、距離ランク関係に委ねられない全てのサンプルは、候補集合に偽陽性として出現する同一の固定された可能性Pcollisionを有する。信号／ノイズのギャップは、ハッシュ関数の個数を増大することにより、または、テーブル・サイズを増大することより調節されることで、可能性Pcollisionが効果的に減少され得る。
【００８８】
図６Ａには、ハッシュ関数の個数を増大することの効果が示される。左側にて、クエリ特徴データ点693は、バケット空間694へとアドレス指定される。バケット空間694を区分すべく所定数のハッシュ関数が使用され、その場合、ハッシュ関数によりアドレス指定された空間の各々(たとえば空間695)はデータ点693と重畳し得る。694と重畳しない空間695の部分(たとえば、空間696)内のデータ点は(当該ハッシュ関数によりアドレス指定された空間695がクエリ・データ点と重畳するというハッシュ関数に対するその関連性に起因して)、依然として候補データ点として収集され得る。上記クエリ点の回りの重畳バケットの密度は、分布690により表され得る。右側に示される如く、ハッシュ関数の個数が増大するにつれ、分布690はガウス分布に収束する。ハッシュ関数の性質、すなわち、無限のパラメータ空間を有限な一群のバケットへとマッピングするという性質により、クエリ・データ点693によりアドレス指定された全てのセグメント694、695、696の外部に位置するデータ点は、依然として、同一のハッシュ・バケット内に収まることがある。理想的なハッシュ関数を仮定すると、これらの所謂バケット衝突は、均一なノイズとして現れる、と言うのも、それらは局所性敏感型特性に委ねられないからである。
【００８９】
図６Ｂ、図６Ｃは、上述の距離ランク尺度の確率的性質を更に活用する検索データ構造を体系化する代表的な方法602、604および606を示している。幾つかの実施形態においては、図６Ｂに示された如く、複数の同時的なハッシュ関数アドレス空間が、ひとつの統一ハッシュ・テーブル607において重畳され得、その場合、ハッシュ群からのハッシュ・インデックスは、一群のハッシュ・バケットへとアドレス指定されることで、複数のハッシュ関数が同一のハッシュ・バケットをアドレス指定することが許容され、各ハッシュ・バケットは要素のリストを記憶する。更に、図６Ｃのハッシュ・テーブル608および609は、バケットが常にゼロ個または１個の要素を有するという、改変された開放アドレス指定ハッシュ・テーブルのレイアウトを用いる新規な記憶手法を示している。ハッシュ衝突(すなわち、同一のバケットを指し示す複数のハッシュ関数)を解決するために、開放アドレス指定方法が採用され得る。図６Ｃの方法604により示された如く、3とアドレス指定されたバケットに対して特徴データ点が書き込まれるべきとき、それは既にデータを記憶している。上記ハッシュ・テーブルは、線形探査順序に従い、空のバケットが探査され得る。この代表例において、上記ハッシュ・テーブルは、線形様式で縦走される(たとえば、連続的にアドレス指定されたバケットを縦走する)。クエリ特徴データ点に対してハッシュ・テーブル・アドレスが算出さたとき、算出されたハッシュ・テーブル・アドレスから開始する全ての要素が、空のバケットに到達するまで、候補データ点に含められる。上記探査順序に沿って収集された候補特徴データ点は、クエリ特徴データ点に対して所定の類似性距離内に在る特徴データ点のみが保持される、という距離比較を用いてフィルタリングされ得る。
【００９０】
幾つかの実施形態においては、図６Ｃの方法606において示された如く、ハッシュ衝突を解決するために、線形探査の代わりに、挿入されたデータ点を、該データ点により最初にアドレス指定されたバケットの回りの所定範囲内のバケット内へとランダムに分散配置することにより、確率論的な局所的探査が使用され得ると共に、探査順序は追尾もされない。更に、距離比較を用いるフィルタリングは実施されず、且つ、ハッシュ・アドレス算出に使用される特徴のベクトル成分は、記憶される必要がない。
【００９１】
上述の確率的距離尺度は、距離インディケータとしての特徴データ点の発生を使用することから、バケット内に収集された候補データ点であって異なるハッシュ・アドレスに由来するという候補データ点が、後時にクエリの結果として読み出されたとき、特徴空間の全体に亙り統計的に分布されたノイズとして出現し得る。以下に記述される如く、これらのデータ点は、一群のバケット・エントリにおけるこれらのデータ点の発生の回数に基づき、正しく収集されたデータ点から区別され得る。たとえば、ハッシュ・テーブルの固有ノイズ・レベル以下であると参照された画像は、廃棄され得る(たとえば、図６Ｄのステップ616を参照)。上記ノイズは、たとえば、ハッシュ・テーブルのサイズを増大し、または、ハッシュ関数の個数を増大するなどにより、緩和(厳密に制御)され得る。
【００９２】
更に、図６Ｃに示された如く、方法606の下では、エントリは、更に最近のデータにより上書きされ得る。たとえば、89とアドレス指定されたバケットは、データ点620を記憶すべく使用されるが、確率論的な局所的探査の結果として、それはデータ点630により上書きされる。典型的に、過剰占有されたバケットに対して関連付けられたデータ点は、嵩高いが固有性の低い特徴に由来するので、これらのデータの上書きによれば、これらの特徴は消去され得ると共に、マッチング特徴の決定に対するそれらの影響は低下され得る。この上書きの方針はまた、オーバーフロー状況(すなわち、ハッシュ・テーブルにおける全てのエントリにデータが記憶されたとき)に対処する様にも調節され得る。
【００９３】
たとえば、図６Ｂ、図６Ｃのハッシュ・テーブル607〜609に従って配置されたハッシュ・テーブルによれば、ハッシュ・テーブルにおける隣接領域は、概略的に、バケット・リストの等価物である。従って、特徴データ点から算出された各ハッシュ・アドレスに対し、たとえば、メモリ・マッピングされたファイルアクセスにおいて通常的に採用されるページング機能を用いて、上記ハッシュ・アドレスの回りにおけるハッシュ・テーブルの固定サイズ・ブロック読取りが実施され得る。この様にして読取られつつある各ブロックはバケット・リストを表し得る一方、それは、ハッシュ関数により区分された特徴空間領域をオーバサンプリングする重畳バケットを表す。上記に説明された様に、バケットにおける特別のデータ点がクエリ・データ点に接近するほど、その特別のデータ点が、上記クエリ・データ点によりアドレス指定された重畳ハッシュ・バケットの少なくとも幾つかによりカバーされる確率が高くなる如く、クエリ・データ点によりアドレス指定された同時的に重畳するハッシュ・バケット(すなわち、上記クエリ・データ点に対してハッシュ関数を適用することにより算出されたアドレスに対して関連付けられたハッシュ・バケット)の個数は、概略的にクエリ・データ点の距離に関連する。結果として、その特別のデータ点は、重畳する各ハッシュ・バケット(すなわち、重畳された特徴空間領域に対してマッピングされたハッシュ・バケット)内において重複物として更に高頻度に出現し得ると共に、(ブロック読取りにより表される)重畳ハッシュ・バケット内におけるその特別のデータ点の発生の回数は、上記クエリ・データ点からのそれの距離を推定すべく使用され得る。上記ブロック内で最も高頻度に発生するこれらのデータ点は、次に、クエリに応じたマッチング特徴であると決定されると共に、候補データ点に含まれ得る。該候補データ点からは、該候補データ点に対して関連付けられた画像が、候補画像として獲得され得る。
【００９４】
図６Ｄは、たとえば図６Ｃのハッシュ・テーブル609を用いて体系化されたデータベースにより、画像特徴インデックス・データベースに対してクエリ・プロセスを実施する代表的方法を示している。ステップ532〜536は、図５Ｂにおけるものと同一であり、それらの記述は此処では反復されない。ステップ536においてバケット・アドレスが決定された後、ステップ612においては、図６Ｃに関して上述された如く、そのバケットの回りのハッシュ・テーブルのブロック読取りが実施される。次に、ステップ613において、収集された重複的な基準特徴データ点の各々は、たとえば、各基準特徴データ点に対して関連付けられた参照カウンタを追尾することにより、カウントされる。全てのクエリ・データ点が解析された後、ステップ614において、収集された基準特徴データ点に対して関連付けられた候補画像は、マッチング候補として選択される。各候補画像は、ステップ613において決定された重複的な基準特徴データ点の各々に対して関連付けられた参照カウンタの組み合わせ物に対して関連付けられ得る。次にステップ615において、上記参照カウンタの組み合わせ物は、候補画像の順位付けおよび選別に使用され得る。ステップ616において、一定のスレッショルド値を超えた幾つかの参照カウンタを備えた候補画像は、廃棄され得る。斯かるスレッショルド値は、所定のノイズ・レベルに基づいて決定され得る。
【００９５】
図６Ｅは、先に記述された如く、基準画像を画像特徴インデックス・データベース内に挿入する方法を示している。ステップ551〜556は図５Ｃの同様に付番されたステップと同一であるので、それらの説明は此処では反復されない。ステップ621においては、基準特徴量に対して第１のバケット・アドレスが決定された後、第２のバケット・アドレスを算出すべくランダム関数が使用される。該ランダム関数は、図６Ｂの方法602と同様に、挿入されたデータ点を、該データ点により最初にアドレス指定されたバケットの回りの所定範囲内のバケットにランダムに分散配置すべく使用され得る。次に、ステップ622において、上記基準データ点は、上記第２アドレスによりアドレス指定されたバケットに記憶される。ステップ623において、もし、そのバケット内に、記憶されている他の従前のデータが在るなら、そのデータは、上記基準データ点を優先して、廃棄される。
【００９６】
図７は、本明細書中に記述された各実施形態が実現され得る、本開示内容の実施形態に係る代表的システム700を示すブロック図である。幾つかの実施形態において、システム700は、図１Ａのサーバ140の一部であり得る。幾つかの実施形態において、システム700は、たとえば、図３のシステム300により送信されたクエリを処理すべく使用され得る。少なくともひとつの代表的実施形態において、システム700は、画像マッチング・モジュール752、基準画像データベース720、ハッシュ・テーブル730、ハッシュ・テーブル管理モジュール740、候補特徴記述子読出しモジュール746、候補画像読出しモジュール750、および、複数のハッシュ関数770を備えて成る。
【００９７】
少なくとも幾つかの代表的実施形態において、画像マッチング・モジュール752は、図１Ａに関して上述された画像マッチング・モジュール142である。
【００９８】
基準画像データベース720は、一群の候補画像を記憶し得る。各候補画像は、(たとえば、TVショーの間におけるシーンのスクリーン・ショットなどの)視覚的メディアの画像であり得ると共に、一群の所定の視覚的特徴を含み得る。これらの視覚的特徴は、システム700により処理されるべきクエリ内に含まれる可能性が高いと事前決定され得る。これらの特徴は、上述の特徴記述子により表され得る。各基準画像は次に、該画像内に含まれた一群の所定の視覚的特徴の少なくとも幾つかに対応するひとつ以上の特徴記述子に対して関連付けられ得る。一群の特徴記述子を含むクエリが受信されたとき、読出される候補画像に含まれる特徴記述子が、クエリのフィンガープリントに含まれる特徴記述子の少なくとも幾つかに対し、一定程度の確実さを以て一致するという決定に基づき、クエリに応じて基準画像データベース720からはひとつ以上の候補画像が読出され得る。幾つかの実施形態において、これらの読出された候補画像は次に、クエリ画像(すなわち、それから上記クエリが生成された画像)と比較されて、最適に一致する候補画像が見出され得る。
【００９９】
此処では、基準画像のデータベースが呈示されるが、データベース内に視覚的特徴をグループ化する(すなわち、視覚的特徴もしくは特徴記述子の組合せ物を、候補画像の代わりに、特別の物体に対して関連付ける)他の手法であって、本明細書中に開示された技術に対して十分に適用可能であり且つ本開示内容の有効範囲内であるという他の手法が在ることを理解すべきである。
【０１００】
ハッシュ・テーブル730は、一群のハッシュ関数770に対して関連付けられる。幾つかの実施形態において、ハッシュ・テーブル管理モジュール740は更に、衝突解決モジュール742およびオーバーフロー対処モジュール744を含んでいる。
【０１０１】
幾つかの実施形態において、ハッシュ・テーブル管理モジュール740、候補特徴記述子読出しモジュール746および候補画像読出しモジュール750は、図６Ｄ、図６Ｅにおいて開示されたクエリの処理を実現すべく構成され得る。ハッシュ・テーブル管理モジュール740は、クエリに応じて、ハッシュ・テーブル730に対するアクセスを提供する。ハッシュ・テーブル管理モジュール340は、ハッシュ・テーブル730に含まれた全てのハッシュ・テーブルのハッシュ・インデックス(すなわち、アドレス)を、図６Ｂ、図６Ｃの統一されたハッシュ・テーブル602、604および606と同様に、一群のハッシュ・バケットへとマッピングするマッピング・テーブルを提供する。各アドレスは、ハッシュ関数770を用い、特徴記述子データ点に基づいて算出される。
【０１０２】
ハッシュ・テーブル管理モジュール740の一部である衝突解決モジュール742は、(たとえば、一群の特徴記述子などの)新たなデータ点をハッシュ・テーブル730に対して関連付けるときに、ハッシュ衝突(すなわち、２つの異なるデータ点が同一バケットに対してアドレス指定される場合)に対処する。幾つかの実施形態において、衝突解決モジュール742は、図６Ｃおよび図６Ｅに関して先に記述された開放アドレス指定／探査方法を実現する。
【０１０３】
ハッシュ・テーブル管理モジュール740の一部であるオーバーフロー対処モジュール744は、ハッシュ・テーブル730において空のスロットが見出され得ない場合、該ハッシュ・テーブルに対する新たなデータ点(たとえば、一群の特徴記述子)の関連付けを取扱う。幾つかの実施形態において、オーバーフロー対処モジュール744は、図６Ｃおよび図６Ｅに関して先に記述された上書き方針を実現する。
【０１０４】
候補特徴記述子読出しモジュール746は、ハッシュ・テーブル730にアクセスし、一群の候補特徴記述子データ点を獲得する。クエリに含まれた各特徴記述子に対し、候補特徴記述子読出しモジュール746は、ハッシュ関数を適用してアドレスを算出し、該アドレスを使用してバケットを位置決定してから、バケットに対して関連付けられた全てのデータ点を読出す。探査順序が追尾されない場合、探査順序と共に他のバケットに対して関連付けられた全てのデータ点も読出される。確率論的な局所的探査が使用される場合、アドレス指定されたバケットの回りの所定範囲内の全てのデータ点も読出される。候補特徴記述子データ点が読出された後、各データ点は次に候補画像読出しモジュール750へと送信され、するとこれは、一群の候補データ点の中で、いずれの群の特徴記述子データ点が最も高頻度に反復しているかを決定し得る。これらの特徴記述子は、上記クエリに含まれた特徴記述子と最も類似していると決定されると共に、次に、上記クエリに応じた一群の候補画像または他の付加的な情報を特定すべく使用され得る。幾つかの実施形態において、候補特徴記述子読出しモジュール746および候補画像読出しモジュール750は、図６Ｄおよび図６Ｅの方法の少なくとも一部を実現する。
【０１０５】
候補画像を受信した後、画像マッチング・モジュール752は、候補画像のフィンガープリントをクエリ・フィンガープリント(またはその一部)と比較し、一致性が在るか否かを決定する。一致性が在るなら、システム700は、当該一致画像に対して注釈データベース780から添付された注釈と共に、一致画像を読出し、且つ、付加的情報および注釈をモバイル機器に対して返信する。
【０１０６】
幾つかの実施形態においては、図８に示された如く、代表的なクライアント・デバイス800は、図３のシステム300に加え、クエリ・キャッシュ840およびクエリ・キャッシュ管理モジュール850を含むことで、クエリ処理に対する二階層システムを形成し得る。クエリ・キャッシュ840は、図４Ｃにおいて記述されたのと類似方法を採用し、先に受信したクエリと、これらのクエリに応じてサーバ140から読出された特徴記述子(および／または候補画像)と、の間のマッピングを記憶し得る。新たなクエリが受信されたとき、クエリ・キャッシュ管理モジュール850は、新たなクエリの内容を、クエリ・キャッシュ800に記憶されたクエリの内容に対して比較し得る。もし、クエリ・キャッシュ840において一致物が見出されたなら、関連付けられた特徴記述子(および／または候補画像)は、上記クエリをサーバ130に送信せずに、応答として提供され得る。クエリ・キャッシュ840および／または候補画像データベース820において一致物が見出されなければ、そのときに、上記クエリはシステム700へと送信される。
【０１０７】
幾つかの実施形態において、斯かる二階層システムは、２つの異なるサーバ間に、または、システム700の一部として実現されることで、異なる複数のクライアント・デバイスに由来するが類似する内容を含むというクエリも取扱い得る。第1のクライアント・デバイスが、第１クエリを呈示してサーバ130に一致画像を読出させた後、別のクライアント・デバイスが、類似する内容を含む第２クエリを呈示することがある。その場合、第２クエリはクエリ・キャッシュ840を検索することにより対処され得ると共に、第１クエリに対する結果が再使用され得る。斯かる配置構成は、類似する内容を有するクエリにおけるスパイクに対処するために有用であり得る。たとえば、先に記述された如く、動画が数百万の視聴者に対して放送されつつあるとき、その多くは、自身の表示デバイス上に同時的に出現する関心対象物のスナップショットを取り込むことによりクエリを呈示し得ると共に、これらのクエリは、非常に類似した内容を含み得る。第１クエリが、相当に大規模の基準画像データベース720にアクセスすることで処理され、且つ、結果がクエリ・キャッシュ840に対して付加された後、同一の関心対象物を含む他のクエリはその後、代替的にクエリ・キャッシュ840にアクセスすることにより対処され得ることで、効率が相当に高められ得る。
【０１０８】
図９は、本開示内容の実施形態が実現され得る、本開示内容の実施形態に係る代表的システム900を示すブロック図である。図９に示された如く、システム900は、クライアント・デバイス910、ネットワーク930、および、サーバ940を含んでいる。クライアント・デバイス910は、ひとつ以上のプロセッサ912、メモリ・デバイス914、記憶デバイス916、ディスプレイ917、ネットワーク・インタフェース918、カメラ119(または他の画像生成デバイス)、および、加速度計922(または、他の配向決定デバイス)を含み、それらの全ては、バス920を介して相互に通信し得る。幾つかの実施形態において、ディスプレイ917は好適には、タッチスクリーンである。上記I/Oデバイスは、マイクロフォン、および、信号を獲得および／または出力し得る他の任意のデバイスを含み得る。ネットワーク930を介し、クライアント・デバイス910はサーバ940とデータを交換し得る。サーバ940もまた、ひとつ以上のプロセッサ942、メモリ・デバイス944、記憶デバイス946、および、ネットワーク・インタフェース948を含み、それらの全ては、バス950を介して相互に通信し得る。
【０１０９】
メモリ914および944は両者ともに、ランダム・アクセス・メモリ(RAM)、または、情報と、プロセッサ912および942により実行されるべき命令とを記憶する他の揮発性の記憶デバイスであり得る。メモリ914および944はまた、プロセッサ912および942により実行されるべき命令の実行の間に一時的変数または他の中間情報を記憶するためにも使用され得る。斯かる命令は、プロセッサ912および914に対してアクセス可能な持続的記憶媒体(たとえば、記憶デバイス916および946)に記憶された後、コンピュータ・システム910および940を、上記命令において指定された動作を実施すべくカスタマイズされた専用マシンとする。上記命令は、例示的にのみ、ソフトウェア・コンポーネント、オブジェクト指向ソフトウェア・コンポーネント、クラス・コンポーネントおよびタスク・コンポーネントの如きコンポーネント、プロセス、関数、フィールド、プロシージャ、サブルーチン、プログラム・コードのセグメント、ドライバ、ファームウェア、マイクロコード、回路機構、データ、データベース、データ構造、テーブル、アレイ、および、変数を含み得る、種々のソフトウェア・モジュールへと構成され得る。
【０１１０】
概略的に、本明細書中で用いられる如く“モジュール”という語句は、ハードウェアまたはファームウェアにおいて具現されるロジックを指し、または、たとえば、Java、Lua、CまたはC++の如きプログラミング言語で書かれた、可能的には入口点および出口点を有するソフトウェア命令の集合を指している。ソフトウェア・モジュールは、コンパイルされて実行可能プログラム内にリンクされ、ダイナミック・リンク・ライブラリ内にインストールされ、または、たとえば、BASIC、PerlまたはPythonなどの如きインタープリット型プログラミング言語で書かれ得る。ソフトウェア・モジュールは、他のモジュールまたはそれら自身から呼出し可能であり得、且つ／又は、検出されたイベントまたは割込みに応じて呼び出され得ることは理解される。演算デバイス上で実行されるべく構成されたソフトウェア・モジュールは、コンパクト・ディスク、デジタル・ビデオ・ディスク、フラッシュ・ドライブ、磁気ディスク、または、他の任意の有形媒体の如きコンピュータ可読媒体上に提供され得るか、または、デジタル・ダウンロード物として提供され得る(と共に、実行に先立ち、インストール、解凍、または、復号化を必要とする圧縮されまたはインストール可能な形態で最初は記憶され得る)。斯かるソフトウェア・コードは、実行用の演算デバイスにより実行されるべく該演算デバイスのメモリ・デバイスに部分的にまたは全体的に格納され得る。ソフトウェア命令は、EPROMの如きファームウェアに内蔵され得る。更に、ハードウェア・モジュールは、ゲートおよびフリップフロップの如き接続された論理ユニットに含まれ得、且つ／又は、プログラマブル・ゲート・アレイまたはプロセッサの如きプログラム可能ユニットに含まれ得ることは理解される。本明細書中に記述されたモジュールまたは演算デバイスの機能性は、好適には、ソフトウェア・モジュールとして実現されるが、ハードウェアまたはファームウェアにおいて具現され得る。概略的に、本明細書中に記述された各モジュールは、当該論理モジュールの物理的な構成または記憶内容に関わらず、他のモジュールと組み合わされるか、下位モジュールへと分割され得る論理モジュールを指している。
【０１１１】
クライアント・デバイス910およびサーバ940は、コンピュータ・システムと協働して該クライアント・デバイス910およびサーバ940を専用マシンとしまたはその様にプログラムする、カスタマイズされた有線ロジック、ひとつ以上のASICもしくはFPGA、ファームウェアおよび／またはプログラム論理を用いて、本明細書中に記述された技術を実現し得る。幾つかの実施形態に依れば、本明細書中に記述された動作、機能性および技術および他の特徴は、メモリ914および944に夫々含まれたひとつ以上の命令のひとつ以上のシーケンスを実行するプロセッサ912および942に応じてクライアント・デバイス940およびサーバ940により実施される。斯かる命令は、記憶デバイス916および946の如き他の記憶媒体からメモリ914および944へと読み込まれ得る。メモリ914および944内に含まれた一連の命令が実行されると、プロセッサ912および942は夫々、本明細書中に記述されたプロセス段階を実施する。代替実施形態においては、ソフトウェア命令の代わりに、または、それと組み合わせて、有線回路機構が使用され得る。
【０１１２】
本明細書中で用いられた“持続的媒体”という語句は、マシンを特別の様式で動作させるデータおよび／または命令を記憶する任意の持続的媒体を指している。斯かる持続的媒体は、不揮発性媒体および／または揮発性媒体を備えて成り得る。不揮発性媒体としては、たとえば、記憶デバイス916および946の如き光学的もしくは磁気的なデバイスが挙げられる。揮発性媒体としては、メモリ914および944の如きダイナミック・メモリが挙げられる。持続的媒体の一般的な形態としては、たとえば、フロッピー・ディスク、フレキシブル・ディスク、ハードディスク、半導体ドライブ、磁気テープ、もしくは、他の任意の磁気的データ記憶媒体、CD-ROM、他の任意の光学的データ記憶媒体、孔のパターンを備えた任意の物理的媒体、RAM、PROM、および、EPROM、FLASH-EPROM、NVRAM、他の任意のメモリチップまたはカートリッジ、および、それらのネットワーク化形態が挙げられる。
【０１１３】
たとえば、図１Ａの機器121および122はクライアント・デバイス910として実現され得ると共に、その場合、図３のシステム300および図４Ａ、図４Ｂの方法400、430および460は、記憶装置916およびメモリ914に記憶されたソフトウェア命令として実現され得る。幾つかの実施形態において、図１Ａのサーバ140はサーバ940として実現され得、その場合、図７のシステム700および図６Ｂ〜図６Ｄの方法600、602、610および620は、記憶装置946およびメモリ944に記憶されたソフトウェア命令として実現され得る。
【０１１４】
ネットワーク・インタフェース918および948は、ネットワーク930に対する二方向データ通信結合を提供し得る。たとえば、ネットワーク・インタフェース918および948は、統合サービス・デジタル・ネットワーク(ISDN)カード、ケーブル・モデム、衛星モデム、または、対応する形式の電話線に対してデータ通信接続を提供するモデムであり得る。別の例として、ネットワーク・インタフェース918および948は、互換的なLANに対してデータ通信接続を提供するローカル・エリア・ネットワーク(LAN)カードであり得る。無線リンクも実施され得る。任意の斯かる実施形態において、ネットワーク・インタフェース918および948は、種々の形式の情報を表すデジタル・データ・ストリームを搬送する電気的、電磁的または光学的な信号であって、記憶デバイス916および946に対してデータ構造を提供するという信号を送信および受信し得る。そのときにプロセッサ912および942は、(たとえば、ソフトウェア命令を実行して上記データを圧縮または解凍することにより)上記データを異なる形態へと変換してから、変換されたデータを(たとえば記憶デバイス916および946などの)記憶デバイスに記憶し、且つ／又は、変換されたデータをネットワーク・インタフェース918および948を介してネットワーク930上で送信し得る。
【０１１５】
幾つかの実施形態に依ると、本明細書中に記述された動作、技術および／または構成要素は、ひとつ以上の専用の演算デバイスを含み得る電子的デバイスにより実現され得る。上記専用の演算デバイスは、本明細書中に記述された動作、技術および／または構成要素を実施すべくハード結線され得るか、または、該演算デバイスは、本明細書中に記述された動作、技術および／または構成要素を実施すべく永続的にプログラムされたひとつ以上の特定用途集積回路(ASIC)またはフィールド・プログラマブル・ゲート・アレイ(FPGA)の如きデジタル電子的デバイスを含み得るか、または、該演算デバイスは、ファームウェア、メモリ、他の記憶装置、または、組合せ物におけるプログラム命令に従い、本開示内容の斯かる特徴を実施すべくプログラムされたひとつ以上のハードウェア・プロセッサを含み得る。斯かる専用の演算デバイスはまた、特注のハード結線ロジック、ASICもしくはFPGAを、特注のプログラムと組み合わせて、本開示内容の技術および他の特徴も達成し得る。上記専用の演算デバイスは、デスクトップ・コンピュータ、可搬的コンピュータ・システム、携帯式デバイス、ネットワーク用デバイス、または、本開示内容の技術および他の特徴を実現すべくハード結線および／またはプログラムされたロジックを取入れた他の任意のデバイスであり得る。
【０１１６】
上記のひとつ以上の専用の演算デバイスは概略的に、iOS、Android、Blackberry、Chrome OS、Windows XP、Windows Vista、Windows 7、Windows 8、Windows Server、Windows CE、UNIX、Linux、SunOS、Solaris、VxWorks、または、他の互換的なオペレーティング・システムの如き、オペレーティング・システムのソフトウェアにより制御および連携調整され得る。他の実施形態において上記演算デバイスは、独自開発されたオペレーティング・システムにより制御され得る。オペレーティング・システムは、実行のためのコンピュータ・プロセスを制御および計画し、メモリ管理を実施し、ファイル・システム、ネットワーク機能、I/Oサービスを提供し、且つ、特にグラフィカル・ユーザ・インタフェース(“GUI”)の如きユーザ・インタフェース機能性を提供する。
【０１１７】
本明細書中に記述された上述のシステムは、多くの用途を有し得ると共に、種々の状況で使用され得る。たとえば、本明細書中に記述された方法およびシステムは、モバイル機器のユーザに対して広告を送るシステムにおいて使用され得る。たとえば、ユーザは、場所を訪れ、刊行物を読み、または、映画を見る間に、関心となる対象物、話題、風景、または、箇所を特定し得る。本明細書における発明的なシステムおよび方法を用いると、ユーザは、上記対象物、風景、または、関心対象となる任意のもののスナップショットを取り込むと共に、画像を生成し得る。該画像は、周囲領域を含め、且つ、任意の視角にて捕捉され得る。そのときに上記システムは、上記画像から特徴を抽出し、上記画像の少なくとも幾分かに対応する特徴記述子を含むクエリを生成し、且つ、該クエリを、抽出された特徴に基づく検索のために、遠隔サーバへと呈示する。ユーザに対して表示され得る付加的情報は、ユーザに対して無料で提供され得るか、または、該情報の幾分かもしくは全ては、有料の広告の形態であり得る。幾つかの状況展開において、ひとつの事業体は、検索サービスを提供すると共に、ユーザに対して送信される製品もしくはサービスに関する付加的情報を送信するために販売者に対して課金し得る。幾つかの状況展開において、モバイル機器のユーザは、上述の方法およびシステムを用いて製品もしくはサービスに関する情報を読出す機能に対して課金され得る。
【０１１８】
上述の明細書においては、実施形態毎に変更され得る多数の特別の詳細に関して各実施形態が記述されてきた。記述された各実施形態の一定の適合化および改変が為され得る。当業者であれば、本明細書の考察、および、本明細書中に開示された発明の実施により、他の各実施形態は明らかであり得る。本明細書および各例は、例示的なものとしてのみ考慮され、発明の真の有効範囲および精神は以下の各請求項により表されることが意図される。各図中に示されたステップの順序は、例示目的のためだけであり、各ステップの何らかの特別の順序に限定されることは意図されない、ということも意図される。故に、当業者であれば、これらのステップは、同一の方法を実現し乍ら、異なる順序で実施され得ることを理解し得よう。
【図１Ａ】
2017513150.tif 000007
【図１Ｂ】
2017513150.tif 000008
【図１Ｃ】
2017513150.tif 000009
【図２Ａ】
2017513150.tif 000010
【図２Ｂ】
2017513150.tif 000011
【図３】
2017513150.tif 000012
【図４Ａ】
2017513150.tif 000013
【図４Ｂ】
2017513150.tif 000014
【図４Ｃ】
2017513150.tif 000015
【図５Ａ】
2017513150.tif 000016
【図５Ｂ】
2017513150.tif 000017
【図５Ｃ】
2017513150.tif 000018
【図５Ｄ】
2017513150.tif 000019
【図５Ｅ】
2017513150.tif 000020
【図５Ｆ】
2017513150.tif 000021
【図５Ｇ】
2017513150.tif 000022
【図５Ｈ】
2017513150.tif 000023
【図６Ａ】
2017513150.tif 000024
【図６Ｂ】
2017513150.tif 000025
【図６Ｃ】
2017513150.tif 000026
【図６Ｄ】
2017513150.tif 000027
【図６Ｅ】
2017513150.tif 000028
【図７】
2017513150.tif 000029
【図８】
2017513150.tif 000030
【図９】
2017513150.tif 000031
【手続補正書】
【提出日】平成28年10月6日(2016.10.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
モバイル機器を以てユーザにより獲得されたクエリ画像に関する付加的情報を特定してモバイル機器へと送信するサーバであって、該サーバは、
ひとつ以上の基準画像に対して関連付けられたひとつ以上の基準特徴記述子を記憶する基準画像データベースであって、少なくともひとつの基準画像特徴記述子は複数の関数を用いて当該基準画像データベースにおけるアドレス空間内の複数の第１アドレスに対してマッピングされ、且つ、該複数の関数はひとつ以上の特徴記述子を同一のアドレス空間へとマッピングすべく構成される、という基準画像データベースと、
プロセッサであって、
該モバイル機器から、ひとつ以上のクエリ画像特徴記述子を含む第１クエリを受信するクエリ受信モジュールと、
該ひとつ以上のクエリ画像特徴記述子の各々に対して該複数の関数を用いて複数の第２アドレスを算出し、且つ、該複数の第２アドレスの各々に対し、該基準画像データベースの所定領域内に記憶された重複的な基準画像特徴記述子の個数を決定するための候補特徴記述子読出しモジュールと、
該決定された重複的な基準画像特徴記述子の個数に基づいて一群の基準画像特徴記述子を選択するための候補画像読出しモジュールと、
該選択された一群の基準画像特徴記述子をひとつ以上のクエリ画像特徴記述子と比較して、該ひとつ以上の基準画像の内のいずれかひとつが該クエリ画像と一致するか否かを決定する画像マッチング・モジュールと、
を備えて成るひとつ以上のモジュールを実行するプロセッサと、
を備えて成り、
一致基準画像が決定されたなら、該サーバは更に、
該少なくともひとつの一致基準画像に対して関連付けられた付加的情報を注釈データベースから獲得する段階と、
該付加的情報を、該少なくともひとつの関心対象物に関する付加的情報として該ユーザに対して表示するために、該モバイル機器へと送信する段階と、
を実施するように構成されている、
サーバ。
【請求項２】
該プロセッサは更に、該複数の第２アドレスの各々に対し、該複数の第２アドレスの各々と該複数の第１アドレスの各々との間の関係に基づき、該ひとつ以上の基準画像特徴記述子に対するひとつ以上の参照子を提供するハッシュ・テーブル管理モジュールを実行すべく構成され、且つ、
該重複的な基準画像特徴記述子の個数は、該関係に基づいて決定される、
請求項１に記載のサーバ。
【請求項３】
該ハッシュ・テーブル管理モジュールは更に、ランダム関数を用いて該複数の第１アドレスを算出する衝突解決モジュールを備えて成る、請求項２に記載のサーバ。
【請求項４】
該ハッシュ・テーブル管理モジュールは、
オーバーフロー対処モジュールであって、
該複数の第１アドレスの内のひとつの第１アドレスが、該複数の第１アドレスの内の該ひとつの第１アドレスが算出されたときに、ひとつの第１基準画像特徴記述子に対して関連付けされるか否かを決定し、
該複数の第１アドレスの内の該ひとつの第１アドレスが該第１基準画像特徴記述子に対して関連付けられているとの決定に応じ、
該複数の第１アドレスの内の該ひとつの第１アドレスを、該第１基準画像特徴記述子から関連解除し、且つ、
該複数の第１アドレスの内の該ひとつの第１アドレスを、第２基準画像特徴記述子に対して関連付ける、
というオーバーフロー対処モジュール、
を更に備えて成る、請求項２に記載のサーバ。
【請求項５】
該プロセッサは更に、該候補画像読出しモジュールを実行して、
該決定された重複的な基準画像特徴記述子の各個数の組み合わせ物に対して各群が関連付けられた一群以上の基準画像記述子を順位付けし、且つ、
該順位付けの結果に基づいて、一群の基準画像特徴記述子を選択する、
ように構成される、請求項１に記載のサーバ。
【請求項６】
該プロセッサは更に、該候補画像読出しモジュールを実行して、
該選択された群の基準画像特徴記述子から、算出された重複的な基準画像特徴記述子の個数であって、所定スレッショルド値よりも小さいという個数に関連付けられたひとつ以上の基準画像を除外するように構成される、
請求項１に記載のサーバ。
【請求項７】
モバイル機器を以てユーザにより獲得された第１クエリ画像に関する付加的情報を特定かつ表示するコンピュータ実行型の方法であって、
該第１クエリ画像に含まれた該ユーザに対する少なくともひとつの関心対象物に対応するひとつ以上のクエリ画像特徴記述子を含む第１クエリを、該モバイル機器から受信する段階と、
該第１クエリの受信に応じ、類似性検索であって、
該クエリ画像特徴記述子の各々に対し、複数の関数を用いて複数のアドレスを算出する段階と、
該複数のアドレスの各々に対し、ひとつ以上の基準画像特徴記述子を記憶する基準画像データベースの一定領域内に記憶された重複的な基準画像特徴記述子の個数を決定する段階であって、該基準画像特徴記述子の各々は少なくともひとつの基準画像に対して関連付けられ、少なくともひとつの基準画像特徴記述子は、該複数の関数を用いて該基準画像データベースにおけるアドレス空間内の複数のアドレスへとマッピングされ、且つ、該複数の関数は、ひとつ以上の特徴記述子を同一のアドレス空間へとマッピングすべく構成される、段階と、
該複数のアドレスの各々に対して関連付けられた該基準画像データベースの該一定領域における該重複的な基準画像特徴記述子の個数に基づいて、ひとつ以上の候補画像を決定する段階と、
該ひとつ以上の候補基準画像に対する該特徴記述子を該クエリ画像特徴記述子と比較して、一致物が在るか否かを決定する段階と、
を備えて成るという類似性検索を実施する段階と、
一致物が在るなら、該一致物に対して関連付けられた付加的情報を獲得する段階と、
該一致物に対して関連付けられた付加的情報を、該ユーザに対する表示のために該モバイル機器へと送信する段階と、
を備えて成る、コンピュータ実行型の方法。
【請求項８】
ひとつのアドレスに対して関連付けられた所定領域内の該重複的な基準画像特徴記述子の個数は、該重複的な基準画像特徴記述子と、該アドレスに対してマッピングされた該第１クエリ画像特徴記述子と、の間の類似性の程度を反映し、且つ、
該ひとつ以上の候補画像を決定する段階は、
該重複的な基準画像特徴記述子の個数は所定スレッショルド値を超過したことを決定する段階と、
該重複的な基準画像特徴記述子に対して関連付けられた該ひとつ以上の候補画像を獲得する段階と、
を備えて成る、
請求項７に記載のコンピュータ実行型の方法。
【請求項９】
各基準画像特徴記述子は、各ハッシュ・バケットがひとつのアドレスに対して関連付けられたという複数のハッシュ・バケットを含むハッシュ・テーブルに基づいてデータベース内に記憶され、
各ハッシュ・バケットは、該アドレス空間内におけるひとつのアドレスに対して関連付けられ、該複数の関数は、ひとつ以上の特徴記述子を、同一群のハッシュ・バケットの内のひとつ以上のハッシュ・バケットに対してマッピングすべく構成される、
請求項７に記載のコンピュータ実行型の方法。
【請求項１０】
該モバイル機器から、ひとつ以上の第２クエリ画像特徴記述子を含む第２クエリを受信する段階と、
該ひとつ以上の第１クエリ画像特徴記述子を、該ひとつ以上の第２クエリ画像特徴記述子と比較する段階と、
該比較の結果に基づき、該類似性検索を実施しないと決定し、且つ、クエリ・キャッシュ内に記憶された該第１クエリと該ひとつ以上の候補画像との間のマッピングに基づき、該ひとつ以上の候補画像を獲得する、段階と、
を更に備えて成る、請求項７に記載のコンピュータ実行型の方法。
【請求項１１】
関心対象物に関する付加的情報を特定して表示するデバイスであって、該デバイスは、
プロセッサであって、
関心対象物を含む第１クエリ画像を獲得する画像獲得モジュールと、
該第１クエリ画像に対して関連付けられた複数の第１クエリ画像特徴記述子を抽出する特徴記述子生成モジュールと、
該抽出された第１クエリ画像特徴記述子に基づいて第１クエリ・フィンガープリントを生成し、且つ、該第１クエリ・フィンガープリントをサーバに対して送信するフィンガープリント生成モジュールであって、
該第１クエリ・フィンガープリントによれば、該サーバは、該第１クエリ・フィンガープリントに基づき、複数の基準画像特徴記述子を記憶するデータベースにおける類似性検索を実施することが可能とされ、且つ、該サーバは、該クエリ特徴記述子を、基準画像特徴記述子が最も高頻度でマッピングされた複数のアドレスまたは複数の隣接アドレスへとマッピングすることにより、該データベースから読出された少なくともひとつの基準画像特徴記述子に対して関連付けられたひとつ以上の候補画像を獲得することが可能とされる、
というフィンガープリント生成モジュールと、
該第１クエリ画像が、該ひとつ以上の候補画像の内の少なくともひとつと一致するか否かを決定する画像マッチング・モジュールと、
を含むひとつ以上のモジュールを実行するプロセッサを備えて成り、
該画像マッチング・モジュールにおける該決定によれば、ユーザに対して該少なくともひとつの関心対象物に関する付加的情報として表示するために、該ひとつ以上の候補画像の内の少なくともひとつに対して関連付けられた付加的情報を獲得することが可能とされる、
デバイス。
【請求項１２】
該プロセッサは更に、該画像マッチング・モジュールを実行して、
該第１クエリ画像特徴記述子同士の間における第１群の相対位置を推定し、
該ひとつ以上の候補画像の内の少なくともひとつに対し、
該各第１クエリ画像特徴記述子に対応する一群の対応する基準画像特徴記述子を決定し、
該一群の対応する特徴記述子同士の間における第２群の相対位置を算出し、且つ、
該第１群の相対位置と該第２群の相対位置との間の関係に基づき、該第１クエリ画像と該候補画像との間の適合の度合いを決定する、
ように構成され、
該第１クエリ画像が該ひとつ以上の候補画像の内の少なくともひとつと一致するか否かの決定は、該決定された適合の度合いに基づく、
請求項１１に記載のデバイス。
【請求項１３】
該各第１クエリ画像特徴記述子に対応する該一群の対応する特徴記述子を決定する該段階は、ひとつ以上の基準画像特徴記述子と該各第１クエリ画像特徴記述子との間のひとつ以上の特徴距離を算出する段階を備えて成る、請求項１２に記載のデバイス。
【請求項１４】
該デバイスは更に、
該第１群の相対位置に基づいて、該第１クエリ画像の第１姿勢を決定する段階と、
該第１姿勢を、先に獲得されたクエリ画像に対して関連付けられた第２姿勢と比較する段階と、
該比較の結果に基づき、トラッキングが喪失されたか否かを決定する段階と、
トラッキングが喪失されたことが決定されたとき、
該画像獲得モジュールにより、第２クエリ画像を獲得させる段階と、
該特徴記述子生成モジュールにより、該第２クエリ画像に対して関連付けられた複数の第２クエリ画像特徴記述子を抽出させる段階と、
該フィンガープリント生成モジュールにより、該抽出された第２クエリ画像特徴記述子に基づいて第２クエリ・フィンガープリントを生成させ、且つ、該第２クエリ・フィンガープリントを該サーバに対して送信させる段階と、
を実施すべく構成される、請求項１２に記載のデバイス。
【請求項１５】
該プロセッサは更に、該画像獲得モジュールを実行して、
複数の画像を獲得し、
該獲得された複数の画像の各々を、複数の第１タイムスタンプの各々に対して関連付け、
スナップショットの取り込みの開始時を検出し、
該開始時を第２タイムスタンプに対して関連付け、且つ、
該複数の第１タイムスタンプの各々と該第２タイムスタンプとの間の関係に基づき、該複数の画像の内のひとつの画像を、該第１クエリ画像として選択する、
ように構成される、
請求項１１に記載のデバイス。
【請求項１６】
モバイル機器を以てユーザにより獲得された画像に関する付加的情報を特定かつ表示するコンピュータ実行型の方法であって、該方法は該モバイル機器により実現され、且つ、該方法は、
付加的情報が表示されるべきであるという該ユーザに対する少なくともひとつの関心対象物を備えて成る第１クエリ画像を獲得する段階と、
該第１クエリ画像から、該少なくともひとつの関心対象物に対応する複数の第１特徴を抽出する段階と、
該抽出された各第１特徴を含む第１クエリを生成する段階と、
該第１クエリをサーバに対して送信する段階であって、該第１クエリによれば、該サーバは、該各クエリ特徴記述子を、基準画像特徴記述子が最も高頻度でマッピングされた複数のアドレスまたは複数の隣接アドレスへとマッピングすることにより、ひとつ以上の基準画像を獲得することが可能とされ、且つ、該サーバは、該第１クエリに基づいて獲得された該ひとつ以上の基準画像に基づき、該サーバが該少なくともひとつの関心対象物に関する付加的情報を記憶していることを決定することが可能とされる、段階と、
該サーバから、該少なくともひとつの関心対象物に関する該付加的情報を受信する段階と、
該少なくともひとつの関心対象物に関する該付加的情報を該ユーザに対して表示する段階と、
を備えて成る、コンピュータ実行型の方法。
【請求項１７】
当該コンピュータ実行型の方法は更に、該モバイル機器のインタフェースを介し、ユーザによる該第１クエリ画像の一部の選択を受信する段階を備えて成り、
該第１クエリ画像から複数の第１特徴を抽出する該段階は、該選択された部分に対応する複数の第１特徴を抽出する段階を備えて成り、且つ、
第１クエリを生成する該段階は、該選択された部分に対応する該抽出された各第１特徴を表す第１クエリを生成する段階を備えて成る、
請求項１６に記載のコンピュータ実行型の方法。
【請求項１８】
該抽出された各第１特徴を記憶する段階と、
第２クエリ画像を獲得する段階と、
該第２クエリ画像から複数の第２特徴を抽出する段階と、
該記憶された各第１特徴と該抽出された各第２特徴との間の関係を決定する段階と、
該関係に基づき、該抽出された各第２特徴を表す情報を含む第２クエリを該サーバに対して送信しないことを決定する段階と、
を更に備えて成る、請求項１６に記載のコンピュータ実行型の方法。
【国際調査報告】
2017513150.tif 000032
2017513150.tif 000033
2017513150.tif 000034