Disclosed is an image processing apparatus and a method of operating the same. The image processing apparatus includes: a memory storing information on at least one random patch; and at least one processor configured to: obtain correlations between a pixel block included in an input image and each of a plurality of random patches obtained from the information on the at least one random patch, obtain weights respectively for the plurality of random patches on a basis of the obtained correlations and apply the weights respectively to the plurality of random patches, and obtain an output image by applying, to the pixel block, the plurality of random patches to which the weights are respectively applied.