Course Home
Administration
Syllabus
References
Lecture Notes
Readings
Assignments
Projects
Resources


Comments? Idea?























































































































































































































































































































































Implementation of Huffman-Clowes Labeling Scheme

Final project by

Igal Shrivker

igal1984@nana.co.il

Vitali Melamud

vitali.melamud@gmail.com


Introduction

One of the challenges in computational vision is to interpret the 2d image to 3d objects we know in our life.
One of the steps in the identification is identify the depth of the image. We would like to know which objects are before other object , which surface is above other surface and etc.

In the next example:


We know how to identify abstract shape in an image that is 3D - we clearly see a CUBE. We understand that the preliminary side is in square shape, and it is the closest to us of all the shape. We also understand that the upper parallelogram is actually another side of the object that appears on the upper part of it from our point of view.
Huffman and Clowes wanted to do this interpretation by computer. And for this reason they built a catalogue that categorize every line in the image to 4 kinds:

And marked them :




After partitioning the lines of the shape into 4 signs, we know the outline of the image.
For example categorizing the shape by catalogue will bring this result:





The catalogue defines the possible relations between lines in intersection:


Thus, in iterative process we can do the categorization of all the lines in the image. Finally we can "see" what kind of 3D shape is shown in the 2D picture (by reading the categorized image)!




Approach and Method

The project consist of 5 steps:

  1. Find the edges of the image
  2. Find the equations of the lines.
  3. Partition the lines into sigments.
  4. Find the intersections and categorize them to 4 types: T,L,W,V.
  5. Run the algorithm of filtering by the catalogue.
Step 1:
For finding the edges we tried to use a few methods: finding the gradient and it thresholds, but mostly we used Canny edge detection with different parameters.


Step 2:
For detecting the lines we used the Hough transform, and for every line we chose this representation:


Thus, every edge point in the image made votes for all the lines that cut the point.
Every point could vote for exactly 180 lines as the number of degrees of all possible lines (that is the accuracy we chose).


Step 3: After we found all the lines in the image, we would like to have more information about them, as where they are located in the image.
Where is the start point of the line, and where is the end point of the line?
This segmentation helps us to find the junction points in the image, and to deal with the lines that built from a few separate segments.
We solved this problem by "stepping" on the lines that we found from the edges (in step 2), and finding the range of edge points that are actually in the image - the line is made of them.


Step 4: In the optimal situation we could find the junctions as intersection of a few lines, but in practice the intersection points are not accurate. Thus, it's not enough to look on the start and end point of the segments, we should also look around this points.
After finding the junctions we categorized them to 4 types: V,W ,T ,L for later use of the catalogue. We did it by counting the number of segments that meet in a junction (categorizing L), and by calculating the angles between each two segments in the junction.

Step 5: In this step we have all the information and we can go over all the junctions in the image and filter the impossible classification of the fragments by using the catalogue.

All of the steps are included in our friendly GUI:




Results

Here are some results of our implementation.
They are devided to 5 steps as mentioned above (except of step 2). One of the options in our implementation is to follow all the "steps" in the algorithm.

Step1 Step2 Step3 Step4 Step5
Example1:
Example2:
Example3:

Conclusions

Here are some new things we found out:

  1. It's difficult to translate an image with lines to simple computational representation
  2. Because we can't find the exact lines in the image - it's also hard to find the exact intersections
  3. Using differnts edge detector can lead to different results
  4. Small tasks as we see them (investigating a simple image) can last long time because of many computations
In general:

We think that by simplifying the problem it is possible to identify 3D objects and their relations in 2D image.
Though also this "simplyfied" task is very hard and can take much time.
Now we can truly understand how hard is to identfy any scene :)

Additional Information

References

  • Computational and Biological vision course, Ben Gurion University - link
  • Lecture by Paul Bates, Florida University - link
  • Matlab tutorials - link