Hand sign recognition using label assignment

• US 8,005,263 B2
• Filed: 10/26/2007
• Issued: 08/23/2011
• Est. Priority Date: 10/26/2007
• Status: Expired due to Fees

• Current Assignee: Honda Motor Co., Ltd. (Honda Motor Company), The Ohio State University Research Foundation
• Original Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Inventors: Xu, Lijie, Fujimura, Kikuo
• Primary Examiner(s): Carter; Aaron W
• Application Number:
  US11/925,557
• Publication Number:
  US 20090110292A1
• Time in Patent Office: 1,397 Days
• Field of Search: 382/103, 382/154, 715/863, 379/52
• US Class Current: 382/103
• CPC Class Codes: G06F 3/017 Gesture based interaction, e.g. based on a set of recognized hand gestures interaction based on gestures traced on a digitiser G06F3/04883
• CPC Class Codes: G06V 20/64 Three-dimensional objects
• CPC Class Codes: G06V 40/107 Static hand or arm

Abstract

A method and system for recognizing hand signs that include overlapping or adjoining hands from a depth image. A linked structure comprising multiple segments is generated from the depth image including overlapping or adjoining hands. The hand pose of the overlapping or adjoining hands is determined using either (i) a constrained optimization process in which a cost function and constraint conditions are used to classify segments of the linked graph to two hands or (ii) a tree search process in which a tree structure including a plurality of nodes is used to obtain the most-likely hand pose represented by the depth image. After determining the hand pose, the segments of the linked structure are matched with stored shapes to determine the sign represented by the depth image.

Claims

1. A computer-based method for recognizing sign language, comprising:

receiving a depth image of a target subject using one or more cameras, the depth image comprising image pixels representing distances between parts of the target subject and the one or more cameras;

classifying the depth image into a first portion representing a first hand of the target subject and a second portion representing a second hand of the target subject responsive to determining that the first hand and the second hand in the depth image overlap or adjoin; and

outputting a sign represented by the first hand and the second hand in the depth image by matching shapes of the first portion and the second portion with stored shapes of hands.

2. The computer-based method of claim 1, further comprising generating a linked structure representing the first hand and the second hand from the depth image, the linked structure comprising two or more segments linked to each other.

3. The computer-based method of claim 2, wherein classifying the depth image comprises:

generating a cost function representing a cost for classifying the two or more segments into the first hand and the second hand; and

determining a hand shape for the first hand and the second hand that minimizes the cost function and satisfies constraint conditions representing characteristics of hands.

4. The computer-based method of claim 3, wherein the constraint conditions comprise:

a first condition that closely located segments are likely to be segments of the same hand;

a second condition that a first segment generated from a first cluster of image pixels includes more than one finger if a first thickness of the first cluster is larger than a threshold;

a third condition that a second segment generated from a second cluster of image pixels include one finger if a second thickness of the second cluster is not larger than the threshold; and

a fourth condition that a total length of segments classified to the first hand or the second hand does not exceed a maximum value.

5. The computer-based method of claim 2, classifying the depth image comprises:

generating a directed acyclic graph structure based on the linked structure, the acyclic graph comprises nodes representing segments and indicates connective relationship between the nodes;

generating combinations of nodes that group a first set of nodes to the first hand and a second set of nodes to the second hand; and

evaluating the combinations of nodes using one or more criteria representing characteristics of hands.

6. The computer-based method of claim 5, evaluating the combinations of the nodes comprises:

obtaining a first score representing linking of a first node to a second node classified to the same hand;

obtaining a second score representing distances between segments and palms of the hands to which the segments are classified;

obtaining a third score representing angles between linked segments classified to the same hand;

obtaining a fourth score representing distances between branching nodes and palms of the hands to which the branching nodes are classified, the branching nodes representing nodes linked to three or more nodes or linked to a palm and two or more nodes; and

determining a combination having a lowest sum of the first score, the second score, the third score, and the fourth score.

7. The computer-based method of claim 1, further comprising detecting palms of the first and the second hands.

8. The computer-based method of claim 7, wherein detecting the first palm or the second palm comprises:

generating a skeleton line based on image pixels representing the first or the second hand;

determining candidate lines for including a center of the first palm or the second palm by obtaining local maximum widths of lines intersecting edges of image pixels outlining the first or the second hand, the lines perpendicular to the skeleton line; and

determining the center of the candidate line that is closest to image pixels representing fingers of the first or the second hand as the center of the palm.

9. The computer-based method of claim 2, wherein generating the linked structure comprises performing thinning operations on the image pixels representing the first hand and the second hand.

10. A computer program product comprising a non-transitory computer readable medium structured to store instructions executable by a processor, the instructions, when executed cause the processor to:

receive a depth image of a target subject using one or more cameras, the depth image comprising image pixels representing distances between parts of the target subject and the one or more cameras;

classify the depth image into a first portion representing a first hand of the target subject and a second portion representing a second hand of the target subject responsive to determining that the first hand and the second hand in the depth image overlap or adjoin; and

output a sign represented by the first hand and the second hand in the depth image by matching shapes of the first portion and the second portion with stored shapes of hands.

