You will be presented with the full text of a science research paper. Please write an abstract for this paper. Your response should include the abstract and no additional text.

Paper text:
with the increasing popularity of technologies such as digital television , internet streaming video and video conferencing , video compression has became an essential component of broadcast and entertainment media . among various kinds of approaches , block - based motion estimation and compression
are most widely accepted ones .
the _ block - matching algorithm_(bma ) for _ motion estimation_(me ) has been adopted in many international standards for digital video compression , such as h.264 and mpeg 4@xcite . in the framework of video coding
, the statistical redundancies can be categorized by either temporal or spatial . for the purpose of reducing the temporal redundancies among frames ,
motion estimation was applied@xcite .
block - based matching algorithms consider each frame in the video sequence formed by many nonoverlapping small regions , called the marcoblocks(mb ) which are often square - shaped and with fixed - size(@xmath0 or @xmath1 ) .
let @xmath2 represents the @xmath3th mb and @xmath4 the number of blocks , and @xmath5 ; let @xmath6 be the entire frame and the partition into mbs should satisfy @xmath7 and @xmath8@xcite .
given a mb @xmath2 in the anchor frame , the motion estimation problem is to determine a corresponding matching mb @xmath9 in the target frame such that the matching error between these two blocks is minimized .
then , a motion vector is computed by subtracting the coordinates of the mb in the anchor frame from that of the matching mb in the target frame . instead of sending the entire frame pixel - by - pixel , a set of motion vectors
is transmitted through the channel which greatly reduces the amount of transmission . in the decoder side
, a motion compensated procedure is applied to reconstruct frames using the received motion vectors and the anchor frame . referred to many researches ,
the motion estimation and encoding part consumes nearly @xmath10 percent of the total amount of computation in the whole video compression procedure thus making it an active research topic in the last two decades .
there are many proposals of bmas in literature .
the most basic one is the _ exhaustive search_(es ) , also known as full search which simply compares the given mb in the anchor frame with all candidate mbs in the target frame exhaustively within a predefined search region .
previous research showed that es can obtain high matching accuracy but requires a very large amount of computation thus infeasible to implement in real - time video applications . to speed up the search , various fast algorithms for block matching which reduce the number of search candidates
have been developed .
well known examples are _
2-d logarithmic search_(logs)@xcite , _ three step search_(tss)@xcite , _ four step search_(4ss)@xcite , _ diamond search_(ds)@xcite which is accepted in the mpeg-4 verification model and widely implemented in vlsi , and the recent proposed _ adaptive rood pattern search_(arps)@xcite which is almost two or three times faster than ds and even achieves higher _ peak signal - to - noise ratio_(psnr ) than that using ds .    from the optimization point of view
, block - based methods can be described by the following minimization@xcite , @xmath11 :    @xmath12 - i_{k-1}[\mathbf{n}+\mathbf{d}_{m}])\ ] ]    where @xmath13 is the target frame ; @xmath14 is the anchor frame ; @xmath15 is the matching error ; @xmath16 are the motion vectors and @xmath17 is the search area to which @xmath18 belongs , defined as @xmath19 .
sign of @xmath20 is positive when motion of the block is towards positive direction from @xmath21th frame to @xmath22th frame . and negative when motion of the blcok is in negative direction from @xmath21th frame to @xmath22th frame .
@xmath23 is an @xmath24 size mb with the top - left corner coordinate at @xmath25 .
the goal is to find the best displacement motion vector @xmath26 for each mb @xmath23 , in the sense of the criterion @xmath27 .
_ particle swarm optimization_(pso ) was originally proposed by kennedy and eberhart in 1995@xcite .
it is widely accepted and focused by researchers due to its profound intelligence background and simple algorithm structure .
currently , pso has been implemented in a wide range of research areas such as functional optimization , pattern recognition , neural network training , fuzzy system control etc . and obtained significant success . like _
genetic algorithm_(ga ) , pso is also an evolutionary algorithm based on swarm intelligence .
but , on the other side , unlike ga , pso has no evolution operators such as crossover and mutation@xcite . in pso ,
the potential solutions , called particles , fly through the solution space by following the current optimum particles . the original intent was to graphically simulate the graceful but unpredictable choreography of a bird flock . through competitions and cooperations ,
particles follow the optimum points in the solution space to optimize the problem .
many proposals indicate that pso is relatively more capable for global exploration and converges more quickly than many other heuristic algorithms@xcite .
the rest of the paper is organized as follows .
section ii introduces the pso algorithm and we propose the pso - zmp block - matching algorithm for motion estimation in section iii .
simulation results and analysis on five video sequences are given in section iv .
section v concludes the paper .
particle swarm algorithm is a kind of evolutionary algorithm based on swarm intelligence .
each potential solution is considered as one particle , and these particles are distributed stochastically in the high - dimensional solution space in the initialization period of the algorithm . through following the optimum discovered by itself and the entire group , each particle periodically updates its own velocity and position .
@xmath28    @xmath29    @xmath30    where , @xmath31 is the number of particles and @xmath32 is the dimensionality ; @xmath33 , @xmath34 $ ] is the velocity vector of particle @xmath35 which decides the particle s displacement in each iteration .
similarly , @xmath36 , @xmath37 $ ] is the position vector of particle @xmath35 which is a potential solution in the solution space .
the quality of the solution is measured by a fitness function ; @xmath38 is the inertia weight which decreases linearly during a run ; @xmath39 are both positive constants , called the acceleration factors which are generally set to 2.0 ; @xmath40 and @xmath41 are two independent random number distributed uniformly over the range @xmath42 $ ] ; and @xmath43 , @xmath44 are the best solutions discovered so far by the group and itself respectively .    in the @xmath45 time iteration , particle @xmath35 uses @xmath43 and @xmath44 as the heuristic information to updates its own velocity and position .
the first term in eq.[vid.original ] represents the diversification , while the second and third intensification .
the second and third terms should be understood as the trustworthiness towards itself and the entire social system respectively .
therefore , a balance between the diversification and intensification is achieved based on which the optimization progress is possible .
in this paper , an algorithm based on _ particle swarm optimization_(pso ) and _ zero - motion prejudgment_(zmp ) is proposed to reduce the computation and obtain satisfied compensated video quality .
the pso - zmp algorithm consists of three sequential routines .
1)zero - motion prejudgment ; 2)predictive image coding ; 3)pso matching . instead of distributed stochastically in the entire matching space
, we also devise a novel distribution pattern for particle initialization to bear the center - biased characteristics of common motion fields .
as widely adopted , we measure the amount of computation and the quality of compensated video sequence by _ computation _ and _ peak signal - to - noise ratio_(psnr ) .
computation is defined as the average number of the error function evaluations per mv generation . due to the minimum computational cost
, we choose _ summed absolute difference_(sad ) as the error function which is defined as follows :    @xmath46    where the size of a mb is @xmath24 .
+ the motion estimate quality between the original @xmath47 and the compensated video sequences @xmath48 is measured in psnr which is defined as :    @xmath49    @xmath50    where @xmath51 is the number of frames in the video sequence .
zero - motion prejudgment(zmp ) was firstly introduced in @xcite .
data shown in @xcite represented that in most of test sequences , more than 70% of the mbs are static which do not need the remaining search .
so , significant reduction of computation is possible if we perform the zmp procedure before the follow - up predictive coding and pso matching routine .
we first calculate the matching error(sad in this paper ) between the mb in the anchor frame and the mb at the same location in the target frame and then compare it to a predetermined threshold , saying @xmath52 .
if the matching error is smaller than @xmath52 , we consider this mb static which do not need any further motion estimation , and return a @xmath53 $ ] as its motion vector(mv ) .      based on the center - biased characteristics in video sequences , that is ,
certain mbs are highly correlated in local regions of the frame , the encoder creates a prediction of a region of the current frame based on previously encoded and transmitted frames .
if the frame is processed in raster order , the current - encoded mb should have four patterns of _ region of support_(ros ) that consists of the neighboring blocks whose mvs will be used to compute the predicted mv for prediction in fig .
[ pre.pattern ] due to the limited computational cost . experiment mentioned in @xcite shows there is little psnr difference using these four ros patterns in the predictive coding routine , and ros type d consumes least amount of computation because of its simplest structure .
thus , ros pattern d is adopted in this paper .      due to the spatial correlation characteristics between mbs in one frame , during the initiation period of the pso matching routine , we distribute the particles in four specific patterns(fig .  [ pattern.all ] ) with a view to reduce the computational cost but to achieve higher psnr .
since frames are processed in raster order , the mb in the top - left corner in the frame , can not be predictive coded because there is no reference mb for prediction in the current - encoded frame .
thus , for this condition , we simply skip the predictive coding and begin pso searching routine directly with the initial positions of particles in the pattern type b in fig .
[ pattern.all ] .    for those mbs located at the leftmost column of frames ,
their reference mbs used in predictive coding are in the other side of the frame , thus may not be highly correlated and inefficient in prediction .
so , we also solely perform the pso searching routine in this case , with the pattern type d in fig .
[ pattern.all ] . and , for the last leftmost
mb been processed in the frame , that is , the mb in the bottom - left corner , we use the pattern type c in fig .
[ pattern.all ] instead .
otherwise , pattern type a in fig .
[ pattern.all ] is adopted .
we put four particles in a rood shape with size zero(size refers to the distance between any vertex point and the center - point ) in the adjacent mbs and four particles in a rood shape with size one , and then rotate it by angle @xmath54 . with two rood shape in difference size
, we try to balance the global exploration and local refined search in order for broader searching space as well as higher matching accuracy .
moreover , we distribute particles equally in all directions(8 particles in 8 directions ) with a view to , in stochastic condition , find the matching mb in each direction with equal possibility .
notably , if the position of a particle in the during initialization and a pso run is out of the boundary of the image frame , we simply put the particle in the position nearest to its intended position .
generally , there are two widely adopted stopping criteria .
fixed - iteration _ , that is , given a certain iteration time , saying @xmath31 , the search stops after @xmath31 times of iteration
. the other is _ specified - threshold_. during a pso run , the most - fitted value found by the entire group @xmath55 , called the 
_ best so far _ " value will be updated by the particles . for minimization problems , we specify a very small threshold @xmath56 , and if the change of @xmath55 during @xmath57 times of iteration is smaller than the threshold , we consider the group best value very near to the global optimum , thus the matching procedure stops . due to the center - biased characteristics of real - world motion fields ,
we adopt the fixed - iteration method in this paper for reducing the computational cost .
we incorporate the zmp , the predictive coding and the pso matching routines together and propose a block - matching algorithm for motion estimation based on pso and zmp .
the algorithm can be summarized in the pseudocode below : +
we ve tested our pso - zmp algorithm on five test video sequences : akiyo , container , mother & daughter , news and silent within 100 image frames(except 90 frames in akiyo due to the limitation of the sequence length ) .
pso matching is the core routine in our algorithm . in this paper , to balance between computational cost and compensated video quality , we adopt the standard pso with inertia weight@xcite which is widely considered as the defacto pso standard .
we use the fixed - iteration stopping criterion with max 5 iterations .
the max velocity is set to 5 .
the inertia weight @xmath38 decreases linearly from 0.9 to 0.4 during a pso run and two acceleration factors @xmath58 , @xmath59 are set to 2.0 , as commonly did .
* we divide a whole image frame into @xmath60 mbs in the simulation . *
we select a zmp threshold @xmath52 for each test video sequence correspondingly based on data obtained in experiments .
the parameters are shown in table  [ zmp.table ] .
* we do not restrict the range of candidate matching mbs rigidly by a search window @xmath17 . instead , through the fixed - iteration and the setting of max velocity , particles search for the matching mb in an area more flexible and adaptable .    .zmp
threshold @xmath52 for five test video sequences [ cols="^,^,^",options="header " , ]
in this paper , we have proposed a fast block - based motion estimation algorithm based on _ particle swarm optimization_(pso ) with novel particle initiation patterns . applied successfully in many functional and combinatorial optimization problems
, pso is proved to have a relevant stronger ability in global exploration .
in addition , a _ zero - motion prejudgment_(zmp ) routine is incorporated into the pso bma to further reduce the computational cost of the algorithm .
simulation results show that the pso - zmp bma proposed requires less amount of computation and achieves psnr in a acceptable degree of drop . while close and acceptable psnr performance compared to
widely accepted arps and ds bma .
moreover pso just consumes a few lines of codes due to its simplicity which makes the pso - zmp algorithm attractive for hardware implementation .    in the future
, variants of pso might be applied to strengthen the global searching ability and the accelerate the convergence speed . and , to speed up the search and avoid being trapped in local minima , a multiresolution procedure may be used .
the authors would like to thank qian wu for helping us make the nice search pattern figures and yuxuan wang for the invaluable discussion and proofreading .
s.zhu and k.k.ma . a new diamond search algorithm for fast block - matching motion estimation . in _ proc .
information , communications and signal processing(icics ) _ , volume  1 , pages 292296 , sept.9 - 12 1997 .
in this paper , we propose a fast 2-d block - based motion estimation algorithm called _ particle swarm optimization - zero - motion prejudgment_(pso - zmp ) which consists of three sequential routines : 1)zero - motion prejudgment . 
 the routine aims at finding static macroblocks(mb ) which do not need to perform remaining search thus reduces the computational cost ; 2)predictive image coding and 3)pso matching routine . 
 simulation results obtained show that the proposed pso - zmp algorithm achieves over 10 times of computation less than diamond search(ds ) and 5 times less than the recent proposed adaptive rood pattern searching(arps ) . meanwhile 
 the psnr performances using pso - zmp are very close to that using ds and arps in some less - motioned sequences . while in some sequences containing dense and complex motion contents , 
 the psnr performances of pso - zmp are several db lower than that using ds and arps but in an acceptable degree .