Removing Redundancies in Binary Images

Abstract

Every day a huge amount of digital data is generated. Processing such big data encourages efficient data structure and parallelized operations. In this regard, this paper proposes a graph-based method reducing the memory requirement of the data storage. Graphs as a versatile representative tool in intelligent systems and pattern recognition may consist of many nonessential edges accumulating memory. This paper defines the structure of such redundant edges in the neighborhood graph of a 2D binary image. We introduce a novel approach for contracting the edges that simultaneously assists in determining the structurally redundant edges. In addition, finding a set of independent edges, the redundant edges are removed in parallel with the complexity O(1 ). Theoretically, we prove that the maximum number of redundant edges is bounded by half of all edges. Practical results show the memory requirement decreases significantly depending on the input data in different categories of binary image data sets. Using the combinatorial map as the data structure, first the topological structure of the graph is preserved. Second, the method can be extended to higher dimensions (nD).