Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve the breakpoint search time for the Mode 1 algorithm #8

Open
bajuwa opened this issue Mar 6, 2020 · 2 comments
Open

Improve the breakpoint search time for the Mode 1 algorithm #8

bajuwa opened this issue Mar 6, 2020 · 2 comments
Assignees
Labels
Comicom The main Comic Compiler script that performs the stitching enhancement New feature or request help wanted Extra attention is needed Testing For anything that requires new or updated automated tests

Comments

@bajuwa
Copy link
Owner

bajuwa commented Mar 6, 2020

Problem
The current BDM#1 ("Breakpoint Detection Mode #1") uses a brute force O(n) search method when trying to find a breakpoint. This can be slow if the images are long and there's not many opportunities to find a breakpoint.

Resolving this ticket may involve creating a new breakpoint mode instead of altering the existing mode 1.

Testing Conditions

  • Should be faster than the existing BDM#1 algorithm
  • Test input:
    • Use images with long unbroken art
    • Also try normal images that commonly start and end in breakpoints
    • Stress test: an all white image with a black vertical line along the left edge
@bajuwa bajuwa added the enhancement New feature or request label Mar 6, 2020
@bajuwa bajuwa self-assigned this Mar 6, 2020
@bajuwa bajuwa added the Comicom The main Comic Compiler script that performs the stitching label Mar 6, 2020
@bajuwa bajuwa added this to the Pre-Python milestone Mar 15, 2020
@bajuwa
Copy link
Owner Author

bajuwa commented Mar 17, 2020

Proposed Solution
After doing a simple 'does image start with breakpoint', proceed to use a binary search style algorithm that roughly follows these steps when trying to find breakpoints:

  1. Define 'chunk to check' as a text value using the imagemagick sample format "[WxH+WO+HO]"
  2. Retain a FILO list of 'chunks to check'
  3. Retain a single 'current chunk to check'
  4. Perform a 'vertical breakpoint detection' call on the whole image as a single chunk
    a. If the chunk contains a potential breakpoint, split the chunk in half, keep the first chunk as 'current chunk to check' and add the other to the 'chunks to check' list
    b. If the chunk does not contain a potential breakpoint, pop the last item (ie most recently added) off the 'chunks to check' list as the new 'current chunk to check'
  5. Repeat step 3 until either:
    a. The most recently checked chunk is $[Break Point Row Check Increments] pixels high or less. Check the top and middle rows of the chunk for explicit horizontal breakpoint. Skip checking bottom because that's essentially the same as checking the top of the next chunk. If check succeeds, return row number. If they all fail, treat the same as 3a
    b. both the 'current chunk to check' and the list are empty; in this case no breakpoint was found in the image

Variable can be removed: $BREAK_POINT_ROW_CHECK_BATCH_MULTIPLIER

I'm an idiot. This will provide a O(n^2) worst case run time instead of the existing O(n), and the likely frequency of the worst case happening is roughly equal between brute force and binary.

New proposed solution: just add 1 vertical full-height check for whitespace before proceeding with the existing brute force algorithm

@bajuwa bajuwa changed the title Improve BDM#1 to use a binary search style vertical detection algorithm Improve the breakpoint search time for the Mode 1 algorithm Mar 17, 2020
@bajuwa
Copy link
Owner Author

bajuwa commented Mar 17, 2020

That still didn't really help with the problematic tests/breakpoint-detection-mode/ test case. Deferring this ticket until later.

@bajuwa bajuwa removed this from the Pre-Python milestone Mar 17, 2020
@bajuwa bajuwa added the wontfix This will not be worked on label Mar 26, 2020
@bajuwa bajuwa removed the wontfix This will not be worked on label Apr 5, 2020
bajuwa added a commit that referenced this issue Apr 5, 2020
…st folder that's excluded from automated testing
@bajuwa bajuwa added the Testing For anything that requires new or updated automated tests label Apr 5, 2020
@bajuwa bajuwa added the help wanted Extra attention is needed label Apr 23, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Comicom The main Comic Compiler script that performs the stitching enhancement New feature or request help wanted Extra attention is needed Testing For anything that requires new or updated automated tests
Projects
None yet
Development

No branches or pull requests

1 participant