TY - THES A1 - Paskin, Martha T1 - Estimating 3D Shape of the Head Skeleton of Basking Sharks Using Annotated Landmarks on a 2D Image N2 - Basking sharks are thought to be one of the most efficient filter-feeding fish in terms of the throughput of water filtered through their gills. Details about the underlying morphology of their branchial region have not been studied due to various challenges in acquiring real-world data. The present thesis aims to facilitate this, by developing a mathematical shape model which constructs the 3D structure of the head skeleton of a basking shark using annotated landmarks on a single 2D image. This is an ill-posed problem as estimating the depth of a 3D object from a single 2D view is, in general, not possible. To reduce this ambiguity, we create a set of pre-defined training shapes in 3D from CT scans of basking sharks. First, the damaged structures of the sharks in the scans are corrected via solving a set of optimization problems, before using them as accurate 3D representations of the object. Then, two approaches are employed for the 2D-to-3D shape fitting problem–an Active Shape Model approach and a Kendall’s Shape Space approach. The former represents a shape as a point on a high-dimensional Euclidean space, whereas the latter represents a shape as an equivalence class of points in this Euclidean space. Kendall’s shape space approach is a novel technique that has not yet been applied in this context, and a comprehensive comparison of the two approaches suggests this approach to be superior for the problem at hand. This can be credited to an improved interpolation of the training shapes. N2 - Riesenhaie zählen zu den effizientesten Filtrierern hinsichtlich des durch die Kiemen gefilterten Wasservolumens. Die Kiemenregion dieser Tiere besitzt eine markante Morphologie, die jedoch bisher nicht umfassend erforscht werden konnte, da es schwierig ist, reale Daten dieser Tiere zu erheben. Die vorliegende Arbeit zielt darauf ab, dies durch die Entwicklung eines mathematischen Formmodels zu ermöglichen, das es erlaubt, die 3D-Struktur des Schädelskeletts anhand von Landmarken, die auf einem 2D-Bild platziert werden, zu rekonstruieren. Die hierzu benötigte Tiefenbestimmung der Landmarken aus einer 2D-Projektion ist ein unterbestimmtes Problem. Wir lösen dies durch die Hinzunahme von Trainingsformen, welche wir aus CT-Scans von Riesenhaien gewinnen. Der Zustand der tomografierten Exemplare erfordert jedoch einen vorhergehenden Korrekturschritt, den wir mit Hilfe eines Optimierungsansatzes lösen, bevor die extrahierten Strukturen als 3D-Trainingsformen dienen können. Um die 3D-Struktur des Schädelskelettes aus 2D-Landmarken zu rekonstruieren, vergleichen wir zwei Ansätze – den sogenannten Active-Shape-Model (ASM)-Ansatz und einen Ansatz basierend auf Kendalls Formenraum. Während eine Form des ASM-Ansatzes durch einen Punkt in einem hochdimensionalen Euklidischen Raum repräsentiert ist, repräsentiert eine Form im Kendall-Formenraum eine Äquivalenzklasse von Punkten des Euklidischen Raumes. Die Anwendung des Kendall-Formenraumes für das beschriebene Problem ist neu und ein umfassender Vergleich der Methoden hat ergeben, dass dieser Ansatz für die spezielle Anwendung zu besseren Ergebnissen führt. Wir führen dies auf die überlegene Interpolation der Trainingsformen in diesem Raum zurück. Y1 - 2022 UR - https://arxiv.org/abs/2207.12687 ER - TY - GEN A1 - Paskin, Martha A1 - Baum, Daniel A1 - Dean, Mason N. A1 - von Tycowicz, Christoph T1 - A Kendall Shape Space Approach to 3D Shape Estimation from 2D Landmarks -- Source Code and Data N2 - Source code and novel dataset of basking shark head skeletons facilitating the reproduction of the results presented in 'A Kendall Shape Space Approach to 3D Shape Estimation from 2D Landmarks' - ECCV 2022. Y1 - 2022 U6 - https://doi.org/10.12752/8730 ER - TY - GEN A1 - Tateiwa, Nariaki A1 - Shinano, Yuji A1 - Yasuda, Masaya A1 - Kaji, Shizuo A1 - Yamamura, Keiichiro A1 - Fujisawa, Katsuki T1 - Massively parallel sharing lattice basis reduction N2 - For cryptanalysis in lattice-based schemes, the performance evaluation of lattice basis reduction using high-performance computers is becoming increasingly important for the determination of the security level. We propose a distributed and asynchronous parallel reduction algorithm based on randomization and DeepBKZ, which is an improved variant of the block Korkine-Zolotarev (BKZ) reduction algorithm. Randomized copies of a lattice basis are distributed to up to 103,680 cores and independently reduced in parallel, while some basis vectors are shared asynchronously among all processes via MPI. There is a trade-off between randomization and information sharing; if a substantial amount of information is shared, all processes will work on the same problem, thereby diminishing the benefit of parallelization. To monitor this balance between randomness and sharing, we propose a metric to quantify the variety of lattice bases. We empirically find an optimal parameter of sharing for high-dimensional lattices. We demonstrate the efficacy of our proposed parallel algorithm and implementation with respect to both performance and scalability through our experiments. T3 - ZIB-Report - 21-38 KW - Discrete optimization KW - Lattice problem KW - Lattice-based cryptography KW - Shortest vector problem KW - Parallel algorithms KW - Ubiquity Generator Framework Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85209 SN - 1438-0064 N1 - under review ER - TY - GEN A1 - Tateiwa, Nariaki A1 - Shinano, Yuji A1 - Yamamura, Keiichiro A1 - Yoshida, Akihiro A1 - Kaji, Shizuo A1 - Yasuda, Masaya A1 - Fujisawa, Katsuki T1 - CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems N2 - Lattice problems are a class of optimization problems that are notably hard. There are no classical or quantum algorithms known to solve these problems efficiently. Their hardness has made lattices a major cryptographic primitive for post-quantum cryptography. Several different approaches have been used for lattice problems with different computational profiles; some suffer from super-exponential time, and others require exponential space. This motivated us to develop a novel lattice problem solver, CMAP-LAP, based on the clever coordination of different algorithms that run massively in parallel. With our flexible framework, heterogeneous modules run asynchronously in parallel on a large-scale distributed system while exchanging information, which drastically boosts the overall performance. We also implement full checkpoint-and-restart functionality, which is vital to high-dimensional lattice problems. Through numerical experiments with up to 103,680 cores, we evaluated the performance and stability of our system and demonstrated its high capability for future massive-scale experiments. T3 - ZIB-Report - 21-16 KW - Discrete optimization KW - Lattice problem KW - Lattice-based cryptography KW - Shortest vector problem KW - Parallel algorithms KW - Ubiquity Generator Framework Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82802 SN - 1438-0064 N1 - Revised version is accepted to HiPC 2021 ER - TY - GEN A1 - Fujii, Koichi A1 - Kim, Sunyoung A1 - Kojima, Masakazu A1 - Mittelmann, Hans D. A1 - Shinano, Yuji T1 - An Exceptionally Difficult Binary Quadratic Optimization Problem with Symmetry: a Challenge for The Largest Unsolved QAP Instance Tai256c N2 - Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. The symmetry induces equivalent subproblems in branch and bound (BB) methods. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the standard orbit branching and a technique to prune equivalent subproblems. With this BB method, a new LB with 1.25% gap is successfully obtained, and computing an LB with 1.0% gap is shown to be still quite difficult. T3 - ZIB-Report - 23-27 Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-93072 SN - 1438-0064 ER -