Deep neural networks (DNNs) have recently emerged as a powerful paradigm for solving Markovian optimal stopping problems. However, a ready extension of DNN-based methods to non-Markovian settings requires significant state and parameter space expansion, manifesting the curse of dimensionality. Further, efficient state-space transformations permitting Markovian approximations, such as those afforded by recurrent neural networks (RNNs), are either structurally infeasible or are confounded by the curse of non-Markovianity. Considering these issues, we introduce, for the first time, an optimal stopping policy gradient algorithm (OSPG) that can leverage RNNs effectively in non-Markovian settings by implicitly optimizing value functions without recursion, mitigating the curse of non-Markovianity. The OSPG algorithm is derived from an inference procedure on a novel Bayesian network representation of discrete-time non-Markovian optimal stopping trajectories and, as a consequence, yields an offline policy gradient algorithm that eliminates expensive Monte Carlo policy rollouts.

Providing a timely intervention before the onset of a critical event, such as a system failure, is of importance in many industrial settings. Before the onset of the critical event, systems typically exhibit behavioral changes which often manifest as stochastic co-variate observations which may be leveraged to trigger intervention. In this paper, for the first time, we formulate the problem of finding an optimally timed intervention (OTI) policy as minimizing the expected residual time to event, subject to a constraint on the probability of missing the event. Existing machine learning approaches to intervention on critical events focus on predicting event occurrence within a pre-defined window (a classification problem) or predicting time-to-event (a regression problem). Interventions are then triggered by setting model thresholds. These are heuristic-driven, lacking guarantees regarding optimality. To model the evolution of system behavior, we introduce the concept of a hazard rate process. We show that the OTI problem is equivalent to an optimal stopping problem on the associated hazard rate process. This key link has not been explored in literature. Under Markovian assumptions on the hazard rate process, we show that an OTI policy at any time can be analytically determined from the conditional hazard rate function at that time. Further, we show that our theory includes, as a special case, the important class of neural hazard rate processes generated by recurrent neural networks (RNNs). To model such processes, we propose a dynamic deep recurrent survival analysis (DDRSA) architecture, introducing an RNN encoder into the static DRSA setting. Finally, we demonstrate RNN-based OTI policies with experiments and show that they outperform popular intervention methods

Abstract Students are nowadays given many options to consume educational content in digital formats as alternatives to printed material. Previous research suggests that while digital content has advantages, printed media still provides other benefits that cannot be matched by digital. Therefore, technology should leverage the benefits of both. In this paper, we present the Meaningful Education and Training Information System, a multifaceted hybrid textbook learning platform. The goal of the system is to provide an easy digital‐to‐print‐to‐digital content creation and reading service. The Meaningful Education and Training Information System incorporates technologies for layout, personalization, cocreation, and assessments. These facilitate common teacher/student tasks and help provide a richer, more effective learning experience. Our system has been demonstrated in multiple international education events, partner engagements, and pilots with local universities and high schools.

Millions of customer reviews for products are available online across hundreds of different websites. These reviews have a tremendous influence on the purchase decision of new customers and in creating a positive brand image. Understanding which of the product issues are critical in determining the product ratings is crucial for marketing teams. We have developed a solution which can derive deep insights from customer reviews which goes significantly beyond keyword based analysis. Our solution can identify key customer issues voiced in the reviews and the impact of each of these on the final rating that a customer gives the product. This insight is very actionable as it helps identify which customer concerns are responsible for bad ratings of products.

Today, students are offered a wide variety of alternatives to printed material for the consumption of educational content. Previous research suggests that, while digital content has its advantages, printed content still offers benefits that cannot be matched by digital media. This paper introduces the Meaningful Education and Training Information System (METIS), a multi-faceted hybrid book learning platform. The goal of the system is to provide an easy digital-to-print-to-digital content creation and reading service. METIS incorporates technology for layout, personalization, co-creation and assessment. These facilitate and, in many cases, significantly simplify common teacher/student tasks. Our system has been demonstrated at several international education events, partner engagements, and pilots with local universities and high schools. We present the system and discuss how it enables hybrid learning.

