Archive for the ‘programming’ Category

Image registration with genetic algorithms, again


Given two images, we want to “reigster” them.

After resizing (pyramid, to speed-up the algorithm) and normalizing (to improve the registration) I’ve tried to find shift + rotation (3 degrees of freedom) using algorithms in matlab’s global optimization toolbox.

  • genetic-algorithm – results are good only if initial guess is good/ image offset is small, even with customized parameters.
  • Direct Search – very good results (but the offset is integer, for some reason)
  • Simulated Annealing – poor results

In all cases, the following function was used:

%try to make B similar to A
function a = cor(alfa1)
 global A B 
 global roi

 b1=imChange(B, alfa1);
 a1=imcrop(A, roi);
 a = 1-corr2(a1,b1);

%vector of form [offset-x, offset-y, angle]
function out = imChange(im, vector)
 global roi
 alfa = vector(3);
 offset = vector(1:2);
 B1=imrotate(im, alfa,'bicubic', 'crop');
 out=imcrop(B1, roi+[offset 0 0]);

Playing with Matlab


Image registration using ga (genetic algorithm)

Given two images, A and B, try to find affine transformation to maximize correlation between the to images.

This simple code works on simple images with simple transformations.

function res=reg1()
 clear all;
 close all;

 global A B


 options = gaoptimset('Generations',50);
 options = gaoptimset(options,'MutationFcn',@mutationadaptfeasible);
 options = gaoptimset(options,'PlotFcns',{@gaplotbestf,@gaplotmaxconstr}, 'Display','iter');
 options = gaoptimset(options,'InitialPopulation',[1 0 0 0 1 0]);
 [a,fval] = ga(ObjectiveFunction,6, options);

function a = cor(alfa)
 global A B
 alfa = reshape(alfa, 3, 2);
 t_n = maketform('affine', alfa);
 D = imtransform(A,t_n);
 D = imresize(D, size(B));

 a = 1-corr2(B, D);

convert 16 bit “half float” to 32 bit float


See also:
IEEE 754 single-precision binary floating-point format: binary32

16-bit Floating-Point Rules

float convert16to32float(unsigned int Xi_Value)
 //TODO:test, imporve, optimize..
  int exp = (Xi_Value>>10) & 0x01f;
  float g=0;
  unsigned int *i=(unsigned int *) & g;
  Xi_Value &= 0xffff;
  *i |= Xi_Value << 16 & 0x80000000; //sign
  *i |= (exp-15+127) << 23; //exponent 
  *i |= (Xi_Value & 0x3FF) << 13; //value
  return g;

copy DB from MS SQL to MYSQL


I’ve burned too much on this simple task, so I want to keep some gotchas it here.
The task: copy DB from MS SQL to MYSQL.


  • MySQL migrate — I couldn’t make it work.
  • — seem to be OK, but demo version is limited, so I’m not sure. Full version – $50.
  • bcp – command line tool; it was extremely difficult (yet possible) to export to a file that MySQL can eat.


dbcDataAdapter l_SourceDA = new OdbcDataAdapter(l_QuerySource, m_strSource);
        OdbcDataAdapter l_TargetDA = new OdbcDataAdapter(l_QueryTarget, m_strTarget);
        OdbcCommandBuilder cmb = new OdbcCommandBuilder(l_TargetDA); //mandatory! Even if I don't use cmb, this line is crucial as in creates INSERT command
        string l_TableName = cmb.QuoteIdentifier(Xi_TableName, m_cTarget);

        DataSet l_SourceDS = new DataSet();
        DataSet l_TargetDS = new DataSet();
        int l_Rows = l_SourceDA.Fill(l_SourceDS, Xi_TableName);
        if (l_Rows <= 0)
          Log("Empty table");
        l_TargetDA.Fill(l_TargetDS, l_TableName);

        DataTable l_tblSource = l_SourceDS.Tables[Xi_TableName];
        DataTable l_tblTarget = l_TargetDS.Tables[l_TableName];

        int l_Errors = 0;
        // Loop through the top five rows, and write the first column to the screen.
        foreach (DataRow l_r in l_tblSource.Rows)
            l_tblTarget.Rows[l_tblTarget.Rows.Count - 1].SetAdded();
          catch (OdbcException ex)
        Log(string.Format("table {0}: {1} errors out of {2} records",
          Xi_TableName, l_Errors, l_Rows));
        DataSet l_Changed = l_TargetDS.GetChanges();

This is OK; but I needed support for tables with dash (“-“).
This was much harder; this thread was useful.
So two changes that fix it:

   //create command
    OdbcCommand cmdInsert = cmb.GetInsertCommand();
        cmdInsert.CommandText = cmdInsert.CommandText.ToLower().Replace(Xi_TableName.ToLower(), "`" + Xi_TableName + "`");
//MSSQL use "[" and "]"; there are prefix/postfix fields somehere in the data adapter

//instead of just updating target data set:
 OdbcDataAdapter l_NewTargetDA = new OdbcDataAdapter(l_TargetDA.SelectCommand);
        l_NewTargetDA.TableMappings.Add("Table", l_TableName);
        l_NewTargetDA.InsertCommand = cmdInsert;

Hopefully this will be useful for someone.

One more HLSL trick


When implementing a quite complex pixel shader on pixel shader for multi-cascade shadows maps on shader model 2.0, I’d got a usual error message saying that “Arithmetic instruction limit of 64 exceeded“, so once again I have to find an instruction slot.

I had a code that tries to find the best shadow map for current pixel, something like:

