AU769689B2 - Converting a Bitmap Image Comprising at Least One Region to a Segment Representation - Google Patents

Description

S&FRef: 580467

I

AUSTRALIA

PATENTS ACT 1990 COMPLETE SPECIFICATION FOR A STANDARD PATENT

ORIGINAL

Name and Address of Applicant: Actual Inventor(s): Address for Service: Invention Title: Canon Kabushiki Kaisha 30-2, Shimomaruko 3-chome, Ohta-ku Tokyo 146 Japan Timothy Merrick Long Christopher Fraser Spruson Ferguson St Martins Tower,Level 31 Market Street Sydney NSW 2000 (CCN 3710000177) Converting a Bitmap Image Comprising at Least One Region to a Segment Representation 0 0 0.:0.0 0. 0. ASSOCIATED PROVISIONAL APPLICATION DETAILS [33] Country [31] Applic. No(s) AU PR2335 [32] Application Date 28 Dec 2000 The following statement is a full description of this invention, including the best method of performing it known to me/us:- 5815c 11 11 1-1- i -1- CONVERTING A BITMAP IMAGE COMPRISING AT LEAST ONE REGION TO A SEGMENT REPRESENTATION Technical Field of the Invention The present invention relates generally to converting a bitmap image comprising at least one region to a segment representation of outlines of said at least one region and, in particular, to converting a bitmap image of a character to a segment representation of the outlines of that character. The invention also relates to rendering a bitmap image comprising at least one region.

Background Traditionally there are two techniques for defining characters, which are to be rendered on a display device, such as a printer or display screen. The most general way is to define each character as a curved or polygonal outline and to scan convert as needed. 9% The other way is to specify the character as a small bitmap image and copy it into a frame buffer as required. Another technique that combines the best of both methods is to store the fonts in outline form and to convert the ones being used in a given application to their bitmap equivalents, that is to build a font cache on the fly. 0 In recent years object based rendering systems have become popular. Typically, many of these object based rendering systems receive characters as outlines. However, some applications and/or operating systems generate characters as bitmap images and thus are not compatible to be used with these object based rendering systems.

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.

According to one aspect of the invention, there is provided a method of rendering a first bitmap image, the method comprising; detecting, for each scanline of a second bitmap image, edge crossings of at least one region comprising pixels having a uniform colour, wherein the edge crossings are those edges of pixels of the second bitmap image that border the at least one region and that are transverse to the scanlines; generating active edges of the at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an 524206.doc outline of the at least one region and that do not cross over said at least one region; generating a segment representation of the outlines of the at least one region from said generated active edges; and rendering said first bitmap image from the segment representation of said outlines of said at least one region using an edge-based scanline graphics object rendering system.

According to another aspect of the invention, there is provided a method of converting a bitmap image comprising at least one region having uniform colour characteristics to a segment representation of outlines of said at least one region, the method comprising; detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating means comprises a sub-step for comparing and processing a current pair of first and second active edges and a current pair of first and second edge crossings, and the sub-step for comparing and processing comprises the sub-steps of: terminating said current pair of active edges at said previous scanline, if the current pair of active edges terminate at the previous scanline prior to a current pair of first and second edge crossings; creating a 20 new pair of active edges starting at the current pair of edge crossings, if the current pair of o.

edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges; creating new active edges at the current scanline of those inside edges of the arch-shaped region, if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region; and terminating the current pair of active o 25 edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region, if the current pairs of edge crossings and active edges form part of an upside down arch-shaped bitmap region; generating a segment representation of the S°outlines of the at least one region from said generated active edges.

According to still another aspect of the invention, there is provided a method of converting a bitmap image comprising at least one region having uniform colour 524206.doc characteristics to a segment representation of outlines of said at least one region, the method comprising; detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating step comprises: a comparison sub-step for comparing a current pair of first and second active edges and a current pair of first and second edge crossings, wherein said comparison step comprises the sub-steps of: determining if a current pair of first and second adjacent active edges terminate at the previous scanline prior to a current pair of first and second adjacent edge crossings, and if so terminating said current active edges in said previous scanline and setting the current pair of first and second adjacent active edges to a next pair of first and second adjacent active edges in the previous scanline and proceeding to sub-step otherwise proceeding to sub-step determining if the current pair of edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges, and if so creating a new pair of active edges starting at the current pair of edge crossings and setting the current pair of first and second edge crossings to a next pair of first and second adjacent edge crossings in the current scanline and proceeding to sub-step otherwise matching the first edge crossing to the first active edge, and setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and then proceeding to sub-step determining if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region and if so creating new active edges at the current scanline of those inside edges of the arch-shaped region and setting the current pair of first and second edge crossings to a next pair of first and second adjacent edge crossings in the current scanline and repeating sub-step otherwise proceeding to sub-step and determining if the current pairs of edge crossings and 524206.doc o 1 'A 1 -4active edges form part of an upside down arch-shaped bitmap region and if so terminating the active edges at the previous scanline of those inside edges of the upside down archshaped bitmap region and setting the current pair of first and second active edges to a next pair of first and second adjacent active edges in the previous scanline not previously eliminated and repeating sub-step otherwise matching the first edge crossing to the first active edge, setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and proceeding to sub-step and returning to sub-step if there are one or more edge crossings not matched or created as active edges in the current scanline; generating a segment representation of the outlines of the at least one region from said generated active edges.

According to still another aspect of the invention, there is provided apparatus for rendering a first bitmap image, the apparatus comprising; means for detecting, for each scanline of a second bitmap image, edge crossings of at least one region comprising pixels having a uniform colour, wherein the edge crossings are those edges of pixels of the second bitmap image that border the at least one region and that are transverse to the L *o scanlines; means for generating active edges of the at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region and that do not cross over said at least one region; means for generating a segment representation of the outlines of the at least one region from said generated active edges; and means for rendering said first bitmap image from the segment representation of said outlines of said at least one region using an edged-based scanline graphics object rendering system.

According to still another aspect of the invention, there is provided apparatus for converting a bitmap image comprising at least one region having uniform colour characteristics to a segment representation of outlines of said at least one region, the apparatus comprising; means for detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels 524206.doc of the bitmap image that border the at least one region and that are transverse to the scanlines; means for generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating means comprises means for comparing and processing a current pair of first and second active edges and a current pair of first and second edge crossings, said comparing and processing means comprising: first means for terminating said current pair of active edges at said previous scanline, if the current pair of active edges terminate at the previous scanline prior to a current pair of first and second edge crossings; second means for creating a new pair of active edges starting at the current pair of edge crossings, if the current pair of edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges; third means for creating new active edges at the current scanline of those inside edges of the arch-shaped region, if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region; and fourth means for terminating the current pair of active edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region, if the current pairs of edge crossings and active edges form part of an upside down arch-shaped bitmap region; means for generating a segment representation of the outlines of the at least one region from said generated active edges. According to still another aspect of the invention, there is provided apparatus for converting a bitmap image comprising at least one region having uniform colour characteristics to a segment representation of outlines of said at least one region, the apparatus comprising; means for detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; means for generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating means comprises means for comparing and processing a current pair of first and second active edges and a current pair of first and second edge crossings, wherein 524206.doc -6said comparison and processing means comprises: first means for determining if a current pair of first and second adjacent active edges terminate at the previous scanline prior to a current pair of first and second adjacent edge crossings, and if so terminating said current active edges in said previous scanline and setting the current pair of first and second adjacent active edges to a next pair of first and second adjacent active edges in the previous scanline and proceeding to the fifth means, otherwise proceeding to the second means; second means for determining if the current pair of edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges, and if so creating a new pair of active edges starting at the current pair of edge crossings and setting the current pair of first and second edge crossings to a next pair of first and second adjacent edge crossings in the current scanline and proceeding to the fifth means, otherwise matching the first edge crossing to the first active edge, and setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and then proceeding to the third means; third means for determining if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region and if so creating new active edges at the current scanline of those inside edges of the arch-shaped region and setting the current pair of first and second edge crossings to a next pair of first and second adjacent edge crossings in the current scanline and repeating the operations of the third means, otherwise proceeding to the fourth means; and fourth means for determining if the current pairs of edge crossings and active edges form part of an upside down arch-shaped bitmap region and if so terminating the active edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region and setting the current pair of first and second active edges to a next pair of first and second adjacent active edges in the previous scanline not previously eliminated and repeating the operations of the third means, otherwise matching the first edge crossing to the first active edge, setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to 524206.doc the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and proceeding to the fifth means; and fifth means for returning to the first means if there are one or more edge crossings not matched or created as active edges in the current scanline; means for generating a segment representation of the outlines of the at least one region from said generated active edges.

According to still another aspect of the invention, there is provided a computer program for rendering a first bitmap image, the computer program comprising; code for detecting, for each scanline of a second bitmap image, edge crossings of at least one region comprising pixels having a uniform colour, wherein the edge crossings are those edges of pixels of the second bitmap image that border the at least one region and that are transverse to the scanlines; code for generating active edges of the at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region and that do not cross over said at least one region; code for generating a segment representation of the outlines of the at least one region from said generated active edges; and code for rendering said first bitmap image from the segment representation of said outlines of said at least one region using an edged-based scanline graphics object rendering system.

According to still another aspect of the invention, there is provided a computer program for converting a bitmap image comprising at least one region having uniform colour characteristics to a segment representation of outlines of said at least one region, the computer program comprising; code for detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; code for generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating code comprises code for comparing and processing a current pair of first and second active edges and a current pair of first and second edge crossings, the code for comparing and processing comprising; first code for terminating said current pair 524206.doc of active edges at said previous scanline, if the current pair of active edges terminate at the previous scanline prior to a current pair of first and second edge crossings; second code for creating a new pair of active edges starting at the current pair of edge crossings, if the current pair of edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges; third code for creating new active edges at the current scanline of those inside edges of the arch-shaped region, if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region; and fourth code for terminating the current pair of active edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region, if the current pairs of edge crossings and active edges form part of an upside down arch-shaped bitmap region; code for generating a segment representation of the outlines of the at least one region from said generated active edges.

