Method for encoding a digital image in order to compress same
The disclosure relates to a method of encoding a digital image in order to compress same, the digital image being defined as a point cloud associating a set of N pixels, designated as vertices, to a scalar intensity value. The method aims at establishing triangulation vertices of the digital image and implements the principles of algorithmic topology.
1. A method for encoding a digital image formed by a set of N pixels (p ij ) for compression thereof, the digital image being defined as a cloud of N points (i, j, f ij ), designated as vertices (v k ), associating the set of N pixels (p ij ) with a scalar intensity value (f ij ), the method comprising the following steps:
a) ordering N vertices (v k ) in increasing order of scalar intensity values (f ij ) in a vertex table, wherein the ordering step comprises applying a discrimination rule so as to order, in the vertex table, two vertices having the same scalar intensity value;
b) initializing an iteration index i and a class index c to 0, initializing a starting simplicial complex (K 0 ) to an empty set and repeating the sequence of the following operations until the iteration index i reaches N:
incrementing the iteration index i;
extracting the vertex of rank i (v i ) from the vertex table and checking whether the vertex of rank i (v i ) is in the neighborhood of a vertex comprised in the simplicial complex of rank i−1 (K i−1 ); and
if no vertex of the simplicial complex of rank i (K i ) is in the neighborhood of the vertex of rank i (v i ), incrementing the rank of class c, forming the simplicial complex of rank i (K i ) by adding a new class (C c ) composed of the vertex of rank i (v i ) to the simplicial complex of rank i−1 (K i−1 ), and assigning rank c to the new class (C c );
if at least one vertex of a single class of the simplicial complex of rank i (K i ) is in the neighborhood of the vertex of rank i (v i ), forming the simplicial complex of rank i (K i ) by adding the vertex of rank i (v i ) to the simplicial complex of rank i−1 (K i−1 ) in this one class;
if several vertices of a plurality of classes of the simplicial complex of rank i (K i ) are in the neighborhood of the vertex of rank i (v i ), forming the simplicial complex of rank i (K i ) by grouping together, in the simplicial complex of rank i−1 (K i−1 ), the vertices forming this plurality of classes and the vertex of rank i (v i ) in the class of lowest rank and forming a persistence pair comprising:
i. the first vertex (v ic ) corresponding to the lowest rank vertex in the lowest rank class of the plurality of classes of the simplicial complex of rank i (K i ), this rank being called the appearance rank of the persistence pair (ic); and
ii. the second vertex (v id ) corresponding to the vertex of rank of index i (v i ), this rank i being called the disappearance rank of the persistence pair (id); and
in a decimation step, calculating, for each persistence pair (v ic , v id ) identified, a lifetime associated with the persistence pair (v ic , v id ) calculated as a difference between the disappearance rank of the persistence pair (id) and the appearance rank of the persistence pair (ic), and retaining, in a restricted list, some of the persistence pairs (v ic , v id ) exhibiting the longest lifetimes;
the encoded digital image comprising at least some pixels (p ij ) corresponding to the vertices constituting the persistence pairs (v ic , v id ) of the restricted list.
2. A non-transitory computer-readable medium storing instructions thereon that, when executed by at least one processor, cause the at least one processor to perform the encoding method according to claim 1 .
3. An encoding device, comprising:
at least one processor; and
a non-transitory computer-readable medium storing instructions thereon that, when executed by the at least one processor, cause the at least one processor to perform the encoding method according to claim 1 .
4. The method of claim 1 , wherein the following steps are also carried out: an iteration index i to N+1 and a class index c are initialized to 0, a starting simplicial complex (K N ) is initialized to the empty set and the sequence of the following operations is repeated until the iteration index i reaches 1:
decrementing the iteration index i;
extracting the vertex of rank i (v i ) from the vertex table and checking whether the vertex of rank i (v i ) is in the neighborhood of a vertex comprised in the simplicial complex of rank i+1 (K i+1 ); and
if no vertex of the simplicial complex of rank i+1 (K i+1 )is in the neighborhood of the vertex of rank i (v i ), incrementing the rank of class c, forming the simplicial complex of rank i (K i ) by adding a new class (C c ) composed of the vertex of rank i (v i ) to the simplicial complex of rank i+1 (K i+1 ), and assigning rank c to the new class (C c );
if at least one vertex of a single class of the simplicial complex of rank i+1 (K i+1 ) is in the neighborhood of the vertex of rank i (v i ), forming the simplicial complex of rank i (K i ) by adding the vertex of rank i (v i ) to the simplicial complex of rank i+1 (K i+1 ) in this one class; and
if several vertices of a plurality of classes of the simplicial complex of rank i+1 (K i+1 ) are in the neighborhood of the vertex of rank i (v i ), forming the simplicial complex of rank i (K i ) by grouping together, in the simplicial complex of rank i+1 (K i+1 ), the vertices forming this plurality of classes and the vertex of rank i (v i ) in the class of lowest rank.
5. The method of claim 1 , wherein a first vertex v 1 , corresponding to a point with indices i 1 , j 1 of the digital image, is in the neighborhood of a second vertex v 2 , corresponding to a point with indices i 2 , j 2 of the digital image, if i 1 =i 2 +1, and/or if j 1 =j 2 +1.
6. The method of claim 5 , further comprising determining a plurality of triangles from triangulation vertices.
7. The method of claim 1 , wherein the scalar intensity value (f ij ) of the digital image results from the combination of a plurality of color intensities of a raw color image.
8. The method of claim 7 , further comprising determining a plurality of triangles from triangulation vertices.
9. The method of claim 1 , wherein the following steps are also carried out: an iteration index i to N+1 and a class index c are initialized to 0, a starting simplicial complex (K N ) is initialized to the empty set and the sequence of the following operations is repeated until the iteration index i reaches 1:
decrementing the iteration index i;
extracting the vertex of rank i (v i ) from the vertex table and checking whether the vertex of rank i (v i ) is in the neighborhood of a vertex comprised in the simplicial complex of rank i+1 (K i+1 ); and
if no vertex of the simplicial complex of rank i+1 (K i+1 ) is in the neighborhood of the vertex of rank i (v i ), incrementing the rank of class c, forming the simplicial complex of rank i (K i ) by adding a new class (C c ) composed of the vertex of rank i (v i ) to the simplicial complex of rank i+1 (K i+1 ), and assigning rank c to the new class (C c );
if at least one vertex of a single class of the simplicial complex of rank i+1 is in the neighborhood of the vertex of rank i (v i ), forming the simplicial complex of rank i (K i ) by adding the vertex of rank i (v i ) to the simplicial complex of rank i+1 (K i+1 ) in this one class; and
if several vertices of a plurality of classes of the simplicial complex of rank i+1 (K i+1 ) are in the neighborhood of the vertex of rank i (v i ), forming the simplicial complex of rank i (K i ) by grouping together, in the simplicial complex of rank i+1 (K i+1 ), the vertices forming this plurality of classes and the vertex of rank i (v i ) in the class of lowest rank.
10. The method of claim 9 , wherein a first vertex v 1 , corresponding to a point with indices i 1 , j 1 of the digital image, is in the neighborhood of a second vertex v 2 , corresponding to a point with indices i 2 , j 2 of the digital image, if i 1 =i 2 +1, and/or if j 1 =j 2 +1.
11. The method of claim 10 , wherein the scalar intensity value (f ij ) of the digital image results from the combination of a plurality of color intensities of a raw color image.
12. The method of claim 11 , further comprising determining a plurality of triangles from triangulation vertices.