AU770371B2 - Method and apparatus for fast skeleton and stroke extraction - Google Patents

Description

S&FRef: 578760 1. .'1

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant Actual Inventor(s): Address for Service: r Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan Cameron Bolitho Browne Spruson Ferguson St Martins Tower,Level 31 Market Street Sydney NSW 2000 (CCN 3710000177) Method and Apparatus for Fast Skeleton and Stroke Extraction Invention Title: s ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) [32] Application Date AU PR2171 20 Dec 2000 The following statement is a full description of this invention, including the best method of performing it known to me/us:- D don: 1 DEC ,Btch No: l 5815c -1- METHOD AND APPARATUS FOR FAST SKELETON AND STROKE

EXTRACTION

Technical Field of the Invention The present invention relates generally to the fields of computational geometry and computer graphics and, in particular, to a method and apparatus for the extraction of strokes from a set of closed finite planar curves. The invention also relates to a computer program product including a computer readable medium having recorded thereon a computer program for the extraction of strokes from a set of closed finite planar curves.

Background Art In the fields of computational geometry and computer graphics it is often desired to convert a set of original planar curves into a set of internal curves that contain additional information about the curves and from which the original curves can be reconstructed. This process is often referred to as "Skeletonisation". Particularly in ee ooo .9 relation to computer graphics, skeletonisation and stroke extraction can be used in the eoo~ee 9. 15 automatic decoration or embellishment of shapes according to stroke-based artistic rules, such as painting with brush strokes, or replacing stroke segments within a shape with correspondingly shaped artwork. For such uses the quality of reconstructed curves should ideally be indistinguishable from equivalent non-stroked outlines. However, the quality of the strokes is not important as long as the strokes contain curve information which will 20 allow for the accurate reconstruction of the original curve.

o999e9 For interactive systems, such as those used in computer graphics drawing packages, the speed of the stroke extraction is very important.

Traditional skeletonisation and stroke extraction methods generally involve converting an outline curve to polygons then processing the polygonised shape. Such traditional skeletonisation methods can loose useful information about the original curves, and can be computationally expensive if a high quality (ie. fine resolution) result is 578760.doc -2required. For example, the publication "Automated Derivation of High Accuracy Road Centerlines Thiessen Polygons Technique", http://www.esri.com/library/userconf/proc96/ T0400/PAP370/P370.HTM, by Ladak A. Martinez, R. (1996) (hereinafter called Ladak) discloses a method for generating the centreline of a polygonal shape using Thiessen Polygons a Voronoi diagram of the shape) and passing the skeleton through midpoints of internal edges. However, the Voronoi diagram can be expensive to compute. Further, the method disclosed by Ladak is based purely on the polygonised shape which looses information from the outline curve and a very fine polygonisation must be done for high quality results.

The publication "The Line-Skeleton", Computer Graphics and Image Processing 11, by F. Bookstein (1979) (hereinafter called Bookstein), at pages 123-137, discloses a method for determining a linear skeleton from a polygon. However, the method disclosed by Bookstein looses original curve information, requires a high number of sides of the original polygon to determine the skeleton and only works on polygons with small S* 15 exterior angles.

*0 The publication "Angular Bisector Network", Vol. PAMI 22, No. 1, 2000, by F.

Cloppet, J. M. Oliva and G. Stamon (hereinafter called Cloppet), at pages 120-128, discloses a method of stroke extraction using a form of the Generalised Voronoi Diagram.

*SSSSS

The generalised voronoi diagram of Cloppet can be expensive to compute and the method "20 disclosed by Cloppet is sensitive to artifacts in segmentation and can result in ambiguous branching cases.

US Patent 5,524,182 discloses a method for decomposing font characters into strokes. The method disclosed by US Patent 5,524,182 requires the predetermination of dominant points which can be limiting, or not even known until after stroke extraction is performed (eg. subdivision for morphing). In addition, the method disclosed by US Patent 5,524,182 requires the use of a Relative Neighborhood Graph and the final result 578760.doc -3of the method gives points mapped to a single central stroke. Finally, the strokes generated from the method of US Patent 5,524,182 and resulting from common degenerate cases can be inaccurate.

Summary of the Invention It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements by performing a fast skeletonisation on a low-resolution polygonisation of a shape, then using key information form original curve outlines of the shape to provide high quality results which are readily decomposed into strokes.

According to one aspect of the present invention there is provided a method of converting a closed curve into a set of strokes describing said curve, said method comprising the steps of: determining line segments describing said curve based on at least one point on said curve and on a stroke width of said curve; 0 15 forming at least one triangle interior to said curve, said triangle including at least one edge being defined by at least one of said line segments; 0000modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; *999.9 classifying each of said cells according to predetermined classifications; and a 99 e 0. 20 forming strokes interior to said cells depending on a classification of each of said cells.

According to another aspect of the present invention there is provided a method of converting a closed curve into a set of strokes describing said curve, said method comprising the steps of: forming at least one triangle interior to said curve, said triangle including at least one edge being defined by a line segment describing said curve; 578760.doc -4modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; classifying each of said cells according to predetermined classifications; and forming strokes interior to said cells depending on a classification of each of said cells.

