Adaptive uniform polar quantization

A simple and complete analysis for an optimal uniform polar quantizer with respect to mean-square error (MSE) as efficient quantization technique for any number of points N (Fixed-Rate) is given. Conditions for the optimality of the polar quantizer and all main equations for phase partitions and opt...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2005
Автори:	Perić, Z.H., Milojković, M., Antić, D., Jovanović, A.Z.
Формат:	Стаття
Мова:	English
Опубліковано:	Інститут проблем реєстрації інформації НАН України 2005
Назва видання:	Реєстрація, зберігання і обробка даних
Теми:	Математичні методи обробки даних
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/50718
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Adaptive uniform polar quantization / Z.H. Perić, M. Milojković, D. Antić, A.Z. Jovanović // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 1. — С. 24-31. — Бібліогр.: 9 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50718
record_format	dspace
spelling	irk-123456789-507182013-10-30T03:06:06Z Adaptive uniform polar quantization Perić, Z.H. Milojković, M. Antić, D. Jovanović, A.Z. Математичні методи обробки даних A simple and complete analysis for an optimal uniform polar quantizer with respect to mean-square error (MSE) as efficient quantization technique for any number of points N (Fixed-Rate) is given. Conditions for the optimality of the polar quantizer and all main equations for phase partitions and optimal number of levels are presented. Improved performance over product polar quantization and scalar uniform quantization proposed in the literature is afforded by allowing a variable number of phases at each magnitude level. Представлено простий і повний аналіз оптимального рівномірного полярного квантування відносно середньоквадратичної помилки як ефективний метод квантування для будь-якого числа точок N (з фіксованою частотою). Також представлені умови оптимальності полярного квантувателя та всі основні рівняння для розділення фаз й оптимальної кількості рівнів. Поліпшена характеристика добутку полярного квантування й скалярного рівномірного квантування, що наведена в літературі, припускається за умови наявності змінного числа фаз при кожному рівні величини. Представлен простой и полный анализ оптимального равномерного полярного квантования относительно среднеквадратической ошибки как эффективный метод квантования для любого числа точек N (с фиксированной частотой). Также представлены условия оптимальности полярного квантователя и все основные уравнения для разделения фаз и оптимальное количество уровней. Улучшенная характеристика произведения полярного квантования и скалярного равномерного квантования, приводимая в литературе, допускается при условии наличия переменного числа фаз при каждом уровне величины. 2005 Article Adaptive uniform polar quantization / Z.H. Perić, M. Milojković, D. Antić, A.Z. Jovanović // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 1. — С. 24-31. — Бібліогр.: 9 назв. — англ. 1560-9189 http://dspace.nbuv.gov.ua/handle/123456789/50718 004.93 en Реєстрація, зберігання і обробка даних Інститут проблем реєстрації інформації НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
topic	Математичні методи обробки даних Математичні методи обробки даних
spellingShingle	Математичні методи обробки даних Математичні методи обробки даних Perić, Z.H. Milojković, M. Antić, D. Jovanović, A.Z. Adaptive uniform polar quantization Реєстрація, зберігання і обробка даних
description	A simple and complete analysis for an optimal uniform polar quantizer with respect to mean-square error (MSE) as efficient quantization technique for any number of points N (Fixed-Rate) is given. Conditions for the optimality of the polar quantizer and all main equations for phase partitions and optimal number of levels are presented. Improved performance over product polar quantization and scalar uniform quantization proposed in the literature is afforded by allowing a variable number of phases at each magnitude level.
format	Article
author	Perić, Z.H. Milojković, M. Antić, D. Jovanović, A.Z.
author_facet	Perić, Z.H. Milojković, M. Antić, D. Jovanović, A.Z.
author_sort	Perić, Z.H.
title	Adaptive uniform polar quantization
title_short	Adaptive uniform polar quantization
title_full	Adaptive uniform polar quantization
title_fullStr	Adaptive uniform polar quantization
title_full_unstemmed	Adaptive uniform polar quantization
title_sort	adaptive uniform polar quantization
publisher	Інститут проблем реєстрації інформації НАН України
publishDate	2005
topic_facet	Математичні методи обробки даних
url	http://dspace.nbuv.gov.ua/handle/123456789/50718
citation_txt	Adaptive uniform polar quantization / Z.H. Perić, M. Milojković, D. Antić, A.Z. Jovanović // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 1. — С. 24-31. — Бібліогр.: 9 назв. — англ.
series	Реєстрація, зберігання і обробка даних
work_keys_str_mv	AT periczh adaptiveuniformpolarquantization AT milojkovicm adaptiveuniformpolarquantization AT anticd adaptiveuniformpolarquantization AT jovanovicaz adaptiveuniformpolarquantization
first_indexed	2025-07-04T12:30:32Z
last_indexed	2025-07-04T12:30:32Z
_version_	1836719520349159424
fulltext	24 UDC 004.93 Zoran H. Perić, Marko Milojković, Dragan Antić, Aleksandra Z. Jovanović Faculty of Electronic Engineering, University of Nis, Serbia e-mail: peric@elfak.ni.ac.yu Adaptive uniform polar quantization A simple and complete analysis for an optimal uniform polar quantizer with respect to mean-square error (MSE) as efficient quantization technique for any number of points N (Fixed-Rate) is given. Conditions for the optimality of the polar quantizer and all main equations for phase partitions and op- timal number of levels are presented. Improved performance over product polar quantization and scalar uniform quantization proposed in the litera- ture is afforded by allowing a variable number of phases at each magnitude level. Key words: uniform polar quantization, method of Lagrange multipliers, op- timization. Introduction Polar quantization techniques as well as their applications in areas such as comput- er holography, discrete Fourier transform encoding, image processing and communica- tions have been studied extensively in the literature. Synthetic Aperture Radars (SARs) images can be represented in polar format (i.e., magnitude and phase components). In the case of MSE quantization of a symmetric two-dimensional source, polar quantiza- tion gives the best result in the field of the implementation [1]. The motivation behind this work is to maintain high accuracy of phase information that is required for some applications such as interferometry and polarimetry, without loosing massive amounts of magnitude information [1, 2]. Problem of the optimal uniform quantization, even for the simplest case, which is uniform scalar quantization, is rather actual nowadays [4]. If we apply the Gaussian quantizer on an arbitrary source we can take advantage of the central limit theorem and the known structure of an optimal scalar quantizer for a Gaussian random variable to code a general process by first filtering it in order to produce an approximately Gaussian density, then scalar-quantizing the result, and finally, inverse-filtering it to recover the original. Various processing techniques, when applied to non-Gaussian sources with memory, produce sequences that are «approximately» independent and Gaussian [7]. In previous works about polar quantization [1, 3] only product uniform quantization was © Zoran H. Perić, Marko Milojković, Dragan Antić, Aleksandra Z. Jovanović Adaptive uniform polar quantization ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 25 always considered (N = P ´ L). That optimization approximated granular distortion as: 2 2 2 2 max 3 2 12 PL rDg p += . SAR images can be represented in polar format (i.e., magnitude and phase compo- nents). In the case of MSE quantization of a symmetric two-dimensional source, polar quantization gives the best result in the field of the implementation. Polar quantization consists of separate but uniform magnitude and phase N level quantization, so that rec- tangular coordinates of the source (x, y) are transformed into the polar coordinates in form: r = (x2 + y2)1/2, f = tan–1(y/x) where r represents magnitude and f is a phase. The optimal uniform polar quantization (OUPQ) is very similar to the original uniform polar quantization (UPQ) except the fact that the number of the regions for the phase angle varies depending on the result of magnitude quantization. In other words each concen- tring ring in quantization pattern allows to have a different number of partitions in the phase quantizer (Pi) when r is in the i-th magnitude ring. Their implementation remains simple requiring only two scalar quantizers and lookup table of the Pi. One UPQ must satisfy the constraint å = = L i i NP 1 in order to use all of N regions for the quantization. In this paper polar quantizers are designed and analysed under additional constraint that each scalar quantizer is a uniform one. This restriction has the following advantages over optimal polar quantization: the implementation is simple, and no compressor- expander pair is needed. Adaptive uniform polar quantization can be used in ADPCM systems. Optimal uniform polar quantization Uniform scalar quantization was considered in previous papers as a uniform quan- tization in magnitude and phase where the number of points was constant. The trans- formed probability density function for the Gaussian source takes the following form: pps f s 2 )( 2 1),( 2 2 2 2 rfrerf r =×= - . (1) We consider uniform polar quantizer of L magnitude levels and Pi phase recon- struction levels on a magnitude reconstruction level mi, 1 £ i £ L. In order to find a truly optimal quantizer we have to minimize the distortion, so we proceed as follows. Magnitude decision levels and reconstruction levels are given as: ,1,)2/1( ,11,)1( Liim Liir i i ££D-= +££D-= where ri is defined in range 1 £ i £ L (0 < r1 < r2 <…< rL < rL+1 = rmax ) and mi in (0 < < m1 < m2 < ... < mL). Next, we make a partition of each magnitude ring into Pi phase Zoran H. Perić, Marko Milojković, Dragan Antić, Aleksandra Z. Jovanović 26 subpartitions. Let fi,j and fi,j+1 be two phase decision levels, and let yi,j be the j-th phase reconstruction level for the i-th magnitude ring, 1 £ j £ Pi. Then: iji Pj /)1(, pf -= , and iji Pj /)12(, py -= . Total distortion D is a combination of granular and overload distortions, D = Dg + + Do. Granular distortion Dg [2] takes the following form: f p yf f f drdrfrmmrD L i P j r r jiiig i ji ji i i 2 )(])cos(2[ 1 1 , 22 1, , 1 åå ò ò = = + + --+= . (2) After the integration over f and the reordering, (2) becomes as follows: drrf P crmmrPPD L i r r i iiLg i i å ò = + -+= 1 22 1 )(])(sin2[),,( 1 p L (where sin c(x) = sin(x)/x) (3) and overload distortion Do is described as: å òò = ¥ --+= +i jL jL P j r jLLLo rmmrD 1 , 22 max 1, , )]cos(2[ yf f f f p drdrf 2 )( × . (4) We use [5]: )( 6 11)(16605,01)sin( 22 xxxx x x ee +-»+-= and after this approxi- mation Dg becomes as follows: .)( 3 1)()(( 1 2 2 2 1 1 drrfrm P drrfmrD L i r r i r r i ig i i i i å ò ò = + + +-= p (5) Thus, we practically define separate amplitude and phase distortions as follows: q g L gg DDD += and for very large N, asymptotically, last equation can be given as: ).( 12 )( 12 2 1 2 2 2 max ii L i i g mfm L r D å = D += q (6) The minimization of the function Dg(P) for fixed number of magnitude levels L constrained by total number of reconstruction points N is formulated in this way: mi- nimize Dg(P) under the constraints: 0),,,( 1 210 ³-= å = L i iL PNPPPg L (7) Adaptive uniform polar quantization ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 27 .1;0)( LiPPg iii ££³= Before describing the minimization procedure, we prove that the problem of mini- mization of the Dg(P) is a convex programming problem. This follows directly from Lemma 1. Lemma 1: Function Dg(P) is convex and constraints g0(P) and gi(Pi) form the con- vex set . Proof of Lemma 1: To prove that the function Dg(P) is convex and constraints g0(P) and gi(Pi) form the convex set it is sufficient to prove that Hessian matrices of the following functions: Dg(P), –g0(P), –gi(Pi), 1 £ i £ L are positive semi-definite [6, p. 27]. Conditions that satisfy the optimal solution for mentioned problem will be seeked using the method of Lagrange multipliers, as: J = Dg + låPi where l represents La- grangian multiplier. From 0= ¶ ¶ iP J we obtain l p ¶ +-= ¶ ò +1 )( )(3 2 3 2 i i r r i ii drrrfm PP J . The optimization problem for polar quantizer can be formulated in this way: it is necessary to find partial derivations of Dg(P). It follows from (10) that ,)( )(3 2 1 3 2 ò + = i i r r i ii g drrrfm PP D p ¶ ¶ while the second partial derivation is ï î ï í ì ¹ = = ò + . ,0 ,,)( )( 2 1 4 2 2 ji jidrrrfm P PP D i i r r i i ji g p ¶¶ ¶ It can be easily concluded that: .0 2 ³ ji g PP D ¶¶ ¶ For Hessian matrix it obviously holds: ,0 2 1 2 1 2 11 2 ³ ú ú ú ú ú ú û ù ê ê ê ê ê ê ë é LL g L g L gg PP D PP D PP D PP D ¶¶ ¶ ¶¶ ¶ ¶¶ ¶ ¶¶ ¶ L LLLLLLLL L while for the constraints we have: Zoran H. Perić, Marko Milojković, Dragan Antić, Aleksandra Z. Jovanović 28 00 2 =- ji PP g ¶¶ ¶ , Li PP g ji i ££=- 1,0 2 ¶¶ ¶ 0 0 2 1 0 2 1 0 2 11 0 2 = ú ú ú ú ú ú û ù ê ê ê ê ê ê ë é LLL L PP g PP g PP g PP g ¶¶ ¶ ¶¶ ¶ ¶¶ ¶ ¶¶ ¶ L LLLLLLLL L , Li ££0 . This completes the proof and it is completely proved that Dg(P) is a convex func- tion of P. After applying method of Lagrange multipliers, we have: åå ò ò == ++-= + + L i i L i r r i r r i i Pdrrfrm P drrfmrJ i i i i 11 2 2 2 ))( 3 1)()(( 1 1 lp . Then: Li drrrfm drrrfm NP L j r r j r r i opti j j i i ££= å ò ò = + + 1; )( )( 1 3 3 1 1 for fixed N. (8) This is the exact result without asymptotical analysis. Our goal is to find rmax, Lopt, and (Piopt)1£i£L for which Dg is minimal. For Gaussian source (after transformed into the polar coordinates) where 2 2 2 2)( s s r errf - = , optimal number of points gets a new form: 2 2 2 2 max 6 6 2 max )1(3 / s s s im r i i e Le rNmP - - - » . (9) These analyses yield to the resulting granular distortion asymptotically Dg = 2 2 max 12L r + 36 2 max 2 422 )1(9 2 2 max ssp r e rN L - - . (10) The optimal number of levels problem can be solved analytically only for the asymptotical analysis as it is suggested: from the condition 0= ¶ ¶ L Dg we come to the optimal solution Lopt Adaptive uniform polar quantization ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 29 p s s N e rL r opt 4 36 max )1( 108 / 2 2 max- - = . (11) Now, we finally have the equation for the optimal distortion of the uniform polar quantizer: 2/36 2 )1(3 2 2 max sps r opt g e N D - -= . (12) Especially interesting is to compare optimal uniform polar quantization with op- timal product polar quantization using proposed method of the optimization. Optimal product granular distortion is then: N rD optprod g 6 2max sp= , (13) ) )1(33 2)( log(10) )( )( log(10)( 2/36 )( max 2 2 max i ir i opt g prod g e ir iD iD iG ss - - == , (14) where Lr ln2max s= [4]. Now we have: p N N NL 4 3 1 )1( 108 ln2 - - = , (15) 12 12 12 2 max 2 ÷÷ ø ö çç è æ = D = N rD skal g . (16) Gains over scalar and optimal product quantization are as follows: ÷ ÷ ÷ ø ö ç ç ç è æ - == - 2 3 3 2 )1(33 ln8log10log10 L N D D G opt g skal g p (17) and Zoran H. Perić, Marko Milojković, Dragan Antić, Aleksandra Z. Jovanović 30 ÷ ÷ ÷ ø ö ç ç ç è æ - == -- 2 3 3 21 )1(33 ln22log10log10 L L D D G opt g prod g . (18) Figure shows the gains for different number of bits per sample. Gain [dB] as a function of number of bits per sample Application of Adaptive Uniform Polar Quantization: Short-time pdf of speech segments are described by Gaussian pdf [8]. This paper addresses potential improvements achievable by means of joint quantization of two con- secutive samples (x, y) referred to as two-dimensional quantization (2-D quantization) over the scalar quantization. Also a transform coding scheme known as spectral phase coding (SPC) is a reliable technique for coding a nonstationary or large dynamic range discrete-time series into a digital form. SPC is essentially a polar format representation of the discrete Fourier Transform (DFT) of a random phase time series. SPC utilises the discrete Fourier Transform and a two-dimensional quantizer to obtain its reliable char- acteristics. Also it may apply optimal uniform polar quantization at Adaptive Differential Pulse Code Modulation (ADPCM). In ADPCM systems it utilises uniform scalar quan- tization [9]. We give a gain which can be achieved if we use optimal uniform polar quantizer in ADPCM systems. Conclusion We introduced optimal uniform polar quantization through simple and complete analysis by constructing an optimal uniform polar MSE quantizer for sources with cir- cularly symmetrical probability density. 4 5 6 7 8 0,5 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5 G (d B) R(bits per sample) G G1 Adaptive uniform polar quantization ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 1 31 We also gave an equation for optimal number of points for different levels and for optimal number of levels. The equations for optimal uniform polar distortion opt gD are provided. Numerical results confirm the potentialities of such an approach. They show that gain based on OUPQ method application is (2,9–4,5) dB over scalar quantization and (0,7–1,9) dB over optimal product quantization. When polar quantization is in use, dis- tortion can be reduced by applying OUPQ method of the optimization. Quantizers de- scribed here are simple for the application and realization. 1. Arslan F.T. Adaptive Bit Rate Allocation in Compression of SAR Images with JPEG2000. — The University of Arizona (USA), 2001. 2. Peric Z.H., Vasic B.V. Optimal Number Phase Divisions in Polar Quantization // Advances in Electrical and Computer Engineering. — 2003. — Vol. 3(10), N 1(19). — P. 5–11. 3. Moo P.W., Neuhoff D.L. Uniform Polar Quantization Revisited // Proc. IEEE Int. Symp. Informa- tion Theory ISIT’98. — Cambridge (USA). —1998, Aug. — P. 100. 4. Hui D., Neuhoff D.L. Asymptotic Analysis of Optimal Fixed-Rate Uniform Scalar Quantization // IEEE Transaction on Information Theory. — 2001, March. — Vol. 47. — P. 957–977. 5. Abramowitz M. and Stegun I. Handbook of Mathematical Functions. — New York: Dover. 6. Himmelblau D.M. Applied Nonlinear Programming. — U.S.A: McGraw-Hill, Inc., 1972. 7. Popat K. and Zeger K. Robust Quantization of Memoryless Sources Using Dispersive FIR Filters // IEEE Trans. Commun. — 1992, Nov. — Vol. 40. — P. 1670–1674. 8. Jayant N.S.and Noll P. DIGITAL CODING OF WAVEFORMS Principles and Applications to Speech and Video. — New Jersey: Prentice-Hall, 1984. 9. Minoli D. Voice Over MPLS Planning and Designing Networks. — McGraw-Hill. Pub, 2002. Received 04.10.2004 UDC 004.93 UDC 004.93 Zoran H. Perić, Marko Milojković, Dragan Antić, Aleksandra Z. Jovanović

Adaptive uniform polar quantization

Репозитарії

Схожі ресурси