Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

AN ITERATIVE CLOSEST POINT METHOD FOR MEASURING THE
LEVEL OF SIMILARITY OF 3D LOG SCANS IN WOOD INDUSTRY
,

,

,

1

Université de Lorraine, Vandœuvre-Lès-Nancy Cedex, France
CNRS, CRAN, UMR7039, France. cyrine.selma.tn@ieee.org,
{hind.el-haouzi, philippe.thomas}@univ-lorraine.fr
3
Department of Computer Science and Software Engineering, Université Laval,
Québec, QC, Canada.
4
FORAC Research Consortium, Université Laval, Québec, Canada.
jonathan.gaudreault@ift.ulaval.ca
5
Department of Mechanical and Industrial Engineering, University of Toronto,
Toronto, ON, Canada. mmorin@mie.utoronto.ca
2

ABSTRACT
In the Canadian’s lumber industry, simulators are used to predict the
lumbers resulting from the sawing of a log at a given sawmill. Giving a
log or several logs’ 3D scans as input, simulators perform a real-time
job to predict the lumbers. These simulators, however, tend to be slow
at processing large volume of wood. We thus explore an alternative
approximation techniques based on the Iterative Closest Point (ICP)
algorithm to identify the already processed log to which an unseen log
resembles
the
most.
The main benefit of the ICP approach is that it can easily handle 3D
scans with a variable number of points. We compare this ICP-based
nearest neighbor predictor, to predictors built using machine learning
algorithms such as the K-nearest-neighbor (kNN) and Random Forest
(RF). The implemented ICP-based predictor enabled us to identify key
points in using the 3D scans directly for distance calculation. The longterm goal of this on-going research is to integrated ICP distance
calculations and machine learning.
Keywords: Sawing simulation, iterative closest point, machine learning
application

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

1. INTRODUCTION
The wood-products industry is facing numerous challenges regarding
the maximization of profits and sales when sawmilling. Natural forest
resources are characterized by their high heterogeneity and the
sawing of a log at a given sawmill is a complex physical process of
which the output is not easily forecasted. It is nonetheless critical to
decide which contracts to accept based on raw material resources,
which sawmill to supply from which cutblocks, and how to configure
the parameters of the sawmilling equipment in order to improve the
profits and the sales.
Sawing simulators, such as Optitek [1], have been used for years to
forecast the production of sawmills and to help at these tasks. They
are, for instance, especially useful for sawmill design where time is not
an issue [5]. Given the three-dimensional (3D) scan of a log and a
sawmill’s model, a sawing simulator outputs, among other
information, the different pieces of wood that will result from the
sawing [1]. Unfortunately, simulators tend to be slow and complex to
use when working on large customers’ demand under time
constraints.
Machine learning algorithms such as K-nearest neighbors (k-NN) [2],
decision tree (DT) [3] and random forest (RF) [4] were proposed as a
complement to sawing simulation [5]. The authors evaluate machine
learning approaches at the task of predicting the lumbers produced at
a given sawmill when processing a given log. Based on simple decision
rules and using six characteristics of an input log instead of the 3D
scan, the predictors built using a machine learning approach are able
to approximate the simulator’s response of a sawmill producing 19
different lumber products. The technique involved learning the
relationship between an input log, described in terms of six features
(volume, length, wide-end diameter, narrow-end diameter, and
shrinking), and the quantity of every lumber type produced at the
plant when sawing it [5].
In this work, we study the usability of the Iterative Closest Point (ICP)
algorithm [7, 8] as a mean to measure the resemblance between an
input logs and already sawn logs. The ICP algorithm has the ability to
exploit the entire amount of data (3D scans) available to determine
the level of resemblance between two logs by measuring the
minimum distance between the two point clouds of their
corresponding scans. We used a simple nearest neighbor approach
where the produced basket is determined by calculating the
minimums of the distances between the input log and the logs of a
given training set. Although standard machine learning approaches
outperform this simple predictive technique, this research shed some

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

light on the principal noise sources that render the ICP approach less
effective for prediction.
This paper is structured as follows. We overview the current
approaches used to approximate the sawing process and discuss the
possibility of an ICP-based predictor in Section 2. Then, in section 3,
we explain the ICP method we retained. Experiments and results are
presented in Section 4. We conclude in Section 5.