According to still another aspect of the present invention there is provided an apparatus for converting a closed curve into a set of strokes describing said curve, said apparatus comprising: determination means for determining line segments describing said curve based on at least one point on said curve and on a stroke width of said curve; first forming means for forming at least one triangle interior to said curve, said triangle including at least one edge being defined by at least one of said line segments; modification means for modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; S" 15 classification means for classifying each of said cells according to predetermined classifications; and second forming means for forming strokes interior to said cells depending on a :classification of each of said cells.

According to still another aspect of the present invention there is provided an 20 apparatus for converting a closed curve into a set of strokes describing said curve, said •o.o•i apparatus comprising: first forming means for forming at least one triangle interior to said curve, said triangle including at least one edge being defined by a line segment describing said curve; modification means for modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; 578760.doc classification means for classifying each of said cells according to predetermined classifications; and second forming means for forming strokes interior to said cells depending on a classification of each of said cells.

According to still another aspect of the present invention there is provided a program for converting a closed curve into a set of strokes describing said curve, said program comprising: code for determining line segments describing said curve based on at least one point on said curve and on a stroke width of said curve; code for forming at least one triangle interior to said curve, said triangle including at least one edge being defined by at least one of said line segments; code for modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; •code for classifying each of said cells according to predetermined classifications; 15 and code for forming strokes interior to said cells depending on a classification of each of said cells.

According to still another aspect of the present invention there is provided a program for converting a closed curve into a set of strokes describing said curve, said S. 20 program comprising: code for forming at least one triangle interior to said curve, said triangle including at least one edge being defined by a line segment describing said curve; code for modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; code for classifying each of said cells according to predetermined classifications; and 578760.doc -6code for forming strokes interior to said cells depending on a classification of each of said cells.

Brief Description of the Drawings One or more embodiments of the present invention will now be described with reference to the drawings, in which: Fig. 1 shows a polygon describing a character formed by a set of finite closed planar curves; Fig. 2 shows the polygon of Fig. 1 after being converted into line segments; Fig. 3 shows a triangulation of the polygon formed by the closed planar curves of Fig. 1; Fig. 4(a) shows a shape composed of a single cell which is classified as singleton; Fig. 4(b) shows a shape composed of a single cell which is classified as •singleton; 15 Fig 4(c) shows another shape composed of a single cell with a stroke end point, where the cell has a sharp end; Fig. 4(d) shows a shape composed of a single cell with a stroke end point where the cell has a square end; Fig. 4(e) shows a cell classified as intermediate; 20 Fig. 4(f) shows a cell where three stroke ends meet at a point and which is classified as a 3-junction cell; Fig. 4(g) shows a cell where two stroke ends meet at a point and which is classified as a 2- junction cell; Fig. 4(h) shows a cell where four stroke ends meet at a point and which is classified as a 4- junction cell; 578760.doc -7- Fig. 4(i) shows a cell where five stroke ends meet at a point and which is classified as a 4- junction cell; Fig. 5 shows two triangles which share a common edge, and the resulting cell for the triangles after collapse; Fig. 6 shows a sharp triangular corner and a stroke growing from said corner; Fig. 7 shows two triangles that share an edge but have no external edges, and the resulting cell for the triangles after collapse; Fig. 8 shows two triangles that share an edge where the triangle has two adjacent external edges, and the resulting cell for the triangles after collapse; Fig. 9 shows three triangles that share edges with each other such that any triangle in the group is joined to any other by common triangles, but no external edges, and the resulting cell for the triangles after collapse; Fig. 10 shows the key cells produced by the triangulation of the polygon describing the letter b of Fig. 1; Fig. 11 shows cells resulting from the collapse of the network of cells formed by 0: the triangulation of the polygon of Fig. 1; Fig. 12 shows the polygon of Fig. 1 with strokes formed; Fig. 13 shows the polygon of Fig. 12 after being simplified; Fig. 14 shows a stroke formed by outline edge segments, which is parameterised S 20 to the range from time t=0 to t=l; Fig. 15(a) shows a set of closed planar curves and a resulting cell for the curves in accordance with the prior art; Fig. 15(b) shows the set of closed planar curves of Fig. 15(a) and a resulting cell for the curves; 578760.doc -8- Fig. 16 is a flowchart showing a method of converting a closed planar curve into a set of strokes; Fig. 17 is a flowchart showing a method of converting a planar curve into a set of line segments; Fig. 18(a) shows a curve run between curve key points; Fig. 18(b) shows another curve run between curve key points; Fig. 18(c) shows still another curve run between curve key points; Fig. 18(d) shows still another curve run between curve key points; Fig. 18(e) shows still another curve run between curve key points; Fig. 19(a) shows still another curve run between curve key points; Fig. 19(b) shows the interior vertices of the curve of Fig. 19(a) after the curve has been polygonised; Fig. 19(c) shows the interior vertices of the curve of Fig. 19(a) after the vertices have been merged; Fig. 20(a) shows a curve run between curve key points; Fig. 20(b) shows the interior vertices of the curve of Fig. 20(a) after the curve has been polygonised; :Fig. 20(c) shows the interior vertices of the curve of Fig. 20(a) after the vertices oooo• have been merged; and 20 Fig. 21 is a schematic block diagram of a general purpose computer upon which arrangements described can be practiced.

