We propose an algorithm for generating naviga- tion summaries. Navigation summaries are a specialization of video summaries, where the focus is on video collected by a mobile robot, on a specified trajectory. We are interested in finding a few images that epitomize the visual experience of a robot as it traverse a terrain. This paper presents a novel approach to generating summaries in form of a set of images, where the decision to include the image in the summary set is made online. Our focus is on the case where the number of observations is infinite or unknown, but the size of the desired summary is known. Our strategy is to consider the images in the summary set as the prior hypothesis of the appearance of the world, and then use the idea of Bayesian Surprise to compute the novelty of an observed image. If the novelty is above a threshold, then we accept the image. We discuss different criterion for setting this threshold. Online nature of our approach allows for several interesting applications such as coral reef inspection, surveying, and surveillance.