Overlapping Images

[Troy Lundin]

I need to overlap two images. When overlapped at the correct point, the overlapped portion of both images match exactly (or very closely).

Now, I have tried to match the color of each pixel in the images, then move one image a bit and match them again until I get a high match rate, usually 95% or higher. The issue is, this is ridiculously slow. Also, I can't find a way to check the pixels if one I need to check a negative co-ordinate.

Here is what I have tried. It's totally wrong, but I have been poking at it for days.

        For y As Int32 = 0 To bmp2.Height Step 4
            If y + StartPos.Y >= bmp1.Height Then Exit For
            For x As Int32 = 0 To bmp2.Width Step 4
                If x + StartPos.X >= bmp1.Width Then Exit For
                C1 = bmp1.GetPixel(x + StartPos.X, y + StartPos.Y)
                C2 = bmp2.GetPixel(x, y)

                If C1 = C2 Then match += 1
            Next
        Next

[Niya]

Do not use GetPixel for this, it is notoriously slow. Instead use Bitmap.LockBits and read the bits from the BitmapData object that LockBits returns.

[Troy Lundin]

This is what I have so far. I am only searching eight pixels from each border. it is much faster, but still too slow to perform in real time. I guess I need a better algorithm to predict which side of the image will be updated so I can search only that side. I am still cheesing it quite a bit.

    Friend Sub Search()

        ' Get the start time.
        time = Date.Now

        ' Lock the bits for reading.
        bmpDataA = bmpA.LockBits(New Rectangle(LastPosition, New Size(240 + Math.Abs(SearchDistance), 160 + Math.Abs(SearchDistance))), ImageLockMode.ReadOnly, PixelFormat.Format32bppPArgb)
        bmpDataB = bmpB.LockBits(New Rectangle(0, 0, 240, 160), ImageLockMode.ReadOnly, PixelFormat.Format32bppPArgb)

        ' Search each overlapping pixel/
        For y As Int32 = SearchDistance * -1 To SearchDistance Step 1
            For x As Int32 = SearchDistance * -1 To SearchDistance Step 1

                ' Set total and reset match.
                total = (240 - Math.Abs(x)) * (160 - Math.Abs(y))
                match = 0

                ' Get pixel data.
                For y1 As Int32 = 0 + LastPosition.Y To 160 + LastPosition.Y - Math.Abs(y) - 1
                    For x1 As Int32 = 0 + LastPosition.X To 240 + LastPosition.X - Math.Abs(x) - 1

                        Select Case True
                            Case x < 0 AndAlso y < 0
                                ofsA = (bmpDataA.Stride * y1) + (4 * x1)
                                ofsB = (bmpDataB.Stride * (y1 + Math.Abs(y))) + (4 * (x1 + Math.Abs(x)))
                            Case x < 0
                                ofsA = (bmpDataA.Stride * (y1 + y)) + (4 * x1)
                                ofsB = (bmpDataB.Stride * y1) + (4 * (x1 + Math.Abs(x)))
                            Case y < 0
                                ofsA = (bmpDataA.Stride * y1) + (4 * (x1 + x))
                                ofsB = (bmpDataB.Stride * (y1 + Math.Abs(y))) + (4 * x1)
                            Case Else
                                ofsA = (bmpDataA.Stride * (y1 + y)) + (4 * (x1 + x))
                                ofsB = (bmpDataB.Stride * y1) + (4 * x1)
                        End Select

                        ' Compare pixels.
                        If Marshal.ReadInt32(bmpDataA.Scan0, ofsA) = Marshal.ReadInt32(bmpDataB.Scan0, ofsB) Then
                            match += 1
                        End If
                    Next
                Next

                ' Check match percent. If match is found...
                If (match / total) * 100 >= GoodMatch Then

                    ' Unlock the bits for drawing.
                    bmpA.UnlockBits(bmpDataA)
                    bmpB.UnlockBits(bmpDataB)

                    ' Draw the new image to the canvas.
                    Using g = Graphics.FromImage(bmpA)
                        g.DrawImage(bmpB, LastPosition.X + x, LastPosition.Y + y)
                    End Using

                    ' Update the last good position.
                    LastPosition = New Point(Math.Max(LastPosition.X + x, 0), Math.Max(LastPosition.Y + y, 0))

                    ' Update the picturebox.
                    PictureBox1.Invalidate()

                    Exit Sub
                End If
                ' [DEBUG] Show progress in title bar.
                SetText(Me, x.ToString.PadLeft(4) & ", " & y.ToString.PadLeft(4))
                Application.DoEvents()
            Next
        Next
        bmpA.UnlockBits(bmpDataA)
        bmpB.UnlockBits(bmpDataB)
    End Sub

[Niya]

Well perhaps you could implement this function in a C++ Dll and define the function with arguments to take the pointer from the BmpData structure, the stride and the image's height. C++ can do stuff like this lightning fast.

What exactly are you doing with the two images ?

[namrekka]

The process of finding an image in an image is called "Image Cross Correlation". I can tell you that that is not an easy task. A fast way is 2D FFT correlation. Hmmm......

http://paulbourke.net/miscellaneous/correlate/

http://www.dspguide.com/ch24/6.htm

An other thing is that such methods will not say true or false. You need a multi stage detection process to refine.

[Niya]

The process of finding an image in an image is called "Image Cross Correlation". I can tell you that that is not an easy task. A fast way is 2D FFT correlation. Hmmm......

http://paulbourke.net/miscellaneous/correlate/

http://www.dspguide.com/ch24/6.htm

An other thing is that such methods will not say true or false. You need a multi stage detection process to refine.

Whoa thats hardcore. I had no idea that this is what he wanted to do.