用 Python 实现“文档扫描”

“扫描全能王” 是我手机里一直都有的 App，我非常喜欢把一些纸质内容电子化，比如书中看到的喜欢的段落、日常生活中的票据、产品说明书等等。

如下图所示，只需要拍一张照片，App 就会自动识别文档的边缘，并将文档转换为“正视图”。

实际上这个 App 用到的算法非常简单，核心就是“边缘检测 + 透视变换”，下面我们就用 Python 和 OpenCV 实现一个简单的 Demo。我用 Tkinter 做了个简单的 GUI ，可以支持手动选择文档的角点，代码地址在：

https://github.com/insaneyilin/document_scanner

边缘检测

第一步是检测目标文档的边界，即找出四条边，最容易想到的就是边缘检测算法。我们直接用 Canny 算法得到图像中的所有 Edges。

接下来我们需要找到我们需要的文档边界。这里图像比较“干净”，我们可以用 OpenCV 自带的 findContours() 找到所有的轮廓，然后取面积最大的轮廓并用四边形近似即可：

def find_corners_by_approx_contour(input_image):
    corners = []
    image = input_image.copy()
    # convert to grayscale and detect edges
    gray_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
    gray_image = cv2.GaussianBlur(gray_image, (5, 5), 0)
    edged_image = cv2.Canny(gray_image, 50, 100)
    # cv2.imshow("edged", edged_image)
    # cv2.waitKey(0)
    # find contours
    cntrs, _ = cv2.findContours(edged_image.copy(), cv2.RETR_LIST, cv2.CHAIN_APPROX_SIMPLE)
    cntrs = sorted(cntrs, key = cv2.contourArea, reverse=True)[:5]
    # loop over the contours, find approx with 4 points
    for c in cntrs:
        # approximate the contour
        peri = cv2.arcLength(c, True)
        approx = cv2.approxPolyDP(c, 0.02*peri, True)
        if len(approx) == 4:
            corners = approx
            break

    return corners

还有一种做法是利用 Hough 变换 找到相应的直线段，通过一些规则得到文档边界，可以参考这里。

透视变换

接下来我们把检测到边界的文档“摆正”。这里需要用到“透视变换”（Perspective Transformation）的概念。

透视变换(Perspective Transformation)是将图片平面投影到一个新的视平面(Viewing Plane)，可以实现平面图像的透视形变。

设 (u, v) 为原始图像坐标，变换后的图像坐标为 (x, y)，变换矩阵为 M (3x3 矩阵)，则透视变换可以表示为：

$\left[ \begin{array}{c} x^{\prime} \\ y^{\prime} \\ w^{\prime} \end{array} \right] = M \left[ \begin{array}{c} u \\ v \\ 1 \end{array} \right]$
$x = x^{\prime} / w^{\prime}, y = y^{\prime} / w^{\prime}$

变换矩阵 M 可以分拆成四个部分

$M = \left[ \begin{array}{ccc} m_{11} & m_{12} & m_{13} \\ m_{21} & m_{22} & m_{23} \\ m_{31} & m_{32} & m_{33} \end{array} \right]$

线性变换部分（rotation，scaling，shearing）：

$\left[ \begin{array}{cc} m_{11} & m_{12}\\ m_{21} & m_{22} \end{array} \right]$

平移部分：

$\left[ \begin{array}{c} m_{13}\\ m_{23} \end{array} \right]$

透视投影部分：

$\left[ \begin{array}{cc} m_{31} & m_{32} \end{array} \right]$

可以看出仿射变换是透视变换的一种特殊形式。

矩阵 M 实际只有 8 个自由度。因此我们只需要 4 对点（一对点的 x、y 坐标各有一个方程）就可以求解出对应的变换矩阵。

下面看一个将正方形变换为一个一般四边形的例子。

$\begin{array}{c} (0,0)\rightarrow(x1,y1) \\ (1,0)\rightarrow(x2,y2) \\ (1,1)\rightarrow(x3,y3) \\ (0,1)\rightarrow(x4,y4) \end{array}$

根据变换公式我们可以列出方程组：

