Sorry for the delay in getting back to you. I've adapted your technique somewhat:

sub eily{
    my $str = shift;
    my @b = map[ ( 1e99, 0 ) x 2 ], 1 .. 256;

    for my $y ( 0 .. $HEIGHT-1 ) {
        my $s = \substr( $$str, $y * $WIDTH, $WIDTH );
        my $t = ' ' . $$s ^ $$s;
        chop $t;
        while( $t  =~ m[[^\0]\0*]g ) {
            my $c = ord substr $$s, $-[0], 1; #, $-[0], $+[0];
            $b[ $c ][ LEFT   ] = $-[0]   if  $-[0]    < $b[ $c ][ LEFT
+   ];
            $b[ $c ][ RIGHT  ] = $+[0]-1 if  $+[0]-1  > $b[ $c ][ RIGH
+T  ];
            $b[ $c ][ TOP    ] = $y      if        $y < $b[ $c ][ TOP 
+   ];
            $b[ $c ][ BOTTOM ] = $y      if        $y > $b[ $c ][ BOTT
+OM ];
        }
    }
    return \@b;
}
[download]

and the results are impressive:

C:\test>\perl22\bin\perl 1176081.pl -WIDTH=10000 -HEIGHT=10000
yr() took 12.478694
buk3() took 8.195635
dave() took 1.876719
eily took 0.888511

C:\test>\perl22\bin\perl 1176081.pl -WIDTH=20000 -HEIGHT=20000
yr() took 18.774189
buk3() took 32.063918
dave() took 5.701784
eily took 2.409520
[download]