# Designing an efficient curve-matching algorithm

I'm currently designing a curve-matching algorithm and as I already explored many ideas I'm requesting your help. So, if you got some advices about how to handle this problem, feel free to answer!

# The Context

I got a flash LIDAR spatio-temporal response to one short impulsion. The data acquired is stored in a 3-D matrix:

• First and second dimensions are spatial ones. As in a 2-D image they represent azimuth and elevation of a pixel.
• Third dimension is the temporal one. For each pixel the illumination is recorded for a fixed duration and stored in this dimension. Typically, the curve observed is a Gaussian and its parameters (variance, max amplitude and delay) are affected by the LIDAR surrounding environment.

To be more specific the laser pulse is distorted by the environment. The multi-path of light impacts the Gaussian variance, the object distance to the RADAR impacts the delay and the amplitude and the reflectivity of the object impacts the amplitude of the Gaussian.

# The Aim

As in the real world objects are contiguous and homogeneously distributed in space, neighboring pixels are more likely to have a similar reflectivity and distance to the LIDAR thus neighboring Gaussians are very similar.

What I'm trying to do is to quantify the similarity of a pixel impulse response to its neighborhood (3x3 neighborhood for instance). This is very close to the concept of gradient, I want to detect pixels that are parts of an homogeneous objects and ones at the border of an object where there is a disruption.

For now I've implemented two different algorithms. One that is similar to a an image derivation adapted to the 3-D structure, with a 2-D Laplacian Filter. The second algorithm is based on the measure of similarity using Sum of Absolute Differences, also adapted to the data 3-D structure.

# The Problem

These algorithms work somewhat fine but since the signal can be noisy and sometimes very far from a Gaussian shape I think and I hope better algorithms can be implemented.

My research tracks are focused on curve-fitting before comparison (Levenberg–Marquardt algorithm for instance) for now, but this proved very computationally time-consuming!

If you know about other methods or concepts that can help in resolving my problem, feel free to participate :)

Thank you!

EDIT:

Matrix size is 32x128x128

• Just to clarify, are you interested in estimating the similarity of two neighbour pixels based on their temporal time series? Also, what sort of computational load are we talking about here? What would be a representative size of that 3D matrix? – A_A Apr 11 '18 at 12:24
• Yes that is right, but since I need an isotropic measurment I take not two pixels but a pixel and its 4 neighbors (cross patern). Concerning the computational load a real-time execution is required but I'm not foucusing on it at this time! The matrix is 32x128x128 so 4096 time series of 128 values each. – Louis Lac Apr 11 '18 at 14:33
• That's great, thank you, what sort of pixel size are we talking about? (Physical pixel size, what is the actual physical area that each pixel represents?) – A_A Apr 11 '18 at 15:12
• do not have the sensor data sheet in front of me, so I can't give you its resolution sorry :/ Each pixel represents a solid angle of the space obviously but I do not know the specifications. I thinks at some point it is not that important for the application, for now! – Louis Lac Apr 11 '18 at 16:16
• Thanks, this last question was to get a feeling about how large that "edge" might be in the transition between a smooth area and a less smooth area. – A_A Apr 11 '18 at 16:22

The two most obvious things you can try are:

1. Fitting a Gaussian to your data and then clustering their parameters
2. Estimate the similarity of waveforms directly and then try to cluster that

Since you know that the return waveform conforms to a Gaussian, it is better to use a method that takes this into account.

So, basically, for every pixel time course, you will end up with a fitted $\mu, \sigma^2$. You can then use these two, plus any other target dependent feature to characterise the surface.

These algorithms work somewhat fine but since the signal can be noisy and sometimes very far from a Gaussian shape I think and I hope better algorithms can be implemented.

The fact that you know that your data is supposed to conform to a specific model is a great deal of knowledge and you should try to take that into account as much as possible. "...sometimes very far from Gaussian..." doesn't always mean "not Gaussian". You might for example be getting two or more returns in the same time-course which means that you might have to apply something like a kernel density estimator or an iterative fitting process to pick up each individual return. For more information, please see this paper.

The second option is to estimate "similarity" of waveforms directly. In this case, given two time series $U,V \in \mathbb{R}^\mathbb{N}$, you are looking at a function $F(U,V,\Theta) \rightarrow \mathbb{R}$ which simply returns a number that is proportional to how "similar" these two waveforms are, given some additional parameters in $\Theta$. Most of the times, "similar" is another word for "co-varying".

The most obvious of the possible $F$s is the discrete cross-correlation. In that case $f_{xcorr}(U,V)$ returns a number between $-1..1$ which tells you how similar $U,V$ are. Another possible $f$ is Coherence. In this case, parameters include the frequency component of which you want the coherence calculated at (e.g. $f_{coher}(U,V,k)$ (for the $k^{th}$ component) which returns a number between $0..1$. Another possible $f$ is Mutual Information with is a slightly different take on "similarity" and more challenging to apply correctly on continuous (rather than digital) signals.

And then, on top of the metrics mentioned above you have variations, like wavelet based cross-correlation instead of correlation, LZ complexity instead of Mutual Information and so on.

The field of Similarity Metrics is vast and there is a lot of work happening in the processing of Electroencephalography (EEG) signals in Functional Connectivity (which basically involves a lot of those evaluations of similarity under very challenging conditions of waveform noise and artifacts). For more information, please see this, this and this.

These publications are not exactly on your topic but they use a great deal of similar methods and tools for estimating the similarity between two time-series which is what you are trying to do as well. Therefore, when reading those, try to extrapolate the terminology and then try to search in remote sensing related journals for similar things. I am sure that such a search would return much more relevant results adapted to the specifics of estimating similarity of the laser pulse returns.

Hope this helps.

• Thank you very much for your answer! I already tried extracting Gaussian parameters and that is very interesting but quite slow for my purpose. I also tried cross-correlation so I'm going to try coherence. Papers about EEG and Processing Full-Waveform Lidar Data seem to be a good source of inspiration, thanks. – Louis Lac Apr 12 '18 at 9:43
• @LouisLégionn'EirbLac Glad to hear this was helpful, all the best with your work. – A_A Apr 12 '18 at 9:44