Geri Dön

Hareket kestirimi

Motion estimation

  1. Tez No: 46270
  2. Yazar: AYLA ÇEVİK
  3. Danışmanlar: DOÇ.DR. MELİH PAZARCI
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Görüntü, Hareket, Image, Motion
  7. Yıl: 1995
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

ÖZET Hareket kestirimi, hareketli görüntü ileten sistemlerde, kodlanarak iletilecek bilgi miktannı azaltmak için kullanılan bir tekniktir. Hareketli bir resim dizisinde ardışık iki çerçevedeki hareketi bulmak ve vektörler ile ifade etmek için kullanılan temel üç hareket kestirim yöntemi vardın Piksel geriye tekrarlı (recursive) veya gradyan yöntem, blok karşılaştırma yöntemi ve faz korelasyonu yöntemi. Tezde bu yöntemlerden blok karşılaştırma ve faz korelasyonu yöntemleri incelenmiştir. Blok karşılaştırma yönteminde, resimler (b*b) boyutlu alt bloklara bölünür ve birinci çerçevedeki her alt blok, ikinci çerçevede karşı düştüğü konumu içine alan, (2*dm+b)*(2*dm+b) boyutlu tarama alanı içinde aranır. Bu aramada, karşılaştırma kriteri olarak minimum karesel hata kriteri (MSE) veya minimum mutlak hata kriteri (MAE) kullanılır. Arama şu şekilde yapılın Birinci çerçevedeki seçilen blok (referans blok) ikinci çerçevede aynı konumdaki blokla, MAE veya MSE kriterine göre karşılaştırılır ve bir tahmin hatası (PE) bulunur. Bulunan tahmin hatası seçilen alt eşikten (T1) büyükse, blok seçilen yönteme göre tarama alanı içinde aranır. Arama tüm tarama alanı içinde yapılıyorsa buna tüm blokta arama yöntemi denir, ancak bu yöntem çok işlem gerektirdiği için aramayı belirli konumlarda yapanz. işlem sayısını azaltmak için geliştirilen yöntemlerden birisi üç adımda arama yöntemidir. Bu yönteme göre, blok önce üç piksel ötedeki 8 komşu blokla karşılaştırılır ve en küçük tahmin hatasını veren bloğun konumu yeni konum olarak belirlenir. İkinci adımda, yine aynı şekilde referans blok yeni konumdaki blok ve onun 2 piksel ötesindeki 8 blokla karşılaştırılır ve yeni konum belirlenir. Üçüncü adımda aynı işlemler bir piksel ötedeki bloklar için yapılır. Sonuçta bulunan blok ile referans blok arasındaki tahmin hatası seçilen ikinci eşikten (T2) küçükse bulunan blok, referans bloğun ikinci çerçevedeki eşidir. Yeni konumla referans bloğun konumlarının yatayda ve dikeyde farklan alınarak, referans blok için hareket vektörü bulunur. Faz korelasyonu yöntemi, diğer yöntemlerden farklı olarak iki ayn adım içerir. Birinci adımda, resimler (M*M) boyutlu bloklara bölünerek her blok için, bir sonraki çerçevedeki karşı düşen blok ile, korelasyon yüzeyi bulunur ve korelasyon yüzeyindeki tepelerin merkezden uzaklığı ölçülerek hareket vektörleri bulunur. Birinci adımda yalnızca olası hareket vektörleri bulunur. İkinci adımda, bulunan hareket vektörleri blok karşılaştırma yöntemindekine benzer bir karşılaştırma ile, doğru konumlara atanır. Faz korelasyonunda genlik bilgisinin kullanılmaması, yöntemin aydınlatmadaki değişimlerden etkilenmemesini sağlar. Büyük tarama alanı kullanıldığında faz korelasyonu yalnızca belli sayıda vektörü denediğinden, blok karşılaştırmaya göre daha etkili bir yöntemdir. İX

Özet (Çeviri)

