Most research works focus on pattern recognition within a small sample images but strategies for running efficiently these algorithms over large images are rarely if ever specifically considered. In particular, the new generation of satellite and microscopic images are acquired at a very high resolution and a very high daily rate. We propose an efficient, generic strategy to explore large images by combining computational geometry tools with a local signal measure of relevance in a dynamic sampling framework. An application to breast cancer grading from huge histopathological images illustrates the benefit of such a general strategy for new major applications in the field of microscopy. © 2010 IEEE.