Motion Estimation (ME) plays an important role in modern video coders since it consumes approximately 60%-80% of the entire encoder's computations. FSBB-ME is the main ME algorithm that is adopted by most coding standards. Although it provides the best coding efficiency amongst various ME algorithms, its computational complexity is very high. This work proposes several alternatives to reduce this bottleneck in video coding either in the pixel domain or in the frequency domain.