2007 IEEE International Conference on
Robotics and Automation
Roma, Italy, 10-14 April 2007

FrA2.4955-fps Real-time Shape Measurement of a Moving/Deforming Object
using High-speed Vision for Numerous-point Analysis
Yoshihiro WATANABE, Takashi KOMURO and Masatoshi ISHIKAWA¡-thisGraduate School of Information Science and Technology, University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan.
E-mail: Yoshihiro Watanabe@ipc.i.u-tokyo.ac.jp
Abstract— This paper describes real-time shape measurement
using a newly developed high-speed vision system. Our proposed measurement system can observe a moving/deforming
object at high frame rate and can acquire data in real-time. Thisis realized by using two-dimensional pattern projection and ahigh-speed vision system with a massively parallel co-processor
for numerous-point analysis. We detail our proposed shapemeasurement system and present some results of evaluation
experiments. The experimental results show the advantages ofour system compared with conventional approaches.

I. INTRODUCTION
There has been an increasing need for shape measurement
techniques in a wide range of application fields. In particularly, approaches using vision are useful because of theircontactless nature and flexibility. On the other hand, there
are demands for improved performance such as accuracy,
measurement range, time, cost and so on, and many kindsof systems have been developed to meet these demands [1].
In this paper, we focus on the improvement of the measurement time and realize high-speed time-sequential shapemeasurement. This type of measurement will have a great
impact on a wide variety of applications, such as control
tasks for robotics; surgery support, for example, observationof a beating heart; rapid visual inspection of products; vehicle
application, for example, checking road surfaces; and humanmachine interaction with high accuracy and flexibility.
On the other hand, in such application fields, we need toobserve a high-speed moving rigid-body and a deforming
or vibrating non-rigid body. Conventional shape measurement, however, is mainly performed in situations where
the relationships between the objects being measured andobservation devices are completely known by ensuring stableor controllable conditions. Also, the performance of conventional systems in terms of throughput and latency isusually not good enough for real-time control applications;for example, throughput on the order of a thousand frames
per second and latency on the order of milliseconds isgenerally required for robotic control.
Based on these backgrounds, the feasible system is considered to have three requirements: (A) the ability to observea moving object, (B) continuous observation at high frame
rate, and (C) real-time acquisition of shape information. To
realize these requirements, our proposed system employs anapproach in which multiple spots in a single image of ashape are acquired using high-speed vision for numerouspoint analysis. As a result, the constructed system achieved
955-fps measurement of shape information with 4.5 ms

1-4244-0602-1/07/$20.00 ©2007 IEEE.

latency. This paper details the system architecture and the
proposed operations, and demonstrates its advantages withsome experimental results.
II. C ONCEPT AND S TRATEGY
Our system has the following three functions: twodimensional pattern projector, high-frame-rate imaging, andhigh-speed image processing system. This section shows thatthe integration of those functions newly realizes effective
measurement for a moving/deforming object.
There have been various methods for vision-based shapemeasurement, such as the time of flight method, active triangular method, moire fringes, interferometry, and so on[1].
Among those, the active triangular method, which basicallyuses a single slit light, achieves sufficient accuracy on theorder of millimeters with a simple setup. Therefore, mostapplications requiring three-dimensional information employ
this approach.
However, this method involving laser scanning needs
typically tens to hundreds of frames to construct a single
range map, the exact number being proportional to theresolution and inversely proportional to the throughput. With
this method, it is necessary to assume that the measured
object remains stationary until measurement is completed,which causes a critical problem if the object moves between
frames. In order to avoid this problem, this method requires
extremely high-frame-rate imaging, which is not feasible
in terms of application development because it involves areduction in image quality and great increase in projected
light intensity.
object motion/s

proposed area

Pattern-projection method
1,000 fps

30 fpsScannning method
1,000 fps
30 fps
10

100

1,000

range maps/s

Fig. 1.

Performance comparison of shape measurement approaches.

Compared with this, there is another method using twodimensional pattern projection acquiring shape information
in a single frame by projecting a pattern to whole measured space. This can be a useful solution to avoid this3192

