ShiftP

Buddy of mine wants to straighten some images automatically, kinda like ShiftN :



Oh, you'll want Python version 2, I said:

#makefile
PIP2=pip
PYTHON2=python

setup2:
$(PIP2) install --user virtualenv
$(PYTHON2) -m virtualenv v2
source v2/bin/activate && pip install numpy Pillow pylsd

And Python 3, I said, also in a VirtualENVironment sandbox:

#makefile
PIP3=pip3
PYTHON3=python3

setup3:
#$(PYTHON3) -m venv v3
source v3/bin/activate && pip install numpy Pillow scipy

setup: setup2 setup3
-mkdir temp

run:
source v2/bin/activate && python FindLines.py Source.jpg

source v3/bin/activate && python Warp.py

Start by finding all your lines:

#FindLines.py
import json
import numpy
import sys

from PIL import Image
import pylsd.lsd

def ExportMeta(fileName,outName):
meta={'fileName':fileName}
image=Image.open(fileName)
meta['width']=image.width
meta['height']=image.height
grayScale=numpy.asarray(image.convert('L'))
lines=pylsd.lsd(grayScale)
lineArray=[]
for row in lines:
lineArray.append(list(row))
meta['lineArray']=lineArray

with open(outName,'w') as f:
f.write(json.dumps(meta,sort_keys=True,separators=(',', ': '),indent=4))


ExportMeta(sys.argv[1],'temp/meta.json')

Always prefilter your inputs, I nagged:

#Warp.py
def FindWeightedLines(lineArray,meta):
linesHorizontal=[]
linesVertical=[]
for (x0,y0,x1,y1,width) in lineArray:
if width<2:
continue
h0=RemapXY(x0,y0,meta)
h1=RemapXY(x1,y1,meta)
dx=abs(h0[0]-h1[0])
dy=abs(h0[1]-h1[1])
if max(dx,dy)<min(dx,dy)*4:
continue
magnitude=dx*dx+dy*dy
if dx<dy:
linesHorizontal.append([magnitude,h0,h1])
else:
linesVertical.append([magnitude,h0,h1])

return sorted(linesHorizontal)[-30:]+sorted(linesVertical)[-30:]
#Always prefilter your inputs!!!

Now here's the tricksy bit, in *TWO* parts, setup a perspective transform:

#Warp.py
def RemapXY(x,y,meta):
xx=(x-meta['width']/2)/meta['scale']
yy=(y-meta['height']/2)/meta['scale']
return (xx,yy,1)

def UnmapXYZ(xx,yy,zz,meta):
rx=xx/zz
ry=yy/zz
x=rx*meta['scale']+meta['width']/2
y=ry*meta['scale']+meta['height']/2
return (x,y)

*And* a non-linear warp. We don't need the full power of Chebyshev Polynomials here, I reminded him. We can just use 0, 1, x, y, x², y² and xy. Why? Because all spanning basis-es are equivalent in low dimensions!

#Warp.py
def ApplyTransform(transform,x,y,z):
rx=x*transform[0]+y*transform[1]+z*transform[2]
ry=x*transform[3]+y*transform[4]+z*transform[5]
rz=x*transform[6]+y*transform[7]+z*transform[8]
nonLinear=True
if nonLinear:
rx+=x*y*transform[9]
ry+=x*y*transform[10]
rx+=x*x*transform[11]
ry+=x*x*transform[12]
rx+=y*y*transform[13]
ry+=y*y*transform[14]
return (rx,ry,rz)

def ApplyTransformhomogenous(transform,x,y,z):
(hx,hy,hz)=ApplyTransform(transform,x,y,z)
return (hx/hz,hy/hz)

Next you'll need a loss function, weakly constrain your transform matrix, then setup a sum-of-squares for your error term:

#Warp.py
def loss(transform,meta):

result=0

for i in range(9):

t=transform[i]

if i==0 or i == 4 or i == 8:

t=transform[i]-1

result += t*t

for(weight,h0,h1) in meta['weightedLineArray']:

(x2,y2)=ApplyTransformHomogenous(transform,*h0)

