Thanks a lot for your time and interest. I had to rewrite the loop in "buk3" like this: 
for my $y ( 0 .. $HEIGHT-1 ) {
    my $s = substr( $$str, $y * $WIDTH, $WIDTH );
    while( $s =~ m[(([^\0])+)]g ) {
        my $c = ord($1); #, $-[0], $+[0];
        $b[ $c ][ LEFT   ] = $-[0]   if $-[0]   < $b[ $c ][ LEFT   ];
        $b[ $c ][ RIGHT  ] = $+[0]-1 if $+[0]-1 > $b[ $c ][ RIGHT  ];
        $b[ $c ][ TOP    ] = $y      if      $y < $b[ $c ][ TOP    ];
        $b[ $c ][ BOTTOM ] = $y      if      $y > $b[ $c ][ BOTTOM ];
    }
}

[download]
Otherwise it goes forever. We can't match globally against substr (as lvalue?), can we? When I run your code (5.24 on Windows), it says: 
yr() took 3.484375
buk() took 1.233143
buk2() took 0.670660
buk3() took 0.029448

[download]
I.e. no hundreds of seconds, for my sub, at all. I would not otherwise publish it here and call it 'fast' :) Also, your test 'image' is something interesting, we can look at it if: 
PDL::IO::Image-> new_from_pdl( 
    pdl([ unpack 'C*', $pdl ])
        -> reshape( 1000, 1000 )-> bitnot
)-> save( 'buk.png', 'PNG' );

[download]
Not exactly representative as real life image. For typical real image it's this: 
PDL: Short D [7616,1200]
max = 145

       s/iter unpack   buk2  regex   buk3
unpack   3.02     --    -6%   -36%   -88%
buk2     2.84     6%     --   -32%   -87%
regex    1.92    57%    48%     --   -81%
buk3    0.362   733%   684%   430%     --

[download]
Anyway, your "buk3" algorithm is fastest.

In reply to Re^4: PDL: Looking for efficient way to extract sub-images, by finding bounding boxes of "objects" (7000x faster) by vr
in thread PDL: Looking for efficient way to extract sub-images, by finding bounding boxes of "objects" by vr

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.