In this paper, we investigate image segmentation as a statistical and computa- tional problem. The observed image is sampled from a theoretical, unknown image, in which pixels are represented by distributions. Our objective is to approximate as best as possible the region segmentation in the ideal image, where each region has pixels with identical expectations, but adjacent regions have different pixel’s expectations. From that model, a concentration-based statistical test for deciding region merging is built, limiting the risk of wrong merges. The analysis is carried out without any assumption on the distribu- tions: we avoid in particular the classics of variance analysis, normality and homocedasticity. A practical approximation of the test is given, of constant time and space computation, which leads in turn to a segmentation algorithm of optimal complexity, easy to implement. Some experiments on various types of images shed light on the quality of the segmentations obtained.