Maybe stupid, but why not directly shifting bits ?
shiftin CLK, AO, 0, (bit1,bit2,bit3,bit4,bit5,bit6,bit7,bit8,bit9,bit10,bit11,bit12,bit13,bit14,bit15)
Centre of line tracking algorithm
- Thread starter hippy
- Start date
shiftin CLK, AO, 0, (bit1,bit2,bit3,bit4,bit5,bit6,bit7,bit8,bit9,bit10,bit11,bit12,bit13,bit14,bit15)
+1Dang it, Hippy, you did it again!
Thank you @hippy, will try this when I get home and report the savings. Somehow you have this great eye for useless manoeuvres.
Edmunds
Dear @Besqueut,
It is not stupid, it is just that you probably have not followed the entire discussion spread out on several threads and no one can be blamed for that sort of thing
. This part of the code is responsible for getting all 128 pixels in - 128 CLK pulses are needed. Using variables of 16 bytes allows to compare the string of 0 and 1 representing a pixel each in every byte to be compared to a lookup table in eeprom for deciding if this byte looks more like a line or no-line. Thus each byte becomes 0 or 1 and is represented by a bit in 16-bit word so my later calculation does not have to deal with anything bigger than that.By now I believe this is the most efficient method available for what needs to be done, because while working with all 128 bits would in theory increase resolution, in practice you would have to start dealing with noise [which is present] and this does not allow for a very simple line finding algorithm. This, in turn, would make things slower, which would reduce the effective resolution by reading the state fewer times per mm driven, which would mean larger correction needed per iteration. It is better to read the line approximately, but very many times per mm driven, than read it very precisely, but few times per mm driven.
Thank you for your input,
Edmunds
Dear all,
I owe an implementation report of the ideas discussed recently. Here you are.
I have added @hippy's optimization and while it has made the code a lot shorter, the actual performance gain is not so big - maybe 200 microseconds for 15 lines of code. I was hoping for more.
Then I implemented the calibration routine I came up with while 'offline'. My initial idea was to acquire another sample and take 4 to 8 analog values of evenly spread out pixels and adjust integration time [=exposure] according to that. My calculation of this taking around or below 2ms was entirely wrong most importantly because maximum integration time [=a delay, just wait and do nothing] alone is 2.6ms. The entire thing threw me back to about 14ms for the total loop and that I just could not be happy with anymore.
Then, I noticed I do these 4 dummy pixel reads from the edges of the sensor to get a 15 bit number so I have a proper zero. By now, I have figured out there are better ways of dealing with this, but more on that below, have not implemented anything and this is a different topic. So, with dummy reads still present, I tried to make them less dummy and measure light level instead. It turned out after some fiddling and measuring actual values, storing them in eeprom and reading back for analysis on the computer (learned something from playing with the magnetometer in the other thread, you know), taking values of only two pixels was sufficient, provided the right target voltages were used. On top of that, I found a place for adjusting the second parameter if I run out of integration time range - sensor LED intensity. So if I cannot reduce integration time anymore, I will try to reduce the LED light output on the sensor to a certain level and vice versa for low light conditions.
This now takes 8ms worst case, about 6ms average and 4.5ms in a very well lit room (shortest integration time). This is a little more than I hoped for in terms of numbers but the car is very, very difficult to push off the line and even if that succeeds, it will stick like crazy to any line or dark-bright edge it can find near by. The important pieces of code attached below.
On a side topic. Dealing with +/-0. If I would go back to 16 bits of line_state variable, I could actually improve small error (steady state?) performance. While having two zeros and not doing anything about them is just a larger dead band, integration can change all that. Imagine, if the first time the line_state is -0, i define the error is also 0. However, if line_state = -0 the second time around, I treat this as -0.5 and issue half of error I would issue in case line_state would be full -1. I have not yet tried to do this, and there is little motivation when it comes to stability on the line - as I said, I have a hard time imagining how better would look, but as a strictly theoretical exercise, this presents an interesting problem to solve and quite possibly this can have something to do with my next goal for this part of the project - minimize power consumption. Reaction to smaller deviation means smaller errors and smaller errors mean less steering. Less steering means less power required.
Cheers,
Edmunds
I owe an implementation report of the ideas discussed recently. Here you are.
I have added @hippy's optimization and while it has made the code a lot shorter, the actual performance gain is not so big - maybe 200 microseconds for 15 lines of code. I was hoping for more.
Then I implemented the calibration routine I came up with while 'offline'. My initial idea was to acquire another sample and take 4 to 8 analog values of evenly spread out pixels and adjust integration time [=exposure] according to that. My calculation of this taking around or below 2ms was entirely wrong most importantly because maximum integration time [=a delay, just wait and do nothing] alone is 2.6ms. The entire thing threw me back to about 14ms for the total loop and that I just could not be happy with anymore
.Then, I noticed I do these 4 dummy pixel reads from the edges of the sensor to get a 15 bit number so I have a proper zero. By now, I have figured out there are better ways of dealing with this, but more on that below, have not implemented anything and this is a different topic. So, with dummy reads still present, I tried to make them less dummy and measure light level instead. It turned out after some fiddling and measuring actual values, storing them in eeprom and reading back for analysis on the computer (learned something from playing with the magnetometer in the other thread, you know
), taking values of only two pixels was sufficient, provided the right target voltages were used. On top of that, I found a place for adjusting the second parameter if I run out of integration time range - sensor LED intensity. So if I cannot reduce integration time anymore, I will try to reduce the LED light output on the sensor to a certain level and vice versa for low light conditions.This now takes 8ms worst case, about 6ms average and 4.5ms in a very well lit room (shortest integration time). This is a little more than I hoped for in terms of numbers but the car is very, very difficult to push off the line and even if that succeeds, it will stick like crazy to any line or dark-bright edge it can find near by. The important pieces of code attached below.
Code:
#macro ReadLineData128()
SampleLine 'Sample line at 8MHz
GetLeftLightLevel 'Measure light level on pixel on the left side
GetLineState 'Store binary pixel data into Line_state
GetRightLightLevel 'Measure light level on pixel on the right side
SetIntegrationTime 'Perform mathematics on Vout to get Tint
#endmacro
#macro SIPulse()
high SI
pulsout CLK, LinePulse
low SI
#endmacro
#macro SampleLine()
SIPulse 'Start a sample
pwmout CLK, 1, 4 'Clock out some fast pulses (8MHz @ 64MHz clock speed)
pauseus Tint 'Allow for sufficient integration time
pwmout CLK, OFF 'Finish the sample
SIPulse
#endmacro
#macro GetLeftLightLevel()
Vout = 0 'Set light level to zero for each loop
pulsout CLK, LinePulse 'Pulse clock to start reading next pixel ...
pulsout CLK, LinePulse 'Pulse clock to start reading next pixel ...
pulsout CLK, LinePulse 'Pulse clock to start reading next pixel ...
readadc 10, pixel_data 'Measure voltage on pixel #4 for light intensity
Vout = Vout + pixel_data 'Add the value to the accumulator
pulsout CLK, LinePulse 'Pulse clock to start reading next pixel ...
#endmacro
#macro GetRightLightLevel()
readadc 10, pixel_data 'Measure voltage on pixel #124 for light intensity
Vout = Vout + pixel_data 'Add the value to the accumulator
pulsout CLK, LinePulse 'Pulse clock to start reading next pixel ...
pulsout CLK, LinePulse 'Pulse clock to start reading next pixel ...
pulsout CLK, LinePulse 'Pulse clock to start reading next pixel ...
pulsout CLK, LinePulse 'Pulse clock to start reading next pixel ...
#endmacro
#macro GetLineState()
adcsetup = 0 'Reset inputs to digital for digital read of 120 pixels
Line_state = 0 'Set line_state to 0 to avoid clearing individual bits
'Shift sensor data into variables in location 56 to 70
shiftin CLK, AO, 0, (@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc,@bptrinc)
read @bptrdec, bit14 'Get pixel state from position 70 and put 1 or 0 into bits of Line_state
read @bptrdec, bit13
read @bptrdec, bit12
read @bptrdec, bit11
read @bptrdec, bit10
read @bptrdec, bit8
read @bptrdec, bit8
read @bptrdec, bit7
read @bptrdec, bit6
read @bptrdec, bit5
read @bptrdec, bit4
read @bptrdec, bit3
read @bptrdec, bit2
read @bptrdec, bit1
read @bptrdec, bit0
#endmacro
#macro SetIntegrationTime()
Vout = Vout / 2 'Obtain average of pixel #4 and #124 outputs
Select case Vout
case > Vtarget 'If voltage above target (saturation possible) ...
if Tint > TintMin then '... if Tint not already at minimum ...
Tint = Tint - TintStep '... reduce by TintStep to try to converge
elseif LEDPWM > LEDMin then 'In case Tint cannot be reduced, try to reuce LED intensity ...
LEDPWM = LEDPWM - LEDStep '... reduce LED intesity by LEDStep
pwmduty LED, LEDPWM
endif
case < Vtarget 'If voltage below target (cannot see in the dark) ...
if Tint < TintMax then '... if Tint not already at maximum ...
Tint = Tint + TintStep '... increase by TintStep to try to converge
elseif LEDPWM < LEDMax then 'In case Tint cannot be reduced, try to increase LED intensity ...
LEDPWM = LEDPWM + LEDStep '... increase LED intensity by LEDStep
pwmduty LED, LEDPWM
endif
endselect
#endmacro
#macro GetLinePos(line_state)
'Determine the position of the line
if line_state > 0 then 'If there is any line at all ...
line_width = NOB line_state '... find the number of set bits = line width ...
line_edge = NCD line_state '... find the highest set bit = rightmost edge of the line ...
line_centre = line_width / 2 '... store half of the line in a new variable to save on number of operations
select case line_edge 'Cater for right and left side limits situations when not all of the line is seen ...
case 1 : line_pos = line_centre '... line dissapearing on the left side ...
case 15 : line_pos = 15 - line_centre '... line dissapearing on the right side ...
else : line_pos = line_edge - line_centre '... both edges inside field of view
endselect
else
endif
select case line_pos 'Maybe can be done faster, but takes us as it is
case 1 to 7 : Eline = -8 + line_pos 'Set negative Eline from line_pos
case 9 to 15 : Eline = line_pos - 8 'Set positive Eline from line_pos
else : ELine = 0 'Set error to zero
endselect
#endmacroCheers,
Edmunds
Last edited:
I just have a look to your data, as per #18
For example this pattern :
11111100 01111100 10111100 11111001
is full zéro (absolutely no line seen...)
Another point : if 11111100 is 0
then 00111111 should be 0 as well (but it is not...)
IHMO, there should be the same number of zero and one patterns,
Symetricals patterns should have the same value.
Negatives patterns should have opposites values.
This will not resolve boundary problem :
00000100 11111111 detect a pixel
but
01001111 11110000 is the same thing, but pixel is not detected.
IHMO, there is no advantage to define "intelligent" patterns...
Patterns with 0 to 4 blacks pixels should be zero, others one.
(but this will not resolve boundary problem)
Last edited:
Dear @Besqueut,
Thank you for your input.
Yes, the pattern definitions is one area I could look into. I did them long ago and fast to get something working not for it to be great. Now that the rest of it is becoming pretty great, this should also be addressed. Will do at some point.
Edmunds
Thank you for your input.
Yes, the pattern definitions is one area I could look into. I did them long ago and fast to get something working not for it to be great. Now that the rest of it is becoming pretty great, this should also be addressed. Will do at some point.
Edmunds
When I run the code on a 28X2 and adjust timing measurements for 64MHz the original takes 1723us and the optimised code takes 777us. That should be about twice as fast with a saving of near 1000us.
It might be worth investigating why you are not getting savings anywhere near what I am seeing.
@hippy, I do get the same results as yours if I test only this portion of the code, so it is possible, it alone is actually giving the speed increase and 200us saving is an underestimate. I calculated 200us from the difference of running the entire code with your and old way, so there must have been something else that changed.
While it is simple to time isolated sections of the code, it has become quite tricky to time and compare the entire loop in real life situation, because a lot depends on how many ones or zeros I get to work with and what is the surrounding light level for integration time. Each of the variable bits can be isolated by providing some fixed value for that item, but I'm only learning to use #ifdef instructions to their full potential and doing it manually is prone to me forgetting to adjust all the right places every time.
Edmunds
It can be difficult to analyse where time is used but it is worth trying to do that. It seems you saved 1000us from my optimisation but have gained 800us of overhead elsewhere. You will be fighting a never-ending challenge to improve things if you gain with one hand but lose with the other, and have no idea where those gains and losses are.