Avvir использует широкий спектр статистических моделей для автоматического обнаружения отклонений между зданиями в том виде, в каком они спроектированы и построены. Но прежде чем мы начнем настраивать и тестировать эти модели, мы должны решить, как представить наши данные.

Обычно мы хотим изобразить точки интереса в некотором метрическом пространстве. Почти во всех случаях мы используем трехмерное евклидово расстояние, но следующие методы можно применить к любому метрическому пространству. Например, можно использовать расстояние Махаланобиса, которое искажает пространство на основе измеренной ковариации распределения точек, или расстояние Манхэттена, чтобы установить приоритет согласования с выбранной системой координат.

Понятие «достопримечательности» также довольно общее. В простейшем случае это означает неупорядоченный набор трехмерных векторов размером n. В просторечии это называется «облаком точек», поскольку оно напрямую не представляет никаких отношений между точками, а только сами точки:

Чтобы представить простые пространственные отношения, мы можем вычислить расстояния между каждой парой точек в соответствии с выбранной нами метрикой расстояния и поместить результаты в симметричный n -by- n матрица:

Мы можем сделать еще один шаг вперед, разбив матрицу, чтобы найти локальные окрестности каждой точки, а затем преобразовав ее в двоичную форму, чтобы сформировать простой граф ближайших соседей. Эта структура является основой для нескольких полезных непараметрических моделей прогнозирования, но имеет важный и особенно поучительный недостаток.

Поскольку большинство пар точек расположены слишком далеко друг от друга, чтобы их можно было считать сильно связанными, мы обычно устанавливаем порог бинаризации в районе менее нескольких десятков. Это делает матрицу смежности разреженной, что означает, что большинство ее элементов являются нулевыми. Для облака точек порядка 10 миллионов точек этот формат может быть очень неэффективным с точки зрения вычислений. Практики обычно используют такие структуры, как kd-деревья и матрицы CSR, чтобы уменьшить временную и пространственную сложность этой структуры с O (n²) до O (n), но тот факт, что проблема масштабируется с помощью количества точек, а не протяженности пространства, должен привлечь наше внимание.

Если мы квантовываем пространство в 3-мерные ячейки и отслеживаем количество точек в каждой ячейке, то размер структуры будет постоянным по количеству точек. Кроме того, пространственное расположение точек теперь запекается в структуре. Это делает его идеальным для функций, которые независимо работают с локальными окрестностями точек, например Сверточные и морфологические операции. Такую структуру данных обычно называют сеткой вокселей (vo- для объема и -el для элемента).

Сетки вокселей все еще имеют потенциальный недостаток разреженности из-за неоднородности выборки. Фактически, с точки зрения объема, здания состоят в основном из пустого пространства. С разреженностью можно бороться, сегментируя точки на более плотные окрестности перед их раздельным объединением, но суть в том, что объем может быть не лучшим термином для описания выравнивания элементов здания. Вместо этого понятие поверхностей на границах облаков точек может быть более точным.

Каждое облако точек имеет уникальную выпуклую оболочку, которая представляет собой наименьшее выпуклое множество, содержащее облако точек. В трехмерном пространстве выпуклая оболочка представляет собой многогранник, вершины которого являются ограничивающими элементами. Эта структура данных имеет преимущество в том, что она в целом более компактна, чем облако точек, и ее грани могут быть равномерно дискретизированы, если желательны более плотные или более однородные облака точек. Также существуют эффективные алгоритмы для вычисления пересечения двух таких многогранников, которые представляют собой выпуклый многогранник, площадь поверхности и объем которого коррелируют с выравниванием двух объектов.

Я не описывал здесь какие-либо из наших дискриминационных моделей, но приведенные выше структуры данных являются основой для функций, которые мы извлекаем и вводим в такие модели. Надеюсь, что заинтересованный практик получит представление о преимуществах и недостатках этих структур и сможет разработать более полезные функции для своих собственных целей.

Джон Кил - ведущий инженер по машинному обучению в Avvir