Detailed Description including Best Mode Where reference is made in any one or more of the accompanying drawings to steps and/or features, which have the same reference numerals, those steps and/or features have for the purposes of this description the same function(s) or operation(s), unless the contrary intention appears.

578760.doc -9- Some portions of the description which follows are explicitly or implicitly presented in terms of algorithms and symbolic representations of operations on data within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

It should be borne in mind, however, that the above and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, and as apparent from the 15 following, it will be appreciated that throughout the present specification, discussions utilizing terms such as "scanning", "calculating", "determining", "replacing", "generating" "initializing", "outputting", or the like, refer to the action and processes of a computer system, or similar electronic device, that manipulates and transforms data represented as physical (electronic) quantities within the registers and memories of the 20 computer system into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

The present specification also discloses apparatus for performing the operations of the methods. Such apparatus may be specially constructed for the required purposes, or may comprise a general purpose computer or other device selectively activated or reconfigured by a computer program stored in the computer. The algorithms and displays 578760.doc presented herein are not inherently related to any particular computer or other apparatus.

Various general purpose machines may be used with programs in accordance with the teachings herein. Alternatively, the construction of more specialized apparatus to perform the required method steps may be appropriate. The structure of a conventional general purpose computer will appear from the description below.

In addition, the present specification also discloses a computer readable medium comprising a computer program for performing the operations of the methods. The computer readable medium is taken herein to include any transmission medium for communicating the computer program between a source and a designation. The transmission medium may include storage devices such as magnetic or optical disks, memory chips, or other storage devices suitable for interfacing with a general purpose computer. The transmission medium may also include a hard-wired medium such as exemplified in the Internet system, or wireless medium such as exemplified in the GSM mobile telephone system. The computer program is not intended to be limited to any S• 15 particular programming language and implementation thereof. It will be appreciated that a variety of programming languages and coding thereof may be used to implement the teachings of the disclosure contained herein.

.The principles of the preferred method described herein have general ooooo applicability to the generation of a skeleton for and the extraction of strokes from a set of 20 closed finite planar curves. However, for ease of explanation, the steps of the preferred method are described with reference to planar outline curves composed of one or more edges, each of which is composed of a continuous set of planar Bezier curve segments. It is not intended that the present invention be limited to the described method. For example, the invention may have application to any type of finite closed curve in any number of dimensions.

578760.doc -11- Fig. 16 is a flowchart showing a method of converting a closed planar curve into a set of strokes. The method of Fig. 16 is preferably implemented as an application program being resident on the hard disk drive 2110 of a computer system 2100 and being read and controlled in its execution by a processor 2105 of the computer system. The computer system 2100 will be described in detail below with reference to Fig. 21. The process begins at step 1601, where inflection points on the curve are marked. For example, Fig. 1 shows a polygon describing a character formed by a set of finite closed planar curves 101. The curves 101 are composed of two edges 107, 109, each of which is composed of a number of Bezier segments (eg. 111) delineated by on-curve knot points (eg. 102 and 103). Knot points shown as circles 102 are derived from the original outline curves, while knot points shown as squares 103 are inflection points that are defined as key points at which the curve tangent lies parallel to the x or y axes.

In accordance with the example of Fig. 1, edges are oriented to satisfy the nonzero winding fill rule. That is, outer outlines are clockwise orientated 104 while interior 15 holes are anticlockwise orientated 105.

From the curves 101 a stroke width S 106 can be estimated for the letter b of Fig. 1. An approximation of stroke width for the polygon describing the letter can be made by considering run lengths between key points, where a "run" is defined as a line oo segment between two key points. For example, run lengths below a lower threshold (eg.

20 5% of shape height) can be used to describe ornaments, serifs, or flaws within a shape, whilst run lengths above the lower threshold but below some upper threshold (eg. 25% of shape height) can be used to give an indication of a shape's stroke width. Run length sizes within a range (eg. 25% of shape height) can be averaged to give an estimated stroke width for any shape. For shapes with no key points and hence no run lengths (eg.

the letter a default estimate of stroke width (eg. 15% of shape height) can be used.

Alternatively, the estimated stroke width from related shapes (eg. the estimated stroke 578760.doc -12width of other characters within the same font) can be used to determine the stroke width of a shape.

Returning to Fig. 16, at the next step 1603, the curves are converted into a set of line segments by the processor 2105 and stored in a memory 2106 of the computer system 2100. The process of converting a curve into a set of line segments is often referred to as polygonisation. Any method of polygonisation can be used. However, preferably the curves are converted into a set of line segments by detecting key points along the curve and estimating an expected stroke width, in accordance with the method described below with reference to the flow chart of Fig. 17.

