Monday, October 22, 2012

GPU-accelerated Path Rendering

Last May I wrote about a major breakthrough in path rendering on the GPU by Mark Kilgard. I am happy to report that Mark—together with Jeff Bolz—has been hard at work on the rest necessary for a complete raster image processor (RIP). They have invented a new "Stencil, then Cover" (StC) algorithm in which the stencil step is explicitly decoupled from the subsequent cover step.

In the stencil step, a path's filled or stroked coverage is determined. In the cover step, the conservative geometry intended to test and reset the coverage determinations of the stencil step is rasterized, while shading color samples within the path. They have not only achieved fantastic acceleration, but also full completeness and correctness. Usually, the performance killer is the bottleneck between CPU and GPU, like when transparency is computed in the CPU. Kilgard and Bolz solve their revalidation bottleneck by using a configurable front-end processor in the GPU to transition quickly between the stencil step and the cover step.

For more information, see their paper at SIGGRAPH Asia, a pre-print of which is available at this link:

Tuesday, October 16, 2012


This year I have been working on document information retrieval, which is as far from color as you can imagine. Indeed, business documents are pretty dry binary black and white items, so that the first step—before even doing optical character recognition—is to binarize the document images so we can efficiently work with bitmaps. In the old days binarization was relatively easy, because almost any scanner illumination can easily be compensated when it is not uniform (see US patent 5,901,243).

Today binarization is much harder, because an increased number of documents is imaged with digital cameras, most often of the kind in smart phones. Much work went into extending existing binarization algorithms to text in pictorial images, alas with little success. It turns out that a completely different algorithmic approach is required, as was recently published in the paper

Yan Wang and Chuanjiang He, Binarization method based on evolution equation for document images produced by cameras, Journal of Electronic Imaging 21 (2012), no. 2, 023030

Here is the abstract:

We present an evolution equation-based binarization method for document images produced by cameras. Unlike the existing thresholding techniques, the idea behind our method is that a family of gradually binarized images is obtained by the solution of an evolution partial differential equation, starting with an original image. In our formulation, the evolution is controlled by a global force and a local force, both of which have opposite sign inside and outside the object of interests in the original image. A simple finite difference scheme with a significantly larger time step is used to solve the evolution equation numerically; the desired binarization is typically obtained after only one or two iterations. Experimental results on 122 camera document images show that our method yields good visual quality and OCR performance.