Abstract:
A camera or other optical system is focused by generating a plurality of digital images each obtained with a different focus setting of the optical system. These images are analysed to generate for each image a score (S) by comparing first groups of pixels chosen from the image with second groups chosen from the image such that the pixels of each second group have same respective positional relationships with respect to one another as the pixels of the first group with which it is compared have to one another, the score (S) being a function of the number of matches obtained with said comparisons. The focus setting that gives the score corresponding to the largest number of matches is chosen.

Description:
This application is the U.S. national phase of International Application No. PCT/GB2006/004602 filed 8 Dec. 2006 which designated the U.S. and claims priority to European Patent Application No. 05257796.2 filed 19 Dec. 2005, the entire contents of each of which are hereby incorporated by reference. 
     BACKGROUND AND SUMMARY 
     This invention is concerned with focus control and finds application in cameras, or indeed any optical device where the focus of an image needs to be adjusted. 
     Traditionally there are two approaches to auto-focus: Active (bouncing infra-red from the scene to calculate a distance) and passive (which maximises the intensity difference between adjacent pixels). One example of the second category is described by Geusebrock et al. “Robust autofocusing in microscopy”, Cytometry, vol 39, No. 1 (1 Feb. 2000), pp. 1-9. Here, a ‘focus score’ is obtained for images taken at different focus settings, and best focus is found by searching for the optimum in the focus curve. Both of these approaches have problems, including when the active beam is obscured by fog or mist, where cameras only focus at the centre of the frame, when there&#39;s low contrast across the image, or when the subject matter is horizontally oriented. 
     In application EP1286539A it was described a method of focusing in which a decision as to which part of an image to focus upon (i.e. the subject) is taken by analysing the image to obtain for each picture element a score indicating the degree of dissimilarity of the element and its environment from the remainder of the image: the subject is that part of the image having a high score (i.e. high degree of dissimilarity). The method of generating the score is discussed in greater detail in U.S. Pat. No. 6,934,415. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of a camera in accordance with one embodiment of the invention. 
         FIG. 2  is a flowchart illustrating the operation of the camera. 
         FIG. 3  is a flowchart illustrating the calculation of the score for each image. 
         FIG. 4  illustrates an experimental setup for a camera system according with one embodiment of the invention. 
         FIG. 5  illustrates an experimental frame score vs. focusing distance curve. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Some embodiments of the invention will now be described, by way of example, with reference to the accompanying drawings. 
     In  FIG. 1 , a digital still camera has an image pickup device  1 , and a lens  2  for focusing an image of a scene upon the pickup device. Adjustment of the lens position and hence focus is performed by a motor  3 . These parts are present in a conventional digital camera, of course. Apart from the focus adjustment arrangements now to be described, other parts of the camera such as exposure control, flash, and image storage are conventional and therefore not shown. 
     Focus control is performed by a control unit, in the form of a suitable program-controlled processor  4 , which has access to a store  5  with storage areas  51  for buffering digital images captured by the pickup device  1  and a storage area  52  for a control program. It is also able to control the focussing motor  3  via a drive interface  6 . 
     The operation of the control program in setting the focus is focussing is shown in the flowchart of  FIG. 2 . At Step  100 , a counter k is initialized to zero, as are a running maximum score Smax and an index k max  corresponding to this maximum score. At step  101  the motor moves the lens to one end of its focusing range (e.g. infinity). 
     At Step  103  an image from the Image pickup device  1  is loaded into the buffer  51 . This image is then subjected at  104  to visual attention analysis to produce a score S. Details of this analysis will be given below. 
     At Step  105 , the score S is tested to see if it exceeds Smax: if so, then at  106  Smax is set to this new maximum value and the index k max  is set to the corresponding value of k; otherwise these values are left unaltered. 
     Then at step  107  the counter k is incremented and at  108  a check is performed as to whether the counter k is below a limit K. If this test returns the answer “yes” the process moves to step  109  where the motor  3  is controlled to move the lens focus setting by one step. If the “home” position of the lens corresponds to focussing on infinity then each step involves moving the lens to a position a little further from the pickup device  1 . The process then repeats from Step  103 , until the counter k reaches the limit K—that is to say, a number of steps that brings the lens to its “near” focussing position (furthest from the pickup device  1 ). 
     When the test at  108  returns “yes”, this means that all K focus positions have been tested, the maximum score is held in Smax and, more particularly the index k max  indicated the number of steps from “home” at which this maximum score—which is deemed to correspond to the optimum focus setting—was found. All that remains, therefore is (Step  110 ) to move the lens to this position—either directly or by returning the lens to the “home position and then issuing k max  step commands to the motor. 
     One the focus has been set, a photograph may then be taken in the usual way. Alternatively, if desired, (for a digital still image) if one retains all the trial images captured at step  103  in the buffer  5 , one could then simply select the image from the buffer that corresponds to the index k max . 
     The above example showed the invention in use in a still, digital camera; naturally it could also be applied to a video camera that captures moving pictures. It could be applied to a camera that takes photographs on conventional film, or any optical device that focuses a real image: In those cases of course the pickup device would be additional to the existing camera. 
     Turning now to the analysis at Step  104  that generates the score S, this is similar to the process described in U.S. Pat. No. 6,934,415, which analyses an image to generate for each pixel x a visual attention measure C x . Here however it is required only one measure S for the whole image, which can be obtained simply by taking the sum of all the measures C x  for the individual pixels. 
     If it is desired to focus preferentially on the centre (or any other defined area) of the image, then S could be the sum of measures in respect of just those pixels that lie within the central (or other) area. If preferred, in the interests of speeding up processing, the score could be generated not for every pixel in the image (or area under consideration) but for a subset of those pixels, subsampled on a regular grid, or at random. 
     The method of generating S will now be described in detail with reference to the flowchart of  FIG. 3 . This is in principle the same as that described in application EP 1286539A, but in this case it is unnecessary to compute each C x  separately, it is sufficient to increment a single score S for the whole image. 
     The image stored in the buffer  51  is arranged as an array A of pixels x where each pixel has colour intensities (r x , g x , b x ) attributed to it. Initially the score S is set to zero (Step  201 ). 
     A pixel x 0  is then selected from the array A (Step  202 ), and its intensity value (r x , g x , b x ) is stored in a test pixel register. A count of the number of pixel comparisons I x  (stored in a comparison counter) is set to zero (step  203 ). 
     The next step ( 205 ) is the random selection of a number of points in the vicinity of the test pixel x 0 . This region is defined by a distance measure u x  (typically in units of pixels). Thus, n pixels x j  are selected such that
 
