Module FillGaps
See Also

Aim of module

Detects gaps (i.e. void pixels) in raster models and provides several interpolation methods to close them.

General description

The generation of Digital Terrain Models (DTM) usually leads to void pixels where buildings and vegetation were removed. Module FillGaps aims to close these gaps with qualified approximation of void pixel using information of valid neighbouring pixels. In a first step, connected void pixels get joined to gap objects with boundary information. Each of the boundary pixels is adjacent to at least one void pixel and contains a valid pixel value. Based on the boundary information the void pixels will be filled with qualified values in a second step.

The following fill methods (parameter method) can be used to close gaps:

  • adaptive - gaps will be filled with a moving plane interpolation with Inverse Distance Weighting (IDW)
  • max - take the maximum value of the boundary pixels as a fill value for all void pixels
  • min - take the minimum value of the boundary pixels as a fill value for all void pixels
  • plane - gaps will be filled with a tilted fitting plane approximation for all boundary pixels
  • triangulation - gaps will be filled with interpolated values from triangulation of the boundary pixels

This module uses Module Bounds to detect the area covered with data in the input file. If no specific boundary polygon is given with boundsFile, an alpha shape is calculated covering the area of valid pixels to get the bounds of the dataset.

Boundary ratio

To detect outer boundaries of the dataset (e.g. pixels outside of boundsFile polygon) and avoid filling them with inappropriate values the parameter boundaryRatio is used. The boundaryRatio specifies a minimum ratio between valid boundary pixel of a gap and the total number of boundary pixel including the pixel at the edge of the picture.

$ \LARGE boundary\ ratio = \frac{valid\ boundary}{total\ boundary} $

The boundary ratio describes how well a gap is described by bordering pixels. If a gap has, for example, 15 valid boundary pixel with 20 boundary pixel in total, the boundary ratio is 0.75, which means that the gap is 75% bounded. Only gaps with a boundary ratio greater than or equal to the given threshold boundaryRatio will be processed and filled.
Examples for boundary ratio (see figure below):

  • yellow - 5 valid boundary pixels, 11 total - boundary ratio = 0.455
  • red - 9 valid boundary pixels, 9 total - boundary ratio = 1.0
  • green - 7 valid boundary pixels, 12 total - boundary ratio = 0.58
  • pink - 7 valid boundary pixels, 8 total - boundary ratio = 0.875
  • blue - 10 valid boundary pixels, 12 total - boundary ratio = 0.83

Examples for boundary ratio - Gaps (colored), valid boundary pixels (light colors) and outer boundaries (black crosses)

Adaptive plane with Inverse Distance Weighting (IDW)

If method adaptive is chosen to fill the gaps, an adaptive plane is fitted for each void pixel. The plane fit is performed based on all valid boundary pixels of a gap, with an adaptive weighting of the pixels based on the distance to the void pixel, where the plane is calculated. The weighting function is based on the inverse squared distance (IDW2) with respect to the dimensions of the gap. This means that a boundary pixel on the opposite side of a gap gets a weight close to zero, while a close-by boundary pixel gets a weight close to one. By using this method, two neighbouring void pixels have similar weights on the boundary pixels in the plane-fit, thus, the method always results in a smooth interpolation within the gap.
Please note, that this method is not applicable for big gaps (>100.000 px). As described above, a plane is fitted for each void pixel involving all boundary pixels. Therefore this method is rather slow for big gaps and can lead to abrupt transition between filled pixels and adjacent boundary pixels, because of the influence of distant boundary pixels.

Maximum area of gaps

The Parameter maxArea allows to specify maximum sizes for gaps to be filled. The first value of the two-value array specifies the maximum area (in unit^2) of gaps to be filled. Especially for the use of the adaptive fill method, where performance issues can be expected for big gaps (as mentioned above), this parameter is of importance. Therefore the second value specifies the maximum area of gaps to be filled with the adaptive fill method. Gaps that are bigger than the specified maximum gap size are filled with the triangulation method.

Parameter description

