How sparse is a point cloud?

ما مدى تناثر سحابة النقاط؟

Voxelize an outdoor LiDAR frame and fewer than 0.01 percent of cells hold a point. An ImageNet input is 100 percent dense, and about 50 percent nonzero after ReLU. Indoor scenes and single objects sit below 1 percent.

حوّل إطار LiDAR خارجياً إلى voxels فتجد أن أقل من 0.01% من الخلايا تحتوي نقطة. أما صورة ImageNet فكثافتها 100%، ونحو 50% غير صفري بعد ReLU. والمشاهد الداخلية والأجسام المفردة أقل من 1%.

This is activation sparsity, but its source is geometry: the zeros are the space between surfaces, so the nonzero pattern should never grow during computation.

هذه activation sparsity، لكن مصدرها الهندسة: الأصفار هي المسافة بين الأسطح، لذا يجب ألا يتمدد نمط القيم غير الصفرية أثناء الحساب.

The dilation problem

مشكلة التمدد (dilation)

A dense 3^d convolution turns one active site into 3^d after one layer and 5^d after two: in general (2L + 1)^d. In 3D that is 1, 27, 125. On the slide grid (4 x 5, active cells at (1,1), (2,2), (2,4), (3,3)), one dense 3 x 3 layer turns 4 of 20 cells into 17 of 20; a second layer fills all 20.

convolution كثيف بحجم 3^d يحوّل موقعاً نشطاً واحداً إلى 3^d بعد طبقة واحدة و5^d بعد طبقتين، وعموماً (2L + 1)^d. في الأبعاد الثلاثة: 1 ثم 27 ثم 125. وعلى شبكة الشريحة (4 x 5 بخلايا نشطة عند (1,1) و(2,2) و(2,4) و(3,3))، تحوّل طبقة 3 x 3 كثيفة واحدة 4 من 20 خلية إلى 17 من 20، وتملأ الطبقة الثانية الخلايا الـ 20 كلها.

Submanifold sparse convolution

الالتفاف المتناثر submanifold

Definition: an output site is computed if and only if the input site at the same coordinate is active (odd kernel, stride 1, same padding). So P_out = P_in, and a deep network stays as sparse as its first layer. It does not compute and mask; it never visits empty positions at all.

التعريف: يُحسب موقع الخرج إذا وفقط إذا كان موقع الدخل في نفس الإحداثي نشطاً (kernel فردي، stride 1، same padding). إذن P_out = P_in، وتبقى الشبكة العميقة متناثرة بقدر طبقتها الأولى. هو لا يحسب ثم يُقنّع، بل لا يزور المواقع الفارغة أصلاً.

The map and the update rule

الخريطة (map) وقاعدة التحديث

A 3 x 3 kernel is nine weight matrices W_(dx,dy), each C_in x C_out, with dx, dy in {-1, 0, 1}. The layer is a list of maps (In, Out, Wgt). The deck's convention: input P sits at output Q shifted by the offset, P = Q + (dx, dy) in (row, column). For every entry:

kernel بحجم 3 x 3 هو تسع مصفوفات أوزان W_(dx,dy)، كل منها C_in x C_out، حيث dx, dy من {-1, 0, 1}. الطبقة هي قائمة maps (In, Out, Wgt). واصطلاح الشرائح: الدخل P يقع عند الخرج Q مزاحاً بالإزاحة، أي P = Q + (dx, dy) بترتيب (صف، عمود). ولكل مدخل في القائمة:

f_out(Q)  =  f_out(Q)  +  f_in(P) x W_(dx,dy)        one (1 x C_in)(C_in x C_out) product

كل مدخل في map هو ضرب متجه في مصفوفة واحد بحجم (1 x C_in)(C_in x C_out)، يُجمع في متجه الخرج.

Slide 95 follows P0 at (1,1). Conventionally P0 lands in nine output windows: nine entries, from (P0, Q0, W_1,1) at the top-left to (P0, Q10, W_-1,-1) at the bottom-right. Sparse: only outputs that are themselves inputs survive, P0's own cell (W_0,0) and (2,2) where P1 sits (W_-1,-1). 9 entries become 2.

