# DGCNN

## 论文

Dynamic Graph CNN for Learning on Point Clouds
Wang, Yue and Sun, Yongbin...


## 核心思想:关于EdgeConv

e i j = h Θ ( x i , x j ) e_{ij} = h_{\Theta}(x_i,x_j)

h Θ : R F × R F → R F ′ h_{\Theta}: {R^F} \times {R^F} \to {R^{F'}}

h Θ h_{\Theta} 是一个非线性的映射，拥有一系列可学习的参数。

h Θ ( x i , x j ) = h ˉ Θ ( x i , x j − x i ) h_{\Theta}(x_i,x_j) = {\bar h}_{\Theta}(x_i, x_j - x_i)

e i j m ′ = R e L U ( θ m ⋅ ( x j − x i ) + ϕ m ⋅ x i ) e_{ijm}' = ReLU(\theta_m \cdot(x_j - x_i) + \phi_m \cdot x_i)

x i m ′ = max ⁡ j : ( i , j ) ∈ ξ e i j m ′ x_{im}' = \mathop {\max }\limits_{j:(i,j) \in \xi }e_{ijm}'

## 部分关键代码

def knn(x,k):
inner = -2 * torch.matmul(x.transpose(2, 1), x)
xx = torch.sum(x**2, dim=1, keepdim=True)
pairwise_distance = -xx - inner - xx.transpose(2, 1)

idx = pairwise_distance.topk(k=k, dim=-1)[1]        #(batch_size, num_points, k)
return idx

def get_graph_feature(x, k=20, idx=None, dim9 = False):
# x: (batch_size, 3, num_points)
batch_size = x.size(0)
num_points = x.size(2)
x = x.view(batch_size, -1, num_points)
if idx is None:
if dim9 == False:
idx = knn(x, k=k)
else:
idx = knn(x[:, 6:], k=k)
device = torch.device('cuda')

idx_base = torch.arange(0, batch_size, device=device).view(-1,1,1)*num_points

idx = idx + idx_base

idx = idx.view(-1)

_,num_dims,_ = x.size()

x = x.transpose(2,1).contiguous()   # (batch_size, num_points, num_dims) --> (batch_size*num_points, num_dims)
feature = x.view(batch_size*num_points, -1)[idx, :]     # KNN
feature = feature.view(batch_size, num_points, k, num_dims)
x = x.view(batch_size, num_points, 1, num_dims).repeat(1,1,k,1)

feature = torch.cat((feature-x, x), dim=3).permute(0, 3, 1, 2).contiguous()

return feature      # (batch_size, 2*num_dims, num_points, k)


class DGCNN_cls(nn.Module):
def __init__(self, args, output_channels = 40):
super(DGCNN_cls, self).__init__()
self.args = args
self.k = args.k

self.bn1 = nn.BatchNorm2d(64)
self.bn2 = nn.BatchNorm2d(64)
self.bn3 = nn.BatchNorm2d(128)
self.bn4 = nn.BatchNorm2d(256)
self.bn5 = nn.BatchNorm1d(args.emb_dims)

self.conv1 = nn.Sequential(nn.Conv2d(6,64, kernel_size = 1, bias = False),
self.bn1,
nn.LeakyReLU(negative_slope=0.2))
self.conv2 = nn.Sequential(nn.Conv2d(64*2, 64, kernel_size=1, bias = False),
self.bn2,
nn.LeakyReLU(negative_slope=0.2))
self.conv3 = nn.Sequential(nn.Conv2d(64*2, 128, kernel_size=1, bias = False),
self.bn3,
nn.LeakyReLU(negative_slope=0.2))
self.conv4 = nn.Sequential(nn.Conv2d(128*2, 256, kernel_size=1, bias = False),
self.bn4,
nn.LeakyReLU(negative_slope=0.2))
self.conv5 = nn.Sequential(nn.Conv1d(512, args.emb_dims, kernel_size=1, bias=False),
self.bn5,
nn.LeakyReLU(negative_slope=0.2))
self.linear1 = nn.Linear(args.emb_dims*2, 512, bias=False)
self.bn6 = nn.BatchNorm1d(512)
self.dp1 = nn.Dropout(p=args.dropout)
self.linear2 = nn.Linear(512, 256)
self.bn7 = nn.BatchNorm1d(256)
self.dp2 = nn.Dropout(p=args.dropout)
self.linear3 = nn.Linear(256, output_channels)

def forward(self, x):
batch_size = x.size(0)
x = get_graph_feature(x, k=self.k)      # (batch_size, 3, num_points) --> (batch_size, 3*2, num_points, k)
x = self.conv1(x)                       # (batch_size, 3*2, num_points, k) --> (batch_size, 64, num_points, k)
x1 = x.max(dim=-1, keepdim=False)[0]    # (batch_size, 64, num_points, k) --> (batch_size, 64, num_points)

x = get_graph_feature(x1, k=self.k)     # (batch_size, 64, num_points) --> (batch_size, 64*2, num_points, k)
x = self.conv2(x)                       # (batch_size, 64*2, num_points, k) --> (batch_size, 64, num_points, k)
x2 = x.max(dim=-1, keepdim=False)[0]    # (batch_size, 64, num_points, k) --> (batch_size, 64, num_points)

x = get_graph_feature(x2, k=self.k)     # (batch_size, 64, num_points) --> (batch_size, 64*2, num_points, k)
x = self.conv3(x)                       # (batch_size, 64*2, num_points, k) --> (batch_size, 128, num_points, k)
x3 = x.max(dim=-1, keepdim=False)[0]    # (batch_size, 128, num_points, k) --> (batch_size, 128, num_points)

x = get_graph_feature(x3, k=self.k)     # (batch_size, 128, num_points) --> (batch_size, 128*2, num_points, k)
x = self.conv4(x)                       # (batch_size, 128*2, num_points, k) --> (batch_size, 256, num_points, k)
x4 = x.max(dim=-1, keepdim=False)       # (batch_size, 256, num_points, k) --> (batch_size, 256, num_points)

x = torch.cat((x1, x2, x3, x4), dim=1)  # (batch_size, 64+64+128+256, num_points)

x = self.conv5(x)                       #(batch_size, 64+64+128+256, num_points) --> (batch_size, emb_dims, num_points)
x1 = F.adaptive_max_pool1d(x, 1).view(batch_size, -1)           # (batch_size, emb_dims, num_points) --> (batch_size, emb_dims)
x2 = F.adaptive_avg_pool1d(x, 1).view(batch_size, -1)           # (batch_size, emb_dims, num_points) --> (batch_size, emb_dims)
x = torch.cat((x1, x2), 1)                                      # (batch_size, emb_dims*2)

x = F.leaky_relu(self.bn6(self.linear1(x)), negative_slope=0.2) # (batch_size, emb_dims*2) --> (batch_size, 512)
x = self.dp1(x)
x = F.leaky_relu(self.bn7(self.linear2(x)), negative_slope=0.2) # (batch_size, 512) --> (batch_size, 256)
x = self.dp2(x)
x = self.linear3(x)                                             #(batch_size, 256) --> (batch_size, output_channels)

return x


## 特性

### 平移不变性

EdgeConv有着部分额平移不变性。因为：

h Θ ( x i , x j ) = h ˉ Θ ( x i , x j − x i ) h_{\Theta}(x_i,x_j) = {\bar h}_{\Theta}(x_i, x_j - x_i)

## 用EdgeConv的理论重新审视其他网络

### PointNet

PointNet的特点是将每一个点进行单独处理，不断抽象到高维空间（这也正是其缺乏局部结构信息的缺陷来源）。

### PointNet++

PointNet++意识到了PointNet中存在的问题，所以它通过FPS采样，然后通过ball query构造局部点集，再通过PointNet抽象出局部特征。

PointNet++ 首先通过欧氏距离来构建图Graph，然后每经过一个layer对图进行一次粗糙化。在每一层，首先通过FPS选取一些点，只有这些被选取的点将保留，其他的点都将被抛弃。通过这种方法，图会在每经过一层网络后变得越来越小。同时，PointNet++使用输入数据的欧式距离来计算点对关系，所以就导致了他们的图在整个训练过程中是固定的，而不是动态调整的（DGCNN一大特点就是动态图）。Edge Function h Θ ( x i , x j ) = h Θ ( x j ) h_{\Theta}(x_i,x_j)=h_{\Theta}(x_j)