OpenRaiser/Intern-Atlas huggingface dataset:
3D Anatomical Representations and Analysis: an Application to the Spine
Venue: arXiv cs.GR 2022
Year: 2022

This work proposes a framework for the patient-specific characterization of the spine, which integrates information on the tissues with geometric information on the spine morphology. Key elements are the extraction of 3D patient-specific models of each vertebra and the intervertebral space from 3D CT images, the segmentation of each vertebra in its three functional regions, and the analysis of the tissue condition in the functional regions based on geometrical parameters. The localization of anomalies obtained in the results and the proposed visualization support the applicability of our tool for quantitative and visual evaluation of possible damages, for surgery planning, and early diagnosis or follow-up studies. Finally, we discuss the main properties of the proposed framework in terms of characterisation of the morphology and pathology of the spine on benchmarks of the spine district.
On the parameterized complexity of symmetric directed multicut
Venue: arXiv cs.DS 2022
Year: 2022

We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph $D$, a set of cut requests $C=\{(s_1,t_1),\ldots,(s_\ell,t_\ell)\}$ and an integer $k$, and the task is to find a set $X \subseteq V(D)$ of size at most $k$ such that for every $1 \leq i \leq \ell$, $X$ intersects either all $(s_i,t_i)$-paths or all $(t_i,s_i)$-paths. Equivalently, every strongly connected component of $D-X$ contains at most one vertex out of $s_i$ and $t_i$ for every $i$. This problem is previously known from research in approximation algorithms, where it is known to have an $O(\log k \log \log k)$-approximation. We note that the problem, parameterized by $k$, directly generalizes multiple interesting FPT problems such as (Undirected) Vertex Multicut and Directed Subset Feedback Vertex Set. We are not able to settle the existence of an FPT algorithm parameterized purely by $k$, but we give three partial results: An FPT algorithm parameterized by $k+\ell$; an FPT-time 2-approximation parameterized by $k$; and an FPT algorithm parameterized by $k$ for the special case that the cut requests form a clique, Symmetric Directed Multiway Cut. The existence of an FPT algorithm parameterized purely by $k$ remains an intriguing open possibility.
Challenges in Applying Robotics to Retail Store Management
Venue: arXiv cs.RO 2022
Year: 2022

An autonomous retail store management system entails inventory tracking, store monitoring, and anomaly correction. Recent attempts at autonomous retail store management have faced challenges primarily in perception for anomaly detection, as well as new challenges arising in mobile manipulation for executing anomaly correction. Advances in each of these areas along with system integration are necessary for a scalable solution in this domain.
Machine learning algorithms for three-dimensional mean-curvature computation in the level-set method
Venue: arXiv cs.LG 2022
Year: 2022

We propose a data-driven mean-curvature solver for the level-set method. This work is the natural extension to $\mathbb{R}^3$ of our two-dimensional strategy in [DOI: 10.1007/s10915-022-01952-2][1] and the hybrid inference system of [DOI: 10.1016/j.jcp.2022.111291][2]. However, in contrast to [1,2], which built resolution-dependent neural-network dictionaries, here we develop a pair of models in $\mathbb{R}^3$, regardless of the mesh size. Our feedforward networks ingest transformed level-set, gradient, and curvature data to fix numerical mean-curvature approximations selectively for interface nodes. To reduce the problem's complexity, we have used the Gaussian curvature to classify stencils and fit our models separately to non-saddle and saddle patterns. Non-saddle stencils are easier to handle because they exhibit a curvature error distribution characterized by monotonicity and symmetry. While the latter has allowed us to train only on half the mean-curvature spectrum, the former has helped us blend the data-driven and the baseline estimations seamlessly near flat regions. On the other hand, the saddle-pattern error structure is less clear; thus, we have exploited no latent information beyond what is known. In this regard, we have trained our models on not only spherical but also sinusoidal and hyperbolic paraboloidal patches. Our approach to building their data sets is systematic but gleans samples randomly while ensuring well-balancedness. We have also resorted to standardization and dimensionality reduction and integrated regularization to minimize outliers. In addition, we leverage curvature rotation/reflection invariance to improve precision at inference time. Several experiments confirm that our proposed system can yield more accurate mean-curvature estimations than modern particle-based interface reconstruction and level-set schemes around under-resolved regions.
Out-of-distribution Detection via Frequency-regularized Generative Models
Venue: arXiv cs.LG 2022
Year: 2022

