Grid-based data input and authentication

• US 8,036,433 B1
• Filed: 04/01/2004
• Issued: 10/11/2011
• Est. Priority Date: 04/01/2004
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Wolff, Gregory J.
• Primary Examiner(s): Mariam; Daniel
• Assistant Examiner(s): Rice; Elisa
• Application Number:
  US10/817,242
• Time in Patent Office: 2,749 Days
• Field of Search: None
• US Class Current: 382/119
• CPC Class Codes: G06V 40/376 Acquisition

Abstract

A system and method for authenticating user-input signatures or other data. A user draws a pattern on an input pad, using for example a pen, stylus, or finger. A grid, including a set of edges, is displayed on the input pad to help the user in drawing in the correct position on the pad. An input processor detects the edges crossed by the user in drawing the pattern. The sequence of edge crossings are converted into a symbolic sequence that can be output, authenticated, compared with previously stored symbolic sequences, or otherwise processed. Additional information, such as edge crossing timing, pen path, and the like, are optionally made available for further authentication.

Claims

1. A method for data entry and authentication, the method comprising:

receiving, with an input device, user input representing a pattern drawn over one or more of a plurality of edges;

detecting, with a processor, edge crossings within the pattern, one of the detected edge crossings specifying an identified point;

mapping, with the processor the plurality of edges to a plurality of symbolic representations, each edge having a unique symbolic representation that includes at least one character, with a relative mapping using the identified point as an origin for the relative mapping; and

generating, with the processor, a symbolic sequence from the detected edge crossings based on the mappings between the edges and the symbolic representations.

2. The method of claim 1, wherein the symbolic sequence comprises a representation of a series of detected edge crossings.

3. The method of claim 1, wherein the symbolic sequence comprises a representation of a series of detected edge crossings and of the direction of each edge crossing.

4. The method of claim 1, wherein the user input comprises a signature.

5. The method of claim 1, wherein the received user input comprises pen-based input.

6. The method of claim 1, further comprising displaying the plurality of edges.

7. The method of claim 1, wherein receiving user input comprises detecting pen-based input on an input pad.

8. The method of claim 1, further comprising providing user feedback by, responsive to the received user input, highlighting crossed edges.

9. The method of claim 1, wherein receiving user input comprises detecting input on a touch-sensitive pad.

10. The method of claim 1, further comprising outputting the generated symbolic sequence.

11. The method of claim 1, further comprising authenticating the generated symbolic sequence.

12. The method of claim 11, wherein authenticating the generated symbolic sequence comprises comparing the generated symbolic sequence with a previously stored symbolic sequence.

13. The method of claim 1, wherein the symbolic sequence comprises a string of alphanumeric characters.

14. The method of claim 13, further comprising:

receiving user input modifying the string; and

storing the modified user string.

15. The method of claim 14, further comprising:

associating the modified user string with a representation of the pattern.

16. The method of claim 1, wherein the plurality of edges forms a grid.

17. The method of claim 16, wherein the mappings between the edges and the symbolic representations are based on the positions of the edges within the grid.

18. The method of claim 1, wherein the plurality of edges forms a grid of squares.

19. The method of claim 1, wherein the plurality of edges forms a grid of rectangles.

20. The method of claim 1, wherein the pattern comprises a series of lines.

21. The method of claim 1, wherein the pattern represents a user signature.

22. The method of claim 1, wherein the pattern represents at least one alphanumeric character.

23. The method of claim 1, further comprising detecting user input indicating completion of the pattern, wherein generating a symbolic sequence is performed responsive to detecting the user input indicating completion of the pattern.

24. The method of claim 23, wherein the user input indicating completion of the pattern comprises user activation of a button on a screen.

25. The method of claim 1, further comprising detecting no user input over a predetermined period of time, indicating completion of the pattern, wherein generating a symbolic sequence is performed responsive to detecting no user input over the predetermined period of time.

