Es wurden verschieden Kodierungsarten fuer FSMs untersucht, schwerpunktmaessig Gray Code und andere Arten der hazardfreien Kodierung. Ein spezieller Kodierungsalgorithmus zur hazardfreien Kodierung wurde entwickelt und in eine Entwurfsumgebung implementiert. Ein weitere Schwerpunkt der Arbeit sind Codegeneratoren, die eine Verhaltensbeschreibung der FSM in Verilog oder in VHDL erzeugen.

Structured light is the most common 3D data acquisition technique used in the industry. Traditional Structured light methods are used to obtain the 3D information of an object. Multiple patterns such as Phase measuring profilometry, gray code patterns and binary patterns are used for reliable reconstruction. These multiple patterns achieve non-ambiguous depth and are insensitive to ambient light. However their application is limited to motion much slower than their projection time. These multiple patterns can be combined into a single composite pattern based on the modulation and demodulation techniques and used for obtaining depth information. In this way, the multiple patterns are applied simultaneously and thus support rapid object motion. In this thesis we have combined multiple gray coded patterns to form a single Gray code Composite Pattern. The gray code composite pattern is projected and the deformation produced by the target object is captured by a camera. By demodulating these distorted patterns the 3D world coordinates are reconstructed.

Counting is pretty basic, right? Zero, one, two, three, four, and so on. This episode of Geek Author presents a situation where we might want to rearrange the sequence of integers in order to provide better reliability in our digital circuits.

We continue our discussion of Gray code by presenting algorithms used to convert between the weighted numeral system of unsigned binary and the Gray code ordered sequence. We also show how to implement these algorithms in our code.

Let G be a graph and k be an integer greater than or equal to the chromatic number of G. The k-colouring graph of G is the graph whose vertices are k-colourings of G, with two colourings adjacent if they colour exactly one vertex differently. We explore the Hamiltonicity and connectivity of such graphs, with particular focus on the k-colouring graphs of complete multipartite graphs. We determine the connectivity of the k-colouring graph of the complete graph on n vertices for all n, and show that the k-colouring graph of a complete multipartite graph K is 2-connected whenever k is at least the chromatic number of K plus one. Additionally, we examine a conjecture that every connected k-colouring graph is 2-connected, and give counterexamples for k greater than or equal to 4. As our main result, we show that for all k greater than or equal to 2t, the k-colouring graph of a complete t-partite graph is Hamiltonian. Finally, we characterize the complete multipartite graphs K whose k-colouring graphs are Hamiltonian when k is the chromatic number of K plus one. / Graduate

Calibrating multiple projectors to create a distortion free environment is required in many fields e.g. simulators and the calibration may be done in a series different ways. This report will cover an automatic single camera projector calibration algorithm.The algorithm handles multiple projectors and can handle projectors covering bigger field of view than a camera by supporting image stitching. A proof of concept blending algorithm is also presented. The algorithm includes a new developed interpolation method building on spline surfaces and an orientation calculation algorithm that calculates the orientation difference between two camera views. Using the algorithm to calibrate, gives pixel accuracy of less than 1 camera pixel after interpolation and the relation between two views are calculated accurately. The images created using the algorithm is distortion free and close to seamless. The algorithm is limited to a controlled projector environment and calibrates the projectors for a single viewpoint. Furthermore, the camera needs to be calibrated positioned in the sweet spot although it can be arbitrary rotated.

A parameter-free solution is presented for data projector calibration using a single camera and Gray coded structured light patterns. The proposed method assumes that both camera and projector exhibit significant non-linear distortion, and that projection surfaces can be either planar or freeform. The camera is calibrated first through traditional methods, and the calibrated images are then used to detect Gray coded patterns displayed on a surface by the data projector. Projector to camera correspondences are created by decoding the patterns in the camera images to form a 2D correspondence map. Calibrated systems produce geometrically correct, ex- tremely short throw projections, while maintaining or exceeding the projection size of a standard configuration. Qualitative experiments are performed on two baseline images, while quantitative data is recovered from the projected image of a chessboard pattern. A typical throw ratio of 0.5 can be achieved with a pixel distance error below 1. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2010-06-29 09:33:50.311

Es wurden verschieden Kodierungsarten fuer FSMs untersucht, schwerpunktmaessig Gray Code und andere Arten der hazardfreien Kodierung. Ein spezieller Kodierungsalgorithmus zur hazardfreien Kodierung wurde entwickelt und in eine Entwurfsumgebung implementiert. Ein weitere Schwerpunkt der Arbeit sind Codegeneratoren, die eine Verhaltensbeschreibung der FSM in Verilog oder in VHDL erzeugen.

