Разработка и исследование алгоритмов автоматического взаимного ориентирования трехмерных дискретных моделей объектов, полученных в результате лазерного сканирования тема диссертации и автореферата по ВАК РФ 25.00.34, кандидат технических наук Велижев, Александр Брониславович

• Велижев, Александр Брониславович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Велижев, Александр Брониславович

Введение.

1. Обзор методов взаимного ориен гирования дискретных точечных моделей.

1.1 Введение.

1.2 Итеративный алгоритм ближайшей точки.

1.3 Получение начальных приближений.

1.4 Выбор точек для поиска соответствий.

1.5 Выбор пространства поиска соответствий.

1.6 Поиск соответствий.

1.7 Минимизация.

1.8 Выводы.

2. Определение элементов взаимного ориентирования дискретных точечных моделей с помощью ориентационных гистограмм.

2.1 Введение.

2.2 Построение восьмеричного дерева.

2.3 Построение ориентадиониой гистограммы.

2.4 Сравнение ориентационных гистограмм, оценка угловой ориентации.

2.5 Построение воксельного представления дискретной точечной модели.

2.6 Сравнение воксельных представлений дискретных точечных моделей методом Фурье анализа.

2.7 Выводы.

3. Описание алгоритма автоматической взаимной ориентации дискретных точечных моделей.

3.1 Введение.

3.2 Чтение файла данных с координатами точек двух точечных моделей.

3.3 Определение пространственных границ каждой точечной модели.

3.4 Рекурсивное построение восьмеричного дерева для каждой точечной модели

3.5 Вычисление нормалей и фильтрация точек.

3.6 Вычисление матрицы ориентацпонной гистограммы.

3.7 Оценка угловых параметров взаимной ориентации точечных моделей.

3.8 Выравнивание угловой ориентации точечных моделей.

3.9 Построение воксельного представления каждой точечной модели.

ЗЛО Оценка вектора сдвига и линейное выравнивание точечных моделей.

3.11 Сохранение второй развернутой точечной модели в файл.

3.12 Описание тестовых данных.

3.13 Результаты автоматического взаимного ориен тирования.

3.14 Визуализация дискретных точечных моделей.

3.14.1 Обратное движение точек.

3.14.2 Динамическая визуализация точечных моделей.

3.14.3 Результаты работы алгоритма визуализации точечных моделей.

3.15 Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование алгоритмов автоматического взаимного ориентирования трехмерных дискретных моделей объектов, полученных в результате лазерного сканирования»

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

Математическим и методическим аспектам обработки данных лазерного сканирования посвящено сравнительно небольшое количество научных работ российских и зарубежных ученых. Стоит отметить, что значительный вклад в разработку данной научной темы внесли российские ученые кандидат технических наук Михайлов А.П., доктор технических наук Журкин И.В., а также и зарубежные ученые Бесл, П.Дж. и МакКей Н.Д.

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