The process of Fig. 17 is preferably implemented as an application program being resident on the hard disk drive 2110 of the computer system 2100 and being read and controlled in its execution by the processor 2105 of the computer system, as will be described in detail below. The process of Fig. 17 begins at step 1701, where the curve to be polygonised is accessed by the processor 2105. At the next step 1703, a stroke width is estimated for the shape described by the accessed curve. The stroke width for the shape can be estimated as described above. For example, an approximation of stroke width for the shape can be made by considering run lengths between key points on the particular curve. The process continues at the next step 1705 where an edge of the curve is selected by the processor 2105. At the next step 1707, the key points for the selected edge are 20 determined. The process continues at the next step 1709, where the processor 2105 determines influence values for the key points. Influence values indicate the estimated i' stroke width of the shape described by the closed curve. The influence values are initially set to the stroke width determined at step 1703. Alternatively, the influence value can be equal to the minimum of: 25 run length to a previous key point; run length to a next key point; or 578760.doc -13estimated stroke width.

Figs. 18(a), and will be used to describe the influence point. Figs. 18(a), and show three curve runs 1801, 1804, 1807 between the curve key points (1811, 1813), (1813, 1815) and (1811, 1815), respectively. The influence of each key point is indicated by the radius of a circle (eg. 1802), drawn with the particular key point (eg.

1811) at the centre. The influence values 1802 and 1803 are both limited to their common run length due to their proximity to each other. In accordance with the example of Figs. 18(a), and influence value 1805 is the same as value 1803 as it is associated with the same control point 1813, whilst influence values 1806 and 1808 belong to the same key point 1815. Further, influence values 1806 and 1808 indicate the estimated stroke width of the shape described by the curve runs 1801, 1804, 1807 since neither run length 1804 nor 1807 adjoining the values 1806, 1808 is less than the values 1806, 1808.

At the next step 1711, a curve run is selected for the chosen edge by the processor 2105. The process continues at the next step 1713, where interior vertices for the run are generated from the end points of the run. As an example, the curve run 1804 is shown in Figs. 18(d) and The end point influences 1805 and 1806 are intersected with the run to give polygon vertices 1810 and 1811 as seen in Fig. 18(d). The curve run 1804 is then shortened so that the points 1810 and 1811 become the run 1804 end 20 key) points. The new influence value 1812 and 1813 for the points 1810 and 1811 are determined based on the influence values 1805 and 1806, respectively, that created them.

i* The new influence values 1812 and 1813 tend towards the estimated stroke width, so if the creating influence value 1, (1816) is less than the estimated stroke width, the new influence value I (1817) is a value in the range between the old influence value and the estimated stroke width. Any suitable interpolating function, such as linear midpoint 578760.doc -14interpolation, can be used to determine the new influence value as long as the new influence value tends towards the estimated stroke width.

The new influence values 1812 and 1813 are intersected with the curve run 1804 to give new polygonal vertices 1814 and 1815 that then become the end points of the run.

The vertices 1814 and 1815 are approximately one estimated stroke width apart so the division process can end and the polygonal vertices for this run 1804 can be determined as vertices 1814 and 1815.

The process of Fig. 17 continues at step 1715, where a determination is made as to whether the vertices determined at step 1713 are too close together. This determination is made on the basis of a predetermined threshold (eg. 50% of the stroke width). If the result of the determination at step 1715 is true then the process proceeds to step 1717 where the vertices are merged. As an example, Figs. 19(a), and show an example of a path terminating condition that results from the final division of a run 1901. The polygonised run 1907 has two vertices 1904 and 1905 that are close to each other within a predetermined threshold as seen in Fig. 19(b). The vertices 1904 and 1905 can be *o0o combined to form a single vertex 1906, as seen in Fig. 19(c), and the division process can terminate for the run 1901.

o.

As a further example, Figs. 20(a), and show a path terminating condition that results from the division of the curve run 2001. The first division of the run 2001 0 0 0o.o-o 20 results in two vertices 2004 and 2005 as seen in Fig. 20(b). The vertices 2004 and 2005 are close to the opposing end points 2007 and 2008 within a predetermined threshold (eg of the end point influence). The vertices 2004 and 2005 can be combined with the end points 2007 and 2008 to leave no interior vertices along the resulting line segment 2006, as seen in Fig. 20(c), and the division process terminates for the curve run 2001.

If the result of the determination at step 1715 is false then the process proceeds to step 1719 where the run is shortened as described above, and the vertices determined at 578760.doc step 1713 will thus form two vertices on the polygonised curve. The two line segments between each of the key points and the associated vertices will therefore form the polygonised curve. At the next step 1721, new end points are assigned by the processor 2105 for the vertices determined at step 1713 and new influence values are determined for the end points. The process then returns to step 1713.

After the vertices are merged at step 1717, the process proceeds to step 1723, where a check is performed to determine whether there are any more runs to be processed. If there are more runs to be processed then the process returns to step 1711.

Otherwise the process proceeds to step 1725 where if there are more edges to be processed the process returns to step 1705. The process concludes when all edges of the curve have been processed.

Fig. 2 shows the polygon vertices described by the outline curves 101 after being converted into line segments (ie. polygonised). The vertices of the polygonised outline curves are defined by original on-curve knot points (eg. 201), inflection points (eg. 202), oe and additional points (eg. 203) added to reduce line segments to approximately length S (ie. the stroke width for the polygon).

Returning to the process of Fig. 16, at the next step 1605, the closed planar 00 0: curves are triangulated by the processor 2105 to produce a network of cells. For example, Fig. 3 shows a triangulation 301 of the polygon formed by the closed planar curves 101.

