The Journal of the Society for Art and Science, Vol. 15, No. 4, pp. 167 – 176 (2016)

A New Method of Refitting Mixture Lithic Materials by Geometric
Matching of Flake Surfaces
Xi Yang

Katsutsugu Matsuyama

Kouichi Konno

Graduate School of Engineering, Iwate University{yangxi} (at) lk.cis.iwate-u.ac.jp

Abstract
In Japan, lithic materials are very important evidences of human activity research in the Palaeolithic
and Jomon periods, while refitting lithic materials is a complex and hard task. In our previous
research, it is possible to refit lithic materials from a single stone core, while it is impossible torefit them from multiple stone cores. This paper proposes a new method for refitting mixture lithic
materials by matching flake surfaces. Each of the input point clouds of lithic materials is segmented
and simplified to obtain flake surfaces. Then, according to several refitting principles in archeology,
the lithic materials are matched starting from a stone core by searching the best matching flake
surface. The flake surfaces of matched lithic materials are reconstructed, and the matching process isrepeated until all data are matched. The implementation of the new method can obtain good refitting
results for experimental examples.
Keywords: Refitting, Lithic material, Matching, Flake surface.

1 Introduction
In archaeology, archaeological materials arevery important evidences of human activity
research[1]. With the data, archaeologists canstudy the time’s technical characteristics, sociocultural backgrounds, habits and other significant
subjects. The stone tools are regarded as cutting
tools or weapons made by striking or polishingrocks, and people in the Palaeolithic and Jomon
periods made a variety of tools. However, themost of excavated relics are just stone tools inJapan because the weather in Japan is almost hot
and humid and the ground soil is acidic. In thisenvironment, the most organics, such as bones orwoods, except stones are perished easily. Hence,lithic materials can be the main objects for tracing human activities in the ancient times[2].
To make a stone tool, the edge of a rock is
struck repeatedly with a pebble, and flake pieces
in various sizes are obtained as shown in Fig-ure 1 (a). These pieces are called lithic materials
and the flakes are the pieces peeled for adjusting the core shape. The core is the rock left asa raw material for a stone tool when flakes arepeeled[2]. Refitting and reassembling lithic materials is a very important work to finish the excavated relics. In addition, by refitting lithic materials, the manufacturing process of stone tools
can be restored and human activities in the ancient times can be conjectured. On the other
hand, by reassembling lithic materials, not only
the original form of relics but also specific human
lives in the ancient times can be known. Furthermore, the reassembled lithic materials have educational values as exhibition materials at history
museums[1].
However, it is extraordinarily diﬃcult to finish and analyze excavated relics[1] as shown in
Figure 1 (b). Although relics are measured bya scanner[3] and many problems can be solved– 167 –

The Journal of the Society for Art and Science, Vol. 15, No. 4, pp. 167 – 176 (2016)(a)(b)
Figure 1: a: Making of a stone tool;
b: An example of excavated lithic
materials.

by computer algorithms rapidly and accurately,
refitting lithic materials is still a complex andhard task and it may consume a lot of time andmanpower. In Japan, even the conjoining status of lithic materials has been analyzed since
1960[4], no superb solution algorithms have been
proposed yet for refitting lithic materials, especially for the mixture lithic materials with several
diﬀerent stone cores.
Therefore, in this paper, a new method is proposed for refitting mixture lithic materials bymatching flake surfaces. In addition, the imitations of lithic materials were examined to show
the new method could obtain good refitting results.

2 Related works
2.1 Previous works

method of adjacent flake surfaces for lithic materials. The paper[8] dose not detail the simplification status, while their simplification could not
obtain simplified results with the roughly same
simplified standard for mixture lithic materials.
Therefore, the matching method could not obtain good results with unified parameters for the
mixture lithic materials. In addition, this method
limited the search ranges of matching flake surface, while the search ranges are ambiguous fordiﬀerence groups of lithic materials. In their mixture experiment, their method can obtain 83%
correct results with top five flakes by D2, and
94% correct results with top ten.

