Abstract:
A method and apparatus to improve the vertical alignment of images captured from video. The method shifts a current scanline by an alignment offset detected locally between either the two fields of the image or within a field of the image itself. This aligns the current scanline to more closely correspond with adjacent intra-field or inter-field scanlines, thereby reducing wiggles or jitters in the vertical lines of the image.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of Invention 
     This invention is related to capturing and printing still images from video data signals. In particular, this invention is directed to a system and method to improve the vertical alignment of images captured from video. 
     2. Description of Related Art 
     Video recorders, camcorders and VCRs, for example, provide a source of electronic video images. However, especially in consumer-quality video recorders, when still images are captured from the video data signal and printed, the quality of the captured and printed still images is often less than desired. Furthermore, these video recorders may inaccurately synchronize the video scanlines. This inaccurate synchronization causes the starting point of scanlines to drift horizontally from scanline to scanline, resulting in the common appearance of wiggles or jitters in the vertical lines of the image. 
     SUMMARY OF THE INVENTION 
     The NTSC television standard forms a full frame image from two separate fields captured {fraction (1/60)}th of a second apart. One field contributes the even scanlines of the image, while the other field provides the odd scanlines of the image. FIG. 1 shows the odd scanlines  10  and even scanlines  20  which form the full image frame. Furthermore, FIG. 1 illustrates a typical example of the horizontal drift that occurs from scanline to scanline within an even or odd field (intra-field drift) as well as the horizontal drift that occurs between the fields (inter-field drift). 
     The average scanline starting position between two scan lines of a field will generally be more correct then the starting position of any single scanline. Since the two fields are separated by time, the horizontal drift of the fields will be uncorrelated. Hence, the average scanline starting position between the two fields is likely to be more nearly correct than the average starting position of either field alone. By measuring the misalignment within and between the fields, detecting the wiggle or jitter is straightforward. 
     U.S. patent application Ser. No. 08/882,933, filed Jun. 26, 1997, U.S. Pat. No. 6,031,581 incorporated herein by reference in its entirety, discloses a system for removing color bleed in a television image adapted for digital printing. Specifically, the 933 application discloses a method for improving an image derived from a television or video tape signal source so that the image can be favorably printed. However, this requires the entire image frame to be stored in memory and several passes over the image to determine the correct alignment. 
     This invention provides systems and methods for removing horizontal drift in still images captured from video data signals. 
     This invention separately provides systems and methods for removing intra-field and inter-field drift from captured still images. 
     This invention separately provides systems and methods that determines an average start position of the scanlines within a field of a captured still image and/or between the two separate fields forming a captured still image. 
     These and other features and advantages of this invention are described in or are apparent from the following detailed description of the preferred embodiments. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The preferred embodiments of this invention will be described in detail, with reference to the following figures, wherein: 
     FIG. 1 shows the vertical scanlines in a captured video frame; 
     FIG. 2 shows the intra- and inter-field alignments of sets of the vertical scanlines of the captured video frame of FIG.  1 . 
     FIG. 3 is one embodiment of a functional block diagram of a system for intra-field and/or inter-field aligning a video frame according to this invention; 
     FIG. 4 outlines one embodiment of a method of improving vertical alignment of scanlines in a captured still image according to this invention; 
     FIG. 5 outlines one embodiment for the step of intra-field aligning the scanlines of a field of FIG. 4 in greater detail; 
     FIG. 6 outlines one embodiment for the step of inter-field aligning the scanlines between the fields of FIG. 4 in greater detail; 
     FIG. 7 shows the horizontal offsets between vertically adjacent scanlines in different fields of the video frame of FIG. 1; 
     FIG. 8 shows the corrected vertical scanlines of the video frame of FIG. 1; and 
     FIG. 9 shows the corrected intra- and inter-field alignments of the captured video frame of FIG. 1 according to this invention. 
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     To detect the wiggle or jitter in a video frame, the systems and methods of this invention maintain intra- and inter-field horizontal offset values as the scanlines of a video frame are sequentially analyzed. Initially, the intra- and inter-field horizontal offset values are set to zero. As the systems and methods of this invention initially sequentially step through the scanlines either for intra-field aligning or for inter-field aligning, and for each scanline, the sum of the absolute pixel differences between the current scanline and a preceding original unshifted scanline or a preceding shifted scanline is determined. Furthermore, for each scanline, the sum of the absolute pixel differences between the current scanline and a next original unshifted scanline or a next shifted scanline is determined. This provides a comparison between the scanlines within a field and between the even and odd fields. The determined differences for each pair of scanlines are taken between pixels offset by the intra-field offset value and/or the inter-field offset value. 
     However, it is to be appreciated that it may be desirable to perform both an intra-field and an inter-field alignment to the input still image in order to achieve greater alignment accuracy. Therefore, where the intra-field alignment has already been performed, a subsequent inter-field alignment is based on the shifted, i.e., aligned, scanlines produced by the intra-field alignment. Furthermore, where the inter-field alignment has already been performed prior to the intra-field alignment, a subsequent intra-field alignment is performed on the shifted, i.e., aligned, scanlines produced by the inter-field alignment. 
     Furthermore, it should be appreciated that the intra-field alignment can be performed on a previously intra-field shifted scanline. Depending on the type of intra- or inter-field mis-alignment, selecting either the previously shifted or unshifted, original scanlines may provide better alignment. 
     While this invention will be described with reference to an embodiment where the intra-field alignment of the odd and even scanlines will be performed, followed by a subsequent inter-field alignment, it would be obvious to one having ordinary skill in the art to modify the invention to perform either the intra-field or the inter-field alignment separately, or the inter-field alignment prior to, in unison with, or subsequent to the intra-field alignment. 
     Therefore, in the current exemplary embodiment, where the intra-field alignment is performed prior to the inter-field alignment, if the offset value indicates that the current scanline is likely to be shifted three pixels to the right relative to the previous scanline and next original, unshifted scanline, then a first absolute difference between the value of a selected pixel of the current scanline and the value of a corresponding pixel in the previous scanline that is three pixels to the left of the selected pixel is determined. At the same time, a second absolute difference between the value of the selected pixel and the value of a corresponding pixel in the next original, unshifted scanline that is three pixels to the right of the selected pixel is determined. The first and second absolute differences are then summed. This is repeated until every pixel of the current scanline has been selected. 
     Similar sums can also be determined for candidate offset values that neighbor the current offset value. For the example shown in FIG. 1, if the inter-field offset value is three, the system and method of this invention also determines the sums for an inter-field offset value of two and an inter-field offset value of four. Furthermore, depending on the time and required precision of the result, offset values plus or minus two from the current offset value, e.g., inter-field offset values of one and five pixels, or even greater shifts could be used as well. This potentially further increases the chances of finding the best alignment. 
     The offset value which gives the minimum sum is then determined. The offset with the minimum sum gives the best alignment within a field or between the fields for the current scanline is used to adjust the horizontal position of the current scanline. The current scanline is then shifted by half of the determined offset value so that the current scanline moves halfway to meet the next scanline. Generally speaking, the systems and methods of this invention cannot distinguish which of the two scanlines has a position closest to the desired alignment, so the systems and methods of this invention use the average position. 
     As shown in FIG. 2, a scanline that extends beyond its neighbors within a field, as illustrated by the distance  90 , has an intra-field drift or mis-alignment. This intra-field mis-alignment is distinct from the inter-field offset  80  between the scanlines of different fields. To correct for intra-field mis-alignment, the current scanline is shifted by the full intra-field offset value within the field. In contrast, the current scanline is shifted by only one-half of the inter-field offset value between the fields. In general, in the first instance, the inter-field alignment determination is identical to the intra-field alignment determination, except each scanline is compared to the original unshifted or shifted scanline above it and the original unshifted, or shifted scanline below it, within the same field. 
     FIG. 3 shows a functional block diagram of one embodiment of an alignment system  100  according to this invention. The alignment system  100  includes a scanline selector  110 , a pixel difference generator  120 , a pixel difference generator  130 , a sum generator  140 , a minimum sum determiner  150 , a scanline shifter  160 , a controller  170  and a memory  180 , each connected to a data and control bus  190 . The alignment system  100  inputs video data signals from a video source  200  and outputs captured still images with aligned fields to a still image sink  300 . 
     The video source  200  that provides the video data signals to the alignment system  100  can be a video camera or any other video source that is capable of providing a video signal or a digitized or captured video frame to the alignment system  100 . 
     The image sink  300  may be any one of a number of different image sinks, such as a printer, a digital copier or a facsimile machine device, that are suitable for receiving electronic image data, or a device suitable for storing and/or transmitting electronic image data, such as a client or server of a network, or a non-volatile memory such as a hard drive and disk or floppy drive and disk. 
     The controller  170  controls the operation of each of the scanline selector  110 , the pixel difference generators  120  and  130 , the sum generator  140 , the minimum sum determiner  150  and the scanline shifter  160  based on one or more control routines stored in the memory  180 . 
     The memory  180  should have at least a non-volatile portion  182  that is able to persistently store the control routine, such as ROM, flash memory or a magnetic media storage drive, such as a floppy drive and disk or a hard drive and disk, although it may also have a volatile portion  184 , such as RAM or the like. Furthermore, the memory  180  should be capable of storing information relating to both shifted and unshifted versions of the input data signal. As previously discussed, the methods and systems of this invention could use both shifted and unshifted versions of the input video data to achieve even greater accuracy. 
     The pixel difference generator  120  determines the absolute difference between the current scanline and a previous scanline that is above the current scanline in either the same field or a different field. Furthermore, the pixel difference generator  130  determines the absolute difference between the current scanline and a next scanline that is below the current scanline in either the same field or a different field. However, it is to be appreciated that the next and previous scanlines can be shifted or original, unshifted scanlines. 
     The sum generator  140  determines the candidate offsets that neighbor the determined current offset. The minimum sum determiner  150  determines which of the determined offset values provides the minimum sum. This offset value will provide the best alignment of the current, previous and next scanlines and will be used to adjust the horizontal position of the current scanline. The scanline shifter  160  uses this offset value to shift the current scanline to improve the intra- or inter-field alignment. 
     In operation, the scanline selector  110  receives a video data signal representing a video frame having even and odd fields from the video source  200 . The even and odd scanline fields of the video data signal can then be merged, and the merged input video data signal can be stored in the memory  180 . In this case, as each scanline is analyzed, that scanline, the previous scanline and the next scanline are read from the memory  180  and output to the pixel difference generators  120  and  130 . Alternately, each scanline of a previously merged interlaced input video data signal can be directly input to the pixel difference generators  120  and  130 . 
     Furthermore, the methods and systems of this invention allow for interlaced input video data signals to be input to the pixel difference generators. As discussed below, while, in general, the intra-field alignment is corrected prior to correcting the inter-field alignment, the methods and systems of this invention work equally well when correcting the intra-field and inter-field alignment in unison, or when correcting the inter-field alignment prior to the intra-field alignment. To implement these various techniques, only the number of scanlines stored in memory needs to be adjusted. 
     For intra-field alignment correction, the scanline selector  110 , under the control of the controller  170 , sequentially selects each previously shifted scanline within a selected field of the input video image. As each scanline from the selected field of the video data signal is selected, that scanline, a previously shifted scanline and a next original, unshifted scanline of the selected field are provided to the pixel difference generators  120  and  130 . The pixel generators  120  and  130  generate the sum of the absolute pixel difference between the current scanline and the previous original, unshifted scanline, and the current scanline and the next original, unshifted scanline respectively, based on a current value for the intra-field offset. The offset value that results in the smallest pixel difference between a current scanline and the previous and/or next scanlines, or both scanlines, is the intra-field mis-alignment. The sum generator  140  sums the pixel difference between the current scanline and the previous original, unshifted scanline, and the pixel difference between the current scanline and the next original, unshifted scanline, as shown in FIG. 7, between the scanlines  30 ,  60  and  70  based on the current value of the intra-field offset. Sums are generated for at least these different horizontal offsets, namely the current offset value, and its incremented and decremented values. 
     As the alignment system  100  in turn selects each of the scanlines of the selected field, the intra-field horizontal offset value is updated in the system memory  180  under the direction of controller  170 . As previously mentioned, the intra-field horizontal offset value is initially set to zero. 
     The minimum sum detector  150  determines which offset value gives the minimum sum. This offset value will provide the best alignment between scanlines for this particular scanline and is used by the scanline shifter  160  to adjust the horizontal position of the current scanline. The scanline shifter  160  shifts the current scanline by the full offset value so that the current scanline is adjusted for better alignment within a field and stores the shifted scanline in the memory  180  as part of an intra-field adjusted video image. Alternatively, the scanline shifter  160  could directly output the shifted scanline to a broadcast or transmission network, or a video printer or the like. 
     Then, for the inter-field alignment correction, the scanline selector  110 , under the control of the controller  170 , sequentially selects each shifted scanline of the stored intra-field adjusted video image. As each shifted scanline of the intra-field adjusted video image is selected, that scanline, the previous shifted scanline and the next shifted scanline of the other field are provided to the pixel difference generators  120  and  130 . The pixel generators  120  and  130  generate the sum of the absolute pixel difference between the current scanline and the previous shifted scanline, and the current scanline and the next shifted scanline respectively, based on a current value for the inter-field offset. The offset value that results in the smallest pixel difference between a current scanline and the previous shifted scanline and the next shifted scanline, or both, is the inter-field mis-alignment. The sum generator  140  sums the pixel difference between the current scanline and the previous shifted scanline, and the pixel difference between the current scanline and the next shifted scanline, as shown in FIG. 7, between the scanlines  30 ,  40  and  50  based on the current value of the inter-field offset. Sums are generated for at least these different horizontal offsets, namely the current offset value, and its incremented and decremented values. 
     As the alignment system  100  in turn selects each of the scanlines, the inter-field horizontal offset value is updated in the system memory  180  under the direction of controller  170 . As previously mentioned, the inter-field horizontal offset value is initially set to zero. 
     The minimum sum detector  150  determines which offset value gives the minimum sum. This offset value will provide the best alignment between fields for this particular scanline and is used by the scanline shifter  160  to adjust the horizontal position of the current scanline. The scanline shifter  160  shifts the current scanline by half of the offset value so that the current scanline moves halfway for better alignment between adjacent scanlines and stores that shifted scanline in the memory  180  as part of an inter-field adjusted video image. 
     FIG. 4 is a flowchart outlining one embodiment of a method that improves the vertical alignment of images captured from video data signal according to this invention. Specifically, FIG. 4 outlines a method where the intra-field alignment is performed prior to the inter-field alignment. Control begins in step S 100 . Next, in step S 200 , an interlaced video image frame, containing both even and odd fields, is input. Control then continues to step S 300 . 
     In step S 300 , the scanlines of the even field are intra-field aligned. Then, in step S 400 , the scanlines of the odd field are intra-field aligned. Next, in step S 500 , the shifted scanlines of the even and odd fields are inter-field aligned. Control then continues to step S 600 . 
     In step S 600 , the aligned image is output. Then, in step S 700 , the control sequence ends. 
     It should also be appreciated that the intra-field aligning steps S 300  and S 400  can alternatively be performed independently on the even and odd fields. That is, intra-field aligning steps can be performed before the captured fields forming the captured frame are merged. This could simplify the analysis of these fields. Furthermore, once a number of scanlines of both fields have been individually intra-field aligned, the intra-field aligned scanlines can be immediately inter-field aligned without requiring either field to be completely intra-field aligned. 
     FIG. 5 is a flowchart outlining one embodiment of the method of aligning the even and odd fields of steps S 300  and S 400  of FIG. 4 in greater detail. Control begins in step S 300  or S 400 . In either case, control continues to step S 305 . In step S 305 , a video image frame is input and an intra-field horizontal offset initially set to zero. Then, in step S 310 , the first scanline of the current field is selected as the current scanline and the second original, unshifted scanline of the same field is selected as the next scanline. At this time there is no previous scanline. However, in the instance where there is no previous scanline, the current scanline could be used as the previous scanline. Control then continues to step S 315 . 
     In step S 315 , the sums of the absolute pixel difference between the current scanline and the previous shifted, or shifted if desired, scanline (if present) are determined, and the sum between the current scanline and the next original, unshifted scanline (if present) are determined. Next, in step S 320 , the sums of the differences between pixels offset by the intra-field offset value are determined for the current offset value. Then, in step S 325 , the sums for candidate offsets, i.e., the current offset value plus or minus one, that border the current offset are determined. Control then continues to step S 330 . 
     In step S 330 , the sums and differences determined in steps S 315 -S 325  are checked to determine if additional offset values, e.g., the current offset plus or minus two, need to be considered. If so, control continues to step S 335 . Otherwise, control jumps to step, S 340 . 
     In step S 335 , the additional offset values are selected. Control then returns to step S 325 . 
     In step S 340 , the offset value giving the minimal sum of the absolute differences is determined and the intra-field offset value is set to this value. This intra-field offset value gives the best alignment within a field for the current scanline. Then, in step S 345 , the current scanline is each shifted by offset value and stored as part of an intra-field adjusted video image, so that the current scanline moves to become more closely aligned with the previous and next scanlines. Control then continues to step S 350 . 
     In step S 350 , the current scanline is checked to determine if the current scanline is the last scanline in the current field. If so, control jumps to step S 360 . Otherwise control continues to step S 365 . In step S 365 , the current original, unshifted scanline is selected as the previous scanline, the next original, unshifted scanline is selected as the current scanline, and the next original, unshifted scanline in the current field is selected as the next scanline. Control then jumps back to step S 315 . 
     In step S 360 , the control sequence returns to either step S 300  or S 400 , depending on which field is being aligned. 
     FIG. 6 is a flowchart outlining one embodiment of the method of aligning the scanlines between fields of step S 500  in greater detail. Control begins in step S 500 . Next, in step S 505 , the intra-field aligned fields of the merged image video image frame are input and an inter-field horizontal offset is initially set to zero. Then, in step S 510 , the first shifted scanline of the merged image is selected as the current scanline and the second shifted scanline of the merged image, i.e., the first scanline of the other field, is selected as the next scanline. At this time there is no previous scanline. Control then continues to step S 515 . 
     In step S 515 , the sums of the differences between pixels offset by the inter-field offset value are determined for the current offset value. Then, in step S 520 , sums for candidate offsets, i.e., the current offset value plus or minus one, that border the current offset are determined. Control then continues to step S 525 . 
     In step S 525 , the sums and differences determined in steps S 515 -S 520  are checked to determine if additional offset values need to be considered. If so, control continues to step S 530 . Otherwise, control jumps to step S 535 . 
     In step S 530 , the additional offset values, e.g., the current offset value plus or minus two, are selected. Control then returns to step S 520 . 
     In step S 535 , the offset value giving the minimum sum of the absolute differences is determined and the inter-field offset value is set to this value. This offset value gives the best alignment between the fields for the current scanline. 
     Then, in step S 540 , the current scanline is shifted by one-half the offset value, so that it moves halfway to become more closely aligned with each other scanline and the shifted scanline is stored as part of an inter-field adjusted video image. Control then continues to step S 545 . 
     In step S 545 , the current scanline is checked to determine if the current scanline is the last scanline in the merged image. If so, control jumps to step S 550 . Otherwise control continues to step S 555 . In step S 555 , the current shifted scanline is selected as the previous scanline, the next shifted scanline is selected as the current scanline, and the next shifted scanline in the image is selected as the next scanline. Then, in step S 560 , the sign of the offset is inverted. Control then jumps back to step S 515 . 
     In step S 545 , the control sequence returns to step S 500  of FIG.  4 . 
     FIG. 8 shows the corrected alignment between fields. Specifically, the scanline  60  is shifted to the left, the scanline  40  is shifted to the right, the scanline  30  is shifted to the left, the scanline  50  is shifted to the right and the scanline  70  is shifted to the left. Clearly the alignment is far improved over the alignment shown in FIG.  6 . It is to be appreciated that in inter-field aligning the even and odd video frames, even better results can be obtained by comparing the alignment of the current scanline with the scanlines above and below the current scanline in the same field. This requires buffering at least five scanlines. If there is wiggle in the alignment, then some scanlines will have the local maximum drift. These scanlines will be identified and shifted left or right, relative to both the scanline above and the scanline below in the same field as the current scanline. These scanlines can be shifted the full amount to align these scanlines with the neighboring scanlines in the same field, as well as half the amount of the offset between the neighboring scanlines in the other field. 
     It is also to be appreciated that in intra-field aligning the even and odd video frames, even better results can be obtained by comparing the alignment of the current scanline with the scanlines above and below the current scanline in the same field. This requires buffering at least five scanlines. If there is wiggle in the alignment, then some scanlines will have the local maximum drift. These scanlines will be identified and shifted left or right, relative to both the scanline above and the scanline below in the same field as the current scanline. These scanlines can be shifted the full amount to align these scanlines with the neighboring scanlines in the same field, as well as half the amount of the offset between the neighboring scanlines in the other field. 
     FIG. 9 shows the corrected alignment between fields. Clearly the alignment is far improved over the alignment shown in FIG.  8 . 
     As shown in FIG. 3, the alignment device is preferably implemented either on a single programmed general purpose computer or separate programmed general purpose computers. However, the intra- and inter-field alignment device can also be implemented on a special purpose computer, a programmed microprocessor or microcontroller and peripheral integrated circuit elements, an ASIC or other integrated circuit, a digital signal processor, a hardwired electronic or logic circuit such as a discrete element circuit, a programmable logic device such as a PLD, PLA, FPGA or PAL, or the like. In general, any device, capable of implementing a finite state machine that is in turn capable of implementing the flowcharts shown in FIGS. 4-6 can be used to implement the intra-field and inter-field alignment device. 
     It is, therefore, apparent that there has been provided in accordance with the present invention a method and apparatus for intra- and inter-field alignment of video images. While this invention has been described in conjunction with preferred embodiments thereof, it is evident that many alternatives, modifications, and variations be apparent to those skilled in the art. Accordingly, applicants intend to embrace all such alternatives, modifications or variations to follow in the spirit and scope of this invention.