An appearance-based approach for topological visual mapping and localization using local invariant features is proposed in this paper. To optimize running times, matchings between the current image and previous visited places are determined using an index based on a set of randomized KD-trees. A discrete Bayes filter is used for predicting loop candidates, whose observation model is a novel approach based on an efficient matching scheme between features. In order to avoid redundant information in the resulting maps, in this work, we also present a map refinement framework, which takes into account the visual information stored in the map for refining the final topology of the environment. These refined maps save storage space and improve the execution times of localizations tasks. The approach has been validated using image sequences from several environments.