Systems and methods for row causal scan-order optimization stereo matching

Systems and methods to determine a disparity map using row causal scanline optimization stereo matching are presented. A method includes, for each corresponding pixel P between a pair of input stereo images, and for each considered disparity, determining a basic match cost and a match cost for each of a set of given orientations including an east orientation and one or more other orientations, determining an overall match cost for each pixel at each considered disparity based on a sum of the determined match costs for all considered orientations for each pixel and disparity pair, and determining a resulting disparity for each pixel based on a minimum of the determined overall match costs, where a subset of the determined resulting disparities becomes available prior to completion of the input images being read in, and where the resulting disparities for all pixels are determined in a single pass through the input images.

BACKGROUND

A camera may produce radiometric measurements of the space within its field of view. It may periodically produce an image, or collection of these measurements. Each radiometric measurement may provide some information about the intensity, frequency and/or polarization of the electromagnetic waves traveling along a physical line, from a point on the line towards the camera at the time of the measurement. For example, a monochrome camera may produce measurements of the intensity of visible light traveling along a ray. A color camera may produce measurements R, G and B of the respective red, green and blue components of the visible light traveling along a ray.

Cameras may produce data in raster order, beginning data output at the upper left pixel, and progressing across the top row from left to right, then returning to the beginning of the next row, etc., until the bottom right pixel is reached. This sequence of pixels in raster order may he referred to as a stream of pixels, or a pixel stream. Each row of data can often be referred to as a scanline.

Stereo vision is the reconstruction of a three-dimensional (3D) structure in a 3D scene using two or more images of the 3D scene, each acquired from a different viewpoint. The images of the 3D scene may be obtained using multiple cameras or one moving camera. Two cameras are often used, termed binocular vision, which is similar to human vision through two eyes. With binocular vision, a stereo image is based on a left image as “seen” from a left camera (a perspective from the left) and a right image as “seen” from a right camera (a perspective from the right).

In image processing, more particularly computer vision, the term disparity refers to the difference in coordinates of similar features within left and right images of a stereo image. The disparity of features between the left and right images may be computed as a shift to the left (e.g., in pixels) of an image feature when viewed in the right image. If stereo images have lens distortion, or are not correctly aligned, image rectification may be performed to remove distortion and correct alignment of the images such that disparities exist only in the horizontal direction, Once rectified, stereo matching may be performed by a linear search for correspondence of features. For stereo matching, an algorithm may be used to scan the left and right images (i.e., process pixels of the images in a particular order) to search for matching image features. A pixel and one or more of its surrounding pixels in the left image are compared to all of the disparities in the right image by comparing corresponding pixel groups. Various metrics may be used for the comparisons. Using one of the metrics, the disparity with the best computed match is considered the disparity for the image feature. This minimum match score is an indication that the matched pixels correspond and hence the shift represents the disparity.

Stereo algorithms can be divided into those that can be done in one pass over the image data and algorithms that require multiple passes, One-pass algorithms tend to he the algorithms used for real-time applications due to their low computational cost and latency. These algorithms generally decide what the best disparity answer is for a pixel based upon a small amount of surrounding local image information. Multi-pass algorithms tend to aggregate information from all parts of the image and have tended to produce denser accurate results, but at considerable additional computational cost and latency.

In the drawings, the leftmost digit(s) of a reference number may identify the drawing in which the reference number first appears.

DETAILED DESCRIPTION

Determining stereo correspondence, whether in one pass or several, is a computationally intensive task. Because there is interest in using stereo depth in real time for interactive computer vision tasks, for example, various custom hardware-based solutions for computing stereo correspondence have been explored. The hardware implementations that have had the highest performance in number of disparity results per second and the least cost in terms of memory and gates have been one-pass algorithms.

Presented herein are approaches to stereo matching algorithms suited to fast hardware implementation that aggregate information from a broader area than the immediate intensities surrounding the pixel in question, yet may be utilized in a single pass over the image, with relatively small local storage. Previously demonstrated pipelined stereo architectures may be combined with scan-order optimization where the algorithm used is “causal.” Thus, when choosing the best match for a pixel (or pixel window), the algorithm may only consider information from input data from the current pixel (or pixel window) and pixels (or pixel windows) occurring earlier on the current row, or in previous rows. The notion of “causal” may be generalized slightly to allow the decisions for a pixel (or pixel window) to include all pixels (or pixel windows) from the current row and above. This generalized notion may be termed “row causal.”

At the heart of most stereo algorithms, there is a notion of a measure of dissimilarity between pixels in the left and right images of a stereo image. One such measure is a matching metric called the census metric. The dissimilarity of matching a pixel P in the left image with a. pixel at disparity d from this pixel may be denoted as C(P,d). Dissimilarity may also be called cost or score.

A simplified one-pass stereo algorithm may output a disparity, chosen in a bounded set of D possible values 0, . . . , D−1, that minimizes the dissimilarity. Using this algorithm, the output disparity at pixel P written d*(P), may be chosen such that
C(P,d*(P))=min {C(P,0),C(P,1), . . . ,C(P,D−1)},  Eq. 1
where D is the number of considered disparities. This may be written as:
d*P=minindex/d C(P,d)  Eq. 2

A more complex family of stereo matching methods may exploit the fact that disparity changes mostly smoothly from one pixel to the next, except at depth boundaries. These methods are usually based on minimizing a combined measure of (1) the dissimilarity at each pixel, and (2) the discontinuity of the output disparity map. One common cost considered for a disparity map d(P), and the cost considered in this document, is the sum, at each pixel, of the dissimilarity C(P,d(P)) and of a penalty for discontinuity with each neighboring pixel P′ of P. The considered penalty is zero if d(P)=d(P′); k1 if d(P)=d(P′)+1 or d(P)d(P′)−1; k2 if |d(P)−d(r)|>1, where k1 and k2 are two constants, with k2 greater than k1. The cost of a given disparity map d(P) may then be:
sum/P C(P,d(P))+sum/n k1 [|d(n)−d(P)|=1]+k2 [|d(n)−d(P)|>1]  Eq. 3
where sum/P indicates a sum over all pixels in the image, sum/n indicates a sum over the neighboring pixels n of pixel P, |d(n)−d(P)| is the absolute value of the difference of d(n) and d(P), [X] is the indicator function (i.e., [X] is equal to one if statement X is true and zero if statement X is false).

One then strives to find a disparity map that minimizes this cost, However, finding a global minimum to this optimization problem is usually not possible in real-time, except in very limited cases. For this reason, methods that find approximate solutions to this optimization problem have been proposed. Among these proposed methods, many involve scan-order optimization, i.e., processing independently lines that run through the image, for example image rows, columns, diagonal lines, or lines following a knight's chess move (L-shaped). Scan-order optimization methods are also called “scanline optimization” methods; however, this use conflates the multiple scan orders of the optimization with the scanning of pixels out of the camera. In scan-order methods, the same cost as Eq. 3 above may be optimized, but only pixels in a given scan-order are considered. Processing with a single scan-order can introduce artifacts in the result, such as streaks along the orientation of the scan. For this reason, the method is often repeated with scan-orders of different orientations, so that streaks created for one orientation may be attenuated by the processing at another orientation.

The above-discussed methods that include several scan-orders have been done with multiple passes over an entire image. As a consequence, they cannot produce any output until the source data is entirely available and all but the last pass have been completed. ln addition, these methods often require considerable storage, proportional to the image size multiplied by the number of considered disparities.

Row Causal Disparity Map Generation

To address the above-discussed limitations, systems and methods for determining a disparity map are presented that are row-causal such that rows (or columns, or scan-orders with any given orientation) of pixels may be processed in succession and the output at a given row may depend just on the previous rows. As a result, the latency of the system may be as small as a few rows, and the storage requirement may be optimized such that it is proportional to the size of a single input image scanline (in pixels, for example) multiplied by the number of considered disparities. This process may be described as a simultaneous execution of multiple single-pass scan-order optitnizations.

Embodiments of the systems and methods are now described with reference to the figures, where like reference numbers may indicate identical or functionally similar elements. While specific configurations and arrangements are discussed, it should be understood that this is done for illustrative purposes only. A person skilled in the relevant art will recognize that other configurations and arrangements can be used without departing from the scope of the description. It will be apparent to a person skilled in the relevant art that this can also be employed in a variety of other systems and applications than what is described herein.

