A Fast Graph-Based Data Classification Method with Applications to 3D Sensory Data in the Form of Point Clouds

Data classification, where the goal is to divide data into predefined classes, is a fundamental problem

in machine learning with many applications, including the classification of 3D sensory data. In this

paper, we present a data classification method which can be applied to both semi-supervised and

unsupervised learning tasks. The algorithm is derived by unifying complementary region-based and

edge-based approaches; a gradient flow of the optimization energy is performed using modified auction

dynamics. In addition to being unconditionally stable and efficient, the method is equipped with

several properties allowing it to perform accurately even with small labeled training sets, often with

considerably fewer labeled training elements compared to competing methods; this is an important

advantage due to the scarcity of labeled training data. Some of the properties are: the embedding of

data into a weighted similarity graph, the in-depth construction of the weights using, e.g., geometric

information, the use of a combination of region-based and edge-based techniques, the incorporation

of class size information and integration of random fluctuations. The effectiveness of the method is

demonstrated by experiments on classification of 3D point clouds; the algorithm classifies a point

cloud of more than a million points in 1-2 minutes.