Dimensionality reduction is essential for analyzing high-dimensional datasets across various fields. While t-SNE is a popular method for this purpose in Euclidean spaces, recent advancements suggest that hyperbolic spaces can better represent hierarchical structures. However, there is a notable lack of data structures and algorithms tailored for hyperbolic spaces. This research addresses this gap by implementing a hyperbolic quadtree structure in the upper half-plane model and integrating it into the hyperbolic t-SNE framework. Our goal is to accelerate the optimization of the hyperbolic t-SNE while maintaining reasonable precision and recall. We conduct rigorous benchmarking experiments to evaluate the performance of this approach, comparing it to existing methods. The findings provide insights into the practical utility of using the hyperbolic quadtree structure in the upper half-plane model in hyperbolic t-SNE embeddings.

With the rapid growth in data collection, efficient data processing is critical. Dimensionality reduction methods, like t-distributed stochastic neighbour embedding (t-SNE), compress high-dimensional data into embeddings that preserve the key features of the datasets making data less sparse and easier to process further. Recent improvements suggest that using hyperbolic space for data representation can benefit embeddings. As it is a new technique, it remains computationally expensive. Previous work suggests that a Barnes-Hut approximation with a polar quadtree can be applied to the Poincaré disk model to approximate the result of hyperbolic t-SNE and accelerate its calculation. However, the polar quadtree is proposed as a solution to accelerate the calculation without exploring alternative approaches. Aiming to close this gap, we propose an acceleration method using Barnes-Hut approximation with a Cartesian quadtree. We experimentally compare our acceleration method to a polar quadtree and showcase its lower execution time without the loss of quality of the embeddings.
Implementation and scripts for the experiments and plots are available at https://github.com/Sne4kers/hyperbolic-tsne

This paper investigates a method for accelerating hyperbolic t-SNE — a popular high-dimensional data visualization technique. In particular, it focuses on building a hyperbolic t-SNE variant that uses a different model of hyperbolic space (called the Lorentz Hyperboloid model) for representing the low-dimensional embeddings. An acceleration algorithm based on a tree data-structure is then used to achieve a better asymptotic runtime complexity compared to the original version. The paper then compares this implementation with other alternatives — including accelerated variants — and shows that it computes embeddings of better quality at a similar rate.

In this work we aim to implement a variaton of the acceleration of hyperbolic t-SNE done by Skrodzki et. al. [19]. This variation aims to embed the points in the Klein Disk model of hyperbolic space instead of the Poincar ́e Disk model using an altared version of a polar quadtree to speed up the computation in a similar fashion as the Barnes-Hut scheme for the Euclidean versino of t-SNE. We analyze our results to prove our acceleration works for the Klein Disk model and compare the efficiency of our implemen- tation to the one for the Poincar ́e model in terms of quality of results and runtime.

Dimensionality reduction is an important task in high-dimensional data visualisation. Among the popular algorithms for achieving this is t-SNE, which aims to preserve local neighbourhoods in the lower-dimensional embeddings. While t-SNE traditionally works in Euclidean space, embedding in hyperbolic space offers several advantages, specifically for data of arbitrary size and exponential growth, such as tree-based structures. We propose a new solution to approximate and accelerate the calculation of t-SNE gradients using a uniform grid structure. This new method produces embeddings with better neighbourhood preservation than previous solutions, while also providing better runtime performance.

Watermarks have an essential role in identifying the origins and age of specific documents. However, this is often a laborious process. One of the main issues in automatic watermark segmentation is the presence of text that obstructs it, making it difficult to properly reconstruct a watermark. Image processing and machine learning techniques face limitations, requiring time, training of data, or manual parameter selection. This research introduces a new method using wavelets transform to locate and remove text from a watermarked image, while preserving the underlying watermark. This method manages to outperform classic image processing techniques for the case when text is thicker than the watermark outline.

Feature extraction techniques for content-based image retrieval are explored, focusing on black-and-white images in the context of historical watermarks. Orthogonal moments and texture features are found to be most applicable. Seven methods are evaluated: four different orthogonal moments, Gabor features, and two novel combinations of orthogonal moments with Gabor features. Retrieval effectiveness is judged based on the precision-recall curve and mean average precision, and watermarks are considered when unchanged, rotated, sheared and both rotated and sheared. The results demonstrate that research into improving efficient grayscale image representation does not translate over to improvements with black-and-white images. As it stands, the basic Zernike moments and novel Gabor-Zernike features are most effective.

This paper tackles the problem of evaluating the task of finding similar scanned historical watermarks - small images embedded in historical paper that have been digitized to be processed on a computer - using pre-trained neural networks. This research aims to identify an efficient and accurate alternative to the traditional, time-consuming manual detection methods for finding similar watermarks. The primary issue addressed is the inefficiency of these manual methods. The evaluation focuses on finding similar watermarks for a specific query watermark, assessing the efficacy of neural networks in comparison to a prior art system that employs traditional image processing techniques. This comparison aims to determine how well these neural networks perform in the task of watermark similarity detection. The study involves a dataset of 500 labeled images tested in two distinct contexts: one using unprocessed images and another using images processed to keep only the watermark outline. The results show that pre-trained models achieve higher accuracy and time efficiency compared to the prior art system that uses image processing. These models demonstrate significant effectiveness in watermark recognition and comparison, with each network achieving over 80% accuracy for traced watermarks. EfficientNetB0 achieved 94.66%, VGG16 89.33%, ResNet50 86.67%, and InceptionV3 84%, while the prior art system gets 64,8%. These results conclude that these models are valuable tools in the field of watermark recognition and comparison.

