Automatic segmentation and analysis of ancient mosaic images can help archaeologists and experts build digital collections and automatically compare mosaics by means of image database indexing and content-based retrieval tools. However, ancient mosaics are characterized by low contrast colors and irregular tessella shape, orientation, and positioning, making automatic segmentation difficult. We propose a tessella-oriented strategy whose first step consists of isolating tessellas from their cemented network by computing the watershed transformation of a criterion image generated to exhibit the cement network as watershed crests. Then a simple k-means algorithm is used to classify tessellas and segment mosaic images with more accuracy than with a pixel-oriented strategy. Additionally, we propose a method to automatically obtain the main directional guidelines of mosaics by estimating tessella orientation. This is done by minimizing a contextual energy computed from gray-level means of neighboring tessellas and the orientation of their borders. Several examples of cartographies show the effectiveness of the method.