7. Multi-Dimensional Regular Expressions for Object Detection with LiDAR Imaging

Regular expressions are a fundamental technique for pattern matching in textual data and for lexical analysis in compiler design. They are ubiquitous in most systems used today, including operating systems (e.g. grep, awk), computer languages (e.g. Perl, Java, Python), and web search engines (e.g. Google). However, this highly useful way of exploring and mining data has thus far eluded non-textual datasets, such as images and 3D geometric data. Shape-based searching of 3D objects continues to be a core problem in computer vision. We propose a novel extension of traditional finite-automata-based methods to find multi-dimensional objects in spatial data sets. Our approach extends regular expressions and finite automata to multi-dimensional pattern models. While we demonstrate the effectiveness and efficiency of our approach for finding target objects in 3D LiDAR image data sets using an implicit geometry representation of the data, it is important to note that the proposed technique can be applied to any general data set of vertices in 3D space. Non-geometric information, such as material and spectral characteristics from hyperspectral image data can also be discretized and encoded into our approach.