The essence of eta-expansion in partial evaluation

Selective eta-expansion is a powerful binding-time improvement,i.e., a source-program modification that makes a partial evaluator yield better results. But like most binding-time improvements, the exact problem it solves and the reason why have not been formalized and are only understood by few.In this paper, we describe the problem and the effect of eta-redexes in terms of monovariant binding-time propagation: eta-redexes preserve the static data flow of a source program by interfacingstatic higher-order values in dynamic contexts anddynamic higher-order values in static contexts. They contribute to twodistinct binding-time improvements.We present two extensions of Gomard's monovariant binding-time analysis for the pure -calculus. Our extensions annotateand eta-expand -terms. The first one eta-expands static higher-order values in dynamic contexts. The second also eta-expands dynamic higher-order values in static contexts.As a significant application, we show that our first binding-time analysis suffices to reformulate the traditional formulation of a CPS transformation into a modern one-pass CPS transformer. This binding-time improvement is known, but it is still left unexplained in contemporary literature,e.g., about cps-based partial evaluation.We also outline the counterpart of eta-expansion for partially static data structures.     

Optimizing Web Servers Using Page Rank Prefetching for Clustered Accesses

This paper presents a Page Rank based prefetching technique for accesses to Web page clusters. The approach uses the link structure of a requested page to determine the most important linked pages and to identify the page(s) to be prefetched. The underlying premise of our approach is that in the case of cluster accesses, the next pages requested by users of the Web server are typically based on the current and previous pages requested. Furthermore, if the requested pages have a lot of links to some important page, that page has a higher probability of being the next one requested. An experimental evaluation of the prefetching mechanism is presented using real server logs. The results show that the Page-Rank based scheme does better than random prefetching for clustered accesses, with hit rates of 90% in some cases.     

Determining literariness in interactive fiction

The authors of interactive fiction are beginning to demonstrate a concern for the literariness of their product. Literariness, as defined by Shklovskij and the Russian Formalists, is the quality of making strange that which is linguistically familiar, a quality Shklovskij termed ostranenie. By applying the principle of ostranenie, as well as other well-known literary principles, to the most serious interactive fictions, we can determine if this new genre exhibits the features of literariness. A study of Mindwheel, Brimstone, Breakers, A Mind Forever Voyaging, Portal, and Trinity suggest that the literariness of interactive fiction comes out of its concern both for making strange what is familiar and for making familiar what is strange.Neil Randall has published several role-playing games, and is working on a full-length critical study of interactive fiction. He is currently assistant professor of English.     

Microscopic vision system with all-in-focus and depth images

In this paper, a high-speed digital processed microscopic observational system for telemicrooperation is proposed with a dynamic focusing system and a high-speed digital-processing system using the depth from focus criterion. In our previous work [10], we proposed a system that could simultaneously obtain an all-in-focus image as well as the depth of an object. In reality, in a microoperation, it is not easy to obtain good visibility of objects with a microscope focused at a shallow depth, especially in microsurgery and DNA studies, among other procedures. In this sense, the all-in-focus image, which keeps an in-focus texture over the entire object, is useful for observing microenvironments with the microscope. However, one drawback of the all-in-focus image is that there is no information about the objects depth. It is also important to obtain a depth map and show the 3D microenvironments at any view angle in real time to actuate the microobjects. Our earlier system with a dynamic focusing lens and a smart sensor could obtain the all-in-focus image and the depth in 2 s. To realize real-time microoperation, a system that could process at least 30 frames per second (60 times faster than the previous system) would be required. This paper briefly reviews the depth from focus criterion to Simultaneously achieve the all-in-focus image and the reconstruction of 3D microenvironments. After discussing the problem inherent in our earlier system, a frame-rate system constructed with a high-speed video camera and FPGA (field programmable gate array) hardware is discussed. To adapt this system for use with the microscope, new criteria to solve the ghost problem in reconstructing the all-in-focus image are proposed. Finally, microobservation shows the validity of this system.Received: 12 August 2001, Accepted: 17 July 2002, Published online: 12 November 2003 Correspondence to: Kohtaro Ohba     

