JP2009020888A - インビジブルジャンクションを生成する方法及びシステム - Google Patents

Abstract

【課題】画像ベースの書類パッチ認識用のインビジブルジャンクションを用いるシステムと共に、従来技術の欠点を克服すること。
【解決手段】本発明は、電子書類のページ毎に固有のローカル特徴群であるインビジブルジャンクションを使用し、捕捉した画像を電子書類の一部と照合する。本発明は、画像捕捉装置、特徴量抽出及び認識システム、及びデータベースを含む。電子書類が印刷される場合、特徴量抽出及び認識システムは、書類ページの画像を捕捉する。捕捉した画像中の特徴は、抽出され、索引付けされ、データベースに格納される。所与の問い合わせ画像−通常的には、低解像度の画像捕捉装置で捕捉された何らかの書類ページの小さなパッチ−に関し、問い合わせ画像中の特徴が抽出され、データベースに格納済みの画像と比較され、その問い合わせ画像を確認する。本発明は、特徴量検索、特徴索引付け、特徴量検索／幾何学的推定の方法も含む。
【選択図】図１

Description

本発明はパッチ認識(patch recognition)の技法に関連する。具体的には、本発明は画像ベース書類パッチ認識に関するインビジブルジャンクション(invisible junction)と呼ばれる新たな特徴を使用するシステム及び方法に関連する。

かつてコンピュータ及び電子書類はデスクトップ環境での使用に制限されていた。デスクトップ環境では、電子書類はコンピュータによりプリンタに出力され、紙で印刷されていた。プリンタ及びコピーは、私用の及び商用のオフィス環境で、パーソナルコンピュータを伴う家庭環境で及び書類印刷や出版サービス環境で使用される。電子書類が紙で印刷されると、これら２種類の書類の取り扱いは殆ど独立である。印刷及び複写技術は、静的な印刷媒体(即ち、紙書類)とインタラクティブな仮想世界(virtual world of interactivity)との間のギャップを埋めることができておらず、その仮想世界は、ディジタル通信、ネットワーキング、情報提供、広告、娯楽及び電子商取引等のようなものをふくむ。

ここ数年にわたる小型携帯通信装置及びパーソナル電子装置(例えば、パーソナルディジタルアシスタント(PDA)、携帯電話機(例えば、カメラ付き携帯電話機)及びディジタルカメラ等)の出現及び普及は、電子的に読取可能且つ検索可能な形式にすることで、及びインタラクティブなマルチメディア機能を導入することで、書類の概念を電子形式を含むように拡張し、これらは従来の印刷媒体では例を見ないものである。

一方の電子書類の世界と他方の紙書類の世界の間を橋渡しする際、従来技術には問題がある。電子的にアクセス可能な仮想マルチメディアの世界と紙媒体の物理的な世界との間にはギャップがある。特に、印刷された紙を使って、その紙書類の生成元の電子書類にアクセスすること又はそれを発見することさえ、非常に困難である及び／又は演算負担が大きい。印刷された書類に対応する電子書類を特定及び発見する際の主な障害は、カメラで捕らえられている画像パッチの認識である。印刷書類の画像を捕捉することは、カメラ付き携帯電話の普及と共に些細なことになりつつあるが、そのような低解像度画像を使って電子書類を取り出す技法は確立してない。

言い換えれば、カメラが見ている書類をデータベースから効率的に特定し、認識されたページでカメラが見ている地点をピンポイントで正確に特定し、認識された書類ページにおける画像のフレームボックスを推定する方法は確立してない。この認識作業は、次のような事項により更に困難になる：１）入力画像は、眺めている書類ページの小さな一部分であること；２）互いに同様に見える多数の書類ページがデータベースに存在すること；３）携帯カメラは様々な表示状態を有し、その表示状態は、手の動きに起因して紙及びカメラの動きに関して様々な表示角度及び距離を含むこと；４）照明の変化に起因して顕著な高度変動が起こること；及び５）ユーザが紙を手で持っている場合、平坦でない幾何学的な歪みがあるかもしれないこと等である。

従来いくつかの試みがあるが、それらはいくつもの欠点を有する。例えば、一般的なSIFT(Scale Invariant Feature Transform)は、テキスト書類には適していない。SIFTキーポイントは、スケール空間中の極値から選択される。より具体的には、全てのスケール及び画像位置が、スケール空間内のローカルな最大値に関してスキャンされ、それらのローカルな最大値がキーポイント候補になる。これは文字の識別におけるSIFTを貧弱なものにしてしまい、SIFTは適切でなくなり、ノイズの多い環境で反復的になる。他の従来法は、テキストブロックの幾何学的特徴に焦点を当てるが、それらはアジアの言語や象形文字の言語には適切でない。

本発明の課題は、画像ベースの書類パッチ認識用のインビジブルジャンクションを用いるシステムと共に、従来技術の欠点を克服することである。

本システムは有利である。なぜなら、本システムは低解像度の画像パッチのインビジブルジャンクションを用いて、関連する電子書類、ページ、見ている場所及び見ている領域を特定及び抽出するからである。本システムは有利である。なぜなら、本システムは西洋の及び東洋の言語双方と共に非常に高速に動作し、文字及び画像成分の混ざった画像を処理するからである。本発明は、電子書類のページ毎に固有のローカルな特徴群であるインビジブルジャンクションを利用して、捕捉した画像と電子書類の一部分とを照合する。一実施例では、本発明によるシステムは、画像捕捉装置、特徴量抽出及び認識システム、及びデータベースを含む。特徴量抽出及び認識システムは、特徴量抽出部、特徴量インデキシング部、特徴量検索部及び幾何学的推定部を更に有する。電子書類が印刷される場合、特徴量抽出及び認識システムは、例えば印刷捕捉ソフトウエアにより、書類ページの画像を捕捉する。その後、捕捉した画像中の特徴は、抽出され、索引付けされ、データベースに格納される。所与の問い合わせ画像(query image)−通常的には、ウェブカム(web-cam)のような低解像度の画像捕捉装置で捕捉された何らかの書類ページの小さなパッチ−に関し、問い合わせ画像中の特徴が抽出され、データベースに格納済みの画像と比較され、その問い合わせ画像を確認する。本発明は、特徴量抽出、特徴量インデキシング、特徴量抽出及び幾何学的推定を行う方法も含む。

上記の特徴及び利点は全てを包含するものではなく、特に、多くの追加的な特徴及び利点が、明細書及び図面の観点から、当該技術分野で通常の知識を有する者に明らかになるであろう。更に、本願で使用されている言葉は、原則として、説明や理解を促すように選ばれており、発明事項の範囲を限定する意図ではないことに留意すべきである。

本発明は非限定的な実施例により添付図面と共に以下で説明され、図中、同様な要素を指すために同様な番号が使用される。

画像ベース書類パッチ認識のインビジブルジャンクションと言及される新規な特徴を利用するシステムが説明される。以下の説明では、説明の目的で多くの具体的詳細が説明され、本発明の十分な理解を図っている。しかしながら、本発明はそのような具体的詳細によらずに実施できることは当業者に明らかであろう。また、本発明を曖昧にすることを避けるため、構造や装置はブロック図形式で示される。

本明細書における「一実施例」又は「実施例」は、その実施例に関して説明される特定の特質、構造又は特徴が、本発明の少なくとも１つの実施例に含まれることを意味する。本明細書の様々な場所で「一実施例」なる用語が使用されていることは、全て同じ実施例であることを必ずしも意味しているわけではない。

以下の詳細な説明の一部は、コンピュータメモリ内のデータビットを処理するアルゴリズム及び記号表現で与えられる。これらのアルゴリズムの説明及び表現は、データ処理技術分野の当業者が他の当業者に彼らの仕事内容を最も効率的に伝えるのに使用される手段である。ここで、アルゴリズムは一般に所望の結果に導く首尾一貫した一連のステップと考えられる。そのステップは物理量の物理的処理を必要とするものである。必須ではないが、通常それらの物理量は、格納、転送、結合、比較その他の処理を施すことの可能な電気的な又は磁気的な信号の形態をとる。原則的な一般的な用法の観点から、ビット、値、エレメント、シンボル、キャラクタ、期間、数等としてそれらの信号に言及することが折に触れて便利なことが分かる。

