Patent Publication Number: US-11030452-B2

Title: Pattern detection

Description:
CROSS-REFERENCES TO RELATED APPLICATIONS 
     This application is a continuation of copending International Application No. PCT/EP2016/071724, filed Sep. 14, 2016, which is incorporated herein by reference in its entirety. 
     Embodiments of the present invention refer to a method and an apparatus for detecting a known pattern having homogenous areas. Advantageous embodiments refer to robust chessboard detection for a geometric camera calibration. 
    
    
     BACKGROUND OF THE INVENTION 
     Nearly every camera and especially cameras having a wide viewing angle have to be calibrated. Such wide viewing angle cameras are often used for endoscopes. 
     Endoscopic procedures are common clinical practice for a variety of diseases. Among others, minimally invasive surgery with endoscopic instruments is performed on abdominal organs (laparoscopy), joints (arthroscopy), or the brain (neurosurgery). Endoscopy involves good orientation, coordination, and fine motor skills of the surgeon. Therefore, computer systems that offer navigation support to the physician are of increasing significance. Navigation systems which relate the view through the endoscope to the geometry of the surgical site may use a calibrated camera. In this context, calibration refers to the process of estimating the intrinsic camera parameters. The intrinsic parameters of a distorted pinhole camera model consist of the focal length, the principal point, as well as radial and tangential distortion parameters. 
     Usually, camera calibration is a two-step process: First, a known calibration pattern is detected in the images. Second, the calibration parameters are estimated based on correspondences between points on the pattern and their projections in the images. 
     Camera calibration for endoscopic applications poses several challenges. Endoscopes often have wide-angle lenses with typical viewing angles between 90° and 120°. Therefore, distortion effects are very strong. Due to the optical setup of the endoscope, the light source is close to the optical center. This often causes strong inhomogeneity, glare, vignetting effects, and high image noise in badly illuminated regions. Within a clinical environment, non-technical staff is expected to be able to perform the calibration process quickly. Consequently, the calibration method is expected to reliably handle motion blur, defocussing, and recordings of partially captured patterns. 
     Various patterns have been developed. Still, the planar chessboard pattern is most established. Mallon et al. [8] have shown that the chessboard pattern outperforms circle patterns in the case of strong perspective or radial distortion. Self-identifying targets (like ARTags [6]) are more complex and may use high resolution and low-noise images. 
     Below, approaches according to the state-of-the-art will be discussed: Ernst et al have introduced a method for robust color chart detection using a region-based approach (patent WO 2012113732 A1) [5]. Barreto et al introduced a calibration method that has been specifically designed to comply with the requirements of endoscopic camera calibration [1] (patents WO 2013015699 A1 and WO 2014054958 A2) and refined subsequently [9, 10]. Fuersattel et al present another approach that detects (partially occluded) checkerboard patterns under worse lightening conditions and in low-resolution images [7]. 
     However, none of the above described concepts are robust enough to handle strong distortions, image blur, noise, and partially visible targets. Therefore, there is the need for an improved approach. 
     The present invention provides a concept for a robust detection of a planar calibration target, i.e. like a chess board, under difficult conditions, for example, in order to enable the calibration of a camera. 
     SUMMARY 
     According to an embodiment, a method for detecting a known pattern having homogenous areas may have the steps of: taking an image of at least a portion of the known pattern; initially detecting a first region of the image, the first region including at least two homogenous areas, to estimate at least one region parameter for the first region; detecting a feature of the known pattern within a second region of the image, the second region including at least two homogenous areas and being adjacent to the first region, to obtain at least one region parameter of the feature within the second region. 
     According to an embodiment, a computer-implemented method for detecting a known pattern having homogenous areas may have the steps of: taking an image of at least a portion of the known pattern; initially detecting a first region of the image, the first region including at least two homogenous areas, to estimate at least one region parameter for the first region; detecting a feature of the known pattern within a second region of the image, the second region including at least two homogenous areas and being adjacent to the first region, to obtain at least one region parameter of the feature within the second region; wherein the step of detecting the feature is iterated for a third region of the image, the third region including at least two homogenous areas and being adjacent to the first and/or the second region to obtain at least one region parameter for the feature within the third region; wherein the step of detecting a feature of the known pattern is iterated for another region in a direction extending from the first region and going through the second region and/or third region taking into account a an adapted projection model until no additional feature is found in this direction. 
     According to an embodiment, a computer-implemented method for detecting a known pattern having homogenous areas may have the steps of: taking an image of at least a portion of the known pattern; initially detecting a first region of the image, the first region including at least two homogenous areas, to estimate at least one region parameter for the first region; detecting a feature of the known pattern within a second region of the image, the second region including at least two homogenous areas and being adjacent to the first region, to obtain at least one region parameter of the feature within the second region; wherein the determining of the feature within the first, second, third or another region includes a corner detection; and wherein the corner detection includes the substep of morphing the template in accordance to a morphing parameter to obtain a morphing model for the first, second, third or another region; and wherein the method further includes this step of determining a projection model based on the one or more determined region parameters and on the assumption that each vertex of the respective morphable model of the first, second, third or another region is projected into the image and/or distorted. 
     According to another embodiment, a method for calibrating a camera may have the steps of: detecting a known pattern having homogenous areas; and calculating camera calibration parameters describing the behavior of the camera based on the at least one region parameter for the first region and/or on the at least one region parameter of the feature within the second region. 
     According to another embodiment, a non-transitory digital storage medium may have a computer program stored thereon to perform the inventive method for detecting a known pattern having homogenous areas, when said computer program is run by a computer. 
     According to another embodiment, an apparatus for detecting a known pattern having homogenous areas may have: an input interface for receiving an image of the known pattern; a calculation unit for initially detecting a first region of the image, the first region including at least two homogenous areas, to estimate at least one region parameter for the first region; and for detecting a feature of the known pattern within a second region of the image, the second region including at least two homogenous areas and being adjacent to the first region, to obtain at least one region parameter of the feature within the second region. 
     According to another embodiment, an apparatus for detecting a known pattern having homogenous areas may have: an input interface for receiving an image of the known pattern; a calculation unit for initially detecting a first region of the image, the first region including at least two homogenous areas, to estimate at least one region parameter for the first region; and for detecting a feature of the known pattern within a second region of the image, the second region including at least two homogenous areas and being adjacent to the first region, to obtain at least one region parameter of the feature within the second region; wherein the step of detecting the feature is iterated for a third region of the image, the third region including at least two homogenous areas and being adjacent to the first and/or the second region to obtain at least one region parameter for the feature within the third region; wherein the step of detecting a feature of the known pattern is iterated for another region in a direction extending from the first region and going through the second region and/or third region taking into account a an adapted projection model until no additional feature is found in this direction; or wherein the determining of the feature within the first, second, third or another region includes a corner detection; and wherein the corner detection includes the substep of morphing the template in accordance to a morphing parameter to obtain a morphing model for the first, second, third or another region; and wherein the method further includes this step of determining a projection model based on the one or more determined region parameters and on the assumption that each vertex of the respective morphable model of the first, second, third or another region is projected into the image and/or distorted. 
     Embodiments of the present invention refer to a method for detecting a known pattern having homogeneous areas, e.g. a chessboard. The method comprises the steps of taking an image of the known pattern or, of at least a portion of the known pattern, and performing detection. Detection comprises at least two steps; namely, an initial detection of a first region of the image and the detection of a feature of the known pattern within a second region of the image. The first region (e.g. a 3×3 portion of a chessboard) comprises at least two homogeneous areas. The second region (e.g. 2×2 checkerboard model) is arranged adjacent to the first region also comprises at least two homogeneous areas. The initial detection has the purpose to estimate at least one region parameter, such as a position of the region of the pattern, and/or orientation of the region or distortion of same. Starting from this, the second region can be selected in which a feature, such as a corner of the checkerboard is detectable. This second detection step has the purpose to obtain at least one region parameter such as the position of a characteristic feature within the second region, wherein the characteristic (exemplarily) means that the feature enables a mapping to the known pattern. 
     Embodiments of the present invention are based on the knowledge that a calibration process can be improved, when the process for detecting the calibration target, here, the known pattern having homogeneous areas, can be performed in a robust and precise manner. According to the teachings disclosed herein, the detection of the pattern/chessboard is performed according to a two-stage strategy. Within the first stage, a raw estimation of a portion of the calibration target, e.g. 3×3 portion of the chessboard is performed in order to detect this portion and to obtain first model parameters, such as the raw orientation of the pattern in the space. Starting from this first guess, regions adjacent to the already detected first region are investigated in order to detect features within the adjacent regions. Starting from the first guess of the first portion the raw position of the pattern should be known, however, the exact (or more exact) position of the known pattern in the space can be refined by the determination of features. The feature may be a corner such that the determination may, for example, be a corner determination. This approach is reliable and handles strong distortion, image blur, noise and partially visible targets. It is robust and provides a precise determining of the calibration target for the camera calibration, e.g. of an endoscopic camera. 
     According to further embodiments, the feature determination may be iterated for further regions, e.g. regions in a direction extending from the first region in a direction through the second region, such that a further refinement can be achieved. According to another embodiment the featured detection can be iterated for a third region adjacent to the first or the second region in order to obtain additional model parameters (a model parameter for a third region e.g. a position of the corner in the third region). Further iterations may be performed for further regions until no additional feature is found. The iteration may be performed within a first direction extending from the first region through the second region or another direction extending from the first region not along the first direction. According to embodiments, the region in which the next feature determination is performed is selected based on an adapted camera model (e.g. describing the distortion of the camera) and based on a simulated model of the calibration target (wherein the simulation is performed based on the previously determined features and/or the initial detection of the characteristic portion of the calibration target). This means, in other words, that according to embodiments, after the detection of the feature within the first, second, third or another region, the camera calibration parameters describing the behavior of the camera, are updated, such that the successive (optional) step of selecting the second, third or another region is performed based on the updated camera parameters. 
     According to embodiments the feature detection is a corner detection. For example, when considering a chessboard as the calibration target, the corner detection may be realized by using templates, each being a checkerboard model in a 2×2 format. The detection is performed by a comparison between the template and the image of the first, second, third or another region of the image. Since typically the corners are not rectangular the template can be morphed during the comparison in order to adapt same to the corner. According to embodiments, the comparison between the template and the image taken is performed by determining a correspondence between a portion within the first, second, third or another region of the image and one or more templates. Here, an intensity difference between mean pixel values of two fields of the checkerboard model can be determined, where the maximum of the intensity difference indicates a matching. Alternatively, a standard deviation of the two fields of the checkerboard model can be determined, wherein a minimum indicates matching. This approach may be expressed with the following mathematical formula: 
     the mean pixel values (μ ra , μ rb ) are approximated using the formula: 
                   μ   ^     :         ℝ     M   ×   2       ×     ℝ     w   ×   h         →     ℝ   ⁡     (       M   ′     ,     I   Σ       )       ↦     μ   r         :=       s   r       a   r         ;         
