source: spip-zone/_plugins_/filtres_images_vectorise/trunk/lib/geometrize/src/bitmap/DominantColours.php @ 116199

Last change on this file since 116199 was 116199, checked in by cedric@…, 21 months ago

Un plugin pour vectoriser en SVG des images bitmap, qui propose 4 nouveaux filtres

  • extraire_palette_couleurs permet d'extraire une palette de couleur d'une image (par defaut les 3 couleurs les plus representees) en utilisant un calcul des couleurs dominantes par partitionnement en k-moyennes

`
<BOUCLE_palette(POUR){tableau #FICHIER|extraire_palette_couleurs{3}}>
<div style="display: inline-block;width: 30px;height: 15px;background-color: #VALEUR;"></div>
</BOUCLE_palette>
`

  • image_geometrize permet de creer une image SVG approchante de l'image d'origine en utilisant le lib GeometrizePHP https://github.com/Cerdic/geometrize-php/ (attention methode gourmande en temps de calcul)
  • image_potrace permet de generer un trace SVG depuis l'image d'origine, a l'aide de Potracio PHP qui est un portage PHP de PotRace? https://seenthis.net/messages/645575
  • image_geopotrize combine les 2 techniques : un background geometrize qui n'a pas besoin d'un grand nombre de shapes et un trace potrace superpose/mixe

Les 3 filtres ont tout un tas d'option pour qui veut jouer avec, mais les reglages par defaut permettent d'avoir immediatement un joli resultat exploitable
A noter que pour image_geometrize, le temps de calcul peut depasser les 30s pour generer le nombre de shapes demandees, selon les reglages utilises.
Dans ce cas le calcul est arrete au bout de 20s, on stocke et on renvoie l'image provisoire incomplete, et on stocke l'etat du calcul qui reprendra au prochain calcul de la page.

