{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:28:02Z","timestamp":1787318882767,"version":"build-2736575974"},"reference-count":59,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Imaging Sci."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>Motivated by a recent halftoning method which is based on electrostatic principles, we analyze a halftoning framework where one minimizes a functional consisting of the difference of two convex functions. One describes attracting forces caused by the image's gray values; the other one enforces repulsion between points. In one dimension, the minimizers of our functional can be computed analytically and have the following desired properties: The points are pairwise distinct, lie within the image frame, and can be placed at grid points. In the two-dimensional setting, we prove some useful properties of our functional, such as its coercivity, and propose computing a minimizer by a forward-backward splitting algorithm. We suggest computing the special sums occurring in each iteration step of our dithering algorithm by a fast summation technique based on the fast Fourier transform at nonequispaced knots, which requires only $\\mathcal{O}(m\\log m)$ arithmetic operations for m points. Finally, we present numerical results showing the excellent performance of our dithering method.<\/jats:p>","DOI":"10.1137\/100790197","type":"journal-article","created":{"date-parts":[[2011,1,25]],"date-time":"2011-01-25T18:06:42Z","timestamp":1295978802000},"page":"79-108","source":"Crossref","is-referenced-by-count":38,"title":["Dithering by Differences of Convex Functions"],"prefix":"10.1137","volume":"4","author":[{"given":"T.","family":"Teuber","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"G.","family":"Steidl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"P.","family":"Gwosdek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Schmaltz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"Weickert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,1,25]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"M. Analoui and J. P. Allebach,\n                      Model-based halftoning using direct binary search\n                      , in Human Vision, Visual Processing, and Digital Display III, Proceedings of the SPIE, Vol. 1666, SPIE, Bellingham, WA, 1992, pp. 96\u2013108.","DOI":"10.1117\/12.135959"},{"key":"R2","unstructured":"J.P. Aubin and H. Frankowska,\n                      Set-Valued Analysis\n                      , Birkh\u00e4user Boston, Boston, 1990."},{"key":"R3","unstructured":"M. Bac\u00e1k and J. M. Borwein,\n                      On Difference Convexity of Locally Lipschitz Functions\n                      , preprint, University of Newcastle, Callaghan, NSW, Australia, 2010."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531392"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2002.806244"},{"key":"R6","unstructured":"M. S. Bartlett,\n                      An Introduction to Stochastic Processes with Special Reference to Methods and Applications\n                      , Cambridge University Press, Cambridge, UK, 1978."},{"key":"R7","unstructured":"B. E. Bayer,\n                      An optimum method for two-level rendition of continuous-tone pictures\n                      , in Conference Record, IEEE International Conference on Communications, Vol. 1, 1973, pp. (26-11)\u2013(26-15)."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R. K. Beatson and G. N. Newsam,\n                      Fast evaluation of radial basis functions.\n                      I, Comput. Math. Appl., 24 (12) (1992), pp. 7\u201319.","DOI":"10.1016\/0898-1221(92)90167-G"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/1618452.1618508"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/040617364"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599352836"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0914081"},{"key":"R13","first-page":"1","volume":"3","author":"Fenn M.","year":"2004","journal-title":"Sampl. Theory Signal Image Process."},{"key":"R14","unstructured":"R. W. Floyd and L. Steinberg,\n                      An adaptive algorithm for spatial greyscale\n                      , in Proceedings of the Society of Information Display, Vol. 17, 1976, pp. 75\u201377."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/151280.151281"},{"key":"R16","unstructured":"R. C. Gonzalez and R. E. Woods,\n                      Digital Image Processing\n                      , Prentice\u2013Hall, Upper Saddle River, NJ, 2008."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1951.tb01365.x"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(87)90140-9"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050015"},{"key":"R20","first-page":"164","volume":"5","author":"Hamdi A.","year":"2005","journal-title":"Appl. Math. E-Notes","ISSN":"https:\/\/id.crossref.org\/issn\/1607-2510","issn-type":"print"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"J.B. Hiriart-Urruty,\n                      Generalized differentiability, duality, and optimization for problems dealing with differences of convex functions\n                      , in Convexity and Duality in Optimization, Lecture Notes in Econom. and Math. Systems 256, Springer, Berlin, 1985, pp. 37\u201370.","DOI":"10.1007\/978-3-642-45610-7_3"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"J.B. Hiriart-Urruty,\n                      From convex optimization to nonconvex optimization. Necessary and sufficient conditions for global optimality\n                      , in Nonsmooth Optimization and Related Topics, Plenum Press, New York, 1989, pp. 219\u2013239.","DOI":"10.1007\/978-1-4757-6019-4_13"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(91)90187-5"},{"key":"R24","unstructured":"P. W. M. Ilbery,\n                      Force Field Halftoning, U.S. Patent\n                      6124844, United States Patent and Trademark Office, Alexandria, VA, 2000."},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/S0146-664X(76)80003-2"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1976.1093397"},{"key":"R27","unstructured":"T. K\u00e4rkk\u00e4inen and S. \u00c4yr\u00e4m\u00f6,\n                      On computation of spatial median for robust data mining\n                      , in Evolutionary and Deterministic Methods for Design, Optimization and Control with Applications to Industrial and Societal Problems, EUROGEN 2005, R. Schilling, W. Haase, J. Periaux, H. Baier, and G. Bugeda, eds., FLM, Munich, 2005, pp. 1\u201314."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056622"},{"key":"R29","unstructured":"K. T. Knox,\n                      Edge enhancement in error diffusion\n                      , in Advance Printing of Paper Summaries, SPSE's 42nd Annual Conference, Boston, 1989, pp. 310\u2013313."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1145\/35039.35040"},{"key":"R31","unstructured":"T. Kolling and A. Keller,\n                      Efficient illumination by high dynamic range images\n                      , in Proceedings of the 14th Eurographics Workshop on Rendering, ACM International Conference Proceeding Series 44, Eurographics Association, Geneva, Switzerland, 2003, pp. 45\u201350."},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.4.597"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.4310\/CMS.2009.v7.n3.a11"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF00935173"},{"key":"R36","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization. A Basic Course\n                      , Kluwer Academic Publishers, Boston, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/040619582"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"V. Ostromoukhov,\n                      A simple and efficient error-diffusion algorithm\n                      , in SIGGRAPH '01, Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, E. Fiume, ed., Los Angeles, ACM, New York, 2001, pp. 567\u2013572.","DOI":"10.1145\/383259.383326"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360688"},{"key":"R40","first-page":"287","volume":"22","author":"Dinh T. Pham","year":"1997","journal-title":"Acta Math. Vietnam."},{"key":"R41","doi-asserted-by":"crossref","unstructured":"T. Pham Dinh and E. B. Soaud,\n                      Algorithms for solving a class of nonconvex optimization problems: Methods of subgradients\n                      , in Fermat Days 85: Mathematics for Optimization, North\u2013Holland Math. Stud. 129, Elsevier, Amsterdam, 1986, pp. 249\u2013270.","DOI":"10.1016\/S0304-0208(08)72402-2"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-004-0538-5"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"D. Potts, G. Steidl, and M. Tasche,\n                      Fast Fourier transforms for nonequispaced data: A tutorial\n                      , in Modern Sampling Theory: Mathematics and Applications, J. J. Benedetto and P. J. S. G. Ferreira, eds., Birkh\u00e4user Boston, Boston, 2001, pp. 247\u2013270.","DOI":"10.1007\/978-1-4612-0143-4_12"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"W. Purgathofer, R. F. Tobler, and M. Geiler,\n                      Forced random dithering: Improved threshold matrices for ordered dithering\n                      , in Proceedings of 1st IEEE International Conference on Image Processing, Vol. 2, Austin, TX, 1994, pp. 1032\u20131035.","DOI":"10.1109\/ICIP.1994.413512"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2010.01716.x"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"A. Secord,\n                      Weighted Voronoi stippling\n                      , in Proceedings of the 2nd International Symposium on Non-Photorealistic Animation and Rendering, ACM Press, New York, 2002, pp. 37\u201343.","DOI":"10.1145\/508530.508537"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.2.001009"},{"key":"R48","unstructured":"P. Stucki,\n                      MECCA\u2014a Multiple-Error Correcting Computation Algorithm for Bilevel Hardcopy Reproduction\n                      , Technical report RZ1060, IBM Research Lab, Z\u00fcrich, Switzerland, 1981."},{"key":"R49","first-page":"451","volume":"21","author":"Sun W.","year":"2003","journal-title":"J. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0254-9409","issn-type":"print"},{"key":"R50","unstructured":"V. Surazhsky, P. Alliez, and C. Gotsman,\n                      Isotropic remeshing of surfaces: A local parameterization approach\n                      , in Proceedings of the 12th International Meshing Roundtable, Sandia National Laboratories, Santa Fe, NM, 2003, pp. 215\u2013224."},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1007\/BF00250669"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1007\/BF02575706"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"R. Ulichney,\n                      Digital Halftoning\n                      , MIT Press, Cambridge, MA, 1987.","DOI":"10.7551\/mitpress\/2421.001.0001"},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1109\/5.3288"},{"key":"R55","unstructured":"D. Vanderhaeghe and V. Ostromoukhov,\n                      Polyomino-based digital halftoning\n                      , in Proceedings of the IADIS International Conference on Computer Graphics and Visualization, P. Isa\u00edas, ed., 2008, pp. 11\u201318."},{"key":"R56","doi-asserted-by":"crossref","unstructured":"L. Velho, A. C. Frery, and J. Gomes,\n                      Image Processing for Computer Graphics and Vision\n                      , Springer, London, 2009.","DOI":"10.1007\/978-1-84800-193-0"},{"key":"R57","first-page":"355","volume":"43","author":"Weiszfeld E.","year":"1937","journal-title":"T\u00f4hoku Math. J.","ISSN":"https:\/\/id.crossref.org\/issn\/0040-8735","issn-type":"print"},{"key":"R58","unstructured":"W. I. Zangwill,\n                      Nonlinear Programming: A Unified Approach\n                      , Prentice\u2013Hall, Englewood Cliffs, NJ, 1969."},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882289"}],"container-title":["SIAM Journal on Imaging Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100790197","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:43:07Z","timestamp":1787316187000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100790197"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100790197"],"URL":"https:\/\/doi.org\/10.1137\/100790197","relation":{},"ISSN":["1936-4954"],"issn-type":[{"value":"1936-4954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}