text:
Strictifying and taming directed paths in Higher Dimensional Automata

Directed paths have been used by several authors to describe concurrent executions of a program. Spaces of directed paths in an appropriate state space contain executions with all possible legal schedulings. It is interesting to investigate whether one obtains different topological properties of such a space of executions if one restricts attention to schedulings with ``nice'' properties, eg involving synchronizations. This note shows that this is not the case, ie that one may operate with nice schedulings without inflicting any harm. Several of the results in this note had previously been obtained by Ziemianski. We attempt to make them accessible for a wider audience by giving an easier proof for these findings by an application of quite elementary results from algebraic topology; notably the nerve lemma.

1. Introduction 1.1. Schedules in Higher Dimensional Automata. Higher Dimensional Automata (HDA) were introduced by V. Pratt [13] back in 1991 as a model for concurrent computation. Mathematically, HDA can be described as (labelled) pre-cubical or -sets (cf Definition 2.1). Those are obtained by glueing individual cubes of various dimensions together; directed paths corresponding to a -set respect the natural partial order in each cube of the model. These directed paths correspond to lawful schedules/executions of a concurrent computation; and paths that are homotopic in a directed sense (d-homotopic, cf [3]), will always lead to the same result.
Compared to other well-studied concurrency models like labelled transition systems, event structures, Petri nets etc., it has been shown by R.J. van Glabbeek [7] that Higher Dimensional Automata have the highest expressivity; on the other hand, they are certainly less studied and less often applied so far.
It is not evident which paths one should admit as directed paths: It is obvious that they should progress along each axis in each facet of the HDA; the time flow is not reversible. This is reflected in the notion of a d-path on such a complex. One may ask, moreover, that processes synchronize after a step (either a full step or an idle step) has been taken. This is what tame d-paths have to satisfy, on top. A natural question to ask is whether one can perform the same computations (and obtain the same results) according to whether synchronization is requested all along or not.
It has been shown by K. Ziemiański [17,18] that the synchronization request has no essential significance: The spaces of directed paths and of tame d-paths between two states are always homotopy equivalent. This has two consequences: On the one hand, one may, without global effects, relax the computational model and allow quite general parallel compositions. On the other hand, in the analysis of the schedules on a HDA, one may restrict attention to tame d-paths, ie mandatory synchronization; these are combinatorially far easier to model and to analyze.
1.2. Posets, poset categories, and algebraic topology. Many (sets of) schedules can be formulated in the language of series-parallel pomsets (of events). Tame d-paths "live in" serial compositions of simple Higher Dimensional Automata consisting of a single cube each. General d-paths underpin more complicated schedules, for which parallel composition is involved in the description; cf eg [5] for a detailed description of finite step transition systems accepting pomset languages and [2] for newer developments.
In this paper, we are not interested in the analysis of individual paths/schedules, but in the analysis of the space of all schedules from a start state to an end state, equipped with a natural topology. It turns out that the way subspaces of schedules are glued together is essentially the same, whether synchronization is mandatory or not.
In that line of argument, posets enter the scene in a different manner: We divide the space of all executions (d-paths) into easy-to-analyze subspaces; for tame d-paths, for example, we simply fix a sequence of faces that they are kept in. Refinement is a partial order relation on these face sequences, and we will exploit the combinatorial/topological properties of the poset category of face sequences (called cube chains).
The use of methods from algebraic topology in the analysis of concurrency properties has been advocated in eg [4,9,3] to which we refer the reader for details. In this paper, we will (apart from the proof of Proposition 6.6) only apply one important result from algebraic topology, the so-called nerve lemma [1,10], cf Theorem 6.2. At a first glance, one may say that it allows to apply a divide and conquer strategy: Cut a space into subspaces that are topologically trivial (contractible); also all non-empty intersections of such are assumed contractible. Then all essential information (up to homotopy equivalence) is contained in the way these subspaces are glued together. That glueing can be described by way of a simplicial complex, the nerve of the associated poset category. If the posets associated to different spaces are (naturally) isomorphic, then their nerves and hence the spaces they describe are homotopy equivalent.

Definitions and results
2.1. Definitions. We start with some notation: The unit interval [0, 1] is denoted by I. For two topological spaces X and Y , we let Y X denote the space of all continuous maps from X to Y equipped with s compact open-topology. For Let p 0 : [t 0 , t 1 ] → X and p 1 : [t 1 , t 2 ] → X denote two paths with p 0 (t 1 ) = p 1 (t 1 ). Their concatenation at t 1 is denoted p 0 * t 1 p 1 : [t 0 , t 2 ] → X. (1) [8,9] A d-space consists of a topological space X together with a subspace P (X) ⊂ X I of paths in X that contains the constant paths, is closed under concatenation and under non-decreasing reparametrizations p : I → I. Elements of P (X) are called d-paths.
(2) For x, y ∈ X, we let P (X) y x = {p ∈ P (X)| p(0) = x, p(1) = y} denote the subspace of all d-paths from x to y.
] ⊂ R denote an interval (a < b) and let ϕ : J → I denote any increasing homeomorphism. Then P J (X) := {p • ϕ| p ∈ P (X)} -independent of the choice of ϕ.
In applications to concurrency, the d-spaces under consideration are usually directed -sets, or rather their geometric realizations [13,6,7,3]: (1) A -set X (also called a pre-cubical or semi-cubical set) is a sequence of disjoint sets X n , n ≥ 0; equipped, for n > 0, with face maps d α i : X n → X n−1 , α ∈ {0, 1}, 1 ≤ i ≤ n, satisfying the pre-cubical relations: Elements of X n are called n-cubes, those of X 0 are called vertices.
(2) A -set X is called proper [17] if for every pair x 0 , x 1 ∈ X 0 of vertices there exists at most one cube with bottom vertex x 0 and top vertex x 1 (cf also Section 4.1). (3) A -set is called non-self-linked [3] if every cube c ∈ X n has n k 2 n−k different iterated faces in X k (ie, iterated faces agree if and only they do so because of the pre-cubical relations). (4) The geometric realization of a pre-cubical set X is the space . , x n−1 ). It seems that typical Higher-Dimensional Automata as they occur in concurrency are proper and non-self-linked.
Speaking about a cube c in X (or rather in |X|; we will often suppress || from the notation), we mean actually the image of the quotient map {c} × I dim c ֒→ n≥0 X n × I n ↓ |X|. If X is non-self-linked, then this map is a homeomorphism onto its image in X; if not, then it may identify points on the boundary of I dim c .
What are the directed paths in the geometric realization of a -set?
(1) A path p : J → I on an interval J is called strictly increasing if it is increasing and moreover satisfies: p(t) = p(t ′ ) ⇒ t = t ′ or p(t) = 0 or p(t) = 1.
(2) A path p = (p 1 , . . . , p n ) : J → I n on an interval J is called (strictly) increasing if every component p i is (strictly) increasing.
A directed path p : I → X is called tame if the subdivision in (3) above can be chosen such that p(t i ) is a vertex for every 0 ≤ i ≤ l. A path that is strictly directed and tame is called strictly tame.
Observe that we allow d-paths that include non-trivial directed loops. (1) A Euclidean cubical complex [16] K is a subset of Euclidean space R n that is a union of elementary cubes [k i , k i + e i ] ⊂ R n with k i ∈ Z and e i ∈ {0, 1}. The maximal cubes in the cubical set that it realizes can be described by a pair of bottom and top vertices (k, l) ∈ Z n × Z n with 0 ≤ l i − k i ≤ 1. A Euclidean cubical complex is obviously proper and non-self-linked. Euclidean cubical complexes arise as models for P V -programs (cf eg [3]).
(2) For an example of a non-proper cubical set, consider the cubical set X glued from two squares (2-cubes) along a common boundary (consisting of four oriented edges and of four vertices). Its geometric realization is homeomorphic to a 2-dimensional sphere; but remark that the directed paths on this sphere are quite peculiar. The space of all such directed paths is actually homotopy equivalent to a circle. (3) [19] The -set Z n with exactly one cube in every dimension k ≤ n is obviously selflinked. For a description of d-paths in the geometric realization of this space, cf Example 6.5. (4) [19] The -set Q n has (n − k + 1) k-cubes c k 0 , . . . , c k n−k and face maps d e i c k j = c k−1 j+i+e . It arises from the cube I n by identifying all faces spanned by two vertices with i, resp. k + i coordinates 1 with each other (0 ≤ i ≤ n − k). This -set is proper, but also self-linked.

Different types of schedulings.
D-(irected): paths correspond to executions of a concurrent program -without the possibility to let one or several processes run backwards in time. Strict: d-paths correspond to programs where a particular process only may be idle at a vertex in the program (once a step is fully taken); between steps it needs to move forward in time at "positive speed". Tame: d-paths correspond to programs where processes need to synchronize at every vertex (a number of processes may stay idle inbetween) before progressing; at synchronization events, a process has taken a full step or it has stayed idle. Strict tame: d-paths correspond to programs combining both properties.
Our main result in Theorem 2.6 below states that the spaces of schedulings, regardless of the restrictions above, will have the same topological properties in all four cases.
In the final Section 6.3 we show that one may restrict (up to homotopy equivalence) the space of tame d-paths even further: It is enough to consider Pl d-paths that are piecewise linear with kink points at certain hyperplanes.

