# Block Matching Motion Estimation Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Block Matching Motion Estimation is known as technique to achieve high compression ratio in video coding has been generally adopted in various coding standards. By exhaustively testing all the candidate blocks within three search window, this technique is implemented conventionally. Full Search (FS) Algorithm is the type of implementation which is provided the optimum solution. However, this algorithm is required substantial amount of computational workload. To overcome this imperfection, many fast Block Matching Algorithms (BMA's) have been designed and developed. In order to find the optimum motion vector with minimal number of required search points, different search patterns and strategies is exploited.

One of these fast BMA's, which is proposed to be implemented in this project, is called Kite Cross Diamond Search (KCDS) Algorithm. The student is required to implement the algorithm in MATLAB and then compare its performance to FS algorithm as well as to other fast BMA's in terms of the peak signal-to-noise ratio (PSNR) produced, number of search points required and computational complexity.

## 1.2 PROBLEM STATEMENTS

Block matching method is to seek for the best matched block from the previous frame, which is the first single frame, within a fixed-sized of search window (w).It introduce the Full search (FS) method. In order to search the block with minimum distortion, full search method matches all possible displaced candidate block within the search area in the reference frame, so this FS algorithm have large motion and more searching point to do the blocks matching. It also introduces high intensive computation. Many fast motion estimation algorithms have been proposed to give a faster estimation with similar block distortion compared to FS over the last two decades. The fast Block matching algorithms are the three step search (TSS), the hexagon based search (HEXBS), the diamond search (DS), the new cross diamond search (NCDS) and kite cross diamond search (KCDS).

## SCOPES OF WORKS

The scopes of works in this project are:

## Background Study:

Study on video or image compression, Motion Estimation, Block Matching Algorithm and Kite Cross Diamond Search (KCDS).

## Implementation of the Kite Cross Diamond Search algorithm using MATLAB.

The proposed algorithm is implemented and simulated using MATLAB.

## Performance Analysis

The performance of Kite Cross Diamond Search (KCDS) algorithm is compared with existing fast block matching motion estimation algorithms.

## OBJECTIVE

The main objective for this project is to implement a one of the available fast Block Matching algorithm Kite Cross Diamond Search (KCDS). The others objectives are:

To implement and develop the of Kite Cross Diamond Search (KCDS) algorithm by using the MATLAB.

To compare the performance of Kite Cross Diamond Search (KCDS) with other algorithm.

To produce working MATLAB program code for the algorithm

## CHAPTER 2

## LITERATURE REVIEW

## 2.1 Video Compression

Video compression is to simplify the quantity of data used to represent digital video images, and is a combination of spatial image compression and temporal motion compensation. Its plays an important role in digital libraries, video in demand and high definition television which are an example of applications of digital video. To exploit the spatial and temporal redundancy of video sequence, it needs used fewer bits to represent a video sequence at an acceptable visual distortion. Besides that, it also represents the objective of a video compression algorithm. [1]

The moving objects in an image sequence is identify by the object based video coding, then their boundaries and interiors is codes and separately. By using motion estimation and coding, video compression is exploiting the spatial and temporal redundancy. It compressed video can effectively reduce the bandwidth required to transmit video. [2]

## 2.2 Motion Estimation

Motion estimation is the process of determining motion vectors that describe the transformation from one 2D image to another; usually from adjacent frames in a video sequence. The temporal prediction technique used in MPEG video is based on motion estimation. To sending a full frame, the inherently have less energy and can be compressed by sending a encoded difference images, it need to save on bits. This is for the idea of motion estimation based video compression. From the video sequence, the motion estimation takes out the motion information.

Motion estimation is to estimate the pels or pixels of the current frame from reference frame. All the video consists of many sequences of frame. To calculate the low energy residue, the motion information is needed to use in video compression to find best matching block in reference frame. The Motion Compensation is to use of the knowledge of the displacement of an object is better successive frames.

By modifying the reference frames, which is very close match to the current frame, for the current frame will create a model by the motion estimation module. The motion vectors is relate to the whole image or specific parts, such as rectangular blocks, arbitrary shaped patches or even per pixel. Frame-rate video conversion, video compression, video retrieval and video surveillance are the example of video applications, and the key role of those applications in motion estimation.

## 2.3 Block Matching Algorithm (BMA)

