(57)【要約】【課題】垂直方向への両眼差ノイズを減少させることができる映像整合方法を提供する。【解決手段】本発明は、一対の２次元映像から３次元の空間情報を再創出する映像整合方法を提供する。この時、映像整合のために両眼差を利用するが、既存の映像整合方法では両眼差の値で垂直方向へのノイズが激しい。本発明では、両眼差を計算する時に隣接する映像ラインの両眼差の情報を制約条件として使用するので、垂直方向へのノイズを除去することができる。そして、両眼差を差動コーディング方式で圧縮して圧縮率を高めることができる。【選択図】図２
2006079584.tif 000002
【特許請求の範囲】
【請求項１】
第１及び第２カメラから入力される映像をデジタル信号に変換して第１及び第２ピクセルデータを出力する映像処理部、そして
同一エピポーラ線上の前記第１及び第２ピクセルデータから所定のコストを決定し、前記所定のコストを決定する前記第１決定値を追跡し、直前のエピポーラ線上の前記第１及び第２ピクセルデータから追跡された第１決定値を利用して最適の第２決定値を出力する映像整合部を含む、複数の映像ラインを利用した映像整合システム。
【請求項２】
前記第１及び第２ピクセルデータは各々同一エピポーラ線上の左側及び右側映像ラインのピクセルデータである、請求項１に記載の複数の映像ラインを利用した映像整合システム。
【請求項３】
前記映像整合部は、
前記第１及び第２ピクセルデータを各々再配列して出力する第１及び第２入力バッファー、そして
前記第１及び第２入力バッファーから各々前記第１及び第２ピクセルデータを受信して前記第１及び第２決定値を追跡するプロセシングエレメントアレイ部を含む、請求項１または２に記載の複数の映像ラインを利用した映像整合システム。
【請求項４】
前記映像整合部は、前記第２決定値の入力を受けて圧縮するエンコーダをさらに含み、
前記エンコーダは、前記第２決定値から幾何学的に存在可能性のない経路を除いて処理する、請求項３に記載の複数の映像ラインを利用した映像整合システム。
【請求項５】
前記プロセシングエレメントアレイ部は、
前記第１ピクセルデータを順次に受信する複数の第１映像レジスター、
前記第２ピクセルデータを順次に受信する複数の第２映像レジスター、そして
前記第１及び第２映像レジスターから各々前記第１及び第２ピクセルデータを受信して前記第１及び第２決定値を追跡する複数のプロセシングエレメントを含む、請求項３に記載の複数の映像ラインを利用した映像整合システム。
【請求項６】
前記第１及び第２映像レジスターは各々Ｎ/２個からなり、前記プロセシングエレメントはＮ個からなる、請求項５に記載の複数の映像ラインを利用した映像整合システム。
【請求項７】
前記プロセシングエレメントは、隣接するプロセシングエレメントとコスト値及び活性信号を送受信する、請求項５に記載の複数の映像ラインを利用した映像整合システム。
【請求項８】
前記活性信号は、マルチラインコストを計算するためのマルチラインプロセシング用活性信号と隣接するプロセシングエレメントの後方プロセシング用活性信号とを含む、請求項７に記載の複数の映像ラインを利用した映像整合システム。
【請求項９】
前記プロセシングエレメントは、
前記第１及び第２ピクセルデータ及び前記マルチラインプロセシング用活性信号からコスト値を決定し、前記決定したコストの経路を示す前記第１決定値を計算する前方プロセッサー、
前記第１決定値を保存するスタック、そして
隣接するエピポーラ線上に対する前記第１決定値及び前記後方プロセシング用活性信号から前記第２決定値を計算する後方プロセッサーを含む、請求項８に記載の複数の映像ラインを利用した映像整合システム。
【請求項１０】
前記前方プロセッサーは、
前記第１及び第２映像レジスターから出力される前記第１及び第２ピクセルデータの差から整合コストを計算する絶対値計算機、
前記マルチラインプロセシング用活性信号からマルチラインコストを決定するマルチラインコストメモリ、
第１加算器でフィードバックされる値に前記整合コスト及び前記マルチラインコストを加算する第２加算器、
前記第２加算器の出力及び隣接する前方プロセッサーのコストのうちの最も小さなコストを出力し、前記最も小さなコストの経路を示す前記第１決定値を出力するマルチプレクサー、
前記マルチプレクサーの出力に前記マルチラインコストを加算する第１加算器、
前記第１加算器の出力を保存するコストレジスター、そして
前記コストレジスターの出力にオクルージョン値を加算して隣接する前方プロセッサーに出力する第３加算器を含む、請求項９に記載の複数の映像ラインを利用した映像整合システム。
【請求項１１】
前記前方プロセッサーの初期化時に、０番目の前方プロセッサーを除く全ての前方プロセッサーのコストレジスター値が最大値に設定される、請求項１０に記載の複数の映像ラインを利用した映像整合システム。
【請求項１２】
前記マルチラインコストメモリは、前記マルチラインプロセシング用活性信号のプロセシングエレメント位置及び前記前方プロセッサーの位置の差から前記マルチラインコストを計算する、請求項１０に記載の複数の映像ラインを利用した映像整合システム。
【請求項１３】
前記後方プロセッサーは、
隣接する後方プロセッサーの活性信号及び前記後方プロセッサーのジマルチプレクサーから出力される活性信号の入力を受けるＯＲゲート、
前記ＯＲゲートの出力を保存する活性レジスター、
前記活性レジスターから入力を受けたデータを前記スタックから出力される前記第１決定値によって出力するジマルチプレクサー、
前記第１決定値を受信して前記活性レジスターの出力によって前記第２決定値を出力する３状態バッファー、
前記活性レジスターから活性ビット値の入力を受けて保存し、マルチライン活性信号を出力するＤバッファーを含む、請求項９に記載の複数の映像ラインを利用した映像整合システム。
【請求項１４】
前記後方プロセッサーの初期化時に、０番目の後方プロセッサーの活性レジスターが活性化され、他の後方プロセッサーの活性レジスターは不活性化される、請求項１３に記載の複数の映像ラインを利用した映像整合システム。
【請求項１５】
前記前方プロセッサーは、現在入力される前記第１及び第２ピクセルデータを処理し、前記後方プロセッサーは、直前の映像ラインに対して前記前方プロセッサーが処理した前記第１決定値の入力を受けて前記第２決定値を出力する、請求項９に記載の複数の映像ラインを利用した映像整合システム。
【請求項１６】
前記複数の前方プロセッサーが処理された後に前記複数の後方プロセッサーが処理され、
前記複数の前方プロセッサー及び前記複数の後方プロセッサーは各々順次に処理される、請求項９に記載の複数の映像ラインを利用した映像整合システム。
【請求項１７】
入力される前記第１及び第２ピクセルデータに相当する前記エピポーラ線上の映像ラインが全映像で奇数番目であるか偶数番目であるかによって、前記第１及び第２映像レジスターに各々入力される前記第１及び第２ピクセルデータの入力順が異なる、請求項５に記載の複数の映像ラインを利用した映像整合システム。
【請求項１８】
前記複数のプロセシングエレメントから出力される前記第２決定値の合計が両眼差の値として出力される、請求項５に記載の複数の映像ラインを利用した映像整合システム。
【請求項１９】
左側及び右側カメラから各々入力される左側及び右側ピクセルデータを受信する段階、
エピポーラ線上の映像ラインの左側及び右側ピクセルデータを配列して各々複数の第１及び第２映像レジスターに順次に出力する段階、
複数の前方プロセッサーが前記複数の第１及び第２映像レジスターから各々出力される前記左側及び右側ピクセルデータから所定のコストを決定し、前記所定のコストを決定する第１決定値を追跡する段階、そして
複数の後方プロセッサーが隣接する映像ラインに対する前記第１決定値から最適の決定値である第２決定値を出力する段階を含み、
前記前方プロセッサー及び前記後方プロセッサーが同時に処理される、複数の映像ラインを利用した映像整合方法。
【請求項２０】
左側及び右側カメラから各々入力される左側及び右側ピクセルデータを受信する段階、
エピポーラ線上の映像ラインの左側及び右側ピクセルデータを配列して各々複数の第１及び第２映像レジスターに順次に出力する段階、
複数の前方プロセッサーが前記複数の第１及び第２映像レジスターから各々出力される前記左側及び右側ピクセルデータから所定のコストを決定し、前記所定のコストを決定する第１決定値を追跡する段階、そして
複数の後方プロセッサーが隣接する映像ラインに対する前記第１決定値から最適の決定値である第２決定値を出力する段階を含み、
前記複数の前方プロセッサーが処理された後に前記複数の後方プロセッサーが処理され、
前記複数の前方プロセッサー及び前記複数の後方プロセッサーは各々順次に処理される、複数の映像ラインを利用した映像整合方法。
【請求項２１】
前記前方プロセッサーは隣接する前方プロセッサーとコスト値を送受信し、前記後方プロセッサーは隣接する後方プロセッサーと活性信号を送受信する、請求項１９または２０に記載の複数の映像ラインを利用した映像整合方法。
【請求項２２】
前記活性信号は、マルチラインコストを計算するためのマルチラインプロセシング用活性信号と隣接するプロセシングエレメントの後方プロセシング用活性信号とを含む、請求項２１に記載の複数の映像ラインを利用した映像整合方法。
【請求項２３】
前記前方プロセッサーで前記第１決定値が追跡される段階は、
前記第１及び第２ピクセルデータの差から整合コストを計算する段階、
前記マルチラインプロセシング用活性信号からマルチラインコストを決定する段階、
フィードバック値に前記整合コスト及び前記マルチラインコストを加算する段階、
前記加算された値及び隣接する前方プロセッサーのコストのうちの最も小さなコストを出力し、前記最も小さなコストの経路を示す前記第１決定値を出力する段階、
前記最も小さなコストに前記マルチラインコストを加算して、この値をフィードバックする段階、そして
前記最も小さなコストに前記マルチラインコストが加算された値にオクルージョン値を加算して隣接する前方プロセッサーに出力する段階を含む、請求項２２に記載の複数の映像ラインを利用した映像整合方法。
【請求項２４】
前記前方プロセッサーは、前記マルチラインプロセシング用活性信号のプロセシングエレメントの位置及び前記前方プロセッサー位置の差から前記マルチラインコストを計算する、請求項２３に記載の複数の映像ラインを利用した映像整合方法。
【請求項２５】
前記後方プロセッサーから前記第２決定値が出力される段階は、
隣接する後方プロセッサーの活性信号及びフィードバックされる活性信号をＯＲ演算する段階、
前記ＯＲ演算された値を前記第１決定値によってジマルチプレクシングする段階、
前記ＯＲ演算された値によって前記第１決定値から前記第２決定値を決定する段階、そして
前記ＯＲ演算された値を保存し、マルチライン活性信号を出力する段階を含む、請求項２２に記載の複数の映像ラインを利用した映像整合方法。
【請求項２６】
前記複数の後方プロセッサーに出力される前記第２決定値が合算されて両眼差の値が出力される、請求項１９または２０に記載の複数の映像ラインを利用した映像整合方法。
【請求項２７】
前記第２決定値の合計から幾何学的に存在可能性のない経路を除いて前記第２決定値を圧縮する段階をさらに含む、請求項１９または２０に記載の複数の映像ラインを利用した映像整合方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の映像ラインを利用した映像整合方法及びそのシステムに関し、特に、多重エピポーラ映像整合のためのシストリックアーキテクチャーのステレオ整合方法及びそのシステムに関する。
【背景技術】
【０００２】
ステレオ整合方法は、一対の２次元映像から３次元の空間情報を再創出する方法である。図１に示したように、左側及び右側映像がエピポーラ線（epipolar line）上の映像ラインから三次元空間上と同じ位置（X、Y、Z）に対応する左右のピクセルを捜し出す方法である。ここで対応するピクセルの対に対する両眼差（d）は次のように定義される。
d=xr-xl
【０００３】
両眼差は距離情報を含み、このような両眼差から計算された幾何学的特性を深さ（depth）と言う。したがって、入力映像からリアルタイムで両眼差の値を計算すれば、観測空間の三次元距離情報及び形態情報を測定することができる。このようなステレオ整合方法については、非特許文献１に基本的な概念が開示されている。そして、ステレオ整合方法を実現したシステムとして、本出願人が出願した特許文献１がある。
【０００４】
しかしながら、このような従来の技術では、図１２に示したようにm番目の左右側エピポーラ線上の映像ライン（gm１、gmr）のみを独立的に演算するため、垂直方向にノイズが激しくなる。つまり、両眼差映像の垂直方向への両眼差の値がノイズの影響によって正確に現れないという問題点がある。その結果、図１３Ａの左側映像及び図１３Ｂの右側映像が入力された時、図１３Ｄのようにノイズが激しい映像が現れる。
【非特許文献１】Umesh R. Dhond and J.K.Aggarwal, “Structure from Stereo - a review”, IEEE Transactions on Systems, Man, and Cybernetics, 19(6), November/December 1989, p.553-572
【特許文献１】米国特許出願公開第２００２／００２５０７５号明細書
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明が目的とする技術的課題は、垂直方向への両眼差ノイズを減少させることができる映像整合方法を提供することにある。
【課題を解決するための手段】
【０００６】
このような課題を解決するために、本発明は、隣接する映像ラインの両眼差を利用する。
【０００７】
本発明の一つの特徴による複数の映像ラインを利用した映像整合システムは、第１及び第２カメラから入力される映像をデジタル信号に変換して第１及び第２ピクセルデータを出力する映像処理部、そして同一エピポーラ線上の第１及び第２ピクセルデータから所定のコストを決定し、所定のコストを決定する第１決定値を追跡し、直前のエピポーラ線上の第１及び第２ピクセルデータから追跡された第１決定値を利用して最適の第２決定値を出力する映像整合部を含む。
【０００８】
この時、第１及び第２ピクセルデータは、各々同一エピポーラ線上の左側及び右側映像ラインのピクセルデータであるのが好ましい。
【０００９】
映像整合部は、第１及び第２ピクセルデータを各々再配列して出力する第１及び第２入力バッファー、そして第１及び第２入力バッファーから各々第１及び第２ピクセルデータを受信して第１及び第２決定値を追跡するプロセシングエレメントアレイ部を含むことができる。また、映像整合部は、第２決定値の入力を受けて圧縮するエンコーダをさらに含み、エンコーダは、差動コーディング方式で圧縮して幾何学的に存在可能性のない経路を除いて処理することができる。
【００１０】
プロセシングエレメントアレイ部は、第１ピクセルデータを順次に受信する複数の第１映像レジスター、第２ピクセルデータを順次に受信する複数の第２映像レジスター、そして第１及び第２映像レジスターから各々第１及び第２ピクセルデータを受信して第１及び第２決定値を追跡する複数のプロセシングエレメントを含むことができる。プロセシングエレメントは、隣接するプロセシングエレメントとコスト値及び活性信号を送受信するのが好ましい。そして、活性信号は、マルチラインコストを計算するためのマルチラインプロセシング用活性信号と隣接するプロセシングエレメントの後方プロセシング用活性信号とを含むのが好ましい。
【００１１】
プロセシングエレメントは、第１及び第２ピクセルデータ及びマルチラインプロセシング用活性信号からコスト値を決定し、決定したコストの経路を示す第１決定値を計算する前方プロセッサー、第１決定値を保存するスタック、そして隣接するエピポーラ線上に対する第１決定値及び後方プロセシング用活性信号から第２決定値を計算する後方プロセッサーを含むことができる。
【００１２】
前方プロセッサーの初期化時に、０番目の前方プロセッサーを除く全ての前方プロセッサーのコストレジスター値が最大値に設定されるのが好ましい。マルチラインコストメモリは、マルチラインプロセシング用活性信号のプロセシングエレメントの位置及び前方プロセッサーの位置の差からマルチラインコストを計算することができる。後方プロセッサーの初期化時に、０番目の後方プロセッサーの活性レジスターが活性化され、他の後方プロセッサーの活性レジスターは不活性化されるのが好ましい。
【００１３】
入力される第１及び第２ピクセルデータに相当するエピポーラ線上の映像ラインが全映像で奇数番目であるか偶数番目であるかによって、第１及び第２映像レジスターに各々入力される第１及び第２ピクセルデータの入力順が異なるのが好ましい。
【００１４】
本発明の他の特徴による複数の映像ラインを利用した映像整合方法は、左側及び右側カメラから各々入力される左側及び右側ピクセルデータを受信する段階、エピポーラ線上の映像ラインの左側及び右側ピクセルデータを配列して各々複数の第１及び第２映像レジスターに順次に出力する段階、複数の前方プロセッサーが複数の第１及び第２映像レジスターから各々出力される左側及び右側ピクセルデータから所定のコストを決定し、所定のコストを決定する第１決定値を追跡する段階、そして、複数の後方プロセッサーが隣接する映像ラインに対する第１決定値から最適の決定値である第２決定値を出力する段階を含み、前方プロセッサー及び後方プロセッサーが同時に処理される。
【００１５】
本発明の他の特徴による複数の映像ラインを利用した映像整合方法は、左側及び右側カメラから各々入力される左側及び右側ピクセルデータを受信する段階、エピポーラ線上の映像ラインの左側及び右側ピクセルデータを配列して各々複数の第１及び第２映像レジスターに順次に出力する段階、複数の前方プロセッサーが複数の第１及び第２映像レジスターから各々出力される左側及び右側ピクセルデータから所定のコストを決定し、所定のコストを決定する第１決定値を追跡する段階、そして、複数の後方プロセッサーが隣接する映像ラインに対する第１決定値から最適の決定値である第２決定値を出力する段階を含み、複数の前方プロセッサーが処理された後に複数の後方プロセッサーが処理され、複数の前方プロセッサー及び複数の後方プロセッサーは各々順次に処理される。
【発明の効果】
【００１６】
本発明によれば、両眼差の計算を高速で処理することができ、また、高い圧縮率で両眼差をエンコーディングすることができる。そして、複数のエピポーラ線上の映像ライン間の幾何学的制約条件を利用して垂直方向のノイズを除去することができるので、安定した距離映像を得ることができる。
【発明を実施するための最良の形態】
【００１７】
以下、添付した図面を参照して、本発明の実施例について、本発明が属する技術分野における通常の知識を有する者が容易に実施することができるように詳細に説明する。しかし、本発明は多様な相異した形態で実現することができ、ここで説明する実施例に限定されない。図面では、本発明を明確に説明するために、説明と関係のない部分は省略した。明細書全体にかけて類似した部分については、同一な図面符号を付けた。
【００１８】
それでは、本発明の実施例による複数の映像ラインを利用した映像整合方法及びそのシステムについて、図面を参照して詳細に説明する。
【００１９】
まず、図２乃至図７を参照して、本発明の第１実施例による複数の映像ラインを利用した映像整合システムについて詳しく説明する。
【００２０】
図２は本発明の第１実施例による映像整合システムの概略的なブロック図であり、図３は本発明の第１実施例による映像整合システムのマルチライン映像整合部の概略的なブロック図である。図４は図３の入力バッファーの詳細ブロック図であり、図５は図３のマルチライン映像整合部の概略的なブロック図である。図６及び図７は各々図５の前方プロセッサー及び後方プロセッサーの詳細ブロック図である。
【００２１】
図２に示したように、本発明の第１実施例による映像整合システムは、左側カメラ１１０、右側カメラ１２０、映像処理部２００、マルチライン映像整合部３００、及び使用者システム４００を含む。左側及び右側カメラ１１０、１２０は、各々被写体の左側及び右側映像を撮影し、撮影した映像信号を映像処理部２００に伝達する。映像処理部２００は、左側及び右側カメラ１１０、１２０から各々入力される左側及び右側映像信号をデジタル信号に変換して出力する。マルチライン映像整合部３００は、映像処理部２００からの映像デジタル信号から決定値を計算して両眼差の値を出力し、使用者システム４００は、マルチライン映像整合部３００から出力される両眼差による距離映像の入力で受けて必要な用途に使用する。
【００２２】
図３に示したように、マルチライン映像整合部３００は、２つの入力バッファー３１０、プロセシングエレメントアレイ部３２０、及びエンコーダ３３０を含む。２つの入力バッファー３１０は、各々左側及び右側映像信号（ピクセルデータ）を受信し、制御信号によってピクセルデータを再配列して出力する。プロセシングエレメントアレイ部３２０は、隣接する映像ラインの両眼差の値から入力されるピクセルデータの両眼差を計算し、エンコーダ３３０は、両眼差の値を適切なフォーマットに変換して出力する。
【００２３】
このようなマルチライン映像整合部３００は、エピポーラ線上の左側及び右側映像ラインのピクセルデータの入力を順次に受けて演算し、両眼差の値を計算して出力するが、両眼差を出力する過程は一対の映像の全てがエピポーラ線上の映像ラインに対して反復的に行われる。
【００２４】
図４に示したように、図２の入力バッファー３１０は、マルチプレクサー３１１、２つのラインバッファー３１２、３１３、ジマルチプレクサー３１４、２つのアドレス生成部３１５、３１６、及び制御部３１７を含む。マルチプレクサー３１１は、入力されるピクセルデータを制御部３１７からの制御信号によって２つのラインバッファー３１２、３１３のうちの一つに出力する。２つのアドレス生成部３１５、３１６は、制御部３１７からの制御信号によって各々ラインバッファー３１２、３１３内のデータのうからの出力するデータを選択する。ジマルチプレクサー３１４は、制御部３１７からの制御信号によってラインバッファー３１２、３１３から出力されるピクセルデータのうちの一つを選択して出力する。
【００２５】
そして、図３及び５に示したように、図２のプロセシングエレメントアレイ部３２０は、N/２個の左側映像レジスター３２１（l２〜lN/２）、N/２個の右側映像レジスター（rN/２-１〜r１）、N個の前方プロセッサー３２３（fp１〜fpN）、N個の後方プロセッサー３２４（bp１〜bpN）、及びN個のスタック３２５を含む。前方プロセッサー３２３、後方プロセッサー３２４、及びスタック３２５を合わせてプロセシングエレメントという。このようなプロセシングエレメントは、指定された最大両眼差まで線状アレイ形態で存在し、各プロセシングエレメントは、隣接するプロセシングエレメントと情報を交換しながら並列に処理される。このような構造は、プロセシングエレメントの個数に制限なく最大速度で動作する。
【００２６】
左側映像レジスターl１には同期信号によって左側映像エピポーラ線上のピクセルデータが入力バッファー３１０を経て一つずつ入力され、左側映像レジスターl１に入力されたピクセルデータは左側映像レジスター（l２〜lN/２）に順次に伝達される。同様に、右側映像レジスターrN/２には右側映像エピポーラ線上のピクセルデータが入力バッファー３１０を経て一つずつ入力され、右側映像レジスターrN/２に入力されたピクセルデータは右側映像レジスター（rN/２-１〜r１）に順次に伝達される。そして、図３に示したように、一つの左側映像レジスターln及び右側映像レジスターrnは、２つの前方プロセッサー（fpj、fpj-１）に対応して形成されている。
【００２７】
以下、図６及び図７を参照して、図５のプロセシングエレメントアレイ部３２０のうちのj（１≦j≦N）番目のプロセシングエレメントを例に挙げて詳細に説明する。
【００２８】
図６に示したように、図５の前方プロセッサー３２３fpjは、絶対値計算機３２３a、マルチラインコストメモリ３２３b、加算器３２３c、３２３d、マルチプレクサー３２３e、コストレジスター３２３f、加算器３２３g、３２３h、及び制御部３２３iを含む。このような前方プロセッサー３２３は、クロック（t）によってエピポーラ線上の左側及び右側映像ラインのピクセルデータの入力を受けて決定値を計算し、スタック３２５に保存する。
【００２９】
絶対値計算機３２３aは、左側映像のピクセルデータ（Ln）（gl(t-j-1)/2）及び右側映像のピクセルデータ（Rn）（gr(t+j-1)/2）の差の絶対値から整合コストを計算し、ピクセルデータは左側及び右側映像レジスター３２１、３２２から入力を受ける。マルチラインコストメモリ３２３bは、マルチラインプロセシング用活性信号
【数１】
2006079584.tif 000003
からマルチラインコストを決定して出力する。
マルチラインコストメモリ３２３bは、隣接するプロセシングエレメントの活性信号に対しては小さなコストを出力し、遠くにあるプロセシングエレメントの活性信号に対しては大きなコストを出力するが、これについては図７で詳しく説明する。
【００３０】
加算器３２３cは、コストレジスター３２３fでフィードバックされる２クロック直前のコスト（Ｕj(t-2)）とマルチラインコストメモリ３２３bから出力されるマルチラインコストとを加算し、加算器３２３dは、加算器３２３cで加算された値に絶対値計算機３２３aの整合コストを加算する。
そして、マルチプレクサー３２３cは、制御部３２３hからの制御信号によって（j+１）番目の前方プロセッサー３２３及び（j-１）番目の前方プロセッサー３２３から出力される１クロック直前のコスト（Ｕj+1(t-1)＋γ、Ｕj-1(t-1)＋γ）及び加算器３２３dの出力（Ｕj(t-1)）のうちの最も小さなコストを出力すると同時に、最も小さなコストの経路を示す決定値（Ｖt,j）を出力する。加算器３２３gは、マルチプレクサー３２３cの出力にマルチラインコストメモリ３２３bのマルチラインコストを加算して現在のクロックのコスト（Ｕj(t)）として出力し、出力されたコスト（Ｕj(t)）はコストレジスター３２３fに保存される。そして、加算器３２３hは、コストレジスター３２３fから出力される２クロック直前のコスト（Ｕj(t-2)）にオクルージョンコスト（γ）を加算して、隣接する（j+１）番目及び（j-１）番目の前方プロセッサー３２３に出力する。
【００３１】
図７に示したように、図５の後方プロセッサー３２４bpjは、ＯＲゲート３２４a、１ビット活性レジスター３２４b、Ｄバッファー３２４c、ジマルチプレクサー３２４d、３状態バッファー３２４e、及び制御部３２４fを含む。このような後方プロセッサー３２４は、スタック３２５から読み込んだ決定値を演算して両眼差の値を計算し、クロックに応じて出力する。
【００３２】
ＯＲゲート３２４aは、隣接する（j+１）番目及び（j-１）番目の後方プロセッサー３２４の活性信号（aj+1(t-1)δ(1＋Ｖt-1,j+1)、aj-1(t-1)δ(1−Ｖt-1,j-1)）及びジマルチプレクサー３２４dでフィードバックされる活性信号（ａj(t)δ(Ｖt,j)）の入力を受ける。ＯＲゲート３２４aの出力が制御部３２３fの制御によって２クロック後の活性ビット値（ａj(t＋2)）として活性レジスター３２４bに保存される。そして、活性レジスター３２４bの出力（ａj(t)）はＤバッファー３２４cに保存され、Ｄバッファー３２４cは、kクロック後に活性ビット値を出力する。このようなＤバッファー３２４cは、活性ビット値の入力を受けてマルチライン活性信号として出力するが、マルチラインプロセシング用活性信号の入力を受ける前方プロセッサー３２３に入力される時に後方プロセッサーに同期させるために使用される。
【００３３】
ジマルチプレクサー３２４dは、活性レジスター３２４bから入力されるデータを前方プロセッサー３２３でスタック３２５を経て入力される決定値（Ｖt,j）によってジマルチプレクシングし、これにより、後方プロセシング用活性信号（ａj(t)δ(1−Ｖt,j)、ａj(t)δ(1＋Ｖt,j)）を隣接する後方プロセッサー３２４に出力すると同時に、活性信号（ａj(t)δ(Ｖt,j)）をＯＲゲート３２４aにフィードバックする。そして、３状態バッファー３２４eは、スタック３２５から決定値（Ｖt,j）を受信して活性レジスター３２４bの出力によって両眼差の増減を示す最適の決定値（Ｖ*t,j）を出力する。このような３状態バッファー３２４eは、活性ビット値（ａj(t)）が‘１'である場合には入力値をそのまま出力し、‘１'でない場合にはハイインピーダンス状態になるのでいずれの値も出力しない。
【００３４】
また、後方プロセッサーbpjから出力される決定値（Ｖ*t,j）を全て加算すると両眼差の値になるが、このような両眼差の値は決定値の変化量で徐々に変化するので、差動コーディング方式で圧縮して圧縮率を高めることができる。つまり、エンコーダ３３０は、決定値（Ｖ*t,j）を加算した形態である両眼差の値を出力せずに、決定値（Ｖ*t,j）をそのまま出力することができる。
【００３５】
しかし、決定値（Ｖ*t,j）は、パスの変化分を示すために、パスの変化なし、上方向、下方向の３つの値を有するので、各々２ビットで‘００’、‘０１’、‘１０’で示すことができ、‘１１’はダミービットである。この時、２つの決定値（Ｖ*t,j、Ｖ*t-1,j）は４ビットが必要であるが、‘０１１０’及び‘１００１’は幾何学的に存在可能性がほとんどない場合であるので‘００００’と同一視することができる。したがって、表１に示したように、不必要なデータ（dummy data）を処理してこれをインコーディングすれば、２つの決定値を３ビットのみで表現することができる。また、一つの数をフラッグ（flag）に割り当てて使用することができるので、フラッグデータも許容される。
【表１】
2006079584.tif 000004
【００３６】
以下、図８及び図９を参照して、前記複数の映像ラインを利用した映像整合システムにおける映像整合方法について詳細に説明する。そして、本発明の第１実施例では、クロックが０から２Nまで行われる時、０から（N-１）までのプロセシングエレメントが並列に処理されるが、図８及び図９では、説明の便宜上、j番目のプロセシングエレメントを基準にして説明する。
【００３７】
本発明の第１実施例では、前記ラインの両眼差の値をプロセシングエレメント内で直接利用して後方プロセッサーbpj及び前方プロセッサーfpjが同時に処理されるため、エピポーラ線上の映像ラインの全映像で奇数番目であるか偶数番目であるかによって、ハードウェアの動作が変化する。これは、決定値の出力によってマルチラインプロセシング用活性信号が変化するので、マルチラインプロセシング用活性信号と前方プロセッサーを同期させるためである。したがって、入力バッファー３１０は、映像ラインのインデックスが奇数であるか偶数であるかによって、ピクセルデータの順を異にして整列しなければならない。
【００３８】
以下、偶数番目の映像ラインのピクセルデータについては図７の流れ図を参照して説明し、奇数番目の映像ラインのピクセルデータについては図８の流れ図を参照して説明する。
【００３９】
図８及び図９は各々本発明の第１実施例による映像整合システムが偶数及び奇数番目の映像ラインのピクセルデータを処理する流れ図である。
まず、図８を参照して、偶数番目の映像ラインのピクセルデータが入力される場合について説明する。まず、０クロック（i=０）でプロセシングエレメントが初期化され、初期化される時のコスト（Uj（０）、j∈[１、N]）は[数２]の通りである（S８１０）。
【数２】
2006079584.tif 000005
【００４０】
次に、図４の下端の左側映像レジスターl１及び上端の右側映像レジスターrN/２は、入力バッファー３１１、３１２から左右側映像ピクセルデータの入力を順次に受け、全ての左側及び右側映像レジスターl１〜lN/２、r１〜rN/２は隣接する映像レジスターl１〜lN/２、r１〜rN/２にピクセルデータを伝達する（S８２０）。
【００４１】
一方、プロセシングエレメントは、現在のクロックi及びプロセシングエレメントの位置jの合計（i+j）が奇数であるか偶数であるかによって、動作が変化する。そして、前方プロセッサーfpjは現在入力される映像ラインのピクセルデータを処理し、後方プロセッサーbpjは、前方プロセッサーfpjで処理された決定値をスタック３２５から読み込んで処理する。そして、以下では、後方プロセッサーbpjが前方プロセッサーfpjより速く処理されるとして説明する。このようにすれば、後方プロセッサーbpjがスタック３２５から読み込んだ位置に前方プロセッサーfpjが決定値を使うことができるので、直前のラインの決定値及び現在のラインの決定値が一つのスタックを共有することができる。したがって、現在のクロックiでの前方プロセッサーfpjの出力であるコスト及び決定値を各々Ｕj(i)及びＶi、jで表示し、後方プロセッサーbpjの出力である活性化信号及び両眼差を各々ａj(i+1)及び
【数３】
2006079584.tif 000006
で表示する。
【００４２】
以下、このようなプロセシングエレメントの動作を、（i+j）が奇数である場合及び偶数である場合に分けて詳細に説明する。
【００４３】
まず、前方プロセッサーfpjの制御部３２３i及び後方プロセッサーbpjの制御部３２４fは、クロックi及びプロセシングエレメントの位置jの合計が奇数であるか偶数であるかを判断する（S８３０）。
【００４４】
この時、（i+j）が奇数である場合には、図６の制御部３２３iはＵj(t-１)をコストとして出力するように制御し（S８４１）、（i+j）が偶数である場合には、Ｕj（t）をコストとして出力するように制御する（S８４２）。
【００４５】
詳しく説明すれば、（i+j）が奇数である場合には、前方プロセッサーfpjの加算器３２３dの出力（Ｕj(t-１)）がコストになるので、iクロックでのコスト（Ｕj(i)）は直前のクロックのコスト（Ｕj(i)-１）に左右ピクセルデータの差を加算した値にマルチラインコストが加算された値になる。マルチラインコストは［数４］のように計算され、後方プロセッサー３２４で計算されたマルチラインプロセシング用活性信号（ａj+p(i)）の入力を受信して、|p|がλより小さければη|p|を出力し、大きければηλを出力する。このようなマルチラインコストは、入力された活性信号（ａj+p(i)）のプロセシングエレメントの位置（j+p）及び前方プロセッサーfpjの位置jの差を考慮してコストを計算して出力するため、整合時に制約条件として使用される。
【数４】
2006079584.tif 000007
ここで、λはマルチラインプロセシング用活性信号（ａj+p(i)）が近辺のプロセシングエレメントに伝達される範囲を示し、ηはマルチラインコスト値のスケールを決定する。
【００４６】
このようなマルチラインコストを考慮すれば、iクロックでのコスト（Ｕj(i)）は［数５］のように表現することができ、この時の決定値（Ｖi、j）は０になる。
【数５】
2006079584.tif 000008
【００４７】
そして、（i+j）が偶数である場合には、前方プロセッサーfpjの加算器３２３gの出力（Ｕj(t-１)）がコストになる。したがって、iクロックでのコスト（Ｕj(i)）はＵj+1(i-1)＋γ、Ｕj(i-1)、Ｕj-1(i-1)＋γのうちの最小値にコストメモリ３２３bのマルチラインコストを加算した値で、［数６］のように表現することができる。そして、決定値（Ｖi、j）は最も小さなコストの経路を示す値で、［数７］のように表現することができる。
【数６】
2006079584.tif 000009
【数７】
2006079584.tif 000010
ここで、
【数８】
2006079584.tif 000011
は、f（x）を最小とするパラメター（x）を出力する関数である。そして、以下では、決定値（Ｖi,j）のうちの偶数番目の映像ラインのピクセルデータに対して前方プロセッサーから出力される決定値をＶbi,jで表示し、奇数番目の映像ラインのピクセルデータに対して前方プロセッサーから出力される決定値をＶai,jで表示する。
このようにS８４１及びS８４２によって決定された決定値（Ｖi,j）は、スタック３２５に保存される。
【００４８】
一方、後方プロセッサーbpjは、直前のラインに対して前方プロセッサーfpjで処理された決定値（Ｖa2N-i,j）をスタック３２５から読み込む。そして、図７の制御部３２４fの制御によって活性レジスター３２４bの出力が活性信号（ａj(i+1)）になる。つまり、図７のＯＲゲート３２４aは、現在の後方プロセッサーbpjが直前のクロックに対して処理した活性信号（ａj(i)δ(Ｖa2N-i,j)）及び隣接する後方プロセッサー（bpj-１、bpj+１）が直前のクロックに対して処理した活性信号（ａj-1(i)δ(1−Ｖa2N-i,j-1)、ａj+1(i)δ(1＋Ｖa2N-i,j+1)）をＯＲ演算して出力する。この結果が現在のクロックでの活性信号（ａj(i+1)）になり、［数９］のように表現することができる。
【数９】
2006079584.tif 000012
【００４９】
３状態バッファー３２４eは、直前のラインに対する決定値（Ｖa2N-i,j）をスタック３２５から受信して活性ビット（ａj(i+1)）によって両眼差の増減を示す最適の決定値（Ｖa2N-i,j）を出力し、この決定値（Ｖa2N-i,j）の合計が両眼差（［数３］）になる。３状態バッファー３２４eは、活性ビット値（ａj(i+1)）がハイ（‘１’）である場合には、決定値（Ｖa2N-i,j）を出力する。そして、活性ビット値（ａj(i+1)）がロー（‘０’）である場合には、３状態バッファー３２４eの出力信号がハイインピーダンス状態になるので他の後方プロセッサーの出力を妨害しないようになる。したがって、両眼差は［数１０］のように表現することができる。
【数１０】
2006079584.tif 000013
【００５０】
次に、現在のクロックiが２Nでなければ（S８５０）、クロックiが１増加して（S８６０）、同一な過程（S８２０、S８３０、S８４１、S８４２）が繰り返される。このようにして、現在の映像ラインのピクセルデータに対して両眼差を計算する。
【００５１】
次に、図９を参照して、奇数番目の映像ラインのピクセルデータが入力される場合について説明する。まず、０クロック（i=０）でプロセシングエレメントが初期化され、初期化される時のコスト（Ｕj(０)、j∈[１、N]）は［数２］の通りである（S９１０）。
【００５２】
次に、図４の下端の左側映像レジスターl１及び上端の右側映像レジスターrN/２は、入力バッファー３１１、３１２から左側及び右側映像ラインのピクセルデータの入力を順次に受け、全ての左側及び右側映像レジスター（l１〜lN/２、r１〜rN/２）は隣接する映像レジスター（l１〜lN/２、r１〜rN/２）にピクセルデータを伝達する（S９２０）。この時、入力されるピクセルデータは、左側及び右側映像ピクセルデータの順序が再配列されてｇlN-(i-j-1)/2、ｇrN-(i-j-1)/2になる。
【００５３】
そして、図８と同様に、（i+j）が奇数であるか偶数であるかを判断して（S９３０）、（i+j）が奇数である場合には、図６の制御部３２３iはＵj(t-１)をコストとして出力するように制御し（S９４１）、（i+j）が偶数である場合には、Ｕj（t）をコストとして出力するように制御する（S９４２）。
【００５４】
したがって、（i+j）が奇数である場合には、前方プロセッサーfpjの加算器３２３dの出力（Ｕj(t-１)）がコストになるので、コスト（Ｕj(i)）は［数１１］のようになり、この時の決定値（Ｖai,j）は０になる。
【数１１】
2006079584.tif 000014
【００５５】
そして、（i+j）が偶数である場合には、前方プロセッサーfpjの加算器３２３gの出力（Ｕj(t-１)）がコストになるので、コスト（Ｕj(i)）及び決定値（Ｖai,j）は各々［数１２］及び［数１３］のように表現することができる。
【数１２】
2006079584.tif 000015
【数１３】
2006079584.tif 000016
このようにS９４１及びS９４２を通じて決定された決定値（Ｖai,j）は、スタック３２５に保存される。
【００５６】
そして、図８と同様に、後方プロセッサーbpjは、隣接する映像ラインに対して前方プロセッサーfpjで処理された決定値（Ｖb2N-i,j）をスタック３２５から読み込んで活性ビット（ａj(i+1)）を出力する。後方プロセッサーbpjの３状態バッファー３２４eは、直前のラインに対する決定値（Ｖb2N-i,j）をスタック３２５から受信して、活性ビット値（ａj(i+1)）によって両眼差の増減を示す最適の決定値（Ｖb2N-i,j）を出力し、この決定値（Ｖb2N-i,j）の合計が両眼差（［数３］）になる。このような活性ビット値（ａj(i+1)）及び両眼差（［数３］）は各々［数１４］及び［数１５］で表現される。
【数１４】
2006079584.tif 000017
【数１５】
2006079584.tif 000018
【００５７】
次に、現在のクロックiが２Nでなければ（S９５０）、クロックiが１増加して（S９６０）、同一な過程（S９２０、S９３０、S９４１、S９４２）が繰り返される。このようにして、現在の映像ラインのピクセルデータに対して両眼差を計算する。
【００５８】
以上で、本発明の第１実施例による映像整合方法について、映像整合システムで処理される過程を中心に説明したが、これとは異なって、ソフトウェア的に処理することもできる。以下では、ソフトウェア的に処理される本発明の第２実施例による映像整合方法について、詳細に説明する。本発明の第２実施例による映像整合方法では、プロセシングエレメントが並列に処理されずに直列に処理される。
【００５９】
図１０は本発明の第２実施例による映像整合方法を示す流れ図である。
図１０に示したように、まず、［数２］に示したように全てのプロセシングエレメントを初期化し（S１０１０）、処理するプロセシングエレメントの位置jを０に設定する（S１０２０）。
【００６０】
次に、左側及び右側映像レジスター（l１〜lN/２、r１〜rN/２）から左側及び右側映像ラインのピクセルデータ（ｇl(t-j-1)/2、ｇr(t+j-1)/2）が前方プロセッサーfpjに入力される（S１０３０）。そして、（i+j）が奇数であるか偶数であるかを判断し（S１０４０）、現在のプロセシングエレメントの位置j及び直前のラインに対する両眼差の値（dold(i)）の差とλとの大きさを比較する（S１０５０）。
【００６１】
（i+j）が奇数であり、|j−dold(i)|がλと同一であるか小さければ［数１６］のようにコスト（Ｕj(i)）を計算し（S１０６１）、（i+j）が奇数であり、|j−dold(i)|がλより大きければ［数１７］のようにコスト（Ｕj(i)）を計算する（S１０６２）。そして、（i+j）が奇数である場合には、決定値（Ｖi、j）を０に設定する。
【数１６】
2006079584.tif 000019
【数１７】
2006079584.tif 000020
【００６２】
この時、（i+j）が偶数であり、|j−dold(i)|がλと同一であるか小さければ各々［数１８］及び［数１９］のようにコスト（Ｕj(i)）及び決定値（Ｖi、j）を計算し（S１０６３）、（i+j）が偶数であり、|j−dold(i)|がλより大きければ各々［数２０］及び［数２１］のようにコスト（Ｕj(i)）及び決定値（Ｖi、j）を計算する（S１０６４）。
【数１８】
2006079584.tif 000021
【数１９】
2006079584.tif 000022
【数２０】
2006079584.tif 000023
【数２１】
2006079584.tif 000024
【００６３】
このようにS１０６１、S１０６２、S１０６３、またはS１０６４を通じてコスト（Ｕj(i)）及び決定値（Ｖi、j）を計算した後、現在の前方プロセッサーfpjの位置jが（N-１）番目であるかを判断する（S１０７０）。jが（N-１）番目でなければjを１増加させた後（S１０７１）、S１０３０から繰り返す。
【００６４】
そして、jが（N-１）番目である場合、つまり全ての前方プロセッサーfpjに対してコスト（Ｕj(i)）及び決定値（Ｖi、j）を計算した場合には、現在のクロックiが２Nであるかを判断する（S１０８０）。現在のクロックiが２Nでない場合には、クロックiを１増加させて（S１０８１）、S１０２０から繰り返す。そして、現在のクロックiが２Nである場合、つまり全てのクロックに対して前方プロセッサーfpjの処理を終えた場合には、後方プロセッサーbpjの処理をする。
【００６５】
次に、後方プロセッサーの処理では、直前の段階で設定された両眼差dj及び［数２２］に示す決定値
【数２２】
2006079584.tif 000025
を利用して現在の段階における両眼差dj-１を［数２３］のように計算して、dold(i)＝diにdold(i)値をアップデートする（S１１１０）。
【数２３】
2006079584.tif 000026
その後、現在のクロックiが０であるかを判断して（S１１２０）、０でなければクロックiを１減少させた後（S１１３０）、S１１１０から繰り返す。
【００６６】
このように、本発明の実施例によると、図１１に示したように隣接する複数のエピポーラ線上の映像ライン（gm１l-gm２l、gm１r-gm２r）の入力を受けて、映像整合時にライン間の制約条件を利用して両眼差のエラーを減少させる。つまり、物体の表面が比較的緩やかであるという仮定下で、両眼差映像の映像ライン間での距離データである両眼差の値の差を映像整合時に制約条件として使用する。したがって、本発明の実施例によると、図１３Ａ及び図１３Ｂの左右側映像が入力される場合に、図１３Ｃに示したように、図１３Ｄに比べてノイズが多く除去されることが分かる。
【００６７】
以上で、本発明の好ましい実施例について詳細に説明したが、本発明の権利範囲はこれに限定されるわけではなく、請求の範囲で定義している本発明の基本概念を利用した当業者の多様な変形及び改良形態も本発明の権利範囲に属する。
【図面の簡単な説明】
【００６８】
【図１】ステレオ整合の概念図である。
【図２】本発明の第１実施例による映像整合システムの概略的なブロック図である。
【図３】本発明の第１実施例による映像整合システムのマルチライン映像整合部の概略的なブロック図である。
【図４】図３の入力バッファーの詳細ブロック図である。
【図５】図３のマルチライン映像整合部の概略的なブロック図である。
【図６】図５の前方プロセッサー及び後方プロセッサーの詳細ブロック図である。
【図７】図５の前方プロセッサー及び後方プロセッサーの詳細ブロック図である。
【図８】本発明の第１実施例による映像整合システムが偶数及び奇数番目の映像ラインのピクセルデータを処理する流れ図である。
【図９】本発明の第１実施例による映像整合システムが偶数及び奇数番目の映像ラインのピクセルデータを処理する流れ図である。
【図１０】本発明の第２実施例による映像整合方法で前方プロセシング及び後方プロセシングを示す流れ図である。
【図１１】本発明の実施例による映像整合方法を概略的に示した図面である。
【図１２】従来の技術による映像整合方法を概略的に示した図面である。
【図１３Ａ】入力される左側及び右側映像を示す図面である。
【図１３Ｂ】入力される左側及び右側映像を示す図面である。
【図１３Ｃ】図１１及び図１２の方法で図１３Ａ及び図１３Ｂの映像を処理した結果を示す図面である。
【図１３Ｄ】図１１及び図１２の方法で図１３Ａ及び図１３Ｂの映像を処理した結果を示す図面である。
【符号の説明】
【００６９】
１１０  左側カメラ
１２０  右側カメラ
２００  映像処理部
３００  マルチライン映像整合部
３１０  入力バッファー
３１１  マルチプレクサー
３１２、３１３  ラインバッファー
３１４  ジマルチプレクサー
３１５、３１６  アドレス生成部
３１７  制御部
３２０  プロセシングエレメントアレイ部
３２１  右側映像レジスター
３２２  左側映像レジスター  
３２３  Ｎ個の前方プロセッサー
３２３ａ  絶対値計算機
３２３ｂ  マルチラインコストメモリ
３２３ｃ、３２３ｄ、３２３ｇ、３２３ｈ  加算機
３２３ｅ  マルチプレクサー
３２３ｆ  コストレジスター
３２３ｉ  制御部
３２４  Ｎ個の後方プロセッサー
３２４ａ  ＯＲゲート
３２４ｄ  ジマルチプレクサー
３２４ｂ  活性レジスター
３２４ｃ  Ｄバッファー
３２４ｅ  ３状態バッファー
３２４ｆ  制御部
３２５  スタック
３３０  エンコーダ
４００  使用者システム
【図１】
2006079584.tif 000027
【図２】
2006079584.tif 000028
【図３】
2006079584.tif 000029
【図４】
2006079584.tif 000030
【図５】
2006079584.tif 000031
【図６】
2006079584.tif 000032
【図７】
2006079584.tif 000033
【図８】
2006079584.tif 000034
【図９】
2006079584.tif 000035
【図１０】
2006079584.tif 000036
【図１１】
2006079584.tif 000037
【図１２】
2006079584.tif 000038
【図１３Ａ】
2006079584.tif 000039
【図１３Ｂ】
2006079584.tif 000040
【図１３Ｃ】
2006079584.tif 000041
【図１３Ｄ】
2006079584.tif 000042