Fast unitary heap transforms: Methods and application in digital signal and image processing

A novel approach is presented for composing discrete unitary transforms that are induced by input signals, i.e., signal-generators, or by transformations between the signals. Such transforms can be parameterised and the parameters are defined by signal-generators, and certain systems of decision equations, of which specified cases are considered. Transformations to be considered are the discrete signal-induced heap transforms (DsiHT). We focus on the heap transforms generated by input signals, without considering statistics of input signals being realizations of random processes. This difficult and interesting problem is beyond the contents of our study. One class of DsiHT is described in detail, the transforms that we call the discrete heap transforms and modified heap transforms which are defined by Givens rotations. The transforms are defined in the time domain, as well as in an angle domain. Properties of these transforms are described and illustrated. Discrete heap transforms are fast, because of a simple form of decomposition of their matrices. For instance, the direct calculation of the N-point discrete heap transform requires no more 5(N - 1) multiplications, 2(N - 1) additions, plus 3(N - 1) trigonometric operations. Fast algorithms of calculation of the direct and inverse heap transforms do not depend on the length of the processed signals. We demonstrate the applications of the heap transforms for transformation and reconstruction of one-dimensional signals and two-dimensional images. In this work the heap transforms is analysed and applied for image enhancement and signal and image filtration. Since the generators can be selected in different ways to make the information invisible and they can be used as keys for recovering information, we describe the application of the heap transform for image cryptography, too. Different models of generating the heap transformations in the 1-D and 2-D cases with different paths are described and examples are given.