Shah: Shape-Adaptive Haar Wavelet Transform For Images With Application To Classification

We propose the SHAH (SHape-Adaptive Haar) transform for images, which results in an orthonormal, adaptive decomposition of the image into Haar-like components, arranged hierarchically according to decreasing importance, whose shapes reflect the features present in the image. The decomposition is as sparse as it can be for piecewise-constant images. It is performed via an iterative bottom-up algorithm with quadratic computational complexity; however, nearly-linear variants also exist. SHAH is rapidly invertible. We use SHAH to define the BAGIDIS semi-distance between images. It compares both the amplitudes and the locations of the SHAH components of the images and is flexible enough to account for feature misalignment. Performance of the SHAH+BAGIDIS methodology is illustrated in regression, classification and clustering problems and shown to be very encouraging. A clear asset of the methodology is its very general scope: it can be used with any images or more generally with data that can be described as graphs or networks.