 |
Claims  |
|
|
What is claimed is:
1. In a computer system comprising a display for displaying characters of a
digital typeface, wherein the typeface is generated for a particular scale
and each character of the typeface is generated for a particular scale and
each character of the typeface is described in a format using control
points comprising X-Y coordinate pairs, a method for minimizing the visual
degradation of the characters of the typeface, said method comprising the
steps of:
forming a frame for each character from said control points, said frame
represented by a plurality of frame points comprising X-Y coordinate
pairs;
determining vertical strokes which comprise each character, said strokes
formed by a plurality of frame points and identified as X strokes;
determining horizontal strokes which comprise each character, said
horizontal strokes formed by a plurality of frame points and identified as
Y strokes;
adjusting the X coordinates of the frame points for each character of the
typeface representative of X strokes, said X strokes being oriented in the
vertical direction and prioritized in order of visual importance to the
character, said strokes being adjusted according to priority wherein the
amount of adjustment of the lower priority strokes is dependent upon the
higher priority strokes, and adjustment regularizing the thicknesses of
the X strokes and preserving the width of the character; adjusting the X
coordinates of the frame points which do not form a stroke, said
adjustment dependent on preserving the width of the character and the
thicknesses of adjusted X strokes;
adjusting the Y coordinates of the frame points for each character of the
typeface representative of Y strokes, said Y strokes being oriented in the
horizontal direction and prioritized in order of visual importance to the
character, said strokes being adjusted according to thepriority wherein
the amount of adjustment of the lower priority strokes is dependent upon
the thicknesses of the higher priority strokes, said adjustment preserving
the heights of the characters of the typeface and the horizontal alignment
of the Y strokes; and
adjusting the Y coordinates of the frame points which do not form a stroke,
said adjustment dependent on preserving the height of the character and
the thicknesses and the horizontal alignment of the adjusted strokes;
whereby the important visual features of the characters of the typeface are
maintained thereby minimizing the visual degradation of the typeface.
2. The method according to claim 1 further comprising:
determining diagonal strokes comprising each character which are oriented
in the diagonal direction, said strokes formed by a plurality of frame
points;
adjusting the frame points of each character of the typeface representative
of the diagonal strokes, said adjustment dependent on preserving the
adjusted thicknesses and locations of the adjusted X and Y strokes.
3. The method of claim 1 wherein the frame is formed in such a manner that
there is a straight line segment for every horizontal tangent, vertical
tangent, straight line segment, tangent of an inflection point and
tangents at a slope discontinuity, said segments connected by weight
segments.
4. The method of claim 1 wherein the step of adjusting the X coordinates of
the frame points which do not form a stroke comprises aligning each X
coordinate with the closest side of a main street stroke and rounding the
coordinate value to the nearest grid position.
5. In a computer system comprising a display for displaying characters of a
digital typeface, wherein the typeface is generated for a particular scale
and each character of the typeface is described in a format using control
points comprising X-Y coordinate pairs, an apparatus for implementing a
method for minimizing the visual degradation of the characters of the
typeface, and apparatus comprising:
means for executing a program routine to form a frame for each character
from said control points, said frame represented by a plurality of frame
points comprising X-Y coordinate pairs, said frame points forming a
polygon having determinable geometric relationships with said control
points based on said coordinates;
means for executing a program routine to determine vertical strokes which
comprise each character, said strokes formed by a plurality of frame
points and identified as X strokes;
means for executing a program routine to determine horizontal strokes which
comprise each character, said horizontal strokes formed by a plurality of
frame points and identified as Y strokes;
means for executing a program routine to adjust the X coordinates of the
frame points for each character of the typeface representative of X
strokes, said X strokes being oriented in the vertical direction and
prioritized in order of visual importance to the character, said strokes
being adjusted according to priority wherein the amount of adjustment of
the lower priority strokes is dependent upon the higher priority strokes,
said adjustment regularizing the thicknesses of the X strokes and
preserving the width of the character.
means for executing a program routine to adjust the X coordinates of the
frame points which do not form a stroke, said adjustment dependent on
preserving the width of the character and the thicknesses of adjusted X
strokes;
means for executing a program routine to adjust the Y coordinates of the
frame points for each character of the typeface representative of Y
strokes, said Y strokes being oriented in the horizontal direction and
prioritized in order of visual importance to the character, said strokes
being adjusted according to the prior wherein the amount or adjustment of
the lower priority strokes is dependent upon the thicknesses of the higher
priority strokes, said adjustment preserving the heights of the characters
of the typeface and the horizontal alignment of the Y strokes; and
means for executing a program routine to adjust the Y coordinates of the
frame points which do not form a stroke, said adjustment dependent on
preserving the height of the character and the thicknesses and the
horizontal alignment of the adjusted strokes;
whereby the important visual features of the characters of the typeface are
maintained thereby minimizing the visual degradation of the typeface.
6. The apparatus of claim 5 further comprises:
means for executing a program routine to determine diagonal strokes
comprising each character which are oriented in the diagonal direction,
said strokes formed by a plurality of frame points;
means for executing a program routine to determine the frame points of each
character of the typeface representative of the diagonal strokes, said
adjustment dependent on preserving the adjusted thicknesses and locations
of the adjusted X and Y strokes.
7. The apparatus of claim 5 wherein the program routine executed to form
frame forms the frame in such a manner that there is a straight line
segment for every horizontal tangent, vertical tangent, straight line
segment, tangent of an inflection point and tangents at a slope
discontinuity, said segments connected by straight segments.
8. The apparatus of claim 5 wherein the program routine executed to adjust
the X coordinates of the frame points which do not form a stroke comprises
a program subroutine for aligning each X coordinate with the closest side
of a main street stroke and rounding the coordinate value of the nearest
grid position. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
In addition to the parent application, this application is also related to
the following divisional applications of the parent application:
a. U.S. patent application Ser. No. 07/846,213, filed on Mar. 4, 1992,
entitled Method and Apparatus for Minimizing Visual Degradation of Digital
Typeface--Character Analysis;
b. U.S. patent application Ser. No. 07/846,781, filed on Mar. 4, 1992,
entitled Method and Apparatus for Minimizing Visual Degradation of Digital
Typeface--Horizontal Adjustment;
c. U.S. patent application Ser. No. 07/846,586, filed on Mar. 5, 1992,
entitled Method and Apparatus for Minimizing Visual Degradation of Digital
Typeface--Vertical Adjustment;
d. U.S. patent application Ser. No. 07/846,584, filed on Mar. 5, 1992,
entitled Method and Apparatus for Minimizing Visual Degradation of Digital
Typeface--Diagonal Adjustment.
FIELD OF THE INVENTION
The method and apparatus of the present invention relates to the technique
of intelligent scaling. More particularly, the present invention relates
to data processing apparatus and methods for minimizing the visual
degradation of digital typefaces.
ART BACKGROUND
As the popularity and affordability of computers have increased, so has the
number of computer programs available. The computer programs available are
diverse, encompassing a wide variety of applications. In addition, the
range of users has broadened from the computer programmer of 10 years ago
to businesses that use the computer for a variety of tasks including word
processing and accounting.
It is well understood from the nature of digital representations of
continuous analog forms that some degradation will occur when translating
from a continuous representation (such as a typeface prepared manually by
a calligrapher) to a discrete digital representation. Programmers and
engineers, the original users of computers and viewers of digital
typefaces generated by computers (typically on CRT's and computer
printers) were not concerned about how the type looked so long as the
characters were somewhat readable. However, not only has the viewer of
digital type changed but also the requirements with respect to legibility
and degradation of type.
As a result, the ability to provide legible digital typefaces has become
extremely important for the automation of the printing and typesetting
industry as well as for word processor users who require legible, letter
quality type. For further information on digital typefaces, see: Bigelow &
Day, "Digital Typography", Scientific American, p. 106-119, August, 1983;
Karow, Digital Formats For Typefaces, (URW Verlag 1987).
Typically, to produce a digital typeface, the typeface is developed
manually, digitized and input into a digital typeface format such as
IKARUS. Problems arise because the control points of the character which
define the outline of the character do not always coincide to the discrete
grid positions corresponding to the resolution of the digital display or
printer. As a result, the control points are rounded off to the nearest
grid position and parts of characters which originally had the same
dimension (for example the widths of the vertical portions of an upper
case "I" and "J") now have different dimensions. This method results in
the visual degradation of the typeface because the reader does not easily
see and recognize the characters with the height and width relationships
among the characters changed. Further degradation of the typeface occurs
when the size of the characters is globally increased by multiplying the
dimensions by a factor, because the inconsistencies in the typeface are
also multiplied by that factor.
Another problem arises due to the fact that the thicknesses or heights of
characters or portions of characters may be approximately, but not
exactly, the same height or width. As the scale of the typeface decreases,
the likelihood of distortion increases due to the small differences in
height or width. If, for example, the heights of the characters are
exactly the same, the scaled version of each of the characters would also
be exactly the same. However, if the heights differ by a small value and
the display is a low resolution device, the height of one character may be
rounded off to one pixel and the height of another character may be
rounded off to a different pixel even though the original difference in
height may have been less than 0.25 of a pixel. In small scale (low
resolution) cases similar to the above example, it is desirable to round
the heights of the character to the same pixel in order to maintain the
original symmetry and proportions. Thus, the typeface loses the original
symmetry and proportion among characters and portions of characters in the
typeface again resulting in the visual degradation of the typeface.
To solve these problems, skilled technicians are employed to manually
correct any deficiencies in the typeface by reviewing each character and
modifying portions of the character which the technician usually perceives
to increase the legibility. However, this process is time consuming and
costly. There are two primary variables that have to be considered when
scaling a digital typeface for display: (1) the different sizes of the
font, e.g. 9 point, 10 point or 12 point; and (2) the different
resolutions of the display or output device. For each typeface, the manual
process must be performed for each possible scale which is equal to the
product of the resolution and font size. In addition, the quality of the
work is dependent on the skill of the technician. Computer aided processes
have been introduced to assist in the manual process. For example there
are systems, which display the character and provide a means for the
skilled technician to view and modify the character on the display.
However, the process of adjustment, what to adjust and how much to adjust
is still performed by a skilled technician. U.S. Pat. No. 4,675,830
discloses a method for producing scaling typeface data in which the
relative dimensions of the characters are preserved. However, the process
disclosed requires not only the input of data which describe the typeface
but also control information such as key points of the typeface which are
aligned with the grid points and dimensions that are to exist between grid
points. This additional input must be generated manually by a skilled
technician who develops the control information by visual inspection of
the typeface.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to minimize the visual
degradation of a digital typeface.
It is an object of the invention to provide an automated method for
increasing the legibility of a digital typeface.
It is further an object of the invention to maintain the visual symmetry
and proportions among the characters of the typeface.
It is an object of the present invention to provide a method of intelligent
scaling.
It is an object of the invention to provide a process for establishing a
classification of visual components which comprise the characters of the
typeface.
It is further an object of the invention to provide a process for
determining the priority of visual components of the typeface wherein the
higher priority components are aligned with grid positions and the
alignment of the lower priority components is dependent on the alignment
of the higher priority component.
Through the method and apparatus of the present invention, the visual
degradation of digital typefaces is minimized without the manual input of
the skilled technicians.
The present invention provides methods and apparatus which are most
advantageously used in conjunction with a digital computer to minimize the
visual degradation that occurs when preparing and scaling digital
typefaces. In the method and apparatus of the present invention, the
frames, which are used to describe each character, are modified according
to a predetermined set of rules which analyzes and establishes the visual
components which make up each character and the priority in which the
components are aligned on grid points and with respect to previously
aligned components.
The control points, which are used to define the character in a digital
typeface format, are analyzed to determine the frame of a character. The
frame is a simplified form of the character which comprises important
visual properties or components of the character which are to be
preserved. The frame is analyzed in the horizontal direction and vertical
direction to determine the priority or importance of the coordinates which
define the outline of the frame. The important coordinates, referred to as
master coordinates, are then further analyzed to determine the
corresponding master segments. These segments are then analyzed to
determine the pairs of segments which form strokes. The strokes are
classified and prioritized.
Using the visual components determined, from the analysis of the character,
the coordinates of the frame are adjusted starting with the highest
priority component, the highest priority stroke, according to certain
rules which are dependent upon whether the strokes formed are oriented in
the horizontal or vertical direction. Components lower in priority, such
as the lower priority strokes, master coordinates which are not part of a
stroke and frame coordinates which are not defined as master coordinates,
are then modified or aligned in a manner that is dependent on the
previously aligned components. As a result of the priority and rules for
adjustment, the important visual components of each character and the
relationship of the visual components of each character with the other
characters of the typeface are preserved thereby minimizing the visual
degradation of the typeface.
BRIEF DESCRIPTION OF THE DRAWINGS
The objects, features and advantages of the method and apparatus for the
present invention will be apparent from the following detailed description
of the preferred embodiment in which:
FIG. 1 illustrates a computer incorporating the present invention.
FIGS. 2(a)-2(d) illustrates the control points used to digitally describe
the character and
FIG. 2e illustrates the contour convention used in the description of the
method and apparatus of the present invention.
FIG. 3 is a flow chart generally depicting the process of the present
invention.
FIG. 4a is an illustration of a character and the corresponding frame and
FIG. 4b is a flow chart illustrating a method for determining the frame of
the character.
FIG. 5 shows the letter "e" and its control points.
FIG. 6 shows the frame formed from the letter "e" depicted in FIG. 5.
FIG. 7a, 7b and 7c illustrates the geometric relationships between control
points and frame points.
FIG. 8 is a flow chart briefly describing the analysis process of the
present invention.
FIG. 9a is a flow chart describing the process of determining the visual
components with respect to X coordinates up to the highest priority visual
component, the X main street.
FIG. 9b is a flow chart describing the process of determining the visual
components with respect to the Y coordinates up to the highest priority
visual component, the Y main street.
FIG. 10a illustrates X master segments and X strokes and
FIG. 10b illustrates Y master segments and Y strokes.
FIGS. 11a and 11b are flow charts describing the limited divergence process
of the present invention.
FIG. 12 is a flow chart describing the horizontal adjustment process of the
present invention.
FIG. 13a illustrates the relative adjustment process of the present
invention and
FIG. 13b illustrates the method for adjusting slave coordinates.
FIGS. 14(a) and 14(b) are illustrations of local extremes.
FIG. 15 is a flow chart illustrating the process of determining clusters
with respect to the Y alignment adjustment process of Y coordinates.
FIG. 16 is a flow chart describing the Y alignment adjustment process of
the present invention.
FIGS. 17a and 17b are flow charts describing the vertical adjustment
process of the present invention.
FIG. 18 illustrates the location of the clusters and strokes used to
describe the vertical adjustment process of the present invention.
FIG. 19 is a flow chart which describes the diagonal adjustment process of
the present invention.
FIG. 20 illustrates the adjustment of a diagonal stroke in the character
"N".
FIG. 21a-21d illustrate the adjustment of the frame points of diagonal
strokes according to the present invention.
NOTATION AND NOMENCLATURE
The detailed descriptions which follow are presented largely in terms of
algorithms and symbolic representations of operations on data bits within
a computer memory. These algorithmic descriptions and representations are
the means used by those skilled in the data processing arts to most
effectively convey the substance of their work to others skilled in the
art.
An algorithm is here, and generally, conceived to be a self-consistent
sequence of steps leading to a desired result. These steps are those
requiring physical manipulations of physical quantities. Usually, though
not necessarily, these quantities take the form of electrical or magnetic
signals capable of being stored, transferred, combined, compared, and
otherwise manipulated. It proves convenient at times, principally for
reasons of common usage, to refer to these signals as bits, values,
elements, symbols, characters, terms, numbers, or the like. It should be
borne in mind, however, that all of these and similar terms are to be
associated with the appropriate physical quantities and are merely
convenient labels applied to these quantities.
Further, the manipulations performed are often referred to in terms, such
as adding or comparing, which are commonly associated with mental
operations performed by a human operator. No such capability of a human
operator is necessary, or desirable in most cases, in any of the
operations described herein which form part of the present invention; the
operations are machine operations. Useful machines for performing the
operations of the present invention include general purpose digital
computers or other similar devices. In all cases there should be borne in
mind the distinction between the method operations in operating a computer
and the method of computation itself. The present invention relates to
method steps for operating a computer in processing electrical or other
(e.g., mechanical, chemical) physical signals to generate other desired
physical signals.
The present invention also relates to apparatus for performing these
operations. This apparatus may be specially constructed for the required
purposes or it may comprise a general purpose computer as selectively
activated or reconfigured by a computer program stored in the computer.
The algorithms presented herein are not inherently related to a particular
computer or other apparatus. In particular, various general purpose
machines may be used with programs written in accordance with the
teachings herein, or it may prove more convenient to construct more
specialized apparatus to perform the required method steps. The required
structure for a variety of these machines will appear from the description
given below.
DETAILED DESCRIPTION OF THE INVENTION
The following detailed description will be divided into several sections.
The first of these will discuss a general system arrangement for
performing the process for minimizing the visual degradation of digital
typefaces. Subsequent sections will deal with such aspects of the present
invention as the analysis of the typeface data to determine the important
visual components of each character in the typeface and the priority of
adjustment of the visual components and adjustment of the characters in
horizontal, vertical and diagonal directions.
In addition, in the following description, numerous specific details are
set forth such as algorithmic conventions, character definition
conventions, specific numbers of bits, etc., in order to provide a
thorough understanding of the present invention. However, it will be
obvious to one skilled in the art that the present invention may be
practiced without these specific details. In other instances, well-known
circuits and structures are not described in detail in order not to
obscure the present invention unnecessarily.
General System Configuration
FIG. 1 shows a typical computer-based system for increasing the legibility
of digital typeface according to the present invention. Shown there is a
computer 1 which comprises three major components. The first of these is
the input/output (I/O) circuit 2 which is used to communicate information
in appropriately structured form to and from the other parts of the
computer 1. Also shown as a part of computer 1 is the central processing
unit (CPU) 3 and memory 4. These latter two elements are those typically
found in most general purpose computers and almost all special purpose
computers. In fact, the several elements contained within computer 1 are
intended to be representative of this broad category of data processors.
Particular examples of suitable data processors to fill the role of
computer 1 include machines manufactured by Sun Microsystems, Inc.,
Mountain View, Calif. Other computers having like capabilities may of
course be adapted in a straightforward manner to perform the functions
described below.
Also shown in FIG. 1 is an input device 5, shown in typical embodiment as a
keyboard. It should be understood, however, that the input device may
actually be a card reader, magnetic or paper tape reader, or other
well-known input device (including, of course, another computer). A mass
memory device 6 is coupled to the I/O circuit 2 and provides additional
storage capability for the computer 1. The mass memory may include other
programs and the like and may take the form of a magnetic or paper tape
reader or other well known device. It will be appreciated that the data
retained within mass memory 6, may, in appropriate cases, be incorporated
in standard fashion into computer 1 as part of memory 4.
In addition, a display monitor 7 is illustrated which is used to display
messages or other communications to the user. Such a display monitor may
take the form of any of several well-known varieties of CRT displays.
Preferably, the display monitor 7 may also display the graphic images i.e.
the typefaces generated from the digital typeface data modified according
to the process of the present invention. A cursor control 8 is used to
select command modes and edit the input data, such as, for example, the
scale of the typeface, and provides a more convenient means to input
information into the system.
Process Overview
Referring to FIGS. 2(a)-2(d) several upper case and lower case characters
of a typeface are shown. In FIGS. 2(a)-2(d) lower case "o" and "f" and
upper case "N" and "G" are illustrated. Associated with each character is
a set of points, for example points 10, 15, 20 and 25 which are the
control points of the character. The control points are dependent on the
digital format that is used to describe the character. In the present
example the characters are described and control points reflect a contour
format comprising straight line segments and arcs of conics and beziers.
Straight line segments are described by two control points, conic arcs are
described by three control points and bezier arcs are described by four
control points. For example, FIGS. 2(a)-2(d) control points 10, 15 and 25
describe a conic arc between points 15 and 25 wherein control point 10
dictates the arc or the radius of the curve. There are many other formats
such as the IKARUS format, DI format, the VC format and the VS format
which are also used to define digital typefaces. However, in the
description of the present invention the format described above will be
used.
Throughout the description of the process, the characters are represented
and described according to a single convention. However, the process is
not limited to use with a single convention and may be easily applied to
other conventions. In the following convention, the character consists of
one or more contours each defining a boundary between "black" and "white".
Each contour consists of a begin point followed by a sequence of arcs.
Each arc is defined by a curve type and two or more control points. Due to
the continuity of the contour the first point of each arc is implicitly
the last of the previous one. The last point of the last arc must be
coincident with the beginning point. The contours are defined in relation
to a coordinate system such that: (1) when the character is viewed in the
normal reading position the X axis points in the direction of successive
character placement, e.g. to the right for the roman alphabet, down for a
Chinese font; (2) the Y axis is 90% counter clockwise from X; and (3) the
direction of the contour is clockwise if the region enclosed is black,
otherwise the direction of the contour is counter clockwise. No arc has
inflections or extremes except at the end points of the arc. Note that an
arc that has an inflection or extreme which is not at an end point, can be
subdivided into two arcs at the point of the inflection or extreme such
that the inflection or extreme occurs at the end points of the newly
created arcs.
To better understand this convention the letter "e" is illustrated.
Referring to FIG. 2(e) the outside contour of the character is oriented in
a clockwise direction reflecting that the outside contour encases a black
region. The inside contour surrounds a white region and is therefore the
contour oriented in the counter clockwise direction.
The curve types description (i.e. straight line segment, arcs of conics or
arcs of Beziers) remain invariant during the adjustment process only the
control points change. The adjusted character is then the one defined by
the same curve types description controlled by the adjusted control
points.
In the description reference is made to the the resolution, font size and
the scale of the display device. The resolution of the display device is
described in terms of pixels, a known computer graphic display quantity.
The resolution may be expressed as the total number of pixels in the
horizontal and vertical direction (e.g. 1024 pixels .times.1024 pixels) of
the display or the number of pixels per inch. The font size is expressed
in units called points, a well known unit in the art of typography. If a
font size is ten point, the distance to the top of the highest character
of the font (e.g. the letter "A"), called the ascender distance, plus the
distance to the bottom of the lowest character of the font (e.g., the
letter "g") called the descender distance, is ten points in length. One A
point is equal to 1/72.3 inches. The scale is equal to the product of
resolution and the font size, for example, if the font size is 6 points
and the resolution is 144 pixels/inch the scale is:
##EQU1##
Referring to FIG. 3, the process of the present invention is briefly
described. At block 50, the input data, which consists of the control
points for each of the characters of the typeface, is input to the system.
At block 55, the system analyzes this information and determines from the
control points input the frame of the character. At block 60, the
coordinates which define the frame are further analyzed to determine the
important visual components of each of the characters of the typeface and
the priority or order of importance that these components adjusted to
minimize the visual degradation of the typeface. At block 65, using the
frames of the characters and the analysis of the important visual
components, the characters of the typeface are adjusted using an
innovative intelligence scaling method to produce adjusted frames
according to the scale desired. The process preserves the important visual
features of the typeface, particularly the consistency of the stroke
thicknesses, the horizontal alignment of the characters (i.e., the
alignment of the Y coordinates of the characters), the proportion of the
white space within a character as well as the total width of the
characters. At block 70, the original control points of each of the
characters are then adjusted to correspond to the adjusted frames. The
adjusted control points are used to control the curve types description to
produce characters in which the visual degradation of the typeface has
been minimized.
Analysis of Characters of Typeface
The first step of the process is to determine the frame of each character.
The object of determining the frame is to simplify each of the characters
to a series of discrete points which may be analyzed and modified to
adjust the character. A frame is a collection of polygons, one for each of
the characters contours. These polygons are simpler than the original
character, yet they retain the characters' fundamental visual properties.
The frame comprises a sequence of straight line segments that follow the
shape of the character such that there is a straight line segment for
every horizontal tangent, vertical tangent, straight line segment, tangent
of an inflection point and for the tangents at a slope discontinuity.
Utilizing the character shown in FIG. 4a, the frame is formed by
connecting the horizontal tangents, 71, vertical tangents 72, tangents of
inflection points 73, straight line segments of the character 74 and
tangents at the slope discontinuities 75.
Preferably, the process depicted in FIG. 4b is used to construct the frame
of a character. At block 76, a polygon is constructed by connecting the
control points of the character in the sequence they are ordered
(according to the direction of the frame). At block 80, each control point
is then assigned the property retained ("i") or non-retained ("n").
Initially, the control points which correspond to the end points of the
arc are retained and the remaining points are identified as non-retained.
The retained points are those points which will be subsequently identified
as the frame points.
The polygon is then simplified into a lower order polygon by eliminating
those control points which are not necessary to maintaining the
fundamental visual properties of the character. In a sequence of polygon
sides <r-n-n-r> (typically representative of a Bezier arc) the central
side is deleted, that is the side between the two non-retained points and
the surrounding sides are extended until they intersect one another. The
new point which occurs at the intersection of the two sides is labeled
non-retained. At block 87, in a series of aligned points, all points but
the two extreme points are eliminated. If the sequence contained two or
more retained points or if one of its points is an inflection, the
remaining points, the two extreme points, are labeled retained. At block
90, for a sequence of points <r-n-n . . . n-r>, all sides lying between
consecutive <n> points are eliminated and the sides at the ends of the
sequence bounded by <r-n> and <n-r> points are extended towards one
another until they insect. The point of intersection is labeled retained.
The points remaining after the completion of the above process are the
frame points which form the frame of the character. FIG. 5 shows the
letter "e" identified by its control points. FIG. 6 shows the frame for
the character It is evident that although the character is simplified
somewhat, e.g. the edges are squared and the character is drawn as
straight line segments, the important visual characteristics are
maintained. Particularly, the relative thickness of certain points of the
character with respect to other sections of the character, the height and
width of the character as well as the relative angles of various sections
of the character are important visual features which are preserved.
The frame provides a simplified representation of the character to perform
the subsequent analysis and adjustment operations on. Once the frame has
been adjusted, the adjusted values of the control points of the character,
which were eliminated when forming the frame, may be computed from the
known geometric relationships between the original values of the frame and
the control points.
For example, FIG. 7 illustrates the three situations during the above
described process for forming the frame in which control points are
eliminated. FIG. 7a illustrates a polygon representation of a Bezier arc.
The three segment arc is identified by points U-M-N-V. Control point U and
control point V are the end points of the arc. During the process of
forming the frame, control points M and N were eliminated and the line
segments represented by control points U-M and V-N were extended until
they intersected one another at point O thereby simplifying the polygon to
two segments, U-O and O-V. Using linear transformations, the adjusted
value of control point M may be calculated using the following equation:
##EQU2##
Where M' is the adjusted value of M, O' is the adjusted value of O and
U'is the adjusted value of U.
N is similarly adjusted using the equation:
##EQU3##
Where N' is the adjusted value of N, V' is the adjusted value of V and O'
is the adjusted value of O.
Similarly, FIG. 7b illustrates a series of aligned control points U-M-V
wherein control point M was eliminated during the process of forming the
frame. The adjusted value of M may be computed according to the following
equation:
##EQU4## | | |
