Abstract: Palette-based image recoloring has recently drawn much attention, which is widely used in poster making, fashion design, film, short video editing, etc. The state-of-the-art method extracts the image palette by calculating the convex hull. However, there are two main problems in this technique: one is that the color distribution inside the convex hull is always ignored, resulting in less representative palettes; the other is that the interpolation weights lack sparsity, which makes it difficult to achieve targeted local editing. This paper proposes a novel palette extraction algorithm to address these problems. Firstly, calculate the convex hull of the image in the RGB space and simplify it. Secondly, extract the color distribution inside the convex hull to build the representative color palette. Finally, perform tetrahedral subdivision of palette colors in RGB space and interpolation of image pixels. More than 40 images are obtained from the Internet to evaluate the proposed algorithm’s effectiveness, comparative analysis and user study on interpolation sparsity and recoloring effects are also presented. Experiments show that the palette extracted by the proposed algorithm is more representative, the interpolation weights are sparser and achieve more accurate local recoloring than state-of-the-art methods.