Given an edge-weighted tree with n vertices and a positive integer L, the length-constrained maximum-density path problem is to find a path of length at least L with maximum density in the tree. The density of a path is the sum of the weights of the edges in the path divided by the number of edges in the path. We present an O(n) time algorithm for the problem. The previously known algorithms run in O(nL) or O(n log n) time.

We previously proposed a query-by-sketch image retrieval system that uses an edge relation histogram (ERH). However, it is difficult for this method to retrieve partial objects from an image, because the ERH is a feature of the entire image, not of each object. Therefore, we propose an object-extraction method that uses edge-based features in order to enable the query-by-sketch system to retrieve partial images. This method is applied to 20,000 images from the Corel Photo Gallery. We confirm that retrieval accuracy is improved by using the edge-based features for extracting objects, enabling the query-by-sketch system to retrieve partial images.

Password-protected secret sharing (PPSS, for short) schemes were proposed by Bagherzandi, Jarecki, Saxena and Lu. In this paper, we consider another attack for PPSS schemes which is based on public parameters and documents. We show that the protocol proposed by Bagherzandi et al. is broken with the attack. We then propose an enhanced protocol which is secure against the attack.

As VLSI process node continue to shrink, chemical mechanical planarization (CMP) process for copper interconnect has become an essential technique for enabling many-layer interconnection. Recently, Edge-over-Erosion error (EoE-error), which originates from overpolishing and could cause yield loss, is observed in various CMP processes, while its mechanism is still unclear. To predict these errors, we propose an EoE-error prediction method that exploits machine learning algorithms. The proposed method consists of (1) error analysis stage, (2) layout parameter extraction stage, (3) model construction stage and (4) prediction stage. In the error analysis and parameter extraction stages, we analyze test chips and identify layout parameters which have an impact on EoE phenomenon. In the model construction stage, we construct a prediction model using the proposed multi-level machine learning method, and do predictions for designed layouts in the prediction stage. Experimental results show that the proposed method attained 2.7∼19.2% accuracy improvement of EoE-error prediction and 0.8∼10.1% improvement of non-EoE-error prediction compared with general machine learning methods. The proposed method makes it possible to prevent unexpected yield loss by recognizing EoE-errors before manufacturing.

An orthogonal ray graph is an intersection graph of horizontal and vertical rays (closed half-lines) in the plane. Such a graph is 3-directional if every vertical ray has the same direction, and 2-directional if every vertical ray has the same direction and every horizontal ray has the same direction. We derive some structural properties of orthogonal ray graphs, and based on these properties, we introduce polynomial-time algorithms that solve the dominating set problem, the induced matching problem, and the strong edge coloring problem for these graphs. We show that for 2-directional orthogonal ray graphs, the dominating set problem can be solved in O(n2 log5 n) time, the weighted dominating set problem can be solved in O(n4 log n) time, and the number of dominating sets of a fixed size can be computed in O(n6 log n) time, where n is the number of vertices in the graph. We also show that for 2-directional orthogonal ray graphs, the weighted induced matching problem and the strong edge coloring problem can be solved in O(n2+m log n) time, where m is the number of edges in the graph. Moreover, we show that for 3-directional orthogonal ray graphs, the induced matching problem can be solved in O(m2) time, the weighted induced matching problem can be solved in O(m4) time, and the strong edge coloring problem can be solved in O(m3) time. We finally show that the weighted induced matching problem can be solved in O(m6) time for orthogonal ray graphs.

In the optimization of decision diagrams, variable reordering approaches are often used to minimize the number of nodes. However, such approaches are less effective for analysis of multi-state systems given by monotone structure functions. Thus, in this paper, we propose algorithms to minimize the number of edges in an edge-valued multi-valued decision diagram (EVMDD) for fast analysis of multi-state systems. The proposed algorithms minimize the number of edges by grouping multi-valued variables into larger-valued variables. By grouping multi-valued variables, we can reduce the number of nodes as well. To show the effectiveness of the proposed algorithms, we compare the proposed algorithms with conventional optimization algorithms based on a variable reordering approach. Experimental results show that the proposed algorithms reduce the number of edges by up to 15% and the number of nodes by up to 47%, compared to the conventional ones. This results in a speed-up of the analysis of multi-state systems by about three times.

This paper presents our project of designing EdgeWrite text entry methods for Japanese language. We are developing a version of EdgeWrite text entry method for Japanese language: Katakana EdgeWrite. Katakana EdgeWrite specifies the line stroke directions and writing order of the Japanese Katakana character. The ideal corner sequence pattern of EdgeWrite for each Katakana character is designed based on its line stroke directions and writing order.

