Accelerating MCR-ALS decomposition of hyperspectral images using k-means clustering

Abstract

A hyperspectral image may be decomposed into component spectra and their distri-
bution in the image to simplify analysis by revealing underlying patterns and reducing the dimensionality of the image; this may be achieved by the algorithm MCR-ALS. However, the algorithm is time consuming, but could be accelerated by a data re-
duction. Data reduction can be done by using a clustering method. In this project,
the aim is to determine how clustering, k-means in particular, can be incorporated
with MCR-ALS to achieve an accelerated decomposition.

We measured how different losses and time consumption were influenced by different
parameter choices, e.g, initialization of the k-means. Clustering can result in a re-
duction in the time-consumption independently of the choice of parameters, but the
choices altered the decomposition substantially.

From the results, we concluded that k-means can be incorporated into MCR-ALS,
and that the method for selection of centroids is the most crucial step. Accordingly,
an optimal set of parameters could be determined.

Popular Abstract (Swedish)

Att analysera livets biokemi, kemin bakom biologiska processer, är viktigt för att få en förståelse av livets mekanismer, speciellt för små längdskalor. Biokemin hos olika typer av celler skiljer sig åt, vilket kan användas för att t.ex skilja mellan elakartade och icke-elakartade tumörer. Vilka ämnen som finns i en cell kan bli identifierade via deras respektive absorptionspektrum. Ett absorptionsspektrum berättar hur stor andel av en specifik våglängd av ljus som har absorberats och är unik för varje ämne. Så kallade hyperspektrala bilder, bilder där pixlar representerar var sitt absorptionsspektrum, är tagna för att spåra ämnena. Dock finns det ett problem: ämnena i bilden är blandade och därför är spektrumen från ämnena också blandade. Det bildas en `soppa’ av kemikaliernas spektrum som gör det svårt att särskilja olika ämnen.

Denna ‘soppa’ av spektrum kan ‘oblandas’ och uppdelas i ‘rena' spektrum och bilder som representerar hur de spektrumen är ‘blandade’ med diverse olika metoder. MCR-ALS är en metod som gör just detta. Ett problem med MCR-ALS är att när en bild blir större med högre upplösning hos dess spektra, tar det längre tid för algoritmen att ‘oblanda’ bilden. Det förekommer att större uppsättningar bilder ska analyseras samtidigt, vilket ökar tidsåtgången ännu mer. En tidsreduktion kan ske genom att utnyttja det faktum att många spektrum är likadana och kan därmed representeras med ett spektrum, vilket minskar mängden data som behövs arbetas med. En sådan gruppering kan göras med hjälp av en klustrings-algoritm.

Klustring är ett begrepp som omfattar alla typer av data-reduktion som automatiskt sorterar data i grupper. Dessa grupper kan sedan representeras av så kallade centroider. Dock, ett problem med klustring är att det inte bevarar data perfekt och kräver tid utöver steget då spektran ‘oblandas’, som beror på det valda antalet centroider. Konsekvenserna kan liknas med en sammanfattning av en film. Har man med för många detaljer hade det tagit kortare tid att se filmen, men om man har för lite detaljer försvinner filmens andemening. I vårt arbete har vi utvecklat en metod när man arbetar med klustrad data i MCR-ALS, namngiven CAM-A, och studerar vilka effekter uppstår av olika val av parametrar.

• author: Kull, Eric
• supervisor: Carl Troein
• organization: Computational Biology and Biological Physics - Undergoing reorganization
• course: FYTK02 20221
• year: 2022
• type: M2 - Bachelor Degree
• subject: Physics and Astronomy
• keywords: k-means, clustering, MCR-ALS, hyperspectral image
• report number: 22-31
• language: English
• id: 9090347
• date added to LUP: 2022-06-23 11:26:25
• date last changed: 2022-06-29 14:32:09