A robust approach for the single machine scheduling problem

This paper describes a robust approach for the single machine scheduling problem 1|r _i |L _max. The method is said to be robust since it characterizes a large set of optimal solutions allowing to switch from one solution to another, without any performance loss, in order to face potential disruptions which occur during the schedule execution. It is based on a dominance theorem that characterizes a set of dominant sequences, using the interval structure defined by the relative order of the release and the due dates of jobs. The performance of a set of dominant sequences can be determined in polynomial time by computing the most favorable and the most unfavorable sequences associated with each job, with regard to the lateness criterion. A branch and bound procedure is proposed which modifies the interval structure of the problem in order to tighten the dominant set of sequences so that only the optimal sequences are conserved.     

一种适用于纹理图象的FIRE滤波器

对于图象滤波系统,如何在降噪的同时保护细节结构是一个难点。文章提出一种新的FIRE（fuzzy inference ruled by else－action）滤波器,通过将对应于不同邻域尺寸下的象素分布模式的模糊规则集成在同一规则基中,将多分辨率图象分析引入到单一模块内。实验表明该方法对纹理图象的去噪效果明显。     

Hierarchical image fusion

A hierarchical image fusion scheme is presented that preserves those details from the input images that are most relevant to visual perception. Results show that fused images present a more detailed representation of the scene and provide information that cannot be obtained by viewing the input images separately. Detection, recognition, and search tasks may therefore benefit from this fused image representation.     

A fast technique for recursive scene matching using pyramids

An algorithm of a fast correlation technique for scene matching using pyramidal image representation is introduced. A mathematical model of the image registration process based on the pyramidal representation of a separable Markov random field is considered in order to evaluate threshold sequence for the algorithm. Experimental results are presented for matching images, both free of noise and corrupted by noise. Theoretical and experimental results given in the paper show that computational efficiency in scene matching could be improved in three orders of magnitude comparatively to the traditional correlation technique.     

VARIANT: A System for Terrain Modeling at Variable Resolution

We describe VARIANT (VAriable Resolution Interactive ANalysis of Terrain), an extensible system for processing and visualizing terrains represented through Triangulated Irregular Networks (TINs), featuring the accuracy of the representation, possibly variable over the terrain domain, as a further parameter in computation.VARIANT is based on a multiresolution terrain model, which we developed in our earlier research. Its architecture is made of a kernel, which provides primitive operations for building and querying the multiresolution model; and of application programs, which access a terrain model based on the primitives in the kernel.VARIANT directly supports basic queries (e.g., windowing, buffering, computation of elevation at a given point, or along a given line) as well as high-level operations (e.g., fly-over visualization, contour map extraction, viewshed analysis). However, the true power of VARIANT lies in the possibility of extending it with new applications that can exploit its multiresolution features in a transparent way.     

SML: A structured musical language

Most of the problems with existing computer musicological systems have to do with the lack of capability for capturing the important notion of musical structure. In the new language SML (AStructuredMusicalLanguage), this aspect is given foremost attention as a technique for encoding a musical score in a clear and vivid form. Musical structures are patterned after the control structures of Pascal, together with instrument representations modeled on the idea of a Pascal record type. A complete example of the SML encoding of a Schumann song is included.Ronald E. Prather is the Caruth Distinguished Professor of Computer Science at Trinity University, San Antonio, Texas 78284. Stephen Elliott is a doctoral candidate in Computer Science at the University of Colorado, Boulder, Colorado 80309.     

A Wavelet-Based Multiresolution Method to Automatically Register Images

We present a method to automatically register images presenting bothglobal and local deformations. The image registration process isperformed by exploiting a multi-level/multi-image approach wherebyafter having wavelet-transformed the images, the subband images atdifferent levels are used in a non-feature-based way to determine themotion vectors between the reference and the target images. The crudemotion field determined by block matching at the coarsest level ofthe pyramid is successively refined by taking advantage of both theorientation sensitivity of the different subbands and thecontribution of the adjacent levels. The final registered image isobtained by applying the motion field to the lowest level of thepyramid and by inversely transforming it.     

The Applications of Wavelets in Hierarchical Representations and Smoothing of Curves and Surfaces

ＴｈｅＡｐｐｌｉｃａｔｉｏｎｓｏｆＷａｖｅｌｅｔｓｉｎＨｉｅｒａｒｃｈｉｃａｌＲｅｐｒｅｓｅｎｔａｔｉｏｎｓａｎｄＳｍｏｏｔｈｉｎｇｏｆＣｕｒｖｅｓａｎｄＳｕｒｆａｃｅｓ①ＳｕｎＹａｎｋｕｉＺｈｕＸｉｎｘｉｏｎｇＭａＬｉｎｇＢｅｉｊｉｎｇＵｎｖｉｅｒ...     

BOXTREE: A Hierarchical Representation for Surfaces in 3D

We introduce the boxtree, a versatile data structure for representing triangulated or meshed surfaces in 3D. A boxtree is a hierarchical structure of nested boxes that supports efficient ray tracing and collision detection. It is simple and robust, and requires minimal space. In situations where storage is at a premium, boxtrees are effective alternatives to octrees and BSP trees. They are also more flexible and efficient than R-trees, and nearly as simple to implement.     

The development of an enterprise resources planning system using a hierarchical design pyramid

