posted December 27, 2003 06:32 AM            

For an algorithm which compresses bitmap data by reducing unneccessary bit depth,
and handling similar pixels following each other, I need to write an array of BITs.
I need to write various data, for example:

1 bit (indicating if similar pixels a following)
if set - number of similar pixels, may be a 6-7 bit number
rest - depending on bit depth (from 1 to 24 bit, may also be 3 bit or 6 bit) - actual
pixel color value.

What's the fastest way to write this? I thought of writing into a byte array first and then
shifting the bits into the right position, but I'm sure that there are better and faster
solutions?

Suggestions of any kind are greatly appreciated.

Regards

posted December 27, 2003 08:07 AM            

I guess you have two diferent questions here..
a) how to set graphic pixels fastest
b) how to set bit in memory fastest

first... the screen data is buffered... while you can set a pixel
on the screen... it is not mirrored in the screen's memoryDC.. so
for what Chris calls persistence, you need to set (or also set) the
pixel in the bufferDC's and refresh (invalidate) the screen for the
data to stay changed...

the fastest way to manipulate data in the DC... depends on where the data is
(or is coming from)... if you are using bitmaps..using DIB's are the fastest
way that I know of...

Borje, has a great example (search for dibSection).. or try this one:

'MESSAGE http://www.powerbasic.com/support/forums/Forum7/HTML/001910.html
'FORUM: Source Code
'TOPIC: DibSection Circle FAST!!!!

but it also seems like you want to make your own img format...
I believe.. you will still have to (convert to bmp) fill a bmp in
order to be able to move the data from the memory to the screen or
printer, using the windows functions...

how to set bit in memory fastest? I want to know also...
but I know it takes some overhead setting up where the data is going
and where the data is coming from first

maybe better post after I get some coffee

Brad

posted December 27, 2003 09:47 AM            

thanks for your reply.

I have spent the last days thinking of a compression algorithm and
I have developed (most parts in my head so far) my own algorithm, based
on the following things:

