Abstract—It is well known that the discrete cosine transform
(DCT) and Karhunen–Loève transform (KLT) are two good
representatives in image and video coding: the first can be implemented
very efficiently while the second offers the best R-D
coding performance. In this work, we attempt to design some
new transforms with two goals: i) approaching to the KLT’s R-D
performance and ii) maintaining the implementation cost no
bigger than that of DCT. To this end, we follow a cascade structure
of multiple butterflies to develop an iterative algorithm: two out
of N nodes are selected at each stage to form a Givens rotation
(which is equivalent to a butterfly); and the best rotation angle
is then determined by maximizing the resulted coding gain. We
give the closed-form solutions for the node-selection as well as
the angle-determination, together with some design examples to
demonstrate their superiority.