The morphological image processing can modify the shapes of objects very efficiently by structure elements. Thus, the morphology processing has recently been applied to industry auto-inspection and medical image processing successfully. In this thesis, we incestigate the efficient processing of morphological image processing by two approaches: quadtree approach and paralell approach. By the quadtree decomposition, any binary image can be decomposed into black and white square blocks with some fixed size of power of 2. Thus, dilation of the whole image can be accomplished by dilating individual decomposed square blocks. On the other hand, any binary image can be presented by bit per pixel basis. Thus, we can exploit the parallel on a personal computer to speed up the set oriented morphological image processing. Experiments have revealed that both approach are much faster than the direct method. The quadtree approach are most advantageous for large structure elements. Whereas, the parralel approach are the fastest for the usual applications.

¡@¡@Morphological image processing technique has been well applied to many image processing areas. However, its long computation time usually can¡¦t be accepted when run on a general purpose sequential computer. Instead of conventional image data representation, some special data structures have led to the development of efficient algorithms. ¡@¡@The quadtree data structure has been well applied to the field of computer vision such as image segmentation and compression. The quadtree with its hierarchical data structure are advantageous due to its ability to focus on the interesting subsets of the data. Thus, the quadtree data structure are particularly convenient for set operations. Therefore, the computation for morphology processing will be facilitated by using the quadtree data structure since the set operations are the basics of the morphology processing. ¡@¡@Although many fast morphological image processing methods have been presented, there is still a need for developing a distributed computing architecture for morphological processing. We propose a scheme direct connection for client to client to improve the data transfer efficiency. Also, the image data is compressed by the quadtree for the transmission efficiency. Due to the efficiency of the network connection and data compression, we have established an efficient web-based distributed work station for morphological image processing.

Η απεικόνιση και συμπίεση χωρικών δεδομένων έχει γίνει ένα θέμα έμφασης και προσοχής για τον τομέα των computer graphics και για εφαρμογές επεξεργασίας εικόνας. Τα quadtrees, σαν μία από τις ιεραρχικές δομές δεδομένων, βασιζόμενα στην αρχή του επαναλαμβανόμενου διαχωρισμού του χώρου, προσφέρουν πάντα μία συμπαγή και αποτελεσματική αντιπροσώπευση μίας εικόνας. Ο σκοπός αυτής της εργασίας είναι η ανάλυση του αλγορίθμου quadtree, και η σχεδίαση του αλγορίθμου με γλώσσα VHDL. Αναλύεται η μηχανή καταστάσεων και το datapath του υπό ανάπτυξη κυκλώματος. Επίσης παρουσιάζονται κυματομορφές των σημάτων της κάθε κατάστασης από την προσομοίωση που έγινε στο Modelsim. Για την επιβεβαίωση της λειτουργίας του κυκλώματος, έγινε σύνθεση του κυκλώματος με τη βοήθεια του προγράμματος ISE της Xilinx. Όσον αφορά την υλοποίηση, χρησιμοποιήθηκε το board της Xilinx Virtex-5 FPGA ML 507 και εξομοίωση λειτουργίας για εικόνα μεγέθους 64x64. Στο Παράρτημα παρουσιάζονται ο κώδικας Matlab της συνάρτησης qtdecomp που χρησιμοποιήθηκε για την κατανόηση του αλγόριθμου quadtree και καθώς και ο κώδικας Matlab που δημιουργήθηκε για να επαληθεύσει τα αποτελέσματα της προσομοίωσης με Modelsim. / Compression of spatial data has become a matter of emphasis and attention in the field of computer graphics and image processing applications. The quadtrees, as one of the hierarchical data structures, applies the principle of repetitive decomposition of space and offers a compact and efficient representation of an image. The purpose of this paper is to analyze the algorithm quadtree, and to design the algorithm with the language VHDL. In this paper the state machine is analyzed as well as the datapath of the circuit. Furthermore the waveforms of the control signals for each state are presented from the simulation done in the Modelsim environment. A confirmation of the operation of the circuit took also place.The circuit was composed with the help of the ISE of Xilinx. Regarding the implementation, the board of Xilinx Virtex-5 FPGA ML 507 is used and the emulation is done for a picture sized 64x64. The Annex outlines code of the MATLAB function qtdecomp used for understanding the quadtree algorithm and the Matlab code created to verify the simulation results of Modelsim.

