Speculative start point selection for motion estimation iterative search

• US 20100014588A1
• Filed: 07/16/2008
• Published: 01/21/2010
• Est. Priority Date: 07/16/2008
• Status: Active Grant

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Nakazato, Munehiro, Koo, Sung-Yul
• Granted Patent: US 8,094,714 B2
• Time in Patent Office: Days
• US Class Current: 375/240.160
• CPC Class Codes: H04N 19/527 Global motion vector estimation
• CPC Class Codes: H04N 19/533 Motion estimation using multistep search, e.g. 2D-log search or one-at-a-time search [OTS]
• CPC Class Codes: H04N 19/56 Motion estimation with initialisation of the vector search, e.g. estimating a good candidate to initiate a search
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

A speculative start point selection for motion estimation iterative search improves the efficiency and quality of the integer-pel motion estimation iterative search by speculatively selecting the start position of the iteration. The start position is selected by comparing the Sum of Absolute Differences (SAD) value of a 0 motion vector, a predicted motion vector and a global motion vector (GMV) and selecting the position with the smallest SAD value. A refinement scheme with a threshold improves the efficiency and quality of the motion estimation iterative search by performing several comparisons to ensure the proper motion vector is selected. Applications of this improved motion estimation search include stabilizing an image as well as many other applications where motion vectors are used.

Claims

1. A method of refining an iterative search result for motion estimation using a computing device, the method comprising:

a. determining a starting position comprising;

i. computing a distance value for each of a plurality of positions;

ii. comparing the distance value of each of the plurality of positions; and

iii. selecting a smallest starting distance position from the distance value of each of the plurality of positions;

b. iteratively searching for a smallest distance position starting from the starting position;

c. adding a motion vector cost to a smallest distance value of the smallest distance position to form a total cost;

d. comparing the total cost with a predictive motion vector distance value to determine a smaller value; and

e. selecting the smaller value of the total cost and the predictive motion vector distance value.

2. The method of claim 1 wherein the distance value is a Sum of Absolute Differences value.

3. The method of claim 1 wherein the plurality of positions includes a first position, a second position and a third position.

4. The method of claim 3 wherein the first position is a zero (0) motion vector, the second position is a predicted motion vector and the third position is a global motion vector.

5. The method of claim 1 wherein the motion vector cost is calculated based on a distance from a predicted motion vector.

6. The method of claim 1 wherein the smaller value is further refined and stabilizes an image.

7. The method of claim 1 wherein iteratively searching further comprises:

a. setting a count to a specified value;

b. computing a sub-region distance value of a sub-region;

c. selecting a smallest regional distance value in the sub-region;

d. comparing the smallest regional distance value with a previous smallest regional distance;

e. retaining a smaller regional distance value of the smallest regional distance value and the previous smallest regional distance value;

f. decrementing the count; and

g. repeating b-f until the count is zero.

8. The method of claim 1 wherein iteratively searching further comprises:

a. computing a sub-region distance value of a sub-region;

b. determining a minimum distance value of the sub-region;

c. comparing the minimum distance value with a threshold;

d. ending prematurely, if the minimum distance value is less than the threshold; and

e. repeating a-d until the count is zero, if the minimum distance value is greater than or equal to the threshold.

9. The method of claim 1 wherein the computing device is selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPod®

and a home entertainment system.

10. A system for refining an iterative search result for motion estimation, the system comprising:

a. a memory for storing an application, the application configured for;

i. determining a starting position comprising;

(1) computing a distance value for each of a plurality of positions;

(2) comparing the distance value of each of the plurality of positions; and

(3) selecting a smallest starting distance position from the distance value of each of the plurality of positions;

ii. iteratively searching for a smallest distance position starting from the starting position;

iii. adding a motion vector cost to a smallest distance value of the smallest distance position to form a total cost;

iv. comparing the total cost with a predictive motion vector distance value to determine a smaller value; and

v. selecting the smaller value of the total cost and the predictive motion vector distance value; and

b. a processor for processing the application.

11. The system of claim 10 wherein the distance value is a Sum of Absolute Differences value.

12. The system of claim 10 wherein the plurality of positions includes a first position, a second position and a third position.

