Note: Descriptions are shown in the official language in which they were submitted.
131~3
METHOD AND APPARATUS FOR REGISTERING COLOR SEPARATIONS
This invention relates in general to the field of graphic
arts and more particularly to the registration of halftone
color separation film. Still more particularly, the
invention is directed to a method and apparatus for
obtaining highly accurate and repeatable registration
of color separation films in order to permit printing of
high quality color pictures.
In the printing of high quality color photographs such as
those which appear in mass circulation magazines and
other publications where quality is of overriding
importance, the color original is broken down into
separate photographic images that are processed
separately. The printed picture is a halftone picture in
which the appearance of continuous tones is realized
by breaking the picture detail up into halftone dots of
varying sizes. In the commonly used four color process,
the halftone color separations are four in number. Each
color separation carries black and white tone information
that reflects the process color content of the
original color picture. The final reproduction requires
that the four halftone color separation films be precisely
registered or aligned so that the printed picture
faithfully reproduces the original.
At present, process color registration is for the most
part performed manually by highly trained persons referred
to in the printing industry as strippers. The manual
~s , . . ,~ -- ~
-2~ ~ 3 1 ~
registration process involves taping or stripping the
separation films (negatives or positives) to carrier
sheets which are usually clear polyester film. The first
reference color film is stripped to a prepunched carrier
S sheet. The film with the second color image is
applied to a second overlaid prepunched carrier sheet, is
visually aligned or registered with the first separation
film, and is then stripped to the second carrier in the
registered position. The third and fourth separation
films are registered with the others by following the
same procedure. Holes which are prepunched in the carrier
sheets are placed on a pair of register pins in the
contact frame to maintain the reyistration for the final
reproduction.
The manual procedure for registering color separation
films is subject to a number of shortcomings, mostly
relating to accuracy. It is necessary for the stripper to
register the separations to within a fraction of a row of
halftone dots in each case, and this high degree of
accuracy is difficult to obtain by even the most skilled
and experienced strippers. In high quality printing,
there are usually about 150 halftone dots per inch, and
the center to center dot spacing is less than 7 mils. As
can easily be appreciated, human error inevitably
results from time to time, and poor quality picture
reproduction often occurs. If an unacceptable
registration is not discovered until press time, it is
; necessary to hold up the presses until the error is
corrected. Press delays due to registration errors
are inordinately expensive events which are to be avoided
if at all possible.
~ Manual registration is also a tedious and time consuming
;~l 35 process which is highly labor intensive. Typically,
registration of four color separations requires between 9
and 20 minutes for a highly skilled and highly paid
stripper to perform. Consequently, the labor costs
.~ ~ , .. .
" ~ ' . ' ' ' ' ' ~ ~ "' '. '
.
;
: , ~ .
, -3- 1 3 ~ 1~ 63
contribute significantly to the overall costs.
Consistency and reliability are also lacking because the
quality of the registration is highly dependent upon the
skill and vision of the individual stripper, and these can
vary considerably. Even the same stripper cannot
maintain the same level of accuracy from one job to the
next due to the variations that are inherent in human
performance capabilities.
Registration aids are sometimes used to magnify the
halftone dot detail, but aids of this type add little to
the accuracy. When a small portion of a halftone picture
is magnified, it appears to the human eye to be a random
collection of halftone dots rather than a recognizable
lS picture. Therefore, picture details are often
~` extremely difficult to align and this problem is
aggravated by the difficulty the stripper has in making
, controlled muscle movements when viewing a magnified
~;' picture. A shaky hand or tired eyes can destroy
registration, and this tendency increases with
magnification. For these reasons, magnification aids are
of limited utility and have not solved the problems that
~' are inherent with manual registration.
In recent years, machines have been developed to
either aid or replace the manual registration procedure.
One machine is an optical-mechanical device having
mechanical arms for movement of the carrier sheets and a
magnified optical display for aiding the worker who
, 30 performs the registration. Picture detail can be used
;~1 as the basis for the registration, or special marks known
as register marks can be used. The register marks are
typically cross hairs located outside the field of the
picture. Whether picture detail or re~ister marks are
used, this machine still relies on human skill and
~1 vision and is thus subject to many of the same problems
,~' that are associated with the strictly manual registration
5~ procedure.
. ,
, ~ :
,
'G~
_ -4~ 3
Two other known machines rely on the register marks
entirely in order to achieve registration. One of these
machines is an electro-mechanical device having an
electro-optical sensor which detects the centers of the
register marks. sased on the information obtained by
the sensor, the mechanical device moves one film into
register with the other and then punches holes in the
carrier sheets. The other machine is essentially a
stripping robot that functions much like the electro-
mechanical machine but tapes the separation films ontoa prepunched carrier rather than acting to punch the holes
itself. The basic problem with both of these latter two
machines i5 that they rely wholly on the register marks to
obtain registration. If the register marks are
inaccurate, registration is also inaccurate. It is
not uncommon for the register marks to be destroyed when
the films are trimmed or otherwise processed, and missing
registration marks render these machines completely
useless. The register marks are also inaccurate at times,
and this too destroys the accuracy of registration.
U.S. Pat. No. 4,641,244 which issued on February 3, 1987
to Wilson et al. discloses an algorithmic based system for
registering halftone films, and this system functions well
for the most part. However, one problem that has been
discovered results in inaccuracies in some situations.
For example, the system disclosed in the above referenced
patent experiences difficulty in accurately registering
pictures that exhibit widely varying digital picture tones
between common picture areas that are to be
registered. Thus, if the picture areas to be registered
entail a white square within a black background which is
to be registered to a black square within a white
background, the tones do not match at all and the system
is not able to make the registration.
.,
The present invention is directed to an improved
- algorithmic based method and apparatus which makes use of
: 1,
,
, ,
.
: ; :
.. ~ - .
13119~3 61316-687
edge based registration techniques to registar halftone pictures
more reliably than occurs in the system of the above referenced
patent. In accordance with the invention, the common macroscopic
edges of two pictures to be registered are extracted and the edges
are linked into line segments which can be optimally aligned. The
process of optimally aligning the line segments provides a
prediction of the offset required to achieve alignment or
registration of one picture with the other picture.
More specifically, the invention provides in a method of
registering a pair of color separation films containing halftone
dot detail and macroscopic edges which align when the films are
registered, the steps of: selecting one of the films as a
reference film; recording first and second pictures of the
reference film centered at spaced apart first and second
locations, respectively; recording third and fourth pictures of
the other film centered at locations thereon which approximately
correspond to but may be offset from the respective first and
second locations; extracting from said first and third pictures
the locations of corresponding macroscopic edges on the reference
film and on the other film; extracting from said second and fourth
pictures the locations of corresponding macroscopic edges on the
reference film and on the other film; and determining the offset
between the edge locations on the reference film and the corres-
ponding edge locations on the other film to thereby determine the
positional adjustment of the other film necessary for registration
with the reference film.
The invention also provides apparatus for effecting
registration between a pair of color separation films containing
~,
'' ~
:~,
~ ~ '
'
, . . .
131~9~3
5a 61316-687
halftone dot detail and macroscopic edges which align when the
films are registered, said apparatus comprising: a digital camera
operable to record digital pictures at locations on each film with
the locations on the respective films corresponding but possibly
being offset; means for extrac'ing from each digital picture the
locations of macroscopic edges thereon; and means for calculating
the offset between the edges on corresponding pictures of the
films thereby determining the relative movement necessary to bring
the films into registration.
The method and apparatus of the present invention makes
use of a series of algorithmic steps which are carried out by a
digital computer, the computing power and speed of which are taken
advantage of in order to carry out the registration. After the
gray level pictures of the halftone films have been optimally
thresholded by known techniques, the macroscopic edges are
extracted through application of a Laplacian of a Gaussian (LOG)
convolution filter having a width parameter ~' that is adjusted to
detect only macroscopic edges and not the edges around the
individual halftone dots.
Preferably, the zero crossings of the LOG output are ?
found at l/8 resolution in order to reduce the computational time
without sacrificing accuracy. Full resolution is restored by
accurately interpolating the reduced resolution zero crossing to
the nearest original image pixel. The final interpolated zero
crossings (edge locations) are corrected for the positional bias
that is inherent in the LOG operator. Linear segments are then
produced by linking and tracing the edges and approximately these
connected edges by line segments, fit within a given tolerance.
~'' ~
,~ .
- : .
:~ , . .. '
- 1311~3
5b 61316-687
Finally, the segments are registered in a two stage
process which first involves initial registration accompli.shed by
the parameter space method (PSM). The second stage involves
correction for size differences by
,,, ~3
,
.
` -6- ~3~ 3
"splitting the diEference" using a quadratic form
formulation o~ the least squares problem, thereby
minimizing the mean distance between matching segment
pairs.
By determining, for both of two selected pictures on each
film, the offset of one picture (referred to as the moved
picture) required to bring it into registration with the
- other picture (reference picture), the films can be
10 punched at locations to assure they will register when
overlaid on registration pins. Consequently, the halftone
pictures can be assembled in registered position, and the
quality of the final product is enhanced due to the
accuracy of the registration and the repeatability
15 provided by the method and apparatus of this
invention.
The final algorithmic step, in fact, is the computation of
the punch hole locations, for each non-reference film,
20 based on the registration offset data for both of the
two selected pictures. Basically, this final algorithm ?
computes the translation and rotation transformation
required to suitably align a vextor on each non-reference
film (between picture points) with the corresponding
25 vector connecting the analogous picture points on the
reference film. If the vector to be moved is M and the
reference vector is R, the registration offset data
computed by the method of this patent application is
simply the difference R-M between vector tips and tails
30 prior to final registration. The final registration
transformation is then applied to the reference punch hole
locations to determine the table motion required to punch
holes on each film to be registered to the reference film.
ibed in U.S. ~atent Soe ~,641,244 h ver
~.,,, . . - :
,
:.
' .
In the accompanying drawings which form a part of the
specification and are to be read in conjunction therewith
and in which like reference numerals are used to indicate
like parts in the various views:
Fig. 1 is a top plan view of a digital registration
machine constructed to effect registration of color
separation films according to a preferred embodiment of
the present invention, with some components shown in
broken lines and portions broken away for purposes of
illustration;
Fig. 2 is a sectional view taken generally along line 2-2
of Fig. 1 in the direction of the arrows;
Fig. 3 is a fragmentary sectional view on an enlarged
scale showing the digital camera and mechanical punch
which are included in the machine;
Fig. 4 is a fragmentary sectional view on an enlarged
scale taken generally along line 4-4 of Fig. 3 in the
direction of the arrows;
Fig. 5 is a top plan view on a reduced scale showing the
movable chase of the machine in position for recording
of the image at one registration point centered beneath
the camera;
Fig. 6 is a top plan view similar to Fig. 5, but showing
the chase in position for punching of one of the
registration holes;
Fig. 7 is a schematic circuit diagram of the pneumatic
system of the machine;
i 3 is a s~mplified blhk Odpa~9rt~on of ~ e ~ c~
,,
,
: .
. ~ .
,
' : ' -
'
. ' ' , .
Fig. 9 is a somewhat more detailed block diagram of the
control components of the machine;
Fig. 10 is a flow chart for the algorithmic process which
is performed by the machine to effect registration of
halftone color film separations;
Fig. lla is a diagrammatic illustration of a macroscopic
edge contour which separates dark and light regions of a
digital picture;
Fig. llb is a diagrammatic illustration showing the edge
contour of Fig. lla detected at discrete edges, with the
arrows indicating the edge direction;
Fig. 12a is a diagrammatic illustration of a step edge
~ contour;
I Fig. 12b is a diagrammatic illustration of the convolution
response of the step edge of Fig. 12a to a second
derivative operator;
!
Fig. 12c i8 a diagrammatic illustration of the convolution
response of the step edge of Fig. 12a to a gradient
` 25 operator;
Fig. 13a is a diagrammatic illustration depicting the
profile of a Gaussian operator;
Fig. 13b is a diagrammatic illustration depicting the
profile of a Laplacian of a Gaussian operator;
Fig. 13c is a diagrammatic illustration depicting a plan
;, view of the Laplacian of a Gaussian operator;
Fig. 14a is a diagrammatic illustration depicting the
profile of a Laplacian of a Gaussian operator superimposed
on the profile of a bright feature having a width less
i,,.~,i
li,, ,
., - , , . , .
~; ' ' ~,,
;, ' , , :,
,~ , - - - ~, .
-9~ 3
than the width of the operator;
Fig. 14b is a diayrammatic illustration depicting the
convolution response of the feature of Fig. 14a to the
Laplacian of a Gaussian operator;
Fig. 15 is a diagrammatic illustration depicting the
profile of the Laplacian of a Gaussian operator and its
minimum configuration for detecting half tone dots having
widths d;
Fig. 16 is a diagrammatic illustration depicting
application of a mask M to a picture P in order to
generate a decimated convolution;
Fig. 17 is a diagrammatic illustration depicting the eight
quantized directions of the edges in the U.S.C. predicate
application;
Fig. 18 is a diagrammatic illustration depicting the
interpolation grid which is erected about each initial
edge location in accordance with the invention;
Fig. 19 is a diagrammatic illustration depicting the model
edge used to correct the edge locations for operator
bias;
Fig. 20 is a diagrammatic illustration depicting the
geometry of the edge bias correction;
Fig. 21 is a diagrammatic illustration depicting
' qualitatively how a 45 shift in direction can improve the
edge direction used to compute the edge bias correction;
'~ i
Fig. 22 is a diagrammatic illustration depicting data
points that form the basis for Layrange polynomial
interpolation in accordance with the invention;
:
;...
o- 131~
Fig. 23 is a diagrammatic illustration depicting the
accumulator array P employed in the parameter space method
of segment registration;
Fig. 24 is a diagrammatic illustration depicting
qualitatively the overlap in score painting windows which
creates a peak in the PSM parameter space;
Fig. 25 is a diagrammatic illustration depicting the
parameter space score profiles before and after
Gaussian smoothing;
Fig. 26 is a diagrammatic illustration depicting improper
and proper registration of a pair of "blobs~ of detail;
Fig. 27a is a diagrammatic illustration depicting a pair
of line segments initially registered;
Fig. 27b is a diagrammatic illustration depicting the line
2~ ~egments of Fig. 27a following least squares final
registration;
Figs. 28a, b and c are diagrammatic illustrations
deplcting separable convolution processes involving
application of row and column filters separately to an
array of data;
Fig. 29 is a diagrammatic illustration of registration
vectors M and R prior to alignment;
Fig. 30 is a diagrammatic illustration of a simplified
example of an offset in the alignment of the registration
I vectors M and R;
'fl 35 Fig. 31 is a diagrammatic illustration which depicts
differene splitting in the regisration vector alignment;
and
'
~'' .
. ~ ~ . . .
,~ , . . . .
: .
: , . .
Fig. 32 is a diagrammatic illustration depicting a
situation requiring operator seletion of the in-register
point in a splsit the difference registration.
Referring now to the drawings in more detail and
initially to Figs. 1-~, numeral 10 generally designates a
film registration machine constructed in accordance with a
preferred embodiment of the present invention. The
machine 10 has a rigid frame which is formed by a
plurality of interconnected square tubes 12. A
plurality of caster wheels 14 are connected with the lower
frame members 12 to permit the machine to be easily
moved. Extending forwardly from the frame of the machine
are brackets 16 on which a horizontal table 18 is
mounted. The table 18 supports digitizer tablet
assembly which is generally designated by numeral 19. A
digitizer tablet 20 rests on a transparent plate 22
forming the top of an enclosure 24 which is illuminated by
a light bulb 26 located within the enclosure and below the
digitizer tablet 20. Overlying the digitizer tablet
is a transparent plate 28 having a vacuum channel 29 and
three upwardly projecting alignment pins 30.
The digitizer tablet 20 is a conventional device which
registers and records locations selected by a
cooperating hand held cursor (not shown). When the cursor
is aligned with a selected location over the digitizer
tablet 20 and activated, the digital location of the
selected point is registered. Preferably, the cursor has
; 30 a re~ting place on a cradle, and the vacuum channel 29
is deactivated when the cursor is in place on its
cradle. However, when the cursor is removed from the
j cradle, the vacuum is automatically applied to channel 29
~! in order to hold plastic carrier sheets for the films down
on the plate 28, as will be described more fully.
,
A digital camera 32 is mounted in a fixed position on the
frame of the machine. The camera 32 is preferably a line
, ,
.
-12~ 3
scan CCD ~charge couple device) digital camera having a
stepping motor for causing the camera to linearly scan the
elements of the pictures which are recorded by the
camera. Preferably, the camera records 640 x 640 pixel
digital pictures, with each pixel being 13 microns
square. The step~ing motor for the camera is controlled
by a microprocessor.
The digital camera 32 is mounted on a pair of brackets 34
which are bolted or otherwise secured to a horizontal
mounting plate 36. The mounting plate is in turn
supported on the frame of the machine. The camera 32 is
carried on a bracket 38 which connects with a dovetail
40. The dovetail fits in a vertical dovetail yroove
formed in a block 42 which is connected with the
mounting brackets 34 by a pair of plates 44 and 46. An
adjustment screw 48 is threaded into the dovetail 40 and
carries a knob 50 to facilitate adjustment of the screw.
Due to the threaded connection between screw 48 and the
dovetail 40, turning of knob 50 causes the dovetail to
move up and down in the dovetail groove in order to raise
and lower the digital camera 32.
~' A movable chase 52 is carried on a positioning table
assembly formed by one table 54 which is restricted to
movement in the "x" direction and another table 56 which
is restricted to movement only in the "y" direction. The
x table 54 is moved by a drive screw 58 and is restricted
to linear movement by guide bearings 60. The drive screw
58 is turned by a reversible electric motor 62 which
is attached to a mounting plate 64 and which drives an
output shaft 66. A coupling 68 connects the output shaft
66 with the drive screw 58, and a bearing 70 supports the
drive screw for rotation. The drive screw 58 is threaded
¦ 35 through a nut 72 secured to the x table 54 such that
~ turning of the drive screw in opposite directions moves
f~', table 54 linearly in opposite directions.
,~,
'.'~'''
,
,- .
:. - ,
. .
' ~ - ' ` ... .
-13
The y tabl~ 56 is driven similarly with its motion
restricted to a direction perpendicular to the direction
of motion of the x table 54. A reversible electric motor
74 mounted on a plate 76 has an output shaft 78. Shaft 78
is coupled at 80 to a drive screw 82 which is
supported to rotate by a bearing 84. Screw 82 is threaded
through a nut 86 secured to the y table 56. Guide
bearings 88 restrict the y table 56 to linear movement.
The movable chase 52 includes a transparent plastic
plate 90 having three upstanding alignment pins 92 which
serve to properly locate the carrier sheets which are
placed on the chase. The plate 90 also has a vacuum
channel 94 for holding of the carrier sheets down on top
of the chase when vacuum is applied. Plate 90 is
provided with a pair of holes 96 which permit the carrier
sheets to be punched in a manner that will be explained in
more detail. A DC light bulb 98 is located immediately
below camera 32 in order to provide illumination during
recording of pictures.
Punching of the carrier sheets is effected by a punch
mechanism which is mounted on a C-shaped bracket 100. The
punch bracket 100 is suitably mounted on the frame at a
location below the camera mounting brackets 34. The
punch mechanism includes a pneumatic cylirder 102 which is
secured to the lower arm of bracket 100 and which has an
extendable and retractable rod 104. A spool 106 is
threaded onto the top end of the rod 104, and a punch 108
is detachably carried by the spool 106. The punch 108
has a head which can be fitted into a slot formed in the
spool in order to maintain the punch in position.
The punch 108 extends through a bushing 110 which is
carried by the upper arm of the bracket 100. A C-
frame 112 has its upper arm located above bracket 100 so
that the transparent plate 90 can be extended between
bracket 100 and the C-frame 112 during the punching
'
- ~ ' ,
-13-
The y table 56 is driven similarly with its motion
restricted to a direction perpendicular to the direction
of motion of the x table 54. A reversible electric motor
74 mounted on a plate 76 has an output shaft 78. Shaft 78
is coupled at 80 to a drive screw 82 which is
supported to rotate by a bearing 84. Screw 82 is threaded
through a nut 86 secured to the y table 56. Guide
bearings 88 restrict the y table 56 to linear movement.
The movable chase 52 includes a transparent plastic
plate 90 having three upstanding alignment pins 92 which
serve to properly locate the carrier sheets which are
placed on the chase. The plate 90 also has a vacuum
channel 94 for holding of the carrier sheets down on top
of the chase when vacuum is applied. Plate 90 is
provided with a pair of holes 96 which permit the carrier
sheets to be punched in a manner that will be explained in
more detail. A DC light bulb 98 is located immediately
below camera 32 in order to provide illumination during
', 20 recording of pictures.
'~, Punching of the carrier sheets is effected by a punch
mechanism which is mounted on a C-shaped bracket lO0. The
punch bracket 100 i8 suitably mounted on the frame at a
location below the camera mounting brackets 34. The
~ punch mechanism includes a pneumatic cylinder 102 which is
;~' secured to the lower arm of bracket 100 and which has an
~i extendable and retractable rod 104. A spool 106 is
threaded onto the top end of the rod 104, and a punch 108
i8 detachably carried by the spool 106. The punch 108
;, has a head which can be fitted into a slot farmed in the
spool in order to maintain the punch in position.
',
,' The punch 108 extends through a bushing 110 which is
~' 35 carried by the upper arm of the bracket lO0. A C-
frame 112 has its upper arm located above bracket 100 so
that ,the transparent plate 90 can be extended between
-'l bracket 100 and the C-frame 112 during the punching
", ~ . :,
. .~ , .
,~,. . . . .
': ~ ' ' , :
~ ' -
:: .
-14- 13~
operation, as best shown in Figs. 3 and 4. A die 114 is
carried on the C-Erame 112 and is aligned directly above
bushing 110 such that the top end of the punch 108 enters
sleeve 114 when the punch is extended as shown in Fig.
4. It should be noted that more than one punch can be
provided if desired.
Fig. 7 shows the pneumatic system which controls the
application of air and vacuum to the various components of
the machine. A suitable air supply 116 connects
through a solenoid valve 118 with the extend and retract
sides of the p;ù~ch cyl ~der 102. When valve 118 is in the
position shown in Fig. 7, the air supply 116 is connected
with the retract side of cylinder 102 and the cylinder is
retracted to the position shown in Fig. 3. However,
when the valve 118 is shifted, the air supply 116 connects
with the extend side of cylinder 102 and the cylinder is
extended to the position of Fig. 4 to punch one of the
film carrier sheets.
A suitable vacuum source 120 connects through a solenoid
valve 122 with the vacuum channels 29 and 94 for the
digitizer tablet assembly 19 and the movable chase 52.
When valve 122 i8 shifted from the position shown in Fig.
7, vacuum is applied to the vacuum channels in order
to hold down any carrier sheets that are then in place on
the digitizer tablet 20 or the movable chase 52. The air
supply 116 may also be connected with channels 29 and 94
through a solenoid valve 124. Valve 124 is normally in
the position of Fig. 7 and then disconnects the air
supply from the vacuum channels. However, when valve 124
is shifted, air under pressure is applied to the vacuum
channels to eject any carrier sheets that are in place on
the digitizer tablet or movable chase.
Fig. 8 is a simplified block diagram of the control
components used to control the registration process which
is carried out by the machine 10. A host computer 126
'
~':','
, ~ , . . .
.. .
-15- ~ 3 ~ 3
supervises the recording and the intermediate storage of
digital pictures recorded by the camera 32. The digital
picture data is transferred from the camera 32 into a high
speed array processor 128 which is a specialized computer
having the ability to quickly perform the necessary
numerical computations. A programmed microprocessor
serves as an intelliyent controller 130 which receives
commands from the host computer and controls through block
131 the drive motors 62 and 74 for the positioning tables
54 and 56. The intelligent controller 130 also
controls the air and vacuum through block 132 and receives
data from the digitizer 19 specifying the locations which
are selected thereon by the cursor.
Fig. 9 is a more detailed block diagram of the control
components of the machine. As shown, the host computer
126 controls the stepping motor (block 133) for the
digital camera 32. Digital image data from the camera is
transferred via an analog to digital electronics block 134
to the array processor 128. The array processor has a
memory 136 which function with a fast recall capability.
The machine 10 operates to register process color films
such as the four halftone color separations used in the
four color process which is commonly used in the
reproduction of high quality color photographs. The
operator of the machine first typically selects either the
cyan or the magenta process color films as a reference,
and the reference film is taped or otherwise mounted to a
clear unpunched polyester carrier sheet such as the
sheet 138 which is shown in the drawings in place on the
chase 52. The other three separation films are similarly
taped or mounted on unpunched polyester carrier sheets in
rough register with respect to the reference film when all
of the carrier sheets are arranged in alignment. The
purpose of the rough register is to achieve an initial
alignment of the films that is comfortably within the
detection range of the algorithm. Typically, the rough
,~
" -16- ~31~
register need only be done to within plus or minus 40
mils. Rotation of the line (vector) between selected
pictures is taken into account by the final registration
transformation previously described in the summary of the
invention. Rotational misregistration between
corresponding selected pictures is very small and can be
initially ignored. The least squares seyment matching
step does, however, also take rotational alignment into
account.
The operator then places the reference carrier over the
digitizer tablet 20 located at the picture selection
station. Two edges of the carrier sheet are positioned
against the three alignment pins 30, as shown in the
phantom view of the carrier sheet 138 in Fig. 1. The
operator then raises the cursor off of its cradle in order
to activate the vacuum channel 29 in plate 28, thereby
holding the carrier sheet 138 in place by suction.
The operator uses the cursor to select two spaced
; apart register points on the film which is carried on
~; sheet 138. Either or both o the register points can be
the approximate center of a reyister mark which is usually
in the form of a hairline cross located outside the
boundary of the picture. However, if register marks
are not present on the film or are present but considered
to be inaccurate, areas containing halftone dot detail can
be selected for one or both reyister points. Ordinarily,
areas of the picture which contain considerable
macroscopic edge detail are selected. When the first
register point 140 has been selected, the cursor is placed
at the first register point on the digitizer tablet 20,
j and the number one cursor button is depressed to record
;' the location of the first register point. The digitizer
tablet 20 then transmits the location to the host
computer. The second reyister point 142 is thereafter
selected and recorded in the host computer by aligning the
cursoe with it and depressing the number two botton on the
,`'1
,
, ~ . .
., . . :
:,. ~ . i ;
-17-
cursor.
After both register points 140 and 142 have been selected,
the operator returns the cursor to its cradle, thereby
releasing the vacuum at channel 29. The reference
carrier sheet 138 is then moved by the operator from the
digitizer tablet onto the movable chase 52. Two edges of
the carrier sheet 138 are positioned against the alignment
pins 92, as best shown in Fig. 1, and a foot switch or
another switch is activated to apply vacuum to the
vacuum channel 94. The vacuum thereafter holds the
carrier sheet 138 in place against the alignment pins
92. At this time, the movable chase 52 is in the
load/unload position shown in Fig. 1.
lS
The machine then begins automatic operation initiated by
the closing of a door on the carrier sheet 138 or by
activation of another switch. Under the control of the
intelligent controller 130, the positioning table drive
motors 62 and 74 are activated to move chase 52 until
the first register point 140 is centered immediately below
the camera 32. The camera records a digital picture of
the area of the film centered at the register point 140,
and the picture data are transferred to the host computer
126 and analyzed by the array processor 128 using high
speed algorithms which will be described in more detail.
The motors 62 and 74 are then activated again to align the
~econd register point 142 with the lens of the digital
camera 32. The digital camera records a picture
centered at point 142, and the data in the picture are
transferred to the host computer and analyzed by the array
processor 128. The chase 52 is then moved until the hole
96 near i~s right edge is centered above the punch 108.
The punch mechanism is activated by the intelligent
controller, and cylinder 102 is extended to punch a
register hole in the carrier sheet 138 for the reference
film. After the punch has been retracted, the chase is
-18~
shifted until the hole 96 ne~r its le~t edge is centered
above the punch, and the punch is then activated again to
punch a second register hole in the reference carrier
sheet 138. When the punching operation has been
completed, the movable chase 52 is returned to the
load/unload position shown in Fig. l, and the vacuum is
removed so that the reference carrier sheet 138 can be
removed by the operator (or automatically ejected if
desired). It should be noted that both of the register
holes can be punched at the same time by two different
punches if desired.
After the reference film has been removed from chase 52,
the carrier sheet for the second film is placed on the
chase with its edges against the alignment pins 92.
The vacuum channel 94 is then activated and automatic
operation of the machine is initiated. The chase 52 is
moved until the location on the second carrier sheet
; corresponding to point 140 is centered beneath the camera
32. The camera records a picture, transfers the
picture data to the host computer, and the data are
analyzed by the high speed array processor 128. The chase
is then moved to center a second point which corresponds
with the register point 142 beneath the camera 32.
Another picture is recorded and analyzed by the array
processor 128.
By using the algorithmic processes to be explained
~, hereinafter, computations are made based on the picture
data to provide the locations at which the second
carrier sheet must be punched in order to effect
registration of the second film with the reference film.
Based on these calculations, the chase 52 is properly
l positioned relative to punch 108 such that the two punched
;l 35 holes made in the second carrier sheet, when aligned
with the punched holes in the reference carrier sheet,
result in alignment between the second film and the
~¦ reference film. After these two register holes have been
, .
- . ................. .
,,~, ,
, "~
- -lg~ 3
punched in succession in the second carrier sheet, chase
52 is returned to the load/unload position, the vacuum is
released, and the second carrier sheet is removed by the
operator or ejected from the chase.
The carrier sheets which hold the third and fourth color
separation films are handled in the same manner as the
second carrier sheet. When all of the register holes have
been punched (two in each carrier sheet), the four carrier
sheets can be "laid up" on register pins with
assurance that the four color separation films are in
registration for final reproduction of the color
photograph. Because the films are initially only in rough
alignment, the picture detail recorded at e~ach register
point is somewhat out of registration but can be used
in the algorithmic process to achieve exact registration.
Fig. 10 is a flow chart which depicts the algorithmic
processes that are carried out by the machine 10 in order
,
to achieve registration of the four color separation
ilms. The screen ruling for the halftone dot detail is
initially specified (or the equivalent 150 line screen
~' ruling for register marks). A 150 line screen is
~l typically used for halftone pictures, although screen
;ii 25 Luling~ in the range of about 120 to 200 can be used
~; without placing undue strain (storage capacity and
computer time) on the computer code implementation that
has been developed.
~, 30 The digital camera calibration may be 1:1, althoughother calibrations are possible. The camera 32 operates
with square 13 micron pixels (about .51 mils). The raw
data picture recorded by the camera at each selected
~;l register point is approximately 640 x 640 pixels and is
, 35 centrally located in the field of view of the camera
-i in order to achieve maximum image quality.
, ~
, The raw data image that is recorded by the camera 32 at
,''.i
'',-` ' ~ ' ~ ' ~ '
t,~, ' ' ' "' '
~' ' -, ~ '
, ~ - ` ~ ,- ",
~ -20- ~31~
each register point on eacll halftone separation sheet is a
gray level picture which is optimally thresholded to a
binary picture. The gray level picture has different
shades of gray ranging from 0 (black) to 255 (white).
Optimal thresholding reduces this raw data gray level
picture to a two level (binary) picture having two tones,
namely black (tone one) and white (tone zero). The black
tone is assigned to all tones less than the threshold
while white represents tones greater than or equal to the
threshold.
The technique for performing the optimal thresholding is
well known (see Digital Image Processing by Gonzales and
Wintz, 1977, p. 327). First, an estimate for the
threshold is obtained by averaging the maximum and
minimum gray tones in the raw data picture. This initial
threshold is used to separate the tones into black and
white groups with numbers above or equal to the initial
threshold considered white and numbers below the initial
threshold considered black. The average white tone
and the average black tone is then found. By averaging
the average black tone and the average white tone, the
optimum threshold is found. A final thresholding is
performed using the optimum threshold determined by this
~, 25 procedure. The thresholding is performed row by row
~i on the pixels in the raw data picture.
Thresholding in this manner eliminates gray scale
variations that may be introduced by the digital camera
electronics and/or the camera light source. In
accordance with the edge based reyistration technique
utilized in the present invention, the macroscopic edge
detection operates on a scale that is greater than the
fine detail of gray level transitions at individual
halftone dot edges. Therefore, the weakness of the
thresholding with respect to the resolution of individual
dot edge pixels (an edge pixel may be partly on and partly
off of a camera sensor element) does not adversely affect
.
,.: ~ ~ . , : .
,.. ~, ~ ,
-~, , . :
, . : , .
:
~ 21- 1 3 ~
the registration result to a significant extent. The
binary detail of the halftone pictures is extracted by the
thresholding and is thereafter independent of gray level
fluctuations.
In accordance with the present invention, macroscopic
edges of the digital pictures are detected and reyistered
using special edge based registration techniques. In
viewing a picture or any graphic image, an edge contour
traces the occurrences of intensity changes in the
picture. Such a contour is depicted in Fig. lla where
there is a marked change in intensity from dark to light
on opposite sides of the edge 144. If the edge contour is
detected only at discrete points, each edge point
(referred to as an edgel) reprecents a local intensity
change with an associated edge orientation or direction.
The edge direction is perpendicular to the maximum rate of
intensity change at each edgel. The edge direction
depends upon whether the intensity change perpendicular to
the edge is from light to dark or dark to light in a
sense chosen by convention. Fig.llb depicts the same edge
~hown in Fig. lla but detected by a plurality of edgels
146. The directional arrows 148 point in the direction of
the edge as determined by the direction of the intensity
change considered in accordance with the convention
which determines the direction in which the arrows point.
Edge detectors may be classified in two broad classes:
gradient operators and second derivative operators. Fig
12a depicts a step edge 148 where the intensity change
takes on the shape of a step. Figs. 12b and 12c
respectively illustrate the responses of the step edge 148
when operated on by a second derivative operator and a
gradient operator (convolution of the edge detector filter
with the edge). The gradient operator (Fig. 12c)
provides a broad peak 150 at the location of the step
edge, and the gradient operator thus requires a thinning
- or maximum detection step that degrades the resolution.
. . .. . .. .. .
-22- ~31~3
On the other hand, the second derivative operator (Fig.
12b) responds with a zero crossing 152 at the location of
the step edge, and the accuracy of location by
interpolation depends on the signal to noise ratio. In
addition, gradient operators detect edges in only one
direction, and it is often necessary to carry out multiple
convolutions with different operators in order to locate
all edges in all directions.
The techniques employed in the present invention
include the use of a second derivative operator known as
the Laplacian of a Gaussian (LOG) operator first suggested
by
D. Marr and E. Hildreth in a paper entitled "Theory of
Edge Detection", presented in the Proceedings of the
Royal Society of London in 1980 (pages 187-217). The LOG
edge operator is written as:
LOG = .5~2-r2/G`2)exp(-r2/2 6~2), (1)
where C-is the width parameter of the operator (the
space or decay constant of the Gaussian) and is the two
dimensional radius of the operator r= JX2+Y2)- The LOG
edge detector is rotationally invariant and requires only
one convolution to enable detection of all edges in all
directions. At a zero crossing, the edge direction
perpendicular to the maximum slope of the zero crossing
response is determined by examining a 3 x 3 pixel window
(local neighborhood) centered at the pixel containing the
zero crossing.
Fig. 13a depicts the profile of the Gaussian and the width
parameter 6-, while Fig. 13b shows the LOG profile.
Fig. 13c is a plan view of the LOG operator and shows the
width w of the excitatory (positive) region of the
operator as well as the truncation of the operator to
a size of 3w. Because the LOG has infinite spatial
extent, it must be truncated to be useful for practical
calculations. Setting the factor
- .~
~' ,
..~'
,
. '' ~ ' . ' "
:. .. .
'~ . .
.~. . -
-23-
.5~2-( r2)/G~2 lequal to zero yields w=2 ~ ~ w is the
diameter or 2r r 2 ~x2~y2). Thus, truncating the size of
the LOG to 3w truncates it to approximately 8.5 6- .
Since 99.7~ of the area under a one dimensional Gaussian
lies between plus and minus three standard deviations
from the mean, truncating the LOG operator to 3w or 8.5C-
introduces virtually no error. In actual practice, the
LOG is adjusted slightly so that the response to a uniform
stimulus is exactly zero. Moreover, the 3w size is in
actuality larger than is necessary for accurate
results, and its use consumes valuable computer time that
is not necessary. Consequently, a LOG size of 21r~'is
selected for use, and the odd integer nearest to 2~r6J
becomes the discrete size in pixels of a symmetric (odd
mask size), square, gridded convolution filter mask M
that is evaluated (at each discretized radius) from the
LOG formula (1). The adjustment to zero uniform mask
response is accomplished by modifying each po.sitive
element in the original mask M by a factor 1 -
-~ 20 ~um/(positive sum), where the term "positive sum" is
the sum of positive elements in the original mask M and
the term ~sum" is the original sum of all mask elements.
The mask M so corrected has an exactly zero sum.
; 25 The principal virtue of the LOG operator as applied to
halftone image registration is that by properly adjusting
the width w (or 6~), only the desired global or
macroscopic edges will be detected, and the edges around
individual halftone dots will not be detected. A G~that
is too small would detect individual halftone dot
edges, and this would destroy image registration because
individual halftone dots on two different color
separations of the same image do not overlay or register
with one another. In fact, the superimposed dots of all
of the color separations form a rosette pattern. The
visual or macroscopic edges detected by the LOG operator
with a suitably large C~register in much the same way as
edge detail is visually aligned in manual registration
,
"~,
~, ,
: :
.
~ ~.
-24- ~31~3
procedures performed by skilled personnel.
The zero crossing contours of features having a width
smaller than w are displaced and may become fused with the
5 zero crossing contours o~ nearby features. When the
~eature width is d (the width or diameter of a halftone
dot), the fusion of zero crossing contours provides the
mechanism for detecting only macroscopic edges and not
individual dot edges. This fusion phenomenon also
10 provides a simple method for initially estimating the
proper 6-- to use for each screen ruling. Fig. 14a
illustrates LOG profile superimposed on the profile of a
bright feature having a width d less than w. Fig. 14b
shows the LOG convolution and illustrat~?s that the zero
15 crossings 154 of the response are displaced from the
edges of the feature by a distance of (w-d)/2.
Fig. 15 illustrates the minimum detectable configuration
of halftone dots, where the inner dot edges are displaced
20 by a dot width d to fuse with the dot edges at the
zero crossing of the response. Setting the displacement
(w-d)/2 equal to d yields
w=3d=3(2R)=6D/~ :52 ~ 6--,(2)
where R is the radius of a circular dot and D is the
dimension of the pixel containing the dot. (The area of
the square pixel D2 is equated with the area of the dot
-6R2). Solving equation (2) for 6~and evaluating ~ at
30 150 line screen ruling (D=1/150 inch) yields
6--=(3d/~)(1000/.5118) ~ 16 pixels, (3)
where the camera operates with 13 micron pixels at 1:1 or
35 .5118 mils per pixel. Since 6-- varies linearly with
the screen ruling, ~ can be evaluated for screen ruling
other than 150 by using proportional scaling from the
ubiquitous 150 line screen value:
~ 25-
~screen ruling = (150/screen rullng) ( ~ 50 ruling) (4)
An elementary Fourier analysis can provide both a
- decimation factor which should be used and also a Eairly
precise value for 6~ at 150 line screen ruling. By
determining an upper limit, a value for is obtained that
is as large as possible in the direction away from
detecting individual dot edges. A lower limit for 6-is of
lesser utility in actual practice.
First, the Gaussian of the LOG exp (-r2/2 ~2) and its
Fourier transform exp (- ~2R2/2) are considered. By the
Parseval Theorem, the original LOG and the transformed
waveform have equal energy. A good approximation of equal
energy can be obtained by equating the aryuments of
the two exponentials and evaluating the radius parameter r
at 6- . This yields the result
C~ =l/R
and gives the desired relationship between the spatial
frequency R and 6-. Since decimation is a sampling
problem, sampling theory can be applied. Applying the
Whittaker-Shannon Sampling Theorem, if the sampling rate
or declmation factor is ~ , then the spatial frequency R
;25 must be no les.s than the R value at the Nyquist limit,
namely,
l/R=2~=6~ (6)
At and above the Nyquist frequency R, aliasing error
~'due to the coarseness of sampling can be safely ignored.
The second equality in equation (6) is taken from equation
(5). Equation (6) i8 the upper limit for G~'since l/R can
not exceed 2~ . Extracting from equation (3) the 16
pixel figure for 150 line screen ruling, the value of ~ is
8. Clearly, the desired integral decimation factor is
closer to 8 than to 7 or 6.
:. ,
.
. ~ , . ' :
.
:~ . , .
-26- ~ 3 ~ 3
From equation ~6), a rather precise value for 6~can be
determined, taking into account dimensional units and the
fact that the pixel size is .5118 mils/pixel:
(.5/.5118 mil/pixel)(6~mil)/~=integer=8 (7)
Canceling the mil units in equation (7) yields: G~150
line screen ruling _ 16.38 pixels. (8)
It has been verified by numerical experimentation that
10 significant deviation from the nearly optimum value of
given by equation (8) leads to edge degradation. In
practice, the 150 line ~~ can be applied to smaller screen
rulings down to about 120 with good results. However, the
150 line 6- cannot be applied to rulings above 150 without
15 creating inaccuracies. In the case of screen rulings
; above 150, the 6' given by equation (4) can be used with
good results. This reaffirms that excess resolution is
not particularly harmful but a lack of resolution is quite
harmful to accuracy. It is also desirable to apply the
150 line ~' to smaller screen rulings because the 150
line 6- resolves fine non-halftone detail (register or
fiducial marks, solid type line or line art) that may be ?
mixed with halftone detail better than a 6~calculated for
the small screen ruling. However, this strategy should
25 not be pushed too far because at some point, too many
edges in the smaller screen rulings would be detected and
the method would be slowed down considerably. The 150
j line ~~ has been empirically determined to be the optimum
central value in the treatment of different rulings.
The LOG operator of equation (1) is realized by a finite,
square gridded mask M having an odd size:
~ mask size=NODD(21r6V), (8a)
j 35 where NODD is the nearest odd integer. Using the C~'
1 defined by equation (8) gives a nominal mask size of 103 x
¦ 103 with 150 line halftone screen, with symmetric
¦ dimensionality about the central polnt. The mask is large
!
~r~
",: . ~, ! ' ; '
: , ' , '
', ' ' ' ' - ' ~':
-27-
~L31~3
enouyh to render the æero sum mask correction sufficiently
small. The zero sum mask correction modifies each
positive element in the original mask by a factor 1 -
sum/positive sum, where "positive sum" is the sum of
positive elements in the original mask and "sum" is
the original sum of all mask elements. The corrected mask
has æero sum over all elements so that the mask responds
with zero value to a uniform picture.
The filter mask M is invariant to rotation by 180
degrees, and each value of the decimated convolution is
simply the dot product of the mask M at the desired
location and the corresponding (same size as M) data block
of the binary picture P:
M dot P(block) (9)
The dot implies the dot product as if each array M and P
(block) were a vector in concatenated columns. Fig. 16
depicts how all of the decimated convolution values
are generated by moving the 103 x 103 pixel mask M over
the picture P in increments of 8 pixels along both of the
mutually perpendicular i and j directions. Since a
partial convolution is not allowed, only the convolution
values inside of the dotted lines 156 in Fig. 16
result. Using a mask of 103 x 103 pixels with a picture
size of 640 x 640 pixels provides a decimated convolution
which fills an array having a size of N x N, where N = 1 +
NEAREST INTEGER to (640 - 103)/8 = 68. Thus, the
decimated convolution is an array of 68 x 68 pixels
containing tones that vary between positive and neyative
values.
~- When using second derivative operators such as the LOG,
edges are located by determining the positions where
the convolution result crosses zero and changes sign. For
some applications, the convolved lmage can be scanned
; horizontally in one dimension for two adjacent pixels of
,~
,. ;
~' . , ' .
~: ,
" .
, : :
- :
-28-
opposite sign or for three adjacent pixels, the middle of
which is zero and the other two of which have opposite
signs. However, in two dimensions, a more sophisticated
approach is necessary in order to assure that the detected
zero crossing contours preserve the size and shape of
the regions of opposite sign they bound and also to
prevent anomalies such as the creation of spurious
edges. In accordance with the present invention, an
algorithm known as the U.S.C. predicate is applied to each
3 x 3 window in the 68 x 68 convolution array that
results from application of the LOG in the manner
previously described.
The U.S.C. predicate was developed at the University of
Southern California by A. Huertas and D. King and has
been continually refined and improved in recent years.
The U.S.C. predicate is a predicate based algorithm which
; provides a set of rules for recognizing a finite number of
possible convolution siyn and magnitude patterns that
correspond to definite predictions for the location
and direction of the edges at zero crossings in the
convolution. Actually, the U.S.C. predicate is a set of
11 individual predicates or logic elements that each
corresponds with a certain pattern of signs and relative
i i
magnitudes o the convolution response in order to
identify one or more edye locations and directions.
',
The U.S.C. predicate is applied by centeriny a 3 x 3 pixel
window successively at each pixel in the convolution
array output. Selected algebraic signs and relative
magnitudes oE the convolution output values in each 3 x 3
window are inspected for a match to one of eleven
allowable zero crossing predicates (or templates). If a 3
x 3 window in the filtered image matches one of the
predicates, edge locations and edge directions are
marked at the appropriate pixels. It should be noted that
a predicate may yield more than one edge location (with
l direction). If there is no match in the window, no edge
~:'
~ v~
; . :
: : , ; ,.' : , . ' '' . : ,
- . , ~ .
I ' ' ' ' .
- .
, . .. . . .
'' ' . ' ~ ' ' ' . ' ~ ' .
-29-
131~3
is located there. rrhe eleven predicates are specifically
constructed to preserve the topology of the signed regions
and prevent detection of extraneous edges. Since the
predicate templates explicitly model the signs of the
pixel values in the 3 x 3 windows, they also constrain
each edge orientation to one of eight quantized directions
which are shown in Fig. 17 by the directional lines
labeled 1-8 and which are offset from one another by 45
progressing counterclockwise.
The U.S.C. detection algorithm is known to those skilled
in the art of edge detection, and its manner of
application in the present invention is described
specifically by the FORTRAN computer program listing which
is identified as Appendix A to this application. In
this listing, each call to subroutine E3PSCX initiates
examination of the predicate matches for a window centered
at coordinates j2, i2 in the convolution response array
PSS (j,i). The nine window locations are identified by
the letters a-i from top to bottom and left to
right. Subroutine E3MEX marks and stores the detected
edge locations and edge direction numbers (numbered as
shown in Fig~ 17).
The edges which are detected by application of the
U.S.C. predicate algorithm lie on pixels of the reduced
resolution (decimated) convolution. In order to determine
the edge locations to the nearest full resolution pixel,
it is necessary to utilize interpolation techniques. The
interpolation method employed in the present invention
involves erection of the interpolation grid shown in Fig.
- 18 about each initial edge location in the reduced
resolution response data array Rd. The grid spacing is
1/8 that between the elements in array Rd. There are thus
289 (17 x 17) potential fine grid point locations for
the full resolution edge position (to the nearest grid
point).
. ~,
,.
, s:
;1-
~r
. :,
.~ ' , .
.
.
~ ~30- 13119~3
It is possible to interpolate a response for each of the
289 grid points and apply the USC predicate to find all of
the full resolution edge points in the interpolation
cell. However, this procedure is unduly time consuming,
and a sampling approximation is thus made, namely, for
each initial edge location, only one interpolated edge
position is chosen. The choice of interpolated edge
position is that location of the 289 locations that
exhibits the minimum interpolated response magnitude.
This choice has the virtue that the point chosen is
indeed a zero crossing or edge position. The location of
this edge position, however, has a certain
unpredictability about where it will occur. In practice,
this unpredictability produces no known degradation of the
final registration results.
The interpolation method is a well known general formula
~see Powell, "Approximation Theory and Methods", 1981,
Chapter 19) which is specialized to restrict the
interpolation offset from a central data point to the
de9ired point. The center-surround data scheme evokes
maximum accuracy from the method. A 9 x 9 interpolation
data grid achieves accuracy from the bicubic spline
interpolation to the level of several parts per
thousand. Another technique used to further improve
accuracy is the moveable interpolation data center. The
accuracy of the interpolation is order h3, where h
i represents the size of the interpolation offset (a number
between 0 and 1 in distance divided by the grid
spacing). If the magnitude of either of the 2-
dimensional interpolation offsets dx, dy exceeds 1/2, then
the central data point can be shifted to a neighboring
point and a corresponding new offset can be taken from the
moved data center to the desired point, that is less than
~, 35 or equal to 1/2 in magnitude- For example in one
dimension, an offset of ~ of ~ =.75 from central data
point i would be replaced by a new offset (a complementary
offset) of -(1 - .75) = -.25 to the left of new data
,..... .... . . . . . .
.
. . :; . . . ~ . ~ :
: . . : :
~, ~ , . . -
. . .
~ -31-
~31~L~63
center i ~ 1.
The specialized interpolation formula is
4 4
(i Yj, i+dxi)= ~ ~ Q (dxi)A n(dyi)Rd(i+n~i+m) (10)
m=-4 n=-4
where R is the interpolated response, Rd is the
interpolation response data, and dxi dyj are the
interpolation offsets (~- 1/2 in magnitude). The cardinal
functions Q~, ~ of the interpolation are linear
combinations of the cubic B splines
15B~ P)~ P~
-~t(~- ~p~3)~ 4)~3
where ~p = p = 0, +-1, +-2,... are the knots of the
piecewise polynominal, is an illustrative argument,
and the truncated cubed differences in the spline formula
are
(6'~ g~ (12)
: and
~ ~)3 ~ O ~r 6 - ~ C O (13)
The cardinal functions are
Qm~dxi)= ~ cpmsp(dxi)
p=_~ (14)
.
and
n(dyj)= ~ CpnBp(dyj)
p=-~ (15)
, .
,
-
32~
with weighting coef~icients ~iven by
1~ -2-~
( - ~r ~ ( ~ -2) (16)
and
~ -2 -~
C ~ 3 -2) (17)
The infinite sums in the cardinal functions have only a
finite number of non-zero terms that are determined by
using the fact that the B spline is zero outside of the
end points between which it is defined. In actual
practice, the interpolation coefficients in equation (10)
are computed and stored once for each of the 289 grid
points since the coefficients are the same for each
edge interpolation.
Due to the intrinsic shape of the LOG operator, the
location of a zero crossing of the LOG convolution is not
the true edge location except in the case of a perfect
step edge. The shift in position from the zero crossing
to the true edge location is the operator edge bias which
must be compensated for to accurately locate the true edge
position. For a perfect edge, the convolution response is
a symmetrical doublet with zero crossing at the center
of the response ~zero edge bias). The simplest example of
an edge bias is the response to a spike. The response has
the same shape as the LOG itself with zero crossings
displayed out to the sides of the LOG. This case is
illustrated by Fig. 14a with the feature width d going
to zero to approximate a æpike. The LOG convolution of
the spike has the same appearance as the LOG (see Fig.
13b).
:,
Because the operator edge bias can vary between
pictures that are to be registered, it must be corrected
by computing the true edge locations rather than tJ-e zero
crossings. In accordance with the present invention, a
,
. . .
.- ~: : . ,
.: ~ '~ . - , ' .
. . : , - : .
,: . . . '
.
:: , ~ .. . ~ , . .
~ -33- ~31~3
simple model edge response is used to facilitate
prediction of the true edge locations. The model edge i~
shown in Fig. 19 and comprises a step having a height d in
the y coordinate direction with a jump discontinuity k2 -
S kl in the y derivative with respect to x across thestep. If k2 - kl = 0, the step is a perfect step and the
edge bias is zero. Using integration by parts, the model
convolution response to the model edge is
1~ R- ~G,'(x~ (x~ (18)
where x is the observation coordinate and t is the true
edge location to be found. The function G (u~ = exp (-
u2/2G'2)
is the one dimensional Gaussian. Evaluating equation (18)
across the jump discontinuity yields
R=[-d(x-t)/c~2+ ~k~ exp[-(x-t)2/2 ~2] (19)
where ~k = k2-kl. By setting R=0 in equation (19), the
relationship between k and can be obtained, namely
xz-t= ~2~k/d (20)
where xz is the zero crossing edge location (including
bias).
Forming the ratio of equation (19) at x = xl and
x = x2, where xl and x2 are on opposite sides of xz,
introducing the term ;~= xz - t, and solving for
yields:
_ Q nlRl(x2-xz)/R2(xl-xz)l+~xl-xz)2-(x2-x~)2 (21)
X 2--X l
where Rl and R2 are interpolated responses at points 1 and
2. Thus, by computing ~ from known quantities, the true
edge position is:
j
:~ .
'' ' :' ' -
. .
~: '
~ 34- ~ 31~3
t=xz- ~ (22
In order to use the one dimensional model of equations
(21) and (22), the single dimension must lie along the
line connecting xl, Yl~ xO, yO, and x2, Y2, where xO,yO is
the interpolated edge location and xl, Yl lies at a
distance 6~/2 from xO, yO in the direction 90 clockwise
from the edge direction. Then, x2, Y2 is the displacement
opposite to the "1" displacement from xO, yO. In the
rotated frame of the response line, xz=O and the prime
(rotated) frame coordinates of the 1, 2 points are
Xl=(Xl-X0)CS~ + (yl-yO)sin ~ (23)
and
X~2 =-xl (24)
~ '
- where the angle ~ is positive clockwise in the unprime
frame of x positive right and y positive down. Fig. 20
pictorally depicts this geometry. From equation
~21), ;~ evaluated in prime frame coordinates is given by
~ ~2~2xl ,Q n¦Rl/R2¦ (25)
and finally, from equation (22) and the conventional
transformation eguations back to the unprime coordinate
frame, the true edge position is
:.
xtrue = -~cosEP+ xo (26)
and
Ytrue = -~sin~ + yo (27)
The normal to the predicate edge direction that enters the
calculation of equation (25) is varied by 45 in both
, ~
.
,:
-35-
~ 31~3
directions from the nominal direction to determine whether
or not an improvement results. The improvement
constitutes a larger ¦R1¦ + ¦R2¦ which is proportional to
the absolute slope of the zero crossing. Fig. 21
qualitatively illustrates how a 45 shift in direction
can place Rl and R2 "more squarely" in the dominant
response region where the slope of the zero crossing is
maximum. While the improved edge direction is used to
compute the edge bias correction, the original edge
direction is used to create line segments in a manner
that will be fully described. The reason is that the
original edge directions relate to the model connectively
of the edges produced from the U.S.C. predicate, and this
connectivity should not be altered by modifying edge
directions. However, there is no reason not to
compute better responses from the modified edge directions
since the U.S.C. predicate does not guarantee that the
best responses will be perpendicular to the predicate edge
directions.
The interpolated responses are screened to assure that
; their signs are opposite ~the edge is rejected if they are
not). A screening is also performed on the magnitude
of ~ determined from equation (25). ;~ must satisfy the
~ 2S equation
.'
1~1 < ~ c- (28)
Since w/2 = ~ ~is the largest possible edge bias
magnitude. A further screening is performed Oll the
absolute value step heiyht d deduced from equations (19),
~20) and ~25) with x evaluated at response point 1.
¦d¦=52¦Rl¦exp[(xl+j~2/2~-2]/¦xi¦ (29)
To determine the threshold of d above which an edge
should be rejected, typically extreme parameter values are
used to evaluate equation (29), such as
!
' ' ' ~ ' ~
-36-
1 3 ~ 3
¦d¦=800G'exp[[l/2~ ~2]2/2~xl04 (30)
Thus, if ¦d¦ exceeds a threshold of 105 the edge is
rejected, and this technique eliminates spurious and very
weak edges.
A final screening is performed on each edge. An
acceptable edge must correspond to either a positive
maximum or negative minimum in the first derivative
response. All other edges should be eliminated. The
condition for an acceptable edge is therefore
sign(fl)sign(f3)<0, (31
where fl is the first derivative response and f3 is
the third derivative response. The third derivative sign
is simply obtained from the edge polarity convention,
namely
~.
~ 20 sign(f3)=-(sign of response 1 in the edge bias canputation).(32)
;
The first derivative sign requires that the decimated
convolution of the picture data with the Gaussian factor
of the LOG be computed. This convolution is precisely
analogous to the decimated LOG convolution previously
described. The first derivative is the directional
derivative in the direction of the clockwise normal to the
edge direction, namely
fl=-fXsin~ +fy coser (33)
where ~ is the edge direction angle. To compute the x and
y direction derivatives, the location of each edge in the
Gaussian convolution is determined and a Lagrange
polynomial interpolation is performed for each
i derivative based on the data points shown in Fig. 22.
With p signifying either x or y direction data and
signifying either x or y, the derivatives fx and fy can be
,, .
., ,
.:
computed from the interpolation formula
3~ P~ - ~P3
~,2
~ p~ (34)
~ p~ 3- P~2l
In equation (34) ~ is the fractional distance (unit
spacing) to the desired derivative evaluation point in the
Gaussian convolution. Thus, equation (31) can be computed
from equations (32)-(34) to perform the final screening on
each edge.
Linear segments are produced from the edges that result
from the foregoiny procedure, and the segments are then
fit to the true edge positions. The steps involved in
segment production include the conventional steps of
linking the edges and tracing the linked edges in the
manner described in Nevatia and Babu, "Linear Feature
Extraction and Description", Computer Graphics and Image
Processing, no. 13, pp. 257-269 (1980). The step of
linking edges involves using the connectivity and edge
directions of the initial edges (reduced resolution edges)
to determine the precursors and successors of each edge in
connection to its neighbor edges. In the tracing of
linked edges, all distinct chains of connected edges are
produced by tracing along the linked edge data (each
edge points to certain of its neighbors). The allowed
angle transition in linking is 45, rather than the 30
stated in the above referenced paper.
The segments are fit to the positions of the edges in
the distinct chains that result from tracing. A fitting
tolerance of .75 pixel is employed (no edye represented by
~I the segment deviates in perpendicular distance to the
segment line by a distance greater than this .75 pixel
fitting tolerance). The fitting technique involves
first creating 2-segments (segments connecting two
neighboring edges) and then combining the 2-segments into
~, longer segments by adding other 2-segments until the
, .~
,
:'
, .
' ~ . ' .' ' '
,. ~ ,' ~ , '. -
" ~ .
_ -38- 131~
fitting tolerance is exceeded. The last "successful" 2-
segment forms the terminus of the longer segment, and a
new segment begins with the failed 2-segment.
The result of the segment fitting is a list of segment
endpoint coordinates for each segment in both of the
reference and moved pictures. Before these data are used,
they are transformed to segrnent center, segment length and
segment angle data. The segment angle i5 detersnined with
respect to a coordinate system in which the x
coordinate is positive to the right and the y coordinate
is positive down. The segment angle is positive in a
clockwise direction from the x axis and lies between 0
and ~ radians.
Seyment registration is next carried out to predict the
final registration offset. Segment registration proceeds
in two stages, namely, initial segment registration accom-
plished by the parameter space method and final
registration utilizing least squares techniques. The
result of the final registration provides the offsets
between the two pictures to be registered and, following
~' the vector alignment step, causes the chase to be properly
positioned for punchiny of the moved picture in the
locations necessary for registration with the
reference picture.
Initial registration takes advantage of the robust nature
of the parameter space method (PSM) and the fact that it
does not require all segments in one picture to
exactly correspond with the segments in the other
picture. The PSM matches similar but not necessary
i identical pictures and it allows matching of segments
having different lengths and slightly different angular
orientations. Each picture has a list of segments
'~ each characterized by length, angle and center
'~1
coordinates. The parameter space in the PSM is an
j accumulator array in the coordinates of the desired
,~
,.
,,
': :
~ , . ' . ' .
:
-
131 ~ 9~3
offset. For each matching pair of segments (one from each
list), the diference between segment centers defines the
central offset parameter in parameter space about which a
rectangular painting window is erected.
As shown in Fig. 23, the parameter space in the PSM is the
accumulator array P in the coordinates of the initial
picture registration offset (the offset by which the moved
picture can be moved into initial registration with the
reference picture). The grid spacing in P is not
illustrated in Fig. 23 but is one pixel of the original
digital pictures for which segments were produced. A
typical size for P is
240 x 240 pixels, which allows the pictures to be
misregistered by slightly more than ~ 5 rows of 150
line screen halftone dots.
Each pair of segments (one from each picture) is tested to
determine if the segments match closely enough in angle.
If they do, the pixels in P within a rectangular
window centered at the parameter of the distance between
segment centers accumulate a "score" (P-~ P + score) for
that pair. Once all segment pairs have contributed, the
parameter space has a peak at a location referred to as
the initial offset prediction. Fig. 24 shows
qualitatively how the segment pair "score painting n
windows overlap to produce a peak at coordinate position
xoff, yOff. The peaks in P tend to be rather rough or
"spiked", as shown in Fig. 25a. Hence, the P score space
is smoothed with a Gaussian smoothing convolution
before the peak is located. After smoothing, the profile
is typically as shown in Fig. 25b and has a smoother peak
1S6.
Considered in more detail, the PSM can be applied to
an exemplary pair of segments that may possibly contribute
to P. The two segments have lengths 1~ and Q2, angles ~ ,
and er2 and center coordinates x~c~ YlC and X2C~ Y2C- The
; ....... ,
, .
. . ~
.- ~ . , :
;
13~9~3
subscript 1 identifies the seyment of the reference
picture and subscript 2 identifies the segment of the
moved picture.
The first test applied to the segment pair is the
condition
min=MinimUm ~ Q~ ~ Q2 3 > QtOQ
where ~toQ = 8; otherwise the segment pair does not
contribute. Q~OQ can he regarded as an information content
parameter. The value 8 represents the typical distance
between two sampled edges from which the segments were
constructed. Such a distance is clearly a physically
reasonable minimum acceptable amount of information
for any segment.
The second and final test applied to the segment pair is
the angle acceptance threshold test. The segment pair is
accepted if the segment absolute angle difference is
less than or equal to a threshold:
~ threshold = Arctan[c/QI)+Arctan[c/~ J
2) (36)
The parameter c is a pixel displacement at each segment
end and has been empirically determined to be adequate at
c = 2.2. Both segments must pass the physically
reasonable condition (36), which is more restrictive than
a simple constant threshold.
Becaùse the convention is reference = moved plus offset,
the offset to the center of the rectangular score painting
window for the segment pair is given by the following
difference between the segment centers:
:,
xi=Nint ( XiC-x2c )
'~
",,~ ' ,
: ' ' , ` "
-41-
and
yi=Nint(ylc-y2c)~ (38)
where Nint signifies to the nearest integer. The
rectangular score painting window centered at the
coordinates given by eguation (37) and (38) in P is a
rectangle of length L given by
L = Ql + Q2
and of constant width W given by
~1=3. (40)
The angle ~ of the window is the angle of the long axis
; through the window center. ~ should be closer to the
angle of the longest segment, hence ~is taken as a
segment length weighted angle
~ =(QI~I +Q2E~2)/(Q~+Q2) (41)
A special case can occur when one of the segment angles is
near pl and the other angle is near zero. In this case,
the angle near pi is converted to a small negative angle
by subtracting pi prior to using equation (41).
Actually, this special case conversion is accomplished
before testing the angle difference in equation (36) to
avoid rejection of valid (special case) matches.
For each grid point of the accumulator P that lies
inside the window, P at that grid point is accumulated by
adding the score multiplied by a trapezoidal score profile
factor that is the overlap factor between segments. This
segment overlap factor is zero at the r~ctangle ends and
ramps up linearly to $ over a distance ~min in from,
both rectangle ends. The profile factor is thus the
constant 1 only over a central region of the rectangular
window of length MAX(~, Q 2)- Qmin. The total window
, ,
-: ,
.- : .
-42- 1~119~3
length is thus Qmax~ Ymin+2 Qmin orQ ~;~Qmax= ~I+ Q2 as in
equation (39). An empirically determined score that has
been found to yield good quality registrations is the
following:
score = (1 + lmin/Q~o~)
(42)
where Qmax is the maximum of Q~ and Q2. The rationale
behind the score given by equation (42) is that
represents a purely democratic score without bias and the
factor ~min/lmaX biases the base score of ~ in favor of
segments that are more closely similar in length (the
length ratio, however, is not biased toward either longer
or shorter segment pairs). Finally, the squaring of
the score improves the signal to noise ratio in the score
or accumulator space.
!,~j .
ii The result when all segment pairs have contributed is
~¦ 20 ready for smoothing. The smoothing is accomplished by
a convolution in which the center of a 7x7 mask S is
passed over the accumulator P in steps of one pixel in
both directions. The result of the convolution is S dot
WINDOW DATA where WINDOW DATA i9 the corresponding 7x7
array of P data. The accumulator location at which
the peak of the smoothing convolution occurs is the
initial offset that moves the moved picture into initial
registration with the reference picture. The mask S is
~i simply a Gaussian exp [(_X2 + y2)/26~0 evaluated at the
discrete xi, yj location of the mask. A value of the
smoothing sigma that yields very good results is
:::
~O - smoothing sigma ~ 1.5.
: ~ :
Th- purpose of the final least squares registration
~tage is to correct the initial segment registration by a
small amount (a few mils or less) to compensate for
possible size differences between the two pictures (not
. ~ ,
r~
~.
~43~ ~31~3
necessarily wliform size diEferences or magnification
differences). When size differences are not present, the
least squares correction is small enough to ignore,
although it even then may represent an improvement over
the initial segment registration.
Compensation for size differences may be termed "splitting
the difference". For example, Fig. 26a shows a "blob" of
detail 158 in one color along with a similarly shaped
"blob" 160 in another color which is smaller than blob
158. The blobs 158 and 160 are incorrectly registered
with one contour of the smaller blob 160 coinciding with a
corresponding contour of the larger blob 158. In
contrast, Fig. 16b depicts similarly shape but different
sized blobs 162 and 164 properly registered with the
smaller blob 164 centered within the larger blob 162. In
the correct registration, the misalignments between the
corresponding contours of the two blobs of detail are
split, thus centering the smaller blob within the larger
blob after the differences have been split.
A slmple example is illustrative of how difference
splitting results from application of the least squares
concept. In Fig. 27a, one pair of segments 166 and 168
separated by a distance e are initially (but
incorrectly) registered with another pair of segments 170
and 172 separated by a greater distance d. In the
initially reglstered position, segments 168 and 172 are
aligned but the other segments 166 and 170 are
considerably misaligned due to the difference between
f the distances d and e~ If o represents the offset
required to accomplish difference splitting, the least
squares measure for minimizing the sum of intersegment
distances is given by the expression
M=(d+e+2O)2 (44~
Taking the partial derivative aM~ and setting it equal
:! to zero yields o = -(d+e)/2. Adding o to d splits the
fff
. .
~ ` .
.
' ': " `' ' ' ' ` ' ' ' ' ' '
.` ~ , ,.
-44~
difference because d + o = ~d-e)/2r and the segments are
properly registered as shown in Fig. 27b when the
difference is split with the corresponding segments 166
and 170 separated by ¦o¦=(d-e)/2 and segments 168 and 172
separated by the same distance.
Although this simple example may be generalized, the use
of tensor analysis allows for averaging of the distance
between segments and for the inclusion of the best fit
rotation correction between pictures as well as the
best fit translational offset correction. This formalism
leads naturally to the classic, solved problem of
minimizing a quadratic form.
L is a straight line represented by column vector
(a b c )t (t denotes transpose), where the line equation
:, ig
:; ~
aX + bY + c = 0 (45)
8ubject to the normalization condition
a2 + b2 =1 (46)
The distance from a point P = (X y l)t to the line L is
the dot product
d (P,L) = Lt. p (47)
Under the assumption of rigid body and small motion (first
order approximation in which rotation angle~satisfies
the condition sin (~)~ ), the displacement of a point P
into a point Q due to translation T and rotation n
! 35 becomes T and a vector cross product added to P,
namely
Q=P+T+QxP (48)
;~ - - - - .
~311~$3
In homogeneous coordinates, the linear operation of
equation (48) can be expre~se~ natrix form:
~t,~ ) C~ o ) ~ ~ ~ ~x
~=IY~ X~ (~~)(~S~ ~ I ty (49) ~ 1 ( X ~ 8~-)(~
In tensor notation, the matrix ( 9) can be written as
(summation over repeated indices implied):
Qi=4 jkDj Pk- (50)
Since any point P is displaced to Q, the distance from a
reference segment SR to a straight line LM representing
the moved segment SM is, from equations (50) and (47),
d(P,LM)=~ijkNRi Dj Pk (51)
Rigid motion requires that D in equation (51) be
conctant. The squared distance from equation (51) can be
integrated along the points of segment SM:
: 20
d2(SM,SR)= ~Sm(~ijkNRiDjPk) ds (52)
On performing the integral of equation (52) the result is
the scalar SK for the Kth segment pair:
: 25
Sk=Dt(NN)t(PP)(NN)D (53)
In formula (53), the D is the displacement
/ ~x\
( ~)
$
I The matrix NN is the tensor dot product
,i
(NN)jk=~ijkNRi
where the vector NR is
, . ~ . ,
:~ , - ,
:
-46- ~ 3
NR=(abc)t (56)
Explicitly, NN is
O o ~
SN N= C~ a b ( 57)
~o b ~ c~
Given that SM goes from endpoint vector Al to vector A2
with length Mr the matrix PP is
PP=(QM/6)[AlA~+A2A2+(A~A2)(A~+A2) ] (58)
where the vectors are
A~ ~ ~ Xo~ nd A2= ~ ~ (59)
~ ~ Yd~J ~ J
In expressions (59), the initial registration move xOffr
yOff from the initial seyment registration has been added
~C to the endpoint coordinates of the moved segment
(which has been moved into initial registration with the
reference segment so that displacement D of expression
~54) will represent a correction to the initial move).
The other segment data are the a,b c parameters evaluated
from the reference segment endpoint data, or
c~ Y~ R~,
b ~ ~X~ - X,~)/QR (60)
C ~ ~r~ X~ryLr/Q~
where lR is the length of the reference segment.
. 30 The problem now is to minimize the sum over k=l to N
f Sk from expression (53) where N is the number of
segment pairs entering the solution. The minimization of
the quadratic form is expressed by the condition
~ N)~p~ D-o ( 61)
: Since D cannot vanish for a non-trivial solution, thevanishing of the summation of expression (61) implies the
, ,
'
'
_47_ ~?3~?1~?~3
solution of an inhomogeneous set o~ 3 simultaneous
equations in the variables tx, ty and ~. Thus, the final
registration move in pixels can be written as
X ~ Yo (62)
~ _ y ~ ~ ~ + ~Xo (63)
where from expression (49), the rotation term is added
back into equations (62) and (63) and evaluated at a
rotation center xO, yO that can be taken at the center of
the pictures. Thus for 640 x 640 pixel original pixels,
xO, yO=319.5, 319.5. This rotation term is quite
important to include when ~is non-negligible.
The choice of N in expression (61) requires care.
Basically, segments that are "close" together are being
registered. In deciding what segment pairs to include in
expression (61), an accurate measure of closeness is
the perpendicular distance from the center of the moved
segment x2c~ Y2C to the infinite line representing the
reference segment. This distance d8 comes from equations
~47) and (60), namely
; 25 Q _ I ~ (X~c ~Xa ~ ) ~ l (~c~ ~O ~) ~ C~ (64)
In a two-pass screening procedure, all of the segment
pairs entering the initial PSM registration are first
~ubjected to the threshold condition
, .
accepted for group 1: d8<tl=l-5pixel8- (65)
;~
In the ~econd pass, the acceptance condition is
accepted for group 2:tl<ds<t2=lO; ~66) ?
neither segment lies in group 1. The segment pairs
passing both conditions (65) and (66) enter the summation
, ,
;
-48-
in expression ~61). The fir~t threshold given by
condition (65) provides very close matches. Such segments
should not be contaminated by additional spurious matches
in group 2; hence the final condition (66). The
threshold 10 in condition (66) is selected as a
reasonable largest size difference to allow.
Finally, an efficient way to compute the summation (61) is
to represent each term in PP of equation (58) by 9 g~r
where g is
~ a~l
g= ~ nJ (67)
and n is for the first two terms in equation t58) and 2
for the last term. Thus, fran expressions (57) and (67),
NNtggtNN yields the 4 x 4 matrix 1 2
/n~ n~b ~ " c~os~ q ~ac~
~ n~ g~n ~o~ ,~ ~lc~ Iz \ (68)
g~ a~g~2-~9~ 92
o.~-a~ g~ alog~2~cbg~n ~ly~
~l Z ~
The upper left 3 x 3 corner of the matrix (68) is Q3 and
V, vt can also be identified, so that the simultaneous
equations to be solve~ from summation (61) become
( ~ ~ ~ X ~) (69)
Where the summations range over segment pairs k = 1,
N and all g~ , gz and n for each kth segment pair.
Equations (69) can be solved by Cramer's rule.
The result of equations (62) and (63) provides the
movement required of the moved picture in order to
register it with the reference picture. With the total
offset of equations (62) and (63) determined for both of
the selected picture points, the registration vector
alignment step can be performed and the table movements
required to punch holes can be computed. The machine 10
and its central system effect proper movement of the chase
";,.
'~ ~
.
, . -'
: . :
49 ~3~-3 ~3
52 necessary to punch holes in the carrier sheet of the
moved picture at the locations wllich assure registration
between it and the reference picture. The other two moved
pictures are thereafter handled in the same manner and
registered with one another and the reference picture.
It is important to realize that the offset between
corresponding registration marks or other marks can be
determined, as well as the offset between corresponding
edges in the halftone detail.
Two-dimensional convolutions have been described herein as
array dot product computations. Such a method of
computation is accurate and simple but suffers from a
computational time burden. The two-dimensional
convolutions described herein can all be performed by
a faster, separable method that entails essentially no
loss in accuracy. The computation time for separable
convolutions scales as N (filter size) rather than N
squared.
The Gaussian filter is separable into h (x) h (y) where h
(~) is the Gaussian exp (-~2/2 ~2 ) h then becomes a
common row and column filter of length 7 (discretized).
Figure 28 illustrates the separable convolution process.
First, the column filter is passed over the data. The
row filter is then passed over the convolution output of
the column filter to yield the final result.
The LOG convolution involves a sum of separable
convolutions, as first shown by Capt. David King while
a student at U.S.C.:
separable LOG filter =hl(x)h2(y)+h2(x)hl(y) (70)
where the two different filter functions are
~()~ p~ (71)
~2.C~) - ,~p~-g~/ac~~3(~
. `'' ~ .- ~ .: : .
-50- ~ 3
Filter h2 is adjuste~ to zero sum in a manner precisely
analogous to the procedure previously described for the
two-dimensional LOG filter. For each separable
convolution of expression ~71), the decimation is
accomplished by decimating in the vertical direction
only in the column filtration of Figure 28 and in both
directions in the final row filtration of Figure 28~ The
linear filters for the ~OG separation have the same size
as the two-dimensional LOG of expression (71), namely a
nominal length of 103 for 150 line screen
The additional Gaussian convolution required for the first
derivative sign in expression (31) can be obtained as a
byproduct of the LOG convolution by taking the Gaussian
filter as hl of expression (71) and using the column
filtration with filter hl also as the first convolution of
the Gaussian convolution. Only one extra, double-
decimated row convolution is then required to produce the
Gaussian convolution.
The result of the edge based registration algorithm
described herein i9 a pair of registration offsets for the
two picture locations 1 and 2. Using this data, a
registratlon transformation (translation and rotation) can
be computed and applied to the reference punch hole
locations, thereby predicting the new punch hole locations
for the non-reference film, required to place the non-
reference film into register with the reference film. The
move from reference punch hole location to new location is
a pure translation that is carried out separately by
the chase 52 for each of the two punch holes in the
referenee picture earrier sheet. In the fixed referenee
frame of the referenee punch hole loeations, the puneh
does not atually move to the new loeation in that same
frame; rather with a fixed punch, the table earries
out a translation that is the exact opposite ~by the
principal of relative motion) of the motion that would be
carried out by a moving punch. More precisely, the table
,,,
.....
,~
: `
_ -51- 13~ 3
motion is a motion into registration, and the motion of a
moving punch is exactly the opposite motion.
One version of the above-mentioned registration
transformation has been described in U.S. Patent No.
4,641,244 which issued on February 3, 1987 to Wilson, et
al. The registration vector alignment algorithm which
will now be described is preferred because it leads
directly to four improvements, namely (1) the delta d-
abort condition which does not punch film if theregistration error is too high, (2) the split the
difference registration vector alignment which reduces
error, ~3) the elimination of some data error by the
imposition of a constant vector length constraint, and (4)
the split the difference registration of films with
image stretching in one film of a registration film pair.
The two registration picture points in each film form a
vector. The reference vector R extends from point x2, Y2
to point xl, Yl on the reference film. The moved
vector M on the film to be registered to the reference
film extends from point X2-dx2,y2-dy2 to point xl-dxl~ Yl-
dyl, where dxl, dyl i9 the computed registration offset
that carries point lM into point lR and dx2, dY2 is the
computed registration offset that carries point 2M
into point 2R. The two vectors in a typical orientation
prior to registration are shown in Fig. 29. The
registration transformation first aligns the tails of the
M and R vectors, then rotates vector M into alignment or
registration with vector R, through the angle in
Figure 29. With vectors M and R suitably aligned, the
reference film is in register with the non-reference film
!~ containing vector M.
' 35 With no offset data error and no image stretching
(global size differences between films to be registered),
, the lengths of vectors R and M are the same. With data
error or global imaye size differences, the lengths differ
.........
. .
, . , . ,- , . . . . .
-52- 13~9~
and delta-d (the absolute difference of the lengths) can
detect an abort (don't punch film) condition if delta-d
exceeds some preset tolerance which is typically 3 mils.
Thus, the registration error (roughly delta-d/2 in
magnitude) can become intolerable in certain
instances, and the machine operator is alerted by the
abort and can take the appropriate action, such as
rejecting the film or trying the registration again with
different picute point selections or with a split the
difference option which will subsequently be
described.
It is useful in the followiny to introduce the variables
~Xo-Xl-X2
aYO Yl~Y2
~x=dx2-dxl (72)
~Y=dY2~dYl-
~ ~
The lengths of the R and M vectors are
dR ~ +QYo (73)
~
dM= J ( bK o+~x ) ~ (~Y o~Y )
then delta-d is
~d=¦dM-dR¦. (74)
~;
The abort condition is no film punching if
; abort: ~d> ~dmax'
where ~dmaX is the laryest tolerable ~d. If there is no
abort, the film is punched and the errors are acceptably
small. Typically, ~dmax=3mil.
.,.~ .
': '
~ ' :
~` _53_ 131~3
In the normal situation, without global image size
differences, ~ x and ~y are subject to a small data error
due to normal computational error of the offsets around
about 1 or 2 (.5 mil) pixels. Since ~x and ~y enter
the computation,~can be improved by eliminating data
error in either ~x or ~y (but not both) by the imposition
of the constraint that ~d be forced to zero for the
purpose of improving either~ x or ~y.
~
If the absolute angle of vector R with the horizontal is
less than or equal to 45 degrees, ~ y can be taken from
data and ~x improved. For angles greater than 45
degrees, ~ x can be taken from data and ~y improved.
The distance preserving equation is
dR=dM, (76)
and for case 1 (¦angle¦ < 45 degrees, ~y from data),
dR=dM yields from expressions (73): !
~x2+b6x+c=0 (77)
where b and c are
b=2~xo
c= ~ yO+ ~y2~ (78)
Solving for ~x and algebraically manipulating the
solution into a computationally robust form, the
im~ ved ~x is
_ s;9v\(lD) ac
Ibl ~ ~ (79)
For case 2 (¦angle¦ > 45 degrees), ~x from data), the
dR=dM equation in ~y is
',, .
;
'., '' :' ' ~ ' '
- : :
.
~ 54- 1 ~ 3
~y2+b~y+c=0 (80)
where b and c are
b=2~Y
c= a~x~xO ~ ~x ( 81)
The analogous solution for improved ~y is
_ S~ )zC (82)
~b)~ b -~C
The quickest way to obtain 8is via the definition of
the vector cross product of M with R, solved for sin~k,
which results in
sin~ = [MxR].[-z] (83)
dMdR
~y the right hand screw rule, the desired negative angle
cross product points in the -z direction. When improved~x
or ~y is utilized, the denominator of the last equation is
replaced by the egual distance denominator dR. The
result i8
sin8 =~ xO+~x)~yO-(~yo+~y)~xo) = -(~X~
~ dR dR
= sin~l~sin~). n I I l (84)
e~ e9;s~ p~C~ *olc ~ ~5
, The tran~formation equations from the prime (rotated
'. frame) to the unprime frame of the punch holes are:
X= X/C08~ -y~sin~+h (85)
"~'1
~ y_ y ~cos~ +xlsin~+k.
. ~,
' ' ' ' '
' , ' '
-55- ~31~3
Since a translation lines up the tails of the vectors at
point 2R, point 2R becomes the rotation origin and
therefore h and k must be
h=x2 (86)
k =y 2
Vector M rotates into vector R by angle er, and signed
points to the prime or R frame. The prime frame
coordinates of the punch hole locations are
xp=xpr-h~dX2 (87)
YP Ypr-k-dy2~
where xpr, Ypr is a reference punch hole location and dx2,
dY2 are subtracted for the same reason that the tail of
lies at x2-dx2, Y2-dy2. Thus, the new registration punch
holes lie at
Xp-(xpr-h-dx2)co9~ ~(Ypr-k-dY2)sin~ +h (88)
yp=(ypr-k-dy2)cos +(xpr-h-dx2)sin +k,
evaluated for each of the two xpr, Ypr punch hole
locations. Fig. 30 illustrates a simplified registration
with ~ =0, dxl=dx2=0 and dyl=dy2=-3. Note that Yp=ypr-(-
3)=Ypr+3~ and that translating the new punch holes in the
M film down to coincide with the reference punch holes
brinys M and R into registration.
In the normal case of a registration n~t abo~ted by~d,
there is a gap at the tips of vectors M and R (aligned at
the tails) of length ~d. It is an improvement to
equally distribute this error at both ends of the
vectors. This is again a "split the difference"
correction, since the shorter length vector will be
~'
, . . ': . , ' . : '
. .
., . . ::
-
~ -56- ~311~3
centered within the longer length vector, as illustrated
by Fig. 31. Let vector R12 extend from point 1 to point 2
on the reference film:
R12=(X2-xl)x+(y2-yl)y- (89)
The chase move or move of vector M with respect to R that
accomplishes the desired difference splitting is simply a
pure translation, namely
s=(dE~~dR) R12' x
~ 2 (90)
f ~-- _
~YS=(dM-dR \ R12 Y
~ 2 J
where the unit vector dot products are simply
R12~X=X2-X1
dR t91)
R12~y=y2_yl
,,~
dR
Since ~X~ ~Y9 iS a chase move, the negatlve of ~xs, ~yS(a
punch move) must be added to the new punch locations xp,
yp to offset difference splitting:
xp ~xp-~xs (92)
YP~ 'YP-~YS -
~ 35 If a registration aborts due to ~d induced by global
;: image stretching size differences, the machine operator
can enable one of two options for re-trying the
~; registration with resulting errors treated by difference
,, 1 ~
~,
,:
,.
~ 57- 131~3
splitting. In such cases, the operator may accept the
retried registration with larger than normal errors split,
providing that the split errors are not deemed unsuitable,
calling for rejection of the film. The deduced image
stretching maynitude, displayed for the operator, also
aids the quality control process. For retries with global
image stretching in one of the two films to be registered,
the ~d abort is disabled, since ~d would naturally be
larger than normally acceptable in the presence of
~ 10 singificant global image stretching.
- Retrying option 1 model for registration with global image
stretching invokes the assumption that the image
stretching is uniform in both the x and y axes, precisely
analogous to a uniform magnification or
demagnification of one film with respect to the other
film. Since uniform magnification does not change angles,
the solution is simply to compute ~XS, ~Ys as before from
expressions (90). It is necessary, however, to bypass the
improvement of expressions (79) or (82) and compute
both ~x and ~y from data [expression [72)1 since the
assumption of ~d forced to zero in angle improvement
with ~x and 4y input significantly modified by global size
differences is invalid in the presence of size differences
that insure that ~d can never vanish. A further
minor modification is thata denominator dR2 in expression
(84) be replaced by the original dRdM. f course, for
any split the difference registration, expression (92)
remains as the final required step.
~, 30
Retrying option 2 modeled for registration with global
image 8tretching invokes the assumption that the dominant
image stretching occurs in one direction (x and y) with
~ only a smaller stretching (or none) present in the other
;;;1 35 direction. This model applies, for example, to imayes
~tretched by virtue of the original image on a paper
substrate being stretched predominantly around a graphic
arts scanner drum. In this case of non-isotropic image
,- . . , : .
, ~ . , .
",''~
, . , - , , ~
-5~- 1311~3
stretching, angles do not remain invariant and special
treatment is required. The option 2 model is not exact
(unlike the option l model), but involves a perturbation
approximation based on the smallness of the non-dominant
image stretching with respect to the dominant
stretching. The result, however, is accurate to within
several tenths of a mil, as testing has borne out.
For option 2, the operator specifies the dominant
direction of image stretching. Only the case of
dominant image stretching in the x direction will be
described. The case of dominant image stretching in the y
direction follows analogously.
By the perturbation assumption, ~y is initially free
from image stretching. Consequently,~ x free (image
stretching removed) from image stretching comes from
equation (79) with ~y taken from data. The split the
difference-correction ~XS is now
~ XS= ~ (~Xda ta~~X )
Applying equation (93), dM can be recomputed with x
error split to determine the residual y effect:
:, .
M J(~xO+~x+~xs)2+(~y0+~y)2 (9
Using equation (94~ ~Ys can be taken from expression
(90), namely,
s= ~dM-dR~(Y2 Yl)-
~"'! 35 ~ - ~
The inital~ y could have actually had some image
~' stretching in it. The lmproved ~y (in the absence of
image stretching) can be computed from
.: ,
,
' .
;
: : .
_59- 1311~3
s= ( ~Q~ ~ ) /2 solved for ~ y or
~Y ~Ydata+2~ys (96)
The solution proceeds by repeating the computation
once using ~y of equation (96) (from iteration 1) as
improved input. ~ is computed on the second pass from
expression (84), and ~ xs. aYs for expression (92) are
taken from the second pass of equations (93) and (95).
Two further refinements enhance the option 2 model of
global image stretching. The first refinement is that the
selection of the dominant stretching direction by the
operator can be replaced automatically by an algorithmic
; 15 detection step. The basis algorithm is to compute the
assumed stretching in both x and y, then select that
stretching as dominant that agrees most closely in
magnitude with d~ta-d of expresion (74) (which measures
stretching). Thus, the computed stretchings SX and sy are
SX=~Xd-~xu=~xd+~yd (~>~ )
i Sy=~yd-~yu=ayd+~xd ( ~; ~
~, where ~xd~ ~Yd are offset rom data as in expression
(72). ~XU in expression (72) is the ~x in the absence
of stretching computed from expression (79) by assuming
~Yd is free of stretching and expanding expression (79) out
~i to only lowest order terms (a very accurate
approximation). Similarly, ~Yu comes from expanded
~ 30 expression (82) with ~xd taken from data.
,,:j
The absolute differences dx, dy are computed by
d =¦¦s ¦-~d¦
dy_¦¦syl-~dl~
~ The stretching is dominant in the x direction if
,,,,
~ ~; ,
".~
~., ~ ' , ' , ' " ',, ' ' . ' ' '
":' ~ ~ , , ' ' .
..
,,: . ' ' : , ' ~ ' ''
1, .~' . . .
. ~ ~ . . .
`' -60~ 3
dx~dy~ (98)
in which case the assumption of validity of dx gives the
best match to ~d. If the condition of expression (98)
does not hold, the dominant stretching is in the y
direction. Condition (98) has been verified with test
films to detect the dominant stretching direction even in
the presence of significant rotation in the rough
register. Note that either ~xO or ~yO becoming very small
in dominator of expression (97) leads to a situation
with splitting in one direction only that is correctly
predicted by expression (98) (for example, if ~yO becomes
small, ¦syl becomes large as ¦sxl becomes small and
expression (98) is evidently satisfied, predicting stretch
splitting only in the x direction).
The second refinement to the option 2 model of global
image stretching is operator selection of the in-register
point of the split the difference registration. So far it
has been implicit that the in-register point in a
split the difference registration lies at the center
between the two registration points 1 and 2. This
situation i8 the normal case where the desired central
point of the halftone detail coincides closely enough with
the in-register point. Fig. 32 illustrates a
situation reguiring operator selection of the in-register
point not at the center between registration points, but
at the center of the halftone detail.
The step that exactly moves the in-register point to
the desired location xc, Yc is a modification of
expression (92), namely
~ '
xp~ xp-axsfx (98
,. yp~ Yp-~YSf y
where the proportional scaling factors fx and fy are
..
. ~ ~
i ~ ,
~",,~ ,.. , , . ~ .
~ : .
~ .
`` -61-
-~ - a (""'` )
a ( YC - ~
__ _ ~ ( g g )
~x(~ ,Y; ) - ~` ~(Y2,~,)
~r ~ ~j ?~ >~2
à ~ /Z
Evidently, if xc, Yc lies midway between registration
points xl, Yl and x2, Y2 then fx=fy=l~ and the
original solution (92) is recovered.
From the foregoing, it will be seen that this invention is
one well adapted to attain all the ends and objects
ZO hereinabove set forth together with other advantages
which are obvious and which are inherent to the structure.
It will be understood that certain features and
subcombinations are of utility and may be employed without
reference to other features and subcombinations. This
is contemplated by and is within the scope of the claims.
Since many possible embodiments may be made of the
invention without departing from the scope thereof, it is
to be understood that all matter herein set forth or
shown in the accompanying drawings is to be interpreted as
illustrative and not in a limiting sense.
.,,
,:,
,
. . .
.~ .,
.~ . . .