Due to the fast development in 3D technology during recent decades, many approaches in 3D representation technologies have been proposed worldwide. In order to get an accurate information to render a 3D representation, more data need to be recorded compared to normal video sequence. In this case, how to find an efficient way to transmit the 3D representation data becomes an important part in the whole 3D representation technology. Recent years, many coding schemes based on the principle of encoding the depth have been proposed. Compared to the traditional multiview coding schemes, those new proposed schemes can achieve higher compression efficiency. Due to the development of depth capturing technology, the accuracy and quality of the reconstructed depth image also get improved. In this thesis we propose an efficient depth data compression scheme for 3D images. Our proposed depth data compression scheme is platelet based coding using Lagrangian optimization, quadtree decomposition and quadratic curve fitting. We study and improve the original platelet based coding scheme and achieve a compression improvement of 1-2 dB compared to the original platelet based scheme. The experimental results illustrate the improvement provided by our scheme. The quality of the reconstructed results of our proposed curve fitting based platelet coding scheme are better than that of the original scheme.

Due to the fast development in 3D technology during recent decades, many approaches in 3D representation technologies have been proposed worldwide. In order to get an accurate information to render a 3D representation, more data need to be recorded compared to normal video sequence. In this case, how to find an efficient way to transmit the 3D representation data becomes an important part in the whole 3D representation technology. Recent years, many coding schemes based on the principle of encoding the depth have been proposed. Compared to the traditional multiview coding schemes, those new proposed schemes can achieve higher compression efficiency. Due to the development of depth capturing technology, the accuracy and quality of the reconstructed depth image also get improved. In this thesis we propose an efficient depth data compression scheme for 3D images. Our proposed depth data compression scheme is platelet based coding using Lagrangian optimization, quadtree decomposition and quadratic curve fitting. We study and improve the original platelet based coding scheme and achieve a compression improvement of 1-2 dB compared to the original platelet based scheme. The experimental results illustrate the improvement provided by our scheme. The quality of the reconstructed results of our proposed curve fitting based platelet coding scheme are better than that of the original scheme.

Quadtree algorithm and morphological image processing are combined in the proposed method in this paper. A new method is proposed to improve the previous pattern mapping method for faster processing. The previous pattern mapping method is a pattern mapping method by storing the tree pattern by string form, which is a pointless data structure. In the proposed method the tree pattern is saved in a point data structure. Therefore, the pointer tree can be applied to the quadtree immediately without the transforming time, which was required in the previous pattern mapping method. In this paper, the pointless quad tree work is modified to pointer quad tree to reduce the processing time. The modified algorithm is applied to circuit detection, image restoration, image segmentation and cell counting.

With the proliferation of wireless communications and rapid advances in technologies, algorithms for efficiently answering queries about large number of spatial data are needed. Spatial data consists of spatial objects including data of higher dimension. Neighbor finding is one of the most important spatial operations in the field of spatial data structures. In recent years, many researchers have focused on finding efficient solutions to the nearest neighbor problem (NN) which involves determining the point in a data set that is the nearest to a given query point. It is frequently used in Geographical Information Systems (GIS). A block B is said to be the neighbor of another block A, if block B has the same property as block A has and covers an equal-sized neighbor of block A. Jozef Voros has proposed a neighbor finding strategy on images represented by quadtrees, in which the four equal-sized neighbors (the east, west, north, and south directions) of block A can be found. However, based on Voros's strategy, the case that the nearest neighbor occurs in the diagonal directions (the northeast, northwest, southeast, and southwest directions) will be ignored. Moreover, there is no total ordering that preserve proximity when mapping a spatial data from a higher dimensional space to a 1D-space. One way of effecting such a mapping is to utilize space-filling curves. Space-filling curves pass through every point in a space and give a one-one correspondence between the coordinate and the 1D-sequence number of the point. The Peano curve, proposed by Orenstein, which maps the 1D-coordinate of a point by simply interleaving the bits of the X and Y coordinates in the 2D-space, can be easily used in neighbor finding. But with the data ordered by the RBG curve or the Hilbert curve, the neighbor finding would be complex. The RBG curve achieves savings in random accesses on the disk for range queries and the Hilbert curve achieves the best clustering for range queries. Therefore, in this thesis, we first show the missing case in the Voros's strategy and show the ways to find it. Next, we show that the Peano curve is the best mapping function used in the nearest neighbor finding. We also show the transformation rules between the Peano curve and the other curves such that we can efficiently find the nearest neighbor, when the data is linearly ordered by the other curves. From our simulation, we show that our proposed two strategies can work correctly and faster than the conventional strategies in nearest neighbor finding. Finally, we present a revised version of NA-Trees, which can work for exact match queries and range queries from a large, dynamic index, where an exact match query means finding the specific data object in a spatial database and a range query means reporting all data objects which are located in a specific range. By large, we mean that most of the index must be stored in secondary memory. By dynamic, we mean that insertions and deletions are intermixed with queries, so that the index cannot be built beforehand.