2. FROM SAWING SIMULATION AND MACHINE LEARNING TO
ITERATIVE CLOSEST POINT
In North America, wood products are standardized by the National
Lumber Grades Authority (NLGA) [6]. Each lumber type has specific
dimensions, grade, value and price. Lumber production is
characterized by a divergent co-productive system; for a single input,
it simultaneously produces multiple outputs showing different
characteristics. The sawing equipment selects the cutting pattern that
maximizes the expected profit. As it is a commodity market, we expect
to sell the entire production. However, not every mill will produce the
same products from the same log. Knowing what each mill would
produce from each log (or batch of logs) allows a company to make
better decisions thus increasing its efficiency. Sawing simulators has
been built especially for that purpose.
Taking the 3D scan of a log as inputs (Figure 1), a sawing simulator
virtually processes the log and allows predicting the products that
could be obtained at the modeled sawmill. However, when there are
tons of logs that must be processed by sawing simulators in a short
period, these simulators tend to be slow and complex to use.

Figure 1: Input of sawing simulators: 3D scan of a log

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

Machine learning was recently proposed as a complement to
simulation to overcome this difficulty [5]. The learning algorithm
build a predictor from known pairs of input and output where each
input is a feature vector representing a log and where its
corresponding output are the quantities of each lumber product
produced at a given sawmill for that log. Once learned, the predictor
can be used to approximate the lumbers resulting from the
transformation of an unseen log at that sawmill. The 3D scans, which
are made of thousands of points and which are of a variable size, were
not used directly for learning.
The ICP-based prediction method we evaluate is based on the nearest
neighbor algorithm [2]. The ICP method is used as a measure of
distance. Based on the geometrical structure of the logs, the ICP
measures the resemblance between the current log and the logs of the
training set to find the closest pair. Using an ICP-based nearest
neighbor, we calculate the distance between the input log and all logs
from the training sets, the minimum of all distances corresponds to
the log to which the input log resembles the most. One of the benefits
of using ICP as a measure of distance is that it can compare two 3D
scans although they might be of a different size in number of points.

3. THE ITERATIVE CLOSEST POINT METHOD
The ICP algorithm was introduced by Best and McKay [7] and Chen
and Medioni [8] in the goal of aligning the 3D point clouds of two
objects by minimizing the distance between them using geometric
transformations (rotations and translations). The ICP algorithm has
two steps:




The first step consists of determining the correspondence
pairs
from two data sets P and X. The goal is to find for
each point in its closest point in .
The second step is to apply a transformation (rotation and
translation) in order to minimize the distance between the
correspondence pairs.

These two steps are repeated until the error is below a given threshold
or until the maximum number of iterations is reached.

3.2 ICP VARIANTS
The three main different variants of the ICP found in the literature are
the point-to-point method introduced by Besl and McKay [10], the

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

point-to-plane technique by Chen and Medioni [8], and the point-toprojection method by Blais and Levine [11]. We present, in the next
section, the point-to-point approach we chose for the experiment.

3.3 THE POINT-TO-POINT REGISTRATION METHOD
Let

and

be two shapes. Shape

is the

model shape onto which we need to align shape P.
Let

be a unit quaternion vector, where
.

and

is the translation vector.

is the transformation vector. The rotation matrix
generated by

is given by:

(1)

Let = (
) be a point of P and
(
The Euclidean distance between and is:

) be a point of X.
(2)

The distance between a point

and the model shape X is:
(3)

The distance between X and the closest point

of X is defined by:
(4)

For
and
to be minimized is given by:

with

, the error function

(5)
The goal of this algorithm is to find the optimal transformation
that minimizes
The center of mass of P and X are given by:

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

(6)
(7)

The cross-covariance matrix of P and X is :
(8)

In order to calculate the vector
where:
.

we use the matrix
is used to calculate
(9)

Where

is the identity matrix.

The optimal rotation vector
maximum eigenvalue of

corresponds to the
.

The optimal translation vector is:
(10)

