A Two-Dimensional (2D) image segmentation apparatus for segmenting pixels of a progressive input 2D image includes a group information storing unit storing information of pixel groups including a plurality of adjacent pixels; a pixel determining unit determining coordinates of an input pixel, and determining whether the input pixel is an effective pixel for segmentation; a group scanning unit scanning a adjacent pixel group disposed in a scan range preset from the effective pixel in the group storing unit when the input pixel is determined as the effective pixel by the pixel determining unit; and a group information updating unit updating information of a pixel group stored in the group information storing unit according to whether there is the scanned adjacent pixel group and a pixel group including an input pixel preceding the effective pixel. Moreover, a method is provided that removes red-eye using area information of a pixel group determined by the segmentation apparatus.