2.2.2.
A simple illustrative example. We refer to Figure 2. Let X = ∂I 3 be the -set corresponding to the boundary of a 3-cube. It has twelve edges: four parallel to each of the axes and labelled x, y resp. z and six two-dimensional facets: two parallel to each of the three coordinate planes and labelled xy, xz resp. yz.
The image of every d-path from the bottom vertex 0 to the top vertex 1 is contained in two subsequent square facets; the image of every tame d-path from 0 to 1 is contained in a pair of an edge and a facet. Taking care of intersections, one arrives in both cases at a category with geometric realization in form of a hexagon; homotopy equivalent to the circle S 1 . The space of all d-paths (whether tame or not) in ∂I n is indeed homotopy equivalent to S n−2 .  The -set X = ∂I 3 models the situation where a shared resource can serve two out of three processes but not all of them at the same time. Remark that a sequence like xy|xz (on top of Figure 2) of two subsequent facets can be interpreted as x (y|z), ie x and y|z are executed concurrently. Allowing this may be very convenient and speed up a concurrent execution. For an analysis of the consequences, it is reassuring to realize that the space of schedules between two given states is qualitatively the same regardless whether one allows parallel execution over a series of steps (like in x (y|z)) or only over one step at a time (like in yz).

Main result.
Let X denote a -set with finitely many cubes. For a given pair of vertices x − denote the spaces of directed, strictly directed, tame, and strictly tame dipaths from x − to x + (considered as subspaces of X I with the compact-open topology). Inclusion maps lead to the commutative diagram that also contains (maps into) the nerve of a poset-category C(X) x + x − explained in the sketch of the proof of our result: Theorem 2.6.
(2) For a proper non-self-linked -set X (cf Definition 2.2(2)), all path spaces are homotopy equivalent to the nerve of the category C(X) x + x − . Overview proof. It is shown in Proposition 3.4 by a cube-wise strictification construction that the maps with labels 1 and 2 are homotopy equivalences.
For a -set X and chosen end points x − , x + , we define a poset category C(X) x + x − , cf Section 4.3: An object of that category is a cube chain (cf Definition 4.11(4)) in X connecting x − with x + ; this a sequence of cubes such that the top vertex of each cube in that sequence agrees with the bottom vertex of the subsequent cube. Morphisms in C(X) x + x − correspond then to refinements of cube chains; for details consult Section 4.3.
We prove in Proposition 6.4 for paths in a proper non-self-linked -set X (cf Definition (indicated by the maps 5 and 6 ) and can therefore deduce that also 3 is a homotopy equivalence: Both spaces have a common underlying combinatorial structure! Our proof uses only the classical nerve lemma [1,10], cf Theorem 6.2, and a transparent taming construction (Proposition 5.1) for strict d-paths subordinate to the collar of a cube chain (cf Definition 4.5). The remaining inclusion 4 is a homotopy equivalence as well by the 2-out-of-3 property for homotopy equivalences. In the more involved case of a general -set X, we show in Proposition 6.6 that 3 is a homotopy equivalence using the projection lemma and the homotopy lemma (cf eg [12]) underlying the proof of the nerve lemma.
Remark 2.7. Many of the results in this paper are not new. Ziemianski proved in [18], using elaborate homotopy theory tools, that the space of tame d-paths T (X) x + x − is always homotopy equivalent to the nerve of a more intricate category Ch(X) of cube chains, even for a general -set X. This Reedy category (cf [11]) takes care of identifications on the boundary of cubes in a cube chain. Moreover, he shows by an ingenious global taming construction, that 4 is a homotopy equivalence. Apart from including spaces of strictly increasing paths (necessary in our proof for taming), this note presents a far more elementary argument that, for proper -sets, only uses the nerve lemma.  3)) with the following properties: Proof. One way to construct such a directed map is as the restriction of the flow of the differential equation y ′ = g(y) corresponding to a smooth function g : I → R with g(0) = g(1) = 0 and g(t) > 0, 0 < t < 1, e.g. g(t) = t − t 2 . For this choice, the function given by F (t, x) = xe t 1−x+xe t has the required properties.
The homotopy F on the interval I from Lemma 3.1 can be used to define a diagonal continuous directed homotopy F : I × I n → I n on the cube I n by F(t; x 1 , . . . , x n ) = (F (t, x 1 ), . . . , F (t, x n )). Remark that F respects all (sub)-faces of I n because of Lemma 3.1 (1). Applying this construction cube-wise (the same for every k-cube!), we define for every (geometric realization of a) semi-cubical set X, a continuous directed map F : I × X → X that lets all cubes -and in particular all vertices -invariant.

3.2.
Strictification is a homotopy equivalence. Using such a directed map F, we define a map S : Proof.
Proof. The metric d 1 corresponding to the l 1 -norm on individual cubes extends to a metric d 1 on X (the distance between two points being the infimum over the sum of distances on connecting chains) that induces the topology on X. The compact open topology on a function space with target X corresponds to the uniform convergence topology with respect to that metric d 1 .
If X is a finite complex, then I × X is compact, and hence the restriction F : I × X → X is uniformly continuous with respect to the metrics induced by d 1 .
Proposition 3.4. Let X denote a finite pre-cubical set with vertices x − and x + . Then the inclusions ι : Proof. The homotopy S : connects the identity map (for s = 0) with the map ι • S (for s = 1). Its restriction to S(X) x + x − connects the identity map on that space with S • ι.
The restriction of S to a map from (1) Every d-path p ∈ P (X) x + x − can thus be arbitrarily well approximated by a strict d-path of the form S(s, p), s > 0. This shows that Arbitrarily close to any strict d-path there is a d-path that "pauses" on a tiny interval.