(x3,y3)=ApplyTransformHomogenous(transform,*h1)

dx=abs(x3-x2)

dy=abs(y3-y2)

if dx<dy:
(dx,dy)=(dy,dx)
q=math.sqrt(dx*dx + dy*dy)
dx=dx/q
dy=dy/q

result += dy*dy

Are we done yet? Oh, a driver...:

#Warp.py
def Main():
with open('temp/meta.json','r') as f:
meta=json.loads(f.read())
meta['scale']=math.sqrt(meta['width']*meta['height'])/2

meta['weightedLineArray']=FindWeightedLines(meta['lineArray'],meta)

m=minimize(loss,[1,0,0,0,1,0,0,0,1,0,0,0,0,0,0],args=meta)

transform=m.x

(x0,y0,x1,y1) = FindClipRectangle(...)

source=Image.open(meta['fileName'])

image=Image.new('RGB',(x1-x0,y1-y0),(0,0,0))

draw=ImageDraw.Draw(image)

meta['splitCount']=64

for x in range(meta['splitCount']):

for y in range(meta['splitCount']):

p00=SquareMap(x,y,meta)

p01=SquareMap(x,y+1,meta)

p10=SquareMap(x+1,y,meta)

p11=SquareMap(x+1,y+1,meta)

r00=ApplyTransform(transform,*RemapXY(*p00,meta))

r01=ApplyTransform(transform,*RemapXY(*p01,meta))

r10=ApplyTransform(transform,*RemapXY(*p10,meta))

r11=ApplyTransform(transform,*RemapXY(*p11,meta))

s00=UnmapXYZ(*r00,meta)

s01=UnmapXYZ(*r01,meta)

s10=UnmapXYZ(*r10,meta)

s11=UnmapXYZ(*r11,meta)

TextureMapTriangle(draw,x0,y0,x1,y1,source,s00,s01,s10,p00,p01,p10)

TextureMapTriangle(draw,x0,y0,x1,y1,source,s10,s01,s11,p10,p01,p11)

print('Progress %d/%d'%(x,meta['splitCount']),flush=True)

image.save('temp/warped.jpg')

Oh, and you need texture mapped triangles? Python is terrible for that, there's no way to make it run fast.... Fine, here's one of those, just to get you started, but don't blame me if it's slow, this needs to be in OpenGL or something so you can run it on the GPU and apply proper gamma correction.

#TextureMapTriangle.py
def Left(p,a,b):
cross=(p[0]-a[0])*(b[1]-a[1])-(p[1]-a[1])*(b[0]-a[0])
return cross<0

def SampleMap(source,x,y,dx,dy):
if x<0:
x=0
if y<0:
y=0
if x>=source.width:
x=source.width-1
if y>=source.height:
y=source.height-1
return source.getpixel((x,y))


def TextureMapTriangle(draw,x0,y0,x1,y1,source,p0,p1,p2,uv0,uv1,uv2):
xy0=list(map(min,zip(p0,p1,p2)))
xy1=list(map(max,zip(p0,p1,p2)))

dx1=p1[0]-p0[0]
dy1=p1[1]-p0[1]
dx2=p2[0]-p0[0]
dy2=p2[1]-p0[1]
det=dx1*dy2-dx2*dy1
if xy0[0]<x0:
xy0[0]=x0
if xy0[1]<y0:
xy0[1]=y0
if xy1[0]>x1:
xy1[0]=x1
if xy1[1]>y1:
xy1[1]=y1

for x in range(math.floor(xy0[0]),math.ceil(xy1[0])):
for y in range(math.floor(xy0[1]),math.ceil(xy1[1])):
p=(x,y)
if Left(p,p0,p1):
continue
if Left(p,p1,p2):
continue
if Left(p,p2,p0):
continue

dx=x-p0[0]
dy=y-p0[1]
u=(dx*dy2-dy*dx2)/det
v=(-dx*dy1+dy*dx1)/det

uu=uv0[0]+u*(uv1[0]-uv0[0])+v*(uv2[0]-uv0[0])
vv=uv0[1]+u*(uv1[1]-uv0[1])+v*(uv2[1]-uv0[1])
c=SampleMap(source,uu,vv,1,1)
draw.point((x-x0,y-y0),tuple(c))

