This invention provides a method and computer-readable medium for detecting flesh-tone regions in pictures, images, and videos. First, a flesh-tone axis is defined in a color space coordinate system, the flesh-tone axis passing through both the center of a flesh-tone region and the origin of the color space coordinate system. A perpendicular point, is then calculated on the flesh-tone axis as being the point having the shortest distance to an input pixel. A first distance and a second distance are then calculated based on the coordinates of the input pixel, the perpendicular point and the center of the flesh-tone region. The determination as to whether the input pixel is in the flesh-tone region can be made based on the first distance and second distance.