Computational complexity reduction methods for multiscale recurrent pattern algorithms

Francisco, Nelson C.; M. M. Rodrigues, Nuno; Silva, Eduardo A. B. da; Carvalho, Murilo B. de; Faria, Sergio

http://hdl.handle.net/10400.8/14753

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
90.pdf		349.83 KB	Adobe PDF	Download

Send Feedback

Authors

Francisco, Nelson C.

M. M. Rodrigues, Nuno

Silva, Eduardo A. B. da

Carvalho, Murilo B. de

Faria, Sergio

Abstract(s)

The Multidimensional Multiscale Parser algorithm was originally proposed as a generic lossy data compression algorithm. An 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 an alternative to traditional transform-based encoders, approaching its computational complexity with that of transform-based algorithms.

Keywords

Image Coding Pattern Matching Data Compression

URI

http://hdl.handle.net/10400.8/14753

Citation

N. C. Francisco, N. M. M. Rodrigues, E. A. B. da Silva, M. B. de Carvalho and S. M. M. de Faria, "Computational complexity reduction methods for multiscale recurrent pattern algorithms," 2011 IEEE EUROCON - International Conference on Computer as a Tool, Lisbon, Portugal, 2011, pp. 1-4, doi: 10.1109/EUROCON.2011.5929396.