Abstract:
The Discrete Pulse Transform (DPT) makes use of LULU smoothing to decompose a signal into block pulses. The
most recent and effective implementation of the DPT is an algorithm called the Roadmaker’s Pavage, which uses
a graph-based algorithm that produces a hierarchical tree of pulses as its final output, shown to have important
applications in artificial intelligence and pattern recognition. Even though the Roadmaker’s Pavage is an efficient
implementation, the theoretical structure of the DPT results in a slow, deterministic algorithm. This paper
examines the use of the spectral domain of graphs and designing graph filter banks to downsample the algorithm.
We investigate the extent to which this speeds up the algorithm and allows parallel processing. Converting
graph signals to the spectral domain can also be a costly overhead, so methods of estimation for filter banks are
examined, as well as the design of a good filter bank that may be reused without needing recalculation. The
sampled version requires different hyperparameters in order to reconstruct the same textures of the image as the
original algorithm, selected previously either through trial and error (subjective) or grid search (costly) which
prevented studying the results on many images effectively. Here an objective and efficient way of deriving similar
results between the original Roadmaker’s Pavage and our proposed Filtered Roadmaker’s Pavage is provided. The
method makes use of the Ht-index which separates the distribution of information in the graph at scale intervals
by recursively calculating averages on decreasing subsections of the scale data stored. This has enabled empirical
research using benchmark datasets providing improved results. The results of these empirical tests showed that
using the Filtered Roadmaker’s Pavage algorithm consistently runs faster, using less computational resources,
while having a positive SSIM (structural similarity) with low variance. This provides an informative and faster
approximation to the nonlinear DPT, a property which is not standardly achieveable.