しかしながら、これらの及び類似の用語の全ては、適切な物理量に関連しており且つそれらの量に付された便宜的なラベルにすぎないことに留意を要する。特に断りのない限り、以下の説明から明らかなように、本説明を通じて、「処理」、「演算」、「計算」、「決定」又は「表示」等のような用語を用いる説明は、コンピュータシステム又は同様な電子コンピュータ装置の動作や処理に関連し、その動作や処理は、コンピュータシステムのレジスタ及びメモリの中で物理的な（電子的な）量として表現されるデータを、コンピュータシステムメモリやレジスタその他の情報ストレージ、伝送又は表示装置の中で物理量として同様に表現される他のデータに変換及び処理することが、理解されるであろう。

本発明はここで説明される処理を実行する装置にも関連している。その装置は、必要な目的に応じて特別に構築されてもよいし、コンピュータに格納されているコンピュータプログラムによって選択的にアクティブにされる又は再構成される汎用コンピュータで構築されてもよい。そのようなコンピュータプログラムはコンピュータ読取可能な記憶媒体に格納されてもよく、その記憶媒体は、フロッピディスク、光ディスク、CD-ROM、磁気光ディスク、リードオンリメモリ(ROM)、ランダムアクセスメモリ(RAM)、EPROM、EEPROM、磁気又は光カード等の如何なるタイプのディスクを含んでもよいし、或いは電子的な命令を格納するのに適した如何なるタイプの媒体を含んでもよい。また、ディスクも媒体もそれぞれコンピュータシステムバスに結合されてもよい。

最後に、ここで説明されるアルゴリズム及び表示は、特定のコンピュータその他の装置のどれにも固有に関連するものではない。様々な汎用システムがここで教示するものによるプログラムと共に使用されてよく、或いは、必要な方法ステップを実行するように、よりいっそう特化した装置を構築することが便利なことが分かるかもしれない。これら様々なシステムに必要な構造は以下の説明から明らかになるであろう。更に、本発明は特定のプログラミング言語のどれにも依存しない。ここで説明される本発明の教示内容を実現するのに様々なプログラミング言語が使用されてよいことが分かるであろう。

システム概要
図１を参照するに、本発明のシステムの例100が示され、その新たな特徴は、画像ベース書類パッチ認識のインビジブルジャンクション(invisible junction)と言及される。本発明はインビジブルジャンクションを使用し、インビジブルジャンクションは、図５Ａ−５Ｄを参照しながら以下で説明されるようなローカル（局所的）な一群の特徴であり、捕捉した画像を電子書類の一部分と照合するためのものである。本実施例では、システム100は、画像捕捉装置106、特徴量抽出及び認識システム108、並びにデータベース110を有し、印刷された又は紙の書類102の一部の画像を捕捉し、対応する電子書類、ページ、見ている場所及び見ている領域を抽出する。紙書類102の元の領域104と電子表現112との間の関連付け(対応関係)は、線114で示されている。図１は、ある紙書類102の小さなパッチ104のようなクエリ画像(問い合わせ画像)を画像捕捉装置106と共に捕捉するシステム100の具体例116aを示す。特徴量抽出及び認識システム108は、問い合わせ画像中の特徴量を抽出し、データベース110に格納済みの画像とそれらを比較し、電子表現112を同定する。

画像捕捉装置106は当該技術分野で既知の如何なる既存のタイプのものでもよい。例えば、問い合わせ画像を処理する場合、画像捕捉装置106は、ウェブカメラでもよいし、携帯電話に備わるカメラでもよいし、或いはディジタルカメラでもよい。本発明は、低解像度の画像捕捉装置と共に動作可能なので、特に有利である。画像捕捉装置106は、特徴量抽出及び認識システム108と通信するように結合されている。この通信は有線ネットワークを介してもよいし或いは無線ネットワークを介してもよい。

モデル画像が索引付け(インデキシング)される別の例では、画像捕捉装置106は、印刷書類を生成するソフトウエアや複合機のスキャナである。例えば、そのような実施例の場合、画像捕捉装置106は印刷捕捉ソフトウエアでもよい。これらの実施例はコンピュータ(図示せず)により出力又は印刷される書類を索引付けするのに使用される。

特徴量抽出及び認識システム108は、特徴量抽出、索引付け及び検索のインビジブルジャンクションに関する機能を実行する。特徴量抽出及び認識システム108は、特徴量抽出部310、特徴量インデキシング部312、特徴量検索部314及び幾何学的推定部316を、図２−４を参照しながら詳細に後述されるように更に有する。特徴量抽出及び認識システム108は、画像捕捉装置106に結合され、画像パッチ又は紙書類のモデル画像、紙書類の画像を受信する。特徴量抽出及び認識システム108は、データベース110に結合され、書類ページ及び電子書類の特徴記述又は電子書類に至るためのインデックスを格納する。特徴量抽出及び認識システム108は更にデータベース110にも結合され、検索の際に電子書類へのインデックス又は電子書類を検索する。特徴量抽出及び認識システム108は電子書類、ページ、見ている地点及び見ている領域等の検索されたものを、他のコンピュータシステムへ出力し、ユーザインターフェースによる表示に備える。

データベース110は通常のタイプのものであり、インデックス、電子書類、特徴記述及び他の情報（索引付けプロセス及び検索プロセスで使用される他の情報）を格納する。データベースはデータベースの連体でもよい。一実施例では、データベース110は複合機内に設けられる。

本発明によるシステム100は、多数の利益をもたらす点で特に優れている。第１に、本発明は新たな特徴を使用し、その特徴はインビジブルジャンクションと呼ばれ、対応する電子書類、ページ、見ている場所及び見ている領域を特定及び抽出することを可能にする。インビジブルジャンクションは、ノイズや表示状態によらない独立性や安定性をもたらし；問い合わせ画像及びモデル画像双方で反復可能であり；強い識別性をもたらし；低次元である。第２に、本発明は10000ページのデータベースで毎秒ほぼ４フレームという非常に速い速度で認識及び検索を行う。この認識及び検索は、リアルタイムのインタラクティブなアプリケーションに充分なほど速い。第３に本発明は、認識及び検索の際、カメラ付き携帯電話で取得されるような低品質の入力画像を利用できる。言い換えれば、画像の回転、スケール変更及び噛み合わせ(occlusions)によらず、検索は正確に行われる。第４に、本発明は東洋の及び西洋の言語の双方で認識及び検索を実行できる。第５に、本発明は、文字及び図形画像双方を含む入力画像について、テキストから画像に至るどの部分ででも、認識及び検索を実行できる。

システム実施例
図２を参照するに、本発明の一実施例により構築された特徴量抽出及び認識システム108の機能ブロック図が示されている。特徴量抽出及び認識システム108は、好ましくは、制御部250、ディスプレイ装置210、入力装置212、カーソル制御部214、通信装置216及び１つ以上の入力／出力(I/O)装置218を有する。

制御部250は、算術論理演算部、マイクロプロセッサ、汎用コンピュータ又は他の情報機器を有し、ディスプレイ装置210に電子表示信号を提供するように備えている。一実施例では、制御部250はグラフィックユーザインターフェース(GUI)を有する汎用コンピュータを有し、例えば、そのGUIはウインドウズ(登録商標)又はユニックス(登録商標)ベースのオペレーティングシステムのようなオペレーティングシステム上で動作するジャバ(Java(登録商標))で書かれたプログラムによって生成されてもよい。一実施例では、１つ以上のアプリケーションプログラムが制御部250によって実行され、そのアプリケーションプログラムは、限定ではないが、描画アプリケーション、ワードプロセシングアプリケーション、電子メールアプリケーション、財務アプリケーション及びウェブブラウザアプリケーション等を含む。

