We introduce graph width parameters, called $\alpha$-edge-crossing width and edge-crossing width. These are defined in terms of the number of edges crossing a bag of a tree-cut decomposition. They are motivated by edge-cut width, recently introduced by Brand et al. (WG 2022). We show that edge-crossing width is equivalent to the known parameter tree-partition-width. On the other hand, $\alpha$-edge-crossing width is a new parameter; tree-cut width and $\alpha$-edge-crossing width are incomparable, and they both lie between tree-partition-width and edge-cut width. We provide an algorithm that, for a given $n$-vertex graph $G$ and integers $k$ and $\alpha$, in time $2^{O((\alpha+k)\log (\alpha+k))}n^2$ either outputs a tree-cut decomposition certifying that the $\alpha$-edge-crossing width of $G$ is at most $2\alpha^2+5k$ or confirms that the $\alpha$-edge-crossing width of $G$ is more than $k$. As applications, for every fixed $\alpha$, we obtain FPT algorithms for the List Coloring and Precoloring Extension problems parameterized by $\alpha$-edge-crossing width. They were known to be W[1]-hard parameterized by tree-partition-width, and FPT parameterized by edge-cut width, and we close the complexity gap between these two parameters.
相關內容
Our work introduces the YCB-Ev dataset, which contains synchronized RGB-D frames and event data that enables evaluating 6DoF object pose estimation algorithms using these modalities. This dataset provides ground truth 6DoF object poses for the same 21 YCB objects \cite{calli2017yale} that were used in the YCB-Video (YCB-V) dataset, enabling the evaluation of algorithm performance when transferred across datasets. The dataset consists of 21 synchronized event and RGB-D sequences, amounting to a total of 7:43 minutes of video. Notably, 12 of these sequences feature the same object arrangement as the YCB-V subset used in the BOP challenge. Our dataset is the first to provide ground truth 6DoF pose data for event streams. Furthermore, we evaluate the generalization capabilities of two state-of-the-art algorithms, which were pre-trained for the BOP challenge, using our novel YCB-V sequences. The proposed dataset is available at //github.com/paroj/ycbev.
A time-space traffic (TS) diagram, which presents traffic states in time-space cells with color, is an important traffic analysis and visualization tool. Despite its importance for transportation research and engineering, most TS diagrams that have already existed or are being produced are too coarse to exhibit detailed traffic dynamics due to the limitations of existing information technology and traffic infrastructure investment. To increase the resolution of a TS diagram and enable it to present ample traffic details, this paper introduces the TS diagram refinement problem and proposes a multiple linear regression-based model to solve the problem. Two tests, which attempt to increase the resolution of a TS diagram 4 and 16 times, are carried out to evaluate the performance of the proposed model. Data collected at different times, in different locations and even in different countries are employed to thoroughly evaluate the accuracy and transferability of the proposed model. Strict tests with diverse data show that the proposed model, despite its simplicity, is able to refine a TS diagram with promising accuracy and reliable transferability. The proposed refinement model will "save" widely existing TS diagrams from their blurry "faces" and enable TS diagrams to show more traffic details.
Whole slide image (WSI) processing is becoming part of the key components of standard clinical diagnosis for various diseases. However, the direct application of conventional image processing algorithms to WSI faces certain obstacles because of WSIs' distinct property: the super-high resolution. The performance of most WSI-related tasks relies on the efficacy of the backbone which extracts WSI patch feature representations. Hence, we proposed BROW, a foundation model for extracting better feature representations for WSIs, which can be conveniently adapted to downstream tasks without or with slight fine-tuning. The model takes transformer architecture, pretrained using self-distillation framework. To improve model's robustness, techniques such as patch shuffling have been employed. Additionally, the model leverages the unique properties of WSIs, utilizing WSI's multi-scale pyramid to incorporate an additional global view, thereby further enhancing its performance. We used both private and public data to make up a large pretraining dataset, containing more than 11000 slides, over 180M extracted patches, encompassing WSIs related to various organs and tissues. To assess the effectiveness of \ourmodel, we run a wide range of downstream tasks, including slide-level subtyping, patch-level classification and nuclei instance segmentation. The results confirmed the efficacy, robustness and good generalization ability of the proposed model. This substantiates its potential as foundation model for WSI feature extraction and highlights promising prospects for its application in WSI processing.
The Johnson--Lindenstrauss (JL) lemma is a powerful tool for dimensionality reduction in modern algorithm design. The lemma states that any set of high-dimensional points in a Euclidean space can be flattened to lower dimensions while approximately preserving pairwise Euclidean distances. Random matrices satisfying this lemma are called JL transforms (JLTs). Inspired by existing $s$-hashing JLTs with exactly $s$ nonzero elements on each column, the present work introduces an ensemble of sparse matrices encompassing so-called $s$-hashing-like matrices whose expected number of nonzero elements on each column is~$s$. The independence of the sub-Gaussian entries of these matrices and the knowledge of their exact distribution play an important role in their analyses. Using properties of independent sub-Gaussian random variables, these matrices are demonstrated to be JLTs, and their smallest and largest singular values are estimated non-asymptotically using a technique from geometric functional analysis. As the dimensions of the matrix grow to infinity, these singular values are proved to converge almost surely to fixed quantities (by using the universal Bai--Yin law), and in distribution to the Gaussian orthogonal ensemble (GOE) Tracy--Widom law after proper rescalings. Understanding the behaviors of extreme singular values is important in general because they are often used to define a measure of stability of matrix algorithms. For example, JLTs were recently used in derivative-free optimization algorithmic frameworks to select random subspaces in which are constructed random models or poll directions to achieve scalability, whence estimating their smallest singular value in particular helps determine the dimension of these subspaces.
The convergence analysis for least-squares finite element methods led to various adaptive mesh-refinement strategies: Collective marking algorithms driven by the built-in a posteriori error estimator or an alternative explicit residual-based error estimator as well as a separate marking strategy based on the alternative error estimator and an optimal data approximation algorithm. This paper reviews and discusses available convergence results. In addition, all three strategies are investigated empirically for a set of benchmarks examples of second-order elliptic partial differential equations in two spatial dimensions. Particular interest is on the choice of the marking and refinement parameters and the approximation of the given data. The numerical experiments are reproducible using the author's software package octAFEM available on the platform Code Ocean.
While text-conditional 3D object generation and manipulation have seen rapid progress, the evaluation of coherence between generated 3D shapes and input textual descriptions lacks a clear benchmark. The reason is twofold: a) the low quality of the textual descriptions in the only publicly available dataset of text-shape pairs; b) the limited effectiveness of the metrics used to quantitatively assess such coherence. In this paper, we propose a comprehensive solution that addresses both weaknesses. Firstly, we employ large language models to automatically refine textual descriptions associated with shapes. Secondly, we propose a quantitative metric to assess text-to-shape coherence, through cross-attention mechanisms. To validate our approach, we conduct a user study and compare quantitatively our metric with existing ones. The refined dataset, the new metric and a set of text-shape pairs validated by the user study comprise a novel, fine-grained benchmark that we publicly release to foster research on text-to-shape coherence of text-conditioned 3D generative models. Benchmark available at //cvlab-unibo.github.io/CrossCoherence-Web/.
Automatic few-shot font generation (AFFG), aiming at generating new fonts with only a few glyph references, reduces the labor cost of manually designing fonts. However, the traditional AFFG paradigm of style-content disentanglement cannot capture the diverse local details of different fonts. So, many component-based approaches are proposed to tackle this problem. The issue with component-based approaches is that they usually require special pre-defined glyph components, e.g., strokes and radicals, which is infeasible for AFFG of different languages. In this paper, we present a novel font generation approach by aggregating styles from character similarity-guided global features and stylized component-level representations. We calculate the similarity scores of the target character and the referenced samples by measuring the distance along the corresponding channels from the content features, and assigning them as the weights for aggregating the global style features. To better capture the local styles, a cross-attention-based style transfer module is adopted to transfer the styles of reference glyphs to the components, where the components are self-learned discrete latent codes through vector quantization without manual definition. With these designs, our AFFG method could obtain a complete set of component-level style representations, and also control the global glyph characteristics. The experimental results reflect the effectiveness and generalization of the proposed method on different linguistic scripts, and also show its superiority when compared with other state-of-the-art methods. The source code can be found at //github.com/awei669/VQ-Font.
The physical and textural attributes of objects have been widely studied for recognition, detection and segmentation tasks in computer vision.~A number of datasets, such as large scale ImageNet, have been proposed for feature learning using data hungry deep neural networks and for hand-crafted feature extraction. To intelligently interact with objects, robots and intelligent machines need the ability to infer beyond the traditional physical/textural attributes, and understand/learn visual cues, called visual affordances, for affordance recognition, detection and segmentation. To date there is no publicly available large dataset for visual affordance understanding and learning. In this paper, we introduce a large scale multi-view RGBD visual affordance learning dataset, a benchmark of 47210 RGBD images from 37 object categories, annotated with 15 visual affordance categories. To the best of our knowledge, this is the first ever and the largest multi-view RGBD visual affordance learning dataset. We benchmark the proposed dataset for affordance segmentation and recognition tasks using popular Vision Transformer and Convolutional Neural Networks. Several state-of-the-art deep learning networks are evaluated each for affordance recognition and segmentation tasks. Our experimental results showcase the challenging nature of the dataset and present definite prospects for new and robust affordance learning algorithms. The dataset is publicly available at //sites.google.com/view/afaqshah/dataset.
An adjacency-crossing graph is a graph that can be drawn such that every two edges that cross the same edge share a common endpoint. We show that the number of edges in an $n$-vertex adjacency-crossing graph is at most $5n-10$. If we require the edges to be drawn as straight-line segments, then this upper bound becomes $5n-11$. Both of these bounds are tight. The former result also follows from a very recent and independent work of Cheong et al.\cite{cheong2023weakly} who showed that the maximum size of weakly and strongly fan-planar graphs coincide. By combining this result with the bound of Kaufmann and Ueckerdt\cite{KU22} on the size of strongly fan-planar graphs and results of Brandenburg\cite{Br20} by which the maximum size of adjacency-crossing graphs equals the maximum size of fan-crossing graphs which in turn equals the maximum size of weakly fan-planar graphs, one obtains the same bound on the size of adjacency-crossing graphs. However, the proof presented here is different, simpler and direct.
Hashing has been widely used in approximate nearest search for large-scale database retrieval for its computation and storage efficiency. Deep hashing, which devises convolutional neural network architecture to exploit and extract the semantic information or feature of images, has received increasing attention recently. In this survey, several deep supervised hashing methods for image retrieval are evaluated and I conclude three main different directions for deep supervised hashing methods. Several comments are made at the end. Moreover, to break through the bottleneck of the existing hashing methods, I propose a Shadow Recurrent Hashing(SRH) method as a try. Specifically, I devise a CNN architecture to extract the semantic features of images and design a loss function to encourage similar images projected close. To this end, I propose a concept: shadow of the CNN output. During optimization process, the CNN output and its shadow are guiding each other so as to achieve the optimal solution as much as possible. Several experiments on dataset CIFAR-10 show the satisfying performance of SRH.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191