如何优化此图像“边缘检测”算法？

Question

我有一个函数，给定一个具有透明背景和未知对象的图像，找到对象的顶部，左侧，右侧和底部边界。目的是让我可以在对象的边界周围画一个盒子。我不是想要检测物体的实际边缘 - 只是最上方，最下方等。

我的功能运行良好，但速度很慢，因为它扫描图像中的每个像素。

我的问题是：是否有一种更快，更有效的方法来检测图像中使用库存PHP/GD功能的最上方，最左侧，最右侧和最底部的不透明像素？

有一个影响选项的问题：图像中的对象可能具有透明部分。例如，如果它是一个非填充形状的图像。

public static function getObjectBoundaries($image) 
{ 
    // this code looks for the first non white/transparent pixel 
    // from the top, left, right and bottom 

    $imageInfo = array(); 
    $imageInfo['width'] = imagesx($image); 
    $imageInfo['height'] = imagesy($image); 

    $imageInfo['topBoundary'] = $imageInfo['height']; 
    $imageInfo['bottomBoundary'] = 0; 
    $imageInfo['leftBoundary'] = $imageInfo['width']; 
    $imageInfo['rightBoundary'] = 0; 

    for ($x = 0; $x <= $imageInfo['width'] - 1; $x++) { 
     for ($y = 0; $y <= $imageInfo['height'] - 1; $y++) { 
      $pixelColor = imagecolorat($image, $x, $y); 
      if ($pixelColor != 2130706432) {  // if not white/transparent 
       $imageInfo['topBoundary'] = min($y, $imageInfo['topBoundary']); 
       $imageInfo['bottomBoundary'] = max($y, $imageInfo['bottomBoundary']); 
       $imageInfo['leftBoundary'] = min($x, $imageInfo['leftBoundary']); 
       $imageInfo['rightBoundary'] = max($x, $imageInfo['rightBoundary']); 
      } 
     } 
    } 

    return $imageInfo; 
} 

Answer 1

我想你可以测试4个方面之一一后，一旦像素被发现停止。 对于顶部边界（未测试的代码）：

// false so we can test it's value 
$bound_top = false; 
// The 2 loops have 2 end conditions, if end of row/line, or pixel found 
// Loop from top to bottom 
for ($y = 0; $y < $img_height && $bound_top === false; $y++) { 
    // Loop from left to right (right to left would work to) 
    for ($x = 0; $x < $img_width && $bound_top === false; $x++) { 
     if (imageColorAt($img, $x, $y) != 2130706432) { 
      $bound_top = $y; 
     } 
    } 
} 

环路后，如果$bound_top仍然false，不用检查另一侧，你检查所有像素，图像是空的。如果没有，那么就为其他方面做同样的事情。

Answer 2

不是每个像素都需要检查。以下代码从左到右检查列以获得leftBoundary，从右到左获取右边界，从上到下的行（同时排除我们已检查过的像素）以获得topBoundary，对于bottomBoundary也是如此。

function get_boundary($image) 
{ 
    $imageInfo = array(); 
    $imageInfo['width'] = imagesx($image); 
    $imageInfo['height'] = imagesy($image); 

    for ($x = 0; $x < $imageInfo['width']; $x++) { 
     if (!is_box_empty($image, $x, 0, 1, $imageInfo['height'])) { 
      $imageInfo['leftBoundary'] = $x; 
      break; 
     } 
    } 

    for ($x = $imageInfo['width']-1; $x >= 0; $x--) { 
     if (!is_box_empty($image, $x, 0, 1, $imageInfo['height'])) { 
      $imageInfo['rightBoundary'] = $x; 
      break; 
     } 
    } 

    for ($y = 0; $y < $imageInfo['height']; $y++) { 
     if (!is_box_empty($image, $imageInfo['leftBoundary'], $y, $imageInfo['rightBoundary']-$imageInfo['leftBoundary']+1, 1)) { 
      $imageInfo['topBoundary'] = $y; 
      break; 
     } 
    } 

    for ($y = $imageInfo['height']-1; $y >= 0; $y--) { 
     if (!is_box_empty($image, $imageInfo['leftBoundary'], $y, $imageInfo['rightBoundary']-$imageInfo['leftBoundary']+1, 1)) { 
      $imageInfo['bottomBoundary'] = $y; 
      break; 
     } 
    } 

    return $imageInfo; 
} 

