Methods and systems for coded rolling shutter

Abstract

Methods and systems for coded rolling shutter are provided. In accordance with some embodiments, methods and system are provided that control the readout timing and exposure length for each row of a pixel array in an image sensor, thereby flexibly sampling the three-dimensional space-time value of a scene and capturing sub-images that effectively encode motion and dynamic range information within a single captured image.

Claims

1. A method for reading an image of a scene detected in an image sensor having an array containing a plurality of pixels, the method comprising: obtaining first image data from a first subset of rows of the array to extract a first sub-image of the scene; obtaining second image data from a second subset of rows of the array to extract a second sub-image of the scene, wherein the first subset of rows is different from the second subset of rows; determining flow information based on a motion of brightness patterns between the first sub-image and the second sub-image or determining the flow information by comparing a position of particular points in the first sub-image and the second sub-image; estimating a point spread function for the image based, at least in part, on the determined flow information; and generating a video based, at least in part, on the first sub-image, the second sub-image, and the estimated point spread function.

2. The method of claim 1, wherein a plurality of sub-images that includes the first sub-image and the second sub-image extracted from the image are uniformly distributed between the plurality of rows of the array.

3. The method of claim 1, wherein determining flow information further comprises estimating the optical flow between the first sub-image and the second sub-image.

4. The method of claim 1, further comprising determining an intermediate image that is interpolated between the first sub-image and the second sub-image.

5. The method of claim 4, wherein the first sub-image, the intermediate image, and the second sub-image are combined to create the video.

6. The method of claim 1, further comprising: receiving a coded pattern for reading the plurality of rows of the array, wherein the coded pattern is an interlaced pattern in which readout time for each row is uniformly distributed into the plurality of sub-images.

7. The method of claim 1, further comprising: receiving a coded pattern for reading the plurality of rows of the array, wherein the coded pattern is a staggered pattern in which an order of reading out a subset of the plurality of rows is reversed for the subset.

8. A method for reading an image of a scene detected in an image sensor comprising an array having a plurality of rows of pixels, the method comprising: obtaining a first image of the scene at a first exposure; determining an adjusted exposure time for each of the plurality of rows of the array based at least in part on scene radiance in the first image of the scene, wherein the adjusted exposure time includes a first exposure time for a first row of the plurality of rows and a second exposure time for a second row of the plurality of rows and wherein the first exposure time is adjusted to be different from the second exposure time; obtaining a second image of the scene using the first exposure time for the first row of the plurality of rows of the array and the second exposure time for the second row of the plurality of rows of the array; and generating a high dynamic range image based on image data from at least the first row and the second row of the plurality of rows.

9. The method of claim 8, further comprising normalizing image data of the second image of the scene with respect to the adjusted exposure time applied to each of the plurality of rows of the array.

10. The method of claim 8, further comprising determining readout times of the plurality of rows of the array.

11. The method of claim 10, further comprising extracting a plurality of sub-images from the image using the determined readout times and the adjusted exposure times, wherein the plurality of sub-images are uniformly distributed between the plurality of rows in the array.

12. The method of claim 11, further comprising: estimating optical flow between a first sub-image and a second sub-image of the plurality of sub-images, wherein estimating the optical flow comprises estimating the optical flow based on a motion of brightness patterns between the first sub-image and the second sub-image or estimating the optical flow by comparing a position of particular points in the first sub-image and the second sub-image; determining motion information based at least in part on the estimated optical flow; and applying the determined motion information to enhance the high dynamic range image that is generated by combining the plurality of sub-images extracted from the image.

13. A system for reading an image of a scene, the system comprising: an image sensor comprising an array having a plurality of rows; and at least one processor programmed to: obtain first image data from a first subset of rows of the array to extract a first sub-image of the scene; obtain second image data from a second subset of rows of the array to extract a second sub-image of the scene, wherein the first subset of rows is different from the second subset of rows; determine flow information based on a motion of brightness patterns between the first sub-image and the second sub-image or determining the flow information by comparing a position of particular points in the first sub-image and the second sub-image; estimate a point spread function for the image based, at least in part, on the determined flow information; and generate a video based, at least in part, on the first sub-image, the second sub-image, and the estimated point spread function.

14. The system of claim 13, wherein a plurality of sub-images that includes the first sub-image and the second sub-image extracted from the image are uniformly distributed between the plurality of rows of the array.

15. The system of claim 13, wherein the processor is further configured to estimate the optical flow between the first sub-image and the second sub-image.

16. The system of claim 13, wherein the processor is further configured to determine an intermediate image that is interpolated between the first sub-image and the second sub-image.

17. The system of claim 16, wherein the first sub-image, the intermediate image, and the second sub-image are combined to create the video.

18. The system of claim 14, wherein the processor is further configured to: receive a coded pattern for reading the plurality of rows of the array, wherein the coded pattern is an interlaced pattern in which readout time for each row is uniformly distributed into the plurality of sub-images.

19. The system of claim 14, further comprising: receive a coded pattern for reading the plurality of rows of the array, wherein the coded pattern is a staggered pattern in which an order of reading out a subset of the plurality of rows is reversed for the subset.

20. A system for reading an image of a scene, the system comprising: an image sensor comprising an array having a plurality of rows; and at least one processor programmed to: obtain a first image of the scene at a first exposure; determine an adjusted exposure time for each of the plurality of rows of the array based at least in part on scene radiance in the first image of the scene, wherein the adjusted exposure time includes a first exposure time for a first row of the plurality of rows and a second exposure time for a second row of the plurality of rows and wherein the first exposure time is adjusted to be different from the second exposure time; obtain a second image of the scene using the first exposure time for the first row of the plurality of rows of the array and the second exposure time for the second row of the plurality of rows of the array; and generate a high dynamic range image based on image data from at least the first row and the second row of the plurality of rows.

21. The system of claim 20, wherein the at least one processor is further programmed to normalize image data of the second image of the scene with respect to the adjusted exposure time applied to each of the plurality of rows of the array.

22. The system of claim 20, wherein the at least one processor is further programmed to determine readout times of the plurality of rows of the array.