(J'evite les screenshots dans le message de commit mais le coeur y est)

File size: 5.3 KB
Line 
1<?php
2
3namespace Cerdic\Geometrize\Bitmap;
4
5use \Cerdic\Geometrize\Bitmap;
6
7/**
8 * Dominant colours by k means derived from code by Charles Leifer at:
9 *   http://charlesleifer.com/blog/using-python-and-k-means-to-find-the-dominant-colors-in-images/
10 *
11 * Greatly Forked from
12 *   https://gist.github.com/pgchamberlin/7092958
13 *
14 */
15class DominantColours {
16
17        /**
18         * @param int $nbColors
19         *   number of Colors we want to extract
20         * @param Bitmap $target
21         *   target Bitmap
22         * @param array $lines
23         *   scanlines of the shape in the target Bitmap
24         * @return array
25         */
26        static public function dominantColours($nbColors, $target, $lines) {
27                $points = [];
28                foreach($lines as $line){
29                        $y = $line['y'];
30                        for ($x=$line['x1']; $x<=$line['x2']; $x++) {
31                                $points[] = $t = $target->data[$y][$x];
32                        }
33                }
34
35                $clusters = DominantColours::kMeans($points, $nbColors);
36
37                $colours = [];
38                foreach ($clusters as $cluster) {
39                        $center = $cluster[0];
40                        $nbPoints = count($cluster[1]);
41                        $colours[$center] = $nbPoints;
42                }
43
44                arsort($colours);
45                return array_keys($colours);
46        }
47
48        /**
49         * kMeans algorithm
50         * @param array $points
51         * @param int $nbClusters
52         * @return array
53         */
54        static protected function kMeans($points, $nbClusters){
55                $clusters = array();
56
57                // start with enough clusters to avoid too near points
58                $shuffle = array_keys($points);
59                shuffle($shuffle);
60                $seen = [];
61                $refused = 0;
62                while (count($clusters)<$nbClusters+10 && count($shuffle)){
63                        $index = array_shift($shuffle);
64                        if (!isset($seen[$points[$index]])
65                          && (!count($clusters) || DominantColours::minDistanceBetween($points[$index], array_column($clusters, 0))>5 || $refused++>$nbClusters)
66                        ) {
67                                $seen[$points[$index]] = true;
68                                $clusters[] = [$points[$index], []];
69                        }
70                }
71
72                // initial cluster distribution
73                $distribute = DominantColours::distributePoints($points, $clusters);
74                foreach ($distribute as $indexPoint => $indexCluster) {
75                        $clusters[$indexCluster][1][] = $points[$indexPoint];
76                }
77
78                $maxIter = 50; // avoid infinite loop
79                while ($maxIter-->0){
80
81                        // compute center of each clusters and create new clusters
82                        $newClusters = [];
83                        $nbSmallest = null;
84                        $indexSmallest = null;
85                        $remove = true;
86                        foreach ($clusters as $index => $cluster) {
87                                $center = DominantColours::centerOfPoints($cluster[1]);
88                                if (!count($newClusters) || DominantColours::minDistanceBetween($center, array_column($newClusters, 0))>20) {
89                                        $newClusters[] = [$center, []];
90                                        if (is_null($indexSmallest) or count($cluster[1])<$nbSmallest) {
91                                                $indexSmallest = $index;
92                                                $nbSmallest = count($cluster[1]);
93                                        }
94                                }
95                                else {
96                                        $remove = false;
97                                }
98                        }
99                        // remove the smallest cluster if still too many
100                        if ($remove && count($newClusters)>$nbClusters) {
101                                unset($newClusters[$indexSmallest]);
102                        }
103
104                        // redistribute along new clusters and watch for any changement
105                        $changed = false;
106                        foreach ($clusters as $indexCluster => $cluster) {
107                                $distribute = DominantColours::distributePoints($cluster[1], $newClusters);
108                                if (count(array_diff($distribute, [$indexCluster]))) {
109                                        $changed = true;
110                                        $countChanged = 0;
111                                        foreach ($distribute as $indexPoint => $indexNewCluster) {
112                                                $newClusters[$indexNewCluster][1][] = $cluster[1][$indexPoint];
113                                                if ($indexNewCluster !== $indexCluster) {
114                                                        $countChanged++;
115                                                }
116                                        }
117                                }
118                                else {
119                                        // unchanged points
120                                        $newClusters[$indexCluster][1] = $cluster[1];
121                                }
122                        }
123
124                        $clusters = $newClusters;
125
126                        if (!$changed) {
127                                break;
128                        }
129                }
130
131                return $clusters;
132        }
133
134        /**
135         * Distribute points into given clusters
136         * @param array $points
137         * @param array $clusters
138         * @return array
139         */
140        static protected function distributePoints($points, $clusters) {
141                $distribute = [];
142                foreach ($points as $indexPoint => $p) {
143                        $bestDistance = null;
144                        foreach ($clusters as $indexCluster => $cluster) {
145                                $e = 0;
146                                foreach ([24,16,8,0] as $k){
147                                        $dk = ($p>>$k & 255)-($cluster[0]>>$k & 255);
148                                        if ($dk<0){
149                                                $dk *= -1;
150                                        }
151                                        $e += $dk;
152                                }
153                                if (is_null($bestDistance) or $e < $bestDistance) {
154                                        $distribute[$indexPoint] = $indexCluster;
155                                        $bestDistance = $e;
156                                }
157                        }
158                }
159                return $distribute;
160        }
161
162        /**
163         * Determine the mean center of an array of points
164         * @param $points
165         * @return int
166         */
167        static protected function centerOfPoints($points) {
168                $center = [24 => 0, 16 => 0, 8 => 0, 0=>0];
169                foreach ($points as $p){
170                        foreach ([24,16,8,0] as $k){
171                                $center[$k] += ($p>>$k & 255);
172                        }
173                }
174                $nbPoints = count($points);
175                $c = 0;
176                foreach ($center as $k => $v) {
177                        $v = round($v / $nbPoints);
178                        $c += ($v&255) << $k;
179                }
180                return $c;
181        }
182
183        /**
184         * Find the smallest distance between a point and an array of points
185         * @param int $p1
186         * @param array $points
187         * @return float
188         */
189        static protected function minDistanceBetween($p1, $points) {
190                $min = null;
191                foreach ($points as $p) {
192                        $e = 0;
193                        foreach ([24,16,8,0] as $k){
194                                $dk = ($p1>>$k & 255)-($p>>$k & 255);
195                                if ($dk<0){
196                                        $dk *= -1;
197                                }
198                                $e += $dk;
199                        }
200                        if (is_null($min) or $e < $min) {
201                                $min = $e;
202                        }
203                }
204                return $e / 4;
205        }
206
207        /**
208         * Compute distance between 2 points
209         * @param int $p1
210         * @param int $p2
211         * @return float|int
212         */
213        static protected function distanceBetween($p1, $p2) {
214                $e = 0;
215                foreach ([24,16,8,0] as $k){
216                        $dk = ($p1>>$k & 255)-($p2>>$k & 255);
217                        if ($dk<0){
218                                $dk *= -1;
219                        }
220                        $e += $dk;
221                }
222                return $e / 4;
223        }
224}
Note: See TracBrowser for help on using the repository browser.