C# - 이미지의 경계 찾기 (크기가 아님)

Question

이미지 격자를 균등하게 분할하고 이미지의 중심을 유사도에 따라 정렬하는 응용 프로그램을 개발 중입니다. 지금까지는 작은 크기의 이미지 격자를 수정할 수 있었지만 큰 "스프라이트"크기 (예를 들어 100x100)를 시도 할 때마다 Stack Overflow 오류가 발생합니다.

예 재귀를 사용하고 있지만 픽셀을 선택할 때마다 목록이 채워질 때까지 불투명도를 설정하여 목록을 복사하고 목록으로 복사 한 다음 나머지를 검사합니다 (모든 방향으로). 그리드의 이미지. 나는 이것이 각 호출 이후로 가장 좋은 방법인지 확실하지 않다. 나는 같은 방법을 7 번 호출한다. (체크되지 않은 7 개의 인접한 픽셀이 있다고 가정한다.) 체크 할 픽셀이 없을 때까지. 그리드의 다음 이미지로 이동할 수 있습니다.

오류가 발생하기 시작한 곳을 추적하려고했는데, 더 많거나 적은 1600 픽셀을 확인하고 목록에 추가 한 후였습니다. MyPixel 4 개 변수를 포함하는 클래스이다 : X (INT), Y (INT), 색 (색상), 및 선택 (BOOL)

public void processSprite(int i, int j) 
    { 
     //OOO 
     //OXO 
     //OOO 
     pixeltemp.Add(new MyPixel(imap.pixels[i, j].x, imap.pixels[i, j].y, imap.pixels[i, j].color)); 
     imap.pixels[i, j].read = true; 
     //OOO 
     //OOX 
     //OOO 
     try 
     { 
      if (!imap.pixels[i + 1, j].read) 
      { 
       if (imap.pixels[i + 1, j].color.A == 0) //Found a Border 
       { 
        imap.pixels[i + 1, j].read = true; 
       } 
       else 
       { 
        processSprite(i + 1, j); 
       } 
      } 
     } 
     //... (code goes on) 
    } 

• pixeltemp 이미지를 보유 화소의 임시리스트이다 (List<MyPixel>)
• IMAP은 전체 이미지 (List<MyPixel>)

내 응용 프로그램은 단지 16메가바이트 상판 정도 걸립니다 이후에 메모리 문제가없는 것 같아요 포함되어 있습니다.

무한 재귀가 아니라면 왜 내 "스택 오버플로"오류가 발생합니까? 이 작업을 수행하는 더 쉬운 방법이 있습니까? 제 코드가보기 흉한 것처럼 보입니다. 어떻게 코드를 더 잘 만들지 모릅니다.

미리 감사드립니다.

Answer 1

스택 오버플로는 무한 재귀가 아니라 프로세스가 처리 할 수있는 것보다 많은 재귀 (또는 호출 스택)로 인해 발생합니다. 귀하의 경우 processSprite에 대한 각각의 재귀 호출은 processSprite에 대한 동일한 수의 재귀 호출을 수행 할 것입니다. 경계를 찾는없이 1600 픽셀의 최악의 시나리오에 그래서, 통화 나무 같을 것이다 :

 
    processSprite(0, j) 
    processSprite(1, j) 
     processSprite(2, j) 
     ... 
      processSprite(1599, j) <-- That's 1600 call frames, 
            enough for an overflow. 

당신은 깊이 우선 검색을하는 선형 루프 알고리즘을 재구성 할 것

, 출발점에 가장 근접한 픽셀을 찾고 싶다면 나선형 패턴을 사용하면됩니다. 이미 다른 사람들이 이미이 문제를 해결하기 위해 개발 한 다른 스파이 알고리즘이 있다고 확신합니다.

편집 :

나는 지금보다 나은 당신이 해결하려는 문제를 이해하고 생각합니다. 0 알파 픽셀로 둘러싸인 여러 이미지 타일을 포함 할 수있는 이미지가있는 것처럼 들리며이 타일 각각에 대해 경계 사각형을 찾고 싶습니다. 그게 해결할 흥미로운 문제처럼 보였으므로, 구현했습니다 :

IEnumerable<Rectangle> FindImageTiles(Bitmap compositeImage) 
{ 
    var result = new List<Rectangle>(); 

    // Scan for a non-empty region that hasn't already been "captured" 
    for (var x = 0; x < compositeImage.Width; x++) 
    { 
     for (var y = 0; y < compositeImage.Height; y++) 
     { 
      // Only process the pixel if we don't have a rectangle that 
      // already contains this and if it's not empty 
      if (!result.Any(r => r.Contains(x, y)) 
       && compositeImage.GetPixel(x, y).A != 0) 
      { 
       // Now that we've found a point, create a rectangle 
       // surrounding that point, then expand outward until 
       // we have a bounding rectangle that doesn't intersect 
       // with the tile 
       var rect = new Rectangle(x - 1, y - 1, 2, 2); 
       bool foundBounds = false; 
       while (!foundBounds) 
       { 
        var xRange = Enumerable.Range(rect.Left, rect.Right) 
         .Where(px => px >= 0 && px < compositeImage.Width); 
        var yRange = Enumerable.Range(rect.Top, rect.Bottom) 
         .Where(py => py >= 0 && py < compositeImage.Height); 

        // Adjust the top 
        if (rect.Top >= 0 
         && xRange 
          .Select(bx => compositeImage.GetPixel(bx, rect.Top)) 
          .Any(p => p.A != 0)) 
        { 
         rect.Y--; 
         rect.Height++; 
        } 
        else if (rect.Bottom < compositeImage.Height 
         && xRange 
          .Select(bx => compositeImage.GetPixel(bx, rect.Bottom)) 
          .Any(p => p.A != 0)) 
        { 
         rect.Height++; 
        } 
        else if (rect.Left >= 0 
         && yRange 
          .Select(by => compositeImage.GetPixel(rect.Left, by)) 
          .Any(p => p.A != 0)) 
        { 
         rect.X--; 
         rect.Width++; 
        } 
        else if (rect.Right < compositeImage.Width 
         && yRange 
          .Select(by => compositeImage.GetPixel(rect.Right, by)) 
          .Any(p => p.A != 0)) 
        { 
         rect.Width++; 
        } 
        else 
        { 
         foundBounds = true; 
        } 
       } 
       result.Add(rect); 
      } 
     } 
    } 

    return result; 
}