Computer Vision Final Project
CS 4501: Computer Vision
Final Project - Poisson Image Editing
Tom Crossland (tcc4dr), Masood Malekghassemi (smm2rc), AJ Mehalic (ajm4ay)
Introduction and Proposal
The main project goal was to have a program capable of taking two scaled color images, called the source and the target, and cloning the source into the target such that the boundary of the source on the target appears seamless without destruction of the source. The user would choose the boundaries of the source and the target images, thus choosing a distinct set of pixels from the source and a distinct location in the target. Upon mapping the source into the target, the project them would attempt to smooth out the boundaries, removing/changing any jarring differences found across the borders of the source image by modifying the source image pixels. The project team aimed to compute such images as these:
Figure 1.1 Seamless copying of Source (bear and children) into Destination (empty pool).
Image taken from Perez et. al.
|
The exact method the project team employed is 'seamless cloning' as described in the research paper 'Poisson Image Editing' by Perez et. al.. This method works with the measured gradients across both images, modifying the insertion region by attempting to create a boundary between the images with a gradient of zero. As this appears to create a massive systems of equations, the project team decided at first at only looking at relatively small images (the specific sizes of which would be determined), and possibly only grayscale representations thereof to start. In summary, the project team hoped to understand, implement, and analyze the equations and solve-methods specified in the Perez et. al. paper.
Previous Work
Poisson image editing as described by Patrick Perez et. al. (research paper included here) is a method of smoothly cloning a sequence of pixels from one image onto another image. The image being cloned will henceforth be termed the 'source' image, and the image it is being cloned onto the 'target' image. The particular source image pixels are selected by a mask that is then mapped onto the target image. The pixels adjacent to the mask in the target image are henceforth termed the edge pixels.
The method itself is a guided interpolation, in the sense that the values desired (cloned values of the source pixels in the masked area of the target image) are found by interpolating the values of the edge pixels into the masked area of the target image under the guidance of data from the masked source image. This guidance is provided by the gradient of the source image, that is, we use the edge pixels as a set of known values and then try to move their values up and down as we progress into the masked target image area based on how the source image behaves within its masked area.
Mathematically, it's a minimization problem of an overdetermined system. The variables are the pixel values for the masked area of the target image under the guidance of the source image and, for the sake of constraining the system to the edges of the target image, the edge pixels. The edge pixels are anchored to constants (their values in the target image), while the masked pixels in the target image each receive two equations: one for setting its x-gradient to be equivalent to the x-gradient of the source image, and another for setting its y-gradient to be equivalent to the y-gradient of the source. Minimizing the error in the solution vector is a linear regression problem, which means that the overdetermined system of equations may be 'solved' by utilizing the pseudoinverse of the coefficient matrix. Upon solving for the solution vector of pixels, the selected pixels are written into the masked portion of the target image and the cloning process is complete.
Design and Implementation
Note
Because the project team had some free time before the project presentation, the team wrote a new, more user-friendly GUI. This change is not reflected in this report; however, it will be demonstrated during the final presentation. If there are questions about the new GUI, please feel free to contact the project team.
runPoisson.m
The system designed to perform seamless cloning was implemented in a series of Matlab functions. The system's main function was written as runPoisson.m. runPoisson.m takes in three different parameters: sFile, tFile, and destFile. First, the project assumes that all images will be located in and saved to somewhere in a subdirectory of the current working directory called "Images." sFile is the file name of the source picture. This is the picture that will be cropped and placed onto a target into to be seamlessly cloned. The program assumes that this is a valid color, non-grayscale image for ease of implementation. The program also assumes that the file is located a subdirectory of the "Images" directory called "Sources." sFile is the file name of the source picture. The program assumes that this is a color, non-grayscale image for ease of implementation. The program also assumes that the file is located a subdirectory of the "Images" directory called "Sources." tFile is the file name of the target picture. This is the picture that the selected source picture is being seamlessly cloned into. The program assumes that this is a valid color, non-grayscale image for ease of implementation. The program also assumes that the file is located a subdirectory of the current working directory called "Targets." destFile is the file name for the finished product of the seamless cloning. runPoisson calls other helper Matlab functions we wrote to perform seamless cloning on the specified images. First, runPoisson calls selectiveCut to get the selection of the source image that the user wants to seamlessly clone onto the target image and the location of where the user wants to perform the cloning. Using this information, the function calls the function createBeforeImg.m to illustrate the selected source image pixels mapped onto the specified location on the target image. The runPoisson function then takes the individual red, blue, and green intensities of the cut source and target images and passes them along with the cut mask to the poissonClone function. This performs the actual seamless cloning. The runPoisson function takes the seamlessly cloned intensity images and combines them into a single RGB image. The final result is the selected portion of the source image seamlessly cloned onto the target image in color. This is saved in a subdirectory of the "Images" directory called "Results."
selectiveCut.m
The selection of the source image that the user wants to seamlessly clone onto the target image and the location of where the user wants to perform the cloning need to be obtained. To do this process, selectiveCut.m was written. This piece of code was inspired by and based off of a previously implemented Matlab code for free-form selection located here. selectiveCut.m takes in two parameters: sFile and tFile. These are assumed to be the same first two inputs for runPoissom.m. The assumptions for the same inputs in runPoisson.m still hold true for the ones for selectiveCut.m. In this helper function, the source image is displayed. The user is asked to cut out a selection of the source image to seamlessly clone onto the target image. The user clicks and drags the mouse around the portion of the image they want to seamlessly clone, lassoing around the desired pixels. Upon completion of the selection, the program displays the original image, a binary mask of the selected region, a new image of the mask burned into the original image, and the masked image. An example of this visualization is provided below.
Figure 2.1 Various visualizations of the source image after selection
|
The program then creates a cut version of the masked image and the source image selection. This cut version includes only the "significant" pixels of the selected region. Therefore, the cut masked image will be a rectangle ranging from the left-most pixel in the mask to the right-most pixel in the mask and the top-most pixel in the mask to the bottom-most pixel in the mask with a one pixel border outside of the mask. The same region is cut from the source image to create the cut source image. Because of the one pixel border, pixels at the border of the source image cannot be selected to be seamlessly cloned. The program assumes that the selected portion of the source will not include any of these pixels.
The program then displays the target image. The user clicks where he or she wants to seamlessly clone the source image on the target image. This clicked location corresponds to where the center of the selected source image will be on the target image. Our implementation of seamless cloning only works when all of the pixels of the cut source correspond one-to-one with a pixel in the target. Therefore, the program will not work if the cut source is placed in such a way on the target that some of the pixels in the cut source exceed the border of the target image. The cut source image cannot be bigger than the target image. If this occurs, the user is notified and asked to replace where he or she wants the source image on the target. If a valid placement is made, the function displays the target image with the pixels corresponding to the cut mask burned. It then asks the user if he or she wants to keep this positioning. If the user answers yes through a dialogue box, the program proceeds to seamless cloning. Else, the function asks the user to reposition where he or she wants the source on the target. A visualization of the positioning acceptance process is provided below. Once the positioning is accepted, the function cuts the target image to include the pixels in the target corresponding to the pixels in the cut source image as determined by the user. The function returns the matrix represenatations of the cut source, cut mask, and cut target images. Various representations of the mask images are saved in the "Masks" subdirectory. In addition, it returns the x and y positions on the target image where the top left corner of the cut source image corresponds to.
Figure 2.2 Visualization of the positioning acceptance process
|
createBeforeImg.m
The createBeforeImg function (located in createBeforeImg.m) takes in six arguments: source, mask, target, Px, Py, and destFile. source and mask are the cut source and mask images as determined by the selectiveCut function. The target is the full representation of the target image. Px and Py are the x and y positions on the target image where the top left corner of the cut source image corresponds to. destFile is the file name of the final image as inputted by the user in the runPoisson function. The createBeforeImg function selectively copies over the pixels of the cut source image in the cut mask to their corresponding locations in the target image. It saves these images in a subdirectory of the "Results" subdirectory.
poissonClone.m
The poissonClone function (located in poissonClone.m) performs the actual Poisson image editing step. It takes in three arguments, source, mask, and target. These are all assumed to be 2-dimensional matrices of the same size. source and target are intensity image matrices (of any color scaling, ex. 0-255 integer values will work the same as 0-1.0 double values), while mask is a matrix that, when cast to Matlab's 'logical' type (values equal to 0 are set to 'false' [0], any other value is set to 'true' [1]), represents the selected locations in both source and target image matrices where the source image is to be cloned into the target. The mask must have a border of 'false' values. This implies that the original user selection must leave leave an outer border of pixels for the function to be called successfully, and that the calling function must ensure that the selection of the image passed has this border of just-outside-the-selection pixels. We will define the unselected pixels directly adjacent to the selected pixels as 'edge pixels'. The implementation itself discovers the edge pixels by shifting the mask by a single pixel in different directions and subtracting the unshifted version, thus eliminating any for-loops and allowing matlab to vectorize the operation. The number of source pixels to be used in the calculation is determined by summing over the logical mask, the number of edge pixels (and thus pixels from the target image) by summing over the logical-ORing of discovered edges, and a helper index is created by cumulatively summing over the set of all relevant locations in the logical-ORing of selected mask and discovered edges (that is, this assigns a single number to each relevant pixel). The equations to be used in the poisson image editing are one equation representing the equivalence of the gradient (calculated by successive differencing) in the 'i' direction for each selected pixel of the source and each bottom-edge pixel, another for the 'j' direction for each selected pixel of the source and each right-edge pixel, and an equation anchoring each edge pixel value to its value in target. Here we used a pair of loops over every image matrix element location because utilizing Matlab vectorization functions (such as arrayfun and bsxfun) would have resulted in convoluted code. This set of equations is placed row-by-row into the overdetermined system of equations matrix [A | b] and solved for optimally via calculating the pseudoinverse of A (in Matlab, this is by default performed via QR-decomposition, a component step of SVD). This is equivalent to finding a least-squares regression of the solution vector of pixel values. These pixel values are then mapped via for-loop into the returned target image matrix. The rate-limiting step of this whole operation is the matrix pseudoinverse calculation (O(mn^2)).
Results
Figure 3.1 Source images of a bear and children in the water.
|
|
Figure 3.2 Target image of water.
|
Figure 3.3 Binary mask and masked source selection of bear.
|
|
Figure 3.4 Binary mask and masked source selection of children.
|
|
Figure 3.5 Selected source on target after seamless cloning with left/up adjacent difference gradient calculation.
|
Figure 3.6 Selected source on target after seamless cloning with average of left-right/up-down adjacent difference gradient calculation.
|
Figure 4.1 Source image of Haunter, a Pokemon.
|
Figure 4.2 Target image of Ash from Pokemon.
|
Figure 4.3 Image before seamless cloning.
|
Figure 4.4 Image after seamless cloning.
|
Figure 5.1 Source image of Abhi Shelat
|
Figure 5.2 Target image of the Mona Lisa.
|
Figure 5.3 Image before seamless cloning.
|
Figure 5.4 Image after seamless cloning.
|
Figure 6.1 Source image of Shelat
|
|
Figure 6.2 Target image of Lawrence.
|
Figure 6.3 Image before seamless cloning.
|
Figure 6.4 Image after seamless cloning.
|
Figure 7.1 Source image of Lawrence.
|
Figure 7.2 Target image of Shelat.
|
Figure 7.3 Binary mask and masked source selections.
|
|
Figure 7.4 Image before seamless cloning.
|
Figure 7.5 Image after seamless cloning.
|
Figure 8.1 Source image of Robin Williams
|
Figure 8.2 Target image of the Royal Wedding.
|
Figure 8.3 Image before seamless cloning.
|
Figure 8.4 Image after seamless cloning.
|
Figure 9.1 Source image of Masood
|
Figure 9.2 Target image of Kim Jong-il.
|
Figure 9.3 Image after seamless cloning.
|
Figure 10.1 Source image of UFO
|
Figure 10.2 Target image of UVa.
|
Figure 10.3 Image before seamless cloning.
|
Figure 10.4 Image after seamless cloning.
|
Figure 11.1 Source image of cat
|
Figure 11.2 Target image of lady with unicorn.
|
Figure 11.3 Image after seamless cloning.
|
Figure 12.1 Source image of Lawrence.
|
|
Figure 12.2 Target image of Water.
|
|
Figure 12.3 Image before seamless cloning.
|
Figure 12.4 Image after seamless cloning.
|
Figure 13.1 Source image of the Lochness Monster.
|
Figure 13.2 Target image of the Panama Canal.
|
Figure 13.3 Image before seamless cloning.
|
Figure 13.4 Image after seamless cloning.
|
Figure 14.1 Source image of the Lochness Monster.
|
|
Figure 14.2 Target image of a pool.
|
Figure 14.3 Image before seamless cloning.
|
Figure 14.4 Image after seamless cloning.
|
Figure 15.1 Source image of a kid.
|
Figure 15.2 Target image of President Hayes.
|
Figure 15.3 Image before seamless cloning.
|
Figure 15.4 Image after seamless cloning.
|
Figure 16.1 Source image of a gull.
|
Figure 16.2 Target image of a beach.
|
Figure 16.3 Image before seamless cloning.
|
Figure 16.4 Image after seamless cloning.
|
Figure 17.1 Source image of a blimp.
|
Figure 17.2 Target image of a beach.
|
|
Figure 17.3 Image before seamless cloning.
|
Figure 17.4 Image after seamless cloning.
|
Figure 18.1 Source image of an apple.
|
Figure 18.2 Target image of a still-life painting.
|
Figure 18.3 Image before seamless cloning.
|
Figure 18.4 Image after seamless cloning.
|
Figure 18.5 Zoomed in image after seamless cloning.
|
Figure 19.1 Source image of a boat.
|
Figure 19.2 Target image of the sea.
|
Figure 19.3 Image before seamless cloning.
|
Figure 19.4 Image after seamless cloning.
|
Figure 20.1 Source image of marbles.
|
Figure 20.2 Target image of different marbles.
|
Figure 20.3 Image before seamless cloning.
|
Figure 20.4 Image after seamless cloning.
|
Figure 21.1 Source image of metal balls.
|
Figure 21.2 Target image of marbles.
|
|
Figure 21.3 Image before seamless cloning.
|
Figure 21.4 Image after seamless cloning.
|
Figure 22.1 Source image of Justin Bieber.
|
Figure 22.2 Target image of gradient.
|
Figure 22.3 Image before seamless cloning.
|
Figure 22.4 Image after seamless cloning.
|
Figure 23.1 Source image of a cat.
|
Figure 23.2 Target image of space.
|
Figure 23.3 Image before seamless cloning.
|
Figure 23.4 Image after seamless cloning.
|
Figure 24.1 Source image of a red ball.
|
Figure 24.2 Target image of a checkerboard.
|
Figure 24.3 Image before seamless cloning.
|
Figure 24.4 Image after seamless cloning.
|
Figure 24.5 Zoomed in image after seamless cloning.
|
Figure 25.1 Source image of a Monet painting.
|
Figure 25.2 Target image of another Monet painting.
|
Figure 25.3 Image before seamless cloning.
|
Figure 25.4 Image after seamless cloning.
|
Figure 26.1 Source image of a shack.
|
Figure 26.2 Target image of a foggy scene.
|
Figure 26.3 Image before seamless cloning.
|
Figure 26.4 Image after seamless cloning.
|
Figure 26.5 Zoomed in image after seamless cloning.
|
Figure 27.1 Source image of clouds.
|
Figure 27.2 Target image of the sky.
|
Figure 27.3 Image before seamless cloning.
|
Figure 27.4 Image after seamless cloning.
|
Discussion
Perception of Seamlessness
A seamlessly cloned image as observed by a human should ideally provide no discernible border. A clear difference in texture or perceived distance/shading along the boundary of the cloned pixels indicates a failing of the algorithm, the degree to which may vary along perceived color and patterning.
Strengths
The algorithm tends to succeed in seamlessly cloning source images into target images when the edge pixels of the masked source vary similarly to the edge pixels of the target image. Similar textures in patterning may vary wildly in color along the relevant edges and still perform well in the seamless cloning algorithm. Fundamentally, this is due to the algorithm working on the idea of guided interpolation with gradients: so long as the pixels may vary with the gradients and still match closely with the edge pixels, the algorithm succeeds in its purpose. Thus, with already similar patterning of relative pixel values, the algorithm merely needs to vary large swathes of pixel colors by relatively constant amounts thus maintaining closeness to the guiding gradient. Examples of cloned images that we considered good are amongst Figures 3.5, 4.4, 8.4, 9.4, 14.4, 17.4, and 18.4.
Computationally, this algorithm is favorable in that it doesn't get stuck in local minima - there's only a single possible minimum error in an overdetermined linear system of equations.
Weaknesses
High frequency textures interacting with low frequency textures along the edge pixels cause a clear seam in the image, due to the algorithm being incapable of varying the patterning of solution pixels too far from the source gradient despite the vastly different gradient located just outside of the mask; the algorithm simply isn't meant to work with this kind of data, as it considers only gradients, and when those don't match up it has no other information to fall back on to modify the equations or acquire a better fit than that provided by the gradient. Good examples include Figures 5.4 (there's a discernible line between the canvas texture and skin texture), 11.4, 12.4, 15.4, 18.4 (look especially at Figure 18.5 - it reveals the texture of the canvas and artist strokes in the original image not making it onto the cloned pixels), and 19.4 (look closely at the water just around the boat and the still water surrounding it).
The algorithm also for different intensities of backgrounds of source and target images may wash out the source pixels cloned into the target, changing their colors significantly. While this is usually desirable, on occassion it may result in some strange discolorations. Clear examples include Figures 4.4, 5.4, 6.4, 7.4, 10.4, 13.4, 15.4, 16.4, 22.4, and 23.4.
The algorithm's performance depends on the ratio of selected pixels to edge pixels. Selecting pixels such that the ratio of selected pixels to edge pixels is large causes the algorithm to effectively weight (because this is effectively a linear-regression algorithm) the patterning of the textures in the selected pixels higher, and thus more likely that differing texture patterns will be noticeable over the patterns that bleed through from the edge via the interpolation calculations. The vice-versa also occurs.
Due to the algorithm anchoring only the edge pixels of the target image, if the masked source just so happens to have a pixel border and gradient matching exactly that of the target image or is very similar, the seamlessly cloned image will be no different than the normally cloned image. This is only a minor concern, as in real world data the chance of this occurring is negligible.
What this algorithm doesn't accomplish (and what it wasn't purposed to accomplish, but it's worth mentioning these anyway), is making the seamless images appear to be properly three-dimensionally oriented or deal with lighting beyond that provided already by the source and target images. Note the inconsistencies of specular highlighting in Figures 20.4 and 21.4, as well as shadow differences in Figures 6.4 (unnaturally light highlighting across the face), 7.4 (unnaturally dark shadows below the ridge of the brow), 13.4 and others (any small change in lighting between scenes produces these artifacts).
Different Gradient Measurement Methods
One of the strange things we noticed with our algorithm was our choice of how we measured the gradient. Anchoring the edge pixels and assigning the x and y gradients of selected pixels to be the average of left-right or up-down adjacent differences resulted in much more washed-out images than taking the gradient as the adjacent differences at each pixel. This is due to the left-right/up-down averaging process effectively smoothing the gradient of each pixel, causing relative peaks to diminish and relative valleys to fade. This provides less variation, which gives the gradient more uniformity, which consequently gives the algorithm's linear-regression step more freedom to minimize color variation at the edge pixels and degrade the contrast of the source image, especially for images chosen with relatively constant edge pixel values. The phenomena can be observed by comparing the results in Figure 3.5 (one-sided adjacent) and Figure 3.6 (average of both sides).
References
Patrick Pérez, Michel Gangnet, and Andrew Blake. 2003. Poisson image editing. ACM Trans. Graph. 22, 3 (July 2003), 313-318. DOI=10.1145/882262.882269 http://doi.acm.org/10.1145/882262.882269"