摘要: In fractal compression a signal is encoded by the parameters of contractive transformation whose fixed point (attractor) an approximation original data. Thus coding can be viewed as optimization problem finding in set admissible transformations attractor closest to given signal. The standard scheme based on collage theorem produces only suboptimal solution. We demonstrate reduction from MAXCUT that determining optimal code NP-hard. To our knowledge, this first analysis intrinsic complexity coding. Additionally, we show not approximating algorithm for problem.
uni-konstanz.de
sci-hub.se 参考文章(7)
D. Saupe, R. Hamzaoui, H. Hartenstein, Fractal Image Compression - An Introductory Overview international conference on computer graphics and interactive techniques. ,(1997)
Yuval Fisher, Fractal Image Compression: Theory and Application ,(2011)
Michael Randolph Garey, Johnson: computers and intractability: a guide to the theory of np- completeness (freeman ,(1979)
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
Jianhua Lin, James A. Storer, Martin Cohn, Optimal pruning for tree-structured vector quantization Information Processing and Management. ,vol. 28, pp. 723- 733 ,(1992) , 10.1016/0306-4573(92)90064-7
Jianhua Lin, Vector quantization for image compression: algorithms and performance Brandeis University. ,(1992)
Michael F. Barnsley, Fractals Everywhere ,(1988)