Hardware Implementation of Tag Tree in JPEG2000 Encoder

Hardware Implementation of Tag Tree in JPEG2000 Encoder

Bach Tuan Dong

Department of Electrical and Electronic Engineering Ho Chi Minh City University of Technology and Education

Ho Chi Minh City, Vietnam

Huynh Hong Tram

Department of Computational Engineering Vietnamese German University Binh Duong Province, Vietnam

Trinh Hoai An

Department of Electrical and Electronic Engineering Ho Chi Minh City University of Technology and Education

Ho Chi Minh City, Vietnam

Le My Ha

Department of Electrical and Electronic Engineering Ho Chi Minh City University of Technology and Education

Ho Chi Minh City, Vietnam

AbstractHierarchical data structure takes an importance rule in many files such as computer graphic, information storage and retrieval, image processing etc. Quad-tree is a kind of hierarchical data structure which is applied widely in image coding. Tag tree, a particular type of quad-tree, is a coding mechanism used in tier-2 coding engine in JPEG2000 encode. In this paper, we propose a hardware implementation of tag tree in JPEG2000 encode system. Tag tree is successful implemented on hardware system, tested by using OpenJPEG and simulated on Modelsim and VCS tools.

KeywordsQuad-tree; tag tree; JPEG2000; OpenJPEG; packet; packet header; node; parent node

1. INTRODUCTION

   JPEG2000 is a new image compression standard, which was created by Joint Photographic Expert Group committed in 2000. It shows many advances such as superior compression performance, multiple resolution representation, progressive transition support, lossless and lossy compression etc. Based on the independent coding mechanism, with JPEG2000, the relevant byte in a compressed codestream can be extracted and reassembled into a different codestream without decompress the codestream [2]. The only thing we have to do is changing the packing way of the codestream, which is processed in Tier

   1. Tier-2 reorders and packs the codeblock bit-stream into the full-feature bit-stream.

      	Full-featured bit-stream
      T2 Layer formation and block summary information Coding engine
      	Embedded block bit-streams and summary information
      T1 Low-level embedded block coding engine
      	Blocks of sub-band sample

      Fig. 1. Tier-1 coding and Tier-2 coding in JPEG2000

      All compressed image data representing a specific tile, layer, component, resolution level and precinct appears in the code stream in a contiguous segment called a packet. Packet data is aligned at 8-bit (one byte) boundaries [1].

      packet

      k0,1

      packet

      k1,1

      head

      Head

      body

      Head

      body

      1

      1

      1

      body

      k1,1

      packet

      Fig. 2. Bit-stream organization

      A packet includes packet header and packet data, which is described as follows.

      A packet header describes:

      • Zero length packet;

      • Code-block inclusion;

      • Zero bit-plane information;

      • Number of coding passes;

      • Length of the code-block compressed image data from a given code-block.

   The code-block inclusion and zero bit-plane information are coded with the tag tree coding algorithm.

   This paper is organized as follows. The section 2 deals with the introduction of tag tree coding scheme. Hardware implementation of tag tree is discussed in section 3. Finally, the result and conclusion are presented in section 4 and section 5.

2. TAG TREE ENCODING PROCEDURE

   1. Tag tree encode algorithm

      Tag tree is a way of representing a two-dimensional array of non-negative integer in hierarchical way. It successive creates reduced resolution levels of this two dimension array, forming a tree. At every node of this tree the minimum integer of the (up to four) nodes below it is recorded [1].

      The following is an example of a tag tree. Assuming that qi(m,n) is the value of an array at row m, column n and level i.

      1 q3 (0, 0)	3 q3 (0,1)	2 q3 (0, 2)	3 q3 (0, 3)	2 q3 (0, 4)	3 q3 (0, 5)
      2 q3 (1, 0)	2 q3 (1,1)	1 q3 (1, 2)	4 q3 (1, 3)	3 q3 (1, 4)	2 q3 (1, 5)
      2 q3 (2, 0)	2 q3 (2,1)	2 q3 (2, 2)	2 q3 (2, 3)	1 q3 (2, 4)	2 q3 (2, 5)

      Fig. 3. Level 3 of tag tree

      Min(1, 3, 2, 2) 1 q2 (0, 0)	Min(2, 3,1, 4) 1 q2 (0,1)	Min(2, 3, 3, 2) 2 q2 (0, 2)
      Min(2, 2) 2 q2 (1, 0)	Min(2, 2) 2 q2 (1,1)	Min(1, 2) 1 q2 (1, 2)

      1

      q1 (0,1)

      Fig. 4. Level 2 of tag tree

      1

      q1 (0, 0)

      Fig. 5. Level 1 of tag tree

      q0 (0, 0)

      Fig. 6. Level 0 of tag tree

   2. Encoding method:

      Each coded node of a tag tree includes d bit zeros and one bit 1 (d is the difference of the value of the current node and its parent node). Specially, the parent node of a root node is 0.

      1. Example 1:

         Encode q3(0,0) in the previous example. In order to encode the node q3(0,0), we should consider q2(0,0), q1(0,0), q0(0,0)

         The parent node of q0(0,0) is 0; and q0(0,0) = 1 q0(0,0) 0 = 1 the coding value at the node q0(0,0) includes one bit 0 and one bit 1 the coding value of q3(0,0) is 01.

         The parent node of q1(0,0) is q0(0,0); and q1(0,0) = 1, q0(0,0) = 1 q1(0,0) q0(0,0) = 0 the coding value of q1(0,0) includes zero bit 0 and one bit 1. Combining with the coding value of the previous node, the current coding value is 0 1 1.

         Similarly, the parent node of q2(0,0) is q1(0,0); and q2(0,0)

         = 1 and q1(0,0) = 1 q2(0,0) q1(0,0) = 0 the coding value at the node q2(0,0) includes zero bit 0 and one bit 1. Combining with the coding value of the previous nodes, the current coding value is 0 1 1 1.

         Similarly, the coding value at the node q3(0,0) is 0 1 1 1 1

      2. Example 2:

   Coding q3(0,1). The parent node of q3(0,1) is q2(0,0). Because the node q2(0,0) has already coded, we just consider q2(0,0) when coding q3(0,1).

   The parent node of q3(0,1) is q2(0,0), q3(0,1) q2(0,0) = 2

   the coding value of the node q3(0,1) includes two bit 0s and one bit 1 The coding value is 001.

