Browsing by Author "Yen, Hsu-Chun"

Now showing 1 - 11 of 11

A new force-directed graph drawing method based on edge-edge repulsion
(2012-02-01)
Lin, Chun-Cheng
;
Yen, Hsu-Chun
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
The conventional force-directed methods for drawing undirected graphs are based on either vertex-vertex repulsion or vertex-edge repulsion. In this paper, we propose a new force-directed method based on edge-edge repulsion to draw graphs, In our framework, edges are modelled as charged springs, and a final drawing can be generated by adjusting positions of vertices according to spring forces and the repulsive forces, derived from potential fields, among edges. Different from the previous methods, our new framework has the advantage of overcoming the problem of zero angular resolution, guaranteeing the absence of any overlapping of edges incident to the common vertex. Given graph layouts probably generated by previous algorithms as the inputs to our algorithm, experimental results reveal that our approach produces promising drawings not only preserving the original properties of a high degree of symmetry and uniform edge length, but also preventing zero angular resolution and usually having larger average angular resolution. However, it should be noted that exhibiting a higher degree of symmetry and larger average angular resolution does not come without a price, as the new approach might result in the increase in undesirable overlapping of vertices as some of our experimental results indicate. To ease the problem of node overlapping, we also consider a hybrid approach which takes into account both edge-edge and vertex-vertex repulsive forces in drawing a graph. (C) 2011 Elsevier Ltd. All rights reserved.
A Zone-Based Approach for Placing Annotation Labels on Metro Maps
(2011)
Wu, Hsiang-Yun
;
Takahashi, Shigeo
;
Lin, Chun-Cheng
;
Yen, Hsu-Chun
;
工業工程與管理學系
Hand-drawn metro map illustrations often employ both internal and external labels in a way that they can assign enough information such as textual and image annotations to each landmark. Nonetheless, automatically tailoring the aesthetic layout of both textual and image labels together is still a challenging task, due to the complicated shape of the labeling space available around the metro network. In this paper, we present a zone-based approach for placing such annotation labels so that we can fully enhance the aesthetic criteria of the label arrangement. Our algorithm begins by decomposing the map domain into three different zones where we can limit the position of each label according to its type. The optimal positions of labels of each type are evaluated by referring to the zone segmentation over the map. Finally, a new genetic-based approach is introduced to compute the optimal layout of such annotation labels, where the order in which the labels are embedded into the map is improved through the evolutional computation algorithm. We also equipped a semantic zoom functionality, so that we can freely change the position and scale of the metro map.
Designing and Annotating Metro Maps with Loop Lines
(2015)
Wu, Hsiang-Yun
;
Poon, Sheung-Hung
;
Takahashi, Shigeo
;
Arikawa, Masatoshi
;
Lin, Chun-Cheng
Schematic metro maps provide an effective means of simplifying the geographical configuration of public rapid transportation systems. Nonetheless, travelers still find it difficult to identify routes of a specific topology on the maps because it is usually hidden behind the conventional octilinear layout of the entire map. In this paper, we present an approach to designing schematic maps with loop lines, which are drawn as circles together with annotation labels for guiding different traveling purposes. Our idea here is to formulate the aesthetic criteria as mathematical constraints in the mixed-integer programming model, which allows us to either align stations on the loop line at a grid if they are interchange stations or non-interchange stations on a circle otherwise. We then distribute the annotation labels associated with stations on the loop line evenly to the four side boundary of the map domain in order to make full use of the annotation space, while maximally avoiding intersections between leader lines and the metro network by employing a flow network algorithm. Finally, we present several experimental results generated by our prototype system to demonstrate the feasibility of the proposed approach.
Drawing graphs with nonuniform nodes using potential fields
(2009-12-01)
Lin, Chun-Cheng
;
Yen, Hsu-Chun
;
Chuang, Jen-Hui
;
資訊工程學系
;
Department of Computer Science
Graphs with nonuniform nodes arise naturally in many real-world applications. Although graph drawing has been a very active research in the computer science community during the past decade, most of the graph drawing algorithms developed thus far have been designed for graphs whose nodes are represented as single points. As a result, it is of importance to develop drawing methods for graphs whose nodes are of different sizes and shapes, in order to meet the need of real-world applications. To this end, a potential field approach, coupled with an idea commonly found in force-directed methods, is proposed in this paper for drawing graphs with nonuniform nodes in 2-D and 3-D. In our framework, nonuniform nodes are uniformly charged, while edges are modelled by springs. Using certain techniques developed in the field of potential-based path planning, we are able to find analytically tractable procedures for computing the repulsive force and torque of a node in the potential field induced by the remaining nodes. The crucial feature of our approach is that the rotation of every nonuniform node and the multiple edges between two nonuniform nodes are taken into account. In comparison with the existing algorithms found in the literature, our experimental results suggest this new approach to be promising, as drawings of good quality for a variety of moderate-sized graphs in 2-D and 3-D can be produced reasonably efficiently. That is, our approach is suitable for moderate-sized interactive graphs or larger-sized static graphs. Furthermore, to illustrate the usefulness of our new drawing method for graphs with zero-sized nodes, we give an application to the visualization of hierarchical clustered graphs, for which our method offers a very efficient solution. (C) 2009 Elsevier Ltd. All rights reserved.
Mental map preserving graph drawing using simulated annealing
(2011-10-01)
Lin, Chun-Cheng
;
Lee, Yi-Yi
;
Yen, Hsu-Chun
;
工業工程與管理學系
;
Department of Industrial Engineering and Management
Visualizing graphs has been studied extensively in the community of graph drawing and information visualization over the years. In some applications, the user is required to interact with a graph by making slight changes to the underlying graph structure. To visualize graphs in such an interactive environment, it is desirable that the differences between the displays of the original and the modified graphs be kept minimal, allowing the user to comprehend the changes in the graph structure faster. As the mental map concept refers to the presentation of a person's mind while exploring visual information, the better the mental map is preserved, the easier the structure change of a graph is understood. It is somewhat surprising that preserving the user's mental map has largely been ignored in the graph drawing community in the past. We propose an effective mental-map-preserving graph drawing algorithm for straight-line drawings of general undirected graphs based on the simulated-annealing technique. Our experimental results and questionnaire analysis suggest this new approach to be promising. (C) 2011 Elsevier Inc. All rights reserved.
On Number of Tags Estimation in RFID Systems
(2017-09-01)
Deng, Der-Jiunn
;
Lin, Chun-Cheng
;
Huang, Tzu-Hsun
;
Yen, Hsu-Chun
;
工業工程與管理學系
According to the latest version of the radio-frequency identification (RFID) standard, EPCglobal UHF Gen2, dynamic framed slotted ALOHA has been accepted and employed as the de facto collision resolution algorithm to share the channel usage when multiple tags respond to the reader's signal command simultaneously. However, the frame size in read cycle is usually far from optimal when the reader does not know the number of unidentified tags in its interrogation zone, and this will lead to several performance issues and technical limitations such as power consumption, longer reading time, and degraded system performance. In this paper, we show that the number of unidentified tags can be expressed as a function of the collision rate received by the reader when the reader collects tags' information, and then we use an extended Kalman filter-based tag number estimation algorithm to estimate the number of unidentified tags in an RFID system on run-time measurements. Simulation results show that our scheme provides much better accuracy than existing well-known approaches even in a fast-changing environment.
One-and-a-Half-Side Boundary Labeling
(2011)
Lin, Chun-Cheng
;
Poon, Sheung-Hung
;
Takahashi, Shigeo
;
Wu, Hsiang-Yun
;
Yen, Hsu-Chun
In boundary labeling, each point site in a rectangular map is connected to a label outside the map by a leader, which may be a rectilinear or a straight-line segment. Among various types of leaders, the so-called type-opo leader consists of three segments (from the site to its associated label) that are orthogonal, then parallel, and then orthogonal to the side to which the label is attached. In this paper, we investigate the so-called 1.5-side boundary labeling, in which, in addition to being connected to the right side of the map directly, type-opo leaders can be routed to the left side temporarily and then finally to the right side. It turns out that allowing type-opo leaders to utilize the left side of a map is beneficial in the sense that it produces a better labeling result; in some cases. To understand this new version of boundary labeling better, we investigate from a computational complexity viewpoint the total leader length minimization problem as well as the bend minimization problem for variants of 1.5-side boundary labeling, which are parameterized by the underlying label size (uniform vs. nonuniform) and port type (fixed-ratio, fixed-position, vs. sliding). For the case of nonuniform labels, the above two problems are intractable in general. We are able to devise pseudopolynomial time solutions for such intractable problems, and also identify the role played by the number of distinct labels in the overall complexity. On the other hand, if labels are identical in size, both problems become solvable in polynomial time. We also characterize the cases for which utilizing the left side for routing type-opo leaders does not help.
Optimized Topological Surgery for Unfolding 3D Meshes
(2011-09-01)
Takahashi, Shigeo
;
Wu, Hsiang-Yun
;
Saw, Seow Hui
;
Lin, Chun-Cheng
;
Yen, Hsu-Chun
Constructing a 3D papercraft model from its unfolding has been fun for both children and adults since we can reproduce virtual 3D models in the real world. However, facilitating the papercraft construction process is still a challenging problem, especially when the shape of the input model is complex in the sense that it has large variation in its surface curvature. This paper presents a new heuristic approach to unfolding 3D triangular meshes without any shape distortions, so that we can construct the 3D papercraft models through simple atomic operations for gluing boundary edges around the 2D unfoldings. Our approach is inspired by the concept of topological surgery, where the appearance of boundary edges of the unfolded closed surface can be encoded using a symbolic representation. To fully simplify the papercraft construction process, we developed a genetic-based algorithm for unfolding the 3D mesh into a single connected patch in general, while optimizing the usage of the paper sheet and balance in the shape of that patch. Several examples together with user studies are included to demonstrate that the proposed approach works well for a broad range of 3D triangular meshes.
QoS/QoE Support for H.264/AVC Video Stream in IEEE 802.11ac
(2017-12-01)
Chang, Che-Yu
;
Yen, Hsu-Chun
;
Lin, Chun-Cheng
;
Deng, Der-Jiunn
;
工業工程與管理學系
The H.264 video compression technique enjoys the merit of good video quality with high compression rate; therefore, it has been widely applied in delivering video content. In IEEE 802.11ac wireless local area networks, enhanced distributed channel access (EDCA) is the primarily adopted access control mechanism for multimedia traffic transmission. However, the performance is degraded due to the unpredictable delay caused by its inefficient backoff procedure. To achieve high quality of service/experience, this paper proposes a multipolling controlled access (MPCA) scheme to guarantee the latency in delivering important video frames while reducing transmission overhead. We also propose a cross-layer designed quality adjustment strategy to maximize the visual experience. Furthermore, the downlink multi-user multiple-input-multiple-output feature in IEEE 802.11ac is exploited to enhance the reliability of MPCA. Theoretical analysis is provided to show high efficiency of MPCA. Simulation results indicate that MPCA has higher throughput, lower packet delay, lower packet loss, and higher peak signal-to-noise ratio than the EDCA.
Spatially Efficient Design of Annotated Metro Maps
(2013-06-01)
Wu, Hsiang-Yun
;
Takahashi, Shigeo
;
Hirono, Daichi
;
Arikawa, Masatoshi
;
Lin, Chun-Cheng
Annotating metro maps with thumbnail photographs is a commonly used technique for guiding travelers. However, conventional methods usually suffer from small labeling space around the metro stations especially when they are interchange stations served by two or more metro lines. This paper presents an approach for aesthetically designing schematic metro maps while ensuring effective placement of large annotation labels that are sufficiently close to their corresponding stations. Our idea is to distribute such labels in a well-balanced manner to labeling regions around the metro network first and then adjust the lengths of metro line and leader line segments, which allows us to fully maximize the space coverage of the entire annotated map. This is accomplished by incorporating additional constraints into the conventional mixed-integer programming formulation, while we devised a three-step algorithm for accelerating the overall optimization process. We include several design examples to demonstrate the spatial efficiency of the map layout generated using the proposed approach through minimal user intervention.
Travel-Route-Centered Metro Map Layout and Annotation
(2012-06-01)
Wu, Hsiang-Yun
;
Takahashi, Shigeo
;
Lin, Chun-Cheng
;
Yen, Hsu-Chun
;
交大名義發表
When providing travel guides for a specific route in a metro network, we often place the route around the center of the map and annotate stations on the route with thumbnail photographs. Nonetheless, existing methods do not offer an effective means of customizing the network layout in order to accommodate such large annotation labels while preserving its planar embedding. This paper presents a new approach for designing the metro map layout in order to annotate stations on a specific travel route with large annotation labels. Our idea is to elongate the travel route to be straight along the centerline of the map so that we can systematically annotate such stations with external labels. This is accomplished by extending the conventional mixed-integer programming technique for computing octilinear layouts where orientations inherent to the metro line segments are plausibly rearranged. The stations are then connected with external labels through leaders while minimizing intersections with metro lines for enhancing visual clarity. We present several design examples of metro maps and user studies to demonstrate that the proposed aesthetic criteria successfully direct viewers attention to specific travel routes.