As b-splines são utilizadas em sistemas CAD/CAM/CAE para representar e definir curvas e superfícies complexas, sendo adotada pelos principais padrões da computação gráfica devido a características como representação matemática de forma compacta, flexibilidade e transformações afins. Em sistemas de aquisição de dados 3D e sistemas CAM-CNC integrados, a utilização da b-spline na transferência de informações geométricas e na reconstrução da superfície de objetos resulta em um significativo incremento na eficiência do processo, geralmente implementado em sistemas embarcados. Nestes sistemas embarcados, integrados no auxílio a máquinas de manufatura, a utilização de FPGAs é incipiente, sem circuitos para b-splines disponibilizados em lógica reconfigurável de circuito aberto (open core), razão pela qual este projeto propõe o desenvolvimento de um circuito de geração b-spline aberto, em um sistema embarcado FPGA, utilizando algoritmos adaptados para os circuitos, elaborados em linguagem Verilog HDL, padronizada para a síntese de circuitos em lógica reconfigurável. Os circuitos foram desenvolvidos, utilizando-se um barramento de dados padronizado em circuito aberto, nas seguintes implementações para processamento paralelo das b-splines: o BFEA, o método baseado em funções base fixas, ambos projetados para circuitos integrados, e o fast Cox-de Boor, desenvolvido para FPGAs. Foram comparados o tempo de execução e o consumo de recursos disponíveis no FPGA utilizado, entre cada implementação. Os resultados evidenciaram que os circuitos de funções base fixas apresentaram o processamento mais rápido para a geração de b-splines em um FPGA, com um tempo de execução em média 20% menor em relação às outras implementações. Os circuitos BFEA apresentaram a menor utilização de elementos lógicos, em média 50% menor em relação aos outros circuitos implementados. O circuito fast Cox-de Boor apresentou a melhor escalabilidade, devido à modularidade da implementação, com tempos de execução similares aos circuitos de funções base fixas. / The b-splines are used in CAD/CAM/CAE systems to represent and define complex curves and surfaces, being adopted by the main computer graphics standards due to features like compact mathematic representation, flexibility and affine transformations. In 3D acquisition systems and integrated CAM-CNC systems, the use of the b-spline in the geometric information data transfer and in the object surface reconstruction results in a increase in the process efficiency, generally implemented in embedded systems. In these embedded systems, integrated in the aid to manufacturing machines, the use of FPGAs is incipient, without available b-splines open core circuits in reconfigurable logic, the reason why this project propose the development of a b-spline generation open core circuit, in a FPGA embedded system, using adaptated algorithms for the circuits, made in Verilog HDL language, standardized for the circuit synthesis in reconfigurable logic. The circuits were developed, using an open core standardized data bus, in the following implementations of b-spline parallel processing: the BFEA, fixed basis functions based method, both designed for integrated circuits, and the fast Cox-de Boor, developed for FPGAs. The execution time and available resource consumption in the FPGA were compared, between each implementation. The results show that the fixed basis functions circuits presented the fastest processing for the b-splines generation in a FPGA, with a 20% mean execution time reduction in relation to the other implementations. The BFEA circuits presented the lowest logic elements use, in mean 50% fewer in relation to the other implemented circuits. The fast Cox-De Boor circuit presented the best scalability, due to the implementation modularity, with execution times similar to the fixed basis functions circuits.

This thesis presents a collection of photogrammetry techniques aimed at the analysis of short-lived events. The small time scale on which these phenomena happen makes them difficult to capture not only from the point of view of hardware but also because one can not obtain several measurements of events that are not repeatable. Three subjects are presented in ascending order of complexity. We first detail a new approach that uses a simple unidimensional image sensor for traffic monitoring in order to obtain a large number of accurate measurements like speed, acceleration or inter-vehicle distances. This is followed by a discussion on the reconstruction of the surface of an evanescent liquid flow using stereovision on floating tracers. Finally, a new spectral model is used for the three-dimensional detection of aircraft wake vortices from IR LIDAR measurements. The approach was successfully tested during flight tests and proved to be invaluable to detect the wakes under these specific conditions.