13. The system of claim 12 wherein the first position is a zero (0) motion vector, the second position is a predicted motion vector and the third position is a global motion vector.

14. The system of claim 10 wherein the motion vector cost is calculated based on a distance from a predicted motion vector.

15. The system of claim 10 wherein iteratively searching further comprises:

a. setting a count to a specified value;

b. computing a sub-region distance value of a sub-region;

c. selecting a smallest regional distance value in the sub-region;

d. comparing the smallest regional distance value with a previous smallest regional distance value;

e. retaining a smaller regional distance value of the smallest regional distance value and the previous smallest regional distance value;

f. decrementing the count; and

g. repeating b-f until the count is zero.

16. The system of claim 10 wherein iteratively searching further comprises:

a. computing a sub-region distance value of a sub-region;

b. determining a minimum distance value of the sub-region;

c. comparing the minimum distance value with a threshold;

d. ending prematurely, if the minimum distance value is less than the threshold; and

e. repeating a-d until the count is zero, if the minimum distance value is greater than or equal to the threshold.

17. The system of claim 10 wherein the smaller value is further refined and used to stabilize an image.

18. The system of claim 10 wherein the processor and the memory are contained within a device selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPod®

and a home entertainment system.

19. An application for refining an iterative search result for motion estimation processed by a processor, the application comprising:

a. a starting position component for determining a smallest starting position for starting an iterative search;

b. an iterative search component for iteratively searching for a smallest distance position; and

c. a comparison component for comparing a total cost with a predicted motion vector distance value, wherein the total cost includes a smallest distance value of the smallest distance position and a motion vector cost.

20. The application of claim 19 wherein determining a smallest starting position includes:

a. computing a distance value for each of a plurality of positions;

b. comparing the distance value of each of the plurality of positions; and

c. selecting a smallest starting distance position from the distance value of each of the plurality of positions.

21. The application of claim 19 wherein the plurality of positions includes a first position, a second position and a third position.

22. The application of claim 21 wherein the first position is a zero (0) motion vector, the second position is a predicted motion vector and the third position is a global motion vector.

23. The application of claim 19 wherein iteratively searching further comprises:

a. setting a count to a specified value;

b. computing a sub-region distance value of a sub-region;

c. selecting a smallest regional distance value in the sub-region;

d. comparing the smallest regional distance value with a previous smallest regional distance value;

e. retaining a smaller regional distance value of the smallest regional distance value and the previous smallest regional distance value;

f. decrementing the count; and

g. repeating b-f until the count is zero.

24. The application of claim 19 wherein the motion vector cost is calculated based on a distance from a predicted motion vector.

25. The application of claim 19 wherein the best distance position is used to determine an appropriate motion vector which is used to stabilize an image.

26. The application of claim 19 wherein the application is contained within a device selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPod®

and a home entertainment system.

27. A method of refining an iterative search result for motion estimation using a computing device, the method comprising:

a. determining a starting position comprising;

i. computing a distance value for each of a plurality of positions;

ii. comparing the distance value of each of the plurality of positions; and

iii. selecting a smallest starting distance position from the distance value of each of the plurality of positions;

b. iteratively searching for a smallest distance position starting from the starting position;

c. adding a motion vector cost to a smallest distance value of the smallest distance position to form a total cost;

d. determining if a global motion vector is less than a threshold;

e. if the global motion vector is less than the threshold, additional steps are taken, including;

i. comparing the total cost with a predictive motion vector distance value to determine a smaller value; and

ii. selecting the smaller value of the total cost and the predictive motion vector distance value for refinement; and

f. if the global motion vector is greater than or equal to the threshold, the smallest distance value of the smallest distance position is selected for refinement.

28. The method of claim 27 wherein the distance value is a Sum of Absolute Differences value.

29. The method of claim 27 wherein the plurality of positions includes a first position, a second position and a third position.

30. The method of claim 29 wherein the first position is a zero (0) motion vector, the second position is a predicted motion vector and the third position is a global motion vector.

31. The method of claim 27 wherein the motion vector cost is calculated based on a distance from a predicted motion vector.

32. The method of claim 27 wherein the method stabilizes an image.

33. The method of claim 27 wherein iteratively searching further comprises:

