searching for the signs

2. shape recognition

The previous entry discussed finding sign-candidates on video frames. Since then, OSM users contributed higher resolution videos with worse weather situation - all the examples of this entry are captured from these.

The last version had problems with multiple signs mounted on the same pole: the shape of two circular signs tightly packed would be a '8' instead of two distinct 'o' shapes, as their frames are touching. The original code took the middle of the image as center of tracing, which would be the touching part of the two edges.

The solution to this problem is simple: do not assume the center of the image is the center of the sign. Instead, flood-fill-search for large white-gray-black areas and run the rest of the code for each such area. This way the '8' shaped combo is split into multiple parts: if background is not grey, the two separate inner parts; else those two inner parts and 4..6 outer parts. Let's call these parts "candidates". For example this is the middle-left outer candidate of a pair of signs (upper sign is a (60), lower sign is an overtake restriction, background is white mist):

After having all the little candidates, with a lot of false ones included, the next step is running the ray tracing from the middle of each, as described in the previous entry. However, instead of just checking whether the ratio of the inner and outer radii are within a range (for circular shapes), the inner radii are saved in an array in a normalized form. The unrolled variant is shown as function on the bottom of the debug output (horizontal axis is angle, vertical axis is normalized inner radius):

A perfectly round sign would have a constant radius of a given value larger than 0. The above example demonstrates this with some real-life noise. An elliptical shape (or a circular sign with some perspective distortion) would have a sine-like shape on this function, but the amplitude of the sine would be small and the whole function would have a large positive offset.

A sign that's not circular would have positive and negative swings:

input image rays output with
shape function

The function is unrolled from 3 o'clock (horizontal ray to the right) CW (clock-wise) and clearly shows the 3 corners, which are on the longest radii. These are local maximums of the function. Local minimums are on the straight lines of the frame at a point that happens to be the closest to the center.

A simple shape recognition approach is to evaluate this function for:

the normalized value of the radius at specific angles
angle of local maximums or minimums (peaks)

To avoid confusion about the directions and angles, shape configuration is given in the "o'clock" notation, with floating point hours (i.e. 2.5 means 2:30, which is 1/24 to the up from 0 with the unrolling).

Below is a short description about each of the current recognition rules:

example result & rules
invalid: at least 30% of the rays are below -60 (very close to the center or no frame at all); in this example only the upper left section has reasonable radius to the red frame
round: more than 85% of the rays are between 60 and 100; this allows elliptical shapes as well
no overtake: the red car is taken as part of the frame as it matches the frame color; this results in a large negative bump at a specific angle; this is specified with 3 value ranges: for the left half, the rule is the same as for round signs; for the right part there are two overlapping regions describing negative radius (more negative around 9 o'clock)
give way: there must be 3 positive peaks: at 2 o'clock, at 10 o'clock and at 6 o'clock (with +- 0.5 hours tolerance for each)
warning: same as the previous triangle sign with different peak angles: 4, 8 and 12 o'clock
no pass, bar: this one is less obvious: there is a very thick red frame all around, except at 3 o'clock and 9 o'clock where it's thin; this sign uses both type of rules: the lower and upper half shall have short inner radii while there must be a positive peak at 3 and 9.

example	result & rules
	invalid: at least 30% of the rays are below -60 (very close to the center or no frame at all); in this example only the upper left section has reasonable radius to the red frame
	round: more than 85% of the rays are between 60 and 100; this allows elliptical shapes as well
	no overtake: the red car is taken as part of the frame as it matches the frame color; this results in a large negative bump at a specific angle; this is specified with 3 value ranges: for the left half, the rule is the same as for round signs; for the right part there are two overlapping regions describing negative radius (more negative around 9 o'clock)
	give way: there must be 3 positive peaks: at 2 o'clock, at 10 o'clock and at 6 o'clock (with +- 0.5 hours tolerance for each)
	warning: same as the previous triangle sign with different peak angles: 4, 8 and 12 o'clock
	no pass, bar: this one is less obvious: there is a very thick red frame all around, except at 3 o'clock and 9 o'clock where it's thin; this sign uses both type of rules: the lower and upper half shall have short inner radii while there must be a positive peak at 3 and 9.

The shapes are printed in the bottom left corner with red font; these are the shapes as recognized by the above simple algorithm.

There are still some corner cases, triangular shapes are sometimes matched on random shaped noise that happen to have local maximums in the right ranges. This will be fixed by additional rules that would require that no local maximums may be present on the straight edges.