Most images obtained with imaging sensors contain Bayer patterns and suffer from blurring caused by the lens. In order to convert a blurred Bayer-patterned image into a viewable image, demosaicing and deblurring are needed. These concepts have been major research areas in digital image processing for several decades. Despite their importance, their performance and efficiency are not satisfactory when considered independently. In this paper, we propose a joint deblurring and demosaicing method in which edge direction and edge strength are estimated in the Bayer domain and then edge adaptive deblurring and edge-oriented interpolation are performed simultaneously from the estimated edge information. Experimental results show that the proposed method produces better image quality than conventional algorithms in both objective and subjective terms.

For the past couple of decades, the usage of the Web as a platform for deploying software products has become incredibly popular. Web applications became more prevalent, as well as more complex. Countless Web applications have already been designed, developed, tested, and deployed on the Internet. However, it is noticeable that many common functionalities are present among these vast number of applications. This paper proposes an approach based on a database containing information from previous test artifacts. The information is used to generate test scenarios for Web applications under test. We have developed a tool based on our proposed approach, with the aim of reducing the effort required from software test engineers and professionals during the test planning and creation stage of software engineering. We evaluated our approach from three viewpoints: comparison between our approach and manual generation, qualitative evaluation by professional software engineers, and comparison between our approach and two open-source tools.

In the process of production design, engineers usually find it is difficult to seek and reuse others' empirical knowledge which is in the forms of lesson-learned documents. This study proposed a novel approach, which uses a semantic-based topic knowledge map system (STKMS) to support timely and precisely lesson-learned documents finding and reusing. The architecture of STKMS is designed, which has five major functional modules: lesson-learned documents pre-processing, topic extraction, topic relation computation, topic weights computation, and topic knowledge map generation modules. Then STKMS implementation is briefly introduced. We have conducted two sets of experiments to evaluate quality of knowledge map and the performance of utilizing STKMS in outfitting design of a ship-building company. The first experiment shows that knowledge maps generated by STKMS are accepted by domain experts from the evaluation since precision and recall are high. The second experiment shows that STKMS-based group outperforms browse-based group in both learning score and satisfaction level, which are two measurements of performance of utilizing STKMS. The promising results confirm the feasibility of STKMS in helping engineers to find needed lesson-learned documents and reuse related knowledge easily and precisely.

Analysis of the trust network proves beneficial to the users in Online Social Networks (OSNs) for decision-making. Since the construction of trust propagation paths connecting unfamiliar users is the preceding work of trust inference, it is vital to find appropriate trust propagation paths. Most of existing trust network discovery algorithms apply the classical exhausted searching approaches with low efficiency and/or just take into account the factors relating to trust without regard to the role of distrust relationships. To solve the issues, we first analyze the trust discounting operators with structure balance theory and validate the distribution characteristics of balanced transitive triads. Then, Maximum Indirect Referral Belief Search (MIRBS) and Minimum Indirect Functional Uncertainty Search (MIFUS) strategies are proposed and followed by the Optimal Trust Inference Path Search (OTIPS) algorithms accordingly on the basis of the bidirectional versions of Dijkstra's algorithm. The comparative experiments of path search, trust inference and edge sign prediction are performed on the Epinions data set. The experimental results show that the proposed algorithm can find the trust inference path with better efficiency and the found paths have better applicability to trust inference.

How do global warming and agriculture influence each other? It is possible to answer the question by searching knowledge about the relationship between global warming and agriculture. As exemplified by this question, strong demands exist for searching relationships between objects. Mining knowledge about relationships on Wikipedia has been studied. However, it is desired to search more diverse knowledge about relationships on the Web. By utilizing the objects constituting relationships mined from Wikipedia, we propose a new method to search images with surrounding text that include knowledge about relationships on the Web. Experimental results show that our method is effective and applicable in searching knowledge about relationships. We also construct a relationship search system named “Enishi” based on the proposed new method. Enishi supplies a wealth of diverse knowledge including images with surrounding text to help users to understand relationships deeply, by complementarily utilizing knowledge from Wikipedia and the Web.

This paper addresses a high-level synthesis (HLS) using dual-edge-triggered flip-flops (DETFFs) as memory elements. In DETFF-based HLS, the duty cycle becomes a manageable resource to improve the timing performance. To utilize the duty cycle radically, a programmable duty cycle (PDC) mechanism is built into this HLS, and captured by a new HLS task named PDC scheduling. As a first step toward DETFF-based HLS with PDC, the execution time minimization problem is formulated for given results of operation scheduling. A linear program is presented to solve this problem in polynomial time. As a next step, simultaneous operation scheduling and PDC scheduling problem for the same objective is tackled. A mixed integer linear programming-based (MILP) approach is presented to solve this problem. The experimental results show that the MILP can reduce the execution time for several benchmarks.