Due to the fast development in 3D technology during recent decades, many approaches in 3D representation technologies have been proposed worldwide. In order to get an accurate information to render a 3D representation, more data need to be recorded compared to normal video sequence. In this case, how to find an efficient way to transmit the 3D representation data becomes an important part in the whole 3D representation technology. Recent years, many coding schemes based on the principle of encoding the depth have been proposed. Compared to the traditional multiview coding schemes, those new proposed schemes can achieve higher compression efficiency. Due to the development of depth capturing technology, the accuracy and quality of the reconstructed depth image also get improved. In this thesis we propose an efficient depth data compression scheme for 3D images. Our proposed depth data compression scheme is platelet based coding using Lagrangian optimization, quadtree decomposition and quadratic curve fitting. We study and improve the original platelet based coding scheme and achieve a compression improvement of 1-2 dB compared to the original platelet based scheme. The experimental results illustrate the improvement provided by our scheme. The quality of the reconstructed results of our proposed curve fitting based platelet coding scheme are better than that of the original scheme.

Background. Rendering planets with high detail from orbit to surface level is becoming increasingly common in video games. In this thesis, two solutions to achieving this will be compared, a quadtree solution and a tessellation solution. These solutions both implement an adaptive level of detail on a spherical shape. The quadtree solution uses six quadtrees to construct the planetary terrain mesh on the CPU with higher detail closer to the viewer. The tessellation solution uses the GPU to subdivide areas of a basic low-resolution model to achieve higher levels of detail close to the viewer. Objectives. Related work that has implemented these solutions uses old hardware and there is a lack of performance data on these solutions running on modern hardware. The objective of this project is to provide performance data and a comparison between the quadtree solution and the tessellation solution on modern hardware. This comparison will include a discussion of the negative and positive performance aspects of the two solutions. Methods. The two solutions will be implemented to create two similar-looking applications with a focus on only the technical aspects of rendering a globe mesh with each of these solutions. The frame time both on the CPU and on the GPU will be measured for each solution. The measurements will be taken at four different distances from the globe, meaning four different levels of detail. Due to a limitation of tessellation, this solution has to be provided with a higher resolution base model to achieve similar detail levels at the surface level. Results. The results show the quadtree frame time increasing with measurements taken closer to the surface of the globe. The tessellation results show a larger performance impact, though this is due to the base globe mesh being swapped for a higher-resolution model. Conclusions. The result suggests that the tessellation solution performs worse, however, the tessellation solution still shows little to no performance loss when comparing frame time measured on the same base mesh, even though the detail difference between them is high. The quadtree solution has an overall better performance and provides more control over the detail levels. The lack of control over the detail levels in the tessellation solution means that the detail level can not be matched exactly, which leads to the tessellation solution giving a richer topology.

