Акимишин О.И. Методы и средства уменьшения объемов данных триангуляционного описания объектов компьютерной томографии. – Рукопись.
Диссертация на соискание учёной степени кандидата технических наук по специальности 05.13.05 – компьютерные системы и компоненты. Национальный университет "Львовская политехника", Львов, 2008.
Диссертация посвящена вопросам уменьшения объемов данных для представления объектов компьютерной томографии триангуляционными сетями. Предложенный метод позволяет уменьшение объемов данных и сохранение геометрической формы объектов в пределах заданного отклонения. Разработано графы алгоритмов и структуры устройств для выполнения основных операций уменьшения объемов данных. На основании анализа триангуляционного описания объектов предложено метод разделения триангуляции на отдельные элементы, что дало возможность ускорить обработку данных и на основе предложенного в работе метода разработать базовую структуру аппаратных ускорителей уменьшения объемов данных. Результаты экспериментов с использованием предложенного метода уменьшения объемов данных показали высокую эффективность на реальных изображениях компьютерной томографии.
Ключевые слова: компьютерная томография, триангуляционные сети, выделение объектов изображений, графы алгоритмов, реконфигурируемые аппаратные ускорители.
O.I. Akymyshyn Methods and facilities of data reduction of triangular mesh description of computed tomography objects. – Manuscript.
Thesis for a candidate's degree in technical sciences in speciality 05.13.05 – Computer systems and components. Lviv Polytechnic National University, Lviv, 2008.
The thesis is dedicated to task solving of reduction amount of data in computed tomography object representation. Computed tomography provides non destructive, three-dimensional characterization and visualization of features within the interior of solid objects. Typically for visualization and post-processing a computed tomography 3D objects are represented by triangular meshes, which often are too huge to be effectively processed. Moreover the object description by regular triangular mesh is redundant, because simple flat region of object surfaces are described by hundreds of thousands of triangles, when they can be represented by a few triangles without the loss of the object geometrical shape quality. Therefore the data reduction of computed tomography 3D object triangular description before their analysis and processing is a important task.
The review of known data reduction methods of triangular mesh and their comparative analysis is carried out. It has been found out that most of the methods provide the reduction of data up to the user's specified number of triangles instead of the user's defined deviation, as computed tomography objects must be represented.
The method that provides the amount of data reduction of a computed tomography object representation with a guaranteed error tolerance of the object geometrical shape has been proposed. The software based on the proposed method is developed and its efficiency on real 3D computed tomography objects is investigated. The results of the method have been compared with the state-of-the-art data reduction methods, including the Mesh Decimation method (MD) and method based on Quadric Error Metric (QEM) numerically, visually and in terms of execution times to strengthen the efficiency and quality of the method. The developed method allows 1.2 times greater reductionamount of data than the MD method with a zero deviation of object geometrical shapes, allows to generate high quality approximation of objects and it is 1.9 times faster than the QEM method.
The basic processing operations of data reduction methods, including normal computation, plane coefficients definition and vertex-plane distance computation, have been singled out and their hardware-oriented algorithms have been developed. It allows to define the structures of the computational devices for data reduction of triangular mesh representation based on the proposed methods. Based on the analysis of data processing performance it has been determined that the stream data processing is the most suitable.
The method of triangulation partitioning into separated processing elements is developed. The separated elements are independent blocks of data, when geometrical changes in one block do not require changing in the other. The proposed method is verified on test objects. It allows partitioning the input triangulation into separated blocks of data to their stream, parallel or pipeline processing. The algorithm of stream data processing based on proposed method has been developed.
The basic structures and functioning principles of the reconfigurable hardware accelerators of data reduction of object triangular representation have been developed. The VHDL-model of the accelerators has been designed and their characteristics have been examined.
The results of numerical experiments of the proposed data reduction method of computed tomography object triangle representation have shown the effectiveness of the method. The results were used in SME “Intron” for the development of the data reduction unit of the Non-Destructive Testing Software System for X-Ray 3D Computed Tomography (NDTS System) for flaw detection in solid objects according to computed tomography data. The results allow 50-90% amount of data reduction depending on object geometrical shapes.
Key words: computed tomography, triangular mesh, object detection, graph of algorithm, reconfigurable hardware accelerators.