A semi-automatic system for edge tracking with snakes

Active contour models, or snakes, developed in (Kass et al. 1988), use a simple physical model to track edges in image sequences. Snakes as originally defined however, tend to shrink, stretch and slide back and forth in unwanted ways along a tracked edge and are also confused by multiple edges, always grabbing the nearest one. In this paper a semi-automatic system is presented that combines motion estimation techniques with snakes to overcome these problems. An algorithm is presented that uses a block matching technique to guide the endpoints of the snake, optical flow to push the snake in the direction of the underlying motion, followed by the traditional snake edge-fitting minimization process. We use this technique for tracking facial features of an actor for driving computer animated characters.     

Image Registration, Optical Flow and Local Rigidity

We address the theoretical problems of optical flow estimation and image registration in a multi-scale framework in any dimension. Much work has been done based on the minimization of a distance between a first image and a second image after applying deformation or motion field. Usually no justification is given about convergence of the algorithm used. We start by showing, in the translation case, that convergence to the global minimum is made easier by applying a low pass filter to the images hence making the energy convex enough. In order to keep convergence to the global minimum in the general case, we introduce a local rigidity hypothesis on the unknown deformation. We then deduce a new natural motion constraint equation (MCE) at each scale using the Dirichlet low pass operator. This transforms the problem to solving the energy minimization in a finite dimensional subspace of approximation obtained through Fourier Decomposition. This allows us to derive sufficient conditions for convergence of a new multi-scale and iterative motion estimation/registration scheme towards a global minimum of the usual nonlinear energy instead of a local minimum as did all previous methods. Although some of the sufficient conditions cannot always be fulfilled because of the absence of the necessary a priori knowledge on the motion, we use an implicit approach. We illustrate our method by showing results on synthetic and real examples in dimension 1 (signal matching, Stereo) and 2 (Motion, Registration, Morphing), including large deformation experiments.     

Nonlinear diffusions in topology optimization

Filtering has been a major technique used in homogenization-based methods for topology optimization of structures. It plays a key role in regularizing the basic problem into a well-behaved setting, but it has the drawback of a smoothing effect around the boundary of the material domain. In this paper, a diffusion technique is presented as a variational approach to the regularization of the topology optimization problem. A nonlinear or anisotropic diffusion process not only leads to a suitable problem regularization but also exhibits strong edge-preserving characteristics. Thus, we show that the use of nonlinear diffusions brings the desirable effects of boundary preservation and even enhancement of lower-dimensional features such as flow-like structures. The proposed diffusion techniques have a close relationship with the diffusion methods and the phase-field methods from the fields of materials and digital image processing. The proposed method is described and illustrated with 2D examples of minimum compliance that have been extensively studied in recent literature of topology optimization.     

On characterizing the “knee” of the Pareto curve based on Normal-Boundary Intersection

This paper deals with the issue of generating one Pareto optimal point that is guaranteed to be in a desirable part of the Pareto set in a given multicriteria optimization problem. A parameterization of the Pareto set based on the recently developed normal-boundary intersection technique is used to formulate a subproblem, the solution of which yields the point of maximum bulge, often referred to as the knee of the Pareto curve. This enables the identification of the good region of the Pareto set by solving one nonlinear programming problem, thereby bypassing the need to generate many Pareto points. Further, this representation extends the concept of the knee for problems with more than two objectives. It is further proved that this knee is invariant with respect to the scales of the multiple objective functions.The generation of this knee however requires the value of each objective function at the minimizer of every objective function (the pay-off matrix). The paper characterizes situations when approximations to the function values comprising the pay-off matrix would suffice in generating a good approximation to the knee. Numerical results are provided to illustrate this point. Further, a weighted sum minimization problem is developed based on the information in the pay-off matrix, by solving which the knee can be obtained.     

An anisotropic mesh parameterization scheme

