A Simple yet Effective Image Repairing Algorithm

A 2D binary image is well-composed if it does not contain 2 x 2 blocks of two diagonal black and two diagonal white pixels, called critical configurations. Some image processing algorithms are simpler on well-composed images. The process of transforming an image into a well-composed one is called repairing.We propose a new topology-preserving approach, which produces two well-composed images starting from an image I depending on the chosen adjacency (vertex or edge adjacency), in the same original square grid space as I. The size of the repaired images depends on the number and distribution of the critical configurations. A well-composed image I is not changed, while in the worst case the size increases at most two times (or four times if we want to preserve the aspect ratio). The advantage of our approach is in the small size of the repaired images, with a positive impact on the execution time of processing tasks. We demonstrate this experimentally by considering two classical image processing tasks: contour extraction and shrinking.