Method for displaying bitmap derived text at a display having limited pixel-to-pixel spacing resolution

Claims

We claim:

1. A method for generating typeset characterized text, at a platform display exhibiting limited display pixel-to-display pixel spacing resolution, said text having a predetermined font of characters of select character pixel defined font type and font size, and said text being conveyed from a server to client software at said platform, comprising the steps of:

I. providing an image font file as a compressed bit map representation of each of said characters of said font, derived as a compressed character image template corresponding with a font size representing an expansion factor, F, based scaling of said predetermined font select size;

II. providing a device independent typesetting specification file for said text and said predetermined font of characters such typesetting specification representing the ideal location of each character of said text at a display;

III. conveying said image font file and said typesetting specification file to said client software; and

IV. at said platform:

(a) determining any positional error from said typesetting specification file and said display pixel-to-display pixel spacing resolution said positional error being derived with respect to said ideal location for each character of said text when located at the nearest display pixel available at said display,

(b) determining for a text character whether said error is greater than a predetermined portion of said pixel-to-pixel spacing,

(c) accessing said image font file for said compressed character image template corresponding with said text character,

(d) shifting said compressed character image template in a predetermined direction an amount representing at least one character image template pixel when said determination (b) is that said error is greater than said predetermined portion of said spacing,

(e) filtering and scaling said compressed character image template to derive an anti-aliased display character of said select font size,

(f) displaying said display character at said platform display, and

(g) reiterating steps (a) through (f) for characters of said text.

2. The method of claim 1 wherein said step IV(b) determines for a said text character whether said error is greater than 1/F of said pixel-to-pixel spacing.

3. The method of claim 1 wherein:

said step IV(e) filtering is carried out by evaluating pixel representative predetermined lengths of pixel defined sequences of said character image template; and

said scaling is carried out by horizontally and vertically incrementing said sequences a number of pixel spaces, said number being based upon a selected sizing factor.

4. The method of claim 3 in which said sizing factor is selected as F.

5. The method of claim 1 in which step IV(e) thereof includes the step of decompressing said compressed character image template to an extent determining the image edge transitions contained therein.

6. The method of claim 5 in which said step of decompressing a said compressed character image is carried out by producing a list of alternating representative white and black run-lengths of pixel positions.

7. A method for generating typeset characterized text, at a platform display exhibiting limited display pixel-to display pixel spacing resolution, said text having a predetermined font of characters of select character pixel defined font type and font size, said text being conveyed from a server to client software at said platform, comprising the steps of:

I. providing an image font file as a compressed bitmap representation of each of said characters of said font, derived as a compressed character image template corresponding with a font size representing an expansion factor, F, based scaling of said predetermined font select size, said step I comprising the steps of:

(a) creating a portable bitmap file for said predetermined font of characters at F times said predetermined font select size,

(b) creating a Group 4 fax encoded TIFF file corresponding with said portable bitmap file, thereby forming a compressed image template for each character of said predetermined font of characters,

(c) dividing said TIFF file into strips with one of said strips for each compressed image template corresponding with each character of said predetermined font of characters, and

(d) creating said image font file from said portable bitmap file and said divided TIFF file strips,

II. providing a device independent typesetting specification file for said text and said predetermined font of characters such typesetting specification representing the ideal location of each character of said text at a display;

III. conveying said image font file and said typesetting specification file to said client software; and

IV. at said platform:

(a) determining any positional error from said typesetting specification file and said limited display pixel-to-display pixel matrix resolution, said positional error being derived with respect to said ideal location for each character of said text when located at the nearest display pixel available at said display,

(b) determining for a text character whether said error is greater than a predetermined portion of said display pixel-to-display pixel spacing,

(c) accessing said image font file for said compressed character image template corresponding with said text character,

(d) shifting said compressed character image template in a predetermined direction an amount representing at least one character pixel when said determination (b) is that said error is greater than said predetermined portion of said spacing,

