The transform modes in several video-coding standards [41].
Abstract
In this chapter, first we give a brief view of transform-based video coding. Second, the basic matrix decomposition scheme for fast algorithm and hardware-sharing-based integer transform design are described. Finally, two case studies for fast algorithm and hardware-sharing-based architecture designs of discrete integer transforms are presented, where one is for the single-standard multiple-mode video transform-coding application, and the other is for the multiple-standard multiple-mode video transform-coding application.
Keywords
- video coding
- transform coding
- fast algorithm
- matrix factorization
- hardware sharing
- multiple modes
- multiple standards
1. Introduction
Video-coding system has generally utilized block-based transform-coding skills to shrink the data rates by joining quantization and entropy coding. Among some block-based transforms, the discrete cosine transform (DCT) [1] and integer transforms have extensively been used to still image and video-coding specifications, such as JPEG [2], MPEG-1/2 [3, 4], MPEG-4 [5], H.264/AVC [6, 7], AVS [8, 9], VC-1 [10], VP8 [11], and HEVC [12]. Because integer transforms perform the low complexity and effective coding performance, the advanced video coding (AVC) in ITU-T H.264 [6, 7, 13, 14], which is also known as MPEG-4 part 10, applies integer transforms for transform process. The 4 × 4 and 8 × 8 transforms in [13, 14] were calculated exactly to prevent non-adaptation issues of inverse transforms for high-quality moving visual images. The VC-1 specification [10, 15, 16] employed 4 × 4 and 8 × 8 integer transforms, and it was developed by Microsoft Corporation and standardized by the Society of Motion Picture and Television Engineers (SMPTE). The 8 × 8 integer transform is utilized to obtain the high-coding performance in the Audio Video Coding Standard (AVS) for China [8, 9]. In [11], the VP8 video-coding standard was developed for Internet browser applications. The Joint Collaborative Team on Video Coding proposed the high-efficiency video coding (HEVC) specification [12]. By HEVC, the compression efficiency was greatly better than that achieved using the H.264/AVC high-profile-coding specification.
To support the single-standard H.264/AVC video coding, several transform architectures in [17–24] have been developed to approach the multiple transform modes in H.264. To support the single-standard H.265/HEVC video coding, several transform architectures in [25–32] have been developed to approach the multiple transform modes in HEVC. Besides, supporting multiple-standard functions in video coding has been an important issue in multimedia applications recently, such as H.264/AVC, MPEG-1/2/4, VC-1, AVS, and VP8 standards, and several transform architectures in [33–41] have also been developed to complete the multiple transform functions. Owing to the growth of multistandard video-coding applications, how to achieve low-computational complexities and implement by hardware-sharing-based cost-effective architectures simultaneously are interesting research topics for the VLSI design of video codecs.
2. Matrix decomposition preprocessing for fast algorithm and hardware-sharing-based designs
Based on the resemblance property, the 8 × 8 inverse integer transforms [41] in H.264/AVC, AVS, VC-1, VP8, MPEG-1/2/4, and HEVC specifications are revealed in Eq. (1), and Table 1 depicts the coefficient values in the transforms.
Transform sizes | VC-1 | AVS | VP8 | MPEG-1/2/4 | H.264/AVC | HEVC |
---|---|---|---|---|---|---|
4 × 4 | √ | √ | √ | N/A | √ | √ |
8 × 8 | √ | √ | N/A | √ | √ | √ |
16 × 16 | N/A | N/A | N/A | N/A | N/A | √ |
32 × 32 | N/A | N/A | N/A | N/A | N/A | √ |
In Eq. (1), it is decomposed by Eq. (2) as
In Eq. (2),
Thus
and
In (3), “⊕ “ is the direct sum operator, and the two diagonal blocks
By Eq. (1), for VC-1 the values of the coefficient set {
The general 4 × 4 inverse integer transform matrices [41] can be presented in Eq. (5) as
By Eq. (5), for VC-1 the values of the coefficient set {h, i, j} are {17, 22, 10}, and those for VP8 are {128, 167, 70}. Next, those for AVS-M are {2, 3, 1}, and those for H.264/AVC are {1, 1, 0.5}. Finally, those for HEVC are {64, 83, 36}.
3. Case study [32]: single-standard multiple-mode transform design
3.1. Hardware-sharing based 32 × 32 integer core transform for HEVC
The one-dimensional (1D) 32 × 32 inverse core transform for HEVC is described in [30]. By the symmetrical property, the 32 × 32 inverse core transform is presented as
where
By Eqs. (6) and (7),
where
where “⊕” means the direct sum operation, and then
where the permutation matrix
First, the lower half of
Second, the coefficients in a single column vector can be shared. The vector coefficient computations are achieved by integrating several base coefficients [32]. After realizing the column vectors of
Adder tree structures are utilized to calculate the aggregate results for the row vectors
where
where
3.2. Hardware-sharing-based 16 × 16 integer core transform for HEVC
The 16 × 16 integer core transform in [30] changes into
where
where
In Eq. (18),
and
where
By the duplicate processed of
where
where
where
where
3.3. Hardware-sharing-based 8 × 8 integer core transform for HEVC
The 8 × 8 integer transform in [30] is described as
where
where
In Eq. (27),
where
In Eq. (28),
where
where
where
In Eq. (32), the computations of
3.4. Hardware-sharing-based 4 × 4 integer core transform for HEVC
The 4 × 4 integer core transform matrix is indicated as
where
where
In Eq. (34),
In Eq. (36),
where
where
By the abovementioned discussions, the hardware modules of 4 × 4, 8 × 8, and 16 × 16 inverse core transforms are shared to implement
Next, the hardware-sharing-based 16-point inverse transform is described as
Finally, the hardware-sharing-based 32-point inverse transform is depicted as
In this section, the hardware-sharing transform architecture cuts down the hardware cost because the same submodules and coefficients of the transforms are extracted to be shared. Figure 1 illustrates the architecture of the hardware-sharing-based inverse core transform design for 4 × 4/8 × 8/16 × 16/32 × 32 transforms [32].
3.5. Architecture comparison
The proposed 1D inverse core transform in [32] involves four inputs to sustain 4 × 4, 8 × 8, 16 × 16, and 32 × 32 transform modes. Several multiplexers are utilized to acquire the transform outputs of the 32 × 32 inverse core transform by the shared design of 4 × 4, 8 × 8, and 16 × 16 inverse core transforms [32]. Table 2 lists the number of adders and shifters needed to calculate four modes of the 1D inverse core transform for HEVC. The developed architecture in [32] does not require any multiplier, and the fixed-coefficient multiplications are replaced with simple additions and shift operations. Table 3 shows the comparison of three 16-point inverse transform designs. Compared with the previous works in [29] and [31], the applied architecture contains fewer adders. However, several more shifters are required. Compared with the cost of adders, the shifters need lower hardware expense. Thus, the used architecture decreases the hardware cost more efficiently than previous transform schemes do.
Transform sizes | 32 × 32 | 16 × 16 | 8 × 8 | 4 × 4 |
---|---|---|---|---|
No. of shifters | 256 | 93 | 40 | 11 |
No. of adders | 461 | 146 | 64 | 10 |
4. Case study [41]: multiple-standard multiple-mode transform design
4.1. Hardware-sharing design for 8 × 8 transforms mode
For H.264/AVC, the transform matrix is employed as a foundation matrix for the multistandard hardware-sharing scheme. Based on Eq. (3), the cost of the upper diagonal matrix in Eq. (43) is eight adders and two shifters.
where
where
where and
where
where
By Eq. (3), on the other side, the down diagonal matrix
where
For AVS, the
where
For VC-1, the
where
where
4.2. Hardware-sharing design for 4 × 4 transforms mode
For AVS-M, the matrix
where
where
where
4.3. Architecture comparison
The applied hardware-sharing-based 1D multistandard inverse integer transform scheme has two inputs, which sustain 4 × 4 and 8 × 8 transform modes. The hardware blocks of processing the 4 × 4 inverse transforms are shared with that of the upper diagonal matrix
Different 1D inverse integer transform modes | No. of adders | No. of shifters |
---|---|---|
Individual designs without hardware shares | 336 | 180 |
Hardware-sharing-based design in Section 4 | 82 | 90 |
To implement the discussed architecture, a cell-based VLSI design flow is utilized to design, simulate, and verify the cost-effective hardware-sharing architecture. For fair comparisons among different transform structures, the normalized mode gain, which is required to normalize the gate counts, is described as follows: By matrix dimensions and without missing generality [40], the normalized mode gains defined for the 32 × 32, 16 × 16, 8 × 8, and 4 × 4 inverse integer transform matrices are 16, 4, 1, and 1/4, respectively.
The hardware-sharing-based design in Section 3 supports 4 × 4, 8 × 8, 16 × 16, and 32 × 32 inverse transform modes for HEVC. Thus, the normalized mode gain of the design is 21.25 (i.e., 16 + 4 + 1 + 0.25). Similarly, five 8 × 8 and five 4 × 4 inverse transform functions are provided by the hardware-shared design in Section 4. Therefore, the normalized mode gain is assigned by 6.25 (i.e., 5 + 1.25) [41]. Afterwards, the normalized gate counts are defined by [40, 41]
Table 5 shows the hardware cost comparisons among different 1D multiple transform architectures, which includes single-standard multiple-mode [32] and multiple-standard multiple-mode [41] transform designs.
Architecture | Ahmed et al. [29] | Shen et. al. [26] |
Martuza et. al. [28] |
Qi et al. [36] | Wang et al. [38] |
||
---|---|---|---|---|---|---|---|
Gate counts | 144.8K | 115.7 K | 134.8 K | 39.4 K | 18 K | 23.06 K | 27.4 K |
Normalized mode gain | 21.25 | 21.25 | 25.75 | 5 | 3.5 | 4.5 | 6.25 |
Normalized gate counts | 6.81 K | 5.44 K | 5.23 K | 7.88 K | 5.14 K | 5.12 K | 4.38 K |
Supporting modes | Single-standard Multiple-mode |
Single-standard Multiple-mode |
Multiple- standard Multiple- mode |
Multiple-standard Multiple-mode |
Multiple-standard Multiple- mode |
Multiple- standard Multiple- mode |
Multiple-standard Multiple-mode |
Supporting standards/Transforms | 4 × 4, 8 × 8, 16 × 16, 32 × 32 modes |
4 × 4, 8 × 8, 16 × 16, 32 × 32 modes |
4 × 4,8 × 8 modes mode; 8 × 8, 16 × 16, 32 × 32 modes |
4 × 4, 8 × 8 modes |
4 × 4, 8 × 8 modes; 8 × 8 mode |
4 × 4, 8 × 8 modes; 8 × 8 mode |
4 × 4, 8 × 8 modes; |
5. Conclusion
For the single-standard multiple-mode transform design, this chapter discussed the 4 × 4, 8 × 8, 16 × 16, and 32 × 32 inverse core transforms in HEVC with a cost-effective and hardware-efficient design. By the symmetrical characteristics of the elements, the core transform matrices were factorized into several submatrices. Thus, the hardware of the (
For the multiple-standard multiple-mode transform design, this chapter also discussed the fast algorithm and hardware-sharing-based design of 4 × 4 and/or 8 × 8 inverse transforms among H.264/AVC, VC-1, HEVC, MPEG-1/2/4, AVS, and VP8 for multistandard video decoders. By only shifters and adders, the decomposition scheme of matrices was used to develop the hardware-shared scheme. The used structure in Section 4 decreased the number of shifters and adders by 50 and 75% more than the individual fast algorithm-based implementation did. Besides, for VLSI implementation, the design in Section 4 requires less normalized gate counts than the designs do in [26, 28, 36, 38].
Acknowledgments
This work was supported by Ministry of Science and Technology, Taiwan, R.O.C. under Grant MOST 105-2221-E-005-078.
References
- 1.
J. R. Rao and P. Yip, Discrete Cosine Transform: Algorithms, Advantage, Applications, New York, NY: Academic, 1990. - 2.
ISO/IEC JTC 1/SC 29/WG 1—Coding of Still Pictures, 2009. - 3.
ISO/IEC 11172-2 MPEG-1 Video Coding Standard, Information Technology—Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1,5 Mbit/s – Part 2: Video, 1993. - 4.
ISO/IEC 13818-2 MPEG-2 Video Coding Standard, Information Technology—Generic Coding of Moving Pictures and Associated Audio Information: Video, 1995. - 5.
ISO/IEC 14496-2 MPEG-4 Video Coding Standard, Information Technology—Coding of Audio-Visual Objects – Part 2: Visual, 2004. - 6.
T. Wiegand and G. Sullivan, Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification, (ITU-T rec. H.264/ISO/IEC 14496-10 AVC, presented at Joint Video Team (JVC) of ISO/IEC MPEG and ITU-T VCEG), 2003. - 7.
Iain E. G. Richardson, H.264 and MPEG-4 Video Compression—Video Coding for Next-generation Multimedia, John Wiley & Sons, 111 River Street, Hoboken NJ07030-5774, New Jersey, United States, 2003. - 8.
W. Gao, C. Reader, F. Wu, Y. He, L. Yu, H. Lu, S. Yang, T. Huang, and X. Pan, AVS—The Chinese Next-Generation Video Coding Standard, National Association of Broadcasters (NAB) Conference, 2004. - 9.
L. Yu, S. Chen, and J. Wang, Overview of AVS video coding standards, Signal Processing: Image Communication, vol. 24, issue 4, pp. 247–262, April 2009. - 10.
SMPTE, Standard for Television: VC-1 Compressed Video Bitstream Format and Decoding Process, SMPTE 421M-2006. - 11.
J. Bankoski, P. Wilkins, and Y. Xu, Technical overview of VP8, an open source video codec for the web, IEEE International Conference on Multimedia and Expo (ICME), pp. 1–6, July 11–15, 2011. - 12.
M. T. Pourazad, C. Doutre, M. Azimi, and P. Nasiopoulos, HEVC: the new gold standard for video compression: How does HEVC compare with H.264/AVC ?, IEEE Consumer Electronics Magazine, vol. 1, pp. 36–46, July 2012. - 13.
H. S. Malvar, A. Hallapuro, M. Karczewicz, and L. Kerofsky, Low-complexity transform and quantization in H.264/AVC, IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 598–603, July 2003. - 14.
S. Gordon, D. Marple, and T. Wiegand, Simplified use of 8x8 transforms—updated proposal and results, JVT-K028, 11th Meeting, Munich, Germany, March 2004. - 15.
S. Srinivasan, P. Hsu, T. Holcomb, K. Mukerjee, S. L. Regunathan, B. Lin, J. Liang, M. C. Lee, and J. Ribas-Corbera, Windows media video 9: overview and applications, Signal Processing: Image Communication, vol. 19, issue 9, pp. 851–875, October 2004. - 16.
S. Srinivasan and S. L. Regunathan, An overview of VC-1, Proceedings of the SPIE, Visual Communications and Image Processing (VCIP), Beijing, China, vol. 5960, pp. 720–728, July 2005. - 17.
T. C. Wang, Y. W. Huang, H. C. Fang, and L. G. Chen, Parallel 4x4 2D transform and inverse transform architecture for MPEG-4 AVC/H.264, IEEE International Symposium on Circuits and Systems, vol. 2, pp. 800–803, 2003. - 18.
Z. Y. Cheng, C. H. Chen, B. D. Liu, and J. F. Yang, High throughput 2-D transform architectures for H.264 advanced video coders, IEEE Asia-Pacific Conference on Circuits and Systems, pp. 1141–1144, December 2004. - 19.
K. H. Chen, J. I. Guo, and J. S. Wang, A high-performance direct 2-D transform coding IP design for MPEG-4 AVC/H.264, IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 4, pp. 472–483, April 2006. - 20.
G. A. Su and C. P. Fan, Cost effective hardware sharing architecture for fast 1-D 8x8 forward and inverse integer transforms of H.264/AVC high profile, IEEE Asia Pacific Conference on Circuits and Systems, pp. 1332–1335, November 2008. - 21.
T. T. T. Do and T. M. Le, High throughput area-efficient SoC-based forward/inverse integer transform for H.264/AVC, IEEE International Symposium on Circuits and Systems, pp. 4113–4116, May 2010. - 22.
W. Hwangbo and C. M. Kyung, A multi-transform architecture for H.264/AVC high-profile coders, IEEE Transactions on Multimedia, vol. 12, no. 3, pp. 157–167, April 2010. - 23.
M. L. Hsia and Oscal T. C. Chen, Low-complexity inverse integer transform in H.264/AVC, IEEE International Conference on Multimedia & Expo, pp. 826–830, July 2010. - 24.
M. Nadeem, S. Wong, and G. Kuzmanov, Inverse integer transform in H.264/AVC intra-frame encoder, Sixth IEEE International Symposium on Electronic Design, Test and Application, pp. 228–233, 2011. - 25.
R. Jeske, J. C. de Souza, G. Wrege, R. Conceicao, M. Grellert, J. Mattos, and L. Agostini, Low cost and high throughput multiplierless design of a 16 point 1-D DCT of the new HEVC video coding standard, Conference on Programmable Logic (SPL), pp. 1–6, March 2012 - 26.
S. Shen, W. Shen, Y. Fan, and Xiaoyang Zeng, A unified 4/8/16/32-point integer IDCT architecture for multiple video coding standards, IEEE International Conference on Multimedia and Expo (ICME), pp. 788–793, July 2012. - 27.
W. Zhao, T. Onoye, and T. Song, High-performance multiplierless transform architecture for HEVC, IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1668–1671, 2013. - 28.
M. Martuza, K. A. Wahid, Implementation of a cost shared transform architecture for multiple video codecs, Journal of Real-Time Image Processing, vol. 10, no. 1, pp. 151–162, March 2015. - 29.
A. Ahmed, M. U. Shahid, and A. Rehman, N point DCT VLSI architecture for emerging HEVC standard, VLSI Design, volume 2012, Article ID 752024, pp. 1–13, 2012. - 30.
Joint Collaborative Team—Video Coding, CE10: Core transform design for HEVC, JCTVC-G495, Geneva, Switzerland, 21–30, November 2011. - 31.
M. N. Haggag, M. El-Sharkawy, and G. Fahmy, Efficient fast multiplication-free integer transformation for the 2-D DCT H.265 standard, IEEE International Conference on Image Processing, pp. 3769–3772, September 2010. - 32.
C. W. Chang, H. F. Hsu, C. P. Fan, C. B. Wu, and Robert C. H. Chang, A fast algorithm-based cost-effective and hardware-efficient unified architecture design of 4×4, 8×8, 16×16, and 32×32 inverse core transforms for HEVC, Journal of Signal Processing Systems, vol. 82, no. 1, pp. 69–89, 2016. - 33.
S. Lee and K. Cho, Architecture of transform circuit for video decoder supporting multiple standards, Electronics Letters, vol. 44, no. 4, pp. 274–275, February 2008. - 34.
C. P. Fan and G. A. Su, Efficient low cost sharing design of fast 1-D inverse integer transform algorithms for H.264/AVC and VC-1, IEEE Signal Processing Letters, vol. 15, pp. 926–929, December 2008. - 35.
G. A. Su and C. P. Fan, Low-cost hardware sharing architecture of fast 1-D inverse transforms for H.264/AVC and AVS applications, IEEE Transactions on Circuits and Systems, Part II, vol. 55, no. 12, pp. 1249–1253, December 2008. - 36.
H. Qi, Q. Huang, and W. Gao, A low-cost very large scale integration architecture for multistandard inverse transform, IEEE Transactions on Circuits and Systems, Part II, vol. 57, no. 7, pp. 551–555, July 2010. - 37.
Y. K. Lai and Y. F. Lai, A Reconfigurable IDCT architecture for universal video decoders, IEEE Transactions on Consumer Electronics, vol. 56, no. 3, pp. 1872–1879, August 2010. - 38.
K. Wang, J. Chen, W. Cao, Y. Wang, L. Wang, and J. Tong, A reconfigurable multi-transform VLSI architecture supporting video codec design, IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 58, no. 7, pp. 432–436, July 2011. - 39.
K. Wahid, M. Martuza, M. Das, and C. McCrosky, Resource shared architecture of multiple transforms for multiple video codecs, 24th Canadian Conference on Electrical and Computer Engineering (CCECE), pp. 000947–000950, 2011. - 40.
C. P. Fan, C. W. Chang, and S. J. Hsu, Cost effective hardware sharing design of fast algorithm based multiple forward and inverse transforms for H.264/AVC, MPEG-1/2/4, AVS, and VC-1 video encoding and decoding applications, IEEE Transactions on Circuits and Systems for Video Technology, vol. 24, no. 4, pp. 714–720, April 2014. - 41.
C. W. Chang, H. F. Hsu, and C. P. Fan, High-efficiency multiple 4x4 and 8x8 inverse transform design with a cost-effective unified architecture for multistandard video decoders, 2014 IEEE Asia Pacific Conference on Circuits & Systems, Okinawa, Japan, pp. 507–510, November 2014. - 42.
C. W. Chang, Fast algorithm based cost-effective and hardware-sharing architecture designs of multiple-mode discrete integer transforms for multi-standard video Codecs, Ph.D. dissertation, National Chung Hsing University, Taiwan, 2015. - 43.
http://en.wikipedia.org/wiki/Kronecker_product