The ICP algorithm is described below:
1. Given the point set P and the model shape X, the first step in
the ICP algorithm is to initialize the iteration by
=P,
and
.
2. The following steps are then applied until the convergence
within a tolerance τ:
a. Search the closest points:
b. Compute the registration:
c. Apply the registration:
d. Stop the iteration when the change is mean-square
error falls below a present threshold
specifying
the desired precision of the registration:
.
ICP moves the shape object in order to best align it with the model
shape. Translations and rotations are applied iteratively in order to

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

minimize the error metric. The algorithm has been proved to converge
to a local minimum.
4. EXPERIMENTS
The goal of the experiment is to evaluate a predictive approach based
on a standard ICP algorithm at handling the 3D scans for prediction
purposes. No filtering of the 3D scan is performed which means that
some scans are missing points. The ICP-based predictor is compared
to predictors built using the machine learning algorithms presented in
[5]. The ICP algorithm used to compute the distance between the
scans is a standard algorithm from the MATLAB machine learning
library [7].
4.1 DATA
A total of 1207 logs were used for the experiments. The training set
contains 724 logs (60% of the available datasets) and test set contains
483 logs (40% of the logs). As 736 of the 1207 logs only produces
wood chips (they are too small to produce lumber) we also tested for
a subset of our dataset from which we removed those (441 logs in the
training set, 295 in the testing set) leading to two different datasets.
We repeated the experiment 10 times, using different partitions of
each dataset into a training and a test set. The sawmill has 19 lumber
types leading to an output vectors
.
For the ICP-based prediction method, the input for the algorithm is
the 3D vector containing the points that represent the log on a 3D axis.
This vector is variable in length since the number of points in each 3D
scans varies.

4.2 PERFORMANCE EVALUATION
We evaluate the performance of the predictors built by each
algorithm, including the ICP-based algorithm, with the metrics
presented using the following metrics [5]: the zero-one loss, the
hamming distance, the augmented hamming distance, the prediction
score, the production score, and the prediction and production area
score.
A zero-one score
of 1 indicates that the predicted output basket
equals the real output basket
, otherwise
is equal
to 0 [9]:

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

(11)
Given an output vector y
and a predicted output
the
hamming distance
represents the average of number of prediction
errors across products [9]:
(12)
where:
(13)
Given an output basket
and a predicted output
the
augmented hamming distance
is the sum of the ratios of the
minimum between the predicted and the real quantity over the
maximum of these quantities averaged across products [5].
(14)
where:
(15)

Given an output basket y
exists also in the predicted output
the prediction ratio score
is the average bounded ratio of the
real production on the predicted production [5].
(16)
Given an output basket y
exists also in the predicted output
the production ratio score
is the average bounded ratio of the
predicted production on the real production [5]:
(17)

Given an output basket y
exists also in the predicted output
, the production and prediction area score
is computed as
the multiplication of the production and the prediction scores [5]:
(18)

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

The ground-truth output and the predicted output are filtered
before computing the scores to avoid overestimating the predictive
performance of the evaluated predictor. The filtering consists in
removing the product pairs for which both the real and the predicted
values are 0.
4.3 RESULTS AND DISCUSION
Using the ICP algorithm, it was possible to determine for each input
log from the test set, the training log to which it resembles the most.
As a final phase the performance scores were calculated. Table 1
contains the average scores for the ICP-based predictor as well as the
average scores obtained by the predictors built using machine
learning algorithms (as presented in [5]).

Table 1: Average test scores on 10 runs with random partitions of the data
Scores
11-

Scores
11-

MEAN
.0722
.1298
.2037
.537
.6666
.3109

Without empty baskets
DT
RF
KRR
KRR-NO
.5834 .6088 .5376
.5519
.6051 .6331 .5809
.5917
.7172 .7423 .7046
.7118
.841
.8538 .8402
.8432
.8762 .8886 .8644
.8686
.7571 .7779 .7426
.7511

K-NN
.56
.5874
.6989
.7982
.9007
.7344

ICP
.1705
.1879
.2662
.5988
.6674
.4071

MEAN
.1905
.2102
.2428
.6332
.6096
.2964

With empty baskets
DT
RF
KRR
KRR-NO
.7006 .7265 .6841
.6919
.7159 .7398 .7077
.7138
.7839 8044
.783
.786
.8894 .8945 .8885
.8904
.8944 .9099 .8946
.8957
.8056 .8256 .8044
.8077

