leptonica

This is a source for a clean, fast implementation of rasterops.
You can find details starting at the Leptonica home page,
and also by looking directly at the source code.
Some of the low-level code is in roplow.c, and an interface is
given in rop.c to the simple Pix image data structure.

2. Binary morphology

   This is a source for efficient implementations of binary morphology
   Details are found starting at the Leptonica home page, and by reading
   the source code.

   Binary morphology is implemented two ways:

   (a) Successive full image rasterops for arbitrary
   structuring elements (Sels)

   (b) Destination word accumulation (dwa) for specific Sels.
   This code is automatically generated. See, for example,
   the code in fmorphgen.1.c and fmorphgenlow.1.c.
   These files were generated by running the program
   prog/fmorphautogen.c. Results can be checked by comparing dwa
   and full image rasterops; e.g., prog/fmorphauto_reg.c.

   Method (b) is considerably faster than (a), which is the
   reason we’ve gone to the effort of supporting the use
   of this method for all Sels. We also support two different
   boundary conditions for erosion.

   Similarly, dwa code for the general hit-miss transform can
   be auto-generated from an array of hit-miss Sels.
   When prog/fhmtautogen.c is compiled and run, it generates
   the dwa C code in fhmtgen.1.c and fhmtgenlow.1.c. These
   files can then be compiled into the libraries or into other programs.
   Results can be checked by comparing dwa and rasterop results;
   e.g., prog/fhmtauto_reg.c

   Several functions with simple parsers are provided to execute a
   sequence of morphological operations (plus binary rank reduction
   and replicative expansion). See morphseq.c.

   The structuring element is represented by a simple Sel data structure
   defined in morph.h. We provide (at least) seven ways to generate
   Sels in sel1.c, and several simple methods to generate hit-miss
   Sels for pattern finding in selgen.c.

   In use, the most common morphological Sels are separable bricks,
   of dimension n x m (where either n or m, but not both, is commonly 1).
   Accordingly, we provide separable morphological operations on brick
   Sels, using for binary both rasterops and dwa. Parsers are provided
   for a sequence of separable binary (rasterop and dwa) and grayscale
   brick morphological operations, in morphseq.c. The main
   advantage in using the parsers is that you don’t have to create
   and destroy Sels, or do any of the intermediate image bookkeeping.

   We also give composable separable brick functions for binary images,
   for both rasterop and dwa. These decompose each of the linear
   operations into a sequence of two operations at different scales,
   reducing the operation count to a sum of decomposition factors,
   rather than the (un-decomposed) product of factors.
   As always, parsers are provided for a sequence of such operations.

3. Grayscale morphology and rank order filters

   We give an efficient implementation of grayscale morphology for brick
   Sels. See the Leptonica home page and the source code.

   Brick Sels are separable into linear horizontal and vertical elements.
   We use the van Herk/Gil-Werman algorithm, that performs the calculations
   in a time that is independent of the size of the Sels. Implementations
   of tophat and hdome are also given.

   We also provide grayscale rank order filters for brick filters.
   The rank order filter is a generalization of grayscale morphology,
   that selects the rank-valued pixel (rather than the min or max).
   A color rank order filter applies the grayscale rank operation
   independently to each of the (r,g,b) components.

4. Image scaling

   Leptonica provides many simple and relatively efficient
   implementations of image scaling. Some of them are listed here;
   for the full set see the web page and the source code.

   Grayscale and color images are scaled using:

   • sampling
   • lowpass filtering followed by sampling,
   • area mapping
   • linear interpolation

   Scaling operations with antialiased sampling, area mapping,
   and linear interpolation are limited to 2, 4 and 8 bpp gray,
   24 bpp full RGB color, and 2, 4 and 8 bpp colormapped
   (bpp == bits/pixel). Scaling operations with simple sampling
   can be done at 1, 2, 4, 8, 16 and 32 bpp. Linear interpolation
   is slower but gives better results, especially for upsampling.
   For moderate downsampling, best results are obtained with area
   mapping scaling. With very high downsampling, either area mapping
   or antialias sampling (lowpass filter followed by sampling) give
   good results. Fast area map with power-of-2 reduction are also
   provided. Optional sharpening after resampling is provided to
   improve appearance by reducing the visual effect of averaging
   across sharp boundaries.

   For fast analysis of grayscale and color images, it is useful to
   have integer subsampling combined with pixel depth reduction.
   RGB color images can thus be converted to low-resolution
   grayscale and binary images.

   For binary scaling, the dest pixel can be selected from the
   closest corresponding source pixel. For the special case of
   power-of-2 binary reduction, low-pass rank-order filtering can be
   done in advance. Isotropic integer expansion is done by pixel replication.

   We also provide 2x, 3x, 4x, 6x, 8x, and 16x scale-to-gray reduction
   on binary images, to produce high quality reduced grayscale images.
   These are integrated into a scale-to-gray function with arbitrary
   reduction.

   Conversely, we have special 2x and 4x scale-to-binary expansion
   on grayscale images, using linear interpolation on grayscale
   raster line buffers followed by either thresholding or dithering.

   There are also image depth converters that don’t have scaling,
   such as unpacking operations from 1 bpp to grayscale, and
   thresholding and dithering operations from grayscale to 1, 2 and 4 bpp.

