(57)【要約】  画像を処理するための方法が記載される。カレントピクセルのためのマスクビットが決定される。マスクビットは、カレントピクセルと複数の隣接ピクセルとの強度比較を示す。マスクビットは、カレントピクセルの隣接ピクセルのおのおのが処理されたか否かをも示し得る。次のピクセルが、マスクビットに基づいて、処理のために選択される。
2016504698.tif 000002
【特許請求の範囲】
【請求項１】
画像を処理するための方法であって、
カレントピクセルのために、前記カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定することと、ここで、前記マスクビットは、前記カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す、
処理するための次のピクセルを、前記マスクビットに基づいて選択することと、を備える、方法。
【請求項２】
前記選択することは、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスすることを備える、請求項１に記載の方法。
【請求項３】
前記選択することは、さらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択することを備える、請求項２に記載の方法。
【請求項４】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項１に記載の方法。
【請求項５】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項１に記載の方法。
【請求項６】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項１に記載の方法。
【請求項７】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または直交的に隣接する、請求項１に記載の方法。
【請求項８】
前記カレントピクセルが、処理されていない隣接ピクセルを有していない場合、前記カレントピクセルを、極値領域の一部として分類すること、をさらに備える、請求項１に記載の方法。
【請求項９】
前記カレントピクセルを、輪郭の一部として分類すること、をさらに備える、請求項１に記載の方法。
【請求項１０】
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理すること、をさらに備える、請求項１に記載の方法。
【請求項１１】
前記画像は、ビデオ内のフレームであり、前記方法は、前記ビデオ内のすべてのフレームに対して実行される、請求項１に記載の方法。
【請求項１２】
画像を処理するための装置であって、
カレントピクセルのために、前記カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定するための手段と、ここで、前記マスクビットは、前記カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す、
処理するための次のピクセルを、前記マスクビットに基づいて選択するための手段と、を備える装置。
【請求項１３】
前記選択するための手段は、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスするための手段を備える、請求項１２に記載の装置。
【請求項１４】
前記選択するための手段はさらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択するための手段を備える、請求項１３に記載の装置。
【請求項１５】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項１２に記載の装置。
【請求項１６】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項１２に記載の装置。
【請求項１７】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項１２に記載の装置。
【請求項１８】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、請求項１２に記載の装置。
【請求項１９】
前記カレントピクセルが、処理されていない隣接ピクセルを有していない場合、前記カレントピクセルを、極値領域の一部として分類するための手段、をさらに備える、請求項１２に記載の装置。
【請求項２０】
前記カレントピクセルを、輪郭の一部として分類するための手段、をさらに備える、請求項１２に記載の装置。
【請求項２１】
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理するための手段、をさらに備える、請求項１２に記載の装置。
【請求項２２】
前記画像は、ビデオ内のフレームであり、前記装置は、前記ビデオ内のすべてのフレームを処理する、請求項１２に記載の装置。
【請求項２３】
画像を処理するための電子デバイスであって、
プロセッサと、
前記プロセッサと電子通信するメモリと、
前記メモリに記憶された命令とを備え、前記命令は、
カレントピクセルのために、前記カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定し、ここで、前記マスクビットは、前記カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す、
処理するための次のピクセルを、前記マスクビットに基づいて選択するように実行可能である、電子デバイス。
【請求項２４】
前記選択するように実行可能な命令は、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスするように実行可能な命令を備える、請求項２３に記載の電子デバイス。
【請求項２５】
前記選択するように実行可能な命令はさらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択するように実行可能な命令をさらに備える、請求項２４に記載の電子デバイス。
【請求項２６】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項２３に記載の電子デバイス。
【請求項２７】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項２３に記載の電子デバイス。
【請求項２８】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項２３に記載の電子デバイス。
【請求項２９】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、請求項２３に記載の電子デバイス。
【請求項３０】
前記カレントピクセルが、処理されていない隣接ピクセルを有していない場合、前記カレントピクセルを、極値領域の一部として分類するように実行可能な命令、をさらに備える、請求項２３に記載の電子デバイス。
【請求項３１】
前記カレントピクセルを、輪郭の一部として分類するように実行可能な命令、をさらに備える、請求項２３に記載の電子デバイス。
【請求項３２】
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理するように実行可能な命令、をさらに備える、請求項２３に記載の電子デバイス。
【請求項３３】
前記画像は、ビデオ内のフレームであり、前記電子デバイスは、前記ビデオ内のすべてのフレームを処理する、請求項２３に記載の電子デバイス。
【請求項３４】
画像を処理するためのコンピュータプログラム製品であって、命令を有する非一時的なコンピュータ読取可能な媒体を備え、前記命令は、
電子デバイスに対して、カレントピクセルのために、前記カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定させるためのコードと、ここで、前記マスクビットは、前記カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す、
前記電子デバイスに対して、処理するための次のピクセルを、前記マスクビットに基づいて選択させるためのコードとを備える、コンピュータプログラム製品。
【請求項３５】
前記電子デバイスに対して選択させるための前記コードは、前記電子デバイスに対して、マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスさせるためのコードを備える、請求項３４に記載のコンピュータプログラム製品。
【請求項３６】
前記電子デバイスに対して、選択させるための前記コードは、前記電子デバイスに対して、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択させるためのコードをさらに備える、請求項３５に記載のコンピュータプログラム製品。
【請求項３７】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項３４に記載のコンピュータプログラム製品。
【請求項３８】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項３４に記載のコンピュータプログラム製品。
【請求項３９】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項３４に記載のコンピュータプログラム製品。
【請求項４０】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、請求項３４に記載のコンピュータプログラム製品。
【請求項４１】
前記カレントピクセルが、処理されていない隣接ピクセルを有していない場合、前記電子デバイスに対して、前記カレントピクセルを、極値領域の一部として分類させるためのコード、をさらに備える、請求項３４に記載のコンピュータプログラム製品。
【請求項４２】
前記電子デバイスに対して、前記カレントピクセルを、輪郭の一部として分類させるためのコード、をさらに備える、請求項３４に記載のコンピュータプログラム製品。
【請求項４３】
前記電子デバイスに対して、ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理させるためのコード、をさらに備える、請求項３４に記載のコンピュータプログラム製品。
【請求項４４】
前記画像は、ビデオ内のフレームであり、前記電子デバイスは、前記ビデオ内のすべてのフレームを処理する、請求項３４に記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
[0001]本願は、「ＤＥＴＥＣＴＩＮＧ  ＭＡＸＩＭＡＬＬＹ  ＳＴＡＢＬＥ  ＥＸＴＲＥＭＡＬ  ＲＥＧＩＯＮＳ  ＩＮ  ＡＮ  ＩＭＡＧＥ」のために２０１３年１月３０日に出願された米国仮特許出願第６１／７５８，６６５号に関連し、同出願の優先権を主張する。
【０００２】
[0002]本開示は、一般に、電子デバイスに関する。さらに詳しくは、本開示は、画像を処理するためのシステムおよび方法に関する。
【背景技術】
【０００３】
[0003]最近の数十年間で、電子デバイスの使用は一般化した。特に、電子技術の進歩は、ますます複雑かつ有用となった電子デバイスのコストを低減してきた。コスト低減と顧客需要とは、電子デバイスが、現代社会において現実にユビキタスとなるように、その使用を急増させた。電子デバイスの使用が拡大したので、電子デバイスの、新たな、かつ改善された機能のための需要がある。さらに詳しくは、新たな機能を実行する、および／または、機能をより高速に、より効率的に、または、より高い品質で実行する電子デバイスが、しばしば必要とされている。
【０００４】
[0004]いくつかの電子デバイス（たとえば、カメラ、ビデオカムコーダ、デジタルカメラ、セルラー電話、スマートフォン、コンピュータ、テレビ等）は、画像をキャプチャまたは利用する。たとえば、デジタルカメラは、デジタル画像をキャプチャし得る。
【０００５】
[0005]電子デバイスの新しい特徴および（または）改善された特徴がしばしば求められる。この議論から観察され得るように、電子デバイスの新たなおよび／または改善された特徴を加えるシステムおよび方法は有益であり得る。
【図面の簡単な説明】
【０００６】
【図１】[0006]画像を処理するための電子デバイスを例示するブロック図。
【図１Ａ】[0007]プロセッサによって実施される図１のシステム内のいくつかの構成要素を例示する図。
【図２】[0008]画像を処理するための方法を例示するフロー図。
【図３】[0009]画像を処理するためのより詳細な方法を例示するフロー図。
【図４】[0010]画像を処理するための方法の別の構成を例示するフロー図。
【図５Ａ】[0011]１つまたは複数の極値領域が検出され得る画像を処理するためのステップを例示するブロック図。
【図５Ｂ】１つまたは複数の極値領域が検出され得る画像を処理するためのステップを例示するブロック図。
【図５Ｃ】１つまたは複数の極値領域が検出され得る画像を処理するためのステップを例示するブロック図。
【図５Ｄ】１つまたは複数の極値領域が検出され得る画像を処理するためのステップを例示するブロック図。
【図５Ｅ】１つまたは複数の極値領域が検出され得る画像を処理するためのステップを例示するブロック図。
【図５Ｆ】１つまたは複数の極値領域が検出され得る画像を処理するためのステップを例示するブロック図。
【図５Ｇ】１つまたは複数の極値領域が検出され得る画像を処理するためのステップを例示するブロック図。
【図５Ｈ】１つまたは複数の極値領域が検出され得る画像を処理するためのステップを例示するブロック図。
【図５Ｉ】１つまたは複数の極値領域が検出され得る画像を処理するためのステップを例示するブロック図。
【図６】[0012]本明細書に記載されたシステムおよび方法に従う隣接マップを例示するブロック図。
【図７】[0013]電子デバイス／ワイヤレスデバイス内に含まれ得るいくつかの構成要素を例示する図。
【発明の概要】
【０００７】
[0014]画像を処理するための方法が記載される。この方法は、カレントピクセルのために、カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定することを含む。マスクビットは、カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す。この方法はまた、処理するための次のピクセルを、マスクビットに基づいて選択することを含む。
【０００８】
[0015]選択することは、マスクビットを、ルックアップテーブル内のインデクスとして用いて、ルックアップテーブル内のデータにアクセスすることを含み得る。選択することはまた、カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択すること、を含み得る。
【０００９】
[0016]マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを含み得る。隣接ピクセルは、カレントピクセルに対して直交的に隣接し得る。隣接ピクセルは、カレントピクセルに対して対角的に隣接し得る。隣接ピクセルは、カレントピクセルに対して対角的に隣接し得るか、または、直交的に隣接し得る。
【００１０】
[0017]この方法は、カレントピクセルが、処理されていない隣接ピクセルを有していない場合、カレントピクセルを、極値領域の一部として分類することを含み得る。この方法は、カレントピクセルを輪郭の一部として分類することを含み得る。
【００１１】
[0018]この方法は、ピクセルとその隣接ピクセルの各々との強度比較を実行することによって、画像内の各ピクセルを前処理することを含み得る。この画像は、ビデオにおけるフレームであり得る。この方法は、ビデオにおけるすべてのフレームのために実行され得る。
【００１２】
[0019]画像を処理するための装置も記載される。この装置は、カレントピクセルのために、カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定するための手段を含む。マスクビットはまた、カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す。この装置はまた、処理するための次のピクセルを、マスクビットに基づいて選択するための手段を含む。
【００１３】
[0020]画像を処理するための電子デバイスも記載される。この電子デバイスは、プロセッサと、プロセッサと電子通信するメモリと、メモリに記憶された命令とを含んでいる。この命令は、カレントピクセルのために、カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定するように実行可能である。マスクビットはまた、カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す。この命令はまた、処理するための次のピクセルを、マスクビットに基づいて選択するように実行可能である。
【００１４】
[0021]画像を処理するためのコンピュータプログラム製品も記載される。このコンピュータプログラム製品は、命令を有する非一時的なコンピュータ読取可能な媒体を含んでいる。この命令は、電子デバイスに対して、カレントピクセルのために、カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定させるためのコードを含んでいる。マスクビットはまた、カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す。この命令また、電子デバイスに対して、処理するための次のピクセルを、マスクビットに基づいて選択させるためのコードを含んでいる。
【発明を実施するための形態】
【００１５】
[0022]最大安定極値領域（ＭＳＥＲ）は、その高い反復性により、および、その他多くの一般に使用されている領域検出器に対して相補的であることにより、一般に使用される領域検出器のタイプになった。ＭＳＥＲ検出器は、広いベースラインステレオ、物体認識、画像検索、シーン分類等を含む様々なコンピュータビジョンアプリケーションに正しく適用された。したがって、迅速かつ正確にＭＳＥＲを検出することが所望され得る。
【００１６】
[0023]極値領域は、その強度のすべてが、この領域を囲むすべてのピクセルの強度よりも一様に大きいまたは小さいという特性を満足する４つの隣接（東、南、西、および北）によって接続されているピクセルのセットである。所与の強度ｉおよびマージンΔについて、ｉ−Δからｉ＋Δへの領域内のピクセル数の変化がローカル最小値であれば、極値領域は、最大に安定する。
【００１７】
[0024]既知のソリューションに従って、ＭＳＥＲは、その進行が景色に適合する物理的なフラッドフィルとして記載され得るアルゴリズムによって抽出され得る。すべてのピクセルに対して、支配的な動作は、隣接ピクセルが処理されたか否かをチェックしており、ピクセルの強度を、隣接ピクセルの強度と比較している。このアルゴリズムは、ピクセルの数において、既に線形時間にあるが、その計算上の複雑さは未だに比較的高い。それは、コンピュータビジョンアプリケーションが、モバイルプロセッサにおけるリアルタイムパフォーマンスを達成することを困難にする。したがって、いくつかの妥協がなされ得る。たとえば、光学式文字認識（ＯＣＲ）では、入力画像は、ＭＳＥＲの抽出のために空間的および時間的の両方でダウンサンプルされ得る。たとえば、３０フレーム／秒（ｆｐｓ）の入力画像におけるビデオグラフィックアレイ（ＶＧＡ）は、ＭＳＥＲの抽出のために、空間的（たとえば、ＶＧＡから１／４ＶＧＡ（ＱＶＧＡ）へ）および時間的（３０ｆｐｓから６ｆｐｓへ）の両方でダウンサンプルされ得る。これらの妥協は、認識精度を低減し得るのみならず、ユーザ経験をも低下させ得る。したがって、ＭＳＥＲを抽出するリアルタイムパフォーマンスを改善することはまた、コンピュータビジョンアプリケーションをも改善し得る。
【００１８】
[0025]さまざまな構成が、同一の参照番号が機能的に類似の要素を示し得る図面を参照して記載される。本明細書において一般的に記載され図面で例示されているようなシステムおよび方法は、広範なさまざまな別の構成でアレンジおよび設計され得る。したがって、これら図面において示されるような、以下に示すいくつかの構成のより詳細な記載は、特許請求されたような範囲を限定することではなく、単に、これらシステムおよび方法の代表であることが意図されている。
【００１９】
[0026]図１は、画像１１４を処理するための電子デバイス１０２を例示するブロック図である。電子デバイス１０２はまた、ワイヤレス通信デバイス、モバイルデバイス、移動局、加入者局、クライアント、クライアント局、ユーザ機器（ＵＥ）、遠隔局、アクセス端末、モバイル端末、端末、ユーザ端末、加入者ユニット等とも称され得る。電子デバイス１０２の例は、ラップトップまたはデスクトップのコンピュータ、セルラー電話、スマートフォン、ワイヤレスモデム、ｅリーダ、タブレットデバイス、ゲームシステム等を含んでいる。これらのデバイスのうちのいくつかは、１つまたは複数の業界規格に従って動作し得る。
【００２０】
[0027]スマートフォンまたはタブレットコンピュータのような電子デバイス１０２は、カメラを含み得る。カメラは、画像センサ１０４、および、光学系１０６の視野内に位置する物体の画像１１４を、画像センサ１０４にフォーカスさせる光学系１０６（たとえばレンズ）を含み得る。電子デバイス１０２はまた、カメラソフトウェアアプリケーションおよびディスプレイ１０８を含み得る。カメラソフトウェアアプリケーションが動作している場合、光学系１０６の視野内に位置する物体の画像１１４が、画像センサ１０４によって記録され得る。
【００２１】
[0028]画像センサ１０４によって記録されている画像１１４はディスプレイ１０８上に表示され得る。これらの画像１１４は、任意の所定の瞬間において、光学系１０６の視野内に位置する物体が、ディスプレイ１０８（たとえば、ディスプレイスクリーン、タッチスクリーン等）上に表示されるように、比較的高いフレームレートで、迅速に連続的に表示され得る。本システムおよび方法は、キャプチャされたビデオフレームの観点から記載されているが、本明細書に記載された技術は、任意のデジタル画像１１４上で使用され得る。したがって、ビデオフレームおよびデジタル画像という用語は、本明細書において相互置換的に使用され得る。ユーザインターフェース１１０は、ユーザが、電子デバイス１０２とインタラクトすることを可能にし得る。
【００２２】
[0029]画像１１４（たとえば、デジタル画像、キャプチャされたビデオフレーム等）内の領域（たとえば、最大安定極値領域（ＭＳＥＲ）１２４）を識別することが所望され得る。本明細書で使用されるように、最大安定極値領域（ＭＳＥＲ）は「極値領域」１２４と称される。画像１１４中のテキストを識別するために、極値領域１２４が光学式文字認識（ＯＣＲ）アプリケーションによって使用され得る。言い換えれば、１つまたは複数の極値領域１２４が識別され、その後、その中で、テキストが発見される。領域検出器１１２が、画像１１４中の極値領域１２４を識別し得る。ビデオシナリオでは、領域検出は、キャプチャされたビデオ中に、すべてのフレームについて、または散発的に実行され得る。さらに、領域検出は、任意の解像度（たとえば、ＶＧＡ、ＱＶＧＡ等）において画像１１４のために実行され得る。
【００２３】
[0030]画像１１４は、ピクセル１１６のグリッドであり得る。１つの構成では、ピクセル１１６は、ピクセル１１６に直交的に隣接している隣接ピクセル１１６を有し得る。直交的に隣接した隣接ピクセル１１６は、本明細書において、ピクセル１１６に対する方向関係（たとえば、東（Ｅ）、南（Ｓ）、西（Ｗ）、または北（Ｎ））によって示される。この構成では、コーナピクセル１１６が、２つの隣接ピクセル１１６を有し、エッジピクセル１１６が、３つの隣接ピクセル１１６を有し、内部（たとえば、非コーナ、非エッジ）ピクセル１１６が、４つの隣接ピクセル１１６を有し得る。本明細書で使用されるように、隣接ピクセル１１６は、ピクセル１１６に対する方向関係（たとえば、隣接Ｅ、隣接Ｓ等）によって指定され得る。
【００２４】
[0031]別の構成では、ピクセル１１６は、ピクセル１１６に対角的に隣接している隣接ピクセル１１６を有し得る。対角的に隣接した隣接ピクセル１１６は、本明細書において、ピクセル１１６に対するその方向関係（たとえば、北東（ＮＥ）、南東（ＳＥ）、南西（ＳＷ）、または北西（ＮＷ））によって示される。この構成では、コーナピクセル１１６が、１つの隣接ピクセル１１６を有し、エッジピクセル１１６が、２つの隣接ピクセル１１６を有し、内部（たとえば、非コーナ、非エッジ）ピクセル１１６が、４つの隣接ピクセル１１６を有し得る。
【００２５】
[0032]また別の構成では、ピクセル１１６は、ピクセル１１６に対して直交的または対角的に隣接している隣接ピクセル１１６を有し得る。この構成では、コーナピクセル１１６が、３つの隣接ピクセル１１６を有し、エッジピクセル１１６が、５つの隣接ピクセル１１６を有し、内部（たとえば、非コーナ、非エッジ）ピクセル１１６が、８つの隣接ピクセル１１６を有し得る。
【００２６】
[0033]本システムおよび方法は、処理するための次のピクセル１１６を選択するために、すべてのピクセル１１６に関連付けられたマスクビット１１８を使用し得る。マスクビット１１８は、各隣接ピクセル１１６の比較ビットおよび処理ビットを含み得る。比較ビットは、ピクセル１１６と隣接ピクセル１１６との強度比較を示し得る。たとえば、ピクセル１１６の西側隣接（たとえば、隣接Ｗ）に関連付けられた比較ビットは、ピクセル１１６の強度が、隣接Ｗの強度よりも高いことを示し得る。
【００２７】
[0034]処理ビットは、カレントピクセル１１６の隣接ピクセル１１６の各々が処理されたか否かを示し得る。たとえば、ピクセル１１６の隣接Ｗに関連付けられた処理ビットは、隣接Ｗが処理されたことを示し得る一方、隣接Ｓに関連付けられた別の処理ビットは、隣接Ｓが処理されていないことを示し得る。本明細書で使用されるように、「処理」および／または「処理すること」という用語は、ピクセル１１６に関連付けられた隣接ピクセル１１６の１つまたは複数のマスクビット１１８の修正を称し得る。
【００２８】
[0035]領域検出器１１２は、画像１１４における極値領域１２４を検出し得る。領域検出器１１２は、ハードウェア（たとえば、回路）、ソフトウェア、またはこれら両方の組合せで実現され得る。図１に例示された要素のうちの１つまたは複数は、いくつかの構成において、回路（たとえば、集積回路）で実現され得ることがまた注目されるべきである。
【００２９】
[0036]１つの構成では、画像１１４内の各ピクセル１１６を前処理することによって、ピクセル１１６とその隣接ピクセル１１６の各々との強度比較が実行され得る。前処理中に、領域検出器１１２は、隣接ピクセル１１６に対するピクセル１１６の相対強度に基づいて、各ピクセル１１６の比較ビットを設定し得る。
【００３０】
[0037]領域検出器１１２は、処理のためのカレントピクセル１１６として、ピクセル１１６を選択し得る。領域検出器１１２は、マスクビット１１８に基づいて、処理するための次のピクセル１１６を選択し得る。たとえば、マスクビット１１８は、カレントピクセル１１６の隣接ピクセル１１６の何れかが、未処理かつ、カレントピクセル１１６よりも低い強度であるか否かを示し得る。領域検出器１１２は、未処理かつ低い強度の隣接ピクセル１１６を、処理するための次のピクセル１１６として選択し得る。１つの構成では、マスクビット１１８は、処理するための次のピクセル１１６を選択するために、ルックアップテーブル１２２内のデータにアクセスするためのインデクスとして使用され得る。
【００３１】
[0038]ピクセル１１６が処理されると、カレントピクセル１１６または隣接ピクセル１１６は、ヒープ１２０上にキュー（たとえば、保存）され得る。ヒープ１２０は、現在の部分的な極値領域１２４の境界ピクセル１１６を保持し得る。カレントピクセル１１６の隣接ピクセル１１６がすべてが処理されると、最小強度（たとえば、グレーレベル）を有するピクセル１１６が、ヒープ１２０からポップアウト（たとえば、取得）され、処理のための次のピクセル１１６として設定され得る。
【００３２】
[0039]カレントピクセル１１６が、未処理の隣接ピクセル１１６を有していない場合、領域検出器１１２は、極値領域１２４の一部として、カレントピクセル１１６を分類し得る。たとえば、マスクビット１１８は、カレントピクセル１１６の隣接ピクセル１１６の各々が処理されていることを示し得る。さらに、または、その代わりに、領域検出器１１２は、カレントピクセル１１６を輪郭の一部として分類し得る。
【００３３】
[0040]図１Ａに図示されるように、領域検出器１１２は、プロセッサ１０１によって実現され得る。その代わりに、異なる構成要素を実現するために異なるプロセッサが使用され得る（たとえば、１つのプロセッサが、マスクビット１１８を決定し、別のプロセッサがヒープ１２０を決定するために使用され、さらに別のプロセッサが、極値領域１２４を判定するために使用され得る）。
【００３４】
[0041]図２は、画像１１４を処理するための方法２００を例示するフロー図である。方法２００は、電子デバイス１０２によって実行され得る。方法２００は、画像１１４における極値領域１２４を発見するために使用され得る。電子デバイス１０２は、カレントピクセル１１６のために、カレントピクセル１１６と、複数の隣接ピクセル１１６との強度比較を示すマスクビット１１８を決定２０２し得る。ピクセル１１６の強度は、ピクセル１１６のグレーレベルに相当し得る。ピクセル１１６とその隣接ピクセル１１６の各々との強度比較は、画像１１４における各ピクセル１１６を前処理することによって実行され得る。マスクビット１１８は、各隣接ピクセル１１６に関連付けられた比較ビットを含み得る。前処理中、電子デバイス１０２は、ピクセル１１６の、その隣接ピクセル１１６への相対強度に基づいて、各ピクセル１１６の比較ビットを設定し得る。
【００３５】
[0042]１つの構成では、隣接ピクセル１１６は、ピクセル１１６に直交的に隣接（たとえば、Ｅ、Ｓ、Ｗ、またはＮ）している。この構成では、電子デバイス１０２は、前処理中に、各ピクセル１１６の隣接Ｅ、隣接Ｓ、隣接Ｗ、および隣接Ｎに対応する比較ビットを設定し得る。
【００３６】
[0043]別の構成では、隣接ピクセル１１６は、ピクセル１１６に対角的に隣接している（たとえば、ＮＥ、ＳＥ、ＳＷ、またはＮＷ）。この構成では、電子デバイス１０２は、前処理中に、各ピクセル１１６の隣接ＮＥ、隣接ＳＥ、隣接ＳＷ、および隣接ＮＷに対応する比較ビットを設定し得る。
【００３７】
[0044]また別の構成では、隣接ピクセル１１６は、カレントピクセル１１６に対して直交的に隣接（たとえば、Ｅ、Ｓ、Ｗ、またはＮ）しているか、または対角的に隣接（たとえば、ＮＥ、ＳＥ、ＳＷ、またはＮＷ）している。この構成では、電子デバイス１０２は、前処理中に、各ピクセル１１６の隣接ＮＥ、隣接Ｅ、隣接ＳＥ、隣接Ｓ、隣接ＳＷ、隣接Ｗ、隣接ＮＷ、および隣接Ｎに対応する比較ビットを設定し得る。
【００３８】
[0045]電子デバイス１０２は、カレントピクセル１１６のために、カレントピクセル１１６の隣接ピクセル１１６の各々が処理されたか否かを示すマスクビット１１８を決定２０４し得る。１つの構成では、マスクビット１１８は、隣接ピクセル１１６が処理されたか否かを示す処理ビットを含み得る。カレントピクセル１１６が処理された場合、隣接ピクセル１１６の処理ビットは、カレントピクセル１１６が処理されたことを示すように更新される。
【００３９】
[0046]電子デバイス１０２は、マスクビット１１８に基づいて、処理するための次のピクセル１１６を選択２０６し得る。１つの実施では、処理のための最初のカレントピクセル１１６は、ランダムに選択され得るか、前の画像１１４における極値領域１２４のうちの１つまたは複数の場所に基づき得るか、または、事前に設定されたピクセル１１６（たとえば、画像１１４のコーナピクセル１１６）であり得る。カレントピクセル１１６のマスクビット１１８は、カレントピクセル１１６の隣接ピクセル１１６の何れかが、未処理でかつ、カレントピクセル１１６よりも低い強度であるか否かを示し得る。電子デバイス１０２は、未処理で、低い強度の隣接ピクセル１１６を、処理するための次のピクセル１１６として選択２０６し得る。
【００４０】
[0047]１つの構成では、マスクビット１１８は、処理するための次のピクセル１１６を選択２０６するために、ルックアップテーブル１２２内のデータにアクセスするためのインデクスとして使用され得る。たとえば、ルックアップテーブル１２２は事前計算され、電子デバイス１０２内に記憶され得る。ルックアップテーブル１２２は、マスクビット１１８の値に対応するデータ（たとえば、リストまたはアレイ）を含み得る。ルックアップテーブル１２２は、インデクス（たとえば、入力）としてマスクビット１１８を用いて、電子デバイス１０２に対して、処理するための次のピクセル１１６としてどのピクセル１１６を選択２０６するかに関して指示し得る。
【００４１】
[0048]隣接ピクセル１１６が処理されたことをマスクビット１１８が示すのであれば、ルックアップテーブル１２２は、電子デバイス１０２に対して、処理するために別の隣接ピクセル１１６を選択２０６するように指示し得る。すべての隣接ピクセル１１６が処理されたことをマスクビット１１８が示すのであれば、カレントピクセル１１６は、極値領域１２４の一部として分類され、処理されるべき次のピクセル１１６が、ヒープ１２０から選択２０６され得る。
【００４２】
[0049]図３は、画像１１４を処理するためのより詳細な方法３００を例示するフロー図である。方法３００は、電子デバイス１０２によって実行され得る。画像１１４は、ピクセル１１６のグリッドであり得る。図３の方法３００に例示される構成では、隣接ピクセル１１６は、ピクセル１１６に直交的に隣接（たとえばＥ、Ｓ、Ｗ、またはＮ）している。方法３００では、カレントピクセル１１６（「カレントピクセルＸ」として示される）が選択され得る。そして、カレントピクセル１１６の各隣接ピクセル１１６が既に処理されているか否かが判定される。
【００４３】
[0050]本システムおよび方法は、極値領域１２４内の各ピクセル１１６が、極値領域１２４を囲む各ピクセル１１６の強度よりも高い強度を有するという特性を満足する極値領域１２４を検出する、ＭＳＥＲ＋アルゴリズムの観点から記載されていることが注目されるべきである。しかしながら、本システムおよび方法はまた、極値領域１２４内の各ピクセル１１６が、極値領域１２４を囲む各ピクセル１１６の強度よりも低い強度を有する極値領域１２４を検出する、ＭＳＥＲ−アルゴリズムをも実施し得る。
【００４４】
[0051]ＭＳＥＲ＋およびＭＳＥＲ−のアルゴリズムは、ピクセル強度の比較を除いて類似している。たとえば、ＭＳＥＲ＋を用いて、アルゴリズムは、東隣接ピクセル１１６がカレントピクセル１１６よりも低い強度（たとえば、Ｅ＜Ｘ）であるか、南隣接ピクセル１１６がカレントピクセル１１６よりも低い強度（たとえば、Ｓ＜Ｘ）であるか、西隣接ピクセル１１６がカレントピクセル１１６よりも低い強度（たとえば、Ｗ＜Ｘ）であるか、および／または、北隣接ピクセル１１６がカレントピクセル１１６よりも低い強度（たとえば、Ｎ＜Ｘ）であるかを判定し得る。ＭＳＥＲ−を用いて、アルゴリズムは、東隣接ピクセル１１６がカレントピクセル１１６よりも高い強度（たとえば、Ｅ＞Ｘ）であるか、南隣接ピクセル１１６がカレントピクセル１１６よりも高い強度（たとえば、Ｓ＞Ｘ）であるか、西隣接ピクセル１１６がカレントピクセル１１６よりも高い強度（たとえば、Ｗ＞Ｘ）であるか、および／または、北隣接ピクセル１１６がカレントピクセル１１６よりも高い強度（たとえば、Ｎ＞Ｘ）であるかを判定し得る。
【００４５】
[0052]１つの実施では、電子デバイス１０２は、カレントピクセルＸ  １１６を選択３０２し得る。処理のための最初のカレントピクセル１１６は、ランダムに選択３０２され得るか、前の画像１１４における極値領域１２４のうちの１つまたは複数の場所に基づき得るか、または、事前に設定されたピクセル１１６（たとえば、画像１１４のコーナピクセル１１６）であり得る。電子デバイス１０２は、東隣接ピクセル１１６（たとえば、隣接Ｅ）が処理されたか否かを判定３０４ａし得る。その後、南隣接ピクセル１１６（たとえば、隣接Ｓ）、西隣接ピクセル１１６（たとえば、隣接Ｗ）、および北隣接ピクセル１１６（たとえば、隣接Ｎ）が処理されたか否かを判定３０４ｂ〜ｄすることが続く。隣接ピクセル１１６がチェックされる順番は、図３に関して記載された順番とは異なり得ることが注目されるべきである。隣接ピクセル１１６が処理されたのであれば、進行中の次の隣接ピクセル１１６（たとえばＥ、Ｓ、Ｗ、Ｎ）がチェックされ得る。
【００４６】
[0053]チェックされている隣接ピクセル１１６が処理されていないのであれば、隣接ピクセル１１６が、処理されているものとして設定３０６ａ〜ｄされ、隣接ピクセル１１６の強度が、カレントピクセル１１６の強度と比較３０８ａ〜ｄされる。隣接ピクセル１１６の強度が、カレントピクセル１１６の強度を超えているか、または、等しいのであれば、隣接ピクセル１１６は、ヒープ１２０上にキュー３１０ａ〜ｄされるが、カレントピクセル１１６として選択されない。前述したように、ヒープ１２０は、現在の部分的な極値領域１２４の境界ピクセル１１６を保持し得る。したがって、ピクセル１１６がヒープ１２０上にキューされていると、そのピクセル１１６が、境界ピクセル１１６であり得る。
【００４７】
[0054]隣接ピクセル１１６の強度がカレントピクセル１１６の強度よりも低いのであれば、カレントピクセル１１６はヒープ１２０上にキュー３１２ａ〜ｄされ、隣接ピクセル１１６は、カレントピクセル１１６として設定３１４ａ〜ｄ（たとえば選択）される。可能なすべての隣接ピクセル１１６が処理されると、カレントピクセルＸ  １１６は、極値領域１２４の一部として分類され、境界ピクセル１１６は、ヒープ１２０からポップ３１６され、カレントピクセルＸ  １１６として設定３１８され得る。１つの構成では、ヒープ１２０からポップ３１６された境界ピクセル１１６は、最小の強度を持つ、ヒープ１２０内のピクセル１１６であり得る。
【００４８】
[0055]しかしながら、図３に例示された方法３００は、非常に効率的という訳ではないことがあり得る。動作の数およびタイプが、（図３において）方法３００における各ステップの隣に図示されており、「ＬＤ」はロード動作であり、「ＣＭＰ」は比較動作であり、「ＳＥＴ」は、設定動作であり、「ＪＭＰ」はジャンプ動作である。隣接ピクセル１１６が処理されるべきか否かがチェック３０４ａ〜ｄされる毎に、電子デバイス１０２は、１つのＬＤ、１つのＣＭＰ、および１つのＪＭＰを実行する。それに加えて、隣接ピクセル１１６の強度が、カレントピクセル１１６の強度と比較３０８ａ〜ｄされる毎に、電子デバイス１０２は、１つのＬＤ、１つのＣＭＰ、および１つのＪＭＰを実行する。
【００４９】
[0056]したがって、電子デバイス１０２は、隣接Ｅの分岐のために以下動作を実行し得る。（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＳＥＴ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＝（２つのＬＤ、２つのＣＭＰ、２つのＪＭＰ、１つのＳＥＴ）。隣接Ｓの分岐が実行される場合、以下の動作が実行され得る。（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＳＥＴ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＝（３つのＬＤ、３つのＣＭＰ、３つのＪＭＰ、１つのＳＥＴ）。隣接Ｗの分岐が実行される場合、以下の動作が実行され得る。（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＳＥＴ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＝（４つのＬＤ、４つのＣＭＰ、４つのＪＭＰ、１つのＳＥＴ）。隣接Ｎの分岐が実行される場合、以下の動作が実行され得る。（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＳＥＴ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＝（５つのＬＤ、５つのＣＭＰ、５つのＪＭＰ、１つのＳＥＴ）。隣接分岐の何れも実行されない（すべての隣接が処理された）場合、以下の動作が実行され得る。（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＋（１つのＬＤ、１つのＣＭＰ、１つのＪＭＰ）＝（４つのＬＤ、４つのＣＭＰ、４つのＪＭＰ）。各分岐が同じ確率で生じるのであれば、各ループ中の動作の平均は（３．６のＬＤ、３．６のＣＭＰ、３．６のＪＭＰ、０．８のＳＥＴ）となるであろう。
【００５０】
[0057]図４は、画像１１４を処理するための方法４００の別の構成を例示するフロー図である。方法４００は、電子デバイス１０２によって実行され得る。図４に例示された方法４００は、画像１１４内のピクセル１１６をくまなく調べ、特定の隣接ピクセル１１６が処理されたか否かと、隣接ピクセル１１６の強度がカレントピクセル１１６の強度を超えているか否かにに基づいて、ヒープ１２０上にピクセル１１６をキューし得る。しかしながら、図３の方法３００とは異なり、図４における方法４００は、効率化のためにマスクビット１１８を使用し得る。言い換えれば、図４の方法４００は、図３の方法３００におけるように、隣接ピクセル１１６のステータスを受動的にキューし、その結果を比較する代わりに、先見的な手法で画像１１４をくまなく調べる（たとえば、方法４００は、カレントピクセル１１６のマスクビット１１８のみに基づいて、対応する分岐４０６、４０７、４０９を選択し得る）。先見的なキュー方法に加えて、図４の方法４００は、ルックアップテーブル（ＬＵＴ）１２２を使用し得る。これは、実施された場合、加速された動作に寄与し得る。図４の方法４００において例示された構成では、隣接ピクセル１１６は、ピクセル１１６に直交的に隣接（たとえば、Ｅ、Ｓ、Ｗ、またはＮ）している。
【００５１】
[0058]電子デバイス１０２は、カレントピクセルＸ  １１６を選択４０２し得る。処理のための最初のカレントピクセル１１６は、ランダムに選択４０２され得るか、前の画像１１４における極値領域１２４のうちの１つまたは複数の場所に基づき得るか、または、事前に設定されたピクセル１１６（たとえば、画像１１４のコーナピクセル１１６）であり得る。
【００５２】
[0059]極値領域１２４を抽出する計算（たとえば、ＭＳＥＲ）の複雑さは、検出された極値領域１２４の数よりも、画像１１４内のピクセル１１６の数に、より強く相関付けられる。具体的には、画像１１４内のすべてのピクセル１１６について、計算上の複雑さは、２種類の動作、１）隣接ピクセル１１６が処理されたか否かをチェックすることと、２）カレントピクセル１１６強度を、隣接ピクセル１１６の強度と比較することと、に大きく依存する。
【００５３】
[0060]図４を参照して示すように、隣接ピクセル１１６が処理されておらず、隣接ピクセル１１６の強度が、カレントピクセル１１６の強度よりも低い場合、「ＡＤＶＡＮＣＥ」分岐４０７ａ〜ｄが実行され得る。図４では、カレントピクセル１１６は、「カレントピクセルＸ」として示される。「ＡＤＶＡＮＣＥ」分岐４０７ａ〜ｄは、隣接ピクセル１１６を処理済みとして印を付け、カレントピクセル１１６をヒープ１２０上にキューし、隣接ピクセル１１６を、次のステップのためのカレントピクセルＸ  １１６として設定し得る。隣接ピクセル１１６が処理されておらず、隣接ピクセル１１６の強度が、カレントピクセル１１６の強度よりも低くない場合、「ＰＲＯＣＥＳＳ」分岐４０６ａ〜ｄが実行され得る。「ＰＲＯＣＥＳＳ」分岐４０６ａ〜ｄは、隣接ピクセル１１６を処理済みとして印を付け、隣接ピクセル１１６をヒープ１２０上にキューし、カレントピクセル１１６を不変のままにし得る。したがって、電子デバイス１０２は、以下の９つの分岐４０６、４０７、４０９（各ステップは、図４における分岐４０６、４０７、４０９に相当する）のうちの１つを実行し得る。
【００５４】
[0061]第１の分岐は「ＰＲＯＣＥＳＳ＿Ｅ」４０６ａとして示され得る。隣接Ｅが処理されておらず、隣接Ｅの強度がカレントピクセルＸ  １１６のそれよりも低くないのであれば、電子デバイス１０２は隣接Ｅを処理し得る。たとえば、隣接Ｅの４つの隣接ピクセル１１６のマスクビット１１８が、隣接Ｅが処理されたことを示すように設定４０８ａされ得る。隣接Ｅは、ヒープ１２０上にキュー４１０ａされ得る。
【００５５】
[0062]第２の分岐は「ＡＤＶＡＮＣＥ＿Ｅ」４０７ａとして示され得る。隣接Ｅが処理されておらず、隣接Ｅの強度がカレントピクセルＸ  １１６のそれよりも低いのであれば、電子デバイス１０２は、隣接Ｅを処理し、隣接Ｅをカレントピクセル１１６として設定４１２ａし得る。たとえば、隣接Ｅの４つの隣接ピクセル１１６のマスクビット１１８が、隣接Ｅが処理されたことを示すために設定４０８ｂされ得る。カレントピクセルＸ  １１６は、ヒープ１２０上にキュー４１０ｂされ得る。さらに、隣接Ｅが、カレントピクセルＸ  １１６として設定４１２ａされ得る。
【００５６】
[0063]第３の分岐は「ＰＲＯＣＥＳＳ＿Ｓ」４０６ｂとして示され得る。隣接Ｅが処理され、隣接Ｓが処理されておらず、隣接Ｓの強度がカレントピクセルＸ  １１６のそれよりも低くないのであれば、電子デバイス１０２は隣接Ｓを処理し得る。たとえば、隣接Ｓの４つの隣接ピクセル１１６のマスクビット１１８は、隣接Ｓが処理されたことを示すように設定４０８ｃされ得る。隣接Ｓは、ヒープ１２０上にキュー４１０ｃされ得る。
【００５７】
[0064]第４の分岐は「ＡＤＶＡＮＣＥ＿Ｓ」４０７ｂとして示され得る。隣接Ｅが処理され、隣接Ｓが処理されておらず、隣接Ｓの強度がカレントピクセルＸ  １１６のそれよりも低いのであれば、電子デバイス１０２は、隣接Ｓを処理し、隣接Ｓをカレントピクセルとして設定４１２ｂし得る。たとえば、隣接Ｓの４つの隣接ピクセル１１６のマスクビット１１８は、隣接Ｓが処理されたことを示すように設定４０８ｄされ得る。カレントピクセルＸ  １１６が、ヒープ１２０上にキュー４１０ｄされ得る。さらに、隣接Ｓが、カレントピクセルＸ  １１６として設定４１２ｂされ得る。
【００５８】
[0065]第５の分岐は、「ＰＲＯＣＥＳＳ＿Ｗ」４０６ｃとして示され得る。隣接ＥおよびＳが処理され、隣接Ｗが処理されておらず、隣接Ｗの強度が、カレントピクセルＸ１１６のそれよりも低くないのであれば、電子デバイス１０２は隣接Ｗを処理し得る。たとえば、隣接Ｗの４つの隣接ピクセル１１６のマスクビット１１８は、隣接Ｗが処理されたことを示すように設定４０８ｅされ得る。隣接Ｗは、ヒープ１２０上にキュー４１０ｅされ得る。
【００５９】
[0066]第６の分岐は、「ＡＤＶＡＮＣＥ＿Ｗ」４０７ｃとして示され得る。隣接ＥおよびＳが処理され、隣接Ｗが処理されておらず、隣接Ｗの強度が、カレントピクセルＸ  １１６のそれよりも低いのであれば、電子デバイス１０２は隣接Ｗを処理し、隣接ＷをカレントピクセルＸ  １１６として設定４１２ｃし得る。たとえば、隣接Ｗの４つの隣接ピクセル１１６のマスクビット１１８は、隣接Ｗが処理されたことを示すように設定４０８ｆされ得る。カレントピクセルＸ  １１６は、ヒープ１２０上にキュー４１０ｆされ得る。さらに、隣接Ｗが、カレントピクセルＸ  １１６として設定４１２ｃされ得る。
【００６０】
[0067]第７の分岐は「ＰＲＯＣＥＳＳ＿Ｎ」４０６ｄとして示され得る。隣接Ｅ、Ｓ、およびＷが処理され、隣接Ｎが処理されておらず、隣接Ｎの強度が、カレントピクセルＸ  １１６のそれよりも低くないのであれば、電子デバイス１０２は隣接Ｎを処理し得る。たとえば、隣接Ｎの４つの隣接ピクセル１１６のマスクビット１１８は、隣接Ｎが処理されたことを示すように設定４０８ｇされ得る。隣接Ｎは、ヒープ１２０上にキュー４１０ｇされ得る。
【００６１】
[0068]第８の分岐は「ＡＤＶＡＮＣＥ＿Ｎ」４０７ｄとして示され得る。隣接Ｅ、Ｓ、およびＷが処理され、隣接Ｎが処理されておらず、隣接Ｎの強度が、カレントピクセルＸ  １１６のそれよりも低いのであれば、電子デバイス１０２は、隣接Ｎを処理し、隣接ＮをカレントピクセルＸ  １１６として設定４１２ｄし得る。たとえば、隣接Ｎの４つの隣接ピクセル１１６のマスクビット１１８は、隣接Ｎが処理されたことを示すように設定４０８ｈされ得る。カレントピクセルＸ  １１６は、ヒープ１２０上にキュー４１０ｈされ得る。さらに、隣接Ｎが、カレントピクセルＸ  １１６として設定４１２ｄされ得る。
【００６２】
[0069]第９の分岐は、「ＡＬＬ＿ＮＥＩＧＨＢＯＲＳ＿ＰＲＯＣＥＳＳＥＤ」４０９として示され得る。４つすべての隣接ピクセル１１６が処理されているのであれば、カレントピクセルＸ  １１６は、極値領域１２４の一部として分類され得る。ピクセル（たとえば、境界ピクセル）１１６は、ヒープ１２０からポップ４１４され得る。ヒープ１２０からポップされるピクセル１１６は、最小の強度を持つ、ヒープ１２０内のピクセル１１６であり得る。ヒープ１２０内の複数のピクセル１１６は、同じ最小強度を有しているのであれば、ヒープ上に最も直近にキュー４１０されたピクセル１１６が、ヒープ１２０からポップ４１４され得る。電子デバイス１０２は、ポップされたピクセル１１６を、カレントピクセルＸ  １１６として設定４１６し得る。
【００６３】
[0070]図４に図示されるように、分岐４０６、４０７、４０９を判定することは、（「Ｘ」として示される）カレントピクセル１１６のマスクビット１１８に基づいて実行され得る。たとえば、電子デバイス１０２は、カレントピクセルＸ  １１６のマスクビット１１８を、ルックアップテーブル（ＬＵＴ）１２２のインデクスとして用いて、ＬＵＴ  １２２をチェック（たとえば、クエリ）４０４し得る。図４に例示される構成では、８つのマスクビット１１８からなる合計２５６の組合せが存在する。ルックアップテーブル１２２の各エントリは、分岐４０６、４０７、４０９が実行され得るかを判定するために使用され得る。
【００６４】
[0071]マスクビット１１８を用いることによって、電子デバイス１０２は、隣接ピクセル１１６のステータスの受動的なクエリを回避することが可能になる。さらに、電子デバイス１０２は、先見的な手法で、前述した２種類の動作（たとえば、隣接ピクセル１１６が処理されたか否かをチェックすること、および、カレントピクセルの強度を、隣接ピクセル１１６の強度と比較すること）を効率的に実施し得る。図４に例示された構成の場合、８つのマスクビット１１８（たとえば、１つのマスクバイト）が、リスト（１）に例示されているように、各ピクセル１１６のために割り振られ得る。
【数１】
2016504698.tif 000003
【００６５】
[0072]リスト（１）では、ｂＮｂＣｍｐＥ、ｂＮｂＣｍｐＳ、ｂＮｂＣｍｐＷ、およびｂＮｂＣｍｐＮからなる４つのビットは、ピクセル１１６の強度の、その４つの隣接ピクセル１１６の強度との（前処理）比較結果を示す比較ビットであり得る。ＭＳＥＲ＋の場合、カレントピクセル１１６の強度がその隣接Ｙの強度よりも高い場合、その場合に限って、ｂＮｂＣｍｐＹ＝１（ここで、Ｙ＝Ｅ、Ｓ、Ｗ、またはＮ）である。たとえば、カレントピクセル１１６の強度が、隣接Ｅよりも高いのであれば、ｂＮｂＣｍｐＥ＝１である。しかしながら、カレントピクセル１１６の強度が隣接Ｅよりも高くないのであれば、ｂＮｂＣｍｐＥ＝０である。
【００６６】
[0073]ＭＳＥＲ−の場合、カレントピクセル１１６の強度がその隣接Ｙの強度よりも低い場合、その場合に限って、ｂＮｂＣｍｐＹ＝１（ここで、Ｙ＝Ｅ、Ｓ、Ｗ、またはＮ）である。たとえば、カレントピクセル１１６の強度が、隣接Ｅよりも低いのであれば、ｂＮｂＣｍｐＥ＝１である。しかしながら、カレントピクセル１１６の強度が、隣接Ｅよりも低くないのであれば、ｂＮｂＣｍｐＥ＝０である。
【００６７】
[0074]これら４つの比較ビット（たとえば、ｂＮｂＣｍｐＥ、ｂＮｂＣｍｐＳ、ｂＮｂＣｍｐＷ、およびｂＮｂＣｍｐＮ）は、前処理機能によってすべてのピクセル１１６のために設定され得る。１つの構成では、前処理機能は、（たとえば、ベクトル化／単一命令、複合データ（ＳＩＭＤ）命令を用いて）ＡＲＭプロセッサ（ＡＲＭ）上で効率的に実施され得る。１つの実施では、前処理機能は、請求項４の方法４００が始まる前に、画像１１４内のすべてのピクセル１１６について比較ビットを設定し得る。
【００６８】
[0075]リスト（１）では、ｂＮｂＰｒｏｃＥ、ｂＮｂＰｒｏｃＳ、ｂＮｂＰｒｏｃＷ、およびｂＮｂＰｒｏｃＮからなる４つのビットは、ピクセル１１６の１つまたは複数の隣接ピクセル１１６が処理されたか否かを示す「処理ビット」と称され得る。１つの構成では、隣接Ｙが処理されている場合、その場合に限って、ｂＮｂＰｒｏｃＹ＝１（ここで、Ｙ＝Ｅ、Ｓ、Ｗ、またはＮ）である。処理ビットは、０となるように初期化され得る。ピクセル１１６が隣接を有さない（たとえば、ピクセル１１６が、コーナピクセルまたはエッジピクセルである）のであれば、存在しない隣接ピクセル１１６に対応するｂＮｂＰｒｏｃＹが、１に設定され得る。カレントピクセル１１６が処理された後、カレントピクセル１１６の各隣接ピクセル１１６は、表１に例示されるように、対応するマスクビット１１８を設定することによって、カレントピクセル１１６が処理されたことを通知され得る。たとえば、カレントピクセル１１６が処理されると、カレントピクセル１１６は隣接Ｅの西であるので、隣接Ｅは、ｂＮｂＰｒｏｃＷを１に設定し得る。
【表１】
2016504698.tif 000004
【００６９】
[0076]１つの構成では、ピクセル１１６が、隣接を有していないのであれば（たとえば、ピクセル１１６がコーナピクセルまたはエッジピクセルであれば）、対応する存在しない隣接ピクセル１１６の比較ビット（たとえば、ｂＮｂＣｍｐＹ）は、（たとえば、前処理中に）０に設定され得る。別の構成では、存在しない隣接ピクセル１１６に対応する処理ビット（たとえば、ｂＮｂＰｒｏｃＹ）が１に設定されている限り、比較ビット（たとえば、ｂＮｂＣｍｐＹ）は、コーナピクセルまたはエッジピクセルについて、０または１の何れかに設定され得る。
【００７０】
[0077]リスト（１）に例示されたマスクビット１１８に従うルックアップテーブル（ＬＵＴ）１２２の一例が、表（２）に提供される。明瞭さのために、マスクビット１１８（たとえば、比較ビットおよび処理ビット）は、表（２）において略語化されている。たとえば、ｂＮｂＰｒｏｃＮは「ＰＮ」として表示され、ｂＮｂＰｒｏｃＷは「ＰＷ」として表示され、ｂＮｂＰｒｏｃＳは「ＰＳ」として表示され、ｂＮｂＰｒｏｃＥは「ＰＥ」として表示され、ｂＮｂＣｍｐＮは「ＣＮ」として表示され、ｂＮｂＣｍｐＷは「ＣＷ」として表示され、ｂＮｂＣｍｐＳは「ＣＳ」として表示され、ｂＮｂＣｍｐＥは「ＣＥ」として示される。マスクビット１１８の値が示される。ここで、“*”は、０または１の何れかの値を表す。前述された９つの分岐４０６、４０７、４０９のうちの１つに対応する動作が、マスクビット１１８値の様々な組合せに関連付けられる。したがって、マスクビット１１８は、実行されるべきある動作を示す、ＬＵＴ  １２２内のインデクスである。動作に関連付けられているマスクビット１１８の組合せの数もまた、表（２）にリストされている。
【表２】
2016504698.tif 000005
【００７１】
[0078]ピクセル１１６のマスクビット１１８を同時にチェックすることによって、電子デバイス１０２は、未処理の隣接ピクセル１１６が発見されるまで個々の各隣接ピクセル１１６がチェックされる状況を回避することが可能となり得る。さらに、処理されるべき次のピクセル１１６が、直ちに決定され得る。これは、より効率的な極値領域１２４検出という結果をもたらす。具体的には、各テーブルルックアップは、２つのＬＤおよび１つのＪＭＰ動作を使用し得る。さらに、隣接ピクセル１１６のマスクビット１１８が設定される毎に、電子デバイス１０２によって、最大４つのＳＥＴ動作が実行され得る。
【００７２】
[0079]したがって、図４における最初の８つの分岐４０６ａ〜ｄ、４０７ａ〜ｄ（たとえば、ＰＲＯＣＥＳＳ＿Ｅ  ４０６ａ、ＡＤＶＡＮＣＥ＿Ｅ  ４０７ａ、ＰＲＯＣＥＳＳ＿Ｓ  ４０６ｂ、ＡＤＶＡＮＣＥ＿Ｓ  ４０７ｂ、ＰＲＯＣＥＳＳ＿Ｗ  ４０６ｃ、ＡＤＶＡＮＣＥ＿Ｗ  ４０７ｃ、ＰＲＯＣＥＳＳ＿Ｎ  ４０６ｄ、およびＡＤＶＡＮＣＥ＿Ｎ  ４０７ｄ）の各々は、以下の動作を実行し得る。（２つのＬＤ、１つのＪＭＰ）＋（４つのＳＥＴ）＝（２つのＬＤ、１つのＪＭＰ、４つのＳＥＴ）。最後の分岐（たとえば、ＡＬＬ＿ＮＥＩＧＨＢＯＲＳ＿ＰＲＯＣＥＳＳＥＤ  ４０９）は、（２つのＬＤ、１つのＪＭＰ）を実行し得る。各分岐４０６ａ〜ｉがそれぞれ等しく可能であれば、すべての分岐４０６、４０７、４０９の平均は、（２つのＬＤ、１つのＪＭＰ、３．５６のＳＥＴ）であり得る。設定された動作は通常、他の動作よりも計算負荷が低いので、図４の方法４００は、図３の方法３００よりも、より高速、かつ、より効率的であり得る。
【００７３】
[0080]画像１１４は、任意のサイズまたは寸法からなるピクセルのグリッドであり得る。たとえば、画像１１４は、３×３、３×４、４×４等のピクセルのグリッドであり得る。カレントピクセル１１６がピクセル（１）であり、ＡＤＶＡＮＣＥ＿Ｅ  ４０７ａ分岐が実行されているのであれば、ピクセル（２）が処理される。本明細書で使用されるように、ピクセル１１６を「処理する」、「処理した」、および／または「処理している」ことは、ピクセル１１６の隣接ピクセル１１６のｂＮｂＰｒｏｃビット（たとえば、ｂＮｂＰｒｏｃＥ、ｂＮｂＰｒｏｃＳ、ｂＮｂＰｒｏｃＷ、およびｂＮｂＰｒｏｃＮ）を修正すること（たとえば、設定すること）を称する。図４の方法４００の分岐４０６、４０７、４０９のうちの１つが、カレントピクセル１１６のために実行されている場合、隣接ピクセル１１６のｂＮｂＰｒｏｃビットが修正され得る。この例において、ピクセル（２）は、隣接ピクセル１１６のｂＮｂＰｒｏｃビットを１に設定４０８ｂすることによって処理される。したがって、ピクセル（２）はピクセル（３）の西隣接であるので、ピクセル（３）のｂＮｂＰｒｏｃＷビットが１に設定４０８ｂされる。ピクセル（２）はピクセル（１）の東隣接であるので、ピクセル（１）のｂＮｂＰｒｏｃＥビットが１に設定４０８ｂされる。さらに、ピクセル（２）はピクセル（６）の北隣接であるので、ピクセル（６）のｂＮｂＰｒｏｃＮビットが１に設定４０８ｂされる。
【００７４】
[0081]ピクセル（１）は、ヒープ１２０上にキュー４１０ｂされ得る。ピクセル（２）は、カレントピクセル１１６として設定４１２ａされ得る。方法４００は、ピクセル（２）のためにどの分岐４０６、４０７、４０９が実行され得るのかを判定するために、ピクセル（２）のマスクビット１１８を用いて、ルックアップテーブル１２２をチェック４０４することによって進行し得る。方法４００を実施するより詳細な例は、図５Ａ〜図５Ｉに関して以下に記載される。本明細書で使用されるように、「ビットを設定する」という用語は、ビットの値を「１」にすることを意味する。対照的に、「ビットをクリアする」という用語は、ビットの値を「０」にすることを意味する。
【００７５】
[0082]図５Ａ〜図５Ｉは、１つまたは複数の極値領域１２４が検出され得る画像１１４を処理するためのステップを例示するブロック図である。具体的には、図５Ａ〜図５Ｉは、１つまたは複数の極値領域１２４が、図４に例示された方法４００を用いてどのようにして検出されるのかを例示する。図５Ａの左上隅における凡例によって記載されているように、強度（たとえば、ピクセル強度またはグレーレベル）が、各ピクセル５１６の左上隅に与えられている。ピクセルインデクス（たとえば、ピクセル番号）が、各ピクセル５１６の右上隅に与えられている。特定のピクセル５１６が、そのピクセルインデクスによって示される（たとえば、０のピクセルインデクスを持つピクセル５１６は、「ピクセル（０）」として示される）。マスクビット５１８は、各ピクセル５１６の底部に沿って８ビットで与えられる。画像１１４は、４ピクセル×４ピクセルの画像１１４として例示されているが、本システムおよび方法は、任意のサイズまたは形状の画像１１４を用いて使用され得る。
【００７６】
[0083]図５Ａ〜図５Ｉに例示される例は、図４に例示される方法４００の３３のステップ（たとえば、ステップ０〜３２）を実証する。実行されている図４からの分岐は、たとえば「ステップ１：ＡＤＶＡＮＣＥ＿Ｅ」のように、ピクセルマップの上にリストされる。さらに、カレントピクセル５１６は、文字「Ｘ」によって示され、次のピクセル５１６（たとえば、次のカレントピクセル５１６）は、「ＮＥＸＴ」によって示される。
【００７７】
[0084]ヒープステータスおよび領域ステータスが、各ピクセルマップの右にリストされる。ヒープ１２０は、現在の部分的な極値領域１２４の境界ピクセル５１６を記憶するために使用され得る。ヒープ１２０に含まれているピクセル５１６は、あるしきい値までの強度を有し得る。１つの構成では、複数の範囲のピクセル強度に対応する複数のヒープ１２０が存在し得る。たとえば、ヒープ「０」は、最大０までの強度を有するピクセル５１６を含み、ヒープ「１」は、最大「１」までの強度を有するピクセル５１６を含み得る、等である。したがって、各ピクセルマップの右にリストされたヒープステータスは、どのピクセル５１６が現在ヒープ１２０にあるかを示す。
【００７８】
[0085]各ピクセルマップの右にリストされた領域ステータスは、どのピクセル５１６が特定の極値領域１２４に属すると判定されているのかを示す。本明細書で使用されるように、領域「０」は、０よりも大きくない強度を有するピクセル５１６の極値領域１２４を称する。さらに、領域「１」は、１よりも大きくない強度を有するピクセル５１６の極値領域１２４を称する、等である。この例において、ピクセル５１６の異なる強度に対応する４つの極値領域１２４（たとえば、領域０〜３）が存在する。
【００７９】
[0086]前処理ステージ（ステップ０（図４には図示されていない））中、電子デバイス１０２は、各ピクセル５１６のマスクビット５１８内に比較ビット（たとえば、ｂＮｂＣｍｐＥ、ｂＮｂＣｍｐＳ、ｂＮｂＣｍｐＷ、およびｂＮｂＣｍｐＮ）を設定し得る。ピクセル５１６の強度は変わらないので、比較ビットは、前処理ステージ後に変わらないことがあり得る。前処理では、画像１１４の境界ピクセル５１６の対応する処理ビット（たとえば、ｂＮｂＰｒｏｃビット）が、ある方向に隣接を有していないのであれば、１に設定される。その結果、方法４００のＭＳＥＲ検出は、これら存在しないピクセルを処理することを試みないであろう。たとえば、ピクセル（０）は、西または北の隣接を有していないので、ピクセル（０）のｂＮｂＰｒｏｃＷビットおよびｂＮｂＰｒｏｃＮビットは、１に設定される。
【００８０】
[0087]前処理後、電子デバイス１０２は、各ピクセル５１６のマスクビット５１８を用いて画像１１４をくまなく調べ得る。電子デバイス１０２は、開始ピクセル５１６（たとえば、第１のカレントピクセル５１６）を選択し得る。１つの実施では、開始ピクセル５１６は、ランダムに選択され得る。別の実施では、開始ピクセル５１６は、前の画像１１４における極値領域１２４の１つまたは複数の場所に基づいて選択され得る。さらに別の実施では、開始ピクセル５１６は、コーナピクセル５１６（たとえば、ピクセル（０））であり得る。この例において、開始ピクセル５１６は、ピクセル（０）である。
【００８１】
[0088]ステップ１では、ピクセル（０）（カレントピクセル５１６）のマスクビット５１８は、ピクセル（１）（たとえば、ピクセル（０）の隣接Ｅ）が処理されておらず、ピクセル（１）の強度がピクセル（０）よりも低いことを示す。１つの構成では、表（２）に例示されるように、マスクビット５１８は、どの動作を実行するのかを決定するために、ルックアップテーブル１２２のインデクスとして使用され得る。したがって、図４からの「ＡＤＶＡＮＣＥ＿Ｅ」分岐は、ルックアップテーブル１２２のインデクスとしてピクセル（０）のマスクビット５１８を用いて、ルックアップテーブル１２２に基づいて、ピクセル（０）について実行される。ピクセル（１）の隣接ピクセル５１６のマスクビット５１８は、ピクセル（１）が処理されたことを反映するように更新（たとえば設定）される。したがって、ピクセル（０）のｂＮｂＰｒｏｃＥ、ピクセル（２）のｂＮｂＰｒｏｃＷ、およびピクセル（５）のｂＮｂＰｒｏｃＮは、１に設定され得る。ピクセル（０）は、ヒープ「３」上でキューされる。これは、最大３の強度を有する極値領域１２４の境界ピクセル５１６のために使用される。ピクセル（１）はその後、次のピクセル５１６（たとえば、次のカレントピクセル５１６）として設定される。
【００８２】
[0089]ステップ２では、ピクセル（１）のマスクビット５１８は、ピクセル（２）（ピクセル（１）の隣接Ｅ）が処理されておらず、ピクセル（２）の強度がピクセル（１）よりも低いことを示す。したがって、「ＡＤＶＡＮＣＥ＿Ｅ」は、ピクセル（１）のために実行される。ピクセル（２）の隣接ピクセル５１６のマスクビット５１８は、ピクセル（２）が処理されたことを反映するように設定される。したがって、ピクセル（１）のｂＮｂＰｒｏｃＥ、ピクセル（３）のｂＮｂＰｒｏｃＷ、およびピクセル（６）のｂＮｂＰｒｏｃＮは、１に設定される。ピクセル（１）はヒープ「２」上にキューされる。これは、最大２の強度を有する極値領域１２４の境界ピクセル５１６のために使用される。ピクセル（２）は、その後、カレントピクセル５１６として設定される。
【００８３】
[0090]ステップ３では、ピクセル（２）のマスクビット５１８は、ピクセル（３）（ピクセル（２）の隣接Ｅ）が処理されていないが、ピクセル（３）の強度は、ピクセル（２）よりも低くないことを示す。したがって、「ＰＲＯＣＥＳＳ＿Ｅ」は、ピクセル（２）のために実行される。ピクセル（３）の隣接ピクセル５１６のマスクビット５１８は、ピクセル（３）が処理されたことを反映するように設定される。したがって、ピクセル（２）のｂＮｂＰｒｏｃＥおよびピクセル（７）のｂＮｂＰｒｏｃＮは、１に設定される。ピクセル（３）は、ヒープ「３」上にキューされる。しかしながら、ピクセル（２）は、カレントピクセル５１６として残る。
【００８４】
[0091]ステップ４では、ピクセル（２）のマスクビット５１８は、ピクセル（３）（たとえば、ピクセル（２）の隣接Ｅ）が処理され、ピクセル（６）（たとえば、隣接Ｓ）が処理されておらず、ピクセル（６）の強度が、ピクセル（２）よりも低いことを示す。したがって、「ＡＤＶＡＮＣＥ＿Ｓ」は、ピクセル（２）のために実行される。ピクセル（６）の隣接ピクセル５１６のマスクビット５１８は、ピクセル（６）が処理されたことを反映するように設定される。したがって、ピクセル（５）のｂＮｂＰｒｏｃＥ、ピクセル（２）のｂＮｂＰｒｏｃＳ、ピクセル（７）のｂＮｂＰｒｏｃＷ、およびピクセル（Ａ）のｂＮｂＰｒｏｃＮが、１に設定される。ピクセル（２）は、ヒープ「１」上にキューされる。ピクセル（６）は、カレントピクセル５１６として設定される。
【００８５】
[0092]ステップ５では、ピクセル（６）のマスクビット５１８は、ピクセル（７）（たとえば、隣接Ｅ）が処理されていないが、ピクセル（７）の強度は、ピクセル（６）よりも低くないことを示す。したがって、「ＰＲＯＣＥＳＳ＿Ｅ」がピクセル（６）のために実行される。これは、ピクセル（６）がカレントピクセル５１６として残ったまま、ステップ３において前述したように達成され得る。
【００８６】
[0093]ステップ６では、ピクセル（６）のマスクビット５１８は、ピクセル（７）（たとえば、隣接Ｅ）が処理され、ピクセル（Ａ）（たとえば、隣接Ｓ）が処理されていないが、ピクセル（Ａ）の強度はピクセル（６）よりも低くないことを示す。したがって、「ＰＲＯＣＥＳＳ＿Ｓ」がピクセル（Ａ）のために実行される。ピクセル（Ａ）の隣接ピクセル５１６のマスクビット５１８は、ピクセル（Ａ）が処理されたことを反映するように設定される。したがって、ピクセル（９）のｂＮｂＰｒｏｃＥ、ピクセル（６）のｂＮｂＰｒｏｃＳ、ピクセル（Ｂ）のｂＮｂＰｒｏｃＷ、およびピクセル（Ｅ）のｂＮｂＰｒｏｃＮが、１に設定される。ピクセル（Ａ）は、ヒープ「０」上にキューされる。しかしながら、ピクセル（６）は、カレントピクセル５１６として残る。
【００８７】
[0094]ステップ７では、ピクセル（６）のマスクビット５１８は、ピクセル（７）（たとえば、隣接Ｅ）およびピクセル（Ａ）（たとえば、隣接Ｓ）が処理され、ピクセル（５）（たとえば、隣接Ｗ）が処理されていないが、ピクセル（５）の強度はピクセル（６）よりも低くないことを示す。したがって、「ＰＲＯＣＥＳＳ＿Ｗ」がピクセル（５）のために実行される。ピクセル（５）の隣接ピクセル５１６のマスクビット５１８は、ピクセル（５）が処理されたことを反映するように設定される。したがって、ピクセル（４）のｂＮｂＰｒｏｃＥ、ピクセル（１）のｂＮｂＰｒｏｃＳ、ピクセル（６）のｂＮｂＰｒｏｃＷ、およびピクセル（９）のｂＮｂＰｒｏｃＮは、１に設定される。ピクセル（５）は、ヒープ「１」にキューされる。しかしながら、ピクセル（６）は、カレントピクセル５１６として残る。
【００８８】
[0095]ステップ８では、ピクセル（６）のマスクビット５１８は、すべての隣接ピクセル５１６が処理されたことを示す。したがって、「ＡＬＬ＿ＮＥＩＧＨＢＯＲＳ＿ＰＲＯＣＥＳＳＥＤ」が実行される。ピクセル（６）は、領域「０」の一部として識別される。最小強度を有するピクセル５１６が、ヒープ１２０からポップされ、カレントピクセル５１６として設定され得る。同じヒープ１２０に複数のピクセル５１６が存在するのであれば、ヒープ１２０に最も直近にキューされたピクセル５１６が、ヒープ１２０からポップされ得る。このケースでは、ピクセル（Ａ）がヒープ「０」からポップされ、カレントピクセル５１６として設定される。
【００８９】
[0096]ステップ９〜１１では、ピクセル（Ａ）の未処理の隣接（ピクセル（Ｂ）、ピクセル（Ｅ）、およびピクセル（９））の各々が処理されるが、その隣接の強度はいずれも０（ピクセル（Ａ）の強度）よりも低くはないので、ステップ１２において、「ＡＬＬ＿ＮＥＩＧＨＢＯＲＳ＿ＰＲＯＣＥＳＳＥＤ」が実行される。ピクセル（Ａ）はまた、領域「０」の一部であるとして識別される。この時点において、領域「０」は完全に定義される。１つの構成では、対応する強度レベルのヒープ１２０がエンプティになった場合、領域は検出される。ピクセル（６）およびピクセル（Ａ）は、領域「１」へ追加される。ピクセル（９）は（１である）最小の強度を有し、ヒープ「１」にキューされるべき最も直近のピクセル５１６であったので、ピクセル（９）がヒープ「１」からポップされ、カレントピクセル５１６として設定される。
【００９０】
[0097]ステップ１３〜１４では、ピクセル（９）の残りの未処理の隣接（ピクセル（Ｄ）およびピクセル（８））が処理される。ピクセル（９）の未処理の隣接の何れも、ピクセル（９）よりも強度的に低くないので、ステップ１５において、「ＡＬＬ＿ＮＥＩＧＨＢＯＲＳ＿ＰＲＯＣＥＳＳＥＤ」が実行される。これは、領域「１」の一部としてピクセル（９）を識別する。ピクセル（５）は（１である）最小の強度を有し、ヒープ「１」にキューされるべき最も直近のピクセル５１６であったので、ピクセル（５）が、ヒープ「１」からポップされ、カレントピクセル５１６として設定される。
【００９１】
[0098]ステップ１６では、ピクセル（５）のマスクビット５１８は、ピクセル（３）（たとえば、隣接Ｗ）が処理されていないことを示す。したがって、「ＰＲＯＣＥＳＳ＿Ｗ」は、ピクセル（５）のために実行され、そこでピクセル（５）はカレントピクセル５１６として残る。
【００９２】
[0099]ステップ１７では、ピクセル（５）のマスクビット５１８は、すべての隣接ピクセル５１６が処理されたことを示す。したがって、「ＡＬＬ＿ＮＥＩＧＨＢＯＲＳ＿ＰＲＯＣＥＳＳＥＤ」がピクセル（５）のために実行される。ピクセル（５）はまた、領域「１」の一部であるとして識別される。ピクセル（２）は、ヒープ１２０内のピクセル５１６の、（１である）最小の強度を有しているので、ピクセル（２）が、ヒープ「１」からポップされ、カレントピクセル５１６として設定される。
【００９３】
[00100]ステップ１８では、ピクセル（２）のマスクビット５１８は、すべての隣接ピクセル５１６が処理されたことを示す。したがって、「ＡＬＬ＿ＮＥＩＧＨＢＯＲＳ＿ＰＲＯＣＥＳＳＥＤ」がピクセル（２）のために実行される。ピクセル（２）はまた、領域「１」の一部であるとして識別される。この時点において、領域「１」は完全に定義される。ピクセル（６）、（Ａ）、（９）、（５）および（２）が、領域「２」へ追加される。ピクセル（Ｄ）は、（１である）最小の強度を有し、ヒープ「２」上にキューされるべき最も直近のピクセル５１６であったので、ピクセル（Ｄ）はヒープ「２」からポップされ、カレントピクセル５１６として設定される。類似の手順が、領域「２」（ステップ１９〜２６）および「３」（ステップ２７〜３２）のために実行され得る。
【００９４】
[00101]図６は、本明細書に記載されたシステムおよび方法にしたがう隣接マップを例示するブロック図である。境界線追跡（たとえば、輪郭を決定すること）を加速するために、マスクビット１１８を用いた隣接マップが決定され得る。１つの構成では、隣接マップは、ベクトル化／単一の命令、複数データ（ＳＩＭＤ）命令によって効率的に実施され得る。境界線追跡を含む画像処理およびコンピュータビジョン機能は、入力としてグレースケール画像１１４を採用し、それらを、（たとえば、すべての非ゼロのピクセルを１に設定することによって）バイナリ画像１１４へ変換し得る。隣接マップは、小さなオーバヘッドを有する境界線追跡アルゴリズムのバイナリ化ステップへと自然にマージされ得る。したがって、境界線追跡中に、隣接マップマスクビット１１６をインデクスとして用いて、隣接探索の複雑な分岐および／またはループが、単一のＬＵＴ動作と交換され得る。隣接マップはまた、隣接探索中に、隣接ピクセル１１８にアクセスするバス帯域幅を節約し得る。
【００９５】
[00102]境界線追跡は、デジタル化されたバイナリ画像の処理における基本的な技術である。境界線追跡は、１ピクセルの接続された構成要素（１−構成要素）と、０ピクセルの接続された構成要素（バックグラウンドまたはホール）との境界から、チェーンコードまたは座標のシーケンスを導出する。境界線追跡アルゴリズムは、広く研究されており、ピクチャ認識、位相幾何学分析、物体カウント、および画像圧縮のような広範なアプリケーションを有する。
【００９６】
[00103]「隣接」６３２という用語が、図６に記載されたアルゴリズムにおいて述べられている場合、これは、８接続ケースにおける８隣接、すなわち、８接続としての１ピクセル１１６と、４接続としての０ピクセル１１６とを意味する。この例において、入力バイナリ画像１１４は、Ｆ＝｛ｆi,j｝として表わされ得る。画像１１４は、ラスタスキャン順にスキャンされ得る。リスト（２）に例示されるアルゴリズムは、各ピクセル１１６のために実行され得る。ここで、ｆi,j≠０である。
【００９７】
（１）  以下のうちの１つを選択する。
【００９８】
（１．ａ）  ｆi,j＝１およびｆi,j-1）＝０であれば、ピクセル（ｉ，ｊ）は、外部境界の境界線追跡開始点であり、（ｉ2，ｊ2）←（ｉ，ｊ−１）と決定する。
【００９９】
（１．ｂ）  ｆi,j≧１でありｆi,j+1＝０であれば、ピクセル（ｉ，ｊ）は、ホール境界の境界線追跡開始点であり、（ｉ2，ｊ2）←（ｉ，ｊ＋１）と決定する。
【０１００】
（１．ｃ）  そうではない場合、（３）に進む。
【０１０１】
（２）  開始点（ｉ，ｊ）から、以下のサブステップ（２．１）乃至（２．５）によって検出された境界に続く。
【０１０２】
（２．１）  （ｉ2，ｊ2）から始まって、（ｉ，ｊ）である隣接内のピクセル１１６において時計回りに見まわし、非ゼロであるピクセル１１６を発見する。（ｉ1，ｊ1）を、第１の発見された非ゼロのピクセル１１６とする。非ゼロのピクセル１１６が発見されなかったのであれば、ｆi,jに−２を割り振り、（３）へ進む。
【０１０３】
（２．２）  （ｉ2，ｊ2）←（ｉ1，ｊ1）、および（ｉ3，ｊ3）←（ｉ，ｊ）。
【０１０４】
（２．３）  ピクセル（ｉ2，ｊ2）の次の要素から反時計回りに始まって、非ゼロのピクセル１１６を発見し、最初のものを（ｉ4，ｊ4）とするために、カレントピクセル（ｉ3，ｊ3）の隣接におけるピクセル１１６を反時計回りに精査する。
【０１０５】
（２．４）  ピクセル（ｉ3，ｊ3）の値
【数２】
2016504698.tif 000006
【０１０６】
を、以下のように変更する。
【０１０７】
（２．４ａ）  ピクセル（ｉ3，ｊ3＋１）が、サブステップ（２．３）において精査された０ピクセルであれば、
【数３】
2016504698.tif 000007
【０１０８】
である。
【０１０９】
（２．４ｂ）  ピクセル（ｉ3，ｊ3＋１）がサブステップ（２．３）において精査された０ピクセルではなく、
【数４】
2016504698.tif 000008
【０１１０】
であれば、
【数５】
2016504698.tif 000009
【０１１１】
である。
【０１１２】
（２．４ｃ）  そうではない場合、
【数６】
2016504698.tif 000010
【０１１３】
は変わらない。
【０１１４】
（２．５）  （ｉ4，ｊ4）＝（ｉ，ｊ）および（ｉ3，ｊ3）＝（ｉ1，ｊ1）（開始点に戻る）であれば、（３）に進み、そうではない場合、（ｉ2，ｊ2）←（ｉ3，ｊ3），（ｉ3，ｊ3）←（ｉ4，ｊ4））となり（２．３）に戻る。
【０１１５】
（３）  ピクセル（ｉ，ｊ＋１）からのラスタスキャンを再開する。スキャンが、画像１１４の右下コーナに達した場合、アルゴリズムは終了し得る。
【０１１６】
リスト（２）
[00104]１ピクセルの８つの隣接は、図６の隣接ピクセルインデクス６３０に例示されているようにインデクスされ得る。リスト（２）の（１．ａ）が真であれば、リスト（２）の（２．１）における（ｉ，ｊ）の隣接６３２におけるピクセル１１６の時計回りの探索が、リスト（３）に例示されたＣコードによって実施され得る。
【数７】
2016504698.tif 000011
【０１１７】
[00105]リスト（３）では、ｓおよびｓＥｎｄは、隣接ピクセル１１６のインデクスであり、ｉ０は、境界線追跡開始点に対するポインタであり、ｉ１は、隣接ピクセル１１６に対するポインタであり、隣接３ｘ３Ｏｆｆｓｅｔは、８つの隣接ピクセル１１６のアドレスオフセットのアレイである。
【０１１８】
[00106]リスト（２）の（１．ｂ）が真であれば、リスト（２）の（２．１）における（ｉ，ｊ）の隣接におけるピクセル１１６の時計周りの探索が、リスト（４）に例示されたＣコードによって実施され得る。
【数８】
2016504698.tif 000012
【０１１９】
[00107]（リスト（３）に例示された）前のＣコードとの相違は、時計回りの探索の開始隣接ピクセル１１６であることである。リスト（２）の（２．３）における（ｉ3，ｊ3）の近隣におけるピクセル１１６の反時計回りの探索は、リスト（５）に例示されたＣコードによって実施され得る。
【数９】
2016504698.tif 000013
【０１２０】
[00108]リスト（５）では、ｓは、隣接ピクセル１１６のインデクスであり、ｉ３はカレントピクセルに対するポインタであり、ｉ４は隣接ピクセル１１６に対するポインタであり、隣接３ｘ３Ｏｆｆｓｅｔは、８つの隣接ピクセル１１６のアドレスオフセットのアレイである。
【０１２１】
[00109]（リスト（３）、（４）、および（５）に例示されるような）これらの探索中、隣接ピクセル１１６の一部またはすべてが読み取られ、０と比較される。この比較結果に基づいて、マスクビット１１８（たとえば、隣接インデクス）が更新され、その後、次の隣接ピクセル１１６が処理される。これらの探索は、隣接マップを用いることによって、より効率的に実行され得る。バイナリ画像１１４の各ピクセル１１６について、ｉ番目の隣接ピクセル１１６が非ゼロである場合、その場合に限って、８つのマスクビット１１８の隣接マップが定義され得る。ここで、ｉ番目のマスクビット１１８は１である。そして、ｉ番目の隣接ピクセル１１８がゼロである場合、その場合に限って、ｉ番目のマスクビット１１８は０である。図６は、隣接６３２の例を例示する。この例において、ゼロではない隣接ピクセル１１６は、陰付きフィールドによって示され、ゼロの隣接ピクセル１１６は、白いフィールドによって示される。隣接ピクセルインデクス（０）から始まって、隣接６３２の対応する隣接マップは、０ｂ１１１００１１１＝０ｘＥ７である。
【０１２２】
[00110]入力バイナリ画像１１４と同じサイズを持つ支援画像バッファは、入力バイナリ画像１１４の各ピクセル１１６の隣接マップを記憶し得る。たとえば、ピクセル（ｉ，ｊ）の隣接マップは、ｎi,jによって示され得る。ピクセル（ｉ，ｊ）の８つの隣接ピクセル１１６の隣接マップがリスト（６）に例示されるように計算され得る。
【数１０】
2016504698.tif 000014
【０１２３】
[00111]１つの構成では、リスト（６）に例示された動作は、ベクトル化／ＳＩＭＤ命令を用いて効率的に実施され得る。８つの隣接マップの８ビットの計算（合計して６４ビット）は、リスト（７）に例示された疑似コードによって実施され得る。
【数１１】
2016504698.tif 000015
【０１２４】
[00112]８つの隣接マップについて、１０のベクトル化／ＳＩＭＤ（ＸＴＹＰＥ）命令および６つのロード／記憶（ＬＤ／ＳＴ）命令がある。これらは、０．６２５パケット／ピクセルを達成し得る。８つの隣接６３２の場合、マスクビット１１８の異なる組合せによって示されるように、合計して２５６の可能な隣接マップが存在する。デジタル信号プロセッサの１つの構成では、１つのパケットは、単一のサイクルで実行され得る。これは、最大で４つの命令を含み得る。各パケットでは、最大で２つのＸＴＹＰＥ命令と、最大で２つのＬＤ／ＳＴ命令とが存在し得る。
【０１２５】
[00113]前述した探索アルゴリズム１は、開始ポイントの隣接マップをインデクスとして用いて、リスト（８）に例示された２５６ビットの１次元ルックアップテーブルｓｔａｒｔｉｎｇＰｏｉｎｔＯｕｔｅｒＢｏｒｄｅｒ［２５６］によって加速され得る。対応するエントリは、探索されたピクセル１１６のインデクスである。
【数１２】
2016504698.tif 000016
【０１２６】
[00114]前述した探索アルゴリズム２は、開始ポイントの隣接マップをインデクスとして用いて、リスト（９）に例示された２５６ビットの１次元ルックアップテーブルｓｔａｒｔｉｎｇＰｏｉｎｔＨｏｌｅＢｏｒｄｅｒ［２５６］によって加速され得る。対応するエントリは、探索されたピクセルのインデクスである。
【数１３】
2016504698.tif 000017
【０１２７】
[00115]前述された探索アルゴリズム３は、カレント隣接６３２における前のピクセル１１６のインデクスおよびカレントピクセル１１６の隣接マップをそれぞれインデクスとして用いて、リスト（１０）に例示された２５６×８ビットの２次元ルックアップテーブルｂｏｒｄｅｒＦｏｌｌｏｗｉｎｇ［２５６］［８］によって加速され得る。対応するエントリは、探索されたピクセル１１６のインデクスである。
【数１４】
2016504698.tif 000018
【０１２８】
[00116]探索アルゴリズムは、ルックアップテーブル（ＬＵＴ）１２２のインデクスとして隣接マップのマスクビット１１８を用いて、１つの単一ＬＵＴ１２２動作によって達成され得る。これは、探索アルゴリズムの、その他の予測不能の複雑さを低減し得る。
【０１２９】
[00117]複雑さが線形的であり、隣接６３２に依存する隣接探索は、隣接マップを利用して、不変の複雑さを有する単一のＬＵＴ１２２動作となる。ＬＵＴのサイズはそれぞれ２５６バイト、２５６バイトおよび２０４８バイトであり得る。これらのＬＵＴは、キャッシュ内に容易に保持され、バストラフィックに対するペナルティをほとんどもたらさない。図６に記載されたシステムおよび方法はまた、４接続ケース、すなわち、より小さなサイズからなる異なるＬＵＴを用いた４接続としての１ピクセルおよび８接続としての０ピクセル（たとえば、１６バイト、１６バイトおよび６４バイト）にも適用され得る。
【０１３０】
[00118]図７は、電子デバイス／ワイヤレスデバイス７０２内に含まれうるいくつかの構成要素を例示する。電子デバイス／ワイヤレスデバイス７０２は、前述された電子デバイス１０２に従って実施され得る。電子デバイス／ワイヤレスデバイス７０２は、アクセス端末、移動局、ユーザ機器等であり得る。電子デバイス／ワイヤレスデバイス７０２はプロセッサ７０１を含む。プロセッサ７０１は、汎用のシングルまたはマルチチップによるマイクロプロセッサ（たとえば、ＡＲＭ）、特別用途のマイクロプロセッサ（たとえば、デジタル信号プロセッサ（ＤＳＰ））、マイクロコントローラ、プログラマブルゲートアレイ等であり得る。プロセッサ７０１は、中央処理装置（ＣＰＵ）と称され得る。図７の電子デバイス／ワイヤレスデバイス７０２中に単一のプロセッサ７０１のみが示されるが、代替的な構成では、プロセッサの組合せ（たとえば、ＡＲＭとＤＳＰ）が使用され得る。
【０１３１】
[00119]電子デバイス／ワイヤレスデバイス７０２はまた、メモリ７０９を含む。メモリ７０９は、電子情報を記憶することが可能な任意の電子コンポーネントであり得る。メモリ７０９は、ランダムアクセスメモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）、磁気ディスク記憶媒体、光記憶媒体、ＲＡＭ中のフラッシュメモリデバイス、プロセッサとともに含まれた内蔵メモリ、消去可能なプログラマブル読取専用メモリ（ＥＰＲＯＭ）、電子的に消去可能なＰＲＯＭ（ＥＥＰＲＯＭ（登録商標））、レジスタ等、およびこれらの組合せを含むものとして具体化され得る。
【０１３２】
[00120]データ７１３ａおよび命令７１１ａは、メモリ７０９に格納され得る。命令７１１ａは、本明細書に開示された方法を実施するプロセッサ７０１によって実行可能であり得る。命令７１１ａを実行することは、メモリ７０９に記憶されたデータ７１３ａの使用を含み得る。プロセッサ７０１が、命令７１１ａを実行する場合、命令７１１ｂのさまざまな部分が、プロセッサ７０１にロードされ、データ７１３ｂのさまざまな断片が、プロセッサ７０１にロードされ得る。
【０１３３】
[00121]電子デバイス／ワイヤレスデバイス７０２はまた、電子デバイス／ワイヤレスデバイス７０２との間での信号の送信および受信を可能にするために、送信機７１７と受信機７１９とを含み得る。送信機７１７および受信機７１９は、送受信機７０５と総称されることがある。複数のアンテナ７０７ａ〜ｎが、トランシーバ７０５に電気的に接続され得る。電子デバイス／ワイヤレスデバイス７０２はまた、複数の送信機、複数の受信機、複数の送受信機および／または追加のアンテナ（図示せず）を含み得る。
【０１３４】
[00122]電子デバイス／ワイヤレスデバイス７０２はデジタルシグナルプロセッサ（ＤＳＰ）７２３を含み得る。電子デバイス／ワイヤレスデバイス７０２はまた、通信インターフェース７２５を含み得る。通信インターフェース７２５は、ユーザが電子デバイス／ワイヤレス通信デバイス７０２と対話することを可能にし得る。
【０１３５】
[00123]電子デバイス／ワイヤレスデバイス７０２の様々なコンポーネントは、電力バス、制御信号バス、ステータス信号バス、データバスなどを含み得る、１つまたは複数のバスによって互いに結合され得る。理解しやすいように、図７では様々なバスはバスシステム７２１として示される。
【０１３６】
[00124]本明細書に記載された技法は、直交多重化方式に基づく通信システムを含む様々な通信システムに使用され得る。そのような通信システムの例には、直交周波数分割多元接続（ＯＦＤＭＡ）システム、シングルキャリア周波数分割多元接続（ＳＣ−ＦＤＭＡ）システムなどが含まれる。ＯＦＤＭＡシステムは、直交周波数分割多重化（ＯＦＤＭ）を利用する。これは、システム帯域幅全体を、複数の直交サブキャリアへ分割する変調技術である。これらサブキャリアはまた、トーン、ビン等とも称され得る。各サブキャリアは、ＯＦＤＭを用いて、データと独立して変調される。ＳＣ−ＦＤＭＡシステムは、システム帯域幅にわたって分散されたサブキャリアで送信するインタリーブＦＤＭＡ（ＩＦＤＭＡ）、隣接するサブキャリアのブロックで送信するローカライズドＦＤＭＡ（ＬＦＤＭＡ）、あるいは、隣接するサブキャリアの複数のブロックで送信するエンハンストＦＤＭＡ（ＥＦＤＭＡ）を利用する。一般に、変調シンボルは、ＯＦＤＭでは周波数領域で、ＳＣ−ＦＤＭＡでは時間領域で送信される。
【０１３７】
[00125]本現在の開示に従って、モバイルデバイス内の回路は、現在のピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定するように適応され得る。同じ回路、異なる回路、または同じ回路または異なる回路の第２のセクションが、現在のピクセルの隣接ピクセルのおのおのが処理されたか否かを示すマスクビットを決定するように適応され得る。第２のセクションは、有利には、第１のセクションに結合するか、または第１のセクションの回路と同じ回路に埋め込むことができる。さらに、同じ回路、異なる回路、または同じ回路または異なる回路の第３のセクションが、マスクビットに基づいて処理のための次のピクセルを選択するように適応され得る。第３のセクションは、有利には、第１および第２のセクションに結合するか、または第１および第２のセクションの回路と同じ回路に埋め込むことができる。
【０１３８】
[00126]「判定すること」という用語は、広範なさまざまな動作を含むので、「判定すること」は、算出すること、計算すること、処理すること、導出すること、調査すること、探索すること（たとえば、テーブル、データベース、またはその他のデータ構造を探索すること）、確認すること等を含み得る。さらに、「判定すること」は、受信すること（たとえば、情報を受信すること）、評価すること（たとえば、メモリ内のデータを評価すること）等を含み得る。さらに、「判定すること」は、解決すること、選択すること、選ぶこと、確立すること等を含み得る。
【０１３９】
[00127]「〜に基づく」というフレーズは、明確に別に指定されていないのであれば、「〜のみに基づく」ことを意味しない。言い換えれば、「〜に基づく」というフレーズは、「〜のみに基づく」と「少なくとも〜に基づく」との両方を説明する。
【０１４０】
[00128]「プロセッサ」という用語は、汎用プロセッサ、中央処理装置（ＣＰＵ）、マイクロプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、コントローラ、マイクロコントローラ、ステートマシン等を含むように広く解釈されるべきである。いくつかの状況では、「プロセッサ」は、特定用途向けＩＣ（ＡＳＩＣ）、プログラマブル論理デバイス（ＰＬＤ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）等を称し得る。「プロセッサ」という用語は、たとえば、ＤＳＰとマイクロプロセッサの組合わせ、複数のマイクロプロセッサ、ＤＳＰコアと連携した１つまたは複数のマイクロプロセッサ、または、その他任意のこのような構成のような処理デバイスの組合わせを称し得る。
【０１４１】
[00129]「メモリ」という用語は、電子情報を記憶することができる任意の電子構成要素を含むように広く解釈されるべきである。メモリという用語は、ランダムアクセスメモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）、不揮発性ランダムアクセスメモリ（ＮＶＲＡＭ）、プログラマブル読取専用メモリ（ＰＲＯＭ）、消去可能なＰＲＯＭ（ＥＰＲＯＭ）、電子的に消去可能なＰＲＯＭ（ＥＥＰＲＯＭ）、フラッシュメモリ、磁気または光学的なデータストレージ、レジスタ等のようなさまざまなタイプのプロセッサ読取可能な媒体を称し得る。プロセッサが、メモリから情報を読み取ったり、メモリへ情報を書き込んだりできる場合、メモリは、プロセッサと電気的に通信していると称される。プロセッサに統合されたメモリは、プロセッサと電気的に通信している。
【０１４２】
[00130]「命令」および「コード」という用語は、任意のタイプのコンピュータ読取可能命令（単数または複数）を含むように広く解釈されるべきである。たとえば、用語「命令」および「コード」は、１つまたは複数のプログラム、ルーチン、サブルーチン、関数、手順等を称し得る。「命令」および「コード」は、単一のコンピュータ読取可能命令、または、多くのコンピュータ読取可能命令を備え得る。
【０１４３】
[00131]本明細書で説明された機能は、ハードウェアによって実行されるソフトウェアまたはファームウェアで実装され得る。その機能は、コンピュータ可読媒体上の１つまたは複数の命令として記憶され得る。「コンピュータ可読媒体」または「コンピュータプログラム製品」という用語は、コンピュータまたはプロセッサによってアクセスされ得る、任意の実体を持った記憶媒体を指す。限定ではなく一例によって、コンピュータ読取可能媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭまたはその他の光ディスク記憶装置、磁気ディスク記憶装置またはその他の磁気記憶デバイス、あるいは、所望のプログラムコードを命令群またはデータ構造の形態で搬送または格納するために使用され、しかも、コンピュータによってアクセスされ得るその他任意の媒体を備え得る。本明細書で使用されるｄｉｓｋおよびｄｉｓｃは、コンパクトディスク（disc）（ＣＤ）、レーザーディスク（登録商標）（disc）、光ディスク（disc）、デジタル多用途ディスク（disc）（ＤＶＤ）、フロッピー（登録商標）ディスク（dick）、およびＢｌｕ−ｒａｙ（登録商標）ディスク（disc）を含み、ここで、ｄｉｓｋは通常データを磁気的に再生する一方、ｄｉｓｃはレーザーを用いてデータを光学的に再生する。
【０１４４】
[00132]本明細書で開示された方法は、説明された方法を達成するための１つまたは複数のステップまたは動作を備える。方法ステップおよび／または動作は、特許請求の範囲から逸脱せずに相互に置換され得る。言い換えれば、説明されている方法の適切な動作のために、ステップまたは動作の具体的な順序が要求されていないのであれば、具体的なステップおよび／または動作の順序および／または使用は、特許請求の範囲から逸脱することなく修正され得る。
【０１４５】
[00133]さらに、図３によって示されたものなど、本明細書で説明する方法および技法を実行するためのモジュールおよび／または他の適切な手段は、デバイスによってダウンロードされ、および／または他の方法で取得され得ることを諒解されたい。たとえば、本明細書に記載された方法を実行するための手段の移動を容易にするために、デバイスがサーバに接続され得る。あるいは、本明細書に記載されたさまざまな方法は、記憶手段（たとえば、ランダムアクセスメモリ（ＲＡＭ）や、読取専用メモリ（ＲＯＭ）や、コンパクトディスク（ＣＤ）やフロッピーディスクのような物理的な記憶媒体等）によって提供され、これによって、デバイスは、記憶手段をデバイスに結合または提供することによって、さまざまな手段を取得し得る。
【０１４６】
[00134]特許請求の範囲は、上記に示された厳密な構成および構成要素に限定されないことを理解されたい。さまざまな修正、変更、および変形が、特許請求の範囲から逸脱することなく、本明細書に記載されたシステム、方法、および装置の構成、動作、および詳細においてなされ得る。
【図１】
2016504698.tif 000019
【図１Ａ】
2016504698.tif 000020
【図２】
2016504698.tif 000021
【図３】
2016504698.tif 000022
【図４】
2016504698.tif 000023
【図５Ａ】
2016504698.tif 000024
【図５Ｂ】
2016504698.tif 000025
【図５Ｃ】
2016504698.tif 000026
【図５Ｄ】
2016504698.tif 000027
【図５Ｅ】
2016504698.tif 000028
【図５Ｆ】
2016504698.tif 000029
【図５Ｇ】
2016504698.tif 000030
【図５Ｈ】
2016504698.tif 000031
【図５Ｉ】
2016504698.tif 000032
【図６】
2016504698.tif 000033
【図７】
2016504698.tif 000034
【手続補正書】
【提出日】平成27年9月29日(2015.9.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画像内の極値領域にピクセルを割り振る際に使用するための方法であって、
（ａ）前記ピクセルと前記それぞれの隣接との強度比較を、複数の隣接ピクセルの各々のために、示し、前記それぞれの隣接ピクセルが処理されているか否かをも示すマスクビットを、前記画像内の各ピクセルのために、決定することと、
（ｂ）前記複数の隣接ピクセルのうちの少なくとも１つが処理されていないか否かを、前記マスクビットに基づいて、カレントピクセルのために、決定し、そうである場合は、処理するために前記処理されていない隣接ピクセルのうちの１つを選択し、前記選択された隣接ピクセルを処理することと、ここにおいて、強度比較を示す前記マスクビットに基づいて、前記カレントピクセルと前記選択された隣接ピクセルのうちの１つは、ヒープ内に含まれ、ステップ（ｂ）は、前記カレントピクセルと前記選択された隣接ピクセルのうちの他方のために反復される、
（ｃ）前記マスクビットに基づいて、カレントピクセルのための前記複数の隣接ピクセルのいずれも処理されていないことが決定される場合、前記カレントピクセルを前記極値領域に分類し、前記画像内の別のピクセルのためにステップ（ｂ）を反復することと、を備える、方法。
【請求項２】
前記処理されていない隣接ピクセルのうちの１つを前記選択することは、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスすることを備える、請求項１に記載の方法。
【請求項３】
前記処理されていない隣接ピクセルのうちの１つを前記選択することは、さらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択することを備える、請求項２に記載の方法。
【請求項４】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項１に記載の方法。
【請求項５】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項１に記載の方法。
【請求項６】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項１に記載の方法。
【請求項７】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または直交的に隣接する、請求項１に記載の方法。
【請求項８】
前記カレントピクセルを、輪郭の一部として分類すること、をさらに備える、請求項１に記載の方法。
【請求項９】
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理すること、をさらに備える、請求項１に記載の方法。
【請求項１０】
前記画像は、ビデオ内のフレームであり、前記方法は、前記ビデオ内のすべてのフレームに対して実行される、請求項１に記載の方法。
【請求項１１】
画像内の極値領域にピクセルを割り振る際に使用するための装置であって、
前記ピクセルと前記それぞれの隣接ピクセルとの強度比較を、複数の隣接ピクセルの各々のために、示し、前記それぞれの隣接ピクセルが処理されているか否かをも示すマスクビットを、前記画像内の各ピクセルのために、決定するための手段と、
前記複数の隣接ピクセルのうちの少なくとも１つが処理されていないか否かを、前記マスクビットに基づいて、カレントピクセルのために、決定し、そうである場合は、処理するために前記処理されていない隣接ピクセルのうちの１つを選択し、前記選択された隣接ピクセルを処理するための手段と、ここにおいて、強度比較を示す前記マスクビットに基づいて、前記カレントピクセルと前記選択された隣接ピクセルのうちの１つは、ヒープ内に含まれ、前記決定するための手段は、前記カレントピクセルと前記選択された隣接ピクセルのうちの他方のために前記決定することを反復するようにアレンジされる、
前記マスクビットに基づいて、カレントピクセルのための前記複数の隣接ピクセルのいずれも処理されていないことが決定される場合、前記カレントピクセルを前記極値領域に分類するための手段と、処理するための次のピクセルを、前記マスクビットに基づいて選択するための手段と、を備える装置。
【請求項１２】
前記処理されていない隣接ピクセルのうちの１つを前記選択するための手段は、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスするための手段を備える、請求項１１に記載の装置。
【請求項１３】
前記処理されていない隣接ピクセルのうちの１つを前記選択するための手段はさらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択するための手段を備える、請求項１２に記載の装置。
【請求項１４】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項１１に記載の装置。
【請求項１５】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項１１に記載の装置。
【請求項１６】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項１１に記載の装置。
【請求項１７】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、請求項１１に記載の装置。
【請求項１８】
前記カレントピクセルを、輪郭の一部として分類するための手段、をさらに備える、請求項１１に記載の装置。
【請求項１９】
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理するための手段、をさらに備える、請求項１１に記載の装置。
【請求項２０】
前記画像は、ビデオ内のフレームであり、前記装置は、前記ビデオ内のすべてのフレームを処理する、請求項１１に記載の装置。
【請求項２１】
画像内の極値領域にピクセルを割り振る際に使用するための電子デバイスであって、
プロセッサと、
前記プロセッサと電子通信するメモリと、
前記メモリに記憶された命令とを備え、前記命令は、
（ａ）前記ピクセルと前記それぞれの隣接ピクセルとの強度比較を、複数の隣接ピクセルの各々のために、示し、前記それぞれの隣接ピクセルが処理されているか否かをも示すマスクビットを、前記画像内の各ピクセルのために、決定することと、
（ｂ）前記複数の隣接ピクセルのうちの少なくとも１つが処理されていないか否かを、前記マスクビットに基づいて、カレントピクセルのために、決定し、そうである場合は、処理するために前記処理されていない隣接ピクセルのうちの１つを選択し、前記選択された隣接ピクセルを処理することと、ここにおいて、強度比較を示す前記マスクビットに基づいて、前記カレントピクセルと前記選択された隣接ピクセルのうちの１つは、ヒープ内に含まれ、ステップ（ｂ）は、前記カレントピクセルと前記選択された隣接ピクセルのうちの他方のために反復される、
（ｃ）前記マスクビットに基づいて、カレントピクセルのための前記複数の隣接ピクセルのいずれも処理されていないことが決定される場合、前記カレントピクセルを前記極値領域に分類し、前記画像内の別のピクセルのためにステップ（ｂ）を反復することとを行うように実行可能である、電子デバイス。
【請求項２２】
前記処理されていない隣接ピクセルのうちの１つを前記選択するように実行可能な命令は、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスするように実行可能な命令を備える、請求項２１に記載の電子デバイス。
【請求項２３】
前記処理されていない隣接ピクセルのうちの１つを前記選択するように実行可能な命令はさらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択するように実行可能な命令をさらに備える、請求項２２に記載の電子デバイス。
【請求項２４】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項２１に記載の電子デバイス。
【請求項２５】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項２１に記載の電子デバイス。
【請求項２６】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項２１に記載の電子デバイス。
【請求項２７】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、請求項２１に記載の電子デバイス。
【請求項２８】
前記カレントピクセルを、輪郭の一部として分類するように実行可能な命令、をさらに備える、請求項２１に記載の電子デバイス。
【請求項２９】
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理するように実行可能な命令、をさらに備える、請求項２１に記載の電子デバイス。
【請求項３０】
前記画像は、ビデオ内のフレームであり、前記電子デバイスは、前記ビデオ内のすべてのフレームを処理する、請求項２１に記載の電子デバイス。
【請求項３１】
画像を処理する際に、極値領域にピクセルを割り振る際に使用するためのコンピュータプログラム製品であって、命令を有する非一時的なコンピュータ読取可能な媒体を備え、前記命令は、
（ａ）前記ピクセルと前記それぞれの隣接ピクセルとの強度比較を、複数の隣接ピクセルの各々のために、示し、前記それぞれの隣接ピクセルが処理されているか否かをも示すマスクビットを、前記画像内の各ピクセルのために、決定することと、
（ｂ）前記複数の隣接ピクセルのうちの少なくとも１つが処理されていないか否かを、前記マスクビットに基づいて、カレントピクセルのために、決定し、そうである場合は、処理するために前記処理されていない隣接ピクセルのうちの１つを選択し、前記選択された隣接ピクセルを処理することと、ここにおいて、強度比較を示す前記マスクビットに基づいて、前記カレントピクセルと前記選択された隣接ピクセルのうちの１つは、ヒープ内に含まれ、ステップ（ｂ）は、前記カレントピクセルと前記選択された隣接ピクセルのうちの他方のために反復される、
（ｃ）前記マスクビットに基づいて、カレントピクセルのための前記複数の隣接ピクセルのいずれも処理されていないことが決定される場合、前記カレントピクセルを前記極値領域に分類し、前記画像内の別のピクセルのためにステップ（ｂ）を反復することとを電子デバイスに対して行わせるコードを備える、コンピュータプログラム製品。
【請求項３２】
前記電子デバイスに対して前記処理されていない隣接ピクセルのうちの１つを選択させるための前記コードは、前記電子デバイスに対して、マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスさせるためのコードを備える、請求項３１に記載のコンピュータプログラム製品。
【請求項３３】
前記電子デバイスに対して、前記処理されていない隣接ピクセルのうちの１つを選択させるための前記コードは、前記電子デバイスに対して、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択させるためのコードをさらに備える、請求項３２に記載のコンピュータプログラム製品。
【請求項３４】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項３１に記載のコンピュータプログラム製品。
【請求項３５】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項３１に記載のコンピュータプログラム製品。
【請求項３６】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項３１に記載のコンピュータプログラム製品。
【請求項３７】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、請求項３１に記載のコンピュータプログラム製品。
【請求項３８】
前記電子デバイスに対して、前記カレントピクセルを、輪郭の一部として分類させるためのコード、をさらに備える、請求項３１に記載のコンピュータプログラム製品。
【請求項３９】
前記電子デバイスに対して、ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理させるためのコード、をさらに備える、請求項３１に記載のコンピュータプログラム製品。
【請求項４０】
前記画像は、ビデオ内のフレームであり、前記電子デバイスは、前記ビデオ内のすべてのフレームを処理する、請求項３１に記載のコンピュータプログラム製品。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０１４６
【補正方法】変更
【補正の内容】
【０１４６】
[00134]特許請求の範囲は、上記に示された厳密な構成および構成要素に限定されないことを理解されたい。さまざまな修正、変更、および変形が、特許請求の範囲から逸脱することなく、本明細書に記載されたシステム、方法、および装置の構成、動作、および詳細においてなされ得る。
以下に、出願当初の特許請求の範囲に記載された発明を付記する。
［Ｃ１］
画像を処理するための方法であって、
カレントピクセルのために、前記カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定することと、ここで、前記マスクビットは、前記カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す、
処理するための次のピクセルを、前記マスクビットに基づいて選択することと、を備える、方法。
［Ｃ２］
前記選択することは、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスすることを備える、Ｃ１に記載の方法。
［Ｃ３］
前記選択することは、さらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択することを備える、Ｃ２に記載の方法。
［Ｃ４］
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、Ｃ１に記載の方法。
［Ｃ５］
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、Ｃ１に記載の方法。
［Ｃ６］
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、Ｃ１に記載の方法。
［Ｃ７］
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または直交的に隣接する、Ｃ１に記載の方法。
［Ｃ８］
前記カレントピクセルが、処理されていない隣接ピクセルを有していない場合、前記カレントピクセルを、極値領域の一部として分類すること、をさらに備える、Ｃ１に記載の方法。
［Ｃ９］
前記カレントピクセルを、輪郭の一部として分類すること、をさらに備える、Ｃ１に記載の方法。
［Ｃ１０］
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理すること、をさらに備える、Ｃ１に記載の方法。
［Ｃ１１］
前記画像は、ビデオ内のフレームであり、前記方法は、前記ビデオ内のすべてのフレームに対して実行される、Ｃ１に記載の方法。
［Ｃ１２］
画像を処理するための装置であって、
カレントピクセルのために、前記カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定するための手段と、ここで、前記マスクビットは、前記カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す、
処理するための次のピクセルを、前記マスクビットに基づいて選択するための手段と、を備える装置。
［Ｃ１３］
前記選択するための手段は、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスするための手段を備える、Ｃ１２に記載の装置。
［Ｃ１４］
前記選択するための手段はさらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択するための手段を備える、Ｃ１３に記載の装置。
［Ｃ１５］
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、Ｃ１２に記載の装置。
［Ｃ１６］
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、Ｃ１２に記載の装置。
［Ｃ１７］
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、Ｃ１２に記載の装置。
［Ｃ１８］
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、Ｃ１２に記載の装置。
［Ｃ１９］
前記カレントピクセルが、処理されていない隣接ピクセルを有していない場合、前記カレントピクセルを、極値領域の一部として分類するための手段、をさらに備える、Ｃ１２に記載の装置。
［Ｃ２０］
前記カレントピクセルを、輪郭の一部として分類するための手段、をさらに備える、Ｃ１２に記載の装置。
［Ｃ２１］
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理するための手段、をさらに備える、Ｃ１２に記載の装置。
［Ｃ２２］
前記画像は、ビデオ内のフレームであり、前記装置は、前記ビデオ内のすべてのフレームを処理する、Ｃ１２に記載の装置。
［Ｃ２３］
画像を処理するための電子デバイスであって、
プロセッサと、
前記プロセッサと電子通信するメモリと、
前記メモリに記憶された命令とを備え、前記命令は、
カレントピクセルのために、前記カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定し、ここで、前記マスクビットは、前記カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す、
処理するための次のピクセルを、前記マスクビットに基づいて選択するように実行可能である、電子デバイス。
［Ｃ２４］
前記選択するように実行可能な命令は、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスするように実行可能な命令を備える、Ｃ２３に記載の電子デバイス。
［Ｃ２５］
前記選択するように実行可能な命令はさらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択するように実行可能な命令をさらに備える、Ｃ２４に記載の電子デバイス。
［Ｃ２６］
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、Ｃ２３に記載の電子デバイス。
［Ｃ２７］
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、Ｃ２３に記載の電子デバイス。
［Ｃ２８］
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、Ｃ２３に記載の電子デバイス。
［Ｃ２９］
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、Ｃ２３に記載の電子デバイス。
［Ｃ３０］
前記カレントピクセルが、処理されていない隣接ピクセルを有していない場合、前記カレントピクセルを、極値領域の一部として分類するように実行可能な命令、をさらに備える、Ｃ２３に記載の電子デバイス。
［Ｃ３１］
前記カレントピクセルを、輪郭の一部として分類するように実行可能な命令、をさらに備える、Ｃ２３に記載の電子デバイス。
［Ｃ３２］
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理するように実行可能な命令、をさらに備える、Ｃ２３に記載の電子デバイス。
［Ｃ３３］
前記画像は、ビデオ内のフレームであり、前記電子デバイスは、前記ビデオ内のすべてのフレームを処理する、Ｃ２３に記載の電子デバイス。
［Ｃ３４］
画像を処理するためのコンピュータプログラム製品であって、命令を有する非一時的なコンピュータ読取可能な媒体を備え、前記命令は、
電子デバイスに対して、カレントピクセルのために、前記カレントピクセルと複数の隣接ピクセルとの強度比較を示すマスクビットを決定させるためのコードと、ここで、前記マスクビットは、前記カレントピクセルの隣接ピクセルの各々が処理されているか否かをも示す、
前記電子デバイスに対して、処理するための次のピクセルを、前記マスクビットに基づいて選択させるためのコードとを備える、コンピュータプログラム製品。
［Ｃ３５］
前記電子デバイスに対して選択させるための前記コードは、前記電子デバイスに対して、マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスさせるためのコードを備える、Ｃ３４に記載のコンピュータプログラム製品。
［Ｃ３６］
前記電子デバイスに対して、選択させるための前記コードは、前記電子デバイスに対して、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択させるためのコードをさらに備える、Ｃ３５に記載のコンピュータプログラム製品。
［Ｃ３７］
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、Ｃ３４に記載のコンピュータプログラム製品。
［Ｃ３８］
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、Ｃ３４に記載のコンピュータプログラム製品。
［Ｃ３９］
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、Ｃ３４に記載のコンピュータプログラム製品。
［Ｃ４０］
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、Ｃ３４に記載のコンピュータプログラム製品。
［Ｃ４１］
前記カレントピクセルが、処理されていない隣接ピクセルを有していない場合、前記電子デバイスに対して、前記カレントピクセルを、極値領域の一部として分類させるためのコード、をさらに備える、Ｃ３４に記載のコンピュータプログラム製品。
［Ｃ４２］
前記電子デバイスに対して、前記カレントピクセルを、輪郭の一部として分類させるためのコード、をさらに備える、Ｃ３４に記載のコンピュータプログラム製品。
［Ｃ４３］
前記電子デバイスに対して、ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理させるためのコード、をさらに備える、Ｃ３４に記載のコンピュータプログラム製品。
［Ｃ４４］
前記画像は、ビデオ内のフレームであり、前記電子デバイスは、前記ビデオ内のすべてのフレームを処理する、Ｃ３４に記載のコンピュータプログラム製品。
【手続補正書】
【提出日】平成27年9月30日(2015.9.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
画像内の極値領域にピクセルを割り振る際に使用するための方法であって、
（ａ）前記ピクセルと前記それぞれの隣接との強度比較を、複数の隣接ピクセルの各々のために、示し、前記それぞれの隣接ピクセルが処理されているか否かをも示すマスクビットを、前記画像内の各ピクセルのために、決定することと、
（ｂ）前記マスクビットを同時にチェックすることによって前記複数の隣接ピクセルのうちの少なくとも１つが処理されていないか否かを、前記マスクビットに基づいて、カレントピクセルのために、決定し、そうである場合は、処理するために前記処理されていない隣接ピクセルのうちの１つを選択し、前記選択された隣接ピクセルを処理することと、ここにおいて、強度比較を示す前記マスクビットに基づいて、前記カレントピクセルと前記選択された隣接ピクセルのうちの１つは、ヒープ上にキューされ、ステップ（ｂ）は、前記カレントピクセルと前記選択された隣接ピクセルのうちの他方のために反復される、
（ｃ）前記マスクビットに基づいて、カレントピクセルのための前記複数の隣接ピクセルのいずれも処理されていないことが決定される場合、前記カレントピクセルを前記極値領域に分類し、前記ヒープからポップした別のピクセルのためにステップ（ｂ）を反復することと、を備える、方法。
【請求項２】
前記処理されていない隣接ピクセルのうちの１つを前記選択することは、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスすることを備える、請求項１に記載の方法。
【請求項３】
前記処理されていない隣接ピクセルのうちの１つを前記選択することは、さらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択することを備える、請求項２に記載の方法。
【請求項４】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項１に記載の方法。
【請求項５】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項１に記載の方法。
【請求項６】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項１に記載の方法。
【請求項７】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または直交的に隣接する、請求項１に記載の方法。
【請求項８】
前記カレントピクセルを、輪郭の一部として分類すること、をさらに備える、請求項１に記載の方法。
【請求項９】
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理すること、をさらに備える、請求項１に記載の方法。
【請求項１０】
前記画像は、ビデオ内のフレームであり、前記方法は、前記ビデオ内のすべてのフレームに対して実行される、請求項１に記載の方法。
【請求項１１】
画像内の極値領域にピクセルを割り振る際に使用するための装置であって、
前記ピクセルと前記それぞれの隣接ピクセルとの強度比較を、複数の隣接ピクセルの各々のために、示し、前記それぞれの隣接ピクセルが処理されているか否かをも示すマスクビットを、前記画像内の各ピクセルのために、決定するための手段と、
前記マスクビットを同時にチェックすることによって前記複数の隣接ピクセルのうちの少なくとも１つが処理されていないか否かを、前記マスクビットに基づいて、カレントピクセルのために、決定し、そうである場合は、処理するために前記処理されていない隣接ピクセルのうちの１つを選択し、前記選択された隣接ピクセルを処理するための手段と、ここにおいて、強度比較を示す前記マスクビットに基づいて、前記カレントピクセルと前記選択された隣接ピクセルのうちの１つは、ヒープ上にキューされ、前記決定するための手段は、前記カレントピクセルと前記選択された隣接ピクセルのうちの他方のために前記決定することを反復するようにアレンジされる、
前記マスクビットに基づいて、カレントピクセルのための前記複数の隣接ピクセルのいずれも処理されていないことが決定される場合、前記カレントピクセルを前記極値領域に分類するための手段と、処理するために前記ヒープからポップした次のピクセルを選択するための手段と、を備える装置。
【請求項１２】
前記処理されていない隣接ピクセルのうちの１つを前記選択するための手段は、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスするための手段を備える、請求項１１に記載の装置。
【請求項１３】
前記処理されていない隣接ピクセルのうちの１つを前記選択するための手段はさらに、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択するための手段を備える、請求項１２に記載の装置。
【請求項１４】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項１１に記載の装置。
【請求項１５】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項１１に記載の装置。
【請求項１６】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項１１に記載の装置。
【請求項１７】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、請求項１１に記載の装置。
【請求項１８】
前記カレントピクセルを、輪郭の一部として分類するための手段、をさらに備える、請求項１１に記載の装置。
【請求項１９】
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理するための手段、をさらに備える、請求項１１に記載の装置。
【請求項２０】
前記画像は、ビデオ内のフレームであり、前記装置は、前記ビデオ内のすべてのフレームを処理する、請求項１１に記載の装置。
【請求項２１】
画像内の極値領域にピクセルを割り振る際に使用するための電子デバイスであって、
プロセッサと、
前記プロセッサと電子通信するメモリと、
前記メモリに記憶された命令とを備え、前記命令は、
（ａ）前記ピクセルと前記それぞれの隣接ピクセルとの強度比較を、複数の隣接ピクセルの各々のために、示し、前記それぞれの隣接ピクセルが処理されているか否かをも示すマスクビットを、前記画像内の各ピクセルのために、決定することと、
（ｂ）前記マスクビットを同時にチェックすることによって前記複数の隣接ピクセルのうちの少なくとも１つが処理されていないか否かを、前記マスクビットに基づいて、カレントピクセルのために、決定し、そうである場合は、処理するために前記処理されていない隣接ピクセルのうちの１つを選択し、前記選択された隣接ピクセルを処理することと、ここにおいて、強度比較を示す前記マスクビットに基づいて、前記カレントピクセルと前記選択された隣接ピクセルのうちの１つは、ヒープ上にキューされ、ステップ（ｂ）は、前記カレントピクセルと前記選択された隣接ピクセルのうちの他方のために反復される、
（ｃ）前記マスクビットに基づいて、カレントピクセルのための前記複数の隣接ピクセルのいずれも処理されていないことが決定される場合、前記カレントピクセルを前記極値領域に分類し、前記ヒープからポップした別のピクセルのためにステップ（ｂ）を反復することとを行うように実行可能である、電子デバイス。
【請求項２２】
前記処理されていない隣接ピクセルのうちの１つを前記選択するように実行可能な命令は、前記マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスするように実行可能な命令を備える、請求項２１に記載の電子デバイス。
【請求項２３】
前記処理されていない隣接ピクセルのうちの１つを前記選択するように実行可能な命令は、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択するように実行可能な命令をさらに備える、請求項２２に記載の電子デバイス。
【請求項２４】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項２１に記載の電子デバイス。
【請求項２５】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項２１に記載の電子デバイス。
【請求項２６】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項２１に記載の電子デバイス。
【請求項２７】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、請求項２１に記載の電子デバイス。
【請求項２８】
前記カレントピクセルを、輪郭の一部として分類するように実行可能な命令、をさらに備える、請求項２１に記載の電子デバイス。
【請求項２９】
ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理するように実行可能な命令、をさらに備える、請求項２１に記載の電子デバイス。
【請求項３０】
前記画像は、ビデオ内のフレームであり、前記電子デバイスは、前記ビデオ内のすべてのフレームを処理する、請求項２１に記載の電子デバイス。
【請求項３１】
画像を処理する際に、極値領域にピクセルを割り振る際に使用するためのコンピュータプログラム製品であって、命令を有する非一時的なコンピュータ読取可能な媒体を備え、前記命令は、
（ａ）前記ピクセルと前記それぞれの隣接ピクセルとの強度比較を、複数の隣接ピクセルの各々のために、示し、前記それぞれの隣接ピクセルが処理されているか否かをも示すマスクビットを、前記画像内の各ピクセルのために、決定することと、
（ｂ）前記マスクビットを同時にチェックすることによって前記複数の隣接ピクセルのうちの少なくとも１つが処理されていないか否かを、前記マスクビットに基づいて、カレントピクセルのために、決定し、そうである場合は、処理するために前記処理されていない隣接ピクセルのうちの１つを選択し、前記選択された隣接ピクセルを処理することと、ここにおいて、強度比較を示す前記マスクビットに基づいて、前記カレントピクセルと前記選択された隣接ピクセルのうちの１つは、ヒープ上にキューされ、ステップ（ｂ）は、前記カレントピクセルと前記選択された隣接ピクセルのうちの他方のために反復される、
（ｃ）前記マスクビットに基づいて、カレントピクセルのための前記複数の隣接ピクセルのいずれも処理されていないことが決定される場合、前記カレントピクセルを前記極値領域に分類し、前記ヒープからポップした別のピクセルのためにステップ（ｂ）を反復することとを電子デバイスに対して行わせるコードを備える、コンピュータプログラム製品。
【請求項３２】
前記電子デバイスに対して前記処理されていない隣接ピクセルのうちの１つを選択させるための前記コードは、前記電子デバイスに対して、マスクビットを、ルックアップテーブル内のインデクスとして用いて、前記ルックアップテーブル内のデータにアクセスさせるためのコードを備える、請求項３１に記載のコンピュータプログラム製品。
【請求項３３】
前記電子デバイスに対して、前記処理されていない隣接ピクセルのうちの１つを選択させるための前記コードは、前記電子デバイスに対して、前記カレントピクセルの隣接ピクセルのうちの何れかが、処理されておらず、かつ、前記カレントピクセルよりも低い強度であるか否かに基づいて、次のピクセルを選択させるためのコードをさらに備える、請求項３２に記載のコンピュータプログラム製品。
【請求項３４】
前記マスクビットは、各々の隣接ピクセルのための、比較ビットおよび処理ビットを備える、請求項３１に記載のコンピュータプログラム製品。
【請求項３５】
前記隣接ピクセルは、前記カレントピクセルに対して直交的に隣接する、請求項３１に記載のコンピュータプログラム製品。
【請求項３６】
前記隣接ピクセルは、前記カレントピクセルに対して対角的に隣接する、請求項３１に記載のコンピュータプログラム製品。
【請求項３７】
前記隣接ピクセルは、前記カレントピクセルに対して、対角的に隣接するか、または、直交的に隣接する、請求項３１に記載のコンピュータプログラム製品。
【請求項３８】
前記電子デバイスに対して、前記カレントピクセルを、輪郭の一部として分類させるためのコード、をさらに備える、請求項３１に記載のコンピュータプログラム製品。
【請求項３９】
前記電子デバイスに対して、ピクセルとその隣接ピクセルの各々との前記強度比較を実行することによって、前記画像内の各ピクセルを前処理させるためのコード、をさらに備える、請求項３１に記載のコンピュータプログラム製品。
【請求項４０】
前記画像は、ビデオ内のフレームであり、前記電子デバイスは、前記ビデオ内のすべてのフレームを処理する、請求項３１に記載のコンピュータプログラム製品。
【国際調査報告】
2016504698.tif 000035
2016504698.tif 000036
2016504698.tif 000037