Abstract:
A technique that improves image analysis efficiency by reducing the number of computations needed to detect constant regions. Constant region detection according to the present techniques includes determining whether an image analysis window at a current position contains a constant region by analyzing a new line of pixels in the image analysis window if a pixel at a predetermined location in the image analysis window in the current position has a value equal to a pixel at the predetermined location from a previous position of the image analysis window. Analyzing only the new line of pixels saves the computational time that would otherwise go into analyzing all of the pixels in the image analysis window.

Description:
BACKGROUND  
       [0001]     A variety of devices may perform image analysis. For example, a computer system may analyze an image to detect features of interest in the image before sending the image to a printer. Similarly, a printer may analyze an image to detect features of interest in the image before printing the image. An example of a feature of interest in an image is a boundary between objects contained in the image.  
         [0002]     An image undergoing analysis may be represented as a two-dimensional array of pixels each having a value. An image represented as a two-dimensional array of pixels may be referred to as an image frame. An image frame may be analyzed using an image analysis window that encompasses a portion of the image frame. An image analysis window may be used to divide image analysis into successive analyses of relatively small areas of an image frame.  
         [0003]     An analysis of an image frame may include determining whether an image analysis window contains a constant region. A constant region may be defined as a region in which all of the pixels have substantially similar values according to an analysis metric, e.g. the values are substantially similar within a predetermined tolerance. A detection of a constant region may be used, for example, to rule out the constant region as containing features of interest  
         [0004]     Prior methods for determining whether an image analysis window contains a constant region may include analyzing all of the pixels contained in the image analysis window. Unfortunately, analyzing all of the pixels contained in an image analysis window as the image analysis window is scanned over an image frame may be computationally intensive. For example, a 3 pixel by 3 pixel image analysis window applied to a 512 pixel wide image frame would include analyzing 9 pixels 512 times in just one 3 pixel high swath across the image frame. Large numbers of computations in detecting constant regions of an image frame slows the process of image analysis and may increase the cost of image analysis.  
       SUMMARY OF THE INVENTION  
       [0005]     A technique is disclosed that improves image analysis efficiency by reducing the number of computations needed to detect constant regions. Constant region detection according to the present techniques includes determining whether an image analysis window at a current position contains a constant region by analyzing a new line of pixels in the image analysis window if a pixel at a predetermined location in the image analysis window in the current position has a value equal to a pixel at the predetermined location from a previous position of the image analysis window. Analyzing only the new line of pixels saves the computational time that would otherwise go into analyzing all of the pixels in the image analysis window.  
         [0006]     Other features and advantages of the present invention will be apparent from the detailed description that follows.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0007]     The present invention is described with respect to particular exemplary embodiments thereof and reference is accordingly made to the drawings in which:  
         [0008]      FIG. 1  shows a device that performs image analysis according to the present teachings;  
         [0009]      FIG. 2  illustrates an image frame stored in an image buffer and an image analysis window used to analyze the image frame;  
         [0010]      FIGS. 3   a - 3   b  illustrate an example of constant region detection according to the present teachings;  
         [0011]      FIG. 4  shows a method for efficient detection of a constant region of an image according to the present teachings.  
     
    
     DETAILED DESCRIPTION  
       [0012]      FIG. 1  shows a device  10  that performs image analysis according to the present teachings. The device  10  includes an image buffer  12  and an image processor  14 . The image processor  14  accesses image frames stored in the image buffer  12  and analyzes the image frames including detecting constant regions of the image frames.  
         [0013]      FIG. 2  illustrates an image frame  20  stored in the image buffer  12 . The image frame  20  includes a two-dimensional array of pixels. The array has a width of x1 pixels and a height of y1 pixels with respect to a set of x-y axes.  
         [0014]     The image frame  20  includes an object  22 . In this example, the values of the pixels in the object  22  are substantially similar, i.e. the object  22  has a substantially uniform color and intensity. In addition, the values of the pixels in the image frame  20  that are outside of the object  22  are substantially different from the pixels of the object  22 .  
         [0015]     The image processor  14  analyzes the image frame  20  using an image analysis window  24 . The image analysis window  24  is relatively small in comparison to the image frame  20 . For example, the image analysis window  24  may be 3 pixels by 3 pixels, or 5 pixels by 5 pixels, or 7 pixels by 7 pixels, etc., while the image frame  20  may be 800 pixels by 600 pixels, or 1024 pixels by 768 pixels, etc.  
         [0016]     The image processor  14  analyzes the image frame  20  by scanning the image frame  20  using the image analysis window  24 . In one embodiment, the image processor  14  scans the image frame  20  from top-left to bottom-right. For example, the image processor  14  may place the image analysis window  24  so that it overlaps the top left pixels of the image frame  20  and then shift the image analysis window  24  to the right one pixel at a time until the line of pixels at x=x1 is reached. The image processor  14  may then move the image analysis window  24  down by the height of the image analysis window  24  and to the left to x=1 and then scan across as before, etc.  
         [0017]     Each time that the image processor  14  shifts the image analysis window  24  to include a new line of pixels of the image frame  20  it determines whether the image analysis window  24  at its current position contains a constant region of the image frame  20 . If the image analysis window  24  at its previous position did not contain a constant region then the image processor  14  determines whether the image analysis window  24  at its current position contains a constant region by analyzing all of the pixels in the image analysis window  24  at its current position, e.g. using known techniques.  
         [0018]     On the other hand, if the image analysis window  24  at its previous position did contain a constant region then the image processor  14  determines whether the image analysis window  24  at its current position contains a constant region using the following analysis that enables a reduction in computational load on the image processor  14 . The image processor  14  detects a constant region by analyzing only the new line of pixels at the current position of the image analysis window  24  if a pixel at a predetermined location in the image analysis window  24  at its current position has a value equal to a value of a pixel in the predetermined location in the image analysis window  24  at its previous position. Only the pixels in the new line need to be analyzed under this condition because all of the other pixels in the image analysis window  24  in its current position are already known to be constant with respect to the pixel at the predetermined location because the image analysis window  24  at its previous position contained a constant region. The new line of pixels may be analyzed by comparing the values in the new line to the value at the predetermined location. If the value of the pixel at the predetermined location in the image analysis window  24  in its current position does not equal the value of the pixel at the predetermined location in the image analysis window  24  at its previous position then the image processor  14  analyzes all of the pixels in the image analysis window  24  to detect a constant region. In one embodiment, the predetermined location is a center pixel of the image analysis window  24 .  
         [0019]      FIGS. 3   a - 3   b  illustrate an example of constant region detection according to the present teachings. The image frame  20  in this example includes an array of pixels P(1,1) through P(9,9). The object  22  in this example is a square region with corner pixels at P(3,3), P(7,3), P(3,7), and P(7,7) . The pixels of the object  22  all have values equal to P1 and the pixels outside of the object  22  all have values equal to P2.  
         [0020]      FIG. 3   a  shows the image analysis window  24  as a 3 by 3 window at a position that includes the pixels P(3,5), P(3,6), P(3,7), P(4,5), P(4,6), P(4,7), P(5,5), P(5,6), and P(5,7) . The image analysis window  24  at its previous position did not contain a constant region because it included the line of pixels P(2,5), P(2,6), and P(2,7) each having the value P2 and the pixels P(3,5), P(3,6), P(3,7), P(4,5), P(4,6), and P(4,7) each having the value P1. As a consequence, the image processor  14  determines whether the image analysis window  24  contains a constant region by analyzing all of the pixels P(3,5), P(3,6), P(3,7), P(4,5), P(4,6), P(4,7), P(5,5), P(5,6), and P(5,7). The image processor  14  records the value of the pixel at the center of the analysis window  24 , i.e. the value P1 of pixel P(4,6).  
         [0021]      FIG. 3   b  shows the image analysis window  24  shifted to the right to include a new line of pixels P(6,5), P(6,6), and P(6,7). The image analysis window  24  at its previous position did contain a constant region so the image processor  14  determines whether the image analysis window  24  at its current position contains a constant region by analyzing only the new line of pixels if the pixel at the center of the image analysis window  24  at its current position, i.e. the pixel P(5,6), has a value equal to the pixel at the center of the previous position of the image analysis window  24 , i.e. the pixel P(4,6). Given that the value of pixel P(5,6) equals the value of the pixel P(4,6) of P1, the image processor  14  detects a constant region in the current position of the image analysis window by analyzing only the pixels P(6,5), P(6,6), and P(6,7). Thus, the computational time that would otherwise be involved in analyzing the remaining pixels P(4,5), P(4,6), P(4,7), P(5,5), P(5,6), and P(5,7) in the image analysis window  24  in its current position is saved.  
         [0022]      FIG. 4  shows a method for efficient detection of a constant region of an image according to the present teachings. At step  100 , an image analysis window is shifted to a current position that includes a new line of pixels from an image frame. At step  102 , it is determined whether a pixel at the center (or some other predetermined location) of the image analysis window in the current position has a value that equals a pixel at the center (or some other predetermined location) of the image analysis window at the previous position of the image analysis window. If the answer is yes then step  104  is performed. Otherwise, step  106  is performed.  
         [0023]     At step  104 , a constant region is detected by analyzing the new line of pixels. The new line of pixels may be analyzed using know techniques, e.g. by determining whether the values of the new line of pixels are within a predetermined tolerance.  
         [0024]     At step  106 , a constant region is detected by analyzing all of the pixels in the image analysis window at its current position. The pixels may be analyzed using know techniques, e.g. by determining whether the values of the pixels are within a predetermined tolerance.  
         [0025]     The present techniques may be implemented in a wide variety of devices including computer systems, computing device, printers or other image generating devices, handheld and portable devices, etc. In addition, the present techniques may be implemented in a variety of image processing systems including image processing performed in software on computer systems as well as application-specific image processing systems.  
         [0026]     The foregoing detailed description of the present invention is provided for the purposes of illustration and is not intended to be exhaustive or to limit the invention to the precise embodiment disclosed. Accordingly, the scope of the present invention is defined by the appended claims.