Frankenstein: A "Live" wire Segmentation Tool

Navigation Path : Home Page > Computer Vision Homeworks > Frankenstein: A "Live" wire Segmentation Tool

• Authors : Sasakthi Abeysinghe, Timothy Simpson
• Date: 05/06/2006

• Problem Specification <Click Here...>

• Source Code and Binaries - Coded in C# .net (Needs the .net runtime to execute)
  • <Click here to download...>

• Tasks Completed
  • Loading and Saving Images.
  • Specifying which edge-detection operator to use.
  • Live-wire segmentation of an image.

GUI Layout and Operation Modes

Source Image View In this view the source image is displayed, and the user can use the mouse to segment the image. Left click to finish last segmentation operation and to start a new segmentation operation Right click to cancel the current segmentation operation
Grayscale Image View In this view the user can segment the image based on a grayscale representation of the original image.
Edge Detected Image View Here the user can see how the edge detection filter detected edges in the image... While this mode can also be used to segment the image, it is more useful when used as a tool to determine which Edge detection operator works best with the image, and to see what threshold is optimal in highlighting the edges that you want.

Algorithm Description

First, we allow the user to load a source image. Upon loading, we convert the source image to a grayscale image and then the edge detection algorithm is run on this grayscale image using the specified edge detection operator (a 3x3 mask). Thereafter the edge and non-edge regions are separated using a user-specified threshold. As the edge detection operator and threshold are user configurable, it allows the user to better view detected edge images. Included operators are Sobel, Prewitt, Robert's Cross, Kirsch, and Robinson. To capture edges aligned in any angle, we use two orthogonal edge detection masks for each 2D point on the image, and thereafter calculate the weighted score by using the square root of the sum of the squares.

Ex: Using the Sobel operator on a specific image location, with a Specified Threshold

i = The intensity at grayscale image pixel (x,y) and its 8 neighbor pixels

32	223	199
59	227	214
60	194	209

OX = The Sobel Operator for the X direction

-1	0	1
-2	0	2
-1	0	1

OY = The Sobel Operator for the Y direction

1	2	1
0	0	0
-1	-2	-1

(The following equation is in the Matlab syntax)

Edge Value = sqrt ( power ( sum ( sum ( i .* OX ) ) , 2 ) + power ( sum ( sum ( i .* OY ) ) , 2) ) = 626.3194

If the above Edge Value is above the Threshold, then the pixel is marked as an edge pixel, and the Edge intensity is specified by the size of the Edge Value. If it is below the threshold then the pixel is marked as a non-edge pixel.

 

Second, we take a user's input click to begin the wire and calculate shortest path information for the entire image. To do this, we treat the image as a graph, connecting the 4 neighboring pixels with weighted edges.

• If the pixel being considered was marked as an edge pixel then the weight of the edge in the graph w, is the difference between the maximum possible Edge intensity m, and the actual Edge intensity. a. (w = m - a). This ensures that the cost when traversing between any two pixels is minimum when in a region with a high edge value.
• If the pixel being considered was marked as a non-edge pixel then the weight of the edge in the graph w, is set to be a very high value which is larger than the maximum possible edge intensity. This is done to make the cost of traveling into a non-edge pixel very high, thereby making the live-wire avoid non-edge pixels whenever possible.

Starting with the input node, we perform a breadth-first search and update all surrounding nodes with the lowest neighboring cost until all nodes have stabilized. We use a priority queue to ensure that lowest cost nodes are considered first, ensuring that the fewest number number of iterations. This step could probably be optimized or partially computed upon image loading, but as it stands this step only takes a few seconds to complete. When this process is done we will have the minimum spanning tree with the point the user clicked as the minimum spanning tree.

Ex: A minimum spanning tree calculation for a given 3x3 graph

Following are the edge weights incurred when visiting each pixel... Assume that the user clicked the middle pixel.. we will calculate the Minimum spanning tree to reach the surrounding 8 pixels. We will call this table C.

5	7	15
18	5	32
23	12	17

First Step is to initialize the root node and build the MST, We put the root node into the priority queue (2,2)

.	.	.
.	0	.
.	.	.

