(57)【要約】【課題】モバイル機器の位置を得るための方法、装置、およびコンピュータ・プログラム製品を提供する。【解決手段】本発明は、画定された空間中のターゲットの画像を得るステップと、識別データおよび画像位置データを得るために画像を解析するステップであって、画像位置データがターゲットを基準とする基準点の画像中の位置を含むステップと、画定された空間中のターゲットの位置を含むターゲット位置データを得るために識別データを用いるステップと、画像位置データおよびターゲット位置データを組み合わせることにより、画定された空間中の基準点の位置を求めるステップと、を含む。【選択図】図２
2009522563.tif 000002
【特許請求の範囲】
【請求項１】
画定された空間中のターゲットの画像を得るステップと、
識別データおよび画像位置データを得るために前記画像を解析するステップであって、前記画像位置データが前記ターゲットを基準とする基準点の前記画像中の位置を含むステップと、
前記画定された空間中の前記ターゲットの位置を含むターゲット位置データを得るために前記識別データを用いるステップと、
前記画像位置データおよび前記ターゲット位置データを組み合わせることにより、前記画定された空間中の前記基準点の位置を求めるステップと、
を含む、
方法。
【請求項２】
前記基準点が、前記画像が撮られた位置を表す、請求項１に記載の方法。
【請求項３】
前記位置データが、前記画定された空間中のターゲットについての画定された空間方位データをさらに含み、前記方法は、
前記ターゲットを基準として前記画像が撮られた方向を含む画像方位データを得るために前記画像を解析するステップと、
前記画像方位データおよび前記画定された空間方位データを組み合わせることにより、前記画定された空間中で前記画像が撮られた方向を求めるステップと、
をさらに含む、
請求項２に記載の方法。
【請求項４】
前記画像が第２のターゲットを含み、前記基準点が第２のターゲットを表す、請求項１に記載の方法。
【請求項５】
前記ターゲットが反射性であり、前記方法は、
前記ターゲットの画像を得る目的で、光源に前記ターゲットを照明させるステップを、
さらに含む、
請求項１に記載の方法。
【請求項６】
画像中でターゲットがあまり目立たないように前記ターゲットを照明する前記光源なしで所定の位置から第１の画像を得るステップと、
前記画像中で前記ターゲットがより目立つように前記ターゲットを照明する前記光源を用いて前記所定の位置から第２の画像を得るステップと、
前記第２の画像から前記第１の画像を差し引くことにより前記ターゲットの前記画像を得るステップと、
をさらに含む、
請求項５に記載の方法。
【請求項７】
前記ターゲット位置データを含むデータベース・エントリにアクセスするために前記識別データを用いるステップをさらに含む、請求項１に記載の方法。
【請求項８】
前記ターゲットがバーコードである、請求項１に記載の方法。
【請求項９】
前記画定された空間が店舗であり、前記基準点がショッピング・カートである、請求項８に記載の方法。
【請求項１０】
データ装置であって、
識別データを符号化するターゲットの画像を得るための画像キャプチャ機器と、
前記識別データおよび画像位置データを得るために前記画像を解析ステップであって、前記画像位置データが前記ターゲットを基準とする基準点の前記画像中の位置を含むステップと、
前記画定された空間中の前記ターゲットの位置を含むターゲット位置データを得るために前記識別データを用いるステップと、
前記画像位置データおよび前記ターゲット位置データを組み合わせることにより、前記画定された空間中の前記基準点の前記位置を求めるステップ、
のための、少なくとも１つのプロセッサと、
を含む、
装置。
【請求項１１】
前記ターゲットを照明するための照明機器をさらに含む、
請求項１０に記載の装置。
【請求項１２】
前記照明機器が、複数の照明レベルを出力し、前記照明機器から出力される照明レベルを変えるために前記画像を解析するように出力するために動作可能である、請求項１０に記載の装置。
【請求項１３】
前記画像キャプチャ機器がビデオ・カメラであり、前記装置は、
前記画像キャプチャ機器から前記画像を受信し、前記画像キャプチャ機器からの前記画像を変換するために、画素の所定の輝度レベルに基づいて、前記画像の各画素について２値信号を出力する比較器と、
新しい画像フレームの開始を示す２値信号および新しい画像線の開始を示す２値信号を示すためのビデオ同期分離器と、
を含む、
請求項１０に記載の装置。
【請求項１４】
画像解析特性を向上させるため、所定の輝度レベルを変えるために、前記比較器が、前記所定の輝度レベルを変えるステップをさらに含む、請求項１３に記載の装置。
【請求項１５】
前記識別データおよび前記画像置換データを、前記識別データを用いるためのプロセッサに送信するための通信機器をさらに含む、請求項１０に記載の装置。
【請求項１６】
前記画像キャプチャ機器および前記画像を解析するためのプロセッサが取り付けられるショッピング・カートをさらに含む、請求項１０に記載の装置。
【請求項１７】
デジタル・コンピュータの内部メモリにロード可能なコンピュータ・プログラムであって、前記製品がコンピュータ上で走らされる場合に、請求項１〜９に記載の方法のステップを実行するためのソフトウェア・コード部分を含む、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、モバイル機器追跡（mobile device tracking）に関し、より具体的には、情報を符号化するターゲットを用いてモバイル機器の位置を求めることに関する。
【背景技術】
【０００２】
追跡されるモバイル機器がショッピング・カートである最新の店舗には、追跡の目的のためにモバイル機器の位置が得られる一般的なシナリオがある。カートは、様々な理由により、例えば、隘路を回避しかつ販売促進用に選ばれた特定製品が最も目立つように店舗内に製品を配列する場合に用いるために、店舗内の顧客の流れの知識を得るためにカートが追跡されることがある。例えば、カートの現在位置の知識は、カートを使用している顧客に情報を提供するために用いられ、その情報は、店舗内のその位置に関係しており、そのような情報は、ショッピング・カートと関連付けられた表示機器に提供される。
【０００３】
店舗内のショッピング・カートの位置を追跡する１つの既知の方法は、店舗の天井に等間隔で取り付けられる電動式赤外線ビーコンを用いる。各ビーコンは、一意の区域識別を符号化する赤外線バーストを送信する。赤外線信号は次に、ショッピング・カートに取り付けられた赤外線受信機によって受信され、このようにして、そのショッピング・カートが位置する区域を求めることが可能になる。しかしながら、この方法にはいくつかの問題点がある。例えば、ビーコンは電力を必要とし、結果として、各ビーコン中の電池を定期的に交換するか、それとも電源に接続された高価なワイヤリング・ハーネスを取り付けるかのいずれか一方が必要である。さらに店舗の照明または照明安定器あるいはその両方は、カートの赤外線受信機と干渉することがあり、また、位置の細分性（granularity）は、ビーコン間の距離に依存する。
【０００４】
店舗内のショッピング・カートの位置を追跡する別の既知の方法は、１つ以上の無線ＬＡＮ（ＷＬＡＮ）アクセス・ポイントを用い、カートの位置は、ショッピング・カート上に設置された受信機により測定される種々のアクセス・ポイントについての信号強度を用いて計算される。しかしながら、この方法にも、店舗環境中の金属を含む既知の問題点があり、この金属は、反射およびマルチパスを引き起こし、位置測定の精度を低下させ、そのため十分な空間分解能および堅牢性（robustness）を提供するために付加的なアクセス・ポイントおよび指向性アンテナを店舗に増設しなければならないことがある。さらに、受信された信号、および計算されたカート位置は、アンテナ方位（回転）により影響されることがあり、また、アクセス・ポイントは、電力接続線を必要とする。
【０００５】
モバイル機器についての位置関連活動および追跡も、例えば、この目的のために電子タグ、ＲＦＩＤタグ、またはバーコードを用いることが知られている他の分野で前もって決められている。
【０００６】
例えば、ｄｅＶｏｓらの米国特許第５，０７６，６９０号は、間隔をあけられ、既知の位置に配置された少なくとも３つの逆反射性エレメントを用いて三角測量計算に基づく位置検出を開示している。逆反射性エレメントの１つは、識別可能であるようにバーコードであり得る。逆反射性エレメントの位置を特定し照明するために、光伝送および検出機器を備える回転部材が用いられる。しかしながら、この解決策は、例えば、店舗内のカートの位置を求めるためには適さない。なぜならば、この解決策は、大型店舗内での考え得るすべてのカート位置について実現することが困難であろう少なくとも３つの壁設置反射板への見通し線（line of sight）を必要とするからである。
【０００７】
例えば、Ｅｖｅｒｅｔｔらの米国特許第５，８１２，２６７号は、各々がそれぞれ、光を発生させ、反射板からの反射光信号を検出する２つのセンサを用いて、複数の反射板からの距離を求めることを開示している。各センサからの検出された信号に基づいて反射板からの距離を求めるために、三角測量が次に用いられる。しかしながら、この解決策は、例えば、店舗内のカート位置を求めるためには適さない。なぜならば、この解決策は、それら複数の反射板からの距離のみを計算し、１つの反射板を別の反射板と区別することができないからである。結果として、ショッピング・カートに適さはない既知の前の位置に基づいて位置を計算することしかできない。
【０００８】
例えば、Ｗｉｂｌｅらの米国特許第４，９１８，６０７号は、２つの逆反射性エレメントからの反射を用いる三角測量計算に基づく位置検出を開示しており、これら２つの逆反射性エレメントは各々、バーコードを用いてそれらの位置を符号化する。前もって選択された、間隔を置かれた同一直線上の位置に配置された逆反射性エレメントの位置を特定するために走査プロセスが用いられる。しかしながら、この解決策も、例えば、店舗内のカート位置を求めるためには適さない。なぜならば、走査機構は、選択された領域のみを走査し、逆反射性エレメントが設置されなければならない位置を制限するからである。
【０００９】
さらに、技術的には、逆反射性バーコードを案内システムにおいて用いることが知られている。例えば、Ｆｒａｎｋｒらの米国特許第５，２０２，７４２号は、道路に沿った乗り物案内のためのレーザ・レーダ装置を開示している。ターゲット距離を求めるために反射性ターゲットからの光伝播遅延がされ、レーザ装置と反射性ターゲットとの間の角度を測定するために走査鏡が用いられる。次に、ターゲットからの距離を計算するために、ターゲット距離および角度の三角法の関係が用いられる。反射性ターゲットは、道路の側、接近しつつある出口、制限速度変更等の情報を伝えるバーコードを含み得る。さらに、例えば、Ｆｉｅｌｄらの米国特許第４，７９０，４０２号は、側方の走査レーザ送信機−受信機が経路に沿った逆反射性ターゲットを検出し、乗り物を規定経路上に維持するためにこれらのターゲットが用いられる案内システムを開示している。逆反射性ターゲットは、走査機によるそれらの識別および読み取りをより容易にするために垂直バーコードを含み得る。
【００１０】
しかしながら、案内システムは、例えば、ショッピング・カートが店舗内を予測できないやり方であちこち移動されることがある店舗内のカート位置を求めるのに適した解決策を提供しない。これは、例えば、ターゲットを基準とした乗り物の位置を案内システムが計算し、次いでこの情報が、次のターゲットの位置を特定し乗り物を規定経路上に維持するために用いられるからである。従って、もし乗り物が次のターゲットを見失えば、その乗り物は迷子になり、別のターゲットの次の検出に基づいてその位置を再決定することはできない。しかしながら、ショッピング・カートを伴う顧客は規定の経路をたどらないのが普通なので、単一のターゲットの検出に基づいて位置を求めることが必要である。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
カート位置を求めるために用いられるターゲットが受動的、すなわち、ターゲットが外部電力を全く必要としない、店舗内のショッピング・カートの位置を求めるのに適したシステムを提供することが本発明の目的である。単一のターゲットの検出から店舗内のショッピング・カートの位置を求め、さらに各ターゲットの位置が比較的融通がきくことが、本発明のさらなる目的である。
【課題を解決するための手段】
【００１２】
第１の態様によれば、本発明は、画定された(defined)空間中のターゲットの画像を得るステップと、識別データおよび画像位置データを得るために画像を解析するステップであって、画像位置データがターゲットを基準とする基準点の画像中の位置を含むステップと、画定された空間中のターゲットの位置を含むターゲット位置データを得るために識別データを用いるステップと、画像位置データおよびターゲット位置データを組み合わせることにより、画定された空間中の基準点の位置を求めるステップと、を含む方法を提供する。
【００１３】
好ましくは、本発明は、基準点が、画像が撮られた位置を表す、方法を提供する。
【００１４】
好ましくは、本発明は、位置データが、画定された空間中のターゲットについての画定された空間方位データをさらに含む方法を提供し、この方法は、ターゲットを基準として画像が撮られた方向を含む画像方位データを得るために画像を解析するステップと、画像方位データおよび画定された空間方位データを組み合わせることにより、画定された空間中で画像が撮られた方向を求めるステップと、をさらに含む。
【００１５】
好ましくは、本発明は、画像が第２のターゲットを含み、基準点が第２のターゲットを表す方法を提供する。
【００１６】
好ましくは、本発明は、ターゲットが反射性である方法を提供し、この方法は、ターゲットの画像を得る目的で、光源にターゲットを照明させるステップをさらに含む。
【００１７】
好ましくは、本発明は、画像中でターゲットがあまり目立たないようにターゲットを照明する光源なしで所定の位置から第１の画像を得るステップと、画像中でターゲットがより目立つようにターゲットを照明する光源を用いて所定の位置から第２の画像を得るステップと、第２の画像から第１の画像を差し引くことによりターゲットの画像を得るステップと、を含む。
【００１８】
好ましくは、本発明は、ターゲット位置データを含むデータベース・エントリにアクセスするために識別データを用いるステップをさらに含む。
【００１９】
好ましくは、本発明は、ターゲットがバーコードである方法をさらに提供する。
【００２０】
好ましくは、本発明は、画定された空間が店舗であり、基準点がショッピング・カートを表す方法を提供する。
【００２１】
第２の態様によれば、本発明は、コンピュータ可読プログラムを有するコンピュータ使用可能媒体を含むコンピュータ・プログラム製品を提供し、コンピュータ可読プログラムは、コンピュータ上で実行される場合に、画定された空間中のターゲットの画像を得るステップであって、ターゲットが識別データを符号化するステップと、識別データおよび画像位置データを得るために画像を解析するステップであって、画像位置データがターゲットを基準とする基準点の画像中の位置を含むステップと、画定された空間中のターゲットの位置を含むターゲット位置データを得るために識別データを用いるステップと、画像位置データおよびターゲット位置データを組み合わせることにより画定された空間中の基準点の位置を求めるステップと、を含む方法をコンピュータに実行させる。
【００２２】
基準点の位置を求めるためにターゲット機器の画像が用いられるので、ターゲットは、受動的、例えば、少なくとも２つの異なる色のバーコードであり得る。例えば、画定された空間は、店舗の内部であり得る。
【００２３】
好ましくは、基準点は、画像が撮られた位置を表する。結果として、この方法は、例えば、画像が得られたショッピング・カートのような機器の位置を求めるために用いられ得る。
【００２４】
もし基準点が、画像が撮られた位置を表していれば、任意選択で、位置データは、画定された空間中のターゲットについての画定された空間方位データをさらに含み、画像は、ターゲットを基準として画像が撮られた方向を含む画像方位データを得るためにさらに解析される。これにより、画定された空間中で画像が撮られた方向を、画像方位データおよび画定された空間方位データを組み合わせることによって求めることが可能になる。
【００２５】
画像が撮られた位置を表す基準点の代わりに、基準点は、画像中に少なくとも部分的に含まれる第２のターゲットを表し得る。結果として、ターゲット位置データは、第２のターゲットの、画定された空間中の位置を求めるために用いられる。
【００２６】
例えば、ターゲットは反射性であってもよく、その場合、画像を得る際にターゲットを照明するために光源を用い得る。
【００２７】
もしターゲットを任意に照明するために光源が使用されれば、第１の画像および第２の画像が所定の位置から得られる。第１の画像は、ターゲット画像中にターゲットが現れないように、ターゲットを照明する光源なしで得られ、第２の画像は、ターゲット画像中にターゲットが現れるように、ターゲットを照明する光源を用いて得られる。次に、ターゲットの画像が、第２の画像から第１の画像を差し引くことによって得られる。これにより、ターゲットの一部ではない画像中のどのような背景データも低減され、ターゲットの解析がより容易になる。
【００２８】
任意選択で、識別データは、ターゲット位置データを含むデータベース・エントリにアクセスするために用いられる。代わりに、識別データは、ターゲット位置データを符号化する。
【００２９】
好ましくは、ターゲットは、識別データを得るために復号されるバーコードである。
【００３０】
第３の態様によれば、本発明は、識別データを符号化するターゲットの画像を得るための画像キャプチャ機器と、識別データおよび画像位置データを得るために画像を解析ステップであって、画像位置データがターゲットを基準とする基準点の画像中の位置を含むステップと、画定された空間中のターゲットの位置を含むターゲット位置データを得るために識別データを用いるステップと、画像位置データおよびターゲット位置データを組み合わせることにより、画定された空間中の基準点の位置を求めるステップのための少なくとも１つのプロセッサと、を含む装置を提供する。
【００３１】
例えば、少なくとも１つのプロセッサは、画像を解析するためのマイクロプロセッサおよび基準点の位置を求める識別データを用いるためのデータ・プロセッサを含み得ることに留意されたい。場合によっては、データ・プロセッサは、マイクロプロセッサから離れており、装置は、マイクロプロセッサから識別データを用いるためのデータ・プロセッサに識別データおよび画像置換データを送信するための通信機器をさらに含む。
【００３２】
任意選択で、装置は、ターゲットを照明するための照明機器をさらに含む。例えば、もしターゲットが反射性であれば、画像は、ターゲットが通信機器からの光を反射している間に撮られ得る。
【００３３】
もし装置が照明機器を含めば、任意選択で、照明機器は、複数の照明レベルを出力することが可能であり、少なくとも１つのプロセッサは、照明機器からの照明出力のレベルをさらに変える。
【００３４】
任意選択で、少なくとも１つのプロセッサはさらに、画像キャプチャ機器を制御し、画像を撮る場合にその画像キャプチャ機器に指示する。
【００３５】
画像キャプチャ機器は、例えば、デジタル・カメラまたはビデオ・カメラであり得る。もし画像キャプチャ機器がビデオ・カメラであれば、任意選択で、装置は、比較器およびビデオ同期分離器をさらに含む。比較器は、画像キャプチャ機器から画像を受信し、画像キャプチャ機器からの画像を２値画像に変換するために、画素の所定の輝度レベルに基づいて２値信号を出力する。例えば、比較器は、所定の輝度レベルより暗い画素については１を、所定の輝度レベルより明るい画素については０を出力し得る。ビデオ同期分離器は、新しい画像フレームの開始を示す比較器からの２値信号および新しい画像線の開始を示す比較器からの２値信号を示す。
【００３６】
もし比較器が用いられれば、任意選択で、例えば、ターゲットの識別データの入手をより容易にする画像の特性を改善するために、少なくとも１つのプロセッサが、所定の輝度レベルを変える。
【００３７】
任意選択で、本発明は、画像キャプチャ機器および画像を解析するためのプロセッサが取り付けられるショッピング・カートをさらに含む。
【００３８】
好ましくは、本発明は、ターゲットを照明するための照明機器を含む装置をさらに提供する。
【００３９】
好ましくは、本発明は、照明機器が複数の照明レベルを出力することができ、画像を解析するプロセッサが、照明機器から出力される照明をさらに変える装置を提供する。
【００４０】
好ましくは、本発明は、画像キャプチャ機器がビデオ・カメラである装置を提供し、この装置は、画像キャプチャ機器からの画像を変換するために、画像キャプチャ機器から画像を受信し、画素の所定の輝度レベルに基づいて、画像の各画素についての２値信号を出力するための比較器と、画像フレームの開始を示す２値信号および新しい画像線の開始を示す２値信号を示すためのビデオ同期分離器と、を含む。
【００４１】
好ましくは、本発明は、画像を解析するプロセッサが、画像解析特性を向上させるために、所定の輝度レベルを変える装置を提供する。
【００４２】
好ましくは、本発明は、識別データおよび画像置換データを、識別データを用いるためのプロセッサに送信するための通信機器をさらに含む装置を提供する。
【００４３】
好ましくは、本発明は、画像キャプチャ機器および画像を解析するためのプロセッサが取り付けられるショッピング・カートをさらに含む装置を提供する。
【００４４】
第４の態様から見ると、本発明は、デジタル・コンピュータの内部メモリにロード可能なコンピュータ・プログラムを提供し、このコンピュータ・プログラムは、前記製品がコンピュータ上で走らされる場合に、上記の様な方法のステップを実行するためのソフトウェア・コード部分を含む。
【００４５】
第５の態様によれば、本発明は、画定された空間を提供し、この画定された空間は、この画定された空間内に分布された複数の間隔を置いて配置されたターゲットであって、各バーコードがこの画定された空間中のターゲットの位置を求めるために用いられ得る識別データを符号化するターゲットと、第３の態様による装置と、を含む。
【００４６】
好ましくは、画定された空間は、画定された空間を覆い、ベルクロ（Velcro）を用いてターゲットが取り付けられる表面をさらに含む。
【００４７】
例えば、表面は、天井であり得る。例えば、画定された空間は、店舗であり得る。
【発明を実施するための最良の形態】
【００４８】
本発明の実施形態は、添付図面に関連して、単に例として以下で詳細に説明される。
【００４９】
代表的な実施形態の以下の説明において、本明細書の一部を成す添付図面が参照され、添付図面において、本発明が実施され得る特定の実施形態が例示の目的で示される。本発明の範囲から逸脱することなく成し得る構造的変更として、他の実施形態が利用できることが理解されるべきである。
【００５０】
本発明の好ましい実施形態において、店舗の天井に貼られた逆反射性バーコード・ターゲットを用いて、店舗内のショッピング・カートの位置が求められる。バーコード・ターゲットの画像は、画像中の位置がカートの位置を表すようにショッピング・カートに設置されたカメラを用いて得られる。次に、バーコードを読み取り画像位置データおよび画像方位データを求めるために、画像が解析される。画像位置データは、バーコードを基準としたカートの（画像中の）極座標である「カート／バーコード画像極座標（Cart/Barcode Image Polar Coordinates）」を含む。「カート／バーコード画像極座標」は、カートから画像中のバーコード・ターゲットまでの角度である「カート／バーコード画像角度（Cart/Barcode Image Angle）」、およびカートからバーコード・ターゲットまでの画像中（画像単位）の距離である「カート／バーコード画像半径（Cart/Barcode Image Radius）」を含む。画像方位データは、バーコードを基準としてカートが指し示している方向である「カート／バーコード画像方位（Cart/Barcode Image Orientation）」を含む。データベースにアクセスし、店舗内のバーコード・ターゲットについての物理的方位および位置データである「バーコード／店舗方位（Barcode/Store Orientation）」および「バーコード／店舗位置（Barcode/StoreLocation）」を得させるために、次にバーコード・ターゲットの復号が用いられる。物理的方位および位置データは次に、「カート／店舗位置（Cart/Store Location）」（店舗について定義された基準点および基準線を基準とする店舗内のカートの物理的位置および方位）を求めるために、画像位置データと組み合わされる。これは、図１〜９に関連して詳細に説明される。
【００５１】
図１のａおよびｂは、本発明の好ましい実施形態によるバーコード逆反射性ターゲット（バーコード）の基本的な構成ブロックを示す。図１のａは、各逆反射性区間１０１と同幅の非逆反射性区間１０２により分離された２つの逆反射性区間１０１を示す。２つの逆反射性区間１０１の分離距離は、この場合には「０」ビットである１つのビットを符号化する。図１ｂは、各逆反射性区間１０１の倍幅である非逆反射性区間１０３により分離された２つの逆反射性区間１０１を示す。２つの逆反射性区間１０１のこの分離距離は、「１」ビットを符号化する。各逆反射性区間を、逆反射性区間の長さに関連する長さ、例えば、隣接する逆反射性区間の長さで分離することにより、２つの逆反射性区間の間の分離距離を求めるために用い得る距離基準が提供されることに留意されたい。これは、例えば、バーコードの画像が広角レンズを用いて撮られる場合、または、バーコードが曲面上に設置されている場合に、有用であり得る。
【００５２】
図１のｃは、図１のａおよび１のｂの基本的構成ブロックを用いるバーコードの例を示す。しかしながら、バーコードの第１の要素は、同期シンボル（sync symbol）と呼ばれる２倍長さの逆反射性区間１０４である。この区間の伸長的性質は、バーコードの開始を識別するために用いられ、さらに、その長さが標準の逆反射性区間の長さの２倍であるので、その長さは、バーコードのいくつかの画像を解釈する場合に有用であり得る標準の逆反射性区間の長さを求めるために用いられ得る。バーコードの残りは、非逆反射性区間および標準幅の逆反射性区間が交互になっている。非逆反射性区間はビットを定義し、この例では、区間は、短い区間１０２、続いて長い区間１０３、続いて２つの短い区間１０２となっており、従って、図２ｃのバーコードは、「０１００」のビット列を定義する。
【００５３】
図１のｄは、本発明の好ましい実施形態に従って取られた写真において見られるような、図１のｃのバーコード例の例示である。この図において、逆反射性区間（１１４、１１１）が赤外（ＩＲ）光を反射するのに対して、非逆反射性区間（１１２、１１３）は、反射しない。従って、バーコードにより符号化された値は、バーコードの取られた写真中の反映されたＩＲ光区間の分離距離に基づいて求められる。
【００５４】
本発明の好ましい実施形態において、逆反射性バーコードは、店舗の天井の適切な場所に取り付けられる。図２は、これを、床から天井を見上げた時に見える、代表的な天井の領域について例示している。天井の領域２００は、タイル間の間隙を満たす金属枠によって支えられる天井タイル２０１を含む。天井には、照明２０２および逆反射性バーコード２０３、２０４、２０５、２０６が取り付けられている。バーコードは、天井への取り付けを容易にするために磁性片で裏打ちされており、バーコードの撮られた画像中での光学干渉を回避するために、照明２０２から離して設置される。各バーコードは、図１のａ〜ｄに関連して説明されるように、異なる番号を符号化する。バーコード２０３は、伸長区間（同期シンボル）２０７で始まり、「０００１」を符号化する非反射性区間を含む。同様に、バーコード２０４、２０５、および２０６は、各バーコードが一意に識別可能であるようにおよび、例えば、データベース中で、店舗内のバーコードの物理的方位および位置を記録するエントリと関連付けられ得るように、「００１０」、「００１１」および「０１００」をそれぞれ符号化する。各バーコードの方位が異なるが、これは、各バーコードの開始をマーキングする伸長区間２０７、２０８、２０９、および２１０のために問題とならないことに留意されたい。
【００５５】
カートの底を通って天井を見上げた時の、図２におけるショッピング・カート２１１の眺めも示してある。ショッピング・カート２１１が店舗の物理的基準線２２１に対してある角度で配向されており、物理的基準点２２０からある距離に位置していることに留意されたい。例えば、基準線は、店舗の壁であり得る。角度および距離がどのように計算され得るかが以下説明される。
【００５６】
各バーコードの逆反射性および非逆反射性区間は、それらが、好ましい実施形態により要求されるようにＩＲ光を反射するまたは反射しない機能を実行するのであれば、どのような色／テクスチャであってもよいことに留意されたい。従って、それらの区間は、例えば、天井タイルまたは金属枠あるいはその両方の色を考慮する場合に、それらの区間をあまり目立たなくしたりまたは見た目に美しくしたりあるいはその両方になるようにする色で作ることができる。例えば、もし天井が黒色であれば、タグは、視覚的には暗いがＩＲ透過性のカバーで覆うことができる。
【００５７】
バーコードの非反射性区間の１つ以上が、例えば、一端に相補的なベルクロ材料を有するポールを用いてバーコードの容易な除去を可能にするベルクロ材料の領域を含み得ることにさらに留意されたい。
【００５８】
図３は、本発明の好ましい実施形態による逆反射性バーコード・ターゲットの画像を取得および解釈するために用いられる、ショッピング・カートに取り付けるためのシステム３００の概略図である。システム３００は、逆反射性バーコード・ターゲット、例えば、バーコード３０１からの反射のためのＩＲ光を放出するために用いられる赤外（ＩＲ）ＬＥＤ照明器３０２を含む。どのような反射光の画像も、ＩＲ通過・可視ブロック光学フィルタ３０４を通して単色ビデオ・カメラ３０３により得られる。フィルタは、非ＩＲ光を減少させるが、バーコード３０１により反射されるＩＲ  ＬＥＤ照明器３０２からのＩＲ光のようなＩＲ光を、ビデオ・カメラ３０３まで通過できるようにするために用いられる。
【００５９】
ビデオ・カメラ３０３は、カメラにより撮られた画像の中心がカメラの位置（従って、ショッピング・カートの位置）をおおよそ表し、画像上に引かれた垂直線が、カートが向いている方向を表すように、ショッピング・カートに実質的に垂直に設置されている。しかしながら、他の実施形態においては、画像がそこから撮られた位置が、画像中のバーコードを基準にして求められ得るのであれば、カメラは異なるやり方で設置できる。
【００６０】
ビデオ・カメラ３０３により撮られた画像は、グレー・スケール・ビデオ信号としてアナログ比較器３０５およびビデオ同期セパレータ３０６に伝えられる。アナログ比較器３０５は、グレー・スケール・ビデオ信号を白黒２値信号に変換することによりビデオ信号を単純化し、これは、ＩＲ通過・可視ブロック光学フィルタ３０４がほとんどすべての非ＩＲ光を除去し、天井照明２０２からの直接的なＩＲ光線およびバーコード３０１からの反射ＩＲだけを残すからである。明るいＩＲ光が、アナログ比較器３０５に高い２値信号を出力させるのに対して、暗い背景は、アナログ比較器３０５に低い２値信号を出力させるの。
【００６１】
ビデオ同期セパレータ３０６は、単色カメラ３０３の複合ビデオ信号出力から垂直および水平同期信号を抽出する。マイクロコントローラ３０７は、各画像／フレームの開始を識別し、比較器３０５から受信された各画像画素の画像内のｘおよびｙ位置を求めるために、ビデオ同期セパレータ３０６からのビデオ同期信号を用いる。すべての水平同期信号の冒頭において、Ｘ軸位置カウンタを表すマイクロコントローラ３０７中で走っている内部カウンタは０にリセットされ、新しい画素列の冒頭を示す。すべての垂直同期信号の冒頭において、Ｙ軸位置カウンタは、０にリセットされ、新しいフレームの開始を示す。Ｘ軸位置カウンタは、内部発振器、一般にマイクロコントローラ３０７クロックにより増分される。Ｙ軸位置カウンタは、水平同期信号により増分される。
【００６２】
マイクロコントローラ３７０メモリおよび処理時間の要件を最小限にするため、アナログ比較器３０５の立ち上がりは、割り込みを引き起こす。割り込みルーチンの間、Ｘ軸位置カウンタおよびＹ軸位置カウンタの値が格納される。マイクロコントローラ３０７中の割り込みコントローラは次に、アナログ比較器３０５の立ち下がりで割り込みを生成するように構成され、プロセスは繰り返される。この方法を用いることにより、明るいオブジェクトの開始および停止位置のみが、処理および格納を必要とする割り込みを引き起こし、メモリ・バッファが画像全体を格納する必要およびすべての画像画素を処理する必要がなくなる。
【００６３】
任意選択で、マイクロコントローラ３０７は、赤外ＬＥＤ照明器３０２をさらに含み、この照明器が必要ではない時にはオフにし、バーコード３０１を十分に照明するのに十分なＩＲ照明だけを送るように赤外ＬＥＤ照明器３０２の器を制御し、それによって、電力を節減する。
【００６４】
任意選択で、マイクロコントローラ３０７は、ＩＲ  ＬＥＤ照明器３０２をオンにして第１の画像を撮り、ＩＲ  ＬＥＤ照明器３０２をオフにして第２の画像を撮る。第１の画像は次に、天井照明２０２のようないかなる外部光源も除去するために、第２の画像から差し引かれる。
【００６５】
任意選択で、マイクロコントローラ３０７は、画像を微調整して、バーコード３０１のようなバーコードが、画像中の他のＩＲ光源とよりうまく区別されるようにするためにアナログ比較器３０５についてのしきい電圧を制御する。
【００６６】
マイクロコントローラ３０７は、バーコード３０１を復号し、他の低レベル機能を実行し、次いで、復号されたデータをコンピュータ３０８に送る。
【００６７】
図４のａは、ショッピング・カート２１１から、カートの後部に取り付けられた（天井に向けて垂直上方に向けられており、画像中でカートが画像の下部中心から上部中心を指すように配向されている）カメラ、例えば、図３のシステムのビデオ・カメラ３０３を用いて撮られた逆反射性バーコード・ターゲット２０６の、図２に関連した、画像の例示である。図４のａにおいて、および画像の例示を伴うすべての他の図において、例示は実際上、実際の画像の陰画であり、すなわち、図３の単色カメラ３０３により撮られた画像において、例示中に示される暗い領域は明るく表示され、例示中に示される明るい領域は暗く表示されるであろう。さらに、画像の中心の十字線は画像の一部ではなく、物理的位置（すなわち、店舗内のカメラ／カートの位置）が求められるべき基準点としてシステムにより用いられる画像の中心を示している。言い換えれば、十字線は、カメラのすぐ上方にある画像中の位置である。画像から、バーコードは、値「０１００」（または４）を符号化するように求められ、この値は、店舗内における逆反射性バーコード３０１の物理的方位および位置を提供するエントリを得るために、データベースへのインデックスとして用いられる。
【００６８】
図４のｂは、図４のａの画像であるが、図４のａの画像がそこから撮られたショッピング・カート２１１（図２参照）のイラストを伴っている。カートの底部を通して天井を見上げた時の、図４のｂにおけるショッピング・カート２１１の床からの眺めも示してある。ショッピング・カートは、画像を撮るためにその後部にカメラ４１１が（垂直上方に向けて）取り付けてあり、従って、画像４のｂにおけるカメラ４１１の位置は、図４のａにおける十字線４００の位置と合致する。ショッピング・カートを基準としたカメラの方位のため、図４のｂにおいてカートが向けられている方向（すなわち、図４ａの画像が撮られた時）は、画像の中心を通る垂直線に沿っている。図４のｂにおけるショッピング・カート２１１のバーコードおよび方位が、図２におけるバーコード２０６およびショッピング・カート２１１の方位と一致することに留意されたい。
【００６９】
本発明の好ましい実施形態において、店舗内のバーコードの物理的位置および方位を記述するデータは、データベース中に格納される。このデータは、同期シンボルの中心の物理的／店舗位置およびバーコードの全長に沿ったバーコードの物理的／店舗方位（例えば、図９における角度９０２）を含む。物理的／店舗位置は、店舗内の基準点、例えば、図２の基準点２２０を基準とする、適切な物理単位系のＸおよびＹ座標を含む。好ましい実施形態においては、単位はメートルであるが、他の実施形態においては、他の単位、例えば、フィートまたは天井タイルが用いられ得る。物理的／店舗方位は、店舗基準線、例えば、図２の店舗壁２２１を基準とする角度である。例えば、方位は０〜３６０度の値を含み得る。任意選択で、物理的位置データは、以降の計算において有用であり得る付加的なデータ、例えば、同期シンボルの長さ、バーコードの長さ、およびバーコードの高さ、を含み得る。
【００７０】
図５は、店舗内のショッピング・カートの物理的／店舗位置および方位を得るための本発明の好ましい実施形態の方法のフローチャートである。ステップ５０１において、ショッピング・カートに設置されたカメラから画像が得られ、画像は、少なくとも１つの逆反射性バーコード・ターゲットを含む。画像は、アナログ比較器３０５からの出力に基づく各画素についての１ビットを有する２値画像である。比較器は、画素が明るければ高い信号を出力し、画素が暗ければ低い信号を出力する。
【００７１】
ステップ５０２において、逆反射性バーコードを取得および復号し、画像中のバーコードおよびカートの相対的な位置を基準として画像位置データおよび画像方位データを求めるために画像が解析される。画像位置データは、バーコードからカートまでの角度および距離（画像単位で）を含み、画像方位データは、バーコードを基準としてカートが向いている方向を含む。
【００７２】
画像中のバーコードの方位は、「バーコード画像方位（Barcode ImageOrientation）」と呼ばれる。これは、バーコードの長手寸法を通る線と、画像および同期シンボルの中心を通る水平線である第１の画像基準線との間の度で表される角度である。
【００７３】
画像中のバーコードを基準としてカートが向いている方向は、「カート／バーコード画像方位（Cart/Barcode Image Orientation）」である。これは、バーコードの長手寸法を通る線と、画像を基準としてカートが向いている方向を表す第２の画像基準線との間の角度である。好ましい実施形態において、カメラは、第２の画像基準線が画像に垂直になるようにショッピング・カートに設置される。
【００７４】
バーコードからカートに対するバーコードの相対位置への角度および距離は、それぞれ「カート／バーコード画像角度（Cart/Barcode Image Angle）」および「カート／バーコード画像半径（Cart/BarcodeImage Radius）」である。「カート／バーコード画像角度」は、バーコードの長手寸法を通る線と、画像基準点（十字線）４００の位置からバーコードの同期シンボルの中心まで走る第３の基準線との間の角度である。「カート／バーコード画像半径」は、画像基準点（十字線）４００の位置からバーコードの同期シンボルの中心までの（画像単位で表した）距離である。画像基準点は、ショッピング・カートの位置を表す画像中の位置であり、ショッピング・カート２１１上のカメラ３０３のすぐ上の点である。「カート／バーコード画像角度」および「カート／バーコード画像半径」は一緒に、「カート／バーコード画像極座標（Cart/Barcode Image Polar Coordinates）」を構成する。
【００７５】
ステップ５０３において、データベースにアクセスして店舗内におけるバーコードの物理的方位および位置データを得るためにバーコード・ターゲットの復号が用いられる。
【００７６】
店舗内におけるバーコードの方位は、「バーコード／店舗方位（Barcode/StoreOrientation）」である。これは、バーコードの長手寸法を通る線と、店舗内における基準線、例えば、図２の店舗壁との間の角度である。
【００７７】
バーコードの物理的位置は、「バーコード／店舗位置（Barcode/StoreLocation）」である。これは、店舗基準点、例えば、図２の店舗基準点２２０を基準とした、同期シンボルの中心の位置の（店舗単位で表して）（Ｘ，Ｙ）座標である。
【００７８】
ステップ５０４において、店舗内におけるカートの方位が求められる。これは、「カート／店舗方位（Cart/Store Orientation）」と呼ばれ、「バーコード／店舗方位」と「カート／バーコード画像方位」との組み合わせから求められる。
【００７９】
ステップ５０５において、店舗内におけるカートの位置が、店舗内の基準点、例えば、図２の基準点２２０を基準として求められる。これは、「カート／店舗位置（Cart/Store Location）」と呼ばれ、「バーコード／店舗方位」、「バーコード／店舗位置」および「カート／バーコード画像極座標」を組み合わせることにより求められる。しかしながら、「カート／バーコード画像極座標」の「カート／バーコード画像半径」が最初に画像単位から店舗単位に変換されなければならない。
【００８０】
ステップ５０２の細分化ならびにステップ５０２、５０４および５０５の計算が、図６、７、８、および９に関連して以下でさらに説明される。
【００８１】
図６は、図５の方法ステップ５０２のフローチャートであり、逆反射性バーコード・ターゲットを識別および復号し、さらにバーコードおよびカート位置（画像の中心）に関する画像位置データを求めるために２値画像が解析される。
【００８２】
ステップ６０１において、適切なオブジェクトを識別するために２値画像の列が左から右へ走査される。オブジェクトは、暗画素により包囲された隣接する明画素の集まりとして識別される。走査の間、ラン・レングス・エンコーダ（ＲＬＥカウンタ）は、明画素が暗画素に続く時に開始され、最初のその後の暗画素において停止される。もしＲＬＥカウンタが、バーコード要素の許容可能な幅を表す所定の範囲外にあれば、明画素の列、および何かの他の隣接する明画素は、無視される。なぜならば、それらが表すオブジェクトが、バーコードの一部であるには大きすぎるか小さすぎるからである。さらに、もしオブジェクトが、所定範囲内にない複数の画素を含んでいれば、そのオブジェクトは無視される。なぜならば、そのオブジェクトは、バーコード・セグメントであるには小さすぎるか大きすぎるからである。ひとたびすべての画素、すなわち、画像全体が処理されると、バーコード・セグメントとして適切であると考えられるオブジェクト（セット・ビット）のみを含む２値画像が得られる。
【００８３】
ステップ６０２において、各適切なオブジェクトの幾何学中心が、画像の左下隅からの画素座標によって求められる。
【００８４】
ステップ６０３において、隣接するオブジェクト間に線分を生成し、候補バーコード・セグメントを識別するために、各適切なオブジェクトの幾何学中心が用いられる。線分は、２つのオブジェクト間の距離であり、オブジェクトは、もしそれらの間の線分の長さが所定範囲内にあれば、候補バーコード・セグメントとして識別される。
【００８５】
ステップ６０４において、最も大きい候補バーコード・セグメントが同期シンボル（図１のｃの１０４）であると想定することにより、候補バーコードが識別される。同期シンボルは次に、隣接するバーコード・セグメントを一緒に候補バーコードにするためのアンカ・ポイントとして用いられる。隣接するバーコード・セグメントは、生成された２値画像を、同期シンボルから左右および上下に走査することにより位置を特定される。
【００８６】
ステップ６０５において、識別された候補バーコードの妥当性は、その候補バーコードが正しい数のセグメント（ビット）を有しているか、および任意選択で、正しいパリティを有しているかを調べることによってチェックされる。図には示してないが、例えば、好ましい実施形態において、２つのパリティ・ビットがこの目的のために用いられる。
【００８７】
最後に、ステップ６０６において、バーコードを基準にしてカートが向いている方向（「カート／バーコード画像方位」）およびバーコードを基準にしたカートの（図中における）極座標（「カート／バーコード画像極座標」）が、図５のステップ５０４および５０５において用いるために計算される。
【００８８】
図６の方法において、いくつかの所定の範囲、すなわち、バーコード要素の許容できる幅を表す所定の範囲、許容できるオブジェクト中の画素の数についての所定の範囲、および線分の長さについての所定の範囲、が用いられることに留意されたい。好ましい実施形態において、これらの範囲は、多数のバーコード画像に基づき、経験的に得られる。例えば、もし図６の方法がいつかの画像について実行されれば、有効な識別されたバーコードについてのデータは、適切な範囲を求めるために用いられる。
【００８９】
図５のステップ５０４、および５０５、ならびに図６のステップ６０６の計算を、図７、８および９に関連して例として説明する。
【００９０】
図７は、例えば、店舗の基準壁、例えば店舗壁（図２においても示される）を基準としてバーコードまたはショッピング・カートの店舗方位についての値を求めるために、本発明の好ましい実施形態において用いられる勾配（角度）方式を例示する。この図は、同期シンボル７０２および最後のバーコード・セグメント７０３を含むバーコード７０１を示している。この図に示されるように、バーコードが、同期シンボルを左にして店舗壁２２１と平行になる方位は、０度であると考えられる。もしバーコードが同期シンボル７０２の中心のまわりに反時計回りに回転されれば、最後のバーコード・セグメントの中心は円７０４を描き、この円は、４つの四分円７０５、７０６、７０７、７０８に分割できる。これらの四分円の各々において、ＸおよびＹの相対符号が示してあり、ＸおよびＹは、同期シンボル７０２の中心のｘおよびｙ座標がそれぞれ引かれた末端セグメント７０３の中心のｘおよびｙ座標を表している。従って、三角関数は、＋／−９０度についての角度計算を提供するだけなので、水平線を基準として計算される角度は、四分円７０６および７０７においては＋１８０度、四分円７０８においては＋３６０度調整される必要がある。
【００９１】
図７は、店舗壁２２１を基準として同じく０度配向されているショッピング・カート７０５も示している。０度において、カートは、店舗壁２２１と平行であり、カート前部が右にあり、カート後部が左にある。従って、カート方位の四分円を求めるために、バーコード７０１と比較される場合、カートの前部は、同期シンボル７０２に相当し、カートの後部は、最後のバーコード・セグメント７０３に相当する。結果として、もしカートがカート前部の中心まわりに反時計回りに回転されれば、カート後部の中心は円７０４を描き、この円は、４つの四分円７０５、７０６、７０７、７０８に分割される。
【００９２】
図８は、図４のａの画像であるがバーコードの物理的位置データを適用する前の画像に関連する方位および位置データを得るために実行される計算を説明するために用いられる付加的なマーキングを有する画像（８００）を示す。従って、図２を基準として、この画像は、ショッピング・カート２１１から撮られた逆反射性バーコード・ターゲット２０６のものであり、従って、天井を見上げているカメラからの視野である。図８中のすべての点は、画像の左下隅である画像の原点を基準として、（Ｘ，Ｙ）座標により（画像単位で）によって参照される。理解を容易にするため、図８は、画像を基準とした物理的基準線（店舗壁）２２１の位置も示す。
【００９３】
図８において、点（Ｘ１，Ｙ１）は、画像が撮られた画像中の位置（すなわち、ショッピング・カートの位置）であり、点（Ｘｓ，Ｙｓ）は、画像中のバーコードの同期シンボルの中心の位置であり、点（Ｘｅ，Ｙｅ）は、バーコードの末端セグメントの中心の位置である。これらの点は、画像の左下隅（０，０）を基準としてそれらの画素位置に基づいて求められる。さらに、（Ｘ１，Ｙ１）から（Ｘ１，Ｙｓ）までの線は、画像を通って垂直に走っており、画像が撮られた時にショッピング・カートが向いていた方向を表す。この図は、画像を基準として店舗壁２２１の位置も示している。
【００９４】
画像から計算される方位および位置データは、角度８０２および８０４（度で表される）、ならびに距離８０５（画像距離単位で表される）を含む。角度８０２は、度で表される「カート／バーコード画像方位」およびバーコードを基準としてカートが向いている方向の角度である。角度８０４は、カートからバーコード・ターゲットまでの角度である「カート／バーコード画像角度」である。距離８０５は、カートからバーコード・ターゲットまでの画像中の（画像単位で表される）距離である「カート／バーコード画像半径」である。角度８０４および距離８０５は、「カート／バーコード画像極座標」を構成し、同期シンボルの中心およびバーコードの長手寸法を通る線を基準とした画像の中心の（画像距離単位で表される）極座標である。
【００９５】
角度８０２（「カート／バーコード画像方位」）は、バーコードを基準としてカートが向いている方向であり、画像（Ｘ１，Ｙ１）の中心を通る（画像を基準としてカートが向いている方向を表す）垂直線とバーコードの長さに沿って走る線との間の角度である。角度８０２を求めるために、角度８０１が最初に求められる。角度８０１は、「バーコード画像方位」であり、バーコードの長さに沿って走る線と、図７に関連して説明された方式に基づいて同期シンボルの中心を通って走る画像中の水平線との間の角度を表す。角度８０１は、同期シンボルの中心の位置（Ｘｓ，Ｙｓ）および別のバーコード要素の中心の位置、この例では、最後または末端のバーコード要素の中心の位置（Ｘｅ，Ｙｅ）を用いて求められる。これら２つの位置を用い、角度８０１は、点（Ｘｓ，Ｙｓ）、（Ｘｅ，Ｙｅ）および（Ｘｅ，Ｙｓ）により定義される直角三角形を考慮することにより基本的な三角法を用いて計算される。例えば、図７の方式（別のバーコード要素の座標が同期シンボルの座標から引かれる）に準拠するため、角度８０１は、式ｔａｎ−１（（Ｙｅ−Ｙｓ）／（Ｘｅ−Ｘｓ））を用いて計算され得る。さらに、（Ｙｅ−Ｙｓ）および（Ｘｅ−Ｘｓ）はどちらも負であり、結果として、角度は、図７の四分円７０７の中にある。従って、計算された角度を＋１８０度調整することが必要である。ひとたび角度８０１が分かると、調整された角度８０１および８０２の合計が２７０度であるという事実に基づいて、角度８０２が求められる。角度８０１および８０２の合計が２７０度であることに留意されたい。なぜならば、この角度は、同期シンボルの中心を通って走る水平基準線と、Ｘ１，Ｙ１から画像に垂直上方に水平線までの線との間にあり、図７においては、これは２７０度に相当する。
【００９６】
角度８０４は、画像の中心から同期シンボルの中心への線と、バーコードの長さに沿って走る線との間の角度である。角度８０４を求めるため、角度８０３が最初に求められる。角度８０３は、同期シンボルの中心を通って走る画像中の水平線と、画像の中心から同期シンボルの中心へ走る線との間の角度である。角度８０１を求めるために用いられる同じ三角法の原理を用いて、角度８０３は、＋１８０度調整された式ｔａｎ−１／（Ｔ１−Ｔｓ）（Ｘ１−Ｘｓ）を用いて計算され得る。ひとたび角度８０３が分かると、角度８０４は、角度８０３と８０１との差として計算される。
【００９７】
最後に、距離８０５は、ショッピング・カートから同期シンボルの中心までの（画像距離単位で表される）距離であり、画像の中心（Ｘ１，Ｙ１）から同期シンボルの中心（Ｘｓ，Ｙｓ）までの線の長さである。これは、点（Ｘ１，Ｙ１）、（Ｘｓ，Ｙｓ）および（Ｘ１，Ｙｓ）により定義される直角三角形を用いる基本的な三角法を用いて求めることができる。例えば、距離８０５は、式（Ｙｓ−Ｙ１）／（ｓｉｎ（角度８０３））から計算できる。
【００９８】
図８において、角度８０２および８０４が、それぞれ約６５度、および４５度であることに留意されたい。さらに、本発明の好ましい実施形態において、画像のＸおよびＹ座標の単位が画素であることに留意されたい。
【００９９】
図９は、物理的基準点２２０が図の左下にあり、物理的基準線（店舗壁）２２１が図の底辺に沿う水平線であるように回転された図８である。この回転により、図９におけるバーコードは、店舗内のバーコードの方位と一致するようになる。図９におけるバーコードは、図２におけるバーコード２０６であり、これは、図７の方式に従い、店舗壁２２１を基準として９０度で配向されているのが分かる。
【０１００】
さらに、図９は、「カート／店舗位置」および「カート／店舗方位」がどのように求められるかを説明するために用いられるマーキングを含んでいる。従って、図９において、座標マーキングは、基準点２２０を基準として店舗位置に基づいている。図８と比較すると、同期シンボルの位置点である点（Ｘｓ，Ｙｓ）は、今では点（Ｘｂ，Ｙｂ）であり、「バーコード／店舗位置」である点（Ｘ１，Ｙ１）は、今では「カート／店舗位置」である点（Ｘｖ，Ｙｃ）である。さらに、距離８０５は、今では距離８０５’であり、これは、距離８０５であるが、画像座標系の単位から店舗座標系の単位にスケール変更されている。角度８０２および８０４は、図８のそれらの角度と同じである。なぜならば、これらの角度は、回転において保存されるからである。角度９０２は、「バーコード／店舗方位」であり、角度９０１は、「カート／店舗方位」である。それは、（Ｘｃ，Ｙｃ）および角度９０１の値を求めることが必要である。
【０１０１】
度で表される「カート／店舗方位」（角度９０１）は、「カート／バーコード画像方位」（角度８０２）を「バーコード／店舗方位」（角度９０２）と組み合わせることにより得られる。「バーコード／店舗方位」は、データベースへのインデックスへのバーコードの復号を用いて、またはバーコード中に直接符号化される情報からのどちらか一方で得られる。もしショッピング・カートがバーコードと平行に並べられていれば、角度８０２は、０または１８０度になることに留意されたい。
【０１０２】
従って：
「カート／店舗方位」＝「カート／バーコード画像方位」＋「バーコード／店舗方位」
すなわち
角度９０１＝角度８０２＋角度９０２
【０１０３】
店舗座標系の単位で表される「カート／店舗位置」は、画像単位から店舗座標単位にスケール変更された「バーコード／店舗方位」、「バーコード／店舗位置」、および「カート／バーコード画像極座標」を組み合わせることにより求められる。
【０１０４】
図９の距離８０５（「カート／バーコード画像半径」）は、距離８０５を画像単（例えば、画素）から店舗座標系単位（例えば、メートル）に変換することにより図９の距離８０５’にスケール変更される。従って、距離８０５’は、「カート／バーコード店舗半径」と呼ばれる。例えば、もし同期シンボルの長さが両方の単位集合において知られていれば、換算係数がそれらから求められるであろう。この場合、同期シンボルの長さは、バーコード物理的位置データと共にデータベースに格納され、画素単位で表される同期シンボルの長さは、画像から求められる。代わりに、両方の単位集合において既知または求めることができるバーコードのどのような側面の長さ、例えば、セグメントまたはバーコード全体の長さも、用いることができる。
【０１０５】
「バーコード／店舗位置」（Ｘｂ．Ｙｂ）から「カート／店舗位置」（Ｘｃ，Ｙｃ）への相対移動は今では分かっているが、極座標（「バーコード／店舗極座標」）においてである。極座標（角度，半径）は、角度９０３（「カート／店舗角度」）および距離８０５’（「カート／バーコード店舗半径」）を含み、角度９０３は、角度８０４（「カート／バーコード画像角度」）＋角度９０２（「バーコード／店舗方位」）である。しかしながら、店舗系におけるｘおよびｙ座標においては、移動は（（Ｘｃ−Ｘｂ），（Ｙｃ−Ｙｂ））として表現され得る。
【０１０６】
極座標をｘおよびｙ座標に変換するために、以下の式を用いることができる：
Ｘ＝ｒ ｃｏｓ（ｈ）
Ｙ＝ｒ ｓｉｎ（ｈ）
式中、ｈは、極座標の角度、ｒは、極座標の半径である。
【０１０７】
従って、「バーコード／店舗位置」から「カート／店舗位置」（Ｘｃ，Ｙｃ）への移動の場合、これらの式は、Ｘを（Ｘｃ−Ｘｂ）とし、Ｙを（Ｙｃ−Ｙｂ）とし、ｒを距離８０５’（「カート／バーコード店舗半径」）とし、ｈを角度９０３（「カート／店舗角度」）として、以下のように書き直すことができる：
（Ｘｃ−Ｘｂ）＝距離８０５’×ｃｏｓ（角度９０３）
（Ｙｃ−Ｙｂ）＝距離８０５’×ｓｉｎ（角度９０３）
従って、「カート／店舗位置」座標（Ｘｃ，Ｙｃ）は、以下から求めることができる：
Ｘｃ＝Ｘｂ＋距離８０５’×ｃｏｓ（角度９０３）
Ｙｃ＝Ｙｂ＋距離８０５’×ｓｉｎ（角度９０３）
式中、（Ｘｂ，Ｙｂ）は、「バーコード／店舗位置」であり、角度９０３は、角度８０４（「カート／バーコード画像角度」）＋角度９０２（「バーコード／店舗方位」）である。
【０１０８】
従って、図４の画像がそこから撮られたショッピング・カートの「カート／店舗位置」（Ｘｃ，Ｙｃ）および「カート／店舗方位」（角度９０１）が求められた。
【０１０９】
バーコードの各区間およびバーコードの全長のサイズは、用途に応じて変わり得ることに留意されたい。例えば、サイズは、画像が撮られた時のバーコードからのカメラの予想される距離、用いられたカメラの解像度、および画像を解釈してバーコードの読み取りの位置を特定するために用いられたソフトウェアの能力に従って求めることができる。例えば、カメラを床から４フィート（１２１．９２ｃｍ）上方で保持する典型的なショッピング・カート、８〜１２フィート（２４３．８４〜３６５．７６ｃｍ）のカメラからバーコードまでの距離（店舗天井高さに関連する）、および６４０×４８０画素カメラの画像（ＶＧＡ形式）の使用に基づき、３／４インチ（１．９０５ｃｍ）×３／４インチ（１．９０５ｃｍ）の区間細部が良好に機能することが分かっている。さらに、このサイズは、吊天井と共に用いられる典型的な金属枠と共存できる。より高い天井は、ＩＲ照明器（図３の３０２）輝度を増大させることにより、または逆反射性区間（図１の１０１）のサイズを増大させることにより、またはカメラの解像度を増大させることにより、あるいはそれらの組み合わせることにより、対応できる。
【０１１０】
図１０のａ、ｂおよびｃは、本発明の好ましい実施形態への拡張において用い得る画像の例示である。これは、例えば、光干渉が問題となる状況において有用な逆反射性バーコード・ターゲットの画像における光干渉を低減するためにいくつかの画像を用いることを伴う。図１０のａは、逆反射性ターゲットを照明するために用いられる赤外光なしで撮られた第１の画像を示しており、結果として画像は背景光データしか含んでいない。この例は、画像右下隅の蛍光１１０１を示すことを意図している。次に図１０のｂは、同じ位置からの画像を示しているが、この画像は、赤外光を当てて撮られたものであり、結果として、この画像は、背景光および逆反射性バーコード・ターゲットによって反射された赤外光双方を含んでいる。これにより、画像１０のｃを得ることが可能になり、これは、図１０のｂの画像であるが、図１０のaの画像からの背景データが差し引かれている。結果として、図１０のｃの画像は、この例では逆反射性バーコード・ターゲットにより反射された赤外光のみである反射赤外光のみを含んでいる。従って、画像１０のａにおける干渉は除去されている。
【０１１１】
図１１は、２つの逆反射性バーコード・ターゲットを含む画像を例示する。本発明の好ましい実施形態への別の拡張において、そのような画像は、新たに設置された、または最近変更されたバーコード配列を較正するために用いられる。もし第１のバーコード１１０１の位置（ＸおよびＹ座標）が知られていれば、第２のバーコード１１０２の位置は、第１および第２のバーコードの間のＹおよびＹ画素の数を測定し、画素長さに換算係数（例えば、画素あたりのインチ）をかけることによって求めることができる。従って、もしバーコードの店舗内の位置が知られていれば、そのバーコードの画像に含まれ得るどのようなバーコードの位置も求めることができるであろう。このプロセスは、位置が求められたどのようなバーコードについても繰り返すことができ、結果として、もし店舗全体にわたってバーコードが適切に配置されれば、少なくとも１つのバーコードの位置が知られているのであれば、すべてのバーコードの位置を求めることができる。例えば、図３に関連して、もしバーコード２０３の位置が知られており、バーコード２０３および２０５を含む画像が撮られれば、バーコード２０５の位置を求めることができる。次に、バーコード２０５および２０６を含む画像が撮られれば、バーコード２０６の位置を求めることができる。このプロセスは、バーコード２０４の位置を求めるために繰り返すことができ、さらに大型店舗において、店舗内のすべてのバーコードの位置を求めるために用いることができるであろう。もしあるバーコードが、位置が知られたバーコードと共に画像中に同時に表示されなければ、イメージャ（光を含む）により取り込まれる他のオブジェクトは、中間地点（waypoint）として用いることができ、すなわち、位置が知られているバーコードへの中間地点のＸおよびＹ距離が測定され、位置が知られていないバーコードへの中間地点のＸおよびＹ距離に加えられる。
【０１１２】
さらに、図７に関連して、本発明の好ましい実施形態への別の拡張において、画像は、システムの較正をチェックするために用いられる。例えば、もし両方の逆反射性バーコードの位置が知られていれば、逆反射性バーコードの一方は、他方の位置を求めるために用いられ得る。求められた位置は、求められた位置が正確であるかどうかを調べるために他の逆反射性バーコードの知られている位置と比較することができる。
【０１１３】
本発明の好ましい実施形態に対し、本発明を逸脱することなく多くの変更が可能であることを当業者は理解するであろうことに留意されたい。
【０１１４】
例えば、バーコード・ターゲットは、ターゲットを識別するためおよびターゲットの方位を求めるため双方に用い得る可読データを符号化する任意の形状をとることができる。これは伸長形状を必要とせず、例えば、円形のターゲットも、もしそれが、視野方向がそこから求めることができる識別可能な方位を有するのであれば、用いることができるであろう。
【０１１５】
さらに、例えば、バーコードは、他の手段、例えば、接着剤、ベルクロ・パッド、留め具等を用いて店舗の天井に取り付けることができるであろう。
【０１１６】
さらに、いくつかの用途においてバーコード・ターゲットを識別および符号化することが可能であれば、逆反射性および非逆反射性区間の使用が必要とされないことがあり、代わりに、異なる色を用いることができる。例えば、これは、画像が撮られる時の光条件、用いられるカメラの解像度、またはオブジェクトを区別するために用いられるソフトウェアの能力、あるいはそれらの組み合わせのようなものに依存する。
【０１１７】
別の実施形態において、図３のシステム３００を、例えば、既知の固定位置に取り付け、逆反射性バーコード・ターゲットをショッピング・カートまたは他のモバイル機器に取り付けることができるであろう。撮られたバーコード・ターゲットの画像に基づき、カート／モバイル機器の位置を求めることが可能であろう。さらに、例えば、システム３００の構成要素は変わることができ、事実、画像の取り込みおよび解析ができるどのようなシステムも用いることができるであろう。例えば、カラー・ビデオ・カメラを用いることができる、または代わりに画像をいつ取得するかについてマイクロコントローラにより指示されるデジタル・カメラを用いることができるであろう。もしデジタル・カメラが用いられれば、アナログ比較器３０５およびビデオ同期セパレータ３０６は必要とされず、２値画像への画像の変換は、マイクロプロセッサまたはデジタル・ロジックにより実行され得ることに留意されたい。
【０１１８】
さらに、図５および６に関連して、ステップのいくつかの順序を変更することができ、さらにいくつかのステップをどこか他の場所で処理し得ることに留意されたい。例えば、図５において、ステップ５０５および５０６の順序は逆にされてもよく、さらに、ステップ５０４および５０５は任意である。
【０１１９】
さらに、ショッピング・カートが図６、７および８に関連して説明されたものであれば、位置および方位を求めるために説明された計算に対する多くの代案に当業者が気付くことに留意されたい。
【０１２０】
さらに、本発明の好ましい実施形態は、店舗内のショッピング・カートの位置を求めることについて説明されてきたが、他の実施形態において、画定された領域内の移動可能オブジェクト、例えば、駐車場内の車両の位置を求めるために本発明を用いえることを当業者は理解するであろうことに留意されたい。この方法は、既知の位置に置かれた既存のカメラと共に用い得るであろう。例えば、この方法は、既存の保安用カメラと共に用い得るであろう。
【０１２１】
本発明は、完全にハードウェア的な実施形態、完全にソフトウェア的な実施形態またはハードウェア要素およびソフトウェア要素双方を含む実施形態の形をとり得る。好ましい実施形態において、本発明は、ソフトウェアに実装され、このソフトウェアは、ファームウェア、常駐ソフトウェア、マイクロコード等を含むが、これらに限定されない
【０１２２】
さらに、本発明は、コンピュータまたは任意のような命令実行システムによりまたはこれらと共に使用するためのプログラム・コードを提供するコンピュータ使用可能またコンピュータ可読媒体からアクセス可能なコンピュータ・プログラム製品の形をとり得る。この説明の目的のため、コンピュータ使用可能またはコンピュータ可読媒体は、命令実行システム、装置、または機器により、またはこれらと共に使用するためのプログラムを収容、格納、通信、伝播、または移送することができる任意の装置であり得る。
【０１２３】
媒体は、電子、磁気、光学、電磁、赤外線、または半導体システム（または装置もしくは機器）あるいは伝播媒体であり得る。コンピュータ可読媒体の例としては、半導体またはソリッド・ステート・メモリ、磁気テープ、取り外し可能なコンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリー・メモリ（ＲＯＭ）、李ジッド磁気ディスクおよび光ディスクが含まれる。光ディスクの現行の例としては、コンパクト・ディスク−リード・オンリー・メモリ（ＣＤ−ＲＯＭ）、コンパクト・ディスク−読み取り／書き込み（ＣＤ−Ｒ／Ｗ）およびＤＶＤが含まれる。
【０１２４】
プログラム・コードの格納または実行あるいはその両方に適するデータ処理システムは、システム・バスを介してメモリ素子に直接的または間接的に結合された少なくとも１つのプロセッサを含む。メモリ素子は、プログラム・コードの実際の実行の間使用されるローカル・メモリ、バルク・ストレージ、および実行の間にバルク・ストレージからコードが取り出されなければならない回数を減らすために少なくともいくらかのコードの一時的な格納を提供するキャッシュ・メモリを含み得る。
【０１２５】
入力／出力すなわちＩ／Ｏ機器（キーボード、表示装置、ポインティング・デバイス等を含むが、これらに限定されない）は、直接的にまたは介在Ｉ／Ｏコントローラを介して間接的に、のいずれか一方でシステムに結合され得る。
【０１２６】
ネットワーク・アダプタも、データ処理システムが他のデータ処理システムまたはリモート・プリンタもしくはストレージ・デバイスに、介在する私的または公的ネットワークを介して結合され得るように、システムに結合され得る。モデム、ケーブ・ルモデムおよびイーサネット・カードは、ネットワーク・アダプタの現在利用可能なほんの一握りのタイプである。
【０１２７】
要約すれば、本発明は、例えば、モバイル機器の位置を得るための方法、装置、およびコンピュータ・プログラムを提供する。画定された空間中のターゲットの画像が得られ、ターゲットは、画定された空間中のその位置を求めることができるデータを符号化する。例えば、モバイル機器の位置を表す画像中の基準点の位置は、ターゲットを基準として求められる。次に、画定された空間中のモバイル機器の位置は、画定された空間中のターゲットの位置を、画像中のターゲットへの基準点の相対位置の適切にスケール変更されたバージョンと組み合わせることにより求められる。
【図面の簡単な説明】
【０１２８】
【図１】図１のａ〜ｄは、本発明の好ましい実施形態によるバーコード逆反射性ターゲットを例示する。
【図２】本発明の好ましい実施形態による、（床から天井を見上げた時に見える）店舗天井の一例を例示する。
【図３】本発明の好ましい実施形態による逆反射性バーコード・ターゲットの画像を取得および解釈するために用いられるシステムの概略図である。
【図４】図４のａおよび４ｂは、本発明の好ましい実施形態に従って、図３のシステムによって撮られる、バーコード逆反射性ターゲットの（床から天井を見上げた時に見える）画像の例である。
【図５】本発明の好ましい実施形態に従って逆反射性バーコード・ターゲットの画像を取得および解釈するために用いられる図３のシステムにより実行される方法のフローチャートである。
【図６】得られた画像を解析するための図５の方法ステップのより詳細な説明である方法のフローチャートである。
【図７】本発明の好ましい実施形態において用いられる方位スキームを例示する（床から天井を見上げた時に見える）図である。
【図８】バーコードの画像を解析するために用いられる計算を説明するために用いられる付加的なマーキングを有する図４の画像である。図８中のすべての距離および座標は、画像単位である。
【図９】回転され、バーコードの画像を解析するために用いられる計算を説明するために用いられる加的なマーキングを付した図８の画像である。図９のすべての距離および座標は、物理単位である。
【図１０】図１０のａ〜ｃは、本発明の好ましい実施形態による図３のシステムにより撮られたさらなる画像の例の例示である。
【図１１】本発明の好ましい実施形態による図３のシステムにより撮られた２つのバーコードを含む画像の例の例示である。
【図１】
2009522563.tif 000003
【図２】
2009522563.tif 000004
【図３】
2009522563.tif 000005
【図４】
2009522563.tif 000006
【図５】
2009522563.tif 000007
【図６】
2009522563.tif 000008
【図７】
2009522563.tif 000009
【図８】
2009522563.tif 000010
【図９】
2009522563.tif 000011
【図１０】
2009522563.tif 000012
【図１１】
2009522563.tif 000013
【国際調査報告】
2009522563.tif 000014
2009522563.tif 000015
2009522563.tif 000016