The approaches described herein involve processing scan-orders at multiple orientations. For each orientation o of a set of orientations O, for each pixel P, and disparity d, the stereo matching cost for that orientation may be defined as:
Co(P,d)=C(P,d)+min[Co(Po,d),Co(Po,d−1)+k1,Co(Po,d+1)+k1, min/xCo(Po,x)+k2]−min/y Co(Po,y)  Eq. 4
where Podenotes the pixel in orientation o from P, k1 and k2 are additional penalty costs, O is a selected set of orientations, and x and y each represent the range of considered disparities. An overall matching cost C*(P,d) may then be the sum for all orientations o of the set of orientations O of Co(P,d), and the resulting disparity for each pixel is the disparity with minimum C*(P,d) for all disparities: minindex/d C*(P,d).

For clarification, a discussion of orientations o may be appreciated, and may he accomplished with reference to the example shown inFIG. 25.FIG. 25shows an example grid of pixels with a pixel P shown in the center. A location of a pixel P in relation to pixel P may be denoted using compass designations, as shown inFIG. 25, in replacement of the “o” For example, a pixel PNWis the pixel located in the block designated “NW”, which denotes the location of pixel PNWfrom the perspective of pixel P. The immediate neighbor pixels have simple compass designations, but one could include additional orientations, such as the “knight's move” orientations, which are two pixels in any direction from pixel P, followed by one pixel in a perpendicular direction, as is done when moving a knight in a game of chess. These could also be referred to as NNW, WNW, NNE, ENE, ESE, SSE, SSW, WSW, as shown inFIG. 25.

Returning to the discussion of disparity map generation, in order to compute both CS(P,d) (i.e., the scan-order optimization of a pixel including data from the south (S)) and CN(P,d) (i.e., the scan-order optimization of a pixel including data from the north (N)), at least two passes over an entire image would he required. If processing an image in conventional left-to-right, top-to-bottom order, CN(P,d) may easily be computed from data gathered while processing prior pixels, while at any pixel P, CS(P,d) cannot be known, as none of the values CS(PS,d) will be known since PSwould not have been seen yet. Thus, since a single pass over an image is more desirable, an algorithm that includes data from the south (such as, for example, any pixel below the row that contains pixel P in the example shown inFIG. 25) is to be avoided.

There are three natural variants of one-pass scan-order optimization algorithms that may he used. Each variant suggests a slightly different architecture for efficient implementation. First, a “North” example algorithm may consider only orientations from previous rows of an image, for example pixels at the northwest (NW), north (N), and/or northeast (NE) positions from a pixel P, or orientations including knight's moves above the current row (e.g., the L-shaped moves described earlier with reference toFIG. 25that are above the current row). It is clear to one skilled in the art that data from these orientations may be easily included in a computation as the inputs Co(Po,d) and min/j Co(Po,j) may all be computed when the previous row is being processed and can be stored for subsequent use in a single row of storage.

Second, a “North and West” example algorithm (which, herein, may also be considered the “West” example for simplicity) may consider a west (W) orientation in addition to the NW, N, and/or NE orientations. With this algorithm, computing CW(P,d) is slightly more complicated than in the North algorithm, as immediate inputs min/j CW(PW,j) would not be known until all disparities for the previous pixel PWhave been considered. Previously known pipelined stereo hardware has done the disparity computation in an overlapped manner such that all disparities for a pixel could not be considered before the first disparity for the next pixel is considered.

A third example algorithm may consider an east (E) orientation in addition to the NW, N, NE, and/or W orientations. Herein, this algorithm may be called the “Non-South” example (or the “East” example for simplicity). To compute CE(P,d), all pixels in a row need to be processed before CE(PE,d) can be known for any pixel in that row. The definition of “one pass” may be relaxed if the input rows are looked at monotonically. When performing a right-to-left pass on the row, the same sort of dependency on the immediately previous pixel occurs for computing CE(PE,d) as occurs when computing CW(PW,d).

The architectures for the above algorithms will now be described.

North Example

FIG. 1is a block diagram of a system100that may be used to determine a disparity map for a stereo image by incorporating information computed for pixels from the north, which may include the northwest (NW), north (N), and northeast (NE) orientations, according to an embodiment. In this example, the NW, N, and NE orientations are all considered. This was done by way of example and ease of discussion only, and not to be limiting. As would be understood by those of skill in the art, any one or more of these orientations may be considered, as well as alternative orientations such as the knight's move orientations described earlier (e.g., WNW, NNW, NNE, and/or ENE). As can be seen inFIG. 1, data from left and right images of a stereo image may be provided to basic cost logic unit102, which may determine basic costs C(P,d) and provide basic costs C(P,d) and optionally texture information to a north cost logic unit104. North cost logic unit104may compute CNW(P,d), CN(P,d), and CNE(P,d), discussed in more detail below. As also discussed below, north cost logic unit104(or alternatively additional logic units (not shown)) may also compute an overall match cost C*(P,d), along with, for example, minimum score(s), a minimum index, and optionally validity information, and may output an optimal disparity and optionally validity information. Although for each pixel, a disparity (or set of disparities) with minimum matching cost will exist, not all of these “best” disparities will correspond to the imaged scene. Evaluations of the amount of distinctive texture in the source images, as well as properties of the computed costs, and match consistency may be used to evaluate the plausibility of individual disparity estimates.

In greater detail, the North example may be implemented as shown inFIGS. 2-5.FIG. 2depicts logic diagram of a stereo pipeline200in which left and right images of a stereo image may be transformed via transform units206-L and206-R, respectively, and differentially delayed via delay units210-1to210-(n-1) and212-1to212-(n-1), respectively, along a main pipeline, allowing successive computation of match costs via correlation units208-1to208-n and sequential minimization of these match costs, An input into pipeline200may include minimum aggregate scores, which may be provided from a memory. Pipeline200may output a minimum score (i.e., minimum cost), minimum index (i.e., disparity), and optionally other outputs that may include, for example, texture measures and other measures useful for determining validity of a match. In addition, pipeline200may output minimum aggregate scores to the memory. Transform units may just pass images through, or may compute transforms such as the census transform.

FIG. 3depicts a logic diagram of a correlator unit308, which may represent any correlator unit fromFIG. 2, according to an embodiment. Correlator308may include a match cost unit302, an aggregator314, a comparator316, and multiplexors318and320. Match cost unit302. may determine a basic match cost that may be provided to aggregator314along with current minimum aggregate scores for determining further minimum aggregate scores and a combined aggregate score (shown as “A”) that is the sum of the scores determined at each orientation NW, N, and NE. In a classical sense of pipelined stereo hardware, aggregator314would be the identity function, and a bus for the current minimum aggregate scores would have zero width (i.e., these components disappear; the aggregator would simply pass the match cost on to its output A, and the minimum aggregate score lines do nothing, as in the old model). Combined aggregate score “A” may be compared to a current minimum score at comparator316to determine if combined aggregate score “A” is less than the current minimum score, and the output (0 or 1) may be used as the selector input to each of multiplexors318and320. Multiplexor318may output the minimum of combined aggregate score “A” and the current minimum score. Multiplexor320may output a minimum of a current disparity d and a current minimum disparity (shown inFIG. 3as “min index”).

FIG. 4depicts a logic diagram of an aggregator414, which may represent an aggregator such as aggregator314ofFIG. 3, according to an embodiment. Aggregator414may include an aggregator422NW, an aggregator422N, and an aggregator422NE. Aggregators422NW,422N, and422NF may each determine and output respective costs CNW(P,d), CN(P,d), and CNE(P,d) based on basic match cost C(P,d) and the minimum aggregate score at the respective orientation. Each of determined costs CNW(P,d), CN(P,d), and CNE(P,d) may be compared, at respective comparators424NW,424N, and424NE, to a current minimum score for the respective orientation to determine a new minimum score for each respective orientation. Determined costs CNW(P,d), CN(P,d), and CNE(P,d) may also be summed at adder426and output as combined aggregate score “A” as described with reference toFIG. 3.

In an embodiment, the computations of CNW(P,d), CN(P,d), and CNE(P,d) are all very similar, but involve slightly different indexing for their memory accesses. As would be understood from the above description, the aggregator unit414, for the North example, consists of three aggregators for the three orientations (NW, N, and NE) and an adder to compute the sum of their results. At the end of the pipeline, the values of the new minimum score for each orientation (i.e., min/k CNW(P,k), min/k CN(P,k), and min/k CNE(P,k)) may be taken from the minimum aggregate scores bus and stored in memory. For the sake of example, the computation of CN(P,d) will now be discussed. As stated above, the computations of CNW(P,d) and CNE(P,d) would be similar, but would involve slightly different indexing for the memory accesses. It would he understood by those of skill in the art how to compute CNW(P,d) and CNE(P,d) based on the description that follows for CN(P,d). In particular, the case of CNW(P,d) involves accessing a stored value computed in the previous row and one column earlier, while CNE(P,d) involves accessing a stored value computed in the previous row and one column later.

