Vinokurov Alexey 

DonNTU | Master's portal

RUS | UKR | ENG

• Biography

Summary of research and developments

Urgency of a theme of research

Recently increasing interest to problems of classification of three-dimensional clouds of points is observed. Algorithms of classification are used in pattern recognition systems. Similar systems are successfully applied in various areas of a science and a life. In the lead positions in such researches occupy the USA, Japan and the countries in the European Union. In Ukraine and the near abroad countries such technologies yet have not received a wide circulation.

Briefly we will describe usages of systems of recognition of three-dimensional models and applied algorithms of classification of three-dimensional clouds of the points describing these models. Similar technologies are used for solution of a wide spectrum of geodetic tasks (for example, creation and recognition of three-dimensional models of a surface of the earth and objects of the difficult geometrical form). Successful developments in the field can find application in such branches of medicine, as oncology, X-rays, a computer tomography, ultrasonic research. Also systems of recognition of three-dimensional scenes and decision-making, enough exact are actual to provide safe automatic control of the car on certain sites of road (a motorway, a known site of road, avenue) . Algorithms of classification are necessary in biometric technologies of identification of the person which are used in modern systems of safety. Detailed documenting of an actual state of objects or a situation, in which they have been detected (for example, at archaeological excavations), is the main and natural reception in any research project in history or culture area. Especial interest to three-dimensional digital saving of objects in the field of culture is swept up in restoration areas (compilation exact and suitable for application virtual representations and models of objects for planning of reconstruction of monuments of culture unique or subject to protection) and archaeology, paleontology, partially in connection with projects of virtual museums. Experts in the field of art criticism can apply algorithms of classification to recognition of distinctive features of the cultural object (age, the country, style etc.) . Including, the identification of the stolen works of art, described in a special database as a cloud of points is possible.

The operation purpose

Research of algorithms of classification of three-dimensional clouds of points. The tasks linked to the purpose are reduced, first, to the direct analysis of algorithms of classification, secondly, to search of possible optimisation of these algorithms, thirdly, to formalising of theoretical base and, fourthly, to program implementation of algorithm in language CUDA.

Prospective scientific novelty

Enough wide circulation was received by the task of visualisation of three-dimensional clouds of points, the set of algorithms and methods is developed for effective solution of the given problem. As to recognition the researches spent in this sphere are much smaller. In given master’s work search of existing algorithms of classification is planned, including application possibility in this area of the algorithms used for visualisation, their analysis and working out, more effective, rather than existing, a method is considered. Improvements of speed and working capacity of algorithm it is planned to reach at the expense of application of deparallelizing by means of use of resources of graphic processors.

Approaches to the decision

There are two essentially different lines of thought to the decision of a problem of classification of three-dimensional clouds of points – methods in which basis the principle of deformation of an initial cloud to reference and cloud interpolation by three-dimensional splines has laid down.

Mathematical bases of deformable models represent set of geometry, physics and the approach theory. The geometry serves for display of the form of object, the physics limits frameworks in which the form can change in time and space, and the theory of optimum approximation formally proves requirements to devices which serve for reduction of models in conformity with the data of measurements.

At the heart of deformation models the problem a parity of contours lies. It is known in the English-speaking literature as “matching”. This problem breaks up to two directions: a marking (labelling) – a parity to a contour, received from a cut, with a contour taken from model; registration (registration) – a parity of the contours received from two different cuts. The decision of the above-stated problems is usually carried out by construction of the structured description of contours and the subsequent "elastic" parity of descriptions. Description structurization is understood as search in a contour of characteristic points, elementary curve and other elements which will be compared between two contours." Elastic "the parity is under construction on the basis of a method of" deformation models ”(deformable models), known also under the name“ the geometrical deformed contours ”. The two-dimensional variant of this method has received the name"snake"(snake). The essence of the given method consists that the contour or its element tests iterative deformation until will reach the greatest possible conformity with other corresponding contour or an element. Change surfaces (deformation) occurs recognising that a required contour tests changes under the influence of two energies: internal and external. On each step of algorithm the contour for which present balance of energies that is the minimum deformation is found. Specification occurs until the criterion of conformity required and reference to a contour will be reached. One more of techniques of comparison of two clouds is the method of construction of surface splines and a further statistical analysis of coefficients of the received polynomial three-dimensional functions.

As interpolating name definition of value of function for intermediate values of argument. It is possible to assume that the schedule of change of function on one step well enough is approximated by a chord, connecting two adjacent point. In practice this condition is fulfilled no means always. The result will be more exact if through the set points to spend a curve, smoother (fig. 2.3) without breaks. Then y (x) for value x=x it will be possible to consider value of function simply from the schedule. Certainly, such way of interpolating leans more likely against intuition, than on the strict mathematics, but, nevertheless, it is better, than linear interpolating. Especially good result will be received in case of application of functional scales when the dependence curve y from x is straightened.

