##
İki boyutlu kafes parametrelerinin sınırlı veri alanlarından hesaplanması

İki boyutlu kafes parametrelerinin sınırlı veri alanlarından hesaplanması

##### Dosyalar

##### Tarih

1994

##### Yazarlar

Yıldız, Nurşen

##### Süreli Yayın başlığı

##### Süreli Yayın ISSN

##### Cilt Başlığı

##### Yayınevi

Fen Bilimleri Enstitüsü

##### Özet

Bir boyutta geliştirilen kafes yapısının bir uzantısı olarak iki boyutlu (2-B)dik kafes süzgeçleri geliştirilmiştir [ 7 ]. Önerilen yöntem çeyrek düzlem veya simetrik olmayan yarı düzleme uygulanabilmektedir. Bu metod ile matris tersi alınmadan iki boyutlu genişletilmiş normal denklemden, kafes parametreleri kullanılarak kestirim yanılgı süzgeç katsayılarım hesaplamak için matris formunda Levinson algoritmasının tam çözümü sunulmaktadır.' Bu çalışmada, sınırlı veri uzunluğuna sahip rastgele alanların özbağlammlı (Autoregressive = AR) modellenmesi için 2-B 'lu dik kafes süzgeçleri sunulmuş, yöntemin doğruluğu simülasyon yolu ile desteklenmiştir. Öncelikle çeyrek veya simetrik olmayan yan düzlem için seçilen maskeye göre özyinelemeli AR veri alanı yaratılmıştır. Yaratılan 2-B 'lu AR veri alanı uygun indeksleme ile 1-B 'lu gibi düşünülebilir. Yine seçilen indekslemeye bağlı olarak birinci çeyrek düzlem geri yönde kestirim yanılgı süzgeci, diğer çeyrek düzlemlerde ileri yönde kestirim yanılgı süzgeçlerine karşılık gelir. Elde edilen sonuçlar incelendiğinde, sınırlı veri uzunlukları için, örnek özilişkilerin kullanıldığı yönteme - Bu yöntem Yule-Walker çözümünü vermektedir.- göre daha başarılı sonuçlar elde edildiği gözlenmiştir [18]. Veri boyutu arttırıldığında, her iki yöntemle de oldukça iyi kestirimler yapılabildiği görülmüştür. İleri ve geri yönlerde kestirim alanlarının dik olması, 2-B 'lu sistem parametrelerinin çözümünde LMS ve RLS gibi adaptif algoritmaların kullanılmalına olanak sağlayacaktır.