FrA2.4
motion constraints and realize high-throughput and lowlatency shape measurement of deforming or moving objects.
Fig. 1 illustrates the comparison between a scanning method
and a pattern projection method with its performance about
throughput and motional allowability. This figure also shows
our target field, where shape information feedback rate is 1
kHz. In this field, the advantages of the pattern projection
method are considered to work quite effectively. Although it
cannot keep constant resolution about space in wide range,
the following two reasons keep its usefulness. First, there arevarious applications even in case that the range is limited.
Second, it can be solved by changing the projected pattern
dynamically, which has a high feasibility.
However, in order to achieve high resolution about both ofspace and time, the method based on the pattern projection
requires to observe high-speed changes in the fine pattern.
Therefore, the high-frame-rate imaging, that is the second
function mentioned above, is an essential component.
In addition, this method requires quite high amount ofprocessing. For the performance about high throughput andlow latency, the processing speed needs to be dramatically
improved. The high-speed image processing system, thatis the third function, plays an important role about thisrequirement. Especially, in the proposed system, the second
and third function is provided by our newly developed highspeed vision system.
III. R EAL - TIME S HAPE M EASUREMENT USING
H IGH - SPEED V ISION FOR N UMEROUS - POINT A NALYSISThis section describes the whole structure of our systemand the essential components including the measurement
principle and high-speed vision for numerous-point analysis.
A. Whole System
Shape Infomation
Measured
Objects

High-Speed
Processing

Multi-spot
Image
Pattern Projector
Plane

VisionProcessor

High-Speed Imaging

Fig. 2. Shape measurement using high-speed vision for numerous-point
analysis.

Fig. 2 shows the basic concept of our system. As themeasurement method, we use a multi-spot projection method
in which numerous pre-calibrated spots are projected into themeasurement space using a laser. In the remainder of thispaper, the number of frames per second (fps) is the same as
the rate used for acquiring a range map because the shapeinformation is obtained in a single frame.

In the related method, other patterns may be used, suchas multiple slits or a grid. Also, it is possible to use color
patterns by using an LCD projector[2]. There are two reasonsfor using a focused multi-spot pattern from a laser: to achieve
high accuracy in each spot to avoid intensity noise, andto simplify the image processing for improving the speed,
resulting in high-frame-rate imaging and high-throughput,
low-latency visual feedback, respectively. This multi-spot
method has also been used to develop a compact range sensor
for a robot[3]. However, it has been difficult for this method
to be used in real-time shape measurement at 1 kHz.
B. Measurement Principle
The principle of this method is shown in Fig. 2. Each measured spot lies on the intersection of two lines, a projection
line and a vision constraining line. Therefore, if geometric
information about the projected line is known, the threedimensional point Mi = [xw , yw , zw ]t can be obtained fromthe image point mi = [Xv , Yv ]t . The suffix i shows the spot
number. The expression for the projection line is:M i = c + δsi(i = 1, . . . , Np ).

(1)

This is a line with gradient si passing through the projector
center c and on which the measured spot i lies. Here, Np is
the total number of projected spots.
The expression for the vision constraining line is:
P M̃ i = ω m̃i .
(2)This expresses the relationship between the image pointm̃i = [mti , 1]t of spot i and a three-dimensional point M̃ iconnected by perspective projection matrix P .
When applying this measurement, c, si , and P are
known parameters, and m̃i is the observed data. The threedimensional point M i is obtained from the above two
equations form the observed image points.
C. High-speed Vision for Numerous-point Analysis
The method using multi-spot pattern involves extraction of
position information of the numerous spots from an image,which requires long processing time. This bottleneck causes
a drop in the frame rate in real-time operation. Therefore,
to avoid this bottleneck, we introduce a newly developed
high-speed vision for numerous-point analysis.
There have been some studies using real-time vision athigh frame rates such as Column Parallel Vision (CPV)[4]and CMOS+FPGA vision[5] in manipulation tasks[6] andmicroscopic applications[7]. CPV has a general-purpose,
massively parallel SIMD processor. However, the operated
processing has been very simple, for example, just calculating the centroid of a single target because its processor
architecture limits the types of image processing. Also thosevision systems connected a processing unit to a camera
directly. This is considered to yield disadvantages in termsof scalability of system functions about module exchanging
and coordination with other heterogeneous processors.
Our newly developed system enables high-speed image
processing requiring a large amount of calculations by installing a massively parallel and dedicated vision processing

