Fast binary image set operations on a run-based representation

摘要

Set operations are common processing of binary images. Though set operations implemented through naive 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. (C) 2016 Published by Elsevier B.V.