Help with speed up my subroutine

[pberrett]

Hi everyone

I have a difficult problem that I am tryng to solve. Is there anyone brave enough to try and tackle it?

I have written a program to find comets in images. The images I am examining are in 1024 x 1024 arrays with zero indexing and each point in the array has a value from 0 to 255.

My program runs very well and effectively finds comets but the central subroutine in the program runs very slowly. I have been able to use numpy to speed up other areas of the program but I can't think of a way to use numpy to speed this subroutine up.


Here's the subroutine

def seqfind(number,starttime,file1,file2,file3,file4,time1,time2,time3,time4,allsequence):
    
    l1=len(file1)
    l2=len(file2)
    l3=len(file3)
    l4=len(file4)
    perc= (time2-time1)/(time4-time1)
    perc2= (time3-time1)/(time4-time1)
    
    avetime=((time4-time1)/36)
    for loop1 in range (0,l1):
        first0=file1[loop1][0]
        first1=file1[loop1][1]
        
        for loop4 in range (0,l4):
            fourth0=file4[loop4][0]
            fourth1=file4[loop4][1]
            sumdist=( abs(first0-fourth0) +  abs(first1-fourth1)  ) /(avetime)    
#            print(sumdist)
            
            
            if 14<sumdist<120:
                
                # Distance is acceptable           
                
                
                
                for loop2 in range(0,l2):
                    
                    second0=file2[loop2][0]
                    second1=file2[loop2][1]
                
                    if first0<second0<fourth0 or first0>second0>fourth0:
                        
                        
                        if first1<second1<fourth1 or first1>second1>fourth1:
                            
                            newx = int((perc*(fourth0-first0)) + first0)
                            newy = int((perc*(fourth1-first1)) + first1)
   
                            
        #                    print (file4[loop4][0])
        #                    print (file1[loop1][0])
                            
        #                    print (str(newx) +"  " + str(newy) + "  " +str(file2[loop2][0]) + "  " + str(file2[loop2][1]))
                            
                            if (newx-2)<second0<(newx+2)and(newy-2)<second1<(newy+2):
                                                            
                                for loop3 in range(0,l3):
                                    
                                    third0=file3[loop3][0]
                                    third1=file3[loop3][1]
                                    
                                    if first0<third0<fourth0 or first0>third0>fourth0:
                                        
                                        if first1<third1<fourth1 or first1>third1>fourth1:
                                           
                                            newx2 = int((perc2*(fourth0-first0))+first0)
                                            newy2 = int((perc2*(fourth1-first1))+first1)

                                            
                                            if (newx2-2)<third0<(newx2+2)and(newy2-2)<third1<(newy2+2):
                                                
                                                sequence = [number,starttime,first0,first1,newx, newy, newx2, newy2,fourth0,fourth1]
                                                
                                                allsequence.append(sequence)
        
    return allsequence
                                

The variables being fed into the subroutine are as follows

number The routine is examining 4 images taken in a row eg imaqges 5,6,7,8 or 7,8,9,10 as part of a list of daily images. Number refers to the sequence of the first image eg 5 or 7 per the examples.
starttime This is used for reference purposes in other areas of the program. It is not used by the subroutine but is appended if a sequence of stars is found.
file1 - a list of positions eg [x,y] where stars have previously been found in the first image
file2 - a list of positions eg [x,y] where stars have previously been found in the second image
file3 - a list of positions eg [x,y] where stars have previously been found in the third image
file4 - a list of positions eg [x,y] where stars have previously been found in the fourth image
time1 - time the first image was taken expressed as the number of minutes passed since the starttime (we may be processing hundreds of images per day so the startime may be several hours ago) eg 0036, 0048, 0612
time2 - time the first image was taken expressed as the number of minutes passed since the starttime eg 0048
time3 - time the first image was taken expressed as the number of minutes passed since the starttime eg 0060
time4 - time the first image was taken expressed as the number of minutes passed since the starttime eg 0085

allsequence This is the list of cometary movement lists. If this routine finds 4 positions in a straight line travelling at a constant speed it appends various details onto that list

The 4 images are generally taken 12 minutes apart but sometimes they are taken at odd times and sometimes the gap between images can be more than 12 minutes eg 24 or 25 minutes.

The object of the subroutine is to examine the 4 lists of star positions and look for a star that appears to move at a constant speed in a straight direction.

The routine does this by looping through every combination of star positions of image 1 and image 4. It makes the assumption that the object iodentified in the two images is the same and then calculates, discounting for time differeces between the images, where the comet should be in images 2 and 3. It then looks in the lists of star positions for those two images to see if a star was listed at those positions. if so then we have a sequence of 4 star positions that gets appended to the list allsequence at the end of the routine.

To give a simple example

A star is identified at [100,100] in the first image and a star is identfied at [130,130] in the fourth image.

The program calculates that if there is a star in the second image at [110,110] and in the third image at [120,120] then there is an object moving at a contant velocity in a straight line. it checks the second and third image lists to see if stars were identified at those positions and if so, appends all the details to allsequence.

Once the routine has analysed the 3 images to find any sequences eg using images 5,6,7,8 the program calls the subroutine again using the next 4 images i.e. images 6,7,8,9

Is there a way to speed the above subroutine up? if so, how? I have tried to vectorize it without succcess.

Thanks Peter

[MvGulik]

As former Zooniverse user you have peeked my interest. Unfortunately I have no numpy experience, so I'm not sure the following might help.

At your 3e and 4e inner loops your using compares like if first0<second0<fourth0 or first0>second0>fourth0:.

One could try to limit that to one compare by using pre-ordered-value variables. ie if low0<second0<high0: or of course if high0>second0<low0:.
This part only give a minor (potential trivial) speed gain, its the fact that you can test and preset those high0 & low0 variables before you enter the loop where you do those compares that makes this potential interesting to gain some speed.
With high0 and low0 being something like: low0=min(first0,fourth0) & high0=max(first0,fourth0)

I'm not sure how much speed gain this gives, probably not that significant. But if applied to all jobs than can be lifted from lower to higher loops, it still might add up.


PS: One other thing. You say

.. 4 positions in a straight line travelling at a constant speed ..

Make sure your detection allows for some deviation, especially for images from ground based telescopes (atmosphere and such).
See for example 'New Candidates' case 2 in this asteroidzoo result.