11. The computer program product of claim 10, further comprising instructions to generate a linked structure representing the first hand and the second hand from the depth image, the linked structure comprising two or more segments linked to each other.

12. The computer program product of claim 11, wherein instructions to classify the depth image comprise instructions to:

generate a cost function representing a cost for classifying the two or more segments into the first hand and the second hand; and

determine a hand shape for the first hand and the second hand that minimizes the cost function and satisfies constraint conditions representing characteristics of hands.

13. The computer program product of claim 12, wherein the constraint conditions comprise:

a first condition that closely located segments are likely to be segments of the same hand;

a second condition that a first segment generated from a first cluster of image pixels includes more than one finger if a first thickness of the first cluster is larger than a threshold;

a third condition that a second segment generated from a second cluster of image pixels include one finger if a second thickness of the second cluster is not larger than the threshold; and

a fourth condition that a total length of segments classified to the first hand or the second hand does not exceed a maximum value.

14. The computer program product of claim 12, wherein the instructions to classifying the digital images comprise instructions to:

generate a directed acyclic graph structure based on the linked structure, the acyclic graph comprises nodes representing segments and indicates connective relationship between the nodes;

generate combinations of nodes that group a first set of nodes to the first hand and a second set of nodes to the second hand; and

evaluate the combinations of nodes using one or more criteria representing characteristics of hands.

15. The computer program product of claim 14, wherein the instructions to evaluate the combinations of the nodes comprise instructions to:

obtain a first score representing linking of a first node and a second node classified to the same hand;

obtain a second score representing distances between segments and palms of the hands to which the segments are classified;

obtain a third score representing angles between linked segments classified to the same hand;

obtain a fourth score representing distances between branching nodes and palms of the hands to which the branching nodes are classified, the branching nodes representing nodes linked to three or more nodes or linked to a palm and two or more nodes; and

determine a combination having a lowest sum of the first score, the second score, the third score and the fourth score.

16. The computer program product of claim 10, further comprising instruction to detect a first palm of the first hand and a second palm of the second hand.

17. The computer program product of claim 16, wherein instructions to detect the first palm or the second palm comprise instructions to:

generate a skeleton line based on image pixels representing the first or the second hand;

determine candidate lines for including a center of the first palm or the second palm by obtaining local maximum widths of lines intersecting edges of image pixels outlining the first or the second hand, the lines perpendicular to the skeleton line; and

determine the center of the candidate line that is closest to image pixels representing fingers of the first or the second hand as the center of the palm.

18. The computer program product of claim 11, wherein the instructions to generate the linked structure comprise instructions to perform thinning operations on the image pixels representing the first hand and the second hand.

19. A computer-based system for recognizing sign language comprising:

one or more cameras for generating a depth image of a target subject, the depth image comprising image pixels representing distances between parts of the target subject and the one or more cameras;

an image pre-processing module coupled to the one or more camera for classifying the depth image into a first portion representing a first hand of the target subject and a second portion representing a second hand of the target subject responsive to determining that the first hand and the second hand in the depth image overlap or adjoin; and

a shape matching module coupled to the image pre-processing module, the shape matching module outputting a sign represented by the first hand and the second hand in the depth image by matching shapes of the first portion and the second portion with stored shapes of hands.

20. The computer-based system of claim 19, wherein the image pre-processing further generates a linked structure representing the first hand and the second hand from the depth image, the linked structure comprising two or more segments linked to each other.

21. The computer-based system of claim 19, wherein the shape matching module comprises a optimization module for generating a cost function representing a cost for classifying the two or more segments into the first hand and the second hand and for determining a hand shape for the first hand and the second hand that minimize the cost function and satisfies constraint conditions representing characteristics of hands.

22. The computer-based system of claim 21, wherein the constraint conditions comprise:

a first condition that closely located segments are likely to be segments of the same hand;

a second condition that a first segment generated from a first cluster of image pixels includes more than one finger if a first thickness of the first cluster is larger than a threshold;

a third condition that a second segment generated from a second cluster of image pixels include one finger if a second thickness of the second cluster is not larger than the threshold; and

a fourth condition that a total length of segments classified to the first hand or the second hand does not exceed a maximum value.

23. The computer-based system of claim 20, wherein the shape matching module comprises a tree search module that generates a directed acyclic graph structure based on the linked structure, the acyclic graph comprises nodes representing segments and indicates connective relationship between the nodes, generates combinations of nodes that group a first set of nodes to the first hand and a second set of nodes to the second hand, and evaluates the combinations of nodes using one or more criteria representing characteristics of hands.

24. The computer-based system of claim 23, the tree search module evaluates the combinations of the nodes by adding a first score representing linking of a first node to a second node classified to the same hand, a second score representing distances between segments and palms of the hands to which the segment is classified, a third score representing angles between linked segments classified to the same hand, and a fourth score representing distances between branching nodes and palms of the hands to which the branching nodes are classified, the branching nodes representing nodes linked to three or more nodes or linked to a palm and two or more nodes.

25. The computer-based system of claim 19, wherein the image pre-processing module detects a first palm of the first hand and a second palm of the second hand.