Data processing system and method

A method of generating disparity results with low latency in a data processing system that processes elements of a first data set and a second data set, each having a plurality of elements, comprising:

• receiving elements of the first and second data sets, including a first element of the first data set;
• and
• generating a disparity result for the first element before substantially all elements of the first and second data sets have been received;
• receiving successive rows of elements of the first and second data sets;
• selecting a transform window having a transform window height equal to an integral number of such rows;
• and
• selecting a correlation window having a correlation window height equal to an integral number of such rows, wherein the correlation window height is greater than the transform window height;
• wherein the generation of a disparity result for the first element occurs before X rows of elements of the first and second data sets have been received, where X is equal to the correlation window height.

A method of generating disparity results with low latency in a data processing system that processes elements of a first data set and a second data set, each having a plurality of elements, comprising:

• receiving elements of the first and second data sets, including a first element of the first data set that is offset from each of a plurality of selected elements of the second data set by a particular disparity;
• performing transformations on such received elements, including the first element and each of the plurality of selected elements;
• and
• correlating the transformed first element with each of the plurality of transformed selected elements to generate a correlation result for each disparity, while concurrently performing transformations on one or more elements of each of the first and second data sets.

A method of generating disparity results with low latency in a data processing system that processes elements of a first data set and a second data set, each having a plurality of elements, comprising:

• receiving elements of the first and second data sets, including a first element of the first data set that is offset from each of a plurality of selected elements of the second data set by a particular disparity;
• performing transformations on such received elements, including the first element and each of the plurality of selected elements;
• and
• correlating the transformed first element with each of the plurality of transformed selected elements to generate a correlation result for each disparity, while concurrently receiving one or more elements of each of the first and second data sets.

A method of generating disparity results with low latency in a data processing system that processes elements of a first data set and a second data set, each having a plurality of elements, comprising:

• receiving elements of the first and second data sets, including a first element of the first data set that is offset from each of a plurality of selected elements of the second data set by a particular disparity;
• performing transformations on such received elements, including the first element and each of the plurality of selected elements;
• correlating the transformed first element with each of the plurality of transformed selected elements to generate a correlation result for each disparity, while concurrently performing transformations on one or more elements of each of the first and second data sets;
• and
• generating a disparity result for the first element by selecting an optimal one of the correlation results, in accordance with predetermined optimization criteria, while concurrently correlating transformed elements of each of the first and second data sets.

A pipelined system for processing elements of a first data set and a second data set, each having a plurality of elements, and generating disparity results for such elements with low latency, the system comprising:

• a transform unit for receiving elements of the first and second data sets, including a first element of the first data set, and for performing transformations on such received elements, including the first element;
• a correlation unit, coupled to the transform unit, for receiving transformed elements of the first and second data sets, including the transformed first element;
• and
• a disparity generation unit, coupled to the correlation unit, for generating a disparity result for the first element before substantially all elements of the first and second data sets have been received in the transform unit.

A pipelined system for processing elements of a first data set and a second data set, each having a plurality of elements, and generating disparity results for such elements with low latency, the system comprising:

• a transform unit for receiving elements of the first and second data sets, including a first element of the first data set that is offset from each of a plurality of selected elements of the second data set by a particular disparity, and for performing transformations on such received elements, including the first element and each of the plurality of selected elements;
• a correlation unit for correlating the transformed first element with the plurality of transformed selected elements to generate a correlation result for each disparity, while the transform unit concurrently performs transformation on one or more received elements of each of the first and second data sets;
• and
• a disparity generation unit for generating a disparity result for the first element by selecting an optimal one of the correlation results, in accordance with predetermined optimization criteria, while the correlation unit concurrently correlates transformed elements of each of the first and second data sets.

A method of generating disparity results with low latency in a data processing system that processes elements of a first data set, including a plurality of ordered elements <X1, X2, . . . XM−1, XM>, and a second data set, including a plurality of ordered elements <Y1, Y2, . . . YN−1, YN>, where M and N respectively represent the total number of elements in the first and second data sets, comprising:

• performing a transformation on elements of the first and second data sets, including a plurality of elements Xi, Xi−1, Xi−2, . . . Xi−(D−1) of the first data set, and a plurality of elements Yj, Yj−1, Yj−2, . . . Y(j−k)−(D−1) of the second data set, where D is a desired number of correlation disparities greater than one and k is an integer greater than zero and less than or equal to (D−1), and wherein element Xi is offset from elements Yj, Yj−1, Yj−2, . . . Yj−(D−1) by a first plurality of respective disparities, and an element Xi−k is offset from elements Yj−k, Yj−k)−1, Y(j−k)−2, . . . Y(j−k)−(D−1) by the first plurality of respective disparities;
• correlating transformed element Xi with transformed elements Yj, Yj−1, Yj−2, . . . Yj−(D−1), respectively, to generate a first plurality of D correlation results for element Xi;
• and
• correlating transformed element Xi−k with transformed elements Y(j−k), Y(j−k)−1, . . . Y(j−k)−(D−1), respectively, to generate a second plurality of D correlation results for element Xi−k, wherein element Xi is correlated with element Yj at substantially the same time as element Xi−k is correlated with element Y(j−2k).

A pipelined system for generating disparity results with low latency for elements of a first data set, including a plurality of ordered elements <X1, X2, . . . XM−1, XM>, and a second data set, including a plurality of ordered elements <Y1, Y2, . . . YN−1, YN>, where M and N respectively represent the number of elements in the first and second data sets, comprising:

• a first transform unit for performing a transformation on elements of the first data set, including elements Xi and Xk of the first data set;
• a second transform unit for performing a transformation on elements of the second data set, including elements Yj and Yl of the second data set, wherein element Xi is offset from element Yj by a first disparity, and element Xk is offset from element Yl by a second disparity;
• a first correlation unit, associated with the first disparity, for correlating transformed element Xi with transformed element Yj to generate a first correlation result;
• and
• a second correlation unit, associated with the second disparity, for correlating transformed element Xk with transformed element Yl to generate a second correlation result, wherein the first and second correlation units operate concurrently to generate, respectively, the first and second correlation results.

A pipelined system for generating disparity results with low latency for elements of a first data set, including a plurality of ordered elements <X1, X2, . . . XM−1, XM>, and a second data set, including a plurality of ordered elements <Y1, Y2, . . . YN−1, YN>, where M and N respectively represent the number of elements in the first and second data sets, comprising:

• a first transform unit for performing a transformation on elements of the first data set, including elements Xi and Xi−k of the first data set;
• a second transform unit for performing a transformation on elements of the second data set, including elements Yj and Yj−2k of the second data set, wherein element Xi is offset from element Yj by a first disparity, and element Xi−k is offset from element Yj−2k by a second disparity;
• a first correlation unit, associated with the first disparity, for correlating transformed element Xi with transformed element Yj to generate a first correlation result;
• and
• a second correlation unit, associated with the second disparity, for correlating transformed element Xi−k with transformed element Yj−2k to generate a second correlation result, wherein the first and second correlation units can operate concurrently to generate, respectively, the first and second correlation results.

A pipelined system for generating disparity results with low latency for elements of a first data set, including a plurality of ordered elements <X1, X2, . . . XM−1, XM>, and a second data set, including a plurality of ordered elements <Y1, Y2, . . . YN−1, YN>, where M and N respectively represent the number of elements in the first and second data sets, comprising:

• a first transform unit for performing a transformation on elements of the first data set, including elements Xi, Xi−1, Xi−2, . . . Xi−(D−1) of the first data set, where D is a desired number of correlation disparities greater than one;
• a second transform unit for performing a transformation on elements of the second data set, including elements Yj, Yj−1, Yj−2, . . . Y(j−k)−(D−1) of the second data set, where k is an integer greater than zero and less than or equal to (D−1), and wherein element Xi is offset from elements Yj, Yj−1, Yj−2, . . . Yj−(D−1) by a first plurality of respective disparities, and an element Xi−k is offset from elements Yj−k, Y(j−k)−1, Y(j−k)−2, . . . Y(j−k)−(D−1) by the first plurality of respective disparities;
• and
• a plurality of correlation units, each associated with a particular one of the D correlation disparities, for correlating transformed element Xi with transformed elements Yj, Yj−1, Yj−2, . . . Yj−(D−1), respectively, to generate a first plurality of D correlation results for element Xi, and correlating transformed element Xi−k with transformed elements Y(j−k), Y(j−k)−1, . . . Y(j−k)−(D−1), respectively, to generate a second plurality of D correlation results for element Xi−k, wherein element Xi is correlated with element Yj at substantially the same time as element Xi−k is correlated with element Y(j−2k).