//float2 map[] is a u/v pair; if it is "inside" the texture, I can use it
if (map[0].x < 0 || map[0].x > 1 ||
    map[0].y < 0 || map[0].y > 1)

This code was converted to:

//float2 map[] is a u/v pair; if it is "inside" the texture, I can use it
if( any (map[0]-saturate(map[0] ) ) )

This takes much less instructions, so now I have some free slots!



Q: In Visual Studio, how to set conditional breakpoint on -1.#IND000000000000 ?

 vairable == -1.#IND000000000000//this cannot work, of course


vairable != vairable

More productive programming


(inspired by 10 best tricks of fooling myself to work and Create more productive environment at your desk)

  1. Drink a good tea constantly.
    it helps to concentrate. I recommend Pu-erh or Oolong)
  2. Drink a your tea with no sugar.
    not only it tastes much better (this is the only reasonable way to drink a tea), but also when it is accidentally  spilled on a keyboard, the keyboard is recoverable, and the keys do not stick. Thus you will be significantly more productive than somebody who drinks tea/coffee  with sugar (or Pepsi or whatever)
  3. Keep your browser closed; get updates using RSS readers.
    I personally had been spending  a lot of time  checking news sites/ /. / HN /Merriam-Webster’s Word of the Day/German word of the day/ Wikipedia watch list  etc.  each time “the code is compiling”, and then continue to surf. Now RSS saves me a lot of time.
  4. Ask a co-worker for help, if you are stuck on a problem more than 30 minutes.
    usually, you will find the solution even before you finish explaining him the issue. If not, you give him a chance to solve your problem and fill genius.
  5. Use Ginkgo biloba, if you still feel dumb.
    I don’t know whether it’ effect is fully Psychosomatic or not, but it helps.

HLSL trick #2


Saving some expensive instruction in shader model 2…
(Trick #1 is described here)

Instead of, e. g.,

float getTotalDiffuse()
 float l1 = getDiffuse(g_light1);
 float l2 = getDiffuse(g_light2);
 float l3 = getDiffuse(g_light3);
 float l4 = getDiffuse(g_light4);
 return l1+l2+l3+l4;


float getTotalDiffuse()
 float4 l = {getDiffuse(g_light1),
 return dot (l, float4(1,1,1,1));

The trick is that sometimes if you want to sum some floats (or vectors), it may be cheaper to use dot product with vector (1, … , 1)

HLSL trick


If you write a HLSL Shader Model 2 you know you are limited to 32 const registers. Here is a trick that helped me to save one.

Suppose you want to write in pixel shader:

 float4x4 l_Color=
      tex2D(samTex0, In.Tex0),
      tex2D(samTex1, In.Tex1),
      tex2D(samTex2, In.Tex2),
      tex2D(samTex3, In.Tex3)
   l_Color[g_BlendLayer] = foo(l_Color[g_BlendLayer]); 
   //OOPS! illegal syntax
   out.Color = combine (Color);

But you cannot write in ShaderModel 2 “array[index] = blah“.

Second try:

  float4 blended = foo(l_Color[g_BlendLayer]);
   switch (BlendLayer)
      case 0: l_Color[0] = blended; break;
      case 1: l_Color[1] = blended; break;
      case 2: l_Color[2] = blended; break;
      case 3: l_Color[3] = blended; break;
   //OOPS! illegal syntax

Of course, there is no switch/case in ShaderModel 2…

  float4 blended = foo(l_Color[g_BlendLayer]);
   switch (BlendLayer)
      case 0: l_Color[0] = blended; break;
      case 1: l_Color[1] = blended; break;
      case 2: l_Color[2] = blended; break;
      case 3: l_Color[3] = blended; break;
   //OOPS! illegal syntax

Same problem: “array[index] = blah“.

  float4 blended = foo(l_Color[g_BlendLayer]);
  if (0 == BlendLayer) l_Color[0] = blended; else
  if (1 == BlendLayer) l_Color[1] = blended; else
  if (2 == BlendLayer) l_Color[2] = blended; else
  if (3 == BlendLayer) l_Color[3] = blended; 
   //OOPS! Too bad

Although this code is syntactically correct, it is wrong: condition are bad, and nested ifs are even worse (just look on disassembly). Too much instructions.

  float4 blended = foo(l_Color[g_BlendLayer]);
  if (0 == BlendLayer) l_Color[0] = blended; 
  if (1 == BlendLayer) l_Color[1] = blended; 
  if (2 == BlendLayer) l_Color[2] = blended; 
  if (3 == BlendLayer) l_Color[3] = blended; 
   //Much better!

This code (same as previous, but without “else”s, is much better. But still, I get “error X5589: Invalid const register num: 32. Max allowed is 31.”

  float4 blended = foo(l_Color[g_BlendLayer]);
  if (0 == BlendLayer--) l_Color[0] = blended; 
  if (0 == BlendLayer--) l_Color[1] = blended; 
  if (0 == BlendLayer--) l_Color[2] = blended; 
  if (0 == BlendLayer--) l_Color[3] = blended; 
   //It works!

Learning the assembly code really helps.
Here is how you get .asm files from your HLSL shaders,
using Microsoft’s fxc tool:

fxc /Gfp /Zi /T ps_2_0 /Fc out.asm l:\efx\mini.fx /E PS_Test

or, to get nice HTML:

fxc /Gfp /Zi /T ps_2_0 /Cc /Fc out.asm.html l:\efx\mini.fx /E PS_Test



Playing with JavaScript.

There are ten matchsticks. You must move the matches such that there are 5 crossed pairs of them. Each turn you can move one matchstick over exactly two other matchsticks. (crossed matchsticks are considered as two!)
10-matchsticks puzzle