Cube chains and collars
4.1. The collar of a face in a cube. We propose a user-friendly notation for repeated face maps in a cube -and then in a -set: Every partition [1 : n] = I 0 ⊔ I * ⊔ I 1 defines a face For a -set X, an n-cell c in X and a partition I 0 ⊔ I * ⊔ I 1 , the combinatorics of the quotient map q : . Remark that (for a self-linked -set), different partitions (of the same cardinality) can give rise to the same face.
If d and c are cubes in X, the collar of d in c is defined as (2) For a cube chain with vertices, we require only dim c i ≥ 0, ie we allow vertices within such a cube chain.
(1) To every cube chain with vertices one may associate a cube chain without vertices by simply leaving out every vertex.
(2) A cube chain in a -set X defines a vertex sequence (x − = x 0 , x 1 , . . . , x n , x n+1 = x + ) but, if X is not proper, not the other way round: More than one cube may share the same bottom and top vertex.
Let us for a moment focus on a single n-cube c in a -set X (with quotient map q : I n → c) and on certain d-paths in its collar C(c, X) connecting a point in st(c 0 ) with a point in st(c 1 ):  (1) The subspace T c (X) ⊂ T (X) of d-paths subordinate to c consists of d-paths with presentation p = [c 1 ; The subspace P C c (X) ⊂ P (X) of d-paths subordinate to the collar C(c) of c consists of d-paths p = p 1 * t 1 · · · * t n−1 p n with p j subordinate to the collar of c j in X.    (1), or if p is the concatenation of two paths subordinate to the collar of (e) at some point on the edge e. In either case, q(0.5, 0.5) is not contained in the image of p.  (1) Every cube chain c -and hence also its collar C(c) -contains a tame strict d-path.
(2) For every strict d-path p ∈ S(X) x + x − , there exists a cube chain c(p) such that p ∈ S C c(p) (X) x + x − . In the following proof, we will make use of coordinate hyperplanes in a cube chain. In a cube I n , consider middle hyperplanes given by the equations x i = 0.5, 1 ≤ i ≤ n. The elementary but crucial observation is that a strict d-path intersects any coordinate hyperplane in at most one point. Likewise, one defines coordinate middle hyperplanes (potentially with identifications on the boundary, one boundary middle hyperplane being identified with another such) in each cube in a -set X. Proof.
(1) The diagonal path δ n in ST (I n ) 1 0 connects bottom and top vertex of the n-cube diagonally with constant speed. For an n-cell c in X, composition with the quotient map I n ↓ c defines a strict tame path δ(c) in c from its bottom vertex to its top vertex. The concatenation δ(c) := δ(c 0 ) * · · · * δ(c n ) defines a strict tame path in the cube chain c connecting bottom and top vertex.
(2) For every strict d-path p : J = [j − , j + ] → I n in a single cube I n defined on some interval J ⊆ I, there is a finite set S ⊂ J (possibly empty) consisting of s j ∈ J at which p intersects one or several of the middle hyperplanes x i = 0.5, 1 ≤ i ≤ n. Define I j 0 , I j * , I j 1 as the set of indices i for which p i (s j ) is less than, equal, resp. greater than 0.5. Since p is strict, we have that I j+1 ] I n of the cube chain is minimal containing p(j + ). Now let p : I → X denote a strict d-path in a -set X from x − to x + with presentation p = [c 1 ; p 1 ] * t 1 [c 2 , p 2 ] * t 2 · · · * t l−1 [c l , p l ]. Then the construction above can be performed for each individual cube c i leading to a sequence c(p) of cubes the collar of which contains p(I). One has to check that two subsequent cubes "match": If p i (t i ) = p i+1 (t i ) is not contained in any middle hyperplane, then it is contained in the star of a vertex which is the top vertex in the cube chain corresponding to p i and the bottom vertex in that corresponding to p i+1 . If p i (t i ) = p i+1 (t i ) is contained in a middle hyperplane, then the last cube in the cube chain corresponding to [c i , p i ] agrees with the first one in the cube chain corresponding to [c i+1 , p i+1 ], ie the minimal cube in the boundary of c i and of c i+1 containing p i (t i ) -according to (b) above.
In a final step, one may erase cubes consisting of a single vertex; cf Remark 4.3(1). Figure 6. D-paths in two subsequent cubes in blue; the corresponding cube chains in orange, their collars in yellow. In the first two cases the two cube chains associated to each individual square consist of a single cube with common top, resp. bottom vertex; in the last case, the two cube chains share a common edge cube.  refinements. (4) Refinement between cube chains in X from a vertex x − to a vertex x + defines a partial order relation among cube chains that gives rise to a thin (poset) category C(X) x + x − with cube chains as objects and refinements as morphisms.
Remark that, for a general -set X, the category Ch(X) in Ziemiański's [18] differs from this poset category. Ziemianski's cube chains are concatenations of cubical maps from a standard cube into a cube in X; moreover cubical symmetries of the standard cube that induce identities in the -set are an additional part of the structure. ( For every strict d-path p ∈ S(X), the chain c(p) (Proposition 4.9(2)) is finest among the cube chains c with p ∈ S C c (X) x − intersect iff c and c ′ have a common refinement. Likewise for spaces of strict tame paths.
If X is proper and non-self-linked (cf Definition 2.2(2-3)), then two cube chains either do not have a common refinement or they have a coarsest one (for which equality holds in (5)). (7) Similar results hold for spaces of strict and tame d-paths. Proof.
(2) The diagonal path in ST c (X) from the proof of Proposition 4.9(1) is not contained in S C c ′ (X) x + x − . (3) Every elementary refinement (cf above) of the cube chain c(p) described above results in a collar that does not intersect at least one of the hyperplanes x j = 0.5 with j ∈ I * within a cube c i . In particular, it cannot contain p(I) which has a non-empty intersection with this hyperplane. (4) ⇐ follows from (1) and Proposition 4.9.
⇒: By (3) above, the cube chain c(p) for a path p in the intersection refines both c and c ′ . (5) The first part follows from (1) above.
Refinement of cube sequences is reflected in inclusion of path spaces (Proposition 4.12(1)). As a result of Proposition 4.9 and 4.12, we conclude: Corollary 4.14. Let X denote a -set with vertices x − , x + ∈ X 0 . Then The colimit identifies path spaces in finer cube chains with subspaces of path spaces in coarser ones; the colimit is therefore just a union of topological spaces.

Comparing paths in a cube chain and in its collar
Let c = (c 1 , . . . , c n ) denote a cube chain in a -set X between vertices x − and x + . The purpose of this section is to establish Proof.
(1) will be proved through a cubewise taming construction -first for individual d-paths and then for spaces of such. The proof of (2) follows the same pattern; you need to check that the d-paths and d-homotopies in the construction below stay tame.
To prove (1), we consider in a first step only strict d-paths subordinate to the collar of a cube chain d = (d 1 , . . . , d k ) within the standard cube I n ; d j is the face Consider the sequence of piecewise linear hypersurfaces H j ⊂ I n , 1 ≤ j < k, given by the equations m j (x) = 1, x ∈ I n , with m j (x 1 , . . . , x n ) := min i∈I j * x i + max i∈I j+1 * x i . The intersection of H j with the collar of the cube d l in I n is empty unless l = j or l = j + 1: In these collars, the coordinates x i satisfy either all x i < 0.5 or x i > 0.5 for i ∈ I j * ∪ I j+1 * . H j intersects the collars of d j and d j+1 within the collar of the vertex v j . For a strict d-path, p ∈ S C d (I n ), consider the functions given by the compositions m j • p : I → R, 1 ≤ j ≤ k; they are strictly increasing. When p enters st(v j ) at t = t − , we have min i∈I j * p i (t − ) = 0.5, whereas max i∈I j+1 * p i (t − ) < 0.5; their sum being less than 1; when p exits st(v j ) at t = t + , we have max i∈I j+1 * p i (t + ) = 0.5 and min i∈I j * p i (t + ) > 0.5; their sum being greater than 1. We conclude that there exists a unique ascending sequence t 1 < t 2 < · · · < t k−1 such that min i∈I j * and p i (t j ) > 0.5 for i ∈ I j 1 . We define a tame d-path t(p) = q as the concatenation q 1 * t 1 q 2 * t 2 · · · * t k−1 q k of strict d-paths q j : [t j−1 , t j ] → d j (from v j−1 to v j ): the components q j i , 1 ≤ i ≤ n, of q j are given by Furthermore, we define a linear d-homotopy H = H s of strict d-paths H s ∈ S C d (I n ) connecting p and q as H(t, s) = (1 − s)p(t) + sq(t).

Remark 5.3.
(1) Formula (5.2) has the following interpretation: On the interval [t j , t j+1 ], the components of p in I j 0 resp. in I j 1 are compressed to 0, resp. 1 (the respective processes in an HDA are idle), whereas its components in I j * are stretched to fill the entire interval (the respective processes take a full step). Remark that q(t j ) is a vertex for every 0 ≤ j ≤ k.
(2) If the cube chain d consists of a single cube only (a face, that may be just a vertex, but also the entire cube), then t(p) = q is given by formula (5.2) for q on the entire domain -no concatenation involved. (3) For a strict d-path p that is already contained in the cube chain c itself, p(t) solves the equation min i∈I j * x i + max i∈I j+1 * x i = 1 exactly at t j with p(t j ) = v j . Hence t(p) = p and H(t, s) = p(t) for s ∈ I.
Lemma 5.4. For every cube chain d in I n , the times t j = t j (p), 1 ≤ j < k, define continuous Proof. Given a d-path p ∈ S C d (I n ) and ε > 0 consider the open set of all strict d-paths q satisfying m j (q(t j (p) − ε)) < 1 and m j (q(t j (p) + ε)) > 1. Obviously, it contains the path p. For a strict d-path satisfying these two inequalities, the solution t =: t j (q) of m j (q(t)) = 1 is contained in the interval (t j (p) − ε, t j (p) + ε).
Proof of Proposition 5.1 continued. In the sequel, we assume given a strict d-path p ∈ S C c (X) x + x − . Let us fix a presentation (cf Definition 2.3(3)) and perform the taming construction above cubewise. It is not difficult to check that, since the cube chain and its collar are unchanged, the resulting tamed path and d-homotopy does not depend on the chosen presentation. Moreover, the tamed d-paths in subsequent cubes (and the d-homotopies) "fit" at top, resp. bottom vertices of the cube chain.
Finally, Lemma 5.4 and formula (5.2) show that the construction yields a continuous taming map T : x − ) I such that H 0 = id and H 1 is given by T -composed with an inclusion map. Moreover, Remark 5.3(3) shows that H leaves S c (X) elementwise fixed. 6. Taming is a homotopy equivalence 6.1. Proper and non-self-linked -sets. In this section, we deal with a proper non-selflinked -set X (cf Definition 2.2(2)). For a such, the taming result ( 3 in Theorem 2.6) is a consequence of the nerve lemma. This is essentially due to Proposition 6.1. Let X denote a proper non-self-linked -set and let c denote a cube chain in X from x − to x + . Furthermore, let also c 1 , . . . c k denote cube chains in X from x − to x + .
(1) The spaces S c (X) x + x − and P c (X) x + x − of (strict) d-paths subordinate to c are contractible.
x − are contractible if the cube chains c i possess a common refinement and empty otherwise. Proof.
(1) For P c (X) x + x − , this has been observed in [17,Proposition 6.2(1)]. In brief, the space of d-paths in a single cube from the bottom to the top vertex is contractible (to the unit speed diagonal path joining them, say) by a linear d-homotopy. For paths in a general cube chain, perform first a reparametrization homotopy joining every d-path with its naturalization [15], ie, a unit speed path with respect to the l 1 -norm along the same trajectory. The space of natural d-paths can then be contracted cube-wise.
For S c (X) x + x − , one can either go through the same steps for strict d-paths or one can refer to Proposition 3.4 (or rather its proof) in the current paper.
(2) For S C c (X) x + x − , this follows from (1) and Proposition 5.1. For P C c (X) x + x − , apply then Proposition 3.4 (or rather its proof).
(3) follows from (2) and Proposition 4.12 (6). Theorem 6.2 (Nerve lemma [1,10]). Let Z denote a paracompact topological space and let U denote a good covering Z = U i of Z by open sets U i ⊂ X, ie all non-empty intersections i∈I U i are contractible. Then X is homotopy equivalent to the nerve of the poset of these non-empty intersections ordered by inclusion.
This nerve is a simplicial complex with vertices corresponding to the U i and (k − 1)dimensional simplices corresponding to non-empty intersections i∈I U i . Corollary 6.3.
(1) The space S(X) x + x − of strict d-paths is homotopy equivalent to the nerve of a covering U (X) x + x − ; likewise, the space ST (X) x + x − of strict tame d-paths is homotopy equivalent to the nerve of a covering V(X) x + x − . (2) The two spaces are homotopy equivalent to each other. (2)) by open (Proposition 4.8 (2)) and contractible (Proposition 6.1) sets; intersections of sets in the covering are empty or contractible by Proposition 6.1 (3). Hence the covering x − are metrizable and thus paracompact, cf [15]. Apply the nerve lemma, Theorem 6.2 to show (1) above.
The two coverings correspond to each other through inclusion maps over the same poset and giving rise to the same nerve: By Proposition 4.12(4), its objects can be enumerated by all sets {c i } of cube chains in X from x − to x + that possess a common refinement (the partial order is generated by refinement and superset).
The remaining paragraphs in this section are not important for the main result, but they lead to a far simpler poset with a smaller nerve, better suited for calculations: The poset category corresponding to the covering U (X) x + x − is very redundant: By Proposition 4.12(4), its objects can be enumerated by all sets {c i } of cube chains in X from x − to x + that possess a common refinement (the partial order is generated by refinement and superset).
x − denote the poset correponding to the covering U (X) x + x − described in the proof of Corollary 6.3 Consider the poset map P U (X) x + x − → C(X) x + x − that associates to a set {c i } of cube chains the coarsest common refinement of all the c i . The fiber (ie comma category) over any c ∈ C(X) x + x − has the set {c} as an initial element, and is thus contractible. Apply Quillen's Theorem A! [14] 6.2. General -sets. I am indebted to K. Ziemiański for pointing out to me that Proposition 6.1 is no longer true for non-proper -sets. Example 6.5. Let Z n denote the unique -set with exactly one cube c k , 0 ≤ k ≤ n, from Example 2.4 (3). For n = 2, consider the cube chain c consisting of the single cube c 2 from c 0 to c 0 . Then S c (X) c 0 c 0 is homotopy equivalent to a circle S 1 -and hence not contractible! In fact, it deformation contracts to the subspace of piecewise linear d-paths in c 2 connecting c 0 with itself through a point on the anti-diagonal (connecting c 0 with itself).
For a general -set X, the proof of Theorem 2.6(1) requires a little more machinery from algebraic topology: Instead of the nerve lemma itself, we apply two more general results in homotopy theory that are used in proving it: the projection lemma comparing colimits with homotopy colimits and the homotopy lemma comparing homotopy colimits of spaces that can be glued together from pieces that are mutually homotopy equivalent. For a quite elementary presentation, cf eg [12]. Using these two results, we can prove that taming is a homotopy equivalence also for general -sets: Proposition 6.6. Let X denote a -set with selected vertices x − , x + ∈ X 0 . Then the inclusion map ι : x − is a homotopy equivalence. Proof. The proof proceeds by a series of homotopy equivalences (denoted ∼ =) : In both cases, the first homotopy equivalence is due to the projection lemma, the second to the homotopy lemma and Propostion 5.1. Paths subordinate to a cube chain c are automatically tame, hence S c (X) x + x − = ST c (X) x + x − . Remark 6.7. By far more sophisticated homotopy theoretical methods, Ziemiański proved in [18] that T (X) x + x − is homotopy equivalent to the nerve of a Reedy category Ch(X) instead of our poset category C(X) x + x − , also for general -sets. He uses a filtration of T (X) x + x − by differently defined contractible subsets using tame presentations. But these subspaces do not define an open covering, and therefore it is not possible to obtain the result by invoking the nerve lemma! Furthermore, Ziemiański shows that T (X) x + x − ֒→ P (X) x + x − is a deformation retract by a global taming construction that is far more tricky than our local one (which is supposed subordinate to the collar of a cube chain).
6.3. PL d-paths and spaces of sequences. In this final section, we restrict attention to proper non-self linked -sets (cf Definition 2.2(2-3)). At least for these, it is possible to find an even smaller model describing the homotopy type of the space of all d-paths between two vertices: To this end, consider the intersections H k of an n-cube I n (and hence of an n-cube in a -set X) with the hyperplanes given by the equations x 1 + · · · + x n = k, k ∈ N, 0 < k < n; different from the hyperplanes previously considered. Every hyperplane section H k is an (n − 1)-dimensional polyhedron with the vertices with k entries 1 and n − k entries 0 as extremal points. Requesting certain variables to take the value 0 or 1 yields the restriction of these hyperplane sections to faces; on which they again are hyperplane sections.
Observe that two elements x k ∈ H k and x k+1 ∈ H k+1 such that x k ≤ x k+1 (ie there exists a d-path from x k to x k+1 ) have l 1 -distance (aka. Manhattan distance) d 1 (x k , x k+1 ) = 1.
The hyperplane sections H k ⊂ I n are achronal: Each d-path p in I n intersects a hyperplane section H k in at most one point p k ∈ H k ; if defined, d 1 (p k , p k+1 ) = 1. The union of all hyperplane sections H k corresponding to all cells in the geometric realization of a -set X form a subspace H(X) ⊂ X. Any d-path between two elements of H(X) has integral l 1length (which is thus invariant under directed homotopy). The shortest length is called their l 1 -distance d 1 ; compare [15] for this concept in greater generality.
A d-path p : A reparametrization linearly adjusting the domain to length one defines an inclusion map ι N : N (X) x + x − ֒→ P (X) x + x − . Analogous to reparametrization by unit speed for curves, one defines a naturalization map in the opposite direction and proves it to be a homotopy inverse: Proposition 6.8. [15,18] For a -set X with selected vertices x − , x + ∈ X 0 , the inclusion map ι N : x − is a homotopy equivalence. The natural tame d-paths form a subspace with inclusion ι N T : N T (X) x + x − ֒→ N (X) x + x − ; naturalization preserves the trace of d-paths and hence tame d-paths and tame d-homotopies stay tame under naturalization: Corollary 6.9. For a -set X with selected vertices x − , x + ∈ X 0 , the inclusion map ι N T : N T (X) x + x − ֒→ T (X) x + x − is a homotopy equivalence. Remark 6.10. Let p : J → X on an interval with min J = 0 denote a natural d-path in X.
(2) If p is tame, then p(i) and p(i + 1), i an integer, are contained in a common cube. A minimal such cube is uniquely determined since X is proper. Moreover, since X is non-self-linked, there is a unique unit speed line segment d-path (of length 1) in this (and any other) cube containing them.
A path p ∈ N T (X) x + x − with p(0) = x − is called P L (piecewise linear) if, for every integer i in its domain, the path between p(i) and p(i + 1) is given by the unit speed line segment (of l 1 -length 1) in the minimal cube that contains them both. These P L paths between x − and x + form the subspace P L(X) x + x − ⊂ N T (X) x + x − . Proposition 6.11. Inclusion ι P L : P L(X) x + x − ֒→ N T (X) x + x − ֒→ T (X) x + x − ֒→ P (X) x + x − is a homotopy equivalence.
Proof. In view of Theorem 2.6 and Corollary 6.9, it remains only to show that the first inclusion is a homotopy equivalence. In fact, P L(X) x + x − is a deformation retract in N T (X) x + x − : To a natural tame d-path p : J → X associate the PL d-path L(p) obtained by linearly connecting p(i) with p(i + 1) for i, i + 1 ∈ Z ∩ J in the unique minimal cube containing both, cf Remark 6.10. Observe that p = L(p) if p is P L. The (natural) convex combination homotopy joining p ∈ N T (X) x + x − with L(p) shows that the linearization map L thus defined is a homotopy inverse to the first inclusion map. It restricts to the constant homotopy on P L(X) x + x − . The only data needed to describe P L d-paths are the kink points p(i) in the cubes they traverse: The space Seq(X) x + x − is defined as the space of all finite sequences (x 0 = x − , . . . , x n = x + ) ∈ n≥0 H(X) n+1 with x i , x i+1 in a common cube such that x i ≤ x i+1 and d 1 (x i , x i+1 ) = 1.
Example 6.12. Consider the boundary of X = ∂I 3 from Section 2.2.2. The hyperplane sections (diagonal lines) in the six boundary squares form two triangles, cf Figure 9. The associated pairs (= sequences) of kink points between the bottom and the top vertex form a hexagon, homotopy equivalent to a circle S 1 : With this definition, we obtain Proposition 6.13. Let X be a proper non-self-linked -set with selected vertices x − , x + ∈ X 0 . Then P (X) x + x − and Seq(X) x + x − are homotopy equivalent. Proof. We may replace P (X) x + x − by P L(X) x + x − by Proposition 6.11. The forgetful map that associates to a path p ∈ P L(X) x + x − the sequence (p(i)) ∈ Seq(X) x + x − -with i running through the integers in its domain -is a homeomorphism. Its inverse is the map that associates to a sequence in Seq(X) x + x − the P L-path that connects any two subsequent elements in the sequence by the unit speed line segment in the unique minimal cube containing them both. Remark 6.14. Extending the results of this section to a general -set X seems to be more intricate. The main reason is that, in some cases, two elements in successive hyperplane sections can be joined by more than one unit speed line segment paths -through different cubes if X is not proper and/or through the same cube if X is self-linked. For example, two vertices in subsequent hyperplane sections may be connected by various edges, after identification of vertices.
It seems to be necessary to replace the cube chains from this paper by the cube chains Ch(X) in Ziemiański's paper [18]; those are generated by cubical maps from a wedge of cubes into X. Hyperplane sections in X are then replaced by hyperplane sections in a wedge of cubes. In such a wedge of cubes (which is obviously both proper and non-self-linked), there is a well-defined unit speed line segment between points on consecutive hyperplane sections.


