A colored point cloud is encoded as at least two images. The point cloud is projected onto two maps, the second map comprising a set of blocks. An interest value is computed for each block of the second map as a function of the number of points of the point cloud projected onto the given block, not already projected on the first map. The first image is encoded in the stream as obtained by the projection while blocks of the second image are encoded according to their interest value. Blocks comprising no or a few new points over the first image and/or comprising a frontier are encoded in manner that minimize their bitrate as the information they carry is already stored in the first image.