The primary goal of this thesis is to develop robust image segmentation methods based on variational techniques. Image segmentation is one of the fundamental problems in image processing and computer vision. Segmentation is also one of the first steps in many image analysis tasks. Image understanding systems such as face or object recognition often assume that the objects of interests are well segmented. Different visual cues, such as color, texture, and motion, help in achieving segmentation. Segmentation is also goal dependent, subjective, and hence ill-posed in a general set up. However, it is desirable to consider generic criteria that can be applied to a large variety of images and can be adapted for specific applications. This thesis work focuses on developing such segmentation methods that work on natural images. The first part of the dissertation proposes new designs for edge-based variational segmentation methods. Starting with the Edgeflow technique, which has been shown to be highly successful on natural images, two edge-based variational methods, a curve evolution method and an anisotropic diffusion method, are proposed. To verify the effectiveness of these new techniques, extensive tests are conducted on the Berkeley segmentation data set and associated ground truth. The results show that our methods outperform the current state of the art. These methods are further extended to multi-scale image segmentation. Second part of the dissertation explores region-based variational segmentation. We propose a new class of variational segmentation cost functions. Our cost functions are based on pair-wise dissimilarities between individual pixels and have been successfully applied to natural images by graph partitioning techniques. We minimize these cost functions within a variational framework. We refer to our work as graph partitioning active contours (GPAC). Such cost functions have been widely used within the graph partitioning framework but their minimization usually requires certain simplifications, which introduce inaccuracies to the final segmentation. By minimizing pair-wise similarity based cost functions using GPAC, we are able to achieve better segmentation results. Efficient implementations of GPAC are proposed. Finally we show an application in which we use GPAC for pruning categories in large image databases.