SKETCH-BASED PASSWORD AUTHENTICATION

• US 20090210939A1
• Filed: 02/20/2008
• Published: 08/20/2009
• Est. Priority Date: 02/20/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wen, Fang, Xu, Ying-Qing, Oka, Mizuki
• Granted Patent: US 8,024,775 B2
• Time in Patent Office: Days
• US Class Current: 726/19
• CPC Class Codes: G06F 21/36 by graphic or iconic representation
• CPC Class Codes: G06V 40/30 Writer recognition; Reading and verifying signatures

Abstract

A graphical password authentication method is based on sketches drawn by user. The method extracts a template edge orientation pattern from an initial sketch of the user and an input edge orientation pattern from an input sketch of the user, compares the similarity between the two edge orientation patterns, and makes an authentication decision based on the similarity. The edge orientations are quantized, and each edge orientation pattern includes a set of quantized orientation patterns each corresponding to one of the quantized edge orientations. The number of quantized edge orientations, as well as other parameters such as the dimension of the final orientation patterns and acceptance threshold, can be optimized either globally or user-specifically.

Claims

1. A method for authentication, comprising:

extracting an input edge orientation pattern from an input sketch of a user;

measuring an edge orientation similarity between the input edge orientation pattern and a template edge orientation pattern; and

making an authentication decision at least partially based on the edge orientation similarity.

2. The method as recited in claim 1, wherein the template edge orientation pattern is extracted from at least one initial sketch of the user.

3. The method as recited in claim 1, wherein the template edge orientation pattern includes a set of quantized orientation patterns.

4. The method as recited in claim 3, wherein each quantized orientation pattern comprises a scalar pattern of one of a plurality of quantized orientations, each pixel of the scalar pattern having an amplitude value.

5. The method as cited in claim 1, wherein extracting the input edge orientation pattern comprises extracting a set of quantized orientation patterns.

6. The method as recited in claim 1, wherein extracting the input edge orientation pattern comprises extracting a set of quantized orientation patterns, each quantized orientation pattern having a scalar pattern of one of R quantized orientations, where R≧

2 is an integer.

7. The method as recited in claim 6, wherein R is optimized for a balance between minimizing false acceptance rate and minimizing false rejection rate of authentication.

8. The method as recited in claim 1, wherein extracting the input edge orientation pattern comprises:

obtaining a preliminary orientation pattern of a first dimension;

obtaining a reduced orientation pattern by reducing the preliminary orientation pattern from the first dimension to a second dimension; and

computing the input edge orientation pattern from the reduced orientation pattern.

9. The method as recited in claim 8, wherein the second dimension is optimized for a balance between minimizing false acceptance rate and minimizing false rejection rate of authentication.

10. The method as recited in claim 1, wherein the template edge orientation pattern is extracted from a plurality of sketches entered by the user.

11. The method as recited in claim 1, further comprising:

updating the template edge orientation pattern based on the input sketch of the user.

12. The method as recited in claim 1, wherein extracting the input edge orientation pattern comprises:

computing a gradient orientation of image intensity in the input sketch; and

quantizing the gradient orientation to rth orientation out of R number of quantized orientations, where r=1, 2, . . . , R; and

computing the input edge orientation pattern from the quantized gradient orientation.

13. The method as recited in claim 1, the method being implemented on a computing device for authenticating user logon.

14. A method for authentication, comprising:

extracting a template edge orientation pattern from at least partially an initial sketch of a user;

receiving an input sketch from the user entered for authentication;

extracting an input edge orientation pattern of the input sketch;

measuring an edge orientation similarity between input edge orientation pattern and a template edge orientation pattern; and

making an authentication decision at least partially based on the edge orientation similarity.

15. The method as recited in claim 14, wherein the template edge orientation pattern comprises a first set of quantized orientation patterns, and the input edge orientation pattern comprises a second set of quantized orientation patterns.

16. The method as recited in claim 15, wherein each quantized orientation pattern comprises a scalar pattern of one of a plurality of quantized orientations, each pixel of the scalar pattern having an amplitude value.

17. The method as recited in claim 14, further comprising:

estimating a false acceptance rate and false rejection rate of the template edge orientation pattern based on the initial sketch of the user; and

suggesting an alternative initial sketch if the false acceptance rate and false rejection rate is unsatisfactory according to a predefined standard.

18. The method as recited in claim 14, wherein extracting the input edge orientation pattern comprises:

computing a gradient orientation of image intensity in the input sketch;

quantizing the gradient orientation to rth orientation out of R number of quantized orientations, where r=1, 2, . . . , R; and

computing the input edge orientation pattern using the quantized gradient orientation.

19. The method as recited in claim 18, wherein extracting the template edge orientation pattern comprises:

computing a gradient orientation of image intensity in the initial sketch;

quantizing the gradient orientation to rth orientation out of R number of quantized orientations, where r=1, 2, . . . , R;

obtaining a preliminary orientation pattern using the quantized gradient orientation;

obtaining a reduced orientation pattern by reducing the preliminary orientation pattern from a first dimension to a second dimension; and

computing the template edge orientation pattern from the reduced orientation pattern.

20. One or more computer readable media having stored thereupon a plurality of instructions that, when executed by a processor, causes the processor to:

extract an input edge orientation pattern from an input sketch of a user;

measure an edge orientation similarity between input edge orientation pattern and a template edge orientation pattern; and

make an authentication decision at least partially based on the edge orientation similarity.