3193

FrA2.4
CPU

Calibration

Main Memory

Initialization

Host Bus
Host-PCI Bridge
size
centroidorientation
shape, etc

moment

CTRL

IF
image

Tracking
1-frameloop

Exchangeable Unit

RAM image in

Initilization
Frame

Massively Parallel Numerous-point
Co-processor
Analysis module

masking shield

NormalFramedata out

projecting one line
at a time
Pattern
Projector

New Point Mapping

FPGA Board

Fig. 4.

Capture Board
High-frame-rate Camera
Other Module Board(Secondary FPGA Board, Output Board, etc.)

The proposed flow of operations from extracting the image
point si to obtaining the three-dimensional point Mi isshown in Fig. 4. Each operation is detailed below.

PCI Bus
High-speed vision system with an massively parallel processor.

unit as a co-processor in a PC. Its configuration diagram isshown in Fig. 3. The co-processor also is exchanged according to applications. The ability to swap the co-processor andthe bus expansion of the co-processor and other devices allow
reconfigurability of the system and ensures high performancein various applications. Based on this configuration, weconstruct high-speed vision for numerous-point analysis byproviding effective modules to co-processor. In the remainderof this section, the details of each component are described.
We mounted the co-processor on a large-scale FPGA
board (KAC02-A, made by Mitsubishi Electric Engineering
Company). This board had two FPGA (XILINX XC2V6000)
for implementing co-processor cores. Also, we used a highframe rate camera (DALSA CA-D6) with a resolution of
256 × 256. The 8-bit gray-scale images were captured andtransferred in real-time at 955 fps. New sensors that arecapable of high-frame-rate image transfer could be developed
based on parallel A-D conversion technology[8]. The host PC
was a Dell Precision 670 with an Intel Xeon 2.80-GHz main
CPU. The co-processor communicated with the host via a
64 bit/66 MHz PCI bus.
In this paper, the co-processor calculated image moments
as spot information. The image moments are parameters thatcan be converted to various geometric features, such as size,
centroid, orientation, rough shape information, and so on [9].
The (i + j)th image moments mij are calculated from:
mij =


x

xi y j I(x, y),Operation flow.

IV. O PERATION FOR SHAPE MEASUREMENT BASED ON
NUMEROUS - POINT ANALYSIS

Additional PCI Device

Fig. 3.

measured objects

Processing for New Points(3)ywhere I(x, y) is the value at pixel (x, y). Normally,
when image moments of multiple objects are calculated in
an N × N image, the amount of calculations following
moment calculation and region division is proportional to thenumber of objects n and O(N 2 ). In contrast, by providing a
massively
parallel architecture, our processor requires only√O( n)[10]. This allows observation of a few thousand
objects at frame rates on the order of thousands of frames
per second.

A. Calibration
First of all, the geometrical relationship between the camera and each projected spot must be determined in advance.
We call this operation calibration. As an example of a simple
method, the calibration can be achieved by determining threefunctions [xw , yw , zw ]t = [f1i (zw ), f2i (zw ), f3i (Xv )]t fromknown pairs of three-dimensional points M i and image
points mi of each projected spot i without obtaining intrinsic
parameters c, si , and P .
The functions f1i and f2i determine the xw and yw coordinates of the three-dimensional point for spot i from thedepth distance, that is the zw coordinate. The relationships
are expressed as linear function:
(i)

(i)

fji (zw ) = αj,1 zw + αj,0(j = 1, 2)(4)

The function f3i determines the depth distance zw fromthe Xv coordinate of an image point. Strictly speaking,this function is expressed as a hyperbola about Xv and Yv .
However, over a small range, this function can be accurately
approximated by a polynomial expression as below:n(i)f3i (Xv ) =α3,k Xvk(5)
k=1

