A Simplified And Fast Version Of The Huockel Operator For Finding Optimal Edges in Pictures

Introduction

Hueckel's operator for edge detection in pictures is one of the best tools which have been invented for this kind of tasks. In very noisy pictures its high effective­ ne~~ can be comparable only with the glo­ bal optimization procedures e. g. by Mon­ tanari and Martelli (8), (9), but without their drawbacks in processing time and me­ mory requirement. The Hueckel operator processes a picture block containing 52 points on PDP-10 in 10 msec, e. g. if it scanned for example a 256 by 256 point picture so that the blocks overlap by one thirds of each other, the processing time would be about 40 seconds. Of course, by means of sophisticated edge-following me­ thods this time can be reduced signifi­ cantly, thus the applicability of this operator is not beyond the possibilities to process a real picture. These 10 msec are, however, rather large to look for some modifications based on its basic idea to speed up the operation, even by possible simplifications which preserve the excellent properties of the original one.

In this paper we present a method aiming at this by reinterpreting the principle of the Hueckel operator and giving a modification of it based on our interpretation.

Hueckel's method in its original form

The original interpretation of the Hueckel operator can be summarized as follows:

• a/ We seek for a function S on a D area in the input picture, which function has a constant b value on one side and

and others ( 7), (10), (11), (12) l~avo:o worked out several versions of this method and investigated them empirically. For example, perhaps the simplest templates for two-dimensional pictures are those of Shirai (17) sketched in Fig. 2. The first of them shows a maximum if it lies exactly on a vertical and the second on a horizontal edge. For making the method less noise-sensitive, one can take into account larger areas, e. g. 5x5 or 8x8

etc.

Since Hubel and Wiesel (4) pointed out that the visual information processing system in mammals operates in a way very close to this method, at least for the local edge and spot extraction on the re­ tina, template matching has a certain theoretical support. Moreover, just this physiological achievement led Deutsch to develop his template called SLEN /Short Line Extractor Neuron (1)/ used for nume­ rical character recognition. For real-time processing of real pictures, however, these methods do not produce so effective results as other ones, being though ad hoc without any theoretical suggestions. In the case of edge detection, if the shape and orien­ tation of the template are fixed, the pro­ bability of good matching is little be­ cause the output value of the convolution decreases very sharply either because of the increase of the angle between the template edge and the real one or the curvature difference of them (2). From this two main shortcomings follow. First, the system would not find certain, un­ luckily oriented edges even from the line­ shaped ones. To surmount this difficulty, Holdermann and Kazmierczak (3) have pre­ sented a method with parallel application of several templates to the same picture area around a point. They took care also of noise elimination by averaging, and their output picture after this multiple template operation looked quite good in quality, but even their method could not avoid the following - second - difficulty: in the case of fixed templates the large majority of the required computer ope­ rations falls into the category of un­ successful trials and the whole processing time may be too long, especially if the picture is not "angular" enough. The main reason of these shortcomings is obviously the rigidity of the templates applied. In contrast to e. g. Holdermann and Kazmierczak's eight templates, we would need only one of them~ but that would be the best matching one. 1he question is how to find just this "optimal template", i.e. how to solve the opposite problem to that of template matching: fitting the template to a fixed picture area and not the picture area to a/some fixed template/s/. Let D be this area of the picture, t the set of all pOssible templates, and F/x,y/ the input two-dimensional grey-·level function, then we seek T/x,y/et so that

ln the next section we will p~i~~ out that Hueckel's operator completes just this task.

The Hueckel operator as a kind of template matching method

We will first need to recall some of Hueckel's notations. Let the grey values of the input picture on a circle-shaped area D be F/x,y/, the sought two-dimen­ sional step function be

Let the base functions chosen in the Hilbert space of all the functions on D be H 0 /x,y/ ··· H 7 /x,y/.

With these notations the functional equation to be solved is:

The Fourier coefficients for F and S are:

X/c,s,r,b,d/ =

Huekcel'i operator solves this functional equation . Now we will prove that /5/ can be rewritten in the form of /1/ in the previous section. For this we need a lemma:

Lemma: Let

that