$\begin{cases} x_1 = \frac{m_{13}}{m_{33}} \\ y_1 = \frac{m_{23}}{m_{33}}\\ x_2 = \frac{m_{11} + m_{13}}{m_{31} + m_{33}} \\ y_2 = \frac{m_{21} + m_{23}}{m_{31} + m_{33}} \\ x_3 = \frac{m_{11} + m_{12} + m_{13}}{m_{31} + m_{32} + m_{33}} \\ y_3 = \frac{m_{21} + m_{22} + m_{23}}{m_{31} + m_{32} + m_{33}} \\ x_4 = \frac{m_{12} + m_{13}}{m_{32} + m_{33}} \\ y_4 = \frac{m_{22} + m_{23}}{m_{32} + m_{33}} \end{cases}$

求解方程组即可以得到将一个正方形变换为指定四边形的透视变换矩阵。

反之，我们也可以得到将任意一个四边形变换为正方形的透视变换。我们通过两次变换：四边形变换到正方形+正方形变换到四边形就可以将任意一个四边形变换到另一个四边形。

回到代码，我们只需要找到刚刚检测到的文档边界四边形的四个顶点和要变换成的“正视图”矩形的四个顶点的对应关系，然后调用 getPerspectiveTransform() 即可以得到透视变换矩阵，最后调用 warpPerspective() 即可以实现“文档扫描”的效果了。相关代码如下，注意这里的 sort_rect_points() 就是按照一定顺序给边界的四个顶点排序，排序后我们自然就得到了对应关系。

def sort_rect_points(points):
    mass_center = get_mass_center(points)
    top_pts = []
    bottom_pts = []
    for pt in points:
        if pt[1] < mass_center[1]:
            top_pts.append(pt)
        else:
            bottom_pts.append(pt)

    if len(top_pts) > 2:
        idx = np.argmax(top_pts, axis=0)[1]
        bottom_pts.append(top_pts[idx])
        top_pts.pop(idx)
    if len(bottom_pts) > 2:
        idx = np.argmin(bottom_pts, axis=0)[1]
        top_pts.append(bottom_pts[idx])
        bottom_pts.pop(idx)

    tl = top_pts[0] if top_pts[0][0] < top_pts[1][0] else top_pts[1]
    tr = top_pts[1] if top_pts[0][0] < top_pts[1][0] else top_pts[0]
    bl = bottom_pts[0] if bottom_pts[0][0] < bottom_pts[1][0] else bottom_pts[1]
    br = bottom_pts[1] if bottom_pts[0][0] < bottom_pts[1][0] else bottom_pts[0]

    return tl, tr, br, bl

def apply_four_point_perspective_transform(input_image, points):
    (tl, tr, br, bl) = sort_rect_points(points)

    # compute the width of the new image, which will be the
    # maximum distance between bottom-right and bottom-left
    # x-coordinates or the top-right and top-left coordinates
    width_1 = math.hypot(br[0]-bl[0], br[1]-bl[1])
    width_2 = math.hypot(tr[0]-tl[0], tr[1]-tl[1])
    max_width = max(int(width_1), int(width_2))

    # compute the height of the new image, which will be the
    # maximum distance between top-right and bottom-right
    # y coordinates or the top-left and bottom-left y coordinates
    height_1 = math.hypot(tr[0]-br[0], tr[1]-br[1])
    height_2 = math.hypot(tl[0]-bl[0], tl[1]-bl[1])
    max_height = max(int(height_1), int(height_2))

    # now that we have dimensions of the new image, construct
    # the set of destination points to obtain a "birds eye view",
    # (i.e. top-down view) of the image, again specifying points
    # in the top-left, top-right, bottom-right, bottom-left order
    dst = np.array([
                   [0, 0],
                   [max_width-1, 0],
                   [max_width-1, max_height-1],
                   [0, max_height-1]], dtype="float32")

    # compute the perspective transform matrix and then apply it
    rect_pts = np.array([
            [tl[0], tl[1]],
            [tr[0], tr[1]],
            [br[0], br[1]],
            [bl[0], bl[1]]], dtype="float32")
    persp_trans_mat = cv2.getPerspectiveTransform(rect_pts, dst)
    warped_image = cv2.warpPerspective(input_image, persp_trans_mat, (max_width,max_height))
    # return the warped image
    return warped_image

参考资料

http://www.pyimagesearch.com/2014/09/01/build-kick-ass-mobile-document-scanner-just-5-minutes/

https://blog.csdn.net/xiaowei_cqu/article/details/26471527

Yilin's Blog

用 Python 实现“文档扫描”

边缘检测

透视变换

参考资料

categories