23. The system of claim 22, wherein the at least one processor is further programmed to extract a plurality of sub-images from the image using the determined readout times and the adjusted exposure times, wherein the plurality of sub-images are uniformly distributed between the plurality of rows in the array.

24. The system of claim 23, wherein the at least one processor is further programmed to: estimate optical flow between a first sub-image and a second sub-image of the plurality of sub-images, wherein estimating the optical flow comprises estimating the optical flow based on a motion of brightness patterns between the first sub-image and the second sub-image or estimating the optical flow by comparing a position of particular points in the first sub-image and the second sub-image; determine motion information based at least in part on the estimated optical flow; and apply the determined motion information to enhance the high dynamic range image that is generated by combining the plurality of sub-images extracted from the image.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 illustrates a schematic diagram of a CMOS image sensor.

(2) FIG. 2 illustrates a schematic diagram of a particular pixel in the pixel array of the CMOS image sensor of FIG. 1.

(3) FIG. 3 illustrates a representation of conventional rolling shutter, where the exposure time is fixed for each row and the readout times are linearly shifted from the top row of the pixel array to the bottom row of the pixel array.

(4) FIG. 4 illustrates an example of an image generated from an image sensor implementing the convention rolling shutter mechanism shown in FIG. 3.

(5) FIG. 5 illustrates a representation of a coded rolling shutter mechanism, where readout timing and exposure length can be controlled in accordance with some embodiments of the disclosed subject matter.

(6) FIG. 6 illustrates a representation of the assignment of conventional rolling shutter.

(7) FIG. 7 illustrates a representation of an interlaced readout pattern, where the readout time for one frame can be uniformly distributed into a number of sub-images in accordance with some embodiments of the disclosed subject matter.

(8) FIG. 8 illustrates examples of an input image and two sub-images obtained using the interlaced readout pattern of FIG. 7 in accordance with some embodiments of the disclosed subject matter.

(9) FIG. 9 illustrates a representation of interpolating intermediate images and determining a skew-free image from the obtained sub-images in accordance with some embodiments of the disclosed subject matter.

(10) FIG. 10 illustrates an example of the determined optical flow between the two sub-images in accordance with some embodiments of the disclosed subject matter.

(11) FIG. 11 illustrates an example of a skew-free image interpolated from the obtained sub-images in accordance with some embodiments of the disclosed subject matter.

(12) FIGS. 12A and 12B illustrate representations of a staggered readout pattern, where the readout time for one frame can be uniformly distributed into a number of sub-images and where the order of readout is reversed in accordance with some embodiments of the disclosed subject matter.

(13) FIG. 13 illustrates examples of an input image and three sub-images obtained using the staggered readout pattern of FIG. 12B in accordance with some embodiments of the disclosed subject matter.

(14) FIG. 14 illustrates a representation of a coded exposure pattern for the different rows of the pixel array in accordance with some embodiments of the disclosed subject matter.

(15) FIG. 15 illustrates a process for determining an optimal exposure for each row of the pixel array in accordance with some embodiments of the disclosed subject matter.

(16) FIG. 16 illustrates a representation that includes membership functions used to describe the degree of being saturated, underexposed, or well-exposed in accordance with some embodiments of the disclosed subject matter.

(17) FIG. 17 illustrates examples of images obtained using conventional auto-exposure and the adaptive row-wise auto-exposure mechanism described in FIGS. 14 and 15 in accordance with some embodiments of the disclosed subject matter.

(18) FIG. 18 illustrates examples of images showing that saturation and noise in dark regions are substantially suppressed in response to using the adaptive row-wise auto-exposure mechanism in accordance with some embodiments of the disclosed subject matter.

(19) FIG. 19 illustrates a representation of a staggered readout and multiple exposure coding for high dynamic range imaging and a process for obtaining high dynamic range images and removing motion blur from information encoded in the sub-images in accordance with some embodiments of the disclosed subject matter.

(20) FIG. 20 illustrates examples of an input image, multiple sub-images, a representation of the estimated optical flow, blur kernels, and an output image obtained using the coded pattern of FIG. 19 in accordance with some embodiments of the disclosed subject matter.

(21) FIG. 21 illustrates an alternative representation of an interlaced readout and multiple exposure coding for high dynamic range imaging in accordance with some embodiments of the disclosed subject matter.

(22) FIG. 22 illustrates a representation of a coded rolling shutter pattern for recovering a skew-free video from a single captured image in accordance with some embodiments of the disclosed subject matter.

(23) FIG. 23 illustrates a representation of a voxel and searching for a matching voxel for reconstructing the time-varying appearance for each pixel in accordance with some embodiments of the disclosed subject matter.

(24) FIG. 24 illustrates examples of multiple slices at particular points in time of the skew-free video recovered from a single captured image in accordance with some embodiments of the disclosed subject matter.

(25) FIG. 25 illustrates a representation of a coded rolling shutter pattern that implements intermittent exposure for recovering a skew-free video from a single captured image in accordance with some embodiments of the disclosed subject matter.

DETAILED DESCRIPTION

(26) In accordance with various embodiments, mechanisms for coded shutter are provided. In some embodiments, mechanisms are provided that control the readout timing and exposure length for each row of a pixel array in an image sensor, thereby flexibly sampling the three-dimensional space-time value of a scene and capturing sub-images that effectively encode motion and dynamic range information within a single captured image. Instead of sending out the row-reset and row-select signals sequentially, signals can be sent using a coded pattern.

(27) In some embodiments, the readout timing can be controlled by providing an interlaced readout pattern, such as the interlaced readout pattern shown in FIG. 7, in which the total readout time for one frame is uniformly divided into multiple sub-images (K). Alternatively, the readout timing can be controlled by providing a staggered readout pattern, such as the staggered readout pattern shown in FIGS. 12A and 12B, in which the total readout time for one frame is uniformly divided into multiple sub-images (K) and where the order of readout within K neighboring rows is reversed.

(28) In some embodiments, additionally or alternatively to controlling the readout timing, mechanisms are provided for controlling the exposure length. As described herein, an optimal exposure for each row of a pixel array can be determined. An illustrative coded exposure pattern, where an optimal exposure has been determined for each row of a pixel array, is shown in FIG. 14.