الشريحة 95 تتتبّع P0 عند (1,1). في الطريقة التقليدية يقع P0 في تسع نوافذ خرج: تسعة مدخلات، من (P0, Q0, W_1,1) أعلى اليسار إلى (P0, Q10, W_-1,-1) أسفل اليمين. أما المتناثرة فلا يبقى إلا الخرج الذي هو نفسه دخل: خلية P0 نفسها (W_0,0) و(2,2) حيث يقع P1 (W_-1,-1). تسعة مدخلات تصبح اثنين.

Worked: build the map for slide 96

مثال محلول: ابنِ الخريطة للشريحة 96

5 x 5 grid, five points in row-major order: P0 (1,1), P1 (2,2), P2 (2,4), P3 (3,2), P4 (4,3). Outputs Q_i sit at the same positions. For each pair within one step, the offset is (dx, dy) = P - Q.

شبكة 5 x 5 فيها خمس نقاط بترتيب الصفوف: P0 (1,1) وP1 (2,2) وP2 (2,4) وP3 (3,2) وP4 (4,3). المخرجات Q_i في نفس المواقع. لكل زوج على بعد خطوة واحدة، الإزاحة هي (dx, dy) = P - Q.

centre entries (every point onto itself), W_0,0:
  (P0,Q0) (P1,Q1) (P2,Q2) (P3,Q3) (P4,Q4)               5 entries

neighbour pairs (Chebyshev distance 1), both directions:
  P0 (1,1) - P1 (2,2):  (P0,Q1) dx,dy = (1,1)-(2,2) = (-1,-1)
                        (P1,Q0) dx,dy = (2,2)-(1,1) = ( 1, 1)
  P1 (2,2) - P3 (3,2):  (P1,Q3) = (-1, 0)    (P3,Q1) = ( 1, 0)
  P3 (3,2) - P4 (4,3):  (P3,Q4) = (-1,-1)    (P4,Q3) = ( 1, 1)
  P2 (2,4): no neighbour, (2,2) is two columns away       6 entries

group by weight (one matmul each, weight-stationary)
  W_-1,-1 : (P0,Q1) (P3,Q4)                     2 rows
  W_-1,0  : (P1,Q3)                             1 row
  W_0,0   : all five centre entries             5 rows
  W_1,0   : (P3,Q1)                             1 row
  W_1,1   : (P1,Q0) (P4,Q3)                     2 rows
  other 4 offsets: empty, no launch
  total 11 entries, 5 matmuls

Weight-stationary execution

التنفيذ بأسلوب weight-stationary

The GPU version on slide 96: for one offset, gather the input rows named by its entries into a buffer (for W_-1,-1: P0 and P3, a 2 x C_in buffer), run one matmul with the C_in x C_out weight to get a 2 x C_out partial sum, then scatter-add the rows into Q1 and Q4: f₁ += f₀ x W_-1,-1, f₄ += f₃ x W_-1,-1. Repeat per offset: five matmuls with 2, 1, 5, 1, 2 rows.

نسخة GPU في الشريحة 96: لإزاحة واحدة، اجمع (gather) صفوف الدخل المذكورة في مدخلاتها في buffer (لـ W_-1,-1: P0 وP3، أي buffer بحجم 2 x C_in)، ثم نفّذ matmul واحداً مع الوزن C_in x C_out لتحصل على partial sum بحجم 2 x C_out، ثم وزّع وأضف (scatter-add) الصفوف إلى Q1 وQ4: f₁ += f₀ x W_-1,-1 وf₄ += f₃ x W_-1,-1. كرّر لكل إزاحة: خمسة matmuls بعدد صفوف 2, 1, 5, 1, 2.

كل مدخل يكلّف 64 x 64 = 4,096 MACs. التقليدي مع تخطّي الأصفار يعطي 30 مدخلاً لأن النقطتين على الحافة لهما ست نوافذ فقط داخل الشبكة. والمتناثر يعطي 10: أربعة مراكز وثلاثة أزواج متجاورة في الاتجاهين.

Zero-skipping alone already cuts most of the work, but it still writes 17 outputs, so the next layer starts from 17 points. Only the submanifold row stays proportional to the number of points layer after layer.

تخطّي الأصفار وحده يزيل معظم العمل، لكنه ما زال يكتب 17 خرجاً، فتبدأ الطبقة التالية من 17 نقطة. الصف submanifold وحده يبقى متناسباً مع عدد النقاط طبقة بعد طبقة.