The temporal redundancy remove technique between 2 or more successive frame is called block matching algorithm (BMA). It is an integral part for most of the motion-compensated video coding standards. Marco blocks (MB) is the frames are being divided into regular size blocks. The macro block is compared with equal block and its adjacent neighbors in the previous frame to create a vector that stipulates the movement of a macro block from one location to another in the previous frame. In the current frame, all macro blocks comprise a frame and this movement is calculated. [3]

Block matching method is to seek for the best matched block from the previous frame, usually the first single frame, within a fixed sized of search window (w). The displacement of the best matched block will be described as the motion vector (MV) to the block in the current frame by based on a block distortion measure (BDM) or other matching criteria.

Figure 2.1: The two frames used to determine the motion vector of a given block. [3]

Figure 2.2: Block matching a macro block

The best match is usually evaluated by a cost function based on a BDM such as Mean Square Error (MSE) and Mean Absolute Difference (MAD) is the less computationally and the most popular.

Many fast block-matching algorithms have been developed, for example, three-step search (TSS), four-step search (4SS), Diamond Search (DS), etc. These fast BMA exploit different search patterns and search strategies for finding the optimum motion vector with drastically reduced number of search points as compared with the FS algorithm.

## 2.4 Full Search Algorithm

Full search (FS) algorithm is a most accurate strategy in BMA which evaluates all possible candidate motion vectors in search window to find the optimum. The candidate that gives the best match for a given block distortion measure is chosen as the estimated motion vector.

## 2.5 Type of Fast Motion Estimation Algorithm

-Three Step Search (TSS) algorithm

- Hexagon based search (HEXBS) algorithm

- Diamond search (DS) algorithm

- New cross diamond search (NCDS) algorithm

- Kite Cross Diamond search (KCDS) Algorithm

## 2.5.1 Three Step Search (TSS) algorithm

One of the widely used in block matching motion estimation is the three-step search (TSS) algorithm. [4] This is because due to its simplicity and effectiveness. For the searching large motion, the sparsely distributed checking point's pattern is the suitable for this condition.. Among these fast BMAs, the three-step search (TSS) algorithm becomes the most popular because of its simplicity and effectiveness. Searching with a large pattern in the first step, TSS is more efficient to find the globe minimum especially for those sequences with large motion.

The Step had shown the TSS method.

At the first step, the initial step size is picked. From the centre (One center point and eight points on the boundary of the search square), eight blocks at a distance are compared in the first step and thereafter only 8 points are searched.

At the start of a new step the search point center is moved from the best matching point from the previous step. Step size is reduced by half after each step.

At the end of the search the step size is one pel.

## 2.5.2 Hexagon Based Search (HEXBS) Algorithm

To achieve the fastest search speed, the minimum number of search points and circle-shaped search pattern with uniform distribution is desirable to choose. Hexagon based search (HEXBS) algorithm [5] is the one of the faster block matching algorithm. The Figure 2.3 is shown search points of HEXBS. The number 1 is represent larger hexagon pattern which has seven check points and the number 2 is represent the inner search for the final search points.

Figure 2.3 Hexagon based search (HEXBS)

The hexagon-based search (HEXBS) algorithm steps is shown below

Step 1 : Step 1 is using the seven search points (large hexagon) to search window in the motion field. If the MBD point is at the center of the hexagon, the go step 3; otherwise, go step 2.

Step 2 : In step 2, the new large hexagon is formed by according to the MBD point in the previous search step as the center. If the MBD point is at the center point of the newly formed hexagon, then proceed to step 3; otherwise, repeat this step continuously.

Step 3 : Step 3 is the ending step. From the large hexagon, the search pattern is switch to small size. The new MBD point is search by compare the small size hexagon and the current MBD. The new MBD point is the final solution if motion vector.

## 2.5.3 Diamond Search (DS) algorithm

Diamond Search (DS) [6] algorithm is one of the fast block matching algorithm. There are two type of search pattern, which are large diamond and small diamond. Large diamond has nine search points and small diamond has five search points. The figure below is shown the search pattern of the large diamond and small diamond.

Figure 2.4 Large Diamond Search Pattern

Figure 2.5 Small Diamond Search Pattern

Step for Diamond Search (DS) algorithm:

Step 1: The first step is use the LDSP to search the MBD point at origin of search window. If the MBD point is found at the center, proceed to step 3; otherwise, proceed to step 2.