(29) Upon exposing each of the plurality of rows in an image sensor using a coded pattern (e.g., an interlaced readout pattern, a staggered readout pattern, a coded exposure pattern, and/or any suitable combination thereof), a single image is captured that encodes motion and/or dynamic range. From this image, multiple sub-images can be read out or extracted from different subsets of the rows of the pixel array. The multiple sub-images and/or other information encoded in the single captured image can be used to determine optical flow, generate a skew-free image, generate a slow motion video, generate a high dynamic range (HDR) image, etc.

(30) These coded rolling shutter mechanisms can be implemented in an image sensor (such as the image sensor shown in FIG. 1) by modifying the logic of a control unit, such as address generator 110 and without any further hardware modification. More particularly, the logic of address generator can be implemented such that it generates particular row-reset and row-select patterns for coded readout and exposure. Alternatively, an external field-programmable gate array (FPGA) can be used to modify the image sensor.

(31) It should be noted that these mechanisms can be used in a variety of applications, such as skew compensation, recovering slow motion in images of moving objects, high-speed photography, and high dynamic range (HDR) imaging. For example, these mechanisms can be used to improve sampling over the time dimension for high-speed photography. In another example, the coded rolling shutter mechanisms can be used to estimate optical flow, which can be useful for recovering slow motion in an image of a moving object, generating a skew-free image, or removing motion blur in an image due to camera shake. In yet another example, these mechanisms can be used to control readout timing and exposure length to capture high dynamic range images from a single captured image. In a further example, these mechanisms can be used to control readout timing and exposure length to recover a skew-free video from a single captured image.

(32) Referring back to FIG. 3, for conventional rolling shutter, it should be noted that reset time, readout time, and exposure time can be represented by Δt (area 310), Δt.sub.r (area 320), Δt.sub.e (area 330), respectively. For an image sensor with M-number of rows, the reset timing for the y-th row, where y is between 1 and M rows, can be represented by the function t.sub.s(y), and the readout timing can be represented by the function t.sub.r(y). For conventional rolling shutter shown in FIG. 3, the reset time, readout time, and exposure time are the same for each row in the image sensor, but are linearly shifted. The reset timing function t.sub.s(y) is shown by the rising edge of the row-reset signals or line 340. Similarly, the readout timing function t.sub.r(y) is shown by the falling edge of the row-readout signals or line 350. Accordingly, for conventional rolling shutter, t.sub.r(y)=yΔt.sub.r and t.sub.s(y)=t.sub.r(y)−Δt.sub.e−Δt.sub.r−Δt.sub.s.

(33) In accordance with some embodiments of the disclosed subject matter, the reset timing, t.sub.s(y), and the readout timing, t.sub.r(y), can be controlled by the address generator. Accordingly, the address generator can also control the exposure time, Δt.sub.e. For example, FIG. 5 shows an illustrative representation of using the address generator to control the readout timing and exposure length for different rows of an image sensor. As shown in FIG. 5, it should be noted that the readout timing and exposure length for each of rows 510, 520, 530, and 540 can be different.

(34) It should be noted that controlling the readout timing and exposure length for the rows of an image sensor provide greater flexibility for sampling the three-dimensional space-time volume of a scene into a single two-dimensional image. To illustrate this, let E(x,y,t) denote the radiance of a scene point (x,y) at time t, and let S(x,y,t) denote the shutter function of a camera. The captured image, I(x,y), can then be represented as:
I(x,y)=∫.sub.−∞.sup.∞E(x,y,t).Math.S(x,y,t)dt

(35) The coded rolling shutter mechanisms described herein extend the shutter function, S(x,y,t), to two dimensions as both readout timing, t.sub.r(y), and the exposure time, Δt.sub.e, can be row-specific. That is, the shutter function for coded rolling shutter is a function of time and image row index. It should be noted that this is unlike conventional rolling shutter and other shutter mechanisms that are merely one-dimensional functions of time.

(36) As mentioned previously, as there is one row of readout circuits, the readout timings for different rows cannot overlap. This imposes a constraint on readout timing, t.sub.r(y). More particularly, for an image sensor with M rows, the total readout time for one frame is MΔt.sub.r. Each readout timing pattern corresponds to a one-to-one assignment of the M readout timing slots to the M rows. The assignment for conventional rolling shutter is shown in FIG. 6. As shown, the readout times for each row are linearly shifted from the top row of pixels to the bottom row of pixels.

(37) In accordance with some embodiments, these coded rolling shutter mechanisms can be used to better sample the time dimension by controlling (e.g., shuffling) the readout timings, t.sub.r(y), among rows. For example, in some embodiments, an interlaced readout pattern, such as the one shown in FIG. 7, can be used. Alternatively, a staggered readout pattern, such as the one shown in FIGS. 12A and/or 12B, can be used. It should be noted that, as there is one row of readout circuits, the readout timings for different rows in the interlaced readout pattern shown in FIG. 7 and the staggered readout pattern shown in FIGS. 12A and 12B do not overlap.

(38) FIG. 7 is an illustrative example of an interlaced readout pattern in accordance with some embodiments of the disclosed subject matter. In the interlaced readout pattern, the total readout time for one frame can be uniformly distributed into K sub-images. Each sub-image, which is encoded in a single captured image, has M/K rows while preserving full resolution in the horizontal direction. As shown in the interlaced readout pattern of FIG. 7, the total readout time is uniformly distributed into two sub-images (K=2) and each sub-image includes six rows of the pixel array. This is also shown in FIG. 9, where two sub-images I.sub.1 and I.sub.2 (represented by lines 910 and 920, respectively) are read out from a single captured image using the interlaced readout pattern. More particularly, each sub-image is associated with a subset of rows of the pixel array (e.g., a first sub-image with a first set of rows, a second sub-image with a second subset of rows, etc.).

(39) It should be noted that, although FIG. 7 and other figures herein shows that two sub-images I.sub.1 and I.sub.2 are read out from a single captured image using the interlaced readout pattern, any suitable number of K sub-images can be read out from the captured image.

(40) For the interlaced readout pattern, the readout timing, t.sub.r(y) for the y-th row can be represented as follows:

(41) $t_r\left(y\right)=\left(\frac{M\left(y-1\right)}{K}-.Math.\frac{y-1}{K}.Math..Math.\left(M-1\right)+1\right)\Delta t_r,$
where the image sensor has a total of M rows and where └.Math.┘ is the floor function.

(42) In some embodiments, the interlaced readout pattern can be used for skew compensation and high speed photography. More particularly, an address generator, such as address generator 110 of FIG. 1, can send the interlaced readout pattern to a pixel array to capture a single image, where the frame rate is substantially increased and the skew is substantially reduced in the sub-images obtained from the single captured image.

(43) Regarding skew in the sub-images, it should be noted that the time lag between the top row and the bottom row of each sub-image is MΔt.sub.r/K, where M is the total number of rows in the image sensor, Δt.sub.r is the readout time, and K is the number of sub-images. As described above, for conventional rolling shutter, the time lag between the top row and the bottom row for one frame is MΔt.sub.r. Thus, the skew in these sub-images is 1/K time of the skew in conventional rolling shutter. Accordingly, the skew in the K sub-images is substantially reduced from the skew of an image captured using conventional rolling shutter.

(44) In addition, it should be noted that the time lag between two consecutive sub-images is also reduced to MΔt.sub.r/K. Thus, the frame rate increases K times between the obtained sub-images. Accordingly, the frame rate in the K sub-images is substantially increased from the frame rate of an image captured using conventional rolling shutter.

(45) Illustrative examples of the sub-images obtained using the interlaced readout pattern of FIG. 7 are shown in FIG. 8. As shown, sub-images 820 and 830 are read out or extracted from a single captured image 810 that was obtained from an image sensor using the interlaced readout pattern. It should be noted that the skew in sub-images 820 and 830 is substantially reduced in comparison with the image shown in FIG. 4 that uses conventional rolling shutter.

(46) It should also be noted that cubic interpolation or any other suitable approach can be used to resize sub-images 820 and 830 vertically to full resolution. For example, for a captured input image with a resolution of 640×480 (M=480 and K=2), each sub-image read out from the captured input image has a resolution of 640×240. Note that, using the interlaced readout pattern, full resolution in the horizontal direction is preserved. Each sub-image can be resized to 640×480 or full resolution by interpolation. The interpolated images are represented by solid lines 910 and 920 (FIG. 9) for sub-images I.sub.1 and I.sub.2, respectively, where the circles represent the sampled points from the input coded image (e.g., image 810 of FIG. 8).

(47) In some embodiments, the extracted sub-images can be used to estimate optical flow. As described above, cubic interpolation or any other suitable interpolation approach can be used to resize the two sub-images I.sub.1 and I.sub.2 vertically to full resolution (shown as solid lines 910 and 920 in FIG. 9). The optical flow u.sub.0 can be determined between the two sub-images. For example, the optical flow can be determined based on the motion of the brightness patterns between the two sub-images. In another example, flow vectors can be determined by comparing the position of particular points in the two sub-images. FIG. 10 illustrates an example of the determined optical flow between the two sub-images. Estimated optical flow can be used, for example, to recover slow motion, remove skew from an image, and/or remove motion blur caused by camera shake from an image.

(48) Using the determined optical flow, intermediate images within a shaded area 930 and between the interpolated sub-images (I.sub.1 and I.sub.2) can be determined using bidirectional interpolation. For example, in some embodiments, intermediate images can be determined using the following equation:
I.sub.w(p)=(1−w)I.sub.1(p−wu.sub.w(p))+wI.sub.2(p+(1−w)u.sub.w(p)),
where 0≦w≦1, p=(x,y) represents one pixel, and u.sub.w(p) is the forward-warped optical flow computed as u.sub.w (p+wu.sub.0(p))=u.sub.0(p). For example, as shown in FIG. 9, line 940 shows the intermediate image I.sub.w=0.5 that can be recovered using bidirectional interpolation of the two sub-images. An example of an interpolated intermediate image 1110 calculated based at least in part on the estimated optical flow is shown in FIG. 11.

(49) In some embodiments, a skew-free image can be interpolated from the obtained sub-images. As shown in FIG. 9, line 950 shows the interpolated skew-free image, I.sub.w=0.5.sup.skew-free. This can be done by replacing the scalar w shown in the above-mentioned equation with a vector, such as w=1−(y−1)/(M=1). An example of a skew-free image 1120 generated from input image 810 of FIG. 8 is also shown in FIG. 11. It should be noted that skew-free image 1120 has substantially compensated for the skew shown in FIG. 4.

(50) To illustrate the skew compensation feature of the disclosed subject matter, FIG. 11 also includes images 1130 and 1140 that illustrates the differences between a ground truth image and interpolated images 1110 and 1120 obtained using the interlaced readout pattern. In particular, images 1130 and 1140 illustrate the error calculated between interpolated images 1110 and 1120 and the ground truth image, where the brighter portions of image 1130 and 1140 identify the areas with greater error or difference from the ground truth image. Note that the skew in image 1110 (I.sub.w=0.5) is substantially reduced from the skew shown in FIG. 4 and that image 1120 is nearly skew-free. The small error in skew-free image 1120 can be caused, for example, by occlusions during the estimation of optical flow.

(51) In addition to compensating for skew, in some embodiments, the sub-images read out from the single captured image using the interlaced readout pattern of FIG. 7 or any other suitable interlaced readout pattern and/or one or more interpolated images can be combined to create a slow motion interpolated video from information encoded in a single captured image. That is, for high speed photography, two or more sub-images can be resized to full resolution and arranged to create a slow-motion video (e.g., interpolated images of a person running, resized sub-images of a balloon popping, etc.). For example, upon capturing a single image having a resolution of 1280×1000 and using an interlaced readout pattern with eight sub-images (K=8), the output video can include eight sub-images that each have a resolution of 1280×125. In another example, the eight sub-images can be resized vertically to full resolution and arranged to generate the output video.

(52) It should be noted that motion blur due to camera shake is a common problem in photography. Merely pressing a shutter release button on a camera can in and of itself cause the camera to shake, and unfortunately result in blurred images. The compact form and small lenses of many of these digital cameras only services to increase the camera shake problem.

