Calculate and return a polygon based on the vds trace mask

[ErlendHaa]

The polygon of the bounding box of the volume is trivially available as metadata in the vds through entries such as origin, rotation, spacing and number of samles.

More useful however, might be the the polygon of the trace mask. I.e. where the volume contains data. This would include cut of edges and corners in irregular sized cubes as well as holes.

This should be and entry in the /metadata endpoint. The representation should match common polygon representation for easy integrations with other formats. E.g. PostGis defines them like this:

'Polygon', 'POLYGON((0 0, 1 0, 1 1, 0 1, 0 0))',
'PolygonWithHole', 'POLYGON((0 0, 10 0, 10 10, 0 10, 0 0),(1 1, 1 2, 2 2, 2 1, 1 1))',

For us a list of points might make more sense than a string, but we can reuse the shape.

[ajaust]

Summary

I did some research into different algorithms and libraries. However, at the moment we cannot implement the feature as we want. As the OpenVDS documentation states about name channels [(Trace channel in our case)](https://osdu.pages.opengroup.org/platform/domain-data-mgmt-services/seismic/open-vds/vds/specification/Metadata.html#named-channels

Trace is a bool-mask if trace was present or not during conversion

In our case all traces are present during the conversion. This means the trace mask is full of ones in our case. This makes is unfeasible at the moment to extract a bounding polygon around the existing data, i.e., points were data is typically different from the "no Value".

Below I summarize some results of the research about edge/contour tracing, polygon reconstruction and polygon formats.

Accessing trace mask in OpenVDS

If one accesses the trace mask (Trace channel) via OpenVDS's Python channel, it behaves as for any other channel. If not retrieves the Trace channel via the C++ interface, one will receive packed 1-bit values. This means one has to use the RequestVolumeSubset1Bit function of the VolumeDataAccessManager which returns an array of uint8_t with 8 bits within each unsigned int. OpenVDS provides the function OpenVDS::ReadElement<bool> to unpack such values.

Note that the bit mask will always contain a number of bits that is a multiple of 8 (since there are 8 bits within each uint8_t element. Therefore, one has to check the bits carefully if the number of grid points is not a multiple of 8.

Algorithms

One could potentially implement the contour tracing (or edge tracing) algorithm ourselves if needed.

Possible choices are

• Reddit post with about extracting a polygon from a raster image and some visualization of the algorithm.
• Marching cubes?
• Contour tracing algorithms with very good explanations.
  • Contour tracing example
• Edge detection algorithms
  • Canny detection might be "bad" for binary images
  • Code examples, buy canny algorithm which might be bad.
  • More Canny edge detection example
• Do I need Morphological Transformations

Favorites

The algorithms below could be a good fit. The Suzuki algorithms can even establish the hierarchy of edges/contours.

• Suzuki algorithm Link
  • juliaimages claims that this is what OpenCV uses as well.
  • more sources
  • Helpful explanations of the Suzuki-Abe algorithm and other topics in computer vision.s
• Fast contour tracking

Libraries for tracking contours and edges

Note that this overview contains also lots of libraries or tools for Python or special data bases for geographic information systems (GIS).

• rasterio, Sample of using rasterio together with shapely.

• cocoapi. Has not seen any updates in a while.

• OpenCV. Seems to be a heavy dependency in case we want to use only one few specific operation.

  • Example of contour approximation and further examples

• Some contourplot example

• StackOverflow thread about algorithms to fit polygon to contour.

• PostGIS

  PostGIS is a spatial database extender for PostgreSQL object-relational database. It adds support for geographic objects allowing location queries to be run in SQL.

  Has nice documentation

• There is a polygon library for C++. The library does not convert to polygons though.

• potrace

• autotrace

• GDAL. Seems to be used by rasterio.

For C++, most examples point to OpenCV. OpenCV is often also the backend used by Python packages.

Favorite

For a quick test I set up a small C++ example that obtains the contour of an artificial bitmask. This worked quite well, but is lacking the polygon representation. Additionally, OpenCV might be a rather large dependency compared to what we actually want to achieve by extracting the contour.

Formats to represent polygons

• PostGIS has two lists of
• points
• • Oracle's databases uses single list, but with marker where the whole starts.
• Coco does something different, but does not support holes. GitHub issue.

Conversion of pixels to polygons

• Matlab code
• Some Python package

[ajaust]

At the moment we cannot fix this issue in a simple way. Therefore, I will mark the issue as wontfix at the moment.