Methods and apparatus for generating variable-width border masks for objects in input images. Given an input image and an initial binary selection of an object in the image, a variable-width border mask method may be applied to automatically generate an accurate, variable-width border mask for the object. An initial border mask may be generated. An initial foreground probability map may be generated within the initial border mask using a Gaussian Mixture color modeling technique. A geodesic smoothing technique may be applied to the initial foreground probability map to reduce or remove noise. An optimization technique may be applied to optimize the foreground boundary, and a final variable-width border mask may be generated. The variable-width border mask may be used as input to image matting algorithms to generate an accurate alpha mask of the foreground object selected from the input image.