2.2 Flake surfaces
Flake surfaces are fractures produced by peeling astone into flakes. For example, Figure 2 (a) shows
the flake surfaces of flakes A and B segmented
by blue boundary lines. Flakes A and B can bematched into one flake as shown in Figure 2 (b),because the two corresponding flake surfaces FA
and FB are produced at the same time. Therefore, flake surface matching is studied to solve
the refitting issue of lithic materials. However,the previous method[8] only can solve the problems of pairwise matching or refitting lithic materials from a single stone core. With improving
the previous methods, we improve the method[8]for refitting mixture lithic materials from multiple groups.

Numerous algorithms have already been published about matching of geometric objects.
Brown et al.[5] presented a system for matching
fresco fragments to reassemble Theran wall paintings. This method requires feature extraction of
surface curvature, whereas the flake surfaces oflithic materials are almost flat and smooth andthe features that can be extracted are very limited. Huang et al.[6] presented a system withgood performance for automatic reassembly of
broken 3D solids. It is an excellent reference, but
it is not entirely suitable for our research because
the refitting of lithic materials has some uniqueprinciples[7], whose details are described in Section 3.3.
Chida et al.[8] proposed a rapid searching– 168 –

(a)(b)

Figure 2: Matching by flake surfaces

The Journal of the Society for Art and Science, Vol. 15, No. 4, pp. 167 – 176 (2016)

3 New method
3.1 Algorithm overview
The input to our algorithm is a set of stone
tool point clouds measured by [3]. Based on thepipeline of the method[8], we improve their algorithm for mixture lithic materials. The algorithm
is executed in the following procedure:
1. Each point cloud is segmented for obtaining flake surfaces. Automatic segmentation
is applied in place of the semi-automatic
method.
2. Each flake surface is simplified to reduce
the number of point cloud. New simplification is employed based on point clouds thatcan control simplified flake surfaces via thesame evaluation with the matching method.
The input flake surfaces are improved by the
new segmentation and simplification, anda premise is provided for refitting mixture
lithic materials with the same threshold parameter.
3. From each flake surface of stone cores, thematching algorithm is used to search the best
matching surface and the transform matrix
is computed. For the mixture lithic materials, all flake surfaces instead of partial ones
are computed until find the best matchingsurface is found with the D2 order.
4. All flake surfaces belonging to one stone toolwith the matched surface are transformed by
the matrix.
5. The new flake surfaces of the matched stone
tools are reconstructed.
6. The matching process is repeated until allstone tools are matched.
Thus, point clouds of all lithic materials arerefitted by the transform matrices.

3.2 Segmentation and simplification of
flake surfaces
In our method, the algorithm of region growing
segmentation is applied to obtain flake surfaces.
The two parameters, angle threshold of normal
vector θ and curvature threshold c, are used to geta superb segmentation result. The greater valuesof θ and c lead to the smaller number of flake
surfaces. The gravel surfaces (that belong to theoriginal rock, not to a flake surface) and the flake
surfaces whose number of points is smaller than
1/20 of the original points are removed. They are
not put into flake surfaces that will be matched.
Matching of the original point clouds requires alarge amount of computing time due to the large
number of points, which makes the simplification
process necessary. The point cloud simplification
based on curvature[9] is employed to simplify theflake surfaces. Matching will fail if the featuresof adjacent flake surfaces are changed by simplification. While, in this method, the features
can be maintained by comparing with the original shapes. Parameter α of the distance thresholdis set to control the number of simplified points,
and the greater α leads to the smaller numberof simplified points. Furthermore, the successfulrate of mixture matching is raised because thesame evaluation as matching process is applied inthis simplification. In this paper, the algorithm offast triangulation[10] is applied to reconstructed
polygon meshes for simplified flake surfaces. The
polygon meshes will be used to evaluate simplification result and matching process.

3.3 Mixture matching
In our previous research[8], it was extremely difficult to control every flake surface in the same
simplified degree with other simplification algorithm, and this led to large simplified diﬀerencesamong the groups. Thus, matching method described in [8] cannot be applied for mixture lithic
materials. While the simplification method[9] inthis research can obtain simplification results inthe same evaluation value for all flake surfaces,
the minimal simplified errors are maintained between the original point clouds and the simplified ones by computing the same normalized distance as matching evaluation. Depending on favorable segmentation and simplification results,
lithic materials can be refitted with mixture materials of several groups at once.
Additionally, there are three properties tomake lithic material refitting diﬀerent from other– 169 –