Step 2: Second step is from MBD point from previous step as center point, form a new LDSP. If the new MBD point is found at the center position, proceed to step 3; otherwise, repeat this step.

Step 3: Step 3 is the final solution of motion vector. The SDSP is use in this final step and the MBD point obtained in this step is the points of the best matching block.

## 2.5.4 New Cross Diamond Search (NCDS) Algorithm

New Cross Diamond (NCDS) algorithm [7] in the first step is same with the Cross Diamond Search (CDS) algorithm. Cross-shape pattern and diamond-shaped pattern is the pattern used in NCDS. This search pattern is almost same with the Kite Cross Diamond Search (KCDS) algorithm. The small cross-shape pattern (SCSP) and the large Cross-shaped pattern (LCSP) is shown is Figure 2.6.

Figure 2.6: Small cross-shaped pattern and Large cross-shaped pattern

Step for the NCDS algorithm

Step 1: First the centered point is at the origin of search window. By using SCSP to search points, the MBD is found. If the MBD point is at center, then search stops (First Step Stop); otherwise proceed to step 2

Step 2: In the second step, with the previous MBD points, the SCSP is use to search the new MBD point. If the MBD point is found at the center of SCSP, it will search stop (Second Step Stop); otherwise proceed to step 3.

Step 3: With the previous MBD point, the LDSP is form. If the MBD point is at the center of LDSP, then proceed to the step 4; otherwise repeat this step.

Step 4: The SDSP is formed by using the MBD point in previous step as a center. The new MBD point is the final solution of motion vector.

## CHAPTER 3

## METHODOLOGY

## 3.1 METHODOLOGY

Project plan

The first discussion with the supervisor is to design the project flow for the PSM I. The explanation of the supervisor about the project is useful for understand the concept of the Motion Estimation. Supervisor plays an important role to help to enhance and develop the project.

Literature review

Literature review is important, because it is the part to gain the knowledge and deeply understand the project needed. Literature reviews are secondary sources, which are finding the theoretical and methodological to support the concept of the project. The source of information could be the text book, journal, internet, magazine or the opinion of the supervisor. The technique used for the Kite Cross Diamond Search (KCDS) algorithm is studies and understood.

By refer to the source, the first task to complete is to upload and play the video by using the MATLAB software.

After uploading the video and play it, the video frame is being extracted from the video sequence and displayed by using MATLAB. The frame has to be represented in number in order to implement the algorithm. The frame can divided into square block with the pixel dimension.

Implementation of the Kite Cross Diamond Search (KCDS) Algorithm

The three step search algorithm is studies to learn more about the block matching algorithm. It has advantages to learn the basic Block Matching Algorithm before to start implement the Kite Cross Diamond Search algorithm.

The Kite Cross Diamond Search (KCDS) algorithm is being implemented on block to determine the motion vectors. The predicted frames are reconstruction by using the motion vectors obtained from the previous stage.

Performance Analysis

The result of Kite Cross Diamond Search (KCDS) algorithm is compared to others algorithm and determined the most suitable algorithm to be used in motion estimation in terms of PSNR, number of search points required and computational complexity.

Thesis Writing and Presentation.

## 3.2 THEORY

Kite Cross Diamond Search (KCDS) algorithm is the one of the fast block matching algorithms, the flow chart for step of KCDS is shown in Figure 3.1.

START

1st step of SCSP

5 search points

At center of SCSP

3rd step of LDSP 9 search points

At center of KSP

4th step of SDSP 5 search points

At center of LDSP

2nd step of KSP 5 search points

END

## YES

## YES

## YES

## NO

## NO

## NO

SCSP-Small Cross Shape Pattern

KSP- Kite Search Pattern

LSDP-Large Diamond Shaped Pattern

SDSP-Small Diamond Shaped Pattern

START

1st step of SCSP

5 search points

At center of SCSP

3rd step of LDSP 9 search points

At center of KSP

4th step of SDSP 5 search points

At center of LDSP

2nd step of KSP 5 search points

END

## YES

## YES

## YES

## NO

## NO

## NO

SCSP-Small Cross Shape Pattern

KSP- Kite Search Pattern

LSDP-Large Diamond Shaped Pattern

SDSP-Small Diamond Shaped PatternFigure 3.1: Flow chart for KCDS algorithm

