Bugs in my head
Still not production; still a work-in-progress. “Progress,” this last week, has mainly entailed throwing out various pre- and post- filter conditioners: a reductionist effort with an aim of seeing what can be gotten away with — a search to find what is really essential in this task of picking out Euro coinage from among the fungi or bacteria (I can’t tell the difference). Should you care to, diff -u
the following with the chough.gmic
listing of Post 42.
chough.gmic - 8fb568ec 'pixlpost529'
#@cli chough : radius>0,bkgrndnoiseelim>0,_precision,_verbose
#@cli : Select: image(s) to be scanned for circular-like
#@cli : artifacts of pixel 'radius'. Execute Conic
#@cli : Hough. Locate the noisy clusters and compute median
#@cli : points of same. Replace selected with a 1xN vector
#@cli : array list of N discovered median points. 2D
#@cli : coordinates + given radius parameter for downstream
#@cli : plotters to draw circular masks centered on the median
#@cli : points. As 'bkgrndnoiseelim' increases, single-pixel
#@cli : noise decreases, but detected edges may dissolve as
#@cli : well. Increasing 'precision' sizes an internal
#@cli : 'parameter space' image. Argument is a multiplier that
#@cli : increases the width and height of the selected input
#@cli : image. Factors of 2-4 is less susceptible noise, but
#@cli : consumes more memory.
#@cli :
chough : check "${1}>0 && ${2=15}>0 && ${3=2}>=1.0 && isbool(${4=0})"
rad,bne,pr,verb=${1-4}
-foreach {
nm={-1,n}
-name. inputimage
ow={w#$inputimage}
oh={h#$inputimage}
# Sprite radius
sd={$pr*$rad+1}
-edges[inputimage] $bne%
-oneminus[inputimage]
# Upcoming point cloud has substantial
# redundancy. Trimming half has little
# effect on solution
-resize[inputimage] 50%,50%,1,1,1
-resize[inputimage] 200%,200%,1,1,4
-pointcloud. 3
-if $verb
-display ,
-fi
# Draw circular sprites centered on suspected
# rims of suspected circular artifacts. Also
# drawing on found noise. Point cloud is non-
# background-colored pixels. Could be anything,
# maybe even five-euro coinage.
-if w#$inputimage
-channels[inputimage] 0,1
-fill[inputimage] "$pr*I"
ox,oy={I(#$inputimage,0,0)}
# Shift sprite image by way of deltas
# from point-to-point. Get those deltas
# by subtracting the pointcloud from a
# one-plot-point-shifted copy of itself,
# i.e., foreach p(n)-p(n-1)
+shift[inputimage] -1,0,0,0,2,0
-reverse[-2,-1]
-sub[-2,-1]
-name. diffs
-input {$ow*$pr},{$oh*$pr},1,1
-name. paramspace
-input [-1]
-name. sprite
# Draw just one circle, then rubber-
# stamp it with shift/add commands.
stat={ellipse(#$sprite,{w/2},{h/2},-$sd,-$sd,0,1,0xffffffff,1.0);1.0}
-shift[sprite] {$ox-w/2},{$oy-h/2},0,0,2,0
-if $verb
-display ,
-fi
-repeat {w#$diffs}
-add[paramspace] [sprite]
-shift[sprite] {I(#$diffs,$>,0)},0,0,2,0
-done
-keep[paramspace]
-if $verb
-display ,
-fi
-fill[paramspace] 'i>=0.97*iM?1:0'
-if im==iM
-echo[^-1] "No\ detected\ coins\ @\ "$rad"\ radius."
-else
# Maybe coins? Got clusters of crossing conics...
# Find mean points of the noisy patches.
-medianofclusters[paramspace] 32,$verb
+fill[paramspace] "V=I(x,y);V=V/$pr;V[2]=$rad;V"
-keep.
-name. $nm
-fi
-else # Seems that w#$inputimage == 0 ...
echo[^-1] $nm"\ seems to have no features. No points found."
-fi
}
#@cli medianofclusters: errorball>0,_verbose(bool)=False
#@cli : Find clusters in pointclouds; compute their
#@cli : medians. Package these in a column vector of
#@cli : centers. errorball: defines cluster radius. Points
#@cli : farther apart than this distance are not in the
#@cli : same cluster. verbose: When true, emits debug
#@cli : data to G'MIC shell log.
#@cli :
medianofclusters: -skip ${1=32},${2=0}
ed={$1^2}
verb=$2
-foreach {
-pointcloud. 3
-channels. 0,2
-if w>1
# Consolidate clusters: find
# their average centers.
nm={-1,n}
-name. cloud
-input 0
-name. cstack
-shift[cloud] 0,0,0,1,2
-permute[cloud] cxzy
-eval ">P=crop(#$cloud);
psz=size(P)/3;
erb=$ed;
vrb=$verb;
cc=0;
ACC=vector2(0);
if(vrb,print(P));
for(
# --------------- INIT
t=1;
k=1;
Q=P[1,2];
ACC+=Q;
if(vrb, print(ACC));
chk=P[0];
P[0]=t;
cc=1,
# --------------- CONDITION
chk==0,
# --------------- PROCEDURE
if(
chk==0,
t=t+1;
k=1;
P[0]=t;
cc=1;
Q=P[1,2];
ACC=Q
),
# --------------- BODY
do(
if(vrb,
print(Q);
print(P[3*k,3])
);
if(
P[3*k]==0,
err = mse(Q,P[3*k+1,2]);
if(vrb, print(err,erb));
if(
err<erb,
P[3*k]=t;
cc+=1;
ACC+=P[3*k+1,2];
if(vrb,
print(P[3*k,3]);
print(ACC);
print(cc)
)
),
_(DO BREAK: Remaining points in P already clustered);
break()
);
k=k+1;
if(vrb, print(k)),
k<psz
); _(Do clustering);
da_push(#$cstack,[ACC/cc,t]);
_(P sort: Shuffle unclustered points to front);
P=sort(P,1,psz,3);
chk=P[0];
if(vrb,
print(t);
print(chk);
print(P)
)
# --------------- END FOR FINDING CLUSTER CENTERS
); _(for: Find median points of clusters);
if(vrb, print(P));
da_freeze(#$cstack)
" # eval math expression argument
-remove[cloud]
-name. $nm
-else
-echo[^-1] "Given image seems to have no circular-like artifacts. Nothing done."
-fi
} # foreach image in command's selection
#@cli chdemo: radius>0,_rblur>0,thres,_precision,_verbose,_sensitivity>0,_precision,_verbose
#@cli : Toy framework
#@cli :
chdemo : check "${1}>0 && ${2=2}>0 && ${3=15}>0 && ${4=50}>0 && ${5=60}>0 && ${6=25%} && isbool(${7=0})"
rad,hc,bne,rblur,thres,pr,verb=${1-7}
-foreach {
nm={-1,n}
ow={w#-1}
oh={h#-1}
sc={s=['$pr'];s[size(s)-1]==_'%'?(s2v(s))/100.0:s2v(s)}
-if $sc>1
-error "Downsampling "$pr" should be a percentage < 100% or decimal fraction < 1.0"
-fi
+resize. {$sc*w},{$sc*h},{d},{s},5
-median. $rblur,$thres
-if $verb -v + -fi
+chough. {$rad*$sc},$bne,1,$verb
-fill.. 0
-resize.. {w#-2/$sc},{h#-2/$sc},{d#-2},1
-resize... {w#-3/$sc},{h#-3/$sc},{d#-3},{s#-3}
-repeat {h#-1}
cx,cy,r={I(#-1,0,$>)/$sc}
-ellipse.. $cx,$cy,{$r+$hc},{$r+$hc},0,1,255
-done
-inpaint_matchpatch... [-2]
-keep...
}
What follows goes under the rubric of “ancedotal asides”: of no use toward reaching the eventual form that this filter should take. If you want, leave the theatre now and get out to the parking lot before the main onrush.
As you may have gathered, these various Hough tools rely upon some voting scheme, that if a feature is present in an image, such as a euro coin with an 80 pixel radius, some scheme will upvote a particular pixel in a “parameter space” image — this scheme will upvote it many, many times, and that some aspects of this upvoted pixel will tell us something about the feature. In the present case, the pixel’s location in parameter space exactly coincides with the euro coin’s location in the original image. That is because we have so declared the parameter space to be in a one-to-one, pixel-to-pixel mapping with the original image, and that our design of the voting scheme is to adhere to this one-to-one mapping. So parameter space voting is important (“Vote early; vote often.” as we say in Brooklyn.); we exploit the accumulation of votes in parameter space to find euros in the original space.
The voting scheme in play here consists of:
- a circle drawn in an off-to-one side “rubber stamp” image — let us call it a “sprite”. This sprite comes to us by way of the
ellipse()
math function. Now, having drawn it, let us put the sprite to one side and come back to it later. - We take all pixels from the original image that seem to be sitting on edges — harnessing a heavily edge-detected version of the original — and make a pointcloud from it: its first argument chooses one behavior from a possible four. We pick option ‘3’ harvest a pointcloud from an image; the other options entail plotting a point cloud onto an image in various ways.
- This brings us to the inner loop. Trusting that the elements in the pointcloud collection all locate pixels sitting on edges, we take each point, one by one, and hand that coordinate pair over to the image stamper.
- The image stamper’s lot in life is to regard the given point as the center of the sprite. So it takes the sprite, positions it in parameter space over the center, and stamps! All pixels displaced from the center point by the radius of the sprite receive an up-vote, this in the form of a slight gain in its luminosity value — an up-vote that is a “simple linear addition” of a fractional value to that which has already accumulated in the pixel from previous stampings — or so I thought.
- This, ladies and gentlemen, constitutes the genesis of the bug in my head: simple linear addition. Though bugs in the head may manifest themselves as defective code, such is generally invisible to the coder possessed by bugs in the head. That is how defective code generally passes the coder’s visual inspection. S/He sees the code, but reads something else, like “simple linear addition.” But the code doesn’t actually do “simple linear addition.”
Bugs in the head to one side, the alignment of stars that this voting scheme seeks take the form of those edge point locations from the point cloud that happen to form a parameter space circle exactly the same radius as that of the circular sprite. For as the sprite stamps — using such magical edge points as centers, there is one point in parameter space that gets up-voted with every stamp. That is because it is center point of the circle the magical edge points form, a circle that matches the radius of the sprite circle. The circumference of the sprite circle crosses the center point of the parameter space circle because their radii match. If it were otherwise then the sprite circumference would miss the center point stamp after stamp.
Here is the image stamper as originally (and defectively) conceived, from the Post 42 version:
# Faster to draw just one circle, then rubber-
# stamp it with image command.
stat={ellipse(#$sprite,$rad*$pr,$rad*$pr,-$sd,-$sd,0,1,0xffffffff,255)}
-repeat {w#$inputimage}
cx,cy={I(#$inputimage,$>,0)}
-image[paramspace] [sprite],{$cx-$rad*$pr},{$cy-$rad*$pr},0,0,0.002
-done
In truth, I hardly gave this code a thought (Ay, and therein lies the rub!). My (quick) read on the behavior of the “image stamper” -image was this:
a0 = 0;
ai = ai–1 + ts
where t scales the contribution from the sprite to a very small value, here 0.002, and, after five hundred up-votes, the accumulated pixel value, a500 would be 1; and after five thousand up-votes, the accumulated pixel value would be 10, and after fifty thousand up-votes the accumulated pixel value would be 100… you get the gist of my thinking. The pixel where the stars align would accumulate up-votes to the order of 10 to a 100, the rest would (likely) accumulate values far below unity, and many, if not most, would accumulate no value whatsoever.
Voting was in the bag. I moved on.
And then voting wasn’t in the bag. I stopped, winking and blinking, a deer in headlights.
Sometime after finishing Post 42, I was finding in testing that the values of hotspots — pixels with their stars in alignment — were generally not at expected accumulated up-vote values. However, with remarkable consistency, they all rather fell short at 63% of their expected value. That is, after fifty thousand up-votes, the accumulated hotspot pixel values would be 60, 62, never much past 63 — and nowhere near 100. Broadly, the behavior was this:
My first thought was to do nothing — nothing is easy — as hot spot detection was working well enough. I mean, things were sort of working. That sort of thinking got me through the night, but the bright dawning of a crisp new spring day came with the realization that — dammit! — we should do things right around here. So I took the time to look at -image
— really look at -image
— and ask myself if I actually understood what its final argument, opacity,
does. To spare you the details, eventually Light Dawned Over Marblehead: that the final argument to -image
is the mixing ratio for a linear interpolation between the sprite and the parameter space image. Since it is lerping that we are doing, the actual behavior of image stamping — and up-voting — is this:
a0 = 0;
ai = ai–1 + t(s–ai–1)
which is not “simple linear addition,” but successive linear interpolations (“lerps”) at the fixed mixing ratio of t=0.002. The result of one lerp folds into the next. So, letting i run off to infinity finds a∞ ⇒ 1–(1/e) ≈ 0.63212, this for a fully opaque sprite value of s = 1. It was at this juncture that I recognized that I had bugs in my head. In effect, accumulating vote values would be progressively shaved as up-votes for successful pixels increased. -image
could not composite in any fashion other than through linear interpolation. It seemed that I had to abandon -image,
a pity, as it was in every other respect a nice stamper, and, being a built-in, was fast.
After casting around for a bit, feeling a bit sheepish, feeling a bit dumb, I settled on using shift as the voting scheme’s sprite positioning mechanism. Also a built-in, perhaps the actual act of voting would not be very much more expensive. -shift
operates with deltas, so the point-cloud had to be shifted, then differenced with itself, keeping one unsubtracted value for initializing the sprite’s first position. Put in other terms, I took to putting the sprite on one image, positioning with one absolute MOVETO
then shifting with the remaining series of relative MOVETO
s. The new voting scheme looks like this:
…
-pointcloud. 3
-name. inputimage
…
-if w#$inputimage
-channels[inputimage] 0,1
…
ox,oy={I(#$inputimage,0,0)} # Absolute start point
# Shift sprite image by way of deltas
# from point-to-point. Get those deltas
# by subtracting the pointcloud from a
# one-plot-point-shifted copy of itself,
# i.e., foreach p(n)-p(n-1)
+shift[inputimage] -1,0,0,0,2,0
-reverse[-2,-1]
-sub[-2,-1] # diff point cloud:
-name. diffs # makes relative movetos…
-input {$ow*$pr},{$oh*$pr},1,1
-name. paramspace # stamp onto this image…
-input [-1]
-name. sprite # stamp from this image…
# Draw just one circle, then rubber-
# stamp it with shift/add commands.
stat={ellipse(#$sprite,{w/2},{h/2},-$sd,-$sd,0,1,0xffffffff,1.0);1.0}
# Single absolute moveto to position sprite
-shift[sprite] {$ox-w/2},{$oy-h/2},0,0,2,0
# Start voting… Here on out
# we make relative moves, then stamp.
-repeat {w#$diffs}
-add[paramspace] [sprite]
-shift[sprite] {I(#$diffs,$>,0)},0,0,2,0
-done
…
So far, so good. The voting scheme set-up mechanics are more involved, what with pointcloud differences being taken, but there is little extra performance drag in the -shift/-add
inner loop. Mathematically, the G’MIC -add
does just that, so there are no longer any curious attenuations taking place in the accumulation of up-votes in parameter space.
With voting irregularities laid to rest, the key feature of allowing target coins to vary in size, at least within a tolerable range, needs to be developed. That will add temporal slices to the parameter space. How many? Not sure, at present. It shall be the work of another weekend. In the meantime, have fun with the play code.