for regression-based single-image super-resolution (sr) problem, the key is to establish a mapping relation between high-resolution (hr) and low-resolution (lr) image patches for obtaining a visually pleasing quality image. most existing approaches typically solve it by dividing the model into several single-output regression problems, which obviously ignores the circumstance that a pixel within an hr patch affects other spatially adjacent pixels during the training process, and thus tends to generate serious ringing artifacts in resultant hr image as well as increase computational burden. to alleviate these problems, we propose to use structured output regression machine (sorm) to simultaneously model the inherent spatial relations between the hr and lr patches, which is propitious to preserve sharp edges. in addition, to further improve the quality of reconstructed hr images, a nonlocal (nl) self-similarity prior in natural images is introduced to formulate as a regularization term to further enhance the sorm-based sr results. to offer a computation-effective sorm method, we use a relative small nonsupport vector samples to establish the accurate regression model and an accelerating algorithm for nl self-similarity calculation. extensive sr experiments on various images indicate that the proposed method can achieve more promising performance than the other state-of-the-art sr methods in terms of both visual quality and computational cost.