The kite-cross-diamond search (KCDS) algorithm adopts a novel asymmetric kite-shaped search patterns in the search step to keep similar distortion or even better in low-motion sequence while the speed of the motion estimation for stationary or quasi-stationary blocks is further boosted. KCDS is particularly faster and more accurate in some kinds of sequences. This algorithm is especially suitable for videoconferencing applications.

The search-point configurations used in the KCDS are divided in 3 different shapes: cross-shaped pattern, diamond-shaped pattern and kite-shaped pattern. The details and the analysis of the algorithm are given below:

Step 1 (Starting - Small Cross-Shape Pattern SCSP): A minimum BDM is found from the 5 search points of the SCSP (Small Cross-Shaped Pattern) [Figure 6] located at the center of search window. If the minimum BDM point occurs at the center of the SCSP (0,0), the search stops (First Step Stop); otherwise, go to Step 2.

Step 2 (KSP): With the vertex (minimum BDM point) in the first SCSP as the center, a particular KSP is formed based on the motion direction in previous step. For example, if the minimum BDM is located in upper vertex in first step, the new KSP will be an up-kite shape described as Figure 7 (a). Thus, there are 4 cases of newly formed KSP in this step: up-kite, down-kite, right-kite and left-kite, depends on the MV motion in step 1. If the minimum BDM point occurs at the center of this KSP, the search stops (Second Step Stop); otherwise go to Step 3.

Step 3 (Diamond Searching): A new Large-Diamond-Shaped Pattern LDSP is formed by repositioning the minimum BDM found in previous step as the center of the LDSP. If the new minimum BDM point is at the center of the newly formed LDSP, then go to Step 4 for converging the final solution; otherwise, this step is repeated.

Step 4 (Ending - Converging step): With the minimum BDM point in the previous step as the center, a SDSP (Small Diamond-

Shaped Pattern) is formed. Identify the new minimum BDM point from the SDSP, which is the final solution for the motion vector.

Figure 2.6: Search pattern KCDS

Figure 2.7: Kite Search Patterns: (a) up kite (b) left kite (c) down kite (d) right kite

## 3.2.1 Advantages

The processing time is improved

Average search points is reduced.

The complexity of motion estimation is reduced.

## 3.2.2 Disadvantages

Required more complex coding.

The PSNR is low compare to other algorithms.

## 3.3 Video Characteristics

Table 3.1: Type of video file

Video

Format

Size

Frames

Akiyo

AVI

144 x 176

100

Salesman

AVI

144 x 176

100

Foreman

AVI

144 x 176

100

Coastguard

AVI

144 x 176

100

News

AVI

144 x 176

100

Tennis

AVI

144 x 176

100

Table 3.2: Characteristics of video file

Test Sequence

Characteristic

Akiyo

Slow

Salesman

Moderate

Foreman

Fast

Coastguard

Moderate

News

Slow

Tennis

Fast

## CHAPTER 4

## RESULTS

## 4.1 Kite Cross Diamond Search (KCDS) Algorithm

The implementation KCDS algorithm is done in MATLAB. The performance analysis of KCDS is represented in terns on average PSNR, elapsed time and average points. The analysis for simulation of KCDS is done in four steps. First stage, six video is used to simulate the KCDS coded algorithm and the original and predicted images for every video. The Table 4.1 is shown the average PSNR, average search points and elapsed time for all the video. In the second stage, the comparison between the KCDS and others algorithm in the single frame is shown in Table 4.2 for elapsed time, Table 4.3 for average search points and Table 4.4 for average PSNR. For the third stage, fifty frames are used to compare the KCDS and others algorithm. The Table 4.5 is shown elapsed time, Table 4.6 for average search points and Table 4.7 for average PSNR for the third stage. In last stage, hundred frames are use to compare the KCDS and others algorithm. The Table 4.8 is shown elapsed time, Table 4.9 for average search points and Table 4.10 for average PSNR for the last stage.

## 4.2 First stage result

## 4.2.1 Akiyo video

Figure 4.1: The original and predicted images for KCDS algorithm

Figure 4.2: Average PSNR for KCDS algorithm

Figure 4.3: Average Points for KCDS algorithm

The elapsed time for akiyo video is 13.919995 seconds. The average PSNR and points are 43.4684 dB and 5.0241. (Show in MATLAB command window).

## 4.2.2 Salesman video

Figure 4.4: The original and predicted images for KCDS algorithm

Figure 4.5: Average PSNR for KCDS algorithm