The Journal of the Society for Art and Science, Vol. 15, No. 4, pp. 167 – 176 (2016)

fractured object reassembling, as shown in Figure 3. The first property is that there is a time
diﬀerence in generation of multiple flakes from asingle core[7]. In other words, lithic material refitting is not an operation to match two flakes arbitrarily. It must follow an order. Suppose flake
A is peeled first and then flake B is peeled, as
an example. In the viewpoint that the flakes arepeeled from a rock one by one and the rest is thestone core, the flakes should be matched with thestone core in reverse order. The second property
is that most of flake surfaces used for matching
are flat and smooth since the selected stone canbe divided sharply[2]. According to this property,
it is not suitable to use the general matching algorithm based on surface features. The third property is that one flake surface may be divided into
several pieces. For example, in order to match
flake A, flake B should be matched with the core
to get flake surface FC by combining flake surfaces
F1 and F2 . Thus, the matched flake surfaces must
be reconstructed to search the next surface.

pair. Figure 4 shows the result of D2 distribution
computation for four diﬀerent flake surfaces by aspot chart. The black, red, blue and green points
show the D2 shape distribution of meshed flake
surfaces 1, 2, 3 and 4 respectively. We can see
the shape of flake surface 1 is similar to 2, anddiﬀerent from 3 and 4. The diﬀerence between
flake surfaces 1 and 2 is significantly less thanthe diﬀerence between 1 and 3 or 4. Therefore,
the sorted matching order could improve the eﬃciency of our matching process.

1

2

3

4

Figure 4: D2 distribution on four flake surfaces.

Figure 3: A case of making a stone tool(flake A
is peeled first and flake B next).
In our method, the stone cores are specified
manually and the matching process begins on
flake surfaces of a stone core. As the data is
mixed with multiple stone cores in our research,
the stone cores are refitted in succession. Eachflake surface of a core is matched with each flake
surface of flakes to search the best matching flake
surface later. In order to reduce the number oftasks for matching, shape distribution D2[11] ofeach flake surface is computed, and the matchingorder is sorted by the Manhattan Distance of each

Figure 5: Computing
distance.

methodofnormalized

Normalized distance D[12] is applied for finding the best matching flake surfaces. It provides
a standard to measure the diﬀerence between two
flake surfaces on a unit area. Normalized distance
D of each pair is calculated as equations (1) and(2), and the best matching flake surface is judged– 170 –

The Journal of the Society for Art and Science, Vol. 15, No. 4, pp. 167 – 176 (2016)

by a value smaller than threshold parameter d.
Figure 5 shows the computing method of normalized distance. In the equations and Figure 5, Vi
is a point on flake surface A, Ti is the triangle on
flake surface B closest to Vi , ni is the normal
vector of Ti and gi is the geometric center of Ti .
Then distance di between Vi and Ti can be calculated by equation (1). D is computed by the sumof (di )2 , dividing mesh area S of flake surface B
like equation (2).
di = (Vi − gi ) · nin1∑D=(di )2
S

(1)
(2)

i=1

Our pairwise matching algorithm is proposedin the following steps and Figure 6:

3. Construct local coordinate systems Ssi and
Stj . For Ssi , set the direction of edge vector
Vsi to the x axis, that of normal vector Nsi to
the y axis, and that of Vsi ×Nsi to the z axis.
Then, match local coordinate system Ssi to
Stj and compute transform matrix Ma . In
addition, transform Fs with Ma to get Fs ′.
4. Search the nearest triangle in Ft for each triangle of Fs ′ by their barycenter. Calculate
the sum of distances between each barycenter pair dc . Select Fs ′ with the minimum
value of dc . Search the nearest triangle Ti
from Ft for each point Pi from Fs ′. Get point
Pi ′ by projecting Pi in Ti and construct point
set P ′.
5. Calculate fitting transform matrix Mb bymatching point set P of Fs ′ to P ′.
6. Finally, matching transform matrix M iscomputed by Ma × Mb .
Thus, the source flake could be matched withthe target flake by transform matrix M .

