(57)【要約】      （修正有）【課題】オブジェクトの対応関係を効率的に特定する。【解決手段】動線生成装置１は、所定エリアにおける障害物領域と、障害物領域の位置とを特定する障害物領域特定部１２１と、所定エリアを移動するオブジェクトの第１時刻以前の位置を特定するオブジェクト位置特定部１２２と、第１時刻よりも後の時刻である第２時刻におけるオブジェクトの一以上の候補位置を特定する検出位置特定部１２３と、第１時刻以前のオブジェクトの位置と、一以上の候補位置と、障害物領域の位置との位置関係に基づいて、オブジェクトが一以上の候補位置のそれぞれに移動するときの困難さを示す移動妨害度を特定する移動妨害度特定部１２４と、オブジェクトの第１時刻以前の位置から一以上の候補位置のそれぞれへの移動コストを移動妨害度に基づいて特定し、移動コストが相対的に小さい候補位置を第２時刻における位置に選択する選択部１２５と、を備える。【選択図】図２
2020021171.tif 000002
【特許請求の範囲】
【請求項１】
所定エリアに存在する障害物の形状に対応する障害物領域と、前記障害物領域の前記所定エリアにおける位置とを特定する障害物領域特定部と、
前記所定エリアを移動するオブジェクトの第１時刻以前の位置を特定するオブジェクト位置特定部と、
前記第１時刻よりも後の時刻である第２時刻における前記オブジェクトの一以上の検出位置の候補である候補位置を特定する検出位置特定部と、
特定した前記第１時刻以前の前記オブジェクトの位置と、特定した一以上の前記候補位置と、特定した前記障害物領域の位置との位置関係に基づいて、前記オブジェクトが一以上の前記候補位置のそれぞれに移動するときの困難さを示す移動妨害度を特定する移動妨害度特定部と、
前記オブジェクトの前記第１時刻以前の位置から一以上の前記候補位置のそれぞれへの移動コストを前記移動妨害度に基づいて特定し、前記移動コストが相対的に小さい前記候補位置を、前記オブジェクトの前記第２時刻における位置に選択する選択部と、
を備える位置選択装置。
【請求項２】
前記オブジェクト位置特定部は、前記オブジェクトの前記第１時刻以前の位置に基づいて、前記オブジェクトの前記第２時刻における位置である第１オブジェクト位置を予測し、
前記移動妨害度特定部は、前記第１オブジェクト位置と、特定した一以上の前記候補位置と、特定した前記障害物領域の位置との位置関係に基づいて、前記移動妨害度を特定する、
請求項１に記載の位置選択装置。
【請求項３】
前記オブジェクト位置特定部は、前記オブジェクトの第１時刻における位置を第１オブジェクト位置として特定し、
前記移動妨害度特定部は、前記第１オブジェクト位置と、特定した一以上の前記候補位置と、特定した前記障害物領域の位置との位置関係に基づいて、前記移動妨害度を特定する、
請求項１に記載の位置選択装置。
【請求項４】
前記移動妨害度特定部は、前記第１オブジェクト位置と、特定した一以上の前記候補位置のそれぞれとを結ぶ線分を特定し、当該線分と特定した前記障害物領域との位置関係に基づいて、特定した一以上の前記候補位置のそれぞれに対応する前記移動妨害度を特定する、
請求項２又は３に記載の位置選択装置。
【請求項５】
前記移動妨害度特定部は、特定した一以上の前記線分のそれぞれについて、当該線分と特定した前記障害物領域との２つの交点を特定し、特定した２つの交点と、当該障害物領域との関係に基づいて前記移動妨害度を特定する、
請求項４に記載の位置選択装置。
【請求項６】
前記移動妨害度特定部は、特定した２つの交点により分断される前記障害物領域の２つの輪郭線のうち、相対的に短い輪郭線の長さに基づいて前記移動妨害度を特定する、
請求項５に記載の位置選択装置。
【請求項７】
前記移動妨害度特定部は、特定した一以上の前記線分のそれぞれについて、当該線分と特定した前記障害物領域との交点が３つ以上存在する場合に、３つの交点の中から取り得る２つの交点のうち、相対的に距離が長い２つの交点を特定する、
請求項５又は６に記載の位置選択装置。
【請求項８】
前記移動妨害度特定部は、特定した２つの交点を結ぶ線分の長さに対する、特定した２つの交点により分断される前記障害物領域の輪郭線の長さの比率に基づいて前記移動妨害度を特定する、
請求項５から７のいずれか１項に記載の位置選択装置。
【請求項９】
前記移動妨害度特定部は、特定した２つの交点のそれぞれと、特定した前記障害物領域の基準点と結ぶ二本の線分のなす角度を特定し、当該角度に基づいて前記移動妨害度を特定する、
請求項５から８のいずれか１項に記載の位置選択装置。
【請求項１０】
前記移動妨害度特定部は、特定した前記障害物領域を構成する辺のうち、特定した２つの交点のいずれかが存在する２辺を特定し、当該２辺の間に存在する２つの辺群のうち、相対的に辺の数が少ない辺群に含まれる辺の数に基づいて前記移動妨害度を特定する、
請求項５から９のいずれか１項に記載の位置選択装置。
【請求項１１】
前記移動妨害度特定部は、特定した線分との交点が存在する前記障害物領域が複数存在する場合に、当該複数の障害物領域を１つの障害物領域に近似する、
請求項５から１０のいずれか１項に記載の位置選択装置。
【請求項１２】
前記オブジェクト位置特定部は、前記第１オブジェクト位置が前記障害物領域内に存在する場合に、当該第１オブジェクト位置を前記障害物領域外の位置に修正する、
請求項２から１１のいずれか１項に記載の位置選択装置。
【請求項１３】
前記障害物領域特定部は、前記障害物の形状が非凸形状の場合に、当該障害物に対応する障害物領域を、凸形状の障害物領域に近似する、
請求項１から１２のいずれか１項に記載の位置選択装置。
【請求項１４】
前記障害物領域特定部は、前記障害物領域を複数特定した場合において、特定した複数の障害物領域が隣接又は重複している場合に、当該複数の障害物領域を、当該複数の障害物領域の和領域に近似する、
請求項１から１３のいずれか１項に記載の位置選択装置。
【請求項１５】
前記検出位置特定部は、特定した前記候補位置が前記障害物領域内に存在する場合に、当該候補位置を前記障害物領域外の位置に修正する、
請求項１から１４のいずれか１項に記載の位置選択装置。
【請求項１６】
前記選択部は、特定した前記第１時刻以前の位置に対応するオブジェクトと、特定した一以上の前記候補位置のそれぞれに対応するオブジェクトとの所定の対応関係における類似度を特定し、当該類似度と、特定した前記移動妨害度とに基づいて、前記第１時刻以前の位置から一以上の前記候補位置のそれぞれへの移動コストを特定する、
請求項１から１５のいずれか１項に記載の位置選択装置。
【請求項１７】
前記選択部は、相対的に小さい前記移動コストが第１の閾値を超える場合に、前記候補位置を選択しないように制御する、
請求項１から１６のいずれか１項に記載の位置選択装置。
【請求項１８】
前記選択部は、特定した前記移動妨害度が第２の閾値を超える前記候補位置について、前記移動コストを前記第１の閾値を超える値に設定する、
請求項１７に記載の位置選択装置。
【請求項１９】
前記オブジェクトの前記第１時刻における位置と、前記選択部が選択した前記オブジェクトの前記候補位置とを関連付けることにより、前記オブジェクトの移動動線を生成する動線生成部をさらに備える、
請求項１から１８のいずれか１項に記載の位置選択装置。
【請求項２０】
コンピュータが実行する、
所定エリアに存在する障害物の形状に対応する障害物領域と、前記障害物領域の前記所定エリアにおける位置とを特定するステップと、
前記所定エリアを移動するオブジェクトの第１時刻以前の位置を特定するステップと、
前記第１時刻よりも後の時刻である第２時刻における前記オブジェクトの一以上の検出位置の候補である候補位置を特定するステップと、
特定した前記第１時刻以前の前記オブジェクトの位置と、特定した一以上の前記候補位置と、特定した前記障害物領域の位置との位置関係に基づいて、前記オブジェクトが一以上の前記候補位置のそれぞれに移動するときの困難さを示す移動妨害度を特定するステップと、
前記オブジェクトの前記第１時刻以前の位置から一以上の前記候補位置のそれぞれへの移動コストを前記移動妨害度に基づいて特定し、前記移動コストが相対的に小さい前記候補位置を、前記オブジェクトの前記第２時刻における位置に選択するステップと、
を備える位置選択方法。
【請求項２１】
コンピュータを、
所定エリアに存在する障害物の形状に対応する障害物領域と、前記障害物領域の前記所定エリアにおける位置とを特定する障害物領域特定部、
前記所定エリアを移動するオブジェクトの第１時刻以前の位置を特定するオブジェクト位置特定部、
前記第１時刻よりも後の時刻である第２時刻における前記オブジェクトの一以上の検出位置の候補である候補位置を特定する検出位置特定部、
特定した前記第１時刻以前の前記オブジェクトの位置と、特定した一以上の前記候補位置と、特定した前記障害物領域の位置との位置関係に基づいて、前記オブジェクトが一以上の前記候補位置のそれぞれに移動するときの困難さを示す移動妨害度を特定する移動妨害度特定部、及び、
前記オブジェクトの前記第１時刻以前の位置から一以上の前記候補位置のそれぞれへの移動コストを前記移動妨害度に基づいて特定し、前記移動コストが相対的に小さい前記候補位置を、前記オブジェクトの前記第２時刻における位置に選択する選択部、
として機能させる位置選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オブジェクトの位置を選択する位置選択装置、位置選択方法、及び位置選択プログラムに関する。
【背景技術】
【０００２】
従来、マーケティングや監視等を目的として、店舗内等の所定エリアに滞在する人物等のオブジェクトを追跡することが行われている。所定エリア内に人物の移動を妨げる壁や什器等の障害物が存在する場合、障害物上を移動しない移動動線を生成することが期待される。また、障害物の位置が事前に得られている場合は、オブジェクトを高精度に追跡することが可能となる。
【０００３】
例えば、特許文献１においては、パーティクルフィルタを利用してオブジェクトを追跡する際に、各パーティクルの予測位置が障害物領域上に存在する場合に、オブジェクトの予測位置を障害物領域以外の位置に修正する方式が開示されている。また、特許文献２においては、各パーティクルの予測位置に障害物の高さに応じたペナルティを付与することで、各パーティクルの障害物上の存在確度を低くする方式が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許５６８７０３５号公報
【特許文献２】特許５５５２０６９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来、オブジェクト追跡を実現するには、カルマンフィルタやパーティクルフィルタ等の近似フィルタを用いるのが主流であった。近年、機械学習や深層学習技術（例えば、Support Vector MachineやConvolutional Neural Network）の発展に伴い、所定エリアを撮像した画像からオブジェクトを高精度に追跡する方式として、Tracking-by-Detection方式が注目を浴びている。Tracking-by-Detection方式は、オブジェクト検出器（Detection）を用いて各時刻で撮像した画像中のオブジェクトの位置を検出し、同一オブジェクト判定器（Re-Identification）を用いて各時刻で検出したオブジェクトを対応付けることにより、オブジェクトの追跡（Tracking）を実現する。
【０００６】
図１５は、障害物領域が存在する所定エリア内でTracking-by-Detection方式によりオブジェクトを追跡する場合の例を示す図である。ここで、障害物領域の位置は事前に既知であるものとする。
【０００７】
時刻ｔ−１までのオブジェクトの追跡結果は、時刻ｔ−１以前の時刻、例えば、時刻ｔ−４、時刻ｔ−３、時刻ｔ−２におけるオブジェクトの検出結果を時刻ｔ−１におけるオブジェクトの検出結果に対応付けることで生成される。当該オブジェクトを時刻ｔまで追跡する場合、時刻ｔ−１までの追跡結果を、時刻ｔにおける検出結果、すなわち検出結果Ａ及び検出結果Ｂのいずれかに対応付ける問題を解くこととなる。
【０００８】
このとき、当該追跡結果に含まれる時刻ｔ−１におけるオブジェクト位置と、時刻ｔにおける検出結果Ａ及び検出結果Ｂのオブジェクト位置とを結ぶ線分上には、いずれも障害物領域が存在する。しかしながら、オブジェクトの位置と障害物領域との位置関係上、当該オブジェクトは、時刻ｔにおいて検出結果Ａとして検出されている可能性が高く、当該オブジェクトの追跡結果を検出結果Ｂよりも検出結果Ａに優先的に対応付けることが望ましい。すなわち、追跡結果と検出結果とを時系列上で単に対応付けるだけのTracking-by-Detection方式では、その途中に存在する障害物領域を考慮していないために、追跡結果と検出結果との対応関係を正しく特定することができないという課題がある。
【０００９】
これに対して、最短経路を探索する方式としてＡ＊（エースター）アルゴリズムが知られている。図１５中で、追跡結果に含まれる時刻ｔ−１におけるオブジェクト位置を開始点、時刻ｔにおけるオブジェクト位置（検出結果Ａ、Ｂのそれぞれ）を終点として、Ａ＊アルゴリズムを適用することで、開始点から障害物を回避して終点に到達する迂回路（最短経路）を特定することができる。したがって、時刻ｔ−１におけるオブジェクト位置と、時刻ｔにおける検出結果Ａ及び検出結果Ｂのオブジェクト位置との対応関係を特定する際のコスト値として当該迂回路の経路上の長さを用いることで、当該オブジェクトの追跡結果を検出結果Ｂよりも検出結果Ａに優先的に対応付けることが可能となる。
【００１０】
しかしながら、Ａ＊アルゴリズムは計算量が多いという課題がある。特に、Tracking-by-Detection方式において、複数のオブジェクトを同時に追跡する場合、対応関係を特定するにあたり、（時刻ｔ−１までに追跡中のオブジェクトの数）×（時刻ｔで検出したオブジェクトの数）の分だけＡ＊アルゴリズムを適用する必要があり、計算量が膨大になるという課題がある。
【００１１】
そこで、本発明はこれらの点に鑑みてなされたものであり、オブジェクトの対応関係を効率的に特定することができる位置選択装置、位置選択方法、及び位置選択プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の第１の態様に係る位置選択装置は、所定エリアに存在する障害物の形状に対応する障害物領域と、前記障害物領域の前記所定エリアにおける位置とを特定する障害物領域特定部と、前記所定エリアを移動するオブジェクトの第１時刻以前の位置を特定するオブジェクト位置特定部と、前記第１時刻よりも後の時刻である第２時刻における前記オブジェクトの一以上の検出位置の候補である候補位置を特定する検出位置特定部と、特定した前記第１時刻以前の前記オブジェクトの位置と、特定した一以上の前記候補位置と、特定した前記障害物領域の位置との位置関係に基づいて、前記オブジェクトが一以上の前記候補位置のそれぞれに移動するときの困難さを示す移動妨害度を特定する移動妨害度特定部と、前記オブジェクトの前記第１時刻以前の位置から一以上の前記候補位置のそれぞれへの移動コストを前記移動妨害度に基づいて特定し、前記移動コストが相対的に小さい前記候補位置を、前記オブジェクトの前記第２時刻における位置に選択する選択部と、を備える。
【００１３】
前記オブジェクト位置特定部は、前記オブジェクトの前記第１時刻以前の位置に基づいて、前記オブジェクトの前記第２時刻における位置である第１オブジェクト位置を予測し、前記移動妨害度特定部は、前記第１オブジェクト位置と、特定した一以上の前記候補位置と、特定した前記障害物領域の位置との位置関係に基づいて、前記移動妨害度を特定してもよい。
【００１４】
前記オブジェクト位置特定部は、前記オブジェクトの第１時刻における位置を第１オブジェクト位置として特定し、前記移動妨害度特定部は、前記第１オブジェクト位置と、特定した一以上の前記候補位置と、特定した前記障害物領域の位置との位置関係に基づいて、前記移動妨害度を特定してもよい。
【００１５】
前記移動妨害度特定部は、前記第１オブジェクト位置と、特定した一以上の前記候補位置のそれぞれとを結ぶ線分を特定し、当該線分と特定した前記障害物領域との位置関係に基づいて、特定した一以上の前記候補位置のそれぞれに対応する前記移動妨害度を特定してもよい。
【００１６】
前記移動妨害度特定部は、特定した一以上の前記線分のそれぞれについて、当該線分と特定した前記障害物領域との２つの交点を特定し、特定した２つの交点と、当該障害物領域との関係に基づいて前記移動妨害度を特定してもよい。
【００１７】
前記移動妨害度特定部は、特定した２つの交点により分断される前記障害物領域の２つの輪郭線のうち、相対的に短い輪郭線の長さに基づいて前記移動妨害度を特定してもよい。
前記移動妨害度特定部は、特定した一以上の前記線分のそれぞれについて、当該線分と特定した前記障害物領域との交点が３つ以上存在する場合に、３つの交点の中から取り得る２つの交点のうち、相対的に距離が長い２つの交点を特定してもよい。
【００１８】
前記移動妨害度特定部は、特定した２つの交点を結ぶ線分の長さに対する、特定した２つの交点により分断される前記障害物領域の輪郭線の長さの比率に基づいて前記移動妨害度を特定してもよい。
前記移動妨害度特定部は、特定した２つの交点のそれぞれと、特定した前記障害物領域の基準点と結ぶ二本の線分のなす角度を特定し、当該角度に基づいて前記移動妨害度を特定してもよい。
【００１９】
前記移動妨害度特定部は、特定した前記障害物領域を構成する辺のうち、特定した２つの交点のいずれかが存在する２辺を特定し、当該２辺の間に存在する２つの辺群のうち、相対的に辺の数が少ない辺群に含まれる辺の数に基づいて前記移動妨害度を特定してもよい。
前記移動妨害度特定部は、特定した線分との交点が存在する前記障害物領域が複数存在する場合に、当該複数の障害物領域を１つの障害物領域に近似してもよい。
【００２０】
前記オブジェクト位置特定部は、前記第１オブジェクト位置が前記障害物領域内に存在する場合に、当該第１オブジェクト位置を前記障害物領域外の位置に修正してもよい。
前記障害物領域特定部は、前記障害物の形状が非凸形状の場合に、当該障害物に対応する障害物領域を、凸形状の障害物領域に近似してもよい。
前記障害物領域特定部は、前記障害物領域を複数特定した場合において、特定した複数の障害物領域が隣接又は重複している場合に、当該複数の障害物領域を、当該複数の障害物領域の和領域に近似してもよい。
前記検出位置特定部は、特定した前記候補位置が前記障害物領域内に存在する場合に、当該候補位置を前記障害物領域外の位置に修正してもよい。
【００２１】
前記選択部は、特定した前記第１時刻以前の位置に対応するオブジェクトと、特定した一以上の前記候補位置のそれぞれに対応するオブジェクトとの所定の対応関係における類似度を特定し、当該類似度と、特定した前記移動妨害度とに基づいて、前記第１時刻以前の位置から一以上の前記候補位置のそれぞれへの移動コストを特定してもよい。
【００２２】
前記選択部は、相対的に小さい前記移動コストが第１の閾値を超える場合に、前記候補位置を選択しないように制御してもよい。
前記選択部は、特定した前記移動妨害度が第２の閾値を超える前記候補位置について、前記移動コストを前記第１の閾値を超える値に設定してもよい。
【００２３】
前記位置選択装置は、前記オブジェクトの前記第１時刻における位置と、前記選択部が選択した前記オブジェクトの前記候補位置とを関連付けることにより、前記オブジェクトの移動動線を生成する動線生成部をさらに備えてもよい。
【００２４】
本発明の第２の態様に係る位置選択方法は、コンピュータが実行する、所定エリアに存在する障害物の形状に対応する障害物領域と、前記障害物領域の前記所定エリアにおける位置とを特定するステップと、前記所定エリアを移動するオブジェクトの第１時刻以前の位置を特定するステップと、前記第１時刻よりも後の時刻である第２時刻における前記オブジェクトの一以上の検出位置の候補である候補位置を特定するステップと、特定した前記第１時刻以前の前記オブジェクトの位置と、特定した一以上の前記候補位置と、特定した前記障害物領域の位置との位置関係に基づいて、前記オブジェクトが一以上の前記候補位置のそれぞれに移動するときの困難さを示す移動妨害度を特定するステップと、前記オブジェクトの前記第１時刻以前の位置から一以上の前記候補位置のそれぞれへの移動コストを前記移動妨害度に基づいて特定し、前記移動コストが相対的に小さい前記候補位置を、前記オブジェクトの前記第２時刻における位置に選択するステップと、を備える。
【００２５】
本発明の第３の態様に係る位置選択プログラムは、コンピュータを、所定エリアに存在する障害物の形状に対応する障害物領域と、前記障害物領域の前記所定エリアにおける位置とを特定する障害物領域特定部、前記所定エリアを移動するオブジェクトの第１時刻以前の位置を特定するオブジェクト位置特定部、前記第１時刻よりも後の時刻である第２時刻における前記オブジェクトの一以上の検出位置の候補である候補位置を特定する検出位置特定部、特定した前記第１時刻以前の前記オブジェクトの位置と、特定した一以上の前記候補位置と、特定した前記障害物領域の位置との位置関係に基づいて、前記オブジェクトが一以上の前記候補位置のそれぞれに移動するときの困難さを示す移動妨害度を特定する移動妨害度特定部、及び、前記オブジェクトの前記第１時刻以前の位置から一以上の前記候補位置のそれぞれへの移動コストを前記移動妨害度に基づいて特定し、前記移動コストが相対的に小さい前記候補位置を、前記オブジェクトの前記第２時刻における位置に選択する選択部、として機能させる。
【発明の効果】
【００２６】
本発明によれば、オブジェクトの対応関係を効率的に特定することができるという効果を奏する。
【図面の簡単な説明】
【００２７】
【図１】本実施形態に係る動線生成装置の概要を説明する図である。
【図２】本実施形態に係る動線生成装置の構成を示す図である。
【図３】第１時刻におけるオブジェクトの位置及び候補位置が特定された例を示す図である。
【図４】第１オブジェクト位置と、一以上の候補位置のそれぞれとを結ぶ線分が特定された例を示す図である。
【図５】第１オブジェクト位置と候補位置とを結ぶ線分と、矩形として特定された障害物領域との交点が特定された例を示す図である。
【図６】特定した２点の交点により分断される障害物領域の２つの輪郭線の例を示す図である。
【図７】２つの交点を結ぶ線分の長さに対する輪郭線の長さの比率を算出する例を示す図である。
【図８】特定した２つの交点のそれぞれと、特定した障害物領域の基準点と結ぶ二本の線分のなす角度を特定する例を示す図である。
【図９】辺の数に基づいて移動妨害度を特定する例を示す図である。
【図１０】複数の障害物領域を１つの障害物領域に近似する例を示す図である。
【図１１】第１時刻以前のオブジェクトの位置と、候補位置との対応関係を特定した例を示す図である。
【図１２】２つの交点を結ぶ線分の長さに対する輪郭線の長さの比率に基づいて移動妨害度を算出する例を示す図である。
【図１３】第２時刻に対応する確定位置を特定した例を示す図である。
【図１４】本実施形態に係る動線生成装置における処理の流れを示すフローチャートである。
【図１５】障害物領域が存在する所定エリア内でTracking-by-Detection方式によりオブジェクトを追跡する場合の例を示す図である。
【発明を実施するための形態】
【００２８】
［動線生成装置１の概要］
図１は、本実施形態に係る動線生成装置１の概要を説明する図である。動線生成装置１は、所定エリアを移動するオブジェクトの各時刻における位置を示す動線情報を生成するコンピュータであり、オブジェクトの候補位置から、オブジェクトの位置を選択する位置選択装置として機能する。
【００２９】
ここで、所定エリアは、例えば店舗のフロアである。所定エリアには、動きを分析する対象の所定のオブジェクトとして、店員等の人物が存在する。なお、以下の説明では、所定のオブジェクトを単にオブジェクトという。
【００３０】
動線生成装置１は、所定エリアに存在する障害物の形状に対応する障害物領域と、障害物領域の所定エリアにおける位置とを特定する。動線生成装置１は、所定エリアを移動するオブジェクトの第１時刻以前の位置を特定し、第１時刻よりも後の時刻である第２時刻におけるオブジェクトの一以上の検出位置の候補である候補位置を特定する。図１では、動線生成装置１が、２つの候補位置Ｐ２Ａ及びＰ２Ｂを特定した例が示されている。
【００３１】
動線生成装置１は、特定した第１時刻以前のオブジェクトの位置と、特定した一以上の候補位置と、特定した障害物領域の位置との位置関係に基づいて、オブジェクトが第１時刻以前における位置から一以上の候補位置のそれぞれに移動するときの困難さを示す移動妨害度を特定する。図１に示す例では、動線生成装置１は、候補位置Ｐ２Ａの移動妨害度を、候補位置Ｐ２Ｂの移動妨害度よりも低いものと特定する。
【００３２】
そして、動線生成装置１は、第１時刻における位置から一以上の候補位置のそれぞれへの移動コストを移動妨害度に基づいて特定し、移動コストが相対的に小さい候補位置を、オブジェクトの第２時刻における位置に選択する。図１に示す例では、動線生成装置１は、候補位置Ｐ２Ａへの移動コストを、候補位置Ｐ２Ｂへの移動コストよりも低く特定し、候補位置Ｐ２Ａを、オブジェクトの第２時刻における位置として選択する。このようにすることで、動線生成装置１は、Ａ＊等の追跡アルゴリズムを使用して第１時刻における位置から複数の候補位置のそれぞれへの最短経路を特定する場合に比べて効率的に候補位置を選択することができる。
【００３３】
［動線生成装置１の構成］
続いて、動線生成装置１の構成を説明する。図２は、本実施形態に係る動線生成装置１の構成を示す図である。図２に示すように、動線生成装置１は、記憶部１１と、制御部１２とを備える。
【００３４】
記憶部１１は、ＲＯＭ（Read Only Memory）及びＲＡＭ（Random Access Memory）等を含む記憶媒体である。記憶部１１は、制御部１２が実行するプログラムを記憶している。例えば、記憶部１１は、動線生成装置１を、障害物領域特定部１２１、オブジェクト位置特定部１２２、検出位置特定部１２３、移動妨害度特定部１２４、選択部１２５、及び動線生成部１２６として機能させる、位置選択プログラムとしての動線生成プログラムを記憶している。
【００３５】
制御部１２は、例えばＣＰＵ（Central Processing Unit）である。制御部１２は、記憶部１１に記憶された動線生成プログラムを実行することにより、障害物領域特定部１２１、オブジェクト位置特定部１２２、検出位置特定部１２３、移動妨害度特定部１２４、選択部１２５、及び動線生成部１２６として機能する。
【００３６】
障害物領域特定部１２１は、所定エリアに存在する障害物の形状に対応する障害物領域と、障害物領域の所定エリアにおける位置とを特定する。例えば、記憶部１１には、障害物領域の形状及び障害物領域の所定エリアにおける位置を示す障害物領域情報が一以上記憶されている。障害物領域情報は、例えば、障害物領域の形状を示す多角形の各頂点の、所定エリアにおける位置（グローバル位置）を示す情報である。多角形領域が矩形の場合には、障害物領域情報は、矩形領域の中央位置を示す位置座標と、横幅及び縦幅とを示す情報であってもよい。障害物領域特定部１２１は、障害物領域情報を参照することにより、障害物領域と、障害物領域の所定エリアにおける位置とを特定する。
【００３７】
障害物領域特定部１２１は、特定した障害物の形状が非凸形状の場合に、当該障害物に対応する障害物領域を、凸形状の障害物領域に近似してもよい。また、障害物領域特定部１２１は、障害物領域を複数特定した場合において、特定した複数の障害物領域が隣接又は重複している場合に、当該複数の障害物領域を、当該複数の障害物領域の和領域に近似してもよい。ここで、障害物領域特定部１２１は、壁も障害物として特定してもよい。そして、壁とその他の障害物とが接している場合、障害物領域特定部１２１は、これらの障害物領域を、これらの障害物領域の和領域である１つの障害物領域に近似してもよい。このようにすることで、動線生成装置１は、障害物領域の形状を単純化することができ、処理負荷を軽減できる。
【００３８】
オブジェクト位置特定部１２２は、所定エリアを移動するオブジェクトの第１時刻以前の位置を特定する。例えば、記憶部１１には、所定エリアを移動するオブジェクトの各時刻における位置を示す動線情報が一以上記憶されている。動線情報は、時刻と、当該時刻におけるオブジェクトの所定エリアにおける位置を示す位置情報とを関連付けた時系列情報である。位置情報は、例えば、メートルやセンチメートルを単位とした２次元座標である。
【００３９】
なお、動線情報に含まれる位置情報は、所定エリアの位置を示すグローバル位置を特定することが可能な情報であってもよく、例えば、所定エリアを撮像した撮像画像における位置を示すローカル位置情報と、当該位置をグローバル位置に変換するための変換用情報とを含むものであってもよい。ローカル位置情報は、例えば、ピクセルを単位としたオブジェクトの位置を示す２次元座標と、オブジェクトの幅及び高さとから構成される矩形情報である。
【００４０】
オブジェクト位置特定部１２２は、第１時刻までの位置情報を含む一以上の動線情報を特定し、当該動線情報において第１時刻に関連付けられている位置情報を特定することにより、一以上のオブジェクトの第１時刻における位置を特定する。なお、オブジェクト位置特定部１２２は、第１時刻を含まず、第１時刻よりも前の時刻に対応する位置情報のみを含む動線情報を特定してもよい。そして、オブジェクト位置特定部１２２は、特定した動線情報において最も新しい時刻に関連付けられている位置情報を特定することにより、オブジェクトの第１時刻以前の位置を特定してもよい。
【００４１】
また、オブジェクト位置特定部１２２は、所定エリアを撮像する撮像装置が第１時刻に撮像した撮像画像に基づいて、第１時刻におけるオブジェクトの位置を特定してもよい。この場合、オブジェクト位置特定部１２２は、撮像画像に基づいてオブジェクトの位置を検出するオブジェクト検出装置に、第１時刻に撮像された撮像画像を入力する。そして、オブジェクト位置特定部１２２は、オブジェクト検出装置から、第１時刻に撮像された撮像画像に写る一以上のオブジェクトの位置を示す位置情報を取得し、取得した位置情報が示す位置を、第１時刻におけるオブジェクトの位置として特定する。ここで、オブジェクト検出装置は、機械学習や深層学習を用いたものであってもよい。また、オブジェクト検出装置は、赤外線を利用した３Ｄセンサ等を用いたものであってもよい。
【００４２】
検出位置特定部１２３は、第１時刻よりも後の時刻である第２時刻におけるオブジェクトの一以上の検出位置の候補である候補位置を特定する。例えば、検出位置特定部１２３は、オブジェクト検出装置に、第２時刻に撮像された撮像画像を入力する。そして、検出位置特定部１２３は、オブジェクト検出装置から、第２時刻に撮像された撮像画像に写る一以上のオブジェクトの位置を示す位置情報を取得することにより、一以上の候補位置を特定する。
【００４３】
検出位置特定部１２３は、特定した候補位置が障害物領域内に存在する場合に、当該候補位置を障害物領域外の位置に修正してもよい。例えば、検出位置特定部１２３は、特定した候補位置が障害物領域内に存在する場合に、障害物領域の輪郭を示す複数の位置のうち、当該候補位置に最も近い位置を、修正後の候補位置とする。なお、動線生成装置１は、オブジェクト検出装置が、オブジェクトの位置として障害物領域の内部の位置を検出しないようにオブジェクト検出装置を制御するようにしてもよい。
【００４４】
図３は、第１時刻以前のオブジェクトの位置及び候補位置が特定された例を示す図である。図３に示す例では、動線Ｔ１に対応する最新のオブジェクト位置Ｐ１Ａと、動線Ｔ２に対応する最新のオブジェクト位置Ｐ１Ｂとが特定され、候補位置Ｐ２Ａ、Ｐ２Ｂ及びＰ２Ｃが特定されていることが確認できる。動線Ｔ１に対応する最新のオブジェクト位置Ｐ１Ａは、第１時刻におけるオブジェクトの位置であり、動線Ｔ２に対応する最新のオブジェクト位置Ｐ１Ｂは、第１時刻以前の時刻におけるオブジェクトの位置である。
【００４５】
移動妨害度特定部１２４は、オブジェクト位置特定部１２２が特定した第１時刻以前のオブジェクトの位置と、検出位置特定部１２３が特定した一以上の候補位置と、障害物領域特定部１２１が特定した障害物領域の位置との位置関係に基づいて、オブジェクトが一以上の候補位置のそれぞれに移動するときの困難さを示す移動妨害度を特定する。
【００４６】
まず、オブジェクト位置特定部１２２は、特定した動線情報が示すオブジェクトの第１時刻以前の位置に基づいて、当該オブジェクトの第２時刻における位置である第１オブジェクト位置を予測する。例えば、オブジェクト位置特定部１２２は、カルマンフィルタやパーティクルフィルタ等の近似フィルタを用いて第１オブジェクト位置を予測する。
【００４７】
そして、移動妨害度特定部１２４は、第１オブジェクト位置と、特定した一以上の候補位置と、特定した障害物領域の位置との位置関係に基づいて移動妨害度を特定する。具体的には、移動妨害度特定部１２４は、特定した第１オブジェクト位置と、特定した一以上の候補位置のそれぞれとを結ぶ線分を特定し、当該線分と特定した障害物領域との位置関係に基づいて、オブジェクトが第１オブジェクト位置から、特定した一以上の候補位置のそれぞれに移動するときの移動妨害度を特定する。
【００４８】
なお、オブジェクト位置特定部１２２は、第１オブジェクト位置を、第１時刻以前の位置に基づいて予測された第２時刻におけるオブジェクトの位置であることとしたが、これに限らない。例えば、オブジェクト位置特定部１２２は、オブジェクトの第１時刻における位置を第１オブジェクト位置として特定してもよい。そして、移動妨害度特定部１２４は、オブジェクト位置特定部１２２が特定した第１オブジェクト位置と、特定した一以上の候補位置と、特定した障害物領域の位置との位置関係に基づいて移動妨害度を特定してもよい。このようにすることで、動線生成装置１は、第２時刻におけるオブジェクトの位置を予測することなく、第２時刻におけるオブジェクトの位置を特定することができる。
【００４９】
また、オブジェクト位置特定部１２２は、特定した第１オブジェクト位置が障害物領域内に存在する場合に、当該第１オブジェクト位置を障害物領域外の位置に修正してもよい。このようにすることで、動線生成装置１は、第１オブジェクトの位置が障害物領域内に存在することにより移動妨害度の特定精度が落ちることを防止することができる。
【００５０】
図４は、第１オブジェクト位置と、一以上の候補位置のそれぞれとを結ぶ線分が特定された例を示す図である。図４では、動線Ｔ１及び動線Ｔ２のそれぞれに対して、第２時刻に対応する第１オブジェクト位置ＰＰＡ及びＰＰＢが特定され、これらの第１オブジェクト位置から、一以上の候補位置Ｐ２Ａ、Ｐ２Ｂ及びＰ２Ｃに対する６本の線分が特定されていることが確認できる。
【００５１】
以下、移動妨害度特定部１２４による移動妨害度の特定方法を複数説明する。移動妨害度特定部１２４は、一以上の特定方法の少なくともいずれかに基づいて、一以上の第１オブジェクト位置のそれぞれから、一以上の候補位置のそれぞれに移動するときの移動妨害度を特定する。例えば、移動妨害度特定部１２４は、複数の特定方法の少なくともいずれかを組み合わせることにより、１つの第１オブジェクト位置から１つの候補位置に移動するときに対応する１つの移動妨害度を特定してもよい。移動妨害度特定部１２４は、１つの第１オブジェクト位置から１つの候補位置に移動するときに対応する１つの移動妨害度を特定する場合に、複数の特定方法のそれぞれに従って複数の移動妨害度を特定し、各々の処理方法により特定した複数の移動妨害度の積や重み付き和等を用いて、１つの移動妨害度を特定してもよい。
【００５２】
移動妨害度特定部１２４は、特定した一以上の線分のそれぞれについて、当該線分と、特定された障害物領域との２つの交点を特定する。図５は、第１オブジェクト位置と候補位置とを結ぶ線分と、矩形として特定された障害物領域との交点が特定された例を示す図である。図５に示すように、第１オブジェクト位置ＰＰＡと候補位置Ｐ２Ａ及びＰ２Ｂとを結ぶ２つの線分と、矩形として特定された障害物領域の辺（輪郭）との交点として、交点ｉ１Ａ、ｉ１Ｂ、ｉ２Ａ、及びｉ２Ｂが特定されていることが確認できる。障害物領域が凸形状の場合、第１オブジェクト位置と候補位置とを通る１つの線分と、障害物領域の輪郭との交点は２点となる。なお、線分が障害物領域の頂点と交差する場合には、交点は１点となるが、この場合には、移動妨害度特定部１２４は、２点の交点を同一の点として特定してもよい。
【００５３】
また、障害物領域が非凸形状の場合、特定した一以上の線分のそれぞれについて、当該線分と障害物領域との交点が３つ以上存在する場合がある。この場合、移動妨害度特定部１２４は、３つの交点の中から取り得る２つの交点のうち、相対的に距離が長い２つの交点を、移動妨害度の特定に用いる２つの交点として特定する。このようにすることで、動線生成装置１は、障害物領域が非凸形状であっても、移動妨害度を精度良く特定することができる。
【００５４】
移動妨害度特定部１２４は、特定した２つの交点と、当該障害物領域との関係に基づいて移動妨害度を特定する。例えば、移動妨害度特定部１２４は、特定した２点の交点により分断される障害物領域の２つの輪郭線のうち、相対的に短い輪郭線の長さに基づいて移動妨害度を特定する。
【００５５】
図６は、特定した２点の交点により分断される障害物領域の２つの輪郭線の例を示す図である。図６には、第１オブジェクト位置ＰＰＡと候補位置Ｐ２Ａとを結ぶ線分により障害物領域が分断されたときの２つの輪郭線ＬＡ及びＬＢが示されていることが確認できる。図６に示す例では、輪郭線ＬＡが、輪郭線ＬＢに比べて短いことが確認できる。移動妨害度特定部１２４は、図６に示す例において、輪郭線ＬＡの長さに基づいて、オブジェクトが第１オブジェクト位置ＰＰＡから候補位置Ｐ２Ａに移動するときの移動妨害度を特定する。例えば、移動妨害度特定部１２４は、輪郭線ＬＡの長さを移動妨害度として算出する。同様に、移動妨害度特定部１２４は、第１オブジェクト位置ＰＰＡと候補位置Ｐ２Ｂとを結ぶ線分により障害物領域が分断されたときの短い方の輪郭線を求め、オブジェクトが第１オブジェクト位置ＰＰＡから候補位置Ｐ２Ｂに移動するときの移動妨害度を特定する。
【００５６】
また、移動妨害度特定部１２４は、特定した２つの交点を結ぶ線分の長さに対する、特定した２つの交点により分断される障害物領域の輪郭線の長さの比率に基づいて移動妨害度を特定してもよい。例えば、移動妨害度特定部１２４は、第１オブジェクト位置と、１つの候補位置とを結ぶ線分により障害物領域が分断されたときの２つの輪郭線のうち、相対的に短い輪郭線を特定する。そして、移動妨害度特定部１２４は、例えば、当該輪郭線に対応する２つの交点を結ぶ線分の長さに対する当該輪郭線の長さの比率を移動妨害度として算出する。
【００５７】
図７は、２つの交点を結ぶ線分の長さに対する輪郭線の長さの比率を算出する例を示す図である。図７には、第１オブジェクト位置ＰＰＡと候補位置Ｐ２Ａとを結ぶ線分により障害物領域が分断されたときの相対的に短い輪郭線ＬＡと、第１オブジェクト位置ＰＰＡと候補位置Ｐ２Ｂとを結ぶ線分により障害物領域が分断されたときの相対的に短い輪郭線ＬＣとが示されている。
【００５８】
図７に示す例において、移動妨害度特定部１２４は、輪郭線ＬＡに対応する２つの交点ｉ１Ａ及びｉ２Ａを結ぶ線分の長さに対する輪郭線ＬＡの長さの比率を、オブジェクトが第１オブジェクト位置ＰＰＡから候補位置Ｐ２Ａに移動するときの移動妨害度として特定する。また、移動妨害度特定部１２４は、輪郭線ＬＣに対応する２つの交点ｉ１Ｂ及びｉ２Ｂを結ぶ線分の長さに対する輪郭線ＬＣの長さの比率を、オブジェクトが第１オブジェクト位置ＰＰＡから候補位置Ｐ２Ｂに移動するときの移動妨害度として特定する。
【００５９】
また、移動妨害度特定部１２４は、特定した２つの交点のそれぞれと、特定した障害物領域の基準点と結ぶ二本の線分のなす角度を特定し、当該角度に基づいて移動妨害度を特定してもよい。ここで、障害物領域の基準点は、例えば、障害物領域の中心点である。
【００６０】
図８は、特定した２つの交点のそれぞれと、特定した障害物領域の基準点とを結ぶ二本の線分のなす角度を特定する例を示す図である。図８には、第１オブジェクト位置ＰＰＡと候補位置Ｐ２Ａとを結ぶ線分により障害物領域を分断したときの２つの交点ｉ１Ａ及びｉ２Ａと、第１オブジェクト位置ＰＰＡと候補位置Ｐ２Ｂとを結ぶ線分により障害物領域を分断したときの２つの交点ｉ１Ｂ及びｉ２Ｂとが示されている。
【００６１】
図８に示す例において、移動妨害度特定部１２４は、候補位置Ｐ２Ａに対応する２つの交点ｉ１Ａ及びｉ２Ａと、中心点Ｏとの角度θＡを特定する。そして、移動妨害度特定部１２４は、当該角度θＡを、オブジェクトが第１オブジェクト位置ＰＰＡから候補位置Ｐ２Ａに移動するときの移動妨害度とする。また、移動妨害度特定部１２４は、候補位置Ｐ２Ｂに対応する２つの交点ｉ１Ｂ及びｉ２Ｂと、中心点Ｏとの角度θＢを特定する。そして、移動妨害度特定部１２４は、当該角度θＢを、オブジェクトが第１オブジェクト位置ＰＰＡから候補位置Ｐ２Ｂに移動するときの移動妨害度とする。
【００６２】
また、移動妨害度特定部１２４は、特定した障害物領域を構成する辺のうち、特定した２つの交点のいずれかが存在する２辺を特定し、当該２辺の間に存在する２つの辺群のうち、相対的に辺の数が少ない辺群に含まれる辺の数に基づいて移動妨害度を特定してもよい。
【００６３】
図９は、辺の数に基づいて移動妨害度を特定する例を示す図である。図９に示す障害物領域は八角形であり、辺Ｅ１〜Ｅ８を備える。図９には、第１オブジェクト位置ＰＰＡと候補位置Ｐ２Ａとを結ぶ線分により障害物領域を分断したときの２つの交点ｉ１Ａ及びｉ２Ａが示されている。図９に示す例では、移動妨害度特定部１２４は、２つの交点ｉ１Ａ及びｉ２Ａのいずれかが存在する２辺として、辺Ｅ３及びＥ６を特定する。当該辺Ｅ３及びＥ６の間には、辺Ｅ４及びＥ５を含む第１の辺群と、辺Ｅ１、Ｅ２、Ｅ７及びＥ８を含む第２の辺群とが存在する。移動妨害度特定部１２４は、相対的に辺の数が少ない第１の辺群に含まれる辺の数（２個）に基づいて、オブジェクトが第１オブジェクト位置ＰＰＡから候補位置Ｐ２Ａに移動するときの移動妨害度を特定する。例えば、移動妨害度特定部１２４は、相対的に辺の数が少ない第１の辺群に含まれる辺の数を移動妨害度とする。
【００６４】
また、移動妨害度特定部１２４は、特定した線分との交点が存在する障害物領域が複数存在する場合に、当該複数の障害物領域を１つの障害物領域に近似してもよい。
【００６５】
図１０は、複数の障害物領域を１つの障害物領域に近似する例を示す図である。図１０では、複数の障害物領域として、障害物領域Ｘ、Ｙ、Ｚが存在しており、第１オブジェクト位置ＰＰＡと候補位置Ｐ２Ａとを結ぶ線分によりこれらの障害物領域を分断したときの６つの交点ｉ１Ａ〜ｉ６Ａが示されている。この場合、移動妨害度特定部１２４は、３つの障害物領域を１つの障害物領域ＳＡに近似する。このようにすることで、移動妨害度特定部１２４は、これらの障害物領域を１つの障害物領域として扱うことができるので、移動妨害度を特定するときの負荷を削減することができる。
【００６６】
選択部１２５は、オブジェクトの第１時刻以前の位置から一以上の候補位置のそれぞれへの移動コストを移動妨害度に基づいて特定し、移動コストが相対的に小さい候補位置を、当該オブジェクトの第２時刻における位置に選択する。
【００６７】
選択部１２５は、オブジェクト位置特定部１２２が特定した第１時刻以前の位置に対応するオブジェクトと、検出位置特定部１２３が特定した一以上の候補位置のそれぞれに対応するオブジェクトとの所定の対応関係における類似度を示す類似度コストを特定する。そして、選択部１２５は、当該類似度コストと、移動妨害度特定部１２４が特定した移動妨害度とに基づいて、第１時刻以前の位置から一以上の候補位置のそれぞれへの移動コストを特定する。
【００６８】
選択部１２５は、第１時刻におけるオブジェクトの位置を特定できた場合には、当該位置に対応するオブジェクトと、一以上の候補位置のそれぞれに対応するオブジェクトとの類似度コストを特定し、第１時刻におけるオブジェクトの位置を特定できなかった場合には、第１時刻よりも前のうち、最新の時刻に対応するオブジェクトの位置に対応するオブジェクトと、一以上の候補位置のそれぞれに対応するオブジェクトとの類似度コストを特定する。
【００６９】
本実施形態では、類似度コストが小さければ小さいほど、第１時刻以前のオブジェクトと、候補位置に対応するオブジェクトとが類似しているものとする。選択部１２５は、例えば、所定エリアの位置に対応するグローバル座標系における第１時刻以前のオブジェクトの位置と、一以上の候補位置のそれぞれとの直線距離又は最短距離を類似度コストとして算出する。また、選択部１２５は、撮像部が撮像した撮像画像上の位置に対応する座標系であるローカル座標系における、オブジェクトに対応する投影領域間の重複率（IoU：Intersection over Union）を算出し、重複率を１から引いた値を類似度コストとして特定してもよい。
【００７０】
また、選択部１２５は、撮像装置により撮像された所定エリアの撮像画像から抽出されたオブジェクトを示すオブジェクト画像が存在する場合には、オブジェクト画像の類似度に基づいて類似度コストを特定してもよい。
【００７１】
例えば、撮像装置により第１時刻に撮像された所定エリアの撮像画像から特定した、第１時刻におけるオブジェクトの位置に対応するオブジェクト画像を第１オブジェクト画像とし、第２時刻に撮像された所定エリアの撮像画像から特定した、一以上の候補位置のそれぞれに対応するオブジェクト画像を第２オブジェクト画像とする。この場合、選択部１２５は、第１オブジェクト画像と、一以上の第２オブジェクト画像のそれぞれとを、同一人物判定装置（不図示）に入力し、同一人物判定装置から判定スコアを取得する。ここで、第１オブジェクト画像に対応する人物と、第２オブジェクト画像に対応する人物とが同一である可能性が高ければ高いほど、判定スコアの値が高くなるものとする。選択部１２５は、例えば、同一人物判定装置から取得した判定スコアの逆数を類似度コストと特定してもよい。
【００７２】
また、選択部１２５は、第１オブジェクト画像の特徴を示す特徴ベクトルと第２オブジェクト画像の特徴を示す特徴ベクトルに基づいて、類似度コストを特定してもよい。例えば、選択部１２５は、特徴量抽出装置（不図示）に、第１オブジェクト画像と、一以上の第２オブジェクト画像とを入力し、特徴量抽出装置から、これらのオブジェクト画像の特徴ベクトルを示す情報を取得する。そして、選択部１２５は、第１オブジェクト画像の特徴ベクトルと、一以上の第２オブジェクト画像のそれぞれに対応する特徴ベクトルとのなす角度により定まるコサイン類似度を算出する。選択部１２５は、一以上の第２オブジェクト画像のそれぞれについて、算出したコサイン類似度を１から引いた値を、当該第２オブジェクト画像に対応する類似度コストとして特定する。
【００７３】
ここで、同一人物判定装置や特徴量抽出装置には、機械学習や深層学習を用いることができる。なお、選択部１２５は、上述した複数の類似度コストの特定方法の少なくともいずれかを組み合わせることにより、第１時刻以前の位置に対応するオブジェクトと、１つの候補位置に対応するオブジェクトとの類似度コストを特定してもよい。
【００７４】
例えば、選択部１２５は、第１時刻以前の位置に対応するオブジェクトと、１つの候補位置に対応するオブジェクトとについて、複数の類似度コストの特定方法のそれぞれに従って類似度コストを特定する。そして、選択部１２５は、各々の特定方法により特定した類似度コストの積や重み付き和等を用いて、第１時刻以前の位置に対応するオブジェクトと、１つの候補位置に対応するオブジェクトとに対応する１つの類似度コストを特定する。
【００７５】
選択部１２５は、特定した類似度コストと、移動妨害度特定部１２４が特定した移動妨害度と少なくともいずれかに基づいて、移動コストを特定する。選択部１２５は、例えば、類似度コストと移動妨害度との積や重み付き和を算出することにより移動コストを特定する。
【００７６】
選択部１２５は、オブジェクト位置特定部１２２が特定した一以上のオブジェクトと、検出位置特定部１２３が検出した一以上の候補位置のそれぞれに対応するオブジェクトとの対応関係を特定するにあたり、移動コストを要素とするコスト行列を生成する。
【００７７】
図４に示す例の場合、選択部１２５は、オブジェクト位置特定部１２２が特定した動線Ｔ１及びＴ２に対応する最新のオブジェクト位置Ｐ１Ａ及びＰ１Ｂを各行とし、候補位置Ｐ２Ａ、Ｐ２Ｂ及びＰ２Ｃを各列とした、２行３列のコスト行列を生成する。行列の各要素には、図４中の各線分が示す対応関係から特定される移動コスト値を含む。選択部１２５は、当該行列にハンガリアン法を適用することにより、コスト値が最小となる第１時刻以前のオブジェクトの位置と、候補位置との対応関係を特定する。
【００７８】
図１１は、第１時刻以前のオブジェクトの位置と、候補位置との対応関係を特定した例を示す図である。図１１は、図４に示される最新のオブジェクト位置Ｐ１Ａ及びＰ１Ｂと、候補位置Ｐ２Ａ、Ｐ２Ｂ及びＰ２Ｃとに対して、ハンガリアン法を適用したときの位置の対応関係として、最新のオブジェクト位置Ｐ１Ａと候補位置Ｐ２Ａ、最新のオブジェクト位置Ｐ１Ｂと候補位置Ｐ２Ｂという２つの対応関係が特定された場合の例を示している。なお、候補位置Ｐ２Ｃは、複数の最新のオブジェクトの位置のいずれとも対応関係が得られていないことが確認できる。
【００７９】
上述した例では、コスト行列として非正方行列（２行３列の行列）を用いるため、候補位置Ｐ２Ｃのように対応関係が特定されない候補位置が生じるが、正方行列を用いる場合には、全ての最新のオブジェクトの位置及び候補位置について対応関係が得られる。このような場合でも、得られた対応関係が必ずしも正しいものとは限らない。
【００８０】
また、移動妨害度は、障害物に基づく移動コストを簡易的に特定した値であることから、例えば、移動距離という観点では、移動妨害度の大小関係は常に正しいとは限らない。これに対し、移動距離の観点から最適な対応関係を特定するためには、計算量の多い最短経路探索アルゴリズムを用いる必要がある。また、コスト行列に含める移動コストを特定するにあたり、類似度コストに移動妨害度を反映させる必要があるが、重み付き和を用いる場合は、適切な重みパラメータの事前設定が困難な場合が多い。
【００８１】
そこで、選択部１２５は、得られた対応関係に対応する移動コストに対して閾値処理を施すことにより、対応関係を高精度に特定してもよい。具体的には、選択部１２５は、最新のオブジェクトの位置と、一以上の候補位置のそれぞれとの移動コストのうち、相対的に小さい移動コストが第１の閾値を超える場合に、当該オブジェクトに対応する候補位置を選択しないように制御してもよい。
【００８２】
また、選択部１２５は、移動妨害度特定部１２４が特定した移動妨害度が第２の閾値を超える候補位置について、当該候補位置に対応する移動コストを、第１の閾値を超える値に設定してもよい。
【００８３】
図１２は、２つの交点を結ぶ線分の長さに対する輪郭線の長さの比率に基づいて移動妨害度を算出する例を示す図である。例えば、図１２に示すように、第１オブジェクト位置ＰＰＡと、候補位置Ｐ２Ａ、Ｐ２Ｂ、Ｐ２Ｃ及びＰ２Ｄとが特定された場合に、移動妨害度特定部１２４が、２つの交点を結ぶ線分の長さに対する輪郭線の長さの比率により移動妨害度を特定したとする。
【００８４】
候補位置Ｐ２Ａに対応する移動妨害度をＤＡ、候補位置Ｐ２Ｂに対応する移動妨害度をＤＢ、候補位置Ｐ２Ｃに対応する移動妨害度をＤＣ、候補位置Ｐ２Ｄに対応する移動妨害度をＤＤとすると、ＤＡ＜ＤＢ＜＜ＤＤ＜ＤＣという大小関係となる。当該大小関係に従うと、候補位置Ｐ２Ａは候補位置Ｐ２Ｂに比べて優先的に第１オブジェクト位置ＰＰＡに対応付けられ、候補位置Ｐ２Ｄは候補位置Ｐ２Ｃに比べて優先的に第１オブジェクト位置ＰＰＡに対応付けられることとなる。しかしながら、対応付けを行うにあたり、必ずしも当該大小関係が正しいとはいえない。
【００８５】
選択部１２５は、移動妨害度が第２の閾値を超える候補位置について、移動コストを第１の閾値を超える値に設定する。例えば、選択部１２５は、移動妨害度が第２の閾値以下の場合は、類似度コストを移動コストとし、第２の閾値を超える場合は、第１の閾値を超える値を移動コストとする。
【００８６】
また、選択部１２５は、移動妨害度が第２の閾値以下の場合は、移動妨害度を１とし、移動妨害度が第２の閾値を超える場合には、移動妨害度を著しく大きい値としてもよい。そして、選択部１２５は、移動妨害度と類似度コストとの積を、移動コストとしてもよい。このようにすることで、第１オブジェクト位置に対する候補位置の移動妨害度が第２の閾値を超える場合は、当該第１オブジェクトに対応する候補位置として、当該候補位置が選択されないように制御することができる。
【００８７】
図１２に示す例では、選択部１２５は、第２の閾値を、移動妨害度ＤＢよりも大きく、移動妨害度ＤＤよりも小さい値に設定する。このようにすることで、選択部１２５は、図１２に示す例において、第１オブジェクト位置ＰＰＡに対して、候補位置Ｐ２Ｃ及び候補位置Ｐ２Ｄが選択されないようにし、第１オブジェクト位置ＰＰＡに対して、候補位置Ｐ２Ａ及びＰ２Ｂのうち、類似度コストが小さい候補位置を対応付けることができる。
【００８８】
動線生成部１２６は、オブジェクトの第１時刻における位置と、選択部１２５が選択した当該オブジェクトの候補位置とを関連付けることにより、当該オブジェクトの移動動線を生成する。例えば、動線生成部１２６は、オブジェクト位置特定部１２２が特定した動線情報に、第２時刻と、選択部１２５が選択した候補位置を示す位置情報と関連付けて追加することにより、当該動線情報を更新する。
【００８９】
なお、動線生成部１２６は、選択部１２５が選択した候補位置を近似フィルタの観測値として用いてもよい。すなわち、動線生成部１２６は、第２時刻における予測位置としての第１オブジェクト位置を、選択部１２５が選択した候補位置に基づいて修正することにより、第２時刻におけるオブジェクトの確定位置としてもよい。図１３は、第２時刻に対応する確定位置を特定した例を示す図である。図１３では、第１オブジェクト位置ＰＰＡと、候補位置Ｐ２Ａとの関係に基づいて、第２時刻ｔにおける確定位置ＰＦＡが特定され、第１オブジェクト位置ＰＰＢと、候補位置Ｐ２Ｂとの関係に基づいて、第２時刻ｔにおける確定位置ＰＦＢが特定されていることが確認できる。このようにすることで、動線生成装置１は、第２時刻ｔにおけるオブジェクトの位置を精度良く特定することができる。
【００９０】
［動線生成装置１における処理の流れ］
続いて、動線生成装置１における処理の流れについて説明する。図１４は、本実施形態に係る動線生成装置１における処理の流れを示すフローチャートである。
【００９１】
まず、障害物領域特定部１２１は、所定エリアに存在する障害物の形状に対応する障害物領域と、障害物領域の所定エリアにおける位置とを特定する（Ｓ１）。
続いて、オブジェクト位置特定部１２２は、所定エリアを移動する一以上のオブジェクトの第１時刻以前の位置を特定する（Ｓ２）。具体的には、オブジェクト位置特定部１２２は、第１時刻までの位置情報又は第１時刻以前の時刻までの位置情報を含む一以上の動線情報を特定し、当該動線情報において最新の時刻に関連付けられている位置情報を特定することにより、一以上のオブジェクトの第１時刻以前の位置を特定する。
【００９２】
続いて、検出位置特定部１２３は、第１時刻よりも後の時刻である第２時刻におけるオブジェクトの一以上の検出位置の候補である候補位置を特定する（Ｓ３）。
続いて、移動妨害度特定部１２４は、一以上の第１オブジェクト位置の、一以上の候補位置のそれぞれに対する移動妨害度を特定する（Ｓ４）。
【００９３】
続いて、選択部１２５は、一以上のオブジェクトの、一以上の候補位置のそれぞれに対応するオブジェクトとの類似度を特定する（Ｓ５）。
続いて、選択部１２５は、Ｓ４において特定された移動妨害度と、Ｓ５において特定された類似度とに基づいて、一以上のオブジェクトの、一以上の候補位置のそれぞれに対応する移動コストを特定する（Ｓ６）。
【００９４】
続いて、選択部１２５は、Ｓ６において特定された、一以上のオブジェクトの、一以上の候補位置のそれぞれに対応する移動コストに基づいて、一以上のオブジェクトと、一以上の候補位置との対応関係を特定する（Ｓ７）。
【００９５】
続いて、動線生成部１２６は、Ｓ２において特定した一以上の動線情報のそれぞれに、第２時刻と、当該動線情報が示すオブジェクトに対して特定された候補位置が示す位置情報とを関連付けて格納することにより、当該動線情報を更新する（Ｓ８）。
【００９６】
［本実施形態における効果］
以上説明したように、本実施形態に係る動線生成装置１は、所定エリアに対応する障害物領域の所定エリアにおける位置を特定し、所定エリアを移動するオブジェクトの第１時刻以前の位置を特定するとともに、第１時刻よりも後の時刻である第２時刻における当該オブジェクトの一以上の候補位置を特定する。動線生成装置１は、特定した第１時刻以前のオブジェクトの位置と、特定した一以上の候補位置と、特定した障害物領域の位置との位置関係に基づいて、オブジェクトが一以上の候補位置のそれぞれに移動するときの移動妨害度を特定する。そして、動線生成装置１は、当該オブジェクトの第１時刻以前の位置から一以上の候補位置のそれぞれへの移動コストを移動妨害度に基づいて特定し、移動コストが相対的に小さい候補位置を、当該オブジェクトの第２時刻における位置に選択する。このようにすることで、動線生成装置１は、オブジェクトの対応関係を効率的に特定することができる。
【００９７】
以上、本発明を実施形態を用いて説明したが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。上記実施形態に、多様な変更又は改良を加えることが可能であることが当業者に明らかである。
【００９８】
また、特に、装置の分散・統合の具体的な実施形態は以上に図示するものに限られず、その全部又は一部について、種々の付加等に応じて、又は、機能負荷に応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。
【符号の説明】
【００９９】
１・・・動線生成装置、１１・・・記憶部、１２・・・制御部、１２１・・・障害物領域特定部、１２２・・オブジェクト位置特定部、１２３・・・検出位置特定部、１２４・・・移動妨害度特定部、１２５・・・選択部、１２６・・・動線生成部
【図１】
2020021171.tif 000003
【図２】
2020021171.tif 000004
【図３】
2020021171.tif 000005
【図４】
2020021171.tif 000006
【図５】
2020021171.tif 000007
【図６】
2020021171.tif 000008
【図７】
2020021171.tif 000009
【図８】
2020021171.tif 000010
【図９】
2020021171.tif 000011
【図１０】
2020021171.tif 000012
【図１１】
2020021171.tif 000013
【図１２】
2020021171.tif 000014
【図１３】
2020021171.tif 000015
【図１４】
2020021171.tif 000016
【図１５】
2020021171.tif 000017