gif-code / effects.ts

/**
 * 
 * More a miscelaneous file for things related to image and color table changes
 * 
 */


type ImageDataOffset = {
	imgdata: ImageData
	offsettop: number
	offsetleft: number
}

/**
 * Recompression experiment. Maybe added in the future. Still needs to normlaize transparency in some way
 * takes a bunch of base image data and returns a more compressable array of image data
 * images need to have the same dimensions
 * @param images 
 * @returns 
 */
function reframe(images: Array<ImageDataOffset>) {
	const doneImages: Array<ImageDataOffset> = []
	doneImages.push({
		imgdata: new ImageData(Uint8ClampedArray.from(images[0].imgdata.data), images[0].imgdata.width, images[0].imgdata.height),
		offsetleft: images[0].offsetleft,
		offsettop: images[0].offsettop
	})

	let left = [-1, -1], top = [-1, -1], right = [-1, -1], down = [-1, -1] // [x,y] coordinates on the image

	const updateRect = function (newpos: number[]) {
		if (newpos[0] < left[0] || left[0] < 0) {
			left = newpos
		}
		if (newpos[1] < top[1] || top[1] < 0) {
			top = newpos
		}
		if (newpos[0] > right[0] || right[0] < 0) {
			right = newpos
		}
		if (newpos[1] > down[1] || down[1] < 0) {
			down = newpos
		}
	}

	//transfroms an index into a pixel coordinate on a theoretical logical screen
	// pixel index has to be the actual idnex of the pixel, not of one of its bytes
	const indexToCoordinate = function (pixelIndex: number, width: number, offsetleft: number, offsettop: number) {
		const x = (pixelIndex % width) + offsetleft
		const y = Math.floor(pixelIndex / width) + offsettop
		return [x, y]
	}

	// returns actual index, not of the first byte in image data
	const coordinatToIndex = function (x: number, y: number, width: number, offsetleft: number, offsettop: number) {
		return (((y - offsettop) * width) + x - offsetleft)
	}

	const getOvelap = function (i1: ImageDataOffset, i2: ImageDataOffset) {
		const left = Math.max(i1.offsetleft, i2.offsetleft)
		const top = Math.max(i1.offsettop, i2.offsettop)

		const right = Math.min(i1.offsetleft + i1.imgdata.width, i2.imgdata.width + i2.offsetleft)
		const bottom = Math.min(i1.imgdata.height + i1.offsettop, i2.imgdata.height + i2.offsettop)

		if (right < left || bottom < top) {
			console.log("images are not overlapping at all")
			return undefined
		}
		return [left, top, right, bottom]
	}

	const isInBounds = function (x: number, y: number, bl: number, bt: number, br: number, bb: number) {
		return (bl <= x && x <= br) && (bt <= y && y <= bb)
	}

	//if either of the indecies are out of the data range this also returns false
	const samePixelAt = function (i1: ImageData, i1Index: number, i2: ImageData, i2Index: number) {
		return i1Index < i1.data.length && i2Index < i2.data.length && (
			i1.data[i1Index * 4] === i2.data[i2Index * 4] &&
			i1.data[i1Index * 4 + 1] === i2.data[i2Index * 4 + 1] &&
			i1.data[i1Index * 4 + 2] === i2.data[i2Index * 4 + 2] &&
			i1.data[i1Index * 4 + 3] === i2.data[i2Index * 4 + 3])
	}


	for (let i = 0; i < images.length - 1; i++) {
		let newImageData = []
		const boundary = getOvelap(images[i], images[i + 1])
		const i2width = images[i + 1].imgdata.width;
		const i2height = images[i + 1].imgdata.height;
		const i2top = images[i + 1].offsettop;
		const i2left = images[i + 1].offsetleft;
		const i1width = images[i].imgdata.width;
		const i1heigth = images[i].imgdata.height;
		const i1top = images[i].offsettop;
		const i1left = images[i].offsetleft;

		left = [-1, -1], top = [-1, -1], right = [-1, -1], down = [-1, -1]


		if (!boundary) { // no overlap so we just put the whole thing into the output
			doneImages.push({
				imgdata: new ImageData(Uint8ClampedArray.from(images[i + 1].imgdata.data), images[i + 1].imgdata.width, images[i + 1].imgdata.height),
				offsetleft: images[i + 1].offsetleft,
				offsettop: images[i + 1].offsettop
			})
			continue
		}

		// getting the rectangle:
		for (let i2Pixel = 0; i2Pixel < images[i + 1].imgdata.data.length / 4; i2Pixel++) {
			const [x, y] = indexToCoordinate(i2Pixel, i2width, i2left, i2top)
			const i1Pixel = coordinatToIndex(x, y, i1width, i1left, i1top)

			if (!samePixelAt(images[i].imgdata, i1Pixel, images[i + 1].imgdata, i2Pixel)) {
				updateRect([x, y])
			}
		}


		// image2 lies completly in image1 = > we do not need to change ther found rectangle
		if (boundary[0] <= i2left && i2left + i2width <= boundary[2] &&
			boundary[1] <= i2top && i2top + i2height <= boundary[3]) {
		}
		else { //if image 2 lies not completly in image 1 we have to retroactviely update the rectangle to include the edges that are outside of image1's bounds.
			if (i2top < i1top) {
				top[1] = i2top
			}
			if (i2left < i1left) {
				left[0] = i2left
			}
			if (i2left + i2width > i1left + i1width) {
				right[0] = i2left + i2width;
			}
			if (i2top + i2height > i1top + i1heigth) {
				down[1] = i2top + i2height
			}
		}

		//actually copying pixels within the rectangle and doing transparency stuff
		for (let i2Pixel = 0; i2Pixel < images[i + 1].imgdata.data.length / 4; i2Pixel++) {
			const [x, y] = indexToCoordinate(i2Pixel, i2width, i2left, i2top)

			if (isInBounds(x, y, left[0], top[1], right[0], down[1])) {
				const i1Pixel = coordinatToIndex(x, y, i1width, i1left, i1top)
				if (samePixelAt(images[i].imgdata, i1Pixel, images[i + 1].imgdata, i2Pixel)) {
					newImageData.push(0)
					newImageData.push(0)
					newImageData.push(0)
					newImageData.push(0)
				} else {
					newImageData.push(images[i + 1].imgdata.data[i2Pixel * 4])
					newImageData.push(images[i + 1].imgdata.data[i2Pixel * 4 + 1])
					newImageData.push(images[i + 1].imgdata.data[i2Pixel * 4 + 2])
					newImageData.push(images[i + 1].imgdata.data[i2Pixel * 4 + 3])
				}
			} else {

			}
		}

		const newWidth = (right[0] - left[0]) + 1
		const newHeight = (down[1] - top[1]) + 1

		if (newImageData.length == 0) {
			console.error("newImageData.length ==0")
			continue
		}

		//console.log(newWidth)
		//console.log(newHeight)

		//console.log(left[0], top[1], right[0], down[1])

		doneImages.push({
			imgdata: new ImageData(Uint8ClampedArray.from(newImageData), newWidth, newHeight),
			offsetleft: left[0],
			offsettop: top[1]
		})
	}

	return doneImages
}