更に図２を参照するに、制御部250はプロセッサ202、メインメモリ204及びデータストレージ装置206を含むように示され、それら全てはシステムバス208に通信可能に結合されている。

プロセッサ202は、データ信号を処理し、様々なコンピュータアーキテクチャを備えていてもよく、コンピュータアーキテクチャは、複合命令セットコンピュータ(CISC)アーキテクチャ、縮小命令セットコンピュータ(RISC)アーキテクチャ又は組み合わせの命令セットを実現するアーキテクチャを含んでよい。図２には１つのプロセッサしか図示されていないが、複数のプロセッサが含まれてもよい。

メインメモリ204は、プロセッサ202で実行されてもよい命令及び／又はデータを格納する。命令及び／又はデータは、本願で説明される技法の全部又は何らかの一部分を実行するコードを有する。メインメモリ204は、ダイナミックランダムアクセスメモリ(RAM)装置、スタティックランダムアクセスメモリ(SRAM)装置、又は当該技術分野で既知の他のメモリ装置でもよい。メモリ204は図３に関連して更に詳細に説明される。

データストレージ装置206は、プロセッサ202用のデータ及び命令を格納し、１つ以上の装置を有する。１つ以上の装置は、ハードディスクドライブ、フロッピディスクドライブ、CD-ROM装置、DVD-ROM装置、DVD-RAM装置、DVD-RW装置、フラッシュメモリ装置又は当該技術分野で既知の他の大容量ストレージ装置等を含む。一実施例では、データストレージ装置206はデータベース110を含む。別の実施例では、データベースは特徴量抽出及び認識システム108に通信装置216及び信号線220（通常のネットワークを表す）を介して結合される。

システムバス208は、制御部250の中で情報及びデータを通信するための共有バスを表す。システムバス208は１つ以上のバスを表現し、その１つ以上のバスは、工業規格アーキテクチャ(ISA)バス、ペリフェラルコンポーネント相互接続(PCI)バス、ユニバーサルシリアルバス(USB)又は同様な機能を備えた当該技術分野で既知の他のバスを含む。システムバス208を介して制御部250に結合される追加的なコンポーネントは、ディスプレイ装置210、入力装置212、カーソル制御部214、通信装置216及びI/Oデバイス218を含む。

ディスプレイ装置210は、上述したような電子画像及びデータを表示するように用意された如何なる装置を表現してもよい。一実施例では、表示装置210は、液晶ディスプレイ(LCD)及び発光ダイオード(LED)であり、ステータスフィードバック、動作設定及び他の情報をユーザに与える。他の実施例では、ディスプレイ装置210は、例えば陰極線管(CRT)でもよいし、或いは表示装置、画面又はモニタを備えた同様な他の如何なるものでもよい。一実施例では、ディスプレイ装置210はタッチスクリーンを備え、及び／又はディジタイザを含み、接触式で感知する透明パネルがディスプレイ装置210の画面をカバーしている。

一実施例では入力装置212はキーパッドである。キーパッドはQWERTYキーパッド、キーのパッド、又はタッチスクリーン上でそのように表現されたものでもよい。カーソル制御部214はユーザ入力装置を表現し、位置データだけでなくコマンド選択内容もプロセッサ202に伝送するように備えられる。カーソル制御部214は、マウス、トラックボール、スタイラス、ペン、タッチスクリーン、カーソル指示キー、又はカーソルを動かす他の手段を含んでもよい。

通信装置216は、制御部250をネットワーク220に結合し、ネットワークは複数の処理システムを含み、一実施例ではネットワークコントローラである。処理システムのネットワークは、ローカルエリアネットワーク(LAN)、広域ネットワーク(WAN)（例えば、インターネット）及び／又は他の何らかの相互接続されたデータ経路(そのデータ経路で複数の装置が通信可能である)を含んでもよい。制御部250は、ネットワークのような他のシステムに対する他の通常の接続も有し、当業者に理解されるようなTCP/IP、http、https及びSMTPのような標準的なネットワークプロトコルを使ってファイル(メディアオブジェクト)を分配する。

I/Oデバイス218はバス208に結合される。これらのI/O装置は他のシステム(図示せず)の一部分でもよい。例えば、I/O装置218は、書類の画像を捕捉する画像スキャナを含んでもよい。I/O装置218も書類を生成するプリンタを含んでもよい。I/O装置218はオーディオ入力／出力装置を備え、マイクロホンを介して音声入力を受信し、スピーカを介して音声出力を送信してもよい。一実施例では、オーディオ装置は汎用のものでもよいし、汎用コンピュータシステム内で使用するように設計されたオーディオアドイン／拡張カードでもよい。選択的に、I/Oオーディオ装置は、１つ以上のアナログディジタル変換器又はディジタルアナログ変換器、及び／又は１つ以上のディジタル信号プロセッサを含み、オーディオ処理を行ってもよい。

特徴量抽出及び認識システム108は、本発明の精神及び範囲から逸脱せずに、図２に示されるものより多い又は少ない要素を含んでよいことが、当業者に明らかであろう。例えば、特徴量抽出及び認識システム108は、追加的なメモリ（例えば、第１又は第２レベルキャッシュ）又は１つ以上の特定用途向け集積回路(ASIC)を含んでもよい。更に、特徴量抽出及び認識システム108は、単独のバス208ではなく、複数のデータバスを含んでもよい。複数のバスは、特徴量抽出及び認識システム108の構成要素間の及び構成要素からの画像データを高速に転送することを可能にし、例えば、ディスプレイ装置へのユーザインターフェース情報の同時データ転送を可能にする。同様に、追加的な入力／出力装置218は制御部250に結合され、制御部はRFIDタグリーダ、ディジタルスチル若しくはビデオカメラ又は他の装置(制御部250に電子データをダウンロードする及び／又は取得するように備わっていてもいなくてもよい)を含む。１つ以上の要素は、キーボード及びカーソル制御部212のように省略されてもよい。

図３は特徴量抽出及び認識システム108のメモリユニット204の一例を示すブロック図である。メモリユニット204は、好ましくは、オペレーティングシステム302、アプリケーション304、制御モジュール306、ブラウザ308、特徴量抽出部310、特徴量インデキシング部312、特徴量検索部314及び幾何学的推定部316を有する。当業者は、メモリ204がバッファを含み、そのバッファは索引付け及び検索プロセスの際にデータ及び他の情報を一時的に格納することを認識するであろう。上述したように、メモリユニット204は、プロセッサ202で実行される命令及び／又はデータを格納する。命令及び／又はデータは、本願で説明される技法の全部又は何れかを実行するコードを有する。これらのモジュール302-314はバス208によりプロセッサ202に結合され、システム100と通信及び協同する。本発明はコンピュータのメモリユニット204の一部分として又はモジュールとして説明されるが、そのモジュール又は一部分は、永続的なデータストレージ装置206のような他の媒体に格納されてもよいし、クライアント／サーバ環境の場合のような複数のコンピュータを有するネットワーク220の中で分散されてもよいことを、当業者は認識するであろう。

オペレーティングシステム302は、好ましくは、カスタムオペレーティングシステムであり、アプリケーションインターフェースを介してユーザはそこにアクセス可能である。代替例では、オペレーティングシステム302は、ウインドウズ(登録商標)、ソラリス(登録商標)又はリナックス(登録商標)ベースのオペレーティングシステムのような通常のタイプのものでよい。

