c++ - ビットマップ境界長方形アルゴリズムC++

Question

現在、ビットマップピクセルデータをcharの配列に格納しています。画像のバウンディングボックスに基づいて画像を切り抜くのに最も効果的なアルゴリズムは何でしょうか。

以下に、達成したいことの比較的正確な例を示します。ベースの「ピクセルカラー」に基づいています。

バウンディングボックスの例

Answer 1

総当りでも問題ありませんがStretchBlt、水平方向と垂直方向の射影を計算するために加速を使用すると、より良い結果が得られます。

ビットマップを取得し、高さ 1 ピクセル、全幅の長方形に描画します。

ビットマップを取得し、幅 1 ピクセル、高さいっぱいの長方形に描画します。

どちらも画像全体を処理する必要がありますが、高度に並列な GPU アクセラレーション レンダリングを使用して処理します。

これらから境界を計算します。

列全体の平均が正確に背景色である場合、結果にエラーが発生する可能性があります。

Answer 2

夜のナイスゲーム！ありがとうございました！このブルート フォースを実行する C# コードをすばやく作成しました。

public class Dimensions
{
    public int left = 0;
    public int right = 0;
    public int top = 0;
    public int bottom = 0;
}

public class ImageDetection
{
    private const int xSize = 2000;
    private const int ySize = 2000;

    private const int xMin = 1800;
    private const int yMin = 1800;
    private const int defaultPixelColor = 0;


    public void GetArray(out char[,] arr)
    {
        arr = new char[xSize, ySize];
        Random rand = new Random();

        for (int i=0; i<xSize; ++i)
        {
            for (int j=0; j<ySize; ++j)
            {
                var d = rand.NextDouble();

                if (d < 0.5)
                {
                    arr[i, j] = Convert.ToChar(defaultPixelColor);
                }
                else
                {
                    int theInt = Convert.ToInt32(255 * d);
                    arr[i, j] = Convert.ToChar(theInt);
                }
            }
        }

        // cut top
        for (int k = 0; k < (xSize - xMin); k++)
        {
            for (int l = 0; l < ySize; l++)
            {
                arr[k, l] = Convert.ToChar(defaultPixelColor);
            }
        }

        // cut bottom
        for (int k = xMin; k < xSize; k++)
        {
            for (int l = 0; l < ySize; l++)
            {
                arr[k, l] = Convert.ToChar(defaultPixelColor);
            }
        }

        // cut left
        for (int k = 0; k < xSize; k++)
        {
            for (int l = 0; l < (ySize - xMin); l++)
            {
                arr[k, l] = Convert.ToChar(defaultPixelColor);
            }
        }

        // cut right 
        for (int k = 0; k < xSize; k++)
        {
            for (int l = xMin; l < ySize; l++)
            {
                arr[k, l] = Convert.ToChar(defaultPixelColor);
            }
        }

    }

    public void WriteArr(ref char[,] arr)
    {
        char[] line = new char[xSize];

        // all lines
        for (int i=0; i<ySize; ++i)
        {
            // build one line
            for (int j = 0; j < xSize; ++j)
            {
                char curChar = arr[i, j];

                if (curChar == '\0')
                {
                    line[j] = '.';
                }
                else
                {
                    line[j] = curChar;
                }
            }

            string s = new string(line);
            s += "\r\n";
            //FileIO.WriteFileText
            System.IO.File.AppendAllText("Matrix.txt", s);
         }
    }

    public void DetectSize(ref char[,] arr, out Dimensions dim)
    {
        dim = new Dimensions();

        dim.left = xSize;
        dim.top = ySize;
        dim.right = 0;
        dim.bottom = 0;

        for (int i = 0; i < xSize; ++i)
        {
            for (int j = 0; j < ySize; ++j)
            {
                if (!arr[i, j].Equals(Convert.ToChar(defaultPixelColor)))
                {
                    if (i < dim.left)
                    {
                        dim.left = i;
                    }

                    if (j < dim.top)
                    {
                        dim.top = j;
                    }

                    if (i > dim.right)
                    {
                        dim.right = i;
                    }

                    if (j > dim.bottom)
                    {
                        dim.bottom = j;
                    }
                }
            }
        }
    }
}

Answer 3

さて、既知の入力形式 (つまり、背景とのコントラストが高い画像内の円のみ) を使用した非常に単純なものの場合、非常に簡単に総当たり攻撃を行うことができます。画像データをループして、これらのコントラストの違いを探すだけです。一番上、一番左、一番右、一番下の位置を保存すれば完了です。

画像がそのような単純な形式でない場合は、ブロブ検出アルゴリズムなど、より高度なものが必要になり ます。