The following algorithm may be used to determine CN(P,d). In this algorithm, PNmay refer to a pixel in the same column but previous row as pixel P, and CN(PN,d) may refer to a computation done at the same pixel on the previous row.
CN(P,d)=C(P,d)+min[CN(PN,d),CN(PN,d−1)+k1,CN(PN,d+1)+k1,CN(PN,j)+k2]−min/k CN(PN,k)  Eq. 5

If the aggregation unit (e.g., aggregator422N) has enough storage for one entry per pixel in a row consisting of CN(PN,d) for all disparities plus one entry for min/j CN(PN,j)+k2, ignoring the case of the first row, then computing CN(P,d) for a particular disparity d may be straightforward. Values for CN(PN,d), CN(PN,d−1), k1, CN(PN,d+1), min/j CN(PN,j), and k2 may be looked up, and the minimum computed. The input cost C(P,d) may be added, and the value of minlk CN(PN,k) may be subtracted. The minimum min/k CN(P,k) may be computed in the correlator pipeline using the minimum aggregate scores bus shown inFIG. 3, and may be stored for access on the next row, where it may be accessed as min/j CN(PN,j)+k2. In this embodiment, disparity zero (0) does not include a cost CN(PN, d−1), while the last correlator does not include a cost CN,(PN,d+1). At the first row of the image, the entries of CN(PN,d) and min/j CN(PN,j)+k2 are not included in the computation or are initialized to zero. A structure for the above-described algorithm to determine CN(P,d) may be seen inFIG. 5, which shows an aggregator522Nusing adders530,532, and534, comparator210, adders538and540, and comparator542. The computed CN(P,d) may also be stored in memory.

North and West Example

In the “North and West” example, irr addition to one or more of the noorthern orientations discussed above, a west orientation is also considered. In this example, the structure may be rearranged such that min/k CW(P,k) may be computed in one pixel-clock time (i.e., costs for all disparities for a pixel may be computed before costs for the next pixel are considered). The block diagram ofFIG. 6shows an example flow of this algorithm, according to an embodiment. Data from left and right images of a stereo image enter a basic match score (C(P,d)) pipeline at646. Match scores for an entire search window may he presented in parallel to the unit that computes CW(P,d) at648, optionally along with other data such as texture data, and CW(P,d) is computed in one pixel-clock time at650. Values for C(P,d) and CW(P,d), along with optional other data such as texture data, may be appropriately delayed and passed, at block652, into a pipeline at block654that computes CNW(P,d), CN(P,d), CNE(P,d), and an overall match cost C*(P,d), along with, for example, minimum score(s), a minimum index, and validity information. From this pipeline, an optimal disparity and optionally validity information may be output. The “North and West” example may similarly be depicted as shown in block diagram700ofFIG. 7, where data from left and right images of a stereo image may be input to a basic cost logic unit702, which may output basic match costs C(P,d) and optionally texture information to a west cost logic unit760. West cost logic unit760may output C(P,d), CW(P,d), and optionally texture information to a north cost logic unit704, which may compute CNW(P,d), CN(P,d), and CNE(P,d). North cost logic unit704(or alternatively additional logic units (not shown)) may also compute an overall match cost C*(P,d), along with, for example, minimum score(s), a minimum index, and optionally validity information, and may output an optimal disparity and optionally validity information. The overall match cost C*(P,d) may be the sum of Co(P,d) over all considered orientations. The optimal disparity for each pixel may be the disparity with the minimum C*(P,d) for all disparities, which may be shown as minindex/d C*(P,d).

In an embodiment, the basic match costs C(P,d) (e.g., summed census scores) may be computed in a pipeline having two delays per correlator for the right image, and one for each pixel of the left image, optionally along with texture measures. In this embodiment, no minimum scores are computed. The scores may be appropriately delayed such that the match score for each disparity, as well as a texture result for a single left pixel are all available simultaneously. An exemplary structure for this embodiment may be as shown in structure800ofFIG. 8, including transform blocks806-L and806-R, match cost units862-1through862-n, delays810-1through810-(n-1), delays812-1through812-(n-1), and delays864-1through864-n (not shown).

In an alternative embodiment, the basic match costs C(P,d) may be computed in a pipeline that delays the left pixels by the number of disparities, and compares each delayed left pixel with the same number of differently delayed right pixels. Although this embodiment would be harder to route, it would require significantly fewer delay stages. An exemplary structure for this embodiment may be as shown in structure900ofFIG. 9, including transform blocks906-L and906-R, match cost units966-1through966-n, delay968, and delays970-1through970-(n-1).

Once basic match costs C(P,d) are available, CW(P,d) for all disparities, as well as min/j CW(P,j) may be computed in one pixel-clock time. The algorithm for computing CW(P,d) may be shown as:
CW(P,d)=C(P,d)+min[CW(PW,d),CW(PW,d−1)+k1,CW(PW,d+1)+k1, min/j CW(PW,j)+k2]−min/k CW(PW,k)  Eq. 6

An implementation of the computation of CW(P,d) for all d and min/j CW(PW,j) may be shown as in module1000ofFIG. 10, according to an embodiment. In module1000, costs CW(P,d) for each disparity may be computed in parallel by cost units1072-1through1072-n based on basic match costs C(P,d) and costs CW(PW,d) that may be obtained from memory accesses, initial basic costs C(P,d), CW(P,d), and optionally texture measures may be appropriately delayed via, for example, delays1074-1through1074-(n-1) and delays1075-1through1075-(n-1) and fed into a second differentially delayed pipeline (discussed below). A min/j CW(P,j) may be determined via comparator1078and stored in memory. An exemplary structure for the above-described algorithm to determine CW(P,d) (shown above as Eq. 6) may be seen inFIG. 11, which shows a cost unit1172(which may represent any of the cost units shown inFIG. 10) including adders1180,1181, and1182, comparator1183, and adders1184and1185.

Once costs C(P,d) and CW(PW,j) are available, their values, and optionally texture measures, may be appropriately delayed and fed into a second differentially delayed pipeline to compute CNW(P,d), CN(P,d), CNE(P,d), an overall match cost C*(P,d), minimum score(s), and a minimum index, as well as optionally validity information, etc.FIG. 12is a logic diagram of a correlation pipeline1200that may be used to process stereo image pixels for the “North and West” example, according to an embodiment. In an embodiment, pipeline1200may include correlator units1286-1through1286-n (one for each disparity) that may receive, in parallel, inputs of C(P,d) and C(P,d) and may compute minimum aggregate scores, a minimum score, a minimum index, and optionally other data, such as, for example, texture measures and other measures that may be used to determine validity of a match. An input into pipeline1200may include minimum aggregate scores, which may be provided from a memory. In addition, pipeline1200may output minimum aggregate scores to the memory.

FIGS. 13A and 13Btogether depict a logic diagram of a correlator1386, which may represent a correlator fromFIG. 12, according to an embodiment. Correlator1386may include aggregators1387NW,1387N, and1387NE, one for each “north” orientation. Each of aggregators1387may receive as inputs basic cost C(P,d) and a current minimum score for its respective orientation. Aggregators1387may output costs CNW(P,d), CN(P,d), and CNE(P,d), respectively. Correlator1386may also include comparators1388NW,1388N, and1388NE, that may each receive as inputs the respective cost CNW(P,d), CN(P,d), or CNE(P,d) computed by respective aggregator1387, and the current minimum score for its respective orientation. Comparators1388may output new minimum scores for their respective orientations to the minimum aggregate scores bus. Correlator1386may also include an adder1389that may sum the costs CNW(P,d), CN(P,d), and CNE(P,d) together with cost CW(P,d). The result of this summing is shown inFIG. 13Aas a combined aggregate score “B”. As shown inFIG. 13B, combined aggregate score “B” may be compared to a current minimum score at comparator1390to determine if combined aggregate score “B” is less than the current minimum score, and the output (0 or 1) may be used as the selector input to each of multiplexors1391and1392. Multiplexor1391may output anew minimum score, the minimum of combined aggregate score “B” and the current minimum score. Multiplexor1392may output anew minimum index, a minimum of a current disparity d and a current minimum index.

In the above “North and West” example, consideration from the north, northeast, and northwest orientations were all considered in addition to the west orientation. This was done by way of example and ease of discussion only, and not to be limiting. As would be understood by those skilled in the art, any orientation or combination of orientations above pixel P may be considered in addition to the west orientation, including the alternative orientations discussed above.

The “Non-South” Example