0o..0 20 The triangulation 301 can be achieved using any known triangulation method such as "Delaunay Triangulation", provided that only interior triangles are produced. A triangle is considered to be interior if at least one of each pair of edges emanating from each vertex of the subject triangle projects towards the interior of the shape.

At the next step 1607, the network of cells, formed by the triangulation at step 1605, is collapsed and each cell is classified, in accordance with the methods described herein. The cells are collapsed depending on the end-points associated with each cell, as 578760.doc -16will be explained in further detail in the following paragraphs. Further, each cell is classified as one of either singleton, a stroke end, an n-junction or an intermediate cell.

Examples of cells classified in accordance with these classifications are shown in Figs.

4(a) to where solid lines indicate cell edges that border the exterior of the shape and dotted lines indicate interior cell edges that join neighbouring cells.

Fig. 4(a) shows a shape composed of a single cell 401 the dot on an which is classified as singleton. The cell 401 has a sharp end. Similarly, Fig. 4(b) shows a shape composed of a single cell 402 which is classified as singleton, however, the cell 402 has a square end. A stroke formed within a singleton cell begins and ends in that particular cell.

Fig 4(c) shows a shape composed of a single cell 403 with a stroke end point, •where the cell 403 has a sharp end. Similarly, Fig. 4(d) shows a shape composed of a single cell 404 with a stroke end point, however, the cell 404 has a square end. A stroke formed within a stroke end cell begins or ends in that particular cell and will grow exterior to that particular cell.

Fig. 4(e) shows an example of a cell 409 where a stroke 411 passes through the cell 409 and continues. The cell 409 is classified as intermediate.

o• .o Figs. 4(f) to show examples of cells where two or more stroke ends meet at a point. These cells are termed junction' cells, where indicates the number of stroke 0:0"i 20 ends which meet at the point within the cell. For example, Fig. 4(f) shows a 3-junction cell 405, Fig. 4(g) shows a 2-junction cell 406, Fig. 4(h) shows a 4-junction cell 407 and Fig. 4(i) shows a 5-junction cell 408. The cells shown in Figs. 4(a) to are examples only, and any n-junction cell where n 2 is possible.

Strokes begin at a stroke end cell or junction, then pass continuously through intermediate cells until another stroke end or junction is encountered. In accordance with 578760.doc -17the methods described herein, strokes do not pass through junctions and junctions act as meeting places that record the joined strokes. For example, Fig. 5 shows two triangles 501 and 502 which share a common edge 511. The triangles 501, 502 have in total three exterior edges (eg. 503) and have substantially right angled internal angles 508, 509. The triangles 501, 502 are collapsed to form a four sided cell 504 with a square end formed by the enclosed edge 505. The stroke 506 begins at the midpoint of the enclosed edge 505 between the two internal angles 508 and 509, then passes through the midpoint of the opposite edge 507 to continue to a neighbouring cell. In some instances, strokes can pass through junctions.

In accordance with the methods described herein, triangles which result from the triangulation process at step 1605 can be collapsed at step 1607 to form triangular cells singleton, stroke end, intermediate, 3-junction), square cells (ie. singleton, stroke end, i 2-junction or corner, 4-junction) or n-sided cells (ie. n-junctions).

Fig. 6 shows a sharp triangular comer 601 that forms a three sided cell 604 after triangulation. The stroke starts at the internal corner 602 then passes through the .oo.oi midpoint of the opposite edge 603 to continue to a neighbouring cell.

Figs. 7, 8 and 9 below will be used to describe how cells are collapsed in accordance with the methods described herein.

Fig. 7 shows two triangles 701 and 702 that share an edge 704 but have no 20 external edges. The triangles 701 and 702 are collapsed to form a single four sided cell 703 where the cell 703 forms a 4-junction.

Fig. 8 shows two triangles 801 and 802 that share an edge 804 where the triangle 802 has two adjacent external edges 805 and 806. The triangles 801 and 802 can be collapsed to form a single cell 803, as seen in Fig. 8, where the cell 803 is classified as a 2-junction (ie. a corner) cell.

578760.doc -18- Fig. 9 shows three triangles 901, 902 and 903 that share edges with each other such that any triangle in the group is joined to any other by common triangles. However, the triangles 901, 902 and 903 do not have any external edges. The three triangles 901, 902 and 903 can be collapsed to a single 5-sided cell that forms a 5-junction cell 904, as seen in Fig. 9. Similarly, any n-triangles which share edges with each other such that any triangle in the group is joined to any other by common triangles, but have no external edges, can be collapsed to an "(n+2)-sided" cell that forms an (n+2)-junction.

Returning to the example of Figs. 1 to 3, Fig. 10 shows the key cells 1001, 1002, 1003 and 1004 produced by the triangulation of the polygon formed by the curves 101 of Fig. 1. Key cells (eg. 1001) are those cells at which strokes, to be formed in the following steps 1609 to 1619 of Fig. 16, will begin and end. The key cells 1001-1004 are classified as square stroke ends (ie. 1001, 1002) and 3-junctions (ie. 1003, 1004).

