Fast binary image set operations on a run-based representation

• Definition of run spatial relations for comparisons between runs in a clear and enumerative way.
• Efficient set operations using a pair of runs as operands.
• The run iterator structure to handle the set operations of columns in a semantically comprehensive and elegant way.
• Efficient set operations of binary images using run forest representation and the run iterator structure.

Set operations are common processing of binary images. Though set operations implemented through naïve pixel-by-pixel logical operations are usually efficient, applications exist where the number of required set operations is large and faster set operations are needed. For such applications, a run-based representation, run forest, of binary images is proposed, and commonly used set operations of intersection, union, complementation, symmetric difference and set difference are realized on it. Run forests are lists of columns, which are also lists of runs in an image column. Spatial relations of two runs are exhaustively enumerated. A data structure called run iterator is designed to elegantly handle the operations of two runs. Run operations themselves consist of logical operations and assignments of integers, and can thus be very fast. Taking advantages of the simplicity of run operations, as well as the nature of run forest being compressive and well ordered, the set operations are efficiently realized. Experimental results show that although conversions of binary images to and from run forests cause computational overheads, this can be quite compensated during the computation of enough set operations, making the proposed method a suitable choice for applications with many set operations among largely fixed binary images, or applications using the run forest as the base representation throughout.