In some embodiments, iterative schemes allowing for the creation of complexity scalable frame-rate up-conversion (FRUC), on the basis of bilateral block-matching searches, may be provided. Such approaches may improve the accuracy of calculated motion vectors at each iteration. Iterative searches with variable block sizes may be employed. It may begin with larger block sizes, to find global motion within a frame, and then proceed to using smaller block sizes for local motion regions.