1. An image processing apparatus for performing graph-based region segmentation processing, comprising: a generation unit configured to generate an edge graph in which a pixel of an image is set as a node and an edge is set between nodes; a classification unit configured to classify the edge into one of a plurality of classes based on a feature amount of the edge, wherein a dissimilarity or similarity between nodes at two ends of the edge is as the feature amount; a determination unit configured to select an edge of interest in ascending class order of the feature amount, and determine whether to merge determination target regions to which the nodes at the two ends of the edge of interest belong; and a merging unit configured to merge determination target regions determined to be able to be merged, and update a feature amount in the merged region, wherein at least one of the generation unit, the classification unit, the determination unit, and the merging unit is implemented using a processor.