Filters and Edges

A greyscale picture is a grid of numbers, one to a pixel, saying how much light arrived there. The scene this page works on is forty eight pixels on a side and is drawn rather than photographed, so that everything in it is known. It holds a square, a disc, a diagonal bar and three small crosses, all of them at the same brightness, on ground that is much darker. Two thousand three hundred and four numbers in all, of which three hundred and seventy five belong to a shape.

There is one more thing in it, and it is deliberate. The whole scene is a little brighter on the right than on the left, by 0.30 spread evenly across the forty eight columns, which is 0.00638 per column. That is a ramp, and it is what a scene looks like when the lamp is off to one side.

Without it the page could not tell the difference between a method that reads the objects and a method that reads the lighting, and the playground above lets you take the ramp away and put it back.

Here is the simplest thing anyone would try first. Every shape in the scene is bright and the ground between them is dark, so pick a number in between and call every pixel at or above it part of a shape. The darkest pixel belonging to a shape reads 0.8119 and the brightest pixel of ground reads 0.42, so any threshold at all between those two labels every one of the two thousand three hundred and four pixels correctly. Take 0.6. Nothing is wrong with the method and there is nothing to tune.

Now light the same scene differently. Turn the lamp up so that every pixel is multiplied by 1.6, and add a second lamp contributing a flat 0.15 everywhere. Nothing in the scene has moved, nothing has changed shape, and no object has come or gone. The average pixel has moved by 0.3765 and the largest single move is 0.7789, which is larger than the whole gap between the ground and the shapes was to begin with.

The threshold of 0.6 now keeps 1252 pixels where it should keep 375, and it disagrees with itself about 877 of them, which is 38.06 per cent of the picture. It is not that 0.6 was a bad choice; the window of thresholds that works has moved out from under it, from between 0.42 and 0.8119 to between 0.822 and 1.4491, and those two windows do not overlap anywhere. No single number can serve both pictures, and a number chosen on one photograph is a number chosen for that photograph’s lamp.

Look at the same two pictures a different way. Instead of asking how bright each pixel is, ask how different it is from the pixel beside it. Turning the lamp up multiplied every pixel by 1.6, so it multiplied every difference by 1.6 as well; the second lamp added a flat 0.15 to every pixel, so it added nothing at all to any difference, since the same constant sits on both sides of every subtraction.

Whatever that pattern of differences was, the same lamp change scales the whole of it by one common number and leaves it otherwise exactly where it was.

Measured on the scene, that is what happens. Every pixel where there is any change at all has its measured sharpness multiplied by a number between 1.5999999999999897 and 1.6000000000000139, which is 1.6 to as many places as float64 arithmetic can carry it. And the direction in which the brightness rises does not move at all, and over all 2304 pixels the largest turn is 1.07e-14 radians, and over the 450 pixels where the change is sharp enough for the angle to mean anything it is 8.9e-16, which is a rounding step rather than a movement.

Be precise about what survives, because the loose version of this claim is false. The size of the change did move, by a factor of 1.6, so a threshold on sharpness is no more portable across lamps than a threshold on brightness was. What survived is everything that does not depend on a common scale. The direction is exact. Any comparison between two sharpness readings is exact, since both were multiplied by the same number. That is why the descriptions built on this in the decades after Roberts count directions and take ratios rather than quoting sizes.

It is worth saying plainly what has been given up, because the answer is a lot. The threshold in step 2 needed one comparison per pixel and gave a verdict about all 2304 of them, saying of each one whether it belonged to a shape. Reading differences instead costs thirty four multiplications and additions per pixel, and what comes back is an answer about the 450 pixels that sit on a boundary, from which it takes a further step to work out which side of the boundary the object is on.

So where the lighting is genuinely fixed, the threshold is the better method, and this is not a close call. A document scanner lights the page itself and a microscope has a lamp under the stage; on pictures from either, thresholding the brightness costs about a thirtieth of the arithmetic and answers a stronger question. Roberts and Prewitt were not working on those. Roberts had photographs of blocks lit by whatever was in the room, and Prewitt had specimens stained by hand.