メモリユニット204は、１つ以上のアプリケーションプログラム304を含み、そのアプリケーションプログラムは、限定ではないが、描画アプリケーション、ワードプロセシングアプリケーション、電子メールアプリケーション、財務アプリケーション及びウェブブラウザアプリケーション等を含む。一実施例では、アプリケーション304は特にメモリ204の他のモジュール又はユニットに固有の機能を使用し、印刷された用紙及び対応する電子書類間のリンクをユーザが設定及び確認できるようにすることで、電子書類及び紙書類間のギャップを埋める（橋渡しを行う）。より具体的には、アプリケーション304は用紙からの電子データにアクセスし、及び電子データを用紙上の特定の場所に付随させ／埋め込み、ユーザが、上記の処理用のツールとしてのカメラを使って、その用紙からの電子データを後で検索できるようにする。例えば、あるアプリケーション304は、ユーザが単にウェブカムを指示し、指示された用紙の画像を捕捉したことに応答して、印刷された用紙の電子ファイル(マイクロソフトワード、アドビPDF等)を検索する。他のアプリケーション例304は、紙ベースのフォトwiki(paper-based photo-wiki)であり、物理的な用紙マップ上の所望の場所にカメラを単に指示することで、ユーザが撮影した像を用紙マップ上の特定の場所に付ける。これらには他の多くのアプリケーション304があり、そのアプリケーションは、例えば、書類データベースにアクセス又はブラウズする新規なユーザインターフェース、ディジタルペン及び用紙、マップナビゲータ、コピーのセキュリティ及びスキャナ、カメラゲーム、著作権保護用の重複検出等である。

制御モジュール306は、メモリ204の他のモジュールを制御するのに使用される。制御モジュール306は、アプリケーション304、ブラウザ308、特徴量抽出部310、特徴量インデキシング部312、特徴量検索部314及び幾何学的推定部316の制御を行い且つそれらとの通信を行うように合わせられている。制御モジュール306の動作は、図４及び６−９に関する以下の説明から明らかになるであろう。制御モジュール306はメモリ204の別個のモジュールとして示されているが、当業者は、別の実施例での制御モジュール306が他のモジュール310-316でのルーチンとして分散されてよいことを認識するであろう。

ブラウザ308は、マイクロソフト(登録商標)のインターネットエクスプローラ又はモジリアのファイヤフォックスのような通常のタイプのものでよい。ウェブブラウザはソフトウエアアプリケーションであり、そのソフトウエアアプリケーションは、文字、画像及び他の情報（典型的には、ローカルエリアネットワーク又はワールドワイドウェブのウェブサイトのウェブページにある）と共にユーザが表示及びやりとりすることを可能にし、 特徴量抽出部310は、紙書類のスキャンした画像及び元の電子書類からインビジブルジャンクションを取り出すソフトウエア及びルーチンである。一実施例では、特徴量抽出部310は、元の電子書類の受信に関連する入力機能と、特徴量記述を特徴量インデキシング部312に与える出力機能とを含む。他の実施例では、特徴量抽出部310は、紙書類の画像を受ける用結合された入力を含み、特徴記述を特徴量検索部314に与える。更に別の実施例では、特徴量抽出部310は、ロケーション判定モジュール、サイズ判定モジュール、方向判定モジュール及び記述子生成モジュールを含み、これらを組み合わせることで特徴量記述を生成する。特徴量抽出部310の動作は、図５Ａ−６を参照しながら以下で詳細に説明される。特徴量抽出部310は、特徴量インデキシング部312及び特徴量検索部314と通信するように結合される。

特徴量インデキシング部312は、インビジブルジャンクション特徴記述子の１つ以上のインデックスを生成し、それらをデータベース110に格納するためのソフトウエア及びルーチンである。一実施例では、特徴量インデキシング部312は量子化ツリーを使って特徴記述を索引付けする。特徴量インデキシング部312は、特徴量抽出部310の出力に結合され、インビジブルジャンクション特徴記述子を受ける。特徴量インデキシング部312はデータベース110に結合される。特徴量インデキシング部312の動作は、図７Ａ及び７Ｂを参照しながら以下で詳細に説明される。

特徴量検索部314は、紙書類のインビジブルジャンクション特徴記述子からクエリ(query)を作成し、データベース110と通信し、データベース110の中で合致する電子書類の表示領域、場所及び書類を検索するソフトウエア及びルーチンである。特徴量検索部314は、特徴量抽出部310の出力に結合されてインビジブルジャンクション特徴記述子を受信し、データベース110に結合され問い合わせを実行して結果を受信する。類似候補の書類、場所及び表示領域は、特徴量検索部314により出力される。特徴量検索部314の動作は図8を参照しながら以下で詳細に説明される。

幾何学的推定部316は、特徴量検索部314から出力された候補書類を分類し、ある幾何学的制約に合う特徴点を最大数含む書類を選択するソフトウエア及びルーチンである。幾何学的推定部316は、特徴量検索部314と通信するように適合させられ、入力画像パッチに合う視野、ポイント及び書類を与える出力を有する。幾何学的推定部316の動作は図９を参照しながら以下で詳細に説明される。

図４を参照するに、本発明の一実施例による特徴量抽出及び認識システム108の機能的なフローが示されている。特徴量抽出及び認識システム108は、２つの動作モードを有し；第1モードでは、オリジナルの電子書類が表示及び入力され、その入力からのインビジブルジャンクション特徴に関して、特徴インデックスが格納され；第２モードでは、画像パッチが入力され、特徴記述が作成され、その特徴記述を使って、対応する書類、場所及び表示領域を検索して出力する。説明の簡明化を図るため、上記の他の実施例と同じ又は同様な機能を有する要素について、同様な番号が使用される。システム108のこの第２の例は、特徴量抽出部310、特徴量インデキシング部312、特徴量検索部314及び幾何学的推定部316を含む。

図４は、特徴量抽出部310、特徴量インデキシング部312、特徴量検索部314及び幾何学的推定部316間の情報の流れを示す。特に、２つの動作モードが別個の組み合わせ420,430と共に示されている。例えば、第１モードは二重線420の経路と共に示され、元の電子書類402が表示され、信号線420を介して特徴量抽出部310に入力される。特徴量抽出部310は、その書類402のインビジブルジャンクションの特徴記述子を信号線402を介して特徴量インデキシング部312に出力し、特徴量インデキシング部312はインデックスを生成し、それらをデータベース110に格納する。第２モードは単一の線430の経路と共に示され、ビデオデータ又はビデオフレームのパッチ404が、信号線430を介して特徴量抽出部310に入力される。特徴量抽出部310は、そのビデオフレーム404内のインビジブルジャンクションの特徴記述子を、信号線430を介して特徴量検索部314に出力する。特徴量検索部314は、特徴記述子を用いて信号線430を介してデータベース110に問い合わせを行い、合致する特徴を有する書類のリストを信号線430を介して幾何学的推定部316に出力する。幾何学的推定部316は、幾何学的な制約を適用し、合致する書類、場所及び表示領域406を選択する。

インビジブルジャンクション特徴量
本発明は、書類パッチ認識に関する新たな特徴群を作成及び使用する。書類表現及び検索に使用される特徴点は、書類ページに存在する固有の骨組の分岐合流点(ジャンクション)である。これらのジャンクションは目に見えないので、即ち、テキスト書類の空白スペース内にある又は一様な色の領域内にあるので、我々はそれらを「インビジブルジャンクション」又は「インビジブルジャンクション特徴」と言及している。インビジブルジャンクション特徴には、４つの主要な成分がある：
ロケーション：特徴点の座標。書類ページの左上隅を原点とする。

方向：隣接する画素を使って各特徴点の記述を演算する際、各特徴点の局所的な座標系を設定するために使用される。

スケール：特徴の大きさ。

説明：特徴の内容。

特徴の内容は、これらの主要な成分(キーファクタ)全てによって決定されるので、それらを安定的に反復可能に持つことは重要である。認識を行うため、記述子(特徴記述)も識別可能でなければならない。

特徴量抽出
図５Ａ乃至５Ｄ及び図６を参照するに、特徴量抽出を行うプロセスの一例が示されている。プロセスは書類を受信すること602で始まる。一実施例では、特徴量抽出部310が、電子書類402の理想的なモデルを受信する602。別の実施例では、特徴量抽出部310は、電子書類402の理想的モデルを受信し602、そのモデルを画像として表現する。他の実施例では、特徴量抽出部310は、ビデオフレーム又はウェブカメラ画像404のような印刷書類の捕捉画像を受信する602。

