of huge amounts of 3D data ▶ Even with cheap hardware and software, one can easily generate 3D data: ▶ 3D data acquisition with common smartphone (e.g., Photogrammetry) O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 4 / 33
Data, new application fields have appeared ▶ Digital Forensics, Cultural Heritage, Body Scanning ▶ The scanned data will often need to be consolidated (to fix scan problems or remove unwanted elements) → Inpainting O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 5 / 33
e, O. L´ ezoray, A smarter exemplar-based inpainting algorithm using local and global heuristics for more geometric coherence, International Conference on Image Processing (ICIP - IEEE), pp. 4622-4626, 2014.. O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 6 / 33
and Object Removal by Exemplar-Based Image Inpainting” C: Confidence term (reliable information for each patch) D: Data term (local structure estimation) O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 7 / 33
and Object Removal by Exemplar-Based Image Inpainting” C: Confidence term (reliable information for each patch) D: Data term (local structure estimation) O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 7 / 33
and Object Removal by Exemplar-Based Image Inpainting” C: Confidence term (reliable information for each patch) D: Data term (local structure estimation) O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 7 / 33
and Object Removal by Exemplar-Based Image Inpainting” C: Confidence term (reliable information for each patch) D: Data term (local structure estimation) How can we do this on 3D colored meshes ? → 3D mesh patches, priority ? O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 7 / 33
represented by a graph G = (V,E) with V = {v1,...,vm} and E ⊂ V×V ▶ vi ∼ vj is used to denote two adjacent vertices ▶ N (vi) = {vj,vj ∼ vi} gives the set of all the adjacent vertices to vi within a 1-hop (vertices that can be reached in one walk). ▶ Lim et al. have proposed local spiral hop descriptors: the surrounding vertices of one vertex can be enumerated by following a spiral Graph signal F : V → Rd. 1. S : V → R3 for coordinates 2. N : V → R3 for normals 3. C : V → R3 for colors O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 10 / 33
an ordered set of vertices whose shortest path to vi is exactly k-hops long ⇒ R0(vi) = {vi} and R1(vi) = N (vi) ▶ k-disk(vi) = l=0,...,k Rl(vi) is the set of vertices that can be reached from vi in 0 to k walks. vi R1 7 R1 1 R1 2 R1 3 R1 4 R1 5 R1 6 R2 1 R2 2 R2 3 R2 4 R2 5 R2 6 R2 7 R2 8 R2 9 R2 10 R2 11 R2 12 R2 13 1-disk(vi) O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 11 / 33
an ordered set of vertices whose shortest path to vi is exactly k-hops long ⇒ R0(vi) = {vi} and R1(vi) = N (vi) ▶ k-disk(vi) = l=0,...,k Rl(vi) is the set of vertices that can be reached from vi in 0 to k walks. ▶ R(k+1)(vi) = N (R(k)(vi))\k-disk(vi) is the set of vertices that can be reached in 1 walk from Rk(vi) without going through its k-disk (that contains vertices that can be reached from vi in 0 to k walks) vi R1 7 R1 1 R1 2 R1 3 R1 4 R1 5 R1 6 R2 1 R2 2 R2 3 R2 4 R2 5 R2 6 R2 7 R2 8 R2 9 R2 10 R2 11 R2 12 R2 13 2-ring(vi) O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 11 / 33
operator Sp(vi,k) is an ordered sequence from the concatenation of the ordered rings Sp(vi,k) = (vi,1-ring(vi),...,k-ring(vi)) = R0 1 (vi),R1 1 (vi),R1 2 (vi),...,Rk |Rk| (vi) ▶ It has 2 degrees of freedom: the direction (clockwise or counterclockwise) of the rings and the first chosen vertex R1 1 (vi) ▶ We fix : ▶ the orientation clockwise ▶ the initial vertex R1 1 (vi) is the one in the direction of the shortest geodesic path to vi: R1 1 (vi) = arg min vj∈N (vi) dG(vi,vj) O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 12 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
operator Sp(vi,k) varies for the vertices ▶ Lim et al. either truncate or zero-pad each spiral depending on its size to compare two local spiral hop descriptors ▶ We propose a more accurate hierarchical comparison d(Sp(vi,k),Sp(vj,k)) = k ∑ l=0 d(Rl(vi),Rl(vj)) Two k-rings are compared by mapping the vertices of the largest ring to the smallest one: d(Rl(vi),Rl(vj)) = |Rl (vi)| ∑ n=0 d(Rl n (vi),Rl n′ (vj)) with n′ = n·|Rl (vj)| |Rl (vi)| and |Rl(vi)| > |Rl(vj)| First vertex descriptor Second vertex descriptor 0-hop 1-hop 2-hop The distance between two vertices is then the distance between their graph signal vectors: d(Rl n (vi),Rl m (vj)) = ∥F(Rl n (vi))−F(Rl m (vj))∥2 O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 13 / 33
associated graph G = (V,E), the area to be inpainted is denoted as Ω ⊂ V and its boundary is ∂Ω ⊂ Ω. We mark the vertices to be inpainted by the following function: Marked(vi) = 1 if vi ∈ Ω 0 if vi / ∈ Ω For vertices vi in Ω, their color is considered as unknown and set to C(vi) = (0,0,0)T . The objective of the inpainting is to recover the color of these vertices by pasting the color of vertices from surrounding spiral patches. O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 16 / 33
and associated graph G = (V,E), inpainting area Ω ⊂ V Set the size k of spiral patches and γ the ring search size Compute Spiral patches Sp(vi,k) of size k, ∀vi ∈ V Mark vertices to be inpainted : Marked(vi) = 1, ∀vi ∈ Ω while ∂Ω ̸= / 0 do 1) Compute Priority(vi), ∀vi ∈ ∂Ω 2) Find the spiral patch Sp(vtarget,k) with the maximum priority i.e., vtarget = arg max vi∈∂Ω Priority(vi) 3) Find the fully-defined exemplar Sp(vbest,k) (with vbest ∈ V\Ω) that minimizes d(Sp(vtarget,k),Sp(vbest,k)) with Confidence(vbest) = 1 in γ-ring(vtarget) 4) Copy colors from the spiral patch Sp(vbest,k) to Sp(vtarget,k), ∀vi ∈ Sp(vtarget,k) with Marked(vi) = 1 6) Update Marked(vi) and ∂Ω for all inpainted vertices end while O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 17 / 33
patches that: ▶ have few missing information (Confidence term), ▶ have a small spatial range (Density term), ▶ are located at strong geometric features (Variance term), ▶ are located at strong color structures (Continuity term). Our priority is defined as Priority(vi) = Confidence(vi)·Density(vi)·Variance(vi)·Continuity(vi) O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 18 / 33
used for images. Its objective is to fill first the spiral patches that have most of their vertices’ colors already known. The confidence is defined as Confidence(vi) = ∑ vj∈ k-disk(vi) (1−Marked(vj)) |k-disk(vi)| This measures the proportion of known vertices’ colors within the spiral patch Sp(vi,k). It is close to 1 if most of the vertices’ colors of the spiral patch are known, and close to 0 for spiral patches that contain few known vertices’ colors O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 19 / 33
patches to be filled first. Indeed, in meshes, the spatial coverage of a patch can be very different from one part of the mesh to another. It is preferable to inpaint first small spiral patches. The density is defined as Density(vi) = |k-ring(vi)| ∑ vj∈ k-ring(vi) ∥S(vi)−S(vj)∥2 This measures the average spatial dispersion of the vertices of the spiral patch Sp(vi,k) with respect to its center vi. It is high if the spiral patch is small and low otherwise O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 20 / 33
of spiral patches that exhibit strong geometrical variations. We measure the latter by the total variance of the vertices’ normals of a spiral patch Sp(vi,k). If its value is high this means that there are variations in the surface of the spiral patch. The variance term is defined as Variance(vi) = 3 ∑ j=1 σ2 j (N(vi,k)) where N(vi,k) is the set of vertices’ normals for vertices in Sp(vi,k). O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 21 / 33
term used for images. Its aim is to encourage the inpainting of spiral patches where a strong variation in color is present. It is based on the Structure Tensor J(vi) = ∇T f(vi)·∇f(vi) Total Variation . ∇f(vi) = [d(Sp(vi,k),Sp(vj,k)),vj ∈ k-ring(vi)]T In the spiral comparison, the graph signal is the vertices’ color vectors: F(vi) = C(vi) We have J(vi) = UΛUT with U its eigenvectors and Λ its eigenvalues. Continuity(vi) = |k-ring(vi)| ∑ j=1 λ2 j with λj = Λ(j, j). If its value is high this means that there are color variations in the surface of the spiral patch O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 22 / 33
Density Mesh colors C inpaint Ω (e) Variance (f) Continuity (g) Priority (h) Target and best matching patches O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 23 / 33
inpainting approach ▶ Defines spiral patch as examplar to be pasted ▶ Defines how to compare spiral patches ▶ Defines a priority term from Confidence, Density, Variance and Continuity terms. ▶ Provides good visual results (quantitative results in the paper) Future works ▶ Limitations due to similar patch search: define a more efficient patch search strategy (adapt patchMatch for meshes) O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 32 / 33
funded by the Normandy Region Council and the European Union (COSURIA project). O. L´ ezoray & S. Bougleux Spiral patch exemplar-based inpainting of 3D colored meshes 33 / 33
lezoray
koukyo1994
skoyamalab
jimboken
gpeyre
tajima_kaho
fufufukakaka
tomohirokoana
terasawat
.png){kind=avatar}
satai
atsukomasano2026
gamella
mfonobong
sergeychernyshev
mkilby
jonoalderson
reverentgeek
dugsong
uxyall
lindahogenes
sonatard
mayatellez
axbom