a. setting a count to a specified value;

b. computing a sub-region distance value of a sub-region;

c. selecting a smallest regional distance value in the sub-region;

d. comparing the smallest regional distance value with a previous smallest regional distance value;

e. retaining a smaller regional distance value of the smallest regional distance value and the previous smallest regional distance value;

f. decrementing the count; and

g. repeating b-f until the count is zero.

34. The method of claim 27 wherein the computing device is selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPod®

and a home entertainment system.

35. A system for refining an iterative search result for motion estimation, the system comprising:

a. a memory for storing an application, the application configured for;

i. determining a starting position comprising;

(1) computing a distance value for each of a plurality of positions;

(2) comparing the distance value of each of the plurality of positions; and

(3) selecting a smallest starting distance position from the distance value of each of the plurality of positions;

ii. iteratively searching for a smallest distance position starting from the starting position;

iii. adding a motion vector cost to a smallest distance value of the smallest distance position to form a total cost;

iv. determining if a global motion vector is less than a threshold;

v. if the global motion vector is less than the threshold, additional steps are taken, including;

(1) comparing the total cost with a predictive motion vector distance value to determine a smaller value; and

(2) selecting the smaller value of the total cost and the predictive motion vector distance value for refinement; and

vi. if the global motion vector is greater than or equal to the threshold, the smallest distance value of the smallest distance position is selected for refinement; and

b. a processor for processing the application.

36. The system of claim 35 wherein the distance value is a Sum of Absolute Differences value.

37. The system of claim 35 wherein the plurality of positions includes a first position, a second position and a third position.

38. The system of claim 37 wherein the first position is a zero (0) motion vector, the second position is a predicted motion vector and the third position is a global motion vector.

39. The method of claim 35 wherein the motion vector cost is calculated based on a distance from a predicted motion vector.

40. The system of claim 35 wherein iteratively searching further comprises:

a. setting a count to a specified value;

b. computing a sub-region distance value of a sub-region;

c. selecting a smallest regional distance value in the sub-region;

d. comparing the smallest regional distance value with a previous smallest regional distance value;

e. retaining a smaller regional distance value of the smallest regional distance value and the previous smallest regional distance value;

f. decrementing the count; and

g. repeating b-f until the count is zero.

41. The system of claim 35 wherein the system stabilizes an image.

42. The system of claim 35 wherein the processor and the memory are contained within a device selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPod®

and a home entertainment system.

43. An application for refining an iterative search result for motion estimation processed by a processor, the application comprising:

a. a starting position component for determining a smallest starting position for starting an iterative search;

b. an iterative search component for iteratively searching for a smallest distance position;

c. a comparison component for comparing a total cost with a predicted motion vector distance value, wherein the total cost includes a smallest distance value of the smallest distance position and a motion vector cost; and

d. a threshold component for comparing a global motion vector with a threshold to determine whether to execute the comparison component or to use a result from the iterative search component.

44. The application of claim 43 wherein determining a smallest starting position includes:

a. computing a distance value for each of a plurality of positions;

b. comparing the distance value of each of the plurality of positions; and

c. selecting a smallest starting distance position from the distance value of each of the plurality of positions.

45. The application of claim 43 wherein the plurality of positions includes a first position, a second position and a third position.

46. The application of claim 45 wherein the first position is a zero (0) motion vector, the second position is a predicted motion vector and the third position is a global motion vector.

47. The application of claim 43 wherein iteratively searching further comprises:

a. setting a count to a specified value;

b. computing a sub-region distance value of a sub-region;

c. selecting a smallest regional distance value in the sub-region;

d. comparing the smallest regional distance value with a previous smallest regional distance value;

e. retaining a smaller regional distance value of the smallest regional distance value and the previous smallest regional distance value;

f. decrementing the count; and

g. repeating b-f until the count is zero.

48. The application of claim 43 wherein the motion vector cost is calculated based on a distance from a predicted motion vector.

49. The application of claim 43 wherein the application stabilizes an image.

50. The application of claim 43 wherein the application is contained within a device selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPod®

and a home entertainment system.

51. A method of selecting a starting position for a motion estimation iterative search using a computing device, the method comprising:

a. computing a distance value for each of a plurality of positions;