次にプロセスは、１つ以上のインビジブルジャンクションの場所を判定する604。一実施例では、特徴量抽出部310は、テキスト書類の骨組みの分岐合流点で特徴を検出する。本実施例に関し、図５Ａ及び５Ｂに示されるように、特徴量抽出部310は、入力画像を２値化し、２値画像に距離変換を適用する。入力画像501の例の場合、入力画像501を２値化したもの502及び２値化されたものの距離変換503が、図５Ａに示されている。次の骨組み(スケルトン)504は、距離変換によるラベルフィールドの境界として検出される。スケルトン504は代替的に、距離フィールドの尾根線(ridge line)でもよい。一実施例では、尾根線は、一次元の中で局所的な最大値として検出される。例えば図５Ａの入力例に関し、距離変換503及びスケルトン504が図５Ｂに示されている。この特徴は、図５Ｂに示されるようなジャンクション点506として検出される。ジャンクション点506は、代替的に、距離変換フィールドの(２Ｄにおける)極大値又はスケルトン504での極大値でもよい。インビジブルジャンクションを利用することは、それらが安定的で反復可能なので特に有利である。文字書類は、テキスト中に大抵は高周波の画像成分(high frequency image content)を含み、その画像成分は容易に汚染され、テキストを劣化させずに選別することは困難である。これに対して、テキストページ中の白色空間は殆ど安定的であり、周波数領域で殆どＤＣである成分を含む。白色空間中のノイズは、特徴的な場所に影響を及ぼさずに容易に選別できる。テキストの内容は最終的には分類に使用されるので、距離変換フィールドは、望まれているテキストの場所に依存するが、インビジブルジャンクション点506の場所は、各ジャンクション付近のテキストは通常同じように汚れるので、ノイズに対して堅牢(ロバスト的)である。

本プロセスは次に、そのインビジブルジャンクションについてジャンクションのサイズ又はスケールを判定するステップに進む（606）。一実施例では、各特徴点506での距離変換値は、特徴点506に固有である。従って特徴点506のスケールは、因子αを乗算したそのような距離値として割り当てられる。図５Ｃで拡大図512に示されるように、この例の場合、αは２に等しいように選択される。円510の内側の内容（円は、特徴点506を中心とし、スケールに等しい半径を有する円である）は、カメラの面内回転及びズーム（又は、カメラの光軸が紙に垂直な場合、紙書類までの距離）に対して不変である。この特徴は局所的(ローカル)なので、即ち、円は小さいので、この特徴も、用紙に対するカメラの視野角の変化（面外回転）に対して堅牢である。言い換えれば、全体的な投影歪みが生じても、そのような投影歪みはローカルには非常に小さく、最終的な特徴記述子に及ぶ影響は、広範囲に亘るカメラの面外回転に関して無視できる。位置と同様に、インビジブルジャンクションのスケールも安定的で反復可能である。スケールは、スケルトンに基づいて計算され、それ故に安定的になる。しかしながら、位置及び方向と比較すると、スケールは、大抵テキスト付近の変化の影響を受ける。一実施例では、この影響は、特徴記述子を計算する際に、距離に逆比例する重み(ウエイト)を適用することで軽減される。

次に、プロセスはインビジブルジャンクション506の向きを判定する608。一実施例では、各特徴点506にはローカルな向きが割り当てられている。各特徴点506に関する２次元ローカル座標系は、特徴点を原点とし、ローカルな向きをｘ軸とするように決定される。特徴記述子は、このローカルな座標系に基づいて計算される。ローカルな向きを導出するため、特徴量抽出部310は、特徴点506を中心とし、その特徴スケールで決定される半径の円511を計算する。円511は、いくつかの位置でスケルトンと交わる。（スケルトンと交わる円周上の点全てのペアの中で）最も離れた２つの交点の位置が、この特徴のローカルな向きを決める。同様な距離の位置ペアが２つあった場合、特徴量抽出部310は、より水平方向に近いものを選択する。図５Ｄは特徴方向の判定例を示す。特徴点506を中心として特徴スケールに等しい半径を有する円511は、スケルトン504と３つの点Ａ，Ｂ及びＣと交わる。２つの点Ａ，Ｂが最も長い距離を有し、従って特徴方向は、線分ＡＢの向きに割り当てられる。ローカルな向きは、ノイズに敏感であり、いくつかの向きは異常値にさえなるかもしれないので、特徴量抽出部310は、グローバルな向き(global orientation)の推定を利用する。特に、ローカル方向を伴う特徴点は、問い合わせ画像についてグローバルな向きを表明している。この表明（投票）は、ローカルな特徴方向の数を360ビン（各ビンにつき１度）にわたって計数することで行われる。向きのヒストグラムの大勢は、グローバル方向として選択される。投票の後、全特徴点は、選択されたグローバルな向きに一致した向きに割り当て直される。一実施例では、ヒストグラムについて数を数える際、特徴量抽出部310はソフトスプリット法を使用し、ノイズで乱される場合でもヒストグラムが円滑に変化することを保証する。

テキストパッチの場合、グローバル方向は安定的である。なぜなら他のほとんどの非テキスト書類についても正しい書類方向が存在するからである。本発明は、純粋にローカルな方向と純粋にグローバルな方向との間でトレードオフを行うように調整を行う。具体的には、各特徴点について、特徴量抽出部310は近隣から向きを収集し（同じ画像中の全ての特徴点からのものと比較しながら）、方向を決定する。これは、日本語や中国語のような言語で、書類ページが縦及び横の文字列双方を含むかもしれない問題を解決する。

ジャンクションの向きはスケルトンによって決定され、スケルトンは上述したように安定的であり、従ってジャンクションの向きも安定的になる。この点、従来のSIFTと対照的であり、SIFTの場合、ローカルな方向は、特徴点周辺の画素の階調度又は輝度変化(gradient)によって決定されている。階調度の方向はノイズを増幅し、それ故に特徴点をノイズに敏感にしてしまうことが良く知られている。本願のローカル方向は、スケルトンから導出され、それよりも充分に安定的である。グローバル投票ステップは、特徴点を更に安定的なものにする。なぜなら、カメラは平坦なページを見ていること、及びそのようなページは不可視の骨組(インビジブルスケルトン)の中で何らかの支配的な方向を有すること、という性質を活用しているからである。

次に、プロセスはインビジブルジャンクションに関する記述子又は特徴記述を作成する610。図５Ｅも参照するに、場所、スケール及び方向が或る特徴についていったん決定されると、特徴量抽出部310は各特徴点506について二次元座標枠516を割り当て、その座標枠516内で記述子518を算出する。各々の特徴について、特徴量抽出部310は、特徴スケールの２倍に等しいエッジ長さの正方形を算出する。この正方形は４×４のセルに分割される。代替実施例では、特徴量抽出部310は、これらのセルを構築するために同心円を利用することができる。各セルの中で、特徴量抽出部310は、８つのビン（即ち、８つの方向）を有する重み付けされた階調度方向のヒストグラムを累積する。ロバート又はソベル演算子(Robert or Sobel operator)を含むいくつかの技法によって階調度は算出可能である。特徴記述子は、そのような方向ヒストグラムの連結であり、128次元の特徴ベクトルになる。特徴ベクトルは、線形な輝度変化に対処できるように規格化される。

一実施例では、特徴量抽出部310は、主成分分析(PCA)を用いる次元低減法を適用し、最初の14次元を確保する。これはその特徴の識別力を減らすかもしれないが、ノイズを減らすことに寄与する。本実施例では、中心付近のセルは殆ど空白なので、次元の削減は更に有意義である。目下の例では各クラスについて唯１つのプロトタイプしか存在しないことを考えると、有利なことに、これは、固有に低次元の特徴点をもたらす。本発明の記述子は、識別可能であって反復可能な点で、特に有利である。この反復可能性は、特徴の場所、方向及びスケールの反復可能性の結果である。理解できるように、各特徴点の中身は、テキスト文書中の３つ以上の言葉からの画素を含む。異なる言葉からのこれらの中身(コンテンツ)は、或る特殊なレイアウトで共に配置され、その識別子を非常に顕著にする。なぜなら、そのような特徴点にとって、同じレイアウトで共に配置された同様な言葉と、他の場所で重複する機会はめったにないからである。量子化（４×４セルおよび８方向）も特徴記述子をノイズに対して堅牢にする。