The multi-dimensional digital signal processing has been developing quite rapidly due to the fact that it has many applications possibilities in various fields. In fields such as image processing, seismic prospecting, visual data communications and target tracking, the data to be processed are inherently multi-dimensional in charecter and the theoretical developments in 2-D signal processing methods can be applied to these fields. The one dimensional lattice structure occurs in the analysis and synthesis of speech for simulating the vocal tract and also more generally in systems for linear prediction. It allows the realization of FIR and IIR filters. Lattice form algorithms are modular in structure; hence, if the requirement calls for increasing the order of the predictor, one can simply add one or more stages (as desired ) without affecting earlier computations. This modular structure makes lattice filters attractive candidates for VLSI implementation. The most important facility of a lattice structure arises from its property of orthogonality. The property allows the filter to be updated in order, without recalculation of the previous lower order filter coefficients. Lattice algoritms owes their robust numerical behaviour to this property of orthogonality [4]. In recent years there has been quite a lot of research studies directed to the development of 2-D equivalent lattice structures. Howewer all these formulations are capable of implementing only a restricted class of transfer functions. In the literature, a fiindemental approach to modeling 2-D fields by the reflection coefficients was realized by Marzetta [13] who has generalized some results to the 2-D case. He proposed a half-plane support which is infinite in one of the two dimensions. This approach while keeping many of the nice charecteristics of the 1-D lattice filters, leads to very long delay filters. Marzetta's algorithm has been successfully applied to 2-D recursive filter design and to linear predictive coding of images. A different approach proposed by Parker and Kayran [14], simultaneously introduces many points in the support when the model order is increased. The filter uses a quarter- plane support and introduces three parameter at each order update. Therefore, it lacks sufficient parameters to represent all classes of 2-D AR quarter-plane filters. More importantly, it lacks the property of orthogonality so that the cascading of stages may not lead to an optimum filter [1]. -v-Recently, Ertüzün [3] presented a new and improved lattice structure developed form the three parameter lattice filter. It was shown that this new structure approximates the maximum entropy more closely compared to the three-parameter structure. The increase in entropy naturally leads to a more reliable and better modeling of AR fields. A relation between multi-channel AR model and single channel 2-D models with quadrant support is proposed by Therrien [17] where simultaneous computation of parameters of all four quarter-plane filters is possible. This method is generalized to multichannel 2-D models and applied to the problem of estimation of the 2-D autospectral and cross spectral components. Lenk and Parker [9], [10] have extended the well- known Levinson and Schur algorithms to the 2-D case for modeling stationary random fields. In this contribution, tensor concepts were used to derive lattice filters presented by considering orthogonalizing coordinate transformations. Kwan and Lui [8] showed that this structure inherits most of the nicer characteristics of the one dimensional lattice filter such as high modularity, low coefficient sensitiveness, low rond off noise and elimination of internal overflow. Türe [18], recently investigated the theory developed by Kayran about the orthogonal 2-D lattice structure for AR modeling of random fields. He showed the validity of the mentioned theory for the given covariance case and by using sample autocorrelation values (Yule -Walker Method) of the original data fields. The result of his simulations showed that the computing of sample autocorrelations would not give sufficient results for short data records. As the data record gets longer, it was observed that the resulting estimation spectrums closely converged the original ones. In this thesis, the theory developed by Kayran is investigated by using Burg's estimation methods. Simulation programs for various ordered filters and have been developed to verify the theory. All the results obtained are compared by the results obtained in Ture's study. The comparisons have been made made in spectrum and contour plot bases. It was shown that the estimation by Burg's method has priority over the sample autocorrelation method -as expected- for shorter data records. As the data record gets longer, both of the methods prove to give sufficient results. Two dimensional orthogonal lattice filters are a natural extension of the one dimensional lattice parameter theory. The method offers a complete solution for the Levinson- type algorithm in matrix form to compute the prediction error filter coefficients using lattice parameters from the given two dimensional augmented normal equation. The proposed theory can be used for the quarter plane and half plane models. -VI-Using two dimensional orthogonal lattice filters in two dimensional spectrum estimation can be classified high resolution and parametric method. For the short data records, this method gives better results than the classical periodogram or FFT-based methods. If the data size extends, then both methods get better but in this situation data may not remain stationary. In the 2-D AR modeling, a stationary random field y(k,,1^ ) is predicted by a linear combination of its neighboring samples. The procedure starts with creating the AR data field according to the prediction region mask which may be quarter-plane or asymmetric half-plane. The 2-D AR data field can be considered as a one dimensional array if the appropriate indexing is chosen. Depending on the indexing specified, for instance the first quadrant backward prediction error filter corresponds to the forward prediction error filters in the second or fourth quadrants. Let us show the 2-D AR data in the indexed form as; yoMki, h) = [K(*i, *2) - 0) y{{hM) - 1) y((hM -N)] where the subscripts 0 and N denote the first and and the last elements in the array respectively. The 2-D non-Toeplitz, symmetric correlation matrix; Roy - £\_yoAh > fe) yl^h > k2) J without taking the inverse of the correlation matrix, and using the partitioned form, can be written as shown below: Row - Ro,m-l fm,Q T T m,0 I'm,m T ro,o r0" fo,»ı Rl,i An efficient method for factoring the symmetric 2-D correlation matrix is called Choleskey factorization and is commonly used in lattice form algorithms. The forward prediction error associated with the prediction of the 0-th sample from the previous m samples within the prediction region can be defined in the compact form shown below: ff\kl,k2) = (tffyUkiM where af> = [l afO) af\m)J -VU-and yoAhM) = \ym,k2)-0) y((h,k2)-i) y(ih,k2)-my\T where the notation y((k1,k^)-i) denotes the i-t element behind y(k,,)Q and the subscripts 0 and m denote the first and the last elements in the array respectively. The bacward prediction error associated with the prediction of the m-th sample (last element), y (( k,,1^ )-m), from the m samples prior to it in the prediction region is defined by: bm\ki,k2)=gm) yo,m(k\,k2) where *â° = OS°0») gSV-i) s2°(i) i] In the Levinson order - update recursions, one can find general expressions for lattice parameters, forward and backward prediction error fields and error powers in more compact form. Forp=l, 2,,mandn=l, 2,,p, lattice parameters can be written as; Jp-n <») v(»-l) "P. pW _ afp-n An-l) V-» >-i) and the minimum mean square errors are given by Ef=n Jo \k\,K2) -İ5./0 (1-1/b i-bj and e£> =E[bW\kuk2)] =Etl\i -rf rff). It is known that, A^l) = A^^ and it can be interpreted as a cross-correlation between the forward and backward prediction errors, Atbx:=E[/r\Kk2)b^\kuk2)] The error propagation equations or general form of the orthogonal 2-D lattice filters is given by; MnQllM).(») bF(kiM 1 Tf Dp r (») /; p-n 1 f£\ki,k2) b{p-l\kuk2) -vııı-p=l, 2,,m ; n=l, 2,,p, and starting with ff\kuk2) = bf\kuk2) = y{{kuk2)~P) for p=0, 1,,m, algorithm starts from the 0-th order and continues up to the m-th order. The prediction error powers can be written as; Ef Jp-n Op 1 -Tb -T {nf ft p-n {nf 'p Jp-n Op In this thesis, an example has been given in order to explain the outline of the theory by means of a first quadrant support second order quarter - plane model. In addition to this example* simulation programs that verify the theory has been presented in appendix-A. Synthesis model and the stability conditions has also been investigated. Since the lattice parameter stages are in tandem in the synthesis model, a sufficient condition for overall stability of the synthesis lattice model is that each stage should be stable. The realization of stability related to each stage has been shown by the help of Marzetta's [13] theorem. The proposed 2-D lattice structures are amenable to systolic implementations. This is quite significant as the processing of the 2-D data fields such as images in real time require high data rates. The simplicity of the algorithm is the main attractive feature and the only requirement is to select an ordering scheme with two types of shifts ( vertical or horizantal ) in the prediction support region. As a result of this, the firt stages are 1-D lattice filters. As the lattice structures form orthogonal bases, linear adaptive algorithms such as least mean-square (LMS) and recursive least - squares (RLS ) can be applied to solve for 2-D system parameters. It is anticipated that the orthogonality property of the structure can be utilized to derive 2-D lattice autoregressive-moving average (ARMA) models, and to solve the 2-D joint-process estimation problem.

