Shape is very essential for detecting and recognizing objects. It is robust to illumination, color changes. Human can recognize objects just based on shapes, thus shape based object detection and recognition methods have been popular in many years. Due to problem of segmentation, some researchers have worked on silhouettes instead of real images. The main problem in this area is object recognition and the difficulty is to handle shapes articulation and distortion. Previous methods mainly focus on one to one shape similarity measurement, which ignores context information between shapes. Instead, we utilize graph-transduction methods to reveal the intrinsic relation between shapes on 'shape manifold'. Our methods consider the context information in the dataset, which improves the performance a lot. To better describe the manifold structure, we also propose a novel method to add synthetic data points for densifying data manifold. The experimental results have shown the advantage of the algorithm. Moreover, a novel diffusion process on Tensor Product Graph is carried out for learning better affinities between data. This is also used for shape retrieval, which reaches the best ever results on MPEG-7 dataset. As shapes are important and helpful for object detection and recognition in real images, a lot of methods have used shapes to detect and recognize objects. There are two important parts for shape based methods, model construction and object detection, recognition. Most of the current methods are based on hand selected models, which is helpful but not extendable. To solve this problem, we propose to construct model by shape matching between some silhouettes and one hand decomposed silhouette. This weakly supervised method can be used not only learn the models in one object class, but also transfer the structure knowledge to other classes, which has the similar structure with the hand decomposed silhouette. The other problem is detecting and recognizing objects. A lot of methods search the images by sliding window to detect objects, which can find the global solution but with high complexity. Instead, we use sampling methods to reduce the complexity. The method we utilized is particle filter, which is popular in robot mapping and localization. We modified the standard particle filter to make it suitable for static observations and it is very helpful for object detection. Moreover, The usage of particle filter is extended for solving the jigsaw puzzle problem, where puzzle pieces are square image patches. The proposed method is able to reach much better results than the method with Loopy Belief Propagation. / Computer and Information Science

The Diploma thesis is concerned with coupling of images. In the first part theoretical bases necessary for successful fulfilling of the assignment are described. The second part deals with the procedures that lead to composition of the jigsaw puzzle. The last part concentrates on controlling the program. The aim of the thesis is to propound an algorithm for solving a puzzle.

How does DNA make the abundant and diverged life world? To address this question, a DNA “Jigsaw Puzzle” structure model was proposed and first tested by comprehensively analyzing the genome of the model dicot plant, Arabidopsis thaliana. However, it is unknown whether this model is held in other species. Here we report the studies of the DNA structure model using the monocot plant model species, rice (Oryza sativa), and the single-celled model species, yeast (Saccharomyces cerevisiae). Analyses of the genomes sequenced so far revealed that the genome of an organism consists of a limited number of sequence-specialized, so-called fundamental function elements. For a higher organism, these elements often include genes (GEN), retro-transposable elements (RTE), DNA transposable elements (DTE), simple sequence repeats (SSR) and low complex repeats (LCR). Datasets were developed for RTE, DTE, SSR, LCR and GEN as well as genes categorized into different function categories from the sequences of the rice and yeast genomes using appropriate window sizes. The datasets were subjected to statistical analyses to test the DNA “Jigsaw Puzzle” structure model in terms of the unambiguousness, correlation, uniqueness and selection of their genome-constituting element arrays. The analyses were conducted with a series of window sizes of the sequences at both the whole genome and individual chromosome levels, both including and excluding the centromeric regions. The results showed that all fundamental function elements of the genomes as well as the genes categorized into different function categories were arrayed in the genomes in an unambiguous manner resembling linear “Jigsaw Puzzles” at the whole genome and/or individual chromosome levels, no matter whether the centromeric regions were included or excluded. The analyses revealed that arraying of the genomic elements was correlated significantly and uniquely for each chromosome and each species. This further confirmed the non-random arraying characteristic of the genomic elements for the DNA “Jigsaw Puzzle” structure model and suggested that the DNA “Jigsaw Puzzle” structure is unique for an organism, which has probably resulted from natural selection. These results unambiguously support the hypothesis of the DNA “Jigsaw Puzzle” structure model. Since the content, arraying and interaction pattern of the fundamental function elements were shown to be unique for each organism, variations of an organism in its DNA “Jigsaw Puzzle” array would lead to phenotypic variations, thus resulting in different organisms. Moreover, the fundamental function elements constituting a genome, as the four nucleotides (A, T, G and C) of DNA, could be arrayed into an infinite number of DNA molecules, thus giving different forms of organisms. Therefore, the DNA “Jigsaw Puzzle” structure model would provide a novel, but convincing explanation for the abundance, diversity and complexity of living organisms in the world.

This thesis examines the problem of the automated re-assembly of jigsaw puzzles. The objectives of this research are as follows: to provide a clear statement of the jigsaw puzzle re-assembly problem; to find out which solution technique is best suited to this problem; to determine the level of sensitivity of the proposed solution technique when solving different variations of this problem; and to explore solution methods for solving incomplete jigsaw puzzles (puzzles with missing pieces). The jigsaw puzzle re-assembly problem has been investigated only intermittently in the research literature. This work presents an extensive examination of the suitability and efficiency of the standard solution techniques that can be applied to this problem. A detailed comparison between different solution methods including Genetic Algorithms, Simulated Annealing, Tabu Search and Constraint Satisfaction Programming, shows that a constraint-based approach is the most efficient method of generating solutions to the jigsaw puzzle problem. The proposed re-assembly algorithm is successful. Consequently, it can be used in development of automated solution generators for other problems in the same domain, thus creating new theoretical and applied directions in this field of research. One potential theoretical line of research concerns jigsaw puzzles that do not have a complete set of puzzle pieces. These incomplete puzzles represent a difficult aspect of this problem that is outlined but can not be resolved in the current research. The computational experiments conducted in this thesis demonstrate that the proposed algorithm being optimised to re-assemble the jigsaw puzzles is not efficient when applied to the puzzles with missing pieces. Further work was undertaken to modify the proposed algorithm to enable efficient re-assembly of incomplete jigsaw puzzles. Consequently, an original heuristic strategy, termed Empty Slot Prediction, was developed to support the proposed algorithm, and proved successful when applied to certain sub-classes of this problem. The results obtained indicate that no one algorithm can be used to solve the multitude of possible scenarios involved in the re-assembly of incomplete jigsaw puzzles. Other variations of the jigsaw puzzle problem that still remain unsolved are presented as avenues for future research. The solution of this problem involves a number of procedures with significant applications in other computer-related areas such as pattern recognition, feature and shape description, boundary-matching, and heuristic modelling. It also has more practical applications in robotic vision and reconstruction of broken artefacts in archaeology.