5. Image shear and rotation (and affine, projective, …)

   Image shear is implemented with both rasterops and linear interpolation.
   The rasterop implementation is faster and has no constraints on image
   depth. We provide horizontal and vertical shearing about an
   arbitrary point (really, a line), both in-place and from source to dest.
   The interpolated shear is used on 8 bpp and 32 bpp images, and
   gives a smoother result. Shear is used for the fastest implementations
   of rotation.

   There are three different types of general image rotators:

   a. Grayscale rotation using area mapping
   - pixRotateAM() for 8 bit gray and 24 bit color, about center
   - pixRotateAMCorner() for 8 bit gray, about image UL corner
   - pixRotateAMColorFast() for faster 24 bit color, about center

   b. Rotation of an image of arbitrary bit depth, using
   either 2 or 3 shears. These rotations can be done
   about an arbitrary point, and they can be either
   from source to dest or in-place; e.g.
   - pixRotateShear()
   - pixRotateShearIP()

   c. Rotation by sampling. This can be used on images of arbitrary
   depth, and done about an arbitrary point. Colormaps are retained.

   The area mapping rotations are slower and more accurate, because each
   new pixel is composed using an average of four neighboring pixels
   in the original image; this is sometimes also also called “antialiasing”.
   Very fast color area mapping rotation is provided.

   The shear rotations are much faster, and work on images of arbitrary
   pixel depth, but they just move pixels around without doing any averaging.
   The pixRotateShearIP() operates on the image in-place.

   We also provide orthogonal rotators (90, 180, 270 degree; left-right
   flip and top-bottom flip) for arbitrary image depth.
   And we provide implementations of affine, projective and bilinear
   transforms, with both sampling (for speed) and interpolation
   (for antialiasing).

6. Sequential algorithms

   We provide a number of fast sequential algorithms, including
   binary and grayscale seedfill, and the distance function for
   a binary image. The most efficient binary seedfill is
   pixSeedfill(), which uses Luc Vincent’s algorithm to iterate
   raster- and antiraster-ordered propagation, and can be used
   for either 4- or 8-connected fills. Similar raster/antiraster
   sequential algorithms are used to generate a distance map from
   a binary image, and for grayscale seedfill. We also use Heckbert’s
   stack-based filling algorithm for identifying 4- and 8-connected
   components in a binary image. A fast implementation of the
   watershed transform, using a priority queue, is included.

7. Image enhancement

   Some simple image enhancement routines for grayscale and color
   images have been provided. These include intensity mapping with
   gamma correction and contrast enhancement, histogram equalization,
   edge sharpening, smoothing, and various color-shifting operations.

8. Convolution and cousins

   A number of standard image processing operations are also
   included, such as block convolution, binary block rank filtering,
   grayscale and rgb rank order filtering, and edge and local
   minimum/maximum extraction. Generic convolution is included,
   for both separable and non-separable kernels, using float arrays
   in the Pix. Two implementations are included for grayscale and
   color bilateral filtering: a straightforward (slow) one, and a
   fast, approximate, separable one.

