In this paper we describe a time efficient approach for computing the (3,4) distance transform and a method of producing intuitively well-shaped nonsensitive skeletons. The need and usefulness of abstracting both skeletal and distance transform information have been demonstrated in various earlier work. However, the approach presented here is intended to overcome several weaknesses while possibly permitting real-time computation on low-cost single or multiprocessor systems for applications such as video processing. Specifically, an incremental improvement to Kwok’s thinning algorithm is presented which allows the distance transform to be computed during thinning using significantly fewer addition and comparison operations. Additionally, efficient techniques are given which then further process the resultant skeleton using the computed distance transform information as well as information gathered about the surrounding chain codes. These techniques efficiently remove various skeletal artifacts, leaving well-shaped graph representations annotated with distance transform values.