wherein the standard deviation (σ ra , σ rb ) are approximated using the following formula:
 
                     σ   ^     ⁢     :     ⁢           ⁢     ℝ     M   ×   2       ×     ℝ     w   ×   h       ×     ℝ     w   ×   h         →     ℝ   ⁢     
     (       M   ′     ,     I   Σ     ,       [     I   2     ]     Σ       )     ↦     σ   r       :=             s   ^     ⁡     (       M   ′     ,       [     I   2     ]     Σ       )         a   r       -     μ   r   2           ;         
wherein a r  is defined by
 
                 a   ^     ⁢     :     ⁢           ⁢     ℝ     M   ×   2         →   ℝ                     M   ′     ↦     a   r       :=       1   2     ⁢       ∑     i   =     k   r         l   r       ⁢     (           u   ˘     i     ⁢       v   ˘       i   +   1         -         u   ˘       i   +   1       ⁢       v   ˘     i         )           ;         
and
 
wherein l s  is defined by
 
                 I   Σ     ⁡     (     x   ,   y     )       :=       ∑       i   ≤   x     ,     j   ≤   y         ⁢     I   ⁡     (     i   ,   j     )               
wherein s r  is a sum of pixel values and wherein [I 2 ] Σ  is an integral image where each pixel value is squared before the summation.
 
     According to embodiments, the morphing of the templates may be performed during the detection, wherein a morphing parameter is used to perform the morphing. This may mathematically be expressed as follows: 
                 T   k     :=     [           x     k   ⁢           ⁢   1             y     k   ⁢           ⁢   1               ⋮       ⋮             x   kM           y   kM           ]       ,       with   ⁢           ⁢   k     ∈     [     0   ,   N     ]             
wherein the morphing is performed using a morph parameter vector:
 
