Switched-capacitor networks for scale-space generation

Switched-Capacitor Networks for Scale-Space Generation M. Su´arez, V.M. Brea, D. Cabello Centro de Investigaci´on en Tecnolog´ıas de la Informaci´on (CITIUS) University of Santiago de Compostela Santiago de Compostela, Spain Email:manuel.suarez.cam[email protected] F. Pozas-Flores, R. Carmona-Gal´an A. Rodr´ıguez-V´azquez Instituto de Microelectr´onica de Sevilla (IMSE-CNM) CSIC-Universidad de Sevilla, Spain Abstract—This work examines the parallel and the bilinear implementations as two different switched-capacitor network topologies for scale-space filtering. The paper assesses the validity of both topologies as scale-space generators in focal-plane processing through object detection with a known scale- and rotation-invariant feature extractor as SIFT. Keywords—switched-capacitor networks, scale-space theory, Gaussian Filtering, diffusion, SIFT. I. INTRODUCTION In scale-space theory signals are represented at several scales, each conveying different details of the original signal. Every new scale (σi) is the result of a smoothing operator on the former scale, either the original signal itself (scale σ0) or a former smoothed version (scale σi−1) [1]. Consistent scalespaces are generated when the structure or details of an image do not increase with the scale parameter σ, i.e., the number of local extrema cannot increase with σ. Babaud et al. show the uniqueness of the Gaussian function as the only valid smoothing operator in 1D signals [2]. In 2D signals, there is not any operator that guarantees that the number of local extrema does not increase with σ. Nevertheless, it is also shown that in continuous 2D signals, the Gaussian kernel is the operator that minimizes the appearance of new details with increasing smoothing [3]. In discrete 2D signals, e.g. images, the solution to the discretized version of the diffusion equation is a correct smoothing operator for scale-space generation [4]. RC networks implement naturally the discretized version of the diffusion equation; hence they provide valid scale-spaces. Reference [5] is a recent example of an RC network for focalplane processing. Therein the different σlevels were defined by sampling the transient evolution of the network. Switchedcapacitor networks are another alternative for an RC grid [6]. In this case, the network evolves across a series of stationary states obtained by charge redistribution among capacitors. This allows for an accurate control of the network evolution through the number of clock cycles. Besides, different network topologies and switching rate offer a great flexibility for focal plane processing. This work addresses two different switched-capacitor network topologies for scale-space filtering. The paper examines their drawbacks and benefits, and it also assesses their performance in focal plane-processing as scale-space generators with object detection with the SIFT algorithm [7]. II. SWITCHED-CAPACITOR IMPLEMENTATIONS We propose two different switched-capacitor topologies for an RC network that implements the discretized version of the diffusion equation, that is, scale-space filtering. Fig. 1 displays such two solutions along with a conventional RC approach for two nodes of a 1D network. In both cases the resistor joining the two capacitors is replaced with either, one or two capacitors and their corresponding switches, yielding the socalled parallel (Forward-Euler) implementation, named as 1C (Fig. 1.b) throughout this paper, and a variant of the bilinear approach, named hereafter as 2C (Fig. 1.c) switched capacitor networks [8]. Switches are controlled by two non-overlapping signals, φ1and φ2. A cycle nis complete after both signals are set to HI. The voltage at any cycle is the result of charge redistribution between two capacitors. Thus, at any cycle any voltage of interest is a settled voltage. This is true as long as φ1or φ2are long enough, or equivalently, when the resistance of the switch and the exchange capacitor CEare small enough. Next two subsections go through the two switched-capacitor network topologies studied in this paper for the particular case of a 1D network with two nodes. This analysis gives valuable information for a subsequent extension to 2D. A. 1C Network Analysis in 1D In a charge redistribution system with two capacitors the charge conservation principle is stated by Eq.(1). ∆Q1(t) = −∆Q2(t)⇒∆V1(t) = −C2 C1 ∆V2(t)(1) This means that the charge amount lost by one of the capacitors is gained by the other one. When both capacitors have the same value, the final voltage at both capacitors settles down to the average value of the initial voltages. The extra capacitor CEand switches φ1and φ2for the 1C network shown in Fig. 1.b isolate capacitors C1and C2from one another, allowing for a succession of settled voltages at C1 (C2) provided by the charge redistribution between C1(C2) CC 1 CC 2 V 1 V 2 (a) CC 1 CC 2 V 1 V 2 V CCC E E (b) CC 1 C C 2 V 1 V 2 V CCC E1 E1 CCC E2 V E2 (c) Φ1Φ2 Φ1Φ2 Φ2Φ1 Fig. 1. Different circuit realizations for an RC network (two nodes shown). and CE. The voltage evolution at C1and C2is an exponential decay (rising) towards an intermediate level between the two initial voltages at C1and C2with a time constant given by the network, which in the case of the 1C 1D network is expressed as Eq.(2). T1Cnetwork =1 CEf C1C2 C1+C2 (2) fis the frequency of the clock comprising the two nonoverlapping signals φ1and φ2. In focal-plane processing an adequate diffusion or smoothing process among pixels with any switched-capacitor network is only possible if the initial voltage at the exchange capacitors, CEin the case of Fig. 1.b, is set to either VC1(t0)or VC2(t0). Any other initial voltages at the exchange capacitors would lead to an erroneous result. If we use the first φ1cycle to initialize CE, the first complete charge redistribution between C1and C2would be ready during the second φ1cycle (φ1 2). At this time, the voltages at C1and C2are calculated with Eq. (3) and Eq. (4). V2(φ1 2) = V2(t0) + CE C2+CE [V1(t0)−V2(t0)] (3) V1(φ2 1) = V1(t0)−C2 C1 CE C2+CE [V1(t0)−V2(t0)] + ξ(4) It is apparent that Eq. (1) does not hold for capacitors C1 and C2. This is due to the charge stored in the exchange capacitor CE, causing a signal-dependent error ξgiven by Eq. (5). Although this can be minimized with CE<< C1, C2, it is a cumulative error throughout the diffusion cycles. This error should be added to those derived from an actual implementation on an IC. The nominal error given by Eq. (5) might make that a scale-space generated by the 1C switchedcapacitor network lead to an erroneous processing in a feature extractor like SIFT in image processing. ξ=C2CE C1(C2+CE)(C1+CE)[V1(t0)−V2(t0)] (5) B. 2C Network Analysis in 1D Similarly to 1C, the voltage evolution at C1and C2for a 2C switched-capacitor network follows an exponential decay (rising). With initial conditions VE1(t0) = V1(t0)and VE2(t0) = V2(t0), the voltages at the end of the first complete diffusion (φ1 2) are those listed in Eq. (6) and Eq. (7). 1.5 1.25 1.0 0.75 0.5 0.25 0.0 V(V) 300 600 Time (ns) 1C 750.2 757.6 757.5 RC RC RC&2C 2C 2C 1C 1C 750 749.8 V(mV) Fig. 2. Evolution of two nodes for the differnt RC networks of Fig (1). V1(φ2 1) = V1(t0)−CE2 C1+CE2 [V1(t0)−V2(t0)] (6) V2(φ1 2) = V2(t0) + CE1 C2+CE1 [V1(t0)−V2(t0)] (7) If C1=C2=C and CE1=CE2=CE, Eq. (8) holds. ∆V1=−CE C+CE [V1(t0)−V2(t0)] = −∆V2(8) The 2C network evolves with a time constant given by Eq. (9), (where C1=C2=C,CE1=CE2=CE), which is half the value of that of the 1C network (Eq. (2)) under the same conditions. T2Cnetwork =1 CEf C 4(9) The most important issue is that, differently from the 1C network, the 2C network provides a proper smoothing operator, suitable for scale-space generation. This is stated by Eq. (8) which meets the condition stated by Eq. (1). C. Simulations The differences between the 1C and the 2C approaches are illustrated with electrical simulations. Fig. 2 plots the voltages at C1and C2for a network of just two nodes. Switches and capacitors are implemented as ideal elements. Capacitor values have been adjusted to have the same network time constant in the 1C and the 2C solutions. We also show the response of a conventional RC network. As seen in the zoom-in at the upper right-hand side corner of Fig. 2, the settled voltages from the 1C approach differ from the expected value. The error level amounts to ∼7mV/1.5V, between 7 and 8 bits, for CE/C = 0.1. The designer should check the error level caused by the 1C network when providing scale-space in the corresponding algorithm and if this is still supported by the application. D. 2D Extension Here we analyze how the 2C switched-capacitor network performs in 2D, i.e. in focal-plane processing. Fig. 3 depicts the case of a 2D 4-connected network, where the hardware for a pixel is enclosed in a dashed-line. It is easy to show that the voltage at pixel ij after the first complete diffusion cycle is determined by Eq. (10). Φ1 Φ1Φ2 Φ2 CCC ij+1 CCC i+1j CCC i-1j CCC ij-1 CCC ij CCC E CCC E CCC E CCC E CCC E CCC E CCC E CCC E Φ1 Φ1Φ2 Φ2 Φ1 Φ1Φ2 Φ2Φ1 Φ1Φ2 Φ2 Fig. 3. 2C switched-capacitor implementation for a 2D 4-connected network. Vij(t) = Vij(t0) + [Vi−1j(t0) + Vi+1j(t0) + Vij−1(t0) +Vij+1(t0)−4Vij(t0)] CE C 1 + 4CE C(10) It is also easy to see that the result of a Gaussian kernel on an image takes the form of Eq. (11). Vij(t) = Vij(t0) + [Vi−1j(t0) + Vi+1j(t0) + Vij−1(t0) +Vij+1(t0)−4Vij(t0)] e− 1 2σ2 1 + 4e− 1 2σ2 (11) Eq. (12) is σfor the first cycle of diffusion, σ0. σ0=2ln C CE−1/2 (12) The relation σ-number of cycles, σ=σ(n), can be inferred from the approximation of the continuous-time by the discretetime case (Eq. (10)). Such an approach is obtained by dividing Eq. (10) by the clock period (TCLK) and making it infinitely short, resulting in the network time constant given by Eq. (13). τ=C+ 4CE CE TCLK (13) In [5] the relation σ=σ(τ)is given. In our case, this is formulated as Eq. (14), where the time has been expressed as a multiple of TCLK,t=n.TCLK, with nbeing an integer number. σ=r2t τ=r2nCE 4CE+C(14) σcan also be found empirically by comparison with Gaussian kernels of well-defined σlevels. The algorithm searches for the σlevel that produces the least RMSE. This approach can be done in two ways: 1) image comparisoncomparing the images from a convolution of Gaussian kernels on a given image with the evolution of the 2C network across different clock cycles and 2) kernels comparisoncomparing a 0 20 40 60 80 100 120 140 160 0,00E+000 5,00E-001 1,00E+000 1,50E+000 2,00E+000 2,50E+000 3,00E+000 3,50E+000 4,00E+000 4,50E+000 5,00E+000 Image Conv. C=200fF Kernel Conv. C=200fF σ=σ(n) C=200fF Image Conv. C=500fF Kernel Conv. C=500fF σ=σ(n) C=500fF Image Conv. C=800fF Kernel Conv. C=800fF σ=σ(n) C=800fF Cycles Sigma C=200fF C=500fF C=800fF 5.0 4.5 4.0 3.5 3.0 2.5 2.0 1.5 1.0 0.5 0.0 Sigma Cycles Fig. 4. σ=σ(n)plots for different C/CEratios. Gaussian kernel of a well-defined σ-level with the recursive nth convolution of the kernel of σ0, (Eq. (12)), derived from the 2C network. Fig. 4 plots the curves for both methods along with the σpredicted by Eq. (14) for three different C/CE ratios, with Cbeing set to 200 fF, 500 fF and 800 fF, and CE=20 fF. The first thing to note is that σhas a large range of variation. This is particularly true for low Cvalues. It must be said here that it is very hard to know in advance the most suited σlevels for a given application, although σ=σ(n)is needed irrespective of how it was achieved. It should also be said that Eq. (14) suits better the experimental methods for low C/CEratios. III. ASSESSMENT: SIFT-BASED OBJECT DETECTION This section assesses the validity of the switched capacitor networks described herein for object detection with the SIFT algorithm [7]. The left-hand side of Fig. 5 shows an example of a 240 x 320 image on which we run the SIFT algorithm. We derive the number of keypoints for a set of seven images from synthetic transformations, in this case, a combination of scale changes with rotations, (Fig. 5 displays an example of one of such rotations). Fig. 6 displays the results of the SIFT implementation available at [9]. The left-hand side figure contains the number of keypoints in every image. The horizontal blueline is the number of keypoints in the original image. The green line shows the number of keypoints on every transformed image. The target is object detection, so we are interested in the number of matched points between images, shown on the right-hand side of the figure. We depict both the outcome of the software implementation available at [9] and the results from generating the scale-spaces with 1C and 2C switchedcapacitor networks with 4-neighborhood for C=200 fF and CE= 20 fF. In this example, σwas obtained empirically from the σ=σ(n)graph of Fig. 4 with the method of comparing image convolutions described above. As expected, the SIFT outcome of the 2C solution is closer to the software-based implementation than that of the 1C network. Nevertheless, the 1C implementation still produces a high number of points, so that up to this point the 1C network should not be discarded as hardware solution, especially with high C/CEratios, although Fig. 5. An example of object detection with SIFT the algorithm. 2 4 6 8 500 600 700 800 900 1000 1100 Image Keypoints 2 3 4 5 6 7 180 190 200 210 220 230 240 250 260 270 280 Image Matches 2 4 6 8 700 800 900 1000 1100 1200 1300 Image Keypoints 2 3 4 5 6 7 150 200 250 300 Image Matches 2 4 6 8 600 700 800 900 1000 1100 1200 1300 Image Keypoints 2 3 4 5 6 7 150 200 250 300 350 Image Matches Software 2C 1C Keypoints 1300 1200 1100 1000 900 800 700 Keypoints 1300 1200 1100 1000 900 800 700 600 Keypoints 1100 1000 900 800 700 600 500 300 250 200 150 300 250 200 150 280 240 200 260 220 180 MatchesMatchesMatches 56 7 43 2 24 6 8 Image Image 56 7 43 2 24 6 8 Image Image 56 7 43 2 24 6 8 Image Image Fig. 6. Outcome of the SIFT algorithm for the image of Fig. 5 under several scale- and rotation-transformations for the software, and the 1C and 2C switched-capacitor networks. a detailed study of errors from an actual IC approach is still to be made. Finally, we also plot the recall vs. 1−precision curves. The precision is defined as p= #tp/(#tp + #fp), and the recall as r= #tp/(#tp + #fn), with #tp being the number of true positives, #fp the number of false positives and #fn the number of false negatives. #tp + #fp is the number of matches, shown as overlapping points in Fig. 5. The number of matches is calculated by comparing the descriptor vectors of two keypoints. If the difference of modules of such vectors is below (above) a certain threshold (th), the corresponding pair of keypoints is regarded as a match. A match becomes true positive when it also complies with the location condition; otherwise it is a false positive. The location condition can be checked easily in a synthetic (known) transformation as that of Fig. 5, as it is possible to track the keypoints from the original to the transformed image; thus it is also possible to calculate the number of false negatives. Fig. 7 displays the recall vs. 1−precision curves for Fig. 5, where the original image is rotated 45o. The graph is achieved by changing th, the threshold for the comparison of two descriptor vectors, for the software solution and the 1C and 2C networks as scale-space generators. It is seen as the 2C network follows more closely the software solution. Again, C= 200 fF and CE= 20 fF were used, and σwas obtained empirically from the graph of Fig. 4 with the method of comparing image convolutions described above. IV. OUTLOOK AND CONCLUSIONS This work has studied two different topologies of switchedcapacitor networks as RC grids for scale-space generation in focal-plane processing. The difference between the two 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.4 0.5 0.6 0.7 0.8 0.9 1 1−precision Recall Software 2C 1C Recall 1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.050.0 0.150.1 0.250.2 0.350.3 0.450.4 0.5 1-precision Software 2C 1C Fig. 7. Recall vs. 1-precision plot for the image of Fig. 5. topologies lies in the resistor realization; in the so-called 1C approach the resistor joining two nodes is implemented with one switched-capacitor, in the 2C solution, such a resistor is made with two switched-capacitors in parallel. We have seen that in 1D the 2C network is an adequate smoothing operator. On the contrary, the 1C mode generates a signal-dependent error. This error can be minimized with high ratios between the state capacitor (C) and the capacitor joining two nodes (R), which would lead to trade-offs on an IC. We have also assessed the performance of both solutions in focal-plane processing through object detection with a scale- and rotation-invariant feature extractor, the SIFT algorithm, that uses scale-space filtering. We have seen that the 2C solution clearly outperforms the 1C approach, giving an outcome closer to a softwarebased implementation. All these studies have been conducted under ideal conditions, in the near future; an analysis of errors derived from an actual implementation will be made with a view to a future IC. ACKNOWLEDGMENT This work was supported by Xunta de Galicia and MICINN (Spain) under the contracts 10PXI206037PR and TEC2009- 12686. The work of F. Pozas, R. Carmona and A. Rodr´ıguez- V´azquez is partially supported by ONR (USA) through grant N000141110312, and MICINN (Spain) through project TEC2009-11812, that is co-funded by the European Regional Development Fund. REFERENCES [1] A.P. Witkin, ”Scale space filtering”, Proceedings of International Joint Conference on Artificial Intelligence, Karlsruhe, 1983. [2] Jean Babaud et al., ”Uniqueness of the Gaussian kernel for scalespace filtering”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, no. 1, pp. 26-33, 1986. [3] J.J. Koenderink and A.J. van Doorn, ”The structure of images”, Biology Cybernetics, vol. 50, pp. 363-370, 1984. [4] Tony Lindeberg, ”Scale-space for discrete signals”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, no. 3, pp. 234-254, March 1990. [5] J. Fern´andez-Berni, R. Carmona-Gal´an, and Luis Carranza-Gonz´alez, ”FLIP-Q: A QCIF resolution focal-plane array for low-power image processing”, IEEE Journal of Solid-State Circuits, Vol. 46, no. 3, pp. 669-680, March 2011. [6] Christopher B. Umminger and Charles G. Sodini, ”Switched capacitor networks for focal plane image processing systems”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 2, no. 4, pp. 392-400, December 1992. [7] D. Lowe, ”Distinctive image features from scale-invariant keypoints”, IJCV 60 (2) (2004) 91-110. [8] Mark N. Seidel, ”Switched-capacitor networks for image processing: analysis, synthesis, response bounding, and implementation”, MIT, PhD, 1994. [9] http://www.vlfeat.org/∼vedaldi/code/sift.html.