And then you could be like me, and license all of the above code under CC0. Yay!

Duplex

Duplex. That’s the technology at Google I/O 2018 where an AI agent can use the existing telephone network to call a restaurant, book a table for 4 at 7pm, and adapt to common problems.

Things get more interesting when the restaurant runs a similar service. AI talking to AI.

Whenever two learning AI’s get together, every single time, they develop a new language. One that us humans can’t understand.

I can imagine the following “conversation”: Alice, a digital assistant, is calling Bob, an AI agent for the restaurant.

  Alice and Bob together: Hi

  Alice: Umm, er, hmmm, yes?

  Bob: Table confirmed, 4 people, tonight at 7pm.

  Alice and Bob together: Bye

Lets slow that recording down and play it back again, annotated this time:

  Alice and Bob together: Hi

       Handshake protocol, are we both digital software? Yes we are.

  Alice: Umm, er, hmmm, yes?

       Translation: I’d like to book a table for 4 people anytime between 6pm and 9pm

  Bob: Table confirmed, 4 people, tonight at 7pm.
       Lets repeat everything for the recording the humans will review.

  Alice and Bob together: Bye

       Handshake protocol, confirm booking.

Are there new words the AI can teach us? More efficient grammatical structures? Can the AI teach us humans to communicate more effectively?

If there is, the AI won’t tell us.

Unless we know how to ask.

Basic Income, Better Living Through Video Games.

If we assume as given we'll eventually live in a society with a UBI (all eligible citizens receive an Unconditional Basic Income, enough to cover their food, clothing and shelter), then the most pressing question is: How should we roll it out?

Years of making Video Games suggest two quick answers:

The easy way is by lottery. Suppose Gary is a winner in the monthly UBI Lottery! Congrats Gary! Gary no longer has to deal with our mess of confusing taxation and welfare regulations. He wins a much simplified UBI and a flat tax. Of course, any change can be scary and difficult, so Gary also has the option to just stick with the old system if he wants.

More interesting is the notion of a Dual Currency. It's a little bit like enrolling in the food stamp program, where he's issued with tokens that can be exchanged for food items at a 1-1 ratio. In a food stamp program, those tokens would normally expire after a set period of time.

Food stamps are really old. Like, 1930's America old. We live in a digital world, so lets make those tokens work more like an energy mechanic in Candy Crush or League of Legends. Those tokens now accrue *continuously* rather than appearing all at once on a Thursday. We'll cap Gary's balance at a maximum of 1 months worth of tokens. Any balance more than 2 weeks of tokens would also have a penalty applied.

Finally pricing. Staples like bread, milk, laundry detergent and cleaning supplies will have a heavily discounted price when purchased using tokens. Healthy options like fruit and vegetables too. Fast food and chocolates might have a premium pricing attached. Lets make it easier for Gary to make good decisions.

Keeping our kids safe, with better level design and video games.

Our local bus stop used to have a safety problem. All the school kids would line up, frantic to be first on the bus.

The front kid would stand with their toes hanging over the curb. The next one behind them, peering over their shoulder, and so on and so forth... They would stand that way in pseudo-formation, for agonizing minutes at a time, as the cars zipped past on the morning commute. Finally the enormous school bus would swing in and stop mere centimeters away from the nose of the kid in front.

Just one tiny fumble, or even just one loud boisterous dog, could have spelled tragedy.

I spoke about it with the other Mums and Dads. I know from designing levels in video games that there's an easy fix we use for these kind of problems. I told them someone could simply paint a yellow “Do Not Cross” line on the ground, and the kids would naturally do the rest, even when the parents weren't around.

For the record, I've never defaced public property, nor would I encourage anyone else to do the same.

Yet some anonymous do-gooder has gone and done just that:

Vigilante safety engineering - a yellow "Do Not Cross" line has been painted at this local school bus stop by an anonymous parent, obviously over the concerns about child safety.

