Landmark-based navigation in unknown unstructured environments is far from solved. The bottleneck nowadays seems to be the fast detection of reliable visual references in the image stream as the robot moves. In our research, we have decoupled the navigation issues from this visual bottleneck, by first using artificial landmarks that could be easily detected and identified. Once we had a navigation system working, we developed a strategy to detect and track salient regions along image streams by just performing on-line pixel sampling. This strategy continuously updates the mean and covariances of the salient regions, as well as creates, deletes and merges regions according to the sample flow. Regions detected as salient can be considered as potential landmarks to be used in the navigation task.