The project aims to implement edge and boundary detection algorithm using Huffman and Clowes catalogue of possible trihedral vertexes types.
We aim to develop a program which given a picture with some object on it resolves all possible interpretations of boundaries of the object.
The fact that we are using the Huffman and Clowes catalogue requires the input objects to contain only vertexes that appear in the catalogue.
To apply the algorithm of relaxation labeling we first and to perform the preprocessing on the input object to resolve the vertexes and their types.
In order to do so we divided the problem to the following steps:
1. Resolve the corners of the received object:
We used Corner detector to detect the corners of the received object. An implementation of CSS (The curvature scale space technique) technique provided by X.C. He and N.H.C. Yung. was used for this purpose
2.Determine the types of the resolved corners according to trihedral model of Huffman and Clowes:
This step was pretty challenging having the corners coordinates we had to determine which lines of the object are connected to each corner and then to determine the type of the corner according to catalogue: T-junction, V-junction, Y-junction, W-junction.
The steps were as follows:
1. Apply Canny edge detector on input image to obtain the edges of the object
2. On the resulting binary image apply Hough transform for lines detection
3. The results of Hough transform are not accurate, the line segment of the object might be cut and thus their edge points do not overlap with none of the
detected corners. The problem is caused by the fact that canny edge detector smoothes the sharp corners of the object
We solved the problem in the following way:
1. For each corner find the edges of obtained segments that lie within the circle denoted by a predefined radius (threshold) and the center, which
is the location of the corner
The found edges belong to line segments that are connected to the corner on the object
2.For each corner we also had to check the case when the corner lies on the interior of the segment (see the report)
After the lines that are connected to each corner are resolved we had to determine the type of the obtained vertex:
1. T-junction
This junction type was detected when checking if the corner lies on the interior of the line segment
2.V-junction
This is the vertex that is connected only to two line segments and is not a T-junction
3. W-junction and Y-junction
For these junctions we developed test according to which we determine the type (see report). The test is based on the angle sizes of each line
segment with respect to x aces
For W-junction we also need to determine which one of three segments is in the middle. This was needed for correct assignment of label during the
relaxation labeling algorithm.
3. Apply the relaxation labeling algorithm on the received vertexes.
We used 'Consistent line drawing labeling via relaxation labeling' that was learnt in class.
4. Present the results
The output is a binary image which contains all edges of the input object. Near each edge all the valid labels are displayed.
The result are far from satisfying. The main problem is that the algorithm itself performs good
only if the input object was clear enough so all the correct object line segments were detected correctly.
Input limitations:
1. Input images have to contain objects with vertexes from catalogue only
2. The ribs of the objects must not be colored
3. There must be a sharp contrast between the colors of object's faces
4. We did not solve the problem of T-junction mentioned in the report
1.IEEE Transactions on Pattern Analysis and
Machine Intelligence, Farzin Mokhtarian and Riku Suomela, Vol. 20, NO. 12, December 1998
2.Application of the generalized Hough
transform to corner detection, E.R Davies, MA, DPhill,
CPhys, FInstP
3.A local edge detector used for finding corners, Fet Shen, Han Wang, School of Electrical and Electronic Engineering, Nanyang Technological University, Singapure
4.Site of
introduction to computational and biological vision, University Ben Gurion of the
5.Curvature scale space corner detector by X.C. He and N.H.C. Yung