// currently not used
function imageToImageData(imageBlok: GifBlockImage): ImageData {

	const indexStream = decompressor.decompressTableBasedImageData(imageBlok.tableBasedImageData)
	const width = imageBlok.imagedescriptor.data![5] | (imageBlok.imagedescriptor.data![6] << 8);
	const height = imageBlok.imagedescriptor.data![7] | (imageBlok.imagedescriptor.data![8] << 8);

	const imagepixels = indexStreamToPicture(indexStream, imageBlok.colortable!.data!);
	return new ImageData(Uint8ClampedArray.from(imagepixels), width, height,)
}

// currently not used
function imagereframertest() {

	if (!gifView) { return }

	const baseimages: ImageDataOffset[] = []

	for (let block of gifView.blocks) {
		if (block.blockType == BlockType.TableBasedImageData) {
			const bundled = gifView!.bundleImage(block)!
			baseimages.push({
				imgdata: imageToImageData(bundled),
				offsettop: (bundled.imagedescriptor as ImageDescriptor).topPosition(),
				offsetleft: (bundled.imagedescriptor as ImageDescriptor).leftPosition()
			})
		}
	}

	const reframed = reframe(baseimages)

	const parentDiv = document.createDocumentFragment()
	parentDiv.appendChild(document.createElement("p"))

	for (let ref of reframed) {
		const canvas = document.createElement("canvas") as HTMLCanvasElement
		canvas.classList.add("canvas-element")
		canvas.width = ref.imgdata.width
		canvas.height = ref.imgdata.height
		canvas.getContext("2d")?.putImageData(ref.imgdata, 0, 0)

		parentDiv.appendChild(canvas)
	}

	document.getElementById("canvas-div")!.replaceChildren()
	document.getElementById("canvas-div")!.append(parentDiv)

}