Modern deep generative models can assign high likelihood to inputs drawn from outside the training distribution, posing threats to models in open-world deployments. While much research attention has been placed on defining new test-time measures of OOD uncertainty, these methods do not fundamentally change how deep generative models are regularized and optimized in training. In particular, generative models are shown to overly rely on the background information to estimate the likelihood. To address the issue, we propose a novel frequency-regularized learning FRL framework for OOD detection, which incorporates high-frequency information into training and guides the model to focus on semantically relevant features. FRL effectively improves performance on a wide range of generative architectures, including variational auto-encoder, GLOW, and PixelCNN++. On a new large-scale evaluation task, FRL achieves the state-of-the-art performance, outperforming a strong baseline Likelihood Regret by 10.7% (AUROC) while achieving 147$\times$ faster inference speed. Extensive ablations show that FRL improves the OOD detection performance while preserving the image generation quality. Code is available at https://github.com/mu-cai/FRL.
Part-aware Prototypical Graph Network for One-shot Skeleton-based Action Recognition
Venue: arXiv cs.CV 2022
Year: 2022

In this paper, we study the problem of one-shot skeleton-based action recognition, which poses unique challenges in learning transferable representation from base classes to novel classes, particularly for fine-grained actions. Existing meta-learning frameworks typically rely on the body-level representations in spatial dimension, which limits the generalisation to capture subtle visual differences in the fine-grained label space. To overcome the above limitation, we propose a part-aware prototypical representation for one-shot skeleton-based action recognition. Our method captures skeleton motion patterns at two distinctive spatial levels, one for global contexts among all body joints, referred to as body level, and the other attends to local spatial regions of body parts, referred to as the part level. We also devise a class-agnostic attention mechanism to highlight important parts for each action class. Specifically, we develop a part-aware prototypical graph network consisting of three modules: a cascaded embedding module for our dual-level modelling, an attention-based part fusion module to fuse parts and generate part-aware prototypes, and a matching module to perform classification with the part-aware representations. We demonstrate the effectiveness of our method on two public skeleton-based action recognition datasets: NTU RGB+D 120 and NW-UCLA.
Revisiting Maximum Satisfiability and Related Problems in Data Streams
Venue: arXiv cs.DS 2022
Year: 2022

We revisit the MaxSAT problem in the data stream model. In this problem, the stream consists of $m$ clauses that are disjunctions of literals drawn from $n$ Boolean variables. The objective is to find an assignment to the variables that maximizes the number of satisfied clauses. Chou et al. (FOCS 2020) showed that $Ω(\sqrt{n})$ space is necessary to yield a $\sqrt{2}/2+ε$ approximation of the optimum value; they also presented an algorithm that yields a $\sqrt{2}/2-ε$ approximation of the optimum value using $O(\log n/ε^2)$ space. In this paper, we focus not only on approximating the optimum value, but also on obtaining the corresponding Boolean assignment using sublinear $o(mn)$ space. We present randomized single-pass algorithms that w.h.p. yield: 1) A $1-ε$ approximation using $\tilde{O}(n/ε^3)$ space and exponential post-processing time and 2) A $3/4-ε$ approximation using $\tilde{O}(n/ε)$ space and polynomial post-processing time. Our ideas also extend to dynamic streams. On the other hand, we show that the streaming kSAT problem that asks to decide whether one can satisfy all size-$k$ input clauses must use $Ω(n^k)$ space. We also consider other related problems in this setting.
ACO based Adaptive RBFN Control for Robot Manipulators
Venue: arXiv cs.RO 2022
Year: 2022