Computational modules early in the human vision system typically generate sparse information about the shapes of visible surfaces in the scene. Moreover, visual processes such as stereopsis can provide such information at a number of levels spanning a range of resolutions. In this paper, we extend this multi-level structure to encompass the subsequent task of reconstructing full surface descriptions from the sparse information. The mathematical development proceeds in three steps. First, the surface most consistent with the sparse constraints is characterized as the solution to an equilibrium state of a thin flexible plate. Second, local, finite element representations of surfaces are introduced and, by applying the finite element method, the continuous variational principle is transformed into a discrete problem in the form of a large system of linear algebraic equations whose solution is computable by local-support, cooperative mechanisms. Third, to exploit the information available at each level of resolution, a hierarchy of discrete problems is formulated and a highly efficient multi-level algorithm, involving both intra-level relaxation processes and bi-directional inter-level algorithm, involving both intra-level relaxation processes and bidirectional inter-level local interpolation processes is applied to their simultaneous solution.. Examples of the generation of hierarchies of surface representations from stereo constraints are given. Finally, the basic surface approximation problem is revisited in a broader mathematical context whose implications are of relevance to vision.

In recent years many researchers have investigated the use of Markov random fields (MRFs) for computer vision. The computational complexity of the implementation has been a drawback of MRFs. In this paper we derive deterministic approximations to MRFs models. All the theoretical results are obtained in the framework of the mean field theory from statistical mechanics. Because we use MRFs models the mean field equations lead to parallel and iterative algorithms. One of the considered models for image reconstruction is shown to give in a natural way the graduate non-convexity algorithm proposed by Blake and Zisserman.

Surface reconstruction of anatomical structures is an integral part of medical modeling. Contour information is extracted from serial cross-sections of tissue data and is stored as "slice" files. Although there are several reasonably efficient triangulation algorithms that reconstruct surfaces from slice data, the models generated from them have a jagged or faceted appearance due to the large inter-slice distance created by the sectioning process. Moreover, inconsistencies in user input aggravate the problem. So, we created a method that reduces inter-slice distance, as well as ignores the inconsistencies in the user input. Our method called the piecewise weighted implicit functions, is based on the approach of weighting smaller implicit functions. It takes only a few slices at a time to construct the implicit function. This method is based on a technique called variational interpolation. <p> Other approaches based on variational interpolation have the disadvantage of becoming unstable when the model is quite large with more than a few thousand constraint points. Furthermore, tracing the intermediate contours becomes expensive for large models. Even though some fast fitting methods handle such instability problems, there is no apparent improvement in contour tracing time, because, the value of each data point on the contour boundary is evaluated using a single large implicit function that essentially uses all constraint points. Our method handles both these problems using a sliding window approach. As our method uses only a local domain to construct each implicit function, it achieves a considerable run-time saving over the other methods. The resulting software produces interpolated models from large data sets in a few minutes on an ordinary desktop computer.

