locked
Bitmaps, Arrays and Maths RRS feed

  • Question

  • Hi,

     

    I need to find the maximum and minimum values in a bitmap in memory.

     

    The bitmap is 256x256 pixels 8-bit grayscale (so 1 pixel = 1 byte, and it is the Min and Max byte values I am after).

     

    My first question is, can a Bitmap in memory be considered simply as an array?

    If not, would it be better to convert it to an array first before performing any math calculations on it?

    I cannot seem to find any in-built Min and Max functions (that work on an array) in VB2005E, can someone confirm if they are present or not.

     

    If no Min or Max array functions are available, what is the best startegy for creating them? (e.g byte by byte, or row by row then column by column, or ...?)

     

    Many thanks

     

    Wibs

    Thursday, May 24, 2007 8:28 AM

Answers

  • I'm not sure which is faster, but the memory stream will hold the bitmap header as well as pixel data (and possibly a palette). So you would need to trim that off. Presumably there are two copy operations when using a stream: bitmap -> Stream -> array. Using Lockbits has just one copy operation.

    I think it always pads to the nearest 4 byte boundary. So if you had a 38 pixel wide image it would have a stride of 40 pixels. As you are 256 pixels wide (1 byte per pixel) it will not need padding (256 mod 4 = 0).

    It should be much faster to simply scan through the array and keep track of the max and min as you go, than to use Array.Sort.

    If you've learnt about Big O notation somewhere...

    Array.Sort uses the QuickSort algorithm. Wikipedia says it is on average O(nLog(n)).

    As we have n pixels, doing something like:

            Dim min As Byte = Byte.MaxValue
            Dim max As Byte = Byte.MinValue
            For i As Integer = 0 To bytes.Length - 1
                If bytes(i) > max Then
                    max = bytes(i)
                ElseIf bytes(i) < min Then
                    min = bytes(i)
                End If
            Next

    If we consider what happens when n is huge, it is going to take a time proportional to the size of bytes.length, in other words it is O(n). Which is more efficient than O(nlog(n))
    Thursday, May 24, 2007 12:55 PM

