Image scaling by seam insertion, preservation of a polygon

Jordan Kaye - 10/23/10

Seam Insertion

Increasing image size by insertion of low-energy seams is very similar to image reduction by seam carving. The least noticeable seams are found by dynamically analyzing the gradient matrix in the same method as before; however, rather than choosing the least noticeable seam as we did for seam removal, we instead choose the kth least noticeable seam (where k ranges from n to 1). This prevents the algorithm from choosing the same seam multiple times, which would create an extremely ugly artifact of stretched pixels. Once the kth seam is found, the seam is inserted by averaging the two neighboring pixels on either side of the seam location, creating a smooth and even transition that leaves no artifact. This algorithm works both horizontally and vertically as it did with seam removal, although certain images are better suited to a specific orientation for the seam insertion.

Interesting results

Unscaled image:

50 seams inserted horizontally:

50 seams inserted vertically:

For the image of the puppies, both insertions were successful. Because there is a relatively generic background, it is simple for the algorithm to find good seams both vertically and horizontally. This is not true for every image, however. For example:

Unscaled image:

50 seams inserted horizontally:

50 seams inserted veritcally:

The horizontal insertion worked very well, and no artifacts exist. The vertical insertion, however, failed. The algorithm couldn't determine good enough seams, causing the strange stretching that can be seen on the left.

Polygon preservation during seam removal

During a seam removal, sometimes a one might want to preserve a certain area of an image (or conversely, delete a certain part first). This can be accomplished by applying a weighted bitmask to the gradient matrix of an image. Adding a negative weight will make it more likely for the polygon to be removed, while adding a positive weight will make it unlikely for that seam to be chosen. My algorithm allows the user to enter the weight that they desire to be added to their gradient matrix (which can be chosen based on the importance of the preservation).

Interesting results

My algorithm had a shortcoming: although it could effectively eliminate or preserve the area specified by the user, the new seams that were chosen as a result of the bitmask weighing usually resulted in very noticeable artifacts when removing an area rather than preserving one. For example:

Unscaled image:

Image with 50 seams removed (weight of 1):

Image with 50 seams removed (weight of -1):

For the preservation of the puppy, the algorithm worked well. The puppy on the right was untouched by the seam removal. The removal of the puppy was not as successful, however. Although seams were chosen well (notice that the left puppy is ignored), serious artifacts remain that make the image ugly. Even if enough seams are chosen to completely remove the puppy, other artifacts still exist:

The entire puppy is successfully removed, but there is a visible boundary where the removed object originally existed.

A possible solution to this would be some kind of averaging of the pixels after each seam is removed (this could help to prevent edges like the one seen above). The best solution would be to choose seams in an even more specific way in order to prevent an increase in total gradient energy, since adding an edge increases the overall energy.

Source files