# Patent

## Title
Method for generating orientation image

## Abstract

A method for generating an orientation image, adapted to an electronic device, includes the following steps. A plurality of input pixels including a current input pixel of an input image is received. Edge detection is performed on the current input pixel in a first and second direction to generate a first current gradient and a second current gradient respectively with respect to the first direction and the second direction. A ratio of the first current gradient to a current gradient absolute sum is calculated to obtain a current ratio, where the current gradient absolute sum is a sum of absolute values of the first and second current gradient. A sign of the second current gradient is extracted to obtain a current sign. The current ratio and the current sign are inputted to a lookup table to obtain an image orientation angle corresponding to the current input pixel.

## Background
CROSS-REFERENCE TO RELATED APPLICATION
This application claims the priority benefit of Taiwan application serial no. 103125530, filed on Jul. 25, 2014. The entirety of the above-mentioned patent application is hereby incorporated by reference herein and made a part of this specification.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to an image processing technique, in particular, to a method for generating an orientation image.
2. Description of Related Art
Edge detection is a critical pre-processing step of object detection in the field of computer vision and image processing. The term “edge” is referred to as a set of neighboring pixels with sharp variation in an image, i.e. regions with discontinuous and rough neighboring pixels. In general, after edge detection is performed on an image in a horizontal and a vertical direction, a gradient intensity and a gradient orientation of each pixel may be accordingly calculated. Thus, image feature extraction may be performed in a follow-up process through, for example, a histogram of oriented gradient (HoG) technique so as to detect an object in the image.
However, given a horizontal gradient Gx and a vertical gradient Gy of a pixel, efficient execution or sufficient memory space is required. For example, to obtain a gradient orientation of the pixel via an arcsine lookup table approach, it is necessary to compute the term




  
    Gx
    
      
        
          Gx
          2
        
        +
        
          Gy
          2
        
      
    
  
  ,




and yet a square-root computation is expensive for a low-cost chip. On the other hand, to obtain the gradient orientation via an arctangent lookup table approach, since the value of





  Gy
  Gx




ranges between −∞ and +∞, an arctangent lookup table may not provide enough coverage for all inputs. Additionally, to obtain the gradient orientation via a two-dimensional arctangent lookup table approach such that the lookup table is constructed based on positive and negative signs of horizontal gradients Gx and vertical gradients Gy as well as





  
    Gy
    Gx
  
  ,




large memory space is required for storing such two-dimensional lookup table. The two-dimensional lookup table may be unfavorable to be loaded into an on-chip memory for real-time computation.

