An Algorithm for Minimum Cost Arc-Connectivity Orientations

Given a 2k-edge-connected undirected graph, we consider to find a minimum cost orientation that yields a k-arc-connected directed graph. This minimum cost k-arc-connected orientation problem is a special case of the submodular flow problem. Frank (1982) devised a combinatorial algorithm that solves the problem in O(k ² n ³ m) time, where n and m are the numbers of vertices and edges, respectively. Gabow (1995) improved Frank’s algorithm to run in O(kn ² m) time by introducing a new sophisticated data structure. We describe an algorithm that runs in O(k ³ n ³+kn ² m) time without using sophisticated data structures. In addition, we present an application of the algorithm to find a shortest dijoin in O(n ² m) time, which matches the current best bound.     

Discharge properties and chemical stability of SrZrO films

Abstract— MgO thin film is currently used as a surface protective layer for dielectric materials because MgO has a high resistance during ion sputtering and exhibits effective secondary electron emission. The secondary‐electron‐emission coefficient γ of MgO is high for Ne ions; however, it is low for Xe ions. The Xe content of the discharge gas of PDPs needs to be raised in order to increase the luminous efficiency. Thus, the development of high‐γ materials replacing MgO is required. The discharge properties and chemical surface stability of SrO containing Zr (SrZrO) as the candidate high‐γ protective layer for noble PDPs have been characterized. SrZrO films have superior chemical stability, especially the resistance to carbonation because of the existence of a few adsorption sites due to their amorphous structure. The firing voltage is 60 V lower than that of MgO films for a discharge gas of Ne/Xe = 85/15 at 60 kPa.     

Deformation characteristics of ultra-thin liquid film considering temperature and film thickness dependence of surface tension

Thermocapillary deformations of an ultra-thin liquid film caused by temperature distribution were three-dimensionally analyzed using the unsteady and linearized long wave equation considering the temperature and film thickness dependence of surface tension. The temperature and film thickness dependence equation for the surface tension of a liquid was firstly established. The temperature dependence of the surface tension was obtained experimentally using a surface tensiometer and the film thickness dependence was obtained theoretically from the corrected van der Waals pressure equation for a symmetric multilayer system. Time evolutions of depression and groove of the ultra-thin liquid film caused by local heating were obtained quantitatively.     

A robust automatic crack detection method from noisy concrete surfaces

In maintenance of concrete structures, crack detection is important for the inspection and diagnosis of concrete structures. However, it is difficult to detect cracks automatically. In this paper, we propose a robust automatic crack-detection method from noisy concrete surface images. The proposed method includes two preprocessing steps and two detection steps. The first preprocessing step is a subtraction process using the median filter to remove slight variations like shadings from concrete surface images; only an original image is used in the preprocessing. In the second preprocessing step, a multi-scale line filter with the Hessian matrix is used both to emphasize cracks against blebs or stains and to adapt the width variation of cracks. After the preprocessing, probabilistic relaxation is used to detect cracks coarsely and to prevent noises. It is unnecessary to optimize any parameters in probabilistic relaxation. Finally, using the results from the relaxation process, a locally adaptive thresholding is performed to detect cracks more finely. We evaluate robustness and accuracy of the proposed method quantitatively using 60 actual noisy concrete surface images.     

New pixel driving circuit using self‐discharging compensation method for high‐resolution OLED micro displays on a silicon backplane

A new 4T2C pixel circuit formed on a silicon substrate is proposed to realize a high‐resolution 7.8‐μm pixel pitch AMOLED microdisplay. In order to achieve high luminance uniformity, the pixel circuit compensates its Vth variation of the MOSFET for the driving transistor internally by using self‐discharging method. Also presented are 0.5‐in Quad‐VGA and 1.25‐in wide Quad‐XGA microdisplays with the proposed pixel circuit.     

A preliminary study on learning effect in a contact positioning task in a virtual environment

