Message Boards

GROUPS:

Anton Antonov

Re-exploring the structure of Chinese character images

Anton Antonov, Accendo Data LLC

Posted 4 months ago

2760 Views

12 Replies

25 Total Likes

Follow this post

Re-exploring the structure of Chinese character images
by Anton Antonov
MathematicaForPrediction at WordPress
MathematicaForPrediction at GitHub
April 2022

Version 0.8

Introduction

In this notebook we show information retrieval and clustering techniques over images of Unicode collection of Chinese characters. Here is the outline of notebook's exposition:

Get Chinese character images.

Cluster "image vectors" and demonstrate that the obtained clusters have certain explainability elements.

Apply Latent Semantic Analysis (LSA) workflow to the character set.

Show visual thesaurus through a recommender system. (That uses Cosine similarity.)

Discuss graph and hierarchical clustering using LSA matrix factors.

Demonstrate approximation of "unseen" character images with an image basis obtained through LSA over a small set of (simple) images.

Redo character approximation with more "interpretable" image basis.

Remark: This notebook started as an (extended) comment for the Community discussion "Exploring structure of Chinese characters through image processing", [SH1]. (Hence the title.)

Get Chinese character images

This code is a copy of the code in the original Community post by Silvia Hao, [SH1]:

In[]:=

