Stroke based skeletonizer

Patent metadata

Field	Value
Publication number	US-10410052-B2
Application number	US-201715828283-A
Country	US
Kind code	B2
Filing date	Nov 30, 2017
Priority date	Nov 30, 2017
Publication date	Sep 10, 2019
Grant date	Sep 10, 2019

Abstract

A method for processing a stroke in an image is provided. The stroke includes a plurality of pixels and the method includes: executing a modified 4-way stroke width transform (SWT) on a mask of the stroke; determining a plurality of certain centerline points among the pixels based on the modified SWT; generating a plurality of polylines within the stroke based on the certain centerline points; determining a plurality of regions of certainty based on the polylines; removing the regions of certainty from the mask and leaving a plurality of regions of uncertainty in the mask; calculating a plurality of joints and end caps for each of the polylines based on the polylines and the regions of uncertainty; generating a completed polyline path by connecting the polylines based on the joints and end caps; and generating a description of the stroke based on the completed polyline path.

First claim

What is claimed is:

1. A method for processing a stroke in an image, the stroke comprising a plurality of pixels and the method comprising:
executing a modified 4-way stroke width transform (SWT) on a mask of the stroke;
determining a plurality of certain centerline points among the pixels based on the modified SWT;
generating a plurality of polylines within the stroke based on the certain centerline points, wherein each of the polylines is formed of contiguous certain centerline points;
determining a plurality of regions of certainty based on the polylines;
removing the regions of certainty from the mask and leaving a plurality of regions of uncertainty in the mask;
calculating a plurality of joints and end caps for each of the polylines based on the polylines and the regions of uncertainty;
generating a completed polyline path by connecting the polylines based on the joints and end caps; and
generating a description of the stroke based on the completed polyline path.

2. The method of claim 1 , wherein executing the modified SWT on the mask of the stroke comprises:
generating a stroke width image, a stroke orientation image, and a stroke width centerline image of the stroke based on an orientation of each of the pixels,
wherein the orientation of each of the pixels is based on a predetermined coordinate system of the image.

3. The method of claim 2 , wherein determining the certain centerline points for the stroke comprises:
calculating a consensus of orientation for a center pixel among the pixels based on comparing an orientation of the center pixel to an orientation of each neighboring pixel that surrounds the center pixel on the stroke orientation using the stroke orientation of the stroke; and
determining that the center pixel is a certain centerline point among the certain centerline points in response to the consensus of orientation exceeding a predetermined certainty threshold.

4. The method of claim 1 , wherein
the regions of certainty include all pixels among the pixels that surround all certain centerline points between terminal ends of each of the polylines, and
the regions of uncertainty include all remaining pixels among the plurality of pixels.

5. The method of claim 1 , wherein calculating the joints comprises:
determining two polylines among the polylines with a potential connection under a predetermined maximum change threshold;
calculating a potential path between the two polylines based on the potential connection between the two polylines; and
removing the two polylines from further consideration,
wherein the potential path between the two polylines is at least selected from a group consisting of: a straight-line, a perpendicular intersection, a corner intersection, a line-to-line intersection, and a curve fit.

6. The method of claim 1 , wherein calculating the end caps comprises:
selecting a region of uncertainty among the regions of uncertainty that comprises only a single polyline among the polylines;
overlapping a plurality of end cap templates over an entirety of the region of uncertainty and calculating a matching value for each of the end cap templates based on the overlapping;
selecting an end cap for the region of uncertainty based on an end cap template with the largest matching value; and
altering a length of the polyline based on the selected end cap,
wherein the plurality of end caps comprises a square end cap, a butt end cap, and a round end cap.

7. The method of claim 1 , further comprising
recreating the mask by connecting the regions of uncertainty based on the completed polyline path and the modified SWT.

8. The method of claim 1 , further comprising:
determining a region of uncertainty, among the plurality of regions of uncertainty, that includes remnant pixels;
removing the remnant pixels in response to a cardinality of the remnant pixels falling below a predetermined remnant pixel threshold;
generating an image of the remnant pixels and associating the remnant pixels with the region of uncertainty in response to the cardinality of the remnant pixels exceeding the predetermined remnant pixel threshold,
wherein the description of the stroke further comprises a remnant pixel information based on the association.

9. The method of claim 1 , wherein the image comprises a writing board, and the stroke is a hand-drawn graphic on the writing board with a marker.

10. A non-transitory computer readable medium (CRM) storing computer readable program code for processing a stroke in an image, the stroke comprising a plurality of pixels, embodied therein that:
executes a modified 4-way stroke width transform (SWT) on a mask of the stroke;
determines a plurality of certain centerline points among the pixels based on the modified SWT;
generates a plurality of polylines within the stroke based on the certain centerline points, wherein each of the polylines is formed of contiguous certain centerline points;
determines a plurality of regions of certainty based on the polylines;
removes the regions of certainty from the mask and leaves a plurality of regions of uncertainty in the mask;
calculates a plurality of joints and end caps for each of the polylines based on the polylines and the regions of uncertainty;
generates a completed polyline path by connecting the polylines based on the joints and end caps; and
generates a description of the stroke based on the completed polyline path.

11. The non-transitory CRM of claim 10 , wherein executing the modified SWT on the mask of the stroke comprises:
generating a stroke width image, a stroke orientation image, and a stroke width centerline image of the stroke based on an orientation of each of the pixels,
wherein the orientation of each of the pixels is based on a predetermined coordinate system of the image.

12. The non-transitory CRM of claim 11 , wherein determining the certain centerline points for the stroke comprises:
calculating a consensus of orientation for a center pixel among the pixels based on comparing an orientation of the center pixel to an orientation of each neighboring pixel that surrounds the center pixel on the stroke orientation using the stroke orientation of the stroke; and
determining that the center pixel is a certain centerline point among the certain centerline points in response to the consensus of orientation exceeding a predetermined certainty threshold.

13. The non-transitory CRM of claim 10 , wherein
the regions of certainty include all pixels among the pixels that surround all certain centerline points between terminal ends of each of the polylines, and
the regions of uncertainty include all remaining pixels among the plurality of pixels.

14. The non-transitory CRM of claim 10 , wherein calculating the joints comprises:
determining two polylines among the polylines with a potential connection under a predetermined maximum change threshold;
calculating a potential path between the two polylines based on the potential connection between the two polylines; and
removing the two polylines from further consideration,
wherein the potential path between the two polylines is at least selected from a group consisting of: a straight-line, a perpendicular intersection, a corner intersection, a line-to-line intersection, and a curve fit.

15. The non-transitory CRM of claim 10 , wherein the image comprises a writing board, and the stroke is a hand-drawn graphic on the writing board with a marker.

16. A system for processing a stroke in an image, the stroke comprising a plurality of pixels, the system comprising:
a memory;
a computer pr

Assignees

• Konica Minolta Laboratory Usa Inc

Inventors

• Guarnieri Stuart

Classifications

• G06V30/347 Primary

  Sampling; Contour coding; Stroke extraction · CPC title

• G06V30/36

  Matching; Classification · CPC title

• G06V30/10

  Character recognition · CPC title

• G06K9/00422 Primary

  Physics · mapped topic

• G06K9/00416

  Physics · mapped topic