All replies

  • OK, had a think about this, and this is one solution I can think of. Any comments on this approach (or better approach)?

     

    Step 1: Convert bitmap to an array:

     

    Dim stream As MemoryStream = New MemoryStream
    Dim bitmap1Bytes As Byte()

    Dim bitmap1 As Bitmap = New Bitmap(256, 256)

    bitmap1.Save(stream, System.Drawing.Imaging.ImageFormat.Bmp)
    bitmap1Bytes = stream.ToArray

    stream.Close()
    bitmap.Dispose()

     

    Step 2: Sort Array, then look at first and last values

     

    Dim sortedBitmap1Bytes As Byte()

    Dim minByte As Byte

    Dim maxByte As Byte

    sortedBitmap1Bytes = Array.Sort (bitmap1Bytes)

    minByte = sortedBitmap1Bytes(0)

    maxByte = sortedBitmap1Bytes(sortedBitmap1Bytes.Length-1)

    Thursday, May 24, 2007 10:04 AM
  • Use lockbits to lock the bitmap in memory, and create a BitmapData object
    Use System.Runtime.InteropServices.Marshal.Copy to copy the data into a byte array. (it's much faster than calling ReadByte repeatedly).
    Unlock the bitmap.

    Watch for the row padding.

    Thursday, May 24, 2007 10:22 AM
  • Something like this jo0ls

     

    Private Sub BitmapToArray()

    Dim bitmap1 As New Bitmap("c:\terrain1.bmp")

    Dim rect As New Rectangle(0, 0, bitmap1.Width, bitmap1.Height)

    Dim bitmap1Data As System.Drawing.Imaging.BitmapData = bitmap1.LockBits(rect, Drawing.Imaging.ImageLockMode.ReadWrite, bitmap1.PixelFormat)

    Dim ptr As IntPtr = bitmap1Data.Scan0

    Dim bytes As Integer = bmp.Width * bmp.Height

    Dim pixelValues(bytes - 1) As Byte

    Dim bitmap1ByteArray As Byte()

    bitmap1ByteArray() = System.Runtime.InteropServices.Marshal.Copy(ptr, pixelValues, 0, bytes)

    bitmap1.UnlockBits(bitmap1Data)

    End Sub

     

    Can you elucidate on why Marshal.Copy is faster than Stream?

    As my image (always) is 256 x 256 pixels, 8-bit grayscale, and 256/32 is a whole number, I do not have to worry about padding, is that correct?

     

    Thanks again for the reply.

    </FONT
    Thursday, May 24, 2007 11:01 AM
  • I'm not sure which is faster, but the memory stream will hold the bitmap header as well as pixel data (and possibly a palette). So you would need to trim that off. Presumably there are two copy operations when using a stream: bitmap -> Stream -> array. Using Lockbits has just one copy operation.

    I think it always pads to the nearest 4 byte boundary. So if you had a 38 pixel wide image it would have a stride of 40 pixels. As you are 256 pixels wide (1 byte per pixel) it will not need padding (256 mod 4 = 0).

    It should be much faster to simply scan through the array and keep track of the max and min as you go, than to use Array.Sort.

    If you've learnt about Big O notation somewhere...

    Array.Sort uses the QuickSort algorithm. Wikipedia says it is on average O(nLog(n)).

    As we have n pixels, doing something like:

            Dim min As Byte = Byte.MaxValue
            Dim max As Byte = Byte.MinValue
            For i As Integer = 0 To bytes.Length - 1
                If bytes(i) > max Then
                    max = bytes(i)
                ElseIf bytes(i) < min Then
                    min = bytes(i)
                End If
            Next

    If we consider what happens when n is huge, it is going to take a time proportional to the size of bytes.length, in other words it is O(n). Which is more efficient than O(nlog(n))
    Thursday, May 24, 2007 12:55 PM
  • Ah, looking back at this...

    What format is the image to be exactly?

    8 bits per pixel, or
    8 bits per pixel Indexed?

    An indexed image has a palette that contains 32 bit color information. So in 8bpp greyscale indexed it would be 256 shades of grey. The pixel data stores the index in the palette that has the color for the pixel. Windows uses indexed colors for all 8 bit images!

    If you have indexed files, then at the moment you are just finding the max and min indexes in the palette, which can't be guarenteed to be the max and min colors. (They would tally if the palette was arranged logically from black to white...)

    If you have non-indexed files then you probably need to parse the header to find where the pixel data starts, and read it into an array... You need to know the format of the file. If .Net can load the file, (I don't know), then it might be translating it to another format, check the Pixelformat property of the bitmap.

    I forgot the System.Math.Max and Min functions.
    Saturday, May 26, 2007 11:53 AM
  • Hi Jo0ls,

    Now I am clearer about the problem I can rephrase the question more clearly. I have opened a bitmap file on disk, test.bmp, and loaded it into a byte array (I have now dispensed with a bitmap in memory idea). The file is always the same format, ie 256x256 pixels, 8-bit greyscale (so no padding is involved). The offset to the start of the pixel data is now also fixed at 1078 (0x0436). The number of bytes of pixel data is 256x256 = 65536 bytes.

    I want to search that part of the byte array, starting at the offset (1078) to the end of the array, and find the maximum and minimum size of bytes.


    Sunday, May 27, 2007 12:13 PM
  • What are you really trying to do?  If you tell us what you are trying to accomplish, there is probably an open source library that you can use to do the job. 

    Just finding the Max and Min could be complex if the index isn't ordered from smallest to largest.  Most programs would convert the indexed bitmap to a non-indexed 32 bpp bitmap to sort the array.

    Sunday, May 27, 2007 2:43 PM
  • Hi John,

    The application that I am working on is a terrain/heightfield generator/editor, in both 2D and 3D. Whereas most people think of an image stored as a bitmap in a file is just simply that, an image, myself and other virtual gamers see it as a data store. Basically a heightfield works like this: Imagine an excel spreadsheet, formatted so the cells are square rather than rectangular. Imagine also that there are 256 by 256 cells. Imagine further that each cell contains just one 8-bit byte, and the value of that byte represents the height of land, ie 00h to FFh represents land height from 0 to 256m high. We now have a unit of land that is 256m by 256m, and heights that range from 0 to 256m high. We now have a 3D representation of terrain (a landscape) in a 2D array. Several virtual worlds use this as their unit of land, but all use proprietory file formats. I am currently developing an application for Second Life, one of the biggest virtual worlds.

    The file format they use is a special variant of the RAW image format, i.e it is 256x256 pixels, 8-bit greyscale (terrain files do not use colour, it is the shade of grey that determines height), and 13 channels. The heightfield is contained in channel 1, and a heightfield multiplier in channel 2. Other channels determine water height, land use and various permissions.

    Just taking channel 1, the heightfield, it is very similar to a bitmap file (think *.bmp now, NOT VB memory  bitmaps). If you take an image that has been saved in *.bmp format, greyscale, 8-bit, 256x256 pixels, then it is exactly what is required, if you first strip off the Bitmap Header, the File Info header, and the colour table, then invert the pixel data (as the *.bmp format saves an image 'upside down').

    Up to now, the only program on the market that will allow you to open, edit and save 13 channel raw files is Adobe Photoshop, and Photoshop is not known for being cheap!

    My program will allow users to create a heighfield in ANY graphics program, such as Gimp or Paint.NET (even Windows Paint could do the job, at a pinch). They can create a new image in 256x256 pixel, 8-bit greyscale format, then paint the landscape using a brush, in shades of grey to achive stunning landscapes. The only problem is, they can only then save out that terrain file in standard *.bmp format, together with its files headers, colour table, etc. My program then takes over, it can load such a file, strip off the headers and colour table, invert the image to the correct way up, then add the other 12 channels, to finally create the required terrain.raw file.

    To answer your specific question, when creating heighfields it is important to know what the maximum and minimum heights of the land are, as the resolution of the final heights is a combination of the raw heightfield in channel 1 and the multiplier in channel 2.

    One of the information bars on my application shows the Maximum and Minimum heights for the terrain file currently loaded. To find out this information I simply need to go through the bytes in the pixel data (and in 8-bit greyscale each pixel is represented by just one 8-bit byte), and look for the largest and the smallest value bytes.

    Two ways have been suggested to me. One is to take the pixel data in a byte array (working with the data in a bitmap in memory was just too complicated for such a simple task), then  either sort the array, and look at the first and last value (simple, but very slow), or to do pairwise comparisons throughout the array.

    The second suggestion looks more promising, but was based on a bitmap in memory, rather than a byte array. I need therefore some tips on how to search through a byte array, starting from offset 1078 through to the end of the array, ending up with two bytes, baMax and baMin, representing the maximum and minimum byte values in the byte array.

    I hope this explains what I am really trying to do. As it is the last Sub to finish (on the input convert and display side), I wanted to avoid using any 3rd-party libraries, and learn by doing myself (but with the help from the knowledgeable folk in this forum of course). Once I have found these max and min values, I will then turn to the creation of the complete output file (the encoder) as I have already have created Subs that can create the other 12 channels.

    So, anybody, how to search a byte array (64Kb in size) and find the max and min values in that array, but fast?

    Wibs



    Sunday, May 27, 2007 9:06 PM
  • OK, just to confirm, Jo0ls answer was spot on. It found the max and min values almost instantly, the final code was this:

                    Dim baMin As Byte = 255
                    Dim baMax As Byte = 0
                    For i As Integer = 1078 To fileBytes.Length - 1
                        If fileBytes(i) > baMax Then
                            baMax = fileBytes(i)
                        ElseIf fileBytes(i) < baMin Then
                            baMin = fileBytes(i)
                        End If
                    Next
                    MsgBox("The minimum height = " & baMin.ToString & " metres" & vbCrLf & _
                    "The maximum height = " & baMax.ToString & " metres" )

    Wibs
    Sunday, May 27, 2007 9:41 PM