Fig. 11 shows the cells (eg. 1104) resulting from the collapse, at step 1607, of the network of cells formed by the triangulation at step 1605. The resulting cells of Fig. 11 are shown with all polygonal vertices (eg. 1101), internal edge midpoints (eg. 1102) and square stroke end midpoints 1103 indicated. Intermediate cells (eg. 1104) can be identified in accordance with the example as 3-sided cells with one external and two oointernal edges.

Continuing the process of Fig. 16, at steps 1609 to 1619, strokes are formed from the internal midpoints of cells resulting from step 1607. The process of steps 1609 to 1619 starts at an internal midpoint which is situated at either an unused stroke end or an unused junction side. At step 1609 a check is performed by the processor 2105 to determine whether the stroke end is unused. If the result of step 1609 is false then the process proceeds to step 1611 where a check is performed to determine whether the junction side is unused.

578760.doc -19- If the result of either steps 1609 or 1611 is true then the process proceeds to step 1613, where a new stroke is started at the internal midpoint of the unused stroke end or junction side. The stroke is grown until the stroke reaches a neighbouring cell. At step 1615, a check is performed to determine whether the neighbouring cell is intermediate. If the result of step 1615 is true then the process proceeds to step 1617, where the stroke is grown through the neighbouring cell until the next neighbouring cell is reached and the process returns to step 1615.

If the result of step 1615 is false then the process proceeds to step 1619, where the stroke ends. After step 1619, the process returns to step 1609 where the next internal midpoint is checked by the processor 2105 to determine whether the midpoint is situated at an unused stroke end. The process of Fig. 16 ends when all of the strokes have been extracted from the internal midpoints of the cells formed at step 1607.

Fig. 12 shows the polygon of Fig. 1 with strokes formed in steps 1609 to 1619, o..

from internal midpoints of the cells resulting from the process of steps 1601 to 1607. For example, the stroke 1202 starts at the top square stroke end 1201, continues through intermediate cells 1203 and 1204, and terminates at the 3-junction cell 1205.

The strokes of Fig. 12 can be simplified, as shown in Fig. 13, to form the resulting strokes 1301, 1302, 1303 and 1304, connected by the two junction cells 1305 and 1306. The result of the stroke extraction process of Fig. 16 is therefore a set of strokes and a set of n-junctions each of which contains a list of the n strokes that meet at the particular junction.

Points on the original outline curve 101 can be mapped to the strokes of Fig. 13.

For example, Fig. 14 shows a stroke 1401 formed by outline edge segments 1402 and 1403, which is parameterised to the range from time t=0 1404 to t=l 1405. Outline point P 1406 can be mapped to coordinates relative to the stroke 1401 where u t is the displacement along the stroke 1407, and v perpendicular 1408 is the distance from the 578760.doc stroke 1409. The coordinates can be used to exactly reconstruct the curve outlines from the strokes. Even if strokes are modified, such as during a morphing operation, an accurate outline relative to the strokes can be derived.

Figs. 15(a) and will be used to show one of the advantages of the preferred method described above over the methods disclosed by the prior art. Given the shape 'p' 1500, as seen in Fig. 15(a), the prior art methods would detect two strokes with a single junction 1501, as shown in Fig. 15(a). The single junction 1501 is overly simplified and loses topological and positional information about the manner in which the arc 1504 joins relative to the straight stroke 1505. In contrast Fig. 15(b) shows the result of processing the shape p 1500 in accordance with the preferred method. The preferred method produces a set of strokes containing information that describes topological relationships between strokes and junctions and, in accordance with the example of Figs. 15(a) and produces two junctions 1502 and 1503.

The aforementioned preferred method comprises a particular control flow. There are many other variants of the preferred method which use different control flows without departing the spirit or scope of the invention. Furthermore one or more of the steps of the preferred methods may be performed in parallel rather sequentially.

The method of converting a closed planar curve into a set of strokes is preferably practiced using a general-purpose computer system 2100, such as that shown in Fig. 21 20 wherein the processes of Figs. 1 to 20 can be implemented as software, such as an application program executing within the computer system 2100. In particular, the steps of method of converting a closed planar curve into a set of strokes are effected by •ooo instructions in the software that are carried out by the computer. The software may be a.

divided into two separate parts; one part for carrying out the preferred method; and another part to manage the user interface between the latter and the user. The software may be stored in a computer readable medium, including the storage devices described 578760.doc -21below, for example. The software is loaded into the computer from the computer readable medium, and then executed by the computer. A computer readable medium having such software or computer program recorded on it is a computer program product.

The use of the computer program product in the computer preferably effects an advantageous apparatus for converting a closed planar curve into a set of strokes.

The computer system 2100 comprises a computer module 2101, input devices such as a keyboard 2102 and mouse 2103, output devices including a printer 2115 and a display device 2114. A Modulator-Demodulator (Modem) transceiver device 2116 is used by the computer module 2101 for communicating to and from a communications network 2120, for example connectable via a telephone line 2121 or other functional medium. The modem 2116 can be used to obtain access to the Internet, and other network systems, such as a Local Area Network (LAN) or a Wide Area Network (WAN).

