As an addendum to Penelope's answer, two popular families (and trendy) of algorithms.
Superpixels
A very popular family of algorithms called Superpixels is very trendy right now (there are even some Superpixel sessions in CV conferences). Superpixels are a lot like over-segmentation (like what watershed gives you), so some post-processing is required.
Superpixels can be seen as small homogeneous images regions. The distance between pixels is evaluated as in bilateral filtering, i.e., it is a mix between their spatial distance and their visual similarity that goes to 0 when they are close and similar and to some bigger value otherwise.
Then, superpixels methods try various criteria to form small homogeneous regions with respect to this measure. There is many of them (graph-based, mode seeking / clustering based...), so I guess it's best to refer you to this tech report.
(edit:) In case somebody is looking for a published peer-reviewed work, this article is by the same authors and covers the same material as the tech report:
R. Achanta, A. Shaji, K. Smith, A. Lucchi, P. Fua, S. Susstrunk: SLIC Superpixels Compared to State-of-the-Art Superpixel Methods
Note as I wrote the first version of the answer that visually the results is very similar to what watershed over-segmentation provides you. This is confirmed by the authors of the tech report who include watersheds in the related work part. Thus, you also need to do the same post-processing: while superpixels can be handy features to use instead of pixels, they still need to be grouped in order to form higher-level regions if you need to track / detect objects.
Graph based segmentation methods
Another popular family of algorithms comes from the analysis of pixel relationship, i.e., how pixels are close in their appearance. This yields a graph-theory based family of segmentation methods such as the normalized cut (J. Shi, J. Malik: Normalized Cuts and Image Segmentation).
Here is the intuition for this approach: suppose your pixels are now points (vertices) of an high-dimensional graph.
In the graph, two vertices can be connected by an edge, whose weight is inversely proportional to some distance between the vertices. Typically, the weight function will be some reciprocal of a mix between their spatial distance and their visual similarity 8as in bilateral filtering).
Then, given this graph, segmentation algorithms can look for the best clusters of vertices, i.e., groups of vertices that have a small intra-group distance and a large extra-group distance.
In the Normalized Cut approach, some additional care is taken in order to avoid any bias introduced by the different population sizes of the clusters. Furthermore, graph exploration can be avoided by computing the SVD of the weights matrix, also known as connectivity matrix in graph theory.