Reconstructing dense geometry for dynamic scenes from a monocular video is a critical yet challenging task. Recent memory-based methods enable efficient online reconstruction, but they fundamentally suffer from a Memory Demand Dilemma: The memory representation faces an inherent conflict between the long-term stability required for static structures and the rapid, high-fidelity detail retention needed for dynamic motion. This conflict forces existing methods into a compromise, leading to either geometric drift in static structures or blurred, inaccurate reconstructions of dynamic objects. To address this dilemma, we propose Mem4D, a novel framework that decouples the modeling of static geometry and dynamic motion. Guided by this insight, we design a dual-memory architecture: 1) The Transient Dynamics Memory (TDM) focuses on capturing high-frequency motion details from recent frames, enabling accurate and fine-grained modeling of dynamic content; 2) The Persistent Structure Memory (PSM) compresses and preserves long-term spatial information, ensuring global consistency and drift-free reconstruction for static elements. By alternating queries to these specialized memories, Mem4D simultaneously maintains static geometry with global consistency and reconstructs dynamic elements with high fidelity. Experiments on challenging benchmarks demonstrate that our method achieves state-of-the-art or competitive performance while maintaining high efficiency.

Vision-Language Navigation (VLN) tasks often leverage panoramic RGB and depth inputs to provide rich spatial cues for action planning, but these sensors can be costly or less accessible in real-world deployments. Recent approaches based on Vision-Language Action (VLA) models achieve strong results with monocular input, yet they still lag behind methods using panoramic RGB-D information. We present MonoDream, a lightweight VLA framework that enables monocular agents to learn a Unified Navigation Representation (UNR). This shared feature representation jointly aligns navigation-relevant visual semantics (e.g., global layout, depth, and future cues) and language-grounded action intent, enabling more reliable action prediction. MonoDream further introduces Latent Panoramic Dreaming (LPD) tasks to supervise the UNR, which train the model to predict latent features of panoramic RGB and depth observations at both current and future steps based on only monocular input. Experiments on multiple VLN benchmarks show that MonoDream consistently improves monocular navigation performance and significantly narrows the gap with panoramic-based agents.

Ocular diseases are among the leading causes of visual impairment and blindness worldwide, and early, accurate diagnosis is crucial for preventing disease progression. In recent years, deep learning methods based on fundus images have achieved remarkable progress in intelligent diagnosis, yet they still face challenges such as severe overfitting, redundant features, and insufficient capability in fine-grained lesion recognition. These issues become more pronounced in the Internet of Medical Things (IoMT) scenario, further limiting the generalization and practicality of the models. To address this, this paper proposes a Vision Transformer model incorporating Information Bottleneck and Contrastive Learning mechanisms (FIBCL-ViT) for multi-class fundus disease diagnosis. Using ViT as the backbone, the model introduces a variational information bottleneck module to compress redundant features and highlight task-relevant information, while integrating a contrastive learning strategy to enhance feature discriminability, thereby improving the model’s generalization ability and robustness. During training, the model jointly optimizes cross-entropy loss, contrastive loss, and the information bottleneck regularization term to achieve efficient learning. Experimental results demonstrate that the proposed FIBCL-ViT model outperforms mainstream comparison methods across multiple public fundus image datasets, achieving superior performance in terms of accuracy, AUC, and other metrics. For the 7:3 training–testing split, the proposed method achieves an accuracy of 0.9376, a precision of 0.9384, a recall of 0.9374, and an AUC of 0.9902 on public fundus image datasets. This study provides a novel solution for automated screening and remote intelligent diagnosis of ophthalmic diseases, showing strong potential for clinical applications.

Detecting antagonistic near-balanced dense subgraphs is a crucial problem for community search and conflict detection in graph and network analysis, which has wide applications in social media analysis, business, geopolitics etc. To tackle the absence of a unified definition of antagonistic situation, we propose theantagonismmeasure, which quantifies the quality of subgraphs by three dimensions: polarity, internal cohesion, and external antagonistic normalized density. Inspired by the contribution of small antagonistic balanced patterns to antagonism and balance, this paper introduces an efficient algorithmic framework to mine locally specific pattern densest subgraph structure to find subgraphs with high antagonism. We in particular jointly consider$hx$-pattern compact number and L$hx$PDS and design a new Iterative Propose-Prune-and-Verify pipeline in signed graphs (IPPV-s) for top-$k$L$hx$PDS detection. The key contributions are: (1) The antagonism measure is defined, bridging the gap between structural density and balance theory. (2) An efficient algorithmic pipeline that combines convex optimization with maximum flow verification is proposed, which enables scalable and efficient antagonistic near-balanced dense subgraph discovery. (3) Extensive experiments on real signed network datasets show the effectiveness of our approach in uncovering meaningful subgraphs that capture both cooperative and conflicting dynamics.

Photo-realistic scene reconstruction from sparse-view, uncalibrated images is highly required in practice. Although some successes have been made, existing methods are either Sparse-View but require accurate camera parameters (i.e., intrinsic and extrinsic), or SfM-free but need densely captured images. This paper proposes Dust to Tower (D2T), a novel coarse-to-fine framework to address the coupled difficulty. The key idea is to explicitly narrow down the solution space and then introduce reliable supervision at novel viewpoints without resorting to expensive diffusion-based view synthesis. To do this, we first introduce a Coarse Construction Module (CCM) which exploits a fast Multi-View Stereo model to initialize a 3D Gaussian Splatting (3DGS) and recover initial camera poses. To refine the 3D model at novel viewpoints, we introduce Confidence-Aware Depth Alignment (CADA), which aligns a monocular inverse-depth prior to the reliable regions of the coarse depth using DUSt3R confidence, producing sharp and scale-consistent depth maps for accurate warping. We further propose Warped Image-Guided Inpainting (WIGI), which converts the accurate warped views into multi-view-consistent pseudo supervision via elaborate warping and inpainting process. Experiments on three benchmark datasets show that D2T achieves superior novel view synthesis quality and pose accuracy over ten representative baselines, while keeping high efficiency.

This paper proposes a general solution to enable point cloud recognition models to handle distribution shifts at test time. Unlike prior methods, which rely heavily on training data (often inaccessible during online inference) and are limited to recognizing a fixed set of point cloud classes predefined during training, we explore a more practical and challenging scenario: adapting the model solely based on online test data to recognize both previously seen classes and novel, unseen classes at test time. To this end, we develop Point-Cache, a hierarchical cache model that captures essential clues of online test samples, particularly focusing on the global structure of point clouds and their local-part details. Point-Cache, which serves as a rich 3D knowledge base, is dynamically managed to prioritize the inclusion of high-quality samples. Designed as a plug-and- play module, our method can be flexibly integrated into large multimodal 3D models to support open-vocabulary point cloud recognition. Notably, our solution operates with efficiency comparable to zero-shot inference, as it is entirely training-free. Point-Cache demonstrates substantial gains across 8 challenging benchmarks and 4 representative large 3D models, highlighting its effectiveness. Code is available at https://github.com/auniquesun/Point-Cache.

Deep visual odometry has demonstrated great advancements by learning-to-optimize technology. This approach heavily relies on the visual matching across frames. However, ambiguous matching in challenging scenarios leads to significant errors in geometric modeling and bundle adjustment optimization, which undermines the accuracy and robustness of pose estimation. To address this challenge, this paper proposes MambaVO, which conducts robust initialization, Mamba-based sequential matching refinement, and smoothed training to enhance the matching quality and improve the pose estimation. Specifically, the new frame is matched with the closest keyframe in the maintained Point-Frame Graph (PFG) via the semi-dense based Geometric Initialization Module (GIM). Then the initialized PFG is processed by a proposed Geometric Mamba Module (GMM), which exploits the matching features to refine the overall inter-frame matching. The refined PFG is finally processed by differentiable BA to optimize the poses and the map. To deal with the gradient variance, a Trending-Aware Penalty (TAP) is proposed to smooth training and enhance convergence and stability. A loop closure module is finally applied to enable MambaVO++. On public benchmarks, MambaVO and MambaVO++ demonstrate SOTA performance, while ensuring real-time running.

Collaborative perception in multi-agent system enhances overall perceptual capabilities by facilitating the exchange of complementary information among agents. Current mainstream collaborative perception methods rely on discretized feature maps to conduct fusion, which however, lacks flexibility in extracting and transmitting the informative features and can hardly focus on the informative features during fusion. To address these problems, this paper proposes a novel Anchor-Centric paradigm for Collaborative Object detection (ACCO). It avoids grid precision issues and allows more flexible and efficient anchor-centric communication and fusion. ACCO is composed by three main components: (1) Anchor featuring block (AFB) that targets to generate anchor proposals and projects prepared anchor queries to image features. (2) Anchor confidence generator (ACG) is designed to minimize communication by selecting only the features in the confident anchors to transmit. (3) A local-global fusion module, in which local fusion is anchor alignment-based fusion (LAAF) and global fusion is conducted by spatial-aware cross-attention (SACA). LAAF and SACA run in multilayers, so agents conduct anchor-centric fusion iteratively to adjust the anchor proposals. Comprehensive experiments are conducted to evaluate ACCO on OPV2V and Dair-V2x datasets, which demonstrate ACCO's superiority in reducing the communication volume, and in improving the perception range and detection performances. Code can be found at: https://github.com/sidiangongyuan/ACCO.

