1. An image processing apparatus comprising: a storage unit configured to store data used to classify line segments of a virtual object corresponding to a physical object into a plurality of groups for which levels are set and to define each of the line segments, where line segments that configure a shape of the virtual object are stored in a group set with a lowest group level; an image sensing unit configured to sense an image of the physical object; a selection unit configured to select one group from the plurality of groups one by one, in turn, from the group set with the lowest group level until a group set with a highest group level without any duplication; a projection unit configured to project line segments which belong to the group selected by said selection unit onto a physical space using the data used to define that line segments, and the image of the physical object; and an updating unit configured to update position and orientation information indicating a position and orientation of said image sensing unit based on the line segments projected onto the physical space and a feature in the image of the physical object.