Search

The unconstrained binary quadratic programming (UBQP) problem is a class of problems of significant importance in many practical applications, such as in combinatorial optimization, circuit design, and other fields. The positive semidefinite penalty (PSDP) method originated from research on semidefinite relaxation, where the introduction of an exact penalty function improves the efficiency and accuracy of problem solving. In this paper, we propose a vectorized PSDP method for solving the UBQP problem, which optimizes computational efficiency by vectorizing matrix variables within a PSDP framework. Algorithmic enhancements in penalty updating and initialization are implemented, along with the introduction of two algorithms that integrate the proximal point algorithm and the projection alternating BB method for subproblem resolution. Properties of the penalty function and algorithm convergence are analyzed. Numerical experiments show the superior performance of the method in providing high-quality solutions and satisfactory solution times compared to the semidefinite relaxation method and other established methods., Comment: 19 pages, 2 figures

Domain Adaptation (DA) is important for deep learning-based medical image segmentation models to deal with testing images from a new target domain. As the source-domain data are usually unavailable when a trained model is deployed at a new center, Source-Free Domain Adaptation (SFDA) is appealing for data and annotation-efficient adaptation to the target domain. However, existing SFDA methods have a limited performance due to lack of sufficient supervision with source-domain images unavailable and target-domain images unlabeled. We propose a novel Uncertainty-aware Pseudo Label guided (UPL) SFDA method for medical image segmentation. Specifically, we propose Target Domain Growing (TDG) to enhance the diversity of predictions in the target domain by duplicating the pre-trained model's prediction head multiple times with perturbations. The different predictions in these duplicated heads are used to obtain pseudo labels for unlabeled target-domain images and their uncertainty to identify reliable pseudo labels. We also propose a Twice Forward pass Supervision (TFS) strategy that uses reliable pseudo labels obtained in one forward pass to supervise predictions in the next forward pass. The adaptation is further regularized by a mean prediction-based entropy minimization term that encourages confident and consistent results in different prediction heads. UPL-SFDA was validated with a multi-site heart MRI segmentation dataset, a cross-modality fetal brain segmentation dataset, and a 3D fetal tissue segmentation dataset. It improved the average Dice by 5.54, 5.01 and 6.89 percentage points for the three tasks compared with the baseline, respectively, and outperformed several state-of-the-art SFDA methods., Comment: 12 pages, 6 figures, to be published on IEEE TMI

Given two $k$-uniform hypergraphs $F$ and $G$, we say that $G$ has an $F$-covering if for every vertex in $G$ there is a copy of $F$ covering it. For $1\leq i\leq k-1$, the minimum $i$-degree $\delta_i(G)$ of $G$ is the minimum integer such that every $i$ vertices are contained in at least $\delta_i(G)$ edges. Let $c_i(n,F)$ be the largest minimum $i$-degree among all $n$-vertex $k$-uniform hypergraphs that have no $F$-covering. In this paper, we consider the $F$-covering problem in $3$-uniform hypergraphs when $F$ is the generalized triangle $T$, where $T$ is a $3$-uniform hypergraph with the vertex set $\{v_1,v_2,v_3,v_4,v_5\}$ and the edge set $\{\{v_{1}v_{2}v_{3}\},\{v_{1}v_{2}v_{4}\},\{v_{3}v_{4}v_{5}\}\}$. We give the exact value of $c_2(n,T)$ and asymptotically determine $c_1(n,T)$. We also consider the $F$-covering problem in $3$-uniform hypergraphs when $F$ are some trees, such as the linear $k$-path $P_k$ and the star $S_k$. Especially, we provide bounds of $c_i(n,P_k)$ and $c_i(n,S_k)$ for $k\geq 3$, where $i=1,2$.