Figure 4.6: Average Points for KCDS algorithm

The elapsed time for salesman video is 13.875325 seconds. The average PSNR and points are 38.7062 dB and 5.0649. (Show in MATLAB command window).

## 4.2.3 Foreman video

Figure 4.7: The original and predicted images for KCDS algorithm

Figure 4.8: Average PSNR for KCDS algorithm

Figure 4.9: Average Points for KCDS algorithm

The elapsed time for foreman video is 14.428464 seconds. The average PSNR and points are 30.3400 dB and 5.2886. (Show in MATLAB command window).

## 4.2.4 Coastguard video

Figure 4.10: The original and predicted images for KCDS algorithm

Figure 4.11: Average PSNR for KCDS algorithm

Figure 4.12: Average Points for KCDS algorithm

The elapsed time for coastguard video is 13.302843 seconds. The average PSNR and points are 29.0268 dB and 5.0657. (Show in MATLAB command window).

## 4.2.5 News video

Figure 4.13: The original and predicted images for KCDS algorithm

Figure 4.14: Average PSNR for KCDS algorithm

Figure 4.15: Average Points for KCDS algorithm

The elapsed time for news video is 13.800696 seconds. The average PSNR and points are 36.4008 dB and 5.0305. (Show in MATLAB command window).

## 4.2.6 Tennis video

Figure 4.16: The original and predicted images for KCDS algorithm

Figure 4.17: Average PSNR for KCDS algorithm

Figure 4.18: Average Points for KCDS algorithm

The elapsed time for tennis video is 14.714112 seconds. The average PSNR and points are 24.2945 dB and 5.4193. (Show in MATLAB command window).

Table 4.1: Elapsed time, average points and average PSNR for KCDS in all video

Algorithm

KCDS

Elapsed Time (s)

Average Search Points

Average PSNR (dB)

Akiyo

13.9200

5.0241

43.4685

Salesman

13.8753

5.0649

38.7062

Foreman

14.4285

5.2886

30.3400

Coastguard

13.3028

5.0657

29.0268

News

13.8007

5.0305

36.4088

Tennis

14.7141

5.4193

24.2945

Form the Table 1, the performance of KCDS algorithm is in term of elapsed time, average search points and average PSNR. The table 4.1 is show all the six video is simulated. The average PSNR of tennis video is the lowest compare to others video, 24.2945dB. This is because tennis video is classified as fast video. Besides that, akiyo video is the lowest average search points compare to others video, which is 5.0241. Akiyo video is the slow video, so the average search point is should be low and average PSNR is highest in all six video. The elapsed time of six video is almost same.

## 4.1.2 Single Frame comparison

Table 4.2: Elapsed time in single frame for TSS, HEXBS, DS, NCDS and KCDS algorithm

Elapsed Time (s)

Algorithms

TSS

HEXBS

DS

NCDS

## KCDS

Akiyo

0.1525

0.1357

0.1538

0.1409

## 0.1321

Salesman

0.1545

0.1356

0.1494

0.1423

## 0.1317

Foreman

0.1545

0.1422

0.1507

0.1420

## 0.1344

Coastguard

0.1522

0.1352

0.1539

0.1429

## 0.1313

News

0.1510

0.1343

0.1498

0.1387

## 0.1344

Tennis

0.1496

0.1313

0.1469

0.1380

## 0.1293

Table 4.3: Average search point in single frame for TSS, HEXBS, DS, NCDS and KCDS algorithm

Average Search Point

Algorithms

TSS

HEXBS

DS

NCDS

## KCDS

Akiyo

25.00

11.00

22.00

5.00

## 5.00

Salesman

25.00

11.00

22.00

5.00

## 5.00

Foreman

23.22

16.81

21.49

6.11

## 6.11

Coastguard

25.00

11.00

22.00

5.00

## 5.00

News

24.75

11.19

22.13

5.32

## 5.08

Tennis

24.24

11.10

21.87

5.79

## 5.00

Table 4.4: Average PSNR in single frame for TSS, HEXBS, DS, NCDS and KCDS algorithm

Average PSNR (dB)

Algorithms

TSS

HEXBS

DS

NCDS

## KCDS

Akiyo

50.6771

50.6771

50.6771

50.6771

## 50.6771

Salesman

42.3975

42.3975

42.3975

42.3975

## 42.3975

Foreman

