1
|
Moragrega A, Fernández-Prades C. A Data-Driven Factor Graph Model for Anchor-Based Positioning. Sensors (Basel) 2023; 23:5660. [PMID: 37420826 DOI: 10.3390/s23125660] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/27/2023] [Revised: 06/12/2023] [Accepted: 06/13/2023] [Indexed: 07/09/2023]
Abstract
This work presents a data-driven factor graph (FG) model designed to perform anchor-based positioning. The system makes use of the FG to compute the target position, given the distance measurements to the anchor node that know its own position.The aim was to design a hybrid structure (that involves data and modeling approaches) to address positioning models from a Bayesian point of view, customizing them for each technology and scenario. The weighted geometric dilution of precision (WGDOP) metric, which measures the effect on the positioning solution of distance error to the corresponding anchor node and network geometry of the anchor nodes, was taken into account. The presented algorithms were tested with simulated data and also with real-life data collected from IEEE 802.15.4-compliant sensor network nodes with a physical layer based on ultra-wide band (UWB) technology, in scenarios with one target node, three and four anchor nodes, and a time-of-arrival-based range technique. The results showed that the presented algorithm based on the FG technique provided better positioning results than the least squares-based algorithms and even UWB-based commercial systems in various scenarios, with different setups in terms of geometries and propagation conditions.
Collapse
Affiliation(s)
- Ana Moragrega
- Centre Tecnològic de Telecomunicacions de Catalunya (CTTC/CERCA), 08860 Castelldefels, Barcelona, Spain
| | - Carles Fernández-Prades
- Centre Tecnològic de Telecomunicacions de Catalunya (CTTC/CERCA), 08860 Castelldefels, Barcelona, Spain
| |
Collapse
|
2
|
Chen Q, Ren Y, Zhou L, Chen C, Liu S. Design and Analysis of Joint Group Shuffled Scheduling Decoding Algorithm for Double LDPC Codes System. Entropy (Basel) 2023; 25:357. [PMID: 36832723 PMCID: PMC9954909 DOI: 10.3390/e25020357] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 01/18/2023] [Revised: 02/14/2023] [Accepted: 02/14/2023] [Indexed: 06/18/2023]
Abstract
In this paper, a joint group shuffled scheduling decoding (JGSSD) algorithm for a joint source-channel coding (JSCC) scheme based on double low-density parity-check (D-LDPC) codes is presented. The proposed algorithm considers the D-LDPC coding structure as a whole and applies shuffled scheduling to each group; the grouping relies on the types or the length of the variable nodes (VNs). By comparison, the conventional shuffled scheduling decoding algorithm can be regarded as a special case of this proposed algorithm. A novel joint extrinsic information transfer (JEXIT) algorithm for the D-LDPC codes system with the JGSSD algorithm is proposed, by which the source and channel decoding are calculated with different grouping strategies to analyze the effects of the grouping strategy. Simulation results and comparisons verify the superiority of the JGSSD algorithm, which can adaptively trade off the decoding performance, complexity and latency.
Collapse
|
3
|
Baker A, Biazzo I, Braunstein A, Catania G, Dall'Asta L, Ingrosso A, Krzakala F, Mazza F, Mézard M, Muntoni AP, Refinetti M, Sarao Mannelli S, Zdeborová L. Epidemic mitigation by statistical inference from contact tracing data. Proc Natl Acad Sci U S A 2021; 118:e2106548118. [PMID: 34312253 DOI: 10.1073/pnas.2106548118] [Citation(s) in RCA: 9] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [What about the content of this article? (0)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/29/2022] Open
Abstract
Contact tracing mobile applications are clear candidates for enabling us to slow down an epidemic and keep society running while holding the health risks down. Currently used mobile applications aim to notify individuals who were recently in significant contact with an individual who tested COVID-19 positive. In our work, we aim to quantify the epidemiological gain one would obtain if, additionally, individuals who were recently in contact could exchange messages of information. With such a message-passing addition, the risk of contracting COVID-19 could be estimated with much better accuracy than simple contact tracing. We conclude that probabilistic risk estimation is capable of enhancing performance of digital contact tracing and should be considered in the mobile tracing applications. Contact tracing is an essential tool to mitigate the impact of a pandemic, such as the COVID-19 pandemic. In order to achieve efficient and scalable contact tracing in real time, digital devices can play an important role. While a lot of attention has been paid to analyzing the privacy and ethical risks of the associated mobile applications, so far much less research has been devoted to optimizing their performance and assessing their impact on the mitigation of the epidemic. We develop Bayesian inference methods to estimate the risk that an individual is infected. This inference is based on the list of his recent contacts and their own risk levels, as well as personal information such as results of tests or presence of syndromes. We propose to use probabilistic risk estimation to optimize testing and quarantining strategies for the control of an epidemic. Our results show that in some range of epidemic spreading (typically when the manual tracing of all contacts of infected people becomes practically impossible but before the fraction of infected people reaches the scale where a lockdown becomes unavoidable), this inference of individuals at risk could be an efficient way to mitigate the epidemic. Our approaches translate into fully distributed algorithms that only require communication between individuals who have recently been in contact. Such communication may be encrypted and anonymized, and thus, it is compatible with privacy-preserving standards. We conclude that probabilistic risk estimation is capable of enhancing the performance of digital contact tracing and should be considered in the mobile applications.
Collapse
|
4
|
Park S. Scheduled QR-BP Detector with Interference Cancellation and Candidate Constraints for MIMO Systems. Sensors (Basel) 2021; 21:3734. [PMID: 34072075 DOI: 10.3390/s21113734] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 05/05/2021] [Revised: 05/24/2021] [Accepted: 05/26/2021] [Indexed: 11/29/2022]
Abstract
In this paper, a QR-decomposition-based scheduled belief propagation (BP) detector with interference cancellation (IC) and candidate constraints is proposed for multiple-input multiple-output (MIMO) systems. Based on a bipartite graph generated from an upper triangular channel matrix following linear transformation using QR decomposition, the proposed detector performs a sequential message updating procedure between bit nodes. During this updating procedure, candidate constraints are imposed to restrict the number of possible candidate vectors for the calculation of observation-to-bit messages. In addition, after obtaining the soft message corresponding to the bit sequence in each transmit symbol, a hard-decision IC operation is performed to reduce the size of the bipartite graph and indirectly update the messages for the remaining symbols. Therefore, the proposed scheme provides a huge complexity reduction compared to conventional BP detectors that perform message updating by using all related messages directly. Simulation results confirm that the proposed detector can achieve suboptimum error performance with significantly improved convergence speed and reduced computational complexity compared to conventional BP detectors in MIMO systems.
Collapse
|
5
|
Hayashi Y, Tanaka A, Matsukubo J. More Tolerant Reconstructed Networks Using Self-Healing against Attacks in Saving Resource. Entropy (Basel) 2021; 23:E102. [PMID: 33445680 DOI: 10.3390/e23010102] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [What about the content of this article? (0)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 12/03/2020] [Revised: 01/07/2021] [Accepted: 01/07/2021] [Indexed: 11/17/2022]
Abstract
Complex network infrastructure systems for power supply, communication, and transportation support our economic and social activities; however, they are extremely vulnerable to frequently increasing large disasters or attacks. Thus, the reconstruction of a damaged network is more advisable than an empirically performed recovery of the original vulnerable one. To reconstruct a sustainable network, we focus on enhancing loops so that they are not trees, which is made possible by node removal. Although this optimization corresponds with an intractable combinatorial problem, we propose self-healing methods based on enhancing loops when applying an approximate calculation inspired by statistical physics. We show that both higher robustness and efficiency are obtained in our proposed methods by saving the resources of links and ports when compared to ones in conventional healing methods. Moreover, the reconstructed network can become more tolerant than the original when some damaged links are reusable or compensated for as an investment of resource. These results present the potential of network reconstruction using self-healing with adaptive capacity in terms of resilience.
Collapse
|
6
|
Yang W, Li Y. An Irregular Graph Based Network Code for Low-Latency Content Distribution. Sensors (Basel) 2020; 20:E4334. [PMID: 32759656 DOI: 10.3390/s20154334] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [What about the content of this article? (0)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 07/16/2020] [Revised: 07/25/2020] [Accepted: 08/03/2020] [Indexed: 11/23/2022]
Abstract
To fulfill the increasing demand on low-latency content distribution, this paper considers content distribution using generation-based network coding with the belief propagation decoder. We propose a framework to design generation-based network codes via characterizing them as building an irregular graph, and design the code by evaluating the graph. The and-or tree evaluation technique is extended to analyze the decoding performance. By allowing for non-constant generation sizes, we formulate optimization problems based on the analysis to design degree distributions from which generation sizes are drawn. Extensive simulation results show that the design may achieve both low decoding cost and transmission overhead as compared to existing schemes using constant generation sizes, and satisfactory decoding speed can be achieved. The scheme would be of interest to scenarios where (1) the network topology is not known, dynamically changing, and/or has cycles due to cooperation between end users, and (2) computational/memory costs of nodes are of concern but network transmission rate is spare.
Collapse
|
7
|
Masoum A, Meratnia N, Havinga PJM. Coalition Formation Based Compressive Sensing in Wireless Sensor Networks. Sensors (Basel) 2018; 18:E2331. [PMID: 30021980 DOI: 10.3390/s18072331] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [What about the content of this article? (0)] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 05/13/2018] [Revised: 07/08/2018] [Accepted: 07/13/2018] [Indexed: 11/17/2022]
Abstract
Compressive sensing originates in the field of signal processing and has recently become a topic of energy-efficient data gathering in wireless sensor networks. In this paper, we propose an energy efficient distributed compressive sensing solution for sensor networks. The proposed solution utilizes sparsity distribution of signals to group sensor nodes into several coalitions and then implements localized compressive sensing inside coalitions. This solution improves data-gathering performance in terms of both data accuracy and energy consumption. The approach curbs both data-transmission costs and number of measurements. Coalition-based data gathering cuts transmission costs, and the number of measurements is reduced by scheduling sensor nodes and adjusting their sampling frequency. Our simulation showed that our approach enhances network performance by minimizing energy cost and improving data accuracy.
Collapse
|
8
|
Abstract
Active inference is a corollary of the Free Energy Principle that prescribes how self-organizing biological agents interact with their environment. The study of active inference processes relies on the definition of a generative probabilistic model and a description of how a free energy functional is minimized by neuronal message passing under that model. This paper presents a tutorial introduction to specifying active inference processes by Forney-style factor graphs (FFG). The FFG framework provides both an insightful representation of the probabilistic model and a biologically plausible inference scheme that, in principle, can be automatically executed in a computer simulation. As an illustrative example, we present an FFG for a deep temporal active inference process. The graph clearly shows how policy selection by expected free energy minimization results from free energy minimization per se, in an appropriate generative policy model.
Collapse
Affiliation(s)
- Bert de Vries
- Department of Electrical Engineering, Eindhoven University of Technology, Eindhoven, Netherlands
- GN Hearing Benelux BV, Eindhoven, Netherlands
| | - Karl J. Friston
- Wellcome Trust Centre for Neuroimaging, Institute of Neurology, University College London, London, United Kingdom
| |
Collapse
|
9
|
Abstract
Compared to standard frame-based cameras, biologically-inspired event-based sensors capture visual information with low latency and minimal redundancy. These event-based sensors are also far less prone to motion blur than traditional cameras, and still operate effectively in high dynamic range scenes. However, classical framed-based algorithms are not typically suitable for these event-based data and new processing algorithms are required. This paper focuses on the problem of depth estimation from a stereo pair of event-based sensors. A fully event-based stereo depth estimation algorithm which relies on message passing is proposed. The algorithm not only considers the properties of a single event but also uses a Markov Random Field (MRF) to consider the constraints between the nearby events, such as disparity uniqueness and depth continuity. The method is tested on five different scenes and compared to other state-of-art event-based stereo matching methods. The results show that the method detects more stereo matches than other methods, with each match having a higher accuracy. The method can operate in an event-driven manner where depths are reported for individual events as they are received, or the network can be queried at any time to generate a sparse depth frame which represents the current state of the network.
Collapse
Affiliation(s)
- Zhen Xie
- College of Computer Science, Zhejiang University of Technology, Hangzhou, China.,Temasek Laboratories, National University of Singapore, Singapore, Singapore
| | - Shengyong Chen
- College of Computer Science, Zhejiang University of Technology, Hangzhou, China
| | - Garrick Orchard
- Temasek Laboratories, National University of Singapore, Singapore, Singapore.,Singapore Institute for Neurotechnology (SINAPSE), National University of Singapore, Singapore, Singapore
| |
Collapse
|
10
|
Massucci FA, Wheeler J, Beltrán-Debón R, Joven J, Sales-Pardo M, Guimerà R. Inferring propagation paths for sparsely observed perturbations on complex networks. Sci Adv 2016; 2:e1501638. [PMID: 27819038 PMCID: PMC5088640 DOI: 10.1126/sciadv.1501638] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 11/13/2015] [Accepted: 09/22/2016] [Indexed: 06/06/2023]
Abstract
In a complex system, perturbations propagate by following paths on the network of interactions among the system's units. In contrast to what happens with the spreading of epidemics, observations of general perturbations are often very sparse in time (there is a single observation of the perturbed system) and in "space" (only a few perturbed and unperturbed units are observed). A major challenge in many areas, from biology to the social sciences, is to infer the propagation paths from observations of the effects of perturbation under these sparsity conditions. We address this problem and show that it is possible to go beyond the usual approach of using the shortest paths connecting the known perturbed nodes. Specifically, we show that a simple and general probabilistic model, which we solved using belief propagation, provides fast and accurate estimates of the probabilities of nodes being perturbed.
Collapse
Affiliation(s)
| | - Jonathan Wheeler
- Departament d’Enginyeria Química, Universitat Rovira i Virgili, Tarragona 43007, Catalonia, Spain
| | - Raúl Beltrán-Debón
- Cheminformatics and Nutrition Research Group, Department of Biochemistry and Biotechnology, Universitat Rovira i Virgili, Tarragona 43007, Spain
| | - Jorge Joven
- Unitat de Recerca Biomèdica, Hospital Universitari de Sant Joan, Institut d’Investigació Sanitària Pere Virgili, Universitat Rovira i Virgili, Reus, Catalonia, Spain
| | - Marta Sales-Pardo
- Departament d’Enginyeria Química, Universitat Rovira i Virgili, Tarragona 43007, Catalonia, Spain
| | - Roger Guimerà
- Departament d’Enginyeria Química, Universitat Rovira i Virgili, Tarragona 43007, Catalonia, Spain
- Institució Catalana de Recerca i Estudis Avançats (ICREA), Barcelona 08010, Catalonia, Spain
| |
Collapse
|
11
|
Bilgel M, Roy S, Carass A, Nyquist PA, Prince JL. AUTOMATED ANATOMICAL LABELING OF THE CEREBRAL ARTERIES USING BELIEF PROPAGATION. Proc SPIE Int Soc Opt Eng 2013; 866918. [PMID: 24236229 DOI: 10.1117/12.2006460] [Citation(s) in RCA: 9] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/14/2022]
Abstract
Labeling of cerebral vasculature is important for characterization of anatomical variation, quantification of brain morphology with respect to specific vessels, and inter-subject comparisons of vessel properties and abnormalities. We propose an automated method to label the anterior portion of cerebral arteries using a statistical inference method on the Bayesian network representation of the vessel tree. Our approach combines the likelihoods obtained from a random forest classifier trained using vessel centerline features with a belief propagation method integrating the connection probabilities of the cerebral artery network. We evaluate our method on 30 subjects using a leave-one-out validation, and show that it achieves an average correct vessel labeling rate of over 92%.
Collapse
Affiliation(s)
- Murat Bilgel
- Biomedical Engineering, The Johns Hopkins University School of Medicine, Baltimore, MD, USA
| | | | | | | | | |
Collapse
|
12
|
Li J, Shi W, Deng D, Jia W, Sun M. Bayesian Stereo Matching Method Based on Edge Constraints. Int J Adv Comput Technol 2012; 4:36-47. [PMID: 25309710 PMCID: PMC4192720 DOI: 10.4156/ijact.vol4.issue22.5] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/04/2023]
Abstract
A new global stereo matching method is presented that focuses on the handling of disparity, discontinuity and occlusion. The Bayesian approach is utilized for dense stereo matching problem formulated as a maximum a posteriori Markov Random Field (MAP-MRF) problem. In order to improve stereo matching performance, edges are incorporated into the Bayesian model as a soft constraint. Accelerated belief propagation is applied to obtain the maximum a posteriori estimates in the Markov random field. The proposed algorithm is evaluated using the Middlebury stereo benchmark. Our experimental results comparing with some state-of-the-art stereo matching methods demonstrate that the proposed method provides superior disparity maps with a subpixel precision.
Collapse
Affiliation(s)
- Jie Li
- School of Electronic Information, Wuhan University, China
| | - Wenxuan Shi
- School of Electronic Information, Wuhan University, China
| | - Dexiang Deng
- School of Electronic Information, Wuhan University, China
| | - Wenyan Jia
- Department of Neurosurgery, University of Pittsburgh, USA
| | - Mingui Sun
- Departments of Neurosurgery, Electrical engineering and Bioengineering, University of Pittsburgh, USA
| |
Collapse
|
13
|
Weinman JJ, Learned-Miller E, Hanson AR. Scene text recognition using similarity and a lexicon with sparse belief propagation. IEEE Trans Pattern Anal Mach Intell 2009; 31:1733-46. [PMID: 19696446 PMCID: PMC3021989 DOI: 10.1109/tpami.2009.38] [Citation(s) in RCA: 20] [Impact Index Per Article: 1.3] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/28/2023]
Abstract
Scene text recognition (STR) is the recognition of text anywhere in the environment, such as signs and storefronts. Relative to document recognition, it is challenging because of font variability, minimal language context, and uncontrolled conditions. Much information available to solve this problem is frequently ignored or used sequentially. Similarity between character images is often overlooked as useful information. Because of language priors, a recognizer may assign different labels to identical characters. Directly comparing characters to each other, rather than only a model, helps ensure that similar instances receive the same label. Lexicons improve recognition accuracy but are used post hoc. We introduce a probabilistic model for STR that integrates similarity, language properties, and lexical decision. Inference is accelerated with sparse belief propagation, a bottom-up method for shortening messages by reducing the dependency between weakly supported hypotheses. By fusing information sources in one model, we eliminate unrecoverable errors that result from sequential processing, improving accuracy. In experimental results recognizing text from images of signs in outdoor scenes, incorporating similarity reduces character recognition error by 19 percent, the lexicon reduces word recognition error by 35 percent, and sparse belief propagation reduces the lexicon words considered by 99.9 percent with a 12X speedup and no loss in accuracy.
Collapse
Affiliation(s)
| | | | - Allen R. Hanson
- Department of Computer Science at the University of Massachusetts Amherst
| |
Collapse
|
14
|
Abstract
Foreground-background segmentation has recently been applied [26,12] to the detection and segmentation of specific objects or structures of interest from the background as an efficient alternative to techniques such as deformable templates [27]. We introduce a graphical model (i.e. Markov random field)-based formulation of structure-specific figure-ground segmentation based on simple geometric features extracted from an image, such as local configurations of linear features, that are characteristic of the desired figure structure. Our formulation is novel in that it is based on factor graphs, which are graphical models that encode interactions among arbitrary numbers of random variables. The ability of factor graphs to express interactions higher than pairwise order (the highest order encountered in most graphical models used in computer vision) is useful for modeling a variety of pattern recognition problems. In particular, we show how this property makes factor graphs a natural framework for performing grouping and segmentation, and demonstrate that the factor graph framework emerges naturally from a simple maximum entropy model of figure-ground segmentation.We cast our approach in a learning framework, in which the contributions of multiple grouping cues are learned from training data, and apply our framework to the problem of finding printed text in natural scenes. Experimental results are described, including a performance analysis that demonstrates the feasibility of the approach.
Collapse
Affiliation(s)
- Huiying Shen
- Smith-Kettlewell Eye Research Institute, San Francisco, CA 94115, USA
| | | | | |
Collapse
|