An $(n,s,q)$-graph is an $n$-vertex multigraph in which every $s$-set of vertices spans at most $q$ edges. Erd\H{o}s initiated the study of maximum number of edges of $(n,s,q)$-graphs, and the extremal problem on multigraphs has been considered since the 1990s. The problem of determining the maximum product of the edge multiplicities in $(n,s,q)$-graphs was posed by Mubayi and Terry in 2019. Recently, Day, Falgas-Ravry and Treglown settled a conjecture of Mubayi and Terry on the case $(s,q)=(4, 6a + 3)$ of the problem (for $a \ge 2$), and they gave a general lower bound construction for the extremal problem for many pairs $(s, q)$, which they conjectured is asymptotically best possible. Their conjecture was confirmed exactly or asymptotically for some specific cases. In this paper, we consider the case that $(s,q)=(5,\binom{5}{2}a+4)$ and $d=2$ of their conjecture, partially solve an open problem raised by Day, Falgas-Ravry and Treglown. We also show that the conjecture fails for $n=6$, which indicates for the case that $(s,q)=(5,\binom{5}{2}a+4)$ and $d=2$, $n$ needs to be sufficiently large for the conjecture to hold.

Generalization to previously unseen images with potential domain shifts and different styles is essential for clinically applicable medical image segmentation, and the ability to disentangle domain-specific and domain-invariant features is key for achieving Domain Generalization (DG). However, existing DG methods can hardly achieve effective disentanglement to get high generalizability. To deal with this problem, we propose an efficient Contrastive Domain Disentanglement and Style Augmentation (CDDSA) framework for generalizable medical image segmentation. First, a disentangle network is proposed to decompose an image into a domain-invariant anatomical representation and a domain-specific style code, where the former is sent to a segmentation model that is not affected by the domain shift, and the disentangle network is regularized by a decoder that combines the anatomical and style codes to reconstruct the input image. Second, to achieve better disentanglement, a contrastive loss is proposed to encourage the style codes from the same domain and different domains to be compact and divergent, respectively. Thirdly, to further improve generalizability, we propose a style augmentation method based on the disentanglement representation to synthesize images in various unseen styles with shared anatomical structures. Our method was validated on a public multi-site fundus image dataset for optic cup and disc segmentation and an in-house multi-site Nasopharyngeal Carcinoma Magnetic Resonance Image (NPC-MRI) dataset for nasopharynx Gross Tumor Volume (GTVnx) segmentation. Experimental results showed that the proposed CDDSA achieved remarkable generalizability across different domains, and it outperformed several state-of-the-art methods in domain-generalizable segmentation., Comment: 14 pages, 8 figures

Background and Objective: Open-source deep learning toolkits are one of the driving forces for developing medical image segmentation models. Existing toolkits mainly focus on fully supervised segmentation and require full and accurate pixel-level annotations that are time-consuming and difficult to acquire for segmentation tasks, which makes learning from imperfect labels highly desired for reducing the annotation cost. We aim to develop a new deep learning toolkit to support annotation-efficient learning for medical image segmentation. Methods: Our proposed toolkit named PyMIC is a modular deep learning library for medical image segmentation tasks. In addition to basic components that support development of high-performance models for fully supervised segmentation, it contains several advanced components tailored for learning from imperfect annotations, such as loading annotated and unannounced images, loss functions for unannotated, partially or inaccurately annotated images, and training procedures for co-learning between multiple networks, etc. PyMIC supports development of semi-supervised, weakly supervised and noise-robust learning methods for medical image segmentation. Results: We present several illustrative medical image segmentation tasks based on PyMIC: (1) Achieving competitive performance on fully supervised learning; (2) Semi-supervised cardiac structure segmentation with only 10% training images annotated; (3) Weakly supervised segmentation using scribble annotations; and (4) Learning from noisy labels for chest radiograph segmentation. Conclusions: The PyMIC toolkit is easy to use and facilitates efficient development of medical image segmentation models with imperfect annotations. It is modular and flexible, which enables researchers to develop high-performance models with low annotation cost. The source code is available at: https://github.com/HiLab-git/PyMIC., Comment: 12 pages, 6 figures

