(57)【要約】【課題】計測用パターンが投射された被写体を撮影した２画像間のマッチングの精度を向上する。【解決手段】本発明の一態様によれば、計測用パターンは、第１のパターン群と、第１のパターン群と第１の方向上で隣接する第２のパターン群とを含む。第１のパターン群において、第１のパターンが第１の方向に沿って繰り返し並べられる。第１のパターンにおいて、第１の基本パターンが第１の方向に直交する第２の方向に沿って繰り返し並べられる。第１の基本パターンは、第２の方向に沿って連続して並べられた自然数Ｈ１個の明ブロックと、これに続けて第２の方向に沿って連続して並べられたＬ１（＞Ｈ１）個の暗ブロックとを含む。第１のパターン群に含まれる、第１の方向上で隣接する明ブロック同士を連結した明領域の各々において、明領域の第１の方向に沿ったサイズが第２の方向に沿ったサイズに比べて大きい。【選択図】      図３
2019184549.tif 000002
【特許請求の範囲】
【請求項１】
計測用パターンが投射された被写体を第１のカメラおよび第２のカメラによってそれぞれ撮影した第１の撮影画像および第２の撮影画像を取得する取得部と、
前記第１の撮影画像から注目画素を含む第１の画素ブロックを抽出し、当該第１の画素ブロックに対応する第２の画素ブロックを前記第２の撮影画像から探索する探索部と
を具備し、
前記計測用パターンは、第１のパターン群と、前記第１のパターン群と第１の方向上で隣接する第２のパターン群とを含み、
前記第１のパターン群において、少なくとも１つの第１のパターンが前記第１の方向に沿って繰り返し並べられ、
前記第２のパターン群において、少なくとも１つの第２のパターンが前記第１の方向に沿って繰り返し並べられ、
前記第１のパターンにおいて、第１の基本パターンが前記第１の方向に直交する第２の方向に沿って繰り返し並べられ、
前記第１の基本パターンは、前記第２の方向に沿って連続して並べられた自然数Ｈ１個の明ブロックと、当該Ｈ１個の明ブロックに続けて前記第２の方向に沿って連続して並べられた前記Ｈ１よりも多いＬ１個の暗ブロックとを含み、
前記第２のパターンにおいて、第２の基本パターンが前記第２の方向に沿って繰り返し並べられ、
前記第２の基本パターンは、前記第２の方向に沿って連続して並べられた自然数Ｈ２個の明ブロックと、当該Ｈ２個の明ブロックに続けて前記第２の方向に沿って連続して並べられた前記Ｈ２よりも多いＬ２個の暗ブロックとを含み、
前記Ｈ１および前記Ｌ１の和Ｃ１は、前記Ｈ２および前記Ｌ２の和Ｃ２とは異なり、
前記第１のパターン群および第２のパターン群に含まれる、前記第１の方向上で隣接する明ブロック同士を連結した明領域の各々において、当該明領域の前記第１の方向に沿ったサイズが前記第２の方向に沿ったサイズに比べて大きい、
画像処理装置。
【請求項２】
前記Ｃ１および前記Ｃ２は互いに素な自然数である、請求項１に記載の画像処理装置。
【請求項３】
前記計測用パターンにおいて、前記第１のパターン群および前記第２のパターン群を含む２以上の自然数Ｖ組のパターン群が前記第１の方向に沿って繰り返し並べられる、請求項１または請求項２に記載の画像処理装置。
【請求項４】
前記第１の基本パターンおよび前記第２の基本パターンを含むＶ種の基本パターンのそれぞれにおける前記明ブロックの個数および前記暗ブロックの個数の和の最小値はＣｍｉｎであり、
前記Ｖ種の基本パターンのそれぞれにおける前記暗ブロックの個数の最大値はＬｍａｘであり、
前記第１の画素ブロックは、前記第１の撮影画像における前記第１の方向の射影方向に前記Ｖ組のパターン群以上のサイズを有し、
前記第１の画素ブロックは、前記第１の撮影画像における前記第２の方向の射影方向に、Ｃｍｉｎ×２およびＬｍａｘのうち大きな一方の数の明ブロックまたは暗ブロック以上のサイズを有する、
請求項３に記載の画像処理装置。
【請求項５】
前記第１の基本パターンおよび前記第２の基本パターンを含むＶ種の基本パターンのそれぞれにおける前記明ブロックの個数および前記暗ブロックの個数の和は前記Ｃ１以下であり、
前記Ｖ種の基本パターンから前記第１の基本パターンを除いたＶ−１種の基本パターンのそれぞれにおける前記明ブロックの個数および前記暗ブロックの個数の和は前記Ｃ２以下であり、
前記探索部は、（ａ）前記第１の画素ブロックのうち前記第１のパターンを表す領域にマッチする第１の領域を前記第２の撮影画像から探索し、（ｂ）当該第１の領域が発見された場合には、前記第２の撮影画像において当該第１の領域を前記第１のパターンおよび前記第２のパターンの位置関係に応じて前記第２の撮影画像における前記第１の方向の射影方向に沿ってずらした第２の領域が前記第１の画素ブロックのうち前記第２のパターンを表す領域にマッチするか否かを判定する、
請求項３または請求項４に記載の画像処理装置。
【請求項６】
計測用パターンが投射された被写体を第１のカメラおよび第２のカメラによってそれぞれ撮影した第１の撮影画像および第２の撮影画像を取得する取得部と、
前記第１の撮影画像から注目画素を含む第１の画素ブロックを抽出し、当該第１の画素ブロックに対応する第２の画素ブロックを前記第２の撮影画像から探索する探索部と
を具備し、
前記計測用パターンは、第１の明暗パターンと、前記第１の明暗パターンと第１の方向上で全暗パターンを介して隣接する第２の明暗パターンとを含み、
前記第１の明暗パターンにおいて、第１の基本パターンが前記第１の方向に直交する第２の方向に沿って繰り返し並べられ、
前記第１の基本パターンは、前記第２の方向に沿って連続して並べられた自然数Ｈ１個の明ブロックと、当該Ｈ１個の明ブロックに続けて前記第２の方向に沿って連続して並べられた前記Ｈ１よりも多いＬ１個の暗ブロックとを含み、
前記第２の明暗パターンにおいて、第２の基本パターンが前記第２の方向に沿って繰り返し並べられ、
前記第２の基本パターンは、前記第２の方向に沿って連続して並べられた自然数Ｈ２個の明ブロックと、当該Ｈ２個の明ブロックに続けて前記第２の方向に沿って連続して並べられた前記Ｈ２よりも多いＬ２個の暗ブロックとを含み、
前記Ｈ１および前記Ｌ１の和Ｃ１は、前記Ｈ２および前記Ｌ２の和Ｃ２とは異なり、
前記全暗パターンにおいて、暗ブロックが前記第２の方向に沿って繰り返し並べられる、
画像処理装置。
【請求項７】
前記Ｃ１および前記Ｃ２は互いに素な自然数である、請求項６に記載の画像処理装置。
【請求項８】
前記計測用パターンにおいて、前記第１の明暗パターンおよび前記第２の明暗パターンを含む自然数Ｖ個の明暗パターンの各々と前記Ｖ個の全暗パターンの各々とを交互に配列した２×Ｖ個のパターンが前記第１の方向に沿って繰り返し並べられる、請求項６または請求項７に記載の画像処理装置。
【請求項９】
前記第１の基本パターンおよび前記第２の基本パターンを含むＶ種の基本パターンのそれぞれにおける前記明ブロックの個数および前記暗ブロックの個数の和の最小値はＣｍｉｎであり、
前記Ｖ種の基本パターンのそれぞれにおける前記暗ブロックの個数の最大値はＬｍａｘであり、
前記第１の画素ブロックは、前記第１の撮影画像における前記第１の方向の射影方向に前記２×Ｖ個のパターン以上のサイズを有し、
前記第１の画素ブロックは、前記第１の撮影画像における前記第２の方向の射影方向に、Ｃｍｉｎ×２およびＬｍａｘのうち大きな一方の数の明ブロックまたは暗ブロック以上のサイズを有する、
請求項８に記載の画像処理装置。
【請求項１０】
前記第１の基本パターンおよび前記第２の基本パターンを含むＶ種の基本パターンのそれぞれにおける前記明ブロックの個数および前記暗ブロックの個数の和は前記Ｃ１以下であり、
前記Ｖ種の基本パターンから前記第１の基本パターンを除いたＶ−１種の基本パターンのそれぞれにおける前記明ブロックの個数および前記暗ブロックの個数の和は前記Ｃ２以下であり、
前記探索部は、（ａ）前記第１の画素ブロックのうち前記第１の明暗パターンを表す領域にマッチする第１の領域を前記第２の撮影画像から探索し、（ｂ）当該第１の領域が発見された場合には、前記第２の撮影画像において当該第１の領域を前記第１の明暗パターンおよび前記第２の明暗パターンの位置関係に応じて前記第２の撮影画像における前記第１の方向の射影方向に沿ってずらした第２の領域が前記第１の画素ブロックのうち前記第２の明暗パターンを表す領域にマッチするか否かを判定する、
請求項８または請求項９に記載の画像処理装置。
【請求項１１】
計測用パターンが投射された被写体を第１のカメラおよび第２のカメラによってそれぞれ撮影した第１の撮影画像および第２の撮影画像を取得する取得部と、
前記第１の撮影画像から注目画素を含む第１の画素ブロックを抽出し、当該第１の画素ブロックに対応する第２の画素ブロックを前記第２の撮影画像から探索する探索部と
を具備し、
前記計測用パターンは、明ブロックおよび暗ブロックをランダムまたは疑似ランダムに配列したパターンにエッジ検出処理を施すことで得られるパターンに相当する、
画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、既定のパターンが投射された被写体を２台のカメラによって撮影し、２画像間のマッチング結果に基づいて、視差／距離を計測する技術に関する。
【背景技術】
【０００２】
従来、プロジェクターによって被写体に既定のパターンを投射し、２台のカメラによって当該被写体を撮影し、２画像間のマッチング結果に基づいて視差／距離を計測する技術が知られている。これにより、外見的特徴の乏しい被写体であっても、既定のパターンを手かがりにマッチングを行うことが可能となる。被写体にどのようなパターンを投射するかによって、２画像間のマッチングの効率および精度が左右される。
【０００３】
特許文献１によれば、デブルーイン系列を用いてブロック単位でコード化されたパターンが用いられる。特許文献２によれば、被写体追跡のために、「２ストライプコード」の投射パターンが用いられる。非特許文献１によれば、ランダムドットパターンが用いられる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第８，１４２，０２３号明細書
【特許文献２】米国特許第６，７５４，３７０号明細書
【非特許文献】
【０００５】
【非特許文献１】日本ロボット学会誌  ｖｏｌ．  １７  Ｎｏ．  １．  ｐｐ．  ４８〜４９．  １９９９
【発明の概要】
【発明が解決しようとする課題】
【０００６】
デブルーイン系列を用いてブロック単位でコード化されたパターンは、各ブロックがいずれもユニークなコードに相当する。故に、例えば被写体表面の明暗の影響により、一方の画像においてブロック内の少なくとも１つの要素の投射パターンの明暗に反転が生じると、当該ブロックは他方の画像における対応するブロックとマッチしないことになる。故に、かかるパターンは、明暗の変動に対してロバストでない。
【０００７】
他方、ランダムドットパターンでは、ドットの疎な領域と密な領域とが混在するので、明暗の空間的な偏りが必然的に生じる。故に、ランダムドットパターンによれば、空間分解能が局所的に低下することになる。また、ランダムドットパターンによれば、マッチングに多くの時間がかかる。さらに、特に被写体に光沢がある場合には、明ドットの周囲にある暗ドットがつぶれやすく、正確なマッチングが困難となるおそれがある。
【０００８】
暗ドットがつぶれる原因として、被写体からの反射光が強い場合に明ドット周囲におけるイメージセンサ出力が飽和して出力画像に滲みが生じること（ハレーション）、被写体からの鏡面反射により被写体の像がイメージセンサ上で結像せずにフレアーが生じること、などが考えられる。
【０００９】
本発明は、計測用パターンが投射された被写体を撮影した２画像間のマッチングの精度を向上することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の第１の態様によれば、画像処理装置は、取得部と、探索部とを含む。取得部は、計測用パターンが投射された被写体を第１のカメラおよび第２のカメラによってそれぞれ撮影した第１の撮影画像および第２の撮影画像を取得する。探索部は、第１の撮影画像から注目画素を含む第１の画素ブロックを抽出し、当該第１の画素ブロックに対応する第２の画素ブロックを第２の撮影画像から探索する。計測用パターンは、第１のパターン群と、第１のパターン群と第１の方向上で隣接する第２のパターン群とを含む。第１のパターン群において、少なくとも１つの第１のパターンが第１の方向に沿って繰り返し並べられる。第２のパターン群において、少なくとも１つの第２のパターンが第１の方向に沿って繰り返し並べられる。第１のパターンにおいて、第１の基本パターンが第１の方向に直交する第２の方向に沿って繰り返し並べられる。第１の基本パターンは、第２の方向に沿って連続して並べられた自然数Ｈ１個の明ブロックと、当該Ｈ１個の明ブロックに続けて第２の方向に沿って連続して並べられたＨ１よりも多いＬ１個の暗ブロックとを含む。第２のパターンにおいて、第２の基本パターンが第２の方向に沿って繰り返し並べられる。第２の基本パターンは、第２の方向に沿って連続して並べられた自然数Ｈ２個の明ブロックと、当該Ｈ２個の明ブロックに続けて第２の方向に沿って連続して並べられたＨ２よりも多いＬ２個の暗ブロックとを含む。Ｈ１およびＬ１の和Ｃ１は、Ｈ２およびＬ２の和Ｃ２とは異なる。第１のパターン群および第２のパターン群に含まれる、第１の方向上で隣接する明ブロック同士を連結した明領域の各々において、当該明領域の第１の方向に沿ったサイズが第２の方向に沿ったサイズに比べて大きい。
【００１１】
本発明の第２の態様によれば、画像処理装置は、取得部と、探索部とを含む。取得部は、計測用パターンが投射された被写体を第１のカメラおよび第２のカメラによってそれぞれ撮影した第１の撮影画像および第２の撮影画像を取得する。探索部は、第１の撮影画像から注目画素を含む第１の画素ブロックを抽出し、当該第１の画素ブロックに対応する第２の画素ブロックを第２の撮影画像から探索する。計測用パターンは、第１の明暗パターンと、第１の明暗パターンと第１の方向上で全暗パターンを介して隣接する第２の明暗パターンとを含む。第１の明暗パターンにおいて、第１の基本パターンが第１の方向に直交する第２の方向に沿って繰り返し並べられる。第１の基本パターンは、第２の方向に沿って連続して並べられた自然数Ｈ１個の明ブロックと、当該Ｈ１個の明ブロックに続けて第２の方向に沿って連続して並べられたＨ１よりも多いＬ１個の暗ブロックとを含む。第２の明暗パターンにおいて、第２の基本パターンが第２の方向に沿って繰り返し並べられる。第２の基本パターンは、第２の方向に沿って連続して並べられた自然数Ｈ２個の明ブロックと、当該Ｈ２個の明ブロックに続けて第２の方向に沿って連続して並べられたＨ２よりも多いＬ２個の暗ブロックとを含む。Ｈ１およびＬ１の和Ｃ１は、Ｈ２およびＬ２の和Ｃ２とは異なる。全暗パターンにおいて、暗ブロックが第２の方向に沿って繰り返し並べられる。
【００１２】
本発明の第３の態様によれば、画像処理装置は、取得部と、探索部とを含む。取得部は、計測用パターンが投射された被写体を第１のカメラおよび第２のカメラによってそれぞれ撮影した第１の撮影画像および第２の撮影画像を取得する。探索部は、第１の撮影画像から注目画素を含む第１の画素ブロックを抽出し、当該第１の画素ブロックに対応する第２の画素ブロックを第２の撮影画像から探索する。計測用パターンは、明ブロックおよび暗ブロックをランダムまたは疑似ランダムに配列したパターンにエッジ検出処理を施すことで得られるパターンに相当する。
【発明の効果】
【００１３】
本発明によれば、計測用パターンが投射された被写体を撮影した２画像間のマッチングの精度を向上することができる。
【図面の簡単な説明】
【００１４】
【図１】第１の実施形態に係る画像処理装置を含む、視差／距離計測システムを例示するブロック図。
【図２】第１の実施形態に係る画像処理装置を例示するブロック図。
【図３】第１の実施形態に係る計測用パターンを例示する図。
【図４】図３の計測用パターンから図２中の対応ブロック探索部によって抽出される第１の画素ブロックを例示する図。
【図５】図４における明ブロックから暗ブロックへの光の漏れの説明図。
【図６】図２中の対応ブロック探索部によって行われる、図４の第１の画素ブロックに対応する第２の画素ブロックの探索の説明図。
【図７】図２の画像処理装置およびその周辺装置の動作を例示するフローチャート。
【図８】図７中のステップＳ２１０の詳細を例示するフローチャート。
【図９】第２の実施形態に係る計測用パターンを例示する図。
【図１０】図９の計測用パターンから図２中の対応ブロック探索部によって抽出される第１の画素ブロックを例示する図。
【図１１】図１０における明ブロックから暗ブロックへの光の漏れの説明図。
【図１２】図２中の対応ブロック探索部によって行われる、図１０の第１の画素ブロックに対応する第２の画素ブロックの探索の説明図。
【図１３】明ブロックおよび暗ブロックをランダムまたは疑似ランダムに配列したパターンを例示する図。
【図１４】図１３のパターンに基づいて生成可能な、第３の実施形態に係る計測用パターンを例示する図。
【発明を実施するための形態】
【００１５】
以下、図面を参照しながら実施形態の説明を述べる。なお、以降、説明済みの要素と同一または類似の要素には同一または類似の符号を付し、重複する説明については基本的に省略する。
【００１６】
（第１の実施形態）  
第１の実施形態に係る画像処理装置は、例えば図１に示す視差／距離計測システムに組み込むことができる。この視差／距離計測システムは、プロジェクター／カメラ制御装置１０と、プロジェクター２０と、（左）カメラ４１と、（右）カメラ４２と、本実施形態に係る画像処理装置１００とを含む。
【００１７】
プロジェクター／カメラ制御装置１０は、プロジェクター２０、左カメラ４１および右カメラ４２を制御する。具体的には、プロジェクター／カメラ制御装置１０は、プロジェクター２０に後述される計測用パターンの投射を命令する。それから、プロジェクター／カメラ制御装置１０は、左カメラ４１および右カメラ４２に、計測用パターンが投射された被写体３０の撮影を命令する。
【００１８】
ここで、計測用パターンは、プロジェクター／カメラ制御装置１０からプロジェクター２０へ送られてもよいし、プロジェクター２０に内蔵または外付けされた記憶装置に保存されていてもよい。
【００１９】
また、計測用パターンは、計測用パターン生成装置（図示されない）によって生成され得る。計測用パターン生成装置は、プロジェクター／カメラ制御装置１０において実装されてもよいし、図示されない外部装置として実装されてもよい。後者の場合には、計測用パターン生成装置によって生成された計測用パターンが、通信媒体または記録媒体を経由して、最終的にプロジェクター２０に届けられる。
【００２０】
計測用パターン生成装置は、計測用パターンを生成するパターン生成部を含む。パターン生成部は、例えば、プロセッサおよびメモリの組み合わせであり得る。ここで、プロセッサは、典型的にはＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）および／またはＧＰＵ(Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ)であるが、マイコン、ＦＰＧＡ(Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ)、またはＤＳＰ(Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ)、などであってもよい。
【００２１】
プロジェクター２０は、プロジェクター／カメラ制御装置１０からの命令に従って、計測用パターンを被写体３０に投射する。そして、左カメラ４１および右カメラ４２は、計測用パターンが投射された被写体３０を撮影し、それぞれ第１の撮影画像および第２の撮影画像を生成する。ここで、左カメラ４１および右カメラ４２の光軸は、平行であることとし、さらに左カメラ４１および右カメラ４２のエピポーラ線は、後述される計測用パターンの水平方向と平行であることとする。
【００２２】
画像処理装置１００は、左カメラ４１および右カメラ４２からそれぞれ第１の撮影画像および第２の撮影画像を取得し、例えば画素毎に第１の撮影画像と第２の撮影画像との間で画素ブロックレベルでのマッチングを行う。そして、画像処理装置１００は、かかるマッチング結果に基づいて当該画素における左カメラ４１および右カメラ４２の視差、および／または左カメラ４１および右カメラ４２から被写体３０における当該画素に対応する点までの距離を算出する。さらに、画像処理装置１００または図示されない後段の外部装置が、距離の算出結果に基づいて被写体の３次元形状を推定してもよい。
【００２３】
画像処理装置１００は、入出力制御、通信制御、および種々の画像処理（例えば、第１の撮影画像および第２の撮影画像の間のマッチング、視差および／または距離の算出、など）を行うプロセッサを含む。画像処理装置１００は、さらに、かかる処理を実現するためにプロセッサによって実行されるプログラムおよび当該プログラムによって使用されるデータなどを一時的に格納するメモリを含んでいる。
【００２４】
画像処理装置１００は、さらに、左カメラ４１および右カメラ４２に接続するための通信インタフェース（Ｉ／Ｆ）を利用可能である。通信Ｉ／Ｆは、画像処理装置１００に内蔵されていてもよいし、画像処理装置１００に外付けされていてもよい。
【００２５】
通信Ｉ／Ｆは、例えば、左カメラ４１および右カメラ４２から第１の撮影画像および第２の撮影画像をそれぞれ受け取る。通信Ｉ／Ｆは、例えば光ファイバケーブル、ＨＤＭＩ（登録商標）（Ｈｉｇｈ−Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）ケーブル、などの有線通信Ｉ／Ｆであってもよいし、例えばＢｌｕｅｔｏｏｔｈ（登録商標）、Ｗｉ−Ｆｉ（登録商標）などの無線通信技術を利用する無線通信Ｉ／Ｆであってもよい。
【００２６】
以下、図２を用いて画像処理装置１００の構成例の説明を続ける。
図２に例示されるように、画像処理装置１００は、撮影画像取得部１０１と、対応ブロック探索部１０２と、視差算出部１０３と、距離算出部１０４とを含む。
【００２７】
撮影画像取得部１０１は、左カメラ４１および右カメラ４２からそれぞれ第１の撮影画像および第２の撮影画像を取得する。撮影画像取得部１０１は、取得した第１の撮影画像および第２の撮影画像を対応ブロック探索部１０２へ送る。撮影画像取得部１０１は、例えば前述のプロセッサおよび通信Ｉ／Ｆに相当し得る。
【００２８】
対応ブロック探索部１０２は、撮影画像取得部１０１から第１の撮影画像および第２の撮影画像を受け取る。対応ブロック探索部１０２は、第１の撮影画像および第２の撮影画像の画素ブロックレベルでのマッチングを行う。そして、対応ブロック探索部１０２は、マッチング結果を視差算出部１０３へ送る。対応ブロック探索部１０２は、前述のプロセッサに相当し得る。
【００２９】
対応ブロック探索部１０２は、まず、第１の撮影画像における画素の１つを注目画素として決定する。なお、以降の説明では、第１の撮影画像、すなわち左カメラ４１による撮影画像から注目画素を決定することとするが、第２の撮影画像、すなわち右カメラ４２による撮影画像から注目画素を決定することも可能である。後者の場合には、以降の説明において「第１の撮影画像」および「第２の撮影画像」の用語を適宜読み替えれば良い。
【００３０】
対応ブロック探索部１０２は、決定した注目画素を含む第１の画素ブロックを第１の撮影画像から抽出する。それから、対応ブロック探索部１０２は、第１の画素ブロックに対応する第２の画素ブロックを第２の撮影画像から探索する。対応ブロック探索部１０２の動作の詳細は後述される。
【００３１】
対応ブロック探索部１０２は、注目画素を変更しながら第１の撮影画像の各画素について上記探索処理を繰り返す。これにより、第１の撮影画像内の各画素について、第２の撮影画像とのマッチングが行われる。そして、対応ブロック探索部１０２は、マッチング結果を、視差算出部１０３へ送る。マッチング結果は、例えば第１の撮影画像の各画素（マッチングに成功した画素）の座標（位置）と、第２の撮影画像において当該画素に対応するとして探索された画素の座標とを含み得る。なお、対応ブロック探索部１０２は、１つの画素について探索が終わる毎にマッチング結果を視差算出部１０３へ送ってもよいし、全ての画素について探索が終わってからマッチング結果をまとめて視差算出部１０３へ送ってもよい。
【００３２】
視差算出部１０３は、対応ブロック探索部１０２からマッチング結果を受け取る。視差算出部１０３は、マッチング結果に基づいて、第１の撮影画像内の各画素（マッチングに成功した画素）に関する左カメラ４１および右カメラ４２の視差を算出する。視差算出部１０３は、視差算出結果を距離算出部１０４へ送る。視差算出結果は、例えば第１の撮影画像の各画素の座標と当該画素に関する視差ベクトルとを含み得る。また、視差算出部１０３は、視差算出結果を図示されない外部装置へ送ってもよい。視差算出部１０３は、例えば前述のプロセッサ（および通信Ｉ／Ｆ）に相当し得る。
【００３３】
距離算出部１０４は、視差算出部１０３から視差算出結果を受け取る。距離算出部１０４は、視差算出結果に基づいて、第１の撮影画像内の画素（マッチングに成功した画素）毎に、左カメラ４１および右カメラ４２から被写体３０における当該画素に対応する点までの距離、すなわち深度を算出する。距離算出部１０４は、距離算出結果を図示されない外部装置へ送ってもよい。距離算出結果は、例えば第１の撮影画像の各画素の座標と当該画素の深度とを含み得る。距離算出結果は、いわゆる深度マップであってもよい。距離算出部１０４は、例えば前述のプロセッサ（および通信Ｉ／Ｆ）に相当し得る。
【００３４】
図示されない外部装置、または画像処理装置１００に内蔵され得る図示されない形状推定部が、距離算出部１０４から距離算出結果を受け取り、これに基づいて被写体３０の３次元形状を推定してもよい。形状推定部は、例えば前述のプロセッサに相当し得る。
【００３５】
以下、被写体３０に投射される計測用パターン、および当該被写体３０の撮影画像に対する対応ブロック探索部１０２の動作の詳細について図３乃至図６を用いて説明する。
計測用パターンの一例を図３に示す。計測用パターンは、第１のパターン群と、この第１のパターン群と第１の方向上で隣接する第２のパターン群と、・・・、第Ｖ−１のパターン群と第１の方向上で隣接する第Ｖのパターン群と、の合計Ｖ組のパターン群を含む。ここで、Ｖは、２以上の自然数であって、図３の例ではＶ＝３である。また、図３の例では、第１の方向は垂直方向である。また、各パターン群において、当該パターン群に対応する１種類のパターンが第１の方向に沿って少なくとも１つ（図３の例では２つ）繰り返し並べられる。
【００３６】
各パターンにおいて、当該パターンに対応する１種類の基本パターンが第１の方向に直交する第２の方向（図３の例では水平方向）に沿って繰り返し並べられる。第ｉ（ｉは、１以上Ｖ以下の任意の整数）の基本パターンは、それぞれ既定の周期Ｃｉを持ち、上記第２の方向に沿って連続して並べられたＨｉ個の明ブロックと、当該Ｈｉ個の明ブロックに続けて上記第２の方向に沿って連続して並べられたＬｉ（＞Ｈｉ）個の暗ブロックとを含む。すなわち、Ｃｉ＝Ｈｉ＋Ｌｉである。図３において、明ブロックは白の四角で表され、暗ブロックは点描模様の四角で表される。
【００３７】
Ｌｉの大きさ、特にＬｉの最小値は、各基本パターンに含まれる暗ブロックが同一または隣接する基本パターンに含まれる明ブロックにより完全につぶれないように定められることが好ましい。例えば、Ｌｉ＝２の基本パターンでは、２個の暗ブロックの左右に明ブロックが配置されることになるが、各明ブロックによりその周囲のおよそ１ブロック分がつぶれるとすれば、これら２個の暗ブロックが全てつぶれてしまうおそれがある。故に、かかるケースでは、Ｌｉの最小値は３以上とすることが好ましい。
【００３８】
また、各パターン群に含まれるパターンの数は、当該パターン群に含まれるいずれかの列の暗ブロックが第１の方向上で隣接する他のパターン群に含まれる明ブロックにより完全につぶれないように定められることが好ましい。例えば、特定の列に関して、あるパターン群には暗ブロック、上下で隣接する他のパターン群には明ブロックが配置されていると仮定する。各明ブロックによりその周囲のおよそ１ブロック分がつぶれるとすれば、このパターン群の上端行および下端行の上記特定の列に含まれる暗ブロックがつぶれることになる。
【００３９】
例えば図４に示される第１の画素ブロックにおいて、実際には図５に例示されるように、明ブロックからの光の漏れにより暗ブロックの一部がつぶれてしまうおそれがある。図５では、暗ブロックのうち明ブロックからの光の漏れにより明るく写る部分を暗ブロックよりも薄い点描模様で模式的に表現している。図５の例では、明ブロックの光の漏れがその周囲０．５ブロックに収まっている。故に、Ｌｉの最小値を２、各パターン群に含まれるパターンの数を２とすれば、それぞれの基本パターンにおける暗ブロックが完全につぶれることはない。すなわち、それぞれの基本パターンにおける明ブロックが、暗ブロックのつぶれにより第２の方向で隣接する他の基本パターンにおける明ブロックとつながることはない。
【００４０】
ここで、明ブロックは最も明るい画素値（強度）が割り当てられ、暗ブロックは例えば最も暗い画素値が割り当てられることを意味する。ただし、両者が区別可能であれば、これと異なる画素値が割り当てられてもよい。例えば、明ブロックおよび／または暗ブロックは、それぞれ、最も明るい／最も暗い以外の画素値が割り当てられてもよい。また、明ブロックおよび暗ブロックのサイズは、それぞれ第１の撮影画像および第２の撮影画像における１画素に相当するように定められてもよいし、これと異なるサイズに定められてもよい。以降の説明では、明ブロックおよび暗ブロックのサイズは、１画素に相当するように定められていることとする。
【００４１】
また、各パターン群に含まれる、第１の方向上で隣接する明ブロック同士を連結した明領域の各々において、当該明領域の第１の方向に沿ったサイズは第２の方向に沿ったサイズに比べて大きいこととする。例えば、図３の例であれば、明ブロックは略正方形であって、かつ、各パターン群が２つの第１の方向上で隣接するパターンを含むから、明領域は第１の方向のサイズ：第２の方向のサイズが２：１の長方形となる。なお、明ブロックおよび暗ブロックは略正方形に限られず、矩形またはその他の多角形、円形または楕円形などであり得る。
【００４２】
図３の例では、第１のパターン群において、２つの第１のパターンが垂直方向に沿って繰り返し並べられる。各第１のパターンにおいて、第１の基本パターンが水平方向に沿って、少なくとも１０セット繰り返し並べられている。第１の基本パターンは、「３」の周期を持ち、水平方向に沿って連続して並べられた１個の明ブロックと、当該１個の明ブロックに続けて水平方向に沿って連続して並べられた２個の暗ブロックとを含む。
【００４３】
同様に、図３の例では、第２のパターン群において、２つの第２のパターンが垂直方向に沿って繰り返し並べられる。各第２のパターンにおいて、第２の基本パターンが水平方向に沿って、少なくとも７．５セット繰り返し並べられている。第２の基本パターンは、「４」の周期を持ち、水平方向に沿って連続して並べられた１個の明ブロックと、当該１個の明ブロックに続けて水平方向に沿って連続して並べられた３個の暗ブロックとを含む。
【００４４】
同様に図３の例では、第３のパターン群において、２つの第３のパターンが垂直方向に沿って繰り返し並べられる。各第３のパターンにおいて、第３の基本パターンが水平方向に沿って、少なくとも６セット繰り返し並べられている。第３の基本パターンは、「５」の周期を持ち、水平方向に沿って連続して並べられた１個の明ブロックと、当該１個の明ブロックに続けて水平方向に沿って連続して並べられた４個の暗ブロックとを含む。
【００４５】
さらに、これらＶ組のパターン群が、上記第１の方向に沿って繰り返し並べられる。図３の例では、第１，・・・，第３のパターン群が、垂直方向に沿って少なくとも２セット繰り返し並べられている。
【００４６】
対応ブロック探索部１０２における探索単位となる画素ブロックの必要サイズは、Ｖ種の基本パターンのそれぞれにおけるＣ１，・・・，ＣＶの最小値（以降、これをＣｍｉｎと称する）と、Ｖ種の基本パターンのそれぞれにおけるＬ１，・・・，ＬＶの最大値（以降、これをＬｍａｘと称する）と、第１の方向に繰り返し並べられるＶ組のパターン群の１組分の行数（パターン数）とによって定められる。
【００４７】
具体的には、第１の（または第２の）画素ブロックは、第１の（または第２の）撮影画像における第１の方向の射影方向に、Ｖ組のパターン群以上のサイズを有することが好ましい。画素ブロックのサイズがこれより小さいと、１つの画素ブロックに第１，・・・，第Ｖのパターン群の全てを収めることができない。すなわち、同一の画素ブロックが短い周期で出現し、マッチングの誤りが生じやすくなる。
【００４８】
他方、第１の（または第２の）の画素ブロックは、第１の（または第２の）撮影画像における第２の方向の射影方向に、Ｃｍｉｎ×２およびＬｍａｘのうち大きな一方の数の明ブロック（または暗ブロック）以上のサイズを有することが好ましい。画素ブロックのサイズがＣｍｉｎ×２個の明ブロック（または暗ブロック）のサイズよりも小さいと、計測用パターンにおける周期がＣｍｉｎ以上の行、すなわち計測用パターンにおける全ての行について、画素ブロック内のいずれの領域に対応するかを特定できないおそれがある。例えば、Ｃｍｉｎ＝３であるにも関わらず、画素ブロックに５個の明ブロックまたは暗ブロックしか収まらないとすると、当該画素ブロック内の各行に対応する領域が全て、暗、暗、明、暗、暗の並びのブロックであった場合に、当該各行が計測用パターンのおけるいずれの領域に対応するかを特定することができない。
【００４９】
また、画素ブロックのサイズがＬｍａｘ個の暗ブロックのサイズよりも小さいと、計測用パターンにおいてＬｍａｘ個の暗ブロックを含む基本パターンが配置された行に対応する画素ブロック内の領域が全て暗ブロックであった場合に、当該領域がＬｍａｘ個の暗ブロックのうちのどこからどこまでに対応しているのかを特定することができないおそれがある。例えば、Ｌｍａｘ＝７であるにも関わらず、画素ブロックに６個の暗ブロックしか収まらないとすると、７個の暗ブロックを含む基本パターンが配置された行に対応する画素ブロック内の領域が全て暗ブロックであった場合に、これら６個の暗ブロックが連続する７個の暗ブロックのうちの最初の暗ブロックを含むのかそれとも最後の暗ブロックを含むのかを区別することができない。
【００５０】
図３の例では、Ｖ＝３であって、各パターン群に含まれるパターンの数は２であり、Ｃｍｉｎ＝３、Ｌｍａｘ＝４である。故に、第１の（または第２の）画素ブロックは、第１の（または第２の）撮影画像における垂直方向および水平方向の射影方向にそれぞれ、６個の明ブロック（または暗ブロック）以上×６個の明ブロック（または暗ブロック）以上のサイズを有することが好ましい。
【００５１】
画素ブロックのサイズが大きくなるほど、マッチングの計算量は大きくなる。他方、画素ブロックのサイズが大きくなるほど、第１の撮影画像または第２の撮影画像において明ブロックまたは暗ブロックの明暗が反転していた場合に、各パターンの周期性を利用してその誤りを推定、訂正しやすくなる。
【００５２】
ここで、それぞれの基本パターンの周期、すなわちＣ１，・・・，ＣＶは、互いに素な自然数であることが好ましい。第２の撮影画像を画素ブロック単位で探索した場合に、同一の画素ブロックが出現する周期は、Ｃ１，・・・，ＣＶの最小公倍数（図３の例では、６０（＝３×４×５）となる。故に、Ｃ１，・・・，ＣＶが、互いに素な自然数、より好ましくは全て素数となるように定めれば、画素ブロックの必要サイズ（これは、前述のようにＣ１，・・・，ＣＶの最小値およびＬ１，・・・，ＬＶの最大値によって決まる）を抑えつつ、同一の画素ブロックが出現する周期を大きくできる。これにより、第２の撮影画像において同一の画素ブロック間の距離が十分に確保され、マッチングの誤りが生じにくくなる。同一の画素ブロック間の距離は、期待される視差／深度の最大値に応じて設定されてよい。
【００５３】
また、対応ブロック探索部１０２は、探索を効率的に行うために、最初に最大周期のパターンについてマッチングを行い、それからより小さな周期のパターンについて順次マッチングを行う。
【００５４】
すなわち最初に、対応ブロック探索部１０２は、第１の画素ブロックのうち最大周期のパターンを表す領域にマッチする第１の領域を第２の撮影画像から探索する。例えば、対応ブロック探索部１０２は、第１の領域が発見されるまで、第２の画素ブロックの候補を第２の方向（の射影方向）に１画素ずつずらしながら探索を継続する。
【００５５】
そして、第１の領域が発見された場合には、対応ブロック探索部１０２は、現在の第２の画素ブロックの候補において２番目に大きな周期のパターンを表す第２の領域を特定し、これが第１の画素ブロックのうち当該パターンを表す領域にマッチするか否かを判定する。なお、第２の領域を特定するには、例えば、第２の撮影画像において上記第１の領域を、最大周期のパターンおよび２番目に大きな周期のパターンの位置関係に応じて第２の撮影画像における第１の方向（の射影方向）に沿ってずらせばよい。
【００５６】
第２の領域が第１の画素ブロックのうち２番目に大きな周期のパターンを表す領域にマッチしなければ、対応ブロック探索部１０２は、第２の画素ブロックの候補を第２の方向に上記最大周期分ずらして、同様に第２の領域を特定し、これが第１の画素ブロックのうち当該パターンを表す領域にマッチするか否かを判定すればよい。他方、両者がマッチすれば、対応ブロック探索部１０２は、より小さな周期のパターンについて、同様の処理を繰り返せばよい。
【００５７】
このように最大周期のパターンについて最初にマッチングを行うことで、残りのパターンについてマッチしなかった場合には、第２の画素ブロックの候補を上記最大周期分ずつずらして探索を継続することができる。これは、第２の画素ブロックの候補を第２の方向に沿って単純に１画素ずつずらしながら探索を行う場合に比べて効率が良い。
【００５８】
具体的には、図３の例において１画素ずつずらしながら探索を行うと、最大６０（＝３×４×５）回も第２の画素ブロックの候補を動かす必要がある。他方、上記探索法によれば、第２の画素ブロックの候補を動かす回数は、高々１６回で済む。この内訳は、最大周期のパターンのマッチングのために最大５回、そして残りのパターンのマッチングのために最大１１回（（６０−５）／５）である。
【００５９】
一例として、図４に例示される第１の画素ブロックに対応する第２の画素ブロックを、図６に例示される第２の撮影画像（の一部）から探索する場合について説明する。
【００６０】
まず、対応ブロック探索部１０２は、第１の画素ブロックのうち最大周期のパターンを表す領域（暗、暗、暗、明、暗、暗、暗）にマッチする第１の領域を第２の撮影画像から探索する。対応ブロック探索部１０２は、第２の画素ブロックの候補を右に１画素ずつずらしながら探索を継続し、図６の第１行、第２列〜第８列に第１の領域を発見する。
【００６１】
次に、対応ブロック探索部１０２は、発見された第１の領域を下に４行分ずらした第２の領域（図６の第５行、第２列〜第８列、暗、暗、明、暗、暗、暗、明）が第１の画素ブロックのうち２番目に大きい周期のパターンを表す領域（暗、暗、明、暗、暗、暗、明）にマッチするか否かを判定する。
【００６２】
今回の第２の領域は第１の画素ブロックのうち２番目に大きい周期のパターンを表す領域にマッチする。故に、対応ブロック探索部１０２は、発見された第２の領域を上に２行分ずらした第３の領域（図６の第３行、第２列〜第８列、暗、明、暗、暗、明、暗、暗）が第１の画素ブロックのうち３番目に大きい周期のパターンを表す領域（暗、暗、明、暗、暗、明、暗）にマッチするか否かを判定する。
【００６３】
しかしながら、今回の第３の領域は第１の画素ブロックのうち３番目に大きい周期のパターンを表す領域にマッチしない。故に、対応ブロック探索部１０２は、第２の画素ブロックの候補を右に５列分ずらして、同様に第２の領域（図６の第２行、第７列〜第１３列、暗、明、暗、暗、暗、明、暗）を特定し、これが第１の画素ブロックのうち当該パターンを表す領域（暗、暗、明、暗、暗、暗、明）にマッチするか否かを判定する。
【００６４】
しかしながら、今回の第２の領域は第１の画素ブロックのうち２番目に大きい周期のパターンを表す領域にマッチしない。故に、対応ブロック探索部１０２は、第２の画素ブロックの候補を右に５列分ずらして、同様の処理を行う。
【００６５】
結局、第２の領域が図６の第５行、第２２列〜第２８列（暗、暗、明、暗、暗、暗、明）にあるときに、第１の画素ブロックのうち２番目に大きい周期のパターンを表す領域に再びマッチする。故に、対応ブロック探索部１０２は、発見された第２の領域を上に２行分ずらした第３の領域（図６の第３行、第２２列〜第２８列、暗、暗、明、暗、暗、明、暗）が第１の画素ブロックのうち３番目に大きい周期のパターンを表す領域（暗、暗、明、暗、暗、明、暗）にマッチするか否かを判定する。
【００６６】
今回の第３の領域は、第１の画素ブロックのうち第３番目に大きい周期のパターンを表す領域にマッチする。故に、対応ブロック探索部１０２は、現在の候補を第２の画素ブロックとして確定させる。
【００６７】
以下、図７を用いて、画像処理装置１００およびその周辺装置の動作を説明する。
【００６８】
まず、プロジェクター２０が、プロジェクター／カメラ制御装置１０からの命令に従って、被写体３０に計測用パターンを投射する（ステップＳ２０１）。プロジェクター２０は、少なくとも次のステップＳ２０２が終了するまで、被写体３０に計測用パターンを投射し続ける必要がある。
【００６９】
次に、左カメラ４１および右カメラ４２がそれぞれ、プロジェクター／カメラ制御装置１０からの命令に従って、被写体３０を撮影し、第１の撮影画像および第２の撮影画像を生成する（ステップＳ２０２）。ステップＳ２０２において生成された第１の撮影画像および第２の撮影画像は、画像処理装置１００内の撮影画像取得部１０１によって取得される。ステップＳ２０２の後に処理はステップＳ２０３へと進む。
【００７０】
ステップＳ２０３において、画像処理装置１００内の対応ブロック探索部１０２は、第１の撮影画像内の未処理の画素の中から注目画素を決定する。注目画素は、例えばラスタスキャン順、またはその他の順序で順番に選定され得る。
【００７１】
対応ブロック探索部１０２は、ステップＳ２０３において決定した注目画素を含む第１の画素ブロックを抽出する（ステップＳ２０４）。第１の画素ブロックの必要サイズについては前述の通りである。例えば、対応ブロック探索部１０２は、注目画素が中心に位置するように第１の画素ブロックを抽出してよい。
【００７２】
対応ブロック探索部１０２は、ステップＳ２０４において抽出した第１の画素ブロックに対応する第２の画素ブロックを第２の撮影画像から探索する（ステップＳ２１０）。なお、ステップＳ２１０の詳細は、図７の説明の後に図８を用いて説明する。
【００７３】
画像処理装置１００内の視差算出部１０３は、ステップＳ２１０において得られたマッチング結果に基づいて、ステップＳ２０３において決定した注目画素に関する左カメラ４１および右カメラ４２の視差を算出する（ステップＳ２０５）。
【００７４】
画像処理装置１００内の距離算出部１０４は、ステップＳ２０５において得られた視差算出結果に基づいて、左カメラ４１および右カメラ４２から被写体３０における注目画素に対応する点までの距離、すなわち深度を算出する（ステップＳ２０６）。そして、処理はステップＳ２０７へ進む。
【００７５】
ステップＳ２０７において、第１の撮影画像の各画素についてステップＳ２０３、ステップ２０４、ステップＳ２１０、ステップＳ２０５およびステップＳ２０６の処理が済んでいれば図７の動作は終了し、未処理の画素が残存していれば処理はステップＳ２０３に戻る。
【００７６】
なお、ステップＳ２０５およびステップＳ２０６は、第１の撮影画像の各画素についてマッチング（ステップＳ２０３、ステップＳ２０４およびステップＳ２１０）が完了した後にまとめて行われてもよい。
【００７７】
次に、図８を用いて、図７のステップＳ２１０の詳細を説明する。
まず、対応ブロック探索部１０２は、第２の撮影画像から第２の画素ブロックの初期候補（の位置）を決定する（ステップＳ２１１）。一例として、対応ブロック探索部１０２は、前回のステップＳ２１０の実行時に当時の第１の画素ブロックとマッチすると判定された前回の第２の画素ブロックの位置に基づいて、今回の第２の画素ブロックの初期候補の位置を決定してもよい。
【００７８】
次に、対応ブロック探索部１０２は、第１の画素ブロックにおいて最も周期の長い行ｒ１を探索する（ステップＳ２１２）。なお、過去のステップＳ２１２の実行時に探索されたｒ１がそのまま今回も当てはまる場合には、ステップＳ２１２は省略され得る。ステップＳ２１２の後に、処理はステップＳ２１３へ進む。
【００７９】
ステップＳ２１３において、対応ブロック探索部１０２は、第２の画素ブロックの現在の候補の第ｒ１行目が、第１の画素ブロックの第ｒ１行目と一致するか否かを判定する。両者が一致することは、第１の画素ブロックのうち最大周期のパターンを表す領域にマッチする第１の領域を第２の撮影画像から探索できたことを意味する。両者が一致すれば処理はステップＳ２１５へ進み、両者が一致しなければ処理はステップＳ２１４へ戻る。
【００８０】
ステップＳ２１４において、対応ブロック探索部１０２は、第２の画素ブロックの現在の候補を、１画素分水平方向（例えば右）にずらす。なお、ここでの水平方向は、より一般化すれば前述の第２の方向、すなわち基本パターンが繰り返し並べられる方向を指す。ステップＳ２１４の後に、処理はステップＳ２１３へ戻る。
【００８１】
ステップＳ２１５において、対応ブロック探索部１０２は、第１の画素ブロックにおいて、現在の候補に対してマッチング未判定の行のうち最も周期の長い行ｒ２を探索する。なお、このｒ２の値は、ステップＳ２１５が実行される度に更新され得る。ステップＳ２１５の後に、処理はステップＳ２１６へ進む。
【００８２】
ステップＳ２１６において、対応ブロック探索部１０２は、第２の画素ブロックの現在の候補の第ｒ２行目が、第１の画素ブロックの第ｒ２行目と一致するか否かを判定する。両者が一致すれば処理はステップＳ２１８へ進み、そうでなければ処理はステップＳ２１７へ進む。
【００８３】
ステップＳ２１７において、対応ブロック探索部１０２は、第２の画素ブロックの現在の候補を、第ｒ１行の１周期分水平方向（例えば右）にずらす。なお、ここでの水平方向は、より一般化すれば前述の第２の方向、すなわち基本パターンが繰り返し並べられる方向を指す。ステップＳ２１７の後に、処理はステップＳ２１５へ戻る。なお、ステップＳ２１７において第２の画素ブロックの候補が切り替わるので、ステップＳ２１５ではｒ２の値も２番目に大きな周期の行を示す値にリセットされる。
【００８４】
ステップＳ２１８において、第１の画素ブロックの全行について第２の画素ブロックの候補の全行とのマッチングが済んでいれば処理はステップＳ２１９へ進み、マッチング未判定の行が残存していれば処理はステップＳ２１５に戻る。この場合に、ステップＳ２１５では、ｒ２はより小さな周期の行を示す値に更新される。
【００８５】
ステップＳ２１９において、対応ブロック探索部１０２は、第２の画素ブロックの現在の候補を、ステップＳ２０４において抽出された第１の画素ブロックにマッチする第２の画素ブロックとして確定させる。ステップＳ２１９を以て、ステップＳ２１０の処理は終了する。
【００８６】
以上説明したように、第１の実施形態に係る画像処理装置は、それぞれにおいて明暗が周期的に遷移し、かつ、明ブロックに比べて暗ブロックが多く配置される複数の異なるパターン群を第１の方向に沿って並べた計測用パターンが投射された被写体を撮影した２画像間のマッチングを行う。また、各パターン群に含まれる、第１の方向上で隣接する明ブロック同士を連結した明領域の各々において、当該明領域の第１の方向に沿ったサイズは第２の方向に沿ったサイズに比べて大きい。故に、この計測用パターンによれば、第１の撮影画像および第２の撮影画像において明ブロックの周囲の暗ブロックが多少つぶれたとしても、各基本パターンに含まれる明ブロックが第２の方向で隣接する他の基本パターンに含まれる明ブロックとつながることはないので、マッチングが可能となる。
【００８７】
また、この計測用パターンによれば、明ブロックおよび暗ブロックが周期的に出現するので、ランダムドットパターンに比べて明暗の空間的な偏りが小さく、空間分解能の局所的な低下を抑制できる。さらに、この計測用パターンによれば、周期の大きい行から順に画素ブロックのマッチングを行うことで効率を向上させることができる。さらに、この計測用パターンによれば、第１の撮影画像または第２の撮影画像において明ブロックまたは暗ブロックの明暗が反転していた場合に、各パターンの周期性を利用してその誤りを推定、訂正できることもある。故に、この計測用パターンは、明暗の変動に対してロバストである。
【００８８】
（第２の実施形態）  
次に、第２の実施形態を説明する。本実施形態は、計測用パターンにおいて第１の実施形態と相違するものの、その他の点については第１の実施形態と同一または類似であり得る。
【００８９】
故に、以降の説明では、第２の実施形態において被写体３０に投射される計測用パターン、および当該被写体３０の撮影画像に対する対応ブロック探索部１０２の動作の詳細について図９乃至図１２を用いて説明する。
【００９０】
計測用パターンの一例を図９に示す。計測用パターンは、第１の明暗パターンと、この第１の明暗パターンと第１の方向上で全暗パターンを介して隣接する第２の明暗パターンと、・・・、第Ｖ−１の明暗パターンと第１の方向上で全暗パターンを介して隣接する第Ｖの明暗パターンと、の合計２×Ｖ個のパターンを含む。ここで、Ｖは、２以上の自然数であって、図９の例ではＶ＝３である。また、図９の例では、第１の方向は垂直方向である。
【００９１】
各全暗パターンにおいて、暗ブロックが第２の方向に沿って繰り返し並べられる。また、各明暗パターンにおいて、当該明暗パターンに対応する１種類の基本パターンが第１の方向に直交する第２の方向（図９の例では水平方向）に沿って繰り返し並べられる。第ｉ（ｉは、１以上Ｖ以下の任意の整数）の基本パターンは、それぞれ既定の周期Ｃｉを持ち、上記第２の方向に沿って連続して並べられたＨｉ個の明ブロックと、当該Ｈｉ個の明ブロックに続けて上記第２の方向に沿って連続して並べられたＬｉ（＞Ｈｉ）個の暗ブロックとを含む。すなわち、Ｃｉ＝Ｈｉ＋Ｌｉである。図９において、明ブロックは白の四角で表され、暗ブロックは点描模様の四角で表される。
【００９２】
Ｌｉの大きさ、特にＬｉの最小値は、各基本パターンに含まれる暗ブロックが同一または隣接する基本パターンに含まれる明ブロックにより完全につぶれないように定められることが好ましい。例えば、Ｌｉ＝２の基本パターンでは、２個の暗ブロックの左右に明ブロックが配置されることになるが、各明ブロックによりその周囲のおよそ１ブロック分がつぶれるとすれば、これら２個の暗ブロックが全てつぶれてしまうおそれがある。故に、かかるケースでは、Ｌｉの最小値は３以上とすることが好ましい。
【００９３】
また、明暗パターン同士の間隙に配置される全暗パターンの数は、当該全暗パターンを介して隣接する明暗パターンの一方に含まれる暗ブロックが他方に含まれる明ブロックにより完全につぶれないように定められることが好ましい。例えば、１つの全暗パターンを介して隣接する明暗パターンについて、上側の明暗パターンのある列には暗ブロックが配置され、下側の明暗パターンの同列には明ブロックが配置されていると仮定する。各明ブロックによりその周囲のおよそ２ブロック分がつぶれるとすれば、上側の明暗パターンの暗ブロックが下側の明暗パターンの明ブロックによってつぶれることになる。
【００９４】
例えば図１０に示される第１の画素ブロックにおいて、実際には図１１に例示されるように、明ブロックからの光の漏れにより暗ブロックの一部がつぶれてしまうおそれがある。図１１では、暗ブロックのうち明ブロックからの光の漏れにより明るく写る部分を暗ブロックよりも薄い点描模様で模式的に表現している。図１１の例では、明ブロックの光の漏れがその周囲０．５ブロックに収まっている。故に、明暗パターン同士の間隙に配置される全暗パターンの数を１つとすれば、それぞれの基本パターンにおける暗ブロックが完全につぶれることはない。すなわち、それぞれの基本パターンにおける明ブロックが、暗ブロックのつぶれにより第２の方向で隣接する他の基本パターンにおける明ブロックとつながることはない。ここで、明ブロックおよび暗ブロックの定義は、第１の実施形態と同一または類似であってよい。
【００９５】
図９の例では、第１の明暗パターンにおいて、第１の基本パターンが水平方向に沿って、少なくとも１０セット繰り返し並べられている。第１の基本パターンは、「３」の周期を持ち、水平方向に沿って連続して並べられた１個の明ブロックと、当該１個の明ブロックに続けて水平方向に沿って連続して並べられた２個の暗ブロックとを含む。
【００９６】
同様に、図９の例では、第２の明暗パターンにおいて、第２の基本パターンが水平方向に沿って、少なくとも７．５セット繰り返し並べられている。第２の基本パターンは、「４」の周期を持ち、水平方向に沿って連続して並べられた１個の明ブロックと、当該１個の明ブロックに続けて水平方向に沿って連続して並べられた３個の暗ブロックとを含む。
【００９７】
同様に図９の例では、第３の明暗パターンにおいて、第３の基本パターンが水平方向に沿って、少なくとも６セット繰り返し並べられている。第３の基本パターンは、「５」の周期を持ち、水平方向に沿って連続して並べられた１個の明ブロックと、当該１個の明ブロックに続けて水平方向に沿って連続して並べられた４個の暗ブロックとを含む。
【００９８】
さらに、これら２×Ｖ個のパターン（１つずつ交互に配置された明暗パターンおよび全暗パターン）が、上記第１の方向に沿って繰り返し並べられる。図９の例では、第１の明暗パターン，全暗パターン，・・・，第３の明暗パターン，全暗パターンが、垂直方向に沿って少なくとも２セット繰り返し並べられている。
【００９９】
対応ブロック探索部１０２における探索単位となる画素ブロックの必要サイズは、Ｖ種の基本パターンのそれぞれにおけるＣ１，・・・，ＣＶの最小値（以降、これをＣｍｉｎと称する）と、Ｖ種の基本パターンのそれぞれにおけるＬ１，・・・，ＬＶの最大値（以降、これをＬｍａｘと称する）と、第１の方向に繰り返し並べられるそれぞれのセットの行数（パターン数）２×Ｖとによって定められる。
【０１００】
具体的には、第１の（または第２の）画素ブロックは、第１の（または第２の）撮影画像における第１の方向の射影方向に、上記２×Ｖ個のパターン以上のサイズを有することが好ましい。画素ブロックのサイズがこれより小さいと、１つの画素ブロックに第１，・・・，第Ｖの明暗パターンの全てを収めることができない。すなわち、同一の画素ブロックが短い周期で出現し、マッチングの誤りが生じやすくなる。
【０１０１】
他方、第１の（または第２の）の画素ブロックは、第１の（または第２の）撮影画像における第２の方向の射影方向に、Ｃｍｉｎ×２およびＬｍａｘのうち大きな一方の数の明ブロック（または暗ブロック）以上のサイズを有することが好ましい。画素ブロックのサイズがＣｍｉｎ×２個の明ブロック（または暗ブロック）のサイズよりも小さいと、計測用パターンにおける周期がＣｍｉｎ以上の行、すなわち計測用パターンにおける全ての行について、画素ブロック内のいずれの領域に対応するかを特定できないおそれがある。例えば、Ｃｍｉｎ＝３であるにも関わらず、画素ブロックに５個の明ブロックまたは暗ブロックしか収まらないとすると、当該画素ブロック内の各行に対応する領域が全て、暗、暗、明、暗、暗の並びのブロックであった場合に、当該各行が計測用パターンのおけるいずれの領域に対応するかを特定することができない。
【０１０２】
また、画素ブロックのサイズがＬｍａｘ個の暗ブロックのサイズよりも小さいと、計測用パターンにおいてＬｍａｘ個の暗ブロックを含む基本パターンが配置された行に対応する画素ブロック内の領域が全て暗ブロックであった場合に、当該領域がＬｍａｘ個の暗ブロックのうちのどこからどこまでに対応しているのかを特定することができないおそれがある。例えば、Ｌｍａｘ＝７であるにも関わらず、画素ブロックに６個の暗ブロックしか収まらないとすると、７個の暗ブロックを含む基本パターンが配置された行に対応する画素ブロック内の領域が全て暗ブロックであった場合に、これら６個の暗ブロックが連続する７個の暗ブロックのうちの最初の暗ブロックを含むのかそれとも最後の暗ブロックを含むのかを区別することができない。
【０１０３】
図９の例では、Ｖ＝３であって、Ｃｍｉｎ＝３、Ｌｍａｘ＝４である。故に、第１の（または第２の）画素ブロックは、第１の（または第２の）撮影画像における垂直方向および水平方向の射影方向にそれぞれ、６個の明ブロック（または暗ブロック）以上×６個の明ブロック（または暗ブロック）以上のサイズを有することが好ましい。
【０１０４】
画素ブロックのサイズが大きくなるほど、マッチングの計算量は大きくなる。他方、画素ブロックのサイズが大きくなるほど、第１の撮影画像または第２の撮影画像において明ブロックまたは暗ブロックの明暗が反転していた場合に、各明暗パターンの周期性を利用してその誤りを推定、訂正しやすくなる。
【０１０５】
ここで、それぞれの基本パターンの周期、すなわちＣ１，・・・，ＣＶは、互いに素な自然数であることが好ましい。第２の撮影画像を画素ブロック単位で探索した場合に、同一の画素ブロックが出現する周期は、Ｃ１，・・・，ＣＶの最小公倍数（図９の例では、６０（＝３×４×５）となる。故に、Ｃ１，・・・，ＣＶが、互いに素な自然数、より好ましくは全て素数となるように定めれば、画素ブロックの必要サイズ（これは、前述のようにＣ１，・・・，ＣＶの最小値およびＬ１，・・・，ＬＶの最大値によって決まる）を抑えつつ、同一の画素ブロックが出現する周期を大きくできる。これにより、第２の撮影画像において同一の画素ブロック間の距離が十分に確保され、マッチングの誤りが生じにくくなる。同一の画素ブロック間の距離は、期待される視差／深度の最大値に応じて設定されてよい。
【０１０６】
また、対応ブロック探索部１０２は、探索を効率的に行うために、最初に最大周期の明暗パターンについてマッチングを行い、それからより小さな周期の明暗パターンについて順次マッチングを行う。
【０１０７】
すなわち最初に、対応ブロック探索部１０２は、第１の画素ブロックのうち最大周期の明暗パターンを表す領域にマッチする第１の領域を第２の撮影画像から探索する。例えば、対応ブロック探索部１０２は、第１の領域が発見されるまで、第２の画素ブロックの候補を第２の方向（の射影方向）に１画素ずつずらしながら探索を継続する。
【０１０８】
そして、第１の領域が発見された場合には、対応ブロック探索部１０２は、現在の第２の画素ブロックの候補において２番目に大きな周期の明暗パターンを表す第２の領域を特定し、これが第１の画素ブロックのうち当該明暗パターンを表す領域にマッチするか否かを判定する。なお、第２の領域を特定するには、例えば、第２の撮影画像において上記第１の領域を、最大周期の明暗パターンおよび２番目に大きな周期の明暗パターンの位置関係に応じて第２の撮影画像における第１の方向（の射影方向）に沿ってずらせばよい。
【０１０９】
第２の領域が第１の画素ブロックのうち２番目に大きな周期の明暗パターンを表す領域にマッチしなければ、対応ブロック探索部１０２は、第２の画素ブロックの候補を第２の方向に上記最大周期分ずらして、同様に第２の領域を特定し、これが第１の画素ブロックのうち当該明暗パターンを表す領域にマッチするか否かを判定すればよい。他方、両者がマッチすれば、対応ブロック探索部１０２は、より小さな周期の明暗パターンについて、同様の処理を繰り返せばよい。
【０１１０】
このように最大周期の明暗パターンについて最初にマッチングを行うことで、残りの明暗パターンについてマッチしなかった場合には、第２の画素ブロックの候補を上記最大周期分ずつずらして探索を継続することができる。これは、第２の画素ブロックの候補を第２の方向に沿って単純に１画素ずつずらしながら探索を行う場合に比べて効率が良い。
【０１１１】
具体的には、図９の例において１画素ずつずらしながら探索を行うと、最大６０（＝３×４×５）回も第２の画素ブロックの候補を動かす必要がある。他方、上記探索法によれば、第２の画素ブロックの候補を動かす回数は、高々１６回で済む。この内訳は、最大周期の明暗パターンのマッチングのために最大５回、そして残りの明暗パターンのマッチングのために最大１１回（（６０−５）／５）である。
【０１１２】
一例として、図１０に例示される第１の画素ブロックに対応する第２の画素ブロックを、図１２に例示される第２の撮影画像（の一部）から探索する場合について説明する。
【０１１３】
まず、対応ブロック探索部１０２は、第１の画素ブロックのうち最大周期の明暗パターンを表す領域（暗、暗、暗、明、暗、暗、暗）にマッチする第１の領域を第２の撮影画像から探索する。対応ブロック探索部１０２は、第２の画素ブロックの候補を右に１画素ずつずらしながら探索を継続し、図１２の第１行、第２列〜第８列に第１の領域を発見する。
【０１１４】
次に、対応ブロック探索部１０２は、発見された第１の領域を下に４行分ずらした第２の領域（図１２の第５行、第２列〜第８列、暗、暗、明、暗、暗、暗、明）が第１の画素ブロックのうち２番目に大きい周期の明暗パターンを表す領域（暗、暗、明、暗、暗、暗、明）にマッチするか否かを判定する。
【０１１５】
今回の第２の領域は第１の画素ブロックのうち２番目に大きい周期の明暗パターンを表す領域にマッチする。故に、対応ブロック探索部１０２は、発見された第２の領域を上に２行分ずらした第３の領域（図１２の第３行、第２列〜第８列、暗、明、暗、暗、明、暗、暗）が第１の画素ブロックのうち３番目に大きい周期の明暗パターンを表す領域（暗、暗、明、暗、暗、明、暗）にマッチするか否かを判定する。
【０１１６】
しかしながら、今回の第３の領域は第１の画素ブロックのうち３番目に大きい周期の明暗パターンを表す領域にマッチしない。故に、対応ブロック探索部１０２は、第２の画素ブロックの候補を右に５列分ずらして、同様に第２の領域（図１２の第２行、第７列〜第１３列、暗、明、暗、暗、暗、明、暗）を特定し、これが第１の画素ブロックのうち当該明暗パターンを表す領域（暗、暗、明、暗、暗、暗、明）にマッチするか否かを判定する。
【０１１７】
しかしながら、今回の第２の領域は第１の画素ブロックのうち２番目に大きい周期の明暗パターンを表す領域にマッチしない。故に、対応ブロック探索部１０２は、第２の画素ブロックの候補を右に５列分ずらして、同様の処理を行う。
【０１１８】
結局、第２の領域が図１２の第５行、第２２列〜第２８列（暗、暗、明、暗、暗、暗、明）にあるときに、第１の画素ブロックのうち２番目に大きい周期の明暗パターンを表す領域に再びマッチする。故に、対応ブロック探索部１０２は、発見された第２の領域を上に２行分ずらした第３の領域（図１２の第３行、第２２列〜第２８列、暗、暗、明、暗、暗、明、暗）が第１の画素ブロックのうち３番目に大きい周期の明暗パターンを表す領域（暗、暗、明、暗、暗、明、暗）にマッチするか否かを判定する。
【０１１９】
今回の第３の領域は、第１の画素ブロックのうち第３番目に大きい周期の明暗パターンを表す領域にマッチする。故に、対応ブロック探索部１０２は、現在の候補を第２の画素ブロックとして確定させる。
【０１２０】
以上説明したように、第２の実施形態に係る画像処理装置は、それぞれにおいて明暗が周期的に遷移し、かつ、明ブロックに比べて暗ブロックが多く配置される複数の異なる明暗パターンの各々を第１の方向に沿って並べた計測用パターンが投射された被写体を撮影した２画像間のマッチングを行う。また、この計測用パターンにおいて、明暗パターン同士の間隙には全暗パターンが配置される。故に、この計測用パターンによれば、第１の撮影画像および第２の撮影画像において明ブロックの周囲の暗ブロックが多少つぶれたとしても、各基本パターンに含まれる明ブロックが第２の方向で隣接する他の基本パターンに含まれる明ブロックとつながることはないので、マッチングが可能となる。
【０１２１】
また、この計測用パターンによれば、明ブロックおよび暗ブロックが周期的に出現するので、ランダムドットパターンに比べて明暗の空間的な偏りが小さく、空間分解能の局所的な低下を抑制できる。さらに、この計測用パターンによれば、周期の大きい行から順に画素ブロックのマッチングを行うことで効率を向上させることができる。さらに、この計測用パターンによれば、第１の撮影画像または第２の撮影画像において明ブロックまたは暗ブロックの明暗が反転していた場合に、各明暗パターンの周期性を利用してその誤りを推定、訂正できることもある。故に、この計測用パターンは、明暗の変動に対してロバストである。
【０１２２】
（第３の実施形態）
次に、第３の実施形態を説明する。本実施形態は、計測用パターンにおいて第１の実施形態および第２の実施形態と相違するものの、その他の点については第１の実施形態と同一または類似であり得る。
【０１２３】
故に、以降の説明では、第３の実施形態において被写体３０に投射される計測用パターンについて図１３および図１４を用いて説明する。なお、本実施形態における計測用パターンによれば、第１の実施形態および第２の実施形態とは異なり明暗ブロックの周期性を利用したマッチングを適用できないものの、例えばランダムドットパターンの場合と同様の既存のマッチングを適用できる。
【０１２４】
計測用パターンの一例を図１４に示す。図１４の計測用パターンは、図１３に例示されるパターン（以降、ベースパターンと称する）に、例えばラプラシアンフィルタなどのエッジ検出処理を施すことで得られるパターンに相当する。このベースパターンは、明ブロックおよび暗ブロックをランダムまたは疑似ランダムに配列したパターンに相当する。
【０１２５】
図１４の計測用パターンによれば、図１３のベースパターンにおけるエッジ部分に限って明領域が出現する。すなわち、この計測用パターンにおいて、明領域は暗領域に比べて狭く、かつ、ランダムな折れ線状に形成される。
【０１２６】
以上説明したように、第３の実施形態に係る画像処理装置は、明領域および暗領域をランダムまたは疑似ランダムに配列したベースパターンにエッジ検出処理を施すことで得られるパターンに相当する計測用パターンが投射された被写体を撮影した２画像間のマッチングを行う。すなわち、この計測用パターンにおいて、明領域は暗領域に比べて狭く形成される。故に、この計測用パターンによれば、第１の撮影画像および第２の撮影画像において明領域の周囲の暗領域が多少つぶれたとしても、計測用パターンの各行に含まれる明領域が同一行内で暗領域を介して隣接する他の明領域とつながることはないので、マッチングが可能となる。また、この計測用パターンにおいて、明領域はランダムな折れ線状に形成される。故に、この計測用パターンによれば、ベースパターンにおける明ブロックおよび暗ブロックの配置に依存するものの、第２の撮影画像において同一の画素ブロック間の距離が十分に確保されやすく、マッチングの誤りが生じにくくなる。
【０１２７】
上述の実施形態は、本発明の概念の理解を助けるための具体例を示しているに過ぎず、本発明の範囲を限定することを意図されていない。実施形態は、本発明の要旨を逸脱しない範囲で、様々な構成要素の付加、削除または転換をすることができる。
【０１２８】
上述の実施形態では、いくつかの機能部を説明したが、これらは各機能部の実装の一例に過ぎない。例えば、１つの装置に実装されると説明された複数の機能部が複数の別々の装置に亘って実装されることもあり得るし、逆に複数の別々の装置に亘って実装されると説明された機能部が１つの装置に実装されることもあり得る。
【０１２９】
上記各実施形態において説明された種々の機能部は、回路を用いることで実現されてもよい。回路は、特定の機能を実現する専用回路であってもよいし、プロセッサのような汎用回路であってもよい。
【０１３０】
上記各実施形態の処理の少なくとも一部は、例えば汎用のコンピュータに搭載されたプロセッサを基本ハードウェアとして用いることでも実現可能である。上記処理を実現するプログラムは、コンピュータで読み取り可能な記録媒体に格納して提供されてもよい。プログラムは、インストール可能な形式のファイルまたは実行可能な形式のファイルとして記録媒体に記憶される。記録媒体としては、磁気ディスク、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ等）、光磁気ディスク（ＭＯ等）、半導体メモリなどである。記録媒体は、プログラムを記憶でき、かつ、コンピュータが読み取り可能であれば、何れであってもよい。また、上記処理を実現するプログラムを、インターネットなどのネットワークに接続されたコンピュータ（サーバ）上に格納し、ネットワーク経由でコンピュータ（クライアント）にダウンロードさせてもよい。
【符号の説明】
【０１３１】
１０・・・プロジェクター／カメラ制御装置
２０・・・プロジェクター
３０・・・被写体
４１・・・左カメラ
４２・・・右カメラ
１００・・・画像処理装置
１０１・・・撮影画像取得部
１０２・・・対応ブロック探索部
１０３・・・視差算出部
１０４・・・距離算出部
【図１】
2019184549.tif 000003
【図２】
2019184549.tif 000004
【図３】
2019184549.tif 000005
【図４】
2019184549.tif 000006
【図５】
2019184549.tif 000007
【図６】
2019184549.tif 000008
【図７】
2019184549.tif 000009
【図８】
2019184549.tif 000010
【図９】
2019184549.tif 000011
【図１０】
2019184549.tif 000012
【図１１】
2019184549.tif 000013
【図１２】
2019184549.tif 000014
【図１３】
2019184549.tif 000015
【図１４】
2019184549.tif 000016