SUMMARY MOTION ESTIMATION Motion considerations have become more and more important, specially for low bit-rate coding. The estimation of motion from a sequence of images is important for dynamic scene analysis. Applications include robot vision and medical applications, as well as digital video, which includes video coding, image (sequence) estimation and restoration, and video standard conversions. Motion estimation is a technique for measuring how objects in a television picture move from one frame to another. The movement is expressed as a series of motion vectors which have both direction and magnitude. Motion compensation is a process which uses derived motion vectors to perform some advantageous process. There are a number of different motion estimation techniques which have been developed for use in image processing. In general, only luminance needs to be considered. Different techniques have been developed by different organisations; the most common of these are; 1) Block matching, 2) Pel-recursive or spatio temporal gradient method, 3) Phase correlation. Although various approaches to motion estimation have been developed, most of them could not meet the requirements of real applications. The main reason for this is that the existing algorithms cannot deal with the ///- posedness or ill-conditioning of the estimation problems. (In the presence of little noise, the computational results obtained by using these algorithms vary enormously). There are some advantages or disadvantages of these techniques compared to each other. The most important criteria for the motion estimator are listed below 1) Velocity range: The range of speeds of motion that the estimator can measure. 2) Precision: The accuracy with which the horizontal and vertical components of the motion can be measured.3) Resolution: The accuracy with which the boundaries of moving areas can be defined. 4) Number of vectors: The number of distinct motion measurement that can be made within an area of a picture. 5) Error rate: The number of incorrect motion measurements made. In real scenes, motion can be a complex combination of translation and rotation. Translational estimate is easy and has been used successfully for motion compensated coding. Most of algorithms for motion estimation in interframe coding make the following assumptions : 1) Objects move in translation in a plane that is parallel to camera plane ( i.e. the effects of camera zoom, and object rotation are not considered ). 2) Illumination is spatially and temporally uniform. 3) Occlussion of one object by another, and uncovered background are neglected. Under these assumptions the monochrome intensities f(z,t) and f(z,t-r) of two consequtive frames are related as f(z,t) =f(z-D, t-r) (1) where r is the time between two frames, D is the two dimensional translational vector of the object during the time interval [ t-r, t ] and z is the two dimensional vector [x,y]' of spatial position. Thus, in real scenes a very good prediction of f(z,t) is f = f(z-D, t-r). The problem then is to estimate D from the intensities of the present and previous frame. Let J(x,y,L]) and f(x,y, to) be the previous and current frames. We assume that AwM =Ax-dx, y-<fy, u) (2) where dx and dy are the horizontal and vertical displacement between /_; and to. A uniform motion between /./ and to can be formulated as J[x,y,t) =Ax-Mt-t-i), y-vft-t-ı\ U) /_/<;/<; to (3) where vx and vy are uniform horizontal and vertical velocities. Let J{x,y,t.\) be denoted by s(x,y): s(x,y) =fey,U) (4) aFrom (3) and (4) we obtain; J{x,y,t)=s(a(pc,y,t), P(x,y,t)) (5) where a.{x,y,t)-x-vjf-u) and p.(x,y,t) -y-vy{t-u) From the (5), assuming ${x,y,t)/âc, dfe,y,tydy, and c#(x,y,tyât exist, we obtain f(x,y,t) = s(a(x,y,t),p (x,y,t)), U^tz t0 (6) df(x,y,t) ds da ds dp ds âx da âx d p ax da dy da dy + dJ3 dy dp ^ ' ' df(x,y,t) d s da ds dp ds ds dt“ da dt + dp dt ~~V*~da~~VyTp ( C) and from these equations we obtain the spatio-temporal constraint equation : 0f(x,y,t) df(x,y,t) df(x,y,t) v _ |_y _ + _ _ y IB) dx y dy dt v ' Unfortunately this equation does not allow object rotation, camera zoom, regions uncovered or occluded by translational object motion, or multiple objects moving with different vx, and vy. We can assume a uniform translational motion only locally and estimate two motion parameters (dx,dy), or (v^vy) at each pixel or at each small subimage. There are three main methods of motion estimation which are to be found in various applications: Pel-recursive (or gradient), block matching and phase correlation. In this thesis, block matching and phase correlation methods are studied. Block matching algorithm (BMA) is the simplest technique to estimate the motion. This class of techniques work by dividing the picture into small blocks and they are utilized to estimate the motion of a block of pixels, of size (MxN) in the present frame in relation to pixels in the previous frame. This block of pixels is compared with a corresponding block within a search area of size ((M+2.dm)x(N+2.dm)) in the previous frame (Fig.1), where dm xiiis the maximum displacement allowed. Square subblocks (M=N) are chosen because these were found to be optimal subimages for computational ease. The best match is found based on some specified criteria such as the minimum mean absolute error (MAE) or minimum mean square error (MSE) t N+2*dm M+2*dm The block of size (M*N), in the previous ftame. The search area of size (M+2.dm,N+2.dm), in the current frame. Fig.1 Geometry of the search area. With block methods, it is assumed that the object displacement is constant within a small two-dimensional block of pixels. This assumption presents difficulties in scenes with multiple moving objects or in scenes in which different parts of the same object move with different displacements. If the size of block is decreased then this assumption becomes more valid; however, then the overhead of computation and transmission of displacement information increases. The displacement D can be estimated by correlation or matching techniques. Thus, D can be chosen such that it minimizes some measure of the prediction error as, PE(D)=^N(f(zJ)-f(z-D,t-r)) (11) where N(.) is a distance metric such as the mean absolute error or the mean square error function. i M-lN-l PE(D) = MAEQJ) = - - ZZl/*(«,»)-A.i (m+i,n+j)\ (12) M.N M=0 #=0 1 M-1W-1 PE{D) = M^(iJ) = -~YL{fk(rn,n)-fk_x(m+hn+j)\ (13) The MAE has advantage that no multiplications are required. Also, it is experimentally observed that the precise definition of PE does not have significant effect on the amount of searching or accuracy of estimation of D xniand, therefore due to simplicity, the criterion of equation (12) is generally preferred. In addition to the simplification of the matching criterion, several methods for simplifying the search procedure have been investigated. Three step search and s-step search methods have been studied in this thesis. Before these methods, full search (FS-BMA) has been explained. In full search BMA, reference block is matched with all possible blocks in the search area. The search process begins from the upper left corner of the search area and the process continues towards the right and down. At the end of the search process, the block that gives the minimum prediction error is chosen; this position is pointed as the new position of the reference block and the motion vector is computed as Motion vector X2 Xj dx (14) [xj.yj] is the upper left corner of the reference block in the first frame and [x^yA is the new estimated position of the reference block in the second frame. Several techniques have been developed to reduce the computational cost. The three step search is the most commonly used technique. The three step search algorithm, shown in Fig. 2, can be described as follows: 1) The block characterized by its upper left corner is compared to the corresponding block in the second frame and prediction error (PE) of these two blocks is calculated. If PE < T1 where T1 is the selected lower threshold, then the block is classified as an unchanged or stationary block and the search ends. Otherwise the algorithm continues to the next step. 2) The pixel positions searched next have been circled in Fig.2 Prediction errors at nine positions are calculated and the position which gives the minimum prediction error, is selected as the new position. This new position is the starting point of the third step. 3) The pixel positions searched next are shown in Fig. 2 with cross markers, and the same processes in the second step are earned. The new position found from this step is the starting point of the fourth step. 4) The pixel positions searched are shown in Fig. 2 with square markers. The same processes in the previous steps are realized and the minimum PE position is found. This prediction error is compared xrvwith a selected second upper threshold, T2. If PE < T2, this position is acceptable and the motion vector of the reference block is calculated as in (14); otherwise a motion vector for this reference block is not assigned. In this algorithm, the search area is ±6 pixels. Fig. 2 Three step search procedure. O: matching position for first step; X : matching position for second step;D : matching position for third step. We can increase the number of the steps of the method presented above. In this case, the only difference is the steps. In this method (s-step search), first, the step (s) is selected and the matching process continues until Bs=1”(in every step“s”is decremented by one). In the s-step search s.(s+l) method, the search area is l - - pixels. Two factors strongly effect the results in the block matching algorithms: First, the size of the search area and second, the size of the measurement block. The size of the search area defines the maximum velocity that can be measured. The size of measured block defines the resolution. If a small block size is used then high resolution can be achieved. Unlike block matching algorithms, phase correlation involves two separate processes for motion measurement. First, the picture is analysed XVmathematically to determine what motion directions and velocities exist in the picture without attempting to identity the particular areas of the motion in the picture. Then a second process matches picture areas with particular motion vector candidates. In this technique, the 2-D FFT of each frame is calculated and the phase information from the transforms is used to determine the relative displacement between successive frames. Let us consider two frames Ii and I2 with velocity (v“ vy) pixels per field. The following relation can be written: I2(x,y) = Il(x-vx,y-vy) (15) Taking the Fourier transform of each side and invoking the shifting theorem gives: F2 (m,n) = F, {m,n).e~'ei{mv'^) (1 6) where Fx and _F2are the Fourier transform of Ii and I2, respectively and m, n represent spatial frequencies. The Fourier transform of the cross-correlation of the images is F(c) = F,.f: = fvF?.e2”-“m”'*n"''i (17) If we divide this expression by FVF* before taking the reverse transform, we obtain the useful result Fj.f;1 ~v~ '*'.' 'yi C(x,y) = F-i\-^7\=S(x-vx,y-vy) (18) where F~x represents the inverse FFT. The correlation function has become a delta function situated at the required displacement. More generally, if h was not a pure translation of h but differed in overall luminance, we would calculate ^-^ö (19) The result of these processes gives the correlation surface which can be thought of as a two dimensional 'motion spectrum'» If the picture is stationary, a single, dominant peak is produced at the centre of the 'spectrum' representing zero motion; if the whole image is moving, this XVIpeak will be displaced from the centre by an amount dependent on the velocity of motion. If motion is more complex than a perfect linear pan, then more peaks may occur corresponding to different rates of motion. The second process of this technique uses a spatial matching technique to identify which measured vector provides the best match for individual picture areas. Typically, about six individual peaks can be identified in a practical correlation surface; peaks which appear to be in significant must be ignored. This, of course, results in valid motion information being discarded. In order to increase the number of vectors that can be identified in a picture, the picture may be split into more blocks, each providing its own correlation surface. Some of advantageous of the phase correlation technique are the following: 1) Vectors can be assigned to individual pixels or blocks of pixels. 2) Vectors tend to correspond more closely to the actual motion in the picture than with gradient or block matching techniques. 3) Brightness changes in the scene do not affect the measurement. This technique can provide quite accurate results for simple linear motion but does not perform well with more complex motion such as a rotation where each point on a rotating object has a different direction and velocity of motion. As a result, phase correlation is the optimal choise for high quality motion estimation, because it simultaneously handles small objects and rapid motion. Computer programs have been written to examine the above techniques and the results have been given in Chapter 6. xvu