A time-saving automobile assembly state monitoring system based on channel-pruned YOLOv4 algorithm

 A time-saving automobile assembly state monitoring system in industrial environment is presented in this paper. The system only needs to input a video which contains the whole detected parts and manually label in the first frame. By finding the best point for tracking and tracking the point, the dataset can be automatically generated which saves time spent on manufacturing the dataset and makes the assembly state monitoring system easy to deploy into a practical industrial environment. The target detection algorithm uses the channel-pruned YOLOv4 neural network. The experimental result shows the algorithm balances speed and accuracy. Compared to original YOLOv4, our proposed method is two times faster and the mAP is nearly equal to it. It shows that the channel pruning process dynamically improves the speed of the forward propagation without sacrifice accuracy.

Introduction
In automobile industry, assembly line requires the most manpower due to the complexity of the process 1 . Despite that the workers are frequently professionally trained, there is still a tiny probability of error. As Murphy's law says: anything that can go wrong will go wrong if repeatedly.
The assembly line covers thousands of steps. If an inaccurate step occurs, the factory will spend a lot of time to repair and even it will cause serious consequences.
In this paper, in response to this problem, a real-time and accurate automobile assembly state monitoring system is proposed. The system is able to detect the result of the assembly by obtaining the image and inputting it to the neural network. If a workpiece is wrongly installed or forgotten by mistake, it will remind the worker to check it, which will eliminate of ill effects of the mistake. In addition, the algorithm is based on deep learning which frees programming personnel from manually extracting image features. Normally, the deep learning algorithm needs numerous labeled images as dataset. Contrastively, the proposed algorithm needn't label the image by hand and the algorithm will automatically label the input image. Besides, operating personnel can shoot a video of the area to be tested and the datasets can be automatically generated. The generated datasets are subsequently used to train the neural network. This saves time spent on manufacturing the dataset and makes the intelligent grasping system easy to deploy into a practical industrial environment.
Due to the accuracy and robustness of the convolutional neural network, the success rate of the gripping operation reached an astonishing 100% without interference. The approach is validated in a series of experiments. This method frees workers from monotonous work and improve factory productivity.
Target detection algorithms based on deep learning are divided into two categories 2 . One is a classification-based target detection algorithm (two-stage) and the other is a regression method for target detection (single-stage). As the name implies, the two-stage method uses two steps to perform target detection: 1. Generate a possible region (Region Proposal) and use CNN to extract features.
2. Use the classifier to classify and correct the position. The representative of this type of method is R-CNN 3 . In 2014, Ross et al. proposed R-CNN. The algorithm uses selective search to obtain candidate regions and then normalizes them as input to the CNN network. Then use the neural network to obtain the characteristics of the candidate area, and finally use multiple SVM classifiers for classification. R-CNN greatly improves the accuracy of target detection. However, because R-CNN performs feature extraction and calculation on all candidate regions, the overlapping regions between multiple candidate regions are repeatedly calculated many times, resulting in a large number of repeated calculations and reducing the computational efficiency. Due to the complexity of the calculation process, a large amount of intermediate data needs to be stored during the calculation process, which requires a large number of storage resources. Therefore, the real-time performance of R-CNN is not strong, and it takes up storage resources very much. In 2015, Fast R-CNN improved on the basis of SPP-Net, simplified the SPP layer, combined the classification and border regression problems, and introduced SVD decomposition to reduce the amount of calculation 4 . However, Fast R-CNN still uses the selective search method to select candidate regions which consumes a lot of computing resources and its calculation speed is still not satisfactory. In response to the problem of candidate region selection, Faster R-CNN uses RPN network instead of selective search method, marking that the target detection algorithm based on deep learning has embarked on a true end-to-end calculation 5 . However, because Faster R-CNN still uses the ROI layer in Fast R-CNN, its effect on the detection task of small targets is not satisfactory. And due to the limitation of two-stage itself, the fastest Faster R-CNN in the two-stage series of algorithms can only reach 5 FPS. Therefore, researchers have proposed another idea: single-stage. The problem of target detection and classification is directly transformed into a regression problem, and the step of selecting candidate regions and extracting features is removed, and the position and category of the detection object are directly obtained through the entire image. The representative of this series of algorithms is the YOLO algorithm 6 . The YOLO algorithm divides the entire picture into S*S grids, and each grid is responsible for detecting the detection object whose center falls within the grid, including the location and category information of the detection object. This algorithm trades for a significant increase in speed by discarding a certain degree of accuracy, and its detection speed can reach up to 45FPS. In 2017, the author of YOLO proposed the YOLOv2 algorithm, which improved the detection accuracy and speed by adding the batch normalization layer after the convolutional layer and adding the K-Means clustering method 7 . This algorithm represents the most advanced target detection algorithm in the industry this year. In 2018, YOLOv3 made some design details improvement based on YOLOv2, and once again improved the detection accuracy while maintaining a higher detection speed 8 . In short, for different application scenarios, the two-stage algorithm and the single-stage algorithm have their respective scopes of application. There is no inferior algorithm, only suitable usage scenarios.

