配列方向検出装置、配列方向検出方法および配列方向検出プログラム
【課題】点群に含まれる点列における複数の点の配列方向を容易かつ高精度に検出する。
【解決手段】配列方向検出装置では、検出対象である配列方向におよそ平行であることが判明している暫定配列方向に長く、かつ、その長さが配列方向に隣接する２つの点８１１の間の距離の最大値である点間最大距離の３倍以上である略矩形状の領域内に存在する点群８が撮像され、点群８の画像から凸包８２が生成される。そして、凸包８２の（−Ｘ）側の部分凸包８２１ａおよび（＋Ｘ）側の部分凸包８２１ｂにそれぞれ含まれる複数の線分のうち最長の線分を方向指示線分８２５ａ，８２５ｂとして特定し、方向指示線分８２５ａ，８２５ｂから、暫定配列方向を基準とする方向の平均値を配列方向として取得することにより、点群８に含まれる点列８１における複数の点８１１の配列方向を容易かつ高精度に検出することができる。
【解決手段】配列方向検出装置では、検出対象である配列方向におよそ平行であることが判明している暫定配列方向に長く、かつ、その長さが配列方向に隣接する２つの点８１１の間の距離の最大値である点間最大距離の３倍以上である略矩形状の領域内に存在する点群８が撮像され、点群８の画像から凸包８２が生成される。そして、凸包８２の（−Ｘ）側の部分凸包８２１ａおよび（＋Ｘ）側の部分凸包８２１ｂにそれぞれ含まれる複数の線分のうち最長の線分を方向指示線分８２５ａ，８２５ｂとして特定し、方向指示線分８２５ａ，８２５ｂから、暫定配列方向を基準とする方向の平均値を配列方向として取得することにより、点群８に含まれる点列８１における複数の点８１１の配列方向を容易かつ高精度に検出することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、配列方向に垂直な方向において互いに重なる複数の点列からなる点群から配列方向を検出する技術に関する。
【背景技術】
【０００２】
従来より、対象物の画像の傾きを求める方法の１つとして、対象物上に目印（いわゆる、アライメントマーク）を設けておき、画像中のアライメントマークの配列の傾きから画像の傾きを求める方法が知られている。
【０００３】
また、特許文献１では、走査方向に垂直な方向における位置を変更しつつ画像を走査方向に沿って複数回走査し、各走査において最初に出現する画素の集合である印刷開始点列（例えば、矩形の印刷領域の上辺の画素）を求め、印刷開始点列の傾きから画像の傾きを求める方法が開示されている。
【０００４】
特許文献２では、画像上においてセルである単位要素が縦方向および横方向に配列されており、各単位要素の重心位置をパターンマッチング処理により求め、縦方向の位置が近い重心を有する単位要素の集合（すなわち、横方向に並ぶ単位要素の集合であり、以下、「単位要素列」という。）を抽出し、当該単位要素列に含まれる複数の単位要素の重心を通る直線の傾きから画像の傾きを求める方法が開示されている。なお、上記重心を点と捉えた場合、多数の点から一の直線上に配列される複数の点を抽出する方法の１つであるハフ（Ｈｏｕｇｈ）変換を用いて単位要素列の複数の重心を通る直線を求めることが考えられるが、ハフ変換ではあらゆる方向を向く直線に対して投票処理を行って適切な直線を求めることになるため、処理時間が多大なものとなってしまう。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平７−８９０６３号公報
【特許文献２】特開２００５−３１３２１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、対象物にアライメントマークを設けて画像の傾きを求める方法では、対象物に対するアライメントマークの付加が必要となる上、画像中からアライメントマークを抽出する必要もあり、傾き検出に要する演算量が増大してしまう。
【０００７】
特許文献１の方法では、上述のように、矩形の印刷領域が設定されている画像の傾きを求めることは可能であるが、印刷領域の輪郭が矩形でない場合（例えば、曲線を含んだり凹凸がある場合）には、画像の傾きを精度良く求めることは困難である。
【０００８】
特許文献２の方法では、画像の傾きが少し大きくなると、一の単位要素列に含まれる複数の単位要素の重心位置と、当該単位要素列に隣接する他の単位要素列に含まれる複数の単位要素の重心位置とが縦方向において近接してしまい、隣接する２つの単位要素列を区別することが困難になって画像の傾きを精度良く求めることができなくなってしまう。また、隣接する単位要素列の間の距離が小さい場合にも同様に、隣接する２つの単位要素列に含まれる単位要素が一緒に抽出されてしまい、画像の傾きを精度良く求めることができなくなってしまう。
【０００９】
本発明は、上記課題に鑑みなされたものであり、点群に含まれる点列における複数の点の配列方向を容易かつ高精度に検出することを目的としている。
【課題を解決するための手段】
【００１０】
請求項１に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出装置であって、前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する撮像部と、前記撮像部からの出力に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する凸包生成部と、前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する配列方向取得部とを備える。
【００１１】
請求項２に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出装置であって、前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する撮像部と、前記撮像部からの出力に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する凸包生成部と、前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する配列方向取得部とを備える。
【００１２】
請求項３に記載の発明は、請求項１または２に記載の配列方向検出装置であって、前記方向指示線分から取得された前記配列方向が仮に決定された配列方向であり、前記撮像部、前記凸包生成部および前記配列方向取得部により、前記点群の前記暫定幅方向の他方側においても前記方向指示線分と同様にもう１つの方向指示線分が特定され、前記配列方向取得部が、前記方向指示線分の方向と前記もう１つの方向指示線分の方向とを用いて最終的な前記配列方向を取得する。
【００１３】
請求項４に記載の発明は、請求項１ないし３のいずれかに記載の配列方向検出装置であって、前記点群において、各点と少なくとも１つの他の点とが前記配列方向に垂直な幅方向に並ぶ。
【００１４】
請求項５に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出方法であって、ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する工程と、ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、ｃ）前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程とを備える。
【００１５】
請求項６に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出方法であって、ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する工程と、ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、ｃ）前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程とを備える。
【００１６】
請求項７に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出プログラムであって、前記配列方向検出プログラムのコンピュータによる実行は、前記コンピュータに、ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する工程と、ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、ｃ）前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程とを実行させる。
【００１７】
請求項８に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出プログラムであって、前記配列方向検出プログラムのコンピュータによる実行は、前記コンピュータに、ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する工程と、ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、ｃ）前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程とを実行させる。
【発明の効果】
【００１８】
本発明では、点群に含まれる点列における複数の点の配列方向を容易かつ高精度に検出することができる。
【図面の簡単な説明】
【００１９】
【図１】第１の実施の形態に係る配列方向検出装置を示す図である。
【図２】点群の画像を示す図である。
【図３】演算部の構成を示す図である。
【図４】演算部の機能を示すブロック図である。
【図５】配列方向の検出の流れを示す図である。
【図６】点群の画像を示す図である。
【図７】点群の画像を示す図である。
【図８】点群の画像を示す図である。
【図９】シリコン基板上の複数のチップの画像を示す図である。
【図１０】第２の実施の形態に係る配列方向検出装置による配列方向の検出の流れを示す図である。
【発明を実施するための形態】
【００２０】
図１は、本発明の第１の実施の形態に係る配列方向検出装置１の構成を示す図である。配列方向検出装置１は、図２にその一部を示す対象物９の画像８０中の複数の点列８１からなる点群８から、点列８１における複数の点８１１の配列方向を検出する装置である。図２では、図の理解を容易にするために、各点列８１を二点鎖線にて囲む。点群８では、複数の点列８１のそれぞれは、図２中のｘｙ平面上において所定の配列方向（図２中におけるｙ方向であり、ｘ方向およびｙ方向は点群８に対して固定された座標軸である。）に複数の点８１１が直線状に配列された点列であり、複数の点列８１は、当該配列方向に垂直な幅方向（すなわち、ｘ方向）において互いに重なっている。換言すれば、点群８では、図２中のｙ方向に平行に伸びる互いに平行な複数の点列８１がｘ方向に配列されている。
【００２１】
図１に示す配列方向検出装置１は、対象物９をガラス面上に保持する保持部１３、対象物９を撮像する撮像部１１、および、撮像部１１により取得された画像を受け付けて所定の演算を行う演算部１２を備える。撮像部１１は、印刷された面を下側（（−Ｚ）側）に向けて保持部１３に保持された対象物９の下方に配置され、対象物９の印刷された面の画像を取得する。
【００２２】
撮像部１１は、対象物９上において図１中のＸ方向に伸びる線状領域を撮像するラインセンサ１１１、対象物９上におけるラインセンサ１１１の撮像領域に光を照射する光照射部１１２、並びに、ラインセンサ１１１および光照射部１１２をＸ方向に垂直なＹ方向に移動するセンサ移動機構１１３を備える。本実施の形態では、ラインセンサ１１１は、線状に配列された複数のＣＣＤ（Charge Coupled Device）素子を備え、ラインセンサ１１１の線状の撮像領域は対象物９のＸ方向の全幅に亘る。
【００２３】
ここで、図１中のＸ方向およびＹ方向は、配列方向検出装置１に対して固定された既知の座標軸であり、ＸＹ平面と図２中のｘｙ平面とは平行である。図２中のｘ方向およびｙ方向はそれぞれ、Ｘ方向およびＹ方向におよそ平行であることは判明しているものの未知の座標軸であり、配列方向検出装置１では、既知のＹ方向に対するｙ方向の傾きが求められることにより、点列８１における複数の点８１１の配列方向が検出される。以下の説明では、複数の点８１１の配列方向であるｙ方向（すなわち、配列方向検出装置１の検出対象）におよそ平行なＹ方向を「暫定配列方向」といい、Ｙ方向に垂直なＸ方向を「暫定幅方向」という。
【００２４】
図３は、演算部１２の構成を示す図である。演算部１２は、通常のコンピュータと同様に、ＣＰＵ１０１、ＲＡＭ１０２、ＲＯＭ１０３、固定ディスク１０４、ディスプレイ１０５、および、入力部１０６等を接続した構成となっており、固定ディスク１０４内には、演算部１２により実行される配列方向検出プログラム１０４１が記憶される。図４は、演算部１２のＣＰＵ１０１等が配列方向検出プログラム１０４１に従って演算処理を実行することにより実現される機能を示すブロック図であり、図４中の凸包生成部１２１および配列方向取得部１２２が、ＣＰＵ１０１等により実現される機能に相当する。これらの機能は複数台のコンピュータにより実現されてもよい。
【００２５】
図５は、配列方向検出装置１による複数の点８１１の配列方向検出の流れを示す図である。図１に示す配列方向検出装置１では、まず、撮像部１１のラインセンサ１１１および光照射部１１２がＹ方向に走査されることにより、対象物９が撮像されて画像８０（図２参照）が演算部１２へと送られる（ステップＳ１１）。
【００２６】
本実施の形態では、図２に示す画像８０中の点群８の全体が、配列方向の検出に利用される対象点群となっている。点群８の複数の点列８１のそれぞれでは複数の点８１１が不等ピッチにて配列されており、複数の点列８１において配列方向であるｙ方向に隣接する２つの点８１１の間の距離の最大値（以下、「点間最大距離」という。）は既知とされる。対象点群である点群８は、暫定配列方向であるＹ方向に長い矩形状の領域８０１（図２において二点鎖線にて示す。）内に存在する。領域８０１のＹ方向の長さは、点間最大距離の３倍以上となっている。なお、図２では、図示の都合上、複数の点列８１のｘ方向におけるピッチを実際よりも大きく描いているが、実際には、隣接する点列８１の間の距離は点間最大距離よりもかなり小さい。
【００２７】
続いて、演算部１２の凸包生成部１２１（図４参照）により、撮像部１１（図１参照）からの出力である画像８０に基づいて、点群８の最も外側に位置する複数の点８１１を、図６に示すように直線にて結んで形成される凸包８２が生成される（ステップＳ１２）。具体的には、画像８０が二値化されて複数の点８１１が抽出され（すなわち、各点８１１を周囲の部位から孤立させて切り出し）、各点８１１の重心の位置が求められ、さらに、複数の点８１１のそれぞれの重心からグラハム（Ｇｒａｈａｍ）の方法等の既知の手法により凸包８２が求められる。なお、画像８０からの複数の点８１１の抽出はパターンマッチング等により行われてもよい。
【００２８】
次に、配列方向取得部１２２（図４参照）により、凸包８２の暫定幅方向の一方側（すなわち、（−Ｘ）側）の部分である部分凸包８２１ａが凸包８２から抽出される（ステップＳ１３）。図６では、図の理解を容易にするために、部分凸包８２１ａを二点鎖線にて囲む。そして、部分凸包８２１ａに含まれる複数の線分８２５のうち最長の線分が方向指示線分８２５ａとして特定され、暫定配列方向であるＹ方向を基準とする方向指示線分８２５ａの方向（例えば、Ｙ方向と方向指示線分８２５ａとの為す角度）が、各点列８１における複数の点８１１の仮に決定された配列方向（以下、「仮配列方向」という。）として取得される（ステップＳ１４）。
【００２９】
また、配列方向取得部１２２により、凸包８２の暫定幅方向の他方側（すなわち、（＋Ｘ）側）の部分であるもう１つの部分凸包８２１ｂが凸包８２から抽出され（ステップＳ１５）、上述の方向指示線分８２５ａと同様に、部分凸包８２１ｂに含まれる複数の線分８２５のうち最長の線分が方向指示線分８２５ｂとして特定される。そして、Ｙ方向を基準とする方向指示線分８２５ｂの方向（例えば、Ｙ方向と方向指示線分８２５ｂとの為す角度）が、各点列８１における複数の点８１１のもう１つの仮配列方向として取得される（ステップＳ１６）。
【００３０】
その後、方向指示線分８２５ａから取得された仮配列方向と方向指示線分８２５ｂから取得された仮配列方向との平均値が、最終的な配列方向として取得される（ステップＳ１７）。これにより、画像８０からの点群８の読み取り時に生じる可能性がある読取誤差等による影響を抑制して配列方向を精度良く取得することができる。
【００３１】
配列方向取得部１２２では、必ずしも上記平均値が最終的な配列方向とされる必要はなく、方向指示線分８２５ａの方向および方向指示線分８２５ｂの方向である２つの仮配列方向が用いられるのであれば、他の様々な方法により最終的な配列方向が取得されてよい。例えば、凸包８２の生成時に対象物９上の汚れ等を誤って点８１１として認識することにより、一方の方向指示線分の方向と暫定配列方向（Ｙ方向）との為す角度が、他方の方向指示線分の方向と暫定配列方向との為す角度に比べて明らかに大きくなってしまっている場合、Ｙ方向と為す角度が小さい方の方向指示線分の方向が最終的な配列方向として取得されてよい。
【００３２】
配列方向検出装置１は、例えば、印刷媒体である対象物９に印刷された暗号情報を示す点群８から暗号情報を読み取る際に利用される。図２に示す点群８では、各点列８１が「０」または「１」を示し、８つの点列８１により８桁のビット列からなる暗号情報が示される。点群８は、対象物９上の余白領域（すなわち、通常の画像が印刷される領域の周囲の領域）等に印刷される。点群８では、一の点列８１が示す値が「０」である場合には、当該点列８１における配列方向であるｙ方向の単位距離中に含まれる点８１１の個数（以下、「単位ドット数」という。）が所定の個数（以下、「ドット閾値」という。）以下とされ、当該点列８１が示す値が「１」である場合には、単位ドット数がドット閾値よりも大きくされる。
【００３３】
対象物９から暗号情報が読み取られる際には、既述のように、配列方向検出装置１により、対象物９の画像８０の取得、対象点群である点群８の凸包８２の生成、凸包８２からの部分凸包８２１ａの抽出（すなわち、部分凸包８２１ａの生成）、部分凸包８２１ａに基づく仮配列方向の取得、凸包８２からの部分凸包８２１ｂの抽出（すなわち、部分凸包８２１ｂの生成）、部分凸包８２１ｂに基づく仮配列方向の取得、および、２つの仮配列方向に基づく最終的な配列方向の取得（ステップＳ１１〜Ｓ１７）が行われる。
【００３４】
続いて、点群８における配列方向であるｙ方向が、暫定配列方向であるＹ方向に一致するように、ｙ方向とＹ方向との為す角度だけ点群８が回転される（具体的には、点群８の各点８１１のＸＹ座標系における座標が変換される）。そして、複数の点列８１のそれぞれの単位ドット数がＹ方向に沿って計数され、単位ドット数がドット閾値と比較されて各点列８１が示す値（「０」または「１」）が取得されることにより、対象物９から暗号情報が読み取られる。上記点群８の回転、各点列８１の単位ドット数の計数、および、各点列８１が示す値の取得は、配列方向検出装置１により行われてもよく、他の装置により行われてもよい。また、点群８の回転が行われることなく、基準となるＹ方向（暫定配列方向）と為す角度が既知となった配列方向に沿って各点列８１の単位ドット数の計数が行われてもよい。
【００３５】
以上に説明したように、配列方向検出装置１では、図２に示す領域８０１のように、暫定配列方向に長く、かつ、その長さが点間最大距離の３倍以上である略矩形状の領域内に存在する対象点群である点群８が撮像され、点群８の画像から凸包８２が生成される。このように、点群８の輪郭が上記の領域８０１の輪郭におよそ沿ったものとされることにより、点群８の凸包８２に含まれる複数の線分８２５のうち、一の点列８１に含まれる点８１１と他の点列８１に含まれる点８１１とを結ぶ線分よりも、一の点列８１に含まれる複数の点８１１を通る線分（すなわち、配列方向を向く線分）の方が確実に長くなる。このため、凸包８２の（−Ｘ）側の部分凸包８２１ａおよび（＋Ｘ）側の部分凸包８２１ｂにそれぞれ含まれる複数の線分のうち最長の線分を方向指示線分８２５ａ，８２５ｂとして特定し、方向指示線分８２５ａ，８２５ｂのそれぞれの方向を用いて最終的な配列方向を取得することにより、点群８に含まれる点列８１における複数の点８１１の配列方向を高精度に検出することができる。また、点群８を囲む凸包８２を利用することにより、ハフ変換のように非常に多数の方向について検討することなく、配列方向を容易に検出することができる。
【００３６】
配列方向検出装置１では、必ずしも点群８全体が凸包８２の形成に利用される対象点群とされる必要はなく、点群８の一部が対象点群とされてもよい。換言すれば、対象点群は、点群８の少なくとも一部であればよい。点群８の一部が対象点群とされる場合、点群８のうち、図７に示すように、暫定配列方向に長く、かつ、その長さが点間最大距離の３倍以上である略矩形状の領域８０１ａ内に存在する対象点群８ａが撮像部１１（図１参照）により撮像される。このように、対象点群８ａの輪郭が上記領域の輪郭におよそ沿ったものとされた状態で、対象点群８ａの凸包８２ａ（すなわち、対象点群８ａの最も外側に位置する点を直線にて結んで形成される凸包）の部分凸包８２１ａ，８２１ｂにて特定された方向指示線分８２５ａ，８２５ｂのそれぞれの方向を用いて配列方向を取得することにより、上記と同様に、点群８に含まれる点列８１（図２参照）における複数の点８１１の配列方向を容易かつ高精度に検出することができる。
【００３７】
配列方向検出装置１では、また、必ずしも部分凸包８２１ａ，８２１ｂにて特定された方向指示線分８２５ａ，８２５ｂの双方の方向を用いて配列方向が取得される必要はなく、例えば、方向指示線分８２５ｂを特定することなく、方向指示線分８２５ａの方向が最終的な配列方向として取得されてもよい。換言すれば、図５中のステップＳ１５〜Ｓ１７が省略され、ステップＳ１４にて求められた仮配列方向が最終的な配列方向とされる。この場合、撮像部１１（図１参照）では、図８に示すように、点群８の一部であって暫定幅方向の一方側である（−Ｘ）側の部位を含む対象点群８ｂが撮像される。そして、対象点群８ｂの凸包８２ｂの（−Ｘ）側の部分である部分凸包８２１ａが生成され、部分凸包８２１ａにて特定された方向指示線分８２５ａの方向が最終的な配列方向として取得される。これにより、点群８に含まれる点列８１（図２参照）における複数の点８１１の配列方向を容易かつ高精度に検出することができる。なお、配列方向検出装置１は、図２中のｘ方向に配列された点列の配列方向の検出に用いられてもよい。
【００３８】
配列方向検出装置１は、また、図９に示すシリコン基板である対象物９ａ上の複数のチップ９１の画像８０ａにおけるチップ９１の配列方向の検出にも利用されてよい。対象物９ａ上では、複数のチップ９１が対象物９ａに固定されたｘｙ座標系のｘ方向およびｙ方向に等ピッチにて配列されており、以下では、各チップ９１の重心を点８１１、配列方向であるｙ方向に配列された複数の点８１１を点列８１、配列方向に垂直な幅方向であるｘ方向に配列された複数の点列８１を点群８と捉えて説明する。点群８では、各点８１１と少なくとも他の点８１１とが幅方向に並んでいる。また、画像８０ａに固定されたＸＹ座標系のＹ方向を既知の暫定配列方向と呼び、Ｙ方向に垂直なＸ方向を暫定幅方向と呼ぶ。
【００３９】
配列方向検出装置１では、まず、上記と同様に、点群８の（少なくとも）一部であって暫定幅方向の一方側および他方側（（−Ｘ）側および（＋Ｘ）側）の部位を含み、かつ、暫定配列方向に長く、その長さが点間最大距離（この場合、ｙ方向における点８１１のピッチに等しい。）の３倍以上である領域内に存在する対象点群８ｃが撮像部１１（図１参照）により撮像される。図９では、図示の都合上、対象点群８ｃの一部のみを描いている。続いて、撮像部１１からの出力に基づいて、対象点群８ｃの最も外側に位置する点を直線にて結んで形成される凸包８２ｃの暫定幅方向の一方側の部分である部分凸包８２１ａ、および、他方側の部分であるもう１つの部分凸包（図示省略）が凸包生成部１２１（図４参照）により生成される。
【００４０】
そして、配列方向取得部１２２（図４参照）により、２つの部分凸包にそれぞれ含まれる複数の線分８２５のうち最長の線分が、方向指示線分８２５ａおよびもう１つの方向指示線分（図示省略）として特定され、方向指示線分８２５ａの方向ともう１つの方向指示線分の方向とを用いて最終的な配列方向が取得される。この場合も、上記と同様に、点群８に含まれる点列８１における複数の点８１１の配列方向を容易かつ高精度に検出することができる。
【００４１】
次に、本発明の第２の実施の形態に係る配列方向検出装置について説明する。第２の実施の形態に係る配列方向検出装置は、図１に示す配列方向検出装置１と同様の構成を備えており、以下の説明では、第２の実施の形態に係る配列方向検出装置の各構成に、図１、図３および図４に示す配列方向検出装置１の対応する構成と同符号を付す。第２の実施の形態に係る配列方向検出装置では、演算部１２の固定ディスク１０４に、図３に示す配列方向検出プログラム１０４１とは異なる配列方向検出プログラムが記憶されるが、以下の説明では、第１の実施の形態と同様に、符号１０４１を付す。
【００４２】
図１０は、第２の実施の形態に係る配列方向検出装置による配列方向検出の流れを示す図である。配列方向検出装置では、上述のステップＳ１１（図５参照）と同様に、撮像部１１（図１参照）により対象物９が撮像されて、図２に示す画像８０が演算部１２へと送られる（ステップＳ２１）。対象物９は、撮像部１１による撮像よりも前に予め粗い姿勢調整（いわゆる、プリアライメント）が行われており、点８１１の配列方向であるｙ方向は暫定配列方向であるＹ方向におよそ平行となっている。
【００４３】
続いて、演算部１２が配列方向検出プログラム１０４１（図３参照）に従って演算処理を実行することにより、凸包生成部１２１（図４参照）により、対象点群である点群８から図６に示す凸包８２が生成され、配列方向取得部１２２（図４参照）により、凸包８２の（−Ｘ）側の部分である部分凸包８２１ａが抽出される（ステップＳ２２，Ｓ２３）。
【００４４】
本実施の形態では、上述のように、対象物９に対するプリアライメントが行われているため、一の点列８１上の複数の点８１１を結ぶ直線の方向は、一の点列８１上の点８１１と他の点列８１上の点８１１とを結ぶ直線の方向よりもＹ方向に近くなる。そこで、配列方向取得部１２２により、部分凸包８２１ａに含まれる複数の線分８２５のうち暫定配列方向（すなわち、図６中のＹ方向）と為す角度が最も小さい線分が方向指示線分８２５ａとして特定され、暫定配列方向であるＹ方向を基準とする方向指示線分８２５ａの方向（例えば、Ｙ方向と方向指示線分８２５ａとの為す角度）が、各点列８１における複数の点８１１の仮配列方向として取得される（ステップＳ２４）。
【００４５】
また、凸包８２の（＋Ｘ）側の部分である部分凸包８２１ｂが抽出され（ステップＳ２５）、部分凸包８２１ｂに含まれる複数の線分８２５のうち暫定配列方向と為す角度が最も小さい線分が方向指示線分８２５ｂとして特定され、暫定配列方向を基準とする方向指示線分８２５ｂの方向が、各点列８１における複数の点８１１のもう１つの仮配列方向として取得される（ステップＳ２６）。その後、第１の実施の形態と同様に、方向指示線分８２５ａから取得された仮配列方向と方向指示線分８２５ｂから取得された仮配列方向とを用いて、最終的な配列方向が取得される（ステップＳ２７）。
【００４６】
第２の実施の形態に係る配列方向検出装置では、第１の実施の形態と同様に、点群８に含まれる点列８１における複数の点８１１の配列方向を容易かつ高精度に検出することができる。配列方向検出装置では、点群８の少なくとも一部が撮像部１１に撮像される対象点群とされていればよく、また、部分凸包８２１ａ，８２１ｂのうちの一方のみが生成され、当該部分凸包にて特定された方向指示線分の方向が最終的な配列方向として取得されてもよい。さらに、第１の実施の形態と同様に、図９に示すように、ｘ方向およびｙ方向に等ピッチにて配列された複数の点８１１を有する点群８の配列方向の検出に利用されてもよい。
【００４７】
また、第１の実施の形態に係る配列方向検出プログラム、および、第２の実施の形態に係る配列方向検出プログラムが一の配列方向検出装置の演算部１２の固定ディスク１０４に記憶され、両配列方向検出プログラムのうちの一方が選択的に用いられて配列方向の検出が行われてもよい。
【００４８】
以上、本発明の実施の形態について説明してきたが、本発明は上記実施の形態に限定されるものではなく、様々な変更が可能である。
【００４９】
配列方向検出装置では、撮像部１１により点群８のうちの対象点群の画像（点群８全体の画像であってもよい。）が取得されるのであれば、必ずしも対象物９の全体の画像が取得される必要はない。また、撮像部１１では、ラインセンサ１１１に代えて、例えば、２次元ＣＣＤカメラが設けられてもよい。
【００５０】
また、配列方向検出装置では、配列方向の検出精度を向上するために、一の対象物に対して上述の配列方向の検出が繰り返し行われてもよい。配列方向検出装置は、上述のような暗号情報を示す点群やシリコン基板上の複数のチップの重心に対応する点群の配列方向を検出する以外にも、様々な点群の配列方向を求める際に利用されてよい。
【符号の説明】
【００５１】
１ 配列方向検出装置
８ 点群
８ａ〜８ｃ 対象点群
１１ 撮像部
８１ 点列
８２，８２ａ〜８２ｃ 凸包
１２１ 凸包生成部
１２２ 配列方向取得部
８０１，８０１ａ 領域
８１１ 点
８２１ａ，８２１ｂ 部分凸包
８２５ 線分
８２５ａ，８２５ｂ 方向指示線分
１０４１ 配列方向検出プログラム
Ｓ１１〜Ｓ１７，Ｓ２１〜Ｓ２７ ステップ
【技術分野】
【０００１】
本発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、配列方向に垂直な方向において互いに重なる複数の点列からなる点群から配列方向を検出する技術に関する。
【背景技術】
【０００２】
従来より、対象物の画像の傾きを求める方法の１つとして、対象物上に目印（いわゆる、アライメントマーク）を設けておき、画像中のアライメントマークの配列の傾きから画像の傾きを求める方法が知られている。
【０００３】
また、特許文献１では、走査方向に垂直な方向における位置を変更しつつ画像を走査方向に沿って複数回走査し、各走査において最初に出現する画素の集合である印刷開始点列（例えば、矩形の印刷領域の上辺の画素）を求め、印刷開始点列の傾きから画像の傾きを求める方法が開示されている。
【０００４】
特許文献２では、画像上においてセルである単位要素が縦方向および横方向に配列されており、各単位要素の重心位置をパターンマッチング処理により求め、縦方向の位置が近い重心を有する単位要素の集合（すなわち、横方向に並ぶ単位要素の集合であり、以下、「単位要素列」という。）を抽出し、当該単位要素列に含まれる複数の単位要素の重心を通る直線の傾きから画像の傾きを求める方法が開示されている。なお、上記重心を点と捉えた場合、多数の点から一の直線上に配列される複数の点を抽出する方法の１つであるハフ（Ｈｏｕｇｈ）変換を用いて単位要素列の複数の重心を通る直線を求めることが考えられるが、ハフ変換ではあらゆる方向を向く直線に対して投票処理を行って適切な直線を求めることになるため、処理時間が多大なものとなってしまう。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平７−８９０６３号公報
【特許文献２】特開２００５−３１３２１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、対象物にアライメントマークを設けて画像の傾きを求める方法では、対象物に対するアライメントマークの付加が必要となる上、画像中からアライメントマークを抽出する必要もあり、傾き検出に要する演算量が増大してしまう。
【０００７】
特許文献１の方法では、上述のように、矩形の印刷領域が設定されている画像の傾きを求めることは可能であるが、印刷領域の輪郭が矩形でない場合（例えば、曲線を含んだり凹凸がある場合）には、画像の傾きを精度良く求めることは困難である。
【０００８】
特許文献２の方法では、画像の傾きが少し大きくなると、一の単位要素列に含まれる複数の単位要素の重心位置と、当該単位要素列に隣接する他の単位要素列に含まれる複数の単位要素の重心位置とが縦方向において近接してしまい、隣接する２つの単位要素列を区別することが困難になって画像の傾きを精度良く求めることができなくなってしまう。また、隣接する単位要素列の間の距離が小さい場合にも同様に、隣接する２つの単位要素列に含まれる単位要素が一緒に抽出されてしまい、画像の傾きを精度良く求めることができなくなってしまう。
【０００９】
本発明は、上記課題に鑑みなされたものであり、点群に含まれる点列における複数の点の配列方向を容易かつ高精度に検出することを目的としている。
【課題を解決するための手段】
【００１０】
請求項１に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出装置であって、前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する撮像部と、前記撮像部からの出力に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する凸包生成部と、前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する配列方向取得部とを備える。
【００１１】
請求項２に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出装置であって、前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する撮像部と、前記撮像部からの出力に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する凸包生成部と、前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する配列方向取得部とを備える。
【００１２】
請求項３に記載の発明は、請求項１または２に記載の配列方向検出装置であって、前記方向指示線分から取得された前記配列方向が仮に決定された配列方向であり、前記撮像部、前記凸包生成部および前記配列方向取得部により、前記点群の前記暫定幅方向の他方側においても前記方向指示線分と同様にもう１つの方向指示線分が特定され、前記配列方向取得部が、前記方向指示線分の方向と前記もう１つの方向指示線分の方向とを用いて最終的な前記配列方向を取得する。
【００１３】
請求項４に記載の発明は、請求項１ないし３のいずれかに記載の配列方向検出装置であって、前記点群において、各点と少なくとも１つの他の点とが前記配列方向に垂直な幅方向に並ぶ。
【００１４】
請求項５に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出方法であって、ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する工程と、ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、ｃ）前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程とを備える。
【００１５】
請求項６に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出方法であって、ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する工程と、ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、ｃ）前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程とを備える。
【００１６】
請求項７に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出プログラムであって、前記配列方向検出プログラムのコンピュータによる実行は、前記コンピュータに、ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する工程と、ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、ｃ）前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程とを実行させる。
【００１７】
請求項８に記載の発明は、平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出プログラムであって、前記配列方向検出プログラムのコンピュータによる実行は、前記コンピュータに、ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する工程と、ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、ｃ）前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程とを実行させる。
【発明の効果】
【００１８】
本発明では、点群に含まれる点列における複数の点の配列方向を容易かつ高精度に検出することができる。
【図面の簡単な説明】
【００１９】
【図１】第１の実施の形態に係る配列方向検出装置を示す図である。
【図２】点群の画像を示す図である。
【図３】演算部の構成を示す図である。
【図４】演算部の機能を示すブロック図である。
【図５】配列方向の検出の流れを示す図である。
【図６】点群の画像を示す図である。
【図７】点群の画像を示す図である。
【図８】点群の画像を示す図である。
【図９】シリコン基板上の複数のチップの画像を示す図である。
【図１０】第２の実施の形態に係る配列方向検出装置による配列方向の検出の流れを示す図である。
【発明を実施するための形態】
【００２０】
図１は、本発明の第１の実施の形態に係る配列方向検出装置１の構成を示す図である。配列方向検出装置１は、図２にその一部を示す対象物９の画像８０中の複数の点列８１からなる点群８から、点列８１における複数の点８１１の配列方向を検出する装置である。図２では、図の理解を容易にするために、各点列８１を二点鎖線にて囲む。点群８では、複数の点列８１のそれぞれは、図２中のｘｙ平面上において所定の配列方向（図２中におけるｙ方向であり、ｘ方向およびｙ方向は点群８に対して固定された座標軸である。）に複数の点８１１が直線状に配列された点列であり、複数の点列８１は、当該配列方向に垂直な幅方向（すなわち、ｘ方向）において互いに重なっている。換言すれば、点群８では、図２中のｙ方向に平行に伸びる互いに平行な複数の点列８１がｘ方向に配列されている。
【００２１】
図１に示す配列方向検出装置１は、対象物９をガラス面上に保持する保持部１３、対象物９を撮像する撮像部１１、および、撮像部１１により取得された画像を受け付けて所定の演算を行う演算部１２を備える。撮像部１１は、印刷された面を下側（（−Ｚ）側）に向けて保持部１３に保持された対象物９の下方に配置され、対象物９の印刷された面の画像を取得する。
【００２２】
撮像部１１は、対象物９上において図１中のＸ方向に伸びる線状領域を撮像するラインセンサ１１１、対象物９上におけるラインセンサ１１１の撮像領域に光を照射する光照射部１１２、並びに、ラインセンサ１１１および光照射部１１２をＸ方向に垂直なＹ方向に移動するセンサ移動機構１１３を備える。本実施の形態では、ラインセンサ１１１は、線状に配列された複数のＣＣＤ（Charge Coupled Device）素子を備え、ラインセンサ１１１の線状の撮像領域は対象物９のＸ方向の全幅に亘る。
【００２３】
ここで、図１中のＸ方向およびＹ方向は、配列方向検出装置１に対して固定された既知の座標軸であり、ＸＹ平面と図２中のｘｙ平面とは平行である。図２中のｘ方向およびｙ方向はそれぞれ、Ｘ方向およびＹ方向におよそ平行であることは判明しているものの未知の座標軸であり、配列方向検出装置１では、既知のＹ方向に対するｙ方向の傾きが求められることにより、点列８１における複数の点８１１の配列方向が検出される。以下の説明では、複数の点８１１の配列方向であるｙ方向（すなわち、配列方向検出装置１の検出対象）におよそ平行なＹ方向を「暫定配列方向」といい、Ｙ方向に垂直なＸ方向を「暫定幅方向」という。
【００２４】
図３は、演算部１２の構成を示す図である。演算部１２は、通常のコンピュータと同様に、ＣＰＵ１０１、ＲＡＭ１０２、ＲＯＭ１０３、固定ディスク１０４、ディスプレイ１０５、および、入力部１０６等を接続した構成となっており、固定ディスク１０４内には、演算部１２により実行される配列方向検出プログラム１０４１が記憶される。図４は、演算部１２のＣＰＵ１０１等が配列方向検出プログラム１０４１に従って演算処理を実行することにより実現される機能を示すブロック図であり、図４中の凸包生成部１２１および配列方向取得部１２２が、ＣＰＵ１０１等により実現される機能に相当する。これらの機能は複数台のコンピュータにより実現されてもよい。
【００２５】
図５は、配列方向検出装置１による複数の点８１１の配列方向検出の流れを示す図である。図１に示す配列方向検出装置１では、まず、撮像部１１のラインセンサ１１１および光照射部１１２がＹ方向に走査されることにより、対象物９が撮像されて画像８０（図２参照）が演算部１２へと送られる（ステップＳ１１）。
【００２６】
本実施の形態では、図２に示す画像８０中の点群８の全体が、配列方向の検出に利用される対象点群となっている。点群８の複数の点列８１のそれぞれでは複数の点８１１が不等ピッチにて配列されており、複数の点列８１において配列方向であるｙ方向に隣接する２つの点８１１の間の距離の最大値（以下、「点間最大距離」という。）は既知とされる。対象点群である点群８は、暫定配列方向であるＹ方向に長い矩形状の領域８０１（図２において二点鎖線にて示す。）内に存在する。領域８０１のＹ方向の長さは、点間最大距離の３倍以上となっている。なお、図２では、図示の都合上、複数の点列８１のｘ方向におけるピッチを実際よりも大きく描いているが、実際には、隣接する点列８１の間の距離は点間最大距離よりもかなり小さい。
【００２７】
続いて、演算部１２の凸包生成部１２１（図４参照）により、撮像部１１（図１参照）からの出力である画像８０に基づいて、点群８の最も外側に位置する複数の点８１１を、図６に示すように直線にて結んで形成される凸包８２が生成される（ステップＳ１２）。具体的には、画像８０が二値化されて複数の点８１１が抽出され（すなわち、各点８１１を周囲の部位から孤立させて切り出し）、各点８１１の重心の位置が求められ、さらに、複数の点８１１のそれぞれの重心からグラハム（Ｇｒａｈａｍ）の方法等の既知の手法により凸包８２が求められる。なお、画像８０からの複数の点８１１の抽出はパターンマッチング等により行われてもよい。
【００２８】
次に、配列方向取得部１２２（図４参照）により、凸包８２の暫定幅方向の一方側（すなわち、（−Ｘ）側）の部分である部分凸包８２１ａが凸包８２から抽出される（ステップＳ１３）。図６では、図の理解を容易にするために、部分凸包８２１ａを二点鎖線にて囲む。そして、部分凸包８２１ａに含まれる複数の線分８２５のうち最長の線分が方向指示線分８２５ａとして特定され、暫定配列方向であるＹ方向を基準とする方向指示線分８２５ａの方向（例えば、Ｙ方向と方向指示線分８２５ａとの為す角度）が、各点列８１における複数の点８１１の仮に決定された配列方向（以下、「仮配列方向」という。）として取得される（ステップＳ１４）。
【００２９】
また、配列方向取得部１２２により、凸包８２の暫定幅方向の他方側（すなわち、（＋Ｘ）側）の部分であるもう１つの部分凸包８２１ｂが凸包８２から抽出され（ステップＳ１５）、上述の方向指示線分８２５ａと同様に、部分凸包８２１ｂに含まれる複数の線分８２５のうち最長の線分が方向指示線分８２５ｂとして特定される。そして、Ｙ方向を基準とする方向指示線分８２５ｂの方向（例えば、Ｙ方向と方向指示線分８２５ｂとの為す角度）が、各点列８１における複数の点８１１のもう１つの仮配列方向として取得される（ステップＳ１６）。
【００３０】
その後、方向指示線分８２５ａから取得された仮配列方向と方向指示線分８２５ｂから取得された仮配列方向との平均値が、最終的な配列方向として取得される（ステップＳ１７）。これにより、画像８０からの点群８の読み取り時に生じる可能性がある読取誤差等による影響を抑制して配列方向を精度良く取得することができる。
【００３１】
配列方向取得部１２２では、必ずしも上記平均値が最終的な配列方向とされる必要はなく、方向指示線分８２５ａの方向および方向指示線分８２５ｂの方向である２つの仮配列方向が用いられるのであれば、他の様々な方法により最終的な配列方向が取得されてよい。例えば、凸包８２の生成時に対象物９上の汚れ等を誤って点８１１として認識することにより、一方の方向指示線分の方向と暫定配列方向（Ｙ方向）との為す角度が、他方の方向指示線分の方向と暫定配列方向との為す角度に比べて明らかに大きくなってしまっている場合、Ｙ方向と為す角度が小さい方の方向指示線分の方向が最終的な配列方向として取得されてよい。
【００３２】
配列方向検出装置１は、例えば、印刷媒体である対象物９に印刷された暗号情報を示す点群８から暗号情報を読み取る際に利用される。図２に示す点群８では、各点列８１が「０」または「１」を示し、８つの点列８１により８桁のビット列からなる暗号情報が示される。点群８は、対象物９上の余白領域（すなわち、通常の画像が印刷される領域の周囲の領域）等に印刷される。点群８では、一の点列８１が示す値が「０」である場合には、当該点列８１における配列方向であるｙ方向の単位距離中に含まれる点８１１の個数（以下、「単位ドット数」という。）が所定の個数（以下、「ドット閾値」という。）以下とされ、当該点列８１が示す値が「１」である場合には、単位ドット数がドット閾値よりも大きくされる。
【００３３】
対象物９から暗号情報が読み取られる際には、既述のように、配列方向検出装置１により、対象物９の画像８０の取得、対象点群である点群８の凸包８２の生成、凸包８２からの部分凸包８２１ａの抽出（すなわち、部分凸包８２１ａの生成）、部分凸包８２１ａに基づく仮配列方向の取得、凸包８２からの部分凸包８２１ｂの抽出（すなわち、部分凸包８２１ｂの生成）、部分凸包８２１ｂに基づく仮配列方向の取得、および、２つの仮配列方向に基づく最終的な配列方向の取得（ステップＳ１１〜Ｓ１７）が行われる。
【００３４】
続いて、点群８における配列方向であるｙ方向が、暫定配列方向であるＹ方向に一致するように、ｙ方向とＹ方向との為す角度だけ点群８が回転される（具体的には、点群８の各点８１１のＸＹ座標系における座標が変換される）。そして、複数の点列８１のそれぞれの単位ドット数がＹ方向に沿って計数され、単位ドット数がドット閾値と比較されて各点列８１が示す値（「０」または「１」）が取得されることにより、対象物９から暗号情報が読み取られる。上記点群８の回転、各点列８１の単位ドット数の計数、および、各点列８１が示す値の取得は、配列方向検出装置１により行われてもよく、他の装置により行われてもよい。また、点群８の回転が行われることなく、基準となるＹ方向（暫定配列方向）と為す角度が既知となった配列方向に沿って各点列８１の単位ドット数の計数が行われてもよい。
【００３５】
以上に説明したように、配列方向検出装置１では、図２に示す領域８０１のように、暫定配列方向に長く、かつ、その長さが点間最大距離の３倍以上である略矩形状の領域内に存在する対象点群である点群８が撮像され、点群８の画像から凸包８２が生成される。このように、点群８の輪郭が上記の領域８０１の輪郭におよそ沿ったものとされることにより、点群８の凸包８２に含まれる複数の線分８２５のうち、一の点列８１に含まれる点８１１と他の点列８１に含まれる点８１１とを結ぶ線分よりも、一の点列８１に含まれる複数の点８１１を通る線分（すなわち、配列方向を向く線分）の方が確実に長くなる。このため、凸包８２の（−Ｘ）側の部分凸包８２１ａおよび（＋Ｘ）側の部分凸包８２１ｂにそれぞれ含まれる複数の線分のうち最長の線分を方向指示線分８２５ａ，８２５ｂとして特定し、方向指示線分８２５ａ，８２５ｂのそれぞれの方向を用いて最終的な配列方向を取得することにより、点群８に含まれる点列８１における複数の点８１１の配列方向を高精度に検出することができる。また、点群８を囲む凸包８２を利用することにより、ハフ変換のように非常に多数の方向について検討することなく、配列方向を容易に検出することができる。
【００３６】
配列方向検出装置１では、必ずしも点群８全体が凸包８２の形成に利用される対象点群とされる必要はなく、点群８の一部が対象点群とされてもよい。換言すれば、対象点群は、点群８の少なくとも一部であればよい。点群８の一部が対象点群とされる場合、点群８のうち、図７に示すように、暫定配列方向に長く、かつ、その長さが点間最大距離の３倍以上である略矩形状の領域８０１ａ内に存在する対象点群８ａが撮像部１１（図１参照）により撮像される。このように、対象点群８ａの輪郭が上記領域の輪郭におよそ沿ったものとされた状態で、対象点群８ａの凸包８２ａ（すなわち、対象点群８ａの最も外側に位置する点を直線にて結んで形成される凸包）の部分凸包８２１ａ，８２１ｂにて特定された方向指示線分８２５ａ，８２５ｂのそれぞれの方向を用いて配列方向を取得することにより、上記と同様に、点群８に含まれる点列８１（図２参照）における複数の点８１１の配列方向を容易かつ高精度に検出することができる。
【００３７】
配列方向検出装置１では、また、必ずしも部分凸包８２１ａ，８２１ｂにて特定された方向指示線分８２５ａ，８２５ｂの双方の方向を用いて配列方向が取得される必要はなく、例えば、方向指示線分８２５ｂを特定することなく、方向指示線分８２５ａの方向が最終的な配列方向として取得されてもよい。換言すれば、図５中のステップＳ１５〜Ｓ１７が省略され、ステップＳ１４にて求められた仮配列方向が最終的な配列方向とされる。この場合、撮像部１１（図１参照）では、図８に示すように、点群８の一部であって暫定幅方向の一方側である（−Ｘ）側の部位を含む対象点群８ｂが撮像される。そして、対象点群８ｂの凸包８２ｂの（−Ｘ）側の部分である部分凸包８２１ａが生成され、部分凸包８２１ａにて特定された方向指示線分８２５ａの方向が最終的な配列方向として取得される。これにより、点群８に含まれる点列８１（図２参照）における複数の点８１１の配列方向を容易かつ高精度に検出することができる。なお、配列方向検出装置１は、図２中のｘ方向に配列された点列の配列方向の検出に用いられてもよい。
【００３８】
配列方向検出装置１は、また、図９に示すシリコン基板である対象物９ａ上の複数のチップ９１の画像８０ａにおけるチップ９１の配列方向の検出にも利用されてよい。対象物９ａ上では、複数のチップ９１が対象物９ａに固定されたｘｙ座標系のｘ方向およびｙ方向に等ピッチにて配列されており、以下では、各チップ９１の重心を点８１１、配列方向であるｙ方向に配列された複数の点８１１を点列８１、配列方向に垂直な幅方向であるｘ方向に配列された複数の点列８１を点群８と捉えて説明する。点群８では、各点８１１と少なくとも他の点８１１とが幅方向に並んでいる。また、画像８０ａに固定されたＸＹ座標系のＹ方向を既知の暫定配列方向と呼び、Ｙ方向に垂直なＸ方向を暫定幅方向と呼ぶ。
【００３９】
配列方向検出装置１では、まず、上記と同様に、点群８の（少なくとも）一部であって暫定幅方向の一方側および他方側（（−Ｘ）側および（＋Ｘ）側）の部位を含み、かつ、暫定配列方向に長く、その長さが点間最大距離（この場合、ｙ方向における点８１１のピッチに等しい。）の３倍以上である領域内に存在する対象点群８ｃが撮像部１１（図１参照）により撮像される。図９では、図示の都合上、対象点群８ｃの一部のみを描いている。続いて、撮像部１１からの出力に基づいて、対象点群８ｃの最も外側に位置する点を直線にて結んで形成される凸包８２ｃの暫定幅方向の一方側の部分である部分凸包８２１ａ、および、他方側の部分であるもう１つの部分凸包（図示省略）が凸包生成部１２１（図４参照）により生成される。
【００４０】
そして、配列方向取得部１２２（図４参照）により、２つの部分凸包にそれぞれ含まれる複数の線分８２５のうち最長の線分が、方向指示線分８２５ａおよびもう１つの方向指示線分（図示省略）として特定され、方向指示線分８２５ａの方向ともう１つの方向指示線分の方向とを用いて最終的な配列方向が取得される。この場合も、上記と同様に、点群８に含まれる点列８１における複数の点８１１の配列方向を容易かつ高精度に検出することができる。
【００４１】
次に、本発明の第２の実施の形態に係る配列方向検出装置について説明する。第２の実施の形態に係る配列方向検出装置は、図１に示す配列方向検出装置１と同様の構成を備えており、以下の説明では、第２の実施の形態に係る配列方向検出装置の各構成に、図１、図３および図４に示す配列方向検出装置１の対応する構成と同符号を付す。第２の実施の形態に係る配列方向検出装置では、演算部１２の固定ディスク１０４に、図３に示す配列方向検出プログラム１０４１とは異なる配列方向検出プログラムが記憶されるが、以下の説明では、第１の実施の形態と同様に、符号１０４１を付す。
【００４２】
図１０は、第２の実施の形態に係る配列方向検出装置による配列方向検出の流れを示す図である。配列方向検出装置では、上述のステップＳ１１（図５参照）と同様に、撮像部１１（図１参照）により対象物９が撮像されて、図２に示す画像８０が演算部１２へと送られる（ステップＳ２１）。対象物９は、撮像部１１による撮像よりも前に予め粗い姿勢調整（いわゆる、プリアライメント）が行われており、点８１１の配列方向であるｙ方向は暫定配列方向であるＹ方向におよそ平行となっている。
【００４３】
続いて、演算部１２が配列方向検出プログラム１０４１（図３参照）に従って演算処理を実行することにより、凸包生成部１２１（図４参照）により、対象点群である点群８から図６に示す凸包８２が生成され、配列方向取得部１２２（図４参照）により、凸包８２の（−Ｘ）側の部分である部分凸包８２１ａが抽出される（ステップＳ２２，Ｓ２３）。
【００４４】
本実施の形態では、上述のように、対象物９に対するプリアライメントが行われているため、一の点列８１上の複数の点８１１を結ぶ直線の方向は、一の点列８１上の点８１１と他の点列８１上の点８１１とを結ぶ直線の方向よりもＹ方向に近くなる。そこで、配列方向取得部１２２により、部分凸包８２１ａに含まれる複数の線分８２５のうち暫定配列方向（すなわち、図６中のＹ方向）と為す角度が最も小さい線分が方向指示線分８２５ａとして特定され、暫定配列方向であるＹ方向を基準とする方向指示線分８２５ａの方向（例えば、Ｙ方向と方向指示線分８２５ａとの為す角度）が、各点列８１における複数の点８１１の仮配列方向として取得される（ステップＳ２４）。
【００４５】
また、凸包８２の（＋Ｘ）側の部分である部分凸包８２１ｂが抽出され（ステップＳ２５）、部分凸包８２１ｂに含まれる複数の線分８２５のうち暫定配列方向と為す角度が最も小さい線分が方向指示線分８２５ｂとして特定され、暫定配列方向を基準とする方向指示線分８２５ｂの方向が、各点列８１における複数の点８１１のもう１つの仮配列方向として取得される（ステップＳ２６）。その後、第１の実施の形態と同様に、方向指示線分８２５ａから取得された仮配列方向と方向指示線分８２５ｂから取得された仮配列方向とを用いて、最終的な配列方向が取得される（ステップＳ２７）。
【００４６】
第２の実施の形態に係る配列方向検出装置では、第１の実施の形態と同様に、点群８に含まれる点列８１における複数の点８１１の配列方向を容易かつ高精度に検出することができる。配列方向検出装置では、点群８の少なくとも一部が撮像部１１に撮像される対象点群とされていればよく、また、部分凸包８２１ａ，８２１ｂのうちの一方のみが生成され、当該部分凸包にて特定された方向指示線分の方向が最終的な配列方向として取得されてもよい。さらに、第１の実施の形態と同様に、図９に示すように、ｘ方向およびｙ方向に等ピッチにて配列された複数の点８１１を有する点群８の配列方向の検出に利用されてもよい。
【００４７】
また、第１の実施の形態に係る配列方向検出プログラム、および、第２の実施の形態に係る配列方向検出プログラムが一の配列方向検出装置の演算部１２の固定ディスク１０４に記憶され、両配列方向検出プログラムのうちの一方が選択的に用いられて配列方向の検出が行われてもよい。
【００４８】
以上、本発明の実施の形態について説明してきたが、本発明は上記実施の形態に限定されるものではなく、様々な変更が可能である。
【００４９】
配列方向検出装置では、撮像部１１により点群８のうちの対象点群の画像（点群８全体の画像であってもよい。）が取得されるのであれば、必ずしも対象物９の全体の画像が取得される必要はない。また、撮像部１１では、ラインセンサ１１１に代えて、例えば、２次元ＣＣＤカメラが設けられてもよい。
【００５０】
また、配列方向検出装置では、配列方向の検出精度を向上するために、一の対象物に対して上述の配列方向の検出が繰り返し行われてもよい。配列方向検出装置は、上述のような暗号情報を示す点群やシリコン基板上の複数のチップの重心に対応する点群の配列方向を検出する以外にも、様々な点群の配列方向を求める際に利用されてよい。
【符号の説明】
【００５１】
１ 配列方向検出装置
８ 点群
８ａ〜８ｃ 対象点群
１１ 撮像部
８１ 点列
８２，８２ａ〜８２ｃ 凸包
１２１ 凸包生成部
１２２ 配列方向取得部
８０１，８０１ａ 領域
８１１ 点
８２１ａ，８２１ｂ 部分凸包
８２５ 線分
８２５ａ，８２５ｂ 方向指示線分
１０４１ 配列方向検出プログラム
Ｓ１１〜Ｓ１７，Ｓ２１〜Ｓ２７ ステップ
【特許請求の範囲】
【請求項１】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出装置であって、
前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する撮像部と、
前記撮像部からの出力に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する凸包生成部と、
前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する配列方向取得部と、
を備えることを特徴とする配列方向検出装置。
【請求項２】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出装置であって、
前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する撮像部と、
前記撮像部からの出力に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する凸包生成部と、
前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する配列方向取得部と、
を備えることを特徴とする配列方向検出装置。
【請求項３】
請求項１または２に記載の配列方向検出装置であって、
前記方向指示線分から取得された前記配列方向が仮に決定された配列方向であり、
前記撮像部、前記凸包生成部および前記配列方向取得部により、前記点群の前記暫定幅方向の他方側においても前記方向指示線分と同様にもう１つの方向指示線分が特定され、
前記配列方向取得部が、前記方向指示線分の方向と前記もう１つの方向指示線分の方向とを用いて最終的な前記配列方向を取得することを特徴とする配列方向検出装置。
【請求項４】
請求項１ないし３のいずれかに記載の配列方向検出装置であって、
前記点群において、各点と少なくとも１つの他の点とが前記配列方向に垂直な幅方向に並ぶことを特徴とする配列方向検出装置。
【請求項５】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出方法であって、
ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する工程と、
ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、
ｃ）前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程と、
を備えることを特徴とする配列方向検出方法。
【請求項６】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出方法であって、
ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する工程と、
ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、
ｃ）前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程と、
を備えることを特徴とする配列方向検出方法。
【請求項７】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出プログラムであって、前記配列方向検出プログラムのコンピュータによる実行は、前記コンピュータに、
ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する工程と、
ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、
ｃ）前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程と、
を実行させることを特徴とする配列方向検出プログラム。
【請求項８】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出プログラムであって、前記配列方向検出プログラムのコンピュータによる実行は、前記コンピュータに、
ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する工程と、
ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、
ｃ）前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程と、
を実行させることを特徴とする配列方向検出プログラム。
【請求項１】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出装置であって、
前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する撮像部と、
前記撮像部からの出力に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する凸包生成部と、
前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する配列方向取得部と、
を備えることを特徴とする配列方向検出装置。
【請求項２】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出装置であって、
前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する撮像部と、
前記撮像部からの出力に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する凸包生成部と、
前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する配列方向取得部と、
を備えることを特徴とする配列方向検出装置。
【請求項３】
請求項１または２に記載の配列方向検出装置であって、
前記方向指示線分から取得された前記配列方向が仮に決定された配列方向であり、
前記撮像部、前記凸包生成部および前記配列方向取得部により、前記点群の前記暫定幅方向の他方側においても前記方向指示線分と同様にもう１つの方向指示線分が特定され、
前記配列方向取得部が、前記方向指示線分の方向と前記もう１つの方向指示線分の方向とを用いて最終的な前記配列方向を取得することを特徴とする配列方向検出装置。
【請求項４】
請求項１ないし３のいずれかに記載の配列方向検出装置であって、
前記点群において、各点と少なくとも１つの他の点とが前記配列方向に垂直な幅方向に並ぶことを特徴とする配列方向検出装置。
【請求項５】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出方法であって、
ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する工程と、
ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、
ｃ）前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程と、
を備えることを特徴とする配列方向検出方法。
【請求項６】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出方法であって、
ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する工程と、
ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、
ｃ）前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程と、
を備えることを特徴とする配列方向検出方法。
【請求項７】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出プログラムであって、前記配列方向検出プログラムのコンピュータによる実行は、前記コンピュータに、
ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含み、かつ、前記暫定配列方向に長く、その長さが前記複数の点列において前記配列方向に隣接する２つの点の間の距離の既知の最大値の３倍以上である領域内に存在する対象点群を撮像する工程と、
ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、
ｃ）前記部分凸包に含まれる複数の線分のうち最長の線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程と、
を実行させることを特徴とする配列方向検出プログラム。
【請求項８】
平面上において、それぞれが所定の配列方向に点が配列された点列であり、かつ、前記配列方向に垂直な方向において互いに重なる複数の点列からなる点群から前記配列方向を検出する配列方向検出プログラムであって、前記配列方向検出プログラムのコンピュータによる実行は、前記コンピュータに、
ａ）前記点群の少なくとも一部であって前記配列方向におよそ平行であることが判明している暫定配列方向に垂直な暫定幅方向の一方側の部位を含む対象点群を撮像する工程と、
ｂ）前記ａ）工程における撮像結果に基づいて前記対象点群の最も外側に位置する点を直線にて結んで形成される凸包の前記暫定幅方向の前記一方側の部分である部分凸包を生成する工程と、
ｃ）前記部分凸包に含まれる複数の線分のうち前記暫定配列方向と為す角度が最も小さい線分を方向指示線分として特定し、前記方向指示線分の方向を前記配列方向として取得する工程と、
を実行させることを特徴とする配列方向検出プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−１８６４０７（Ｐ２０１０−１８６４０７Ａ）
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願番号】特願２００９−３１３９５（Ｐ２００９−３１３９５）
【出願日】平成２１年２月１３日（２００９．２．１３）
【出願人】（０００２０７５５１）大日本スクリーン製造株式会社 (2,640)
【Ｆターム（参考）】
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願日】平成２１年２月１３日（２００９．２．１３）
【出願人】（０００２０７５５１）大日本スクリーン製造株式会社 (2,640)
【Ｆターム（参考）】
[ Back to top ]