26. The method of claim 1, further comprising detecting deactivation of an input device, indicating completion of the pattern, wherein generating a symbolic sequence is performed responsive to detecting deactivation of the input device.

27. The method of claim 1, further comprising detecting lifting of a stylus, indicating completion of the pattern, wherein generating a symbolic sequence is performed responsive to detecting lifting of the stylus.

28. The method of claim 1, wherein receiving user input comprises receiving input from a pointing device, the method further comprising, responsive to the received user input, displaying the path of the pointing device.

29. The method of claim 1, further comprising, responsive to the received user input, displaying the pattern.

30. The method of claim 1, further comprising storing the generated symbolic sequence.

31. The method of claim 1, further comprising detecting directions for the edge crossings.

32. The method of claim 31, further comprising authenticating the user input by comparing the detected edge crossing directions with previously stored edge crossing directions.

33. The method of claim 31, further comprising authenticating the user input by comparing the generated symbolic representation with a previously stored symbolic representation and by comparing the detected edge crossing directions with previously stored edge crossing directions.

34. The method of claim 1, further comprising detecting time intervals between the edge crossings.

35. The method of claim 34, further comprising authenticating the user input by comparing the detected time intervals with previously stored time intervals.

36. The method of claim 34, further comprising authenticating the user input by comparing the generated symbolic representation with a previously stored symbolic representation and by comparing the detected time intervals with previously stored time intervals.

37. The method of claim 34, further comprising authenticating the user input by performing statistical comparison of the detected time intervals with previously stored time intervals.

38. The method of claim 1, wherein receiving user input comprises receiving user input via a pointing device, the method further comprising detecting a path of the pointing device.

39. The method of claim 38, further comprising authenticating the user input by comparing the detected path with a previously stored path.

40. The method of claim 38, further comprising authenticating the user input by comparing the generated symbolic representation with a previously stored symbolic representation and by comparing the detected path with a previously stored path.

41. The method of claim 38, further comprising authenticating the user input by performing statistical comparison of the detected path with a previously stored path.

42. The method of claim 1, wherein receiving user input comprises receiving user input via a pointing device, the method further comprising detecting at least two selected from the group consisting of:

directions for the edge crossings;

time intervals between the edge crossings; and

path of the pointing device.

43. The method of claim 42, further comprising authenticating the user input by performing a combination of comparisons, the combination of comparisons comprising at least two selected from the group consisting of:

comparing directions for the edge crossings with previously stored edge crossing directions;

comparing time intervals between the edge crossings with previously stored time intervals between edge crossings; and

comparing path of the pointing device with a previously stored path.

44. The method of claim 42, further comprising authenticating the user input by performing a combination of comparisons, the combination of comparisons comprising comparing the generated symbolic representation with a previously stored symbolic representation, the combination of comparisons further comprising at least two selected from the group consisting of:

comparing directions for the edge crossings with previously stored edge crossing directions;

comparing time intervals between the edge crossings with previously stored time intervals between edge crossings; and

comparing path of the pointing device with a previously stored path.

45. The method of claim 38, further comprising authenticating the user input by performing a combination of comparisons, the combination of comparisons comprising at least two selected from the group consisting of:

comparing directions for the edge crossings with previously stored edge crossing directions;

statistical comparison of time intervals between the edge crossings with previously stored time intervals between edge crossings; and

statistical comparison of path of the pointing device with a previously stored path.

46. The method of claim 1, wherein generating a symbolic sequence from the detected edge crossings comprises:

a) comparing an edge sequence of detected edge crossings with entries in a lookup table;

b) identifying a longest matching entry in the lookup table;

c) appending the identified entry to a result string; and

d) responsive to the edge sequence containing data that has not been matched to an entry in the lookup table, repeating steps b) through d) for the data that has not been matched.

47. A computer program product for data entry and authentication comprising a non-transitory computer-readable medium having computer program code for:

receiving user input representing a pattern drawn over one or more of a plurality of edges;

detecting edge crossings within the pattern, one of the detected edge crossings specifying an identified point;

mapping the plurality of edges to a plurality of symbolic representations, each edge having a unique symbolic representation that includes at least one character, with a relative mapping using the identified point as an origin for the relative mapping; and

generating a symbolic sequence from the detected edge crossings, using based on the mappings between the edges and the symbolic representations.

48. The computer program product of claim 47, wherein the symbolic sequence comprises a representation of a series of detected edge crossings.

49. The computer program product of claim 47, wherein the symbolic sequence comprises a representation of a series of detected edge crossings and of the direction of each edge crossing.

50. The computer program product of claim 47, wherein the user input comprises a signature.

51. The computer program product of claim 47, wherein the received user input comprises pen-based input.

52. The computer program product of claim 47, wherein the computer program code for receiving user input comprises computer program code for detecting pen-based input on an input pad.

53. The computer program product of claim 47, further comprising computer program code for providing user feedback by, responsive to the received user input, highlighting crossed edges.

54. The computer program product of claim 47, wherein the computer program code for receiving user input comprises computer program code for detecting input on a touch-sensitive pad.

55. The computer program product of claim 47, further comprising computer program code for outputting the generated symbolic sequence.

56. The computer program product of claim 47, further comprising computer program code for authenticating the generated symbolic sequence.

57. The computer program product of claim 47, wherein the pattern represents a user signature.

58. The computer program product of claim 47, further comprising computer program code for detecting directions for the edge crossings.

59. The computer program product of claim 47, further comprising computer program code for detecting time intervals between the edge crossings.

60. The computer program product of claim 47, wherein the computer program code for receiving user input comprises computer program code for receiving user input via a pointing device, the computer program product further comprising computer program code for detecting a path of the pointing device.

61. The computer program product of claim 47, wherein the computer program code for receiving user input comprises computer program code for receiving user input via a pointing device, the computer program product further comprising computer program code for detecting at least two selected from the group consisting of:

directions for the edge crossings;

time intervals between the edge crossings; and

path of the pointing device.

62. A data entry and authentication system, comprising:

an input device, for receiving user input representing a pattern drawn over one or more of a plurality of edges;

a mapping system for mapping the plurality of edges to a plurality of symbolic representations, each edge having a unique symbolic representation that includes at least one character; and

a processor, coupled to the input device and the mapping system, for detecting edge crossings within the pattern, one of the detected edge crossings specifying an identified point, and generating a symbolic sequence from the detected edge crossings based on the mappings between the edges and the symbolic representations,

the mapping system further configured to map the plurality of edges to the plurality of symbolic representations with a relative mapping using the identified point as an origin for the relative mapping.

63. The system of claim 62, wherein the symbolic sequence comprises a representation of a series of detected edge crossings.

64. The system of claim 62, wherein the symbolic sequence comprises a representation of a series of detected edge crossings and of the direction of each edge crossing.

65. The system of claim 62, wherein the user input comprises a signature.

66. The system of claim 62, wherein the received user input comprises pen-based input.

67. The system of claim 62, further comprising an output device, coupled to the processor, for displaying the plurality of edges.

68. The system of claim 67, wherein the input device and the output device comprise a combined input/output device.

69. The system of claim 62, wherein the input device comprises an input pad for detecting pen-based input.

70. The system of claim 62, further comprising an output device, coupled to the processor, for providing user feedback by, responsive to the received user input, highlighting crossed edges.

71. The system of claim 62, wherein the input device comprises a touch-sensitive pad for receiving user input.

72. The system of claim 62, further comprising an output device, coupled to the processor, for outputting the generated symbolic sequence.

73. The system of claim 62, wherein the processor authenticates the generated symbolic sequence.

74. The system of claim 73, wherein the processor authenticates the generated symbolic sequence by comparing the generated symbolic sequence with a previously stored symbolic sequence.