p:=(Δ x , Δ y , s, α 1 , . . . , α N ), wherein the parameter α k  is associated with each deformation target T k  for k&gt;0 to specify the weight of each template in the linear combination and wherein Δ x  and Δ y  are global translations and wherein s is a scaling parameter.
 
     In this context it should be noted that according to embodiments the morph model may be defined as follows: 
     
       
         
           
             m 
             : 
             
               
                 ℝ 
                 
                   N 
                   + 
                   3 
                 
               
               → 
               
                 ℝ 
                 
                   M 
                   × 
                   2 
                 
               
             
           
         
       
       
         
           
             
               p 
               ↦ 
               M 
             
             = 
             
               
                 [ 
                 
                   
                     
                       
                         
                           x 
                           ˘ 
                         
                         1 
                       
                     
                     
                       
                         
                           y 
                           ˘ 
                         
                         1 
                       
                     
                   
                   
                     
                       ⋮ 
                     
                     
                       ⋮ 
                     
                   
                   
                     
                       
                         
                           x 
                           ˘ 
                         
                         M 
                       
                     
                     
                       
                         
                           y 
                           ˘ 
                         
                         M 
                       
                     
                   
                 
                 ] 
               
               := 
               
                 
                   s 
                   ( 
                   
                     
                       T 
                       0 
                     
                     + 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         N 
                       
                       ⁢ 
                       
                         
                           α 
                           k 
                         
                         ⁡ 
                         
                           ( 
                           
                             
                               T 
                               k 
                             
                             - 
                             
                               T 
                               0 
                             
                           
                           ) 
                         
                       
                     
                   
                   ) 
                 
                 + 
                 
                   
                     [ 
                     
                       
                         
                           
                             Δ 
                             x 
                           
                         
                         
                           
                             Δ 
                             y 
                           
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             Δ 
                             x 
                           
                         
                         
                           
                             Δ 
                             y 
                           
                         
                       
                     
                     ] 
                   
                   . 
                 
               
             
           
         
       
     
     According to further embodiments, a determination of a projection model may be performed. This projection model is based on the respective morphable model and the assumption that each vertex of the respective morphable model (belonging to the first, second, third or another region) is linearly projected into the image. 
     According to embodiments, the so-called homography matrix is used which defines the linear projection of each vertex from M into the image frame. This is defined by the following formula: 
     
       
         
           
             
               
                 [ 
                 
                   
                     
                       
                         u 
                         ~ 
                       
                     
                   
                   
                     
                       
                         v 
                         ~ 
                       
                     
                   
                   
                     
                       
                         w 
                         ~ 
                       
                     
                   
                 
                 ] 
               
               = 
               
                 H 
                 ⁡ 
                 
                   [ 
                   
                     
                       
                         
                           x 
                           ˘ 
                         
                       
                     
                     
                       
                         
                           y 
                           ˘ 
                         
                       
                     
                     
                       
                         1 
                       
                     
                   
                   ] 
                 
               
             
             , 
           
         
       
         
         
           
             wherein
 
 u=ũ/{tilde over (w)}  and  v={tilde over (v)}/{tilde over (w)},  
 
             wherein
 
 ŭ:=u (1+ k   1   r   2   +k   2   r   4 )+( p   2 ( r   2 +2 u )+2 p   1   uv ),
 
 v̆:=v (1+ k   1   r   2   +k   2   r   4 )+( p   1 ( r   2 +2 v )+2 p   2   uv ),
 
             where the coefficients k 1 , k 2  cause radial distortion and p 1 , p 2  cause tangential distortion, and where the radius r is the distance of each vertex to the distortion center (c x , c y ). 
           
         
       
    
     According to embodiments, the initial detection is performed using a so-called discriminant criterion which has to be calculated for the different portions/locations/subregions of the first region. Here, this calculation is performed for different (sub-)regions and/or different distributions of the pixel within the entire image in order to find the first region. The first region is found when the discriminant criterion is fulfilled on maximum. Here, it is beneficial that the calculation is performed just for some pixels, e.g. five pixels per area or, in general, a limited number of pixels less than all pixels of the area, such that the calculation can be done quickly. Note that the number of pixels is based on the trade-off between the calculation performance and the calculation accuracy, since a larger number of pixels allow the determination more accurately. 
     According to further embodiments, the calculation of the discriminant criterion may be based on the following mathematical relationship: 
                 s   p     :=           μ   ^     1     -       u   ^     2             σ   ^     1     +       σ   ^     2           ,         
wherein {circumflex over (σ)} 1  and {circumflex over (σ)} 2  denote the standard deviation, and wherein {circumflex over (μ)} 1  and {circumflex over (μ)} 2  denote the corresponding intensity means, and where p denotes the dependency on the region parameters; and/or wherein the discriminant criterion is calculated for different combinations of the region parameters to find a proper guess for the region parameters belonging to the portion. This approach enables performing a quick estimation as to how the chessboard is arranged within the space.
 
     Another embodiment provides a method for calibration of a camera, a random method uses the pattern detection as described above and the calculation of at least a camera calibration parameter, e.g. the lens distortion. This calibration method may be beneficially used for endoscopic cameras since the same have often a strong lens distortion. 
     Another embodiment provides the computer program which enables when running on a computer to perform one of the above method steps. According to a further embodiment an apparatus is provided enabling execution of the above method. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Embodiments of the present invention will be detailed subsequently referring to the appended drawings, in which: 
         FIG. 1 a    shows a schematic flow chart illustrating the method for calibrating a camera according to a basic embodiment; 
         FIG. 1 b    shows another schematic flow chart illustrating an enhanced version of the method for calibrating a camera according to an enhanced embodiment; 
         FIGS. 2 a  to 2 g    illustrate seven images of a calibration target during six different steps of the method for calibrating the camera and adjusting the camera calibration parameters according to embodiments; 
         FIG. 3  shows a checkerboard model together with sampling points used for performing the initial estimation according to embodiments; 
         FIG. 4  shows dramatic representations of seven differently morphed templates which are used for the feature detection/corner detection according to embodiments; 
         FIGS. 5 a  and 5 b    show two different schematic views for illustrating the principal of the subpixel precise corner detection using a 2×2 checkerboard model before and after the optimization of the morph template according to embodiments; 
         FIGS. 6 a  and 6 b    show two different views illustrating examples of candidates; and 
         FIG. 7  shows an algorithm for performing the pattern detection. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Below, embodiments of the present invention will subsequently be discussed referring to the figures. Here, identical reference numbers are provided to elements or steps having identical or similar functions. Therefore, the description thereof is interchangeable and mutually applicable. 
       FIG. 1 a    shows the basic method  100  for detecting a known pattern  10  having homogeneous areas  10   a  and  10   b . The known pattern  10  may be, for example, a chessboard or another regular or irregular pattern e.g. comprising circles or having QRcode arrangement. Typically, but unnecessarily, the areas  10   a  and  10   b  are black and white, such that the same offer a high contrast. However, according to further embodiments, the homogeneous areas may have a different color. The method  100  comprises the three basic steps  110 ,  120  and  130 . 
     In the first step  110 , a picture of the entire pattern  10  or a portion of the pattern  10  is taken. Starting from this picture, the pattern detection is performed using the steps  120  and  130 . 
     Within the step  120  an initial detection of a first region  12  is performed. This initial detection may, for example, be performed using a trial and error procedure, namely by calculating so-called discriminant criterion for different regions (c.f. patched cycle  12 ′) within the image of the pattern  10 . Here, different positions within the image and/or different orientations of the region  12  may be calculated in order to achieve the best fulfilment of the discriminant criterion. This second step  120  of the detection has the purpose to get a raw estimation of at least one region parameter for the first region, such as the position of the region. 
     Regarding this step  120 , it should be noted that this step may be optional, and be performed just based on the calculation of the discriminant criterion for a limited number of pixels in order to perform the initial estimation quickly. Based on this first region parameter, it is, theoretically, possible to calculate the orientation of the pattern within the space, such that this knowledge can be used for a camera calibration. However, practically the first guess of the region parameter is used for two issues, commonly for estimating the camera calibration parameter and, especially as input for the next step  130  of detecting a feature of the known pattern, e.g. a corner of the chessboard. 
     Since a first region parameter (c.f. step  120 ) is known, the known pattern  10  can be arranged virtually within the space, such that the approx. position of the feature to be determined within the step  130  is known. Starting from this knowledge the second region  14  in which the feature is searched (is selected). Here, the second region  14  is adjacent to the first region  12 . “Here” means adjacent, for example, that the second region  14  abuts the first region  12  or that it lies in the vicinity, wherein another region may be arranged in between. Based on this selected second region  14 , the step  130  of detecting the feature of the known pattern is performed in order to obtain at least one region parameter of the feature, e.g. the exact position of a corner of the chessboard. Note that the second region  14  can overlap the first region  12  or can be a part of the first region  12 . Thus, the step  130  is performed for determining the feature/corner in the region  12  (as described below). 
     Since now, at least one region parameter for a region is known, the pattern can be determined. However, in order to determine the same more precisely, it is possible, according to further embodiments, to iterate the step  130  for a third or further region (arrow having broken lines). Here, the third region (c.f. reference number  16 ) may be arranged in the direction extending from the first region  12  through the second region  14  to the border of the image  10 . Alternatively, the third region may be arranged in another region, (c.f. third region  16 ′). Typically, the step  130  is, according to embodiments, iterated until no additional feature is found. For each iteration, the camera calibration parameter may be updated as will be discussed with respect to  FIG. 1   b.    
       FIG. 1 b    shows the method  200  which consists of three phases, namely, the initial estimation phase  220 , the pattern growing phase  230  and the optional parameter optimization phase  240 . 
     In the initial phase  220 , a so-called spare sampling strategy  221 , is used to find the initial guess for the checkerboard position and size. In context to this, it is referred to  FIGS. 2 a  and 2 c    illustrating this spare sampling strategy. This spare sampling strategy substantially complies with the above described approach of finding the first region  12  (c.f. step  120 ). 
     Within the step  222  the best match is selected from which the pattern growing phase  230  is started. Within this pattern growing phase  230 , the guess is refined to subpixel precise corner locations. This step is called refined corners  231 . Here, according to embodiments, an approach using differently morphed templates is used. The templates may also be referred to as morphable corner models. Here, comparison between the template and the image within the second region  14  is performed at different positions within the second region  14 , wherein the morph parameters are varied for morphing the template to adapt (distorting, shifting) same to the corner which should be detected. The result of the comparison is that one morphed template achieves at one position the best matching. This position is elected as a region parameter, c.f. step  232 . 
     The determined region parameter is used for the parameter optimization (c.f.  240 ). Here, the camera calibration (model) parameters are re-estimated, as illustrated by the step  241 . 
     Starting from the re-estimated camera calibration (model) parameter, the pattern growing phase  230  is continued. Here, the step  233  of creating a new candidate, namely, of searching a new region, e.g. the third region  16 , is performed. When this candidate is found, the step  231  and  232  are iterated until no new feature (corner) is found. This decision is taken within the phase parameter optimization  240 , namely, using the decision step  242 . This means in other words that the expansion phase iteratively searches new checkerboard corners/features in the vicinity of the detected corners and updates the camera parameters (c.f. step  241 ). This is illustrated, when looking at  FIG. 2 , by  FIGS. 2 e    and  2   f.    
     After no new features/corners are found, the method  200  is finalized (c.f.  243 ). Here, all features/corners (reference number X) are detected, as illustrated by  FIG. 2   g.    
     This method  200  and especially the phases  220 ,  230  and  240 , are now discussed in more detail. 
     Initial Estimation Phase  220   
     The method  200  has an initial estimate of the checkerboard size, pose and position. Here, the image with a 3×3 checkerboard model (see  FIG. 3 ) is regularly scanned to find positions of high correspondence between the checkerboard model and the image (see  FIGS. 2 a  and 2 b   ). At its position, the intensity of five points P within each of the nine checkerboard patches is sampled. 
       FIG. 3  shows a random sampling model used for finding the region  12 . The points, marked by the reference numeral P, indicate samples. Note that the model consists of two groups (black and white) of homogeneous areas. 
     The regular structure of a checkerboard allows its division into two of homogeneous intensities. A successful initial guess is characterized by a high intensity difference between both groups and a low intensity variance within each group. The Fisher linear discriminant is suited to identify the best guesses. It is commonly used to maximize the spread of samples in pattern classification problems [4]. Let {circumflex over (σ)} 1  and {circumflex over (σ)} 2  denote the standard deviation of all samples in the respective group. Let {circumflex over (μ)} 1  and {circumflex over (μ)} 2  denote the corresponding intensity means. The correspondence between the checkerboard model and the image is defined—based on the idea of the Fisher discriminant—as: 
                 s   p     :=           μ   ^     1     -       u   ^     2             σ   ^     1     +       σ   ^     2           ,         