編集：参考までに、私はこのブルートフォースアルゴリズムを書いて、少し前に非常に似たようなことをしました。シンプルでメソッドは明確なはずですが、完璧にはほど遠いし、高度に最適化されているわけでもありません。すべてをここに投稿します (私をあまり厳しく判断しないでください。私は数年前に C# を独学していたときに書きました)。このアルゴリズムは、強度のしきい値を使用して円を見つけます (コントラストとは対照的に、私の入力は非常に明確に定義されていました)。

/// <summary>
/// Locates the spot of light on the image and returns an AnalysisResults object.
/// </summary>        
unsafe private Rectangle AnalyzeImage( )
{
    // function assumes 24bpp RGB format
    Bitmap image = m_originalImage;
    if ( image.PixelFormat != PixelFormat.Format24bppRgb )
    {
        throw new ArgumentException( "Image format must be 24bpp RGB" );
    }

    // using the GDI+ GetPixel method is too slow for a 
    // 1280x1024 image, so get directly at the image buffer instead.                    
    GraphicsUnit unit = GraphicsUnit.Pixel;
    imageRect = Rectangle.Truncate( image.GetBounds( ref unit ) );                

    BitmapData data = image.LockBits( imageRect, ImageLockMode.ReadWrite, image.PixelFormat );

    int intensityThreshold = IntensityThreshold;
    // initialize 'top' to -1 so that we can check if it has been set before setting it.
    // once a valid value for 'top' is found we don't need to set it again.
    int top = -1;

    // search for the left point starting at a high value so that we can simply
    // pull it towards the left as we find pixels inside of the spot.
    int left = imageRect.Right;
    int bottom = 0;
    int right = 0;

    // locate the circle in the image by finding pixels with average
    // intesity values above the threshold and then performing
    // some edge checks to set the top, left, right, and bottom values.
    int height = imageRect.Height + imageRect.Y;
    int width = imageRect.Width + imageRect.X;
    byte* pSrc = ( byte* ) data.Scan0;

    int rowOffset = 1;            
    for ( int y = imageRect.Y ; y < height ; ++y, ++rowOffset )
    {
        for ( int x = imageRect.X ; x < width ; ++x )
        {
            // windows stores images in memory in reverse byte order ( BGR )
            byte b = *pSrc++;
            byte g = *pSrc++;
            byte r = *pSrc++;                    

            // get the average intensity and see if it is above the threshold
            int intensity = GetIntensity( r, g, b );
            if ( intensity > intensityThreshold )
            {
                if ( !StrayPixel( pSrc, data, intensityThreshold ) )
                {
                    // found a point in the circle
                    if ( top == -1 ) top = y;
                    if ( x < left ) left = x;
                    if ( y > bottom ) bottom = y;
                    if ( x > right ) right = x;
                }
            }                    
        }

        // next row
        pSrc = ( ( byte* ) data.Scan0 ) + ( rowOffset * data.Stride );
    }

    image.UnlockBits( data );            

    // bounding rectangle of our spot
    return Rectangle.FromLTRB( left, top, right, bottom );
}                   

/// <summary>
/// Returns true if the pixel at (x,y) is surrounded in four 
/// directions by pixels that are below the specified intesity threshold.
/// This method only checks the first pixel above, below, left, and right
/// of the location currently pointed to by 'pSrc'.
/// </summary>        
private unsafe bool StrayPixel( byte* pSrc, BitmapData data, int intensityThreshold )
{
    // this method uses raw pointers instead of GetPixel because
    // the original image is locked and this is the only way to get at the data.

    // if we have a pixel with a relatively high saturation 
    // value we can safely assume that it is a camera artifact.
    if ( Color.FromArgb( pSrc[ 2 ], pSrc[ 1 ], *pSrc ).GetSaturation( ) > MAX_PIXEL_SAT )
    {
        return true;
    }

    byte* pAbove = pSrc - data.Stride;
    int above = GetIntensity( pAbove[ 2 ], pAbove[ 1 ], *pAbove );

    byte* pRight = pSrc + 3;
    int right = GetIntensity( pRight[ 2 ], pRight[ 1 ], *pRight );

    byte* pBelow = pSrc + data.Stride;
    int below = GetIntensity( pBelow[ 2 ], pBelow[ 1 ], *pBelow );

    byte* pLeft = pSrc - 3;
    int left = GetIntensity( pLeft[ 2 ], pLeft[ 1 ], *pLeft );

    // if all of the surrounding pixels are below the threshold we have found a stray
    return above < intensityThreshold &&
           right < intensityThreshold &&
           below < intensityThreshold &&
           left  < intensityThreshold;
}

/// <summary>
/// Returns the average of ( r, g, b )
/// </summary>  
private int GetIntensity( byte r, byte g, byte b )
{
    return GetIntensity( Color.FromArgb( r, g, b ) );
}

/// <summary>
/// Returns the average of ( c.r, c.g, c.b )
/// </summary>
private int GetIntensity( Color c )
{
    return ( c.R + c.G + c.B ) / 3;
}