In this “Non-South” example (which may also be referred to herein as the “East” example), an east (E) orientation is considered in addition to the NW, N, NE, and W orientations. Cost CE(P,d) and min/j CE(P,j) may be computed in one pixel-clock time, but scanning a row of pixels from right to left (from an east (E) orientation). In this example, before starting the right to left scan, a whole row of match costs C(P,d) for each disparity and a whole row of CW(P,d) for each disparity may be stored. In an embodiment, costs CNW(P,d), CN(P,d), and CNE(P,d) may be computed and added to the cost CW(P,d), with the resulting sum stored. In an alternative embodiment, costs CNW(P,d), CN(P,d), and CNE(P,d) may be computed in a final disparity computation as in the “North and West” example (as discussed above with reference toFIGS. 13A and 13B). In the “Non-South” example, the computation of C(P,d) and CW(P,d) may be the same as in the “North and West” example. Once C(P,d) and CW(P,d) are stored, the final computations of CE(P,d) and disparity may be similar to the computations of CW(P,d) and disparity in the “North and West” example. However, the scan goes from right to left, and the correlators have an additional input, namely CE(P,d), as shown inFIG. 14, where NWE correlators1486of correlator pipeline1400each have an additional input of CE(P,d), and also as shown inFIG. 15, where adder1589of partially-shown correlator unit1586has an additional input of CE(P,d).

In an embodiment, storage for C(P,d) and CW(P,d) may be filled from left-to-right and right-to-left for alternate scanline rows with reference to successive pixel locations in the stereo image, which may allow C(P,d) and CW(P,d) to be appropriately available, as CE(P,d) is computed from right to left. This may allow the same storage to be used for both the row on which C(P,d) and CW(P,d) may be computed, as well as for the row in which CE(P,d) may be computed. An example of this is shown inFIG. 16, which depicts successive storage and reading out of scanline data in alternating directions using the same single row of storage, according to an embodiment. In example1651, scanline data from row0may be inserted into a storage line from left to right. When storage of row0data is complete, storage of row1data may begin to be inserted from right to left as row0data is being read out from right to left, as shown in example1653. Example1655shows the progression of the storage of row1data from right to left as row0data is being read out from right to left. When storage of row1data is complete, storage of row2data may begin to be inserted from left to right as row1data is being read out from left to right, as shown in example1657. Example1659shows the progression of the storage of row2data from left to right as row1data is being read out from left to right. Those of skill in the art would recognize that this would continue for the storage and data readouts of the remaining scanline data of the stereo image as needed.

The “Non-South” (or “East”) example may similarly he depicted as shown in block diagram1700ofFIG. 17, where data from left and right images of a stereo image may be input to a basic cost logic unit1702, which may output basic match costs C(P,d) and optionally texture information to a west cost logic unit1760. West cost logic unit1760may output C(P,d). CW(P,d), and optionally texture information to an east cost logic unit1793, which may output C(P,d), CW(P,d), and CE(P,d), and optionally texture information to a north cost logic unit1704. In this example, the east cost logic unit1793may reverse its inputs row by row. North cost logic unit1704may compute CNW(P,d), CN(P,d), CNE(P,d), and output C(P,d), CW(P,d), CE(P,d), CNW(P,d), CN(P,d), CNE(P,d), and optionally texture information to a disparity logic unit1794, which may determine an overall match cost C*(P,d), along with, for example, minimum score(s), a minimum index, and optionally validity information, and may output an optimal disparity and optionally validity information. The overall match cost C*(P,d) may be the sum of Co(P,d) over all considered orientations. The optimal disparity for each pixel may be the disparity with the minimum C*(P,d) for all disparities, which may he shown as: minindex/d C*(P,d). In an embodiment, disparity logic unit1794may include an overall match logic unit1795to determine the overall match cost C*(P,d), and may include a resulting disparity logic unit1796to determine the optimal disparity. As with other block diagrams described herein, the system may be broken down into functional blocks for ease of understanding, but is not to be limited to the breakdowns shown. For example, the functions of the disparity logic unit1794may alternatively be configured as part of the north cost logic unit1704.

The “Non-South” (or “East”) example may also be depicted as shown in block diagram1800ofFIG. 18, where data from left and right images of a stereo image may be input to a cost logic unit1897, which may output C(P,d), CW(P,d), CE(P,d), CNW(P,d), CN(P,d), CNE(P,d), and optionally texture information to a disparity logic unit1894. Disparity logic unit1894may determine an overall match cost C*(P,d), along with, for example, minimum score(s), a minimum index, and optionally validity information, and may output an optimal disparity and optionally validity, which may optionally be stored. As previously discussed, the overall match cost C*(P,d) may be the sum of C(P,d) over all considered orientations, and the optimal disparity for each pixel may be the disparity with the minimum C*(P,d) for all disparities, which may be shown as: minindex/d C*(P,d). Disparity logic unit1894may include an overall match logic unit1895to determine the overall match cost C*(P,d), and may include a resulting disparity logic unit1896to determine the optimal disparity. As with other block diagrams described herein, the system may be broken down into functional blocks for ease of understanding, but is not to be limited to the breakdowns shown. For example, the functions of the disparity logic unit1894may alternatively be configured as part of the cost logic unit1897.

The method discussed above for the “East” example may be summarized as shown in the flow chart1900ofFIG. 19, according to an embodiment. At1902, a basic match costs C(P,d) at each pixel P between a pair of stereo images may be determined for a given set of disparities d. At1904, a match cost CEAST(P,d) for each pixel may be determined based on determined basic match costs C(P,d). At1906, one or more additional match costs for each pixel for one or more other orientations may be determined based on the determined match costs C(P,d). At1908, an overall match cost for each pixel at each of disparities d may be determined based on a sum of the determined match costs for all considered orientations for each pixel and disparity pair, At1910, a resulting; disparity for each pixel may be determined based on a minimum of the determined overall match costs.

Another summarization of the method discussed above for the “East” example may be shown in flow chart2000ofFIG. 20. At2002, for each pixel between a pair of stereo images, and for each considered disparity, a match cost may be determined for each of a set of given orientations of pixel processing, where the set of given orientations includes an east orientation and one or more other orientations. The match cost for the given orientations may incorporate data associated with a pixel located at that orientations from a perspective of pixel P. At2004, an overall match cost may be determined for each pixel at each considered disparity based on a sum of determined match costs for all of the orientations for each pixel and disparity pair. At2006, a resulting disparity for each pixel may be determined based on a minimum of the determined overall match costs.

The respective tasks shown in the examples ofFIGS. 19 and 20may be performed in an overlapping or parallel manner as the image data from the input images is being read in such that a subset of the determined resulting disparities becomes available prior to completion of the input images being read in. This is due, in part, to basing match cost determinations on previously stored match cost determinations for previously read pixels in an optimized way, and in doing so, a latency of disparity determination over prior known systems is significantly reduced. In an embodiment, a latency associated with the determination of the match costs and resulting disparities is proportional to an amount of time it takes to read in a single scanline of image data of the input images. In addition, in an embodiment, the resulting disparities for all pixels of the stereo images may be determined in a single pass through the input images.

In the above “Non-South” example, consideration from the west, north, northeast, and northwest orientations were all considered in addition to the east orientation. This was done by way of example and ease of discussion only, and not to be limiting. As would be understood by those skilled in the art, any orientation or combination of orientations level or above pixel P may be considered in addition to the east orientation, including the alternative orientations discussed above.

Presented above are systems and methods for computing a disparity map that approximate more optimal systems and methods, but are amenable to efficient implementation in hardware, An advantage of the approaches described herein is that each scanline of pixels is processed only once from left to right, and once from right to left, in a single pass, where memory storage is proportional to the size of the scanline multiplied by the number of possible disparity values, time is proportional to the size of the scanline, and hardware computational resources are proportional to the number of disparities. In addition, initial disparity results can be read out before all of the input pixels have entered the system, resulting in the latency of the system being limited to a small number of scanlines of input data, Further, the disparity computed at each pixel benefits from the knowledge of the disparities computed on previous scanlines and other pixels on the current scanline.

Exemplary Systems

FIG. 21is a block diagram of an exemplary system2100in which the methods described herein may be implemented, according to an embodiment. System2100may include a. computing device2101having an image processor2103with one or more logic units2105. System2100may also include cameras2107/2109with sensors2111/2113, respectively. In an embodiment, cameras2107/2109may be integrated with computing device2101. In another embodiment, cameras2107/2109may not he a part of computing device2101. In such an embodiment, image data captured by cameras2107/2109at sensors2111/2113may be provided to computing device2101for processing at image processor2103via input/output (I/O) ports (not shown) at the cameras2107/2109and computing device2101. The communication between the I/O ports may he, for example, wireless communication, wired communication, or via a hand-carried computer-readable medium such as a compact disk, a flash drive, or other data storage device. In an embodiment, image processor2103may execute the methods described herein using one or more logic units2105. One skilled in the art would recognize that the functions described herein may be executed by a single logic unit, or any number of logic units.

