如何優化此圖像「邊緣檢測」算法？

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); 
}