(e) filtering and scaling said character image template to derive an anti-aliased display character of said select font size,

(f) displaying said display character at said platform display, and

(g) reiterating steps (a) through (f) for characters of said text.

8. The method of claim 7 in which step I(a) thereof for creating a portable bitmap file comprises the steps of:

selecting a said predetermined font expanded in size at F times said font select size and representing an expanded font;

creating an empty bitmap file with a pixel-based width greater than the maximum width of the characters of said expanded font and having a height greater than 256 times the height of a said character of said expanded font;

rendering each of said characters of said expanded font as character cells within said empty bitmap; and

writing the pixel based width, height, acscent and descent of said character cells, the width and height of said bitmap and the raw binary image data representing said character cells to an output file.

9. The method of claim 7 in which:

step I(a) thereof for creating a portable bitmap comprises the steps of:

selecting a said predetermined font expanded in size at F times said font select size and representing an expanded font;

creating an empty bitmap file with a pixel-based width greater than the maximum width of the characters of said expanded font and having a height greater than 256 times the height of a said character of said expanded font;

rendering each of said characters of said expanded font as character cells within said empty bitmap; and

writing the pixel based width, height, acscent and descent of said character cells, the width and height of said bitmap and the raw binary image data representing said character cells to an output file;

step I(b) thereof for creating a Group 4 fax encoded TIFF file comprises the steps of:

extracting said character cell width and height;

trimming the said pixel-based width of said bitmap file to equal said extracted character cell width; and

creating a Group 4 fax encoded TIFF file from the trimmed bitmap file with compressed character image template data representing said character cells.

10. The method of claim 7 in which:

step I(a) thereof for creating a portable bitmap file comprises the steps of:

selecting a said predetermined font expanded in size at F times said font select size and representing an expanded font;

creating an empty bitmap file with a pixel-based width greater than the maximum width of the characters of said expanded font and having a height greater than 256 times the height of said character of said expanded font;

rendering each of said characters of said expanded font as character cells within said empty bitmap; and

writing the pixel based width, height, acscent and descent of said character cells, the width and height of said bitmap and the raw binary image data representing said character cells to an output file;

step I(b) thereof for creating a Group 4 fax encoded TIFF file comprises the steps of:

extracting said character cell width and height;

trimming the said pixel-based width of said bitmap file to equal said extracted character cell width; and

creating a Group 4 fax encoded TIFF file from the trimmed bitmap file with compressed character image template data representing said character cells;

step I(c) thereof for dividing said TIFF file into strips comprises the steps of:

for said character cells of said TIFF file, copying said compressed character image template data corresponding with a said character into buffer as a strip;

writing a TIFF header for said strip;

retaining only that compressed character image template data which is unique; and

writing TIFF tags to derive a new multi-stripped TIFF file.

11. The method of claim 7 in which:

step I(a) thereof for creating a portable bitmap file comprises the steps of:

selecting a said predetermined font expanded in size at F times said font select size and representing an expanded font;

creating an empty bitmap file with a pixel-based width greater than the maximum width of the characters of said expanded font and having a height greater than 256 times the height of a said character of said expanded font;

rendering each of said characters of said expanded font as character cells within said empty bitmap; and

writing the pixel based width, height, acscent and descent of said character cells, the width and height of said bitmap and the raw binary image data representing said character cells to an output file;

step I(b) thereof for creating a Group 4 fax encoded TIFF file comprises the steps of:

extracting said character cell width and height;

trimming the said pixel-based width of said bitmap file to equal said extracted character cell width; and

creating a Group 4 fax encoded TIFF file from the trimmed bitmap file with compressed character image template data representing said character cells;

step I(c) thereof for dividing said TIFF file into strips comprises the steps of:

for said character cells of said TIFF file, copying said compressed character image template data corresponding with a said character into buffer as a strip;

writing a TIFF header for said strip;

