Fully convert a black and white image to a set of lines (aka vectorize using only lines)

Question

I have a number of black and white images and would like to convert them to a set of lines, such that I can fully, or at least close to fully, reconstruct the original image from the lines. In other words I'm trying to vectorize the image to a set of lines.

I have already looked at the HoughLinesTransform, however this does not cover every part of the image and is more about finding the lines in the image rather than fully converting the image to a line representation. In addition the line transform does not encode the actual width of the lines leaving me guessing at how to reconstruct the images back (which I need to do as this is a preproccesing step towards training a machine learning algorithm).

So far I tried the following code using the houghLineTransform:

import numpy as np
import cv2

MetersPerPixel=0.1

def loadImageGray(path):
    img=(cv2.imread(path,0))
    return img

def LineTransform(img):
    edges = cv2.Canny(img,50,150,apertureSize = 3)
    minLineLength = 10
    maxLineGap = 20
    lines = cv2.HoughLines(edges,1,np.pi/180,100,minLineLength,maxLineGap)
    return lines;

def saveLines(liness):
    img=np.zeros((2000,2000,3), np.uint8)
    for lines in liness:
        for x1,y1,x2,y2 in lines:
            print(x1,y1,x2,y2)
            img=cv2.line(img,(x1,y1),(x2,y2),(0,255,0),3)
    cv2.imwrite('houghlines5.jpg',img)

def main():
    img=loadImageGray("loadtest.png")
    lines=LineTransform(img)
    saveLines(lines)

main()

However when tested using the following

I got this image:

As you can see it is missing lines that are not axis aligned and if you look closely even the detected lines have been split into 2 lines with some space between them. I also had to draw these images with a preset width while the real width isn't known.

Edit: on the suggestion of @MarkSetchell I tried the pypotrace by using the following code, currently it largely ignored bezier curves and just tries to act like they are straight lines, I will focus on that problem later, however right now the results aren't optimal either:

def TraceLines(img):
    bmp = potrace.Bitmap(bitmap(img))
    path=bmp.trace()
    lines=[]
    i=0
    for curve in path:
        for segment in curve:
            print(repr(segment))
            if segment.is_corner:
                c_x, c_y = segment.c
                c2_x ,c2_y= segment.end_point
                            lines.append([[int(c_x), int(c_y),int(c2_x) ,int(c2_y)]])

            else:
                c_x, c_y = segment.c1
                c2_x ,c2_y= segment.end_point
            i=i+1
    return lines

this results in this image , which is an improvement, however while the problem with the circle can be addressed at a later point the missing parts of the square and the weird artefacts on the other straight lines are more problematic. Anyone know how to fix them? Any tips on how to get the line widths?

Anybody got any suggestions on how to better approach this problem?

edit edit: here is another test image : , it includes multiple line widths I would like to capture.

Answer 1

OpenCV

Using OpenCV's findContours and drawContours it is possible to first vectorise the lines and then exactly recreate the original image:

import numpy as np

import cv2

img = cv2.imread('loadtest.png', 0)

result_fill = np.ones(img.shape, np.uint8) * 255
result_borders = np.zeros(img.shape, np.uint8)

# the '[:-1]' is used to skip the contour at the outer border of the image
contours = cv2.findContours(img, cv2.RETR_LIST,
                            cv2.CHAIN_APPROX_SIMPLE)[0][:-1]

# fill spaces between contours by setting thickness to -1
cv2.drawContours(result_fill, contours, -1, 0, -1)
cv2.drawContours(result_borders, contours, -1, 255, 1)

# xor the filled result and the borders to recreate the original image
result = result_fill ^ result_borders

# prints True: the result is now exactly the same as the original
print(np.array_equal(result, img))

cv2.imwrite('contours.png', result)

Result

Scikit-Image

Using scikit-image's find_contours and approximate_polygon allows you to reduce the number of lines by approximating polygons (based on this example):

import numpy as np
from skimage.measure import approximate_polygon, find_contours

import cv2

img = cv2.imread('loadtest.png', 0)
contours = find_contours(img, 0)

result_contour = np.zeros(img.shape + (3, ), np.uint8)
result_polygon1 = np.zeros(img.shape + (3, ), np.uint8)
result_polygon2 = np.zeros(img.shape + (3, ), np.uint8)