According to still another aspect of the invention, there is provided a computer program for converting a bitmap image comprising at least one region having uniform colour characteristics to a segment representation of outlines of said at least one region, the computer program comprising; code for detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; code for generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating code comprises code for comparing and processing a current pair of first and second active edges and a current pair of first and second edge crossings, wherein said comparison and processing code comprises: first code for determining if a current pair of first and second adjacent active edges terminate at the previous scanline prior to a current pair of first and second adjacent edge crossings, and if so terminating said current active edges in said previous scanline and setting the current pair of first and second adjacent active edges to a next pair of first and second adjacent active edges in the previous scanline and proceeding to the fifth code, otherwise proceeding to the second code; second code for determining if the current pair of edge crossings form a new pair of 524206.doc -9active edges in the current scanline prior to the current pair of active edges, and if so creating a new pair of active edges starting at the current pair of edge crossings and setting the current pair of first and second edge crossings to a next pair of first and second adjacent edge crossings in the current scanline and proceeding to the fifth code, otherwise matching the first edge crossing to the first active edge, and setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and then proceeding to the third code; third code for determining if the current pairs of edge crossings and active edges form part of an archshaped bitmap region and if so creating new active edges at the current scanline of those inside edges of the arch-shaped region and setting the current pair of first and second edge crossings to a next pair of first and second adjacent edge crossings in the current scanline and repeating the operations of the third code, otherwise proceeding to the fourth code; and fourth code for determining if the current pairs of edge crossings and active edges form part of an upside down arch-shaped bitmap region and if so terminating the active edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region and setting the current pair of first and second active edges to a next pair ofo first and second adjacent active edges in the previous scanline not previously eliminated and repeating the operations of the third code, otherwise matching the first edge crossing to the first active edge, setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and proceeding to the fifth code; and fifth code for returning to the first code if there are one or more edge crossings not matched or created as active edges in the current scanline; code for generating a segment representation of the outlines of the at least one region from said generated active edges.

Brief Description of the Drawings 524206.doc A number of embodiments of the present invention will now be described with reference to the drawings, in which: Fig. 1 is a block diagram showing an overview of the functional operation of a process of rendering graphic objects including a bitmap image of a character, the process being in accordance with a first arrangement; Fig. 2 is a block diagram showing an overview of the functional operation of the method 102 of Fig. 1 in more detail; Figs. 3 is a flowchart of the sub-process 206 of Fig. 2 in more detail; Fig. 4 is a diagram of a portion of an example bitmap image for illustrating "Exterior case 1" in Fig. 3; Fig. 5 is a diagram of a portion of an example bitmap image for illustrating "Exterior case 2" in Fig. 3; Fig. 6 is a diagram of a portion of an example bitmap image for illustrating "Interior case 1" in Fig. 3; Fig. 7 is a diagram of a portion of an example bitmap image for illustrating "Interior case 2" in Fig. 3; Fig 8A illustrates a bitmap image of the character Fig. 8B illustrates the edge crossings detected during the sub-process 204 for the bitmap image as shown in Fig. 8A; o Fig. 8C illustrates the active edges generated'during the sub-process 206 for the edge crossings shown in Fig. 8C; Figs. 9A and 9B, there is shown a flow chart of the sub-process 208 for generating a segment representation 103 from the active edges that follow the contours of the character; Fig. 10 illustrates the three different segments available to produce rendered pixels with respect to an example bitmap; Fig. 11 illustrates an example of the tracking of an inclined vector segment; Fig. 12 is a flow chart of a sub-process 1200 for finishing the generation of segments of an active edge; Fig. 13 is a flow chart of a sub-process 1300 for creating a new active edge; and 524206.doc Fig. 14 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.

The principles of the prefer-red method described herein have general applicability to the conversion of bitmap images to a segment representation of that image. However, for ease of explanation, the steps of the prefer-red method are described with reference to edged based object rendering systems. However, it is not intended that the present invention be limited to the described method. For example, the invention may have application to the converting of scanned images to a segment representation for compression and subsequent storage.

Turning now to Fig. 1, there is shown an overview of the functional operation of a process of rendering graphic objects including a bitmap image of a character, the process being in accordance with a first arrangement. The bitmap image of the character is a bi- tonal image comprising regions of background pixels and foreground pixels, with the foreground pixels forming the character. The process 100 comprises a method 102 for converting bitmap images 101 of characters to a segment representation 103 of those characters. The segment representation 103 of the characters are supplied by the method 102 to a method 104 of rendering graphic objects, which method 104 renders the segment representations 103 of the characters as respective bitmap images together with other noncharacter objects 105 to a display device 107 (not shown), such as a printer or display screen. Any known graphic object rendering system would be suitable for performing the method 104 of rendering the graphic objects. The method 102 would in particular be suitable for association with an edge-based scanline graphics object rendering system.

Turning now to Fig. 2, there is shown a block diagram of an overview of the functional operation of the method 102 of Fig. 1 in more detail. The method 102 comprises a sub-process 204 for detecting the edges of the character in the bitmap image 524206.doc 12- 101, a sul-process 206 for generating from these detected edge crossings 205 a number of sets of matched edge crossings 207 of the character outline, and a sub-process 208 for generating a segment representation 103 from these sets of matched edge crossings 207 that follow the contours of the character.

The sub-process 204 accepts a character bitmap 101 as input. It examines the bitmap one scanline (horizontal row of pixels) at a time, moving from the top of the character to the bottom, (or from the bottom of the character to the top if the character is to be rendered upside-down). This block examines each scanline, and outputting 205 the transitions from non-rendered pixels to rendered pixels background to foreground..

pixels) and vice versa. Preferably, the edge crossing detection speed can be increased by i.

comparing the current scanline with the previous scanline to take advantage of any similarities between the two scanlines.

These transitions, known as 'edge crossings', are then passed 205 on a per scanline basis to the sub-process 206. The sub-process 206 matches edge crossings in the currently scan line being examined with the already partially constructed sets of matched edge crossings that were formed from the analysis of the previous scan lines. For ease of explanation, a set of matched edge crossings is herein referred to as an active edge. The correct match between an active edge and subsequent edge crossing is the one that allows the edge to follow the contour of the character, and which does not allow it to cross over regions of foreground pixels. If the sub-process 206 determines that a current edge crossing in the current scanline matches with an active edge, then that edge crossing is allocated to that active edge. If the sub-process 206 is unable to match the current edge crossing to any active edge, then the sub-process 206 generates a new active edge and allocates the current edge crossing to the new active edge. If however, the sub-process 206 is not able to match an active edge to any edge crossing in the current scanline, then the sub-process 206 does not perform any further matching for this active edge.

Preferably, these active edges are passed 207 to the sub-process 208 for generating a segment representation of the character on a scanline basis with a latency equivalent to a at least three scanlines.

524206.doc -13- The sub-process 208 is called by and receives as input the active edges generated during step 206 on a scanline basis. The sub-process 208 generates segments (using steps and inclined vectors) that follow the contours of the character, and that would produce the pixels required, when rendered by the method 104. These segments are a representation of the active edges with each active edge being represented by one or more segments which will be discussed below in more detail. The sub-process 208 outputs those segments representing an active edge on completion of that active edge.

Preferably, the sub-process 206 stores information concerning partially generated active edges in a linked list in memory herein called the ACTIVE EDGE list. The ACTIVE EDGE list is generated during the main method 102 and is continually being updated during the sub-process 206. The items of the ACTIVE EDGE list correspond to respective active edges that are partially generated during the scanning of the bitmap image. Each item of the ACTIVE EDGE list comprise a buffer for storing the segments generated so far of the corresponding active edge. Each item of the ACTIVE EDGE list

S'

*SSSSS

also comprise information concerning the edge crossings of the corresponding active edge currently being processed for generation of a segment herein called the current segment see* information). The current segment information comprises variables base_x and base_y for respectively storing the x,y co-ordinates of the edge crossing of the active edge which forms the start of the segment currently being processed, a variable tipx which stores the x co-ordinate of the active edge herein called tip) in the scanline previous to the scanline currently being processed, and a variable nscans for storing the number of scanlines between the tipx and basex inclusive. The current segment information also comprises a flag indicating whether the current segment being processed is an inclined vector. The items (active edges) of the ACTIVE EDGE list are ordered in the list according to the active edges position in the bitmap in left to right scanline order. When a new active edge is created by the sub-process 206 it is added to the relevant location in the ACTIVE EDGE list in scanline order and when an active edge is fully generated by the sub-process 206 it is removed from the ACTIVE EDGE list.

Turning now to Figs. 3, there is shown a flowchart of the sub-process 206 of Fig. 2 in more detail. The purpose of the sub-process 206 is to compare (304, 306, 314, and 524206.doc -14- 316) the positions of the active edges of the previous scanline with the positions of the edge crossings in the current scanline by evaluating them against 4 different edge position scenarios.

The sub-process 206 comprises a loop 352 to enable the processing of all the edge crossings within the current scanline. The loop 352 scans the active edges of the previous scan line and edge crossings of the current scanline from left to right until a decision has been made about each one. Active edges are 'eliminated' (not compared further by the sub-process 206 during the current scanline) when they are either matched up with edge crossings continued to the current scanline, or finished not continued to the current scanline. Edge crossings are 'eliminated' (not compared further by the sub-process 206 during the current scanline) when they are either matched up with active edges or created

S

as new active edges. Specifically, the sub-process 206 initially compares the first two adjacent edge crossings (EC1,EC2) in a current scanline with the first two adjacent active edges (AE1,AE2) in the previous scanline. If the sub-process 206 determines that the 0 active edges (AE1, AE2) terminate in the previous scanline, the sub-process 206 finishes processing those active edges (AE1,AE2) and then compares the next two adjacent active edges (AE3,AE4) in the previous scanline in left to right scanline order with the first two adjacent edge crossings (EC1,EC2). However, if the sub-process 206 determines that the first two edge crossings (EC1, EC2) are the start of two new active edges, it creates two new active edges for the current scanline, and then compares the next two adjacent edge crossings (EC3, EC4) in the current scanline in left to right scanline order with the active edges (AE1,AE2) of the previous scanline. However, if the sub-process 206 matches the active edge (AE1) with the edge crossing (EC1), then the sub-process 206 matches this edge crossing (EC1) to the active edge (AE1) and then compares the adjacent edge crossings (EC2,EC3) with the active edges (AE2,AE3), where EC3 is the next edge crossing in the current scanline adjacent to EC2 in left to right scanline order, and AE3 is the next active crossing in the previous scanline adjacent to AE2 in left to right scanline order. The sub-process 206 continues scanning the active edges and edge crossings in this fashion until all the edges have been processed.

