Method and apparatus for registering color film separations

Abstract

An algorithmically based method and apparatus for registering halftone color separations using edge based registration techniques and three registration points on each film separation in order to handle image stretching in both directions. Improved techniques include the use of gray level transformation, an improved U.S.C. predicate, double accuracy interpretation after systematic convolution sampling, finer angle sweeping to achieve smoother edge transitions around sharp corners, elimination of gaps in the edge continuity, enhancement of final edge linking, a more accurate and robust segment matching algorithm, invocation of a registration quality index for quality control checking of each segment picture registration, and reduction of machine cycle time by performing computations concurrently with machine movement.

Having thus described the invention, what is claimed is: 
     
       1. In a method of registering a pair of color separation films containing macroscopic edges which align when the films are registered, the steps of: selecting one of the films as a reference film;   recording first, second and third pictures of the reference film containing macroscopic edges and centered at spaced apart first, second and third locations, respectively;   recording fourth, fifth and sixth pictures of the other film containing macroscopic edges and centered at locations on the other film which approximately correspond to but may be offset from the respective first, second and third locations;   extracting from said first and fourth pictures the locations of corresponding macroscopic edges on the reference film and on the other film;   extracting from said second and fifth pictures the locations of corresponding macroscopic edges on the reference film and on the other film;   extracting from said third and sixth 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 corresponding edge locations on the other film to thereby determine the positional adjustment of the other film necessary for registration with the reference film.   
     
     
       2. The method of claim 1, wherein each picture comprises a digital picture and including the step of transforming gray levels of each digital picture prior to extracting therefrom the locations of the corresponding macroscopic edges.   
     
     
       3. The method of claim 1, wherein the step of extracting the locations of said corresponding macroscopic edges comprises for each picture the steps of: obtaining a systematically sampled convolution output to produce a reduced resolution determination of the locations of edge points on the macroscopic edges of the picture and the edge direction at each such location; and   interpolating said convolution output in a manner to obtain a determination of the locations of the edge points on the macroscopic edges of the picture that is at least twice as accurate as interpolation of said convolution output from the reduced resolution to full resolution.   
     
     
       4. The method of claim 3, wherein said determining step comprises using the parameter space method to match edges on the reference film and the other film and the edges matched by the parameter space method are based on the results of said interpolating step, whereby offsets produced by the parameter space method are at least doubly accurate. 
     
     
       5. The method of claim 1, wherein said determining step comprises effecting a coordinate transformation using an origin at one of said locations at which the pictures are centered and a rotation angle that effects registration of the films, said step of effecting a coordinate transformation comprising the further step of effecting difference splitting to produce a translation component which represents a registration compromise. 
     
     
       6. The method of claim 5, wherein said step of effecting difference splitting comprises determining a pair of image stretching coefficients α x ,α y  along mutually perpendicular x and y axes from a least squares solution of the equation:   α.sub.x d.sub.xij cos θ.sub.ij +α.sub.y d.sub.yij sin θ.sub.ij =d.sub.Mij -d.sub.Rij     where R is a vector connecting two points xi,yi and xj,yj having a length of dRij on the reference film, thetaij is the angle from the x axis to the vector R, dxij,dyij are the absolute component lengths of vector R along the respective x and y axes and the vector corresponding to the vector R on the other film is represented R+Sij by vector addition and has a length DMij, where Sij is a stretching vector given by     S.sub.ij =α.sub.x d.sub.xij X+α.sub.y d.sub.yij y.     
     
     
       7. The method of claim 6, wherein said step of effecting difference splitting further comprises determining split the difference translations ex and ey along the respective x and y axes in accordance with ##EQU36## where Lx and Ly are the side lengths of a box along the respective x and y axes with said box minimally confining said first, second and third locations. 
     
     
       8. The method of claim 1, including the step of algorithmically computing a quality control edge segment match quality index based on the registration offsets at said first and fourth locations, second and fifth locations and third and sixth locations. 
     
     
       9. In a method of registering a pair of color separation films containing macroscopic edges, the steps of: selecting one of the films as a reference film;   recording at least first and second digital pictures of the reference film containing macroscopic edges and centered at spaced apart first and second locations, respectively;   recording at least third and fourth digital pictures of the other film containing macroscopic edges and centered at locations on the other film which approximately correspond to but may be offset from the respective first and second locations;   determining the locations of edge points on the macroscopic edges of each picture and the edge direction at each such edge point location by obtaining a systematically sampled convolution output effective to produce a reduced resolution determination of said edge point locations and edge directions;   interpolating said convolution output in a manner to obtain an interpolated determination of said edge point locations that is at least twice as accurate as interpolation from the reduced resolution to full resolution; and   using said interpolated determination of said edge point locations in the parameter space method to match macroscopic edges on said first and third pictures and to match macroscopic edges on said second and fourth pictures, thereby producing offsets for the matched macroscopic edges that are at least doubly accurate.   
     
     
       10. Apparatus for effecting registration between a pair of color separation films containing macroscopic edges which align when the films are registered, since apparatus comprising: means for recording first, second and third digital pictures containing macroscopic edges on one of the films centered at respective first, second and third locations spaced apart on said one film;   means for recording fourth, fifth and sixth digital pictures containing macroscopic edges on the other film centered at locations on said other film which approximately correspond to but may be offset from the respective first, second and third locations;   means for extracting the locations of corresponding macroscopic edges on said first and fourth pictures, on said second and fifth pictures and on said third and sixth pictures; and   means for computing the offsets between the macroscopic edge locations on said one film and the corresponding macroscopic edge locations on said other film to thereby determine the positional adjustment necessary to effect registration of the films.   
     
     
       11. Apparatus as set forth in claim 10, wherein said extracting means comprises: means for extracting from each picture a systematically sampled convolution output representing a reduced resolution determination of the locations of edge points located on the macroscopic edges of each picture and the edge direction at each such edge location; and   means for interpolating said convolution output in a manner to obtain an interpolated determination of the locations of the macroscopic edge points that is more accurate than the result of interpolating the convolution output to full resolution.   
     
     
       12. Apparatus as set forth in claim 11, wherein said computing means comprises means for using said interpolated determination in the parameter space method to compute said offsets more accurately than would result from use of data derived from interpolating the convolution output to full resolution. 
     
     
       13. Apparatus for registering a pair of color separation films containing macroscopic edges which align when the films are registered, said apparatus comprising: a digital camera operable to record digital pictures;   means for effecting relative motion between said camera and each film to align the camera with selected locations on each film and record digital pictures at two spaced apart locations on each film which correspond to but may be offset from corresponding locations on the other film;   means for computing from the image data on each digital picture the locations of edge points which lie on the macroscopic edges of the picture, said computing means being operable to carry out computations for each digital picture while relative motion between said camera and the film is being effected;   means for calculating the offset between the corresponding macroscopic edges on the films; and   means for using said offset to locate punch hole positions on the films that effect registration of the films upon alignment of the punch hole positions.   
     
     
       14. Apparatus as set forth in claim 13, including: means for punching each film to form plural punch holes therein;   means for effecting approximate alignment between said punching means and the punch hole positions on each film; and   means for effecting exact alignment between said punching means and the punch hole positions on each film, said calculating means being operable to calculate said offset while relative motion is being effected between said punching means and the film by said means for effecting approximate alignment.   
     
     
       15. In a method of registering a pair of color separation films containing macroscopic edges which align when the films are registered, the steps of: recording at least first and second digital pictures of the reference film containing macroscopic edges and centered at spaced apart first and second locations, respectively;   recording at least third and fourth digital pictures of the other film containing macroscopic edges and centered at locations on the other film 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;   determining the offset between the edge locations on the reference film and the corresponding edge locations on the other film to thereby determine the positional adjustment of the other film necessary for registration with the reference film; and   algorithmically computing a quality control edge segment match quality index based on the registration offsets at said first and third locations and said second and fourth locations.   
     
     
       16. In a method of registering a pair of color separation films containing macroscopic edges which align when the films are registered, the steps of: selecting one of the films as a reference film;   recording first, second and third pictures of the reference film containing macroscopic edges and centered at spaced apart first, second and third locations, respectively;   recording fourth, fifth and sixth pictures of the other film containing macroscopic edges and centered at locations on the other film which approximately correspond to but may be offset from the respective first, second and third locations;   extracting from said first and fourth pictures the locations of corresponding macroscopic edges on the reference film and on the other film;   extracting from said second and fifth pictures the locations of corresponding macroscopic edges on the reference film and on the other film;   extracting from said third and sixth pictures the locations of corresponding macroscopic edges on the reference film and on the other film, said extracting step comprising for each picture the step of obtaining a systematically sampled convolution output to produce a reduced determination of the locations of edge points on the macroscopic edges of the picture and the edge direction at each such location; and the step of interpolating said convolution output in a manner to obtain a determination of the locations of the edge points on the macroscopic edges of the picture that is at least twice as accurate as interpolation of said convolution output from the reduced resolution to full resolution; and   determining the offset between the edge locations on the reference film and the corresponding edge locations on the other film to thereby determine the positional adjustment of the other film necessary for registration with the reference film.