Adaptive Regularization Algorithm Paired with Image Segmentation Tatiana Serezhnikova1,2 1 Krasovsky Institute of Mathematics and Mechanics UB RAS 2 Ural Federal University, Ekaterinburg, Russia sti@imm.uran.ru Abstract. This paper presents the subsequent improvements of our adaptive regularization algorithm. The current version of the algorithm contains an additional stabilizer. This stabilizer includes the coefficient, which utilizes prior information about segmentation of an image to be processed. We demonstrate that our adaptive regularization algorithm can exploit only the observed image segmentation for both the adaptive coefficient calculation and successful restoration of the original image segmentation. Keywords: image restoration, Tikhonov regularization, adaptation, im- age segmentation 1 Introduction In the model experiments, see [1-4], we demonstrated, that our adaptive reg- ularization algorithm can successfully restore and provide more deblurred and denoisy intensity of the original model image. In this paper, we improve our algorithm, which is based on the results from [5-7], by an additional stabilizer. This stabilizer includes the coefficient, which utilizes some information about segmentation of an image to be restored. Most artificial objects are made of surfaces, resulting in images with several subimages (or a single subimage) together with their boundary lines. These facts motivate us to use ideas from image segmentation in order to improve our algorithm. In the sequel, we describe the stabilizer coefficient con- struction, using ideas from image segmentation. Image segmentation algorithms are based on properties of intensity values: discontinuity and similarity, see [8-11]. Starting with the observed object inten- sity, setting β(x, y) ≡ 0 in our adaptive algorithm, we successfully apply the original approach for both sub-images and their boundaries. In the next iter- ations, the adaptive algorithm utilizes this initial result for calculation of the coefficient β. Thus, we consider image segmentation both as result and tool in every image restoration. We prove numerically that the proposed algorithm can reveal the latent image segmentation of observed images. 166 The paper is organized as follows. In Section 2, we describe regularizing functionals and present our adaptive technique. In Section 3, we describe the calculation process of our stabilizer coefficient. The last section concludes the paper. 2 Mathematical Model for Image Deblurring We consider the following two-dimensional Fredholm integral equation of the first kind: Z1 Z1 Au ≡ K(x − ξ, y − η)u(x, y)dx, dy = f (ξ, η). (1) 0 0 In image restoration, the estimation of u from the observation of f is referred to as the two-dimensional image deblurring problem. We construct and develop the novel technique for numeric solution of equa- tion (1). Abstract methods with convergence analysis of regularization for this problem are presented in [3-7]. The foundation of the regularization method is given by Z  min ||Ah u − fδ ||2L2 + α (||u||2L2 + J(u)) : u ∈ U , J(u) = |∇u| dx, (2) D where ∇u denotes the gradient of smooth function u, (u ∈ W11 (D)), J(u) is the total variation of the function u on D. The practical implementation of this method requires minimization of the functional in (2). The novelty was that we proposed to add the version of the iterative tech- nique, containing additional parameters βi,j , βi,j ≥ 0 , see [1-4]: X uk = arg min {Φα N (u) + βi,j (ui,j − uk−1 2 N i,j ) : u ∈ R } . (3) i,j Here, N = n2 , Φα N (u) is the discrete form of the functional in (2). P βi,j (ui,j − uk−1 2 i,j ) is a discrete form for the additional stabilizer in (3). i,j We use the iterative subgradient method in order to compute uk defined in (3), see details in [1-4]. 167 3 Stabilizer coefficient selection 3.1 Image Segmentation: Motivation The previous version of the algorithm (3) used the constant β in every mesh point of discrete models. The low resulting accuracy of this two-dimensional model led us to change the way of {βi,j } selection. As we said above, most man-made objects are made of surfaces, resulting in images with a single image or some sub-images. The quality of the images restoration features the quality of sub-images restoration together with sub- image boundary lines restoration. In [1], we proposed the more general form of the stabilizer I β : Z I = β(x, y)[u(x, y) − uk (x, y)]2 dxdy, β (4) Q we used  β(x, y) = umax , for (x, y) ∈ Q, (5) β(x, y) = 0, for (x, y) ∈ Π/Q, where umax = max{utrue (x, y) , (x, y) ∈ Π = [0, 1] × [0, 1]}, (6) (x, y) ∈ Q ⇔ utrue (x, y) = umax . (7) So, in [1] our regularization algorithm stabilizer includes the coefficient β, which uses some information about true image segmentation, see (6) and (7). This facts motivates us to exclude true image parameters. We approach this purpose using image segmentation ideas. 3.2 Image Segmentation as Tool In this paper we propose to begin calculations with the parameter β ≡ 0. So, in this case, we use standard regularization method: Z  min ||Ah u − fδ ||2L2 + α (||u||2L2 + J(u)) : u ∈ U , J(u) = |∇u| dx, (8) D where ∇u denotes the gradient of smooth function u, J(u) is the total variation of the function u on D. After obtaining the solution of problem (8), we get approximate ũ0 (x, y) , Q0 , ΓQ0 , and we use them for the βi,j construction: βi,j ∈ {o; c}, c = max{ũ0 (x, y), (x, y) ∈ Q0 ∪ ΓQ0 }. (9) 168 3.3 Image Segmentation as Result Now, using β calculated in (9), the algorithm computes the final image restora- tion including its final image segmentation. Numerical experiments have confirmed our ideas. Thus, we see in Figure 1: (a) the observed image; (b) the restoration image; (c) the central image segment restoration, Q0 ∪ ΓQ0 , calculated with β ≡ 0; (b) the central image segment restoration, Q̃∪ Γ̃Q̃ , calculated with adapted β. a) The observed image b) The recovered image c) The model segment restoration d) The model segment restoration for β(x, y) ≡ 0 for the adapted stabilizer coeffi- cient β(x, y) Fig. 1. Model experiments It is clear, that we can write the final image segmentation of the recovered image in the form: Π = {Π/Q̃} ∪ Q̃, (10) were Q̃ ∪ Γ̃Q̃ we see in Figure 1.(d), Π = [0, 1] × [0, 1]. 169 3.4 Conclusion In this paper, we have described and verified the image segmentation approach for the construction of stabilizer coefficient β. Starting with the observed object intensity and setting the stabilizer coef- ficient β ≡ 0 in the regularization algorithm, we successfully apply the initial approach for both the sub-image and the sub-image boundary, Q0 , ΓQ0 . After that, we use calculated results for construction of the adaptive stabilizer coefficient β. At this step the image segmentation is a tool. Using the calculated coefficient β, the algorithm computes the final recovered image. We obtain a good localization of segments, Q̃, ΓQ̃ , and we see a more deblurred final image segmentation. As a result, in this paper, we have described and verified that our adaptive algorithm does not need a priori information. For successful image restoration and restoration of image segmentation, our adaptive algorithm can utilize the image of an observed object only. We plan the following modifications and experiments: – inclusion of the solution estimate for equation u(x, y, ΓQ (x, y)) = c to the estimate list; – validation of β k inclusion in (4), where k is the iteration number; – processing of thin lines and narrow segments. Acknowledgments The author expresses special gratitude to Prof. V.V.Vasin from the Institute Mathematics and Mechanics of Ural Branch of RAS. The author would like to thank the colleagues from AIST Program and Organizing Committees for their helpful advice and guidance in the paper preparations. This work was supported by the Program of UB RAS “Mathematical models, algorithms, high-performance computational and information technologies and applications”, project 15-7-1-13. References [1] T.I. Serezhnikova. An algorithm based on the special method of the reg- ularizationand the adaptation for improving the quality of image restora- tions.Univer.J.Comp.Math.,V.2(1) 11–16 (2014) [2] T.I. Serezhnikova. Image restoration algorithm based on regularization and adaptation.In.: AIST 2014, CCIS 436, Springer, 213–221 (2014) [3] V.V. Vasin and T.I. Serezhnikova. A regularizing algorithm for approximation of a nonsmooth solution of Fredholm integral equations of the first kind. J. VICH. TECH., V. 15(2), 15–23 ( 2010) [4] V.V. Vasin and T.I. Serezhnikova. Two steps method for approximation of a nons- mooth solutions and nosy image reconstructions. J. Avt. Tel., No.2, 126–135 (2004) 170 [5] V.V. Vasin. Proximal algorithm with projection in problems of the convex programming.Ural Sci. Center AN SSSR, Instit. Mathem. I Mekhan., Sverdlovsk, pp. 47 (1982) [6] A.N. Tikhonov and V. Arsenin. Solutions of Ill-Posed Problems. Wiley, New York (1977) [7] C.R. Vogel. Computational methods for inverse problems. SIAM, Philadelphia (2002) [8] R.C. Gonzalez, R.E. Woods. Digital image processing,3-ed ed. Prentice Hall,New Jersey(2008) [9] X.Chen, M.K. Ng, C. Zhang. Non-Lipshitz lp − regularization and box constrained model for image reconstruction. IEEE Tr. Im. Proc. V.21(12), 4709–4721 (2012) [10] P. Arbelaer, M. Maire, Ch. Eowlkes, J. Malik. Contour detection and hierarchical image segmentation. IEEE Trans. Pattern Analysis and Machine Intelligence. 33(5), 898-916 (2011) [11] J.Canny A computational approach to edge detection. IEEE Trans. Pattern Anal- ysis and Machine Intelligence. V.8(6), 679-698 (1986) 171