This invention is directed to provide a technique for efficiently, optimally deciding the shape and number of meshes when performing mesh coding for an object having a gradation. This invention is also directed to provide a technique for setting representative points to minimize the mesh distortion. A mesh generation unit divides an object area into a plurality of meshes and obtains position information, gradient information, and color information for each vertex of a mesh. A mesh control unit decides unnecessary vertices based on the difference between color information of each vertex and color information in the object area that corresponds to the vertex. An optimization unit obtains position information, gradient information, and color information of necessary vertices to minimize the difference between color information of each necessary vertex other than the unnecessary vertices and color information at a position in the object area that corresponds to the necessary vertex.