A region-of-interest extraction device is provided with an extraction unit configured to extract one or a plurality of local regions from an input image; a retrieval unit configured to search an image database storing a plurality of images and retrieve an image matching a local region for each of the local regions extracted by the extraction unit; and a relevance score determination unit configured to determine a relevance score for each of the local regions on the basis of the retrieval result from the retrieval unit.