9. Image I/O

   Some facilities have been provided for image input and output.
   This is of course required to build executables that handle images,
   and many examples of such programs, most of which are for
   testing, can be built in the prog directory. Functions have been
   provided to allow reading and writing of files in JPEG, PNG,
   TIFF, BMP, PNM ,GIF, WEBP and JP2 formats. These formats were chosen
   for the following reasons:

   • JFIF JPEG is the standard method for lossy compression
     of grayscale and color images. It is supported natively
     in all browsers, and uses a good open source compression
     library. Decompression is supported by the rasterizers
     in PS and PDF, for level 2 and above. It has a progressive
     mode that compresses about 10% better than standard, but
     is considerably slower to decompress. See jpegio.c.

   • PNG is the standard method for lossless compression
     of binary, grayscale and color images. It is supported
     natively in all browsers, and uses a good open source
     compression library (zlib). It is superior in almost every
     respect to GIF (which, until recently, contained proprietary
     LZW compression). See pngio.c.

   • TIFF is a common interchange format, which supports different
     depths, colormaps, etc., and also has a relatively good and
     widely used binary compression format (CCITT Group 4).
     Decompression of G4 is supported by rasterizers in PS and PDF,
     level 2 and above. G4 compresses better than PNG for most
     text and line art images, but it does quite poorly for halftones.
     It has good and stable support by Leffler’s open source library,
     which is clean and small. Tiff also supports multipage
     images through a directory structure. Note: because jpeg is
     a supported tiff compression mode, leptonica requires linking
     both libtiff and libjpeg to read and write tiff. See tiffio.c

   • BMP has (until recently) had no compression. It is a simple
     format with colormaps that requires no external libraries.
     It is commonly used because it is a Microsoft standard,
     but has little besides simplicity to recommend it. See bmpio.c.

   • PNM is a very simple, old format that still has surprisingly
     wide use in the image processing community. It does not
     support compression or colormaps, but it does support binary,
     grayscale and rgb images. Like BMP, the implementation
     is simple and requires no external libraries. See pnmio.c.

   • WEBP is a new wavelet encoding method derived from libvpx,
     a video compression library. It is rapidly growing in acceptance,
     and is supported natively in several browsers. Leptonica provides
     an interface through webp into the underlying codec. You need
     to download libwebp. See webpio.c.

   • JP2 (jpeg2000) is a wavelet encoding method, that has clear
     advantages over jpeg in compression and quality (especially when
     the image has sharp edges, such as scanned documents), but is
     only slowly growing in acceptance. For it to be widely supported,
     it will require support on a major browser (as with webp).
     Leptonica provides an interface through openjpeg into the underlying
     codec. You need to download libopenjp2, version 2.X. See jp2kio.c.

   • GIF is still widely used in the world. With the expiration
     of the LZW patent, it is practical to add support for GIF files.
     The open source gif library is relatively incomplete and
     unsupported (because of the Sperry-Rand-Burroughs-Univac
     patent history). Leptonica supports versions 5.1+. See gifio.c.

   Here’s a summary of compression support and limitations:

   • All formats except JPEG, WEBP and JP2K support 1 bpp binary.
   • All formats support 8 bpp grayscale (GIF must have a colormap).
   • All formats except GIF support rgb color.
   • All formats except PNM, JPEG, WEBP and JP2K support 8 bpp colormap.
   • PNG and PNM support 2 and 4 bpp images.
   • PNG supports 2 and 4 bpp colormap, and 16 bpp without colormap.
   • PNG, JPEG, TIFF, WEBP, JP2K and GIF support image compression;
     PNM and BMP do not.
   • WEBP supports rgb color and rgba.
   • JP2 supports 8 bpp grayscale, rgb color and rgba.
     Use prog/ioformats_reg for a regression test on all formats, including
     thorough testing on TIFF.
     For more thorough testing on other formats, use:
   • prog/pngio_reg for PNG.
   • prog/gifio_reg for GIF
   • prog/webpio_reg for WEBP
   • prog/jp2kio_reg for JP2

   We provide generators for PS output, from all types of input images.
   The output can be either uncompressed or compressed with level 2
   (ccittg4 or dct) or level 3 (flate) encoding. You have flexibility
   for scaling and placing of images, and for printing at different
   resolutions. You can also compose mixed raster (text, image) PS.
   See psio1.c for examples of how to output PS for different applications.
   As examples of usage, see:

   • prog/converttops.c for a general image --> PS conversion
     for printing. You can specify the PS compression level (1, 2, or 3).
   • prog/imagetops.c for a special image --> PS conversion
     for printing at maximum size on 8.5 x 11 paper. You can
     specify the PS compression level (1, 2, or 3).
   • prog/convertfilestops.c to generate a multipage level 3 compressed
     PS file that can then be converted to pdf with ps2pdf.
   • prog/convertsegfilestops.c to generate a multipage, mixed raster,
     level 2 compressed PS file.

   We provide generators for PDF output, again from all types of input
   images, and with ccittg4, dct, flate and jpx (jpeg2000) compression.
   You can do the following for PDF:

   • Put any number of images onto a page, with specified input
     resolution, location and compression.
   • Write a mixed raster PDF, given an input image and a segmentation
     mask. Non-image regions are written in G4 (fax) encoding.
   • Concatenate single-page PDF wrapped images into a single PDF file.
   • Build a PDF file of all images in a directory or array of file names.
     As examples of usage, see:
   • prog/converttopdf.c: fast pdf generation with one image/page.
     For speed, this avoids transcoding whenever possible.
   • prog/convertfilestopdf.c: more flexibility in the output. You
     can set the resolution, scaling, encoding type and jpeg quality.
   • prog/convertsegfilestopdf.c: generates a multipage, mixed raster pdf,
     with separate controls for compressing text and non-text regions.

   Note: any or all of these I/O library calls can be stubbed out at
   compile time, using the environment variables in environ.h.

   For all formatted reads and writes, we support read from memory
   and write to memory. The gnu C runtime library (glibc) supports
   two I/O functions, open_memstream() and fmemopen(), which read
   and write directly to memory as if writing to a file stream.

   • On all platforms, leptonica supports direct read/write with memory
     for TIFF, PNG, BMP, GIF and WEBP formats.
   • On linux, leptonica uses the special gnu libraries to enable
     direct read/write with memory for JPEG, PNM and JP2.
   • On platforms without the gnu libraries, such as OSX, Windows
     and Solaris, read/write with memory for JPEG, PNM and JP2 goes
     through temp files.
     To enable/disable memory I/O for image read/write, see environ.h.

   We also provide fast serialization and deserialization between a pix
   in memory and a file (spixio.c). This works on all types of pix images.

