THEORY:
   
Greedy Algorithm

  • Simple algorithm proposed by Williams and Shah for energy minimization
  • At each iteration each of n points may be moved to any point in neighborhood of size n
  • Reduces complexity to O(nm)
It allows a contour with controlled first and second order continuity to converge on an area of high image energy for edges. This algorithm allows the inclusion of hard constraints but faster than other algorithms.
        The algorithm is iterative. During each iteration, a neighborhood of each point is examined and the point in the neighborhood giving the smallest value for the energy term is chosen as the new location of the point. However, only closed contours are being closed. The quantity being minimized by this algorithm is:
                    , where
  • Econt and Ecurv are first and second order continuity constraints. They correspond to interior energy.
  • Eimage is the energy of image; measure some image quality such as edge strength or intensity.
  • α, β and γ are parameter (weight); they are used to balance the relative influence of the three terms. Their relative sizes, rather than absolute sizes are significant.
Example: a=1, ß=0 or 1, ?=1.2 (depending upon whether a corner is assumed at that location)   NEXT-->