Binary operator design by k‐nearest neighbor learning with application to image resolution increasing

In a typical office environment, heterogeneous devices and software, each working in a different spatial resolution, must interact. As a result resolution conversion problems arise frequently. This paper addresses the spatial resolution increasing of binary images and documents (e.g., conversion of a 300‐dots per inch [dpi] image into 600 dpi). A new, accurate and efficient solution to this problem is proposed. It makes use of the k‐nearest neighbor learning to design automatically a windowed zoom operator starting from pairs of in‐out sample images. The resulting operator is stored in a look‐up table, which is extremely fast computationally and therefore fit for real‐time applications. It is useful to know a priori the sample complexity (the quantity of training samples needed to get, with probability 1‐δ, an operator with accuracy ε). We use the probably approximately correct (PAC) learning theory to compute sample complexity, for both noise‐free and noisy cases. Because the PAC theory yields an overestimated sample complexity, the statistical estimation is used to estimate, a posteriori, a tight error bound. The statistical estimation is also used to show that the k‐nearest neighbor learning has a good inductive bias that allows reduction of the quantity of training sample images needed. © 2001 John Wiley & Sons, Inc. Int J Imaging Syst Technol, 11, 331–339, 2000