This Full Paper in the Innovative Practice category begins by asking “can algorithms be thought of and taught as dynamical systems?” Our exploration of this idea — Algodynamics — is guided by a vision to achieve convergence between computing and engineering education. The engineering sciences share a common conceptual vocabulary originating in dynamical systems: state spaces, flows, actions, invariants, fixed points, convergence, etc. The goal of algodynamics is to build, ab initio, a framework for understanding and teaching algorithms using concepts from dynamics. This allows us to teach computing and algorithms as an engineering science. Engineers work with models. In algodynamics, models are expressed using transition systems rather than as pseudocode or programs. This allows a crisp representation of two important classes of computation: sequential algorithms as ‘discrete flows’ (iterative systems) and interactive applications as ‘action flows’ (transition systems). The focus of this paper is on the first of these classes, algorithms, but using ideas from the second, viz., transition systems. In this framework, algorithms emerge as convergent iterative systems. Due to their non-interactivity, iterative systems may be hard to understand. The student may trace through the algorithm, but to know how the parts of the algorithm work together requires ‘opening up’ the algorithm and situating it within the more general class of interactive systems. Doing so helps the student to understand the machinery of an algorithm in an incremental and modular way. The student interactively solves the algorithmic problem, experimenting with various strategies along the way. At each stage of the design, interactivity is traded for automation. We illustrate our approach by considering a classic example from sorting: Bubblesort. We first examine a solution based on fixed point iteration. Then we approach Bubblesort as a sequence of five interactive transition systems that culminate in the Bubblesort algorithm. This exercise reveals to the student design decisions and strategies that help understand why Bubblesort works. The successive refinement also pays off in terms of highly modular code whose primitives are elements of the transition system models.

The Virtual Labs project (vlabs) is a country wide effort to provide access to internet and browser based virtual laboratories to science and engineering college students in India. There are currently over 800 experiments packaged in 70 vlabs in more than ten science and engineering disciplines. More than five hundred workshops on these virtual labs have been conducted and the experiments have been used over 2 million times. Vlabs are an important Government initiative in higher learning in engineering in India. This paper examines virtual labs from a usability perspective, focusing on vlabs. Usability of user-interface elements (technical usability) as well as how they aid learning (pedagogical usability) has been considered. We adapt Nielsen's technical usability heuristics and Nokelainen's pedagogical usability criteria to virtual labs and evaluate the usability of the top three most used vlabs. We construct checklists for each of these criteria and evaluate the vlabs against this checklist. Our analysis reveals a lack of usability focus in lab design. Lab design and implementation guidelines seem to be deficient in covering key usability criteria. We make suggestions on how to quickly improve the usability of these labs.

Algorithmic interpretation of question articulation is one of the key steps in a machine-driven question-answering system. Machine understanding of an input question is tightly related to recognition of articulation in the context of the computational capabilities of an underlying processing algorithm. In this paper, a mathematical model to capture and distinguish the latent structure in the articulation of questions is presented. It is argued that an objective-driven approach to represent this latent structure is beneficial when examples of complementary objectives are not available. We show that the latent structure can be represented as a system that maximizes a cost function related to the underlying objective. Further, we show that the optimization formulation can be approximated to building a memory of patterns represented as a trained neural auto-encoder. Experimental evaluation using many clusters of questions, each related to an objective, shows 80% recognition accuracy and a negligible false positive across these clusters of questions. We then extend the same memory to a related task where the goal is to iteratively refine clusters of questions based on latent articulation. We show that the refinement scheme called K-fingerprints achieves nearly 100% cluster recognition with negligible false positive between different clusters.

Efficient video representation models are critical for many video analysis and processing tasks. In this paper, we present a framework based on the concept of finding the sparsest solution to model video frames. To model the spatio-temporal information, frames from one scene are decomposed into two components: (i) a common frame, which describes the visual information common to all the frames in the scene/segment, and (ii) a set of innovative frames, which depicts the dynamic behaviour of the scene. The proposed approach exploits and builds on recent results in the field of compressed sensing to jointly estimate the common frame and the innovative frames for each video segment. We refer to the proposed modeling framework by CIV (Common and Innovative Visuals). We show how the proposed model can be utilized to find scene change boundaries and extend CIV to videos from multiple scenes. Furthermore, the proposed model is robust to noise and can be used for various video processing applications without relying on motion estimation and detection or image segmentation. Results for object tracking, video editing (object removal, inpainting) and scene change detection are presented to demonstrate the efficiency and the performance of the proposed model.

Typical consumer digital cameras sense only one out of three color components per image pixel. The problem of demosaicing deals with interpolating those missing color components. In this paper, we present compressive demosaicing (CD), a framework for demosaicing natural images based on the theory of compressed sensing (CS). Given sensed samples of an image, CD employs a CS solver to find the sparse representation of that image under a fixed sparsifying dictionary Ψ. As opposed to state of the art CS-based demosaicing approaches, we consider a clear distinction between the interchannel (color) and interpixel correlations of natural images. Utilizing some well-known facts about the human visual system, those two types of correlations are utilized in a nonseparable format to construct the sparsifying transform Ψ. Our simulation results verify that CD performs better (both visually and in terms of PSNR) than leading demosaicing approaches when applied to the majority of standard test images.

