{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,16]],"date-time":"2026-11-16T10:41:52Z","timestamp":1794825712245,"version":"4.9.1"},"reference-count":49,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GR 993\/10-2"],"award-info":[{"award-number":["GR 993\/10-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000921","name":"European Cooperation in Science and Technology","doi-asserted-by":"publisher","award":["MP1207"],"award-info":[{"award-number":["MP1207"]}],"id":[{"id":"10.13039\/501100000921","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Superresolution imaging aims at improving the resolution of an image by enhancing it with other images or data that might have been acquired using different imaging techniques or modalities. In this paper we consider the task of doubling, in each dimension, the resolution of grayscale images of binary objects by fusion with double-resolution tomographic data that have been acquired from two viewing angles. We show that this task is polynomial-time solvable if the gray levels have been reliably determined. The problem becomes ${N}{P}$-hard if the gray levels of some pixels come with an error of $\\pm1$ or larger. The ${N}{P}$-hardness persists for any larger resolution enhancement factor. This means that noise does not only affect the quality of a reconstructed image but, less expectedly, also the algorithmic tractability of the inverse problem itself.<\/jats:p>","DOI":"10.1137\/17m1115629","type":"journal-article","created":{"date-parts":[[2018,6,14]],"date-time":"2018-06-14T12:53:05Z","timestamp":1528980785000},"page":"1369-1399","source":"Crossref","is-referenced-by-count":6,"title":["On Double-Resolution Imaging and Discrete Tomography"],"prefix":"10.1137","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0663-6037","authenticated-orcid":true,"given":"Andreas","family":"Alpers","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0157-6880","authenticated-orcid":true,"given":"Peter","family":"Gritzmann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,6,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09741"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1080\/14786435.2015.1015469"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ultramic.2013.01.002"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/040617443"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2017-1588"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6420\/aaa202"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2014.10.022"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1107\/S002188980601939X"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"M. Bertero and P. Boccacci,\n                      Introduction to Inverse Problems in Imaging\n                      , IOP, Philadelphia, 1998.","DOI":"10.1887\/0750304359"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1111\/ene.13173"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"R.A. Brualdi,\n                      Combinatorial Matrix Classes\n                      , Cambridge University Press, Cambridge, 2006.","DOI":"10.1017\/CBO9780511721182"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1023\/B:JMIV.0000011325.36760.1e"},{"key":"atypb13","first-page":"151","author":"Cook S.A.","year":"1971","journal-title":"New York"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/15M1021404"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/100799733"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1957.7.1073"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-97-01741-8"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00347-1"},{"key":"atypb19","unstructured":"M.R. Garey and D.S. Johnson,\n                      Computers and Intractability\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"atypb20","first-page":"816","author":"Gompel G. Van","year":"2010","journal-title":"NJ"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0703-7"},{"key":"atypb22","first-page":"19","author":"Gritzmann P.","year":"1997","journal-title":"Berlin"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/100803262"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"P.C. Hansen,\n                      Discrete Inverse Problems: Insights and Algorithms\n                      , Fundam. Algorithms 7, SIAM, Philadelphia, 2010.","DOI":"10.1137\/1.9780898718836"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"G.T. Herman and A. Kuba, eds.\n                      Discrete Tomography: Foundations, Algorithms and Applications\n                      , Birkha\u0308user, Boston, 1999.","DOI":"10.1007\/978-1-4612-1568-4"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"G.T. Herman and A. Kuba, eds.\n                      Advances in Discrete Tomography and its Applications\n                      , Birkha\u0308user, Boston, 2007.","DOI":"10.1007\/978-0-8176-4543-4"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.ultramic.2014.01.013"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790191010"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1109\/TMI.2005.861705"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3991(94)00202-X"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-1098(1998)9:2\/3<118::AID-IMA8>3.0.CO;2-E"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.3934\/ipi.2009.3.69"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/15M1020459"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1364\/BOE.8.000193"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1109\/TMI.2005.862151"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1002\/cmmi.393"},{"key":"atypb37","unstructured":"P. Milanfar, ed.\n                      Super-Resolution Imaging\n                      , CRC Press, Boca Raton, FL, 2010."},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"J.L. Mueller and S. Siltanen,\n                      Linear and Nonlinear Inverse Problems with Practical Applications\n                      , Comput. Sci. Eng. 10, SIAM, Philadelphia, 2012.","DOI":"10.1137\/1.9781611972344"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1107\/S1600577516017756"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1107\/S0021889807001288"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1957-044-3"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1088\/0266-5611\/8\/1\/010"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1063\/1.4872378"},{"key":"atypb44","unstructured":"A. Schrijver,\n                      Theory of Linear and Integer Programming\n                      , Wiley, Chichester, UK, 1986."},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.71.4150"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1038\/nature10934"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1118\/1.3560887"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2013.2297025"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1063\/1.4906928"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1115629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:18Z","timestamp":1787317578000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1115629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1115629"],"URL":"https:\/\/doi.org\/10.1137\/17m1115629","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}