dist( x   j   −x   j-1 )&lt; u   x  
         where j=1, . . . , n and x 0 =x.       

     The distance used may be any of those conventionally used, such as the Euclidean distance or the “city block distance between the positions within the image of the two pixels. If the horizontal and vertical coordinates of x j  are p(x j ) and q(x j ) then the Euclidean distance is
 
√{square root over ([p(x j )−p(x j-1 )] 2 +[q(x j )−q(x j-1 )] 2 )}{square root over ([p(x j )−p(x j-1 )] 2 +[q(x j )−q(x j-1 )] 2 )}{square root over ([p(x j )−p(x j-1 )] 2 +[q(x j )−q(x j-1 )] 2 )}{square root over ([p(x j )−p(x j-1 )] 2 +[q(x j )−q(x j-1 )] 2 )}
 
whilst the city block distance is
 
|p(x j )−p(x j-1 )|+|q(x j )−q(x j-1 )|
 
Typically n=3, and u x =1. For u x =1, the pixels are contiguous, but, in general the pixels may not necessarily neighbour one another or be contiguous in any sense.
 
     A pixel y 0  is now selected randomly (step  206 ) from the array A to be the current comparison pixel whose Identity is stored in a comparison pixel register. 
     The value of I x  stored in the comparison counter is incremented (step  207 ): if a limit L is exceeded, no further comparisons for the test pixel x are made: either another pixel is selected (Step  208 ) and processed from Step  203 , or if all (or sufficient) pixels have been dealt with, the process terminates. 
     Assuming that L has not yet been exceeded, the contents of the neighbour group definition register are then used to define a set of pixels forming a test group x j  and a set of pixels forming a comparison group y j , each pixel y j  of the comparison group having the same positional relationship to the comparison pixel y as the corresponding pixel x j  in the test group has to the test pixel x (Step  209 ). 
     The calculation processor then compares each of the pixels x j  with the corresponding pixel y j , using a set of threshold values Δr x , Δg x  and Δb x . 
     A pixel y is identified as being similar to a test pixel x if:
 
