# Wildfire Detection Via Transfer Learning: A Survey

Ziliang Hong, Emadeldeen Hamdan, Yifei Zhao, Tianxiao Ye, Hongyi Pan, A. Enis
Cetin  Department of Electrical and Computer Engineering
University of Illinois Chicago
Chicago, IL 60607, USA

###### Abstract

This paper surveys different publically available neural network models used
for detecting wildfires using regular visible-range cameras which are placed
on hilltops or forest lookout towers. The neural network models are pre-
trained on ImageNet-1K and fine-tuned on a custom wildfire dataset. The
performance of these models is evaluated on a diverse set of wildfire images,
and the survey provides useful information for those interested in using
transfer learning for wildfire detection. Swin Transformer-tiny has the
highest AUC value but ConvNext-tiny detects all the wildfire events and has
the lowest false alarm rate in our dataset.

###### Index Terms:

Wildfire detection, transfer learning, convolutional neural network, vision
transformer

##  I Introduction

Early detection of wildfires is crucial in minimizing the harm they cause to
people and the economy. Researchers have developed different techniques,
including real-time algorithms that use video-based surveillance systems and
deep neural networks that can recognize fire and smoke images[1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11, 12, 13, 3, 14]. Some of these methods enable a single
camera to detect wildfire smoke in real-time from a distance[15].

Neural network-based methods for wildfire detection eliminate the need for
manual feature selection, but they require a lot of data and computing power.
To mitigate the issue of insufficient data, synthetic data is used for
training, and transfer learning techniques like Fast R-CNN[16] and Yolo series
algorithms[17] are utilized to enhance the model’s performance and reduce the
amount of data required[18, 19]. Transfer learning has been used in this
survey, inspired by previous papers[20, 15], leading to the development of
effective neural network models for forest fire detection since 2015.

In this paper, we explore the feasibility of several classical models in the
field of wildfire detection and compare their performance. These models are
Residual Neural Network V2(ResNetV2), Data-efficient, image Transformers
(DeiT), EffecientNetV2, Big Transfer (BiT), MobileNetV3, Swin Transformer, and
ConvNeXt[21, 22, 23, 24, 25, 26, 27, 28]. Inspired by a previous paper [15], a
single image is split into sub-images for object detection. We evaluate
critical indicators, including accuracy, false alarm rate, true detection
rate, detection latency, and implementation latency for wildfire detection
[15, 20, 29]. Experiments compare model performance, analyze superior models,
and provide a summary of comparisons.

##  II Overview of Artificial Neural Networks

In this section, we present a comprehensive review of the selected models,
detailing their respective structures and innovations.

###  II-A Residual Neural Network (ResNet)

ResNet is a revolutionary neural network [30]. It achieved unprecedented depth
with more than 1000 layers, owing to the introduction of residual blocks [30].
Before the ResNet, it is always challenging to design very deep Convolutional
Neural Networks (CNNs) because neural networks that are too deep usually face
the problems of gradient vanishing and exploding. Besides, an increasing
number of layers could also cause degeneration. Through the skip connection
structure of layers which is called residual block and the usage of the Batch
Normalization (BN) layer, ResNet shows its ability to solve this predicament.
The core equation of a residual block in ResNet can be expressed as follows:

$\displaystyle y=\mathcal{F}(x,\\{W_{i}\\})+W_{s}x.$ (1)

In ResNetv2 [21], the structure of the residual module was improved. The BN
layer and activation function are placed in front of the weight layer as
preactivation. This is the main difference between ResNetv2 and ResNetV1. Such
a structure can not only afford efficient backpropagation but also allow the
BN layer to play a regularization role, which makes ResNetV2 significant
progress.

###  II-B MobileNet

MobileNet [31] is built primarily from depthwise separable convolutions.
Depthwise separable convolutions include a standard convolution into a
depthwise convolution and a 1×1 convolution called a pointwise convolution. It
can reduce computation and model size effectively.

Meanwhile, the network structure has been optimized and a parameter called
width multiplier has been introduced to further thin the network uniformly at
each layer. MobileNet is small and has low latency. It is implementable on
computationally limited platforms and shows strong performance. The authors
introduce MobileNetV2 using the inverted residual with the linear bottleneck
to further improve the network [32]. In the next generation MobileNetV3, a
combination of these modules (depthwise separable convolutions and inverted
residual with linear bottleneck) are used in the first two generations.
Platform-aware Neural Architecture Search (NAS) is also employed to search for
the global network structures and then use the NetAdapt algorithm to search
per layer for the number of filters. Computationally expensive layers has been
redesigned and a nonlinearity called swish to replace ReLU is used instead. As
the next generation of MobileNet, MobileNetV3 can achieve higher accuracy and
lower latency than MobileNetV2 [26].

###  II-C Big Transfer (BiT)

The innovation of BiT lies in its large-scale pretraining strategy that
involves training on multiple public datasets. By leveraging this strategy,
BiT achieves high performance on a wide range of computer vision tasks and
surpasses previous state-of-the-art results. Also, Group Normalization and
weight standardization is used instead of Batch Normalization. Because it
incurs inter-device synchronization costs when using distributed training. And
it is detrimental to transfer due to the requirement to update running
statistics.

During the transfer to downstream tasks, a fine-tuning protocol called BiT-
HyperRule is proposed. It is heuristic to set the following hyperparameters
per-task: training schedule length, resolution, and whether to use MixUp
regularization. The models are evaluated on standard benchmarks and have a
good performance. The recipe is simple and effective when we transfer pre-
trained models to diverse tasks [25].

###  II-D EffecientNet

The compound scaling method is proposed to scale network width, depth, and
resolution with a set of fixed scaling coefficients. NAS is used to design a
new baseline network and scale it up to obtain a family of models called
EfficientNets, which is smaller and faster than existing convolutional neural
networks [33].

EfficientNetV2 is introduced in June 2021. A combination of training-aware NAS
and scaling are used to improve both training speed and parameter efficiency.
They design a search space enriched with additional ops such as Fused-MBConv
and propose an improved method of progressive learning, which can adjust
regularization along with image size. EfficientNetV2 have up to 11x faster
training speed and up to 6.8x better parameter efficiency on ImageNet, CIFAR,
Cars, and Flowers dataset, than prior art such as ResNet-101 and ViT-L/16
(21k) [24].

###  II-E Data-efficient image Transformers (DeiT)

Recurrent Neural Networks (RNNs) require information from previous or next-
time steps for calculations, making parallel computation difficult and
limiting them to serial processing. By adopting the Self-Attention mechanism
[34], The Transformer model for sequence processing avoids horizontal
propagation, relying instead on vertically stacked self-attention layers that
allow for parallel computation and acceleration using GPUs.

Vision Transformer (Vit) is a transformer-based model in computer vision which
require massive training data [35]. In order to overcome the limitations of
Vit, the Data-efficient image transformers (DeiT) model was developed. A
systematic optimization and regularization approach was employed on DeiT,
which includes data augmentation during training. The authors employed the so-
called soft and hard-label knowledge distillation to facilitate the teacher
model in guiding DeiT during training [22, 23].

###  II-F Swin Transformer

Swin Transformer [27] uses a hierarchical construction method similar to CNNs.
Such a backbone helps to build detection and segmentation tasks on this basis.
When using the Windows Multi-head Self-Attention (W-MSA) module, the self-
attention calculation will only be performed within each window, so there is
no information transfer from window to window. To solve this problem, the
authors introduced the Shifted Windows Multi-Head Self-Attention (SW-MSA)
module. Relative Position Bias is also employed to improve the performance of
the model.

###  II-G ConvNeXt

ConvNeXt does not introduce novel architectural or methodological innovations.
Instead, it leverages existing techniques and optimized CNNs for enhanced
performance. The authors first used the strategy of training ViT to train the
original ResNetV2-50 model and observed a significant improvement in
performance compared to the baseline. This benchmark performance was then
utilized for subsequent experiments. Through a series of experiments, ConvNeXt
has faster inference speed and higher accuracy compared with Swin Transformer
with the same computational complexity [28].

##  III Methodology

###  III-A Methods of Implementation

Object detection tasks involve identifying the location and classification of
objects in images. Usually, the bounding box-based method needs to manually
label massive bounding boxes like the Yolo series algorithm[17]. In this
experiment, the approach taken is to divide each image into 45 blocks as Fig.
1. Using this approach, it is possible to detect and locate fires accurately
and we do not need to label the bounding box of the wildfire. Assuming that
the dimensions of the active image area are $M_{i}$ and $N_{i}$ and that the
dimensions of each block are $M_{b}$ and $N_{b}$, an equation can be used to
express the row number R and column number C for each block:

$R=\lfloor\frac{M_{i}}{M_{b}}\rfloor,C=\lfloor\frac{N_{i}}{N_{b}}\rfloor$ (2)

where $\lfloor\cdot\rfloor$ stands for the floor function. The main task is to
construct a binary classifier that can predict the whether there is a wildfire
or not. Forest fire detection devices are often used in remote wilderness
areas where weight and computational resources are limited. Therefore, small
models are chosen to fit these devices.

Figure 1: The top is a sample to be detected, and the below is the detected
result. (detected by Swin Transformer-tiny)

###  III-B Dataset

In this work, we build a wildfire dataset by enriching the dataset in [15] and
[20] to about 35k images. The training subset approximately contains 14k
images of normal forests and 9k wildfire images. The test subset contains
about 8k images of normal forests and 4k wildfire images. All the data images
are from the HPWREN wildfire dataset [36], the FIRESENSE database [37], google
images, and YouTube videos. Furthermore, to evaluate the performance in real-
world applications, we evaluate the models on the HPWREN videos to estimate
the detection latency. Fig. 2 and Fig. 3 show some samples from the dataset.

(a)  (b)  (c)  (d)

Figure 2: Examples of the dataset images. Wildfire exists in (a) and (b).
Wildfire does not exist in (c) and (d).

Figure 3: HPWREN samples for test model detection. We use data from 9 HPWREN
cameras, each of which recorded the process of occurrence of fire.

##  IV Experiment

###  IV-A Training Models

Transfer learning techniques in deep learning can address the time-consuming
task of gathering extensive training data and overfitting problems In this
study, pre-trained models from the ImageNet-1K open-source database [38] were
used for forest fire detection using theTensorFlow deep learning library with
an NVIDIA RTX3070 GPU. The training process consisted of 15 epochs with a
fixed feature extractor method used in the first 10 epochs and a transfer
learning strategy applied in the final 5 epochs. Fine-tuning all the layers in
the whole model further improved the models’ performance while reducing the
demand for large amounts of data. After fine-tuning, the probability of
wildfire was calculated by feeding the results to a softmax layer. The study
assumed that images with fire are negative samples and images without fire are
positive samples. To ensure practical application, the wildfire detection
model should not be overly sensitive while accurately detecting forest fires
to the greatest extent possible using the true detection rate and false alarm
rate in the confusion matrix.

Figure 4: ROC of models. Models are arranged by AUC size from top to bottom.  Model | Parameters (M) | FLOPs (G) | AUC | ACC | True Detection | False Alarm
---|---|---|---|---|---|---
Swin Transformer-tiny | 27.6 | 8.99 | 0.99917 |  97.95$\%$ |  94.63$\%$ |  0.36$\%$
DeiT-tiny | 5.5 | 2.54 | 0.99876 | 98.13$\%$ |  95.12$\%$ |  0.35$\%$
ConvNeXt-tiny | 27.8 | 8.99 | 0.99743 |  96.69$\%$ |  90.52$\%$ |  0.18$\%$
MobileNetV3-small | 20.3 | 0.12 | 0.99114 |  95.17$\%$ |  94.11$\%$ |  4.30$\%$
BiT-small | 23.5 | 8.38 | 0.98973 |  96.86$\%$ | 99.78$\%$ |  4.63$\%$
ResNetV2-50 | 23.6 | 6.99 | 0.98837 |  95.00$\%$ |  98.92$\%$ |  6.99$\%$
EfficientNetV2 | 1.5 | 5.74 | 0.98571 |  93.47$\%$ |  96.48$\%$ | 8.06$\%$
Mobilenet-edgetpu-v2 | 2.5 | 1.03 | 0.98056 |  94.70$\%$ |  91.73$\%$ |  3.79$\%$
Table I: Parameters, FLOPs, AUC of models. Accuracy, True Detection Rate, and False Alarm Rate of models on the test dataset. Models are arranged in descending order of AUC.  Video No. | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Average
---|---|---|---|---|---|---|---|---|---|---
Swin Transformer-tiny | 7 | 4 | 0 | 27 | 6 | 1 | 2 | 4 | 2 | 5.8
DeiT-tiny | 5 | 4 | 1 | 29 | 7 | 2 | 6 | 4 | 2 | 6.7
ConvNeXt-tiny | 5 | 4 | 0 | 29 | 7 | 1 | 6 | 6 | 1 | 6.6
MobileNetV3-small | 6 | 11 | 0 | 35 | 7 | 4 | 27 | 13 | 1 | 11.6
BiT-small | 2 | 0 | 0 | 26 | 4 | 1 | 1 | 3 | 1 | 4.2
ResNetV2-50 | 3 | 2 | 0 | 29 | 5 | 1 | 8 | 7 | 2 | 6.3
EfficientNetV2 | 4 | 2 | 0 | 26 | 6 | 4 | 6 | 2 | 1 | 5.7
Mobilenet-edgetpu-v2 | 6 | 11 | 1 | 35 | 7 | 4 | 6 | 11 | 1 | 9.1
Table II: Considering the rigor of fire prediction, we set the threshold to
95$\%$. Each number represents the frame number at which the models first
detected the presence of fire.We Calculate detection latency as the time
between the frame when the fire is first detected and the frame when the fire
starts. In the last column, we calculate the average detection latency.

###  IV-B Testing Models

####  IV-B1 Evaluation Indicators

The evaluation of deep neural networks (DNNs) involves five key indicators:
accuracy, true detection rate, false alarm rate, floating point operations
(FLOPs), number of parameters, detection latency, and Receiver Operating
Characteristic (ROC). ROC curve is a graph that shows how sensitive a model is
to various threshold ranges between 0$\%$ and 100$\%$ [39]. By calculating the
False Positive Rate (FPR) and True Positive Rate (TPR) under different
thresholds and setting them as X-axis and Y-axis respectively, ROC curve and
Area Under the Curve (AUC) can be used to compare the performance of different
models and usually a larger AUC indicates a better performance. The
mathematical expressions for ROC and AUC can be represented as:

$\text{ROC}=\frac{\text{TPR}}{\text{TPR}+\text{FPR}}$ (3)

$\text{AUC}=\int_{0}^{1}\text{ROC}(x)\,\mathrm{d}x$ (4)

Accuracy measures the percentage of accurate predictions generated by the
neural network, indicating the models’ fitness for purpose. True detection
rate and false alarm rate are crucial indicators in wildfire detection
systems, with true detection rate representing the proportion of correct
negative predictions made by the model and false alarm rate indicating the
percentage of false alarms, with a lower false alarm rate indicating greater
reliability.

Parameters and FLOPs are essential factors affecting neural networks, with the
former indicating the model’s complexity and the latter measuring the number
of calculations an algorithm can perform in a second. FLOPs are also used to
estimate the computational requirements of training or executing a neural
network on a hardware device.

Finally, detection latency refers to the interval between the start of an
actual fire and the system’s detection of it. In experiments, this metric is
evaluated in frames rather than seconds. These indicators can assist in
evaluating the potential applicability and performance of DNNs, which can
inform the development of more reliable and efficient models.

####  IV-B2 Basic Test

Fig. 4 shows the ROC curve of each model. Because the curves are dense, Fig. 4
displays the details of the top left part. Table I shows the FLOPs and
parameters of each model, the models are arranged in the order of AUC size,
from largest to smallest. Table I records the performance of each model on the
test dataset with the threshold of 95$\%$. As Table I shows, DeiT-tiny owns
the highest accuracy which is 98.13$\%$ followed by 97.95$\%$ from Swin
Transformer-tiny and they are both transformer-based models. The remaining
traditional CNNs models perform slightly worse, with BiT-small and ConvNeXt-
tiny performing better than 96$\%$, the rest of the models’ performance is
relatively mediocre.

For image recognition with fire, traditional CNNs perform very well, with
ResNetV2-50 reaching 98$\%$ accuracy and BiT-small even reaching 99$\%$.
However, a high true detection rate comes at the cost of a high false alarm
rate. Both models have a high false alarm rate, ResNetV2-50 was found to have
a false alarm rate of 6.99$\%$. On the contrary, the transformer-based models
have a very low false alarm rate, although the accuracy is slightly lower than
that of the CNNs models. ConvNeXt-tiny, a member of the traditional CNNs, has
a slightly lower accuracy than other CNN models but has a comparable false
alarm rate with the transformer-based models.

####  IV-B3 Detection Latency

Detection latency is a way to describe the time from the onset of the fire
until the model raises an alarm and it is measured in frames. Nine datasets
are selected to calculate the detection latency, which does not overlap with
the data in the test dataset. The result is shown in Table II.

