Reconstruction of Connected Digital Lines Based on Constrained Regularization

This paper presents a new approach for reconstruction of disconnected digital lines (DDLs) based on a constrained regularization model which ensures connectivity of the digital lines (DLs) in the discrete image plane. The first step in this approach is to determine the order of given pixels of the DDL. To determine connectivity of pixels, we use the usual 8-neighbor connectivity in discrete images. For any neighboring pixels of the DDL that are not connected, we determine a number of new pixel values that need to be reconstructed between these pixels. Next, the integer-valued $x$ - and $y$ -coordinates of the location of the pixels of the DDLs are segregated into two 1D signal vectors. Then the $x$ - and $y$ -coordinates of the missing pixels of the DDLs are estimated using a new constrained regularization. While the solution of this constrained minimization problem provides real values for the $x$ - and $y$ -coordinates of pixels positions, the imposed constraint ensures connectivity of the resulting DLs in the image plane after transforming the computed values from $\mathbb {R}$ to $\mathbb {N}$ . The proposed regularization approach forces connected lines with small curvature. The experimental results demonstrate that the proposed technique improves DL intersection detection, as well. Moreover, this technique has a high potential to be used as a fast approach in binary image inpainting particularly overcoming the shortcomings of conventional methods which cause destruction of thin objects and blurring in the recovered regions.

I. Introduction

Digital lines (DLs) are the discrete representation of straight lines or curves in a discrete coordinate system, play an important role in image processing and pattern recognition. One of the most important properties of DLs is the connectivity. We call a DL connected if successive components of the DL are neighboring pixels (i.e., 4/8-neighbor connectivity). DLs describe patterns of objects in the images but usually appear as disconnected segments in the discrete planes. For example, DLs resulting from edge detection methods are often discontinuous due to the presence of noise or low variation in the distribution of the grey levels. Disconnected DLs (DDLs) also appear as outputs of parametric active contours due to the nature of these methods. Connectivity of the DLs is crucial for a wide range of applications in image processing such as image segmentation, edge linking [1], [2], [3], [4], [5], [6], [7], [8], [9] and DLs intersection detection [10], [11]. Also, the conventional approach to generate a binary mask, which has many applications in image segmentation and pattern recognition, uses the imfill function of MATLAB and requires connected DLs as an input. Moreover, in most applications, generation and usage of the connected DLs are a part of computationally expensive workflows, while disconnected lines can terminate the running workflows [12]. So far, to the best of the author’s knowledge, not much attention has been paid to this problem. Typical approaches that are currently used to compute DDLs include morphological operations as well as 1D and 2D interpolations. In the following subsection, we discuss these approaches and their drawbacks.