How to find the centerline line of 2-dimensional long region

How to design a thinning algorithm to find the center-line of a 2-dimensional long region, for instance a river in a geological map? or is there any other method to find the center-line of an irregular 2-dimensional long region?

T开发者_JS百科hanks for any helpful answers.

Try to search for "Skeletonization". Roughly it's extraction of center lines from graphical objects. There are several algorithms for this:

1. gradually remove pixels which are not part of skeleton: http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/azar/skeleton.html#define
2. sending wave from object borders to inside and looking for self-collisions
3. sending wave from some part of the object and looking for middle of wave front

[I made it a separate answer, because approach is too different]

This approach is applicable for rivers without branches:

1. Extract "left" and "right" border as sequences of pixel coordinates
2. Find correspondence between pixels from left and right borders (e.g. with dynamic programming)
3. Define centre line points as middle points between two corresponding left and right points

Edit:

By correspondence I mean sequence of pairs of pixels which goes continuously along both borders keeping distance between them minimal. "Continuously" means that we either do one step along both borders or one step along one of them.

Example of finding such sequence is described here: http://en.wikipedia.org/wiki/Levenshtein_distance