/**
 * functions that change a colortable wrt certain visual needs. Recoloring happens as a side effect on the given colortables
 */
namespace ColorTableEffects {

	/**
	 * Applies the given function to each color table. Tables should be changed as a side effect of the effect function.
	 * @param effect the effect function from ColorTableEffects to be used on every color table
	 * @param options parameters to be passed to the effect function
	 * @example //apply a red shift of +10 to all color tables
	 * ColorTableEffects.applyColorTableEffectToAll(colorshift, 10, 0, 0)
	 */
	export function applyColorTableEffectToAll(effect: Function, ...options: any) {
		if (!gifView) { return }
		if (gifView.globalColorTable) {
			effect(gifView.globalColorTable as ColorTable, ...options)
		}

		for (let lct of gifView.getBlocksOfType(BlockType.LocalColorTable)) {
			effect(lct as ColorTable, ...options);
		}
	}

	/**
	 * Converts every color in the given color table to a grey color using the average of its rgb values.
	 * @param colorTable Color table to be changed
	 */
	export function greyscale(colorTable: ColorTable) {
		for (let i = 0; i < colorTable.data.length / 3; i++) {
			const value = (colorTable.data[i * 3] + colorTable.data[i * 3 + 1] + colorTable.data[i * 3 + 2]) / 3;
			colorTable.data[i * 3] = value;
			colorTable.data[i * 3 + 1] = value;
			colorTable.data[i * 3 + 2] = value;
		}
	}

	export function colorshift(colorTable: ColorTable, redshift = 0, greenshift = 0, blueshift = 0) {
		for (let i = 0; i < colorTable.data!.length / 3; i++) {
			colorTable.data![i * 3] = Math.min(255, (colorTable.data![i * 3] + redshift));
			colorTable.data![i * 3 + 1] = Math.min(255, (colorTable.data![i * 3 + 1] + blueshift));
			colorTable.data![i * 3 + 2] = Math.min(255, (colorTable.data![i * 3 + 2] + greenshift));
		}
	}

	/**
	 * Allows the application of any kind of recoloring on a color to color basis
	 * @param colorTable colortable to be changed
	 * @param fct A function with signature (r,g,b) => [r,g,b] which is then applied to every colortable entry
	 */
	function recolor(colorTable: ColorTable, fct: Function) {
		for (let i = 0; i < colorTable.data!.length / 3; i++) {
			const [r, g, b] = fct(colorTable.data![i * 3], colorTable.data![i * 3 + 1], colorTable.data![i * 3 + 2])
			colorTable.data![i * 3] = r;
			colorTable.data![i * 3 + 1] = g;
			colorTable.data![i * 3 + 2] = b;
		}
	}

	/**
	 * Get rid of excess colors via merging the closest neighbours. Either takes the average of both merged colors, or subsumes the "lower" color into the "higher" one
	 * @param imageBundle GifBlockImage holding the relevant data. Will be changed through the function.
	 * @param targetAmount Amount of colors that should remain. If it is greater than colors exist, nothing is done
	 */
	function colorMerge(imageBundle: GifBlockImage, targetAmount: number, middle = false) {


	}

}

/**
 * Experimental function that produces a gif displaying all 24bit colors.
 */