524206.doc The sub-process 206 commences at step 300, where any necessary parameters are initialized. The sub-process 206 is called by the main method 102 for each new scanline being processed.

During step 300 an array designated CURRENT_SCANLINE array is generated.

The CURRENTSCANLINE array is one-dimensional array storing the x co-ordinate positions of the edge crossings of the current scanline. The sub-process 206 stores in the CURRENT_SCANLINE array these x co-ordinate positions of the edge crossings in left to right scanline order.

Also during step 300 the sub-process 206 initializes the variables A, B, P, and Q for the current scanline. The variables A, B store the x- co-ordinate positions of two adjacent active edges A and B in the previous scanline to the scanline currently being considered by the sub-process 206. Specifically, the variables A and B are set to the corresponding tip_x values stored in the ACTIVE EDGE list of the two adjacent active edges A and B. The sub-process 206 processes pairs of adjacent active edges in a left to right scanline order and continually updates the variables A, B to the tip_x positions of the currently processed active edges. The variables A, B are initially set to the tip_x values of the first two active edges respectively of the ACTIVE EDGE list prior to commencement of the 9* current scanline. In the event there are no active edges in the ACTIVE EDGE list the variables A, B are set to NULL. This will occur when the sub-process 206 is processing the first scanline as there is no previous scanline.

The variables P, Q store the x- co-ordinate positions of two adjacent edge crossings P, Q in the current scanline. Specifically, the variables P and Q are set to the x coordinate positions stored in two adjacent entries of the CURRENT_SCANLINE array.

The variables P and Q will in most instances also be continually updated during the processing of the current scanline by the sub-process 206. The variables P, Q initially store the x co-ordinate positions of the first two entries respectively of the CURRENTSCANLINE array. In the event there are no edge crossing positions in the CURRENT_SCANLINE array, P and Q are both set to NULL.

524206.doc -16- The sub-process 206 matches the positions of active edges of the previous scanline with the positions of edge crossings of the current scanline by comparing these variables A, B, P and Q.

After the commencement step 300, the sub-process 206 proceeds to the decision block 302, where a check is made whether there are any more edge crossings P, Q in the current scanline to be processed by the sub-process 206. Specifically, the decision block 302 determines whether either one or both of the variables P and Q is not NULL. If the decision block 302 returns TRUE (Yes), the sub-process 206 proceeds to decision block 304 of the loop 352, otherwise the sub-process 206 proceeds to step 324.

The decision block 304, herein called "Exterior Case tests for the first edge position scenario. The decision block 304 compares the two edge crossings P and Q with the active edges A and B. The Exterior Case 1 tests whether these active edges B) are on the left side of the edge crossings namely it tests whether the active edges (A, B) are 'dangling'. Fig. 4 shows a typical example of Exterior Case 1. Current edges A and B are the two dangling active edges that will be finished as a result of testing against i: this example. Specifically, the decision block 304 determines the following conditional statement: If A is not NULL and B is not NULL, and If P> B.

If the decision block 304 returns FALSE (no) to this conditional statement, then the sub-process 206 proceeds to decision block 306. This may occur during the processing of the first scanline when there are no active edges in the ACTIVE EDGE list. On the other hand, if the decision block 304 returns TRUE (yes) the sub-process 206 proceeds to step 312.

During step 312, the sub-process 206 completes the generation of the segments representing the active edges A, B and these completed segments representing the active edges are submitted to the rendering method 104. The step 312 completes this generation by calling the sub-process 1200 for each active edge A and B. This sub-process 1200 will 524206.doc -17be described in more detail below with reference to Fig. 12. After sub-process 1200 is completed for both active edges A and B and removes the active edges A, B from the ACTIVE EDGE list, the step 312 then updates the values for A and B. Specifically, the step 312 sets the variables A and B to the tip_x positions of the next two adjacent active edges in the ACTIVE EDGE list. After completion of step 312, the sub-process 206 proceeds to decision block 302.

The decision block 306, herein called "Exterior Case tests for the second edge position scenario. The decision block 306 again compares these the two edge crossings P and Q with the active edges A and B. The second case, External Case 2, tests whether these edge crossings P, Q are protruding up and further left than the active edges A and B.

Figure 5 shows a typical example of Exterior Case 2. Edge crossings P and Q are the two protruding edge crossings that will be the start of the two new edges as a result of the testing this example. Specifically, the decision block 306 determines the following conditional statement: If( A is not NULL and A Q) or( A NULL and B =NULL) *i If the decision block 306 returns FALSE then the sub-process 206 proceeds to step 308. On the other hand, if the decision block 304 returns TRUE (yes) the subprocess 206 proceeds to step 310. During step 310, the sub-process 206 creates the start of two new active edges at P and Q of the current scanline. The step 312 creates these new active edges by calling the sub-process 1400 for each edge crossing P, Q. This subprocess 1400 will be described in more detail below with reference to Fig. 14. After the sub-process 1400 is completed for both edge crossings P, Q, the step 310 then 'eliminates' the edge crossings P,Q from further comparison during the processing of the current scanline. Namely, the variables P and Q are updated to store the positions of the next two adjacent edge crossings in the CURRENTSCANLINE array in left to right scanline order. In the event there are no further edge crossings in the CURRENTSCANLINE array, the both P and Q are set to NULL. After completion of step 310, the sub-process 206 proceeds to decision block 302.

524206.doc li~r~iv~ nn~nmr i YICL7CmW-~IF'~1 rUuuq lil~i~i*~'*illl~ri~II:?1UIWhllhl*UY~ir IR.P.VL~llill;e YIII/I~YI:1 18 If both decision blocks 304 and 306 return FALSE the sub-process 206 proceeds to step 308 where the edge crossing P is matched with the active edge A.

Specifically, the step 308 submits the edge crossing P to sub-process 900 for the possible generation of a current segment representing the matched active edge. After completion of sub-process 900, the step 308 updates the variables A, B, P, and Q thus eliminating the current edge crossing P and current active edge A from further comparison during the further processing of the current scanline. Specifically step 308 sets the variable A to variable B and variable B to the tip-x value of the next active edge in the ACTIVE EDGE list and sets the variable P to variable Q and the variable Q to the x co-ordinate position stored in the next entry in the CURRENTSCANLIE array. Thus the active edges A and B will effectively move one active edge to the left in the previous scanline and edge crossings P and Q will effectively move one edge crossing to the left in the current scanline. If there is no next active edge in the ACTIVE EDGE list, the variable B is set to NULL. Also, if there is no next edge crossing in the CURRENTSCANLINE array, the variable Q is set to NULL.

After completion of step 308, the sub-process 206 continues to decision block 314. The decision block 314, herein called "Interior Case tests for pairs of edge crossings that can start new edges on the inside walls of an arch-shaped bitmap region. Fig. 6 shows a typical example of Interior Case 1. In this scenario, the edge crossings P and Q are on the inside of the walls and the active edge A is on the outer left side of bitmap region. The decision block 314 compares the current two edge crossings P and Q with the current two active edges A and B. Specifically, the decision block 314 determines the following conditional statement.

if P is not NULL and Q is not NULL, and if A is not NULL and A Q If the decision block 314 returns FALSE the sub-process 206 proceeds- to decision block 316. On the other hand, if the decision block 314 returns TRUE, the subprocess 206 proceeds to step 318.

524206.doc 19- During step 318, the sub-process 206 creates the start of two new active edges at P and Q of the current scanline. During step 318, the sub-process 206 creates the start of two new active edges at P and Q of the current scanline. The step 318 creates these new active edges by calling the sub-process 1400 for each edge crossing P, Q. This subprocess 1400 will be described in more detail below with reference to Fig. 14. After the sub-process 1400 is completed for both edge crossings P, Q, the step 318 then 'eliminates' the edge crossings P,Q from further comparison during the processing of the current scanline. Namely, the variables P and Q are updated to store the positions of the next two adjacent edge crossings in the CURRENTSCANLINE array in left to right scanline order. If there is no next edge crossing in the CURRENTSCANLINE array, the variables P and Q are set to NULL. After completion of step 318, the sub-process 206 proceeds to decision block 314 for retesting of any further interior regions representative of the active edges A, B and the newly updated edge crossings P and Q.

If the decision block 314 returns FALSE the sub-process 206 proceeds to decision block 316. The decision block 316, herein called, "Interior Case tests for pairs of active edges that finish, which are running along the inside walls of an upsidedown arch-shaped bitmap region. Fig. 7 shows a typical example of Interior Case 2.

Active edges A and B are on the inside walls of the upside-down arch-shaped bitmap region shown in the example and terminate in the previous scanline. The decision block 20 316 compares the current two edge crossings P and Q with the current two active edges A and B. Specifically, the decision block 316 determines the following conditional statement.

if A is not NULL and B is not NULL, and .00 25 if Pis not NULL and P> B 0 0: If the decision block 316 returns FALSE the sub-process 206 proceeds to step 322. On the other hand, if the decision block 316 returns TRUE, the sub-process 206 proceeds to step 320.

524206.doc 20 During step 320, the sub-process 206 completes the generation of the segments representing the active edges A, B and these completed segments representing the active edges are submitted to the rendering method 104. The step 320 completes this generation by calling the sub-process 1200 for each active edge A and B. This sub-process 1200 will be described in more detail below with reference to Fig. 12. After sub-process 1200 is completed for both active edges A and B and removes the active edges A, B from the ACTIVE EDGE list, the step 320 then updates the values for A and B. Specifically, the step 320 sets the variables A and B to the tip-x positions of the next two adjacent active edges in the ACTIVE EDGE list. If there are no more active edges in the ACTIVE EDGE list, then the variables A and B are both set to NULL. After completion of step 320, the sub-process 206 proceeds to decision block 314 for retesting of any further interior regions representative of t he newly updated active edges A, B and edge crossings P, and Q.