Reconstruction of continuous signals from a number of their discrete samples is central to digital signal processing. Digital devices can only process discrete data and thus processing the continuous signals requires discretization. After discretization, possibility of unique reconstruction of the source signals from their samples is crucial. The classical sampling theory provides bounds on the sampling rate for unique source reconstruction, known as the Nyquist sampling rate. Recently a new sampling scheme, Compressive Sensing (CS), has been formulated for sparse signals. CS is an active area of research in signal processing. It has revolutionized the classical sampling theorems and has provided a new scheme to sample and reconstruct sparse signals uniquely, below Nyquist sampling rates. A signal is called (approximately) sparse when a relatively large number of its elements are (approximately) equal to zero. For the class of sparse signals, sparsity can be viewed as prior information about the source signal. CS has found numerous applications and has improved some image acquisition devices. Interesting instances of CS can happen, when apart from sparsity, side information is available about the source signals. The side information can be about the source structure, distribution, etc. Such cases can be viewed as extensions of the classical CS. In such cases we are interested in incorporating the side information to either improve the quality of the source reconstruction or decrease the number of the required samples for accurate reconstruction. A general CS problem can be transformed to an equivalent optimization problem. In this thesis, a special case of CS with side information about the feasible region of the equivalent optimization problem is studied. It is shown that in such cases uniqueness and stability of the equivalent optimization problem still holds. Then, an efficient reconstruction method is proposed. To demonstrate the practical value of the proposed scheme, the algorithm is applied on two real world applications: image deblurring in optical imaging and surface reconstruction in the gradient field. Experimental results are provided to further investigate and confirm the effectiveness and usefulness of the proposed scheme.

Surface reconstruction of anatomical structures is an integral part of medical modeling. Contour information is extracted from serial cross-sections of tissue data and is stored as "slice" files. Although there are several reasonably efficient triangulation algorithms that reconstruct surfaces from slice data, the models generated from them have a jagged or faceted appearance due to the large inter-slice distance created by the sectioning process. Moreover, inconsistencies in user input aggravate the problem. So, we created a method that reduces inter-slice distance, as well as ignores the inconsistencies in the user input. Our method called the piecewise weighted implicit functions, is based on the approach of weighting smaller implicit functions. It takes only a few slices at a time to construct the implicit function. This method is based on a technique called variational interpolation. <p> Other approaches based on variational interpolation have the disadvantage of becoming unstable when the model is quite large with more than a few thousand constraint points. Furthermore, tracing the intermediate contours becomes expensive for large models. Even though some fast fitting methods handle such instability problems, there is no apparent improvement in contour tracing time, because, the value of each data point on the contour boundary is evaluated using a single large implicit function that essentially uses all constraint points. Our method handles both these problems using a sliding window approach. As our method uses only a local domain to construct each implicit function, it achieves a considerable run-time saving over the other methods. The resulting software produces interpolated models from large data sets in a few minutes on an ordinary desktop computer.

Many laser devices acquire directly 3D objects and reconstruct their surface. Nevertheless, the final reconstructed surface is usually smoothed out as a result of the scanner internal de-noising process and the offsets between different scans. This thesis, working on results from high precision scans, adopts the somewhat extreme conservative position, not to loose or alter any raw sample throughout the whole processing pipeline, and to attempt to visualize them. Indeed, it is the only way to discover all surface imperfections (holes, offsets). Furthermore, since high precision data can capture the slightest surface variation, any smoothing and any sub-sampling can incur in the loss of textural detail.The thesis attempts to prove that one can triangulate the raw point cloud with almost no sample loss. It solves the exact visualization problem on large data sets of up to 35 million points made of 300 different scan sweeps and more. Two major problems are addressed. The first one is the orientation of the complete raw point set, an the building of a high precision mesh. The second one is the correction of the tiny scan misalignments which can cause strong high frequency aliasing and hamper completely a direct visualization.The second development of the thesis is a general low-high frequency decomposition algorithm for any point cloud. Thus classic image analysis tools, the level set tree and the MSER representations, are extended to meshes, yielding an intrinsic mesh segmentation method.The underlying mathematical development focuses on an analysis of a half dozen discrete differential operators acting on raw point clouds which have been proposed in the literature. By considering the asymptotic behavior of these operators on a smooth surface, a classification by their underlying curvature operators is obtained.This analysis leads to the development of a discrete operator consistent with the mean curvature motion (the intrinsic heat equation) defining a remarkably simple and robust numerical scale space. By this scale space all of the above mentioned problems (point set orientation, raw point set triangulation, scan merging, segmentation), usually addressed by separated techniques, are solved in a unified framework.

