Method and apparatus for continuous synchronization of a plurality of asynchronous data sources

FIELD OF THE INVENTION

0001The present invention relates in general to continuous synchronization of a plurality of independently clocked asynchronous data sources and in particular, to merging scanner data streams.

BACKGROUND OF THE INVENTION

0002In duplex document scanning applications, it is desirable to merge both front and rear document image acquisition system outputs into a single composite image. It is further desirable to merge the outputs of two image acquisition systems, which are asynchronous to one another. Generally speaking, the image data from the two asynchronous data streams could be interleaved in one of three possible ways, 1) pixel interleaving where each pixel could be n-bits wide, 2) raster interleaving where a raster is comprised of several n-bit bytes, and 3) document interleaving where a document is comprised of several rasters.

0003Merging data from multiple sources can be accomplished in a variety of ways. The first method requires that the data streams be synchronous to one another. For example, one method might implement a master clock on one image acquisition system while the other image acquisition system is synchronized to the master via a phase locking mechanism. From a manufacturing perspective, this requires that two different parts be stocked; a master and a slave. Furthermore, group delays associated with transmitting the master clock between systems would cause a skew between the data and clock of the slave system. This is especially true, and a potential limitation, at high data rates or while transmitting data over long distances.

0004Another scheme for merging data from multiple sources is to have a master clock at the receiver. This master clock is then transmitted to the image acquisition systems. Once again, this scheme presents a problem with group delays which would cause skew between the data and the clock, possibly limiting data rates and transmission distances. Furthermore, the clock frequency of the image acquisition systems in this scenario is dictated by the data receiver making the system less flexible.

0005The method described in U.S. Pat. No. 6,115,377 describes a method wherein the image acquisition systems are allowed to be asynchronous and the receiver merges the data by buffering the data. A problem with this method results from the fact it uses the document length for calculating the image frame size, which is used to calculate the total additional memory requirements (TAMR). This limits the document length to the amount of memory available. Furthermore, it uses the image acquisition system (IAS) offset and therefore places restrictions on the offset between the two streams to be merged. This method requires a moment in time where both data streams are idle or contain invalid data to prevent the buffers from overflowing.

0006It is desirable to allow each image acquisition system, or any other data source, to select a data rate that is appropriate for the application. It is also desirable to allow each system to supply its own clock, completely asynchronous to one another. Finally, it is desirable to synchronize and merge the data from the sources without concern for the length of the data stream or location of valid data.

SUMMARY OF THE INVENTION

0007Briefly, according to one aspect of the present invention a method for continuous synchronization of a plurality of independently clocked asynchronous data sources comprises the steps of: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0008">a) acquiring data units from a plurality of m data sources;</li><li id="ul0002-0002" num="0009">b) designating one of the data sources as a master data source;</li><li id="ul0002-0003" num="0010">c) designating all other data sources except the master data source as slave data sources;</li><li id="ul0002-0004" num="0011">d) set n=1 wherein n is one of the slave data source; <ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0012">d1) set p=1 wherein p is a secondary valid line for the slave data sources;</li></ul></li><li id="ul0002-0005" num="0013">e) compare a secondary valid line p for n slave data source to a reference valid line p for the master data source; <ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0014">e1) if the n secondary valid line p is synchronized to within a predetermined threshold of the reference valid line p go to step f);</li><li id="ul0004-0002" num="0015">e2) if the n secondary valid line p lags the reference valid line p subtract at least one idle pixel from an interline gap in the secondary valid line and go to step e4);</li><li id="ul0004-0003" num="0016">e3) if the n secondary valid line p leads the reference valid line p add at least one idle pixel to an interline gap in the secondary valid line and go to step e4);</li><li id="ul0004-0004" num="0017">e4) set p=p+1 and go to step e);</li></ul></li><li id="ul0002-0006" num="0018">f) compare n to m; <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0019">f1) if n is less than m, set n=n+1, go to step e);</li><li id="ul0005-0002" num="0020">f2) if n is equals m−1, go to step g); and</li></ul></li><li id="ul0002-0007" num="0021">g) assert a lock signal.</li></ul></li></ul>

0022The invention and its objects and advantages will become more apparent in the detailed description of the preferred embodiment presented below.

BRIEF DESCRIPTION OF THE DRAWINGS

<figref idref="DRAWINGS">FIG. 1</figref> shows a timing diagram of a system wherein clock source two is slower than the reference clock source.