最後にプロセスは書類中に更に多くのインビジブルジャンクションが有るか否かを確認する612。存在した場合、本方法は未処理のジャンクションを選択し、それを処理するためにステップ604に続く。それ以上のインビジブルジャンクションが無かった場合、書類の処理は完了し、終了する。

特徴量インデキシング
上述したように、特徴量インデキシング部312は、インビジブルジャンクション特徴記述子の１つ以上のインデックスを生成し、それらをデータベース110に格納する。モデル画像各々について、特徴量インデキシング部312は、特徴点を取り出し、それらをデータベース110に格納する。特徴量インデキシング部312は、各特徴点に関連するメタデータも格納し、メタデータは、その特徴点を含む書類ページの固有のID、特徴記述子、スケール、方向及び場所(x,y)を含む。高速なリアルタイムの照合及び抽出を可能にするため、特徴量インデキシング部312は、効率的な格納及びデータベースからの効率的な抽出に備えてこれらのデータを索引付けする。

図７Ａを参照するに、本発明による特徴量インデキシングを行う方法例が示されている。プロセスは量子化ツリーを作成することで始まる702。一実施例では、量子化ツリーは、階層的なクラスタリングを行って一群のトレーニング特徴（トレーニングセット）によって慣らされる。そのトレーニングセットはＫ個のクラスタに再帰的に分割される。Ｋ個の分岐(ブランチ)及びＬ個のレベルを伴う量子化ツリーの場合、Ｋ^Ｌ個のリーフノードが有り、即ちボキャブラリ(vocabulary)サイズはＫ^Ｌである。特徴をクラスタリングする場合、特徴量インデキシング部312は、複数のランダム初期化と共にk-meansアルゴリズムを使用する。ツリーの各ノードにおいて、特徴量インデキシング部312は、そのノードに属する点（ポイント）によって与えられるクラスタ中心を記録する。量子化ツリーの各ノードは、用語−頻度−逆−書類−頻度(term-frequency-inverse-document-frequency)を使って、あるノードにも関連付けられる。量子化ツリーは、階層的な方法で特徴空間を区分けする。いったん量子化ツリーが作成されると、それはデータベース110に格納される704。次に、特徴点が特徴量抽出部310から抽出され又は受信され706、ツリーを押し下げ、データベースに加えられる708。ツリーの各レベルにて、特徴点は、その特徴点に最も近いクラスタ中心を伴うブランチを選択する。特徴点がリーフノードに達すると、その特徴点に関するエントリがそのリーフノードのヒットリストに挿入され、その特徴点の座標(x,y)及びページIDを記録する。そのページIDがヒットリスト中に既に存在していた場合、特徴量インデキシング部312はその作法を既存のエントリに付随させ、ヒットリストにおけるそのページIDの出現頻度をインクリメントする。特徴点は２つのクラスタ間の境界にある又は境界近傍にあるかもしれないので、特徴量インデキシング部312は、特徴点を量子化ツリーに押し込む際にソフトスプリット(soft split)を使用する。しかしながら、これは、そのような特徴点によってヒットするリーフノードの数が多くなってしまう。トレードオフとして、特徴量インデキシング部312は、特徴点を、最も近いｋ個（目下の例の場合、ｋ＝２）のリーフノードだけに挿入する。

他の実施例では、特徴量インデキシング部312は、元の特徴記述子を格納しない。いったん特徴量インデキシング部312が特徴空間を量子化すると、特徴量インデキシング部312は、量子か空間内にあるセルのインデックスで特徴記述子を近似する。各フレームについて、特徴量インデキシング部312は書類ページIDのみを格納し、書類ページIDは、その特徴に加えて、書類ページ内の特徴の座標も含む。従って、必要な格納スペースは顕著に減少する。

図７Ｂを参照するに、特徴量インデキシングを行う本発明による別の方法例が示されている。本実施例では、特徴量インデキシング部312は通常のk-dツリーを使用して、特徴点を組織化する722。他の実施例では、通常のk-dツリーは、高速ディスクI/O用に拡張されたk-dツリーに修正されてもよい。k-dツリーは、特徴点を複数のセルに分割し、各セルは１つ以上の特徴点（実際には、特徴点を指すポインタ）を含んでいる。k-最近接サーチ(k-nearest neighbor search)を行う際、ツリーを逆に辿ることがしばしば必要になる。特徴量インデキシング部312は、ツリーの深度優先線形化(depth-first linearization)を利用して、特徴点を順序付ける；逆に辿る際に、メモリ／ディスクの場所が保存される方法で行われる。その結果として、キャッシュミス率が減り（その特徴がメインメモリ内に或る場合、キャッシュはCPUキャッシュでもよいし、或いは特徴が外部ハードディスクドライブ内にある場合、キャッシュはメモリキャッシュでもよい）、速度性能が向上する。そして、特徴量インデキシング部312はPCAを利用して、特徴の次元を減らし724、或いはより正確には、有用な次元数を発見する。我々のデータが本来的に低次元であったとしても、その低次元の空間は、結果のk-dツリーが良好にバランスをとるように推定される必要がある。そのような次元削減の有用性は、低次元の要請に合うだけでなく、空間分割が最も効率的になるような方法で特徴次元をも要求する。言い換えれば、殆どのエネルギを伴う次元が先ず削減されるような方法で空間削減が要求され726、システム108はあるk-dツリーに至ることができ、そのツリーは、バランスがとれているだけでなく、安定的なセル境界を伴うものでもある（即ち、ノイズが小さければ、特徴が属すべきセル内を乱さない。）。

特徴量抽出及び幾何学的推定
図８を参照するに、本発明による特徴量抽出の方法例が示されている。

図７Ａに関して説明された第１の例に従って索引付け(インデキシング)が行われる場合、特徴量検索部314は、問い合わせ画像の中で検出された特徴点を量子化に至るまで送信し、リーフノードでヒットリストを収集する。これは、各候補ページについての座標(x,y)のリストと共に書類ページ候補のテーブルを生成する。これは更なる処理に備えて幾何学的推定部に送信可能である。

図７Ｂでのインデキシングの代替例では、検索プロセスは、特徴量検索部314が特徴量抽出部310から特徴記述子を受信することで始まる802。特徴量検索部314は、ローカル特徴に基づいてパターン認識を実行する。特徴量検索部314はあるページ書類を探し、そのページ書類の特徴点は、所与の問い合わせ画像パッチの特徴点に最良に対応するものである。その対応関係を確立するため（即ち、認識するため）、特徴量検索部314は、所与の画像の中で各特徴点を認識する。より具体的には、特徴量検索部314は、問い合わせ画像におけるｋ個の最近接の(kNN: k nearest neighbors)特徴点を求めてデータベース110を探す。データベース中のそのような点全体の集まりは、複数の群(セット)に分割され806、ある群中の点は同じ書類ページIDを共有する(IDは、その特徴点を伴うメタデータとしてデータベースに記録される)。書類ページの候補各々について、特徴量検索部314は、一群の特徴対応物を生成する。そのような多くの対応物は飛び値になることに留意を要する（各問い合わせ点に関し、最近接のｋ個の中で高々１つの真の対応物しか存在しないからである。）。

当業者は、様々なｋの値が使用可能なことを認識するであろう。一実施例では、k=10である。他の値のｋが、問い合わせ時間を短縮するために使用されてもよい。代替方法は、問い合わせ特徴と現在の近辺との間の距離もモニタする。その距離に大きな飛躍があった場合、特徴量検索部314は、k<10個の近辺に戻り、その場合の近隣はおそらくは飛び値になる（即ち、真の対応物はおそらく現在のｋ＜10個の点の中にある。）。