for contour in contours:
    print('Contour shape:', contour.shape)

    # reduce the number of lines by approximating polygons
    polygon1 = approximate_polygon(contour, tolerance=2.5)
    print('Polygon 1 shape:', polygon1.shape)

    # increase tolerance to further reduce number of lines
    polygon2 = approximate_polygon(contour, tolerance=15)
    print('Polygon 2 shape:', polygon2.shape)

    contour = contour.astype(np.int).tolist()
    polygon1 = polygon1.astype(np.int).tolist()
    polygon2 = polygon2.astype(np.int).tolist()

    # draw contour lines
    for idx, coords in enumerate(contour[:-1]):
        y1, x1, y2, x2 = coords + contour[idx + 1]
        result_contour = cv2.line(result_contour, (x1, y1), (x2, y2),
                                  (0, 255, 0), 1)
    # draw polygon 1 lines
    for idx, coords in enumerate(polygon1[:-1]):
        y1, x1, y2, x2 = coords + polygon1[idx + 1]
        result_polygon1 = cv2.line(result_polygon1, (x1, y1), (x2, y2),
                                   (0, 255, 0), 1)
    # draw polygon 2 lines
    for idx, coords in enumerate(polygon2[:-1]):
        y1, x1, y2, x2 = coords + polygon2[idx + 1]
        result_polygon2 = cv2.line(result_polygon2, (x1, y1), (x2, y2),
                                   (0, 255, 0), 1)

cv2.imwrite('contour_lines.png', result_contour)
cv2.imwrite('polygon1_lines.png', result_polygon1)
cv2.imwrite('polygon2_lines.png', result_polygon2)

Results

Python output:

Contour shape: (849, 2)
Polygon 1 shape: (28, 2)
Polygon 2 shape: (9, 2)
Contour shape: (825, 2)
Polygon 1 shape: (31, 2)
Polygon 2 shape: (9, 2)
Contour shape: (1457, 2)
Polygon 1 shape: (9, 2)
Polygon 2 shape: (8, 2)
Contour shape: (879, 2)
Polygon 1 shape: (5, 2)
Polygon 2 shape: (5, 2)
Contour shape: (973, 2)
Polygon 1 shape: (5, 2)
Polygon 2 shape: (5, 2)
Contour shape: (224, 2)
Polygon 1 shape: (4, 2)
Polygon 2 shape: (4, 2)
Contour shape: (825, 2)
Polygon 1 shape: (13, 2)
Polygon 2 shape: (13, 2)
Contour shape: (781, 2)
Polygon 1 shape: (13, 2)
Polygon 2 shape: (13, 2)

contour_lines.png:

polygon1_lines.png:

polygon2_lines.png:

The length of the lines can then be calculated by applying Pythagoras' theorem to the coordinates: line_length = math.sqrt(abs(x2 - x1)**2 + abs(y2 - y1)**2). If you want to get the width of the lines as numerical values, take a look at the answers of "How to determine the width of the lines?" for some suggested approaches.

Answer 2

I made an attempt at this and am not altogether happy with the results but thought I would share my ideas and some code and anyone else is welcome to take, borrow, steal or develop any ideas further.

I think some of the issues stem from the choice of Canny as the edge detection because it results in two edges, so my first plan of attack was to replace that with a skeletonisaton from scikit-image. That gives this as the edge image:

Then I decided to use HoughLinesP rather than HoughLines, but it didn't seem to find much. I tried increasing and decreasing the resolution parameters but it didn't help. So, I decided to dilate (fatten) the skeleton a bit and then it seems to start detecting the shapes better, and I get this:

I am not sure why it is so sensitive to line thickness and, as I said, if anyone else want to take it and experiment, here's where I got to with the code:

#!/usr/bin/env python3

import numpy as np
import cv2
from skimage.morphology import medial_axis, dilation, disk

def loadImageGray(path):
    img=cv2.imread(path,0)
    return img

def LineTransform(img): 
    # Try skeletonising image rather than Canny edge - only one line instead of both sides of line
    skeleton = (medial_axis(255-img)*255).astype(np.uint8)
    cv2.imwrite('skeleton.png',skeleton)

    # Try dilating skeleton to make it fatter and more detectable
    selem = disk(2)
    fatskel = dilation(skeleton,selem)
    cv2.imwrite('fatskeleton.png',fatskel)

    minLineLength = 10
    maxLineGap = 20
    lines = cv2.HoughLinesP(fatskel,1,np.pi/180,100,minLineLength,maxLineGap)
    return lines

def saveLines(liness):
    img=np.zeros((2000,2000,3), np.uint8)
    for lines in liness:
        for x1,y1,x2,y2 in lines:
            print(x1,y1,x2,y2)
            img=cv2.line(img,(x1,y1),(x2,y2),(0,255,0),3)
    cv2.imwrite('houghlines.png',img)

img=loadImageGray("loadtest.png")
lines=LineTransform(img)
saveLines(lines)

---

In fact, if you take the code above and ignore the skeletonisation and fattening, and just use the inverse of the original image for HoughLinesP, the results are pretty similar:

def LineTransform(img): 
    minLineLength = 10
    maxLineGap = 20
    lines = cv2.HoughLinesP(255-img,1,np.pi/180,100,minLineLength,maxLineGap)
    return lines