(57)【要約】【課題】周辺環境に強く、少ない両眼差ノイズを有する映像整合方法を提供するために、単一スキャンライン以上の多様なスキャンラインをステレオマッチングに用いる信頼性伝播アルゴリズムの原理を基本的に用い、これを高速化し、チップの開発を容易にするために、従来の順次的ソフトウェアアルゴリズムとは異なる新たな並列パイプライン構造のアルゴリズムを提供することにある。【解決手段】本発明の並列ＶＬＳＩ計算構造又はアルゴリズムを用いるメッセージ伝達基盤ステレオ映像整合システムは、第１及び第２映像取得手段から入力される映像をデジタル信号に変換して第１及び第２ピクセルデータを出力する映像処理部と、同一エピポーラ線上の前記第１及び第２ピクセルデータのデータ値を用いて各ピクセルの上方、下方、前方、後方メッセージのうち少なくとも２つ以上のメッセージを計算し、隣接するピクセルに対応する計算されたメッセージを用いて各ピクセルの両眼差値を計算する映像整合部とを含む。【選択図】      図２
2010509670.tif 000002
【特許請求の範囲】
【請求項１】
第１及び第２映像取得手段から入力される映像をデジタル信号に変換して第１及び第２ピクセルデータを出力する映像処理部と、
同一エピポーラ線上の前記第１及び第２ピクセルデータのデータ値を用いて各ピクセルの上方、下方、前方、後方メッセージのうち少なくとも２つ以上のメッセージを計算し、隣接するピクセルに対応する計算されたメッセージを用いて各ピクセルの両眼差値を計算する映像整合部と
を含む並列ＶＬＳＩ計算構造又はアルゴリズムを用いるメッセージ伝達基盤ステレオ映像整合システム。
【請求項２】
前記映像整合部は、
前記左右映像ピクセルデータを格納するスキャンラインバッファと、
前記左右映像ピクセルデータを受けて前方メッセージを計算する前方プロセッサと、前記前方プロセッサにより計算された前方メッセージを格納するスタックと、
前記左右映像ピクセルデータを受けて後方メッセージを計算する後方プロセッサと、
前記左右映像ピクセルデータと前記スタックに格納された前方メッセージ及び後方メッセージを受けて前記両眼差値を計算する両眼差計算プロセッサと
を含むことを特徴とする請求項１に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項３】
前記映像整合部による映像整合は全てのラインに対して行われ、各ラインで一方の水平方向に前記前方メッセージが計算され、計算された前記前方メッセージが前記スタックに格納される前方処理が完了した後に、前記ラインで他方の水平方向に前記後方メッセージ値を計算し、前記両眼差値を計算する後方処理が行われることを特徴とする請求項２に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項４】
前記映像整合部は、
前記左右映像ピクセルデータを格納するスキャンラインバッファと、
前記左右映像ピクセルデータ及び隣接した上ラインに対応する下方メッセージを受けて前方メッセージを計算する前方プロセッサと、
前記前方プロセッサにより計算された前方メッセージ値を格納するスタックと、
前記左右映像ピクセルデータ及び前記隣接した上ラインに対応する下方メッセージを受けて後方メッセージを計算する後方プロセッサと、
前記左右映像ピクセルデータと前記スタックに格納された前方メッセージ及び前記後方メッセージを受けて両眼差値を計算する両眼差計算プロセッサと
を含むことを特徴とする請求項１に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項５】
前記映像整合部による映像整合は前記隣接した上ラインに対して前記下方メッセージを計算し、その後に前記計算された下方メッセージを用いて前記前方及び後方メッセージを計算し、前記両眼差値を計算し、現在のラインの前記下方メッセージを計算して隣接した下ラインで用いるようにすることを特徴とする請求項４に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項６】
前記前方処理時に前記前方プロセッサが動作し、前記後方処理時に前記後方及び下方プロセッサと前記両眼差計算プロセッサが動作することを特徴とする請求項４に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項７】
前記映像整合部は、
前記左右映像ピクセルデータを格納するスキャンラインバッファと、
前記左右映像ピクセルデータ及び以前反復ループで計算された隣接した下ラインに対応する隣接した上方メッセージ、前記以前反復ループで計算された隣接した上ラインに対応する隣接した下方メッセージを受けて前方メッセージを計算する前方プロセッサと、
前記前方プロセッサにより計算された前方メッセージを格納するスタックと、
前記スキャンラインバッファから受けた前記左右映像ピクセルデータ及び前記以前反復ループで計算された前記隣接した下ラインに対応する前記隣接した上方メッセージ、前記以前反復ループで計算された前記隣接した上ラインに対応する前記隣接した下方メッセージを受けて後方メッセージを計算する後方プロセッサと、
前記スキャンラインバッファから受けた前記左右映像ピクセルデータ値と前記以前反復ループで計算された前記隣接した下ラインに対応する前記隣接した上方メッセージ、前記以前反復ループで計算された前記隣接した上ラインに対応する前記隣接した下方メッセージを受けて前記両眼差値を計算する両眼差計算プロセッサと、
前記左右映像ピクセルデータと前記前方メッセージ及び前記後方メッセージ、前記隣接した下方メッセージの入力を受けて現在のラインに対応する現在の下方メッセージを計算する下方プロセッサと、
前記左右映像ピクセルデータと前記前方メッセージ及び前記後方メッセージ、前記隣接した上方メッセージの入力を受けて現在のラインに対応する現在の上方メッセージを計算する上方プロセッサと
を含むことを特徴とする請求項１に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項８】
前記映像整合部は映像全体に対して前記映像整合を複数回繰り返し行って両眼差映像のノイズを低減することを特徴とする請求項７に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項９】
前記前方処理時に前記前方プロセッサが動作し、前記後方処理時に前記後方及び上方、下方プロセッサ、前記両眼差計算プロセッサが動作することを特徴とする請求項７に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項１０】
前記映像整合部は、
前記左右映像ピクセルデータを格納するスキャンラインバッファと、
複数のプロセッサが並列配列されている並列プロセッサ部と、
前記上方及び下方メッセージを格納する２つ以上のメッセージバッファと
を含み、
それぞれの前記プロセッサは、前記スキャンラインバッファから前記左右映像ピクセルデータを受信し、前記上方メッセージを格納しているメッセージバッファから前記上方メッセージを受信し、前記下方メッセージを格納している他のメッセージバッファから前記下方メッセージを受信してそれぞれの映像ラインを処理した後、前記上方メッセージを格納している前記メッセージバッファに前記下方メッセージを格納し、前記下方メッセージを格納している前記他のメッセージバッファに前記上方メッセージを格納することを特徴とする請求項１に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項１１】
並列に配列されている前記プロセッサの同時実行により複数のラインを処理することを特徴とする請求項１０に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項１２】
前記並列プロセッサ部は、
前記左右映像ピクセルデータ及び隣接するメッセージバッファから隣接した下ラインに対応する隣接した上方メッセージ、他の隣接するメッセージバッファから隣接した上ラインに対応する隣接した下方メッセージを受けて前方メッセージを計算する前方プロセッサと、
前記計算された前方メッセージを格納するスタックと、
前記左右映像ピクセルデータ及び前記隣接するメッセージバッファから前記隣接した下ラインに対応する前記隣接した上方メッセージ、前記他の隣接するメッセージバッファから前記隣接した上ラインに対応する前記隣接した下方メッセージを受けて後方メッセージを計算する後方プロセッサと、
前記左右映像ピクセルデータと前記スタックに格納された前記前方メッセージ及び前記後方メッセージ、前記隣接した上方メッセージ、前記隣接した下方メッセージを受けて両眼差値を計算する両眼差計算プロセッサと、
前記左右映像ピクセルデータと前記前方メッセージ及び前記後方メッセージ、前記隣接した下方メッセージの入力を受けて現在の下方メッセージを計算する下方プロセッサと、
前記左右映像ピクセルデータと前記前方メッセージ及び前記後方メッセージ、前記隣接した上方メッセージの入力を受けて現在の上方メッセージを計算する上方プロセッサと
を含むことを特徴とする請求項１０に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項１３】
前記映像整合部は、映像全体に対して映像整合を複数回繰り返し行い、一定数の前記プロセッサが同一数のラインをそれぞれ並列に処理することを特徴とする請求項１０に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項１４】
それぞれの前記プロセッサが並列に処理されて前方処理時に前記前方プロセッサが動作し、後方処理時に前記後方及び上方、下方プロセッサ、両眼差計算プロセッサが動作することを特徴とする請求項１０に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項１５】
前記前方、後方、上方又は下方プロセッサは、
前記左右映像ピクセルデータの入力を受けてマッチングコストを計算するマッチングコストプロセッサと、
前記マッチングコストと多重メッセージ値の入力を受けて前方コストを計算する前方コストプロセッサと、
前記前方コストの入力を受けて格納するスタックと、
前記スタックから前記前方コストの入力を受けて後方コストを計算する後方コストプロセッサと、
前記後方コストを次回の実行時に再帰的に利用可能にするリカーシブバッファと
を含むことを特徴とする請求項２に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項１６】
前記前方コストプロセッサは、
前記入力を受けた多重メッセージ値から入力パラメータを差し引く減算器と、
前記減算器の出力値と前記マッチングコストを加算する第１加算器と、
第１入力値を１クロック遅延させる第１ディレーバッファと、
前記第１ディレーバッファの出力値に任意の制御パラメータ値を加算する第２加算器と、
前記第１加算器の出力値と前記第２加算器の出力値のうち、より小さい値を前記第１ディレーバッファの前記第１入力値として提供する第１比較器と、
前記第１加算器の出力値と第２入力値とを比較してより小さい値を出力する第２比較器と、
前記第２比較器の結果値を１クロック遅延させて前記遅延された値を前第２比較器の前記第２入力値として提供する第２ディレーバッファと、
前記第２比較器の出力値に制御パラメータを加算する第３加算器と
を含むことを特徴とする請求項１５に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項１７】
前記後方コストプロセッサは、
前記入力を受けた前方コストと比較入力値のうち、より小さい値を選択する第１比較器と、
前記第１比較器の出力値を１クロック遅延させる第１ディレーバッファと、
前記第１ディレーバッファの出力値と任意の制御パラメータ値を加算して前記加算した値を前記第１比較器の前記比較入力値として提供する第１加算器と、
前記第１比較器の出力値と入力パラメータとを比較してより小さい値を出力する第２比較器と、
前記第２比較器の出力値と追加入力値を加算する第２加算器と、
前記第２加算器の出力値を１クロック遅延させて前記遅延された値を前記第２加算器の前記追加入力値として提供する第２ディレーバッファと、
前記第２加算器の出力値を任意の数だけシフトさせて前記シフトされた値をパラメータとして出力するシフト部と
を含むことを特徴とする請求項１５に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項１８】
前記マッチングコストプロセッサは、
前記左右映像ピクセルデータの入力を受けて２つの値の差の絶対値を計算する差絶対値計算部と、
前記差絶対値計算部の出力値と制御パラメータとを比較してより小さい値を出力する比較器と
を含むことを特徴とする請求項１５に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項１９】
前記両眼差計算プロセッサは、
前記入力を受けたメッセージ値から入力パラメータを差し引く減算器と、
前記左右映像ピクセルデータを用いてマッチングコストを計算するマッチングコストプロセッサと、
前記減算器の出力値と前記マッチングコストプロセッサの出力値を加算する加算器と、
前記加算器の出力値と第２入力値のうち、より小さい値を出力する比較器と、
前記比較器の出力値を１クロック遅延させて前記遅延された値を前記比較器の前記第２入力値として提供するディレーバッファと、
前記両眼差計算プロセッサの各反復ループのステップ番号を知らせるカウンタと、
前記比較器の出力値が前記加算器の出力値になれば、前記カウンタの出力値を格納する両眼差出力バッファと
を含むことを特徴とする請求項１５に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項２０】
前記両眼差計算プロセッサは、反復ループ毎に前記左右映像ピクセルデータと入力メッセージ値のステート値を読み込んで前記マッチングコストを計算し、前記計算されたマッチングコストから入力パラメータを差し引いた値を前記入力メッセージ値に加算し、新たに計算された値と以前反復ループで計算された以前最小値とを比較して現在反復ループで現在の最小値を計算し、前記新たに計算された値が前記現在の最小値である時、前記現在反復ループのステップ番号をレジスタに格納し、全ての反復ループが終了すれば、前記レジスタに格納された値を出力することを特徴とする請求項１５に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項２１】
前記前方、後方プロセッサは、前記マッチングコストプロセッサにより計算されたコスト値と入力メッセージ値と前記リカーシブバッファに格納されたコスト値を用いて前記前方コストプロセッサがクロックステップ毎に前記前方コストを計算して前記計算された前方コストを前記スタックに格納する前方処理を終えると、前記後方コストプロセッサは前記スタックから前記前方コストを計算して後方コストを出力し、出力された後方コストを前記リカーシブバッファに入力させる後方処理を行うことを特徴とする請求項１５に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項２２】
前記前方コストプロセッサは、前記ディレーバッファを可能な限り大きい値に初期化し、反復ループ毎に入力コストを読み込みながら、前記入力コストから入力パラメータを差し引いた値を入力メッセージ値に加算し、前記加算した値を前記ディレーバッファに格納された以前値に制御パラメータを加算した値と比較してより小さい値を出力すると同時に、前記より小さい値を前記ディレーバッファに格納することを特徴とする請求項２１に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項２３】
前記後方コストプロセッサは、前記第１ディレーバッファを可能な限り最大値に初期化し、前記第２ディレーバッファを０に初期化した後、反復ループ毎に前記前方コストを読み込んで前記前方コストを前記第１ディレーバッファに格納された値に制御パラメータ値を加算した比較値と比較してより小さい値を前記第１ディレーバッファに格納し、前記第１ディレーバッファの出力値を入力パラメータと比較してより小さい値を出力し、反復ループ毎に前記第１ディレーバッファの現在の出力値を前記第１ディレーバッファの以前出力値と加算して前記加算した値を前記第２ディレーバッファに格納し、前記第２ディレーバッファに格納された値を任意の数だけシフトしてパラメータを計算した後に出力することを特徴とする請求項２１に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項２４】
前記上方、下方プロセッサは、クロックステップ毎に前記マッチングコストプロセッサにより計算されたコスト値と入力メッセージ値を用いて前記前方コストプロセッサが前方コストを計算した後、前記計算された前方コストを前記スタックに格納する前方処理を終えると、前記後方コストプロセッサは前記スタックから前記前方コストを受けて後方コストを出力する後方処理を行うことを特徴とする請求項１５に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項２５】
前記前方コストプロセッサは、前記ディレーバッファを可能な限り大きい値に初期化し、反復ループ毎に入力コストを読み込みながら、前記入力コストから入力パラメータを差し引いた値を入力マッサージ値に加算し、前記加算した値を前記ディレーバッファに格納された以前値に制御パラメータを加算した値と比較してより小さい値を出力すると同時に、前記より小さい値を前記ディレーバッファに格納することを特徴とする請求項２４に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項２６】
前記後方コストプロセッサは、前記第１ディレーバッファを可能な限り最大値に初期化し、前記第２ディレーバッファを０に初期化した後、反復ループ毎に前記前方コストを読み込んで前記前方コストを前記第１ディレーバッファに格納された値に制御パラメータを加算した値と比較してより小さい値を前記第１ディレーバッファに格納し、前記第１ディレーバッファの出力値は入力パラメータと比較して小さい値を出力し、ステップ毎に前記第１ディレーバッファの現在の出力値に前記第１ディレーバッファの以前出力値を加算して前記加算した値を前記第２ディレーバッファに格納し、前記第２ディレーバッファに格納された値を任意の数だけシフトしてパラメータを計算した後に出力することを特徴とする請求項２４に記載のメッセージ伝達基盤ステレオ映像整合システム。
【請求項２７】
前記前方、後方、上方、下方プロセッサは、それぞれ前方、後方、上方、下方メッセージを計算することを特徴とする請求項１５に記載のメッセージ伝達基盤ステレオ映像整合システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はメッセージ伝達基盤ステレオ映像整合システムに関し、更に詳しくは、多重ライン又はフル映像ライン処理方式のメッセージ伝達基盤リアルタイム並列ステレオ整合システムに関する。
【背景技術】
【０００２】
周知のように、ステレオ整合方法は一対の２次元イメージから３次元の空間情報を再現する方法である。図１に示すように、左側及び右側映像のエピポーラ線上の映像ラインから３次元空間における特定位置（Ｘ、Ｙ、Ｚ）に対応する左右ピクセルを見つける方法である。ここで、対応するピクセル対に対する両眼差ｄは、下記の式１のように定義される。
【数１】
2010509670.tif 000003
【０００３】
両眼差は距離情報を含み、このような両眼差から計算された幾何学的特性を深さという。従って、入力映像からリアルタイムで両眼差値を計算すれば、観測空間の３次元距離情報と形態情報を測定できる。
【０００４】
このようなステレオ整合方法については、Ｄｈｏｎｄなどの論文（下記の非特許文献１参照）に基本的な概念が開示されており、最新ステレオマッチングアルゴリズムはＳｚｅｌｉｓｋｉの論文（下記の非特許文献２参照）に分かりやすく整理されている。
【０００５】
ステレオマッチングは、ローカルコストを用いてウィナー・テーク・オール（Ｗｉｎｎｅｒ−ｔａｋｅ−ａｌｌ）方式でマッチングする技法があり、グローバルエネルギーモデルを立て、それに基づいてエネルギーを最小化する技法がある。ウィナー・テーク・オール方式は単一スキャンライン内でステレオ整合を行い、高速で処理が可能である代りに、両眼差エラーが非常に大きい。グローバルエネルギーモデル技法の代表としては、グラフカット（Ｇｒａｐｈ ｃｕｔ）、信頼性伝播（Ｂｅｌｉｅｆ Ｐｒｏｐａｇａｔｉｏｎ）などが挙げられる。グラフカットと信頼性伝播技法はエネルギー最小化技法であって、非常によい結果を出しているが、処理時間が長くかかる。即ち、信頼性伝播技法は、下上ラインの関係を利用してエラーの少ない良好なステレオマッチング結果を示す。また、信頼性伝播技法はそれぞれシークエンス毎に繰り返して隣接するプロセッサからメッセージを受け、同時にメッセージを計算して隣接するプロセッサに送る方式であるので、ハードウェア化して高速並列処理を行うようになれば、短時間内で処理が可能である。そして、それぞれのメッセージは前方、後方、上方、下方に映像のピクセル位置から隣接する方向にメッセージをやりとりする構造を有する。
【０００６】
前述したように、従来のリアルタイムアルゴリズムは高速で処理が可能である代りに、両眼差マッチングエラーが大きく、信頼性伝播技法は順次的ソフトウェアアルゴリズムであって、両眼差マッチングエラーは少ないが、処理時間が多くかかるという問題がある。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Ｕｍｅｓｈ Ｒ. Ｄｈｏｎｄ ａｎｄ Ｊ.Ｋ.Ａｇｇａｒｗａｌ, Ｓｔｒｕｃｔｕｒｅ ｆｒｏｍ Ｓｔｅｒｅｏ − ａ ｒｅｖｉｅｗ, ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓｔｅｍｓ, Ｍａｎ, ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ, １９（６）:５５３-５７２, ｎｏｖ／ｄｅｃ １９８９.
【非特許文献２】Ｄ. Ｓｃｈａｒｓｔｅｉｎ ａｎｄ Ｒ. Ｓｚｅｌｉｓｋｉ. Ａ Ｔａｘｏｎｏｍｙ ａｎｄ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｄｅｎｓｅ Ｔｗｏ−Ｆｒａｍｅ Ｓｔｅｒｅｏ Ｃｏｒｒｅｓｐｏｎｄｅｎｃｅ Ａｌｇｏｒｉｔｈｍｓ. ＩＪＣＶ ４７（１／２／３）:７-４２, Ａｐｒｉｌ-Ｊｕｎｅ ２００２.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は上記事情に鑑みてなされたものであって、その目的は、周辺環境に強く、少ない両眼差ノイズを有する映像整合方法を提供するために、単一スキャンライン以上の多様なスキャンラインをステレオマッチングに用いる信頼性伝播アルゴリズムの原理を基本的に用い、これを高速化し、チップの開発を容易にするために、従来の順次的ソフトウェアアルゴリズムとは異なる新たな並列パイプライン構造のアルゴリズムを提供することにある。
【課題を解決するための手段】
【０００９】
前記目的を実現するための本発明によるメッセージ伝達基盤ステレオ映像整合システムは、第１及び第２映像取得手段から入力される映像をデジタル信号に変換して第１及び第２ピクセルデータを出力する映像処理部と、同一エピポーラ線上の前記第１及び第２ピクセルデータのデータ値を用いて各ピクセルの上方、下方、前方、後方メッセージのうち少なくとも２つ以上のメッセージを計算し、隣接するピクセルに対して計算されたメッセージを用いて各ピクセルの両眼差値を計算する映像整合部とを含む。
【発明の効果】
【００１０】
前述したように、本発明によれば、従来の順次的ソフトウェアアルゴリズムとは異なり、ＶＬＳＩに実現可能な並列パイプラインのハードウェア構造を有することにより、高速処理が可能になる。即ち、整合時に多様な映像ラインを用いることで、周辺環境に強く、低いマッチングエラーを有すると同時に、新たな並列パイプラインＶＬＳＩ構造を有することで、０（Ｎ）の時間複雑度（ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ）を有するため、リアルタイム処理が可能であるという効果を奏する。
【００１１】
そして、多数の映像ラインをマッチングに用いることで、両眼差出力映像のノイズを除去できるので、周辺環境に安定的、且つ、正確な距離映像情報が得られるという効果がある。
【図面の簡単な説明】
【００１２】
【図１】ステレオ映像整合の概念図である。
【図２】本発明による多重ライン又はフル映像ライン処理方式のメッセージ伝達基盤リアルタイム並列ステレオ整合システムのブロック構成図である。
【図３】本発明の第１実施形態によってアルゴリズムIを行う映像整合部の構成図である。
【図４】本発明の第２実施形態によってアルゴリズムIIを行う映像整合部の構成図である。
【図５】本発明の第３実施形態によってアルゴリズムIIIを行う映像整合部の構成図である。
【図６】本発明の第４実施形態によってアルゴリズムIVを行う映像整合部の構成図である。
【図７】本発明の第４実施形態によってアルゴリズムIVを行う映像整合部でそれぞれのラインを処理するプロセッサの内部構成図である。
【図８】本発明による映像整合部を構成する前方、後方、上方、下方プロセッサの内部構成図である。
【図９】本発明による前方コストプロセッサの内部構成図である。
【図１０】本発明による後方コストプロセッサの内部構成図である。
【図１１】本発明によるマッチングコストプロセッサの内部構成図である。
【図１２】本発明による映像整合部に含まれる両眼差計算プロセッサの内部構成図である。
【図１３】本発明の第１実施形態によってアルゴリズムIを行う映像整合部の動作過程を示すフローチャートである。
【図１４】本発明の第２実施形態によってアルゴリズムIIを行う映像整合部の動作過程を示すフローチャートである。
【図１５】本発明の第３実施形態によってアルゴリズムIIIを行う映像整合部の動作過程を示すフローチャートである。
【図１６】本発明の第４実施形態によってアルゴリズムIVを行う映像整合部の動作過程を示すフローチャートである。
【図１７】本発明によるアルゴリズムI〜IVで両眼差計算アルゴリズムの処理過程を示すフローチャートである。
【図１８】本発明によるアルゴリズムI〜IVで前方、後方、上方、下方メッセージプロセシングの動作過程を示すフローチャートである。
【図１９】図１８の前方コスト計算アルゴリズムの処理過程を示すフローチャートである。
【図２０】図１８の後方コスト計算アルゴリズムの処理過程を示すフローチャートである。
【図２１】本発明によるマッチングコスト計算アルゴリズムの処理過程を示すフローチャートである。
【図２２】従来技術の映像整合による両眼差出力映像と、本発明の映像整合による両眼差出力映像とを比較して説明するための図である。
【図２３】従来技術の映像整合による両眼差出力映像と、本発明の映像整合による両眼差出力映像とを比較して説明するための図である。
【図２４】従来技術の映像整合による両眼差出力映像と、本発明の映像整合による両眼差出力映像とを比較して説明するための図である。
【図２５】従来技術の映像整合による両眼差出力映像と、本発明の映像整合による両眼差出力映像とを比較して説明するための図である。
【図２６】従来技術の映像整合による両眼差出力映像と、本発明の映像整合による両眼差出力映像とを比較して説明するための図である。
【図２７】従来技術の映像整合による両眼差出力映像と、本発明の映像整合による両眼差出力映像とを比較して説明するための図である。
【図２８】従来技術の映像整合による両眼差出力映像と、本発明の映像整合による両眼差出力映像とを比較して説明するための図である。
【発明を実施するための形態】
【００１３】
以下、本発明の好適な実施形態を添付する図面を参照して詳細に説明する。なお、本発明を説明するにおいて、関連した公知の構成又は機能に関する具体的な説明が本発明の要旨を曖昧にするおそれがあると判断される場合にはその詳細な説明を省略する。
【００１４】
本発明は、映像におけるそれぞれのピクセルに対する両眼差値を計算するために、各ピクセルの上方、下方、前方、後方メッセージを計算し、プロセッサが隣接するピクセルに対応する計算されたメッセージをやりとりする並列パイプライン構造を有する。そして、それぞれのメッセージの計算に対してＶＬＳＩで実現できるj構造を有する。
【００１５】
図２は、本発明による多重ライン又はフル映像ライン処理方式のメッセージ伝達基盤リアルタイム並列ステレオ整合システムのブロック構成図である。
【００１６】
図示するように、本発明による並列ステレオ整合システムは、映像取得手段である第１、２カメラ１０、２０から入力される映像をデジタル信号に変換して第１及び第２ピクセルデータを出力する映像処理部３０と、同一エピポーラ線上の第１及び第２ピクセルデータから所定のメッセージを計算し、計算されたメッセージを用いて決定値をユーザシステム５０に出力する映像整合部４０とを含む。ここで、第１及び第２ピクセルデータは、それぞれ同一エピポーラ線上の左側及び右側映像ラインのピクセルデータであることが好ましい。
【００１７】
映像整合部４０は、大きくアルゴリズムI、II、III、IVに応じてそれぞれ変わる。
【００１８】
まず、以下の説明で用いられる略号を整理すれば、次の通りである。
【００１９】
ｔfは前方プロセシング時間を意味し、ｔbは後方プロセシング時間を意味し、ｔuは上方プロセシング時間を意味し、ｔdは下方プロセシング時間を意味し、ｔoは両眼差計算（Ｄｉｓｐａｒｉｔｙ Ｃｏｍｐｕｔａｔｉｏｎ）時間を意味し、ｔallは前方、後方、上方、下方プロセシング及び両眼差計算時間を意味する。このような各時間ｔf、ｔb、ｔu、ｔd、ｔo、ｔallは、並列に処理される時に同じタイミングになることもできる。
【００２０】
図３は、本発明の第１実施形態によってアルゴリズムIを行う映像整合部４０の構成図である。
【００２１】
左右映像ピクセルデータｇr（ｊ＋ｄ（ｔall）、ｉ）、ｇl（ｊ、ｉ）をスキャンラインバッファ４０１１に格納し、前方プロセッサ（ＰＥf）４０１２が左右映像ピクセルデータを受けて、その映像ピクセルデータ値を用いて計算された前方メッセージｍf（ｔf、ｊ）をスタック４０１３に格納する。後方プロセッサ（ＰＥb）４０１４も左右映像ピクセルデータｇr（ｊ＋ｄ（ｔall）、ｉ）、ｇl（ｊ、ｉ）値を受けて、その映像ピクセルデータを用いて計算されたメッセージｍb（ｔb）を両眼差計算プロセッサ（ＰＥo）４０１５に送れば、両眼差計算プロセッサ（ＰＥo）４０１５はスタック４０１３から格納された前方メッセージｍf（ｔf、ｊ）を受け、後方メッセージｍb（ｔb）、そして左右映像ピクセルデータを受けて両眼差値を出力する。
【００２２】
図４は、本発明の第２実施形態によってアルゴリズムIIを行う映像整合部４０の構成図である。
【００２３】
左右映像ピクセルデータｇr（ｊ＋ｄ（ｔall）、ｉ）、ｇl（ｊ、ｉ）をスキャンラインバッファ４０２１に格納し、前方プロセッサ（ＰＥf）４０２２がスキャンラインバッファ４０２１から左右映像ピクセルデータを受け、バッファ４０２６から上ラインで計算された下方メッセージｍd（ｔall、ｊ、ｉ−１）を受けて、その受けた映像ピクセルデータと下方メッセージを用いて計算された前方メッセージｍf（ｔf、ｊ）をスタック４０２３に格納する。後方プロセッサ（ＰＥb）４０２４も左右映像ピクセルデータｇr（ｊ＋ｄ（ｔall）、ｉ）、ｇl（ｊ、ｉ）及び下方メッセージｍd（ｔall、ｊ、ｉ−１）を受けて計算されたメッセージ値ｍb（ｔb）を両眼差計算プロセッサ（ＰＥo）４０２５に送れば、両眼差計算プロセッサ（ＰＥo）４０２５でスタック４０２３から格納された前方メッセージｍf（ｔf、ｊ）を受け、後方メッセージｍb（ｔb）、下方メッセージ、左右映像ピクセルデータの入力を受けて両眼差値を出力する。下方プロセッサ（ＰＥd）４０２７では上ラインの下方メッセージと後方メッセージ、前方メッセージ、映像ピクセルデータの入力を受けて下方メッセージｍd（ｔd、ｊ、ｉ）を計算してバッファ４０２６に格納する。
【００２４】
図５は、本発明の第３実施形態によってアルゴリズムIIIを行う映像整合部４０の構成図である。アルゴリズムIIIは反復的計算構造を有し、反復ループ（ｉｔｅｒａｔｉｏｎ ｌｏｏｐ）をｆで表した。
【００２５】
左右映像ピクセルデータｇr（ｊ＋ｄ（ｔall）、ｉ）、ｇl（ｊ、ｉ）をスキャンラインバッファ４０３１に格納し、前方プロセッサ（ＰＥf）４０３２がスキャンラインバッファ４０３１から左右映像ピクセルデータ値ｇr（ｊ＋ｄ（ｔall）、ｉ）、ｇl（ｊ、ｉ）を受け、バッファ４０３６から以前反復ループで計算された上ラインと下ラインの下方メッセージ値ｍd（ｔall、ｊ、ｉ−１、ｆ−１）及び上方メッセージ値ｍu（ｔall、ｊ、ｉ＋１、ｆ−１）を受けて前方メッセージ値ｍf（ｔf、ｊ）を計算してスタック４０３３に格納し、後方プロセッサ（ＰＥb）４０３４も左右映像ピクセルデータ値及び上方、下方メッセージを受けて計算された後方メッセージｍb（ｔb）を両眼差計算プロセッサ（ＰＥo）４０３５に送れば、両眼差計算プロセッサ（ＰＥo）４０３５でスタック４０３３に格納された前方メッセージと後方、上方、下方メッセージ、そして左右映像ピクセルデータを受けて両眼差値を出力する。下方プロセッサ（ＰＥd）４０３７では上ラインの下方メッセージと後方、前方メッセージ、映像ピクセルデータの入力を受けて新たな下方メッセージｍd（ｔd、ｊ、ｉ）、ｆ）を計算してバッファ４０３６に格納する。上方プロセッサ（ＰＥu）４０３８では下ラインの上方メッセージと後方、前方メッセージ、映像ピクセルデータの入力を受けて新たな上方メッセージｍu（ｔu、ｊ、ｉ、ｆ）を計算してバッファ４０３６に格納する。
【００２６】
図６は、本発明の第４実施形態によってアルゴリズムIVを行う映像整合部４０の構成図である。アルゴリズムIVは反復的計算構造を有し、反復ループをｆで表した。そして、高速処理のために、Ｐ個のプロセッサＰＥ０、ＰＥ１、ＰＥ２、…が並列に処理される。
【００２７】
左右映像ピクセルデータはカメラ映像から入力され、スキャンラインバッファ４０４１に格納される。Ｐ個のそれぞれのラインに対してプロセッサＰＥ０、ＰＥ１、ＰＥ２…が並列に配置されて同時にＰ個のラインを処理し、処理が終了すれば、その次のＰ個のラインを同時に処理する方式で行われる。従って、図６に示すように、Ｐ個のラインで最初のプロセッサは最初のライン処理を行い、ｐ番目のプロセッサはｐ番目のライン処理を行う。このような方式で１つの映像は映像ライン数がＮ個であれば、計Ｎ／Ｐだけ処理しなければ、映像全体が処理されない。各プロセッサは、左右映像ピクセルデータｇr（ｊ＋ｄ（ｔall）、ｑ＊Ｐ＋ｐ）、ｇl（ｊ、ｑ＊Ｐ＋ｐ）をスキャンラインバッファ４０４１から入力を受け、隣接するプロセッサとの通信のために、上位バッファ４０４６から下方メッセージｍd（ｔd、ｊ、ｑ＊Ｐ＋ｐ、ｆ）を受け、下位バッファ４０４６から上方メッセージｍu（ｔu、ｊ、ｑ＊Ｐ＋ｐ、ｆ）を受けて処理した後、上位バッファ４０４６に上方メッセージを格納し、下位バッファ４０４６に下方メッセージを格納する。全てのプロセッサは、このような方式で高速で互いにメッセージをやりとりし、並列に処理される。
【００２８】
図７は、本発明の第４実施形態によってアルゴリズムIVを行う映像整合部４０でそれぞれのラインを処理するプロセッサＰＥ０、ＰＥ１、ＰＥ２、…の内部構成図である。
【００２９】
前方プロセッサ（ＰＥf）４０４２が左右映像ピクセルデータｇr（ｊ＋ｄ（ｔall）、ｑ＊Ｐ＋ｐ）、ｇl（ｊ、ｑ＊Ｐ＋ｐ）と以前反復ループで計算された上ラインと下ラインの下方メッセージ値ｍd（ｔall、ｊ、ｑ＊Ｐ＋ｐ−１、ｆ−１）及び上方メッセージ値ｍu（ｔall、ｊ、ｑ＊Ｐ＋ｐ＋１、ｆ−１）の入力を受けて前方メッセージ値ｍf（ｔf、ｊ）を計算してスタック４０４３に格納する。後方プロセッサ（ＰＥb）４０４４も左右映像ピクセルデータ及び上方、下方メッセージを受けてその映像ピクセルデータとメッセージを用いて計算された後方メッセージｍb（ｔf）を両眼差計算プロセッサ（ＰＥo）４０４５に送れば、両眼差計算プロセッサ（ＰＥo）４０４５でスタック４０４２から格納された前方メッセージと後方、上方、下方メッセージ、そして左右映像ピクセルデータを受けて両眼差値を出力する。下方プロセッサ（ＰＥd）４０４７では上ラインの下方メッセージと後方、前方メッセージ、映像ピクセルデータの入力を受けて新たな下方メッセージを計算する。上方プロセッサ（ＰＥu）４０４８では下ラインの上方メッセージと後方、前方メッセージ、映像ピクセルデータの入力を受けて新たな上方メッセージを計算する。
【００３０】
図８は、本発明によるリアルタイム並列ステレオ整合システムで映像整合部４０を構成する前方、後方、上方、下方プロセッサの内部構成図である。
【００３１】
各プロセッサは、メッセージを計算するために構成されるが、左右映像ピクセルデータｇr（ｊ＋ｄ（ｔi））、ｇl（ｊ）の入力を受けてマッチングコストを計算するマッチングコストプロセッサ４０５１と、マッチングコストと多重メッセージ値の入力を受けて前方コストを計算する前方コストプロセッサ４０５２と、前方コストの入力を受けて格納するスタック４０５３と、スタック４０５３から前方コストの入力を受けて後方コストを計算する後方コストプロセッサ４０５４と、後方コストを次の実行時に再帰的に利用可能にするリカーシブバッファ４０５５とを含む。
【００３２】
図９は、本発明による前方コストプロセッサ４０５２の内部構成図である。図９で便宜上、前方コストプロセッサを２つの回路に分けて示したが、実際は１つの回路である。
【００３３】
前方コストプロセッサ４０５２は、入力を受けたメッセージから入力パラメータを差し引く減算器４０５２１と、それぞれの減算器４０５２１の出力とマッチングコストを加算する第１加算器４０５２２と、第１加算器４０５２２の出力値と第２加算器４０５２５の出力値のうち、小さい値を出力する比較器４０５２３と、比較器４０５２３値を１クロック遅延させる第１ディレーバッファ４０５２４と、第１ディレーバッファ４０５２４の出力にコストＣ0を加算する第２加算器４０５２５と、第１加算器４０５２２の出力値と他の入力値とを比較して小さい値を出力する第２比較器４０５２６と、第２比較器４０５２６の結果値を１クロック遅延させて第２比較器４０５２６の他の入力値として提供する第２ディレーバッファ４０５２７と、第２比較器４０５２６の出力にコストＫ1を加算して出力する第３加算器４０５２８とを含む。
【００３４】
図１０は、本発明による後方コストプロセッサ４０５４の内部構成図である。図１０で便宜上、後方コストプロセッサを２つの回路に分けて示したが、実際は１つの回路である。
【００３５】
後方コストプロセッサ４０５４は、入力を受けたコストと第１加算器４０５４３の出力値のうち、小さい値を選択する第１比較器４０５４１と、第１比較器４０５４１の出力を１クロック遅延させて第１加算器４０５４３に提供する第１ディレーバッファ４０５４２と、Ｃ0値と第１ディレーバッファ４０５４２の出力を加算する第１加算器４０５４３と、第１比較器４０５４１の出力と入力パラメータ値とを比較してより小さい値を出力する第２比較器４０５４４と、第２比較器４０５４４の出力値と第２ディレーバッファ４０５４６の出力値を加算する第２加算器４０５４５と、第２加算器４０５４５の出力値を１クロック遅延させて第２加算器４０５４５の入力値として提供する第２ディレーバッファ４０５４６と、第２加算器４０５４５の出力値を任意の数だけシフトさせてパラメータとして出力するシフト部４０５４７とを含む。
【００３６】
図１１は、本発明によるマッチングコストプロセッサ４０５１の内部構成図である。
【００３７】
マッチングコストプロセッサ４０５１は、左右映像ピクセルデータの入力を受けて２つの映像ピクセルデータ値の差の絶対値を計算する差絶対値計算部４０５１１と、差絶対値計算部４０５１１の出力値をパラメータＫ2と比較してより小さい値を出力する比較器４０５１２とを含む。
【００３８】
図１２は、本発明によるリアルタイム並列ステレオ整合システムで映像整合部４０に含まれる両眼差計算プロセッサ４０１５、４０２５、４０３５、４０４５の内部構成図である。
【００３９】
入力を受けたメッセージから入力パラメータを差し引く減算器４００５１と、左右映像ピクセルデータからマッチングコストを計算するマッチングコストプロセッサ４００５２と、それぞれの減算器４００５１の出力とマッチングコストプロセッサ４００５２の出力を加算する加算器４００５３と、比較器４００５５の出力値を１クロック遅延させるディレーバッファ４００５４と、ディレーバッファ４００５４の出力値と加算器４００５３の出力値のうち、小さい値を出力する比較器４００５５、両眼差計算プロセシングのステップを知らせるｔカウンタ４００５６と、比較器４００５５の２つの入力値のうち、加算器４００５３からの入力値がより小さい値になった時、ｔカウンタ４００５６値を格納する両眼差出力バッファ４００５７とで構成される。
【００４０】
以下、本発明によるリアルタイム並列ステレオ整合システムの各構成要素別の動作順序を詳細に説明する。
【００４１】
図１３は、本発明の第１実施形態によってアルゴリズムIを行う映像整合部４０の動作過程を示すフローチャートである。
【００４２】
映像ライン数がＮであり、１ラインでピクセル数がＭである時、ｉ番目の映像ラインとその映像ラインでｊ番目のピクセルに対して個別に計算が行われる。本アルゴリズムは、ｉ番目の映像ラインで、０からＭ−１までｊ番目のピクセル上で前方処理（Ｓ１１１〜Ｓ１１７）され、その後、Ｍ−１から０までｊ番目のピクセル上で後方処理（Ｓ１２１〜Ｓ１２８）される。前方処理では図３の前方プロセッサが左右映像のピクセルデータ値の入力を受けて前方メッセージ値を計算（Ｓ１１４）し、その前方メッセージ値をスタックに格納（Ｓ１１５）する。そして、後方処理では図３の後方プロセッサが左右映像のピクセルデータ値の入力を受け、後方メッセージ値を計算（Ｓ１２３）し、図３の両眼差計算プロセッサは後方メッセージ値とスタックから前方メッセージ値を読み込んで両眼差値を計算（Ｓ１２４）する。
【００４３】
図１４は、本発明の第２実施形態によってアルゴリズムIIを行う映像整合部４０の動作過程を示すフローチャートである。
【００４４】
ｉ番目の映像ラインとその映像ラインでｊ番目のピクセルに対して個別に計算が行われる。本アルゴリズムは、ｉ番目の映像ラインで０からＭ−１までｊ番目のピクセル上で前方処理（Ｓ２１１〜Ｓ２１７）された後、Ｍ−１から０までｊ番目のピクセル上で後方処理（Ｓ２２１〜Ｓ２２９）される。前方処理では図４の前方プロセッサで左右映像ピクセルデータ値と上ラインの下方メッセージ値の入力を受けて前方メッセージ値が計算（Ｓ２１４）され、その前方メッセージ値がスタックに格納（Ｓ２１５）される。そして、後方処理では図４の後方プロセッサで左右映像ピクセルデータ値と上ラインの下方メッセージ値の入力を受け、後方メッセージ値を計算（Ｓ２２３）し、図４の下方プロセッサでは左右映像ピクセルデータ値と前方、後方及び上ラインの下方メッセージ値の入力を受けて現在のラインの下方メッセージ値を計算（Ｓ２２４）する。図４の両眼差計算プロセッサでは下方、後方、前方メッセージ値を読み込んで両眼差値を計算（Ｓ２２５）する。
【００４５】
図１５は、本発明の第３実施形態によってアルゴリズムIIIを行う映像整合部４０の動作過程を示すフローチャートである。
【００４６】
ｆ番目の反復ループとそのループでｉ番目の映像ラインとその映像ラインでｊ番目のピクセルに対して個別に計算が行われる。本アルゴリズムは、映像全体をＦ回数だけ繰り返し行って両眼差映像のノイズを低減する。本アルゴリズムはｉ番目のラインで、ｊ番目のピクセル上では０からＭ−１まで前方処理（Ｓ３１１〜Ｓ３１８）された後、ｊ番目のピクセル上でＭ−１から０まで後方処理（Ｓ３２１〜Ｓ３３２）される。前方処理では図５の前方プロセッサで左右映像のピクセルデータ値とｆ−１番目の反復ループで上ラインの下方メッセージ値とｆ−１番目の反復ループで下ラインの上方メッセージ値の入力を受けて前方メッセージ値が計算（Ｓ３１５）され、その値がスタックに格納（Ｓ３１６）される。そして、後方処理では図５の後方プロセッサで左右映像のピクセルデータ値とｆ−１番目の反復ループにおける上ラインの下方メッセージ値とｆ−１番目の反復ループにおける下ラインの上方メッセージ値の入力を受け、後方メッセージ値を計算（Ｓ３２３）し、図５の下方プロセッサでは左右映像のピクセルデータ値と前方、後方及びｆ−１番目の反復ループにおける上ラインの下方メッセージ値の入力を受けて現在のラインの下方メッセージ値を計算（Ｓ３２４）する。図５の上方プロセッサでは左右映像のピクセルデータ値と前方、後方及びｆ−１番目の反復ループにおける下ラインの上方メッセージ値の入力を受けて現在のラインの上方メッセージ値を計算（Ｓ３２４）する。図５の両眼差計算プロセッサでは後方、前方メッセージ値とｆ−１番目の反復ループにおける上方、下方メッセージ値を読み込んで両眼差値を計算（Ｓ３２５）する。
【００４７】
図１６は、本発明の第４実施形態によってアルゴリズムIVを行う映像整合部４０の動作過程を示すフローチャートである。
【００４８】
本アルゴリズムは、映像全体においてＦ回繰り返して行われ、高速処理のために、Ｐ個のプロセッサが並列に処理される。即ち、本アルゴリズムは、アルゴリズムIIIの並列高速処理のために構成される。それぞれの映像ラインに対してプロセッサが並列に配置されて同時にＰ個のラインを処理し、処理が終了すれば、その次のＰ個のラインを同時に処理する方式で行われる。従って、図６に示すように、Ｐ個のラインで、最初のプロセッサは最初のラインを、ｐ番目のプロセッサはｐ番目のラインを処理する。このような方式で１つの映像は映像ライン数がＮ個である時、計Ｑ＝Ｎ／Ｐだけ行わなければ、映像全体が完全に処理されない。
【００４９】
ｉ番目のラインで、処理はｊ番目のピクセル上では０からＭ−１まで前方処理（Ｓ４１１〜Ｓ４１８）された後、ｊ番目のピクセル上でＭ−１から０まで後方処理（Ｓ４２１〜Ｓ４３１）される。前方処理では図７の前方プロセッサで左右映像ピクセルデータ値とｆ−１番目の反復ループで上ラインの下方メッセージ値とｆ−１番目の反復ループで下ラインの上方メッセージ値の入力を受けて前方メッセージ値が計算（Ｓ４１５）され、その値がスタック（Ｓ４１６）に格納される。そして、後方処理では図７の後方プロセッサで左右映像のピクセルデータ値とｆ−１番目の反復ループにおける上ラインの下方メッセージ値とｆ−１番目の反復ループにおける下ラインの上方メッセージ値の入力を受け、後方メッセージ値を計算（Ｓ４２３）し、図７の下方プロセッサでは左右映像のピクセルデータ値と前方、後方及びｆ−１番目の反復ループにおける上ラインの下方メッセージ値の入力を受けて現在のラインの下方メッセージ値を計算（Ｓ４２４）する。図６Ｂの上方プロセッサでは左右映像のピクセルデータ値と前方、後方及びｆ−１番目の反復ループにおける下ラインの上方メッセージ値の入力を受けて現在のラインの上方メッセージ値を計算（Ｓ４２４）する。図５の両眼差計算プロセッサでは後方、前方メッセージ値及びｆ−１番目の反復ループにおける上方、下方メッセージ値を読み込んで両眼差値を計算（Ｓ４２５）する。
【００５０】
図１７は、本発明によるアルゴリズムI〜IVで両眼差計算アルゴリズムの処理過程を示すフローチャートである。
【００５１】
段階Ｓ５０８〜Ｓ５０９により、入力メッセージｍk（ｔ）はｔが０からＤ−１までのステート値を有するベクトルであり、ｍk（−１）は入力パラメータを示す。Ｕ0（−１）＝Ｋに初期化（可能な限り最大値）（Ｓ５０１）し、左右映像ピクセルデータ値と入力メッセージのそれぞれのステート値は反復ループ毎に入力される（Ｓ５０２）。そして、左右映像ピクセルデータ値を用いて図１１のマッチングコストプロセッサでマッチングコストを計算（Ｓ５０３）し、計算されたマッチングコストを入力メッセージから入力パラメータを差し引いた値に加算（Ｓ５０４）する。新たに計算されたＵi（ｔ）値は以前ループで計算された最小値Ｕ0（ｔ−１）と比較（Ｓ５０５）して現ループの最小値Ｕ0（ｔ）を計算（Ｓ５０６、Ｓ５０７）する。そして、新たに計算された値Ｕi（ｔ）が最小値である時、反復ループの個数ｔをｄレジスタに格納し、全ステップが終了すれば、値ｄを出力（Ｓ５１０）する。即ち、それぞれステップ毎に計算された値が全体反復ループで最小となるＵi（ｔ）を求め、その時のループの個数ｔを値ｄとして出力するアルゴリズムである。
【００５２】
図１８は、本発明によるアルゴリズムI〜IVで前方、後方、上方、下方メッセージの処理過程を示すフローチャートである。
【００５３】
図８のマッチングコストプロセッサでは左右映像ピクセルデータの入力（Ｓ６０１）を受けてマッチングコストｍdata（ｔ）を計算（Ｓ６０２）し、図８の前方コストプロセッサではマッチングコストｍdata（ｔ）と入力メッセージと図８のリカーシブバッファから入力されるｍ0（ｔbuf）の入力を受けて前方コストを計算（Ｓ６０３）した後、スタックに格納（Ｓ６０４）し、図８の後方コストプロセッサではスタックで前方コスト値を読み込んで（Ｓ６０５）、後方コスト値を出力（Ｓ６０６〜Ｓ６０７）する。このとき、出力された後方コスト値が図８のリカーシブバッファに入力されて次回の前記アルゴリズムを行う際に用いることができる。ｍ0（ｔbuf）は前方及び下方メッセージを計算する過程で再帰的に前方コストプロセッサが計算を行う時、メッセージ入力として提供される。
【００５４】
図１９は、図１８の前方コスト計算アルゴリズムの処理過程を示すフローチャートである。
【００５５】
段階Ｓ７０７〜Ｓ７０８により、入力コストｍk（ｔ）はｔが０からＤ−１までの値を有するベクトルであり、ｍk（−１）は入力パラメータを示す。Ｕ0（−１）＝Ｋに初期化（Ｓ７０１）し、入力コスト値は反復ループ毎に入力され（Ｓ７０２）、入力コストから入力パラメータを差し引いた値を加算する（Ｓ７０３）。新たに計算された値Ｕi（ｔ）は、以前ループで計算されたＵ0（ｔ−１）＋Ｃ0と比較（Ｓ７０４）して最小値を現ループのＵ0（ｔ）として計算（Ｓ７０５〜Ｓ７０６）する。
【００５６】
図２０は、図１７の後方コスト計算アルゴリズムの処理過程を示すフローチャートである。
【００５７】
段階Ｓ８１０〜Ｓ８１１により、入力メッセージＵi（ｔ）はｔが−１からＤ−１までのステート値を有するベクトルであり、ｍk（−１）は入力パラメータを示す。Ｕ0（−１）＝Ｋに初期化（可能な限り最大値）（Ｓ８０１）し、反復ループ毎に前方コストの各ステート値Ｕi（ｔ）が入力される（Ｓ８０２）。Ｕi（ｔ）と以前ループで計算されたｍa（ｔ−１）＋Ｃ0とを比較して最小値を現ループのｍa（ｔ）にセットする（Ｓ８０３〜Ｓ８０５）。
【００５８】
次に、ｍa（ｔ）は再び入力パラメータＵi（−１）と比較されて小さい値がｍ0（ｔ）として計算されて出力される（Ｓ８０６〜Ｓ８０８）。
【００５９】
ｍs（ｔ）は０に初期化された後、反復ループ毎にｍ0（ｔ）を加算し（Ｓ８０９）、最終のループでｍs（Ｄ−１）をＡ0だけシフトライト（Ｓｈｉｆｔ ｒｉｇｈｔ）する（Ｓ８１２）。このシフトされた値は、メッセージの正規化パラメータとなる。
【００６０】
図２１は、本発明によるリアルタイム並列ステレオ整合システムでマッチングコスト計算アルゴリズムの処理過程を示すフローチャートである。
【００６１】
左右映像ピクセルデータの入力を受けて２つデータの差の絶対値ａ（ｔ）を計算し（Ｓ９０１）、ａ（ｔ）とＫ1とを比較（Ｓ９０２）して、より小さい値がｍdata（ｔ）として計算（Ｓ９０３、Ｓ９０４）される。
【００６２】
図２２及び図２３は、入力される左右映像を示し、図２４は、基準（ｒｅｆｅｒｅｎｃｅ）両眼差出力映像を示す。図２５は、左右映像の単一スキャンラインのみを用いた他のアルゴリズム（ｓｃａｎ ｌｉｎｅ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ）の計算結果を示す。図２６は、本発明の第１実施形態によってアルゴリズムIを行って得られた両眼差出力映像であり、図２７は、本発明の第２実施形態によってアルゴリズムIIを行って得られた両眼差出力映像であり、図２８は、本発明の第３実施形態によってアルゴリズムIIIを行うか、本発明の第４実施形態によってアルゴリズムIVを行って得られた両眼差出力映像である。
【００６３】
このように本発明の実施形態によれば、アルゴリズムIからアルゴリズムII、アルゴリズムIII、アルゴリズムIVに発展するほど、水平方向のストライプノイズが除去されて両眼差エラーが減少したことが分かる。
【００６４】
以上、本発明の幾つかの実施形態に限定して説明したが、本発明の技術が当業者によって容易に変形実施される可能性は自明である。このように変形された実施形態は、本発明の特許請求の範囲に記載された技術思想に当然含まれるものと理解すべきである。
【図１】
2010509670.tif 000004
【図２】
2010509670.tif 000005
【図３】
2010509670.tif 000006
【図４】
2010509670.tif 000007
【図５】
2010509670.tif 000008
【図６】
2010509670.tif 000009
【図７】
2010509670.tif 000010
【図８】
2010509670.tif 000011
【図９】
2010509670.tif 000012
【図１０】
2010509670.tif 000013
【図１１】
2010509670.tif 000014
【図１２】
2010509670.tif 000015
【図１３】
2010509670.tif 000016
【図１４】
2010509670.tif 000017
【図１５】
2010509670.tif 000018
【図１６】
2010509670.tif 000019
【図１７】
2010509670.tif 000020
【図１８】
2010509670.tif 000021
【図１９】
2010509670.tif 000022
【図２０】
2010509670.tif 000023
【図２１】
2010509670.tif 000024
【図２２】
2010509670.tif 000025
【図２３】
2010509670.tif 000026
【図２４】
2010509670.tif 000027
【図２５】
2010509670.tif 000028
【図２６】
2010509670.tif 000029
【図２７】
2010509670.tif 000030
【図２８】
2010509670.tif 000031
【国際調査報告】
2010509670.tif 000032
2010509670.tif 000033