3.4 Flake surface reconstruction(a)

In order to reconstruct the original flake surface,
the divided flake surfaces should be detected andmade into one flake surface after matching two
flakes. Figure 7 shows the reconstruction of flake
surfaces Fa and Fb , where the two matched flake
surfaces are shown in darker gray. The flake surfaces are reconstructed in the following procedure:(b)
Figure 6: Matching algorithm.

1. Set a polygon mesh with the smaller area assource mesh Fs , and the one with the larger
area as target mesh Ft .
2. For meshes Fs and Ft , search their edge line
sets Es and Et and edge triangle sets Ts andTt . For each pair of Esi and Etj , obtain vectors Vsi and Vtj in counterclockwise direction
for normal vectors Nsi and Ntj of triangles
Tsi and Ttj .

Figure 7: Searching reconstruction flake surfaces.

1. For each pair of flake surface Fa and Fb of two
matched flake surfaces sets, search nearest– 171 –

The Journal of the Society for Art and Science, Vol. 15, No. 4, pp. 167 – 176 (2016)

point Pbj from Fb for each point Pai from
Fa . If the distance between Pai and Pbj isshorter than distance threshold dr , they are
put into the corresponding point pair set Pc .
2. For each point in Pc , search the triangles
that belong to the point. For point Pai on
Fa , triangle set Tai on Fa can be obtained.
Then, compute mean vector Vai from all normal vectors of the triangles in Tai .
3. Calculate the angle between each vector pair
Vai and Vbi . If both angles are smaller thanangle threshold θr , the flake surface pair Fa
and Fb should be reconstructed to one flake
surface.

for matching. From this figure, we can clearly seethat the flake surfaces of stone tool models aresegmented precisely and integrated.

N o.13 (θ = 1.5, c = 1.0)
Figure 9: Results of segmentation.

4 Results and limitation
4.1 Experimental results
We have implemented the new method using
C++ and PCL[13], and examined the method in
a PC with Intel Core i7-4790 CPU and 8.00GB
memory. The data of 43 lithic material imitations
were examined in our experiment, shown in Figure 8. N o.01 and N o.20 shown with black thickframes are the stone cores. The 43 data could
be refitted into two groups by our new matchingalgorithm in the order of N o.01 and N o.20.

Figure 10 shows the constructed meshes andfaces of three simplified flake surfaces of N o.13.
Distance threshold parameter α is set to 3.0. For
the three flake surfaces from left to right, thenumber of the original point clouds, the numberof the simplified point clouds, simplified rate, execution times and normalized distance are shownin the Table 1. The normalized distances showthat the simplified results are very close to theoriginal point clouds, and we can see that thecontour lines are almost identical. Thus, thesimplified flake surfaces can be used for matching very well. Furthermore, the simplified process can drastically reduce the computing time ofmatching.

Figure 8: 43 experiment data.
Figure 9 shows the segmentation results ofN o.13 by point clouds. The flake surfaces are displayed in diﬀerent colors. The red points do notbelong to any flake surfaces. There are about 833
thousand points, the execution times are about
95 seconds, and four flake surfaces are segmented(a) Mesh(b) Face

Figure 10: Results of Simplification.
Through the process of segmentation and simplification, the 43 data are divided into 169 flake– 172 –

The Journal of the Society for Art and Science, Vol. 15, No. 4, pp. 167 – 176 (2016)

Table 1: Results of Simplification.
Flake
Original number
Simplified number
Simplified rate
Execution time
Normalized distance

1
78119
591
0.76%
4.4s
0.090

2
167834
1095
0.65%
11.5s
0.066

3
86643
628
0.72%
5.8s
0.067

(a) Reconstructed flake surfaces of N o.8, N o.13
and N o.18.

