An image processing apparatus inputs a first and a second captured videos; extracts attribute values of image regions of background objects commonly included in the first and the second captured videos respectively; extracts attribute values of image regions of objects respectively included in the first and the second captured videos; derives a relative index of an attribute value of the image region of the object with reference to the attribute value of the image region of the background object with respect to the object included in each of the first and the second captured videos; and detects the same object included in the first and the second captured videos based on the index derived with respect to the object included in each of the first and the second captured videos.