Sketch-based password authentication

• US 8,024,775 B2
• Filed: 02/20/2008
• Issued: 09/20/2011
• Est. Priority Date: 02/20/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xu, Ying-Qing, Wen, Fang, Oka, Mizuki
• Primary Examiner(s): EL HADY, NABIL M
• Application Number:
  US12/034,254
• Publication Number:
  US 20090210939A1
• Time in Patent Office: 1,308 Days
• Field of Search: 726/16, 726/21, 726/2, 726 17- 20, 713182-186
• US Class Current: 726/2
• 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 a preliminary edge orientation pattern that fits in a first dimension from an input sketch of a user, the preliminary edge orientation pattern including a set of quantized orientation patterns;

obtaining an input edge orientation pattern by scaling the preliminary orientation pattern that fits in the first dimension to fit into a second dimension that is smaller than the first dimension by blurring, the scaling reducing a corresponding size of each quantized orientation pattern;

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,

wherein a size of the second dimension is selected to achieve a desired balance between a false acceptance rate and a false rejection rate of authentication, and wherein extracting the preliminary edge orientation pattern comprises;

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

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

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

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 that includes one or more pixels, each pixel of the scalar pattern having an amplitude value.

5. The method as cited in claim 1, wherein a quantity of the quantized orientation patterns in the set corresponds to a number of quantized orientations.

6. The method as recited in claim 1, wherein each quantized orientation pattern is a scalar pattern for one of R quantized orientations, where R≧

2 is an integer.

7. The method as recited in claim 6, wherein R is selected to achieve a desired balance between a false acceptance rate and a false rejection rate of authentication.

8. The method as recited in claim 1, wherein a number of strokes in the input sketch is selected to achieve a desired balance between a false acceptance rate and a false rejection rate of authentication.

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

10. The method as recited in claim 1, further comprising updating the template edge orientation pattern based on the input sketch of the user.

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

12. A method for authentication, comprising:

extracting a corresponding initial edge orientation pattern for each of multiple initial sketches of an image produced by user;

averaging the initial edge orientation patterns to obtain a template edge orientation pattern;

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;

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

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

suggesting an alternative image for obtaining at least on corresponding additional sketch from the user if the false acceptance rate and false rejection rate is unsatisfactory according to a predefined standard,

wherein extracting the input edge orientation pattern comprises;

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

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

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

13. The method as recited in claim 12, 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.

14. The method as recited in claim 13, wherein each quantized orientation pattern comprises a scalar pattern of one of a plurality of quantized orientations that includes one or more pixels, each pixel of the scalar pattern having an amplitude value.

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

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

quantizing the gradient orientation to r th 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 input edge orientation pattern from the reduced orientation pattern.

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

determine a number of quantized orientations for generating quantized orientation patterns that achieve a desired balance between a false acceptance rate and a false rejection rate for an input sketch-based user authentication;

extract an input edge orientation pattern from an input sketch of a user, the input edge orientation pattern including a set of quantized orientation patterns that corresponds to the number of quantized orientations;

measure an edge orientation similarity between input edge orientation pattern and a template edge orientation pattern having a set of template quantized orientation patterns that corresponds to the number of quantized orientations; and

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

wherein extracting the input edge orientation pattern comprises;

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

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

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