Existing tracking-by-detection Multi-Object Tracking methods mainly rely on associating objects with tracklets using motion and appearance features. However, variations in viewpoint and occlusions can result in discrepancies between the features of current objects and those of historical tracklets. To tackle these challenges, this paper proposes a novel Spatial-Temporal Tracklet Graph Matching paradigm (STAR). The core idea of STAR is to achieve long-term, reliable object association through the association of ``tracklet clips (TCs)". TCs are segments of confidently associated multi-object trajectories, which are linked through graph matching. Specifically, STAR initializes TCs using a Confident Initial Tracklet Generator (CITG) and constructs a TC graph via Tracklet Clip Graph Construction (TCGC). In TCGC, each object in a TC is treated as a vertex, with the appearance and local topology features encoded on the vertex. The vertices and edges of the TC graph are then updated through message propagation to capture higher-order features. Finally, a Tracklet Clip Graph Matching (TCGM) method is proposed to efficiently and accurately associate the TCs through graph matching. STAR is model-agnostic, allowing for seamless integration with existing methods to enhance their performance. Extensive experiments on diverse datasets, including MOTChallenge, DanceTrack, and VisDrone2021-MOT, demonstrate the robustness and versatility of STAR, significantly improving tracking performance under challenging conditions.

Vision-Language Navigation is a critical task for developing embodied agents that can follow natural language instructions to navigate in complex real-world environments. Recent advances by finetuning large pretrained models have significantly improved generalization and instruction grounding compared to traditional approaches. However, the role of reasoning strategies in navigation—an action-centric, long-horizon task—remains underexplored, despite Chain-of-Thought reasoning's demonstrated success in static tasks like question answering and visual reasoning. To address this gap, we conduct the first systematic evaluation of reasoning strategies for VLN, including No-Think (direct action prediction), Pre-Think (reason before action), and Post-Think (reason after action). Surprisingly, our findings reveal the Inference-time Reasoning Collaps issue, where inference-time reasoning degrades navigation accuracy, highlighting the challenges of integrating reasoning into VLN. Based on this insight, we propose Aux-Think, a framework that trains models to internalize structured reasoning patterns through CoT supervision during training, while preserving No-Think inference for efficient action prediction. To support this framework, we release R2R-CoT-320k, a large-scale Chain-of-Thought annotated dataset. Empirically, Aux-Think significantly reduces training effort without compromising performance.

The Budget Limited Coreness Maximization (BLCM) problem aims to enhance average user engagement by activating a limited number of connections, i.e., inserting up to b edges to maximize the coreness gain of all vertices in a graph. Due to the cascading feature, we prove the BLCM is NP-hard, APX-hard, and not submodular, meaning greedy sequential edge insertion fails to deliver satisfactory results. As a result, solving BLCM requires combinatorial edge insertion and must face the combinatorial exploration difficulty. This paper proposes the first effective and polynomial-time approach to BLCM. It embeds local combinatorial optimization into global greedy search to boost the benefits of combinatorial optimization while restricting its complexity. Specifically, we propose efficient methods to evaluate the cascaded coreness improvements of two local combinatorial strategies, i.e., when a leader or a group of nodes increase their coreness values via local edge insertion. Note that the key difficulty lies in evaluating the cascading effects. Based on these, we propose three efficient combinatorial edge insertion strategies: (1) Leader-Centric Greedy Insertion (LCGI), (2) Group-Centric Greedy Insertion (GCGI), and (3) a Leader-Group Balance (LGB) insertion. LCGI greedily finds the most influential leader that can produce the highest coreness gain together with its followers. GCGI finds the most influential group that can promote the most coreness gain. LGB combines the two strategies to select edge combinations adaptively. We prove the low complexity of LCGI, GCGI and LGB. Experiments conducted on 13 real-world datasets highlight their practical utility and superiority over existing approaches.

This article proposes a general solution for point set matching that effectively addresses the challenges of low-overlap, sparse, or featureless point set matching (LSFPM). Unlike previous methods that mainly rely on feature or neighborhood similarity that often fail under such difficult conditions, this work proposes a Geometry-based Point Matching (GPM) method. GPM first introduces two geometric concepts: the “Structural Element” (SE) and the “Superstructural Element” (SSE), both of which are constructed based on local geometric structures. The SSE is an enhanced version of the SE. A descriptor for the SE, called the SE Descriptor (SED), is designed to encode the SE and facilitate an efficient geometry-based similarity metric. We demonstrate that the cosine similarity of SEDs is invariant to scale and rotation. Subsequently, a SE Matching Maximization (SEMM) problem is formulated to identify a size-penalized SSE set that maximizes the sum of similarities. This problem is efficiently solved using the proposed SEMM-MCMC (Markov Chain Monte Carlo) algorithm. The matched SSEs then vote on corresponding point matches, generating high-confidence one-to-one matches, low-confidence one-to-one matches and one-to-many matches. Finally, the InferMatch algorithm is proposed to jointly assess low-confidence one-to-one point set matching while simultaneously distinguishing one-to-many point set matching. The GPM approach can also complement other feature-based and motion-based methods. It has been extensively validated on both synthetic and real datasets, demonstrating its versatility in addressing various point set matching problems, and is not limited to the LSFPM problem. Extensive experiments on diverse datasets, including SPair-71k, UAVDT, VisDrone2021-MOT, and SparseMatch, further demonstrate the robustness and versatility of GPM. The proposed approach significantly improves matching performance under challenging conditions and effectively addresses key limitations of existing point set matching methods.

Registering 3D point clouds with low overlap is challenging in 3D computer vision, primarily due to difficulties in identifying small overlap regions and removing correspondence outliers. We observe that the neighborhood similarity can be utilized to detect point correspondence, and the consistent neighborhood correspondence can be used as a criterion to detect robust overlapping regions. So that a Double-layer Multi-scale Star-graph (DMS) structure is proposed to detect robust correspondences using two different types of multi-scale star-graphs. The first-layer Multi-scale Neighbor Feature Star-graphs (MNFS) takes each point as the center and its multi-scale nearest neighbors as the leaves. The MNFS enables to establish the initial correspondence candidate set between the two point clouds based on multi-scale neighborhood topology and feature similarity. Subsequently, each pair of corresponding points find their nearest neighbors within the correspondence sets to construct a Multi-scale Matching Star-graphs (MMS) on each side, so the mutual correspondence relationships between the MMS vertices are identified. These identified mutual correspondences are treated as vertices to construct the Multi-scale Correspondence Star-graphs (MCS), that indicate the relationships among the correspondences. We design edge weight and vertex weight criterion in MCS to detect only the robust correspondence set that has strong neighborhood consistency, so as to reject the outliers. Finally, the point cloud registration is conducted based on the detected robust correspondence. The experimental results demonstrate clearly that the proposed DMS method exhibits superior robustness when compared to existing state-of-the-art registration algorithms.

Registering multiple point clouds (MPC) to form a consistent global map is a crucial problem for various 3D mapping applications, which is however highly challenging due to the tightly coupled difficulties of: 1) identifying the registrable point cloud pairs (RPCPs), 2) detecting the point correspondence in each RPCP, 3) estimating the relative transformation for each RPCP, and 4) aligning the RPCPs to generate the global map. This paper proposes an Iterative Pairing and Transformation (IPT) framework to address above difficulties. A Registrability Graph (RG) is in particular proposed, whose vertices represent the $n$n point clouds and its edges model the registerability between each pair of the point clouds. Registerability is an indicator for whether the relative transformation of the two point clouds can be trustfully estimated. Starting from an $N$N-clique, the obviously unregistrable pairs will be identified through an adaptive coarse registration stage using RANSAC, leading to a sparser RG. For the remained edges in RG, the relative transformation for each registrable pair is accessed by a learning-based pairwise registration algorithm. These pairwise relative poses among vertices are then input into the global registration step, which optimizes and generates globally consistent pose for each point cloud, as well as a global map. Then, based on the global poses of the point clouds, the edges of the RG will be reevaluated to adjusting the registrable pairs, and this local pairing and global optimization process will repeat until convergence. The experimental results show IPT outperforms current state-of-the-art MPC registration algorithms.