(This is related to http://www.powerbasic.com/support/forums/Forum4/HTML/009750.html)

* Dividing the screen into small rectangles
* Since the data is "streaming", one screenshot following each other, only sending
pixels / rectangles which changed in content
* Optionally, reducing color depth to 15-bit (3x5 bit RGB)
* Compressing by using a palette - the palette is built dynamically in memory, but
palette compressing is dropped as soon as a certain number of entries is reached.
* Further decreasing bit depth of each pixel when a palette is used - for example, if
there are four palette entries (different colors in one rectangle), only use 2 bits for
each pixel
* Compressing by detecting duplicates / similar pixels following each other
* Perhaps JPEG compression for certain regions of the screen (for faster transmission of
"pictures" like wallpaper or other things)

For that, I need to write into an array of bits. My output of the first compression pass will
look like this:

BT = 1 BYTE: Bit depth of the value following
VL = 4 BYTES: Long integer value
etc etc.

So I need to write the (BT) number of bits from VL into the output buffer, at the current bit position,
and this as fast as possible.

Regards

------------------

posted December 27, 2003 10:18 AM            

I want to add the value 10 (1010) to a bit array at position 20.
Which is faster?

BitArray = BitArray + value * 2^20

Or - setting the bits manually with BIT statements and functions?

Or - any other suggestions?

Regards

posted December 27, 2003 09:58 PM            

havn't had time to run tests which I want to do anyway.. but think
about this... no-matter what you do..you will still need to put ht
file into bitmap to get it onto the screen... the hardware it set up
to read from DC to DC fast.. (thru DMA?? I think??) anyway, if you
use a dib... then you set the data in the loaded bitmap dirrectly
instead of setting bits in another array and then loading it into the dc..
so... I doubt you will get faster than dibs w/o other hardware???

most dib examples use pointers, but maybe BIT SET, or !mov, might be
quicker???

??
Brad

posted December 28, 2003 03:18 AM            

Thanks for your reply.

You misunderstood me - I'm reading a bitmap out of the screen DC, and then
compress the bitmap in order to transmit it via the internet. On the other
side it is decompressed and converted into a bitmap again, before it is dislpayed.

The bit thing is only for compression, it doesn't have anything to do with device
contexts etc.

Best Regards

posted December 28, 2003 03:51 AM            

From what you are describing it sounds like you are trying to replicate RLE encoding.

There are a number of sources for this as this is the standard compression built into the BMP file format.

Here is one that may help... http://netghost.narod.ru/gff/graphics/summary/os2bmp.htm

That said, RLE is not a very good compressor unless your graphic is composed of large blocks of EXACTLY the same
color. In fact, it could increase the size of file in some cases were there are very few runs of similar colors.

posted December 28, 2003 08:40 AM            

Here is something that could help you.
It is very fast at performing colors count.

Note: the BitmapColorCount does use in input a standard
bitmap handle that it converts on the fly into DIB.

#INCLUDE "WIN32API.INC"
'
FUNCTION BitmapColorCount& (BYVAL hBmp&) 
'
    REGISTER x&, y&
'    
    LOCAL bm AS BITMAP
    LOCAL bi AS BITMAPINFO
    LOCAL dwp AS DWORD PTR
'
    DIM C(524287) AS LONG ' 524287 * 8 bits = room for 16777216 colors
'
    IF hBmp& = 0 THEN EXIT FUNCTION
'    
    CALL GetObject(hBmp&, SIZEOF(bm), bm)
    pWidth& = bm.bmWidth: pHeight& = bm.bmHeight
'
    hIC& = CreateIC ("DISPLAY", BYVAL 0&, BYVAL 0&, BYVAL 0&)
'
    hMem1DC& = CreateCompatibleDC(hIC&)
    hMem2DC& = CreateCompatibleDC(hIC&)
    hTmpBmp& = CreateCompatibleBitmap(hIC&, pWidth&, pHeight&)
'    
    CALL SelectObject(hMem1DC&, hBmp&)
'
    CALL SelectObject(hMem2DC&, hTmpBmp&)
    CALL BitBlt(hMem2DC&, 0, 0, pWidth&, pHeight&, hMem1DC&, 0, 0, %SRCCOPY)
'
    bi.bmiHeader.biSize = SIZEOF(bi.bmiHeader)
    bi.bmiHeader.biWidth = pWidth&
    bi.bmiHeader.biHeight = pHeight&
    bi.bmiHeader.biPlanes = 1
    bi.bmiHeader.biBitCount = 32
    bi.bmiHeader.biCompression = %BI_RGB
'
    hToDIB& = CreateDIBSection(hMem1DC&, bi, %DIB_RGB_COLORS, 0, 0, 0)
'
    CALL SelectObject(hMem1DC&, hToDIB&)
    CALL GetObject(hToDIB&, SIZEOF(bm), bm)
    CALL BitBlt(hMem1DC&, 0, 0, pWidth&, pHeight&, hMem2DC&, 0, 0, %SRCCOPY)
'
'   'DIM pBits AS BYTE PTR
'   'pBits = bm.bmBits
    dwp  = bm.bmBits
    FOR Y& = pHeight& - 1 TO 0 STEP - 1
       FOR X& = 0 TO pWidth& - 1
' 
           'Colr& = RGB(@pBits[2], @pBits[1], @pBits[0])
           'IF BIT(C(0), Colr&) = 0 THEN BIT SET C(0), Colr&: INCR ColorCount&
           'pBits = pBits + 4
'           
           IF BIT(C(0), @dwp) = 0 THEN BIT SET C(0), @dwp: INCR ColorCount&
           dwp = dwp + 4
       NEXT
    NEXT
'
    CALL DeleteDC(hMem1DC&)
    CALL DeleteDC(hMem2DC&)
    CALL DeleteDC(hIC&)
    CALL DeleteObject(hTmpBmp&)
    CALL DeleteObject(hToDIB&)
'
    FUNCTION = ColorCount&
'
END FUNCTION
'
FUNCTION PBMAIN
'
    FileToLoad$ = "d:\zmp350\zmbwlp.bmp"
   'FileToLoad$ = "d:\zmp350\billes.bmp"
'
    hBmp& = LoadImage(BYVAL 0&, (FileToLoad$), %IMAGE_BITMAP, 0, 0, %LR_LOADFROMFILE)
    IF hBmp& THEN
       ColorCount& = BitmapColorCount(hBmp&)
       MSGBOX STR$(ColorCount&)
       CALL DeleteObject(hBmp&)
    END IF
'
END FUNCTION

posted December 28, 2003 09:24 AM            

Patrice, thanks for the code. That's very helpful, I'm already thinking of a fast way
to build a color table. I'll write in PB and later translate parts to ASM.

George, I don't know about compression formats, but I'm thinking of a good
way to compress a screenshot - nothing more. A typical screenshot would be the
PowerBasic website, inside an Internet Explorer window etc.

You can see, if you take a single block / rectangle on the screen, let's say which
contains the first few characters of a link (e.g. 30x30 pixels), the single rectangle
usually does not contain more than 4 different colors.

So, without loss of quality, a 3-Byte-Value could be converted into a 2-Bit-Value. This
means that we only need 1/12 of space / bandwith (for that particular rectangle).

Things are getting complicated when pictures like wallpapers are transmitted, but you can
turn that off.

Of course I'm open to other suggestions relating the best compression for a screen shot.

I thought of the GIF format but it seems to be limited to 256 colors. That's enough for remote
control, but the program should also be used for remote presentations etc.

Still one question remains open - if I write e.g. 2-Bit-Values into a bit array, what's the fastest
way? Using BIT SET, or value = value + 2^offset * addvalue ?

Best Regards

------------------

posted December 28, 2003 09:39 AM            

It sounds like you are reinventing MPEG. They do similar stuff

1. Divide the image into squares called macro blocks - (16x16 I think)
2. Run a transform on that area to reduce the byte count, the numbers plugged into the transform determine the quality of the resulting decompressed image.
3. Only save into the final file the macro blocks that change, but keep some kind of marker to tell the decompressor what to use from the previous frame
4. RLE the final mess to scrunch it down a bit more.

Of course I'm over simplifying the whole process by a lot. There are software encoders and decoders available out there. I don't know if any are open source or free.

Another compression method that produces a much more pleasing result is Wavelets. You might want to do a google search and see what's out there.

Russ Srole

posted December 28, 2003 10:02 AM            

<<what's the fastest way? Using BIT SET, or value = value + 2^offset * addvalue ?>>
<<I'll write in PB and later translate parts to ASM>>

Since you're happy to move to ASM eventually then you should use the BIT SET version as it can later be translated into the BTS opcode which is bound to be faster as it's a single ASM opcode which sets a bit in an array.

e.g.

'for PBwin7.02
#COMPILE EXE
#REGISTER NONE
FUNCTION PBMAIN
DIM a&(1000)
BIT SET a&(0),321       'set bit 321 = 10th word (each 32 bits), 1st bit
MSGBOX STR$(a&(10))     'show that it worked
 
c&=VARPTR(a&(0))        'get address of data
!mov ecx,c&             'point to data
!mov eax, 322           'we're going to set bit 322 i.e 10th word, bit 2 (=10*32bits+2=322)
!bts [ecx], eax         'set the bit
 
MSGBOX STR$(a&(10))     'show that it worked
 
END FUNCTION 

posted December 28, 2003 11:11 AM            

here's a quick time test templete:

BTW, PB Functions are "HARD TO BEAT!!!"

#COMPILE EXE
#INCLUDE "WIN32API.INC"
FUNCTION PBMAIN() AS LONG
  DIM t1 AS QUAD ,t2 AS QUAD ,t3 AS QUAD ,t4 AS QUAD ,t5 AS QUAD ,t6 AS QUAD
  DIM count AS LONG , i&
  DIM Dat(3) AS DWORD
    DIM offstBit&
    offstBit = 5
    MSGBOX "start"
'run BIT SET Proc
   QueryPerformanceCounter t1
    FOR count = 1 TO 50000
        BIT SET Dat(0),offstBit
    NEXT count
  QueryPerformanceCounter t2
'make DatStr0$ just to display that data is correct
    DIM DatStr0$
    FOR i = 0 TO 31
        DatStr0 = DatStr0 + STR$(BIT(Dat(0),i))+","
    NEXT
  MSGBOX "BIT SET Proc: "+ $CRLF + $CRLF +_
  "DatStr0$ :" + $CRLF + DatStr0 + $CRLF + $CRLF +_
  "BIT SET time : " + (FORMAT$(t2-t1,"#0.00000"))
'run 2^offst Proc
    DIM value???
    QueryPerformanceCounter t3
    FOR count = 1 TO 50000
       value = Dat(1) + 2^offstBit*1
    NEXT count
    QueryPerformanceCounter t4
'make DatStr1$ just to display that data is correct
    DIM DatStr1$
    FOR i = 0 TO 31
        DatStr1 = DatStr1 + STR$(BIT(value,i))+","
    NEXT
  MSGBOX "2^offst Proc: "+ $CRLF + $CRLF +_
  "DatStr1$ :" + $CRLF + DatStr1 + $CRLF + $CRLF +_
  "2^offst time : " + (FORMAT$(t4-t3,"#0.00000"))

'run Paul's !bts Proc
    DIM valuePtr AS DWORD PTR
    QueryPerformanceCounter t5
    FOR count = 1 TO 50000
        valuePtr = VARPTR(Dat(2))
        ! mov ecx, valuePtr
        ! mov eax, offstBit
        ! bts [ecx], eax
    NEXT count
    QueryPerformanceCounter t6
'make DatStr0$ just to display that data is correct
    DIM DatStr2$
    FOR i = 0 TO 31
        DatStr2 = DatStr2 + STR$(BIT(Dat(2),i))+","
    NEXT
  MSGBOX "Paul's !bts Proc: "+ $CRLF + $CRLF +_
  "DatStr2$ :" + $CRLF + DatStr2 + $CRLF + $CRLF +_
  "Paul's !bts time : " + (FORMAT$(t6-t5,"#0.00000"))+ $CRLF +_
  "BIT SET time : " + (FORMAT$(t2-t1,"#0.00000"))+ $CRLF +_
  "2^offst time : " + (FORMAT$(t4-t3,"#0.00000"))
END FUNCTION

------------------
Wash DC Area
Borje's "Poff's" is likely the BEST tool for learning PB.. http://www.tolkenxp.com/pb

posted December 29, 2003 02:20 PM            

Compression is compression. If you have some data to compress,
it doesn't matter if the 1s and 0s represent a digital image or
a data file. I would suggest trying some of the well known
compression algorithms that are already available in PB code.
Check out Wayne's Crypto Archives to find
an organized list of compression (and decompression) algorithms.

posted January 03, 2004 01:58 AM            

Bern, I hate to dissagree, but compression of data and compression of images can be quite different. Data can not be lossless, one tossed bit and it's completely useless. Images, on the other hand, might sustain quite a lot of "lossy" compression and still be useful.

For instance, in television signals, various forms of compression are used very often, from YUV 422 (luminance sampled twice as often as color) to JPEG, MPEG and now JPEG-2000 (wavelets). It's the same on the web. Again in the TV game we have contribution quality (low or no compression) and distrabution quality (some, to really way too much compression). The main point is that the untrained human eye is not really all that particular about certain things and can be happily fooled. The rule is that the luminence component (the black & white part) is more important then the color part, so if you convert a picture to a HSL type code and the compress the HS part, you can get a nice result even though when you convert it back, some colors won't be there, but they'll be "rounded" to other similar colors. This method is used all the time (YUV), in fact it's so common that even some TV folks don't think of it as compression.

At any rate, by itself, this sort of trick won't buy Lother near enough for what he wants to do & he'll need to resort to other, more sophisticated methods. Smaller Animals has some JPEG-2000 routines in one of their packages.
http://www.smalleranimals.com/isource/saj2k.htm

I haven't played with it, but if I need mess with this kind of thing, that's where I'm going to start. The licence is only about $40, which seems like a great deal to me.

Russ Srole