更に別の実施例では、特徴量検索部314は、ツリー交差(tree intersection)を用いるスコアリングを行う。問い合わせ画像の各々について、特徴量検索部314は、問い合わせの点が出て行くパスを与えるツリー表現を有する。特徴量検索部314は、候補ページ各々について同様なツリーを構築する。問い合わせ画像とモデル画像の類似性は、２つのツリーの交差に基づいて算出される。その後にツリー交差がランキングされる。

図９は、幾何学的推定を行う本発明による方法例のフローチャートである。全ての候補ページの身元が特徴量検索部314で確認されると、候補は幾何学的推定部に伝送され、書類ページ候補全ての身元を格付け（ランキング）し、最終的な問い合わせ結果を生成する。各候補ページ書類が持っている特徴点の数を利用して、候補書類を分類することで、幾何学的推定部316は処理を始める902。幾何学的推定部316は、幾何学的な制約を使ってその候補をランキングする。例えば、幾何学的推定部316はある書類を選択し、その書類は、入力された画像面の幾何学的制約に合う特徴点を最多数含んでいる。従って、紙面とカメラ画像面との間に或る変換が存在する。最終的に、幾何学的推定部316は合致する書類の身元、ページ、ポイント及び表示領域を出力する906。

以上、本発明の実施例の説明が例示及び記述の観点からなされてきた。説明が網羅的なものであることを意図してはおらず、説明された厳密な形式に本発明を限定する意図でもない。多くの修正及び変形が上記の教示内容に照らして可能である。本発明はこの詳細な説明によっては限定されず、本願の特許請求の範囲によって規定される。当業者に理解されるように、本発明は、その本質的特徴又は精神から逸脱せずに、他の特定の形態に具現化されてもよい。同様に、モジュール、ルーチン、特徴、属性、方法及び他の性質に関する特手の名称や区分けは、必須でも重要でもなく、本発明又はその特徴を実現する手段は、別の名称、区分け及び／又は形式をとってもよい。更に、当業者に明白なように、モジュール、ルーチン、特徴、属性、方法及び他の本発明の性質は、ソフトウエア、ハードウエア若しくはファームウエアによって、又はそれらの如何なる組み合わせによって実現されてもよい。例えばモジュールであるコンポーネントがソフトウエアとして実現される場合はいつでも、そのコンポーネントは、スタンドアローンプログラムとして、大規模なプログラムの一部分として、複数の別々のプログラムとして、静的に又は動的にリンクしたライブラリとして、カーネルローダブルモジュールとして、デバイスドライバとして実現されてもよいし、及び／又は、コンピュータプログラミングの技術分野の当業者にとって現在既知の若しくは将来既知になる何らかの他の方法で実現されてもよい。更に、本発明は、何らかの特定のプログラミング言語で実現されることに限定されず、何らかの特定のオペレーティングシステムや環境で実現されることにも限定されない。従って、本発明の開示内容は例示的であり、本発明の範囲を限定するものでもなく、本発明は特許請求の範囲の記載によって規定される。

特徴量抽出及び認識を行う本発明によるシステムの機能を示す図である。 本発明の一実施例により構築されたシステム例の機能を示す図である。 本発明の一実施例により構築された図２のシステム例のメモリに関するブロック図である。 本発明による図１の特徴量抽出及び認識システム例のブロック図である。 ある画像例で実行される本発明の一実施例による特徴量抽出ステップの図式表現を示す図である。 ある画像例で実行される本発明の一実施例による特徴量抽出ステップの図式表現を示す図である。 ある画像例で実行される本発明の一実施例による特徴量抽出ステップの図式表現を示す図である。 ある画像例で実行される本発明の一実施例による特徴量抽出ステップの図式表現を示す図である。 ある画像例で実行される本発明の一実施例による特徴量抽出ステップの図式表現を示す図である。 特徴量抽出を行う本発明による方法例のフローチャートである。 特徴量インデキシングを行う本発明による方法例のフローチャートである。 特徴量インデキシングを行う本発明による別の方法例のフローチャートである。 本発明による特徴量抽出方法例のフローチャートである。 幾何学的推定を行う本発明による方法例のフローチャートである。

符号の説明

１００ システム
１０２ 印刷された又は紙の書類
１０４ 紙書類の元の領域
１０６ 画像捕捉装置
１０８ 特徴量抽出及び認識システム
１１０ データベース
１１２ 電子表現
１１４ 対応関係を表す線
２０４ メモリユニット
２１０ ディスプレイ装置
２１２ 入力装置
２１４ カーソル制御部
２１６ 通信装置
２１８ 入力／出力(I/O)装置
２５０ 制御部
３０２ オペレーティングシステム
３０４ アプリケーション
３０６ 制御モジュール
３０８ ブラウザ
３１０ 特徴量抽出部
３１２ 特徴量インデキシング部
３１４ 特徴量検索部
３１６ 幾何学的推定部

Claims (35)

1. インビジブルジャンクションを生成する方法であって、
   電子書類の画像を受信するステップと、
   前記画像からインビジブルジャンクションを決定するステップと、
   前記インビジブルジャンクションの特著記述子を生成するステップと、
   を有し、前記決定するステップは、複数のインビジブルジャンクションについて実行され、
   前記生成するステップは、複数の特徴記述子を生成するようにした方法。
2. 前記画像からインビジブルジャンクションを決定するステップは、ジャンクションの位置及びサイズを決定するステップを含み、
   前記特徴記述子は、前記ジャンクションの位置及びサイズを含む
   ようにした請求項１記載の方法。
3. 前記画像からインビジブルジャンクションを決定するステップは、ジャンクションの向きを決定するステップを含み、
   前記特徴記述子は、前記ジャンクションの向きを含む
   ようにした請求項１記載の方法。
4. 前記画像からインビジブルジャンクションを決定するステップは、
   ２値画像を生成するため、前記画像を２値化するステップと、
   距離変換を行うため、前記２値画像に距離変換を適用するステップと、
   前記距離変換されたものの骨組を検出するステップと、
   前記骨組の中のジャンクション点を前記インビジブルジャンクションとして決定するステップと、
   を有する請求項１記載の方法。
5. インビジブルジャンクションを生成及び格納する方法であって、
   電子書類の画像を受信するステップと、
   前記画像からインビジブルジャンクション特徴記述子を抽出するステップと、
   前記インビジブルジャンクション特徴記述子から特徴インデックスを生成するステップと、
   前記特徴インデックスを格納するステップと、
   を有する方法。
6. 前記画像からインビジブルジャンクション特徴記述子を抽出するステップが、
   前記画像からインビジブルジャンクションを決定するステップと、
   前記インビジブルジャンクションについて前記インビジブルジャンクション特徴記述子を生成するステップと、
   を有する請求項５記載の方法。
7. 前記特徴インデックスを格納するステップが、前記特徴インデックス及び前記特徴記述子をデータベースに格納するステップを有する請求項５記載の方法。
8. 前記インビジブルジャンクション特徴記述子から特徴インデックスを生成するステップが、
   量子化ツリーを生成するステップと、
   前記インビジブルジャンクション特徴記述子について特徴点を前記量子化ツリーに付加するステップと、
   を有する請求項５記載の方法。
9. 追加的なインビジブルジャンクション特徴記述子を抽出するステップと、
   前記追加的なインビジブルジャンクション特徴記述子について第２の特徴点を前記量子化ツリーに付加するステップと、
   を有する請求項８記載の方法。
10. 前記量子化ツリーが、階層的なクラスタリングを用いて一群のトレーニング特徴によって整えられる請求項９記載の方法。
11. 前記特徴点のページID及び座標(x,y)を含むリーフノードを付加することで、前記特徴点が前記量子化ツリーに付加される請求項９記載の方法。
12. 前記インビジブルジャンクション特徴記述子から特徴インデックスを生成するステップが、
    前記特徴点をk-dツリーに組織化するステップと、
    主要成分分析を使って特徴次元を減らすステップと、
    前記k-dツリーを効果的に分けるように前記特徴次元を整理するステップと、
    を有する請求項５記載の方法。