The computer module 2101 typically includes at least one processor unit 2105, a memory unit2106, for example formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output interfaces including a video interface 2107, and an 11 interface 2113 for the keyboard 2102 and mouse 2103 and optionally a joystick (not illustrated), and an interface 2108 for the modem 2116. A storage device 2109 is provided and typically includes a hard disk drive 2110 and a floppy disk drive 2111. A magnetic tape drive (not illustrated) may also be used. A CD- 20 ROM drive2112 is typically provided as a non-volatile source of data. The components 2105 to 2113 of the computer module 2101, typically communicate via an interconnected bus 2104 and in a manner which results in a conventional mode of operation of the computer system 2100 known to those in the relevant art. Examples of computers on which the described arrangements can be practised include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.

578760.doc -22- Typically, the application program is resident on the hard disk drive 2110 and read and controlled in its execution by the processor 2105. Intermediate storage of the program and any data fetched from the network 2120 may be accomplished using the semiconductor memory 2106, possibly in concert with the hard disk drive 2110. In some instances, the application program may be supplied to the user encoded on a CD-ROM or floppy disk and read via the corresponding drive 2112 or 2111, or alternatively may be read by the user from the network 2120 via the modem device 2116. Still further, the software can also be loaded into the computer system 2100 from other computer readable medium including magnetic tape, a ROM or integrated circuit, a magneto-optical disk, a radio or infra-red transmission channel between the computer module 2101 and another device, a computer readable card such as a PCMCIA card, and the Internet and Intranets •including email transmissions and information recorded on websites and the like. The foregoing is merely exemplary of relevant computer readable mediums. Other computer readable media may alternately be used.

The method of converting a closed planar curve into a set of strokes may a *-*alternatively be implemented in dedicated hardware such as one or more integrated circuits performing the functions or sub functions of Fig. 16. Such dedicated hardware •may include graphic processors, digital signal processors, or one or more microprocessors and associated memories.

-:Oti 20 The foregoing describes only some embodiments of the present invention, and modifications and/or changes can be made thereto without departing from the scope and spirit of the invention, the embodiments being illustrative and not restrictive.

In the context of this specification, the word "comprising" means "including principally but not necessarily solely" or "having" or "including" and not "consisting only of'. Variations of the word comprising, such as "comprise" and "comprises" have corresponding meanings.

578760.doc

Claims (4)

1. A method of converting a closed curve into a set of strokes describing said curve, said method comprising the steps of: determining line segments describing said curve based on at least one point on said curve and on a stroke width of said curve; forming at least one triangle interior to said curve, said triangle including at least one edge being defined by at least one of said line segments; modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; classifying each of said cells according to predetermined classifications; and 0e° °forming strokes interior to said cells depending on a classification of each of said o cells. J o

2. The method according to claim 1, wherein each of said cells are classified as one of a singleton, a stroke end, a junction, or an intermediate cell. c• o

3. The method according to claim 1, wherein said modification of a triangle is dependent on end-points of a line segment associated with said triangle.

4. The method according to claim 2, wherein a stroke formed interior to a singleton cell begins and ends in said singleton cell. The method according to claim 2, wherein a portion of a stroke formed in relation to a stroke end point cell, is exterior to said stroke end point cell.