We introduce a simple anisotropic modification of Floaters shape-preserving parameterization scheme. The original scheme is formulated as a discrete energy minimization and the modification is performed by introducing an additional stretching term. Results and example applications to anisotropic regular surface meshing are presented.     

Topology optimization of continuum structures with material failure constraints

This work presents an efficient strategy for dealing with topology optimization associated with the problem of mass minimization under material failure constraints. Although this problem characterizes one of the oldest mechanical requirements in structural design, only a few works dealing with this subject are found in the literature. Several reasons explain this situation, among them the numerical difficulties introduced by the usually large number of stress constraints. The original formulation of the topological problem (existence/non-existence of material) is partially relaxed by following the SIMP (Solid Isotropic Microstructure with Penalization) approach and using a continuous density field as the design variable. The finite element approximation is used to solve the equilibrium problem, as well as to control through nodal parameters. The formulation accepts any failure criterion written in terms of stress and/or strain invariants. The whole minimization problem is solved by combining an augmented Lagrangian technique for the stress constraints and a trust-region box-type algorithm for dealing with side constraints (0<_min1) . Numerical results show the efficiency of the proposed approach in terms of computational costs as well as satisfaction of material failure constraints. It is also possible to see that the final designs define quite different shapes from the ones obtained in classical compliance problems.     

Coupled algebraic multigrid methods for the Oseen problem

We provide a concept combining techniques known from geometric multigrid methods for saddle point problems (such as smoothing iterations of Braess- or Vanka-type) and from algebraic multigrid (AMG) methods for scalar problems (such as the construction of coarse levels) to a coupled algebraic multigrid solver. Coupled here is meant in contrast to methods, where pressure and velocity equations are iteratively decoupled (pressure correction methods) and standard AMG is used for the solution of the resulting scalar problems. To prove the efficiency of our solver experimentally, it is applied to finite element discretizations of real life industrial problems.     

Notes on Max Flow Time Minimization with Controllable Processing Times

In a scheduling problem with controllable processing times the job processing time can be compressed through incurring an additional cost. We consider the identical parallel machines max flow time minimization problem with controllable processing times. We address the preemptive and non-preemptive version of the problem. For the preemptive case, a linear programming formulation is presented which solves the problem optimally in polynomial time. For the non-preemptive problem it is shown that the First In First Out (FIFO) heuristic has a tight worst-case performance of 3–2/m, when jobs processing times and costs are set as in some optimal preemptive schedule. Supported by Swiss National Science Foundation project 20-63733.00/1, Resource Allocation and Scheduling in Flexible Manufacturing Systems, and by the Metaheuristics Network, grant HPRN-CT-1999-00106.     

On Weight Distributions of Shifts of Goethals-like Codes

We study weight distributions of shifts of codes from a well-known family: the 3-error-correcting binary nonlinear Goethals-like codes of length n = 2 ^m , where m 6 is even. These codes have covering radius = 6. We know the weight distribution of any shift of weight i = 1, 2, 3, 5, or 6. For a shift of weight 4, the weight distribution is uniquely defined by the number of leaders in this shift, i.e., the number of vectors of weight 4. We also consider the weight distribution of shifts of codes with minimum distance 7 obtained by deleting any one position of a Goethals-like code of length n.     

Active Appearance Models Revisited

Active Appearance Models (AAMs) and the closely related concepts of Morphable Models and Active Blobs are generative models of a certain visual phenomenon. Although linear in both shape and appearance, overall, AAMs are nonlinear parametric models in terms of the pixel intensities. Fitting an AAM to an image consists of minimising the error between the input image and the closest model instance; i.e. solving a nonlinear optimisation problem. We propose an efficient fitting algorithm for AAMs based on the inverse compositional image alignment algorithm. We show that the effects of appearance variation during fitting can be precomputed (projected out) using this algorithm and how it can be extended to include a global shape normalising warp, typically a 2D similarity transformation. We evaluate our algorithm to determine which of its novel aspects improve AAM fitting performance.Supplementary material to this paper is available in electronic form at http://dx.doi.org/10.1023/B:VISI.0000029666.37597.d3     