K-NN
.6979
.7137
.7813
.8635
.9178
.8012

ICP
.3805
.4037
.4798
.7775
.7022
.5427

It is worth mentioning that without the filtering of the couples equal
to zero during the computation of the scores (see Section 4.2), the ICPbased predictor reached more than 90% accuracy with the
score.
When filtering the real and the predicted baskets before computing
the scores, the evaluation scores for the ICP-based predictor
inevitable goes down. This behavior was also observed for the
standard machine learning predictors [5]. In all cases, the scores of
the ICP-based predictor are better than the MEAN algorithm while
being worse than the ones obtained by the predictor built using a
machine learning approach. This is expected since the ICP-based

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

predictor uses a simple nearest neighbor approach. These results also
highlight some of the difficulties encountered by an ICP-based
predictor while comparing the 3D scans. We recall that no prefiltering of the scans is made in this case.

Figure 3: 3D representations of two logs for which the ICP distance is large

The first encountered difficulty is that some logs, although separated
by a large ICP distance, share the same basket of products. This is the
case of the logs presented in Figure 3. These logs are separated by a
large distance using the ICP algorithm, and they are not considered as
similar, even though they have the same basket of products. Our
hypothesis is that more data will help in overcoming this issue.
Another difficulty encountered is that some logs that are similar do
not share the same basket of products. This is the case for the in the
example of Figure 4. The two logs have a high level of similarity
according to the ICP distance, but the first log has an empty basket of
products and the second one has a basket that contains two products
type 2.

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

Figure 4: 3D representations of two logs for which the ICP distance is small

5. CONCLUSION
In this paper, we used the ICP algorithm to compute the distance
between pairs of 3D log scans. By minimizing the distance between
two given logs, this method is able to determine to which log from a
training set an unseen log resembles the most although the 3D scans
might differ in the number of points.
The ICP associates a distance to the compared pairs, when this
distance is too large, we can understand that the compared couple
doesn’t have a high level of similarities. This intuition leads to the
evaluation of a simple predictor based on the nearest neighbor
algorithm.
Coupling the ICP with a machine learning method is one of the
perspectives to be considered for the amelioration of the prediction
process. As also discussed in the experiments section, we saw that
direct use of the logs’ 3D scans by an ICP-based predictor might
require specific normalization procedures.
REFERENCES
1

FPInnovations 2014. “Optitek 10”. User’s Manual.

2

Fix, E. and Hodges, J. (1951). Discriminatory Analysis.
Nonparametric
Discrimination: Consistency Properties.
Technical report, DTIC Document

3

Breiman, L., Friedman, J., Olshen, R. and Stone, C. (1996).
Classification and Regression Trees. Belmont, CA: Chapman and
Hall.

Workshop on Service Orientation in Holonic and Multi Agent
Manufacturing Control

4

Breiman, L. (2001). Random Forests. Machine Learning, 45 (1): 5–
32.

5

Morin, M., Paradis, F., Rolland, A., Wery, J., Gaudreault, J. and
Laviolette, F. (2015) Machine learning-based metamodels for
sawing simulation, Proceedings of the 2015 Winter Simulation
Conference, pp. 2160–2171.

6

NLGA Standard Grading Rules For Canadian Lumber (2014
edition)

7

Paul J and Neil D. McKay. A Method for Registration of 3-D Shapes.
IEEE Transactions on Pattern Analysis and Machine Intelligence
(PAMI), 14(2), pp. 239– 256, 1992.

8

Chen, Y. and Medioni, G. (1992). Object modelling by registration
of multiple range images. Image and Vision Computing, 10(3),
pp.145-155.

9

Bakir, G., Hofmann, T., Scholkopf, Smola, A., Taskar, B. and S. V. N.
(2007). Vishwanathan: Predicting Structured Data. MIT press.

10 Besl, P. and McKay, N. (1992). A method for registration of 3-D
shapes. IEEE Transactions on Pattern Analysis and Machine
Intelligence, 14(2), pp.239-256.
11 Blais, G. and Levine, M. (1995). Registering multiview range data
to create 3D computer objects. IEEE Transactions on Pattern
Analysis and Machine Intelligence, 17(8), pp.820-824.

