In this paper we present an efficient method for visual mapping of open water environments using exploration and reward identification followed by selective visual coverage. In particular, we consider the problem of visual mapping a shallow water coral reef to provide an environmental assay. Our approach has two stages based on two classes of sensors: 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 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 pay-off, 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 collage of the reef.