One or more features disclosed herein may be implemented in hardware, software, firmware, and combinations thereof including discrete and integrated circuit logic, application specific integrated circuit (ASIC) logic, and microcontrollers, and may be implemented as part of a domain-specific integrated circuit package, or a combination of integrated circuit packages. The terms software and firmware, as used herein, refer to a computer program product including at least one computer readable medium having computer program logic, such as computer-executable instructions, stored therein to cause a computer system to perform one or more features and/or combinations of features disclosed herein. The computer readable medium may be transitory or non-transitory. An example of a transitory computer readable medium may be a digital signal transmitted over a radio frequency or over an electrical conductor, through a local or wide area network, or through a network such as the Internet. An example of a non-transitory, computer readable medium may be a compact disk, a flash memory, or other data storage device.

In an embodiment, some or all of the processing described herein may be implemented as software or firmware, Such a software or firmware embodiment may be illustrated in the context of a computing system2201inFIG. 22. Computing system2201may represent, for example, computing device2101shown inFIG. 21. Computing system2201may include one or more central processing unit(s) (CPU), such as general processor2215, connected to memory2217, one or more secondary storage devices2219, and an image processor2203by a bus2221or similar mechanism. Alternatively, image processor2203may be integrated with general processor2215. Image processor2203may include one or more logic units2205for carrying out the methods described herein. One skilled in the art would recognize that the functions described herein may be executed by a single logic unit, or any number of logic units. Computing system2201may optionally include communication interface(s)2223and/or user interface components2225. The one or more secondary storage devices2219may be, for example, one or more hard drives or the like, and may store instructions2227to be executed by image processor2203and/or general processor2215. In an embodiment, the general processor2215and/or image processor2203may be microprocessors, and software, such as instructions2227, may be stored or loaded into the memory2217for execution by general processor2215and/or image processor2203to provide the functions described herein. As discussed above, in an embodiment, computing system2201may include integrated cameras2207/2209having sensors2211/2213, respectively. In another embodiment, cameras2207/2209may not be integrated with computing system2201. In such an embodiment, communication interface(s)2223may be used to provide image data captured by cameras2207/2209to computing system2201for processing using methods described herein. Note that while not shown, computing system2201may include additional components.

The systems, methods, and computer program products described above may be a part of a larger information system.FIG. 23illustrates such an embodiment, as a system2300. In embodiments, system2300may be a media system although system2300is not limited to this context. For example, system2300may be incorporated into a personal computer (PC), laptop computer, ultra-laptop computer, tablet, touch pad, portable computer, handheld computer, palmtop computer, personal digital assistant (PDA), cellular telephone, combination cellular telephone/PDA, television, smart device (e.g., smart phone, smart tablet or smart television), mobile Internet device (MID), messaging device, data communication device, and so forth.

In embodiments, system2300comprises a platform2302coupled to a display2320. Platform2302may receive content from a content device such as content services device(s)2330or content delivery device(s)2340or other similar content sources. A navigation controller2350comprising one or more navigation features may be used to interact with, for example, platform2302and/or display2320. Each of these components is described in more detail below.

Processor2310may be implemented as Complex Instruction Set Computer (CISC) or Reduced Instruction Set Computer (RISC) processors, x86 instruction set compatible processors, multi-core, or any other microprocessor or central processing unit (CPU). In embodiments, processor2310may comprise dual-core processor(s), dual-core mobile processor(s), and so forth.

Graphics subsystem2315may perform processing of images such as still or video for display. Graphics subsystem2315may be a graphics processing unit (GPU) or a visual processing unit (WU), for example. An analog or digital interface may be used to communicatively couple graphics subsystem2315and display2320. For example, the interface may be any of a High-Definition Multimedia Interface, DisplayPort, wireless HDMI, and/or wireless HD compliant techniques. Graphics subsystem2315could be integrated into processor2310or chipset2305. Graphics subsystem2215could be a stand-alone card communicatively coupled to chipset2305.

In embodiments, display2320may comprise any television type monitor or display. Display2320may comprise, for example, a computer display screen, touch screen display, video monitor, television-like device, and/or a television. Display2320may be digital and/or analog. In embodiments, display2320may be a holographic display. Also, display2320may be a transparent surface that may receive a visual projection. Such projections may convey various forms of information, images, and/or objects. For example, such projections may be a visual overlay for a mobile augmented reality (MAR) application. Under the control of one or more software applications2316, platform2302may display user interface2322on display2320.

In embodiments, content services device(s)2330may be hosted by any national, international and/or independent service and thus accessible to platform2302via the Internet, for example. Content services device(s)2330may be coupled to platform2302and/or to display2320. Platform2302and/or content services device(s)2330may be coupled to a network2360to communicate (e.g., send and/or receive) media information to and from network2360. Content delivery device(s)2340also may be coupled to platform2302and/or to display2320.

In embodiments, content services device(s)2330may comprise a cable television box, personal computer, network, telephone, Internet enabled devices or appliance capable of delivering digital information and/or content, and any other similar device capable of unidirectionally or bidirectionally communicating content between content providers and platform2302and/display2320, via network2360or directly. It will be appreciated that the content may be communicated unidirectionally and/or bidirectionally to and from any one of the components in system2300and a content provider via network2360. Examples of content may include any media information including, for example, video, music, medical and gaming information, and so forth.

Content services device(s)2330receives content such as cable television programming including media information, digital information, and/or other content. Examples of content providers may include any cable or satellite television or radio or Internet content providers. The provided examples are not meant to limit embodiments disclosed herein.

In embodiments, platform2302may receive control signals from navigation controller2350having one or more navigation features. The navigation features of controller2350may be used to interact with user interface2322, for example. In embodiments, navigation controller2350may be a pointing device that may be a computer hardware component (specifically human interface device) that allows a user to input spatial (e.g., continuous and multi-dimensional) data into a computer. Many systems such as graphical user interfaces (GUI), and televisions and monitors allow the user to control and provide data to the computer or television using physical gestures.

Movements of the navigation features of controller2350may be echoed on a display (e.g., display2320) by movements of a pointer, cursor, focus ring, or other visual indicators displayed on the display. For example, under the control of software applications2316, the navigation features located on navigation controller2350may be mapped to virtual navigation features displayed on user interface2322, for example. In embodiments, controller2350may not be a separate component but integrated into platform2302and/or display2320. Embodiments, however, are not limited to the elements or in the context shown or described herein,

In embodiments, drivers (not shown) may comprise technology to enable users to instantly turn on and off platform2302like a television with the touch of a button after initial boot-up, when enabled, for example. Program logic may allow platform2302to stream content to media adaptors or other content services device(s)2330or content delivery device(s)2340when the platform is turned “off” In addition, chipset2305may comprise hardware and/or software support for 5.1 surround sound audio and/or high definition 7.1 surround sound audio, for example. Drivers may include a graphics driver for integrated graphics platforms. In embodiments, the graphics driver may comprise a peripheral component interconnect (PCI) Express graphics card.

In various embodiments, any one or more of the components shown in system2300may be integrated. For example, platform2302and content services device(s)2330may be integrated, or platform2302and content delivery device(s)2340may be integrated, or platform2302, content services device(s)2330, and content delivery device(s)2340may be integrated, for example, in various embodiments, platform2302and display2320may be an integrated unit. Display2320and content service device(s)2330may be integrated, or display2320and content delivery device(s)2340may be integrated, for pie. These examples are not meant to limit the embodiments disclosed herein.

As described above, system2300may be embodied in varying physical styles or form factors.FIG. 24illustrates embodiments of a small form factor device2400in which system2300may be embodied. In embodiments, for example, device2400may be implemented as a mobile computing device having wireless capabilities. A mobile computing device may refer to any device having a processing system and a mobile power source or supply, such as one or more batteries, for example.

As shown inFIG. 24, device2400may comprise a housing2402, a display2404, an input/output (I/O) device2406, and an antenna2408. Device2400also may comprise navigation features2412. Display2404may comprise any suitable display unit for displaying information appropriate for a mobile computing device. I/O device2406may comprise any suitable I/O device for entering information into a mobile computing device. Examples for I/O device2406may include an alphanumeric keyboard, a numeric keypad, a touch pad, input keys, buttons, switches, rocker switches, microphones, speakers, voice recognition devices and software, and so forth. Information also may be entered into device2400by way of microphone. Such information may be digitized by a voice recognition device. The embodiments are not limited in this context.

The following examples pertain to further embodiments.