Printing has long been a neglected aspect of the Web, and the print function of browsers, when used on documents designed for on-screen consumption, often leads to a poor result. Whereas print CSS goes some way towards optimizing the paper experience, it still does not enable full control over the page layout, which is necessary to obtain a publication-quality print result. Furthermore, its use requires web authors to invest additional resources for a feature that might only be used infrequently. This paper introduces a framework designed to alleviate these issues and improve the print experience on the Web. We describe the technologies that enable us to automatically compose and optimize the layout of a document, and generate a high quality PDF fully within the browser. This functionality can be offered to web publishers in the form of a print button, enabling content to be simultaneously delivered in screen and print formats, and ensuring a publication-quality result that adheres to the publisher's design guidelines.

We present AERO, an extensible framework for adaptive web layout synthesis. The goal is to provide an underlying software architecture to allow general adaptive layout behaviors. The framework consists of a 1) a suite of templates specified in HTML/CSS, 2) A hierarchical, highly customizable scoring function specification and 3) An evaluation engine that leverages native browser rendering to rapidly render content and apply the scoring functions. Unlike current responsive layout frameworks for web (e.g., Twitter Bootstrap) that have pre-configured grid layouts that adapt in a manually pre-encoded content-independent manner, AERO allows layout to adapt automatically based on multiple content-dependent criteria like aesthetic quality, cropability of individual images, layout A/B testing results, Ad placement etc.

Pagination the process of determining where to break an article across pages in a multi-article layout is a common layout challenge for most commercially printed newspapers and magazines. To date, no one has created an algorithm that determines a minimal pagination break point based on the content of the article. Existing approaches for automatic multi-article layout focus exclusively on maximizing content (number of articles) and optimizing aesthetic presentation (e.g., spacing between articles). However, disregarding the semantic information within the article can lead to overly aggressive cutting, thereby eliminating key content and potentially confusing the reader, or setting too generous of a break point, thereby leaving in superfluous content and making automatic layout more difficult. This is one of the remaining challenges on the path from manual layouts to fully automated processes that still ensure article content quality. In this work, we present a new approach to calculating a document minimal break point for the task of pagination. Our approach uses a statistical language model to predict minimal break points based on the semantic content of an article. We then compare 4 novel candidate approaches, and 4 baselines (currently in use by layout algorithms). Results from this experiment show that one of our approaches strongly outperforms the baselines and alternatives. Results from a second study suggest that humans are not able to agree on a single "best" break point. Therefore, this work shows that a semantic-based lower bound break point prediction is necessary for ideal automated document synthesis within a real-world context.

A news article generally contains a high-level overview of the facts early on, followed by paragraphs of more detailed information. This structure allows copy editors to truncate the latter paragraphs of an article in order to satisfy space limitations without losing critical information. Existing approaches to this problem of automatic multi-article layout focus exclusively on maximizing content and aesthetics. However, no algorithm can determine how "good" a truncation point is based on the semantic content, or article readability. Yet, disregarding the semantic information within the article can lead to either overly aggressive cutting, thereby eliminating key content and potentially confusing the reader; conversely, it may set too generous of a truncation point, thus leaving in superfluous content and making automatic layout more difficult. This is one of the remaining challenges on the path from manual layouts to fully automated processes with high quality output. In this work, we present a new semantic-focused approach to rate the quality of a truncation point. We built models based on results from an extensive user study on over 700 news articles. Further results show that existing techniques over-cut content. We demonstrate the layout impact through a second evaluation that implements our models in the first layout approach that integrates both layout and semantic quality. The primary contribution of this work is the demonstration that semantic-based modeling is critical for high-quality automated document synthesis within a real-world context.