function makeImageFULLCOLORGIF() {

	const header = [
		0x47, 0x49, 0x46, //GIF 
		0x38, 0x39, 0x61 //89a
	];

	const lsd = [
		0x00, 0x10, //width
		0x00, 0x10,  //height
		0b01110000, //packed fields
		0x00, //background color index
		0x00 // pixel aspect ratio
	];

	const gce = [
		0x21, // extension introducer
		0xF9, // Graphic Control Label
		0x4, // Block Size
		0b00000100,//<Packed Fields>
		0x05, 0x00,//Delay Time //should be 5/100 seconds
		0x0,
		0x0,
	];

	const uint16ToLE = (x: number): number[] => {
		const s = [];
		s.push(x & 0b11111111);
		s.push((x >> 8) & 0b11111111);
		return s;
	};


	const makeimg = (leftPos: number, topPos: number) => {
		return [
			0x2C, //Image Separator               
			leftPos & 0b11111111, (leftPos >> 8) & 0b11111111, //Image Left Position 
			topPos & 0b11111111, (topPos >> 8) & 0b11111111, //Image Top Position
			0x00, 0x01, //Image Width  //256
			0x01, 0x00, //Image Height //1
			0b10000111 // packed fields
		]
	};


	const id = [
		0x2C, //Image Separator               
		0x00, 0x00, //Image Left Position 
		0x00, 0x00, //Image Top Position
		0x00, 0x01, //Image Width  //256
		0x01, 0x00, //Image Height //1
		0b10000111 // packed fields
	];

	const trailer = [0x3B];

	let gif: number[] = [];
	gif.push(...header);
	gif.push(...lsd);

	const compressed = compressor.compress(Array.from(Array(256).keys()), 8).reverse(); // should result in a compression of the codes 0 to 255

	const tbid = [
		0x08, // min lzw size
		0xFF, //size of the first subdata block
	];

	tbid.push(...compressed.slice(0, 255));
	tbid.push(compressed.length - 255); //we are going to be over the 255 bytes alone through having 256 color codes in the data
	tbid.push(...compressed.slice(255));
	tbid.push(0); //last subdatablock with 0 length


	let colorm: number[] = [];
	let leftoffest = 0;
	let topoffset = 0;
	for (let r = 0; r < 256; r++) {
		for (let g = 0; g < 256; g++) {
			for (let b = 0; b < 256; b++) {
				colorm.push(...[r, g, b]);

				if (colorm.length == 256 * 3) {
					//add a new image
					gif.push(...gce);
					gif.push(...makeimg(leftoffest * 256, topoffset));
					gif.push(...colorm);
					gif.push(...tbid);
					colorm = [];
					leftoffest++;
					if (leftoffest == 16) {
						leftoffest = 0;
						topoffset++;
					}
				}
			}
		}
	}

	gif.push(...trailer);

	downloadBlob(new Blob([Uint8Array.from(gif)], { type: "image/gif" }), "jsfullcolorgif.gif");

}

/**
 * Type to keep track of colors during posterization
 */
type kMeanColorpoint = {
	id: number, // id in the colortable
	color: [number, number, number],
	groupID: number
}

/**
 * Kmeans using the triangle inequality and some other stuff to be quicker
 * @example const posterizer = new colorPosterizer()
 *  posterizer.setCentroidAmount(256) // as many centroids as we want to have colors at the end
 *  posterizer.initPoints(colors) // unique colors in source image as starting points
 *  posterizer.calc(100) //max 100 iterations
 * 	const mapping = posterizer.createIDToGroupMapping() // maps source color indices onto cluster ids
 */
class colorPosterizer {

	private points: kMeanColorpoint[]
	private means: [number, number, number][]
	private groupings: Map<number, kMeanColorpoint[]> //maps a group id to the points in that centroid. Trades extra memory for a good speed boost
	private meanDistances: Map<number, [number, number][]> // meanID -> [other meanID, distance to other mean]
	private centroidAmount: number;

	constructor() {
		this.points = [];
		this.means = [];
		this.centroidAmount = 1;
		this.groupings = new Map();
		this.meanDistances = new Map();
	}