retaining only that compressed character image template data which is unique; and

writing TIFF tags to derive a new multi-stripped TIFF file;

step I(d) thereof for creating said image font file comprises the steps of:

extracting said width, height, ascent and descent data of said character cells derived in said step I(a);

writing out identification bytes for said image font file;

writing out the size of the header of said image font file;

writing out said extracted width, height, ascent and descent data into said image font file header; and

copying the contents of said multi-stripped TIFF file to said image font file.

12. A method for generating typeset characterized text, at a platform display exhibiting limited pixel-to-pixel spacing resolution, said text having a predetermined font of characters of selected pixel defined font type and font size, and said text being conveyed from a server to a client software at said platform, comprising the steps of:

I. providing an image font file as a compressed bitmap representation of each of said characters of said font, derived as a compressed character image template corresponding with a font size representing an expansion factor, F, based scaling of said predetermined font select size;

II. providing a device independent typesetting specification file for said text and said predetermined font of characters representing the ideal location of each character of said text at a display;

III. conveying said image font file and said typesetting specification file to said client software; and

IV. at said platform:

(a) determining any positional error from said typesetting specification file and said given pixel matrix resolution, said positional error with respect to said ideal location for a character of said text when located at the nearest pixel available at said display,

(b) determining for said character of said text whether said error is greater than a predetermined portion of said pixel-to-pixel spacing resolution,

(c) when said error is determined to be greater than said predetermined portion of said pixel-to-pixel spacing resolution, then determining whether an anti-aliased display character has been generated in accordance with step (g) hereof and cached in temporary memory and, in the event that it has been so cached, then going to step (i) hereof,

(d) when said display character has not been cached, accessing said image font file for said compressed character image template corresponding with said character of said text,

(e) decompressing said accessed compressed character image template to an extent identifying character image transitions from relative black and white runs of pixels,

(f) when said error is determined to be greater than said predetermined portion of said pixel-to-pixel spacing, carrying out an effective shifting of a predetermiend number of pixel positions in a predetermined horizontal direction at said decompressed character image template, to derive a shifted character image template,

(g) then filtering and scaling said shifted character image template to produce an anti-aliased display character of said select font size,

(h) caching said anti-aliased display character in temporary memory,

(i) displaying said display character at said platform display, and

(j) reiterating steps (a) through (i) for characters of said text.

13. The method of claim 12 in which said step (e) of decompressing said accessed compressed character image template is carried out by decoding each row position of said template to produce a list of alternating relative white and black pixel run lengths.

14. A method for generating typeset characterized text, at a platform display exhibiting limited display pixel-to-display pixel spacing resolution, said text having a predetermined font of characters of selected character pixel defined font type and font size, and said text being conveyed from a server to a client software at said platform, comprising the steps of:

I. providing an image font file as a compressed bitmap representation of each of said characters of said font, derived as a compressed character image template corresponding with a font size representing an expansion factor, F, based scaling of said predetermined font select size;

II. providing a device independent typesetting specification file for said text and said predetermined font of characters representing the ideal location of each character of said text at a display;

III. conveying said image font file and said typesetting specification file to said client software; and

IV. at said platform:

(a) determining from said typesetting specification file and said display pixel-to-display pixel spacing resolution the positional error with respect to said ideal location for a character of said text when located at the nearest pixel available at said display,

(b) determining for said character of said text whether said error is greater than a predetermined portion of said display pixel-to-display pixel spacing resolution, said predetermined portion being 2/F,

(c) when said error is determined to be greater than said predetermined portion of said pixel-to-pixel spacing resolution, then determining whether an anti-aliased display character has been generated in accordance with step (g) hereof and cached in temporary memory and, in the event that it has been so cached, then going to step (i) hereof,

(d) when said display character has not been cached, accessing said image font file for said compressed character image template corresponding with said character of said text,

(e) decompressing said accessed compressed character image template to an extent identifying character image transitions from relative black and white runs of pixels,

