Computational reduction in motion estimation based on lower bound of cost function
A method for motion estimation comprising the steps of (A) determining whether a cost of encoding one or more prediction parameters for a current search position is less than a current best cost, (B) when the cost of encoding the one or more prediction parameters for the current search position is less than the current best cost, updating the current best cost if the current best cost is greater than or equal to a sum of the cost for encoding the one or more prediction parameters for the current search position and a distortion measurement for the current search position and (C) ending the search when the current best cost is less than or equal to the cost of encoding the one or more prediction parameters for the current search position and less than a minimum cost for encoding one or more prediction parameters for one or more remaining search positions.
1. A method for motion estimation comprising the steps of:
(A) determining whether a cost of encoding one or more prediction parameters for a current search position is less than a current best cost;
(B) when said cost of encoding said one or more prediction parameters for said current search position is less than said current best cost, updating said current best cost if said current best cost is greater than or equal to a sum of said cost for encoding said one or more prediction parameters for said current search position and a distortion measurement for said current search position; and
(C) ending said search when said current best cost is less than or equal to said cost of encoding said one or more prediction parameters for said current search position and less than a minimum cost for encoding one or more prediction parameters for one or more remaining search positions.
2. The method according to claim 1 , wherein said one or more prediction parameters comprise a motion vector.
3. The method according to claim 1 , further comprising the steps of:
determining a measurement of distortion between a current block and a reference block at said current search position; and
determining whether a sum of (i) said cost of encoding said one or more prediction parameters for said current search position and (ii) said measurement of distortion between said current block and said reference block at said current search position is less than said current best cost.
4. The method according to claim 1 , wherein said distortion measurement is determined using a sum of absolute differences between a current block and a reference block at said current search position.
5. The method according to claim 4 , wherein updating said current best cost comprises:
setting said current best cost equal to the sum of (i) said cost of encoding said one or more prediction parameters for said current search position and (ii) said distortion measurement between said current block and said reference block at said current search position.
6. The method according to claim 1 , wherein said minimum cost for encoding said one or more prediction parameters of said one or more remaining search positions is determinable based on said cost of encoding said one or more prediction parameters for said current search position.
7. The method according to claim 6 , wherein said minimum cost for encoding said one or more prediction parameters of said one or more remaining search positions is substantially equal to one-half the cost of encoding said one or more prediction parameters for said current search position.
8. The method according to claim 1 , further comprising the step of:
ordering said search positions such that the cost of encoding prediction parameters for each subsequent search position increases substantially monotonically.
9. The method according to claim 8 , wherein:
said search positions are ordered along a spiral search path.
10. An apparatus comprising:
means for determining whether a cost of encoding one or more prediction parameters for a current search position in a reference picture is less than a current best cost;
means for updating said current best cost if said current best cost is (i) greater than or equal to said cost of encoding one or more prediction parameters for a current search position and (ii) greater than or equal to a sum of said cost for encoding said one or more prediction parameters for said current search position and a distortion measurement for said current search position; and
means for ending said search when said current best cost is (i) less than or equal to said cost of encoding said one or more prediction parameters for said current search position and (ii) less than a minimum cost for encoding one or more prediction parameters for one or more remaining search positions.
11. An apparatus comprising:
a first circuit configured to compare a first block of a current picture with each of a number of second blocks located at a number of search positions in a reference picture; and
a second circuit configured to determine whether a cost of encoding one or more prediction parameters for a current search position in said reference picture is less than a current best cost, wherein a motion estimation search is ended when said current best cost is (i) less than or equal to said cost of encoding said one or more prediction parameters for said current search position in said reference picture and (ii) less than a minimum cost for encoding one or more prediction parameters for one or more remaining search positions.
12. The apparatus according to claim 11 , wherein said one or more prediction parameters comprise a motion vector.
13. The apparatus according to claim 11 , wherein:
said first circuit is further configured to determine a measurement of distortion between said first block and a respective one of the second blocks at said current search position; and
said second circuit is further configured to update said current best cost if said current best cost is greater than or equal to a sum of (i) said cost of encoding said one or more prediction parameters for said current search position and (ii) said measurement of distortion between said first block and the respective second block at said current search position.
14. The apparatus according to claim 13 , wherein said measurement of distortion between said first block and the respective second block comprises a sum of absolute differences.
15. The apparatus according to claim 13 , wherein:
said second circuit is further configured to update said current best cost by setting said current best cost equal to said sum of (i) said cost of encoding said one or more prediction parameters for said current search position and (ii) said measurement of distortion between said first block and the respective second block at said current search position.
16. The apparatus according to claim 11 , wherein said second circuit is further configured to determined said minimum cost for encoding said one or more prediction parameters of said one or more remaining search positions based upon said cost of encoding said one or more prediction parameters for said current search position.
17. The apparatus according to claim 11 , wherein said minimum cost for encoding said one or more prediction parameters of said one or more remaining search positions is set equal to one-half the cost of encoding said one or more prediction parameters for said current search position.
18. The apparatus according to claim 11 , wherein:
said first circuit is further configured to order said search positions such that the cost of encoding one or more prediction parameters for each search position increases substantially monotonically.
19. The apparatus according to claim 18 , wherein:
said search positions are ordered along a spiral search path.
20. The apparatus according to claim 11 , wherein said apparatus is part of an encoder that is compliant with the H.264/MPEG4-AVC compression standard.