22.4957

24.1265

23.3986

23.7703

## 23.7912

Coastguard

33.5785

33.5785

33.5785

33.5785

## 33.5785

News

33.1884

33.2420

33.2213

33.2128

## 33.1443

Tennis

29.8790

29.8029

30.0009

29.0326

## 28.4420

From the Table 4.2, the KCDS algorithm is the shorter elapsed time compare to other algorithms. In video of tennis, elapsed time for KCDS and HEXBS algorithms are 0.1293 second and 0.1313 second. The difference of the elapsed time is 0.002 second, which is reducing 1.52% in term of HEXBS. From the Table 4.3, KCDS and NCDS algorithms has a same average search point in video of akiyo, salesman, foreman and coastguard. If compared to DS algorithm, KCDS algorithm can reduce about 77.27% in term of DS algorithm. Form Table 4.4, the KCDS algorithm has a same PSNR in video of coastguard.

Figure 4.19: The original and predicted images for TSS algorithm

Figure 4.20: The original and predicted images for HEXBS algorithm

Figure 4.21: The original and predicted images for DS algorithm

Figure 4.22: The original and predicted images for NCDS algorithm

Figure 4.23: The original and predicted images for KCDS algorithm

By compared the TSS, HEXBS, DS, NCDS and KCDS algorithm, KCDS algorithm is the faster elapsed time in all the video. In the tennis video, the PSNR for all the algorithm is very low compare to others video. So the images for the all the algorithm have different between the original and predicted images.

## 4.1.3 Fifty Frames comparison

Table 4.5: Elapsed time in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm

Elapsed Time (s)

Algorithms

TSS

HEXBS

DS

NCDS

## KCDS

Akiyo

7.2752

6.6062

7.1949

6.5036

## 6.5928

Salesman

7.5783

7.1536

7.6250

7.1580

## 6.5881

Foreman

7.5159

7.0748

7.4723

6.9303

## 6.6027

Coastguard

7.8505

7.2015

7.4302

7.0219

## 6.6943

News

7.6204

6.9334

7.5163

6.8929

## 6.8621

Tennis

7.9771

7.0145

7.4207

6.9547

## 7.0282

Table 4.6: Average search point in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm

Average Search Points

Algorithms

TSS

HEXBS

DS

NCDS

## KCDS

Akiyo

25.00

11.00

21.99

5.05

## 5.00

Salesman

25.00

11.02

21.97

5.14

## 5.08

Foreman

24.35

12.08

21.40

5.75

## 5.29

Coastguard

22.00

11.01

22.00

5.00

## 5.00

News

24.98

11.02

22.03

5.06

## 5.04

Tennis

24.08

12.77

20.96

6.51

## 5.38

Table 4.7: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm

Average PSNR (dB)

Algorithms

TSS

HEXBS

DS

NCDS

## KCDS

Akiyo

43.6918

43.6899

43.6899

43.6918

## 43.6918

Salesman

38.1159

38.0362

37.9927

38.0867

## 38.0713

Foreman

28.7771

29.9984

29.1147

30.0583

## 30.0406

Coastguard

31.6368

30.9899

30.0158

30.9507

## 30.9507

News

37.8084

37.7964

37.7334

37.7698

## 37.7779

Tennis

27.2075

27.7033

27.5703

27.2262

## 26.8529

Figure 4.24: The original and predicted images for TSS algorithm in tennis video

Figure 4.25: The original and predicted images for HEXBS algorithm in tennis video

Figure 4.26: The original and predicted images for DS algorithm in tennis video

Figure 4.27: The original and predicted images for NCDS algorithm in tennis video

Figure 4.28: The original and predicted images for KCDS algorithm in tennis video

Figure 4.29: Average points in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in akiyo video

Figure 4.30: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in akiyo video

Figure 4.31: Average points in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in salesman video

Figure 4.32: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in salesman video

Figure 4.33: Average points in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in foreman video

Figure 4.34: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in foreman video

Figure 4.35: Average points in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in coastguard video

Figure 4.36: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in coastguard video

Figure 4.37: Average points in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in news video

Figure 4.38: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in news video

Figure 4.39: Average points in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in tennis video

Figure 4.40: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in tennis video

## 4.1.4 Hundred Frames comparison

Table 4.8: Elapsed time in hundred frames for TSS, HEXBS, DS, NCDS and KCDS algorithm