On the Incorporation of Time-delay Regularization into Curvature-based Diffusion

A new anisotropic nonlinear diffusion model incorporating time-delay regularization into curvature-based diffusion is proposed for image restoration and edge detection. A detailed mathematical analysis of the proposed model in the form of the proof of existence, uniqueness and stability of the viscosity solution of the model is presented. Furthermore, implementation issues and computational methods for the proposed model are also discussed in detail. The results obtained from testing our denoising and edge detection algorithm on several synthetic and real images showed the effectiveness of the proposed model in prserving sharp edges and fine structures while removing noise.     

Edge Detection by Helmholtz Principle

We apply to edge detection a recently introduced method for computing geometric structures in a digital image, without any a priori information. According to a basic principle of perception due to Helmholtz, an observed geometric structure is perceptually meaningful if its number of occurences would be very small in a random situation: in this context, geometric structures are characterized as large deviations from randomness. This leads us to define and compute edges and boundaries (closed edges) in an image by a parameter-free method. Maximal detectable boundaries and edges are defined, computed, and the results compared with the ones obtained by classical algorithms.     

Analog hardware for detecting discontinuities in early vision

The detection of discontinuities in motion, intensity, color, and depth is a well-studied but difficult problem in computer vision [6]. We discuss the first hardware circuit that explicitly implements either analog or binary line processes in a deterministic fashion. Specifically, we show that the processes of smoothing (using a first-order or membrane type of stabilizer) and of segmentation can be implemented by a single, two-terminal nonlinear voltage-controlled resistor, the resistive fuse; and we derive its current-voltage relationship from a number of deterministic approximations to the underlying stochastic Markov random fields algorthms. The concept that the quadratic variation functionals of early vision can be solved via linear resistive networks minimizing power dissipation [37] can be extended to non-convex variational functionals with analog or binary line processes being solved by nonlinear resistive networks minimizing the electrical co-content.We have successfully designed, tested, and demonstrated an analog CMOS VLSI circuit that contains a 1D resistive network of fuses implementing piecewise smooth surface interpolation. We furthermore demonstrate the segmenting abilities of these analog and deterministic line processes by numerically simulating the nonlinear resistive network computing optical flow in the presence of motion discontinuities. Finally, we discuss various circuit implementations of the optical flow computation using these circuits.     

Unique reconstruction of piecewise-smooth images by minimizing strictly convex nonquadratic functionals

We propose the minimization of a nonquadratic functional or, equivalently, a nonlinear diffusion model to smooth noisy image functionsg: R ⁿ R while preserving significant transitions of the data. The model is chosen such that important properties of the conventional quadratic-functional approach still hold: (1) existence of a unique solution continuously depending on the datag and (2) stability of approximations using the standard finite-element method. Relations with other global approaches for the segmentation of image data are discussed. Numerical experiments with real data illustrate this approach.This work was supported by the ESPRIT project SUBSYM.     

Edge crossings in drawings of bipartite graphs

Systems engineers have recently shown interest in algorithms for drawing directed graphs so that they are easy to understand and remember. Each of the commonly used methods has a step which aims to adjust the drawing to decrease the number of arc crossings. We show that the most popular strategy involves an NP-complete problem regarding the minimization of the number of arcs in crossings in a bipartite graph. The performance of the commonly employed barycenter heuristic for this problem is analyzed. An alternative method, the median heuristic, is proposed and analyzed. The new method is shown to compare favorably with the old in terms of performance guarantees. As a bonus, we show that the median heuristic performs well with regard to the total length of the arcs in the drawing.     

Unitary immersions of nonlinear systems

In this paper, we define what we call a unitary immersion of a nonlinear system. We observe that, for classical Hamiltonian systems, this notion contains, in some sense, the concept of quantization. We restrict our attention to degree-zero unitary immersions, where all observation functions must be represented by operators of the type multiplication by a function. We show that the problem of classifying such degree-zero unitary immersions of a given nonlinear system is not obvious. In some cases, we solve this problem.Chargé de Recherche au CNRS.Maître de Conférences.