An optical navigation apparatus, an optical navigation method, and a non-transitory computer readable medium thereof are provided. The optical navigation apparatus includes a light source unit, an image sensing unit, and a processing unit. The processing unit is electrically connected to the light source unit and the image sensing unit. The light source unit provides a beam of light. The image sensing unit captures a first image at a first time instant when the light is projected onto a reflection surface. The processing unit calculates an image quality index of the first image and determines a matching block size between the first image and a second image according to the image quality index.