An algorithm for the rapid computation of boundaries of run-length encoded regions

摘要

A finite state machine-based algorithm for the rapid extraction of boundaries of run-length encoded regions is presented. The algorithm operates directly on the run data structure contained in run-length encoding, and yields boundaries in the form of four- or eight-connected point lists describing closed positively directed countours of four- or eight-connected regions. The algorithm differentiates between external and internal (boundaries of holes in the region) boundaries, and can handle multiple external and internal boundaries for each run-length encoded region. The four state finite state machine can be reduced to a two-state machine. A state transition occurs as the boundary traverses each run. The transition predicates can be implemented as a simple decision tree.Run-length encoding is a common image/region encoding techniques. This algorithm complements the existing operators which work directly on such region descriptors, making them more attractive as a representation for region manipulation.