SUMMARY OF THE INVENTION
Accordingly, the invention is directed to a method for generating an orientation image, where an orientation image associated with an input image may be generated precisely in real time with low-cost implementation.
The invention is directed to a method for generating an orientation image, adapted to an electronic device, where the orientation image includes a plurality of image orientation angles, and each of the image orientation angles ranges between 0 and 2π or between 0 and 360°. The method includes the following steps. First, a plurality of input pixels of an input image are received, where the input pixels include a current input pixel. Edge detection is performed on the current input pixel in a first direction and a second direction so as to respectively generate a first current gradient and a second current gradient with respect to the first direction and the second direction. A ratio of the first current gradient to a current gradient absolute sum is calculated so as to obtain a current ratio, where the current gradient absolute sum is a sum of an absolute value of the first current gradient and an absolute value of the second current gradient. A sign of the second current gradient is extracted so as to obtain a current sign. The current ratio and the current sign are input to a lookup table so as to obtain the image orientation angle corresponding to the current input pixel.
According to an embodiment of the invention, the method for constructing the lookup table includes the following steps. A plurality of first components having positive signs, negative signs, and zeros as well as a plurality of second components having positive signs, negative signs, and zeros are provided. For each set formed by any one of the first components and any one of the second components: a first ratio corresponding to the first component is calculated, where the first ratio is equal to the first component divided by a square root of a sum of squares of the first component and the second component; a sign of the second component is extracted so as to obtain a reference sign; an orientation angle is calculated by using an arccosine function or an arcsine function according to the first ratio and the reference sign, where the orientation angle ranges between 0 and 2π or between 0 and 360°; a second ratio corresponding to the first component is calculated, where the second ratio is equal to the first component divided by a sum of an absolute value of the first component and an absolute value of the second component; and the lookup table is constructed according to the second ratio, the reference sign, and the orientation angle, where inputs of the lookup table are the second ratio and the reference sign, and where an output of the lookup table is the orientation angle.
According to an embodiment of the invention, the first direction is orthogonal to the second direction.
The invention is directed to a method for generating an orientation image, adapted to an electronic device, where the orientation image includes a plurality of image orientation angles, and each of the image orientation angles ranges between 0 and π or between 0 and 180°. The method includes the following steps. First, a plurality of input pixels of an input image are received, where the input pixels include a current input pixel. Edge detection is performed on the current input pixel in a first direction and a second direction so as to respectively generate a first current gradient and a second current gradient with respect to the first direction and the second direction. A ratio of the first current gradient to a current gradient absolute sum is calculated so as to obtain a current ratio, where the current gradient absolute sum is a sum of an absolute value of the first current gradient and an absolute value of the second current gradient. The current ratio is input to a lookup table so as to obtain the image orientation angle corresponding to the current input pixel.
According to an embodiment of the invention, the method for constructing the lookup table includes the following steps. A plurality of first components having positive signs, negative signs, and zeros as well as a plurality of second components having positive signs, negative signs, and zeros are provided. For each set formed by any one of the first components and any one of the second components: a first ratio corresponding to the first component is calculated, where the first ratio is equal to the first component divided by a square root of a sum of squares of the first component and the second component; an orientation angle is calculated by using an arccosine function or an arcsine function according to the first ratio and the reference sign, where the orientation angle ranges between 0 and π or between 0 and 180°; a second ratio corresponding to the first component is calculated, where the second ratio is equal to the first component divided by a sum of an absolute value of the first component and an absolute value of the second component; and the lookup table is constructed according to the second ratio and the orientation angle, where an input of the lookup table is the second ratio, and where an output of the lookup table is the orientation angle.
According to an embodiment of the invention, the first direction is orthogonal to the second direction.
The present invention is directed to a method for generating an orientation image, adapted to an electronic device, where the orientation image includes a plurality of image orientation angles, and each of the image orientation angles ranges between 0 and π/4 or between 0 and 90°. The method includes the following steps. First, a plurality of input pixels of an input image are received, where the input pixels include a current input pixel. Edge detection is performed on the current input pixel in a first direction and a second direction so as to respectively generate a first current gradient and a second current gradient with respect to the first direction and the second direction. A ratio of an absolute value of the first current gradient to a current gradient absolute sum is calculated so as to obtain a current ratio, where the current gradient absolute sum is a sum of an absolute value of the first current gradient and an absolute value of the second current gradient. The current ratio is input to a lookup table so as to obtain the image orientation angle corresponding to the current input pixel.
According to an embodiment of the invention, the method for constructing the lookup table includes the following steps. A plurality of first components having positive signs and zeros as well as a plurality of second components having positive signs and zeros are provided. For each set formed by any one of the first components and any one of the second components: a first ratio corresponding to the first component is calculated, where the first ratio is equal to the first component divided by a square root of a sum of squares of the first component and the second component; an orientation angle is calculated by using an arccosine function or an arcsine function according to the first ratio and the reference sign, where the orientation angle ranges between 0 and π/4 or between 0 and 90°; a second ratio corresponding to the first component is calculated, where the second ratio is equal to the first component divided by a sum of an absolute value of the first component and an absolute value of the second component; and the lookup table is constructed according to the second ratio and the orientation angle, where an input of the lookup table is the second ratio, and where an output of the lookup table is the orientation angle.
According to an embodiment of the invention, the first direction is orthogonal to the second direction.
To sum up, in the method of the invention for generating an orientation image, a lookup table mathematically equivalent to an arcsine lookup table or an arccosine lookup table is prestored in an electronic device, where large memory space is not a requirement. After an input image is received and a first and a second current gradient of each input pixels are obtained through edge detection, a square-root and a square computation requiring high processing cost are replaced by an absolute computation, and an orientation image may be obtained by using the aforementioned lookup table. Accordingly, while generating a precise orientation image, the applicability of the technique proposed in the invention is increased in practical application especially for consumer electronic products integrated with a low-cost chip having a real-time computational capability.



BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings are included to provide a further understanding of the invention, and are incorporated in and constitute a part of this specification. The drawings illustrate embodiments of the invention and, together with the description, serve to explain the principles of the invention.
FIG. 1 illustrates a flowchart of a method for constructing a lookup table of an orientation image according to an embodiment of the invention.
FIG. 2 illustrates a flowchart of a method for generating an orientation image according to the embodiment of FIG. 1.
FIG. 3 illustrates a flowchart of another method for constructing a lookup table of an orientation image according to an embodiment of the invention.
FIG. 4 illustrates a flowchart of a method for generating an orientation image according to the embodiment of FIG. 3.
FIG. 5 illustrates a flowchart of another method for constructing a lookup table of an orientation image according to an embodiment of the invention.
FIG. 6 illustrates a flowchart of a method for generating an orientation image according to the embodiment of FIG. 5.



DESCRIPTION OF THE EMBODIMENTS
Given a horizontal gradient Gx and a vertical gradient Gy of a pixel, in order to obtain a gradient orientation of the pixel via an arcsine lookup table approach, it is a necessity to compute the term




  
    Gx
    
      
        
          Gx
          2
        
        +
        
          Gy
          2
        
      
    
  
  ,




and yet a square-root computation is relatively expensive for a low-cost chip. The main concept of the invention is to perform an absolute computation (|Gx|+|Gy|) with lower computational cost instead of a square-root and a square computation (√{square root over (Gx2+Gy2)}) with higher computational cost as well as to pre-construct a lookup table mathematically equivalent to an arcsine lookup table or an arccosine lookup table, and thus an orientation image of an input image may be obtained precisely in real-time.

Reference will now be made in detail to the present embodiments of the invention, examples of which are illustrated in the accompanying drawings. Wherever possible, the same reference numbers are used in the drawings and the description to refer to the same or like parts. In addition, the specifications and the like shown in the drawing figures are intended to be illustrative, and not restrictive. Therefore, specific structural and functional detail disclosed herein are not to be interpreted as limiting, but merely as a representative basis for teaching one skilled in the art to variously employ the invention.
FIG. 1 illustrates a flowchart of a method for constructing a lookup table of an orientation image according to an embodiment of the invention. The lookup table herein is mathematically equivalent to an arcsine lookup table or an arccosine lookup table and is adapted to generate an orientation image with orientation angles ranging between 0 and 2π or between 0 and 360°.
Referring to FIG. 1, in Step S110, a plurality of first components with respect to a first direction and having positive signs, negative signs, and zeros as well as a plurality of second components with respect to a second direction and having positive signs, negative signs, and zeros are provided. In the present embodiment, the first direction is orthogonal to the second direction. In other words, each of the first components is a horizontal component Gx, and each of the second components is a vertical component Gy. The precision of the lookup table is determined by the number of the first components and the second components.
Next, the following steps may be performed on each set (Gx, Gy) formed by any one of the first components and any one of the second components. In Step S120, a first ratio corresponding to the first component is calculated, where the first ratio is equal to the first component divided by a square root of a sum of squares of the first component and the second component and may be written as Eq. (1.1):




  
    
      
        
          R
          1
        
        =
        
          Gx
          
            
              
                Gx
                2
              
              +
              
                Gy
                2
              
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        
          (
          1.1
          )
        
      
    
  




where R1 represents the first ratio. Since the lookup table in the present embodiment is adapted to generate an orientation image with orientation angles ranging between 0 and 2π or between 0 and 360°, in Step S130, a sign of the second component is extracted so as to obtain a reference sign, where the reference sign S may be written as Eq. (1.2):

S=sign(Gy)  Eq. (1.2)