b. comparing the distance value of each of the plurality of positions; and

c. selecting a smallest starting distance position from the distance value of each of the plurality of positions.

52. The method of claim 51 wherein the distance value is a Sum of Absolute Differences value.

53. The method of claim 51 wherein the plurality of positions includes a first position, a second position and a third position.

54. The method of claim 53 wherein the first position is a zero (0) motion vector, the second position is a predicted motion vector and the third position is a global motion vector.

55. The method of claim 51 wherein the computing device is selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPod®

and a home entertainment system.

56. The method of claim 51 wherein the smallest starting distance position is used as the starting position for the motion estimation iterative search which stabilizes an image.

57. A method of estimating motion using a computing device, the method comprising:

a. determining a starting position comprising;

i. computing a distance value for each of a plurality of positions;

ii. comparing the distance value of each of the plurality of positions; and

iii. selecting a smallest starting distance position from the distance value of each of the plurality of positions; and

b. iteratively searching for a smallest distance position starting from the starting position.

58. The method of claim 57 wherein the distance value is a Sum of Absolute Differences value.

59. The method of claim 57 wherein iteratively searching further comprises:

a. setting a count to a specified value;

b. computing a sub-region distance value of a sub-region;

c. selecting a smallest regional distance value in the sub-region;

d. comparing the smallest regional distance value with a previous smallest regional distance value;

e. retaining a smaller regional distance value of the smallest regional distance value and the previous smallest regional distance value;

f. decrementing the count; and

g. repeating b-f until the count is zero.

60. The method of claim 57 wherein the plurality of positions includes a first position, a second position and a third position.

61. The method of claim 60 wherein the first position is a zero (0) motion vector, the second position is a predicted motion vector and the third position is a global motion vector.

62. The method of claim 57 wherein the computing device is selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPod®

and a home entertainment system.

63. The method of claim 57 wherein the smallest distance position is used to determine an appropriate motion vector which is used to stabilize an image.

64. A system for estimating motion, the system comprising:

a. a memory for storing an application, the application configured for;

i. determining a starting position comprising;

(1) computing a distance value for each of a plurality of positions;

(2) comparing the distance value of each of the plurality of positions; and

(3) selecting a smallest starting distance position from the distance value of each of the plurality of positions; and

ii. iteratively searching for a smallest distance position starting from the starting position; and

b. a processor for processing the application.

65. The system of claim 64 wherein the distance value is a Sum of Absolute Differences value.

66. The system of claim 64 wherein iteratively searching further comprises:

a. setting a count to a specified value;

b. computing a sub-region distance value of a sub-region;

c. selecting a smallest regional distance value in the sub-region;

d. comparing the smallest regional distance value with a previous smallest regional distance value;

e. retaining a smaller regional distance value of the smallest regional distance value and the previous smallest regional distance value;

f. decrementing the count; and

g. repeating b-f until the count is zero.

67. The system of claim 64 wherein the plurality of positions includes a first position, a second position and a third position.

68. The system of claim 67 wherein the first position is a zero (0) motion vector, the second position is a predicted motion vector and the third position is a global motion vector.

69. The system of claim 64 wherein the processor and the memory are contained within a device selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPod®

and a home entertainment system.

70. The system of claim 64 wherein the smallest distance position is used to determine an appropriate motion vector which is used to stabilize an image.

71. An application for estimating motion processed by a processor, the application comprising:

a. a starting position component for determining a best starting position for starting an iterative search; and

b. an iterative search component for iteratively searching for a smallest distance position.

72. The application of claim 71 wherein iteratively searching further comprises:

a. setting a count to a specified value;

b. computing a distance value of a sub-region;

c. selecting a smallest regional distance value in the sub-region;

d. comparing the smallest regional distance value with a previous smallest regional distance value;

e. retaining a smaller regional distance value of the smallest regional distance value and the previous smallest regional distance value;

f. decrementing the count; and

g. repeating b-f until the count is zero.

73. The application of claim 71 wherein determining the best starting position includes:

a. computing a distance value for each of a plurality of positions;

b. comparing the distance value of each of the plurality of positions; and

c. selecting a smallest starting distance position from the distance value of each of the plurality of positions.