The multi-dimensional digital signal processing has been developing quite rapidly due to the fact that it has many applications possibilities in various fields. In fields such as image processing, seismic prospecting, visual data communications and target tracking, the data to be processed are inherently multi-dimensional in charecter and the theoretical developments in 2-D signal processing methods can be applied to these fields. The one dimensional lattice structure occurs in the analysis and synthesis of speech for simulating the vocal tract and also more generally in systems for linear prediction. It allows the realization of FIR and IIR filters. Lattice form algorithms are modular in structure; hence, if the requirement calls for increasing the order of the predictor, one can simply add one or more stages (as desired ) without affecting earlier computations. This modular structure makes lattice filters attractive candidates for VLSI implementation. The most important facility of a lattice structure arises from its property of orthogonality. The property allows the filter to be updated in order, without recalculation of the previous lower order filter coefficients. Lattice algoritms owes their robust numerical behaviour to this property of orthogonality [4]. In recent years there has been quite a lot of research studies directed to the development of 2-D equivalent lattice structures. Howewer all these formulations are capable of implementing only a restricted class of transfer functions. In the literature, a fiindemental approach to modeling 2-D fields by the reflection coefficients was realized by Marzetta [13] who has generalized some results to the 2-D case. He proposed a half-plane support which is infinite in one of the two dimensions. This approach while keeping many of the nice charecteristics of the 1-D lattice filters, leads to very long delay filters. Marzetta's algorithm has been successfully applied to 2-D recursive filter design and to linear predictive coding of images. A different approach proposed by Parker and Kayran [14], simultaneously introduces many points in the support when the model order is increased. The filter uses a quarter- plane support and introduces three parameter at each order update. Therefore, it lacks sufficient parameters to represent all classes of 2-D AR quarter-plane filters. More importantly, it lacks the property of orthogonality so that the cascading of stages may not lead to an optimum filter [1]. -v-Recently, Ertüzün [3] presented a new and improved lattice structure developed form the three parameter lattice filter. It was shown that this new structure approximates the maximum entropy more closely compared to the three-parameter structure. The increase in entropy naturally leads to a more reliable and better modeling of AR fields. A relation between multi-channel AR model and single channel 2-D models with quadrant support is proposed by Therrien [17] where simultaneous computation of parameters of all four quarter-plane filters is possible. This method is generalized to multichannel 2-D models and applied to the problem of estimation of the 2-D autospectral and cross spectral components. Lenk and Parker [9], [10] have extended the well- known Levinson and Schur algorithms to the 2-D case for modeling stationary random fields. In this contribution, tensor concepts were used to derive lattice filters presented by considering orthogonalizing coordinate transformations. Kwan and Lui [8] showed that this structure inherits most of the nicer characteristics of the one dimensional lattice filter such as high modularity, low coefficient sensitiveness, low rond off noise and elimination of internal overflow. Türe [18], recently investigated the theory developed by Kayran about the orthogonal 2-D lattice structure for AR modeling of random fields. He showed the validity of the mentioned theory for the given covariance case and by using sample autocorrelation values (Yule -Walker Method) of the original data fields. The result of his simulations showed that the computing of sample autocorrelations would not give sufficient results for short data records. As the data record gets longer, it was observed that the resulting estimation spectrums closely converged the original ones. In this thesis, the theory developed by Kayran is investigated by using Burg's estimation methods. Simulation programs for various ordered filters and have been developed to verify the theory. All the results obtained are compared by the results obtained in Ture's study. The comparisons have been made made in spectrum and contour plot bases. It was shown that the estimation by Burg's method has priority over the sample autocorrelation method -as expected- for shorter data records. As the data record gets longer, both of the methods prove to give sufficient results. Two dimensional orthogonal lattice filters are a natural extension of the one dimensional lattice parameter theory. The method offers a complete solution for the Levinson- type algorithm in matrix form to compute the prediction error filter coefficients using lattice parameters from the given two dimensional augmented normal equation. The proposed theory can be used for the quarter plane and half plane models. -VI-Using two dimensional orthogonal lattice filters in two dimensional spectrum estimation can be classified high resolution and parametric method. For the short data records, this method gives better results than the classical periodogram or FFT-based methods. If the data size extends, then both methods get better but in this situation data may not remain stationary. In the 2-D AR modeling, a stationary random field y(k,,1^ ) is predicted by a linear combination of its neighboring samples. The procedure starts with creating the AR data field according to the prediction region mask which may be quarter-plane or asymmetric half-plane. The 2-D AR data field can be considered as a one dimensional array if the appropriate indexing is chosen. Depending on the indexing specified, for instance the first quadrant backward prediction error filter corresponds to the forward prediction error filters in the second or fourth quadrants. Let us show the 2-D AR data in the indexed form as; yoMki, h) = [K(*i, *2) - 0) y{{hM) - 1) y((hM -N)] where the subscripts 0 and N denote the first and and the last elements in the array respectively. The 2-D non-Toeplitz, symmetric correlation matrix; Roy - £\_yoAh > fe) yl^h > k2) J without taking the inverse of the correlation matrix, and using the partitioned form, can be written as shown below: Row - Ro,m-l fm,Q T T m,0 I'm,m T ro,o r0" fo,»ı Rl,i An efficient method for factoring the symmetric 2-D correlation matrix is called Choleskey factorization and is commonly used in lattice form algorithms. The forward prediction error associated with the prediction of the 0-th sample from the previous m samples within the prediction region can be defined in the compact form shown below: ff\kl,k2) = (tffyUkiM where af> = [l afO) af\m)J -VU-and yoAhM) = \ym,k2)-0) y((h,k2)-i) y(ih,k2)-my\T where the notation y((k1,k^)-i) denotes the i-t element behind y(k,,)Q and the subscripts 0 and m denote the first and the last elements in the array respectively. The bacward prediction error associated with the prediction of the m-th sample (last element), y (( k,,1^ )-m), from the m samples prior to it in the prediction region is defined by: bm\ki,k2)=gm) yo,m(k\,k2) where *â° = OS°0») gSV-i) s2°(i) i] In the Levinson order - update recursions, one can find general expressions for lattice parameters, forward and backward prediction error fields and error powers in more compact form. Forp=l, 2,,mandn=l, 2,,p, lattice parameters can be written as; Jp-n <») v(»-l) "P. pW _ afp-n An-l) V-» >-i) and the minimum mean square errors are given by Ef=n Jo \k\,K2) -İ5./0 (1-1/b i-bj and e£> =E[bW\kuk2)] =Etl\i -rf rff). It is known that, A^l) = A^^ and it can be interpreted as a cross-correlation between the forward and backward prediction errors, Atbx:=E[/r\Kk2)b^\kuk2)] The error propagation equations or general form of the orthogonal 2-D lattice filters is given by; MnQllM).(») bF(kiM 1 Tf Dp r (») /; p-n 1 f£\ki,k2) b{p-l\kuk2) -vııı-p=l, 2,,m ; n=l, 2,,p, and starting with ff\kuk2) = bf\kuk2) = y{{kuk2)~P) for p=0, 1,,m, algorithm starts from the 0-th order and continues up to the m-th order. The prediction error powers can be written as; Ef Jp-n Op 1 -Tb -T {nf ft p-n {nf 'p Jp-n Op In this thesis, an example has been given in order to explain the outline of the theory by means of a first quadrant support second order quarter - plane model. In addition to this example* simulation programs that verify the theory has been presented in appendix-A. Synthesis model and the stability conditions has also been investigated. Since the lattice parameter stages are in tandem in the synthesis model, a sufficient condition for overall stability of the synthesis lattice model is that each stage should be stable. The realization of stability related to each stage has been shown by the help of Marzetta's [13] theorem. The proposed 2-D lattice structures are amenable to systolic implementations. This is quite significant as the processing of the 2-D data fields such as images in real time require high data rates. The simplicity of the algorithm is the main attractive feature and the only requirement is to select an ordering scheme with two types of shifts ( vertical or horizantal ) in the prediction support region. As a result of this, the firt stages are 1-D lattice filters. As the lattice structures form orthogonal bases, linear adaptive algorithms such as least mean-square (LMS) and recursive least - squares (RLS ) can be applied to solve for 2-D system parameters. It is anticipated that the orthogonality property of the structure can be utilized to derive 2-D lattice autoregressive-moving average (ARMA) models, and to solve the 2-D joint-process estimation problem.

##### Açıklama

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 1994

##### Anahtar kelimeler

Kafes filtreler,
Matrisler,
Parametreler,
Lattice filters,
Matrices,
Parameters