Quadtree Module

The quadtree reduces the amount of displacement information contained in a full resolution displacement scene by adaptively subsampling in areas of complex signal (a visual example can be found here InSAR Scene Inspection with Spool. The complexity of the signal is defined through the standard deviation within a tile (or QuadNode) of the data. The quadtree parameters define thresholds when a QuadNode is split. The four essential threshold controlling the tree are:

• epsilon/std threshold (epsilon)

• Fraction of NaN values within (nan_allowed)

• Maximum and minium dimension of the tile (tile_size_max and tile_size_min)

Programming example of the quadtree can be found here Quadtree and here InSAR Scene Inspection with Spool.

class kite.Quadtree(scene, config=<kite.quadtree.QuadtreeConfig object>)

Quadtree for irregular subsampling InSAR displacement data held in kite.scene.Scene

InSAR displacement scenes can hold a vast amount of data points, which is often highly redundant and unsuitably large for the use in inverse modeling. By subsampling and therefore decimating the data points systematically through a parametrized quadtree we can reduce the dataset without significant loss of displacement information. Quadtree subsampling keeps a high spatial resolution where displacement gradients are high and efficiently reduces data point density in regions with small displacement variations. The product is a managable dataset size with good representation of the original data.

The standard deviation from kite.quadtree.QuadNode.displacement is evaluated against different corrections:

• mean: Mean is substracted

• median: Median is substracted

• bilinear: A 2D detrend is applied to the node

• std: Pure standard deviation without correction

set through setCorrection(). If the standard deviation exceeds epsilon the node is split.

The leaves can also be exported in a CSV format by export_csv(), or GeoJSON by export_geojson().

Controlling attributes are:

• epsilon, RMS threshold

• nan_fraction, allowed numpy.nan in node

• tile_size_max, maximum node size in

  meters or degree

• tile_size_min, minimum node size in

  meter or degree

leaves hold the current tree’s QuadNode ‘s.

blacklistLeaves(leaves)

Blacklist a leaf and exclude it from the tree

Parameters

leaves (list) – Leaf instances

clearLeaves()

Clear cached leafs and properties

epsilon

Threshold for quadtree splitting its QuadNode.

The threshold is the maximum standard deviation of leaf mean, median or simply its values (see ‘’SetSplitMethod’‘) allowed to not further split a “QuadNode”.

Setter

Sets the epsilon/RMS threshold

Getter

Returns the current epsilon

Type

float

epsilon_min

Getter

(Cached) Lowest allowed epsilon

Type

float

export_csv(filename)

Exports the current quadtree leaves to filename in a CSV format

The formatting is:

# node_id, focal_point_E, focal_point_N, theta, phi,             mean_displacement, median_displacement, absolute_weight

Parameters

filename (string) – export_csv to path

getMPLRectangles()

Get the quadtree as a list of matplotlib rectangles.

Returns

Rectangles for plotting

Return type

list of matplotlib.patcjes.Rectangle

getStaticTarget()

Not Implemented

leaf_center_distance

Getter

(Cached)

Getter

Leaf distance to center point of the quadtree

Type

numpy.ndarray, size (N, 3)

leaf_coordinates

Synonym for Quadtree.leaf_focal_points() in easting/northing

leaf_focal_points

Getter

Leaf focal points in local coordinates.

Type

numpy.ndarray, size (N, 2)

leaf_focal_points_meter

Getter

Leaf focal points in meter.

Type

numpy.ndarray, size (N, 2)

leaf_los_rotation_factors

Getter

(Cached)

Getter

Trigonometric factors for rotating displacement matrices towards LOS. See kite.BaseScene.los_rotation_factors

Type

numpy.ndarray, Nx3

leaf_matrix_means

Getter

Leaf mean displacements casted to kite.Scene.displacement.

Type

numpy.ndarray, size (N, M)

leaf_matrix_medians

Getter

Leaf median displacements casted to kite.Scene.displacement.

Type

numpy.ndarray, size (N, M)

leaf_matrix_weights

Getter

Leaf weights casted to kite.Scene.displacement.

Type

numpy.ndarray, size (N, M)

leaf_mean_px_var

Getter

Mean pixel variance in each quadtree, if kite.Scene.displacement_px_var is set.

Type

numpy.ndarray, size N.

leaf_means

Getter

(Cached)

Getter

Leaf mean displacements from kite.quadtree.QuadNode.mean.

Type

numpy.ndarray, size N.

leaf_medians

Getter

(Cached)

Getter

Leaf median displacements from kite.quadtree.QuadNode.median.

Type

numpy.ndarray, size N.

leaf_phis

Getter

Median leaf LOS phi angle. kite.Scene.phi

Type

numpy.ndarray, size (N)

leaf_thetas

Getter

Median leaf LOS theta angle. kite.Scene.theta

Type

numpy.ndarray, size (N)

leaves

Getter

(Cached):getter: List of leaves for current configuration.

Type

(list or QuadNode s)

nan_allowed

Fraction of allowed NaN values in quadtree leaves. If value is exceeded the leaf is kicked out entirely.

Setter

Fraction 0. <= fraction <= 1.

Type

float

nleaves

Getter

Number of leaves for current parametrisation.

Type

int

nnodes

Getter

Number of nodes of the built tree.

Type

int

nodes

Getter

(Cached) All nodes of the tree

Getter

Get the list of nodes

Type

list

plot

Getter

(Cached) Simple matplotlib illustration of the quadtree

Type

Quadtree.leaf_matrix_means.

reduction_efficiency

This is measure for the reduction of the scene’s full resolution over the quadtree.

Getter

Quadtree efficiency as \(N_{full} / N_{leaves}\)

Type

float

reduction_rms

The RMS error is defined between leaf_matrix_means and kite.Scene.displacement.

Getter

The reduction RMS error

Type

float

setConfig(config=None)

Sets and updated the config of the instance

Parameters

config (QuadtreeConfig, optional) – New config instance, defaults to configuration provided by parent Scene

setCorrection(correction='mean')

Set correction method calculating the standard deviation of instances QuadNode s

The standard deviation from kite.quadtree.QuadNode.displacement is evaluated against different corrections:

• mean: Mean is substracted

• median: Median is substracted

• bilinear: A 2D detrend is applied to the node

• std: Pure standard deviation without correction

Parameters

correction (str) – Choose from methods mean_std, median_std, bilinear_std, std

Raises

AttributeError

tile_size_max

Maximum allowed tile size in meter. Measured along long edge (max(dE, dN)) Maximum tile size defaults to 1/5th of the largest dimension

Getter

Returns the maximum allowed tile size

Setter

Sets the maximum threshold

Type

float

tile_size_min

Minimum allowed tile size in meter. Measured along long edge (max(dE, dN)). Minimum tile size defaults to 1/20th of the largest dimension

Getter

Returns the minimum allowed tile size

Setter

Sets the minimum threshold

Type

float

QuadtreeConfig

The QuadtreeConfig holds the necessary configuration to reconstruct and save an instance.

class kite.quadtree.QuadtreeConfig(**kwargs)

Quadtree configuration object holding essential parameters used to reconstruct a particular tree

♦ correction

builtins.str (pyrocko.guts.StringChoice), default: 'median'

Node correction for splitting, available methods ['mean', 'median', 'bilinear', 'std']

♦ epsilon

float, optional

Variance threshold when a node is split

♦ nan_allowed

float, default: 0.9

Allowed NaN fraction per tile

♦ tile_size_min

float, optional

Minimum allowed tile size in meters or degree

♦ tile_size_max

float, optional

Maximum allowed tile size in meters or degree

♦ leaf_blacklist

list of pyrocko.guts.Any objects, optional, default: []

Blacklist of excluded leaves

QuadNode Object

class kite.quadtree.QuadNode(quadtree, llr, llc, length)

A node (or tile) in held by Quadtree. Each node in the tree hold a back reference to the quadtree and scene to access

Parameters

• llr (int) – Lower left corner row in kite.Scene.displacement matrix.

• llc (int) – Lower left corner column in kite.Scene.displacement matrix.

• length (int) – Length of node in from llr, llc in both dimensions

• id (str) – Unique id of node

• children (List of QuadNode) – Node’s children

corr_bilinear

Getter

(Cached) Standard deviation of node’s displacement corrected for bilinear trend (2D)

Type

float

corr_mean

Getter

(Cached) Standard deviation of node’s displacement corrected for mean

Type

float

corr_median

Getter

(Cached) Standard deviation of node’s displacement corrected for median

Type

float

createTree()

Create the tree from a set of basenodes, ignited by Quadtree instance. Evaluates Quadtree correction method and epsilon_min.

displacement

Getter

(Cached) Displacement array, slice from kite.Scene.displacement

Type

numpy.ndarray

displacement_mask

Getter

(Cached) Displacement nan mask of displacement

Type

numpy.ndarray, dtype numpy.bool

Todo

Faster to slice Scene.displacement_mask?

displacement_masked

Getter

(Cached) Masked displacement, see displacement

Type

numpy.ndarray

displacement_px_var

Getter

(Cached) Displacement array, slice from kite.Scene.displacement

Type

numpy.ndarray

focal_point

Getter

(Cached) Node focal point in local coordinates respecting NaN values

Type

tuple, float - (easting, northing)

focal_point_meter

Getter

(Cached) Node focal point in local coordinates respecting NaN values

Type

tuple, float - (easting, northing)

gridE

Getter

(Cached) Grid holding local east coordinates, see kite.scene.Frame.gridE.

Type

numpy.ndarray

gridEmeter

Getter

(Cached) Grid holding local east coordinates, see kite.scene.Frame.gridEmeter.

Type

numpy.ndarray

gridN

Getter

(Cached) Grid holding local north coordinates, see kite.scene.Frame.gridN.

Type

numpy.ndarray

gridNmeter

Getter

(Cached) Grid holding local north coordinates, see kite.scene.Frame.gridNmeter.

Type

numpy.ndarray

iterChildren()

Iterator over the all children.

Yields

Children of it’s own.

Type

QuadNode

iterLeaves()

Iterator over the leaves, evaluating parameters from Quadtree instance.

Yields

Leafs fullfilling the tree’s parameters.

Type

QuadNode

llE

Getter

Lower left east coordinate in local coordinates (meters or degree).

Type

float

llN

Getter

Lower left north coordinate in local coordinates (meter or degree).

Type

float

mean

Getter

(Cached) Mean displacement

Type

float

mean_px_var

Getter

(Cached) Variance of displacement

Type

float

median

Getter

(Cached) Median displacement

Type

float

nan_fraction

Getter

(Cached) Fraction of NaN values within the tile

Type

float

npixel

Getter

(Cached) Undocumented

phi

Getter

(Cached) Median Phi angle, see Scene.

Type

float

sizeE

Getter

(Cached)

Getter

Size in eastern direction in meters or degree.

Type

float

sizeN

Getter

(Cached)

Getter

Size in northern direction in meters or degree.

Type

float

std

Getter

(Cached) Standard deviation of displacement

Type

float

theta

Getter

(Cached) Median Theta angle, see Scene.

Type

float

var

Getter

(Cached) Variance of displacement

Type

float

weight

Getter

Absolute weight derived from kite.Covariance - works on tree leaves only.

Type

float