% --- ------------------------------------------------------------------ % --- Halftone Output from TeX. % --- ------------------------------------------------------------------ % --- This file should be formatted by LaTeX and printed with an half an % --- inch of top and an inch of left margin. The page layout should be % --- compatible with TUGboat. % --- ------------------------------------------------------------------ % --- Macros and mnemonics. % --- ------------------------------------------------------------------ \def\|#1|{{\tt#1}} % teletype text \def\cmd#1{{\tt\char92#1}} % for `\command' \def\fig#1{Fig.~#1} % references to figures \def\mc{\small} % medium caps \def\ASCII{{\mc ASCII}} \def\bigTeX{{big \large\TeX}} \def\FTN{{\mc FORTRAN}} \def\VAX{\leavevmode\hbox{V\kern-.12em A\kern-.1em X}} \def\VMS{\leavevmode\hbox{V\kern-.06em MS}} % --- ------------------------------------------------------------------ % --- Document style. % --- ------------------------------------------------------------------ \nofiles \font\halftone=halftone % the halftone font \documentstyle[tugboat]{article} % --- ------------------------------------------------------------------ % --- The title. % --- ------------------------------------------------------------------ \title{Halftone Output from \TeX} \author{Adrian F. Clark} % --- ------------------------------------------------------------------ % --- The article itself. % --- ------------------------------------------------------------------ \begin{document} \maketitle \noindent Don Knuth's article in \TUB\ volume~8 number~2 described the development of a number of fonts which allow halftone output---pictures---to be incorporated into \TeX\ documents. This article chronicles the author's experiments into halftone production on a particular computer/laser printer combination, \VAX/\VMS\ and the LN03. It is important to understand that the picture is actually {\em typeset,\/} not just inserted into the final output by some printer-specific \cmd{special} command; the following results can, in principle, be achieved on {\em any\/} output device using a perfectly normal implementation of \TeX. In the image processing field, where the author works, technical reports are invariably crammed with halftone output. The conventional method of reproducing pictures is photographically. This is slow and expensive, particularly for internal reports with small distributions. Moreover, unless great care is taken over the photographs---using a flat-screen {\mc CRT}, calibrating films, standardising the processing, and so on---much of the visual impact can be lost. Hence, the possibility of incorporating imagery into \TeX\ document without recourse to a dark room is very attractive. A great deal of work has been carried out into the properties of the human eye. One result is that the eye is only really capable of distinguishing about 64~grey levels, although it is very good at detecting boundaries between regions of slightly differing grey level (see, for example, {\sl ``Digital Image Processing''\/} by R.~C.~Gonzalez and P.~Wintz, published by Addison-Wesley in 1977). Another result is that the eye is much more sensitive to boundaries in dark regions than in light regions. The halftone font used here is more or less the same as the `double-dot' font described by Knuth. It has some 65~different grey levels, represented by the \ASCII\ characters `{\tt 0}' (white) to `{\tt p}' (black). In principle, all one needs to do is to convert the grey levels of the individual pixels (``picture elements'') of an image to the appropriate characters of the halftone font and sprinkle in a few \TeX\ commands to ensure that the lines of the image are lined up in the output. The only minor complication is that this sequence of characters includes `\verb"\"', `\verb"^"' and `\verb"_"', which have special meanings to \TeX. These must be treated specially. Knuth's approach was to delimit the picture data between macros, \cmd{beginhalftone} and \cmd{endhalftone} which disable the special characters in a similar way to the `verbatim' macros in Appendix~E of {\sl ``The \TeX book''.\/} The approach developed by the author is much less elegant and builds larger disc files, but does not require special-purpose macros. Each line of the image is built up as a single \cmd{hbox}. These lines are stacked into a \cmd{vbox}, with the inter-line skip turned off. Finally, the \cmd{vbox} is enclosed in another \cmd{hbox}, which makes it easier to handle the picture in constructs such as \cmd{centerline}. The scheme can be summarised as: \begin{verbatim} \hbox{ \vbox{ \halftone \offinterlineskip \hbox{...} ... \hbox{...} }} \end{verbatim} \noindent The \cmd{halftone} command is used to select the halftone font, which would be loaded with a command such as \begin{verbatim} \font\halftone=hf300 \end{verbatim} \noindent assuming the {\mc TFM} file is called {\tt HF300.TFM}. A \FTN\ \|SUBROUTINE|, \|TEXPIC|, was written to output images to files in this format. The image is represented as a \|REAL| array dimensioned as \|(M,N)|, where \|M| is the number of pixels per line and \|N| the number of lines. (The use of a \|REAL| array to hold data which are usually 8-bit may seem a little strange, but this representation has many advantages---for example, when Fourier transforming an image.) Since we would normally like our pictures to have the best contrast, \|TEXPIC| scans through the image to find its minimum and maximum, then scales the output to make full use of the grey levels in the halftone font. For most purposes, a single \begin{verbatim} CALL TEXPIC( PIC, M, N, FN ) \end{verbatim} \noindent is sufficient. (\|FN| is a \|CHARACTER| variable or quoted string holding the output filename.) Of course, there are occasions when we would like to compare pictures, so fixing the contrast is sometimes desirable; hence, \|TEXPIC| has associated routines to fix the range of intensities (\|ZRANGE|) and re-select automatic intensity scaling (\|ZAUTO|), which must be invoked before \|TEXPIC| to have an effect. Similarly, \|TEXPIC| can plot negative pictures as well as positive ones: \|DONEG| tells it to output subsequent pictures as negatives and \|DOPOS| returns it to the default state. Inserting the picture into a document prepared with plain \TeX\ is quite simple, using commands to generate a `float', such as \begin{verbatim} \midinsert \centerline{\input picture} \endinsert \end{verbatim} \noindent assuming the picture is in the file {\tt PICTURE.TEX}. This command sequence should be typed between paragraphs, when \TeX\ is in `vertical mode'. To draw a border around the picture, as for the examples presented here, one would define a macro \cmd{border} \begin{verbatim} \def\border#1{\vbox{\hrule\hbox{ \vrule\kern3pt\vbox{\kern3pt#1 \kern3pt}\kern3pt\vrule}\hrule}} \end{verbatim} \noindent The picture would then be set with \begin{verbatim} \centerline{\border{\input picture}} \end{verbatim} The procedure with \LaTeX\ is somewhat different. The most sensible approach is to use the {\tt figure} environment ({\em not\/} the {\tt picture} environment) \begin{verbatim} \begin{figure} \centering \mbox{\input picture\relax} \caption{...} \end{figure} \end{verbatim} \noindent This generates a `floating' figure, which usually surfaces at the top of the next page of output. The \cmd{relax} following the filename in the \cmd{mbox} command ensures that \LaTeX\ knows where the filename ends. To draw a border around the picture, replace the \cmd{mbox} with a \cmd{fbox}. It is traditional to test out new image processing techniques on the `girl' picture from the image database of the University of Southern California's Signal and Image Processing Institute. She is shown in \fig{1} ($64 \times 64$ pixels). The output was plotted on a standard {\tt LN03} laser printer using version~10 of Flavio Rose's {\tt DVI2LN3}. For those unfamiliar with the {\tt LN03}, it is a 300~dpi, white-writing laser printer based a Ricoh mechanism, supporting the down-loading of fonts into on-board and plug-in RAM cartridges. The quality of the picture does not appear to be particularly good, but this is due to the comparatively low spatial resolution of the image data: $256 \times 256$ pixels are needed to give a visually satisfying result---as we shall see. \begin{figure} \centering \fbox{\input picture\relax} \caption{The Ubiquitous `Girl' Image} \end{figure} Unfortunately, the standard \|LN03| will not output images much greater than 64~pixels wide: if one tries to do so, it generates ``band too complex'' errors and produced broad white bands in the output. The actual cause of this is not known; however, it seems to be because the \|LN03| buffers the plotting commands internally rather than writing dark pixels into a bitmap. When the print operation actually starts, the driving microprocessor cannot translate the commands sufficiently quickly. However, the \|LN03+| device (a field-installable hardware and firmware upgrade) has a full-page bitmap, and is quite capable of printing off large pictures. (However, a little care is needed in setting up the terminal line to which the printer is attached.) The is another problem in producing these large pictures, and it concerns \TeX\ itself. Since \TeX\ was designed for typesetting text rather than pictures, its memory capacity is too small. Increasing the size of the memory (i.e., \verb"mem_size") is obviously feasible, at least on \VAX en, but there is a snag: \TeX\ was written to use 16-bit integers for subscripts into the memory arrays. However, the change file mechanism of {\mc WEB} and the careful way in which \TeX\ was written, makes the conversion of 16-bit integers to 32-bit integers quite straightforward. (It is also necessary to disable some of \TeX's initial consistency checking.) When the author did this, producing a ``\bigTeX'', he found that the 16-bit and 32-bit versions of \TeX\ were identical in almost every respect. The executable file was a few percent bigger, probably due to the increased memory space rather than the different integer representation. Likewise, the string pool and format files were slightly larger. However, there is {\em no\/} perceivable impact on execution times. (In fact, the author replaced the 16-bit version with \bigTeX\ without telling users---and no-one noticed any difference!) This may seem a little surprising at first, but an examination of the (pseudo-) assembler generated by the {\mc PASCAL} compiler provides the answer. The machine code generated for variables declared as \|0..65535| (or, indeed, \|0..255|) is {\em identical\/} to that for, say \|0..262144|; 32-bit integers are used in all cases. (This does, of course, not apply to {\bf packed array}s.) \TeX\ is very frugal in the way it handles its memory arrays, always re-using the same region if possible; this keeps the page fault rate low. Since the \VAX\ initialises all memory to be `demand-zero' when a program is loaded, there is no increase in the system overhead due to unused regions of \TeX's memory. \begin{figure*} \centering \fbox{\input boat\relax} \caption{A $256 \times 256$ Lake Scene} \end{figure*} The version of \TeX\ at the author's site has a large enough memory capacity for four $256 \times 256$ pictures (or one $512 \times 512$ picture!) in addition to the usual text, fonts and macro definitions. This allows users to put a few images into floating figures, as described above, without overflowing \TeX's memory. A $256 \times 256$ picture is shown in \fig{2}. Indeed, to a certain extent, the physical size of a picture on the printed page determines the maximum number of pixels which can be plotted. Images of $512 \times 512$ pixels are more or less standard in the image processing community, while satellite images used in remote sensing applications have several thousand pixels on a side! Hence, if the image size exceeds a proscribed maximum (256~pixels, say), \|TEXPIC| must {\em interpolate} between pixels to reduce the size of an image. Another associated \|SUBROUTINE|, \|TEXMAX|, is used to tell \|TEXPIC| the maximum number of pixels which can be output. If the \|M| dimension of an image exceeds this value, the image is interpolated down to this plottable maximum number of pixels. \begin{figure*} \centering \fbox{\input mandy\relax} \caption{Mandrill Image, Reduced to $200 \times 200$ Pixels from $512 \times 512$ Pixels} \end{figure*} There are many ways to perform the interpolation. The theoretical optimum is to use a $\sin x / x$ interpolation function (usually achieved via Fourier transformation), but this is slow. Cubic or linear interpolators tend to be used in practise. Recognising that \TeX\ output of a reduced $4000 \times4000$~pixel image will inevitably be inaccurate, \|TEXPIC| uses a linear interpolation scheme. However, since linear interpolators usually blur edges (a particularly undesirable effect), it attempts to reduce the blur by using a {\em context-sensitive\/} interpolator. This interpolates between triplets of pixels at right angles and selects the value of the line with maximum gradient. For example, \fig{3} is a $200 \times 200$~pixel image, reduced from a $512 \times 512$ image in this way. All the software described here is available. \|TEXPIC| and supporting routines exist in both standard \FTN\ and \VAX\ \FTN; the \VAX\ version does clever things with filenames and channel numbers. The \bigTeX\ change file is, of course, specific to \VMS, but may be useful for people making similar enhancements on other machines. \subsection*{Enhancements to the Software} Since this article was submitted to \TUB, a few improvements have been made to \|TEXPIC|. Firstly, the code used an \|ASSIGN|ed \|GO~TO|, which is no longer a part of the \FTN\ standard. The latest version of the routine has this section of code in both the places where it is needed. The second improvement is to output the picture in a more concise format, along the lines of Don Knuth's macros in \TUB\ volume~8 number~1. The files written in this new format are fully compatible with existing \TeX\ documents. There has been no perceivable change in execution time. Another support routine has been written, too: \|ZSAME| tells \|TEXPIC| that subsequent pictures should be scaled with the same factors as the last picture. (An error message is generated if no previous picture has been plotted.) Thanks to Guy Facius of SFEBP Paris for this suggestion. \end{document}