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.