When decision block 316 returns FALSE the sub-process 206 proceeds to step 322 where the edge crossing P is matched with the active edge A. Specifically, the step 322 submits the edge crossing P to sub-process 900 for the possible generation of a current segment representing the matched active edge. After completion of sub-process 900, the step 322 updates the variables A, B, P, and Q thus eliminating the current edge crossing P and current active edge A from further comparison during the further processing of the current scanline. Specifically step 322 sets the variable A to variable B and variable B to the tipx value of the next active edge in the ACTIVE EDGE list and sets the variable P to variable Q and the variable Q to the x co-ordinate position stored in the next entry in the CURRENTSCANLINE array. Thus the active edges A and B will effectively move one active edge to the left in the previous scanline and edge crossings P and Q will effectively move one edge crossing to the left in the current scanline. If there is no next active edge in the ACTIVE EDGE list, the variable B is set to NULL. Also, if there is no next edge crossing in the CURRENTSCANLINE array, the variable Q is set to NULL.

After the completion of either one of the steps 312, 310 and 322, the sub-process 206 proceeds to decision block 302. In decision block 302 a check is made whether there 524206.doc -21 are any more edge crossings in the current scanline to process. Specifically, the decision block 302 determines whether either one or both of the variables P and Q is not NULL. If the decision block 302 returns FALSE the sub-process 206 proceeds to step 324, otherwise it returns to decision block 304 for further processing of the remaining edge crossings.

In the event there are no more edge crossings to process for the current scanline, there still may be remaining active edges in the previous scanline, that have not been previously 'eliminated'. During step 324, the sub-process 206 completes the generation of the segments representing the remaining active edges and the completed segments representing the active edges are submitted to the rendering method 104. The step 324 completes this generation by calling the sub-process 1200 for each of the remaining active edges, if any. This sub-process 1200 will be described in more detail below with reference to Fig. 12. After sub-process 1200 is completed for the remaining active edges, the sub-process 206 then terminates 358 and returns to the calling method 102. Turning now to Fig 8A, there is shown an illustration of a bitmap image 800 of the character comprising bi-tonal pixels arranged as a 8 by 10 block of pixels. The method 102 for converting bitmap images receives the bitmap image and the sub-process 204 detects the edges of characters in the bitmap image on a scanline basis.

Turning now to Fig. 8B, there is shown the edge crossings detected during the subprocess 204 for the bitmap image as shown in Fig. 8A. The edge crossings of the character are highlighted by dark lines. For example, the first edge crossing in scanline order of the character is referenced as 802. These edge crossings of the character are then passed to the sub-process 206, where the active edges are generated.

Turning now to Fig. 8C, there is shown the active edges generated during the subprocess 206 for the edge crossings shown in Fig. 8C. The active edges generated 1, 2, 3, 4, 5, and 6 by the sub-process 206 are then fed to a sub-process 208 for generating of segments of the character The manner in which these active edges are generated will be described with reference to the example shown in Figs. 8A, 8B and 8C. This example illustrates all of the possible edge scenarios.

524206.doc -22- Initially, during the processing of the first scanline by the sub-process 206, the variables A and B are NULL as there is no previous scanline. Consequently, the two edge crossings of the first scanline fail "Exterior case 1" but pass "Exterior case 2" and two new active edges 4, 3 are created at the two edge crossings of the first scanline.

During the processing of the second scanline the variable A is set to the position of the first active edge 4 at the first scanline and the variable B is set to the position of the second active edge 3 at the first scanline. The variables P and Q are set to the positions of the first and second edge crossings of the second scanline. The "Exterior case 1" fails as P B and "Exterior case 2" fails as A Q. The sub-process 206 thus extends the active edge 4 to the first edge crossing in the second scanline. The sub-process 206 then updates the variables A, B, P and Q. The variable A is now set to the position of the second active edge 3 of the first scanline and B is set to NULL. P and Q are set to the second and third edge crossings of the second scanline. The sub-process 206 then tests for the "Interior case which passes as A Q. The sub-process 205 thus generates two new active edges 1 and 2 at the second and third edge crossings of the second scanline respectively.

The sub-process then updates the variables P and Q, where the variable P is set to the position of the fourth edge crossing in the second scanline and Q is set to Null. "Interior case 1" is retested and fails as Q is Null. The sub-process 206 proceeds to "Interior case 2" which fails as B is Null. The sub-process 206 thus extends the active edge 3 to the fourth edge crossing of the second scanline. The sub-process 206 proceeds to the third scanline as all the edge crossings of the second scanline have been examined.

During the processing of the third scanline, the sub-process 206 initially sets the variables A and B to the positions of the active edges 4 and 1 in the second scanline and sets the variables P and Q to the positions of the first and second edge crossings in the third scanline. The "Exterior case 1" fails as P is not B, and the "Exterior case 2" fails as A is not Q. The sub-process 206 then extends the active edge 4 to the first edge crossing in the third scanline and updates the variables A, B, P, and Q. The sub-process 206 then updates the variables A and B to the positions of the second and third active edges respectively and updates the variable P to the position of the second edge crossing in the third scanline and Q to NULL as there are no more remaining edge crossings in the 524206.doc 23 third scanline. The "Interior case 1" then fails as Q is NULL and the "Interior case 2" fails as P is not B. The sub-process 206 then extends the active edge 1 to the second edge crossing in the third scanline. As all edge crossings have been examined, the subprocess 206 finishes the active edges 2 and 3 of the second scanline. The sub-process 206 then proceeds to the fourth scanline for processing.

During the processing of the fourth scanline, the sub-process 206 initially sets the variables A and B to the positions of the active edges 4 and 1 in the third scanline and sets the variables P and Q to the positions of the first and second edge crossings in the fourth scanline. The "Exterior case 1" then fails as P is not B, and the "Exterior case 2" fails as A is not Q. The sub-process 206 then extends the active edge 4 to the first edge crossing in the fourth scanline and updates the variables A, B, P, and Q. The sub-process 206 then updates the variable A to the position of the active edge 1 and sets the variable B to NULL as there are no more active edges in the third scanline. The sub-process 206 also updates the variable P to the position of the second edge crossing in the fourth scanline. The "Interior case 1" and "Interior case 2" then both fail as B and Q are both NULL. The sub-process 206 then extends the active edge 1 to the second edge crossing in the fourth scanline. As all edge crossings have been examined, the sub-process 206 then proceeds to the fifth scanline for processing.

The sub-process 206 processes the fifth though to the eight scanlines in a similar fashion as the fourth scanline and will not described any further. The sub-process 206 then proceeds to the processing of the ninth scanline.

During the processing of the ninth scanline, the sub-process 206 initially sets the variables A and B to the positions of the active edges 4 and 1 in the eight scanline and sets the variables P and Q to the positions of the first and second edge crossings in the ninth scanline. The "Exterior case 1" then fails as P is not B and the "Exterior case 2" passes. The sub-process 206 then creates two new active edges 5, 6 at the first and second edge crossings of the ninth scanline. The sub-process 206 then updates the variables P and Q, by setting P and Q to the positions of the third and fourth edge crossings of the ninth scanline respectively. The "Exterior case 1" now fails as P is not B and the "Exterior case 2" now fails as A is not Q. The sub-process 206 then extends 524206.doc 24 the active edge 1 to the third edge crossing of the ninth scanline and then updates the variables A, B, P, Q. The sub-process 206 sets the variable A to the position of the active edge 1 in the eight scanline and sets the variable B to NUJLL as there are no more active edges in the eight scanline. The sub-process sets the variable P to the position of the fourth edge crossing of the ninth scanline and sets the variable Q to NULL as there are no more remaining edge crossings in the ninth scanline. The sub-process proceeds to "Interior case 1 which fails as Q is NULL and then proceeds to "Interior case 2" which fails as B is NULL. The sub-process 206 then extends the active edge 1 to the fourth edge crossing of the ninth scanline. As all the edge crossings have now been examined, the sub-process 206 proceeds to the processing of the tenth scanline.: During the processing of the tenth scanline, the sub-process 206 initially sets the variables A and B to the positions of the active edges 5 and 6 in the ninth scanline and sets the variables P and Q to the positions of the first and second edge crossings in the tenth scanline. The "Exterior case 1" then fails as P is not B and the "Exterior case 2" fails as A is not Q. The sub-process 206 then extends the active edge 5 of the ninth scanline to the-first edge crossing of the tenth scanline. The sub-process 206 then updates the variables A, B, P, and Q. The variable A is set to the position of the active edge 6 in the ninth scanline and the variable B is set to the position of the active edge 4 in the ninth scanline. The variable P is set to the position of the second edge crossing in the tenth scanline and the variable Q is set to NULL as there are no more remaining edge scanlines in the tenth scanline. The sub-process 206 then proceeds to "Interior case 1" which fails as Q is NULL. The sub-process 206 then proceeds to "Interior case 2" which passes, The sub-process 206 then tenminates the actives edges 4, 6 in the ninth scanline. The subprocess the updates the variables A and B. The variable A is set to the position of the active edge 1 in the ninth scanline and the variable B is set to NULL as there are no more remaining active edges. The sub-process then repeats the "Interior case 1 which fails as Q is NULL and then proceeds to "Interior case 2" which fails as B is NULL. The subprocess thus extends the active edge 1 to the second edge crossing of the tenth scanline.

As all edge crossings of the last scanline have now been completed the sub-process 206 terminates.

524206.doc As can be seen from Figs. 3, 8B and 8C, the sub-process 206 compares current edge crossings P and Q of a current scanline with current active edges A and B of a previous scanline. The sub-process 206 initially starts with the two left most active edges in the previous scanline and the two left most edge crossings in the current scanline for comparison. When the sub-process 206 completes its processing of any one or more of these edge crossing(s) and/or active edge(s) it moves to the next pair of edge crossings and/or next pair of active edges, which occur next in the left to right scan order for processing. The sub-process 206 keeps track of the current edge crossings and active edges being processed by referencing the ACTIVE EDGE list and CURRENTSCANLINE arrays. There are many other ways of keeping track of the current pair of edge crossings and pair of active edges without departing from the spirit or the scope of the invention.

Returning now to Fig. 2, the method 102 passes the generated active edges 207 to the sub-process 208 for generating segments (using steps and inclined vectors) that follow these active edges. These generated segments are then passed together with other noncharacter graphic objects to the edge-based graphic object rendering method 104 for 0o.o rendering. The rendering method 104 then effectively reconstitute these active edges i from these generated segments and composites and then renders the character together with any other possible non-character obj ect(s) input utilizing this edge information.