(53) In some embodiments, the sub-images and the estimated optical flow from the sub-images can be used to remove motion blur from a single image caused by camera shake or any other suitable motion (sometimes referred to herein as “motion de-blurring”). As described above, cubic interpolation or any other suitable interpolation approach can be used to resize the two sub-images I.sub.1 and I.sub.2 vertically to full resolution (see, e.g., FIG. 8). The optical flow u.sub.0 can then be determined or estimated between the two sub-images (see, e.g., FIG. 10), where the optical flow can encode motion information between the sub-images. Using the estimated optical flow, a blur estimation, such as a point spread function (PSF), can be calculated. For example, a point spread function (PSF) can be calculated that represents the spatial motion and/or the speed of the moving camera. Accordingly, an output image can be enhanced and/or substantially de-blurred by applying the calculated point spread function to the output image (e.g., an interpolated sub-image, a combination of the interpolated sub-images, etc.).

(54) Alternatively, in accordance with some embodiments, the readout timing of the image sensor can be controlled by implementing a staggered readout pattern, such as the staggered readout pattern shown in FIGS. 12A and/or 12B. As shown in the staggered readout patterns of FIGS. 12A and 12B, the total readout time for one frame is uniformly divided into multiple sub-images (K). As also shown, the staggered readout pattern reverses the order of readout with every K neighboring rows. Similar to the interlaced readout pattern described above, K sub-images can be extracted from a single coded image, where each sub-image has M/K rows.

(55) In a more particular example, FIG. 12A shows that two sub-images (K=2) are extracted from a single captured image and that the two sub-images are uniformly distributed between the twelve rows of the pixel array. Similarly, FIG. 12B shows that eight sub-images are extracted from a single captured image. It should be noted that the eight sub-images are uniformly distributed between the rows of the pixel array. However, any suitable number of K sub-images can be read out from the captured image using the staggered readout pattern.

(56) For the staggered readout pattern, the readout timing, t.sub.r(y), for the y-th row can be represented as follows:

(57) $t_r\left(y\right)=\left(\left(2.Math.\frac{y-1}{K}.Math.+1\right)K-y+1\right)\Delta t_r.$

(58) It should be noted that the time lag within each sub-image for staggered readout is (M−K+1)Δt.sub.r.

(59) It should also be noted that the time lag between two consecutive sub-images is Δt.sub.r, which is a substantially higher frame rate than the frame rate achieved using conventional rolling shutter. The readout time, Δt.sub.r, is generally between about 15×10.sup.−6 seconds or 15 microseconds and about 40×10.sup.−6 or 40 microseconds. Accordingly, an image sensor that uses staggered readout can be used for ultra-high speed photography of time-critical events, such as a speeding bullet, a bursting balloon, a foot touching the ground, etc.

(60) FIG. 13 illustrates an example of using staggered readout of FIG. 12B for an ultra-high speed photography application. As shown, a single image 1310 is captured using the staggered readout pattern. From single image 1310, eight sub-images are extracted using staggered readout pattern shown in FIG. 12B. Of the eight sub-images, three sub-images 1320, 1330, and 1340 are shown in FIG. 13—i.e., sub-image I.sub.1, sub-image I.sub.4, and sub-image I.sub.8. Because of the substantially higher frame rate in the sub-images obtained from a single captured image, these sub-images can be used to capture the precise moment that the foot touches the ground. In addition, in some embodiments, sub-images I.sub.1 through I.sub.8 can be arranged to provide a smooth motion video that spans a short period of time (e.g., eight sub-images within one frame time).

(61) Generally speaking, high dynamic range (HDR) imaging generally requires either multiple images of a particular scene that are taken with different exposures or specially-designed image sensors and/or hardware. Capturing multiple images of a particular scene with different exposures requires a static scene and a stable camera to avoid ghosting and/or motion blur. Specially-designed image sensors, on the other hand, are expensive. Accordingly, these generally make high dynamic range imaging inconvenient or impractical, especially for handheld consumer cameras.

(62) In accordance with some embodiments, high dynamic range images can be obtained from a single captured image by controlling the exposure length, Δt.sub.e(y), for each row of the pixel array. Moreover, as described herein, by controlling readout timing, Δt.sub.r(y), and the exposure length, Δt.sub.e(y), for each row of the pixel array, high dynamic range images, where motion blur is substantially removed, can be obtained from a single captured image.

(63) FIG. 14 illustrates an example of coded exposures for the different rows of a pixel array in accordance with some embodiments of the disclosed subject matter. Coded row-wise exposure, Δt.sub.e(y), can be used to alleviate the above-mentioned problems for high dynamic range imaging. The dynamic range of scene radiance can be better captured by either adaptively setting the exposure for each row or interlacing multiple exposures into a single image. This avoids taking multiple images of a particular scene and effectively reduces ghosting and motion blur due to camera shake.

(64) In some embodiments, an optimal exposure for each row of the pixel array can be determined (sometimes referred to herein as “adaptive row-wise auto-exposure”) using a process 1500 as illustrated in FIG. 15. As shown, a temporary image of a scene (e.g., a physical object) is captured using an imaging device at 1510. This temporary image can be captured using, for example, an auto-exposure (AE) feature of the imaging device.

(65) In response to capturing the temporary image, an optimal exposure can be determined for each row of the pixel array at 1520. Generally speaking, an optimal exposure for a given row can be determined that minimizes the number of saturated and under-exposed pixels within the row while maintaining a substantially number of pixels well-exposed. As shown in FIG. 16, three membership functions—i.e., μ.sub.s(i), μ.sub.d(i), and μ.sub.g(i)—can be used to describe the degree of being overexposed or saturated (μ.sub.s(i)), underexposed (μ.sub.d(i)), or well-exposed (μ.sub.g(i)) for intensity, i. Scene radiance can be determined by L=I.sub.0(1+sμ.sub.s(I.sub.0)), where s≧0 is a scale factor used to estimate the scene radiance in saturated regions and I.sub.0 is the temporary image.

(66) It should be noted that scene radiance can be measured everywhere except in the saturated regions, where no information is recorded. It should also be noted that a small value for the scale factor, s, corresponds to a conservative auto-exposure algorithm.