10. Colormap removal and color quantization

Leptonica provides functions that remove colormaps, for conversion
to either 8 bpp gray or 24 bpp RGB. It also provides the inverse
function to colormap removal; namely, color quantization
from 24 bpp full color to 8 bpp colormap with some number
of colormap colors. Several versions are provided, some that
use a fast octree vector quantizer and others that use
a variation of the median cut quantizer. For high-level interfaces,
see for example: pixConvertRGBToColormap(), pixOctreeColorQuant(),
pixOctreeQuantByPopulation(), pixFixedOctcubeQuant256(),
and pixMedianCutQuant().

11. Programmatic image display

For debugging, pixDisplay() and pixDisplayWithTitle() in writefile.c
can be called to display an image using one of several display
programs (xzgv, xli, xv, l_view). If necessary to fit on the screen,
the image is reduced in size, with 1 bpp images being converted
to grayscale for readability. Another common debug method is to
accumulate intermediate images in a pixa, and then either view these
as a mosaic (using functions in pixafunc2.c), or gather them into
a compressed PDF or PostScript file for viewing with evince. Common
image display programs are: xzgv, xli, xv, display, gthumb, gqview,
evince, gv and acroread.

12. Document image analysis

Many functions have been included specifically to help with
document image analysis. These include skew and text orientation
detection; page segmentation; baseline finding for text;
unsupervised classification of connected components, characters
and words; dewarping camera images; adaptive binarization; and
a simple book-adaptive classifier for various character sets,
segmentation for newspaper articles, etc.

13. Data structures

Several simple data structures are provided for safe and efficient handling
of arrays of numbers, strings, pointers, and bytes. The generic
pointer array is implemented in four ways: as a stack, a queue,
a heap (used to implement a priority queue), and an array with
insertion and deletion, from which the stack operations form a subset.
Byte arrays are implemented both as a wrapper around the actual
array and as a queue. The string arrays are particularly useful
for both parsing and composing text. Generic lists with
doubly-linked cons cells are also provided. Other data structures
are provided for handling ordered sets and maps, as well as hash sets
and hash maps.

14. Examples of programs that are easily built using the library:

    • for plotting x-y data, we give a programmatic interface
      to the gnuplot program, with output to X11, png, ps or eps.
      We also allow serialization of the plot data, in a form
      such that the data can be read, the commands generated,
      and (finally) the plot constructed by running gnuplot.

    • a simple jbig2-type classifier, using various distance
      metrics between image components (correlation, rank
      hausdorff); see prog/jbcorrelation.c, prog/jbrankhaus.c.

    • a simple color segmenter, giving a smoothed image
      with a small number of the most significant colors.

    • a program for converting all images in a directory
      to a PostScript file, and a program for printing an image
      in any (supported) format to a PostScript printer.

    • various programs for generating pdf files from compressed
      images, including very fast ones that don’t scale and
      avoid transcoding if possible.

    • converters between binary images and SVG format.

    • an adaptive recognition utility for training and identifying
      text characters in a multipage document such as a book.

    • a bitmap font facility that allows painting text onto
      images. We currently support one font in several sizes.
      The font images and postscript programs for generating
      them are stored in prog/fonts/, and also as compiled strings
      in bmfdata.h.

    • a binary maze game lets you generate mazes and find shortest
      paths between two arbitrary points, if such a path exists.
      You can also compute the “shortest” (i.e., least cost) path
      between points on a grayscale image.

    • a 1D barcode reader. This is still in an early stage of development,
      with little testing, and it only decodes 6 formats.

    • a utility that will dewarp images of text that were captured
      with a camera at close range.

    • a sudoku solver and generator, including a good test for uniqueness

    • see (13, above) for other document image applications.

15. JBig2 encoder