Convolutional Neural Networks (CNNs) have achieved state-of-the-art performance for medical image segmentation, yet need plenty of manual annotations for training. Semi-Supervised Learning (SSL) methods are promising to reduce the requirement of annotations, but their performance is still limited when the dataset size and the number of annotated images are small. Leveraging existing annotated datasets with similar anatomical structures to assist training has a potential for improving the model's performance. However, it is further challenged by the cross-anatomy domain shift due to the different appearance and even imaging modalities from the target structure. To solve this problem, we propose Contrastive Semi-supervised learning for Cross Anatomy Domain Adaptation (CS-CADA) that adapts a model to segment similar structures in a target domain, which requires only limited annotations in the target domain by leveraging a set of existing annotated images of similar structures in a source domain. We use Domain-Specific Batch Normalization (DSBN) to individually normalize feature maps for the two anatomical domains, and propose a cross-domain contrastive learning strategy to encourage extracting domain invariant features. They are integrated into a Self-Ensembling Mean-Teacher (SE-MT) framework to exploit unlabeled target domain images with a prediction consistency constraint. Extensive experiments show that our CS-CADA is able to solve the challenging cross-anatomy domain shift problem, achieving accurate segmentation of coronary arteries in X-ray images with the help of retinal vessel images and cardiac MR images with the help of fundus images, respectively, given only a small number of annotations in the target domain., Comment: 12 pages, 6 figures

In clinical practice, a segmentation network is often required to continually learn on a sequential data stream from multiple sites rather than a consolidated set, due to the storage cost and privacy restriction. However, during the continual learning process, existing methods are usually restricted in either network memorizability on previous sites or generalizability on unseen sites. This paper aims to tackle the challenging problem of Synchronous Memorizability and Generalizability (SMG) and to simultaneously improve performance on both previous and unseen sites, with a novel proposed SMG-learning framework. First, we propose a Synchronous Gradient Alignment (SGA) objective, which not only promotes the network memorizability by enforcing coordinated optimization for a small exemplar set from previous sites (called replay buffer), but also enhances the generalizability by facilitating site-invariance under simulated domain shift. Second, to simplify the optimization of SGA objective, we design a Dual-Meta algorithm that approximates the SGA objective as dual meta-objectives for optimization without expensive computation overhead. Third, for efficient rehearsal, we configure the replay buffer comprehensively considering additional inter-site diversity to reduce redundancy. Experiments on prostate MRI data sequentially acquired from six institutes demonstrate that our method can simultaneously achieve higher memorizability and generalizability over state-of-the-art methods. Code is available at https://github.com/jingyzhang/SMG-Learning., Comment: Early accepted in MICCAI2022

Efficiently utilizing discriminative features is crucial for convolutional neural networks to achieve remarkable performance in medical image segmentation and is also important for model generalization across multiple domains, where letting model recognize domain-specific and domain-invariant information among multi-site datasets is a reasonable strategy for domain generalization. Unfortunately, most of the recent disentangle networks are not directly adaptable to unseen-domain datasets because of the limitations of offered data distribution. To tackle this deficiency, we propose Contrastive Domain Disentangle (CDD) network for generalizable medical image segmentation. We first introduce a disentangle network to decompose medical images into an anatomical representation factor and a modality representation factor. Then, a style contrastive loss is proposed to encourage the modality representations from the same domain to distribute as close as possible while different domains are estranged from each other. Finally, we propose a domain augmentation strategy that can randomly generate new domains for model generalization training. Experimental results on multi-site fundus image datasets for optic cup and disc segmentation show that the CDD has good model generalization. Our proposed CDD outperforms several state-of-the-art methods in domain generalizable segmentation., Comment: 10 pages, 2 figures

Active set method aims to find the correct active set of the optimal solution and it is a powerful method for solving strictly convex quadratic problem with bound constraints. To guarantee the finite step convergence, the existing active set methods all need strict conditions or some additional strategies, which greatly affect the efficiency of the algorithm. In this paper, we propose a random active set method which introduces randomness in the update of active set. We prove that it can converge in finite iterations with probability one without any conditions on the problem or any additional strategies. Numerical results show that the algorithm obtains the correct active set within a few iterations, and compared with the existing methods, it has better robustness and efficiency., Comment: 17 pages, 4 figures

Deep neural networks usually require accurate and a large number of annotations to achieve outstanding performance in medical image segmentation. One-shot segmentation and weakly-supervised learning are promising research directions that lower labeling effort by learning a new class from only one annotated image and utilizing coarse labels instead, respectively. Previous works usually fail to leverage the anatomical structure and suffer from class imbalance and low contrast problems. Hence, we present an innovative framework for 3D medical image segmentation with one-shot and weakly-supervised settings. Firstly a propagation-reconstruction network is proposed to project scribbles from annotated volume to unlabeled 3D images based on the assumption that anatomical patterns in different human bodies are similar. Then a dual-level feature denoising module is designed to refine the scribbles based on anatomical- and pixel-level features. After expanding the scribbles to pseudo masks, we could train a segmentation model for the new class with the noisy label training strategy. Experiments on one abdomen and one head-and-neck CT dataset show the proposed method obtains significant improvement over the state-of-the-art methods and performs robustly even under severe class imbalance and low contrast.

Domain generalizable model is attracting increasing attention in medical image analysis since data is commonly acquired from different institutes with various imaging protocols and scanners. To tackle this challenging domain generalization problem, we propose a Domain Composition and Attention-based network (DCA-Net) to improve the ability of domain representation and generalization. First, we present a domain composition method that represents one certain domain by a linear combination of a set of basis representations (i.e., a representation bank). Second, a novel plug-and-play parallel domain preceptor is proposed to learn these basis representations and we introduce a divergence constraint function to encourage the basis representations to be as divergent as possible. Then, a domain attention module is proposed to learn the linear combination coefficients of the basis representations. The result of linear combination is used to calibrate the feature maps of an input image, which enables the model to generalize to different and even unseen domains. We validate our method on public prostate MRI dataset acquired from six different institutions with apparent domain shift. Experimental results show that our proposed model can generalize well on different and even unseen domains and it outperforms state-of-the-art methods on the multi-domain prostate segmentation task., Comment: Accepted by MICCAI 2021

The segmentation of coronary arteries by convolutional neural network is promising yet requires a large amount of labor-intensive manual annotations. Transferring knowledge from retinal vessels in widely-available public labeled fundus images (FIs) has a potential to reduce the annotation requirement for coronary artery segmentation in X-ray angiograms (XAs) due to their common tubular structures. However, it is challenged by the cross-anatomy domain shift due to the intrinsically different vesselness characteristics in different anatomical regions under even different imaging protocols. To solve this problem, we propose a Semi-Supervised Cross-Anatomy Domain Adaptation (SS-CADA) which requires only limited annotations for coronary arteries in XAs. With the supervision from a small number of labeled XAs and publicly available labeled FIs, we propose a vesselness-specific batch normalization (VSBN) to individually normalize feature maps for them considering their different cross-anatomic vesselness characteristics. In addition, to further facilitate the annotation efficiency, we employ a self-ensembling mean-teacher (SEMT) to exploit abundant unlabeled XAs by imposing a prediction consistency constraint. Extensive experiments show that our SS-CADA is able to solve the challenging cross-anatomy domain shift, achieving accurate segmentation for coronary arteries given only a small number of labeled XAs.

Nasopharyngeal Carcinoma (NPC) is a leading form of Head-and-Neck (HAN) cancer in the Arctic, China, Southeast Asia, and the Middle East/North Africa. Accurate segmentation of Organs-at-Risk (OAR) from Computed Tomography (CT) images with uncertainty information is critical for effective planning of radiation therapy for NPC treatment. Despite the stateof-the-art performance achieved by Convolutional Neural Networks (CNNs) for automatic segmentation of OARs, existing methods do not provide uncertainty estimation of the segmentation results for treatment planning, and their accuracy is still limited by several factors, including the low contrast of soft tissues in CT, highly imbalanced sizes of OARs and large inter-slice spacing. To address these problems, we propose a novel framework for accurate OAR segmentation with reliable uncertainty estimation. First, we propose a Segmental Linear Function (SLF) to transform the intensity of CT images to make multiple organs more distinguishable than existing methods based on a simple window width/level that often gives a better visibility of one organ while hiding the others. Second, to deal with the large inter-slice spacing, we introduce a novel 2.5D network (named as 3D-SepNet) specially designed for dealing with clinic HAN CT scans with anisotropic spacing. Thirdly, existing hardness-aware loss function often deal with class-level hardness, but our proposed attention to hard voxels (ATH) uses a voxel-level hardness strategy, which is more suitable to dealing with some hard regions despite that its corresponding class may be easy. Our code is now available at https://github.com/HiLab-git/SepNet., Comment: Accepted by Neurocomputing

Radiotherapy is the main treatment modality for nasopharynx cancer. Delineation of Gross Target Volume (GTV) from medical images such as CT and MRI images is a prerequisite for radiotherapy. As manual delineation is time-consuming and laborious, automatic segmentation of GTV has a potential to improve this process. Currently, most of the deep learning-based automatic delineation methods of GTV are mainly performed on medical images like CT images. However, it is challenged by the low contrast between the pathology regions and surrounding soft tissues, small target region, and anisotropic resolution of clinical CT images. To deal with these problems, we propose a 2.5D Convolutional Neural Network (CNN) to handle the difference of inplane and through-plane resolution. Furthermore, we propose a spatial attention module to enable the network to focus on small target, and use channel attention to further improve the segmentation performance. Moreover, we use multi-scale sampling method for training so that the networks can learn features at different scales, which are combined with a multi-model ensemble method to improve the robustness of segmentation results. We also estimate the uncertainty of segmentation results based on our model ensemble, which is of great importance for indicating the reliability of automatic segmentation results for radiotherapy planning.

In this article, we study algorithms for nonnegative matrix factorization (NMF) in various applications involving streaming data. Utilizing the continual nature of the data, we develop a fast two-stage algorithm for highly efficient and accurate NMF. In the first stage, an alternating non-negative least squares (ANLS) framework is used, in combination with active set method with warm-start strategy for the solution of subproblems. In the second stage, an interior point method is adopted to accelerate the local convergence. The convergence of the proposed algorithm is proved. The new algorithm is compared with some existing algorithms in benchmark tests using both real-world data and synthetic data. The results demonstrate the advantage of our algorithm in finding high-precision solutions., Comment: 10 pages, 3 figures

Deep learning networks have shown promising performance for accurate object localization in medial images, but require large amount of annotated data for supervised training, which is expensive and expertise burdensome. To address this problem, we present a one-shot framework for organ and landmark localization in volumetric medical images, which does not need any annotation during the training stage and could be employed to locate any landmarks or organs in test images given a support (reference) image during the inference stage. Our main idea comes from that tissues and organs from different human bodies have a similar relative position and context. Therefore, we could predict the relative positions of their non-local patches, thus locate the target organ. Our framework is composed of three parts: (1) A projection network trained to predict the 3D offset between any two patches from the same volume, where human annotations are not required. In the inference stage, it takes one given landmark in a reference image as a support patch and predicts the offset from a random patch to the corresponding landmark in the test (query) volume. (2) A coarse-to-fine framework contains two projection networks, providing more accurate localization of the target. (3) Based on the coarse-to-fine model, we transfer the organ boundingbox (B-box) detection to locating six extreme points along x, y and z directions in the query volume. Experiments on multi-organ localization from head-and-neck (HaN) CT volumes showed that our method acquired competitive performance in real time, which is more accurate and 10^5 times faster than template matching methods with the same setting. Code is available: https://github.com/LWHYC/RPR-Loc., Comment: Early accepted by MICCAI 2021

Bang-Jensen, Bessy, Havet and Yeo showed that every digraph of independence number at most 2 and arc-connectivity at least 2 has an out-branching $B^+$ and an in-branching $B^-$ which are arc-disjoint (such two branchings are called a {\it good pair}), which settled a conjecture of Thomassen for digraphs of independence number 2. They also proved that every digraph on at most 6 vertices and arc-connectivity at least 2 has a good pair and gave an example of a 2-arc-strong digraph $D$ on 10 vertices with independence number 4 that has no good pair. They asked for the smallest number $n$ of vertices in a 2-arc-strong digraph which has no good pair. In this paper, we prove that every digraph on at most 9 vertices and arc-connectivity at least 2 has a good pair, which solves this problem., Comment: 50 pages, 5 figures