where p denotes the dependency on the model parameters (i.e. size, pose and position).
 
     Testing for different combinations of size, position, sharing and rotation is performed to find a proper guess. Finally, the sample that maximizes |s p | is chosen to calculate an initial homography H 0  based on the model and image coordinates. Distortion has not been taken into account, and the distortion d 0  is initialized to an identity mapping. The complete procedure is denoted as spare region sampling. 
     Phase Pattern Growing  230   
     Based on the initial guess, the expansion phase iteratively detects new checkerboard corners. For each detected checkerboard corner, it regards the four direct neighbors as corner candidates and performs the corner detection. Then, it refines the initial guess accordingly. The pattern growing phase mainly consists of the region-based corner detection, which makes this method very robust against blur and noise. In order to explain the process in detail, the morphable model is introduced that allows for a highly flexible parameterization and its projection into the image space. 
     The morphable model is defined by a linear combination of N deformation templates with coefficients α k  and a default template. The coefficients determine the shape of the model. The choice of templates offers fine-grained control over the parameterization of the model shape. That, in turn, simplifies fitting the model onto the image. In this embodiment, a morphable corner model m is used that consists of seven elementary templates T k  (see  FIG. 4 ). Each template consists of M vertices. With N:=6, the resulting formula is: 
     
       
         
           
             
               
                 T 
                 k 
               
               := 
               
                 [ 
                 
                   
                     
                       
                         x 
                         
                           k 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                         
                       
                     
                     
                       
                         y 
                         
                           k 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           1 
                         
                       
                     
                   
                   
                     
                       ⋮ 
                     
                     
                       ⋮ 
                     
                   
                   
                     
                       
                         x 
                         kM 
                       
                     
                     
                       
                         y 
                         kM 
                       
                     
                   
                 
                 ] 
               
             
             , 
             
               
                 with 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 k 
               
               ∈ 
               
                 [ 
                 
                   0 
                   , 
                   N 
                 
                 ] 
               
             
           
         
       
     
     T 0  is the unmorphed default template (see  FIG. 4 ). One parameter α k  is associated with each deformation target T k  for k&gt;0 to specify the weight of each template in the linear combination. In addition, a global translation Δ x , Δ y  and a scaling parameter s is introduced. The morph parameter vector combines all parameters in:
 
 p :=(Δ x ,Δ y   ,s,α   1 , . . . ,α N )
 
     The morphable model combines the templates using p: 
     
       
         
           
             m 
             : 
             
               
                 ℝ 
                 
                   N 
                   + 
                   3 
                 
               
               → 
               
                 ℝ 
                 
                   M 
                   × 
                   2 
                 
               
             
           
         
       
       
         
           
             
               p 
               ↦ 
               M 
             
             = 
             
               
                 [ 
                 
                   
                     
                       
                         
                           x 
                           ˘ 
                         
                         1 
                       
                     
                     
                       
                         
                           y 
                           ˘ 
                         
                         1 
                       
                     
                   
                   
                     
                       ⋮ 
                     
                     
                       ⋮ 
                     
                   
                   
                     
                       
                         
                           x 
                           ˘ 
                         
                         M 
                       
                     
                     
                       
                         
                           y 
                           ˘ 
                         
                         M 
                       
                     
                   
                 
                 ] 
               
               := 
               
                 
                   s 
                   ( 
                   
                     
                       T 
                       0 
                     
                     + 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         N 
                       
                       ⁢ 
                       
                         
                           α 
                           k 
                         
                         ⁡ 
                         
                           ( 
                           
                             
                               T 
                               k 
                             
                             - 
                             
                               T 
                               0 
                             
                           
                           ) 
                         
                       
                     
                   
                   ) 
                 
                 + 
                 
                   
                     [ 
                     
                       
                         
                           
                             Δ 
                             x 
                           
                         
                         
                           
                             Δ 
                             y 
                           
                         
                       
                       
                         
                           ⋮ 
                         
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             Δ 
                             x 
                           
                         
                         
                           
                             Δ 
                             y 
                           
                         
                       
                     
                     ] 
                   
                   . 
                 
               
             
           
         
       
     
     The morphable model is influenced by the point distribution model (pdm) by Cootes and Taylor [3]. The deviation of each deformation template from the default template is similar to the modes of variation in the pdm. However, the morphable model artificially introduces more degrees of freedom to yield a simpler error surface. It additionally accounts for scaling and translation in the model coordinate frame. 
       FIG. 4  shows different morphed templates. T 0 : unmorphed template; T 1  and T 2 : shearing at the model center; T 3  to T 6 : shearing by moving only the top, bottom, left and right side. 
     With respect to  FIG. 5 , subpixel precise corner detection using a 2×2 checkerboard is illustrated. Here,  FIG. 5 a    shows the corner model before optimization, whereas  FIG. 5 b    shows the corner model after the optimization process. 
     Projection Model 
     The morphable model resides in the model coordinate frame and M is a matrix of model coordinates. For example, planar calibration targets are used, wherein also the usage of non-planar targets would be possible. Therefore, the image coordinates of the model lie in a two dimensional linear manifold of    3 . A homography defines the linear projection of each vertex (x̆, y̆) from M into the image frame by: 
     
       
         
           
             
               [ 
               
                 
                   
                     
                       u 
                       ~ 
                     
                   
                 
                 
                   
                     
                       v 
                       ~ 
                     
                   
                 
                 
                   
                     
                       w 
                       ~ 
                     
                   
                 
               
               ] 
             
             = 
             
               
                 H 
                 ⁡ 
                 
                   [ 
                   
                     
                       
                         
                           x 
                           ˘ 
                         
                       
                     
                     
                       
                         
                           y 
                           ˘ 
                         
                       
                     
                     
                       
                         1 
                       
                     
                   
                   ] 
                 
               
               . 
             
           
         
       
     
     The homography matrix H∈   3×3  is defined up to a scale [14]. The inhomogeneous representation of the image coordinates can be got by u=ũ/{tilde over (w)} and v={tilde over (v)}/{tilde over (w)}, respectively. Afterwards, the Brown-Conrady model is applied to account for non-linear radial and tangential distortion [2]:
 
 ŭ:=u (1+ k   1   r   2   +k   2   r   4 )+( p   2 ( r   2 +2 u )+2 p   1   uv ),
 
 v̆:=v (1+ k   1   r   2   +k   2   r   4 )+( p   1 ( r   2 +2 v )+2 p   2   uv ),
 
