Segmentation based content alteration techniques

• US 7,653,944 B2
• Filed: 01/31/2005
• Issued: 01/26/2010
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lester, Erren Dusan, Kallin, Shannon A., Chellapilla, Kumar H., Paya, Ismail Cem, Simard, Patrice Y.
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): RAHIM, MONJUR
• Application Number:
  US11/046,996
• Publication Number:
  US 20050246775A1
• Time in Patent Office: 1,821 Days
• Field of Search: 709/225, 709/206, 709/229, 382/100, 713/202, 713/182, 705/14, 705/50, 726/23, 726/27, 380/202
• US Class Current: 726/27
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/55 Detecting local intrusion or implementing counter-measures
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06T 3/00 Geometric image transformations in the plane of the image

Abstract

The subject invention provides a unique system and method that facilitates creating HIP challenges (HIPs) that can be readily segmented and solved by human users but that are too difficult for non-human users. More specifically, the system and method utilize a variety of unique alteration techniques that are segmentation-based. For example, the system and method employ thicker arcs or occlusions that do not intersect characters already placed in the HIP. The thickness of the arc can be measured or determined by the thickness of the characters in the HIP. In addition to increasing the thickness, the arcs can be lengthened because longer arcs tend to resemble pieces of characters and may be harder to erode. Usability maps can be generated and used to selectively place clutter or occlusions and to selectively warp characters or the character sequence to facilitate human recognition of the characters.

Claims

1. A segmentation-based human interactive proof (HIP) generation system to ensure that a response is not generated by a computer by asking a user to complete a simple test which the computer is able to generate and grade, comprising:

a first selection component to form a preliminary HIP sequence by randomly selecting multiple characters from a plurality of characters stored in a character cache.

an arc generation module, a computer processor populates a thick arc cache with a plurality of thick arcs having a line thickness approximately equal to a line thickness of the multiple characters comprising the HIP sequence;

and a second selection component to randomly select one or mores thick arcs from the thick arc cache for placement among the multiple characters of the HIP sequence such that each of the one or more thick arcs are free from intersection with the multiple characters of the HIP sequence.

2. The system of claim 1, wherein the second selection component randomly flips or rotates at least one of the one or more thick arcs prior to placing the one or more thick arcs among the multiple characters of the HIP sequence.

3. The system of claim 1, wherein the arc generation module further populates a thin arc cache with a plurality of thin arcs of a plurality of line thicknesses according to a pre-determined maximum line thickness, the thin arcs intersect with one or more foreground pixels in the HIP sequence.

4. The system of claim 1, wherein the character cache stores multiple versions of each of the plurality of characters such that each of the multiple versions account for variances among x and y scaling, rotation, and font.

5. A segmentation-based human interactive proof (HIP) generation system, comprising:

an HIP sequence comprising a plurality of characters;

a thick non-intersecting arc cache comprising pre-rendered thick arcs having a line thickness approximately equivalent to a line thickness of the plurality of characters comprising the HIP sequence.

a selection component of a computer processor, to randomly select one or more pre-rendered thick arcs for placement among the plurality of characters of the HIP sequence;

an acceptance module to reject the randomly selected one or more pre-rendered thick arcs when a bounding box of the randomly selected one or more thick arcs intersects with at least one of the plurality of characters of the HIP sequence; and

a warping component to warp the HIP sequence based at least upon a warp field selected from a warp field cache.

6. The system of claim 5, further comprising:

a character cache to store a plurality of pre-rendered character images, the plurality of characters in the HIP sequence selected from among the pre-rendered character images stored in the character cache;

a thin arc cache to store pre-rendered thin arcs having a line thickness less than the minimum line thickness of the thick arcs, the selection component to select one or more thin arcs from the thin arc cache for rendering among the plurality of characters of the HIP sequence, wherein at least one of the selected one or more thin arcs intersect with one or more foreground pixels of the HIP sequence when rendered among the plurality of characters of the HIP sequence; and

a thick background arc cache to store one or more thick intersecting arcs that are randomly selected for rendering in the HIP sequence in a color identical to a background color of the HIP sequence, wherein the one or more thick intersecting arcs are rendered in the HIP sequence after the one or more thin arcs are rendered among the plurality of characters of the HIP sequence but before the warp field is applied.

7. The system of claim 5, wherein the thick non-intersecting arc cache further stores thick arcs having a length configured to facilitate generation of characters with long stroke lengths.

8. The system of claim 5, wherein the selection component places each thick arc based at least in part upon a usability map for a given character in the HIP sequence.

9. The system of claim 5, wherein the warping component warps the HIP sequence in at least one of globally or locally based upon a usability map for a given character.

10. The system of claim 5, further comprising a component to alter at least one of a rotation and curvature of one or more thick arcs selected from the thick arc cache before rendering the arc in the HIP sequence to facilitate minimizing cache size.

11. The system of claim 5, further comprising a usability map builder component to collect human user solutions to a plurality of HIP challenges to construct usability maps for at least a subset of characters found in the HIP challenges, the usability maps to indicate which portions of a character are more important for human recognition of the character.

12. The system of claim 5, further comprising at least one of a HIP cache that comprises a plurality of HIP signatures successfully solved by humans that are served to humans again;

and a usability map cache that comprises a plurality of usability maps.

13. A segmentation-based human interactive proof (HIP) generation method, comprising:

copying one or more characters from a character cache containing pre-rendered images of the one or more characters to place and on a HIP image;

randomly generating by a computer processor, one or more arcs within a given line thickness range;

selecting positions and orientations for each arc on the HIP image;

computing an acceptability score for the placement of each arc on the existing image; and

placing the arcs that are above the acceptability threshold on the HIP image.

14. The method of claim 13, further comprising storing one or more generated arcs to at least one cache based in part on a line thickness of the arcs.

15. The method of claim 13, wherein computing the acceptability score comprises at least one of the following:

ascertaining whether a bounding box of the arc intersects with a bounding box of any character in the HIP sequence; and

ascertaining whether the arc intersects with one or more foreground pixels present in the HIP sequence.

16. The method of claim 13, further comprising placing at least one of a thick non-intersecting arc and a thin intersecting arc in the HIP sequence based at least in part upon a usability map for any given character in the HIP sequence.

17. The method of claim 13, further comprising warping a HIP sequence in at least one of a global and local manner based at least in part upon at least one usability map for any given character in the HIP sequence.

18. The method of claim 13, further comprising building a plurality of usability maps to facilitate improved human recognition of characters in the HIP sequences, the building of the plurality of usability maps comprises:

collecting human user solutions to a plurality of HIP sequences;

analyzing successes and errors for each HIP sequence; and

determining which character portions are at least one of more or less important for successful human recognition of the character.

19. The method of claim 18, further comprising storing the plurality of usability maps in a usability map cache.