This paper presents two shape descriptors, multiscale fractal dimension and contour saliences, using a graph-based approach-the image foresting transform. It introduces a robust approach to locate contour saliences from the relation between contour and skeleton. The contour salience descriptor consists of a vector, with salience location and value along the contour, and a matching algorithm. We compare both descriptors with fractal dimension, Fourier descriptors, moment invariants, Curvature Scale Space and Beam Angle Statistics regarding to their invariance to object characteristics that belong to a same class (compact-ability) and to their ability to separate objects of distinct classes (separability). (C) 2003 Published by Elsevier Ltd on behalf of Pattern Recognition Society.37611631174