Using the Minimum Spanning Tree to recognize dotted and dashed curves

An important problem in pattern recognition is the organization into two and three-dimensional space curves of data given as points ("dots") or short line segments ("dashes"). This paper describes a general method for recognizing such dotted or dashed space curves employing the Minimum Spanning Tree (MST). The use of the MST is motivated by its successful use in grouping two-dimensional point sets in a fashion closely resembling human visual perception. The extension of the method to handle "dashed" curves requires only the definition of a closeness measure between dashes which reflects the directional information as well as positional. It is possible to use the method in a layered hierarchy where the MST of dots is used to detect dashes, the MST of dashes to detect short curves without inflexions, and an MST constructed from these curves is used to detect larger curves with possible inflexions. The method described will be exemplified by its use to recognize particle tracks in streamer chamber photographs.