Modern deep neural networks have shown remarkable performance in medical image classification. However, such networks either emphasize pixel-intensity features instead of fundamental anatomical structures (e.g., those encoded by topological invariants), or they capture only simple topological features via single-parameter persistence. In this paper, we propose a new topology-guided classification framework that extracts multi-scale and multi-filtration persistent topological features and integrates them into vision classification backbones. For an input image, we first compute cubical persistence diagrams (PDs) across multiple image resolutions/scales. We then develop a "vineyard" algorithm that consolidates these PDs into a single, stable diagram capturing signatures at varying granularities, from global anatomy to subtle local irregularities that may indicate early-stage disease. To further exploit richer topological representations produced by multiple filtrations, we design a cross-attention-based neural network that directly processes the consolidated final PDs. The resulting topological embeddings are fused with feature maps from CNNs or Transformers. By integrating multi-scale and multi-filtration topologies into an end-to-end architecture, our approach enhances the model’s capacity to recognize complex anatomical structures. Evaluations on three public datasets show consistent, considerable improvements over strong baselines and state-of-the-art methods, demonstrating the value of our comprehensive topological perspective for robust and interpretable medical image classification.

Despite the rapid advancements of electrocardiogram (ECG) signal diagnosis and analysis methods through deep learning, two major hurdles still limit their clinical adoption: the lack of versatility in processing ECG signals with diverse configurations, and the inadequate detection of risk signals due to sample imbalances. Addressing these challenges, we introduceVersAtile andRisk-Sensitive cardiac diagnosis (VARS), an innovative approach that employs a graph-based representation to uniformly model heterogeneous ECG signals. VARS stands out by transforming ECG signals into versatile graph structures that capture critical diagnostic features, irrespective of signal diversity in the lead count, sampling frequency, and duration. This graph-centric formulation also enhances diagnostic sensitivity, enabling precise localization and identification of abnormal ECG patterns that often elude standard analysis methods. To facilitate representation transformation, our approach integrates denoising reconstruction with contrastive learning to preserve raw ECG information while highlighting pathognomonic patterns. We rigorously evaluate the efficacy of VARS on three distinct ECG datasets, encompassing a range of structural variations. The results demonstrate that VARS not only consistently surpasses existing state-of-the-art models across all these datasets but also exhibits substantial improvement in identifying risk signals. Additionally, VARS offers interpretability by pinpointing the exact waveforms that lead to specific model outputs, thereby assisting clinicians in making informed decisions. These findings suggest that our VARS will likely emerge as an invaluable tool for comprehensive cardiac health assessment.

State-of-the-art (SOTA) methods for cell instance segmentation are based on deep learning (DL) semantic segmentation approaches, focusing on distinguishing foreground pixels from background pixels. In order to identify cell instances from foreground pixels (e.g., pixel clustering), most methods decompose instance information into pixel-wise objectives, such as distances to foreground-background boundaries (distance maps), heat gradients with the center point as heat source (heat diffusion maps), and distances from the center point to foreground-background boundaries with fixed angles (star-shaped polygons). However, pixel-wise objectives may lose significant geometric properties of the cell instances, such as shape, curvature, and convexity, which require a collection of pixels to represent. To address this challenge, we present a novel pixel clustering method, called Ceb (for Cell boundaries), to leverage cell boundary features and labels to divide foreground pixels into cell instances. Starting with probability maps generated from semantic segmentation, Ceb first extracts potential foreground-foreground boundaries (i.e., boundary candidates) with a revised Watershed algorithm. For each boundary candidate, a boundary feature representation (called boundary signature) is constructed by sampling pixels from the current foreground-foreground boundary as well as the neighboring background-foreground boundaries. Next, a lightweight boundary classifier is used to predict its binary boundary label based on the corresponding boundary signature. Finally, cell instances are obtained by dividing or merging neighboring regions based on the predicted boundary labels. Extensive experiments on six datasets demonstrate that Ceb outperforms existing pixel clustering methods on semantic segmentation probability maps. Moreover, Ceb achieves highly competitive performance compared to state-of-the-art cell instance segmentation methods. The code is available at: https://github.com/pxliang/Ceb.

Cancer survival analysis commonly integrates information across diverse medical modalities to make survival-time predictions. Existing methods primarily focus on extracting different decoupled features of modalities and performing fusion operations such as concatenation, attention, and Mixture-of-Experts (MoE)-based fusion. However, these methods still face two key challenges: 1) fixed fusion schemes (concatenation and attention) can lead to model over-reliance on predefined feature combinations, limiting the dynamic fusion of decoupled features; and 2) in MoE-based fusion methods, each expert network handles separate decoupled features, which limits information interaction among the decoupled features. To address these challenges, we propose a novel Decoupling-Reorganization-Fusion framework (DeReF), which devises a random feature reorganization strategy between modalities decoupling and dynamic MoE fusion modules. Its advantages are: 1) it increases the diversity of feature combinations and granularity, enhancing the generalization ability of the subsequent expert networks; and 2) it overcomes the problem of information closure and helps expert networks better capture information among decoupled features. Additionally, we incorporate a regional cross-attention network within the modality decoupling module to improve the representation quality of decoupled features. Extensive experimental results on our in-house Liver Cancer (LC) and three widely used public datasets from The Cancer Genome Atlas (TCGA) confirm the effectiveness of our proposed method. Codes are available at https://github.com/ZJUMAI/DeReF.

Bladder cancer is one of the most prevalent malignancies worldwide, with a recurrence rate of up to 78 %, necessitating accurate post-operative monitoring for effective patient management. Multi-sequence contrast-enhanced MRI is commonly used for recurrence detection; however, interpreting these scans remains challenging, even for experienced radiologists, due to post-surgical alterations such as scarring, swelling, and tissue remodeling. AI-assisted diagnostic tools have shown promise in improving bladder cancer recurrence prediction, yet progress in this field is hindered by the lack of dedicated multi-sequence MRI datasets for recurrence assessment study. In this work, we first introduce a curated multi-sequence, multimodal MRI dataset specifically designed for bladder cancer recurrence prediction, establishing a valuable benchmark for future research. We then propose H-CNN-ViT, a new Hierarchical Gated Attention Multi-Branch model that enables selective weighting of features from the global (ViT) and local (CNN) paths based on contextual demands, achieving a balanced and targeted feature fusion. Our multi-branch architecture processes each modality independently, ensuring that the unique properties of each imaging channel are optimally captured and integrated. Evaluated on our dataset, H-CNN-ViT achieves an AUC of 78.6 %, surpassing state-of-the-art models. Our model is publicly available at https://github.com/XLIAaron/H-CNN-ViT.

Recent advancements in foundation models, such as the Segment Anything Model (SAM), have shown strong performance in various vision tasks, particularly image segmentation, due to their impressive zero-shot segmentation capabilities. However, effectively adapting such models for medical image classification is still a less explored topic. In this paper, we introduce a new framework to adapt SAM for medical image classification. First, we utilize the SAM image encoder as a feature extractor to capture segmentation-based features that convey important spatial and contextual details of the image, while freezing its weights to avoid unnecessary overhead during training. Next, we propose a novel Spatially Localized Channel Attention (SLCA) mechanism to compute spatially localized attention weights for the feature maps. The features extracted from SAM's image encoder are processed through SLCA to compute attention weights, which are then integrated into deep learning classification models to enhance their focus on spatially relevant or meaningful regions of the image, thus improving classification performance. Experimental results on three public medical image classification datasets demonstrate the effectiveness and dataefficiency of our approach.

This paper proposes a new autoregressive model as an effective and scalable monocular depth estimator. Our idea is simple: We tackle the monocular depth estimation (MDE) task with an autoregressive prediction paradigm, based on two core designs. First, our depth autoregressive model (DAR) treats the depth map of different resolutions as a set of tokens, and conducts the low-to-high resolution autoregressive objective with a patch-wise causal mask. Second, our DAR recursively discretizes the entire depth range into more compact intervals, and attains the coarse-to-fine granularity autoregressive objective in an ordinal-regression manner. By coupling these two autoregressive objectives, our DAR establishes new state-of-the-art (SOTA) on KITTI and NYU Depth v2 by clear margins. Further, our scalable approach allows us to scale the model up to 2.0B and achieve the best RMSE of 1.799 on the KITTI dataset (5% improvement) compared to 1.896 by the current SOTA (Depth Anything). DAR further showcases zero-shot generalization ability on unseen datasets. These results suggest that DAR yields superior performance with an autoregressive prediction paradigm, providing a promising approach to equip modern autoregressive large models (e.g., GPT-4o) with depth estimation capabilities. Project page: https://depth-ar.github.io/.

One-shot semantic segmentation aims to segment query images given only ONE annotated support image of the same class. This task is challenging because target objects in the support and query images can be largely different in appearance and pose (i.e., intra-class variation). Prior works suggested that incorporating more annotated support images in few-shot settings boosts performances but increases costs due to additional manual labeling. In this paper, we propose a novel and effective approach for ONE-shot semantic segmentation, called Group-On, which packs multiple query images in batches for the benefit of mutual knowledge support within the same category. Specifically, after coarse segmentation masks of the batch of queries are predicted, query-mask pairs act as pseudo support data to enhance mask predictions mutually. To effectively steer such process, we construct an innovative MoME module, where a flexible number of mask experts are guided by a scene-driven router and work together to make comprehensive decisions, fully promoting mutual benefits of queries. Comprehensive experiments on three standard benchmarks show that, in the ONE-shot setting, Group-On significantly outperforms previous works by considerable margins. With only one annotated support image, Group-On can be even competitive with the counterparts using 5 annotated images.

Ordinal regression bridges regression and classification by assigning objects to ordered classes. While human experts rely on discriminative patch-level features for decisions, current approaches are limited by the availability of only image-level ordinal labels, overlooking fine-grained patch-level characteristics. In this paper, we propose a Dual-level Fuzzy Learning with Patch Guidance framework, named DFPG that learns precise feature-based grading boundaries from ambiguous ordinal labels, with patch-level supervision. Specifically, we propose patch-labeling and filtering strategies to enable the model to focus on patch-level features exclusively with only image-level ordinal labels available. We further design a dual-level fuzzy learning module, which leverages fuzzy logic to quantitatively capture and handle label ambiguity from both patch-wise and channel-wise perspectives. Extensive experiments on various image ordinal regression datasets demonstrate the superiority of our proposed method, further confirming its ability in distinguishing samples from difficult-to-classify categories. The code is available at https://github.com/ZJUMAI/DFPG-ord.

Topological structures in image data, such as connected components and loops, play a crucial role in understanding image content (e.g., biomedical objects). Despite remarkable successes of numerous image processing methods that rely on appearance information, these methods often lack sensitivity to topological structures when used in general deep learning (DL) frameworks. In this paper, we introduce a new general approach, called TopoImages (for Topology Images), which computes a new representation of input images by encoding local topology of patches. In TopoImages, we leverage persistent homology (PH) to encode geometric and topological features inherent in image patches. Our main objective is to capture topological information in local patches of an input image into a vectorized form. Specifically, we first compute persistence diagrams (PDs) of the patches, and then vectorize and arrange these PDs into long vectors for pixels of the patches. The resulting multi-channel image-form representation is called a TopoImage. TopoImages offers a new perspective for data analysis. To garner diverse and significant topological features in image data and ensure a more comprehensive and enriched representation, we further generate multiple TopoImages of the input image using various filtration functions, which we call multi-view TopoImages. The multi-view TopoImages are fused with the input image for DL-based classification, with considerable improvement. Our TopoImages approach is highly versatile and can be seamlessly integrated into common DL frameworks. Experiments on three public medical image classification datasets demonstrate noticeably improved accuracy over state-of-the-art methods.

Deep learning (DL) methods have shown remarkable successes in medical image segmentation, often using large amounts of annotated data for model training. However, acquiring a large number of diverse labeled 3D medical image datasets is highly difficult and expensive. Recently, mask propagation DL methods were developed to reduce the annotation burden on 3D medical images. For example, Sli2Vol [59] proposed a self-supervised framework (SSF) to learn correspondences by matching neighboring slices via slice reconstruction in the training stage; the learned correspondences were then used to propagate a labeled slice to other slices in the test stage. But, these methods are still prone to error accumulation due to the inter-slice propagation of reconstruction errors. Also, they do not handle discontinuities well, which can occur between consecutive slices in 3D images, as they emphasize exploiting object continuity. To address these challenges, in this work, we propose a new SSF, called Sli2Vol+, for segmenting any anatomical structures in 3D medical images using only a single annotated slice per training and testing volume. Specifically, in the training stage, we first propagate an annotated 2D slice of a training volume to the other slices, generating pseudo-labels (PLs). Then, we develop a novel Object Estimation Guided Correspondence Flow Network to learn reliable correspondences between consecutive slices and corresponding PLs in a self-supervised manner. In the test stage, such correspondences are utilized to propagate a single annotated slice to the other slices of a test volume. We demonstrate the effectiveness of our method on various medical image segmentation tasks with different datasets, showing better generalizability across different organs, modalities, and modals. Code is available at https://github.com/adlsn/Sli2Volplus

Protein phosphorylation regulates protein function and cellular signaling pathways, and is strongly associated with diseases, including neurodegenerative disorders and cancer. Phosphorylation plays a critical role in regulating protein activity and cellular signaling by modulating protein-protein interactions (PPIs). It alters binding affinities and interaction networks, thereby influencing biological processes and maintaining cellular homeostasis. Experimental validation of these effects is labor-intensive and expensive, highlighting the need for efficient computational approaches. We propose DeepPhosPPI, the first sequence-based deep learning framework for phosphorylation effects on PPIs prediction, which employs the pre-trained protein language model for feature embedding, with ProtBERT and ESM-2 as alternative backbone encoders. By combining attention-based convolutional neural network and Transformer models, DeepPhosPPI accurately predicts phosphorylation effects. The experimental results show that DeepPhosPPI consistently outperforms state-of-the-art methods in multiple tasks, including functional sites identification and regulatory effect classification.

Multi-rater annotations commonly occur when medical images are independently annotated by multiple experts (raters). In this paper, we tackle two challenges arisen in multi-rater annotations for medical image segmentation (called ambiguous medical image segmentation): (1) How to train a deep learning model when a group of raters produces a set of diverse but plausible annotations, and (2) how to fine-tune the model efficiently when computation resources are not available for retraining the entire model on a different dataset domain. We propose a multi-rater prompt-based approach to address these two challenges altogether. Specifically, we introduce a series of rater-aware prompts that can be plugged into the U-Net model for uncertainty estimation to handle multi-annotation cases. During the prompt-based fine-tuning process, only 0.3% of learnable parameters are required to be updated comparing to training the entire model. Further, in order to integrate expert consensus and disagreement, we explore different multi-rater incorporation strategies and design a mix-training strategy for comprehensive insight learning. Extensive experiments verify the effectiveness of our new approach for ambiguous medical image segmentation on two public datasets while alleviating the heavy burden of model re-training. Code will be made available.

Lane detection is an important yet challenging task in autonomous driving systems. Based on the development of the Visual Transformer, early Transformer-based lane detection studies have achieved promising results in some scenarios. However, for complex road conditions such as uneven illumination intensity and heavy traffic, the performance of these methods remains limited and may even be worse than that of contemporaneous CNN-based methods. In this paper, we propose a novel Transformer-based end-to-end network, called SinLane, that attains the attention weights focusing on the sparse yet meaningful locations and improves the accuracy of lane detection in complex environments. SinLane is composed of a novel Siamese Visual Transformer structure and a novel Feature Pyramid Network (FPN) structure called Pyramid Feature Integration (PFI). We utilize the proposed PFI to better integrate global semantics and finer-scale features and to promote the optimization of the Transformer. Moreover, the designed Siamese Visual Transformer is combined with multiple levels of the PFI and is employed to refine the multi-scale lane line features output from the PFI. Extensive experiments on three benchmark datasets of lane detection demonstrate that our SinLane achieves state-of-the-art results with high accuracy and efficiency. Specifically, our SinLane improves the accuracy by over 3% compared to the current best-performing Transformer-based method for lane detection on CULane.

The transferability of deep neural networks (DNNs) has made significant progress in image and language processing. However, due to the heterogeneity among tables, such DNN bonus is still far from being well exploited on tabular data prediction (e.g., regression or classification tasks). Condensing knowledge from diverse domains, language models (LMs) possess the capability to comprehend feature names from various tables, potentially serving as versatile learners in transferring knowledge across distinct tables and diverse prediction tasks, but their discrete text representation space is inherently incompatible with numerical feature values in tables. In this paper, we present TP-BERTa, a specifically pre-trained LM for tabular data prediction. Concretely, a novel relative magnitude tokenization converts scalar numerical feature values to finely discrete, high-dimensional tokens, and an intra-feature attention approach integrates feature values with the corresponding feature names. Comprehensive experiments demonstrate that our pre-trained TP-BERTa leads the performance among tabular DNNs and is competitive with Gradient Boosted Decision Tree models in typical tabular data regime.

Data organized in tabular format is ubiquitous in real-world applications, and users often craft tables with biased feature definitions and flexibly set prediction targets of their interests. Thus, a rapid development of a robust, effective, dataset-versatile, user-friendly tabular prediction approach is highly desired. While Gradient Boosting Decision Trees (GBDTs) and existing deep neural networks (DNNs) have been extensively utilized by professional users, they present several challenges for casual users, particularly: (i) the dilemma of model selection due to their different dataset preferences, and (ii) the need for heavy hyperparameter searching, failing which their performances are deemed inadequate. In this paper, we delve into this question: Can we develop a deep learning model that serves as a sure bet solution for a wide range of tabular prediction tasks, while also being user-friendly for casual users? We delve into three key drawbacks of deep tabular models, encompassing: (P1) lack of rotational variance property, (P2) large data demand, and (P3) over-smooth solution. We propose ExcelFormer, addressing these challenges through a semi-permeable attention module that effectively constrains the influence of less informative features to break the DNNs' rotational invariance property (for P1), data augmentation approaches tailored for tabular data (for P2), and attentive feedforward network to boost the model fitting capability (for P3). These designs collectively make ExcelFormer a sure bet solution for diverse tabular datasets. Extensive and stratified experiments conducted on real-world datasets demonstrate that our model outperforms previous approaches across diverse tabular data prediction tasks, and this framework can be friendly to casual users, offering ease of use without the heavy hyperparameter tuning. The codes are available at https://github.com/whatashot/excelformer.

Tabular datasets play a crucial role in various applications.Thus, developing efficient, effective, and widely compatible prediction algorithms for tabular data is important.Currently, two prominent model types, Gradient Boosted Decision Trees (GBDTs) and Deep Neural Networks (DNNs), have demonstrated performance advantages on distinct tabular prediction tasks.However, selecting an effective model for a specific tabular dataset is challenging, often demanding time-consuming hyperparameter tuning.To address this model selection dilemma, this paper proposes a new framework that amalgamates the advantages of both GBDTs and DNNs, resulting in a DNN algorithm that is as efficient as GBDTs and is competitively effective regardless of dataset preferences for GBDTs or DNNs.Our idea is rooted in an observation that deep learning (DL) offers a larger parameter space that can represent a well-performing GBDT model, yet the current back-propagation optimizer struggles to efficiently discover such optimal functionality.On the other hand, during GBDT development, hard tree pruning, entropy-driven feature gate, and model ensemble have proved to be more adaptable to tabular data.By combining these key components, we present a Tree-hybrid simple MLP (T-MLP).In our framework, a tensorized, rapidly trained GBDT feature gate, a DNN architecture pruning approach, as well as a vanilla back-propagation optimizer collaboratively train a randomly initialized MLP model.Comprehensive experiments show that T-MLP is competitive with extensively tuned DNNs and GBDTs in their dominating tabular benchmarks (88 datasets) respectively, all achieved with compact model storage and significantly reduced training duration.The codes and full experiment results are available at https://github.com/jyansir/tmlp.

The Vision Transformer has attained remarkable success in various computer vision applications. However, the large computational costs and complex design limit its ability in handling large feature maps. Existing research predominantly focuses on constraining attention to small local regions, which reduces the number of tokens attending the attention computation while overlooking computational demands caused by the feed-forward layer in the Vision Transformer block. In this paper, we introduce Group Vision Transformer (GVT), a relatively simple and efficient variant of Vision Transformer, aiming to improve attention computation. The core idea of our model is to divide and group the entire Transformer layer, instead of only the attention part, into multiple independent branches. This approach offers two advantages: (1) It helps reduce parameters and computational complexity; (2) it enhances the diversity of the learned features. We conduct comprehensive analysis of the impact of different numbers of groups on model performance, as well as their influence on parameters and computational complexity. Our proposed GVT demonstrates competitive performances in several common vision tasks. For example, our GVT-Tiny model achieves 84.8% top-1 accuracy on ImageNet-1K, 51.4% box mAP and 45.2% mask mAP on MS COCO object detection and instance segmentation, and 50.1% mIoU on ADE20K semantic segmentation, outperforming the CAFormer-S36 model by 0.3% in ImageNet-1K top-1 accuracy, 1.2% in box mAP, 1.0% in mask mAP on MS COCO object detection and instance segmentation, and 1.2% in mIoU on ADE20K semantic segmentation, with similar model parameters and computational complexity. Code is accessible at https://github.com/yaoppeng/GVT.

Lane detection is an important yet challenging task in autonomous driving systems. Existing lane detection methods mainly rely on finer-scale information to identify key points of lane lines. Since local information in realistic road environments is frequently obscured by other vehicles or affected by poor outdoor lighting conditions, these methods struggle with the regression of such key points. In this paper, we propose a novel Siamese Transformer with hierarchical refinement for lane detection to improve the detection accuracy in complex road environments. Specifically, we propose a high-to-low hierarchical refinement Transformer structure, called LAne TRansformer (LATR), to refine the key points of lane lines, which integrates global semantics information and finer-scale features. Moreover, exploiting the thin and long characteristics of lane lines, we propose a novel Curve-IoU loss to supervise the fit of lane lines. Extensive experiments on three benchmark datasets of lane detection demonstrate that our proposed new method achieves state-of-the-art results with high accuracy and efficiency. Specifically, our method achieves improved F1 scores on the OpenLane dataset, surpassing the current best-performing method by 5.0 points.

Modern deep neural networks have achieved great successes in medical image analysis. However, the features captured by convolutional neural networks (CNNs) or Transformers tend to be optimized for pixel intensities and neglect key anatomical structures such as connected components and loops. In this paper, we propose a persistent homology guided approach (PHG-Net) that explores topological features of objects for medical image classification. For an input image, we first compute its cubical persistence diagram and extract topological features into a vector representation using a small neural network (called the PH module). The extracted topological features are then incorporated into the feature map generated by CNN or Transformer for feature fusion. The PH module is lightweight and capable of integrating topological features into any CNN or Transformer architectures in an end-to-end fashion. We evaluate our PHG-Net on three public datasets and demonstrate its considerable improvements on the target classification tasks over state-of-the-art methods.

Cervical lesion detection (CLD) using colposcopic images of multi-modality (acetic and iodine) is critical to computer-aided diagnosis (CAD) systems for accurate, objective, and comprehensive cervical cancer screening. To robustly capture lesion features and conform with clinical diagnosis practice, we propose a novel corresponding region fusion network (CRFNet) for multi-modal CLD. CRFNet first extracts feature maps and generates proposals for each modality, then performs proposal shifting to obtain corresponding regions under large position shifts between modalities, and finally fuses those region features with a new corresponding channel attention to detect lesion regions on both modalities. To evaluate CRFNet, we build a large multi-modal colposcopic image dataset collected from our collaborative hospital. We show that our proposed CRFNet surpasses known single-modal and multi-modal CLD methods and achieves state-of-the-art performance, especially in terms of Average Precision.

Drug Target Interaction (DTI) prediction plays a crucial role in in-silico drug discovery, especially for deep learning (DL) models. Along this line, existing methods usually first extract features from drugs and target proteins, and use drug-target pairs to train DL models. However, these DL-based methods essentially rely on similar structures and patterns defined by the homologous proteins from a large amount of data. When few drug-target interactions are known for a newly discovered protein and its homologous proteins, prediction performance can suffer notable reduction. In this paper, we propose a novel Protein-Context enhanced Master/Slave Framework (PCMS), for zero-shot DTI prediction. This framework facilitates the efficient discovery of ligands for newly discovered target proteins, addressing the challenge of predicting interactions without prior data. Specifically, the PCMS framework consists of two main components: a Master Learner and a Slave Learner. The Master Learner first learns the target protein context information, and then adaptively generates the corresponding parameters for the Slave Learner. The Slave Learner then perform zero-shot DTI prediction in different protein contexts. Extensive experiments verify the effectiveness of our PCMS compared to state-of-the-art methods in various metrics on two public datasets.

As a common and critical medical image analysis task, deep learning based biomedical image segmentation is hindered by the dependence on costly fine-grained annotations. To alleviate this data dependence, in this article, a novel approach, called Polygonal Approximation Learning (PAL), is proposed for convex object instance segmentation with only bounding-box supervision. The key idea behind PAL is that the detection model for convex objects already contains the necessary information for segmenting them since their convex hulls, which can be generated approximately by the intersection of bounding boxes, are equivalent to the masks representing the objects. To extract the essential information from the detection model, a repeated detection approach is employed on biomedical images where various rotation angles are applied and a dice loss with the projection of the rotated detection results is utilized as a supervised signal in training our segmentation model. In biomedical imaging tasks involving convex objects, such as nuclei instance segmentation, PAL outperforms the known models (e.g., BoxInst) that rely solely on box supervision. Furthermore, PAL achieves comparable performance with mask-supervised models including Mask R-CNN and Cascade Mask R-CNN. Interestingly, PAL also demonstrates remarkable performance on non-convex object instance segmentation tasks, for example, surgical instrument and organ instance segmentation.

Cortical cataract, a common type of cataract, is particularly difficult to be diagnosed automatically due to the complex features of the lesions. Recently, many methods based on edge detection or deep learning were proposed for automatic cataract grading. However, these methods suffer a large performance drop in cortical cataract grading due to the more complex cortical opacities and uncertain data. In this paper, we propose a novel Transformer-based Knowledge Distillation Network, called TKD-Net, for cortical cataract grading. To tackle the complex opacity problem, we first devise a zone decomposition strategy to extract more refined features and introduce special sub-scores to consider critical factors of clinical cortical opacity assessment (location, area, density) for comprehensive quantification. Next, we develop a multi-modal mix-attention Transformer to efficiently fuse sub-scores and image modality for complex feature learning. However, obtaining the sub-score modality is a challenge in the clinic, which could cause the modality missing problem instead. To simultaneously alleviate the issues of modality missing and uncertain data, we further design a Transformer-based knowledge distillation method, which uses a teacher model with perfect data to guide a student model with modality-missing and uncertain data. We conduct extensive experiments on a dataset of commonly-used slit-lamp images annotated by the LOCS III grading system to demonstrate that our TKD-Net outperforms state-of-the-art methods, as well as the effectiveness of its key components. Codes are available at https://github.com/wjh892521292/Cataract_TKD-Net.

Recent development of deep neural networks (DNNs) for tabular learning has largely benefited from the capability of DNNs for automatic feature interaction. However, the heterogeneity nature of tabular features makes such features relatively independent, and developing effective methods to promote tabular feature interaction still remains an open problem. In this paper, we propose a novel Graph Estimator, which automatically estimates the relations among tabular features and builds graphs by assigning edges between related features. Such relation graphs organize independent tabular features into a kind of graph data such that interaction of nodes (tabular features) can be conducted in an orderly fashion. Based on our proposed Graph Estimator, we present a bespoke Transformer network tailored for tabular learning, called T2G-Former, which processes tabular data by performing tabular feature interaction guided by the relation graphs. A specific Cross-level Readout collects salient features predicted by the layers in T2G-Former across different levels, and attains global semantics for final prediction. Comprehensive experiments show that our T2G-Former achieves superior performance among DNNs and is competitive with non-deep Gradient Boosted Decision Tree models. The code and detailed results are available at https://github.com/jyansir/t2g-former.

Ordinal regression refers to classifying object instances into ordinal categories. It has been widely studied in many scenarios, such as medical disease grading and movie rating. Known methods focused only on learning inter-class ordinal relationships, but still incur limitations in distinguishing adjacent categories thus far. In this paper, we propose a simple sequence prediction framework for ordinal regression called Ord2Seq, which, for the first time, transforms each ordinal category label into a special label sequence and thus regards an ordinal regression task as a sequence prediction process. In this way, we decompose an ordinal regression task into a series of recursive binary classification steps, so as to subtly distinguish adjacent categories. Comprehensive experiments show the effectiveness of distinguishing adjacent categories for performance improvement and our new approach exceeds state-of-the-art performances in four different scenarios. Codes are available at https://github.com/wjh892521292/Ord2Seq.

Image ordinal regression has been mainly studied along the line of exploiting the order of categories. However, the issues of class imbalance and category overlap that are very common in ordinal regression were largely overlooked. As a result, the performance on minority categories is often unsatisfactory. In this paper, we propose a novel framework called CIG based on controllable image generation to directly tackle these two issues. Our main idea is to generate extra training samples with specific labels near category boundaries, and the sample generation is biased toward the less-represented categories. To achieve controllable image generation, we seek to separate structural and categorical information of images based on structural similarity, categorical similarity, and reconstruction constraints. We evaluate the effectiveness of our new CIG approach in three different image ordinal regression scenarios. The results demonstrate that CIG can be flexibly integrated with off-the-shelf image encoders or ordinal regression models to achieve improvement, and further, the improvement is more significant for minority categories.

Since annotating medical images for segmentation tasks commonly incurs expensive costs, it is highly desirable to design an annotation-efficient method to alleviate the annotation burden. Recently, contrastive learning has exhibited a great potential in learning robust representations to boost downstream tasks with limited labels. In medical imaging scenarios, ready-made meta labels (i.e., specific attribute information of medical images) inherently reveal semantic relationships among images, which have been used to define positive pairs in previous work. However, the multi-perspective semantics revealed by various meta labels are usually incompatible and can incur intractable "semantic contradiction" when combining different meta labels. In this paper, we tackle the issue of "semantic contradiction" in a gradient-guided manner using our proposed Gradient Mitigator method, which systematically unifies multi-perspective meta labels to enable a pre-trained model to attain a better high-level semantic recognition ability. Moreover, we emphasize that the fine-grained discrimination ability is vital for segmentation-oriented pre-training, and develop a novel method called Gradient Filter to dynamically screen pixel pairs with the most discriminating power based on the magnitude of gradients. Comprehensive experiments on four medical image segmentation datasets verify that our new method GCL: (1) learns informative image representations and considerably boosts segmentation performance with limited labels, and (2) shows promising generalizability on out-of-distribution datasets.

Graph Neural Networks (GNNs) have become widely-used models for semi-supervised learning. However, the robustness of GNNs in the presence of label noise remains a largely under-explored problem. In this paper, we consider an important yet challenging scenario where labels on nodes of graphs are not only noisy but also scarce. In this scenario, the performance of GNNs is prone to degrade due to label noise propagation and insufficient learning. To address these issues, we propose a novel RTGNN (Robust Training of Graph Neural Networks via Noise Governance) framework that achieves better robustness by learning to explicitly govern label noise. More specifically, we introduce self-reinforcement and consistency regularization as supplemental supervision. The self-reinforcement supervision is inspired by the memorization effects of deep neural networks and aims to correct noisy labels. Further, the consistency regularization prevents GNNs from overfitting to noisy labels via mimicry loss in both the inter-view and intra-view perspectives. To leverage such supervisions, we divide labels into clean and noisy types, rectify inaccurate labels, and further generate pseudo-labels on unlabeled nodes. Supervision for nodes with different types of labels is then chosen adaptively. This enables sufficient learning from clean labels while limiting the impact of noisy ones. We conduct extensive experiments to evaluate the effectiveness of our RTGNN framework, and the results validate its consistent superior performance over state-of-the-art methods with two types of label noises and various noise rates.

A large number of people suffer from life-threatening cardiac abnormalities, and electrocardiogram (ECG) analysis is beneficial to determining whether an individual is at risk of such abnormalities. Automatic ECG classification methods, especially the deep learning based ones, have been proposed to detect cardiac abnormalities using ECG records, showing good potential to improve clinical diagnosis and help early prevention of cardiovascular diseases. However, the predictions of the known neural networks still do not satisfactorily meet the needs of clinicians, and this phenomenon suggests that some information used in clinical diagnosis may not be well captured and utilized by these methods. In this paper, we introduce some rules into convolutional neural networks, which help present clinical knowledge to deep learning based ECG analysis, in order to improve automated ECG diagnosis performance. Specifically, we propose a Handcrafted-Rule-enhanced Neural Network (called HRNN) for ECG classification with standard 12-lead ECG input, which consists of a rule inference module and a deep learning module. Experiments on two large-scale public ECG datasets show that our new approach considerably outperforms existing state-of-the-art methods. Further, our proposed approach not only can improve the diagnosis performance, but also can assist in detecting mislabelled ECG samples.

Proteins commonly perform biological functions through protein-protein interactions (PPIs). The knowledge of PPI sites is imperative for the understanding of protein functions, disease mechanisms, and drug design. Traditional biological experimental methods for studying PPI sites still incur considerable drawbacks, including long experimental time and high labor costs. Therefore, many computational methods have been proposed for predicting PPI sites. However, achieving high prediction performance and overcoming severe data imbalance remain challenging issues. In this paper, we propose a new sequence-based deep learning model called CLPPIS (standing for CNN-LSTM ensemble based PPI Sites prediction). CLPPIS consists of CNN and LSTM components, which can capture spatial features and sequential features simultaneously. Further, it utilizes a novel feature group as input, which has 7 physicochemical, biophysical, and statistical properties. Besides, it adopts a batch-weighted loss function to reduce the interference of imbalance data. Our work suggests that the integration of protein spatial features and sequential features provides important information for PPI sites prediction. Evaluation on three public benchmark datasets shows that our CLPPIS model significantly outperforms existing state-of-the-art methods.

We aim to quantitatively predict protein semantic similarities (PSS), which is vital to making biological discoveries. Previously, researchers commonly exploited Gene Ontology (GO) graphs (containing standardized hierarchically-organized GO terms for annotating distinct protein attributes) to learn GO term embeddings (vector representations) for quantifying protein attribute similarities and aggregate these embeddings to form protein embeddings for similarity measurement. However, two key properties of GO terms and annotated proteins are not yet well-explored by these learning-based methods: (1) taxonomy relations between GO terms; (2) GO terms' different contributions in describing protein semantics. In this paper, we propose TANGO, a new framework composed of a TAxoNomy-aware embedding module and an aggreGatiOn module. Our Embedding Module encodes taxonomic information into GO term embeddings by incorporating GO term topological distances in the GO graph hierarchy. Hence, distances between GO term embeddings can be used to more accurately measure shared meanings between correlated protein attributes. Our Aggregation Module automatically determines the contributions of GO terms when merging into the target protein embeddings, by mining GO term concept dependency relations in the GO graph and correlations in protein annotations. We conduct extensive experiments on several public datasets. On two PSS metrics, our new method significantly outperforms known methods by a large margin.

Pathology images contain rich information of cell appearance, microenvironment, and topology features for cancer analysis and diagnosis. Among such features, topology becomes increasingly important in analysis for cancer immunotherapy. By analyzing geometric and hierarchically structured cell distribution topology, oncologists can identify densely-packed and cancer-relevant cell communities (CCs) for making decisions. Compared to commonly-used pixel-level Convolution Neural Network (CNN) features and cell-instance-level Graph Neural Network (GNN) features, CC topology features are at a higher level of granularity and geometry. However, topological features have not been well exploited by recent deep learning (DL) methods for pathology image classification due to lack of effective topological descriptors for cell distribution and gathering patterns. In this paper, inspired by clinical practice, we analyze and classify pathology images by comprehensively learning cell appearance, microenvironment, and topology in a fine-to-coarse manner. To describe and exploit topology, we design Cell Community Forest (CCF), a novel graph that represents the hierarchical formulation process of big-sparse CCs from small-dense CCs. Using CCF as a new geometric topological descriptor of tumor cells in pathology images, we propose CCF-GNN, a GNN model that successively aggregates heterogeneous features (e.g., appearance, microenvironment) from cell-instance-level, cell-community-level, into image-level for pathology image classification. Extensive cross-validation experiments show that our method significantly outperforms alternative methods on H&E-stained and immunofluorescence images for disease grading tasks with multiple cancer types. Our proposed CCF-GNN establishes a new topological data analysis (TDA) based method, which facilitates integrating multi-level heterogeneous features of point clouds (e.g., for cells) into a unified DL framework.

The rib fracture is a common type of thoracic skeletal trauma, and its inspections using computed tomography (CT) scans are critical for clinical evaluation and treatment planning. However, it is often challenging for radiologists to quickly and accurately detect rib fractures due to tiny objects and blurriness in large 3D CT images. Previous diagnoses for automatic rib fracture mostly relied on deep learning (DL)-based object detection, which highly depends on label quality and quantity. Moreover, general object detection methods did not take into consideration the typically elongated and oblique shapes of ribs in 3D volumes. To address these issues, we propose a shape-aware method based on DL called SA-FracNet for rib fracture detection and segmentation. First, we design a pixel-level pretext task founded on contrastive learning on massive unlabeled CT images. Second, we train the fine-tuned rib fracture detection model based on the pre-trained weights. Third, we develop a fracture shape-aware multi-task segmentation network to delineate the fracture based on the detection result. Experiments demonstrate that our proposed SA-FracNet achieves state-of-the-art rib fracture detection and segmentation performance on the public RibFrac dataset, with a detection sensitivity of 0.926 and segmentation Dice of 0.754. Test on a private dataset also validates the robustness and generalization of our SA-FracNet.

Tabular data are ubiquitous in real world applications. Although many commonly-used neural components (e.g., convolution) and extensible neural networks (e.g., ResNet) have been developed by the machine learning community, few of them were effective for tabular data and few designs were adequately tailored for tabular data structures. In this paper, we propose a novel and flexible neural component for tabular data, called Abstract Layer (AbstLay), which learns to explicitly group correlative input features and generate higher-level features for semantics abstraction. Also, we design a structure re-parameterization method to compress the trained AbstLay, thus reducing the computational complexity by a clear margin in the reference phase. A special basic block is built using AbstLays, and we construct a family of Deep Abstract Networks (DANets) for tabular data classification and regression by stacking such blocks. In DANets, a special shortcut path is introduced to fetch information from raw tabular features, assisting feature interactions across different levels. Comprehensive experiments on seven real-world tabular datasets show that our AbstLay and DANets are effective for tabular data classification and regression, and the computational complexity is superior to competitive methods. Besides, we evaluate the performance gains of DANet as it goes deep, verifying the extendibility of our method. Our code is available at https://github.com/WhatAShot/DANet.

We introduce Scalar2Vec, a new deep learning solution that translates scalar fields to velocity vector fields for scientific visualization. Given multivariate or ensemble scalar field volumes and their velocity vector field counterparts, Scalar2Vec first identifies suitable variables for scalar-to-vector translation. It then leverages a k-complete bipartite translation network (kCBT-Net) to complete the translation task. kCBT-Net takes a set of sampled scalar volumes of the same variable as input, extracts their multi -scale information, and learns to synthesize the corresponding vector volumes. Ground-truth vector fields and their derived quantities are utilized for loss computation and network training. After training, Scalar2Vec can infer unseen velocity vector fields of the same data set directly from their scalar field counterparts. We demonstrate the effectiveness of Scalar2Vec with quantitative and qualitative results on multiple data sets and compare it with three other state-of-the-art deep learning methods.

Surgery is the only viable treatment for cataract patients with visual acuity (VA) impairment. Clinically, to assess the necessity of cataract surgery, accurately predicting postoperative VA before surgery by analyzing multi-view optical coherence tomography (OCT) images is crucially needed. Unfortunately, due to complicated fundus conditions, determining postoperative VA remains difficult for medical experts. Deep learning methods for this problem were developed in recent years. Although effective, these methods still face several issues, such as not efficiently exploring potential relations between multi-view OCT images, neglecting the key role of clinical prior knowledge (e.g., preoperative VA value), and using only regression-based metrics which are lacking reference. In this paper, we propose a novel Cross-token Transformer Network (CTT-Net) for postoperative VA prediction by analyzing both the multi-view OCT images and preoperative VA. To effectively fuse multi-view features of OCT images, we develop cross-token attention that could restrict redundant/unnecessary attention flow. Further, we utilize the preoperative VA value to provide more information for postoperative VA prediction and facilitate fusion between views. Moreover, we design an auxiliary classification loss to improve model performance and assess VA recovery more sufficiently, avoiding the limitation by only using the regression metrics. To evaluate CTT-Net, we build a multi-view OCT image dataset collected from our collaborative hospital. A set of extensive experiments validate the effectiveness of our model compared to existing methods in various metrics. Code is available at: https://github.con wjh892521292/Cataract-OCT.

Self-supervised instance discrimination is an effective contrastive pretext task to learn feature representations and address limited medical image annotations. The idea is to make features of transformed versions of the same images similar while forcing all other augmented images’ representations to contrast. However, this instance-based contrastive learning leaves performance on the table by failing to maximize feature affinity between images with similar content while counter-productively pushing their representations apart. Recent improvements on this paradigm (e.g., leveraging multi-modal data, different images in longitudinal studies, spatial correspondences) either relied on additional views or made stringent assumptions about data properties, which can sacrifice generalizability and applicability. To address this challenge, we propose a new self-supervised contrastive learning method that uses unsupervised feature clustering to better select positive and negative image samples. More specifically, we produce pseudo-classes by hierarchically clustering features obtained by an auto-encoder in an unsupervised manner, and prevent destructive interference during contrastive learning by avoiding the selection of negatives from the same pseudo-class. Experiments on 2D skin dermoscopic image segmentation and 3D multi-class whole heart CT segmentation demonstrate that our method outperforms state-of-the-art self-supervised contrastive techniques on these tasks.

Understanding of spatial attributes is central to effective 3D radiology image analysis where crop-based learning is the de facto standard. Given an image patch, its core spatial properties (e.g., position & orientation) provide helpful priors on expected object sizes, appearances, and structures through inherent anatomical consistencies. Spatial correspondences, in particular, can effectively gauge semantic similarities between inter-image regions, while their approximate extraction requires no annotations or overbearing computational costs. However, recent 3D contrastive learning approaches either neglect correspondences or fail to maximally capitalize on them. To this end, we propose an extensible 3D contrastive framework (Spade, for Spa tial De biasing) that leverages extracted correspondences to select more effective positive & negative samples for representation learning. Our method learns both globally invariant and locally equivariant representations with downstream segmentation in mind. We also propose separate selection strategies for global & local scopes that tailor to their respective representational requirements. Compared to recent state-of-the-art approaches, Spade shows notable improvements on three downstream segmentation tasks (CT Abdominal Organ, CT Heart, MR Heart).

Electrocardiogram (ECG) is a widely used non-invasive diagnostic tool for heart diseases. Many studies have devised ECG analysis models (e.g., classifiers) to assist diagnosis. As an upstream task, researches have built generative models to synthesize ECG data, which are beneficial to providing training samples, privacy protection, and annotation reduction. However, previous generative methods for ECG often neither synthesized multi-view data, nor dealt with heart disease conditions. In this paper, we propose a novel disease-aware generative adversarial network for multi-view ECG synthesis called ME-GAN, which attains panoptic electrocardio representations conditioned on heart diseases and projects the representations onto multiple standard views to yield ECG signals. Since ECG manifestations of heart diseases are often localized in specific waveforms, we propose a new "mixup normalization" to inject disease information precisely into suitable locations. In addition, we propose a "view discriminator" to revert disordered ECG views into a pre-determined order, supervising the generator to obtain ECG representing correct view characteristics. Besides, a new metric, rFID, is presented to assess the quality of the synthesized ECG signals. Comprehensive experiments verify that our ME-GAN performs well on multi-view ECG signal synthesis with trusty morbid manifestations.

MOTIVATION: Drug response prediction (DRP) plays an important role in precision medicine (e.g. for cancer analysis and treatment). Recent advances in deep learning algorithms make it possible to predict drug responses accurately based on genetic profiles. However, existing methods ignore the potential relationships among genes. In addition, similarity among cell lines/drugs was rarely considered explicitly. RESULTS: We propose a novel DRP framework, called TGSA, to make better use of prior domain knowledge. TGSA consists of Twin Graph neural networks for Drug Response Prediction (TGDRP) and a Similarity Augmentation (SA) module to fuse fine-grained and coarse-grained information. Specifically, TGDRP abstracts cell lines as graphs based on STRING protein-protein association networks and uses Graph Neural Networks (GNNs) for representation learning. SA views DRP as an edge regression problem on a heterogeneous graph and utilizes GNNs to smooth the representations of similar cell lines/drugs. Besides, we introduce an auxiliary pre-training strategy to remedy the identified limitations of scarce data and poor out-of-distribution generalization. Extensive experiments on the GDSC2 dataset demonstrate that our TGSA consistently outperforms all the state-of-the-art baselines under various experimental settings. We further evaluate the effectiveness and contributions of each component of TGSA via ablation experiments. The promising performance of TGSA shows enormous potential for clinical applications in precision medicine. AVAILABILITY AND IMPLEMENTATION: The source code is available at https://github.com/violet-sto/TGSA. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Compression is a standard procedure for making convolutional neural networks (CNNs) adhere to some specific computing resource constraints. However, searching for a compressed architecture typically involves a series of time-consuming training/validation experiments to determine a good compromise between network size and performance accuracy. To address this, we propose an image complexity-guided network compression technique for biomedical image segmentation. Given any resource constraints, our framework utilizes data complexity and network architecture to quickly estimate a compressed model which does not require network training. Specifically, we map the dataset complexity to the target network accuracy degradation caused by compression. Such mapping enables us to predict the final accuracy for different network sizes, based on the computed dataset complexity. Thus, one may choose a solution that meets both the network size and segmentation accuracy requirements. Finally, the mapping is used to determine the convolutional layer-wise multiplicative factor for generating a compressed network. We conduct experiments using 5 datasets, employing 3 commonly-used CNN architectures for biomedical image segmentation as representative networks. Our proposed framework is shown to be effective for generating compressed segmentation networks, retaining up to ≈95% of the full-sized network segmentation accuracy, and at the same time, utilizing ≈32x fewer network trainable weights (average reduction) of the full-sized networks.

Exploiting complementary advantages of different reflection and scattering properties of near-infrared (NIR) images and visible (VIS) images, this letter first proposes a defogging model for single image input and then develops an extended model, a fusion model for NIR and VIS color images, to enhance the visibility of image objects in scattering environments. Our fusion model enhances the extracted details of NIR and VIS images by filtering with our defogging model in the frequency domain that takes into account the energy preservation of these two types of images in addition to the high resolution of the fused results. Finally, based on the initial fusion, we propose a color retention mapping method to keep the fusion results free of color distortion. Experimental results demonstrate that our proposed method not only achieves good defogging effect, but also can effectively combine the complementary NIR and VIS information in image color and visibility.

Accurate cervical lesion detection (CLD) methods using colposcopic images are highly demanded in computer-aided diagnosis (CAD) for automatic diagnosis of High-grade Squamous Intraepithelial Lesions (HSIL). However, compared to natural scene images, the specific characteristics of colposcopic images, such as low contrast, visual similarity, and ambiguous lesion boundaries, pose difficulties to accurately locating HSIL regions and also significantly impede the performance improvement of existing CLD approaches. To tackle these difficulties and better capture cervical lesions, we develop novel feature enhancing mechanisms from both global and local perspectives, and propose a new discriminative CLD framework, called CervixNet, with a Global Class Activation (GCA) module and a Local Bin Excitation (LBE) module. Specifically, the GCA module learns discriminative features by introducing an auxiliary classifier, and guides our model to focus on HSIL regions while ignoring noisy regions. It globally facilitates the feature extraction process and helps boost feature discriminability. Further, our LBE module excites lesion features in a local manner, and allows the lesion regions to be more fine-grained enhanced by explicitly modelling the inter-dependencies among bins of proposal feature. Extensive experiments on a number of 9888 clinical colposcopic images verify the superiority of our method (AP$_{.75}$= 20.45) over state-of-the-art models on four widely used metrics.

Automatic detection of cervical lesion cells or cell clumps using cervical cytology images is critical to computer-aided diagnosis (CAD) for accurate, objective, and efficient cervical cancer screening. Recently, many methods based on modern object detectors were proposed and showed great potential for automatic cervical lesion detection. Although effective, several issues still hinder further performance improvement of such known methods, such as large appearance variances between single-cell and multi-cell lesion regions, neglecting normal cells, and visual similarity among abnormal cells. To tackle these issues, we propose a new task decomposing and cell comparing network, called TDCC-Net, for cervical lesion cell detection. Specifically, our task decomposing scheme decomposes the original detection task into two subtasks and models them separately, which aims to learn more efficient and useful feature representations for specific cell structures and then improve the detection performance of the original task. Our cell comparing scheme imitates clinical diagnosis of experts and performs cell comparison with a dynamic comparing module (normal-abnormal cells comparing) and an instance contrastive loss (abnormal-abnormal cells comparing). Comprehensive experiments on a large cervical cytology image dataset confirm the superiority of our method over state-of-the-art methods.

Deep learning (DL) based semantic segmentation methods have achieved excellent performance in biomedical image segmentation, producing high quality probability maps to allow extraction of rich instance information to facilitate good instance segmentation. While numerous efforts were put into developing new DL semantic segmentation models, less attention was paid to a key issue of how to effectively explore their probability maps to attain the best possible instance segmentation. We observe that probability maps by DL semantic segmentation models can be used to generate many possible instance candidates, and accurate instance segmentation can be achieved by selecting from them a set of "optimized" candidates as output instances. Further, the generated instance candidates form a well-behaved hierarchical structure (a forest), which allows selecting instances in an optimized manner. Hence, we propose a novel framework, called hierarchical earth mover's distance (H-EMD), for instance segmentation in biomedical 2D+time videos and 3D images, which judiciously incorporates consistent instance selection with semantic-segmentation-generated probability maps. H-EMD contains two main stages: (1) instance candidate generation: capturing instance-structured information in probability maps by generating many instance candidates in a forest structure; (2) instance candidate selection: selecting instances from the candidate set for final instance segmentation. We formulate a key instance selection problem on the instance candidate forest as an optimization problem based on the earth mover's distance (EMD), and solve it by integer linear programming. Extensive experiments on eight biomedical video or 3D datasets demonstrate that H-EMD consistently boosts DL semantic segmentation models and is highly competitive with state-of-the-art methods.

Medical image segmentation plays a vital role in disease diagnosis and analysis. However, data-dependent difficulties such as low image contrast, noisy background, and complicated objects of interest render the segmentation problem challenging. These difficulties diminish dense prediction and make it tough for known approaches to explore data-specific attributes for robust feature extraction. In this paper, we study medical image segmentation by focusing on robust data-specific feature extraction to achieve improved dense prediction. We propose a new deep convolutional neural network (CNN), which exploits specific attributes of input datasets to utilize deep supervision for enhanced feature extraction. In particular, we strategically locate and deploy auxiliary supervision, by matching the object perceptive field (OPF) (which we define and compute) with the layer-wise effective receptive fields (LERF) of the network. This helps the model pay close attention to some distinct input data dependent features, which the network might otherwise 'ignore' during training. Further, to achieve better target localization and refined dense prediction, we propose the densely decoded networks (DDN), by selectively introducing additional network connections (the 'crutch' connections). Using five public datasets (two retinal vessel, melanoma, optic disc/cup, and spleen segmentation) and two in-house datasets (lymph node and fungus segmentation), we verify the effectiveness of our proposed approach in 2D and 3D segmentation.

We present STNet, an end-to-end generative framework that synthesizes spatiotemporal super-resolution volumes with high fidelity for time-varying data. STNet includes two modules: a generator and a spatiotemporal discriminator. The input to the generator is two low-resolution volumes at both ends, and the output is the intermediate and the two-ending spatiotemporal super-resolution volumes. The spatiotemporal discriminator, leveraging convolutional long short-term memory, accepts a spatiotemporal super-resolution sequence as input and predicts a conditional score for each volume based on its spatial (the volume itself) and temporal (the previous volumes) information. We propose an unsupervised pre-training stage using cycle loss to improve the generalization of STNet. Once trained, STNet can generate spatiotemporal super-resolution volumes from low-resolution ones, offering scientists an option to save data storage (i.e., sparsely sampling the simulation output in both spatial and temporal dimensions). We compare STNet with the baseline bicubic+linear interpolation, two deep learning solutions ( SSR+TSF, STD), and a state-of-the-art tensor compression solution (TTHRESH) to show the effectiveness of STNet.

Accurate drug response prediction (DRP) is a crucial yet challenging task in precision medicine. This paper presents a novel Attention-Guided Multi-omics Integration (AGMI) approach for DRP, which first constructs a Multiedge Graph (MeG) for each cell line, and then aggregates multi-omics features to predict drug response using a novel structure, called Graph edge-aware Network (GeNet). For the first time, our AGMI approach explores gene constraint based multi-omics integration for DRP with the whole-genome using GNNs. Empirical experiments on the CCLE and GDSC datasets show that our AGMI largely outperforms state-of-the-art DRP methods by 8.3%-34.2% on four metrics. Our data and code are available at https://github.com/yivan-WYYGDSG/AGMI.

Convolutional neural networks (CNNs) for biomedical image segmentation are often of very large size, resulting in high memory costs and high latency of operations. To ensure CNNs’ accommodation of key computing resource constraints in specific applications, network compression is commonly used. However, time-consuming training/validation experiments are often involved when searching for a compressed CNN for a specific imaging application, in order to achieve a desired compromise between the network size and network accuracy. Recognizing that biomedical images tend to have relatively uniform target objects, we present kCC-Net, a framework to reduce the cost of compressing CNNs for biomedical image segmentation. kCC-Net first uses training data complexity and target network architecture to estimate the network accuracy degradation caused by compression and compute a layer-wise multiplier for generating a compressed network, referred to as CC-Net. To enhance kCC-Net’s ability to extract rich hierarchical features, we incorporate a multi-scale approach by utilizing multiple submodules of CC-Net to generate a new network which is capable of extracting finer features. Verified using three public biomedical image segmentation datasets, our proposed kCC-Net framework is shown to be effective, retaining up to $\sim 95$% of the full-sized networks’ segmentation accuracy, while utilizing $\sim 51 x$ fewer network trainable weights (average reduction) of the full-sized networks.

In previous Capsule Neural Networks (CapsNets), routing algorithms often performed clustering processes to assemble the child capsules’ representations into parent capsules. Such routing algorithms were typically implemented with iterative processes and incurred high computing complexity. This paper presents a new capsule structure, which contains a set of optimizable receptors and a transmitter is devised on the capsule’s representation. Specifically, child capsules’ representations are sent to the parent capsules whose receptors match well the transmitters of the child capsules’ representations, avoiding applying computationally complex routing algorithms. To ensure the receptors in a CapsNet work cooperatively, we build a skeleton to organize the receptors in different capsule layers in a CapsNet. The receptor skeleton assigns a share-out objective for each receptor, making the CapsNet perform as a hierarchical agglomerative clustering process. Comprehensive experiments verify that our approach facilitates efficient clustering processes, and CapsNets with our approach significantly outperform CapsNets with previous routing algorithms on image classification, affine transformation generalization, overlapped object recognition, and representation semantic decoupling.

Multi-lead electrocardiogram (ECG) provides clinical information of heartbeats from several fixed viewpoints determined by the lead positioning. However, it is often not satisfactory to visualize ECG signals in these fixed and limited views, as some clinically useful information is represented only from a few specific ECG viewpoints. For the first time, we propose a new concept, Electrocardio Panorama, which allows visualizing ECG signals from any queried viewpoints. To build Electrocardio Panorama, we assume that an underlying electrocardio field exists, representing locations, magnitudes, and directions of ECG signals. We present a Neural electrocardio field Network (Nef-Net), which first predicts the electrocardio field representation by using a sparse set of one or few input ECG views and then synthesizes Electrocardio Panorama based on the predicted representations. Specially, to better disentangle electrocardio field information from viewpoint biases, a new Angular Encoding is proposed to process viewpoint angles. Also, we propose a self-supervised learning approach called Standin Learning, which helps model the electrocardio field without direct supervision. Further, with very few modifications, Nef-Net can synthesize ECG signals from scratch. Experiments verify that our Nef-Net performs well on Electrocardio Panorama synthesis, and outperforms the previous work on the auxiliary tasks (ECG view transformation and ECG synthesis from scratch). The codes and the division labels of cardiac cycles and ECG deflections on Tianchi ECG and PTB datasets are available at https://github.com/WhatAShot/Electrocardio-Panorama.

Colorectal cancer (CRC) is one of the most life-threatening malignancies. Colonoscopy pathology examination can identify cells of early-stage colon tumors in small tissue image slices. But, such examination is time-consuming and exhausting on high resolution images. In this paper, we present a new framework for colonoscopy pathology whole slide image (WSI) analysis, including lesion segmentation and tissue diagnosis. Our framework contains an improved U-shape network with a VGG net as backbone, and two schemes for training and inference, respectively (the training scheme and inference scheme). Based on the characteristics of colonoscopy pathology WSI, we introduce a specific sampling strategy for sample selection and a transfer learning strategy for model training in our training scheme. Besides, we propose a specific loss function, class-wise DSC loss, to train the segmentation network. In our inference scheme, we apply a sliding-window based sampling strategy for patch generation and diploid ensemble (data ensemble and model ensemble) for the final prediction. We use the predicted segmentation mask to generate the classification probability for the likelihood of WSI being malignant. To our best knowledge, DigestPath 2019 is the first challenge and the first public dataset available on colonoscopy tissue screening and segmentation, and our proposed framework yields good performance on this dataset. Our new framework achieved a DSC of 0.7789 and AUC of 1 on the online test dataset, and we won the [Formula: see text] place in the DigestPath 2019 Challenge (task 2). Our code is available at https://github.com/bhfs9999/colonoscopy_tissue_screen_and_segmentation.

Keratoconus is one of the most severe corneal diseases, which is difficult to detect at the early stage (i.e., sub-clinical keratoconus) and possibly results in vision loss. In this paper, we propose a novel end-to-end deep learning approach, called KerNet, which processes the raw data of the Pentacam HR system (consisting of five numerical matrices) to detect keratoconus and sub-clinical keratoconus. Specifically, we propose a novel convolutional neural network, called KerNet, containing five branches as the backbone with a multi-level fusion architecture. The five branches receive five matrices separately and capture effectively the features of different matrices by several cascaded residual blocks. The multi-level fusion architecture (i.e., low-level fusion and high-level fusion) moderately takes into account the correlation among five slices and fuses the extracted features for better prediction. Experimental results show that: (1) our novel approach outperforms state-of-the-art methods on an in-house dataset, by ~1% for keratoconus detection accuracy and ~4 for sub-clinical keratoconus detection accuracy; (2) the attention maps visualized by Grad-CAM show that our KerNet places more attention on the inferior temporal part for sub-clinical keratoconus, which has been proved as the identifying regions for ophthalmologists to detect sub-clinical keratoconus in previous clinical studies. To our best knowledge, we are the first to propose an end-to-end deep learning approach utilizing raw data obtained by the Pentacam HR system for keratoconus and subclinical keratoconus detection. Further, the prediction performance and the clinical significance of our KerNet are well evaluated and proved by two clinical experts. Our code is available at https://github.com/upzheng/Keratoconus.

Many known supervised deep learning methods for medical image segmentation suffer an expensive burden of data annotation for model training. Recently, few-shot segmentation methods were proposed to alleviate this burden, but such methods often showed poor adaptability to the target tasks. By prudently introducing interactive learning into the few-shot learning strategy, we develop a novel few-shot segmentation approach called Interactive Few-shot Learning (IFSL), which not only addresses the annotation burden of medical image segmentation models but also tackles the common issues of the known few-shot segmentation methods. First, we design a new few-shot segmentation structure, called Medical Prior-based Few-shot Learning Network (MPrNet), which uses only a few annotated samples (e.g., 10 samples) as support images to guide the segmentation of query images without any pre-training. Then, we propose an Interactive Learning-based Test Time Optimization Algorithm (IL-TTOA) to strengthen our MPrNet on the fly for the target task in an interactive fashion. To our best knowledge, our IFSL approach is the first to allow few-shot segmentation models to be optimized and strengthened on the target tasks in an interactive and controllable manner. Experiments on four few-shot segmentation tasks show that our IFSL approach outperforms the state-of-the-art methods by more than 20% in the DSC metric. Specifically, the interactive optimization algorithm (IL-TTOA) further contributes ~10% DSC improvement for the few-shot segmentation models.

We present V2V, a novel deep learning framework, as a general-purpose solution to the variable-to-variable (V2V) selection and translation problem for multivariate time-varying data (MTVD) analysis and visualization. V2V leverages a representation learning algorithm to identify transferable variables and utilizes Kullback-Leibler divergence to determine the source and target variables. It then uses a generative adversarial network (GAN) to learn the mapping from the source variable to the target variable via the adversarial, volumetric, and feature losses. V2V takes the pairs of time steps of the source and target variable as input for training, Once trained, it can infer unseen time steps of the target variable given the corresponding time steps of the source variable. Several multivariate time-varying data sets of different characteristics are used to demonstrate the effectiveness of V2V, both quantitatively and qualitatively. We compare V2V against histogram matching and two other deep learning solutions (Pix2Pix and CycleGAN).

Image segmentation is critical to lots of medical applications. While deep learning (DL) methods continue to improve performance for many medical image segmentation tasks, data annotation is a big bottleneck to DL-based segmentation because (1) DL models tend to need a large amount of labeled data to train, and (2) it is highly time-consuming and label-intensive to voxel-wise label 3D medical images. Significantly reducing annotation effort while attaining good performance of DL segmentation models remains a major challenge. In our preliminary experiments, we observe that, using partially labeled datasets, there is indeed a large performance gap with respect to using fully annotated training datasets. In this paper, we propose a new DL framework for reducing annotation effort and bridging the gap between full annotation and sparse annotation in 3D medical image segmentation. We achieve this by (i) selecting representative slices in 3D images that minimize data redundancy and save annotation effort, and (ii) self-training with pseudo-labels automatically generated from the base-models trained using the selected annotated slices. Extensive experiments using two public datasets (the HVSMR 2016 Challenge dataset and mouse piriform cortex dataset) show that our framework yields competitive segmentation results comparing with state-of-the-art DL methods using less than ~ 20% of annotated data.

We present SSR-VFD, a novel deep learning framework that produces coherent spatial super-resolution (SSR) of three-dimensional vector field data (VFD). SSR-VFD is the first work that advocates a machine learning approach to generate high-resolution vector fields from low-resolution ones. The core of SSR-VFD lies in the use of three separate neural nets that take the three components of a low-resolution vector field as input and jointly output a synthesized high-resolution vector field. To capture spatial coherence, we take into account magnitude and angle losses in network optimization. Our method can work in the in situ scenario where VFD are down-sampled at simulation time for storage saving and these reduced VFD are upsampled back to their original resolution during postprocessing. To demonstrate the effectiveness of SSR-VFD, we show quantitative and qualitative results with several vector field data sets of different characteristics and compare our method against volume upscaling using bicubic interpolation, and two solutions based on CNN and GAN, respectively.

In clinical practice, medical image interpretation often involves multi-labeled classification, since the affected parts of a patient tend to present multiple symptoms or comorbidities. Recently, deep learning based frameworks have attained expertlevel performance on medical image interpretation, which can be attributed partially to large amounts of accurate annotations. However, manually annotating massive amounts of medical images is impractical, while automatic annotation is fast but imprecise (possibly introducing corrupted labels). In this work, we propose a new regularization approach, called Flow-Mixup, for multi-labeled medical image classification with corrupted labels. Flow-Mixup guides the models to capture robust features for each abnormality, thus helping handle corrupted labels effectively and making it possible to apply automatic annotation. Specifically, Flow-Mixup decouples the extracted features by adding constraints to the hidden states of the models. Also, FlowMixup is more stable and effective comparing to other known regularization methods, as shown by theoretical and empirical analyses. Experiments on two electrocardiogram datasets and a chest X-ray dataset containing corrupted labels verify that FlowMixup is effective and insensitive to corrupted labels.

Automatic histopathology image segmentation is crucial to disease analysis. Limited available labeled data hinders the generalizability of trained models under the fully supervised setting. Semi-supervised learning (SSL) based on generative methods has been proven to be effective in utilizing diverse image characteristics. However, it has not been well explored what kinds of generated images would be more useful for model training and how to use such images. In this paper, we propose a new data guided generative method for histopathology image segmentation by leveraging the unlabeled data distributions. First, we design an image generation module. Image content and style are disentangled and embedded in a clustering-friendly space to utilize their distributions. New images are synthesized by sampling and cross-combining contents and styles. Second, we devise an effective data selection policy for judiciously sampling the generated images: (1) to make the generated training set better cover the dataset, the clusters that are underrepresented in the original training set are covered more; (2) to make the training process more effective, we identify and oversample the images of “hard cases” in the data for which annotated training data may be scarce. Our method is evaluated on glands and nuclei datasets. We show that under both the inductive and transductive settings, our SSL method consistently boosts the performance of common segmentation models and attains state-of-the-art results.

Automatic tracking of moving cells in time-lapse image sequences plays an important role in studying many biological processes in development and diseases. Large variations in cell appearances, limited image resolution, and various cell behaviors (e.g., division, apoptosis, deformation, clustering, and migration in or out of the imaging window) make cell tracking a challenging task. However, known cell tracking methods were designed for and tailored to specific cell image sequences and behaviors, thus having limited applicability to various cell image sequences. Aiming toward more robust cell tracking, we propose a new detector-tracker approach for detection and association based cell tracking. First, we propose a new deep learning based detector to detect cells in each image frame and assign division/non-division labels to them. Second, we carefully design an Earth Mover's Distance (EMD) based hierarchical tracker to associate detected cells through the image sequence and form moving cell trajectories. The tracker is able to correct possible detection errors made by the detector. Evaluated on several open challenge datasets, our approach outperforms state-of-the-art cell tracking methods for determining cell trajectories.

Cell nucleus segmentation is a fundamental task in biomedical image analysis. Generating realistic cell nucleus data with ground truth masks can help tackle difficulties such as insufficient training data for deep learning models and the need to deal with "hard" cases (e.g., tightly clumped nuclei). Known nucleus generation methods generated individual nucleus masks from parametric models or based on direct transformations of real masks. It is difficult for these methods to capture and simulate the distributions of real nuclei and interactions among hard nuclei. In this paper, we propose a new three-stage coarse-to-fine nucleus generation method for 2D and 3D nucleus segmentation. The first stage simulates the positions and sizes of nuclei; the second stage simulates the shapes of nuclei and interactions among clumped nuclei; the third stage simulates the textures of nuclei. We evaluate our method on 2D and 3D cell nucleus image datasets. Experimental results show that our new nucleus generation method considerably helps improve cell nucleus segmentation performance and outperforms known nucleus generation methods for nucleus segmentation with a small amount of training data.

3D object detection on point clouds finds many applications. However, most known point cloud object detection methods did not adequately accommodate the characteristics (e.g., sparsity) of point clouds, and thus some key semantic information (e.g., shape information) is not well captured. In this paper, we propose a new graph convolution (GConv) based hierarchical graph network (HGNet) for 3D object detection, which processes raw point clouds directly to predict 3D bounding boxes. HGNet effectively captures the relationship of the points and utilizes the multi-level semantics for object detection. Specially, we propose a novel shape-attentive GConv (SA-GConv) to capture the local shape features, by modelling the relative geometric positions of points to describe object shapes. An SA-GConv based U-shape network captures the multi-level features, which are mapped into an identical feature space by an improved voting module and then further utilized to generate proposals. Next, a new GConv based Proposal Reasoning Module reasons on the proposals considering the global scene semantics, and the bounding boxes are then predicted. Consequently, our new framework outperforms state-of-the-art methods on two large-scale point cloud datasets, by ~4% mean average precision (mAP) on SUN RGB-D and by ~3% mAP on ScanNet-V2.

Visual relationship is crucial to image understanding and can be applied to many tasks (e.g., image caption and visual question answering). Despite great progress on many vision tasks, relationship detection remains a challenging problem due to the complexity of modeling the widely spread and imbalanced distribution of {subject - predicate - object} triplets. In this paper, we propose a new framework to capture the relative positions and sizes of the subject and object in the feature map and add a new branch to filter out some object pairs that are unlikely to have relationships. In addition, an activation function is trained to increase the probability of some feature maps given an object pair. Experiments on two large datasets, the Visual Relationship Detection (VRD) and Visual Genome (VG) datasets, demonstrate the superiority of our new approach over state-of-the-art methods. Further, ablation study verifies the effectiveness of our techniques.

Metal artifacts commonly appear in computed tomography (CT) images of the patient body with metal implants and can affect disease diagnosis. Known deep learning and traditional metal trace restoring methods did not effectively restore details and sinogram consistency information in X-ray CT sinograms, hence often causing considerable secondary artifacts in CT images. In this paper, we propose a new cross-domain metal trace restoring network which promotes sinogram consistency while reducing metal artifacts and recovering tissue details in CT images. Our new approach includes a cross-domain procedure that ensures information exchange between the image domain and the sinogram domain in order to help them promote and complement each other. Under this cross-domain structure, we develop a hierarchical analytic network (HAN) to recover fine details of metal trace, and utilize the perceptual loss to guide HAN to concentrate on the absorption of sinogram consistency information of metal trace. To allow our entire cross-domain network to be trained end-to-end efficiently and reduce the graphic memory usage and time cost, we propose effective and differentiable forward projection (FP) and filtered back-projection (FBP) layers based on FP and FBP algorithms. We use both simulated and clinical datasets in three different clinical scenarios to evaluate our proposed network's practicality and universality. Both quantitative and qualitative evaluation results show that our new network outperforms state-of-the-art metal artifact reduction methods. In addition, the elapsed time analysis shows that our proposed method meets the clinical time requirement.

We present AntVis, a web-based visual analytics tool for exploring ant movement data collected from the video recording of ants moving on tree branches. Our goal is to enable domain experts to visually explore massive ant movement data and gain valuable insights via effective visualization, filtering, and comparison. This is achieved through a deep learning framework for automatic detection, segmentation, and labeling of ants, ant movement clustering based on their trace similarity, and the design and development of five coordinated views (the movement, similarity, timeline, statistical, and attribute views) for user interaction and exploration. We demonstrate the effectiveness of AntVis with several case studies developed in close collaboration with domain experts. Finally, we report the expert evaluation conducted by an entomologist and point out future directions of this study.

Deep learning has been applied successfully to many biomedical image segmentation tasks. However, due to the diversity and complexity of biomedical image data, manual annotation for training common deep learning models is very timeconsuming and labor-intensive, especially because normally only biomedical experts can annotate image data well. Human experts are often involved in a long and iterative process of annotation, as in active learning type annotation schemes. In this paper, we propose representative annotation (RA), a new deep learning framework for reducing annotation effort in biomedical image segmentation. RA uses unsupervised networks for feature extraction and selects representative image patches for annotation in the latent space of learned feature descriptors, which implicitly characterizes the underlying data while minimizing redundancy. A fully convolutional network (FCN) is then trained using the annotated selected image patches for image segmentation. Our RA scheme offers three compelling advantages: (1) It leverages the ability of deep neural networks to learn better representations of image data; (2) it performs one-shot selection for manual annotation and frees annotators from the iterative process of common active learning based annotation schemes; (3) it can be deployed to 3D images with simple extensions. We evaluate our RA approach using three datasets (two 2D and one 3D) and show our framework yields competitive segmentation results comparing with state-of-the-art methods.

3D image segmentation plays an important role in biomedical image analysis. Many 2D and 3D deep learning models have achieved state-of-the-art segmentation performance on 3D biomedical image datasets. Yet, 2D and 3D models have their own strengths and weaknesses, and by unifying them together, one may be able to achieve more accurate results. In this paper, we propose a new ensemble learning framework for 3D biomedical image segmentation that combines the merits of 2D and 3D models. First, we develop a fully convolutional network based meta-learner to learn how to improve the results from 2D and 3D models (base-learners). Then, to minimize over-fitting for our sophisticated meta-learner, we devise a new training method that uses the results of the baselearners as multiple versions of “ground truths”. Furthermore, since our new meta-learner training scheme does not depend on manual annotation, it can utilize abundant unlabeled 3D image data to further improve the model. Extensive experiments on two public datasets (the HVSMR 2016 Challenge dataset and the mouse piriform cortex dataset) show that our approach is effective under fully-supervised, semisupervised, and transductive settings, and attains superior performance over state-of-the-art image segmentation methods.

Graphics processing units (GPUs) have been widely adopted to accelerate the training of deep neural networks (DNNs). Although the computational performance of GPUs has been improving steadily, the memory size of modern GPUs is still quite limited, which restricts the sizes of DNNs that can be trained on GPUs, and hence raises serious challenges. This paper introduces a framework, referred to as moDNN (memory optimal DNN training on GPUs), to optimize the memory usage in DNN training. moDNN supports automatic tuning of DNN training code to match any given memory budget (not smaller than the theoretical lower bound). By taking full advantage of overlapping computations and data transfers, we develop new heuristics to judiciously schedule data offloading and prefetching transfers, together with convolution algorithm selection, to optimize memory usage. We further devise a new sub-batch size selection method which also greatly reduces memory usage. moDNN can save memory usage up to 59×, compared with an ideal case which assumes that the GPU memory is sufficient to hold all data. When executing moDNN on a GPU with 12 GB memory, the training time is increased by only 3 percent, which is much shorter than that incurred by the best known approach, vDNN. Furthermore, we propose an optimization strategy for moDNN on multiple GPUs again by utilizing the idea of overlapping data transfers and GPU computations. The results show that 3.7× speedup is attained on four GPUs.

With the rapid growth of medical and biomedical image data, energy-efficient solutions for analyzing such image data that can be processed fast and accurately on platforms with low power budget are highly desirable. This paper uses segmenting glial cells in brain microscopy images as a case study to demonstrate how to achieve biomedical image segmentation with significant energy saving and minimal comprise in accuracy. Specifically, we design, train, implement, and evaluate Fully Convolutional Networks (FCNs) for biomedical image segmentation on IBM's neurosynaptic DNN processor - TrueNorth (TN). Comparisons in terms of accuracy and energy dissipation of TN with that of a low power NVIDIA TX2 mobile GPU platform have been conducted. Experimental results show that TN can offer at least two orders of magnitude improvement in energy efficiency when compared to TX2 GPU for the same workload.

With pervasive applications of medical imaging in health-care, biomedical image segmentation plays a central role in quantitative analysis, clinical diagnosis, and medical intervention. Since manual annotation suffers limited reproducibility, arduous efforts, and excessive time, automatic segmentation is desired to process increasingly larger scale histopathological data. Recently, deep neural networks (DNNs), particularly fully convolutional networks (FCNs), have been widely applied to biomedical image segmentation, attaining much improved performance. At the same time, quantization of DNNs has become an active research topic, which aims to represent weights with less memory (precision) to considerably reduce memory and computation requirements of DNNs while maintaining acceptable accuracy. In this paper, we apply quantization techniques to FCNs for accurate biomedical image segmentation. Unlike existing literatures on quantization which primarily targets memory and computation complexity reduction, we apply quantization as a method to reduce overfitting in FCNs for better accuracy. Specifically, we focus on a state-of-the-art segmentation framework, suggestive annotation [26], which judiciously extracts representative annotation samples from the original training dataset, obtaining an effective small-sized balanced training dataset. We develop two new quantization processes for this framework: (1) suggestive annotation with quantization for highly representative training samples, and (2) network training with quantization for high accuracy. Extensive experiments on the MICCAI Gland dataset show that both quantization processes can improve the segmentation performance, and our proposed method exceeds the current state-of-the-art performance by up to 1%. In addition, our method has a reduction of up to 6.4x on memory usage.

Graphics processing units (GPUs) are widely adopted to accelerate the training of deep neural networks (DNNs). However, the limited GPU memory size restricts the maximum scale of DNNs that can be trained on GPUs, which presents serious challenges. This paper proposes an moDNN framework to optimize the memory usage in DNN training. moDNN supports automatic tuning of DNN training code to match any given memory budget (not smaller than the theoretical lower bound). By taking full advantage of overlapping computations and data transfers, we have developed heuristics to judiciously schedule data offloading and prefetching, together with training algorithm selection, to optimize the memory usage. We further introduce a new sub-batch size selection method which also greatly reduces the memory usage. moDNN can save the memory usage up to 50 χ, compared with the ideal case which assumes that the GPU memory is sufficient to hold all data. When executing moDNN on a GPU with 12GB memory, the performance loss is only 8%, which is much lower than that caused by the best known existing approach, vDNN. moDNN is also applicable to multiple GPUs and attains 1.84 χ average speedup on two GPUs.

Structural variation is important in disease etiology and ecological adaptation. Prior work has focused on using either only short paired-end reads or a hybrid approach that combines long and short reads to detect structural variants. Few methods have focused solely on using long reads. Here, we aim to detect a specific type of structural variation, large inversions, using only raw PacBio long reads. We propose a new breakpoint detection approach that is complementary to current state-of-the-art methods and models inversion detection as a Max-Cut problem. We show that this new approach is powerful for detecting large inversions when compared with popular structural variation detection tools. In particular, it yields high Positive Predictive Value (PPV), relatively good sensitivity for detecting large inversions, and shows potential for detecting inversions in more complex genomes. Our software is publicly available at https://bitbucket.org/NDBL/invdet.

Convolution is a fundamental operation in many applications, such as computer vision, natural language processing, image processing, etc. Recent successes of convolutional neural networks in various deep learning applications put even higher demand on fast convolution. The high computation throughput and memory bandwidth of graphics processing units (GPUs) make GPUs a natural choice for accelerating convolution operations. However, maximally exploiting the available memory bandwidth of GPUs for convolution is a challenging task. This paper introduces a general model to address the mismatch between the memory bank width of GPUs and computation data width of threads. Based on this model, we develop two convolution kernels, one for the general case and the other for a special case with one input channel. By carefully optimizing memory access patterns and computation patterns, we design a communication-optimized kernel for the special case and a communication-reduced kernel for the general case. Experimental data based on implementations on Kepler GPUs show that our kernels achieve 5.16x and 35.5% average performance improvement over the latest cuDNN library, for the special case and the general case, respectively.

In this paper, we study a generalization of the classical Voronoi diagram, called the clustering induced Voronoi diagram (CIVD). Different from the traditional model, CIVD takes as its sites the power set $U$ of an input set $P$ of objects. For each subset $C$ of $P$, CIVD uses an influence function $F(C,q)$ to measure the total (or joint) influence of all objects in $C$ on an arbitrary point $q$ in the space $\mathbb{R}^d$ and determines the influence-based Voronoi cell in $\mathbb{R}^d$ for $C$. This generalized model offers a number of new features (e.g., simultaneous clustering and space partition) to the Voronoi diagram which are useful in various new applications. We investigate the general conditions for the influence function which ensure the existence of a small-size (e.g., nearly linear) approximate CIVD for a set $P$ of $n$ points in $\mathbb{R}^d$ for some fixed $d$. To construct CIVD, we first present a stand-alone new technique, called approximate influence (AI) decomposition, for the general CIVD problem. With only $O(n\log n)$ time, the AI decomposition partitions the space $\mathbb{R}^{d}$ into a nearly linear number of cells so that all points in each cell receive their approximate maximum influence from the same (possibly unknown) site (i.e., a subset of $P$). Based on this technique, we develop assignment algorithms to determine a proper site for each cell in the decomposition and form various $(1-\epsilon)$-approximate CIVDs for some small fixed $\epsilon>0$. Particularly, we consider two representative CIVD problems, vector CIVD and density-based CIVD, and show that both of them admit fast assignment algorithms; consequently, their $(1-\epsilon)$-approximate CIVDs can be built in $O(n \log^{\max\{3,d+1\}}n)$ and $O(n \log^{2} n)$ time, respectively.

Ultrasound as a well-established imaging modality is widely used in imaging lymph nodes for clinical diagnosis and disease analysis. Quantitative analysis of lymph node features, morphology, and relations can provide valuable information for diagnosis and immune system studies. For such analysis, it is necessary to first accurately segment the lymph node areas in ultrasound images. In this paper, we develop a new deep learning method, called Coarse-to-Fine Stacked Fully Convolutional Nets (CFS-FCN), for automatically segmenting lymph nodes in ultrasound images. Our method consists of multiple stages of FCN modules. We train the CFS-FCN model to learn the segmentation knowledge from a coarse-to-fine, simple-to-complex manner. A data set of 80 ultrasound images containing both normal and diseased lymph nodes is used in our experiments, which show that our method considerably outperforms the state-of-the-art deep learning methods for lymph node segmentation.

Segmentation of 3D images is a fundamental problem in biomedical image analysis. Deep learning (DL) approaches have achieved the state-of-the-art segmentation performance. To exploit the 3D contexts using neural networks, known DL segmentation methods, including 3D convolution, 2D convolution on the planes orthogonal to 2D slices, and LSTM in multiple directions, all suffer incompatibility with the highly anisotropic dimensions in common 3D biomedical images. In this paper, we propose a new DL framework for 3D image segmentation, based on a combination of a fully convolutional network (FCN) and a recurrent neural network (RNN), which are responsible for exploiting the intra-slice and inter-slice contexts, respectively. To our best knowledge, this is the first DL framework for 3D image segmentation that explicitly leverages 3D image anisotropism. Evaluating using a dataset from the ISBI Neuronal Structure Segmentation Challenge and in-house image stacks for 3D fungus segmentation, our approach achieves promising results, comparing to the known DL-based 3D segmentation approaches.

Shared memory many-core processors such as GPUs have been extensively used in accelerating computation-intensive algorithms and applications. When porting existing algorithms from sequential or other parallel architecture models to shared memory many-core architectures, non-trivial modifications are often needed to match the execution patterns of the target algorithms with the characteristics of many-core architectures. Ray traversal is a fundamental process in many applications, and is commonly accelerated by spatial decomposition schemes captured in hierarchical data structures (e.g., kd-trees). However, ray traversal using hierarchical data structures needs to conduct repeated hierarchical searches. Such search process is time-consuming on shared memory manycore architectures since it incurs considerable amounts of expensive memory accesses and execution divergence. In this paper, we propose a novel spatial decomposition based data structure, called Shell, which completely avoids hierarchical search for ray traversal. In Shell, a structure is built on the boundary of each region in the decomposed space, which allows any ray traversing in a region to find the next neighboring region to traverse using table lookup schemes, without any hierarchical search. While our ray traversal approach works for other spatial decomposition paradigms and many-core processors in higher dimensional scenes, we illustrate it using kd-tree on GPU for 3D scenario and compare with the fastest known kd-tree searching algorithms for ray traversal. Experimental results in graphics ray tracing and radiation dose calculation show that our approach improves the performance by 3.5-5.5χ over the fastest known kd-tree based approaches.

The iris is a stable biometric trait that has been widely used for human recognition in various applications. However, deployment of iris recognition in forensic applications has not been reported. A primary reason is the lack of human-friendly techniques for iris comparison. To further promote the use of iris recognition in forensics, the similarity between irises should be made visualizable and interpretable. Recently, a human-in-the-loop iris recognition system was developed, based on detecting and matching iris crypts. Building on this framework, we propose a new approach for detecting and matching iris crypts automatically. Our detection method is able to capture iris crypts of various sizes. Our matching scheme is designed to handle potential topological changes in the detection of the same crypt in different images. Our approach outperforms the known visible-feature-based iris recognition method on three different data sets. In particular, our approach achieves over 22% higher rank one hit rate in identification, and over 51% lower equal error rate in verification. In addition, the benefit of our approach on multi-enrollment is experimentally demonstrated.

Cell segmentation and motion tracking in time-lapse images are fundamental problems in computer vision, and are also crucial for various biomedical studies. Myxococcus xanthus is a type of rod-like cells with highly coordinated motion. The segmentation and tracking of M. xanthus are challenging, because cells may touch tightly and form dense swarms that are difficult to identify individually in an accurate manner. The known cell tracking approaches mainly fall into two frameworks, detection association and model evolution, each having its own advantages and disadvantages. In this paper, we propose a new hybrid framework combining these two frameworks into one and leveraging their complementary advantages. Also, we propose an active contour model based on the Ribbon Snake, which is seamlessly integrated with our hybrid framework. Evaluated by 10 different datasets, our approach achieves considerable improvement over the state-of-the-art cell tracking algorithms on identifying complete cell trajectories, and higher segmentation accuracy than performing segmentation in individual 2D images.

Glands are vital tissues found throughout the human body and their structure and function are affected by many diseases. The ability to segment and detect glands among other types of tissues is important for the study of normal and disease processes and is readily visualized by pathologists in microscopic detail. In this paper, we develop a new approach for segmenting and detecting intestinal glands in H&E stained histology images, which utilizes a set of advanced image processing techniques such as graph search, ensemble, feature extraction and classification. Our method computes fast, and is able to preserve gland boundaries robustly and detect glands accurately. We tested the performance of gland detection and segmentation by analyzing a dataset of 1723 glands from digitized high-resolution clinical histology images obtained in normal and diseased intestines. The experimental results show that our method outperforms considerably the state-of-the-art methods for gland segmentation and detection tasks.

Monte Carlo based ray tracing (MCBRT) is the foundation of simulating the transport of particles in an inhomogeneous medium, and arises in different applications such as global illumination in graphics rendering and dose calculation in radiation therapy. Due to the computation intensive nature of MCBRT, GPUs have been extensively adopted to accelerate it. However, memory bandwidth becomes a new bottleneck for GPU-based implementations due to the lack of data locality in the MCBRT random memory access patterns. To tackle this issue and consequently improve performance of MCBRT, we present a new locality enhancing method, called LEMCBRT, on CPU-GPU heterogeneous systems. LEMCBRT is based on task partitioning and scheduling, which enhances both the spatial and temporal data locality by organizing random rays into coherent groups. We also develop a CPU-GPU pipeline scheme to reduce the overhead in such ray organization process. To show the applicability of our LEMCBRT method, we apply it to a dose calculation problem in radiation cancer treatment, achieving 6-8X speedup over the best-known GPU solutions on various clinical cases of radiation therapy.

In this paper, we present a new automated algorithm for image completion, i.e., reconstructing the missing, damaged, or occluded parts in images in a visually non-detectable fashion. Our algorithm is capable of recovering both structural and textural information on the damaged parts, by solving several key subproblems such as determining the connections and shapes of the occluded region boundary curves, synthesizing textures, etc. Our algorithm combines structure-based and texture-based approaches and is hinged on optimization techniques. In particular, we formulate a set of key subproblems as optimization problems in graph theory, and solve them optimally in polynomial time. Previous methods for these problems either cannot ensure the topological correctness of the restored structures or rely only on heuristics.

A fundamental problem in computational geometry is to compute an obstacle-avoiding Euclidean shortest path between two points in the plane. The case of this problem on polygonal obstacles is well studied. In this article, we consider the problem version on curved obstacles, which are commonly modeled as splinegons . A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge (polygons are special splinegons), and the combinatorial complexity of each curved edge is assumed to be O (1). Given in the plane two points s and t and a set s of h pairwise disjoint splinegons with a total of n vertices, after a bounded degree decomposition of S is obtained, we compute a shortest s -to- t path avoiding the splinegons in O ( n + h log h + k ) time, where k is a parameter sensitive to the geometric structures of the input and is upper bounded by O ( h 2 ). The bounded degree decomposition of S , which is similar to the triangulation of the polygonal domains, can be computed in O ( n log n ) time or O ( n + h log 1 + ϵ h ) time for any ϵ > 0. In particular, when all splinegons are convex, the decomposition can be computed in O ( n + h log h ) time and k is linear to the number of common tangents in the free space (called “free common tangents”) among the splinegons. Our techniques also improve several previous results: (1) For the polygon case (i.e., when all splinegons are polygons), the shortest path problem was previously solved in O ( n log n ) time, or in O ( n + h 2 log n ) time. Thus, our algorithm improves the O ( n + h 2 log n ) time result, and is faster than the O ( n log n ) time solution for sufficiently small h , for example, h = o (√ n ,log n . (2) Our techniques produce an optimal output-sensitive algorithm for a basic visibility problem of computing all free common tangents among h pairwise disjoint convex splinegons with a total of n vertices. Our algorithm runs in O ( n + h log h + k ) time and O ( n ) working space, where k is the number of all free common tangents. Note that k = O ( h 2 ). Even for the special case where all splinegons are convex polygons , the previously best algorithm for this visibility problem takes O ( n + h 2 log n ) time. (3) We improve the previous work for computing the shortest path between two points among convex pseudodisks of O (1) complexity each. In addition, a by-product of our techniques is an optimal O ( n + h log h ) time and O ( n ) space algorithm for computing the Voronoi diagram of a set of h pairwise disjoint convex splinegons with a total of n vertices.

Fibrin networks, formed during blood clotting, have a large and complicated structure and play a crucial role in regulating blood clot growth. Identifying and analyzing the 3D topological structure of fibrin networks using fluorescence confocal microscopy images is challenging due to their complex anatomy, and known automated methods do not seem to work well. In this paper, we present a two-stage approach for identifying the topological structure of fibrin networks in 3D confocal microscopy images. The first stage segments fibrin networks using a new Indicator-Guided Adaptive Thresholding (IGAT) algorithm. The second stage extracts, prunes, and analyzes the skeleton of fibrin networks in order to identify their topological structure. A new approach based on orientation analysis is applied to refine the extracted topological structure. Evaluation on 3D confocal microscopy images demonstrates that our approach is not sensitive to parameter selection and outperforms the known method, reducing the false positive rate for detecting branch points by 24% and reducing the false negative rate for detecting fiber segments by 15%.

Let P be a set of h pairwise-disjoint polygonal obstacles with a total of n vertices in the plane. In this paper, we consider the problem of building a data structure that can quickly compute an L1 shortest obstacle-avoiding path between any two query points s and t. We build a data structure of size O(n + h2 · log h · 4√log h) in O(n + h2 · log2 h · 4√log h) time that answers each query in O(log n + k) time, where k is the number of edges of the output path. Note that n + h2 · log2 h · 4√log h = O(n+h2+ϵ) for any constant ϵ > 0. We also extend our techniques to the weighted rectilinear version in which the "obstacles" of P are rectilinear regions with "weights" and allow L1 paths to travel through them with weighted costs. Our algorithm answers each query in O(log n + k) time with a data structure of size O(n2 · log n · 4√log n) that is built in O(n2 · log2 n · 4√log n) time.

The Finite Element Method (FEM) is a numerical technique widely used in finding approximate solutions for many scientific and engineering problems. The Data Assembly (DA) stage in FEM can take up to 50% of the total FEM execution time. Accelerating DA with Graphics Processing Units (GPUs) presents challenges due to DA's mixed compute-intensive and memory-intensive workloads. This paper uses a representative finite element mini-application to explore DA acceleration on CPU+GPU platforms. Implementations based on different thread, kernel and task design approaches are developed and compared. Their performance and energy consumption are measured on four CPU+GPU and two CPU only platforms. The results show that (i) the performance and energy for different implementations on the same platform can vary significantly but the performance and energy trends are the same, and (ii) there exist performance and energy tradeoffs across some platforms if the best implementation is chosen for each of the platforms.

In this paper, we study the problem of finding Euclidean shortest paths among curved obstacles in the plane. We model curved obstacles as splinegons. A splinegon can be viewed as replacing each edge of a polygon by a convex curved edge, and each curved edge is assumed to be of O(1) complexity. Given in the plane two points s and t and a set of h pairwise disjoint splinegons with a total of n vertices, we present an algorithm that can compute a shortest path from s to t avoiding the splinegons in O(n+hlogεh+k) time for any ε>0, where k is a parameter sensitive to the input splinegons and k=O(h2). If all splinegons are convex, a common tangent of two splinegons is "free" if it does not intersect the interior of any splingegon; our techniques yield an output sensitive algorithm for computing all free common tangents of the h splinegons in O(n+hlogh+k) time and O(n) working space, where k is the number of all free common tangents.

In this paper, we study a generalization of the classical Voronoi diagram, called clustering induced Voronoi diagram (CIVD). Different from the traditional model, CIVD takes as its sites the power set U of an input set P of objects. For each subset C of P, CIVD uses an influence function F(C, q) to measure the total (or joint) influence of all objects in C on an arbitrary point q in the space ℝd, and determines the influence-based Voronoi cell in ℝdfor C. This generalized model offers a number of new features (e.g., simultaneous clustering and space partition) to Voronoi diagram which are useful in various new applications. We investigate the general conditions for the influence function which ensure the existence of a small-size (e.g., nearly linear) approximate CIVD for a set P of n points in ℝdfor some fixed d. To construct CIVD, we first present a standalone new technique, called approximate influence (AI) decomposition, for the general CIVD problem. With only O(n log n) time, the AI decomposition partitions the space ℝdinto a nearly linear number of cells so that all points in each cell receive their approximate maximum influence from the same (possibly unknown) site (i.e., a subset of P). Based on this technique, we develop assignment algorithms to determine a proper site for each cell in the decomposition and form various (1-ε)-approximate CIVDs for some small fixed € > 0. Particularly, we consider two representative CIVD problems, vector CIVD and density-based CIVD, and show that both of them admit fast assignment algorithms; consequently, their (1 - €)-approximate CIVDs can be built in O(n logd+1n) and O(n log2n) time, respectively.

Given a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, after the free space is triangulated, we present an O(n+h log h) time and O(n) space algorithm for building a data structure (called shortest path map) of size O(n) such that for any query point t, the length of the L_1 shortest obstacle-avoiding path from s to t can be reported in O(log n) time and the actual path can be found in additional time proportional to the number of edges of the path. Previously, the best algorithm computes such a shortest path map in O(n log n) time and O(n) space. In addition, our techniques also yield an improved algorithm for computing the L_1 geodesic Voronoi diagram of m point sites among the obstacles.

Multiple objects in the plane are called pseudodisks if the boundaries of any two of them intersect transversely at most twice. Given a set of $n$ (possibly intersecting) convex pseudodisks of $O(1)$ complexity each and two points $s$ and $t$ in the plane, we present an efficient algorithm for computing a shortest $s$-to-$t$ path avoiding the pseudodisks. After the union of the pseudodisks is computed, which can be done in $O(n\log n)$ randomized time or $O(n\log^2 n)$ deterministic time, our algorithm runs in $O(n\log n+k)$ deterministic time, where $k$ is the size of the extended visibility graph of the union of the pseudodisks. Note that $k = O(n^2)$ in the worst case. In over two decades, the previously best algorithms for this problem have not improved on the bound of $O(n^2\log n)$ time, even when all the pseudodisks are pairwise disjoint disks. Our technique is also applicable to a motion planning problem of finding a shortest path to translate a convex object in the plane from one location to another avoiding a given set of polygonal obstacles, improving the previously best known solution and settling an open problem posed in 1988. Our algorithm actually solves a more general version of the open problem. Further, as a byproduct of our approach, we present an $O(n\log n + k)$-time algorithm for computing the extended visibility graph of a set of $n$ (possibly intersecting) convex pseudodisks in the plane. The previously best known time bound for this visibility problem is $O(n^2 \log n)$.

Remarkable progress has been made in the past few decades in various aspects of radiation therapy (RT). However, some of these promising technologies, such as image-guided online replanning and arc therapy, rely heavily on the availability of fast dose calculation. In this article, based on a popular dose calculation algorithm, the Collapsed-Cone Convolution/Superposition (CCCS) algorithm, we present a multi-FPGA accelerator to speed up radiation dose calculation. Our performance-driven design strategy yields a fully pipelined architecture, which includes a resource-economic raytracing engine and high-performance energy deposition pipeline. An evaluation based on a set of clinical treatment planning cases confirms that our FPGA design almost fully utilizes the available external memory bandwidth and achieves close to the best possible performance for the CCCS algorithm while using less resource. Compared with an existing FPGA design which aimed to accelerate the identical algorithm, the proposed design achieved 1.9X speedup by providing better memory bandwidth utilization (81.7% v.s. 43% of the available external memory bandwidth), higher working frequency (90MHz v.s. 70MHz) and less logic resource usage (25K v.s. 55K logic cells). Furthermore, it obtains a speedup of 20X over a commercial multithreaded software on a quad-core system and 15X performance improvement over closely related results. In terms of accuracy, the measured less than 1% statistical fluctuation indicates that our solution is practical in real medical scenarios.

Ray tracing within a uniform grid volume is a fundamental process invoked frequently by many applications, especially radiation-dose calculation methods in radiotherapy. However, the conflicting features between the GPU memory architecture and the memory-accessing patterns of volume ray tracing lead to inefficient usage of GPU memory bandwidth and waste of capability of modern GPUs. To improve the ray tracing performance on GPU, we propose a lookup-table-based ray tracing method which is specially optimized towards the GPU memory system for processing a massive number of rays. The proposed method is based on a key observation that many of these applications normally involves a massive number of rays, but their ray tracing may not need to follow a specific execution order. Therefore, we divide the 3D space into many regions (called pyramids) and group together the rays falling into the same pyramid. For each ray group, the volume is rotated and resampled for their raytracing. This divide-and-rotate strategy allows the memory access of the ray tracing process to adopt a table-lookup approach and leads to better memory coalescing on GPU. Our proposed method was thoroughly evaluated in four volume setups with randomly-generated rays. The collapsed-cone convolution/superposition (CCCS) dose calculation method is also implemented with/without the proposed approach to verify the feasibility of our method. Compared with the direct GPU implementation of the popular 3DDDA algorithm, our method provides a speedup in the range of 1.91--2.94X for the volume settings we used. Major performance factors, including ray origins, volume size, and pyramid size, are also analyzed. The proposed technique was also found to be able to give a speedup of 1.61--2.17X over the original GPU implementation of the CCCS algorithm. Our experiment results indicate that the proposed approach is capable of offering better coalesced memory access which eventually boosts the raytracing performance on GPU. Moreover, our approach is conceptually simple and can be readily included into various applications.

Identification of both the luminal and the wall areas of the bronchial tree structure from volumetric X-ray computed tomography (CT) data sets is of critical importance in distinguishing important phenotypes within numerous major lung diseases including chronic obstructive pulmonary diseases (COPD) and asthma. However, accurate assessment of the inner and outer airway wall surfaces of a complete 3-D tree structure is difficult due to their complex nature, particularly around the branch areas. In this paper, we extend a graph search based technique (LOGISMOS) to simultaneously identify multiple inter-related surfaces of branching airway trees. We first perform a presegmentation of the input 3-D image to obtain basic information about the tree topology. The presegmented image is resampled along judiciously determined paths to produce a set of vectors of voxels (called voxel columns). The resampling process utilizes medial axes to ensure that voxel columns of appropriate lengths and directions are used to capture the object surfaces without interference. A geometric graph is constructed whose edges connect voxels in the resampled voxel columns and enforce validity of the smoothness and separation constraints on the sought surfaces. Cost functions with directional information are employed to distinguish inner and outer walls. The assessment of wall thickness measurement on a CT-scanned double-wall physical phantom (patterned after an in vivo imaged human airway tree) achieved highly accurate results on the entire 3-D tree. The observed mean signed error of wall thickness ranged from -0.09 ±0.24 mm to 0.07 ±0.23 mm in bifurcating/nonbifurcating areas. The mean unsigned errors were 0.16±0.12 mm to 0.20±0.11 mm. When the airway wall surface was partitioned into meaningful subregions, the airway wall thickness accuracy was the same in most tested bifurcation/nonbifurcation and carina/noncarina regions (p=NS). Once validated on phantoms, our method was applied to human in vivo volumetric CT data to demonstrate relationships of airway wall thickness as a function of luminal dimension and airway tree generation. Wall thickness differences between the bifurcation/nonbifurcation regions were statistically significant (p < 0.05) for tree generations 6, 7, 8, and 9. In carina/noncarina regions, the wall thickness was statistically different in generations 1, 4, 5, 6, 7, and 8.

Multiple objects in the plane are called pseudodisks if they are convex and the boundaries of any two of them intersect transversely at most twice. Given a set of n (possibly intersecting) pseudodisks of O(1) complexity each and two points s and t in the plane, we develop an O(n2) time algorithm for computing a shortest s-to-t path avoiding the pseudodisks. In over two decades, the previously best algorithms for this problem take O(n2 log n) time, even when all pseudodisks are pairwise-disjoint disks. Our technique is also applicable to a motion planning problem of finding a shortest path to translate a convex object in the plane from one location to another avoiding a given set of polygonal obstacles, improving the previously best known solution. Our algorithm actually solves a more general version of the motion planning problem. Further, as a by-product of our approach, we present an O(n2) time algorithm for computing the visibility graph of a set of n (possibly intersecting) pseudodisks in the plane. The previously best known time bound of this visibility problem is O(n2 log n). In addition, for n pairwise disjoint (non-polygonal) convex objects of O(1) complexity each in the plane, we compute a shortest s-to-t path avoiding all objects in O(n log n + k) time, where k is the size of the visibility graph of the objects.

In this paper, we study the problem of segmenting, reconstructing, and analyzing the structure and growth of thrombi (clots) in vivo in blood vessels based on 2-photon microscopic image data. First, we develop an algorithm for segmenting clots in 3-D microscopic images which incorporates the density-based clustering algorithm and other methods for dealing with imaging artifacts. Next, we apply the union-of-balls (or alpha-shape) algorithm to reconstruct the boundary of clots in 3-D. Finally, we perform experimental analysis on the reconstructed clots and obtain quantitative data of thrombus growth and structures. The experiments are conducted on laser-induced injuries in vessels of two types of mice (the wild type and the type with low levels of coagulation factor VII). By analyzing and comparing the developing clot structures based on their reconstruction from image data, we obtain results of biomedical significance. Our quantitative analysis of the clot composition leads to better understanding of the thrombus development, which is also valuable to the modeling and verification of computational simulation of thrombogenesis.

The problem of calculating accurate dose distributions lies in the heart of modern radiation therapy for cancer treatment. Software implementations of dose calculation algorithms are highly costly in terms of CPU time. This paper proposes a multi-engine hardware design for 3D dose calculation based on the collapsed-cone algorithm. The performance of the hardware with one engine (100 Mhz) is already superior to the software counterpart executed on a 2.4 GHz PC. By exploiting the inherent parallelism of the collapsed-cone algorithm, the proposed two-level design with multiple engines can achieve almost a linear speedup compared with the one-engine design. Due to its modular approach, the design can also be easily implemented on a multi-FPGA system for an even greater speedup.

When exploring computing elements made from technologies other than complementary metal-oxide-semiconductor, it is imperative to investigate circuits and systems assuming realistic physical implementation constraints. This paper looks at molecular quantum-dot cellular automata (QCA) devices within this context. With molecular QCA, physical coplanar wire crossings may be very difficult to fabricate in the near to midterm. Here, we consider how this will affect interconnect. We introduce a novel technique to remove wire crossings in a given design in order to facilitate the self-assembly of real circuits - thus, providing meaningful and functional design targets for both physical and computer scientists. The proposed methodology eliminates all wire crossings with minimal logic gate/node duplications. Simulation results based on existing QCA circuits and other benchmarks are presented, and suggest that further investigation is needed.

One goal of contemporary proteome research is the elucidation of cellular protein interactions. Based on currently available protein-protein interaction and domain data, we introduce a novel method, Maximum Specificity Set Cover (MSSC), for the prediction of protein-protein interactions. In our approach, we map the relationship between interactions of proteins and their corresponding domain architectures to a generalized weighted set cover problem. The application of a greedy algorithm provides sets of domain interactions which explain the presence of protein interactions to the largest degree of specificity. Utilizing domain and protein interaction data of S. cerevisiae, MSSC enables prediction of previously unknown protein interactions, links that are well supported by a high tendency of coexpression and functional homogeneity of the corresponding proteins. Focusing on concrete examples, we show that MSSC reliably predicts protein interactions in well-studied molecular systems, such as the 26S proteasome and RNA polymerase II of S. cerevisiae. We also show that the quality of the predictions is comparable to the Maximum Likelihood Estimation while MSSC is faster. This new algorithm and all data sets used are accessible through a Web portal at http://ppi.cse.nd.edu.

This paper presents a leaf sequencing software called SLS (static leaf sequencing) for intensity-modulated radiation therapy (IMRT). SLS seeks to produce improved clinical IMRT treatment plans by (1) shortening their treatment times and (2) minimizing their machine delivery errors. Our SLS software is implemented using the C programming language on Linux workstations and is designed as a separate module to complement the current commercial treatment planning systems. The input to SLS is discrete radiation intensity maps computed by current planning systems, and its output is (modified) optimized control sequences for the radiotherapy machines. Our SLS approach is very different from the commonly used planning methods in medical literature in that it is based on graph algorithms and computational geometry techniques. Comparisons of SLS with the CORVUS commercial planning system indicated that for the same set of discrete radiation intensity maps, treatment times can be shortened by over 30% by our SLS plans while maintaining the same treatment quality. We have used SLS in clinical applications at two cancer treatment centers. This paper discusses the various aspects of the implementation, installation, commissioning, and testing of our SLS software system

Radiation dose calculation is an important step in the treatment of cancer patients requiring radiation therapy. It ensures that the physician prescribed dose agrees with the dose delivered to the patient. Current methods use software implementing either three-dimensional (3D) convolution/superposition algorithms or Monte Carlo analysis. These software methods create a bottleneck in radiation therapy. The required computation time limits both the accuracy of the calculation and the number of patients whom can be treated. This paper presents a novel FPGA implementation for radiation dose calculation. The implementation is based on the 3D convolution/superposition collapsed cone algorithm (Ahnesjo, 1989). To achieve higher accuracy and performance, the original algorithm has been modified and advanced design techniques were applied. Experimental data demonstrate that the FPGA implementation shows significant improvements over software implementation

Efficient segmentation of globally optimal surfaces representing object boundaries in volumetric data sets is important and challenging in many medical image analysis applications. We have developed an optimal surface detection method capable of simultaneously detecting multiple interacting surfaces, in which the optimality is controlled by the cost functions designed for individual surfaces and by several geometric constraints defining the surface smoothness and interrelations. The method solves the surface segmentation problem by transforming it into computing a minimum s-t cut in a derived arc-weighted directed graph. The proposed algorithm has a low-order polynomial time complexity and is computationally efficient. It has been extensively validated on more than 300 computer-synthetic volumetric images, 72 CT-scanned data sets of different-sized plexiglas tubes, and tens of medical images spanning various imaging modalities. In all cases, the approach yielded highly accurate results. Our approach can be readily extended to higher-dimensional image segmentation.

In this paper, we present a new geometric algorithm for the 3-D static leaf sequencing (SLS) problem arising in intensity-modulated radiation therapy (IMRT), a modern cancer treatment technique. The treatment time and machine delivery error are two crucial factors for measuring the quality of a solution (i.e., a treatment plan) for the SLS problem. In the current clinical practice, physicians prefer to use treatment plans with the lowest possible amount of delivery error, and are also very concerned about the treatment time. Previous SLS methods in both the literature and commercial treatment planning systems either cannot minimize the error or achieve that only by treatment plans which require a prolonged treatment time. In comparison, our new geometric algorithm is computationally efficient; more importantly, it guarantees that the output treatment plans have the lowest possible amount of delivery error, and the treatment time for the plans is significantly shorter. Our solution is based on a number of novel schemes and ideas (e.g., mountain reduction, block matching, profile-preserving cutting, etc) which may be of interest in their own right. Experimental results based on real medical data showed that our new algorithm runs fast and produces much better quality treatment plans than current commercial planning systems and well-known algorithms in medical literature.

When exploring computing elements made from technologies other than CMOS, it is imperative to investigate the effects of physical implementation constraints. This paper focuses on molecular quantum-dot cellular automata circuits. For these circuits, it is very difficult for chemists to fabricate wire crossings (at least in the near future). A novel technique is introduced to remove wire crossings in a given circuit to facilitate the self assembly of real circuits - thus providing meaningful and functional design targets for both physical and computer scientists. The technique eliminates all wire crossings with minimal logic gate/node duplications. Experimental results based on existing QCA circuits and other benchmarks are quite encouraging, and suggest that further investigation is needed.

This paper presents the Quantum-Dot Cellular Automata (QCA) physical design problem, in the context of the VLSI physical design problem. The problem is divided into three subproblems: partitioning, placement, and routing of QCA circuits. This paper presents an ILP formulation and heuristic solution to the partitioning problem, and compares the two sets of results. Additionally, we compare a human-generated circuit to the ILP and Heuristic solutions. The results demonstrate that the heuristic is a practical method of reducing partitioning run time while providing a result that is close to the optimal for a given circuit.

In this paper, we address the problem of minimizing energy consumption of real-time tasks on variable voltage processors whose transition energy overhead is not negligible. Voltage settings with minimum number of transitions are found first and sequences of lower voltage cycles are evaluated to decide voltage for each cycle of every task. Experimental results demonstrate that our approach can reduce energy consumed by transitions from 41% to 8% and save more energy.

The static leaf sequencing (SLS) problem arises in radiation therapy for cancer treatments, aiming to accomplish the delivery of a radiation prescription to a target tumor in the minimum amount of delivery time. Geometrically, the SLS problem can be formulated as a 3-D partition problem for which the 2-D problem of partitioning a polygonal domain (possibly with holes) into a minimum set of monotone polygons is a special case. In this paper, we present new geometric algorithms for a basic case of the 3-D SLS problem (which is also of clinical value) and for the general 3-D SLS problem. Our basic 3-D SLS algorithm, based on new geometric observations, produces guaranteed optimal quality solutions using Steiner points in polynomial time; the previously best known basic 3-D SLS algorithm gives optimal outputs only for the case without any Steiner points, and its time bound involves a multiplicative factor of a factorial function of the input. Our general 3-D SLS algorithm is based on our basic 3-D SLS algorithm and a polynomial time algorithm for partitioning a polygonal domain (possibly with holes) into a minimum set of x-monotone polygons, and has a fast running time. Experiments and comparisons using real medical data and on a real radiotherapy machine have shown that our 3-D SLS algorithms and software produce treatment plans that use significantly shorter delivery time and give better treatment quality than the current most popular commercial treatment planning system and the most well-known SLS algorithm. Some of our techniques and geometric procedures (e.g., for the problem of partitioning a polygonal domain into a minimum set of x-monotone polygons) are interesting in their own right.

In this paper, we present a two-phase framework that integrates task assignment, ordering and voltage selection (VS) together to minimize energy consumption of real-time dependent tasks executing on a given number of variable voltage processors. Task assignment and ordering in the first phase strive to maximize the opportunities that can be exploited for lowering voltage levels during the second phase, i.e., voltage selection. In the second phase, we formulate the VS problem as an Integer Programming (IP) problem and solve the IP efficiently. Experimental results demonstrate that our framework is very effective in executing tasks at lower voltage levels under different system configurations.

In this paper we present a new library-oriented cell selection approach to minimize power consumption of combinational circuits. Our unified Mixed Integer Linear-Programming (MILP) formulation selects library cells with different gate sizes, supply voltages and threshold voltages simultaneously during technology mapping. Experimental results on bench-marks mapped to an industrial library show that our technique achieves 19% more power saving in less CPU time comparing with other approaches.

The problem of packing congruent spheres (i.e., copies of the same sph ere) in a bounded domain arises in many applications. In this paper, we present a new pack-and-shake scheme for packing congruent spheres in various bounded 2-D domains. Our packing scheme is based on a number of interesting ideas, such as a trimming and packing approach, optimal lattice packing under translation and/or rotation, shaking procedures, etc. Our packing algorithms have fairly low time complexities. In certain cases, they even run in nearly linear time. Our techniques can be easily generalized to congruent packing of other shapes of objects, and are readily extended to higher dimensional spaces. Applications of our packing algorithms to treatment planning of radiosurgery are discussed. Experimental results suggest that our algorithms produce reasonably dense packings.

As the sizes of many IC design problems become increasingly larger, approximation has become a valuable approach for arriving at satisfactory results without incurring exorbitant computational cost. In this paper, we present several approximation techniques for solving floorplan area minimization problems. These new techniques enable us to reduce both the time and space complexities of the previously best known approximation algorithms by more than a factor of n and n 2 for rectangular and L-shaped subfloorplans, respectively (where n is the number of given implementions). The improvements in the time and space complexities of such approximation techniques is critical to their applicability in floorplan area minimization algorithms. The techniques are quite general, and may be applicable to other classes of approximation problems.

Presents a new method for determining optimal paths in a weighted and dynamic 2D environment, together with some simulation results. After mapping the dynamic and weighted 2D environment onto a static 3D space-time workspace, we represent the 3D workspace by a weighted and framed octree (wf-octree), and find optimal paths in the weighted and dynamic 2D environment by propagating a diamond-shaped path planning wave in the 3D workspace through the uniformly weighted leaf nodes of the wf-octree. A wave propagation heap is introduced to control the process of the wave propagation. Based on interesting data-structural and computational geometric techniques, our approach propagates the path-planning wave through each uniformly-weighted and framed octant efficiently. Our approach guarantees the optimality of the resulting paths without requiring the entire static 3D space-time workspace to be searched. Therefore, it is much more efficient than other commonly-used cell decomposition methods such as the grid-based ones, while it achieves at least the same accuracy as other cell decomposition methods. The distance we compute is based on the L/sub 1/ or L/sub /spl infin// metric.

The problem of processing shortest path queries in graphs arises in application areas such as intelligent transportation

We study the problems of processing single-source and two-point shortest path queries among weighted polygonal obstacles in the rectilinear plane. For the single-source case, we construct a data structure in O(nlog 3/2 n ) time and O(nlog n) space, where n is the number of obstacle vertices; this data structure enables us to report the length of a shortest path between the source and any query point in O(log n) time, and an actual shortest path in O(log n+ k) time, where k is the number of edges on the output path. For the two-point case, we construct a data structure in O(n 2 log 2 n) time and space; this data structure enables us to report the length of a shortest path between two arbitrary query points in O(log 2 n ) time, and an actual shortest path in O(log 2 n + k) time. Our work improves and generalizes the previously best-known results on computing rectilinear shortest paths among weighted polygonal obstacles. We also apply our techniques to processing two-point L 1 shortest obstacle-avoiding path queries among arbitrary (i.e., not necessarily rectilinear) polygonal obstacles in the plane. No algorithm for processing two-point shortest path queries among weighted obstacles was previously known.

We present efficient algorithms for solving the problem of computing an optimal penetration (a ray or a line segment) among weighted regions in 2-D and 3-D spaces.This problem finds applications in several areas, such as radiation therapy, geological exploration, and environmental engineering.Our algorithms are based on a combination of geometric techniques and optimization methods.Our geometric analysis shows that the optimal penetration problem in d-D (d = 2,3) can be reduced to solving O(n2td-l)) instances of certain special types of nonlinear optimization problems, where n is the total number of vertices of the regions.We also give implementation results of our 2-D algorithms. IntroductionIn this paper, we study the following geometric optimization problem (called optimal penetration problem): Given a subdivision R with a total of n vertices in 2-D or 3-D space, divided in m regions R..i, i = 1,2,. . ., m, find a ray L such that L

Article Global register allocation for minimizing energy consumption Share on Authors: Yumin Zhang Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, INView Profile , Xiaobo (Sharon) Hu Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, INView Profile , Danny Z. Chen Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, INView Profile Authors Info & Claims ISLPED '99: Proceedings of the 1999 international symposium on Low power electronics and designAugust 1999 Pages 100–102https://doi.org/10.1145/313817.313877Online:17 August 1999Publication History 4citation75DownloadsMetricsTotal Citations4Total Downloads75Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions.Given an n-vertex polygonal curve P in EL', d 2 3, we approximate P by another polygonal curve P' of m 5 n vertices in IR! such that the vertex sequence of P' is an ordered subsequence of the vertices of P. The goal is to either minimize the size m of P' for a given error tolerance E (called the min-# problem), or to minimize the deviation error E between P and P' for a given size m of P' (called the min-.sproblem).Our techniques enable us to develop efficient nearquadratic-time algorithms in 3-D and sub-cubictime algorithms in 4-D for solving the mm-# and mine problems.We discuss extensions of our solutions to d-dimensional space, where d > 4.

The following problem is studied in this paper: Given a scene with an n-vertex simple polygon and a trajectory path in the plane, construct a data structure for reporting the perspective view from a moving point along the trajectory. We present conceptually simple algorithms for the cases of this problem in which the trajectory path consists of several line segments or of a conic curve that contains the polygon. Our algorithms take O(n log n) time and O(n) space. We also prove that the problem of reporting perspective views from successive points along a trajectory path takes n log n) time in the worst case in the algebraic computation tree model. Our data structure reports the view from any query point on the trajectory in O(k + log n) time for a view of size k. Keywords: Algorithms, visibility, simple polygon, trajectory, topology change, shortest path. 1 Introduction In this paper, we study the following problem: Given a scene with an n-vertex simple polygon P and a trajectory ...

In this paper, we study the following all-pair shortest path query problem: Given the interval model of an unweighted interval graph of n vertices, build a data structure such that each query on the shortest path (or its length) between any pair of vertices of the graph can be processed efficiently (both sequentially and in parallel). We show that, after sorting the input intervals by their endpoints, a data structure can be constructed sequentially in O(n) time and O(n) space; using this data structure, each query on the length of the shortest path between any two intervals can be answered in O(1) time, and each query on the actual shortest path can be answered in O(k) time, where k is the number of intervals on that path. Furthermore, this data structure can be constructed optimally in parallel, in O(log n) time using O(n/log n) CREW PRAM processors; each query on the actual shortest path can be answered in O(1) time using k processors. Our techniques can be extended to solving the all-pair shortest path query problem on circular-arc graphs, both sequentially and in parallel, in the same complexity bounds. As an immediate consequence of our results, we improve by a factor of n the space complexity of the previously best-known sequential all-pair shortest path algorithm for unweighted interval graphs. © 1998 John Wiley & Sons, Inc. Networks 31: 249–258, 1998

Pemmsim to make digil:lldl:[r(i topics td'Jll (Jr patl ollhis m21trlal I'or pcrsmull or classroom IIs< ,s granlc(l L,ilhiml ILCprovided 111:11 Ilw c(>p,cs 'Ire Il[>t!)l:ldL> or dislrihllt~>d till prL)til Of LXIIII 111 C1L,i:ll fi[i\l:lll!:lgC.!ht.L,~)p\,- rigJlt notic.c.(hc title ot'[he pulll Icall(l[l (l[l[i ils dole appear.and nolicc is given LIIA copyright is 11~pcmllsslon (11'llw ;\C1l.[m.'10 copy o[hcnviw, to republish.Iu pos[ on scmvrs or 10 rcdlstrilwlc 10 Iisls.rcqutl-esspccitic permission wvllor lit (Compurm]onol (;comelq, 97 N'icc I'rmlcc

This paper describes how, through a combination of scheduling and buffer insertion, real-time systems may be optimized for power consumption while maintaining deadlines.Beginning with simple examples (components that have no internal pipelines and in which the only design freedoms are buffer insertion and scheduling), we illustrate the effect of adjusting the time at which data are processed on power consumption.Algorithms for optimizing the energy saving are proposed for several real-time system implementations including non-pipelined and pipelined.We also discuss extension to this preliminary work including selection of alternate processing units in order to reduce power consumption while maintaining deadlines.

In this paper we investigate the problem of finding a Euclidean (L/sub 2/) shortest path between two distinct locations in a planar environment. We propose a novel cell decomposition approach which calculates an L/sub 2/ distance transform through the use of a circular path-planning wave. The proposed method is based on a new data structure, called the framed-quadtree, which combines together the accuracy of high resolution grid-based path planning techniques with the efficiency of quadtree-based techniques, hence having the advantages of both. The heart of this method is a linear time algorithm for computing certain special dynamic Voronoi diagrams. The proposed method does not place any unrealistic constraints on obstacles or on the environment and represents an improvement in accuracy and efficiency over traditional path planning approaches in this area.

Approximation has been shown to be an effective method for reducing the time and space costs of solving various floorplan area minimization problems. In this paper, we present several approximation techniques for solving floorplan area minimization problems. These new techniques enable us to reduce both the time and space complexities of the previously best known approximation algorithms by more than a factor of n and n² for rectangular and L-shaped subfloorplans, respectively (where n is the number of given implementations). The efficiency in the time and space complexities is critical to the applicability of such approximation techniques in floorplan area minimization algorithms. We also give a technique for enhancing the quality of approximation results.

We study the problems of processing single-source and all-pairs shortest path queries among weighted polygonal obstacles in the rectilinear plane.For the single-source case, we construct a data structure in O(n log3/2 n) time and O(n log n) space, where n is the number of obstacle vertices; this data structure enables

A conditional shortest path is a collision-free path of shortest distance based on known information on an obstacle-scattered environment at a given time. This paper investigates the problem of finding a conditional L/sub 2/ shortest path through an unknown environment in which path planning is implemented "on the fly" as new obstacle information becomes available through external sensors. We propose a novel cell decomposition approach which calculates an L/sub 2/ distance transform through the use of a circular path-planning wave. The proposed method is based on a new data structure, called the framed-quadtree, which combines together the accuracy of grid-based path planning techniques with the efficiency of quadtree-based techniques, hence having the advantages of both. The heart of this method is a linear time algorithm for computing dynamic Voronoi diagrams.

We present parallel techniques on hypercubes for solving optimally a class of polygon problems. We thus obtain optimal O(log n) time, n-processor hypercube algorithms for the problems of computing the portions of an n-vertex simple polygonal chain C that are visible from a given source point, computing the convex hull of C, testing an n-vertex simple polygon P for monotonicity, and other related problems as well. Previously it was not known how to achieve these complexity bounds on hypercubes, one of the main difficulties being that there is no known optimal sorting hypercube algorithm that achieves these bounds. In fact these are the first optimal geometric hypercube algorithms that do not assume that the input is given already sorted by x or y coordinates. The hypercube model we use is the standard one, with O(1) local memory per processor, and with one port communication.>

We present a technique that can be used to obtain efficient parallel geometric algorithms in the EREW PRAM computational model. This technique enables us to solve optimally a number of geometric problems in O(log n) time using O(n/log n) EREW PRAM processors, where n is the input size of a problem. These problems include: computing the convex hull of a set of points in the plane that are given sorted, computing the convex hull of a simple polygon, computing the common intersection of half-planes whose slopes are given sorted, finding the kernel of a simple polygon, triangulating a set of points in the plane that are given sorted, triangulating monotone polygons and star-shaped polygons, and computing the all dominating neighbors of a sequence of values. PRAM algorithms for these problems were previously known to be optimal (i.e., in O(log n) time and using O(n/log n) processors) only on the CREW PRAM, which is a stronger model than the EREW PRAM.>

Let A be a sorted array of n numbers and B a sorted array of m numbers, both in nondecreasing order, with n/spl les/m. We consider the problem of determining, for each element A(j), j=1, 2, ..., n, the unique element B(i), 0/spl les/i/spl les/m, such that B(i)/spl les/A(j)>

The problem of detecting the weak visibility of an n-vertex simple polygon P is that of finding whether or not P is weakly visible from one of its edges and (if it is) identifying every edge from which P is weakly visible. In this paper, we present an optimal parallel algorithm for solving this problem. Our algorithm runs in O(log n) time using O(n/log n) processors in the CREW-PRAM computational model, and is very different from the sequential algorithms for this problem. This algorithm also enables us to optimally solve, in parallel, several other problems on weakly visible polygons.

article Free Access Share on An optimal parallel algorithm for the visibility of a simple polygon from a point Authors: Mikhail J. Atallah Purdue Univ., West Lafayette, IN Purdue Univ., West Lafayette, INView Profile , Hubert Wagener Technische Univ., Berlin, Germany Technische Univ., Berlin, GermanyView Profile , Danny Z. Chen Purdue Univ., West Lafayette, IN Purdue Univ., West Lafayette, INView Profile Authors Info & Claims Journal of the ACMVolume 38Issue 3July 1991 pp 515–532https://doi.org/10.1145/116825.116827Published:01 July 1991Publication History 19citation554DownloadsMetricsTotal Citations19Total Downloads554Last 12 Months13Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let P be a simple rectilinear convex polygon of size O(n) inside which lie n pairwise disjoint rectangular rectilinear obstacles.We provide parallel techniques for computing rectilinear shortest paths that avoid the set of obstacles in P. Specifically, we compute descriptions of shortest paths in O(log' n) time, with O(n'/ log' n) processors in the CREW-PRAM model if source and destination are on the boundary of P, with O(n'/ log n) processors if the source is an obsta-

We present a parallel algorithm for computing the visible portion of a simple polygonal chain with n vertices from a point in the plane. The algorithm runs in Ο(log n) time using Ο(n/ log n) processors in the CREW-PRAM computational model, and hence is asymptomatically optimal.