Key frame extraction algorithms select a subset of the most informative frames from videos. Key frame extraction finds applications in several broad areas of video processing research such as video summarization, video indexing, and prints from video. In this paper, an image epitome [1][2] based method to extract key frames from unstructured consumer videos is presented. In the proposed approach, we exploit image epitome to measure dissimilarity between frames of the input video. The dissimilarity scores are further analyzed using a min-max approach to extract the desired number of key frames from the input video. The proposed approach does not require shot(s) detection, segmentation, or semantic understanding. A comparison of the results obtained by this method with the ground truth agreed by multiple judges clearly indicates the feasibility of the proposed approach.

In this paper, we explore the notion of using frames to project sensed colors within their inherently 3D space onto a larger number of color basis vectors. In particular, we develop a new frame design, Incoherent Color Frames (ICF), which can include an arbitrary number of incoherent color vectors. An ICF frame possesses key desired properties including the ability to sparsify colors in 3D and to decorrelate color channels utilizing a spatial-frequency selective strategy. We present a low complexity algorithm for constructing ICF frames targeted for the problem of image demosaicing. Our simulation results show that when incorporating the proposed ICF within a Compressive Demosaicing (CD) framework, significant visual improvements can be achieved when compared with traditional and Compressed Sesnsing-based demosaicing solutions.

The utility of Compressed Sensing (CS) for demosaicing of images captured using random panchromatic color filter arrays (CFA) has been investigated in [1]. Meanwhile, most camera manufacturers employ periodic CFAs such as the popular Bayer CFA. In this paper, we derive a CS-based solution to demosaicing images captured using the general class of periodic CFAs. It is well known that periodic CFAs can be designed to effectively separate luminance and chrominance frequency bands [2, 3]. We employ this ability to reduce artifacts associated with luminance-chrominance overlap at the solver side. We show that the modified compressive demo-saicing method coupled with the additional constraint that chrominance channels have smooth surfaces achieves further improved results for most periodic CFAs.

Key frame extraction algorithms select a subset of the most informative frames from videos. Key frame extraction finds applications in several broad areas of video processing research such as video summarization, creating “chapter titles” in DVDs, video indexing, and prints from video. In this paper, a sparse representation based method to extract key frames from unstructured consumer videos is presented. In the proposed approach, video frames are projected to a low dimensional random feature space and theory from sparse signal representation is used to analyze the spatio-temporal information of the video data and generate key frames. The proposed approach is computationally efficient and does not require shot(s) detection, segmentation, or semantic understanding. A comparison of the results obtained by this method with the ground truth agreed by multiple judges and another approach based on camera operator's intent clearly indicates the feasibility of the proposed approach.

A new method to detect salient region(s) in images is proposed in this paper. The proposed approach, which is inspired by object-based visual attention theory, segments the input image into coherent regions and measures region-based center-surround distance (RBCSD), which is a distance between region attributes such as color histograms found in each region and its surrounding region. Furthermore, segmented regions are merged such that the RBCSD of the merged region is greater than the individual RBCSD of the component regions through region-based incremental center surround distance (RBCSD+I) process. Due to this RBCSD+I process, merged regions may contain incoherent color regions, which improves the robustness of the proposed approach. The key advantages of the proposed algorithm are: (1) it provides a salient region with plausible object boundaries, (2) it is robust to color incoherency present in the salient region, and (3) it is computationally efficient. Extensive qualitative and quantitative evaluation of the proposed algorithm on widely used data sets and comparison with the existing saliency detection approaches clearly indicates the feasibility and efficiency of the proposed approach.

Compared to well-edited videos with predefined structures (e.g., news or sports videos), extracting key frames from unconstrained consumer videos remains a much more challenging problem due to their extremely diverse contents (no pre-imposed structure) and uncontrolled video quality (e.g., due to poor lighting or camera shake). In order to exploit spatio-temporal correlation present in the video for key frame extraction, we propose a bi-layer group sparse representation in which the input video frames are first segmented into homogeneous patches and group sparsity is imposed at two levels simultaneously: (i) patch-to-frame, and (ii) frame-to-sequence. The grouped sparse coefficients are further combined with frame quality scores to generate key frames. Extensive experiments are performed on videos from actual end users. Results obtained by the proposed approach compare favorably with existing methods to confirm its effectiveness.