ClearAll[pipe,branch,branchSeq]pipe=RightComposition;branch=Through@*{##}&;branchSeq=pipe[branch[##],Apply[Sequence]]&;ClearAll[λ,ppImg](*assumeIusemyfirstmonitor:*)λ=1/First[Lookup["Scale"][SystemInformation["Devices","ConnectedDisplays"]]];ppImg[magF_:1]:=FunctionModule{nbMgfy=AbsoluteCurrentValue[EvaluationNotebook[],Magnification],$width=Part[ImageDimensions@#,1]},Image#,ImageSize->

magFλ$width

nbMgfy



In[]:=

Module[{fsize=50,width=64,height=64},lsCharIDs=Map[FromCharacterCode[#,"Unicode"]&,16^^4E00-1+Range[widthheight]];]

In[]:=

charPage=Module[{fsize=50,width=64,height=64},16^^4E00-1+Range[widthheight]//pipe[FromCharacterCode[#,"Unicode"]&,Characters,Partition[#,width]&,Grid[#,BackgroundBlack,Spacings{0,0},ItemSize{1.5,1.2},Alignment{Center,Center},FrameAll,FrameStyleDirective[Red,AbsoluteThickness[3λ]]]&,Style[#,White,fsize,FontFamily"Source Han Sans CN",FontWeight"ExtraLight"]&,Rasterize[#,BackgroundBlack]&]];chargrid=charPage//ColorDistance[#,Red]&//Image[#,"Byte"]&//Sign//Erosion[#,5]&;lmat=chargrid//MorphologicalComponents[#,Method"BoundingBox",CornerNeighborsFalse]&;chars=ComponentMeasurements[{charPage//ColorConvert[#,"Grayscale"]&,lmat},"MaskedImage",#Width>10&]//Values//Map@RemoveAlphaChannel;chars=Module[{size=chars//Map@ImageDimensions//Max},ImageCrop[#,{size,size}]&/@chars];

Here is a sample of the obtained images:

SeedRandom[33];RandomSample[chars,5]

Out[]=





Vector representation of images

Define a function that represents an image into a linear vector space (of pixels):

In[]:=

Clear[ImageToVector];ImageToVector[img_Image]:=Flatten[ImageData[ColorConvert[img,"Grayscale"]]];ImageToVector[img_Image,imgSize_]:=Flatten[ImageData[ColorConvert[ImageResize[img,imgSize],"Grayscale"]]];ImageToVector[___]:=$Failed;

Show how vector represented images look like:

Table[BlockRandom[img=RandomChoice[chars];ListPlot[ImageToVector[img],FillingAxis,PlotRange->All,PlotLabelimg,ImageSizeMedium,AspectRatio1/6],RandomSeedingrs],{rs,{33,998}}]

Out[]=







Data preparation

In this section we represent the images into a linear vector space. (In which each pixel is a basis vector.)

Make an association with images:

aCImages=AssociationThread[lsCharIDs->chars];Length[aCImages]

Out[]=

4096

Make flat vectors with the images:

AbsoluteTiming[aCImageVecs=ParallelMap[ImageToVector,aCImages];]

Out[]=

{0.998162,Null}

Do matrix plots a random sample of the image vectors:

SeedRandom[32];MatrixPlot[Partition[#,ImageDimensions[aCImages〚1〛]〚2〛]]&/@RandomSample[aCImageVecs,6]

Out[]=

垖

,埄

,媭

,垝

,偭

,効



Clustering over the image vectors

In this section we cluster "image vectors" and demonstrate that the obtained clusters have certain explainability elements. Expected Chinese character radicals are observed using image multiplication.

Cluster the image vectors and show summary of the clusters lengths:

SparseArray[Values@aCImageVecs]

Out[]=

SparseArray



Specified elements: 4658698

Dimensions: {4096,2500}

Data not in notebook. Store now



SeedRandom[334];AbsoluteTiming[lsClusters=FindClusters[SparseArray[Values@aCImageVecs]->Keys[aCImageVecs],35,Method->{"KMeans"}];]Length@lsClustersResourceFunction["RecordsSummary"][Length/@lsClusters]

Out[]=

{24.6383,Null}

Out[]=



1 column 1

Min	17
1st Qu	79.75
Mean	117.029
Median	118
3rd Qu	146.75
Max	225



For each cluster:

◼

Take 30 different small samples of 7 images

◼

Multiply the images in each small sample

◼

Show three "most black" the multiplication results

SeedRandom[33];Table[i->TakeLargestBy[Table[ImageMultiply@@RandomSample[KeyTake[aCImages,lsClusters〚i〛],UpTo[7]],30],Total@ImageToVector[#]&,3],{i,Length[lsClusters]}]

Out[]=

1

,2

,3

,4

,5

,6

,7

,8

,9

,10

,11

,12

,13

,14

,15

,16

,17

,18

,19

,20

,21

,22

,23

,24

,25

,26

,27

,28

,29

,30

,31

,32

,33

,34

,35



Remark: We can see that the clustering above produced "semantic" clusters -- most of the multiplied images show meaningful Chinese characters radicals and their "expected positions."

Here is one of the clusters with the radical "mouth":

KeyTake[aCImages,lsClusters〚26〛]

Out[]=

卟

,収

,叨

,叫

,叮

,叱

,叶

,叹

,叺

,叻

,叼

,叿

,吀

,吁

,吃

,吅

,吆

,吇

,吋

,吐

,吒

,吓

,吖

,吗

,吘

,吜

,吟

,吥

,吧

,听

,吭

,吽

,呀

,呌

,呍

,呓

,呕

,呛

,呜

,呞

,呟

,呧

,呪

,呫

,呮

,呯

,呵

,呷

,呸

,呺

,呾

,咀

,咊

,咋

,咍

,咓

,咔

,咟

,咡

,咥

,咶

,咺

,哏

,哙

,哣

,哩

,哹

,哻

,唂

,唈

,唔

,唱

,啀

,喣

,屔



LSAMon application

In this section we apply the "standard" LSA workflow, [AA1, AA4].

Make a matrix with named rows and columns from the image vectors:

mat=ToSSparseMatrix[SparseArray[Values@aCImageVecs],"RowNames"->Keys[aCImageVecs],"ColumnNames"->Automatic]

Out[]=

SparseArray



Specified elements: 4658698

Dimensions: {4096,2500}

Data not in notebook. Store now



The following Latent Semantic Analysis (LSA) monadic pipeline is used in [AA2, AA2]:

SeedRandom[77];AbsoluteTiming[lsaAllObj=LSAMonUnit[]⟹LSAMonSetDocumentTermMatrix[mat]⟹LSAMonApplyTermWeightFunctions["None","None","Cosine"]⟹LSAMonExtractTopics["NumberOfTopics"60,Method"SVD","MaxSteps"15,"MinNumberOfDocumentsPerTerm"0]⟹LSAMonNormalizeMatrixProduct[NormalizedRight]⟹LSAMonEcho[Style["Obtained basis:",Bold,Purple]]⟹LSAMonEchoFunctionContext[ImageAdjust[Image[Partition[#,ImageDimensions[aCImages〚1〛]〚1〛]]]&/@SparseArray[#H]&];]

Obtained basis:





Out[]=

{7.60828,Null}

Remark: LSAMon's corresponding theory and design are discussed in [AA1, AA4]:

Get the representation matrix:

W2=lsaAllObj⟹LSAMonNormalizeMatrixProduct[Normalized->Right]⟹LSAMonTakeW

Out[]=

SparseArray



Specified elements: 245760

Dimensions: {4096,60}

Data not in notebook. Store now



Get the topics matrix:

H=lsaAllObj⟹LSAMonNormalizeMatrixProduct[Normalized->Right]⟹LSAMonTakeH

Out[]=

SparseArray



Specified elements: 138002

Dimensions: {60,2500}

Data not in notebook. Store now



Cluster the reduced dimension representations and show summary of the clusters lengths:

AbsoluteTiming[lsClusters=FindClusters[Normal[SparseArray[W2]]->RowNames[W2],40,Method->{"KMeans"}];]Length@lsClustersResourceFunction["RecordsSummary"][Length/@lsClusters]

Out[]=

{2.33331,Null}

Out[]=



1 column 1

Min	26
1st Qu	59
Median	96.5
Mean	102.4
3rd Qu	142
Max	200



Show cluster interpretations:

AbsoluteTiming[aAutoRadicals=Association@Table[i->TakeLargestBy[Table[ImageMultiply@@RandomSample[KeyTake[aCImages,lsClusters〚i〛],UpTo[8]],30],Total@ImageToVector[#]&,3],{i,Length[lsClusters]}];]aAutoRadicals

Out[]=

{0.878406,Null}

Out[]=

1

,2

,3

,4

,5

,6

,7

,8

,9

,10

,11

,12

,13

,14

,15

,16

,17

,18

,19

,20

,21

,22

,23

,24

,25

,26

,27

,28

,29

,30

,31

,32

,33

,34

,35

,36

,37

,38

,39

,40



Using FeatureExtraction

I experimented with clustering and approximation using WL's function FeatureExtraction. Result are fairly similar as the above; timings a different (a few times slower.)

Visual thesaurus

In this section we use Cosine similarity to find visual nearest neighbors of Chinese character images.

In[]:=

matPixels=WeightTermsOfSSparseMatrix[lsaAllObj⟹LSAMonTakeWeightedDocumentTermMatrix,"IDF","None","Cosine"];matTopics=WeightTermsOfSSparseMatrix[lsaAllObj⟹LSAMonNormalizeMatrixProduct[Normalized->Left]⟹LSAMonTakeW,"None","None","Cosine"];

In[]:=

smrObj=SMRMonUnit[]⟹SMRMonCreate[<|"Topic"->matTopics,"Pixel"->matPixels|>];

Consider the character "團":

aCImages["團"]

Out[]=

Here are the nearest neighbors for that character found by using both image topics and image pixels:

(*focusItem=RandomChoice[Keys@aCImages];*)focusItem="團","仼","呔"1;smrObj⟹SMRMonEcho[Style["Nearest neighbors by pixel topics:",Bold,Purple]]⟹SMRMonSetTagTypeWeights[<|"Topic"->1,"Pixel"->0|>]⟹SMRMonRecommend[focusItem,8,"RemoveHistory"->False]⟹SMRMonEchoValue⟹SMRMonEchoFunctionValue[AssociationThread[Values@KeyTake[aCImages,Keys[#]],Values[#]]&]⟹SMRMonEcho[Style["Nearest neighbors by pixels:",Bold,Purple]]⟹SMRMonSetTagTypeWeights[<|"Topic"->0,"Pixel"->1|>]⟹SMRMonRecommend[focusItem,8,"RemoveHistory"->False]⟹SMRMonEchoFunctionValue[AssociationThread[Values@KeyTake[aCImages,Keys[#]],Values[#]]&];

Nearest neighbors by pixel topics:

value:團1.,圑0.831716,圕0.826445,圊0.75788,圈0.73557,圏0.718088,圚0.691223,圓0.670589



1.,

0.831716,

0.826445,

0.75788,

0.73557,

0.718088,

0.691223,

0.670589

Nearest neighbors by pixels:



1.,

0.914661,

0.904474,

0.890879,

0.889363,

0.881746,

0.881071,

0.879139

Remark: Of course, in the recommender pipeline above we can use both pixels and pixels topics. (With their contributions being weighted.)

Graph clustering

In this section we demonstrate the use of graph communities to find similar groups of Chinese characters.

Here we take a sub-matrix of the reduced dimension matrix computed above:

In[]:=

W=lsaAllObj⟹LSAMonNormalizeMatrixProduct[Normalized->Right]⟹LSAMonTakeW;

Here we find the similarity matrix between the characters and remove entries corresponding to "small" similarities:

In[]:=

matSym=Clip[W.Transpose[W],{0.78,1},{0,1}];

Here we plot the obtained (clipped) similarity matrix:

MatrixPlot[matSym]

Out[]=

Here we:

◼

Take array rules of the sparse similarity matrix

◼

Drop the rules corresponding to the diagonal elements

◼

Convert the keys of rules into uni-directed graph edges

◼

Make the corresponding graph

◼

Find graph's connected components

◼

Show the number of connected components

◼

Show a tally of the number of nodes in the components

gr=Graph[UndirectedEdge@@@DeleteCases[Union[Sort/@Keys[SSparseMatrixAssociation[matSym]]],{x_,x_}]];lsComps=ConnectedComponents[gr];Length[lsComps]ReverseSortBy[Tally[Length/@lsComps],First]

Out[]=

138

Out[]=

{{1839,1},{31,1},{27,1},{16,1},{11,2},{9,2},{8,1},{7,1},{6,5},{5,3},{4,8},{3,14},{2,98}}

Here we demonstrate the clusters of Chinese characters make sense:

aPrettyRules=Dispatch[Map[#->Style[#,FontSize36]&,Keys[aCImages]]];CommunityGraphPlot[Subgraph[gr,TakeLargestBy[lsComps,Length,10]〚2〛],Method->"SpringElectrical",VertexLabels->Placed["Name",Above],AspectRatio1,ImageSize1000]/.aPrettyRules

Out[]=

Remark: By careful observation of the clusters and graph connections we can convince ourselves that the similarities are based on pictorial sub-elements (i.e. radicals) of the characters.

Hierarchical clustering

In this section we apply hierarchical clustering to the reduced dimension representation of the Chinese character images.

Here we pick a cluster:

lsFocusIDs=lsClusters〚12〛;Magnify[ImageCollage[Values[KeyTake[aCImages,lsFocusIDs]]],0.4]

Here is how we can make a dendrogram plot (not that useful here):

In[]:=

(*smat=W2〚lsClusters〚13〛,All〛;Dendrogram[Thread[Normal[SparseArray[smat]]->Map[Style[#,FontSize16]&,RowNames[smat]]],Top,DistanceFunctionEuclideanDistance]*)

Here is a heat-map plot with hierarchical clustering dendrogram (with tool-tips):

gr=HeatmapPlot[W2〚lsFocusIDs,All〛,DistanceFunction->{CosineDistance,None},Dendrogram{True,False}];gr/.Map[#->Tooltip[Style[#,FontSize16],Style[#,Bold,FontSize36]]&,lsFocusIDs]

Out[]=

Remark: The plot above has tooltips with larger character images.

Representing all characters with smaller set of basic ones

In this section we demonstrate that a relatively small set of simpler Chinese character images can be used to represent (or approxumate) the rest of the images.

Remark: We use the following heuristic: the simpler Chinese characters have the smallest amount of white pixels.

Obtain a training set of images -- that are the darkest -- and show a sample of that set :

{trainingInds,testingInds}=TakeDrop[Keys[SortBy[aCImages,Total[ImageToVector[#]]&]],800];SeedRandom[3];RandomSample[KeyTake[aCImages,trainingInds],12]

Out[]=

冶

,孒

,亍

,刓

,伡

,呂

,古

,呔

,岳

,冎

,众

,宎



Show all training characters with an image collage:

Magnify[ImageCollage[Values[KeyTake[aCImages,trainingInds]],BackgroundGray,ImagePadding1],0.4]

Apply LSA monadic pipeline with the training characters only:

SeedRandom[77];AbsoluteTiming[lsaPartialObj=LSAMonUnit[]⟹LSAMonSetDocumentTermMatrix[SparseArray[Values@KeyTake[aCImageVecs,trainingInds]]]⟹LSAMonApplyTermWeightFunctions["None","None","Cosine"]⟹LSAMonExtractTopics["NumberOfTopics"80,Method"SVD","MaxSteps"120,"MinNumb