Artificial Intelligence ME 768 Jan-Apr 2000
|
|
K.V.Srikanth
and
Mayank Gupta
IIT Kanpur : April 2000
A lot of work has been done in the field of graphics recognition which deals with the problem of extrcting graphic objects from scanned images. The article by [Dori/Wenyin:1999] classifies graphic objects in a class based hierarchy (dashed lines, arcs etc). Moreover, it describes the algorithm to identify these features.
Many approaches have been adopted to solve the problem. These can be classified into three groups
In our project we are going to use constraint methods to obtain 3-D wireframe model of the 2-D projections. The earlier constraint based algorithms proposed were O(n^2) where n is the no of edges. Recently, method of complexity O(n*lg(n)) has been proposed by [Sastry/Sasmal/Mukerjee:1999] . The latter one was an algorithm that dealt with only lines and we propose to extend it for arcs and other complex figures.
Our task in this porject is to generate 3-D from scanned orthographic projections of EDs. This involoves the following.
For line recognition we have used standard hough algorithm.
Hough transformation can be used to identiy lines, curves etc. The basic idea of Hough transforms is as follows.
A line in x-y coordinate system can be represented as parametric coordinates (r,#) where
Clearly, the value in the accumulator array indicates the number of pixels lying on the line. Hence the entries for which we have a large value represents a line.
After generating the accumulator array, we take its maximum entry (the average of 3 entries along the r-parameter) and find the line segments corresponding to this line. For this we make use of the link-list associated with the line.
We sort the link-list according to x-coord.(if slope<1) or y-coord(if slope>=1). Now, two consecutive entries in the link-list lie on the same line segment, if they are sufficiently close enough. We use this property to identify line ends. Then we neglet lines which are less than a specified threshold to prevent recognition of false lines.
We repeat this algorithm for all values of accumulator array above a threshold.
ExamplesHough transformation can also be used to identify circles. They are parametrised by (x,y,r) where x,y refer to the center position and r refers to circle radius. In order to reduce the amount of computation in a 3-D Hough transform, the problem is divided into two passes.
To find circle centers, first note that any given pixel on a circle, the corresponding circle center will lie on the normal to the tangent at that pixel. We define a histogram over an (x,y) parameter space which is congruent to the image. For each black pixel p we estimate the tangent as the line of best fit to all pixels within a neighbourhood centered on p (using least-square method). This allows us to compute the normal and the pixels lying on these normals are recorded. Local maximas of the histogram give the location of candidate circle centers.
Now to find the radius of the circle, we construct a 1-D histogram for each center. For each black pixel in the image we compute its distance from the center and record it in the array. Maxima of this histogram correspond to the radii of circles.
By storing the coordinates of the pixel in the privious step, we get the pixels lying on the circle. From this we can calculate the start and end of the arc of the circle.
An ellipse is defined by a five parameters but a five parameter Hough Transform is undesirable as it will make impractical computational and memory demands. We have adopted the approach which separates the task into two passes. First, we identify possible ellipse centres, this requires only a two parameter Hough Transform. Then we evaluate the remaining three parameters using a simple focusing implementation of the Hough Transform.
Ellipse centres are extracted as follows. Consider two points P and Q (see Fig. 1) on an ellipse and estimate the tangents at these points. Let T be the point where these tangents intersect and M be the midpoint of PQ. For a perfect ellipse, the ellipse centre will lie on the ray originating at M and directed away from T.
Rays formed from different pairs of image points on an ellipse will intersect at the ellipse centre. A two parameter Hough Transform can be used to accumulate these rays, with the intersection of the rays corresponding to a maximum of the histogram.
As this algorithm records an entry for each pixel pair in the image, it is computationally very demanding.
We have chosen to define the ellipse by the radius of its major and minor axes (r1 and r2 respectively) and the angle ` that the major axis makes with the x axis (see Fig. 2). To find these parameters, we assume two parameters at regular intervals and find the third parameter for each black pixel. The maximum of the array will correspond to the actual parameters.
Following is a brief outline of the proposed algorithm:
As shown in fig 3. in constraint based reconstruction, we start with a view(say front view). Now, for each geometrical element (ellipse,circle,line,vertex) in the front view, we find the corresponding element in other views. To find the corresponding elements in other views, we use constraints such as:
By using these constraints we can identify the plane in which the curve lies by finding three points lying on the plane. Then by a suitable transformation we can reconstruct the 3-D curve.
Lines in 3-D can be qualitatively classified into 7 categories. In order to describe them we need a relation Rx,Ry,Rz between the end points of the line segments. The relation Rx, says that the x-coordinates of the end points of the line segments are equal and similarly for Ry and Rz. Moreover !Rx means that the relation Rx doesn't holds. Now a line can belong to these categories.
The lines circles and ellipses generated by vectorization are not accurate
and thus we need to post process the vectorized images obtained by
hough transformations.
We developed a post processing algorithm for lines only and couldn't develop an
algorithm for circles and ellipses.This became a bottleneck in our project.
The post processing algorithm for lines is as follows.
After the line vectorization is done the lines thus obtained are some pixels off their correct positions. So what we do is for each point(End point of a line) find out all the points lying in an epsilonn radius from that point and average all of them. Two overlapping parellel lines within some epsilon distance are merged. Vectorization also gives repeated lines so finally we remove all the repeated lines. What we do next is to generate the intersection points of the lines and generate the vertices, which are required by the reconstruction algorithm. The post processed image is then ready for reconstruction.
The problem arises in the post processing of circles and ellpises because, unlike
in lines we can't just manipulate the end points to correct the image. This is
hence a far more complicated problem and hence we couldn't device an appropriate
algorithm.The results of the post processing algorithm are clear from the following
example images.
The hough transformation algorithm which we had used for circles could not detect the circles
accurately due to which a lot of post processing was requried.Since we didn't have a good
post processing algorithm for circles we entered the parameters for circles manually
to obtain the result for our original figure.
We also obtained moderate results for noisy images having only lines. This is due to
our good line detection and post processing algorithms. We could reconstruct the
noisy image .
Finally we got good results for reconstruction of an already vectorized image but couldn't
get good results for recognition.
Conclusion
The aim of our project was to completely recognise and reconstruct
the image shown in our results, we achived
the required to a certain extent. Our algorithm for
reconstruction worked perfectly for all the possible cases as demonstrated.
The algorithm for recognition worked well for lines and
the post processing algorithm
which we had used was a success for lines but, we are yet to design a good post
processing algorithm for circles and ellipse.
@Article{Dori/Wenyin:1999,
author= { Dori, Dov and Liu Wenyin},
year = {1999},
keywords= { GRAPHICS RECOGNITION, VECTORIZATION,
RASTER-TO-VECTOR, ENGINEERING DRAWINGS},
institution= { Israel Institute of Technology, Haifa and Microsoft Research
Sigma Center, Beijing},
title= { Automated CAD Conversion with the Machine Drawing
Understanding System: Concepts, Algorithms, and Performance},
pages= { 411-416},
annote= {
In this paper the authors has described the way in which graphic object
can be classified in a hierarical manner. The authors has used the
ideas of object-oriented programming languages such as Abstract
classes, Inheritance etc to build the hierarchy.
Moreover the author has described generic ways of detecting different
graphic objects in an image using the above hierarchy.
},
}
@TechReport{Sastry/Sasmal/Mukerjee:1999,
author= { Sastry, D. Sridhar and Nilanjan Sasmal and Amitabha Mukerjee },
year = { 1999},
keywords = { Engineering Drawings, 3-D Reconstruction},
institution= { IIT Kanpur},
title = { Efficient Categorization of 3D Edges from 2D Projections},
pages = { 279 - 286 },
annote= {
In this paper an efficient algorithm of reconstructing 3D wireframes
of 2D projections consisting of only lines and edges has been described.
They have used the constraint based approach in which they use the
3D relationship between the end of lines.
By this approach they have been able to remove redundant edges.
Also, the authors have proved the correctness and efficiency of
there algorithm.
},
}
This report was prepared by K.V.Srikanth and Mayank Gupta as a part of the project component in the Course on Artificial Intelligence in Engineering in the JAN semester of 2000 . (Instructor : Amitabha Mukerjee )
[ COURSE WEB PAGE ]