1. An image processing apparatus for segmenting a multilevel image into a plurality of regions with different attributes, comprising: an input processor for inputting a multilevel image; a binary image generation processor for generating a binary image by binarizing the multilevel image; a region segmentation processor for segmenting the binary image into a plurality of regions with different attributes to obtain a first region segmentation result, the plurality of regions including a character region classified as a character attribute and a halftone region classified as a halftone attribute; an edge image generation processor for generating a binary edge image by obtaining an edge strength of each pixel based on the multilevel image and binarizing each pixel based on the obtained edge strength, the binary edge image including first and second pixel values, the first pixel value representing an edge component, and the second pixel value representing a non-edge component; an outline extraction processor for extracting a pixel block having the first pixel value from the binary edge image, determining whether the pixel block forms a rectangular outline of which each length of four sides is equal to or larger than a threshold value, and (1) if the pixel block forms the rectangular outline, storing the pixel block as an outline candidate of a halftone region, and (2) if the pixel block does not form the rectangular outline, not storing the pixel block as an outline candidate; a composition processor for obtaining a second region segmentation result by correcting the halftone region of the first region segmentation result obtained by the region segmentation processor with the outline candidate stored by the outline extraction processor when the halftone region of the first region segmentation result overlaps with the outline candidate stored by the outline extraction processor; and an output processor for outputting the second region segmentation result obtained by the composition processor.