function is_box_empty($image, $x, $y, $w, $h) 
{ 
    for ($i = $x; $i < $x+$w; $i++) { 
     for ($j = $y; $j < $y+$h; $j++) { 
      $pixelColor = imagecolorat($image, $i, $j); 
      if ($pixelColor != 2130706432) {  // if not white/transparent 
       return false; 
      } 
     } 
    } 

    return true; 
} 

Answer 3

PHP中的函数调用非常昂贵。调用每个像素的imagecolorat（）将绝对损坏性能。 PHP中的高效编码意味着找到可以以某种方式完成这项工作的内置函数。以下代码使用调色板GD函数。一目了然，它可能并不直观，但逻辑实际上非常简单：代码一直在复制图像一行像素，直到它注意到它需要多种颜色来表示它们。

function getObjectBoundaries2($image) { 
    $width = imagesx($image); 
    $height = imagesy($image); 

    // create a one-pixel high image that uses a PALETTE 
    $line = imagecreate($width, 1); 
    for($y = 0; $y < $height; $y++) { 
     // copy a row of pixels into $line 
     imagecopy($line, $image, 0, 0, 0, $y, $width, 1); 

     // count the number of colors in $line 
     // if it's one, then assume it's the transparent color 
     $count = imagecolorstotal($line); 
     if($count > 1) { 
      // okay, $line has employed more than one color so something's there 
      // look at the first color in the palette to ensure that our initial 
      // assumption was correct 
      $firstColor = imagecolorsforindex($line, 0); 
      if($firstColor['alpha'] == 127) { 
       $top = $y; 
      } else { 
       // it was not--the first color encountered was opaque 
       $top = 0; 
      } 
      break; 
     } 
    } 

    if(!isset($top)) { 
     // image is completely empty 
     return array('width' => $width, 'height' => $height); 
    } 

    // do the same thing from the bottom 
    $line = imagecreate($width, 1); 
    for($y = $height - 1; $y > $top; $y--) { 
     imagecopy($line, $image, 0, 0, 0, $y, $width, 1); 
     $count = imagecolorstotal($line); 
     if($count > 1) { 
      $firstColor = imagecolorsforindex($line, 0); 
      if($firstColor['alpha'] == 127) { 
       $bottom = $y; 
      } else { 
       $bottom = $height - 1; 
      } 
      break; 
     } 
    } 
    $nonTransparentHeight = $bottom - $top + 1; 

    // scan from the left, ignoring top and bottom parts known to be transparent 
    $line = imagecreate(1, $nonTransparentHeight); 
    for($x = 0; $x < $width; $x++) { 
     imagecopy($line, $image, 0, 0, $x, $top, 1, $nonTransparentHeight); 
     $count = imagecolorstotal($line); 
     if($count > 1) { 
      $firstColor = imagecolorsforindex($line, 0); 
      if($firstColor['alpha'] == 127) { 
       $left = $x; 
      } else { 
       $left = 0; 
      } 
      break; 
     } 
    } 

    // scan from the right 
    $line = imagecreate(1, $nonTransparentHeight); 
    for($x = $width - 1; $x > $left; $x--) { 
     imagecopy($line, $image, 0, 0, $x, $top, 1, $nonTransparentHeight); 
     $count = imagecolorstotal($line); 
     if($count > 1) { 
      $firstColor = imagecolorsforindex($line, 0); 
      if($firstColor['alpha'] == 127) { 
       $right = $x; 
      } else { 
       $right = $width - 1; 
      } 
      break; 
     } 
    } 

    return array('width' => $width, 'height' => $height, 'topBoundary' => $top, 'bottomBoundary' => $bottom, 'leftBoundary' => $left, 'rightBoundary' => $right); 
}