75. The system of claim 62, wherein the symbolic sequence comprises a string of alphanumeric characters.

76. The system of claim 75, wherein the input device receives user input modifying the string, the system further comprising:

a storage device, coupled to the processor, for storing the modified user string.

77. The system of claim 76, wherein the storage device associates the modified user string with a representation of the pattern.

78. The system of claim 62, wherein the plurality of edges forms a grid.

79. The system of claim 78, wherein the mappings between the edges and the symbolic representations are based on the positions of the edges within the grid.

80. The system of claim 62, wherein the plurality of edges forms a grid of squares.

81. The system of claim 62, wherein the plurality of edges forms a grid of rectangles.

82. The system of claim 62, wherein the pattern comprises a series of lines.

83. The system of claim 62, wherein the pattern represents a user signature.

84. The system of claim 62, wherein the pattern represents at least one alphanumeric character.

85. The system of claim 62, wherein the input device detects user input indicating completion of the pattern, and wherein the processor generates a symbolic sequence is performed responsive to the input device detecting the user input indicating completion of the pattern.

86. The system of claim 62, further comprising a storage device, coupled to the processor, for storing the generated symbolic sequence.

87. The system of claim 62, wherein the processor detects directions for the edge crossings.

88. The system of claim 87, wherein the processor authenticates the user input by comparing the detected edge crossing directions with previously stored edge crossing directions.

89. The system of claim 87, wherein the processor authenticates the user input by comparing the generated symbolic representation with a previously stored symbolic representation and by comparing the detected edge crossing directions with previously stored edge crossing directions.

90. The system of claim 62, wherein the processor detects time intervals between the edge crossings.

91. The system of claim 90, wherein the processor authenticates the user input by comparing the detected time intervals with previously stored time intervals.

92. The system of claim 90, wherein the processor authenticates the user input by comparing the generated symbolic representation with a previously stored symbolic representation and by comparing the detected time intervals with previously stored time intervals.

93. The system of claim 90, wherein the processor authenticates the user input by performing statistical comparison of the detected time intervals with previously stored time intervals.

94. The system of claim 62, wherein the input device comprises a pointing device, and wherein the processor detects at least two selected from the group consisting of:

directions for the edge crossings;

time intervals between the edge crossings; and

path of the pointing device.

95. The system of claim 94, wherein the processor authenticates the user input by performing a combination of comparisons, the combination of comparisons comprising at least two selected from the group consisting of:

comparing directions for the edge crossings with previously stored edge crossing directions;

comparing time intervals between the edge crossings with previously stored time intervals between edge crossings; and

comparing path of the pointing device with a previously stored path.

96. The system of claim 94, wherein the processor authenticates the user input by performing a combination of comparisons, the combination of comparisons comprising comparing the generated symbolic representation with a previously stored symbolic representation, the combination of comparisons further comprising at least two selected from the group consisting of:

comparing directions for the edge crossings with previously stored edge crossing directions;

comparing time intervals between the edge crossings with previously stored time intervals between edge crossings; and

comparing path of the pointing device with a previously stored path.

97. The system of claim 90, wherein the processor authenticates the user input by performing a combination of comparisons, the combination of comparisons comprising at least two selected from the group consisting of:

comparing directions for the edge crossings with previously stored edge crossing directions;

statistical comparison of time intervals between the edge crossings with previously stored time intervals between edge crossings; and

statistical comparison of path of the pointing device with a previously stored path.

98. The system of claim 62, wherein the processor generates a symbolic sequence from the detected edge crossings by:

a) comparing an edge sequence of detected edge crossings with entries in a lookup table;

b) identifying a longest matching entry in the lookup table;

c) appending the identified entry to a result string; and

d) responsive to the edge sequence containing data that has not been matched to an entry in the lookup table, repeating steps b) through d) for the data that has not been matched.