In the actual experiment, we used a two-dimensional polynomial approximation. Also those functions were determinedby obtaining multiple spot patterns to xw yw planes at the
known different distance zw .
B. Initialization
The processing system needs to know which image point
corresponds to each projected spot. Our method uses theinformation of the previous frame at the high-frame-rate
imaging and achieves the matching between them. This
tracking-based method can easily make the dynamic modification of the search area according to pattern changes. On
the other hand, at beginning of the measurement, it requires
another operation. We call this operation initialization.
In the applications focusing on moving objects, imaging
all unknown spots at one time and stopping the motion of themeasured object have the drawback of feasibility although
they easily solve the problem. We therefore control the start
time t(i) of projecting about each spot i as follows:

3194

FrA2.4
timet(i) = Tδ(i ∈ Aδ : δ = 1, . . . , Ne )(6)

Here, Aδ is a class of projected spots, whose epipolarlines li (Yv = li (Xv )) constraining movement of spot i inimage space don’t intercross. Ne is the number of divided
classes. Fig. 4 shows the case under the condition that the
points at the same line are regarded as the same class.
This enables ambiguity in the correspondence to be avoided,
which ensures high versatility. Moreover, since this spot
pattern is already projected when commencing sequential
frame operation, as detailed in IV-C, there is no loss of shapeinformation after beginning the measurement.
C. Sequential frame operation
This section describes the operation in normal frames.
After initialization, shape information is measured only in
input frames. When the frame rate is relatively high compared to changes in the measured phenomena, it can beassumed that the difference between spots projected on asmooth surface between successive frames is small. Using
this assumption, the operation for corresponding an image
point to a spot i could be expressed as a tracking operation
between frames, in which a point mi (t−1) corresponding toa point m(t) is searched for using corrected points at timet − 1 based on the evaluation min{|mi (t − 1) − m(t)| +Mi (t − 1) − M̃ (t)}.
Such searching of neighbour points in two-dimensional
image space can be performed using the bucket method,which can efficiently perform the search operation of thenearest point to an input point by dividing the search space
into grids and accessing only neighbour areas, instead ofaccessing all points. This makes the number of calculations
required linear with respect to the number of measured image
points to be corresponded, so long as the set of points is
distributed equally, which results in an equal number ofpoints included within each grid. We call this operation the
tracking in Fig. 4.
On the other hand, there are points that move discontinuously because they are on points of contact between
the measured object and the projected line of the spot.
These points are mapped exceptionally by using the epipolar line. This search operation is based on the evaluationmin{|Yv (t) − li (Xv (t))|}.
The relative number of these discontinuously moving
points can be assumed to be small, and this operation does
not cause a crucial problem in terms of processing time. We
call this operation the new point mapping operation in Fig.
4. It is necessary, however, to define constraints for the speed
at which these points jump in the depth direction between
frames in order to avoid the overlapping of spots in image
space.
D. Performance of Real-time shape measurement
This section describes the performance about measurement
speed using the proposed system and operations. The timing
chart is shown in Fig. 5. First, images were captured (Ex) andstored in main memory through the capture board (R1/R2).

Numerous Object Analysis(1,024 Objects:40MHz)

latency: 4.5[ms]image transfer

data transfer
Ex R1 R2 Im Sh Pre-Processing
I1 I2 D1 D2Frame-2
Ex R1 R2 Im Sh
P1 P2
Frame-3
Ex R1 R2 Im
Frame-1

1[ms](throuput: 955 fps)
Ex: exposure phase (1[ms])Im: Image Processing (1[ms])Fig. 5.

80[us]

540[us]R1/2: image readout (1[ms])Sh: Shape Calculation (0.5[ms])Timing in system operation.

Next, the image was converted to a binary image on themain CPU (Pre-Processing) and transferred to the two coprocessors (I1/I2). Each co-processor received 256 × 128
image and extracted image moments of numerous spots(P1/P2) and stored the data in the host (D1/D2). Finally,
the main CPU calculated shape information (Sh) based on
the method described in IV.
The co-processor was operated at 40 MHz and extracted
0th and 1st order image moments of 1,024 spots from animage. Also, the number of regions and the order of image
moments can be changed.
Each stage was pipelined and operated at 955 fps. Thismeans that our system could achieve measurement witha throughput of 955 fps and a latency of 4.5 ms. It isconsidered enough for most applications. However, this is
not the performance limit of the system because there is
still room for improvement in the processing time of the coprocessor and the total latency. Also we can include simple
operations for improvement of the image quality such as
sharpening at pre-processing on the CPU.
V. E VALUATION E XPERIMENT
A. Experimental Setup

