# US 11,443,435 B2 · Watershed segmentation in civil engineering > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,443,435 B2 - Document ID: US11443435B2 - Status: Granted - Kind: B2 - Application number: 17/107,032 - Filed: 2020-11-30 - Published: 2021-06-03 - Granted: 2022-09-13 - Earliest claimed: 2019-11-28 - Assignees: Dassault Systemes - Applicants: Dassault Systemes - Inventors: Nicolas Montana; Andre Lieutier; Marc Monteil - Web page: https://patentgrep.com/patent/US11443435B2 ## CPC - G06T 7/11: Region-based segmentation - G06T 7/155: involving morphological operators - G06T 7/187: involving region growing; involving region merging; involving connected component labelling - G06T 17/05: Geographic models - G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation} - G06T 2207/20072: Graph-based image processing - G06T 2207/20152: Watershed segmentation - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract Computer-implemented method for civil engineering including obtaining a mesh representing a terrain and computing a watershed segmentation of the terrain based on the mesh, the computing of the watershed segmentation including identifying one or more saddle points on the mesh, for each identified saddle point, identifying paths each ascending from the saddle point according to a direction of a local maximal slope around the saddle point, and a path descending from the saddle point according to a direction of a steepest slope around the saddle point, the identified ascending paths dividing the mesh into connected components, and, for each identified saddle point, merging each connected component of which bottom point is the saddle point with a connected component including the identified path descending from the saddle point according to a direction of a steepest slope. The merging yields at least a part of a basin. ## Claims ### Claim 1 A computer-implemented method for civil engineering, the method comprising: obtaining a mesh representing a real-world terrain; and computing a watershed segmentation of the terrain based on the mesh, the computing of the watershed segmentation including: identifying one or more saddle points on the mesh, for each identified saddle point, identifying: paths each ascending from the saddle point according to a direction of a local maximal slope around the saddle point, and a path descending from the saddle point according to a direction of a steepest slope around the saddle point, the identified ascending paths dividing the mesh into connected components each bounded by two identified ascending paths, each connected component correspond either to a connected part of the terrain having the saddle point as bottom and on which water flows towards the saddle point, or to a connected part of the terrain forming a steepest valley descending from the saddle point, and for each identified saddle point, merging each connected component of which bottom point is the saddle point with a connected component including the identified path descending from the saddle point according to a direction of a steepest slope around the saddle point, the merging yielding at least a part of a drainage basin bounded by watershed lines that divide water flow so that any pair of points lying from either side of the watershed lines gives rise to two paths that reach two different basin outlets. ### Claim 2 (depends on 1) The method of claim 1, wherein the identifying of the paths ascending from the saddle point comprises determining slope local maxima around the saddle point, each respective one of said paths ascending from the saddle point being directed according to a determined slope local maxima. ### Claim 3 (depends on 2) The method of claim 2, wherein the determined slope local maxima around the saddle point are local maxima of a radial slope around the saddle point. ### Claim 4 (depends on 3) The method of claim 3, wherein the identifying of the paths ascending from the saddle point comprises projecting mesh elements including the saddle point onto a plane, the radial slope around the saddle point being a function of a direction angle around a projection of the saddle point in the plane. ### Claim 5 (depends on 4) The method of claim 4, wherein the identifying of the paths ascending from the saddle point comprises, for each mesh element including the saddle point and including at least two local maxima of the radial slope, retrieving, among couples of local maxima of the at least two local maxima of the radial slope, a couple of local maxima of which directions form a maximal angle in the projection of the mesh element, the respective directions of the local maxima of the couple yielding one of said connected components. ### Claim 6 (depends on 5) The method of claim 5, wherein the retrieving of the couple forming the maximal angle comprises retrieving a first local maxima of the radial slope and a last maxima of the radial slope according to a trigonometric order or to an anti-trigonometric order in the projection of the mesh element. ### Claim 7 (depends on 1) The method of claim 1, wherein the identifying of the path descending from the saddle point comprises computing a slope global minimum around the saddle point. ### Claim 8 (depends on 7) The method of claim 7, wherein the slope global minimum is a global minimum of a radial slope around the saddle point. ### Claim 9 (depends on 1) The method of claim 1, wherein the merging includes: determining a graph having nodes each representing a connected component and arcs each representing a connection between two connected components, and extracting the connected components of the graph, each connected component of the graph representing a basin of the terrain. ### Claim 10 (depends on 9) The method of claim 9, wherein each node representing a connected component having a saddle point as a bottom point is connected by an arc in the graph to a node representing a connected component of the mesh that is located below the saddle point and that comprises the identified path descending from the saddle point according to a direction of a steepest slope around the saddle point. ### Claim 11 (depends on 1) The method of claim 1, wherein at least one of the identified one or more saddle points is a degenerate saddle point. ### Claim 12 (depends on 1) The method of claim 1, wherein the terrain is a construction terrain. ### Claim 13 (depends on 1) The method of claim 1, further comprising displaying a visualization of the computed watershed segmentation of the real-world terrain. ### Claim 14 A device comprising: a processor; and a non-transitory data storage medium having recorded thereon a computer program comprising instructions that when executed by the processor causes the processor to be configured to: obtain a mesh representing a real-world terrain, and compute a watershed segmentation of the terrain based on the mesh, the computing of the watershed segmentation including the processor being further configured to: identify one or more saddle points on the mesh; and for each identified saddle point, identify: paths each ascending from the saddle point according to a direction of a local maximal slope around the saddle point, and a path descending from the saddle point according to a direction of a steepest slope around the saddle point, the identified ascending paths dividing the mesh into connected components each bounded by two identified ascending paths, each connected component correspond either to a connected part of the terrain having the saddle point as bottom and on which water flows towards the saddle point, or to a connected part of the terrain forming a steepest valley descending from the saddle point, and for each identified saddle point, merge each connected component of which bottom point is the saddle point with a connected component including the identified path descending from the saddle point according to a direction of a steepest slope around the saddle point, the merging yielding at least a part of a drainage basin bounded by watershed lines that divide water flow so that any pair of points lying from either side of the watershed lines gives rise to two paths that reach two different basin outlets. ### Claim 15 (depends on 14) The device of claim 14, wherein the processor is further configured to identify the paths ascending from the saddle point by being configured to determine slope local maxima around the saddle point, each respective one of said paths ascending from the saddle point being directed according to a determined slope local maxima. ### Claim 16 (depends on 15) The device of claim 15, wherein the determined slope local maxima around the saddle point are local maxima of a radial slope around the saddle point. ### Claim 17 (depends on 16) The device of claim 16, wherein the processor is further configured to identify the paths ascending from the saddle point by being configured to project mesh elements including the saddle point onto a plane, the radial slope around the saddle point being a function of a direction angle around a projection of the saddle point in the plane. ### Claim 18 A non-transitory data storage medium having recorded thereon a computer program comprising instructions that when executed by a computer causes the computer to implement a method for civil engineering, the method comprising: obtaining a mesh representing a real-world terrain; and computing a watershed segmentation of the terrain based on the mesh, the computing of the watershed segmentation including: identifying one or more saddle points on the mesh, for each identified saddle point, identifying: paths each ascending from the saddle point according to a direction of a local maximal slope around the saddle point, and a path descending from the saddle point according to a direction of a steepest slope around the saddle point, the identified ascending paths dividing the mesh into connected components each bounded by two identified ascending paths, each connected component correspond either to a connected part of the terrain having the saddle point as bottom and on which water flows towards the saddle point, or to a connected part of the terrain forming a steepest valley descending from the saddle point, and for each identified saddle point, merging each connected component of which bottom point is the saddle point with a connected component including the identified path descending from the saddle point according to a direction of a steepest slope around the saddle point, the merging yielding at least a part of a drainage basin bounded by watershed lines that divide water flow so that any pair of points lying from either side of the watershed lines gives rise to two paths that reach two different basin outlets.