Everything on this page, and most of what the rest of this section does, is one operation asked different questions. Take a small grid of numbers, lay it over the picture so that its middle sits on some pixel, multiply each of its numbers by the pixel under it, add all of those up, and write the total down as the answer for that pixel. Then move along one pixel and do it again. That is a sweep, and the small grid is the weights.

Written out for a three wide, three tall grid whose weights are called w and a picture called p, the answer at row r and column c is the following.

answer(r, c) = ∑ over i in −1, 0, 1 and j in −1, 0, 1 of w(i, j) × p(r + i, c + j)

Nine multiplications and eight additions, and then the same nine multiplications and eight additions at the next pixel. What the sweep answers is decided entirely by what is written in the weights, and the rest of this page is about choosing them.

The forty eight by forty eight scene is too large to check by hand, so there is a small picture beside it, six pixels on a side, whose every row is the same six numbers.

0  0  0  1  1  1

It is dark on the left and bright on the right, so the one change of brightness in it sits between columns two and three, and every answer below can be checked on paper. Sweep it with the simplest weights on the page, half of the right neighbour minus half of the left one, written as a one by three grid.

−0.5   0   0.5

column 2: (−0.5) × 0 + 0 × 0 + 0.5 × 1 = 0.5
column 3: (−0.5) × 0 + 0 × 1 + 0.5 × 1 = 0.5
column 4: (−0.5) × 1 + 0 × 1 + 0.5 × 1 = 0

0   0   0.5   0.5   0   0

Notice what the answer says about where the change is. There is one boundary in this picture and two columns report it, at equal strength. That is not a fault in the weights and there is no cleverer choice that avoids it, since the change happens between two pixels, and any three wide window centred on either of them straddles it equally. An operator of this kind says where the brightness is changing to within a pixel and not to within less, which is a permanent property of asking the question this way.

The answer at a position is written down at the pixel the middle of the grid was sitting on. A grid with an odd number of columns has a middle column, and a grid with an even number does not, so the answer from a two wide grid belongs half a pixel to the side of anywhere it could be written. That half-pixel offset then travels through everything downstream: every later stage that compares this answer against the picture, or against another sweep’s answer, is quietly comparing things measured half a pixel apart.

This is not a rule about what is possible. Roberts’ own operator is two by two, and it works; its answers belong to the corners between pixels rather than to the pixels, and he knew that. Everything on this page is odd on both sides, so every answer sits at a pixel, and a grid with an even side is refused rather than quietly shifting the whole answer.

There is a fork here that looks like pedantry and is not. Having laid the weights over the picture, we can multiply them by the pixels in the order they are written, or we can turn the weights end over end first and then multiply. The first is called correlation and the second convolution. For a grid that reads the same forwards as backwards the two agree exactly and nobody ever notices the question.

For the weights on this page they do not agree, because these weights are negative on one side and positive on the other, and reversing them swaps which.

On the six by six picture, sweeping in the order written answers 0.5 at columns two and three, and sweeping the reversed weights answers −0.5 at exactly the same two columns. Nothing else about the sweep has changed. Every number has the same size and the opposite sign, which means that the two conventions disagree about which way the brightness is rising everywhere at once. The reversing switch on the widget above does this.

Put the middle of a three wide grid on column zero and its left column falls on column minus one, which does not exist. The same happens at the last column, and for a three by three grid at the top row and the bottom row as well, so every pixel around the outside of the picture is affected. On the six by six picture that is twenty of the thirty six positions, and on the forty eight by forty eight scene it is 188 of the 2304.

There is no right answer to what should be read there, and that is a genuine fact about the situation rather than an admission of laziness. The photograph is a window onto a scene that continued outside the frame, and nothing in the file records what was there. Whatever is read is invented, so the only question is which invention to make and what it costs.

Four answers are in common use, and the small picture is a good place to see them apart, because it has exactly one boundary and everything else it reports is invention. Its left side is dark and its right side is bright, which is what makes the four disagree.

The pair worth looking at twice is the first two, because on this picture they agree at the left border and both answer 0 there. That agreement is a property of the picture rather than of the rules, since this picture happens to be dark on its left, and the right border is where they part company. A scene tested only on the left of this picture would leave someone believing those two rules were the same rule.

