Abstract <p>In this article, for a sequential number of brightness gradations, the problem of exact calculation of <i>optimal</i> approximations of a halftone image that differ from the image in the minimum values of the total square error is investigated. To establish the patterns inherent in the input data domain under discussion, a standard halftone image is analyzed, the optimal approximations of which are known. The concept is formalized of <i>structures</i> of a multiset of pixels defined by approximations that, depending on the number of gradations, are described by a convex sequence of values of the total square error. A visual representation of the optimal image structure is constructed, which demonstrates that it is not random and also suggests recurrent algorithms for the high-speed generation of most optimal image approximations using Otsu’s multithreshold method applied to pixel associations from adjacent brightness ranges.</p>