It is widely agreed that an introductory computer science (CS) course should be about more than just programming. Other aims are acquainting students with concepts and principles of CS and developing students' problem-solving skills. In this paper we propose an early introduction of a term often used by computer scientists: the Sliding Window (SW). The term has evolved over time among professionals to simplify the description of algorithms and can be used as well to support beginners when solving algorithmic problems. This metaphoric term enables abstracting and communicating ideas and at the same time it is easy to implement with elementary programming tools. We illustrate a set of stimulating problems in contemporary CS topics that use the SW and may be introduced in an introductory course.

We introduce the patch transform, where an image is broken into non-overlapping patches, and modifications or constraints are applied in the “patch domain”. A modified image is then reconstructed from the patches, subject to those constraints. When no constraints are given, the reconstruction problem reduces to solving a jigsaw puzzle. Constraints the user may specify include the spatial locations of patches, the size of the output image, or the pool of patches from which an image is reconstructed. We define terms in a Markov network to specify a good image reconstruction from patches: neighboring patches must fit to form a plausible image, and each patch should be used only once. We find an approximate solution to the Markov network using loopy belief propagation, introducing an approximation to handle the combinatorially difficult patch exclusion constraint. The resulting image reconstructions show the original image, modified to respect the user’s changes. We apply the patch transform to various image editing tasks and show that the algorithm performs well on real world images.

Bob offers a face-detection web service where clients can submit their images for analysis. Alice would very much like to use the service, but is reluctant to reveal the content of her images to Bob. Bob, for his part, is reluctant to release his face detector, as he spent a lot of time, energy and money constructing it. Secure Multi- Party computations use cryptographic tools to solve this problem without leaking any information. Unfortunately, these methods are slow to compute and we intro- duce a couple of machine learning techniques that allow the parties to solve the problem while leaking a controlled amount of information. The first method is an information-bottleneck variant of AdaBoost that lets Bob find a subset of features that are enough for classifying an image patch, but not enough to actually recon- struct it. The second machine learning technique is active learning that allows Alice to construct an online classifier, based on a small number of calls to Bob’s face detector. She can then use her online classifier as a fast rejector before using a cryptographically secure classifier on the remaining image patches.

We give a fast rejection scheme that is based on image segments and demonstrate it on the canonical example of face detection. However, in- stead of focusing on the detection step we focus on the rejection step and show that our method is simple and fast to be learned, thus making it an excellent pre-processing step to accelerate standard machine learning classifiers, such as neural-networks, Bayes classifiers or SVM. We de- compose a collection of face images into regions of pixels with similar behavior over the image set. The relationships between the mean and variance of image segments are used to form a cascade of rejectors that can reject over 99.8% of image patches, thus only a small fraction of the image patches must be passed to a full-scale classifier. Moreover, the training time for our method is much less than an hour, on a standard PC. The shape of the features (i.e. image segments) we use is data-driven, they are very cheap to compute and they form a very low dimensional feature space in which exhaustive search for the best features is tractable.

A drawback of most watermarking techniques is the need for some additional information in order to retrieve the watermark. Additionally, the robustness of the watermark decreases as the number of information bits stored in the image increases. We present a watermarking technique which requires no information for decoding in addition to the watermarked image. The watermark is multi-level with few bits embedded robustly at low levels and longer watermark sequences embedded less robustly at higher levels. This allows detection of "tampered" and "attacked" images by detection of existence of the watermark at low levels and deterioration of the watermark at high levels. In order to prevent interference of the watermarks at different levels various image representation spaces are used. The watermark is shown to be non-visible and robust.