Image analysis – Image compression or coding – Contour or chain coding
Reexamination Certificate
2001-03-09
2003-09-02
Johnson, Timothy M. (Department: 2625)
Image analysis
Image compression or coding
Contour or chain coding
C345S442000, C345S469000, C345S469100, C345S947000, C382S199000, C382S243000
Reexamination Certificate
active
06614940
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to compression algorithms, and more particularly to compressing textual data for storage and/or transmission utilizing a network.
BACKGROUND OF THE INVENTION
It is well known that an amount of dot data which is obtained by dividing image data of a character or the like into dots is extremely large. Therefore, in order to compress such a large quantity of data and then store or transmit the compressed data, various kinds of data compressing methods have been proposed. For example, the shape of a character or the like may be detected as a contour and contour information may be stored, thereby compressing the data amount.
For example, there are known: a straight line approximating method disclosed in Japanese Patent Laid-Open Applications Nos. 149522/1979 and 79154/1980; an n-degree curve approximating method disclosed in Japanese Patent Laid-open Nos. 39963/1982, 134745/1983, and 75976/1985; and the like.
Another approach is to convert the originally-scanned quantized data into a connected set of mathematically-defined boundaries of two-dimensional regions representing the “inside” or “outside” of a character. The boundaries are comprised of “curve elements” which, in the most primitive implementations, are simple line segments.
More sophisticated systems use more complex shapes such as quadratic or cubic Bezier curves. All of these systems have the objective of storage of these mathematical shapes, and reconstruction of the digital representations of the characters through properly constructed physical mechanisms or computer instructions.
A major benefit to the mathematical description is the ability to render output characters at any size by scaling the coordinate information stored in the character data descriptions, thereby eliminating the need for storage of bitmap data at every desired point size and/or output resolution. An added benefit of a mathematical description is the ability to subdivide the original outline into as many “curve elements” as necessary and to store the data representing them at whatever precision is required for replication of an original “master” design to the degree permitted by the scanning resolution.
In summary, according to the former straight line approximating method, smoothness of the contour is not assured. On the other hand, according to the latter n-degree curve approximating method, although smoothness of a curve is ensured, it is complicated to convert the functional equations to the curve, so that it takes a long time to generate the curve. Therefore, this method has the drawback that it cannot be practically used in a high-speed display device such as CRT or laser beam printer in terms of the processing speed. While attempts at using a Bezier cubic curve have been used to overcome this drawback, such method of forming an approximation is difficult.
There is therefore a need for improved techniques for compressing bitmap fonts using mathematical approximations.
DISCLOSURE OF THE INVENTION
A system, method and computer program product are provided for compression of characters. Upon receipt of a plurality of characters, at least one test is performed on the characters to determine if an outline of the characters is capable of being approximated by a mathematical approximation. If the outline of the characters is capable of being approximated, the characters are approximated using the mathematical approximation.
In one embodiment of the present invention, a search may be conducted for curved splines associated with the characters. Thereafter, the test may be performed on the uncovered curved splines. More particularly, the searching may be conducted for curved splines that connect smoothly.
In another embodiment of the present invention, one of the curved splines may be removed if the outline of the characters is not capable of being approximated. As such, the at least one test may be performed again to determine if the on outline of the characters is now capable of being approximated.
In one aspect of the present invention, the mathematical approximation may be selected from the group consisting of cubic splines, elliptical arcs, and hyperbolic arcs. In an embodiment where the mathematical approximation includes an elliptical arc, such elliptical arc may be approximated by position information and rotational information relating to the rotational orientation of the elliptical arc.
In the present embodiment where the mathematical approximation includes an elliptical arc, the rotational information may include a plurality of points on the elliptical arc, three or more dimensionless parameters, and a bit of information. Such three or more dimensionless parameters may be determined by defining a center of a circle associated with the elliptical arc, applying a first linear transformation to stretch the circle, and applying a second linear transformation that includes a shear parameter.
As an option, constraints may be imposed on the three or more dimensionless parameters to expedite the generation thereof. Further, the constraints may include a rule that the elliptical arc has a same maximum lateral extent from a line defined by a pair of on-curve points on the character.
In still another embodiment of the present invention, the mathematical approximation may include a cubic spline approximated by a plurality of control points that are determined by an equation including two variables. Such control points may be determined by the two-variable equation by imposing constraints on slopes associated with lines on which the control points reside. As an option, constraints may be imposed on the manner in which the mathematical approximations are joined together.
In still yet another embodiment of the present invention, a compressed file may be generated utilizing the mathematical approximation. Optionally, such process may be tunable. Further, a number of bits used to store position coordinates and curve approximation parameters may be approximated. Also, the step of creating the compressed file may involve XY sequences.
REFERENCES:
patent: 4907282 (1990-03-01), Daly et al.
patent: 4949281 (1990-08-01), Hillenbrand et al.
patent: 5131058 (1992-07-01), Ting et al.
patent: 5363107 (1994-11-01), Gertz et al.
patent: 5408598 (1995-04-01), Pryor, Jr.
patent: 5452371 (1995-09-01), Bozinovic et al.
patent: 5623555 (1997-04-01), Nelson et al.
patent: 5774639 (1998-06-01), Schildkraut et al.
Azam Syed Aamer
Reinsch Matthias W.
Johnson Timothy M.
Morisawa & Co., Ltd.
Silicon Valley IP Group
Zilka Kevin J.
LandOfFree
System, method and computer program product for generic... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, method and computer program product for generic..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method and computer program product for generic... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3102939