Journal of the Korea Academia-Industrial cooperation Society Vol. 17, No. 11 pp. 20-25, 2016 http://dx.doi.org/10.5762/kais.2016.17.11.20 ISSN 1975-4701 / eissn 2288-4688 고해상도영상의효과적인처리를위한블록버퍼기반의저복잡도무손실프레임메모리압축방법 김종호순천대학교멀티미디어공학과 Lossless Frame Memory Compression with Low Complexity based on Block-Buffer Structure for Efficient High Resolution Video Processing Jongho Kim Department of Multimedia Engineering, Sunchon National University 요약본논문에서는고해상도영상의효과적인처리를위한블록버퍼기반의저복잡도무손실프레임메모리 (frame memory) 압축방법을제안한다. 제안하는압축방법은공간적상관도를제거하기위하여블록단위 MHT (modified Hadamard transform) 를사용하고, 엔트로피부호화를위하여 AGR (adaptive Golomb-Rice) 부호화기법을적용하여저복잡도무손실압축및효과적인하드웨어구현을달성한다. MHT 는가산기와 1비트오른쪽시프트 (1-bit right shift) 연산만으로구성되어있고, AGR은별도의메모리공간및메모리접근동작 (memory access operation) 을포함하지않아저복잡도구현이용이하다. 기존의저복잡도무손실압축방법과비교하여제안한알고리즘은압축률측면에서우수한성능을나타내고, 기존코덱 (codec) 의구조를크게수정하지않으면서화질의열화없이하드웨어장치에적용될수있음을다양한영상에대한실험및복잡도분석을통해보인다. 또한제안한방법은메모리접근동작을필요로하지않아하드웨어구현을위한비용을최소화할수있어, Fill HD급이상의고해상도영상을효과적으로처리하는데유용하다. Abstract This study addresses a low complexity and lossless frame memory compression algorithm based on block-buffer structure for efficient high resolution video processing. Our study utilizes the block-based MHT (modified Hadamard transform) for spatial decorrelation and AGR (adaptive Golomb-Rice) coding as an entropy encoding stage to achieve lossless image compression with low complexity and efficient hardware implementation. The MHT contains only adders and 1-bit shift operators. As a result of AGR not requiring additional memory space and memory access operations, AGR is effective for low complexity development. Comprehensive experiments and computational complexity analysis demonstrate that the proposed algorithm accomplishes superior compression performance relative to existing methods, and can be applied to hardware devices without image quality degradation as well as negligible modification of the existing codec structure. Moreover, the proposed method does not require the memory access operation, and thus it can reduce costs for hardware implementation and can be useful for processing high resolution video over Full HD. Keywords : AGR, Block-based MHT, Frame memory compression, High resolution video, Lossless image compression 1. 서론 영상압축기술은영상데이터의효과적인전송및저 장과하드웨어자원의효율적인이용을위한요구에따라발전해왔다. 압축되지않은비디오데이터는상당한저장공간및전송대역폭 (bandwidth) 을필요로하는데, * Corresponding Author : Jongho Kim (Sunchon National Univ.) Tel: +82-61-750-3835 email: jhkim@sunchon.ac.kr Received October 31, 2016 Revised November 9, 2016 Accepted November 10, 2016 Published November 30, 2016 20
고해상도영상의효과적인처리를위한블록버퍼기반의저복잡도무손실프레임메모리압축방법 영상압축은이를효과적으로절약할수있는방법이다 [1]. 영상압축알고리즘은압축과복원과정에서정보의손실이전혀없는무손실 (lossless) 압축과영상데이터의일부를제외시키되인간시각시스템 (HVS; human visual system) 에의해영상품질의손실이검출되기어렵게하여압축률을높이는데중점을둔손실 (lossy) 압축의두가지방식으로구분된다 [2]. 최근 LCD (liquid crystal display) 등의디스플레이장치와대용량비디오데이터를원활하게처리할수있는 DSP (digital signal processing) 기술의발전및메모리비용의지속적인감소등으로인해 Full HD급 (1920 1080) 이상의고해상도영상의활용이보편화되고있다. 이러한영상을압축하기위하여 H.264/AVC 및 HEVC (high efficiency video coding) 등의국제표준이발표되었는데, 이러한기법에서는압축성능을향상시키기위하여더욱많은내부프레임메모리를필요로하고있다 [3-5]. 즉, 고해상도영상에대한처리, 1/4 및 1/8 이상의부화소단위와다중참조프레임움직임예측 / 보상등의과정에서많은프레임메모리를요구한다. 따라서영상압축을포함한영상시스템의비용을낮추고고해상도영상의효과적인활용을위하여프레임메모리의크기를줄여야할필요성이지속적으로제기되고있다 [1]. 고해상도영상의효과적인처리및디스플레이를위하여크게두가지접근법이제안되고있는데, 디스플레이장치에포함된프레임버퍼 (frame buffer) 를줄이는방법과영상의압축및복원을위한코덱 (codec) 에포함된프레임메모리 (frame memory) 를줄이는방법이그것이다. 두경우모두전체적인영상시스템의효율을향상시키기위한목적이므로무손실압축방식을고려하되, 저복잡도의연산이중요한요소로포함되어야한다. 디스플레이장치를위한프레임버퍼를압축하기위해서는장치의특성을반영하여주로라인 (line) 단위의압축방법이제안된반면, 코덱내부의프레임메모리를압축하기위해서는많은비디오압축알고리즘이블록 (block) 단위처리를수행하는점을고려하여블록단위의압축방법이제안되어왔다 [6-11]. 저복잡도를갖는무손실압축에관한많은연구가수행되어왔는데, 이들중몇가지는비디오코덱을위한프레임메모리압축과관련이있다. Song과 Shimamoto 는 H.264/AVC 비디오복호기의프레임메모리를줄이기위한무손실압축방식을제안하였는데, DAP (differential of adjacent pixel) 과 Huffman 부호기의결합을통해하드웨어구현을쉽게하였다 [9]. Lee et al. 도 H.264/AVC 복호기를위한방법을제시하였는데, 이는복호기자체의구조를이용하여프레임메모리의크기를줄였다 [12]. 무손실영상압축을위한국제표준인 JPEG-LS를고려할수있는데, 이는 JPEG 및 JPEG2000 과같은국제표준에비해비교적저복잡도를갖는다 [13]. 그러나하드웨어구현관점에서많은곱셈기를필요로하고, 압축된비트스트림이임의접근 (random access) 을허용하지않기때문에비디오코덱의프레임메모리감소를위한저복잡도방법으로직접적용하기어렵다. Lee는 MPEG-2 비디오복호기의하드웨어구조를고려한알고리즘을제안하였는데, 메모리소비를줄이기위하여영상품질을떨어뜨리는양자화과정을도입하였다 [14]. 본논문에서는고해상도비디오코덱을위한저복잡도의무손실프레임메모리압축및복원알고리즘에초점을맞춘다. 앞서언급한바와같이, 고해상도영상을효율적으로처리하기위해서프레임메모리의감소와이의하드웨어구현을위한저복잡도조건을고려하도록한다. 더욱이압축코덱내부의프레임메모리에서영상품질에변화가생기면전체영상시스템의성능에영향을미치기때문에손실압축방법은피하도록한다. 제안하는방법은입력영상을일정크기의블록으로나누고, 각블록에대해변형하다마드변환 (MHT; modified Hadamard transform) 과적응적 Golomb-Rice (AGR; adaptive GR) 부호기를적용한다. 다양한실험을통해제안하는알고리즘이기존방법 [9, 14] 과비교하여향상된압축성능을보이면서계산복잡도가낮게유지됨을보이도록한다. 본논문의구성은다음과같다. 2장에서는프레임메모리를압축하기위하여제안하는저복잡도의무손실압축알고리즘의구조를자세히기술한다. 3장에서는다양한영상에대하여제안한방법의성능평가결과를보이고, 결론및향후과제를 4장에서제시한다. 2. 제안하는압축알고리즘 2.1 제안하는알고리즘의구조고해상도영상의효과적인처리를위한저복잡도무손실프레임메모리압축알고리즘의전체적인흐름은 Fig. 1과같다. 21
한국산학기술학회논문지제 17 권제 11 호, 2016 s 0 s 1 h 0 (DC) h 1 8 8 block input s 2 h 2 8-point MHT (horizontal then vertical application) s 3 s 4 h 3 h 4 s 5 h 5 DC Zigzag Scan and Rice Mapping AC Adaptive Golomb-Rice Coding Bitstream Formatting Bitstream Segment s 6 h 6 s 7 h 7 Fig. 2. Signal flow of 8-point MHT MPEG 표준에서사용되고그효과가검증된지그재그 (zigzag) 스캔방식을사용한다. 또한 AGR 부호기는음이아닌수를입력으로하는반면, 변환계수는음의값을가질수있기때문에변환계수를음이아닌수로변환해야한다. 이는보통식 (1) 의 Rice 매핑에의해수행된다. Fig. 1. Overall flow diagram of the proposed algorithm 제안하는알고리즘은기존압축코덱의방식을고려하여 8 8 크기의블록 (block) 을입력으로하고, 해당블록에대한압축된비트스트림세그먼트 (bit-stream segment) 를최종출력으로한다. 각블록에대해 8-point MHT를가로및세로방향으로적용하여하나의 DC와 63개의 AC 성분을생성한다. 이후, 지그재그 (zigzag) 스캔을거쳐 DC 계수는고정길이부호 (FLC; fixed-length code) 로부호화되고, Rice 매핑 (mapping) 과정을거쳐재표현된 AC 계수들은 AGR 부호기를통해가변길이부호 (VLC; variable length code) 로부호화된다. 이후압축된비트스트림세그먼트를일정한규칙에의해구성하는포맷팅 (formatting) 과정이진행된다. 2.2 변형하다마드변환 (MHT) 제안하는방법에서는영상의공간적상관도를제거하기위하여 Yoo et al. 의 MHT를 2차원적용하도록한다 [15]. MHT는가산기와 1비트오른쪽시프트 (1-bit right shift) 연산만으로실행할수있어, 하드웨어구현에매우유리하다. Fig. 2는 8-point MHT의신호흐름도를나타내는데, 점선은부호반전을의미하고, (shift right) 은 1비트오른쪽시프트연산을의미한다. MHT 수행후얻어진계수에대해 AGR 부호화를적용하기위해서는 2차원신호를 1차원형태로정렬해야할필요가있다. 이를위하여본논문에서는 JPEG 및 (1) 이때, n은변환계수를나타내고, p는 AGR 부호기의입력값을의미한다. 또한, p의 LSB (least significant bit) 가 n의부호를나타내고, n의크기는 p를 1비트오른쪽시프트연산하여간단히구할수있기때문에 p에서 n으로의역매핑은매우간단하다. 2.3 적응적 Golomb-Rice 부호화 (AGR) 지그재그스캔및 Rice 매핑을거쳐 1차원정렬된 MHT 계수는 AGR 부호기에의해엔트로피부호화 (entropy coding) 과정이수행된다. AGR 부호화는 GR 부호화에기반한적응적부호화기법으로, 동적 Golomb-Rice 부호화라고도한다. GR 부호화는양면기하분포 (two-sided geometric distribution) 를갖는정수에대해최적 Huffman 부호화를근사화한다고알려져있다 [16]. 또한 Huffman 부호화에비해복잡도가낮고, 부호화테이블저장을위한 ROM (read-only memory) 을필요로하지않아하드웨어시스템에서구현이용이하다. GR 부호화는비트시프트연산을이용하여 2에의한곱셈과나눗셈을수행하거나, 비트마스크 (mask) 연산을통해나머지 (remainder) 를매우빠르게구할수있다. 더욱이 GR 부호화는손쉽게적응적방식으로이용될수있는반면, 적응적 Huffman 부호화는많은계산량을필요로한다. 이와같은다양한장점으로인해 GR 부호화는 JPEG-LS 22
고해상도영상의효과적인처리를위한블록버퍼기반의저복잡도무손실프레임메모리압축방법 및 H.264/AVC 등과같은무손실및손실영상압축방법에서저복잡도및고효율엔트로피부호화를위해널리사용된다 [17]. For a 8 8 block Bitstream segment for one block k value (3 bits) DC (8 bits) ACs k value (3 bits) DC (8 bits) ACs Fig. 4. Bitstream alignment format for each block Read each AC coeff. for a block 3. 실험및결과 Calculate the GR code length for k = 1 to 8 Select the minimum GR code length Store the k value of the minimum GR code length Fig. 3. Flow diagram of AGR coding for a block 각입력블록에대한 AGR 부호화의흐름을 Fig. 3에나타내었다. 최대의압축성능을얻기위해 GR 부호화방법을적응적으로적용하는데, 이로인해영상의각블록은다른 k값을가지게된다. 이때최적 k 파라미터는모든 AC 계수에대해 GR 부호화된비트의길이를더하여구할수있는데, 주어진 p에대한 GR 부호의길이는식 (2) 에의해계산한다. (2) 이후, GR 부호길이의합을최소로하는 k를최적값으로결정한다. 식 (2) 에서작은 p에대해서는 k가작을수록 GR 부호길이가짧아지고, 상대적으로큰 p에대해서는 k가커질수록 GR 부호길이가짧아짐을알수있다. 이로부터 k는입력되는 p의크기에따라결정되는적응적특성을지님을알수있다. 2.4 비트스트림포맷팅 (formatting) 최종적으로각블록에대한부호화결과성분들을일정한규칙에의해배치하여 Fig. 4와같은비트스트림세그먼트를구성하는포맷팅 (formatting) 과정이수행된다. 먼저입력영상의각블록에대한최적 k는 3비트의 FLC로부호화되어저장된다. 그다음, MHT 과정에의한 DC와 AC 성분들이각각 8비트의 FLC와 AGR 부호로저장된다. 이과정은나머지블록에대해반복적으로적용된다. 제안하는알고리즘의성능을평가하기위하여기존의저복잡도무손실압축방법과비교결과를제시하였는데, DAP를 Huffman 부호화한 Song et al. 의방법 [9] 과 MHT 계수를 GR 부호화한 Lee의방법 [14] 과비교하였다. 다만, Lee의방법은손실부호화방식이기때문에본논문에서는양자화과정을생략하여무손실방식으로동작하도록수정하여비교실험을진행하였다. 성능평가는압축성능에대한비교뿐만아니라계산복잡도및메모리요구량분석결과에대한비교를수행하였다. Table 1은제안한방법을포함한각알고리즘의압축성능비교결과를나타낸것이다. Table 1. Comparison of compression ratio Images Song Lee Proposed Lena 30.3 31.1 37.7 Baboon 17.7 17.2 23.1 Barbara 26.8 28.9 29.2 Airplane 35.9 33.3 40.8 Peppers 32.6 27.2 36.4 Man 26.4 25.3 30.2 Elaine 28.8 29.1 36.1 Zelda 39.0 40.3 42.4 Average 29.7 29.1 34.5 제안하는저복잡도무손실영상압축알고리즘의충분한실험결과를얻기위하여 Table 1의첫번째열 (column) 에나열된바와같은 8개의 512 512 크기의테스트영상을사용하였다. 각알고리즘의압축성능을측정하기위하여평균압축률을계산하였는데, 이는식 (3) 과같이정의한다. (%) (3) 이때, R C 은압축률 (compression ratio) 을의미하고, byte 단위로측정된원영상과압축된영상에대한파일을사용한다. 23
한국산학기술학회논문지제 17 권제 11 호, 2016 Table 1의결과에서보는바와같이, 부호화효율관점에서제안한방법이기존방법에비해우수함을알수있는데, Song et al. 의방법과비교하여평균 4.8%, Lee 의방법에비해서는평균 5.4% 의압축률향상이있는것을확인할수있다. Table 2. Comparison of computational complexity and memory size requirement analysis Method Song Lee Proposed Module Computation Operations per Pixel Memory Requirement DAP 1 8 8 block buffer Huffman Memory Access Operation ROM required MHT 6 1 line buffer GR N/A N/A MHT 6 8 8 block buffer AGR 6 N/A Table 2는기존방법과제안한방법의계산복잡도와메모리요구량분석결과를나타낸것이다. Table 2에서알수있는바와같이, 제안한알고리즘에의한계산량이기존알고리즘과비교할때유사하거나다소증가함을알수있다. 그러나 Song et al. 의방법은제안한방법에비해추가적인메모리를필요로하는데, 이는 Huffman 부호화를위한 ROM이사용되기때문이다. 보통 SoC (System on a Chip) 구현및임베디드 (embedded) 시스템에서는 ROM의사용을가급적피하는것이좋다. 연산을위한계산량을 Table 2와같이분석했지만, 실제각동작을수행하는데필요한정확한시간은하드웨어의구성및성능에따라달라질수있다. 또한 Song et al. 의방법에서엔트로피부호화과정이진행될때필요한메모리접근동작 (memory access operation) 은설계및구현을복잡하게하는요인이된다. 메모리양을많이필요로할수록알고리즘의비용또한증가하기때문에기존및제안한알고리즘의전체적인계산비용은필요로하는메모리양에따라달라진다. 따라서 Song et al. 의방법이제안한알고리즘과비교해서연산량은작지만, 많은메모리를필요로하기때문에전체적인계산비용은더욱많이든다. 제안한알고리즘은단지덧셈 ( 및뺄셈 ) 과시프트연산만을필요로하는데, 이는하드웨어에서간단하게구현될수있다. Lee의방법과비교하면, 제안한알고리즘이픽셀당 6번의추가연산을필요로하지만이는전체적인계산비용에큰영 향을미치지않는다. 또한압축률에있어평균 5.4% 우수한결과를고려할때, 하드웨어로간단하게구현될수있는연산이추가된점은충분히수용가능하다. 4. 결론 본논문에서는고해상도영상의프레임메모리 (frame memory) 압축을위한블록버퍼기반의저복잡도무손실압축방법을제안하였다. 제안하는압축방법은블록단위 MHT (modified Hadamard transform) 와 AGR (adaptive Golomb-Rice) 부호화를이용하여저복잡도및효과적인하드웨어구현이달성될수있도록하였다. 기존의저복잡도무손실압축방법과비교하여제안한방법은압축률측면에서우수한성능을보였고, 기존코덱의구조를크게수정하지않고도화질의열화없이하드웨어장치에적용될수있음을다양한실험과복잡도분석을통해보였다. 더욱이제안한알고리즘은데이터저장을위하여어떠한메모리접근동작도필요로하지않아하드웨어구현을위한비용을최소화할수있다. 이러한결과로부터 Full HD급 (1920 1080) 이상의고해상도영상을처리하는다양한분야에제안한알고리즘이효과적으로적용될수있을것으로기대된다. 또한, 향후컬러프레임메모리압축방법및다른저복잡도알고리즘을이용하여압축성능을더욱향상시킬수있는방법에대한연구를진행할예정이다. References [1] H.-C. Kuo and Y.-L. Lin, "A hybrid algorithm for effective lossless compression of video display frames," IEEE Trans. Multimedia, vol. 14, no. 3, pp. 500-509, Jun. 2002. [2] J. Kim, "Orientation-based adaptive prediction for effective lossless image compression," J. Korea Inst. Inf. Commun. Eng., vol. 19, no. 10, pp. 2409-2416, Oct. 2015. DOI: https://doi.org/10.6109/jkiice.2015.19.10.2409 [3] H. Schwarz, D. Marpe, and T. Wiegand, "Overview of the scalable video coding extension of the H.264/AVC standard," IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 9, pp. 1103-1120, Sep. 2007. DOI: https://doi.org/10.1109/tcsvt.2007.905532 [4] M. Tikekar, C.-T. Huang, C. Juvekar, V. Sze, and A. P. Chandrakasan, "A 249-Mpixel/s HEVC video-decoder chip for 4K ultra-hd applications," IEEE J. Solid-State 24
고해상도영상의효과적인처리를위한블록버퍼기반의저복잡도무손실프레임메모리압축방법 Circuits, vol. 49, no. 1, pp. 61-72, Jan. 2014. DOI: https://doi.org/10.1109/jssc.2013.2284362 [5] G. J. Sullivan, J. Ohm, W.-J. Han, and T. Wiegand, "Overview of the High Efficiency Video Coding (HEVC) standard," IEEE Trans. Circuits Syst. Video Technol., vol. 22, no. 12, pp. 1649-1668, Dec. 2012. DOI: https://doi.org/10.1109/tcsvt.2012.2221191 [6] J. Lei, X. Zou, Z. Wu, and W. Fan, "Research of an image map encoding algorithm on frame buffer," in Proc. Int. Conf. ASIC, Guilin, China, pp. 894-897, 2007. [7] T. L. B. Yng, B.-G. Lee, and H. Yoo, "A low complexity and lossless frame memory compression for display devices," IEEE Trans. Consum. Electron., vol. 54, no. 3, pp. 1453-1458, Aug. 2008. DOI: https://doi.org/10.1109/tce.2008.4637640 [8] S. Dikbas and F. Zhai, "Lossless image compression using adjustable fractional line-buffer," Signal Processing: Image Commun., vol. 25, no. 5, pp. 345-351, Jun. 2010. DOI: https://doi.org/10.1016/j.image.2010.02.004 [9] T. Song and T. Shimamoto, "Reference frame data compression method for H.264/AVC," IEICE Electron. Exp., vol. 4, no. 3, pp. 121-126, Feb. 2007. DOI: https://doi.org/10.1587/elex.4.121 [10] S. H. Lee, M. K. Chung, S. M. Park, and C. M. Kyung, "Lossless frame memory recompression for video codec preserving random accessibility of coding unit," IEEE Trans. Consum. Electron., vol. 55, no. 4, pp. 2105-2113, Nov. 2009. DOI: https://doi.org/10.1109/tce.2009.5373775 [11] J. Kim and C. M. Kyung, "A lossless embedded compression using significant bit truncation for HD video coding," IEEE Trans. Circuits Syst. Video Technol., vol. 20, no. 7, pp. 848-860, Jun. 2010. [12] Y. Lee, C.-E. Rhee, and H.-J. Lee, "A new frame recompression algorithm integrated with H.264 video compression," in Proc. IEEE Int. Symposium on Circuits and Systems, pp. 1621-1624, May 2007. DOI: https://doi.org/10.1109/iscas.2007.378829 [13] M. J. Weinberger, G. Seroussi, and G. Sapiro, "The LOCO-I lossless image compression algorithm: Principles and standardization into JPEG-LS," IEEE Trans. Image Processing, vol. 9, no. 8, pp. 1309-1324, Aug. 2000. DOI: https://doi.org/10.1109/83.855427 [14] T. Y. Lee, "A new frame-recompression algorithm and its hardware design for MPEG-2 video decoders," IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 6, pp. 529-534, Jun. 2003. DOI: https://doi.org/10.1109/tcsvt.2003.813425 [15] H. Yoo, J. M. Jo, and J. C. Jeong, "A hierarchical lossless image compression based on modified Hadamard transform," in Proc. 10th Workshop on Image Processing and Understanding, pp. 516-520, 1998. [16] N. Merhav, G. Seroussi, and M. J. Weinberger, "Optimal prefix codes for source with two-sided geometric distribution," IEEE Trans. Information Theory, vol. 46, no. 1, pp. 121-135, Jan. 2000. DOI: https://doi.org/10.1109/18.817520 [17] X. Lian, Z. Liu, W. Zhou, and Z. Duan, "Lossless frame memory compression using pixel-grain prediction and dynamic order entropy coding," IEEE Trans. Circuits Syst. Video Technol., vol. 26, no. 1, pp. 223-235, Jan. 2016. DOI: https://doi.org/10.1109/tcsvt.2015.2469572 김종호 (Jongho Kim) [ 종신회원 ] 2000 년 2 월 : 한양대학교대학원전자통신공학과 ( 공학석사 ) 2008 년 8 월 : 한양대학교대학원전자통신공학과 ( 공학박사 ) 2008 년 9 월 ~ 2009 년 2 월 : 삼성전자책임연구원 2009 년 3 월 ~ 현재 : 순천대학교멀티미디어공학과교수 < 관심분야 > 영상압축및통신, 컴퓨터비전, 영상처리, 디지털신호처리 25