Description: Highlights • The proposed method automatically assesses the abundance of poly-metallic nodules on the seafloor. • No manually created feature reference set is required. • Large collections of benthic images from a range of acquisition gear can be analysed efficiently. Abstract Underwater image analysis is a new field for computational pattern recognition. In academia as well as in the industry, it is more and more common to use camera-equipped stationary landers, autonomous underwater vehicles, ocean floor observatory systems or remotely operated vehicles for image based monitoring and exploration. The resulting image collections create a bottleneck for manual data interpretation owing to their size. In this paper, the problem of measuring size and abundance of poly-metallic nodules in benthic images is considered. A foreground/background separation (i.e. separating the nodules from the surrounding sediment) is required to determine the targeted quantities. Poly-metallic nodules are compact (convex), but vary in size and appear as composites with different visual features (color, texture, etc.). Methods for automating nodule segmentation have so far relied on manual training data. However, a hand-drawn, ground-truthed segmentation of nodules and sediment is difficult (or even impossible) to achieve for a sufficient number of images. The new ES4C algorithm (Evolutionary tuned Segmentation using Cluster Co-occurrence and a Convexity Criterion) is presented that can be applied to a segmentation task without a reference ground truth. First, a learning vector quantization groups the visual features in the images into clusters. Secondly, a segmentation function is constructed by assigning the clusters to classes automatically according to defined heuristics. Using evolutionary algorithms, a quality criterion is maximized to assign cluster prototypes to classes. This criterion integrates the morphological compactness of the nodules as well as feature similarity in different parts of nodules. To assess its applicability, the ES4C algorithm is tested with two real-world data sets. For one of these data sets, a reference gold standard is available and we report a sensitivity of 0.88 and a specificity of 0.65. Our results show that the applied heuristics, which combine patterns in the feature domain with patterns in the spatial domain, lead to good segmentation results and allow full automation of the resource-abundance assessment for benthic poly-metallic nodules.