We describe a navigation and coverage system based on unsupervised learning driven by visual input. Our objective is to allow a robot to remain continuously moving above a terrain of interest using visual feedback to avoid leaving this region. As a particular application domain, we are interested in doing this in open water, but the approach makes few domain-specific assumptions. Specifically, our system employed an unsupervised learning technique to train a k-Nearest Neighbor classifier to distinguish between images of different terrain types through image segmentation. A simple random exploration strategy was used with this classifier to allow the robot to collect data while remaining confined above a coral reef, without the need to maintain pose estimates. We tested the technique in simulation, and a live deployment was conducted in open water. During the latter, the robot successfully navigated autonomously above a coral reef during a 20 minutes period.