In this paper we address the development of efficient methods for visual mapping of outdoor environments using exploration and reward identification followed by selective visual coverage. In particular, we consider the problem of visual mapping of a shallow water coral reef to provide an environmental assay. Our approach has two stages based on two classes of sensor: bathymetric mapping and visual mapping. We use a robotic boat to collect bathymetric data using a sonar sensor for the first stage and video data using a visual sensor for the second stage. Since underwater environments have varying visibility, we use the sonar map to select regions of potential value, and we efficiently construct the bathymetric map from sparse data using a Gaussian Process model. In the second stage, we collect visual data only where there is good potential payoff, and we use a reward-driven finite-horizon model akin to a Markov Decision Process to extract the maximum amount of valuable data in the least amount of time. We show that a very small number of sonar readings suffice on a typical fringing reef. We validate and demonstrate our surveying technique using real robot in the presence of real world conditions such as wind and current. We also show that our proposed approach is suitable for visual surveying by presenting a visual collages of the reef.