We present a method for the automated composition of personalized newspapers. Traditional newsprint composition is a laborious and expensive manual process. We develop a two level hierarchical page layout model that models aesthetic design choices using local (within article region) and global (page level) prior probability distributions. Given content to be composed, our model can infer the best way to divide a page into layout regions and simultaneously optimize content fit within these regions. We automate decisions on how to paginate articles, flow article text across pages, crop images, adjust whitespace etc. for the best overall newspaper compositions. We also show how content editing which is a very important task in the traditional news workflow can be incorporated in a semi-automated manner within our framework. Our model is a generalization of our prior work on probabilistic modeling of single-flow layouts to enable multiple article flows on a page, while still allowing one or more articles that may break on a page and continue on subsequent pages.

We consider the problem of automatically inserting advertisements (ads) into machine composed documents. We explicitly analyze the fundamental tradeoff between expected revenue due to ad insertion and the quality of the corresponding composed documents. We show that the optimal tradeoff a publisher can expect may be expressed as an efficient-frontier in the revenue-quality space. We develop algorithms to compose documents that lie on this optimal tradeoff frontier. These algorithms can automatically choose distributions of ad sizes and ad placement locations to optimize revenue for a given quality or optimize quality for given revenue. Such automation allows a market maker to accept highly personalized content from publishers who have no design or ad inventory management capability and distribute formatted documents to end users with aesthetic ad placement. The ad density/coverage may be controlled by the publisher or the end user on a per document basis by simply sliding along the tradeoff frontier. Business models where ad sales precede (ad-pull) or follow (ad-push) document composition are analyzed from a document engineering perspective.

Managing large document databases has become an important task. Being able to automatically compare document layouts and classify and search documents with respect to their visual appearance proves to be desirable in many applications. We propose a new algorithm that approximates a metric function between documents based on their visual similarity. The comparison is based only on the visual appearance of the document without taking into consideration its text content. We measure the similarity of single page documents with respect to distance functions between three document components: background, text, and saliency. Each document component is represented as a Gaussian mixture distribution; and distances between the components of different documents are calculated as an approximation of the Hellinger distance between corresponding distributions. Since the Hellinger distance obeys the triangle inequality, it proves to be favorable in the task of nearest neighbor search in a document database. Thus, the computation required to find similar documents in a document database can be significantly reduced.

We present a new paradigm for automated document composition based on a generative, unified probabilistic document model (PDM) that models document composition. The model formally incorporates key design variables such as content pagination, relative arrangement possibilities for page elements and possible page edits. These design choices are modeled jointly as coupled random variables (a Bayesian Network) with uncertainty modeled by their probability distributions. The overall joint probability distribution for the network assigns higher probability to good design choices. Given this model, we show that the general document layout problem can be reduced to probabilistic inference over the Bayesian network. We show that the inference task may be accomplished efficiently, scaling linearly with the content in the best case. We provide a useful specialization of the general model and use it to illustrate the advantages of soft probabilistic encodings over hard one-way constraints in specifying design aesthetics.

Unlike blue-noise halftone patterns which are composed of isolated pixels, green noise patterns are composed of pixel-clusters. This makes green noise halftones robust to printer distortions due to the poor isolated pixel reproduction. Levien modified error diffusion by adding a hysteresis filter that feeds a filtered version of the past outputs into the quantizer input in classic error diffusion in order to promote dot-clustering. The patterns produced by the Levien algorithm were analyzed by Lau, Arce and Galagher who coined the term ¿green-noise¿ since the pattern power spectrum was mid-frequency rather than high-frequency (characteristic of ¿blue-noise¿ halftones). However no work has been done to study Leviens algorithm directly in the frequency domain and understand why it works as a green-noise generator. In this paper we will first analyze the Levien green noise error diffusion based on the gain model proposed by Kite et al.. We isolate the noise shaping behavior of the Levien algorithm in the frequency domain and show that it indeed shapes noise into the mid-frequency regions. We then develop two new green noise generators from frequency domain considerations by first by modifying how the error term is computed in conventional error diffusion and then by replacing the error filter in conventional error diffusion by an infinite impulse response (IIR) filter.