Le traitement automatique de documents consiste en la transformation dans un format compréhensible par un système informatique de données présentes au sein de documents et compréhensibles par l'Homme. L'analyse de document et la compréhension de documents sont les deux phases du processus de traitement automatique de documents. Étant donnée une image de document constituée de mots, de lignes et d'objets graphiques tels que des logos, l'analyse de documents consiste à extraire et isoler les mots, les lignes et les objets, puis à les regrouper au sein de blocs. Les différents blocs ainsi formés constituent la structure géométrique du document. La compréhension de documents fait correspondre à cette structure géométrique une structure logique en considérant des liaisons logiques (à gauche, à droite, au-dessus, en-dessous) entre les objets du document. Un système de traitement de documents doit être capable de : (i) localiser une information textuelle, (ii) identifier si cette information est pertinente par rapport aux autres informations contenues dans le document, (iii) extraire cette information dans un format compréhensible par un programme informatique. Pour la réalisation d'un tel système, les difficultés à surmonter sont liées à la variabilité des caractéristiques de documents, telles que le type (facture, formulaire, devis, rapport, etc.), la mise en page (police, style, agencement), la langue, la typographie et la qualité de numérisation du document. Dans ce mémoire, nous considérons en particulier des documents numérisés, également connus sous le nom d'images de documents. Plus précisément, nous nous intéressons à la localisation d'informations textuelles au sein d'images de factures, afin de les extraire à l'aide d'un moteur de reconnaissance de caractères. Les factures sont des documents très utilisés mais non standards. En effet, elles contiennent des informations obligatoires (le numéro de facture, le numéro siret de l'émetteur, les montants, etc.) qui, selon l'émetteur, peuvent être localisées à des endroits différents. Les contributions présentées dans ce mémoire s'inscrivent dans le cadre de la localisation et de l'extraction d'informations textuelles fondées sur des régions identifiées au sein d'une image de document.Tout d'abord, nous présentons une approche de décomposition d'une image de documents en sous-régions fondée sur la décomposition quadtree. Le principe de cette approche est de décomposer une image de documents en quatre sous-régions, de manière récursive, jusqu'à ce qu'une information textuelle d'intérêt soit extraite à l'aide d'un moteur de reconnaissance de caractères. La méthode fondée sur cette approche, que nous proposons, permet de déterminer efficacement les régions contenant une information d'intérêt à extraire.Dans une autre approche, incrémentale et plus flexible, nous proposons un système d'extraction d'informations textuelles qui consiste en un ensemble de régions prototypes et de chemins pour parcourir ces régions prototypes. Le cycle de vie de ce système comprend cinq étapes:- Construction d'un jeu de données synthétiques à partir d'images de factures réelles contenant les informations d'intérêts.- Partitionnement des données produites.- Détermination des régions prototypes à partir de la partition obtenue.- Détermination des chemins pour parcourir les régions prototypes, à partir du treillis de concepts d'un contexte formel convenablement construit.- Mise à jour du système de manière incrémentale suite à l'insertion de nouvelles données / Document processing is the transformation of a human understandable data in a computer system understandable format. Document analysis and understanding are the two phases of document processing. Considering a document containing lines, words and graphical objects such as logos, the analysis of such a document consists in extracting and isolating the words, lines and objects and then grouping them into blocks. The subsystem of document understanding builds relationships (to the right, left, above, below) between the blocks. A document processing system must be able to: locate textual information, identify if that information is relevant comparatively to other information contained in the document, extract that information in a computer system understandable format. For the realization of such a system, major difficulties arise from the variability of the documents characteristics, such as: the type (invoice, form, quotation, report, etc.), the layout (font, style, disposition), the language, the typography and the quality of scanning.This work is concerned with scanned documents, also known as document images. We are particularly interested in locating textual information in invoice images. Invoices are largely used and well regulated documents, but not unified. They contain mandatory information (invoice number, unique identifier of the issuing company, VAT amount, net amount, etc.) which, depending on the issuer, can take various locations in the document. The present work is in the framework of region-based textual information localization and extraction.First, we present a region-based method guided by quadtree decomposition. The principle of the method is to decompose the images of documents in four equals regions and each regions in four new regions and so on. Then, with a free optical character recognition (OCR) engine, we try to extract precise textual information in each region. A region containing a number of expected textual information is not decomposed further. Our method allows to determine accurately in document images, the regions containing text information that one wants to locate and retrieve quickly and efficiently.In another approach, we propose a textual information extraction model consisting in a set of prototype regions along with pathways for browsing through these prototype regions. The life cycle of the model comprises five steps:- Produce synthetic invoice data from real-world invoice images containing the textual information of interest, along with their spatial positions.- Partition the produced data.- Derive the prototype regions from the obtained partition clusters.- Derive pathways for browsing through the prototype regions, from the concept lattice of a suitably defined formal context.- Update incrementally the set of protype regions and the set of pathways, when one has to add additional data.