A curve is a continuously bending line with no angles that can be found anywhere in the real world, forming shapes and outlines. They are also the building blocks of historic watermarks, imprinted images on paper that may be used to identify its manufacturers. Their shapes consist of curves as bent wires are used in their production process. Often, the processing of scans of those curves may introduce gaps or a degraded quality which could be corrected by reconstructing the curves in those gaps. Curve reconstruction is a fundamental problem with many research applications, one of which is the reconstruction of curves for binarised scans of historic watermarks. In this paper, a data generation approach is proposed for the simulation of the watermark curves domain through singular automatically generated curves and human-drawn sketches which are then used along binarised watermark scans. I propose a hybrid method combining machine-learning and analytical approaches for curve reconstruction, aiming to leverage their advantages together. The method is compared to its components separately. Quantitative results against them demonstrate the superiority of the pure machine learning approach, as well as the need for more research into potentially better analytical components and a more realistic domain simulation.

A watermark image is a scan of a historical paper document that contains a watermark, which is a motif embedded in the paper that provides valuable information on the origins of a document. Developing tools to automatically identify watermarks can make this information more accessible to researchers. This paper focuses on one specific binarization technique, thresholding. Thresholding selects a threshold value, which is used to turn an image binary such that one color represents foreground and the other represents background. Ideally, binarization isolates the watermark’s shape by representing it as foreground, and removes unwanted information. This research compares the effectiveness of different thresholding techniques when applied to watermark images. Eight algorithms are selected from the literature, and a novel algorithm is proposed that seeks to improve on the other algorithms when applied to watermarks. The nine total algorithms are evaluated quantitatively on synthetic data, and qualitatively through a survey where participants select which algorithm appears best and rate it. The results show that there is no clear algorithm which works best for all images, however a logical adaptive approach may work marginally better than other approaches. Additionally, the presented algorithms do not adequately remove non-watermark information from the images. Further research should be conducted to analyze different binarization techniques in this context.

Navigation is a core aspect of exploring virtual environments. To assist players, a mini-map is a commonly used navigational tool. Navigation in an unknown space can be difficult. This difficulty is only increased when a player finds themselves in a non-Euclidean space. This paper explores the effect the mini-map's positioning has on the player's navigational performance in Virtual Reality using hyperbolic space. For this two positions are used: the first mini-map is positioned on the Heads-Up Display and the second is positioned on the player's right hand. Two player groups are randomly created to take part in a player experiment. Players get to read an information sheet and complete a small tutorial before having to complete 3 levels. Players are measured on how much time and how many steps it takes them to complete each level, how much their time and steps improve over the levels, their total time, and their total amount of steps. Combined these results indicate that there is no clear effect on the player's performance navigating a hyperbolic space in Virtual Reality.

Virtual Reality allows for the ultimate immersion in environments not naturally encountered. Still, hyperbolic environments are extremely difficult to get used to. This paper explores whether immersion in virtual hyperbolic environments can be enhanced by introducing a procedurally generated world. We propose a Wave Function Collapse (WFC) algorithm that can divide the hyperbolic plane into distinct areas and populate the space with dynamically generated objects. This can assist players in recognising areas visited prior, which can create an intuitive feel for how hyperbolic space operates. Although 5-order square tiling is used in this paper, the proposed algorithm can be extended to other tiling approaches. Evidence suggests players in a populated hyperbolic environment need on average fewer steps to reach their objective compared to a control group with an empty environment, although the time taken for both groups is roughly the same. From this and a qualitative analysis we infer that players feel more immersed in the environment when it is procedurally generated instead of mostly empty.

Simulating non-Euclidean geometry in virtual reality is of interest to a wide variety of fields of research. However it is still quite a challenge. Various methods are already known, but they vary greatly in performance and applicability. This paper compares some methods of rendering a non-Euclidean space. We focus on the order-5 square tiling that can be found in the hyperbolic plane, but the methods used are also relevant to other non-Euclidean spaces. We render this space using portals with two different implementations: one using render textures, an one using stencil polygons. Through an experiment where we measured and compared the frame rate of each method, we have found that, even with a small number of portals, the stencil polygon approach is more than two times as efficient. However, this method is limited in the number of portals, whereas render textures can be used for any number of portals.

It is possible to use a different representation of space in a Virtual Reality (VR) game, instead of using the euclidean representation we are used to. The reason why that is interesting is that it opens up the possibility of traversing infinitely far in the virtual space while being confined to a relatively limited space in the real world. But for this to be a useful use case, people will need the ability to traverse this new space in an intuitive or at least competent way. One way to help people with navigation in such a space would be to show the person what the fastest path from point A to point B is. This paper researches the possible ways to calculate this path so it can be used to help people while they are traversing this different type of space. Concluding that a trade-off needs to be made between the speed and accuracy of the result depending on the situation, and that no algorithm exists which is the best in both speed and accuracy. Meaning that the context determines what algorithm should be used.