We propose a new face relighting method using an illuminance template generated from a single reference portrait. First, the reference is wrapped according to the shape of the target. Second, we employ a new spatially variant edge-preserving smoothing filter to remove the facial identity and texture details of the wrapped reference, and obtain the illumination template. Finally, we relight the target with the template in CIELAB color space. Experiments show the effectiveness of our method for both grayscale and color faces taken from different databases, and the comparisons with previous works demonstrate a better relighting effect produced by our method.

Considering the non-linear properties of the human visual system, many non-linear operators and models have been developed, particularly the logarithmic image processing (LIP) model proposed by Jourlin and Pinoli, which has been proved to be physically justified in several laws of the human visual system and has been successfully applied in image processing areas. Recently, several modifications based on this logarithmic mathematical framework have been presented, such as parameterized logarithmic image processing (PLIP), pseudo-logarithmic image processing, homomorphic logarithmic image processing. In this paper, a new single parameter logarithmic model for image processing with an adaptive parameter-based Sobel edge detection algorithm is presented. On the basis of analyzing the distributive law, the subtractive law, and the isomorphic property of the PLIP model, the five parameters in PLIP are replaced by a single parameter to ensure the completeness of the model and physical constancy with the nature of an image, and then an adaptive parameter-based Sobel edge detection algorithm is proposed. By using an image noise estimation method to evaluate the noise level of image, the adaptive parameter in the single parameter LIP model is calculated based on the noise level and grayscale value of a corresponding image area, followed by the single-parameter LIP-based Sobel operation to overcome the noise-sensitive problem of classical LIP-based Sobel edge detection methods, especially in the dark area of an image, while retaining edge sensitivity. Compared with the classical LIP and PLIP model, the given single parameter LIP achieves satisfactory results in noise suppression and edge accuracy.

In tooth contour extraction there is insufficient intensity difference in x-ray images between the tooth and dental bone. This difference must be enhanced in order to improve the accuracy of tooth segmentation. This paper proposes a method to improve the intensity between the tooth and dental bone. This method consists of an estimation of tooth orientation (intensity projection, smoothing filter, and peak detection) and PCA-Stacked Gabor with ellipse Gabor banks. Tooth orientation estimation is performed to determine the angle of a single oriented tooth. PCA-Stacked Gabor with ellipse Gabor banks is then used, in particular to enhance the border between the tooth and dental bone. Finally, active contour extraction is performed in order to determine tooth contour. In the experiment, in comparison with the conventional active contour without edge (ACWE) method, the average mean square error (MSE) values of extracted tooth contour points are reduced from 26.93% and 16.02% to 19.07% and 13.42% for tooth x-ray type I and type H images, respectively.

Considering the real existent fact of the ideal edge and the learning style of image analogy without reference parameters, a blind image recovery algorithm using a self-adaptive learning method is proposed in this paper. We show that a specific local image patch with degradation characteristic can be utilized for restoring the whole image. In the training process, a clear counterpart of the local image patch is constructed based on the ideal edge assumption so that identification of the Point Spread Function is no longer needed. Experiments demonstrate the effectiveness of the proposed method on remote sensing images.

This paper proposes a new double-edge-triggered implicitly level-converting flip-flop, suitable for a low-power and low-voltage design. The design employs a sense amplifier architecture to reduce the delay and power consumption. Experimentally, when implemented with a 130-nm, single-Vt and 0.84V VDD process, it achieves 64% power-delay product (PDP) improvement, and moreover, 78% PDP improvement when implemented with a mixed-Vt technology, as compared to that of the classic double-edge-triggered flip-flop design.

A method of frame synchronization between the color video and depth-map video for depth based 3D video using edge coherence is proposed. We find a synchronized pair of frames using edge coherence by computing the maximum number of overlapped edge pixels between the color video and depth-map video in regions of temporal frame difference. The experimental results show that the proposed method can be used for synchronization of depth-based 3D video and that it is robust against Gaussian noise with σ = less than 30 and video compression by H.264/AVC with QP = less than 44.

We propose a novel method for knowledge consolidation based on a knowledge graph as a next step in relation extraction from text. The knowledge consolidation method consists of entity consolidation and relation consolidation. During the entity consolidation process, identical entities are found and merged using both name similarity and relation similarity measures. In the relation consolidation process, incorrect relations are removed using cardinality properties, temporal information and relation weight in given graph structure. In our experiment, we could generate compact and clean knowledge graphs where number of entities and relations are reduced by 6.1% and by 17.4% respectively with increasing relation accuracy from 77.0% to 85.5%.