We present two new techniques for reducing blocking artifacts in motion compensated frames. These techniques can be applied generally to motion compensated frames obtained by employing any partitioning schemes. In the first technique, the weighting coefficients of the overlapped block motion compensation are modeled with fuzzy relations. These fuzzy relations are formed based on two fuzzy sets, which define the closeness of a given pixel to the block boundaries in the horizontal and vertical directions, respectively. The second technique uses the similarity between a set of pixels inside a partitioned region and that on the borders to modify the border pixels. Simulations conducted on several benchmark video sequences indicate that the proposed techniques can improve the subjective quality of the frames as well as reduce the prediction error.