Supersampling is widely used by graphics hardware to render anti-aliased images. In conventional supersampling, multiple scene samples are computationally combined to produce a single screen pixel. We consider a novel imaging paradigm that we calldisplay supersampling, where multiple display samples are physically combined via the superimposition of multiple image subframes. Conventional anti-aliasing and texture mapping techniques are shown inadequate for the task of rendering high-quality images on supersampled displays. Instead of requiring anti-aliasing filters, supersampled displays actually require alias generation filters to cancel the aliasing introduced by nonuniform sampling. We present fundamental theory and efficient algorithms for the real-time rendering of high-resolution anti-aliased images on supersampled displays. We show that significant image quality gains are achievable by taking advantage of display supersampling. We prove that alias-free resolution beyond the Nyquist limits of a single subframe may be achieved by designing a bank of alias-canceling rendering filters. In addition, we derive a practical noniterative filter bank approach to real-time rendering and discuss implementations on commodity graphics hardware.

We consider the problem of rendering high-resolution images on a display composed of multiple superimposed lower-resolution projectors. A theoretical analysis of this problem in the literature previously concluded that the multi-projector superimposition of low resolution projectors cannot produce high resolution images. In our recent work, we showed to the contrary that super-resolution via multiple superimposed projectors is indeed theoretically achievable. This paper derives practical algorithms for real multi-projector systems that account for the intra- and inter-projector variations and that render high-quality, high-resolution content at real-time interactive frame rates. A camera is used to estimate the geometric, photometric, and color properties of each component projector in a calibration step. Given this parameter information, we demonstrate novel methods for efficiently generating optimal sub-frames so that the resulting projected image is as close as possible to the given high resolution images.

Multi-projector super-resolution is the dual of multi-camera super-resolution. The goal of projector super-resolution is to produce a high resolution frame via superimposition of multiple low resolution subframes. Prior work claims that it is impossible to improve resolution via superimposed projection except in specialized circumstances. Rigorous analysis has been previously restricted to the special case of uniform display sampling, which reduces the problem to a simple shift-invariant deblurring. To understand the true behavior of superimposed projection as an inverse of classical camera super-resolution, one must consider the effects of non-uniform displacements between component subframes. In this paper, we resolve two fundamental theoretical questions concerning resolution enhancement via superimposed projection. First, we show that it is possible to reproduce frequencies that are well beyond the Nyquist limit of any of the component subframes. Second, we show that nonuniform sampling and pixel reconstruction functions impose fundamental limits on achievable resolution.

Grayscale error diffusion introduces nonlinear distortion (directional artifacts and false textures), linear distortion (sharpening), and additive noise. Tone-dependent error diffusion (TDED) reduces these artifacts by controlling the diffusion of quantization errors based on the input graylevel. We present an extension of TDED to color. In color-error diffusion, which color to render becomes a major concern in addition to finding optimal dot patterns. We propose a visually meaningful scheme to train input-level (or tone-) dependent color-error filters. Our design approach employs a Neugebauer printer model and a color human visual system model that takes into account spatial considerations in color reproduction. The resulting halftones overcome several traditional error-diffusion artifacts and achieve significantly greater accuracy in color rendition.

We present a general framework for the modeling and optimization of scalable multi-projector displays. Based on this framework, we derive algorithms that can robustly optimize the visual quality of an arbitrary combination of projectors without manual adjustment. When the projectors are tiled, we show that our framework automatically produces blending maps that outperform state-of-the-art projector blending methods. When all the projectors are superimposed, the framework can produce high-resolution images beyond the Nyquist resolution limits of component projectors. When a combination of tiled and superimposed projectors are deployed, the same framework harnesses the best features of both tiled and superimposed multi-projector projection paradigms. The framework creates for the first time a new unified paradigm that is agnostic to a particular configuration of projectors yet robustly optimizes for the brightness, contrast, and resolution of that configuration. In addition, we demonstrate that our algorithms support high resolution video at real-time interactive frame rates achieved on commodity graphics platforms. This work allows for inexpensive, compelling, flexible, and robust large scale visualization systems to be built and deployed very efficiently.