This paper describes a new approach for approximating the inverse kinematics of a manipulator using an Ant Colony Optimization (ACO) based RBFN (Radial Basis Function Network). In this paper, a training solution using the ACO and the LMS (Least Mean Square) algorithm is presented in a two-phase training procedure. To settle the problem that the cluster results of k-mean clustering Radial Basis Function (RBF) are easy to be influenced by the selection of initial characters and converge to a local minimum, Ant Colony Optimization (ACO) for the RBF neural networks which will optimize the center of RBF neural networks and reduce the number of the hidden layer neurons nodes is presented. The result demonstrates that the accuracy of Ant Colony Optimization for the Radial Basis Function (RBF) neural networks is higher, and the extent of fitting has been improved.
Shift Variance in Scene Text Detection
Venue: arXiv cs.CV 2022
Year: 2022

Theory of convolutional neural networks suggests the property of shift equivariance, i.e., that a shifted input causes an equally shifted output. In practice, however, this is not always the case. This poses a great problem for scene text detection for which a consistent spatial response is crucial, irrespective of the position of the text in the scene. Using a simple synthetic experiment, we demonstrate the inherent shift variance of a state-of-the-art fully convolutional text detector. Furthermore, using the same experimental setting, we show how small architectural changes can lead to an improved shift equivariance and less variation of the detector output. We validate the synthetic results using a real-world training schedule on the text detection network. To quantify the amount of shift variability, we propose a metric based on well-established text detection benchmarks. While the proposed architectural changes are not able to fully recover shift equivariance, adding smoothing filters can substantially improve shift consistency on common text datasets. Considering the potentially large impact of small shifts, we propose to extend the commonly used text detection metrics by the metric described in this work, in order to be able to quantify the consistency of text detectors.
A Pragmatic Methodology for Blind Hardware Trojan Insertion in Finalized Layouts
Venue: arXiv cs.CR 2022
Year: 2022

A potential vulnerability for integrated circuits (ICs) is the insertion of hardware trojans (HTs) during manufacturing. Understanding the practicability of such an attack can lead to appropriate measures for mitigating it. In this paper, we demonstrate a pragmatic framework for analyzing HT susceptibility of finalized layouts. Our framework is representative of a fabrication-time attack, where the adversary is assumed to have access only to a layout representation of the circuit. The framework inserts trojans into tapeout-ready layouts utilizing an Engineering Change Order (ECO) flow. The attacked security nodes are blindly searched utilizing reverse-engineering techniques. For our experimental investigation, we utilized three crypto-cores (AES-128, SHA-256, and RSA) and a microcontroller (RISC-V) as targets. We explored 96 combinations of triggers, payloads and targets for our framework. Our findings demonstrate that even in high-density designs, the covert insertion of sophisticated trojans is possible. All this while maintaining the original target logic, with minimal impact on power and performance. Furthermore, from our exploration, we conclude that it is too naive to only utilize placement resources as a metric for HT vulnerability. This work highlights that the HT insertion success is a complex function of the placement, routing resources, the position of the attacked nodes, and further design-specific characteristics. As a result, our framework goes beyond just an attack, we present the most advanced analysis tool to assess the vulnerability of HT insertion into finalized layouts.
Scaling Blockchains with Error Correction Codes: A Survey on Coded Blockchains
Venue: arXiv cs.DC 2022
Year: 2022

