Identifying shapes in an image by comparing Bézier curves

Patent metadata

Field	Value
Publication number	US-9741133-B2
Application number	US-201514869959-A
Country	US
Kind code	B2
Filing date	Sep 29, 2015
Priority date	Sep 29, 2015
Publication date	Aug 22, 2017
Grant date	Aug 22, 2017

Abstract

The present disclosure is directed to identifying shapes in an image. For example, a shape identification system may identify an unknown shape represented by a Bézier path that has at least one Bézier curve. The shape identification system may also identify a stored Bézier path that has at least one stored Bézier curve, for example, in a database of known shapes. Using the Bézier curve of the unknown shape and the stored Bézier curve of the known shape, the shape identification system can determine a transformation matrix that transforms the transforms the Bézier curve of unknown shape to the stored Bézier curve of the known shape. Then, the shape identification system can compare the transformed Bézier curve to the stored Bézier curve to determine whether the unknown shape matches the known shape.

First claim

We claim:

1. In a digital medium environment for analyzing and classifying images, a method for identifying a shape in an image, comprising:
identifying an unknown shape within an image represented by a Béziér path, the Béziér path comprising at least one Béziér curve;
identifying a known shape represented by a stored Béziér path, the stored Béziér path comprising at least one stored Béziér curve;
determining, by at least one processor, a matrix transformation that transforms the at least one Béziér curve of the unknown shape to the at least one stored Béziér curve of the known shape, wherein the matrix transformation accounts for a change in scale and a change in skew between the at least one Béziér curve and the at least one stored Béziér curve;
applying the matrix transformation to the at least one Béziér curve of the unknown shape;
comparing the transformed at least one Béziér curve of the unknown shape to the at least one stored Béziér curve of the known shape to determine whether the unknown shape matches the known shape; and
classifying the image based on the comparison of the at least one Béziér curve of the unknown shape to the at least one stored Béziér curve of the known shape.

2. The method of claim 1 , further comprising classifying the unknown shape within the image using one or more properties from the known shape if the unknown shape matches the known shape.

3. The method of claim 1 , wherein the known shape is stored in a database of known shapes, and wherein each known shape in the database of known shapes comprises one or more stored Béziér curves.

4. The method of claim 3 , further comprising identifying the one or more stored Béziér curves representing the known shapes in the database of known shapes.

5. The method of claim 4 , further comprising determining, for each of the one or more stored Béziér curves representing the known shapes, a matrix transformation that transforms the at least one Béziér curve of the unknown shape to the stored Béziér curve.

6. The method of claim 1 , further comprising applying the matrix transformation to the Béziér path representing the unknown shape by applying the matrix transformation to each Béziér curve of a plurality of Béziér curves representing the unknown shape.

7. The method of claim 6 , further comprising comparing the transformed Béziér path representing the unknown shape to the stored Béziér path of the known shape to determine if the unknown shape matches the known shape.

8. The method of claim 7 , wherein determining if the unknown shape matches the known shape comprises determining whether the transformed Béziér path of the unknown shape is within tolerance level difference of the stored Béziér path of the known shape.

9. The method of claim 1 , further comprising identifying Béziér points associated with the at least one Béziér curve of the unknown shape and corresponding stored Béziér points associated with the at least one stored Béziér curve of the known shape.

10. The method of claim 9 , further comprising:
generating a plurality of equations based on the Béziér points associated with the at least one Béziér curve of the unknown shape and the corresponding stored Béziér points associated with the at least one stored Béziér curve of the unknown shape, the plurality of equations including a plurality of transformation variables; and
solving the plurality of equations to determine the plurality of transformation variables.

11. The method of claim 10 , wherein the Béziér points associated with the at least one Béziér curve of the unknown shape comprise one or more Béziér points and one or more Béziér control points, and wherein the corresponding stored Béziér points associated in the at least one stored Béziér curve of the known shape comprise one or more stored Béziér point and one or more stored Béziér control point.

12. The method of claim 11 , wherein generating the plurality of equations based on the Béziér points associated with the at least one Béziér curve and the corresponding Béziér points associated with the at least one stored Béziér curve comprise generating six equations using three of four sets of corresponding Béziér points.

13. The method of claim 12 , wherein solving the plurality of equations to determine the plurality of transformation variables comprises solving the six equations to determine six transformation variables.

14. The method of claim 13 , wherein determining the matrix transformation that transforms the at least one Béziér curve to the at least one stored Béziér curve comprises determining the matrix transformation based on the six determined transformation variables.

15. The method of claim 14 , wherein the matrix transformation further accounts for a change in rotation and a change in position between the at least one Béziér curve and the at least one stored Béziér curve.

16. The method of claim 14 , wherein comparing the transformed at least one Béziér curve of the unknown shape to the at least one stored Béziér curve of the known shape to determine whether the unknown shape matches the known shape comprises comparing a fourth set of corresponding Béziér points after applying the transformation matrix to the at least one Béziér curve.

17. In a digital medium environment for analyzing and classifying images, a method for identifying a shape in an unstructured form, comprising:
identifying an unknown shape within an image represented by a Béziér path, the Béziér path comprising at least one Béziér curve;
identifying a known form element represented by a stored Béziér path, the Béziér path comprising at least one stored Béziér curve;
determining, by at least one processor, a matrix transformation that transforms the at least one Béziér curve of the unknown shape to the at least one stored Béziér curve, wherein the matrix transformation accounts for a change in scale and a change in skew between the at least one Béziér curve and the at least one stored Béziér curve;
applying the matrix transformation to the at least one Béziér curve of the unknown shape;
comparing the transformed Béziér path of the unknown shape to the stored Béziér path of the known form element to determine that the unknown shape matches the known form element;
applying properties associated with the known form element to the unknown shape; and
classifying the image based on the comparison of the transformed Béziér path of the unknown shape to the stored Béziér path of the known form element.

18. The method of claim 17 , wherein applying properties associated with the known form element to the unknown shape comprises applying user-input functionality to the unknown shape based on the user-input functionality of the known form element.

19. The method of claim 17 , wherein the known form element is one of a blank text field, a radio button, a check box, or a comb field.

20. In a digital medium environment for analyzing and classifying images, a system for identifying a shape in an image, comprising:
at least one processor; and
at least one non-transitory computer readable storage medium storing instructions thereon, that, when executed by the at least one processor, cause the system to:
identify an unknown shape within an image represented by a Béziér path, the Béziér path comprising at least one Béziér curve;
identify a known shape represented by a stored Béziér path, the stored Béziér path comprising at least one stored Béziér curve;
determine a matrix transformation that transforms the at least one Béziér curve of the unknown shape t

Assignees

• Adobe Systems Inc

Inventors

• Yu Fan
• Thevenet Frederic

Classifications

• G06V30/412 Primary

  Layout analysis of documents structured with printed lines or input boxes, e.g. business forms or tables · CPC title

• G06T7/60 Primary

  Analysis of geometric attributes · CPC title

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title

• G06F18/24

  Classification techniques · CPC title

• G06V10/471

  using approximation functions · CPC title