Perhaps a simple general rule will cover 98% of cases. For example, “The coin is the smallest circle that is not inside a larger circle, and with a radius that is at least 15 pixels”.
And perhaps another simple rule will cover 98% of the rest.
HA! Economy in expression! How often that crops up in so many endeavours!
The Writer’s Lament: “I am sorry I wrote such a long letter. I did not have time to write a short one.”
Attributed, I believe, to Sun Tzu: “To gain knowledge: add. To gain wisdom: subtract.”
As @David_Tschumperle noted, the better euro coin finder is probably the Circular Hough Transform, a generalization of the linear version already in G’MIC. The major pieces for a generalization are lying around. BUT, even there I foresee difficulties: round petri dishes, round bacterial colonies, round euros. Betwixt Scylla and Charybdis there is but a narrow way…
EDIT:
There is that…
Previous pictures of petri dish were about fungi.
As regards the bacteria, here they are:
For bacteria, which are usually white-yellowish, I usually put a black background.
Erwinia amylovora, in this picture is quite a big problem for plants in the USA too.
Actually, it was “imported”, by accident, in Europe from the USA many years ago and now it is quite established 
That’s why it is good that you are the plant pathologist. me: “bacteria, fungi, whydayawannaknowthediff anyway?”
You probably all found this already but here is a cod e for opencv in C++, java and python
tutorial_hough_circle
1 Like
Not to forget Digital Image Processing with C++ written by some guy we see around here and his buddies. Section 6.2, page 128. Hough transform. Go buy the book; the authors have families to feed…
Hahaha so do i… So if the authors agree for a refund i will buy it 
Considering the very low royalties earned on each sale, I’dreally need to sell a lot to be able to support myself!
…Or maybe just one though.
Hello everyone,
First off, thanks a lot indeed to anyone for your suggestions and input.
In all truth, I have opened this thread mostly out of curiosity because for very important images (e.g. the ones which I e-mail to someone else) I delete the coins manually through GIMP and G’MIC.
Within the mycological group of which I am a member I take several pictures as well.
They are for pleasure. No real work involved
Over the years, I have adopted a different “setup”: green background and coin of 1 euro
At present, with G’MIC I am mainly worried about the loss of my Exif data (with the command line interface).
For my personal needs, at work, this is a real deal breaker 
From what I have gathered, over the years, there is no way to avoid that, right?
I don’t know much about programming (only a tiny bit of SQL) therefore I don’t know whether this loss occurs also with other frameworks (e.g. ImageMagick)
With GIMP and G’MIC (through the GUIs) this data loss does not occur.
All the Exif data are preserved after the G’MIC filter has been applied.
Sadly, yes, ImageMagick doesn’t copy all the exif metadata. Exiftool can be used for that.
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.
2 Likes
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 MOVETOs. 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.
1 Like
Circular Hough
This — or something very much like this — may serve @Silvio_Grosso 's aims. Perhaps he could give the script a try when time permits. See details.
Following, sample arguments for various images seen here, and a gallery of results.
chough.gmic — 7f18dfedfba7 June 18, 2023
#@cli chough : radius>0,_BackgroundNoiseElim>0,_precision>=1,0<=_decimate<=1,0.1<=_sensitivity<1,_verbose=0
#@cli : Select image(s) to be scanned for circular-like artifacts, via
#@cli : Circular Hough. 'radius' sets the scan target pixel radius
#@cli : (required). Replace selected images with 1xN vector array lists of the
#@cli : N discovered center points of matching circles, along with the
#@cli : specified target radius parameter, these data are for the benefit of
#@cli : downstream mask plotters. Increasing 'BackgroundNoiseElim' favors
#@cli : edges, but faint edges may be taken as noise and
#@cli : eliminated. Increasing 'precision' sizes an internal 'parameter space'
#@cli : image. It is a multiplier that scales parameter space upward from the
#@cli : selected input image. Multipliers of 2-4 are less susceptible noise
#@cli : but consumes memory. 'decimate' reduces an internally generated
#@cli : pointcloud of candidate center points. Unity decimates the entire
#@cli : pointcloud (including solutions); zero leaves it intact, resulting in
#@cli : excessive plotting that can obscure solutions. The pointcloud tends to
#@cli : be highly redundant; decimations of 0.7 -> 0.9 are typical. Use
#@cli : smaller values (getting more points) for faint or noisy
#@cli : images. 'sensitivity' cuts all but the most likely solutions of
#@cli : clusters around potential center points; 0.9 is typical. Use lower (less
#@cli : sensitive) values to capture less likely center points, increase to
#@cli : reduce false solutions. Try to get 'radius' correct before adjusting
#@cli : 'sensitivity'. 'verbose' turns on intermediary displays of internal
#@cli : images and dumps of trial lists of center points.
#@cli : $ chough[imagetocheck] 55 -if h repeat {h} a='{I(0,$>)}' echo \$a done -fi
chough : check "${1}>0 && \
${2=15}>0 && \
${3=2}>=1.0 && \
${4=0.875}>=0 && ${4}<=1 && \
${5=0.9}>=0.1 && ${5}<=1 && \
isbool(${6=0})"
rad,nsmooth,pr,decim,sensitivity,verb=${1-6}
-foreach {
nm={-1,n}
-name. inputimage
ow={w#$inputimage}
oh={h#$inputimage}
# Sprite radius
sd={_round($pr*$rad+1,1)}
-edges[inputimage] $nsmooth%
-oneminus[inputimage]
-if $verb
-display[inputimage] ,
-fi
# Trimming the data
# has little effect on solution
-fill[inputimage] 'i>0?(u(1)>($decim)?1:0):0'
-input {$ow*$pr},{$oh*$pr},1,1
-name. sprite
# Draw circular sprite for shift/adding paramspace
# edgepoints. Draw just one circle, then rubber-
# stamp with shift/add
stat={ellipse(#$sprite,{w/2},{h/2},-$sd,-$sd,0,1,0xffffffff,1.0);1.0}
-pointcloud[inputimage] 3
-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
-move. 0
-sub[-3,-2]
-name.. diffs
-input {$ow*$pr},{$oh*$pr},1,1
-name. paramspace
-shift[sprite] {$ox-w/2},{$oy-h/2},0,0,2,0
-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>=$sensitivity*iM?1:0
-if $verb
-display ,
-fi
-if im==iM
-echo[^-1] "No\ detected\ coins\ @\ "$rad"\ radius."
-else
# Find means 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[pointcloudimage] 64
medianofclusters: -skip ${1=32},${2=0}
ed={$1^2}
verb=$2
echo[^] "Extract from selected images of impulse pixels \
point cluster median locations with radius "$ed" or less."
-foreach {
-pointcloud. 3
-channels. 0,2
-if w>1 # Takes at least two points to cluster
# 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
-fi # w>1 - Takes at least two points to cluster
} # foreach image in command's selection
#@cli circlefix : radius>0,_preblur(0)>=0,_outer(2)>0,_nsmooth(15)>=0,_medianf(10)>0,_medians(10)>0,_decimate(0.875)>=0&&<=1,verbose=0
#@cli : Replace circular features with given 'radius' with an inpaint-generated
#@cli : synthesized patch.
#@cli : 'preblur' Optional pre-blurring to reduce false identification of
#@cli : circular features. Default to no blurring (0).
#@cli : 'outer' Optionally extend synthesized path boundary by outer number
#@cli : of pixels. Default to two pixels.
#@cli : 'nsmooth' Edge-detection smoothing. Default to 15, Larger to further
#@cli : smooth edges; smaller to detect faint circular features.
#@cli : 'medianf/medians' Blur/sharpen parameters for edge detection. Default
#@cli : to 10/10. Adjust blur down and sharpen up for greater edge
#@cli : detection, but also susceptibility to false detection.
#@cli : 'decimate' Decimate pointcloud by this factor. Default to
#@cli : 0.875; limit to 1 (full decimation). Larger arguments yield
#@cli : greater decimation and faster results, but a greater
#@cli : likelihood of missed circular features.
#@cli : 'sensitivity' Reduces all but the most likely solutions of pointcloud
#@cli : clusters around potential center points; 0.9 is typical.
#@cli : Use lower (less sensitive) values to capture less likely
#@cli : center points, increase to reduce false solutions.
#@cli : Try to get 'radius' correct before adjusting 'sensitivity'.
#@cli : 'verbose' Set to enable display of intermediary analytic images.
#@cli : $ circlefix[0] 32
circlefix : check "${1}>0 && \
${2=0}>=0 && \
${3=2}>0 && \
${4=15}>0 && \
${5=10}>0 && \
${6=10}>0 && \
${7=0.125}>=0 && ${7}<=1 && \
${8=0.9}>=0.1 && ${8}<=1 && \
isbool(${9=0})"
rad,preblur,outer,nsmooth,medianf,medians,decimate,sensitivity,verbose=${1-9}
-foreach {
nm={-1,n}
-name. coinpic
+blur[coinpic] {$preblur},2
-median. {$medianf},{$medians}
-name. medianpic
-if $verbose -v + -fi
+chough[medianpic] $rad,$nsmooth,1,$decimate,$sensitivity,$verbose
-name. clist
+fill[medianpic] 0
-name. mask
-repeat {h#$clist}
cx,cy,r={I(#$clist,0,$>)}
ofs={$r+$outer}
-if isnum($sprite)==0
-input {2*$ofs+1},{2*$ofs+1},{d#$medianpic},{s#$medianpic},1
-name. sprite
-fi
-image[mask] [sprite],{$cx-$ofs},{$cy-$ofs}
-done
-remove[^coinpic,mask]
-inpaint_matchpatch[coinpic] [mask],0,13,13,{2*$outer},1,0
-keep[coinpic]
-name. $nm
}
$ gmic -command chough.gmic -h circlefix
[gmic]-0./ Start G'MIC interpreter.
[gmic]-0./ Import commands from file 'chough.gmic', with debug info (3 new, total: 4602).
circlefix:
radius>0,_preblur(0)>=0,_outer(2)>0,_nsmooth(15)>=0,_medianf(10)>0,_medians(10)>0,_decimate(0.125)>=0&&<=1,verbose=0
Replace circular features with given 'radius' with an inpaint-generated
synthesized patch.
'preblur' Optional pre-blurring to reduce false identification of
circular features. Default to no blurring (0).
'outer' Optionally extend synthesized path boundary by outer number
of pixels. Default to two pixels.
'nsmooth' Edge-detection smoothing. Default to 15, Larger to further
smooth edges; smaller to detect faint circular features.
'medianf/medians' Blur/sharpen parameters for edge detection. Default
to 10/10. Adjust blur down and sharpen up for greater edge
detection, but also susceptibility to false detection.
'decimate' Decimate pointcloud by this factor. Default to
0.875; limit to 1 (full decimation). Larger arguments yield
greater decimation and faster results, but a greater
likelihood of missed circular features.
'sensitivity' Reduces all but the most likely solutions of pointcloud
clusters around potential center points; 0.9 is typical.
Use lower (less sensitive) values to capture less likely
center points, increase to reduce false solutions.
Try to get 'radius' correct before adjusting 'sensitivity'.
'verbose' Set to enable display of intermediary analytic images.
Example:
[#1] circlefix[0] 32
Table of trials
| File | Post | radius | preblur | outer | nsmooth | medianf | medians | decimate | sensitivity |
|---|---|---|---|---|---|---|---|---|---|
| 1.jpg | 1 | 44 | 2 | 5 | 15 | 5 | 6 | 0.8 | 0.9 |
| apple1.jpg | 12 | 58 | 2 | 10 | 15 | 5 | 6 | 0.8 | 0.9 |
| apple2.jpg | 19 | 50 | 2 | 5 | 15 | 5 | 6 | 0.8 | 0.9 |
| armillaria_mellea.png | 40 | 43 | 2 | 20 | 15 | 5 | 5 | 0.8 | 0.9 |
| blueberry.jpg | 19 | 50 | 2 | 16 | 15 | 5 | 6 | 0.8 | 0.9 |
| capsule_petri_retro.jpg | 21 | 18 | 2 | 5 | 20 | 5 | 5 | 0.8 | 0.9 |
| coins_small.png | ** | 37 | 2 | 12 | 15 | 5 | 6 | 0.8 | 0.9 |
| coins_small.png | ** | 43 | 2 | 13 | 20 | 5 | 6 | 0.8 | 0.9 |
| erwinia_amylovora_nsa.jpg | 32 | 10 | 3 | 4 | 15 | 30 | 30 | 0.5 | 0.8 |
| petri_dish.jpg | 29 | 12.5 | 2 | 3 | 30 | 40 | 40 | 0.5 | 0.4 |
| tiling.png | 44 | 51 | 2 | 40 | 15 | 20 | 30 | 0.8 | 0.9 |
| tiling_02.png | 44 | 83 | 2 | 40 | 15 | 20 | 30 | 0.8 | 0.9 |
| truncatella_nocciolo_fusto.jpg | 21 | 45 | 2 | 5 | 15 | 5 | 5 | 0.8 | 0.9 |
Gallery
1.jpg
apple1.jpg, apple2.jpg
armillaria_mellea.jpg, blueberry.jpg
capsule_petri_retro.jpg
coins_small.jpg (37 pixel radius), coins_small.jpg (43 pixel radius)
erwinia_amylovora_nsa.jpg
petri_dish.jpg
tiling.jpg
tiling_02.jpg
Notes
- capsule_petri_retro.jpg: When coin radii become small (≈15 pixels or less), locating the coin becomes problematic; more so as radius decreases. Similar issue with erwinia_amylovora_nsa.jpg
- coin_small.jpg: shifting the radius from 37 to 43 pixels picks off different sets of coins.
- tiling.jpg, tiling_02.jpg With increased medianf and medians arguments, noise from quasi-periodic backgrounds can be smoothed out; circular hough then works fine. Probably, the generic arguments given to inpaint_matchpatch could be better tuned, but that wasn’t key to the remit, to wit: find the centers of circle-like things.
2 Likes
It’s looking more, and more viable as a scientific filter.
Hello everyone (@grosgood, @Reptorian)
In the coming days, I will check for sure with my pictures.
Thanks a lot indeed!
Hi @Silvio_Grosso . Some improvements in the inpainting bit — minimized smudgy edges for textured backgrounds. Generally, internal changes for more refined in-painting. helpdoc updates: chough.gmic 47279854db9 - Sat Jun 24 19:27:21 2023 (EDT - UTC-4)
chough_gmic.txt (11.4 KB)
Rename chough_gmic.txt ⇒ chough.gmic.
$ gmic -command chough.gmic -input tiling_02.png circlefix. 83,2,30,15,20,30,0.8,0.95 o. /dev/shm/tiling_02_out.png
[gmic]-0./ Start G'MIC interpreter.
[gmic]-0./ Import commands from file 'chough.gmic', with debug info (3 new, total: 4605).
[gmic]-0./ Input file 'tiling_02.png' at position 0 (1 image 683x683x1x3).
[gmic]-1./ Seek 83 pixel radius circles in selected images; perform inpaint removal of same.
[gmic]-1./ Output image [0] as png file '/dev/shm/tiling_02_out.png' (1 image 683x683x1x3).
[gmic]-1./ End G'MIC interpreter.
Compare with last week:
Enjoy.
2 Likes
Wow, it’s looking ready as a official filter for G’MIC.
Hello @grosgood
At present, I am studying your basic G’MIC tutorials
This is because I am a beginner with this language: I have started using G’MIC since its very creation by David Tschumperlé but it was with Gimp through its GUIs
Currently I only know a bit of SQL
Here are a few questions:
1)
What does occur when the coin is on top of some mushrooms?
Usually it is not the case but once in a while it may occur.
In short, there is not a solid color as background (underneath the coins)?
Take this image for instance:
I have tried your command but it fails (Windows 11 - Powershell - gmic-3.2.5-cli-win64)
I suppose I am doing something wrong…
PS C:\Users\gross\Downloads\gmic-3.2.5-cli-win64> .\gmic.exe -command chough.gmic -input agrocybe_praecox.jpg circlefix. 83,2,30,15,20,30,0.8,0.95 -o prova.jpg
[gmic]-0./ Start G’MIC interpreter.
[gmic]-0./ Import custom commands from expression ‘chough.gmic’ (1 new, total: 2410).
[gmic]-0./ Input file ‘agrocybe_praecox.jpg’ at position 0 (1 image 2992x4487x1x3).
[gmic]-1./ Input file ‘circlefix.’ at position 0
[gmic]-1./ *** Error *** Command ‘input’: Unknown filename ‘circlefix.’.
One more question…
If I understand correctly your code is meant to “only” remove the coins, right?
In short, I am supposed to add manually, in the image, a graduated scale, depending on the size of the coin removed.
For instance, with a 5 cents coins I am going to add later on a 2 cm (20 mm) graduated scale and so on and so forth
Is it correct?
At present, I am doing all these steps with GIMP:
- I add the graduated scale: it is a svg image with transparent background;
- I remove the coin with G’MIC: I paint manually, with red, over the coin, and I apply the filter: Inpaint - multi scale.