This paper reviews and highlights how coding schemes have been used to solve various problems in blockchain systems. Specifically, these problems relate to scaling blockchains in terms of their data storage, computation and communication cost, as well as security. To this end, this paper considers the use of coded blocks or shards that allows participants to store only a fraction of the total blockchain, protect against malicious nodes or erasures due to nodes leaving a blockchain system, ensure data availability in order to promote transparency, and scale the security of sharded blockchains. Further, it helps reduce communication cost when disseminating blocks, which is critical to bootstrapping new nodes and helps speed up consensus of blocks. For each category of solutions, we highlight problems and issues that motivated their designs and use of coding. Moreover, we provide a qualitative analysis of their storage, communication and computation cost.
Awaiting for Godot: Stateless Model Checking that Avoids Executions where Nothing Happens
Venue: arXiv cs.SE 2022
Year: 2022

Stateless Model Checking (SMC) is a verification technique for concurrent programs that checks for safety violations by exploring all possible thread schedulings. It is highly effective when coupled with Dynamic Partial Order Reduction (DPOR), which introduces an equivalence on schedulings and need explore only one in each equivalence class. Even with DPOR, SMC often spends unnecessary effort in exploring loop iterations that are pure, i.e., have no effect on the program state. We present techniques for making SMC with DPOR more effective on programs with pure loop iterations. The first is a static program analysis to detect loop purity and an associated program transformation, called Partial Loop Purity Elimination, that inserts assume statements to block pure loop iterations. Subsequently, some of these assumes are turned into await statements that completely remove many assume-blocked executions. Finally, we present an extension of the standard DPOR equivalence, obtained by weakening the conflict relation between events. All these techniques are incorporated into a new DPOR algorithm, Optimal-DPOR-Await, which can handle both awaits and the weaker conflict relation, is optimal in the sense that it explores exactly one execution in each equivalence class, and can also diagnose livelocks. Our implementation in Nidhugg shows that these techniques can significantly speed up the analysis of concurrent programs that are currently challenging for SMC tools, both for exploring their complete set of interleavings, but even for detecting concurrency errors in them.
A heuristic algorithm for straight-line embedding of a hamiltonian cycle onto a given set of points inside simple polygons
Venue: arXiv cs.CG 2022
Year: 2022

This paper investigated the problem of embedding a simple Hamiltonian Cycle with n vertices on n points inside a simple polygon. This problem seeks to embed a straight-line cycle (without bends), which does not intersect either itself or the sides of the polygon, i.e., it is planar. This problem is a special case of an open problem to find a simple Hamiltonian (s, X, t)-path (a simple path that starts at s and ends at t, where s, t, and all other vertices within the path are a member of set X) inside a simple polygon, which does not intersect itself or the sides of the polygon. The complexity of the problem in this paper is not verified yet, and it is an open problem. However, similar problems are resolved that are NP-Complete. A heuristic algorithm with time complexity of O(r(n2m + n3)) and space complexity of O(n2 + m) is proposed to solve the problem.
Blockchain-based traffic management for Advanced Air Mobility
Venue: arXiv cs.MA 2022
Year: 2022

The large public interest in Advanced Air Mobility (AAM) will soon lead to congested skies overhead cities, analogously to what happened with other transportation means, including commercial aviation. In the latter case, the combination of large distances and demanded number flights is such that a system with centralized control, with most of the decisions made by human operators, is safe. However, for AAM, it is expected a much higher demand, because it will be used for people's daily commutes. Thus, higher automation levels will become a requirement for coordinating this traffic, which might not be effectively managed by humans. The establishment of fixed air routes can abate complexity, however at the cost of limiting capacity and decreasing efficiency. Another alternative is the use of a powerful central system based on Artificial Intelligence (AI), which would allow flexible trajectories and higher efficiency. However, such system would require concentrated investment, could contain Single-Points-of-Failure (SPoFs), would be a highly sought target of malicious attacks, and would be subject to periods of unavailability. This work proposes a new technology that solves the problem of managing the high complexity of the AAM traffic with a secure distributed approach, without the need for a proprietary centralized automation system. This technology enables distributed airspace allocation management and conflict resolution by means of trusted shared data structures and associated smart contracts running on a blockchain ecosystem. This way, it greatly reduces the risk of system outages due to SPoFs, by allowing peer-to-peer conflict resolution, and being more resilient to failures in the ground communication infrastructure. Furthermore, it provides priority-based balancing mechanisms that help to regulate fairness among participants in the utilization of the airspace.
Text to Image Generation: Leaving no Language Behind
Venue: arXiv cs.CL 2022
Year: 2022