	/**
	 * Calculates the distance between two 3D points
	 * @returns Distance between the two given points
	 */
	private static distance(point1: [number, number, number], point2: [number, number, number]) {
		return Math.sqrt(
			Math.pow(point1[0] - point2[0], 2) +
			Math.pow(point1[1] - point2[1], 2) +
			Math.pow(point1[2] - point2[2], 2)
		)
	}

	/**
	 * Initializes color points so that means calcualtion can start. 
	 * @param colortable Color data where 3 consecutive indices give the rgb components for a color.
	 */
	public initPoints(colortable: number[]) {
		if (colortable.length % 3 !== 0) {
			throw new Error("colortable not long enough")
		}
		this.points = []
		for (let i = 0; i < colortable.length / 3; i++) {
			const point: kMeanColorpoint = {
				id: i,
				color: [colortable[i * 3], colortable[i * 3 + 1], colortable[i * 3 + 2]],
				groupID: 0
			}
			this.points.push(point)
		}
	}

	/**
	 * Sets the amount of centroids to be used when calculating means
	 */
	public setCentroidAmount(amount: number) {
		this.centroidAmount = Math.max(amount, 1)
	}

	/**
	 * call after running the .calc() method to obtain a mapping of point IDs to their respective cluster.
	 * This can be used then for example to map indices in a indexstream
	 * @returns map of point id -> centroid id
	 */
	public createIDToGroupMapping() {
		const mapping: Map<number, number> = new Map()
		for (let p of this.points) {
			mapping.set(p.id, p.groupID)
		}

		return mapping
	}

	/**
	 * Actual calculation of kmeans. groups the points and moves means until convergence or maxIterations is reached.
	 */
	public calc(maxIterations = 1) {
		this.initializeMeans()
		this.centroidDistances()
		let iterations = 0;
		let notDone = true
		while (notDone) {
			iterations++
			notDone = this.assignPoints()
			this.moveMeans(true)
			this.centroidDistances()
			if (iterations >= maxIterations) {
				break;
			}
		}
	}

	/**
	 * Creates a color table based on the current grouping of points. Grouping order = color index order
	 * @param type Type of the returned color table
	 * @param useMeans Flag if the group mean should be used. If false, the point closest to the mean is used. True by default 
	 * @return a new colortable with as many colors as there are groups
	 */
	public createColors(useMeans = true) {
		const colors: number[] = []

		if (useMeans) {
			for (let i = 0; i < this.means.length; i++) {
				colors.push(Math.round(this.means[i][0]))
				colors.push(Math.round(this.means[i][1]))
				colors.push(Math.round(this.means[i][2]))
			}
		} else {
			const closest = this.closestToCenter()
			for (let i = 0; i < closest.length; i++) {
				colors.push(closest[i].color[0])
				colors.push(closest[i].color[1])
				colors.push(closest[i].color[2])
			}
		}
		return colors
	}

	/**
	 * returns a list of points such that per grouping the point closest to the groups mean is included
	 */
	private closestToCenter() {
		const minPoints: kMeanColorpoint[] = []
		for (let i = 0; i < this.means.length; i++) {
			const mean = this.means[i]
			let minPoint: kMeanColorpoint = { id: 0, groupID: 0, color: [0, 0, 0] };
			let minDist = 10000; //way too high distance so we def will have a change
			for (let point of this.points) {
				if (point.groupID === i) {
					const distance = colorPosterizer.distance(point.color, mean)
					if (distance < minDist) {
						minPoint = point
						minDist = distance
					}
				}
			}
			if (typeof minPoint === "undefined") {

			}
			minPoints.push({ id: minPoint!.id, groupID: minPoint!.groupID, color: [minPoint!.color[0], minPoint!.color[1], minPoint!.color[2]] })
		}
		return minPoints
	}