The fourth rule deserves its own paragraph, because it is the only one that changes the shape of the answer, and shape is what everything downstream is built on. A three by three grid that refuses to hang off the picture answers two fewer rows and two fewer columns, so the forty eight by forty eight scene comes back as forty six by forty six and the six by six picture as four by four.

That is not a small inconvenience. Two sweeps of different grids now answer different sizes and cannot be laid on top of each other; the answer’s row three is the picture’s row four, so any position quoted from one has to be translated before it means anything in the other; and stacking several sweeps shrinks the picture each time, which is the reason the first three rules exist at all.

Part 1 asked how different a pixel is from the pixel beside it. The cheapest way to answer is to subtract the left neighbour from the right one and halve it, since the two are two pixels apart, which is the central difference and is the one by three grid already used above.

rate across at column c ≈ ( p(c + 1) − p(c − 1) ) / 2

It is exact on a straight ramp, where the brightness really does rise by the same amount each column, and it is hopeless on a photograph. Its answer at a pixel depends on exactly two other pixels, so a single sensor reading a little high moves it by half of however wrong that reading was, and it moves it whether or not there is a boundary anywhere near.

The repair every named operator makes is the same one. A real boundary is not one pixel long; it runs for some distance, so the rows just above and just below the pixel being answered for are looking at the same boundary and should have a say. Take the same left-minus-right difference on three neighbouring rows and average the three answers, and a stray reading in one of them now counts for a third of what it did while a real boundary, which is present in all three, counts for the same.

Written as a grid, that averaging is what turns the one by three grid into a three by three one. The difference is still taken across, left column negative and right column positive; what is new is the weighting down the middle, and that weighting is the entire difference between the three named operators.

Sobel middle-left entry = 2 × (−1) = −2

The grid that asks about the downward direction is this one turned on its side, which is not a coincidence and not worth writing out separately. It is the same estimate asked about the other axis, so writing the second by hand would only be an opportunity to write it wrong.

Put each of the four over a clean step, a picture whose left columns are all zero and whose right columns are all one, and the answer at the boundary is easy to predict without computing anything. Every positive weight sits over a one and contributes itself; every negative weight sits over a zero and contributes nothing. So the answer is the sum of the positive weights, and it is different for every operator.

So the same boundary, in the same picture, is reported as 0.5, 3, 4 or 16 depending on nothing but which grid was swept. None of them is normalised, and that has a practical consequence worth stating, which is that a threshold chosen for one of these is meaningless for another, and the factor between Scharr and the central difference is thirty two.

What every one of them does share is that its weights add to zero. That is what makes the answer zero on any flat region, whatever the brightness of that region, since the positive and negative weights then meet the same value and cancel. It is also why adding a constant to every pixel, which is what a second lamp did in Part 1, changes no answer anywhere.

Given that the four answer 0.5, 3, 4 and 16 at the same boundary, it would be reasonable to expect them to disagree about a good deal else. They do not. On the clean step every one of the four reports the brightness rising at exactly zero radians, which is due right, and every one reports the boundary itself as running at exactly a quarter circle to that. Not close to; exactly, because the vertical sweep answers exactly zero on a picture whose rows are identical, whichever grid does it.

On something harder they still nearly agree. The diagonal bar in the scene runs up and to the right, so its edges run at minus forty five degrees and the brightness across one of them rises at minus a hundred and thirty five. The four report −134.44, −134.16, −134.25 and −134.31 degrees, which is a spread of 0.2839 degrees between the furthest apart of them, while their sizes there are 0.4622, 1.8399, 2.7643 and 11.9904, a factor of 25.94 between the largest and the smallest.

If the four barely disagree, the question is what Scharr’s three and ten was for. The answer needs an edge the scene does not contain, because every boundary in it is drawn by arithmetic and is one pixel wide, and a step one pixel wide is a case where none of these estimates is any good.

So the test is a straight edge drawn at every angle from zero to eighty five degrees, and drawn twice, once as a hard one-pixel step and once spread across a couple of pixels, which is what a lens and a sensor do to the boundary of a real object.

On the spread edge the ordering is exactly the published one and the gaps are large. The worst angle any of them reports across the eighteen drawn angles is out by 4.13 degrees for the central difference, 3.10 for Prewitt, 1.16 for Sobel and 0.28 for Scharr, so Scharr’s weights are four times steadier than Sobel’s and nearly fifteen times steadier than the bare difference.