Proposed system description
The procedure of intelligent grasping system proposed in this paper is illustrated in Fig. 1. In this system, a video including detected workpiece in various angles is the original input of the system. Operating personnel set the region of interest which only includes the detected workpiece. And then the system will work automatically. In the region of interest, at most 100 tracking points are extracted to realize the tracking of the detected workpiece in the first frame. The tracking points will update in the next frame by optical flow method. In each frame, the smallest orthogonal rectangle containing each tracking point is calculated. Each frame is saved to image and together with the coordinates and dimensions are integrate into datasets to train the neural network based on YOLOv4 model.

Find the best point for tracking
First, take a video containing all the parts whose assembly state is inspected. Then, find the strongest corners to be tracked in the first frame. To find them, convert every frame of the video to 2-dimensional grayscale. Assume an area with coordinate (u, v) and shifted by (x, y). The weighted sum of squared differences between these two areas which are denoted by S(x, y) can be calculated by: Perform Taylor expansion to I(u+x, v+y) and let I x and I y be the partial derivatives of I. We have: Which produces the approximation: where A is the structure tensor, A strong corner has a large value of S in two directions. Calculate the eigenvalues of A and select A with two large eigenvalues as the strong corner. Based on the magnitudes of the eigenvalues λ 1 and λ 2 , the points with min(λ 1 ,λ 2 ) are selected for tracking according to the Kanade-Tomasi corner detecting method 9 . As shown in Fig. 2, in the first frame of the video, a total of 100 points are selected to be used for the next track.

Fig. 2
The best points to be tracked

Track the point and generated the dataset
After the corner points are selected, use the optical flow method to track the trajectory of these points. In the video, assume that the displacement of the part between two nearby frames is small and almost constant in a little area. Hence, the optical flow velocity vector (V x , V y ) always satisfies the following equation: Where q 1 , q 2 , ... q n are the pixels near the corner point, and I x (q i ), I y (q i ), I t (q i ) are the partial derivatives with respect to position x, y and time t. Convert these equations into matrix form: The system of equations is overdetermined. Based on the least-squares principle, the optimal solution is as follows 10 : Iterating on every frame, the assembly part is tracked in the video. The tracking effect of the workpiece is shown in Fig. 3. By extracting the best tracking point and tracking by optical flow method, the position of the detected workpiece in each frame is accurately calculated, which is crucial to produce the dataset.

Neural networks configuration
Use the training image datasets generated by the above method to train the convolutional neural network. Experimental evidence demonstrates that the quantity is adequate for the convolutional neural network to provide precise object detection. A novel neural network whose inputs are 608×608 images resized from the original images and outputs are coordinate position of the workpiece is proposed. The neural network configuration is based on the YOLOv4 11 which is a CNN-based object detector. The architecture of the neural network is shown in Fig. 4, composed of an input layer, backbones, neck and heads. The backbone is the core of the network for extracting features whose role is to extract the information in the image for use by the subsequent network.
These networks often use Resnet, VGG, etc. because these networks have proven that they have strong feature extraction capabilities on classification problems 12 . In training process, the officially trained model parameters are directly loaded, followed by our own network. Let these two parts of the network be trained at the same time because the loaded backbone model already has the ability to extract features. During the training process, it will be fine-tuned to make it more suitable for the tasks. The neck is placed between the backbones and the head to make better use of the features extracted by the backbones. The head is the network that obtains the output content of the network, using the previously extracted features, and the head uses these features to make predictions. The tensor formula is as follows: Fig. 4 The architecture of the YOLOv4 neural network Where bounding box=2, offset=4 and object=1. As the Fig. 5 shown, N is equal to 19, 38 and 76 respectively so the result can be predicted for the three scales in the network which improves the performance of detecting tiny objects. There are two types of datasets: successfully assembled and not assembled, so class=2. value. Hence, this the sigmoid is multiplied by a factor λ=2, so simplifying detection of the objects on the edge of grid.
There are two factors that influence objectness score. First, whether the area has a target to be predicted. If there is a target to be measured, set P r (object) to 1. If the opposite, set it to 0. Then calculating the intersection over union (IOU) of the predicted and ground truth region. The product of the two factors is the objectness score which is calculated by:

�10.�
Because the prediction box contains two categories and each prediction box can contain no more than one category, the softmax activation function is selected to output the probability. In order to balance the disparity between the number of positive and negative samples, a weighting factor α∈[0, 1] is imported 13 . In practice, we define the loss function as: Where L represents the value of cross-entropy loss, y (i) is the label of the sample whose value is 0 or 1, � ( ) is the probability that the sample is predicted to be positive and α denotes the weight coefficients for different classes. This method is adopted in the experiments as it dramatically improves accuracy over the conventional cross-entropy function and found that α=0.8 works firstrate in the experiments.

Discussion
In order to accurately detect the assembly state and deploy the system on industrial computers with inferior compute capability, a real-time target detection algorithm based on YOLOv4 and a channel pruning algorithm were proposed in this paper. Besides, the dataset is automatically generated by corner detection and optical flow method which saves the time of manually creating datasets. The main conclusions are as follows.

