Recognizing symmetries along paths in vector art

• US 8,300,951 B1
• Filed: 11/26/2008
• Issued: 10/30/2012
• Est. Priority Date: 09/19/2008
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Mech, Radomir, Yeh, Yi-Ting
• Primary Examiner(s): Chang, Jon
• Application Number:
  US12/324,265
• Time in Patent Office: 1,434 Days
• Field of Search: 382/203, 382/206, 382/288
• US Class Current: 382/203
• CPC Class Codes: G06T 2207/20048 Transform domain processing
• CPC Class Codes: G06T 7/68 of symmetry
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56

Abstract

A method to find symmetries along curved paths in input scenes. The method may detect a curve in an input scene and one or more elements on that curve. The method may define and group points for the one or more element on the curve, and define a centroid for each group. The method may then parameterize a transformation in transformation space between each centroid pair in the input scene. The method may then extract transformation paths by clustering points. The method may create phantom objects in case of mirroring along curved paths to help detect the curved paths.

Claims

1. A computer-implemented method, comprising:

receiving an image, wherein the image comprises a first scene, wherein the first scene comprises one or more objects distributed on one or more curves, wherein the one or more objects are arranged according to one or more symmetries;

placing a plurality of sample points for the one or more objects at uniform distances along each of the one or more curves in the first scene;

matching transformations in transformation space for pairs of the plurality of the sample points, wherein one or more of the pairs of the plurality of the sample points comprise a respective matching neighborhood; and

placing one or more points in the transformation space for each of the one or more pairs with the matching neighborhood to find the one or more symmetries.

2. The method of claim 1, further comprising:

detecting a plurality of elements by finding the respective one or more matching neighborhoods of the sample point pairs with matching transformations.

3. The method of claim 2, further comprising:

defining a first centroid for a first element of the plurality of elements and a second centroid for a second element of the plurality of elements, wherein the first centroid and the second centroid comprise a first centroid pair;

finding one or more transformations between the centroids of the first centroid pair.

4. The method of claim 3, further comprising:

examining the first centroid pair;

placing points in the transformation space dependent on the first centroid pair; and

clustering in the transformation space to obtain symmetries along the one or more curves according to the placed points.

5. The method of claim 4, wherein said placing points in the transformation space comprises:

creating phantom objects for the first centroid pair that exhibit a mirror symmetry; and

placing points in the transformation space for a first pair of phantom objects.

6. The method of claim 4, further comprising:

receiving input indicative of sliding a group of elements along the one or more curves; and

in response to said receiving, sliding the group of elements along the one or more curves.

7. The method of claim 4, further comprising:

determining that distances between elements in consecutive pairs on the two or more curves are constant; and

in response to said receiving, merging the one or more curves.

8. The method of claim 4, further comprising:

receiving input indicative of changing spacing between at least some of the plurality of elements along a respective one of the one or more curves; and

in response to said receiving, changing the spacing between the at least some of the plurality of elements along the respective one of the one or more curves.

9. The method of claim 4, further comprising:

locally straightening a geometry of the first scene around the one or more curves.

10. The method of claim 1, further comprising:

storing the image using one of the found one or more symmetries.

11. The method of claim 1,

wherein the one or more symmetries comprise one or more of:

reflection symmetry;

translation symmetry;

scaling symmetry;

or

any other type of symmetry.

12. A system, comprising:

one or more processors; and

a memory coupled to the one or more processors, wherein the memory stores program instructions executable by the one or more processors to implement;

receiving an image, wherein the image comprises a first scene, wherein the first scene comprises one or more objects distributed on one or more curves, wherein the one or more objects are arranged according to one or more symmetries;

placing a plurality of sample points for the one or more objects at uniform distances along each of the one or more curves in the first scene;

matching transformations in transformation space for pairs of the plurality of the sample points, wherein one or more of the pairs of the plurality of the sample points comprise a respective matching neighborhood; and

placing one or more points in the transformation space for each of the one or more pairs with the matching neighborhood to find the one or more symmetries.

13. The system of claim 12, wherein the program instructions are further executable by the one or more processors to implement:

detecting a plurality of elements by finding the respective one or more matching neighborhoods of the sample point pairs with matching transformations.

14. The system of claim 13, wherein the program instructions are further executable by the one or more processors to implement:

defining a first centroid for a first element of the plurality of elements and a second centroid for a second element of the plurality of elements, wherein the first centroid and the second centroid comprise a first centroid pair;

finding one or more transformations between the centroids of the first centroid pair.

15. The system of claim 14, wherein the program instructions are further executable by the one or more processors to implement:

examining the first centroid pair;

placing points in the transformation space dependent on the first centroid pair; and

clustering in the transformation space to obtain symmetries along the one or more curves according to the placed points.

16. The system of claim 15, wherein said placing points in the transformation space comprises:

creating one or more phantom objects for the first centroid pair that exhibit a mirror symmetry; and