Next, in Step S140, an orientation angle is calculated by using an arccosine function or an arcsine function according to the first ratio and the reference sign respectively obtained in Step S120 and Step S130. In other words, after arccos(R1 or arcsin(R1) is calculated, the orientation angle θ may be obtained according to the reference sign S. Since the first component is set to the horizontal component Gx, the orientation angle θ may be obtained by using the arcsine function arcsin(R1) in conjunction with the orientation angle θ.
Moreover, in Step S150, a second ratio corresponding to the first component is calculated, where the second ratio is equal to the first component divided by a sum of an absolute value of the first component and an absolute value of the second component and may be written as Eq. (1.3):




  
    
      
        
          R
          2
        
        =
        
          Gx
          
            (
            
              
                
                Gx
                
              
              +
              
                
                Gy
                
              
            
            )
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        
          (
          1.3
          )
        
      
    
  




where R2 represents the second ratio.

In Step S160, the lookup table is constructed according to the second ratio, the reference sign, and the orientation angle computed in Step S140, where inputs of the lookup table are the second ratio and the reference sign, and an output of the lookup table is the orientation angle. Since the function for calculating the first ratio R1




  (
  
    i
    .
    e
    .
    
      
    
    ⁢
    
      Gx
      
        
          
            Gx
            2
          
          +
          
            Gy
            2
          
        
      
    
  
  )




and the function for calculating the second ratio R2





  (
  
    i
    .
    e
    .
    
      
    
    ⁢
    
      Gx
      
        (
        
          
            
            Gx
            
          
          +
          
            
            Gy
            
          
        
        )
      
    
  
  )




are both injective functions, the lookup table constructed in Step S160 is mathematically equivalent to the arcsine lookup table constructed based on the first ratio, the reference sign, and the orientation angle.

FIG. 2 illustrates a flowchart of a method for generating an orientation image according to the embodiment of FIG. 1. The orientation image in the present embodiment includes a plurality of image orientation angles, where each of the image orientation angles ranges between 0 and 2π or between 0 and 360°. The method is adapted to an electronic device with an image processing feature such as a personal computer, a laptop computer, a digital camera, a digital camcorder, a web camera, a smart phone, a tabular computer, a vehicle event recorder, a vehicle video and audio system, and so forth. The invention is not limited herein. The lookup table constructed in the embodiment of FIG. 1 is prestored in the electronic device.
Referring to FIG. 2, a plurality of input pixels of an input image are received in Step S210, where the input pixels includes a current input pixel. The input pixels are arranged in a matrix with columns and rows. Since the processing step is the same for each of the input pixels, only the current input pixel among the input pixels would be illustrated hereinafter.
Next, in Step S220 and Step 230, edge detection is performed on the current input pixel in a first direction and a second direction so as to respectively generate a first current gradient and a second current gradient with respect to the first direction and the second direction. To be specific, gradients of the current pixel with respect to different directions may be calculated by using an edge detection filter. In the present embodiment, the first direction is orthogonal to the second direction. The first current gradient with respect to the first direction and the second current gradient with respect to the second direction are a horizontal gradient Gx′ and a vertical gradient Gy′ of the current input pixel respectively.
In Step S240, a ratio of the first current gradient to a current gradient absolute sum is calculated so as to obtain a current ratio, where the current gradient absolute sum is a sum of an absolute value of the first current gradient and an absolute value of the second current gradient, and the current ratio R′ may be written as Eq. (2.1):




  
    
      
        
          R
          ′
        
        =
        
          
            Gx
            ′
          
          
            (
            
              
                
                
                  Gx
                  ′
                
                
              
              +
              
                
                
                  Gy
                  ′
                
                
              
            
            )
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        
          (
          2.1
          )
        
      
    
  




In Step S250, a sign of the second current gradient is extracted so as to obtain a current sign, where the current sign S′ may be written as Eq. (2.2):

S′=sign(Gy′)  Eq. (2.2)

Next, in Step S260, the current ratio and the current sign are input to the lookup table constructed in FIG. 1 so as to obtain the image orientation angle corresponding to the current input pixel, and the image orientation angle is output in Step S270. After all of the input pixels of the input image are processed, the orientation image ranging between 0 and 2π or between 0 and 360° would then be generated.

FIG. 3 illustrates a flowchart of another method for constructing a lookup table of an orientation image according to an embodiment of the invention. FIG. 4 illustrates a flowchart of a method for generating an orientation image according to the embodiment of FIG. 3. The lookup table constructed in FIG. 3 is mathematically equivalent to an arcsine lookup table or an arccosine lookup table and is adapted to generate an orientation image with orientation angles ranging between 0 and π or between 0 and 180°. The steps illustrated in FIG. 3 and FIG. 4 are similar to those in FIG. 1 and FIG. 2, and thus only the difference would be described in detail.
Referring to FIG. 3, in Step S310, a plurality of first components with respect to a first direction and having positive signs, negative signs, and zeros as well as a plurality of second components with respect to a second direction and having positive signs, negative signs, and zeros are provided. In the present embodiment, the first direction is orthogonal to the second direction. In other words, each of the first components is a horizontal component Gx, and each of the second components is a vertical component Gy.
Next, the following steps may be performed on each set (Gx, Gy) formed by any one of the first components and any one of the second components. In Step S320, a first ratio corresponding to the first component is calculated, where the first ratio is equal to the first component divided by a square root of a sum of squares of the first component and the second component and may be written as Eq. (3.1):




  
    
      
        
          R
          1
        
        =
        
          Gx
          
            
              
                Gx
                2
              
              +
              
                Gy
                2
              
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        
          (
          3.1
          )
        
      
    
  




where R1 represents the first ratio. Since the lookup table in the present embodiment is adapted to generate an orientation image with orientation angles ranging between 0 and π or between 0 and 180°, a sign of the second component (i.e. the vertical component) is not associated with the construction of the lookup table. A sign extraction process similar to Step S130 would not be performed on the second component herein.

Moreover, in Step S330, a second ratio corresponding to the first component is calculated, where the second ratio is equal to the first component divided by a sum of an absolute value of the first component and an absolute value of the second component, and may be written as Eq. (3.2):




  
    
      
        
          R
          2
        
        =
        
          Gx
          
            (
            
              
                
                Gx
                
              
              +
              
                
                Gy
                
              
            
            )
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        
          (
          3.2
          )
        
      
    
  




where R2 represents the second ratio.

In Step S340, an orientation angle is calculated by using an arccosine function or an arcsine function according to the first ratio obtained in Step S320. Since the first ratio has a positive or negative sign, the orientation angle θ calculated herein may range between 0 and π or between 0 and 180°.
In Step S350, the lookup table is constructed according to the second ratio and the orientation angle computed in Step S340, where an input of the lookup table is the second ratio, and an output of the lookup table is the orientation angle. The lookup table constructed in Step S350 is mathematically equivalent to the arcsine lookup table constructed based on the first ratio and the orientation angle.
Next, referring to FIG. 4, the orientation image in the present embodiment includes a plurality of image orientation angles, where each of the image orientation angles ranges between 0 and π or between 0 and 180°. The method in the present embodiment is adapted to an electronic device similar to that in the embodiment of FIG. 2, and the lookup table constructed in the embodiment of FIG. 3 is prestored in the electronic device.
In Step S410, a plurality of input pixels of an input image are received in Step S410, where the input pixels includes a current input pixel. Similarly, since the processing step is the same for each of the input pixels, only the current input pixel among the input pixels would be illustrated hereinafter.
Next, in Step S420 and Step S430, edge detection is performed on the current input pixel in a first direction and a second direction so as to respectively generate a first current gradient and a second current gradient with respect to the first direction and the second direction. In the present embodiment, the first direction is orthogonal to the second direction. The first current gradient with respect to the first direction and the second current gradient with respect to the second direction are a horizontal gradient Gx′ and a vertical gradient Gy′ of the current input pixel respectively.
In Step S440, a ratio of the first current gradient to a current gradient absolute sum is calculated so as to obtain a current ratio, where the current gradient absolute sum is a sum of an absolute value of the first current gradient and an absolute value of the second current gradient, and the current ratio R′ may be written as Eq. (4.1):




  
    
      
        
          R
          ′
        
        =
        
          
            Gx
            ′
          
          
            (
            
              
                
                
                  Gx
                  ′
                
                
              
              +
              
                
                
                  Gy
                  ′
                
                
              
            
            )
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        
          (
          4.1
          )
        
      
    
  




Next, in Step S450, the current ratio computed in Step S440 is input to the lookup table constructed in FIG. 3 so as to obtain the image orientation angle corresponding to the current input pixel, and the image orientation angle is output in Step S460. After all of the input pixels of the input image are processed, the orientation image ranging between 0 and π or between 0 and 180° would then be generated.
FIG. 5 illustrates a flowchart of another method for constructing a lookup table of an orientation image according to an embodiment of the invention. FIG. 6 illustrates a flowchart of a method for generating an orientation image according to the embodiment of FIG. 5. The lookup table constructed in FIG. 5 is mathematically equivalent to an arcsine lookup table or an arccosine lookup table and is adapted to generate an orientation image with orientation angles ranging between 0 and π/4 or between 0 and 90°. The steps illustrated in FIG. 5 and FIG. 6 are similar to those in FIG. 1 and FIG. 2, and thus only the difference would be described in detail.
Referring to FIG. 5, in Step S510, a plurality of first components with respect to a first direction and having positive signs and zeros as well as a plurality of second components with respect to a second direction and having positive signs and zeros are provided. In the present embodiment, the first direction is orthogonal to the second direction. In other words, each of the first components is a horizontal component Gx, and each of the second components is a vertical component Gy.
Next, the following steps may be performed on each set (Gx, Gy) formed by any one of the first components and any one of the second components. In Step S520, a first ratio corresponding to the first component is calculated, where the first ratio is equal to the first component divided by a square root of a sum of squares of the first component and the second component and may be written as Eq. (5.1):




  
    
      
        
          R
          1
        
        =
        
          
            
            Gx
            
          
          
            
              
                Gx
                2
              
              +
              
                Gy
                2
              
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        
          (
          5.1
          )
        
      
    
  




where R1 represents the first ratio. Since the lookup table in the present embodiment is adapted to generate an orientation image with orientation angles ranging between 0 and π/4 or between 0 and 90°, the first component and the second component are positive or zeros. A sign extraction process similar to Step S130 would not be performed on the second component herein.
Moreover, a second ratio corresponding to the first component is calculated in Step S530, where the second ratio is equal to the first component divided by a sum of an absolute value of the first component and an absolute value of the second component and may be written as Eq. (5.2):




  
    
      
        
          R
          2
        
        =
        
          
            
            Gx
            
          
          
            (
            
              
                
                Gx
                
              
              +
              
                
                Gy
                
              
            
            )
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        
          (
          5.2
          )
        
      
    
  




where R2 represents the second ratio.

In Step S540, an orientation angle is calculated by using an arccosine function or an arcsine function according to the first ratio obtained in Step S520. Since the first ratio is positive or zero, the orientation angle θ calculated herein may range between 0 and π/4 or between 0 and 90°.
In Step S550, the lookup table is constructed according to the second ratio and the orientation angle computed in Step S540, where an input of the lookup table is the second ratio, and an output of the lookup table is the orientation angle. The lookup table constructed in Step S550 is mathematically equivalent to the arcsine lookup table constructed based on the first ratio and the orientation angle.
Next, referring to FIG. 6, the orientation image in the present embodiment includes a plurality of image orientation angles, where each of the image orientation angles ranges between 0 and π/4 or between 0 and 90°. The method in the present embodiment is adapted to an electronic device similar to that in the embodiment of FIG. 2, and the lookup table constructed in the embodiment of FIG. 5 is prestored in the electronic device.
In Step S610, a plurality of input pixels of an input image are received, where the input pixels includes a current input pixel. Similarly, since the processing step is the same for each of the input pixels, only the current input pixel among the input pixels would be illustrated hereinafter.
Next, in Step S620 and Step S630, edge detection is performed on the current input pixel in a first direction and a second direction so as to respectively generate a first current gradient and a second current gradient with respect to the first direction and the second direction. In the present embodiment, the first direction is orthogonal to the second direction. The first current gradient with respect to the first direction and the second current gradient with respect to the second direction are a horizontal gradient Gx′ and a vertical gradient Gy′ of the current input pixel respectively.
In Step S640, a ratio of an absolute value of the first current gradient to a current gradient absolute sum is calculated so as to obtain a current ratio, where the current gradient absolute sum is a sum of an absolute value of the first current gradient and an absolute value of the second current gradient, and the current ratio R′ may be written as Eq. (6.1):




  
    
      
        
          R
          ′
        
        =
        
          
            
            
              Gx
              ′
            
            
          
          
            (
            
              
                
                
                  Gx
                  ′
                
                
              
              +
              
                
                
                  Gy
                  ′
                
                
              
            
            )
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        
          (
          6.1
          )
        
      
    
  




Since the orientation angles of the orientation image to be generate in the present embodiment would range between 0 and π/4 or between 0 and 90°, the first current gradient is restricted to be positive.

Next, in Step S650, the current ratio computed in Step S640 is input to the lookup table constructed in FIG. 5 so as to obtain the image orientation angle corresponding to the current input pixel, and the image orientation angle is output in Step S660. After all of the input pixels of the input image are processed, the orientation image ranging between 0 and π/4 or between 0 and 90° would then be generated.
To sum up, in the method of the invention for generating an orientation image, a lookup table mathematically equivalent to an arcsine lookup table or an arccosine lookup table is prestored in an electronic device, where large memory space is not a requirement. After an input image is received and a first and a second current gradient of each input pixels are obtained through edge detection, a square-root and a square computation requiring high processing cost are replaced by an absolute computation, and an orientation image may be obtained by using the aforementioned lookup table. Accordingly, while generating a precise orientation image, the applicability of the technique proposed in the invention is increased in practical application especially for consumer electronic products integrated with a low-cost chip having a real-time computational capability.
It will be apparent to those skilled in the art that various modifications and variations can be made to the structure of the present invention without departing from the scope or spirit of the invention. In view of the foregoing, it is intended that the present invention cover modifications and variations of this invention provided they fall within the scope of the following claims and their equivalents.

## Claims

1. A method for generating an orientation image, adapted to an electronic device, wherein the orientation image comprises a plurality of image orientation angles, each of the image orientation angles ranges between 0 and 2π or between 0 and 360°, and wherein the method comprises:
receiving a plurality of input pixels of an input image, wherein the input pixels comprises a current input pixel;
performing edge detection on the current input pixel in a first direction and a second direction so as to respectively generate a first current gradient and a second current gradient with respect to the first direction and the second direction, wherein the first current gradient is a first component of a gradient of the current input pixel with respect to the first direction, and wherein the second current gradient is a second component of the gradient of the current input pixel with respect to the second direction;
calculating a ratio of the first current gradient to a current gradient absolute sum so as to obtain a current ratio, wherein the current gradient absolute sum is a sum of an absolute value of the first current gradient and an absolute value of the second current gradient;
extracting a sign of the second current gradient so as to obtain a current sign; and
inputting the current ratio and the current sign to a lookup table so as to obtain the image orientation angle corresponding to the current input pixel, wherein the lookup table maps the current ratio and the current sign to an arccosine value or an arcsine value, and wherein the lookup table outputs an orientation angle corresponding to the arccosine value or the arcsine value.

2. The method according to claim 1, wherein the steps for constructing the lookup table comprise:
providing a plurality of first components having positive signs, negative signs, and zeros as well as a plurality of second components having positive signs, negative signs, and zeros; and
for each set formed by any one of the first components and any one of the second components:
calculating a first ratio corresponding to the first component, wherein the first ratio is equal to the first component divided by a square root of a sum of squares of the first component and the second component;
extracting a sign of the second component so as to obtain a reference sign;
calculating an orientation angle by using an arccosine function or an arcsine function according to the first ratio and the reference sign, wherein the orientation angle ranges between 0 and 2π or between 0 and 360°;
calculating a second ratio corresponding to the first component, wherein the second ratio is equal to the first component divided by a sum of an absolute value of the first component and an absolute value of the second component; and
constructing the lookup table according to the second ratio, the reference sign, and the orientation angle, wherein inputs of the lookup table are the second ratio and the reference sign, and wherein an output of the lookup table is the orientation angle.

3. The method according to claim 2, wherein the first direction is orthogonal to the second direction.

4. A method for generating an orientation image, adapted to an electronic device, wherein the orientation image comprises a plurality of image orientation angles, each of the image orientation angles ranges between 0 and π or between 0 and 180°, and wherein the method comprises:
receiving a plurality of input pixels of an input image, wherein the input pixels comprises a current input pixel;
performing edge detection on the current input pixel in a first direction and a second direction so as to respectively generate a first current gradient and a second current gradient with respect to the first direction and the second direction, wherein the first current gradient is a first component of a gradient of the current input pixel with respect to the first direction, and wherein the second current gradient is a second component of the gradient of the current input pixel with respect to the second direction;
calculating a ratio of the first current gradient to a current gradient absolute sum so as to obtain a current ratio, wherein the current gradient absolute sum is a sum of an absolute value of the first current gradient and an absolute value of the second current gradient; and
inputting the current ratio to a lookup table so as to obtain the image orientation angle corresponding to the current input pixel, wherein the lookup table maps the current ratio and the current sign to an arccosine value or an arcsine value, and wherein the lookup table outputs an orientation angle corresponding to the arccosine value or the arcsine value.

5. The method according to claim 4, wherein the steps for constructing the lookup table comprise:
providing a plurality of first components having positive signs, negative signs, and zeros as well as a plurality of second components having positive signs, negative signs, and zeros; and
for each set formed by any one of the first components and any one of the second components:
calculating a first ratio corresponding to the first component, wherein the first ratio is equal to the first component divided by a square root of a sum of squares of the first component and the second component;
calculating an orientation angle by using an arccosine function or an arcsine function according to the first ratio, wherein the orientation angle ranges between 0 and π or between 0 and 180°;
calculating a second ratio corresponding to the first component, wherein the second ratio is equal to the first component divided by a sum of an absolute value of the first component and an absolute value of the second component; and
constructing the lookup table according to the second ratio and the orientation angle, wherein an input of the lookup table is the second ratio, and wherein an output of the lookup table is the orientation angle.

6. The method according to claim 5, wherein the first direction is orthogonal to the second direction.

7. A method for generating an orientation image, adapted to an electronic device, wherein the orientation image comprises a plurality of image orientation angles, each of the image orientation angles ranges between 0 and π/4 or between 0 and 90°, and wherein the method comprises:
receiving a plurality of input pixels of an input image, wherein the input pixels comprises a current input pixel;
performing edge detection on the current input pixel in a first direction and a second direction so as to respectively generate a first current gradient and a second current gradient with respect to the first direction and the second direction, wherein the first current gradient is a first component of a gradient of the current input pixel with respect to the first direction, and wherein the second current gradient is a second component of the gradient of the current input pixel with respect to the second direction;
calculating a ratio of an absolute value of the first current gradient to a current gradient absolute sum so as to obtain a current ratio, wherein the current gradient absolute sum is a sum of an absolute value of the first current gradient and an absolute value of the second current gradient; and
inputting the current ratio to a lookup table so as to obtain the image orientation angle corresponding to the current input pixel, wherein the lookup table maps the current ratio and the current sign to an arccosine value or an arcsine value, and wherein the lookup table outputs an orientation angle corresponding to the arccosine value or the arcsine value.

8. The method according to claim 7, wherein the steps for constructing the lookup table comprise:
providing a plurality of first components having positive signs and zeros as well as a plurality of second components having positive signs and zeros; and
for each set formed by any one of the first components and any one of the second components:
calculating a first ratio corresponding to the first component, wherein the first ratio is equal to the first component divided by a square root of a sum of squares of the first component and the second component;
calculating an orientation angle by using an arccosine function or an arcsine function according to the first ratio, wherein the orientation angle ranges between 0 and π/4 or between 0 and 90°;
calculating a second ratio corresponding to the first component, wherein the second ratio is equal to the first component divided by a sum of a value of the first component and a value of the second component; and
constructing the lookup table according to the second ratio and the orientation angle, wherein an input of the lookup table is the second ratio, and wherein an output of the lookup table is the orientation angle.

9. The method according to claim 8, wherein the first direction is orthogonal to the second direction.