Conic Hough
Careful - one typo away from Comic Hough — which epitomizes various aspects of this project.
- Armillaria mellea reposing on green with its five euro piece.
- Same. Flattened to near graphic shapes. Conic Hough locates the euro piece and masks it in orange.
- An image containing a column vector. The script consumes its selected images and replaces them with column vectors of likely circle centers. Here, the column vector has one entry with three components: [x,y,r]; the first two components are the coordinates of where Conic Hough thinks the center of the five euro piece resides. r is the distinguishing radius of all the circles that Conic Hough aims to seek out and mark.
$ gmic chough.gmic -input Armillaria_mellea.jpg v + chdemo. 83,0.2,2,1
chdemo:
Toy framework to preprocess images for consumption by chough,
which implements the Conic Hough algorithm. Preprocess ⇒ means ‘Flatten to near-graphic shapes.’ Hit the arrow for the chough.gmic
code for details. Some of it is even commented.
chough.gmic
#@cli chough : radius>0,_sensitivity>0,_precision,_verbose
#@cli : Select: image(s) to be scanned for circular-like artifacts
#@cli : of pixel 'radius'. Execute Conic Hough. Locate the
#@cli : noisy clusters and compute median points of same. Replace
#@cli : selected with a 1xN vector array list of N discovered median
#@cli : points. 2D coordinates + given radius parameter for downstream
#@cli : plotters to draw circular masks centered on the median points.
#@cli : As 'sensitivity' approaches zero, more suspected artifacts
#@cli : could turn up, but at the price of longer analysis. Could
#@cli : also turn up just noise instead of artifacts. Increasing
#@cli : 'precision' sizes an internal 'parameter space' image.
#@cli : Argument is a multiplier that increases the width and height
#@cli : of the selected input image. Factors of 2-4 is less susceptible
#@cli : noise, but consumes more memory.
#@cli :
chough : check "${1}>0 && ${2=0.01}>0 && ${2}<=1 && ${3=2}>=1.0 && isbool(${4=0})"
rad,sen,pr,verb=${1-4}
-foreach {
nm={-1,n}
-name. inputimage
ow={w#$inputimage}
oh={h#$inputimage}
# Sprite diameter
sd={$pr*$rad+1}
-luminance[inputimage]
-gradient_norm[inputimage]
-fill[inputimage] ">abs(
i-j(1,1,0,0,0,1)
)>$sen*iv?
1:
abs(
i-j(1,0,0,0,0,1)
)>$sen*iv?
1:0"
# Try to image process circular-like artifacts
# as thin, single-pixel circles.
-closing_circ[inputimage] 3
-if $verb
-display ,
-fi
# Performance killer. More than half of runtime
# takes place in thinning...
-thinning[inputimage] 1
-if $verb
-display ,
-fi
# Draw circular sprite 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.
-pointcloud[inputimage] 3
-if w#$inputimage
-channels[inputimage] 0,1
-fill[inputimage] "$pr*I"
-input {$ow*$pr},{$oh*$pr},1,1
-name. paramspace
-input {2*$sd},{2*$sd},1,1
-name. sprite
# 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
-keep[paramspace]
-normalize_local[paramspace] 10,200,4%,4%,1,0,255
-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
}
_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,_sensitivity>0,_precision,_verbose,_sensitivity>0,_precision,_verbose
#@cli : Toy framework
#@cli :
chdemo : check "${1}>0 && ${2=0.01}>0 && ${2}<=1 && ${3=2}>=1.0 && isbool(${4=0})"
rad,sen,pr,verb=${1-4}
-foreach {
+median. 40,80
-repeat 3
-smooth. 80,0.8,0.3,0.8,1.1,0.8,7
-done
-if $verb -v + -fi
+chough. $rad,$sen,$pr,$verb
-if $verb
-display ,
-fi
-eval. "
vrb=$verb;
PP=crop(#-1);
if(vrb, print(PP));
repeat(
size(PP)/3,idx,
ellipse(#-2,PP[idx,2],PP[idx+2],PP[idx+2],0,1,[255,170,0])
)
"
}
Arguments:
- Radius (83 pixels). Conic Hough won’t notice circles of other radii. Nor ellipses. Nor messy piles of mushroom roots. The algorithm is picky on this. ± one or two pixels and the euro is passed over as Not A Matching Circle. More on that below.
- Sensitivity. (0.2 — Bigger ⇒ marginal imagery is more likely to not even be considered) Too big (0.4+) and euros may not be noticed. Too small (0.05–) and too much is noticed.
- Parameter space multiplier (2). Internally, Conic Hough plots circular ‘sprites’ in a ‘parameter space.’ This is a a grayscale, multiplied up from the given image. Conic Hough draws some ≈42,000 sprites, very — very! — faint sprites, on this parameter image. This tracing process into parameter space works off the edge image, which, in turn, has been derived from the source image, and which Conic Hough follows, transferring the path to parameter space and tracing with sprites (faintly!) into that parameter space. Should there be an edge image that looks like a circle — exactly with a radius of 83 pixels — then stars align and the tracings of an 83 pixel circular sprite (very faint!) around the circumference of an 83 pixel radius, circular edge image, transferred to parameter space, causes a Hotspot! to appear exactly in the center of the edge image. That’s where the rims of all the faint circles criss-cross and criss-cross and criss-cross, since the radii match. Then it is just a matter of locating the coordinates of the hot spot. It corresponds to the center of the five euro piece, which has a radius of ≈83 pixels in the image. This hot spot won’t happen if the edge image is larger or smaller than the sprite. See the graphics following. This tracing of matching circles, sprite and edge image, is the gist of the Conic Hough algorithm’s workings.
- A boolean flag. Turn it on and Conic Hough dumps bits and pieces of its internal state to gmic’s log, and stops here and there to display intermediary parameter space images. See the code listings above.
Parameter space gallery
Some internal images illustrating the progression of Conic Hough:
If a photograph can be coaxed into a state of Ligne claire — perhaps like a frame from Hergé’s The Adventures of Tintin, then there is a hope for finding the five euro piece. If the coin slips from the depth of field and is blurry, then Conic Hough just can’t cope: it needs edges to position sprite plotting.
Ditto. Morphological thinning. This is the time pig. More than half the run time is in thinning, but it delivers on Ligne claire. Pondering other approaches is on the TODO.
Some forty-two thousand 83 pixel circular sprites tracing the edge lines on the parameter space image makes a hotspot! where the stars align: the tracing of 83 pixel radial sprites along the circumference of an 83 pixel radial edge image engender a pileup at the exact center of the parameter space circle image. Any other radius won’t work — like the mushroom heads. This is the essence of Conic Hough. Most everything else is book-keeping.
What’s Next?
Fix what is missing: Conic Hough in a 3D parameter space can do trial radii, say, ± 20% around a target radius. The present implementation furnishes no lee-way on the euro piece changing size from input image to input image. Coins move around. Cameras move around. This implementation will miss the euro if the radius is just one or two pixels off. That won’t work in ‘set-and-forget’ production environments.
So this isn’t production. But the way forward is clear. Hack on it some more next weekend. In the meantime, everyone have fun with what’s here.