measured area
cameraprojector
Fig. 6.

Experimental setup.

This section describes the experimental setup. Fig. 6 showsa photograph of the system. As the laser projector for themulti-spot pattern, we used SNF-533X (33 × 33 dots, line
pitch 0.45 deg) made by Moritex.
The measurement results for planes are shown in Fig.
7. The xw yw plane is defined as a plane perpendicular tothe base. Fig. 7(a) shows the three-dimensional points ofeach measured spot at distances of zw =−60, 0, 40 mm. The
measured area in this experimental setup is also shown in
the figure. The distance between the image plane and thecenter of the measured area was about 40 cm. This setup

3195

FrA2.4

110

110

20
0
−20
−40

60

Z [mm]

40
20
100

0

-20

50

-40
-60

140
140

-50

50
0

100

-100

50

50

0
−50

50
0

−50

(a) 0 ms

0

0
−50

−50

(b) 20 ms

-50

0

50
X [mm]
100 -100(a) Measured Result

Y [mm]
20
0
−20
−40

60
40
measured distance [mm]

20
0
−20
−40

20
0
−20
−40
50

20

50
0
−50

0

50

0

50
0

−50

0
−50

(c) 40 ms−50(d) 60 ms

−20

20
0
−20
−40

−40
−60
−80
−80

−60

Fig. 7.

−40−20
0object distance [mm]

20

20
0
−20
−40

40

50

(b) Error Evaluation
Measurement results for planes.

50
0

0
−50

is an example and not the measurement limitation. Fig. 7(b)shows the average object distance, that is, zw coordinate,
at each plane, together with maximum and minimum bars.
From this figure, it is clear that the calibration was performed
correctly with about the order of millimeter accuracy. Also,
the allowable difference of each spots in the space between
frames was defined as a maximum of 50 mm/ms in thisexperiment.

−50

50

50
0

0
−50

−50

(e) 80 ms(f) 100 ms
Fig. 9. Sequential measurement results of the waving flag.

correctly measured the motion of a non-rigid body in a highspeed fluid. These results suggest the possibility of using
this system in applications such as inspection of dynamic
deformations and control of complex vibrations.

B. Experimental Results
Here, we describe the measurement results for three different types of object: a waving flag, a flying ball, and moving
hand. The motion of these objects is usually fast and isdifficult to measure with conventional systems.
Fig. 10.

waving flag

fanFig. 8.

Waving flag.

1) Waving Flag: In this experiment, we used a piece ofcloth as a flag and fixed it at one side. The cloth was thenblown from the fixed side by a fan and to produce waves
like a flag blowing in the wind. A photograph of the waving
flag is shown in Fig. 8.
Fig. 9 shows time-sequential measurement results for thewaving flag. In this figure, the points show three-dimensional
points of the measured spots. The estimated surface isalso plotted. The measurement results show that the system

Photograph of measured ball.

2) Flying ball: The next measurement object was a moving rigid body, namely, a flying ball. In this measurement,
the background plane shown in Fig. 6 was set between thecamera and measurement space. Fig. 10 shows a photographof the measured egg-shaped ball.
The measurement results are shown in Fig. 11. The results
show that the shape of the ball was measured almost correctly
while it was moving.
One possible application of this time-sequential shape andmotion measurement is dynamic manipulation of a rigid
body, which plays an important role in robot tasks. To
develop such an application, however, the system will needto handle more complex shapes. This will be the subject of
future work.
3) Moving Hand: The third measurement object was amoving hand. In this experiment, an open hand came into
the measurement space between the camera and backgroundplane described above, and it was then closed. Fig. 12 shows

3196

FrA2.4

0
−20
−40
−60

50

50

0
−20
−40
−60

−50

50

50

0

0

20
−20
−60

−50

−50

(a) 0 ms

50

50
−50

50

−50

50
0
−50

50

−50

−50

−50

−50

50
−50

20
−20
−60
50

50

0

0

0

−50

−50

−50