Elapsed Time (s)

Algorithms

TSS

HEXBS

DS

NCDS

## KCDS

Akiyo

16.8645

12.9304

14.3037

13.1305

## 13.1996

Salesman

13.7634

12.7513

13.7438

12.6382

## 12.3514

Foreman

13.7031

13.4831

14.2761

13.3885

## 12.2330

Coastguard

14.7688

13.1995

14.3779

13.3219

## 12.7545

News

13.9776

12.5948

13.7646

13.1339

## 12.2830

Tennis

13.9536

13.3667

13.7533

12.9774

## 12.8658

Table 4.9: Average search point in hundred frames for TSS, HEXBS, DS, NCDS and KCDS algorithm

Average Search Points

Algorithms

TSS

HEXBS

DS

NCDS

## KCDS

Akiyo

25.00

11.00

21.98

5.08

## 5.02

Salesman

24.98

11.04

21.98

5.12

## 5.06

Foreman

23.92

12.14

20.88

6.26

## 5.29

Coastguard

24.15

11.44

21.90

5.47

## 5.07

News

24.93

11.15

22.00

5.08

## 5.03

Tennis

24.06

12.85

20.56

6.84

## 5.42

Table 4.10: Average PSNR in hundred frames for TSS, HEXBS, DS, NCDS and KCDS algorithm

Average PSNR (dB)

Algorithms

TSS

HEXBS

DS

NCDS

## KCDS

Akiyo

43.46840

43.46740

43.46740

43.46840

## 43.46840

Salesman

38.75310

38.72390

38.63910

38.74270

## 38.70620

Foreman

29.02780

30.38160

29.68090

30.42930

## 30.34000

Coastguard

29.73440

29.28170

28.44890

29.13360

## 29.02680

News

36.43520

36.46260

36.30800

36.41990

## 36.40080

Tennis

24.51390

24.82480

24.29000

24.54170

## 24.29450

Figure 4.31: Average points in hundred frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in akiyo video

Figure 4.30: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in akiyo video

Figure 4.31: Average points in hundred frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in salesman video

Figure 4.30: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in salesman video

Figure 4.31: Average points in hundred frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in foreman video

Figure 4.30: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in foreman video

Figure 4.31: Average points in hundred frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in coastguard video

Figure 4.30: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in coastguard video

Figure 4.31: Average points in hundred frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in news video

Figure 4.30: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in news video

Figure 4.31: Average points in hundred frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in tennis video

Figure 4.30: Average PSNR in fifty frames for TSS, HEXBS, DS, NCDS and KCDS algorithm in tennis video

From the Table 4.8, the TSS algorithm has longer time compare to other algorithms, KCDS algorithm has shorter elapsed time in all the six video, which is reducing about 0.8~21% in term of the slower algorithms. Besides that, from Table 4.9, KCDS algorithm also has a lowest average search points in all the six video. NCDS algorithm has same step with the KCDS algorithm, but different search pattern, so average search points of NCDS algorithm is quite same with the KCDS algorithms. Form the Table 4.10, there are almost the same average PNSR value in all six video. KCDS algorithm maybe has less average PSNR compare to other algorithms, but is only about 1~10% in certain video.

## CHAPTER 5

## DISCUSSION

From the result above, the elapsed time and average search points of KCDS algorithm is the shorter compare to other algorithms. This is because KCDS algorithm has a critical search point which is kite pattern. This pattern can reduce the search point and the time. But in tern of PSNR, KCDS algorithm is lowest in the tennis video. These phenomena happen maybe because of the fast video. By refer to the image original and all algorithms predicted images, the predicted images of all algorithms will be different, this is cause by the process of block matching process or compression. From the PSNR table, the quality of image can be observed by according to the principle of peak-signal-noise-ratio. As a conclusion of the result analysis, the KCDS algorithm has a better performance in terms of elapsed time and average search point compare to other algorithms.

## SUMMARY AND CONCLUSION

By observing the result in chapter 4, the KCDS algorithm has an improvement of speed and average search points compare to other algorithms. It show that the KCDS algorithm has a better performance compare to TSS, HEXBS, DS and NCDS algorithms in terms of speed and average search points. The simulation results showed that KCDS is the fastest algorithm and it also providing the similar average PSNR and predicted accuracy to other algorithms, so KCDS algorithm is suitable for the all fast and slow video.