	/**
	 * Seeds as many mean points as we have clusters.
	 * Either uses r,g,b points, or grey ones
	 * @param grey flag to indivcate if grey points should be used
	 */
	private initializeMeans(grey = false) {
		this.means = []
		this.groupings.clear()

		// instead of using random points in the point cloud. We use pure red green and blue points
		if (!grey) {
			const addertoadder = Math.round(256 * 3 / this.centroidAmount)
			let adder = 0;
			for (let i = 0; i < this.centroidAmount; i++) {
				this.groupings.set(i, [])
				const color: [number, number, number] = [0, 0, 0]
				if (i % 3 === 0) {
					adder = Math.min(adder + addertoadder, 255)
				}
				switch (i % 3) {
					case 0:
						color[0] = adder
						break;
					case 1:
						color[1] = adder
						break;
					case 2:
						color[2] = adder
						break;
					default:
						break;
				}
				this.means.push(color)
				this.groupings.set(i, [])
			}
			if (this.centroidAmount === 256) { // edgecase where we would have the same color twice
				this.means[255] = [0, 0, 0]
			}

		} else {
			for (let i = 0; i < this.centroidAmount; i++) {
				const color: [number, number, number] = [i * (256 / this.centroidAmount), i * (256 / this.centroidAmount), i * (256 / this.centroidAmount)]
				this.means.push(color)
				this.groupings.set(i, [])
			}
		}
	}

	/**
	 * Moves each mean to the center of its cluster.
	 * @param usePoints flag to indicate if means should be set to nearest point of center instead of the center itself
	 */
	private moveMeans(usePoints = false) {
		for (let i = 0; i < this.means.length; i++) {

			const groupPoints = this.groupings.get(i)!
			if (groupPoints.length === 0) {
				continue
			}
			const meancolor: [number, number, number] = [0, 0, 0]
			//With high color pictures could this run into an overflow?
			for (let p of groupPoints) {
				meancolor[0] = meancolor[0] + p.color[0]
				meancolor[1] = meancolor[1] + p.color[1]
				meancolor[2] = meancolor[2] + p.color[2]
			}
			meancolor[0] = meancolor[0] / groupPoints.length
			meancolor[1] = meancolor[1] / groupPoints.length
			meancolor[2] = meancolor[2] / groupPoints.length
			this.means[i] = meancolor

			if (usePoints) {
				let minPoint = groupPoints[0];
				let minDist = colorPosterizer.distance(minPoint.color, this.means[i])

				for (let point of groupPoints) {
					const distance = colorPosterizer.distance(point.color, this.means[i])
					if (distance < minDist) {
						minPoint = point
						minDist = distance
					}
				}
				this.means[i] = minPoint.color
			}

			this.groupings.set(i, [])! //reset points of the centroid because assign points will fill them in again.
		}
	}

	/**
	 * Assigns points to clusters based on the current means.
	 * @returns true if any points have changed their cluster designation, else false.
	 */
	private assignPoints() {
		let clusterChange = false;
		for (let point of this.points) {
			const meansToCheck = this.meanDistances.get(point.groupID)! // [ID, distance]
			let minMeanIndex = point.groupID;
			let minDist = colorPosterizer.distance(point.color, this.means[point.groupID])
			const prevDistance = minDist;

			for (let i = 1; i < meansToCheck.length; i++) {
				if (meansToCheck[i][1] >= 4 * prevDistance) { // there can not be a mean closer to our point
					break;
				}
				const distance = colorPosterizer.distance(point.color, this.means[meansToCheck[i][0]])
				if (distance < minDist) {
					minMeanIndex = meansToCheck[i][0];
					minDist = distance
				}
			}
			const prevID = point.groupID
			point.groupID = minMeanIndex;
			this.groupings.get(minMeanIndex)!.push(point)

			if (point.groupID !== prevID) {
				clusterChange = true;
			}
		}
		return clusterChange
	}

	/**
	 * Calculates distances between centroids and stores them in ascending order. Needed for the triangle inequality speed up.
	 */
	private centroidDistances() {
		for (let i = 0; i < this.means.length; i++) {
			const distances: [number, number][] = []
			for (let j = 0; j < this.means.length; j++) { //we could cut this in half if we were smarter about it...
				distances.push([j, colorPosterizer.distance(this.means[i], this.means[j])])
			}
			distances.sort(
				(a, b) => a[1] - b[1]
			)
			this.meanDistances.set(i, distances)
		}
	}

}