Constructing a convex hull for the pixel colors of an image by viewing them as 3D points can extract a set of palette colors for the image, then image recoloring can be achieved by modifying the palette colors. For better recoloring effect, the convex hull should contain more pixels (inclusive) and be more compact. Otherwise, reconstruction error would occur or the extracted palette color would be less representative, yielding wrong recoloring results or less effective edit. We observe that convex hulls constructed by prior methods can contain all the image pixels, but are far from compact. Efforts have been made to optimize the vertices of convex hull to increase the compactness but are still not perfect. In this paper, we propose a novel coarse to fine convex hull construction scheme with auxiliary vertices. We start by constructing a coarse convex hull whose vertices are directly image pixels which is thus the most compact but cannot contain all pixels. We then make a remedy by adding auxiliary vertices into the coarse convex hull to obtain a fine convex hull. More auxiliary vertices are added, more image pixels will be contained into the fine convex hull. The auxiliary vertices are image pixels too so that the compactness can still be maintained. During editing, the auxiliary vertices are not allowed to be edited for edit convenience, but deformed as-rigid-as-possible with the adjusting of other vertices. Our convex hull is both inclusive and compact. Extensive experiments validate the effectiveness of the proposed method.