13. インビジブルジャンクションを使用して電子書類を抽出する方法であって、
    入力電子書類の画像を受信するステップと、
    前記画像からインビジブルジャンクション特徴記述子を抽出するステップと、
    前記インビジブルジャンクション特徴記述子を用いて出力電子書類を検索するステップと、
    を有する方法。
14. 出力電子書類を検索するステップが、
    前記インビジブルジャンクション特徴記述子を使用して、複数の出力電子書類を検索するステップと、
    前記出力電子書類として、複数の出力電子書類の何れかを幾何学的制約を使って選択するステップと、
    を有する請求項１３記載の方法。
15. 出力電子書類を検索するステップが、前記インビジブルジャンクション特徴記述子を使用してデータベースに問い合わせを行うステップを有する請求項１３記載の方法。
16. 出力電子書類を検索するステップが、
    前記特徴記述子を検索するステップと、
    前記特徴記述子の特徴点についてｋ個の近接点を検索するステップと、
    検索された近接点を、それらの対応する書類の身元で組織化するステップと、
    を有する請求項１３記載の方法。
17. 複数の出力電子書類の何れかを選択するステップが、
    各書類中の特徴点数に基づいて前記複数の出力電子書類を分類するステップと、
    格納済みの前記複数の出力電子書類を幾何学的制約を使用してランク付けするステップと、
    最高のランクを伴う電子書類を出力するステップと、
    を有する請求項１４記載の方法。
18. 電子書類の出力は、前記最高ランクを伴う電子書類の書類識別子、場所及び表示領域を出力することを含む請求項１４記載の方法。
19. インビジブルジャンクションを生成するシステムであって、
    入力及び出力を有し、画像からインビジブルジャンクションを決定する特徴決定部であって、該特徴決定部の前記入力は電子書類の画像を受信するように結合されている特徴決定部と、
    入力及び出力を有し、前記インビジブルジャンクションの特徴記述子を生成する記述子生成部であって、前記入力は、前記特徴決定部の前記出力に結合され、前記インビジブルジャンクションの情報を受信し、該記述子生成部の出力は、前記特徴記述子を提供するようにした記述子生成部と、
    を有するシステム。
20. 特徴記述子を格納するデータベースを更に有し、前記記述子生成部の前記出力は前記データベースに結合されている請求項１９記載のシステム。
21. 前記特徴決定部は、入力及び出力を有し、ジャンクションの位置を決定するロケーション決定モジュールを有し、該ロケーション決定モジュールの前記入力は、前記電子書類の前記画像を受信するように結合され、前記ロケーション決定モジュールの前記出力は、前記記述子生成部の前記入力に結合されるようにした請求項１９記載のシステム。
22. 前記特徴決定部は、入力及び出力を有し、ジャンクションのサイズを決定するサイズ決定モジュールを有し、該サイズ決定モジュールの前記入力は、前記ジャンクションの位置を受信するように前記ロケーション決定モジュールの前記出力に結合され、前記サイズ決定モジュールの前記出力は、前記記述子生成部の前記入力に結合されるようにした請求項２１記載のシステム。
23. 前記特徴決定部は、入力及び出力を有し、ジャンクションの方向を決定する方向決定モジュールを有し、該方向決定モジュールの前記入力は、前記ジャンクションのサイズを受信するように前記サイズ決定モジュールの前記出力に結合され、前記方向決定モジュールの前記出力は、前記記述子生成部の前記入力に結合されるようにした請求項２２記載のシステム。
24. 入力及び出力を有し、画像からインビジブルジャンクション特徴記述子を生成する特徴量抽出部であって、該特徴量抽出部の前記入力は、電子書類の前記画像を受信するように結合されている特徴量抽出部と、
    入力及び出力を有し、前記インビジブルジャンクションの特徴インデックスを生成する特徴量インデキシング部であって、該特徴量インデキシング部の前記入力は、前記特徴量抽出部の前記出力に結合され、前記インビジブルジャンクション特徴記述子を受信し、前記特徴量インデキシング部の前記出力は前記特徴インデックスを提供する特徴量インデキシング部と、
    を更に有する請求項１９記載のシステム。
25. 入力及び出力を有し、ジャンクションの位置を決定するロケーション決定モジュールであって、該ロケーション決定モジュールの前記入力は、前記電子書類の前記画像を受信するように結合されたロケーション決定モジュールと、
    入力及び出力を有し、ジャンクションのサイズを決定するサイズ決定モジュールであって、該サイズ決定モジュールの前記入力は、前記ジャンクションの位置を受信するように前記ロケーション決定モジュールの前記出力に結合されたサイズ決定モジュールと、
    入力及び出力を有し、ジャンクションの方向を決定する方向決定モジュールであって、該方向決定モジュールの前記入力は、前記ジャンクションのサイズを受信するように前記サイズ決定モジュールの前記出力に結合された方向決定モジュールと、
    を前記特徴量抽出部が備え、前記特徴量抽出部は、前記ジャンクションの位置、ジャンクションのサイズ及びジャンクションの方向を提供するように前記特徴量インデキシング部に結合されている請求項２４記載のシステム。
26. 前記特徴量インデキシング部は、前記インビジブルジャンクション特徴記述子も提供する請求項２２記載のシステム。
27. 前記特徴量インデキシング部は、量子化ツリーを生成し、前記インビジブルジャンクション特徴記述子について特徴点を前記量子化ツリーに付加する請求項２２記載のシステム。
28. 前記特徴点のページID及び座標(x,y)を含むリーフノードを付加することで、前記特徴量インデキシング部が、前記特徴点を付加する請求項２７記載のシステム。
29. 前記特徴記述子が特徴点を含み、前記特徴量インデキシング部は、前記特徴点をk-dツリーに組織化し、主要成分分析を使って前記k-dツリーの特徴次元を減らし、前記k-dツリーを効果的に分けるように前記特徴次元を整理するようにした請求項２２記載のシステム。
30. 電子書類をインビジブルジャンクション特徴を使用して抽出するシステムであって、
    入力及び出力を有し、画像からインビジブルジャンクション特徴記述子を生成する特徴量抽出部であって、該特徴量抽出部の前記入力は入力画像を受信するように結合されている特徴量抽出部と、
    入力及び出力を有し、前記インビジブルジャンクション特徴記述子を用いて出力電子書類を検索する特徴量検索部であって、前記特徴量検索部の前記入力は前記特徴量抽出部の前記出力に結合され、前記特徴量検索部の前記出力は出力電子書類の情報を提供するようにした特徴量検索部と、
    を有するシステム。
31. 複数のインビジブルジャンクション特徴記述子及び出力電子書類に対応する情報を格納するデータベースを更に有し、前記特徴量検索部の前記出力は前記データベースに結合されている請求項３０記載のシステム。
32. 前記特徴量検索部は、前記インビジブルジャンクション特徴記述子を用いて複数の出力電子書類を検索し、前記出力電子書類として、前記複数の出力電子書類の何れかを幾何学的制約を用いて選択するようにした請求項３０記載のシステム。
33. 前記特徴量検索部は、前記特徴記述子の特徴についてｋ個の近接点を検索し、検索された特徴点をそれらの対応する書類識別子で組織化する請求項３０記載のシステム。
34. 前記特徴量検索部が、各書類中の特徴点数に基づいて前記複数の出力電子書類を分類し、格納済みの前記複数の出力電子書類を幾何学的制約を使用してランク付けし、最高のランクを伴う電子書類を出力するようにした請求項３２記載のシステム。
35. 前記電子書類の情報は、前記出力電子書類の書類識別子、場所、表示領域及び電子バージョンを含む請求項３２記載のシステム。