Abstract This paper presents a new image restoration method based on a linear optimization model which restores part of the image from structured side information (SSI). The SSI can be transmitted to the receiver or embedded into the image itself by a digital watermarking technique. In this paper we focus on a special type of SSI for digital watermarking where the SSI is composed of mean values of 4×4 image blocks which can be used to restore manipulated blocks. Different from existing image restoration methods for similar types of SSI, the proposed method minimizes image discontinuity according to a relaxed definition of smoothness based on a 3×3 averaging filter of four adjacent pixel value differences, and the objective function of the optimization model has a second regularization term corresponding to a second-order smoothness criterion. Our experiments on 100 test images showed that given complete information of the SSI, the proposed image restoration technique can outperform the state-of-the-art model based on a simple linear optimization model by around 2dB in terms of an average Peak Signal-to-Noise Ratio (PSNR) value and around 0.04 in terms of a Structural Similarity Index (SSIM) value. We also tested the robustness of the image restoration method when it is applied to a self-restoration watermarking scheme and the experimental results showed that it is moderately robust to errors in SSI (which is embedded as a watermark) caused by JPEG compression (the average PSNR value remains above 16.5dB even when the JPEG QF is 50), additive Gaussian white noises (the average PSNR value is approximately 18.4dB when the noise variance σ2 is 10) and image rescaling assuming the original image size is known at the receiver side (e.g. the average PSNR value is approximately 19.6dB when the scaling ratio is 1.4).