| GISdevelopment.net ---> AARS ---> ACRS 2000 ---> Image Processing |
Subband SAR Image Coding by
using Quadtree Decomposition on Variable Block Truncation Code
Amnach KHAWNE, Somchai OMSIN, Suthichai NOPPANAKEEPONG and Krit WONGRUJIRA
Student, Student, Doctor and Lecturer, Telecommunication Engineering
King Mongkut Institute of Technology Ladkrabang 3 Moo 2 chalongkrung rd. Ladkrabang Bongkok Thailand 10520
Tel. (662) - 737-2500 Ext. 3354
E-mail :s2061037@kmitl.ac.th
Amnach KHAWNE, Somchai OMSIN, Suthichai NOPPANAKEEPONG and Krit WONGRUJIRA
Student, Student, Doctor and Lecturer, Telecommunication Engineering
King Mongkut Institute of Technology Ladkrabang 3 Moo 2 chalongkrung rd. Ladkrabang Bongkok Thailand 10520
Tel. (662) - 737-2500 Ext. 3354
E-mail :s2061037@kmitl.ac.th
Keywords: Synthetic aperture radar, Subband
coding, Block Truncation code, Quadtree decomposition
Abstract
This paper proposes a subband synthetic aperture radar (SAR) image coding by using variable block truncation code, which is assisted by quadtree decomposition (QT) technique to divide image data. Quadtree decomposition is a simple technique for ordering an image data to hierarchical levels. This technique is partitioning an image into variable-sized blocks based on a quadtee structure, that the data in each subblock-size will be homogeneous. Quadtree decomposition will optimize a block for coding by setting up variable block sizes. Therefore, memory and process times are reduced when compared with fixed-block truncation code and absolute moment block truncation coding. The subband image coding is based on the decomposition of a signal into narrow band by a set of parallel filters. This paper uses the 16-band separable subband filter based on the quadrature mirror filter (QMF) by using the separable 2-D QMF, which allows the aliasing to be removed in the reconstruction signal. The coefficients are obtained from each subband and encoded by a classified priority, that is the lower subband having more information than the higher subband. It should be coded with a small block size. In this case, we choose the minimum block equal to 1x1 and the maximum block size is 16x16. For the higher subband, we choose 4x4 minimum block and 16x16 maximum block. The lower subband, especially a part of approximation can be coded with the small block size, but a part of details can be coded large block than the approximation. A combination of both techniques improves the minimum mean square error and image quality.
I.Introduction
Block truncation code (BTC) is the simple technique that is firstly introduced by Delp and Mitchell [1,2]. It is an efficient image coding method that has been adapted to obtain the statistical properties of the block in image compression. This algorithm, the image is firstly divided into non-overlap blocks. The BTC output data set is including of the binary bit plane, which defines the quantization level of each pixel, and two-reconstruction level values, determined by the mean and standard deviation of the block Xi . Where i=1 to II , q is the number of pixels with values greater thean or equal to the transmitted mean u , the two output levels a and b from the quantizer for each block are given by
is the sample mean and 
is the standard deviation that is
In addition, the BTC method is a fixed-based method, that inefficiency for coding. We have the method for dividing an image into varieties of the small block. The pixel in the block is homogeneous called quadtree decomposition (QT) [3,4]. This QT is efficiency than fixed block, especially used for coding SAR image. This paper proposes the combination of subband coding and variable block truncation code.
Section II introduces the subband coding of images. Section III describes the quadtree decomposition method. Section IV describes the combination between the quadtree decomposition method and block truncation code. Simulation result and conclusion are given in section V and VI
II. Subband Image Coding
Subband coding [5] is the most important to obtain high bit-rate compression as illustrate in Fig 1. This figure shows the transform using the two-channel filter bank. The part of the system on the left of the dotted line is the analysis part, and the part of the right is the synthesis part. In the analysis stage, the input data signal is processed by the analysis filter bank consisting of the time-invariant linear with transfer function , , such that is lowpass and is highpass filter respectively.
Figure 1. General two-channel subband coding system
The basic two-channel system in Figure 1 should be designed so that if no compression takes places, the system output will be equal to the translation of the system input. This is called the perfect reconstruction condition or PR-QMF [6,7]. We identify of the two conditions for perfect reconstruction. One condition is removed distortion and the other is removed alising. The signal can be perfectly reconstructed if the analysis and systhesis filters satisfy the conditions (5), (6), (7), (8).
G0(z)=-H1(-z) (5)
G1(z)=-H0(-z) (6)
H1(z)=z-(n-1)H0(-z-1) (7)
H0(z)H0(-z-1)+H0(-z) H0(-z-1)=1 (8)
III. Quadtree Decomposition
Quadtree Decompostion (QT) [3,4] is the analysis technique that involves subdividing the image into blocks that are more homogeneous than the image itself. This technique works by dividing the square image into four equal-sized squared blocks by determining the criterion and then testing each block to meet same criterion of homogeneity. If block meets the criterion, it is not divided any further. If it does not meet the criterion, it is subdivided again into four blocks, and the test criterion is applied to those blocks. This process is repeated iteratively until each block meets the criterion. The result may have blocks of several different sizes. In the Figure 2 illustrates the result of QT
Figure 2. quadtree decomposition. (a) quadtree decompostion an image. (b) Tree structure of quadtree
The quadtree is the tree structure in which each internal node has four branches emanating form it. In the other words, each node in the quadtree has either four children as illustrated in Figure 3. The four children of a particular parent node represent the four subblocks obtained by splitting the parent block into four equal-sized square blocks. In this case, all of leave nodes are compressed by BTC method, described in the next section.
IV. Subband And Variable Block Truncation Code (VBTC)
Image was reduced noise and pre-processed method will be divided into subband. In this case, we used the subband to 16 subbands as shown in Figure 3. for coding. Each subband is filtered and downsampled from filter bank stage and then is divided into small block by quadtree decomposition. The leave node of quadtree can be coded by setting the priority and coded by using VBTC [3,4] method. Subbands are defined as inter-subband and intra-subband [5] for arrangement the subband to coding. The Classification as inter-subband or intra-subband depends on whether they have the same parent source signal. In this case, subband HHLL and HHHH are the intra-subband because both of there are generated from the same parent source signal subband HH. Subband HHLL and LLLL are inter-subbands because their parent source signals are subband HH and LL, respectively
(a)
(b)
Figure 3. (a) 16 subbands structure, (b) Tree structure 16 subbands
V. Simulations and Results
In the experiment the original SAR images, with size 512 x 512 show in Fig. 4. (a),(c). It is divided by the QT method and differently encoded by VBTC for every leave node of the QT. The results are shown in Fig. 4. (b),(d). In Fig. 4 (b), SAR image are reconstructed and measured then evaluate mean square error and peak signal to noise ratio. This technique gives higher of peak signal to noise ratio than the BTC technique and can be reduced the processing time. Compression ratio depends on as a defined of the threshold in a quad tree technique. Table 1. illustrate a process time, mean square error (MSE) and peak signal to noise ratio (PSNR)of each image. The MSE and PSNR in the compression are expressed as
Table 1. Simulations and results
Figure 4. (a),(e) Original SAR images , (d),(g) Reconstruction by subband BTC and (f),(b) Reconstruction by subband VBTC
Figure
4. (con't.) (h) Original sar3, (i) Reconstruction by subband VBTC
VI. Conclusions
Subband SAR image coding by using the variable block truncation coding (VBTC) is more efficient than using Fixed Block Truncation code that is reduced the processing time for compression a SAR image. VBTC technique can be classified data in an image into group that is homogeneous in a group of data. Data in each group is divided by QT decomposition, which is optimal for encoding by using VBTC encoder. Disadvantage of VBTC technique is the threshold selection in the quadtree stage. These thresholds are the criterion for dividing the image into block. If we select the maximum threshold which is obtained most large of blocks and a few blocks for coding. We will get the high compression rate, but the low quality of reconstruction image. In other word, reconstruction image is high quality, but low compression rate. Good pre-filter are required to reduce noise before compressive procedure that are obtained high quality of the reconstruction image.
VII. References
Abstract
This paper proposes a subband synthetic aperture radar (SAR) image coding by using variable block truncation code, which is assisted by quadtree decomposition (QT) technique to divide image data. Quadtree decomposition is a simple technique for ordering an image data to hierarchical levels. This technique is partitioning an image into variable-sized blocks based on a quadtee structure, that the data in each subblock-size will be homogeneous. Quadtree decomposition will optimize a block for coding by setting up variable block sizes. Therefore, memory and process times are reduced when compared with fixed-block truncation code and absolute moment block truncation coding. The subband image coding is based on the decomposition of a signal into narrow band by a set of parallel filters. This paper uses the 16-band separable subband filter based on the quadrature mirror filter (QMF) by using the separable 2-D QMF, which allows the aliasing to be removed in the reconstruction signal. The coefficients are obtained from each subband and encoded by a classified priority, that is the lower subband having more information than the higher subband. It should be coded with a small block size. In this case, we choose the minimum block equal to 1x1 and the maximum block size is 16x16. For the higher subband, we choose 4x4 minimum block and 16x16 maximum block. The lower subband, especially a part of approximation can be coded with the small block size, but a part of details can be coded large block than the approximation. A combination of both techniques improves the minimum mean square error and image quality.
I.Introduction
Block truncation code (BTC) is the simple technique that is firstly introduced by Delp and Mitchell [1,2]. It is an efficient image coding method that has been adapted to obtain the statistical properties of the block in image compression. This algorithm, the image is firstly divided into non-overlap blocks. The BTC output data set is including of the binary bit plane, which defines the quantization level of each pixel, and two-reconstruction level values, determined by the mean and standard deviation of the block Xi . Where i=1 to II , q is the number of pixels with values greater thean or equal to the transmitted mean u , the two output levels a and b from the quantizer for each block are given by
is the sample mean and is the standard deviation that is
In addition, the BTC method is a fixed-based method, that inefficiency for coding. We have the method for dividing an image into varieties of the small block. The pixel in the block is homogeneous called quadtree decomposition (QT) [3,4]. This QT is efficiency than fixed block, especially used for coding SAR image. This paper proposes the combination of subband coding and variable block truncation code.
Section II introduces the subband coding of images. Section III describes the quadtree decomposition method. Section IV describes the combination between the quadtree decomposition method and block truncation code. Simulation result and conclusion are given in section V and VI
II. Subband Image Coding
Subband coding [5] is the most important to obtain high bit-rate compression as illustrate in Fig 1. This figure shows the transform using the two-channel filter bank. The part of the system on the left of the dotted line is the analysis part, and the part of the right is the synthesis part. In the analysis stage, the input data signal is processed by the analysis filter bank consisting of the time-invariant linear with transfer function , , such that is lowpass and is highpass filter respectively.
Figure 1. General two-channel subband coding system
The basic two-channel system in Figure 1 should be designed so that if no compression takes places, the system output will be equal to the translation of the system input. This is called the perfect reconstruction condition or PR-QMF [6,7]. We identify of the two conditions for perfect reconstruction. One condition is removed distortion and the other is removed alising. The signal can be perfectly reconstructed if the analysis and systhesis filters satisfy the conditions (5), (6), (7), (8).
G0(z)=-H1(-z) (5)
G1(z)=-H0(-z) (6)
H1(z)=z-(n-1)H0(-z-1) (7)
H0(z)H0(-z-1)+H0(-z) H0(-z-1)=1 (8)
III. Quadtree Decomposition
Quadtree Decompostion (QT) [3,4] is the analysis technique that involves subdividing the image into blocks that are more homogeneous than the image itself. This technique works by dividing the square image into four equal-sized squared blocks by determining the criterion and then testing each block to meet same criterion of homogeneity. If block meets the criterion, it is not divided any further. If it does not meet the criterion, it is subdivided again into four blocks, and the test criterion is applied to those blocks. This process is repeated iteratively until each block meets the criterion. The result may have blocks of several different sizes. In the Figure 2 illustrates the result of QT
 (a) |
(b) |
Figure 2. quadtree decomposition. (a) quadtree decompostion an image. (b) Tree structure of quadtree
The quadtree is the tree structure in which each internal node has four branches emanating form it. In the other words, each node in the quadtree has either four children as illustrated in Figure 3. The four children of a particular parent node represent the four subblocks obtained by splitting the parent block into four equal-sized square blocks. In this case, all of leave nodes are compressed by BTC method, described in the next section.
IV. Subband And Variable Block Truncation Code (VBTC)
Image was reduced noise and pre-processed method will be divided into subband. In this case, we used the subband to 16 subbands as shown in Figure 3. for coding. Each subband is filtered and downsampled from filter bank stage and then is divided into small block by quadtree decomposition. The leave node of quadtree can be coded by setting the priority and coded by using VBTC [3,4] method. Subbands are defined as inter-subband and intra-subband [5] for arrangement the subband to coding. The Classification as inter-subband or intra-subband depends on whether they have the same parent source signal. In this case, subband HHLL and HHHH are the intra-subband because both of there are generated from the same parent source signal subband HH. Subband HHLL and LLLL are inter-subbands because their parent source signals are subband HH and LL, respectively
(a)
(b)
Figure 3. (a) 16 subbands structure, (b) Tree structure 16 subbands
V. Simulations and Results
In the experiment the original SAR images, with size 512 x 512 show in Fig. 4. (a),(c). It is divided by the QT method and differently encoded by VBTC for every leave node of the QT. The results are shown in Fig. 4. (b),(d). In Fig. 4 (b), SAR image are reconstructed and measured then evaluate mean square error and peak signal to noise ratio. This technique gives higher of peak signal to noise ratio than the BTC technique and can be reduced the processing time. Compression ratio depends on as a defined of the threshold in a quad tree technique. Table 1. illustrate a process time, mean square error (MSE) and peak signal to noise ratio (PSNR)of each image. The MSE and PSNR in the compression are expressed as
| image | Bit Rate | MSE(dB) | PSNR | Subband encoded with [1x1] , {2x2} | Times (Sec.) |
| Tm4 | 1.2813 | 44.2823 | 31.6684 | [ LLLL,LHLL,HLLL] | 353.94 |
| Tm4 | 0.4553 | 43.4394 | 31.6684 | [ LLLL,LHLL,HLLL] | 321.1 |
| Sanfran | 2.875 | 17.7568 | 35.6371 | [LLLL,LLHLLHLL,HLLL] | 1349 |
| Sanfran | 0.8748 | 17.2611 | 35.6855 | [LLLL,LLHLLHLL,HLLL] | 842.44 |
| Sar3 | 3.0625 | 40.0997 | 32.0033 | [LLLL,LLHLLHLL,HLLL],{LLLH,LLHH} | 1430 |
| Sar3 | 0.9788 | 39.3096 | 32.1858 | [LLLL,LLHLLHLL,HLLL],{LLLH,LLHH} | 850.03 |
 (a) Original Tm4. image |
 (b) 0.8748 bpp ; PSNR 35.6855 dB. |
 (d) 1.2813 bpp, PSNR = 31.6684 |
 (e) Original sanfran image |
 (f) 0.9166 bpp, PSNR = 28.2613 |
 (g) 2.8750 bpp, PSNR = 28.1818 |
Figure 4. (a),(e) Original SAR images , (d),(g) Reconstruction by subband BTC and (f),(b) Reconstruction by subband VBTC
 (h) Original sar3 image |
 (i) 0.9788 bpp, PSNR = 32.1858 |
VI. Conclusions
Subband SAR image coding by using the variable block truncation coding (VBTC) is more efficient than using Fixed Block Truncation code that is reduced the processing time for compression a SAR image. VBTC technique can be classified data in an image into group that is homogeneous in a group of data. Data in each group is divided by QT decomposition, which is optimal for encoding by using VBTC encoder. Disadvantage of VBTC technique is the threshold selection in the quadtree stage. These thresholds are the criterion for dividing the image into block. If we select the maximum threshold which is obtained most large of blocks and a few blocks for coding. We will get the high compression rate, but the low quality of reconstruction image. In other word, reconstruction image is high quality, but low compression rate. Good pre-filter are required to reduce noise before compressive procedure that are obtained high quality of the reconstruction image.
VII. References
- Delp, E. J., and Mitchell, O. R., 1991, Moment Preserving Quantization, IEEE Transactions on Communications, Vol. 39, pp. 1549-1558.
- Delp, E. J., Saenz, M., and Salama, P., 2000, Block Truncation Coding (BTC), Handbook of Image and Video Processing, edited by Bovik A. C., Academic Press, pp. 176-181.
- Long Wen Chang, and Ching Yang Wang, 1999, Image Compression Using Optimal Variable Block Truncation Coding, Multimedia Signal Processing, 1999, IEEE 3rd Workshop on, 1999, pp. 413-418.
- Mohamed Kamel, Sun C. T., and Lian Guan, 1991, Image Compression by Variable Block Truancation Coding with Optimal Threshold, IEEE Transactions on Signal Processing. Vol. 39, No. 1, pp. 208-212.
- Kai-Krung Ma, and Sarah A. Rajala, 1991, Subband Coding of Digital Images Using Absolute Moment Block Truncation, IEEE Transactions on Acoustics, Speech, and Signal Processing, 1991. ICASSP-91., International Conference on, 1991 Vol. 4, pp. 2645-2648.
- Martin Vetterli, and Cormac Harley, 1992, Wavelets and Filter Banks: Theory and Dsign, IEEE Transactions on Signal Processing, Vol. 40, No. 9, pp. 2207-2232.
- Strang G., and Ngnyen T., 1996, Wavelet and Filter Banks, M.A., edited by Wellesley-Cambridge Press, pp. 103-113.