The region graph is based on the region skeleton, and the first step is the skeleton construction. Most thinning procedures repeatedly remove boundary elements until a pixel set with maximum thickness of one or two is found. The following algorithm constructs a skeleton of maximum thickness two. Steps of this algorithm are illustrated in the next Figure. If there are skeleton segments which have a thickness of two, one extra step can be added to reduce those to a thickness of one, although care must be taken not to break the skeleton connectivity.
Mathematical morphology is a powerful tool used to find the region skeleton.
Thinning procedures often use a medial axis transform to construct a region skeleton. Under the medial axis definition, the skeleton is the set of all region points which have the same minimum distance from the region boundary for at least two separate boundary points. The skeleton can be determined as a set of pixels whose distance from the region's border is locally maximal. Small changes in the boundary may cause serious changes in the skeleton. This sensitivity can be removed by first representing the region as a polygon, then constructing the skeleton.