74. The application of claim 73 wherein the plurality of positions includes a first position, a second position and a third position.

75. The application of claim 74 wherein the first position is a zero (0) motion vector, the second position is a predicted motion vector and the third position is a global motion vector.

76. The application of claim 71 wherein the application is contained within a device selected from the group consisting of a personal computer, a laptop computer, a computer workstation, a server, a mainframe computer, a handheld computer, a personal digital assistant, a cellular/mobile telephone, a smart appliance, a gaming console, a digital camera, a digital camcorder, a camera phone, an iPod®

and a home entertainment system.

77. The application of claim 71 wherein the smallest distance position is used to determine an appropriate motion vector which is used to stabilize an image.

78. A method of improving motion estimation using a computing device, the method comprising:

a. determining a starting position comprising;

i. computing a distance value for each of a plurality of positions;

ii. comparing the distance value of each of the plurality of positions; and

iii. selecting a smallest starting distance position from the distance value of each of the plurality of positions;

b. iteratively searching for a smallest distance position starting from the starting position; and

c. avoiding a local minimum comprising;

i. determining a previous position;

ii. determining a new position;

iii. comparing the previous position and new position; and

iv. based on the previous position and the new position comparison, selecting a new search center, wherein the new search center is based on the previous position if the new position is in an opposite direction from the previous position and the new search center is based on the new position if the new position is not in the opposite direction from the previous position.

79. A method of improving motion estimation using a computing device, the method comprising:

a. determining a starting position comprising;

i. computing a distance value for each of a plurality of positions;

ii. comparing the distance value of each of the plurality of positions; and

iii. selecting a smallest starting distance position from the distance value of each of the plurality of positions;

b. iteratively searching for a smallest distance position starting from the starting position; and

c. determining a center point of a next search area comprising;

i. determining a position of a search area with a smallest distance search value;

ii. determining an offset for a center point of a next search area based on the position with the smallest distance search value; and

iii. selecting the center point of the next search area based on the offset.

80. A method of improving motion estimation using a computing device, the method comprising:

a. determining a starting position comprising;

i. computing a distance value for each of a plurality of positions;

ii. comparing the distance value of each of the plurality of positions; and

iii. selecting a smallest starting distance position from the distance value of each of the plurality of positions;

b. iteratively searching for a smallest distance position starting from the starting position;

c. determining a center point of a next search area comprising;

i. determining a position of a search area with a smallest distance search value;

ii. determining an offset for a center point of a next search area based on the position with the smallest distance search value; and

iii. selecting the center point of the next search area based on the offset; and

d. avoiding a local minimum comprising;

i. determining a previous position;

ii. determining a new position;

iii. comparing the previous position and new position; and

iv. based on the previous position and the new position comparison, selecting a new search center, wherein the new search center is based on the previous position if the new position is in an opposite direction from the previous position and the new search center is based on the new position if the new position is not in the opposite direction from the previous position.

81. A method of improving motion estimation using a computing device, the method comprising:

a. determining a starting position comprising;

i. computing a distance value for each of a plurality of positions;

ii. comparing the distance value of each of the plurality of positions; and

iii. selecting a smallest starting distance position from the distance value of each of the plurality of positions;

b. iteratively searching for a smallest distance position starting from the starting position;

c. adding a motion vector cost to the smallest distance value of the smallest distance position to form a total cost;

d. determining if a global motion vector is less than a threshold;

e. if the global motion vector is less than the threshold, additional steps are taken, including;

i. comparing the total cost with a predictive motion vector distance value to determine a smaller value; and

ii. selecting the smaller value of the total cost and the predictive motion vector distance value for refinement;

f. if the global motion vector is greater than or equal to the threshold, the smallest distance value of the smallest distance position is selected for refinement; and

g. determining a center point of a next search area comprising;

i. determining a position of a search area with a smallest distance search value;

ii. determining an offset for a center point of a next search area based on the position with the smallest distance search value; and

iii. selecting the center point of the next search area based on the offset.

82. A method of improving motion estimation using a computing device, the method comprising:

a. determining a starting position comprising;

i. computing a distance value for each of a plurality of positions;

ii. comparing the distance value of each of the plurality of positions; and

