(57)【要約】  本発明は、屋外環境でのマーカーの光学的認識のための頑健な方法に関する。これに関連して、本発明は、画像を取得する工程と、画像の中の隣接する色の領域をフラッドフィルによって識別する工程と、隣接する領域のデータ及びパラメータを抽出する工程と、隣接する領域から抽出されたデータ及びパラメータに基づいて、凸包を求めるアルゴリズム及び正方形の位置の予測により光学マーカーを検出する工程と、を備える、光学マーカーの光学的認識のための方法を提供する。従って、本発明の方法により、部分的遮蔽及び照明の変動に関して、明確にかつ十分な頑健性を備えて、チェッカーボード及びターゲット等のマーカーの識別が可能になる。
2021516388.tif 000002
【特許請求の範囲】
【請求項１】
光学マーカーの光学的認識のための方法であって、
画像を取得する工程と、
前記画像の中の隣接する色の領域をフラッドフィルによって識別する工程と、
前記隣接する領域のデータ及びパラメータを抽出する工程と、
前記隣接する領域から抽出された前記データ及びパラメータに基づいて、凸包を求めるアルゴリズム及び正方形の位置の予測により光学マーカーを検出する工程と、
を備える、方法。
【請求項２】
請求項１に記載の方法であって、前記光学マーカーはチェッカーボードである、方法。
【請求項３】
請求項１又は２に記載の方法であって、
前記画像中の隣接する色の領域を識別する工程は、以下のサブ工程、すなわち、
前記画像に少なくとも１つのフィルタをかける工程と、
前記隣接する色の異なる領域を分離するために前記画像のエッジを検出する工程と、
フラッドフィルを用いて前記分離された領域の塗りつぶしを実行する工程と、
前記隣接する色の異なる領域のそれぞれを、それらの特性によって識別する工程と、
を備える、方法。
【請求項４】
請求項３に記載の方法であって、
前記分離された領域の塗りつぶしを実行する前記サブ工程は、以下のサブ工程、すなわち、
エッジマップを受け取る工程と、
色領域のマップを作成する工程と、
色を表す番号であるインデックスを各ピクセルに割り当てることによって、前記色領域のマップを初期化する工程と、
前記色領域のマップが変更されなくなるまで、以下の工程、すなわち、
（ｉ）前記色領域のマップを、左から右、右から左、最上部から最下部、及び最下部から最上部に、任意の順序で並列に走査する工程、及び
（ｉｉ）前記ピクセルがいずれのエッジ内にも位置せず、そのインデックスが直前のピクセルのインデックスよりも大きい場合、現在のピクセルに前記直前のピクセルと同じインデックスを付与する工程
を実行する工程と、のうち、少なくとも１つを備える、方法。
【請求項５】
請求項１乃至４のうちいずれか１項に記載の方法であって、
前記光学マーカーを検出する工程は、以下のサブ工程、すなわち、
（ｉ）同じ領域にグループ化されている隣接する色の領域の中心の前記凸包を算出する工程と、
（ｉｉ）前記凸包の中の各頂点ｖｎに対して、ｖｎ→ｖｎ‐ｉ及びｖｎ→ｖｎ‐ｉにより形成される線の間の角度を算出する工程と、
（ｉｉｉ）前記算出された角度によって前記頂点を順序付ける工程と、
（ｉｖ）その間で最も大きい角度を有する４つの頂点を保持し、対頂角が閾値より大きい領域を破棄する工程と、
のうちの少なくとも１つを備える、方法。
【請求項６】
請求項１乃至５のうちのいずれか１項に記載の方法であって、
前記光学マーカーを検出する工程は、チェッカーボードの規則性の分析をさらに備え、以下のサブ工程、すなわち、
（ｉ）隣接する領域の２Ｄ空間における中心を用いて凸包を求めるアルゴリズムを適用し、チェッカーボードの前記エッジにある４つの外縁の正方形を見出す工程と、
（ｉｉ）前記４つの外縁の正方形を基準として用いて、固定された正方形の位置を算出して格納する工程と、
（ｉｉｉ）前記分析される領域のグループが十分な領域を有する場合、４つの外縁の正方形を有する最も近いチェッカーボード上の位置に領域を割り当てる工程と、
（ｉｖ）１つを超える領域が同じ位置に割り当てられる場合、そのチェッカーボードを却下する工程と、
のうち、少なくとも１つを備える、方法。
【請求項７】
請求項６に記載の方法であって、
前記４つの外縁の正方形は同じ色であり、好ましくは前記４つの外縁の正方形は黒色である、方法。
【請求項８】
光学マーカーの光学的認識のための方法であって、
画像を取得する工程と、
前記画像の中の隣接する色の領域をフラッドフィルによって識別する工程と、
前記隣接する領域のデータ及びパラメータを抽出する工程と、
複数の同心円を備えるターゲットである光学マーカーを識別するために、前記隣接する領域から抽出され前記データ及びパラメータに基づき前記パラメータを組み合わせることにより光学マーカーを検出する工程と、
を備える、方法。
【請求項９】
請求項８に記載の方法であって、文字を前記隣接する領域のそれぞれに割り当てて、前記複数の同心円の色のシーケンスを識別する工程をさらに備える、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、マーカーの光学的認識のための方法に関する。より具体的には、本開示は、屋外環境におけるマーカーの光学的認識のための頑健な方法に関する。
【背景技術】
【０００２】
屋外環境におけるパターンの検出は、顔認識から照明が変動する環境に置かれているパターンの認識に至るまで、多くの技術分野において研究対象とされてきている、困難な課題である。しかしながら、照明及び全体的なヒストグラムが大幅に変動する可能性がある外部の状況において、光学マーカーを識別するという問題に対しては、ほとんど注意が払われていない。
【０００３】
屋外環境におけるマーカーの光学的認識のための頑健な方法が適用される可能性があるものとしては、
（ｉ）建設現場、造船所、船舶、及びプラットフォームにおける、構成部品、機器、又はその他の対象物の識別及び位置特定、
（ｉｉ）モジュール及びプラットフォームのアッセンブリのための、機器の動的な位置決め用のシステム、
（ｉｉｉ）屋外環境における、臨場感ある仮想現実の適用、
（ｉｖ）有人又は無人の航空機のための、地理位置情報システム及び光学的参照システム、
（ｖ）屋外環境における、構成部品及び機器の位置特定、動きの監視、及び追跡、
（ｖｉ）構成部品のロボット化された位置決めのためのフィードバックシステム、
を挙げることができる。
【０００４】
現在、マーカーの光学的認識は、照明が制御された屋内環境に制限されており、屋外環境における頑健性は要求されていない。これらの方法は、通常、今日において一般的となっている、拡張現実の生成に関連している。
【０００５】
例えば、国際公開第２０１５／１７６１６３号公報は、（ｉ）画像の１つ以上前のフレーム中のマーカーを検出する工程と、（ｉｉ）前記画像の現在のフレームの中のエッジを検出するためにエッジ検出器を用いる工程と、（ｉｉｉ）前のフレームで検出されたマーカーの線分エッジを追跡して新たな線分のセットを見出す工程と、（ｉｖ）新たな線分のセットをグループ化して、凸角点を有する多角形の新たなセットを提供する工程と、（ｖ）多角形の凸角点からホモグラフィを算出する工程と、（ｖｉ）ホモグラフィのリストを生成する工程と、（ｖｉｉ）ホモグラフィを有する入力画像からバイナリデータを抽出する工程と、（ｖｉｉｉ）チェックサム機能及び誤り訂正機能を実行することにより、前記画像がマーカーであるかどうか検証する工程と、（ｉｘ）前記画像がマーカーである場合、前記画像は連続する画像シーケンスであり、マーカーとして識別し、バイナリデータを検証する工程と、を含む、画像の中のマーカーを検出するための方法を開示している。
【０００６】
また、米国特許第８９６３９５７号明細書は、現実の視野を拡張するためのシステム及び方法を開示している。一実施形態において、第１の媒体は、第１の現実の視野に重ね合わされている。透視度の変更、大きさの変更及び位置の変更等、重ね合わされた媒体に対する1つ以上の変更が受信される。第１の現実の視野の少なくとも一部を備える第１のマーカーが生成される。第１の媒体及び／又は第１のマーカーに関連する第１のメタデータも生成される。第１の媒体、第１のマーカー、及び第１のメタデータは、保管場所に送られる。他の実施形態において、第２の媒体、第２のマーカー、及び第２のメタデータが、前記保管場所から受信される。第２のマーカーは、第２の現実の視野の少なくとも一部に一致し、第２の媒体は、第２の現実の視野の少なくとも一部に重ね合わされて、拡張された現実の視野が生成される。
【０００７】
さらに、欧州特許第１７２０１３１号明細書は、（ｉ）実環境の画像データを収集するための手段と、（ｉｉ）前記画像データから仮想の画像データを生成するための手段と、（ｉｉｉ）前記画像データに基づいて実環境の所定のマーカーオブジェクトを識別するための手段と、（ｉｖ）前記所定のマーカーオブジェクトに対応して、仮想の画像の位置でオブジェクト画像データのセットを前記仮想の画像データに重ね合わせるための手段と、を備える、拡張現実の方法及びシステムを開示している。
【０００８】
しかしながら、上記文献で開示された方法はいずれも、屋外環境でのマーカーの識別において、頑健性を提供する工程を開示していない。
【０００９】
これらに加えて、既知の通り、光学的認識のために最も利用されている技術はＡＲＴｏｏｌＫｉｔであり、拡張現実の生成において広く利用されている。ＡＲＴｏｏｌＫｉｔアルゴリズムは、以下の工程、すなわち、
１．画像の取得工程と、
２．デジタル化工程と、
３．接続される構成要素の識別工程と、
４．細かいエッジの識別工程と、
５．頂点及び辺の抽出工程と、
６．パターンの正規化工程と、
７．テンプレートとの比較工程と、
８．ホモグラフィ及びカメラの変換工程と、
９．仮想オブジェクトの包含工程と、
を備える。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、当該技術は、工業及び建設現場の環境における利用に対してあまり頑健でないという重大な制限がある（無制御の照明又は部分的遮蔽がある状況下では、マーカーを認識することができない）。特に、上記の工程３、４、５、及び７は、照明の変動及び部分的遮蔽に非常に影響されやすいため、当該技術は、屋外環境で適用する際に、十分な頑健性が得られない。
【００１１】
構成要素に特有のマーカーを固定する必要がある、無線周波数識別（ＲＦＩＤ）やＶＩＣＯＮシステム等のその他の追跡技術も存在するが、それらはデータベース及び複雑なデータ取得機器を必要とする。
【００１２】
このように、先行技術において、屋外環境で通常遭遇する無制御の照明又は部分的遮蔽の状況においても頑健な、一般的に使用されるマーカーの光学的認識のための技法が必要とされている。
【００１３】
以下に詳細に説明するように、本開示は、上記の先行技術の問題を、実用的かつ効率的な方法で解決することを目的としている。
【００１４】
本開示は、無制御の照明又は部分的遮蔽の状況においても頑健な、屋外環境でのマーカーの光学的認識のための方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
本開示に従って、光学マーカーの光学的認識のための方法であって、画像を取得する工程と、前記画像の中の隣接する色の領域をフラッドフィルによって識別する工程と、前記隣接する領域のデータ及びパラメータを抽出する工程と、前記隣接する領域から抽出された前記データ及びパラメータに基づいて、凸包を求めるアルゴリズム及び正方形の位置の予測により光学マーカーを検出する工程と、を備える方法が提供される。当該方法は、屋外環境での利用に、特に適している可能性がある。
【００１６】
前記光学マーカーは、同心円またはチェッカーボードを備えるターゲットであってもよい。
【００１７】
前記画像中の隣接する色の領域を識別する工程は、以下のサブ工程、すなわち、前記画像に少なくとも１つのフィルタをかける工程と、前記隣接する色の異なる領域を分離するために前記画像のエッジを検出する工程と、フラッドフィルを用いて前記分離された領域の塗りつぶしを実行する工程と、前記隣接する色の異なる領域のそれぞれを、それらの特性によって識別する工程と、を備えていてもよい。
【００１８】
前記分離された領域の塗りつぶしを実行する前記サブ工程は、以下のサブ工程、すなわち、エッジマップを受け取る工程と、色領域のマップを作成する工程と、特有な色番号であるインデックスを各ピクセルに割り当てることによって、前記色領域のマップを初期化する工程と、前記色領域のマップが変更されなくなるまで、以下の工程、すなわち、（ｉ）前記色領域のマップを、左から右、右から左、最上部から最下部、及び最下部から最上部に、任意の順序で並列に走査する工程、及び（ｉｉ）前記ピクセルがいずれのエッジ内にも位置せず、そのインデックスが直前のピクセルのインデックスよりも大きい場合、現在のピクセルに前記直前のピクセルと同じインデックスを付与する工程を実行する工程と、のうち、少なくとも１つを備えていてもよい。
【００１９】
前記光学マーカーを検出する工程は、以下のサブ工程、すなわち、（ｉ）同じ領域にグループ化されている隣接する色の領域の中心の前記凸包を算出する工程と、（ｉｉ）前記凸包の中の各頂点ｖｎに対して、ｖｎ→ｖｎ‐ｉ及びｖｎ→ｖｎ‐ｉにより形成される線の間の角度を算出する工程と、（ｉｉｉ）前記算出された角度によって前記頂点を順序付ける工程と、（ｉｖ）その間で最も大きい角度を有する４つの頂点を保持し、対頂角が閾値より大きい領域を破棄する工程と、のうち、少なくとも１つを備えていてもよい。
【００２０】
光学マーカーを検出する工程は、チェッカーボードの規則性の分析をさらに備え、以下のサブ工程、すなわち、（ｉ）隣接する領域の２Ｄ空間における中心を用いて凸包を求めるアルゴリズムを適用し、チェッカーボードのエッジにある４つの外縁の正方形を見出す工程と、（ｉｉ）４つの外縁の正方形を基準として用いて、固定された正方形の位置を算出して格納する工程と、（ｉｉｉ）前記分析される領域のグループが十分な領域を有する場合、４つの外縁の正方形を有する最も近いチェッカーボード上の位置に領域を割り当てる工程と、（ｉｖ）１つを超える領域が同じ位置に割り当てられる場合、そのチェッカーボードを却下する工程と、のうち、少なくとも１つを備えていてもよい。
【００２１】
前記４つの外縁の正方形は、同じ色であってもよい。また、前記４つの外縁の正方形は、黒色であってもよい。
【００２２】
本開示に従って、光学マーカーの光学的認識のための方法であって、画像を取得する工程と、前記画像の中の隣接する色の領域をフラッドフィルによって識別する工程と、前記隣接する領域のデータ及びパラメータを抽出する工程と、複数の同心円を備えるターゲットである光学マーカーを識別するために、前記隣接する領域から抽出され前記データ及びパラメータに基づき前記パラメータを組み合わせることにより光学マーカーを検出する工程と、を備える方法も提供される。
【００２３】
当該方法は、文字を前記隣接する領域のそれぞれに割り当てて、前記複数の同心円の色のシーケンスを識別する工程をさらに備えていてもよい。
【００２４】
本開示に従って、ａ）画像を取得する工程と、ｂ）パラレルフィルにより、前記画像の中の隣接する色の領域を識別する工程と、ｃ）前記隣接する領域のデータ及びパラメータを抽出する工程と、ｄ）凸包を求めるアルゴリズム及び正方形の位置の予測によってターゲット及びチェッカーボードを検出する工程と、のうち、少なくとも１つを備えることを特徴とする、屋外環境でのマーカーの光学的認識のための方法も提供する。
【００２５】
前記画像中の隣接する色の領域を識別する工程（ｂ）は、以下のサブ工程、すなわち、前記画像に少なくとも１つのフィルタをかける工程と、隣接する色の異なる領域を分離するためにエッジを検出する工程と、パラレルフィルを用いて前記分離された領域の塗りつぶしを実行する工程と、その特性に従って前記異なる領域のそれぞれを識別する工程と、を備えていてもよい。
【００２６】
前記領域の塗りつぶしを実行する前記サブ工程は、以下のサブ工程、すなわち、エッジマップを受け取る工程と、色領域のマップを作成する工程と、各ピクセルをインデックスと呼ばれる特有の色番号に割り当てることにより、前記色領域のマップを初期化する工程と、色領域のマップが変更されなくなるまで以下の工程、すなわち、（ｉ）前記領域のマップを、左から右へ、右から左へ、最上部から最下部へ、及び最下部から最上部へ任意の順序で並列に走査する工程、及び（ｉｉ）前記ピクセルがいずれのエッジ内にも位置せず、またそのインデックスが直前のピクセルのそれより大きい場合、現在のピクセルに前記直前のピクセルと同じインデックスを付与する工程を実行する工程と、のうち、少なくとも１つを備えていてもよい。
【００２７】
凸包を求めるアルゴリズム及び正方形の位置の予測によってターゲット及びチェッカーボードを検出する工程（ｄ）は、以下のサブ工程、すなわち、（ｉ）同じ領域にグループ化されている隣接する色の領域の中心の前記凸包を算出する工程と、（ｉｉ）前記凸包の中の各頂点ｖｎに対して、ｖｎ→ｖｎ‐ｉ及びｖｎ→ｖｎ‐ｉにより形成される線の間の角度を算出する工程と、（ｉｉｉ）その角度により前記頂点を順序付ける工程と、（ｉｖ）最初の４つの頂点を保持し、対頂角が互いに非常に異なる領域を破棄する工程と、のうち、少なくとも１つを備えていてもよい。
【００２８】
凸包を求めるアルゴリズム及び正方形の位置の予測によってターゲット及びチェッカーボードを検出する工程（ｄ）は、チェッカーボードの規則性の分析をさらに備え、以下のサブ工程、すなわち、（ｉ）隣接する領域の２Ｄ空間における中心を用いて凸包を求めるアルゴリズムを適用し、前記エッジにある正方形を見出す工程と、（ｉｉ）４つの黒色の外縁の正方形を基準として用いて、固定された正方形の位置を算出して格納する工程と、（ｉｉｉ）前記分析される領域のグループが十分な領域を有する場合、最も近いチェッカーボード上の位置に領域を割り当てる工程と、（ｉｖ）１つを超える領域が同じ位置に割り当てられる場合、そのチェッカーボードを除外する工程と、のうち、少なくとも１つを備えていてもよい。
【００２９】
上記の目的を実現するために、本開示は、（ａ）画像を取得する工程と、（ｂ）前記画像の中の隣接する色の領域をフラッドフィルによって識別する工程と、（ｃ）前記隣接する領域のデータ及びパラメータを抽出する工程と、（ｄ）凸包を求めるアルゴリズム及び正方形の位置の予測によってターゲット及びチェッカーボードを検出する工程と、を備える、屋外環境でのマーカーの光学的認識のための方法を提供する。
【図面の簡単な説明】
【００３０】
以下に示す詳細な説明では、添付の図及びそれらの各参照番号を参照する。
【００３１】
【図１ａ】本開示の方法が適用される例示画像を灰色で示す図である。
【図１ｂ】図１ａに関して、各インデックスを付したカラーマップの初期化を示す図である。
【図２ａ】本実施例に適用された、Ｓｏｂｅｌ法の典型的なエッジマップを示す図である。
【図２ｂ】本実施例に適用された、左から右への第１の走査を示す図である。
【図３ａ】本実施例に適用された、右から左への第１の走査を示す図である。
【図３ｂ】本実施例に適用された、最上部から最下部への第１の走査を示す図である。
【図４ａ】本実施例に適用された、最下部から最上部への第１の走査を示す図である。
【図４ｂ】本実施例に適用された、左から右への第２の走査を示す図である。
【図５ａ】本実施例に適用された、右から左への第２の走査を示す図である。
【図５ｂ】本実施例に適用された、最上部から最下部への第２の走査を示す図である。
【図６ａ】本実施例における、最下部から最上部への第２の走査、左から右への第３の走査、及び右から左への第３の走査後の、マップの最終形態を示す図である。
【図６ｂ】領域が特有の色で識別されている、本実施例のマップの最終形態を示す図である。
【図７】リング形式における、隣接する色の領域を示す図である。
【図８】不規則なパターンと比較したチェッカーボードを示す図である。
【図９】様々な位置及び傾きで識別される、様々な大きさのチェッカーボードを示す図である。
【図１０】様々な位置及び傾きで識別される、様々な大きさのチェッカーボードを示す図である。
【図１１】チェッカーボードの識別が本開示の方法によって依然としてうまく行われる遮蔽パターンの実施例を示す図である。
【図１２】本開示の方法によって識別可能なターゲット（マーカー）のパターンの実施例を示す図である。
【図１３】本開示の方法によって識別可能なターゲット（マーカー）のパターンの実施例を示す図である。
【発明を実施するための形態】
【００３２】
関連出願の相互参照
本出願は、２０１８年２月１９日に提出されたブラジル特許出願第１０  ２０１８  ００３１２５‐２の優先権の利益を主張し、その全体が参照により本明細書の中に組み込まれる。
【００３３】
最初に、以下に記載する説明は、好ましい実施形態に基づいていることを強調する。ただし、当業者にとって明白であるように、本発明は当該特定の実施形態に限定されない。
【００３４】
本開示は、マーカーの光学的認識のための方法を提供する。本方法は、屋外環境でのマーカーの認識に、特に適している可能性がある。本方法の第１の工程（ａ）は、画像を取得することであってもよい。当該画像は、認識を実行することが望まれる環境に配置された、光学マーカーを備えることが好ましい。当該光学マーカーは、同心円を備えたターゲット又はチェッカーボード（すなわち、黒色と白色の正方形等の、交互に着色された正方形から構成される領域）であってもよい。当該画像は、任意の適切な方法、例えば、カメラを用いることにより、取得することができる。
【００３５】
本方法の第２の部分は、画像の隣接する色の領域を、フラッドフィル（パラレルフィルとしても知られている）によって識別する工程（ｂ）である。本方法の当該部分は、以下の工程、すなわち、
（ｉ）任意に選択される、前記画像に少なくとも１つのフィルタをかける工程と、
（ｉｉ）隣接する色の異なる領域を分離するために、エッジを検出する工程と、
（ｉｉｉ）フラッドフィルを用いて分離された領域の塗りつぶしを実行する工程と、
（ｉｖ）隣接する色の異なる領域のそれぞれを、その特性によって識別する工程と、
に分けられることが好ましい。
【００３６】
工程（ｉｉ）は、先行技術で広く知られている、Ｓｏｂｅｌ法等の多数のエッジアルゴリズムを用いて実行できることが好ましい。文書「ＢＡＧＬＯＤＩ，Ｖ．エッジ検出の比較研究及び新たな方法の考察（Edge detection comparison study and discussion of new methodology）．ＩＥＥＥ  Ｓｏｕｔｈｅａｓｔｃｏｎ  ２００９．[Ｓ．Ｉ．：ｓ．ｎ．]、２００９．Ｐ．４４６‐４４６．  ＩＳＳＮ  １０９１‐００５０」に、Ｓｏｂｅｌ法の使用について詳細に記載されており、その内容が参照により本明細書に組み込まれる。
【００３７】
フラッドフィルを用いて分離された領域の塗りつぶしを実行する工程（ｉｉｉ）は、以下のサブ工程、すなわち、
（ｉｉｉ‐ａ）エッジマップを受け取る工程と、
（ｉｉｉ‐ｂ）色領域のマップを作成する工程と、
（ｉｉｉ‐ｃ）各ピクセルに、色を表す特有のインデックス番号を割り当てることによって、色領域のマップを初期化する工程と、
（ｉｉｉ‐ｄ）色領域のマップが変更されなくなるまで、以下の工程、すなわち、
（ｉｉｉ‐ｄ‐１）領域のマップを、左から右、右から左、最上部から最下部、及び最下部から最上部に、任意の順序で並列に走査する工程、及び
（ｉｉｉ‐ｄ‐２）ピクセルがいずれのエッジ内にも位置せず、そのインデックスが前のピクセルのそれより大きい場合、現在のピクセルに前のピクセルと同じインデックスを付与する工程、
を実行する工程と、を備えることが好ましい。
【００３８】
図１乃至図６は、この目的のために作成された画像を用いて隣接する色の領域を識別するための、提案されたアルゴリズムを示している。特に、図１ａ及び図１ｂは、それぞれ、灰色の例示画像と、それぞれのインデックスを有する色マップの初期化とを示している。図２ａ及び図２ｂは、それぞれ、Ｓｏｂｅｌ法の典型的なエッジマップと、左から右への第１の走査とを示している。各行において、左から右に走査したとき、エッジ内に配置されておらず、前のピクセルより大きい数字を有するピクセルは、前のピクセルと同じ数字が付与される。例えば、図２ａのピクセル１‐１４は、図２ｂにおいて数字「０」が付与される。他方、ピクセル３１‐４９は、エッジ領域の一部であるため、数字の再付与はされない。図３ａ及び図３ｂは、それぞれ、右から左への第１の走査（図２ｂからの変更はない）と、最上部から最下部への第１の走査とを示している。図４ａ及び図４ｂは、それぞれ、最下部から最上部への第１の走査（図３ｂからの変更はない）と、左から右への第２の走査とを示している。図５ａ及び図５ｂは、それぞれ、右から左への第２の走査と、最上部から最下部への第２の走査とを示している。図６ａは、最下部から最上部への第２の走査（変更はない）、左から右への第３の走査（変更はない）、及び右から左への第３の走査後のマップの最終形態を示している。
【００３９】
図６ｂに示すように、アルゴリズムが終了したとき、画像の２つの領域が識別される。並列の作業アイテムの数は、行を走査するときの画像の高さ、及び列を走査するときの画像の幅に等しい。これにより、フルＨＤ画像（１９２０×１０８０ピクセル）を処理するとき、各場合において１０００を超える作業アイテムが生成される場合がある。エッジのインデックスの変化は、現在のピクセルのインデックスが前のピクセルのインデックスより大きいときにのみ起きるため、全ての方向（左から右、右から左、最上部から最下部及び最下部から最上部）の走査が必要となる。
【００４０】
上述した工程（ｉｉｉ）のアルゴリズムが終了したとき、異なる領域をその特性によって識別する、次の工程が実行される。異なる領域のそれぞれをその特性によって識別する工程（ｉｖ）は、前記特性を特徴づけること（すなわち、測定、算出、又は演算すること）を含むことが好ましい。換言すると、各領域に対して少なくとも１つの特性を算出し、そしてそれをその領域の識別子として（又は識別するために）使用することができる。所定の形状の領域に対して算出することができる特性の例を、以下の表に示す。
【表１】
2021516388.tif 000003
【００４１】
本方法の第３の部分は、隣接する領域のデータ及びパラメータを抽出する工程（ｃ）である。当該工程において、各種類の領域には特定のパラメータがあるため、その特性の算出は、領域の種類又はフォーマット（例えば、形状）に応じて実行される。
【００４２】
例えば、同心円の領域は、図７に示すように、同じ色の複数のリングで構成されている場合がある。この場合は、各リングの幅はｗで、中心との平均距離はｒである。領域の特性に関するデータは、下記の表２に示されており、領域の特性をリング形式で近似するために使用されてもよい。換言すると、表２の第２列は、リング状領域に関する以下の特性の、正確な数学的定義を示している。次に、第３列は、特性が表１の特性とどのように関連付けられているかを示すため、表１の第２列の「計算方法」は、特にリング状領域の特性を算出するために使用することができる。
【表２】
2021516388.tif 000004
【００４３】
光学マーカーを識別するために、隣接する領域を識別して指定するための基準が提案されている。以下の表３に提示されているように、領域の特性（表１に規定された特性等）により、どの領域が他の領域に隣接しているかを決定することが可能である。すなわち、表１の特性は、以下に示すように、隣接領域を識別して指定するために使用することができる。
【表３】
2021516388.tif 000005
【００４４】
隣接データ（すなわち、抽出された隣接領域のデータ及びパラメータ）の後処理により、隣接グループを生成することができる。隣接グループは、図８に示すように、可視化及びデバッグの理由のために、ランダムな共通の色の円を用いて好ましく印を付けることができる。そのような後処理の１つの可能な方法を、以下の工程（ｄ）で説明する。
【００４５】
チェッカーボードは、規則性のはっきりとした特性を有する隣接領域の、特別な事例であることを強調したい。新しいアルゴリズムでは、この概念を、隣接領域のその他のパターンを識別し、新しいカスタマイズされた光学マーカーを作成するための基礎として用いることができる。
【００４６】
上記の後処理の例は、本方法の第４の部分である、凸包を求めるアルゴリズム（凸閉包を求めるアルゴリズムとしても知られている）及び正方形の位置の予測によって、ターゲット及びチェッカーボード等の光学マーカーを検出する工程（ｄ）である。
【００４７】
チェッカーボードの識別に関する特別な場合では、識別は、グループの中の隣接する色の領域の数を数えること、及び内部空間の規則性を調べることによって実行されてもよい。
【００４８】
一実施例において、凸包を求めるアルゴリズム及び正方形の位置の予測によって、ターゲット及びチェッカーボードを検出する工程（ｄ）は、隣接領域のグループに適用される後処理を備え、チェッカーボードの頂点の位置を特定し、ポイントクラウドに長方形を挿入し、以下のサブ工程、すなわち、
（ｉ）同じ領域にグループ化されている隣接する色の領域の中心の凸包を算出する工程と、
（ｉｉ）凸包の各頂点ｖｎに対して、ｖｎ→ｖｎ‐ｉ及びｖｎ→ｖｎ‐ｉにより形成される線の間の角度を算出する工程と、
（ｉｉｉ）算出された角度によって凸包の頂点を順序付ける工程と、
（ｉｖ）その間で最も大きい角度を有する最初の４つの頂点を保持し、対頂角が閾値より大きい（すなわち、互いに非常に異なる）領域を破棄する工程、換言すると、頂点間で最も大きい角度を有する頂点は、チェッカーボードの角にあるものと想定する工程と、
を備える。
【００４９】
平面的なチェッカーボードは、十分に曲率が小さい、機器の部品を識別するために好ましく使用される。曲率が小さいとき、その表面に接着剤で付けられたマーカーは、大幅な変形を受けることはないであろう。チェッカーボードが背景色と異なる色の４つの角の正方形を有するとき、チェッカーボードの角を検出することができ、それゆえ、その寸法を判定することができる。チェッカーボードの全ての頂点（すなわち、角の正方形）は、黒色の正方形で構成されることが好ましい。チェッカーボードの角の正方形検出の信頼性を向上させるために、フィルタ（例えば、高コントラストのフィルタ）を使用してもよい。これは、角の正方形が黒色でないときや、角の正方形の色が背景色と著しく異なっていないときに、特に有用であることがある。
【００５０】
本開示に係る方法は、複数の校正済みカメラを備えるシステムの開発に適用されてもよい。これにより、チェッカーボードのマーカーから法線ベクトルデータを抽出することが可能となり、その構成部品の配向及び位置決めが正しいことを確認することが可能となる。
【００５１】
ひとたびチェッカーボードの寸法が分かると（上記の方法に従って行うことができる）、その内部の領域の中心が位置している場所を推定することができる。チェッカーボードの規則性の分析は、以下のサブ工程、すなわち、
（ｉ）隣接する領域の２Ｄ空間における中心を用いて凸包を求めるアルゴリズムを適用し、チェッカーボードの前記エッジにある４つの外縁の正方形を見出す工程と、
（ｉｉ）４つの外縁の正方形を基準として用いて、固定された正方形の位置を算出し、格納する工程と、
（ｉｉｉ）分析されている領域のグループが十分な領域を有する場合、４つの外縁の正方形を有する最も近いチェッカーボード上の位置に領域を割り当てる工程と、
（ｉｖ）１つを超える領域が同じ位置に割り当てられる場合、そのチェッカーボードを除外する工程と、
に従って、隣接する色の領域のグループで実行される。
【００５２】
工程（ｉｉｉ）は、領域のそれぞれを、チェッカーボード上のそれぞれの推定位置（すなわち、固定された正方形）に割り当てるために用いられる。グループの中に十分な領域が存在しない場合は、工程（ｉｉｉ）を省略してもよい。これは、例えば、マーカー上のチェッカーボードの領域が不明瞭な場合であろう。
【００５３】
工程（ｉｖ）は、チェッカーボードの外縁の正方形として識別された、４つの正方形が正しく識別されたことを確認する。工程（ｉｉｉ）において、1つを超える領域がチェッカーボード上の同じ位置に割り当てられた場合、これは、チェッカーボード上の同じ位置に割り当てられる領域が、実際にはチェッカーボードの一部ではないことを示している可能性がある。これにより、次に、外縁の正方形として識別された４つの正方形が、実際には単一のチェッカーボードの４つの外縁の正方形ではないと判定することが可能になる。この場合、当該チェッカーボードは除外される。
【００５４】
上述した外縁の正方形は、背景と異なる色を有すると判定することにより、識別されてもよい。それらは、全て同じ色を有してもよいし、例えば、上記の４つの黒色の正方形であってもよい。
【００５５】
上記の規則性の分析により、図９及び図１０に示すように、様々な大きさを連続して点検することにより、チェッカーボードの寸法を自動的に識別することが可能になる。これらの図から、異なる種類の複数のターゲットを、同じ画像で識別できることが分かる。
【００５６】
規則性の分析により、チェッカーボードの正方形の中の部分的遮蔽を補正することも可能である。換言すると、チェッカーボードは、一部の正方形が見えないときでも、なお識別することが可能である。隣接する領域のグループは、部分的遮蔽の影響を受ける場合があるか、又は明度の状態に起因して、その内部の領域が適切に識別されない場合がある。これらの場合、頂点の４つの黒色の正方形（すなわち、角）が目に見える限り、効果的に識別された領域の中心を正方形の予想される位置と比較することによって、いくつかの正方形が認識されない場合においても、チェッカーボードの認識が可能になる。
【００５７】
規則性の分析は、ボード上で想定されている全ての位置が色領域により占められていない場合でも、チェッカーボードを受け入れる（すなわち、検出することができる）。図１１は、ボードの識別がなお正常に行われる遮蔽パターン（重ね合わされた正方形として表されている）の例を示している。これは、チェッカーボードの一部の個々の正方形の領域が不明瞭であるにもかかわらず、チェッカーボードの角の正方形を検出でき、かつ全体の形状及び寸法が判定できるからである。
【００５８】
同心円を備える（チェッカーボードではなくて）ターゲット形状のマーカーの識別の場合、以下の表４に示すように、隣接する色の領域の特有な特性が、この種類のマーカーに対して使用される。以下の特性により、リング形状の領域を識別することが可能になり、そしてまた、ターゲット形状のマーカーの中央の円形領域が可能になることが理解されよう。
【表４】
2021516388.tif 000006
【００５９】
隣接する色の領域の識別後、どのピクセルが各領域（[ｘ、ｙ]座標のリスト）に属するか等の領域のデータを抽出し、格納することができ、それにより、表１に示すパラメータを算出することができる。これらのパラメータを組み合わせることによって、ターゲット（図１２に示すように、同心円領域‐中心が互いに近接している同じ色のリング）及び隣接する領域（特性が実質的に等しい、オーバーラップのない隣接する色の領域）を識別することができる。ターゲットは、次のインデックス、すなわち、Ｗ：白、Ｐ：黒、Ｒ：赤、Ｇ：緑、Ｂ：青、？：識別されていない色（Ｗ、Ｐ、Ｒ、Ｇ、又はＢとして識別されない）に従って、その色のシーケンスに関連する文字のシーケンスにより識別される。
【００６０】
例えば、シーケンスＲＷＰ？Ｇは、最も内側の領域の色は赤であり、続いて白、黒、識別されていない色、及び緑であることを示している。図１２及び図１３は、提案されたアルゴリズムの結果を示している。
【００６１】
このように、本開示の方法により、部分的遮蔽及び／又は照明が変動する状況においても、明確にかつ十分な頑健性を持って、チェッカーボード及び同心円を備えるターゲット等のマーカーの識別が可能になる。
【００６２】
本出願の保護範囲内に入る、多くの変形が可能である。これは、本発明が上記の特定の形態又は実施形態に限定されないという事実を強調するものである。
【００６３】
上記の機器及び方法の修正、実施可能な様々な変形例の間の組み合わせ、及び当業者にとって明白な本発明の態様の変形例は、特許請求の範囲の趣旨及び範囲内にあることが意図されている。
【図１ａ】
2021516388.tif 000007
【図１ｂ】
2021516388.tif 000008
【図２ａ】
2021516388.tif 000009
【図２ｂ】
2021516388.tif 000010
【図３ａ】
2021516388.tif 000011
【図３ｂ】
2021516388.tif 000012
【図４ａ】
2021516388.tif 000013
【図４ｂ】
2021516388.tif 000014
【図５ａ】
2021516388.tif 000015
【図５ｂ】
2021516388.tif 000016
【図６ａ】
2021516388.tif 000017
【図６ｂ】
2021516388.tif 000018
【図７】
2021516388.tif 000019
【図８】
2021516388.tif 000020
【図９】
2021516388.tif 000021
【図１０】
2021516388.tif 000022
【図１１】
2021516388.tif 000023
【図１２】
2021516388.tif 000024
【図１３】
2021516388.tif 000025
【国際調査報告】
2021516388.tif 000026
2021516388.tif 000027
2021516388.tif 000028
2021516388.tif 000029