Wednesday, June 25, 2014

Stroke Width Transform using Generalized Distance Transform

The original Stroke Width Transform algorithm is described in the following paper: 
Detecting Text in Natural Scenes with Stroke Width Transform

There are two major implementations available:
1- The version Jue's matlab implementation uses from bresenham_swt.m

2- A version provided by a few Cornell students: https://github.com/aperrau/DetectText

This algorithm starts by edge detection. Then from each edge pixel it traces rays prependicular to the edge orientation at that pixel and tried to hit another edge. The distance between the two edge pixels give an estimate of stroke width.My implementation of Stroke Width Transform is different. Instead of ray tracing I use Generalized Distance Transform. The core of my code is three MATLAB lines:

D = DT(img);
[~, R]= DT(-D);
swt=sqrt(D(R));

DT is generalized distance transform function from here. D is distance transform and R is the assignment.

Other than its simplicity this implementation has several advantages:
1- Its complexity is O(n) where n is the number of pixels
2- The input can be continues grayscale values. The algorithm takes advantage of anti-aliasing matt around strokes to provide a more accurate stroke width estimate.
3- The output is smoother. There are some holes in the original SWT implementation that are fixed here.
Here is a visual comparison of my implementation with the old techniques.
https://dl.dropboxusercontent.com/u/20022261/reports/stroke_width_transform_benchmark.html

The first column contains the original images. The second column is a segmentation using rgb k-means. Please note that the boundary matt is preserved. The third column is the output of my SWT implementation. The forth column is the code Jue's students currently use. The Forth column is an implementation from Cornell students. The last 




No comments:

Post a Comment