An Implementation of the Efros and Freeman Image Quilting AlgorithmComputer Science 766 Fall 2004 Final ProjectEric RobinsonAbstractIntroductionRelated WorkMotivationProblem StatementHigh-level Overview of the AlgorithmDetailed Discussion of the AlgorithmStep a: Patch selectionStep b: Calculate the error surfaceStep c: Determine minimum-cost boundary cutOther Implementation details:Experimental ResultsSome Possible Extensions to the Basic AlgorithmExperimental Results of the Implemented ExtensionsConcluding RemarksReferencesAppendix: Original Java Source codeImageFile.java – Used for the “processing”ImageQuilt.java – used for parsing the command line argsAn Implementation of the Efros and Freeman ImageQuilting AlgorithmComputer Science 766 Fall 2004 Final ProjectEric RobinsonAbstractThe focus of this project is an implementation of the Efros and Freeman “Image Quilting” Algorithm. The algorithm is designed to solve the texture synthesis problem in a unique way. It proposes to tile together patches of an input image in order to produce the output image. The novelty of the algorithm is in allowing neighboring patches to meet at edges that are not simply straight lines. I will specifically discuss the parameters that control the behavior of the algorithm and the experimental results that I obtained when implementing according to the original paper. After this I discuss some of the common problems that appear when applying the algorithm to structured and semi-structured textures, my thoughts on why they appear, and my proposals for how to compensate for them. I then discuss the experimental results obtained from implementing some extensions with specific emphasis on how effective the extensions were at achieving their intended goals. Finally I offer some concluding remarks on the algorithm itself, as well as on texture synthesis in general. IntroductionIn recent years advances in the technology and techniques for producing high-quality synthesized images has only been outstripped by the demand for such images. From special effects in films on the big screen to realistic virtual worlds in video games on the small screen, consumers are continually demanding more synthesized images of increasingly better quality. The additional trend of the proliferation of computing, and more specifically imaging, capabilities in places undreamed of even a decade ago (e.g. video games on cell phones) indicates that such demand will not abate any time soon. One technique researchers in computer graphics and computer vision have employed to meet this demand is texture mapping. In contrast to a three-dimensional reconstruction approach, a texture mapping approach generates a novel view from a smaller sample of the “real-world” and makes this view more realistic by mapping the appropriate visual texture onto the scene objects. Possibly the biggest advantage of this approach is that it isgenerally much faster and requires a smaller input dataset. To be successful, however, requires the availability of arbitrarily large patches of visual texture. This, in turn, drives the need for better, and faster, techniques for synthesizing large texture patches from smaller ones[1].In this project I implement a relatively recently developed technique for solving the texture synthesis problem. The technique that I implemented is commonly known as “image quilting” and was first proposed in the SIGGRAPH ‘01 conference paper, “ImageQuilting for Texture Synthesis and Transfer” by A.A. Efros and W.T. Freeman. The algorithm, some extensions, and experimental results are described in greater detail in therest of the paper. The main idea of the algorithm is to compose a large patch of texture by “stitching together” arbitrarily shaped smaller patched from the input texture – hence the term image quilting. Because I implemented an existing algorithm from a conferencepaper, this project report has a predictably strong reliance on the original paper and its cited sources. Related WorkIn [1], Efros and Freeman cite the long history of the interest in texture and how it is processed by the human visual system. Based on some of this research, in 1995 Heeger and Bergen introduced a statistical, histogram-based, approach to modeling and generating arbitrarily large patches of a stochastic texture from a given sample input texture [2]. Heeger and Bergen’s work served as the basis for many subsequent global statistical pattern focused texture synthesis algorithms. While successful for stochastic textures, these approaches have foreseeable difficulties in modeling structured and semi-structured textures[1]. As a response to the local neighborhood problems suffered by the global statistical algorithms, Efros and Leung, in 1999, proposed a “pixel-at-a-time” approach to texture synthesis based on the conditional probability distribution of a pixel value given its already generated neighbors [3]. The major drawback of this approach is, of course, the run time. Several variations on this basic approach were proposed and implemented with varying levels of success. The observation that, for the basic algorithm, the main component of the running time was the need to search the entire input image for each pixel in the output image was what prompted Efros and Freeman to develop the “patch-at-a-time” approach in [1] that is the primary focus of this project. Since the image quilting algorithm described in [1] is not an optimization of the pixel-at-a-time approach, but rather an entirely new approach, it is able to achieve a speedup of a much greater order of magnitude. MotivationAs stated in the introduction, modern techniques to meet the demand for high-quality synthetic images rely on the ability to generate arbitrarily large images of a texture from (possibly much) smaller input images. While stochastic and structured textures are challenging in their own right, the texture synthesis problem is most difficult for semi-structured textures. Early successful approaches at synthesizing structured and semi-structured textures, like the pixel-at-a-time approach in [3], were notable for their computational intensity and long running times. In [1], Efros and Freeman make the casethat the full input image searches of the approach described in [3] are unnecessary for many of the pixels in structured textures. The “image quilting” idea, that is the idea of stitching together large