Example 1 may include a system for use in image processing, comprising an image processor comprising a basic match cost logic unit configured to determine, for a given set of disparities d, a basic match cost C(P,d) at each pixel P between a pair of stereo images input for processing; an east orientation cost logic unit configured to determine a match cost CEast(P,d) for each pixel P based on corresponding determined basic match costs COW), wherein match cost CEast(P,d) incorporates data associated with a pixel located to the east of pixel P; and one or more additional orientation cost logic units configured to determine one or more additional match costs for each pixel P, the one or more additional match costs incorporating data associated with pixels at one or more other directional orientations from a perspective of pixel P. The system may also include a disparity logic unit configured to determine an overall match cost for each pixel P at each of disparities d based on a sum of the determined match costs for all considered orientations for each pixel and disparity pair and determine a resulting disparity for each pixel P based on a minimum of the determined overall match costs, wherein a subset of the determined resulting disparities becomes available prior to completion of the input images being read in, and wherein the resulting disparities for all pixels of the stereo images are determined in a single pass through the input images. The system may also include a memory, in communication with the image processor, that is used to store necessary data in the determination of the match costs and resulting disparities.

Example 2 may include the subject matter of example 1, wherein the one or more additional orientation cost logic units include a west orientation cost logic unit configured to determine a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P; and wherein, prior to starting the determination of match costs CEast(P,d), the determined basic match costs C(P,d) and match costs CWest(P,d) at each disparity for a scanline row of pixels are stored such that basic match costs C(P,d) and match costs CWest(P,d) are made available as necessary to determine CEast(P,d) in right to left order.

Example 3 may include the subject matter of example 2, wherein the determined basic match costs C(P,d) and match costs CWest(P,d) are stored from left-to-right and right-to-left for alternate scanline rows with reference to pixel locations of the input images such that the same storage can be used for both the row in which C(P,d) and CWest(P,d) are computed and for the row in which CEast(P,d) is computed.

Example 4 may include the subject matter of any of examples 1-3, wherein a minimum storage capacity of the memory for the determination of match costs is proportional to a value representing the number of pixels of a single scanline of pixels of the input images multiplied by a value representing the number of considered disparities.

Example 5 may include the subject matter of any of examples 1-4, wherein a latency associated with the determination of the match costs and resulting disparities is proportional to an amount of time it takes to read in a single scanline of image data of the input images.

Example 6 may include the subject matter of any of examples 1, 4, and 5, wherein the one or more additional orientation cost logic units include one or more of a west orientation cost logic unit configured to determine a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P; and one or more north orientation cost logic units configured to determine one or more northern-orientated match costs for each pixel P based on corresponding determined basic match costs C(P,d), wherein the one or More northern-orientated match costs include one or more of CNorth(P,d) that incorporates data associated with a pixel located to the north of pixel P, CNorthwest(P,d) that incorporates data associated with a pixel located to the northwest of pixel P, and CNortheast(P,d) that incorporates data associated with a pixel located to the northeast of pixel P.

Example 7 may include the subject matter of any of examples 1 and 4-6, wherein the one or more additional orientation cost logic units include one or more alternative orientation cost logic units configured to determine one or more alternative-orientated match costs for each pixel P based on corresponding determined basic match costs C(P,d), wherein the alternative-orientated match costs incorporate data associated with pixels other than pixels located east, west, north, northwest, northeast, and anywhere south of pixel P.