<figref idref="DRAWINGS">FIG. 2</figref> shows a timing diagram of a system wherein clock source two is faster than the reference clock source.

<figref idref="DRAWINGS">FIG. 3</figref> illustrates the relationship between the input data from two asynchronous data sources and the resultant output data stream of interleaved data.

<figref idref="DRAWINGS">FIG. 4</figref> illustrates a composite image, which results when two images are merged and there exist a composite raster wherein there is no valid image data.

<figref idref="DRAWINGS">FIG. 5</figref> illustrates a composite image, which results when two images are merged and all composite rasters contain valid image data.

<figref idref="DRAWINGS">FIG. 6</figref> illustrates a high-level block diagram of a system for interleaving data from asynchronous sources.

<figref idref="DRAWINGS">FIG. 7</figref> illustrates the matching rising edges on valid lines of the reference and secondary systems, wherein the rising edges of the secondary system lags the rising edge first system.

<figref idref="DRAWINGS">FIG. 8</figref> illustrates matching rising edges on valid lines of the reference and secondary systems, where the rising edges are aligned.

<figref idref="DRAWINGS">FIG. 9</figref> illustrates a high-level block diagram of the data merge controller.

DETAILED DESCRIPTION OF THE INVENTION

0032The present invention will be directed in particular to elements forming part of, or in cooperation more directly with the apparatus in accordance with the present invention. It is to be understood that elements not specifically shown or described may take various forms well known to those skilled in the art.

0033When two independent clocks are present in a system, there will always be an unknown phase relationship between the two clock sources. Worse yet, no matter what the clock sources are, there will also be a frequency difference. This frequency difference will cause the clocks to move in both time and phase relationship to each other. There are two cases to consider when analyzing this scenario as shown in <figref idref="DRAWINGS">FIG. 1</figref> where Clock Source <b>2</b> is slower than Clock Source <b>1</b>. The other scenario is illustrated in <figref idref="DRAWINGS">FIG. 2</figref> where Clock Source <b>2</b> is faster than Clock Source <b>1</b>. For discussion purposes, Clock Source <b>1</b> will be used as the reference clock source.

0034Although the frequency difference is overly exaggerated in <figref idref="DRAWINGS">FIGS. 1 and 2</figref>, it can be seen from the initial coincident rising edge (t₁) until the next coincident rising edge (t₂) that there is a difference in the number of cycles that each clock goes through. The problem arises when a third system receives this data and is required to maintain a certain relationship between the data being received from both clock sources. In Case I, the data stream associated with Clock Source <b>2</b> is falling behind the data stream associated with Clock Source <b>1</b>. In Case II the opposite condition occurs. Thus, in any given time window there will always be a mismatch between the number of data elements received and the number of data pairs which can be created. This implies that the slower clock source dominates the rate at which data pairs can be created and requires the data interleaving system to have memory to store the excess data coming from the faster data stream.

0035Under continuous data interleaving operation, the interleaving system would have to have an infinite memory depth because it must continuously store the faster systems excess data. However, if a finite limit can be imposed on the size of the data expected, then the interleaving system only requires a memory which is deep enough to hold the excess data which accumulates over the data stream's transmission time. Upon completing the transmission of the frame data from both asynchronous input data streams, some idle time is required to transmit the excess data from the faster data stream. The idle time between data stream transmissions must be long enough for the interleaving system to empty the memory where the excess data has accumulated. Only when the following two conditions are met can a system be developed to handle the interleaving of two or more asynchronous data streams; finite amount of data; and sufficient idle time between data stream transmissions.

0036One application of this method is described below where image data from two asynchronous image acquisition systems of a duplex scanner are to be merged. For the remainder of this disclosure, the preferred embodiment will be limited to a duplex scanner where the front and rear side images of a document are to be merged using the raster interleaving technique. The reader is reminded that pixel interleaving and document interleaving are also possible. Both of which are extensions of raster interleaving.

0000Image Data, A Special Case

0037The preferred embodiment will implement a raster interleaving technique (more generally, record interleaving). In this case, image data is received in packets called rasters from the image acquisition systems (IAS) at 17 MHz. This data is synchronized as discussed later in the text using input FIFOs and sequenced into a composite raster <b>102</b> comprised of both front IAS raster <b>100</b> and rear IAS raster <b>101</b> interleaved as illustrated in <figref idref="DRAWINGS">FIG. 3</figref>. The raster data is output at least twice the input data rate, or 40 MHz, in this particular instance.