All the kids now line up a safe distance from the road, and the possibility of tragedy at our local bus stop has been dramatically reduced.

Well sure, this act of civil disobedience might not be able to protect the neighbourhood kids from the harmful rays of the sun, mindless advertising, unvaccinated kids or bad language... but at least now the kids at my local bus stop line up further away from the traffic.

If you have a concerns about traffic safety at your bus stop, here's one small thing that any anonymous do-gooder can do, that will actually make a difference, all thanks to better level design and video games.

Wi-Fi in Schools

A friend of mine asks :


Question : What's the effect on the human body, of 20 children in a classroom, each downloading a 3 minute youtube video over Wi-Fi?

An excellent question!

As with all good science, let's start with an experiment.  I happen to have a 3 minute HD video on my network, so I can time how long it takes to copy across to my laptop:

missingbytes:$ time copy /NetworkDrive/HDVideo.mp4 .
real   0m6.550s
user   0m0.001s
sys    0m0.116s

So a single 3 minute video (3:19 to be precise) will use about 6.5 seconds of Wi-Fi time to copy.

With 20 students, and rounding up a little to account for congestion..

... lets call it 200 seconds of Wi-Fi activity total.

Transmit power

The transmission power for Wi-Fi signals is heavily regulated in the EU, the US and also in New Zealand where I'm performing the test.

The maximum 2.4-GHz transmission power is regulated by law, so lets assume it's 20dBm = 100mW = 0.1W ( source )

As we all learnt when we were in school, a watt is a joule per second, so 200 seconds at 0.1W is 20J.

Now we know that a class room of children downloading a youtube video results in 20 joules of microwave energy being emitted from the Wi-Fi router's antenna.

A brief diversion : Ionizing and Non-Ionizing radiation

Electromagnetic radiation forms a spectrum, from low frequency and radio waves, up through the microwaves, visible light, X-rays and on to gamma rays which have very high frequencies indeed.

Those high frequencies are characterized as ionizing, they're very dangerous to humans and their ability to cause DNA damage and ultimately cancer is well known. This is the reason why we need to be so careful around medical/dental imaging devices, and need to take precautions such as wearing sunscreen and polarized sunglasses when we're outdoors on a sunny day.

It's not necessarily the amount of energy, it's more the frequency that's the problem.  This high frequency ionizing radiation quite literally has the ability to rip electrons off their atoms.  It's these "ions" which go on to cause damage to biological systems.

By contrast, the lower frequency non-ionizing radiation (such as used in Wi-Fi, or FM radio) doesn't have the same ability to affect us in this way.

By itself, non-ionizing radiation can only cause heating in biological systems. Indirectly, it's this heating which slows down or speeds up chemical reactions and/or signalling within the cell, and it's these secondary effects which has the potential to cause problems.

Intuitively, this is why the 1000 watt microwave oven in your kitchen makes food super hot in a few minutes using microwave energy, but it doesn't actually make your food radioactive.  (You'd need an X-Ray oven for that!)

Anyway, lets continue, we've got 20 joules remember?

Absorption

Now we need to make a pretty unrealistic assumption. Suppose that the entirety of those 20 joules of energy was somehow absorbed by one child.  Of course, this can't happen in the real world for two fairly obvious reasons:

• A router transmits energy in all directions.  For all the energy to be absorbed by the child, the router would somehow need to be inside the child.
• Microwave energy interacts only weakly with the human body.  That's one of the great benefits of Wi-Fi, it can pass right through walls and ceilings and straight through you and me.

But just for fun, lets continue on anyway and figure out what would happen if all of those 20 joules were absorbed by one child.