Example 8 may include a computer program product for image processing, including at least one non-transitory computer readable medium having computer program logic stored therein, the computer program logic including: logic to cause a processor to determine, for a given set of disparities d, a basic match cost C(P,d) at each pixel P between a pair of stereo images input for processing; logic to cause the processor to determine a match cost CEast(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CEast(P,d) incorporates data associated with a pixel located to the east of pixel P; logic to cause the processor to determine one or more additional match costs for each pixel P, the one or more additional match costs incorporating data associated with pixels at one or more other directional orientations from a perspective of pixel P; logic to cause the processor to determine an overall match cost for each pixel P at each of disparities d based on a sum of the determined match costs for all considered orientations for each pixel and disparity pair; and logic to cause the processor to determine a resulting disparity for each pixel P based on a minimum of the determined overall match costs, wherein a subset of the determined resulting disparities becomes available prior to completion of the input images being read in, and wherein the resulting disparities for all pixels of the stereo images are determined in a single pass through the input images.

Example 9 may include the subject matter of example 8, wherein the logic to cause the processor to determine one or more additional match costs comprises logic to cause the processor to determine a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P, and wherein the computer program logic further comprises logic to cause the processor to store, prior to starting the determination of match costs CEast(P,d), the determined basic match costs C(P,d) and match costs CWest(P,d) at each disparity for a scanline row of pixels such that basic match costs C(P,d) and match costs CWest(P,d) are made available as necessary to determine CEast(P,d) in right to left order.

Example 10 may include the subject matter of example 9, wherein the computer program logic further comprises logic to cause the processor to store the determined basic match costs C(P,d) and match costs CWest(P,d) from left-to-right and right-to-left for alternate scanline rows with reference to pixel locations of the input images such that the same storage can be used for both the row in which C(P,d) and CWest(P,d) are computed and for the row in which CEast(P,d) is computed.

Example 11 may include the subject matter of any of examples 8-10, wherein a minimum storage capacity for the determination of match costs is proportional to a value representing the number of pixels of a single scanline of pixels of the input images multiplied by a value representing the number of considered disparities.

Example 12 may include the subject matter of any of examples 8-11, wherein a latency associated with the determination of the match costs and resulting disparities is proportional to an amount of time it takes to read in a single scanline of image data of the input images.

Example 13 may include the subject matter of any of examples 8, 11, and 12, wherein the computer program logic further comprises one or more of: logic to cause the processor to determine a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P; and logic to cause the processor to determine one or more northern-orientated match costs for each pixel P based on corresponding determined basic match costs C(P,d), wherein the one or more northern-orientated match costs include one or more of CNorth(P,d) that incorporates data associated with a pixel located to the north of pixel P, CNorthwest( P,d) that incorporates data associated with a pixel located to the northwest of pixel P, and CNortheast(P,d) that incorporates data associated with a pixel located to the northeast of pixel P.

Example 14 may include the subject matter of any of examples 8 and 11-13, wherein the computer program logic further comprises logic to cause the processor to determine one or more alternative-orientated match costs for each pixel P based on corresponding determined basic match costs C(P,d), wherein the alternative-orientated match costs incorporate data associated with pixels other than pixels located east, west, north, northwest, northeast, and anywhere south of pixel P.

Example 15 may include an apparatus for image processing, comprising means for determining, for a given set of disparities d, a basic match cost C(P,d) at each pixel P between a pair of stereo images input for processing; means for determining a match cost CEast(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CEast(P,d) incorporates data associated with a pixel located to the east of pixel P; means for determining one or more additional match costs for each pixel P, the one or more additional match costs incorporating data associated with pixels at one or more other directional orientations from a perspective of pixel P; means for determining an overall match cost for each pixel P at each of disparities d based on a such of the determined match costs for all considered orientations for each pixel and disparity pair; and means for determining a resulting disparity for each pixel P based on a minimum of the determined overall match costs, wherein a subset of the determined resulting disparities becomes available prior to completion of the input images being read in, and wherein the resulting disparities for all pixels of the stereo images are determined in a single pass through the input images,

Example 16 may include the subject matter of example 15, wherein the means for determining one or more additional match costs includes means for determining a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P, and wherein the apparatus further comprises means for storing, prior to starting the determination of match costs CEast(P,d), the determined basic match costs C(P,d) and match costs CWest(P,d) at each disparity for a scanline row of pixels such that basic match costs C(P,d) and match costs CWest(P,d) are made available as necessary to determine CEast(P,d) in right to left order.

Example 17 may include the subject matter of example 16, wherein the determined basic match costs C(P,d) and match costs CWest(P,d) are stored from left-to-right and right-to-left for alternate scanline rows with reference to pixel locations of the input images such that the same storage can be used for both the row in which C(P,d) and CWest(P,d) are computed and for the row in which CEast(P,d) is computed.

In example 18, the subject matter of any of examples 15-17 may optionally include means for storing necessary data in the determination of the match costs, wherein a minimum storage capacity for the determination of match costs is proportional to a value representing the number of pixels of a single scanline of pixels of the input images multiplied by a value representing the number of considered disparities.

Example 19 may include the subject matter of any of examples 15-18, wherein a latency associated with the determination of the match costs and resulting disparities is proportional to an amount of time it takes to read in a single scanline of image data of the input images.

Example 20 may include the subject matter of any of examples 15, 18, and 19, wherein the means for determining one or more additional match costs includes one or more of means for determining a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P; and means for determining one or more northern-orientated match costs for each pixel P based on corresponding determined basic match costs C(P,d), wherein the one or more northern-orientated match costs include one or more of CNorth(P,d) that incorporates data associated with a pixel located to the north of pixel P, CNorthwest(P,d) that incorporates data associated with a pixel located to the northwest of pixel P, and CNortheast(P,d) that incorporates data associated with a pixel located to the northeast of pixel P.

Example 21 may include the subject matter of any of examples 15 and 18-20, wherein the means for determining one or more additional match costs includes means for determining one or more alternative-orientated match costs for each pixel P based on corresponding determined basic match costs C(P,d), wherein the alternative-orientated match costs incorporate data associated with pixels other than pixels located east, west, north, northwest, northeast, and anywhere south of pixel P.

Example 22 may include a method of image processing, comprising determining, by a computing device, for a given set of disparities d, a basic match cost C(P,d) at each pixel P between a pair of stereo images input for processing; determining, by the computing device, a match cost CEast( P,d) far each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CEast(P,d) incorporates data associated with a pixel located to the east of pixel P; determining, by the computing device, one or more additional match costs for each pixel P, the one or more additional match costs incorporating data associated with pixels at one or more other directional orientations from a perspective of pixel P: determining, by the computing device, an overall match cost for each pixel P at each of disparities d based on a sum of the determined match costs for all considered orientations for each pixel and disparity pair; and determining, by the computing device, a resulting disparity for each pixel P based on a minimum of the determined overall match costs, wherein a subset of the determined resulting disparities becomes available prior to completion of the input images being read in, and wherein the resulting disparities for all pixels of the stereo images are determined in a single pass through the input images.

Example 23 may include the subject matter of example 22, wherein determining one or more additional match costs includes determining a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P, and wherein the method further comprises, prior to starting the determination of match costs CEast(P,d), storing determined basic match costs C(P,d) and match costs CWest(P,d) at each disparity for a scanline row of pixels such that basic match costs C(P,d) and match costs CWest(P,d) are made available as necessary to determine CEast(P,d) in right to left order.

Example 24 may include the subject matter of example 23, wherein the determined basic match costs C(P,d) and match costs CWest(P,d) are stored from left-to-right and right-to-left for alternate scanline rows with reference to pixel locations of the input images such that the same storage can be used for both the row in which C(P,d) and CWest(P,d) is computed and for the row in which CEast(P,d) is computed.

Example 25 may include the subject matter of any of examples 22-24, wherein a minimum storage capacity for the determination of match costs is proportional to a value representing the number of pixels of a single scanline of pixels of the input images multiplied by a value representing the number of considered disparities.

Example 26 may include the subject matter of any of examples 22-25, wherein a latency associated with the determination of the match costs and resulting disparities is proportional to an amount of time it takes to read in a single scanline of image data of the input images.

Example 27 may include the subject matter of any of examples 22, 25, and 26, wherein determining one or more additional match costs includes determining one or more of determining a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P; and determining one or more northern-orientated match costs for each pixel P based on corresponding determined basic match costs C(P,d), wherein the one or more northern-orientated match costs include one or more of CNorth(P,d) that incorporates data associated with a pixel located to the north of pixel P, CNorthwest(P,d) that incorporates data associated with a pixel located to the northwest of pixel P, and CNortheast(P,d) that incorporates data associated with a pixel located to the northeast of pixel P.

Example 28 may include the subject matter of any of examples 22 and 25-27, wherein determining one or more additional match costs includes determining one or more alternative-orientated match costs for each pixel P based on corresponding determined basic match costs C(P,d), wherein the alternative-orientated match costs incorporate data associated with pixels other than pixels located east, west, north, northwest, northeast, and anywhere south of pixel P.

Example 29 may include the subject matter of any of examples 22-28, wherein the determining of match costs for each orientation are based on the equation:
Co(P,d)=C(P,d)+min[Co(Pod),Co(Po,d−1)+k1,Co(Po,d+1)+k1, min/x Co(Po,x)+k2]−min/y Co(Po,y)
where

Corepresents the match cost at an orientation o,

C represents a basic match cost,

Porepresents a pixel in orientation o from pixel P,

d represents the considered disparity,

k1 and k2represent defined penalty costs; and

x and y each represent a range of considered disparities.

Example 30 may include the subject matter of any of examples 22-29, wherein the determining basic match costs C(P,d) comprises determining basic match costs C(P,d) for a pixel at each disparity simultaneously.

Example 31 may include the subject matter of any of examples 22-30, wherein the determining match costs CEast(P,d) comprises determining match costs CEast(P,d) for a pixel at all considered disparities in one pixel-clock lime.

Example 32 may include the subject matter of any of examples 22-31, wherein determining one or more additional match costs comprises determining each of the one or more additional match costs for a pixel at all considered disparities in one pixel clock time.

Example 33 may include at least one machine readable medium comprising a plurality of instructions that in response to being executed on a computing device, cause the computing device to carry out a method according to any one of examples 22-32.

Example 34 may include a computer system to perform the method of any one of examples 22-32.

Example 35 may include an apparatus configured to perform the method of any one of examples 22-32.

Example 36 may include a machine to perform the method of any one of examples 22-32. Example 37 may include an apparatus comprising means for performing the method of any one of examples 22-32.

Examples 38 may include a computing device comprising a chipset according to any one of examples 22-32 and memory to process images.

Example 39 may include a system for use in image processing, comprising an image processor comprising a first logic unit configured to, for each pixel P between a pair of stereo images input for processing, and for each considered disparity, determine a match cost for each of a set of given orientations of pixel processing, where the set of given orientations includes an east orientation and one or more other orientations, where the match cost for a given orientation incorporates data associated with a pixel located at that orientation from a perspective of pixel P, and where subsequent match cost determinations are based on previously stored match cost determinations; a second logic unit configured to determine an overall match cost for each pixel P at each considered disparity based on a sum of determined match costs for all of the orientations for each pixel and disparity pair; and a third logic unit configured to determine a resulting disparity for each pixel P based on a minimum of the determined overall match costs, wherein a subset of the determined resulting disparities becomes available prior to completion of the input images being read in, and wherein the resulting disparities for all pixels of the stereo images are determined in a single pass through the input images. The system also may include a memory in communication with the image processor that is used to store necessary data in the determination of the match costs and resulting disparities.

Example 40 may include the subject matter of example 39, wherein the determining of the match cost by the first logic unit comprises determining a basic match cost C(P,d) at each pixel P; determining a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a.

pixel located to the west of pixel P, and determining a match cost CEast(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CEast(P,d) incorporates data associated with a pixel located to the east of pixel P, wherein prior to starting the determination of match costs CEast(P,d), the determined basic match costs C(P,d) and match costs CWest(P,d) at each disparity for a scanline row of pixels are stored such that basic match costs C(P,d) and match costs CWest(P,d) are made available as necessary to determine CEast(P,d) in right to left order.

Example 41 may include the subject matter of example 40, wherein the determined basic match costs C(P,d) and match costs CWest(P,d) are stored from left-to-right and right-to-left for alternate scanline rows with reference to pixel locations of the input images such that the same storage can be used for both the row in which C(P,d) and CWest(P,d) is computed and for the row in which CEast(P,d) is computed.

Example 42 may include the subject matter of any of examples 39-41, wherein a minimum storage capacity in the memory for determining match costs is proportional to a value representing the number of pixels of a single scanline of pixels of the input images multiplied by a value representing the number of considered disparities.

Example 43 may include the subject matter of any of examples 39-42, wherein a latency associated with the determination of the match costs and resulting disparities is proportional to an amount of time it takes to read in a single scanline of image data of the input images.

Example 44 may include a computer program product for image processing, including at least one non-transitory computer readable medium having computer program logic stored therein, the computer program logic including logic to cause a processor to, for each pixel P between a pair of stereo images input for processing, and for each considered disparity, determine a match cost for each of a set of given orientations of pixel processing, where the set of given orientations includes an east orientation and one or more other orientations, where the match cost for a given orientation incorporates data associated with a pixel located at that orientation from a perspective of pixel P. and where subsequent match cost determinations are based on previously stored match cost determinations; logic to cause the processor to determine an overall match cost for each pixel P at each considered disparity based on a sum of determined match costs for all of the orientations for each pixel and disparity pair; and logic to cause the processor to determine a resulting disparity for each pixel P based on a minimum of the determined overall match costs, wherein a subset of the determined resulting disparities becomes available prior to completion of the input images being read in, and wherein the resulting disparities for all pixels of the stereo images are determined in a single pass through the input images.

Example 45 may include the subject matter of example 44, wherein the logic to cause the processor to determine the match cost includes logic to cause the processor to determine a basic match cost C(P,d) at each pixel P; determine a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P, and determine a match cost CEast(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CEast(P,d) incorporates data associated with a pixel located to the east of pixel P, wherein prior to starting the determination of match costs CEast(P,d), the determined basic match costs C(P,d) and match costs CWest(P,d) at each disparity for a scanline row of pixels are stored such that basic match costs C(P,d) and match costs CWest(P,d) are made available as necessary to determine CEast(P,d) in right to left order.

Example 46 may include the subject matter of any of examples 45, wherein the computer program logic further comprises logic to cause the processor to store the determined basic match costs C(P,d) and match costs CWest(P,d) from left-to-right and right-to-left for alternate scanline rows with reference to pixel locations of the input images such that the same storage can be used for both the row in which C(P,d) and CWest(P,d) are computed and for the row in which CEast(P,d) is computed.

Example 47 may include the subject matter of any of examples 44-46, wherein a minimum storage capacity for the determination of match costs is proportional to a value representing the number of pixels of a single scanline of pixels of the input images multiplied by a value representing the number of considered disparities.

Example 48 may include the subject matter of any of examples 44-47, wherein a latency associated with the determination of the match costs and resulting disparities is proportional to an amount of time it takes to read in a single scanline of image data of the input images.

Example 49 may include means for, for each pixel P between a pair of stereo images input for processing, and for each considered disparity, determining a match cost for each of a set of given orientations of pixel processing, where the set of given orientations includes an east orientation and one or more other orientations, where the match cost for a given orientation incorporates data associated with a pixel located at that orientation from a perspective of pixel P, and where subsequent match cost determinations are based on previously stored match cost determinations; means for determining an overall match cost for each pixel P at each considered disparity based on a sum of determined match costs for all of the orientations for each pixel and disparity pair; and means for determining a resulting disparity for each pixel P based on a minimum of the determined overall match costs, wherein a subset of the determined resulting disparities becomes available prior to completion of the input images being read in, and wherein the resulting disparities for all pixels of the stereo images are determined in a single pass through the input images.

Example 50 may include the subject matter of example 49, wherein the means for determining the match cost comprises means for determining a basic match cost C(P,d) at each pixel P; means for determining a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P. and means for determining a match cost CEast(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CEast(P,d) incorporates data associated with a pixel located to the east of pixel P, wherein prior to starting the determination of match costs CEast(P,d), the determined basic match costs C(P,d) and match costs CWest(P,d) at each disparity for a scanline row of pixels are stored such that basic match costs C(P,d) and match costs CWest(P,d) are made available as necessary to determine CEast(P,d) in right to left order.

Example 51 may include the subject matter of example 50, wherein the determined basic match costs C(P,d) and match costs CWest(P,d) are stored from left-to-right and right-to-left for alternate scanline rows with reference to pixel locations of the input images such that the same storage can be used for both the row in which C(P,d) and CWest(P,d) are computed and for the row in which CEast(P,d) is computed.

In example 52, the subject matter of any of examples 49-51 may optionally include means for storing necessary data in the determination of the match costs, wherein a minimum storage capacity for the determination of match costs is proportional to a value representing the number of pixels of a single scanline of pixels of the input images multiplied by a value representing the number of considered disparities.

Example 53 may include the subject matter of any of examples 49-52, wherein a latency associated with the determination of the match costs and resulting disparities is proportional to an amount of time it takes to read in a single scanline of image data of the input images.

Example 54 may include a method of image processing, comprising, for each pixel P between a pair of stereo images input for processing, and for each considered disparity, determining, by a computing device, a match cost for each of a set of given orientations of pixel processing, where the set of given orientations includes an east orientation and one or More other orientations, where the match cost for a given orientation incorporates data associated with a pixel located at that orientation from a perspective of pixel P, and where subsequent match cost determinations are based on previously stored match cost determinations; determining, by the computing device, an overall match cost for each pixel P at each considered disparity based on a sum of determined match costs for all of the orientations for each pixel and disparity pair; and determining, by the computing device, a resulting disparity for each pixel P based on a minimum of the determined overall match costs, wherein a subset of the determined resulting disparities becomes available prior to completion of the input images being read in, and wherein the resulting disparities for all pixels of the stereo images are determined in a single pass through the input images.

Example 55 may include the subject natter of example 54, wherein the determining the match cost comprises determining a basic match cost C(P,d) at each pixel P; determining a match cost CWest(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CWest(P,d) incorporates data associated with a pixel located to the west of pixel P, and determining a match cost CEast(P,d) for each pixel P based on corresponding determined basic match costs C(P,d), wherein match cost CEast(P,d) incorporates data associated with a pixel located to the east of pixel P; and storing, prior to starting the determination of match costs CEast(P,d), the determined basic match costs C(P,d) and match costs CWest(P,d) at each disparity for a scanline row of pixels such that basic match costs C(P,d) and match costs CWest(P,d) are made available as necessary to determine CEast(P,d) in right to left order.

Example 56 may include the subject matter of example 55, wherein the storing comprises storing the determined basic match costs C(P,d) and match costs CWest(P,d) from left-to-right and right-to-left for alternate scanline rows with reference to pixel locations of the input images such that the same storage can be used for both the row in which C(P,d) and CWest(P,d) are computed and for the row in which CEast(P,d) is computed.

Example 57 may include the subject matter of example 55, wherein the determining the basic match cost C(P,d) comprises determining the basic match cost C(P,d) such that basic match costs C(P,d) for a pixel at each disparity are determined simultaneously.

Example 58 may include the subject matter of example 55, wherein the determination of match costs CWest(P,d) for a pixel at all considered disparities occurs in one pixel-clock time.

Example 59 may include the subject matter of example 55, wherein the determination of match costs CEast(P,d) for a pixel at all considered disparities occurs in one pixel-clock time.

Example 60 may include the subject matter of any of examples 54-59 wherein a minimum storage capacity for the determination of match costs is proportional to a value representing the number of pixels of a single scanline of pixels of the input images multiplied by a value representing the number of considered disparities.

Example 61 may include the subject matter of any of examples 54-60, wherein a latency associated with the determination of the match costs and resulting disparities is proportional to an amount of time it takes to read in a single scanline of image data of the input images. Example 62 may include the subject matter of any of examples 54, 60, and 61, wherein the set of given orientations further includes one or more of a west orientation, a north orientation, a northwest orientation, and a northeast orientation.

Example 63 may include the subject matter of any of examples 54 and 60-62, wherein the set of given orientations further includes one or more alternative orientations, wherein the one or more alternative orientations include orientations other than east, west, north, northwest, northeast, and anywhere south of pixel P.

Example 64 may include the subject matter of any of examples 54-63, wherein the determining the match costs for each orientation is based on the equation:
Co(P,d)=C(P,d)+min[Co(Po,d),Co(Po,d−1)+k1,Co(Po,d+1)+k1, min/x Co(Po,x)+k2]−min/y Co(Po,y)
where

Corepresents the match cost at an orientation o of the set of orientations,

C represents a basic match cost,

Porepresents a pixel in orientation o from pixel P,

d represents the considered disparity,

k1 and k2 represent defined penalty costs; and

x and y each represent a range of the considered disparities.

Example 65 may include at least one machine readable medium comprising a plurality of instructions that in response to being executed on a computing device, cause the computing device to carry out a method according to any one of examples 54-64.

Example 66 may include a computer system to perfbrin the method of any one of examples 54-64.

Example 67 may include an apparatus configured to perform the method of any one of examples 54-64.

Example 68 may include a machine to perform the method of any one of examples 54-64.

Example 69 may include an apparatus comprising means for performing the method of any one of examples 54-64.

Example 70 may include a computing device comprising a chipset according to any one of examples 54-64 and memory to process images.

Methods and systems are disclosed herein with the aid of functional building blocks illustrating the functions, features, and relationships thereof. At least some of the boundaries of these functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternate boundaries may be defined so long as the specified functions and relationships thereof are appropriately performed.

While various embodiments are disclosed herein, it should be understood that they have been presented by way of example only, and not limitation. It will be apparent to persons skilled in the relevant art that various changes in form and detail may he made therein without departing from the scope of the methods and systems disclosed herein. Thus, the breadth and scope of the claims should not be limited by any of the exemplary embodiments disclosed herein.

As may be used in this application and in the claims, a list of items joined by the term “one or more of” can mean any combination of the listed terms. For example, the phrases “one or more of A, B or C” can mean A; B; C, A and B; A and C; B and C; or A, B and C.