View-based methods have demonstrated promising performance in 3D shape understanding. However, they tend to make strong assumptions about the relations between views or learn the multi-view correlations indirectly, which limits the flexibility of exploring inter-view correlations and the effectiveness of target tasks. To overcome the above problems, this article investigates flexible organization and explicit correlation learning for multiple views. In particular, we propose to incorporate different views of a 3D shape into a permutation-invariant set, referred to as View Set, which removes rigid relation assumptions and facilitates adequate information exchange and fusion among views. Based on that, we devise a nimble Transformer model, named VSFormer, to explicitly capture pairwise and higher-order correlations of all elements in the set. Meanwhile, we theoretically reveal a natural correspondence between the Cartesian product of a view set and the correlation matrix in the attention mechanism, which supports our model design. Comprehensive experiments suggest that VSFormer has better flexibility, efficient inference efficiency and superior performance. Notably, VSFormer reaches state-of-the-art results on various 3 d recognition datasets, including ModelNet40, ScanObjectNN and RGBD. It also establishes new records on the SHREC'17 retrieval benchmark.

Bottom-up k-vertex connected component (k- VCC) enumeration methods, referred to as VCCE-BU, have exhib-ited better efficiency compared to the exact top-down k- VCC enumeration method (VCCE-TD). However, VCCE-BU has been found to have surprisingly low detection accuracy, that it may detect fewer k- VCC vertices than VCCE-TD. This raises the question of what causes VCCE-BU to have a low k-VCC enumeration quality. This paper investigates the reason and proposes that the local expansion should be reformulated as a Multiple vertex collaborative Expansion problem instead of the traditional Unitary Expansion (UE). A Multiple Expansion (ME) approach, which allows to expand multiple neighboring vertices jointly and collaboratively is proposed, which is proven exact in local expansion. However, the exact ME-based local expansion needs to explore large neighborhoods in each step, which is time-consuming. To address the efficiency issue, a Ring-based Multiple Expansion (RME) is proposed to conduct ME within one-hop neighbors. A maximum flow-based merging algorithm FBM is proposed for effective merging. A maximal clique and breath-first-search-based quick seeding algorithm QkVCS is proposed to generate k-VCC seeds efficiently. As a result, RIPPLE which integrates QkVCS+FBM+RME is presented as a new accurate and efficient bottom-up approach. Extensive verifications in real large-scale graph datasets demonstrate that even the single-thread RIPPLE is much more accurate and a magnitude faster than the state-of-the-art VCCE-BU method. We also demonstrate the effective speeding up to run RIPPLE in parallel.

The availability of city-scale Lidar maps enables the potential of city-scale place recognition using mobile cameras. However, the city-scale Lidar maps generally need to be compressed for storage efficiency, which increases the difficulty of direct visual place recognition in compressed Lidar maps. This paper proposes VOLoc, an accurate and efficient visual place recognition method that exploits geometric similarity to directly query the compressed Lidar map via the real-time captured image sequence. In the offline phase, VOLoc compresses the Lidar maps using a Geometry-Preserving Compressor (GPC), in which the compression is reversible, a crucial requirement for the downstream 6DoF pose estimation. In the online phase, VOLoc proposes an online Geometric Recovery Module (GRM), which is composed of online Visual Odometry (VO) and a point cloud optimization module, such that the local scene structure around the camera is online recovered to build the Querying Point Cloud (QPC). Then the QPC is compressed by the same GPC, and is aggregated into a global descriptor by an attentionbased aggregation module, to query the compressed Lidar map in the vector space. A transfer learning mechanism is also proposed to improve the accuracy and the generality of the aggregation network. Extensive evaluations show that VOLoc provides localization accuracy even better than the Lidar-toLidar place recognition, setting up a new record for utilizing the compressed Lidar map by low-end mobile cameras. The code are publicly available at https://github.com/Master-cai/VOLoc.

This paper presents a parameter-efficient prompt tuning method, named PPT, to adapt a large multi-modal model for 3D point cloud understanding. Existing strategies are quite expensive in computation and storage, and depend on timeconsuming prompt engineering. We address the problems from three aspects. Firstly, a PromptLearner module is devised to replace hand-crafted prompts with learnable contexts to automate the prompt tuning process. Then, we lock the pre-trained backbone instead of adopting the full fine-tuning paradigm to substantially improve the parameter efficiency. Finally, a lightweight PointAdapter module is arranged near target tasks to enhance prompt tuning for 3D point cloud understanding. Comprehensive experiments are conducted to demonstrate the superior parameter and data efficiency of the proposed method. Meanwhile, we obtain new records on 4 public datasets and multiple 3D tasks, i.e., point cloud recognition, few-shot learning, and part segmentation. The implementation is available at https://github.com/auniquesun/PPT.

Multi-object tracking (MOT) on static platforms, such as by surveillance cameras, has achieved significant progress, with various paradigms providing attractive performances. However, the effectiveness of traditional MOT methods is significantly reduced when it comes to dynamic platforms like drones. This decrease is attributed to the distinctive challenges in the MOT-on-drone scenario: (1) objects are generally small in the image plane, blurred, and frequently occluded, making them challenging to detect and recognize; (2) drones move and see objects from different angles, causing the unreliability of the predicted positions and feature embeddings of the objects. This paper proposes DroneMOT, which firstly proposes a Dual-domain Integrated Attention (DIA) module that considers the fast movements of drones to enhance the drone-based object detection and feature embedding for small-sized, blurred, and occluded objects. Then, an innovative Motion-Driven Association (MDA) scheme is introduced, considering the concurrent movements of both the drone and the objects. Within MDA, an Adaptive Feature Synchronization (AFS) technique is presented to update the object features seen from different angles. Additionally, a Dual Motion-based Prediction (DMP) method is employed to forecast the object positions. Finally, both the refined feature embeddings and the predicted positions are integrated to enhance the object association. Comprehensive evaluations on VisDrone2019-MOT and UAVDT datasets show that DroneMOT provides substantial performance improvements over the state-of-the-art in the domain of MOT on drones. The code will be available at https://github.com/PenK1nG/DroneMOT.

Image matching aims at identifying corresponding points between a pair of images. Currently, detector-free methods have shown impressive performance in challenging scenarios, thanks to their capability of generating dense matches and global receptive field. However, performing feature interaction and proposing matches across the entire image is unnecessary, because not all image regions contribute to the matching process. Interacting and matching in unmatchable areas can introduce errors, reducing matching accuracy and efficiency. Meanwhile, the scale discrepancy issue still troubles existing methods. To address above issues, we propose PRogressive dependency maxImization for Scale-invariant image Matching (PRISM), which jointly prunes irrelevant patch features and tackles the scale discrepancy. To do this, we firstly present a Multi-scale Pruning Module (MPM) to adaptively prune irrelevant features by maximizing the dependency between the two feature sets. Moreover, we design the Scale-Aware Dynamic Pruning Attention (SADPA) to aggregate information from different scales via a hierarchical design. Our method's superior matching performance and generalization capability are confirmed by leading accuracy across various evaluation benchmarks and downstream tasks. The code is publicly available at https://github.com/Master-cai/PRISM.

Collaborative autonomous driving with multiple vehicles usually requires the data fusion from multiple modalities. To ensure effective fusion, the data from each individual modality shall maintain a reasonably high quality. However, in collaborative perception, the quality of object detection based on a modality is highly sensitive to the relative pose errors among the agents. It leads to feature misalignment and significantly reduces collaborative performance. To address this issue, we propose RoCo, a novel unsupervised framework to conduct iterative object matching and agent pose adjustment. To the best of our knowledge, our work is the first to model the pose correction problem in collaborative perception as an object matching task, which reliably associates common objects detected by different agents. On top of this, we propose a graph optimization process to adjust the agent poses by minimizing the alignment errors of the associated objects, and the object matching is re-done based on the adjusted agent poses. This process is carried out iteratively until convergence. Experimental study on both simulated and real-world datasets demonstrates that the proposed framework RoCo consistently outperforms existing relevant methods in terms of the collaborative object detection performance, and exhibits highly desired robustness when the pose information of agents is with high-level noise. Ablation studies are also provided to show the impact of its key parameters and components. The code is released at https://github.com/HuangZhe885/RoCo.