surfaces for mixture matching algorithm. Figure 11 shows the result of pairwise matching of
two stone tools N o.1 and N o.7. Figure 12 showsa case of matching where some matched flake surfaces must be reconstructed into one flake surface
to match with the next one. Three flake surfacesof stone tools N o.8, N o.13 and N o.18 are reconstructed to match with N o.19.

(b) Target flake N o.19.

(c) Result of matching.
Figure 12: Result of reconstruction.

(a) N o.1(b) N o.7(c) Result of matching
Figure 11: Result of pairwise matching.
Tables 2 and 3 show the details of matchinggroups 1 and 2. In the tables, Number indicatesthe flake surfaces matched currently, where thedigits are the number of stone tools, and the alphabets are the number of flake surfaces produced
from the same stone tool. Order indicates thesorted order of flake surfaces for searching thebest matching flake surface by D2. Long execution time is required for calculating the fitting
transform matrix for each pair, and a large number of pairs need to be computed. For example,
the execution time is 1007.9 seconds for searching
the best matching flake surface 06A in the group
1. The average matching time is about 32.5 seconds for each pair, while 31 times of matching
are required. All flake surfaces are matched starting from the two stone cores N o.01 and N o.20.
The threshold parameter of normalized distanced is set to 0.06 to judge the best matching flake
surface. Finally, sixteen stone tools are matchedin group 1, and twelve are matched in group 2.
Flake E cannot be matched by our method, andthe details are described in Section 4.2. Figure 13
shows the results of the final matching for groups
1 and 2 and the pictures of imitations matchedby hands.

4.2 Limitation
Figure 14 shows an example where our method
cannot match. The two red circles show the corresponding points of matching. The two flake sur-– 173 –

The Journal of the Society for Art and Science, Vol. 15, No. 4, pp. 167 – 176 (2016)

Table 2: Matching of group 1.
Number
01A-12B
└ 06A
└ 10B
└ 07B
…
└ 04B
Total

Order
1/163
31/16045/156
1/152…
45/113

Normalized distance
0.0248339
0.0565872
0.0253672
0.0429291…
0.0148311
15846.5s

Time
121.0s1007.9s
1758.9s
88.6s…
140.3s(a) Matched flakes of two groups.

Table 3: Matching of group 2.
Number
21A-25D
└ 34A
└ 33A
└ 07E
…
└ 35D
Total

Order
30/99
3/94
7/91
7/86
…
4/59

Normalized distance
0.0348425
0.0071474
0.0219804
0.0580872…
0.0130739
4399.5sTime992.8s19.5s
47.6s
376.2s…
142.9sfaces overlap partially (shown by the gray diagonal lines), and the one with the larger area shownin the right cannot be completely cover the other.
Because of this, the minimum distance of the two
flake surfaces could not be computed correctly.
Our method results in an error for such flake surfaces. The incidence rate of such case depends onthe condition of lithic materials, and there is only
one in this experiment.

5 Conclusions and further work
In this paper, we proposed a new method for refitting mixture lithic materials by matching flake
surfaces. Several characteristics were designed in
our algorithm according to the principles of lithic
material refitting. The experiment results could
show that our new method could obtain precise
refitting results for mixture lithic materials. In
the further works, we will study more eﬃciency
matching algorithms. Moreover, we will study
the matching method for flakes that are matching each other on a extremely small part.

(b) Matched results by our new method.
Figure 13: Results of final matching and actual
pictures.

Acknowledgements
Part of this work was supported by JSPS KAKENHI Grant Number 15H02945. 3D data is provided by Tokyo National Museum and LANG,
Co., Ltd..

References[1] K. Suzuki, Koukogaku nyuumon (Archaeology Introduction), University of Tokyo
Press, Kyoto, JP, 1988.
[2] K. Matsufuji, S. Monta, Yoku wakaru
koukogaku (Understand archeology), Minerva Shobo, Kyoto, JP, pp.18-18, 2010.
[3] E. Altantsetseg, Y. Muraki, F. Chiba, K.
Konno, 3D Surface Reconstruction of Stone
Tools by Using Four-Directional Measurement Machine, International Journal of Virtual Reality, Vol. 0, No.1, pp.37-43, 2011.
[4] A. Igarashi, Analytical Reviews of Conjoinable Stone Artefacts from Palaeolithic Sites
in Japan, The historical science, Keio University, Vol.67, No.3, pp.465-488, 1998.

