This thesis is divided into two parts. Both cope with multi-class image segmentation and utilize non-smooth optimization algorithms. The topic of the first part, namely unsupervised segmentation, is the application of clustering to image pixels. Therefore, we start with an introduction of the biconvex center-based clustering algorithms c-means and fuzzy c-means, where c denotes the number of classes. We show that fuzzy c-means can be seen as an approximation of c-means in terms of power means. Since noise is omnipresent in our image data, these simple clustering models are not suitable for its segmentation. To this end, we introduce a general and finite dimensional segmentation model that consists of a data term stemming from the aforementioned clustering models plus a continuous regularization term. We tackle this optimization model via an alternating minimiza- tion approach called regularized c-centers (RcC). Thereby, we fix the centers and optimize the segment membership of the pixels and vice versa. In this general setting, we prove convergence in the sense of set-valued algorithms using Zangwill’s Theory [172]. Further, we present a segmentation model with a total variation regularizer. While updating the cluster centers is straightforward for fixed segment memberships of the pixels, updating the segment membership can be solved iteratively via non-smooth, convex optimization. Thereby, we do not iterate a convex optimization algorithm until convergence. Instead, we stop as soon as we have a certain amount of decrease in the objective functional to increase the efficiency. This algorithm is a particular implementation of RcC providing also the corresponding convergence theory. Moreover, we show the good performance of our method in various examples such as simulated 2d images of brain tissue and 3d volumes of two materials, namely a multi-filament composite superconductor and a carbon fiber reinforced silicon carbide ceramics. Thereby, we exploit the property of the latter material that two components have no common boundary in our adapted model. The second part of the thesis is concerned with supervised segmentation. We leave the area of center based models and investigate convex approaches related to graph p-Laplacians and reproducing kernel Hilbert spaces (RKHSs). We study the effect of different weights used to construct the graph. In practical experiments we show on the one hand image types that are better segmented by the p-Laplacian model and on the other hand images that are better segmented by the RKHS-based approach. This is due to the fact that the p-Laplacian approach provides smoother results, while the RKHS approach provides often more accurate and detailed segmentations. Finally, we propose a novel combination of both approaches to benefit from the advantages of both models and study the performance on challenging medical image data.