One of the latest applications of Artificial Intelligence (AI) is to generate images from natural language descriptions. These generators are now becoming available and achieve impressive results that have been used for example in the front cover of magazines. As the input to the generators is in the form of a natural language text, a question that arises immediately is how these models behave when the input is written in different languages. In this paper we perform an initial exploration of how the performance of three popular text-to-image generators depends on the language. The results show that there is a significant performance degradation when using languages other than English, especially for languages that are not widely used. This observation leads us to discuss different alternatives on how text-to-image generators can be improved so that performance is consistent across different languages. This is fundamental to ensure that this new technology can be used by non-native English speakers and to preserve linguistic diversity.
End-to-end Clinical Event Extraction from Chinese Electronic Health Record
Venue: arXiv cs.CL 2022
Year: 2022

Event extraction is an important work of medical text processing. According to the complex characteristics of medical text annotation, we use the end-to-end event extraction model to enhance the output formatting information of events. Through pre training and fine-tuning, we can extract the attributes of the four dimensions of medical text: anatomical position, subject word, description word and occurrence state. On the test set, the accuracy rate was 0.4511, the recall rate was 0.3928, and the F1 value was 0.42. The method of this model is simple, and it has won the second place in the task of mining clinical discovery events (task2) in the Chinese electronic medical record of the seventh China health information processing Conference (chip2021).
Learning filtered discretization operators: non-intrusive versus intrusive approaches
Venue: arXiv cs.CE 2022
Year: 2022

Simulating multi-scale phenomena such as turbulent fluid flows is typically computationally very expensive. Filtering the smaller scales allows for using coarse discretizations, however, this requires closure models to account for the effects of the unresolved on the resolved scales. The common approach is to filter the continuous equations, but this gives rise to several commutator errors due to nonlinear terms, non-uniform filters, or boundary conditions. We propose a new approach to filtering, where the equations are discretized first and then filtered. For a non-uniform filter applied to the linear convection equation, we show that the discretely filtered convection operator can be inferred using three methods: intrusive (`explicit reconstruction') or non-intrusive operator inference, either via `derivative fitting' or `trajectory fitting' (embedded learning). We show that explicit reconstruction and derivative fitting identify a similar operator and produce small errors, but that trajectory fitting requires significant effort to train to achieve similar performance. However, the explicit reconstruction approach is more prone to instabilities.
Wildfire Forecasting with Satellite Images and Deep Generative Model
Venue: arXiv cs.CV 2022
Year: 2022

Wildfire forecasting has been one of the most critical tasks that humanities want to thrive. It plays a vital role in protecting human life. Wildfire prediction, on the other hand, is difficult because of its stochastic and chaotic properties. We tackled the problem by interpreting a series of wildfire images as a video and used it to anticipate how the fire would behave in the future. However, creating video prediction models that account for the inherent uncertainty of the future is challenging. The bulk of published attempts is based on stochastic image-autoregressive recurrent networks, which raises various performance and application difficulties, such as computational cost and limited efficiency on massive datasets. Another possibility is to use entirely latent temporal models that combine frame synthesis and temporal dynamics. However, due to design and training issues, no such model for stochastic video prediction has yet been proposed in the literature. This paper addresses these issues by introducing a novel stochastic temporal model whose dynamics are driven in a latent space. It naturally predicts video dynamics by allowing our lighter, more interpretable latent model to beat previous state-of-the-art approaches on the GOES-16 dataset. Results will be compared towards various benchmarking models.