This paper investigates the 3D domain generalization (3DDG) ability of large 3D models based on prevalent prompt learning. Recent works demonstrate the performances of 3D point cloud recognition can be boosted remarkably by parameter-efficient prompt tuning. However, we observe that the improvement on downstream tasks comes at the expense of a severe drop in 3D domain generalization. To resolve this challenge, we present a comprehensive regulation framework that allows the learnable prompts to actively interact with the well-learned general knowledge in large 3D models to maintain good generalization. Specifically, the proposed framework imposes multiple explicit constraints on the prompt learning trajectory by maximizing the mutual agreement between task-specific predictions and task-agnostic knowledge. We design the regulation framework as a plug-and-play module to embed into existing representative large 3D models. Surprisingly, our method not only realizes consistently increasing generalization ability but also enhances task-specific 3D recognition performances across various 3DDG benchmarks by a clear margin. Considering the lack of study and evaluation on 3DDG, we also create three new benchmarks, namely base-to-new, cross-dataset and few-shot generalization benchmarks, to enrich the field and inspire future research. Code and benchmarks are available at \url{https://github.com/auniquesun/Point-PRC}.

Detecting locally, non-overlapping, near-clique densest subgraphs is a crucial problem for community search in social networks. As a vertex may be involved in multiple overlapped local cliques, detecting locally densest sub-structures considering h -clique density, i.e., locally h-clique densest subgraph (LhCDS) attracts great interests. This paper investigates the L h CDS detection problem and proposes an efficient and exact algorithm to list the top- k non-overlapping, locally h -clique dense, and compact subgraphs. We in particular jointly consider h -clique compact number and L h CDS and design a new ''Iterative Propose-Prune-and-Verify'' pipeline (IPPV) for top- k L h CDS detection. (1) In the proposal part, we derive initial bounds for h -clique compact numbers; prove the validity, and extend a convex programming method to tighten the bounds for proposing L h CDS candidates without missing any. (2) Then a tentative graph decomposition method is proposed to solve the challenging case where a clique spans multiple subgraphs in graph decomposition. (3) To deal with the verification difficulty, both a basic and a fast verification method are proposed, where the fast method constructs a smaller-scale flow network to improve efficiency while preserving the verification correctness. The verified L h CDSes are returned, while the candidates that remained unsure reenter the IPPV pipeline. (4) We further extend the proposed methods to locally more general pattern densest subgraph detection problems. We prove the exactness and low complexity of the proposed algorithm. Extensive experiments on real datasets show the effectiveness and high efficiency of IPPV. Codes are available at: https://github.com/Elssky/IPPV

When the edge between two nodes is not measured, is there any hint to know the edge property, and will the inferred edge property be useful? To answer these questions, this paper uniformly defines the properties of unmeasurable edges in generic graphs. For an unmeasurable edge$(i,j)$, it is called rangeable if its length is unique in any realization of the graph, rigid if the number of its possible lengths is finite, and flexible if it has infinite possible lengths. The rangeable edge can provide deterministic hidden knowledge as if the edge is measured. A condition for an unmeasured edge being rangeable in 2D space is firstly proposed, based on which a centralized identification algorithm (DRE) is designed. However, the centralized rangeable edge identification has the overhead of global information collection. Therefore distributed condition and algorithm to identify rangeable edges are further investigated. We prove that an unmeasurable edge$(i,j)$is rangeable if there are at least two Disjoint Minimally Rigid Branches (DMRBs) between$i$and$j$. The unmeasurable edge$(i,j)$is rigid and flexible when the number of DMRB is one and zero, respectively. A distributed Branching and Blacklisting (BB) algorithm is proposed to find DMRBs, so that rangeable edges are identified distributively. Then, the applications of rangeable, rigid, and flexible edges are discussed. Experimental evaluations show that the centralized and distributed algorithms can identify a rich set of unmeasurable but rangeable edges in distance graphs, even more than the number of directly measured edges. Moreover, BB has a similar identification performance as the centralized DRE algorithm and outperforms existing distributed unmeasurable edge inference algorithms significantly.

Identifying the Maximal Rigid subGraphs (MRGs) whose relative formations cannot deform continuously in$\Re ^{d}$, is a fundamental problem in network formation control and network localization. When$d=3$, it becomes extremely challenging and has been open for decades because the fundamental Laman condition doesn’t hold in$\Re ^{3}$. This paper presents a new understanding of this problem. Because of the existence of “implicit hinges” in 3D, its essence should be to detect the Maximal Rigid Clusters (MRCs). An MRC is a maximal set of vertices in which each vertex is mutually rigid to the others, but the vertices are not necessarily connected. We show that the MRGs in the original graph can be easily deduced from the connected components generated by the MRCs. For efficiently identifying the MRCs, at first, a randomized algorithm to detect mutually rigid vertex pairs is exploited. Based on this, a Basic MRC Identification algorithm (BMI) is proposed, which is an exact algorithm that can detect all MRCs based on the extracted rigid vertex pairs, but it has$O(|V|^{4})$time complexity. To further pursue an efficient algorithm, we observe the “hinge MRCs” appear rarely. So an Efficient framework for MRC Identification (EMI) is proposed. It consists of two steps: 1) a Trimmed-BMI algorithm that guarantees to detect all simple MRCs and may miss only hinge MRCs; 2) a Trim-FIX algorithm that can find all hinge MRCs. We prove EMI can guarantee to detect all the MRCs as accurately as BMI, using$O(|V|^{3})$times. Further, we show EMI achieves magnitudes of times faster than BMI in experiments. Extensive evaluations verify the effectiveness and high efficiency of EMI in various 3D networks. We have uploaded the code of the related program tohttps://github.com/fdwqh/EMI-algorithm.

Ranging-based localization is a fundamental problem in the Internet of Things and unmanned aerial vehicle networks. However, the nodes’ limited-ranging scope and users’ broad coverage purpose inevitably cause network sparsity or subnetwork sparsity. The performances of existing localization algorithms are extremely unsatisfactory in sparse networks. A crucial way to deal with the sparsity is to exploit the hidden knowledge provided by the unmeasured edges, which inspires this work to propose a hypothesis-based Joint Edge Inference and Localization algorithm called InferLoc . InferLoc mines the Unmeasured but Inferable Edges (UIEs). Each UIE is an unmeasured edge, but it is restricted through other edges in the network to be inside a rigid component, so it has only a limited number of possible lengths. We propose an efficient method to detect UIEs and geometric approaches to infer possible lengths for UIEs in 2D and 3D networks. The inferred possible lengths of UIEs are then treated as multiple hypotheses to determine the node locations and the lengths of UIEs simultaneously through a joint graph optimization process. In the joint graph optimization model, to make the 0/1 decision variables for hypotheses selection differentiable, differentiable functions are proposed to relax the 0/1 selections, and rounding is applied to select the final length after the optimization converges. We also prove the condition when a UIE can contribute to sparse localization. Extensive experiments show remarkably better accuracy and efficiency performances of InferLoc than the state-of-the-art network localization algorithms. In particular, it reduces the localization errors by more than 90% and speeds up the convergence time more than 100 times than that of the widely used G2O-based methods in sparse networks.

Recently, a growing number of work design unsupervised paradigms for point cloud processing to alleviate the limitation of expensive manual annotation and poor transferability of supervised methods. Among them, CrossPoint follows the contrastive learning framework and exploits image and point cloud data for unsupervised point cloud understanding. Although the promising performance is presented, the unbalanced architecture makes it unnecessarily complex and inefficient. For example, the image branch in CrossPoint is ~8.3x heavier than the point cloud branch leading to higher complexity and latency. To address this problem, in this paper, we propose a lightweight Vision-and-Pointcloud Transformer (ViPFormer) to unify image and point cloud processing in a single architecture. ViPFormer learns in an unsupervised manner by optimizing intra-modal and cross-modal contrastive objectives. Then the pretrained model is transferred to various downstream tasks, including 3D shape classification and semantic segmentation. Experiments on different datasets show ViPFormer surpasses previous state-of-the-art unsupervised methods with higher accuracy, lower model complexity and runtime latency. Finally, the effectiveness of each component in ViPFormer is validated by extensive ablation studies. The implementation of the proposed method is available at https://github.com/auniquesun/ViPFormer.

The basic components of a point-based 3D object detector is set abstraction (SA) layer, which down-samples points for better efficiency and enlarges receptive fields. However, existing SA layer only takes the relative locations among points into consideration, e.g. using furthest point sampling (FPS), while ignoring point features. Because the points on the objects take small proportion of space, the cascaded SA may miss to contain objects' points in the last layer, which will degrade the 3D object detection performances. We design a new lightweight and effective SA layer named Boundary-Aware Set Abstraction layer (BA-Net) to retain important foreground and boundary points during cascaded down-sampling. Technically, a lightweight point segmentation model (PSM) to compute the point-wise foreground scores is firstly embedded, then a Boundary Prediction Model (BPM) to detect the points on the object boundaries is proposed. These semantic scores are used to weight inter-node distances and the Boundary-aware Furthest Point down-Sampling (B-FPS) is conducted in this twisted distance space. Experimental results show that BA-Net can enhance the average accuracy (mAP) of the most competitive car class on the KITTI dataset by 1.14% and 1.06% in two different baseline. Code is available at https://github.com/HuangZhe885/Boundary-Aware-SA.

