Generalized S Transform
Michael D. Adams, Member, IEEE, Faouzi Kossentini, Senior Member, IEEE, and
Rabab Ward, Fellow, IEEE
Dept. of Elec. and Comp. Engineering, University of British Columbia,
Vancouver, BC, Canada V6T 1Z4
Abstract
The generalized S transform (GST), a family of reversible integer-to-integer transforms inspired by the S transform, is
proposed. This family of transforms is then studied in detail, by considering topics such as GST parameter calculation, the
effects of using different rounding operators in the GST, and the relationship between the GST and the lifting scheme. Some
examples of specific transforms in the GST family are also given. In particular, a new transform in this family is introduced,
and its practical utility demonstrated.
EDICS Category: 3-COMP (Signal Representation and Compression)
Please address all correspondence concerning this manuscript to:
Michael D. Adams
Department of Electrical and Computer Engineering
University of British Columbia
2356 Main Mall
Vancouver, BC, Canada V6T 1Z4
Phone: 604-822-2872, Fax: 604-822-5949
Email: mdadams@ieee.org
1
Generalized S Transform
Michael D. Adams, Member, IEEE, Faouzi Kossentini, Senior Member, IEEE, and
Rabab Ward, Fellow, IEEE
This work was supported by the Natural Sciences and Engineering Research Council of Canada.
November 28, 2001 DRAFT
2
Abstract
The generalized S transform (GST), a family of reversible integer-to-integer transforms inspired by the S transform, is
proposed. This family of transforms is then studied in detail, by considering topics such as GST parameter calculation, the
effects of using different rounding operators in the GST, and the relationship between the GST and the lifting scheme. Some
examples of specific transforms in the GST family are also given. In particular, a new transform in this family is introduced,
and its practical utility demonstrated.
I. INTRODUCTION
Reversible integer-to-integer transforms have become a popular tool for use in signal coding applications requir-
ing lossless signal reproduction [1–5]. One of the best known transforms of this type is the S transform [3,4,6]. In
this manuscript, we propose the generalized S transform (GST), a family of reversible integer-to-integer transforms
based on the key ideas behind the S transform. We then study the GST in some detail. This leads to a number of
interesting insights about transforms belonging to the GST family (including the S transform amongst others) and
reversible integer-to-integer transforms in general.
The remainder of this manuscript is structured as follows. We begin, in Section II, with a brief discussion of
the notation and terminology used herein. The S transform is then introduced in Section III, and the GST family
of transforms is defined in Section IV. Sections V and VI proceed to examine GST parameter calculation and
the effects of using different rounding operators in the GST. Some examples of well known transforms belonging
to the GST family are given in Section VII, and in Section VIII, we present a new GST-based transform, and
demonstrate its utility for image coding applications. Finally, we conclude in Section IX with a summary of our
results and some closing remarks.
II. NOTATION AND TERMINOLOGY
Before proceeding further, a short digression concerning the notation and terminology used in this manuscript
is appropriate. The symbols
and
denote the sets of integer and real numbers, respectively. Matrix and vector
quantities are indicated using bold type. The symbol
is used to denote the
identity matrix. In cases
where the size of the identity matrix is clear from the context, the subscript
may be omitted. A matrix
is
said to be unimodular if
. The
th minor of the
matrix
, denoted
!#"%$&'() *
, is the
+-,.(/0+1,2(
matrix formed by removing the
th row and
th column from
. The notation
34'567
denotes
the probability of event
6
, and the notation
896:
denotes the expected value of the quantity
6
.
Suppose that
;
denotes a rounding operator. In this manuscript, such operators are defined only in terms of a
single scalar operand. As a notational convenience, however, we use an expression of the form
;<=>
, where
=
is
November 28, 2001 DRAFT
3
a vector/matrix quantity, to denote a vector/matrix for which each element has had the operator
;
applied to it. A
rounding operator
;
is said to be integer invariant if it satisfies
; 6:4 6
for all
6
(1)
(i.e.,
;
leaves integers unchanged). As customary, in this manuscript, we consider only integer-invariant rounding
operators. For obvious reasons, rounding operators that are not integer invariant are of little practical value. At
times, we focus our attention on six specific rounding operators (i.e., the floor, biased floor, ceiling, biased ceiling,
truncation, and biased truncation functions) which are defined below.
For
, the notation
denotes the largest integer not more than
(i.e., the floor function), and the notation
denotes the smallest integer not less than
(i.e., the ceiling function). In passing, we also note that the floor
and ceiling functions satisfy the relationship
,
,
for all
(2)
The biased floor, biased ceiling, truncation, and biased truncation functions are defined, respectively, as
& &'
"
<
<,
(3)
*'
$
<
!"
#
"$
for
&%('
for
&)('
and (4)
*'
$
<
!
"
#
"
$
& &'
for
&%('
"
for
&)('
(5)
The mapping associated with the
*'
$
function is essentially equivalent to traditional rounding (to the nearest
integer). The fractional part of a real number
is denoted
*
'
+
and defined as
*
'
+
-,
.
,
/
Thus, we have that
'&0(*
'
+
1)
for all
. We define the
! &
function as
! & 6>
32
4,
6 ,
52
6
76829
where
6
32
. (6)
This function simply computes the remainder obtained when
6
is divided by
2
, with division being defined in such
a way that the remainder is always nonnegative. From (6) and (2), we trivially have the identities
6
76829
;:<=/>@?BAC:D EGF
E
for
2IH
J'
(7)
6
76829
:BKL=/>@?BAM<:D EGF
E
for
2IH
J'N
(8)
November 28, 2001 DRAFT
4
III. S TRANSFORM
One of the simplest and most ubiquitous reversible integer-to-integer mappings is the S transform [2–4], a
nonlinear approximation to a particular normalization of the Walsh-Hadamard transform. The S transform is also
well known as the basic building block for a reversible integer-to-integer version of the Haar wavelet transform [2–
4]. The forward S transform maps the integer vector
:
:
to the integer vector
E
E
, and is defined most
frequently (e.g., equation (1) in [3] and equation (3.3) in [4]) as
E
E
A :
KL:
F
:
@<:
The corresponding inverse transform is given (e.g., equation (2) in [3]) by
:
:
<E
where
4,
.2
2
(
(9)
While the S transform can be viewed as exploiting the redundancy between the sum and difference of two
integers, namely that both quantities have the same parity (i.e., evenness/oddness), this overlooks a much more
fundamental idea upon which the S transform is based. That is, as noted by Calderbank et al. [2], the S transform
relies, at least in part, on lifting-based techniques.
IV. GENERALIZED S TRANSFORM
By examining the S transform in the context of the lifting scheme, we are inspired to propose a natural extension
to this transform, which we call the generalized S transform (GST). For convenience in what follows, let us define
two integer vectors
=
and
as
=
,
:
:
:
,
E
E
!
E
"
The forward GST is a mapping from
=
to
of the form
$#
=
;0*
&%
, (
"#
=>
(10)
where
%
is real matrix of the form
%
,
(')*
,+
+.-
+
/
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
/0
132
4
#
is a unimodular integer matrix defined as
#
,
5')
*6
87
6
87
6
87
-
6
87
6
97
6
97
6
97
-
6
97
6
-
7
6
-
7
6
-
7
-
6
-
7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
97
6
97
6
97
-
6
97
132
4
November 28, 2001 DRAFT
- 1
- 2
- 3
- 4
- 5
- 6
前往页