In Table II, BiT-small demonstrates the best performance, exhibiting a
remarkable ability to recognize small features. However, this also leads to a
higher susceptibility to similar features, which is related to BiT-small’s
higher false alarm rate in Table I. The performance of ConvNeXt-tiny and DeiT-
tiny in the detection latency test is moderate, despite their good inference
speed and accuracy. Moreover, the difference in detection latency between them
is insignificant. On the other hand, Swin Transformer-tiny is slower in
detection latency.

####  IV-B4 Implement Latency

Model | Sub-image | Whole Image
---|---|---
Swin Transformer-tiny | 0.02227 | 1.0023
DeiT-tiny | 0.02272 | 1.0223
ConvNeXt-tiny | 0.06151 | 2.7680
MobileNetV3-small | 0.00591 | 0.2660
BiT-small | 0.01636 | 0.7363
ResNetV2-50 | 0.00683 | 0.3074
EfficientNetV2 | 0.01441 | 0.6483
Mobilenet-edgetpu-v2 | 0.00892 | 0.4013
Table III: The time it takes for the model to process the image to make a
prediction. Measured in seconds.

In addition to the model’s ability to detect fires at the earliest stages, we
are also interested in image processing speed. Implement latency is used to
measure the time that a model needed to process a single image. Since we split
our single image into 45 sub-images, we both calculate the time of processing
a single image and a sub-image. At the same time, Table III indicates the
speed of models and we can note that MobileNetV3-small has the shortest
implement latency and ResNetV2-50 has the second shortest implement latency.
While ConvNeXt-tiny has a smaller false alarm rate compared to Swin-tiny and
DeiT-tiny, it is not as efficient in processing images as these transformer-
based models.

##  V Conclusion

In this paper, we chose 8 pre-trained models that are widely used in image
classification to validate the effectiveness and performance of artificial
deep neural networks for wildfire detection using regular visible-range
cameras. Transfer learning is used to train these models and the models are
evaluated based on different indicators. Based on the experiments summarized
above, the strengths and limitations of these models are determined. According
to the criteria of traditional image classifiers, transformer-based models
Swin Transformer and DeiT achieved the highest AUC and accuracy. Traditional
CNNs models have slightly lower AUC and accuracy. On the other hand,
traditional CNN models except ConvNeXt are more efficient in implementation
and superior in detecting tiny smoke features. Swin Transformer and DeiT
consume more time to implement relatively, but it is still acceptable in
practice because the processing time of an entire image frame size is less
than 1 second except for Swin Transformer and DeiT networks. Unfortunately,
Swin Transformers and Deit are less sensitive to tiny smoke features.
ConvNext-tiny has the lowest false alarm rate. A low false alarm rate is very
important for the acceptance of the use of machine learning in wildfire
detection problems.

Future research will focus on the use of other types of data, such as thermal
and multispectral imagery. Additionally, the development of hybrid models that
combine deep learning algorithms with traditional machine learning techniques
and domain knowledge can also be a promising direction for improving the
accuracy of wildfire detection systems.

