A Sobel Edge Detector Digital Filter Structure and its Distributed Arithmetic Implementation
Kobchai Dejhan, Fusak Cheevasuvit, Somjin Thongplew, Soontorn Oraintara
Faculty of Engineering, King Mongkut's Institute of Technology Ladkraband
Ladkrabang, Bangkok 10520, Thailand
Tel : 66-2-326 9967, 66-2-326 9081,
Fax 66-2-326 9086, 66-2-326 9965
Narong Arjrith
Faculty of Engineering, Srinakharinwirot University
Bangkhen, Bangkok 10220 Thailand
Tel : 66-2-972 9652, 66-2-521 1005, 66-2-521 1108 ext 474
Ekachai Prommas
Faculty of Engineering, Kasembundit Unversity
Patanakarn Road, Bangkok 10250, Thailand
Tel : 66-2-321 6930-39 ext 212
Abstract
Edge detection is an important step in most image segmentation techniques. It Can identify the areas of a image where larges change in intensity occur. These changes are associated with the physical boundary or edge in the scene from which the image is derived. The ultimate object i segmentation is to develope contiguous set of pixels forming a closed contour around each object of interest in the 9mage with more heuristic rules- based algorithms which track boundaries and link edged to form whole contours. Sobel edge detection method based on Sobel operators has the advantage of emphasizing the central part of the edge. Each direction of Sobel operator is applied to an image, then two new images are created. One image shows the vertical response and the other shows the horizontal response. The purpose is to determine the existence and location of edges in a picture. Two images in combined into a single one. Distributed arithmetic (DA) is used in digital signal and image processing instead of the encountered form of computation such as sum of products. DA is an extreme computational efficiencies and exploited in circuit design form. This paper proposes an implementation of 2-dimensional digital image filter for low pass filter and Sobel edge detector. The method of DA in this paper is a transformation of transfer function by using look-up table.
Theory
The distributed arithmetic (DA) is a bit serial computational operation by forming an inner product (or dot product) of a pair of vectors in a single direct step. The method is to distribute all of the number into binary digit in order to process the signal in the form of digital circuit. The use of DA will be high efficiency in the case of sum of multiplication equation. The DA technique is faster than standard microprocessor when used the same clock rate [2,3]. DA uses look-up table to multiple the input signal with the coefficients which are stored in memory unit.
consider the calculation of the following sum of products: [1]
The A
k are fixed coefficients, and Xk are the input data words. If X
k is a 2's-complement binary number scaled such that Xk<1, then the expression of each X
k can be shown as
where the B
kn are the bits, 0 or 1, b
k0 is the sign bit,
b
k,N-1, is the least significant bit (LSB), and N is number of bit per input data.
The equation can be obtained:
Rearrange the equation, thus
Distribute the equation :
The equation (5) is distributed arithmetic form, consider the factor
and suppose that it is equal to Y'. Then, the equation is shown as
The b
kn are the bits, 0 or 1. Thus, Y '. should be possible 2k values and these values will be calculated and pass to store in ROM as in Table 1. The input data will be used to be ROM address. The final results will be stored in accumulator [5,6] and obtain the output Y. Fig.1 shows the distributed arithmetic structure [1] of the type 1 BAAT (one-bit-at-a-time) for equation (1).
Table 1 Stored data in ROM [1]
| 1£n£N-1 |
| Input Code |
32-Word
Memory Content |
| Ts |
b1n |
b2n |
b3n |
b4n |
| 0 |
0 |
0 |
0 |
0 |
0 |
| 0 |
0 |
0 |
0 |
1 |
A4=0.11 |
| 0 |
0 |
0 |
1 |
0 |
A3=0.95 |
| 0 |
0 |
0 |
1 |
1 |
A3+A4=1.06 |
| 0 |
0 |
1 |
0 |
0 |
A2=-0.30 |
| 0 |
0 |
1 |
0 |
1 |
A2+A4=-0.19 |
| 0 |
0 |
1 |
1 |
0 |
A2+A3=0.65 |
| 0 |
0 |
1 |
1 |
1 |
A2+A3+A4=0.75 |
| 0 |
1 |
0 |
0 |
0 |
A1=0.72 |
| 0 |
1 |
0 |
0 |
1 |
A1+A4=0.83 |
| 0 |
1 |
0 |
1 |
0 |
A1+A3=1.67 |
| 0 |
1 |
0 |
1 |
1 |
A1+A3+A4=1.78 |
| 0 |
1 |
1 |
0 |
0 |
A1+A2=0.42 |
| 0 |
1 |
1 |
0 |
1 |
A1+A2+A4=0.53 |
| 0 |
1 |
1 |
1 |
0 |
A1+A2+A3=1.37 |
| 0 |
1 |
1 |
1 |
1 |
A1+A2+A3+A4=1.48 |
Figure 1 DA Structure of type 1 BAAT for equation (1)
An application of DA can be used with two-dimensional signal processing, for example the digital filter [10]. Therefore, the linear differential equation of two-dimensional second order recursive digital filter [5]. has a general form as :
The X
m,n and Y
m,n are output data of system, respectively, The a
k,1 and b
i,j are fixed coefficients of filtering, its values are between +1 of 2's s-complement for B bit resolution including 1 sign bit.
