1. An image processing apparatus for segmenting a multilevel image into a plurality of regions with different attributes, comprising: input means for inputting a multilevel image; binary image generation-means for generating a binary image by binarizing the multilevel image; edge image generation means for generating an edge image by extracting an edge component in the multilevel image; region segmentation means for segmenting the binary image into a plurality of regions with different attributes; outline extraction means for extracting an outline candidate of a halftone region from the edge image; and output means for outputting a second region segmentation result on the basis of information of the outline candidate obtained by said outline extraction means and region segmentation result information obtained by said region segmentation means.