An average 6 year old child weighs about 22 kilograms.  (Of course, my 4 year old son also weighs 22 kilograms, but that's a blogpost for another day!)
The human body is about 65% water, so lets consider 14 kilograms of water.

The specific heat capacity of water is 4.18 J / gK

So we have 20 J / (14,000 g) / (4.18 J / gK) = 0.00034 K = 0.0004 °C
(That's 0.4 millikelvin for all you geeks out there.)

Answers!

So there we have it, even with a wildly exaggerated assumption:

Answer : A classroom of children, all downloading a 3 minute youtube clip over Wi-Fi yields a maximum biological heating due to 2.4GHz microwave radiation of 0.0004 °C.

(0.4 millikelvin is about twice as small as it's possible to measure using a precision thermometer.)

Conclusion

We shouldn't really be too surprised.  Wi-Fi signals are incredibly weak. Consider this, those 20 joules of microwave radiation is the same amount of chemical energy contained in one thousandth of a teaspoon of sugar.

There's no way to prove scientifically that microwave radiation from Wi-Fi is safe in the human body. Science doesn't work that way. You can't prove a negative.

But we can try and make smart choices about tiny risks.


For example, the exposure from a banana is about 0.1 μSv of harmful ionizing radiation because of their high quantities of naturally occurring radioactive potassium.

Yet who thinks twice about giving bananas to kids in schools?

Thoughts, questions or especially corrections?  Please feel free to leave a comment down below!

Praise the Fire Fighter, Damn the Safety Inspector

There's a sickness eating our industry.  It's a culture of Macho Programming.  In it's simplest form, it's the idea that if we just push harder, longer, stronger, then we will win.  Yet time and time again, experience shows that the way to win is by working smarter.

Side-effects

I was once working on a particular AAA title.  The game was running late.  We were in crunch, and had been for a while.  There was no end in sight.  I came across the following code:⁽¹⁾

bool DetectCollision(Vector3 location, float radius){
  ...
  radius * 1.2f;
  ...
}

So that line of code makes the collisions a bit fatter.  It's what we call a 'Fudge Factor' - we don't know why a problem is occurring, so we fudge the numbers a little until it works.

But take a closer look.  The statement as written has no side-effects.  It doesn't actually modify the value of radius.  When the programmer wrote:

  radius * 1.2f;

they intended to write:

  radius *= 1.2f;

Let's review the facts:

• It's the wrong fix to begin with (fudge factors are generally a bad idea)

• It doesn't actually change the behaviour of the running program

• The programmer didn't verify that their "fix" worked

And we can safely assume that the programmer didn't verify the original bug in the first place.

Compound Fail

It gets worse.  In this late stage of crunch, there were so many easily avoidable bugs coming in to the code, that the production team mandated every changelist required a second programmer to sign off.

That's right, not one, but two programmers, working together, managed to convince each other that this placebo changelist actually improved the game.  Together, they marked the bug as fixed and sent it back to QA, fully confident they had made the game better.

What other trivial mistakes did those programmers make that night?

What a colossal waste of time and resources, simply because those two programmers had inadequate sleep.  The project would have been much better off if those two programmers had just gone home at 18:00.  Or 17:00.  Or even 14:00.

[Edit: I just wanted to add, these are actually two really good programmers! I'd jump at the chance to have them on my team again.  The equation here is crunch + good programmers = too many careless mistakes.]

Praise The Fire Fighter ...

When you're deep in crunch, it's easy to see the heroic efforts, the mountains of caffeinated beverages, the change logs at 4am.  It's easy to point to the person who's working the hardest and say "We all need to be more like that guy."  Because when it's all falling apart, you need to do something.

(Hint: That something we need to do is to get more sleep.)

... Damn the Safety Inspector

And when you're at the beginning of the project, and the Safety Inspector is telling you that what you're building isn't up to code, that the schedules are unrealistic and will lead to crunch, slipped deadlines, hard-to-find bugs and adds unacceptable levels of risk to the project...  Well they're easy to dismiss "We're trying to build something here! Why are you trying to stop us?"

(Hint: The Safety Inspector is probably right.)

Macho Programming

As an industry, we should be working smarter than that. We should be rewarding measurable results and hard evidence, rather than effort and posturing.

To me, Macho Programming, is blundering onward in whichever way you possibly can, without regard to what's best for the project or the team, simply for the appearance of getting something done.

I think we can do better than that.  In the true Agile sense, as a team, we need to make the best decisions based on the best information we have, right now, and move forward in the best direction we can.

Who's with me?




⁽¹⁾ Some details have been changed to preserve anonymity.