-inFileinput raster file
Type: opals::Path
Remarks: mandatory
Import raster image in GDAL supported format.
-outFileoutput raster file
Type: opals::Path
Remarks: estimable
Path to the output raster image file in GDAL supported format
Estimation rule: The current directory and the name (body) of the input file are used as file name basis. Additionally, the postfix '_filled' plus the output format specific extension is added.
-oFormatraster file format [GTiff,AAIGrid,SCOP,...]
Type: opals::String
Remarks: estimable
Use GDAL driver names like GTiff, AAIGrid, USGSDEM, SCOP... .
Estimation rule: The output format is estimated based on the extension of the output file (*.tif->GTiff, *.dem->USGSDEM, *.dtm->SCOP...).
-methodfill method
Type: opals::FillMethod
Remarks: mandatory

Possible values:  
  min ............. Fill gap with minimum value of boundary points
  max ............. Fill gap with maximum value of boundary points
  plane ........... Uses tilted plane fit to fill gaps
  adaptive ........ Uses adaptive plane fit with inverse distance weighting
  triangulation ... Uses triangulation of boundary points

The different fill methods use the boundary points of a gap for the approximation of void pixels inside the gap.

-boundaryRatiominimum boundary ratio
Type: float
Remarks: default=0.6
Ratio between the number of valid boundary pixel and the total number of boundary pixel of a gap including pixel that lie along the edge of the image or specified bounds. Gaps with a boundary ratio lower than the specified minimum boundary ratio will not be filled.
-boundsFilebounds file
Type: opals::Path
Remarks: optional
Vector file (supported by opalsImport, e.g. *.shp) containing a polygon which specifies a boundary for the area where the gaps should be filled.
-maxAreamaximum area of a gap to be filled
Type: opals::Vector<double>
Remarks: optional
The first value of the vector specifies the maximum area of a gap to be filled (in units^2). If the parameter is omitted or set as -1, gaps of any size will be filled (if they are within the bounds). The second value specifies the maximum area to be filled with the adaptive method, if selected (see documentation above). Gaps that are bigger than this maxArea-adaptive threshold are filled with triangulation method, if the adaptive method was selected. If the second value is omitted for use of the adaptive method, the maxArea-adaptive is calculated as 100.000 [px] * px_area [units^2].
-debugOutFiledebug outfile
Type: opals::String
Remarks: optional
Write different outfiles for debug reasons (e.g. boundary, void, boundary_values)


The data used in the following examples can be found in the $OPALS_ROOT/demo/ directory. As a prerequisite the data of (flyover.laz) are imported into an OPALS data manager and a raster DTM is calculated using the following commands:

opalsImport -inFile flyover.laz -tileSize 100
opalsGrid -inFile flyover.odm -outFile flyover_dtm.tif -interpolation movingPlanes -neighbours 8 -searchRadius 2 -selMode quadrant

The dataset contains a flyover over a highway, which needs to be filled with proper values.

Z-colored DTM of flyover_dtm.tif

Example 1:

opalsFillGaps -inFile flyover_dtm.tif -outFile flyover_dtm_adaptive.tif -method adaptive

Z-colored DTM of flyover_dtm_adaptive.tif - Gap filled with adaptive interpolation

Example 2:

opalsFillGaps -inFile flyover_dtm.tif -outFile flyover_dtm_triangulation.tif -method triangulation

Z-colored DTM of flyover_dtm_triangulation.tif - Gap filled with triangulation method

Example 3:

opalsFillGaps -inFile flyover_dtm.tif -outFile flyover_dtm_plane.tif -method plane

Z-colored DTM of flyover_dtm_plane.tif - Gap filled with tilted plane interpolation

Example 4:

opalsFillGaps -inFile flyover_dtm.tif -outFile flyover_dtm_min.tif -method min

Z-colored DTM of flyover_dtm_min.tif - Gap filled with the minimum bounding value

Example 5:

opalsFillGaps -inFile flyover_dtm.tif -outFile flyover_dtm_max.tif -method max

Z-colored DTM of flyover_dtm_max.tif - Gap filled with the maximum bounding value