Creating and sharing knowledge for telecommunications

Computational complexity reduction methods for multiscale recurrent pattern algorithms

Francisco, N. ; Rodrigues, Nuno M. M. ; Silva, E. ; Carvalho, M. ; Faria, S.M.M.

Computational complexity reduction methods for multiscale recurrent pattern algorithms , Proc IEEE Region 8 EUROCON 2011 International Conf. on Computer as a Tool joint with the Conf. on Telecommunications, Lisbon, Portugal, Vol. , pp. - https://doi.org/10.1109/EUROCON.2011.5929396, April, 2011.

Digital Object Identifier: 10.1109/EUROCON.2011.5929396

Abstract
The Multidimensional MuItiscale Parser algorithm was originally proposed as a generic lossy data compression algorithm. A high degree of adaptivity and versatility allowed it to outperform state-of-the-art transform-based compression methods for a wide range of applications, from still images, compound documents, or even ECG's, just to name a few.
However, as other pattern matching algorithms, it presents a high computational complexity. In this paper, we investigated several techniques that allowed to considerably reduce both the encoder's and the decoder's computational complexity, with marginal R-D performance losses. The most important reduction was achieved on the decoder, that reduced up to 95 % the time required by the previous method. These improvements contribute to affirm MMP as au alternative to traditional transform-based encoders, approaching its computational complexity with that of transform-based algorithms.