Training process
This section uses YOLOv4 algorithm for training and testing. To train the training set of 2400 images, the PC is equipped with 32.0 GB RAM, Core i7-9700F CPU 3.0 GHz, and the NVIDIA GeForce RTX 2060. A batch size of 32 and 4000 epochs are specified. The experiment includes the following three steps.
• Step 1: A dataset including 500 images is automatically generated. The images were used to train the neural network.
• Step 2: The trained neural network was used to detect the images containing the assembly part.
• Step 3: In order to achieve the desired results, we finetuned the parameters and retrained.
Steps 1, 2, and 3 are repeated continuously. When all the states of automobile assembly are detected, the training process ends. The experimental process is shown in Fig. 6.

Fig. 6 The detailed experimental process
To execute the detection, the input size of the neural network was specified to 608 pixels × 608 pixels, which was mainly due to the relatively small size of assembly parts. Then perform subsequent processing. There will be 19*19*14, 38*38*14, and 76*76*14 feature maps in the network. The parameters of the training process are shown in Table 1.
After the training is completed, the loss curve during the training process is shown in Fig. 7. It shows that at the initial stage of the assembly parts detection model training, the model learning efficiency was higher, and the training curve convergence speed was faster. As the training deepened, the slope of the training curve gradually decreased. Finally, when the number of training iterations reaches about 2000, the model learning efficiency gradually reached saturation and the loss function fluctuated slightly around 0.05.

Parameters Value
Input size 608 × 608 Learning rate 1.0 × 10 -3 Batch size 32 Classes 2 Iterations 4000 Step1: Automatically generate images with label Step2: Use the generated images to train the model Step 3: Based on the results, fine-tune the training parameters. We set a total of 20 sets of scene images containing the assembly process which have not appeared in the training dataset. Each scene contains one or two assembly parts which are randomly set as successfully assemble or not. The proposed algorithm successfully identifies these assembly states. The detection effect of the trained YOLOv4 algorithm on assembly parts was shown in Fig.   8. It could be seen that the algorithm could completely detect the assembly parts, indicating that the algorithm used in this research could be deployed in auto industry and perform excellently.

Channel Pruning and Fine-tuning
To accelerate the process of forward propagation and reduce requirements for compute capability, the original YOLOv4 is slimmed by pruning the channels in which many scaling factors are near zero 14 . The workflow is shown in Fig. 9. In the training process, the loss function is added a sparsity-induced penalty on the scaling factors to obtain a narrow network (see Fig. 10). The new loss function is calculated by: Where γ is a scaling factor for each channel multiplied to the output of that channel and λ is a parameter that balances two terms. In YOLO, γ is the scale affine transformation parameters which are responsible for linearly transforming normalized activations in batch normalization layer.
Further experiments show that the training effect is the best when λ=10 -5 . The smooth function is defined as: Compared with the L1 and L2 norms, the smooth function converges faster and is more robust to outliers.
Train with channel sparsity regularization Prune channels with small scaling factors Fine-tune the pruned network Narrow network Original network

Comparison of different object detection algorithms
In recent years, algorithms based on deep learning have achieved good results in the industry.
More and more excellent algorithms are proposed. In order to compare the performance of these algorithms in recognizing assembly state, five algorithms are tested in this paper, including Faster R-CNN, SSD 300, Tiny-YOLOv2, YOLOv3 and original YOLOv4. The backbones of these four object detection algorithms are ResNet50, VGG16, compressed Darknet 19, Darknet53.
Use the same training dataset to train five types of neuron networks, and then measure the performance of them by the same test dataset. Evaluation index includes precision, recall, mAP, F1 score (also called Dice similarity coefficient) and detection speed. The calculation formula is as follows: The accuracy of the detection reflects the model's ability to recognize the assembly state.
Meanwhile, the speed of detection represents the potential of the algorithm to be deployed in portable devices or industrial computers with inferior compute capability. In this paper, a total of six different object neural networks including the Faster R-CNN, SSD 300, Tiny YOLOv2, YOLOv3, original YOLOv4 and the proposed method were tested to analyze the performance of assembly state detection. The test results were shown in Table 2. The Tiny-YOLOv2 was the fastest among six algorithms. However, the mAP of the Tiny-YOLOv2 was much lower than that of the proposed algorithm. Compared to original YOLOv4, our proposed method is two times faster and the mAP is nearly equal to it. It shows that the channel pruning process dynamically improves the speed of the forward propagation without sacrifice accuracy.
In addition, we restrict the algorithm to run on the CPU to simulate being deployed in industrial computers. The original YOLOv4 consumes 1 second for each forward propagation. Contrastively, the proposed channel-pruned network only consumes 0.6 seconds to complete the same process.
The result shows that even if deployed in portable devices or industrial computers with inferior compute capability, the algorithm can also achieve good detection results.


YOLO-SD: A Real-Time Crew Safety Detection and Early Warning Approach

Wearing safety rope while working at the loft and over the side of a ship is an effective means to protect seafarers from accidents. However, there are no active and effective monitoring methods on ships to control this issue. In this article, a one-stage system is proposed to automatically monitor whether the crew is wearing safety ropes. When the system detects that a crew enters the work area without a safety rope, it will warn the supervisor. In this regard, a safety rope wearing detection dataset is established. +en a data augmentation algorithm and a boundary loss function are designed to improve the training effect and the convergence speed. Furthermore, features from different scales are extracted to get the final detection results. +e obtained results demonstrate that the proposed approach YOLO-SD is effective at different on-site conditions and can achieve high precision (97.4%), recall rate (91.4%), and mAP (91.5%) while ensuring real-time performance (38.31 FPS on average).

Introduction
In order to minimize the human injury and loss of life at sea, the International Maritime Organization (IMO) has adopted the International Safety Management (ISM Code) as a mandatory standard and requires vessel operators to develop, implement, and maintain their Safety Management System (SMS). Generally, it requires that when working aloft, the crew must obtain the captain's permission, and a checklist, two or more staff, and a task manager must be assigned at the same time. However, it cannot guarantee that all the crew can implement these rules. Issued statistics by the European Maritime Safety Agency (EMSA) [1] indicate that, from 2014 to 2019, maritime accidents across Europe caused more than 496 deaths and 6,210 injuries, of which slips, trips, and falls share almost 37% of all accidents. More specifically, during a ship drilling in November 2019, a Japanese cargo ship ORANGE PHOENIX crew died after falling to the deck without a safety rope. Studies of the EMSA show that many casualties at offshore tasks originate from not wearing safety ropes by the crew. Currently, monitoring the safety rope wearing is one of the workers' mutual inspections before the operation [2]. So far, no automatic method has been proposed in this regard so that it is a challenge for the captain or shipping company manager to ensure whether the crew is wearing safety ropes when working at high altitudes. Accordingly, it is of significant importance to establish a method to automatically determine whether the crew is wearing a safety rope when entering the work area. e crew working at height refers to working on ship masts (see Figure 1(a)), outside chimneys (see Figure 1(b)), or ship crane (see Figure 1(c)). Unlike ordinary construction sites, there are a few crews onboard, which mainly originates from the space limitation. Accordingly, the working crews lack adequate supervision and protection during the work. Moreover, the crew works in a wide range of vertical space on the ship, which requires safety rope detection algorithms, multiscale detection capabilities, and high robustness. On the other hand, conventional target detection algorithms often rely on cloud platforms with substantial computing power or high-performance GPU computer clusters to achieve better detection rates. However, considering onboard requirements, it is a challenge to apply these algorithms. Generally, safety detection and early warning systems for the crews working at heights should have the following capabilities: (1) determine whether all individuals in the working area are wearing a safety rope; (2) detect the surveillance video in real time; (3) issue a warning message when the crew enters the working area without wearing a safety rope. Currently, investigations about safety ropes are mainly focused on the use of visual perception technology [3][4][5][6] and signal processing [7,8] to perform a qualitative or quantitative analysis of the reliability of safety rope. Particularly, detecting the wearing of safety rope on the ship has not yet been carried out.
In the present study, it is intended to specifically address the task of safety rope-wearing detection on the ship. e main objective of this article is to identify whether all crews on the ship's high-altitude operation area wear a safety rope or not; otherwise, a warning message should be issued on the monitoring screen. e difficulty of the above-mentioned tasks makes it problematic to rely on any multistage method with handicraft features. In order to resolve this problem, a convolutional neural network (CNN) is introduced. e proposed method is inspired by the development of a one-stage detector YOLO (You Only Look Once) [9], which implements the object by directly regressing bounding boxes through a single CNN. Compared with conventional target detection methods, the established method can automatically perform feature learning and provide excellent performance in the field of computer vision. e main contributions of this article can be summarized as follows: (1) It is the first method that introduces CNN into the crew safety detection and early warning in surveillance video. e proposed system is end-to-end trainable. (2) Based on the YOLOv5 pipeline and BN-Conv modules, a multiscale CNN framework YOLO-SD is proposed to improve the accuracy and speed of the detection under complex surveillance conditions. (3) Based on the proposed method, Crew Safety Rope Wearing Detection Dataset is established, which contains 3150 images and 6,583 safety ropes instances.
ese images cover massive changes in diverse scenes and scales as well as examples with occlusion. Each instance in the benchmark is annotated with a class label with a bounding box. e contents of this article are organized as follows: e literature survey is presented in Section 2, followed by the system overview in Section 3. en details of the proposed Crew Safety Rope Detection algorithm are discussed in Section 4. e experimental results are presented in Section 5. Finally, conclusions and main achievements are summarized in Section 6.

