Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
. i
CA 02375013 2002-03-11
a'~
i
ELECTROMAGNETIC PROFILE SCANNER
RELATED APPLICATION
This application is a divisional application of Canadian patent application
2,163,934 filed 28
November, 1995.
For convenience, this specification includes both the description of the
invention claimed
i o in the parent application 2,163,934 and the description of the inventions
claimed in this divisional
application.
BACKGROUND OF THE INVENTION
i5 This invention relates generally to a method and apparatus for the
measurement of the
dimensions of an object, and more particularly to a non-contact system to
generate measurement
data representative of planar sections of an object and contour maps of an
object (which data may
be used as an input to suitable process control apparatus), and to a spatially
coded pattern for use
with such system. The invention will be described primarily in connection with
using
2o electromagnetic radiation to obtain measurement data representing planar
sections (profiles) of the
external surtaces of logs so as to compute the three-dimensional surtace
profile of each individual
log for the purpose of adjusting sawing equipment in saw mills (for example,
to optimize the
quantity or value of the lumber produced). However, the invention is also
applicable to
measurement of other objects, particularly where rapid and accurate shape
determination is
25 necessary. Such measurements may be made both as to objects' external
surfaces and also as
to internal interfaces (e.g. imaging and measurement of internal organs for
medical purposes), the
latter when suitable penetrating radiation is reflected from such internal
interfaces and detectable
(as reflected) by a suitable receiver. Further, the invention, while described
as using
1
CA 02375013 2002-03-11
electromagnetic radiation, is applicable to measurements using other forms of
radiation, such as
sound or particles, so long as reflection occurs from either an external or
internal interface, and so
long as a pattern divisible into distinguishable pattern elements as herein
described may be applied
to such radiation and detected by a suitable receiver.
The simplest non-contact automatic method commonly used to determine the
shapes of
logs is known in the prior art as shadow scanning. The log moves past a row of
beams of light and
the cross-sectional width of the log is determined by measuring the shadow
cast by the log on an
array of sensors on the other side of the log, which sensors are lined up with
the projected light
1o beams. Beams of light must be applied from several directions and sensed by
a corresponding
set of sensor arrays to obtain even a rough profile, The shadow method cannot
measure or even
detect concave features such as hole in the log. It measures the outer
envelope of the profile of
the log.
i 5 Other methods known in the prior art for determining the shape of an
object without contact
depend on the principle of triangulation, which has been known historically
prior to the present
century. The application of this principle can be illustrated by considering a
single beam of light
transmitted in a known direction in space from a known location at an object
being measured.
Some suitably selected form of receiving system positioned so as to view the
object from a
2o direction different from the direction at which the light was transmitted
detects the direction from
the receiving system at which the reflection from the projected light spot
appears on the object
being measured. The distance between the transmitter and the receiver is known
and fixed.
Hence two angles (determined from the transmitting and receiving directions)
and one side of a
triangle (the distance between the transmitter and the receiver) are
determined, and thus the
25 location of the spot on the object relative to the measuring apparatus is
easily calculated.
To use triangulation to measure the shape of an object (rather than merely to
measure the
coordinates of a single point), many spots in a raster pattern or the like
would have to be
2
CA 02375013 2002-03-11
t
determined. This could be done by projecting a pattern of beams
simultaneously, by sweeping one
beam over the surface of the object in a suitable scanning pattern in a
continuous motion, or by
projecting a sequence of beams, one at a time, at different points on the
object being measured
(this technique is often referred to as "time multiplexing"). Simultaneous
projection, as taught by
s the prior art, is not able to reliably measure irregular surfaces because
identification of a particular
spot with a particular transmitted beam becomes uncertain or ambiguous if any
spots are obscured.
In some cases, the ambiguity or uncertainty could be overcome by the use of a
reference spot
whose coordinates are known, thereby enabling the operator to establish a
correspondence
between at least one transmitted beam and one detected spot. However,
ambiguity or uncertainty
1o would remain a problem for other spots in the pattern, even if the
reference spot were located
unambiguously, as identification of spots other than the reference spot
depends on the assumption
that no spots between the reference spot and the spots to be identified are
obscured. While beam
sweeping and time multiplexing do not entail the foregoing ambiguity problem,
both are subject to
the problem that the accurate instantaneous measurement of the profile of an
object such as a log
15 moving rapidly is difficult, by reason of the need for adequate computing
time required to determine
each profile. For example, in a typical saw mill, logs move at 500 feet per
minute, so that to obtain
profiles of, say, 1" apart (axially) on the log requires that each scan take
less than 10 milliseconds.
An alternative surface profile measurement apparatus taught in Leong, U.S.
Patent No.
20 4,937,445, granted on 26 June 1990, that is alleged to achieve unique
identification of detected
spots with transmitted beams, uses a small number of beams, so that within a
limited depth of
range, the spot from each beam will be observed within a limited region on the
imaging device.
However, this implies that increasing the number of beams to increase
resolution of surface
features decreases the range of depths that can be measured. Further, accurate
knowledge of the
2s direction of each beam in the Leong technique is critical, making frequent
calibration necessary.
An alternative taught in Corby, U.S. Patent No. 4,687,325, granted on 18
August 1987, is
to project onto the scanned object a time-separated series of different
complete-scan patterns of
3
CA 02375013 2002-03-11
beams so that identification of the pattern of spots on the scanned object can
be used to identify
beams uniquely with detected spots. Triangulation is used to obtain the
spatial coordinates of the
spots. Corby requires the sequential projection of a series of mutually
differing patterns of beams,
and so suffers from the same problem from which beam sweeping and time
multiplexing suffer,
namely the inability to determine the instantaneous profile of a rapidly
moving object. Furthermore,
complexity arises in Corby from the need to transmit a plurality of different
patterns in time
sequence.
For the foregoing reasons, it can be readily understood that the problem of
measuring at
1o a distance the surface profiles of irregular objects moving rapidly along a
production line (say) is
not solved satisfactorily by the known art. A satisfactory measuring apparatus
should:
(a) have either (i) the capability to make very fast (snapshot) measurements
of the
profile of the object so that as the object moves past the measuring
apparatus, the surface contour
i5 of the entire object can be built up as a series of profiles; or (ii) the
capability to make a
measurement of the entire surface contour of the object at one time;
(b) have the ability to cope with failure to receive portions of the
transmitted pattern (due
to irregularity of surface features of the object or to the occlusion of
portions of the object by
2o intervening spurious objects);
(c) be compact, rugged, with a minimum of moving parts;
(d) not require frequent calibration; and
(e) have sufficient resolution and depth of field to measure accurately
irregular objects
such as logs.
4
CA 02375013 2002-03-11
The prior art teaches that a multiplicity of discrete beams (a pattern)
projected
simultaneously onto the object to be measured from different angles is needed
to satisfy the
requirements set out above for the rapid measurement of the complete surface
profile of the object.
However, the beam patterns taught in the prior art are not satisfactory as
they do not enable
reliable measurements to be made in situations that can occur in a sawmill and
in other scanning
situations, namely that the received signal may not represent the entirety of
the transmitted
scanning beam. There are various reasons why this may happen. The log may be
smaller than
the transmitted scanning beam. Irregularities on the surface of the object
being scanned (e.g.,
bumps on the log) may occlude a portion of the log's surtace such that the
scanning beam does
1o not reach the surface in question, or the bump may occlude the light
reflected from the portion in
question. Further, a log is carried by a conveyor, and sometimes the scan
intersects a portion of
the conveyor instead of the log, the log's surface being occluded by such
conveyor portion.
Consequently, the reflected light signal may be unreliable; portions of it may
have to be rejected.
Furthermore, if only a portion of the total scanned beam is received reliably
by the detector, it may
i 5 not readily be possible (within the teaching of the prior art) to
correlate the received portion with any
particular part of the log or other object being scanned. If the received
signal cannot reliably be
correlated with a particular portion of the object being scanned, then the
received signal may be
useless to the purpose at hand.
SUMMARY OF THE INVENTION
The present invention, like some other prior inventions, makes use of the
concept of
structured light or other radiation. According to this concept, a detector is
able to identify the point
of change from, for example, transparency to opacity, from brightness to
darkness, from one color
(wavelength) to another, or from one polarization to another, in accordance
with the nature of the
detector. If brightness to darkness is used, a suitable structured light
pattern is projected onto the
object to be measured so that these light-to-dark and dark-to-light transition
points may be
5
CA 02375013 2002-03-11
identified. According to the present invention, the pattern of structured
light (or other radiation) is
coded such that discretely and uniquely identifiable sub-patterns exist that
can be correlated with
corresponding portions of the transmitted pattern, and thus with corresponding
portions of the
object being scanned. This requires that the beam of light, or other radiation
that is projected onto
s the object being scanned, be patterned and coded in such a manner that sub-
patterns (subsets of
the pattern) above some predetermined size can be uniquely identified and
associated with a
specific portion of the scanning beam, and thus with the object being scanned.
In one aspect, the invention provides a projector for projecting a pre-
determined coded
~ o pattern of radiation onto a scanned object. For iog scanning applications,
the radiation is preferably
light. Light or other chosen radiation reflected from the scanned object is
detected and processed
by a detector in the nature of an imaging device parse known in the
technology, so as to generate
a useful output signal representing the reflected radiation. Preferably the
analog signal thus
obtained is converted to a digital signal for further processing. The
principle of triangulation is used
15 to obtain the coordinates of points on the object being scanned relative to
the projector or detector.
The resulting data can be further analyzed and processed according to known
techniques to obtain
a useful technical or industrial result. For example, profile information
concerning the shape and
dimensions of a log may be used to control a saw and edgers in a sawmill to
cut the maximum
number of boards of predetermined cross-sectional dimensions from the log,
boards with the
2o maximum value, or boards with dimensions specialty ordered by a customer.
Because scanning and detection apparatus according to the invention makes use
of the
well-known principle of triangulation to obtain reliable distance information
relative to the object
being scanned, and because apparatus according to the invention makes use in
part of a
25 combination of devices that are per se known in the technology, such
devices will accordingly not
be described in detail in this specification.
Apparatus constructed in accordance with the invention need not include any
mechanical
6
CA 02375013 2002-03-11
moving parts for projecting the scanning beams or for receiving and detecting
the reflected signal.
The inventive apparatus reliably correlates the received signal corresponding
to only a portion of
the projected scanning beam (such portion being greater in size than some
predetermined
minimum that depends upon the characteristics of the projected beam in
conjunction with a
s preselected spatially coded pattern, as will be described further below)
with a counterpart portion
of the projected beam, so that useful profile information is obtained about
the object being
scanned, even though such information may relate to only part of the scanned
object. If enough
useful information is obtained on a partial scan basis over a sufficient
scanning area, then there
may be enough information obtained in total by combining the useful
information for any given scan
i o with the useful information obtained from other scans that the entirety of
the profile of the scanned
object may be reliably ascertained.
The predetermined coded pattern used in apparatus according to the invention
is selected
so that for any given scan, the smallest useful portion of the projected
scanning beam is
i s characterized by an array of discernible pattern elements that enable any
one such smallest useful
portion to be distinguished from any other smallest useful portion.
Accordingly, if only a relatively
small portion of the reflected signal is useful, then if that signal is
characterized by an array of
pattern elements that correspond uniquely to an array of pattern elements of a
portion of the
projected signal at least as large as the smallest useful portion thereof, it
follows that the reflected
2o signal data can also be correlated uniquely with an identifiable discrete
portion of the scanned
object.
The significant advantage of the invention is thus that if the reflected
signal detected by the
detector corresponds to only a portion of the projected scanning beam (or
matrix), then that
2s reflection signal information can nevertheless be processed to obtain
reliable profile information
about an identifiable portion of the object being scanned. This is possible
according to the
invention because of the use of a suitable coded pattern having uniquely
identifiable divisions. The
projected beam strikes or scans the object with the pattern characteristics
superimposed, and
7
CA 02375013 2002-03-11
consequently the pattern as projected onto and reflected from the scanned
object will also be
capable of recognition in the reflected signal. The character of the pattern
will vary depending upon
whether a one-dimensional scan (obtaining profile information in two
dimensions along the
intersection of a plane with the surface of the object scanned) or a scanning
matrix in two
dimensions (obtaining three dimensional profile information of the object
scanned) is used, and
depending upon a number of other parameters to be given due consideration by
the system
designer, including the resolution of the projected pattern on the surface of
the scanned object, the
overall size of the object being scanned, the resolution capability of the
detector, an assessment
of the smallest portion of the scanned object about which any profile
information will be considered
io useful, the general expected shape of the object being scanned, and the
industrial or technical
purpose to which the profile information is to be put.
If a given scan yields two or more subgroups of received pattern data that are
correlatable with two or more identifiable portions of the scanned object,
then the spatial
i s coordinates of those two or more identifiable portions may be determined.
To give two examples that illustrate the distinctions between two different
possible
applications of the present invention, consider the scan of a log in a sawmill
on the one hand, as
against the scan of a small fossil or artifact by an archaeologist, on the
other hand. In the one
2o case, the sawmill operator wishes to obtain the largest possible number of
board feet of lumber of
certain cross-sectional dimensions (say), and in the other instance, the
archaeologist wants to
obtain a non-contact surface profile of the fossil (say) so as to be able to
reproduce it exactly for
study purposes, without damaging the original. It is immediately evident that
the parameters and
factors to be considered, including those mentioned in the preceding
paragraph, will be different
2s from one another in these two different possible applications of the
invention. Of course, in each
case, other factors unrelated to the present invention may enter into the
decision making - for
example, the final decision as to the cutting of a log may depend upon an
assessment of where
the knots are as well as upon the exterior profile of the log, but that
consideration in the decision-
8
CA 02375013 2002-03-11
making process is entirely irrelevant to the present invention, which is
concerned with profile
characteristics only. (of course, given satisfactory resolution, the profiler
of the present invention
can help to identify the probable surface location of knots on the log.)
In a simple one-dimensional scanning beam yielding two-dimensional profile
information
along the intersection of a plane with the surface of the object being
scanned, the scanning pattern
may resemble, for example, a bar code of the sort applied to goods in a
grocery for price
identification. Just as the varying light and dark patterns in a bar code
represent uniquely
determinable numeric information as one proceeds from one end of the bar code
pattern to the
io other, so a structured light pattern according to the invention corresponds
to uniquely identifiable
subsets of useful spatial information. Each subset of detected reflected
radiation corresponds to
a uniquely and discretely identifiable portion of the projected scanning beam,
and thus to a uniquely
and discretely identifiable portion of the object being scanned.
If the scanning beam is projected not as a linear one-dimensional scanning
beam yielding
two-dimensional contour line information about the object being scanned, but
instead is projected
as a two-dimensional matrix (the matrix could be, for example, Cartesian or
polar in character),
then the pattern of light-to-dark transitions (say) may be rather more
elaborate than a simple bar
code, and may conform to a wide variety of two-dimensional configurations. For
example, a
2o possible two-dimensional pattern might comprise selected letters of the
alphabet distributed over
a plane. The character, number, and relative sizes of the elements in the
pattern will depend in
part upon the factors previously mentioned, e.g., the expected general
character of the profile of
the object being scanned, its expected size, the resolution of the pattern as
projected on the object,
the resolution of the detector, the industrial or technical application of the
distance data obtained,
2s etc.
An example of the use of the invention to determine the coordinates of the
intersection of
a plane with the surface of an object, i.e., the contour line of the object in
that plane, will be
9
CA 02375013 2002-03-11
discussed first. Such plane will include the projected beam of structured
light (say) having a
suitable coded pattern. The use of the invention according to this example to
determine the
coordinates of the entire surface of a three dimensional object is a
straightforward extension,
involving projection and detection of a spatially separated sequence of beams
over the length of
s the object, thereby generating a corresponding series of contour line
profiles.
To determine a contour line of the object being scanned, the projector of the
invention
projects a spatially coded pattern of light (say) in a narrow strip across the
object. For example,
one possible such pattern is a series of light and dark bands (created by
alternating transparent
1o and opaque regions of a strip of material through which the transmitted
beam is to be projected)
running generally perpendicular to the direction of projection of the narrow
strip and in which the
dark-to-light (opaque-to-transparent) transitions are regularly spaced while
the light-to-dark
(transparent-to-opaque) transitions (say) are irregularly spaced according to
a predetermined
pattern, thereby generating discretely identifiable subsets of the pattern.
(Either set of transitions
could be regularly spaced, so as to identify the boundaries of the pattern
elements, whilst the other
set is spaced in accordance with the coding applied to the pattern.)
The reflection of the pattern is detected and compared to the projected
pattern to determine
a one-to-one correspondence between the features of the projected pattern and
the reflected
2o pattern. To this end, analysis of subsets of pattern elements of the
received pattern data, such
subsets selected to be above a certain size in the linear dimension along the
strip, affords a means
for discriminating between such subsets. This analysis is possible even if
only a portion of the
projected pattern (above some predetermined minimum size) is received, because
the subsets of
the pattern as received can be discriminated from one another, leading to a
reliable identification
25 of the corresponding portion of the object being illuminated.
One way to obtain the correspondence between a subset of the reflection signal
data and
the projected pattern is perform a suitable fitting routine on the data. A
convolution routine
CA 02375013 2002-03-11
revealing a fit for a given maximum sum result could be used, but the
inventors have found that the
use of a "least squares" fitting procedure provides satisfactory results. Once
this fitting step is
done, the coordinates of a point on the surface of the object at which a
particular feature of the
pattern is seen are determined (using ordinary principles of triangulation)
from the distance
between the projecting and observing locations and the orientation of the
projecting and observing
apparatus. If more than one projector/detector pair is used, each functioning
through a selected
angular range of view, the entire cross-section of the object can
theoretically be measured,
although in practice at least three and sometimes four or more such pairs
operating from several
directions about the scanned object, are typically employed in a given
application so as to afford
to complete three-dimensional information about the scanned object. If the
object is moved past the
projector or the projector is moved past the object, then a three-dimensional
image of the object
can be generated by combining the results of individual two-dimensional
profile data taken at a
series of scans along the length of the object.
is The invention is thus seen to include as a primary distinguishing feature,
use of a spatially
coded pattern in apparatus of the foregoing type to allow the determination of
a one-to-one
correspondence between projected and observed features of the pattern. There
are two aspects
to this feature. The first aspect is the use of the spatial coding scheme for
the projected beam of
light (or other radiation), which enables any small portion of the projected
pattern to be identified
2o uniquely and distinguished from any other small portion above some
predetermined size. The
second aspect is the use of the spatial coding to determine a correspondence
between a portion
of the pattern projected and a corresponding portion of the pattern observed,
thereby permitting
useful information to be obtained about the shape of that part of the object
to which the
corresponding portions of the pattern apply, even if information for the
complete scan (i.e.,
25 complete projected pattern) is not available.
What is not part of the invention is the choice of mechanism for projecting
the coded pattern
of light or other radiation (although the coded pattern is part of the
invention), the choice of
11
CA 02375013 2002-03-11
apparatus for obtaining an image of the object illuminated in the pattern of
radiation, the choice of
apparatus for digitizing the image and comparing it electronically to the
known pattern being
projected, the choice of means for calculating the coordinates of projected
features of the coded
pattern on the surface of the object (if this is desired), the choice of means
for displaying a cross-
s sectional representation of the object, nor the choice of means for
providing data pertaining to that
display to other equipment for further or other processing. Suitable
projectors, imagers,
triangulation calculation routines, monitors, and related software, etc. are
already known perseand
available in the industry for such purposes.
BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 is an schematic plan view of a first embodiment of electromagnetic
profile scanning
and detection apparatus according to the invention.
Figure 2 is schematic diagram showing the unfolded optical path of Figure 1.
Figure 3 is a sample mask according to the invention used to generate a
suitable pattern
of projected light for use in the apparatus of Figure 1.
Figure 4 is schematic block diagram of an embodiment of signal processing and
computational apparatus according to the invention for use in conjunction with
the scanning and
detection apparatus of Figure 1.
Figure 5 is a flow chart depicting the flow of data through the signal
processing and
computational apparatus of Figure 4.
Figure 6 is a graph depicting the processing of a sample of data, at three
stages in the
12
CA 02375013 2002-03-11
signal processing viz.: the raw signal amplitude; the amplitude of the
processed signal after the
raw signal has passed through a suitable differentiator and a noise reduction
filter; and the edge
detector output signal, for a specimen reflected signal generated by the
scanning and detection
apparatus of Figure 1 using the mask shown in Figure 3 and a test object.
Figure 7 is a bar graph showing duty cycles corresponding to the sample
received data
shown in Figure 6, determined from the edge detector output of the edge
detector of Figure 4.
Figure 8 is a graph showing the fitting error, calculated by a least squares
technique, of the
1o fit of the received pattern of the duty cycles shown in Figure 7 to the
transmitted pattern of duty
cycles of the transmitted signal corresponding to the mask shown in Figure 3,
as a function of the
offset between the first duty cycle of the pattern of duty cycles shown in
Figure 7 and the first duty
cycle of the pattern of duty cycles of the transmitted signal corresponding to
the mask shown in
Figure 3.
Figure 9 is a bar graph showing the duty cycles shown in Figure 7 superimposed
upon the
transmitted duty cycle pattern (shown as open bars), corresponding to the mask
shown in Figure
3, at the matching of best fit as determined from the data presented in Figure
8.
DETAILED DESCRIPTION OF THE INVENTION
A preferred embodiment of the one-dimensional scan variant of an
electromagnetic profile
scanner according to the invention is shown in schematic form in Figure 1 and
generally referred
to by reference numeral 11. The optical profile scanner 11 is suitable for use
in scanning the
surface of a log (say) whose longitudinal (axial) extension is generally
perpendicular to the plane
of a coded scanning beam 18. It is desirable that the profile scanner 11 be
placed relatively close
to the scanned object so that the resolution of the coded pattern on the
scanned object is
13
_ _ . _.__. _.___~. __.
__
CA 02375013 2002-03-11
sufficiently high. For example, the profile scanner 11 might be located from
about 16 to 30 inches
from the log 20 being scanned. The optical profiler 11 of Figure 1 makes a
series of scans each
generally perpendicular to the axis of the scanned log 20. As the log 20 moves
past the profile
scanner 11, the entire surface profile of the log 20 within the scanning beam
is scanned (as a
s series of line profiles). This can be accomplished by having the projector
(e.g. laser source 10) of
the profiler 11 project the beam 18 continuously onto the log 20 as it moves
past the profiler, and
having the receiver (e.g. image sensor 28) take a series of sequential
"snapshots" of the reflected
light pattern of the log 20 as sequential surface area portions of the log 20
come within the viewing
angle of image sensor 28.
An array of such profile scanners 11 may be positioned about the circumference
of the log
to enable a complete surface profile of the log 20 to be obtained.
The laser light source 10 and a suitable cylindrical lens 12 within the
housing 19 of profile
15 scanner 11 produce a beamed sheet (fan) of light of generally uniform
intensity across the angle
of the sheet, generally indicated as 8. The beamed sheet 8 may be considered
to be a two-
dimensional sheet lying in the plane of Figure 1 and having a very small
dimension (approximately
0.04" for typical laser sources) perpendicular to the plane of Figure 1. The
beamed sheet 8 is
reflected from mirror 14 and is thence transmitted through a mask 16 that
encodes the beamed
2o sheet 8 of light into a spatially varying pattern of beams 18 that is
directed toward the object 20
(e.g., a log) to be measured. In the preferred embodiment illustrated here,
the mask 16 is placed
as far as possible from the cylindrical lens 12 for the purpose of minimizing
the loss of pattern
resolution on the object (log 20) being scanned that arises from diffraction
of the beam 8 as it
passes through the mask 16.
The angle P through which the beam 18 is projected should not be unduly large,
because
a large angle tends to entail an unacceptable degree of non-uniformity of size
and resolution of
pattern elements as projected onto the scanned object (here log 20). To some
extent, such non-
14
CA 02375013 2002-03-11
uniformity can be compensated for by transmitting the beam 8 through a mask 16
that is curved
instead of straight, or by varying the relative size of pattern elements as
one proceeds from the
extremity to the centre of the pattern applied to the mask 16. However, it is
preferable to provide
several scanners each working in an acceptably small angular range rather than
to use too wide
a scanning beam 18.
A portion of the diffuse light reflected from the surface of the log 20 passes
through a
window 22 in profiler housing 19, is reflected by a mirror 24, and is focused
by an imaging lens 26
to form an image on the image sensor 28. The window 6 in which mask 16 is
placed and the
io window 22 are the only windows in the otherwise closed profiler housing 19
which housing 19 is
opaque to light. The sensor 28 may suitably comprise a linear array of light
detecting elements that
lie in the same plane as the pattern of beams 18. In the embodiment
illustrated, the image sensor
28 is preferably a linear array of charge coupled devices, referred to herein
as the CCD array 28.
~ s Mirror 14 and mirror 24 allow the elements of the preferred embodiment
illustrated here to
fit inside a compact housing while maintaining the preferred spacing of the
mask 16 and lens 12.
It will be apparent to those skilled in optical design that the mirrors 14 and
24 are not essential to
the system, but permit the transmitted and reflected light beams to be
"folded" so as to permit the
assembly of Figure 1 to be more compactly designed than would be the case if
such mirrors were
2o not used. Further, the negative effects of diffraction of the light beam 8
as it passes through the
mask 16 are minimized if the mask 16 is placed as close as possible to the log
20, and the mirror
arrangement of Figure 1 facilitates this objective.
The image data represented by the accumulated charges on the light sensitive
elements
25 (pixels) of the CCD array 28 is read out periodically (once after each
scan) and the resulting signal
processed by the signal processing apparatus shown schematically in Figure 4
and operating
functionally as represented in Figure 5 (which structure and operation are
described in detail below)
to determine the profile of the object 20 lying in the plane of the
transmitted encoded pattern of
CA 02375013 2002-03-11
beam 18. Each individual scan gives a line profile of that portion of the
object 20 lying in the
pattern of beams 18 at any given time. As the object 20 moves past the optical
profiler 11, a series
of such line profiles generate a surface profile for that portion of the total
surface of the object 20
that is scanned by the series of line scans. The signal processing apparatus
preferably uses a
s triangulation technique to determine the coordinates of the regions (spots)
of the surface of the
object 20 on which each beam of light in the pattern of beams 18 falls.
The application of a suitable triangulation technique is possible because the
laser light
source 10, the cylindrical lens 12, the mirror 14, the mask 16, the mirror 24,
the imaging lens 26,
i o and the CCD array 28 (collectively referred to as the optical elements)
are fixed in both orientation
and position relative to each other. Once the signal processing apparatus of
Figure 4 identifies a
first transmitted beam of light passing through a particular transparent
section of the mask 16 with
a second reflected beam of light falling on a particular pixel of the CCD
array 28 (a process
described in detail below), the coordinates of the point (spot) on the object
20 at which the first
is beam fell can be determined by ray tracing the optical path from the laser
light source 10 to the
CCD array 28.
To understand the application of triangulation principles to the invention,
consider unfolding
the optical paths shown in Figure 1 by removing the mirrors 14 and 24 and
placing the laser light
2o source 10 and cylindrical lens 12 and the imaging lens 26 and CCD array 28
at their respective
virtual positions as illustrated in Figure 2. If we consider a transmitted ray
15 of light passing
through a particular transparent section 13 of the mask 16 and the
corresponding reflected ray 17
from the object 20 that is detected by a particular pixel 27 of the CCD array
28, then triangulation
can be applied to determine the coordinates of the point 29 at which the light
ray 15 falls on the
25 object 20 being measured. It can readily be seen that a triangle is formed
by portions of:
(a) the incident light ray 15 that originates in the laser light source 10,
passes through the
cylindrical lens 12, the transparent section 13 of the mask 16, and intercepts
the object 20 at point
16
CA 02375013 2002-03-11
29; and
(b) the reflected light ray 17 that originates at point 29 on the object 20,
passes through the
imaging lens 26, and is detected by pixel 27 of the CCD array 28;
and
(c) the base line 25 from the cylindrical lens 12 to the imaging lens 26. (For
simplicity, we have
assumed that a particular ray falls on a particular pixel, but a typical
pattern element of a suitable
~o coded pattern is likely to fall upon a contiguous series of pixels).
The angle 21 between ray 15 and line 25 is measured as part of the calibration
of the optical
profiler 11 for each transparent section 13 of a given mask 16. Similarly, the
angle 23 between ray
17 and line 25 is either measured as part of the calibration of the optical
profiler 11 or is found by
interpolation from angles measured as part of the calibration for pixels near
to pixel 27. Once a
ray can be traced through a particular transparent section 13 of the mask 16
and correlated with
its reflection from the object 20 to a particular pixel 27 of the CCD array
28, the two angles 21 and
23 are known from the calibration of the optical profiler 11, and the included
side of the triangle
base line 25 is fixed as part of the construction of the optical profiler 11,
so that the distance from
2o the imaging lens 26 or the cylindrical lens 12 to the point 29 on the
object 20 can be found from
elementary trigonometry, as can the coordinates of point 29 in any coordinate
system fixed to the
optical elements.
An example of a suitable mask 16 for use in the apparatus of Figure 1 is shown
in detail in
Figure 3. In the mask, which may be, for example, a strip of plastic,
alternating transparent bands
and opaque bands form a pattern. The opaque bands are either narrow bands 31
or wide bands
33. The transparent bands are either wide bands 35 or narrow bands 37. The
combined width of
an opaque band and the transparent band to its immediate left (as seen in
Figure 3) is constant.
17
CA 02375013 2002-03-11
The essential characteristic of the mask 16 is that the pattern be designed so
that any
sequence of transparent and opaque bands larger than some minimum size, which
is a
characteristic of the design, be distinguishable from all other sequences of
bands in the pattern that
are the same size. For example, examination of Figure 3 will confirm that the
sequence 30 of
bands does not appear elsewhere in the mask pattern shown in Figure 3. Shorter
sequences of
bands that are not unique may be found in the mask pattern shown in Figure 3;
e.g., a wide light
band next to a narrow dark band or a narrow light band next to a wide dark
band both appear
repeatedly in the mask pattern shown in Figure 3.
~o It is the purpose of the invention to make possible a correlation of the
specimen signal read
out of the CCD array 28 for the reflected light from the irregular surface of
a particular test object
20 illuminated by light that has passed through the sample mask pattern shown
in Figure 3, with
the features of the sample mask pattern shown in Figure 3. The transmitted
pattern in the pattern
of beams 18 is of course determined by the pattern of light and dark bands in
the mask 16. For
i 5 the purpose of comparing the transmitted pattern with the received
pattern, the transmitted pattern
is divided into pattern elements each comprising a light (transparent) band
and an adjacent dark
(opaque) band immediately to its right (as seen in Figure 3). These pattern
elements can each be
described as beginning with a rising edge (dark-to-light transition), followed
by a falling edge (light-
to-dark transition), followed by a second rising edge (dark-to-light
transition), as one moves across
2o the pattern of beams 18 transmitted at the object 20 being measured, in a
left-to-right order with
respect to Figure 3.
The sample pattern shown in Figure 3 is designed so that in the overall
transmitted signal,
the rising edges occur with a fixed spacing whereas the falling edges occur at
either 1/3 or 2/3 of
25 the distance between consecutive rising edges. In other words, the pattern
elements each
comprise a selected one of two available optical symbols, one of which has a
falling edge at 1/3
the distance between consecutive rising edges, the other of which has a
falling edge at 2/3 the
distance between consecutive rising edges. For example, when read in the
direction of the arrow
18
__T .
CA 02375013 2002-03-11
32 (left to right) in Figure 3, the sequence 30 of bands may be represented as
the binary series
0111100001, where each 0 represents a symbol in which the falling edge occurs
at 1/3 of the
distance between the rising edges, and each 1 represents a symbol in which the
falling edge
occurs at 2/3 of the distance between the rising edges. Another way of
expressing the foregoing
is that the more opaque or darker symbols have the value 0 and the more
transparent or lighter
symbols have the value 1, or can be so considered. The portion of a pattern
element that is light
(transparent in the mask) is referred to here as a mark, whereas the dark
portion (opaque in the
mask) is referred to here as a space. The transmitted signal is therefore a
spatial sequence of
pattern elements each consisting of a mark and adjacent space with the
understanding that the
1o signal is read consistently in a given direction; here we use the direction
of arrow 32 in Figure 3.
The sequence 30 of pattern elements is thus 0111100001, where 0's represent
pattern elements
having narrower marks and 1's represent pattern elements having wider marks.
In Figure 3, the pattern elements are regularly spaced, i.e. each occupies a
uniform
is distance. However, since the surface of the object to be scanned may, in
the case of a log, be
assumed to be generally convex, it follows that the spacing of the pattern
elements as they appear
on the log's surface will vary as one proceeds from the edge to the centre of
the log. To
compensate for this effect, the relative distance occupied by the pattern
elements of Figure 3 could
be varied as one proceeds from the end to the centre of the pattern.
Alternatively, the mask 16
2o could be curved instead of straight.
The size and spacing of marks and spaces selected for the pattern of the mask
16 must
take into account the appearance of the pattern as it strikes the scanned
object. As mentioned,
diffraction of the beam of light as it passes through the mask 16 will cause
the light pattern on the
25 scanned object to be somewhat fuzzy. If the pattern elements of the pattern
in the mask 16 are
too small, it will not be possible to discriminate between the marks and
spaces of the pattern
elements on the surface of the scanned object. Assuming, for example, a
pattern element width
of about 0.03 inches on the mask 16, the width of the projected pattern
elements on the log 20 may
19
CA 02375013 2002-03-11
on the average be, say, four times that of the pattern elements in the mask,
or 0.12 inches. The
foregoing considerations imply that surface features on the log smaller than
0.12 inches cannot be
resolved, for the example under discussion.
s Note also that the choice of 1 /3 and 2/3 for the ratio of mark width to
pattern element width
is a somewhat arbitrary choice. One could have selected mark width values of,
say, 1/4 and 3/4
of pattern element width. With such latter choice, it is possible that one
might wish to use a slightly
greater width of pattern element if the discrimination between sequential
pattern elements on the
log's surtace were otherwise difficult to detect and measure.
The pattern applied to the scanned object need not be produced by shining
light through
a mask. It could, for example, be applied by means of one or more laser
sources in combination
with a rotating mirror (compare similar devices to be found within laser
printers). The choice of
pattern element parameter for mutual distinction of symbols (pattern element
types) is also open
1s to the designer - polarization differences, wavelength (colour)
differences, etc. could be chosen
instead of intensity/pattern element width distinctions.
An empirical approach to pattern design is recommended, taking into account
the foregoing
considerations.
The purpose of the receiving portion of the invention, including the imaging
lens 26, the
CCD array 28, and the signal processing circuitry described below, is to
receive the reflected light,
including the reflection of the pattern of beams of 18, from the object 20,
and to analyze the
received signal from the CCD array 28 in such a manner as to correlate as many
received pattern
2s elements as possible with transmitted pattern elements. Once a received
pattern element is
correlated with a transmitted pattern element, the coordinates of the point on
the object from which
that pattern element was reflected can be determined by a straightforward
triangulation method
such as that described with reference to Figure 2, because that received
pattern element is then
CA 02375013 2002-03-11
associated with a known ray of light that can be traced from the laser fight
source 10 through a
particular transparent portion of the mask 16 a determinable spot on the
scanned object 20 and
thence by reflection to a particular pixel element of the CCD array 28.
The selection of a specific pattern for the mask 16 can be done by trial and
error or by
systematic exploration of the possible patterns for a selected number of
symbols and a selected
total number of pattern elements in the pattern, for any given choice of
symbols. For example,
using the two different symbols illustrated in the mask shown in Figure 3 and
representing those
symbols in the manner described above by 0 for the symbol that is 1/3 light
(the space is twice as
~o wide as the mark) and 1 for the symbol that is 2/3 light (the mark is twice
as wide as the space),
a straightforward selection of useful patterns can be made by testing the
pattern of digits in the
binary representations of all numbers less than 2", where n is the total
number of pattern elements
in the pattern.
~s For example, the mask pattern shown in Figure 3 contains an exemplary 72
pattern
elements, each being a selected one of the above exemplary two available
symbols. Read in the
direction of arrow 32, the symbols commence with the leftmost pattern element
34 and end with
rightmost pattern element 36, so that the pattern can be represented by the
following binary
number:
010111101111111000010000111100001111111000000010000000111100000001111111
This pattern or any other pattern of 72 pattern elements each comprising one
of two
available symbols can be evaluated for use in the invention by systematically
comparing each
subpattern consisting of a string of binary digits to each other string of
binary digits of the same
length in the binary representation of the number being tested. The length of
the string being
compared would be started at a small number of consecutive pattern elements
(at least one more
than the number of different symbols) and would be increased each time the
testing procedure
21
CA 02375013 2002-03-11
determined that any string of that length appeared at least twice in the
pattern being tested. Each
length need only be tested until one string of that length fails to be unique
in the pattern.
Specifically, the string consisting of the first m pattern elements would be
compared with the m
pattern elements starting at the second digit in the pattern. If a match
occurred, then no further
testing at length m would be necessary and m would be increased by 1. If the
two strings did not
match, then the string consisting of the first m pattern elements would be
compared with the m
pattern elements starting at the third digit in the pattern, and so forth
until the first m digits were
checked against all the other strings of length m. Then the string consisting
of the m symbols
starting at the second digit in the pattern would be compared with the m
symbols starting at the
io third digit in the pattern and so forth. If all subpatterns of a given
minimum length m passed, then
that length would be the characteristic subpattern size of the pattern being
tested. After all patterns
were tested, those with the smallest characteristic subpattern size would
presumably be best
potential for use as patterns for masks of the given total number of pattern
elements using a given
set of symbols, because such patterns would contain the smallest possible
pattern element subsets
t 5 that could be uniquely identified. For patterns composed of elements that
can comprise a selected
one of more than two symbols, the strings tested would be simply numbers
represented in the
number system whose base is equal to the number of symbols. For example, if
the pattern were
made up of three possible symbols, then the numbers tested would be numbers
represented in the
base 3 number system, and the maximum number that would need to be tested
would be 3".
Note that characteristic subpattern size is not perse determinative of the
optical resolution
of the system, because the width of a pattern element can be varied (within
limits) to attempt to
meet the resolution requirement of the system.
The choice of specific pattern from available candidates satisfying the
criteria discussed
above admits of an empirical approach, taking into account other pattern
desiderata that the
designer may have in mind. For example, if the designer plans to use a "least
squares" fitting
routine (to be described further below), it may be desirable to avoid pattern
element sequences that
22
CA 02375013 2002-03-11
would closely resemble other close-by pattern element sequences if one pattern
element in any
such sequence were not detected and identified or if a spurious (non-existent)
pattern element
were improperly identified.
s The preferred embodiment of the optical profile scanner 11 of the invention
is constructed
so that mask 16 is interchangeable with masks having other patterns. Other
masks might, for
example, have larger or smaller pattern elements (larger or smaller
transparent and opaque
sections), for use with larger or smaller scanned objects, or for varying
resolution so that small
surface irregularities on the scanned object could be selectably detected or
ignored. Alternatively,
io an active LCD array could be used in place of the mask 16 so that the mask
pattern could be
changed without physical installation of another mask. Having the ability to
change the pattern
element size may be desirable if the surface characteristics of the objects)
being scanned change.
It is usually desirable that the dimensions of the mark of a pattern element
at the surface
i 5 of the scanned object be appreciably larger than any expected area of
abrupt surface discontinuity
(e.g. a crack) on the surface of the scanned object, so that the reflected
radiation from the object
will not be subject to spurious signal spikes. However, if information such as
the presence or
absence of surface features such as knot holes in logs is needed for setting
sawing equipment,
then the pattern element size must not be larger than the surface features
that must be detected,
2o as a larger pattern element size will average out the distances over the
region of the log on which
the pattern element falls, causing the smaller surface features to be
undetectable. On the other
hand, if the surface contains sharp discontinuities on the size scale of the
pattern elements, the
region of the surface on which a mark or a space of a pattern element falls
may be hidden by the
discontinuity, causing a missing mark or space and as a result, a break in the
received pattern.
2s If this occurs too frequently, the processing routines described below may
be unable to match any
portion of the received pattern to the transmitted pattern, resulting in no
measurement at all. The
remedy is to increase the size of pattern elements used.
23
CA 02375013 2002-03-11
In a preferred embodiment of the invention, the signal and data processing
apparatus for
processing the received signal in the CCD array 28 is schematically
illustrated in Figure 4 and
consists of three (say) printed circuit boards 76, 78, and 80 constructed out
of readily available off-
the-shelf components familiar to those skilled in the art. Printed circuit
board 76 contains the power
control circuitry 77 for the laser light source 10, and also contains the CCD
driver 75 and CCD
video amplifier 79 for reading out the voltages accumulated on the light-
sensitive pixel elements
of the CCD array 28 and for amplifying the signal consisting of the pixel
sequence of those
voltages. Printed circuit board 78 is constructed of discrete components and
programmable logic
arrays and consists of an analog-to-digital converter 69, edge detector 71,
and first-in first-out
io memory 73. Printed circuit board 80 is a central processing unit consisting
of a micro-controller
81, flash read-only memory 83, static random access memory 85, and serial and
parallel
input/output circuits 87.
The apparatus schematically illustrated in Figure 4 processes the received
signal to
1s correlate received pattern elements with transmitted pattern elements in
accordance with the
overall process shown functionally in Figure 5. Each part of the overall
process shown in Figure
5 takes place in portions of the apparatus illustrated in Figure 4 as
described in the following
discussion.
2o The signal read 60 from the CCD array 28 by the CCD driver 75 and amplified
by the CCD
video amplifier 79 undergoes digitization 61 in the analog-to-digital
converter 69. The resulting
signal is the set of the intensities of the light falling at locations (pixel
addresses) along the image
that was formed on the CCD array 28 by the imaging lens 26. The signal then
undergoes edge
detection 62 in the edge detector 71 to find the pixel addresses at which the
intensity of the light
25 falling on the CCD array 28 rises and falls. The edge detector 71 uses
conventional methods to
differentiate and smooth the signal and then to detect peaks in the result.
Figure 6 illustrates the processing carried out by the edge detector 71 as
applied to the
24
CA 02375013 2002-03-11
received signal corresponding to the portion of the transmitted signal
originating from the portion
of the mask shown in Figure 3 from the mark of pattern element 38 to the mark
of pattern element
41. The magnitude of the raw received signal 42 from the CCD array as a
function of the pixel
address (position on the CCD array) is plotted as a dark solid line in Figure
6. In Figure 6 the
s differentiated and smoothed received signal 44 is plotted as a light dotted
line. Spikes, of which
spikes 46, 48, 50, 52, 54, 56, 58, and 59 are examples, are plotted at the
maxima and minima of
the differentiated and smoothed received signal 44. The spikes are plotted at
pixel addresses at
which the received signal increases or decreases suddenly, i.e., edges of the
marks and spaces
of received pattern elements.
The mark of pattern element 38 (Figure 3) corresponds to the received signal
between edge
46 and edge 48. The space of pattern element 38 corresponds to the signal
between edge 48 and
edge 50. The mark of pattern element 40 of the mask 16 (Figure 3) can be seen
to correspond
to the received signal between edge 52 and edge 54. The space of pattern
element 40
1s corresponds to the received signal between edge 54 and edge 56. (Note that
in the exemplary
received signal of Figure 6, the edge detector 71 encountered difficulties
between edge 56 and
edge 58, missing a falling and a rising edge, because the differentiated and
smoothed signal 44
between edge 56 and edge 58 was less than the threshold for reliable edge
detection. The
threshold level is set by testing without the mask 16 in the window 6 to
determine the noise level.
2o The threshold is set accordingly.)
Note that, as in the case of any other system in which data are communicated,
the system
designer has the choice of attempting to capture all available information
from the data at the risk
of increased noise, or maintaining a detection threshold at a relatively high
level to reject all or most
2s noise, at the risk of failing to capture some information from the data.
Again, an empirical approach
is preferred, to balance the desiderata of information capture and noise
suppression.
The edge detector 71 stores the pixel addresses and the direction (rising of
falling) of each
CA 02375013 2002-03-11
edge in the received signal in the first-in-first-out memory 73 to be read by
the micro-controller 81
when the micro-controller 81 is ready to process the scan represented in
Figure 6.
Referring to Figure 5, the first three functions (reading step 60, analog-to-
digital conversion
61, and edge detection 62) have already been discussed. The functions symbol
recovery 64,
normalization 66, pattern matching 68, and ray-assignment-and-translation-to-
coordinates 70 are
performed by the micro-controller 81 (Figure 4) using software and calibration
data stored in the
flash read-only memory 83.
1 o The duty cycle of a pattern element is the portion that the mark of the
pattern element
(measured in number of consecutive pixels) is, in width, of the width (again
measured in number
of consecutive pixels) of the pattern element containing the mark. The
normalization routine 66
involves the calculation of the apparent duty cycle of each received pattern
element by dividing the
difference in pixel addresses of the rising and falling edges of the mark of
the received pattern
element, by the difference in the pixel addresses of the rising edges that
constitute the beginning
and end of the received pattern element. This is illustrated in Figure 6 for
the pattern element
received that corresponds to the transmitted pattern element 38 shown in
Figure 3. Suppose, for
example, that the pixel address of edge 50 is 574, that of the edge 46 is 525,
and that of the edge
48 is 560. The duty cycle of the received pattern element from edge 46 to edge
50 is then:
560-525 - 35 =0. 71
574-525 49
The duty cycles of all transmitted pattern elements are determined by the
design of the
mask shown in Figure 3 and are, in the illustrated embodiment, either 1/3 or
2/3.
2s The calculated values of duty cycles for received pattern elements will be
variable due to
26
CA 02375013 2002-03-11
the curvature of the surface of the object 20. The duty cycles of the received
pattern elements
corresponding to the portion of the transmitted signal from the mark 38 to
mark 41 in Figure 3 are
plotted as bars in Figure 7. For example, the received pattern element
corresponding to
transmitted pattern element 38, which in Figure 6 is the signal from edge 46
to edge 50, has a duty
s cycle represented by the duty cycle bar 82 in Figure 7. Similarly, the duty
cycle of the received
pattern element corresponding to transmitted pattern element 40, which
received pattern element
in Figure 6 is the signal from edge 52 to edge 56, is represented by the duty
cycle bar 84 in Figure
7.
~o Before the pattern matching routine 68 and the ray-assignment-and-
translation-to-
coordinates routine 70 can be employed, the received signal pattern of duty
cycles plotted in Figure
7 is only known to correspond to some as-yet-undetermined portion of the mask
pattern shown in
Figure 3, and thus to some as-yet-undetermined portion of the object 20 being
scanned. A human
operator might be able to see the correspondence between the received signal
pattern and
15 transmitted signal pattern easily from inspection of Figure 3 and Figure 7,
but in a practical
application, the correspondence must be found almost instantly by the signal
processing apparatus,
which necessitates a mathematical approach. To find which portion of the
transmitted pattern
corresponds to the received pattern plotted in Figure 7, the pattern matching
routine 68 is
employed to attempt to fit the duty cycle pattern plotted in Figure 7 to some
determinable portion
20 of the known duty cycle pattern of the entire transmitted signal. The duty
cycle values for the
transmitted pattern elements found in the mask shown in Figure 3 are shown in
Figure 9 as a
sequence of open bars, and the received duty cycle pattern is shown as a
sequence of solid bars.
In the illustrative example, to obtain the best fit, the micro-controller 81,
using the pattern
2s matching routine 68, attempts to match the received pattern of the 18 duty
cycle values plotted in
Figure 7 to each possible sequence of 18 duty cycle values in the sequence of
72 duty cycle values
for the transmitted signal shown in Figure 9 as open bars. At each offset of
the first duty cycle of
the received pattern from the first duty cycle of the transmitted sequence,
the micro-controller 81,
27
CA 02375013 2002-03-11
using the pattern matching routine 68, calculates a measure of the closeness
of the fit (the fitting
error) by summing the squares of the differences between the duty cycle values
of the received
pattern and the subsequence of the transmitted signal being tested.
Specifically, the difference
between the first duty cycle of the received pattern and the first duty cycle
of the subsequence of
the transmitted signal being tested is squared and added to the square of the
difference between
the second duty cycle of the received pattern and the second duty cycle of the
subsequence of the
transmitted signal being tested, and so forth. The fitting error for the
illustrative example is plotted
in Figure 8 as a function of the offset between the first duty cycle of the
received pattern and the
first duty cycle of the transmitted signal pattern. The smallest fitting error
occurs at an offset of 35
~o pattern elements, indicating that the received pattern corresponds to a
portion of the transmitted
signal commencing at the 35th pattern element. The fit of the received pattern
shown in Figure 7
to the transmitted pattern obtained from the use of the mask illustrated in
Figure 3 that is obtained
by this procedure is shown in Figure 9. The black bars represent the received
pattern shown in
Figure 7 and the open bars, the transmitted pattern obtained from the use of
the mask shown in
~5 Figure 3. (This "least squares" approach to correlation of received signal
with transmitted signal
is a preferred approach, but not the only possible approach. For example, the
pairs of duty cycle
values, referred to in the description of the least squares method above,
could be multiplied
together rather than the differences taken and then added together, in a
process sometimes
referred to as convolution. As another example, a human operator could, albeit
slowly, monitor the
2o two patterns and make a visual determination of the best fit.)
Each pattern element of the transmitted signal pattern can be correlated with
a known ray
(beam) of light of width just sufficient to include such pattern element, that
has passed through the
mask 16 shown in Figure 3. The mark of the pattern element will have passed
through a known
25 transparent band of the mask 16. Therefore, once the offset from the scan
limit at which a
received pattern of duty cycle values best fits the duty cycle values of the
pattern element
transmitted signal is found, each mark of that received pattern can be
assigned to a unique ray of
light that passed through a now-known transparent band of the mask 16. In
calibrating the
28
CA 02375013 2002-03-11
apparatus of Figure 4, a reference table 74 (Figure 5) is preferably used that
provides the set of
the angles with respect to the mask 16 and the CCD array 28 at which a beam
would fall on the
object 20 for each possible combination of transmitted pattern element and
received pattern
element pixel address on the CCD array 28. The coordinate assignment routine
70 uses the
reference table 74 to assign coordinates to each pattern element of each
received pattern on the
surface of the object 20 being scanned.
Finally, the output routine 72 (Figure 5) converts the coordinates of the
profile of the object
20 being scanned into a form that can be transferred as serial or parallel
data to the host computer
92 (Figure 4) for further use. The input/output hardware on printed circuit
board 80, in addition to
carrying out output routine 72, preferably also provides input capability to
allow the host computer
92 to request the next set of data for determination of the next profile in
the set of profiles to be
determined, which when combined, provide surface coordinate information for
the entirety of the
surface of the scanned object (e.g. log 20) within the field of view of the
profile scanner 11.
The embodiment of the profile scanner 11 described above is assumed to
incorporate a
single scanning head. (A "head" would include the elements illustrated in
Figure 1 ) In practice,
more than one such head would be disposed generally circumferentially about
the periphery of the
log 20 (say) to obtain an entire profile of a given log 20, or else a
circumferential array of such
2o profile scanners would be disposed about the periphery of the log 20, to
achieve the same result.
The host computer 92 would combine the profile information from more than one
scanning head.
Software to do this and to process the combined profile information data for
use in the control of
saw mill equipment is known and commercially available from, e.g., MPM
Engineering Limited.
Langley, British Columbia and Porter Engineering Limited, Richmond, British
Columbia.
The symbol recovery function 64 shown in Figure 5 is an optional feature that
a person
skilled in the art might wish to add to the embodiment of the invention
described above to allow
measurement of the surface of the scanned object under adverse conditions.
Under adverse
29
CA 02375013 2002-03-11
conditions, poor surface characteristics (e.g., variations in reflectivity) of
the object being measured
or other problems may cause the received signal to be too weak or too noisy at
some pixel
addresses to enable the edge detector 71 to correctly identify rising or
falling edges (thereby
causing edge data to be missing or spurious edge data to be produced by the
edge detector 71 ).
The symbol recoveryfunction 64 would involve processing the entire set of edge
information
from the received signal produced by the edge detector 71 to find subsets of
the edge information
that appear to be valid (in the sense to be described below) and then adding
or removing spurious
edge information to enlarge each valid subset as much as possible (permitting
adjacent subsets
i o to combine into a single valid subset where possible). To do this, the
symbol recovery function 64
relies upon the premise of constant spacing of rising edges in the transmitted
signal. As stated
above, the spacing of rising edges is constant in the exemplary transmitted
signal here being
discussed because the rising edges (opaque-to-transparent transitions) are
evenly spaced in the
mask 16 shown in Figure 3. The spacing of successive rising edges in the
received signal is not
necessarily quite as obvious as in the transmitted signal; the spacing of
successive rising edges
in the received signal will typically vary slowly if the scanned object (e.g.
log 20) has a moderate
curvature, because the direction from which the reflected pattern is viewed
differs from the direction
from which the transmitted pattern of beams 18 is projected. If the reflection
data reveal that
apparently the spacing of the rising edges appears to vary abruptly, or if a
given sequence of
2o consecutive rising or falling edges detectable by the discrimination
apparatus of Figure 4 were too
widely or too narrowly spaced, then portions of the reflected pattern may be
missing from the
received signal data, or else spurious pattern elements may be improperly
present in the received
signal data, either because the curvature of the surface of the object varies
too rapidly (as might
happen for very small knots in a log) or because portions of the surface may
be hidden from the
view of the CCD array 28 (as might happen if the log conveyor occluded a part
of the log, say).
The symbol recovery routine 64 acts on the set of pixel addresses of the
rising edges in the
received signal provided to it by the edge detector 71. The pixel addresses of
the rising edges are
I
CA 02375013 2002-03-11
arranged and numbered in order of increasing pixel address. To determine
whether a rising edge
is likely to be valid, it is assumed that the local spacing (the differences
between the pixel
addresses of consecutive rising edges) of valid rising edges will vary slowly,
so that valid rising
edges can be identified by a measure of the local rate of change of the
spacing of the rising edges
near each prospective valid rising edge. A variability of, say, 10 per cent
from one local spacing
to the next may suggest that the data are reliable, but a variability of, say,
50 per cent from one
local spacing to the next may indicate unreliability of the apparent rising
edge number sequence,
and consequently unreliability of the apparent pattern element number
sequence, which latter is
what is desired to be ascertained.
A suitable measure M; of the local spacing variability has been found to be
M.= (A1+1-Ai) ~Ai Ai_1)
i IAi+1_Ai) + l,Ai_Ai_1)
where:
i is the integer identifying the i'" rising edge.
A; is the pixel address of the i~' edge
(A; - A~) is the difference, measured in pixels, between the pixel address of
the it" rising edge A; and
that of the j'" rising edge A~.
This measure M, has the advantage of being normalized to the average local
spacing at
rising edge A;, because the denominator
A.)
is simply twice the local average spacing
( A~ . . -A, . )
31
CA 02375013 2002-03-11
near A;, and the numerator is simply the difference in spacing between the
increasing and the
decreasing directions of pixel address, relative to the pixel address under
consideration. Therefore
a large M, indicates that the local spacing is changing relatively rapidly
near A;, suggesting
unreliable data, whereas a small M; indicates a small change of local spacing,
suggesting that the
s data are reliable in the vicinity of that pixel address.
Using the M; values, sets of rising edge pixel addresses containing at least
three rising edge
pixel addresses are searched for in the edge data set such that each member of
a set has a value
of M; less than some preselected minimum (0.25, i.e. 25 percent, has been
found to be suitable).
Each valid subset must then satisfy the requirement that it includes all
values of A~ for which i _<
1o n <_ j; j >_ i + 2; and M~ < 0.25. Members of these sets are referred to
here as valid rising edges,
rather than the longer term valid rising edge pixel addresses.
If all rising edges in the data received from the edge detector are found to
be valid, then the
symbol recovery function 64 is terminated, and data processing moves on to the
normalization
is function 66, as described above.
In some cases, however, the rising edge data corresponding to the extremities
of the
received pattern may be poor due to increasing curvature of the scanned object
in these regions,
causing rising edges to be perceived as missing. For example, in Figure 6, a
rising edge has not
2o been detected between rising edge 56 and rising edge 58. The remainder of
the data processing
in the symbol recovery function 64 deals with a method of attempting to extend
the sets of valid
rising edges by inserting contrived rising edge data where they are expected
to occur, or by
removing rising edge data from where they are not expected to occur. This
method uses estimates
of the likely pixel addresses of rising edges, based on the trend of the
spacing of rising edges
25 already accepted as valid.
The process of extending a set of valid rising edge pixel addresses will be
described here
for the case of extension in the direction of increasing pixel addresses. The
same procedure can
32
CA 02375013 2002-03-11
be applied by extension to lower pixel addresses. The process is iterative in
that if a rising edge
pixel address is accepted to be valid, then the process is repeated using the
newly validated pixel
address as part of the set of valid rising edge pixel addresses to attempt a
further extension. Only
the first iteration is described in detail here.
The first step of the extension process (for extension to larger pixel address
values) is to
estimate the pixel address of the next rising edge beyond the largest pixel
address of a valid rising
edge, based on the spacing of the last three valid rising edges. The estimate
found to be
satisfactory is given by the equation
E =V+~V_v )+~~V_y )_(y -V )
n+1 n n n-1 n n-1 n-1 n-2
where E~+, is the estimated pixel address of the next rising edge and V~ is
the pixel address of the
n~' rising edge that has been accepted previously as valid. This equation
estimates the expected
change in spacing of rising edges as the change in spacing of the previous two
rising edges. That
~5 is, (V~ - V~_,) is the last spacing and (V~_, - V~_2) is the spacing before
that. The difference between
these spacings is used as an estimate of the change in spacing from V~ to the
expected edge E~+,.
In other words, the next expected rising edge pixel address is the last valid
pixel edge address plus
the spacing between the last two valid edges plus the change in spacing
between the last two valid
edges and the spacing between the last but one and last but two valid edges.
The edge data beyond the last edge currently accepted as valid can either have
edges too
closely spaced or too widely spaced to have been accepted as valid previously.
To rectify the data,
either some edge data must be deleted or some must be added. The rectification
procedure is as
follows: Having estimated the next edge address E~+,, the measure of the
closeness of the next
edge A~+, in the observed data set of rising edge pixel addresses to the
estimated edge is
calculated by the ratio:
33
CA 02375013 2002-03-11
An+1- V
Rn+ 1=
En+1 _ V
where A~+, is the next pixel address of a rising edge in the observed data set
of rising edges after
the last valid edge V~ and En+, is the estimated pixel address calculated as
above, pursuant to
s equation (2).
There are now four possible cases which can occur:
Case A: If the ratio R~+, is 1.0 or within a preset range (t 0.3 is
empirically found to be useful)
io centered on 1.0, then A~+, could be a valid pixel address of a rising edge.
To verify this, the ratio
for the next observed rising edge A~+2 is calculated as R~+Z by the following
equation:
Rn+2 - An+2 V
En+1 n
If the ratio R~+2 is closer to 1.0 than Rn+, is, then A~+2 is a better choice
for the next valid edge, and
A~+, is discarded from the rising edge data set. In that case, An+s is also
checked to make sure it
is not closer than A~+2, and so on until the observed rising edge pixel
address closest in pixel
is address to E~+, is found. That observed rising edge pixel address becomes
V~+, and all observed
pixel addresses between it and V~ are discarded from the valid rising edge
data set as unreliable.
The process described above is then repeated with the newly enlarged set of
valid rising edge pixel
addresses and the remaining observed rising edge data set, that now excludes
previously
discarded pixel address data. This rectification process continues until all
remained rising edge
2o data is tested, or another set of valid rising edges is reached.
Case B: If the ratio R~+, is 2.0 or within a preset range (t 0.3 is
empirically found to be useful)
centered on 2.0, then a valid rising edge may have been missed. A new valid
rising edge pixel
34
CA 02375013 2002-03-11
address V~+, with a value equal to E~+, is added to the valid set, inserted
after pixel address V~, and
the iterative rectification process is continued with the enlarged valid set.
Case C: If the ratio R~+, is less than 1.0 and does not qualify under case A,
then A~+, is
s discarded from the set of edge data and the rectification process run
through again, using data
excluding An+,.
Case D: If the ratio Rn+, is greater than 1.0, but does not fall under either
case A or case B,
then the process is ended and the valid subset is truncated. The rectification
routine would then
i o try extension to lower rising edge pixel values (so far we have been
discussing extension upwards,
not extension downwards) until a similar result occurred. Once extension as
far as possible to
lower values has been completed, the rectification routine applies the same
set of procedures to
any other valid subsets. Once the valid subset or subsets are extended as far
as possible, the valid
subset or subsets are provided to the normalization routine 66, and the
remaining processing
15 functions treat each valid subset as a separate sub-scan because the proper
number of rising
edges between the valid subsets is unknown.
Where contrived rising edges have been added (inserted) and no falling edges
have been
found, the symbol recovery routine flags all such rising edges so that the
unknown pattern
2o elements corresponding to the rising edges with unknown falling edges are
not used by the fitting
function.
Variants within the scope of the invention will be readily apparent to those
skilled in the
technology. For example, instead of a single projected pattern characterized
by only one
2s parameter, two or more patterns or two or more parameters could be used.
For example, a
composite projected pattern might comprise a pattern in red light and a
pattern in green light.
Further, more than one pattern may be projected simultaneously with the use of
more than one
detector. For example, patterns in differing colors using brightness and
darkness may be projected
CA 02375013 2002-03-11
simultaneously and detected simultaneously by detection systems capable of
discrimination of both
intensity and color.
36