/usr/share/pyshared/gamera/plugins/geometry.py is in python-gamera 3.3.2-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 | #
# Copyright (C) 2009-2011 Christoph Dalitz
# 2010 Oliver Christen, Tobias Bolten
# 2011 Christian Brandt
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
#
from gamera.plugin import *
from gamera.args import NoneDefault
import _geometry
try:
from gamera.core import RGBPixel
except:
def RGBPixel(*args):
pass
class voronoi_from_labeled_image(PluginFunction):
u"""
Computes the area Voronoi tesselation from an image containing labeled
Cc's. In the returned onebit image, every pixel is labeled with the
label value of the closest Cc in the input image.
To prepare the input image, you can use cc_analysis__. When the Cc's
only consist of single points, the area Voronoi tesselation is identical
to the ordinary Voronoi tesselation.
.. __: segmentation.html#cc-analysis
The implementation applies a watershed algorithm to the distance transform
of the input image, a method known as *seeded region growing* (U. K\u00f6the:
*Primary Image Segmentation.* Proceedings 17th DAGM-Symposium, pp. 554-561,
Springer, 1995).
The example shown below is the image *voronoi_cells* as created with
the the following code:
.. code:: Python
# create an area Voronoi tesselation and
# mark the cells and their edges in color
ccs = image.cc_analysis() # labels the image
voronoi = image.voronoi_from_labeled_image()
voronoi_cells = voronoi.color_ccs()
voronoi_cells.highlight(image, RGBPixel(0,0,0))
voronoi_edges = voronoi.labeled_region_edges()
voronoi_cells.highlight(voronoi_edges, RGBPixel(255,255,255))
"""
self_type = ImageType([ONEBIT,GREYSCALE])
return_type = ImageType([ONEBIT,GREYSCALE])
def __doc_example1__(images):
image = images[ONEBIT]
ccs = image.cc_analysis()
voronoi = image.voronoi_from_labeled_image()
voronoi_cells = voronoi.color_ccs()
voronoi_cells.highlight(image, RGBPixel(0,0,0))
voronoi_edges = voronoi.labeled_region_edges()
voronoi_cells.highlight(voronoi_edges, RGBPixel(255,255,255))
return [image, voronoi_cells]
doc_examples = [__doc_example1__]
author = u"Christoph Dalitz, based on code by Ullrich K\u00f6the"
class voronoi_from_points(PluginFunction):
"""
Computes the Voronoi tesselation from a list of points and point labels.
The result is directly written to the input image. Each white pixel is
labeled with the label value of the closest point. Non white pixel in the
input image are not overwritten.
The arguments *points* and *labels* specify the points and labels, such
that ``labels[i]`` is the label of ``points[i]``. Note that the labels
need not necessarily all be different, which can be useful as an
approximation of an area Voronoi tesselation.
The algorithm is very simple: it stores the points in a `kd-tree`_ and
then looks up the closest point for each image pixel. This has a runtime
of *O(N log(n))*, where *N* is the number of image pixels and *n* is the
number of points. For not too many points, this should be faster than the
morphological region growing approach of `voronoi_from_labeled_image`_.
.. _`kd-tree`: kdtree.html
.. _`voronoi_from_labeled_image`: #voronoi-from-labeled-image
The example shown below is the image *voronoi_edges* as created with
the the following code:
.. code:: Python
# create a Voronoi tesselation and mark
# the cell edges in a second image
points = [(10,10),(20,30),(32,22),(85,14),(40,70),(80,85)]
voronoi = Image((0,0),(90,90))
voronoi.voronoi_from_points(points,[i+2 for i in range(len(points))])
voronoi_edges = voronoi.labeled_region_edges()
for p in points:
voronoi_edges.set(p,1)
"""
self_type = ImageType([ONEBIT,GREYSCALE])
args = Args([PointVector("points"),IntVector("labels")])
return_type = None
def __doc_example1__(images):
from gamera.core import Image
points = [(10,10),(20,30),(32,22),(85,14),(40,70),(80,85)]
voronoi = Image((0,0),(90,90))
voronoi.voronoi_from_points(points,[i+2 for i in range(len(points))])
voronoi_edges = voronoi.labeled_region_edges()
for p in points:
voronoi_edges.set(p,1)
return [voronoi_edges]
doc_examples = [__doc_example1__]
author = "Christoph Dalitz"
class labeled_region_neighbors(PluginFunction):
"""
For an image containing labeled regions, a list of all label pairs belonging
to touching regions is returned. When *eight_connectivity* is ``True``
(default), 8-connectivity is used for neighborship, otherwise
4-connectivity is used.
This can be useful for building a Delaunay graph from a Voronoi tesselation
as in the following example:
.. code:: Python
#
# build Delaunay graph of neighboring (i.e. adjacent) Cc's
#
# create map label->Cc for faster lookup later
ccs = image.cc_analysis()
label_to_cc = {}
for c in ccs:
label_to_cc[c.label] = c
# compute area Voronoi tesselation and neighborship list
voronoi = image.voronoi_from_labeled_image()
labelpairs = voronoi.labeled_region_neighbors()
# build map of all neighbors for each label for fast lookup
neighbors = {}
for label in label_to_cc.keys():
neighbors[label] = []
for n in labelpairs:
neighbors[n[0]].append(n[1])
neighbors[n[1]].append(n[0])
# now, all neighbors to a given cc can be looked up with
neighbors_of_cc = [label_to_cc[label] for label in neighbors[cc.label]]
"""
self_type = ImageType([ONEBIT])
args = Args([Check("eight_connectivity",default=True)])
return_type = Class("labelpairs")
author = "Christoph Dalitz"
# wrapper for passing default argument
def __call__(self, eight_connectivity=True):
return _geometry.labeled_region_neighbors(self, eight_connectivity)
__call__ = staticmethod(__call__)
class delaunay_from_points(PluginFunction):
"""
Computes the Delaunay triangulation directly from a list of points and
point labels. The result is a list which contains tuples of adjacent labels,
where in each tuple the smaller label is given first.
The arguments *points* and *labels* specify the points and nonnegative
labels, such that ``labels[i]`` is the label of ``points[i]``. Note that
the labels need not necessarily all be different, which can be useful
for the computation of a neighborship graph from a set of connected
components.
The computation of the Delaunay triangulation is based on the Delaunay
tree which is a randomized geometric data structure. It is
described in O. Devillers, S. Meiser, M. Teillaud:
`Fully dynamic Delaunay triangulation in logarithmic expected time per operation.`__
Computational Geometry: Theory and Applications 2, pp. 55-80, 1992.
.. __: http://hal.inria.fr/inria-00090678
This can be useful for building a neighborhood graph as shown in the
following example:
.. code:: Python
from gamera import graph
from gamera.plugins.geometry import delaunay_from_points
points = [(10,10),(20,30),(32,22),(85,14),(40,70),(80,85)]
labels = range(len(points))
neighbors = delaunay_from_points(points, labels)
g = graph.Graph(graph.UNDIRECTED)
for pair in neighbors:
g.add_edge(pair[0], pair[1])
"""
self_type = None
args = Args([PointVector("points"), IntVector("labels")])
return_type = Class("labelpairs")
author = "Oliver Christen (based on code by Olivier Devillers)"
class graph_color_ccs(PluginFunction):
"""
Returns an RGB Image where each segment is colored with one of the colors
from *colors* with the constraint that segments adjacent in the
neighborship graph have different colors.
This function can be used to verify that the pagesegmentation
e.g. ``runlength_smearing`` is working correctly for your image.
For coloring the Gamera graph library is used. For more information on the
coloring algorithm see Graph.colorize__
.. __: graph.html#colorize
*ccs*:
ImageList which contains ccs to be colored. Must be views on
the image on which this method is called.
*colors*:
list of colors (instances of RGBPixel) which will be used for coloring.
When ``None``, the default set of seven colors given in the example
below is used.
*method*:
Controls the calculation of the neighborhood graph:
0 = from the CC center points
(fastest, but can be inaccurate for large CC's)
1 = from a 20 percent sample of the contour points
(reasonable compromise between speed and accuracy)
2 = from the exact area Voronoi diagram
(can be slow on large images)
.. code:: Python
ccs = imgage.cc_analysis()
colors = [ RGBPixel(150, 0, 0),
RGBPixel(0, 250, 0),
RGBPixel(0, 0, 255),
RGBPixel(250, 0, 255),
RGBPixel(50, 150, 50),
RGBPixel(0, 190, 255),
RGBPixel(230, 190, 20) ]
rgb = imgage.mycolor_ccs(ccs, colors, 1)
.. note:: *colors* may not contain less than six colors.
"""
category = "Color"
author = "Oliver Christen and Tobias Bolten"
args = Args([ImageList('ccs'), Class('colors', klass=RGBPixel, list_of=True,default=NoneDefault), Choice('method', ["CC center", "20% contour points", "voronoi diagram"], default=1)])
self_type = ImageType([ONEBIT])
return_type = ImageType([RGB])
def __call__(image, ccs, colors=None, method=1):
if colors == None:
from gamera.core import RGBPixel
colors = [ RGBPixel(150, 0, 0),
RGBPixel(0, 250, 0),
RGBPixel(0, 0, 255),
RGBPixel(250, 0, 255),
RGBPixel(50, 150, 50),
#RGBPixel(120, 120, 120),
#RGBPixel(250, 250, 0),
RGBPixel(0, 190, 255),
RGBPixel(230, 190, 20),
]
return _geometry.graph_color_ccs(image, ccs, colors, method)
__call__ = staticmethod(__call__)
class convex_hull_from_points(PluginFunction):
"""Returns the polygon vertices of the convex hull of the given list of
points.
The function uses Graham's scan algorithm as described e.g. in Cormen et al.:
*Introduction to Algorithms.* 2nd ed., MIT Press, p. 949, 2001
"""
self_type = None
args = Args([PointVector("points")])
return_type = PointVector("convexhull")
author = "Christian Brandt and Christoph Dalitz"
class convex_hull_as_points(PluginFunction):
"""Returns the vertex points of the convex hull of all black pixels
in the given image.
Actually not all black pixels are required for computing the convex hull,
but only the left and right contour pixels of the image. This follows
from the fact that, when a point is invisible both from the left and the
right, it lies on the connection axis between two visible points and thus
cannot be a vertex point of the convex hull.
"""
self_type = ImageType([ONEBIT])
args = Args([])
return_type = PointVector("convexhull")
author = "Christoph Dalitz"
class convex_hull_as_image(PluginFunction):
"""Returns an image containing the polygon of the convex hull calculated
by convex_hull_as_points_.
.. _convex_hull_as_points: geometry.html#convex_hull_as_points
"""
self_type = ImageType([ONEBIT])
args = Args([Check("filled",default=False)])
return_type = ImageType([ONEBIT])
author = "Christoph Dalitz"
doc_examples = [(ONEBIT,)]
def __call__(image, filled=False):
return _geometry.convex_hull_as_image(image, filled)
__call__ = staticmethod(__call__)
class GeometryModule(PluginModule):
cpp_headers = ["geometry.hpp"]
category = "Geometry"
import glob
cpp_sources=["src/geostructs/kdtree.cpp", "src/geostructs/delaunaytree.cpp"] + glob.glob("src/graph/*.cpp")
cpp_include_dirs=["include/graph/"]
functions = [voronoi_from_labeled_image,
voronoi_from_points,
labeled_region_neighbors,
delaunay_from_points,
graph_color_ccs,
convex_hull_from_points,
convex_hull_as_points,
convex_hull_as_image]
author = "Christoph Dalitz"
url = "http://gamera.sourceforge.net/"
module = GeometryModule()
delaunay_from_points = delaunay_from_points()
convex_hull_from_points = convex_hull_from_points()
|