(f) when said error is determined to be greater than said predetermined portion of said pixel-to-pixel spacing, carrying out an effective shifting of at least two character pixel positions in a predetermined horizontal direction at said decompressed character image template, to derive a shifted character image template,

(g) then filtering and scaling said shifted character image template to produce an anti-aliased display character of said select font size,

(h) caching said anti-aliased display character in temporary memory,

(i) displaying said display character at said platform display, and

(j) reiterating steps (a) through (i) for characters of said text.

15. The method of claim 14 in which:

said step IV(b) includes a step of determining whether said error is greater than 1/F of said pixel-to-pixel spacing resolution when said error is not greater than 2/F; and

said step IV(f) predetermined number of character pixel positions is at least one when said error is greater than 1/F but not greater than 2/F of said display pixel-to-display pixel spacing resolution.

16. The method of claim 15 in which said step IV(f) predetermined number of character pixel positions is zero when the determination of step IV(b) is that said error is less than 1/F of said display pixel-to-display pixel spacing resolution.

17. A method for generating typeset characterized text, at a platform display exhibiting limited display pixel-to-display pixel spacing resolution, said text having a predetermined font of characters of selected character pixel defined font type and font size, and said text being conveyed from a server to a client software at said platform, comprising the steps of:

I. providing an image font file as a compressed bitmap representation of each of said characters of said font, derived as a compressed character image template corresponding with a font size representing an expansion factor, F, based scaling of said predetermined font select size;

II. providing a device independent typesetting specification file for said text and said predetermined font of characters representing the ideal location of each character of said text at a display;

III. conveying said image font file and said typesetting specification file to said client software; and

IV. at said platform:

(a) determining from said typesetting specification file and said given pixel matrix resolution the positional error with respect to said ideal location for a character of said text when located at the nearest pixel available at said display,

(b) determining for said character of said text whether said error is greater than a predetermined portion of said pixel-to-pixel spacing resolution,

(c) when said error is determined to be greater than said predetermined portion of said pixel-to-pixel spacing resolution, then determining whether an anti-aliased display character has been generated in accordance with step (g) hereof and cached in temporary memory and, in the event that it has been so cached, then going to step (i) hereof,

(d) when said display character has not been cached, accessing said image font file for said compressed character image template corresponding with said character of said text,

(e) decompressing said accessed compressed character image template to an extent identifying character image transitions from relative black and white runs of pixels,

(f) when said error is determined to be greater than said predetermined portion of said pixel-to-pixel spacing, carrying out an effective shifting of a predetermined number of pixel positions in a predetermined horizontal direction at said decompressed character image template, to derive a shifted character image template,

(g) then filtering and scaling said shifted character image template to produce an anti-aliased display character of said select font size,

(h) caching said anti-aliased display character in temporary memory,

(i) displaying said display character at said platform display, and

(j) reiterating steps (a) through (i) for characters of said text, said step (g) comprising the steps of:

(g1) examining a sequence of x pixel positions in an initial row of pixel positions of said character image template with a virtual filter of x successive horizontal pixel positions and y pixel rows, each such position having a select weighting factor,

(g2) deriving an intermediate output value representing the sum of the product of each said weighting factor with an associated pixel position,

(g3) horizontally shifting said virtual filter along said row a number of pixel horizontal positions corresponding with a select scaling factor, S, and deriving a next said intermediate output value,

(g4) reiterating said step (g3) until all pixel horizontal positions along said row have been examined,

(g5) reiterating said step (g4) to derive said intermediate values at each row for said y pixel rows, and summing said intermediate values for a said virtual filter x, y orientation of x horizontal pixel position and y rows, and

(g6) deriving a gray scale value for a pixel represented by said virtual filter x, y orientation summed intermediate values.

18. The method of claim 17 including the steps of:

(g7) vertically shifting said virtual filter a number of rows corresponding with said select scaling factor, S;