where the coefficients k 1 , k 2  cause radial distortion and p 1 , p 2  cause tangential distortion, and where the radius r is the distance of each vertex to the distortion center (c x , c y ).
 
 r   2 =( u−c   x ) 2 +( v−c   y ) 2 .
 
     The distortion parameter vector summarizes all coefficients in d:=(c x , c y , k 1 , k 2 , p 1 , p 2 ). The combination of the linear and non-linear transform yields: 
     
       
         
           
             
               
                 m 
                 ′ 
               
               : 
               
                 
                   
                     ℝ 
                     
                       N 
                       + 
                       3 
                     
                   
                   × 
                   
                     ℝ 
                     
                       3 
                       × 
                       3 
                     
                   
                   × 
                   
                     ℝ 
                     6 
                   
                 
                 → 
                 
                   
                     ℝ 
                     
                       M 
                       × 
                       2 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ( 
                   
                     p 
                     , 
                     H 
                     , 
                     d 
                   
                   ) 
                 
                 ↦ 
                 
                   M 
                   ′ 
                 
               
             
             = 
             
               [ 
               
                 
                   
                     
                       
                         u 
                         ˘ 
                       
                       1 
                     
                   
                   
                     
                       
                         v 
                         ˘ 
                       
                       1 
                     
                   
                 
                 
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       
                         u 
                         ˘ 
                       
                       M 
                     
                   
                   
                     
                       
                         v 
                         ˘ 
                       
                       M 
                     
                   
                 
               
               ] 
             
           
         
       
     
     The number of coefficients used for distortion modeling has an impact on the accuracy of the model. Tsai points out that for industrial machine vision applications, it is adequate to model only radial distortion with one coefficient [11]. Barreto et al show that for endoscopy applications it can be advantageous to use more than a single radial coefficient [1]. The advantageous application deals with endoscopy images that exhibit strong distortion effects. Therefore, two radial and two tangential coefficients are used, similar to others [13, 14]. 
     Region-Based Corner Detection 
     The corner detection model M consists of four distinct areas that form a 2×2 checkerboard pattern (see  FIGS. 4 and 5 ). The outline of each area is given by a sequence of vertices (ŭ i ,v̆ i ), i∈[k r ,l r ] with k r+1 :=l r +1 and l r ≥k r +2 for all r∈[1,4] Here, r denotes the index and k r ,l r ∈[1, M] are the boundaries of r. The 2×2 corner model is applied to the domain of corner detection. Therefore, a criterion is needed that measures how well the model separates the four checkerboard areas in the image. A variant of the Fisher discriminant was applied to find the sample that separates the groups of black and white checkerboard patches best. Based on the same idea, a local measure is derived that provides better guidance to the optimizer for subpixel precise corner detection. The Levenberg-Marquardt method is used to minimize the model residual. To gain enough residuals, the Fisher discriminant is split into two independent terms, where each term accounts for the variance within one area and the separation from one of its neighbors. In contrast to the original formulation, absolute values are not used to allow for signed residuals, as they provide better guidance to the optimizer. Finally, the maximization is turned into a minimization problem. Let μ r  and σ r  be the pixel value mean and the standard deviation of all pixels in area r. The separation between two areas r a  and r b  is defined by: 
     
       
         
           
             
               
                 
                   σ 
                   
                     r 
                     a 
                   
                 
                 + 
                 
                   σ 
                   
                     r 
                     b 
                   
                 
               
               
                 
                   μ 
                   
                     r 
                     a 
                   
                 
                 - 
                 
                   μ 
                   
                     r 
                     b 
                   
                 
               
             
             = 
             
               
                 
                   σ 
                   
                     r 
                     a 
                   
                 
                 
                   
                     μ 
                     
                       r 
                       a 
                     
                   
                   - 
                   
                     μ 
                     
                       r 
                       b 
                     
                   
                 
               
               + 
               
                 
                   
                     σ 
                     
                       r 
                       b 
                     
                   
                   
                     
                       μ 
                       
                         r 
                         a 
                       
                     
                     - 
                     
                       μ 
                       
                         r 
                         b 
                       
                     
                   
                 
                 . 
               
             
           
         
       
     
     The assumption is that the four areas are indexed in clockwise order, such that: (r a ,r b )∈{(r 1 ,r 2 ), (r 2 ,r 3 ), (r 3 ,r 4 ), (r 4 ,r 1 )} are pairs of neighboring areas. Then, the separation of some area r a  to one of its neighbors r b  is derived by: 
     
       
         
           
             
               
                 e 
                 ^ 
               
               : 
               
                 
                   
                     [ 
                     
                       1 
                       , 
                       4 
                     
                     ] 
                   
                   × 
                   
                     [ 
                     
                       1 
                       , 
                       4 
                     
                     ] 
                   
                 
                 → 
                 
                   ℝ 
                   ⁢ 
                   
                     
 
                   
                   ( 
                   
                     
                       r 
                       a 
                     
                     , 
                     
                       r 
                       b 
                     
                   
                   ) 
                 
                 ↦ 
                 
                   e 
                   
                     
                       r 
                       a 
                     
                     ⁢ 
                     
                       r 
                       b 
                     
                   
                 
               
             
             := 
             
               
                 
                   σ 
                   
                     r 
                     a 
                   
                 
                 
                   
                     μ 
                     
                       r 
                       a 
                     
                   
                   - 
                   
                     μ 
                     
                       r 
                       b 
                     
                   
                 
               
               . 
             
           
         
       
     
     With that, the separation criterion for M is defined by:
 
 e :=( e   12   ,e   21   ,e   23   e   32   ,e   34   ,e   43   ,e   41   ,e   14 ) T  
 
     For now, assume that the parameters H and d are roughly known for the projection of M into the image space. Therefore it is known which corner model coordinates (Δ x , Δ y ) potentially correspond to checkerboard corners in the image space. In the first iteration, H and d are initialized. In subsequent iterations, these estimates are updated by taking newly detected corners into consideration. The update procedure is described below. The exact image location x*=(ŭ 0 *, v̆ 0 *) of the checkerboard corner is searched for. This is done by minimizing e with respect to the morph template parameters. Therefore: 
               p   *     =     arg   ⁢           ⁢       min   p     ⁢          e        2               
