Binary and Morphological Image Processing (Course: OCRopus)

Binary and Morphological Image Processing

Mathematical Morphology

What is it?

non-linear image processing
based on set theory, lattice theory, topology, and random functions
one way of capturing notions of size, shape, convexity, connectivity, and geodesic distance
defined on both discrete and continuous signals (as well as graphs, etc.)
can be generalized to grayscale

Applications

smoothing
structure detection (edges, lines, corners, etc.)
segmentation
direct morphological object and character recognition

Basic Operations

Erosion	Dilation
Opening	Closing

(Images from Wikipedia)

Different Implementations

Binary Morphology

brute force implementation on bytearrays
distance transform implementation
brute force implementation on packed bitmapas
run-length based implementations
(quad-tree based implementation)
(wavefront implementation)

Grayscale Morphology

brute force implementation on bytearrays
(other implementations)

Tradeoffs

brute force implementation on bytearrays

easy to use, requires no conversions, easy to extend
slow for large masks, inefficient image storage

distance transform implementation

fast for large masks
requires intarray (4x storage)

brute force implementation on packed bitmaps

faster than bytearray implementation, requires less storage
still slow for large masks, requires conversions

run-length based implementations

very fast for large masks, like packed bitmaps for smaller masks
requires conversions, only basic operations implemented

Pixelwise Operations

general operations (binary_ prefix)

invert, autoinvert, and, or
erode/dilate/close/open with circle/rect

distance transform computations

brushfire_1, brushfire_2, brushfire_inf (with various optional results)

distance transform morphology

dilate/erode with metric 1/2/inf
anisotropically scaled variants

grayscale morphology (gray_ prefix)

erode, dilate, open, close with arbitrary masks

Packed Integer & Run-Length Morphology

BitImage

bits.convert(bitimage,image), etc.
convert, count_rect, set_rect, resample_normed, resample, ...
reduce2_and (binary reduction)
transpose, flip_h, flip_v, rotate_rect (multiple of 90 deg)
set, setnot, and, or, andnot, ornot, xor, invert
skew, rotate
erode/dilate/open/close with rect/mask/rrect/line/circ

RLEImage

rle.transpose(out,in), etc.
convert, count_bits, invert, And, Or
dilate/erode/open/close with rect
skew, rotate, flip_v, bounding_boxes
runlength_statistics, runlength_peaks
dshow
(marker morphology etc.)

Document Cleanup using Morphology

Here is a simple example of noise removal using morphology:

byteimage = bytearray()
bitimage = bits.BitImage()
cleaned = bits.BitImage()
directional = bits.BitImage()

dinit(600,600)

temp = bytearray()
function bitshow(b,spec)
    spec = spec or ""
    bits.convert(temp,b)
    dshow(temp,spec)
end

read_image_binary(byteimage,arg[1])
bits.convert(bitimage,byteimage)
cleaned:copy(bitimage)
bitshow(cleaned,"a")
bits.close_rect(cleaned,2,2)
bitshow(cleaned,"c")
bits.open_rect(cleaned,2,2)
bitshow(cleaned,"d")
dwait()

Document Cleanup using Morphology

Thinning / Skeletonization

There's a special morphological operation: skinning or skeletonization:

thin(byteimage)

This is implemented by special purpose erosion loops.

Connected Component Analysis

after morphological filtering operations (to select the elements we want), we need to actually measure and extract those elements
operations for this in OCRopus are connected component labeling

label_components(intarray)
bounding_boxes(rectarray,intarray)
renumber_labels(intarray,start)
propagate_labels(intarray), propagate_labels_to(intarray,seed) [marker morphology]
remove_dontcares(intarray)
runlength statistics

TODO

Planned Improvements

make morphological operations consistent between implementations
implement more standard primitives for marker morphology
port RLE marker morphology
port fast grayscale morphology
fix bugs, make boundary conditions more consistent, simplify

Please submit bug reports (with examples that fail),

Layout Analysis using Morphology

Many simple layout analysis methods can be formulated as morphological operations:

morphological skew detection

rotate the page image at various different orientations
look for the rotations that let the largest number of horizontal runs survive an openingar

"text line smearing" and Docstrum mean linking horizontally close

horizontal black closing
determine opening parameters from runlength statistics (second peak * 1.5)

column separators contain tall, skinny whitespace rectangles

whitespace-based layout analysis

black horizontal or vertical lines contain skinny black rectangles

detecting layout components directly
requires near perfect deskewing

Example: Line Finding by Smearing

read_image_binary(image,arg[1])

runlength_histogram(hist,image,true,false)
gauss1d(hist,2.0)
valleys(spacing,hist,1,100,0.0)
wordsep = spacing:at(1)

binary_open_rect(image,wordsep,3)

lines:copy(image)
narray.sub(255,lines)
label_components(lines)

bounding_boxes(boxes,lines)

for i=1,boxes:length()-1 do
b = boxes:at(i)
print(i,b.x0,b.y0,b.x1,b.y1)
end

Example: Line Finding by Smearing (with display)

image = bytearray()
hist = floatarray(400)
spacing = intarray(3)
lines = intarray()
boxes = rectarray()

dinit(800,800)

read_image_binary(image,arg[1])
runlength_histogram(hist,image,true,false)
gauss1d(hist,2.0); dshow1d(hist); dwait()
valleys(spacing,hist,1,100,0.0)
wordsep = spacing:at(1)
dshow(image); dwait()
binary_open_rect(image,wordsep,3)
dshow(image); dwait()
lines:copy(image)
narray.sub(255,lines)
label_components(lines)
dshowr(lines); dwait()
bounding_boxes(boxes,lines)
for i=1,boxes:length()-1 do
b = boxes:at(i)
print(i,b.x0,b.y0,b.x1,b.y1)
end

Course: OCRopus