PIC Microcontoller DSP Math Method sorting

median filter and sort by Mehmet Çetin

Mehmet Çetin Says

Hi all!!

There are(were) alot of people looking for median filter and sort algorithm so were I. At last I wrote aprogram sorting any lentgh any number of data and median filtering. 16 24 or 32 bits 5 7 9 11 ....bytes data.

Thanks to Lawrence Lille. This program is a higher version of his 8 bit sort/filter program. Thanks for the idea.

;
;this is a plug and play code
;not a plug and pray code!!
;
;Thanks to Lawrence Lille for the original
;program and the idea
;
;register assignments
;
	cblock 		0x20
;
        x
	y
;
	analog1h
	analog1l
;
	analog2h
	analog2l
;
	analog3h
	analog3l
;
	analog4h
	analog4l
;
	analog5h
	analog5l
;
	analog6h
	analog6l
;
	analog7h
	analog7l
;
	analog8h
	analog8l
;
	analog9h
	analog9l
;
	analog10h
	analog10l
;
	analog11h
	analog11l
;
	analog12h
	analog12l
;
	analog13h
	analog13l
;
	analog14h
	analog14l
;
	analog15h
	analog15l
;
;result regs
;
	resulth
	resultl
;
;regs used to compare the adjacent data
;in the array to compare and swap the places
;to sort them in ascending or descending order
;
	ahi
	amd
	alo
;
	bhi
	bmd
	blo
;
	a1hi
	a1lo
;
	b1hi
	b1lo
;
	c1hi
	c1lo
;
	d1lhi
	d1lo
;
;data pointer counter
;
	cntr1
;
	endc
;
indir           equ       00h
tmr0            equ       01h
pcl             equ       02h
status          equ       03h
fsr             equ       04h
;***************status register bits
#define         c         status,0 
#define         dc        status,1
#define         z         status,2
#define         pd        status,3
#define         to        status,4
#define         rp0       status,5
#define         rp1       status,6
#define         irp       status,7
;
        list    p=16c620   ; pic16c620 is the target processor
	org 0
;
	goto main
;
;the pointer table must be in
;accordance with the nember of the data
;array!!
;
gethi	addwf	pcl,f
	retlw	analog1h
	retlw	analog2h
	retlw	analog3h
	retlw	analog4h
	retlw	analog5h
	retlw	analog6h
	retlw	analog7h
	retlw	analog8h
	retlw	analog9h
	retlw	analog10h
	retlw	analog11h
	retlw	analog12h
	retlw	analog13h
	retlw	analog14h
	retlw	analog15h
;
;
;
getlo	addwf	pcl,f
	retlw	analog1l
	retlw	analog2l
	retlw	analog3l
	retlw	analog4l
	retlw	analog5l
	retlw	analog6l
	retlw	analog7l
	retlw	analog8l
	retlw	analog9l
	retlw	analog10l
	retlw	analog11l
	retlw	analog12l
	retlw	analog13l
	retlw	analog14l
	retlw	analog15l
;
;place some data to test
;the code it really works!!
;
readpot2
	movlw	d'251'
	movwf	analog1l
	movlw	h'ff'
	movwf	analog1h
;
	movlw	d'254'
	movwf	analog2l
	movlw	h'ff'
	movwf	analog2h
;
	movlw	d'10'
	movwf	analog3l
	movlw	h'ff'
	movwf	analog3h
;
	movlw	d'200'
	movwf	analog4l
	movlw	h'ff'
	movwf	analog4h
;
	movlw	d'50'
	movwf	analog5l
	movlw	h'ff'
	movwf	analog5h
;
	movlw	d'4'
	movwf	analog6l
	movlw	h'ff'
	movwf	analog6h
;
	movlw	d'255'
	movwf	analog7l
	movlw	h'ff'
	movwf	analog7h
;
	movlw	d'99'
	movwf	analog8l
	movlw	h'ff'
	movwf	analog8h
;
	movlw	d'12'
	movwf	analog9l
	movlw	h'ff'
	movwf	analog9h
;
	movlw	d'11'
	movwf	analog10l
	movlw	h'ff'
	movwf	analog10h
;
	movlw	d'13'
	movwf	analog11l
	movlw	h'ff'
	movwf	analog11h
;
	movlw	d'9'
	movwf	analog12l
	movlw	h'ff'
	movwf	analog12h
;
	movlw	d'8'
	movwf	analog13l
	movlw	h'ff'
	movwf	analog13h
;
	movlw	d'7'
	movwf	analog14l
	movlw	h'ff'
	movwf	analog14h
;
	movlw	d'6'
	movwf	analog15l
	movlw	h'ff'
	movwf	analog15h
;
	retlw	0
; end readpot2