Over the past years, augmented reality (AR) based on mobile phones has gained great attention. When multiple phones are used in AR applications, collaborative simultaneous localization and mapping (SLAM) is considered one of the enabling technologies, i.e., multiple mobile phones complete the localization and mapping through collaboration. However, the state-of-the-art collaborative SLAM systems not only suffer from the delays introduced by a high-complexity graph optimization problem, but also may exhibit varying levels of accuracy across dissimilar environments or different types of mobile devices. In this paper, we propose a scalable and robust collaborative SLAM system, point-line-based Collaborative SLAM (ColSLAM). Technically, ColSLAM includes two innovative features that help achieve satisfactory scalability and robustness. First, a mapping cacher (MC) is designed for each agent on the server, which uses global keyframes to detect loop closures, updates the cached local map, and quickly responds to the agent's pose drifts. With MC, each agent's local pose is corrected using global knowledge in real-time. Secondly, to improve the robustness performance, ColSLAM employs point-line-fusion-based Visual Inertial Odometry (VIO), point-line-fusion-based NetVLAD loop detection, and an enhanced geometric verification and relative pose calculation method called PNPL. Empirical evaluations based on the EuRoc dataset and real degenerate environments demonstrate that ColSLAM outperforms the existing collaborative SLAM systems in terms of accuracy, robustness, and scalability.

Distributed estimation of 6-DOF relative states, including three-dimensional relative poses and three-dimensional relative positions, is a key problem in UAV (Unmanned Aerial Vehicle) networks, which generally requires vision-involved iterative state estimation. How to achieve communication efficiency is a crucial challenge considering the large volume of vision data. This paper jointly considers the communication efficiency, latency, and accuracy for distributed relative state estimation involving vision data in UAV networks. The key is to solve a distributed graph optimization problem, which includes two key steps: (1) local graph construction and node state initialization in an initialization phase, and (2) iterative state update and communication with neighbors until convergence in online iteration phase. A communication efficient, Locating Then Informing (LTI) initialization scheme is proposed, which is run only once by each node to initialize each node’s local graph and initial states. For online iteration, a RIPPLE-like distributed state iteration scheme is proposed. It inherits the advantages of traditional sequential and parallel methods while avoiding their drawbacks. It enables nodes’ states to converge quickly using fewer rounds of communications. The communication costs for the initialization and online iteration processes are analyzed theoretically. Extensive evaluations use synthetic data generated by AirSim (a widely used UAV network simulation platform) and real-world data are presented. The results show that the proposed method provides accuracy comparable to the centralized graph optimization method and significantly outperforms the other distributed methods in terms of accuracy, communication cost, and latency.

The barycentric linear localization (BLL) methods provide a lightweight, distributed way to calculate locations for resource-limited IoT devices. A crucial requirement for BLL is that the nodes participating in the iterative location propagation are localizable. Otherwise, the unlocalizable nodes will continuously pose error information in the location propagation process, making even the theoretically localizable nodes converge to the wrong locations. However, the research on node localizability in BLL is much lacked, greatly limiting the application scope of BLL. In specific, BLL node localizability is detected on a generated graph$\mathcal {G^{A}}$. For any node, its neighbors appear in$\mathcal {G^{A}}$only when the neighbors can form triangle(s), so that$\mathcal {G^{A}}$is much sparser than the original$\mathcal G$. Thus, the node localizability condition in BLL is harder to be satisfied than that in traditional localization methods. Moreover, the distributed algorithm to detect BLL localizable nodes is still open. This paper thoroughly investigates the node localizability conditions and distributed localizable node detection algorithms in BLL. At first, an efficient and fully distributed Negative Edge Inference (NEI) algorithm is proposed for each node to infer implicit edges in its neighborhood. NEI strengthens the distance graph by revealing more distance constraints so that enables more neighboring triangles. Then a new sufficient condition, i.e., the recursive three disjoint path condition (Recursive-3DP) on the strengthened distance graph is proposed to identify BLL localizable nodes much more accurately. Secondly, a distributed Path Extension and Pruning (PEP) algorithm is proposed for distributed localizable node detection. PEP is proved to detect all the theoretically Recursive-3DP nodes in the strengthened distance graph. A Fast-PEP algorithm is further proposed, which misses very limited Recursive-3DP nodes while bringing significant improvement in efficiency. PEP and Fast-PEP guarantee to identify BLL localizable nodes in$2H$rounds, where$H$is the maximum hop number of the node disjoint paths. Finally, by using NEI and PEP (Fast-PEP), a localizability-aware BLL (LABEL) method is proposed, which correctly identifies localizable nodes and guarantees their correct location convergence. Extensive analysis and experiments show the advantages in localizability and location accuracy of the proposed schemes over the state-of-the-art methods.

Determining whether nodes can be uniquely localized, called localizability detection, is a concomitant problem in network localization. Localizability detection under the traditional Non-Linear Localization (NLL) schema has been well explored, whereas localizability under the emerging Barycentric coordinate-based Linear Localization (BLL) schema has not been well investigated. Non-awareness of the node localizability in BLL may cause theoretically localizable nodes to converge to wrong locations because their locations are impacted by the wrong locations of the unlocalizable nodes through the iterative location propagation. In this article, the deficiency of existing localizability theories and algorithms in BLL is firstly investigated and then a necessary condition and a sufficient condition for BLL node localizability detection are proposed. Based on these two conditions, an efficient Iterative Maximum Flow (IMF) algorithm is designed to identify BLL localizable nodes, and only localizable nodes are selected to enable a Localizability Aware Barycentric Linear Localization (LABLL) algorithm, which can guarantee the locations of the localizable nodes converging correctly. The proposed IMF and LABLL algorithms are validated by both theoretical analysis and experimental evaluations.

Partitioning the Maximal Redundant Rigid Components (MRRC) and Maximal Global Rigid Components (MGRC) in generic 2D graphs are critical problem for network structure analysis, network localizability detection, and localization algorithm design. This article presents efficient algorithms to partition MRRCs and MGRCs and develops an open-sourced toolbox, GPART, for these algorithms to be conveniently used by the society. We firstly propose conditions and an efficient algorithm to merge the over-constrained regions to form the maximal redundant rigid components (MRRC). The detected MRRCs are proved to be maximal and all the MRRCs are guaranteed to be detected. The time to merge the over-constrained regions is linear to the number of nodes in the over-constrained components. To detect MGRCs, the critical problem is to decompose 3-connected components in each MRRC. We exploit SPQR-tree based method and design a local optimization algorithm, called MGRC_acce to prune the unnecessary decomposition operations so that the SPQR-tree functions can be called much less number of times. We prove the MGRCs can be detected inside MRRCs using at most O(mn ) time. Then a GPART toolbox is developed and extensively tested in graphs of different densities. We show the proposed MRRC and MGRC detection algorithms are valid and MGRC_acce greatly outperforms the direct SPQR-tree based decomposition algorithm. GPART is outsourced at https://github.com/inlab-group/gpart .

The virtual try-on (VTON) system in augmented reality (AR) has attracted significant research interest. This paper presents a novel real-time AR virtual shoe try-on system (VTONShoes). Users can see the virtual shoes with full degrees of freedom on the mobile device. In particular, we propose an efficient framework to detect, classify, and recover 6-DoF pose of shoes from the captured images and then accurately render the 3D shoe model on the screen in realtime and in full degrees of freedom. For accurate pose recovery, dense keypoints are designed on the 3D shoe model. An efficient joint 2D keypoint localization and leg silhouette segmentation module (KeyPointLoc) is designed to predict keypoint projections on 2D images and the shoe-leg occlusion relationship. In order to reduce jitter between frames, an optimization-based framework with the longest continuous invariant subarray constraints is proposed to minimize classification errors caused by model switching, and a smoothing module with Exponential Weights Decay is presented to post-process the rendered results. We also developed a large-scale dataset named Diverse-Shoes which contains images extracted from 80K videos, annotated with the shoe bounding box, transformation matrices, and silhouettes of legs. Our system has achieved a smooth and stable try-on effect on mainstream devices with a real-time speed of around 25 to 45 FPS on mainstream mobile phones, which significantly outperforms state-of-the-art methods for real-time performance and rendering accuracy.

Inferring network topology via inter-node distance measurements is an important problem. It is challenging when the distance measurements are sparse because the lack of edge constraints may lead to ambiguous realizations that differ greatly from the ground truth. The flipping ambiguities are caused by binary vertex cut sets in 2D and triple vertex cut sets in 3D, which are calledseparators. This paper investigates conditions on whether the flipping ambiguities caused by these separators can be disambiguated using neighborhood, full graph, and component-level conditions. Accordingly, local flipping-free condition (LFFC), global flipping-free condition (GFFC), and component-based flipping free condition (CFFC) are proposed. Then a disambiguating framework based on a combinatorial application of these conditions is proposed. It detects separators and first disambiguate separators locally by LFFC, which converts the graph to a binary tree, whose leaf nodes are flipping-free components and edges are LFFC unsolvable separators. Then the CFFC condition is further applied to disambiguate LFFC unsolvable separators between components. If$k$and$g$separators are disambiguated by LFFC and CFFC respectively, the number of ambiguous solutions for network localization will be reduced by${2^{k+g}}$times. Finally, the flipping-free components realize node coordinates in their local coordinate systems and a residue-based weighted component stitching algorithm (RWCS) is proposed to iteratively synchronize components’ local coordinates to generate global coordinates of the network. Extensive simulations show the LFFC, CFFC and RWCS frameworks are efficient, which resolve a major portion of flipping ambiguities and greatly improve the localization accuracy than the state of art algorithms in various sparse network settings.

The rapid popularization of mobile devices makes it more convenient and cost-efficient to collect synchronized WiFi received signal strength (RSS) and inertial measurement unit sequences by crowdsensing. The transition model has proven to be a promising unsupervised localization approach that captures the transition relationship between the change of RSS signal space and the change of physical space, alleviating the need of extra knowledge for creating radio map. However, it faces two essential challenges in real-world deployments. First, model coverage affects its locating performance, because a specific transition model only represents its local space. Second, the instability of RSS leads to a conflicting relationship between changes of two spaces because of the complex environment and the heterogeneous type of devices. To address these challenges, we propose Lightgbm-CTMM, a novel unsupervised localization framework. First, a clustering method is adopted to capture the expected relationship to ensure robust coverage. Second, direction filter is employed to guarantee that the change in signal space corresponds to the change in physical space. The feasibility and effectiveness of Lightgbm-CTMM are evaluated by extensive experiments, and the locating performance of Lightgbm-CTMM is better than that of conventional approaches. Moreover, Lightgbm-CTMM reduces the work on quality assessment of trajectories.

Cyberbullying has caused serious consequences especially for social network users in recent years. However, the challenge is how to fight against the cyberbullying effectively from the algorithmic perspective. In this article, we study the fighting against the cyberbullying problem, i.e., identify an initial witness set with a budget to spread the positive influence to protect the users in a specific target set such that the number of cybervictim users in the target set being activated by the seed set of cyberbullying is minimized. We first formulate this problem and show its NP-hardness. We further prove that the objective function is submodular with respect to the size of witnesses set when we convert the original problem into the maximal version. Then we propose a stochastic approach to solve this maximal version problem based on the Reverse Sampling Technique with a constant factor guarantee. In addition, we provide theoretical analysis and discuss the relationship between the optimal value and the value returned by the proposed algorithm. To evaluate the proposed approach, we implement extensive experiments on synthetic and real datasets. The experimental results show our approach is superior to the comparison methods.

The increasing availability of autonomous small-size Unmanned Aerial Vehicles (UAVs) has provided a promising way for data gathering from Wireless Sensor Networks (WSNs) with the advantages of high mobility, flexibility, and good speed. However, few works considered the situations that multiple UAVs are collaboratively used and the fine-grained trajectory plans of multiple UAVs are devised for collecting data from network including detailed traveling and hovering plans of them in the continuous space. In this paper, we investigate the problem of the Fine-grained Trajectory Plan for multi-UAVs (FTP), in which m UAVs are used to collect data from a given WSN, where m ≥ 1. The problem entails not only to find the flight paths of multiple UAVs but also to design the detailed hovering and traveling plans on their paths for efficient data gathering from WSN. The objective of the problem is to minimize the maximum flight time of UAVs such that all sensory data of WSN is collected by the UAVs and transported to the base station. We first propose a mathematical model of the FTP problem and prove that the problem is NP-hard. To solve the FTP problem, we first study a special case of the FTP problem when m = 1, called FTP with Single UAV (FTPS) problem. Then we propose a constant-factor approximation algorithm for the FTPS problem. Based on the FTPS problem, an approximation algorithm for the general version of the FTP problem when m > 1 is further proposed, which can guarantee a constant factor of the optimal solution. Afterwards, the proposed algorithms are verified by extensive simulations.

Following the recent advances in the Internet of Things (IoT), it is drawing lots of attention to design distributed algorithms for various network optimization problems under the SINR (Signal‐to‐Interference‐and‐Noise‐Ratio) interference model, such as spanner construction. Since a spanner can maintain a linear number of links while still preserving efficient routes for any pair of nodes in wireless networks, it is important to design distributed algorithms for spanners. Given a constant t > 1 as the required stretch factor, the problem of our concern is to design an efficient distributed algorithm to construct a t‐spanner of the communication graph under SINR such that the delay for the task completion is minimized, where the delay is the time interval between the time slot that the first node commences its operation to the time slot that all the nodes finish their task of constructing the t‐spanner. Our main contributions include four aspects. First, we propose a proximity range and proximity independent set (PISet) to increase the number of nodes transmitting successfully at the same time in order to reduce the delay. Second, we develop a distributed randomized algorithm SINR‐Spanner to construct a required t‐spanner with high probability. Third, the approximation ratio of SINR‐Spanner is proven to be a constant. Finally, extensive simulations are carried out to verify the effectiveness and efficiency of our proposed algorithm.

Inferring nodes' locations by inter-node measurements is a crucial problem in the IoT era. Despite the various approaches to this problem, obtaining accurate results is still challenging when the measurements are noisy, sparse, or uneven. Such unsatisfactory measurements are, however, inevitable for the general consideration of the deployment cost and the limited sensing scope.This paper proposes a Hierarchical Graph Optimization (HGO) framework to address the network localization problem when the measurements are sparse and noisy. It firstly efficiently extracts the dense sub-graphs and realizes their local structures in local coordinate systems. The local structures of dense components are rather accurate for the local sufficiency of the measurements. Then, the noises of the inter-edges that sparsely connect the dense sub-graphs are found as the main course of the network localization errors. A close-loop condition is derived and two denoising algorithms are proposed to set up linear equation arrays to correct the noises of these critical edges. After that, a projection algorithm is proposed to realize a smoothed backbone graph using the corrected critical edges, and finally, a hierarchical registration method is proposed to register the realized backbone and the dense sub-components to produce the global network structure. A parallel implementation is further developed, which speeds up HGO in large scale networks. Extensive simulations verify that HGO consistently outperforms existing network localization algorithms in terms of accuracy, efficiency, and reliability under various measurement settings.

As a promising technology to achieve perpetual operation of battery-powered wireless sensor devices, wireless power transfer has attracted much attention recently. In wireless power transfer, the charger enables the energy to be wirelessly transmitted to the rechargeable sensor devices that are hungry for energy. Previous works mainly focus on maximizing the charging utility or minimizing the charging delay. This paper concerns a more practical issue of placing wireless chargers, which aims at minimizing the deployment cost of chargers while satisfying the overall requirement for charging utility. We investigate the above cost-minimum charger placement problem under two typical scenarios in which omni chargers and directional chargers are used, respectively. To resolve this problem under the two charging models, we first prove its NP-hardness and then propose two approximation algorithms with proven performance guarantees. Finally, we conduct extensive simulation experiments to validate our designs, and the experimental results demonstrate that the proposed algorithms significantly outperform the baselines.

In recent years, social networks have become important platforms for people to disseminate information. However, we need to take effective measures such as blocking a set of links to control the negative rumors spreading over the network. In this article, we propose a Rumor Spread Minimization (RSM) problem, i.e., we remove an edge set from network such that the rumor spread is minimized. We first prove the objective function of RSM problem is not submodular. Then, we propose both submodular lower-bound and upper-bound of the objective function. Next, we develop a heuristic algorithm to approximate the objective function. Furthermore, we reformulate our objective function as the DS function (the Difference of Submodular functions). Finally, we conduct experiments on real-world datasets to evaluate our proposed method. The experiment results show that the upper and lower bounds are very close, which indicates the good quality of them. And, the proposed method outperforms the comparison methods.

One significant problem in exchange networks is finding the equilibrium. To solve this problem, the concept of stable outcome has been developed. However, there are few effective methods to solve it from the point of graph theory. In this paper, we propose a minimum cost stable outcome (MCSO) problem, which is to find a stable outcome whose total transaction cost is minimized. Two algorithms have been designed to solve this problem on unit and general profit networks respectively. For unit profit networks, we use minimum cost edge cover based method to give the optimal solution. For general profit networks, we develop an approximate algorithm and prove that performance ratio is no more than twice the optimal value. Moreover, we provide the probabilistic analysis. At last, extensive experiments have been conducted on synthetic and real-life datasets. Experimental results validate the performance of the proposed algorithms.

Accurate and robust localization is crucial for wireless ad-hoc and sensor networks. Among the localization techniques, component-based methods advance themselves for conquering network sparseness and anchor sparseness. But component-based methods are sensitive to ranging noises, which may cause a huge accumulated error either in component realization or merging process. This paper presents three results for robust component-based localization under ranging noises. (1) For a rigid graph component, a novel method is proposed to evaluate the graph's possible number of flip ambiguities under noises. In particular, graph's \emph{MInimal sepaRators that are neaRly cOllineaR (MIRROR) } is presented as the cause of flip ambiguity, and the number of MIRRORs indicates the possible number of flip ambiguities under noise. (2) Then the sensitivity of a graph's local deforming regarding ranging noises is investigated by perturbation analysis. A novel Ranging Sensitivity Matrix (RSM) is proposed to estimate the node location perturbations due to ranging noises. (3) By evaluating component robustness via the flipping and the local deforming risks, a Robust Component Generation and Realization (RCGR) algorithm is developed, which generates components based on the robustness metrics. RCGR was evaluated by simulations, which showed much better noise resistance and locating accuracy improvements than state-of-the-art of component-based localization algorithms.

A swarm of unmanned air vehicles (UAVs) may form a dynamic 3-D network whose topology changes frequently. Tracking the geometric formation of the network is a critical problem. Recent advantage of wireless ranging technologies (e.g., ultrawideband) enables inter-UAV distance measurement up to hundreds meters with errors in centimeter level. This makes it possible to track the network topology by the partially measured distance matrix among the UAVs, which is known as the formation tracking problem. But the measured distances are generally sparse and noisy, and the topology of UAV network is changing continuously. These cause the formation tracking highly challenging. Existing methods are generally fragile to the measurement noises and network sparsity. This paper exploits a fact that well-connected subcomponents, whose local structures can be calculated reliably, exist widely because the unevenness of node distribution in sparse networks. Therefore, a weighted component stitching (WCS) method to find the reliable components and stitch their local structures with weights is proposed for calculating the formation of the network accurately. In particular, we propose efficient two-center four-vertex-connected star-graph (2-4-star) detection and merging algorithms to extract the reliable global rigid components. A WCS algorithm and a weighted component-based Kalman filter algorithm with complexity both O(n3) are proposed for robust formation tracking in n vertex UAV networks. Extensive experiments were conducted, showing that the proposed methods can improve the formation tracking accuracy 21%-48% over existing state-of-the-art methods, especially in sparse, noisy UAV networks under different parameter settings.

Online multi-kernel learning is promising in the era of mobile computing, in which a combined classifier with multiple kernels are offline trained, and online adapts to personalized features for serving the end user precisely and smartly. The online adaptation is mainly carried out at the end-devices, which requires the adaptation algorithms to be light, efficient and accurate. Previous results focused mainly on efficiency. This paper proposes an novel online model adaptation framework for not only efficiency but also optimal online adaptation. At first, an online optimal incremental simplex tableau (IST)algorithm is proposed, which approaches the model adaption by linear programming and produces the optimized model update in each step when a personalized training data is collected.But keeping online optimal in each step is expensive and may cause over-fitting especially when the online data is noisy. A Fast-IST approach is therefore proposed, which measures the deviation between the training data and the current model. It schedules updating only when enough deviation is detected. The efficiency of each update is further enhanced by running IST only limited iterations, which bounds the computation complexity. Theoretical analysis and extensive evaluations show that Fast-IST saves computation cost greatly, while achieving speedy and accurate model adaptation.It provides better model adaptation speed and accuracy while using even lower computing cost than the state-of-the art.

Binary proximity sensors (BPS) is a generic model for many non- collaborative, presence detecting sensor. It outputs "1'' when one or more targets are presenting in its sensing range and "0" otherwise. It cannot tell the number of targets nor the targets' identities in its sensing range. But for its privacy protection and device-free properties, BPS-based tracking has attracted great attentions. However, multiple target counting and tracking (MTCT) by BPS network remains very challenging. Existing approaches generally rely on trajectory decomposition, which suffer association complexity issue and can hardly provide accurate results. To address these challenges, this paper presents an novel intensity-based counting and tracking approach, called IntenCT, which tracks the evolvement of the multi-targets' probabilistic density distribution overtime, without the complexity of enumerating the multiple targets' trajectories. Then, clustering algorithms on the density distribution are proposed to find the target groups, and count the targets in each group by calculating the integral of the density distribution in the group region. At last, the trajectories of the separable targets in each group are estimated using K-means and a motion consistency model. Extensive analysis and simulations show that IntenCT has quadratic complexity which is very efficient; provides the current best known multi-target counting lower bound; and tracks the multi-targets more accurately than the existing approaches.

Radio-map based method has been widely used for indoor location and navigation, but remaining key challenges are: 1) laborious efforts to calibrate a fine-grained radio-map, and 2) the locating result inaccuracy and not robust problems due to random signal strength (RSS) noises. An efficient way to overcome these problems is to collect RSS signatures along indoor paths and utilize sequence matching to enhance the location robustness. But, due to problems of indoor path combinational explosion, random RSS loss during movement, and moving speed disparity during online and offline phases, how to exploit sequence matching in radio-map remains difficult. This paper proposes WarpMap, an efficient sequence-type radio-map model and an accurate indoor location method by dynamic warping. Its distinct features include: 1) an undirected graph model (Trace-graph) for efficiently calibrating and storing sequence-type radio-map, which overcomes the path combinational explosion and RSS miss-of-detection problems; 2) an efficient sub-sequence dynamic time warping (SDTW) algorithm for accurate and efficient on-line locating. We show SDTW can tolerate random RSS disparities at discrete points and handle the moving speed differences in on-line and offline phases. The impacts of different warping distance functions, RSS preprocessing techniques were also investigated. Extensive experiments in office environments verified the efficiency and accuracy of WarpMap, which can calibrated within ten minutes by one person for 1100m2 area and provides overall nearly 20% accuracy improvements than the state-of-the-art of radio-map method.

In Hybrid networks, which synergistically mix together wired and wireless links to achieve flexible and reliable communication, it is particularly challenging to routing selfish tasks since each task wish to finish transmission as early as possible and its decision could have impacts on the others. In this paper, we investigate the problem to route a given set of selfish tasks in hybrid networks. Under a unified cost model, the competitive behaviors of selfish players are modeled as a noncooperative game. We show the game is ordinal potential, and the existence of a pure-Nash Equilibrium (pure-NE) is therefore guaranteed. We also design a routing scheme, called Selfish Task-Driven Routing (STaR), to achieve a pure-NE. Extensive simulations show that our scheme can not only efficiently converge to an equilibrium but also outperform other source routing protocols regarding the completion time and load balancing.

A basic problem in time of arrival (TOA)-based locating systems using narrow-band ultrasound (NBU) is how to improve the location update rate for tracking multiple targets. It is challenging because each ongoing ultrasound (US) signal occupies the channel for a rather long time because the slow propagation speed in air and it is hard to encode information in the narrow-band US. In this paper, we investigate to allow multiple NBU targets to transmit signals concurrently and to determine their locations by signal processing, which is called locating in chorus mode. The key observation is the signal interference characteristics of the concurrently chorusing targets. Based on it, the necessary and sufficient conditions for the receivers to determine the TOAs from multiple concurrently transmitting targets are investigated. However, because NBU cannot encode the target's ID, the detected TOAs are lacking labels of the target ID, causing ambiguities in location estimation. We exploited both historical consistence and self-consistence methods to narrow down the possible IDs of the TOAs and proposed probabilistic particle filter algorithm to disambiguate the motion trajectories of targets based on the targets' motion pattern consistency. A prototype of chorus-mode NBU locating system was developed. Extensive evaluations of both simulations and prototype experiments showed the effectiveness of the proposed theories and algorithms. In the testbed experiment, chorus locating provided 300% refreshing rate improvements compared with exclusive locating method, while the accuracy is still kept.

With the global trend of population aging in industrialized countries, efficient information and communication technologies (ICT) for aiding elders or patients' healthcare have attracted great research attentions. Among these technologies, health state sensing by wearable sensors and mobile phones is an important foundation. It monitors the real-time body states; stores, or sends the result to remote family members or doctors. In this way, it can either help people to pay more attention to the overlooked phenomenon, such as the clue of dangerous disease, or help people to issue panic alert when emergency happens. There are many critical issues in health sensing. First, the sensors must be non-intrusive to people's comfort and safety, while providing good accuracy. At the same time, because of being worn by people, numerous noises posed by body motions must be efficiently processed for reducing false alarming. At last, different health or decease signals generally require different sensing technologies and instrument. To tease out the technology advantages that address these challenges and diversities, this paper presented a survey on the state of the art of health sensing technologies using body sensor networks and mobile phones. It classify related works by their application goals, including i) fall detection, ii) gait analyzing, iii) activity qualification, iv) heart state sensing, and v) sleep sensing. It also conducts summary and comparison of related sensing systems and algorithms, to reveal the development lines in each subarea.

Locating individual congested links in large scale networks is an important but difficult problem, because of the hardness to directly measure the massive links. Current advantages of network tomography propose to infer the link congestion states by end-to-end measurements via solving a set of linear equations in Boolean algebra. But one challenging problem in such approaches is the requirement to construct n linearly independent measurements for uniquely identifying the states of n links. It is especially cost inefficient when the congested links are sparse, but requiring larger than n measurements to form a full-rank observation matrix. In this paper, we focus on efficient methods to take only limited number of path measurements to locate the sparsely congested links. To avoid the ambiguity of solving the boolean equations, at first, we propose a compressive sensing method to estimate the congestion probabilities of the individual links based on the deficient measurements (routing matrix is not full rank). Based on the congestion probability estimation, a greedy iterative estimation algorithm is developed to locate the congested links by online snapshot of the deficient measurements. Extensive simulations shows the effectiveness of proposed methods which reduce the measurement costs while preserving the detection accuracy.