Literature Survey
Aiming at detecting the target precisely, detection and classification with precise target positioning are combined to provide a proper understanding of the image. In conventional target detection techniques, artificial features are mainly applied to extract and shallow trainable structures for target detection. Consequently, these methods may simply fail in complicated scenes, severe climate, and different occlusions.
With the emergence of deep learning technology [10][11][12][13], many limitations of conventional target detection technologies have been resolved so that deeper semantics and features can be learned. e deep learning-based target detector has three main modules, including information area selection, feature extraction, and classification. In the information area selection process, a multiscale sliding window is usually applied to scan the entire image and calculate the height process. Moreover, the target recognition process is mainly carried out in the feature extraction process. It is based on visual feature extraction to characterize the semantics of the target. It is worth noting that common features in this regard are SIFT [14], HOG [15], and Haarlike [16]. Finally, classification is defined as the process of distinguishing the target object from all other categories. Some common effective classifiers are AdaBoost [17], support vector machine (SVM) [18], and deformable component model (DPM) [19]. Based on these algorithms, modern target detectors can be mainly divided into two categories: (1) target detectors based on the area proposal such as R-CNN [20], Fast R-CNN [21], Faster R-CNN [22]; (2) detectors based on the target detector for classification/regression such as YOLO [10,[23][24][25], SSD [26], and Effi-cientDet [27]. In the former detectors, the area proposal should be initially generated and then the proposal area should be classified. is two-level detector based on the region suggestion extracts the candidate area, which is a complex and time-consuming process to achieve real-time detection. On the other hand, the target detector based on classification/regression has only a single forward CNN network, eliminating the region suggestion generation and subsequent feature resampling. Accordingly, it encapsulates all calculations in a network, thereby making it easier to realize a real-time detection. Redmon used mapping and direct evaluation of class probabilities to predict candidate frames and proposed a one-stage object detector YOLO [9]. e main idea of this detector was to divide the captured image into specific grid units, where each grid unit is responsible for predicting the candidate anchor and the corresponding confidence value. Further investigations reveal that this method can process 45 frames of images per second in real time, which is much higher than that of other target detectors. However, YOLO cannot effectively deal with objects with unusual aspect ratios or small objects. In order to resolve these shortcomings, Liu used the anchor, RPN, and multiscale representations and proposed a single-shot multibox detector (SSD) [26]. Moreover, Redmon improved the original YOLO and proposed YOLO9000 [23] and YOLO v3 [24] and achieved good results in detecting high-resolution or multiscale targets. Bochkovskiy [25] improved Redmon's YOLO framework and proposed YOLO v4 and YOLO v5. Accordingly, a 43.5% average accuracy and 140 fps were achieved on the MS-COCO data set. Figure 2 shows the framework of the proposed algorithm YOLO-SD, indicating that the proposed framework is mainly composed of three networks.

System Overview
(1) Data Augmentation Network: In the training stage, a data augmentation network is designed to augment the dataset and increase the number of multiscale safety ropes and the number of target-occluded images artificially, to improve the network's ability to detect different scale safety ropes and improve the algorithm robustness. When the prediction network detects a crew member entering the work area without wearing a safety rope, the system marks it out and issues a sound warning to remind the supervisor.

Data Augmentation Network.
During the experiment, it was found that the majority of missing targets were relatively small targets. is phenomenon may be attributed to the following two reasons: (1) e area of the safety rope in the image is relatively small. (2) e safety rope can be easily blocked by other objects. Kisantal [28] showed that the algorithm's detection performance for small targets could be improved through the oversampling and copy-pasting data enhancement methods for images containing targets. Accordingly, a data augmentation strategy is designed to train the algorithm and overcome the foregoing problems. To this end, each image is initially oversampled and then new training images are generated by flipping, random scaling, random cropping, and random arrangement. Figure 3 shows that the bottom image, which is used for the training, is generated by randomly cropping, arbitrarily scaling, flipping, and rearranging the four top images.

Feature Extraction Network.
e extraction of safety rope features is the key to detect and identify the safety rope. In this regard, the Darknet53 network is employed to extract safety rope features, which is based on the Darknet-19 and residual network of YOLO v2. e network is deepened to layer 53 and then shortcut connections are added between layers. It should be indicated that as the deeper network structure deepens, more advanced features of the safety rope can be extracted. However, the corresponding network calculation and the computational complexity dramatically increase.
e Darknet53 network introduces Cross-Stage Partial Networks (CSPNet) [29] to achieve a more decadent combination of gradients while reducing the calculation. In particular, CSPNet divides the feature map of the Darknet53 network base layer into two parts, where the first part passes through a dense block and the other part passes a transition layer and then merges them through a cross-stage hierarchical structure. e main idea is to propagate the gradient flow through different network paths by separating the upper layer of gradient flow. Accordingly, the CSPNet can reduce the number of inference calculations by about 20%. Meanwhile, the memory usage during the feature pyramid generation process can be reduced by up to 75%. e feature extraction network of YOLO v5s uses CSPDarknet53, and its network structure is shown in Figure 4. It should be indicated that CSPDarknet53 is based on the idea of Cross-Stage Partial Networks (CSPNet) to transform the Darknet53 network.
Since the safety rope may have different sizes in different images, the feature extraction network is required to perform the multiscale feature extraction process. In this regard, Feature Pyramid Network (FPN) [30], which is composed of the bottom-up pathway, top-down pathway, and lateral connections, can be applied to generate a high resolution containing low-level safety rope contour features with less semantic information and low resolutions containing highlevel safety rope texture feature with rich semantic information.
e bottom-up pathway is the feedforward calculation of the backbone network, which calculates the feature level composed of feature maps of multiple scales with a zoom step of 2.
e top-down pathway generates higher resolution features by upsampling spatially coarser but semantically more robust feature maps from higher pyramid levels, enhanced by horizontal connections. Each horizontal connection incorporates feature maps of the same size in the bottom-up path and the top-down path. For example, Figure 5  e cross-stage partial network (CSPNet) reduces the number of network calculations. However, the existence of a large number of CBL modules in the entire feature extraction network still increases the computational expense. In particular, there are 48 CBL modules in the YOLO v5s network structure. Meanwhile, each CBL module consists of a convolutional layer, a batch normalization (BN) layer, and an activation function (Leaky Relu). e BN layer can accelerate network convergence in the network training process. Moreover, it also increases the computational expense in the network forward inference process and affects   the model performance. Based on the CBL module, the BN layer is merged into the convolution layer to form a new BN-Conv layer to reduce the calculation of forwarding inference of the model. e BN layer is between the convolution layer and the activation function Leaky Relu. It converts each small batch of data into a standard Gaussian distribution with the zero mean and the variance of 1.
is can be mathematically expressed in the form below: Moreover, the BN layer can be expressed as follows: where ε, c, and β are the regularization parameter, scaling factor, and the offset term, respectively. en the convolutional layer can be written in the form below: where w i denotes the weight of the i-th layer. e BN-Conv layer is formed by merging the BN layer into the convolutional layer, where the weight parameter w i ′ and bias term β ′ can be calculated from the following expressions: Finally, the BN-Conv layer can be obtained from the following expression:

Prediction Network.
In the safety rope prediction network, three different scale feature maps of the feature extraction network are applied to generate prediction boxes and the corresponding category predictions. Accordingly, a unique prediction box can be obtained through the nonmaximum suppression (NMS). Furthermore, the loss function is an essential part of the model training process and the prediction network. It affects the convergence speed and the prediction error of the model. e loss function of YOLO v5s consists of three parts, including classification loss, confidence loss, and bounding box loss. It is worth noting that the bounding box loss function is a Generalized Intersection over Union (GIoU) [31], which is an evolutionary version of Intersection over Union (IoU).
IoU is the most commonly used indicator in target detection tasks. In anchor-based methods, the main role of IoU is to determine the positive and negative samples of the safety rope and evaluate the output box's distance to the ground-truth. IoU can be mathematically expressed in the form below: where A and B are the blue target box and yellow prediction box in Figure 6, respectively. Moreover, A ∩ B and A⋃ B denote the intersection and union of A and B, respectively. Equation (6) indicates that the definition of the IoU loss function is relatively simple. Further investigations reveal that this definition has two shortcomings: (1) when the target box and the prediction box do not intersect, equation (6) results in IoU � 0. However, this result cannot reflect the distance between the two boxes so that the loss function cannot be derived and optimized. (2) When the target boxes and the prediction boxes have the same size separately, as long as A ∩ B is constant, the corresponding IoU value is the same regardless of A and B relative position. Meanwhile, the IoU loss function cannot distinguish the intersection of the two boxes. In order to resolve these two shortcomings, the GIoU loss function has been introduced to the YOLO v5s.
where A c is the minimum area of the two boxes' enclosed area (the red box in Figure 7). Unlike IoU, which only considers overlapping areas, all areas are considered in GIoU. Accordingly, GIoU can better reflect the overlap degree between the two boxes. It is worth noting that when the prediction box is inside the target box, A c and A⋃ B are equal, and GIoU reduces into IoU, and their relative positional relationship cannot be distinguished. Although the foregoing shortcomings of the IoU loss function are resolved in the GIoU function, some other problems, including slow convergence and inaccurate regression [32], should be resolved. Accordingly, the Distance-IoU (DIoU) loss function is proposed in the present article to replace the GIoU loss function and resolve these problems.
where b and b gt are the center points of the prediction box and the target box, respectively. Moreover, ρ and c denote the Euclidean and the diagonal distance of the minimum closure area A c , respectively. In the DIoU function, the overlap area and the center point distance are considered simultaneously. When the target box wraps the prediction box, the distance between the two boxes is directly measured, so the DIoU loss function converges faster. In this regard, the black arrow in Figure 8 represents the diagonal distance c of the minimum closure area A c , and the red arrow Journal of Advanced Transportation represents the Euclidean distance between the center point of the prediction box and the center point of the target box In summary, the overlapping area and the distance between the center points of the two boxes are considered in the proposed DIoU loss function. is loss function is expected to improve the accuracy of the prediction box's regression and increase the convergence rate.

Dataset.
e training and testing result of the algorithm depends on the data set. However, no public crew safety rope data set is available for use. erefore, a self-made crew safety rope data set is created in this study. In this regard, two data sources, including the surveillance video onboard and web crawlers, have been prepared prior to the test. In total, 3,150 images and 6,583 targets are gathered in the dataset. After extracting images from the ship's surveillance video, some images including crew are screened out and labelled. en the labelled targets are divided into two categories, including safety harness with 1,250 images and dangerous cases with 1,900 pictures. During training the algorithm, the data set is divided into the training set, the validation set, and the test set at the ratio of 16 : 4:5. Figure 9 shows some images of the prepared dataset.

Evaluation Indicators and Experimental Platform.
e performance of the algorithm depends on the objective evaluation indicators. In the present article, precision, recall, mean average precision (mAP), and frame rate are considered as the primary performance evaluation indicators.
Precision and recall are used to evaluate the algorithm's accuracy in classifying the target and its capability to find the target. ese indicators are defined in equations (9) and (10), respectively. e distribution of the precision-recall rate (P-R) can be drawn by taking the recall rate as the X-axis and the precision as the Y-axis. Average precision (AP) is applied to calculate the area under the precision-recall (P-R) rate curve of a specific category. Moreover, the mean average precision (mAP) is used to calculate the average of the area under the P-R curve of all categories. It should be indicated that mAP reflects the average detection accuracy of all categories and can be used to evaluate the performance of the proposed DIoU loss function.
where TP (True Positive) refers to the number of positive classes predicted as positive, FP (False Positive) refers to the number of false positives that predict a negative class as a positive class, and FN (False Negative) refers to the number of false negatives that predict a positive class as a negative class.
All simulations are carried out on a personal PC with an Intel(R) Core(R) 7 @ 3.60 GHz CPU, 16G running memory, NVIDIA Geforce GTX1070 graphics card, CUDA v10.1 software, Window7 64-bit operating system, and Pytorch 1.7 deep learning framework.

Analysis of Experimental Results.
In order to evaluate the advantages of the proposed algorithm, obtained results are compared with those of the standard YOLO v5s, SSD, and EfficientDet algorithms on the same platform. Figure 10 shows sample results of the algorithm training process. It is observed that, after 250 iterations, the average loss value remains constant and approaches an asymptotic value, indicating rapid convergence of the algorithm. e precision-recall rate (P-R) curve in Figure 10(b) shows that, for the recall rate of 96%, the accuracy can reach 90%. Moreover, Figure 10 improved YOLO v5s. It is observed that the modified algorithm outperforms the bounding box loss from the aspects of convergence rate and regression accuracy.

Comparison with Standard Algorithms.
In order to verify the detection effect of the proposed algorithm, the detection results obtained from the standard YOLO v5s and the proposed YOLO-SD algorithms are compared. Table 1 shows that proposed YOLO-SD algorithm improves the accuracy, recall, and average accuracy. More specifically, the detection speed is increased by 7.3%.

Comparisons with Other Algorithms.
To further evaluate the performance of the proposed algorithm, the detection efficiencies of YOLO-SD, SSD, and EfficientDet [27] algorithms are compared. In this regard, the test results are presented in Table 2. It is observed that the SSD algorithm performs well, where the mAP value reaches 89.3%, but the detection frame rate in the SSD algorithm is only one-third that of the proposed YOLO-SD algorithm. Meanwhile, it is found that the EfficientDet-d0 algorithm has the highest detection speed, up to 59.30 fps, while that of the proposed YOLO-SD algorithm is 38.31 fps. However, mAP value of the YOLO-SD algorithm is much higher than that of the EfficientDet-d0 algorithm. It should be indicated that the EfficientDet-d1 algorithm has a higher mAP value than the EfficientDet-d0 algorithm, but there is still a remarkable gap with that of the proposed YOLO-SD algorithm. Moreover, it is found that the detection speed of EfficientDet is lower than that of the proposed one. Since the proposed YOLO-SD algorithm considers both the detection precision and detection speed, it can better complete the crew safety rope's detection task. Figure 11 shows some of the crew safety detection results. From left to right, the crew's distance and the camera become farther and the crew's imaging size gradually decreases. It should be indicated that each image has a different resolution. It is found that the SSD algorithm has one misdetection and two fraudulent detections. Moreover, the EfficientDet-d1 algorithm has four missing detections. Meanwhile, the proposed algorithm has only one misdetection. Table 3 indicates that the average confidence values of the SSD, EfficientDet-d1, and YOLO-SD algorithms are 78.33, 47.13, and 78.63, respectively. It is concluded that the proposed algorithm has the highest average confidence value and has the most concentrated distribution of confidence values. Meanwhile, it has the best detection stability in different image resolutions and target sizes and has a good detection effect. Accordingly, it is inferred that the proposed algorithm has good robustness. Figure 12 shows sample results of the surveillance video detection process. It is observed that the proposed YOLO-SD algorithm achieves good results in the detection process. Although the crew's back safety rope was partially obscured by the iron bar at certain moments (see Figure 12 Frame 350), YOLO-SD algorithm can still detect the safety rope.

Anti-Interference Test.
To evaluate the algorithm's detection stability, tests are conducted on images taken at different working conditions such as low-light, night, rainy, and foggy days. e obtained results are presented in Figure 13. To quantitatively analyse the anti-image pollution ability of the algorithm, Perlin Noise [33] is added to test images. It is worth noting that applying Perlin Noise is a widely adopted method to generate specific texture noises or augmentation data sets [34,35]. Figure 14 reveals that the test set images are polluted by 10%, 20%, 30%, 40%, 50%, and 60% coverage rates of Perlin Noise. e test results are shown in Table 4. It is found that when 40% noise is added to the original image, the decline of recall and mAP is less than 6%. Moreover, when the noise coverage increases to 50% and 60%, the corresponding drop of recall and mAP increases to 21% and 35%, respectively. However, the detection precision remains at a high level. Figure 15 shows the detection demo software based on the pyQt5 framework. A surveillance camera is used at the port to test the software's functions. When the start button is pressed, the program detects the crew in the surveillance video, marks the detected crew with a mark box, and records the detection information in the log box. en when a detected crew with no safety rope enters the surveillance area, an alarm will be issued to notify the supervisor.

5.4.
Discussion. An automatic system for identifying nonsafety-ropes-use provides an effective means to reduce the risk of falling and improve safety issues in a ship's high-  altitude operations. e main objective of the present article is to employ the target recognition method to detect whether the safety rope is worn or not. In this regard, extensive experiments on the self-built dataset have been carried out, which demonstrate the effectiveness of the proposed method.
It is found that CNN-based safety ropes wearing detection methods are reliable and stable in a wide range of on-site conditions such as visual range, individual posture, and occlusions. rough a series of improvements to the original algorithm, the YOLO-SD algorithm has improved the mAP (91.5% vs. 89.1%). To apply the new BN-Conv modules, the network inference speed increases by 7.3% (38.31 fps vs. 35.71 fps). Experimental results show that, for the same training and testing dataset, the proposed YOLO-SD algorithm outperforms the SSD method by 8.8% (97.4% vs. 89.5%) in the detection precision and 312.4% (38.31 fps vs. 9.29 fps) in the detection speed. Moreover, the SSD model has a larger weight file and a larger parameter amount so that it requires more memory space and more powerful equipment. Further investigations show that the proposed YOLO-SD algorithm is slower than the EfficientDet-d0 algorithm (38.31 fps vs. 59.30 fps) and faster than the EfficientDet-d1 algorithm (38.31 fps vs. 26.93 fps). However, the mAP value of the YOLO-SD algorithm is significantly higher than that of EfficientDet-d1 (91.5% vs. 48.0%) and EfficientDet-d0 (91.5% vs. 15.2%) algorithms.      Figure 11.
Method Figure 11(a) Figure 11(b) Figure 11(c) Figure 11(d) Figure 11 Note. e SSD algorithm incorrectly detects the crew on the right side of Figure 11(b), and the crew has two wrong classification boxes.     Real-time detection screen Log Figure 15: Detection demo software.

Conclusion
In the present study, an algorithm is designed to resolve shortcomings of the manual supervision of safety rope wearing in ship operation sites and has high detection accuracy and speed under different resolutions and target sizes. e performed experiments show that, compared with the state-of-the-art target detection algorithms, the YOLO-SD algorithm has a good detection effect, while it is robust in real time. e present article is only focused on the accuracy and speed problems in the detection process of crew safety rope wearing and has not researched algorithm transplantation to artificial intelligence chip or edge computing device.

Data Availability
Some or all data, models, or codes that support the findings of this study are available from the corresponding author upon reasonable request.

Conflicts of Interest
e authors declare that they have no conflicts of interest.