| r   y   −r   x |&lt;Δr x  and
 
| g   y   −g   x   |&lt;Δg   x  and
 
| b   y   −b   x   &lt;Δb   x .
         where Δr x , Δg x  and Δb x  are threshold values which are, in this embodiment, fixed.       

     If all the pixels X j  in the test group are similar to their corresponding pixels V 1 —in the comparison group, the process is repeated by selecting a new set of neighboring pixels (Step  205 ) and a new comparison pixel y 0  (Step  206 ). If one, or more pixels X j  in the test group are not similar to the corresponding pixel y, in the comparison group, in accordance with the similarity definition above, the score S stored in the anomaly count register is incremented (Step  210 ). Another comparison pixel y 0  is randomly selected and stored in the comparison pixel register (return to Step  206 ) and the neighbor group definition retrieved from the neighbor group definition store is used to supply a new comparison neighbor group to the comparison group register for comparison with the test group stored in the test group register. A set of pixels X j  is retained in the test group register so long as it continues to fail to match other parts of the image. Such a set represents a distinguishing feature of the locality of x—the more failures to match that occur, the more distinctive it is. The more comparison pixels y that the test pixel x fails to provide matches for, the higher the score S becomes. 
     When the process has finished, the final value of S is the measure of visual attention for the image Al x, and is the number of attempts (from a total of number of attempts equal to L multiplied by the number of pixels considered) for which the inherent characteristics (i.e. the colors) of randomly selected neighbors of pixel x failed to match the corresponding neighbors of randomly selected pixels y. A high value indicates a high degree of mismatch for pixels of the image with the rest of the image. 
     As noted above, the process may be repeated, from step  203 , for every pixel in the image as the test pixel, so that the value S is in effect the sum of scores for every pixel x in the array A. Typically, L may be set to be 100. 
     As described above, comparisons are performed for the neighboring pixels X j , yj, j=i, . . . n; however, if desired, the original or root pixels may also be included, the comparisons being performed for j=0, . . . , n. 
     Note too that, whilst preferred, it is not essential that the analysis loop of  FIG. 3  terminals (at  209 ) upon a single match. For variation, see our aforementioned US patent. 
     Note that where subsampling is used as discussed above, only a subset of pixels are chosen as pixels x; however it is preferable that the neighboring pixels are chosen from the full image 
     EXPERIMENTAL RESULTS 
     A Canon EOS 300D camera was used to photograph the same scene whilst focusing at different distances, from 11 cm to 39 cm, as shown In  FIG. 4 . A small F-stop (large aperture) was used to minimise the depth of field. All photos were taken as 1.5 mega-pixel JPEGs, converted to BMP, and then resealed to be 200×266 pixels in size. They were then processed by the VA algorithm, with a view radius of 10, fork radius u x  of 5, 10 pixels per fork, no skipping, 10 tests and a colour threshold of 50. The overall frame score was then plotted graphically, as shown in  FIG. 5 . This shows a clear peak at exactly the frame corresponding to the distance at which the book had been placed. 
     Thus we see that, by computing a total VA scores for the entire image a measure of overall interest can be found. In turn, if the total score is compared against multiple candidate images, it can be used to help decide which is most interesting, and possibly best if used to control a camera&#39;s auto-focus. 
     However, by computing the global interest level within each frame, then slightly changing the focus, it&#39;s possible for the camera to quickly lock onto the focus distance at which the frame is most interesting. Indeed, this could be used to determine the depth of field of the image, by seeing how much the focus can be changed without a significant drop in overall score. 
     There are a huge number of other applications—anywhere where there are parameters that need changing to optimize an output image could potentially benefit from VA being used to automatically choose the best values.