Discrete Homotopy Based On Digital Image Analysis

Digital image analysis is the theoretical basis of digital image processing.There are mainly two fundamental approaches to the digital image analysis:graph-based and topology-based approaches.They have their own’s advantages.Based on the digital image analysis,this paper,combining the topological method with the graph theory method,discusses discrete homotopies in the graph category and the hypergraph category.The main contents include the following two parts:In the first part,we introduce a weak graph map homotopy in the finite graph category and discuss its properties and applications to a mapping class group of a graph,1-order homotopy groups of a pointed simple graph and digital image analysis et al.Firstly,we introduce a notion of a weak graph map homotopy for graphs(we call it M-homotopy)in terms of maps.Based on this notion,we further define the M-strong deformation retracts of a simple graph and the M-homotopy equivalence between two simple graphs.Then it is proved that all M-strong deformation retracts of a simple graph could been found by removing trivial vertices one by one,and that the notion of Mhomotopy equivalence between graphs coincides with that of graph homotopy equivalence defined by Shing-Tung Yau et al.Although the two notions coincide with each other,by comparing processes of the transformations,we have found that the transformation up to the graph homotopy equivalence studied by Shing-Tung Yau et al is defined by means of combinatorial operations,and the transformation up to the M-homotopy equivalence could describe more accurately the process in terms of maps.Then we investigate some applications of M-homotopy to a mapping class group of a simple graph,1-order MPhomotopy groups of a pointed simple graph,digital image analysis,and so on.We also provide examples showing that the mapping class group of a graph based on M-homotopy is helpful to the study of symmetry of a graph.Moreover,it is proved that homology groups of a graph and the 1-order MP-homotopy group of a pointed simple graph are invariant up to M-homotopy equivalence.In the second part,we introduce several different types of discrete homotopy and Hom construction in the category of finite hypergraphs,and investigate relations among them and some related topological properties.On one hand,we define a notion of I-weak homotopy associated to the categorical product of hypergraphs,which is a generalization of the homotopy of hypergraph homomorphisms defined by Shing-Tung Yau et al.Then we discuss the relation between I-weak homotopy and the path connectivity ofⅠ-exponential hypergraph,which shows that they interact well with each other.Next,by Ⅰ-Hom construction associated to the categorical product of hypergraphs,we prove that if two hypergraph homomorphisms f and g are homotopic then they are path connected in the poset HomIC(H’,H),but the converse does not hold.Furthermore,it is proved that the homotopy of hypergraph homomorphisms defined by Shing-Tung Yau et al could be equivalently characterized by properties of Ⅱ-Hom construction associated to the categorical product of hypergraphs,and hence it provides a reasonable interpretation of the homotopy of hypergraph homomorphisms from the view of topology.On the other hand,in order to study the homotopy equivalence between the product operation of finite hypergraphs and exponential hypergraphs up to corresponding Hom-constructions,we define a notion of sq-homotopy associated to the square product of hypergraphs.From the view of product rules of hypergraphs,it is a generalization of the homotopy of hypergraph homomorphisms defined by Shing-Tung Yau et al.By properties of Ⅰ-Hom construction associated to the square product of hypergraphs,we prove that if two hypergraph homomorphisms f and g are sq-homotopic then they are path connected in the poset HomIs(H’,H),but the converse does not hold.Furthermore,it is proved the sq-homotopy could be equivalently characterized by properties of Ⅱ-Hom construction associated to the square product of hypergraphs,and that there is an inclusion of a strong deformation retract |HomIs(H■H’,H")|→|HomIs(H,H"ⅡH’)|,and hence it shows thatⅡ-exponential hypergraphs interact well with the square product of finite hypergraphs up to corresponding Hom-constructions.In addition,we define a notion of Ⅱ-weak homotopy associated to the square product of hypergraphs,which is a generalization of sq-homotopy.Then we discuss the correspondence between Ⅱ-weak homotopy and the path connectivity of Ⅱ-exponential hypergraph,and some applications to colorings of finite hypergraphs and the product of cubical complexes related to digital image analysis.Finally,it is pointed out that the investigation has applicability to not only digital image data analysis,but also to other general types of data analysis.