(57)【特許請求の範囲】
【請求項１】
画像を処理するための方法（１００）であって、
１組の主要点を前記画像から提供するステップ（１００）と、
前記１組の主要点の位置情報を二値行列の形で記述するステップ（１０３）と、
前記二値行列を所定の順序に従って走査することによって、前記１組の主要点の前記位置情報の新規表現を生成するステップ（１０５）と、
を含み、
前記１組の主要点の位置情報の前記新規表現は別の二値行列（４０２）の形態をとり、
前記別の二値行列（４０２）は様々なサイズのマクロブロックに分割され、前記画像の関心領域またはその周囲に配置された主要点の位置情報を有するマクロブロックのサイズは、前記画像の外縁に位置する主要点の位置情報を有するマクロブロックよりも大きい、
方法（１００）。
【請求項２】
前記二値行列を所定の順序に従って走査するステップ（１０５）は、
前記二値行列を、前記画像の関心領域またはその周囲に配置された主要点から開始して前記画像の外縁に位置する主要点に向かって走査するか、または、前記画像の外縁に位置する主要点から開始して前記画像の関心領域またはその周囲に配置された主要点に向かって走査するステップ（１０５）と、
を含む、請求項１に記載の方法（１００）。
【請求項３】
前記画像の前記関心領域は前記画像の中心にあるかまたは前記画像の中心の周囲にある、請求項２に記載の方法（１００）。
【請求項４】
前記二値行列（４０１）を走査するステップ（１０５）は反時計回りまたは時計回りに実施される、請求項１乃至３の何れか１項に記載の方法（１００）。
【請求項５】
前記二値行列（４０１）を走査するステップ（１０５）は同心円環内の部分で実行される、請求項１乃至４の何れか１項に記載の方法（１００）。
【請求項６】
前記別の二値行列（４０２）は、前記別の二値行列の要素を列方向または行方向に埋めることによって生成される、請求項１に記載の方法（１００）。
【請求項７】
前記１組の主要点の主要点ごとに、記述子が前記主要点を囲む有向パッチから計算される、請求項６に記載の方法（１００）。
【請求項８】
前記二値行列は空セルと非空セルから成るヒストグラム・マップであり、非空セルは前記画像における主要点の位置を表す、請求項６または７の何れか１項に記載の方法（１００）。
【請求項９】
前記１組の主要点の位置情報の前記新規表現を圧縮するステップをさらに含む、請求項６乃至８の何れか１項に記載の方法（１００）。
【請求項１０】
前記１組の主要点の位置情報の前記新規表現を圧縮するステップは、
位置情報を有しない前記二値行列の外縁部を排除することによって前記二値行列のサイズを縮小するステップ（２１１）であって、前記縮小するステップ（２１１）は前記二値行列を走査するステップ（１０５、２１２）の前に実施されるステップ
を含む、請求項９に記載の方法（１００）。
【請求項１１】
前記１組の主要点の位置情報の前記新規表現を圧縮するステップは、
非空値を有さない前記二値行列の同心円環に対応する前記別の二値行列の空要素を排除するステップ（２１３）
を含む、請求項９に記載の方法（１００）。
【請求項１２】
エントロピ符号化が、前記別の二値行列（４０２、２１２）のｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋ情報（２１６）に適用され、前記エントロピ符号化が前記別の二値行列（４０２、２１２）の非空マクロブロック（２１７）にも適用される、請求項１に記載の方法（１００）。
【請求項１３】
エントロピ符号化を適用するときにコンテキスト生成（２１５）を適用する、請求項１２に記載の方法（１００）。
【請求項１４】
画像の局所的特徴を前記画像の１組の主要点の位置情報の行列表現から再構築するための方法（１０００）であって、
前記画像の前記１組の主要点の位置情報の前記行列表現を所定の順序に従って解凍するステップ（１００１）であって、前記画像の前記局所的特徴は前記主要点を囲む有向パッチから計算されるステップ
を含み、
前記行列表現は、
１組の主要点を画像から提供し（１０１）、
前記１組の主要点の位置情報を二値行列の形で記述し（１０３）、
前記二値行列を所定の順序に従って走査することによって、前記１組の主要点の前記位置情報の新規表現を生成する（１０５）
ことによって生成され、
前記１組の主要点の位置情報の前記新規表現は別の二値行列（４０２）の形態をとり、
前記別の二値行列（４０２）は様々なサイズのマクロブロックに分割され、前記画像の関心領域またはその周囲に配置された主要点の位置情報を有するマクロブロックのサイズは、前記画像の外縁に位置する主要点の位置情報を有するマクロブロックよりも大きい、
方法。
【請求項１５】
１組の主要点を画像（１１０３）から提供し（１０１）、
前記１組の主要点の位置情報を二値行列の形で記述し（１０３）、
前記二値行列を所定の順序に従って走査することによって、前記１組の主要点の前記位置情報の新規表現（１１０５）を生成する（１０５）
ように構成されたプロセッサ（１１０１）を備え、
前記１組の主要点の位置情報の前記新規表現は別の二値行列（４０２）の形態をとり、
前記別の二値行列（４０２）は様々なサイズのマクロブロックに分割され、前記画像の関心領域またはその周囲に配置された主要点の位置情報を有するマクロブロックのサイズは、前記画像の外縁に位置する主要点の位置情報を有するマクロブロックよりも大きい、
位置情報符号化器（１１００）。
【請求項１６】
画像の１組の主要点の位置情報の行列表現を所定の順序に従って解凍する（１００１）ことによって前記画像の前記１組の主要点の前記位置情報の前記行列表現（１２０３）から前記画像の局所的特徴（１２０５）を再構築するように構成されたプロセッサ（１２０１）を備え、
前記行列表現は、
１組の主要点を画像から提供し（１０１）、
前記１組の主要点の位置情報を二値行列の形で記述し（１０３）、
前記二値行列を所定の順序に従って走査することによって、前記１組の主要点の前記位置情報の新規表現を生成する（１０５）
ことによって生成され、
前記１組の主要点の位置情報の前記新規表現は別の二値行列（４０２）の形態をとり、
前記別の二値行列（４０２）は様々なサイズのマクロブロックに分割され、前記画像の関心領域またはその周囲に配置された主要点の位置情報を有するマクロブロックのサイズは、前記画像の外縁に位置する主要点の位置情報を有するマクロブロックよりも大きい、
位置情報復号器（１２００）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ・ビジョンの分野における画像処理技術に関し、特に、通常は視覚探索または拡張現実と呼ばれるトピックに関する。視覚探索や拡張現実のアプリケーションでは、画像または画像シーケンスから抽出された情報がサーバに送信され、サーバで、当該情報が、認識されるオブジェクトのモデルを表す参照画像または画像シーケンスのデータベースから抽出した情報と比較される。この状況において、本発明は、サーバに送信される画像または画像シーケンスから抽出した情報の圧縮、特に、画像または画像シーケンスから抽出した関心点の位置の圧縮に関する。
【背景技術】
【０００２】
視覚探索（ＶＳ）とは、テキスト記述、メタデータ等のような外部データを利用することなく、画像または画像シーケンスの視覚的態様のみを分析することによって、画像または画像シーケンスで表された１つまたは複数のオブジェクトを特定する自動化システムの能力をいう。拡張現実（ＡＲ）はＶＳの高度な利用とみなすことができ、特に、モバイルの分野に適用される。画像シーケンスに示したオブジェクトが特定された後、追加のコンテンツ、通常は合成オブジェクトが現実のシーンに重ね合わされて、現実のコンテンツを現実のオブジェクトと一貫した位置で「拡張」する。画像シーケンス内に表されたオブジェクトの特定を実現する技術は同じである。以下では、イメージという用語と画像という用語を同義的に使用する。
【０００３】
今日、主要な視覚探索方法では所謂局所的特徴の決定が利用されている。局所的特徴を以下では特徴または記述子とも称する。一般的な方法は、非特許文献１に開示のＳＩＦＴ（Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｆｅａｔｕｒｅ  Ｔｒａｎｓｆｏｒｍｓ）と、非特許文献２に開示のＳＵＲＦ（Ｓｐｅｅｄｅｄ  Ｕｐ  Ｒｏｂｕｓｔ  Ｆｅａｔｕｒｅｓ）である。これらの技術の多数の変形を見出すことができる。当該変形を、これら２つのオリジナルな技術の改良と考えることができる。
【０００４】
図１３から分かるように、局所的特徴はコンパクトな記述であり、例えば、画像１３０１内の点１３０５を囲むパッチ１３０３のＳＩＦＴにおける特徴ごとに１２８バイトである。図１３は、局所的特徴の抽出（図１３の上部）と表現（図１３の下部）の１例を示す。図１３の上部には、局所的特徴が計算される点の位置が、画像１３０１内の点１３０５を表す円で示され、当該円が有向パッチ１３０３を表す正方形で囲まれている。図１３の下部には、パッチ１３０３のグリッド１３０９の再分割が、当該局所的特徴のヒストグラム成分１３１１を含む。局所的特徴を計算するために、点１３０５の主方位１３０７が、点１３０５の囲み内の主勾配成分に基づいて計算される。この方位１３０７から開始して、主方位１３０７に向かって配向されたパッチ１３０３が抽出される。次いで、当該パッチ１３０３が長方形または放射状のグリッド１３０９に再分割される。グリッド１３０９の要素ごとに、局所勾配のヒストグラム１３１１が計算される。グリッド１３０９の要素に対して計算したヒストグラム１３１１は局所的特徴の成分を表す。図１３の下部に示したグリッド１３０９の要素のヒストグラム１３１１を含む記述子１３１３の特徴は、回転、照射、および投影歪みに対して不変である。
【０００５】
画像１３０１では、記述子１３１３が計算される点１３０５は、通常、例えば角や特定のパターン等のシーンの特有の要素に関連する。かかる点は通常は主要点１３０５と呼ばれ、図１３の上部で示した円である。主要点１３０５の計算のプロセスは、マルチスケール画像１３０１の表現における局所的な極値の特定に基づく。
【０００６】
２つの画像１３０１と１４０１を比較するとき、図１４に示すように、第１の画像１３０１の各記述子１３１３を第２の画像１４０１の各記述子と比較する。図１４は、画像１３０１と１４０１のみを示し記述子は示していない。距離測定値を使用し、様々な主要点の間で、例えば第１の画像１３０１内の第１の主要点１３０５と第２の画像１４０１内の第２の主要点１４０５の間で、マッチングを特定する。正確なマッチングは、通常はインライア１４０７と呼ばれ、画像１３０１と１４０１における拡大縮小、回転、投影歪みがあったとしても一貫した相対的位置を有する必要がある。マッチング段階における誤差は、主要点抽出に対して使用した統計的アプローチに起因して生ずる可能性があり、幾何的一貫性チェックと呼ばれる段階により排除される。幾何的一貫性チェックでは、様々な主要点の位置の一貫性が推定される。当該誤差は、通常はアウトライナ１４０９と呼ばれ、図１４の点線で示すように取り除かれる。残存するインライア１４０７の数に従って、２つの画像１３０１、１４０１における同一のオブジェクトの存在に関する推定を実施することができる。
【０００７】
図１５に示すように、典型的なクライアント・サーバ型のサービス・アーキテクチャを表すＶＳパイプライン・システム１５００では、記述子は、主要点識別１５０５、特徴計算１５０７、後述の特徴選択１５０９、およびエンコーディング１５１１の手続きによりクライアント装置１５０１で計算され、これらの記述子１５１９をサーバ１５０３に送信する。サーバ１５０３は、当該記述子、即ち、データベース上の参照画像から抽出した参照記述子１５２１に対してマッチする（１５１３）。詳細には、クライアント１５０１からのデータ・ストリーム１５１５を復号化して（１５１７）、当該データベース上の参照画像から主要点識別１５２３と特徴計算１５２５により計算された参照記述子１５２１に対してマッチされる（１５１３）原画像の記述子１５１９を取得する。マッチング１５１３の後、幾何的一貫性チェック１５２７を適用して再構築画像の幾何的一貫性をチェックする。
【０００８】
何千もの特徴を１つの画像から抽出することができ、その結果、画像あたり数キロバイトの大量の情報がネットワークで送信されることとなる。幾つかのシナリオでは、記述子を送信するのに必要なビットレートは圧縮画像自体よりも大きくなりうる。
【０００９】
これは、クライアント／サーバ接続におけるネットワーク遅延の可能性と、無数の参照画像の記述子をメモリに同時に保持しなければならないサーバ側で必要なメモリの量に起因する、リアルタイム・アプリケーションに関する課題を意味する。したがって、圧縮したバージョンの記述子の必要性が生じる。未圧縮の記述子から始めて記述子を圧縮できるようにするステップが必要である。最初のステップは、以下のような主要点選択の機構である。即ち、画像から抽出された全ての記述子がサーバに送信されるわけではなく、統計分析に従って、マッチング段階であまりエラーを発生させず、かつ、描画されたオブジェクトに対してより典型的と考えられる点を示すもののみがサーバに送信される。当該第２のステップは、残りの記述子に適用される圧縮アルゴリズムである。
【００１０】
ＭＰＥＧ（Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅｓ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ）標準化委員会は現在、新たな標準ＭＰＥＧ−７（ＩＳＯ／ＩＥＣ  １５９３８−Ｍｕｌｔｉｍｅｄｉａ  ｃｏｎｔｅｎｔ  ｄｅｓｃｒｉｐｔｉｏｎ  ｉｎｔｅｒｆａｃｅ）のパート、即ち、パート１３を定義しており、圧縮記述子の標準形式の開発に専念している。新たな標準の圧縮機能をテストするために、画像から抽出した全ての記述子を格納または送信するのに必要なビットレートを表す６つの動作点が５１２−１０２４−２０４８−４０９６−８１９２−１６３８４バイトとして特定されている。当該テスト段階は、これらの動作点を参照として用いて行われる。主要点選択機構の適用のため、これらの動作点で、様々な数の主要点がサーバに送信され、この数は最小の動作点にある１１４個の主要点から最高動作点にある９７０個の主要点に及ぶ。
【００１１】
記述子圧縮を記述子に適用するとき、２つの異なる種類の情報が圧縮される。１つ目は記述子の値に関するものである。２つ目は、画像内の主要点のデカルト座標である記述子の位置情報、即ち、ｘ／ｙ位置である。
【００１２】
現在のＶＳ標準の参照モデル（ＲＭ）ならびに当業界に存在する大多数のＶＳアルゴリズムでは、記述子抽出段階の前に、画像が６４０×４８０画素であるＶＧＡ（Ｖｉｄｅｏ  Ｇｒａｐｈｉｃ  Ａｒｒａｙ）解像度に拡大される。ＶＧＡ解像度を以降では最大解像度と称する。
【００１３】
したがって、画像内の単一の主要点の位置を記述する固有のｘ／ｙの組が１９ビットを占有しうる。これは、特に最小の動作点では許容できないものである。したがって、位置情報を圧縮し、より多くの記述子を挿入するかまたはあまり制限的でない圧縮アルゴリズムを記述子に適用するために、より多くのビットを割り当てる必要がある。
【００１４】
主要点の座標は、元の拡大されていない画像解像度の浮動小数点値で表される。全ての画像に適用される第１の操作はＶＧＡ解像度への縮小であるので、当該主要点の座標は、本来１９ビットであるＶＧＡ解像度の整数値に丸められる。したがって、幾つかの点が同一の座標に丸められる可能性がある。２つの記述子が２つの異なる方位を有する同一の主要点で計算される可能性もある。この最初の丸めが抽出性能に及ぼす影響は無視できる。
【００１５】
図１６はかかる丸め操作の１例を示し、各正方セル１６０３、１６０５が最大解像度の１×１画素セルに対応する。非空要素が主要点の位置に対応する画像１６００を生成することができ、行列表現１６０２で表せる画素セル表現１６０１に分割することができる。これらの正方セル１６０３、１６０５の値、例えば、図１６に示すように第１の正方セル１６０３に対して２および第２の正方セル１６０５に対して１が行列１６０２で表される。ここで、非空セル１６０７、１６０９は主要点の位置を表す。例えば第１の非空セル１６０７は第１の正方セル１６０３に対応し、第２の非空セル１６０９は第２の正方セル１６０５に対応する。その結果、上記の課題を、最高動作点においても極めて疎、即ち、非空セルが１００個未満であるという特性を有する６４０×４８０要素の行列１６０２を圧縮する必要性として再構成することができる。当該行列を圧縮するために、２種類の異なる情報を表す必要がある。当該２種類の情報とは、空セルと非空セルから成る二値マップであるヒストグラム・マップと、ヒストグラム数、即ち、各非空セル内の発生数を含むベクトルである。ヒストグラム・マップは、図１６に示す画素セル表現１６０１の二値形式により表され、ヒストグラム数は、図１６に示す行列表現１６０２の非空要素で生成されたベクトルで表される。圧縮効率を高めるために、当業界では、これらの２つの要素が常に別々にエンコードされる。
【００１６】
既存の技術では、ブロック量子化を含むロッシ技術をヒストグラム・マップに適用して圧縮効率を高める。即ち、通常は４×４ブロックまたは８×８ブロックが使用され、ヒストグラム・マップとヒストグラム数の生成機構を不変とする。当該操作の結果として、行列の次元は大幅に減少する。即ち、４×４ブロックが適用されるときは１４０×１２０画素に、８×８ブロックが適用されるときは７０×６０画素に減少する。それでも、縮小した行列には依然として非常に疎な行列が残る。このケースでは、図１６の表現が依然として有効であり、セルの次元のみが変化している。本明細書の残りの部分では、ヒストグラム・マップ行列の要素を行列セルと称する。当該セルは、その想定する次元に関わらず、最大解像度での１×１から、圧縮された場合はＮ＞１であるＮ×Ｎ（例えば８×８）までである。
【００１７】
当業界では、３つの主要な文献が、位置情報圧縮の分野における最新の進展をもたらしている。１番目の文献は、以降では［ＲＭ］と称するが、ＭＰＥＧ参照モデルである非特許文献３である。２番目の文献は、以降では［Ｓｔａｎｆｏｒｄ１］と称するが、ＭＰＥＧ入力コントリビューション（ＭＰＥＧ  ｉｎｐｕｔ  ｃｏｎｔｒｉｂｕｔｉｏｎ）である非特許文献４である。３番目の文献は、以降では［Ｓｔａｎｆｏｒｄ２］と称するが、学会論文である非特許文献５である。
【００１８】
これらの３つの文献の全ては、異なるアプローチから得られながらも同じ問題を提示している。即ち、座標は最大解像度では表されず、量子化領域、即ち、４×４、６×６、８×８ブロックで表されている。
【００１９】
ブロック量子化のヒストグラム・マップへの適用は、ロッシ圧縮にも関わらず、抽出精度の点で性能低下が限定的であるのを保証できる。何れにせよ、クエリ画像内の認識オブジェクトを局所化する必要があるとき、例えば拡張現実アプリケーションにおいて、オブジェクトを局所化し一連の画像にわたって追跡する必要がある場合には、これらの量子化されたブロックを適用することにより性能が大幅に低下する。例えば、［Ｓｔａｎｆｏｒｄ１］によれば、局所化精度は、４×４ブロックを最小動作点で適用するときには５％低下し、ブロックが８×８の次元を有するときには１０％低下する。
【００２０】
最大解像度まで拡大するとき、先行技術には幾つかの問題がある。ヒストグラム数圧縮は非常に単純であるので、考慮には入れられない。ヒストグラム・マップ行列の圧縮に関して生ずる問題を以下で提示する。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】D. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, Int. Journal of Computer Vision 60 (2) (2004) 91-110. H
【非特許文献２】Bay, T. Tuytelaars, L. V. Gool, SURF: Speeded Up Robust Features, in: Proceedings of European Conference on Computer Vision (ECCV), Graz, Austria, 2006, http://www.vision.ee.ethz.ch/~surf/
【非特許文献３】“G. Francini, S. Lepsoy, M. Balestri “Description of Test Model under Consideration for CDVS”, ISO/IEC JTC1/SC29/WG11/N12367, Geneva, November 2011”
【非特許文献４】“S. Tsai, D. Chen, V. Chandrasekhar, G. Takacs, M. Makar, R. Grzeszczuk , B. Girod, “Improvements to the location coder in the TMuC “, ISO/IEC JTC1/SC29/WG11/M23579672, San Jose, February 2012”
【非特許文献５】“S. Tsai, D. Chen, G. Takacs, V. Chandrasekhar, J. Singh, and B. Girod, "Location coding for mobile image retrieval", International Mobile Multimedia Communications Conference (MobiMedia), September 2009”
【発明の概要】
【発明が解決しようとする課題】
【００２２】
文献［ＲＭ］は、主要点が出現しない、空の行と列をヒストグラム・マップから削除して行列の疎性を減少させることを目的とした方法を使用している。行および列ごとに１ビットを費やして、完全な行または列が空かどうかを示す。最大解像度での問題は、４８０×６４０行列では、この情報を圧縮ビット・ストリームに埋め込むのに１１２０ビットが必要であるということである。これは、許容できない量のビットであり、最小動作点（１１４個の点）で主要点ごとにほぼ１０ビットが生じる。
【００２３】
［Ｓｔａｎｆｏｒｄ１］では、以下の２つの改善により、バイナリ・エントロピ符号化を行列全体に対して使用している。マクロブロック分析が適用されている。即ち、以降ではｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋと称するが、行列がマクロブロックに再分割され、マクロブロックごとに、当該ブロックが空かどうかを示す１ビットが割り当てられる。ブロックが完全に空である場合には、その要素にはエントロピ符号化プロセスを行わない。また、コンテキスト・モデリングがエントロピ符号化に適用される。当該コンテキスト・モデリングは、エンコードすべきものを囲むセルに基づく。特に、１０個の近傍が考慮され、結果として４５個のコンテキストが生ずる。その複雑さに加えて、特に、生成される４５個のコンテキストを有するトレーニング段階に対し、このアプローチを最大解像度のケースに効果的に適用することはできない。この場合、行列は非常に疎であるので、１０個の最も近接するセルの中で非空セルに遭遇するのは非常に稀である。
【００２４】
文献［Ｓｔａｎｆｏｒｄ２］によれば、２つの方法が適用される。１つ目は、文献［Ｓｔａｎｆｏｒｄ１］で提供されたものと非常に類似し、同じ問題を提示しているので、ここではこれ以上論じない。２つ目は、四分木に基づくものである。四分木は、行列が密であるときには非常に効果的な表現をもたらすが、行列が非常に疎であるときには、最大解像度のケースと同様、当該木の構築には大量のビットを消費し、性能が劣化することとなる可能性がある。
【課題を解決するための手段】
【００２５】
本発明の目的は、上述の先行技術の概念と比べて位置情報の圧縮率が高く複雑度が非常に低い画像処理に関する概念を提供することである。本発明の目的は、添付の独立請求項の特徴により実現される。さらなる実施形態については、それらの従属請求項、発明の詳細な説明、および添付図面から明らかである。
【００２６】
画像のヒストグラム・マップの圧縮作業を、非常に疎な行列の圧縮として考えることができる。本発明は、特に低いビットレートにおいて、この疎性にも関わらず主要点が画像にわたって均一に分散しないという知見に基づく。これは特に、主要点のサブセットを全ての抽出した主要点から特定するために適用される主要点選択機構に起因する。一般的に、関心点は画像の中心に描かれるので、当該主要点選択機構は画像中心から近い距離を特別に扱う。例えば関心領域（ＲＯＩ）に基づいて、代替的な主要点選択方法を適用するとき、画像内の主要点の分布は依然として均一ではない。その結果、より密集した領域が通常は画像の中心周辺に存在し、行列の側面には非常に多数の零が存在することとなる。したがって、反対にブロック表現を画像にわたって均一に適用する［Ｓｔａｎｆｏｒｄ１］のアプローチで利用されるｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋ情報の適合的な利用を考慮して、当該機能を利用することが可能である。行列の中心には、空の領域は殆ど生じない。したがって、このようにｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋ情報送信に関して殆どビットを使用しない、非常に大規模なマクロブロックの適用が想定される。他方、行列の側面では、小規模なマクロブロックを適用して高い精度で空の領域を特定するのが有利である。
【００２７】
本発明の諸態様では、位置情報圧縮アルゴリズムの性能を高める画像処理の概念を提供する。本発明を詳細に説明するために、以下の用語、略語、および記法を使用する。
【００２８】
ＶＳ：視覚探索。ＶＳは、テキスト記述、メタデータ等のような外部データを利用することなく、画像または画像シーケンスの視覚的態様のみを分析することによって当該画像または画像シーケンス内で示された１つまたは複数のオブジェクトを特定する自動化システムの能力をいう。
ＡＲ：拡張現実。ＡＲとは、特にモバイルの領域に適用されるＶＳの高度な利用と考えることができる。フレーム・シーケンスで示されたオブジェクトを特定した後、追加のコンテンツ、通常は合成オブジェクトを現実のシーンに重ね合わせて、現実のコンテンツを現実のオブジェクトに一貫した位置で「補強」する。
ＳＩＦＴ：スケール不変特徴変換（Ｓｃａｌｅ−Ｉｎｖａｒｉａｎｔ  Ｆｅａｔｕｒｅ  Ｔｒａｎｓｆｏｒｍｓ）
ＳＵＲＦ：高速化ロバスト特徴（Ｓｐｅｅｄｅｄ  Ｕｐ  Ｒｏｂｕｓｔ  Ｆｅａｔｕｒｅｓ）
ＭＰＥＧ−７：Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅｓ  Ｅｘｐｅｒｔ  Ｇｒｏｕｐ  Ｎｏ．７は、視覚探索の標準の開発に特化した、ＩＳＯ／ＩＥＣ１５９３８に従うマルチメディア・コンテンツ記述インタフェースを定義する。
ＲＯＩ：関心領域
ＲＭ：参照モデル
ＶＧＡ：ビデオ・グラフィック・アレイ。最大解像度とも呼ばれる。
局所的特徴：局所的特徴は、回転、照射、および投影歪みに対して不変な、画像内の主要点を囲むパッチのコンパクトな記述である。
記述子：局所的特徴
主要点：画像において、記述子が計算される点は通常はシーンの特定の要素、例えば隅、特定のパターン等に関連する。かかる点は通常、主要点と呼ばれる。主要点の計算のプロセスは、マルチスケール画像表現における局所的極値の特定に基づく。
ｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋ：非空値を含まない画像のヒストグラム・マップを表す行列セグメント
【００２９】
第１の態様によれば、本発明は画像処理方法に関する。当該方法は、１組の主要点を当該画像から提供するステップと、当該１組の主要点の位置情報を二値行列の形で記述するステップと、当該二値行列を所定の順序に従って走査することによって、当該１組の主要点の位置情報の新規表現を生成するステップとを含む。
【００３０】
本発明の第１の態様により、特にヒストグラム・マップ行列の圧縮に使用される、画像から抽出された記述子（局所的特徴）の位置情報を処理するための新たな方法を提供する。当該方法は、当分野の技術の状態と比較したときの改善された圧縮率により特徴づけられる。当該方法を最大解像度レベルでの固有の問題に遭遇することなく適用することができる。本発明の主要な要素は、データの新規表現に基づき、より効率的なブロック・ベースの分析および表現を可能とする。適合的ブロック・ベース分析を当該新規表現に対して適用することができ、データの性質をより良く利用して改善された圧縮率を達成することができる。複雑な操作に遭遇しないので、提供した方法の複雑性は極めて限定的である。
【００３１】
第１の態様に従う方法の第１の可能な実施形態では、当該二値行列を所定の順序に従って走査するステップは、当該二値行列を、当該画像の関心領域またはその周囲に配置された主要点から開始して当該画像の外縁に位置する主要点に向かって走査するか、または、当該画像の外縁に位置する主要点から開始して当該画像の関心領域またはその周囲に配置された主要点に向かって走査するステップを含む。
【００３２】
画像の関心領域は一般的には画像の中心領域に配置される。したがって、走査によって関心領域またはその周囲に配置された主要点と画像周囲の非関心領域が区別されるとき、処理を改善することができる。
【００３３】
第１の態様の第１の実施形態に従う方法の第２の可能な実施形態では、画像の関心領域は当該画像の中心にあるかまたは当該画像の中心の周囲にある。
【００３４】
通常、画像の最も関連する情報を、画像の中心からまたは画像の中心周りから抽出することができる。処理が画像の中心と周囲を区別する場合には、当該処理とそれによる圧縮を改善することができる。
【００３５】
第１の態様に従う方法または第１の態様の上述の実施形態の何れかに従う方法の第３の可能な実施形態では、当該二値行列の走査は反時計回りまたは時計回りに実施される。反時計回りまたは時計回りの走査によって、処理を改善することができる。
【００３６】
第１の態様に従う方法または第１の態様の第１の実施形態に従う方法の第４の可能な実施形態では、当該二値行列の走査は画像の同心円環内の部分で実行される。
【００３７】
最も本質的な特徴は画像の中心に配置されているので、画像の中心に向かう小環が大部分の情報を保持し、画像の周辺に向かう大環が少ない情報を保持する。周辺に向かう大環は疎に占有され、空の領域が発生し、これをｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋ情報で特定することができる。
【００３８】
第１の態様に従う方法または第１の態様の上述の実施形態の何れかに従う方法の第５の可能な実施形態では、１組の主要点の位置情報の新規表現は別の二値行列の形をとる。
【００３９】
第１の態様の第５の実施形態に従う方法の第６の可能な実施形態では、当該別の二値行列は列方向または行方向に生成される。
【００４０】
したがって、本質的な情報を保持する領域が新たな行列表現の近傍領域に配置され、以下の適合的ブロック分析を使用することができる。
【００４１】
第１の態様の第５の実施形態に従う方法または第１の態様の第６の実施形態に従う第７の可能な実施形態では、当該１組の主要点の中の主要点ごとに、記述子が当該主要点を囲む有向パッチから計算される。
【００４２】
記述子は通常、画像の特定の要素、例えば、隅、特定のパターン等に関する。したがって、画像処理に関する記述子を利用することによって、オブジェクトの認識と追跡の性能が高まる。
【００４３】
第１の態様の第５乃至第７の実施形態の何れかに従う方法の第８の可能な実施形態では、当該二値行列は空セルと非空セルから成るヒストグラム・マップであり、非空セルは当該画像における主要点の位置を表す。
【００４４】
第１の態様の第５乃至第８の実施形態の何れかに従う方法の第９の可能な実施形態では、当該方法はさらに、１組の主要点の位置情報の新規表現を圧縮するステップを含む。
【００４５】
当該１組の主要点の位置情報の新規表現が第１の態様に従う方法または第１の態様の上述の実施形態の何れかに従って生成されるとき、関連情報の大部分、即ち、非空要素が行列の１つの領域に集中するので、圧縮が改善される。上記別の二値行列は、位置情報密度が高い部分と位置情報密度が低い部分を含む。様々な圧縮技術をこれらの部分に対して使用して、圧縮を改善することができる。
【００４６】
第１の態様の第９の実施形態に従う方法の第１０の可能な実施形態では、１組の主要点の位置情報の新規表現を圧縮するステップは、位置情報を有しない二値行列の外縁部を排除することによって当該二値行列のサイズを縮小するステップを含み、当該縮小するステップは当該二値行列を走査する前に実施される。
【００４７】
したがって、走査を実施する前に非本質的な情報を除去することができ、したがって、圧縮すべき情報の量が減り、画像処理方法の性能が速度と記憶の点で改善される。
【００４８】
第１の態様の第９の実施形態に従う方法の第１１の可能な実施形態では、１組の主要点の位置情報の新規表現を圧縮するステップは、位置情報を保持しない当該二値行列の同心円環に対応する別の二値行列の空要素を排除するステップを含む。
【００４９】
したがって、走査を実施した後に非本質的な情報を除去することができ、したがって、圧縮すべき情報の量が減り、画像処理方法の性能が速度と記憶の点で改善される。
【００５０】
第１の態様の第５乃至第１１の実施形態の何れかに従う方法の第１２の可能な実施形態では、当該別の二値行列は様々なサイズのマクロブロックに分割され、当該画像の関心領域またはその周囲に配置された主要点の位置情報を有するマクロブロックのサイズは、当該画像の外縁に位置する主要点の位置情報を有するマクロブロックよりも大きい。したがって、画像の中心からの情報が大規模なマクロブロックに格納され、画像の周辺からの情報が小規模なマクロブロックに格納される。したがって、さらなる処理から排除できる空要素のみを保持する一部の小規模なマクロブロックを特定することができ、画像処理の性能が改善される。
【００５１】
第１の態様の第１２の実施形態に従う方法の第１３の可能な実施形態では、エントロピ符号化が上記別の二値行列のｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋ情報と当該別の二値行列の非空マクロブロックに適用される。
【００５２】
第１の態様の第１３の実施形態に従う方法の第１４の可能な実施形態では、エントロピ符号化を適用するときにコンテキスト・モデリングが適用される。
【００５３】
第１の態様の第１２乃至第１４の実施形態の何れかに従う方法の第１５の可能な実施形態では、上記別の二値行列は、画像の中心とその周囲に配置された位置情報を保持する第１の数の特定のサイズ（以降、ＭＢ＿Ｓｉｚｅとして示す）のマクロブロックと、画像の周辺に配置された位置情報を保持する第２の数のＭＢ＿Ｓｉｚｅ分の何分の１かのマクロブロックを含む。
【００５４】
ＭＢ＿Ｓｉｚｅの大きさのマクロブロックとその一部を用いることで、上述の方法の実施が単純になる。異なるメモリ・サイズの複雑なメモリ割当てを適用する必要はない。メモリ構造は極めて単純である。
【００５５】
第１の態様の第１５の実施形態に従う方法の第１６の可能な実施形態では、第１の数のＭＢ＿Ｓｉｚｅの大きさのマクロブロックは全ての画像にわたって固定され、または、別の行列表現の大きさに依存する。
【００５６】
第１の態様の第５乃至第１６の実施形態に従う方法の第１７の可能な実施形態では、当該方法は、ｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋビット・シーケンスを使用して、位置情報を保持しない別の二値行列の空のマクロブロックを示すステップをさらに含む。
【００５７】
位置情報を保持しない当該別の二値行列の空のマクロブロックを示すことによって、当該方法は、これらのマクロブロックをさらに圧縮するステップを考慮しないでおくことができ、それにより、圧縮率が高まる。
【００５８】
第１の態様の第１７の実施形態に従う方法の第１８の可能な実施形態では、上記１組の主要点の位置情報の新規表現は、上記別の二値行列の非空マクロブロックのエントロピ符号化したｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋビット・シーケンスとエントロピ符号化した位置情報を結合することによって圧縮される。
【００５９】
第１の態様の第１８の実施形態に従う方法の第１９の可能な実施形態では、当該位置情報は、トレーニング・セットにわたって計算された非空マクロブロック内の平均的な数の非空要素を利用するコンテキスト・モデルを用いてエントロピ符号化される。
【００６０】
当該コンテキストでは、余分な情報を送信する必要がなく、当該別の二値行列内のマクロブロックの平均密度に従ってエントロピ符号化器を最適化することができる。
【００６１】
第１の態様の第５乃至第１９の実施形態の何れかに従う方法の第２０の可能な実施形態では、メモリ占有を最小化するために、上記別の二値行列全体ではなく、当該別の二値行列の非空要素のみまたは非空のマクロブロックの順序リストを記憶する。
【００６２】
大量のリソースを消費する操作はコンテキスト・モデリングであり、これは任意のものである。それにも関わらず、コンテキスト・モデリングを適用するときには、新たなコンテキスト・モデリング方法が提案され、これは先行技術で適用されるものより簡単である。提供するコンテキスト・モデリング方法では非常に限られた数のコンテキストを利用する。さらに、マクロブロック情報は本来新たなデータ表現において運搬されるので、余分なビットがコンテキスト・モデリングに対して使用されない。
【００６３】
第２の態様によれば、本発明は、画像の局所的特徴を当該画像の１組の主要点の位置情報の行列表現から再構築するための方法に関し、当該方法は、当該画像の当該１組の主要点の位置情報の行列表現を所定の順序に従って解凍するステップを含み、当該画像の当該局所的特徴は当該主要点を囲む有向パッチから計算される。当該解凍方法は、圧縮方法の逆の操作を逆順に実施するものであり、したがって、上述の圧縮方法と同じ利点をもたらす。
【００６４】
第３の態様によれば、本発明は、１組の主要点を画像から提供し、当該１組の主要点の位置情報を二値行列の形で記述し、当該二値行列を所定の順序に従って走査することによって、当該１組の主要点の位置情報の新規表現を生成するように構成されたプロセッサを備える、位置情報符号化器に関する。当該位置情報符号化器は、上述の低い複雑度の位置情報圧縮方法を実施するので、複雑度が極めて限定的である。
【００６５】
第４の態様によれば、本発明は、画像の１組の主要点の位置情報の行列表現を所定の順序に従って解凍することによって当該画像の局所的特徴を当該画像の１組の主要点の位置情報の行列表現から再構築するように構成されたプロセッサであって、当該画像の当該局所的特徴は当該主要点を囲む有向パッチから計算されるプロセッサを備える、位置情報復号器に関する。当該位置情報復号器は、上述の低い複雑度の画像処理方法を実施するので、複雑度が極めて限定的である。
【００６６】
第５の態様によれば、本発明は、第１の態様に従う方法もしくは第１の態様の上述の実施形態の何れかに従う方法を実施するためのプログラム・コードを有するコンピュータ・プログラムに関し、または、当該プログラム・コードがコンピュータで実行されるときには第２の態様に従う方法を実施するためのプログラム・コードを有するコンピュータ・プログラムに関する。
【００６７】
本明細書で説明する方法を、デジタル信号プロセッサ（ＤＳＰ）、マイクロ・コントローラ、もしくは他の任意のプロセッサにおけるソフトウェアとして、または特殊用途向け集積回路（ＡＳＩＣ）内のハードウェア回路として実装してもよい。
【００６８】
本発明をデジタル電子回路で、または、コンピュータハードウェア、ファームウェア、ソフトウェア、もしくはそれらの組合せとして実装することができる。
【００６９】
本発明のさらなる諸実施形態を、以下の図面と関連して説明する。
【図面の簡単な説明】
【００７０】
【図１】１実施形態に従う画像処理方法の略図である。
【図２】１実施形態に従う位置情報圧縮方法の略図である。
【図３】画像内の主要点分布を示すグラフの図である。
【図４】新たな行列表現を生成するための行列走査方法の略図である。
【図５】１実施形態に従う別の行列表現の略図である。
【図６】１実施形態に従う図５に示した別の行列表現の適合的ブロック・ベース分析の略図である。
【図７】１実施形態に従う位置情報圧縮方法の略図である。
【図８】１実施形態に従う位置情報圧縮方法の略図である。
【図９】１実施形態に従う位置情報圧縮方法の略図である。
【図１０】１実施形態に従う位置情報解凍方法の略図である。
【図１１】１実施形態に従う位置情報符号化器のブロック図である。
【図１２】１実施形態に従う位置情報復号器のブロック図である。
【図１３】視覚探索のための局所的特徴の抽出および表現の例を示す図である。
【図１４】２つの画像の従来の比較における特徴マッチングおよびアウトライナ排除の例を示す図である。
【図１５】典型的なクライアント−サーバサービス・アーキテクチャで使用される視覚探索パイプラインのブロック図である。
【図１６】従来のヒストグラム・マップおよびヒストグラム数生成方法の略図である。
【発明を実施するための形態】
【００７１】
図１は、１実施形態に従う画像処理方法１００の略図を示す。画像処理方法１００は、１組の主要点を画像から提供するステップ（１０１）と、当該１組の主要点の位置情報を二値行列の形で記述するステップ（１０３）と、当該二値行列を所定の順序に従って走査することによって、当該１組の主要点の位置情報の新規表現を生成するステップ（１０５）とを含む。１実施形態では当該１組の主要点の位置情報の当該新規表現は別の二値行列の形である。
【００７２】
図２は、１実施形態に従う位置情報圧縮方法２０１の略図を示す。画像圧縮方法２０１は、ヒストグラム・マップおよびヒストグラム数の生成（２００）と、ヒストグラム・マップの圧縮（２１０）と、ヒストグラム数の圧縮（２２０）と、圧縮された記述子（２３０）に応じた符号化されたビット・ストリームの生成（２４０）を含む。当該ヒストグラム・マップは、図１６に示す説明に従う画素セル表現１６０１における画像１６００の空セルと非空セルから成る二値マップである。画像１６００を、行列表現１６０２で表せる画像セル表現１６０１に分割することができる。当該ヒストグラム数は、図１６に示す説明に従う行列表現１６０２において画像１６００の各非空セルが出現する数である。１実施形態では、ヒストグラム・マップの圧縮（２１０）とヒストグラム数の圧縮（２２０）を並列に行う。１実施形態では、ヒストグラム・マップの圧縮（２１０）とヒストグラム数の圧縮（２２０）を互いに独立に実施する。１実施形態では、ヒストグラム・マップの圧縮（２１０）のみを実施し、ヒストグラム数の圧縮（２２０）は実施しない。
【００７３】
１実施形態では、ヒストグラム・マップおよびヒストグラム数の生成（２００）は、１組の局所的特徴を画像から決定するステップ（１０１）と各主要点を記述子により記述するステップ（１０３）に対応し、ヒストグラム・マップの圧縮（２１０）は、走査（１０５）による主要点の行列表現の生成と、以下の２１１乃至２１７の操作に対応する。
【００７４】
本発明の諸態様は、画像から抽出した記述子（局所的特徴）の位置情報の圧縮、特に、図２に示したヒストグラム・マップ行列の圧縮に対する新たな方法を提供する。当該方法は、最新の技術と比較して改善された圧縮により特徴づけられる。当該方法を、最大解像度レベルでの固有の問題に遭遇することなく適用することができる。
【００７５】
本発明の諸態様はデータの新規表現に基づくものであり、より効率的なブロック・ベースの分析と表現を可能とする。図７、８、および９に関して後述するように、適合的ブロック・ベース分析を当該新規表現に適用して、当該データの性質をより良く利用して圧縮率の向上を実現することができる。
【００７６】
複雑な操作が含まれないので、当該方法の複雑性は極めて限られている。大部分のリソース消費操作はコンテキスト・モデリングであり、これは任意のものである。それにも関わらず、図９に関して後述するようにコンテキスト・モデリングを適用するときには、先行技術で使用されているものよりも単純な新たなコンテキスト・モデリング方法を使用する。１実施形態では、当該コンテキスト・モデリング方法は非常に限定的な数のコンテキストを利用する。さらに、マクロブロック情報が本来当該新たなデータ表現で運搬されるので、当該コンテキスト・モデリングに対して余分なビットは使用されない。
【００７７】
本発明の諸実施形態では広範囲の削除をもたらす。即ち、行列の側面にある完全に空の領域が削除される。本発明の実施形態では、従来のようにＲＭで使用される空の行および列を識別するのではなく、空の領域を識別するための新たな方法を提供する。
【００７８】
図３は、画像３００における主要点３０１の分布を表すグラフを示す。後述するように、ヒストグラム・マップの圧縮作業を非常に疎な行列の圧縮と考えることができる。本発明の基本的な考え方は、図３から分かるように、特に低いビットレートにおいて、この疎性にも関わらず、主要点３０１が画像に均一に分布しないことである。これは、特に主要点選択機構を適用して主要点のサブセットを全ての抽出した主要点から特定するときに生ずる。一般に関心のあるオブジェクトは画像の中心に描画されるので、主要点選択機構は画像中心から短い距離を特別に扱う。その結果、ヒストグラム・マップ行列の中心はより密になり、行列の側面は零で支配される。代替的な主要点選択方法を例えば関心領域（ＲＯＩ）に基づいて適用するとき、画像内の主要点の分布は依然として均一ではない。したがって、諸実施形態では、（ブロック表現を画像にわたって反対方向に均一に適用する）［Ｓｔａｎｆｏｒｄ１］のアプローチで利用されるｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋ情報を適合的に用いて、当該特徴を使用する。行列の中心では、空の領域が発生するのは非常に稀である。したがって、本発明の諸実施形態では、非常に大きなマクロブロックを使用し、ｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋ情報の送信に対してはビットを殆ど使用しない。行列の側面では、より小規模なマクロブロックを適用して、より正確に空の領域を特定する。
【００７９】
図４では、１実施形態に従う、新たな行列表現の生成に関する走査段階の略図を示す。本図は、図１に関して説明した走査ステップ１０５を示す。ヒストグラム・マップ行列の要素を要素１、２、３、・・・、４２で表す。
【００８０】
図４に示す１実施形態では、画像４０１を、画像の中心に配置された要素１、２、３、４、５、６（円）から当該画像の外縁に配置された要素２１、２２、・・・、４１、４２（三角形）へと走査する。走査した要素を、新たな行列表現を表す行列４０２に再マップする。図４に示す１実施形態では、行列４０２において行列要素を列方向に配置する。この走査手続きにより、画像４０１の中心に配置された要素１、２、３、４、５、６（円）が行列４０２の左に格納され、画像４０１の中心と周辺の間に配置された要素７、８、９、・・・、２０（正方形）は行列４０２の中央に格納され、画像４０１の周辺に配置された要素２１、２２、・・・、４１、４２（三角形）は行列４０２の右に格納される。
【００８１】
図４には示していない中心から周辺へ走査する代替的な実施形態では、要素は行列４０２において行方向に配置される。この走査手続きにより、画像４０１の中心に配置された要素１、２、３、４、５、６（円）は行列４０２の上部に格納され、画像４０１の中心と周辺の間に配置された要素７、８、９、・・・、２０（正方形）は行列４０２の中央部に格納され、画像４０１の周辺に配置された要素２１、２２、・・・、４１、４２（三角形）は行列４０２の下部に配置される。
【００８２】
図４に示した１実施形態では、画像４０１を、当該画像の外縁に配置された要素２１、２２、・・・、４１、４２（三角形）から画像の中心に配置された要素１、２、３、４、５、６（円）へと走査する。走査された要素は、新たな行列表現を表す行列４０２で提供される。１実施形態では、当該要素は行列４０２において列方向に配置される。この走査手続きにより、画像４０１の周辺に配置された要素２１、２２、・・・、４１、４２（三角形）は行列４０２の左に格納され、画像４０１の中心と周辺の間に配置された要素７、８、９、・・・、２０（正方形）は行列４０２の中央に格納され、画像４０１の中心に配置された要素１、２、３、４、５、６（円）は行列４０２の右に配置される。
【００８３】
周辺から中心へと走査する代替的な実施形態では、主要点は行列４０２において行方向に配置される。この走査手続きにより、画像４０１の周辺に配置された要素２１、２２、・・・、４１、４２（三角形）は行列４０２の上部に格納され、画像４０１の中心と周辺の間に配置された要素７、８、９、・・・、２０（正方形）は行列４０２の中央部に格納され、画像４０１の中心に配置された要素１、２、３、４、５、６（円）は行列４０２の下部に格納される。
【００８４】
行列４０２は、記述子の位置情報の表現を提供する。主要点は画像の中心から１つの側へ、即ち、別の行列表現の左、右、上、または下にマップされる。したがって、画像の中心に通常配置される画像の関連情報が当該行列の１つの側にマップされる。したがって、当該行列は１つの側で密に占有された部分を有し、他方で疎に占有された部分を有する。当該行列構造または行列形式により、効率的な圧縮技術を適用することができる。
【００８５】
当該新たな行列形式は完全に可逆であり、この適合的なブロック表現を都合よく適用することができる。１実施形態では、当該新たな行列表現を以下のように生成する。
【００８６】
・マクロブロックの大きさを選ぶ（例えば、後述する図５と図６の例では１２８）。
・行列の空の境界を任意の操作として削除する。
・行列の中心から開始して、同心円環で実施する反時計回りまたは時計回りの走査によって、全ての画素を走査し、図４に示すように新たな行列形式で列方向または行方向に格納する。
【００８７】
１実施形態では、図４に示すように画素を同心の長方形で走査する。１実施形態では、画素を、同心の円、三角形、五角形、または他の幾何学的形状の上で走査する。
【００８８】
図１乃至４に関して説明した方法の１実施形態では、画像の走査は反時計回りまたは時計回りに実施される。図１乃至４に関して説明した方法の１実施形態では、画像の走査は当該画像の同心円環内の部分で実行される。図１乃至４に関して説明した方法の１実施形態では、別の行列表現が列方向または行方向で提供される。
【００８９】
図５は、１実施形態に従う、行列により表された１つの画像から抽出された１組の主要点の別の行列表現５００の略図を示す。図から分かるように、図１乃至４に関して説明した方法に従って得られる新たな行列表現の左側は、元の行列の中央の要素を含み、右側よりも非常に密になっている。
【００９０】
図６は、１実施形態に従う、図５に示した別の行列表現５００の適合的なブロック・ベースの行列分析６００の略図を示す。
【００９１】
この新たな行列表現５００から開始して、適合的ブロック・ベース分析を適用する。新たな行列表現５００の左側に対して、ＭＢ＿Ｓｉｚｅの大きさのマクロブロック、例えば、行列表現６００の大きさに従い１２８画素×１２８画素のマクロブロックを適用する。新たな行列表現５００の右側に対しては、ＭＢ＿Ｓｉｚｅの大きさの一部（一般的には、ＭＢ＿Ｓｉｚｅ／２）のマクロブロック、例えば、行列表現６００の大きさに従い６４画素×６４画素のマクロブロックを適用する。このように、空のマクロブロックに遭遇する確率が増大する。当該空のマクロブロックは、後続の圧縮技術を適用することにより排除することができる。１実施形態では、ＭＢ＿Ｓｉｚｅの大きさのマクロブロックの数は画像にわたって固定されている。代替的な実施形態では、ＭＢ＿Ｓｉｚｅの大きさのマクロブロックの数は行列内の列または行の数に従って変化している。次に、ｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋに関する０／１の指示をエントロピ符号化する。
【００９２】
図７は、１実施形態に従う位置情報圧縮方法２０２の略図を示し、以下では第１の実施形態と称する。第１の実施形態では図１乃至６に関して説明した動作の流れを使用する。
【００９３】
任意のステップである境界削除（２１１）の後、新たな行列表現（代替的な行列表現と称する）を、中心から同心円へと生成し（２１２）、図６に関する説明に従って適合的ブロック分析２１４を適用する。当該分析の結果、即ち、ｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋと非空マクロブロックの行列要素に関する情報を後続のステップ２１６と２１７でエントロピ符号化する。圧縮された情報をヒストグラム数の圧縮（２２０）と結合して、位置情報の圧縮段階を完了する。ビット・ストリーム生成（２４０）を当該圧縮された情報で実施する。
【００９４】
１実施形態では、境界排除（２１１）は、局所的特徴が決定されていない画像の外縁部を排除することによって画像のサイズを縮小するステップを含む。当該縮小は、別の行列表現の生成（２１２）に対応する画像の走査の前に実施される。
【００９５】
１実施形態では、適合的ブロック・ベース分析２１４により、図６に関して説明したように、別の行列表現を様々なサイズのマクロブロックに分割する。画像の中心またはその周りに配置された主要点を保持するマクロブロックのサイズは、画像の周辺に配置された主要点を保持するマクロブロックよりも大きい。１実施形態では、位置情報の行列表現が、画像の中心およびその周りに配置された主要点を提供するための、第１の数、例えば図６の説明によれば３個、または、他の任意の数のＭＢ＿Ｓｉｚｅの大きさのマクロブロックと、画像の周辺に配置された主要点を提供するための、第２の数、例えば図６の説明によれば１４個、または、他の任意の数の、マクロブロックの一部、例えば、図６の説明によればＭＢ＿Ｓｉｚｅの４分の１またはＭＢ＿Ｓｉｚｅの任意の割合のマクロブロックとを含む。１実施形態では、第１の数のＭＢ＿Ｓｉｚｅの大きさのマクロブロックを画像にわたって固定する。代替的な実施形態では、第１の数のＭＢ＿Ｓｉｚｅの大きさのマクロブロックは圧縮画像の行列表現のサイズ、特に、行列表現の列または行の数に依存する。
【００９６】
１実施形態では、ｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋビット・シーケンスを使用して、位置情報を保持しない行列表現の空のマクロブロックを特定する。図６によれば、ｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋビット・シーケンス｛１、０、１、１、１、１、１、１、１、１、０、０、１、１｝は、ＭＢ＿Ｓｉｚｅの何分の１かの大きさの第２の数のマクロブロックのうち空のマクロブロックを示し、「１」は非空マクロブロックを、「０」は空のマクロブロックを示す。
【００９７】
復号器は、逆の操作を逆順に適用する。１実施形態では、復号器は、画像の外縁に位置する主要点から画像の中心に配置された主要点へまたはその逆に行列表現の要素を逐次的に通過する１組の主要点の位置情報の行列表現を解凍する。当該画像の各主要点は記述子により記述され、当該記述子は、画像内の主要点の位置を示す位置情報を含み、局所的特徴が当該主要点を囲む有向パッチから計算される。
【００９８】
図８は、１実施形態に従う位置情報圧縮方法２０３の略図を示し、以下では第２の実施形態と称する。
【００９９】
画像圧縮方法２０３は、図７に関して説明したステップ２１１、２１２、２１４、２１６、２１７、２２０および２４０を含み、別の行列表現の生成ステップ２１２と適合的ブロック・ベース分析２１４の間に空要素を排除する任意のステップ２１３をさらに含む。
【０１００】
別の行列表現を生成するステップ２１２の後、空の領域を排除するための新たな方法を適用する。空の行と列が排除される上述のような参照モデルの解決策と対称的に、ここで説明する方法は、新たな行列表現の構築中に空の同心円環を特定することである。符号化されたビット・ストリームでは、同心円環が空であるか否かを示すために１ビットを使用する。ここで提供するアプローチの利点は、画像内の行および列ごとに１ビットを使用するのではなく、（その数が、小さい行列次元の半分に等しい）同心円環ごとに１ビットのみが使用されるということである。
【０１０１】
図８から分かるように、空要素を排除する追加のステップ２１３では、空の同心円環の排除が上述のように行われる。１実施形態では、空要素を排除するステップ２１３では、図３の説明に従って空要素が局所的特徴を保持しない画像の同心円環に対応する圧縮画像の行列表現の空要素を排除する。復号器は、逆の操作を逆順に適用する。
【０１０２】
図９は、１実施形態に従う位置情報圧縮方法２０４の略図を示し、以下では第３の実施形態と称する。
【０１０３】
画像圧縮方法２０４は、図８に関して説明したステップ２１１、２１２、２１３、２１４、２１６、２１７、２２０および２４０を含み、さらに、適合的ブロック・ベース分析のステップ２１４の後にブロックごとの非空要素の数に基づくコンテキストを生成する任意のステップ２１５を含む。コンテキストを生成するステップ２１５の結果が、行列要素の算術エントロピ符号化のステップ２１７に入力される。
【０１０４】
第３の実施形態では、コンテキスト・モデリングを適用して、緩やかな複雑度の増大を犠牲にして圧縮効率を優先する。２つの異なるコンテキスト・モデルを適用することができる。第１の実施形態では、コンテキスト・モデリングをマクロブロックに対して、新たな行列表現の同一位置にあるマクロブロックに対応するトレーニング・セット内の非空セルの平均数に基づいて適用する。当該アプローチは、位置が予め分かっているので、圧縮されたビット・ストリーム内に余分なビットは不要であるという利点がある。第２の実施形態では、コンテキスト・モデリングが、現在分析されているマクロブロック内の要素の数に基づいて適用される。このケースでは、各マクロブロック内の非空セルの数を送信するために、圧縮されたビット・ストリームにおいて余分なビットを費やす必要がある。
【０１０５】
１実施形態では、図７に関して説明したエントロピ符号化したｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋビット・シーケンスと圧縮画像の行列表現の非空マクロブロックのエントロピ符号化した位置情報を結合することによって、圧縮行列を提供する。当該位置情報は、図９のステップ２１５で示したように非空マクロブロック内の非空要素の平均数を利用するコンテキスト・モデルを用いることによってエントロピ符号化される。復号器は逆の操作を逆順に適用する。
【０１０６】
図１０は、１実施形態に従う、画像の位置情報を当該画像の１組の主要点の位置情報の行列表現から再構築するための方法１０００の略図を示す。
【０１０７】
方法１０００は、当該画像の１組の主要点の位置情報の行列表現を所定の順序に従って解凍するステップ１００１を含む。当該画像の局所的特徴は当該主要点を囲む有向パッチから計算される。
【０１０８】
１実施形態では、方法１０００はさらに、ｓｋｉｐ−Ｍａｃｒｏｂｌｏｃｋビットをエントロピ復号化するステップを含む。１実施形態では、方法１０００はさらに、非空セルに関連する位置情報をエントロピ復号化するステップを含む。
【０１０９】
図１１は、１実施形態に従う位置情報符号化器１１００のブロック図を示す。位置情報符号化器１１００は、図１乃至９に関して説明した方法の１つを実施する、即ち、１組の主要点を当該画像から提供し、当該１組の主要点の位置情報を二値行列の形で記述し、当該二値行列を所定の順序に従って走査することによって、当該１組の主要点の当該位置情報の新規表現を生成するように構成されたプロセッサ１１０１を備える。１実施形態では、プロセッサ１１０１は、当該１組の主要点の位置情報の当該新規表現を別の二値行列の形または別の適切な形で出力するように構成される。
【０１１０】
１実施形態では位置情報符号化器１１００は、画像の中心に配置された要素から始まり当該画像の外縁に配置された要素へまたはその逆へ向かってヒストグラム・マップ行列を走査して新たな行列表現を提供し、以下のステップ、即ち、適合的ブロック分析とエントロピ符号化を適用して圧縮された記述子の位置情報を取得するようにさらに構成される。
【０１１１】
図１１は、画像をその入力１１０３で受信し位置情報のみをその出力１１０５で提供する位置情報符号化器１１００を示す。しかし、他の様々な情報、例えば記述子等をその出力１１０５で提供することができる。
【０１１２】
図１２は、１実施形態に従う位置情報復号器１２００のブロック図を示す。画像復号器１２００は、図１０に関して説明した方法を実施する、即ち、当該画像の１組の主要点の位置情報の行列表現を所定の順序に従って解凍することによって当該画像の局所的特徴を当該画像の１組の主要点の位置情報の行列表現から再構築するように構成されたプロセッサ１２０１を備える。当該画像の当該局所的特徴は当該主要点を囲む有向パッチから計算される。
【０１１３】
図１２は位置情報をその入力１２０３で受信するのみである位置情報復号器１２００を示す。しかし、他の様々な情報、例えば、記述子等をその入力で受信することができる。
【０１１４】
以上から、様々な方法、システム、記録媒体上のコンピュータ・プログラム等が提供されることは当業者には明らかである。
【０１１５】
本発明はまた、実行されたときに少なくとも１つのコンピュータに本明細書で説明した諸ステップの実施と計算を実行させる、コンピュータ実行可能コードまたはコンピュータ実行可能命令を含むコンピュータ・プログラム製品もサポートする。
【０１１６】
本発明はまた、本明細書で説明した諸ステップの実施と計算を実行するように構成されたシステムもサポートする。
【０１１７】
以上の教示事項に鑑みて、多数の代替物、修正物、および変形は当業者には明らかである。勿論、本明細書の開示事項を超える多数の本発明の適用があることは当業者には容易に理解される。１つまたは複数の特定の実施形態を参照して本発明を説明したが、本発明の範囲を逸脱しない多数の変更を加えうることは当業者には理解される。したがって、添付の特許請求の範囲およびその均等物において、本発明を本明細書で具体的に説明したもの以外で実施してもよいことは理解される。
【符号の説明】
【０１１８】
１５０１  クライアント
１５０３  サーバ
１５０５  主要点識別
１５０７  特徴計算
１５０９  特徴選択
１５１１  符号化
１５１３  マッチング
１５１９  復号化
１５２３  主要点識別
１５２５  特徴計算
１５２７  幾何的一貫性チェック
【図１】
0005962937.tif 000002
【図２】
0005962937.tif 000003
【図３】
0005962937.tif 000004
【図４】
0005962937.tif 000005
【図５】
0005962937.tif 000006
【図６】
0005962937.tif 000007
【図７】
0005962937.tif 000008
【図８】
0005962937.tif 000009
【図９】
0005962937.tif 000010
【図１０】
0005962937.tif 000011
【図１１】
0005962937.tif 000012
【図１２】
0005962937.tif 000013
【図１３】
0005962937.tif 000014
【図１４】
0005962937.tif 000015
【図１５】
0005962937.tif 000016
【図１６】
0005962937.tif 000017