In case function sort y (x) is known, but its parameters interpolating can be strict mathematical operation are unknown only.

The algorithm of matching by construction of deformation models is fulfilled long enough: for each point of a recognised cloud energy from which in it each point of a standard cloud will be deformed settles up. An initial cloud make n points, and standard – m. If to assume that n it is approximately equal m complexity of algorithm can be estimated, as O (n2). Besides, construction of deformation model – process iterative, demanding some number of steps – k. However, k 10 times less n, therefore in time complexity it will not be mirrored. It is necessary as to consider labour input of process of solution of the equation of Euler which as will demand notable machine time.

At interpolating there is a surface construction on a cloud of points by splitting of a cloud into certain sites, and finding of surface function as it is possible passing through the points making a site. Spline construction is less labour-consuming, rather than solution of the equation of Euler. Time complexity of interpolational algorithm will make O (n).

Now concerning size of the expanded memory necessary for operation of algorithm. For construction of deformation model as already it has been told earlier, it is necessary to solve Euler's equation. However there is a way of replacement of the equation of Euler on system of simple equations. Quantity of the equations and unknown persons directly proportional to quantity of points in a cloud, and as consequence it will be necessary to store a matrix with coefficients of the equations in the size n*n. For an interpolation method by some rules it will be necessary to define m coefficients for each polynomial spline which it is included an order n units. But as m It would seem, the same problem will arise and at matching of clouds by a method deformation models. But among all variations of deformation models there is an algorithm of deformation by internal or external sphere. The algorithm consists in stage-by-stage deformation entered in a cloud, or the sphere described round it before reaching of similarity to a cloud with a certain error. The given technique usually is used for cloud visualisation, but will approach and for classification. By comparison of two clouds the energy necessary for deformation of sphere to initial and standard clouds taking into account coefficient of scaling is considered. The difference of energies of deformation of sphere to an initial cloud and to the measurement standard will be a measure of matching of similarity.

The reached results and the further prospects

By the current moment the theoretical analysis of two essentially different concepts of classification of three-dimensional clouds of points – a method of deformation models and its versions and a method by volume interpolation by means of three-dimensional splines is made. Are revealed their strong and weaknesses, the possible way of optimisation is considered at the further realisation, and also possible problems which can arise by working out of the software on the basis of the given algorithms are revealed. The most suitable is found to the decision of a task in view algorithm - a method of construction of deformation model with use of internal sphere. Optimisation will be reached for the account of algorithms deparallelizing on graphic processors by means of language CUDA. It is necessary to notice that CUDA concerns a subset – SIMD languages, that is on set of processors GPU one algorithm can be carried out simultaneously only. Operating time reduction will be reached at the expense of sphere splitting into some sectors, for each of which energy of deformation to a corresponding site of a cloud will be calculated.

The given author's abstract has survey character as master’s the dissertation on which it is written, is in a stage of working out and will be improved throughout an autumn semester of 2009.

References

1. Скороспелов, В. А. Сплайны в инженерной геометрии. –М.: Машиностроение 1985. – 156с.
2. Неймарк Ю.И., Баталова З.С., Васин Ю.Г., Брейдо М.Д. Распознавание образов и медицинская диагностика. М.: Наука, 1972.
3. Terzopoulos, D. 1986b). Regularization of inverse visual problems involving discontinuities. IEEE Transon Pattern Analysis and Machine Intelligence 8(4):413–424.
4. Fischler, M. and Elschlager, R. (1973). The representation and matching of pictorial structures. IEEE Transon Computers 22(1):67–92.
5. Zienkiewicz, O.C.and Taylor, R.L.(1989). The Finite Element Method. NewYork, NY:McGraw–Hill.
6. Gourdon, A.(1995). Simplication ofirregular surface meshes in3Dmedical images. InAyache(1995b). 413–419.
7. Hill,A.,Thornham,A.andTaylor,C.J.(1993). Model-based interpretation of3Dmedicalimages. InProc.4th British Machine Vision Conf. (BMVC93), Surrey, UK,September, 1993, 339–348. BMVAPress.
8. Essa, I., Sclaroff, S. and Pentland, A.P. (1993). Physically-based modeling for graphics and vision. In Martin, R.,ed., Directions in Geometric Computing. Information Geometers, U.K.
9. Young, A.A., Axel, L., Dougherty, L., Bogen, D.K. and Parenteau, C.S. (1993). Validation of tagging with MR imaging to estimate material deformation. Radiology 188:101–108.
10. Берилло, А. NVIDIA CUDA — неграфические вычисления на графических процессорах http://www.ixbt.com/video3/cuda-1.shtml