Digital image composition has recently received much attention for special effects in movies and in a variety of desktop application.
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.