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

• US 7,725,395 B2
• Filed: 09/19/2003
• Issued: 05/25/2010
• 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
• Primary Examiner(s): Worjloh; Jalatee
• Application Number:
  US10/664,657
• Publication Number:
  US 20050065802A1
• Time in Patent Office: 2,440 Days
• Field of Search: 382/216, 382/181, 382/155, 705/1, 705/50, 706/1, 713/188
• US Class Current: 705/50
• 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:

using a computer for generating a human interactive proof employing an image of one or more deformed body parts wherein features of the deformed body parts are at known locations in said image wherein generating the human interactive proof comprises;

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

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

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

performing local deformations to features of the body part using the generic model;

generating an image with the deformed and transformed body part with the confusion texture map applied to be used as a test image in the human interactive proof;

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

comparing the computer user'"'"'s locations of said at least one feature of said deformed body part to its known location in the image created using the deformed and transformed body part with the confusion texture map applied; and

determining whether the computer user is a human or a computer program using the comparison of the computer user'"'"'s location of said at least one feature to the known location and outputting this determination.

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

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

4. The computer-implemented process of claim 1 wherein said one or more deformed 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 computer-user-identified feature locations are specified by the user using a computer pointing device.

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

using a computing device for generating a human interactive proof employing an image of one or more deformed body parts wherein features thereof are at known locations in said image, comprising;

inputting a first texture map, T_m, and a generic model of a 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 a 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 b 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, I₃, 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, to be used as the image of the human interactive proof employing an image by making N copies of the feature regions in F_h and randomly putting said N copies into 13 to generate the final test image I_F;

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

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

determining whether the computer user is a human or a computer program based on the comparison of the computer user'"'"'s locations to the known locations and outputting this determination.

8. 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 executed by the computing device, the computer program modules further comprising modules to,

generate a human interactive proof employing an image of a deformed human face wherein features of the deformed human face are at known locations in said image, wherein the module for generating a human interactive proof comprises sub-modules for;

inputting a first texture map, T_m, and a generic model of a 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 the face using said generic model;

performing local deformations to features of the face;

generating an image, F_h, with a 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, I₃, 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, to be used as the image of the human interactive proof employing an image by making N copies of feature regions in F_h and randomly putting said N copies into I₃ to generate the final test image I_F;

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

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

determine whether the computer user is a human or a bot based on the comparing and output this determination.

9. The system of claim 8 wherein the image is automatically synthesized.

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

11. The system of claim 8 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.

12. The system of claim 8 wherein the features of the deformed face comprise the four corners of the eyes and the two corners of the mouth.

13. The system of claim 8 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.

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

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

16. The system of claim 15 wherein the computer input device is a mouse.

17. The system of claim 8 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.

18. The system of claim 8 wherein the image size is 512×

512 pixels.

19. The system of claim 8 wherein the image in the human interactive proof is test image I_F with ground truth of face locations and facial feature locations.

20. A computer-readable storage medium having computer-executable instructions stored thereon 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 with a face and a first texture map of an arbitrary person; and

generating a human interactive proof using said generic head model and the first texture map, by;

inputting the first texture map, T_m, and the generic model of a head with the 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 the face using the generic model;

performing local deformations to features of the face;

generating an image, F_h, with a 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, I₃, 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, to be used as the image of the human interactive proof employing an image by making N copies of the feature regions in c_h and randomly putting said N copies into I₃ to generate the final test image I_F.

21. The computer-readable storage medium of claim 20 wherein the human interactive proof employs an image of a deformed human face in which face features are at known locations in said image.

22. The computer-readable storage medium of claim 21 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.