System and method for devising a human interactive proof that determines whether a remote client is a human or a computer program

• US 20050065802A1
• Filed: 09/19/2003
• Published: 03/24/2005
• Est. Priority Date: 09/19/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rui, Yong, Liu, Zicheng
• Granted Patent: US 7,725,395 B2
• Time in Patent Office: Days
• US Class Current: 715/764
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A system and method for automatically determining if a remote client is a human or a computer. A set of HIP design guidelines which are important to ensure the security and usability of a HIP system are described. Furthermore, one embodiment of this new HIP system and method is based on human face and facial feature detection. Because human face is the most familiar object to all human users the embodiment of the invention employing a face is possibly the most universal HIP system so far.

Claims

1. A computer-implemented process for determining whether a computer user is a human or a computer program, comprising the process actions of:

generating a human interactive proof employing an image of one or more body parts wherein certain features thereof are at known locations in said image;

requiring a computer user to locate at least one feature of said one or more body parts in the image;

comparing the computer user'"'"'s locations of said at least one feature of said one or more body parts to their actual location in the image; and

determining whether the computer user is a human or a computer program.

2. The computer-implemented process of claim 1 wherein said one or more body parts is a human face.

3. The computer-implemented process of claim 1 wherein said one or more body parts is an entire human body.

4. The computer-implemented process of claim 1 wherein said one or more body parts is an animal.

5. The computer-implemented process of claim 1 wherein said determination of whether a computer user is a human or a computer program is used for one of:

assigning an email account;

validating an input in a poll;

using a search engine;

using a chat room; and

accessing data on a website.

6. The computer-implemented process of claim 1 wherein the process action for generating a human interactive proof employing an image of a human body part wherein certain features are at known locations in said image, comprises one or more of,

inputting a first texture map, T_m, and a generic model of said body part;

generating a confusion texture map, T_c, which distributes features of the body part differently than from the first texture map;

generating a transformation of a pose of said body part using said generic model;

performing local deformations to features of said body part;

generating an image, F_h, with the deformed and transformed mesh with the first texture applied;

generating an image, F_c, with the deformed and transformed mesh with the confusion texture map applied;

generating an image, I₁, with F_c as background and a shrunken F_h as foreground;

generating an image, I₂, by making L copies of the confusion texture map that are scaled down in size and put into I₁ with varying sizes and locations;

generating an image, I₃, by

making a number of copies of F_c and randomly putting these copies of F_c into I₂;

dividing the image into M+1 regions, where M of the regions come from F_c and one region comes from F_h;

calculating the average intensity of the M regions and remapping the intensity of each region such that the average intensities are uniformly distributed across the M+1 regions;

randomly dividing each of the M+1 regions said region into four quadrants and increasing the intensity of some quadrants, while decreasing the intensity of other quadrants; and

generating a final image, I_F, by making N copies of the feature regions in F_h and randomly putting said N copies into I₃ to generate the final test image.

7. The computer-implemented process of claim 1 wherein the process action for determining whether the computer user is a human or a computer program comprises using a comparison of the computer user'"'"'s locations of said at least one feature of said one or more body parts to the location of said features in the image.

8. The computer-implemented process of claim 1 wherein the computer-user-identified feature locations are specified by the user using a computer pointing device.

9. The computer-implemented process of claim 8 wherein the computer pointing device is one of:

a mouse; and

a digital pen.

10. A system for creating a Human Interactive Proof using an image of a face, the system comprising:

a general purpose computing device; and

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

generate a human interactive proof employing an image of a human face wherein certain features are at known locations in said image;

require a computer user to locate certain features of said face in the image;

compare the computer user'"'"'s locations of said features of said face to their actual location in the image; and

determine whether the computer user is a human or a bot.

11. The system of claim 10 wherein the image is automatically synthesized.

12. The system of claim 10 wherein the image is a distorted face embedded in a cluttered background

13. The system of claim 10 wherein the module to determine whether a computer user is a human or a bot determines that the computer user is a human if the computer user'"'"'s locations of said features are within a given distance from their actual location.

14. The system of claim 10 wherein the features of the face comprise the four corners of the eyes and the two corners of the mouth.

15. The system of claim 10 wherein the module for generating a human interactive proof employing an image of a face wherein certain features are at known locations in said image, comprises modules for:

inputting a first texture map, T_m, and a generic model of said face;

generating a confusion texture map, T_c, which distributes features of the face differently than from the first texture map;

generating a transformation of a pose of said face using said generic model;

performing local deformations to features of said face;

generating an image, F_h, with the deformed and transformed mesh with the first texture applied;

generating an image, F_c, with the deformed and transformed mesh with the confusion texture map applied;

generating an image, I₁, with F_c as background and a shrunken F_h as foreground;

generating an image, I₂, by making L copies of the confusion texture map that are scaled down in size and put into I₁ with varying sizes and locations;

generating an image, I₃, by

making a number of copies of F_c and randomly putting these copies of F_c into I₂;

dividing the image into M+1 regions, where M of the regions come from F_c and one region comes from F_h;

calculating the average intensity of the M regions and remapping the intensity of each region such that the average intensities are uniformly distributed across the M+1 regions;

randomly dividing each of the M+1 regions, said region into four quadrants and increasing the intensity of some quadrants, while decreasing the intensity of other quadrants; and

generating a final image, I_F, by making N copies of the feature regions in F_h and randomly putting said N copies into I₃ to generate the final test image.

16. The system of claim 10 wherein the image is generated to include at least one of:

non-frontal faces;

faces that are non-symmetrical;

various lighting and shading conditions; and

a background that contains face-like clutter.

17. The system of claim 10 wherein the determination of whether the user is a human or a computer program is made without human intervention.

18. The system of claim 10 wherein the user points to the feature points with a computer input device.

19. The system of claim 18 wherein the computer input device is a mouse.

20. The system of claim 10 wherein the inputs to generate the image are a 3D wire model of a generic head and a cylindrical texture map T_m of an arbitrary person.

21. The system of claim 10 wherein the image size is 512×

512 pixels.

22. The system of claim 10 wherein the output of the image generation module is test image I_F with ground truth of face locations and facial feature locations.

23. A computer-readable medium having computer-executable instructions for creating a test to determine whether a user is a person or a bot, said computer executable instructions comprising:

inputting a 3D wire model of a generic head and a texture map of an arbitrary person; and

generating a human interactive proof using said generic head model and texture map.

24. The computer-readable medium of claim 23 wherein the human interactive proof employs an image of a human face in which certain face features are at known locations in said image.

25. The computer-readable medium of claim 24 wherein a comparison of the locations of said features input by a user is made to their actual location in the image and is used to determine whether the user is a human or a bot.