0038The simple case composite image <b>72</b> is illustrated in <figref idref="DRAWINGS">FIG. 4</figref>. The front and rear images of a document are independently received from two asynchronous image acquisition systems. Once each raster of the front image <b>70</b> has been paired with its corresponding raster from the rear image <b>71</b>, a composite image <b>72</b> is created. This single image can then be processed by a single image processor. To avoid initial condition anomalies around the perimeter of each image, a black border is added. Note that the front and rear images <b>70</b> and <b>71</b> of a document overlap each other such that there exist a composite raster <b>102</b> that does not contain any valid image data.

0039The complex composite image <b>73</b> is illustrated in <figref idref="DRAWINGS">FIG. 5</figref>. In this case, the inter-document gap is so small and/or IAS offset is so large that the front and rear image <b>70</b> and <b>71</b> may overlap multiple documents. The front and rear images <b>70</b> and <b>71</b> of a document are independently received from two asynchronous image acquisition systems and overlap each other such that there is always valid image data in each composite raster. This means that once the complex composite image <b>73</b> is started, it can not be stopped without losing data.

0040This complex composite image <b>73</b> causes the method that is described in U.S. Pat. No. 6,115,377 to fail. The first-in-first-out (FIFOs) would be required to continuously capture image data, which would cause them to overflow. The FIFOs could be reset before the FIFO overflows but this would result in the loss of image data. Both options are unacceptable.

0041Again, it is also possible to perform pixel interleaving, document interleaving as well, or more generally n-bit byte interleaving or file interleaving. Pixel interleaving is impractical for this application since image data is typically arranged in rasters (or records). Similarly, document interleaving is impractical because each rear side of a document image would have to be completely buffered while the front side image is processed; this can be quite costly. Both these approaches may not make sense for image data management but may be similarly applied to other data systems.

0042Referring now to <figref idref="DRAWINGS">FIGS. 6-9</figref> the image merge operation of the preferred embodiment is performed by using input FIFOs to store raster data <b>84</b> and <b>88</b> from both the front image acquisition systems <b>81</b> and rear image acquisition systems <b>82</b>. The basic functional block diagram of the image synchronization system <b>10</b> is shown in <figref idref="DRAWINGS">FIG. 6</figref>. The preferred embodiment describes a system, which is capable of acquiring image raster data <b>84</b> and <b>88</b> from two image acquisition systems <b>81</b> and <b>82</b>, each independently clocked by input clocks <b>83</b> and <b>87</b>. In preferred embodiment, the data rate is 17 Mbyes/sec but in practice, other data rates are also possible depending upon the product needs.

0043Data is written into the front and rear FIFOs synchronized to the IAS clocks <b>83</b> and <b>87</b>, and read out synchronized to the merge controller clock <b>90</b> by the data merge controller <b>95</b>. However because the two FIFO write clocks are asynchronous to each other, a phase skew and difference frequency exists between the front and rear FIFO fill rates. This makes the merge logic very complex but also requires the input FIFOs to have additional memory storage to handle the data requirements imposed by the effects of the phase skew and difference frequency (f_diff) described in the previous section.

0044The clock phase skew translates into a valid line phase skew as shown in <figref idref="DRAWINGS">FIG. 7</figref> which imposes reserving one raster of storage in the input FIFOs to handle this case. In a data merge operation, one IAS's valid line <b>85</b> or <b>86</b> must be selected as the reference valid line <b>21</b>. The reference valid line <b>21</b> will be used to start the merge operation but, as shown in <figref idref="DRAWINGS">FIG. 7</figref>, the secondary valid line <b>22</b> may be nearly an entire raster time out of phase with the reference valid line <b>21</b>. In this case, the reference input FIFO must store one entire raster of input data while the merge logic controller waits for the secondary input FIFO to fill up with its' first valid line of data. Which valid line, front or rear, is selected as the reference has no affect on the additional FIFO memory requirement imposed by the valid line skew. However, the valid line selected as the reference does determine which half of the merged data the front and rear images appear in.

0045However, if one were to align the start of the valid lines <b>23</b> and <b>24</b>, the mis-alignment due to the phase skew and difference frequency would be pushed towards the end of the valid line as shown in <figref idref="DRAWINGS">FIG. 8</figref>. This would remove requirement of reserving one raster of storage in the input FIFOs to handle the valid line phase skew as shown in <figref idref="DRAWINGS">FIG. 7</figref>.