Today, manufacturers are measured by their ability to respond quickly to sudden, often unpredictable changes in customer needs and wants. Competition beyond the twenty-first century places an increased emphasis upon receiving business information that is accurate and up to date. In order to achieve this, a business planning and closed-loop manufacturing execution system must reflect how work is done, in order to support the overall business objectives without being limited by any hardware, software and human resource constraints. Enterprise resources planning (ERP) is considered to be the most effective computer application in the modern manufacturing industry which meets these requirements. However, only a few manufacturers can design and implement the system successfully. They encounter various problems during the design and implementation cycle. One of the major reasons why they cannot implement the system successfully is the inappropriate use of design and implementation methodology. A systematic design and implementation methodology is therefore proposed for ERP. Called the hierarchical design pyramid (HDP), it encompasses recent research on the ICAM definition method (IDEF) and the object-oriented methodology (OOM) as well as an architecture for any manufacturers who seriously consider ERP implementation.     

Hierarchical control of discrete-event systems

An abstract hierarchical control theory is developed for discrete-event systems, based on the concepts of control structures and observers. Control structure is an abstract generalization of the family of controllable sublanguages in the Ramadge-Wonham framework. We establish a general version of Zhong's hierarchical consistency by first achieving control consistency — preservation of control structures through the aggregation mapping in a two-level hierarchy. For a refinement of hierarchical consistency with preservation of nonblocking, the concept of observer is introduced via congruences on nondeterministic transition structures.     

Multidimensional Morphable Models: A Framework for Representing and Matching Object Classes

We describe a flexible model for representing images of objects of a certain class, known a priori, such as faces, and introduce a new algorithm for matching it to a novel image and thereby perform image analysis. The flexible model, known as a multidimensional morphable model, is learned from example images of objects of a class. In this paper we introduce an effective stochastic gradient descent algorithm that automatically matches a model to a novel image. Several experiments demonstrate the robustness and the broad range of applicability of morphable models. Our approach can provide novel solutions to several vision tasks, including the computation of image correspondence, object verification and image compression.     

Image decomposition on the basis of an inverse pyramid with 3-layer neural networks

The contemporary information technologies and Internet impose high requirements on the image compression efficiency. Great number of methods for information redundancy reduction had already been developed, which are based on the image processing in the spatial or spectrum domain. Other methods for image compression use some kinds of neural networks. In spite of their potentialities, the methods from the last group do not offer high compression efficiency. New adaptive method for image decomposition on the basis of an inverse pyramid with neural networks is presented in this paper. The processed image is divided in blocks and then each is compressed in the space of the hidden layers of 3-layer BPNNs, which build the so-called inverse difference pyramid. The results of the new method modeling are presented for sequence of static images in comparison with results for single images from the same group.     

Mod-2-OBDDs—A data structure that generalizes EXOR-sum-of-products and ordered binary decision diagrams

We present a data structure for Boolean manipulation-the Mod-2-OBDDs-that considerably extends ESOPs (EXOR-sum-of-products) as well as OBDDs (ordered binary decision diagrams). There are Boolean functions of practical interest which have exponential size optimal ESOPs (even multilevel EXOR-expressions) and/or OBDDs that can be represented by (low degree) polynomial size Mod-2-OBDDs. We show that Boolean manipulation tasks such as apply operation, quantification, composition can be performed with Mod-2-OBDDs at least as efficient as with OBDDs. Indeed, since the size of a minimal Mod-2-OBDD-representation of a Boolean function is, in general, smaller (sometimes even exponentially smaller) than the size of an optimal OBDD-representation, the increase in efficiency is considerable. Moreover, EXOR-operations as well as complementations can be performed in constant timeO (1). However, the price of constant time EXOR-apply operations is the canonicity of the Mod-2-OBDD-representation. In order to allow in spite of this fact efficient analysis of Mod-2-OBDDs we present a fast probabilistic equivalence test with one-sided error probability for Mod-2-OBDDs (and, hence, for ESOPs) which performs only linear many arithmetic operations.     

A real-time computer controller for a Robotic Filament Winding system

This paper presents an integrated real-time control system for a Robotic Filament Winding manufacturing cell. The architecture is based on a multiprocessor system employing four processor boards. The system incorporates a hierarchical control layout with the task specification at the highest level and the robot and winder set point tracking at the lowest. Eventual design goals include a PC front-end unit capable of winding path generation and testing prior to actual part production. Preliminary experimental results on cylindrical, elbow and T-shaped pipe-fittings are included.     

A data dependence test based on the projection of paths over shape graphs

We propose a data dependence detection test based on a new conflict analysis algorithm for C codes which make intensive use of recursive data structures dynamically allocated in the heap. This algorithm requires two pieces of information from the code section under analysis (a loop or a recursive function): (i) abstract shape graphs that represent the state of the heap at the code section; and (ii) path expressions that collect the traversing information for each statement. Our algorithm projects the path expressions on the shape graphs and checks over the graphs to ascertain whether one of the sites reached by a write statement matches one of the sites reached by another statement on a different loop iteration (or on a different call instance in a recursive function), in which case a conflict between the two statements is reported. Although our algorithm presents exponential complexity, we have found that in practice the parameters that dominate the computational cost have very low values, and to the best of our knowledge, all the other related studies involve higher costs. In fact, our experimental results show reductions in the data dependence analysis times of one or two orders of magnitude in some of the studied benchmarks when compared to a previous data dependence algorithm. Thanks to the information on uncovered data dependences, we have manually parallelized these codes, achieving speedups of 2.19 to 3.99 in four cores.     

层次化区域匹配指导的视频颜色迁移

提出了一种基于层次化结构的视频颜色迁移方法。利用层次化分割技术对视频帧进行区域分割并将分割区域之间的组织关系用树的形式来描述,形成表示图像组成区域的具有层次化特征的树状结构。通过定义表示图像的树之间的层次化结构的相似性比较方法,对迁移图像之间的局部区域特征进行相似性比较,以寻找目标图像与参考图像局部迁移的最佳区域。在此基础上,利用颜色概率分布迁移的方法在图像的不同区域上进行局部颜色迁移以实现保持目标图像视觉特征的目的。