Error diffusion halftoning is a popular method of producing frequency modulated (FM) halftones for printing and display. FM halftoning fixes the dot size (e.g., to one pixel in conventional error diffusion) and varies the dot frequency according to the intensity of the original grayscale image. We generalize error diffusion to produce FM halftones with user-controlled dot size and shape by using block quantization and block filtering. As a key application, we show how block-error diffusion may be applied to embed information in hardcopy using dot shape modulation. We enable the encoding and subsequent decoding of information embedded in the hardcopy version of continuous-tone base images. The encoding-decoding process is modeled by robust data transmission through a noisy print-scan channel that is explicitly modeled. We refer to the encoded printed version as an image barcode due to its high information capacity that differentiates it from common hardcopy watermarks. The encoding/halftoning strategy is based on a modified version of block-error diffusion. Encoder stability, image quality versus information capacity tradeoffs, and decoding issues with and without explicit knowledge of the base image are discussed.

We optimize the noise shaping behavior of color error diffusion by designing an optimized error filter based on a proposed noise shaping model for color error diffusion and a generalized linear spatially-invariant model of the human visual system. Our approach allows the error filter to have matrix-valued coefficients and diffuse quantization error across channels in an opponent color representation. Thus, the noise is shaped into frequency regions of reduced human color sensitivity. To obtain the optimal filter, we derive a matrix version of the Yule-Walker equations which we solve by using a gradient descent algorithm.

Error diffusion halftoning is a popular method of producing frequency modulated (FM) halftones. In FM halftoning the dot size and shape is fixed (equal to one pixel) and the dot frequency is varied in accordance to the graylevel values of the underlying grayscale image. We generalize error diffusion to produce FM halftones with user controlled dot size and shape using block quantization and a block filter in the feedback loop. We call this modified quantization and feedback process block error diffusion. The block filters are designed from well known scalar error filter prototypes and retain their properties. Further, we show that choosing a structured block filter results in an efficient parallel implementation of block error diffusion.

Grayscale digital image halftoning quantizes each pixel to one bit. In error diffusion halftoning, the quantization error at each pixel is filtered and fed back to the input in order to diffuse the quantization error among the neighboring grayscale pixels. Error diffusion introduces nonlinear distortion (directional artifacts), linear distortion (sharpening), and additive noise. Threshold modulation, which alters the quantizer input, has been previously used to reduce either directional artifacts or linear distortion. This paper presents an adaptive threshold modulation framework to improve halftone quality by optimizing error diffusion parameters in the least squares sense. The framework models the quantizer implicitly, so a wide variety of quantizers may be used. Based on the framework, we derive adaptive algorithms to optimize 1) edge enhancement halftoning and 2) green noise halftoning. In edge enhancement halftoning, we minimize linear distortion by controlling the sharpening control parameter. We may also break up directional artifacts by replacing the thresholding quantizer with a deterministic bit flipping (DBF) quantizer. For green noise halftoning, we optimize the hysteresis coefficients.

Traditional error diffusion halftoning is a high quality method for producing binary images from digital grayscale images. Error diffusion shapes the quantization noise power into the high frequency regions where the human eye is the least sensitive. Error diffusion may be extended to color images by using error filters with matrix-valued coefficients to take into account the correlation among color planes. For vector color error diffusion, we propose three contributions. First, we analyze vector color error diffusion based on a new matrix gain model for the quantizer, which linearizes vector error diffusion. The model predicts the key characteristics of color error diffusion, esp. image sharpening and noise shaping. The proposed model includes linear gain models for the quantizer by Ardalan and Paulos (1987) and by Kite et al. (1997) as special cases. Second, based on our model, we optimize the noise shaping behavior of color error diffusion by designing error filters that are optimum with respect to any given linear spatially-invariant model of the human visual system. Our approach allows the error filter to have matrix-valued coefficients and diffuse quantization error across color channels in an opponent color representation. Thus, the noise is shaped into frequency regions of reduced human color sensitivity. To obtain the optimal filter, we derive a matrix version of the Yule-Walker equations which we solve by using a gradient descent algorithm. Finally, we show that the vector error filter has a parallel implementation as a polyphase filterbank.