iii. selecting a smallest starting distance position from the distance value of each of the plurality of positions;

b. iteratively searching for a smallest distance position starting from the starting position;

c. adding a motion vector cost to the smallest distance value of the smallest distance position to form a total cost;

d. determining if a global motion vector is less than a threshold;

e. if the global motion vector is less than the threshold, additional steps are taken, including;

i. comparing the total cost with a predictive motion vector distance value to determine a smaller value; and

ii. selecting the smaller value of the total cost and the predictive motion vector distance value for refinement;

f. if the global motion vector is greater than or equal to the threshold, the smallest distance value of the smallest distance position is selected for refinement; and

g. avoiding a local minimum comprising;

i. determining a previous position;

ii. determining a new position;

iii. comparing the previous position and new position; and

iv. based on the previous position and the new position comparison, selecting a new search center, wherein the new search center is based on the previous position if the new position is in an opposite direction from the previous position and the new search center is based on the new position if the new position is not in the opposite direction from the previous position.

83. A method of improving motion estimation using a computing device, the method comprising:

a. determining a starting position comprising;

i. computing a distance value for each of a plurality of positions;

ii. comparing the distance value of each of the plurality of positions; and

iii. selecting a smallest starting distance position from the distance value of each of the plurality of positions;

b. iteratively searching for a smallest distance position starting from the starting position;

c. adding a motion vector cost to the smallest distance value of the smallest distance position to form a total cost;

d. determining if a global motion vector is less than a threshold;

e. if the global motion vector is less than the threshold, additional steps are taken, including;

i. comparing the total cost with a predictive motion vector distance value to determine a smaller value; and

ii. selecting the smaller value of the total cost and the predictive motion vector distance value for refinement; and

f. if the global motion vector is greater than or equal to the threshold, the smallest distance value of the smallest distance position is selected for refinement; and

g. determining a center point of a next search area comprising;

i. determining a position of a search area with the smallest distance search value;

ii. determining an offset for a center point of a next search area based on the position with the smallest distance search value; and

iii. selecting the center point of the next search area based on the offset; and

h. avoiding a local minimum comprising;

i. determining a previous position;

ii. determining a new position;

iii. comparing the previous position and new position; and

iv. based on the previous position and the new position comparison, selecting a new search center, wherein the new search center is based on the previous position if the new position is in an opposite direction from the previous position and the new search center is based on the new position if the new position is not in the opposite direction from the previous position.

84. A method of improving motion estimation using a computing device, the method comprising:

a. determining a starting position comprising;

i. computing a distance value for each of a plurality of positions;

ii. comparing the distance value of each of the plurality of positions; and

iii. selecting a smallest starting distance position from the distance value of each of the plurality of positions;

b. iteratively searching for a smallest distance position starting from the starting position;

c. adding a motion vector cost to the smallest distance value of the smallest distance position to form a total cost;

d. determining if a global motion vector is less than a threshold;

e. if the global motion vector is less than the threshold, additional steps are taken, including;

i. comparing the total cost with a predictive motion vector distance value to determine a smaller value; and

ii. selecting the smaller value of the total cost and the predictive motion vector distance value for refinement;

f. if the global motion vector is greater than or equal to the threshold, the smallest distance value of the smallest distance position is selected for refinement; and

g. determining a center point of a next search area comprising;

i. determining a position of a search area with the smallest distance search value;

ii. determining an offset for a center point of a next search area based on the position with the smallest distance search value; and

iii. selecting the center point of the next search area based on the offset;

h. avoiding a local minimum comprising;

i. determining a previous position;

ii. determining a new position;

iii. comparing the previous position and new position; and

iv. based on the previous position and the new position comparison, selecting a new search center, wherein the new search center is based on the previous position if the new position is in an opposite direction from the previous position and the new search center is based on the new position if the new position is not in the opposite direction from the previous position; and

i. terminating iteratively searching early comprising;

i. computing a sub-region distance value of a sub-region;

ii. determining a minimum distance value of the sub-region;

iii. comparing the minimum distance value with a threshold;

iv. ending prematurely, if the minimum distance value is less than the threshold; and

v. repeating i-iv until the count is zero, if the minimum distance value is greater than or equal to the threshold.