We validate the use of matrix factorization for the automatic identification of relevant components from atomic pair distribution function (PDF) data. We also present a newly developed software infrastructure for analyzing the PDF data arriving in streaming manner. We then apply two matrix factorization techniques, Principal Component Analysis (PCA) and Non-negative Matrix Factorization (NMF), to study simulated and experiment datasets in the context of in situ experiment.

Accurate medical image segmentation is essential for diagnosis and treatment planning of diseases. Convolutional Neural Networks (CNNs) have achieved state-of-the-art performance for automatic medical image segmentation. However, they are still challenged by complicated conditions where the segmentation target has large variations of position, shape and scale, and existing CNNs have a poor explainability that limits their application to clinical decisions. In this work, we make extensive use of multiple attentions in a CNN architecture and propose a comprehensive attention-based CNN (CA-Net) for more accurate and explainable medical image segmentation that is aware of the most important spatial positions, channels and scales at the same time. In particular, we first propose a joint spatial attention module to make the network focus more on the foreground region. Then, a novel channel attention module is proposed to adaptively recalibrate channel-wise feature responses and highlight the most relevant feature channels. Also, we propose a scale attention module implicitly emphasizing the most salient feature maps among multiple scales so that the CNN is adaptive to the size of an object. Extensive experiments on skin lesion segmentation from ISIC 2018 and multi-class segmentation of fetal MRI found that our proposed CA-Net significantly improved the average segmentation Dice score from 87.77% to 92.08% for skin lesion, 84.79% to 87.08% for the placenta and 93.20% to 95.88% for the fetal brain respectively compared with U-Net. It reduced the model size to around 15 times smaller with close or even better accuracy compared with state-of-the-art DeepLabv3+. In addition, it has a much higher explainability than existing networks by visualizing the attention weight maps. Our code is available at https://github.com/HiLab-git/CA-Net

For two graphs $G,H$ and a positive integer $k$, the \emph{Gallai-Ramsey number} $\operatorname{gr}_k(G,H)$ is defined as the minimum number of vertices $n$ such that any $k$-edge-coloring of $K_n$ contains either a rainbow (all different colored) copy of $G$ or a monochromatic copy of $H$. If $G$ and $H$ are both complete graphs, then we call it Gallai-Ramsey function. Fox and Sudakov proved $\operatorname{gr}_k(K_s,K_t)\leq s^{4kt}$. Alon et al. showed that $\operatorname{gr}_k(K_s,K_t)\leq (2s^3+4s^2)^{kt}$. In this paper, we prove that $\operatorname{gr}_k(K_s,K_t)\leq 2^{kt}s^{3kt}$ for $t\geq 47$. We also give better upper bounds for $\operatorname{gr}_k(G,H)$ when $G,H$ are some special graphs. In this paper, we derive some lower bounds for Gallai-Ramsey functions and numbers by Lov\'{a}sz Local Lemma., Comment: 17 pages

We present an algorithm to extract the distance list from atomic pair distribution functions (PDFs) in a highly automated way. The algorithm is constructed via curve fitting based on a Debye scattering equation model. Due to the non-convex nature of the resulting optimization problem, a number of techniques are developed to overcome various computational difficulties. A key ingredient is a new approach to obtain a reasonable initial guess based on the theoretical properties of the mathematical model. Tests on various nanostructured samples show the effectiveness of the initial guess and the accuracy and overall good performance of the extraction algorithm. This approach could be extended to any spectrum that is approximated as a sum of Gaussian functions.

The anti-Ramsey problem was introduced by Erd\H{o}s, Simonovits and S\'{o}s in 1970s. The anti-Ramsey number of a hypergraph $\mathcal{H}$, $ar(n,s, \mathcal{H})$, is the smallest integer $c$ such that in any coloring of the edges of the $s$-uniform complete hypergraph on $n$ vertices with exactly $c$ colors, there is a copy of $\mathcal{H}$ whose edges have distinct colors. In this paper, we determine the anti-Ramsey numbers of linear paths and loose paths in hypergraphs for sufficiently large $n$, and give bounds for the anti-Ramsey numbers of Berge paths. Similar exact anti-Ramsey numbers are obtained for linear/loose cycles, and bounds are obtained for Berge cycles. Our main tools are path extension technique and stability results on hypergraph Tur\'{a}n problems of paths and cycles.