where £ sions. is a vector of arbitrary dimen-

xHere we neglect Hueckel's heuristic weighting coefficients as they have no

relevance to the problem considered.

then if for some values of E

min.

values fof E

V/EI = max.

The proof is given in Appendix A. According to this lemma, /5/ can be re­ written as

Substituting fi from /3/:

= max.

With some trivial transscriptions:

>-' /c,s,r,b,d/

The expression

T/x,y,c,s,r,b,d/

is a template by its role in /6/, as the form of /6/ is identical with that of /1/. T/x,y,c,s,r,b,d/ is the optimal template to the F/x,y/ input function constructed as a linear combination from the set of

original templates H 0 .·· H 7 .

The possibility of simplifying the Hueckel operator

In Hueckel's interpretation the basic aim, i. e. finding an edge, is reached by fittinga two-dimensional function to the input grey-level function in a picture area. Consequently, a relatively large set of both the base functions and edge para­ meters is required, because it is obvious that no satisfying degree of fitting could be approached by a remarkably simpler base field and parameter vector /containing e.g. two or three functions or values res­ pectively/. If we are, however, considering the method as a template matching one, the fitting problem becomes unimportant and its requirements cannot be taken into account.

First, we may choose a two-dimensional parameter vector /c,s/ instead of /c,s,r,b,d/ as the grey values of the two sides of the step function are irrelevant, and the exact location of the edge inside the D area can be computed in a very simple way once we have determined the edge di­ rection. The direction is characterized only by c and s, as in the equation of the

then for the same

c and s are just the direction cosines to

the +x axis.

Second, if we need only the edge di­ rection, we may work with only two of Hueckel's original templates H 0 ··· H 7 , because it seems well even intuitively /we will prove it later, of course/ that by the linear combination of H 2 and H 3 the direction of the optimal template can be determined. By the direction of a template we mean the direction of the a-crossing

of a H 2 or H 3 type function.

Third, if we do not take care of the mathematical conditions of the Fourier function fitting in a Hilbert space - as these conditions determined the choosing of H 8 ... H 7 in Hueckel's work /Chapter 2/­ the nly criterion in choosing our two templates can be the speed of computation which is very crucial in real applications. Thus we can use both constant-valued template functions and a more convenient shape for the D picture area. The con­ venience of this shape means also the speed of computing c and s or any other quantities characterizing the direction.

The method we have got to by the above considerations will be set forth in the following section. lt is essentially simpler and faster than that of Hueckel, but as will be ssen from the examples pre­ sented later, it preserves all of its ad­ vantages in comparison to other methods. The computation consists of two steps. The first one is· the determination of the edge direction by constructing an optimal template from two beginner ones by linear combination. Just like in Hueckel's method, a vast part of the extremization problem is solved analytically and the number of the required arithmetical operations is small. The second step is the determination of the exact location of the edge in D by its two border points. It is solved by some simple logical rules and point reflections.

Description of our edge detection operator

The core of the method is based upon the following elementary theorem:

Theorem: Let D denote the unit square, f 1 be the function being +1 above the sub­ diagonal of D, and -1 below it, f 2 be the

function being +l above the principia! diagonal of D and -1 below it,/see Fig. 3, a, b/ and let f be a function being b+d above a line e in D, and b below this line. /See Fig. 3, cord/. Then if a denotes the angle between the subdiagonal of D and e, the following equation will hold:

The proof of the theorem will be pre­ sented in Appendix B. The odd thing about the theorem is that the expression at the left side does not depend either on b and d or on the real place of the line but its angle.

By this theorem we are given a very pleasant tool to determine an edge in a little part of the picture. The two in­ tegrals can be very easy and fast computed, and because of the integrations this method is of very low sensitivity for noises. /Later we shall elaborate further considerations about this./

In our work we have chosen D to be a square consisting of 8x8 picture points. Having supposed that there was a straight edge in the picture at D, by using the above mentioned theorem we could determine its place, i. e. its two endpoints in D.

