PROJECTS AT VISL FINISHED IN 2003 | |||||||

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 costsSince 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- CrossingThis 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:
1 if
IL(
Where d d L(
Optimal pathThe 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
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 |