0046Since the IAS's valid lines <b>23</b> and <b>24</b> are asserted at the same time, the data merge controller <b>95</b> could start reading from the reference FIFO as soon as the data is written into the FIFO. Depending on the read clock frequency and when the merge controller starts reading from the FIFO it is possible to have the merge controller finish reading from the reference FIFO immediately after the last piece of data is written.

0047The IAS's valid lines <b>85</b> and <b>86</b> do not need to be asserted exactly at the same time. The amount of skew that could be tolerated depends on a number of factors, such as, but not limited to, interline gap, IAS frequencies and read rate.

0048The data merge controller <b>95</b> receives the asynchronous input data from each source, and, according to the present invention, interleaves said data into a single composite output stream <b>93</b>. For maximum flexibility, according to the present invention, output clock <b>90</b> may operate independently of any of the other clocks in the system, with the only limitation being that the rate of the output clock must satisfy the following condition: <br />Clock out>(clock one+clock two)

0049As shown in <figref idref="DRAWINGS">FIG. 9</figref>, data merge controller <b>95</b> is composed of two data storage unit <b>61</b> and <b>62</b>, a counter <b>60</b> and the merge logic <b>65</b>. The data units arrive at data storage unit one <b>61</b> at a rate of clock one <b>83</b> and at data storage two <b>62</b> at a rate of clock two <b>87</b>. The counter <b>60</b> increments once for each clock pulse of clock one <b>83</b> while valid line one <b>85</b> is active and decrements once for each clock pulse of output clock <b>90</b> in which data is read from data storage unit <b>61</b>. The choice between counting the data from IAS one <b>81</b> or IAS two <b>82</b> does not matter since valid line one <b>85</b> and valid line two <b>86</b> would be aligned and the data would be arriving at the two data storage unit <b>61</b> and <b>62</b> at about the same time. The data storage units <b>61</b> and <b>62</b> stores the data in a first-in-first-out (FIFO) manner. The output clock <b>90</b> clocks the data out of the FIFO to create the composite output stream <b>93</b>. The merge logic <b>65</b> compares the count value <b>64</b> to a predetermine threshold to determine when to start merging data. The data merge logic <b>65</b> also monitors the lock signal <b>63</b>, which indicates when the valid line one <b>85</b> and valid line two <b>86</b> are aligned.

0050In the preferred embodiment, the IAS nominal frequency is 17 MHz and the merge controller's output clock <b>90</b> is at least 2× the IAS clock. The data merge controller <b>95</b> starts reading when the reference FIFO is half full. This causes the reference FIFO to be emptied at the end of the reference valid line. The secondary FIFO is started immediately after the reference FIFO is empty. As long as the secondary FIFO is empty before it is time to start reading from the reference FIFO no additional memory is required. In the preferred embodiment, the reference FIFO needs to hold at least a half a raster and the secondary FIFO only needs to hold one raster worth of data. Since the relation between IAS is controlled, the maximum amount of data that can accumulate in the FIFOs is predictable and there is no need to have an event counter to track valid line one <b>85</b> and valid line two <b>86</b> as was done in U.S. Pat. No. 6,115,377.

0051Besides the phase skew, there is also data accumulating over an image frame time as a consequence of the difference frequency that exists between the two asynchronous clock sources. The difference frequency exists because any two-clock sources, no matter how ideal, will always have some variance between them unless one is phase locked to the other. To find the additional memory requirements imposed by the difference frequency, a detailed analysis of the difference frequency must be done.

0052The maximum difference frequency that exists between the front image acquisition systems clock <b>83</b> and rear and image acquisition systems clock <b>87</b> occurs when one oscillator is at its maximum frequency and the other is at its minimum frequency. This definition yields the following equation for difference frequency (f_diff): <br /><i>f</i>_diff=Nominal Oscillator Frequency/1×10⁶*2<i>*PPM </i>stability  EQ. 1<br /> The oscillator frequency chosen for this example has a nominal operating point of 20 MHz with a +/−100 PPM stability. Using Equation 1 defined above, the maximum difference frequency between the two image acquisition systems is: <br /><i>f</i>_diff=20 MHz/1×10⁶*100*2=4,000 Hz<br /> Once the difference frequency is found the rate at which the two-image acquisition systems clocks slip in relationship to each other must be found. The slip count is found by determining the number of oscillator cycles in the difference frequency, which can be expressed with the following equation: <br />Slip Count=Nominal Oscillator Frequency/<i>f</i>_diff  EQ. 2<br /> Using Equation 2, the slip count is: <br />Slip Count=20 MHz/4,000 Hz=5,000

