We present the BossaNova scheme for the ImageCLEF 2012 Flickr Photo Annotation Task. BossaNova is a mid-level image representation, recently developed by our team, that enriches the Bag-of-Words representation, by keeping a histogram of distances between the descriptors found in the image and those in the codebook. Our scheme has the advantage of being conceptually simple, non-parametric, and easily adaptable. Compared to other schemes existing in the literature to add information to the Bag-of-Words model, it leads to much more compact representations. Furthermore, it complements well the cutting-edge Fisher Vector representations, showing even better results when employed in combination with them. In our participation, we submitted four purely visual runs. Our best result (MiAP = 34.37%) achieved the second rank by MiAP measure among the 28 purely visual submissions and the 18 teams.