The Discrete Pulse Transform (DPT) makes use of LULU smoothing to decompose a signal into block pulses. The most recent and e ective 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 nal output. This algorithm has been shown to have important applications in arti cial intelligence and pattern recognition. Even though the Roadmaker's Pavage is an e cient 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 lter banks to downsample the Roadmaker's Pavage 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, and so methods of estimation for lter banks are examined, as well as the design of a good lter bank that may be reused without needing recalculation.
The Discrete Pulse Transform (DPT) decomposes a signal into block pulses
using LULU smoothers in such a way that the signal can be reconstructed fully
[
It should be noted that although the implementation algorithms of the DPT have reduced to linear complexity, the algorithms are still computationally slow. This is due to the algorithms needing to be processed in series, as well as the comparisons and transformations of data structures required at each step. Hence the true computational times needed is somewhat masked by the Big-O complexity. There is still a need to reduce to computational time, particularly for real-time application. The fact that these newer implementations are in the form of graph structures provides several advantages, especially considering the recent advances in theory and application of graph sampling and interpolation methods.
The research conducted here makes use of such recent developments in graph sampling and graph spectral theory to improve the running time and memory requirements of the Roadmaker's Pavage algorithm by using an approximation of the algorithm and its output. In addition to this, any advantages that come with graph spectral analysis is now also introduced to the algorithm. The primary mechanism behind these improvements comes from the use of graph spectral lters and graph sampling methods.
The paper begins with an overview of the suggested algorithm and its components in section 2, and then demonstrates application of the algorithm in section 3, before concluding. 2
The method used to improve computational speed of the Roadmaker's Pavage
algorithm involves the use of a graph spectral lter bank. The reason behind
ltering the signals is in order to band limit the signal. Band limited graph
signals can be interpolated with perfect reconstruction after sampling under
certain conditions [
Roadmaker's Pavage decomposition and extraction DP Tdc and DP Tex The Roadmaker's Pavage is a graph-based algorithm that results in a tree that contains the information required to extract the same pulses as de ned by the DPT. The algorithm starts by imposing the image on a rectangular grid graph, known in this context as the Working Graph. Through a series of edge contractions, comparisons and clusterings, this Working Graph is eventually transformed into a tree. An example of the pulses extracted from a small 2 2 image, as well as the data structures built by the Roadmaker's Pavage is shown in Figure 2.
The Working Graph that is initialized is an example of a rectangular grid graph, which is also a bipartite graph. Even though the nal product of the Roadmaker's Pavage is a tree, the extracted pulses need to be reshaped into an image with the same dimensions as the original in order to be meaningful. The reshaped output signal is not contained in a graph, but its properties and relations still behave as if it was imposed a new grid graph with the same dimensions as the original working graph. Thus, ltering, sampling and interpolation is based on this Working Graph structure. The original signal is on a graph of this type and is ltered and sampled from accordingly, while the output signal is upsampled and ltered as if it were a signal on a new grid graph. For these reasons the Roadmaker's Pavage decomposition, as well as extraction of the desired pulses, is inserted into the middle of the lter bank. 2.2
Graph Spectral Filters H0( ) and H1( )
H0( ) and H1( ) are low and high pass lters respectively. They rst
convert a graph signal, x 2 RN with each xi de ned on vertex i, into its graph
spectral domain using the Graph Fourier Transform (GFT). The signal is then
converted back to the vertex domain using the Inverse Graph Fourier
Transform (IGFT). The Graph Fourier Transform can be obtained from the
eigendecomposition of a graph shift operator [
An alternative shift operator derived from A is the Laplacian Matrix, L [
1
pdeg(vi)deg(vj)
if i = j and deg(vi) 6= 0
if i 6= j and vi is adjacent to vj
otherwise:
As the name implies, this version of the Laplacian is always symmetric, hence its
eigenvector basis is real and orthogonal [
L = U
U T ; where is a diagonal matrix containing the eigenvalues f 1; 2; :::; N g of L and the columns of U contains the eigenvectors of L . This eigenbasis is orthonormal, hence U 1 = U T .
De nition 1. The Graph Fourier Transform is the projection of a graphs signal in its vertex domain to the graphs spectral domain. For a diagonalizable graph shift operator L = U U T on graph G, the Graph Fourier Transform of graph signal x 2 RN is given by:
x^ = U T x Alternatively it may be de ned by its evaluation at each eigenvalue: 8 k; x^k = (x;vkT ) =
N
X xiuk;i = xT uk
i=1
where uk is the eigenvector associated with the kth eigenvalue of L, which is
also the kth column of U [
The GFT is invertible, as U x^ =U U spectral lters can be constructed.
De nition 2. A Graph Spectral Filter is a function that projects separately on each of the eigenspaces of L depending on the value of the respective . Mathematically, a kernel ! h( ), de nes a graph lter H such that H = U h( )U T .
Hence a ltered signal is de ned such that xh = Hx. Several kernels are
suitable to de ne a lter. The simplest is to use an indicator function that cuts
o certain frequencies completely, such as h( ) = 1 if < w; else h( ) = 0, where
w is the desired cut-o frequency. The lter used here is a graph quadrature
mirror lter (graph-QMF) so that:
1x = x. With the GFT de ned, graph
1. H0 and H1 are used in both the analysis and synthesis bank of each respective
pipeline, as opposed to di erent lters used at each end,
2. H0 = H1(2 ). Recall that the eigenvectors of L are symmetric around 1
and range from 0 to 2, and
3. H02( ) + H12( ) = c2
where 1=c2 is a constant that scales the nal output signal [
Finally, of note is the fact that exact calculation of these graph lters requires
calculation of the full eigenspectrum as well as the dense eigenvector matrix U
of size N 2 which can require more memory space than available for large N .
For this reason, Chebyshev polynomials are used to approximate the response
of xh = U h( )U T x. This is because h( ) can be approximated as a Kth order
polynomial PkK=01 ak k [
Upsampling and downsampling operators # S and " S
The operators Sd0; Sd1 and Su0,Su1 are used to downsample and upsample
signals, respectively. Downsampling is done by simply taking only the n < N
vertices and corresponding signals in the graph that are chosen so that RN ! Rn.
Upsampling increases the dimension of a sampled signal to the original graph
dimensions, imposing the signal on the original vertices and then lls any missing
values with zeroes. The initial graph used in the Roadmaker's Pavage algorithm
is a grid graph, which is also a bipartite graph. A bipartite graph is a graph that
can be divided into two disjoint and independent sets VBottom and VT op such
that every edge connects a vertex in VBottom to one in VT op, while the vertices
within a set are not connected to each other. Sampling a bipartite graph signal
according to these disjoint bipartite sets is a standard procedure when sampling
is required, as the sets will cover a large area of the graph with approximately
equal spacing between both sampled and excluded vertices. This makes
interpolation of an upsampled signal more accurate as each empty excluded node will
have several neighbours used to interpolate its value [
There is however, a major caveat when using bipartite sampling for the Roadmaker's Pavage. By de nition, each bipartite set has no connections within itself but the Roadmaker's Pavage requires a connected graph in order to perform the required transform and comparisons. To remedy this, an adjusted graph is used for sampling. First, vertex indices to be sampled are chosen in a bipartite manner as usual. Additional diagonal edges are then used to join nodes together. Finally the two sets are separated from each other as if the graph is still bipartite, but now each set is connected. Thus the Roadmaker's Pavage algorithm can proceed on these sampled graphs. An example of this procedure performed on a small graph with 4 nodes is shown in Figure 3. 3
In this section a comparison is shown between using the original Roadmaker's Pavage algorithm on an example image (of Chelsea the cat), and the proposed
Roadmaker's Pavage used in conjunction with a lter bank. The original image was decomposed into pulses using both methods. In the case of the sampled and ltered algorithm, it was found that the entire high frequency pipeline could be discarded for the cost of a small decrease in mean-squared-error and extraction accuracy of smaller features. This meant that only one line of lters and samplers was required in this instance as well as only a single tree data structure.
The image was then reconstructed both fully and partially in both cases. Partial reconstruction included extraction of only the smallest textures in the image, extraction of a mid-range of pulse sizes giving a smoothed image and extraction of the largest pulses giving the large features present in the image. The full and partial reconstruction of the image can be seen in Figure 4 while the equivalent reconstructions can be seen in Figure 5.
The original image has 135 300 pixels. The root-mean-squared-error between the fully reconstructed original image and the interpolated fully reconstructed image from the ltered Roadmaker's Pavage was 1:47. The original algorithm has an RMSE of zero as it perfectly reconstructs the original image. The error introduced by the ltered algorithm can be justi ed by the noticeable decrease in computational time and storage requirements. The original algorithm required 87 CPU seconds to decompose, approximately 5:5 CPU seconds to reconstruct the signals and needed a tree with 170 777 nodes to store the information. The ltered algorithm needed only 27:5 CPU seconds to decompose the signal, approximately 2:5 CPU seconds to reconstruct and a tree with 89 234 nodes for storage. A summary of these ndings is given in Table 1
The size of the sampled graphs is approximately half the size of the original.
The size and distribution of pulses extracted depends on the signal and size of
the graph used. No precise method to nd equivalent pulses between the full
Roadmaker's Pavage output and the ltered and sampled Roadmaker's Pavage
output. Future work will develop adaptive selection of the pulses using shape
measurements of pulses.
This paper has shown that an approximation of the Discrete Pulse Transform
can be obtained using the Roadmaker's Pavage algorithm in conjunction with
Fig. 5. An image of Chelsea decomposed and reconstructed using the Roadmaker's
Pavage via a graph bank that has been upsampled, ltered and interpolated after the
pulses were reconstructed. Shown in: (a) interpolation of all pulses reconstructed, (b)
interpolation of smallest textures, (c) interpolation of smooth image, (d) interpolation
of largest features.
graph spectral ltering and sampling. A minor loss of accuracy comes with the
bene ts of noticeably shorter computational time and storage requirements.
Depending on the level of precision required and the size of the features needed, the
high pass lters can be discarded if not necessary for the task. Even if the high
frequencies are still needed, this approximate algorithm can now be calculated
with two independent channels and thus can be parallel processed. Simulations
are to be conducted in the future on sets of images to nd the distribution
and consistency of these ndings. The partially reconstructed images here were
obtained through trial and error to nd rough equivalents between the two
methods. For these reasons no mean square-error or similarity comparison was yet
made to compare partial reconstruction. These will be compared in simulations
in the future using trial methods such as approximating the equivalent pulse
sizes needed by checking the relative pulse distributions of the original
Roadmaker's Pavage and the new ltered Roadmaker's Pavage, and shape measures.
This sampling approach for the DPT should be further tested for accuracy in
areas the DPT has been applied such as segmentation [