Efficient algorithms for recovering watershed boundaries?

Question

This is somewhat related to a previous question I asked: What Algorithm is used by ArcGIS Watershed tool?

I was wondering if there is a more efficient way to calculate catchment areas if you are interested only in the polygon defining the catchment area (rather than all cells contributing to the catchment area). Doing a recursive search seems very expensive and would return a lot of information we don't want (namely each cell within the area).

Assuming the same starting point - a raster grid and a pour point/outlet (I leave it open for now whether the raster is a DEM, Flow Direction or Flow Accumulation).

My first thought was to simply follow the 'steepest path' upstream of the outlet point, which would quickly take us to the 'edge'. But I could not think of a way to follow the 'edge' around.

Are there any other possibilities?

Answer 1

I am not sure that following the boundary will be more efficient than expanding the area. With raster data, you need to account for the number of times that you "go through" the entire image. With a region growing method, each pass will process an increasing number of pixels until you reach the boundary. If you look at the contour only, you might end up with more passes because your neighborhood does not expand.

That being said, to give you a hint for your idea, you could use the definition of a ridge pixel : a pixel which could contribute to more than one watershed. So you can use an edge detection filter to identify the closest pixels to the zero value of the slope, and those would be potential ridges (with holes and artefacts, especially if you don't have a "smooth" DEM, but if you are lucky you can use a threshold to identify your ridges in two passes). Then you link those ridges using some "edge segmentation" methods in order to "close" your polygon. The methods used for edge based segmentation could help you find a solution to the specific case of watershed.