3. IMPLEMENT TAG TREE ON HARDWARE SYSTEM

   1. Some problems had to solve to build a tag tree on hardware system

      • In order to encode data at a specific position, the tree structure has to build first (for example, the coding value of q3(0,0) is obtained by finding the differences of q0(0,0) and 0, q1(0,0) and q0(0,0), q2(0,0) and q1(0,0), q3(0,0) and q2(0,0)

      • To determine whether a node is encoded, a flag is used to mark an encoded node. If that node is not encoded, encode that node and jump to its parent node. If that node is encoded, encode that not and stop the coding process for that node.

      • Beginning from the inut array of the maximum level, we can find the minimum values of groups of four elements to determine array data values of the next levels.

      • The number of coding bit of a tag tree cannot be predetermined; it depends on the input values. Therefore, we need two kinds of signals to express the output. The first one is the coding, which shows the coded values. The second one is mask, which shows the number of valid bits in the coding signal.

        The tag tree on hardware system is divided into 3 parts:

      • Part 1: Save data into RAM and build the tree.

      • Part 2: Read data from RAM and encode.

      • Part 3: Pack encoded data into packets and send packet out.

   2. Tag tree hardware architecture overview

      1. Part 1:

         The input data is sent to the tag tree module in raster order. Line buffer module captures data and groups them into groups of four elements. Each group is sent to min module, which finds the minimum value of groups of four elements. These minimum values are saved in RAM. Besides, these minimum values also push out to the next level. The similar method is applied for all levels.

         The tree structure is generated and saved in RAM.

         Fig. 7. Tag tree structure – Part 1

      2. Part 2:

         Part 2 is the reading (from RAM) and encoding process. The main purpose of this part is sending out the coding values which are suitable with the input positions.

      3. Part 3:

      Part 3 is the parking process. It sends out packets and mask packets.

      RAM

      (level 3)

      Transfer addess

      Row column

      Read_level

      0,0

      0,1

      0,2

      0,3

      2,0

      3,1

      2,2

      2,3

      RAM

      (level 2)

      Read-level_i

      RAM

      (level 1)

      Read-level_i

      packing

      RAM

      (level 0)

      Read-level_0

      Choose data

      Fig. 8. Tag tree structure – Part 2 and 3

   3. Tag tree architecture in details

   1. Module combine address and data

      Combine data_in , row_in and column _in into a data line.

   2. Module line buffer

      1. Function:

         Create two consecutive rows.

      2. Example:

   Assume that we have a 4×4-input array. The output data from the line buffer module is described as following:

   Fig. 11. Array Module

   3,3

   3,2

   3,1

   3,0

   1,3

   1,2

   1,1

   1,0

   Read-level_Max

   Each group includes 4 data lines sent to the min module in parallel.

   The main purpose of combine_address_data, line buffer and array is grouping data into arrays of 2×2 elements and inserting the maximum possible values into every missing element. Therefore, there are always 4 data lines sent to the min module.

   1. Module min:

      Find the minimum value of 4 elements gotten from array module.

      Create the information described for a node. The information includes parent node address, flag (which is used to mark coded nodes) and the differences of each element in a 2×2 array and the minimum value of that 2×2 array. The structure of a tag tree is saved in RAM.

      1 q3 (0, 0)	3 q3 (0,1)	2 q3 (0, 2)	3 q3 (0, 3)	2 q3 (0, 4)	3 q3 (0, 5)
      2 q3 (1, 0)	2 q3 (1,1)	1 q3 (1, 2)	4 q3 (1, 3)	3 q3 (1, 4)	2 q3 (1, 5)
      2 q3 (2, 0)	2 q3 (2,1)	2 q3 (2, 2)	2 q3 (2, 3)	1 q3 (2, 4)	2 q3 (2, 5)

   2. Save tag tree module into RAM Consider the following array as an example: Level = 3, widtp = 6, height3 = 2;

   0,0

   1,0

   2,0

   3,0

   0,1

   1,1

   2,1

   3,1

   0,2

   1,2

   2,2

   3,2

   0,3

   1,3

   2,3

   3,3

   Line_buffer 0,0

   1,0

   0,1

   1,1

   0,2

   1,2

   0,3

   3,3

   3,2

   3,1

   3,0

   2,3

   2,2

   3,1

   2,0

   1,3

   Fig. 12. Group data in level 3

   Fig. 9. Line buffer even height

   0,0	0,1	0,2	0,3		2,0	3,1	2,2	2,3
   1,0	1,1	1,2	1,3

   In case of the height is odd, the values at A, B, C, D is the maximum performed value. For example, we need 4 bits to perform the input values of line buffer; it means that the values at cells A, B, C, D are 1111b.

   Consider the 2×2 green array; min (q3(0,0), q3(0,1), q3(1,0), q3(1,1)) = q2(0,0), q2(0,0) (the 1×1 yellow array) is the parent node of the green array.

   Min(1, 3, 2, 2) 1 q2 (0, 0)	Min(2, 3,1, 4) 1 q2 (0,1)	Min(2, 3, 3, 2) 2 q2 (0, 2)
   Min(2, 2) 2 q2 (1, 0)	Min(2, 2) 2 q2 (1,1)	Min(1, 2) 1 q2 (1, 2)

   Level = 2; widtp = 3; height2 = 2

   `

   A B C D

   Fig. 13. Group data in level 2

   1

   q1 (0,1)

   Level = 1; widtp = 2; height1 = 1

   Fig. 10. Line Buffer odd height

   The output values of the line buffer module are the input values of the array module.

   3) Module Array

   Group the data out from the line buffer module into groups of four elements. The input value gotten from the line buffer module is processed by the array module and creates the following output order:

   1

   q1 (0, 0)

   Fig. 84. Group data in level 2

   Each cell in RAM describes the information of a 2×2 array block. It means that an address in RAM permits to access to a 2×2-block. Following with an address line is a position line, which permits to access a specific value in that 2×2-block.

   1. Module Transfer address

      The input node address is described in term of row and column, the transfer address module gets that row and column and changes them into respective address to access

      RAM level max (address and position)

4. RESULT

   1. Parameter

      • Level max =

        max([log2(WITH_TAG_TREE)],[log2(HEIGHT_TAG_TREE)])

        This module is used once in case of level max, the remaining levels of RAM base on the parent node saved in

        • Memlength(i)=

          Levelmax

          WIDTHi HEIGHTi

          {[ ]*[ ]}

          RAM at that level to access the upper level.

          1. Module Read_level:

          0 2 2

          Levelmax WIDTHlevel

          The encoding is proceeded here. It is connected to RAM in encode period to control reading data out from RAM and writing the flag when finishing coding a node.

          The output data of this module is coding and mask. Coding is the encoded value, and mask is the number of valid bit in coding.

          • WIDTH_LEVEL=

          • HEIGHT_LEVEL=

   2. Compile result

   [ ]

   level 2

   ]

   Levelmax HEIGHTlevel

   [

   level 2

   0

   Altera Device	Area	Fmax (MHz)	Mem	DSP
   Cyclone II EP2C35F672C6	14,867 LEs	92.89	0	0
   Stratix II EP2S30F672C3	4,891 ALUTs	151.38	0

   The read_level module includes 2 parts: coding and choose. Coding encodes for a node, choose selects one data line of levels to send out.

   The following is the data flow of the read_level module.

   Current Address, current

   position LEVELMAX

   Start

   Assume that WIDTH = 32, HEIGHT = 32, PACKET_LEN =

   8, we have the compile result on Quartus II version 11.0:

   Level = 0

   No

   Coding

   Yes

   Stop

5. CONCLUSION

Based on the tag tree encoding algorithm, this paper presents the implementation of a tag tree on hardware system. This core is processed through three parts. Part 1 is saving data and building the tree structure. Part 2 is encoding; and part 3 is packing. Although the input array values of a tag tree require the raster-scan order, the information in the tree may be coded in any order. The input array dimension, data input bit-width and the maximum length of a packet are defined in an inclusion file by users. The architecture is successfully applied on theJPEG2000 Encoder IP of ICDREC. The tag tree operates at more than 150 MHz on Stratix II Family of Altera FPGA

Current Address = Parent Address Current Position = Parent Position Level = Level – 1

REFERENCES

Flag current = 1

Yes

1. JPEG2000 Part 1 Final Committee Draft Version 1.0, ISO/IEC JTC1/SC 29/WG N1646R, 2000.

2. David S. Taubman, JPEG2000 Image Compression Fundamentals,

   Standards and Practice, 2002

3. Coding of Still Pictures, ISO/IEC JTC 1/SC 29/WG 1 WG1N1684,

   April 25, 2000

4. Schelkens, Skodras, Ebrahimi The JPEG 2000 Suite, 2009

5. Chung-JrLian, Lifting Based Discrete Wavelet Transform Architecture for JPEG2000, 2009

Coding

Flag current = 1

Fig. 95. Encoding flow of the read_level module.