Method and apparatus for compressing Bezier descriptions of letterforms in outline fonts using vector quantization techniques
View Patent ↗Vector quantization provides font contour data reduction. Characters are defined in a font collection using segmented outline forms and common references stored to curve segments for similar segments in different characters of the font collection. Compressing the font collection preferably includes applying an entropy encoding data reduction. The common references are stored in a segment storage location. Another aspect includes decompressing a font store containing a compressed collection of outline fonts. The uncompressed curve segments are scaled so as to match a requested size for a letterform.
1. A method for font data storage for fonts having segmented outline forms defined by contours having contour segments defined by curves represented by curve elements, the method comprising the steps of:
defining characters in a font collection having segmented outline forms defined; and
storing common references to representative curve element segments in a curve element storage location for similar curve elements composing curve segments in different characters of the font collection, wherein the storing further includes mapping the curve elements into vector representations and type identifiers by normalizing start and end points of the curve elements to a unit square and classifying the normalized curve elements using class tables, respectively, collecting the vector representations and type identifiers into data sets of vector data and type data, and applying a vector quantization process to the vector data.
2. The method according to claim 1 , wherein the common references include a vector data index and a curve type code to access the representative curve elements.
3. The method according to claim 1 , wherein the step of storing further includes the steps of:
employing an entropy analysis process to the type identifiers, wherein the vector quantized data is stored as an entry in a code book and the data resulting from entropy analysis is stored as a type codification table.
4. The method according to claim 3 , wherein the step of storing further includes the steps of:
for each vector representation, selecting a vector index referencing a code book entry having a representative vector representation; and
for each type identifier, applying an entropy encoding scheme by selecting a type code from the type codification table.
5. The method according to claim 4 , wherein the entropy analysis and encoding processes use a Huffman entropy process.
6. The method according to claim 1 further including the step of subgrouping the font collection into font groups having similar segmented outline form characteristics.
7. An apparatus for font data storage for fonts having segmented outline forms defined by contours having contour segments defined by curves represented by curve elements, the apparatus comprising:
a segmented outline font storage for storing segmented outline forms for characters in a font collection;
a representative curve element storage for storing representative curve elements; and,
a curve element reference storage having common references to the representative curve elements, including curve type codes and representative vector data, wherein the representative vector data is derived by vector quantizing vector description data for all curve elements of a same class.
8. The apparatus according to claim 7 , wherein the representative curve elements are stored in a normalized form.
9. The apparatus according to claim 7 , wherein the representative curve elements include representative vector data stored in code books.
10. The apparatus according to claim 7 , wherein:
the type codes are derived by entropy analysis of all the curve type elements of the font group.
11. The apparatus according to claim 10 , wherein the entropy encoding uses a Huffman entropy encoding scheme.
12. The apparatus according to claim 7 wherein font groups having similar segmented outline form characteristics are collected together to improve a ratio of representative curve references to actual curve elements.
13. A method for font data decompression using a font store containing a collection of fonts, the font store comprising a curve element reference storage and segmented outline forms for font characters, the method comprising the steps of:
generating the font characters by accessing the segmented outline forms of the font characters;
determining contour segments for the segmented outline of the font characters; and
accessing the curve element reference storage to obtain representative curve elements composing the contour segments;
wherein each curve element reference stored in the curve element reference storage includes at least one vector reference datum and one curve element reference datum, wherein the vector reference data refers to curve element vectors stored in a code book obtained via vector quantization, and wherein the curve element data refers to curve element types specified in a code table.
14. The method according to claim 13 , wherein the step of accessing includes the step of scaling the contour segments.
15. The method according to claim 13 , wherein the step of accessing includes:
looking up a vector stored in the code book for each vector reference datum; and
decoding a segment type stored in the code table for each segment type datum.
16. The method according to claim 15 , wherein the step of decoding includes applying a Huffman entropy decoding scheme.
17. An apparatus for font data decompression using a font store containing a collection of fonts, the font store comprising a curve element reference storage and segmented outline forms for font characters, the segmented outline forms having contour segments represented by curve elements, the apparatus comprising:
segmented outline forms defining font characters in a collection of fonts;
a curve element storage area comprising curve element data and curve element references providing links to the curve element data, wherein each curve element reference includes at least one vector reference datum and one segment datum; and
a processor routine accessing the segmented outline forms and curve element references, the processor routine retrieving the curve element data corresponding to the curve element references for reconstruction of the contour segments composing the segmented outline forms, the processor routine including a look-up routine for looking up a vector stored in a code book obtained via vector quantization for each vector reference datum.
18. The apparatus according to claim 17 , wherein the processor routine includes a transformation process comprising at least one of connecting, positioning, scaling, rotation, mirroring, skewing, and reconstructing.
19. The apparatus according to claim 17 , wherein the processor routine includes:
a decoder routine for decoding a curve element type stored in a code table for each segment type datum.
20. The apparatus according to claim 19 , wherein the decoder routine performs a Huffman entropy decoding scheme.