US5068803A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for filling contours in digital typefaces
Assignee: Sun Microsystems Inc
•
Filing: 1989-09-15
•
Granted: 1991-11-26
•
Expires: 2009-09-15
Abstract
Abstract A method and apparatus is described which fills in the pixels missed when drop-out occurs during the fill process of character contours. The character contour is decomposed into a series of rook moves. The pixel selected is the one more covered by the actual shape of the portion of the curve where the rook moves are coincident and dropout occurs. This is dependent upon the slope of each of the curves at the location of dropout. Preferably the length of the sequence of colinear consecutive rook moves is used to approximate the slopes of the curves. The target pixel of the longest sequence of colinear rook moves is more covered than its opposite pixel and therefore the target pixel is set. The target pixel for a rook move is the pixel in the winding direction (i.e., left or right direction) along the rook move. Thus the target pixel of the stronger rook moves will be set and added to the bit map image generated using a outline fill process. In the preferred embodiment, the rook moves are examined to determine the length of a sequence, that is the number of rook moves that are sequentially in alignment with one another. A strength value is then assigned to each of those rook moves in a sequence equal to the number of rook moves in the sequence. The strength value of the rook move is then compared to the strength value of the opposite pixel, that is the pixel opposite the target pixel for a particular rook move. If the strength value of the target pixel of the rook move is greater than the strength of the opposite pixel, the opposite pixel value if reset to zero and the target pixel is set to equal the strength of the sequence. This process is performed for each rook move in a sequence and for each sequence of rook moves around the contour of the character. Once all rook moves have been evaluated, the value is assigned to the pixels of the character according to this process, are adjusted to reflect a bit map image to be displayed. This is achieved by turning on all bits which are greater than zero. The bit map generated is then logically ORed with the bit map generated using the contour fill process to provide a filled character in which drop out is eliminated and the distortion to the character is minimized.
Inventors
- 👤 Jacobo Valdes
- 👤 Eduardo Martinez
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 15:00
CPC Classifications
G; G06; G06T; G06T1/00; G09; G09G; G09G5/00; G09G5/22; G09G5/24; G06K; G06K11/00
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
235 words
A computer-implemented method for filling in outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, said method comprising the steps of: breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move; generating a first bit map of the character by setting those pixels between rook moves to equal a value of one; generating a second bit map of the character comprising the steps of: initializing the pixels of the bit map to zero; determining the strength of each rook move, the strength of a rook move corresponding to the total number of rook moves in a colinear sequence; if the strength of the rook move is greater than the target pixel value and the strength of the rook move is greater than the opposite pixel value; setting the target pixel value to equal the strength of the rook move; setting the opposite pixel value to equal zero; and translating the pixel values having a value greater than zero to a value of one thereby providing a second bit map of the character; and performing a logical OR of the first and second bit maps of the character whereby the resulting bit map is the filled character.
Claim 2
Dependent Claim
235 words
A computer-implemented method for filling in outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, said method comprising the steps of: breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move; generating a first bit map of the character by setting those pixels between rook moves to equal a value of one; generating a second bit map of the character comprising the steps of: initializing the pixels of the bit map to zero; determining the strength of each rook move, the strength of a rook move corresponding to the total number of rook moves in a colinear sequence; if the strength of the rook move is greater than the target pixel value and the strength of the rook move is greater than the opposite pixel value; setting the target pixel value to equal the strength of the rook move; setting the opposite pixel value to equal zero; and translating the pixel values having a value greater than zero to a value of one thereby providing a second bit map of the character; and performing a logical OR of the first and second bit maps of the character whereby the resulting bit map is the filled character.
Claim 3
Dependent Claim
121 words
The method of claim 1 wherein the step of generating a first bit map of the character comprises the steps of: evaluating a character scan line by scan line starting at a first pixel in a scan line and continuing to an end pixel of the scan line; setting pixels to a value of one which are subsequent to a first rook move which crosses the scan line; setting pixels to a value of zero subsequent to a second rook move which crosses the scan line; setting subsequent pixels to a value of one if subsequent first rook moves cross the scan line; and setting subsequent pixels to a value of zero if subsequent second rook moves cross the scan line.
Claim 4
Dependent Claim
32 words
The method of claim 1 wherein the steps of determining the strength of the rook moves and setting the target and opposite pixels are sequentially determined around the outline of the character.
Claim 5
Dependent Claim
193 words
A computer-implemented method for eliminating the drop out which occurs in filled outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, the filled outlines depicted by a first bit mapped image of the character said method comprising the steps of: breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move and have an initial value of zero; determining the strength of each rook move, the strength of a rook move corresponding to the total number of rook moves in a colinear sequence; if the strength of the rook move is greater than the target pixel value and the strength of the rook move is greater than the opposite pixel value; setting the target pixel value to equal the strength of the rook move; and setting the opposite pixel value to equal zero; adding those pixel values generated which are greater than zero to the first bit mapped image whereby the drop out is eliminated.
Claim 6
Dependent Claim
193 words
A computer-implemented method for eliminating the drop out which occurs in filled outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, the filled outlines depicted by a first bit mapped image of the character said method comprising the steps of: breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move and have an initial value of zero; determining the strength of each rook move, the strength of a rook move corresponding to the total number of rook moves in a colinear sequence; if the strength of the rook move is greater than the target pixel value and the strength of the rook move is greater than the opposite pixel value; setting the target pixel value to equal the strength of the rook move; and setting the opposite pixel value to equal zero; adding those pixel values generated which are greater than zero to the first bit mapped image whereby the drop out is eliminated.
Claim 7
Dependent Claim
77 words
The method of claim 4 wherein the step of adding pixel values greater than zero to the first bit mapped image comprises the steps of: translating the pixel values having a value greater than zero to a value of one thereby providing a second bit map of the character; performing a logical OR of the first and second bit maps of the character whereby the resulting bit map is the filled character with the drop out eliminated.
Claim 8
Dependent Claim
32 words
The method of claim 4 wherein the steps of determining the strength of the rook moves and setting the target and opposite pixels are sequentially determined around the outline of the character.
Claim 9
Dependent Claim
189 words
A computer-implemented method for eliminating the drop out which occurs in filled outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, the filled outlines depicted by a first bit mapped image of the character, said method comprising the steps of: breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move and have an initial value of zero; setting to a value of one those target pixels which are associated with rook moves having a strong visual effect on a viewer of the character and setting the corresponding opposite pixels to zero, said strong visual effect of the rook moves being related to the number of rook moves in a colinear sequence wherein the larger the number of rook moves in a colinear sequence, the stronger the visual effect; adding those pixel values set to a value of one to the first bit mapped image whereby the drop out is eliminated.
Claim 10
Dependent Claim
189 words
A computer-implemented method for eliminating the drop out which occurs in filled outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, the filled outlines depicted by a first bit mapped image of the character, said method comprising the steps of: breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move and have an initial value of zero; setting to a value of one those target pixels which are associated with rook moves having a strong visual effect on a viewer of the character and setting the corresponding opposite pixels to zero, said strong visual effect of the rook moves being related to the number of rook moves in a colinear sequence wherein the larger the number of rook moves in a colinear sequence, the stronger the visual effect; adding those pixel values set to a value of one to the first bit mapped image whereby the drop out is eliminated.
Claim 11
Dependent Claim
166 words
The method of claim 7 wherein the step of setting to a value of one those target pixels which are associated with rook moves having a strong visual effect on a viewer of a character comprises the steps of: determining the strength of each rook move, the strength of a rook move corresponding to the total number of rook moves in a colinear sequence; if the strength of the rook move is greater than the target pixel value and the strength of the rook move is greater than the opposite pixel value; setting the target pixel value to equal the strength of the rook move; and setting the opposite pixel value to equal zero; translating the pixel values having a value greater than zero to a value of one thereby providing a second bit map of the character; performing a logical OR of the first and second bit maps of the character whereby the resulting bit map is the filled character with the drop out eliminated.
Claim 12
Dependent Claim
32 words
The method of claim 7 wherein the steps of determining the strength of the rook moves and setting the target and opposite pixels are sequentially determined around the outline of the character.
Claim 13
Independent Claim
246 words
An apparatus for filling in outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, said method comprising: means for breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move; means for generating a first bit map of the character by setting those pixels between rook moves to equal a value of one; means for generating a second bit map of the character comprising: means for initializing the pixels of the bit map to zero; means for determining the strength of each rook move, the strength of a rook move corresponding to the total number of rook moves in a colinear sequence; if the strength of the rook move is greater than the target pixel value and the strength of the rook move is greater than the opposite pixel value; means for setting the target pixel value to equal the strength of the rook move; means for setting the opposite pixel value to equal zero; and means for translating the pixel values having a value greater than zero to a value of one thereby providing a second bit map of the character; and means for performing a logical OR of the first and second bit maps of the character whereby the resulting bit map is the filled character.
Claim 14
Independent Claim
246 words
An apparatus for filling in outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, said method comprising: means for breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move; means for generating a first bit map of the character by setting those pixels between rook moves to equal a value of one; means for generating a second bit map of the character comprising: means for initializing the pixels of the bit map to zero; means for determining the strength of each rook move, the strength of a rook move corresponding to the total number of rook moves in a colinear sequence; if the strength of the rook move is greater than the target pixel value and the strength of the rook move is greater than the opposite pixel value; means for setting the target pixel value to equal the strength of the rook move; means for setting the opposite pixel value to equal zero; and means for translating the pixel values having a value greater than zero to a value of one thereby providing a second bit map of the character; and means for performing a logical OR of the first and second bit maps of the character whereby the resulting bit map is the filled character.
Claim 15
Dependent Claim
128 words
The apparatus of claim 10 wherein the means for generating a first bit map of the character comprises: means for evaluating a character scan line by scan line starting at a first pixel in a scan line and continuing to an end pixel of the scan line; means for setting pixels to a value of one which are subsequent to a first rook move which crosses the scan line; means for setting pixels to a value of zero subsequent to a second rook move which crosses the scan line; means for setting subsequent pixels to a value of one of subsequent first rook moves cross the scan line; and means for setting subsequent pixels to a value of zero if subsequent second rook moves cross the scan line.
Claim 16
Dependent Claim
31 words
The apparatus of claim 10 wherein the means for determining the strength of the rook moves and setting the target and opposite pixels sequentially determine around the outline of the character.
Claim 17
Independent Claim
198 words
An apparatus for eliminating the drop out which occurs in filled outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, the filled outlines depicted by a first bit mapped image of the character said means comprising: means for breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move and have initial values of zero; means for determining the strength of each rook move, the strength of a rook move corresponding to the total number of rook moves in a colinear sequence; if the strength of the rook move is greater than the target pixel value and the strength of the rook move is greater than the opposite pixel value; means for setting the target pixel value to equal the strength of the rook move; and means for setting the opposite pixel value to equal zero; means for adding those pixel values generated which are greater than zero to the first bit mapped image whereby the drop out is eliminated.
Claim 18
Independent Claim
198 words
An apparatus for eliminating the drop out which occurs in filled outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, the filled outlines depicted by a first bit mapped image of the character said means comprising: means for breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move and have initial values of zero; means for determining the strength of each rook move, the strength of a rook move corresponding to the total number of rook moves in a colinear sequence; if the strength of the rook move is greater than the target pixel value and the strength of the rook move is greater than the opposite pixel value; means for setting the target pixel value to equal the strength of the rook move; and means for setting the opposite pixel value to equal zero; means for adding those pixel values generated which are greater than zero to the first bit mapped image whereby the drop out is eliminated.
Claim 19
Dependent Claim
78 words
The apparatus of claim 13 wherein the means for adding pixel values greater than zero to the first bit mapped image comprises: means for translating the pixel values having a value greater than zero to a value of one thereby providing a second bit map of the character; means for performing a logical OR of the first and second bit maps of the character whereby the resulting bit map is the filled character with the drop out eliminated.
Claim 20
Dependent Claim
31 words
The apparatus of claim 13 wherein the means for determining the strength of the rook moves and setting the target and opposite pixels sequentially determine around the outline of the character.
Claim 21
Independent Claim
189 words
An apparatus for eliminating the drop out which occurs in filled outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, the filled outlines depicted by a first bit mapped image of the character, said apparatus comprising: means for breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move and have an initial values of zero; means for setting to a value of one those target pixels which are associated with rook moves having a strong visual effect on a viewer of the character and setting the corresponding opposite pixels to zero, said strong visual effect of the rook moves being related to the number of rook moves in a colinear sequence wherein the larger the number of rook moves in a colinear sequence, the stronger the visual effect; adding those pixel values set to a value of one to the first bit mapped image whereby the drop out is eliminated.
Claim 22
Independent Claim
189 words
An apparatus for eliminating the drop out which occurs in filled outlines of characters in digital typefaces, each character outline having one or more contours, each contour having a direction, the filled outlines depicted by a first bit mapped image of the character, said apparatus comprising: means for breaking down the contours of the characters into a series of rook moves according to the direction of the contour, each rook move having a target and opposite pixel associated with it which are adjacent to the rook move and have an initial values of zero; means for setting to a value of one those target pixels which are associated with rook moves having a strong visual effect on a viewer of the character and setting the corresponding opposite pixels to zero, said strong visual effect of the rook moves being related to the number of rook moves in a colinear sequence wherein the larger the number of rook moves in a colinear sequence, the stronger the visual effect; adding those pixel values set to a value of one to the first bit mapped image whereby the drop out is eliminated.
Claim 23
Dependent Claim
173 words
The apparatus of claim 16 wherein the means for setting to a value of one those target pixels which are associated with rook moves having a strong visual effect on a viewer of a character comprising: means for determining the strength of each rook move, the strength of a rook move corresponding to the total number of rook moves in a colinear sequence; if the strength of the rook move is greater than the target pixel value and the strength of the rook move is greater than the opposite pixel value; means for setting the target pixel value to equal the strength of the rook move; and means for setting the opposite pixel value to equal zero; means for translating the pixel values having a value greater than zero to a value of one thereby providing a second bit map of the character; means for performing a logical OR of the first and second bit maps of the character whereby the resulting bit map is the filled character with the drop out eliminated.
Claim 24
Dependent Claim
31 words
The method of claim 16 wherein the means for determining the strength of the rook moves and setting the target and opposite pixels sequentially determine around the outline of the character.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-11-25 | 1995-05-27 | 1995-11-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-11-25 | 1999-05-27 | 1999-11-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-11-25 | 2003-05-27 | 2003-11-26 | $7700.00 | Window Closed / Lapsed |