## References

  * [1] Philippe Guillemant and Je’ ro me Vicente.  Real-time identification of smoke images by clustering motions on a fractal curve with a temporal embedding method.  Optical Engineering, 40(4):554–563, 2001.
  * [2] B Ugur Toreyin, Yigithan Dedeoglu, and A Enis Cetin.  Wavelet based real-time smoke detection in video.  In 2005 13th European signal processing conference, pages 1–4. IEEE, 2005.
  * [3] B Ugur Toreyin, Yigithan Dedeoglu, Ugur Gudukbay, and A Enis Cetin.  Computer vision based method for real-time fire and flame detection.  Pattern recognition letters, 27(1):49–58, 2006.
  * [4] Feiniu Yuan.  A fast accumulative motion orientation model based on integral image for video smoke detection.  Pattern Recognition Letters, 29(7):925–932, 2008.
  * [5] B Ugur Toreyin and A Enis Cetin.  Wildfire detection using lms based active learning.  In 2009 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 1461–1464. IEEE, 2009.
  * [6] Osman Günay, Kasım Taşdemir, B Uğur Töreyin, and A Enis Çetin.  Fire detection in video using lms based active learning.  Fire technology, 46:551–577, 2010.
  * [7] Y Hakan Habiboglu, Osman Gunay, and A Enis Cetin.  Real-time wildfire detection using correlation descriptors.  In 2011 19th European Signal Processing Conference, pages 894–898. IEEE, 2011.
  * [8] Yusuf Hakan Habiboglu, Osman Gunay, and A Enis Cetin.  Covariance matrix-based fire and flame detection method in video.  Machine Vision and Applications, 23:1103–1113, 2012.
  * [9] Osman Gunay, Behçet Ugur Toreyin, Kivanc Kose, and A Enis Cetin.  Entropy-functional-based online adaptive decision fusion framework with application to wildfire detection in video.  IEEE Transactions on Image Processing, 21(5):2853–2865, 2012.
  * [10] A Enis Çetin, Kosmas Dimitropoulos, Benedict Gouverneur, Nikos Grammalidis, Osman Günay, Y Hakan Habiboǧlu, B Uǧur Töreyin, and Steven Verstockt.  Video fire detection–review.  Digital Signal Processing, 23(6):1827–1843, 2013.
  * [11] Osman Günay and A Enis Çetin.  Real-time dynamic texture recognition using random sampling and dimension reduction.  In 2015 IEEE International Conference on Image Processing (ICIP), pages 3087–3091. IEEE, 2015.
  * [12] Suleyman Aslan, Ugur Gudukbay, B Ugur Toreyin, and A Enis Cetin.  Early wildfire smoke detection based on motion-based geometric image transformation and deep convolutional generative adversarial networks.  In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8315–8319. IEEE, 2019.
  * [13] Parul Jindal, Himanshu Gupta, Nikhil Pachauri, Varun Sharma, and Om Prakash Verma.  Real-time wildfire detection via image-based deep learning algorithm.  In Soft Computing: Theories and Applications: Proceedings of SoCTA 2020, Volume 2, pages 539–550. Springer, 2021.
  * [14] A Enis Cetin, Bart Merci, Osman Gunay, Behcet Ugur Toreyin, and Steven Verstockt.  Methods and techniques for fire detection: signal, image and video processing perspectives.  Academic Press, 2016.
  * [15] Hongyi Pan, Diaa Badawi, Xi Zhang, and Ahmet Enis Cetin.  Additive neural network for forest fire detection.  Signal, Image and Video Processing, 14:675–682, 2020.
  * [16] Ross Girshick.  Fast r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 1440–1448, 2015.
  * [17] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 779–788, 2016.
  * [18] Qi-xing Zhang, Gao-hua Lin, Yong-ming Zhang, Gao Xu, and Jin-jun Wang.  Wildland forest fire smoke detection based on faster r-cnn using synthetic smoke images.  Procedia engineering, 211:441–446, 2018.
  * [19] Xuehui Wu, Xiaobo Lu, and Henry Leung.  An adaptive threshold deep learning method for fire and smoke detection.  In 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 1954–1959. IEEE, 2017.
  * [20] Hongyi Pan, Diaa Badawi, and Ahmet Enis Cetin.  Computationally efficient wildfire detection method using a deep convolutional network pruned via fourier analysis.  Sensors, 20(10):2891, 2020.
  * [21] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  In Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11–14, 2016, Proceedings, Part IV 14, pages 630–645. Springer, 2016.
  * [22] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  arXiv preprint arXiv:1503.02531, 2015.
  * [23] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herve Jegou.  Training data-efficient image transformers & distillation through attention.  In International conference on machine learning, pages 10347–10357. PMLR, 2021.
  * [24] Mingxing Tan and Quoc Le.  Efficientnetv2: Smaller models and faster training.  In International conference on machine learning, pages 10096–10106. PMLR, 2021.
  * [25] Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby.  Big transfer (bit): General visual representation learning.  In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part V 16, pages 491–507. Springer, 2020.
  * [26] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al.  Searching for mobilenetv3.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 1314–1324, 2019.
  * [27] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 10012–10022, 2021.
  * [28] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie.  A convnet for the 2020s.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11976–11986, 2022.
  * [29] Hongyi Pan, Diaa Badawi, Chang Chen, Adam Watts, Erdem Koyuncu, and Ahmet Enis Cetin.  Deep neural network with walsh-hadamard transform layer for ember detection during a wildfire.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 257–266, 2022.
  * [30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [31] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  arXiv preprint arXiv:1704.04861, 2017.
  * [32] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen.  Mobilenetv2: Inverted residuals and linear bottlenecks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4510–4520, 2018.
  * [33] Mingxing Tan and Quoc Le.  Efficientnet: Rethinking model scaling for convolutional neural networks.  In International conference on machine learning, pages 6105–6114. PMLR, 2019.
  * [34] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [35] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [36] America University of California San Diego, California.  The high performance wireless research and education network. 2019.  http://hpwren.ucsd.edu/index.html.  Accessed December 25, 2022.
  * [37] Nikos Grammalidis, Kosmas Dimitropoulos, and Enis Cetin.  Firesense database of videos for flame and smoke detection.  IEEE Trans Circuits Syst Video Technol, 25:339–351, 2017.
  * [38] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [39] Kevin Woods and Kevin W Bowyer.  Generating roc curves for artificial neural networks.  IEEE Transactions on medical imaging, 16(3):329–337, 1997.


11institutetext:  11email<EMAIL_ADDRESS>GE Healthcare, Buc
78530, France
11email<EMAIL_ADDRESS>22institutetext: MAP5, Universite de Paris, Paris 75006, France 22email:
<EMAIL_ADDRESS>
# Partial Matching in the Space of Varifolds

11 Pierre-Louis Antonsanti  1122 Joan Glaunès  22 Thomas Benseghir  11 Vincent
Jugnon  11 Irène Kaltenmark  22

###### Abstract

In computer vision and medical imaging, the problem of matching structures
finds numerous applications from automatic annotation to data reconstruction.
The data however, while corresponding to the same anatomy, are often very
different in topology or shape and might only partially match each other. We
introduce a new asymmetric data dissimilarity term for various geometric
shapes like sets of curves or surfaces. This term is based on the Varifold
shape representation and assesses the embedding of a shape into another one
without relying on correspondences between points. It is designed as data
attachment for the Large Deformation Diffeomorphic Metric Mapping (LDDMM)
framework, allowing to compute meaningful deformation of one shape onto a
subset of the other. Registrations are illustrated on sets of synthetic 3D
curves, real vascular trees and livers’ surfaces from two different
modalities: Computed Tomography (CT) and Cone Beam Computed Tomography (CBCT).
All experiments show that this data dissimilarity term leads to coherent
partial matching despite the topological differences.

##  1 Introduction

Finding shape correspondences is a standard problem in computer vision that
has numerous applications such as pattern recognition ([6], [5], [17]),
annotation ([4], [12]) and reconstruction ([16]). In particular, in the field
of medical imaging, matching an atlas and a patient’s anatomy ([12]), or
comparing exams of the same patient acquired with different imaging techniques
([27], [2]), provide critical information to physicians for both planning and
decision making.

In medical imaging, this problem has been tackled by numerous authors ([26])
by registering directly the images, most of the time assuming that both images
contains the entire object of interest. But in practice, it often happens that
only part of an object is visible in one of the two modalities: in CBCT for
instance, the imaged organs can be larger than the field of view, when the
whole organ can be acquired in CT. In order to make the best of the two
modalities, one needs to find a partial matching between them. This work is
focused on sparse segmented structures registration where only part of these
structures can be matched.

####  1.0.1 Previous works.

The problem of matching shapes has been widely addressed in the literature in
the past decades ([18]). In the specific case of partial matching, one can
find two main approaches to such problem: either by finding correspondences,
sparse or dense, between structures from descriptors that are invariant to
different transformations ([1], [24], [15]), or by looking for a deformation
aligning the shapes with respect to a given metric ([1], [4], [12], [16]).

The early works on partial shape correspondence as reviewed in [18] rely on
correspondences between points computed from geometric descriptors extracted
from an isotropic local region around the selected points. The method is
refined in [17] by selecting pairs of points to better fit the local geometry
using bilateral map. The features extracted can also be invariant to different
transformation, as in [25] where the descriptors extraced are scale invariant.
Such sparse correspondences are naturally adapted to partial matching, yet
they cannot take the whole shapes into account in the matching process.

Using a different approach, functional maps were introduced in [22] allowing
dense correspondences between shapes by transferring the problem to linear
functions between spaces of functions defined over the shapes. In [24] the
non-rigid partial shape correspondence is based on the Laplace-Beltrami
eigenfunctions used as prior in the spectral representation of the shapes.
Recently in [15], such functional map models were adapted in a deep
unsupervised framework by finding correspondences minimizing the distortion
between shapes. Such methods are yet limited to surface correspondences.

The second kind of approaches relies on the deformations that can be generated
to align the shapes with each other. It usually involves minimizing a function
called data attachment that quantifies the alignment error between the shapes.
A deformation cost is sometimes added to regularize these deformations. The
sparse correspondences being naturally suited to partial matching, they are
notably used in Iterative Closest Point (ICP) methods and their derivatives to
guide a registration of one shape onto the other. In [1] a regularized version
of the ICP selects the sets of four co-planar points in the points cloud. In
[4] the ICP is adapted to the specific case of vascular trees and compute
curves’ correspondences through an Iterative Closest Curve method. Working on
trees of 3D curves as well, [12] hierarchically selects the overall curves
correspondences minimizing the tree space geodesic distance between the trees.
This latter method although specific to tree-structures, allows topological
changes in the deformation.

On the other hand some authors compute the deformation guided by a dense data
attachment term. In [6] isometry-invariant minimum distortion deformations are
applied to 2D Riemannian manifolds thanks to a multiscale framework using
partial matching derived from Gromov’s theory. This work is extended in [5] by
finding the optimal trade-off between partial shape matching and similarity
between these shapes embedded in the same metric space. Recently in [16] a
partial correspondence is performed through a non-rigid alignment of one shape
and its partial scan seen as points clouds embedded in the same representation
space. The non-rigid alignment is done with a Siamese architecture network.
This approach seems promising and is part of a completion framework, however
it requires a huge amount of data to train the network.

Interestingly, the regularization cost can be seen as a distance between
shapes itself (as in [12]) by quantifying the deformation amount necessary to
register one shape onto the other. This provides a complementary tool to the
metrics used to quantify the shapes dissimilarities.

A well established and versatile framework to compute meaningful deformations
is the Large Deformation Diffeomorphic Metric Mapping. It allows to see the
difference between shapes through the optimal deformations to register a
source shape $S$ onto a target shape $T$. However, the data attachment metrics
proposed so far aim to compare the source and target shapes in their entirety
([9]), or look for explicit correspondences between subparts of these shapes
([13]). In [20] the growth model presented introduces a first notion of
partial matching incorporated to the LDDMM framework, yet no explicit partial
dissimilarity term was proposed.

We propose a new asymmetric dissimilarity term adapted as data attachment in
the LDDMM framework derived from the Varifold shape representation [10] to
quantify the partial shape matching. This term can be used in both continuous
and discrete settings, and applied to many discrete shape representations
without requiring any point correspondences. When combined with LDDMM, this
approach allows to build meaningful deformations while being adapted to the
partial matching between shapes.

##  2 Partial Matching

We are interested in the problem of finding an optimal deformation to register
a source shape $S$ onto an unknown subset of a target shape $T$, where $S,T$
are assumed to be finite unions of $m$-dimensional submanifolds of
$E=\mathbb{R}^{d}$, with either $m=1$ (curves) or $m=d-1$ (hypersurfaces).

###  2.1 The varifold framework for shape matching

In this section we will quickly review the oriented varifold framework
introduced in [19], of which the varifold framework ([10]) is a particular
case.

Let $E=\mathbb{R}^{d}$, with $d\geq 2$ the ambient space. Shapes $S$ and $T$
are assumed to be compact $m$-rectifiable subsets of $\mathbb{R}^{d}$. In
particular at almost every point $x\in S$ (resp. $y\in T$) is defined a unit
tangent - for curves - or normal - for hypersurfaces - vector
$\tau_{x}S\in\mathbb{S}^{d-1}$ (resp. $\tau_{y}T$).

Let $W$ be a Reproducing Kernel Hilbert Space (RKHS) of functions defined over
$\mathbb{R}^{d}\times\mathbb{S}^{d-1}$, continuously embedded in
$C_{0}(\mathbb{R}^{d}\times\mathbb{S}^{d-1})$. Its dual space $W^{\prime}$ is
a space of varifolds. The following proposition gives a practical way to
define such a space:

######  Proposition 1 ([10], Lemma 4.1)

Assume that we are given a positive-definite real kernel $k_{e}$ on the space
$\mathbb{R}^{d}$ such that $k_{e}$ is continuous, bounded and for all
$x\in\mathbb{R}^{d}$, the function $k_{e}(x,.)$ vanishes at infinity. Assume
that a second positive-definite real kernel $k_{t}$ is defined on the manifold
$\mathbb{S}^{d-1}$ and is also continuous. Then the RKHS W associated to the
positive-definite kernel $k_{e}\otimes k_{t}$ is continuously embedded into
the space $C_{0}(\mathbb{R}^{d}\times\mathbb{S}^{d-1})$.

In the following we assume that the reproducing kernel of $W$ is of the form
$k_{e}\otimes k_{t}$, with the assumptions of proposition 1. We also assume
that $k_{e}$ and $k_{t}$ are non negative functions. In practice, we will use
for $k_{e}:{(\mathbb{R}^{d})}^{2}\rightarrow\mathbb{R}$ a gaussian kernel
$k_{e}(x,y)=e^{-\|x-y\|^{2}/\sigma_{W}^{2}}$, where $\sigma_{W}$ is a scale
parameter, and for $k_{t}:{(\mathbb{S}^{d-1})}^{2}\rightarrow\mathbb{R}$ the
kernel $k_{t}(u,v)=e^{\langle\,u,v\rangle_{\mathbb{R}^{d}}}$

We associate with shape $S$ the canonical function $\omega_{S}\in W$ defined
for all $y\in\mathbb{R}^{d}$ and $\tau\in\mathbb{S}^{d-1}$ as follows:

$\omega_{S}(y,\tau)=\int_{S}k_{e}(y,x)k_{t}(\tau,\tau_{x}S)dx\,.$

This function corresponds to the unique representer of the varifold
$\mu_{S}\in W^{\prime}$ via the Riesz representation theorem. Similarly, we
define the canonical function $\omega_{T}$ associated with shape $T$. Via this
representation of shapes, one may express the scalar product between the
varifolds $\mu_{S},\mu_{T}$, or equivalently between the canonical functions
$\omega_{S},\omega_{T}$ as follows:

$\displaystyle\langle\,\mu_{S},\mu_{T}\rangle_{W^{\prime}}=\langle\,\omega_{S},\omega_{T}\rangle_{W}=\int_{S}\int_{T}k_{e}(x,y)k_{t}(\tau_{x}S,\tau_{y}T)dx\,dy\,.$

Finally, the shape matching distance as defined in [10] is the following:

$\displaystyle d_{W^{\prime}}(S,T)^{2}$ $\displaystyle=$
$\displaystyle\|\omega_{S}-\omega_{T}\|_{W}^{2}=\|\mu_{S}-\mu_{T}\|_{W^{\prime}}^{2}$
$\displaystyle=$
$\displaystyle\langle\,\mu_{S},\mu_{S}\rangle_{W^{\prime}}-2\langle\,\mu_{S},\mu_{T}\rangle_{W^{\prime}}+\langle\,\mu_{T},\mu_{T}\rangle_{W^{\prime}}\,.$

In order to adapt this distance for partial matching, a first and intuitive
way could be to use half of the expression as follows:

$\Delta(S,T)=\langle\,\mu_{S},\mu_{T}-\mu_{S}\rangle_{W^{\prime}}^{2}=\langle\,\mu_{S},\mu_{S}-\mu_{T}\rangle_{W^{\prime}}^{2}.$

The intuition behind this definition is that if $S$ is a subset of $T$, then
$\mu_{T}-\mu_{S}$ is the varifold corresponding to $T\setminus S$, which is
disjoint from shape $S$ and thus roughly orthogonal to it from the varifold
metric viewpoint.

Yet, if $S=S_{1}\sqcup S_{2}$, a mismatch of $S_{1}$ into $T$, characterized
by $\langle\,\mu_{S_{2}},\mu_{S}-\mu_{T}\rangle_{W^{\prime}}>0$, can be
compensated by an overrated characterization of the inclusion $S_{2}\subset T$
with $\langle\,\mu_{S_{2}},\mu_{S}-\mu_{T}\rangle_{W^{\prime}}<0$, which
happens if the mass of $T$ around ${S_{2}}$ is larger than the mass of
${S_{2}}$. Hence, we introduce in this paper a localized characterization of
the inclusion.

###  2.2 Definition of the partial matching dissimilarity

To simplify the notation, we denote for $x,x^{\prime}\in S$,
$\vec{\mathbf{x}}=(x,\tau_{x}S)$,
$\omega_{S}(\vec{\mathbf{x}})=\omega_{S}(x,\tau_{x}S)$ and
$k(\vec{\mathbf{x}},\vec{\mathbf{x}}^{\prime})=k_{e}(x,x^{\prime})k_{t}(\tau_{x}S,\tau_{x^{\prime}}S)$.

###### Definition 1

Let $g:\mathbb{R}\mapsto\mathbb{R}$ defined as $g(s)=(\max(0,s))^{2}$. We
define the partial matching dissimilarity as follows:

$\displaystyle\Delta(S,T)$ $\displaystyle=$
$\displaystyle\int_{S}g\left(\omega_{S}(\vec{\mathbf{x}})-\omega_{T}(\vec{\mathbf{x}})\right)dx$
$\displaystyle=$
$\displaystyle\int_{S}g\left(\int_{S}k(\vec{\mathbf{x}},\vec{\mathbf{x}}^{\prime})dx^{\prime}-\int_{T}k(\vec{\mathbf{x}},\vec{\mathbf{y}})dy\right)dx\,.$

With $g(s)=s$, we would retrieve
$\langle\,\mu_{S},\mu_{S}-\mu_{T}\rangle_{W^{\prime}}$. The threshold
$\max(0,\cdot)$ prevents the compensation of a local mismatch by an overrated
match in another area.

###### Proposition 2

If $S\subset T$, $\Delta(S,T)=0$.

Since $k_{e}$ and $k_{t}$ are assumed to be non negative functions, we have

$\displaystyle\Delta(S,T)$ $\displaystyle=$
$\displaystyle\int_{S}g\left(\int_{S}k(\vec{\mathbf{x}},\vec{\mathbf{y}})dy-\int_{T}k(\vec{\mathbf{x}},\vec{\mathbf{y}})dy\right)dx$
(1) $\displaystyle=$ $\displaystyle\int_{S}g\left(-\int_{{T\setminus
S}}k(\vec{\mathbf{x}},\vec{\mathbf{y}})dy\right)dx=0\,.\quad\squareforqed$

The next proposition highlights the local nature of the dissimilarity function
$\Delta$.

###### Proposition 3

If $S^{\prime}\subset S$, then $\Delta(S^{\prime},T)\leq\Delta(S,T)$. In
particular, if
${\Delta(S,T)=0}$ then for any subset $S^{\prime}$ of $S$,
$\Delta(S^{\prime},T)=0$.

Since $k\geq 0$, we have for any $S^{\prime}\subset S$ and any
$\vec{\mathbf{y}}\in\mathbb{R}^{d}\times\mathbb{S}^{d-1}$

$\omega_{S^{\prime}}(\vec{\mathbf{y}})=\int_{S^{\prime}}k(\vec{\mathbf{x}},\vec{\mathbf{y}})dx\leq\int_{S}k(\vec{\mathbf{x}},\vec{\mathbf{y}})dx=\omega_{S}(\vec{\mathbf{y}})\,.$

Hence, since $g$ is an increasing function

${g\left(\omega_{S^{\prime}}(\vec{\mathbf{y}})-\omega_{T}(\vec{\mathbf{y}})\right)\leq
g\left(\omega_{S}(\vec{\mathbf{y}})-\omega_{T}(\vec{\mathbf{y}})\right)}$

and thus
$\displaystyle\Delta(S^{\prime},T)\leq\int_{S}g\left(\omega_{S}(\vec{\mathbf{x}})-\omega_{T}(\vec{\mathbf{x}})\right)dx=\Delta(S,T)$.
$\quad\squareforqed$

In the next proposition, we show that $\Delta$ does not satisfies the property
$\Delta(S,T)=0\Rightarrow S\subseteq T$.

###### Proposition 4

Consider the two following shapes. The source is a segment
$S_{\epsilon}=\\{(s,\epsilon)\,|\,s\in[-\alpha,\alpha]\\}$ slightly shifted by
a step $\epsilon>0$ above a larger target
$T=\\{(t,0)\,|\,t\in[-\beta,\beta]\\}$, with $0<\alpha<\beta$. Since the
tangent vectors are almost all equal, we can ignore $k_{t}$ and consider a
kernel $k_{e}$ defined by a decreasing function
$\rho:\mathbb{R}^{+}\to\mathbb{R}^{+}$ as follows
$k_{e}(x,x^{\prime})=\rho(|x-x^{\prime}|^{2})$. Then for any such $\rho$,
there exists $(\epsilon,\alpha,\beta)$ such that
$\Delta(S_{\epsilon}^{\alpha},T^{\beta})=0$ and $S_{\epsilon}^{\alpha}\cap
T^{\beta}=\emptyset$.

We need to show that for any $x_{0}\in S$,
$\omega_{S}(x_{0})\leq\omega_{T}(x_{0})$ where
$\omega_{S}(x_{0})=\int_{S}k_{e}(x_{0},x)dx$ and
$\omega_{T}(x_{0})=\int_{T}k_{e}(x_{0},x^{\prime})dx^{\prime}$. Denote
$x=(s,\epsilon)\in S$, $x_{0}=(s_{0},\epsilon)\in S$ and $x^{\prime}=(t,0)\in
T$ then $\|x-x_{0}\|^{2}=\|(s,\epsilon)-(s_{0},\epsilon)\|^{2}=(s-s_{0})^{2}$
and
$\|x^{\prime}-x_{0}\|^{2}=\|(t,\epsilon)-(s_{0},\epsilon)\|^{2}=(t-s_{0})^{2}+\epsilon^{2}$.
We then obtain

$\omega_{S}(x_{0})=\int_{-\alpha}^{\alpha}\rho((s-s_{0})^{2})ds,\qquad\qquad\omega_{T}(x_{0})=\int_{-\beta}^{\beta}\rho((s-s_{0})^{2}+\epsilon^{2})ds\,.$

Denote these integrals
$I_{\alpha}(s_{0})=\int_{-\alpha}^{\alpha}\rho((s-s_{0})^{2})ds$ and
$I_{\beta}(s_{0},\epsilon)=\int_{-\beta}^{\beta}\rho((s-s_{0})^{2}+\epsilon^{2})ds$.
The integrands are symmetric with respect to $s=s_{0}$ and since $\rho$ is
decreasing, we have the following inequalities:

$\displaystyle\mbox{for any }s_{0}\in[-\alpha,\alpha],\qquad$ $\displaystyle
I_{\alpha}(\alpha)\leq I_{\alpha}(s_{0})\leq I_{\alpha}(0),$ (2)
$\displaystyle\mbox{for any }s_{0}\in[-\alpha,\alpha],\mbox{for any
}\epsilon>0,\qquad$ $\displaystyle I_{\beta}(\alpha,\epsilon)\leq
I_{\beta}(s_{0},\epsilon)\leq I_{\beta}(0,\epsilon).$ (3)

Let us now show that there exist $(\epsilon,\alpha,\beta)$ such that
$I_{\alpha}(0)\leq I_{\beta}(\alpha,\epsilon)$ that is
$\int_{-\alpha}^{\alpha}\rho(s^{2})ds\leq\int_{-\beta}^{\beta}\rho((s-\alpha)^{2}+\epsilon^{2})ds$.
For $\alpha$ small enough and $\beta$ large enough,
$\int_{-\beta}^{\beta}\rho((s-\alpha)^{2}+\epsilon^{2})ds\geq\int_{-2\alpha}^{2\alpha}\rho(s^{2}+\epsilon^{2})ds$.
This last integral tends to $\int_{-2\alpha}^{2\alpha}\rho(s^{2})ds$ when
$\epsilon$ tends to $0$ and this limit is strictly larger than $I_{\alpha}(0)$
(with $\alpha$ small enough, $\rho(\alpha)>0$). Thus, for $\epsilon$ small
enough, we have $I_{\alpha}(0)<I_{\beta}(\alpha,\epsilon)$.
Thanks to eq. (2) and (3), we deduce that for any $x_{0}\in S$,
$\omega_{S}(x_{0})\leq\omega_{T}(x_{0})$. $\quad\squareforqed$

This example shows that if the mass of the target is larger than the mass of
the source then this excess of mass can compensate the lack of alignment
between the shapes. For this reason, we introduce a normalized dissimilarity
term.

###  2.3 Normalized partial matching dissimilarity

Assume that $x_{0}\in S$ and $y_{0}\in T$ are two close points. If around
these points, the mass of $T$ is twice the mass of $S$, i.e.
$\omega_{S}(\vec{\mathbf{x}}_{0})\approx\frac{1}{2}\omega_{T}(\vec{\mathbf{y}}_{0})$,
then the local embedding of $S$ in $T$ is characterized by
$\omega_{S}(\vec{\mathbf{x}}_{0})\leq\frac{1}{2}\omega_{T}(\vec{\mathbf{x}}_{0})$
and more generally by
$\omega_{S}(\vec{\mathbf{x}}_{0})\leq\frac{\omega_{S}(\vec{\mathbf{x}}_{0})}{\omega_{T}(\vec{\mathbf{y}}_{0})}\omega_{T}(\vec{\mathbf{x}}_{0})$.
Conversely, if the mass of $S$ is twice the mass of $T$, then we consider that
locally $S\varsubsetneq T$ (e.g. two branches of a tree should not match the
same branch of a target). Hence, the criterion of Definition 1 should be
preserved :
$\omega_{S}(\vec{\mathbf{x}}_{0})\leq\omega_{T}(\vec{\mathbf{x}}_{0})$ is not
satisfied. These observations lead to a new dissimilarity term that
encompasses these two cases.

###### Definition 2

Using the same threshold function $g$ as in Definition 1, we define the
partial matching normalized dissimilarity as follows:

$\displaystyle\underline{\Delta}(S,T)$ $\displaystyle=$
$\displaystyle\int_{S}g\left(\omega_{S}(\vec{\mathbf{x}})-\int_{T}{\min}_{\epsilon}\left(1,\dfrac{\omega_{S}(\vec{\mathbf{x}})}{\omega_{T}(\vec{\mathbf{y}})}\right)k(\vec{\mathbf{x}},\vec{\mathbf{y}})dy\right)dx$

where $\min_{\epsilon}(1,s)=\frac{s+1-\sqrt{\epsilon+(s-1)^{2}}}{2}$ with
$\epsilon>0$ small, is used as a smooth approximation of the $\min(1,\cdot)$
function.

###  2.4 Use in the LDDMM setting

The framework we propose is sufficiently flexible to be embedded in a variety
of inexact registration methods; in this paper, we focus on the LDDMM model
described in [3]. In this model, diffeomorphisms are constructed as flows of
time-dependent square integrable velocity fields $t\in[0,1]\mapsto v_{t}$,
each $v_{t}$ belonging to a predefined Hilbert space $V$ of smooth vector
fields. In the following we will denote $\phi^{v}_{1}$ the diffeomorphism of
$\mathbb{R}^{d}$, solution at $t=1$ of the flow equation
$\partial_{t}\phi^{v}_{t}=v_{t}\circ\phi^{v}_{t}$ with initial condition
$\phi^{v}_{0}=id$.

###### Proposition 5

Let $\lambda>0$ be a fixed parameter. The partial matching problem, which
consists in minimizing over $L_{V}^{2}$ the function :

$J(v)=\lambda\int_{0}^{1}\|v_{t}\|_{V}^{2}dt+\underline{\Delta}({\phi_{1}^{v}(S)},T)\,,$

has a solution.

From [14], theorem 7, the proof boils down to showing that the mapping
$v\mapsto A(v)=\underline{\Delta}({\phi_{1}^{v}(S)},T),$ is weakly continuous
on $L_{V}^{2}$. Let $(v_{n})$ be a sequence in $L^{2}_{V}$, weakly converging
to some $v\in L^{2}_{V}$. We need to show that
$\underline{\Delta}(\phi_{1}^{v_{n}}(S),T)\longrightarrow\underline{\Delta}(\phi_{1}^{v}(S),T)$.
To simplify we denote $S_{n}=\phi_{1}^{v_{n}}(S)$, $S_{*}=\phi_{1}^{v}(S)$ and
for any $\vec{\mathbf{x}}\in\mathbb{R}^{d}\times\mathbb{S}^{d-1}$,
$\displaystyle
f_{n}(\vec{\mathbf{x}})=\omega_{S_{n}}(\vec{\mathbf{x}})-\int_{T}{\min}_{\epsilon}\left(1,\dfrac{\omega_{{S_{n}}}(\vec{\mathbf{x}})}{\omega_{T}(\vec{\mathbf{y}})}\right)k(\vec{\mathbf{x}},\vec{\mathbf{y}})dy$
and $f_{*}(\vec{\mathbf{x}})$ likewise for $S_{*}$.
We then have

$\displaystyle\underline{\Delta}({S_{n}},T)-\underline{\Delta}({S_{*}},T)$
$\displaystyle=\mu_{S_{n}}(g\circ f_{n})-\mu_{S_{*}}(g\circ f_{*})\,.$ (4)

The area formula

$\displaystyle\mu_{\phi(S)}(\omega)=\int_{S}\omega(\phi(x),d_{x}\phi(\tau_{x}S))\left|{d_{x}\phi}_{|\tau_{x}S}\right|dx,$

leads to

$\displaystyle\Big{|}\mu_{S_{n}}(g\circ f_{n})-\mu_{S_{*}}(g\circ
f_{*})\Big{|}\leq\int_{S}\Big{|}g\circ
f_{n}(\phi^{n}(x),d_{x}\phi^{n}(\tau_{x}S))\cdot\left|{d_{x}\phi^{n}}_{|\tau_{x}S}\right|$
$\displaystyle-g\circ
f_{*}(\phi(x),d_{x}\phi(\tau_{x}S))\cdot\left|{d_{x}\phi}_{|\tau_{x}S}\right|\Big{|}dx$
$\displaystyle\leq\int_{S}$ $\displaystyle\Big{|}g\circ
f_{n}(\phi^{n}(x),d_{x}\phi^{n}(\tau_{x}S))\cdot\left|{d_{x}\phi^{n}}_{|\tau_{x}S}\right|-g\circ
f_{n}(\phi(x),d_{x}\phi(\tau_{x}S))\cdot\left|{d_{x}\phi}_{|\tau_{x}S}\right|$
$\displaystyle+g\circ
f_{n}(\phi(x),d_{x}\phi(\tau_{x}S))\cdot\left|{d_{x}\phi}_{|\tau_{x}S}\right|-g\circ
f_{*}(\phi(x),d_{x}\phi(\tau_{x}S))\cdot\left|{d_{x}\phi}_{|\tau_{x}S}\right|\Big{|}dx$
$\displaystyle\leq\int_{S}$ $\displaystyle|g\circ
f_{n}|_{\infty}\cdot\Big{|}\left|{d_{x}\phi^{n}}_{|\tau_{x}S}\right|-\left|{d_{x}\phi}_{|\tau_{x}S}\right|\Big{|}+\left|d_{x}\phi\right|_{\infty}|g\circ
f_{n}-g\circ f_{*}|_{\infty}\,dx\,.$

Since $d_{x}\phi^{n}$ converge to $d_{x}\phi$, uniformly on $x\in S$ ([14]),
we only need to show that $|g\circ f_{n}-g\circ f_{*}|_{\infty}\to 0$. We
first show that $|f_{n}-f_{*}|_{\infty}\to 0$. For any
$\vec{\mathbf{x}}\in\mathbb{R}^{d}\times\mathbb{S}^{d-1}$

$\displaystyle f_{n}(\vec{\mathbf{x}})-f_{*}(\vec{\mathbf{x}})=$
$\displaystyle\omega_{S_{n}}(\vec{\mathbf{x}})-\omega_{S_{*}}(\vec{\mathbf{x}})$
(5)
$\displaystyle+\int_{T}k(\vec{\mathbf{x}},\vec{\mathbf{y}})\left[{\min}_{\epsilon}\left(1,\dfrac{\omega_{{S_{n}}}(\vec{\mathbf{x}})}{\omega_{T}(\vec{\mathbf{y}})}\right)-{\min}_{\epsilon}\left(1,\dfrac{\omega_{S_{*}}(\vec{\mathbf{x}})}{\omega_{T}(\vec{\mathbf{y}})}\right)\right]dy\,.$
(6)

Since $W$ is continuously embedded in
$C_{0}^{2}(\mathbb{R}^{d}\times\mathbb{S}^{d-1})$, there exists $c_{W}$ such
that for any $n$, $|\omega_{S_{n}}-\omega_{S_{*}}|_{\infty}\leq
c_{W}|\omega_{S_{n}}-\omega_{S_{*}}|_{W}$. Moreover, since $v_{n}$ weakly
converges to $v$, Corollary 1 from [7] ensures that
$|\omega_{S_{n}}-\omega_{S_{*}}|_{W}\to 0$.
Regarding the integral, since $\mathbb{R}\ni s\mapsto\min_{\epsilon}(1,s)$ is
Lipschitz, there exists $c_{\epsilon}>0$ such that

$\displaystyle\left|\int_{T}k(\vec{\mathbf{x}},\vec{\mathbf{y}})\left[{\min}_{\epsilon}\left(1,\dfrac{\omega_{{S_{n}}}(\vec{\mathbf{x}})}{\omega_{T}(\vec{\mathbf{y}})}\right)-{\min}_{\epsilon}\left(1,\dfrac{\omega_{S_{*}}(\vec{\mathbf{x}})}{\omega_{T}(\vec{\mathbf{y}})}\right)\right]dy\right|$
(7)
$\displaystyle\leq\int_{T}\dfrac{k(\vec{\mathbf{x}},\vec{\mathbf{y}})}{|\omega_{T}(\vec{\mathbf{y}})|}c_{\epsilon}|\omega_{S_{n}}(\vec{\mathbf{x}})-\omega_{S_{*}}(\vec{\mathbf{x}})|dy\leq
c_{\epsilon}c_{W}|\omega_{S_{n}}-\omega_{S_{*}}|_{W}\int_{T}\dfrac{k(\vec{\mathbf{x}},\vec{\mathbf{y}})}{\omega_{T}(\vec{\mathbf{y}})}dy$
(8)

Since $T$ is compact and $\omega_{T}$ is continuous and strictly positive on
$\vec{\mathbf{T}}=\\{(y,\tau_{y}T)\,|\,y\in T\\}$, we have
$c_{T}=\inf_{\vec{\mathbf{T}}}\omega_{T}(\vec{\mathbf{y}})>0$ so that
$\displaystyle\int_{T}\frac{k(\vec{\mathbf{x}},\vec{\mathbf{y}})}{\omega_{T}(\vec{\mathbf{y}})}dy\leq\frac{\omega_{T}(\vec{\mathbf{x}})}{c_{T}}\leq\frac{c_{W}|\omega_{T}|_{W}}{c_{T}}<+\infty$.
This shows that $|f_{n}-f_{*}|_{\infty}\to 0$. Now, since $f_{*}$ is bounded,
there exists $M>0$ such that for any $n$,
$|f_{*}|_{\infty}+|f_{n}|_{\infty}\leq M$ and since $g$ is locally Lipschitz,
we deduce that $|g\circ f_{n}-g\circ f_{*}|_{\infty}\to 0\,.$
$\quad\squareforqed$

####  2.4.1 Discrete formulation.

The discrete versions of the partial matching dissimilarities can be derived
very straightforwardly, following the same discrete setting described in [9]
for varifold matching. We omit its complete description here. The LDDMM
registration procedure is numerically solved via a geodesic shooting algorithm
[21], optimizing on a set of initial momentum vectors located at the
discretization points of the source shape.

##  3 Experiments

In order to evaluate the proposed dissimilarity terms, we conducted three
experiments on two different types of data : two on sets of 3D-curves (one
synthetic and one real) and one on surfaces. In all the following experiments,
we initialize the registration by aligning objects barycenters since no prior
positioning is known in our applications. To model non-rigid deformations, we
define the reproducing kernel $K_{V}$ of $V$ to be a sum of Gaussian kernels
$K_{V}(x,y)=\sum_{s}\exp\left(-\|x-y\|^{2}\;/\;(\sigma_{0}/s)^{2}\right)$,
where $s\in[1,4,8,16]$ and $\sigma_{0}$ is about half the size of the shapes
bounding boxes. For each set of experiments we use the same hyperparameters
($\sigma_{0},\sigma_{W},\lambda$) to compare the influence of the data
attachment terms. Our Python implementation makes use of the libraries PyTorch
[23] and KeOps [8], to benefit from automatic differentiation and GPU
acceleration of kernel convolutions.

(a)

(b)

(c)

(d)

Figure 1:  Diffeomorphic registrations of a trimmed tree (blue) onto a richer
one (red). (a) Initial Positions; (b) Varifold registration; (c) Partial
matching registration (Eq. 1); (d) Normalized partial matching registration
(Eq. 2).

Synthetic experiment. A first experiment was conducted to validate our
approach on synthetic trees of 3D-curves. The target is composed of six
3D-curves (red tree in Fig.1.(a)), while the source (blue colored tree in
Fig.1.(a)) is a trimmed version of the target. Then we apply to the source a
random diffeomorphic deformation $\psi$ that we will try to retrieve by
registration.

We have shown in Fig.1 that the classic distance aims at registering the
entire source onto the entire target. This leads to abnormal distortions of
the source curves that can be observed in the light blue stretched curve in
Fig.1.(b). On the contrary, both partial dissimilarity terms successfully
guide the registration of the source onto a subset of the target. The main
difference between these two terms can be seen in the bifurcations’
neighborhoods : the partial matching dissimilarity fails to register the
source curves when the normalized partial matching doesn’t fall into a flat
local minima. The excess of mass in the target at the bifurcation has no
negative effect with the normalization.

Registration of a template onto a real vascular tree. Now that we have
illustrated the potential of our method on a toy example, we continue on
entire vascular trees extracted from real patients datasets. Finding
correspondences between the annotated template and a raw target is of great
interest in clinical applications such as interventional radiology, and could
provide automatic partial annotation of the imaged vascular tree.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

Figure 2:  (a) Template composed of different arteries of interest. (b),(e)
Real vascular trees. (c),(f) Varifold registrations. (d),(g) Normalized
partial matching registrations (Eq. 2).

Because of the high topological variability of the vasculature, there is no
perfect template of all the patients, and a simpler template seems suited. The
target tree (Fig.2. (b), (e)) is obtained by automatic centerlines extraction
from an injected CBCT inspired from the fast marching method ([11]) that have
been labeled by a clinical expert. The source tree (Fig.2.(a)) is a manually
simplified template in which arteries of interest have been selected.

This experiment is particularly difficult in the classic LDDMM framework, and
the partial normalized dissimilarity term introduces a meaningful deformation
of the simple template onto a subset of the target despite the wide
topological difference.

(a)

(b)

(c)

(d)

Figure 3:  Registration of a truncated liver’s surface from a CBCT (a) onto a
complete liver’s surface from a CT (b). The deformed surfaces are colored by
the determinant of the Jacobian. (c) Varifold registration; (d) Partial
normalized registration (2) (d).

Liver Surface registration with truncation. In the third experiment, we
register a truncated liver surface manually segmented from a CBCT onto a
complete liver surface manually segmented from a CT scan. In CBCT exams, the
livers are usually larger than the field of view, causing the truncation of
the surface. Both acquisitions come from the same patient and are separated in
time by one month.

We show in Fig. 3 the registrations results of the LDDMM associated to the
distance in the space of Varifolds and to the normalized partial dissimilarity
term. The deformed shapes are colored by the determinant of the Jacobian of
the deformation, that can be seen as its intensity. As expected the Varifold
distance leads to unrealistic deformation that tends to fill the holes in the
source shape to cover the entire target. From the anatomical and medical point
of view this is misleading. On the contrary the partial matching allows a
coherent deformation of the source.

##  4 Conclusion

In this paper we adapted the scalar product of Hilbert spaces of Varifolds to
guide partial shape matching and registration. We applied this new data
attachment to the registration of a template vascular tree onto real cases. We
also showed that it is suitable for the registration of a truncated surface
onto a complete one. This data term is suited to different shapes comparison
such as unions of curves or surfaces.

The main bottleneck of our approach is the risk of shrinkage when no easy
registration is possible. A promising lead to tackle this issue would be to
also find a subset of the target to include in the source, such as [5]. The
dissimilarity term introduced can be modified to fit the problem of
registering a complete shape onto a truncated one. In further work we would
also like to extend this dissimilarity term to other space of representations
such as the Normal Cycles or the functional Varifolds.

#####

Acknowledgement We would like to thank Perrine Chassat for her early work on
the partial matching , allowing us to easily adapt the new data fidelity terms
to the real case of liver surfaces registrations.

## References

  * [1] Aiger, D., Mitra, N., Cohen-Or, D.: 4-points congruent sets for robust pairwise surface registration. 35th International Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’08) 27 (08 2008). https://doi.org/10.1145/1399504.1360684
  * [2] Bashiri, F.S., Baghaie, A., Rostami, R., Yu, Z., D’Souza, R.: Multi-modal medical image registration with full or partial data: A manifold learning approach. Journal of Imaging 5, 5 (12 2018). https://doi.org/10.3390/jimaging5010005
  * [3] Beg, M.F., Miller, M., Trouvé, A., Younes, L.: Computing large deformation metric mappings via geodesic flows of diffeomorphisms. International Journal of Computer Vision 61, 139–157 (02 2005). https://doi.org/10.1023/B:VISI.0000043755.93987.aa
  * [4] Benseghir, T., Malandain, G., Vaillant, R.: Iterative closest curve: A framework for curvilinear structure registration application to 2d/3d coronary arteries registration pp. 179–186 (2013)
  * [5] Bronstein, A., Bronstein, M., Bruckstein, A., Kimmel, R.: Partial similarity of objects, or how to compare a centaur to a horse. International Journal of Computer Vision 84, 163–183 (08 2009). https://doi.org/10.1007/s11263-008-0147-3
  * [6] Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching. Proceedings of the National Academy of Sciences 103(5), 1168–1172 (2006). https://doi.org/10.1073/pnas.0508601103
  * [7] Charlier, B., Charon, N., Trouvé, A.: The fshape framework for the variability analysis of functional shapes. Found Comput Math 17, 287–357 (2017)
  * [8] Charlier, B., Feydy, J., Glaunès, J.A., Collin, F.D., Durif, G.: Kernel operations on the gpu, with autodiff, without memory overflows (2020), https://www.kernel-operations.io/keops/index.html
  * [9] Charon, N., Charlier, B., Glaunès, J., Gori, P., Roussillon, P.: 12 - fidelity metrics between curves and surfaces: currents, varifolds, and normal cycles pp. 441 – 477 (2020). https://doi.org/https://doi.org/10.1016/B978-0-12-814725-2.00021-2
  * [10] Charon, N., Trouvé, A.: The varifold representation of nonoriented shapes for diffeomorphic registration. SIAM Journal on Imaging Sciences 6(4), 2547–2580 (2013). https://doi.org/10.1137/130918885
  * [11] Deschamps, T., Cohen, L.D.: Fast extraction of minimal paths in 3d images and applications to virtual endoscopy. Medical image analysis 5(4), 281–99 (2001)
  * [12] Feragen, A., Petersen, J., de Bruijne, M., et al.: Geodesic atlas-based labeling of anatomical trees: Application and evaluation on airways extracted from ct. IEEE Transactions on Medical Imaging 34, 1212–1226 (2015)
  * [13] Feydy, J., Charlier, B., Vialard, F.X., Peyré, G.: Optimal transport for diffeomorphic registration. Lecture Notes in Computer Science p. 291–299 (2017), http://dx.doi.org/10.1007/978-3-319-66182-7˙34
  * [14] Glaunès, J.: Transport par difféomorphismes de points, demesures et de courants pour la comparaison de formes et l’anatomie numérique. (2005)
  * [15] Halimi, O., Litany, O., Rodolà, E.R., Bronstein, A.M., Kimmel, R.: Unsupervised learning of dense shape correspondence pp. 4365–4374 (2019). https://doi.org/10.1109/CVPR.2019.00450
  * [16] Halimi, O., Imanuel, I., Litany, O., Trappolini, G., Rodolà, E., Guibas, L.J., Kimmel, R.: The whole is greater than the sum of its nonrigid parts. CoRR abs/2001.09650 (2020)
  * [17] van Kaick, O., Zhang, H., Hamarneh, G.: Bilateral maps for partial matching. Computer Graphics Forum (CGF) (09 2013). https://doi.org/10.1111/cgf.12084
  * [18] van Kaick, O., Zhang, H., Hamarneh, G., Cohen-Or, D.: A survey on shape correspondence. Computer Graphics Forum 30(6), 1681–1707 (2011), https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-8659.2011.01884.x
  * [19] Kaltenmark, I., Charlier, B., Charon, N.: A general framework for curve and surface comparison and registration with oriented varifolds (July 2017)
  * [20] Kaltenmark, I., Trouvé, A.: Estimation of a Growth Development with Partial Diffeomorphic Mappings. Quaterly of Applied Mathematics 77, 227–267 (Nov 2018)
  * [21] Miller, M.I., Trouvé, A., Younes, L.: Geodesic shooting for computational anatomy. Journal of Mathematical Imaging and Vision 24(2), 209–228 (Mar 2006)
  * [22] Ovsjanikov, M., Ben-Chen, M., Solomon, J., Butscher, A., Guibas, L.: Functional maps: A flexible representation of maps between shapes. ACM Trans. Graph. 31(4) (Jul 2012). https://doi.org/10.1145/2185520.2185526
  * [23] Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., Lerer, A.: Automatic differentiation in PyTorch. In: NIPS Autodiff Workshop (2017)
  * [24] Rodolà, E., Cosmo, L., Bronstein, M.M., Torsello, A., Cremers, D.: Partial functional correspondence. Computer Graphics Forum 36(1), 222–236 (2017). https://doi.org/https://doi.org/10.1111/cgf.12797
  * [25] Rodolà, E., Albarelli, A., Bergamasco, F., Torsello, A.: A scale independent selection process for 3d object recognition in cluttered scenes. International Journal of Computer Vision 102 (03 2013). https://doi.org/10.1007/s11263-012-0568-x
  * [26] Sotiras, A., Davatzikos, C., Paragios, N.: Deformable medical image registration: A survey. IEEE Transactions on Medical Imaging 32(7), 1153–1190 (July 2013). https://doi.org/10.1109/TMI.2013.2265603
  * [27] Zhen, X., Gu, X., Yan, H., Zhou, L., Jia, X., Jiang, S.B.: 57(21), 6807–6826 (oct 2012). https://doi.org/10.1088/0031-9155/57/21/6807