In order to shorten the time required for a setting operation of features, an information processing apparatus includes an acquisition unit configured to acquire features used for deriving a positional attitude of an imaging device from an image captured by the imaging device, a setting unit configured to set a plurality of partial regions included in the image as a plurality of candidate regions to which a feature is to be added, an evaluation unit configured to evaluate the plurality of set candidate regions, a determination unit configured to determine a position and/or an orientation of a feature to be newly added based on the plurality of evaluated candidate regions, and an output unit configured to output the determined position and/or the orientation.