(g8) then reiterating said steps (g5) and (g6) for the entire said character image template and deriving a scaled gray scale bitmap representing said display character.

19. The method of claim 18 in which:

said expansion factor, F, has a value of 3;

said virtual filter x succession of horizontal pixel positions is 4 positions and said y pixel rows are 4 rows; and

said scaling factor, s, has a value of 3.

20. The method of claim 19 in which:

said step (g1) select weighting factor for each pixel of said virtual filter x succession of horizontal pixel positions respectively is: 1,2,2,1; and

said select weighting factors for successive rows of said virtual filter x, y orientation of four y pixel rows are multiplied by the respective values: 1,2,2,1 subsequent to said step (g1) and prior to said step (g2).

21. The method of claim 19 in which said step (g7) includes the step of discarding the intermediate output values derived from the first three rows of the next previous four y pixel rows.

BACKGROUND

A communications system designed in the 1960s as part of preparation for surviving nuclear war evolved globally into what is now referred to as the "Internet". In effect, the Internet is a multitude of networks which interconnect to transfer information but without the supervision of an oversight organization. In 1989, a physicist at the European Particle Physics Laboratory known as CERN proposed a worldwide web (WWW), a set of protocols layered upon the Internet which utilize hypertext, a technique for presenting and relating information which uses links rather than linear sequences. The Web was demonstrated in 1991 and expanded rapidly with hypermedia and multimedia software. Developed in concert with the Web were a series of software interface programs structured to aid in navigating the Web which are called "browsers". In this regard, a team of programmers at the National Center for Supercomputing Applications (NCSA) developed a non-proprietary graphical interface browser for the Web which was released in 1993 under the name "Mosaic". Within six months of that release, more than two million people downloaded Mosaic from the NCSA host computer in Champaigne, Ill. The Mosaic browser is a cross-platform application, such that it is able to run in various different computing environments, i.e. PC-Windows, Macintosh, Amiga, and Unix-based systems. In the internet, for example, the Mosaic browser is deemed a "client"--an applications program running on a desktop computer and sending out requests for information typically to remotely located computer programs referred to as "servers". Within the Web, the client is responsible for displaying the information it receives from the server, and the server is responsible for performing the computation needed to retrieve the information the client is going to display, controlling access to that information, and recording usage statistics. The NCSA's Mosaic interface is a common one in use and when employed as an electronic publishing vehicle, its native HyperText Transfer Protocol (HTTP) (CERN, 1994a) is the protocol for communication with servers. Information itself is transmitted in HyperText Mark-up Language (HTML) which, in turn, is an application of the international (ISO, 1986) Standard Generalized Mark-up Language (SGML). Information transmitted in HTML is interpreted and displayed by the client as text and graphics on the user's screen or printer. See generally: Hickey, "Present and Future Capabilities of the Online Journal" LIBRARY TRENDS, vol. 43, No. 4, Spring, 1995, pp 528-543.

Several browsers are now available, for example Netscape Navigator has become widely used. More recently, a Web browser termed "Hot Java" has been developed by Sun Microsystems, Inc. using a language also developed by the Sun organization called "Java" which allow additional capabilities found desirable by database operators and developers seeking to serve internet clients. For example, code can be downloaded dynamically from the server to the user or client at the desktop level.

