Segmentation based content alteration techniques

• US 20050246775A1
• Filed: 01/31/2005
• Published: 11/03/2005
• Est. Priority Date: 03/31/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chellapilla, Kumar H., Simard, Patrice Y.
• Granted Patent: US 7,653,944 B2
• Time in Patent Office: Days
• US Class Current: 726/22
• 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 HIP generation system comprising:

an arc generation module that generates a plurality of arcs of a plurality of thicknesses and a minimum thickness that mimics a distribution of character strokes in any selected font; and

a selection component that randomly selects any number of thick arcs and places each thick arc such that the arc does not intersect with any characters already present in a selected HIP sequence.

2. The system of claim 1, further comprising:

a selection component that randomly selects any number of thick arcs and places each thick arc such that the arc does not intersect with at least one of the following;

any characters already present and any arcs added so far in a selected HIP sequence.

3. The system of claim 1, further comprising at least one of:

an arc generation module that generates arcs of a plurality of thicknesses below a pre-determined maximum thickness whereby the thin arcs can intersect with any foreground pixel already in an existing HIP sequence; and

a warping component that warps the existing HIP sequence.

4. The system of claim 1, where the arc generation module is a cache of pre-rendered arcs.

5. A segmentation-based HIP generation system comprising:

a thick non-intersecting arc cache that comprises pre-rendered thick arcs having a plurality of thicknesses and a minimum thickness that mimics a distribution of character strokes in any selected font;

a selection component that randomly selects any number of thick arcs and places each thick arc such that the arc does not intersect with any characters already present in a selected HIP sequence; and

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

6. The system of claim 5, further comprising at least one of the following:

a character cache that comprises a plurality of pre-rendered character images;

a thin intersecting arc cache that comprises pre-rendered arcs having a thickness less than the minimum thickness of the thick arcs, whereby the thin arcs intersect with any foreground pixels already present in the HIP sequence; and

a thick background arc cache that comprises 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.

7. The system of claim 5, the thick non-intersecting arc cache further comprises thick arcs having a length large enough to facilitate generation of characters with longer stroke lengths.

8. The system of claim 5, 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, 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 that alters at least one of a rotation and curvature of any number of 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 that collects 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, whereby the usability maps 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 can be served to humans again;

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

13. A system that generates HIP combinations of characters and arcs comprising:

a HIP cache that comprises a plurality of HIP signatures successfully solved by humans; and

a warping component that warps each cached HIP signature before serving it to a user for solving.

14. The system of claim 13, further comprising a HIP generation module that randomly selects any number of characters and arcs to create at least one HIP signature.

15. A segmentation-based HIP generation method comprising:

randomly generating any number of characters from a character set and placing them on a HIP image;

randomly generating any number of arcs within a given thickness range;

selecting positions and orientations for each arc;

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

placing only the arcs that are above the acceptability threshold on the exisiting image.

16. The method of claim 15, further comprising caching any number of generated arcs to at least one cache, whereby the cache selected is based in part on the thickness of the arcs.

17. The method of claim 15, determining whether placement of each arc is acceptable 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 any foreground pixels already present in the HIP sequence.

18. The method of claim 15, 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.

19. The method of claim 15, 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.

20. The method of claim 15, 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.

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