The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] graph(1418hit)

161-180hit(1418hit)

  • Wireless Power Transfer in the Radiative Near-Field Using a Novel Reconfigurable Holographic Metasurface Aperture Open Access

    Wenyu LUO  

     
    LETTER-Power Transmission

      Vol:
    E102-A No:12
      Page(s):
    1928-1931

    In this letter, we propose a novel wireless power transfer (WPT) scheme in the radiative near-field (Fresnel) region, which based on machine vision and dynamically reconfigurable holographic metasurface aperture capable of focusing power to multiple spots simultaneously without any information feedback. The states of metamaterial elements, formed by tunable meander line resonators, is determined using holographic design principles, in which the interference pattern of reference mode and the desired radiated field pattern leads to the required phase distribution over the surface of the aperture. The three-dimensional position information of mobile point sources is determined by machine visual localization, which can be used to obtain the aperture field. In contrast to the existing research studies, the proposed scheme is not only designed to achieve free multi-focuses, but also with machine vision, low-dimensionality, high transmission efficiency, real-time continuous reconfigurability and so on. The accuracy of the analysis is confirmed using numerical simulation.

  • Sampling Shape Contours Using Optimization over a Geometric Graph

    Kazuya OSE  Kazunori IWATA  Nobuo SUEMATSU  

     
    PAPER-Pattern Recognition

      Pubricized:
    2019/09/11
      Vol:
    E102-D No:12
      Page(s):
    2547-2556

    Consider selecting points on a contour in the x-y plane. In shape analysis, this is frequently referred to as contour sampling. It is important to select the points such that they effectively represent the shape of the contour. Generally, the stroke order and number of strokes are informative for that purpose. Several effective methods exist for sampling contours drawn with a certain stroke order and number of strokes, such as the English alphabet or Arabic figures. However, many contours entail an uncertain stroke order and number of strokes, such as pictures of symbols, and little research has focused on methods for sampling such contours. This is because selecting the points in this case typically requires a large computational cost to check all the possible choices. In this paper, we present a sampling method that is useful regardless of whether the contours are drawn with a certain stroke order and number of strokes or not. Our sampling method thereby expands the application possibilities of contour processing. We formulate contour sampling as a discrete optimization problem that can be solved using a type of direct search. Based on a geometric graph whose vertices are the points and whose edges form rectangles, we construct an effective objective function for the problem. Using different shape datasets, we demonstrate that our sampling method is effective with respect to shape representation and retrieval.

  • An Exact Algorithm for the Arrow Placement Problem in Directed Graph Drawings

    Naoto KIDO  Sumio MASUDA  Kazuaki YAMAGUCHI  

     
    PAPER-Algorithms and Data Structures

      Vol:
    E102-A No:11
      Page(s):
    1481-1489

    We consider the problem of placing arrows, which indicate the direction of each edge in directed graph drawings, without making them overlap other arrows, vertices and edges as much as possible. The following two methods have been proposed for this problem. One is an exact algorithm for the case in which the position of each arrow is restricted to some discrete points. The other is a heuristic algorithm for the case in which the arrow is allowed to move continuously on each edge. In this paper, we assume that the arrow positions are not restricted to discrete points and propose an exact algorithm for the problem of finding an arrow placement such that (a) the weighted sum of the numbers of overlaps with edges, vertices and other arrows is minimized and (b) the sum of the distances between the arrows and their edges' terminal vertices is minimized as a secondary objective. The proposed method solves this problem by reducing it to a mixed integer linear programming problem. Since this is an exponential time algorithm, we add a simple procedure as preprocessing to reduce the running time. Experimental results show that the proposed method can find a better arrow placement than the previous methods and the procedure for reducing the running time is effective.

  • Rootkit inside GPU Kernel Execution

    Ohmin KWON  Hyun KWON  Hyunsoo YOON  

     
    LETTER-Dependable Computing

      Pubricized:
    2019/08/19
      Vol:
    E102-D No:11
      Page(s):
    2261-2264

    We propose a rootkit installation method inside a GPU kernel execution process which works through GPU context manipulation. In GPU-based applications such as deep learning computations and cryptographic operations, the proposed method uses the feature by which the execution flow of the GPU kernel obeys the GPU context information in GPU memory. The proposed method consists of two key ideas. The first is GPU code manipulation, which is able to hijack the execution flow of the original GPU kernel to execute an injected payload without affecting the original GPU computation result. The second is a self-page-table update execution during which the GPU kernel updates its page table to access any location in system memory. After the installation, the malicious payload is executed only in the GPU kernel, and any no evidence remains in system memory. Thus, it cannot be detected by conventional rootkit detection methods.

  • Synchronized Tracking in Multiple Omnidirectional Cameras with Overlapping View

    Houari SABIRIN  Hitoshi NISHIMURA  Sei NAITO  

     
    PAPER-Image Recognition, Computer Vision

      Pubricized:
    2019/07/24
      Vol:
    E102-D No:11
      Page(s):
    2221-2229

    A multi-camera setup for a surveillance system enables a larger coverage area, especially when a single camera has limited monitoring capability due to certain obstacles. Therefore, for large-scale coverage, multiple cameras are the best option. In this paper, we present a method for detecting multiple objects using several cameras with large overlapping views as this allows synchronization of object identification from a number of views. The proposed method uses a graph structure that is robust enough to represent any detected moving objects by defining their vertices and edges to determine their relationships. By evaluating these object features, represented as a set of attributes in a graph, we can perform lightweight multiple object detection using several cameras, as well as performing object tracking within each camera's field of view and between two cameras. By evaluating each vertex hierarchically as a subgraph, we can further observe the features of the detected object and perform automatic separation of occluding objects. Experimental results show that the proposed method would improve the accuracy of object tracking by reducing the occurrences of incorrect identification compared to individual camera-based tracking.

  • High Noise Tolerant R-Peak Detection Method Based on Deep Convolution Neural Network

    Menghan JIA  Feiteng LI  Zhijian CHEN  Xiaoyan XIANG  Xiaolang YAN  

     
    LETTER-Biological Engineering

      Pubricized:
    2019/08/02
      Vol:
    E102-D No:11
      Page(s):
    2272-2275

    An R-peak detection method with a high noise tolerance is presented in this paper. This method utilizes a customized deep convolution neural network (DCNN) to extract morphological and temporal features from sliced electrocardiogram (ECG) signals. The proposed network adopts multiple parallel dilated convolution layers to analyze features from diverse fields of view. A sliding window slices the original ECG signals into segments, and then the network calculates one segment at a time and outputs every point's probability of belonging to the R-peak regions. After a binarization and a deburring operation, the occurrence time of the R-peaks can be located. Experimental results based on the MIT-BIH database show that the R-peak detection accuracies can be significantly improved under high intensity of the electrode motion artifact or muscle artifact noise, which reveals a higher performance than state-of-the-art methods.

  • Protograph-Based LDPC Coded System for Position Errors in Racetrack Memories

    Ryo SHIBATA  Gou HOSOYA  Hiroyuki YASHIMA  

     
    PAPER-Coding Theory

      Vol:
    E102-A No:10
      Page(s):
    1340-1350

    In racetrack memories (RM), a position error (insertion or deletion error) results from unstable data reading. For position errors in RM with multiple read-heads (RHs), we propose a protograph-based LDPC coded system specified by a protograph and a protograph-aware permutation. The protograph-aware permutation facilitates the design and analysis of the coded system. By solving a multi-objective optimization problem, the coded system attains the properties of fast convergence decoding, a good decoding threshold, and a linear minimum distance growth. In addition, the coded system can adapt to varying numbers of RHs without any modification. The asymptotic decoding thresholds with a limited number of iterations verify the good properties of the system. Furthermore, for varying numbers of RHs, the simulation results with both small and large number of iterations, exhibit excellent decoding performances, both with short and long block lengths, and without error floors.

  • An Efficient Parallel Triangle Enumeration on the MapReduce Framework

    Hongyeon KIM  Jun-Ki MIN  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2019/07/11
      Vol:
    E102-D No:10
      Page(s):
    1902-1915

    A triangle enumerating problem is one of fundamental problems of graph data. Although several triangle enumerating algorithms based on MapReduce have been proposed, they still suffer from generating a lot of intermediate data. In this paper, we propose the efficient MapReduce algorithms to enumerate every triangle in the massive graph based on a vertex partition. Since a triangle is composed of an edge and a wedge, our algorithms check the existence of an edge connecting the end-nodes of each wedge. To generate every triangle from a graph in parallel, we first split a graph into several vertex partitions and group the edges and wedges in the graph for each pair of vertex partitions. Then, we form the triangles appearing in each group. Furthermore, to enhance the performance of our algorithm, we remove the duplicated wedges existing in several groups. Our experimental evaluation shows the performance of our proposed algorithm is better than that of the state-of-the-art algorithm in diverse environments.

  • Scalable Community Identification with Manifold Learning on Speaker I-Vector Space

    Hongcui WANG  Shanshan LIU  Di JIN  Lantian LI  Jianwu DANG  

     
    PAPER-Artificial Intelligence, Data Mining

      Pubricized:
    2019/07/10
      Vol:
    E102-D No:10
      Page(s):
    2004-2012

    Recognizing the different segments of speech belonging to the same speaker is an important speech analysis task in various applications. Recent works have shown that there was an underlying manifold on which speaker utterances live in the model-parameter space. However, most speaker clustering methods work on the Euclidean space, and hence often fail to discover the intrinsic geometrical structure of the data space and fail to use such kind of features. For this problem, we consider to convert the speaker i-vector representation of utterances in the Euclidean space into a network structure constructed based on the local (k) nearest neighbor relationship of these signals. We then propose an efficient community detection model on the speaker content network for clustering signals. The new model is based on the probabilistic community memberships, and is further refined with the idea that: if two connected nodes have a high similarity, their community membership distributions in the model should be made close. This refinement enhances the local invariance assumption, and thus better respects the structure of the underlying manifold than the existing community detection methods. Some experiments are conducted on graphs built from two Chinese speech databases and a NIST 2008 Speaker Recognition Evaluations (SREs). The results provided the insight into the structure of the speakers present in the data and also confirmed the effectiveness of the proposed new method. Our new method yields better performance compared to with the other state-of-the-art clustering algorithms. Metrics for constructing speaker content graph is also discussed.

  • A Hybrid CRBP-VMP Cooperative Positioning Algorithm for Distributed Multi-UAVs

    Lu LU  Guangxia LI  Tianwei LIU  Siming LI  Shiwei TIAN  

     
    PAPER

      Pubricized:
    2019/04/26
      Vol:
    E102-B No:10
      Page(s):
    1933-1940

    Positioning information plays a significant role in multi-unmanned aerial vehicles (UAVs) applications. Traditionally, the positioning information is widely provided by Global Navigation Satellite System (GNSS) due to its good performance and global coverage. However, owing to complicated flight environment or signal blockage, jamming and unintentional interference, the UAVs may fail to locate themselves by using GNSS alone. As a new method to resolve these problems, cooperative positioning, by incorporating peer-to-peer range measurements and assisted information, has attracted more and more attentions due to its ability to enhance the accuracy and availability of positioning. However, achieving good performance of cooperative positioning of multi-UAVs is challenging as their mobility, arbitrary nonlinear state-evolution, measurement models and limited computation and communication resources. In this paper, we present a factor graph (FG) representation and message passing methodology to solve cooperative positioning problem among UAVs in 3-dimensional environment where GNSS cannot provide services. Moreover, to deal with the nonlinear state-evolution and measurement models while decreasing the computation complexity and communication cost, we develop a distributed algorithm for dynamic and hybrid UAVs by means of Spherical-Radial Cubature Rules (CR) method with belief propagation (BP) and variational message passing (VMP) methods (CRBP-VMP) on the FG. The proposed CRBP deals with the highly non-linear state-evolution models and non-Gaussian distributions, the VMP method is employed for ranging message, gets the simpler message representation and can reduce communication cost in the joint estimation problem. Simulation results demonstrate that the higher positioning accuracy, the better convergence as well as low computational complexity and communication cost of the proposed CRBP-VMP algorithm, which can be achieved compared with sum-product algorithm over a wireless network (SPAWN) and traditional Cubature Kalman Filters (CKF) method.

  • A Hypergraph Matching Labeled Multi-Bernoulli Filter for Group Targets Tracking Open Access

    Haoyang YU  Wei AN  Ran ZHU  Ruibin GUO  

     
    LETTER-Image Recognition, Computer Vision

      Pubricized:
    2019/07/01
      Vol:
    E102-D No:10
      Page(s):
    2077-2081

    This paper addresses the association problem of tracking closely spaced targets in group or formation. In the Labeled Multi-Bernoulli Filter (LMB), the weight of a hypothesis is directly affected by the distance between prediction and measurement. This may generate false associations when dealing with the closely spaced multiple targets. Thus we consider utilizing structure information among the group or formation. Since, the relative position relation of the targets in group or formation varies slightly within a short time, the targets are considered as nodes of a topological structure. Then the position relation among the targets is modeled as a hypergraph. The hypergraph matching method is used to resolve the association matrix. At last, with the structure prior information introduced, the new joint cost matrix is re-derived to generate hypotheses, and the filtering recursion is implemented in a Gaussian mixture way. The simulation results show that the proposed algorithm can effectively deal with group targets and is superior to the LMB filter in tracking precision and accuracy.

  • Revisiting the Top-Down Computation of BDD of Spanning Trees of a Graph and Its Tutte Polynomial Open Access

    Farley Soares OLIVEIRA  Hidefumi HIRAISHI  Hiroshi IMAI  

     
    PAPER-Graph algorithms

      Vol:
    E102-A No:9
      Page(s):
    1022-1027

    Revisiting the Sekine-Imai-Tani top-down algorithm to compute the BDD of all spanning trees and the Tutte polynomial of a given graph, we explicitly analyze the Fixed-Parameter Tractable (FPT) time complexity with respect to its (proper) pathwidth, pw (ppw), and obtain a bound of O*(Bellmin{pw}+1,ppw}), where Belln denotes the n-th Bell number, defined as the number of partitions of a set of n elements. We further investigate the case of complete graphs in terms of Bell numbers and related combinatorics, obtaining a time complexity bound of Belln-O(n/log n).

  • Acute Constraints in Straight-Line Drawings of Planar Graphs

    Akane SETO  Aleksandar SHURBEVSKI  Hiroshi NAGAMOCHI  Peter EADES  

     
    PAPER-Graph algorithms

      Vol:
    E102-A No:9
      Page(s):
    994-1001

    Recent research on graph drawing focuses on Right-Angle-Crossing (RAC) drawings of 1-plane graphs, where each edge is drawn as a straight line and two crossing edges only intersect at right angles. We give a transformation from a restricted case of the RAC drawing problem to a problem of finding a straight-line drawing of a maximal plane graph where some angles are required to be acute. For a restricted version of the latter problem, we show necessary and sufficient conditions for such a drawing to exist, and design an O(n2)-time algorithm that given an n-vertex plane graph produces a desired drawing of the graph or reports that none exists.

  • Forbidden Subgraphs Generating Almost All Claw-Free Graphs with High Connectivity

    Michitaka FURUYA  Maho YOKOTA  

     
    PAPER-Graph algorithms

      Vol:
    E102-A No:9
      Page(s):
    987-993

    For a family H of connected graphs and an integer k≥1, let Gk(H) denote the family of k-connected graphs which contain no element of H as an induced subgraph. Let H+ be the family of those connected graphs of order 5 which contain K1,3 as an induced subgraph. In this paper, for each integer k≥1, we characterize the families H⊆H+ such that the symmetric difference of Gk(K1,3) and Gk(H) is finite.

  • A Fully-Connected Ising Model Embedding Method and Its Evaluation for CMOS Annealing Machines

    Daisuke OKU  Kotaro TERADA  Masato HAYASHI  Masanao YAMAOKA  Shu TANAKA  Nozomu TOGAWA  

     
    PAPER-Fundamentals of Information Systems

      Pubricized:
    2019/06/10
      Vol:
    E102-D No:9
      Page(s):
    1696-1706

    Combinatorial optimization problems with a large solution space are difficult to solve just using von Neumann computers. Ising machines or annealing machines have been developed to tackle these problems as a promising Non-von Neumann computer. In order to use these annealing machines, every combinatorial optimization problem is mapped onto the physical Ising model, which consists of spins, interactions between them, and their external magnetic fields. Then the annealing machines operate so as to search the ground state of the physical Ising model, which corresponds to the optimal solution of the original combinatorial optimization problem. A combinatorial optimization problem can be firstly described by an ideal fully-connected Ising model but it is very hard to embed it onto the physical Ising model topology of a particular annealing machine, which causes one of the largest issues in annealing machines. In this paper, we propose a fully-connected Ising model embedding method targeting for CMOS annealing machine. The key idea is that the proposed method replicates every logical spin in a fully-connected Ising model and embeds each logical spin onto the physical spins with the same chain length. Experimental results through an actual combinatorial problem show that the proposed method obtains spin embeddings superior to the conventional de facto standard method, in terms of the embedding time and the probability of obtaining a feasible solution.

  • Enumerating Highly-Edge-Connected Spanning Subgraphs

    Katsuhisa YAMANAKA  Yasuko MATSUI  Shin-ichi NAKANO  

     
    PAPER-Graph algorithms

      Vol:
    E102-A No:9
      Page(s):
    1002-1006

    In this paper, we consider the problem of enumerating spanning subgraphs with high edge-connectivity of an input graph. Such subgraphs ensure multiple routes between two vertices. We first present an algorithm that enumerates all the 2-edge-connected spanning subgraphs of a given plane graph with n vertices. The algorithm generates each 2-edge-connected spanning subgraph of the input graph in O(n) time. We next present an algorithm that enumerates all the k-edge-connected spanning subgraphs of a given general graph with m edges. The algorithm generates each k-edge-connected spanning subgraph of the input graph in O(mT) time, where T is the running time to check the k-edge-connectivity of a graph.

  • Explicit Relation between Low-Dimensional LLL-Reduced Bases and Shortest Vectors Open Access

    Kotaro MATSUDA  Atsushi TAKAYASU  Tsuyoshi TAKAGI  

     
    PAPER-Cryptography and Information Security

      Vol:
    E102-A No:9
      Page(s):
    1091-1100

    The Shortest Vector Problem (SVP) is one of the most important lattice problems in computer science and cryptography. The LLL lattice basis reduction algorithm runs in polynomial time and can compute an LLL-reduced basis that provably contains an approximate solution to the SVP. On the other hand, the LLL algorithm in practice tends to solve low-dimensional exact SVPs with high probability, i.e., >99.9%. Filling this theoretical-practical gap would lead to an understanding of the computational hardness of the SVP. In this paper, we try to fill the gap in 3,4 and 5 dimensions and obtain two results. First, we prove that given a 3,4 or 5-dimensional LLL-reduced basis, the shortest vector is one of the basis vectors or it is a limited integer linear combination of the basis vectors. In particular, we construct explicit representations of the shortest vector by using the LLL-reduced basis. Our analysis yields a necessary and sufficient condition for checking whether the output of the LLL algorithm contains the shortest vector or not. Second, we estimate the failure probability that a 3-dimensional random LLL-reduced basis does not contain the shortest vector. The upper bound seems rather tight by comparison with a Monte Carlo simulation.

  • An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs

    Yuichi ASAHIRO  Guohui LIN  Zhilong LIU  Eiji MIYANO  

     
    PAPER-Optimization

      Vol:
    E102-A No:9
      Page(s):
    1142-1149

    In this paper, we investigate the maximum induced matching problem (MaxIM) on C5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C5-free d-regular graphs is $left( rac{3d}{4}- rac{1}{8}+ rac{3}{16d-8} ight)$. In this paper, we design a $left( rac{2d}{3}+ rac{1}{3} ight)$-approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one when d≥6.

  • The Secure Parameters and Efficient Decryption Algorithm for Multivariate Public Key Cryptosystem EFC Open Access

    Yacheng WANG  Yasuhiko IKEMATSU  Dung Hoang DUONG  Tsuyoshi TAKAGI  

     
    PAPER-Cryptography and Information Security

      Vol:
    E102-A No:9
      Page(s):
    1028-1036

    At PQCrypto 2016, Szepieniec et al. proposed a new type of trapdoor called Extension Field Cancellation (EFC) for constructing secure multivariate encryption cryptosystems. They also specifically suggested two schemes EFCp- and EFCpt2- that apply this trapdoor and some modifiers. Although both of them seem to avoid all attacks used for cryptanalysis on multivariate cryptography, their decryption efficiency has room for improvement. On the other hand, their security was analyzed mainly through an algebraic attack of computing the Gröbner basis of the public key, and there possibly exists more effective attacks. In this paper, we introduce a more efficient decryption approach for EFCp- and EFCpt2-, which manages to avoid all redundant computation involved in the original decryption algorithms without altering their public key. In addition, we estimate the secure parameters for EFCp- and EFCpt2- through a hybrid attack of algebraic attack and exhaustive search.

  • Card-Based Physical Zero-Knowledge Proof for Kakuro

    Daiki MIYAHARA  Tatsuya SASAKI  Takaaki MIZUKI  Hideaki SONE  

     
    PAPER-Cryptography and Information Security

      Vol:
    E102-A No:9
      Page(s):
    1072-1078

    Kakuro is a popular logic puzzle, in which a player fills in all empty squares with digits from 1 to 9 so that the sum of digits in each (horizontal or vertical) line is equal to a given number, called a clue, and digits in each line are all different. In 2016, Bultel, Dreier, Dumas, and Lafourcade proposed a physical zero-knowledge proof protocol for Kakuro using a deck of cards; their proposed protocol enables a prover to convince a verifier that the prover knows the solution of a Kakuro puzzle without revealing any information about the solution. One possible drawback of their protocol would be that the protocol is not perfectly extractable, implying that a prover who does not know the solution can convince a verifier with a small probability; therefore, one has to repeat the protocol to make such an error become negligible. In this paper, to overcome this, we design zero-knowledge proof protocols for Kakuro having perfect extractability property. Our improvement relies on the ideas behind the copy protocols in the field of card-based cryptography. By executing our protocols with a real deck of physical playing cards, humans can practically perform an efficient zero-knowledge proof of knowledge for Kakuro.

161-180hit(1418hit)