A Sobel Edge Detector Digital Filter Structure and its Distributed Arithmetic Implementation

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	32-Word Memory Content
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.

Design Technique
The system consists of the digital image calculation circuit and the imagery data delay line. The processes of imagery data for obtaining the new image (edge detection, contrast of image) depend on impulse response by using mask over imagery data and move it to every position of picture. All of data will be multiplied with the results and sum together. Therefore, the new digital image data will be obtained.

1	2	1
2	4	2
1	2	1

(Smooth filter)

0	-1	0
-1	5	-1
0	1	0

(high-pass filter)

-1	0	1
-1	0	1
-1	0	1

(vertical edge detection)

1	1	1
0	0	0
-1	-1	-1

(horizontal edge detection)

The Picture processing using DA uses the signal sequence X(m,n) to rearrange. All of 9 data sequence will pass to process by using look-up table which stored the data of low-pass filter ,high-pass filter of edge detector. The input data are in parallel and the are converted into serial ,DA will increase the processing speed better than the old method [2,3]. The digital image data delay line can be used serial shift register to shift the data.

Sobel Edge Detector
Sobel edge detector gets better the contour for object in image. The edge detection process is shown in Fig.2. The experiment uses the process as shown in Fig .3.DA convert the three sets of data (smooth filter, horizontal edge detector and vertical edge detector) as the method shown in table 2.

Table 2 Stored data in ROM

a b c d e f g h i	Y+aA+bB+cC+dD+eE+fF+gG+hH+iI
0 0 0 0 0 0 0 0 0	Y=0
0 0 0 0 0 0 0 0 0	Y=I
0 0 0 0 0 0 0 0 0	Y=H
0 0 0 0 0 0 0 0 0	Y=H+I
0 0 0 0 0 0 0 0 0	Y=G
0 0 0 0 0 0 0 0 0	Y=G+I
:	:
:	:
0 0 1 0 1 0 1 0 0	Y=C+E+G
0 0 1 0 1 0 1 0 1	Y=C+E+G+I
0 0 1 0 1 0 1 1 0	Y=C+E+G+H
0 0 1 0 1 0 1 1 1	Y=C+E+G+H+I
:	:
:	:
1 1 1 1 1 1 1 0 0	Y=A+B+C+D+E+F+G
1 1 1 1 1 1 1 0 1	Y=A+B+C+D+E+F+G+I
1 1 1 1 1 1 1 1 0	Y=A+B+C+D+E+F+G+H
1 1 1 1 1 1 1 1 1	Y=A+B+C+D+E+F+G+H+I

Figure 2 Edge detection diagram

Figure 3 Picture data processing based on DA
The hardware [7,8] can process only each digital image data and then arrange the vertical edge and horizontal edge data together by using software [9]. The increase of hardware can be done and will increase the processing speed and more convenient [4].

A	B	C
D	E	F
G	H	I

Results
The analytic digital image data and the effect of Sobel edge detector can be compared together as shown in Fig.4.

Fig.4 Comparison of analytic data and effects of sable edge detector.
Conclusion
The application of DA is used to apply for image processing and it can be implemented in easily form. This technique will be useful to construct the system that can use with picture of image processing.

References

S.A.White, "Applications of distributed arithmetic," IEEE ASSP Mag., vol.6, no.3, pp.4, 19, July 1989.
A. Peled and B. Liu, "A new hardware realization of digital filter," IEEE Trans. ASSP,vol.ASSP-22,pp.456-462, Dec.1974.
A. Pelt and B. Liu, "Digital signal processing," John wiley & Sons, pp.212-226, 1976.
D.F. Elliott. "Handbook of digital signal processing," Academic Press, PP.964-972, 1987.
H. Jaggernaught and A.N. Venetsanopoulos, "Real-time image, Processing through arithmetic," IEEE Trans. Circuit and systems, vol.1 pp.393-397, may 1983.
C.F.N. Cowan, S.G. Smith and J.H. Elliott, " A digital adaptive filter using a memory accumulator architecture," IEEE Trans. vol.1 pp. ASSP, vol.ASSP-31 June 1983.
K-S Lin, "Digital signal processing," Texas Instrument Series, prentice Hall, pp.F2-F9, 1988.
C.E. Sporck, "F 100 K ECL logic data book," National semiconductor ,pp.(3) 199-9(3)205, 1990.
P.M.Embree and B. Kimble, " C language algorithm for digital signal processing," Prentice Hall, pp.393-400. 1991.
J.S.Lim, "Two-dimensional signal and image processing," Prentice Hall, pp.476-487, 1990.