This project deals with locating picture edges by modeling the picture as a Markov Random Field. Nowadays automatic processing of pictures as a way of understanding their content is a major issue.
Abstract
This project deals with locating picture edges by modeling the picture as a Markov Random Field. Nowadays automatic processing of pictures as a way of understanding their content is a major issue. In our expedition to the world of pixels we have tried to show that this approach can provide a solution that does not fall from gradient based algorithms in dealing with edge detection.
The Project goal
- To create an Algorithm for Edge Detection based on Markov Chains
- To illustrate the fact that the blob boundary finding problem can be formulated as a ML estimation problem within a Markov Random Field setting
Background
- The images treated consist of an underlying picture blob of constant gray level surrounded by a constant gray level background
- A Noisy image consists of a White Gaussian noise field that is superimposed on the original image in order to create the resulting picture function
- A Blob boundary is estimated by maximizing the joint likelihood of a hypothesized blob boundary and all of the image data contained in the directional derivative (Gradient)
How do we compose the blob boundary?
Pixel by pixel. The decision is made for each pixel as to where to go next: Left, Right or Forward. The decision is performed “In motion” and is based on the nearest neighborhood.
The Algorithm Basics
The Algorithm deals with boundaries in two kinds of pictures:
- Clear pictures (With no AWGN superimposed)
- Noisy pictures (AWGN superimposed)
For Clear pictures:
- Calculate the Local Gradient in each direction:
The Calculation is simply the difference of pixel value in each direction (Left, Right or Forward).
- Calculate the angle weight:
The following model will calculate the weight of each possible angle:
- c is a normalization constant
- b is a control parameter of the contrast between angles
The decision rule is actually a MAP estimator:
Is the t+1 boundary element.
are the pixel values.
… After some computations we get:
This Model is based on two criteria:
- “Punish” boundaries of high curvature
- Give high priority to advancing in the Local Gradient direction
For Noisy pictures:
Some definitions:
Is the noise value of the pixel i.
Is the value of the pixel i for the clear picture.
Is the value of the pixel i for the noisy picture.
We start with 
and after some algebra we get
with
This Model is based on the same criteria that are used by the clear picture model.
Tools
The algorithms have been developed using MathWork’s MATLAB.
Conclusions
- We succeeded in creating an Algorithm for Edge Detection based on Markov Chains
- The blob boundary finding problem can be formulated as a ML estimation problem and it has been shown that it doesn’t fall below gradient based algorithms
Acknowledgement
We would like to thank Tsachy Weissman who has been a great guide and teacher.
We would also like to thank Johanan Erez who always had time to see us and his door was always open for our problems.
Last, but not least, we would like to mention the “Ollendorff Minerva Center Fund” (Ollendorff Minerva Center )
which constantly supports the laboratories research projects and many of the lab’s equipment and software.