For ease of explanation, this rendering process will be briefly described with reference to the example shown Fig. 8C. The rendering method 104 renders the image in scanline order commencing with the first scanline. The system during the first scanline reconstitutes the edge information from the generated segments and renders from a first edge (equivalent to active edge 4) to a second edge (equivalent to active edge 3) with a designated fill. The rendering method 104 during the second scanline reconstitutes the edge information and renders from the first edge (equivalent to active edge 4) to the second edge (equivalent to active edge 1) with a designated fill and renders from the third edge (equivalent to active edge 2) to the fourth edge(equivalent to active edge 3) with a designated fill. The rendering method 104 proceeds in similar fashion to all the remaining scanlines.

524206.doc 26 Turning now to Figs. 9A and 9B, there is shown a flow chart of the sub-process 208 for generating a segment representation 103 from the active edges that follow the contours of the character. The sub-process 208 generates segments based on three basic segments types, a step segment, an inclined vector segment, and a step-inclined vector segment. The step segment has a horizontal component followed by a vertical component, where the horizontal component can be zero, and the vertical component can be any number of scanlines. An inclined vector segment is a vector segment, which is inclined to the vertical, but excludes purely horizontal and vertical vectors. A stepinclined vector segment is an horizontally-offset inclined vector segment. Other possible segments types are possible without departing from the spirit and scope of the invention.

An active edge is output by the sub-process 208 as a series of one or more generated segments, each of which comprise a segment type identifier and a number of parameters for defining the segment.

Turning now to Fig. 10, there is shown a section of a example bitmap image and the segments that were used to represent an outline of a character shown by the image. The bitmap image comprises two active edges 1006, 1008. The left most active edge 1006 is made up of a number of segments, one of which is a step segment 1000. A step segment has parameters x, y=nscans indicating an x axis movement of the step of a number of pixels in a positive direction or negative direction and a y axis movement of nscans pixels. As the generation of the segments is from top to bottom, the direction of the y axis movement is always in one direction and no sign is needed. The specific x,y values for the example step segment 1000 are +1 and 4 respectively. The right most active edge 1008 comprises amongst others an inclined vector segment 1002 and a step inclined vector segment 1004. The inclined vector segment 1002 has parameters nscan=5 and dx=1 indicating the inclined vector scans five scanlines and has a slope of 1. The step inclined segment 1004 has similar parameters to that of the inclined vector segment together with an additional parameter indicating the horizontal offset in pixels from the previous segment, which is in this example two pixels. An active edge is output by subprocess 208 as a series of one more segments together with another parameter indicating the initial scanline where the active edge commences. An active edge that comprises only 524206.doc -27one pixel is output as a step segment that has its parameters x and y set to x=0 and y 1.

Returning now to Figs. 9A and 9B, a description of the operation of the sub-process 208 is now given. The sub-process 208 is called by steps 308 and 322 of the sub-process 206 for each generated active edge of a current scanline. As the sub-process 206 operates on a scanline basis, the sub-process 208 will effectively be called on a scanline basis.

The sub-process 208 waits until it has edge crossing positions from at least 3 successive scanlines before it generates a segment. Namely, it waits until it has been called at least three times for a corresponding active edge before it considers generating a segment for that active edge. The first of the edge crossings is called the base and the x co-ordinate of which is stored in the variable base_x and the y co-ordinate of which is stored in the variable base_y in the item of the ACTIVE EDGE list corresponding to the current active edge. The variables base x and basey are updated only when a previous segment is generated by sub-process 208 and are set to the x,y co-ordinates of the last position of this previous segment. The second edge crossing is called the tip and the x coordinate of which is stored in the variable tipx in the item of the ACTIVE EDGE list corresponding to the current active edge. The variable tip_x is continually being updated and stores the x co-ordinate of the edge crossing of the active edge of the previous scanline. The third point is the edge crossing x co-ordinate position that has just been submitted, that is the edge crossing of the current active edge in the current scanline that resulted in the sub-process 208 being called. The third point is called the submitted point.

After the sub-process 208 has been called, it proceeds to decision block 904, where a check is made whether the current scanline is the second scanline for the current segment of this active edge. The decision block 904 makes this decision utilizing the variable basey and the y co-ordinate of the current scanline. If the decision block 904 returns TRUE (Yes), the sub-process 208 proceeds to step 908, where the variable tipx is set to the x co ordinate of the current edge crossing and the variable nscans is incremented. The variable nscans indicates the number of scanlines that the current active edge has traversed since the last edge crossing of the previously generated segment and is also stored in the item of the ACTIVE EDGE list of the current active edge. When the previous segment of the current active edge is terminated nscans is reset to the 524206.doc 28 number of scanlines between and inclusive of the new base and tip. After completion of step 908, the sub-process 208 then terminates until it is called again for processing of the next edge crossing in the next scanline.

On the other hand if the decision block 904, returns FALSE the sub-process 208 proceeds to decision block 906. During decision block 906, a check is made whether the current scanline is the third scanline for the current segment of this active edge. The decision block 904 makes this decision utilizing the variable base y and the y co-ordinate of the current scanline. If the decision block 906 returns TRUE (yes), the sub-process 208 proceeds to decision block 910. The sub-process 208 is now in a position to make a decision as to what type of segment the three initial edge crossings of the active edge can become.

In decision block 910, a check is made whether the edge crossings produced so far since the last segment produce a vertical line of pixels. If the decision block 910 returns TRUE (Yes), the sub-process 208 increments 914 the variable nscans. After completion of step 914, the sub-process 208 then terminates until it is called again for processing of the next edge crossing in the next scanline.

If decision block 910 returns FALSE the sub-process 208 proceeds to decision block 912, where a check is made whether an inclined vector can be made from the edge crossings submitted so far since the generation of the last segment of the active 20 edge. If the decision block 912 returns TRUE (yes), the sub-process 208 proceeds to step 916, where the a flag in the current active edge of the ACTIVE EDGE list is set to indicate that these edge crossings can be reproduced using a vector segment. After completion of step 916, the sub-process 208 then terminates until it is called again for processing of the next edge crossing in the next scanline. In this situation, the sub- 25 process 208 has determined that the edge crossings of the active edge of the three initial *0successive scanlines can form an inclined vector segment.

0 0 .000*:On the other hand if the decision block 912 returns FALSE (No) the sub-process 0: 208 proceeds to decision block 918 where a check is made whether the variables base-x :0000.and tip x have the same x co-ordinate. If the decision block 918 returns TRUE (yes), the *0 0 00 o: 30 sub-process 208 proceeds to step 920. The sub-process 208, during step 920, generates a 524206.doc 29 vertical step segment of length nscans from the last edge crossing of the previous segment. The step 920 then stores this generated segment in a buffer associated with the item of the ACTIVE EDGE list corresponding to the currently tracked active edge.

Finally, the step 920 updates the variables base_x, base y, tipx and nscans of this item.

Specifically it sets the basex,base y variables to the x,y co-ordinates of the last point of the active edge of the generated segment and sets tipx to the x co-ordinate of the active edge in the current scanline. The nscans variable is set to the number of scanlines between the base and tip inclusive. After completion of step 920, the sub-process 208 then terminates 924. When the sub-process 208 is called again for the active edge in the next scanline it will be for the generation of the next segment.

If however, the decision block 918 returns FALSE then the sub-process 208 proceeds to step 922. The sub-process 208, during step 922, generates a step segment having a vertical length of nscans pixels and horizontal length of one pixel. The step 922 then stores this generated segment in a buffer associated with the item of the ACTIVE EDGE list corresponding to the currently tracked active edge. Finally, the step 922 updates the variables base_x, base-y, tipx and nscans of this item. Specifically it sets the base_xbase y variables to the x,y co-ordinates of the last point of the active edge of the generated segment and sets tipx to the x co-ordinate of the active edge in the current scanline. The nscans variable is set to the number of scanlines between the base and tip inclusive. After completion of step 922, the sub-process 208 then terminates 924. When the sub-process 208 is called again for the active edge in the next scanline it will be for the generation of the next segment.

If however, the decision block 906 returns FALSE the sub-process 208 proceeds to decision block 926, where a check is made whether the current active edge from basex to tip-x is an inclined vector. If the decision block 926 returns FALSE the sub-process proceeds to decision box 928, where a check is made whether the x co-ordinate of currently submitted edge crossing differs from the x co-ordinate of the variable tipx. If the decision block 928 returns FALSE the sub-process 208 proceeds to step 930, where the variable nscans is incremented. After completion of step 524206.doc 930, the sub-process 208 then terminates 924 until it is called again for processing of the next edge crossing in the next scanline.

If, however, the decision block 928 returns TRUE (Yes), the sub-process 208 proceeds to step 932. The sub-process 208, during step 932, creates a vertical step segment from edge crossing corresponding to base_x to the edge crossing corresponding to the variable tip_x transversing nscans pixels. The step 932 then stores this generated segment in a buffer associated with the item of the ACTIVE EDGE list corresponding to the currently tracked active edge. Finally, the step 932 updates the variables base_x, basey, tipx and nscans of this item. Specifically it sets the base_x,basey variables to the x,y co-ordinates of the last point of the active edge of the generated segment and sets tipx to the x co-ordinate of the active edge in the current scanline. The nscans variable is set to the number of scanlines between the base and tip inclusive. After completion of step 932, the sub-process 208 then terminates 924. When the sub-process 208 is called again for the active edge in the next scanline it will be for the generation of the next S segment.

If the decision block 926 returns TRUE (Yes), the sub-process 208 then proceeds to decision block 934, where a check is made whether the inclined vector segment produced during the last call to the sub-process 208 can be extended to the currently submitted edge crossing. If the decision block 934 returns FALSE (No) the sub-process proceeds to step 936. During step 936, the sub-process 208 creates an inclined vector to the last submitted edge crossing of the active edge. The step 936 then stores this generated segment in a buffer associated with the item of the ACTIVE EDGE list corresponding to the currently tracked active edge. Finally, the step 936 updates the variables base_x, base_y, tipx and nscans of this item. Specifically it sets the base_x,base_y variables to the x,y co-ordinates of the last point of the active edge of the generated segment and sets tip_x to the x coordinate of the active edge in the current scanline. The nscans variable is set to the number of scanlines between the base and tip inclusive. After completion of step 936, the sub-process 208 then terminates 924 until it is called again for processing of the next edge crossing in the next scanline.

524206.doc '-ll~nrnnnr-:lillr *mm *nl~rl** r~ irrnnl *lll~i l l r r n~liillii*i vlurrhl*u Ilrr*~nlinulllr uiI;*il~~l~ illlilll1lilll~lliilFlil*"U~'1*i':'l"~r I.r~UI.

