一些工作中经常会用到的算法

• IOU 的计算

  bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
      int area_rec1 = (rec1[3] - rec1[1]) * (rec1[2] - rec1[0]);
      int aera_rec2 = (rec2[3] - rec2[1]) * (rec2[2] - rec2[0]);
  
      int w = max(0.0, min(rec1[2], rec2[2]) - max(rec1[0], rec2[0]));
      int h = max(0.0, min(rec1[3], rec2[3]) - max(rec1[1], rec2[1]));
  
      int intersect = w * h;
      return intersect /(rec1_area + rec1_area - intersect);
  }

• resnet 残差(pytorch)

  class BasicBlock(nn.Module):
      """ 假设输入通道和输出通道一致 """
      def __init__(self, in_channels, out_channels):
          super(BasicBlock, self).__init__()
          self.conv1 = nn.Conv2d(in_channels, out_channels, 3, 1, 1)
          self.bn1 = nn.BatchNorm(out_channels)
          self.relu = nn.ReLU(inplace = True);
          
          self.conv2 = nn.Conv2d(out_channels, out_channels, 3, 1, 1)
          self.bn2 = nn.BatchNorm(out_channels)
          
          self.shortcut = nn.Sequential()
          if in_channels != out_channels:
            self.short_cut = nn.Sequential(nn.Conv2d(in_channels, out_channels, 3, 1, 1),
                                           nn.BatchNorm(out_channels))
          
      def forward(self, x):
          out = self.relu(self.bn1(self.conv1(x)))
          out = self.bn2(self.conv2(x))
          out += self.shortcut(x)
          return self.relu(out)

• 翻转图像、反转图像、旋转矩阵、图像渲染、图像重叠

  // 832. 翻转图像
  vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
      if(A.size() == 0 || A[0].size() == 0) return A;
  
      int m = A.size();
      int n = A[0].size();
  
      for(int i = 0; i < m; i++){
          for(int j = 0; j < n/2; j++){
              swap(A[i][j], A[i][n-j-1]);
          }
      }
  
      for(int i = 0; i < m; i++){
          for(int j = 0; j < n; j++){
              A[i][j] = 1 - A[i][j];
          }
      }
      return A;
  }
  
  // 48. 旋转矩阵
  void rotate(vector<vector<int>>& matrix) {
      if(matrix.size() == 0 || matrix[0].size() == 0) return;
      int row = matrix.size(), col = matrix[0].size();
      // 沿主对角线对折
      for(int i = 0; i < row; i++){
          for(int j = i; j < col; j++){
              swap(matrix[i][j], matrix[j][i]);
          }
      }
      // 水平翻转
      for(int i = 0; i < row; i++){
          for(int j = 0; j < col / 2; j++){
              swap(matrix[i][j], matrix[i][col-1-j]);
          }
      }
      return;
  }
  
  // 733.图像渲染 颜色填充
  vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
      if(image.size() == 0 || image[0].size() == 0) return image;
      int oriColor = image[sr][sc];
      bfs(image, sr, sc, newColor, oriColor);
      return image;
  }
  
  void bfs(vector<vector<int>>& image, int sr, int sc, int newColor, int oriColor){
      if(sr >= image.size() || sc >= image[0].size()  || sc < 0 || sr < 0) return;
      if(image[sr][sc] == oriColor && image[sr][sc] != newColor){
          image[sr][sc] = newColor;
          bfs(image, sr-1, sc, newColor, oriColor);
          bfs(image, sr+1, sc, newColor, oriColor);
          bfs(image, sr, sc-1, newColor, oriColor);
          bfs(image, sr, sc+1, newColor, oriColor);
      }
  }

• BN 层的实现

  # 简化版
  import numpy as np
  
  def batchnorm_forward(x, gamma, beta, eps):
      # calculate mean & var
      batch_mean = np.mean(x, axis=(0, 2, 3), keepdims=True)
      batch_var = np.var(x, axis=(0, 2, 3), keepdims=True)
  
      # normalize
      x_hat = (inp - batch_mean) / np.sqrt(batch_var + eps)
  
      # scale & shift
      out = x_hat * gamma + beta
      return out

  # 复杂版本
  import numpy as np
  
  def batchnorm_forward(x, gamma, beta, bn_param):
      mode = bn_param['mode']
      eps = bn_param.get('eps', 1e-5) 
      momentum = bn_param.get('momentum', 0.9)
      
      N, D = s.shape  # N is batch_size * H * W, D is channels
      running_mean = bn_param.get('running_mean', np.zeros(D, dtype=x.dtype))
      running_var = bn_param.get('running_var', np.zeros(D, dtype=x.dtype))
      
      out, cahce = None, None
      if mode == 'train':    
          batch_mean = np.mean(x, axis=0, keepdims=True)
          batch_var = np.var(x, axis=0, keepdims=True) 
          x_norm = (inp - batch_mean) / np.sqrt(batch_var + eps)
          out = x_norm * gamma + beta
          # store variables in cache
          cache = (x, x_norm, gamma, beta, eps, batch_mean, batch_var)
          # update running_mean & running var
          running_mean = momentum * running_mean + (1 - momentum) * batch_mean
          running_var = momentum * running_var + (1 - momentum) * batch_var
      elif mode == 'test':
          x_norm = (x - running_mean) / np.sqrt(running_var + eps)
          out = x_norm * gamma + beta
          
      bn_param['running_mean'] = running_mean
      bn_param['running_var'] = running_var
      return out, cache

• kmeans算法

• 手写 nms 算法

  import numpy as np
  
  def pu_cpu_nms(dets, thresh):
      # 提取四边形并计算区域面积
      x1 = dets[:, 0]
      y1 = dets[:, 1]
      x2 = dets[:, 2]
      y2 = dets[:, 3]
      area = (x2 - x1 + 1) * (y2 - y1 + 1)
      # 提取 scores 并进行排序
      scores = dets[:, 4]
      order = scores.argsort()[::-1]
      
      keep = []
      while order.size > 0:
          # 计算 iou
          i = order[0]
          keep.append(i)
          xx1 = np.maximum(x1[i], x1[1:])
          yy1 = np.maximun(y1[i], y1[1:])
          xx2 = np.minimum(x2[i], x2[1:])
          yy2 = np.minimum(y2[i], y2[1:])
          
          w = np.maximum(0.0, xx2 - xx1 + 1)
          h = np.maximum(0.0, yy2 - yy1 + 1)
          
          inter = w * h
          ovr = inter / (area[i] + area[order[1:]] - inter)
          
          # 保留小于 thresh 的 bbox
          inds = np.where(ovr <= thresh)[0]
          order = order[inds + 1]
          
      return keep

• 最大的岛屿面积

  int bfs(vector<vector<int>>& grid, int r, int c, int m, int n){
      if(r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == 0) return 0;
  
      grid[r][c] = 0;
      return 1 + bfs(grid, r-1, c, m, n) + bfs(grid, r+1, c, m, n) 
                  + bfs(grid, r, c-1, m, n) + bfs(grid, r, c+1, m, n);
  }
  
  
  int maxAreaOfIsland(vector<vector<int>>& grid) {
      int max_area = 0;
      if(grid.size() == 0 || grid[0].size() == 0) return 0;
      int m = grid.size();
      int n = grid[0].size();
  
      int res = 0;
      for(int i = 0; i < m; i++){
          for(int j = 0; j < n; j++){
              if(grid[i][j] == 1) {
                  int cur_area = bfs(grid, i, j, m, n);
                  max_area = max(max_area, cur_area);
              }
          }
      }
      return max_area;
  }

• 手写卷积