Сформулируем задачу взаимного ориентирования дискретных точечных моделей. Дискретной точечной моделью объекта Р будем называть набор из N трехмерных точек, расположенных произвольно на поверхности объекта в единой произвольно ориентированной в простраичтве системе координат. Пусть Р( и Рг-две различные точечные модели одного объекта, описывающие поверхность с некоторым перекрытием.

Любую точку Р[ можно перевести в систему координат Р? используя уравнение:

3д1 ,г3 3.xI Зг| где Т - вектор переноса иЕ- матрица поворота между системами координат точечных моделей Р| и Рч, р1 - произвольная точка из Р|, /?, - координаты точки в системе координат Р2. Пусть N1 и N2 - число точек в точечных моделях Р| и Ро.

Таким образом, решение задачи взаимного ориентирования дискретных точечных моделей сводится к отысканию значений грех углов ам, оом, км. входящих в магрицу поворота Л, и трех координат Х0, У0, задающих вектор переноса Т.

В данной работе предлагается автоматическая методика о гыскания значений К и Т без знания каких-либо начальных значений параметров взаимной ориентации точечных моделей (Х0, У о, ¿о, <*м, <»м, км).

Первая глава диссертации посвящена анализу существующих методов решения задачи взаимной ориентации точечных моделей. Во второй главе рассмотрена предлагаемая автором методика решения задачи ориентации. Третья глава посвящена анализу и оценке результатов решения задачи предложенным методом.

Заключение диссертации по теме «Аэрокосмические исследования земли, фотограмметрия», Велижев, Александр Брониславович

3.15 Выводы

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

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

Заключение

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

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

В диссертационной работе решены следующие задачи:

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

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

3. Создано соответствующее программное обеспечение, позволяющее решить задачу автоматического взаимного ориентирования моделей по предложенной методике.

4. Выполнены многочисленные экспериментальные исследования предложенной методики автоматического ориентирования дискретных точечных моделей. Результаты исследования показывают высокую эффективность и надежность решения задачи.

Разработано программное обеспечение, позволяющие быстро и качественно визуализировать дискретные модели из десятков миллионов точек.

Список литературы диссертационного исследования кандидат технических наук Велижев, Александр Брониславович, 2008 год

1. Arun, K., Huang, Т., and Blostein, S. "Least-Squares Fitting of Two 3-D Point Sets," Trans. PAMI, Vol. 9. No. 5, 1987

2. Benjemaa. R. and Schmitt, F. "Fast Global Registration of 3D Sampled Surfaces Using a Multi-z-Bufter Technique," Proc. 3D1M, 1997

3. Bentley. J.L. Multidimensional binary search trees used for associative searching. Comm. of the ACM. 18(9). 509-517, 1975

4. Besl, P.J. and McKay, N.D. 1992. A method for registration of 3D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14 (2), pp. 239-256.

5. Besl, P. J., and McKay, N.D. A method for registration of 3D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14 (2), pp. 239-256, 1992

6. Bohm, .1., Becker S„ Automatic Marker-Free Registration of Terrestrial Laser Scans using Reflectance Features. In: Proceedings of 8th Conference on Optical 3D Mcasurment Techniques, Zurich, Switzerland, July 9-12, pp. 338-344, 2007

7. Boubekeur Т., Reuter P., Schlick C., Surfel Stripping, ACM Graphite, 2005

8. Boubekeur Т., Heidrich W., Granier X., Schlick C., Volume-Surface Trees, Computer Graphics Forum (Proceedings of EUROGRAPHICS), Volume 25, Number 3, page 399406. 2006

9. Brinkhoff, Т., Spatial access methods for organizing laserscanner data. IAPRS, 35(B4), pp. 98-102,2004

10. Chen, Y., and Medioni, G., Object modelling by registration of multiple range images. Image and Vision Computing, 10(3), pp. 145-155, 1992

11. Chetverikov D., Stepanov D., Krsek P., Robust Euclidean alignment of 3D point sets: the Trimmed Iterative Closest Point algorithm. Im. and Vis. Сотр. 23, 3, 299-309, 2005

12. Dold, C. and Brenner, C., Automatic Matching of Terrestrial Scan Data as a Basis for the Generation of Detailed 3D City Models, 2004

13. Dold, C., Extended Gaussian images for the registration of terrestrial scan data, ISPRS WG III/3, III/4, V/3 Workshop "Laser scanning 2005". Enschede, the Netherlands, September 12-14, 2005

14. Godin, G., Rioux, M., and Baribeau, R., "Three-dimensional Registration Using Range and Intensity Information," Proc. SPIE: Videometries III, Vol. 2350, 1994

15. Godin, G., Laurendeau, D. and Bergevin. R., A method for the registration of attributed range images. 3DIM. Quebec, pp. 179-186, 2001

16. Eggert, D.W., Fitzgibbon. A.W. and Fisher, R.B. Simultaneous registration of multiple range views for use in reverse engineering of CAD models. CVIU, 69(3). 253-272, 1998

17. Feldmar J., N.J. Ayache, Rigid, affine and locally affine registration of free-form surfaces. International Journal of Computer Vision, No. 2, May, pp. 99-119, 1996

18. Fischler, Bolles, "RANdom SAmpling Consensus: a paradigm fro model fitting with application to image analysis and automated cartography" Comniun.Assoc.Comp. Mack. :381-95, 1981

19. Greenspan, M., and Godin, G., A nearest neighbor method for efficient ICP. 3DIM, Quebec, pp. 161-168,2001

20. Gobbetti E., Marton F. Layered point clouds, in: Proc. Eurographics Symposium on Point Based Graphics, pp. 113-120,227, 2004

21. Hansen, W., Registration of Agia Sanmarina Lidar Data Using Surface Elements. ISPRS Workshop on Laser Scanning 2007 and SilviLaser 2007, Espoo, September 12-14, 2007

22. Isenburg M., Gumhold S., Out-of-Core Compression for Gigantic Polygon Meshes. Proceedings of SIGGRAPH'03, pages 935-942, July, 2003

23. Jackins C. L., Tanimoto S. L., Quad-trees, oct-Uees, and k-trees. A generalized approach to recursive decomposition of Euclidean space, EEE Trans. Pattern Anal. Machine Intell, vol. PAMI-5, pp. 533-539, 1983

24. Johnson, A. and Hebert, M., '"Surface Registration by Matching Oriented Points," Proc. 3DIM, 1997

25. Johnson 97 II. Johnson A.E. S.B. Kang, '"Registration and integration of textured 3-D data", Proc. Int. Conf. on Recent Advances in 3-D Digital Imaging and Modeling, Ottawa, Canada, May 12-15. pp. 234-241, 1997

26. Jokinen, O., and Ilaggren, H., Statistical analysis of two 3-D registration and modeling strategies. ISPRS Journal of Photogrammetry & Remote Sensing, 53(6), 320-341, 1998

27. Horn, B., "Closed-Form Solution of Absolute Orientation Using Unit Quaternions," JOSA A, Vol. 4, No. 4, 1987

28. Horn B., Extended gaussian images, Proc. IEEE, A.I. Memo No. 740. Vol. 72(12), pp. 1671-1686, 1984

29. Horn, B., Hilden, H., and Negahdaripour, S., "Closed-Form Solution of Absolute Orientation Using Orthonormal Matrices," JOSA A, Vol. 5, No. 7, 1988

30. Kang Z., Zlatanova S., Gorte B., Automatic Registration of Terrestrial Scanning Data Based on Registered Imagery, Proceedings FIG Working Week, May, Hong Kong, pp. 11,2007

31. Kwang-Ho Bae, D. D. Lichti. Automated Registration Of Unorganised Point Clouds From Terrestrial Laser Scanners, 2004

32. Lowe D.G. Distinctive image features from scale-invariant key points, International journal of computer vision, 60(2):9l-l 10, 2004

33. Masuda, T., Sakaue, K., and Yokoya, N. "Registration and Integration of Multiple Range Images for 3-D Model Construction," Proc. CVPR. 1996.

34. Neugebauer. P.J., Reconstruction of real-world objects via simultaneous registration and robust combination of multiple range images. Int. J. of Shape Modeling, 3(1-2), 71-90, 1997

35. Nishino K.,. Ikeuchi. K., "Robust simultaneous registration of multiple range images," The 5th Asian Conf. on Computer Vision (ACCV2002), 23-25, 2002

36. Pajdla T. and L. Van Gool, Matching of 3-D Curves using Semi-differential Invariants. In 5th International Conference on Computer Vision, pages 390-395. 1995

37. Park, S.Y., Subbarao, M., A fast point-to-tangent plane technique for multi-view registration. IEEE International Conference on 3D Digital Imaging and Modeling, Banff, October 6-10, pp. 276-283, 2003

38. Pulli fC, "Multiview registration for large data sets." Proc. Of 2nd Intn. Conf. on 3D Digital Imaging and Modeling, 1999

39. Rabbania T„ vail den Heuvelb F. A., Vosselman G., Segmentation of point clouds using smoothness constraint, IAPRS Volume XXXVI. Part 5, 2006

40. Ripperda, N., Brenner, C., "Marker-Free Registration of Terrestrial Laser Scans Using the Normal Distribution Transform", Proceedings of the ISPRS Working Group V/4 Workshop VOLUME XXXVI, PART 5/W17, 2005

41. Rusinkiewicz, S., and Levoy. M., Efficient variants of the ICP algorithm. IEEE International Conference on 3D Digital Imaging and Modeling, Quebec, May 28 June l,pp. 145-152,2001

42. Sankaranarayanan, .1., Samet, H., Varshney, A., A fast all nearest neighbor algorithm for applications involving large point-clouds. Computers and Graphics, 31,2 (Apr. 2007), 157-174, 2007

43. Sharp, G. C. Lee. S.W. and Wehe, D. K., ICP registration using invariant features. IEEE Transactions on Pattern Recognition and Machine Intelligence 24(1), pp. 90-102, 2002

44. Simon, D., Fast and Accurate Shape-Based Registration. PhD thesis, Robotics Institute, Carnegie Mellon University, 1996

45. The Stanford 3D Scanning Repository, электронный ресурс., http://graphics.stanford.edu/data/3Dscanrep

46. Turk. G., and Levoy. M., Zippered polygon meshes from range images. In: A. Glassner (ed.), Proceedings of SIGGRAPH'94. Florida. July 24-29, pp. 311-318, 1994

47. Umeyama S., "Least-Squares Estimation of Transformation Parameters Between Two Point Patterns." IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 4, pp. 376-380, Apr. 1991

48. Vanden Wyngaerd, J., Van Gool, L. Koch, R., and Proesmans, M., Invariant-based registration of surface patches. IEEE International Conference on Computer Vision, Kerkyra, September 20-27, pp. 301-306, 1999

49. Weik, S. "Registration of 3-D Partial Surface Models Using Luminance and Depth Information," Proc. 3DIM, 1997.

50. Walker, M., Shao, L., and Volz, R., "Estimating 3-D Location Parameters Using Dual Number Quaternions," CVGIP: Image Understanding, Vol. 54. No. 3, 1991

51. Zhang, Z., Iterative point matching for registration of free-form curves and surfaces. International Journal of Computer Vision, 13 (2). pp. 119-152, 1994

52. Чнбуннчев А.Г., Велижев А.Б., Автоматическое определение взаимной ориентации трехмерных моделей объектов, полученных по результатам лазерного сканирования, «Геодезия и аэрофотосъемка», Москва, 2007, № 1, стр. 127-134.

53. Чибуничев А.Г., Велижев А.Б., Автоматическое сопоставление облаков точек, полученных в результате наземного лазерного сканирования, с использованием ориентационных гистограмм, «Геодезия и аэрофотосъемка», 2008, Москва, №3, стр. 112-119

54. Велижев А.Б., Визуализация результатов лазерного сканирования, "Инженерные изыскания", 2008, №2, стр. 94-95

55. Комиссаров А.В., 2007. Методика исследования метрических характеристик сканеров, автореферат диссертации на соискание ученой степени кандидата технических наук, Новосибирск

56. Жигалов К.Ю., Векторизация и конвертация данных лазерной локации в ГИС-технологиях, автореферат диссертации на соискание ученой степени кандидата технических наук, Москва, 2007

57. Волкович Е.В., Разработка технологии получения электронных крупномасштабных планов сложных инженерных сооружений по результатам наземной лазерной съемки, автореферат диссертации на соискание ученой степени кандидата технических наук, Москва, 2007