We get the first element in the priority queue and calculate the cost to reach its 4 neighbors (To reach the top neighbor the cost is MST(2,2) + C(2,1)). For each neighbor visited, we add the neighbors to the priority queue.

.	7	.
18	0	32
.	12	.

We perform the above step for each element in the priority queue. When considering a pixel which has already been visited, we update the MST and put the pixel in the priority queue only if the new cost for reaching the pixel is lower than the current cost. Finally we get the following MST

12	7	22.
18	0	32
35	12	29

Third, as the user chooses moves the mouse on the image we can easily work our way backwards to find the path to the root node (which was the original click point). For each pixel of the path, the earlier path location is found by getting its current cost c, and its weight w, and finding which one of its neighbors has the value w-c.

Finally, we iterate along this minimum path, drawing our "wire" over our image until the user clicks again to stop. At this point we update the source image with the "wire", making it a permanent addition. This enables us to run edge detection on our wires, if we so choose at a later time.

Decisions taken

We chose not to display the vector map for shortest path since it was unclear how useful this would be. Given our implementation, the vector map would change on each click, and so it would only be useful during the drawing stage. Unfortunately, this is exactly when most people would want to be looking at either the edges or the source image.

We decided to use a user-configurable threshold to give the user the option of ignoring very light edges if need be.

We decided to offset the non-edge regions of the image (those below the threshold) with a very high edge weight in order to encourage a path that traverses mostly along edges.

We decided to let the user have a choice of one of five common edge detection operators. This was based on the assumption that for different input images different edge detection operators might function much better.

We decided that pre-computing the minimum spanning tree on each mouse click (which takes about 5 seconds) was an acceptable delay for a much faster run-time performance when the user was moving the mouse.

Problems and Future Work

1. The path is not very accurate in areas of high density of edges. It will run through the middle of many edges rather than run along any one particular edge. The results can usually be improved by adjusting the threshold and by changing the penalty of the non-edge pixels. But the exact values for the threshold and the penalty are image dependant, and thus cannot directly be solved using an automated technique. (See following images for an example of this problem)
2. The algorithm seems to favor medium-strength broad edges over high-strength fine edges. Depending on the source image, this can either be a good thing or a bad thing. This can most likely be controlled by increasing the disparity in edge weights to favor strong edges (perhaps by squaring the edge strengths).

Test Case #1 - Rusty saw blade

The Source Image Notice the large amount of detail in the surrounding grassy area, and also the large amount detail in the wood texture.
Segmenting the Saw The saw was segmented using 4 clicks for the outer ridge, and 3 clicks for the inner circle Note the inaccuracies in the outer edge on the left. This is due to the fact that the edges in that region are so low contrast that they are almost invisible to the human eye.
The Edge Map The edge map of the above segmented image.
Segmenting the concrete base This region was segmented using 3 clicks. Note the grassy region picked up on the left. This problem is most possibly due to the overabundance of edges detected in the edge image. This problem might be solvable by trying to add a snake type energy minimization technique. Note the wire crossing through the patterned area of the wood, this too is caused because of the overabundance of close edges. Although the most visually appealing scenario would have been if the edge traveled along the saw and then traveled along the outermost region of the wood, the algorithm has no way of determining which is more visually appealing.

Test Case #2 - Lilies in the pond

This was segmented by clicking on two points. The threshold was set to 0. Note how the path sometimes cross non-edge regions to reach its destination. We will solve this problem by adjusting the threshold in the next image
Here we have increased the threshold value but clicked on the same two points. Note how in this image the path follows only pronounced edges, and follows non-edge regions only when it is unavoidable.
In this picture we see how the algorithm reacts to areas with a high-density of edges. The leaves and the outer region of the flower was traced without any issues, but when we look at the inner region of the flowers we see that instead of tracing through the fine detail, the wire just cuts across the region. This is caused because that region contains a large concentration of edge points, and the cost of traveling that path while visiting the non-edge pixels is still better than the cost of traveling the long distance along the edge to reach the destination. We can fix this problem by changing the penalty when traveling in non-edge pixels, but the exact value for the penalty must be determined only through experimentation.