1. A movement distance estimating device comprising: a memory; and a processor coupled to the memory and configured to: determine, based on a first image and a second image included in a plurality of images among images captured by an image capture device mounted on a moving body, an amount of relative movement of the moving body between a first time point at which the first image is captured and a second time point at which the second image is captured, determine a plurality of scales for the amount of relative movement using the plurality of images, each of the plurality of scales being determined based on a relation in a three-dimensional space between a road surface and a spatial point corresponding to a feature point in an area other than a road-surface area in each of the plurality of images, select a smallest scale among the plurality of scales, and determine a movement distance of the moving body between the first time point and the second time point, based on the amount of relative movement and the smallest scale.