;compare two adjacent variables by 16 to 32 or more
;bit math save them in temp regs and swap them if necessary
;
; x a
; y b
; x-y
; a-b
;
order	
;x a
; a := a1 := analog[cntr1]
	movf	cntr1,W
	call	getlo
	movwf	fsr
	movf	indir,W
	movwf	alo
	movwf	a1lo
	movf	cntr1,W
	call	gethi
	movwf	fsr
	movf	indir,W
	movwf	amd
	movwf	a1hi
	clrf	ahi
;
;y b
; b := b1 := analog[cntr1+1];
	incf	cntr1,f
	  movf	cntr1,W
	  call	getlo
	  movwf	fsr
	  movf	indir,W
	  movwf	blo
	  movwf	b1lo
	  movf	cntr1,W
	  call	gethi
	  movwf	fsr
	  movf	indir,W
	  movwf	bmd
	  movwf	b1hi
	  clrf	bhi
	decf	cntr1,f
;
; b-a
; y-x
; difference := a-b = analog[cntr1] - analog[cntr1+1];
; Perhaps it would be better to use the routine at
; http://massmind.org/techref/microchip/math/sub/16bb.htm.
	movf	blo,W
	subwf	alo,f
;
	movf	bmd,W
	skpc
	  incfsz	bmd,W
	subwf	amd,f
;
	movf	bhi,W
	skpc
	  incfsz	bhi,W
	subwf	ahi,f
; if( difference < 0 )
; {
;    swap them
; }
	btfss	ahi,7
	goto	ba_
;x>y
ab_	
	retlw	0
;
;swap a b
;
;y>x
ba_
;x
; analog[cntr1] = b1;
	movf	cntr1,W
	call	getlo
	movwf	fsr
	movf	b1lo,W
	movwf	indir
	movf	cntr1,W
	call	gethi
	movwf	fsr
	movf	b1hi,W
	movwf	indir
;y
; analog[cntr1+1] = a1;
	incf	cntr1,f
	  movf	cntr1,W
	  call	getlo
	  movwf	fsr
	  movf	a1lo,W
	  movwf	indir
	  movf	cntr1,W
	  call	gethi
	  movwf	fsr
	  movf	a1hi,W
	  movwf	indir
	decf	cntr1,f
	retlw	0
; end order()

;if there are n values
;
;x and y values are n-1
;
; for( y=n-1; y>0; y-- ){
;   cntr1 = 0;
;   for( x=n-1; x>0; x--){
;     order( analog[cntr1], analog[cntr1+1] );
;     cntr1++;
;   }
; }
sortarray
	movlw   .14              ;.14
	movwf   y               ; for y = 15 do while y >0  
sortloop2
	clrf	cntr1
	movlw	.14              ;.14
	movwf	x
sortloop
	call    order		; sort fsr and fsr+1
	incf	cntr1,f		; increment fsr pointer
	decfsz	x,f		; end do loop	
	goto    sortloop
	decfsz  y,f
	goto    sortloop2
;
;the result is in the regs in the mid
;pos. of the data array that can be any length
;if n=15 median index is 8
;your result is here!!
;
	movf    analog8h,W      ;here's your answer
	movwf   resulth         ;placed into the file result for use anywhere else. 
	movf	analog8l,W
	movwf	resultl
;
	return
	; end sortarray
;*****************************************************************************

;place the values and do the task
;
main    call readpot2
	call sortarray	        ;sort the new data into the array
lp1	goto lp1		;that's all
;
	end

David A Cary Says: " (I modified to use standard notation:
Use ",W" instead of ",0".
Use ",f" instead of ",1". ) "

David A Cary Says:

Rather than comparing *adjacent* pointers (doing a complete bubblesort), would the extra complexity of a (single iteration of) quicksort make it go any faster ? Especially when I collect lots of data, and I only want the median, not a completely sorted list.

pseudo-code for single iteration of quicksort:

• partial_sort:
• scan the left half of the array for any "out of place item". (Any item with a values more than or equal to the value at the midpoint of the array). (if there is none, leave left_pointer pointing at the midpoint).
• scan the right half of the array for any "out of place item". (Any item with a value less than or equal to the value at the midpoint of the array). (if there are none, leave right_pointer pointing at the midpoint).
• swap the 2 out of place items.
• While left_pointer and right_pointer are *different*, repeat partial_sort.
• Otherwise, left_pointer and right_pointer are now both pointing at the midpoint of the array, which is the median. All the values to the left are less than the median (but are probably not sorted). All the values to the right are greater than the median (but are probably not sorted).

variations: rather than picking *any* out-of-place item, would it go any quicker to pick the *worst* out-of-place item (the maximum value on the left side, the minimum value on the right side) ?

Says:

I had great trouble with unstable adc values and this code helped a great deal, but it was not the final answer. I finaly averaged 16 median values to get a very stable result. With a 4MHz PIC it takes quite some time, but the result was worth it.

For a practical application of this code see: PIC Microcontoller Input / Ouput Method - Median Filtering A2D results by Louis Nel

Questions: