Cleaning - divyadeep1/Internship_at_IITk GitHub Wiki

Cleaning of the lines generated after hough line pass requires snapping of vertices that are close to each other and splitting of intersecting lines. Before going in the details of the two processes, let's take a look at how the code is organized and what the data representation is.

Files :-

Two files are used for cleaning the lines, they are lines_to_walls.py and geometry.py, both of which are located in https://github.com/divyadeep1/Internship_at_IITk/tree/master/graph_formation.

Input :-

The lines given as output of the hough line step are written into a .json file. Each entry of the file is a python list containing the following 6 entries (in the stated order):

  1. Line number
  2. x-coordinate of one end-point of the line
  3. x-coordinate of the second end-point of the line
  4. y-coordinate of end point of line, corresponding to the first x-coordinate
  5. y-coordinate of end point of the second line, corresponding to the second x-coordinate
  6. Weight/Thickness of line in the original image
    Example - [1, 200, 300, 100, 100, 10]
    These json files are stored in https://github.com/divyadeep1/Internship_at_IITk/tree/master/json/Make%20walls.

Output :-

Output of the cleaning step is a json file having lists of lines, with the representation being the same as input lines.
These json files are stored in https://github.com/divyadeep1/Internship_at_IITk/tree/master/json/Make%20graph
NOTE- The json files, and all the files corresponding to a particular image take the name of the original image file.
The two steps involved in cleaning are stated below:

Snapping of vertices:

For every line, we iterate over every other line and find out the end points of lines that are close enough to each other and snap them. The first loop in lines_to_walls.py does exactly that. The algorithm is:

  1. For line1 in lines do:
  2. For every line2 in lines (other than line1) do:
  3. Store that point of line2 that is close to point1 of line1, if any, in a list (list1).
  4. Store that point of line2 that is close to point2 of line2, if any, in another list (list2).
  5. Replace all the points in list1 with the centroid of intersection point of all these points with point1 of line1.
  6. Replace all the points in list2 with the centroid of intersection point of all these points with point2 of line2.
    (Refer https://github.com/divyadeep1/Internship_at_IITk/blob/master/graph_formation/lines_to_walls.py for more details.)

Splitting of intersecting lines:

Intersecting lines need to be split into 4 different lines because in real world, 2 walls that seem to intersect don't go through each other, they are 4 walls that meet at a point. Keeping this in mind, we need to render the walls in 3D in the same manner. Hence, the following algorithm is used for achieving this purpose:

  1. For every line1 in lines:
  2. For every other line2 in lines:
  3. Get intersection point of line1 and line2
  4. If the intersection point lies inside the two line segments, go to next step, otherwise go to step 2
  5.  Remove the original 2 lines from the list *lines* and insert 4 new lines, where each new line consists of the   
 following two end points - 1 point from the 4 end points of the two line segments, and other end point as the  
 *intersection point*.

There's another pass that immediately follows the cleaning process - conversion of the lines' representation from [line_no., x1, x2, y1, y2, weight] to a graph structure, with the vertices as the nodes and the walls as the edges, and weight as the edge weight. This operation is performed in the walls_to_graph.py file, which is located in https://github.com/divyadeep1/Internship_at_IITk/tree/master/graph_formation as well. The location of the input and output is described below:

Input:

The output of lines_to_walls.py serves as the input for walls_to_graph.py, so naturally, the input folder is - https://github.com/divyadeep1/Internship_at_IITk/tree/master/json/Make%20walls.

Output:

The output of this pass is a json file consisting of vertices (coordinates of vertices) and an adjacency list representation of the edges.
The output files go in https://github.com/divyadeep1/Internship_at_IITk/tree/master/json/To%20extrude folder.