To begin with we transform the value of the tangent to a more treatable form. We determine from the value of tg a how many picture points are the difference between the right and the left end of a line in D, the angle of which with the subdiagon~l is ~. /It is enough to deal with lines lying in the quarter of the plane shown on Fig. 4, because if the edge lies in the other quarter, then by counting with ltg al, after the whole process a reflection of the edge to the principia! diagonal of D - i. e. its end­ points- gives the real edge./

Everything stated until now is valid both for pictures with two and for those of more grey levels. Now we shall show the determining process of the real edge at first only for pictures with 2 grey levels and after that we shall show how to ge­ neralize that idea for pictures with more grey levels.

In the case with 2 grey levels the sum of the l's in D divided by 8 shows, roughly spoken, up to what a height D is filled with ones. This means e. g. that if the edge were horizontal, then the edge could be either the horizontal line at that height, or that reflected to the centre of D /for D could be filled with ones from its bottom or from its top/. But even if the edge were not horizontal, we could know what was the difference between its left and right endpoints' height, so we could determine the edge. If both the left and the right endpoints of this edge were inside of D then we had only to de­ termine whether this was the real edge or we had still to reflect it to the centre of D.

If one of the endpoints of the above obtained edge were not in D, it could be only by 1, 2, or 3 points sticking out of D, because now already the edge we are working with lies in the plane quarter shown on Fig. 4. But in these cases it is already very easy to determine the real edge.

For pictures with more grey levels we could use the same method if we knew b and d, because then the number of the points with greater grey level could be approxi­ mated by the following expression:

where S denotes I fdxdy, I 1. e. the sum of

the grey levels of all points of D. But now by using the notations of Fig. 5, let T 1 , T 2 , T 3 and T 4 denote the sum of the grey levels of f /i.e. of the picture/ in these 4 quarters of D, and min{T.} max{T.} l. l. --: 1 -, 6 ,........::;;.__ resp. 16 approximates well b

resp. b+d. After this the above described method of finding the edge can be followed in the case with more grey levels as well.

By this method we have already found either the real edge in f or the same reflected to the centre of D. /See Fig.6/ To determine which of them is the real edge, the following table shows a method provided that up to this time we have supposed in the steps that D was filled by the ones /resp. by b+d's/ from its top. The case A means that we have found the real edge while B means that still we have to reflect our edge to the centre of D.

This method was implemented by a program on the assembly language of a 16 bit microprogrammed minicomputer of 550 program instructions without any cycles. If there is an edge in D it needs 250-400 machine operations, i. e. about 500-800 ~sees. No floating point arithmetics are needed.

About the reliability of the method rough under-estimations show that supposing a noise with a binomial distribution with a mean value of 5 error points in a 8x8 square, the probability of the difference between the edge determined by this method and the real edge being not greater than 1 point anywhere, is over 95 %.

Finally we present three examples for the working of the method. Example 1 is the example shown in Hueckel's article ( 5)

which we have completed at the corners. The dotted line shows the edge found by Hueckel, the continuous one is the edge found by our method.

Appendix A

Proof of the lemma used on page 5:

Appendix B

The proof of the theorem: Let's use the notations of Fig. 8. We shall deal only with the case if 45°~a<90°, because all other cases can be handled symmetrically. First we show that in the case of the line on Fig. 8, the statement of the theorem is valid. Here the quotient of the two integrals is:

Considering the sides of D to be one, we have

Consequently, if e' lay above the line examined just now, then because of the si­ milarity of all relevant triangles /see Fig. 9/ the statement would be true for e' as well:

Now if e' lay between e and the centre of D, then using the notations of Fig. 10 on account of the similarity of the triangles T 1 and T 2 uT 3 ux here and T 1 and T 2 on Fig. 10 we have

Subtracting 1 from both side, taking their reciprocal and adding 1 again we have

· This means we have to show only that

And this is larities of FG CD FB = CB; so true for, because of the simi­ the triangles FJB and CAB, it is enough to show thaf ~~ =

Now for AD is the bisector of the angle CAE, we have:

triangles CAB and EHB

and for the triangle AEH is isoceles AE=EH, and the theorem is proved in this case,too. If e were below the centre of D, the same proof could be presented for negative d. /We have nowhere made use of the positive property of D./ So the whole theorem is proved.