## 4 3D Partial Parallel Thinning Algorithm  
The parallel thinning algorithm is based on several pre-defined removing templates (class A, B, C, and D) [21; 22]. The target voxel will be removed if the voxel is a non-tail voxel and the neighborhoods of the voxel match one of the templates. Figure 3 shows the templates of each class. There are six templates in class A, 12 templates in class B, 8 templates in class C, and 36 templates in class D. A solid black circle denotes a binary value 1, which means that a voxel exists. A white circle (background voxel) denotes a binary value 0, which  
Figure 2: Adjacencies in a 3D binary array. means that there is no voxel. The voxels in the unmarked positions are 'don't care' voxels, which means that the binary values can be either 1 or 0. The white squares mean that at least one of them is 1. The two white triangles in Figure 3d mean that both cannot be 1 simultaneously, which means that, at most, one of them is 1 or both of them are 0. If a voxel \(p\) is 26-adjacent to only one voxel, then it is called a line-end voxel. If the \(p\) is 26-adjacent to only two voxels, then it is called a near-line-end voxel. If the \(p\) is either a line-end or a near-line-end voxel, then it is called a tail voxel; otherwise, it is called a non-tail voxel. Analyze each voxel of a 3D model to determine whether it is a non-tail voxel and satisfies at least one of the removing templates of any class. After analyzing and marking the whole voxels, the voxels that satisfy both conditions will be removed simultaneously. Repeat the process until no voxel can be removed. The authors in [21] found that the 12 conventional templates of class D in [22] may disconnect the skeleton. Therefore, they modified and expanded each template of class D to three templates. Each of the templates from d1 to d6 in Figure 3d is expanded to three templates according to the binary values of the two triangles. There are thus 36 templates in class D. In [21], 18 templates were used to illustrate the templates from d1 to d6. However, in this paper, they are simplified to six templates by using the two triangles. Figure 3: _Cont._  
However, the fully parallel thinning algorithm has a drawback of thinning the voxels of pyramid structure. It removes each layer of voxels from the surface to the inside in each iteration and finally removes all voxels of pyramid structure. Figure 4 shows an example of the problem. Figure 4a shows a portion of a manta ray model's wing. Figure 4b shows a result after eight iterations of thinning procedures. After the ninth iteration, the whole voxels of the part are removed. The surface voxels of each layer are non-tail voxels and satisfy the removing templates. Therefore, the skeleton of the manta ray model's wing cannot be extracted by the fully parallel thinning algorithm. Figure 3: 62 pre-defined removing templates of classes A, B, C, and D. (**a**) 6 removing templates in class A; (**b**) 12 removing templates in class B; (**c**) 8 removing templates in class C; (**d**) 36 removing templates in class D.  
In [23], the templates are modified so that they are without any extended neighbors, which means that only the 26-adjacent voxels of the target voxel are considered for investigation. One of the two additional criteria is to determine whether any voxel in the 26-neighbors of the target voxel are 26-connected. If so, the target voxel is a candidate for removal. The other criterion is to determine whether any background voxel in the 18-neighbors of the target voxel is connected and contains at least one background 6-neighbor. If so, then the target voxel is considered for removal. However, this algorithm has the drawback of thinning the voxels with a structure as shown in Figure 5.  
Figure 5 shows a lower part of the voxels of a model with the shape of the digit nine. The voxels satisfy the modified removing templates in class A and the two criteria. All voxels were therefore removed. If the templates are kept as in Figure 3, then the skeleton of this model can be extracted.