画像処理装置、画像処理方法、および、記録媒体
【課題】ステレオ法による画像処理において、処理を高精度化および高速化する。
【解決手段】カメラにより撮像された画像１乃至５は、画像入力部１００−１乃至１００−５にそれぞれ入力され、内蔵されているメモリに格納された後、カメラのレンズの収差をキャンセルするような順序で読み出され、各カメラの特性に起因する濃淡値の相違が補正される。ＳＡＤ２００−１乃至２００−４は、１つのカメラから出力される基準画像と、その他２つのカメラから出力される参照画像との間で画素値の差分の絶対値を算出し、ＳＳＡＤ回路３００−１乃至３００−４は、各ＳＡＤ回路からの出力をブロックマッチング処理し、２次近似部４００−１乃至４００−４は、各ＳＳＡＤ回路から出力されたデータを２次近似し、最小値選択部５００，６００および結果メモリ７００は、２次近似部４００−１乃至４００−４から出力されるデータの最小値を選択する。
【解決手段】カメラにより撮像された画像１乃至５は、画像入力部１００−１乃至１００−５にそれぞれ入力され、内蔵されているメモリに格納された後、カメラのレンズの収差をキャンセルするような順序で読み出され、各カメラの特性に起因する濃淡値の相違が補正される。ＳＡＤ２００−１乃至２００−４は、１つのカメラから出力される基準画像と、その他２つのカメラから出力される参照画像との間で画素値の差分の絶対値を算出し、ＳＳＡＤ回路３００−１乃至３００−４は、各ＳＡＤ回路からの出力をブロックマッチング処理し、２次近似部４００−１乃至４００−４は、各ＳＳＡＤ回路から出力されたデータを２次近似し、最小値選択部５００，６００および結果メモリ７００は、２次近似部４００−１乃至４００−４から出力されるデータの最小値を選択する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置、画像処理方法、および、記録媒体に関し、特に、ステレオ法により対象点までの距離を算定する画像処理装置、画像処理方法、および、記録媒体に関する。
【背景技術】
【０００２】
ステレオ法は、複数の視点から撮像した画像を用いて、対象点までの距離を三角測量の原理を用いて測定する技法である。
【０００３】
図６は、従来における、ステレオ法を用いて対象点までの処理を測定する画像処理装置の構成例を示す図である。
【０００４】
この図において、メモリ１−１乃至メモリ１−５は、図示せぬカメラ１乃至カメラ５によって撮像された１フレーム分の画像を格納し、所定の順序で画素データを読み出して出力するようになされている。なお、カメラ１乃至５のうちの、例えば、カメラ１は基準カメラとされ、この基準カメラの画像と他のカメラ（参照カメラ）の画像を比較することにより、マッチング処理を行い、マッチング処理の結果に応じて視差を算定するようになされている。
【０００５】
ＳＡＤ（Sum of Absolute Difference）回路２は、メモリ１−１から出力された基準画像と、その他のメモリ１−２乃至１−５から出力された各画像との間で画素値の差分の絶対値を算出する。例えば、ＳＡＤ回路２は、メモリ１−１とメモリ１−２、メモリ１−１とメモリ１−３、メモリ１−１とメモリ１−４、および、メモリ１−１とメモリ１−５の間で画素値の差分の絶対値を算出して出力する。
【０００６】
ＳＳＡＤ（Sum of SAD）回路３は、ＳＡＤ回路２から出力される各カメラ間の画素差分の絶対値をもとにして、各カメラ間のブロックマッチング処理を行った結果を出力するようになされている。
【０００７】
最小値検出部４は、ＳＳＡＤ回路３から出力される結果の中から、最小値を検出して出力する。
【０００８】
２次近似部５は、最小値検出部４から出力される最小値とその前後の値を２次関数により近似（補間）し、更に高い精度で最小値を算出するようになされている。
【０００９】
メモリ６は、２次近似部５から出力される最小値を記憶するようになされている。
【００１０】
次に、以上の従来例の動作について説明する。
【００１１】
いま、カメラ１（図示せず）が中央に配置され、その他のカメラ２乃至５（図示せず）がそれを囲むように配置されているとする。そのとき、カメラ１から出力された画像は、基準画像としてメモリ１−１に格納される。また、その他のカメラ２乃至５から出力された画像は、メモリ１−２乃至１−５にそれぞれ格納される。
【００１２】
ＳＡＤ回路２は、メモリ１−１から出力された基準画像と、他のメモリ１−２乃至１−５から出力された参照画像とでペアを形成し、各ペアの間で画素の差分の絶対値を算出して出力する。
【００１３】
ＳＳＡＤ回路３は、ＳＡＤ回路２から出力された各ペア毎の画素の差分の絶対値から所定の画素ブロック（例えば、５×５ブロックなど）のマッチング処理を行う。即ち、ＳＳＡＤ回路３は、画素ブロック単位で差分を計算し、得られた結果を最小値検出部４に供給する。
【００１４】
最小値検出部４は、ＳＳＡＤ回路３から出力される差分値の中から、最小値を検出して、２次近似部５に供給する。
【００１５】
２次近似部５は、最小値検出部４から出力された最小値と、その前後２点のデータを２次曲線により近似（補間）して、更に精度の高い最小値データを生成し、出力する。
【００１６】
メモリ６は、２次近似部５から出力されたデータを記憶する。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
ところで、ステレオ法に基づく処理では、基準となる画像の各画素が、参照画像のどこに対応するかという対応点問題を解く必要がある。この対応点問題を解く方法としては、マッチング処理が一般的に用いられている。即ち、基準画像と参照画像を比較することにより、最もマッチング（類似度）が高い部分が対応点として相互に関連づけられる。
【００１８】
マッチング処理により対応点を探索する場合、探索範囲はキャリブレーション（校正）により予め決定される。この探索範囲は、理論的には、エピポーララインと呼ばれる直線に沿っている存在する筈であるが、実際には、レンズの収差などにより曲線となる場合が多い。
【００１９】
そこで、そのような問題を解決するために、探索点を全て列挙し、それらをルックアップテーブルに予め格納しておくことが考えられる。しかしながら、そのようにして作成したルックアップテーブルを使用した場合においても、各画素の濃淡値がレンズの種類の相違や、絞りの違いなどにより、各カメラ間で異なる場合が生じ、そのような場合には正確にマッチング処理を行うことができないと言う課題があった。
【００２０】
そこで、そのような問題点を解決するために、入力画像を４ビットに圧縮し、かつ、濃淡値の違いを吸収するために、濃淡値が大きく変化する部分を強調する処理を行うことが提案されている（参考文献「“A Stereo Machine for Video-rate Dense Depth Mapping and Its New Applications”Takeo Kanade, Atsushi Yoshida, Kazuo Oda, Hiroshi Kano and Masaya Tanaka, Proceedings of 15th Computer Vision and Pattern Recognition Conference(CVPR). June 18-20, 1996, San Francisco.」）。
【００２１】
しかしながら、このような方法では、原画像の微妙な濃淡の差が無視されるため、微妙な濃淡の差をマッチング処理の結果に反映することができない。従って、濃淡値が大きく変化する部分では、正しいマッチング処理の結果が得られる一方で、濃淡の変化が小さい部分では、正しいマッチング処理の結果が得られないという課題があった。
【００２２】
また、マッチング処理の結果得られた距離データは、高い精度で求めることが望ましいので、前述の従来例では、対応点を探索した結果得られた最小値データを２次曲線により補間し、更に精度の高いデータを求めていた。
【００２３】
しかしながら、この補間処理を実行するためには計算コストが高くつく除算を行う必要があることから、従来においては、回路規模を縮小するために、ブロックマッチングによって得られた結果の最小値（最小値検出部４の出力）に対してのみ補間処理が実施されていた。このような方法では、ハードウエア規模は縮小できるものの、最小値が出力された後に補間処理を実行する必要があることから、処理全体に遅延が生じ、その結果として処理を高速化することが困難となるという課題があった。
【００２４】
本発明は、以上のような状況に鑑みてなされたものであり、正確なマッチング処理を可能とするとともに、処理を高速化することを可能とするものである。
【課題を解決するための手段】
【００２５】
請求項１に記載の画像処理装置は、各撮像装置から出力される画像を記憶する第１の記憶手段と、記憶手段に記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶手段と、第２の記憶手段に記憶された順序に応じて、第１の記憶手段に記憶されている画素データを読み出す読み出し手段と、読み出し手段によって読み出された画素データの階調を変換する変換手段とを備えることを特徴とする。
【００２６】
請求項４に記載の画像処理方法は、各撮像装置から出力される画像を記憶する第１の記憶ステップと、記憶ステップに記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶ステップと、第２の記憶ステップに記憶された順序に応じて、第１の記憶ステップに記憶されている画素データを読み出す読み出しステップと、読み出しステップによって読み出された画素データの階調を変換する変換ステップとを備えることを特徴とする。
【００２７】
請求項５に記載の記録媒体は、各撮像装置から出力される画像を記憶する第１の記憶ステップと、記憶ステップに記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶ステップと、第２の記憶ステップに記憶された順序に応じて、第１の記憶ステップに記憶されている画素データを読み出す読み出しステップと、読み出しステップによって読み出された画素データの階調を変換する変換ステップとを備えるプログラムを記録する。
【００２８】
請求項１に記載の画像処理装置、請求項４に記載の画像処理方法、および、請求項５に記載の記録媒体においては、各撮像装置から出力される画像を記憶し、記憶された画像を構成する画素データを読み出す順序を記憶し、記憶された順序に応じて、記憶されている画素データを読み出し、読み出された画素データの階調を変換する。例えば、各撮像装置から出力される画像を記憶し、記憶された画像を構成する画素データを、各撮像装置のレンズの収差をキャンセルするように読み出す順序を記憶し、記憶された順序に応じて、記憶されている画素データを読み出し、読み出された画素データの階調が各カメラ間で誤差を生じないように変換する。
【発明の効果】
【００２９】
本発明によれば、ステレオ法において、対象までの距離を正確に算出することが可能となる。
【発明を実施するための最良の形態】
【００３０】
図１は、本発明の実施の形態の構成例を示すブロック図である。
【００３１】
この図において、画像入力部１００−１（第１の入力手段）、および、画像入力部１００−２乃至１００−５（第２の入力手段）は、図示せぬカメラ１乃至５から出力された画像をそれぞれ格納する。そして、レンズの収差をキャンセルするように所定の順序で読み出されるとともに、ルックアップテーブルに応じて画素の値が階調変換されて出力されるようになされている。なお、この画像入力部１００−１乃至１００−５の詳細な構成例については図２を参照して後述する。
【００３２】
ここで、カメラ１から出力される画像は基準画像とされており、また、その他のカメラ２乃至５から出力される画像は参照画像とされている。
【００３３】
ＳＡＤ回路２００−１乃至２００−４（マッチング手段）は、基準画像と２つの参照画像との間で画素の差分の絶対値を計算するようになされている。例えば、ＳＡＤ回路２００−１は、基準画像（メモリ１００−１から出力される画像）と、カメラ２およびカメラ３から出力された画像（メモリ１００−２およびメモリ１００−３から出力される画像）を入力し、これらの間で画素の差分の絶対値を演算するようになされている。なお、ＳＡＤ回路２００−１乃至２００−４の詳細については図３を参照して後述する。
【００３４】
ＳＳＡＤ回路３００−１乃至３００−４（マッチング手段）は、例えば、５×５個の画素から構成される画素ブロック単位で差分値を算出して出力するようになされている。なお、このＳＳＡＤ回路３００−１乃至３００−４の詳細は、図４を参照して後述する。
【００３５】
２次近似部４００−１乃至４００−４（補間手段）は、ＳＳＡＤ回路３００−１乃至３００−４からそれぞれ出力される３つの差分値の入力を受け、それら３点を通る２次曲線を求めるとともに、その２次曲線の最小値を求めて出力するようになされている。なお、この２次曲線近似部４００−１乃至４００−４の詳細については、図５を参照して後述する。
【００３６】
最小値選択部５００（検出手段）は、２次近似部４００−１乃至４００−４からそれぞれ出力されるデータの中から最小値を選択して出力するようになされている。
【００３７】
最小値選択部６００（検出手段）は、最小値選択部５００から出力された新たな最小値と、結果メモリ７００（検出手段）に格納されているそれまでの最小値とを比較し、小さい方を選択して出力するようになされている。
【００３８】
結果メモリ７００は、最小値選択部６００から出力された最小値を一時的に格納するとともに、格納されているそれまでの最小値を最小値選択部６００に供給するようになされている。
【００３９】
なお、この最小値選択部６００と結果メモリ７００が協働することにより、最小値選択部５００から出力される一連のデータの中から最小値を有するデータが選択されて、結果メモリ７００に格納されることになる。
【００４０】
次に、図２を参照して図１に示す画像入力部１００の詳細な構成例について説明する。
【００４１】
この図において、メモリ１０１（第１の記憶手段、読み出し手段）は、カメラから出力された画像データをカウンタ１０２から出力されるアドレスデータに対応するアドレスに格納するようになされている。また、格納されたデータを読み出す場合には、メモリ１０３（第２の記憶手段）から出力されるアドレスデータに対応するアドレスからデータを読み出して出力するようになされている。セレクタ１０６は、画像データをメモリ１０１に入力する場合には、カウンタ１０２側へ接続され、また、画像データをメモリ１０１から出力する場合には、メモリ１０３側へ接続されるようになされている。
【００４２】
カウンタ１０２は、メモリ１０１に対して画像データを読み込む場合に、アドレスデータを出力するようになされており、例えば、小さい順にアドレスデータを出力するようになされている。
【００４３】
カウンタ１０４は、アドレスデータを所定の順序で出力するようになされている。メモリ１０３は、カウンタ１０４から出力されたアドレスデータを、レンズの収差をキャンセルするように変換して出力するようになされている。なお、メモリ１０３に格納されているアドレス変換用のデータは、キャリブレーションを行う際に対応点を手がかりとして生成される。
【００４４】
また、メモリ１０３に格納されているデータには有効ビットが付加されており、各カメラ毎に予め求められている探索範囲が画像の領域を越える場合には、この有効ビットは“０”とされているので、メモリ１０３から出力される有効ビット信号は“０”の状態となる。なお、探索範囲が画像の領域内である場合には、メモリ１０３から出力される有効ビット信号は“１”の状態とされる。
【００４５】
ルックアップテーブル１０５（変換手段）は、階調変換を行うためのデータが格納されており、入力されたデータに対応するアドレスからデータが読み出されて出力されるようになされている。なお、このルックアップテーブル１０５に格納されているデータは、カメラ１乃至カメラ５により同一のパターンを撮像した場合に、全てのカメラの出力が同一になるようなデータが格納されている。従って、このルックアップテーブル１０５により各カメラの特性のばらつきが補正される。
【００４６】
続いて、図３を参照して、図１に示すＳＡＤ回路２００の詳細な構成例について説明する。なお、ＳＡＤ回路２００−１乃至２００−４は全て同様の構成とされているので、以下では、ＳＡＤ回路２００−１を例に挙げて説明する。
【００４７】
この図において、減算回路２０１−１は、カメラ１から出力された基準画像の画素値から、カメラ２から出力された参照画像の画素値を減算して出力するようになされている。減算回路２０１−２は、カメラ１から出力された基準画像の画素値から、カメラ３から出力された参照画像の画素値を減算して出力するようになされている。
【００４８】
絶対値回路２０２−１は、減算回路２０１−１から出力されるデータの絶対値を演算し、得られた結果を出力するようになされている。また、絶対値回路２０２−２は、減算回路２０１−２から出力されるデータの絶対値を演算し、得られた結果を出力するようになされている。
【００４９】
セレクタ２０３−１は、カメラ２の有効ビットが“１”の状態である場合には、絶対値回路２０２−１の出力を選択して出力するようになされている。一方、カメラ２の有効ビットが“０”の状態である場合には、絶対値回路２０２−２の出力を選択して出力するようになされている。
【００５０】
セレクタ２０３−２は、カメラ３の有効ビットが“１”の状態である場合には、絶対値回路２０２−２の出力を選択して出力するようになされている。一方、カメラ３の有効ビットが“０”の状態である場合には、絶対値回路２０２−１の出力を選択して出力するようになされている。
【００５１】
加算回路２０４は、セレクタ２０３−１の出力と、セレクタ２０３−２の出力を加算して出力するようになされている。
【００５２】
セレクタ２０６は、カメラ２またはカメラ３の少なくとも一方の有効ビットが“１”の状態である場合には、加算回路２０４の出力を選択して出力する。また、双方の有効ビットが“０”の場合には、最大値回路２０５から出力されるデータ（例えば、５１１）を選択して出力するようになされている。
【００５３】
最後に、図４を参照して、図１に示すＳＳＡＤ回路３００の詳細な構成例について説明する。
【００５４】
この図において、ディレイライン３０１は、入力された画素値の差分の絶対値をブロックマッチングのブロックの大きさ×１ラインの画素数分だけ遅延して出力するようになされている。
【００５５】
減算回路３０２は、ディレイライン３０１を経由していないデータから、ディレイライン３０１から出力されたデータを減算し、得られた結果を出力するようになされている。
【００５６】
加算回路３０３は、減算回路３０２から出力されたデータと、メモリ３０４から出力されたデータを加算して出力するようになされている。メモリ３０４は、加算回路３０３から出力されたデータを１ライン分遅延した後、出力するようになされている。
【００５７】
ディレイライン３０５は、加算回路３０３の出力を１ラインを構成する画素数分だけ遅延して出力するようになされている。減算回路３０６は、加算回路３０３の出力からディレイライン３０５の出力を減算して出力するようになされている。
【００５８】
加算回路３０７は、減算回路３０６の出力とメモリ３０８の出力とを加算して出力するようになされている。メモリ３０８は、加算回路３０７の出力をブロックマッチングのブロックの大きさ分だけ遅延して出力するようになされている。
【００５９】
次に、以上の実施の形態の動作について説明する。
【００６０】
図１に示す実施の形態に、カメラ１乃至カメラ５から出力される画像が入力されると、画像入力部１００−１乃至１００−５は、画像を一旦格納した後、所定の順序で読み出すとともに、階調変換を施して出力する。
【００６１】
即ち、図２に示すメモリ１０１に対して画像データが供給されると、カウンタ１０２から出力されるアドレスデータに対応するアドレスに、データが逐次格納されていくことになる。なお、このような動作は、画像入力部１００−１乃至１００−５の全てにおいて実行され、カメラ１乃至５から出力された画像がメモリ１０１の所定のアドレスに逐次格納されることになる。また、このとき、セレクタ１０６は、カウンタ１０２側を選択している。
【００６２】
画像データの格納が終了すると、セレクタ１０６がメモリ１０３側に接続される。そして、カウンタ１０４からアドレスデータの出力が開始される。メモリ１０３は、カウンタ１０４から出力されたアドレスデータに対応するアドレスから所定のデータを読み出してメモリ１０１に供給する。メモリ１０３に格納されているデータは、各画素毎、かつ、各探索ディスパリティ毎に画像データを読み出すように設定されているので、その結果、探索するエピポーララインが非直線の場合でも対応でき、レンズの収差等を吸収することが可能となる。
【００６３】
また、メモリ１０３に格納されているデータには、前述のように有効ビットが付加されているので、各カメラ毎に求められている探索範囲が画像の領域を越えた場合には、有効ビットが“０”の状態とされる。また、探索範囲が画像の領域を越えていない場合には、同ビットは“１”の状態とされる。
【００６４】
メモリ１０１から出力された画像データは、ルックアップテーブル１０５に供給される。ルックアップテーブル１０５は、メモリ１０１から出力された画像データに対応するアドレスに格納されているデータを読み出して出力する。このルックアップテーブル１０５に格納されているデータは、各カメラの特性の相違に起因する階調の差を補正するように設定されているので、その結果、各カメラ間の明暗の相違などを吸収することができる。
【００６５】
このようにして、レンズの収差と各カメラの特性に対する補正処理が施された画像データは、画像入力部１００−１乃至１００−５から出力され、ＳＡＤ回路２００−１乃至２００−４に供給される。
【００６６】
ＳＡＤ回路２００−１乃至２００−４は、画像入力部１００−１乃至１００−５から出力された基準画像データと２つの参照画像データとの間で画素値の差分の絶対値を算出して出力する。なお、ＳＡＤ回路２００−１乃至２００−４において行われる演算は、有効ビットの値に応じて適宜変更される。
【００６７】
即ち、画像入力部１００−１から出力された補正処理が施された画像データは、減算回路２０１−１と減算回路２０１−２にそれぞれ供給される。また、画像入力部１００−２と画像入力部１００−３から出力された画像データは、それぞれ、減算回路２０１−１と減算回路２０１−２に供給される。
【００６８】
減算回路２０１−１は、基準画像の画素値から、参照画像であるカメラ２の画像の画素値を減算して出力する。また、減算回路２０１−２は、基準画像の画素値から、参照画像であるカメラ３の画像の画素値を減算して出力する。
【００６９】
絶対値回路２０２−１は、減算回路２０１−１の計算結果の絶対値を演算して出力する。また、絶対値回路２０２−２は、減算回路２０１−２の計算結果の絶対値を演算して出力する。その結果、絶対値回路２０２−１からは、参照画像である画像入力部１００−２からの画像と、基準画像である画像入力部１００−１からの画素の差分の絶対値が出力される。また、絶対値回路２０２−２からは、参照画像である画像入力部１００−３の画像と、基準画像である画像入力部１００−１からの画像の画素の差分の絶対値が出力されることになる。
【００７０】
セレクタ２０３−１は、カメラ２の探索範囲が画像の領域内にある場合には、有効ビットが“１”の状態とされるので、絶対値回路２０３−１の出力を選択して加算回路２０４に出力する。また、カメラ２の探索範囲が画像の領域を越えた場合には、有効ビットが“０”の状態とされるので、その場合には、セレクタ２０３−１は、絶対値回路２０２−２の出力を選択して加算回路２０４に出力する。
【００７１】
同様に、セレクタ２０３−２は、カメラ３の探索範囲が画像の領域内にある場合には、有効ビットが“１”の状態とされるので、絶対値回路２０３−２の出力を選択して、加算回路２０４に出力する。また、カメラ３の探索範囲が画像の領域を越えた場合には、有効ビットが“０”の状態とされるので、その場合には、セレクタ２０３−２は、絶対値回路２０２−１の出力を選択して加算回路２０４に出力する。
【００７２】
加算回路２０４は、セレクタ２０３−１と２０３−２の出力を加算して出力する。また、セレクタ２０６は、カメラ２とカメラ３の有効ビットの状態に応じて、加算回路２０４、または、最大値回路２０５の出力を選択して出力する。その結果、セレクタ２０６の出力は、カメラ２とカメラ３の有効ビットの状態に応じて以下のような出力を生ずることになる。
【００７３】
（１）双方の有効ビットが“１”（有効）の状態であれば、絶対値回路２０２−１と絶対値回路２０２−２がそのまま加算されて出力される。
（２）どちらか一方の有効ビットが“０”（無効）である場合には、有効である方の絶対値回路の出力が２倍されて出力される。
（３）双方の有効ビットが“０”である場合には、最大値回路２０５の出力（例えば、画素データが８ビットの場合には値５１１）が選択されて出力される。
【００７４】
ＳＡＤ回路２００−１乃至２００−４の出力は、ＳＳＡＤ回路３００−１乃至３００−４にそれぞれ供給される。
【００７５】
ＳＳＡＤ回路２００−１乃至２００−４は、例えば、５×５個の画素からなる画素ブロック単位でブロックマッチング処理を行い、得られた結果を出力する。
【００７６】
即ち、ＳＡＤ回路２００−１乃至２００−４から出力された画素の差分の絶対値（｜ａij−ｂij｜）は、減算回路３０２に供給されるとともに、ディレイライン３０１に供給され、ブロックマッチングの大きさ×１ラインの画素数分だけ遅延された後、減算回路３０２に供給される。
【００７７】
減算回路３０２は、ＳＡＤ回路の出力データから、ディレイライン３０１により遅延されたデータを減算して、加算回路３０３に出力する。
【００７８】
加算回路３０３は、メモリ３０４により遅延された１ライン分前のデータと減算回路３０２の出力とを加算して出力する。その結果、加算回路３０３からは、２次元ブロックマッチングの１次元処理が施されたデータ（Σi｜ａij−ｂij｜
）が出力されることになる。
【００７９】
ディレイライン３０５、減算回路３０６、加算回路３０７、および、メモリ３０８は、前段の回路と同様の処理を実行し、その結果、加算回路３０７からは、２次元のブロックマッチング処理が施されたデータ（ΣjΣi｜ａij−ｂij｜）が出力されることになる。
【００８０】
ＳＳＡＤ回路３００−１乃至３００−４から出力されたデータは、２次近似処理部４００−１乃至４００−４にそれぞれ供給される。
【００８１】
２次近似部４００−１乃至４００−４は、ＳＳＡＤ回路３００−１乃至３００−４から出力されたあるデータＳ2と、それに前後するデータＳ1，Ｓ3を２次曲
線で補間して、更に正確な最小値データを得る。
【００８２】
図５は、２次近似部４００の動作を説明する図である。
【００８３】
この図に示すように、ＳＳＡＤ回路３００の出力ｄ1乃至ｄ3が入力されると、２次近似回路４００は、ｄ1乃至ｄ3を結ぶ曲線を以下の２次式により生成する。
【００８４】
Ｓ1＝ａ・ｄ12＋ｂ・ｄ1＋ｃ ・・・（１）
Ｓ2＝ａ・ｄ22＋ｂ・ｄ2＋ｃ ・・・（２）
Ｓ3＝ａ・ｄ32＋ｂ・ｄ3＋ｃ ・・・（３）
【００８５】
ここで、ｄ1＝−１，ｄ2＝０，ｄ3＝１とすると、以上の式（１）乃至（３）
は、次のようになる。
【００８６】
Ｓ1＝ａ−ｂ＋ｃ ・・・（４）
Ｓ2＝ｃ ・・・（５）
Ｓ3＝ａ＋ｂ＋ｃ ・・・（６）
【００８７】
これを解くと、最小値ｄは、以下の式により表すことができる。
【００８８】
ｄ＝（Ｓ1−Ｓ3）／｛２×（Ｓ1−２・Ｓ2＋Ｓ3）｝ ・・・（７）
【００８９】
ここで、ｄの範囲は、以下のように表すことができる。
【００９０】
−０．５≦ｄ≦０．５ ・・・（８）
【００９１】
従って、各項を２倍すると、以下の式を得る。
【００９２】
−１≦２・ｄ≦１ ・・・（９）
【００９３】
式（９）に式（７）を代入すると、以下の式を得る。
【００９４】
−１≦（Ｓ1−Ｓ3）／（Ｓ1−２・Ｓ2＋Ｓ3）≦１ ・・・（１０）
【００９５】
通常、式（７）に示すような除算を含む演算を行う場合、ハードウエアの計算コストは大きくなる。しかしながら、ここでは、求める精度が小数点以下３乃至４ビットと少なく、また、得られる結果の範囲が式（１０）に示すように明確になっている。即ち、２次曲線近似で求める正確な最小値を示す位置は、求まった最小値の位置から±０．５の範囲にある。従って、除算の代わりに減算を用いて計算を行うことができることから、計算を大幅に簡略化するとともに、ハードウエア資源を削減することができる。
【００９６】
なお、以上の構成では、ＳＳＡＤ回路３００から出力される全てのデータに対して２次近似が施されることになるが、最終的には、最小値選択部５００により最小値のみが選択されるので問題は生じない。
【００９７】
このようにして２次近似されたデータは、最小値選択部５００に供給される。最小値選択部５００は、２次近似部４００−１乃至４００−４から出力されたデータから最小値を選択し、最小値選択部６００に対して出力する。
【００９８】
最小値選択部６００は、結果メモリ７００に格納されているそれまでの最小値と、最小値選択部５００から新たに出力された値とを比較し、より小さい方を選択して出力する。結果メモリ７００は、最小値選択部６００から出力された値を保持する。その結果、結果メモリ７００には、全てのカメラペア（各ＳＡＤ回路に入力されている画像に対応するカメラの組み合わせ）から得られたデータのうち、最小のデータが選択されて格納されることになる。
【００９９】
このような最小のデータは、マッチング度が最も高いデータであるので、そのデータを用いることにより、最も精度の高い視差を求めることが可能となる。
【０１００】
以上のような実施の形態によれば、ＳＳＡＤ回路３００の出力を２次近似部４００により２次近似した後で、最小値選択部５００により最小値を選択するようにしたので、装置をパイプライン化し、また、並列分散処理を行うことが可能となる。従って、演算を高速に実行することが可能となる。
【０１０１】
また、メモリ１０３を設けて、データを非直線的に読み出すことができるようにしたので、レンズの収差の影響をキャンセルすることが可能となる。更に、ルックアップテーブル１０５を設け、各カメラの特性の相違に起因する濃淡値の誤差を補正するようにしたので、結果として測定精度を向上させることが可能となる。
【０１０２】
なお、以上の実施の形態においては、５台のカメラを用いて測定を行うようにしたが、本発明はこのような場合にのみ限定されるものではないことは勿論である。
【０１０３】
また、明細書中において、伝送媒体は、ＦＤ，ＣＤ−ＲＯＭなどの情報記録媒体の他、インターネット、ディジタル衛星などのネットワーク伝送媒体も含まれる。
【図面の簡単な説明】
【０１０４】
【図１】本発明の実施の形態の構成例を示すブロック図である。
【図２】図１に示す画像入力部１００の詳細な構成例を示すブロック図である。
【図３】図１に示すＳＡＤ回路２００の詳細な構成例を示すブロック図である。
【図４】図１に示すＳＳＡＤ回路３００の詳細な構成例を示すブロック図である。
【図５】図１に示す２次近似部４００の処理を説明する図である。
【図６】従来の画像処理装置の構成例を示すブロック図である。
【符号の説明】
【０１０５】
１００−１ 画像入力部（第１の入力手段）， １００−２乃至１００−５ 画像入力部（第２の入力手段）， １０１ メモリ（第１の記憶手段、読み出し手段）， １０３ メモリ（第２の記憶手段）， １０５ ルックアップテーブル（変換手段）， ２００−１乃至２００−４ ＳＡＤ回路（マッチング手段）， ３００−１乃至３００−４ ＳＳＡＤ回路（マッチング手段）， ５００， ６００ 最小値検出部（検出手段）， ７００ 結果メモリ（検出手段）
【技術分野】
【０００１】
本発明は、画像処理装置、画像処理方法、および、記録媒体に関し、特に、ステレオ法により対象点までの距離を算定する画像処理装置、画像処理方法、および、記録媒体に関する。
【背景技術】
【０００２】
ステレオ法は、複数の視点から撮像した画像を用いて、対象点までの距離を三角測量の原理を用いて測定する技法である。
【０００３】
図６は、従来における、ステレオ法を用いて対象点までの処理を測定する画像処理装置の構成例を示す図である。
【０００４】
この図において、メモリ１−１乃至メモリ１−５は、図示せぬカメラ１乃至カメラ５によって撮像された１フレーム分の画像を格納し、所定の順序で画素データを読み出して出力するようになされている。なお、カメラ１乃至５のうちの、例えば、カメラ１は基準カメラとされ、この基準カメラの画像と他のカメラ（参照カメラ）の画像を比較することにより、マッチング処理を行い、マッチング処理の結果に応じて視差を算定するようになされている。
【０００５】
ＳＡＤ（Sum of Absolute Difference）回路２は、メモリ１−１から出力された基準画像と、その他のメモリ１−２乃至１−５から出力された各画像との間で画素値の差分の絶対値を算出する。例えば、ＳＡＤ回路２は、メモリ１−１とメモリ１−２、メモリ１−１とメモリ１−３、メモリ１−１とメモリ１−４、および、メモリ１−１とメモリ１−５の間で画素値の差分の絶対値を算出して出力する。
【０００６】
ＳＳＡＤ（Sum of SAD）回路３は、ＳＡＤ回路２から出力される各カメラ間の画素差分の絶対値をもとにして、各カメラ間のブロックマッチング処理を行った結果を出力するようになされている。
【０００７】
最小値検出部４は、ＳＳＡＤ回路３から出力される結果の中から、最小値を検出して出力する。
【０００８】
２次近似部５は、最小値検出部４から出力される最小値とその前後の値を２次関数により近似（補間）し、更に高い精度で最小値を算出するようになされている。
【０００９】
メモリ６は、２次近似部５から出力される最小値を記憶するようになされている。
【００１０】
次に、以上の従来例の動作について説明する。
【００１１】
いま、カメラ１（図示せず）が中央に配置され、その他のカメラ２乃至５（図示せず）がそれを囲むように配置されているとする。そのとき、カメラ１から出力された画像は、基準画像としてメモリ１−１に格納される。また、その他のカメラ２乃至５から出力された画像は、メモリ１−２乃至１−５にそれぞれ格納される。
【００１２】
ＳＡＤ回路２は、メモリ１−１から出力された基準画像と、他のメモリ１−２乃至１−５から出力された参照画像とでペアを形成し、各ペアの間で画素の差分の絶対値を算出して出力する。
【００１３】
ＳＳＡＤ回路３は、ＳＡＤ回路２から出力された各ペア毎の画素の差分の絶対値から所定の画素ブロック（例えば、５×５ブロックなど）のマッチング処理を行う。即ち、ＳＳＡＤ回路３は、画素ブロック単位で差分を計算し、得られた結果を最小値検出部４に供給する。
【００１４】
最小値検出部４は、ＳＳＡＤ回路３から出力される差分値の中から、最小値を検出して、２次近似部５に供給する。
【００１５】
２次近似部５は、最小値検出部４から出力された最小値と、その前後２点のデータを２次曲線により近似（補間）して、更に精度の高い最小値データを生成し、出力する。
【００１６】
メモリ６は、２次近似部５から出力されたデータを記憶する。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
ところで、ステレオ法に基づく処理では、基準となる画像の各画素が、参照画像のどこに対応するかという対応点問題を解く必要がある。この対応点問題を解く方法としては、マッチング処理が一般的に用いられている。即ち、基準画像と参照画像を比較することにより、最もマッチング（類似度）が高い部分が対応点として相互に関連づけられる。
【００１８】
マッチング処理により対応点を探索する場合、探索範囲はキャリブレーション（校正）により予め決定される。この探索範囲は、理論的には、エピポーララインと呼ばれる直線に沿っている存在する筈であるが、実際には、レンズの収差などにより曲線となる場合が多い。
【００１９】
そこで、そのような問題を解決するために、探索点を全て列挙し、それらをルックアップテーブルに予め格納しておくことが考えられる。しかしながら、そのようにして作成したルックアップテーブルを使用した場合においても、各画素の濃淡値がレンズの種類の相違や、絞りの違いなどにより、各カメラ間で異なる場合が生じ、そのような場合には正確にマッチング処理を行うことができないと言う課題があった。
【００２０】
そこで、そのような問題点を解決するために、入力画像を４ビットに圧縮し、かつ、濃淡値の違いを吸収するために、濃淡値が大きく変化する部分を強調する処理を行うことが提案されている（参考文献「“A Stereo Machine for Video-rate Dense Depth Mapping and Its New Applications”Takeo Kanade, Atsushi Yoshida, Kazuo Oda, Hiroshi Kano and Masaya Tanaka, Proceedings of 15th Computer Vision and Pattern Recognition Conference(CVPR). June 18-20, 1996, San Francisco.」）。
【００２１】
しかしながら、このような方法では、原画像の微妙な濃淡の差が無視されるため、微妙な濃淡の差をマッチング処理の結果に反映することができない。従って、濃淡値が大きく変化する部分では、正しいマッチング処理の結果が得られる一方で、濃淡の変化が小さい部分では、正しいマッチング処理の結果が得られないという課題があった。
【００２２】
また、マッチング処理の結果得られた距離データは、高い精度で求めることが望ましいので、前述の従来例では、対応点を探索した結果得られた最小値データを２次曲線により補間し、更に精度の高いデータを求めていた。
【００２３】
しかしながら、この補間処理を実行するためには計算コストが高くつく除算を行う必要があることから、従来においては、回路規模を縮小するために、ブロックマッチングによって得られた結果の最小値（最小値検出部４の出力）に対してのみ補間処理が実施されていた。このような方法では、ハードウエア規模は縮小できるものの、最小値が出力された後に補間処理を実行する必要があることから、処理全体に遅延が生じ、その結果として処理を高速化することが困難となるという課題があった。
【００２４】
本発明は、以上のような状況に鑑みてなされたものであり、正確なマッチング処理を可能とするとともに、処理を高速化することを可能とするものである。
【課題を解決するための手段】
【００２５】
請求項１に記載の画像処理装置は、各撮像装置から出力される画像を記憶する第１の記憶手段と、記憶手段に記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶手段と、第２の記憶手段に記憶された順序に応じて、第１の記憶手段に記憶されている画素データを読み出す読み出し手段と、読み出し手段によって読み出された画素データの階調を変換する変換手段とを備えることを特徴とする。
【００２６】
請求項４に記載の画像処理方法は、各撮像装置から出力される画像を記憶する第１の記憶ステップと、記憶ステップに記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶ステップと、第２の記憶ステップに記憶された順序に応じて、第１の記憶ステップに記憶されている画素データを読み出す読み出しステップと、読み出しステップによって読み出された画素データの階調を変換する変換ステップとを備えることを特徴とする。
【００２７】
請求項５に記載の記録媒体は、各撮像装置から出力される画像を記憶する第１の記憶ステップと、記憶ステップに記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶ステップと、第２の記憶ステップに記憶された順序に応じて、第１の記憶ステップに記憶されている画素データを読み出す読み出しステップと、読み出しステップによって読み出された画素データの階調を変換する変換ステップとを備えるプログラムを記録する。
【００２８】
請求項１に記載の画像処理装置、請求項４に記載の画像処理方法、および、請求項５に記載の記録媒体においては、各撮像装置から出力される画像を記憶し、記憶された画像を構成する画素データを読み出す順序を記憶し、記憶された順序に応じて、記憶されている画素データを読み出し、読み出された画素データの階調を変換する。例えば、各撮像装置から出力される画像を記憶し、記憶された画像を構成する画素データを、各撮像装置のレンズの収差をキャンセルするように読み出す順序を記憶し、記憶された順序に応じて、記憶されている画素データを読み出し、読み出された画素データの階調が各カメラ間で誤差を生じないように変換する。
【発明の効果】
【００２９】
本発明によれば、ステレオ法において、対象までの距離を正確に算出することが可能となる。
【発明を実施するための最良の形態】
【００３０】
図１は、本発明の実施の形態の構成例を示すブロック図である。
【００３１】
この図において、画像入力部１００−１（第１の入力手段）、および、画像入力部１００−２乃至１００−５（第２の入力手段）は、図示せぬカメラ１乃至５から出力された画像をそれぞれ格納する。そして、レンズの収差をキャンセルするように所定の順序で読み出されるとともに、ルックアップテーブルに応じて画素の値が階調変換されて出力されるようになされている。なお、この画像入力部１００−１乃至１００−５の詳細な構成例については図２を参照して後述する。
【００３２】
ここで、カメラ１から出力される画像は基準画像とされており、また、その他のカメラ２乃至５から出力される画像は参照画像とされている。
【００３３】
ＳＡＤ回路２００−１乃至２００−４（マッチング手段）は、基準画像と２つの参照画像との間で画素の差分の絶対値を計算するようになされている。例えば、ＳＡＤ回路２００−１は、基準画像（メモリ１００−１から出力される画像）と、カメラ２およびカメラ３から出力された画像（メモリ１００−２およびメモリ１００−３から出力される画像）を入力し、これらの間で画素の差分の絶対値を演算するようになされている。なお、ＳＡＤ回路２００−１乃至２００−４の詳細については図３を参照して後述する。
【００３４】
ＳＳＡＤ回路３００−１乃至３００−４（マッチング手段）は、例えば、５×５個の画素から構成される画素ブロック単位で差分値を算出して出力するようになされている。なお、このＳＳＡＤ回路３００−１乃至３００−４の詳細は、図４を参照して後述する。
【００３５】
２次近似部４００−１乃至４００−４（補間手段）は、ＳＳＡＤ回路３００−１乃至３００−４からそれぞれ出力される３つの差分値の入力を受け、それら３点を通る２次曲線を求めるとともに、その２次曲線の最小値を求めて出力するようになされている。なお、この２次曲線近似部４００−１乃至４００−４の詳細については、図５を参照して後述する。
【００３６】
最小値選択部５００（検出手段）は、２次近似部４００−１乃至４００−４からそれぞれ出力されるデータの中から最小値を選択して出力するようになされている。
【００３７】
最小値選択部６００（検出手段）は、最小値選択部５００から出力された新たな最小値と、結果メモリ７００（検出手段）に格納されているそれまでの最小値とを比較し、小さい方を選択して出力するようになされている。
【００３８】
結果メモリ７００は、最小値選択部６００から出力された最小値を一時的に格納するとともに、格納されているそれまでの最小値を最小値選択部６００に供給するようになされている。
【００３９】
なお、この最小値選択部６００と結果メモリ７００が協働することにより、最小値選択部５００から出力される一連のデータの中から最小値を有するデータが選択されて、結果メモリ７００に格納されることになる。
【００４０】
次に、図２を参照して図１に示す画像入力部１００の詳細な構成例について説明する。
【００４１】
この図において、メモリ１０１（第１の記憶手段、読み出し手段）は、カメラから出力された画像データをカウンタ１０２から出力されるアドレスデータに対応するアドレスに格納するようになされている。また、格納されたデータを読み出す場合には、メモリ１０３（第２の記憶手段）から出力されるアドレスデータに対応するアドレスからデータを読み出して出力するようになされている。セレクタ１０６は、画像データをメモリ１０１に入力する場合には、カウンタ１０２側へ接続され、また、画像データをメモリ１０１から出力する場合には、メモリ１０３側へ接続されるようになされている。
【００４２】
カウンタ１０２は、メモリ１０１に対して画像データを読み込む場合に、アドレスデータを出力するようになされており、例えば、小さい順にアドレスデータを出力するようになされている。
【００４３】
カウンタ１０４は、アドレスデータを所定の順序で出力するようになされている。メモリ１０３は、カウンタ１０４から出力されたアドレスデータを、レンズの収差をキャンセルするように変換して出力するようになされている。なお、メモリ１０３に格納されているアドレス変換用のデータは、キャリブレーションを行う際に対応点を手がかりとして生成される。
【００４４】
また、メモリ１０３に格納されているデータには有効ビットが付加されており、各カメラ毎に予め求められている探索範囲が画像の領域を越える場合には、この有効ビットは“０”とされているので、メモリ１０３から出力される有効ビット信号は“０”の状態となる。なお、探索範囲が画像の領域内である場合には、メモリ１０３から出力される有効ビット信号は“１”の状態とされる。
【００４５】
ルックアップテーブル１０５（変換手段）は、階調変換を行うためのデータが格納されており、入力されたデータに対応するアドレスからデータが読み出されて出力されるようになされている。なお、このルックアップテーブル１０５に格納されているデータは、カメラ１乃至カメラ５により同一のパターンを撮像した場合に、全てのカメラの出力が同一になるようなデータが格納されている。従って、このルックアップテーブル１０５により各カメラの特性のばらつきが補正される。
【００４６】
続いて、図３を参照して、図１に示すＳＡＤ回路２００の詳細な構成例について説明する。なお、ＳＡＤ回路２００−１乃至２００−４は全て同様の構成とされているので、以下では、ＳＡＤ回路２００−１を例に挙げて説明する。
【００４７】
この図において、減算回路２０１−１は、カメラ１から出力された基準画像の画素値から、カメラ２から出力された参照画像の画素値を減算して出力するようになされている。減算回路２０１−２は、カメラ１から出力された基準画像の画素値から、カメラ３から出力された参照画像の画素値を減算して出力するようになされている。
【００４８】
絶対値回路２０２−１は、減算回路２０１−１から出力されるデータの絶対値を演算し、得られた結果を出力するようになされている。また、絶対値回路２０２−２は、減算回路２０１−２から出力されるデータの絶対値を演算し、得られた結果を出力するようになされている。
【００４９】
セレクタ２０３−１は、カメラ２の有効ビットが“１”の状態である場合には、絶対値回路２０２−１の出力を選択して出力するようになされている。一方、カメラ２の有効ビットが“０”の状態である場合には、絶対値回路２０２−２の出力を選択して出力するようになされている。
【００５０】
セレクタ２０３−２は、カメラ３の有効ビットが“１”の状態である場合には、絶対値回路２０２−２の出力を選択して出力するようになされている。一方、カメラ３の有効ビットが“０”の状態である場合には、絶対値回路２０２−１の出力を選択して出力するようになされている。
【００５１】
加算回路２０４は、セレクタ２０３−１の出力と、セレクタ２０３−２の出力を加算して出力するようになされている。
【００５２】
セレクタ２０６は、カメラ２またはカメラ３の少なくとも一方の有効ビットが“１”の状態である場合には、加算回路２０４の出力を選択して出力する。また、双方の有効ビットが“０”の場合には、最大値回路２０５から出力されるデータ（例えば、５１１）を選択して出力するようになされている。
【００５３】
最後に、図４を参照して、図１に示すＳＳＡＤ回路３００の詳細な構成例について説明する。
【００５４】
この図において、ディレイライン３０１は、入力された画素値の差分の絶対値をブロックマッチングのブロックの大きさ×１ラインの画素数分だけ遅延して出力するようになされている。
【００５５】
減算回路３０２は、ディレイライン３０１を経由していないデータから、ディレイライン３０１から出力されたデータを減算し、得られた結果を出力するようになされている。
【００５６】
加算回路３０３は、減算回路３０２から出力されたデータと、メモリ３０４から出力されたデータを加算して出力するようになされている。メモリ３０４は、加算回路３０３から出力されたデータを１ライン分遅延した後、出力するようになされている。
【００５７】
ディレイライン３０５は、加算回路３０３の出力を１ラインを構成する画素数分だけ遅延して出力するようになされている。減算回路３０６は、加算回路３０３の出力からディレイライン３０５の出力を減算して出力するようになされている。
【００５８】
加算回路３０７は、減算回路３０６の出力とメモリ３０８の出力とを加算して出力するようになされている。メモリ３０８は、加算回路３０７の出力をブロックマッチングのブロックの大きさ分だけ遅延して出力するようになされている。
【００５９】
次に、以上の実施の形態の動作について説明する。
【００６０】
図１に示す実施の形態に、カメラ１乃至カメラ５から出力される画像が入力されると、画像入力部１００−１乃至１００−５は、画像を一旦格納した後、所定の順序で読み出すとともに、階調変換を施して出力する。
【００６１】
即ち、図２に示すメモリ１０１に対して画像データが供給されると、カウンタ１０２から出力されるアドレスデータに対応するアドレスに、データが逐次格納されていくことになる。なお、このような動作は、画像入力部１００−１乃至１００−５の全てにおいて実行され、カメラ１乃至５から出力された画像がメモリ１０１の所定のアドレスに逐次格納されることになる。また、このとき、セレクタ１０６は、カウンタ１０２側を選択している。
【００６２】
画像データの格納が終了すると、セレクタ１０６がメモリ１０３側に接続される。そして、カウンタ１０４からアドレスデータの出力が開始される。メモリ１０３は、カウンタ１０４から出力されたアドレスデータに対応するアドレスから所定のデータを読み出してメモリ１０１に供給する。メモリ１０３に格納されているデータは、各画素毎、かつ、各探索ディスパリティ毎に画像データを読み出すように設定されているので、その結果、探索するエピポーララインが非直線の場合でも対応でき、レンズの収差等を吸収することが可能となる。
【００６３】
また、メモリ１０３に格納されているデータには、前述のように有効ビットが付加されているので、各カメラ毎に求められている探索範囲が画像の領域を越えた場合には、有効ビットが“０”の状態とされる。また、探索範囲が画像の領域を越えていない場合には、同ビットは“１”の状態とされる。
【００６４】
メモリ１０１から出力された画像データは、ルックアップテーブル１０５に供給される。ルックアップテーブル１０５は、メモリ１０１から出力された画像データに対応するアドレスに格納されているデータを読み出して出力する。このルックアップテーブル１０５に格納されているデータは、各カメラの特性の相違に起因する階調の差を補正するように設定されているので、その結果、各カメラ間の明暗の相違などを吸収することができる。
【００６５】
このようにして、レンズの収差と各カメラの特性に対する補正処理が施された画像データは、画像入力部１００−１乃至１００−５から出力され、ＳＡＤ回路２００−１乃至２００−４に供給される。
【００６６】
ＳＡＤ回路２００−１乃至２００−４は、画像入力部１００−１乃至１００−５から出力された基準画像データと２つの参照画像データとの間で画素値の差分の絶対値を算出して出力する。なお、ＳＡＤ回路２００−１乃至２００−４において行われる演算は、有効ビットの値に応じて適宜変更される。
【００６７】
即ち、画像入力部１００−１から出力された補正処理が施された画像データは、減算回路２０１−１と減算回路２０１−２にそれぞれ供給される。また、画像入力部１００−２と画像入力部１００−３から出力された画像データは、それぞれ、減算回路２０１−１と減算回路２０１−２に供給される。
【００６８】
減算回路２０１−１は、基準画像の画素値から、参照画像であるカメラ２の画像の画素値を減算して出力する。また、減算回路２０１−２は、基準画像の画素値から、参照画像であるカメラ３の画像の画素値を減算して出力する。
【００６９】
絶対値回路２０２−１は、減算回路２０１−１の計算結果の絶対値を演算して出力する。また、絶対値回路２０２−２は、減算回路２０１−２の計算結果の絶対値を演算して出力する。その結果、絶対値回路２０２−１からは、参照画像である画像入力部１００−２からの画像と、基準画像である画像入力部１００−１からの画素の差分の絶対値が出力される。また、絶対値回路２０２−２からは、参照画像である画像入力部１００−３の画像と、基準画像である画像入力部１００−１からの画像の画素の差分の絶対値が出力されることになる。
【００７０】
セレクタ２０３−１は、カメラ２の探索範囲が画像の領域内にある場合には、有効ビットが“１”の状態とされるので、絶対値回路２０３−１の出力を選択して加算回路２０４に出力する。また、カメラ２の探索範囲が画像の領域を越えた場合には、有効ビットが“０”の状態とされるので、その場合には、セレクタ２０３−１は、絶対値回路２０２−２の出力を選択して加算回路２０４に出力する。
【００７１】
同様に、セレクタ２０３−２は、カメラ３の探索範囲が画像の領域内にある場合には、有効ビットが“１”の状態とされるので、絶対値回路２０３−２の出力を選択して、加算回路２０４に出力する。また、カメラ３の探索範囲が画像の領域を越えた場合には、有効ビットが“０”の状態とされるので、その場合には、セレクタ２０３−２は、絶対値回路２０２−１の出力を選択して加算回路２０４に出力する。
【００７２】
加算回路２０４は、セレクタ２０３−１と２０３−２の出力を加算して出力する。また、セレクタ２０６は、カメラ２とカメラ３の有効ビットの状態に応じて、加算回路２０４、または、最大値回路２０５の出力を選択して出力する。その結果、セレクタ２０６の出力は、カメラ２とカメラ３の有効ビットの状態に応じて以下のような出力を生ずることになる。
【００７３】
（１）双方の有効ビットが“１”（有効）の状態であれば、絶対値回路２０２−１と絶対値回路２０２−２がそのまま加算されて出力される。
（２）どちらか一方の有効ビットが“０”（無効）である場合には、有効である方の絶対値回路の出力が２倍されて出力される。
（３）双方の有効ビットが“０”である場合には、最大値回路２０５の出力（例えば、画素データが８ビットの場合には値５１１）が選択されて出力される。
【００７４】
ＳＡＤ回路２００−１乃至２００−４の出力は、ＳＳＡＤ回路３００−１乃至３００−４にそれぞれ供給される。
【００７５】
ＳＳＡＤ回路２００−１乃至２００−４は、例えば、５×５個の画素からなる画素ブロック単位でブロックマッチング処理を行い、得られた結果を出力する。
【００７６】
即ち、ＳＡＤ回路２００−１乃至２００−４から出力された画素の差分の絶対値（｜ａij−ｂij｜）は、減算回路３０２に供給されるとともに、ディレイライン３０１に供給され、ブロックマッチングの大きさ×１ラインの画素数分だけ遅延された後、減算回路３０２に供給される。
【００７７】
減算回路３０２は、ＳＡＤ回路の出力データから、ディレイライン３０１により遅延されたデータを減算して、加算回路３０３に出力する。
【００７８】
加算回路３０３は、メモリ３０４により遅延された１ライン分前のデータと減算回路３０２の出力とを加算して出力する。その結果、加算回路３０３からは、２次元ブロックマッチングの１次元処理が施されたデータ（Σi｜ａij−ｂij｜
）が出力されることになる。
【００７９】
ディレイライン３０５、減算回路３０６、加算回路３０７、および、メモリ３０８は、前段の回路と同様の処理を実行し、その結果、加算回路３０７からは、２次元のブロックマッチング処理が施されたデータ（ΣjΣi｜ａij−ｂij｜）が出力されることになる。
【００８０】
ＳＳＡＤ回路３００−１乃至３００−４から出力されたデータは、２次近似処理部４００−１乃至４００−４にそれぞれ供給される。
【００８１】
２次近似部４００−１乃至４００−４は、ＳＳＡＤ回路３００−１乃至３００−４から出力されたあるデータＳ2と、それに前後するデータＳ1，Ｓ3を２次曲
線で補間して、更に正確な最小値データを得る。
【００８２】
図５は、２次近似部４００の動作を説明する図である。
【００８３】
この図に示すように、ＳＳＡＤ回路３００の出力ｄ1乃至ｄ3が入力されると、２次近似回路４００は、ｄ1乃至ｄ3を結ぶ曲線を以下の２次式により生成する。
【００８４】
Ｓ1＝ａ・ｄ12＋ｂ・ｄ1＋ｃ ・・・（１）
Ｓ2＝ａ・ｄ22＋ｂ・ｄ2＋ｃ ・・・（２）
Ｓ3＝ａ・ｄ32＋ｂ・ｄ3＋ｃ ・・・（３）
【００８５】
ここで、ｄ1＝−１，ｄ2＝０，ｄ3＝１とすると、以上の式（１）乃至（３）
は、次のようになる。
【００８６】
Ｓ1＝ａ−ｂ＋ｃ ・・・（４）
Ｓ2＝ｃ ・・・（５）
Ｓ3＝ａ＋ｂ＋ｃ ・・・（６）
【００８７】
これを解くと、最小値ｄは、以下の式により表すことができる。
【００８８】
ｄ＝（Ｓ1−Ｓ3）／｛２×（Ｓ1−２・Ｓ2＋Ｓ3）｝ ・・・（７）
【００８９】
ここで、ｄの範囲は、以下のように表すことができる。
【００９０】
−０．５≦ｄ≦０．５ ・・・（８）
【００９１】
従って、各項を２倍すると、以下の式を得る。
【００９２】
−１≦２・ｄ≦１ ・・・（９）
【００９３】
式（９）に式（７）を代入すると、以下の式を得る。
【００９４】
−１≦（Ｓ1−Ｓ3）／（Ｓ1−２・Ｓ2＋Ｓ3）≦１ ・・・（１０）
【００９５】
通常、式（７）に示すような除算を含む演算を行う場合、ハードウエアの計算コストは大きくなる。しかしながら、ここでは、求める精度が小数点以下３乃至４ビットと少なく、また、得られる結果の範囲が式（１０）に示すように明確になっている。即ち、２次曲線近似で求める正確な最小値を示す位置は、求まった最小値の位置から±０．５の範囲にある。従って、除算の代わりに減算を用いて計算を行うことができることから、計算を大幅に簡略化するとともに、ハードウエア資源を削減することができる。
【００９６】
なお、以上の構成では、ＳＳＡＤ回路３００から出力される全てのデータに対して２次近似が施されることになるが、最終的には、最小値選択部５００により最小値のみが選択されるので問題は生じない。
【００９７】
このようにして２次近似されたデータは、最小値選択部５００に供給される。最小値選択部５００は、２次近似部４００−１乃至４００−４から出力されたデータから最小値を選択し、最小値選択部６００に対して出力する。
【００９８】
最小値選択部６００は、結果メモリ７００に格納されているそれまでの最小値と、最小値選択部５００から新たに出力された値とを比較し、より小さい方を選択して出力する。結果メモリ７００は、最小値選択部６００から出力された値を保持する。その結果、結果メモリ７００には、全てのカメラペア（各ＳＡＤ回路に入力されている画像に対応するカメラの組み合わせ）から得られたデータのうち、最小のデータが選択されて格納されることになる。
【００９９】
このような最小のデータは、マッチング度が最も高いデータであるので、そのデータを用いることにより、最も精度の高い視差を求めることが可能となる。
【０１００】
以上のような実施の形態によれば、ＳＳＡＤ回路３００の出力を２次近似部４００により２次近似した後で、最小値選択部５００により最小値を選択するようにしたので、装置をパイプライン化し、また、並列分散処理を行うことが可能となる。従って、演算を高速に実行することが可能となる。
【０１０１】
また、メモリ１０３を設けて、データを非直線的に読み出すことができるようにしたので、レンズの収差の影響をキャンセルすることが可能となる。更に、ルックアップテーブル１０５を設け、各カメラの特性の相違に起因する濃淡値の誤差を補正するようにしたので、結果として測定精度を向上させることが可能となる。
【０１０２】
なお、以上の実施の形態においては、５台のカメラを用いて測定を行うようにしたが、本発明はこのような場合にのみ限定されるものではないことは勿論である。
【０１０３】
また、明細書中において、伝送媒体は、ＦＤ，ＣＤ−ＲＯＭなどの情報記録媒体の他、インターネット、ディジタル衛星などのネットワーク伝送媒体も含まれる。
【図面の簡単な説明】
【０１０４】
【図１】本発明の実施の形態の構成例を示すブロック図である。
【図２】図１に示す画像入力部１００の詳細な構成例を示すブロック図である。
【図３】図１に示すＳＡＤ回路２００の詳細な構成例を示すブロック図である。
【図４】図１に示すＳＳＡＤ回路３００の詳細な構成例を示すブロック図である。
【図５】図１に示す２次近似部４００の処理を説明する図である。
【図６】従来の画像処理装置の構成例を示すブロック図である。
【符号の説明】
【０１０５】
１００−１ 画像入力部（第１の入力手段）， １００−２乃至１００−５ 画像入力部（第２の入力手段）， １０１ メモリ（第１の記憶手段、読み出し手段）， １０３ メモリ（第２の記憶手段）， １０５ ルックアップテーブル（変換手段）， ２００−１乃至２００−４ ＳＡＤ回路（マッチング手段）， ３００−１乃至３００−４ ＳＳＡＤ回路（マッチング手段）， ５００， ６００ 最小値検出部（検出手段）， ７００ 結果メモリ（検出手段）
【特許請求の範囲】
【請求項１】
複数の撮像装置によって撮像された画像に基づいて、対象点までの距離を画像処理により算出する画像処理装置において、
各撮像装置から出力される画像を記憶する第１の記憶手段と、
前記記憶手段に記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶手段と、
前記第２の記憶手段に記憶された順序に応じて、前記第１の記憶手段に記憶されている画素データを読み出す読み出し手段と、
前記読み出し手段によって読み出された画素データの階調を変換する変換手段と
を備えることを特徴とする画像処理装置。
【請求項２】
前記第２の記憶手段に記憶されているデータは、各撮像装置のレンズの収差に応じて生成されている
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記変換手段は、前記複数の撮像装置の階調が全て等しくなるように設定されている
ことを特徴とする請求項１に記載の画像処理装置。
【請求項４】
複数の撮像装置によって撮像された画像に基づいて、対象点までの距離を画像処理により算出する画像処理方法において、
各撮像装置から出力される画像を記憶する第１の記憶ステップと、
前記記憶ステップに記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶ステップと、
前記第２の記憶ステップに記憶された順序に応じて、前記第１の記憶ステップに記憶されている画素データを読み出す読み出しステップと、
前記読み出しステップによって読み出された画素データの階調を変換する変換ステップと
を備えることを特徴とする画像処理方法。
【請求項５】
複数の撮像装置によって撮像された画像に基づいて、対象点までの距離を画像処理により算出する画像処理装置で使用されるコンピュータプログラムが記録されている記録媒体において、
各撮像装置から出力される画像を記憶する第１の記憶ステップと、
前記記憶ステップに記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶ステップと、
前記第２の記憶ステップに記憶された順序に応じて、前記第１の記憶ステップに記憶されている画素データを読み出す読み出しステップと、
前記読み出しステップによって読み出された画素データの階調を変換する変換ステップとを備えるプログラムが記録されている記録媒体。
【請求項６】
請求項５に記載の記録媒体に記録されたプログラムを用いて画像処理を行う画像処理方法。
【請求項１】
複数の撮像装置によって撮像された画像に基づいて、対象点までの距離を画像処理により算出する画像処理装置において、
各撮像装置から出力される画像を記憶する第１の記憶手段と、
前記記憶手段に記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶手段と、
前記第２の記憶手段に記憶された順序に応じて、前記第１の記憶手段に記憶されている画素データを読み出す読み出し手段と、
前記読み出し手段によって読み出された画素データの階調を変換する変換手段と
を備えることを特徴とする画像処理装置。
【請求項２】
前記第２の記憶手段に記憶されているデータは、各撮像装置のレンズの収差に応じて生成されている
ことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記変換手段は、前記複数の撮像装置の階調が全て等しくなるように設定されている
ことを特徴とする請求項１に記載の画像処理装置。
【請求項４】
複数の撮像装置によって撮像された画像に基づいて、対象点までの距離を画像処理により算出する画像処理方法において、
各撮像装置から出力される画像を記憶する第１の記憶ステップと、
前記記憶ステップに記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶ステップと、
前記第２の記憶ステップに記憶された順序に応じて、前記第１の記憶ステップに記憶されている画素データを読み出す読み出しステップと、
前記読み出しステップによって読み出された画素データの階調を変換する変換ステップと
を備えることを特徴とする画像処理方法。
【請求項５】
複数の撮像装置によって撮像された画像に基づいて、対象点までの距離を画像処理により算出する画像処理装置で使用されるコンピュータプログラムが記録されている記録媒体において、
各撮像装置から出力される画像を記憶する第１の記憶ステップと、
前記記憶ステップに記憶された画像を構成する画素データを読み出す順序を記憶する第２の記憶ステップと、
前記第２の記憶ステップに記憶された順序に応じて、前記第１の記憶ステップに記憶されている画素データを読み出す読み出しステップと、
前記読み出しステップによって読み出された画素データの階調を変換する変換ステップとを備えるプログラムが記録されている記録媒体。
【請求項６】
請求項５に記載の記録媒体に記録されたプログラムを用いて画像処理を行う画像処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００６−１６４２９７（Ｐ２００６−１６４２９７Ａ）
【公開日】平成１８年６月２２日（２００６．６．２２）
【国際特許分類】
【出願番号】特願２００５−３７８６０２（Ｐ２００５−３７８６０２）
【出願日】平成１７年１２月２８日（２００５．１２．２８）
【分割の表示】特願平９−２０７９５２の分割
【原出願日】平成９年８月１日（１９９７．８．１）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成１８年６月２２日（２００６．６．２２）
【国際特許分類】
【出願日】平成１７年１２月２８日（２００５．１２．２８）
【分割の表示】特願平９−２０７９５２の分割
【原出願日】平成９年８月１日（１９９７．８．１）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]