Nothing Special   »   [go: up one dir, main page]
Next Issue
Volume 11, September
Previous Issue
Volume 11, July
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
4.1
1.8
Journals
Algorithms
Volume 11
Issue 8
share announcement

Algorithms, Volume 11, Issue 8 (August 2018) – 20 articles

  • Issues are regarded as officially published after their release is announced to the table of contents alert mailing list.
  • You may sign up for e-mail alerts to receive table of contents of newly released issues.
  • PDF is the official format for papers published in both, html and pdf forms. To view the papers in pdf format, click on the "PDF Full-text" link, and use the free Adobe Reader to open them.
Order results
Result details
Section
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
23 pages, 508 KiB  
Article
DenseZDD: A Compact and Fast Index for Families of Sets †
by Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, Shin-ichi Minato and Kunihiko Sadakane
Algorithms 2018, 11(8), 128; https://doi.org/10.3390/a11080128 - 17 Aug 2018
Cited by 3 | Viewed by 4854
Abstract
In this article, we propose a succinct data structure of zero-suppressed binary decision diagrams (ZDDs). A ZDD represents sets of combinations efficiently and we can perform various set operations on the ZDD without explicitly extracting combinations. Thanks to these features, ZDDs have been [...] Read more.
In this article, we propose a succinct data structure of zero-suppressed binary decision diagrams (ZDDs). A ZDD represents sets of combinations efficiently and we can perform various set operations on the ZDD without explicitly extracting combinations. Thanks to these features, ZDDs have been applied to web information retrieval, information integration, and data mining. However, to support rich manipulation of sets of combinations and update ZDDs in the future, ZDDs need too much space, which means that there is still room to be compressed. The paper introduces a new succinct data structure, called DenseZDD, for further compressing a ZDD when we do not need to conduct set operations on the ZDD but want to examine whether a given set is included in the family represented by the ZDD, and count the number of elements in the family. We also propose a hybrid method, which combines DenseZDDs with ordinary ZDDs. By numerical experiments, we show that the sizes of our data structures are three times smaller than those of ordinary ZDDs, and membership operations and random sampling on DenseZDDs are about ten times and three times faster than those on ordinary ZDDs for some datasets, respectively. Full article
(This article belongs to the Special Issue Efficient Data Structures)
►▼ Show Figures

Figure 1

Figure 1
<p>Example of ZDD.</p> Full article ">Figure 2
<p>Reduction rules of ZDDs.</p> Full article ">Figure 3
<p>ZDD using 0-element edges that is equivalent to the ZDD in <a href="#algorithms-11-00128-f001" class="html-fig">Figure 1</a>.</p> Full article ">Figure 4
<p>Worst-case example of a straightforward translation.</p> Full article ">Figure 5
<p>Example of the construction of the zero-edge tree from a ZDD by inserting dummy nodes and adding/deleting edges. A black and white circle represents a dummy and real node, respectively. The number in a circle represents its index. A dotted arrow in the left figure represents a 0-edge.</p> Full article ">Figure 6
<p>Zero-edge tree and a dummy node vector obtained from the ZDD in <a href="#algorithms-11-00128-f003" class="html-fig">Figure 3</a>.</p> Full article ">Figure 7
<p>One-child array obtained from the ZDD in <a href="#algorithms-11-00128-f003" class="html-fig">Figure 3</a>.</p> Full article ">Figure 8
<p>Computing real preorder ranks from the 0-terminal node to real nodes with higher indices.</p> Full article ">
15 pages, 1365 KiB  
Article
Application of Angle Related Cost Function Optimization for Dynamic Path Planning Algorithm
by Mingbin Zeng, Xu Yang, Mengxing Wang and Bangjiang Xu
Algorithms 2018, 11(8), 127; https://doi.org/10.3390/a11080127 - 15 Aug 2018
Cited by 4 | Viewed by 4019
Abstract
In recent years, Intelligent Transportation Systems (ITS) have developed a lot. More and more sensors and communication technologies (e.g., cloud computing) are being integrated into cars, which opens up a new design space for vehicular-based applications. In this paper, we present the Spatial [...] Read more.
In recent years, Intelligent Transportation Systems (ITS) have developed a lot. More and more sensors and communication technologies (e.g., cloud computing) are being integrated into cars, which opens up a new design space for vehicular-based applications. In this paper, we present the Spatial Optimized Dynamic Path Planning algorithm. Our contributions are, firstly, to enhance the effective of loading mechanism for road maps by dividing the connected sub-net, and building a spatial index; and secondly, to enhance the effect of the dynamic path planning by optimizing the search direction. We use the real road network and real-time traffic flow data of Karamay city to simulate the effect of our algorithm. Experiments show that our Spatial Optimized Dynamic Path Planning algorithm can significantly reduce the time complexity, and is better suited for use as a real-time navigation system. The algorithm can achieve superior real-time performance and obtain the optimal solution in dynamic path planning. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Search space of the Dijkstra algorithm.</p> Full article ">Figure 2
<p>Search space of the ant colony algorithm.</p> Full article ">Figure 3
<p>Search space of the A* algorithm.</p> Full article ">Figure 4
<p>Illustration of the A* evaluation function.</p> Full article ">Figure 5
<p>The influence of the search direction on the evaluation function.</p> Full article ">Figure 6
<p>Cosine theorem.</p> Full article ">Figure 7
<p><math display="inline"><semantics> <mrow> <mo>−</mo> <mi>cos</mi> <mo>(</mo> <mi>α</mi> <mo>)</mo> </mrow> </semantics></math>.</p> Full article ">Figure 8
<p>Image for <math display="inline"><semantics> <mrow> <msub> <mi>h</mi> <mi>r</mi> </msub> <mrow> <mo>(</mo> <mi>i</mi> <mo>)</mo> </mrow> </mrow> </semantics></math>.</p> Full article ">Figure 9
<p>Interface for SUMO.</p> Full article ">Figure 10
<p>Karamay city.</p> Full article ">Figure 11
<p>Path search result under normal situation.</p> Full article ">Figure 12
<p>Path search result under congestion situation.</p> Full article ">
18 pages, 4866 KiB  
Article
Robust Visual Tracking via Patch Descriptor and Structural Local Sparse Representation
by Zhiguo Song, Jifeng Sun, Jialin Yu and Shengqing Liu
Algorithms 2018, 11(8), 126; https://doi.org/10.3390/a11080126 - 15 Aug 2018
Viewed by 3278
Abstract
Appearance models play an important role in visual tracking. Effective modeling of the appearance of tracked objects is still a challenging problem because of object appearance changes caused by factors, such as partial occlusion, illumination variation and deformation, etc. In this paper, we [...] Read more.
Appearance models play an important role in visual tracking. Effective modeling of the appearance of tracked objects is still a challenging problem because of object appearance changes caused by factors, such as partial occlusion, illumination variation and deformation, etc. In this paper, we propose a tracking method based on the patch descriptor and the structural local sparse representation. In our method, the object is firstly divided into multiple non-overlapped patches, and the patch sparse coefficients are obtained by structural local sparse representation. Secondly, each patch is further decomposed into several sub-patches. The patch descriptors are defined as the proportion of sub-patches, of which the reconstruction error is less than the given threshold. Finally, the appearance of an object is modeled by the patch descriptors and the patch sparse coefficients. Furthermore, in order to adapt to appearance changes of an object and alleviate the model drift, an outlier-aware template update scheme is introduced. Experimental results on a large benchmark dataset demonstrate the effectiveness of the proposed method. Full article
►▼ Show Figures

