{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:45:32Z","timestamp":1740109532604,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,3,16]],"date-time":"2020-03-16T00:00:00Z","timestamp":1584316800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,16]],"date-time":"2020-03-16T00:00:00Z","timestamp":1584316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000735","name":"University of Cambridge","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000735","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we study a class of fast geometric image inpainting methods based on the idea of filling the inpainting domain in successive shells from its boundary inwards. Image pixels are filled by assigning them a color equal to a weighted average of their already filled neighbors. However, there is flexibility in terms of the order in which pixels are filled, the weights used for averaging, and the neighborhood that is averaged over. Varying these degrees of freedom leads to different algorithms, and indeed the literature contains several methods falling into this general class. All of them are very fast, but at the same time all of them leave undesirable artifacts such as \u201ckinking\u201d (bending) or blurring of extrapolated isophotes. Our objective in this paper is to build a theoretical model in order to understand why these artifacts occur and what, if anything, can be done about them. Our model is based on two distinct limits: a continuum limit in which the pixel width<jats:inline-formula><jats:alternatives><jats:tex-math>$$h \\rightarrow 0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>h<\/mml:mi><mml:mo>\u2192<\/mml:mo><mml:mn>0<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and an asymptotic limit in which<jats:inline-formula><jats:alternatives><jats:tex-math>$$h &gt; 0$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>h<\/mml:mi><mml:mo>&gt;<\/mml:mo><mml:mn>0<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>but<jats:inline-formula><jats:alternatives><jats:tex-math>$$h \\ll 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>h<\/mml:mi><mml:mo>\u226a<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The former will allow us to explain \u201ckinking\u201d artifacts (and what to do about them) while the latter will allow us to understand blur. Both limits are derived based on a connection between the class of algorithms under consideration and stopped random walks. At the same time, we consider a semi-implicit extension in which pixels in a given shell are solved for simultaneously by solving a linear system. We prove (within the continuum limit) that this extension is able to completely eliminate kinking artifacts, which we also prove must always be present in the direct method. Finally, we show that although our results are derived in the context of inpainting, they are in fact abstract results that apply more generally. As an example, we show how our theory can also be applied to a problem in numerical linear algebra.<\/jats:p>","DOI":"10.1007\/s10208-020-09450-3","type":"journal-article","created":{"date-parts":[[2020,3,16]],"date-time":"2020-03-16T23:02:55Z","timestamp":1584399775000},"page":"1549-1651","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Analysis of Artifacts in Shell-Based Image Inpainting: Why They Occur and How to Eliminate Them"],"prefix":"10.1007","volume":"20","author":[{"given":"L. Robert","family":"Hocking","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Holding","sequence":"additional","affiliation":[]},{"given":"Carola-Bibiane","family":"Sch\u00f6nlieb","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,16]]},"reference":[{"key":"9450_CR1","doi-asserted-by":"crossref","unstructured":"Ambrosio, L., Fusco, N., Pallara, D.: Functions of bounded variation and free discontinuity problems. Oxford Mathematical Monographs (2000)","DOI":"10.1093\/oso\/9780198502456.001.0001"},{"key":"9450_CR2","unstructured":"Apostol, T.M.: Mathematical Analysis. Pearson (1974)"},{"issue":"3","key":"9450_CR3","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s11263-010-0418-7","volume":"93","author":"P Arias","year":"2011","unstructured":"Arias, P., Facciolo, G., Caselles, V., Sapiro, G.: A variational framework for exemplar-based image inpainting. Int. J. Comput. Vision 93(3), 319\u2013347 (2011). https:\/\/doi.org\/10.1007\/s11263-010-0418-7.","journal-title":"Int. J. Comput. Vision"},{"issue":"8","key":"9450_CR4","doi-asserted-by":"publisher","first-page":"1200","DOI":"10.1109\/83.935036","volume":"10","author":"C Ballester","year":"2001","unstructured":"Ballester, C., Bertalmio, M., Caselles, V., Sapiro, G., Verdera, J.: Filling-in by joint interpolation of vector fields and gray levels. IEEE Transactions on Image Processing 10(8), 1200\u20131211 (2001). https:\/\/doi.org\/10.1109\/83.935036","journal-title":"IEEE Transactions on Image Processing"},{"key":"9450_CR5","unstructured":"Bellman, R.: A Brief Introduction to Theta Functions. Holt (1961)"},{"key":"9450_CR6","doi-asserted-by":"crossref","unstructured":"Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C.: Image inpainting. In: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pp. 417\u2013424. ACM Press\/Addison-Wesley Publishing Co. (2000)","DOI":"10.1145\/344779.344972"},{"issue":"3","key":"9450_CR7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/s10851-007-0017-6","volume":"28","author":"F Bornemann","year":"2007","unstructured":"Bornemann, F., M\u00e4rz, T.: Fast image inpainting based on coherence transport. Journal of Mathematical Imaging and Vision 28(3), 259\u2013278 (2007). https:\/\/doi.org\/10.1007\/s10851-007-0017-6.","journal-title":"Journal of Mathematical Imaging and Vision"},{"key":"9450_CR8","volume-title":"The Fourier Transform and its Applications","author":"R Bracewell","year":"1978","unstructured":"Bracewell, R.: The Fourier Transform and its Applications, second edn. McGraw-Hill Kogakusha, Ltd., Tokyo (1978)","edition":"2"},{"key":"9450_CR9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719505","volume-title":"A Multigrid Tutorial","author":"WL Briggs","year":"2000","unstructured":"Briggs, W.L., Henson, V.E., McCormick, S.F.: A Multigrid Tutorial: Second Edition. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000)","edition":"2"},{"key":"9450_CR10","unstructured":"Brown, R.A.: Barycentric coordinates as interpolants. CoRR (2013). arXiv:1308.1279"},{"issue":"4","key":"9450_CR11","doi-asserted-by":"publisher","first-page":"1129","DOI":"10.1137\/080728548","volume":"2","author":"M Burger","year":"2009","unstructured":"Burger, M., He, L., Sch\u00f6nlieb, C.: Cahn-hilliard inpainting and a generalization for grayvalue images. SIAM J. Imaging Sci. 2(4), 1129\u20131167 (2009)","journal-title":"SIAM J. Imaging Sci."},{"issue":"2","key":"9450_CR12","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1109\/TIP.2016.2619263","volume":"26","author":"P Buyssens","year":"2017","unstructured":"Buyssens, P., Meur, O., Daisy, M., Tschumperl\u00e9, D., L\u00e9zoray, O.: Depth-guided disocclusion inpainting of synthesized rgb-d images. IEEE Transactions on Image Processing 26(2), 525\u2013538 (2017). https:\/\/doi.org\/10.1109\/TIP.2016.2619263","journal-title":"IEEE Transactions on Image Processing"},{"key":"9450_CR13","doi-asserted-by":"crossref","unstructured":"Chan, T., Kang, S., Shen, J.: Euler\u2019s elastica and curvature-based inpainting. SIAM Journal on Applied Mathematics pp. 564\u2013592 (2002)","DOI":"10.1137\/S0036139901390088"},{"issue":"5","key":"9450_CR14","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1002\/cpa.20075","volume":"58","author":"T Chan","year":"2005","unstructured":"Chan, T., Shen, J.: Variational image inpainting. Communications on pure and applied mathematics 58(5), 579\u2013619 (2005)","journal-title":"Communications on pure and applied mathematics"},{"issue":"2","key":"9450_CR15","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1006\/jnth.1993.1017","volume":"43","author":"J Cilleruelo","year":"1993","unstructured":"Cilleruelo, J.: The distribution of the lattice points on circles. Journal of Number Theory 43(2), 198 \u2013 202 (1993). https:\/\/doi.org\/10.1006\/jnth.1993.1017.","journal-title":"Journal of Number Theory"},{"key":"9450_CR16","doi-asserted-by":"publisher","first-page":"1200","DOI":"10.1109\/TIP.2004.833105","volume":"13","author":"A Criminisi","year":"2004","unstructured":"Criminisi, A., P\u00e9rez, P., Toyama, K.: Region filling and object removal by exemplar-based image inpainting. IEEE Transactions on Image Processing 13, 1200\u20131212 (2004)","journal-title":"IEEE Transactions on Image Processing"},{"key":"9450_CR17","doi-asserted-by":"publisher","unstructured":"Daribo, I., Pesquet-Popescu, B.: Depth-aided image inpainting for novel view synthesis. In: 2010 IEEE International Workshop on Multimedia Signal Processing, pp. 167\u2013170 (2010). https:\/\/doi.org\/10.1109\/MMSP.2010.5662013","DOI":"10.1109\/MMSP.2010.5662013"},{"key":"9450_CR18","unstructured":"domotorp (http:\/\/mathoverflow.net\/users\/955\/domotorp): Conjecture regarding closest point inside a discrete ball to a line. MathOverflow. http:\/\/mathoverflow.net\/q\/187830 (version: 2014-11-22)"},{"issue":"1\u20133","key":"9450_CR19","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S0012-365X(98)00329-X","volume":"200","author":"P Erd\u00f6s","year":"1999","unstructured":"Erd\u00f6s, P., Hall, R.: On the angular distribution of gaussian integers with fixed norm. Discrete Mathematics 200(1\u20133), 87 \u2013 94 (1999). https:\/\/doi.org\/10.1016\/S0012-365X(98)00329-X.","journal-title":"Discrete Mathematics"},{"key":"9450_CR20","doi-asserted-by":"publisher","first-page":"286","DOI":"10.5201\/ipol.2013.87","volume":"3","author":"P Getreuer","year":"2013","unstructured":"Getreuer, P.: A Survey of Gaussian Convolution Algorithms. Image Processing On Line 3, 286\u2013310 (2013). https:\/\/doi.org\/10.5201\/ipol.2013.87","journal-title":"Image Processing On Line"},{"issue":"1","key":"9450_CR21","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1109\/MSP.2013.2273004","volume":"31","author":"C Guillemot","year":"2014","unstructured":"Guillemot, C., Meur, O.: Image inpainting : Overview and recent advances. IEEE Signal Processing Magazine 31(1), 127\u2013144 (2014). https:\/\/doi.org\/10.1109\/MSP.2013.2273004","journal-title":"IEEE Signal Processing Magazine"},{"issue":"2","key":"9450_CR22","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1214\/aop\/1176996709","volume":"2","author":"A Gut","year":"1974","unstructured":"Gut, A.: On the moments and limit distributions of some first passage times. Ann. Probab. 2(2), 277\u2013308 (1974). https:\/\/doi.org\/10.1214\/aop\/1176996709.","journal-title":"Ann. Probab."},{"key":"9450_CR23","doi-asserted-by":"publisher","unstructured":"Gut, A.: On the moments of some first passage times for sums of dependent random variables. Stochastic Processes and their Applications 2(1), 115 \u2013 126 (1974). https:\/\/doi.org\/10.1016\/0304-4149(74)90015-5. http:\/\/www.sciencedirect.com\/science\/article\/pii\/0304414974900155","DOI":"10.1016\/0304-4149(74)90015-5"},{"key":"9450_CR24","unstructured":"Gut, A.: Stopped Random Walks: Limit Theorems and Applications. Springer Series in Operations Research and Financial Engineering. Springer New York (2009). https:\/\/books.google.co.uk\/books?id=tWfBs5G7jHIC"},{"key":"9450_CR25","unstructured":"Gut, A., Janson, S.: The limiting behaviour of certain stopped sums and some applications. Scandinavian Journal of Statistics 10(4), 281\u2013292 (1983). http:\/\/www.jstor.org\/stable\/4615930"},{"key":"9450_CR26","unstructured":"Hocking, L., Holding, T., Sch\u00f6nlieb, C.: Numerical analysis of shell-based geometric image inpainting algorithms and their semi-implicit extension. arXiv:1707.09713"},{"key":"9450_CR27","unstructured":"Hocking, L., MacKenzie, R., Sch\u00f6nlieb, C.: Guidefill: Gpu accelerated, artist guided geometric inpainting for 3d conversion of film. arXiv:1611.05319"},{"key":"9450_CR28","doi-asserted-by":"crossref","unstructured":"LeVeque, R.J.: Numerical methods for conservation laws (2. ed.). Lectures in mathematics. Birkh\u00e4user (1992)","DOI":"10.1007\/978-3-0348-8629-1"},{"key":"9450_CR29","doi-asserted-by":"publisher","unstructured":"Ma, L., Do, L., de\u00a0With, P.: Depth-guided inpainting algorithm for free-viewpoint video. In: 2012 19th IEEE International Conference on Image Processing, pp. 1721\u20131724 (2012). https:\/\/doi.org\/10.1109\/ICIP.2012.6467211","DOI":"10.1109\/ICIP.2012.6467211"},{"key":"9450_CR30","doi-asserted-by":"publisher","unstructured":"Malinovskii, V.K.: Limit theorems for stopped random sequences. i: Rates of convergence and asymptotic expansions. Theory of Probability & Its Applications 38(4), 673\u2013693 (1994). https:\/\/doi.org\/10.1137\/1138067","DOI":"10.1137\/1138067"},{"issue":"4","key":"9450_CR31","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1137\/100807296","volume":"4","author":"T M\u00e4rz","year":"2011","unstructured":"M\u00e4rz, T.: Image inpainting based on coherence transport with adapted distance functions. SIAM J. Img. Sci. 4(4), 981\u20131000 (2011). https:\/\/doi.org\/10.1137\/100807296","journal-title":"SIAM J. Img. Sci."},{"issue":"4","key":"9450_CR32","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1007\/s10208-014-9199-7","volume":"15","author":"T M\u00e4rz","year":"2015","unstructured":"M\u00e4rz, T.: A well-posedness framework for inpainting based on coherence transport. Foundations of Computational Mathematics 15(4), 973\u20131033 (2015). https:\/\/doi.org\/10.1007\/s10208-014-9199-7.","journal-title":"Foundations of Computational Mathematics"},{"key":"9450_CR33","unstructured":"Masnou, S., Morel, J.: Level lines based disocclusion. In: Image Processing, 1998. ICIP 98. Proceedings. 1998 International Conference on, pp. 259\u2013263. IEEE (1998)"},{"key":"9450_CR34","doi-asserted-by":"crossref","unstructured":"Sch\u00f6nlieb, C.: Partial Differential Equation Methods for Image Inpainting. Cambridge University Press (2015)","DOI":"10.1017\/CBO9780511734304"},{"key":"9450_CR35","volume-title":"The Scientist and Engineer\u2019s Guide to Digital Signal Processing","author":"SW Smith","year":"1997","unstructured":"Smith, S.W.: The Scientist and Engineer\u2019s Guide to Digital Signal Processing. California Technical Publishing, San Diego, CA, USA (1997)"},{"key":"9450_CR36","unstructured":"Stam, A.J.: Local central limit theorem for first entrance of a random walk into a half space. Compositio Mathematica 23(1), 15\u201323 (1971). http:\/\/eudml.org\/doc\/89073"},{"key":"9450_CR37","unstructured":"Tao, T.: Variants of the central limit theorem. https:\/\/terrytao.wordpress.com\/2015\/11\/19\/275a-notes-5-variants-of-the-central-limit-theorem\/#more-8566"},{"issue":"1","key":"9450_CR38","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1080\/10867651.2004.10487596","volume":"9","author":"A Telea","year":"2004","unstructured":"Telea, A.: An image inpainting technique based on the fast marching method. Journal of Graphics Tools 9(1), 23\u201334 (2004)","journal-title":"Journal of Graphics Tools"},{"key":"9450_CR39","unstructured":"Trottenberg, U., Oosterlee, C., Schuller, A.: Multigrid. Elsevier Science (2000). https:\/\/books.google.ca\/books?id=9ysyNPZoR24C"},{"issue":"1","key":"9450_CR40","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s11263-006-5631-z","volume":"68","author":"D Tschumperl\u00c9","year":"2006","unstructured":"Tschumperl\u00c9, D.: Fast anisotropic smoothing of multi-valued images using curvature-preserving pde\u2019s. International Journal of Computer Vision 68(1), 65\u201382 (2006). https:\/\/doi.org\/10.1007\/s11263-006-5631-z.","journal-title":"International Journal of Computer Vision"},{"key":"9450_CR41","doi-asserted-by":"publisher","unstructured":"Varah, J.: A lower bound for the smallest singular value of a matrix. Linear Algebra and its Applications 11(1), 3 \u2013 5 (1975). https:\/\/doi.org\/10.1016\/0024-3795(75)90112-3. http:\/\/www.sciencedirect.com\/science\/article\/pii\/0024379575901123","DOI":"10.1016\/0024-3795(75)90112-3"},{"key":"9450_CR42","unstructured":"Varga, R.: Matrix iterative analysis. Prentice-Hall series in automatic computation. Prentice-Hall (1962). https:\/\/books.google.co.uk\/books?id=PFYWAAAAIAAJ"},{"issue":"3","key":"9450_CR43","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1109\/TPAMI.2007.60","volume":"29","author":"Y Wexler","year":"2007","unstructured":"Wexler, Y., Shechtman, E., Irani, M.: Space-time completion of video. IEEE Trans. Pattern Anal. Mach. Intell. 29(3), 463\u2013476 (2007). https:\/\/doi.org\/10.1109\/TPAMI.2007.60","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09450-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-020-09450-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-020-09450-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T07:30:46Z","timestamp":1722583846000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-020-09450-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,16]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["9450"],"URL":"https:\/\/doi.org\/10.1007\/s10208-020-09450-3","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"type":"print","value":"1615-3375"},{"type":"electronic","value":"1615-3383"}],"subject":[],"published":{"date-parts":[[2020,3,16]]},"assertion":[{"value":"11 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}