(e) 40 ms(f) 50 ms
Fig. 11. Time-sequential results for flying ball.

−50

−50

(d) 60 ms

20
−20
−60
50

0

0

(c) 40 ms

0
−20
−40
−60
0

50

50

0

0

(d) 30 ms

50
0

20
−20
−60
50

0
−50

(c) 20 ms

0
−20
−40
−60

(b) 20 ms

20
−20
−60
0

−50

−50

(a) 0 ms

50

0

0

−50

−50

0
−20
−40
−60

0

50

50

0

0

−50

(b) 10 ms

0
−20
−40
−60
0

50

50

0

0

20
−20
−60

(e) 80 ms
Fig. 13.

50

50

0

0
−50

−50

(f) 100 ms

Time-sequential results for moving hand.

of spots, introducing dynamically changeable projector, integrating shape information between frames, and so forth. This
improvement should make the system even more feasible forthe applications mentioned above.
R EFERENCES

Fig. 12.

Photograph of the measured hand.

a photograph of the measured hand.
Fig. 13 shows the measurement results. We can see thatthe shape and motion of the hand was correctly measured.
These results suggest the possibility of using this system ina flexible, high-precision man-machine interface.
VI. C ONCLUSION
In this paper, we have described a time-sequential highframe-rate shape measurement system for moving and deforming objects. The system is based on multi-spot projection measurement in a single image using a high-speed
vision with a co-processor for numerous-point analysis. We
demonstrated a throughput of 955 fps and a latency of 4.5
ms. Experimental results for three kinds of objects showedthat the objects were measured correctly.
This type of measurement system is expected to find uses
particularly in feedback applications such as robotic manipulation, inspection, vibration suppression, human-machineinterfaces, and so on. We believe that our system is highly
promising for these kinds of applications. As a next step,in parallel with development of applications, we should
consider improving the accuracy by increasing the number[1] F. Chen, G. M. Brown, and M. Song, “Overview of three-dimensional
shape measurement using optical methods,” Journal of OpticalEngineering, vol. 39, no. 1, 2000.
[2] P. Fong and F. Buron, “High-resolution three dimensional sensing offast deforming objects,” in Proceedings of International Conferenceon Intelligent Robotics and Systems, 2005, pp. 1606–1611.
[3] K. Umeda, “A compact range image sensor suitable for robots,” inProceedings of International Conference on Robotics and Automation,
2004, pp. 3167–3172.
[4] Y. Nakabo, M. Ishikawa, H. Toyoda, and S. Mizuno, “1ms column
parallel vision system and its application of high speed target tracking,”
in Proceedings of 2000 IEEE International Conference on Robotics
and Automation, 2000, pp. 650–655.
[5] K. Shimizu and S. Hirai, “CMOS+FPGA vision system for visualfeedback of mechanical systems,” in Proceedings of 2006 IEEE
International Conference on Robotics and Automation, 2006, pp.
2060–2065.
[6] N. Furukawa, A. Namiki, T. Senoo, and M. Ishikawa, “Dynamic
regrasping using a high-speed multifingered hand and a high-speed
vision system,” in Proceedings of International Conference on
Robotics and Automation, 2006, pp. 181–187.
[7] N. Ogawa, H. Oku, K. Hashimoto, and M. Ishikawa, “Microrobotic
visual control of motile cells using high-speed tracking system,” IEEE
Transactions of Robotics, vol. 21, no. 4, 2005.
[8] S. Kleinfelder, S. Lim, X. Liu, and A. E. Gamal, “A 10000 frames/s
CMOS digital pixel sensor,” IEEE Journal of Solid-State Circuits, vol.
36, no. 12, pp. 2049–2058, 2001.
[9] R. J. Prokop and A. P. Reeves, “A survey of moment-based techniques
for unoccluded object representation and recognition,” GraphicalModels and Image Processing, vol. 54, no. 5, pp. 438–460, 1992.
[10] Y. Watanabe, T. Komuro, S. Kagami, and M. Ishikawa, “Parallel
extraction architecture for image moments of numerous objects,”
in Proceedings of IEEE 7th International Workshop on Computer
Architecture for Machine Perception (CAMP’05), 2005, pp. 105–110.

3197