-31 If on the other hand, the decision block 934 returns TRUE(Yes), the sub-process 208 proceeds to step 938. During step 938, the sub-process 208 updates the variable tip~x to the position of the submitted active edge of the current scanline and increments the variable nscans. Preferably, tipx is incremented by dx for better accuracy. After completion of step 938, the sub-process 208 then terminates 924 until it is called again for processing of the next edge crossing in the next scanline.

As mentioned above, the sub-process 208 examines the initial 3 points (base, tip, and submitted) to see if it is possible to use a inclined vector to draw these points. If it is possible to draw a inclined vector, it is marked as one, and tracking continues. If it is not 0 possible to draw a inclined vector, a step segment is output for the base and tip points, and a new segment is started with the base at the old tip and the tip at the submitted edge crossing. For scanlines after the 3rd one, the submitted edge crossing is checked with the current segment to see if the segment can be extended to it. If it does fit, the tip value becomes the value of the submitted edge crossing so it becomes part of the segment. If it does not fit, the segment is output and a new one started (again with the base at the old tip and the tip at the submitted edge crossing).

see* If the current segment is a vertical-only step (no pre-horizontal movement) and the 0 submitted edge crossing does not fit, it might be possible to draw a inclined vector that 0: can cover all of the pixels from the step, as well as the submitted edge crossing. If it is possible, the segment is marked as a inclined vector and tracking continues. If not, the segment is output as a step and a new segment is started (same initialization as previously stated).

The sub-process 208 also watches for a step with a y axis height of zero followed by a inclined vector, which can then be turned into a step inclined vector segment. This layer of the sub-process 208 also looks for a step followed by another step with an x-axis width of zero, which can be combined into a single step.

Turning now to Fig. 12, there is shown a sub-process 1200 for finishing the generation of segments of an active edge. This sub-process 1200 is called by steps 312 and 320 of sub-process 206 for the current active edge(s). Where two active edges are to be finished the sub-process 1200 is called separately for each active edge.

524206.doc 32 The sub-process 1200 commences at step 1202, where any necessary parameters are initialized. After completion of step 1202, the sub-process 1200 proceeds to decision block 1204 where a check is made whether the variable nscans is two or less. This variable nscans is stored in the item of the ACTIVE EDGE list associated with the active edge for which this process 1200 has been called.

If the decision block 1204 returns FALSE the sub-process 1200 proceeds to decision block 1206, where a check is made whether the segment of the active edge currently in progress is a vector. The decision block 1204 determines this with reference to the flag stored in the item of the ACTIVE EDGE list corresponding to the current active edge. If the decision block 1206 returns TRUE (YES), the sub-process 1200 creates a vector segment as described by the variables dx, nscans in the item of the ACTIVE EDGE list corresponding to the current active edge. The sub-process 1200 then stores this vector segment in the buffer associated with the item of the ACTIVE EDGE list corresponding to the current active edge. After completion of step 1208, the subprocess 1200 proceeds to step 1218.

On the other hand, if the decision block 1206 returns FALSE the sub-process 1200 proceeds to step 12 10. In step 12 10, the sub-process 1200 creates a step segment as described by the variables tip_x, base-x, nscans in the item of the ACTIVE EDGE list corresponding to the current active edge. The sub-process 1200 then stores this step 20 segment in the buffer associated with the item of the ACTIVE EDGE list corresponding to the current active edge. After completion of step 1210, the sub-process 1200 proceeds to step 1218.

On the other hand, if the decision block 1204 returns TRUE (YES), the sub-process 1200 proceeds to decision block 1212, where a check is made whether the variable tip~x is equal to base -x in the item of the ACTIVE EDGE list corresponding to the current active edge. If the decision block 1212 returns TRUE( Yes), then the sub-process 1200 proceeds to step 1214. In step 1214, the sub-process 1200 creates a vertical step from base to tip equivalent to nscans. The step 1214 then stores this vertical step in the buffer associated with the item of ACTIVE EDGE list corresponding to the current active edge.

After completion of step 1214, the sub-process 1200 proceeds to step 1218.

524206.doc On the other hand, if the decision block 1212 returns FALSE then the subprocess proceeds to step 1216. In step 1216, the sub-process 1200 first creates a vertical step one scanline in height from base-x downwards, and then creates a step with a horizontal movement of tipx base x pixels and a vertical movement downwards of one scanline height. The step 1216 then stores these steps in the buffer associated with the item of the ACTIVE EDGE list corresponding to the current active edge. After completion of step 1214, the sub-process 1200 proceeds to step 1218.

After completion of either of the steps 1214, 1216, 1208, or 1210, the sub-process 1200 proceeds to step 1218, were the segment buffer of the item of the ACTIVE EDGE list corresponding to the current active edge is terminated. The sub-process 1200 then submits 1220 the completed segment in the segment buffer of the item of the ACTIVE EDGE list corresponding to the current active to the rendering method 104. The subprocess 1200 then removes the item from the ACTIVE EDGE list corresponding to the current active edge. After completion of step 1220, the sub-process 1200 terminates and returns to the calling step of sub-process 206 for further processing of the edges.

Turning now to Fig. 13, there is shown a flow chart of a sub-process 1300 for creating a new active edge item for insertion in the ACTIVE EDGE list. The sub-process 1300 is called by steps 310 or step 318 of sub-process 206 for each new active edge.

Where two active edges are to be created the sub-process 1300 is called separately for each of those active edges.

The sub-process 1300 commences at step 1302, where any necessary parameters are initialized. The sub-process 1300 then proceeds to step 1304, where the sub-process 1300 creates and initializes a new active edge item. For instance the sub-process initializes the base variables of the item to the x,y co-ordinates of the start of the new active edge. The sub-process 1300 then inserts 1306 the active edge item in the ACTIVE EDGE list at the relevant location according to its (base) position in the left to right scanline order. After completion of step 1306, the sub-process 1300 terminates 1308 and returns to the calling step of sub-process 206.

The aforementioned preferred method(s) and process(es) comprise a particular control flow. There are many other variants of the preferred method(s) and process(es) 524206.doc -34which use different control flows without departing the spirit or scope of the invention.

Furthermore one or more of the steps of the preferred method(s) may be performed in parallel rather sequential.

The process 100 for rendering graphic objects as shown in Fig. 1 can be implemented using an application specific integrated circuit (ASIC). Alternatively, the process 100 can be implemented using a general-purpose computer system 1400 as shown in Fig. 12, where the steps of the process are implemented as coded instructions in software. The process 100 can also be implemented in a software/hardware combination, wherein the method for converting bitmap images 102 is implemented as software using such a general purpose computer and the method of rendering graphics objects is implemented as hardware in combination therewith.

The software may be stored in a computer readable medium, including the storage devices described below, 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 rendering graphic objects...: The computer system 1400 comprises a computer module 1401, input devices such-• as a keyboard 1402 and mouse 1403, output devices including a printer 1415 and a display device 1414. A Modulator-Demodulator (Modem) transceiver device 1416 is used by the computer module 1401 for communicating to and from a communications network 1420, for example connectable via a telephone line 1421 or other functional medium. The modem 1416 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 1401 typically includes at least one processor unit 1405, a memory unit 1406, for example formed from semiconductor random access memory (RAM) and read only memory (ROM), input/output interfaces including a video interface 1407, and an 1/0 interface 1413 for the keyboard 1402 and mouse 1403 and optionally a joystick (not illustrated), and an interface 1408 for the modem 1416. A storage device 1409 is provided and typically includes a hard disk drive 1410 and a 524206.doc 1 -l ~'lli 11.91-- il--LI l lnir~ 1YLULSlllll(~~l;i I*IIYL(II( ill.O _irii :LIUL floppy disk drive 1411. A magnetic tape drive (not illustrated) may also be used. A CD- ROM drive 1412 is typically provided as a non-volatile source of data. The components 1405 to 1413 of the computer module 1401, typically communicate via an interconnected bus 1404 and in a manner which results in a conventional mode of operation of the computer system 1400 known to those in the relevant art. Examples of computers on which the described arrangements can be practiced include IBM-PC's and compatibles, Sun Sparcstations or alike computer systems evolved therefrom.

Typically, the application program is resident on the hard disk drive 1410 and read and controlled in its execution by the processor 1405. Intermediate storage of the program and any data fetched from the network 1420 may be accomplished using the semiconductor memory 1406, possibly in concert with the hard disk drive 1410. 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 1412 or 1411, or alternatively may be read by the user from the network 1420 via the modem device 1416. Still further, the software can also be loaded into the computer system 1400 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 1401 and another 0.

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.

Industrial Applicability It is apparent from the above that the arrangements described are applicable to the computer graphics and data processing industries).

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 embodiment(s) 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 524206.doc 36 of'. Variations of the word comprising, such as "comprise" and "comprises" have corresponding meanings.

524206.d.

Claims (5)

1. A method of rendering a first bitmap image, the method comprising; detecting, for each scanline of a second bitmap image, edge crossings of at least one region comprising pixels having a uniform colour, wherein the edge crossings are those edges of pixels of the second bitmap image that border the at least one region and that are transverse to the scanlines; generating active edges of the at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region and that do not cross over said at least one region; generating a segment representation of the outlines of the at least one region from said generated active edges; and rendering said first bitmap image from the segment representation of said outlines of said at least one region using an edge-based scanline graphics object rendering system.

2. A method as claimed in claim 1, wherein said at least one region is a character.

3. A method as claimed in claim 1, wherein said step of generating active edges comprises a comparison sub-step for comparing a current pair of first and second active edges and a current pair of first and second edge crossings against a predetermined number of edge scenarios for matching the edge crossings to the active edges.

4. A method of converting a bitmap image comprising at least one region having V. 25 uniform colour characteristics to a segment representation of outlines of said at least one region, the method comprising; detecting, for each scanline of the bitmap image, edge crossings of the at least one Sregion, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; oe*

