gradient detection convolutions
Square instead of rectangle: to avoid problems concerning diagonal
- usually 3 x 3
- apply gradient detection convolution
- find where gradient appears
/ \ / \ / \ / \ | | | | _____________________________ <- at this line, the gradient is extreme ****************************** ****************************** ******************************
- find maximum gradient points
- edge is perpendicular to gradients
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.
- treat the picture as a graph
- each pixel is connected to neighboring pixels
- cost minimization
- cost = 1 - gradient // higher gradient, better to choose
- optionally, cost for diagonal is higher, etc.
- simply adding up cost of each step
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.
In Image Processing
- Independent var: features of the image
- Dependent var: classification(is it a dog?)
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:
- maxima of gradient
- area of gradient turns
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.
- INPUT: Image
- OUTPUT: Smaller image, that does not look distorted.
- focus objects are in frame
- no obvious distortion
- only boring parts are cut off
Use magnitude of gradient to approximate the “interestingness”.
- large gradient: an object -> interest
- low gradient: same across image -> less information
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.
- For each row, pick the least interesting pixel
- line shifts, and the image will be distorted
- Select one vertical line
- This will create a visible vertical line of discontinuous
- Make sure that pixels removed are adjacent to each other
- After selecting one pixel, select one of the 3 pixels below it.
- Pick first pixel:
- dynamic programming
- minimize cost from first row to each pixel of the next row
- for each pixel, we have a
prev, and a minimized accumulative cost
- at the last row, find the smallest accumulative cost, and follow the
prevs back up to generate the path to be cut.
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.
- look at the hole’s boundary
- find patches in the image that matches the best with the boundary’s patches
- fill the area with the patches inwards
find one patch
patch - image patch.gradient - image.gradient
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.
- remove whole persons from the scene
- replace a person from the scene
computer detection of tempering
- Although human cannot see some anomalies, computers can detect them
- 3D Geometric features:
- shadow length / light source angle
Power Snail STUDIES