where p is initialized with (Δ x , Δ y ; s, 0, . . . ). The model is translated and sheared with six different shearing templates. This simplifies minimization because it lowers the risk that the error only decreases when several parameters are adjusted simultaneously. The solution, x* is then given by the center vertex of m′(p*, H, d) (see  FIG. 5 b   ). Without loss of generality, the Levenberg-Marquardt method is used to minimize above Equation p*. Note that the scale parameter s of the model controls the size of the 2×2 search template relative to the checkerboard size. For example, each patch of the search template covers approximately one fourth of the area of the checkerboard patch, if s=0:5. Applying the morph templates in model space and then mapping them to image coordinates is advantageous because: First, given a good estimate (H, d) and corner model coordinates (Δ x , Δ y ), the corner model fits well onto the checkerboard corner that corresponds to the given model coordinates and accounts for possible distortions right away. That is why the optimization does not need an initial guess. Second, applying the morph parameters in the model coordinate frame makes them scale independent. For example, setting Δ x =1 moves the template by the width of one checkerboard patch in the image frame, independent of the image resolution and patch size. That simplifies computing the numerical derivative of the above equation describing e, because fixed delta values can be used. In addition, that approach allows jumping easily from one potential checkerboard corner to another.
 
       FIG. 6  illustrates two examples of candidates that have been dropped due to a degenerate result (c.f.  FIG. 6 a   ) or due to a high residual (c.f.  FIG. 6 b   ). 
     Candidate Selection 
     Not every result from the corner detection corresponds to a valid checkerboard corner in the image (see  FIG. 6  for examples). Therefore, constraints are introduced that allow invalid results to be rejected. First, the detected corner is in the vicinity of the corner that is predicted by the current model state. This ensures that the optimization did not converge to a neighboring point. In practice, it is sufficient to allow a deviation of one half of the checkerboard patch width. This can be easily verified with the translation parameters (Δ x , Δ y ) of m. The aim is that they differ by no more than ½ from their initialization. Second, the aim is that the area of the corner detection model before the optimization will differ not too heavily from its area after the optimization. This constraint prohibits degenerate configurations. Finally, the error ∥e∥ 2  of the detection model residual is expected to fulfill a certain threshold. This rejects checkerboard corners that lie on one of the edges of the pattern. 
     Region Statistics 
     The calculation of μ r  and σ r  is a time consuming task and needs to be carried out in every single iteration of the optimization. In a previous work, the integral image approach of Viola and Jones [12] was extended to polygonal areas [5]. The efficient approximation of region statistics within polygonal image areas is summarized here. The integral image I Σ  of an image I is given by I Σ (x,y):=Σ i≤x,j≤y I(i,j). The sum of pixel values s r  within some polygonal area r can be approximated by: 
                     s   ^     ⁢     :     ⁢           ⁢     ℝ     M   ×   2       ×     ℝ     w   ×   h         →     ℝ   ⁢     
     (       M   ′     ,     I   Σ       )     ↦     s   r       :=       1   2     ⁢       ∑     i   =     k   r         l   r       ⁢     [         I   Σ     ⁡     (         u   ˘     i     ,       v   ˘       i   +   1         )       -       I   Σ     ⁡     (         u   ˘       i   +   1       ,       v   ˘     i       )         ]           ,         
