An information processing apparatus that calculates information on a position and an orientation of an image capture device relative to an object captured by the image capture device, holds three-dimensional information including a plurality of line segments that constitute the object, acquires an image of the object captured by the image capture device, detects an image feature indicating a line segment from the acquired image, calculates a position and orientation of the image capture device based on correspondence between the image feature indicating the detected line segment and the held line segment, and determines, for each of the held line segments, whether to use the line segment for the calculation of the position and orientation thereafter, based on at least one of a result of detection of the image feature, and information acquired in the calculation of the position and orientation.