Every one of them is exact at zero and at forty five degrees, where the arrangement of pixels around the edge is symmetric, and worst somewhere between fifteen and twenty five degrees, and again at the mirror of that past forty five, since the curve is symmetric about the diagonal.

On the hard one-pixel step none of that holds. Every operator is out by more than nine degrees on average, Prewitt and Sobel come out identical at 9.2367, and Scharr is the worst of the three at 10.8913, with a worst case of 27.01 against Sobel’s 21.57. That is the honest report and it is not a defect in Scharr.

A one-pixel step has no well-defined rate of change to estimate, so the weights tuned to estimate one accurately have nothing to be accurate about, and the fact that the workbench scene is drawn that way is exactly why the diagonal bar showed so little between them.

The counting part is exact. A three by three grid does nine multiplications and eight additions at every pixel, and a gradient needs two sweeps, one across and one down, so it is thirty four operations per pixel and 78,336 for the whole forty eight by forty eight scene. The magnitude and the angle add a square root and an inverse tangent per pixel on top of that.

The timings underneath are a measurement of whichever machine answered the request and move a little between runs, which is why they are read live rather than written into this page. The figure worth taking from them is the shape rather than any one number, since the cost per pixel at the scene’s size is roughly double what it is on a picture a thousand pixels on a side, because on a small picture most of the time goes on arranging the sweep rather than on doing it.

It also scales as the number of pixels and not worse, so a picture with four times as many pixels costs about four times as much, which is what made these operators usable on the hardware they were invented on.

Sweeping once answers how fast the brightness rises to the right, and that alone is not an edge. A boundary running exactly up and down is invisible to it in the vertical direction and a boundary running exactly flat is invisible to it in the horizontal one, which is why the vertical sweep of the six by six picture answers zero everywhere while the horizontal sweep answers 4 at two columns.

So the same picture is swept twice, with the same grid turned on its side for the second, and the two answers are kept together.

Together they are a pair of numbers at every pixel, and a pair of numbers is an arrow. Handing back two separate pictures and leaving them to be paired up later is how the two get separated and one of them gets compared against the wrong half of something else, so they travel as one thing.

The length of that arrow says how sharply the brightness is changing at that pixel, taking both directions into account at once. It comes from the two rates the way the length of any arrow comes from its two sides.

sharpness = √( across² + down² )

Being a length, it is never negative, and it is zero exactly where the brightness is flat in both directions at once. On the scene the sharpest reading anywhere is 2.9974, and it sits on the disc’s rim rather than on a side of the square, since a boundary crossed at an angle gives both sweeps something to answer and the two lengths add through the square root. The square’s upright sides read 2.6911 and its flat ones 2.6405.

The flat regions still contain the brightness ramp introduced in step 1. The filter compares positions two columns from its centre, and its positive weights add to four. That predicts the small nonzero response.

ramp response ≈ 2 × 0.00638 × 4 ≈ 0.0511

Remove the ramp in the playground and those same 1666 interior pixels return zero. The filter was responding to a small brightness change, even where the larger shapes looked flat.

The angle of the arrow says which way the brightness is rising, and it comes from the two rates the way any angle does.

direction = arctan2( down, across )

Measured from pointing right and turning towards pointing down, it lies between minus half a turn and half a turn. Zero means the brightness rises to the right, a quarter circle means it rises downward, and a whole half turn either way means it rises to the left.

There is one honest gap in that. Where the picture is flat, both rates are zero, and an arrow of zero length has no angle at all; a number still comes back, and the number is zero, and it is a convention rather than a measurement. That is why every drawing on this page of directions draws a stroke only where the sharpness is above a share of the largest, and why any later stage that counts directions has to weight each one by its sharpness rather than counting them equally.

This is the thing most often got the wrong way round, so it is worth being blunt. The arrow points the way the brightness increases. Standing on a boundary, the way the brightness increases is across it, from the dark side to the bright side. The boundary itself runs at right angles to that.

