{"id":259,"date":"2009-05-08T07:00:50","date_gmt":"2009-05-08T11:00:50","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2009\/05\/08\/continental-divide-3-regmin\/"},"modified":"2019-10-28T15:31:47","modified_gmt":"2019-10-28T19:31:47","slug":"continental-divide-3-regmin","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2009\/05\/08\/continental-divide-3-regmin\/","title":{"rendered":"Locating the US continental divide, part 3 – Regional minima"},"content":{"rendered":"
\r\n

In the previous post in this series<\/a> on computing the US continental divide, we used the watershed<\/tt> function to find catchment basins in a DEM (digital elevation model). The result was more than half a million catchment basins,\r\n most of which were tiny and looked something like this:\r\n <\/p>\r\n

<\/p>\r\n

Why so many?<\/p>\r\n

To answer this question, let's look at a different kinds of minima<\/i> in image processing. A local minimum<\/i> is usually defined as a pixel that is less than or equal to all its neighbors. In a one-dimensional example:\r\n <\/p>

a = [3 2 1 1 1 2 3 4 3 5 6]<\/pre>
\r\na =\r\n\r\n     3     2     1     1     1     2     3     4     3     5     6\r\n\r\n<\/pre>
the third, fourth, fifth, and nineth elements are local minima.  A convenient way to find local minima is to use morphological\r\n      erosion:\r\n   <\/p>
imerode(a, [1 1 1]) == a<\/pre>
\r\nans =\r\n\r\n     0     0     1     1     1     0     0     0     1     0     0\r\n\r\n<\/pre>
Now find the local minima in this example:<\/p>
b = [2 1 1 2 3 4 4 4 5 6]<\/pre>
\r\nb =\r\n\r\n     2     1     1     2     3     4     4     4     5     6\r\n\r\n<\/pre>
imerode(b, [1 1 1]) == b<\/pre>
\r\nans =\r\n\r\n     0     1     1     0     0     0     1     1     0     0\r\n\r\n<\/pre>
Now, if you are thinking about the watershed transform and identifying catchment basins, I think you'll agree there's an important\r\n      distinction between the two groups of local minima (the 1-valued elements and the 4-valued elements) found in b<\/tt>.  Water would not accumulate on the flat spot, or plateau, represented by the 4-valued elements; it would instead flow downhill\r\n      to the left.\r\n   <\/p>\r\n   
That thought leads us to the definition of a regional minimum<\/i>: a connected group of pixels from which you cannot travel further downhill without going uphill first.  The 1-valued elements\r\n      in b<\/tt> form a regional minima, but the 4-valued elements in b<\/tt> do not.\r\n   <\/p>\r\n   
The Image Processing Toolbox function imregionalmin<\/tt> locates regional minima for you:\r\n   <\/p>
imregionalmin(b)<\/pre>
\r\nans =\r\n\r\n     0     1     1     0     0     0     0     0     0     0\r\n\r\n<\/pre>
Let's connect that back to the watershed transform. Every regional minimum is a collection point for water flowing downhill.\r\n      Thus, there's a one-to-one correspondence between regional minima and catchment basins found by the watershed transform.\r\n   <\/p>\r\n   
Here are all the regional minima pixels in the zoomed-in portion of the DEM that we looked at previously.<\/p>
% The file continental_divide.mat was created in an earlier post.<\/span>\r\ns = load('continental_divide'<\/span>);\r\ndem = s.dem_cropped;\r\nreg_min = imregionalmin(dem);\r\nimshow(reg_min, 'InitialMagnification'<\/span>, 'fit'<\/span>);\r\naxis([5580 5670 2060 2100])<\/pre> 
We can count the number of regional minima by doing connected-component labeling on the output of imregionalmin<\/tt>.\r\n   <\/p>
reg_min_labeled = bwlabel(reg_min);\r\nmax(reg_min_labeled(:))<\/pre>
\r\nans =\r\n\r\n      540976\r\n\r\n<\/pre>
That's the same as the number of catchment basins we found in the previous post.<\/p>\r\n   
We're on our way to computing just two catchment basins, one for the Pacific Ocean and one for the Atlantic Ocean.  Next time\r\n      we'll take a closer look at the ocean pixels in this data set.\r\n   <\/p>\r\n   
About this Series<\/i><\/p>\r\n   
This series<\/a> explores the problem of computing the location of the continental divide for the United States.  The divide separates the\r\n      Atlantic and Pacific Ocean catchment basins for the North American continent.\r\n   <\/p>\r\n   
As an algorithm development problem, computing the divide lets us explore aspects of data import and visualization, manipulating\r\n      binary image masks, label matrices, regional minima, and the watershed transform.\r\n   <\/p>\r\n   
\r\n