– 174 –

The Journal of the Society for Art and Science, Vol. 15, No. 4, pp. 167 – 176 (2016)

Figure 14: Limitation of our method.

[5] B. J Brown, C. Toler-Franklin, D. Nehab,
M. Burns, D. Dobkin, A. Vlachopoulos,
C. Doumas, S. Rusinkiewicz, T. Weyrich,
A system for high-volume acquisition andmatching of fresco fragments: Reassembling
Theran wall paintings, IACM Transactions
on Graphics (TOG), Vol.27, No.3, Article
84, pp.1-9, 2008.
[6] Q.-X. Huang, S. Flöry, Na. Gelfand, M.
Hofer, H. Pottmann, Reassembling fractured
objects by geometric matching, ACM Transactions on Graphics (TOG), Vol.25, No.3,
pp.569-578, 2006.
[7] A. Igarashi, Hakuhen hakuri genri: Seisei
no zengo kankei (Flakes peeling principle:
The context of generation), Sekki zukuri no
ziken koukogaku (Experimental archeology of
the Stone tool Making), Lithic Technology
Research Society, Gakuseisha, Tokyo, JP,
pp.22-35, 2004.
[8] A. Chida, K. Matsuyama, F. Chiba, K.
Konno, A rapid searching method of adjacent flake surface in stone implements by using sets of measured points for generating ajoining material, The Journal of the Society
for Art and Science, Vol.13, No.2, pp.107115, 2014.
[9] X. Yang, K. Matsuyama, K. Konno, Y.
Tokuyama, Feature-Preserving Simplification of Point Cloud by Using Clustering
Approach Based on Mean Curvature, The
Journal of the Society for Art and Science,
Vol.14, No.4, pp.117-128, 2015.

[10] Z. C. Marton, R. B. Rusu, M. Beetz, On
fast surface reconstruction methods for large
and noisy point clouds, Robotics and Automation, 2009. ICRA’09. IEEE International Conference on, pp.3218-3223, 2009.
[11] R. Osada, T. Funkhouser, B. Chazelle, D.
Dobkin, Matching 3D models with shape
distributions, Shape Modeling and Applications, SMI 2001 International Conferenceon., pp.154-166, 2001.
[12] K. Yamahara, K. Konno, F. Chiba, M.
Satoh, A Method of Detecting Adjacent
Flakes in Stone Tool Restoration by Extracting Peeling Surfaces, Japan Society for
Archaeological Information., Vol.17, No.1-2,
pp.23-31, 2011.
[13] Point Cloud Library (PCL), http: //pointclouds. org/ , 2015.

Xi Yang

Xi Yang is currently a Ph.D student in Faculty ofEngineering at Iwate University. He received the
BE degree in College of Information Engineeringfrom Northwest A&F University in 2012. He received the ME degree in Faculty of Engineering
at Iwate University. His research interests include
geometric modeling and computer graphics.
Katsutsugu Matsuyama

Katsutsugu Matsuyama is currently an assistantprofessor at Iwate University. His research interests include computer graphics, information visualization and interactive systems. He received– 175 –

The Journal of the Society for Art and Science, Vol. 15, No. 4, pp. 167 – 176 (2016)

BE, ME, DE degrees in computer science from
Iwate University in 1999, 2001 and 2005, respectively. He was a research associate at Future
University-Hakodate from 2005 to 2011.
Kouichi Konno

Kouichi Konno is a professor of Faculty of Engineering at Iwate University. He received a BS in
Information Science in 1985 from the Universityof Tsukuba. He earned his Dr.Eng. in precision machinery engineering from the Universityof Tokyo in 1996. He joined the solid modelingproject at RICOH from 1985 to 1999, and the
XVL project at Lattice Technology in 2000. He
worked on an associate professor of Faculty of Engineering at Iwate University from 2001 to 2009.
His research interests include virtual reality, geometric modeling, 3D measurement systems, andcomputer graphics. He is a member of IEEE.

– 176 –