(57)【要約】【課題】  奥行画像から、重なり合ったり隣接する手を含む手話を認識するための方法およびシステムを提供する。【解決手段】  リンク構造７００は、重なり合ったり隣接する手を含んだ奥行画像２１２から生成した複数のセグメントを含む。重なり合ったり隣接する手形状を、（ｉ）コスト関数および制約条件を用いてリンクグラフのセグメントを両方の手に分類するような、制約条件付最適化処理を用いるか、または（ｉｉ）複数のノードを含んだツリー構造を用いたツリー検索処理を用いて、奥行画２１２像で表される最も可能性の高い手形状を得る。手形状を決定した後は、リンク構造７００のセグメントを、記憶している形状にマッチングさせて、奥行画像２１２で表されるサインを決定する。【選択図】図２
2011501316.tif 000002
【特許請求の範囲】
【請求項１】
手話を認識するコンピュータベースの方法であって、
前記方法は、
１つ以上のカメラを用いて、対象の部位と前記１つ以上のカメラとの距離を表す画像画素を含んだ前記対象の奥行画像を受信し、
前記奥行画像における前記対象の第１の手と第２の手とが重なり合うか隣接していると決定した場合に、前記奥行画像を、前記対象の第１の手を表す第１の部位と前記対象の第２の手を表す第２の部位とに分類し、
前記第１の部位と前記第２の部位との形状を、記憶している手形状にマッチングさせて、前記奥行画像において前記第１の手と前記第２の手とで表されるサインを出力する
ことを特徴とするコンピュータベースの方法。
【請求項２】
前記奥行画像から前記第１の手と前記第２の手とを表すリンク構造を生成し、前記リンク構造は、互いにリンクする２つ以上のセグメントを含むことを特徴とする請求項１に記載のコンピュータベースの方法。
【請求項３】
前記奥行画像を分類することは、
前記２つ以上のセグメントを前記第１の手と前記第２の手とに分類するためのコストを示すコスト関数を生成し、
前記コスト関数を最小化し、さらに、手の特性を表す制約条件を満たすような、前記第１の手と前記第２の手とについての手形状を決定する
ことを含むことを特徴とする請求項２に記載のコンピュータベースの方法。
【請求項４】
前記制約条件は、
近接するセグメントどうしは、同じ手に属するセグメントになる可能性が高い第１条件と、
画像画素の第１クラスタから生成した第１セグメントは、前記第１クラスタの第１の厚さが閾値よりも大きい場合には、２本以上の指を含む第２条件と、
画像画素の第２クラスタから生成した第２セグメントは、前記第２クラスタの第２の厚さが前記閾値以下である場合には、１本の指を含む第３条件と、
前記第１の手と前記第２の手とに分類されるセグメントの長さの合計は、最大値を超えない第４条件とを含む
ことを特徴とする請求項３に記載のコンピュータベースの方法。
【請求項５】
前記奥行画像を分類することは、前記リンク構造に基づいて、セグメントを表すノードを含み、かつ前記ノード間の連結間関係を示すような非循環有向グラフの構造を生成し、
前記ノードの第１のセットを前記第１の手にグループ化し、前記ノードの第２のセットを前記第２の手にグループ化するような、ノードの組み合わせを生成し、
両方の手の特徴を表す１つ以上の基準を用いて、前記ノードの組み合わせを評価する
ことを特徴とする請求項２に記載のコンピュータベースの方法。
【請求項６】
前記ノードの組み合わせを評価することは、
同じ手に分類された第１のノードと第２のノードとのリンクを表す第１のスコアを求め、
セグメントが分類された手のひらと前記セグメントとの距離を表す第２のスコアを求め、
前記同じ手に分類された、リンクするセグメントどうしの角度を表す第３のスコアを求め、
分岐ノードと前記分岐ノードが分類された手のひらとの距離を表す第４のスコアを求め、この場合の前記分岐ノードは、３つ以上のノードにリンクするノード、もしくは手のひらと２つ以上のノードにリンクするノードを表し、
前記第１のスコアと、前記第２のスコアと、前記第３のスコアと、前記第４のスコアとの合計値が最も小さい組み合わせを決定する
ことを含むことを特徴とする請求項５に記載のコンピュータベースの方法。
【請求項７】
前記第１の手のひらと前記第２の手のひらとを検出することを含むことを特徴とする請求項１に記載のコンピュータベースの方法。
【請求項８】
前記第１の手のひらまたは前記第２の手のひらを検出することは、
前記第１の手と前記第２の手とを表す画像画素に基づいてスケルトン線を生成し、
前記スケルトン線と直交し、かつ前記第１の手と前記第２の手の輪郭となる画像画素のエッジと交差する線の極大長さを求めることで、前記第１の手のひらまたは前記第２の手のひらの中央部を含んでいる線の候補を決定し、
前記第１の手または前記第２の手の指を表す画像画素に最も近接する前記線の候補の中央部を、前記手のひらの中央部として決定する
ことを特徴とする請求項７に記載のコンピュータベースの方法。
【請求項９】
前記リンク構造を生成することは、前記第１の手および前記第２の手を表す前記画像画素を細線化する
ことを含むことを特徴とする請求項２に記載のコンピュータベースの方法。
【請求項１０】
プロセッサによって実行可能な指令を記憶するコンピュータ読み取り可能媒体を含むコンピュータプログラム製品であって、
前記指令を実行することで、プロセッサは、
１つ以上のカメラを用いて、対象の部位と前記１つ以上のカメラとの距離を表す画像画素を含んだ前記対象の奥行画像を受信し、
前記奥行画像における前記対象の第１の手と第２の手とが重なり合うか隣接していると決定した場合に、前記奥行画像を、前記対象の第１の手を表す第１の部位と前記対象の第２の手を表す第２の部位とに分類し、
前記第１の部位と前記第２の部位との形状を、記憶している手形状にマッチングさせて、前記奥行画像において前記第１の手と前記第２の手とで表されるサインを出力する
ことを特徴とするコンピュータプログラム製品。
【請求項１１】
前記コンピュータプログラム製品は、前記奥行画像から前記第１の手と前記第２の手を表すリンク構造を生成する指令をさらに含み、
前記リンク構造は互いにリンクする２つ以上のセグメントを含む
ことを特徴とする請求項１０に記載のコンピュータプログラム製品。
【請求項１２】
前記奥行画像を分類する指令は、
前記２つ以上のセグメントを前記第１の手と前記第２の手とに分類するためのコストを示すコスト関数を生成し
前記コスト関数を最小化し、さらに、手の特性を表す制約条件を満たすような、前記第１の手と前記第２の手とについての手形状を決定する指令を含む
ことを特徴とする請求項１１に記載のコンピュータプログラム製品。
【請求項１３】
前記制約条件は、
近接するセグメントどうしは、同じ手に属するセグメントになる可能性が高い第１条件と、
画像画素の第１クラスタから生成した第１セグメントは、前記第１クラスタの第１の厚さが閾値よりも大きい場合には、２本以上の指を含む第２条件と、
画像画素の第２クラスタから生成した第２セグメントは、前記第２クラスタの第２の厚さが前記閾値以下である場合には、１本の指を含む第３条件と、
前記第１の手と前記第２の手とに分類されるセグメントの長さの合計は、最大値を超えない第４条件とを含む
ことを特徴とする請求項１２に記載のコンピュータプログラム製品。
【請求項１４】
前記デジタル画像を分類する指令は、
前記リンク構造に基づいて、セグメントを表すノードを含み、前記ノード間の連結間関係を示すような非循環有向グラフの構造を生成し、
前記ノードの第１のセットを前記第１の手にグループ化し、前記ノードの第２のセットを前記第２の手にグループ化するような、ノードの組み合わせを生成し、
手の特徴を表す１つ以上の基準を用いて、前記ノードの組み合わせを評価するための指令であることを特徴とする請求項１２に記載のコンピュータプログラム製品。
【請求項１５】
前記ノードの組み合わせを評価する指令は、
同じ手に分類された第１のノードと第２のノードとのリンクを表す第１のスコアを求め、
セグメントが分類された手のひらと前記セグメントとの距離を表す第２のスコアを求め、
前記同じ手に分類された、リンクするセグメントどうしの角度を表す第３のスコアを求め、
分岐ノードと前記分岐ノードが分類される手のひらとの距離を表す第４のスコアを求め、この場合の前記分岐ノードは、３つ以上のノードにリンクするノード、もしくは手のひらと２つ以上のノードにリンクするノードを表し、
前記第１のスコアと、前記第２のスコアと、前記第３のスコアと、前記第４のスコアとの合計値が最も小さい組み合わせを決定する指令を含むことを特徴とする請求項１４に記載のコンピュータプログラム製品。
【請求項１６】
前記第１の手のひらと前記第２の手のひらを検出するための指令をさらに含む
ことを特徴とする請求項１０に記載のコンピュータプログラム製品。
【請求項１７】
前記第１の手のひらまたは前記第２の手のひらを検出するための指令は、
前記第１の手と前記第２の手とを表す画像画素に基づいてスケルトン線を生成し、
前記スケルトン線と直交し、かつ前記第１の手と前記第２の手の輪郭となる画像画素のエッジと交差する線の極大長さを求めることで、前記第１の手のひらまたは前記第２の手のひらの中央部を含んでいる線の候補を決定し、
前記第１の手または前記第２の手の指を表す画像画素に最も近接する前記線の候補の中央部を、前記手のひらの中央部として決定する
ことを特徴とする請求項１６に記載のコンピュータプログラム製品。
【請求項１８】
前記リンク構造を生成するための前記指令は、前記第１の手および前記第２の手を表す前記画像画素を細線化するための指令を含む
ことを特徴とする請求項１１に記載のコンピュータプログラム製品。
【請求項１９】
手話認識用のコンピュータベースシステムであって、
前記システムは、対象の奥行画像を生成する１つ以上のカメラを備え、前記奥行画像は、対象の部位と前記１つ以上のカメラとの距離を表す画像画素を含み、
前記１つ以上のカメラに接続されて、前記奥行画像における前記対象の第１の手と前記第２の手とが重なり合うか隣接していると決定した場合に、前記奥行画像を、前記対象の第１の手を表す第１の部位と前記対象の第２の手を表す第２の部位とに分類する
画像前処理モジュールと、
前記画像前処理モジュールに接続され、前記第１の部位と前記第２の部位との形状を、記憶している手形状にマッチングさせて、前記奥行画像において前記第１の手と前記第２の手とで表されるサインを出力する形状マッチングモジュールと
を備えることを特徴とするコンピュータベースシステム
【請求項２０】
前記前処理モジュールは、さらに、前記奥行画像から前記第１の手と前記第２の手を表すリンク構造を生成し、前記リンク構造は、互いにリンクする２つ以上のセグメントを含むことを特徴とする請求項１９に記載のコンピュータベースシステム
【請求項２１】
前記形状マッチングモジュールは、
前記２つ以上のセグメントを前記第１の手と前記第２の手とに分類するためのコストを示すコスト関数を生成し、
前記コスト関数を最小化し、さらに、手の特性を表す制約条件を満たすような、前記第１の手と前記第２の手とについての手形状を決定する最適化モジュールを備える
ことを特徴とする請求項１９に記載のコンピュータベースシステム。
【請求項２２】
前記制約条件は、
近傍に位置するセグメントどうしは、同じ手に属するセグメントになる可能性が高い第１条件と、
画像画素の第１クラスタから生成した第１セグメントは、前記第１クラスタの第１の厚さが閾値よりも大きい場合には、２本以上の指を含む第２条件と、
画像画素の第２クラスタから生成した第２セグメントは、前記第２クラスタの第２の厚さが前記閾値以下である場合には、１本の指を含む第３条件と、
前記第１の手と前記第２の手とに分類されるセグメントの長さの合計は、最大値を超えない第４条件とを含む
ことを特徴とする請求項２１に記載のコンピュータベースシステム。
【請求項２３】
前記形状マッチングモジュールは、前記リンク構造に基づいて、セグメントを表すノードを含み、前記ノード間の連結関係を示すような非循環有向グラフの構造を生成し、
前記ノードの第１のセットを前記第１の手にグループ化し、前記ノードの第２のセットを前記第２の手にグループ化するような、ノードの組み合わせを生成し、
両手の特徴を表す１つ以上の基準を用いて、前記ノードの組み合わせを評価するようなツリー検索モジュールをさらに備える
ことを特徴とする請求項２０に記載のコンピュータベースシステム。
【請求項２４】
前記ツリー検索モジュールは、
同じ手に分類される第１のノードと第２のノードとのリンクを表す第１のスコアと、セグメントが分類される手のひらと前記セグメントとの距離を表す第２のスコアと、前記同じ手に分類されたリンクするセグメントどうしの角度を表す第３のスコアと、分岐ノードと前記分岐ノードが分類される手のひらとの距離を表す第４のスコアとを足して、前記ノードの組み合わせを評価し、
この場合の前記分岐ノードは、３つ以上のノードにリンクするノードもしくは手のひらと２つ以上のノードにリンクするノードを表す
ことを特徴とする請求項２３に記載のコンピュータベースシステム。
【請求項２５】
前記画像前処理モジュールは、前記第１の手のひらと、前記第２の手のひらを検出することを特徴とする請求項１９に記載のコンピュータベースの方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には人間−機械インタラクションに関し、具体的には手話の手サインの認識に関する。
【背景技術】
【０００２】
超高速演算システムと高効率デジタル画像システムの到来によって、人間−機械インタラクションに基づくコンピュータビジョンの分野は、著しい技術進歩の時代を経験している。
モーションによって機械（監視システムなど）からの応答を誘発するような簡便なモーション検出システムから、高度に複雑化した三次元（３Ｄ）画像サイン認識システム（imaging sign recognition systems）に至るまでの技術は、近年の著しい発展の主題である。例えば、サインに基づく人間−機械コミュニケーションの領域では、人間の手話を認識することは、人間−機械コミュニケーションにおける有望な技術として、近年、多くの研究においてテーマとなっている。
この他に、手と手の動きを、他の身体部位（腕部、胴体部、頭部など）の関係から探し出して追跡するような各種方法に基づいたサイン認識システムや、より複雑なジェスチャ認識システムが開発されている。
【０００３】
サインおよびジェスチャの認識には、一般に、マシンビジョンシステムでサインやジェスチャのソースを見つけ出すための支援として、マーカー、特定色、背景あるいはグローブが必要になる。例えば、手検出に関する従来の手法によっては、システムに対して身振りをする片手や両手に対応する画像領域を決定するために、色やモーションの情報を用いる。しかし、このような手法では、照明条件の変化にともなって手のモーションの追跡の信頼性が著しく低下する。さらに、システムによってはグローブなどの特殊な装置を用いたり、タスクを実行可能にするために特殊色の背景を用いたりするものもある。
【０００４】
また、従来技術の別群では、サインやジェスチャを認識するために、ステレオビジョンカメラや飛行時間センサで生成した奥行画像を用いる。奥行画像を解析して、手や腕を表す画像画素を抽出する。抽出した画像画素をさらに処理し、記憶している手形状とマッチングさせて、手と腕を表す画像画素で表される手サインを認識する。また、手と腕の軌跡を追跡して、画像シーケンスにおいて手形状と手の動きで表されるジェスチャや手話を決定することもある。奥行画像を用いた従来技術は、管理されない実生活の環境下での実装に便利であるため、マーカー、特殊な色や背景あるいはグローブを必要とする技術と比較して、有利である。さらに、奥行画像を用いる従来技術は、手話を介してコミュニケーションする人物に機器や装置を取付けたり、あるいは、その人物の周辺に機器や装置を設置する必要がない点でも有利である。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、奥行画像を用いる従来の手サイン認識システムは、１本または２本の手が隣接したり重なり合わないような手話においてのみ認識可能である。奥行画像とは、一般に、カメラから対象までの距離を示す画像画素を有するグレースケール画像である。このような奥行画像では、奥行画像中で２つ以上のオブジェクト（手など）が重なり合ったり隣接している場合は、どの画像画素がどのオブジェクト（手など）を表しているのかが曖昧になる。
【０００６】
例えば、図１（ａ）ないし図１（ｃ）は、手が重なり合ったり隣接するような日本手話（ＪＳＬ：Japanese Sign Language）を示したものである。図１（ａ）は「手紙」を意味するサインを、図１（ｂ）は「井戸」を意味するサインを、図１（ｃ）は「合う（fit）」を意味するサインを日本手話で示している。従来の奥行画像を用いたサイン認識システムは、手どうしが重り合う場合には、片方の手を表す画像画素をもう片方の手から分離させる能力を備えていないため、このように重なり合ったり隣接するような手形状や手の動きを認識し、特定することはできない。したがって、従来の奥行画像を用いたサイン認識システムが認識できるのは、手話で一般的に用いられるサインの一部のみである。
【課題を解決するための手段】
【０００７】
本発明の実施形態では、重なり合ったり隣接する手を含んでいる手話サインを認識するための方法とシステムを提供する。サイン認識システムは、対象の奥行画像を受信し、対象の手を表す奥行画像の部分を抽出し、さらに、サイン認識システムは、奥行画像の手が重なり合ったり隣接していると決定した場合には、奥行画像を対象の第１の手を表す第１の部位と対象の第２の手を表す第２の部位とに分類する。
【０００８】
一実施形態では、サイン認識システムは、第１の手と第２の手を表すリンク構造を生成する。次に、リンク構造のセグメントを、第１の手に割当てるための第１のセグメントのセットと、第２の手に割当てるための第２のセグメントのセットとに分類する。次に、第１のセグメントのセットと第２のセグメントのセットをそれぞれ、記憶している手形状にマッチングさせて、第１の手と第２の手によって表されるサインを決定する。
【０００９】
本発明の一実施形態では、リンク構造のセグメントを、制約条件付最適化技術を用いて第１の手と第２の手とに分類する。１つのセグメントのセットを第１の手と、別のセグメントのセットを第２の手とに分類するためのコストを表すコスト関数を生成する。さらに、手の物理的な構造および特徴に関する制約条件を生成する。例えば、制約条件には、互いに隣接するセグメントどうしは同じ手に分類される可能性が高い条件が含まれる。本実施形態に係るサイン認識システムは、上記のコスト関数と制約条件とを用いて、サイン認識をラベル付与問題に変換する。次に、サイン認識システムは、リンク構造のセグメントを第１の手と第２の手とに分類する。
【００１０】
本発明の一実施形態では、ツリー検索技術を用いて、リンク構造のセグメントを第１の手と第２の手とに分類する。ツリー検索技術は、リンク構造に基づいて（セグメントを表す）ノードを有する非循環有向グラフを生成し、これらのノードどうしの連結関係を示すことを含む。上記のノードは、第１の手に割当てた第１のノードのセットと、第２の手に割当てた第２のノードのセットとに分類される。１つ以上の基準を用いて、ノードの各種組み合わせを評価する。
【００１１】
本発明の一実施形態では、第１の手のひらと第２の手のひらとを検出する。第１の手のひらと第２の手のひらは、まず、第１の手または第２の手を表す画像画素のスケルトン線を生成する。第１の手のひらまたは第２の手のひらの中央部を含んでいる可能性のある線の候補を求めるには、スケルトン線と直交する線の、第１の手や第２の手の輪郭となる画像画素のエッジ間の長さを測定することで求める。第１の手のひらまたは第２の手のひらの中央部を含む線として、指に最も近接する線の候補を選ぶようにしてもよい。
【００１２】
本明細書に記載される特徴および利点はすべて包含される必要はなく、特に、当業者であれば、図や明細書あるいは特許請求の範囲に照らして、さらなる特徴および利点を追加することが可能であることは明らかである。
さらに、本明細書中の説明で用いられた文言は、読みやすさや例示的な目的から主に用いられたものであって、本発明の主題の範囲を詳説したり、限定するために選択されたものではない。
【図面の簡単な説明】
【００１３】
【図１】（ａ）ないし（ｃ）は、重なり合ったり隣接する手を含む日本手話のサインと例示している。
【図２】本発明の一実施形態に係るサイン認識システムの概略ブロック図を例示している。
【図３】（ａ）は本発明の一実施形態に係る形状マッチングモジュールのブロック図を、（ｂ）は本発明の一実施形態に係る形状マッチングモジュールのブロック図を、それぞれ例示している。
【図４】本発明の一実施形態に係る手話を認識する方法のフローチャートを例示している。
【図５】本発明の一実施形態に係る手のひらを検出する方法のフローチャートを例示している。
【図６】本発明の一実施形態に係る手のひらを検出するための手の画像を例示している。
【図７】（ａ）は本発明の一実施形態に係るサイン認識システムで処理する奥行画像の事例を、（ｂ）は本発明の一実施形態に係る、（ａ）の奥行画像から生成したスケルトン構造を、（ｃ）は本発明の一実施形態に係る、（ｂ）のスケルトン構造から生成したリンク構造を、それぞれ例示している。
【図８】本発明の一実施形態に係る、制約条件最適化法を用いてリンク構造のセグメントを分類する方法を例示している。
【図９】本発明の一実施形態に係る、ツリー検索法を用いてリンク構造のセグメントを分類する方法を例示している。
【図１０】本発明の一実施形態に係る、非循環有向グラフを用いて手形状を生成する方法のフローチャートを例示している。
【図１１】本発明の一実施形態に係る、図７（ｃ）のリンク構造から生成したノードを有するツリー構造を例示している。
【図１２】本発明の一実施形態に係る、右手と左手に分類したときの奥行画像の画像画素の事例を示している。
【発明を実施するための形態】
【００１４】
図面を参照しつつ、以下に、本発明の好ましい実施形態について説明するのが、類似する参照番号は同一もしくは機能的に類似する構成要素を表す。さらに、図面の各参照番号の最左桁は、その参照番号が最初に用いられる図に対応する。
【００１５】
明細書中の「一実施形態」あるいは「実施形態」という記述は、当該の実施形態に関して記載された特定の特徴、構造、特性が本発明の少なくとも１つの実施形態に含まれることを意味する。明細書の随所に現れる「一実施形態では」という表現は、必ずしも同一の実施形態について言及するものではない。
【００１６】
詳細な記載の部分によっては、コンピュータメモリ内のデータビットの操作に関するアルゴリズムや符号表現によって提示される。このようなアルゴリズム的な記載や表現は、データ処理技術を扱う当業者によって用いられる手段であり、他の当業者に仕事の実体を効果的に伝達するためのものである。ここで言う一般的なアルゴリズムとは、所望の結果を導くためのステップ（指令）を自己無頓着に連続したものと認識されるものである。このようなステップでは、物理量を物理的に操作することを必要とする。必ずしもではないが通常、このような物理量は、記憶、伝送、結合、比較、もしくは処理が可能な電気信号あるいは磁気信号の形態をとる。主に一般用途の理由から、このような信号をビット、値、要素、シンボル、文字、用語、数などで呼ぶほうがしばしば利便である。さらに、物理的な数量の物理的な操作を必要とするステップに関する特定の構成を、モジュールや符号装置などと呼ぶほうが、一般性を失うことなく、しばしば利便である。
【００１７】
しかしながら、このような表現あるいは類似の表現は所定の物理量に関連する便宜上のラベルにすぎない。説明から明らかな場合を除いて特に言及しない限りは、記載全体を通じて「処理する」、「演算する」、「算出する」、「決定する」あるいは「表示する」などの表現を用いる説明では、コンピュータシステムの記録部や記憶部に記憶される物理的（電子的）な数量として表されるデータを操作して、コンピュータシステムの記録部、記憶部、送信部、表示部などに記憶される、同様に物理量として表される別のデータに変換するようなコンピュータシステムあるいは類似の電子演算装置の実行や処理について述べている。
【００１８】
本発明の特定の側面は、ここではアルゴリズムの形態で記載される処理ステップや指令を含む。なお、本発明のこれらの処理ステップや指令は、ソフトウェア、ファームウェアあるいはハードウェアにおいて具現可能であり、ソフトウェアにおいて具現する場合、各種のオペレーションシステムで用いられる異なるプラットフォーム上に搭載され、そこから操作したりするためにダウンロードが可能である。
【００１９】
また、本発明は、ここに記載される動作を実行する装置に関する。この装置は、必要な用途に合わせて特定の構成を備えていてもよいし、コンピュータに記憶されるコンピュータプログラムによって選択的に起動されたり、再構成されるような汎用コンピュータから構成されていてもよい。かかるコンピュータプログラムは、以下のようなコンピュータ読取り可能な媒体に記憶されてもよいが、これらに限定されるものではない：フレキシブルディスク、光ディスク、CD-ROM、磁気光ディスクなどを含むあらゆる種類のディスク、ROM、RAM、EPROM、EEPROM、磁気カードや光カード、ASIC（Application Specific Integrated Circuits）、あるいは電子命令（electronic instructions）の記憶に適したあらゆる種類の媒体、および各々がコンピュータシステムバスに連結されたもの。さらに、本明細書に記載されるコンピュータには単一のプロセッサが含まれ、あるいは、演算能力を向上させるために複数のプロセッサデザインを用いた構造であってもよい。
【００２０】
ここでいうアルゴリズムや表示は、特定のコンピュータやこの他の装置のみを指すものではない。各種の汎用システムは、ここに教示される内容に従ったプログラムとともに用いてもよく、あるいは、必要な方法ステップを実行するために専用の装置を構築するほうが利便な場合もある。これらの各種システムに必要な構造は、以下の記載から明らかである。さらに、本発明は、特定のプログラミング言語を指して記載されるものではない。各種のプログラミング言語を用いて、以下に記載される本発明の教示を実装するようにしてもよく、さらに、以下の特定言語は、本発明の実施可能性と最良の形態を開示するために記載されたものであることは理解されるであろう。
【００２１】
さらに、本明細書中の説明で用いられた文言は、読みやすさや例示的な目的から主に用いられたものであって、本発明の主題の範囲を詳説したり、限定するために選択されたものではない。したがって、本発明の開示は、例示を意図したものであって、以下の特許請求の範囲に記載される本発明の範囲を限定するものではない。
【００２２】
手サイン認識の一実施形態によれば、サイン認識システムにより認識、特定できるサインの数を増大させることができる。具体的には、サイン認識システムは、奥行画像において両手が重なり合ったり隣接する場合であっても、両手の形状を決定するものである。重なり合ったり隣接する両手の形状は、（ｉ）コスト関数と制約条件を用いて、リンク構造のセグメントを分類する問題を線形計画最適化問題（linear programming optimization problem）の形態のラベル付与問題に変換する制約条件付最適化法（constrained optimization method）、あるいは（ｉｉ）複数のノードを含む非循環有向グラフ（directed acyclic graph）を用いて、奥行画像に表される両手について最も可能性が高そうな形状を求めるツリー検索法（tree search method）によって決定するようにしてもよい。両手の形状を決定した後、リンク構造のセグメントを、記憶している手形状とマッチングさせて、奥行画像に表されるサインを決定する。
【００２３】
ここで言うリンク構造とは、重なり合ったり隣接する両手の形状を決定するために用いる画像画素から得たリンク線のセットを言う。このようなリンク構造には、奥行画像の手の特徴を表す２つ以上のセグメントが含まれる。リンク構造は、例えば、重なり合ったり隣接する手を表す画像画素のクラスタを細線化し、さらに、手形状を特定、認識するための処理を行うことで求める。このように、リンク構造を用いれば、手話サインを認識、特定する際に画像画素を処理する必要がなくなるため、手話サインを認識するための演算やアルゴリズムを簡略化することができる。
【００２４】
図面と以下の記載は、実例のみを用いた本発明の好ましい実施形態に関する。以下の記載から、ここに開示される構成や方法の代替の実施形態は、請求項に係る発明の原則から逸脱しない範囲で実現可能な代替案として容易に認識されるであろう。
【００２５】
サイン認識システムの構造
図２は、本発明の一実施形態に係るサイン認識システム２００の概略ブロック図である。サイン認識システム２００は、構成部品の中でも特に、画像キャプチャ装置２１０と画像処理モジュール２２０とを備える。画像キャプチャ装置２１０は、対象２５２の奥行画像２１２を取得し、この奥行画像２１２を画像処理モジュール２２０に送信する。画像処理モジュール２２０は、奥行画像２１２を処理し、特定した対象２５２の手サインを示すデータ２４０を出力する。
【００２６】
一実施形態では、画像キャプチャ装置２１０は、手形状を分析するために十分な解決策として機能する飛行時間センサを備え、例えば、スイス連邦チューリッヒのCSEM SA社製、イスラエル国ヨークナムの3DV Systems社製、あるいはカリフォルニア州サンノゼのCanesta, Inc社製のカメラなどである。飛行時間センサは、対象が動き回ると予測される範囲の領域を包含する奥行のある窓に設置する。なお、背景などの非対象物は奥行画像２１２の一部をなさない。別の実施形態では、画像キャプチャ装置２１０は、距離を隔てて設置した２つ以上の画像センサに基づいて、奥行画像２１２を生成するステレオビジョンカメラを備える。符号化光や時間−空間ステレオ画像を用いて奥行画像２１２を生成するようにしてもよい。
【００２７】
画像処理モジュール２２０は、奥行画像２１２から手サインを認識するための専用装置であってもよい。あるいは、画像処理モジュール２２０は、パーソナルコンピュータなどの汎用演算装置の一部であってもよい。画像処理モジュール２２０は、構成部品の中でも特に、コンピュータプロセッサや、ＲＡＭ、ＲＯＭ、フラッシュメモリ、ディスクドライブ等のコンピュータ読み取り可能媒体などの従来のデータ処理装置やデータ記憶装置を備える。好ましくは、コンピュータプロセッサは、実行可能なソフトウェアプログラムからのプログラム指令が実行されると画像処理機能を具現化するような能力を有する従来の汎用プロセッサである。一実施形態では、画像処理モジュール２２０は、ジェスチャの特徴を認識し、関連する変化を表示装置（図示せず）に表示するために、１つ以上のコンピュータプログラムにアクセスできるようなコンピュータ読み取り可能媒体（図示せず）を備える。
【００２８】
一実施形態では、サイン認識システム２００は、例えば、日本国東京の本田技研工業株式会社製の最新人間型ロボット「ＡＳＩＭＯ」（登録商標）などに用いるロボット用人間−機械インタラクションシステムの一部である。本実施形態では、画像キャプチャ装置２１０は、ロボットビジョンユニットの一部であってもよく、画像処理モジュール２２０はロボットの制御理論の一部であってもよい。ロボット用人間−機械インタラクションシステムにおけるサイン認識システム２００は、例えば、会話や音声による指令が有効でないような騒々しい環境でロボットに指示を与えるときに用いるようにしてもよい。
【００２９】
画像処理モジュール２２０は画像キャプチャ装置２１０に接続しており、奥行画像２１２を受信する。画像処理モジュール２２０は、構成部品の中でも特に、画像バッファ２２２と、画像前処理モジュール２２４と、形状マッチングモジュール２２６とを備える。画像バッファ２２２は、画像キャプチャリング装置２１０から奥行画像２１２を受信するように構成されている。画像バッファ２２２は、周辺インターフェースハードウェア、ネットワークインターフェースハードウェア（有線または無線）などの一部であってもよい。一実施形態では、画像バッファ２２２から受信した奥行画像２１２を、ハードディスク、フラッシュメモリ、ＲＡＭなどの内部データ記憶装置（図示せず）に記憶する。
【００３０】
画像前処理モジュール２２４では、各種の画像処理作業を行い、その中でも特に、例えば、米国特許出願番号第11/129164号、発明の名称「Sign Based Human-Machine Interaction」、出願日２００５年５月１２日（米国特許公開番号第2005/0271279号として公開）、および米国特許出願番号第11/869435号、発明の名称「Human Pose Estimation and Tracking Using Label Assignment」、出願日２００７年１０月９日に記載されるような、対象２５２の特定の部位を表す画像画素のモーション追跡やクラスタ抽出などを行う。なお、前記文献に記載されるすべての内容をここに引用する。サイン認識については、画像前処理モジュール２２４は、図４を参照しつつ後述するように、処理作業の中でも特に、両手を表す画像画素のクラスタの抽出、両手のひらの検出、およびリンク構造の生成の処理を行う。
【００３１】
形状マッチングモジュール２２６は画像前処理モジュール２２４に接続しており、リンク構造と両手のひらの位置に関する情報を受信する。形状マッチングモジュール２２６は、リンク構造のどのセグメントをどちらの手に割り当てるべきかを決定し、この決定した手の形状と記憶している手形状とをマッチングさせて、対象２５２が示す手形状を決定する。リンク構造のどのセグメントをどちらの手に割り当てるべきかを決定すれば、どの画像画素をどちらの手に割り当てるべきかを決定することができる。一実施形態では、画像画素を隣接のセグメントと同じ手に割り当てる。
【００３２】
図３（ａ）および（ｂ）は、本発明の実施形態に係る形状マッチングモジュール２２６のブロック図を示している。図３（ａ）に示す実施形態では、形状マッチングモジュール２２６Ａは、オーバーラップ手形状検出モジュール３１６と、非オーバーラップ手形状マッチングモジュール３２０と、制約条件付最適化モジュール３４０と、形状データベース３５０とを備える。オーバーラップ手形状検出モジュール３１６は、手が重なり合ったり隣接していることを示す画像画素が奥行画像２１２に含まれているか否かを決定する。
【００３３】
オーバーラップ手形状検出モジュール３１６は、奥行画像の手が重なり合ったり隣接していないと決定した場合には、非オーバーラップ手形状マッチングモジュール３２０を用いて、例えば、米国特許出願番号第11/129164号、発明の名称「Sign Based Human-Machine Interaction」（米国特許公開番号第2005/0271279号）に開示されるような方法で手サインを認識する。一方、奥行画像２１２の手が重なり合ったり隣接していると決定した場合には、図８ないし図１０を参照しつつ詳細に後述するように、制約条件付最適化モジュール３４０を用いて手形状を決定するとともに、手形状が示すサインを決定する。
【００３４】
例えば、米国特許出願第11/129164号、発明の名称「Sign Based Human-Machine Interaction」（米国特許公開番号第2005/0271279号）に開示されるように、形状データベース３５０には、非オーバーラップ手形状マッチングモジュール３２０あるいは制約条件付最適化モジュール３４０で決定した手形状とマッチングさせるための手形状のプロファイルが記憶されている。なお、前記文献に記載されるすべての内容をここに引用する。
【００３５】
図３（ｂ）の実施形態は、制約条件付最適化モジュール３４０の代わりにツリー検索モジュール３４４を用いる点を除いて、実質的に図３（ａ）の実施形態と同じである。図３（ｂ）のオーバーラップ手形状検出モジュール３１６の機能と、非オーバーラップ手形状マッチングモジュール３２０の機能と、形状データベース３５０の機能は、本質的に図３（ａ）の実施形態と同じである。しかしながら、図３（ｂ）の実施形態のツリー検索モジュール３４４は、非循環有向グラフを用いて、図９ないし図１１を参照しつつ詳細に後述するような方法で手形状を決定する。図３（ａ）および（ｂ）の形状マッチングモジュール２２６Ａおよび２２６Ｂは、以下においては、まとめて形状マッチングモジュール２２６と呼ぶ。
【００３６】
手サイン認識方法
図４は、本発明の一実施形態に係る手サイン認識方法のフローチャートを示している。まず、画像前処理モジュール２２４は奥行画像２１２から両手を表す画像画素のクラスタを抽出する（Ｓ４１０）。両手を表す画像画素のクラスタを決定するには、例えば、米国特許出願番号第11/869435号、発明の名称「Human Pose Estimation and Tracking Using Label Assignment」、出願日２００７年１０月９日に開示されるように、奥行画像および色画像の一部分を、対象の異なる部位に分類し、ラベリングすることで決定できる。なお、前記文献に記載されるすべての内容をここに引用する。次に、画像前処理モジュール２２４は、抽出した画像画素のクラスタに重なり合ったり隣接する両手が含まれているか否かを決定する（Ｓ４２０）。
【００３７】
画像画素のクラスタに含まれる手が重なり合っていたり隣接していると決定した場合には、図５および図６を参照しつつ詳細に後述するように、前処理モジュール２２４は両手のひらを検出する。続いて、前処理モジュール２２４は、例えば、手を表す画像画素のクラスタについて中間軸変換（medial axis transform）を行い、リンク構造（図７Ｃを参照）を生成する（Ｓ４４０）。一実施形態においては、中間軸変換は、クラスタに細線化処理を施こすことで実行する。前処理モジュール２２４で生成したリンク構造は、画像画素のクラスタのスケルトンを近似化したものである。
【００３８】
次に、形状マッチングモジュール２２６は、制約条件付最適化もしくはツリー検索を行って、図８および図１０を参照しつつ詳細に後述するように、手形状の曖昧さを解像する（Ｓ４５０）。手の形状の曖昧さを、リンク構造もしくはノードのセグメントを片方の手かもう片方の手に割り当てることで解像する。
【００３９】
制約条件付最適化法あるいはツリー検索法を用いて、リンク構造またはノードのセグメントをどちらかの手に割り当てた後、例えば、米国特許出願番号第11/129164号、発明の名称「Sign Based Human-Machine Interaction」、出願日２００５年５月１２日（米国特許公開番号第2005/0271279号）に開示されるように、形状マッチングモジュール２２６において、Ｓ４５０で解像した手形状を、形状データベース３５０に記憶している手形状プロファイルにマッチングさせる（Ｓ４６０）。なお、前記文献に記載されるすべての内容をここに引用する。形状マッチングモジュール２２６は、奥行画像２１２の手形状を、記憶している手形状プロファイルにマッチングさせることで、特定した手サイン２４０を出力する（Ｓ４７０）。
【００４０】
Ｓ４２０において、奥行画像２１２に重なり合ったり隣接する手が含まれないと決定した場合は、処理をＳ４８０に進めて、例えば、米国特許出願番号第11/129164号、発明の名称「Sign Based Human-Machine Interaction」、出願日  ２００５年５月１２日（米国特許公開番号第2005/0271279号）に開示されるような、距離マッチングやスケルトンマッチングなどの技法を用いて、奥行画像２１２の手形状を決定する。なお、前記文献に記載されるすべての内容をここに引用する。次に、処理をＳ４７０に進めて、特定した手サインを出力して処理を終了する。
【００４１】
手のひら検出
図５は、本発明の一実施形態に係る手のひらを検出する方法に関するフローチャートを示している。ツリー検索法および制約条件付最適化法の精度は、手のひらの検出の正確さに左右されるため、手のひらの位置の決定は非常に重要である。ツリー検索法と制約条件付最適化法のどちらも、セグメントを片方の手またはもう片方の手に分類する（これにより画像画素を分類する）際には、手のひらまでの相対的な距離やセグメントが手のひらにリンクしているか否かの判断に一部基づいて行う。したがって、手のひらの位置の検出が正確でないならば、セグメントを手に分類するときの精度が低下してしまう。
【００４２】
まず、従来の方法を用いて、手を表す（場合によっては前腕の一部も含む）画像画素のクラスタ６００のスケルトンを生成する（Ｓ５２０）。図６を参照しつつ、画像画素のクラスタ６００のスケルトンを表す線６３０を描く。次に、線６３０（つまりスケルトン）と直交するクラスタの幅を測定する（Ｓ５３０）。クラスタの幅は、線６３０と直交する線が手の輪郭線６０４と交わる点どうしの距離を測定することで決定する。図６は、クラスタ６００の幅は、線６３０に沿って移動するときに直交する線（例えば、線６１０、６２０、６４０、６５０）を用いて測定する事例を示している。極大値となる長さ（クラスタの幅）を有する直交する線（線６１０、６２０、６４０、６５０）を、手のひらの中央部を含んでいる可能性のある線の候補として多数選択する。
【００４３】
図５に戻って、閾値よりも長さが短い線の候補を捨てる（Ｓ５５０）。長さの短い線の候補は、手のひらではなく指を表している可能性が高いため候補から外す。例えば、図６の線６１０および６２０はこの段階で捨てる。
【００４４】
残りの線の候補（例えば線６４０と６５０）の中で、指に最も近い候補である線６４０を手のひらの中央部を含んでいる線として選択する（Ｓ５６０）。一実施形態では、指の検出は、線周辺のクラスタが、同じスケルトン中の他の線のクラスタよりも幅細であるような線から検出する。手のひらの中央部を含んでいる線として、線６４０を選択すると、手のひらの中央部として、線６４０の中央部を決定する（Ｓ５７０）。一実施形態では、手のひらの形状は、半径または軸の最大値がクラスタ内に収まるような円や楕円を選択して決定する。
【００４５】
リンク構造の事例
図７（ａ）は、本発明の一実施形態に係るサイン認識システム２００でこれから処理しようとするサインを含んだ奥行画像を例示したものである。
図７（ａ）は、日本手話（ＪＳＮ）の「Ｂ」という文字を表している対象の画像から抽出した奥行画像である。図７（ａ）の奥行画像に含まれる、対象の画像の背景とその他の物品は画像前処理モジュール２２４で削除している。
【００４６】
図７（ｂ）は、本発明の一実施形態に係る図７（ａ）の奥行画像から生成したスケルトン構造を例示したものである。
右の手のひら７１０と左の手のひら７２０を、例えば、図５および図６を参照しつつ説明したような方法で検出する。図７（ｂ）のスケルトン構造は、複数のセグメントに区分する前の状態である。
図７（ｂ）のスケルトン構造には、手の特徴になり得ないような短い断片（例えば、ぶら下がり線７３０）を含んでいる可能性がある。このような短い断片は、デジタル画像中のノイズとなったり、あるいは画像処理中に発生するアーチファクトとなることが多い。
【００４７】
図７（ｃ）は、本発明の一実施形態に係る、図７（ｂ）から生成したリンク構造７００を例示している。リンク構造７００は、複数のノードでセグメント（Ｓ０−Ｓ８）に区分化されている点で、スケルトン構造とは異なる。
リンク構造７００には、図７（ｂ）のぶら下がり線７３０のような短い断片は含まれない。リンク構造７００を生成するために、スケルトン構造を次のようなノードで区分するようにしてもよい：
（ｉ）３本以上の線が集まる分岐ノード
このようなノードは、指が始まる、隣接する、終端となるような点である可能性が高い。
（ｉｉ）線の角度が急に変化するような点（例えば、図７（ｂ）の点７４０）
このような点では手の指やその他の部位と交差する可能性が高い。
（ｉｉｉ）所定の閾値よりも長い線の途中で最大曲率の変化が発生するような点（例えば、図７（ｃ）の点７３４）
手のセグメントであれば、このような閾値を超える長さを有する可能性は低い。
【００４８】
制約条件付最適化法
図８は、本発明の一実施形態に係る、制約条件付最適化法を用いてリンク構造のセグメントをグループ化する方法を例示したものである。
制約条件付最適化モジュール３４０は、まず、リンク構造のセグメントを、右手と左手に分類するためのコスト関数を生成する。一実施形態では、次のようなコスト関数Q(f)を用いる。
【００４９】
【数１】
2011501316.tif 000003
【００５０】
ここで、Nはリンク構造中のセグメントの合計数であり、Mは手の数（つまりM = 2）、c(i, j)はセグメント si を手 j （j = 1 は左手、j = 2 は右手、またはその反対）に割り当てる費用を表し、Aijはセグメント si が右手と左手のどちらに割り当てられているかを表す（下の表１に示す関連表の中に記載されるように）０または１の値を有するパラメータを表し、we は隣接する２つのセグメント間の奥行差を表す重みを表し、Ze はセグメント分類の問題をラベル付与問題に変換するために導入されるパラメータである。最適化処理の全体の目的は、コスト関数 Q(f) を最小化するAij のセットを見つけることである。
【００５１】
式（１）の重み we は、セグメント si (i = 1,2,…,N) 間の関係の強さを表す。互いに隣接するセグメントどうしは強い関係を有し、同じラベル付部位に分類される可能性が高い。このような強い関係はより高い重み we で表される。対照的に、互いに隣接しないセグメントどうしは弱い関係を有する。このように弱い関係はより低い重み we で表される。重み we に関連するパラメータ Zeは、セグメント分類の問題を、線形計画法による最適化問題の形式のラベル付与問題に変換するために導かれるものである。
【００５２】
【表１】
2011501316.tif 000004
【００５３】
一実施形態では、Q(f) を最小化する問題は次の制約条件に左右される。
【００５４】
【数２】
2011501316.tif 000005
【００５５】
式（２）は、周辺に幅の狭いクラスタ群を有するセグメントには指が１本のみ含まれる、という制約条件を表している。したがって、このようなセグメントは右手または左手に分類することはできるが、両手に分類することはできない。
式（３）は、幅の広い複数のクラスタを有するセグメントには２本の指が含まれる、という制約条件を表している。したがって、このようなセグメントは、左手、右手あるいは両手に分類することができる。
【００５６】
式（４）ないし式（６）（Zej は絶対値 |Apj-Aqj| を表す）は、隣接するセグメントどうしは、同じラベル付け部位または隣接のラベル付け部位に分類されなければならない、という制約条件から導かれたものである。式（７）は、前記の通り、Aij は０か１である、という制約条約を表す。式（８）と式（９）は、右手または左手の指の長さの合計は最大値を越えてはならない、という制約条件を表す。
【００５７】
式（１）ないし式（９）で示される最適化問題は、ＮＰ困難と呼ばれる整数計画（integer program）である。一実施形態では、Aij を非整数値にすることで、最適化問題を線形計画法に簡略化することができる。このような簡略化を用いることで、式（１）ないし式（９）で表される最適化問題は、一般に入手可能なソフトウェアライブラリ、例えば、 lp_solve 5.5.0.10（http://lpsolve.sourceforge.net/5.5/ 等で入手可能）を使って効果的に解くことができる。
【００５８】
一実施形態では、式（１）の重み we を無視（weをゼロに設定）し、その代わりに、指が鋭角度に曲げられる場合を排除する制約条件を追加する。このような制約条件は、例えば、閾値（例えば、１６０度）未満の角度で交差するような隣接するセグメント Sa および Sb （ここで、1 ≦ a ≦ N および 1 ≦ b ≦ N）を求めるための下のような式（１０）および式（１１）で表すことができる。式（１０）および式（１１）は、セグメント Sa と Sb とはそれぞれ異なる手に分類されなければならないことを示している。
【００５９】
【数３】
2011501316.tif 000006
【００６０】
式（２）、（３）、（５）ないし（１１）で表される制約条件下で、重み we がゼロに設定された式（１）の最小化問題を解くために、一般に入手可能なソフトウェアライブラリ、例えば、 lp_solve 5.5.0.10を用いてもよい。
【００６１】
一実施形態では、すべてのセグメントを右手または左手、もしくは両手に割り当てた後に、奥行画像２１２の画像画素を、隣接のセグメントが割りあてられている手と同じ手に割り当てる。
【００６２】
ツリー検索法
図９は、本発明の一実施形態に係る、ツリー検索法を用いてリンク構造のセグメントを２本の手に分類する方法に関するフローチャートである。まず、従来の方法を用いて、リンク構造７００から非循環有向グラフを生成する（Ｓ９２０）。図１１は、図７（ｃ）のリンク構造から生成した非循環有向グラフ１１００をツリーの形態で構成したもの（よって、この方法を「ツリー検索法」と呼ぶ）を示す。
【００６３】
図１１に示す非循環有向グラフ１１００の例では、非循環有向グラフのトップノード８は、右の手のひら７１０に最も近いセグメントＳ８（図７（ｃ）を参照）から始まって、左の手のひら７２０に向けて処理が進むにしたがって、連結するセグメントへ次々と広がっていく。非循環有向グラフ１１００の矢印はノード間の連結関係を示す。なお、非循環有向グラフ１１００は、代替の方法を用いて生成してもよい。
【００６４】
再び図９を参照しつつ、非循環有向グラフ１１００を生成した後は、図１０を参照しつつ詳細に後述する通りに、右手の手形状と左手の手形状の候補を生成する（Ｓ９３０）。
【００６５】
１つ以上の基準を用いて、これらの手形状の候補を評価する（Ｓ９４０）。一実施形態では、各基準についてスコアを計算し、これらスコアを足して、手形状の候補を評価する。手形状の候補を評価するための基準には、例えば、以下のようなものが含まれる：（ｉ）手は物理的にリンクする物体であることから、左手と右手のノードがリンクするような手形状の候補には高いスコアを付与し、（ｉｉ）指は手のひらの近くにあることから、手のノードが、この手のひらから所定の距離内に位置するような手形状の候補には高いスコアを付与し、（ｉｉｉ）指を鋭角に曲げることはあまりないため、セグメントどうしの角度が鋭角であるような手形状の候補には低いスコアを付与し、（ｉｖ）分岐するセグメントが指から始まることはあまりない（通常、分岐するセグメントは、複数の指が連結する手のひらから始まる）ため、分岐するノードが、この分岐するノードが割り当てられた手のひらから離れた位置にあるような手形状の候補には低いスコアを付与する。基準（ｉ）ないし（ｉｖ）までのスコアを算出し、これらのスコアを足して合計スコアを求める。なお、これらの基準は限定的、包括的なものではなく、異なる基準を用いて両手形状の候補を評価するようにしてもよい。
【００６６】
最もスコアの高い手形状の候補を、最も可能性の高い手形状として選択する。異なる基準を表す異なるスコアに対しては、異なる重みを付与するようにすることで、異なる基準を組み合わせた場合にも正確な評価を行えるようにしてもよい。
【００６７】
図１０は、本発明の一実施形態に係る、左手と右手の手形状の候補を生成するフローチャートを示している。可能と思われる手形状の候補をすべて生成して、手形状の候補をすべてを評価することは可能であるが、ノードとセグメントで表される手の物理的構造を考慮すれば、手形状によっては実際には不可能なものもあるため、こうしたやり方は、演算コストが高くなり非効率的である。したがって、本発明の一実施形態では、図９のステップＳ９４０でさらに評価するために、ノードどうしの特定の連結関係を満たすような手形状の候補のみを生成する。
【００６８】
本実施形態では、図１１に例示される非循環有向グラフ１１００を生成した後、top-to-bottom検索（top-to-bottom search）を行って、どちらかの手（例えば、右手）に割り当てるためのノードの組み合わせを生成する（Ｓ１０２０）。具体的には、非循環有向グラフ１１００のトップノード８から始まって、右手について４組のノードの組み合わせ方が可能であることが分かる：（ｉ）ノード８のみが右手に属する（ノード８以外のノードは左手に割り当てる）第１の手形状の候補、（ｉｉ）ノード６から分岐する枝に含まれるノードのすべてまたは一部を右手に分類する、多数の手形状の候補、（ｉｉｉ）ノード３から分岐する枝に含まれるノードのすべてまたは一部を右手に分類するような、多数の手形状の候補、（ｉｖ）（ノード３から分岐する枝とノード６から分岐する枝の）両方の枝に含まれるノードのすべてまたは一部を右手に分類するような、多数の手形状の候補。ノード８、６、３を含んでいることに基づいて手形状の候補を決定した後、処理を次の段階へ進めて、ノード８のときと同じ方法で、これらの手形状の候補がノード０、５および２を含んでいるか否かを決定する。同様に、これらの手形状の候補がノード７、４および１を含んでいるか否かについても決定する。
【００６９】
右手の手形状の候補に含まれると決定したノードどうしを連結して、右手の手形状の候補をすべて生成する（Ｓ１０３０）。次に、どちらかの手（例えば、右手）の手形状の候補の各々について、非循環有向グラフ１１００のノードからこの（右手の）手形状の候補のノードを削除して、反対側（左手）の手形状の候補のノードを決定する（Ｓ１０４０）。続いて、反対側の手形状の候補の中にあるノードを連結して、左手の手形状の候補を生成する（Ｓ１０５０）。例えば、右手の手形状の候補にノード８、６、０、７が含まれる場合は、反対側の左手の手形状の候補にはノード１ないし５が含まれる。この場合の事例では、ノード８、６、０、７を連結して右手の手形状の候補を生成し、ノード１ないし５を連結して左手の手形状の候補を生成する。
【００７０】
非循環有向グラフ１１００から、右手の連結関係を満たすような右手の手形状と左手の手形状との組み合わせをすべて生成した後、図９を参照して説明したような基準ごとにスコア付けを行って、各手形状の組み合わせを評価をする。
【００７１】
実験結果
図１２は、本発明の各種実施形態に係る、両手に割り当てた画像画素の事例を示したものである。具体的には、図１２の事例は、制約条件付最適法を用いて正確に特定した、日本手話（ＪＳＬ）のアルファベット文字のＡ、アルファベット文字のＫ、アルファベット文字のＧ、アルファベット文字のＢ、アルファベット文字のＸ、単語の「井戸」、単語の「会う」、単語の「手紙」を例示している。図１２の各画像中の円は、図５を参照して詳述した方法を用いて検出した両手のひらを表している。
【００７２】
ここでの実験では、サイン認識システムは、２．１３ＧＨｚペンティアム（登録商標）プロセッサで動作するプロセッサと２ギガバイトのＲＡＭを備えたラップトップ型コンピュータにより具現化した。かかるハードウェア構成のサイン認識システムは、約０．５秒のサインを正確に識別できた。このように認識時間が俊敏であることは、本発明の実施形態に係る手形状マッチングモジュールは演算コストが安価であり、サイン認識処理全体にかかる演算費用を最小化できることを意味する。
【００７３】
代替の実施形態
一実施形態では、サイン認識システムは、例えば、米国特許出願番号第11/129164号、発明の名称「Sign Based Human-Machine Interaction」、出願日：２００５年５月１２日（米国特許公開番号第2005/0271279号）に開示されるような、手の軌道を追跡するためのジェスチャマッチングモジュールをさらに備える。なお、前記文献に記載されるすべての内容をここに引用する。このジェスチャマッチングモジュールを、本発明の各種実施形態に係る形状マッチングモジュールに対応させて、重なり合ったり隣接する手の動きを追跡するようにしてもよい。
【００７４】
一実施形態では、手形状の識別の精度を向上させるために、色画像データを用いてもよい。奥行画像だけを用いて正確に識別するのが困難な場合には、色画像データから取得した色と形状を用いて、手形状の曖昧さを解像するようにしてもよい。色画像データを用いる場合は、さらに基準や制約条件を追加するようにしてもよい。
【００７５】
一実施形態では、形状マッチングモジュール２２６は、制約条件最適化モジュールとツリー検索モジュールの両方を備えるようにしてもよい。形状マッチングモジュール２２６は、異なる状況であっても、より正確な結果が得られるように２つの方法（制約条件最適化法とツリー検索法）に関する情報を備えるようにして、状況に応じて制約条件最適化モジュールとツリー検索モジュールのいずれかを用いるようにしてもよい。別の実施形態では、制約条件最適化モジュールとツリー検索モジュールのそれぞれで予備的な識別サインを生成し、さらに、形状マッチングモジュール２２６で解析・選択の処理を行ってから、最終的な識別サインを生成するようにしてもよい。
【００７６】
本発明の特定の実施形態および応用例について例示し、説明したが、本発明は、ここに開示される構造や構成部品に厳密に限定されるものではなく、本発明の方法と装置の配置構成、動作および詳細について、付属の特許請求の範囲に定義されるような本発明の趣旨および範囲から逸脱しない限りにおいて各種の修正、変更、変形例が可能である。
【図１】
2011501316.tif 000007
【図２】
2011501316.tif 000008
【図３】
2011501316.tif 000009
【図４】
2011501316.tif 000010
【図５】
2011501316.tif 000011
【図６】
2011501316.tif 000012
【図７】
2011501316.tif 000013
【図８】
2011501316.tif 000014
【図９】
2011501316.tif 000015
【図１０】
2011501316.tif 000016
【図１１】
2011501316.tif 000017
【図１２】
2011501316.tif 000018
【国際調査報告】
2011501316.tif 000019