A new thinning algorithm for gray-scale images based on the relaxation technique is proposed. Thinning is treated as a process of assigning each picture point to either a skeleton or a nonskeleton category so that relaxation can be used to perform thinning. Contextual information existing in input data is utilized in the thinning process so that line straightness can be preserved. Five classes are created to classify each point, with four classes belonging to the skeleton category for different orientations and one to the nonskeleton category. An initial probability value for assigning a point to each class is computed first. In the relaxation process, interactions take place among the probability values of neighbouring points, making the skeleton probability values of the points in compatible orientations to enhance one another. The probability value for each point to belong to the nonskeleton class of each point is also refined according to the point type. The relaxation process is terminated when it converges to a condition in which points lying on skeletons achieve high skeleton probability values, while other points have unity nonskeleton probability values. Experimental results show that the proposed approach produces good thinning results in keeping line straightness.