While the Web browsers have multi-platform capabilities, they have been constrained to use the text or character forming facilities of the individual platforms. Thus, there has been essentially no control available to the server for the final structuring of text and, particularly, the facilities from one platform to another are varied such that they do not have a commonality in techniques for painting characters upon a screen. This becomes a hindrance where scholarly text becomes the subject of Web distribution. For example, technical journals typically will incorporate glyphs or characters associated with mathematical equations and the like, for which platform-based character formations will have no counterparts. To overcome these difficulties, bit-map defined characters may be employed, preferably along with device independent typesetting specification files (DVI) which call for a particular character and font, and exactly define where the character should be positioned, for example, to the extent of 1/64,000th of a point (a point is 1/72nd of an inch). Such device independent files are described in U.S. Pat. No. 4,803,643, entitled "System and Method for Creating Memory-Retained, Formatted Pages of Text, Tabulation, and Graphic Data" by Hickey, issued Feb. 7, 1989. With such DVI systems, information can be transmitted to the client as to the proper position of the character at hand, its definition, and the like. However, because of the variety of facilities exhibited by various platforms to which the server transmits, the raster defined pixel matrixes by which characters are fashioned will vary and be unable to accommodate the precise DVI character positioning information. Typically, a given character is horizontally "relocated" to the closest available pixel on the screen or raster. In effect, a spatial character shift then becomes observable at a display with resultant text-character renditions which are disconcerting to the user. For example, characters of a given word may be bunched together or spread apart beyond their proper spacing definition. Particularly when viewed upon a dynamic screen or display, such spatial vagaries are quite disquieting. Generally, pixels in a display matrix are spaced apart between about 1/70th and 1/100th inch. While a displacement of that amount or only one half of that amount seems dismissable it will be very visible and distracting to the reader.

An approach in the field of computer graphics for improving image qualities, particularly with respect to "staircasing" or "jaggies" has been through resort to antialiasing which may employ any of a variety of sampling techniques to develop gray-scale variations in the definition of images. In effect, the human eye-neural system synthesizes the resultant gray-scale image and mentally interprets it as an improved sharper image. Such approaches to character display improvement were undertaken by investigators at about the time of the introduction of the personal computer. See, for example:

1. Negroponte, N., SoftFonts. Proceeding, Society for Information Display, 1980

2. Schmandt, C., Fuzzy Forms: Analog Models Inprove Digital Text Quality, Conference of Exhibition of the National Computer Graphics Association (4th, 1983)

3. Schmandt, C. Soft Typography, Information Processing '80. Proceedings of IFIPS, pp.1027-1032

4. Wilkes, A. J. and Wiseman, N. E., A Soft-edged Character Set and Its Derivation, The Computer Journal, vol. 25, No. 1, pp 140-145 (1982)

Anti-aliased image generation also is undertaken with varying hues or colors. See in this regard:

5. Schmandt, C., Greyscale Fonts Designedfrom Video Signal Analysis, Architecture Machine Group, Massachusetts Institute of Technology

6. Gupta, S., Bantz, D., Sholtz, P., Evangelisti., C., and DeOrazio, W., YODA: An Advanced Display for Personal Computers, IBM J. Res. Develop., vol. 31, No. 1, pp 44-57 (Jan. 1987)

While the anti-aliasing approach to character generation has served the purpose of presenting relatively higher quality characters on limited resolution displays, the need to achieve a form of sub-pixel positioning on a practical basis has persisted. In effect, the high resolution typesetting specifications do not translate into integer values at low resolution. Thus, the noted character positioning aberrations. Investigators have addressed this anomaly by looking to an approach carrying out a sub-pixel shifting utilizing a gray scale filtering process. See in this regard:

7. Warnock, J. E., The Display of Characters Using Gray Level Sample Arrays, Comput. Graph. 14, No. 3, 302-307 (July 1980)

8. Computer Graphics, Principles and Practice, 2d Ed., pp 976-979, Addison-Wesley Co., Inc. (1990)

Filter derived sub-pixel positions or locations, sometimes called "phases", however, pose the problem of requiring immense amounts of storage and computational constraints which have remained unsolved. As the Internet system expands, however, an increasing demand follows for the an improved accessing and display of scholarly works. A technique for the practical generation of such materials at lower level resolution displays has heretofore proved to be an elusive goal.

SUMMARY

The present invention is addressed to a method for generating bitmap-described text in conjunction with typeset specifications at displays exhibiting limited pixel-to-pixel resolution. While display character positioning is developed