A meaningful affinity measure between pixels is essential for many computer vision and image processing applications. We propose an algorithm that works in the features? histogram to compute image specific affinity measures. We use the observation that clusters in the feature space are typically smooth, and search for a path in the feature space between feature points that is both short and dense. Failing to find such a path indicates that the points are separated by a bottleneck in the histogram and therefore belong to different clusters. We call this new affinity measure the "Bottleneck Geodesic". Empirically we demonstrate the superior results achieved by using our affinities as opposed to those using the widely used Euclidean metric, traditional geodesics and the simple bottleneck.