This thesis consists of two parts. In part I, a group of combinatorial problems pertaining to strings, boolean matrices and graphs is studied. For given two strings x and y, their edit distance is the minimum number of character insertions, deletions and substitutions required to convert x into y. In this thesis we provide an algorithm that computes a constant approximation of edit distance in truly sub-quadratic time. Based on the provided ideas, we construct a separate sub- quadratic time algorithm that can find an occurrence of a pattern P in a given text T while allowing a few edit errors. Afterwards we study the boolean matrix multiplication (BMM) problem where given two boolean matrices, the aim is to find their product over boolean semi-ring. For this problem, we present two combinatorial models and show in these models BMM requires Ω(n3 /2O( √ log n) ) and Ω(n7/3 /2O( √ log n) ) work respectively. Furthermore, we also give a construction of a sparse sub-graph that preserves the distance between a designated source and any other vertex as long as the total weight increment of all the edges is bounded by some constant. In part II, we study the efficient construction of quasi-Gray codes. We give a construction of space optimal quasi-Gray codes over odd sized alphabets with read complexity 4...

Nous introduisons des codes de Gray et des algorithmes efficaces de génération exhaustivepour trois classes de mots: (1) suites à croissance restreinte, (2) mots évitant un facteurspécifié, (3) permutations à motif exclus. Pour les deux premières classes, nos codes de Gray (et les algorithmes de génération qui en découlent) sont basés sur des relations d'ordre obtenues par la spécialisation de l'ordre du code de Gray réfléchi. Pour la troisième classe, les codes de Gray et les algorithmes de génération correspondants sont basés sur l'ordre induit par l'algorithme de Steinhaus-Johnson-Trotter pour la génération des permutations.Concernant les suites à croissance restreinte, nous définissons un code de Gray et donnonsun algorithme de génération exhaustive pour ce code. En particulier, nous considéronsles suites sous-excédantes et ascendantes, les fonctions à croissance restreinte et les mots `escalier'.Les relations d'ordre considérées sont RGC et Co-RGC, qui sont des relations partitionnantles listes selon, respectivement, le préfixe et le suffixe. De plus, nous explorons la possibilité pour l'obtention des codes de Gray pour les suites ascendantes restreintes.Pour les mots de q-aires à facteur interdit nous donnons deux codes de Gray et les algorithmes degénération correspondants. Les relations d'ordre considérées sont RGC, pour q pair, et Dual RGC pour q impair. Parmi les notions utilisées, citons la périodicité zéro et un algorithme classique derecherche de motif du à Knuth, Morris et Pratt. Comme application, nous considéronsles ensembles `cross-bifix-free'.Finalement, des résultats similaires sont obtenus pour certaines classes de permutations à motifinterdit. Plus précisément, nous montrons que la restriction ducode de Gray de Steinhaus-Johnson-Trotter aux ensembles de permutations évitant certains motifsreste un code de Gray (moins restrictif). Parmi les techniques utilisées, nous mentionnonsla fonction de succession et une bijection classique entre permutations et tableaux d'inversions,et donnons quelques conséquences en théorie des graphes. / We consider Gray codes and efficient exhaustive generating algorithms for the sets belonging to three major classes of restricted words, that are: (1) restricted growth sequences, (2) factor avoiding q-ary words, and (3) pattern avoiding permutations. For the first two classes, our Gray codes (and thus, our generating algorithms) are based on order relations obtained by specializing known order relations; namely Reflected Gray Code (RGC) order and its variations, and we call them Reflected Gray Code based orders. The Gray code and the generating algorithm for the third class are based on Steinhaus-Johnson-Trotter order, that is, order relation induced by Steinhaus-Johnson-Trotter Gray code for permutations. In the first results, we define Gray codes and give efficient generating algorithms for the class of restricted growth sequences that satisfy our prescribed properties. In particular, we focus on four mainstream subclasses: subexcedant and ascent sequences, restricted growth functions and staircase words. The results are given in two parts: by using original RGC order and Co-RGC order, which generates prefix (and suffix, respectively) partitioned Gray codes; and we give comparison between the two results. In addition, we investigate the Graycodeness of the restricted ascent sequences.In the second results, we define Gray codes and give an efficient generating algorithm for the class of factor avoiding q-ary words. Among the involved tools, we make use of original RGC order for even q and Dual RGC order for odd q, the zero periodicity property, and word matching techniques adapted from that of Knuth-Morris-Pratt. We give the implementation of these results to define Gray code and generating algorithm for cross-bifix-free sets.In the third results, we define Gray codes and give efficient generating algorithms for the class of pattern avoiding permutations. In particular, we show that the Steinhaus-Johnson-Trotter Gray code for permutations, when restricted by avoiding some set of patterns, still remains a (possibly less restricted) Gray code. The main ingredients we are using in the investigation of the Graycodeness are: succession functions, the classical bijection from inversion tables to permutations, and the list of inversion tables with respect to RGC order. We give additional results on graph theoretic consequences.