Benzer Tezler

  1. Tez No

    47998

    Regularized motion estimation techniques and their applications to video coding

    Düzgünleştirilmiş hareket kestirimi teknikleri ve video kodlamadaki uygulamaları

    SERKAN KIRANYAZ

    Yüksek Lisans

    İngilizce

    İngilizce

    1996

    Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    PROF.DR. LEVENT ONURAL

  2. Tez No

    33468

    Three-Dimensional facial motion and structure estimation in video coding

    Görüntü dizisi kodlamada yüze ait üç boyutlu hareket ve yapı kestirimi

    GÖZDE BOZDAĞI

    Doktora

    İngilizce

    İngilizce

    1994

    Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. LEVENT ONURAL

  3. Tez No

    76811

    Modele dayalı kodlama yöntemlerinin incelenmesi

    An Investigation on model based coding

    SERDAR YILMAZ

    Yüksek Lisans

    Türkçe

    Türkçe

    1998

    Elektrik ve Elektronik MühendisliğiAnkara Üniversitesi

    Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. MÜMTAZ YILMAZ

  4. Tez No

    78043

    Trajectory prediction of moving object by means of natural networks

    Başlık çevirisi yok

    HAKAN BARIŞIK

    Yüksek Lisans

    İngilizce

    İngilizce

    1998

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİzmir Yüksek Teknoloji Enstitüsü

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. İ. SITKI AYTAÇ

  5. Tez No

    58602

    Object-based 3-D motion and structure analysis for video coding applications

    Video kodlama uygulamaları için nesneye dayalı üç-boyutlu harket ve derinlik analizi

    A.AYDIN ALATAN

    Doktora

    İngilizce

    İngilizce

    1997

    Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. LEVENT ONURAL

Geri Dön