(67) Accordingly, the optimal exposure, Δt.sub.e(y), for the y-th row can be found by maximizing the following equation:

(68) $\underset{\Delta t_l\le \Delta t_{e\left(y\right)}\le \Delta t_u}{\max }\underset{x}{.Math.}\mu \left(L\left(x,y\right)\Delta t_e\left(y\right)\right)$
where μ(i) can be defined as:
μ(i)=μ.sub.s(i)+λ.sub.dμ.sub.d(i)+λ.sub.gμ.sub.g(i),
which includes weights λ.sub.d and λ.sub.g and lower and upper bounds of exposure adjustment Δt and Δt.sub.u.

(69) Referring back to FIG. 15, upon determining the optimal exposure for each row by maximizing the above-mentioned equation and modifying the exposure times for each row of the pixel array (e.g., coded adaptive row-wise auto-exposure pattern shown in FIG. 14), a second image is captured, where each row of the pixel array has been adjusted for best capturing scene radiance at 1530.

(70) In some embodiments, the second image (I.sub.c) can be normalized to generate the final output image (I.sub.r) at 1540. For example, in some embodiments, the second image can be normalized by dividing the second image by the row-wise exposure, Δt.sub.e(y). Accordingly:

(71) $I_r\left(x,y\right)=\frac{I_c\left(x,y\right)}{\Delta t_e\left(y\right)}$

(72) Illustrative examples of the images and exposures obtained using process 1500 of FIG. 15 are shown in FIGS. 17 and 18. Images 1710 show images obtained using conventional auto-exposure. Due to conventional auto-exposure, note the saturation in regions 1712 and 1718 and the noise in darkened regions 1714, 1716, and 1720. Images 1730 show an example of coded images (I.sub.c) obtained using row-wise exposures 1732, which are displayed alongside images 1730. Upon normalizing images 1730, images 1740 are the final output images I.sub.r. The output images have been normalized by dividing by the row-wise exposures 1732. FIG. 18 displays enlarged versions of regions 1712 through 1720 from images 1710 and regions 1742 through 1750 from images 1740. As shown, adaptive row-wise auto-exposure produces higher quality images, where the saturation (e.g., the clouds and the text shown in regions 1712, 1718, 1742, and 1748) and the noise in the dark regions (e.g., the statutes and the toys in regions 1714, 1716, 1720, 1744, 1746, and 1750) are substantially suppressed.

(73) It should be noted that the adaptive row-wise auto-exposure mechanism described above requires little to no image processing. However, in some embodiments, additional post-processing, such as de-noising, can be performed. For example, noise amplification along the vertical direction, which can be derived from the exposure patterns, can be considered. In another example, for scenes where the dynamic range is predominantly spanned in the horizontal direction (e.g., a dark room that is being viewed from the outside), the adaptive row-wise auto-exposure mechanism can revert the imaging device to use a conventional auto-exposure feature.

(74) In some embodiments, high dynamic range images can be obtained from a single captured image using the above-mentioned adaptive row-wise auto-exposure approach with the previously described coded readout pattern. Using adaptive row-wise auto-exposure to determine optimal exposure for each row in the pixel array along with a coded readout pattern, multiple exposures can be coded into a single captured image and planar camera motion can be estimated to remove blue due to camera shake.

(75) FIG. 19 illustrates an example of a staggered readout and multiple exposure coding for high dynamic range imaging in accordance with some embodiments. As shown, the pixel array of an image sensor can be coded with staggered readout for three sub-images (K=3) and three exposures—i.e., Δt.sub.e1, Δt.sub.e2, and Δt.sub.e3. Accordingly, from a single input image (I.sub.e), three sub-images, I.sub.1, I.sub.2, and I.sub.3, can be extracted. These sub-images can be resized vertically to full resolution using cubic interpolation or any other suitable interpolation approach.

(76) These sub-images (I.sub.1, I.sub.2, and I.sub.3) can be used to compose a high dynamic range image. For example, for static scenes/cameras, an output high dynamic range image can be produced by combining the sub-images of multiple exposures.

(77) In addition, in some embodiments, these sub-images (I.sub.1, I.sub.2, and I.sub.3) obtained from using coded pattern 1900 can be used to compose a high dynamic range and remove motion blur due to camera shake as shown in process flow 1950. For example, motion blur due to camera shake is a common problem in photography and the compact form and small lenses of handheld digital cameras only services to increase the camera shake problem. For handheld digital cameras, motion blur in images caused by camera shake is inevitable, especially for long exposure times. Accordingly, in some embodiments, where camera shake is an issue, optical flow can be determined between the sub-images to account for the camera shake.

(78) It should be noted that, as the sub-images are obtained using a staggered readout, the time lag between the sub-images is small. Therefore, the camera shake velocity can generally be the same in the sub-images. It should be also noted that, within one frame time, the amount of motion caused by camera shake is small and can be approximated as a planar motion.

(79) In some embodiments, the sub-images, which are sampled at different timings, and the estimated optical flow from the sub-images can be used to remove motion blur from a single image caused by camera shake or any other suitable motion as shown in flow 1950. A motion vector, {right arrow over (u)}=[u.sub.x, u.sub.y], can be estimated from sub-images I.sub.1 and I.sub.2 by the estimated optical flow:
{right arrow over (u)}=average(computeFlow(I.sub.1,I.sub.2−I.sub.1))
The motion vector can be used determine blur kernels. More particularly, by de-blurring two composed images, I.sub.1⊕I.sub.2 and I.sub.1⊕I.sub.2⊕I.sub.3, ringing can be effectively suppressed, where the operator ⊕ denotes that the images are first center-aligned with the motion vector, {right arrow over (u)}, and then added together. The two de-blurred images can be represented as:
I.sub.b1=deblur(I.sub.1⊕I.sub.2,{right arrow over (u)},Δt.sub.e1,Δt.sub.e2)
I.sub.b2=deblur(I.sub.1⊕I.sub.2⊕I.sub.3,{right arrow over (u)},Δt.sub.e1,Δt.sub.e2,Δt.sub.e3)
Accordingly, the output de-blurred high dynamic range (HDR) image can be calculated by the following:

(80) $I_r\left(\frac{I_1}{\Delta t_{e1}}+\frac{I_{b1}}{\Delta t_{e1}+\Delta t_{e2}}+\frac{I_{b2}}{\Delta t_{e1}+\Delta t_{e2}+\Delta t_{e3}}\right)/3$

(81) It should be noted that the optimal exposure ratios Δt.sub.e3:Δt.sub.e2:Δt.sub.e1 (e.g., 8Δt.sub.e1:2 Δt.sub.e1:Δt.sub.e1) can be determined based at least in part on the desired extended dynamic range and the noise amplification due to motion de-blurring. For example, a larger Δt.sub.e3:Δt.sub.e1 exposure ratio provides a larger extended dynamic range, but can also amplify noise during motion de-blurring.

(82) Illustrative examples of the coded input image, sub-images, and output high dynamic range image obtained using the staggered readout and multiple exposure coding 1900 of FIG. 19 are shown in FIG. 20. Image 2010 is the input image (I.sub.e) that is generated according to the coding pattern 1900 of FIG. 19. Images 2020, 2030, and 2040 are the sub-images (I.sub.1, I.sub.2, and I.sub.3) extracted from input image 2010. It should be noted that each sub-image 2020, 2030, and 2040 has a different exposure length to extend the dynamic range. However, for this particular scene, it should also be noted that each sub-image has portions that are dark and noisy, blurry, and/or saturated. For example, as sub-images 2020 and 2030 have shorter exposure times than sub-image 2040, sub-images 2020 and 2030 have greater noise than sub-image 2040. On the other hand, as the exposure time for sub-image 2040 is longer, portions of sub-image 2040 are saturated and exhibit motion blur. Using sub-images 2020 and 2030, the optical flow 2050 can be estimated and blur kernels and de-blurred images can be obtained at 2060. Using the sub-images to remove motion blur caused by camera shake and combining the sub-images of multiple exposures, a high dynamic range output image 2070 can be recovered. It should be noted that high dynamic range image 2070 is substantially higher in quality than an image obtained using conventional rolling shutter and substantially higher in quality than any of the sub-images alone. Accordingly, a larger dynamic range is preserved and motion blur caused by camera shake is effectively removed.

(83) Although FIG. 19 describes the use of staggered readout and multiple exposure coding for obtaining a high dynamic range image, it should be noted that any suitable coded shutter pattern can be used. For example, FIG. 21 illustrates another coding pattern for high dynamic range imaging. Unlike pattern 1900 shown in FIG. 19, pattern 2100 shows an interlaced readout and multiple exposure coding for high dynamic range imaging. In particular, an image sensor that uses coded pattern 2100 obtains three sub-images (I.sub.1, I.sub.2, and I.sub.3) with two different exposures, Δt.sub.e1 and Δt.sub.e2. It should be noted that the exposure lengths for sub-images I.sub.1 and I.sub.2 are the same. Similarly, optical flow can be estimated from sub-images I.sub.1 and I.sub.2 as the time lag between the sub-images is small. In response, the estimated the optical flow can be used to remove motion blur from sub-image I.sub.3, which has a longer exposure time than sub-images I.sub.1 and I.sub.2.

(84) It should be noted that, as described above in connection with interlaced readout patterns, the sub-images obtained using coded pattern 2100 has substantially reduced skew than images obtained using conventional rolling shutter. Accordingly, coded pattern 2100 of FIG. 21 can be used for high dynamic range imaging of moving objects.

(85) In accordance with some embodiments, mechanisms are provided for controlling exposure length and readout times that can recover a skew-free video from a single captured image. Generally speaking, by modeling the scene brightness for one pixel (x,y) over time t as a one-dimensional signal, the corresponding pixel intensity in the captured image is a linear projection of this one-dimensional signal with the exposure pattern. Accordingly, with randomly coded exposure patterns, space-time volume (e.g., a skew-free video) can be reconstructed from a single captured image by exploiting the sparsity in signal gradients.

(86) In a more particular example, a skew-free video can be recovered from a single captured image using compressive sensing techniques. Compressive sensing techniques provide an approach for reconstructing sparse signals from far fewer samples than required by other techniques, such as the Shannon sampling theorem. As described above, the captured image I (x,y) can be described as a line-integral measurement of the space-time volume E (x,y,t). Accordingly, by controlling the shutter function, S (x,y,t), from a single image, several measurements can be acquired within neighboring rows to recover the space-time volume E (x,y,t).

(87) Consider the time-varying appearance of a given pixel (x,y) within one time frame E (x,y,t), where 0≦t≦MΔt.sub.r. This can be discretized into a P-element vector, where

(88) $x={\left[E\left(x,y,\frac{M\Delta t_r}{P}\right),E\left(x,y,\frac{2M\Delta t_r}{P}\right),\mathrm{.Math.},E\left(x,y,M\Delta t_r\right)\right]}^T$
As shown in the coded pattern 2200 of FIG. 22, to reconstruct x from a single captured image, vertical image resolution is traded off and multiple measurements from the K neighboring rows are obtained. It should be noted that this generally assumes that the appearance is similar within a given locality. The reconstruction can be performed every K rows within a sliding window.

(89) If b denotes the intensities of the K neighboring pixels in the input image I, b can be represented as:

(90) $b={\left[I\left(x,y-\frac{K}{2}\right),\mathrm{.Math.},I\left(x,y+\frac{K}{2}-1\right)\right]}^T$
Accordingly, Ax=b, where A is a K×P matrix representing the coding patterns.

(91) The process for recovering a skew-free video from a single captured image begins by obtaining an initial estimate E.sub.0 using, for example, block matching and linear interpolation. In a more particular example, the input image can be normalized by dividing by the exposure such that: I.sub.n(x,y)=I(x,y)/Δt.sub.e(y). Each pixel (x,y) in the normalized image (In) corresponds to a set of sampled voxels in the initial estimate, E.sub.0(x,y,t), where t.sub.s(y)≦t≦t.sub.r(y). These sampled voxels can be used to fill in portions of the initial estimate, E.sub.0.