Non-Euclidean spaces are spaces that do not satisfy all of Euclid’s postulates. An example of such a space is hyperbolic space. In this paper, a method is discussed to draw a tessellation of hyperbolic space in a manner that fits with the virtual reality game "Holonomy", a game which takes place in hyperbolic space. The main result shows that the new approach is better in terms of simplicity than the old approach and is able to draw the game world more faithfully than the old approach. The features of the new approach could still be significantly expanded upon.

A cellular automaton for simulating territories is presented. In it, cells have a certain amount of markings of two different groups. The amount of markings for each group gets higher based on the amounts of that group in neighboring cells and the amount of markings of the opposite group in the current cell to simulate an avoidance tendency. The markings also decay at a certain rate. Depending on the parameters, the simulation can end up in a mixed state, where there are no clear territories, or a segregated state, where both groups have a large amount of connected cells where they are dominant. Small changes in these parameters can change the outcome significantly. Unless an unconsidered combination of parameters changes it, this model is not the most realistic. It could however have uses in more influence-based processes, such as the spread and boundaries of languages or religion.

This research paper proposes a discrete agent-based model to simulate territorial development among micro-organisms. The model involves two species that interact through marker signals left behind by agents as they move through a three-dimensional lattice. The study builds on previous research that established a phase transition from a well-mixed to a well-segregated state for two-dimensional lattices. This research extends the finding to three dimensions and confirms that the properties observed in the two-dimensional model are also present in the three-dimensional model. We conclude that the addition of more mass or the ratio between gamma and lambda behaves similarly to the two-dimensional model. However, the three-dimensional model needs a larger mass to reach the same critical point as the two-dimensional one.

In 1952, Alan M. Turing presented a reaction-diffusion model that described formation of skin patterns. The patterns he predicted have later been found in various natural phenomena, such as in skins of fish or even in vegetation around termite hills. His patterns have even been taken to the micro-level. In 1984, David A. Young proposed a discretisation of this model, which enabled computer simulation. Both Turing and Young had only looked at two-dimensional patterns, until Martin Skrodzki and Konrad Polthier took the patterns to the third dimension in 2017. In this paper, these 3D simulations are generalised to produce patterns with more than two substances. We want to see whether Turing-like patterns also emerge there. To increase simulation speeds, a Graphics Processing Unit (GPU) implementation is described for this multi-species extension. Furthermore, we begin to investigate to what extent an order parameter can be defined, to analyse the formation of 3D structures. We found that our multi-species extension produced Turing-like structures that look similar to the ones found by former models. Our GPU simulation provided a significant performance increase. We also found that our order parameter can distinguish between well-mixed, well-segregated, and fully dominated states. However, it is yet unclear whether it can also be used to classify shapes.

Watermarks are historical motifs present in the texture of paper that are commonly used to identify the paper manufacturers. They only become visible when viewed under certain light conditions. Under ideal circumstances, researchers may use watermarks to determine a historical document’s origins and context. To identify a watermark, it is matched to a previously archived watermark. Currently, this matching must be done manually, which is neither scalable nor parallelizable. Existing studies explore digital reconstructions of watermarks, but do not focus on a comparison-based setup. This report discusses a system that can automatically identify similar watermarks using traditional image processing techniques. The resulting system speeds up the process considerably, can be used on small datasets, and is more accessible to end-users.

The system uses harmonization, feature extraction, and similarity matching. Harmonization involves improving the clarity of the watermark, which is often obscured by the material properties of the paper. Feature extraction involves finding useful information from the isolated watermarks, and similarity matching uses this information to score the similarity of a pair.

We evaluated our system based on a dataset provided by the German Museum of Books and Writing. Over a broader range of quality, accuracy was found to be within the range of 41-53%. It was also found that improving watermark quality within the dataset improved accuracy results to around 82%. The system shows promise particularly with higher quality datasets. This report therefore demonstrates that traditional image processing techniques can be valuable when applied to situations where artificial intelligence may not be possible or efficient. Further research into this domain would be required to understand the advantages and limitations of image processing in comparison with artificial intelligence.

This paper describes the process and evaluation methods by which we adapted a Reaction-Diffusion model and an order parameter to monitor its segregation state in a 2D Cellular Automaton model. The model simulates Turing pattern formations, whose behavior will be studied by an order parameter formulated for this project. This order parameter acts as an indicator of the mixture state of the world. The implementation process of such a cellular automaton and an order parameter is described in detail, as well as the evaluation of this model and its order parameter. Different evaluation methods will be performed on this order parameter to show it as a valid indicator of the segregation state of the world in this model, as well as showcase different interesting properties and limitations of the parameters. Such methods will involve plots like Evolution, Phase-Transition, or Linear Regression plots, and the paper will conclude by summing up all the work taken into this project to confirm that this order parameter, with its formulation in this paper, is a valid and interesting one to use.