PROJECTS AT VISL FINISHED IN 2003


Intelligent Scissor for edge detection

by Shirli Cohen and Keren Zimbelman
Supervised by Idan Shatz

Abstract

The purpose of this project is to realize and implement an algorithm for edge detection in a picture. The algorithm was proposed by Eric N.Mortensen and William A.Barrett in an article published by them at 1995: ""Intelligent Scissors for Image Composition"".


The Background:

Digital image composition has recently received much attention for special effects in movies and in a variety of desktop application. The goal of image composition is to combine objects or regions from various still photographs or movie frames to create a seamless, believable, image or image sequence which appears convincing and real. This project describes a new, interactive, digital image segmentation tool called ""intelligent scissors"" which allows rapid object extraction from arbitrarily complex backgrounds.


The Basic Approach:

Boundry definition via dynamic programming can be formulated as a graph searching problem where the goal is to find the optimal path between a start node and a set of gole nodes. As applied to image boundary finding, the graph search consists of finding the globally optimal path from a start pixel to a goal pixel- in particular,pixels represents nodes and edges are created between each pixel and its 8 neighbors. Optimality is defined as the minimum cumulative cost path from a start pixel to a goal pixel where the cumulative cost of a path is the sum of the local edge costs on the path.
Local costs
Since a minimum cost path should corresponds to an image component boundary, pixels that exhibit strong edge features should have low local cost and vise-versa. Thus, local component costs are created from the various edge features: Laplacian zero-crossing (fz), Gradient Magnitude (fg), Gradient Direction (fd). The local costs are computed as a weighted sum of these component functionals. Letting L(p,q) represent the local cost on the directed link from pixel p to a neighboring pixel q, the local cost function is:
L(p,q)=Wz*fz(q)+Wd*fd(p,q)+Wg*fg(q)
Where each W is the weight of the corresponding feature function.

Fz: Laplacian Zero- Crossing
This a binary edge feature used for edge localization. The laplacian image zero- crossing corresponds to points of maximal gradient magnitude. Thus, these points represent &qout;good&qout; edge properties and should have a low local cost. If IL(q) is the laplacian of an image I at pixel q, then:

 Fz(q)={ 0   if   IL(q)=0

              1   if   IL(q)0

Fg: Gradient Magnitude
Gradient magnitude provides a direct correlation between edge strenght and local cost. If Ix and Iy represent the partials of an image I in x and y respectively, then the gradient magnitude G is approximated with:
G=sqrt(Ix2+Iy2).
The gradient is scaled and inverted so high gradients produce low costs and vise-versa. thus, the gradient component function is:
fg = [max(G)-G]/ max(G) = 1- G/max(G)
giving an inverse linear ramp function. To keep the resulting maximum gradient at unity, fg(q) is scaled by 1 if q is diagonal neighbor to p and by 1/√2 if q is a horizonal or vertical neighbor.

Fd: Gradient Direction
The gradient direction adds a smoothness constraint to the boundary by associating high cost for sharp changes in boundary direction. The gradient direction is the unit vector defined by Ix and Iy letting D(p) be the unit vector prependicular to the gradient direction at point p:

 Fd(p,q)=2*{acos[dp(p,q)]+acos[dq(p,q)]}/3π

Where

dp(p,q)=D(p)*L(p,q)

dq(p,q<)= L(p,q)* D(q)

L(p,q)={ q-p;          if   D(p)*(q-p)≥0

               p-q; if D(p)*(q-p)<0

The neighborhood link direction associates a high cost to an edge or link between two pixels that have similar gradient directions but are perpendicular, or near perpendicular, to the link between them. Therefore, the direction feature cost is low when the gradient direction of the two pixels are similar to each other and the link between them.

Optimal path
The optimal path is defined as the shortest path (minimum cost) from one initial point to any other point on the graph. The direct graph search for an optimal path is choosen to be found (in this project) by Dijkstra algorithm.

Tools

In this project we used the PC workstations of the VISL lab. The language programming we used is Matlab.


Conclusions and Results

Intelligent Scissors provides an accurate and efficient interactive tool for object extraction and image composition.Figure 1 shows the border defined using Intelligent Scissors. It can be seen that the border that was found by intelligent scissors is very accurate. The technique:
The complite border is created by fragments. At the beginning the user selects the initial seed point and marks an area arround desired object. In every fragment the optimal path is defined as the mutual path of 3 optimal pathes. This 3 pathes have been created from 3 adjacent points to an initial seed point. The last point of this fragment is now the inial seed point of the next fragment. This process repeats itself until all the border is found. It can be noticed in the figure 1, that the algorithem creates the border of the object (the red line) from the nodes that where marked by the user. .

Figure 1 - Finding the optimal path.



Figure 2 - The GUI screen .

The GUI panel enables a good interface with the user, that can select objects from the left picture and paste them on the right picture (as shown in figure 2).

Acknowledgment

We are grateful to our project supervisor Idan Shatz for his help and guidance throughout this work.
We are also grateful to the Ollendorf Minerva Center Fund for supporting this project.

FULL DOCUMENTATION