Browse Prior Art Database

AN INVESTIGATION OF THE DISCRETE KARHUNEN-LOEVE TRANSFORM: METHODS AND COMPUTATIONAL ASPECTS

IP.com Disclosure Number: IPCOM000128463D
Original Publication Date: 1983-Dec-01
Included in the Prior Art Database: 2005-Sep-16
Document File: 8 page(s) / 37K

Publishing Venue

Software Patent Institute

Related People

Michael R. Betker: AUTHOR [+5]

Abstract

In this report we discuss some of the computational aspects of the discrete Karhunen-Loeve transform. We examine the implementation of the algorithm in an image data compression scheme. We further discuss extension of the algorithm using a high speed floating point computer system.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 8

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AN INVESTIGATION OF THE DISCRETE KARHUNEN- LOEVE TRANSFORM: METHODS AND COMPUTATIONAL ASPECTS

Michael R. Betker,

Edward J. Delp and
T.N. Mudge
CRL-TR-35-83

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY

December 1983

Room l079, East Engineering Building
Ann Arbor, Michigan 48109
USA
Tel: (313) 763-8000

ABSTRACT

In this report we discuss some of the computational aspects of the discrete Karhunen-Loeve transform. We examine the implementation of the algorithm in an image data compression scheme. We further discuss extension of the algorithm using a high speed floating point computer system.

Introduction

The Discrete Karhunen-Loeve (K-L) transform has various applications in source coding, 1

image processing, 2 speech processing, 3 and pattern recognition.4 The K-L transform was first used by Huang and Schultheiss5as a block coder to produce uncorrelated transform coefficients. They showed that the performance of this optimal transform coding technique was similar to the optimal block code when a mean square error distortion was used and a Gaussian assumption made on the input. Habibi and Wintz6 later extended this result and there has been a great deal of interest in transform coding. Recently the Cosine transform has been shown to approximate the K-L transform for a wide class of random processes. 7 The issues to be

1 T. T. Y. Huang and P. M. Schultheiss, "Block Quantization of Correlated Gaussian Random Variables," IRE Trans. Communications, Vol. COM-11, No. 9, Sept. 1963, pp. 289-296.

2 A. Rosenfeld and A. C. Kak, Digital Picture Processing, Academic Press, 1976.

3 A. K. Jain, "A fast Karhunen-Loeve transform for a class of random processes," IEEE Trans. Communications, vol. COM-24, Sept. 1976, pp. 1023-1029.

4 K. Fukunaga, Introduction to Statistical Pattern Recognition, Academic Press, 1972.

5 T. T. Y. Huang and P. M. Schultheiss, "Block Quantization of Correlated Gaussian Random Variables," IRE Trans. Communications, Vol. COM-11, No. 9, Sept. 1963, pp. 289-296.

6 A. Habibi and P. A. Wintz, "Image coding by linear transformation and block quantization," IEEE Trans. Communications, vol. COM-19, Feb. 1971, pp. 50-62.

7 A. K. Jain, "A fast Karhunen-Loeve transform for a class of random processes," IEEE Trans. Communications, vol. COM-24, Sept. 1976, pp. 1023-1029. H. Kitajima, "A Symmetric Cosine Transform," IEEE Trans Computers,

University of Michigan Computing Research Laboratory Page 1 Dec 01, 1983

Page 2 of 8

AN INVESTIGATION OF THE DISCRETE KARHUNEN-LOEVE TRANSFORM: METHODS AND COMPUTATIONAL ASPECTS

investigated in this report are methods for implementing the transform, and the speed of these methods. While transforms such as the Fourier transform and Cosine transform have fast algorithms, the K-L transform has no such fast algorithm. The goal of this study is to determine the computational needs of the K-L transform and investigate the attainable speed...