A method of generating disparity results in a data processing system that processes elements of a first data set and a second data set, each having a plurality of elements, comprising:

• receiving elements of the first and second data sets, including a first element of the first data set that is offset from each of a plurality of selected elements of the second data set by a particular disparity;
• performing transformations on such received elements, including the first element and each of the plurality of selected elements;
• correlating the transformed first element with each of the plurality of transformed selected elements to generate a correlation result for each disparity;
• and
• generating a disparity result for the first element via the following steps:
• generating a preliminary disparity result by selecting an optimal one of the correlation results, in accordance with predetermined optimization criteria;
• selecting, as first and second adjacent correlation results, the correlation results for the next higher and next lower disparities from the preliminary disparity result;
• and
• calculating the disparity result via a sub-pixel estimation function of the first and second adjacent correlation results and the preliminary disparity result.

A method for determining the distance of image elements from an aligned first camera and second camera by generating disparity results for such image elements with low latency, comprising:

• obtaining image elements of a first data set and a second data set, representing pixel intensities captured respectively by the first camera and the second camera, the first and second data sets each having a plurality of image elements, including a first image element of the first data set that is offset from each of a plurality of selected image elements of the second data set by a particular disparity;
• performing transformations on such received image elements, including the first image element and each of the plurality of selected image elements;
• correlating the transformed first image element with each of the plurality of transformed selected image elements to generate a correlation result for each disparity, while concurrently performing transformations on one or more image elements of each of the first and second data sets;
• generating a disparity result for the first image element by selecting an optimal one of the correlation results, in accordance with predetermined optimization criteria, while concurrently correlating transformed image elements of each of the first and second data sets;
• and
• determining the distance of the first image element from the first and second cameras, based upon the disparity result.

A scalable correlation unit, for generating disparity results with low latency for elements of a first data set and a second data set, each having a plurality of elements, in a pipelined system having a plurality of such correlation units connected in series, each associated with a particular disparity, the scalable correlation unit comprising:

• a set of inputs for receiving a first transformed element from the first data set, a second transformed element from the second data set, a first current correlation result and a first current disparity associated with the first current correlation result;
• correlation processor for correlating the first and second transformed elements and generating a second current correlation result and a second current disparity associated with the second current correlation result, and for selecting an optimal current correlation result and associated current disparity based upon predetermined optimization criteria;
• and
• a set of delayed outputs for providing the first transformed element and the optimal current correlation result and associated current disparity to be delayed by a first delay, and the second transformed element to be delayed by a second delay.

A scalable correlation unit, for generating and checking the consistency of a plurality of disparity results with low latency for elements of a first data set and a second data set, each having a plurality of elements, in a pipelined system having a plurality of such correlation units connected in series, each associated with a particular disparity, the scalable correlation unit comprising:

• a set of inputs including a first transformed element from the first data set, a second transformed element from the second data set, a first current correlation result and first associated disparity for elements of the first data set, and a second current correlation result and second associated disparity for elements of the second data set;
• a correlation processor for correlating the first and second transformed elements and generating a new correlation result and new associated disparity, and for selecting a first and second optimal current correlation result and associated current disparity, based upon predetermined optimization criteria, for the first and second data sets respectively;
• and
• a set of delayed outputs including the first transformed element and the first optimal current correlation result and associated current disparity to be delayed by a first delay, and the second transformed element and the second optimal current correlation result and associated current disparity to be delayed by a second delay.

A method of generating disparity results with low latency in a data processing system that processes elements of a first data set and a second data set, each having a plurality of elements, comprising:

• receiving elements of the first and second data sets, including a first element of the first data set;
• and
• generating a disparity result for the first element before substantially all elements of the first and second data sets have been received;
• and
• receiving successive rows of elements of the first and second data sets;
• selecting a transform window having a transform window height equal to an integral number of such rows;
• selecting a correlation window having a correlation window height equal to an integral number of such rows, wherein the correlation window height is greater than the transform window height;
• and
• wherein the generation of a disparity result for the first element occurs before X rows of elements of the first and second data sets have been received, where X is equal to the correlation window height.