578760.doc -24- 6. The method according to claim 2, wherein a stroke formed in relation to an intermediate cell, includes at least a portion which is exterior to said intermediate cell. 7. The method according to claim 2, wherein a junction cell is defined as a cell where two or more strokes meet. 8. The method according to claim 1, including the further step of determining an influence value for each of said points depending on said stroke width. 9. The method according to claim 8, including the further step of determining vertices on said curve utilising said influence values. The method according to claim 8, wherein said line segments are based on said vertices. 11. The method according to claim 9, including the further step of merging said vertex to form a single vertex if said vertices are less than a predetermined threshold distance apart. I°o°° S 20 12. The method of claim 11, wherein said predetermined threshold distance is dependent on said stroke width. *i i 13. The method according to claim 9, including the further step of determining influence values for each of said vertices. 578760.doc 14. The method according to claim 13, wherein the influence values determined for each of said vertices are determined using an interpolation process The method according to claim 1, wherein said stroke width is dependent on at s least one of a distance between said points or another closed curve related to said closed curve. 16. A method of converting a closed curve into a set of strokes describing said curve, said method comprising the steps of: forming at least one triangle interior to said curve, said triangle including at least one edge being defined by a line segment describing said curve; modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; classifying each of said cells according to predetermined classifications; and forming strokes interior to said cells depending on a classification of each of said cells. 17. An apparatus for converting a closed curve into a set of strokes describing said curve, said apparatus comprising: 20 determination means for determining line segments describing said curve based on at least one point on said curve and on a stroke width of said curve; first forming means for forming at least one triangle interior to said curve, said :*triangle including at least one edge being defined by at least one of said line segments; modification means for modifying said triangles depending on line segments 0 25 associated with each of said triangles, to form at least one cell interior to said curve; 0:•oo: 578760.doc -26- classification means for classifying each of said cells according to predetermined classifications; and second forming means for forming strokes interior to said cells depending on a classification of each of said cells. 18. The apparatus according to claim 17, wherein each of said cells are classified as one of a singleton, a stroke end, ajunction, or an intermediate cell. 19. The apparatus according to claim 17, wherein said modification of a triangle is 10 dependent on end-points of a line segment associated with said triangle. 20. The apparatus according to claim 18, wherein a stroke formed interior to a singleton cell begins and ends in said singleton cell. 21. The apparatus according to claim 18, wherein a portion of a stroke formed in S•relation to a stroke end point cell, is exterior to said stroke end point cell. 22. The apparatus according to claim 18, wherein a stroke formed in relation to an .ooooi intermediate cell, includes at least a portion which is exterior to said intermediate cell. 23. The apparatus according to claim 18, wherein a junction cell is defined as a cell where two or more strokes meet. 24. The apparatus according to claim 17, further comprising means for determining an influence value for each of said points depending on said stroke width. 578760.doc -27- The apparatus according to claim 24, further comprising means for determining vertices on said curve utilising said influence values. 26. The apparatus according to claim 24, wherein said line segments are based on said vertices. 27. The apparatus according to claim 25, further comprising means for merging said vertex to form a single vertex if said vertices are less than a predetermined threshold distance apart. 28. The apparatus of claim 27, wherein said predetermined threshold distance is dependent on said stroke width. 29. The apparatus according to claim 25, further comprising means for determining influence values for each of said vertices. 30. The apparatus according to claim 29, wherein the influence values determined for each of said vertices are determined using an interpolation process o 000 0000 0. 20 31. The apparatus according to claim 17, wherein said stroke width is dependent on at least one of a distance between said points or another closed curve related to said closed curve. 32. An apparatus for converting a closed curve into a set of strokes describing said 25 curve, said apparatus comprising: 25 curve, said apparatus comprising: 578760.doc -28- first forming means for forming at least one triangle interior to said curve, said triangle including at least one edge being defined by a line segment describing said curve; modification means for modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; classification means for classifying each of said cells according to predetermined classifications; and second forming means for forming strokes interior to said cells depending on a classification of each of said cells. 10 33. A program for converting a closed curve into a set of strokes describing said curve, said program comprising: code for determining line segments describing said curve based on at least one point on said curve and on a stroke width of said curve; code for forming at least one triangle interior to said curve, said triangle including at least one edge being defined by at least one of said line segments; S"code for modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; code for classifying each of said cells according to predetermined classifications; and code for forming strokes interior to said cells depending on a classification of each of said cells. 34. The program according to claim 33, wherein each of said cells are classified as one of a singleton, a stroke end, a junction, or an intermediate cell. 578760.doc -29- The program according to claim 33, wherein said modification of a triangle is dependent on end-points of a line segment associated with said triangle. 36. The program according to claim 34, wherein a stroke formed interior to a singleton cell begins and ends in said singleton cell. 37. The program according to claim 34, wherein a portion of a stroke formed in relation to a stroke end point cell, is exterior to said stroke end point cell. 38. The program according to claim 34, wherein a stroke formed in relation to an intermediate cell, includes at least a portion which is exterior to said intermediate cell. 39. The program according to claim 34, wherein a junction cell is defined as a cell where two or more strokes meet. The program according to claim 33, further comprising code for determining an influence value for each of said points depending on said stroke width. 0• 41. The program according to claim 40, further comprising code for determining 20 vertices on said curve utilising said influence values. 42. The program according to claim 40, wherein said line segments are based on said ••go vertices. 578760.doc 43. The program according to claim 41, further comprising code for merging said vertex to form a single vertex if said vertices are less than a predetermined threshold distance apart. 44. The program of claim 43, wherein said predetermined threshold distance is dependent on said stroke width. The program according to claim 41, further comprising code for determining influence values for each of said vertices. 46. The program according to claim 45, wherein the influence values determined for each of said vertices are determined using an interpolation process 47. The program according to claim 33, wherein said stroke width is dependent on at least one of a distance between said points or another closed curve related to said closed curve. 48. A program for converting a closed curve into a set of strokes describing said curve, said program comprising: S 20 code for forming at least one triangle interior to said curve, said triangle including at least one edge being defined by a line segment describing said curve; ~code for modifying said triangles depending on line segments associated with each of said triangles, to form at least one cell interior to said curve; 99• code for classifying each of said cells according to predetermined classifications; .99. 2 25 and 578760.doc -31 code for forming strokes interior to said cells depending on a classification of each of said cells. 49. The program according to any one of claims 33 to 48, wherein said program is stored in a memory means of an apparatus and said program is executed by a processor configured within said apparatus. A method of converting a closed planar curve into a set of strokes describing said curve, said method being substantially as herein described with reference to any one of the embodiments as illustrated in Figs. 1 to 51. An apparatus for converting a closed planar curve into a set of strokes describing said curve, said apparatus being substantially as herein described with reference to any one of the embodiments as illustrated in Figs. 1 to 52. A program for converting a closed planar curve into a set of strokes describing said curve, said program being substantially as herein described with reference to any one 0 of the embodiments as illustrated in Figs, 1 to DATED this Eigteenth Day of December 2001 Canon Kabushiki Kaisha Patent Attorneys for the Applicant SPRUSON&FERGUSON 578760.doc