Take a boundary running straight up and down with the bright side on the right. The brightness does not change at all as you walk up or down it, and changes as fast as it ever does as you step sideways across it, so the arrow points due right, at zero radians, while the boundary runs vertically, at a quarter circle. Those two numbers are the same fact reported two ways and are a quarter turn apart, always.

The widget draws both, and the square is the clearest place to see it. Switched to the way the brightness rises, the strokes on the square’s left and right sides lie horizontally, cutting across sides that are vertical. Switched to the way the edge runs, the same strokes lie along those sides. On the disc, whose boundary points in every direction in turn, the first setting gives a starburst pointing inward from the rim, since the disc is the bright thing, and the second gives a set of strokes lying around the rim like a wheel.

Everything on this page has been calling the answer a rate of change, and it is worth saying what that phrase can and cannot mean here. A rate of change is defined for a quantity known at every point of a continuum. Brightness is known at whole pixels and nowhere between them, so there is no rate of change to compute; there is only an estimate of what the rate would have been had the scene been sampled finely enough for the question to have an answer.

That is not a quibble, because it says exactly when the estimate is good. It is good when the scene changes slowly compared with the spacing of the pixels, so that three neighbouring readings really do lie near one smooth curve. It has nothing to say when the scene changes faster than that, and a boundary between two flat regions one pixel apart is the extreme case.

Step 16 measured what that does. On an edge spread over a couple of pixels the four operators report angles out by between 0.28 and 4.13 degrees, and on a one-pixel step the same four are out by between 21.57 and 40.00.

The obvious last step is to decide, at every pixel, whether it is on an edge, by keeping the pixels whose sharpness is above some number. On the scene as it is drawn that works perfectly, and it is worth seeing why before seeing why it does not generally. Drawn by arithmetic the scene has no noise, so flat ground never answers above 0.0511 and the faintest pixel on a real boundary answers 0.898, more than seventeen times as much. Every threshold between those two labels all 2304 pixels correctly.

Now add the thing a photograph has and a drawing does not. With a normal spread of 0.08 added to every pixel, which is twelve per cent of the contrast between the shapes and the ground, flat ground answers as high as 1.0157. The faintest real boundary is still at 0.898. Those two ranges now overlap, and once they overlap there is no number that separates them, because the populations are not separated in the quantity being thresholded.

The sweep says what that costs at each end. At 0.4 nothing real is lost and 693 of the 1854 flat pixels survive as false edges. At 1.1 no flat pixel survives at all and 63 pixels on a real boundary have gone. In between, both happen at once, and the best threshold in the whole sweep is 0.9, and it keeps 5 flat pixels and loses 35 real ones, of which 33 come from the 98 obliquely crossed pixels on the disc’s rim and along the diagonal bar, where the change is genuinely gentler because a three wide window straddles it rather than meeting it square.

So the faint half of a real boundary and the loud half of the noise occupy the same range of sharpness, and no single number keeps one and drops the other. The escape is to stop asking for one number, which is what the work after 1980 did, and the two usual moves are to use two thresholds and keep a weak pixel only when it joins a strong one, and to smooth first at a chosen scale so that the noise loses more than the boundary does.

Both are still choices with a cost; neither turns the overlap into a separation.

The last limit is not about arithmetic at all, and it is the one that stops this being a solved problem. An edge operator answers a question about brightness. The question anyone actually wants answered is about objects, and those two questions have different answers in both directions.

Brightness changes where no object ends. The shadow a hand casts on a table has a boundary as sharp as the hand does, and so does the printed edge of a pattern on a shirt, and so does the line where sunlight stops on a wall; a gradient operator reports all of them at full strength, because at each of them the brightness really is changing sharply, which is all it was ever asked.

And objects end where the brightness does not change. A grey cat on a grey sofa has a real boundary along which the brightness is the same on both sides, and the operator answers close to nothing there, correctly and uselessly.

There is nothing in the estimate that could distinguish these, because the distinction is not present in the numbers being read. It needs something the operator does not have, which is either a colour or a texture that does differ across the boundary, or knowledge of what shape the thing is, or a second view of the same scene from elsewhere.

That is roughly the history of the subject after this page, since everything else in this section is a way of building something more informative on top of these answers, and none of it repairs the gap between where the brightness changes and where the object is.