You might try this. It expects a reference to the raw string, and the width & height available in globals -- adapt to your preferences:

sub buk {
    my( $str ) = @_;

    my @b = map[ ( 1e99, 0 ) x 2 ], 1 .. 256; #$s-> max;

    my( $i, $x, $y, $c ) = 0;
    for my $c ( unpack 'C*', $$str ) {
        $x = $i % $WIDTH;
        $y = int( $i / $WIDTH );
        $b[ $c ][ LEFT   ] = $x if $x < $b[ $c ][ LEFT   ];
        $b[ $c ][ RIGHT  ] = $x if $x > $b[ $c ][ RIGHT  ];
        $b[ $c ][ TOP    ] = $y if $y < $b[ $c ][ TOP    ];
        $b[ $c ][ BOTTOM ] = $y if $y > $b[ $c ][ BOTTOM ];
        ++$i;
    }
    return \@b;
}
[download]

In my simulated tests, it performs 224 times faster than your posted code on a 1000x1000x1byte image and 1700 times faster on a 2000x2000:

C:\test>1176081 -WIDTH=999 -HEIGHT=999
yr() took 329.728896
buk() took 1.474515

C:\test>1176081 -WIDTH=2000 -HEIGHT=2000
yr() took 10265.728694
buk() took 5.976180
[download]

It is also trivially adaptable to images that use short/word/doubleword/quadword sized pixels.

I have a couple of ideas for a faster version, which I'll post if they pan out.