Author | John Talbot | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Institution | Physics Dept., University of Ottawa | ||||||||||||||
Latest version | 0.3 pre-alpha, progress 30% | ||||||||||||||
Description | Feature extraction toolkit based on a wavelet multiscale vision model. Includes 1D signal processing sample application for line identification and classification of astronomical spectra. | ||||||||||||||
Purpose |
| ||||||||||||||
License | GPL version 2 | ||||||||||||||
Source Code | Located on SourceForge | ||||||||||||||
API Documentation | JavaDoc API and hyperlinked source code | ||||||||||||||
Programming Language | Java 5.0 required | ||||||||||||||
Persistence |
| ||||||||||||||
Dependencies |
| ||||||||||||||
Reliability | Unit testing | ||||||||||||||
Algorithm |
|
||||||||||||||
Procedure |
| ||||||||||||||
Progress |
|
Click on titles for more details.
The first step in the Multiscale Vision Model for feature extraction is to
transform the signal using a discrete wavelet transform based on the à trous
with a B3-spline smoothing function.
(see Starck, 2002).
This produces the wavelet coefficients in several scales and the 1-sigma
threshold. Each above threshold artifact is associated with a structure. Each
wavelet scale contains a structure which is a set of contiguous wavelet
coefficients which exceed a noise threshold. A structure is defined in a scale
with a noise threshold. A structure optionally contains a reference to its
parent structure and a list children structures via interscale relationships. A
structure may be a part of an object. A structure may be due noise if it
posseses very few pixels (the upper limit of which is application specific) and
it is not connected to any other structure via an InterscaleRelationship or it
is located near the boundary of the signal, in which case it might be due to
boundary effects.
More ... .
The next step in the Multiscale Vision Model involves an attempt to associate structures into an object tree which corresponds to a kind of feature in the original signal. An object contains a set of connected interscale relationships representing a tree of structures spanning multiple scales and usually restricted to a small subset of positions in the original signal. Each interscale relationship share one structure in common with another interscale relationship instance in the same object. An object is composed of zero or more sub-objects represented by a subset of the interscale relationship of the parent object. Separation into sub- objects is based on the local-maxima contained in each object.
The final step in the Multiscale Vision Model
is to accurately reconstruct each object using an iterative conjugate gradient
matrix solver. All objects are extracted, irrespective of shape or extend.
More ... .
The various features in a signal can be measured. For instance in 1D signals some features resemble peaks which can be measured by fitting them using a Levenberg Marquardt non-linear least-square-fit to obtain the width, height and center of a gaussian function. This type of measurement is but one example, many other kinds of features could be measured such as discontinuities.
A Java GUI for viewing original signal and overlays of its extracted features.
The following sections go into greater detail for each step :
The term 'à trous' comes from the 'holes' inserted between the smoothing function coefficients
kernel : {1, 4, 6, 4, 1} / 16
compact B3 spline smoothing functionj
: wavelet scalec(j)
: successively smoothed signalw(j)
: multiresolution discrete wavelet tranform scales of signalc(0) = signal
j = 1
c(j)
= convolution of c(j-1)
with kernel
w(j) = c(j) - c(j-1)
kernel
filter coefficients (holes). (i.e. the filter expands by a factor of 2 at every iteration)j = j + 1
c(0) = c(p) +
Σ w(j)
, where c(p)
is the smoothed array at the last scale p
Operators | |
---|---|
W | Wavelet transform operator |
Pw | Projection onto Oi structures operator |
A = Pw o W | Composition of the two previously defined operators |
A-1 | Adjoint of A operator |
W-1 | Inverse transform of W operator |
Variables | |
Oi | Signal corresponding to object with index i |
Wi | Wavelet space signal restricted to Oi structures, zero elsewhere |
n | Reconstruction iteration |
Oi(n) | Object with index i at iteration n |
wr(n) | Wavelet residual signal at iteration n |
R(n) | Residual signal at iteration n |
α(n) | Convergence parameter at iteration n |
β(n) | Convergence parameter at iteration n |
threshold | Threshold for wavelet residual (constant) |
1 | Intialization | Oi(0) = W-1Wi wr(0) = Wi − AOi(0) R(0) = A-1wr(0) |
---|---|---|
2 | Convergence parameter | α(n) = | A-1wr(n) | 2 / | AR(n) | 2 |
3 | Correction | Oi(n+1) = Oi(n) + α(n)R(n) |
4 | Positivity constraint | Negative values of Oi(n+1) are set to zero |
5 | Wavelet residual | wr(n+1) = Wi − AOi(n+1) |
6 | Convergence test | if | wr(n+1) | < threshold then STOP |
7 | Convergence parameter | β(n+1) = | A-1wr(n+1) | 2 / | A-1wr(n) | 2 |
8 | Residual image | R(n+1) = A-1wr(n+1) + β(n+1)R(n) |
9 | Return to step 2 |