This talk is inspired by the notion of a P-simple set proposed by Bertrand [1] and the 3D parallel 6-subiteration surface-thinning algorithm reported by Gong and Bertrand [2].

A reduction transforms a binary picture only by changing some black points to white ones, which is referred to as deletion. Sequential reductions traverse the black points of a picture, and consider a single point for possible deletion, while parallel reductions can delete a set of black points simultaneously. Two reductions are called equivalent if they produce the same result for each input picture. A deletion rule is said to be equivalent if it provides a pair of equivalent parallel and sequential reductions.

The author introduced a special class of deletion rules: A deletion rule is said to be general-simple if it deletes only simple points, and the deletability of any point does not depend on the 'color' of any deletable point [3]. He showed that a deletion rule is equivalent, and provides topology-preserving reductions if it is general-simple [3].

We are to discuss the relationship between P-simple sets and general-simple deletion rules:

- Reductions with general-simple deletion rules delete P-simple sets [4].

- For each P-simple set Q in a picture, there is a general-simple deletion rule that deletes Q from this picture [4].

In addition, we are to report that the deletion rule of the parallel thinning algorithm proposed by Gong and Bertrand is general-simple [5]. Hence, it deletes P-simple sets, and it is equivalent to a sequential algorithm with the same deletion rule.

References

[1] G. Bertrand: On P-simple points. Compte Rendu de l'Académie des Sciences de Paris, Série Math. 321, pp 1077-1084, 1995.

[2] W.X. Gong, G. Bertrand: A simple parallel 3d thinning algorithm. In: Proc. 10th IEEE Int. Conf. Pattern Recognition, ICPR'90, 188-190, 1990.

[3] K. Palágyi: Equivalent sequential and parallel reductions in arbitrary binary pictures. Int. J. Pattern Recognition and Artificial Intelligence 28, 2014.

[4] K. Palágyi: How sufficient conditions are related for topology-preserving reductions. Acta Cybernetica 23, 939-958, 2018.

[5] K. Palágyi, G. Németh, P. Kardos: Equivalent sequential and parallel subiteration-based surface-thinning algorithms. In Proc. 17th International Workshop on Combinatorial Image Analysis, IWCIA 2015, LNCS 9448, Springer, 31-45, 2015.