We study the problem of reconstructing small objects from their low-resolution images, by modelling them as r-regular objects. Previous work shows how the boundary constraints imposed by r-regularity allows bounds on estimation error for noise-free images. In order to utilize this for noisy images, this paper presents a graph-based framework for reconstructing noise-free images from noisy ones. We provide an optimal, but potentially computationally demanding algorithm, as well as a greedy heuristic for reconstructing noise-free images of r-regular objects from images with noise.