Graphical abstract

Graphical abstract
Full article ">Figure 1
<p>Target region division. (<b>a</b>) Sampling patches; (<b>b</b>) sampling sub-patches; (<b>c</b>) a patch distribution map.</p> Full article ">Figure 2
<p>Schematic diagram of the proposed tracking method.</p> Full article ">Figure 3
<p>An illustration of the variation of the outlier ratio <span class="html-italic">η</span> on the FaceOcc1 sequence. In the bottom plot, the blue curve reflects the variation of the outlier ratio on each frame, and the two horizontal red dashed lines are the predefined thresholds (set to 0.1 and 0.35 in our approach). We also mark the key frames and their indices with red points in the plot, which are correspondingly shown at the top of the plot.</p> Full article ">Figure 3 Cont.
<p>An illustration of the variation of the outlier ratio <span class="html-italic">η</span> on the FaceOcc1 sequence. In the bottom plot, the blue curve reflects the variation of the outlier ratio on each frame, and the two horizontal red dashed lines are the predefined thresholds (set to 0.1 and 0.35 in our approach). We also mark the key frames and their indices with red points in the plot, which are correspondingly shown at the top of the plot.</p> Full article ">Figure 4
<p>The precision and success plots of the tracking results on the OTB-2013 benchmark dataset. The legends contain the scores of the center location error with the threshold of 20 pixels and values of the area under curve for all trackers in the precision and success plots, respectively. Note that the color of one curve is determined by the rank of the corresponding trackers, not their names.</p> Full article ">Figure 5
<p>Precision plots for different attributes. The legend contains the precision score of each tracker at 20 pixels.</p> Full article ">Figure 6
<p>Success plots for different attributes. The legend contains the AUC score of each tracker.</p> Full article ">Figure 6 Cont.
<p>Success plots for different attributes. The legend contains the AUC score of each tracker.</p> Full article ">Figure 7
<p>Evaluation of template update strategy on the OTB-2013 benchmark dataset.</p> Full article ">Figure 8
<p>Screenshots of some sampled tracking results, where objects are heavily occluded. (<b>a</b>) FaceOcc1 with occlusion; (<b>b</b>) Football with occlusion and background clutters; (<b>c</b>) Walking2 with occlusion and scale variation.</p> Full article ">Figure 9
<p>Screenshots of some sampled tracking results, where objects undergo deformations. (<b>a</b>) Crossing with deformation and illumination variation; (<b>b</b>) David3 with deformation and occlusion; (<b>c</b>) Skating1 with deformation and illumination variation.</p> Full article ">Figure 9 Cont.
<p>Screenshots of some sampled tracking results, where objects undergo deformations. (<b>a</b>) Crossing with deformation and illumination variation; (<b>b</b>) David3 with deformation and occlusion; (<b>c</b>) Skating1 with deformation and illumination variation.</p> Full article ">Figure 10
<p>Screenshots of some sampled tracking results, where objects suffer from significant scale variations. (<b>a</b>) CarScale with scale variation and occlusion; (<b>b</b>) Freeman3 with scale variation and rotation; (<b>c</b>) Singer1 with scale variation and illumination variation.</p> Full article ">Figure 11
<p>Screenshots of some sampled tracking results, where objects suffer from rotation. (<b>a</b>) David with rotation and illumination variation; (<b>b</b>) Dudek with rotation and scale variation; (<b>c</b>) Freeman4 with rotation and occlusion.</p> Full article ">
17 pages, 738 KiB  
Article
An Effective Data Transmission Algorithm Based on Social Relationships in Opportunistic Mobile Social Networks
by Yeqing Yan, Zhigang Chen, Jia Wu and Leilei Wang
Algorithms 2018, 11(8), 125; https://doi.org/10.3390/a11080125 - 14 Aug 2018
Cited by 17 | Viewed by 5085
Abstract
With the popularization of mobile communication equipment, human activities have an increasing impact on the structure of networks, and so the social characteristics of opportunistic networks become increasingly obvious. Opportunistic networks are increasingly used in social situations. However, existing routing algorithms are not [...] Read more.
With the popularization of mobile communication equipment, human activities have an increasing impact on the structure of networks, and so the social characteristics of opportunistic networks become increasingly obvious. Opportunistic networks are increasingly used in social situations. However, existing routing algorithms are not suitable for opportunistic social networks, because traditional opportunistic network routing does not consider participation in human activities, which usually causes a high ratio of transmission delay and routing overhead. Therefore, this research proposes an effective data transmission algorithm based on social relationships (ESR), which considers the community characteristics of opportunistic mobile social networks. This work uses the idea of the faction to divide the nodes in the network into communities, reduces the number of inefficient nodes in the community, and performs another contraction of the structure. Simulation results show that the ESR algorithm, through community transmission, is not only faster and safer, but also has lower transmission delay and routing overhead compared with the spray and wait algorithm, SCR algorithm and the EMIST algorithm. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>A 12-node network as an example, to show the division of nodes based on faction.</p> Full article ">Figure 2
<p>These seven graphs show the results of the division of factions after all nodes in the network have been traversed.</p> Full article ">Figure 3
<p>This picture shows the result of community division of the network structure shown in <a href="#algorithms-11-00125-f001" class="html-fig">Figure 1</a>.</p> Full article ">Figure 4
<p>The influence of community division interval on packet delivery rate.</p> Full article ">Figure 5
<p>The packet delivery ratio of the ESR algorithm, EIMST algorithm, Spray and wait algorithm and the SCR algorithm at different node cache sizes and numbers of nodes. (<b>a</b>) The effect of node cache on packet delivery ratio; (<b>b</b>) The effect of node numbers on packet delivery ratio.</p> Full article ">Figure 6
<p>The average end-to-end transmission delay of ESR algorithms, EIMST algorithm, Spray and wait algorithm and SCR algorithm when at different node cache sizes and number of nodes. (<b>a</b>) The effect of node cache on transmission delay; (<b>b</b>) The effect of node numbers on transmission delay.</p> Full article ">Figure 7
<p>The average routing overhead of the ESR algorithm, EIMST algorithm, Spray and wait algorithm and SCR algorithm when at different node cache sizes and number of nodes. (<b>a</b>) The effect of node cache on routing overhead; (<b>b</b>) The effect of node cache on routing overhead.</p> Full article ">
13 pages, 1979 KiB  
Article
A Simhash-Based Integrative Features Extraction Algorithm for Malware Detection
by Yihong Li, Fangzheng Liu, Zhenyu Du and Dubing Zhang
Algorithms 2018, 11(8), 124; https://doi.org/10.3390/a11080124 - 14 Aug 2018
Cited by 10 | Viewed by 5396
Abstract
In the malware detection process, obfuscated malicious codes cannot be efficiently and accurately detected solely in the dynamic or static feature space. Aiming at this problem, an integrative feature extraction algorithm based on simhash was proposed, which combines the static information e.g., API [...] Read more.
In the malware detection process, obfuscated malicious codes cannot be efficiently and accurately detected solely in the dynamic or static feature space. Aiming at this problem, an integrative feature extraction algorithm based on simhash was proposed, which combines the static information e.g., API (Application Programming Interface) calls and dynamic information (such as file, registry and network behaviors) of malicious samples to form integrative features. The experiment extracts the integrative features of some static information and dynamic information, and then compares the classification, time and obfuscated-detection performance of the static, dynamic and integrated features, respectively, by using several common machine learning algorithms. The results show that the integrative features have better time performance than the static features, and better classification performance than the dynamic features, and almost the same obfuscated-detection performance as the dynamic features. This algorithm can provide some support for feature extraction of malware detection. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>The process of the simhash-based integrative feature extraction algorithm. (PEiD (PE iDentifier), IDA Pro (Interactive Disassembler Professional)).</p> Full article ">Figure 2
<p>The process of the simhash algorithm.</p> Full article ">Figure 3
<p>Integrative feature extraction.</p> Full article ">Figure 4
<p>The ROC (Receiver Operating Characteristic curve, ROC) curve of the algorithms. TP (True Positive rate, TP), FP (False Positive, FP), NB (Naive Bayes, NB), SGD (Stochastic Gradient Descent, SGD), SVM (Support Vector Machine, SVM), Ada (Adaboost, Ada) and RT (Random Trees, RT).</p> Full article ">Figure 5
<p>Classification effect of different types of features under different algorithms. CC (Correctly Classified rate, CC), NB (Naive Bayes, NB), SGD (Stochastic Gradient Descent, SGD), SVM (Support Vector Machine, SVM), Ada (Adaboost, Ada) and RT (Random Trees, RT).</p> Full article ">Figure 6
<p>Classification effect of different algorithms under different types of features. CC (Correctly Classified rate, CC), NB (Naive Bayes, NB), SGD (Stochastic Gradient Descent, SGD), SVM (Support Vector Machine, SVM), Ada (Adaboost, Ada) and RT (Random Trees, RT).</p> Full article ">Figure 7
<p>The obfuscated-detection results. DR (Detection Rate, DR), NB (Naive Bayes, NB), SGD (Stochastic Gradient Descent, SGD), SVM (Support Vector Machine, SVM), Ada (Adaboost, Ada) and RT (Random Trees, RT).</p> Full article ">
19 pages, 4243 KiB  
Article
Time Series Forecasting Using a Two-Level Multi-Objective Genetic Algorithm: A Case Study of Maintenance Cost Data for Tunnel Fans
by Yamur K. Al-Douri, Hussan Hamodi and Jan Lundberg
Algorithms 2018, 11(8), 123; https://doi.org/10.3390/a11080123 - 13 Aug 2018
Cited by 24 | Viewed by 5961
Abstract
The aim of this study has been to develop a novel two-level multi-objective genetic algorithm (GA) to optimize time series forecasting data for fans used in road tunnels by the Swedish Transport Administration (Trafikverket). Level 1 is for the process of forecasting time [...] Read more.
The aim of this study has been to develop a novel two-level multi-objective genetic algorithm (GA) to optimize time series forecasting data for fans used in road tunnels by the Swedish Transport Administration (Trafikverket). Level 1 is for the process of forecasting time series cost data, while level 2 evaluates the forecasting. Level 1 implements either a multi-objective GA based on the ARIMA model or a multi-objective GA based on the dynamic regression model. Level 2 utilises a multi-objective GA based on different forecasting error rates to identify a proper forecasting. Our method is compared with using the ARIMA model only. The results show the drawbacks of time series forecasting using only the ARIMA model. In addition, the results of the two-level model show the drawbacks of forecasting using a multi-objective GA based on the dynamic regression model. A multi-objective GA based on the ARIMA model produces better forecasting results. In level 2, five forecasting accuracy functions help in selecting the best forecasting. Selecting a proper methodology for forecasting is based on the averages of the forecasted data, the historical data, the actual data and the polynomial trends. The forecasted data can be used for life cycle cost (LCC) analysis. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Two-level system of multi-objective GAs.</p> Full article ">Figure 2
<p>Labour cost data forecasting based on the ARIMA model.</p> Full article ">Figure 3
<p>Material cost data forecasting based on the ARIMA model.</p> Full article ">Figure 4
<p>Labour cost data forecasting using the multi-objective GA based on the ARIMA model.</p> Full article ">Figure 5
<p>Material cost data forecasting using the multi-objective GA based on the ARIMA model.</p> Full article ">Figure 6
<p>Labour cost error rate.</p> Full article ">Figure 7
<p>Material cost error rate.</p> Full article ">Figure 8
<p>Labour cost data forecasting based on the dynamic regression model.</p> Full article ">Figure 9
<p>Material cost data forecasting based on the dynamic regression model.</p> Full article ">
14 pages, 2802 KiB  
Article
Efficient Model-Based Object Pose Estimation Based on Multi-Template Tracking and PnP Algorithms
by Chi-Yi Tsai, Kuang-Jui Hsu and Humaira Nisar
Algorithms 2018, 11(8), 122; https://doi.org/10.3390/a11080122 - 12 Aug 2018
Cited by 12 | Viewed by 6009
Abstract
Three-Dimensional (3D) object pose estimation plays a crucial role in computer vision because it is an essential function in many practical applications. In this paper, we propose a real-time model-based object pose estimation algorithm, which integrates template matching and Perspective-n-Point (PnP) pose estimation [...] Read more.
Three-Dimensional (3D) object pose estimation plays a crucial role in computer vision because it is an essential function in many practical applications. In this paper, we propose a real-time model-based object pose estimation algorithm, which integrates template matching and Perspective-n-Point (PnP) pose estimation methods to deal with this issue efficiently. The proposed method firstly extracts and matches keypoints of the scene image and the object reference image. Based on the matched keypoints, a two-dimensional (2D) planar transformation between the reference image and the detected object can be formulated by a homography matrix, which can initialize a template tracking algorithm efficiently. Based on the template tracking result, the correspondence between image features and control points of the Computer-Aided Design (CAD) model of the object can be determined efficiently, thus leading to a fast 3D pose tracking result. Finally, the 3D pose of the object with respect to the camera is estimated by a PnP solver based on the tracked 2D-3D correspondences, which improves the accuracy of the pose estimation. Experimental results show that the proposed method not only achieves real-time performance in tracking multiple objects, but also provides accurate pose estimation results. These advantages make the proposed method suitable for many practical applications, such as augmented reality. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>System framework of the proposed model-based object pose estimation algorithm.</p> Full article ">Figure 2
<p>Three template patches of the Object-Of-Interest (OOI) used in the experiments.</p> Full article ">Figure 3
<p>Pose estimation results of the proposed algorithm in tracking the OOI with the three templates shown in <a href="#algorithms-11-00122-f002" class="html-fig">Figure 2</a>: 3D pose estimation by tracking (<b>a</b>) the template No. 1, (<b>b</b>) the two templates No.1 and No. 3, (<b>c</b>) the template No. 3, (<b>d</b>) the two templates No.1 and No. 3 again, (<b>e</b>) the template No. 1, (<b>f</b>) the two templates No. 1 and No. 2, (<b>g</b>) the template No. 2 and (<b>h</b>) the template No. 1 with a rotation on the <span class="html-italic">z</span>-axis.</p> Full article ">Figure 4
<p>Experimental results of the proposed algorithm to estimate the translation motions of the OOI along the (<b>a1</b>–<b>h1</b>) <span class="html-italic">x</span>-axis, (<b>a2</b>–<b>h2</b>) <span class="html-italic">y</span>-axis and (<b>a3</b>–<b>h3</b>) <span class="html-italic">z</span>-axis.</p> Full article ">Figure 5
<p>Experimental results of the proposed algorithm to estimate the rotation angles of the (<b>a1</b>–<b>h1</b>) <span class="html-italic">x</span>-axis, (<b>a2</b>–<b>h2</b>) <span class="html-italic">y</span>-axis and (<b>a3</b>–<b>h3</b>) <span class="html-italic">z</span>-axis of the OOI.</p> Full article ">Figure 6
<p>Experimental results of multi-object pose tracking of the proposed algorithm [<a href="#B32-algorithms-11-00122" class="html-bibr">32</a>].</p> Full article ">
10 pages, 1560 KiB  
Article
Stacked-GRU Based Power System Transient Stability Assessment Method
by Feilai Pan, Jun Li, Bendong Tan, Ciling Zeng, Xinfan Jiang, Li Liu and Jun Yang
Algorithms 2018, 11(8), 121; https://doi.org/10.3390/a11080121 - 9 Aug 2018
Cited by 25 | Viewed by 6311
Abstract
With the interconnection between large power grids, the issue of security and stability has become increasingly prominent. At present, data-driven power system adaptive transient stability assessment methods have achieved excellent performances by balancing speed and accuracy, but the complicated construction and parameters are [...] Read more.
With the interconnection between large power grids, the issue of security and stability has become increasingly prominent. At present, data-driven power system adaptive transient stability assessment methods have achieved excellent performances by balancing speed and accuracy, but the complicated construction and parameters are difficult to obtain. This paper proposes a stacked-GRU (Gated Recurrent Unit)-based transient stability intelligent assessment method, which builds a stacked-GRU model based on time-dependent parameter sharing and spatial stacking. By using the time series data after power system failure, the offline training is performed to obtain the optimal parameters of stacked-GRU. When the application is online, it is assessed by framework of confidence. Basing on New England power system, the performance of proposed adaptive transient stability assessment method is investigated. Simulation results show that the proposed model realizes reliable and accurate assessment of transient stability and it has the advantages of short assessment time with less complex model structure to leave time for emergency control. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Gated Recurrent Unit.</p> Full article ">Figure 2
<p>The structure of stacked-GRU.</p> Full article ">Figure 3
<p>Online application of transient stability intelligent assessment.</p> Full article ">Figure 4
<p>The New England power system.</p> Full article ">Figure 5
<p>(<b>a</b>) Transient stable case; (<b>b</b>) transient unstable case.</p> Full article ">Figure 6
<p>(<b>a</b>) The relationship between ART and number of layers; (<b>b</b>) <math display="inline"><semantics> <mrow> <mi mathvariant="sans-serif">δ</mi> </mrow> </semantics></math> sensitivity analysis.</p> Full article ">Figure 7
<p>Comparison of different model performance.</p> Full article ">
17 pages, 300 KiB  
Article
Probabilistic Interval-Valued Hesitant Fuzzy Information Aggregation Operators and Their Application to Multi-Attribute Decision Making
by Wenying Wu, Ying Li, Zhiwei Ni, Feifei Jin and Xuhui Zhu
Algorithms 2018, 11(8), 120; https://doi.org/10.3390/a11080120 - 6 Aug 2018
Cited by 24 | Viewed by 4160
Abstract
Based on the probabilistic interval-valued hesitant fuzzy information aggregation operators, this paper investigates a novel multi-attribute group decision making (MAGDM) model to address the serious loss of information in a hesitant fuzzy information environment. Firstly, the definition of probabilistic interval-valued hesitant fuzzy set [...] Read more.
Based on the probabilistic interval-valued hesitant fuzzy information aggregation operators, this paper investigates a novel multi-attribute group decision making (MAGDM) model to address the serious loss of information in a hesitant fuzzy information environment. Firstly, the definition of probabilistic interval-valued hesitant fuzzy set will be introduced, and then, using Archimedean norm, some new probabilistic interval-valued hesitant fuzzy operations are defined. Secondly, based on these operations, the generalized probabilistic interval-valued hesitant fuzzy ordered weighted averaging (GPIVHFOWA) operator, and the generalized probabilistic interval-valued hesitant fuzzy ordered weighted geometric (GPIVHFOWG) operator are proposed, and their desirable properties are discussed. We further study their common forms and analyze the relationship among these proposed operators. Finally, a new probabilistic interval-valued hesitant fuzzy MAGDM model is constructed, and the feasibility and effectiveness of the proposed model are verified by using an example of supplier selection. Full article
(This article belongs to the Special Issue Algorithms for Decision Making)
14 pages, 2666 KiB  
Article
An Opportunistic Network Routing Algorithm Based on Cosine Similarity of Data Packets between Nodes
by Yucheng Lin, Zhigang Chen, Jia Wu and Leilei Wang
Algorithms 2018, 11(8), 119; https://doi.org/10.3390/a11080119 - 6 Aug 2018
Cited by 8 | Viewed by 4016
Abstract
The mobility of nodes leads to dynamic changes in topology structure, which makes the traditional routing algorithms of a wireless network difficult to apply to the opportunistic network. In view of the problems existing in the process of information forwarding, this paper proposed [...] Read more.
The mobility of nodes leads to dynamic changes in topology structure, which makes the traditional routing algorithms of a wireless network difficult to apply to the opportunistic network. In view of the problems existing in the process of information forwarding, this paper proposed a routing algorithm based on the cosine similarity of data packets between nodes (cosSim). The cosine distance, an algorithm for calculating the similarity between text data, is used to calculate the cosine similarity of data packets between nodes. The data packet set of nodes are expressed in the form of vectors, thereby facilitating the calculation of the similarity between the nodes. Through the definition of the upper and lower thresholds, the similarity between the nodes is filtered according to certain rules, and finally obtains a plurality of relatively reliable transmission paths. Simulation experiments show that compared with the traditional opportunistic network routing algorithm, such as the Spray and Wait (S&W) algorithm and Epidemic algorithm, the cosSim algorithm has a better transmission effect, which can not only improve the delivery ratio, but also reduce the network transmission delay and decline the routing overhead. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Schematic diagram of opportunistic network transmission.</p> Full article ">Figure 2
<p>The topology structure of sub-network.</p> Full article ">Figure 3
<p>The structure of the tree.</p> Full article ">Figure 4
<p>The structure of the tree.</p> Full article ">Figure 5
<p>Transmission paths.</p> Full article ">Figure 6
<p>(<b>a</b>) Lower Threshold and (<b>b</b>) Upper Threshold.</p> Full article ">Figure 7
<p>Delivery ratio (node cache).</p> Full article ">Figure 8
<p>Delivery ratio.</p> Full article ">Figure 9
<p>Delivery delay.</p> Full article ">Figure 10
<p>Routing overhead.</p> Full article ">
11 pages, 446 KiB  
Article
Sliding Suffix Tree
by Andrej Brodnik and Matevž Jekovec
Algorithms 2018, 11(8), 118; https://doi.org/10.3390/a11080118 - 3 Aug 2018
Cited by 4 | Viewed by 6460
Abstract
We consider a sliding window W over a stream of characters from some alphabet of constant size. We want to look up a pattern in the current sliding window content and obtain all positions of the matches. We present an indexed version of [...] Read more.
We consider a sliding window W over a stream of characters from some alphabet of constant size. We want to look up a pattern in the current sliding window content and obtain all positions of the matches. We present an indexed version of the sliding window, based on a suffix tree. The data structure of size Θ(|W|) has optimal time queries Θ(m+occ) and amortized constant time updates, where m is the length of the query string and occ is its number of occurrences. Full article
(This article belongs to the Special Issue Efficient Data Structures)
►▼ Show Figures