(92) FIG. 23 illustrates sampled voxels in accordance with some embodiments of the disclosed subject matter. For each sampled voxel, such as voxel 2310 (v.sub.1=(x.sub.1, y.sub.1, t.sub.1)), a search is conducted through the other sampled voxels to find a suitable matching voxel, such as voxel 2320 (v.sub.2=(x.sub.2, y.sub.2, t.sub.2)). It should be noted that the matching voxel can be selected such that error is minimized. For example, in one suitable approach, error can be described as |N.sub.x(v.sub.1)−N.sub.x(v.sub.2)|, where N.sub.x (v) denotes the neighborhood of voxel v in the x-direction. If the minimum error is greater than a preset or predetermined threshold, no suitable matching voxel is found. For each matched pair of voxels, the voxels between the matched pair of voxels can be interpolated as shown by the interpolated voxels 2330 in FIG. 23.

(93) In some embodiments, a particular voxel can be interpolated multiple times. If a particular voxel is interpolated multiple times, the value of that voxel can be set to the result computed from the matched pair with the minimum matching error. This fills in a substantial portion of the initial estimate, E.sub.0. The remaining voxels can then be initialized to the values in the normalized image (I.sub.n(x,y)) at the corresponding rows.

(94) The initial estimate, E.sub.0, can then be used to reconstruct the time-varying appearance x for each pixel by exploiting the sparsity in the gradient of the pixel's radiance over time:
min|x′|+λ|x−x.sub.0|
where |x′| is the L−1 norm of the gradient of x over time, λ is a weight parameter, and x.sub.0 is the corresponding signal in E.sub.0. An optimization using the initial estimate can be run multiple times (e.g., twice). The output of the first iteration can be used to adaptively adjust the values of K for different rows. It should be noted that for rows with large variance in the recovered appearance over time, the K value can be lowered, and vice versa. The adjustment is performed based on a precomputed or predetermined mapping between K values, variances of appearance over time, and reconstruction errors. Multiple iterations can continue to be performed and, in some embodiments, a median filter can be applied prior to generating the final output.

(95) FIG. 24 illustrates examples of multiple slices at particular points in time of the skew-free video. Image 2410 shows an image of a moving truck taken using conventional rolling shutter. As described previously, there is substantial skew exhibited in image 2410. Image 2430 shows a coded input image obtained using obtained using a coding pattern 2420. In some embodiments, coding pattern 2420 can include a randomly coded exposure pattern. Using the approach described above, a skew-free video is reconstructed from input image 2430 by exploiting the sparsity in signal gradients. Images 2440, 2450, 2560, and 2470 illustrate slices taken from the reconstructed skew-free video at particular points in time. It should be noted that each of the images from the skew-free video exhibits substantially reduced skew when compared to image 2410, which was obtained using conventional rolling shutter.

(96) In some embodiments, if a frame buffer is available on the CMOS image sensor, intermittent exposures can be implemented for each pixel, where each pixel can receive multiple row-select and row-reset signals during one frame as shown in FIG. 25. As illustrated in coding pattern 2500, the intermittent exposure allows more complex coding patterns for reconstruction via compressive sensing and, in some embodiments, can achieve better reconstruction results. In addition to correcting for geometric skew, such as geometric distortion of moving options, the proposed coding patterns can be used to compensate for photometric skew, such as the partial exposure caused by uncontrollable flashes.

(97) In some embodiments, hardware used in connection with the coded mechanisms can include an image capture device. The image capture device can be any suitable device for capturing images and/or video, such as a portable camera, a video camera or recorder, a computer camera, a scanner, a mobile telephone, a personal data assistant, a closed-circuit television camera, a security camera, an Internet Protocol camera, etc.

(98) The image capture device can include an image sensor, such as the image sensor shown in FIG. 1. As shown, image sensor 100 includes a pixel array 105 having multiple rows of pixels and an address generator 110. The coded rolling shutter mechanisms can be implemented by modifying the logic of a control unit, such as address generator 110, in the CMOS image sensor of FIG. 1 and without any further hardware modification. More particularly, the logic of address generator can be implemented such that it generates particular row-reset and row-select patterns for coded readout and exposure. Alternatively, an external field-programmable gate array (FPGA) can be used to modify the image sensor.

(99) In some embodiments, the hardware can also include an image processor. The image processor can be any suitable device that can process images and image-related data as described herein. For example, the image processor can be a general purpose device such as a computer or a special purpose device, such as a client, a server, an image capture device (such as a camera, video recorder, scanner, mobile telephone, personal data assistant, etc.), etc. It should be noted that any of these general or special purpose devices can include any suitable components such as a processor (which can be a microprocessor, digital signal processor, a controller, etc.), memory, communication interfaces, display controllers, input devices, etc.

(100) In some embodiments, the hardware can also include image storage. The image storage can be any suitable device for storing images such as memory (e.g., non-volatile memory), an interface to an external device (such as a thumb drive, a memory stick, a network server, or other storage or target device), a disk drive, a network drive, a database, a server, etc.

(101) In some embodiments, any suitable computer readable media can be used for storing instructions for performing the processes described herein. For example, in some embodiments, computer readable media can be transitory or non-transitory. For example, non-transitory computer readable media can include media such as magnetic media (such as hard disks, floppy disks, etc.), optical media (such as compact discs, digital video discs, Blu-ray discs, etc.), semiconductor media (such as flash memory, electrically programmable read only memory (EPROM), electrically erasable programmable read only memory (EEPROM), etc.), any suitable media that is not fleeting or devoid of any semblance of permanence during transmission, and/or any suitable tangible media. As another example, transitory computer readable media can include signals on networks, in wires, conductors, optical fibers, circuits, any suitable media that is fleeting and devoid of any semblance of permanence during transmission, and/or any suitable intangible media.

(102) Accordingly, methods and systems for coded readout of an image are provided.

(103) Although the invention has been described and illustrated in the foregoing illustrative embodiments, it is understood that the present disclosure has been made only by way of example, and that numerous changes in the details of implementation of the invention can be made without departing from the spirit and scope of the invention, which is only limited by the claims which follow. Features of the disclosed embodiments can be combined and rearranged in various ways.