| Name | ncut-pytorch JSON |
| Version |
2.2.7
JSON |
| download |
| home_page | None |
| Summary | Normalized Cut and Spectral Embedding |
| upload_time | 2025-10-31 03:08:42 |
| maintainer | None |
| docs_url | None |
| author | None |
| requires_python | >=3 |
| license | None |
| keywords |
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
### [🌐Documentation (old version)](https://ncut-pytorch.readthedocs.io/) | [🤗HuggingFace Demo](https://huggingface.co/spaces/huzey/ncut-pytorch)
## Nyström Normalized Cut
Normalized Cut and spectral embedding, 100x faster than sklean implementation. $O(n)$ time complexity, $O(1)$ space complexity.
https://github.com/user-attachments/assets/cdf53e33-bb34-4a84-b1f4-679b66da1d48
<div align="center">
Video: Ncut spectral embedding eigenvectors, on SAM features.
</div>
---
## Installation
<div style="text-align:">
<pre><code class="language-shell">pip install -U ncut-pytorch</code></pre>
</div>
## Quick Start: plain Ncut
```py linenums="1"
import torch
from ncut_pytorch import Ncut
features = torch.rand(1960, 768)
eigvecs = Ncut(n_eig=20).fit_transform(features)
# (1960, 20)
from ncut_pytorch import kway_ncut
kway_eigvecs = kway_ncut(eigvecs)
cluster_assignment = kway_eigvecs.argmax(1)
cluster_centroids = kway_eigvecs.argmax(0)
```
## Quick Start: Ncut DINOv3 Predictor
```py linenums="1"
from ncut_pytorch.predictor import NcutDinov3Predictor
from PIL import Image
predictor = NcutDinov3Predictor(model_cfg="dinov3_vitl16")
predictor = predictor.to('cuda')
images = [Image.open(f"images/view_{i}.jpg") for i in range(4)]
predictor.set_images(images)
image = predictor.summary(n_segments=[10, 25, 50, 100], draw_border=True)
display(image)
```
More examples and detailed usage can be found in the `examples` directory.
## Performance
- `ncut_pytorch.Ncut` is $O(n)$ time complexity
- `sklearn.SpectralEmbedding` is $O(n^2)$ time complexity.
#### Setup:
CPU: Intel(R) Core(TM) i9-13900K CPU
RAM: 128 GiB
GPU: RTX 4090 24 GiB
SYSTEM: Ubuntu 22.04.3 LTS
#### Run benchmark:
```shell
pytest unit_tests/bench_speed.py --benchmark-columns=mean,stddev --benchmark-sort=mean
```
#### Results:
```
------------- benchmark 'ncut-pytorch (CPU) vs sklearn': 8 tests ------------
Name (time in ms) Mean StdDev
-----------------------------------------------------------------------------
test_ncut_cpu_100_data_10_eig 2.5536 (1.0) 0.2782 (1.0)
test_sklearn_100_data_10_eig 4.0913 (1.60) 1.6749 (6.02)
test_ncut_cpu_300_data_10_eig 4.9034 (1.92) 1.6575 (5.96)
test_sklearn_300_data_10_eig 10.1861 (3.99) 3.8870 (13.97)
test_ncut_cpu_1000_data_10_eig 11.1968 (4.38) 1.7070 (6.13)
test_ncut_cpu_3000_data_10_eig 38.6101 (15.12) 1.6379 (5.89)
test_sklearn_1000_data_10_eig 193.5934 (75.81) 8.1933 (29.45)
test_sklearn_3000_data_10_eig 1,246.4295 (488.11) 1,047.0191 (>1000.0)
-----------------------------------------------------------------------------
```
```
------------- benchmark 'ncut-pytorch (GPU) n_data': 5 tests -------------
Name (time in ms) Mean StdDev
--------------------------------------------------------------------------
test_ncut_gpu_100_data_10_eig 2.9564 (1.0) 0.1816 (1.0)
test_ncut_gpu_1000_data_10_eig 4.6938 (1.59) 0.3933 (2.17)
test_ncut_gpu_10000_data_10_eig 67.9607 (22.98) 4.0902 (22.52)
test_ncut_gpu_100000_data_10_eig 396.9994 (134.29) 3.6202 (19.93)
test_ncut_gpu_1000000_data_10_eig 798.4598 (270.08) 1.5704 (8.65)
--------------------------------------------------------------------------
```
```
------------- benchmark 'ncut-pytorch (GPU) n_eig': 3 tests --------------
Name (time in ms) Mean StdDev
--------------------------------------------------------------------------
test_ncut_gpu_10000_data_10_eig 67.9607 (1.0) 4.0902 (10.76)
test_ncut_gpu_10000_data_100_eig 74.0033 (1.09) 0.7856 (2.07)
test_ncut_gpu_10000_data_1000_eig 179.8690 (2.65) 0.3801 (1.0)
--------------------------------------------------------------------------
```
#### Run benchmark:
```shell
python unit_tests/bench_memory.py
```
#### Results:
`ncut-pytorch.Ncut` is $O(1)$ space complexity
```
+---------------+------------------------+
| Data Points | Peak GPU Memory (MB) |
+===============+========================+
| 1,000 | 8.14 |
+---------------+------------------------+
| 10,000 | 0.1 |
+---------------+------------------------+
| 100,000 | 0.39 |
+---------------+------------------------+
| 1,000,000 | 0.39 |
+---------------+------------------------+
```
## Citation
```
@misc{yang2024alignedcutvisualconceptsdiscovery,
title={AlignedCut: Visual Concepts Discovery on Brain-Guided Universal Feature Space},
author={Huzheng Yang and James Gee and Jianbo Shi},
year={2024},
eprint={2406.18344},
archivePrefix={arXiv},
primaryClass={cs.CV},
url={https://arxiv.org/abs/2406.18344},
}
```
Raw data
{
"_id": null,
"home_page": null,
"name": "ncut-pytorch",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3",
"maintainer_email": null,
"keywords": null,
"author": null,
"author_email": "Huzheng Yang <huze.yann@gmail.com>",
"download_url": "https://files.pythonhosted.org/packages/38/93/f1f9ff6a98398916ebf758831bfddb16b549c350e51acfb80e76cf81874c/ncut_pytorch-2.2.7.tar.gz",
"platform": null,
"description": "\n### [\ud83c\udf10Documentation (old version)](https://ncut-pytorch.readthedocs.io/) | [\ud83e\udd17HuggingFace Demo](https://huggingface.co/spaces/huzey/ncut-pytorch)\n\n\n## Nystr\u00f6m Normalized Cut\n\nNormalized Cut and spectral embedding, 100x faster than sklean implementation. $O(n)$ time complexity, $O(1)$ space complexity.\n\n\n\nhttps://github.com/user-attachments/assets/cdf53e33-bb34-4a84-b1f4-679b66da1d48\n\n\n\n\n<div align=\"center\">\n Video: Ncut spectral embedding eigenvectors, on SAM features.\n</div>\n\n\n---\n\n## Installation\n\n<div style=\"text-align:\">\n <pre><code class=\"language-shell\">pip install -U ncut-pytorch</code></pre>\n</div>\n\n\n## Quick Start: plain Ncut\n\n\n```py linenums=\"1\"\nimport torch\nfrom ncut_pytorch import Ncut\n\nfeatures = torch.rand(1960, 768)\neigvecs = Ncut(n_eig=20).fit_transform(features)\n # (1960, 20)\n\nfrom ncut_pytorch import kway_ncut\nkway_eigvecs = kway_ncut(eigvecs)\ncluster_assignment = kway_eigvecs.argmax(1)\ncluster_centroids = kway_eigvecs.argmax(0)\n```\n\n## Quick Start: Ncut DINOv3 Predictor\n\n```py linenums=\"1\"\nfrom ncut_pytorch.predictor import NcutDinov3Predictor\nfrom PIL import Image\n\npredictor = NcutDinov3Predictor(model_cfg=\"dinov3_vitl16\")\npredictor = predictor.to('cuda')\n\nimages = [Image.open(f\"images/view_{i}.jpg\") for i in range(4)]\npredictor.set_images(images)\n\nimage = predictor.summary(n_segments=[10, 25, 50, 100], draw_border=True)\ndisplay(image)\n\n```\n\n\n\n\n\nMore examples and detailed usage can be found in the `examples` directory.\n\n## Performance\n\n- `ncut_pytorch.Ncut` is $O(n)$ time complexity\n\n- `sklearn.SpectralEmbedding` is $O(n^2)$ time complexity.\n\n#### Setup:\n\nCPU: Intel(R) Core(TM) i9-13900K CPU\n\nRAM: 128 GiB\n\nGPU: RTX 4090 24 GiB\n\nSYSTEM: Ubuntu 22.04.3 LTS\n\n#### Run benchmark:\n\n\n```shell\npytest unit_tests/bench_speed.py --benchmark-columns=mean,stddev --benchmark-sort=mean\n```\n\n#### Results:\n\n```\n------------- benchmark 'ncut-pytorch (CPU) vs sklearn': 8 tests ------------\nName (time in ms) Mean StdDev \n-----------------------------------------------------------------------------\ntest_ncut_cpu_100_data_10_eig 2.5536 (1.0) 0.2782 (1.0) \ntest_sklearn_100_data_10_eig 4.0913 (1.60) 1.6749 (6.02) \ntest_ncut_cpu_300_data_10_eig 4.9034 (1.92) 1.6575 (5.96) \ntest_sklearn_300_data_10_eig 10.1861 (3.99) 3.8870 (13.97) \ntest_ncut_cpu_1000_data_10_eig 11.1968 (4.38) 1.7070 (6.13) \ntest_ncut_cpu_3000_data_10_eig 38.6101 (15.12) 1.6379 (5.89) \ntest_sklearn_1000_data_10_eig 193.5934 (75.81) 8.1933 (29.45) \ntest_sklearn_3000_data_10_eig 1,246.4295 (488.11) 1,047.0191 (>1000.0)\n-----------------------------------------------------------------------------\n```\n```\n------------- benchmark 'ncut-pytorch (GPU) n_data': 5 tests -------------\nName (time in ms) Mean StdDev \n--------------------------------------------------------------------------\ntest_ncut_gpu_100_data_10_eig 2.9564 (1.0) 0.1816 (1.0) \ntest_ncut_gpu_1000_data_10_eig 4.6938 (1.59) 0.3933 (2.17) \ntest_ncut_gpu_10000_data_10_eig 67.9607 (22.98) 4.0902 (22.52) \ntest_ncut_gpu_100000_data_10_eig 396.9994 (134.29) 3.6202 (19.93) \ntest_ncut_gpu_1000000_data_10_eig 798.4598 (270.08) 1.5704 (8.65) \n--------------------------------------------------------------------------\n```\n```\n------------- benchmark 'ncut-pytorch (GPU) n_eig': 3 tests --------------\nName (time in ms) Mean StdDev \n--------------------------------------------------------------------------\ntest_ncut_gpu_10000_data_10_eig 67.9607 (1.0) 4.0902 (10.76) \ntest_ncut_gpu_10000_data_100_eig 74.0033 (1.09) 0.7856 (2.07) \ntest_ncut_gpu_10000_data_1000_eig 179.8690 (2.65) 0.3801 (1.0) \n--------------------------------------------------------------------------\n```\n\n\n#### Run benchmark:\n\n```shell\npython unit_tests/bench_memory.py\n```\n\n#### Results:\n\n`ncut-pytorch.Ncut` is $O(1)$ space complexity\n\n```\n+---------------+------------------------+\n| Data Points | Peak GPU Memory (MB) |\n+===============+========================+\n| 1,000 | 8.14 |\n+---------------+------------------------+\n| 10,000 | 0.1 |\n+---------------+------------------------+\n| 100,000 | 0.39 |\n+---------------+------------------------+\n| 1,000,000 | 0.39 |\n+---------------+------------------------+\n```\n\n\n\n## Citation\n\n```\n@misc{yang2024alignedcutvisualconceptsdiscovery,\n title={AlignedCut: Visual Concepts Discovery on Brain-Guided Universal Feature Space}, \n author={Huzheng Yang and James Gee and Jianbo Shi},\n year={2024},\n eprint={2406.18344},\n archivePrefix={arXiv},\n primaryClass={cs.CV},\n url={https://arxiv.org/abs/2406.18344}, \n}\n```\n",
"bugtrack_url": null,
"license": null,
"summary": "Normalized Cut and Spectral Embedding",
"version": "2.2.7",
"project_urls": {
"Documentation": "https://ncut-pytorch.readthedocs.io/",
"Github": "https://github.com/huzeyann/ncut_pytorch/",
"PyPI": "https://pypi.org/project/ncut_pytorch/"
},
"split_keywords": [],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "d0063b5879d96bfbe8c1b23a91622b2c779499e3d346887a74bc69b62425e89f",
"md5": "015e8ca7806aac4b7751d40bd3f78291",
"sha256": "e22e8544b3deb93212236474d994ac5792dea5a5a8e3b5e488c557021399a64f"
},
"downloads": -1,
"filename": "ncut_pytorch-2.2.7-py3-none-any.whl",
"has_sig": false,
"md5_digest": "015e8ca7806aac4b7751d40bd3f78291",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3",
"size": 51672,
"upload_time": "2025-10-31T03:08:41",
"upload_time_iso_8601": "2025-10-31T03:08:41.500912Z",
"url": "https://files.pythonhosted.org/packages/d0/06/3b5879d96bfbe8c1b23a91622b2c779499e3d346887a74bc69b62425e89f/ncut_pytorch-2.2.7-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "3893f1f9ff6a98398916ebf758831bfddb16b549c350e51acfb80e76cf81874c",
"md5": "1b606d120a3fca1d5ddeadf6f4357e50",
"sha256": "86b33a4ba90507ff20e7e5f53636a90257010387c124294c1f0decbce5579bc3"
},
"downloads": -1,
"filename": "ncut_pytorch-2.2.7.tar.gz",
"has_sig": false,
"md5_digest": "1b606d120a3fca1d5ddeadf6f4357e50",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3",
"size": 44800,
"upload_time": "2025-10-31T03:08:42",
"upload_time_iso_8601": "2025-10-31T03:08:42.454925Z",
"url": "https://files.pythonhosted.org/packages/38/93/f1f9ff6a98398916ebf758831bfddb16b549c350e51acfb80e76cf81874c/ncut_pytorch-2.2.7.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-10-31 03:08:42",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "huzeyann",
"github_project": "ncut_pytorch",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "ncut-pytorch"
}