524206.doc ""lix I j. l n .lk generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating means comprises a sub-step for comparing and processing a current pair of first and second active edges and a current pair of first and second edge crossings, and the sub-step for comparing and processing comprises the sub-steps of: terminating said current pair of active edges at said previous scanline, if the current pair of active edges terminate at the previous scanline prior to a current pair of first and second edge crossings; creating a new pair of active edges starting at the current pair of edge crossings, if the current pair of edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges; creating new active edges at the current scanline of those inside edges of the arch-shaped region, if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region; and terminating the current pair of active edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region, if the current pairs of edge crossings and active edges formn part of an upside down arch-shaped bitmap region; 20 generating a segment representation of the outlines of the at least one region from said generated active edges.

5. The method as claimed in claim 4, wherein if the condition in sub-tp()itre then the current pair of active edges to be subsequently compared are updated and the comparison sub-step is repeated. The method as claimed in claim 4, wherein if the condition in sub-step is false, then the comparison sub-step proceeds to sub-step 524206.doc -39- 7. The method as claimed in claim 4, wherein if the condition in sub-step is true, then the current pair of edge crossings to be subsequently compared are updated and the comparison sub-step is repeated. 8. The method as claimed in claim 4, wherein if the condition in sub-step is false, then the first edge crossing is matched to the first active edge and the current pairs of edge crossings and active edges to be subsequently compared are updated and the comparison sub-step proceeds to sub-step 9. The method as claimed in claim 4, wherein if the condition in sub-step is true, then the current pair of edge crossings to be subsequently compared are updated and the comparison sub-step repeats sub-step The method as claimed in claim 4, wherein if the condition in sub-step is false, then the comparison sub-step proceeds to sub-step 11. The method as claimed in claim 4, wherein if the condition in sub-step is true, then the current pair of active edges to be subsequently compared are updated and the comparison sub-step repeats sub-step 11 12. The method as claimed in claim 4, wherein if the condition in sub-step is false, then the first edge crossing is matched to the first active edge and the current pairs of edge crossings and active edges to be subsequently compared are updated and the comparison step is repeated. S 13. A method of converting a bitmap image comprising at least one region having uniform colour characteristics to a segment representation of outlines of said at least one region, the method comprising; S.524206.doc 524206.doc detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating step comprises: a comparison sub-step for comparing a current pair of first and second active edges and a current pair of first and second edge crossings, wherein said comparison step comprises the sub-steps of: determining if a current pair of first and second adjacent active edges terminate at the previous scanline prior to a current pair of first and second adjacent edge crossings, and if so terminating said current active edges in said previous scanline and setting the current pair of first and second adjacent active edges to a next pair of first and second adjacent active edges in the previous scanline and proceeding to sub-step otherwise proceeding to sub-step determining if the current pair of edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges, and if so creating a new pair of active edges starting at the current pair of edge crossings and S setting the current pair of first and second edge crossings to a next pair of first and second adjacent edge crossings in the current scanline and proceeding to sub-step otherwise matching the first edge crossing to the first active edge, and setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and then proceeding to sub-step determining if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region and if so creating new active edges at the current scanline of those inside edges of the arch-shaped region and setting the current pair of first and second edge crossings to a next pair of first and second adjacent edge 524206.doc -41- crossings in the current scanline and repeating sub-step otherwise proceeding to sub- step and determining if the current pairs of edge crossings and active edges form part of an upside down arch-shaped bitmap region and if so terminating the active edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region and setting the current pair of first and second active edges to a next pair of first and second adjacent active edges in the previous scanline not previously eliminated and repeating sub-step otherwise matching the first edge crossing to the first active edge, setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and proceeding to sub-step and returning to sub-step if there are one or more edge crossings not matched or created as active edges in the current scanline; generating a segment representation of the outlines of the at least one region from said generated active edges.... 14. The method as claimed in claim 13, wherein the active edge generating step further comprises the following sub-step after sub-step terminating, in the event all edge crossings in the current scanline have been matched or created as active edges, any remaining active edges not matched or already finished in the previous scanline. 15. The method as claimed in claim 13, wherein the current pair of first and second active edges are set to said next pair of first and second active edges in the previous scanline, which occur first and second in a predetermined scanline order in the previous scanline. 524206.doc -42- 16. The method as claimed in claim 13, wherein the current pair of first and second edge crossings are set to said next pair of first and second edge crossings in the current scanline, which occur first and second in a predetermined scanline order in the current scanline. 17. The method as claimed in claim 15 or 16, wherein the initial current pair of active edges are set to the first and second active edges in the previous scanline, which occur first and second respectively in the previous scanline in a predetermined scan order and the initial current pair of edge crossings are set to the first and second edge crossings in the current scanline, which occur first and second respectively in the current scanline in a predetermined scan order. 18. The method as claimed in claim 13, wherein in the event there are no more active edges in the previous scanline that have been matched or finished, then the first and second active edges of the pair are both set to a value indicating that no first and second active edges exist. 19. The method as claimed in claim 13, wherein in the event there are no more edge crossings in the current scanline that have been matched or created as active edges, then the first and second edge crossings of the pair are both set to a value indicating that no first and second edge crossings exist. 20. The method as claimed in claim 13, wherein said edge detecting step passes said edge crossings to said active edge generating step on a scanline basis and said active edge generating step passes said generated active edges to said segment generating step on a scanline basis. 21. The method as claimed in claim 13, wherein said edge detecting step passes said .edge crossings to said active edge generating step on an image basis and said active edge 524206.doc -43 generating step passes said generated active edges to said segment generating step on an image basis. 22. Apparatus for rendering a first bitmap image, the apparatus comprising; means for detecting, for each scanline of a second bitmap image, edge crossings of at least one region comprising pixels having a uniform colour, wherein the edge crossings are those edges of pixels of the second bitmap image that border the at least one region and that are transverse to the scanlines; means for generating active edges of the at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region and that do not cross over said at least one region; means for generating a segment representation of the outlines of the at least one region from said generated active edges; and means for rendering said first bitmap image from the segment representation of said outlines of said at least one region using an edge-based scanline graphics object rendering system. 23. The apparatus as claimed in claim 22, wherein said at least one region is a 20 character. 24. The apparatus as claimed in claim 22, wherein said means for generating active edges comprises a comparison means for comparing a current pair of first and second active edges and a current pair of first and second edge crossings against a predetermined 25 number of edge scenarios for matching the edge crossings to the active edges. .00.0:25. Apparatus for converting a bitmap image comprising at least one region having uniform colour characteristics to a segment representation of outlines of said at least one :0.000region, the apparatus comprising; 524206.doc -44- means for detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; means for generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating means comprises means for comparing and processing a current pair of first and second active edges and a current pair of first and second edge crossings, said comparing and processing means comprising: first means for terminating said current pair of active edges at said previous scanline, if the current pair of active edges terminate at the previous scanline prior to a current pair of first and second edge crossings; second means for creating a new pair of active edges starting at the current pair of edge crossings, if the current pair of edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges; third means for creating new active edges at the current scanline of those inside edges of the arch-shaped region, if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region; and e fourth means for terminating the current pair of active edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region, if the current pairs of edge crossings and active edges form part of an upside down arch-shaped bitmap region; means for generating a segment representation of the outlines of the at least one region from said generated active edges. 26. The apparatus as claimed in claim 25, wherein said means for generating active edges further comprises: means for updating said current pair of active edges and said current pair of first and second edge crossings. 524206.doc 45 27. The apparatus as claimed in claim 26, wherein if the first means terminates said current pair of active edges, then the updating means updates the current pair of active edges to a next pair of active edges and passes the current pairs to the first means for processing. 28. The apparatus as claimed in claim 26, wherein if the second means creates a new pair of active edges, then the updating means updates the current pair of edge crossings to a next pair of edge crossings and passes the current pairs to the first means for processing, otherwise the second means matches a first current edge crossing to a first current active edge, and the updating means updates the pair of cur-rent edge crossings to a next pair of edge crossings and the pair of current active edges to a next pair of active edges and passes the current pairs to the third means for processing. 29. The apparatus as claimed in claim 26, wherein if the third means creates new active edges at the current scanline of those inside edges of the arch-shaped region, then updating means updates the current pair of edge crossings to a next pair of edge crossings and passes the current pairs to the third means for processing, otherwise the current pairs are passed to the fourth means for processing. 30. The apparatus as claimed in claim 26, wherein if the fourth means terminates the current pair of active edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region, then the updating means updates the current pair of active edges to a next pair of active edges and passes the current pairs to the third means for processing, otherwise the fourth means matches a first edge crossing to a first active edge of the current pairs and the updating means updates the current pairs of edge crossings and active edges to next pairs of edge crossings and active edges. 3 1. Apparatus for converting a bitmap image comprising at least one region having uniform colour characteristics to a segment representation of outlines of said at least one region, the apparatus comprising; 524206.doc -46- means for detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; means for generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating means comprises means for comparing and processing a current pair of first and second active edges and a current pair of first and second edge crossings, wherein said comparison and processing means comprises: first means for determining if a current pair of first and second adjacent active edges terminate at the previous scanline prior to a current pair of first and second adjacent edge crossings, and if so terminating said current active edges in said previous scanline and setting the current pair of first and second adjacent active edges to a next pair of first and second adjacent active edges in the previous scanline and proceeding to the fifth means, otherwise proceeding to the second means; second means for determining if the current pair of edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges, and if so creating a new pair of active edges starting at the current pair of edge crossings and setting the current pair of first and second edge crossings to a next pair of first and 99 9 second adjacent edge crossings in the current scanline and proceeding to the fifth means, otherwise matching the first edge crossing to the first active edge, and setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and then proceeding to the third means; third means for determining if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region and if so creating new active edges at the current scanline of those inside edges of the arch-shaped region and setting the current pair of first and second edge crossings to a next pair of first and second 524206.doc -47- adjacent edge crossings in the current scanline and repeating the operations of the third means, otherwise proceeding to the fourth means; and fourth means for determining if the current pairs of edge crossings and active edges form part of an upside down arch-shaped bitmap region and if so terminating the active edges at the previous scanline of those inside edges of the upside down arch- shaped bitmap region and setting the current pair of first and second active edges to a next pair of first and second adjacent active edges in the previous scanline not previously eliminated and repeating the operations of the third means, otherwise matching the first edge crossing to the first active edge, setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge S crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and proceeding to the fifth means; and too. fifth means for returning to the first means if there are one or more edge crossings not matched or created as active edges in the current scanline; means for generating a segment representation of the outlines of the at least one region from said generated active edges. *9Se 32. The apparatus as claimed in claim 31, wherein the active edge generating means further comprises: sixth means for terminating, in the event all edge crossings in the current scanline have been matched or created as active edges, any remaining active edges not matched or already finished in the previous scanline. 33. The apparatus as claimed in claim 31, wherein the current pair of first and second active edges are set to said next pair of first and second active edges in the previous scanline, which occur first and second in a predetermined scanline order in the previous scanline. 524206.doc -48- 34. The apparatus as claimed in claim 31, wherein the current pair of first and second edge crossings are set to said next pair of first and second edge crossings in the current scanline, which occur first and second in a predetermined scanline order in the current scanline. The apparatus as claimed in claim 33 or 34, wherein the initial current pair of active edges are set to the first and second active edges in the previous scanline, which occur first and second respectively in the previous scanline in a predetermined scan order and the initial current pair of edge crossings are set to the first and second edge crossings in the current scanline, which occur first and second respectively in the current scanline in a predetermined scan order. 36. The apparatus as claimed in claim 31, wherein in the event there are no more active edges in the previous scanline that have matched or finished, then the first and second active edges of the pair are both set to a value indicating that no first and second active edges exist. 37. The apparatus as claimed in claim 31, wherein in the event there are no more edge crossings in the current scanline that have been matched or created as active edges, then 20 the first and second edge crossings of the pair are both set to a value indicating that no 0 first and second edge crossings exist. 400 0O0 38. The apparatus as claimed in claim 31, wherein said edge detecting means passes said edge crossings to said active edge generating means on a scanline basis and said active edge generating means passes said generated active edges to said segment generating means on a scanline basis. 39. The apparatus as claimed in claim 31, wherein said edge detecting means passes ysaid edge crossings to said active edge generating means on an image basis and said 524206.doc -49- active edge generating means passes said generated active edges to said segment generating step on an image basis. A computer program for rendering a first bitmap image, the computer program comprising; code for detecting, for each scanline of a second bitmap image, edge crossings of at least one region comprising pixels having a uniform colour, wherein the edge crossings are those edges of pixels of the second bitmap image that border the at least one region and that are transverse to the scanlines; code for generating active edges of the at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region and that do not cross over said at least one region; code for generating a segment representation of the outlines of the at least one region from said generated active edges; and code for rendering said first bitmap image from the segment representation of said outlines of said at least one region using an edge-based scanline graphics object rendering system. 0 20 41. The computer program as claimed in claim 40, wherein said at least one region is a 0: 0. •character. *o 42. The computer program as claimed in claim 40, wherein said generating code comprises comparison code for comparing a current pair of first and second active edges V 25 and a current pair of first and second edge crossings against a predetermined number of 90*0edge scenarios for matching the edge crossings to the active edges. 43. A computer program for converting a bitmap image comprising at least one region having uniform colour characteristics to a segment representation of outlines of said at least one region, the computer program comprising; 524206.doc code for detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; code for generating active edges of said at least one region from said detected edge crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating code comprises code for comparing and processing a current pair of first and second active edges and a current pair of first and second edge crossings, the code for comparing and processing comprising; first code for terminating said current pair of active edges at said previous .0 scanline, if the current pair of active edges terminate at the previous scanline prior to a current pair of first and second edge crossings; second code for creating a new pair of active edges starting at the current pair of edge crossings, if the current pair of edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges; I: third code for creating new active edges at the current scanline of those inside edges of the arch-shaped region, if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region; and fourth code for terminating the current pair of active edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region, if the current pairs of edge crossings and active edges form part of an upside down arch-shaped bitmap region; code for generating a segment representation of the outlines of the at least one region from said generated active edges. 44. The computer program as claimed in claim 43, wherein said code for generating active edges further comprises: code for updating said current pair of active edges and said current pair of first and second edge crossings. 524206.doc li iri~l-l jLIi irxrnu'('lr~~~ ~ri~ii~lr WI;, ~~i.~l~-ilLIIBY.Ili li"rW~ ~i ~%i~i~il *IIli dlW~lrY_ X .~lh~lii~ili 1 -51 The computer program as claimed in claim 44, wherein if the first code terminates said current pair of active edges, then the updating code updates the current pair of active edges to a next pair of active edges and passes the current pairs to the first code for processing. 46. The computer program as claimed in claim 44, wherein if the second code creates a new pair of active edges, then the updating code updates the current pair of edge crossings to a next pair of edge crossings and passes the current pairs to the first means for processing, otherwise the second code matches a first current edge crossing to a first current active edge, and the updating code updates the pair of current edge crossings to a next pair of edge crossings and the pair of current active edges to a next pair of active edges and passes the current pairs to the third code for processing. 47. The computer program as claimed in claim 44, wherein if the third code creates new active edges at the current scanline of those inside edges of the arch-shaped region, then updating code updates the current pair of edge crossings to a next pair of edge crossings and passes the current pairs to the third code for processing, otherwise the current pairs are passed to the fourth code for processing. 48. The computer proogram as claimed in claim 44, wherein if the fourth code terminates the current pair of active edges at the previous scanline of those inside edges of the upside down arch-shaped bitmap region, then the updating code updates the current pair of active edges to a next pair of active edges and passes the current pairs to the third means for processing, otherwise the fourth code matches a first edge crossing to a first active edge of the current pairs and the updating code updates the current pairs of edge crossings and active edges to next pairs of edge crossings and active edges. 49. A computer program for converting a bitmap image comprising at least one region having uniform colour characteristics to a segment representation of outlines of said at least one region, the computer program comprising; 524206.doc -52- code for detecting, for each scanline of the bitmap image, edge crossings of the at least one region, wherein the edge crossings are those edges of pixels of the bitmap image that border the at least one region and that are transverse to the scanlines; code for generating active edges of said at least one region from said detected edge s crossings, wherein a said active edge is a set of matched said edge crossings of different scanlines that follow an outline of the at least one region, and wherein said generating code comprises code for comparing and processing a current pair of first and second active edges and a current pair of first and second edge crossings, wherein said comparison and processing code comprises: first code for determining if a current pair of first and second adjacent :o active edges terminate at the previous scanline prior to a current pair of first and second adjacent edge crossings, and if so terminating said current active edges in said previous scanline and setting the current pair of first and second adjacent active edges to a next pair of first and second adjacent active edges in the previous scanline and proceeding to the fifth code, otherwise proceeding to the second code; second code for determining if the current pair of edge crossings form a new pair of active edges in the current scanline prior to the current pair of active edges, .i and if so creating a new pair of active edges starting at the current pair of edge crossings and setting the current pair of first and second edge crossings to a next pair of first and second adjacent edge crossings in the current scanline and proceeding to the fifth code, otherwise matching the first edge crossing to the first active edge, and setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and then proceeding to the third code; third code for determining if the current pairs of edge crossings and active edges form part of an arch-shaped bitmap region and if so creating new active edges at the current scanline of those inside edges of the arch-shaped region and setting the current pair of first and second edge crossings to a next pair of first and second 524206.doc -53- adjacent edge crossings in the current scanline and repeating the operations of the third code, otherwise proceeding to the fourth code; and fourth code for determining if the current pairs of edge crossings and active edges form part of an upside down arch-shaped bitmap region and if so terminating the active edges at the previous scanline of those inside edges of the upside down arch- shaped bitmap region and setting the current pair of first and second active edges to a next pair of first and second adjacent active edges in the previous scanline not previously eliminated and repeating the operations of the third code, otherwise matching the first edge crossing to the first active edge, setting the current first active edge to the current second active edge and setting the current second active edge to a next active edge in the previous scanline, and setting the current first edge crossing to the current second edge crossing and setting the current second active edge crossing to a next edge crossing in the current scanline and proceeding to the fifth code; and fifth code for returning to the first code if there are one or more edge crossings not matched or created as active edges in the current scanline; code for generating a segment representation of the outlines of the at least one region from said generated active edges. •o The computer program as claimed in claim 49, wherein the active edge generating code further comprises: sixth code for terminating, in the event all edge crossings in the current scanline have been matched or created as active edges, any remaining active edges not matched or already finished in the previous scanline. 51. The computer program as claimed in claim 49, wherein the current pair of first and second active edges are set to said next pair of first and second active edges in the previous scanline, which occur first and second in a predetermined scanline order in the previous scanline. 524206.doc r~-1 -54- 52. The computer program as claimed in claim 49, wherein the current pair of first and second edge crossings are set to said next pair of first and second edge crossings in the current scanline, which occur first and second in a predetermined scanline order in the current scanline. 53. The computer program as claimed in claim 51 or 52, wherein the initial current pair of active edges are set to the first and second active edges in the previous scanline, which occur first and second respectively in the previous scanline in a predetermined scan order and the initial current pair of edge crossings are set to the first and second edge crossings in the current scanline, which occur first and second respectively in the current scanline in a predetermined scan order. 54. The computer program as claimed in claim 49, wherein in the event there are no more active edges in the previous scanline that have matched or finished, then the first and second active edges of the pair are both set to a value indicating that no first and second active edges exist. The computer program as claimed in claim 49, wherein in the event there are no more edge crossings in the current scanline that have been matched or created as active edges, then the first and second edge crossings of the pair are both set to a value Si ••indicating that no first and second edge crossings exist. 56. The computer program as claimed in claim 49, wherein said edge detecting code passes said edge crossings to said active edge generating code on a scanline basis and said S 25 active edge generating code passes said generated active edges to said segment generating code on a scanline basis. 57. The computer program as claimed in claim 49, wherein said edge detecting code passes said edge crossings to said active edge generating code on an image basis and said passes said edge crossings to said active edge generating code on an image basis and said 524206.doc active edge generating code passes said generated active edges to said segment generating code on an image basis. 58. A method of converting a bitmap image comprising at least one region to a segment representation of outlines of said at least one region, the method substantially as described herein with reference to Figs. 1 to 13 of the accompanying drawings. 59. Apparatus for converting a bitmap image comprising at least one region to a segment representation of outlines of said at least one region, the apparatus substantially as described herein with reference to Figs. 1 to 14. A computer program for converting a bitmap image comprising at least one region to a segment representation of outlines of said at least one region, the computer program substantially as described herein with reference to Figs. 1 to 14. Dated 21 December, 2001 CANON KABUSHIKI KAISHA. Patent Attorneys for the Applicant/Nominated Person SPRUSON FERGUSON 524206.doc