placing points in the transformation space for a first pair of phantom objects.

17. The system of claim 15, wherein the program instructions are further executable by the one or more processors to implement:

receiving input indicative of sliding a group of elements along the one or more curves; and

in response to said receiving, sliding the group of elements along the one or more curves.

18. The system of claim 15, wherein the program instructions are further executable by the one or more processors to implement:

determining that distances between elements in consecutive pairs on the two or more curves are constant; and

in response to said determining, merging the one or more curves that.

19. The system of claim 15, wherein the program instructions are further executable by the one or more processors to implement:

receiving input indicative of changing spacing between at least some of the plurality of elements along a respective one of the one or more curves; and

in response to said receiving, changing the space between the at least some of the plurality of elements along the respective one of the one or more curves.

20. The system of claim 15, wherein the program instructions are further executable by the one or more processors to implement:

locally straightening a geometry of the first scene around the one or more curves.

21. The system of claim 12, wherein the program instructions are further executable by the one or more processors to implement:

storing the image using one of the one or more symmetries.

22. The system of claim 12,

wherein the one or more symmetries comprise one or more of:

reflection symmetry;

translation symmetry;

scaling symmetry;

or

any other type of symmetry.

23. A computer-readable storage medium storing program instructions computer-executable to implement:

receiving an image, wherein the image comprises a first scene, wherein the first scene comprises one or more objects distributed on one or more curves, wherein the one or more objects are arranged according to one or more symmetries;

placing a plurality of sample points for the one or more objects at uniform distances along each of the one or more curves in the first scene;

matching transformations in transformation space for pairs of the plurality of the sample points, wherein one or more of the pairs of the plurality of the sample points comprise a respective matching neighborhood; and

placing one or more points in the transformation space for each of the one or more pairs with the matching neighborhood to find the one or more symmetries.

24. The computer-readable storage medium of claim 23, wherein the program instructions are further computer-executable to implement:

detecting a plurality of elements by finding the respective one or more matching neighborhoods of the sample point pairs with matching transformations.

25. The computer-readable storage medium of claim 24, wherein the program instructions are further computer-executable to implement:

defining a first centroid for a first element of the plurality of elements and a second centroid for a second element of the plurality of elements, wherein the first centroid and the second centroid comprise a first centroid pair;

finding one or more transformations between the centroids of the first centroid pair.

26. The computer-readable storage medium of claim 25, wherein the program instructions are further computer-executable to implement:

examining the first centroid pair;

placing points in the transformation space dependent on the first centroid pair; and

clustering in the transformation space to obtain symmetries along the one or more curves according to the placed points.

27. The computer-readable storage medium of claim 26, wherein said placing points in the transformation space comprises:

creating one or more phantom objects for the first centroid pair that exhibit a mirror symmetry; and

placing points in the transformation space for a first pair of phantom objects.

28. The computer-readable storage medium of claim 26, wherein the program instructions are further computer-executable to implement:

receiving input indicative of sliding a group of elements along the one or more curves; and

in response to said receiving, sliding the group of elements along the one or more curves.

29. The computer-readable storage medium of claim 26, wherein the program instructions are further computer-executable to implement:

determining that distances between elements in consecutive pairs on the one or more curves are constant; and

in response to said determining, merging the one or more curves.

30. The computer-readable storage medium of claim 26, wherein the program instructions are further computer-executable to implement:

receiving input indicative of changing spacing between at least some of the plurality of elements along a respective one of the one or more curves; and

in response to said receiving, changing spacing of the at least some of the plurality of elements along the respective one of the one or more curves.

31. The computer-readable storage medium of claim 26, wherein the program instructions are further computer-executable to implement:

locally straightening a geometry of the first scene around the one or more curves.

32. The computer-readable storage medium of claim 23, wherein the program instructions are further computer-executable to implement:

storing the image using one of the one or more symmetries.

33. The computer-readable storage medium of claim 23,

wherein the one or more symmetries comprise one or more of:

reflection symmetry;

translation symmetry;

scaling symmetry;

or

any other type of symmetry.

34. A computer-implemented method, comprising:

executing instructions on a specific apparatus so that binary digital electronic signals representing an image are received, wherein the image comprises a first scene, wherein the first scene comprises one or more objects distributed on one or more curves, wherein the one or more objects are arranged according to one or more symmetries;

executing instructions on said specific apparatus so that binary digital electronic signals representing a plurality of sample points are placed for the one or more objects at uniform distances along each of the one or more curves in the first scene;

executing instructions on said specific apparatus to match transformations in transformation space for pairs of the plurality of the sample points, wherein one or more of the pairs of the plurality of the sample points comprise a respective matching neighborhood; and

executing instructions on said specific apparatus so that binary digital electronic signals representing one or more points in the transformation space are placed for each of the one or more pairs with the matching neighborhood to find the one or more symmetries.