I am trying to use a TI C6x IMGLIB routine to low-pass filter an
image. This routine expects the input parameters to be in Q15 format
which I must not understand correctly, and would like some assistance
with.
Ok, so my 3x3 kernel (in floating point form) is quite simple, merely:
1/9 1/9 1/9
1/9 1/9 1/9
1/9 1/9 1/9
To convert to Q15 format, I 1st need to ensure that the coeffs are
within the range [-1, 1], which is clearly not a problem here. Since
1/9*2^15 = 3640.89, my 3x3 kernel in Q15 format is now:
3640 3640 3640
3640 3640 3640
3640 3640 3640
The TI routine (IMG_corr_gen, but that is not important) expects the
pixel data to be in Q15 format as well. So what I do is normalize my
8-bit pixels by dividing each pixel by 255 and then multiplying by
32768. So if my original 8x8 image was:
64 2 3 61 60 6 7 57
9 55 54 12 13 51 50 16
17 47 46 20 21 43 42 24
40 26 27 37 36 30 31 33
32 34 35 29 28 38 39 25
41 23 22 44 45 19 18 48
49 15 14 52 53 11 10 56
8 58 59 5 4 62 63 1
In Q15 format, after dividing by 255 and multiplying by 2^15, it's
now:
8224 257 385 7838 7710 771 899 7324
1156 7067 6939 1542 1670 6553 6425 2056
2184 6039 5911 2570 2698 5525 5397 3084
5140 3341 3469 4754 4626 3855 3983 4240
4112 4369 4497 3726 3598 4883 5011 3212
5268 2955 2827 5654 5782 2441 2313 6168
6296 1927 1799 6682 6810 1413 1285 7196
1028 7453 7581 642 514 7967 8095 128
Consider what happens with the pixel in the 2nd row and 2nd column
(7076) - basically during the low-pass filtering operation what occurs
is:
p(2,2) = 8224(3640)+257(3640)+385(3640)+1156(3640)+7067(3640)+6939(3640)+2184(3640)+6039(3640)+5911(3640)
This # is huge, and overflow will take over. Clearly I'm missing
something quite fundamental here, with regards to translating a rather
simple signal processing algorithm into a fixed-point implementation.
Do I even need to convert my original pixels by multiplying by 32768?
Even still, I would still end up with intermediate values greater than
what a Q30 accumulator could accomodate.
Any assisstance would be greatly appreciated. All of the fixed point
TI coding examples I have found on the web or in various books involve
IIR or FIR filters that filter sinusoidal signals, which by their very
nature already lie within the range [-1,1]. I have been unable to
find on the web an adequate image processing fixed-point example in C
(preferably using TI DSPs).
Shehrzad
2D correlation in Q15 fixed-point format
Started by ●April 18, 2004
Reply by ●April 18, 20042004-04-18
Shehrzad wrote:> I am trying to use a TI C6x IMGLIB routine to low-pass filter an > image. This routine expects the input parameters to be in Q15 format > which I must not understand correctly, and would like some assistance > with. > > Ok, so my 3x3 kernel (in floating point form) is quite simple, merely: > > 1/9 1/9 1/9 > 1/9 1/9 1/9 > 1/9 1/9 1/9 > > To convert to Q15 format, I 1st need to ensure that the coeffs are > within the range [-1, 1], which is clearly not a problem here. Since > 1/9*2^15 = 3640.89, my 3x3 kernel in Q15 format is now: > > 3640 3640 3640 > 3640 3640 3640 > 3640 3640 3640 > > The TI routine (IMG_corr_gen, but that is not important) expects the > pixel data to be in Q15 format as well. So what I do is normalize my > 8-bit pixels by dividing each pixel by 255 and then multiplying by > 32768. So if my original 8x8 image was: > > 64 2 3 61 60 6 7 57 > 9 55 54 12 13 51 50 16 > 17 47 46 20 21 43 42 24 > 40 26 27 37 36 30 31 33 > 32 34 35 29 28 38 39 25 > 41 23 22 44 45 19 18 48 > 49 15 14 52 53 11 10 56 > 8 58 59 5 4 62 63 1 > > In Q15 format, after dividing by 255 and multiplying by 2^15, it's > now: > > 8224 257 385 7838 7710 771 899 7324 > 1156 7067 6939 1542 1670 6553 6425 2056 > 2184 6039 5911 2570 2698 5525 5397 3084 > 5140 3341 3469 4754 4626 3855 3983 4240 > 4112 4369 4497 3726 3598 4883 5011 3212 > 5268 2955 2827 5654 5782 2441 2313 6168 > 6296 1927 1799 6682 6810 1413 1285 7196 > 1028 7453 7581 642 514 7967 8095 128 > > Consider what happens with the pixel in the 2nd row and 2nd column > (7076) - basically during the low-pass filtering operation what occurs > is: > > p(2,2) = 8224(3640)+257(3640)+385(3640)+1156(3640)+7067(3640)+6939(3640)+2184(3640)+6039(3640)+5911(3640) > > This # is huge, and overflow will take over. Clearly I'm missing > something quite fundamental here, with regards to translating a rather > simple signal processing algorithm into a fixed-point implementation. > Do I even need to convert my original pixels by multiplying by 32768? > Even still, I would still end up with intermediate values greater than > what a Q30 accumulator could accomodate. > > Any assisstance would be greatly appreciated. All of the fixed point > TI coding examples I have found on the web or in various books involve > IIR or FIR filters that filter sinusoidal signals, which by their very > nature already lie within the range [-1,1]. I have been unable to > find on the web an adequate image processing fixed-point example in C > (preferably using TI DSPs). > > ShehrzadThe chip is set up to do Q15 math automatically, so in effect you're not multiplying (8224)(3640), etc., you're multiplying (0.251)(0.111). There will also be a mechanism to prevent overflow from a series of MAC operations, but with your kernel you shouldn't have to worry. I wouldn't normalize by dividing by 255 then multiplying by 32768, I'd normalize by dividing by 256 then multiplying by 32768 -- because then you're just shifting up by 8 bits, and you can do it way fast, or just arrange your hardware so the data appears that way in the first place. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●April 19, 20042004-04-19
Thank you very much Tim!
Your explanation makes sense, and indeed I wrote a little program on
my TI C6701 to aid in my understanding. The TI function I wish to use
expects signed 16-bit integers (shorts), so I wrote a little test
function to simulate what I think that function would be doing. My
function, as written below, should compute the average pixel value of
my "image" [64 2 3;9 55 54;17 47 46] (to borrow MATLAB notation):
short test_lowpass_filter()
{
short pixels[] = {64,2,3,9,55,54,17,47,46};
short h[] = {3640,3640,3640,3640,3640,3640,3640,3640,3640}; // 1/9 *
2^15
int ii, prod, acc=0;
short output;
for (ii=0; ii<9; ++ii)
pixels[ii] <<=8; // convert to Q.15 fmt: div by 256 & mult by
32768
// fir filter
for (ii=0; ii<9; ++ii) {
prod = (h[ii]*pixels[ii]); // perform Q.15 mult
acc += prod; // update 32-bit accumulator
}
output = (short) (acc>>15); // cast output to 16 bits
return output;
}
Sure enough, upon return 'output' is 8445 which when shifted right by
8 bits is 32 (the mean of the data in 'pixels' is 33). Then I
replaced pixels with the following:
short pixels[] = {215,171,173,133,213,96,51,5,212}; // avg = 141
This did not work, as when you shift 215 left by 8 bits you end up
with a negative number. Changing all of the shorts to unsigned shorts
does mitigate the problem (upon return the unsigned short's value is
36087, which when shifted left by 8 bits is 140).
So if I could bother you again, what shall I do here? It may be the
case that TI's IMGLIB function does something different than what I
have "reverse engineered" above, but it would seem to me that if their
function is expecting signed 16-bit integers than I need to scale my
data differently. Perhaps instead of thinking of the range 0-255 I
need to think of my pixels as being normalized to within the range
-128 to +127?
Thanks in advance,
Shehrzad
Reply by ●April 19, 20042004-04-19
Shehrzad wrote:> Thank you very much Tim! > > Your explanation makes sense, and indeed I wrote a little program on > my TI C6701 to aid in my understanding. The TI function I wish to use > expects signed 16-bit integers (shorts), so I wrote a little test > function to simulate what I think that function would be doing. My > function, as written below, should compute the average pixel value of > my "image" [64 2 3;9 55 54;17 47 46] (to borrow MATLAB notation): > > short test_lowpass_filter() > { > short pixels[] = {64,2,3,9,55,54,17,47,46}; > short h[] = {3640,3640,3640,3640,3640,3640,3640,3640,3640}; // 1/9 * > 2^15 > int ii, prod, acc=0; > short output; > > for (ii=0; ii<9; ++ii) > pixels[ii] <<=8; // convert to Q.15 fmt: div by 256 & mult by > 32768 > > // fir filter > for (ii=0; ii<9; ++ii) { > prod = (h[ii]*pixels[ii]); // perform Q.15 mult > acc += prod; // update 32-bit accumulator > } > > output = (short) (acc>>15); // cast output to 16 bits > return output; > } > > > Sure enough, upon return 'output' is 8445 which when shifted right by > 8 bits is 32 (the mean of the data in 'pixels' is 33). Then I > replaced pixels with the following: > > short pixels[] = {215,171,173,133,213,96,51,5,212}; // avg = 141 > > This did not work, as when you shift 215 left by 8 bits you end up > with a negative number. Changing all of the shorts to unsigned shorts > does mitigate the problem (upon return the unsigned short's value is > 36087, which when shifted left by 8 bits is 140). > > So if I could bother you again, what shall I do here? It may be the > case that TI's IMGLIB function does something different than what I > have "reverse engineered" above, but it would seem to me that if their > function is expecting signed 16-bit integers than I need to scale my > data differently. Perhaps instead of thinking of the range 0-255 I > need to think of my pixels as being normalized to within the range > -128 to +127? > > Thanks in advance, > > ShehrzadYes, 215 doesn't fit in a "signed 8-bit" format, so you should only shift your numbers up 7 bits if TI's routine expects signed information. If your image data is limited to 8 bits you won't suffer much loss! What you've reverse-engineered will give you accurate results _except_ that it'll be much slower and it won't handle saturation as well as TI's code should. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●April 19, 20042004-04-19
Tim Wescott wrote:> Shehrzad wrote: > >> Thank you very much Tim! >> >> Your explanation makes sense, and indeed I wrote a little program on >> my TI C6701 to aid in my understanding. The TI function I wish to use >> expects signed 16-bit integers (shorts), so I wrote a little test >> function to simulate what I think that function would be doing. My >> function, as written below, should compute the average pixel value of >> my "image" [64 2 3;9 55 54;17 47 46] (to borrow MATLAB notation): >> >> short test_lowpass_filter() >> { >> short pixels[] = {64,2,3,9,55,54,17,47,46}; >> short h[] = {3640,3640,3640,3640,3640,3640,3640,3640,3640}; // 1/9 * >> 2^15 >> int ii, prod, acc=0; >> short output; >> >> for (ii=0; ii<9; ++ii) >> pixels[ii] <<=8; // convert to Q.15 fmt: div by 256 & mult by >> 32768 >> // fir filter >> for (ii=0; ii<9; ++ii) { >> prod = (h[ii]*pixels[ii]); // perform Q.15 mult >> acc += prod; // update 32-bit accumulator >> } >> >> output = (short) (acc>>15); // cast output to 16 bits >> return output; >> } >> >> >> Sure enough, upon return 'output' is 8445 which when shifted right by >> 8 bits is 32 (the mean of the data in 'pixels' is 33). Then I >> replaced pixels with the following: >> >> short pixels[] = {215,171,173,133,213,96,51,5,212}; // avg = 141 >> >> This did not work, as when you shift 215 left by 8 bits you end up >> with a negative number. Changing all of the shorts to unsigned shorts >> does mitigate the problem (upon return the unsigned short's value is >> 36087, which when shifted left by 8 bits is 140). >> >> So if I could bother you again, what shall I do here? It may be the >> case that TI's IMGLIB function does something different than what I >> have "reverse engineered" above, but it would seem to me that if their >> function is expecting signed 16-bit integers than I need to scale my >> data differently. Perhaps instead of thinking of the range 0-255 I >> need to think of my pixels as being normalized to within the range >> -128 to +127? >> >> Thanks in advance, >> >> Shehrzad > > > Yes, 215 doesn't fit in a "signed 8-bit" format, so you should only > shift your numbers up 7 bits if TI's routine expects signed information. > If your image data is limited to 8 bits you won't suffer much loss! > > What you've reverse-engineered will give you accurate results _except_ > that it'll be much slower and it won't handle saturation as well as TI's > code should.If there is no meaning that can be attached to a negative pixel value, then going unsigned, using all eight bits for magnitude, seems the better choice. There can be no negative-value results if the output is unsigned. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●April 19, 20042004-04-19
Jerry Avins wrote:> Tim Wescott wrote: > >> Shehrzad wrote: >> >>> Thank you very much Tim! >>> >>> Your explanation makes sense, and indeed I wrote a little program on >>> my TI C6701 to aid in my understanding. The TI function I wish to use >>> expects signed 16-bit integers (shorts), so I wrote a little test >>> function to simulate what I think that function would be doing. My >>> function, as written below, should compute the average pixel value of >>> my "image" [64 2 3;9 55 54;17 47 46] (to borrow MATLAB notation): >>> >>> short test_lowpass_filter() >>> { >>> short pixels[] = {64,2,3,9,55,54,17,47,46}; >>> short h[] = {3640,3640,3640,3640,3640,3640,3640,3640,3640}; // 1/9 * >>> 2^15 >>> int ii, prod, acc=0; >>> short output; >>> for (ii=0; ii<9; ++ii) >>> pixels[ii] <<=8; // convert to Q.15 fmt: div by 256 & mult by >>> 32768 >>> // fir filter >>> for (ii=0; ii<9; ++ii) { >>> prod = (h[ii]*pixels[ii]); // perform Q.15 mult >>> acc += prod; // update 32-bit accumulator >>> } >>> output = (short) (acc>>15); // cast output to 16 bits >>> return output; >>> } >>> >>> >>> Sure enough, upon return 'output' is 8445 which when shifted right by >>> 8 bits is 32 (the mean of the data in 'pixels' is 33). Then I >>> replaced pixels with the following: >>> >>> short pixels[] = {215,171,173,133,213,96,51,5,212}; // avg = 141 >>> >>> This did not work, as when you shift 215 left by 8 bits you end up >>> with a negative number. Changing all of the shorts to unsigned shorts >>> does mitigate the problem (upon return the unsigned short's value is >>> 36087, which when shifted left by 8 bits is 140). >>> >>> So if I could bother you again, what shall I do here? It may be the >>> case that TI's IMGLIB function does something different than what I >>> have "reverse engineered" above, but it would seem to me that if their >>> function is expecting signed 16-bit integers than I need to scale my >>> data differently. Perhaps instead of thinking of the range 0-255 I >>> need to think of my pixels as being normalized to within the range >>> -128 to +127? >>> >>> Thanks in advance, >>> >>> Shehrzad >> >> >> >> Yes, 215 doesn't fit in a "signed 8-bit" format, so you should only >> shift your numbers up 7 bits if TI's routine expects signed >> information. If your image data is limited to 8 bits you won't suffer >> much loss! >> >> What you've reverse-engineered will give you accurate results _except_ >> that it'll be much slower and it won't handle saturation as well as >> TI's code should. > > > If there is no meaning that can be attached to a negative pixel value, > then going unsigned, using all eight bits for magnitude, seems the > better choice. There can be no negative-value results if the output is > unsigned. > > JerryTrue, but if his library only handles 16-bit signed data then losing the one bit with signed data is probably much less of an issue than spending the time to write his own 2D convolution in assembly. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●April 19, 20042004-04-19
[snip]> >> > >> Yes, 215 doesn't fit in a "signed 8-bit" format, so you should only > >> shift your numbers up 7 bits if TI's routine expects signed > >> information. If your image data is limited to 8 bits you won't suffer > >> much loss! > >> > >> What you've reverse-engineered will give you accurate results _except_ > >> that it'll be much slower and it won't handle saturation as well as > >> TI's code should. > >I understand, I was just trying to gain an understanding. When I call into TI's routines, all I get back are some crazy values. It's too much of a black box for me to debug.> > > > If there is no meaning that can be attached to a negative pixel value, > > then going unsigned, using all eight bits for magnitude, seems the > > better choice. There can be no negative-value results if the output is > > unsigned. > > > > Jerry > > True, but if his library only handles 16-bit signed data then losing the > one bit with signed data is probably much less of an issue than spending > the time to write his own 2D convolution in assembly.Again, thank you for the much needed help. Tim's response above is the crux of my problem. The point is I really would like to use TI's IMGLIB library, which is written in hand-optimized assembly, and if that library expects signed 16-bit integers then I'm stuck. Jerry is correct that there is no meaning that can be attached to a negative pixel value, except when you're transforming the data. For example, IMGLIB provides wavelet transform functions, and the wavelet coefficients certainly could take on negative values. I suspect that is why the IMGLIB functions take signed integers. Now as for why TI provides the forward wavelet transform and not the inverse, well that's a whole other can of worms ;) Thanks again, -SQ