0053The slip count tells us that for every 5,000 clock cycles there will be a cycle of slippage between the two image acquisition systems. This means that if the two valid lines start at about the same time, after 5,000 clocks one IAS will be ahead one clock cycle and its FIFO will accumulate an extra pixel of data.

0054To keep the two valid lines <b>85</b> and <b>86</b> aligned, one of the IAS must adjust itself to compensate for the extra cycle due to the slippage. This is done by designating one of the IAS as the master (reference) and one as the slave (secondary). The master IAS's output signal valid line will be designated as the reference valid line and the slave IAS's output signal valid line will be designated as the secondary valid line. The slave IAS will monitor the valid line signal from the master IAS. When the slave IAS detects a slip, it will then add or subtract a cycle (idle pixel) to adjust itself for the next valid line. The added or subtracted cycle is added or subtracted from the interline gap. The IAS control logic could be designed such that a small slippage from the ideal alignment would be acceptable. Only when the slippage exceeded some threshold would the slave IAS adjust itself. The tolerance of acceptable slippage and how often the slave IAS is updated would be dependent on the system.

0055Once the slave IAS has adjusted itself to within the tolerance of acceptable slippage, the slave IAS will continuously adjust its valid line signal to stay within the predefined threshold. The slave IAS will also define a lock threshold, which is slightly larger than the predefined adjustment threshold. If the skew between the master and slave valid line remains inside of the lock threshold, a lock signal <b>63</b> will be asserted to indicate that the IAS has not exceeded the lock threshold.

0056The invention has been described in detail with particular reference to certain preferred embodiments thereof, but it will be understood that variations and modifications can be effected within the scope of the invention.

PARTS LIST

0000<ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0057"><b>10</b> image synchronization system</li><li id="ul0006-0002" num="0058"><b>21</b> reference valid line</li><li id="ul0006-0003" num="0059"><b>22</b> secondary valid line</li><li id="ul0006-0004" num="0060"><b>23</b> reference valid line (aligned)</li><li id="ul0006-0005" num="0061"><b>24</b> secondary valid line (aligned)</li><li id="ul0006-0006" num="0062"><b>60</b> counter</li><li id="ul0006-0007" num="0063"><b>61</b> data storage one</li><li id="ul0006-0008" num="0064"><b>62</b> data storage two</li><li id="ul0006-0009" num="0065"><b>63</b> lock signal</li><li id="ul0006-0010" num="0066"><b>64</b> count value</li><li id="ul0006-0011" num="0067"><b>65</b> data merge logic</li><li id="ul0006-0012" num="0068"><b>70</b> front image</li><li id="ul0006-0013" num="0069"><b>71</b> rear image</li><li id="ul0006-0014" num="0070"><b>72</b> composite image</li><li id="ul0006-0015" num="0071"><b>73</b> complex composite image</li><li id="ul0006-0016" num="0072"><b>81</b> IAS one</li><li id="ul0006-0017" num="0073"><b>82</b> IAS two</li><li id="ul0006-0018" num="0074"><b>83</b> IAS clock one</li><li id="ul0006-0019" num="0075"><b>84</b> IAS data in one</li><li id="ul0006-0020" num="0076"><b>85</b> IAS valid line one</li><li id="ul0006-0021" num="0077"><b>86</b> IAS valid line two</li><li id="ul0006-0022" num="0078"><b>87</b> IAS clock two</li><li id="ul0006-0023" num="0079"><b>88</b> IAS data in two</li><li id="ul0006-0024" num="0080"><b>90</b> merge controller clock</li><li id="ul0006-0025" num="0081"><b>93</b> single composite output stream</li><li id="ul0006-0026" num="0082"><b>95</b> data merge controller</li><li id="ul0006-0027" num="0083"><b>100</b> front IAS raster</li><li id="ul0006-0028" num="0084"><b>101</b> rear IAS raster</li><li id="ul0006-0029" num="0085"><b>102</b> composite IAS raster</li></ul>