CV算法面试题学习

本文记录了CV算法题的学习。

点在多边形内（point in polygon）

参考自文章1，其提供的代码没有考虑一些特殊情况，所以做了改进。
做法：射线法。以待判断点A为端点，画出方向水平朝右的射线，统计该射线与多边形B的交点个数。奇数：内，偶数：外。(需考虑点A是否在B的某个点或边上是否有平行的边。)
图片来自：https://www.jianshu.com/p/ba03c600a557。

代码：

def is_in_poly(p, poly):
    """
    :param p: [x, y]
    :param poly: [[], [], [], [], ...]
    :return:
    """
    px, py = p
    is_in = False
    for i, corner in enumerate(poly):
        next_i = i + 1 if i + 1 < len(poly) else 0
        x1, y1 = corner
        x2, y2 = poly[next_i]
        if (x1 == px and y1 == py) or (x2 == px and y2 == py):  # 点p是否在多边形的某个点上
            is_in = True
            break
        if y1 == y2 :  #边是水平的，如果点在边上则break，如果不在，则跳过这一轮判断
            if  min(x1, x2) < px < max(x1, x2)and y1==py: 
                is_in = True
                break
        elif min(y1, y2) <= py <= max(y1, y2):  #边不是水平的
            x = x1 + (py - y1) * (x2 - x1) / (y2 - y1)
            if x == px:  # 点是否在射线上
                is_in = True
                break
            elif x > px:  # 点是否在边左侧，即射线是否穿过边
                is_in = not is_in

    return is_in
 
 
if __name__ == '__main__':
    #第一组，内
    point = [3, 10/7] 
    poly = [[0, 0], [7, 3], [8, 8], [5, 5]]
    print(is_in_poly(point, poly))
    #第二组，外
    point = [3, 8/7]
    poly = [[0, 0], [7, 3], [8, 8], [5, 5]]
    print(is_in_poly(point, poly))
    #第三组，有平行边，射线与边重合，外
    point = [-2, 0]
    poly = [[0, 0], [7, 0], [7, 8], [5, 5]]
    print(is_in_poly(point, poly))
    #第四组，有平行边，射线与边重合，内
    point = [2, 0]
    poly = [[0, 0], [7, 0], [7, 8], [5, 5]]
    print(is_in_poly(point, poly))
    #第五组，在某点上
    point = [7, 3] 
    poly = [[0, 0], [7, 3], [8, 8], [5, 5]]
    print(is_in_poly(point, poly))

高斯滤波器

参考文章2
高斯滤波器为线性平滑滤波器，通常假定图像包含高斯白噪声，可以通过高斯滤波来抑制噪声。
二维高斯分布公式：

其中的ux和uy是中心点坐标。

3x3滤波核的生成：

1. 先得到相对于中心点的坐标模板。
   
2. 根据公式和坐标模板得到滤波核的每个位置的值。当标准差$\sigma$为1.3时，得到的整数形式的滤波核为：
   

代码：

import cv2
 
import numpy as np
 
# Gaussian filter
 
def gaussian_filter(img, K_size=3, sigma=1.3):
 
    if len(img.shape) == 3:
        H, W, C = img.shape
    else:
        img = np.expand_dims(img, axis=-1)
        H, W, C = img.shape
 
    ## Zero padding
    pad = K_size // 2
    out = np.zeros((H + pad * 2, W + pad * 2, C), dtype=np.float)
    out[pad: pad + H, pad: pad + W] = img.copy().astype(np.float)
 
    ## prepare Kernel
    K = np.zeros((K_size, K_size), dtype=np.float)
    for x in range(-pad, -pad + K_size):
        for y in range(-pad, -pad + K_size):
            K[y + pad, x + pad] = np.exp( -(x ** 2 + y ** 2) / (2 * (sigma ** 2)))
    K /= (2 * np.pi * sigma * sigma)
    K /= K.sum() #归一化
    print(K)
    K=K[:,:,np.newaxis].repeat(C,axis=2)# 扩展维度至（K_size,K_size,C）
    print(K[:,:,0])
    print(K[:,:,1])
    tmp = out.copy()
 
    # filtering
    for y in range(H):
        for x in range(W):
            # for c in range(C):
                out[pad + y, pad + x, :] = np.sum(np.sum(K * tmp[y: y + K_size, x: x + K_size, :],axis=0),axis=0)
    out = np.clip(out, 0, 255)
    out = out[pad: pad + H, pad: pad + W].astype(np.uint8)

    return out
 
# Read image
img = cv2.imread("./lena.png")
 
# Gaussian Filter
out = gaussian_filter(img, K_size=3, sigma=1.3)
 
# Save result
cv2.imwrite("out.jpg", out)
cv2.imshow("result", out)
cv2.imshow("origin", img) 
cv2.waitKey(0)
cv2.destroyAllWindows()

结果：