A multifilter is a filter with matrix-valued coefficients, and is used in the processing of vector-valued signals, e.g. color images. Convolution becomes a vector sum of matrix-vector multiplication. In this paper, we efficiently implement a multifilter as a parallel combination of scalar filters. Each scalar filter works on one component of the input vector signal, which increases processing speed by the dimension of the vector-valued signal. This means that by using N processors, the throughput is increased by a factor of N while the total memory usage remains unchanged. We also present a frequency-domain analysis of the filtering.

We model a degraded image as an original image that has been subject to linear frequency distortion and additive noise injection. Since the psychovisual effects of frequency distortion and noise injection are independent, we decouple these two sources of degradation and measure their effect on the human visual system. We develop a distortion measure (DM) of the effect of frequency distortion, and a noise quality measure (NQM) of the effect of additive noise. The NQM, which is based on Peli's (1990) contrast pyramid, takes into account the following: 1) variation in contrast sensitivity with distance, image dimensions, and spatial frequency; 2) variation in the local luminance mean; 3) contrast interaction between spatial frequencies; 4) contrast masking effects. For additive noise, we demonstrate that the nonlinear NQM is a better measure of visual quality than peak signal-to noise ratio (PSNR) and linear quality measures. We compute the DM in three steps. First, we find the frequency distortion in the degraded image. Second, we compute the deviation of this frequency distortion from an allpass response of unity gain (no distortion). Finally, we weight the deviation by a model of the frequency response of the human visual system and integrate over the visible frequencies. We demonstrate how to decouple distortion and additive noise degradation in a practical image restoration system.

Halftones and other binary images are difficult to process with causing several degradation. Degradation is greatly reduced if the halftone is inverse halftoned (converted to grayscale) before scaling, sharpening, rotating, or other processing. For error diffused halftones, we present (1) a fast inverse halftoning algorithm and (2) a new multiscale gradient estimator. The inverse halftoning algorithm is based on anisotropic diffusion. It uses the new multiscale gradient estimator to vary the tradeoff between spatial resolution and grayscale resolution at each pixel to obtain a sharp image with a low perceived noise level. Because the algorithm requires fewer than 300 arithmetic operations per pixel and processes 7x7 neighborhoods of halftone pixels, it is well suited for implementation in VLSI and embedded software. We compare the implementation cost, peak signal to noise ratio, and visual quality with other inverse halftoning algorithms.

We present a generalized optimal minimum phase digital FIR filter design algorithm that supports (1) arbitrary magnitude response specifications, (2) high coefficient accuracy, and (3) real and complex filters. The algorithm uses the discrete Hilbert transform relationship between the magnitude spectrum of a causal real sequence and its minimum phase delay phase spectrum given by Cizek (1970). We extend the transform pair to the complex case and show that the algorithm gives arbitrary coefficient accuracy. We present design examples that exceed the coefficient accuracy of the optimal real minimum phase filters reported by Chen and Parks (1986) and reduce the length of the optimal complex linear phase filters designed by Karam and McClellan (1995).

We present a fast, non-iterative technique for producing grayscale images from error diffused and dithered halftones. The first stage of the algorithm consists of a Gaussian filter and a median filter, while the second stage consists of a bandpass filter, a thresholding operation, and a median filter. The second stage enhances the rendering of edges in the inverse halftone. We compare our algorithm to the best reported statistical smoothing, wavelet, and Bayesian algorithms to show that it delivers comparable PSNR and subjective quality at a fraction of the computation and memory requirements. For error diffused halftones, our technique is seven times faster than the MAP estimation method and 75 times faster than the wavelet method. For dithered halftones, our technique is 200 times faster than the MAP estimation method. A C implementation of the algorithm is available.

We present an inverse halftoning algorithm for error diffused halftones. At each pixel, the algorithm applies a separable 7/spl times/7 FIR filter parameterized by the computed local horizontal and vertical gradients. All operations are entirely local; only 7 rows of image storage and fewer than 300 operations per pixel are required. The algorithm can be easily implemented in embedded software or hardware. We compare our algorithm with previously reported approaches, and show that it delivers comparable PSNR and subjective quality at a fraction of the computation and memory requirements. A C implementation of the algorithm is available.