Figure 1

Figure 1
<p>Illustration of the suffix tree for text ABRACADABRA<span>$</span> including the implicit labels. Suffix links connecting internal nodes are drawn as dotted green lines. Values in each internal node represent the start index and the length of a label on the incoming edge, whereas the value of a leaf represent the suffix position in the text.</p> Full article ">Figure 2
<p>On the left: Illustration of partially constructed suffix tree <math display="inline"><semantics> <mi mathvariant="script">T</mi> </semantics></math> with implicit buffer <span class="html-italic">B</span> and active node <math display="inline"><semantics> <mi>β</mi> </semantics></math>. On the right: Illustration of the stream, the sliding window <span class="html-italic">W</span>, the implicit buffer <span class="html-italic">B</span>, and three cases for positions of the query strings <math display="inline"><semantics> <mrow> <mi>o</mi> <mi>c</mi> <msub> <mi>c</mi> <mn>1</mn> </msub> </mrow> </semantics></math>, <math display="inline"><semantics> <mrow> <mi>o</mi> <mi>c</mi> <msub> <mi>c</mi> <mn>2</mn> </msub> </mrow> </semantics></math>, and <math display="inline"><semantics> <mrow> <mi>o</mi> <mi>c</mi> <msub> <mi>c</mi> <mn>3</mn> </msub> </mrow> </semantics></math>.</p> Full article ">Figure 3
<p>(<b>a</b>) Occurrences of <span class="html-italic">B</span> in the window, if <math display="inline"><semantics> <mrow> <mi>x</mi> <mo>&gt;</mo> <mi>n</mi> <mo>-</mo> <mn>2</mn> <mo>|</mo> <mi>B</mi> <mo>|</mo> </mrow> </semantics></math>. (<b>b</b>) Repeated pattern <span class="html-italic">P</span>. (<b>c</b>) Potential occurrences of <span class="html-italic">Q</span>. <math display="inline"><semantics> <msub> <mi>y</mi> <mn>1</mn> </msub> </semantics></math> and <math display="inline"><semantics> <msub> <mi>y</mi> <mn>2</mn> </msub> </semantics></math> are positions stored in the finalized suffix tree. The second two positions of <span class="html-italic">Q</span> are obtained in Case 3, Step 1. The last position of <span class="html-italic">Q</span> is obtained in Case 3, Step 2.</p> Full article ">Figure 4
<p>Shifting the window <math display="inline"><semantics> <mrow> <mi>a</mi> <mi>b</mi> <mi>a</mi> <mi>b</mi> <mi>c</mi> <mi>a</mi> <mi>b</mi> <mi>a</mi> <mi>b</mi> </mrow> </semantics></math> to the right for one character, where <math display="inline"><semantics> <mrow> <mi>B</mi> <mo>=</mo> <mi>a</mi> <mi>b</mi> <mi>a</mi> <mi>b</mi> </mrow> </semantics></math> denoted by red labels. Notice the “lost” leaf <math display="inline"><semantics> <mrow> <mi>a</mi> <mi>b</mi> <mi>a</mi> <mi>b</mi> </mrow> </semantics></math> on the right, where instead of removing the oldest leaf, we only update its position. For brevity, the figure omits the newly appended character to the window.</p> Full article ">
16 pages, 3615 KiB  
Article
Research of the Vibration Source Tracking in Phase-Sensitive Optical Time-Domain Reflectometry Signals Based by Image Processing Method
by Yanzhu Hu, Song Wang and Xinbo Ai
Algorithms 2018, 11(8), 117; https://doi.org/10.3390/a11080117 - 2 Aug 2018
Cited by 1 | Viewed by 3925
Abstract
This paper aims to improve the source tracking efficiency of distributed vibration signals generated by phase-sensitive optical time-domain reflectometry (Φ-OTDR). Considering the two dimensions (time and length) of Φ-OTDR signals, the authors saved and processed these signals as images after particle filtering. The [...] Read more.
This paper aims to improve the source tracking efficiency of distributed vibration signals generated by phase-sensitive optical time-domain reflectometry (Φ-OTDR). Considering the two dimensions (time and length) of Φ-OTDR signals, the authors saved and processed these signals as images after particle filtering. The filtering method could save 0.1% of hard drive space without sacrificing the original features of the signals. Then, an integrated feature extraction method was proposed to further process the generated image. The method combines three individual extraction methods, namely, texture feature extraction, shape feature extraction and intrinsic feature extraction. Subsequently, the signal of each frame image was recognized to track the vibration source. To verify the effect of the proposed method, several experiments were carried out to compare it with popular and traditional approaches. The results show that: Hard drive space is greatly conserved by saving the distributed vibration signals as images; the proposed particle filter is a desirable way to screen the vibration signals for monitoring; the integrated feature extraction outperforms the individual extraction methods for texture features, shape features and intrinsic features; the proposed method has a better effect than other popular integrated feature extraction methods; and, the signal source tracking method has little impact on the positioning accuracy of the vibration source. The research findings provide important insights into the source tracking of Φ-OTDR signals. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Steps of the proposed method.</p> Full article ">Figure 2
<p>2D diagram of distributed vibration signals.</p> Full article ">Figure 3
<p>The flow diagram of algorithm.</p> Full article ">Figure 4
<p>Structure of GoogLeNet.</p> Full article ">Figure 5
<p>Improved box filter. (<b>a</b>) Box filter of D<span class="html-italic">xy</span> (Two order derivatives for <span class="html-italic">X</span> and <span class="html-italic">Y</span> axes) (<b>b</b>) Box filter of D<span class="html-italic">yy</span> (Two order derivatives for <span class="html-italic">Y</span> axe) (<b>c</b>) Box filter of D<span class="html-italic">xx</span> (Two order derivatives for <span class="html-italic">X</span> axe).</p> Full article ">Figure 6
<p>Image of Φ-OTDR instrument.</p> Full article ">Figure 7
<p>Image of the standard five-hammer vibration device.</p> Full article ">Figure 8
<p>Images of the signals of each step: (<b>a</b>) Image of the original signals; (<b>b</b>) image of the filtered signals; and, (<b>c</b>) image of the enhanced signals.</p> Full article ">Figure 8 Cont.
<p>Images of the signals of each step: (<b>a</b>) Image of the original signals; (<b>b</b>) image of the filtered signals; and, (<b>c</b>) image of the enhanced signals.</p> Full article ">Figure 9
<p>Comparison of two indexes under different weight.</p> Full article ">Figure 10
<p>Comparison of two indexes under different weight.</p> Full article ">Figure 11
<p>Subjective effect of target recognition in different methods.</p> Full article ">Figure 12
<p>Perceptual model on length axis.</p> Full article ">
21 pages, 2999 KiB  
Article
A Robust and Energy-Efficient Weighted Clustering Algorithm on Mobile Ad Hoc Sensor Networks †
by Huamei Qi, Fengqi Liu, Tailong Xiao and Jiang Su
Algorithms 2018, 11(8), 116; https://doi.org/10.3390/a11080116 - 1 Aug 2018
Cited by 9 | Viewed by 4232
Abstract
In an Ad hoc sensor network, nodes have characteristics of limited battery energy, self-organization and low mobility. Due to the mobility and heterogeneity of the energy consumption in the hierarchical network, the cluster head and topology are changed dynamically. Therefore, topology control and [...] Read more.
In an Ad hoc sensor network, nodes have characteristics of limited battery energy, self-organization and low mobility. Due to the mobility and heterogeneity of the energy consumption in the hierarchical network, the cluster head and topology are changed dynamically. Therefore, topology control and energy consumption are growing to be critical in enhancing the stability and prolonging the lifetime of the network. In order to improve the survivability of Ad hoc network effectively, this paper proposes a new algorithm named the robust, energy-efficient weighted clustering algorithm (RE2WCA). For the homogeneous of the energy consumption; the proposed clustering algorithm takes the residual energy and group mobility into consideration by restricting minimum iteration times. In addition, a distributed fault detection algorithm and cluster head backup mechanism are presented to achieve the periodic and real-time topology maintenance to enhance the robustness of the network. The network is analyzed and the simulations are performed to compare the performance of this new clustering algorithm with the similar algorithms in terms of cluster characteristics, lifetime, throughput and energy consumption of the network. The result shows that the proposed algorithm provides better performance than others. Full article
(This article belongs to the Special Issue Selected Papers from: 11th Annual International Conference on Combinatorial Optimization and Applications (COCOA'17))
►▼ Show Figures

Figure 1

Figure 1
<p>Nodes displacement schematic.</p> Full article ">Figure 2
<p>The <span class="html-italic">CH</span> selection process in RE<sup>2</sup>WCA. (<b>a</b>) Tentative CHs (A, B, C, D, E) form. There are some nodes fail to join a cluster. (<b>b</b>) The tentative CHs (A, D, E, F, G, H, I) are updated and increased, so only a few nodes are at free state. (<b>c</b>) All nodes have their only cluster and tentative CHs become formal CHs (A, D, E, F, G, H, I, J).</p> Full article ">Figure 3
<p>A clustering wireless sensor network model.</p> Full article ">Figure 4
<p>(<b>a</b>–<b>c</b>) is the practical example of fault node detection process. (<b>a</b>) Cluster members (3, 9) send message to <span class="html-italic">CH</span>. Node 6 fails sending, hence node 6 is to be probable fault node. (<b>b</b>) Nodes (3, 6, 9) send message to <span class="html-italic">CH</span> respectively. Node 6 is normal. (<b>c</b>) Nodes (3, 9) send message to <span class="html-italic">CH</span> respectively. Node 6 still fails to send messages.</p> Full article ">Figure 5
<p>(<b>a</b>–<b>c</b>) is the practical example of Backup <span class="html-italic">CH</span> mechanism process. (<b>a</b>) In the period of <span class="html-italic">time_fn2</span>, nodes (3, 9) receive the message from <span class="html-italic">CH</span> (5) but node 6 not. Node 6 marks <span class="html-italic">CH</span> possibly failed. (<b>b</b>) Backup <span class="html-italic">CH</span> launch the status enquiry message for cluster. (<b>c</b>) Backup <span class="html-italic">CH</span> receive the messages from inner- cluster nodes and judge <span class="html-italic">CH</span> is faulted or not.</p> Full article ">Figure 6
<p>Round of network set up.</p> Full article ">Figure 7
<p>TDMA schemes adopted for the intra-cluster communication.</p> Full article ">Figure 8
<p>CDMA schemes adopted for the inter-cluster communication.</p> Full article ">Figure 9
<p>Features of elected CHs. (<b>a</b>) Percentage of CHs. (<b>b</b>) Average residual energy per <span class="html-italic">CH</span>.</p> Full article ">Figure 10
<p>Features of clusters. (<b>a</b>) Standard deviation of the number of nodes/cluster. (<b>b</b>) Percentage of non-single clusters. (<b>c</b>) Ratio of maximum number of nodes in RE<sup>2</sup>WCA to other two types protocol. (<b>d</b>) Rate of <span class="html-italic">CH</span> changes with node speed varying.</p> Full article ">Figure 11
<p>Surviving nodes vary with Round number.</p> Full article ">Figure 12
<p>Throughput of the network. (<b>a</b>) Network throughput varies with the distance. (<b>b</b>) Network throughput under certain fault nodes.</p> Full article ">Figure 13
<p>Number of packages dropped varies with Mobility parameter.</p> Full article ">Figure 14
<p>Network energy consumption with the network round number increases.</p> Full article ">
12 pages, 486 KiB  
Article
Color-Based Image Retrieval Using Proximity Space Theory
by Jing Wang, Lidong Wang, Xiaodong Liu, Yan Ren and Ye Yuan
Algorithms 2018, 11(8), 115; https://doi.org/10.3390/a11080115 - 28 Jul 2018
Cited by 10 | Viewed by 3923
Abstract
The goal of object retrieval is to rank a set of images by their similarity compared with a query image. Nowadays, content-based image retrieval is a hot research topic, and color features play an important role in this procedure. However, it is important [...] Read more.
The goal of object retrieval is to rank a set of images by their similarity compared with a query image. Nowadays, content-based image retrieval is a hot research topic, and color features play an important role in this procedure. However, it is important to establish a measure of image similarity in advance. The innovation point of this paper lies in the following. Firstly, the idea of the proximity space theory is utilized to retrieve the relevant images between the query image and images of database, and we use the color histogram of an image to obtain the Top-ranked colors, which can be regard as the object set. Secondly, the similarity is calculated based on an improved dominance granule structure similarity method. Thus, we propose a color-based image retrieval method by using proximity space theory. To detect the feasibility of this method, we conducted an experiment on COIL-20 image database and Corel-1000 database. Experimental results demonstrate the effectiveness of the proposed framework and its applications. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>(<b>a</b>) The query image; and (<b>b</b>) the color histogram of image (<b>a</b>).</p> Full article ">Figure 2
<p>The framework of the content-based image retrieval using proximity space theory.</p> Full article ">Figure 3
<p>The left image shows car category results, while the right image shows cup category results.</p> Full article ">Figure 4
<p>Images selected from COIL-20 dataset.</p> Full article ">Figure 5
<p>Ten classes on Corel-1000 dataset.</p> Full article ">Figure 6
<p>Retrieved images for the Top 20: the dinosaurs category (<b>a</b>); (<b>b</b>) the horses category; and (<b>c</b>) the foods category. The query image is the first image in each class.</p> Full article ">
9 pages, 557 KiB  
Article
Revisiting Chameleon Sequences in the Protein Data Bank
by Mihaly Mezei
Algorithms 2018, 11(8), 114; https://doi.org/10.3390/a11080114 - 28 Jul 2018
Cited by 5 | Viewed by 4471
Abstract
The steady growth of the Protein Data Bank (PDB) suggests the periodic repetition of searches for sequences that form different secondary structures in different protein structures; these are called chameleon sequences. This paper presents a fast (nlog(n)) algorithm for [...] Read more.
The steady growth of the Protein Data Bank (PDB) suggests the periodic repetition of searches for sequences that form different secondary structures in different protein structures; these are called chameleon sequences. This paper presents a fast (nlog(n)) algorithm for such searches and presents the results on all protein structures in the PDB. The longest such sequence found consists of 20 residues. Full article
►▼ Show Figures

Graphical abstract

Graphical abstract
Full article ">Figure 1
<p>Distribution of helix length (full line) and sheet (broken line) length in the Protein Data Bank (PDB); length is the number of residues.</p> Full article ">
11 pages, 2556 KiB  
Article
Improved Parameter Identification Method for Envelope Current Signals Based on Windowed Interpolation FFT and DE Algorithm
by Xiangfeng Su, Huaiqing Zhang, Lin Chen, Ling Qin and Lili Yu
Algorithms 2018, 11(8), 113; https://doi.org/10.3390/a11080113 - 27 Jul 2018
Cited by 1 | Viewed by 3516
Abstract
Envelope current signals are increasingly emerging in power systems, and their parameter identification is particularly necessary for accurate measurement of electrical energy. In order to analyze the envelope current signal, the harmonic parameters, as well as the envelope parameters, need to be calculated. [...] Read more.
Envelope current signals are increasingly emerging in power systems, and their parameter identification is particularly necessary for accurate measurement of electrical energy. In order to analyze the envelope current signal, the harmonic parameters, as well as the envelope parameters, need to be calculated. The interpolation fast Fourier transform (FFT) is a widely used approach which can estimate the signal frequency with high precision, but it cannot calculate the envelope parameters of the signal. Therefore, this paper proposes an improved method based on windowed interpolation FFT (WIFFT) and differential evolution (DE). The amplitude and phase parameters obtained through WIFFT and the envelope parameters estimated by the envelope analysis are optimized using the DE algorithm, which makes full use of the performance advantage of DE. The simulation results show that the proposed method can improve the accuracy of the harmonic parameters and the envelope parameter significantly. In addition, it has good anti-noise ability and high precision. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>The current signal of an electric locomotive.</p> Full article ">Figure 2
<p>The flow chart of the improved method based on WIFFT and DE algorithm.</p> Full article ">Figure 3
<p>Simulation results of WIFFT: (<b>a</b>) Comparison of original signal and reconstructed signal; (<b>b</b>) Absolute error of original signal and reconstructed signal.</p> Full article ">Figure 4
<p>Simulation results of WIFFT and envelope parameters estimation method: (<b>a</b>) Comparison of original signal and reconstructed signal; (<b>b</b>) Absolute error of original signal and reconstructed signal.</p> Full article ">Figure 5
<p>Simulation results of the improved method based on WIFFT and DE algorithm: (<b>a</b>) Comparison of the original signal and reconstructed signal; (<b>b</b>) Absolute error of original signal and reconstructed signal.</p> Full article ">Figure 6
<p>Analysis results of envelope current signal of an electric locomotive when employing the WIFFT and envelope parameter estimation method: (<b>a</b>) The comparison of original signal and the reconstructed signal; (<b>b</b>) Absolute error of original signal and reconstructed signal.</p> Full article ">Figure 7
<p>Analysis results of envelope current signal of an electric locomotive when employing the improved method based on WIFFT and DE: (<b>a</b>) Comparison of the original signal and reconstructed signal; (<b>b</b>) Absolute error of original signal and reconstructed signal.</p> Full article ">
15 pages, 1938 KiB  
Article
A Novel Parallel Auto-Encoder Framework for Multi-Scale Data in Civil Structural Health Monitoring
by Ruhua Wang, Ling Li and Jun Li
Algorithms 2018, 11(8), 112; https://doi.org/10.3390/a11080112 - 27 Jul 2018
Cited by 21 | Viewed by 4304
Abstract
In this paper, damage detection/identification for a seven-storey steel structure is investigated via using the vibration signals and deep learning techniques. Vibration characteristics, such as natural frequencies and mode shapes are captured and utilized as input for a deep learning network while the [...] Read more.
In this paper, damage detection/identification for a seven-storey steel structure is investigated via using the vibration signals and deep learning techniques. Vibration characteristics, such as natural frequencies and mode shapes are captured and utilized as input for a deep learning network while the output vector represents the structural damage associated with locations. The deep auto-encoder with sparsity constraint is used for effective feature extraction for different types of signals and another deep auto-encoder is used to learn the relationship of different signals for final regression. The existing SAF model in a recent research study for the same problem processed all signals in one serial auto-encoder model. That kind of models have the following difficulties: (1) the natural frequencies and mode shapes are in different magnitude scales and it is not logical to normalize them in the same scale in building the models with training samples; (2) some frequencies and mode shapes may not be related to each other and it is not fair to use them for dimension reduction together. To tackle the above-mentioned problems for the multi-scale dataset in SHM, a novel parallel auto-encoder framework (Para-AF) is proposed in this paper. It processes the frequency signals and mode shapes separately for feature selection via dimension reduction and then combine these features together in relationship learning for regression. Furthermore, we introduce sparsity constraint in model reduction stage for performance improvement. Two experiments are conducted on performance evaluation and our results show the significant advantages of the proposed model in comparison with the existing approaches. Full article
(This article belongs to the Special Issue Discrete Algorithms and Discrete Problems in Machine Intelligence)
►▼ Show Figures

Figure 1

Figure 1
<p>Proposed parallel based sparse auto-encoder framework.</p> Full article ">Figure 2
<p>Proposed parallel auto-encoder model.</p> Full article ">Figure 3
<p>Laboratory steel frame model and the dimensions of the steel frame structure.</p> Full article ">Figure 4
<p>Finite element model of the steel frame structure.</p> Full article ">Figure 5
<p>Damage identification results of a single damage case from SAF and the proposed approach.</p> Full article ">Figure 6
<p>An example of multiple damage identification of SAF and the proposed approach.</p> Full article ">
20 pages, 18365 KiB  
Article
A Weighted Histogram-Based Tone Mapping Algorithm for CT Images
by David Völgyes, Anne Catrine Trægde Martinsen, Arne Stray-Pedersen, Dag Waaler and Marius Pedersen
Algorithms 2018, 11(8), 111; https://doi.org/10.3390/a11080111 - 25 Jul 2018
Cited by 12 | Viewed by 6774
Abstract
Computed Tomography (CT) images have a high dynamic range, which makes visualization challenging. Histogram equalization methods either use spatially invariant weights or limited kernel size due to the complexity of pairwise contribution calculation. We present a weighted histogram equalization-based tone mapping algorithm which [...] Read more.
Computed Tomography (CT) images have a high dynamic range, which makes visualization challenging. Histogram equalization methods either use spatially invariant weights or limited kernel size due to the complexity of pairwise contribution calculation. We present a weighted histogram equalization-based tone mapping algorithm which utilizes Fast Fourier Transform for distance-dependent contribution calculation and distance-based weights. The weights follow power-law without distance-based cut-off. The resulting images have good local contrast without noticeable artefacts. The results are compared to eight popular tone mapping operators. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Indicator array generation: <span class="html-italic">z</span> coordinates are calculated from the pixel value of the 2D image.</p> Full article ">Figure 2
<p>Columns in the <span class="html-italic">z</span>-direction contain the weighted histograms for corresponding pixels. Every pixel has its own local weighted histogram.</p> Full article ">Figure 3
<p>Local histograms might be clipped to reduce noise over-amplification.</p> Full article ">Figure 4
<p>Harbour in sunset, taken by the first author. The fine details of the deck and the buildings are hidden in the shadow.</p> Full article ">Figure 5
<p>Tone mapped chest CT scan with eight common operators and the proposed method. Parameters are summarized in <a href="#algorithms-11-00111-t001" class="html-table">Table 1</a>; a quantitative comparison is presented in <a href="#algorithms-11-00111-t002" class="html-table">Table 2</a>.</p> Full article ">Figure 5 Cont.
<p>Tone mapped chest CT scan with eight common operators and the proposed method. Parameters are summarized in <a href="#algorithms-11-00111-t001" class="html-table">Table 1</a>; a quantitative comparison is presented in <a href="#algorithms-11-00111-t002" class="html-table">Table 2</a>.</p> Full article ">Figure 6
<p>Tone mapped head CT scan with eight common operators and the proposed method. Parameters are summarized in <a href="#algorithms-11-00111-t001" class="html-table">Table 1</a>; a quantitative comparison is presented in <a href="#algorithms-11-00111-t002" class="html-table">Table 2</a>.</p> Full article ">Figure 7
<p>The effect of the <math display="inline"><semantics> <mrow> <mn>1</mn> <mo>/</mo> <msup> <mi>r</mi> <mi>a</mi> </msup> </mrow> </semantics></math> weighting function and clipping. Rows from top to bottom have <span class="html-italic">a</span> = 0.7, 1.0, 1.5, 2.0, respectively, and the clip limits in the columns from left to right are 1, 5, 10 and 20, using <math display="inline"><semantics> <mrow> <mn>1</mn> <mo>/</mo> <mi>N</mi> </mrow> </semantics></math> units where <span class="html-italic">N</span> is the number of histogram bins.</p> Full article ">Figure 8
<p>The effect of the <math display="inline"><semantics> <mrow> <mn>1</mn> <mo>/</mo> <msup> <mi>r</mi> <mi>a</mi> </msup> </mrow> </semantics></math> weighting function and clipping. Rows from top to bottom have <span class="html-italic">a</span> = 0.7, 1.0, 1.5, 2.0, respectively, and the clip limits in the columns from left to right are 1, 5, 10 and 20, using <math display="inline"><semantics> <mrow> <mn>1</mn> <mo>/</mo> <mi>N</mi> </mrow> </semantics></math> units where <span class="html-italic">N</span> is the number of histogram bins.</p> Full article ">Figure 9
<p>Structural similarity map for the head CT example. Brighter shades belong to higher local structural similarity (white = 1.0, black = 0.0).</p> Full article ">Figure 9 Cont.
<p>Structural similarity map for the head CT example. Brighter shades belong to higher local structural similarity (white = 1.0, black = 0.0).</p> Full article ">Figure 10
<p>Parameter sensitivity of the algorithm for (<b>a</b>) the chest CT, and (<b>b</b>) the head CT image.</p> Full article ">Figure 11
<p>Calculating the histograms using a decreasing number of discretization levels. While quality slightly degrades after a while, the linear interpolation and dithering make the algorithm robust. TMQI structural similarity slowly decreases as the approximation becomes coarser.</p> Full article ">Figure 12
<p>Calculating the histograms using spatial downsampling along each axis. Even significant downsampling does not cause very visible artefacts, which is also reflected in the TMQI score. However, local differences might appear, e.g., compare the middle region of the left lung in (<b>a</b>) and (<b>f</b>).</p> Full article ">Figure 13
<p>Approximate execution time scales with the number of pixels and the number of discretization levels plus a constant overhead because of data pre- and post-processing.</p> Full article ">
12 pages, 453 KiB  
Article
Image De-Quantization Using Plate Bending Model
by David Völgyes, Anne Catrine Trægde Martinsen, Arne Stray-Pedersen, Dag Waaler and Marius Pedersen
Algorithms 2018, 11(8), 110; https://doi.org/10.3390/a11080110 - 24 Jul 2018
Viewed by 3588
Abstract
Discretized image signals might have a lower dynamic range than the display. Because of this, false contours might appear when the image has the same pixel value for a larger region and the distance between pixel levels reaches the noticeable difference threshold. There [...] Read more.
Discretized image signals might have a lower dynamic range than the display. Because of this, false contours might appear when the image has the same pixel value for a larger region and the distance between pixel levels reaches the noticeable difference threshold. There have been several methods aimed at approximating the high bit depth of the original signal. Our method models a region with a bended plate model, which leads to the biharmonic equation. This method addresses several new aspects: the reconstruction of non-continuous regions when foreground objects split the area into separate regions; the incorporation of confidence about pixel levels, making the model tunable; and the method gives a physics-inspired way to handle local maximal/minimal regions. The solution of the biharmonic equation yields a smooth high-order signal approximation and handles the local maxima/minima problems. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Example of non-continuous regions. The sky exhibits strong false contours, and the foreground ship partitions the sky into several regions. The photo was taken by the first author.</p> Full article ">Figure 2
<p>Two dimensional simplified example of mirrored periodic boundary conditions. The image is represented as a red P, and its edges are outlined with a black line. The reflected signals are in black.</p> Full article ">Figure 3
<p>Discretized signal samples with upper and lower limits for the possible original function values. The minimized squared gradient magnitude (Laplace problem) assumption leads to a piecewise linear solution (red), while minimizing the bending energy or mean curvature leads to a higher-order smooth solution (blue).</p> Full article ">Figure 4
<p>Top row: Gaussian function; Bottom row: Rosenbrock function. From left to right: 8-bit reference image, downscaled 2-bit image, Laplace reconstruction, and biharmonic reconstruction.</p> Full article ">Figure 5
<p>Reconstruction of night sky. Top row from left to right: original 8-bit image, mask for region of interest, 2-bit quantization. Bottom row from left to right: Laplace reconstruction with mask, biharmonic reconstruction solving inside the mask only, biharmonic reconstruction where the masked values were added back.</p> Full article ">
12 pages, 1153 KiB  
Article
Long Length Document Classification by Local Convolutional Feature Aggregation
by Liu Liu, Kaile Liu, Zhenghai Cong, Jiali Zhao, Yefei Ji and Jun He
Algorithms 2018, 11(8), 109; https://doi.org/10.3390/a11080109 - 24 Jul 2018
Cited by 18 | Viewed by 4643
Abstract
The exponential increase in online reviews and recommendations makes document classification and sentiment analysis a hot topic in academic and industrial research. Traditional deep learning based document classification methods require the use of full textual information to extract features. In this paper, in [...] Read more.
The exponential increase in online reviews and recommendations makes document classification and sentiment analysis a hot topic in academic and industrial research. Traditional deep learning based document classification methods require the use of full textual information to extract features. In this paper, in order to tackle long document, we proposed three methods that use local convolutional feature aggregation to implement document classification. The first proposed method randomly draws blocks of continuous words in the full document. Each block is then fed into the convolution neural network to extract features and then are concatenated together to output the classification probability through a classifier. The second model improves the first by capturing the contextual order information of the sampled blocks with a recurrent neural network. The third model is inspired by the recurrent attention model (RAM), in which a reinforcement learning module is introduced to act as a controller for selecting the next block position based on the recurrent state. Experiments on our collected four-class arXiv paper dataset show that the three proposed models all perform well, and the RAM model achieves the best test accuracy with the least information. Full article
►▼ Show Figures

Figure 1

Figure 1
<p>Model convolutional neural networks (CNN)_Random_Agg architecture.</p> Full article ">Figure 2
<p>Long–short term memory (LSTM) node.</p> Full article ">Figure 3
<p>Model CNN_LSTM_AGG architecture.</p> Full article ">Figure 4
<p>Model CNN_RAM_Agg architecture. RAM—recurrent attention model.</p> Full article ">Figure 5
<p>Experimental results of these models (ACC is the accuracy of classification): (<b>a</b>) Fixing the number of extracted words to 1000, vary the window size; (<b>b</b>) Fixing the window size to 40 words, vary the total number of extracted words.</p> Full article ">
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-20
Previous Issue
Next Issue
Back to TopTop