Compressive sensing over graphs has recently attracted great research attentions, which takes limited number end-to-end measurements along paths (walks) to recover sparse vectors representing link/node properties. Unlike traditional compressive sensing, the along-path measurements rule out the freedom of random sampling, which introduces path constraints to the measurement matrix. The constraint makes explicit analysis of recovery performance difficult Only for undirected graphs, early results showed that O(klog(n)) end-to-end measurements taken by random walks are sufficient to recover k-sparse edge vector. However, the problem becomes more difficult when directed graphs are considered, because of the easy state absorbing and the difficulty of evaluating the stationary distribution. But digraphs inherently model many network systems. In this paper, particularly for strongly connected digraphs with low node degrees, we presents bounds for the stationary distribution of random walks, and present deliberative proofs which put forward that O(klog(n)) path measurements are sufficient to recover k-sparse edge vectors. Further more, because urban road networks are exactly strongly connected, low degree digraphs, we designed efficient recovery methods to estimate road delays by a small number of probing cars. Although the road delay vector is actually not sparse, we leverage the empirical non-congested road delays as references and develop an algorithm which divide the problem to iteratively recover several k-sparse vectors. Simulation results show that when less than 10% edges are congested, more than 90% congestion states can be recovered correctly by 10% measurements.

Binary proximity sensors (BPS) provide extremely low cost and privacy preserving features for tracking mobile targets in smart environment, but great challenges are posed for track- ing multiple targets, because a BPS cannot distinguish one or multiple targets are in its sensing range. In this paper, we at first address the counting problem by presenting a maxi- mum clique partition model on unit disk graph, which leads to a tight lower bound for estimating the number of targets by a snapshot of sensor readings. Then, to more accurately count and track the multiple targets by sequential readings of sensors, we state the key is to comprehensively infer the states behind the events. Therefore, at each event we infer which target may trigger the event via a dynamic coloring technique (DEC) and predict the potential regions of the multiple targets by a colorful area shrinking and expanding approach. Such an approach generates multiple potential scenarios containing different colors to interpret the sequen- tial events, where the number of colors indicates the different estimations of the target number. Then we designed multi- color particle filter (MCPF), which is run in parallel in each scenario to enumerate and evaluate the potential trajecto- ries of the targets under the color constraint. The likelihoods of the trajectories are evaluated by each target's movement consistence. The overall best trajectory over all scenarios is voted to provide not only the most possible target number, but also the trajectories of the targets. Extensive simula- tions were conducted using a multi-agent simulator which show good accuracy of the proposed multi-target tracking algorithms.

Ranging by Time of Arrival (TOA) of Narrowband ultrasound (NBU) has been widely used by many locating systems for its characteristics of low cost and high accuracy. However, because it is hard to support code division multiple access in narrowband signal, to track multiple targets, existing NBU-based locating systems generally need to assign exclusive time slot to each target to avoid the signal conflicts. Because the propagation speed of ultrasound is slow in air, dividing exclusive time slots on a single channel causes the location updating rate for each target rather low, leading to unsatisfied tracking performances as the number of targets increases. In this paper, we investigated a new multiple target locating method using NBU, called UltraChorus, which is to locate multiple targets while allowing them sending NBU signals simultaneously, i.e., in chorus mode. It can dramatically increase the location updating rate. In particular, we investigated by both experiments and theoretical analysis on the necessary and sufficient conditions for resolving the conflicts of multiple NBU signals on a single channel, which is referred as the conditions for chorus ranging and chorus locating. To tackle the difficulty caused by the anonymity of the measured distances, we further developed consistent position generation algorithm and probabilistic particle filter algorithm to label the distances by sources, to generate reasonable location estimations, and to disambiguate the motion trajectories of the multiple concurrent targets based on the anonymous distance measurements. Extensive evaluations by both simulation and testbed were carried out, which verified the effectiveness of our proposed theories and algorithms.

This article presents a framework for deploying a minimal number of smart meters to accurately track the ON/OFF states of a massive number of electrical appliances which exploits the sparseness feature of simultaneous ON/OFF switching events of the massive appliances. A theoretical bound on the least number of required smart meters is studied by an entropy-based approach, which qualifies the impact of meter deployment strategies to the state tracking accuracy. It motivates a meter deployment optimization algorithm (MDOP) to minimize the number of meters while satisfying given requirements to state tracking accuracy. To accurately decode the real-time ON/OFF states of appliances by the readings of meters, a fast state decoding (FSD) algorithm based on the hidden Markov model (HMM) is presented to track the state sequence of each appliance for better accuracy. Although traditional HMM needs O ( t 2 2 N ) time complexity to conduct online sequence decoding, FSD improves the complexity to O ( tn U+1 ), where n < N and U is an upper bound of the simultaneous switching events. Both MDOP and FSD are verified extensively using simulations and real PowerNet data. The results show that the meter deployment cost can be saved by more than 80% while still getting over 90% state tracking accuracy.

For large-scale sensor networks deployed for data gathering, energy efficiency is critical. Eliminating the data correlation is a promising technique for energy efficiency. Compressive Data Gathering (CDG) [8], which employs distributed coding to compress data correlation, is an important approach in this area. However, the CDG scheme uses a uniform pattern in data transmission, where all nodes transmit the same amount of data regardless of their hop distances to the sink, making it inefficient in saving transmission costs in 2-D networks. In this paper, the Major Coefficient Recovery (MCR) scheme is proposed, where the Discrete Cosine Transformation (DCT) is applied in a distributed fashion to the original sensed data. A non-uniform data transmission pattern is proposed by exploiting the energy concentration property of DCT and QR decomposition techniques so that sensors with larger hop-count can transmit fewer messages for network energy efficiency. The sink node recovers only the major coefficients of the DCT to reconstruct the original data accurately. MCR reduces the transmission overhead to O(kn - k2), an improvement by O(logn) over CDG in both 1-D and 2-D cases. The recovery performance of MCR is verified by extensive simulations.

In order to realize precision agriculture information monitoringover long periods of time and over large areas of space, we propose OPAIMS, an open-architecture precision agriculture information monitoring system. OPAIMS consists of a two-tiered sensor network and an information service platform. The sensor network contains a large amount of energy-limited low tier nodes (LNs) to capture and report information of their designated vicinity, and some powerful GPRS gateways in the high tier to organize the LNs to form clusters and to report the aggregated information to the Internet. The information service platform logs information from the sensor network and provide value-created services to the users. In this paper, we focus on the design methodologies of OPAIMS, including the system architecture, the standard interfaces and the multi-hop joint scheduling of LNs. Such designs make OPAIMS not only scalable and longevous, but also universal for various kinds of sensors and hardware. Users can easily establish a precision agriculture monitoring system based on the proposed OPAIMS.

This paper proposes the autonomous ultrasonic indoor tracking system (AUITS), an ultrasound based system for locating and tracking mobile objects inside a building. Ultrasound shows promise to be exploited for a practical indoor location system due to its high accuracy ranging, low cost, safety, and imperceptibility. However, conventional ultrasonic location systems pose such challenges as high installation cost and manual calibration. The key idea of AUITS is to use only one autonomous device, positioning on one device (POD), to not only process signal acquisition but also conduct position computation. Structural topology is designed to make POD easily deployed and easily calibrated. In addition, a structural localization algorithm is proposed to provide an effective and affordable algorithm for POD to calculate the object's position. We describe the of AUITS and evaluate its performance both experimentally and with simulation. The results show that the coverage area of a POD can reach 65 m2and the positioning error is less than 15 cm with over 90% probability.

Cluster-based self-organization scheme is attracting tremendous research interest in the studies of the wireless sensor networks (WSN), because it meets the critical runtime requirement of the WSN based applications: working in self-organized and energy efficient way. Whereas, an important problem in the cluster scheme remains seldom studied, that the cluster heads depletes energy very fast and the rotation strategy of the cluster head is needed to prolong the system's lifetime. In this paper, the cluster head rotation problem is studied with the dynamic programming method. An energy first cluster head rotation strategy is proposed and is proved to be the optimal in the means of the cluster lifetime. Further, the upper bound and the lower bound of the cluster lifetime are derived based on the law of conservation of energy. We show that the optimal strategy is not unique, which can be accomplished in different ways. Based on the analysis, a practical, LEast-rotation, near-optimal cluster head rotation algorithm (LENO) is proposed to practice the inner cluster rotation. The validity of LENO is verified with the node level simulation tool PowerTOSSIM. Near optimal cluster lifetime is obtained as desired, which is much better than the performances of Leach and EDAC etc.