AppletTalk.com Java discussions newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Arrays not big enough          AppletTalk.com Forum Index -> Java Help View previous topic :: View next topic   Author Message Rudiga Guest Posted: Wed Oct 26, 2005 11:40 am    Post subject: Arrays not big enough Hi I wonder if anyone might be able to help. The program I am writing for my dissertation is to process pictures against the previous one, i.e frames of a video clip. I have run into a problem when comparing the RGB values for each pixal against the last one as I am unable to store it all in any kind of datastructure. For example, i want to find the Standard deviation of the Red value for a specific pixal in a 10 sec video clip, i would process each frame, store the Red value in an array and then repeat until the end of the clip. e.g for (int x = 0; x < picWidth; x++) { for (int y = 0; y < picHeight; y++) { for(int i = 0; i < frames; i++){ } // end each frame } // end y } // end x This method works (ie is more memory efficient) if i do one pixal at a time and cycle the frame on the inner loop like above, however that requires more calls to the hdd, ie for every pixal of every image. Therefore this takes forever to calculate, therefore impractical. By having the frame on the outer part of the loop would solve the speed issue, ie reducing the calls to the hdd, but i have no way of storing all the images in memory as it is too big. Can anyone suggest any method to solve this problem? Thankyou Martin Back to top Rudiga Guest Posted: Wed Oct 26, 2005 11:53 am    Post subject: Re: Arrays not big enough Oh and also, I wanted to find the median of each pixal over a set of frames, which causes a problem as i need to store each value for each pixal in order to choose the median pixal value. "Rudiga" <none (AT) none (DOT) net> wrote Quote: Hi I wonder if anyone might be able to help. The program I am writing for my dissertation is to process pictures against the previous one, i.e frames of a video clip. I have run into a problem when comparing the RGB values for each pixal against the last one as I am unable to store it all in any kind of datastructure. For example, i want to find the Standard deviation of the Red value for a specific pixal in a 10 sec video clip, i would process each frame, store the Red value in an array and then repeat until the end of the clip. e.g for (int x = 0; x < picWidth; x++) { for (int y = 0; y < picHeight; y++) { for(int i = 0; i < frames; i++){ } // end each frame } // end y } // end x This method works (ie is more memory efficient) if i do one pixal at a time and cycle the frame on the inner loop like above, however that requires more calls to the hdd, ie for every pixal of every image. Therefore this takes forever to calculate, therefore impractical. By having the frame on the outer part of the loop would solve the speed issue, ie reducing the calls to the hdd, but i have no way of storing all the images in memory as it is too big. Can anyone suggest any method to solve this problem? Thankyou Martin Back to top Roedy Green Guest Posted: Wed Oct 26, 2005 12:23 pm    Post subject: Re: Arrays not big enough On Wed, 26 Oct 2005 11:40:29 GMT, "Rudiga" <none (AT) none (DOT) net> wrote, quoted or indirectly quoted someone who said : Quote: By having the frame on the outer part of the loop would solve the speed issue, ie reducing the calls to the hdd, but i have no way of storing all the images in memory as it is too big. You might look at memory mapped files, and work on keeping your pokings from hopping all over. The way the Gimp handles this is with tiles, but that would probably count as a datastructure. Perhaps split the image into squares, one square per file. Then just read a corresponding pair of files into RAM, and do your calculation, then move on to the next pair. To make life easy on yourself put some slop around each image so you don't have to do fine needlework on the edges. You can do efficient bit fiddling by using longs and binary operators. Look also into java.util.BitSet. see http://mindprod.com/jgloss/binary.html Just a hunch you might find this idea fun to play with.. Instead of RGB bits like this rrrrrrrrggggggggbbbbbb interdigitate them: rgbrgbrgbrgbrgbrgbrgbrgb or convert them to HSB. -- Canadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. Back to top Eric Sosman Guest Posted: Thu Oct 27, 2005 4:35 pm    Post subject: Re: Arrays not big enough Rudiga wrote On 10/26/05 07:40,: Quote: Hi I wonder if anyone might be able to help. The program I am writing for my dissertation is to process pictures against the previous one, i.e frames of a video clip. I have run into a problem when comparing the RGB values for each pixal against the last one as I am unable to store it all in any kind of datastructure. For example, i want to find the Standard deviation of the Red value for a specific pixal in a 10 sec video clip, i would process each frame, store the Red value in an array and then repeat until the end of the clip. e.g for (int x = 0; x < picWidth; x++) { for (int y = 0; y < picHeight; y++) { for(int i = 0; i < frames; i++){ } // end each frame } // end y } // end x This method works (ie is more memory efficient) if i do one pixal at a time and cycle the frame on the inner loop like above, however that requires more calls to the hdd, ie for every pixal of every image. Therefore this takes forever to calculate, therefore impractical. By having the frame on the outer part of the loop would solve the speed issue, ie reducing the calls to the hdd, but i have no way of storing all the images in memory as it is too big. Mean and standard deviation are easy, because you don't need to have all the samples present at the same time: you can process an entire frame updating a couple of per-pixel totals, then throw the frame away and move to the next. In a follow-up you said you're also interested in the median, which is a bit trickier but still tractable. Since the color components for each pixel have a very restricted range (0<=R<256), you could just count the number of times each possible R value appeared at each pixel position and then figure out the median (or other quantiles) after processing all the frames. If maintaining 256 counters per color component per pixel is too much, and if an estimate is acceptable instead of an exact median, various approximate-median algorithms exist. One that I've used is by Raj Jain and Imrich Chlamtac: "The P**2 Algorithm for Dynamic Calculation of Quantiles and Histograms Without Storing Observations," CACM volume 28 number 10 (October 1985), pages 1076-1085. Roedy Green's suggestion of breaking the images into suitably-sized tiles can be used in conjunction with any of these techniques. -- [email]Eric.Sosman (AT) sun (DOT) com[/email] Back to top Oliver Wong Guest Posted: Thu Oct 27, 2005 9:10 pm    Post subject: Re: Arrays not big enough "Eric Sosman" <eric.sosman (AT) sun (DOT) com> wrote Quote: If maintaining 256 counters per color component per pixel is too much, and if an estimate is acceptable instead of an exact median, various approximate-median algorithms exist. One that I've used is by Raj Jain and Imrich Chlamtac: "The P**2 Algorithm for Dynamic Calculation of Quantiles and Histograms Without Storing Observations," CACM volume 28 number 10 (October 1985), pages 1076-1085. I'm not familiar with the paper cited above, but if you memory is a problem and you're satisfied with an approximate mean, then a simple algorithm would be to break up the possible values into chunkier bands (perhaps 0-32,33-64,65-96,etc.), and store how many times a pixel value falls in those bands, histogram style, and report the median to be the center of the band with the most values. - Oliver Back to top Nigel Wade Guest Posted: Fri Oct 28, 2005 10:30 am    Post subject: Re: Arrays not big enough Boudewijn Dijkstra wrote: Quote: "Rudiga" <none (AT) none (DOT) net> schreef in bericht news:NWJ7f.15376$65.6255 (AT) newsfe6-win (DOT) ntli.net... Hi I wonder if anyone might be able to help. The program I am writing for my dissertation is to process pictures against the previous one, i.e frames of a video clip. I have run into a problem when comparing the RGB values for each pixal against the last one as I am unable to store it all in any kind of datastructure. For example, i want to find the Standard deviation of the Red value for a specific pixal in a 10 sec video clip, i would process each frame, store the Red value in an array and then repeat until the end of the clip. e.g for (int x = 0; x < picWidth; x++) { for (int y = 0; y < picHeight; y++) { for(int i = 0; i < frames; i++){ } // end each frame } // end y } // end x This method works (ie is more memory efficient) if i do one pixal at a time and cycle the frame on the inner loop like above, however that requires more calls to the hdd, ie for every pixal of every image. Therefore this takes forever to calculate, therefore impractical. By having the frame on the outer part of the loop would solve the speed issue, ie reducing the calls to the hdd, but i have no way of storing all the images in memory as it is too big. You don't need to store all the images. To calculate the standard deviation of all red values in a range of frames, you perform four stages. In the first stage, you iteratively load each frame and add the red values to a special 'sum-image' with increased bit depth. In the second stage, you calculate the average value of each dot using the sum-image. In the third stage you make a second pass over all the images to calculate the variance of each dot using the average-image. The fourth stage is simply to take the square root of the variances, to obtain the standard deviation of each dot. There's no need to process the images twice, once should be sufficient. To calculate the mean and variance you require sigma(x) and sigma(x squared) [writing equations in ASCII is not ideal...]. Both these quantities can be calculated on a single pass. For non-complex data the mean is sigma(x)/N, and the variance is ((sigma(x squared) - (sigma(x)*sigma(x)/N)) / (N-1) So you only need to have 2 "frames", one to store sigma(x) for each pixel and another to store sigma(x squared) for each pixel. These need to have sufficient dynamic range to hold the summations. -- Nigel Wade, System Administrator, Space Plasma Physics Group, University of Leicester, Leicester, LE1 7RH, UK E-mail : [email]nmw (AT) ion (DOT) le.ac.uk[/email] Phone : +44 (0)116 2523548, Fax : +44 (0)116 2523555 Back to top Eric Sosman Guest Posted: Tue Nov 01, 2005 4:35 pm    Post subject: Re: Arrays not big enough Oliver Wong wrote On 10/27/05 17:10,: Quote: "Eric Sosman" <eric.sosman (AT) sun (DOT) com> wrote in message news:djqvjs$glt$1 (AT) news1brm (DOT) Central.Sun.COM... If maintaining 256 counters per color component per pixel is too much, and if an estimate is acceptable instead of an exact median, various approximate-median algorithms exist. One that I've used is by Raj Jain and Imrich Chlamtac: "The P**2 Algorithm for Dynamic Calculation of Quantiles and Histograms Without Storing Observations," CACM volume 28 number 10 (October 1985), pages 1076-1085. I'm not familiar with the paper cited above, but if you memory is a problem and you're satisfied with an approximate mean, then a simple algorithm would be to break up the possible values into chunkier bands (perhaps 0-32,33-64,65-96,etc.), and store how many times a pixel value falls in those bands, histogram style, and report the median to be the center of the band with the most values. Almost, but what you describe approximates the mode (or one of them), not the median. As for the mean, there's no reason to settle for an approximation: computing the exact mean (within the limits of numerical precision) is cheap. -- [email]Eric.Sosman (AT) sun (DOT) com[/email] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         AppletTalk.com Forum Index -> Java Help All times are GMT Page 1 of 1   Jump to: Select a forum Java Newsgroups----------------Java DiscussionsWeb-based java games comp.lang.java 3D Graphics API's for Java Java: Support and criticism Java System Announcements comp.lang.java.api JavaBeans Java and CORBA Java and Databases comp.lang.java.developer Java GUI Toolkits Java Help comp.lang.java.javascript JVM, native methods and hardware comp.lang.java.misc Java Language Programming Security and Java comp.lang.java.setup Java Software Tools comp.lang.java.tech ibm.software.java.linux  Non-English Java Newsgroups----------------Java Language (German)Language Java (Français)Java (Italian)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.