Сегментация облака точек по Т. Раббани

Обратный инжиниринг — это процесс восстановления геометрической модели изделия из дискретного представления, например, облака точек или триангуляции.

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

Реконструкция начинается с сегментации — выделения порций облака точек (триангуляцию мы здесь не рассматриваем), из которых будут создаваться отдельные геометрические примитивы.

Для реконструкции крупных индустриальных объектов широко применяется алгоритм сегментации Тахира Раббани [Rabbani et al. 2006], в котором облако точек размыкается на компоненты сообразно т.н. «критерию гладкости». Идея состоит в том, чтобы обеспечить грубое разбиение начального облака на сегменты так, чтобы они оказались по возможности крупнее любого гладкого конструктивного элемента модели. На деле алгоритм сегментации состоит в добавлении все новых и новых точек в формируемый сегмент на основании поведения вектора нормали в каждой точке-кандидате. Если нормаль изменяется незначительно, то окрестность точки считается достаточно гладкой для прирастания региона этой точкой. Собственно алгоритм, реализующий этот подход, так и называется: «разрастание регионов» (region growing).

Для реализации алгоритма Т. Раббани нам потребуется, очевидно, метод конструирования нормалей в облаке точек. Метод состоит в построении приближающей плоскости для окрестности данной точки. Это задача линейной аппроксимации, которая сводится к отысканию собственных значений матрицы ковариации, как описано в работе Хоппа [Hoppe et al. 1992].

Для линейного приближения окрестности данной точки эту окрестность еще надо суметь получить. Здесь на помощь приходят k-d деревья, причем на практике себя отлично показывает библиотека FLANN [Muja and Lowe 2014], реализующая быстрый приближенный поиск соседей.

Алгоритм разрастания регионов начинается с выбора стартовой точки и продолжается вплоть до исчерпания облака. Стартовая точка порождает окрестность, в которой может найтись новая стартовая, чем и обеспечивается разрастание из локальной окрестности в глобальный регион.

Следующая точка становится новой стартовой, если выполняется «критерий гладкости» (т.е. нормаль незначительно отклоняется от начального направления) и невязка линейного приближения (т.е. расстояние до плоскости, аппроксимирующей окрестность) не превосходит заданную эмпирическую величину.

Пороговые значения для углового отклонения и линейной невязки подбираются под задачу, исходя из зашумленности входных данных. На идеальном облаке (полученном сэмплированием геометрической модели без имитации шума) можно получить вполне адекватные результаты сегментации, если принять во внимание еще одно замечание. Дело в том, что «критерий гладкости», очевидно, не соблюдается на ребрах предполагаемой модели, т.к. поле нормалей в таких зонах терпит разрыв. Кроме того, линейная аппроксимация острого края не может быть адекватной, т.к. окрестные точки начинают располагаться как попало.

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

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

1. [Hoppe et al. 1992] HOPPE, H., DEROSE, T., DUCHAMP, T., MCDONALD, J., AND STUETZLE, W. 1992. Surface reconstruction from unorganized points. ACM SIGGRAPH Computer Graphics 26, 2, 71–78.


2. [Muja and Lowe 2014] MUJA, M. AND LOWE, D.G. 2014. Scalable Nearest Neighbour Algorithms for High Dimensional Data. IEEE Transactions on Pattern Analysis and Machine Intelligence 36, 11, 2227-2240.


3. [Rabbani et al. 2006] RABBANI, T., VAN DEN HEUVEL, F. A, AND VOSSELMAN, G. 2006. Segmentation of point clouds using smoothness constraint. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences - Commission V Symposium "Image Engineering and Vision Metrology" 36, 5, 248-253.


4. [Rusu and Cousins 2011] RUSU, R.B. AND COUSINS, S. 2011. 3D is here: point cloud library. IEEE International Conference on Robotics and Automation, 1-4.