With the rise of mobile media devices, resizing an image or video to fit a screen of arbitrary size has become an important topic. In general, arbitrary resizing does not preserve the original image aspect ratio, and hence, can introduce significant visual distortion. Content-aware retargeting methods have been proposed to preserve salient features of an image or video even under arbitrary changing of the aspect ratio. While these are useful tools, little attention has been given to the development of an efficient retargeting-driven representation of images. Such representation, for example, can lead to efficient distribution of media destined for retargeting at a variety of devices with different aspect ratios. We propose a new framework, seamlets, which utilizes the discrete wavelet transform (DWT) to perform content-aware arbitrary media resizing. In essence, seamlets provide an efficient multi-resolution representation for retargeting applications. The seamlet transform elegantly generalizes the DWT and seam carving, which is an intriguing retargeting method. The result is a new image framework, seamlets, that inherits the benefits of retargeting and wavelets.

In this paper an image fusion approach is proposed for denoising digital images corrupted with signal-independent and signal-dependent noise. In the proposed approach, multiple captures of the same scene of interest are acquired and fused to estimate the original, noise-free image. This approach is motivated by the fact that noise is random in nature; hence, its interaction with the pixels will change with each capture, which in turn can be exploited for denoising purposes. In order to fuse multiple captures, a local affine model is developed to relate these captures and the corresponding original image. Furthermore, total variation (TV) regularization, which preserves discontinuity and is robust to noise, is used to solve the local affine fusion model iteratively to estimate the original image. While the proposed approach requires multiple captures, it is still computationally very fast and the quality of the denoised images clearly indicates the feasibility of the proposed approach.

This paper discusses use of a single image sensor with a four-channel color filter array (CFA) and flexible readout capabilities for a compact digital camera. It considers camera system technology and design tradeoffs, followed by a discussion of an example four-channel sensor. Advantages of the sensor include better sensitivity than a similar sensor with a three-channel CFA and more flexible exposure and readout control. The example sensor enables a new approach for multiframe image capture, termed multicomponent image capture.

With the abundance and variety of display devices, novel image resizing techniques have become more desirable. Content-aware image resizing (retargeting) techniques have been proposed that show improvement over traditional techniques such as cropping and resampling. In particular, seam carving has gained attention as an effective solution, using simple filters to detect and preserve the high-energy areas of an image. Yet, it stands to be more robust to a variety of image types. To facilitate such improvement, we recast seam carving in a more general framework and in the context of filter banks. This enables improved filter design, and leads to a multiscale model that addresses the problem of scale of image features. We have found our generalized multiscale model to improve on the existing seam carving method for a variety of images.

A typical consumer digital camera uses a Color Filter Array (CFA) to sense only one color component per image pixel. The original three-color image is reconstructed by interpolating the missing color components. This interpolation process (known as demosaicing) corresponds to solving an under-determined system of linear equations. In this paper, we show that by replacing the traditional CFA with a random panchromatic CFA, recent results in the emerging field of Compressed Sensing (CS) can be used to solve the demosaicing problem in a novel way. Specifically, during the image reconstruction process, we exploit the fact that the multi-dimensional color of each pixel has a compressible representation in a (possibly overcomplete) color system. While adhering to the “single color per pixel sensing” constraint at the sensing stage, during the reconstruction process we utilize the inter-pixel correlation by exploiting the compressible representation of the overall image in some sparsifying bases. Depending on the CFA, sparsifying bases and the color system, we form an underdetermined system of linear equations and find the sparsest solution for the color image by utilizing a CS solver. We illustrate that, for natural images, the proposed Compressive Demosaicing (CD) framework visually outperforms leading demosaicing methods in a consistent manner; in many cases it achieves clear visible improvements in a significant way.

In this paper, a novel digital camera sensor architecture to acquire images with high fidelity under low light conditions is proposed. Today, almost all digital cameras have only red, green, and blue color pixels. Due to their limited sensitivity to the wavelengths of visible light, the images captured using these color pixels under low light conditions are noisy. A new sensor architecture that has panchromatic pixels sensitive to all visible wavelengths along with the red, green, and blue pixels is proposed. Panchromatic pixels allow luminance information to be detected with higher sensitivity whereas red, green, and blue pixels produce the color information. Real images captured using the proposed sensor design are compared with the corresponding images obtained using a traditional digital camera having only red, green, and blue pixels. The results clearly show the feasibility of the proposed approach.

In this paper, a total variation (TV) based approach is proposed for pixel-level fusion to fuse images acquired using multiple sensors. In this approach, fusion is posed as an inverse problem and a locally affine model is used as the forward model. A TV seminorm based approach in conjunction with principal component analysis is used iteratively to estimate the fused image. The feasibility of the proposed algorithm is demonstrated on images from computed tomography (CT) and magnetic resonance imaging (MRI) as well as visible-band and infrared sensors. The results clearly indicate the feasibility of the proposed approach.

Blind restoration of single-input/multiple-output images finds application in diverse fields including multi-sensor remote sensing, non-destructive testing and medical imaging. In this paper, an iterative forward propagation dynamic programming based approach is proposed for restoring images in a single-input/multiple-output multichannel framework. This algorithm exploits cross channel correlation for restoring images, leading to improved performance as compared to single channel restoration. The algorithm is applied to both synthetic as well as experimental data and initial results indicate the feasibility of the proposed algorithm.