The present invention concerns a method of segmenting a media item comprising media elements. The method comprises: selecting a first seed media element for a first cluster of media elements, referred to hereinafter as a first adaptel; selecting a second seed media element, different from the first seed media element, for a second cluster of media elements, different from the media elements of the first adaptel, the second cluster being referred to hereinafter as a second adaptel; successively forming the first and second adaptels, starting from the first and second seed media elements, respectively, by allocating a first plurality of the media elements to the first adaptel, and then allocating a second plurality of the media elements to the second adaptel; and reallocating at least one media element of the first adaptel to the second adaptel if a dissimilarity measure between the at least one media element and the second adaptel is smaller than the dissimilarity measure between the at least one media element and the first adaptel. The second seed media element is selected from a set of the media elements neighboring the first adaptel.