Gradient Detection Convolutions, Seam Carving, and Patch March

2016-11-03 781 words 4 minutes read graphics notes

Gradient detection convolutions

Square instead of rectangle: to avoid problems concerning diagonal

edge detection

 / \    / \    / \   / \
  |      |      |     |
 _____________________________  <- at this line, the gradient is extreme

Segmentation: Intelligent Scissors

INPUT: a set of points OUTPUT: find a path(curve) that is following edge as much as possible

This is a graph traversal problem. Each pixel has some neighbors, and we choose points based on gradient at each point.


Segmentation: k-means

automatic algorithm: k neighbor

It finds pixels that are close in color-space & geometry, and connect them. By tweaking the weight of adjacency and color-space closeness, we can have different results. This can be used in color reduction. It reduces the amount of gradient exists in the graph.


Image Processing Algorithms: Machine Learning

Machine Learning Model

A black box, that takes in independent and dependent vars, and output a function that describes the relationship between those.

$$Black-Box(x, y) \to y = f(x)$$

In Image Processing

To find features, we try to find patterns of gradient in the image.

There are parts of the image that are more informative than others. It contains patterns that are robust against small changes. It will be stable across different images sharing the same pattern, despite small differences.

This could be represented by:

These are works for feature detection algorithms.

For example, a gray box.

This is easily identified, because the right angles of the square corners are a robust feature. The change in gradient pattern is consistent in different images.

Seam Carving


Seam Carving

Use magnitude of gradient to approximate the “interestingness”.

In order to get a better estimate, we might need to blur the image a little bit.

NOTE: the reason that the gradient image on Wikipedia has squares is because JPEG compression

How to decide what to remove?

In order to narrow an image for 1 pixel, every row needs to be smaller by 1 pixel.

  1. For each row, pick the least interesting pixel
  1. Select one vertical line
  1. Make sure that pixels removed are adjacent to each other

Enlarging the image with the same algorithm

Duplicate paths, from the lowest cost path to higher ones in the original image.

But this is less well-defined. Because we need to add details, there are many complications. The one rule is not to duplicate the same path over and over again.

Patch March

find one patch

the whole hole

It is only after the hole is filled, do we know whether this is done well.

It works well when there are plenty of similar patterns, it will work well.

Removing a part of a critical component, nose from the face for example, cannot work.

random selection of patches

Randomly replacing patches with better patches, until the whole patched area is smoothly integrated.

Because there are too many choices, we use randomized search to iteratively improve the patch quality.

Heuristics, for example interpolated color gradient, can be used as an initial guess.

Another improvement could be giving the algorithm more images to draw patches from.


computer detection of tempering