画像にモルフォロジカル演算を適用するための方法及び画像にモルフォロジカル演算を実施するためのシステム
【課題】画像へのモルフォロジカル演算を適用するための効率的な方法を提供することである。
【解決手段】上記課題は、反復的にモルフォロジカル演算を画像の焦点ピクセル及び画像の別のピクセルに適用し、この別のピクセルは焦点ピクセルに関してオフセットにあり、このオフセットは演算カウントに基づくことによって解決される。
【解決手段】上記課題は、反復的にモルフォロジカル演算を画像の焦点ピクセル及び画像の別のピクセルに適用し、この別のピクセルは焦点ピクセルに関してオフセットにあり、このオフセットは演算カウントに基づくことによって解決される。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、U.S. Provisional Application No.60/637,653 filed December 20, 2004の利益を主張し、これは参照文献としてここに取り込まれる。
【背景技術】
【０００２】
本発明は一般的に画像処理に関し、より特定すれば、２値及びグレースケールアプリケーションの両方におけるモルフォロジー演算の計算の最適化に関する。
【０００３】
数学的モルフォロジーは、（例えばセグメント化及びスケルトン化タスクのために）コンピュータヴィジョン及び医用イメージングアプリケーションのような様々なデジタル画像処理アプリケーションに使用されている。例えば、医療要員は患者にコンピューテッドトモグラフィ（ＣＴ）スキャンを実施することができる。ＣＴスキャンはｘ線装置を使用して人体の周りの異なる角度から画像データを収集し、次いでこれらのデータを体組織及び器官の断面図を図示するために処理する。次いで、画像はハイライトされた特定エリアにモルフォロジカル演算子を使用する方法によって解析され、この結果、放射線技師（又は他の医療要員）が比較的簡単にガン、心臓血管疾病、感染性疾病、外傷及び筋骨格障害のような患者に関する問題を診断できる。
【０００４】
このタイプの画像解析はモルフォロジカル演算子（構造要素（structuring element(SE)）とも呼ばれる）を画像に適用することによって行われる。異なるスケールのＳＥは気道又は血管セグメント化を実施する場合のステップの間のように使用される。スケルトン化方法は所与のオブジェクトの中央軸を計算するためのモルフォロジカル演算子の繰り返される適用に依存する。
【０００５】
構造要素を入力画像に適用するために、構造要素は入力画像に沿って移動され、演算が実施される。基本的なモルフォロジー演算はダイレーション（dilation）及びエロージョン（erosion）である。２値ダイレーションは、入力画像の各ピクセル／ボクセルに関する構造要素（フィルターカーネルとも呼ばれる）により定義される近傍の論理ＯＲを計算し、その値を演算子の中心に割り当てることによって実施される。２値エロージョンは入力画像の各ピクセル／ボクセルに関する構造要素により定義される近傍の論理ＡＮＤを計算することによって実施される。グレーレベル画像の場合には、論理ＯＲ／ＡＮＤはグレーレベルダイレーション／エロージョンを発生するためにＭＡＸ／ＭＩＮ演算子により置き換えられる。論理ＯＲ／ＡＮＤはＭＡＸ／ＭＩＮ演算子とともに比較演算子と総称される。
【０００６】
図１は３×３正方形構造要素１００が入力画像１０４に適用される事例を示す。実施される演算は２値ダイレーションであり、この２値ダイレーションは入力画像１０４の各ピクセルに関して構造要素１００により定義される近傍の論理ＯＲを計算することによって実施される。ダイレーションを実施するためには、ＳＥ１００の中央ピクセル１０８が入力画像１０４の各ピクセルに位置決めされ、ＯＲ演算子が非零である場合にＳＥ１００が入力画像ピクセルと代わる。異なった結果を出すためには、構造要素１００が入力画像１０４のどのピクセルをＯＲするかを特定する。よって、ダイレーション演算子は結果的に出力画像１１２を生じ、この出力画像１１２は入力画像１０４よりも多くの非零ピクセルを含む。シェードを付けられたピクセル１１６は演算の結果として加えられたピクセルを表し、他方で白いピクセル１１８はオリジナル入力画像１０４からのものである。画像１１２は「オフ（off）」であるピクセル１２０により取り囲まれており、これらの「オフ（off）」であるピクセル１２０はバイナリ値０を有し、画像の部分（すなわち、「オン（on）」であるピクセル）ではない。
【０００７】
図１はさらに同じ正方形ＳＥ１００が２値エロージョンにおいて同じ入力画像１０４に適用される事例を示す。前述のとおり、２値エロージョンは構造要素１００と入力画像１０４との間の論理ＡＮＤ演算を使用する。出力画像１２０は入力画像１０４に比べて「オン」ピクセルの数が少ない。この例では、残っているのはただ一つのピクセルである。というのも、入力画像の中には演算子がこの画像により包含されるたった１つの位置しかなく、このたった１つの位置がＡＮＤ演算に対して真値をもたらすからである。画像１２０はオフであるピクセル１２４（すなわちバイナリ値０を有する）によって囲まれている。
【０００８】
これらのモルフォロジー演算のダイレクトな適用は計算機的にはインテンシブである。とりわけ、コンピュータにより必要とされる計算時間はダイレクトに実施される計算機的演算の数及びタイプに比例し、これが今度はＳＥと画像サイズとの積に比例する。タイムリーなやり方で結果を得るためには、効率的なアルゴリズムが必要である。さもなければ、ＳＥ又は入力画像のサイズに制限されてしまう。
【０００９】
モルフォロジカル演算を実施するために使用されうる幾つかのアルゴリズムがある。最もシンプルなアプローチはブルートフォース（brute force）アルゴリズムである。ブルートフォースアルゴリズムはＳＥ内の全ピクセル／ボクセルをピクセル毎に計算して確かめる。結果は異なる画像へと格納される。ブルートフォースアルゴリズムの計算時間は構造要素の「デジタルマス（digital mass）」に依存する。デジタルマスは、２次元（すなわち２Ｄ）ジオメトリ（すなわちそのディスクリートエリア）のコンテキストにおける特定の範囲内のピクセルの数又は特定の３次元（すなわち３Ｄ）ジオメトリ（すなわちそのディスクリートボリューム）内のボクセルの数に関連する。よって、ブルートフォースアルゴリズムでは、各出力ピクセルは構造要素のデジタルマスマイナス１（中央ピクセル）に等しい演算の数を必要とする。特に、正方形構造要素１００が３ピクセルの長さ及び幅を有する場合には、この構造要素１００を使用して出力画像１１２、１２０の各ピクセルを得るために必要な（以下においてはｏｐｓと呼ぶ）演算の数は、正方形構造要素１００のエリアマイナス１（すなわち８ｏｐｓ）である。さらに、ますます多くの構造要素が異なる出力画像を得るために使用されるならば、計算時間量は指数関数的に増大する。例えば、正方形構造要素の直径（側面長）が線形に増大するにつれて、計算時間はその直径の二乗に比例して増大する。立方体の場合には、計算時間はこの立方体の側面長が線形に増大するにつれてその側面の三乗により増大する。
【００１０】
モルフォロジカル演算を実施するための別の技術は因数分解アルゴリズム（factorization algorithm）である（例えばhomotopic decomposition）。この因数分解アルゴリズムは「基本(fundamental)」構造要素を使用する。これらの基本構造要素はより大きな構造要素を「破壊する」ために使用される。従って、１つの大きなＳＥを画像に適用する代わりに、一連の基本ＳＥが使用される。最終結果は同一であるが、計算時間は低減される。なぜなら、より小さいＳＥのために必要な演算の数が単一の大きなＳＥのそれよりも小さいからである。例えば、構造要素が半径２の立方体であるとする。ブルートフォースアルゴリズムでは、５３−１＝１２４ｏｐｓが出力画像ボクセル毎に必要とされる。しかし、因数分解アルゴリズムを使用すれば、出力画像ボクセル毎に（３３−１）*２＝５２ｏｐｓが必要とされる。因数分解によって、計算費用はそのデジタルマスよりもむしろ考慮される構造要素を制限する立方体のディスクリートな直径に比例する。よって、因数分解アルゴリズムはブルートフォース技術において有意義な計算機的な節約を提供する。
【００１１】
しかし、因数分解アルゴリズムも大きな落とし穴を有する。近似なしでアルゴリズムが使用される比較的大きな構造要素の形状はシビアに使用される基本構造要素によって限定されてしまう。例えば、２次元デジタル化された円形構造要素又は３次元球形構造要素は人体（例えば気道）の構造のために医用画像処理を実施するためにしばしば使用される形状である。しかし、因数分解アルゴリズムは、大抵の場合、デジタル化された円又は球の形状に対して可能な基本構造要素の形状のために、過度な複雑性なしには円状又は球状構造要素には使用できない。従って、実際的な目的のためには、最良の可能な結果は円又は球の近似である。
【００１２】
結果的に、構造要素の形状に制約を課すことなしにモルフォロジカル演算子を実施する場合には、特に円及び球に対して、計算時間を低減する必要性がまだ残存している。
【特許文献１】U.S. Provisional Application No.60/637,653 filed December 20, 2004
【発明の開示】
【発明が解決しようとする課題】
【００１３】
画像へのモルフォロジカル演算を適用するための効率的な方法を提供することである。
【課題を解決するための手段】
【００１４】
上記課題は、反復的にモルフォロジカル演算を画像の焦点ピクセル及び画像の別のピクセルに適用し、この別のピクセルは焦点ピクセルに関してオフセットにあり、このオフセットは演算カウントに基づくことによって解決される。
【発明を実施するための最良の形態】
【００１５】
本発明は画像へのモルフォロジカル演算を適用するための効率的な方法である。２値及びグレースケールモルフォロジーの両方が多次元画像においてサポートされる。モルフォロジカル演算（例えばダイレーション又はエロージョン）は反復的に画像の焦点ピクセル及び焦点ピクセルに関してオフセットに配置された他のピクセルに適用される。このオフセットは演算カウントに基づき、この演算カウントはモルフォロジー演算が適用される毎に増大する。演算カウントは１から所定の演算回数まで増大する。最後の２回の演算を除く全て演算に対するオフセットは２Ｎ−１によって決定され、ここでNは演算カウントである。
【００１６】
必要とされる演算の数は画像に適用される構造要素の予め決定された長さの対数に基づく。とりわけ、必要とされる演算の数はlog２(Ｑ)のシーリング（ceiling）に等しく、ここでＱは特定の次元における構造要素の予め決定された長さである。全演算（比較）は最後の演算と除いて中央ピクセルに対して特定の方向に進み、最後の演算は逆方向に進む。最後の演算のオフセットはフロア（floor）（Ｑ／２）のネガティブである。最後から２番目の演算はシーリング（Ｑ／２）−２（Ｎ−２）のオフセットを有し、Nは演算カウントである。
【００１７】
１つの実施形態では、構造要素はさらに予め決定された幅及び／又は予め決定された高さを含む。いくつかの実施形態では、ピクセルはボクセルである。
【００１８】
本発明の方法は、凸状構造要素を使用する画像にモルフォロジカル演算を実施するための方法を含む。反復的に画像に凸状構造要素の最も外側の寸法に相応する寸法を有するワーク構造要素が適用される。付加的なワーキングキャンバス（画像）が中間計算のために使用される。以前のワーク構造要素によってはまだ被覆されていない凸状構造要素の残りの外側寸法に相応するようにワーク構造要素の寸法が調整される。この調整は常に大きくなり、以前の反復の結果が現在の反復において使用されることを許容する。適用及び調整ステップは、予め決定された数のモルフォロジカル演算が実施されるまで繰り返され、この結果、所与の凸状構造要素のモルフォロジー計算が得られる。
【００１９】
凸状構造要素は円形ディスク、球及び楕円であればよい。ワーク構造要素はさらに１次元構造要素又は長方形構造要素でもよい。それはダイアモンド形状又は対角線要素でもよい。計算の以前の数はさらにワーク構造要素の現在の長さ及び以前の長さの対数のシーリングを含む。
【００２０】
これらの及び他の本発明の利点は当業者には以下の詳細な記述及び添付図を参照すれば明らかである。
【実施例】
【００２１】
以下の記述は本発明を本発明の実施形態をインプリメントするために必要な処理ステップに関して記述する。これらのステップは適切にプログラムされたコンピュータにより実施され、このコンピュータのコンフィギュレーションは従来技術において公知である。適当なコンピュータは例えば周知のコンピュータプロセッサ、メモリユニット、ストレージデバイス、コンピュータソフトウェア及び他のコンポーネントを使用してインプリメントされる。このようなコンピュータのハイレベルブロック線図が図２には示されている。コンピュータ２０２はプロセッサ２０４を含み、このプロセッサ２０４はコンピュータプログラム命令を実行することによってコンピュータ２０２の演算全体をコントロールし、このコンピュータプログラム命令はこのような演算を定義する。コンピュータプログラム命令はストレージデバイス２１２（例えば磁気ディスク）に格納され、コンピュータプログラム命令の実行が所望される時にメモリ２１０にロードされる。コンピュータ２０２は１つ又は複数のインターフェース２０６を他のデバイスとの（例えばローカルに又はネットワークを介しての）通信のために含む。コンピュータ２０２はインプット／アウトプット２０８も含み、このインプット／アウトプット２０８はコンピュータ２０２とのユーザインタラクションを可能にするデバイスを表す（例えば、ディスプレイ、キーボード、マウス、スピーカ、ボタンなど）。当業者ならば、実際のコンピュータのインプリメンテーションが他のコンポーネントを含むこと及び図２は説明目的のためのこのようなコンピュータのコンポーネントのうちのいくつかのハイレベル表現であることを認めるだろう。さらに、当業者ならば、ここで記述される処理ステップは回路が特にこのような処理ステップをインプリメントするために構成されている特定用途ハードウェアを使用してインプリメントされうることを認めるだろう。代替的に、処理ステップはハードウェアとソフトウェアの様々なコンビネーションを使用してインプリメントされうる。
【００２２】
図３は１次元画像キャンバス３００のブロック線図を示し、関心ピクセル（すなわち焦点ピクセル）３０４をハイライトしてある。画像キャンバス３００は画像を含むピクセル（又はボクセル）のエリアである。焦点ピクセル３０４は最適化アルゴリズムとして後述される一連の演算によってどのように単一ピクセルが影響を受けるのかをより良く伝えるために使用される。もっとも、これらの演算は入力画像の全ピクセルに適用されるのだが。この例では、ブルートフォース方法の代わりに、一連の比較が画像キャンバス３００において各ステップでたった２つの画素の間で行われる。これはその特定のステップに対して２つの要素（ｓｐａｒｓｅ）ＳＥを有することに似ている。各適用事例は２つの画素の間の右オフセットを増大させることを含む：（これは論理ＯＲ、論理ＡＮＤ、ＭＡＸ又はＭＩＮのうちの１つでもよいが）行における各ピクセルのその右の隣との論理ＯＲ（すなわち各ピクセルを右側へとその隣によってダイレートすること）。最適化アルゴリズムは比較演算子の等冪性（idempotency property）を利用する（すなわち、要素に一回以上この演算子を実施するとこの演算子が一回適用された場合と同じ結果を発生する）。
【００２３】
コンピュータ２０２はこの最初の演算を現場で実施する（すなわち、焦点ピクセル３０４とその右の隣接ピクセルとの間のＯＲ演算の結果が焦点ピクセル３０４での出力である）。この最初のダイレーションは行３０８（すなわちno ops行）から行３０４（１ops 行）を生じる。各事例に対する下記の各演算がベクトル化されていることに注目してもらいたい。つまり、各演算は計算が継続するとともに焦点ピクセルを結果的に置換するのである。よって、最初の演算においては、キャンバス３００における各ピクセルはそれ自体とその直ぐ右側の隣接ピクセルとの間の論理ＯＲによって置換される。
【００２４】
結果的に、各ピクセルの出力はそれ自体と隣接ピクセルとの演算の結果である。これは以下において演算のスパン（the span of the operation）と呼ばれ、すなわちそのピクセルがピクセルに格納された情報の結果に寄与する。図３における焦点ピクセル３０４のスパンにはシェードが付けられている。１回の演算の後で、行３１２における焦点ピクセル３０４のスパンはそれ自体とその右側の隣接ピクセルである。
【００２５】
次に、論理ＯＲ演算が各ピクセルとその隣接ピクセルではなく右へと１つだけ越えたピクセルとの間で実施される。これは行３１２から行３１６への矢印により示されている。この結果、２つのＯＲ演算の後で、スパンは４ピクセルである。このスパンは４ピクセルである、なぜならこの論理ＯＲ演算は事実上焦点ピクセル３０４及びその右隣りならびに第３のピクセル及びその右隣りをカバーしているからである。
【００２６】
次の演算子は行３１６から行３２０へと示されているように、第４のピクセル３２４に実施される。焦点ピクセル３０４と第４のピクセル３２４との論理ＯＲによって、スパンは８ピクセルに増大する。特に、焦点ピクセル３０４がその３つの隣接ピクセルとの論理ＯＲの結果（すなわち４つのピクセル）であるように、第４のピクセル３２４はその３つの隣接ピクセルとの論理ＯＲの結果（すなわち４つのピクセル）である。画像に対して実施される３ｏｐｓの結果は、画像に対する８ピクセル幅ＳＥ計算と同じである。
【００２７】
出力ピクセル毎にＭ個のｏｐｓにおいてカバーされうる最大スパンは２Ｍである。この限定の逆は、Ｎ個の隣接するピクセルのモルフォロジカルな比較を実施するために必要とされる最小演算数Ｍｍｉｎが
Ｍｍｉｎ＝ＣＥＩＬ（log２(Ｎ)）
により定義されることである。
【００２８】
上記の最適化アルゴリズムをブルートフォース技術と比較すると、この最適化アルゴリズムは８個の論理ＯＲ演算（すなわち８ダイレーション）をたった３ｏｐｓで実施することに等価である。しかし、ブルートフォース技術は８個の論理ＯＲ演算を実施するために８ｏｐｓを必要とする。よって、この最適化アルゴリズムは有意義な計算節約を提供する。
【００２９】
特例として、下記のように左端のピクセル（太字）にセンターを有する１Ｄの４つのピクセル構造要素が同じく下記のような入力画像をダイレート（dilate）するために使用されると仮定しよう：
１１１１ 構造要素
０００００１０００００ 入力画像
ブルートフォースアプローチによれば、構造要素の中央ピクセルは入力画像の各ピクセルと整列され、次いで構造要素によって定められる入力画像の近傍がＯＲ演算される。この結果、出力画像
００１１１１０００００
が得られる。
【００３０】
入力画像に最適化アルゴリズムを使用すると、得られる結果は各演算毎に：
no ops ：０００００１０００００
1 op ：００００１１０００００
2 ops ：００１１１１０００００
となる。
【００３１】
図示されているように、最適化アルゴリズムは２回の演算の後でブルートフォースアルゴリズムと同一の結果を生じる。４ピクセル１次元構造要素に対して必要な演算の数は上記の式から決定される：２Ｎ＝４；Ｎ＝２ｏｐｓ。よって、２ｏｐｓが４ピクセル１次元構造要素を適用する場合に得られるのと同じ出力画像を得るために必要である。上記の説明では、１方向のｏｐｓだけが示されている。これは左側センターピクセルを有するＳＥだけを可能にする。同様に反対方向の単一ｏｐの使用は対称的な演算子を可能にする。
【００３２】
上記の原理に基づいて、長方形構造要素最適化アルゴリズムが画像への長方形構造要素の提供に使用されうる。図４は画像キャンバス４００に対して最適化アルゴリズムを使用する５×７長方形構造要素に対する２値ダイレーションのブロック線図を示す。焦点ピクセル４０４は関心ピクセルを表し、上記のように演算がベクトル化されている。
【００３３】
ステップ４５０はそれ自体とその右隣との間での論理ＯＲを表す焦点ピクセル４０４を示す。次に、ステップ４５４では、論理ＯＲが再び焦点ピクセル４０４とその右隣との間で実施される。これは（ステップ４５４に示されているように）（ベクトル化のために）焦点ピクセル４０４の右側に２ピクセルを含むスパンを増大させる。よって、焦点ピクセル４０４はステップ４５４においてシェードを付けられた２つのピクセルに関する情報を含む。ステップ４５８では、コンピュータ２０２は焦点ピクセル４０４に対する遠心ピクセル（distal pixel）の方向を逆転させ（すなわち、焦点ピクセルｘ［ｍ，ｎ］＝ｘ［ｍ，ｎ］｜ｘ［ｍ−２，ｎ］）、この結果、スパンが反対方向に拡張する。これは長方形構造要素の焦点ピクセル４０４に関してスパン対称性を維持することである。ステップ４５８の終了時には、各ピクセルは長さ５の１行であるスパンを有する。
【００３４】
ステップ４６２では、コンピュータ２０２は焦点ピクセル４０４とその直下のピクセルとの間の論理ＯＲを計算する。これは実際には５×２近傍に配置された１０個のオリジナルピクセル値の間の論理ＯＲである。コンピュータ２０２はステップ４６６及び４７０でステップ４５４及び４５８と同じやり方で最適化アルゴリズムをインプリメントしつづける。ただしここでは水平方向ではなく垂直方向にこのアルゴリズムが適用される。最終結果はステップ４７０に示されている。焦点ピクセル４０４は画像キャンバス４００との５×７長方形構造要素のダイレーション結果を表す。さらに、２Ｄ長方形構造要素に関して上では記述したが、上記の最適化アルゴリズムはさらに３次元長方形構造要素（例えば、５×５×７）に適用しうる。
【００３５】
以下においては２値ダイレーション演算子（すなわち論理ＯＲ）の適用を記述するが、最適化アルゴリズムはいかなる比較演算子をも使用できる。それゆえ、ＯＲ演算子はいかなる他のモルフォロジカル比較演算子（例えば、ＡＮＤ、ＭＩＮ又はＭＡＸ）によっても置換されうる。この能力はこの方法を２値領域とグレースケール領域の両方に適用することを可能にする。対角方向におけるこの方法の適用は、ダイアモンド形状の構造要素のモルフォロジー計算を可能にする。
【００３６】
図５は長方形又は立方体構造要素によるダイレーションのための最適化アルゴリズムのフローチャートを示す。このフローチャートは２Ｄケース及び３Ｄケースが両方とも１Ｄケースの拡張である（すなわち異なる軸に適用される）ように１Ｄケースにおける一般化を示す。それゆえ、図５は２値ピクセルの奇数長（Ｑ）ランの論理比較を効率的に得るための最適化アルゴリズムを示し、他方で最終結果における対称性を維持するようにしている。
【００３７】
Ｑ個のピクセルを比較するために必要とされる必要なｏｐｓの最小数（Ｎ）は最初にステップ５０４で決定される。この最小数は上記の式により与えられる：
Ｎｍｉｎ＝ＣＥＩＬ（log２(Ｑ)）
最終結果が対称的となるように、最後のｏｐ（すなわちＮ）を除く全てのｏｐｓ（すなわち、最初のＮ−１ｏｐｓ）はステップ５０８において（フォワード方向と呼ばれる）１方向へのスパンを増大させて拡張される。最後のｏｐはリバース方向へのスパンを増大させて拡張される。
【００３８】
焦点ピクセルに対する各ｏｐのオフセットを得ることが必要である。累積する論理ｏｐｓに対するＮ−１個のフォワードオフセットが存在するだろう。なぜなら、最後のｏｐはリバース方向にあるからである。最初のＮ−２ｏｐｓ（すなわち最後のフォワードｏｐを除く全て）は焦点ピクセルに関して２Ｐのオフセットで実行され、ただしここでP∈［０，１，２，・・・（Ｎ−２）−１］である。最後のフォワードオフセットはＣＥＩＬ（Ｑ／２）−２（Ｎ−２）である。
【００３９】
コンピュータ２０２は次いでステップ５１２でリバース方向にスパンを拡張する。コンピュータ２０２は最初に焦点ピクセルに関して最後のｏｐのためのオフセットを決定する。このオフセットは−ＦＬＯＯＲ（Ｑ／２）であり、このマイナス符号はオフセットがリバース方向であることを示すために使用される。
【００４０】
例えば、Ｎ＝２の場合には、たった一つのフォワードオフセット（Ｎ−１）しかない。これはＱ＝３の場合に生じる（すなわち、焦点ピクセル、焦点ピクセルの右に１ピクセル及び焦点ピクセルの左に１ピクセルが構造要素を構成する）。
【００４１】
上記でも下記でも２値ダイレーション演算子を適用することが記述される（例えば論理ＯＲ）が、最適化アルゴリズムはいかなる比較演算子をも使用できる。それゆえ、ＯＲ演算子は同じくいかなる他のモルフォロジカル比較演算子（例えば、ＡＮＤ、ＭＩＮ又はＭＡＸ）によっても置換されうる。さらに、ステップ５０４〜５１２は残りの軸において繰り返される。
【００４２】
図６Ａ〜６Ｃはブルートフォースアルゴリズム、因数分解アルゴリズム及び最適化アルゴリズムを立方体構造要素に対して使用してその半径が１〜１０まで増大する時の様子を時間に対してタイムプロットしたものを示す。
【００４３】
図６Ａは立方体構造要素の半径が増加するにつれてブルートフォースアルゴリズムにおいて計算消費が指数関数的に増大することを示す。よって、立方体構造要素の半径が６である時、曲線６０２はブルートフォースアルゴリズムを使用する構造要素を適用するために必要な時間がほぼ２０００ユニット（例えば秒）であることを示す。他の２つの方法により必要とされるタイミングはブルートフォース方法の時間を示すために必要な高さのためにほとんど見えない。
【００４４】
図６Ｂは立方体構造要素の半径が増加するにつれて因数分解アルゴリズムにおいて計算消費が線形に増大することを示す曲線６０４を示している。立方体構造要素の半径が６である時、曲線６０４は因数分解アルゴリズムを使用する構造要素を適用するために必要な時間がほぼ１５０ユニット（例えば秒）であることを示す。タイムスケールはブルートフォースアルゴリズムの場合の０〜１００００から因数分解アルゴリズムの場合の０〜３００にまで低減されている。提案される本発明の方法の時間はここでもほとんど見えない。
【００４５】
図６Ｃは上記のような最適化アルゴリズムの場合の計算消費が立方体構造要素の半径のｌｏｇに比例することを示す曲線６０８を示している。立方体構造要素の半径が６である時、曲線６０８は構造要素を適用するために必要な時間がほぼ１２ユニット（例えば秒）であることを示す。タイムスケールは因数分解アルゴリズムの場合の０〜３００から最適化アルゴリズムの場合の６〜１６にまで低減されている。
【００４６】
最適化アルゴリズムは２Ｄ円形（又は楕円）又は３Ｄ球体（又は楕円体）のようなデジタル的に凸状（convex）構造要素にも適用されうる。ここでは凸性（convexity）とは、デジタル的に凸状の構造（２Ｄ）におけるいかなるピクセルの中心点からも同一構造のいかなる他のピクセルの中心点へとラインを描くことが可能であること及びラインが完全にこの構造体の内部に存在しければならないか又はもしラインがこの構造の外側に出てしまってもそのラインセグメントにより制限されるエリア及びこのラインセグメントと共通の開始点及び終了点を共有するデジタル構造の境界セグメントがこの構造の部分ではないいかなるピクセルの中心点をも含まないことを意味する。
【００４７】
１つの実施形態では、円状構造要素を適用するために、２つの画像キャンバスが最適化アルゴリズムを使用してモルフォロジー結果を達成するために必要とされる。コンピュータ２０２は最適化アルゴリズムを反復的に実施し、この場合、各反復がスパン拡張ステップ及びピックアップ／比較ステップを含む。各反復においてコンピュータ２０２は残ってアドレス指定される構造要素を「チップアウェイ（chips away）」する。
【００４８】
構造要素はトップダウンで検査される。すなわち、ユニークな長さを有するその最も外側の行／列が考察されなければならない。凸性によって、生じる各々新しい行／列長さが以前のものよりも長くなるだろう。こうして、ワークキャンバスの各ピクセルにおいて比較が行われるところの近傍のスパンが拡張される。これによって以前の反復によって既に利用可能な計算に基づいて形成することが可能となる。これらの中間結果のシステマティックな合成は所望のモルフォロジー結果をもたらす。構造要素の分解はアルゴリズム（トップダウン）に対する"divide and conquer"アプローチである。なぜなら、それはダイナミックプログラミング（ボトムアップ）に類似したフレームワーク内でモルフォロジーをインプリメントするためのステージを設定するからである。よって、隣接出力ピクセルにおけるオリジナルキャンバスの比較の空間的オーバーラップが利用される。
【００４９】
図７は｛５，９，１１，１３，１５，１７｝の行長さ及び｛１，５，９，１１，１３，１５｝の列長さを有する凸状構造要素（２Ｄデジタル化された円）７００の例を示す。この構造要素７００は上記の因数分解アルゴリズムには向いていない。２つの画像キャンバスが各反復において更新され、ここで暫定ワークキャンバスＷは最初に更新され、長方形スパン拡張を反映する（パート１）。これに続いて、出力画像キャンバスＯ自体と更新されたＷとの間でのベクトル化された比較により出力画像キャンバスＯを更新する（パート２）。１つの実施形態では、入力画像キャンバスがＯのために使用される。代替的に、別個の画像キャンバスが使用される。
【００５０】
図８Ａ及び８Ｂは２つの図７に示された２Ｄ円形構造要素を画像に適用する最適化アルゴリズムにおける２つの画像キャンバス８０４、８０８を示す。中間キャンバスＷ８０４はオリジナル画像及びそれ自体における計算からの結果を含む。最終出力画像Ｏ８０８はＷとそれ自体との間で行われた演算を含む。このアプリケーションは３回の反復で完了する。第１の部分８０４の３回の反復では、もし適切な構造要素によりダイレートされるならば、残っている構造要素（ＲＳＥ）を完全にカバーするために使用されうるようにＷの長方形ダイレーションフットプリントが最も大きい長方形に増大される。第２の部分８０８の３回の反復では、ＷがシステマティックにＯと比較される。Ｗの長方形ダイレーションフットプリントはＲＳＥと相関するようにオフセットされる。よって、Ｏ内の各ピクセルは、ＲＳＥの最も外側のユニークな行及び列がチップアウェイされうるようにそれ自体と相応の位置からオフセットされるＷ値との比較により更新される。
【００５１】
とりわけ、コンピュータ２０２は最初に５ピクセルの行である構造要素を使用してＷに対する適切な（in place）ダイレーションを実施し、次いでその結果を横切って、反復１におけるＯを形成する。この結果、Ｗ内の４ピクセルがＯ内の単一中央ピクセルへと結合され、これはｓｐａｒｓｅ４ピクセルＳＥを適用することに似ている。これは本質的に残ってアドレス指定される構造要素を「チップアウェイ」する。更新されたＲＳＥは今や（図７に示されたような）オリジナルの構造要素に関して除去されたトップ及びボトム行及び最も左の及び最も右のピクセルを有する。
【００５２】
反復２では、Ｗは９×５長方形構造要素を有するオリジナル画像のダイレーション結果を含むことを要求される。といのも、それらはＲＳＥの最も外側の行／列長さ（すなわち、先のステップで構造要素によりカバーされなかった最も外側の寸法）であるからである。反復１の結果、Ｗは既に５×１長方形構造要素を有するダイレーション結果を含んでいる。それゆえ、コンピュータ２０２は５×１長方形ダイレーションフットプリントが９×５長方形ダイレーションフットプリントに拡張されるようにＷを更新する必要がある。注意すべきは、このステップが反復１からのデータを再利用することであり、これによりこのステップはスクラッチから９×５ＳＥを計算するよりも計算的により効率的なものにする。次いで、Ｗ内のピクセルはストラテジー的にＯ内のピクセルと比較される。反復２の終了時にＯの各ピクセルに反映されるダイレーションフットポイントが示されている。
【００５３】
反復３において、コンピュータ２０２はＷ内のダイレーション結果を１３×９（これは更新されたＲＳＥの最も外側の行／列長さである）となるように拡張し、所望の結果を得るためにＯとのピッキング／比較の最終ラウンドを行う。いかなる凸状のＸ−Ｙ対称構造要素に対してもここで概略を述べたアルゴリズムを実施するために必要とされるパラメータは反復の回数、各反復毎のＷの内の長方形スパンにおける増大（すなわち、第１の部分８０４）及びＯ焦点位置に関してＷ要素をセレクトするためのオフセット（第２の部分８０８）である。Ｗにおいて必要とされるパディング（すなわち、構造要素の調整（例えば拡張））は前述の式よりもより一般的な式による。この一般的な式は
Ｎｍｉｎ＝ＣＥＩＬ（log２(Ｌｎｏｗ／Ｌｐｒｅｖ)）
である。
【００５４】
よって、必要とされるモルフォロジカル演算の最小回数は長方形構造要素の現在の長さ及び以前の長さに依存している。
【００５５】
さらに、２Ｄ円状構造要素に対する上記の最適化アルゴリズムは３Ｄ球状構造要素にも適用される。３Ｄ球の場合には、６以上のボクセル演算子が使用されることになる。凸状構造要素の別の例は楕円である。
【００５６】
図９は変化する直径を有する１０個の円形構造要素を使用する５１２×５１２×５０閾値ＣＴサブイメージの２値ダイレーションのための実行時間の線図９００を示す。線図９００は従来技術の（例えばＭＡＴＬＡＢツールボックス）アルゴリズムを使用する場合にディスクリートな円形構造要素の半径が増大する時の計算時間の増大を示すプロット９０４を示している。プロット９０８は上記の最適化アルゴリズムを使用する場合に円形構造要素の半径が増大する時の計算時間の増大を示す。従来技術において達成される最大実行時間はほぼ１１００秒であり、他方で線図９００では最適化アルゴリズムにおいて達成される最大実行時間はほぼ２００秒である。
【００５７】
上記の詳細な記述はあらゆる観点から説明的及び例示的なものであり、限定的なものではないと理解してほしい。さらに、ここで開示された本発明の範囲はこの詳細な記述から決定されるべきではなく、むしろ特許法により許可される最大外延に従って解釈されるように請求項から決定されるべきである。ここに示され上述された実施例は単に本発明の原理の例証となるものであり、様々な修正が本発明の範囲及び精神から離れることなく当業者によりインプリメントされうることを理解してほしい。当業者は本発明の範囲及び精神から離れることなく様々な他のフィーチャ組み合わせをインプリメントできるはずである。
【図面の簡単な説明】
【００５８】
【図１】３×３正方形構造要素による入力画像の２値ダイレーション及びエロージョンの従来技術のブロック線図を示す。
【図２】本発明の実施例によるコンピュータのハイレベルブロック線図である。
【図３】本発明の実施例による１次元（１Ｄ）行における最適化されたモルフォロジーアルゴリズムのブロック線図である。
【図４】本発明の実施例による最適化アルゴリズムを使用する５×７長方形構造要素における２値ダイレーションのブロック線図である。
【図５】本発明の実施例による長方形又は立方体構造要素による画像のダイレーションのための最適化アルゴリズムのフローチャートである。
【図６】図６Ａ〜６Ｃは本発明の実施例による立方体構造要素の半径が１〜１０まで増大する時のブルートフォースアルゴリズム、因数分解アルゴリズム及び最適化アルゴリズムを使用する際に必要とされる時間のプロットを示す。
【図７】本発明の実施例による２Ｄ凸状構造要素の例を示す。
【図８】図８Ａ及び８Ｂは本発明の実施例による画像への楕円状構造要素の適用のための最適化アルゴリズムの適用事例のブロック線図である。
【図９】本発明の実施例とブルートフォースインプリメンテーションによる変化する直径を有する１０個の円状構造要素を使用する５１２×５１２×５０閾値ＣＴサブイメージの２値ダイレーションのための実行時間を比較する線図を示す。
【符号の説明】
【００５９】
１００ 正方形構造要素
１０４ 入力画像
１０８ 中央ピクセル
１１２ 出力画像
１１６ シェードを付けられたピクセル
１１８ 白いピクセル
１２０ 「オフ」であるピクセル
２０２ コンピュータ
２０４ プロセッサ
２０６ インターフェース
２０８ Ｉ／Ｏ
２１０ メモリ
２１２ ストレージ
３００ １次元画像キャンバス
３０４ 関心ピクセル（焦点ピクセル）
３０８ 行
３１２ 行
３１６ 行
３２０ 行
３２４ 第４のピクセル
４００ 画像キャンバス
４０４ 焦点ピクセル
６０２ ブルートフォースアルゴリズムの際の計算消費曲線
６０４ 因数分解アルゴリズムの際の計算消費曲線
６０８ 最適化アルゴリズムの際の計算消費曲線
７００ 凸状構造要素
８０４ 第１の部分、中間キャンバスＷ
８０８ 第２の部分、最終出力画像Ｏ
ＲＳＥ 残っている構造要素（the remaining structuring element）
ＳＥ 構造要素（structuring element）
９００ 変化する直径を有する１０個の円形構造要素を使用する５１２×５１２×５０閾値ＣＴサブイメージの２値ダイレーションのための実行時間の線図
９０４ 従来技術の（例えばＭＡＴＬＡＢツールボックス）アルゴリズムを使用する場合にディスクリートな円形構造要素の半径が増大する時の計算時間の増大を示すプロット
９０８ 本発明の最適化アルゴリズムを使用する場合に円形構造要素の半径が増大する時の計算時間の増大を示すプロット
【技術分野】
【０００１】
本出願は、U.S. Provisional Application No.60/637,653 filed December 20, 2004の利益を主張し、これは参照文献としてここに取り込まれる。
【背景技術】
【０００２】
本発明は一般的に画像処理に関し、より特定すれば、２値及びグレースケールアプリケーションの両方におけるモルフォロジー演算の計算の最適化に関する。
【０００３】
数学的モルフォロジーは、（例えばセグメント化及びスケルトン化タスクのために）コンピュータヴィジョン及び医用イメージングアプリケーションのような様々なデジタル画像処理アプリケーションに使用されている。例えば、医療要員は患者にコンピューテッドトモグラフィ（ＣＴ）スキャンを実施することができる。ＣＴスキャンはｘ線装置を使用して人体の周りの異なる角度から画像データを収集し、次いでこれらのデータを体組織及び器官の断面図を図示するために処理する。次いで、画像はハイライトされた特定エリアにモルフォロジカル演算子を使用する方法によって解析され、この結果、放射線技師（又は他の医療要員）が比較的簡単にガン、心臓血管疾病、感染性疾病、外傷及び筋骨格障害のような患者に関する問題を診断できる。
【０００４】
このタイプの画像解析はモルフォロジカル演算子（構造要素（structuring element(SE)）とも呼ばれる）を画像に適用することによって行われる。異なるスケールのＳＥは気道又は血管セグメント化を実施する場合のステップの間のように使用される。スケルトン化方法は所与のオブジェクトの中央軸を計算するためのモルフォロジカル演算子の繰り返される適用に依存する。
【０００５】
構造要素を入力画像に適用するために、構造要素は入力画像に沿って移動され、演算が実施される。基本的なモルフォロジー演算はダイレーション（dilation）及びエロージョン（erosion）である。２値ダイレーションは、入力画像の各ピクセル／ボクセルに関する構造要素（フィルターカーネルとも呼ばれる）により定義される近傍の論理ＯＲを計算し、その値を演算子の中心に割り当てることによって実施される。２値エロージョンは入力画像の各ピクセル／ボクセルに関する構造要素により定義される近傍の論理ＡＮＤを計算することによって実施される。グレーレベル画像の場合には、論理ＯＲ／ＡＮＤはグレーレベルダイレーション／エロージョンを発生するためにＭＡＸ／ＭＩＮ演算子により置き換えられる。論理ＯＲ／ＡＮＤはＭＡＸ／ＭＩＮ演算子とともに比較演算子と総称される。
【０００６】
図１は３×３正方形構造要素１００が入力画像１０４に適用される事例を示す。実施される演算は２値ダイレーションであり、この２値ダイレーションは入力画像１０４の各ピクセルに関して構造要素１００により定義される近傍の論理ＯＲを計算することによって実施される。ダイレーションを実施するためには、ＳＥ１００の中央ピクセル１０８が入力画像１０４の各ピクセルに位置決めされ、ＯＲ演算子が非零である場合にＳＥ１００が入力画像ピクセルと代わる。異なった結果を出すためには、構造要素１００が入力画像１０４のどのピクセルをＯＲするかを特定する。よって、ダイレーション演算子は結果的に出力画像１１２を生じ、この出力画像１１２は入力画像１０４よりも多くの非零ピクセルを含む。シェードを付けられたピクセル１１６は演算の結果として加えられたピクセルを表し、他方で白いピクセル１１８はオリジナル入力画像１０４からのものである。画像１１２は「オフ（off）」であるピクセル１２０により取り囲まれており、これらの「オフ（off）」であるピクセル１２０はバイナリ値０を有し、画像の部分（すなわち、「オン（on）」であるピクセル）ではない。
【０００７】
図１はさらに同じ正方形ＳＥ１００が２値エロージョンにおいて同じ入力画像１０４に適用される事例を示す。前述のとおり、２値エロージョンは構造要素１００と入力画像１０４との間の論理ＡＮＤ演算を使用する。出力画像１２０は入力画像１０４に比べて「オン」ピクセルの数が少ない。この例では、残っているのはただ一つのピクセルである。というのも、入力画像の中には演算子がこの画像により包含されるたった１つの位置しかなく、このたった１つの位置がＡＮＤ演算に対して真値をもたらすからである。画像１２０はオフであるピクセル１２４（すなわちバイナリ値０を有する）によって囲まれている。
【０００８】
これらのモルフォロジー演算のダイレクトな適用は計算機的にはインテンシブである。とりわけ、コンピュータにより必要とされる計算時間はダイレクトに実施される計算機的演算の数及びタイプに比例し、これが今度はＳＥと画像サイズとの積に比例する。タイムリーなやり方で結果を得るためには、効率的なアルゴリズムが必要である。さもなければ、ＳＥ又は入力画像のサイズに制限されてしまう。
【０００９】
モルフォロジカル演算を実施するために使用されうる幾つかのアルゴリズムがある。最もシンプルなアプローチはブルートフォース（brute force）アルゴリズムである。ブルートフォースアルゴリズムはＳＥ内の全ピクセル／ボクセルをピクセル毎に計算して確かめる。結果は異なる画像へと格納される。ブルートフォースアルゴリズムの計算時間は構造要素の「デジタルマス（digital mass）」に依存する。デジタルマスは、２次元（すなわち２Ｄ）ジオメトリ（すなわちそのディスクリートエリア）のコンテキストにおける特定の範囲内のピクセルの数又は特定の３次元（すなわち３Ｄ）ジオメトリ（すなわちそのディスクリートボリューム）内のボクセルの数に関連する。よって、ブルートフォースアルゴリズムでは、各出力ピクセルは構造要素のデジタルマスマイナス１（中央ピクセル）に等しい演算の数を必要とする。特に、正方形構造要素１００が３ピクセルの長さ及び幅を有する場合には、この構造要素１００を使用して出力画像１１２、１２０の各ピクセルを得るために必要な（以下においてはｏｐｓと呼ぶ）演算の数は、正方形構造要素１００のエリアマイナス１（すなわち８ｏｐｓ）である。さらに、ますます多くの構造要素が異なる出力画像を得るために使用されるならば、計算時間量は指数関数的に増大する。例えば、正方形構造要素の直径（側面長）が線形に増大するにつれて、計算時間はその直径の二乗に比例して増大する。立方体の場合には、計算時間はこの立方体の側面長が線形に増大するにつれてその側面の三乗により増大する。
【００１０】
モルフォロジカル演算を実施するための別の技術は因数分解アルゴリズム（factorization algorithm）である（例えばhomotopic decomposition）。この因数分解アルゴリズムは「基本(fundamental)」構造要素を使用する。これらの基本構造要素はより大きな構造要素を「破壊する」ために使用される。従って、１つの大きなＳＥを画像に適用する代わりに、一連の基本ＳＥが使用される。最終結果は同一であるが、計算時間は低減される。なぜなら、より小さいＳＥのために必要な演算の数が単一の大きなＳＥのそれよりも小さいからである。例えば、構造要素が半径２の立方体であるとする。ブルートフォースアルゴリズムでは、５３−１＝１２４ｏｐｓが出力画像ボクセル毎に必要とされる。しかし、因数分解アルゴリズムを使用すれば、出力画像ボクセル毎に（３３−１）*２＝５２ｏｐｓが必要とされる。因数分解によって、計算費用はそのデジタルマスよりもむしろ考慮される構造要素を制限する立方体のディスクリートな直径に比例する。よって、因数分解アルゴリズムはブルートフォース技術において有意義な計算機的な節約を提供する。
【００１１】
しかし、因数分解アルゴリズムも大きな落とし穴を有する。近似なしでアルゴリズムが使用される比較的大きな構造要素の形状はシビアに使用される基本構造要素によって限定されてしまう。例えば、２次元デジタル化された円形構造要素又は３次元球形構造要素は人体（例えば気道）の構造のために医用画像処理を実施するためにしばしば使用される形状である。しかし、因数分解アルゴリズムは、大抵の場合、デジタル化された円又は球の形状に対して可能な基本構造要素の形状のために、過度な複雑性なしには円状又は球状構造要素には使用できない。従って、実際的な目的のためには、最良の可能な結果は円又は球の近似である。
【００１２】
結果的に、構造要素の形状に制約を課すことなしにモルフォロジカル演算子を実施する場合には、特に円及び球に対して、計算時間を低減する必要性がまだ残存している。
【特許文献１】U.S. Provisional Application No.60/637,653 filed December 20, 2004
【発明の開示】
【発明が解決しようとする課題】
【００１３】
画像へのモルフォロジカル演算を適用するための効率的な方法を提供することである。
【課題を解決するための手段】
【００１４】
上記課題は、反復的にモルフォロジカル演算を画像の焦点ピクセル及び画像の別のピクセルに適用し、この別のピクセルは焦点ピクセルに関してオフセットにあり、このオフセットは演算カウントに基づくことによって解決される。
【発明を実施するための最良の形態】
【００１５】
本発明は画像へのモルフォロジカル演算を適用するための効率的な方法である。２値及びグレースケールモルフォロジーの両方が多次元画像においてサポートされる。モルフォロジカル演算（例えばダイレーション又はエロージョン）は反復的に画像の焦点ピクセル及び焦点ピクセルに関してオフセットに配置された他のピクセルに適用される。このオフセットは演算カウントに基づき、この演算カウントはモルフォロジー演算が適用される毎に増大する。演算カウントは１から所定の演算回数まで増大する。最後の２回の演算を除く全て演算に対するオフセットは２Ｎ−１によって決定され、ここでNは演算カウントである。
【００１６】
必要とされる演算の数は画像に適用される構造要素の予め決定された長さの対数に基づく。とりわけ、必要とされる演算の数はlog２(Ｑ)のシーリング（ceiling）に等しく、ここでＱは特定の次元における構造要素の予め決定された長さである。全演算（比較）は最後の演算と除いて中央ピクセルに対して特定の方向に進み、最後の演算は逆方向に進む。最後の演算のオフセットはフロア（floor）（Ｑ／２）のネガティブである。最後から２番目の演算はシーリング（Ｑ／２）−２（Ｎ−２）のオフセットを有し、Nは演算カウントである。
【００１７】
１つの実施形態では、構造要素はさらに予め決定された幅及び／又は予め決定された高さを含む。いくつかの実施形態では、ピクセルはボクセルである。
【００１８】
本発明の方法は、凸状構造要素を使用する画像にモルフォロジカル演算を実施するための方法を含む。反復的に画像に凸状構造要素の最も外側の寸法に相応する寸法を有するワーク構造要素が適用される。付加的なワーキングキャンバス（画像）が中間計算のために使用される。以前のワーク構造要素によってはまだ被覆されていない凸状構造要素の残りの外側寸法に相応するようにワーク構造要素の寸法が調整される。この調整は常に大きくなり、以前の反復の結果が現在の反復において使用されることを許容する。適用及び調整ステップは、予め決定された数のモルフォロジカル演算が実施されるまで繰り返され、この結果、所与の凸状構造要素のモルフォロジー計算が得られる。
【００１９】
凸状構造要素は円形ディスク、球及び楕円であればよい。ワーク構造要素はさらに１次元構造要素又は長方形構造要素でもよい。それはダイアモンド形状又は対角線要素でもよい。計算の以前の数はさらにワーク構造要素の現在の長さ及び以前の長さの対数のシーリングを含む。
【００２０】
これらの及び他の本発明の利点は当業者には以下の詳細な記述及び添付図を参照すれば明らかである。
【実施例】
【００２１】
以下の記述は本発明を本発明の実施形態をインプリメントするために必要な処理ステップに関して記述する。これらのステップは適切にプログラムされたコンピュータにより実施され、このコンピュータのコンフィギュレーションは従来技術において公知である。適当なコンピュータは例えば周知のコンピュータプロセッサ、メモリユニット、ストレージデバイス、コンピュータソフトウェア及び他のコンポーネントを使用してインプリメントされる。このようなコンピュータのハイレベルブロック線図が図２には示されている。コンピュータ２０２はプロセッサ２０４を含み、このプロセッサ２０４はコンピュータプログラム命令を実行することによってコンピュータ２０２の演算全体をコントロールし、このコンピュータプログラム命令はこのような演算を定義する。コンピュータプログラム命令はストレージデバイス２１２（例えば磁気ディスク）に格納され、コンピュータプログラム命令の実行が所望される時にメモリ２１０にロードされる。コンピュータ２０２は１つ又は複数のインターフェース２０６を他のデバイスとの（例えばローカルに又はネットワークを介しての）通信のために含む。コンピュータ２０２はインプット／アウトプット２０８も含み、このインプット／アウトプット２０８はコンピュータ２０２とのユーザインタラクションを可能にするデバイスを表す（例えば、ディスプレイ、キーボード、マウス、スピーカ、ボタンなど）。当業者ならば、実際のコンピュータのインプリメンテーションが他のコンポーネントを含むこと及び図２は説明目的のためのこのようなコンピュータのコンポーネントのうちのいくつかのハイレベル表現であることを認めるだろう。さらに、当業者ならば、ここで記述される処理ステップは回路が特にこのような処理ステップをインプリメントするために構成されている特定用途ハードウェアを使用してインプリメントされうることを認めるだろう。代替的に、処理ステップはハードウェアとソフトウェアの様々なコンビネーションを使用してインプリメントされうる。
【００２２】
図３は１次元画像キャンバス３００のブロック線図を示し、関心ピクセル（すなわち焦点ピクセル）３０４をハイライトしてある。画像キャンバス３００は画像を含むピクセル（又はボクセル）のエリアである。焦点ピクセル３０４は最適化アルゴリズムとして後述される一連の演算によってどのように単一ピクセルが影響を受けるのかをより良く伝えるために使用される。もっとも、これらの演算は入力画像の全ピクセルに適用されるのだが。この例では、ブルートフォース方法の代わりに、一連の比較が画像キャンバス３００において各ステップでたった２つの画素の間で行われる。これはその特定のステップに対して２つの要素（ｓｐａｒｓｅ）ＳＥを有することに似ている。各適用事例は２つの画素の間の右オフセットを増大させることを含む：（これは論理ＯＲ、論理ＡＮＤ、ＭＡＸ又はＭＩＮのうちの１つでもよいが）行における各ピクセルのその右の隣との論理ＯＲ（すなわち各ピクセルを右側へとその隣によってダイレートすること）。最適化アルゴリズムは比較演算子の等冪性（idempotency property）を利用する（すなわち、要素に一回以上この演算子を実施するとこの演算子が一回適用された場合と同じ結果を発生する）。
【００２３】
コンピュータ２０２はこの最初の演算を現場で実施する（すなわち、焦点ピクセル３０４とその右の隣接ピクセルとの間のＯＲ演算の結果が焦点ピクセル３０４での出力である）。この最初のダイレーションは行３０８（すなわちno ops行）から行３０４（１ops 行）を生じる。各事例に対する下記の各演算がベクトル化されていることに注目してもらいたい。つまり、各演算は計算が継続するとともに焦点ピクセルを結果的に置換するのである。よって、最初の演算においては、キャンバス３００における各ピクセルはそれ自体とその直ぐ右側の隣接ピクセルとの間の論理ＯＲによって置換される。
【００２４】
結果的に、各ピクセルの出力はそれ自体と隣接ピクセルとの演算の結果である。これは以下において演算のスパン（the span of the operation）と呼ばれ、すなわちそのピクセルがピクセルに格納された情報の結果に寄与する。図３における焦点ピクセル３０４のスパンにはシェードが付けられている。１回の演算の後で、行３１２における焦点ピクセル３０４のスパンはそれ自体とその右側の隣接ピクセルである。
【００２５】
次に、論理ＯＲ演算が各ピクセルとその隣接ピクセルではなく右へと１つだけ越えたピクセルとの間で実施される。これは行３１２から行３１６への矢印により示されている。この結果、２つのＯＲ演算の後で、スパンは４ピクセルである。このスパンは４ピクセルである、なぜならこの論理ＯＲ演算は事実上焦点ピクセル３０４及びその右隣りならびに第３のピクセル及びその右隣りをカバーしているからである。
【００２６】
次の演算子は行３１６から行３２０へと示されているように、第４のピクセル３２４に実施される。焦点ピクセル３０４と第４のピクセル３２４との論理ＯＲによって、スパンは８ピクセルに増大する。特に、焦点ピクセル３０４がその３つの隣接ピクセルとの論理ＯＲの結果（すなわち４つのピクセル）であるように、第４のピクセル３２４はその３つの隣接ピクセルとの論理ＯＲの結果（すなわち４つのピクセル）である。画像に対して実施される３ｏｐｓの結果は、画像に対する８ピクセル幅ＳＥ計算と同じである。
【００２７】
出力ピクセル毎にＭ個のｏｐｓにおいてカバーされうる最大スパンは２Ｍである。この限定の逆は、Ｎ個の隣接するピクセルのモルフォロジカルな比較を実施するために必要とされる最小演算数Ｍｍｉｎが
Ｍｍｉｎ＝ＣＥＩＬ（log２(Ｎ)）
により定義されることである。
【００２８】
上記の最適化アルゴリズムをブルートフォース技術と比較すると、この最適化アルゴリズムは８個の論理ＯＲ演算（すなわち８ダイレーション）をたった３ｏｐｓで実施することに等価である。しかし、ブルートフォース技術は８個の論理ＯＲ演算を実施するために８ｏｐｓを必要とする。よって、この最適化アルゴリズムは有意義な計算節約を提供する。
【００２９】
特例として、下記のように左端のピクセル（太字）にセンターを有する１Ｄの４つのピクセル構造要素が同じく下記のような入力画像をダイレート（dilate）するために使用されると仮定しよう：
１１１１ 構造要素
０００００１０００００ 入力画像
ブルートフォースアプローチによれば、構造要素の中央ピクセルは入力画像の各ピクセルと整列され、次いで構造要素によって定められる入力画像の近傍がＯＲ演算される。この結果、出力画像
００１１１１０００００
が得られる。
【００３０】
入力画像に最適化アルゴリズムを使用すると、得られる結果は各演算毎に：
no ops ：０００００１０００００
1 op ：００００１１０００００
2 ops ：００１１１１０００００
となる。
【００３１】
図示されているように、最適化アルゴリズムは２回の演算の後でブルートフォースアルゴリズムと同一の結果を生じる。４ピクセル１次元構造要素に対して必要な演算の数は上記の式から決定される：２Ｎ＝４；Ｎ＝２ｏｐｓ。よって、２ｏｐｓが４ピクセル１次元構造要素を適用する場合に得られるのと同じ出力画像を得るために必要である。上記の説明では、１方向のｏｐｓだけが示されている。これは左側センターピクセルを有するＳＥだけを可能にする。同様に反対方向の単一ｏｐの使用は対称的な演算子を可能にする。
【００３２】
上記の原理に基づいて、長方形構造要素最適化アルゴリズムが画像への長方形構造要素の提供に使用されうる。図４は画像キャンバス４００に対して最適化アルゴリズムを使用する５×７長方形構造要素に対する２値ダイレーションのブロック線図を示す。焦点ピクセル４０４は関心ピクセルを表し、上記のように演算がベクトル化されている。
【００３３】
ステップ４５０はそれ自体とその右隣との間での論理ＯＲを表す焦点ピクセル４０４を示す。次に、ステップ４５４では、論理ＯＲが再び焦点ピクセル４０４とその右隣との間で実施される。これは（ステップ４５４に示されているように）（ベクトル化のために）焦点ピクセル４０４の右側に２ピクセルを含むスパンを増大させる。よって、焦点ピクセル４０４はステップ４５４においてシェードを付けられた２つのピクセルに関する情報を含む。ステップ４５８では、コンピュータ２０２は焦点ピクセル４０４に対する遠心ピクセル（distal pixel）の方向を逆転させ（すなわち、焦点ピクセルｘ［ｍ，ｎ］＝ｘ［ｍ，ｎ］｜ｘ［ｍ−２，ｎ］）、この結果、スパンが反対方向に拡張する。これは長方形構造要素の焦点ピクセル４０４に関してスパン対称性を維持することである。ステップ４５８の終了時には、各ピクセルは長さ５の１行であるスパンを有する。
【００３４】
ステップ４６２では、コンピュータ２０２は焦点ピクセル４０４とその直下のピクセルとの間の論理ＯＲを計算する。これは実際には５×２近傍に配置された１０個のオリジナルピクセル値の間の論理ＯＲである。コンピュータ２０２はステップ４６６及び４７０でステップ４５４及び４５８と同じやり方で最適化アルゴリズムをインプリメントしつづける。ただしここでは水平方向ではなく垂直方向にこのアルゴリズムが適用される。最終結果はステップ４７０に示されている。焦点ピクセル４０４は画像キャンバス４００との５×７長方形構造要素のダイレーション結果を表す。さらに、２Ｄ長方形構造要素に関して上では記述したが、上記の最適化アルゴリズムはさらに３次元長方形構造要素（例えば、５×５×７）に適用しうる。
【００３５】
以下においては２値ダイレーション演算子（すなわち論理ＯＲ）の適用を記述するが、最適化アルゴリズムはいかなる比較演算子をも使用できる。それゆえ、ＯＲ演算子はいかなる他のモルフォロジカル比較演算子（例えば、ＡＮＤ、ＭＩＮ又はＭＡＸ）によっても置換されうる。この能力はこの方法を２値領域とグレースケール領域の両方に適用することを可能にする。対角方向におけるこの方法の適用は、ダイアモンド形状の構造要素のモルフォロジー計算を可能にする。
【００３６】
図５は長方形又は立方体構造要素によるダイレーションのための最適化アルゴリズムのフローチャートを示す。このフローチャートは２Ｄケース及び３Ｄケースが両方とも１Ｄケースの拡張である（すなわち異なる軸に適用される）ように１Ｄケースにおける一般化を示す。それゆえ、図５は２値ピクセルの奇数長（Ｑ）ランの論理比較を効率的に得るための最適化アルゴリズムを示し、他方で最終結果における対称性を維持するようにしている。
【００３７】
Ｑ個のピクセルを比較するために必要とされる必要なｏｐｓの最小数（Ｎ）は最初にステップ５０４で決定される。この最小数は上記の式により与えられる：
Ｎｍｉｎ＝ＣＥＩＬ（log２(Ｑ)）
最終結果が対称的となるように、最後のｏｐ（すなわちＮ）を除く全てのｏｐｓ（すなわち、最初のＮ−１ｏｐｓ）はステップ５０８において（フォワード方向と呼ばれる）１方向へのスパンを増大させて拡張される。最後のｏｐはリバース方向へのスパンを増大させて拡張される。
【００３８】
焦点ピクセルに対する各ｏｐのオフセットを得ることが必要である。累積する論理ｏｐｓに対するＮ−１個のフォワードオフセットが存在するだろう。なぜなら、最後のｏｐはリバース方向にあるからである。最初のＮ−２ｏｐｓ（すなわち最後のフォワードｏｐを除く全て）は焦点ピクセルに関して２Ｐのオフセットで実行され、ただしここでP∈［０，１，２，・・・（Ｎ−２）−１］である。最後のフォワードオフセットはＣＥＩＬ（Ｑ／２）−２（Ｎ−２）である。
【００３９】
コンピュータ２０２は次いでステップ５１２でリバース方向にスパンを拡張する。コンピュータ２０２は最初に焦点ピクセルに関して最後のｏｐのためのオフセットを決定する。このオフセットは−ＦＬＯＯＲ（Ｑ／２）であり、このマイナス符号はオフセットがリバース方向であることを示すために使用される。
【００４０】
例えば、Ｎ＝２の場合には、たった一つのフォワードオフセット（Ｎ−１）しかない。これはＱ＝３の場合に生じる（すなわち、焦点ピクセル、焦点ピクセルの右に１ピクセル及び焦点ピクセルの左に１ピクセルが構造要素を構成する）。
【００４１】
上記でも下記でも２値ダイレーション演算子を適用することが記述される（例えば論理ＯＲ）が、最適化アルゴリズムはいかなる比較演算子をも使用できる。それゆえ、ＯＲ演算子は同じくいかなる他のモルフォロジカル比較演算子（例えば、ＡＮＤ、ＭＩＮ又はＭＡＸ）によっても置換されうる。さらに、ステップ５０４〜５１２は残りの軸において繰り返される。
【００４２】
図６Ａ〜６Ｃはブルートフォースアルゴリズム、因数分解アルゴリズム及び最適化アルゴリズムを立方体構造要素に対して使用してその半径が１〜１０まで増大する時の様子を時間に対してタイムプロットしたものを示す。
【００４３】
図６Ａは立方体構造要素の半径が増加するにつれてブルートフォースアルゴリズムにおいて計算消費が指数関数的に増大することを示す。よって、立方体構造要素の半径が６である時、曲線６０２はブルートフォースアルゴリズムを使用する構造要素を適用するために必要な時間がほぼ２０００ユニット（例えば秒）であることを示す。他の２つの方法により必要とされるタイミングはブルートフォース方法の時間を示すために必要な高さのためにほとんど見えない。
【００４４】
図６Ｂは立方体構造要素の半径が増加するにつれて因数分解アルゴリズムにおいて計算消費が線形に増大することを示す曲線６０４を示している。立方体構造要素の半径が６である時、曲線６０４は因数分解アルゴリズムを使用する構造要素を適用するために必要な時間がほぼ１５０ユニット（例えば秒）であることを示す。タイムスケールはブルートフォースアルゴリズムの場合の０〜１００００から因数分解アルゴリズムの場合の０〜３００にまで低減されている。提案される本発明の方法の時間はここでもほとんど見えない。
【００４５】
図６Ｃは上記のような最適化アルゴリズムの場合の計算消費が立方体構造要素の半径のｌｏｇに比例することを示す曲線６０８を示している。立方体構造要素の半径が６である時、曲線６０８は構造要素を適用するために必要な時間がほぼ１２ユニット（例えば秒）であることを示す。タイムスケールは因数分解アルゴリズムの場合の０〜３００から最適化アルゴリズムの場合の６〜１６にまで低減されている。
【００４６】
最適化アルゴリズムは２Ｄ円形（又は楕円）又は３Ｄ球体（又は楕円体）のようなデジタル的に凸状（convex）構造要素にも適用されうる。ここでは凸性（convexity）とは、デジタル的に凸状の構造（２Ｄ）におけるいかなるピクセルの中心点からも同一構造のいかなる他のピクセルの中心点へとラインを描くことが可能であること及びラインが完全にこの構造体の内部に存在しければならないか又はもしラインがこの構造の外側に出てしまってもそのラインセグメントにより制限されるエリア及びこのラインセグメントと共通の開始点及び終了点を共有するデジタル構造の境界セグメントがこの構造の部分ではないいかなるピクセルの中心点をも含まないことを意味する。
【００４７】
１つの実施形態では、円状構造要素を適用するために、２つの画像キャンバスが最適化アルゴリズムを使用してモルフォロジー結果を達成するために必要とされる。コンピュータ２０２は最適化アルゴリズムを反復的に実施し、この場合、各反復がスパン拡張ステップ及びピックアップ／比較ステップを含む。各反復においてコンピュータ２０２は残ってアドレス指定される構造要素を「チップアウェイ（chips away）」する。
【００４８】
構造要素はトップダウンで検査される。すなわち、ユニークな長さを有するその最も外側の行／列が考察されなければならない。凸性によって、生じる各々新しい行／列長さが以前のものよりも長くなるだろう。こうして、ワークキャンバスの各ピクセルにおいて比較が行われるところの近傍のスパンが拡張される。これによって以前の反復によって既に利用可能な計算に基づいて形成することが可能となる。これらの中間結果のシステマティックな合成は所望のモルフォロジー結果をもたらす。構造要素の分解はアルゴリズム（トップダウン）に対する"divide and conquer"アプローチである。なぜなら、それはダイナミックプログラミング（ボトムアップ）に類似したフレームワーク内でモルフォロジーをインプリメントするためのステージを設定するからである。よって、隣接出力ピクセルにおけるオリジナルキャンバスの比較の空間的オーバーラップが利用される。
【００４９】
図７は｛５，９，１１，１３，１５，１７｝の行長さ及び｛１，５，９，１１，１３，１５｝の列長さを有する凸状構造要素（２Ｄデジタル化された円）７００の例を示す。この構造要素７００は上記の因数分解アルゴリズムには向いていない。２つの画像キャンバスが各反復において更新され、ここで暫定ワークキャンバスＷは最初に更新され、長方形スパン拡張を反映する（パート１）。これに続いて、出力画像キャンバスＯ自体と更新されたＷとの間でのベクトル化された比較により出力画像キャンバスＯを更新する（パート２）。１つの実施形態では、入力画像キャンバスがＯのために使用される。代替的に、別個の画像キャンバスが使用される。
【００５０】
図８Ａ及び８Ｂは２つの図７に示された２Ｄ円形構造要素を画像に適用する最適化アルゴリズムにおける２つの画像キャンバス８０４、８０８を示す。中間キャンバスＷ８０４はオリジナル画像及びそれ自体における計算からの結果を含む。最終出力画像Ｏ８０８はＷとそれ自体との間で行われた演算を含む。このアプリケーションは３回の反復で完了する。第１の部分８０４の３回の反復では、もし適切な構造要素によりダイレートされるならば、残っている構造要素（ＲＳＥ）を完全にカバーするために使用されうるようにＷの長方形ダイレーションフットプリントが最も大きい長方形に増大される。第２の部分８０８の３回の反復では、ＷがシステマティックにＯと比較される。Ｗの長方形ダイレーションフットプリントはＲＳＥと相関するようにオフセットされる。よって、Ｏ内の各ピクセルは、ＲＳＥの最も外側のユニークな行及び列がチップアウェイされうるようにそれ自体と相応の位置からオフセットされるＷ値との比較により更新される。
【００５１】
とりわけ、コンピュータ２０２は最初に５ピクセルの行である構造要素を使用してＷに対する適切な（in place）ダイレーションを実施し、次いでその結果を横切って、反復１におけるＯを形成する。この結果、Ｗ内の４ピクセルがＯ内の単一中央ピクセルへと結合され、これはｓｐａｒｓｅ４ピクセルＳＥを適用することに似ている。これは本質的に残ってアドレス指定される構造要素を「チップアウェイ」する。更新されたＲＳＥは今や（図７に示されたような）オリジナルの構造要素に関して除去されたトップ及びボトム行及び最も左の及び最も右のピクセルを有する。
【００５２】
反復２では、Ｗは９×５長方形構造要素を有するオリジナル画像のダイレーション結果を含むことを要求される。といのも、それらはＲＳＥの最も外側の行／列長さ（すなわち、先のステップで構造要素によりカバーされなかった最も外側の寸法）であるからである。反復１の結果、Ｗは既に５×１長方形構造要素を有するダイレーション結果を含んでいる。それゆえ、コンピュータ２０２は５×１長方形ダイレーションフットプリントが９×５長方形ダイレーションフットプリントに拡張されるようにＷを更新する必要がある。注意すべきは、このステップが反復１からのデータを再利用することであり、これによりこのステップはスクラッチから９×５ＳＥを計算するよりも計算的により効率的なものにする。次いで、Ｗ内のピクセルはストラテジー的にＯ内のピクセルと比較される。反復２の終了時にＯの各ピクセルに反映されるダイレーションフットポイントが示されている。
【００５３】
反復３において、コンピュータ２０２はＷ内のダイレーション結果を１３×９（これは更新されたＲＳＥの最も外側の行／列長さである）となるように拡張し、所望の結果を得るためにＯとのピッキング／比較の最終ラウンドを行う。いかなる凸状のＸ−Ｙ対称構造要素に対してもここで概略を述べたアルゴリズムを実施するために必要とされるパラメータは反復の回数、各反復毎のＷの内の長方形スパンにおける増大（すなわち、第１の部分８０４）及びＯ焦点位置に関してＷ要素をセレクトするためのオフセット（第２の部分８０８）である。Ｗにおいて必要とされるパディング（すなわち、構造要素の調整（例えば拡張））は前述の式よりもより一般的な式による。この一般的な式は
Ｎｍｉｎ＝ＣＥＩＬ（log２(Ｌｎｏｗ／Ｌｐｒｅｖ)）
である。
【００５４】
よって、必要とされるモルフォロジカル演算の最小回数は長方形構造要素の現在の長さ及び以前の長さに依存している。
【００５５】
さらに、２Ｄ円状構造要素に対する上記の最適化アルゴリズムは３Ｄ球状構造要素にも適用される。３Ｄ球の場合には、６以上のボクセル演算子が使用されることになる。凸状構造要素の別の例は楕円である。
【００５６】
図９は変化する直径を有する１０個の円形構造要素を使用する５１２×５１２×５０閾値ＣＴサブイメージの２値ダイレーションのための実行時間の線図９００を示す。線図９００は従来技術の（例えばＭＡＴＬＡＢツールボックス）アルゴリズムを使用する場合にディスクリートな円形構造要素の半径が増大する時の計算時間の増大を示すプロット９０４を示している。プロット９０８は上記の最適化アルゴリズムを使用する場合に円形構造要素の半径が増大する時の計算時間の増大を示す。従来技術において達成される最大実行時間はほぼ１１００秒であり、他方で線図９００では最適化アルゴリズムにおいて達成される最大実行時間はほぼ２００秒である。
【００５７】
上記の詳細な記述はあらゆる観点から説明的及び例示的なものであり、限定的なものではないと理解してほしい。さらに、ここで開示された本発明の範囲はこの詳細な記述から決定されるべきではなく、むしろ特許法により許可される最大外延に従って解釈されるように請求項から決定されるべきである。ここに示され上述された実施例は単に本発明の原理の例証となるものであり、様々な修正が本発明の範囲及び精神から離れることなく当業者によりインプリメントされうることを理解してほしい。当業者は本発明の範囲及び精神から離れることなく様々な他のフィーチャ組み合わせをインプリメントできるはずである。
【図面の簡単な説明】
【００５８】
【図１】３×３正方形構造要素による入力画像の２値ダイレーション及びエロージョンの従来技術のブロック線図を示す。
【図２】本発明の実施例によるコンピュータのハイレベルブロック線図である。
【図３】本発明の実施例による１次元（１Ｄ）行における最適化されたモルフォロジーアルゴリズムのブロック線図である。
【図４】本発明の実施例による最適化アルゴリズムを使用する５×７長方形構造要素における２値ダイレーションのブロック線図である。
【図５】本発明の実施例による長方形又は立方体構造要素による画像のダイレーションのための最適化アルゴリズムのフローチャートである。
【図６】図６Ａ〜６Ｃは本発明の実施例による立方体構造要素の半径が１〜１０まで増大する時のブルートフォースアルゴリズム、因数分解アルゴリズム及び最適化アルゴリズムを使用する際に必要とされる時間のプロットを示す。
【図７】本発明の実施例による２Ｄ凸状構造要素の例を示す。
【図８】図８Ａ及び８Ｂは本発明の実施例による画像への楕円状構造要素の適用のための最適化アルゴリズムの適用事例のブロック線図である。
【図９】本発明の実施例とブルートフォースインプリメンテーションによる変化する直径を有する１０個の円状構造要素を使用する５１２×５１２×５０閾値ＣＴサブイメージの２値ダイレーションのための実行時間を比較する線図を示す。
【符号の説明】
【００５９】
１００ 正方形構造要素
１０４ 入力画像
１０８ 中央ピクセル
１１２ 出力画像
１１６ シェードを付けられたピクセル
１１８ 白いピクセル
１２０ 「オフ」であるピクセル
２０２ コンピュータ
２０４ プロセッサ
２０６ インターフェース
２０８ Ｉ／Ｏ
２１０ メモリ
２１２ ストレージ
３００ １次元画像キャンバス
３０４ 関心ピクセル（焦点ピクセル）
３０８ 行
３１２ 行
３１６ 行
３２０ 行
３２４ 第４のピクセル
４００ 画像キャンバス
４０４ 焦点ピクセル
６０２ ブルートフォースアルゴリズムの際の計算消費曲線
６０４ 因数分解アルゴリズムの際の計算消費曲線
６０８ 最適化アルゴリズムの際の計算消費曲線
７００ 凸状構造要素
８０４ 第１の部分、中間キャンバスＷ
８０８ 第２の部分、最終出力画像Ｏ
ＲＳＥ 残っている構造要素（the remaining structuring element）
ＳＥ 構造要素（structuring element）
９００ 変化する直径を有する１０個の円形構造要素を使用する５１２×５１２×５０閾値ＣＴサブイメージの２値ダイレーションのための実行時間の線図
９０４ 従来技術の（例えばＭＡＴＬＡＢツールボックス）アルゴリズムを使用する場合にディスクリートな円形構造要素の半径が増大する時の計算時間の増大を示すプロット
９０８ 本発明の最適化アルゴリズムを使用する場合に円形構造要素の半径が増大する時の計算時間の増大を示すプロット
【特許請求の範囲】
【請求項１】
画像にモルフォロジカル演算を適用するための方法において、該方法は、
反復的にモルフォロジカル演算を画像の焦点ピクセル及び前記画像の別のピクセルに適用し、該別のピクセルは前記焦点ピクセルに関してオフセットにあり、該オフセットは演算カウントに基づくことを有する、画像にモルフォロジカル演算を適用するための方法。
【請求項２】
演算カウントはモルフォロジカル演算が適用された回数である、請求項１記載の方法。
【請求項３】
演算カウントは１から画像にモルフォロジカル演算を適用しなければならない演算の数まで増大する、請求項１記載の方法。
【請求項４】
オフセットは２Ｎ−１によって決定され、ここでNは演算カウントである、請求項１記載の方法。
【請求項５】
さらに、必要とされる演算の数を決定することを有する、請求項３記載の方法。
【請求項６】
必要とされる演算の数は構造要素の予め決定された長さに依存する、請求項５記載の方法。
【請求項７】
演算の数は予め決定された長さの対数に基づく、請求項６記載の方法。
【請求項８】
演算の数はシーリング（log２(Ｑ)）に等しく、ここでＱは構造要素の予め決定された長さである、請求項７記載の方法。
【請求項９】
演算の数の最後の演算は少なくともいくつかの他の演算に対して逆方向に進む、請求項８記載の方法。
【請求項１０】
最後の演算のオフセットはフロア（Ｑ／２）のネガティブであり、ここでＱは構造要素の予め決定された長さである、請求項６記載の方法。
【請求項１１】
最後から２番目の演算はシーリング（Ｑ／２）−２（Ｎ−２）のオフセットを有し、ここでＱは構造要素の予め決定された長さであり、Nは演算カウントである、請求項６記載の方法。
【請求項１２】
ピクセルはボクセルである、請求項１記載の方法。
【請求項１３】
構造要素はさらに予め決定された幅を有する、請求項６記載の方法。
【請求項１４】
構造要素はさらに予め決定された高さを有する、請求項６記載の方法。
【請求項１５】
凸状構造要素を使用する画像にモルフォロジカル演算を実施するための方法において、該方法は、
反復的に画像に凸状構造要素の最も外側の寸法に相応する寸法を有するワーク構造要素を適用し、
以前のワーク構造要素によってはまだ被覆されていない凸状構造要素の残りの外側寸法に相応するようにワーク構造要素の寸法を調整し、
予め決定された数のモルフォロジカル演算が実施されるまで適用及び調整を繰り返すことを有する、凸状構造要素を使用する画像にモルフォロジカル演算を実施するための方法。
【請求項１６】
凸状構造要素は円、球及び楕円のうちの少なくとも１つを有する、請求項１５記載の方法。
【請求項１７】
ワーク構造要素はさらに１次元構造要素を有する、請求項１５記載の方法。
【請求項１８】
ワーク構造要素はさらに長方形構造要素を有する、請求項１５記載の方法。
【請求項１９】
モルフォロジカル演算の予め決定された数はさらに構造要素の現在の長さ及び以前の長さの対数のシーリングを有する、請求項１５記載の方法。
【請求項２０】
ワーク構造要素の寸法の調整はワークキャンバス上で行われる、請求項１５記載の方法。
【請求項２１】
画像へのワーク構造要素の適用は画像の少なくとも１つの焦点ピクセル及び前記画像の少なくとも１つの他のピクセルにモルフォロジカル演算を適用することによって行われる、請求項１５記載の方法。
【請求項２２】
画像の焦点ピクセル及び前記画像の少なくとも１つの他のピクセルはさらに少なくとも１つのボクセルを含む、請求項２１記載の方法。
【請求項２３】
凸状構造要素を使用する画像へのモルフォロジカル演算を実施するためのシステムにおいて、該システムは、
反復的に画像に凸状構造要素の最も外側の寸法に相応する寸法を有する構造要素を適用するための手段と、
以前のワーク構造要素によってはまだ被覆されていない凸状構造要素の残りの外側寸法に相応するように構造要素の寸法を調整するための手段と、
予め決定された数のモルフォロジカル演算が実施されるまで適用及び調整を繰り返すための手段を有する、凸状構造要素を使用する画像へのモルフォロジカル演算を実施するためのシステム。
【請求項２４】
凸状構造要素は円、球及び楕円のうちの少なくとも１つを有する、請求項２３記載のシステム。
【請求項２５】
ワーク構造要素はさらに１次元構造要素を有する、請求項２３記載のシステム。
【請求項２６】
ワーク構造要素はさらに長方形構造要素を有する、請求項２３記載のシステム。
【請求項２７】
モルフォロジカル演算の予め決定された数はさらに構造要素の現在の長さ及び以前の長さの対数のシーリングを有する、請求項２３記載のシステム。
【請求項２８】
ワーク構造要素の寸法の調整はワークキャンバス上で行われる、請求項２３記載のシステム。
【請求項２９】
画像へのワーク構造要素の適用は画像の少なくとも１つの焦点ピクセル及び前記画像の少なくとも１つの他のピクセルにモルフォロジカル演算を適用することによって行われる、請求項２３記載のシステム。
【請求項３０】
画像の焦点ピクセル及び前記画像の少なくとも１つの他のピクセルはさらに少なくとも１つのボクセルを含む、請求項２９記載のシステム。
【請求項３１】
画像にモルフォロジカル演算を適用するためのシステムにおいて、該システムは、
反復的にモルフォロジカル演算を画像の焦点ピクセル及び前記画像の別のピクセルに適用するための手段を有し、該別のピクセルは前記焦点ピクセルに関してオフセットにあり、該オフセットは演算カウントに基づく、画像にモルフォロジカル演算を適用するためのシステム。
【請求項３２】
演算カウントはモルフォロジカル演算が適用された回数である、請求項３１記載のシステム。
【請求項３３】
演算カウントは１から画像にモルフォロジカル演算を適用しなければならない演算の数まで増大する、請求項３１記載のシステム。
【請求項３４】
オフセットは２Ｎ−１によって決定され、ここでNは演算カウントである、請求項３１記載のシステム。
【請求項３５】
さらに、必要とされる演算の数を決定するための手段を有する、請求項３３記載のシステム。
【請求項３６】
必要とされる演算の数は構造要素の予め決定された長さに依存する、請求項３５記載のシステム。
【請求項３７】
演算の数は予め決定された長さの対数に基づく、請求項３６記載のシステム。
【請求項３８】
演算の数はシーリング（log２(Ｑ)）に等しく、ここでＱは構造要素の予め決定された長さである、請求項３７記載のシステム。
【請求項３９】
演算の数の最後の演算は少なくともいくつかの他の演算に対して逆方向に進む、請求項３８記載のシステム。
【請求項４０】
最後の演算のオフセットはフロア（Ｑ／２）のネガティブであり、ここでＱは構造要素の予め決定された長さである、請求３９記載のシステム。
【請求項４１】
最後から２番目の演算はシーリング（Ｑ／２）−２（Ｎ−２）のオフセットを有し、ここでＱは構造要素の予め決定された長さであり、Nは演算カウントである、請求項３９記載のシステム。
【請求項４２】
ピクセルはボクセルである、請求項３１記載のシステム。
【請求項４３】
構造要素はさらに予め決定された幅を有する、請求項３６記載のシステム。
【請求項４４】
構造要素はさらに予め決定された高さを有する、請求項３６記載のシステム。
【請求項１】
画像にモルフォロジカル演算を適用するための方法において、該方法は、
反復的にモルフォロジカル演算を画像の焦点ピクセル及び前記画像の別のピクセルに適用し、該別のピクセルは前記焦点ピクセルに関してオフセットにあり、該オフセットは演算カウントに基づくことを有する、画像にモルフォロジカル演算を適用するための方法。
【請求項２】
演算カウントはモルフォロジカル演算が適用された回数である、請求項１記載の方法。
【請求項３】
演算カウントは１から画像にモルフォロジカル演算を適用しなければならない演算の数まで増大する、請求項１記載の方法。
【請求項４】
オフセットは２Ｎ−１によって決定され、ここでNは演算カウントである、請求項１記載の方法。
【請求項５】
さらに、必要とされる演算の数を決定することを有する、請求項３記載の方法。
【請求項６】
必要とされる演算の数は構造要素の予め決定された長さに依存する、請求項５記載の方法。
【請求項７】
演算の数は予め決定された長さの対数に基づく、請求項６記載の方法。
【請求項８】
演算の数はシーリング（log２(Ｑ)）に等しく、ここでＱは構造要素の予め決定された長さである、請求項７記載の方法。
【請求項９】
演算の数の最後の演算は少なくともいくつかの他の演算に対して逆方向に進む、請求項８記載の方法。
【請求項１０】
最後の演算のオフセットはフロア（Ｑ／２）のネガティブであり、ここでＱは構造要素の予め決定された長さである、請求項６記載の方法。
【請求項１１】
最後から２番目の演算はシーリング（Ｑ／２）−２（Ｎ−２）のオフセットを有し、ここでＱは構造要素の予め決定された長さであり、Nは演算カウントである、請求項６記載の方法。
【請求項１２】
ピクセルはボクセルである、請求項１記載の方法。
【請求項１３】
構造要素はさらに予め決定された幅を有する、請求項６記載の方法。
【請求項１４】
構造要素はさらに予め決定された高さを有する、請求項６記載の方法。
【請求項１５】
凸状構造要素を使用する画像にモルフォロジカル演算を実施するための方法において、該方法は、
反復的に画像に凸状構造要素の最も外側の寸法に相応する寸法を有するワーク構造要素を適用し、
以前のワーク構造要素によってはまだ被覆されていない凸状構造要素の残りの外側寸法に相応するようにワーク構造要素の寸法を調整し、
予め決定された数のモルフォロジカル演算が実施されるまで適用及び調整を繰り返すことを有する、凸状構造要素を使用する画像にモルフォロジカル演算を実施するための方法。
【請求項１６】
凸状構造要素は円、球及び楕円のうちの少なくとも１つを有する、請求項１５記載の方法。
【請求項１７】
ワーク構造要素はさらに１次元構造要素を有する、請求項１５記載の方法。
【請求項１８】
ワーク構造要素はさらに長方形構造要素を有する、請求項１５記載の方法。
【請求項１９】
モルフォロジカル演算の予め決定された数はさらに構造要素の現在の長さ及び以前の長さの対数のシーリングを有する、請求項１５記載の方法。
【請求項２０】
ワーク構造要素の寸法の調整はワークキャンバス上で行われる、請求項１５記載の方法。
【請求項２１】
画像へのワーク構造要素の適用は画像の少なくとも１つの焦点ピクセル及び前記画像の少なくとも１つの他のピクセルにモルフォロジカル演算を適用することによって行われる、請求項１５記載の方法。
【請求項２２】
画像の焦点ピクセル及び前記画像の少なくとも１つの他のピクセルはさらに少なくとも１つのボクセルを含む、請求項２１記載の方法。
【請求項２３】
凸状構造要素を使用する画像へのモルフォロジカル演算を実施するためのシステムにおいて、該システムは、
反復的に画像に凸状構造要素の最も外側の寸法に相応する寸法を有する構造要素を適用するための手段と、
以前のワーク構造要素によってはまだ被覆されていない凸状構造要素の残りの外側寸法に相応するように構造要素の寸法を調整するための手段と、
予め決定された数のモルフォロジカル演算が実施されるまで適用及び調整を繰り返すための手段を有する、凸状構造要素を使用する画像へのモルフォロジカル演算を実施するためのシステム。
【請求項２４】
凸状構造要素は円、球及び楕円のうちの少なくとも１つを有する、請求項２３記載のシステム。
【請求項２５】
ワーク構造要素はさらに１次元構造要素を有する、請求項２３記載のシステム。
【請求項２６】
ワーク構造要素はさらに長方形構造要素を有する、請求項２３記載のシステム。
【請求項２７】
モルフォロジカル演算の予め決定された数はさらに構造要素の現在の長さ及び以前の長さの対数のシーリングを有する、請求項２３記載のシステム。
【請求項２８】
ワーク構造要素の寸法の調整はワークキャンバス上で行われる、請求項２３記載のシステム。
【請求項２９】
画像へのワーク構造要素の適用は画像の少なくとも１つの焦点ピクセル及び前記画像の少なくとも１つの他のピクセルにモルフォロジカル演算を適用することによって行われる、請求項２３記載のシステム。
【請求項３０】
画像の焦点ピクセル及び前記画像の少なくとも１つの他のピクセルはさらに少なくとも１つのボクセルを含む、請求項２９記載のシステム。
【請求項３１】
画像にモルフォロジカル演算を適用するためのシステムにおいて、該システムは、
反復的にモルフォロジカル演算を画像の焦点ピクセル及び前記画像の別のピクセルに適用するための手段を有し、該別のピクセルは前記焦点ピクセルに関してオフセットにあり、該オフセットは演算カウントに基づく、画像にモルフォロジカル演算を適用するためのシステム。
【請求項３２】
演算カウントはモルフォロジカル演算が適用された回数である、請求項３１記載のシステム。
【請求項３３】
演算カウントは１から画像にモルフォロジカル演算を適用しなければならない演算の数まで増大する、請求項３１記載のシステム。
【請求項３４】
オフセットは２Ｎ−１によって決定され、ここでNは演算カウントである、請求項３１記載のシステム。
【請求項３５】
さらに、必要とされる演算の数を決定するための手段を有する、請求項３３記載のシステム。
【請求項３６】
必要とされる演算の数は構造要素の予め決定された長さに依存する、請求項３５記載のシステム。
【請求項３７】
演算の数は予め決定された長さの対数に基づく、請求項３６記載のシステム。
【請求項３８】
演算の数はシーリング（log２(Ｑ)）に等しく、ここでＱは構造要素の予め決定された長さである、請求項３７記載のシステム。
【請求項３９】
演算の数の最後の演算は少なくともいくつかの他の演算に対して逆方向に進む、請求項３８記載のシステム。
【請求項４０】
最後の演算のオフセットはフロア（Ｑ／２）のネガティブであり、ここでＱは構造要素の予め決定された長さである、請求３９記載のシステム。
【請求項４１】
最後から２番目の演算はシーリング（Ｑ／２）−２（Ｎ−２）のオフセットを有し、ここでＱは構造要素の予め決定された長さであり、Nは演算カウントである、請求項３９記載のシステム。
【請求項４２】
ピクセルはボクセルである、請求項３１記載のシステム。
【請求項４３】
構造要素はさらに予め決定された幅を有する、請求項３６記載のシステム。
【請求項４４】
構造要素はさらに予め決定された高さを有する、請求項３６記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００６−１７８９８８（Ｐ２００６−１７８９８８Ａ）
【公開日】平成１８年７月６日（２００６．７．６）
【国際特許分類】
【外国語出願】
【出願番号】特願２００５−３６６５９７（Ｐ２００５−３６６５９７）
【出願日】平成１７年１２月２０日（２００５．１２．２０）
【出願人】（５９３０７８００６）シーメンス コーポレイト リサーチ インコーポレイテツド (47)
【氏名又は名称原語表記】Ｓｉｅｍｅｎｓ Ｃｏｒｐｏｒａｔｅ Ｒｅｓｅａｒｃｈ，Ｉｎｃ．
【住所又は居所原語表記】７５５ Ｃｏｌｌｅｇｅ Ｒｏａｄ Ｅａｓｔ，Ｐｒｉｎｃｅｔｏｎ， ＮＪ ０８５４０，Ｕｎｉｔｅｄ Ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ
【Ｆターム（参考）】
【公開日】平成１８年７月６日（２００６．７．６）
【国際特許分類】
【出願番号】特願２００５−３６６５９７（Ｐ２００５−３６６５９７）
【出願日】平成１７年１２月２０日（２００５．１２．２０）
【出願人】（５９３０７８００６）シーメンス コーポレイト リサーチ インコーポレイテツド (47)
【氏名又は名称原語表記】Ｓｉｅｍｅｎｓ Ｃｏｒｐｏｒａｔｅ Ｒｅｓｅａｒｃｈ，Ｉｎｃ．
【住所又は居所原語表記】７５５ Ｃｏｌｌｅｇｅ Ｒｏａｄ Ｅａｓｔ，Ｐｒｉｎｃｅｔｏｎ， ＮＪ ０８５４０，Ｕｎｉｔｅｄ Ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ
【Ｆターム（参考）】
[ Back to top ]