with l r +1:=k r . Similarly, â provides the area a r  inside r:
 
     
       
         
           
             
               
                 a 
                 ^ 
               
               ⁢ 
               
                 : 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 ℝ 
                 
                   M 
                   × 
                   2 
                 
               
             
             → 
             ℝ 
           
         
       
       
         
           
             
               
                 M 
                 ′ 
               
               ↦ 
               
                 a 
                 r 
               
             
             := 
             
               
                 1 
                 2 
               
               ⁢ 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     
                       k 
                       r 
                     
                   
                   
                     l 
                     r 
                   
                 
                 ⁢ 
                 
                   
                     ( 
                     
                       
                         
                           
                             u 
                             ˘ 
                           
                           i 
                         
                         ⁢ 
                         
                           
                             v 
                             ˘ 
                           
                           
                             i 
                             + 
                             1 
                           
                         
                       
                       - 
                       
                         
                           
                             u 
                             ˘ 
                           
                           
                             i 
                             + 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             v 
                             ˘ 
                           
                           i 
                         
                       
                     
                     ) 
                   
                   . 
                 
               
             
           
         
       
     
     With two above Equations for (M′,l Σ ) and M′, the mean pixel value μ r  within r is approximated by 
     
       
         
           
             
               
                 
                   μ 
                   ^ 
                 
                 ⁢ 
                 
                   : 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   ℝ 
                   
                     M 
                     × 
                     2 
                   
                 
                 × 
                 
                   ℝ 
                   
                     w 
                     × 
                     h 
                   
                 
               
               → 
               
                 ℝ 
                 ⁢ 
                 
                   
 
                 
                 ( 
                 
                   
                     M 
                     ′ 
                   
                   , 
                   
                     I 
                     Σ 
                   
                 
                 ) 
               
               ↦ 
               
                 μ 
                 r 
               
             
             := 
             
               
                 
                   s 
                   r 
                 
                 
                   a 
                   r 
                 
               
               . 
             
           
         
       
     
     Approximating the standard deviation σ r  within r may use a second integral image [I 2 ] Σ , where each pixel value is squared before the summation. Then, the result is: 
     
       
         
           
             
               
                 
                   σ 
                   ^ 
                 
                 ⁢ 
                 
                   : 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   ℝ 
                   
                     M 
                     × 
                     2 
                   
                 
                 × 
                 
                   ℝ 
                   
                     w 
                     × 
                     h 
                   
                 
                 × 
                 
                   ℝ 
                   
                     w 
                     × 
                     h 
                   
                 
               
               → 
               
                 ℝ 
                 ⁢ 
                 
                   
 
                 
                 ( 
                 
                   
                     M 
                     ′ 
                   
                   , 
                   
                     I 
                     Σ 
                   
                   , 
                   
                     
                       [ 
                       
                         I 
                         2 
                       
                       ] 
                     
                     Σ 
                   
                 
                 ) 
               
               ↦ 
               
                 σ 
                 r 
               
             
             := 
             
               
                 
                   
                     
                       
                         s 
                         ^ 
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             M 
                             ′ 
                           
                           , 
                           
                             
                               [ 
                               
                                 I 
                                 2 
                               
                               ] 
                             
                             Σ 
                           
                         
                         ) 
                       
                     
                     
                       a 
                       r 
                     
                   
                   - 
                   
                     μ 
                     r 
                     2 
                   
                 
               
               . 
             
           
         
       
     
     This way, μ r  and σ r  can be efficiently approximated and a fast and robust local corner detector can be implemented. Bilinear sampling is applied to achieve subpixel precision. This step permits estimation  240 . 
     Parameter Estimation 
     The corner refinement step finds the true image location of a checkerboard corner x* that corresponds to a corner coordinate x=(Δ x , Δ y ) in model space. With that relation, two sets are defined:    t :={x 1 , x 2 , . . . , x N     t   } and    t :={x 1 *, x 2 *, . . . , x N     t   *}. 
     Here, x i  denotes the model coordinate corresponding to x i * and t∈N denotes the iteration number. The outcome of the previous iteration is used, (H t-1 , d t-1 ), and Equation for (P, H, d) is applied on every x i ∈   t . By this, the crossing point x i ′ is derived that is predicted by the current camera model. The error that is caused by the camera model with parameters H and d is given by the difference between each detected crossing point x i * and its prediction x i ′. Therefore, the model parameters that minimize the error in iteration t are found by: 
     
       
         
           
             
               ( 
               
                 
                   H 
                   t 
                 
                 , 
                 
                   d 
                   t 
                 
               
               ) 
             
             = 
             
               
                 
                   arg 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   min 
                 
                 
                   ( 
                   
                     H 
                     , 
                     d 
                   
                   ) 
                 
               
               ⁢ 
               
                 
                   
                      
                     
                       [ 
                       
                         
                           
                             
                               
                                 x 
                                 1 
                                 ′ 
                               
                               - 
                               
                                 x 
                                 1 
                                 * 
                               
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               
                                 x 
                                 
                                   N 
                                   t 
                                 
                                 ′ 
                               
                               - 
                               
                                 x 
                                 
                                   N 
                                   t 
                                 
                                 * 
                               
                             
                           
                         
                       
                       ] 
                     
                      
                   
                   2 
                 
                 . 
               
             
           
         
       
     
     With respect to  FIG. 7 , an algorithm is shown which is configured to perform the above described method. At this point, all relevant parts have been introduced. The procedure in Algorithm 1 is now summarized. To simplify notation, the definition of the initial guess is skipped. The one used is shown in  FIGS. 2 c    and  3  and the resulting inner corners are shown in  FIG. 2 d   . In practice, many variants may work equally well. Line  3  initializes H 0  with the result of the initial guess. Then, the algorithm starts iterating, until no new corners are found. In the first iteration, the corners of the initial guess model are refined to subpixel precision, because    0  has been initialized with those corners (see  FIG. 2 d   ). In the subsequent iterations, the algorithm searches for checkerboard corners in the vicinity of those that have been detected during the previous iteration (see  FIGS. 2 e  and 2 f   ). The actual region-based corner detection is applied on line  7 . Subsequently, the center vertex, i.e. the subpixel precise corner position, is extracted from the corner detection model. In line  9 , it is assessed if the detected point fulfills defined quality measures. If all those constraints are met, the point is accepted. After all corner candidates in M have been detected or dropped, the model parameters are re-estimated such that they profit from the added points (see line  15 ). Finally, new candidates are generated for the next iteration (line  16 ). Here, n (v) denotes the four direct neighbors of v in model coordinates. Alternatively, the four diagonal neighbors could be used instead or in addition. For the sake of an efficient implementation, it is not mandatory to refine all x i Σ  in every iteration. Instead, it is sufficient to refine all corners that have been added to   at the end of the previous iteration. Then, it is advisable to refine all corners again once the algorithm terminates using the projection parameters of the last iteration. Sometimes, it is even possible to detect new corners that have been dropped before. That is, because the projection parameters become much more accurate compared to early iterations, which leads to a better initialization of the corner detector in terms of translation and deformation. 
     Although the above embodiments have been discussed, focusing on a classical chessboard pattern, it is clear that the proposed method can be adapted to other calibration targets as well. For example, one solely needs to replace the corner model by an appropriate one and possibly replace the neighborhood definition for pattern growing. 
     In the case of the sparse region sampling, it should be noted that in the current approach, five sampling points per region/area are used totally to 45 sampling points per sample. 
     That number can surely be decreased. Probably two or even one sampling point will be sufficient, which would speed up the procedure. In addition, other template forms, such as a cross (5 patches) or an X (5 patches) may be useful. Of course the results may be weaker. That could be compensated by a subsequent search in the vicinity as soon as a candidate is found. 
     According to embodiments the morph templates may not only be used for the corner detection, but also for detecting the above mentioned circles (in case the pattern is formed by circles). Here the template comprises a circle which is differently morphed (so as to form an ellipsis). Such circle templates enable to detect the position, e.g. the center of a circle. 
     With regard to the corner detection it should be noted: Currently, the objective function Equation for p* does not include any constraints. Instead, constraints are checked in the aftermath. It is easy to integrate those constraints as penalty terms in the objective function. That would provide additional guidance to the optimizer. Possibly, the complete optimization problem could then be rewritten as a Lagrangian function and solved by maximizing the corresponding dual problem. 
     In the above embodiments, the corner detection has been described based on an approach using morph templates. However, also other corner detection techniques, like an approach based on Affine Transformation are possible. 
     With regard to camera models, it should be noted that there are camera models not in focus. Advantageously, a standard Brown-Conrady model is used. 
     Of course it is easy to plug in different camera models. For that, it is sufficient to replace the mapping from model to image coordinates as described above. 
     Further embodiments refer to a calibration process, e.g. for a camera of an endoscope. This approach can, according to further embodiments, be adapted to automatic multi-camera calibration. 
     The calibration of multi-camera setups involves that the coordinate origin remains constant across the complete sequence of calibration images. To this end, one usually places some kind of marker on at least one of the checkerboard fields to define the coordinate origin. The marker can easily be modeled and detected by the region-based approach. Alternatively, some of the checkerboard fields could have specific colors. Fields having a specific/different color enable to localize the origin of coordinate system, as well. Additionally the markers and field having the specific color enable when detected the approximated orientation of the pattern within the space, even if only a part of the pattern is shown by the image. Moreover the colored fields or markers are beneficial for an extrinsic calibration or for the calibration of a multi camera arrangement (since these calibrations typically using a plurality of frames). 
     With regard to the gradient descent optimization, it should be noted that instead of using the Levenberg-Marquardt method to minimize the corner detector residual, one could also apply a gradient-based approach. That may allow for a more efficient implementation, especially by replacing the numerical derivative by automatic differentiation. 
     With regard to the estimate chromatic aberration, it should be noted that in combination with an appropriate model, the approach could be easily extended to detect chromatic aberrations. To this end, the checkerboard detection can be applied separately on each color channel. 
     Although some aspects have been described in the context of an apparatus, it is clear that these aspects also represent a description of the corresponding method, where a block or device corresponds to a method step or a feature of a method step. Analogously, aspects described in the context of a method step also represent a description of a corresponding block or item or feature of a corresponding apparatus. Some or all of the method steps may be executed by (or using) a hardware apparatus, like for example, a microprocessor, a programmable computer or an electronic circuit. In some embodiments, some one or more of the most important method steps may be executed by such an apparatus. 
     Depending on certain implementation requirements, embodiments of the invention can be implemented in hardware or in software. The implementation can be performed using a digital storage medium, for example a floppy disk, a DVD, a Blu-Ray, a CD, a ROM, a PROM, an EPROM, an EEPROM or a FLASH memory, having electronically readable control signals stored thereon, which cooperate (or are capable of cooperating) with a programmable computer system such that the respective method is performed. Therefore, the digital storage medium may be computer readable. 
     Some embodiments according to the invention comprise a data carrier having electronically readable control signals, which are capable of cooperating with a programmable computer system, such that one of the methods described herein is performed. 
     Generally, embodiments of the present invention can be implemented as a computer program product with a program code, the program code being operative for performing one of the methods when the computer program product runs on a computer. The program code may for example be stored on a machine readable carrier. 
     Other embodiments comprise the computer program for performing one of the methods described herein, stored on a machine readable carrier. 
     In other words, an embodiment of the inventive method is, therefore, a computer program having a program code for performing one of the methods described herein, when the computer program runs on a computer. 
     A further embodiment of the inventive methods is, therefore, a data carrier (or a digital storage medium, or a computer-readable medium) comprising, recorded thereon, the computer program for performing one of the methods described herein. The data carrier, the digital storage medium or the recorded medium are typically tangible and/or non-transitionary. 
     A further embodiment of the inventive method is, therefore, a data stream or a sequence of signals representing the computer program for performing one of the methods described herein. The data stream or the sequence of signals may for example be configured to be transferred via a data communication connection, for example via the Internet. 
     A further embodiment comprises a processing means, for example a computer, or a programmable logic device, configured to or adapted to perform one of the methods described herein. 
     A further embodiment comprises a computer having installed thereon the computer program for performing one of the methods described herein. 
     A further embodiment according to the invention comprises an apparatus or a system configured to transfer (for example, electronically or optically) a computer program for performing one of the methods described herein to a receiver. The receiver may, for example, be a computer, a mobile device, a memory device or the like. The apparatus or system may, for example, comprise a file server for transferring the computer program to the receiver. 
     In some embodiments, a programmable logic device (for example a field programmable gate array) may be used to perform some or all of the functionalities of the methods described herein. In some embodiments, a field programmable gate array may cooperate with a microprocessor in order to perform one of the methods described herein. Generally, the methods are advantageously performed by any hardware apparatus. 
     While this invention has been described in terms of several embodiments, there are alterations, permutations, and equivalents which fall within the scope of this invention. It should also be noted that there are many alternative ways of implementing the methods and compositions of the present invention. It is therefore intended that the following appended claims be interpreted as including all such alterations, permutations and equivalents as fall within the true spirit and scope of the present invention. 
     REFERENCES 
     
         
         [1] J. Barreto, J. Roquette, P. Sturm, and F. Fonseca. Automatic camera calibration applied to medical endoscopy. In BMVC 2009-20th British Machine Vision Conference, pages 1-10, London, United Kingdom, 2009. The British Machine Vision Association (BMVA). 
         [2] D. C. Brown. Close-range camera calibration. Photogrammetric Engineering, 37:855-866, 1971. 
         3] T. F. Cootes and C. J. Taylor. Active shape models—‘smart snakes’. In Proceedings of the British Machine Vision Conference, pages 28.1-28.10. BMVA Press, 1992. doi:10.5244/C.6.28. 
         [4] R. O. Duda, D. G. Stork, and P. E. Hart. Pattern classification and scene analysis. Wiley, New York, USA, 2nd edition, 2001. 
         [5] A. Ernst, A. Papst, T. Ruf, and J.-U. Garbas. Check My Chart: A Robust Color Chart Tracker for Colorimetric Camera Calibration. In Proceedings of the 6th International Conference on Computer Vision/Computer Graphics Collaboration 8 Techniques and Applications, MIRAGE &#39;13, pages 5:1-5:8, New York, N.Y., USA, 2013. ACM. 
         [6] M. Fiala and C. Shu. Fully automatic camera calibration using self-identifying calibration targets. 2005. 
         [7] P. Fuersattel, S. Dotenco, S. Placht, M. Balda, A. Maier, and C. Riess. Ocpad—occluded checkerboard pattern detector. In Applications of Computer Vision (WACV), 2016 IEEE Winter Conference on, March 2016. 
         [8] J. Mallon and P. F. Whelan. Which pattern? biasing aspects of planar calibration patterns and detection methods. Pattern recognition letters, 28(8):921-930, 2007. 
         [9] A. Malti and J. P. Barreto. Hand-eye and radial distortion calibration for rigid endoscopes. The International Journal of Medical Robotics and Computer Assisted Surgery, 9(4):441-454, 2013. 
         [10] R. Melo, J. Barreto, and G. Falcão. A New Solution for Camera Calibration and Real-Time Image Distortion Correction in Medical Endoscopy—Initial Technical Evaluation. IEEE Transactions on Biomedical Engineering, 59(3):634-644, March 2012. 
         [11] R. Tsai. A Versatile Camera Calibration Technique for High-accuracy 3D Machine Vision Metrology Using Off-the-shelf TV Cameras and Lenses. In L. Wolff, S. Shafer, and G. Healey, editors, IEEE Journal of Robotics and Automation, pages 221-224. USA, 1987. 
         [12] P. Viola and M. Jones. Rapid object detection using a boosted cascade of simple features. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, volume 1, pages 511-518. IEEE, 2001. 
         [13] G.-Q. Wei and S. D. Ma. Implicit and explicit camera calibration: theory and experiments. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5): 469-480, 1994. 
         [14] Z. Zhang. A flexible new technique for camera calibration. In IEEE Transactions on Pattern Analysis and Machine Intelligence, page 22, 2000.