This dissertation investigates issues relevant to virtualization of a real 3D object – that is, producing a model of the object from its image data, and then visualizing this model as an image seen on the computer screen The object of investigation is methods and algorythms for reconstruction of a complex geometric shape from a number of unorganised point sets in to electronic form. Unorganised point sets are obtained by scanning the 3d object from defferent points of view. The choise of the complex oject is made so that it can not be described by a simple mathematical expression. To attain the aim, the following tasks were put forward: developing a model for a source of linear beam (scanner) and generating an unorganized point set that approximates the object scanned, filtering the unorganized point set and aggregating the unorganized point set to build an entire image of the object and reconstruct its surface. The aim of this work was to reconstruct the surface image of a 3D object using linear beam. This aim was sought by modifying the existing methods, or proposing new methods, and evaluating the accuracy of the reconstruction using statistical techniques The work consists of the general characteristic, four chapters, conclusions, list of literature and list of publications. The first section reviews the human visual system, computer vision and three-dimensional imaging technologies. The second section is addressed to a problem of linear beam’s centreline extraction in 2d... [to full text] / Šioje disertacijoje nagrinėjamas realaus trimačio objekto virtualizavimas – t. y. objekto paviršiaus modelio sukūrimas iš skenuotų vaizdų aibės, po to vizualizuojant šį modelį atvaizdo kompiuterio monitoriaus ekrane pavidalu. Tyrimų objektas – sudėtingos geometrinės formos erdvinio objekto paviršiaus atkūrimo elektroniniu pavidalu iš keleto nestruktūrizuotų taškų rinkinių, gautų nuskaitant objektą skirtingomis apžvalgos kryptimis, metodai ir algoritmai. Sudėtinga objekto forma pasirinkta tam, kad jos nebūtų galima perteikti paprasta matematine išraiška. Erdvinio objekto virtualizavimo procesą galima išskaidyti į šiuos keturis etapus: nestruktūrizuotų taškų rinkinio formavimą, filtravimą, apjungimą ir rekonstravimą. Pirmojo etapo metu, naudojant optinius jutiklius ir kontaktinį skaitymo metodą, objektas nuskaitomas skirtingomis apžvalgos kryptimis, taip gaunant keletą objekto paviršiaus nestruktūrizuotų taškų rinkinių. Antrame etape pašalinami taškai, atsiradę dėl optinių iškraipymų, atspindžių ir šešėlinių sričių įtakos. Trečiame etape atskiri taškų rinkiniai apjungiami į visumą. Paskutinis etapas skirtas erdvinio objekto paviršių aproksimuojančiam tinkleliui gauti. Pagrindinis šio darbo tikslas buvo rekonstruoti erdvinio objekto paviršiaus atvaizdą, objektą apšviečiant linijiniu šviesos pluoštu. Šio tikslo buvo siekiama tobulinant esamus metodus arba kuriant naujus, o taip pat statistiniais metodais vertinant rekonstrukcijos tikslumą. Disertacijos... [toliau žr. visą tekstą]

This thesis presents a new technique for the reconstruction of a smooth surface from a set of 3D data points. The reconstructed surface is represented by an everywhere -continuous subdivision surface which interpolates all the given data points. And the topological structure of the reconstructed surface is exactly the same as that of the data points. The new technique consists of two major steps. First, use an efficient surface reconstruction method to produce a polyhedral approximation to the given data points. Second, construct a Doo-Sabin subdivision surface that smoothly passes through all the data points in the given data set. A new technique is presented for the second step in this thesis. The new technique iteratively modifies the vertices of the polyhedral approximation 1CM until a new control meshM, whose Doo-Sabin subdivision surface interpolatesM, is reached. It is proved that, for any mesh M with any size and any topology, the iterative process is always convergent with Doo-Sabin subdivision scheme. The new technique has the advantages of both a local method and a global method, and the surface reconstruction process can reproduce special features such as edges and corners faithfully.