How the human central nervous system adjusts sensorimotor coordination to haptic stimuli is a major topic in several fields including robotics. There are studies focusing on contact positioning tasks such as catching a ball or a volley in tennis, where position control of a human hand is required only at the moment of contact for successful completion of the tasks. A previous study dealt with a task of catching a ball in a virtual environment, and reported an interesting observation of the learning process in the relationship between operational performance and energy consumption of an operator; however, the operational condition given to the operators in the previous study seemed to be relatively simple. The interest in this paper is similar to that of the previous study; however, this paper considers application of a slightly more complex operational condition to a task of catching a ball. For corresponding to increase of difficulty in operation in the task, two movements of a paddle for catching a ball are given to operators, and difference between the movements is observed. Although the final goal of the study in this paper is similar to that in the previous study, this paper considers how learning effect can be observed in operational performance by comparing the performance of novice operators with that of experienced operators. The comparison shows differences in the performances between the operators from three analytic aspects. This paper also considers how many operations are required for novice operators to exhibit the learning effect in operational performance.     

Implementation of a decision support system using an interactive large-scale high-resolution display

In this research, we propose and evaluate a decision support system using an interactive large-scale high-resolution display. This decision support system supports the summarization and decision-making of a large amount of disaster information during the occurrence of a large-scale natural disaster. Municipal employees at the disaster control headquarters can display disaster information on the large-scale display with a touch or flick on a laptop or tablet. To evaluate the operability, readability, functionality, and necessity of the decision support system, we surveyed 23 municipal employees in the disaster prevention division using a questionnaire. The system received a great evaluation in all the evaluation items.     

An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem

We consider the minimum maximal matching problem, which is NP-hard (Yannakakis and Gavril (1980) [18]). Given an unweighted simple graph G=(V,E), the problem seeks to find a maximal matching of minimum cardinality. It was unknown whether there exists a non-trivial approximation algorithm whose approximation ratio is less than 2 for any simple graph. Recently, Z. Gotthilf et al. (2008) [5] presented a -approximation algorithm, where c is an arbitrary constant.In this paper, we present a -approximation algorithm based on an LP relaxation, where χ^′(G) is the edge-coloring number of G. Our algorithm is the first non-trivial approximation algorithm whose approximation ratio is independent of |V|. Moreover, it is known that the minimum maximal matching problem is equivalent to the edge dominating set problem. Therefore, the edge dominating set problem is also -approximable. From edge-coloring theory, the approximation ratio of our algorithm is , where Δ(G) represents the maximum degree of G. In our algorithm, an LP formulation for the edge dominating set problem is used. Fujito and Nagamochi (2002) [4] showed the integrality gap of the LP formulation for bipartite graphs is at least . Moreover, χ^′(G) is Δ(G) for bipartite graphs. Thus, as far as an approximation algorithm for the minimum maximal matching problem uses the LP formulation, we believe our result is the best possible.     

Direct Ray Tracing of Phong Tessellation

There are two major ways of calculating ray and parametric surface intersections in rendering. The first is through the use of tessellated triangles, and the second is to use parametric surfaces together with numerical methods such as Newton's method. Both methods are computationally expensive and complicated to implement. In this paper, we focus on Phong Tessellation and introduce a simple direct ray tracing method for Phong Tessellation. Our method enables rendering smooth surfaces in a computationally inexpensive yet robust way.     

Real-time CAM-based Hough transform algorithm and its performance evaluation

Abstract. This paper proposes a highly parallel Hough transform algorithm for real-time straight-line extraction and its hardware implementation on a content-addressable memory (CAM). To achieve high-speed processing, incrementation for voting, which composes the Hough transform, and calculations for coordinate updating are carried out for the every scan line, not every edge pixel, and extracting maxima in Hough space is executed by parallel comparing. Moreover, variously weighted voting achieves more accurate line extraction in spite of the quantization error and noise in the image space. In the implementation, the CAM acts as a PE (processing-element) array that effectively performs highly parallel processing for the Hough transform and also as a memory for two-dimensional Hough space, and both voting and peak extraction are directly executed by the CAM. Evaluations of CAM hardware size, processing time and the accuracy of line extraction show that a real-time and high-resolution Hough transform for a 256256 picture can be achieved using a single CAM chip with current VLSI technology. This CAM-based Hough transform algorithm promises to be an important step towards the realization of a real-time and compact image-understanding system. Received: 15 August 1998 / Accepted: 15 March 2000