(57)【要約】【課題】投影後のパターン画像を構成するパターン要素に対して適切に配列における位置情報を付与する。【解決手段】複数のパターン要素がグリッド状に配列されたパターン画像を、前記パターン要素の座標情報とともに取得する取得部と、取得した前記パターン要素それぞれに対して、前記座標情報を用いて算出された他のパターン要素との距離が最も近い前記パターン要素である隣接要素を少なくとも２方向ごとに特定する隣接要素特定部と、隣接する前記パターン要素同士を連結して連結成分としてグループ化する連結部と、前記連結成分に含まれる前記パターン要素のうち、始点となる前記パターン要素から順に、予め定められた規則性にしたがって、前記配列内の位置情報を割り当てる割当部と、を備える。【選択図】図１
2014002718.tif 000002
【特許請求の範囲】
【請求項１】
複数のパターン要素がグリッド状に配列されたパターン画像を、前記パターン要素の座標情報とともに取得する取得部と、
取得した前記パターン要素それぞれに対して、前記座標情報を用いて算出された他のパターン要素との距離が最も近い前記パターン要素である隣接要素を少なくとも２方向ごとに特定する隣接要素特定部と、
隣接する前記パターン要素同士を連結して連結成分としてグループ化する連結部と、
前記連結成分に含まれる前記パターン要素のうち、始点となる前記パターン要素から順に、予め定められた規則性にしたがって、前記配列内の位置情報を割り当てる割当部と、
を備えることを特徴とするパターン処理装置。
【請求項２】
前記連結成分に含まれる前記パターン要素の要素数が、予め定められた条件を満たすか否かを判定し、満たさない場合には、前記連結成分を校正用の前記パターン画像からは除外する検査部を
更に備えることを特徴とする請求項１に記載のパターン処理装置。
【請求項３】
前記パターン要素の座標情報を、元の座標系を線形結合した座標系へと変換する座標変換部と、
前記パターン要素を、前記線形結合した後の座標情報の値のいずれかによって、並べ替えを行う並べ替え部と、
を更に備え、
前記割当部は、並べ替えに用いた座標が並び替えの順で最初に位置する前記パターン要素を前記始点に設定する
ことを特徴とする請求項１、又は２に記載のパターン処理装置。
【請求項４】
前記隣接要素特定部は、前記複数のパターン要素から１の注目要素を選択し、前記注目要素とそれぞれ他のパターン要素との間の前記方向における距離を算出し、前記距離が第１の閾値以下であり、かつ最も近い前記パターン要素を前記隣接要素として特定する
ことを特徴とする請求項１、又は２に記載のパターン処理装置。
【請求項５】
前記隣接要素特定部は、前記位置情報が割り当てられた隣接する前記パターン要素間の距離が、隣接方向において他の隣接する前記パターン要素間の距離と比較して有意に大きい場合、前記パターン要素を前記隣接要素から除外する
こと特徴とする請求項１、又は２に記載のパターン処理装置。
【請求項６】
前記位置情報は、Ｎ次の配列（Ｎは正の整数）における位置情報により構成され、
前記割当部は、前記パターン要素それぞれに割り当てたそれぞれの配列次元における位置情報成分が同じ値であるパターン要素の個数をカウントし、前記個数がそれぞれの配列次元に含まれるべき前記パターン要素の数として予め設定された範囲である配列次元において、前記位置情報が最小であるパターン要素を前記始点として再設定し、設定された前記始点を基準に前記パターン要素それぞれに新たな前記位置情報を割り当てる
ことを特徴とする請求項１、又は２に記載のパターン処理装置。
【請求項７】
複数のパターン要素がグリッド状に配列されたパターン画像を、前記パターン要素の座標情報とともに取得する取得ステップと、
取得した前記パターン要素それぞれに対して、前記座標情報を用いて算出された他のパターン要素との距離が最も近い前記パターン要素である隣接要素を少なくとも２方向ごとに特定する隣接要素特定ステップと、
隣接する前記パターン要素同士を連結して連結成分としてグループ化する連結ステップと、
前記連結成分に含まれる前記パターン要素のうち、始点となる前記パターン要素から順に、予め定められた規則性にしたがって、前記配列内の位置情報を割り当てる割当ステップと、
を含むことを特徴とするパターン処理方法。
【請求項８】
コンピュータに、
複数のパターン要素がグリッド状に配列されたパターン画像を、前記パターン要素の座標情報とともに取得する取得ステップと、
取得した前記パターン要素それぞれに対して、前記座標情報を用いて算出された他のパターン要素との距離が最も近い前記パターン要素である隣接要素を少なくとも２方向ごとに特定する隣接要素特定ステップと、
隣接する前記パターン要素同士を連結して連結成分としてグループ化する連結ステップと、
前記連結成分に含まれる前記パターン要素のうち、始点となる前記パターン要素から順に、予め定められた規則性にしたがって、前記配列内の位置情報を割り当てる割当ステップと、
を実行させるためのパターン処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン処理装置、パターン処理方法、パターン処理プログラムに関する。
【背景技術】
【０００２】
通常、プロジェクタからスクリーンへ投影される画像には、プロジェクタとスクリーンの相対的な位置関係により台形歪みが生じる。また、投影されるスクリーンの局所的な凹凸やねじれによる非線形歪みが見られる場合もある。
【０００３】
こうした歪みを補正するために、特許文献１においては、特定の図形配列からなる校正用のパターン画像を投影したスクリーンをデジタルカメラ等で撮像し、図形配列に基づいて撮像画像上で抽出される特徴点の理想的な位置と実際の抽出位置とのずれから歪みの程度を算出し、算出された歪みを解消するように補正された画像をプロジェクタから投影する技術を開示している。
【０００４】
このように理想的な状態の画像と、歪みのある画像との特徴点同士を比較する場合、特徴要素に対してそれぞれ列成分、及び行成分からなるグリッド配列情報を付与し、それぞれ同じ配列情報が割り当てられた特徴点同士を比較することにより歪み量を算出する方法が一般的である。
【０００５】
そこで、上記の特許文献１においては、投影された画像中の特徴要素に対しては、元の投影前の画像における特徴要素から最も近い位置に存在する特徴点に対して、同じグリッド配列情報が付与されるようになっている。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述のような技術にあっては、歪みの量が少ない場合にあっては有効ではあるが、歪みが大きい場合、例えばプロジェクタの設定台自体が大きく傾いている場合等にあっては、異なる位置の特徴点が元の画像における別の特徴点と最も近い位置にくることもあり、その場合誤った配列情報が特徴点に割り当てられてしまうこととなる。
【０００７】
本発明は、上記課題に鑑みてなされたものであり、投影後のパターン画像を構成するパターン要素に対して適切に配列における位置情報を付与することができるパターン処理装置を提供することにある。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するために、本発明は、複数のパターン要素がグリッド状に配列されたパターン画像を、前記パターン要素の座標情報とともに取得する取得部と、取得した前記パターン要素それぞれに対して、前記座標情報を用いて算出された他の要素パターンとの距離が最も近い前記パターン要素である隣接要素を少なくとも２方向ごとに特定する隣接要素特定部と、隣接する前記パターン要素同士を連結した連結成分を生成する連結部と、前記連結成分に含まれる前記パターン要素のうち、始点となる前記パターン要素から順に、特定された前記パターン要素が隣接する順番にしたがって、前記配列内の位置情報を割り当てる割当部と、を備える。
【発明の効果】
【０００９】
本発明によれば、投影後のパターン画像を構成するパターン要素に対して適切に配列における位置情報を付与することができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、第１の実施の形態にかかるパターン処理装置の構成を示すブロック図である。
【図２−１】図２−１は、第１の実施形態における投影される校正用パターン画像のデータの一例を示す図である。
【図２−２】図２−２は、第１の実施形態における実際に投影された校正用パターン画像の一例を示す図である。
【図３】図３は、第１の実施形態にかかるパターン処理の流れを示すフロー図である。
【図４】図４は、第１の実施形態におけるｕ，ｖ座標系を示す図である。
【図５】図５は、第１の実施形態におけるｕ，ｖ座標系を示す図である。
【図６】図６は、第１の実施形態において左側隣接要素を特定する処理の流れを示すフロー図である。
【図７】図７は、第１の実施形態において上側隣接要素を特定する処理の流れを示すフロー図である。
【図８】図８は、第１の実施形態において、特定された隣接要素の関係を示す図である。
【図９】図９は、第１の実施形態において、隣接要素がないパターン要素の例を示す図である。
【図１０】図１０は、第１の実施形態において、抽出された連結成分の例を示す図である。
【図１１】図１１は、第１の実施形態において、抽出された連結成分の例を示す図である。
【図１２】図１２は、第１の実施形態において、検査処理の流れを示すフロー図である。
【図１３】図１３は、第２の実施形態において、要素間の距離を示す図である。
【図１４】図１４は、第３の実施形態において、始点となる要素がノイズであった場合を示す図である。
【図１５】図１５は、第４の実施形態において、３次元の座標空間を示す図である。
【図１６】図１６は、第４の実施形態において、３次元の座標空間を示す図である。
【図１７】図１７は、パターン処理装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１１】
以下に添付図面を参照して、パターン処理装置の実施の形態を詳細に説明する。実施形態においては、パターン処理装置をプロジェクタに具体化した例を示す。
【００１２】
（第１の実施形態）
図１は、第１の実施の形態にかかるパターン処理装置であるプロジェクタ１の構成を示すブロック図である。プロジェクタ１は、スクリーン１０に対して予め定められた歪み校正用のパターン画像データを投影する。投影された校正用のパターン画像データは、デジタルカメラ２０によって撮影され、撮影データは入力ケーブルなどを通じて、プロジェクタ１に対して入力される。
【００１３】
プロジェクタ１は、ＣＰＵ１０１、記憶部１０２、Ｉ／Ｆ１０３、投影部１０４、パターン取得部１０５、隣接要素特定部１０６、連結部１０７、割当部１０８、検査部１０９、座標変換部１１０、及び並べ替え部１１１を備えている。記憶部１０２は、ハードディスクやＲＯＭ、及びＲＡＭなどにより構成されており、プロジェクタ１内において各種パターンに対する処理が行われた際の途中の状態のデータが保存されたり、投影される校正用のパターン画像データが記憶されていたりする。Ｉ／Ｆ１０３は、プロジェクタ１に接続された機器との間でのデータの入出力を行う。デジタルカメラ２０が撮影した投影された校正用のパターン画像の撮影データはＩ／Ｆ１０３を通じてプロジェクタ１に入力される。
【００１４】
投影部１０４は、記憶部１０２に記憶された校正用のパターン画像に対して、プロジェクタ１の設定に基づく画像処理が行われた画像データを、スクリーン１０に対して投影する。
【００１５】
パターン取得部１０５は、入力された撮影データから、校正用パターン画像を構成するパターン要素と、パターン要素の座標情報とを取得する。図２−１は、校正用パターン画像を示した図である。また、図２−２は、投影されたパターン画像をデジタルカメラにて撮影した撮影データを示した図である。校正用パターン画像１００は、Ｍ×Ｎ個のパターン要素１００ａがグリッド状に配置された画像データである。校正用パターン画像１００は、投影されると図２−２に示されるように、歪みが生じる場合がある。このように生じた歪みを補正するために、投影された校正用パターン画像１００は、デジタルカメラ２０によって撮影され、撮影データをパターン取得部１０５が取得する。パターン取得部１０５は取得したパターン要素をその座標情報と関連付けて、それぞれ記憶部１０２におけるバッファに記憶する。
【００１６】
そして、この取得されたパターン画像と、元の画像データとをそれぞれ比較することにより、投影時に歪みがどれだけ発生しているかが把握され歪み補正のための補正量が算出される。なお、この歪み算出の際には、グリッド状の配列において、同じ位置に存在するパターン要素同士を比較することにより算出される。そのためには、投影されたパターン画像に対しても、配列における位置情報を付与し、元のパターン画像データにおいて付与されている位置情報と同じ位置情報を付与されているパターン要素同士の間で、ずれの量を算出することが望ましい。そこで、以下において、投影されたパターン画像のパターン要素に対して、位置情報を付与する処理が行われる。
【００１７】
以下、取得されたパターン画像１００の撮影データに対して、列の位置情報と、行の位置情報とからなり、配列における位置情報を割り当てる処理の流れについて図３に基づき説明する。本実施形態においては、パターン要素がどのパターン要素と隣接しているかを特定することにより、特定された隣接関係を参照して、パターン要素に位置情報を付与していく。本実施形態においては、投影されたパターン画像の左上側に位置するパターン要素を位置情報の始点である＜０，０＞が付与されることを前提に説明する。
【００１８】
まず、座標変換部１１０は、パターン要素の座標情報を変換する（ステップＳ１０１）。具体的には、パターン要素の座標情報は図４に示されるように、Ｘ座標とＹ座標とから構成されている。図中における右方向がＸ軸における正の方向、下方向がＹ軸における正の方向である。以下では取得されたパターン要素の総数をＣ、第ｉ番目のパターン要素をＡ［ｉ］、その座標を（ｘ［ｉ］，ｙ［ｉ］）とする。
【００１９】
座標変換部１１０は、パターン要素の座標情報をその成分の線形結合で表される次式によって（ｘ，ｙ）座標系から（ｕ，ｖ）座標系へ変換する。
ｕ［ｉ］＝（ｘ［ｉ］−ｙ［ｉ］）／√２
ｖ［ｉ］＝（ｘ［ｉ］＋ｙ［ｉ］）／√２
【００２０】
このように、（ｕ，ｖ）座標系へと変換する理由としては、図５に示されるように、パターン要素のｖ座標に注目すると、ｖ座標において、あるパターン要素１００ａよりも、ｖ座標が小さいパターン要素１００ｂは、必ずパターン要素１００ａよりも上側、または左側に位置することとなる。なお、投影するパターン画像が、４５度傾けて投影されていれば、座標変換部１１０による線形結合を用いた変換は不要となる。また、投影時にパターン画像を傾ける処理をするのではなく、パターン要素の配置が元から４５度分ずれた態様になっていてもよい。この場合、座標変換部１１０による変換処理が不要となるため、処理の高速化を図ることができるようになる。
【００２１】
次いで、並び替え部１１１は、パターン要素をｖ座標を基準に、値の小さいものから順に並び替えを行う（図３：ステップＳ１０２）。並べ替えをすることにより、以降の処理において、ｖ座標の値を用いた処理を行う際により効率的に行うことができるようになる。並び替えがされたパターン要素１００ａには、ｖ座標の値が小さいものから順にｉ（１＜＝ｉ＜＝Ｃの整数）が付与され、元のパターン要素とは別のバッファに、並び替えられた順に記憶される。
【００２２】
次いで、隣接要素特定部１０６は、パターン要素同士の隣接要素を特定する処理を行う（図３：ステップＳ１０３）。本実施形態においては、あるパターン要素を選択し、選択したパターン要素に対して、上側、及び左側の２方向において隣接するパターン要素を特定する。なお、特定する方向は最終的に全てのパターン要素の位置が特定できればよく、少なくとも２方向であれば、例えば上と右、右と下、４方向全てを特定するようにしてもよい。また、上述の並び替えにおいては、特定する方向を上と左方向としたため、上側と左側に位置するパターン要素を特定しやすいように、ｖ座標の大小で並べ替えることとしたが、並び替えに使用する座標は、特定する方向に応じて変更するのがよい。
【００２３】
以下、図６、及び図７を用いて、隣接要素を特定する処理の流れについて説明する。図６は、ある選択されたパターン要素の左側に隣接するパターン要素を特定する処理の流れを示すフロー図である。図７は、ある選択されたパターン要素の上側に隣接するパターン要素を特定する処理の流れを示すフロー図である。
【００２４】
図６に示されるように、まず隣接要素特定部１０６は、ｉ＝１番目のパターン要素１００ａから処理を行うため、ｉ＝１とする（ステップＳ２０１）。ｉは並び替え後にパターン要素１００ａに付与された番号である。次いで、隣接要素特定部１０６は、最も距離の近いパターン要素の番号を示すＪｍｉnを０に、最小のパターン要素間の距離を示す閾値であるＤＮｍｉｎを、予め暫定に設定した閾値であり、各パターン要素間の距離の最大値として設定した値であるＴよりも１大きい値に、ｉ番目のパターン要素と比較するｊ番目のパターン要素を示す番号ｊをｉより１小さい値にそれぞれ設定する（ステップＳ２０２）。ｉよりも左側に存在する可能性のあるパターン要素１００ａのみを処理対象とすればよいため、ｊはｉよりも小さい値のみでよい。
【００２５】
次いで、隣接要素特定部１０６は、ｊが１以上であって、かつｖ[ｉ]−ｖ[ｊ]が閾値Ｔ以下であるか否かを判定する（ステップＳ２０３）。ｊが１より小さい場合は、すなわちｊが０となる場合は、ｉが１であるため、始点である場合や、選択したパターン要素Ａ[ｉ]を、左側にある可能性のある全てのパターン要素Ａ[ｊ]と比較し終わった場合である。また、ｖ[ｉ]−ｖ[ｊ]が閾値Ｔ以下であるかを判定することで、選択したパターン要素Ａ[ｉ]との距離が予め定めた閾値であるＴよりも大きいパターン要素Ａ[ｊ]は以降の処理の対象から除外することで、処理にかかる負荷を抑制している。
【００２６】
ｊが１以上であって、かつｖ[ｉ]−ｖ[ｊ]が閾値Ｔ以下であると判定された場合（ステップＳ２０３：Ｙｅｓ）、次いで隣接要素特定部１０６は、ｕ[ｊ]−ｕ[ｉ]が０より小さいか否かを判定する（ステップＳ２０４）。ｕ[ｉ]−ｕ[ｊ]は、ｊ番目のパターン要素１００ａがｉ番目のパターン要素１００ａよりも座標空間において上側に存在するか否かを判定するための値である。図６の処理では、選択したパターン要素１００ａの左側に隣接するパターン要素を特定することから、ｕ[ｉ]−ｕ[ｊ]が０より小さいパターン要素１００ａを検索する。ｕ[ｉ]−ｕ[ｊ]が０より小さいと判定された場合（ステップＳ２０４：Ｙｅｓ）、次いで、２つのパターン要素の座標、Ａ［ｉ］とＡ［ｊ］との間のベクトルのノルムであるＤＮを以下の式に沿って算出する（ステップＳ２０５）。
ＤＮ＝ＳＱＲＴ｛（ｕ［ｊ］−ｕ［ｉ］）２＋（ｖ［ｊ］−ｖ［ｉ］）２｝
【００２７】
次いで、隣接要素特定部１０６は、ＤＮがＴ以下であって、かつＤＮがＤＮ＜ＤＮｍｉｎであるか否かを判定する（ステップＳ２０６）。ＤＮがＴ以下であるか否かを判定することにより、パターン要素間の距離が予め定めた閾値であるＴより大きい場合は、以降の処理から除外することで、処理負担を抑制している。また、ＤＮをＤＮｍｉｎと比較することで、パターン要素がこれまで比較したパターン要素同士の間で最も距離が近いものであるか否かが判別される。ＤＮがＴ以下であって、かつＤＮ＜ＤＮｍｉｎであると判定された場合（ステップＳ２０６：Ｙｅｓ）、隣接要素特定部１０６は、ＤＮｍｉｎをＤＮの値に更新するとともに、Ｊｍｉｎにｊを代入する（ステップＳ２０７）。Ｊｍｉｎは、選択したパターン要素と最も距離の近いパターン要素１００ａの番号を示す値である。そして、隣接要素特定部１０６は、パターン要素のＡ［ｉ］の左隣接要素番号をＪｍｉｎとし、ステップＳ２０９へと移行する（ステップＳ２０８）。
【００２８】
一方、ｊが１より小さいか、ｖ[ｉ]−ｖ[ｊ]が閾値Ｔより大きい場合（ステップＳ２０３：Ｎｏ）、ｕ[ｊ]−ｕ[ｉ]が０以上の場合（ステップＳ２０４：Ｎｏ）、ＤＮがＴより大きいか、ＤＮがＤＮｍｉｎ以上であると判定された場合（ステップＳ２０６：Ｎｏ）、次のパターン要素と隣接関係にあるか否かの判定を行うべく、ｊを１減算する（ステップＳ２０９）。そして、ｊが１以上であるか否かが判定され（ステップＳ２１２）、ｊが１以上の場合は（ステップＳ２１２：Ｙｅｓ）、ステップＳ２０３へと戻り、ｊが１より小さい場合は（ステップＳ２１２：Ｎｏ）、ステップＳ２１０へと進む。
【００２９】
そして、ステップＳ２０８においてある選択されたパターン要素であるＡ[ｉ]についての左隣接要素が特定されると、隣接要素特定部１０６はｉを１加算し（ステップＳ２１０）、ｉが最大値であるＣに達したか否かを判定する（ステップＳ２１１）。ｉが最大値であるＣに達した場合（ステップＳ２１１：Ｙｅｓ）、処理は終了し、一方、ｉが最大値であるＣに達していないと判定された場合（ステップＳ２１１：Ｎｏ）、ステップＳ２０２から処理を繰り返す。
【００３０】
図７の上隣接要素を特定する処理においては、ステップＳ３０４のみが異なり、ｕ[ｉ]−ｕ[ｊ]が０より大きいか否かが判定される（ステップＳ３０４）。あるパターン要素１００ａのＡ[ｉ]よりもＡ[ｊ]が上側に存在する場合、ｕ[ｉ]−ｕ[ｊ]は０よりも大きくなる。したがって、上隣接要素を特定する場合、ステップＳ３０４の処理において、パターン要素１００ａが絞り込まれる。以上の処理では探索をｊ＝ｉ−１から始めてｊ＝１に向かって進め、ｖ［ｉ］−ｖ［ｊ］＞Ｔとなった時点で、それよりも小さいｊでは必ずｖ［ｉ］−ｖ［ｊ］＞Ｔ、ひいてはＤＮ＞Ｔであることが確実となることから探索を終了しており、処理にかかる負担をさらに削減している。
【００３１】
この処理を行うことにより、左側の隣接要素と、上側の隣接要素に同じパターン要素が特定されてしまうといった問題を防ぐことができる。上述のような方法で特定されたあるパターン要素１００ａのＡ[ｉ]の上隣接要素番号と、左隣接要素番号は、図８に示されるように、注目要素ごとに特定され、この対応関係は記憶部１０２におけるバッファに記憶される。なお図９に示されるように、グリッド配列の外周部に位置するパターン要素群１００ｃや、撮影データにおいてパターン要素にある欠損があり、左、又は上に欠損が存在するパターン要素群１００ｄに対しては、対応する左（上）隣接要素番号に「隣接なし」を意味する０を設定しておく。
【００３２】
隣接要素が特定できると、次いで連結部１０７は、パターン要素を連結する要素ラベリング処理を実施する（図３：ステップＳ１０４）。連結部１０７は、特定した隣接要素同士を連結してグループ化していき、連結成分を抽出し、それぞれのラベリングを付与する。一般にラベリングとは二値画像上の隣接する黒画素同士を連結していって黒画素連結成分を抽出する処理を指すが、ここでいう要素ラベリングは連結すべき対象要素が黒画素からパターン要素に置き換わったものであり、具体的な処理手順については従来から広く利用されている公知のラベリング手法をそのまま用いることができる。
【００３３】
図１０は連結成分の生成結果の一例を示している。同図には校正用のパターン画像に対応する第１の連結成分３００、及び投影されたパターン画像の撮像時に写りこんだ背景オブジェクトやノイズに由来する別の第二の連結成分４００も抽出されている。抽出された各連結成分３００、４００は、記憶部１０２のバッファに記憶される。
【００３４】
続いて、割当部１０８は、グリッドインデックス決定処理を行う（図３：ステップＳ１０５）。グリッドインデックス決定処理においては、抽出された連結成分３００、４００に含まれるパターン要素に対し、所属する連結成分内における位置情報を決定する。本実施形態では位置情報をグリッド列番号ｐ（０≦ｐ≦Ｍ−１）とグリッド行番号ｑ（０≦ｑ≦Ｎ−１）の組み合わせ＜ｐ，ｑ＞で示す。
【００３５】
具体的にはまず、それぞれの連結成分３００、４００の中でｖ座標の順に並び替えた順が先頭であるパターン要素を探し、連結成分３００、４００における始点とする。始点とは、連結成分３００、４００の中で最も左上に位置し、左隣接要素、及び上隣接要素を持たず、グリッドの開始列、及び開始行に対応する。始点となるパターン要素１００ａには位置情報として、＜０，０＞が割り当てられる。
【００３６】
割当部１０８は、始点となったパターン要素から、特定された隣接要素を参照し、始点を左隣接要素とするパターン要素には位置情報として＜１，０＞を付与する。また割当部１０８は、さらに＜１，０＞を左隣接要素とするパターン要素には＜２，０＞をというように、順に位置情報を割り当てる。
【００３７】
割当部１０８は、始点を上隣接要素とするパターン要素には位置情報として＜０，１＞を付与する。さらに割当部１０８は、＜０，１＞が割り当てられたパターン要素を左隣接要素とするパターン要素には＜１，１＞を、また＜０，１＞のパターン要素を上隣接要素とするパターン要素には＜０，２＞を、さらに＜０，２＞のパターン要素を左隣接要素とするパターン要素には＜１，２＞を、という順に位置情報を割り当てていく。以上の方法においては、少なくとも左隣接要素、及び上隣接要素のいずれかが存在しているパターン要素であれば、その位置情報を割り当てることができるようになる。なお、位置情報の割当の方法としては、このように各パターン要素が隣接する順番に従って割り当てる以外にも、予め定められた規則性にしたがって割当られればよい。例えば、視点が反対側に位置するパターン要素から始まって反対向きに位置情報が割り当てられてもよい。図１１には連結成分３００、４００それぞれに割り当てられた位置情報の例を示す。
【００３８】
位置情報が割当られた連結成分３００、４００は校正用のパターン画像として出力されて、元のパターン画像との比較によって歪み補正が実行されるが、本実施形態においては、出力の前に、ノイズなどに由来する連結成分３００を出力から除外するためのグリッド検査処理が実行される（図３：ステップＳ１０６）。
【００３９】
図１２は、グリッド検査処理の詳細を示すフロー図である。グリッド検査処理は、連結成分３００、４００ごとに実行される。図１２に示されるように、まず検査部１０９は、検査スコアであるＳと、位置情報のうち行成分であるｑの値をそれぞれ０に初期化する（ステップＳ４０１）。次いで、検査部１０９は、位置情報のうち列成分であるｐの値を０に初期化する（ステップＳ４０２）。
【００４０】
次いで、検査部１０９は、現在の＜ｐ，ｑ＞の位置情報が割当られたパターン要素が連結成分３００、４００中に存在しているか否かを判定する（ステップＳ４０３）。＜ｐ，ｑ＞の位置情報が割当られたパターン要素が連結成分３００、４００中に存在していないと判定された場合（ステップＳ４０３：Ｎｏ）、検査スコアＳの値が１加算される（ステップＳ４０４）。一方、＜ｐ，ｑ＞の位置情報が割当られたパターン要素が連結成分３００、４００中に存在している場合（ステップＳ４０３：Ｙｅｓ）、検査スコアＳを加算することなく、検査部１０９は、ｐがＭ−１であるか否かを判定する（ステップＳ４０５）。ｐがＭ−１でないと判定された場合（ステップＳ４０５：Ｎｏ）、すなわち未だある行において終点のパターン要素にまで検査が到達していない場合、検査部１０９はｐの値を１加算して、ステップＳ４０３からの処理を繰り返す（ステップＳ４０６）。
【００４１】
ｐがＭ−１であると判定された場合（ステップＳ４０５：Ｙｅｓ）、検査部１０９は、ｑがＮ−１であるか否かを判定する（ステップＳ４０７）。ｑがＮ−１でないと判定された場合（ステップＳ４０７：Ｎｏ）、すなわち未だ全てのパターン要素に対して検査が完了していない場合、検査部１０９はｑの値を１加算して、ステップＳ４０２からの処理を次の行に対して繰り返す（ステップＳ４０８）。一方、がＮ−１であると判定された場合（ステップＳ４０７：Ｙｅｓ）、検査部１０９は、検査スコアＳが予め定められた閾値ＴＳ以下であるか否かを判定する（ステップＳ４０９）。閾値ＴＳは、パターン要素が欠損する場合を想定して設定された数値である。検査スコアＳが予め定められた閾値ＴＳ以下の場合（ステップＳ４０９：Ｙｅｓ）、処理は終了し、その連結成分は校正用パターンとして出力される。一方、検査スコアＳが予め定められた閾値ＴＳより大きくなった場合（ステップＳ４０９：Ｎｏ）、検査部１０９は、連結成分を校正用パターン画像としての出力から除外する（ステップＳ４１０）。
【００４２】
上述した、連結成分２００の場合においては、元のパターン画像であるＭ×Ｎ個のパターン要素を含むため、検査スコアＳが閾値ＴＳより大きくなることはないため、出力から除外されることはない。一方、連結成分３００は、パターン要素が＜０，０＞、＜０，１＞、＜１，０＞、＜１，１＞、及び＜２，１＞のみであり、本来あるべきパターン要素数から、Ｍ×Ｎ−５のパターン要素が不足することから、検査スコアＳはＭ×Ｎ−５となり、通常であれば閾値ＴＳを越えてしまうため、連結成分３００は出力からは除外されることとなる。
【００４３】
こうして検査がなされた連結成分が、校正用のパターン画像として出力され、記憶部１０２に記憶されたパターン画像と、同じ位置情報が付与されたパターン要素同士を比較することでその歪みの量が算出され、歪み補正のための補正量が自動的に計算されるようになる。
【００４４】
以上に示した、本実施形態のパターン処理装置においては、投影されたパターン画像に対して、スキューや台形歪み、局所的な非線形歪み等、さまざまな歪みが生じている場合であっても、パターン画像を構成するパターン要素に対して適切にグリッド状の配置における位置情報を付与することができるようになる。
【００４５】
（第２の実施形態）
本実施形態においては、各パターン要素に対して、図６、及び図７における隣接要素を特定する処理の際に、ステップＳ２０６のＤＮ≦Ｔ、かつＤＮがＤＮｍｉｎより小さいという条件を満たすパターン要素Ａ[ｊ]が見つかった場合の処理が異なる。
【００４６】
通常はこのＡ［ｊ］がＡ［ｉ］の左隣接要素、又は上隣接要素となるが、撮影データに欠損があった場合、欠損箇所を飛ばして本来は２つ先となるべきパターン要素であるＡ[ｊ]を隣接要素として取得してしまっている可能性があり、その状態を図１３に示す。例えば、撮像時のカメラからスクリーンまでの撮影距離に柔軟性を持たせるために要素間距離の最大値である閾値Ｔを大きい値に設定した場合にこうした状況は発生しやすい。また、撮影距離が遠くてパターン画像全体が小さめに写っている場合などにおいても、図１３のような状況は発生しやすい。
【００４７】
そこで、本実施形態では、パターン要素のＡ［ｉ］とＡに対して求まった要素間距離ＤＮを、Ａ［ｊ］とその左隣接要素Ａ［ｋ］との要素間距離ＤＬと比較する。本来、ＤＮとＤＬには大きな差はないはずであるが、ここでは、仮にＤＮがＤＬの１．５倍よりも大きい、すなわちＤＮ＞ＤＬ×１．５が成り立つならば、Ａ［ｊ］を棄却し、注目要素Ａ［ｉ］の左隣接要素を「なし」と設定する処理を行う。
【００４８】
なお、左隣接候補Ａ［ｊ］が左隣接要素を持たない場合は以上の処理は行わない。本実施形態のプロジェクタ１においては、パターン要素の欠損が生じている場合に、誤って２つ先のパターン要素を隣接要素と特定してしまうエラーを回避できる。なお、１．５倍としたのは一例であり、乗数１．５を別の値に置き換えてもよいし、ＤＬを定数倍するかわりにＤＬに定数を加える式で判定するようにしてもよい。
【００４９】
（第３の実施形態）
上記の本実施形態においては、配列における位置情報の決定において、通常は連結成分の中で並べ替えられたパターン要素のうち先頭のものが始点となる。しかし図１４（ａ）に示すように、ノイズに相当するパターン要素を誤って始点としてしまい、開始列を誤って認識してしまう可能性がある。またノイズの位置次第で同様に開始行を誤ることもありえる。そこで、本実施形態においては、このようなノイズに由来する位置情報の誤った割当を検出、及び修正する構成が採用されている。
【００５０】
具体的には、図１４（ｂ）に示されるように、配列の位置情報＜ｉ，ｊ＞を一度割り当てた後、その列成分ｉごとに、列成分＝ｉ（位置情報成分）を持つカウント値Ｆ［ｉ］がカウントされる。また、同様にして行成分ｊごとに、行成分＝ｊを持つカウント値Ｇ［ｊ］がカウントされる。
【００５１】
図１４（ｂ）の場合、配列の位置情報で列成分＝０を持つパターン要素はノイズ相当の１つだけであるからＦ［０］＝１、列成分＝１を持つパターン要素は本来の開始列に相当するパターン要素群が対応し、Ｍ列Ｎ行で要素欠損がないとしてＦ［１］＝Ｎとなる。また行成分＝０を持つパターン要素は本来の開始行とパターン要素が対応し、Ｇ［０］＝Ｍ＋１となる。
【００５２】
そして、カウント値Ｆ［ｉ］が本来の行数Ｎと一致する列のうち最小のｉを改めてグリッドの開始列と定め、カウント値Ｇ［ｊ］が本来の列数Ｍと一致する行の最小のｊをあらためてグリッドの開始行と定める。
【００５３】
上記の処理は以下の式により示すことができる。
新開始列：ｉ０＝ＭＩＮ｛ｉ｜Ｎ＝Ｆ［ｉ］｝
新開始行：ｊ０＝ＭＩＮ｛ｊ｜Ｍ＝Ｇ［ｊ］｝
【００５４】
そして新しい開始列が列番号＝０を持つように各配列の位置情報の列成分からｉ０を差し引き、新しい開始行が行番号＝０を持つように行成分からｊ０を差し引く処理が行われる。本実施形態により、撮影データの中にノイズが存在していて始点を誤って割り当てていた場合であってもグリッド開始列・開始行を正しく割り当てることができるようになる。
【００５５】
なお、この場合本来の行数Ｎと一致するか否かで判定するのではなく、例えばカウントした個数が予め定めた所定の範囲内にあるか否かで判定し、範囲内であれば正しい行列として処理するようにしてもよい。また、２次元配列ではなく３次元配列の場合であっても、各配列ごとにパターン要素の数をカウントすることで、適用することも可能である。
【００５６】
（第４の実施形態）
以上に示した実施形態においては、校正用パターンが縦横の２次元で構成される画像を用いた場合を示したが、３次元のパターンを利用する場合についても本発明は適用可能である。図１５、及び図１６を用い３次元の場合について説明する。図１５に示されるように、３次元座標は、左右にて示されるＸ座標軸、上下にて示されるＹ座標軸、および奥と手前にて示されるＺ座標軸とから構成されている。
【００５７】
３次元座標空間においては、次式にしたがって（ｘ，ｙ，ｚ）から（ｕ，ｖ，ｗ）への変換を行う。
ｕ［ｉ］＝（ｘ［ｉ］−ｚ［ｉ］）／ＳＱＲＴ｛２｝
ｖ［ｉ］＝（−ｘ［ｉ］＋２＊ｙ［ｉ］−ｚ［ｉ］）／ＳＱＲＴ｛６｝
ｗ［ｉ］＝（ｘ［ｉ］＋ｙ［ｉ］＋ｚ［ｉ］）／ＳＱＲＴ｛３｝
【００５８】
本実施形態においては、左上奥側に位置するパターン要素を、始点として配列における位置情報を付与するものとする。したがって、並べ替え部１１１は、ｗ座標の値が小さいものから順に並べ替えを実施する。図１６は、並べ替え実施後の、（ｕ，ｖ，ｗ）座標空間における状態を示している。
【００５９】
３次元座標空間においては、あるパターン要素に対して、左隣接要素、上隣接要素、及び奥隣接要素の３つのパターン要素を特定する処理が行われる。左・上・奥の分別については、選択されたパターン要素から探索対象のパターン要素へ向かうベクトルをｕｖ平面へ射影したベクトルとｕ軸単位ベクトルとのなす角θにもとづき、９０°＜θ≦２１０°ならば左隣接要素、２１０°＜θ≦３３０°ならば上隣接要素、０≦θ≦９０°、または３３０°＜θ＜３６０°ならば奥隣接要素等のように判別することができる。この処理は図６、及び図７においては、ステップＳ２０４、及びＳ３０４のどの方向の隣接要素であるかを判定する処理が該当する。また、隣接要素は各方向においてｗ軸で示される距離が最も近いものが隣接要素として特定される。
【００６０】
隣接要素が特定されれば、そこから各パターン要素への位置情報の付与を行うことができて、抽出されたパターン要素の中で最もｗ座標の小さい要素を始点とし、位置情報＜０，０，０＞を割り当てる。以下、パターン要素ごとに特定された隣接関係を参照しつつ、各パターン要素の列位置情報、行位置情報、及び層位置情報を順次割り当てていけばよい。  
【００６１】
また、上記各実施形態においては、パターン画像は白黒によって示されたパターン要素が使用されていた。これに対し、パターン要素を配列の規則にしたがって、色づけするようにしておいてもよい。例えば赤色のパターン要素の右には緑、下には青が位置するように各パターン要素を配置する。また、緑のパターン要素の右には青が、下には赤が位置するようにパターン要素を配置する。また、青のパターン要素の右には赤が、下には緑が位置するようにパターン要素を配置する。このように、パターン要素を配置することで、パターン要素間の隣接関係を位置関係からは把握しにくい場合であっても、色情報を参照することで、パターン要素の隣接関係の特定の精度を向上させることができるようになる。
【００６２】
なお、パターン処理にかかるプログラムはコンピュータ上のプログラムに実行させることもできる。図１７は一般的なコンピュータの構成を示すハードウェア構成図であり、ＣＰＵ２０１、ハードディスク２０２、ディスプレイ２０３、通信装置２０４、ＣＤ−ＲＯＭドライブ２０５、メモリ２０６、及びキーボード／マウス２０７を備えている。例えば、ＣＤ−ＲＯＭ等の記録媒体に記録されたパターン処理プログラムを、ＣＤ−ＲＯＭドライブ２０５を通じて読み込み、実行時にはメモリ２０６上にロードされ、ＣＰＵ２０１からの指令によってプログラムの処理ステップが順次実行されるようにしてもよい。入力画像は、あらかじめハードディスク２０２上に蓄えられるか、または実行時に図示しないデジタルカメラを通じて取り込まれた後、メモリ２０６上にロードされて参照される。パターン抽出の結果はメモリ２０６に保存された後、利用の必要に応じてメモリ２０６から読み出され、ハードディスク２０２に書き出されたり、ディスプレイ２０３に出力されたり、通信装置２０４を介してネットワーク上へ送出されたり、あるいは図示しないプリンタを通じて紙上に印字されたりする。
【符号の説明】
【００６３】
１  プロジェクタ
１０  スクリーン
２０  デジタルカメラ
１００  校正用パターン画像
１００ａ  パターン要素
１０１  ＣＰＵ
１０２  記憶部
１０３  Ｉ／Ｆ
１０４  投影部
１０５  パターン取得部
１０６  隣接要素特定部
１０７  連結部
１０８  割当部
１０９  検査部
１１０  座標変換部
１１１  並べ替え部
２００  校正用パターン画像
２０２  ハードディスク
２０３  ディスプレイ
２０４  通信装置
２０５  ＣＤ−ＲＯＭドライブ
２０６  メモリ
２０７  キーボード／マウス
３００  連結成分
４００  連結成分
【先行技術文献】
【特許文献】
【００６４】
【特許文献１】特開２０１０−０２８４１１号公報
【図１】
2014002718.tif 000003
【図２−１】
2014002718.tif 000004
【図２−２】
2014002718.tif 000005
【図３】
2014002718.tif 000006
【図４】
2014002718.tif 000007
【図５】
2014002718.tif 000008
【図６】
2014002718.tif 000009
【図７】
2014002718.tif 000010
【図８】
2014002718.tif 000011
【図９】
2014002718.tif 000012
【図１０】
2014002718.tif 000013
【図１１】
2014002718.tif 000014
【図１２】
2014002718.tif 000015
【図１３】
2014002718.tif 000016
【図１４】
2014002718.tif 000017
【図１５】
2014002718.tif 000018
【図１６】
2014002718.tif 000019
【図１７】
2014002718.tif 000020